Logarithmique vs complexité temporelle logarithmique double

Dans les applications du monde réel, y a-t-il un avantage concret à utiliser les algorithmes $\mathcal{O}(\log(\log(n))$ au lieu des algorithmes $\mathcal{O}(\log(n))$ ?

C'est le cas lorsque l'on utilise par exemple des arbres van Emde Boas au lieu d'implémentations d'arbres de recherche binaires plus conventionnelles. Mais par exemple, si nous prenons alors dans le meilleur des cas, l'algorithme logarithmique double surpasse celui logarithmique par (approximativement) un facteur de . Et aussi en général, la mise en œuvre est plus délicate et complexe.$n < 10^6$$5$

Étant donné que je préfère personnellement le BST aux arbres VEB, qu'en pensez-vous?

On pourrait facilement démontrer que:

$\qquad \displaystyle \forall n < 10^6.\ \frac{\log n}{\log(\log(n))} < 5.26146$

N'oubliez pas que croît toujours de façon exponentielle (dans log ( n ) ) plus rapidement que log ( log n ) !$\log n$$\log(n)$$\log(\log n)$

En effet, si vous regardez le quotient de et log ( log ( n ) ) , il n'y a pas grand chose à voir:$\log(n)$$\log(\log(n))$

^{[ source ]}

Mais tout de même, vous obtenez un facteur cinq à six pour des tailles allant jusqu'à . Notez que les grandes tailles ne sont pas rares dans la pratique, et une accélération de ce facteur est géniale ! Cela peut faire la différence entre avoir des résultats après le déjeuner ou seulement demain. Soyez conscient qu'une partie de l'accélération peut être rongée par des constantes plus élevées de l'implémentation de l'arborescence; vous devriez tracer (ou analyser) c ⋅ log ( n ) et d ⋅ log ( log ( n ) ) avec c , d les constantes d'exécution réelles pour obtenir une image réelle.$100000$$c\cdot \log(n)$$d\cdot \log(\log(n))$$c,d$

De plus, ce que Dave mentionne est important: si l'opération accélérée est ainsi exécutée, disons, linéairement souvent, les accélérations constantes deviennent des accélérations linéaires, c'est-à-dire que vous pouvez diminuer la constante de tête de tout votre algorithme! Comme je l'ai dit plus haut, c'est génial. Regardez ce qui se passe si vous exécutez l'opération fois:$n$

^{[ source ]}

Maintenant, si cela ne vaut pas la peine, je ne sais pas quoi.

On pourrait imaginer que la différence de complexité importe peu, et que le temps d'exécution réel est plus important. Mais si l'algorithme est au cœur d'un autre algorithme, cette différence peut être importante.

D'un but purement théorique, la différence importe bien sûr, surtout si l'algorithme fait partie d'un autre. Il peut placer l'algorithme le plus grand dans une classe de complexité différente.

J'ai déjà testé l'arbre van Emde-Boas une fois. Je l'ai comparé avec un arbre AA, une table de hachage et un tableau de bits.

Les tests effectuent des sizeinsertions avec des nombres aléatoires dans l'intervalle [0, bound], puis des sizerecherches, puis des sizesuppressions, puis de nouvelles sizerecherches. Les suppressions sont également effectuées sur des nombres aléatoires, vous devez donc d'abord déterminer s'ils sont dans la structure.

Voici les résultats ( size= 2000000, bound= 10000000) en quelques secondes:

AATreeLookup - O(n log n)
Inserting... 3.3652452
Searching... 5.2280724
Deleting...  7.3457427
Searching... 9.1462039
HashLookup - O(n) expected
Inserting... 0.3369505
Searching... 0.6223035
Deleting...  0.9062163
Searching... 1.1718223
VanEmdeBoasTree - O(n log log n)
Inserting... 0.7007531
Searching... 1.1775800
Deleting...  1.7257065
Searching... 2.2147703
ArrayLookup - O(n)
Inserting... 0.0681897
Searching... 0.1720300
Deleting...  0.2387776
Searching... 0.3413800

Comme vous pouvez le voir, les arbres van Emde-Boas sont environ deux fois plus lents que les cartes de hachage, dix fois plus lents que les tableaux de bits et 5 fois plus rapides que les arbres de recherche binaires.

Bien sûr, ce qui précède a besoin d'une clause de non-responsabilité: les tests sont artificiels, vous pouvez éventuellement améliorer le code ou utiliser un langage différent avec un compilateur dont la sortie est plus rapide, et ainsi de suite.

Cet avertissement est au cœur de la raison pour laquelle nous utilisons l'analyse asymptotique dans la conception d'algorithmes: comme vous n'avez aucune idée de ce que sont les constantes et que les constantes peuvent changer en fonction de facteurs environnementaux, le mieux que nous pouvons faire est une analyse asymptotique.

Maintenant, dans le cas de $\log n$$\log \log n$$2^{32}$$\log 2^{32} = 32$$\log 32 = 5$