Ich bin neu im Verständnis von Informatik-Algorithmen. Ich verstehe den Prozess der binären Suche, habe aber ein leichtes Missverständnis hinsichtlich ihrer Effizienz.
Bei einer Größe von $ s = 2 ^ n $ Elementen würde es durchschnittlich $ n $ dauern Schritte, um ein bestimmtes Element zu finden. Wenn Sie den Logarithmus zur Basis 2 beider Seiten nehmen, erhalten Sie $ \ log_2 (s) = n $. Wäre also nicht die durchschnittliche Anzahl von Schritten für den binären Suchalgorithmus $ \ log_2 (s) $?
Dieser Wikipedia-Artikel auf Der binäre Suchalgorithmus gibt an, dass die durchschnittliche Leistung $ O (\ log n) $ beträgt. Warum ist das so? Warum ist diese Zahl nicht $ \ log_2 (n) $?
Kommentare
- Duplizieren auf SO – Ist Big O (logn) log base e?
Antwort
Wenn Sie die Basis des Logarithmus ändern, unterscheidet sich der resultierende Ausdruck nur durch einen konstanten Faktor, der durch Definition der Big-O-Notation impliziert, dass beide Funktionen hinsichtlich ihres asymptotischen Verhaltens zur selben Klasse gehören.
Zum Beispiel $$ \ log_ {10} n = \ frac {\ log_ {2} n} {\ log_ {2} 10} = C \ log_ {2} {n} $$ wobei $ C = \ frac {1} {\ log_ {2} 10} $.
$ \ log_ {10} n $ und $ \ log_ {2} n $ unterscheiden sich also um eine Konstante $ C $, und daher sind beide wahr: $$ \ log_ {10} n \ text {is} O. (\ log_ {2} n) $$ $$ \ log_ {2} n \ text {is} O (\ log_ {10} n) $$ Im Allgemeinen ist $ \ log_ {a} {n} $ $ O (\ log_ {b} {n}) $ für positive ganze Zahlen $ a $ und $ b $ größer als 1.
Eine weitere interessante Tatsache bei logarithmischen Funktionen ist, dass für die Konstante $ k > 1 $ $ n ^ k $ NICHT $ O (n) $ ist, sondern $ \ log {n ^ k} $ ist $ O (\ log {n}) $, da $ \ log {n ^ k} = k \ log {n} $, was sich von $ \ log {n} $ nur durch den konstanten Faktor $ unterscheidet k $.
Kommentare
- Nicht nur für positive ganze Zahlen: Für alle reellen $ a gilt b > 1 $, z $ e $.
- Ich würde hinzufügen, dass dies der Grund ist, warum bei der Big-O-Notation die Basis des Logarithmus normalerweise nicht angegeben wird. Dies bedeutet auch, dass keine Verwirrung darüber besteht, welche Basis $ O (\ log n) $ verwendet: Es kann sich um eine der häufig verwendeten Basen handeln, da ' keinen Unterschied macht.
Antwort
Zusätzlich zur Antwort von fade2black (die völlig korrekt ist) ist es erwähnenswert dass die Notation „$ \ log (n) $“ nicht eindeutig ist. Die Basis wird nicht tatsächlich angegeben, und die Standardbasis ändert sich basierend auf dem Kontext. In der reinen Mathematik wird fast immer angenommen, dass die Basis $ e $ ist (sofern nicht anders angegeben), während sie in bestimmten technischen Kontexten 10 sein kann. In der Informatik , Basis 2 ist so allgegenwärtig, dass $ \ log $ häufig als Basis 2 angenommen wird. Dieser Wikipedia-Artikel sagt nie etwas über die Basis aus.
Aber wie bereits gezeigt, ist dies in diesem Fall nicht der Fall. “ Am Ende spielt es keine Rolle.
Kommentare
- Es ist wahrscheinlich weiter erwähnenswert, dass " protokolliert (n) " ist möglicherweise nicht eindeutig, dass " O (log (n)) " liegt nicht daran, dass Letzteres nur eine Bedeutung hat, egal an welche Basis Sie denken.