Ist Big O (logn) log base e?

96

Für Datenstrukturen vom Typ eines binären Suchbaums wird die Big O-Notation normalerweise als O (logn) angegeben. Bedeutet dies mit einem Kleinbuchstaben 'l' im Protokoll die Protokollbasis e (n), wie sie durch den natürlichen Logarithmus beschrieben wird? Entschuldigung für die einfache Frage, aber ich hatte immer Probleme, zwischen den verschiedenen impliziten Logarithmen zu unterscheiden.

math binary-tree complexity-theory big-o BuckFilledPlatypus
quelle

58

Wie andere eindringlich betont haben, spielt es keine Rolle. Alle Logarithmen unterscheiden sich durch eine Konstante, die nur von den beteiligten Basen abhängt. Da diese Faktoren Konstanten sind, sind sie für die asymptotische Analyse irrelevant. Zweitens hängt die Bestimmung der implizierten Basis vom Kontext ab. Als grobe Faustregel gilt Folgendes: 1. Wenn ein Mathematiker schreibt log n, meint er den natürlichen Logarithmus. 2. Wenn ein Informatiker schreibt log n, meint er Basis zwei. 3. Wenn ein Ingenieur schreibt log n, meint er Basis zehn. Diese sind normalerweise wahr.

Jason

4

@ Jason, eine andere Konvention (innerhalb der Mathematik) ist, dass ln n den natürlichen Logarithmus bedeutet und log n die Basis zehn ist. Think ln steht für den französischen 'Logarithmus naturelle'.

Internet-Mann

2

Die Basis des Logarithmus ist die Anzahl der Kinder, die jeder Knoten hat. Wenn es sich um einen Binärbaum handelt, handelt es sich um ein Basis-2-Protokoll.

Paul

3

Ich schätze deine Antwort, Jason, und hier ist etwas zum Nachdenken. Als ich untersucht habe, auf welcher Basis sich das Protokoll befindet (ich habe 2 angenommen), habe ich die gleiche Antwort gesehen: Es spielt keine Rolle, weil Sie die Konstante log_10 (2) entfernen können. Mein Problem dabei ist, dass zum Beispiel: 5 log_10 (5) <5, während 5 log_2 (5)> 5. Ich habe diese schnell in meine Berechnung eingegeben, um zu verstehen, wo O (n logn) eine bessere oder schlechtere Laufzeit als O hat (n). Abhängig von der Basis spielt es eine Rolle. Daher denke ich wirklich, dass die RICHTIGE Antwort darauf sein sollte, dass Protokoll in den meisten Informatikanwendungen kontextuell Basis 2 bedeutet.

Doug Mead

@ Jason, ich würde sagen, dass es einfacher ist, ln zu verwenden (Interpretation des Mathematikers);). Die beiden anderen Beispiele sind sinnvoll.

Belford

76

Einmal in der Notation big-O () ausgedrückt, sind beide korrekt. Während der Ableitung des O () - Polynoms ist im Fall der binären Suche jedoch nur log ₂ korrekt. Ich gehe davon aus, dass diese Unterscheidung die intuitive Inspiration für Ihre Frage war.

Meiner Meinung nach ist das Schreiben von O (log ₂ N) für Ihr Beispiel besser, da es die Ableitung der Laufzeit des Algorithmus besser kommuniziert.

In der Big-O () - Notation werden konstante Faktoren entfernt. Bei der Umrechnung von einer Logarithmusbasis in eine andere wird mit einem konstanten Faktor multipliziert.

O (log N) entspricht also aufgrund eines konstanten Faktors O (log ₂ N).

Wenn Sie jedoch in Ihrer Antwort leicht log ₂ N setzen können, ist dies pädagogischer. Bei der Suche nach binären Bäumen haben Sie Recht, dass log ₂ N während der Ableitung der Laufzeit von big-O () eingeführt wird.

Bevor Sie das Ergebnis als big-O () -Notation ausdrücken, ist der Unterschied sehr wichtig. Wenn das zu kommunizierende Polynom über die Big-O-Notation abgeleitet wird, ist es für dieses Beispiel falsch , vor dem Anwenden der O () - Notation einen anderen Logarithmus als log ₂ N zu verwenden. Sobald das Polynom verwendet wird, um eine Worst-Case-Laufzeit über die Big-O () -Notation zu kommunizieren, spielt es keine Rolle, welcher Logarithmus verwendet wird.

Heath Hunnicutt
quelle

4

Aber es ist sehr einfach zu zeigen, dass log_2 nes sich Θ(log_a n)um eine Basis handelt a, daher bin ich mir nicht sicher, ob die Verwendung von Basis 2 "korrekter" ist.

bcat

1

Kinopkio und bcat, danke, dass Sie dazu beigetragen haben, dass es nützlich wird. Es war zunächst nicht sehr gut geschrieben. :)

Heath Hunnicutt

2

Nun, ich habe Klarheit hinzugefügt, aber ich bin sicher verletzt, dass Sie denken, meine Antwort könnte die Leute verwirren. Tatsächlich berücksichtigten die meisten Antworten hier nicht die Intuition des OP und versuchten, ihm viel beizubringen. Ich bin nicht so begeistert von der Konkurrenz, ich bin irgendwie traurig über die niedrige Bar für Pädagogik.

Heath Hunnicutt

11

"Während der Ableitung des O () - Polynoms ist im Fall der binären Suche nur log2 korrekt." -1 für schlechte Mathematik. Die Definition von x (n) ~ O (f (n)) besagt, dass es eine Konstante c gibt, so dass c * (f (n)) <x (n) für alle n> n_0 ist. Somit ist der konstante Koeffizient während der Analyse völlig irrelevant.

Rlbond

3

Da log2 (x) gleich log10 (x) / log10 (2) ist, können Sie es so oder so ableiten. Das Protokoll ist zu keinem Zeitpunkt streng Basis 2.

Rlbond

80

O - Notation nicht durch logarithmische Basis beeinträchtigt wird, weil alle Logarithmen in verschiedenen Basen sind mit einem konstanten Faktor bezogen , O(ln n)entspricht O(log n).

Cade Roux
quelle

2

Die Grafiken sind ordentlich, aber denken Sie an die Ableitung des O () - Polynoms ... bevor O () angewendet wird, ist nur log-base-2 für die binäre Suche korrekt.

Heath Hunnicutt

1

@Heath Hunnicutt: Nein log_2 xunterscheidet sich log_b xvon einem konstanten Faktor c(b)für jede Basis bunabhängig von x.

Jason

4

Aber warum redest du darüber, wenn es keinen Bezug zur Frage hat und nur zur Verwirrung dient?

Hobbs

4

hobbs: Weil diese Tatsache der Grund ist, warum das OP inspiriert wurde, sich zu erkundigen. Ich versuche, seine Ideen mit der Antwort zu verbinden, damit er versteht, warum er seine Intuition hatte, warum sie nicht für O () gilt, aber das, was er hier lernt, nicht auf den Ableitungsteil der Analyse überträgt. Die knappen Antworten, die die Grundursache des Missverständnisses nicht ansprechen, können zu weiteren Missverständnissen führen. Es ist schlechte Pädagogik.

Heath Hunnicutt

4

@Heath Hunnicutt: Wenn Sie asymptotische Analysen durchführen, spielt das keine Rolle. Dass Sie bis zur letzten Minute warten, um ein paar große O's zu werfen, ändert nichts an der Tatsache, dass ich alle meine Logarithmen durch eine dumme Konstante multiplizieren und dividieren und die Basis bei allen Schritten ändern kann. Das heißt, wenn ich eine Analyse habe, die dies beinhaltet log_2 n, kann ich einfach log_2 nüberall hineingehen und ersetzen log_pi 2 * log_2 n / log_pi 2und dann einfach eine Analyse erhalten, die log_pi 2 * log_pi nüberall vorhanden ist. Jetzt ist meine Analyse in Bezug auf log_pi n.

Jason

9

Es spielt keine Rolle, um welche Basis es sich handelt, da die Big-O-Notation normalerweise nur mit der asymptotisch höchsten Ordnung von geschrieben wird n, sodass konstante Koeffizienten wegfallen. Da eine andere Logarithmusbasis einem konstanten Koeffizienten entspricht, ist sie überflüssig.

Das heißt, ich würde wahrscheinlich Log Base 2 annehmen.

Daniel Pryden
quelle

@ Kinopiko: Was genau ist daran falsch? Genauer gesagt, wie unterscheidet sich meine Antwort sachlich von Ihrer und anderen hier?

Daniel Pryden

Ah, vielleicht mein Fehler bei der Verwendung von "Koeffizient". Ich werde bearbeiten, um zu klären.

Daniel Pryden

Das war mein Hauptproblem bei Ihrer Antwort. Es ist auch ein bisschen unklar, was Sie unter "sie werden noch eine gewisse Wirkung haben" verstehen. Einige Auswirkungen auf was?

bcat

1

Ihre Antwort beschreibt die Koeffizienten höchster Ordnung. Was Sie gesagt haben, ist soweit richtig, aber das ist nicht der Grund, warum die Logarithmusbasis irrelevant ist. Der Grund ist, dass der Unterschied zwischen verschiedenen Basislogarithmen eine Konstante ist, die vom O () absorbiert wird.

1

@ Kinopiko: OK. Ich denke, wir sagen dasselbe. Ich würde O (100) = O (1) sagen, weil O (100) = O (100 * 1) = O (C * 1) = O (1). Was ich damit meinte, dass ständige Ausdrücke überflüssig sind. Das heißt, die Reihenfolge von jeder Konstante ist 1.

Daniel Pryden

7

Beide sind richtig. Denk darüber nach

log2(n)=log(n)/log(2)=O(log(n))
log10(n)=log(n)/log(10)=O(log(n))
logE(n)=log(n)/log(E)=O(log(n))

cartonn
quelle

2

Ja, wenn es um Big-O-Notation geht, spielt die Basis keine Rolle. Bei einem echten Suchproblem ist dies jedoch rechnerisch von Bedeutung.

Wenn Sie eine Intuition über Baumstrukturen entwickeln, ist es hilfreich zu verstehen, dass ein binärer Suchbaum in O (n log n) Zeit durchsucht werden kann, da dies die Höhe des Baums ist, dh in einem binären Baum mit n Knoten der Baum Tiefe ist O (n log n) (Basis 2). Wenn jeder Knoten drei untergeordnete Knoten hat, kann der Baum weiterhin in O (n log n) -Zeit durchsucht werden, jedoch mit einem Logarithmus zur Basis 3. Rechnerisch kann die Anzahl der Kinder, die jeder Knoten hat, einen großen Einfluss auf die Leistung haben (siehe zum Beispiel: Linktext ).

Genießen!

Paul

Paul
quelle

du wolltest sagen, dass die Höhe eines Binärbaums log n ist, nicht n log n, oder?

Zelle

1

Technisch spielt die Basis keine Rolle, aber Sie können sie allgemein als Basis 2 betrachten.

Tim Sylvester
quelle

1

Zuerst müssen Sie verstehen, was es bedeutet, dass eine Funktion f (n) O (g (n)) ist.

Die formale Definition lautet: * Eine Funktion f (n) heißt O (g (n)) iff | f (n) | <= C * | g (n) | wann immer n> k, wobei C und k Konstanten sind. *

also sei f (n) = logarithmische Basis a von n, wobei a> 1 und g (n) = logarithmische Basis b von n, wobei b> 1 ist

HINWEIS: Dies bedeutet, dass die Werte a und b beliebig größer als 1 sein können, z. B. a = 100 und b = 3

Jetzt erhalten wir Folgendes: log base a von n heißt O (log base b von n) iff | log base a von n | <= C * | log base b von n | wann immer n> k

Wählen Sie k = 0 und C = log base a von b.

Nun sieht unsere Gleichung wie folgt aus: | log base a von n | <= log base a von b * | log base b von n | wann immer n> 0

Nun sieht unsere Gleichung wie folgt aus: | log base a von n | <= | log base a von n | wann immer n> 0

Die Gleichung ist immer wahr, unabhängig von den Werten n, b oder a, abgesehen von ihren Einschränkungen a, b> 1 und n> 0. Die logarithmische Basis a von n ist also O (logarithmische Basis b von n), und da a, b keine Rolle spielen, können wir sie einfach weglassen.

Sie können ein YouTube-Video hier sehen: https://www.youtube.com/watch?v=MY-VCrQCaVw

Sie können einen Artikel dazu hier lesen: https://medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca

tempmail
quelle

Ist Big O (logn) log base e?

Antworten: