Qu'est-ce qui causerait la complexité O(log n) d'un algorithme?

Les Termes

O(log n) peuvent apparaître à différents endroits, mais il y a généralement deux routes principales qui arriveront à cette période.

rétrécissement par Racine Carrée

comme mentionné dans la réponse à la question liée, une façon courante pour un algorithme d'avoir la complexité du temps O(log n) est que cet algorithme de travailler en réduisant à plusieurs reprises la taille de l'entrée vers le bas d'un facteur constant sur chaque itération. Si c'est le cas, le l'algorithme doit se terminer après les itérations O(log n), parce qu'après avoir fait des divisions O(log n) par une constante, l'algorithme doit réduire la taille du problème à 0 ou 1. C'est pourquoi, par exemple, la recherche binaire a une complexité O(log n).

il est intéressant de noter qu'il existe une façon similaire de réduire la taille d'un problème qui donne des temps d'exécution de la forme O(log n). Au lieu de diviser l'entrée en deux à chaque couche, que se passe-t-il si nous prenons la racine carrée de la taille à chaque couche?

par exemple, prenons le numéro 65536. Combien de fois faut-il diviser ça par 2 jusqu'à ce qu'on tombe à 1? Si nous faisons cela, nous obtenons

• 65,536 / 2 = 32,768
• 32,768 / 2 = 16,384
• 16,384 / 2 = 8,192
• 8,192 / 2 = 4,096
• 4,096 / 2 = 2,048
• de 2048 / 2 = 1,024
• 1,024 / 2 = 512
• 512 / 2 = 256
• 256 / 2 = 128
• 128 / 2 = 64
• 64 / 2 = 32
• 32 / 2 = 16
• 16 / 2 = 8
• 8 / 2 = 4
• 4 / 2 = 2
• 2 / 2 = 1

ce processus prend 16 étapes, et c'est aussi le cas que 65,536 = 2 ¹⁶ .

mais, si nous prenons la racine carrée à chaque niveau, nous obtenons

• √65,536 = 256
• √256 = 16
• √16 = 4
• √4 =2

notez qu'il ne prend que quatre étapes pour descendre jusqu'à 2. Pourquoi est-ce? Bien, réécrivons cette séquence en termes de pouvoirs de deux:

• √65,536 = √2 ¹⁶ = (2 ¹⁶ ) ^1/2 = 2 ⁸ = 256
• √256 = √2 ⁸ = (2 ⁸ ) ^1/2 = 2 ⁴ = 16
• √16 = √2 ⁴ = (2 ⁴ ) ^1/2 = 2 ² = 4
• √4 = √2 ² = (2 ² ) ^1/2 = 2 ¹ = 2

Notez que nous avons suivi la séquence 2 ¹⁶ → 2 ⁸ → 2 ⁴ → 2 ² → 2 ¹ . À chaque itération, nous avons coupé l'exposant de la puissance de deux en deux. C'est intéressant, parce que cela se connecte à ce que nous savons déjà - vous ne pouvez diviser le nombre k que par deux fois O(log k) avant qu'il tombe à zéro.

donc prenez n'importe quel nombre n et écrivez-le comme n = 2 ^k . Chaque fois que vous prenez la racine carrée de n, vous divisez l'exposant dans cette équation. Par conséquent, il ne peut y avoir que des racines carrées O(log k) appliquées avant que k tombe à 1 ou plus bas (dans ce cas, n tombe à 2 ou plus bas). Depuis n = 2 ^k , cela signifie que k = log ₂ n, et donc le nombre de racines carrées prises est O (log k) = O(log n). Par conséquent, s'il existe un algorithme qui fonctionne en réduisant de façon répétée le problème à un sous-problème de taille qui est la racine carrée de la taille du problème original, cet algorithme se terminera après les étapes O(log n).

un exemple concret de ceci est le van Emde Boas tree (VEB-tree) données structure. Un VEB-tree est une structure de données spécialisée pour stocker des entiers dans la gamme 0 ... N-1. Il fonctionne comme suit: le noeud racine de l'arbre a √n pointeurs dans lui, la division de la gamme 0 ... N-1 en seaux √N ayant chacun une portée d'environ √n entiers. Ces seaux sont ensuite subdivisés à l'interne en seaux √(√ n), chacun contenant à peu près des éléments √(√ n). Pour traverser l'arbre, vous commencez à la racine, déterminez à quel seau vous appartenez, puis continuez récursivement dans la appropriée de la sous-arborescence. En raison de la façon dont le VEB-tree est structuré, vous pouvez déterminer dans O(1) le temps dans lequel subtree descendre, et ainsi après o(log n) pas, vous atteindrez le fond de l'arbre. En conséquence, les recherches dans un arbre vEB ne prennent que du temps O(log n).

un autre exemple est L'algorithme Hopcroft-Fortune la paire de points la plus proche . Cet algorithme tente de trouver les deux points les plus proches dans une collection de points 2D. Il fonctionne par créer une grille de seaux et distribuer les points dans ces seaux. Si à un moment donné dans l'algorithme d'un seau est trouvé qui a plus de √N points, l'algorithme récursivement processus seau. La profondeur maximale de la récursion est donc O (log n), et une analyse de l'arbre de récursion permet de montrer que chaque couche de l'arbre fonctionne O(N). Par conséquent, la durée d'exécution totale de l'algorithme est O(N log n).

o(log n) algorithmes sur Petites Entrées

il y a d'autres algorithmes qui atteignent les temps D'exécution O(log n) en utilisant des algorithmes comme la recherche binaire sur des objets de taille O(log n). Par exemple, la structure de données X-fast trie effectue une recherche binaire sur les couches de l'arbre de la hauteur O(log U), de sorte que l'exécution de certaines de ses opérations est O(log U). Le y-fast trie associé obtient une partie de ses durées de fonctionnement O(log U) en maintenant un équilibre Techniciennes se chargent de O(log U) les nœuds de chaque, permet de réaliser des recherches dans les arbres pour s'exécuter en temps O(log log U). Le arbre tango et le arbre multisplay structures de données se terminent avec un terme O(log n) dans leurs analyses parce qu'ils maintiennent des arbres qui contiennent des éléments O(log n) chacun.

Autres Exemples

D'autres algorithmes atteignent la durée D'exécution O (log n) d'autres façons. recherche par Interpolation s'attend à ce que l'exécution O(log n) trouve un nombre dans un tableau trié, mais l'analyse est assez impliquée. Finalement, l'analyse fonctionne en montrant que le nombre d'itérations est égal au nombre k tel que n ^{2 -k} ≤ 2, pour lequel log n est la bonne solution. Certains algorithmes , comme L'algorithme Cheriton-Tarjan MST , arrivent à un runtime impliquant O (log n) en résolvant un complexe problème d'optimisation limité.

Espérons que cette aide!