Jeg er ny i forståelsen av datavitenskapelige algoritmer. Jeg forstår prosessen med binært søk, men jeg har en liten misforståelse med effektiviteten.
I størrelsen $ s = 2 ^ n $ elementer vil det i gjennomsnitt ta $ n $ trinn for å finne et bestemt element. Å ta base 2 logaritmen fra begge sider gir $ \ log_2 (s) = n $. Så ville ikke det gjennomsnittlige antall trinn for den binære søkealgoritmen være $ \ log_2 (s) $?
Denne Wikipedia-artikkelen på den binære søkealgoritmen sier at den gjennomsnittlige ytelsen er $ O (\ log n) $. Hvorfor er dette slik? Hvorfor er ikke dette tallet $ \ log_2 (n) $?
Kommentarer
- Dupliser på SO – Er Big O (logn) loggbase e?
Svar
Når du endrer logaritmegrunnlaget, skiller det resulterende uttrykket seg bare ut med en konstant faktor som ved definisjon av Big-O-notasjon , innebærer at begge funksjonene tilhører samme klasse med hensyn til deres asymptotiske oppførsel.
For eksempel $$ \ log_ {10} n = \ frac {\ log_ {2} n} {\ log_ {2} 10} = C \ log_ {2} {n} $$ hvor $ C = \ frac {1} {\ log_ {2} 10} $.
Så $ \ log_ {10} n $ og $ \ log_ {2} n $ adskiller seg med en konstant $ C $, og dermed er begge sanne: $$ \ log_ {10} n \ text {er} O (\ log_ {2} n) $$ $$ \ log_ {2} n \ text {er} O (\ log_ {10} n) $$ Generelt er $ \ log_ {a} {n} $ $ O (\ log_ {b} {n}) $ for positive heltall $ a $ og $ b $ større enn 1.
Et annet interessant faktum med logaritmiske funksjoner er at mens det for konstant $ k > 1 $, $ n ^ k $ IKKE er $ O (n) $, men $ \ logg {n ^ k} $ er $ O (\ log {n}) $ siden $ \ log {n ^ k} = k \ log {n} $ som skiller seg fra $ \ log {n} $ med bare konstant faktor $ k $.
Kommentarer
- Ikke bare for positive heltall: For alle reelle $ a, b > 1 $, f.eks $ e $.
- Jeg vil legge til at dette er grunnen til at med big-O-notasjon er logaritmens base ofte ikke spesifisert. Det betyr også at det ikke er noen forvirring om hvilken base $ O (\ log n) $ bruker: det kan være hvilken som helst basert basert, siden den ikke ' ikke gjør en forskjell.
Svar
I tillegg til fade2black «s svar (som er helt riktig), er det verdt å merke seg at betegnelsen «$ \ log (n) $» er tvetydig. Basen er ikke spesifisert, og standardbasen endres basert på kontekst. I ren matematikk antas basen nesten alltid å være $ e $ (med mindre spesifisert), mens det i visse tekniske sammenhenger kan være 10. I informatikk , base 2 er så allestedsnærværende at $ \ log $ ofte antas å være base 2. Den wikipedia-artikkelen sier aldri noe om basen.
Men, som allerede er vist, i dette tilfellet betyr det ikke » t ender opp med å si.
Kommentarer
- Det er sannsynligvis ytterligere verdt å merke seg at mens " logg (n) " kan være tvetydig at " O (log (n)) " er ikke fordi sistnevnte bare har én betydning, uansett hvilken base du tenker på.