Dlaczego log w dużym O wyszukiwania binarnego nie jest bazą 2?

35

Jestem nowy w zrozumieniu algorytmów informatycznych. Rozumiem proces wyszukiwania binarnego, ale mam niewielkie nieporozumienie z jego wydajnością.

W rozmiarze elementów znalezienie danego elementu wymagałoby średnio kroków. Biorąc podstawę 2 logarytmu obu stron daje . Czy więc średnia liczba kroków dla algorytmu wyszukiwania binarnego nie byłaby ? $s = 2^n$ $n$ $\log_2(s) = n$ $\log_2(s)$

Artykuł z Wikipedii na temat algorytmu wyszukiwania binarnego mówi, że średnia wydajność wynosi . Dlaczego tak jest? Dlaczego ten numer nie jest ? $O(\log n)$ $\log_2(n)$

algorithms runtime-analysis binary-search

— Dr Pepper
źródło

2

Duplikat na SO - Czy Big O (logn) log base e?

— Dukeling

86

Po zmianie podstawy logarytmu wynikowe wyrażenie różni się tylko stałym czynnikiem, który z definicji notacji Big-O oznacza, że obie funkcje należą do tej samej klasy pod względem ich asymptotycznego zachowania.

Na przykład gdzie .

\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}$

Więc i różni się stałą , a zatem oba są prawdziwe: Ogólnie to dla dodatnich liczb całkowitych i większych niż 1. $\log_{10}n$ $\log_{2}n$ $C$

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

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

\log_{2} n is 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$

Innym interesującym faktem związanym z funkcjami logarytmicznymi jest to, że chociaż dla stałej , to NIE , ale to od który różni się od tylko stałym współczynnikiem . $k>1$ $n^k$ $O(n)$ $\log{n^k}$ $O(\log{n})$ $\log{n^k} = k\log{n}$ $\log{n}$ $k$

— fade2black
źródło

Nie tylko dla dodatnich liczb całkowitych: Dla wszystkich rzeczywistych , np .

a, b > 1

$a,b > 1$

e

$e$

— nbubis

2

Dodałbym, że jest to powód, dla którego w notacji big-O podstawa logarytmu nie jest zwykle określona. Oznacza to również, że nie ma wątpliwości co do tego, której bazy używa : może to być dowolna z powszechnie używanych baz , ponieważ nie robi to różnicy.

O (\log n)

$O(\log n)$

— sick

9

Oprócz odpowiedzi fade2black (która jest całkowicie poprawna), warto zauważyć, że notacja „ ” jest niejednoznaczna. Baza nie jest właściwie określona, a domyślna baza zmienia się w zależności od kontekstu. W czystej matematyce prawie zawsze przyjmuje się, że podstawa to (o ile nie określono), podczas gdy w niektórych kontekstach inżynierskich może to być 10. W informatyce podstawa 2 jest tak wszechobecna, że często przyjmuje się jako podstawa 2. Ta wikipedia artykuł nigdy nie mówi nic o bazie. $\log(n)$ $e$ $\log$

Ale, jak już pokazano, w tym przypadku nie ma to znaczenia.

— MattPutnam
źródło

7

Prawdopodobnie warto dalej zauważyć, że chociaż „log (n)” może być dwuznaczne, że „O (log (n))” nie jest, ponieważ to ostatnie ma tylko jedno znaczenie, bez względu na to, o jakiej podstawie myślisz.

— Chris