Was würde dazu führen, dass ein Algorithmus eine Komplexität von O (log log n) aufweist?

Diese frühere Frage befasst sich mit einigen Faktoren, die dazu führen können, dass ein Algorithmus eine O (log n) -Komplexität aufweist.

Was würde dazu führen, dass ein Algorithmus Zeitkomplexität O (log log n) hat?

O-Begriffe (log log n) können an verschiedenen Orten angezeigt werden. In der Regel gibt es jedoch zwei Hauptrouten, die zu dieser Laufzeit eintreffen.

Schrumpfen um eine Quadratwurzel

Wie in der Antwort auf die verknüpfte Frage erwähnt, besteht eine übliche Methode für einen Algorithmus, Zeitkomplexität O (log n) zu haben, darin, dass dieser Algorithmus arbeitet, indem die Größe der Eingabe bei jeder Iteration wiederholt um einen konstanten Faktor verringert wird. Wenn dies der Fall ist, muss der Algorithmus nach O (log n) -Iterationen beendet werden, da der Algorithmus nach dem Ausführen von O (log n) -Divisionen durch eine Konstante die Problemgröße auf 0 oder 1 verkleinern muss. Deshalb zum Beispiel Die binäre Suche hat die Komplexität O (log n).

Interessanterweise gibt es eine ähnliche Methode, um die Größe eines Problems zu verringern, das Laufzeiten der Form O (log log n) ergibt. Was passiert, wenn wir die Quadratwurzel der Größe auf jeder Ebene ziehen, anstatt die Eingabe auf jeder Ebene in zwei Hälften zu teilen ?

Nehmen wir zum Beispiel die Nummer 65.536. Wie oft müssen wir dies durch 2 teilen, bis wir auf 1 kommen? Wenn wir das tun, bekommen wir

• 65.536 / 2 = 32.768
• 32.768 / 2 = 16.384
• 16.384 / 2 = 8.192
• 8,192 / 2 = 4,096
• 4,096 / 2 = 2,048
• 2,048 / 2 = 1,024
• 1.024 / 2 = 512
• 512/2 = 256
• 256/2 = 128
• 128/2 = 64
• 64/2 = 32
• 32/2 = 16
• 16/2 = 8
• 8/2 = 4
• 4/2 = 2
• 2/2 = 1

Dieser Vorgang dauert 16 Schritte, und es ist auch der Fall, dass 65.536 = 2 ¹⁶ .

Aber wenn wir auf jeder Ebene die Quadratwurzel ziehen, bekommen wir

• 65.536 = 256
• √256 = 16
• √16 = 4
• √4 = 2

Beachten Sie, dass es nur vier Schritte dauert, bis 2 erreicht ist. Warum ist das so?

Zunächst eine intuitive Erklärung. Wie viele Ziffern enthalten die Zahlen n und √n? Es gibt ungefähr log n Ziffern in der Zahl n und ungefähr log (√n) = log (n ^1/2 ) = (1/2) log n Ziffern in √n. Dies bedeutet, dass Sie jedes Mal, wenn Sie eine Quadratwurzel ziehen, die Anzahl der Stellen in der Zahl ungefähr halbieren. Da Sie eine Menge nur k O (log k) Mal halbieren können, bevor sie auf eine Konstante (z. B. 2) abfällt, können Sie nur Quadratwurzeln O (log log n) mal ziehen, bevor Sie die Zahl verringert haben zu einer Konstanten (sagen wir 2).

Lassen Sie uns nun etwas rechnen, um dies rigoros zu machen. Le'ts schreibt die obige Sequenz in Zweierpotenzen um:

• √65.536 = √2 ¹⁶ = (2 ¹⁶ ) ^1/2 = 2 ⁸ = 256
• √256 = √2 ⁸ = (2 ⁸ ) ^1/2 = 2 ⁴ = 16
• √16 = √2 ⁴ = (2 ⁴ ) ^1/2 = 2 ² = 4
• √4 = √2 ² = (2 ² ) ^1/2 = 2 ¹ = 2

Beachten Sie, dass wir der Sequenz 2 ¹⁶ → 2 ⁸ → 2 ⁴ → 2 ² → 2 ¹ gefolgt sind . Bei jeder Iteration halbieren wir den Exponenten der Zweierpotenz. Das ist interessant, weil dies auf das zurückführt, was wir bereits wissen - Sie können die Zahl k nur in halbe O (log k) mal teilen, bevor sie auf Null fällt.

Nehmen Sie also eine beliebige Zahl n und schreiben Sie sie als n = 2 ^k . Jedes Mal, wenn Sie die Quadratwurzel von n ziehen, halbieren Sie den Exponenten in dieser Gleichung. Daher können nur O (log k) Quadratwurzeln angewendet werden, bevor k auf 1 oder weniger fällt (in diesem Fall fällt n auf 2 oder weniger ab). Da n = 2 ^{k ist} , bedeutet dies, dass k = log ₂ n ist und daher die Anzahl der Quadratwurzeln O (log k) = O (log log n) ist. Wenn es einen Algorithmus gibt, der das Problem wiederholt auf ein Teilproblem der Größe reduziert, das die Quadratwurzel der ursprünglichen Problemgröße ist, wird dieser Algorithmus nach O-Schritten (log log n) beendet.

Ein reales Beispiel dafür ist der van Emde Boas-Baum(vEB-Baum) Datenstruktur. Ein vEB-Baum ist eine spezialisierte Datenstruktur zum Speichern von Ganzzahlen im Bereich von 0 ... N - 1. Sie funktioniert wie folgt: Der Wurzelknoten des Baums enthält √N Zeiger, die den Bereich 0 ... N - aufteilen. 1 in √N Eimer, die jeweils einen Bereich von ungefähr √N ganzen Zahlen enthalten. Diese Eimer werden dann jeweils intern in √ (√ N) Eimer unterteilt, von denen jeder ungefähr √ (√ N) Elemente enthält. Um den Baum zu durchlaufen, beginnen Sie an der Wurzel, bestimmen, zu welchem ​​Bucket Sie gehören, und fahren dann rekursiv mit dem entsprechenden Teilbaum fort. Aufgrund der Struktur des vEB-Baums können Sie in O (1) -Zeit bestimmen, in welchen Teilbaum Sie absteigen möchten. Nach O (log log N) -Schritten erreichen Sie den unteren Rand des Baums. Dementsprechend benötigen Suchvorgänge in einem vEB-Baum nur Zeit O (Protokollprotokoll N).

Ein weiteres Beispiel ist der Hopcroft-Fortune-Algorithmus für das nächstgelegene Punktepaar . Dieser Algorithmus versucht, die zwei nächstgelegenen Punkte in einer Sammlung von 2D-Punkten zu finden. Es funktioniert, indem ein Raster von Buckets erstellt und die Punkte in diesen Buckets verteilt werden. Wenn zu irgendeinem Zeitpunkt im Algorithmus ein Bucket gefunden wird, der mehr als √N Punkte enthält, verarbeitet der Algorithmus diesen Bucket rekursiv. Die maximale Tiefe der Rekursion beträgt daher O (log log n), und anhand einer Analyse des Rekursionsbaums kann gezeigt werden, dass jede Ebene im Baum O (n) funktioniert. Daher beträgt die Gesamtlaufzeit des Algorithmus O (n log log n).

O (log n) Algorithmen für kleine Eingänge

Es gibt einige andere Algorithmen, die O-Laufzeiten (log log n) erreichen, indem sie Algorithmen wie die binäre Suche nach Objekten der Größe O (log n) verwenden. Beispielsweise führt die x-fast trie- Datenstruktur eine binäre Suche über die Schichten eines Baums mit der Höhe O (log U) durch, sodass die Laufzeit für einige ihrer Operationen O (log log U) ist. Der zugehörige y-fast-Versuch erhält einige seiner O-Laufzeiten (log log U), indem ausgeglichene BSTs von jeweils O (log U) -Knoten beibehalten werden, sodass die Suche in diesen Bäumen in der Zeit O (log log U) ausgeführt werden kann. Der Tango - Baum und verwandte multisplay Baumdatenstrukturen Ende mit einem O (log log n) Laufzeit in ihren Analysen, weil sie Bäume halten , die jedes O (log n) Elemente enthalten.

Andere Beispiele

Andere Algorithmen erreichen die Laufzeit O (log log n) auf andere Weise. Die Interpolationssuche hat erwartet, dass die Laufzeit O (log log n) eine Zahl in einem sortierten Array findet, aber die Analyse ist ziemlich kompliziert. Letztlich ist die Analyse Arbeiten zeigen , dass die Anzahl der Iterationen , die der Anzahl k gleich ist , so daß n ^{2 -k} ≤ 2, für die log log n ist die richtige Lösung. Einige Algorithmen, wie der Cheriton-Tarjan-MST-Algorithmus , erreichen eine Laufzeit mit O (log log n), indem sie ein komplexes Problem der eingeschränkten Optimierung lösen.

Hoffe das hilft!

Eine Möglichkeit, den Faktor O (log log n) in der Zeitkomplexität zu sehen, besteht in der Division, wie in der anderen Antwort erläutert, aber es gibt eine andere Möglichkeit, diesen Faktor zu sehen, wenn wir einen Handel zwischen Zeit und Raum / Zeit machen wollen und Annäherung / Zeit und Härte / ... von Algorithmen und wir haben einige künstliche Iteration auf unserem Algorithmus.

Zum Beispiel hat SSSP (Single Source Shortest Path) einen O (n) -Algorithmus für planare Graphen, aber vor diesem komplizierten Algorithmus gab es einen viel einfacheren (aber immer noch ziemlich harten) Algorithmus mit der Laufzeit O (n log log n), dem Die Basis des Algorithmus ist wie folgt (nur eine sehr grobe Beschreibung, und ich würde anbieten, das Verständnis dieses Teils zu überspringen und den anderen Teil der Antwort zu lesen):

1. Teilen Sie den Graphen mit einigen Einschränkungen in Teile der Größe O (log n / (log log n)).
2. Angenommen, jeder der genannten Teile ist ein Knoten im neuen Graphen G ', dann wird SSSP für G' in der Zeit O (| G '| * log | G' |) ==> hier berechnet, weil | G '| = O (| G | * log log n / log n) können wir den Faktor (log log n) sehen.
3. Berechnen Sie SSSP für jeden Teil: erneut, weil wir einen O (| G '|) - Teil haben und SSSP für alle Teile in der Zeit | n / logn | berechnen können * | log n / log logn * log (logn / log log n).
4. Gewichte aktualisieren, dieser Teil kann in O (n) erfolgen. Für weitere Details sind diese Vorlesungsunterlagen gut.

Mein Punkt ist jedoch, dass wir hier die Division mit der Größe O (log n / (log log n)) auswählen. Wenn wir andere Abteilungen wie O (log n / (log log n) ^ 2) wählen, läuft dies möglicherweise schneller und bringt ein anderes Ergebnis. Ich meine, in vielen Fällen (wie bei Approximationsalgorithmen oder randomisierten Algorithmen oder Algorithmen wie SSSP wie oben) wählen wir, wenn wir über etwas iterieren (Teilprobleme, mögliche Lösungen, ...), die Anzahl der Iterationen, die dem Handel davon entsprechen wir haben (Zeit / Raum / Komplexität des Algorithmus / konstanter Faktor des Algorithmus, ...). Vielleicht sehen wir in realen Arbeitsalgorithmen kompliziertere Dinge als "log log n".