Ist Big O(logn) log base e?

Question

Für Datenstrukturen vom Typ binärer Suchbaum wird die Big-O-Notation üblicherweise als O(logn) angegeben. Bedeutet ein klein geschriebenes "l" in log, dass es sich um die logarithmische Basis e (n) handelt, wie sie der natürliche Logarithmus beschreibt? Entschuldigen Sie die einfache Frage, aber ich hatte schon immer Schwierigkeiten, zwischen den verschiedenen impliziten Logarithmen zu unterscheiden.

Answer 1

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) heißt O(g(n)), wenn |f(n)| <= C * |g(n)| immer dann, wenn n > k ist, wobei C und k Konstanten sind.

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

HINWEIS: Das bedeutet, dass die Werte a und b einen beliebigen Wert größer als 1 haben können, z. B. a = 100 und b = 3

Nun erhalten wir folgendes: log base a von n heißt O(log base b von n), wenn |log base a von n| <= C * |log base b von n| immer dann, wenn n > k

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

Unsere Gleichung sieht nun wie folgt aus: |log Basis a von n| <= log Basis a von b * |log Basis b von n| immer wenn n > 0

Beachten Sie die rechte Seite, wir können die Gleichung manipulieren: = log base a von b * |log base b von n| = |log base b von n| * log base a von b = |log base a von b^(log base b von n)| = |log base a von n|

Unsere Gleichung sieht nun wie folgt aus: |log Basis a von n| <= |log Basis a von n| immer wenn n > 0

Die Gleichung ist immer wahr, unabhängig von den Werten n, b oder a, mit Ausnahme der 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 spielt, können wir sie einfach weglassen.

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

Einen Artikel darüber können Sie hier lesen: https://medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca

Answer 2

Technisch gesehen spielt die Basis keine Rolle, aber man kann sie sich im Allgemeinen als Basis-2 vorstellen.