Que signifie exactement O (log n)?

J'apprends les temps de fonctionnement et les temps amortis de Big O Notation. Je comprends la notion de temps linéaire O (n) , ce qui signifie que la taille de l'entrée affecte la croissance de l'algorithme proportionnellement ... et il en va de même pour, par exemple, le temps quadratique O (n ² ), etc. , comme les générateurs de permutation, avec O (n!) fois, qui croissent par factorielles.

Par exemple, la fonction suivante est O (n) car l'algorithme croît proportionnellement à son entrée n :

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

De même, s'il y avait une boucle imbriquée, le temps serait O (n ² ).

Mais qu'est-ce que O (log n) exactement ? Par exemple, que signifie dire que la hauteur d'un arbre binaire complet est O (log n) ?

Je sais (peut-être pas trop en détail) ce qu'est le logarithme, dans le sens où: log ₁₀ 100 = 2, mais je ne comprends pas comment identifier une fonction avec un temps logarithmique.

Je ne comprends pas comment identifier une fonction avec une heure de journal.

Les attributs les plus courants de la fonction d'exécution logarithmique sont les suivants:

• le choix de l'élément suivant sur lequel effectuer une action est l'une des nombreuses possibilités, et
• un seul devra être choisi.

ou

• les éléments sur lesquels l'action est effectuée sont des chiffres de n

C'est pourquoi, par exemple, rechercher des personnes dans un annuaire téléphonique est O (log n). Vous n'avez pas besoin de vérifier chaque personne dans l'annuaire pour trouver la bonne personne; au lieu de cela, vous pouvez simplement diviser pour mieux régner en recherchant en fonction de la position alphabétique de son nom, et dans chaque section, il vous suffit d'explorer un sous-ensemble de chaque section avant de finalement trouver le numéro de téléphone de quelqu'un.

Bien sûr, un annuaire téléphonique plus long vous prendra encore plus de temps, mais il n'augmentera pas aussi rapidement que l'augmentation proportionnelle de la taille supplémentaire.

Nous pouvons étendre l'exemple de l'annuaire téléphonique pour comparer d'autres types d'opérations et leur durée d'exécution. Nous supposerons que notre annuaire téléphonique comporte des entreprises (les "Pages jaunes") qui ont des noms uniques et des personnes (les "Pages blanches") qui peuvent ne pas avoir de noms uniques. Un numéro de téléphone est attribué à au plus une personne ou une entreprise. Nous supposerons également qu'il faut un temps constant pour passer à une page spécifique.

Voici les temps d'exécution de certaines opérations que nous pourrions effectuer sur l'annuaire téléphonique, du plus rapide au plus lent:

• O (1) (dans le pire des cas): étant donné la page sur laquelle se trouve le nom d'une entreprise et le nom de l'entreprise, recherchez le numéro de téléphone.

• O (1) (dans le cas moyen): Étant donné la page sur laquelle se trouve le nom d'une personne et son nom, recherchez le numéro de téléphone.

• O (log n): Étant donné le nom d'une personne, trouvez le numéro de téléphone en choisissant un point au hasard à mi-chemin dans la partie du livre que vous n'avez pas encore recherchée, puis vérifiez si le nom de la personne est à ce point. Répétez ensuite le processus à mi-chemin de la partie du livre où se trouve le nom de la personne. (Il s'agit d'une recherche binaire du nom d'une personne.)

• O (n): recherchez toutes les personnes dont les numéros de téléphone contiennent le chiffre "5".

• O (n): Étant donné un numéro de téléphone, recherchez la personne ou l'entreprise avec ce numéro.

• O (n log n): Il y a eu une confusion au bureau de l'imprimante, et notre annuaire téléphonique avait toutes ses pages insérées dans un ordre aléatoire. Corrigez l'ordre afin qu'il soit correct en regardant le prénom sur chaque page, puis en plaçant cette page à l'endroit approprié dans un nouvel annuaire téléphonique vide.

Pour les exemples ci-dessous, nous sommes maintenant au bureau de l'imprimante. Les annuaires téléphoniques attendent d'être envoyés par la poste à chaque résident ou entreprise, et il y a un autocollant sur chaque annuaire téléphonique indiquant où il doit être envoyé. Chaque personne ou entreprise reçoit un annuaire téléphonique.

• O (n log n): Nous voulons personnaliser l'annuaire téléphonique, nous allons donc trouver le nom de chaque personne ou entreprise dans leur copie désignée, puis encercler leur nom dans le livre et écrire une courte note de remerciement pour leur patronage .

• O (n ² ): Une erreur s'est produite au bureau et chaque entrée dans chacun des annuaires téléphoniques a un "0" supplémentaire à la fin du numéro de téléphone. Prenez un peu de blanc et retirez chaque zéro.

• O (n · n!): Nous sommes prêts à charger les répertoires téléphoniques sur le quai d'expédition. Malheureusement, le robot qui était censé charger les livres est devenu détraqué: il place les livres dans le camion dans un ordre aléatoire! Pire encore, il charge tous les livres dans le camion, puis vérifie s'ils sont dans le bon ordre, et sinon, il les décharge et recommence. (C'est le genre de bogo redouté .)

• O (n ⁿ ): vous réparez le robot pour qu'il charge correctement les objets. Le lendemain, l'un de vos collègues vous fait une farce et connecte le robot du quai de chargement aux systèmes d'impression automatisés. Chaque fois que le robot va charger un livre original, l'imprimante d'usine fait une copie de tous les répertoires! Heureusement, les systèmes de détection de bogues du robot sont suffisamment sophistiqués pour que le robot n'essaie pas d'imprimer encore plus de copies lorsqu'il rencontre un livre en double pour le chargement, mais il doit toujours charger chaque livre original et en double qui a été imprimé.

O(log N)signifie essentiellement que le temps augmente linéairement tandis que le naugmente de façon exponentielle. Donc, s'il faut deux 1secondes pour calculer les 10éléments, il faudra des 2secondes pour calculer les 100éléments, des 3secondes pour calculer les 1000éléments, etc.

C'est O(log n)lorsque nous divisons et conquérons des types d'algorithmes, par exemple la recherche binaire. Un autre exemple est le tri rapide où chaque fois que nous divisons le tableau en deux parties et chaque fois qu'il faut du O(N)temps pour trouver un élément pivot. D'où N O(log N)

Beaucoup de bonnes réponses ont déjà été postées à cette question, mais je pense qu'il nous manque vraiment une réponse importante - à savoir la réponse illustrée.

Que signifie dire que la hauteur d'un arbre binaire complet est O (log n)?

Le dessin suivant représente un arbre binaire. Remarquez comment chaque niveau contient le double du nombre de nœuds par rapport au niveau supérieur (d'où binaire ):

La recherche binaire est un exemple de complexité O(log n). Disons que les nœuds au niveau inférieur de l'arborescence de la figure 1 représentent des éléments dans une collection triée. La recherche binaire est un algorithme de division et de conquête, et le dessin montre comment nous aurons besoin (au plus) de 4 comparaisons pour trouver l'enregistrement que nous recherchons dans cet ensemble de données de 16 éléments.

Supposons que nous avions à la place un ensemble de données avec 32 éléments. Continuez le dessin ci-dessus pour trouver que nous aurons maintenant besoin de 5 comparaisons pour trouver ce que nous recherchons, car l'arbre n'a augmenté que d'un niveau plus profond lorsque nous avons multiplié la quantité de données. En conséquence, la complexité de l'algorithme peut être décrite comme un ordre logarithmique.

Le traçage log(n)sur une feuille de papier ordinaire se traduira par un graphique où la montée de la courbe ralentit à nmesure que les augmentations:

L'explication ci-dessous utilise le cas d'un arbre binaire entièrement équilibré pour vous aider à comprendre comment nous obtenons la complexité temporelle logarithmique.

L'arbre binaire est un cas où un problème de taille n est divisé en sous-problème de taille n / 2 jusqu'à atteindre un problème de taille 1:

Et c'est ainsi que vous obtenez O (log n) qui est la quantité de travail qui doit être effectuée sur l'arborescence ci-dessus pour trouver une solution.

Un algorithme commun avec une complexité temporelle O (log n) est la recherche binaire dont la relation récursive est T (n / 2) + O (1), c'est-à-dire qu'à chaque niveau suivant de l'arbre, vous divisez le problème en deux et effectuez une quantité de travail supplémentaire constante.

Aperçu

D'autres ont donné de bons exemples de diagrammes, tels que les diagrammes d'arbre. Je n'ai vu aucun exemple de code simple. Donc, en plus de mon explication, je fournirai quelques algorithmes avec des instructions d'impression simples pour illustrer la complexité des différentes catégories d'algorithmes.

Tout d'abord, vous voudrez avoir une idée générale du logarithme, que vous pouvez obtenir sur https://en.wikipedia.org/wiki/Logarithm . Utilisation des sciences naturelles eet logarithme naturel. Les disciples du génie utiliseront log_10 (base de journal 10) et les informaticiens utiliseront beaucoup log_2 (base de journal 2), car les ordinateurs sont basés sur le binaire. Parfois, vous verrez des abréviations de log naturel comme ln(), les ingénieurs laissent normalement le _10 éteint et utilisent simplement log()et log_2 est abrégé en lg(). Tous les types de logarithmes se développent de manière similaire, c'est pourquoi ils partagent la même catégorie de log(n).

Lorsque vous regardez les exemples de code ci-dessous, je recommande de regarder O (1), puis O (n), puis O (n ^ 2). Une fois que vous êtes bon avec ceux-ci, regardez les autres. J'ai inclus des exemples clairs ainsi que des variations pour montrer comment des changements subtils peuvent toujours entraîner la même catégorisation.

Vous pouvez considérer O (1), O (n), O (logn), etc. comme des classes ou des catégories de croissance. Certaines catégories prendront plus de temps que d'autres. Ces catégories nous permettent de classer les performances de l'algorithme. Certains se sont développés plus rapidement à mesure que l'entrée n augmente. Le tableau suivant montre numériquement cette croissance. Dans le tableau ci-dessous, considérez log (n) comme le plafond de log_2.

Exemples de codes simples de diverses catégories Big O:

O (1) - Exemples à temps constant:

• Algorithme 1:

L'algorithme 1 s'imprime bonjour une fois et ne dépend pas de n, il s'exécutera donc toujours en temps constant O(1).

print "hello";

• Algorithme 2:

L'algorithme 2 s'imprime bonjour 3 fois, mais il ne dépend pas d'une taille d'entrée. Même à mesure que n grandit, cet algorithme n'imprimera toujours bonjour que 3 fois. Cela étant dit 3, est une constante, donc cet algorithme l'est aussi O(1).

print "hello";
print "hello";
print "hello";

O (log (n)) - Exemples logarithmiques:

• Algorithme 3 - Cela agit comme "log_2"

L'algorithme 3 illustre un algorithme qui s'exécute dans log_2 (n). Remarquez la post-opération de la boucle for multiple la valeur actuelle de i par 2, donc iva de 1 à 2 à 4 à 8 à 16 à 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";

• Algorithme 4 - Cela agit comme "log_3"

L'algorithme 4 illustre log_3. L'avis iva de 1 à 3 à 9 à 27 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";

• Algorithme 5 - Cela agit comme "log_1.02"

L'algorithme 5 est important, car il permet de montrer que tant que le nombre est supérieur à 1 et que le résultat est multiplié à plusieurs reprises contre lui-même, vous regardez un algorithme logarithmique.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O (n) - Exemples de temps linéaire:

• Algorithme 6

Cet algorithme est simple, qui s'imprime bonjour n fois.

for(int i = 0; i < n; i++)
  print "hello";

• Algorithme 7

Cet algorithme montre une variation, où il s'imprimera bonjour n / 2 fois. n / 2 = 1/2 * n. Nous ignorons la constante 1/2 et voyons que cet algorithme est O (n).

for(int i = 0; i < n; i = i + 2)
  print "hello";

O (n * log (n)) - nlog (n) Exemples:

• Algorithme 8

Considérez cela comme une combinaison de O(log(n))et O(n). L'imbrication des boucles for nous aide à obtenir leO(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";

• Algorithme 9

L'algorithme 9 est comme l'algorithme 8, mais chacune des boucles a permis des variations, ce qui a pour résultat que le résultat final est O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O (n ^ 2) - n au carré Exemples:

• Algorithme 10

O(n^2) s'obtient facilement en imbriquant un standard pour les boucles.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";

• Algorithme 11

Comme l'algorithme 10, mais avec quelques variantes.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O (n ^ 3) - n cubes Exemples:

• Algorithme 12

C'est comme l'algorithme 10, mais avec 3 boucles au lieu de 2.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";

• Algorithme 13

Comme l'algorithme 12, mais avec quelques variations qui donnent toujours O(n^3).

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

Sommaire

Ce qui précède donne plusieurs exemples simples et des variations pour aider à démontrer quels changements subtils peuvent être introduits qui ne changent vraiment pas l'analyse. J'espère que cela vous donnera suffisamment d'informations.

Si vous aviez une fonction qui prend:

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2^n elements.

Ensuite, cela prend du temps log ₂ (n). La notation Big O , en gros, signifie que la relation ne doit être vraie que pour les grands n, et que les facteurs constants et les termes plus petits peuvent être ignorés.

Le temps d'exécution logarithmique ( O(log n)) signifie essentiellement que le temps d'exécution augmente proportionnellement au logarithme de la taille d'entrée - par exemple, si 10 éléments prennent au maximum un certain temps x, et 100 éléments prennent au maximum, disons 2x, et 10000 éléments prend tout au plus 4x, alors ça ressemble à une O(log n)complexité temporelle.

Le logarithme

Ok, essayons de bien comprendre ce qu'est un logarithme.

Imaginez que nous avons une corde et que nous l'avons attachée à un cheval. Si la corde est directement attachée au cheval, la force que le cheval devrait retirer (par exemple, d'un homme) est directement 1.

Imaginez maintenant que la corde soit enroulée autour d'un poteau. Le cheval qui s'éloignera devra maintenant tirer plusieurs fois plus fort. Le nombre de fois dépendra de la rugosité de la corde et de la taille du poteau, mais supposons que cela multipliera sa force par 10 (lorsque la corde fait un tour complet).

Maintenant, si la corde est bouclée une fois, le cheval devra tirer 10 fois plus fort. Si l'humain décide de rendre les choses vraiment difficiles pour le cheval, il peut à nouveau enrouler la corde autour d'un poteau, augmentant sa force de 10 fois supplémentaires. Une troisième boucle augmentera à nouveau la force de 10 fois.

Nous pouvons voir que pour chaque boucle, la valeur augmente de 10. Le nombre de tours requis pour obtenir n'importe quel nombre est appelé le logarithme du nombre, c'est-à-dire que nous avons besoin de 3 postes pour multiplier votre force par 1000 fois, 6 postes pour multiplier votre force par 1 000 000.

3 est le logarithme de 1 000 et 6 est le logarithme de 1 000 000 (base 10).

Que signifie donc O (log n)?

Dans notre exemple ci-dessus, notre «taux de croissance» est O (log n) . Pour chaque boucle supplémentaire, la force que notre corde peut gérer est 10 fois plus:

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

Maintenant, l'exemple ci-dessus a utilisé la base 10, mais heureusement, la base du journal est insignifiante lorsque nous parlons de la notation du grand o.

Imaginons maintenant que vous essayez de deviner un nombre compris entre 1 et 100.

Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!  

Maintenant, il vous a fallu 7 suppositions pour bien faire les choses. Mais quelle est la relation ici? Quel est le plus grand nombre d'articles que vous pouvez deviner à partir de chaque supposition supplémentaire?

Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024

En utilisant le graphique, nous pouvons voir que si nous utilisons une recherche binaire pour deviner un nombre compris entre 1 et 100, cela nous prendra au plus 7 tentatives. Si nous avions 128 nombres, nous pourrions également deviner le nombre en 7 tentatives, mais 129 nombres nous prendront au plus 8 tentatives (en relation avec les logarithmes, ici nous aurions besoin de 7 suppositions pour une plage de 128 valeurs, 10 suppositions pour une plage de 1024 valeurs 7 est le logarithme de 128, 10 est le logarithme de 1024 (base 2)).

Notez que j'ai mis en gras «tout au plus». La notation Big-O fait toujours référence au pire des cas. Si vous êtes chanceux, vous pourriez deviner le nombre en une seule tentative et donc le meilleur cas est O (1), mais c'est une autre histoire.

Nous pouvons voir que pour chaque supposition, notre ensemble de données diminue. Une bonne règle de base pour identifier si un algorithme a un temps logarithmique consiste à voir si l'ensemble de données diminue d'un certain ordre après chaque itération

Et O (n log n)?

Vous rencontrerez éventuellement un algorithme O temps linéaire (n log (n)) . La règle générale ci-dessus s'applique à nouveau, mais cette fois, la fonction logarithmique doit s'exécuter n fois, par exemple en réduisant la taille d'une liste n fois , ce qui se produit dans des algorithmes comme un mergesort.

Vous pouvez facilement identifier si le temps algorithmique est n log n. Recherchez une boucle externe qui itère dans une liste (O (n)). Ensuite, regardez s'il y a une boucle intérieure. Si la boucle interne coupe / réduit l'ensemble de données à chaque itération, cette boucle est (O (log n)), et donc l'algorithme global est = O (n log n) .

Avertissement: L'exemple du logarithme de la corde a été tiré de l'excellent livre Delight du mathématicien de W.Sawyer .

Vous pouvez penser à O (log N) intuitivement en disant que le temps est proportionnel au nombre de chiffres dans N.

Si une opération effectue un travail à temps constant sur chaque chiffre ou bit d'une entrée, l'opération entière prendra un temps proportionnel au nombre de chiffres ou de bits dans l'entrée, et non à l'amplitude de l'entrée; ainsi, O (log N) plutôt que O (N).

Si une opération prend une série de décisions à temps constant dont chacune réduit de moitié (réduit d'un facteur 3, 4, 5 ..) la taille de l'entrée à considérer, l'ensemble prendra un temps proportionnel au log base 2 (base 3 , base 4, base 5 ...) de la taille N de l'entrée, plutôt que d'être O (N).

Etc.

La meilleure façon dont j'ai toujours eu à visualiser mentalement un algorithme qui s'exécute en O (log n) est la suivante:

Si vous augmentez la taille du problème d'une quantité multiplicative (c'est-à-dire multipliez sa taille par 10), le travail n'est augmenté que d'une quantité additive.

En appliquant cela à votre question d'arbre binaire, vous avez donc une bonne application: si vous doublez le nombre de nœuds dans un arbre binaire, la hauteur n'augmente que de 1 (une quantité additive). Si vous le doublez à nouveau, il n'a encore augmenté que de 1. (Évidemment, je suppose qu'il reste équilibré et tel). De cette façon, au lieu de doubler votre travail lorsque la taille du problème est multipliée, vous ne faites que très légèrement plus de travail. C'est pourquoi les algorithmes O (log n) sont géniaux.

Je vous recommande d'abord de lire le livre suivant;

Algorithmes (4e édition)

Voici quelques fonctions et leurs complexités attendues. Les nombres indiquent les fréquences d'exécution des instructions .

Le graphique de complexité Big-O est également tiré de bigocheatsheet

Enfin une vitrine très simple montre comment il est calculé;

Anatomie des fréquences d'exécution des instructions d'un programme.

Analyse du temps d'exécution d'un programme (exemple).

Qu'est-ce que le log _b (n)?

C'est le nombre de fois que vous pouvez couper un journal de longueur n à plusieurs reprises en b parties égales avant d'atteindre une section de taille 1.

Les algorithmes de division et de conquête ont généralement un logncomposant pour le temps d'exécution. Cela vient de la réduction de moitié répétée de l'entrée.

Dans le cas d'une recherche binaire, à chaque itération, vous jetez la moitié de l'entrée. Il convient de noter qu'en notation Big-O, log est log base 2.

Edit: Comme indiqué, la base de journal n'a pas d'importance, mais lors de la dérivation des performances Big-O d'un algorithme, le facteur de journal proviendra de la réduction de moitié, d'où la raison pour laquelle je le considère comme la base 2.

Mais qu'est-ce que O (log n) exactement? Par exemple, que signifie dire que la hauteur d'un> arbre binaire complet est O (log n)?

Je reformulerais ceci comme «la hauteur d'un arbre binaire complet est log n». Calculer la hauteur d'un arbre binaire complet serait O (log n), si vous descendiez pas à pas.

Je ne peux pas comprendre comment identifier une fonction avec un temps logarithmique.

Le logarithme est essentiellement l'inverse de l'exponentiation. Donc, si chaque «étape» de votre fonction élimine un facteur d'éléments de l'ensemble d'éléments d'origine, c'est un algorithme de temps logarithmique.

Pour l'exemple de l'arborescence, vous pouvez facilement voir que la réduction d'un niveau de nœuds réduit un nombre exponentiel d'éléments lorsque vous continuez à parcourir. L'exemple populaire de recherche dans un annuaire téléphonique trié par nom est essentiellement équivalent à parcourir un arbre de recherche binaire (la page du milieu est l'élément racine, et vous pouvez déduire à chaque étape si vous allez à gauche ou à droite).

Ces 2 cas prendront du temps O (log n)

case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }


 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }

O (log n) est un peu trompeur, plus précisément c'est O (log ₂ n), c'est-à-dire (logarithme avec base 2).

La hauteur d'un arbre binaire équilibré est O (log ₂ n), car chaque nœud a deux (notez les "deux" comme dans le journal ₂ n) nœuds enfants. Ainsi, un arbre à n nœuds a une hauteur de log ₂ n.

Un autre exemple est la recherche binaire, qui a un temps d'exécution de O (log ₂ n) car à chaque étape, vous divisez l'espace de recherche par 2.

O(log n) fait référence à une fonction (ou algorithme, ou étape d'un algorithme) fonctionnant dans un laps de temps proportionnel au logarithme (généralement en base 2 dans la plupart des cas, mais pas toujours, et en tout état de cause, cela n'est pas significatif par la notation big-O *) de la taille de l'entrée.

La fonction logarithmique est l'inverse de la fonction exponentielle. Autrement dit, si votre entrée croît de façon exponentielle (plutôt que de façon linéaire, comme vous le pensez normalement), votre fonction se développe de façon linéaire.

O(log n)les temps d'exécution sont très courants dans toute sorte d'application de division et de conquête, car vous coupez (idéalement) le travail en deux à chaque fois. Si dans chacune des étapes de division ou de conquête, vous effectuez un travail à temps constant (ou un travail qui n'est pas à temps constant, mais avec un temps qui croît plus lentement que O(log n)), alors votre fonction entière l'est O(log n). Il est assez courant que chaque étape nécessite un temps linéaire à la place; cela équivaudra à une complexité temporelle totale de O(n log n).

La complexité du temps d'exécution de la recherche binaire en est un exemple O(log n). En effet, dans la recherche binaire, vous ignorez toujours la moitié de votre entrée à chaque étape ultérieure en divisant le tableau en deux et en vous concentrant uniquement sur une moitié à chaque étape. Chaque étape est à temps constant, car dans la recherche binaire, vous n'avez qu'à comparer un élément avec votre clé afin de savoir quoi faire ensuite, quelle que soit la taille du tableau que vous envisagez à tout moment. Vous effectuez donc approximativement les étapes log (n) / log (2).

La complexité du temps de fonctionnement du tri par fusion en est un exemple O(n log n). Cela est dû au fait que vous divisez le tableau en deux à chaque étape, ce qui donne un total d'environ log (n) / log (2) étapes. Cependant, à chaque étape, vous devez effectuer des opérations de fusion sur tous les éléments (qu'il s'agisse d'une opération de fusion sur deux sous-listes d'éléments n / 2 ou de deux opérations de fusion sur quatre sous-listes d'éléments n / 4, cela n'a pas d'importance car cela ajoute à la nécessité de faire cela pour n éléments à chaque étape). Ainsi, la complexité totale est O(n log n).

* N'oubliez pas que la notation big-O, par définition , n'a pas d'importance. De même, par le changement de règle de base pour les logarithmes, la seule différence entre les logarithmes de différentes bases est un facteur constant.

Cela signifie simplement que le temps nécessaire à cette tâche augmente avec log (n) (exemple: 2s pour n = 10, 4s pour n = 100, ...). Lisez les articles de Wikipedia sur l' algorithme de recherche binaire et la notation Big O pour plus de précisions.

Autrement dit: à chaque étape de votre algorithme, vous pouvez réduire le travail de moitié. (Asymptotiquement équivalent aux troisième, quatrième, ...)

Si vous tracez une fonction logarithmique sur une calculatrice graphique ou quelque chose de similaire, vous verrez qu'elle augmente très lentement - encore plus lentement qu'une fonction linéaire.

C'est pourquoi les algorithmes à complexité logarithmique temporelle sont très recherchés: même pour de très gros n (disons n = 10 ^ 8, par exemple), ils fonctionnent plus qu'acceptablement.

Mais quel est exactement O (log n)

Ce que cela signifie précisément, c'est "comme ntend vers infinity, le timetend vers a*log(n)où aest un facteur d'échelle constant".

Ou en fait, cela ne signifie pas tout à fait cela; plus probablement, cela signifie quelque chose comme " timedivisé par a*log(n)tend vers 1".

"Tends vers" a le sens mathématique habituel de 'analyse': par exemple, que "si vous choisissez n'importe quelle constante non nulle arbitrairement petite k, alors je peux trouver une valeur correspondante Xtelle qu'elle ((time/(a*log(n))) - 1)soit inférieure à celle kde toutes les valeurs nsupérieures à X."

En termes simples, cela signifie que l'équation du temps peut avoir d'autres composants: par exemple, elle peut avoir un temps de démarrage constant; mais ces autres composantes pâle vers l'insignifiance pour les grandes valeurs de n, et le a * log (n) est le terme dominant pour le grand n.

Notez que si l'équation était, par exemple ...

temps (n) = a + b log (n) + c n + d n n

... alors ce serait O (n au carré) car, quelles que soient les valeurs des constantes a, b, c et d non nulles, le d*n*nterme dominerait toujours les autres pour toute valeur suffisamment grande de n.

C'est ce que signifie la notation du bit O: cela signifie "quel est l'ordre de terme dominant pour tout n suffisamment grand".

Je peux ajouter quelque chose d'intéressant, que j'ai lu il y a longtemps dans un livre de Kormen et etc. Maintenant, imaginez un problème, où nous devons trouver une solution dans un espace à problème. Cet espace problématique doit être fini.

Maintenant, si vous pouvez prouver qu'à chaque itération de votre algorithme, vous coupez une fraction de cet espace, ce qui n'est pas moins qu'une certaine limite, cela signifie que votre algorithme s'exécute en temps O (logN).

Je dois souligner que nous parlons ici d'une limite de fraction relative, pas absolue. La recherche binaire est un exemple classique. À chaque étape, nous jetons la moitié de l'espace problématique. Mais la recherche binaire n'est pas le seul exemple de ce genre. Supposons que vous ayez prouvé d'une manière ou d'une autre qu'à chaque étape, vous jetez au moins 1/128 d'espace problématique. Cela signifie que votre programme est toujours en cours d'exécution au moment O (logN), bien que beaucoup plus lent que la recherche binaire. C'est un très bon indice pour l'analyse d'algorithmes récursifs. Il peut souvent être prouvé qu'à chaque étape la récursivité n'utilisera pas plusieurs variantes, ce qui conduit à la coupure d'une fraction dans l'espace du problème.

Je peux donner un exemple de boucle for et peut-être une fois saisi le concept, il sera peut-être plus simple à comprendre dans différents contextes.

Cela signifie que dans la boucle, le pas croît de façon exponentielle. Par exemple

for (i=1; i<=n; i=i*2) {;}

La complexité en notation O de ce programme est O (log (n)). Essayons de le parcourir à la main (n étant compris entre 512 et 1023 (à l'exception de 1024):

step: 1   2   3   4   5    6    7    8     9     10
   i: 1   2   4   8   16   32   64   128   256   512

Bien que n soit compris entre 512 et 1023, seulement 10 itérations ont lieu. En effet, le pas dans la boucle croît de façon exponentielle et ne prend donc que 10 itérations pour atteindre la terminaison.

Le logarithme de x (à la base de a) est la fonction inverse de a ^ x.

C'est comme dire que le logarithme est l'inverse de l'exponentielle.

Essayez maintenant de voir les choses de cette façon, si l'exponentielle croît très rapidement, le logarithme croît (inversement) très lentement.

La différence entre O (n) et O (log (n)) est énorme, similaire à la différence entre O (n) et O (a ^ n) (a étant une constante).

En fait, si vous avez une liste de n éléments et créez un arbre binaire à partir de cette liste (comme dans l'algorithme de division et de conquête), vous continuerez à diviser par 2 jusqu'à atteindre des listes de taille 1 (les feuilles).

À la première étape, vous divisez par 2. Vous avez alors 2 listes (2 ^ 1), vous divisez chacune par 2, vous avez donc 4 listes (2 ^ 2), vous divisez à nouveau, vous avez 8 listes (2 ^ 3 ) et ainsi de suite jusqu'à ce que la taille de votre liste soit 1

Cela vous donne l'équation:

n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps

(vous prenez le lg de chaque côté, lg étant la base du journal 2)

Chaque fois que nous écrivons un algorithme ou un code, nous essayons d'analyser sa complexité asymptotique. Il est différent de sa complexité temporelle .

La complexité asymptotique est le comportement du temps d'exécution d'un algorithme tandis que la complexité temporelle est le temps d'exécution réel. Mais certaines personnes utilisent ces termes de manière interchangeable.

Parce que la complexité temporelle dépend de divers paramètres à savoir.
1. Système physique
2. Langage de programmation
3. Style de codage
4. Et bien plus encore ......

Le temps d'exécution réel n'est pas une bonne mesure pour l'analyse.

Au lieu de cela, nous prenons la taille d'entrée comme paramètre, car quel que soit le code, l'entrée est la même. Le temps d'exécution est donc fonction de la taille d'entrée.

Voici un exemple d'algorithme de temps linéaire

Recherche linéaire
Étant donné n éléments d'entrée, pour rechercher un élément dans le tableau, vous avez besoin d' au plus 'n' comparaisons . En d'autres termes, quel que soit le langage de programmation que vous utilisez, le style de codage que vous préférez, le système sur lequel vous l'exécutez. Dans le pire des cas, il ne nécessite que n comparaisons. Le temps d'exécution est linéairement proportionnel à la taille d'entrée.

Et ce n'est pas seulement une recherche, quel que soit le travail (incrémenter, comparer ou n'importe quelle opération), c'est une fonction de la taille d'entrée.

Ainsi, lorsque vous dites qu'un algorithme est O (log n), cela signifie que le temps d'exécution est log fois la taille d'entrée n.

À mesure que la taille d'entrée augmente, le travail effectué (ici le temps d'exécution) augmente (d'où la proportionnalité).

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

Voyez comme la taille d'entrée a augmenté, le travail effectué est augmenté et il est indépendant de toute machine. Et si vous essayez de découvrir la valeur des unités de travail, cela dépend en fait de ces paramètres spécifiés ci-dessus. Cela changera en fonction des systèmes et de tout.

log x to base b = y est l'inverse de b^y = x

Si vous avez un arbre M-aire de profondeur d et de taille n, alors:

• traversant l'arbre entier ~ O (M ^ d) = O (n)

• Marcher un seul chemin dans l'arbre ~ O (d) = O (log n à la base M)

En technologie de l'information, cela signifie que:

  f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, 
  such that
  for all N>N0  "C*g(n) > f(n) > 0" is true.

Et il semble que cette notation ait été principalement empruntée aux mathématiques.

Dans cet article, il y a une citation: DE Knuth, "BIG OMICRON ET BIG OMEGA ET BIG THETA", 1976 :

Sur la base des questions discutées ici, je propose que les membres de SIGACT et les rédacteurs en chef des revues d'informatique et de mathématiques adoptent les notations définies ci-dessus, à moins qu'une meilleure alternative ne puisse être trouvée assez rapidement .

Aujourd'hui, c'est 2016, mais nous l'utilisons encore aujourd'hui.

En analyse mathématique, cela signifie que:

  lim (f(n)/g(n))=Constant; where n goes to +infinity

Mais même dans l'analyse mathématique, ce symbole était parfois utilisé pour signifier "C * g (n)> f (n)> 0".

Comme je le sais de l'université, le symbole a été introduit par le mathématicien allemand Landau (1877-1938)

L'exemple binaire complet est O (ln n) car la recherche ressemble à ceci:

1 2 3 4 5 6 7 8 9 10 11 12

La recherche de 4 donne 3 résultats: 6, 3 puis 4. Et log2 12 = 3, ce qui correspond bien au nombre de résultats lorsque cela est nécessaire.

Si vous cherchez une réponse basée sur l'intuition, j'aimerais vous proposer deux interprétations.

1. Imaginez une colline très haute avec une base très large également. Pour atteindre le sommet de la colline, il y a deux façons: l'une est un chemin dédié qui tourne en spirale autour de la colline pour atteindre le sommet, l'autre: une petite terrasse comme des sculptures découpées pour fournir un escalier. Or si la première voie atteint en temps linéaire O (n), la seconde est O (log n).

2. Imaginez un algorithme, qui accepte un entier, ncomme entrée et se termine en temps proportionnel à nalors il est O (n) ou thêta (n) mais s'il s'exécute en proportion temporelle à number of digits or the number of bits in the binary representation on numberalors l'algorithme s'exécute en O (log n) ou thêta (log n) temps.

Les algorithmes du paradigme Divide and Conquer sont de complexité O (logn). Un exemple ici, calculez votre propre fonction de puissance,

int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

depuis http://www.geeksforgeeks.org/write-ac-program-to-calculate-powxn/