webentwicklung-frage-antwort-db.com.de

Unterschied zwischen O(n) und O(log(n)) - was ist besser und was genau ist O (log (n))?

Dies ist mein erster Kurs in Datenstrukturen und in jeder Vorlesung/TA-Vorlesung sprechen wir über O(log(n)). Dies ist wahrscheinlich eine dumme Frage, aber ich würde mich freuen, wenn mir jemand genau erklären könnte, was das bedeutet!?

39
ron

Dies bedeutet, dass das betreffende Objekt (normalerweise die Laufzeit) in einer Weise skaliert wird, die mit dem Logarithmus seiner Eingabegröße übereinstimmt.

Big-O-Notation bedeutet nicht eine exakte Gleichung, sondern eine Grenze . Beispielsweise ist die Ausgabe der folgenden Funktionen alle O (n):

f(x) = 3x
g(x) = 0.5x
m(x) = x + 5

Denn wenn Sie x erhöhen, werden ihre Ausgaben alle linear erhöht. Wenn zwischen f(n) und g(n) ein Verhältnis von 6: 1 besteht, besteht auch ein Verhältnis von ungefähr 6: 1 zwischen f(10*n) und g(10*n) und so weiter.


Überlegen Sie, ob O(n) oder O(log n) besser ist: wenn n = 1000, dann log n = 3 (für log-base-10). Welchen Algorithmus möchten Sie lieber ausführen lassen: 1000 Sekunden oder 3 Sekunden?

72
Amber

Für die Eingabe der Größe n führt ein Algorithmus von O(n) Schritte proportional zu n aus, während ein anderer Algorithmus von O(log(n)) Schritte ungefähr log(n) ausführt. 

Natürlich ist log(n) kleiner als n, daher ist der Algorithmus der Komplexität O(log(n)) besser. Da wird es viel schneller.

9
anuragsn7

Für die kurze Antwort ist O (log n) besser als O (n)

Was genau ist nun O (log n)?

Im Allgemeinen bezieht sich log n auf den Logarithmus zur Basis 2 (auf dieselbe Weise ln) stellt Basis-E-Logarithmen dar). Dieser Logarithmus zur Basis 2 ist das Inverse einer Exponentialfunktion. Eine Exponentialfunktion wächst sehr schnell und wir können intuitiv ableiten, dass sie genau das Gegenteil bewirkt, dh wächst sehr langsam.

Zum Beispiel

x = O (log n)

Wir können n darstellen als,

n = 2x

Und

210 = 1024 → lg (1024) = 10

220 = 1.048.576 → lg (1048576) = 20

230 = 1.073.741.824 → lg (1073741824) = 30

Große Inkremente in n führen nur zu einer sehr geringen Zunahme von log (n)

Für eine Komplexität von O(n) erhalten wir dagegen eine lineare Beziehung

Ein Faktor von log2n sollte jederzeit um den Faktor n übernommen werden.

Um dies weiter zu festigen, stieß ich auf ein Beispiel in Algorithmen, die von Thomas Cormen freigeschaltet wurden

Betrachten Sie zwei Computer: A und B

Beide Computer haben die Aufgabe, ein Array nach einem Wert zu durchsuchen. Nehmen wir an, die Arrays haben 10 Millionen Elemente, die durchsucht werden müssen

Computer A - Dieser Computer kann 1 Milliarde Anweisungen pro Sekunde ausführen und es wird erwartet, dass er die obige Aufgabe unter Verwendung eines Algorithmus mit einer Komplexität von O (n) ausführt. Wir können die Zeit schätzen, die dieser Computer benötigt, um die Aufgabe auszuführen

n/(Anweisungen p Sekunde) → 107/ 10 ^ 9 = 0,01 Sekunden

Computer B - Dieser Computer ist viel langsamer und kann nur 10 Millionen Anweisungen pro Sekunde ausführen. Von Computer B wird erwartet, dass er die obige Aufgabe unter Verwendung eines Algorithmus mit einer Komplexität von O (log n) ausführt. Wir können die Zeit schätzen, die dieser Computer benötigt, um die Aufgabe auszuführen

log (n)/(Anweisungen p Sekunde) → log (107)/107 = 0,000002325349

Anhand dieser Abbildung können wir erkennen, dass Computer A aufgrund des von B verwendeten Algorithmus die Aufgabe viel schneller erledigt, obwohl er viel besser ist als Computer B.

Ich denke, es sollte jetzt klar sein, warum O(log(n)) viel schneller ist als O (n)

8
tayo
1
user1311390

O (logn) bedeutet, dass die maximale Laufzeit des Algorithmus proportional zum Logarithmus der Eingangsgröße ist . O (n) bedeutet, dass die maximale Laufzeit des Algorithmus proportional zur Eingangsgröße ist.

im Grunde ist O(something) eine Obergrenze für die Anzahl der Befehle des Algorithmus (atomare Anweisungen). Daher ist O(logn) fester als O(n) und auch hinsichtlich der Algorithmenanalyse besser. Aber alle Algorithmen, die O(logn) sind, sind auch O (n), aber nicht rückwärts ...

1
Eyal

Formale Definition:

g (x) = O(f(x)) <=> gibt es x0 und die Konstante C, dass für jedes x> x0, | g (x) | <= C | f (x) |.

Wenn Sie also den Algorithmus A für das Problem P finden, dass seine Komplexität O (f (n)), Ist, können Sie sagen, dass die Anzahl der Schritte, die Ihr Algorithmus ausführen wird, niedriger oder gleich asymptotisch zu f (n) ist, wenn n ist normalerweise die Eingangsgröße. (n kann alles sein)

Weitere Informationen: http: //en.wikipedia.org/wiki/Big_O_notation.

0
barak1412