Logarithmische vs doppelte logarithmische Zeitkomplexität

Gibt es in realen Anwendungen einen konkreten Vorteil bei der Verwendung von anstelle von O ( log ( n ) ) Algorithmen?$\mathcal{O}(\log(\log(n))$$\mathcal{O}(\log(n))$

Dies ist der Fall, wenn beispielsweise Van-Emde-Boas-Bäume anstelle herkömmlicherer binärer Suchbaumimplementierungen verwendet werden. Wenn wir zum Beispiel nehmen, übertrifft der doppelte logarithmische Algorithmus im besten Fall den logarithmischen um (ungefähr) den Faktor 5 . Und auch im Allgemeinen ist die Implementierung schwieriger und komplexer.$n < 10^6$$5$

Was denkst du, da ich BST persönlich VEB-Bäumen vorziehe?

Man könnte leicht zeigen, dass:

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

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

Wenn Sie sich den Quotienten aus und log ( log ( n ) ) ansehen, ist in der Tat nicht viel Beeindruckendes zu sehen:$\log(n)$$\log(\log(n))$

^{[ Quelle ]}

Trotzdem erhalten Sie einen Faktor fünf bis sechs für Größen bis zu . Beachten Sie, dass größere Größen in der Praxis keine Seltenheit sind und eine Beschleunigung um diesen Faktor fantastisch ist ! Es kann den Unterschied zwischen Ergebnissen nach dem Mittagessen oder erst morgen ausmachen. Beachten Sie, dass ein Teil der Beschleunigung möglicherweise von höheren Konstanten der Baumimplementierung verschlungen wird. Sie müssten c ⋅ log ( n ) und d ⋅ log ( log ( n ) ) mit c , d der tatsächlichen Laufzeitkonstanten zeichnen (oder analysieren) , um ein reales Bild zu erhalten.$100000$$c\cdot \log(n)$$d\cdot \log(\log(n))$$c,d$

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

^{[ Quelle ]}

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

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 sich der Algorithmus jedoch im Kern eines anderen Algorithmus befindet, kann dieser Unterschied wichtig sein.

Aus rein theoretischen Gründen spielt der Unterschied natürlich eine Rolle, insbesondere wenn der Algorithmus Teil eines anderen ist. Es kann den größeren Algorithmus in eine andere Komplexitätsklasse einordnen.

Ich habe den van Emde-Boas-Baum tatsächlich einmal selbst gemessen. Ich habe es mit einem AA-Baum, einer Hashmap und einem Bit-Array verglichen.

Die Tests führen sizeEinfügungen mit Zufallszahlen im Intervall durch [0, bound], sizesuchen dann, sizelöschen und sizesuchen dann erneut . Löschvorgänge werden auch für Zufallszahlen ausgeführt, sodass Sie zuerst herausfinden müssen, ob sie überhaupt in der Struktur enthalten 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 etwa doppelt so langsam wie Hash-Maps, zehnmal so langsam wie Bit-Arrays und fünfmal so schnell wie binäre Suchbäume.

Für die oben genannten Punkte ist natürlich ein Haftungsausschluss erforderlich: Die Tests sind künstlich, Sie können möglicherweise den Code verbessern oder eine andere Sprache mit einem Compiler verwenden, dessen Ausgabe schneller ist, und so weiter und so fort.

Dieser Haftungsausschluss ist der Grund für die Verwendung der asymptotischen Analyse beim Entwurf von Algorithmen: Da Sie keine Ahnung haben, wie die Konstanten lauten, und sich die Konstanten in Abhängigkeit von Umgebungsfaktoren ändern können, können wir am besten eine asymptotische Analyse durchführen.

$\log n$$\log \log n$$2^{32}$$\log 2^{32} = 32$$\log 32 = 5$