The big O

Fiindcă în viața reală nu prea se mai întâmplă nimic intersant, am decis să scriu o serie de articole legate de calculatoare. Asta și deoarece temele abordate de mine până acum nu se prea potrivesc cu titlul blogului ”Just a coder”. Categoria nou creată se numește ”General knowledge for programmers”(parcă nu ar suna bine în română), și doresc să scriu o serie de post-uri, despre concepte des întâlnite în viața de coder, dar de care lumea se cam sperie. Posturile din această categorie nu se vor exhaustive, nici măcar pe departe. Tot ce doresc să prezint e un skimming prin conceptele abordate, după care cititorul interesat poate da un search pe Google pentru a se documenta corespunzător.

Post-ul de azi se referă la notația asimptotică, numită în engleză ”the big O notation”, și se adresează în special celor care au nedumeriri atunci când aud că un algoritm are complexitatea O(n^2), în timp ce altul are doar O(n \log n).

Complexitatea unui algoritm nu e altceva decât o măsură a numărului de operații pe care algoritmul îl face. Să zicem că avem un algoritm care găsește elementul maxim dintr-un vector oarecare(sau dacă vreți, listă).

Dacă cititorul s-a încumetat să ajungă până aici, probabil îi este familiar conceptul de vector, și știe că pentru a determina elementul maxim, trebuie să inițializeze o valoare cu primul element, apoi să o compare pe rând cu celelalte. Mai concret vorbind, dacă vrem să aflăm care este cel mai înalt elev din clasă, le cerem să intre pe rând pe ușă, punându-l pe primul drept etalon. De fiecare dată când intră cineva mai înalt decât etalonul, elevul mai înalt devine etalon. Evident, ultimul elev rămas drept etalon este cel mai înalt din clasă.

Până acum probabil ne-am dat deja seama că numărul de operații depinde de numărul de elemente din vector, sau de numărul de elevi din clasă, pe care în general îl notăm cu n. Mai exact, operațiile efectuate pentru determinarea maximului sunt comparații, în număr de n-1(deoarece pe primul element nu avem cu cine îl compara). Cu toate acestea, vom zice că algoritmul are complexitatea O(n), și nu O(n-1). În primul rând, acel 1 nu este relevant, pentru că oricum programul va face anumite operații de inițializare, pe care nu trebuie să le luăm în calcul, și în al doilea rând, faptul că îl luăm doar pe n, ne simplifică mult calculele, și ne ajută de multe ori să ”vedem” mai bine problema.

Așa cum multă lume își poate imagina, la apelul unei funcții care face ceva util, se fac anumite operații(punere parametri de apel și adresă de întoarcere pe stivă, inițializare variabile, etc. – dacă aceste operații nu sunt cunoscute, cititorul nu trebuie să își facă griji, deoarece sunt irelevante în acest post -). Vine atunci întrebarea ”de ce aceste operații nu se iau în considerare când măsurăm complexitatea?”. Răspunsul este că această complexitate nu trebuie să ne dea numărul exact de pași efectuați de algoritm, ci ne interesează mai mult cum se modifică acest număr de pași, dacă dimensiunea datelor problemei se modifică.

De exemplu, dacă avem un algoritm cu complexitate O(n), care rulează pentru n=1000, timp de 10 secunde, și îl mărim pe n cu 1, folosind regula de trei simplă, obținem un timp de execuție de 10.01 secunde, care practic nu diferă în mod vizibil de primul. Chiar dacă îl dublăm pe n, vom dubla doar timpul de execuție, la 20 de secunde, care rămâne tot în limitele rezonabile.

Să ne închipuim acum un algoritm de complexitate O(2^n), care rulează tot pentru n=1000 timp de 10 secunde. Dacă îl mărim pe n doar cu 1, cunoscând că 2^{n+1} = 2 \cdot 2^n, ne dăm seama că timpul de execuție se dublează. Dacă îl mărim pe n cu 10 doar, adică de la 1000 la 1010, timpul de execuție va crește de 2^{10} = 1024 ori, adica de la 10 secunde la aproape 3 ore. Timpul este încă rezonabil, dacă lucrăm la o problemă suficient de importantă, cât să merite să așteptăm 3 ore, dar ce ne facem de exemplu dacă ne trece prin cap să dublăm dimensiunea datelor problemei? Astfel de probleme se numesc probleme intractabile, și vom discuta mai multe despre ele într-un post viitor.

Am observat mai sus că pentru calcularea complexității unui algoritm, nu trebuie să ținem cont de constantele aditive care apar, deoarece acestea nu influențează semnificativ numărul de operații, atunci când dimensiunea datelor problemei se modifică. Vestea bună este că ”big O” ne scapă nu doar de constantele aditive, ci și de alte neplăceri.

Să luăm un alt exemplu, calcularea sumei elementelor de deasupra diagonalei principale, a unei matrici. Aceste elemente sunt în număr de 1 + 2 + \ldots (n-1) = \dfrac{n(n-1)}{2}, deci acesta este numărul de adunări pe care îl vom face. Dacă scriem acestă valoare sub formă polinomială, avem \dfrac{1}{2} n^2 - \dfrac{1}{2} n. Ca să trecem la notația asimptotică, trebuie să-l luăm doar pe n la puterea cea mai mare, fără a ”căra” după noi constantele multiplicative, aditive, sau puteri mai mici ale lui n, deoarece pentru valori suficient de mari ale acestuia, doar puterea cea mai mare din polinom va contribui semnificativ la creșterea numărului de operații. Vom obține complexitatea pentru această problemă O(n^2). Denumirea de notație asimptotică vine de la conceptul de asimptotă din matematică, dar n-o să intru în detalii aici.

Ar trebui ca deja să ne fi prins de șmecherie : pentru a calcula complexitatea unui algoritm, putem număra operațiile efectuate, fără a ține cont de detalii, iar acea valoare, deși oarecum aproximativă, ne va da o bună estimare a creșterii numărului de operații, la creșterea dimensiunii datelor problemei.

O ultimă chestiune, pentru a răspunde la o întrebare pe care unii cititori și-ar putea-o pune: ”Cum numărăm operațiile, de ajungem uneori la logaritmi, în formula complexității?”. Pentru a răspunde la această întrebare e necesar să cunoaștem conceptul de arbore binar. Chiar dacă o problemă nu specifică în mod explicit această structură, rezolvarea o poate sugera, prin împărțirea structurii de date în două jumătăți egale, și aplicarea algoritmului pe fiecare jumătate. Astfel, devine necesară parcurgerea unui astfel de arbore de la rădăcină, până la o frunză, ceea ce face ca numărul de operații să fie proporțional cu înălțimea acestuia. Un exercițiu pe care îl las pe seama cititorului care nu a adormit încă, este verificarea sau demonstrarea faptului că înălțimea unui arbore binar echilibrat este de ordinul \log_2 n, unde n este numărul de noduri al arborelui.

Anunțuri
Published in: on Februarie 5, 2010 at 01:54  Lasă un comentariu  

The URI to TrackBack this entry is: https://just1coder.wordpress.com/2010/02/05/the-big-o/trackback/

RSS feed for comments on this post.

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s

%d blogeri au apreciat asta: