Cette question précédente aborde certains des facteurs qui peuvent faire qu'un algorithme ait une complexité O(log n).
Pourquoi un algorithme aurait-il 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 voies principales qui arrivent à ce temps d'exécution.
Comme mentionné dans la réponse à la question liée, une façon courante pour un algorithme d'avoir une complexité temporelle O(log n) est que cet algorithme fonctionne en réduisant de façon répétée la taille de l'entrée par un certain 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 effectué 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).
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 log n). Au lieu de diviser l'entrée en deux à chaque couche, que se passe-t-il si nous prendre la racine carrée de la taille à chaque couche ?
Par exemple, prenons le nombre 65 536. Combien de fois devons-nous le diviser par 2 jusqu'à ce que nous arrivions à 1 ? Si nous faisons cela, nous obtenons
Ce processus prend 16 étapes, et c'est aussi le cas que 65,536 = 2 16 .
Mais, si nous prenons la racine carrée à chaque niveau, nous obtenons
Remarquez qu'il ne faut que quatre étapes pour arriver à 2. Pourquoi ?
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 approximativement par deux le nombre de chiffres du nombre. Comme on ne peut diviser une quantité par deux que k O(log k) fois avant qu'elle ne descende à une constante (disons 2), cela signifie qu'on ne peut prendre des racines carrées que O(log log n) fois avant d'avoir réduit le nombre à une certaine constante (disons 2).
Maintenant, faisons un peu de mathématiques pour rendre cela rigoureux. Réécrivons la séquence ci-dessus en termes de puissances de deux :
Remarquez que nous avons suivi la séquence 2 16 → 2 8 → 2 4 → 2 2 → 2 1 . À chaque itération, nous réduisons de moitié l'exposant de la puissance de deux. C'est intéressant, car cela nous ramène à ce que nous savons déjà : vous ne pouvez diviser le nombre k en deux que O(log k) fois avant qu'il ne 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 par deux l'exposant de cette équation. Par conséquent, il ne peut y avoir que O(log k) racines carrées appliquées avant que k ne tombe à 1 ou moins (auquel cas n tombe à 2 ou moins). Puisque n = 2 k ce qui signifie que k = log 2 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 de manière répétée le problème à un sous-problème de taille égale à la racine carrée de la taille du problème original, cet algorithme se terminera après O(log log n) étapes.
Un exemple concret de cette situation est le arbre van Emde Boas (vEB-tree), une structure de données. Une vEB-tree est une structure de données spécialisée dans le stockage d'entiers dans l'intervalle 0 ... N - 1. N - 1. Elle fonctionne de la manière suivante : le nœud racine de l'arbre possède √N pointeurs en lui, divisant la plage 0 .... N - 1 en √N compartiments, chacun contenant une plage d'environ √N nombres entiers. Ces compartiments sont ensuite subdivisés en √(√ N) compartiments, chacun contenant environ √(√ N) éléments. Pour parcourir l'arbre, on commence à la Racine, on détermine à quel godet on appartient, puis on continue 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. Par conséquent, les recherches dans un vEB-tree ne prennent que O(log log N).
Un autre exemple est le Algorithme de la plus proche paire de points de Hopcroft-Fortune . Cet algorithme tente de trouver les deux points les plus proches dans une collection de points 2D. Il fonctionne en créant une grille de godets et en distribuant les points dans ces godets. Si, à un moment quelconque de l'algorithme, on trouve un godet contenant plus de √N points, l'algorithme traite récursivement ce godet. La profondeur maximale de la récursion est donc de O(log log n), et en utilisant une analyse de l'arbre de récursion, on peut montrer que chaque couche de l'arbre effectue O(n) travail. Par conséquent, le temps d'exécution total de l'algorithme est de O(n log log n).
Il existe d'autres algorithmes qui atteignent des temps d'exécution de O(log log n) en utilisant des algorithmes comme la recherche binaire sur des objets de taille O(log n). Par exemple, l'algorithme x-fast trie effectue une recherche binaire sur les couches d'un 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). La structure de données y-fast trie obtient certains de ses temps d'exécution O(log log U) en maintenant des BST équilibrés de O(log U) nœuds chacun, permettant aux recherches dans ces arbres de s'exécuter en temps O(log log U). Le site arbre à tango et autres arbre multi-écrans Les structures de données se retrouvent avec un terme O(log log n) dans leurs analyses car elles maintiennent des arbres qui contiennent O(log n) éléments chacun.
D'autres algorithmes atteignent un temps d'exécution O(log log n) par d'autres moyens. Recherche par interpolation a un temps d'exécution prévu O(log log n) pour trouver un nombre dans un tableau trié, mais l'analyse est assez complexe. En fin de compte, l'analyse fonctionne en montrant que le nombre d'itérations est égal au nombre k tel que n 2 -k ≤ 2, pour laquelle log log n est la solution correcte. Certains algorithmes, comme le Algorithme MST de Cheriton-Tarjan Nous sommes parvenus à un temps d'exécution de O(log log n) en résolvant un problème complexe d'optimisation sous contrainte.
J'espère que cela vous aidera !
@JonathonReinhart- Il se trouve que c'est quelque chose que je trouve (a) vraiment, vraiment cool, et (b) pas très connu. Je suis toujours heureux de partager des choses comme ça ! :-)
@Mahesha999 Stack Overflow encourage activement les utilisateurs à répondre à leurs propres questions . :-)
Je me demande quelles sont les autres implications de l'option "Répondez à votre propre question" en bas de la page "Posez une question" ou si elle permet simplement d'activer la zone de texte de réponse sur la page de la question.
Une façon de voir un facteur de O(log log n) dans la complexité temporelle est la division comme expliqué dans l'autre réponse, mais il y a une autre façon de voir ce facteur, quand nous voulons faire un échange entre le temps et l'espace/temps et l'approximation/temps et la dureté/... des algorithmes et nous avons une certaine 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 facile (mais toujours assez difficile) avec un temps d'exécution O(n log log n), la base de l'algorithme est la suivante (juste une description très grossière, et je vous propose de sauter cette partie et de lire l'autre partie de la réponse) :
Mais ce que je veux dire, c'est qu'ici nous choisissons que la division soit de taille O(log n/(log log n)). Si nous choisissons d'autres divisions comme O(log n/(log log n)^2), cela peut être plus rapide et donner un autre résultat. Je veux dire, dans de nombreux cas (comme dans les algorithmes d'approximation ou les algorithmes aléatoires, ou les algorithmes comme SSSP comme ci-dessus), lorsque nous itérons sur quelque chose (sous-problèmes, solutions possibles, ...), nous choisissons le nombre d'itération correspondant à l'échange que nous avons (temps/espace/complexité de l'algorithme/facteur constant de l'algorithme, ...). Il se peut donc que nous voyions des choses plus compliquées que "log log n" dans les algorithmes réels.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
