Nie mam doświadczenia w zrozumieniu algorytmów informatycznych. Rozumiem proces wyszukiwania binarnego, ale mam niewielkie nieporozumienie co do jego wydajności.
Przy rozmiarze $ s = 2 ^ n $ elementów zajęłoby to średnio $ n $ kroki, aby znaleźć określony element. Biorąc logarytm o podstawie 2 z obu stron, otrzymujemy $ \ log_2 (s) = n $. Czy zatem średnia liczba kroków algorytmu wyszukiwania binarnego nie wyniosłaby $ \ log_2 (s) $?
Ten artykuł w Wikipedii na algorytm wyszukiwania binarnego mówi, że średnia wydajność to $ O (\ log n) $. Dlaczego tak jest? Dlaczego nie ma tej liczby $ \ log_2 (n) $?
Komentarze
- Duplikuj na SO – Czy Big O (logn) log base e?
Odpowiedź
Po zmianie podstawy logarytmu wynikowe wyrażenie różni się tylko stałym współczynnikiem, który przez definicja notacji Big-O oznacza, że obie funkcje należą do tej samej klasy ze względu na ich asymptotyczne zachowanie.
Na przykład $$ \ log_ {10} n = \ frac {\ log_ {2} n} {\ log_ {2} 10} = C \ log_ {2} {n} $$ gdzie $ C = \ frac {1} {\ log_ {2} 10} $.
Więc $ \ log_ {10} n $ i $ \ log_ {2} n $ różni się stałą $ C $, a zatem obie są prawdziwe: $$ \ log_ {10} n \ text {is} O (\ log_ {2} n) $$ $$ \ log_ {2} n \ text {is} O (\ log_ {10} n) $$ Ogólnie $ \ log_ {a} {n} $ wynosi $ O (\ log_ {b} {n}) $ dla dodatnich liczb całkowitych $ a $ i $ b $ większych niż 1.
Innym interesującym faktem dotyczącym funkcji logarytmicznych jest to, że podczas gdy dla stałej $ k > 1 $, $ n ^ k $ NIE jest $ O (n) $, ale $ \ log {n ^ k} $ to $ O (\ log {n}) $ od $ \ log {n ^ k} = k \ log {n} $, które różni się od $ \ log {n} $ tylko stałym współczynnikiem $ k $.
Komentarze
- Nie tylko dla dodatnich liczb całkowitych: dla wszystkich rzeczywistych $ a, b > 1 $ np $ e $.
- Dodałbym, że jest to powód, dla którego w notacji duże-O podstawa logarytmu często nie jest określana. Oznacza to również, że nie ma niejasności co do tego, której podstawy $ O (\ log n) $ używa: może to być dowolna z powszechnie używanych baz, ponieważ nie ' nie robi różnicy.
Odpowiedź
Oprócz odpowiedzi fade2black (która jest całkowicie poprawna), warto zwrócić uwagę że zapis „$ \ log (n) $” jest niejednoznaczny. Baza nie jest faktycznie określona, a domyślna podstawa zmienia się w zależności od kontekstu. W czystej matematyce prawie zawsze zakłada się, że podstawa to $ e $ (chyba że określono), podczas gdy w pewnych kontekstach inżynierskich może to być 10. W informatyce , podstawa 2 jest tak wszechobecna, że często zakłada się, że $ \ log $ jest podstawą 2. Ten artykuł na Wikipedii nigdy nie mówi nic o bazie.
Ale, jak już pokazano, w tym przypadku tak nie jest. ” nie ma znaczenia.
Komentarze
- W takim razie prawdopodobnie warto zauważyć, że podczas " log (n) " może być niejednoznaczne, że " O (log (n)) " nie dlatego, że to drugie ma tylko jedno znaczenie, bez względu na to, o jakiej bazie myślisz.