Que signifie exactement O(log n) ?

Question

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

Par exemple, la fonction suivante est O(n) parce que 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 de O(n 2 ).

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

Je sais (peut-être pas 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.

Answer 1

Je n'arrive pas à comprendre comment identifier une fonction avec un temps logarithmique.

Les attributs les plus courants de la fonction de temps de fonctionnement logarithmique sont les suivants :

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

o

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

C'est pourquoi, par exemple, la recherche de personnes dans un annuaire téléphonique est O(log n). Vous n'avez pas besoin de vérifier chaque Au lieu de cela, vous pouvez simplement diviser et conquérir en cherchant en fonction de la position alphabétique de leur nom, et dans chaque section, vous n'avez besoin d'explorer qu'un sous-ensemble de chaque section avant de trouver le numéro de téléphone de quelqu'un.

Bien sûr, un annuaire plus grand vous prendra toujours 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 de services. leur temps de fonctionnement. Nous supposerons que notre annuaire téléphonique a entreprises (les "Pages Jaunes") qui ont des noms et des noms uniques personnes (les "pages blanches") qui peuvent ne pas avoir de nom unique. Un numéro de téléphone est attribué à une seule personne ou entreprise au maximum. 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) : En fonction de la page sur laquelle figure le nom d'une entreprise et du nom de l'entreprise, trouvez 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, trouvez le numéro de téléphone.

• O(log n) : Pour trouver le numéro de téléphone d'une personne, choisissez un point au hasard à peu près au milieu de la partie du livre que vous n'avez pas encore fouillée, puis vérifiez si le nom de la personne se trouve à ce point. Répétez ensuite le processus à peu près au milieu 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) : Trouvez toutes les personnes dont le numéro de téléphone contient le chiffre "5".

• O(n) : Si l'on vous donne un numéro de téléphone, trouvez la personne ou l'entreprise qui a ce numéro.

• O(n log n) : Il y a eu une confusion chez l'imprimeur, et toutes les pages de notre annuaire téléphonique ont été insérées dans un ordre aléatoire. Corrigez l'ordre en regardant le premier nom sur chaque page et en plaçant cette page à l'endroit approprié dans un nouvel annuaire vide.

Pour les exemples ci-dessous, nous nous trouvons maintenant chez l'imprimeur. Des annuaires téléphoniques attendent d'être envoyés à chaque personne ou entreprise, et un autocollant sur chaque annuaire indique à qui il doit être envoyé. Chaque personne ou entreprise reçoit un annuaire.

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

• O(n 2 ) : 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 du white-out et effacez chaque zéro.

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

• O(n n ) : Tu répares le robot pour qu'il charge les choses correctement. Le lendemain, 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 annuaire original, l'imprimante de l'usine fait un tirage en double de tous les annuaires ! Heureusement, les systèmes de détection de bugs 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 à charger, mais il doit quand même charger tous les livres originaux et en double qui ont été imprimés.

Answer 2

O(log N) signifie essentiellement que le temps augmente de façon linéaire tandis que la n augmente de façon exponentielle. Donc, s'il faut 1 seconde pour calculer 10 éléments, il faudra 2 secondes pour calculer 100 éléments, 3 secondes pour calculer 1000 éléments, et ainsi de suite.

Il est O(log n) quand on fait des algorithmes de type diviser pour régner, 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 que cela prend O(N) Il est temps de trouver un élément pivot. Par conséquent, il N O(log N)

Answer 3

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

Qu'est-ce que cela signifie de 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 du niveau inférieur de l'arbre de la figure 1 représentent les éléments d'une collection triée. La recherche binaire est un algorithme de division et de conquête, et le dessin montre que nous aurons besoin (au maximum) de 4 comparaisons pour trouver l'enregistrement que nous recherchons dans cet ensemble de données de 16 éléments.

Supposons que nous ayons à la place un ensemble de données avec 32 éléments. Continuez le dessin ci-dessus pour constater que nous aurons maintenant besoin de 5 comparaisons pour trouver ce que nous cherchons, car l'arbre n'a gagné qu'un niveau de profondeur lorsque nous avons multiplié la quantité de données. Par conséquent, la complexité de l'algorithme peut être décrite comme un ordre logarithmique.

Traceur log(n) sur une feuille de papier ordinaire, donnera un graphique où l'élévation de la courbe décélérera comme n augmentations :

Answer 4

L'explication ci-dessous s'appuie sur le cas d'une entreprise entièrement équilibré arbre binaire pour vous aider à comprendre comment on obtient une complexité en temps logarithmique.

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

Et c'est ainsi que l'on obtient O(log n) qui est la quantité de travail à effectuer sur l'arbre ci-dessus pour atteindre une solution.

Un algorithme courant 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é constante de travail supplémentaire.

Answer 5

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, il prend le journal ₂ (n) temps. Le site Notation du grand O En gros, cela signifie que la relation ne doit être vraie que pour un grand n, et que les facteurs constants et les termes plus petits peuvent être ignorés.