Warum ist das Protokoll im Big-O der binären Suche nicht Basis 2?

35

Ich bin neu im Verständnis von Algorithmen der Informatik. Ich verstehe den Prozess der binären Suche, habe aber ein leichtes Missverständnis mit der Effizienz.

Bei einer Größe von Elementen würde es im Durchschnitt Schritte dauern, um ein bestimmtes Element zu finden. Nimmt man den Logarithmus zur Basis 2 beider Seiten, so ergibt sich . Wäre die durchschnittliche Anzahl der Schritte für den binären Suchalgorithmus also nicht ? $s = 2^n$ $n$ $\log_2(s) = n$ $\log_2(s)$

Dieser Wikipedia-Artikel über den binären Suchalgorithmus besagt, dass die durchschnittliche Leistung . Warum ist das so? Warum ist diese Nummer nicht ? $O(\log n)$ $\log_2(n)$

algorithms runtime-analysis binary-search DrPepper
quelle

2

Auf SO duplizieren - Ist Big O (logn) log base e?

Dukeling

86

Wenn Sie die Basis des Logarithmus ändern, unterscheidet sich der resultierende Ausdruck nur durch einen konstanten Faktor, der per Definition der Big-O-Notation impliziert, dass beide Funktionen hinsichtlich ihres asymptotischen Verhaltens derselben Klasse angehören.

Zum Beispiel wobei .

{Log}_{10} n = \frac{{Log}_{2} n}{{Log}_{2} 10} = C {Log}_{2} n

$\log_{10}n = \frac{\log_{2}n}{\log_{2}10} = C \log_{2}{n}$

C = \frac{1}{\log_{2} 10}

$C = \frac{1}{\log_{2}10}$

So und unterscheidet sich durch eine Konstante , und somit beide erfüllt sind: Im allgemeinen ist für positive ganze Zahlen und größer als 1 ist . $\log_{10}n$ $\log_{2}n$ $C$

{Log}_{10} n ist O ({Log}_{2} n)

$\log_{10}n \text{ is } O(\log_{2}n)$

{Log}_{2} n ist O ({Log}_{10} n)

$\log_{2}n \text{ is } O(\log_{10}n)$

\log_{a} n

$\log_{a}{n}$

O (\log_{b} n)

$O(\log_{b}{n})$

a

$a$

b

$b$

Eine weitere interessante Tatsache mit logarithmischer Funktionen ist , dass , während für konstante , ist nicht , aber ist seit unterscheidet sich von nur durch den konstanten Faktor . $k>1$ $n^k$ $O(n)$ $\log{n^k}$ $O(\log{n})$ $\log{n^k} = k\log{n}$ $\log{n}$ $k$

fade2black
quelle

Nicht nur für positive ganze Zahlen: Für alle reellen , zB .

a, b > 1

$a,b > 1$

e

$e$

nbubis

2

Ich würde hinzufügen, dass dies der Grund ist, warum bei der Big-O-Notation die Basis des Logarithmus üblicherweise nicht spezifiziert wird. Dies bedeutet auch, dass es keine Verwirrung darüber gibt, welche Basis verwendet: Es kann eine der allgemein verwendeten sein, da es keinen Unterschied macht.

O (\log n)

$O(\log n)$

Svick

9

Zusätzlich zu der Antwort von fade2black (die völlig korrekt ist) ist anzumerken, dass die Notation " " mehrdeutig ist. Die Basis ist nicht wirklich angegeben und die Standardbasis ändert sich basierend auf dem Kontext. In der reinen Mathematik wird die Basis fast immer als (sofern nicht anders angegeben), während es in bestimmten technischen Zusammenhängen 10 sein können. In der Informatik ist die Basis 2 so allgegenwärtig, dass häufig als Basis 2 angenommen wird Artikel sagt nie etwas über die Basis. $\log(n)$ $e$ $\log$

Aber wie bereits gezeigt wurde, spielt es in diesem Fall keine Rolle.

MattPutnam
quelle

7

Dann ist es wahrscheinlich noch erwähnenswert, dass, während "log (n)" nicht eindeutig ist, "O (log (n))" nicht, weil letzteres nur eine Bedeutung hat, unabhängig davon, an welche Basis Sie denken.

Chris

Warum ist das Protokoll im Big-O der binären Suche nicht Basis 2?

Antworten: