Exemples notables de l'idée de racine carrée dans l'analyse de complexité

Il existe un certain nombre d'algorithmes et de structures de données qui exploitent l'idée que obtient sa valeur minimale à k = \ sqrt n . Les exemples courants incluent k = $\max \left\{k, n/k\right\}$$k=\sqrt n$

• algorithme pas à pas géant pour calculer le logarithme discret en $O(\sqrt n)$ ,
• comptage orthogonal 2D statique en temps $O(\sqrt n)$ et mémoire $O(n)$ ,
• file d'attente prioritaire avec EXTRACT-MIN en $O(\sqrt[k] n)$ et DECREASE-KEY en $O(1)$ ,
• colorier un graphe à 3 couleurs avec $O(\sqrt n)$ couleurs en temps polynomial,

Juste pour en nommer quelques-uns.

Bien que ces algorithmes soient souvent sous-optimaux, ils sont faciles à comprendre par les élèves et bons à montrer rapidement que les limites naïves ne sont pas optimales. De plus, les structures de données à racine carrée sont parfois plus pratiques que leurs homologues à base d'arbre binaire en raison de la convivialité du cache (sans considérer les techniques sans cache). C'est pourquoi j'accorde une attention particulière à ce sujet tout en enseignant.

Je suis intéressé par des exemples plus distinctifs de ce type. Je recherche donc des algorithmes (de préférence élégants), des structures de données, des protocoles de communication, etc. dont l'analyse repose sur l'idée de racine carrée. Leurs asymptotiques n'ont pas besoin d'être optimales.

L'article de Chazelle, Liu et Magen's Algorithmes géométriques sublinéaires (STOC 2003, SICOMP 2006) a plusieurs applications intelligentes de l'astuce d'échantillonnage aléatoire suivante. Des variantes de la même astuce ont déjà été utilisées par Gärtner et Welzl [ DCG 2001 ], qui citent la première édition de CLR (1990).

Supposons que l'on nous donne une liste triée de nombres liés et circulaires, stockés dans un bloc de mémoire contigu. Autrement dit, nous avons deux tableaux et , oùN e x t [ 1 .. n $Key[1..n]$$Next[1..n]$

• $Key[1..n]$ stocke un ensemble de nombres dans un ordre arbitraire ;$n$
• Si la est le plus grand nombre de l'ensemble, alors la est le plus petit nombre de l'ensemble; sinon, est le plus petit nombre de l'ensemble supérieur à .$Key[i]$$Key[Next[i]]$$Key[Next[i]]$$Key[i]$

Ensuite, nous pouvons trouver le successeur d'un nombre donné dans temps attendu comme suit:$x$$O(\sqrt{n})$

• Choisissez un échantillon aléatoire d'éléments de la du tableau . Soit le plus grand échantillon inférieur à x (ou le plus grand échantillon, si tous les échantillons sont supérieurs à x ).$\sqrt{n}$$Key$$Key[j]$$x$$x$

• Suivez les pointeurs de K e y [ j ] jusqu'à ce que nous voyions un nombre supérieur ou égal à x (après enroulement si tous les échantillons étaient plus grands que x ).$Next$$Key[j]$$x$$x$

Une application relativement simple du lemme de Yao implique que le limite de temps attendue est optimale. Tout algorithme déterministe pour ce problème nécessite un tempsΩ(n)dans le pire des cas.$O(\sqrt{n})$$\Omega(n)$

Il y triangles dans toute m -arête graphique et qu'ils peuvent être trouvés dans O ( m 3 / deux ) fois. Il existe de nombreuses façons de le faire, mais je pense que l'une des premières est Itai et Rodeh (STOC 1977) qui fournissent un algorithme qui passe par une séquence d'itérations en temps linéaire, chacune supprimant une forêt s'étendant du graphique. Dans les premières itérations lorsque la forêt restante a au moins n - k composants, l'algorithme supprime au moins k bords par étape, et dans les dernières itérations quand il a au plus$O(m^{3/2})$$m$$O(m^{3/2})$$n-k$$k$ composants, le degré maximum est k et diminue d'au moins un à chaque pas. Ainsi, le nombre total d'itérations est au plus m / k + k et le choix du bon compromis donne la limite globale de O ( $n-k$$k$$m/k+k$suritérations etO(m 3 / 2 )surtemps.$O(\sqrt m)$$O(m^{3/2})$