Amarengo

Articles and news

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

O(log log n) Begriffe können an verschiedenen Stellen angezeigt werden, aber es gibt normalerweise zwei Hauptrouten, die zu dieser Laufzeit gelangen.

Schrumpfen um eine Quadratwurzel

Wie in der Antwort auf die verknüpfte Frage erwähnt, besteht eine übliche Möglichkeit für einen Algorithmus, die Zeitkomplexität O (log n) zu haben, darin, dass dieser Algorithmus wiederholt arbeitet Reduzieren Sie die Größe der Eingabe bei jeder Iteration um einen konstanten Faktor. Wenn dies der Fall ist, muss der Algorithmus nach O (log n) Iterationen beendet werden, da der Algorithmus nach O (log n) Divisionen durch eine Konstante die Problemgröße auf 0 oder 1 verkleinern muss. Aus diesem Grund hat beispielsweise die binäre Suche die Komplexität O (log n).

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

Nehmen wir zum Beispiel die Zahl 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 Prozess dauert 16 Schritte, und es ist auch der Fall, dass 65.536 = 216.

Aber wenn wir die Quadratwurzel auf jeder Ebene nehmen, erhalten wir

  • √65,536 = 256
  • √256 = 16
  • √16 = 4
  • √4 = 2

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

Zunächst eine intuitive Erklärung. Wie viele Ziffern haben die Zahlen n und √n? Es gibt ungefähr log n Ziffern in der Zahl n und ungefähr log (√n) = log (n1 / 2) = (1/2) log n Ziffern in √n. Dies bedeutet, dass Sie jedes Mal, wenn Sie eine Quadratwurzel nehmen, die Anzahl der Ziffern in der Zahl ungefähr halbieren. Da Sie eine Menge k O (log k) nur halbieren können, bevor sie auf eine Konstante (z. B. 2) abfällt, bedeutet dies, dass Sie nur Quadratwurzeln O (log log n) nehmen können, bevor Sie die Zahl auf eine Konstante (z. B. 2) reduziert haben.

Nun, lassen Sie uns etwas Mathe machen, um dies rigoros zu machen. Le’ts schreiben die obige Sequenz in Zweierpotenzen um:

  • √65,536 = √216 = (216)1/2 = 28 = 256
  • √256 = √28 = (28)1/2 = 24 = 16
  • √16 = √24 = (24)1/2 = 22 = 4
  • √4 = √22 = (22)1/2 = 21 = 2

Beachten Sie, dass wir der Sequenz gefolgt sind 216 → 28 → 24 → 22 → 21. Bei jeder Iteration halbieren wir den Exponenten der Potenz von zwei. Das ist interessant, weil dies eine Verbindung zu dem herstellt, was wir bereits wissen – Sie können die Zahl k nur in die Hälfte O (log k) teilen, bevor sie auf Null fällt.

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

Ein reales Beispiel dafür ist die van Emde Boas Tree (vEB-tree) Datenstruktur. Ein vEB-Baum ist eine spezielle Datenstruktur zum Speichern von Ganzzahlen im Bereich 0 … N – 1. Es funktioniert wie folgt: Der Wurzelknoten des Baums enthält √N Zeiger, die den Bereich 0 aufteilen … N – 1 in √ N Buckets, die jeweils einen Bereich von ungefähr √ N ganzen Zahlen enthalten. Diese Buckets werden dann jeweils intern in √ (√ N) Buckets unterteilt, von denen jeder ungefähr √ (√ N) Elemente enthält. Um den Baum zu durchlaufen, beginnen Sie am Stamm, bestimmen, zu welchem Bucket Sie gehören, und fahren dann rekursiv im entsprechenden Teilbaum fort. Aufgrund der Art und Weise, wie der vEB-Baum strukturiert ist, können Sie in O (1) -Zeit bestimmen, in welchen Teilbaum Sie absteigen möchten, und so erreichen Sie nach O (log log N) -Schritten das Ende des Baums. Dementsprechend dauern Suchvorgänge in einem vEB-Baum nur O (log log N).

Ein weiteres Beispiel ist der Hopcroft-Fortune closest pair of points Algorithmus. Dieser Algorithmus versucht, die beiden nächstgelegenen Punkte in einer Sammlung von 2D-Punkten zu finden. Es funktioniert, indem ein Raster von Buckets erstellt und die Punkte in diese Buckets verteilt werden. Wenn an einem beliebigen Punkt im Algorithmus ein Bucket gefunden wird, der mehr als √N Punkte enthält, verarbeitet der Algorithmus diesen Bucket rekursiv. Die maximale Tiefe der Rekursion ist daher O (log log n), und anhand einer Analyse des Rekursionsbaums kann gezeigt werden, dass jede Schicht im Baum O (n) funktioniert. Daher ist die Gesamtlaufzeit des Algorithmus O (n log log n).

O (log n) Algorithmen für kleine Eingaben

Es gibt einige andere Algorithmen, die O (log log n) Laufzeiten 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 Ebenen eines Baums der Höhe O(log U) durch, sodass die Laufzeit für einige ihrer Operationen O(log log U) . Der zugehörige y-Fast-Trie erhält einige seiner O (log log U) -Laufzeiten, indem ausgeglichene BSTs von jeweils O (log U) -Knoten beibehalten werden, sodass Suchen in diesen Bäumen in der Zeit O (log log U) ausgeführt werden können. Der Tango-Baum und die zugehörigen Multiplay-Baumdatenstrukturen erhalten in ihren Analysen einen O (log log n) -Term, da sie Bäume pflegen, die jeweils 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 aufwendig. Letztendlich zeigt die Analyse, dass die Anzahl der Iterationen gleich der Anzahl k ist, sodass n2-k ≤ 2 ist, für die log log n die richtige Lösung ist. Einige Algorithmen, wie der Cheriton-Tarjan-MST-Algorithmus, erreichen eine Laufzeit mit O (log log n), indem sie ein komplexes beschränktes Optimierungsproblem lösen.

Hoffe das hilft!

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.