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

70

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

algorithm data-structures complexity-theory big-o logarithm JAN
quelle
2
Eine mögliche Wiederholung von stackoverflow.com/questions/487258/…
sank am
2
Whoa, 1429 positive Stimmen? Ich werde mit der Hälfte davon für meinen Wikipedia-Link zufrieden sein.
Hat mir die Informationen gegeben, die ich brauchte.
MadHatter

Antworten:

90

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

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

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

Denn wie Sie x zu erhöhen, deren Ausgänge alle Anstiege linear - wenn es ein 6 ist: 1 - Verhältnis zwischen f(n)und g(n), es wird auch etwa ein 6: 1 - Verhältnis zwischen f(10*n)und g(10*n)und so weiter.

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

Bernstein
quelle
29
Schön erklärt. Außerdem möchte ich einige Informationen darüber hinzufügen, was ein Logarithmus überhaupt für diejenigen ist, die es nicht wissen. log n in der Informatik bedeutet, der Exponent, den ich benötigen würde, um die Zahl 2 zu erhöhen, um n zu erhalten. Stellen Sie sich also vor, wenn n = 16. Unser Exponent wäre viel viel kleiner als der tatsächliche n-Wert. Es wäre 4. Hoffe das macht Sinn. In dem obigen Beispiel von Amber gibt sie ein ähnliches Beispiel, erhöht aber 10 auf die Potenz von 3.
Horse Voice
1
+1 - Die klarste Erklärung, die in der kleinsten Anzahl von Wörtern möglich ist. Vielen Dank.
Techfoobar
1
Erwähnenswert ist auch, dass sich Big-O im Allgemeinen auf jede Bindung bezieht , nicht unbedingt auf die engste Grenze (dh das kleinste g (x), so dass f (x) = O (g (x))). f(x), g(x), m(x)Auch O (n ^ 2). Im Zusammenhang mit der Leistungsanalyse möchten wir jedoch, dass die tightestGrenze (dh die kleinste Funktion, die die Leistungskurve eines bestimmten Algorithmus begrenzt) uns eine "Worst-Case" -Idee der Leistung eines Algorithmus gibt.
Minh Tran
@Horse Voice In Ihrem Beispiel verwenden Sie 2 ** 4, während in Bernsteins Code das Beispiel ist 10 ** 3; Wie bestimme ich Parameter?
MadHatter
Dieser Link zeigt eine Grafik mit all den verschiedenen Komplexitäten: bigocheatsheet.com
silver_mx
24

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

Was genau ist nun O (log n)?

Wenn man sich auf die große O-Notation bezieht, bezieht sich log n im Allgemeinen auf den Logarithmus zur Basis 2 (auf die gleiche Weise repräsentiert ln die Logarithmen der Basis e). Dieser Logarithmus zur Basis 2 ist die Umkehrung einer Exponentialfunktion. Eine Exponentialfunktion wächst sehr schnell und wir können intuitiv ableiten, dass ihre Umkehrung genau das Gegenteil bewirkt, dh sehr langsam wächst .

Zum Beispiel

x = O (log n)

Wir können n darstellen als,

n = 2 x

Und

2 10 = 1024 → lg (1024) = 10

2 20 = 1.048.576 → lg (1048576) = 20

2 30 = 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 andererseits eine lineare Beziehung

Ein Faktor von log 2 n sollte jederzeit übernommen werden. Ein Faktor von n.

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

Betrachten Sie 2 Computer: A und B.

Beide Computer haben die Aufgabe, ein Array nach einem Wert zu durchsuchen. Nehmen wir an, die Arrays enthalten 10 Millionen zu durchsuchende Elemente

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

n / (Anweisungen p Sekunde) → 10 7/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 als zu erledigen

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

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

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

tayo
quelle
16

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

Ist eindeutig log(n)kleiner als ndaher ist der Algorithmus der Komplexität O(log(n))besser. Da wird es viel schneller gehen.

anuragsn7
quelle
5

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

Im Grunde ist O (etwas) eine Obergrenze für die Anzahl der Anweisungen des Algorithmus (atomare). Daher ist O (logn) enger als O (n) und auch in Bezug auf die Algorithmusanalyse besser. Aber alle Algorithmen, die O (logn) sind, sind auch O (n), aber nicht rückwärts ...

Eyal
quelle
4
"O (n) ist enger als O (logn) und auch besser in Bezug auf die Algorithmusanalyse" ... eindeutig ist O (log (n)) besser als O (n). Ich denke du meintest den anderen Weg.
LuxuryMode
3

Formale Definition:

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

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

Zur weiteren Lektüre: http: //en.wikipedia.org/wiki/Big_O_notation.

barak1412
quelle