Bestimmen, ob ein Algorithmus O ist (log n)

25

Ich aktualisiere meine CS-Theorie und möchte wissen, wie man die Komplexität eines Algorithmus O (log n) identifiziert. Gibt es eine einfache Möglichkeit, es zu identifizieren?

Ich weiß, mit O (n) hast du normalerweise eine einzelne Schleife; O (n ^ 2) ist eine Doppelschleife; O (n ^ 3) ist eine Dreifachschleife usw. Wie wäre es mit O (log n)?

Atif
quelle
Ah, das ist der einzige Ort, an dem ich nicht hingeschaut habe :)
Atif

Antworten:

32

Ich weiß, mit O (n) hast du normalerweise eine einzelne Schleife; O (n ^ 2) ist eine Doppelschleife; O (n ^ 3) ist eine Dreifachschleife usw. Wie wäre es mit O (log n)?

Du machst es hier wirklich falsch. Sie versuchen sich zu merken, welcher Big-O-Ausdruck zu einer bestimmten algorithmischen Struktur gehört, aber Sie sollten wirklich nur die Anzahl der Operationen, die der Algorithmus benötigt, hochzählen und diese mit der Größe der Eingabe vergleichen. Ein Algorithmus, der seine gesamte Eingabe durchläuft, hat eine O (n) -Leistung, weil er die Schleife n-mal durchläuft, und nicht, weil er eine einzelne Schleife hat. Hier ist eine einzelne Schleife mit O (log n) -Leistung:

for (i = 0; i < log2(input.count); i++) {
    doSomething(...);
}

Jeder Algorithmus, bei dem die Anzahl der erforderlichen Operationen in der Größenordnung des Logarithmus der Größe der Eingabe liegt, ist also O (log n). Aus der Big-O-Analyse geht hervor, wie sich die Ausführungszeit eines Algorithmus im Verhältnis zur Größe der Eingabe ändert: Wenn Sie die Größe der Eingabe verdoppeln, führt der Algorithmus einen weiteren Schritt aus (O (log n)). , doppelt so viele Schritte (O (n)), viermal so viele Schritte (O (n ^ 2)) usw.

Hilft es aus Erfahrung zu wissen, dass Algorithmen, die ihre Eingaben wiederholt partitionieren, normalerweise "log n" als Komponente ihrer Leistung haben? Sicher. Aber suchen Sie nicht nach der Partitionierung und gehen Sie zu dem Schluss, dass die Leistung des Algorithmus O (log n) ist - es könnte sich um etwas wie O (n log n) handeln, was ganz anders ist.

Caleb
quelle
3
Man beachte, dass eine umgangssprachlichere Möglichkeit, "in der Reihenfolge des Logarithmus der Größe" zu sagen, darin besteht, "in der Reihenfolge der Anzahl der Ziffern in der Größe" zu sagen.
@Caleb Die tatsächliche Basis des Logarithmus ist für die Skalierung unwichtig.
@Caleb Absolutes zu reden macht bei big-O keinen Sinn. Eine Formulierung, die Ihnen vielleicht besser gefällt: Wenn sich die Anzahl der Stellen verdoppelt, verdoppelt sich die Anzahl der Schritte.
@Caleb Absolutes zu reden macht bei big-O keinen Sinn. Eine Formulierung, die Ihnen vielleicht besser gefällt: Wenn sich die Anzahl der Stellen verdoppelt, verdoppelt sich die Anzahl der Schritte.
@ ThorbjørnRavnAndersen Ja, das bedeutet "der Logarithmus der Größe". Ich bin mir nicht sicher, was dein Problem mit der Phrase ist, außer dass du es anders gesagt hättest. Grundsätzlich denke ich, dass wir uns einig sind.
Caleb
25

Die Idee ist, dass ein Algorithmus besteht, O(log n)wenn Sie, anstatt 1 zu 1 durch eine Struktur zu scrollen, die Struktur immer wieder in zwei Hälften teilen und für jede Teilung eine konstante Anzahl von Operationen ausführen. Suchalgorithmen, bei denen der Antwortraum immer weiter aufgeteilt wird, sind O(log n). Ein Beispiel hierfür ist die binäre Suche , bei der Sie ein geordnetes Array immer wieder halbieren, bis Sie die Nummer gefunden haben.

Hinweis: Sie müssen nicht unbedingt in gerade Hälften teilen.

Casey Patton
quelle
1
Was passiert, wenn ich die Eingabe in zwei Teile teile und dann den Rest 2 ^ (n / 2) Mal durchlaufe, bevor ich sie erneut teile? (Natürlich weiß ich was dann, ich wollte nur ein Beispiel zeigen, wo dieser vereinfachende Ansatz fehlschlägt).
Tamás Szelei
@afish Das ist eher selten. Es ist spektakulär selten bei der Suche.
Donal Fellows
1
@DonalFellows Die Algorithmus-Theorie ist keine empirische Wissenschaft. Und es ging nicht um die Suche, sondern nur um die Erwähnung von log nausgelösten binären Suchreflexen bei Menschen.
Tamás Szelei
2
Durch die Partitionierung wird der Algorithmus nicht zu O (log n), sondern (normalerweise) zu einem Faktor von log n zum Big-O-Limit hinzugefügt. Rekursive Sortierungen wie Heapsort und Mergesort sind perfekte Beispiele: Sie partitionieren die Eingabe, aber dann partitionieren sie beide resultierenden Partitionen rekursiv. Das Ergebnis ist die Leistung von O (n log n).
Caleb
@ Fisch: Guter Punkt. Mein Ziel bei dieser Antwort ist es, sie angesichts der Art der Frage so einfach wie möglich zu halten. Ich habe die Zeile "Sie teilen die Struktur in zwei Hälften ..." in "Sie teilen die Struktur in zwei Hälften ... und mache eine konstante Anzahl von Operationen für jede Teilung" geändert, um zu versuchen, diesen Punkt einfach zu vermitteln.
Casey Patton
2

Die typischen Beispiele sind solche, die sich mit der binären Suche befassen. Zum Beispiel ist ein binärer Suchalgorithmus normalerweise O(log n).

Wenn Sie einen binären Suchbaum haben , sind das Nachschlagen, Einfügen und Löschen O(log n)kompliziert.

In jeder Situation, in der Sie den Space kontinuierlich partitionieren, wird häufig eine log nKomponente benötigt. Dies ist der Grund, warum viele Sortieralgorithmen komplex sind O(nlog n), da sie häufig eine Menge aufteilen und sortieren, während sie arbeiten.

Kris Harper
quelle
1

Wenn Sie es so einfach wie "Einzelschleife -> O (n), Doppelschleife -> O (n ^ 2)" wollen, lautet die Antwort wahrscheinlich "Baum -> O (log n)". Präziseres Überqueren eines Baumes von der Wurzel zu einem (nicht allen!) Blatt oder umgekehrt. Dies sind jedoch alles Übervereinfachungen.

Narbenkühlschrank
quelle
Also, was ist los mit meiner Antwort? Ich bin offen für konstruktive Kritik.
Scarfridge
0

Sie möchten wissen, ob es eine einfache Möglichkeit gibt, festzustellen, ob ein Algorithmus O (log N) ist.

Nun, lauf einfach und leg los. Führen Sie es für Eingaben 1.000, 10.000, 100.000 und eine Million aus.

Wenn Sie eine Laufzeit von 3,4,5,6 Sekunden (oder ein Vielfaches davon) sehen, können Sie sicher sagen, dass es O (log N) ist. Wenn es eher wie folgt aussieht: 1,10,100,1000 Sekunden, dann ist es wahrscheinlich O (N). Und wenn es wie 3,40,500,6000 Sekunden ist, dann ist es O (N log N).

Pieter B
quelle
Jeder sollte dieser Antwort eine positive und eine negative Bewertung geben, beide aus offensichtlichen Gründen :-)
gnasher729