Sunt nou înțelegerea algoritmilor de informatică. Înțeleg procesul căutării binare, dar am o ușoară neînțelegere cu privire la eficiența sa.
Într-o dimensiune de $ s = 2 ^ n $ elemente, ar fi nevoie, în medie, de $ n $ pași pentru a găsi un anumit element. Luând logaritmul de bază 2 al ambelor părți, se obține $ \ log_2 (s) = n $. Deci, numărul mediu de pași pentru algoritmul de căutare binară nu ar fi $ \ log_2 (s) $?
Acest articol Wikipedia pe algoritmul de căutare binară spune că performanța medie este de $ O (\ log n) $. De ce este așa? De ce nu este acest număr $ \ log_2 (n) $?
Comentarii
- Duplicat pe SO – Este Big O (logn) log log e?
Răspuns
Când schimbați baza logaritmului, expresia rezultată diferă doar de un factor constant care, prin definiția notării Big-O , implică faptul că ambele funcții aparțin aceleiași clase în ceea ce privește comportamentul lor asimptotic.
De exemplu $$ \ log_ {10} n = \ frac {\ log_ {2} n} {\ log_ {2} 10} = C \ log_ {2} {n} $$ unde $ C = \ frac {1} {\ log_ {2} 10} $.
Deci $ \ log_ {10} n $ și $ \ log_ {2} n $ diferă cu o constantă $ C $ și, prin urmare, ambele sunt adevărate: $$ \ log_ {10} n \ text {este} O (\ log_ {2} n) $$ $$ \ log_ {2} n \ text {este} O (\ log_ {10} n) $$ În general $ \ log_ {a} {n} $ este $ O (\ log_ {b} {n}) $ pentru numerele întregi pozitive $ a $ și $ b $ mai mari de 1.
Un alt fapt interesant cu funcțiile logaritmice este că, în timp ce pentru constant $ k > 1 $, $ n ^ k $ NU este $ O (n) $, ci $ \ log {n ^ k} $ este $ O (\ log {n}) $ din moment ce $ \ log {n ^ k} = k \ log {n} $ care diferă de $ \ log {n} $ numai cu factorul constant $ k $.
Comentarii
- Nu numai pentru numere întregi pozitive: Pentru toate $ a reale, b > 1 $, de ex $ e $.
- Aș adăuga că acesta este motivul pentru care, cu notația big-O, baza logaritmului nu este de obicei specificată. De asemenea, înseamnă că nu există confuzie cu privire la baza pe care o folosește $ O (\ log n) $: poate fi oricare dintre cele utilizate în mod obișnuit, deoarece nu face ' o diferență.
Răspuns
Pe lângă răspunsul lui fade2black (care este complet corect), merită remarcat că notația „$ \ log (n) $” este ambiguă. Baza nu este de fapt specificată, iar baza implicită se modifică în funcție de context. În matematica pură, baza este aproape întotdeauna presupusă a fi $ e $ (dacă nu este specificat), în timp ce în anumite contexte de inginerie ar putea fi 10. În informatică , baza 2 este atât de omniprezentă încât $ \ log $ este adesea presupus a fi baza 2. Acest articol din Wikipedia nu spune niciodată nimic despre bază.
Dar, așa cum s-a arătat deja, în acest caz nu ” Nu sfârșesc să conteze.
Comentarii
- Probabil că merită menționat și faptul că, în timp ce jurnalul " (n) " ar putea fi ambiguu că " O (log (n)) " nu se datorează faptului că acesta din urmă are un singur sens, indiferent de baza la care te-ai putea gândi.