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=2nnlog2(s)=nlog2(s)

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


Odpowiedzi:


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 .

log10n=log2nlog210=Clog2n
C=1log210

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.log10nlog2nC

log10n is O(log2n)
log2n is O(log10n)
loganO(logbn)ab

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>1nkO(n)lognkO(logn)lognk=klognlognk


Nie tylko dla dodatnich liczb całkowitych: Dla wszystkich rzeczywistych , np .a,b>1e
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(logn)
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)elog

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


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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.