wake-up-neo.com

Ist Big O(logn) log base e?

Bei Datenstrukturen mit binärem Suchbaum wird die Big O-Notation normalerweise als O (logn) angegeben. Bedeutet dies mit einem Kleinbuchstaben 'l' in log die log-Basis e (n), wie sie durch den natürlichen Logarithmus beschrieben wird? Entschuldigen Sie die einfache Frage, aber ich hatte immer Probleme, zwischen den verschiedenen impliziten Logarithmen zu unterscheiden.

84

Einmal in Big-O () ausgedrückt, sind beide korrekt. Während der Ableitung des O() Polynoms, im Fall von binär nur log2 ist richtig. Ich gehe davon aus, dass diese Unterscheidung die intuitive Inspiration für Ihre Frage war.

Meiner Meinung nach schreibe ich auch O (log2 N) ist für Ihr Beispiel besser, weil 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.

Also ist O (log N) äquivalent zu O (log2 N) aufgrund eines konstanten Faktors.

Wenn Sie jedoch leicht Protokoll setzen können2 N in Ihrer Antwort ist dies eher pädagogisch. Bei der Suche nach binären Bäumen ist dieses Protokoll korrekt2 N wird während der Ableitung der Laufzeit von big-O () eingeführt.

Bevor das Ergebnis als Big-O () -Notation ausgedrückt wird, ist der Unterschied sehr wichtig. Wenn Sie das Polynom ableiten, das über die Big-O-Notation kommuniziert werden soll, wäre es in diesem Beispiel falsch, einen anderen Logarithmus als log zu verwenden2 N, vor dem Anwenden der O () - Notation. 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.

66
Heath Hunnicutt

Die Big O-Notation wird von der logarithmischen Basis nicht beeinflusst, da alle Logarithmen in verschiedenen Basen bezogen auf einen konstanten Faktor , O(ln n) entspricht O(log n).

enter image description here

71
Cade Roux

Es spielt keine Rolle, um welche Basis es sich handelt, da die Big-O-Notation normalerweise nur mit der asymptotisch höchsten Ordnung von n geschrieben wird, 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.

8
Daniel Pryden

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))
4
cartonn

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

Die formale Definition lautet: * Eine Funktion f(n) soll O(g(n)) iff | f (n) | <= C * | g (n) | immer wenn 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

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

Nun erhalten wir Folgendes: Die logarithmische Basis a von n wird als O (logarithmische Basis b von n) bezeichnet, wenn | logarithmische Basis a von n | <= C * | log Basis b von n | wann immer n> k

Wählen Sie k = 0 und C = logarithmische Basis a von b.

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

Beachten Sie, dass wir auf der rechten Seite die Gleichung manipulieren können: = logarithmische Basis a von b * | logarithmische Basis b von n | = | log Basis b von n | * logarithmische Basis a von b = | logarithmische Basis a von b ^ (logarithmische Basis b von n) | = | log Basis a von n |

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

Die Gleichung ist immer wahr, unabhängig davon, welche Werte n, b oder a außer ihren Einschränkungen a, b> 1 und n> 0 sind. Die logarithmische Basis a von n ist also O (logarithmische Basis b von n), und da a, b keine Rolle spielt, 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 hier einen Artikel darüber lesen: https://medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca

1
tempmail

Technisch spielt die Basis keine Rolle, aber man kann sie allgemein als Basis 2 betrachten.

1
Tim Sylvester

Ja, wenn es um die Big-O-Notation geht, spielt die Basis keine Rolle. Wenn Sie jedoch mit einem echten Suchproblem konfrontiert sind, spielt dies eine Rolle.

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 - in einem binären Baum mit n Knoten der Baum Die 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

1
Paul