Question Qu'est-ce que O (log n) signifie exactement?


Je suis en train d'en apprendre plus sur les durées de fonctionnement de Big O Notation et les durées d'amortissement. Je comprends la notion de Sur) temps linéaire, 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 Sur2) algorithmes similaires, tels que les générateurs de permutation, avec Sur!) fois, qui poussent par des factoriels.

Par exemple, la fonction suivante est Sur) parce que l'algorithme se développe en proportion de 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, l'heure serait O (n2).

Mais qu'est-ce que c'est exactement O (log n)? Par exemple, que veut dire 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ù:dix 100 = 2, mais je ne peux pas comprendre comment identifier une fonction avec un temps logarithmique.


1732
2018-02-21 20:05


origine


Réponses:


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

Les attributs les plus communs 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 téléphonique pour trouver le bon; Au lieu de cela, vous pouvez simplement diviser pour régner en regardant en fonction de l'endroit où leur nom est alphabétique, 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 téléphonique plus gros vous prendra encore plus de temps, mais il ne progressera pas aussi rapidement que l'augmentation proportionnelle de la taille supplémentaire.


Nous pouvons développer l'exemple de l'annuaire téléphonique pour comparer d'autres types d'opérations et leur temps de course. Nous supposerons que notre annuaire téléphonique a entreprises (les "Pages Jaunes") qui ont des noms uniques et gens (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 retourner à une page spécifique.

Voici les temps de fonctionnement de certaines opérations que nous pourrions effectuer sur l'annuaire, du meilleur au pire:

  • O (1) (meilleur cas): Compte tenu de la page sur laquelle le nom d'une entreprise est et le nom de l'entreprise, trouver le numéro de téléphone.

  • O (1) (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): Au vu du nom d'une personne, trouvez le numéro de téléphone en choisissant un point aléatoire à mi-chemin de la partie du livre que vous n'avez pas encore recherchée, puis en vérifiant si le nom de la personne est à ce moment-là. Puis répétez le processus à mi-chemin à travers la partie du livre où le nom de la personne se trouve. (Ceci est une recherche binaire pour le nom d'une personne.)

  • Sur): Trouver toutes les personnes dont les numéros de téléphone contiennent le chiffre "5".

  • Sur): Avec un numéro de téléphone, trouvez la personne ou l'entreprise avec ce numéro.

  • O (n log n): Il y avait une confusion dans le bureau de l'imprimeur, et notre annuaire téléphonique avait toutes ses pages insérées dans un ordre aléatoire. Fixez la commande afin qu'elle soit correcte en regardant le prénom sur chaque page et en plaçant cette page à l'endroit approprié dans un nouveau répertoire téléphonique vide.

Pour les exemples ci-dessous, nous sommes maintenant au bureau de l'imprimeur. 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 devrait être posté. Chaque personne ou entreprise obtient 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 de chaque entreprise dans leur copie désignée, puis encercler leur nom dans le livre et rédiger une courte note de remerciement pour leur patronage.

  • Sur2): Une erreur s'est produite au bureau et chaque entrée de chaque annuaire téléphonique comporte un «0» supplémentaire à la fin du numéro de téléphone. Prenez un peu de blanc et enlevez chaque zéro.

  • O (n · n!): Nous sommes prêts à charger les annuaires sur le quai d'expédition. Malheureusement, le robot qui était censé charger les livres a été détraqué: il met les livres sur 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. (Ceci est le redouté bogo sort.)

  • Surn): Vous réparez le robot pour qu'il charge les choses correctement. Le lendemain, un de vos collègues vous blague et câble le robot de quai de chargement vers les 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 à charger, mais il doit encore charger chaque livre original et en double qui a été imprimé.


2177
2018-02-21 20:14



Beaucoup de bonnes réponses ont déjà été postées sur 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 ci-dessus (d'où binaire):

Binary tree

La recherche binaire est un exemple avec la complexité O(log n). Disons que les nœuds dans le niveau inférieur de l'arbre 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 maximum) de 4 comparaisons pour trouver l'enregistrement que nous recherchons dans cet ensemble 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 trouver que nous aurons maintenant besoin de 5 comparaisons pour trouver ce que nous recherchons, car l'arbre a seulement grandi d'un niveau plus profond quand nous avons multiplié la quantité de données. Par conséquent, la complexité de l'algorithme peut être décrite comme un ordre logarithmique.

Traçage log(n) sur un simple morceau de papier, se traduira par un graphique où la hausse de la courbe décélère comme n augmente:

O(log n)


509
2018-02-21 22:22



O(log N) signifie fondamentalement le temps monte linéairement tandis que le n monte exponentiellement. Donc, si cela prend 1 deuxième à calculer 10 éléments, il faudra 2 secondes pour calculer 100 éléments, 3 secondes pour calculer 1000 éléments, et ainsi de suite.

C'est O(log n) quand on divise et conquiert le type 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 O(N) temps de trouver un élément pivot. D'où il N O(log N) 


463
2018-02-21 20:18



L'explication ci-dessous utilise le cas d'un équilibré arbre binaire pour vous aider à comprendre comment nous obtenons la complexité du temps 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:

height of a binary tree

Et c'est ainsi que vous obtenez O (log n) qui est la quantité de travail qui doit être fait sur l'arbre ci-dessus pour parvenir à une solution.

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


196
2017-10-26 19:33



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 journal2(n) l'heure. le Big O notation, en gros, signifie que la relation ne doit être vraie que pour n grand, et que les facteurs constants et les termes plus petits peuvent être ignorés.


120
2018-02-21 20:11



Aperçu

D'autres ont donné de bons exemples de diagrammes, tels que les diagrammes en arbre. Je n'ai vu aucun exemple de code simple. Donc, en plus de mon explication, je vais fournir 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 de Logarithme, que vous pouvez obtenir de https://en.wikipedia.org/wiki/Logarithm . Utilisation des sciences naturelles e et le journal naturel. Les disciples de l'ingénierie utiliseront log_10 (log base 10) et les informaticiens utiliseront beaucoup log_2 (log base 2), car les ordinateurs sont binaires. Parfois, vous verrez des abréviations de log naturel comme ln(), les ingénieurs quittent normalement le _10 et utilisent juste log() et log_2 est abrégé en lg(). Tous les types de logarithmes se développent de la même manière, c'est pourquoi ils partagent la même catégorie de log(n).

Lorsque vous regardez les exemples de code ci-dessous, je vous recommande de regarder O (1), puis O (n), puis O (n ^ 2). Après que vous êtes bon avec ceux, alors regardez les autres. J'ai inclus des exemples propres ainsi que des variations pour montrer comment des changements subtils peuvent encore aboutir à la même catégorisation.

Vous pouvez penser à O (1), O (n), O (logn), etc. en tant que classes ou catégories de croissance. Certaines catégories prendront plus de temps à faire que d'autres. Ces catégories aident à nous donner un moyen de commander les performances de l'algorithme. Certains ont grandi plus vite que l'entrée n grandit. Le tableau suivant démontre ladite croissance numériquement. Dans le tableau ci-dessous, considérez log (n) comme le plafond de log_2.

enter image description here

Exemples de code simple de diverses catégories Big O:

O (1) - Exemples de temps constant:

  • Algorithme 1:

L'algorithme 1 imprime bonjour une fois et il ne dépend pas de n, donc il fonctionnera toujours à temps constant, il est donc O(1).

print "hello";
  • Algorithme 2:

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

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

O (log (n)) - Exemples logarithmiques:

  • Algorithme 3 - Cela agit comme "log_2"

L'algorithme 3 montre un algorithme qui s'exécute dans log_2 (n). Notez que l'opération post de la boucle for multiplie la valeur actuelle de i par 2, donc i va 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 montre log_3. Remarquer i va 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, cela signifie que vous regardez un algorithme logarithmique.

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

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

  • Algorithme 6

Cet algorithme est simple, qui imprime bonjour n fois.

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

Cet algorithme montre une variation, où il va imprimer 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

Pensez à cela comme une combinaison de O(log(n)) et O(n). L'imbrication des boucles for nous aide à obtenir le O(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 similaire à l'algorithme 8, mais chacune des boucles a permis des variations, ce qui entraîne toujours le résultat final 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) est obtenu facilement par nidification 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 variations.

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 encore 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";

Résumé

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 pas vraiment l'analyse. Espérons que cela vous donne assez de perspicacité.


107
2018-04-26 22:50



Temps de fonctionnement logarithmique (O(log n)) signifie essentiellement que le temps de fonctionnement augmente en proportion de la logarithme de la taille d'entrée - à titre d'exemple, si 10 éléments prend au plus un certain temps x, et 100 articles prend au plus, disons, 2x, et 10 000 articles prend au plus 4x, alors ça ressemble à un O(log n) la complexité du temps.


84
2018-02-21 20:10



Le logarithme

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

Imaginez que nous ayons une corde et que nous l'ayons attachée à un cheval. Si la corde est directement attachée au cheval, la force dont le cheval aurait besoin pour s'éloigner (disons d'un homme) est directement 1.

Imaginez maintenant que la corde est enroulée autour d'un poteau. Le cheval à s'enfuir devra maintenant tirer beaucoup plus fort. La quantité de temps dépendra de la rugosité de la corde et de la taille du poteau, mais supposons qu'elle multiplie sa force par 10 (quand 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 la tâche difficile pour le cheval, il peut boucler la corde autour d'un poteau, augmentant sa force de 10 fois. Une troisième boucle augmente encore la force de 10 fois.

enter image description here

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

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

Alors, que signifie réellement 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 supporter 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 log est insignifiante quand on parle de notation de type «o».

Maintenant, imaginons que vous essayez de deviner un nombre entre 1-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'éléments que vous pouvez deviner à partir de chaque estimation 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 entre 1-100, il nous faudra au plus 7 tentatives. Si nous avions 128 numéros, nous pourrions aussi deviner le nombre dans 7 tentatives mais 129 chiffres nous prendront au plus 8 tentatives (en relation avec les logarithmes, ici nous aurions besoin de 7 estimations pour une gamme de valeurs de 128, 10 suppositions pour une gamme de valeurs de 1024. 7 est le logarithme de 128, 10 est le logarithme de 1024 (base 2)).

Remarquez que j'ai écrit "tout au plus". La notation Big o se réfère toujours au pire des cas. Si vous êtes chanceux, vous pouvez deviner le nombre en une tentative et le meilleur des cas est O (1), mais c'est une autre histoire.

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

Qu'en est-il de O (n log n)?

Vous finirez par rencontrer un temps linerarithmique O (n log (n) algorithme. La règle empirique ci-dessus s'applique à nouveau, mais cette fois, la fonction logarithmique doit être exécutée n fois, par ex. réduire la taille d'une liste n fois, qui se produit dans des algorithmes comme un mergesort.

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

Disclaimer: L'exemple corde-logarithme a été saisi de l'excellent Le livre de Mathematician's Delight par W.Sawyer. 


55
2017-10-08 14:27



Vous pouvez penser intuitivement à O (log N) en disant que le temps est proportionnel au nombre de chiffres en 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, pas à l'amplitude de l'entrée; donc, O (log N) plutôt que O (N).

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

Etc.


54
2018-02-21 20:13



La meilleure façon de visualiser mentalement un algorithme s'exécutant dans 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 est seulement augmenté d'une quantité additive.

En appliquant ceci à votre question d'arbre binaire, vous avez une bonne application: si vous doublez le nombre de nœuds dans un arbre binaire, la hauteur augmente seulement de 1 (une quantité additive). Si vous le doublez encore, il n'a 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 faites seulement un peu plus de travail. C'est pourquoi les algorithmes O (log n) sont géniaux.


48
2018-02-22 19:51