Dies ist mein erster Kurs in Datenstrukturen und jeder Vortrag/TA Vortrag, wir sprechen über O(log(n)). Das ist wahrscheinlich eine dumme Frage, aber ich würde mich freuen, wenn mir jemand genau erklären kann, was es bedeutet!?Unterschied zwischen O (n) und O (log (n)) - was ist besser und was genau ist O (log (n))?
Es bedeutet, dass die betreffende Sache (normalerweise Laufzeit) in einer Weise skaliert, die mit dem Logarithmus ihrer Eingabegröße übereinstimmt.
Big-O notation keine genaue Gleichung bedeuten, sondern eine gebunden. Zum Beispiel ist der Ausgang der folgenden Funktionen alle O (n):
f(x) = 3x
g(x) = 0.5x
m(x) = x + 5
Denn wie man x zu erhöhen, deren Ausgänge alle Anstieg linear - wenn eine da ist 6: 1-Verhältnis zwischen f(n) und g(n), wird es auch etwa ein 6: 1-Verhältnis zwischen f(10*n) und g(10*n) und so weiter sein.
Als ob O(n) oder O(log n) ist besser, abwägen: Wenn n = 1000, dann log n = 3 (für log-base-10). Welchen Algorithmus würden Sie lieber einsetzen: 1000 Sekunden oder 3 Sekunden?
Schön erklärt. Außerdem möchte ich einige Informationen darüber hinzufügen, was ein Logarithmus für diejenigen ist, die nichts wissen. log n in Informatik bedeutet, der Exponent müsste ich die Zahl 2 erhöhen, um n zu bekommen. Stellen Sie sich vor, wenn n = 16. Unser Exponent wäre viel kleiner als der tatsächliche n-Wert. Es wäre 4. Hoffentlich macht das Sinn. In dem obigen Beispiel von Amber gibt sie ein ähnliches Beispiel, aber 10 erhöht die Potenz 3. –
+1 - Die klarste Erklärung in der kleinsten Anzahl von Wörtern möglich. Vielen Dank. – techfoobar
http://en.wikipedia.org/wiki/Big_oh
O (log n) ist besser.
O (logn) bedeutet, dass die Laufzeit des Algorithmus vom Logarithmus der Eingabegröße abhängig ist. O (n) bedeutet, dass die Laufzeit des Algorithmus von der Eingabegröße abhängig ist.
Grundsätzlich ist O (etwas) eine Obergrenze für die Anzahl der Anweisungen des Algorithmus (atomare). daher ist O (logn) enger als O (n) und ist auch hinsichtlich der Analyse der Algorithmen besser. Aber alle Algorithmen, die sind O (log n) sind ebenfalls O (n), aber nicht rückwärts ...
"O (n) ist enger als O (logn) und ist auch besser in Bezug auf die Algorithmenanalyse" ... klar O (log (n)) ist besser als O (n). Ich denke du meintest den anderen Weg. – LuxuryMode
Silly :) bearbeitet – Eyal
Für die Eingabe von Größe n, ein Algorithmus von O(n) wird führen Sie die Schritte perportional zu n, während ein anderer Algorithmus von O(log(n)) führt die Schritte grob log(n).
Offensichtlich log(n) ist kleiner als n daher Algorithmus der Komplexität O(log(n)) ist besser. Da wird es viel schneller sein.
formale Definition:
g (x) = O (f (x)) = <> bestehen X0 und Konstante C, die für jeden x> x0, | g (x) | < = C | f (x) |.
Also, wenn Sie Algorithmus A für Problem P finden, dass seine Komplexität O (f (n)), Sie sagen können, dass die Anzahl der Schritte Ihr Algorithmus tun wird, ist asymptotisch niedriger oder gleich f (n), wenn n normalerweise die Eingabegröße ist. (n kann alles sein)
Für weitere Informationen: http: //en.wikipedia.org/wiki/Big_O_notation.
Eine mögliche Wiederholung von http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o/487278#487278 – sank
Whoa, 1429 upvotes? Ich werde mit der Hälfte davon für meinen Wikipedia-Link glücklich sein. –