Olen uusi tietotekniikan algoritmien ymmärtämisessä. Ymmärrän binäärihaun prosessin, mutta minulla on pieni väärinkäsitys sen tehokkuudesta.
Elementtien koon $ s = 2 ^ n $ ollessa keskimäärin $ n $ vaiheet tietyn elementin löytämiseksi. Kun molempien puolien perustason 2 logaritmi otetaan, saadaan $ \ log_2 (s) = n $. Eli binäärihakualgoritmin keskimääräinen vaiheiden määrä olisi $ \ log_2 (s) $?
Tämä Wikipedia-artikkeli päällä binaarihakualgoritmin mukaan keskimääräinen suorituskyky on $ O (\ log n) $. Miksi näin on? Miksi tätä numeroa $ \ log_2 (n) $ ei ole?
Kommentit
- Kopio SO: sta – Onko iso O (logn) lokikanta e?
vastaus
Kun muutat logaritmin perustaa, tuloksena oleva lauseke eroaa vain vakiotekijällä, joka Big-O-merkinnän määritelmä tarkoittaa, että molemmat toiminnot kuuluvat samaan luokkaan niiden asymptoottisen käyttäytymisen suhteen.
Esimerkiksi $$ \ log_ {10} n = \ frac {\ log_ {2} n} {\ log_ {2} 10} = C \ log_ {2} {n} $$ missä $ C = \ frac {1} {\ log_ {2} 10} $.
Joten $ \ log_ {10} n $ ja $ \ log_ {2} n $ eroavat toisistaan vakiolla $ C $, joten molemmat ovat totta: $$ \ log_ {10} n \ text {on} O (\ log_ {2} n) $$ $$ \ log_ {2} n \ text {on} O (\ log_ {10} n) $$ Yleensä $ \ log_ {a} {n} $ on $ O (\ log_ {b} {n}) $ positiivisille kokonaisluvuille $ a $ ja $ b $ suurempi kuin 1.
Toinen mielenkiintoinen tosiasia logaritmisilla funktioilla on se, että vaikka vakiona $ k > 1 $, $ n ^ k $ EI OLE $ O (n) $, mutta $ \ loki {n ^ k} $ on $ O (\ log {n}) $, koska $ \ log {n ^ k} = k \ log {n} $, joka eroaa $ \ log {n} $: sta vain vakiotekijällä $ k $.
Kommentit
- Ei vain positiivisille kokonaisluvuille: Kaikille todellisille $ a, b > 1 $, esim $ e $.
- Lisään, että tämä on syy, miksi iso-O-notaatiolla logaritmin perustaa ei yleensä määritellä. Se tarkoittaa myös, että ei ole hämmennystä siitä, mitä perustaa $ O (\ log n) $ käyttää: se voi olla mikä tahansa yleisesti käytetty pohja, koska se ei muuta '.
vastaus
fade2black-vastauksen (joka on täysin oikea) lisäksi on syytä huomata että merkintä ”$ \ log (n) $” on epäselvä. Perusta ei ole tosiasiallisesti määritelty, ja oletuspohja muuttuu kontekstin perusteella. Puhtaassa matematiikassa perustan oletetaan melkein aina olevan $ e $ (ellei toisin mainita), kun taas tietyissä teknisissä yhteyksissä se voi olla 10. Tietojenkäsittelytieteessä , base 2 on niin läsnä, että $ \ log $ oletetaan usein olevan base 2. Tuo wikipedia-artikkeli ei koskaan kerro mitään tukikohdasta.
Mutta kuten jo on osoitettu, tässä tapauksessa se ei ” Sillä ei ole merkitystä.
Kommentit
- Sitten on todennäköisesti syytä huomata, että vaikka " log (n) " saattaa olla epäselvä, että " O (log (n)) " ei johdu siitä, että jälkimmäisellä on vain yksi merkitys riippumatta siitä, mitä pohjaa saatat ajatella.