Amarengo

Articles and news

Qu’est-ce qui ferait en sorte qu’un algorithme ait une complexité O (log log n) ?

Les termes O (log log n) peuvent apparaître à différents endroits, mais il existe généralement deux routes principales qui arriveront à ce runtime.

Réduction d’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) consiste à réduire à plusieurs reprises la taille de l’entrée d’un facteur constant à chaque itération. Si c’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 un moyen similaire de réduire la taille d’un problème qui génère 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 arrivions à 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 = 216.

Mais, si l’on prend la racine carrée à chaque niveau, on obtient

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

Notez qu’il ne faut que quatre étapes pour descendre jusqu’à 2. Pourquoi est-ce?

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

Maintenant, faisons quelques calculs pour rendre cela rigoureux. Les Le’ts réécrivent la séquence ci-dessus en termes de puissances de deux:

  • √65,536 = √216 = (216)1/2 = 28 = 256
  • √256 = √28 = (28)1/2 = 24 = 16
  • √16 = √24 = (24)1/2 = 22 = 4
  • √4 = √22 = (22)1/2 = 21 = 2

Notez que nous avons suivi la séquence 216 → 28 → 24 → 22 → 21. À chaque itération, nous coupons l’exposant de la puissance de deux en deux. C’est intéressant, car cela renvoie à ce que nous savons déjà – vous ne pouvez diviser le nombre k en deux fois O (log k) avant qu’il ne tombe à zéro.

Prenez donc n’importe quel nombre n et écrivez-le comme n = 2k. Chaque fois que vous prenez la racine carrée de n, vous divisez de moitié 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 = 2k, cela signifie que k = log2 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 du problème d’origine, cet algorithme se terminera après les étapes O (log log n).

Un exemple concret de ceci est la structure de données de van Emde Boas tree (vEB-tree). Un arbre vEB est une structure de données spécialisée pour stocker des entiers dans la plage 0… N-1. Cela 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 godets sont ensuite subdivisés chacun intérieurement en godets √ (√ N), chacun contenant approximativement √ (√ N) éléments. Pour parcourir l’arborescence, vous commencez à la racine, déterminez à quel compartiment vous appartenez, puis continuez récursivement dans le sous-arbre approprié. En raison de la façon dont l’arbre vEB est structuré, vous pouvez déterminer en O(1) temps dans quel sous-arbre descendre, et donc après O (log log N) étapes, vous atteindrez le bas de l’arbre. En conséquence, les recherches dans un arbre vEB ne prennent que du temps O (log log N).

Un autre exemple est l’algorithme de la paire de points la plus proche de 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 contient plus de √N points, l’algorithme traite récursivement ce compartiment. 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, l’exécution totale de l’algorithme est O (n log log n).

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

Il existe d’autres algorithmes qui permettent d’obtenir des temps d’exécution O (log log n) en utilisant des algorithmes tels que 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 hauteur O (log U), de sorte que l’exécution de certaines de ses opérations est O (log log U). Le trie y-fast associé obtient une partie de ses temps d’exécution O (log log U) en maintenant des BSTs é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’arborescence tango et les structures de données d’arborescence multisplay associées se retrouvent avec un terme O (log log n) dans leurs analyses car elles maintiennent des arbres contenant chacun des éléments O (log n).

Autres exemples

D’autres algorithmes réalisent l’exécution O (log log n) d’autres manières. La recherche par interpolation s’attend à ce que l’exécution O (log log n) trouve un nombre dans un tableau trié, mais l’analyse est assez impliquée. En fin de compte, l’analyse fonctionne en montrant que le nombre d’itérations est égal au nombre k tel que n2-k ≤ 2, pour lequel log log n est la bonne solution. Certains algorithmes, comme l’algorithme MST de Cheriton-Tarjan, arrivent à un runtime impliquant O (log log n) en résolvant un problème d’optimisation contraint complexe.

J’espère que cela vous aidera!

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.