Pourquoi un algorithme aurait-il une complexité O (log log n)?

Cette question précédente aborde certains des facteurs qui peuvent amener un algorithme à avoir une complexité O (log n).

Qu'est-ce qui rendrait un algorithme une complexité temporelle O (log log n)?

Les termes O (log log n) peuvent apparaître à différents endroits, mais il y a généralement deux routes principales qui arriveront à ce moment d'exécution.

Rétrécissement par une racine carrée

Comme mentionné dans la réponse à la question liée, un moyen courant pour un algorithme d'avoir une complexité temporelle O (log n) est que cet algorithme fonctionne en réduisant à plusieurs reprises la taille de l'entrée d'un facteur constant à chaque itération. Si tel est le cas, l'algorithme doit se terminer après O (log n) itérations, car après avoir fait O (log n) divisions 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).

Fait intéressant, il existe une manière similaire de réduire la taille d'un problème qui produit des temps d'exécution de la forme O (log 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 nombre 65 536. Combien de fois devons-nous diviser cela par 2 jusqu'à ce que nous descendions à 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
• 2.048 / 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

Remarquez qu'il suffit de quatre étapes pour arriver à 2. Pourquoi est-ce?

Tout d'abord, une explication intuitive. Combien de chiffres y a-t-il dans les nombres n et √n? Il y a environ log n chiffres dans le nombre n et environ log (√n) = log (n ^1/2 ) = (1/2) log n chiffres dans √n. Cela signifie que chaque fois que vous prenez une racine carrée, vous divisez environ par deux le nombre de chiffres dans le nombre. Parce que vous ne pouvez réduire de moitié une quantité k O (log k) fois avant qu'elle ne tombe à une constante (par exemple, 2), cela signifie que vous ne pouvez prendre des racines carrées que O (log log n) fois avant de réduire le nombre. à une certaine constante (disons, 2).

Maintenant, faisons quelques calculs pour rendre cela rigoureux. Le'ts réécrit la séquence ci-dessus en termes de puissances 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 divisons par deux l'exposant de la puissance de deux. C'est intéressant, car cela renvoie à ce que nous savons déjà - vous ne pouvez diviser le nombre k que par deux fois O (log k) avant qu'il ne tombe à zéro.

Prenez donc 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 par deux 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 moins (auquel cas n tombe à 2 ou moins). Puisque n = 2 ^k , cela signifie que k = log ₂ n, et donc le nombre de racines carrées prises est O (log k) = O (log log n). Par conséquent, s'il existe un algorithme qui fonctionne en réduisant à plusieurs reprises le problème à un sous-problème de taille qui est la racine carrée de la taille d'origine du problème, cet algorithme se terminera après les étapes O (log log n).

Un exemple concret de ceci est l' arbre van Emde Boas(vEB-tree) structure de données. Un arbre vEB est une structure de données spécialisée pour stocker des entiers dans la plage 0 ... N - 1. Il fonctionne comme suit: le nœud racine de l'arbre contient √N pointeurs, divisant la plage 0 ... N - 1 dans √N compartiments contenant chacun une plage d'environ √N entiers. Ces seaux sont ensuite chacun subdivisés en interne en √ (√ N) seaux, chacun contenant à peu près √ (√ N) éléments. Pour parcourir l'arborescence, vous commencez à la racine, déterminez à quel compartiment vous appartenez, puis continuez de manière récursive dans le sous-arbre approprié. En raison de la façon dont l'arbre vEB est structuré, vous pouvez déterminer en temps O (1) dans quel sous-arbre descendre, et ainsi, après O (log log N) étapes, vous atteindrez le bas de l'arbre. En conséquence, les recherches dans une arborescence vEB ne prennent que du temps O (log log N).

Un autre exemple est l' algorithme de la paire de points la plus proche Hopcroft-Fortune . Cet algorithme tente de trouver les deux points les plus proches dans une collection de points 2D. Cela fonctionne en créant une grille de seaux et en distribuant les points dans ces seaux. Si à un moment quelconque de l'algorithme un compartiment contenant plus de √N points est trouvé, l'algorithme traite ce compartiment de manière récursive. La profondeur maximale de la récursivité est donc O (log log n), et en utilisant une analyse de l'arbre de récursivité, on peut montrer que chaque couche de l'arbre fonctionne O (n). Par conséquent, le temps d'exécution total de l'algorithme est O (n log log n).

Algorithmes O (log n) sur les petites entrées

Il existe d'autres algorithmes qui réalisent des temps d'exécution O (log 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 d'arbre de hauteur O (log U), de sorte que le temps d'exécution de certaines de ses opérations est O (log log U). Le trie y-rapide associé obtient une partie de ses temps d'exécution O (log log U) en maintenant des BST équilibrés de nœuds O (log U) chacun, permettant aux recherches dans ces arbres de s'exécuter dans le temps O (log log U). L' arbre de tango et les structures de données d' arbre multisplay associées se retrouvent avec un terme O (log log n) dans leurs analyses car ils conservent des arbres contenant chacun des éléments O (log n).

Autres exemples

D'autres algorithmes atteignent le runtime O (log log n) d'autres manières. La recherche d'interpolation a prévu que l'exécution O (log log n) trouve un nombre dans un tableau trié, mais l'analyse est assez complexe. 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 log n est la bonne solution. Certains algorithmes, comme l' algorithme MST Cheriton-Tarjan , arrivent à un runtime impliquant O (log log n) en résolvant un problème d'optimisation complexe contraint.

J'espère que cela t'aides!

Une façon de voir le facteur de O (log log n) dans la complexité du temps est par division comme ce qui est expliqué dans l'autre réponse, mais il existe une autre façon de voir ce facteur, lorsque nous voulons faire un échange entre le temps et l'espace / temps. et approximation / temps et dureté / ... des algorithmes et nous avons une itération artificielle sur notre algorithme.

Par exemple, SSSP (Single source shortest path) a un algorithme O (n) sur les graphes planaires, mais avant cet algorithme compliqué, il y avait un algorithme beaucoup plus simple (mais toujours assez difficile) avec un temps d'exécution O (n log log n), le La base de l'algorithme est la suivante (juste une description très approximative, et je proposerais de sauter la compréhension de cette partie et de lire l'autre partie de la réponse):

1. divisez le graphe en parties de taille O (log n / (log log n)) avec quelques restrictions.
2. Supposons que chacune des parties mentionnées soit un nœud dans le nouveau graphe G 'puis calculez SSSP pour G' dans le temps O (| G '| * log | G' |) ==> ici car | G '| = O (| G | * log log n / log n) nous pouvons voir le facteur (log log n).
3. Calculez SSSP pour chaque partie: encore une fois parce que nous avons une partie O (| G '|) et que nous pouvons calculer SSSP pour toutes les parties dans le temps | n / logn | * | log n / log logn * log (logn / log log n).
4. mettre à jour les poids, cette partie peut être effectuée en O (n). pour plus de détails, ces notes de cours sont bonnes.

Mais mon point est, ici, nous choisissons la division pour être de taille O (log n / (log log n)). Si nous choisissons d'autres divisions comme O (log n / (log log n) ^ 2) qui peut s'exécuter plus rapidement et apporter un autre résultat. Je veux dire, dans de nombreux cas (comme dans les algorithmes d'approximation ou les algorithmes randomisés, ou des algorithmes comme SSSP comme ci-dessus), quand on itère sur quelque chose (sous-problèmes, solutions possibles, ...), on choisit le nombre d'itération correspondant au métier de cela on a (temps / espace / complexité de l'algorithme / facteur constant de l'algorithme, ...). Ainsi peut-être que nous voyons des choses plus compliquées que "log log n" dans de vrais algorithmes de travail.