Jag är ny på att förstå datavetenskapliga algoritmer. Jag förstår processen med binär sökning, men jag har ett litet missförstånd med dess effektivitet.
I storleken $ s = 2 ^ n $ element skulle det i genomsnitt ta $ n $ steg för att hitta ett visst element. Att ta bas 2-logaritmen för båda sidor ger $ \ log_2 (s) = n $. Så skulle inte det genomsnittliga antalet steg för den binära sökalgoritmen vara $ \ log_2 (s) $?
Denna Wikipedia-artikel på den binära sökalgoritmen säger att den genomsnittliga prestandan är $ O (\ log n) $. Varför är det så? Varför är inte detta nummer $ \ log_2 (n) $?
Kommentarer
- Duplicera på SO – Är Big O (logn) logbas e?
Svar
När du ändrar logaritmens bas skiljer sig det resulterande uttrycket bara med en konstant faktor som, med definition av Big-O-notering , innebär att båda funktionerna tillhör samma klass med avseende på deras asymptotiska beteende.
Till exempel $$ \ log_ {10} n = \ frac {\ log_ {2} n} {\ log_ {2} 10} = C \ log_ {2} {n} $$ där $ C = \ frac {1} {\ log_ {2} 10} $.
Så $ \ log_ {10} n $ och $ \ log_ {2} n $ skiljer sig med konstant $ C $, och därför är båda sanna: $$ \ log_ {10} n \ text {är} O (\ log_ {2} n) $$ $$ \ log_ {2} n \ text {är} O (\ log_ {10} n) $$ Generellt är $ \ log_ {a} {n} $ $ O (\ log_ {b} {n}) $ för positiva heltal $ a $ och $ b $ större än 1.
Ett annat intressant faktum med logaritmiska funktioner är att medan för konstant $ k > 1 $, är $ n ^ k $ INTE $ O (n) $, men $ \ log {n ^ k} $ är $ O (\ log {n}) $ eftersom $ \ log {n ^ k} = k \ log {n} $ som skiljer sig från $ \ log {n} $ med endast konstant faktor $ k $.
Kommentarer
- Inte bara för positiva heltal: För alla riktiga $ a, b > 1 $, t.ex. $ e $.
- Jag vill tillägga att det här är anledningen till att logaritmens bas ofta inte anges med stor-O-notation. Det betyder också att det inte finns någon förvirring om vilken bas $ O (\ logn) $ använder: det kan vara vilken som helst baserad eftersom den inte ' gör skillnad.
Svar
Förutom fade2blacks svar (vilket är helt korrekt) är det värt att notera att beteckningen ”$ \ log (n) $” är tvetydig. Basen är faktiskt inte specificerad och standardbasen ändras baserat på kontext. I ren matematik antas basen nästan alltid vara $ e $ (om inte annat anges), medan det i vissa tekniska sammanhang kan vara 10. I datavetenskap , bas 2 är så allestädes närvarande att $ \ log $ ofta antas vara bas 2. Den Wikipedia-artikeln säger aldrig någonting om basen.
Men, som redan har visats, i det här fallet gör det inte ” t hamnar i saken.
Kommentarer
- Det är förmodligen ytterligare värt att notera att medan " log (n) " kan vara tvetydigt att " O (log (n)) " är inte för att den senare bara har en betydelse, oavsett vilken bas du tänker på.