Déterminer si un algorithme est O (log n)

25

Je rafraîchis ma théorie CS, et je veux savoir comment identifier cet algorithme de complexité O (log n). Plus précisément, existe-t-il un moyen facile de l'identifier?

Je sais qu'avec O (n), vous avez généralement une seule boucle; O (n ^ 2) est une double boucle; O (n ^ 3) est une triple boucle, etc. Qu'en est-il de O (log n)?

Atif
la source
Ah, c'est le seul endroit où je n'ai pas regardé :)
Atif

Réponses:

32

Je sais qu'avec O (n), vous avez généralement une seule boucle; O (n ^ 2) est une double boucle; O (n ^ 3) est une triple boucle, etc. Qu'en est-il de O (log n)?

Vous y allez vraiment mal ici. Vous essayez de mémoriser quelle expression big-O va avec une structure algorithmique donnée, mais vous devriez vraiment compter le nombre d'opérations que l'algorithme nécessite et le comparer à la taille de l'entrée. Un algorithme qui boucle sur toute son entrée a des performances O (n) car il exécute la boucle n fois, pas parce qu'il a une seule boucle. Voici une boucle unique avec des performances O (log n):

for (i = 0; i < log2(input.count); i++) {
    doSomething(...);
}

Ainsi, tout algorithme où le nombre d'opérations requises est de l'ordre du logarithme de la taille de l'entrée est O (log n). La chose importante que l'analyse big-O vous dit est de savoir comment le temps d'exécution d'un algorithme change par rapport à la taille de l'entrée: si vous doublez la taille de l'entrée, l'algorithme fait-il encore 1 étape (O (log n)) , deux fois plus de pas (O (n)), quatre fois plus de pas (O (n ^ 2)), etc.

Est-il utile de savoir par expérience que les algorithmes qui partitionnent à plusieurs reprises leurs entrées ont généralement «log n» comme composante de leurs performances? Sûr. Mais ne cherchez pas le partitionnement et passez à la conclusion que les performances de l'algorithme sont O (log n) - cela pourrait être quelque chose comme O (n log n), ce qui est assez différent.

Caleb
la source
3
Notez qu'une manière plus familière de dire "dans l'ordre du logarithme de la taille" est de dire "dans l'ordre du nombre de chiffres dans la taille".
@Caleb la base réelle du logarithme n'a pas d'importance lors de la mise à l'échelle.
@Caleb parler des absolus n'a pas de sens avec big-O. Une formulation que vous aimeriez mieux: lorsque le nombre de chiffres double, le nombre de pas double.
@Caleb parler des absolus n'a pas de sens avec big-O. Une formulation que vous aimeriez mieux: lorsque le nombre de chiffres double, le nombre de pas double.
@ ThorbjørnRavnAndersen Oui, c'est ce que signifie "le logarithme de la taille". Je ne sais pas quel est votre problème avec la phrase, sauf que vous auriez choisi de la dire différemment. Fondamentalement, je pense que nous sommes d'accord.
Caleb
25

L'idée est qu'un algorithme est O(log n)si au lieu de faire défiler une structure 1 par 1, vous divisez la structure en deux encore et encore et effectuez un nombre constant d'opérations pour chaque division. Les algorithmes de recherche dans lesquels l'espace de réponse ne cesse de se diviser sont O(log n). Un exemple de ceci est la recherche binaire , où vous continuez de diviser un tableau ordonné en deux à plusieurs reprises jusqu'à ce que vous trouviez le nombre.

Remarque: Vous n'avez pas nécessairement besoin de vous diviser en deux moitiés égales.

Casey Patton
la source
1
Que se passe-t-il si je divise l'entrée en deux puis répète 2 ^ (n / 2) fois sur le reste avant de la diviser à nouveau? (Bien sûr, je sais quoi alors, je voulais juste montrer un exemple où cette approche simpliste échoue).
Tamás Szelei
@afish C'est plutôt rare. C'est spectaculairement rare lors de la recherche.
Donal Fellows
1
@DonalFellows La théorie des algorithmes n'est pas une science empirique. Et la question n'était pas de chercher, c'est juste que la mention des log nréflexes de recherche binaires déclenchés chez les gens.
Tamás Szelei
2
Le partitionnement ne fait pas l'algorithme O (log n), il ajoute (généralement) un facteur de log n à la limite big-O. Les tris récursifs comme heapsort et mergesort sont des exemples parfaits: ils partitionnent l'entrée, mais ils partitionnent récursivement les deux partitions résultantes. Le résultat est une performance O (n log n).
Caleb
@afish: Bon point. Mon objectif avec cette réponse est de rester aussi simple que possible compte tenu de la nature de la question. J'ai changé la ligne "vous divisez la structure en deux ..." en "vous divisez la structure en deux ... et effectuez un nombre constant d'opérations pour chaque division" pour essayer de faire passer ce point simplement.
Casey Patton
2

Les exemples typiques sont ceux qui traitent de la recherche binaire. Par exemple, un algorithme de recherche binaire est généralement O(log n).

Si vous avez une arborescence de recherche binaire , la recherche, l'insertion et la suppression sont toutes O(log n)complexes.

Toute situation où vous partitionnez continuellement l'espace impliquera souvent un log ncomposant. C'est pourquoi de nombreux algorithmes de tri sont O(nlog n)complexes, car ils partitionnent souvent un ensemble et trient au fur et à mesure.

Kris Harper
la source
1

Si vous le voulez aussi simple que "boucle simple -> O (n), boucle double -> O (n ^ 2)", alors la réponse est probablement "Tree -> O (log n)". Traverser plus précisément un arbre de la racine à une feuille (pas toutes!) Ou inversement. Cependant, ce sont toutes des simplifications excessives.

écharpe
la source
Alors, quel est le problème avec ma réponse? Je suis ouvert aux critiques constructives.
scarfridge
0

Vous voulez savoir s'il existe un moyen simple d'identifier si un algorithme est O (log N).

Eh bien: il suffit de courir et de chronométrer. Exécutez-le pour les entrées 1.000, 10.000, 100.000 et un million.

Si vous voyez comme un temps de fonctionnement de 3,4,5,6 secondes (ou plusieurs), vous pouvez dire en toute sécurité que c'est O (log N). Si c'est plutôt: 1,10,100,1000 secondes, alors c'est probablement O (N). Et si c'est comme 3,40,500,6000 secondes, alors c'est O (N log N).

Pieter B
la source
Tout le monde devrait donner à cette réponse un vote positif et un vote négatif, les deux pour des raisons évidentes :-)
gnasher729