Jeg er ny inden for forståelse af datalogiske algoritmer. Jeg forstår processen med den binære søgning, men jeg har en lille misforståelse med dens effektivitet.
I en størrelse på $ s = 2 ^ n $ elementer ville det i gennemsnit tage $ n $ trin for at finde et bestemt element. At tage basis 2-logaritmen fra begge sider giver $ \ log_2 (s) = n $. Så ville det gennemsnitlige antal trin for den binære søgealgoritme ikke være $ \ log_2 (s) $?
Denne Wikipedia-artikel om den binære søgealgoritme siger, at den gennemsnitlige ydeevne er $ O (\ log n) $. Hvorfor er det sådan? Hvorfor er ikke dette tal $ \ log_2 (n) $?
Kommentarer
- Kopier på SO – Er Big O (logn) logbase e?
Svar
Når du ændrer logaritmebasen, adskiller det resulterende udtryk sig kun med en konstant faktor, som ved definition af Big-O notation , indebærer, at begge funktioner tilhører samme klasse med hensyn til deres asymptotiske opfø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 sig med en konstant $ C $, og derfor er begge sande: $$ \ 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 heltal $ a $ og $ b $ større end 1.
En anden interessant kendsgerning med logaritmiske funktioner er, at mens det for konstant $ k > 1 $, er $ n ^ k $ IKKE $ O (n) $, men $ \ log {n ^ k} $ er $ O (\ log {n}) $ siden $ \ log {n ^ k} = k \ log {n} $, som kun adskiller sig fra $ \ log {n} $ med kun konstant faktor $ k $.
Kommentarer
- Ikke kun for positive heltal: For alle reelle $ a, b > 1 $, f.eks $ e $.
- Jeg vil tilføje, at dette er grunden til, at med big-O notation er logaritmens base ofte ikke specificeret. Det betyder også, at der ikke er nogen forvirring om, hvilken base $ O (\ log n) $ bruger: det kan være en af de almindeligt anvendte baserede, da den ikke ' ikke gør en forskel.
Svar
Ud over fade2blacks svar (hvilket er helt korrekt), er det værd at bemærke at betegnelsen “$ \ log (n) $” er tvetydig. Basen er ikke faktisk specificeret, og standardbasen ændres baseret på kontekst. I ren matematik antages basen næsten altid at være $ e $ (medmindre andet er angivet), mens det i visse tekniske sammenhænge måske er 10. I datalogi , base 2 er så allestedsnærværende, at $ \ log $ ofte antages at være base 2. Den wikipedia-artikel siger aldrig noget om basen.
Men som det allerede er vist, i dette tilfælde betyder det ikke ” t ender med at have noget at gøre.
Kommentarer
- Det er sandsynligvis yderligere værd at bemærke, at mens " log (n) " kan være tvetydigt, at " O (log (n)) " er ikke fordi sidstnævnte kun har en betydning, uanset hvilken base du tænker på.