Hvorfor er loggen i big-O for binær søgning ikke base 2?

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

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

Skriv et svar

Din e-mailadresse vil ikke blive publiceret. Krævede felter er markeret med *