Logarithmiques vs à double complexité temporelle logarithmique

Question

Dans des applications réelles du monde est-il un avantage concret en utilisant $ \ mathcal {O} (\ log (\ log (n)) $ au lieu de $ \ mathcal {O} (\ log (n)) $ algorithmes?

Ceci est le cas quand on l'utilisation par exemple van Emde Boas arbres au lieu d'implémentations d'arbres de recherche binaires plus conventionnels. Mais par exemple, si l'on prend $ n <10 ^ 6 $, alors dans le meilleur des cas, la double algorithme logarithmique surclasse celui logarithmique par (environ) un facteur de 5 $ $. Et en général, la mise en œuvre est plus délicate et complexe.

Étant donné que je préfère BST sur VEB arbres, que pensez-vous?

On pourrait facilement démontrer que:

$ \ qquad \ displaystyle \ forall n <10 ^ 6. \ \ Frac {\ log n} {\ log (\ log (n))} <5,26146 $

Answer 1

Ne pas oublier que $ \ log n $ croît de façon exponentielle encore (en $ \ log (n) $) plus vite que $ \ log (\ log n) $!

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

^{[ la source ]}

Mais encore, vous obtenez un facteur de cinq à six pour les tailles jusqu'à 100 000 $ $. Notez que les grandes tailles ne sont pas rares dans la pratique, et par ce facteur speedup est génial ! Il peut faire la différence entre avoir des résultats après le déjeuner ou demain seulement. Sachez qu'une partie peut être le speedup rongé par des constantes plus élevées de la mise en œuvre de l'arbre; vous auriez à tracer (ou d'analyser) $ c \ cdot \ log (n) $ et $ d \ cdot \ log (\ log (n)) $ avec $ c, d $ les constantes d'exécution réelles pour obtenir une image réelle.

De plus, ce que Dave mentionne est important: si l'opération est exécutée accéléra, dire thusly, souvent de façon linéaire, constante speedups deviennent linéaires speedups, à savoir que vous pouvez diminuer la constante de premier plan de votre algorithme entier! Comme je l'ai dit plus haut, c'est génial. Il suffit de regarder ce qui se passe si vous exécutez l'opération $ n $ fois:

^{[ la source ]}

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

Answer 2

On pourrait imaginer que la différence de complexité n'a pas d'importance tant, et que l'exécution réelle 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 de cours est importante, surtout si l'algorithme est une partie d'une autre. Il peut mettre l'algorithme plus dans une autre classe de complexité.

Answer 3

Je l'ai fait étalonnée van Emde-Boas moi-même arbre une fois. Je l'ai comparé avec un arbre AA, un hashmap et un tableau de bits.

Les tests effectuent inserts size avec des nombres aléatoires dans l'intervalle [0, bound], puis recherche size, puis supprime size, puis de nouveau les recherches size. Les suppressions sont effectuées sur des nombres aléatoires aussi bien, de sorte que vous devez d'abord savoir si elles sont dans la structure du tout.

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, van arbres Emde-Boas sont environ deux fois plus lent que les cartes de hachage, dix fois plus lent que les tableaux de bits, et 5 fois plus rapide que les arbres binaires de recherche.

Bien sûr, les besoins ci-dessus une mise en garde:. Les tests sont artificiels, vous pouvez éventuellement améliorer le code ou utiliser une autre langue avec un compilateur dont la sortie est plus rapide, et ainsi de suite et ainsi de suite

Cette exclusion de responsabilité est au cœur de la raison pour laquelle nous utilisons l'analyse asymptotique dans les algorithmes de conception: comme vous ne savez pas ce que les constantes sont et que les constantes peuvent varier en fonction des facteurs environnementaux, le mieux que nous pouvons faire est une analyse asymptotique.

, dans le cas de $ \ log n $ par rapport à $ \ log \ log n $: dans l'exemple ci-dessus, mon arbre van Emde-Boas est capable de contenir 2 $ ^ {32} $ éléments. $ \ Log 2 ^ {32} = 32 $, et $ \ log 32 = 5 $, ce qui est un facteur 6 amélioration, ce qui est un peu dans la pratique. De plus, les arbres van Emde-Boas ont de bons facteurs constants (il est tout au sujet des facteurs constants dans la pratique des différences ce petit) car ils ne ont pas besoin de s'équilibrer.