Logarithmische gegen doppelte logarithmische Zeitkomplexität

Question

In realen Anwendungen gibt es einen konkreten Nutzen bei der Verwendung von $ mathcal {o} ( log ( log (n)) $ anstelle von $ mathcal {o} ( log (n)) $ algorithmen?

Dies ist der Fall, wenn eine Verwendung beispielsweise van Emde Boas -Bäume anstelle von konventionelleren Binär -Suchbäumen -Implementierungen. Wenn wir beispielsweise $ n <10^6 $ nehmen, übertrifft der doppelte logarithmische Algorithmus im besten Fall den logarithmischen Faktor von $ 5 $. Und im Allgemeinen ist die Implementierung schwieriger und komplexer.

Was denkst du, wenn ich persönlich BST gegenüber VEB-Bäumen bevorzuge?

Man könnte leicht zeigen:

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

Answer 1

Vergessen Sie nicht, dass $ log n $ weiterhin exponentiell (in $ log (n) $) schneller wächst als $ log ( log n) $!

Wenn Sie sich den Quotienten von $ log (n) $ und $ log ( log (n)) $ ansehen, gibt es nicht viel beeindruckend zu sehen:

^[Quelle]

Trotzdem erhalten Sie einen Faktor fünf bis sechs für Größen bis zu 100000 US -Dollar. Beachten Sie, dass größere Größen in der Praxis nicht ungewöhnlich sind, und eine Beschleunigung durch diesen Faktor ist fantastisch! Es kann den Unterschied zwischen den Ergebnissen nach dem Mittagessen oder nur morgen ausmachen. Beachten Sie, dass ein Teil der Beschleunigung durch höhere Konstanten der Umsetzung von Baum gefressen werden kann. Sie müssten $ c cdot log (n) $ und $ d cdot log ( log (n)) $ mit $ c, d $ die tatsächlichen Laufzeitkonstanten zeichnen (oder analysieren), um ein echtes Bild zu erhalten.

Darüber hinaus ist das, was Dave erwähnt, wichtig: Wenn die Operation so ausgeführt wird, dass beispielsweise linear häufig ständige Beschleunigungen linear werden, können Sie die führende Konstante Ihres gesamten Algorithmus verringern! Wie ich oben sagte, ist das großartig. Schauen Sie sich einfach an, was passiert, wenn Sie die Operation $ n $ mal ausführen:

^[Quelle]

Wenn das nicht die Mühe wert ist, weiß ich nicht was.

Answer 2

Man könnte sich vorstellen, dass der Unterschied in der Komplexität wirklich nicht so wichtig ist und dass die tatsächliche Laufzeit wichtiger ist. Wenn der Algorithmus jedoch im Kern eines anderen Algorithmus ist, kann dieser Unterschied wichtig sein.

Aus einem rein theoretischen Zweck ist der Unterschied natürlich wichtig, insbesondere wenn der Algorithmus ein Teil eines anderen ist. Es kann den größeren Algorithmus in eine andere Komplexitätsklasse bringen.

Answer 3

Ich habe den Van Emde-Boas-Baum selbst einmal einmal untersucht. Ich habe es mit einem AA -Baum, einem Hashmap und einem bisschen Array verglichen.

Die Tests werden durchgeführt size Einfügt mit Zufallszahlen im Intervall ein [0, bound], dann size Suchanfragen dann size löscht und dann wieder size Suchanfragen. Deletes werden auch mit Zufallszahlen durchgeführt, sodass Sie zuerst herausfinden müssen, ob sie überhaupt in der Struktur sind.

Hier sind die Ergebnisse (size=2000000, bound= 10000000) in Sekunden:

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

Wie Sie sehen können, sind Van Emde-Boas-Bäume ungefähr doppelt so langsam wie Hash-Karten, zehnmal so langsam wie Bit-Arrays und 5-mal so schnell wie binäre Suchbäume.

Natürlich braucht der oben genannte Haftungsausschluss: Die Tests sind künstlich, Sie können den Code möglicherweise verbessern oder eine andere Sprache mit einem Compiler verwenden, dessen Ausgabe schneller ist, und so weiter und so weiter.

Dieser Haftungsausschluss steht im Mittelpunkt des Grundes, warum wir die asymptotische Analyse im Design von Algorithmen verwenden: Da Sie keine Ahnung haben, was die Konstanten sind und wie sich die Konstanten je nach Umweltfaktoren ändern können, können wir am besten eine asymptotische Analyse tun.

Im Fall von $ log n $ gegen $ log log n $: Im obigen Beispiel kann mein Van Emde-Boas-Baum $ 2^{32} $ Elemente enthalten. $ log 2^{32} = 32 $ und $ log 32 = 5 $, was eine Verbesserung der Faktor 6 darstellt, was in der Praxis ziemlich viel ist. Darüber hinaus haben Van Emde-Boas-Bäume gute konstante Faktoren (es geht um ständige Faktoren in der Praxis für so kleine Unterschiede), da sie sich nicht ausgleichen müssen.