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

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)?

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.

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.

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.

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.

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).