Diferența dintre O(n) și O(log(n)) – care este mai bună și ce este mai exact O(log(n))? (Programare, Algoritm, Structuri De Date, Teoria Complexității, Mare O, Logaritm)

JAN a intrebat.

Acesta este primul meu curs de structuri de date și în fiecare curs / TA lecture , vorbim despre O(log(n)) . Aceasta este probabil o întrebare stupidă, dar aș aprecia dacă cineva îmi poate explica exact ce înseamnă exact !?

Comentarii

  • O posibilă repetare a stackoverflow.com/questions/487258/… -.  > Por s-a scufundat.
  • Uau, 1429 de aprecieri? M-aș mulțumi cu jumătate din asta pentru linkul meu de pe wikipedia. – user1311390
  • Mi-a dat informațiile de care aveam nevoie. –  > Por MadHatter.
6 răspunsuri
Amber

Înseamnă că lucrul în cauză (de obicei timpul de execuție) se scalează într-un mod care este în concordanță cu logaritmul dimensiunii sale de intrare.

Notația Big-O nu înseamnă că o exactă exactă, ci mai degrabă o ecuație limită. De exemplu, rezultatul următoarelor funcții este tot O(n):

f(x) = 3x
g(x) = 0.5x
m(x) = x + 5

Deoarece, pe măsură ce crește x, ieșirile lor cresc toate liniar – dacă există un raport 6:1 între f(n) și g(n), , va exista, de asemenea, un raport de aproximativ 6:1 între f(10*n) și g(10*n) și așa mai departe.


În ceea ce privește întrebarea dacă O(n) sau O(log n) este mai bun, luați în considerare: dacă n = 1000, , atunci log n = 3 (pentru log-bază-10). Ce ați prefera ca algoritmul dvs. să dureze mai mult pentru a fi executat: 1000 de secunde sau 3 secunde?

Comentarii

    29

  • Foarte bine explicat. De asemenea, aș dori să adaug câteva informații despre ce este chiar un logaritm pentru cei care nu știu. log n în informatică înseamnă, exponentul la care ar trebui să ridic numărul 2 pentru a obține n. Imaginați-vă deci, dacă n = 16. Exponentul nostru ar fi mult, mult mai mic decât valoarea reală a lui n. Ar fi 4. Sper că acest lucru are sens. În exemplul de mai sus al lui Amber, ea dă un exemplu similar, dar ridicând 10 la puterea 3. –  > Por Vocea Calului.
  • +1 – Cea mai clară explicație posibilă în cel mai mic număr de cuvinte. Mulțumesc. –  > Por techfoobar.
  • De asemenea, merită menționat faptul că Big-O se referă în general la orice limită, nu neapărat cea mai strânsă limită (adică cel mai mic g(x) astfel încât f(x) = O(g(x))). f(x), , g(x), , m(x) sunt, de asemenea, O(n^2). Dar, în contextul analizei performanței, dorim să se obțină cea mai tightest limită (adică cea mai mică funcție care delimitează curba de performanță a unui anumit algoritm) să ne dea o idee despre performanța unui algoritm în „cel mai rău caz”. –  > Por Minh Tran.
  • @Horse Voice În exemplul dvs. 2 ** 4, , în timp ce în codul lui Amber exemplul este 10 ** 3; cum se determină parametrii? –  > Por MadHatter.
  • Acest link prezintă un grafic cu toate complexitățile diferite: bigocheatsheet.com –  > Por silver_mx.
tayo

Pentru un răspuns scurt, O(log n) este mai bun decât O(n)

Acum, ce este mai exact O( log n) ?

În general, atunci când ne referim la notația O mare, log n se referă la logaritmul de bază-2, (la fel ca și ln reprezintă logaritmii de bază e). Acest logaritm de bază-2 este inversul unei funcții exponențiale. o funcție exponențială crește foarte rapid și putem deduce intuitiv că inversa sa va face exact opusul, adică crește foarte încet.

De exemplu

x = O(log n)

Putem reprezenta n sub forma ,

n= 2x

Și

210 = 1024 → lg(1024) = 10

220 = 1,048,576 → lg(1048576) = 20

230 = 1,073,741,824 → lg(1073741824) = 30

Creșteri mari în n conduc doar la o creștere foarte mică a log(n)

Pe de altă parte, pentru o complexitate de O(n), obținem o relație liniară

Un factor de log2n ar trebui să fie luat în considerare în locul unui factor de n oricând.

Pentru a consolida și mai mult acest lucru, am dat peste un exemplu în Algorithms Unlocked de Thomas Cormen

Luați în considerare 2 calculatoare : A și B

Ambele calculatoare au sarcina de a căuta o valoare într-un array Să presupunem că array-urile au 10 milioane de elemente de căutat

Calculatorul A- Acest calculator poate executa 1 miliard de instrucțiuni pe secundă și se așteaptă să îndeplinească sarcina de mai sus folosind un algoritm cu o complexitate de O(n). Putem aproxima timpul necesar acestui calculator pentru a îndeplini sarcina ca fiind

n/(instrucțiuni pe secundă) → 107/10^9 = 0,01 secunde

Calculatorul B- Acest calculator este mult mai lent și poate executa doar 10 milioane de instrucțiuni pe secundă. Se așteaptă ca calculatorul B să îndeplinească sarcina de mai sus folosind un algoritm cu o complexitate de O(log n). Putem aproxima timpul necesar acestui calculator pentru a îndeplini sarcina ca fiind

log(n) /(instrucțiuni pe secundă) → log(107)/107 = 0.000002325349

Cu această ilustrație, putem vedea că, deși calculatorul A este mult mai bun decât calculatorul B, datorită algoritmului utilizat de B, acesta îndeplinește sarcina mult mai repede.

Cred că acum ar trebui să fie foarte clar de ce O(log(n)) este mult mai rapid decât O(n)

anuragsn7

Pentru o intrare de dimensiune n, , un algoritm de O(n) va efectua pași proporționali cu n, , în timp ce un alt algoritm de O(log(n)) va efectua pași aproximativ log(n).

Este evident că log(n) este mai mic decât n deci algoritmul de complexitate O(log(n)) este mai bun. Deoarece va fi mult mai rapid.

user1311390

http://en.wikipedia.org/wiki/Big_oh

O(log n) este mai bun.

Eyal

O(logn) înseamnă că timpul maxim de execuție al algoritmului este proporțional cu logaritmul mărimii datelor de intrare.O(n) înseamnă că timpul maxim de execuție al algoritmului este proporțional cu mărimea datelor de intrare.

Practic, O(ceva) este o limită superioară a numărului de instrucțiuni (atomice) ale algoritmului. prin urmare, O(logn) este mai strâns decât O(n) și este, de asemenea, mai bun din punct de vedere al analizei algoritmilor. Dar toți algoritmii care sunt O(logn) sunt și O(n), dar nu invers…

Comentarii

  • „O(n) este mai strâmt decât O(logn) și este, de asemenea, mai bun din punct de vedere al analizei algoritmilor”… este clar că O(log(n)) este mai bun decât O(n). Cred că ai vrut să spui invers. –  > Por LuxuryMode.
barak1412

Definiție formală:

g(x) = O(f(x)) <=> există x0 și o constantă C care pentru orice x > x0, |g(x)| <= C|f(x)|.

Astfel, dacă găsiți un algoritm A pentru problema P a cărui complexitate este O(f(n)), puteți spune că numărul de pași pe care îi va face algoritmul dumneavoastră este mai mic sau egal asimptotic cu f(n), când n este de obicei dimensiunea intrării. (n poate fi orice)

Pentru lectură suplimentară: http://en.wikipedia.org/wiki/Big_O_notation.