Clasa VII/VIII lecția 9 - 18 nov 2014
Tema - rezolvări
Rezolvări aici [1]
Lecție
Analiză amortizată
Despre analiza amortizată. Citat din CLR: În analiza amortizată facem media timpului necesar pentru a executa o secvență operații, împărțindu-l la toate operațiile executate. Prin analiza amortizată putem să arătăm că costul mediu al unei operații este mic, atunci cînd împărțim la numărul de operații, cu toate că o singură operație din secvență ar putea fi "scumpă". Acest cost mediu per operație se mai numește și costul amortizat.
Să luăm cîteva exemple clasice de analiză amortizată
Incrementarea unui contor binar
Să presupunem că vrem să incrementăm un număr binar ale cărui cifre se află într-un vector. Numărul are n cifre, cea mai puțin semnificativă cifră (ultima din număr) fiind stocată prima în vector. Cum arată această incrementare?
i = 0;
while ( v[i] == 1 ) {
v[i] = 0;
i++;
}
v[i] = 1;Vom face această operatiune de 2n ori, pentru a trece prin toate valorile binare posibile. Întrebarea este care este numărul de operații per incrementare?
Un răspuns intuitiv ar fi că numărul maxim de operații la o incrementare oarecare este n, deci probabil că numărul mediu de operații este n/2, ceea ce ne duce la un timp O(n) per incrementare. Desigur că răspunsul este incorect. Să încercăm să-l calculăm mai exact. Vom calcula numărul total de operații pe parcursul tuturor incrementărilor și îl vom împărți la numărul de incrementări, 2n.
Să observăm că ultima cifră își va schimba valoarea la fiecare incrementare. Penultima numai din doi în doi. Antepenultima numai din patru în patru și așa mai departe. De unde rezultă că numărul total de cifre schimbate (egal cu numărul de operații total) este:
T(n) = 2n + 2n-1 + 2n-2 + ... + 21
Această sumă se calculează folosind formula sumei unei progresii geometrice, pe care o veți învăța abia în clasa a zecea. Pînă atunci să folosim un artificiu: să observăm că numărul T(n) este 111...110 în baza doi. El conține n cifre 1, iar ultima cifră este zero deoarece 20 lipsește din sumă. Ce se întîmplă dacă adunăm 2 la acest număr? Vom obține:
111...110(2) + 2(10) = 100...0(2) (1 cu n+1 zerouri)
Acest număr este 2n+1. Rezultă că:
T(n) + 2 = 2n+1
și deci
T(n) = 2n+1 - 2
Acesta este numărul total de operații, pentru toate incrementările. Împărțind la numărul de incrementări, care este 2n, obținem aproximativ două operațiuni per incrementare!
Iată cum, folosind analiza amortizată, am obținut un rezultat mult mai bun. În loc de O(n) am aflat că incrementarea unui contor binar este O(1)!
Permutări
Am studiat în lecțiile trecute algoritmi de generare a permutărilor. Întrebarea, ca și la exercițiul anterior, este cîte operații ne costă generarea unei permutări? Un prim răspuns, intuitiv, este că trebuie să așezăm n elemente în vector pentru fiecare permutare, deci probabil costul este O(n). Desigur că este greșit. Să încercăm să îl calculăm:
Să considerăm al doilea algoritm studiat, cel cu liste, deoarece calculul este mai ușor. În acest caz avem n niveluri de recursivitate, la fiecare nivel așezînd cifre, astfel:
- pe nivelul 1 vom așeza n cifre
- pentru fiecare cifră de pe nivelul 1, pe nivelul 2 vom așeza n-1 cifre
- pentru fiecare cifră de pe nivelul 2, pe nivelul 3 vom așeza n-2 cifre
- ...
- pentru fiecare cifră de pe nivelul n-1, pe nivelul n vom așeza o cifră
Vom avea în total n! așezări de cifre. Dar cît durează așezarea unei cifre? Mulțumită listelor, la fiecare nivel parcurgem strict lista de cifre nefolosite, ceea ce înseamnă că așezarea unei cifre este O(1). De aici rezultă că numărul total de operații este O(n!). Deoarece avem n! permutări rezultă că generarea unei permutări ne costă O(1)! Din nou un rezultat surprinzător. Desigur că acest rezultat nu ia în calcul afișarea permutărilor, ci doar generarea lor în vector.
Să considerăm acum primul agoritm, cel care folosește un vector de incluziune pentru a ști dacă o cifră a mai fost folosită, înainte de a o plasa pe poziția curentă. Calculul este similar, pînă ajungem la întrebarea cît ne costă să așezăm o cifră. Aici ne împotmolim, deoarece nu este clar. La primul nivel ne costă o operație per cifră, dar undeva la mijloc vom face tot n operații pentru a așeza doar n/2 cifre, deoarece parcurgem toate cifrele pentru a determina care sînt cele așezabile. Ce facem în acest caz? Să folosim din nou matematica. Să notăm cu T(k) costul pentru a așeza permutările de k (ultimele k poziții ale vectorului de permutări). În final ne va interesa T(n).
Ce operațiuni efectuăm pe nivelul k? În primul rînd o parcurgere a tuturor elementelor, pentru a vedea dacă le putem folosi, deci n operații. Apoi, pentru fiecare element așezat vom chema recursiv funcția, deci vom avea k apeluri la nivelul k-1:
T(k) = n + k T(k-1)
T(k) = n + k { n + (k-1)[n + (k-2)(n + ... + 3(n + 2 T(1)) ... )]}
T(k) = n + k n + k(k-1)n + k(k-1)(k-2)n + ... + k(k-1)(k-2)...3 n + k(k-1)(k-2)...3 2 T(1)
Dar T(1) este n, deoarece vom parcurge toate elementele și vom așeza unul singur. Așa încît:
T(k) = n + n(k + k(k-1) + k(k-1)(k-2) + ... + k(k-1)(k-2)...3 + k(k-1)(k-2)...3 2)
T(k) = n + n(k!/(k-1)! + k!/(k-2)! + k!/(k-3)! + ... + k!/2! + k!/1!)
T(k) = n + nk!(1/(k-1)! + 1/(k-2)! + 1/(k-3)! + ... + 1/2! + 1/1!)
Suma dintre paranteze va fi studiată în clasa a zecea. Se demonstrează că ea este mai mică decît o constantă e = 2.71828.... Drept pentru care:
T(k) = n + enk!
Numărul total de operații se obține pentru k = n:
T(n) = n(1 + e n!)
Atunci cînd împărțim acest număr la numărul de permutări generate, n!, obținem costul per permutare ca fiind aproximativ e n, adică O(n). De unde rezultă că acest algoritm este inferior celui cu liste.
Clădiri vizibile
Să presupunem că avem n clădiri înșirate pe o stradă, lipite una de alta. Se cunosc înălțimile fiecărei clădiri. Pornind de la stînga la dreapta și mergînd pe acoperișurile clădirilor ne întrebăm, pentru fiecare acoperiș, ce clădire vedem la acea înălțime uitîndu-ne înapoi, spre stînga.
Să traducem această problemă în limbaj informatic: dat un vector v de n numere naturale să se calculeze un vector w, unde w[i] este v[j], j cel mai mare indice j < i astfel încît v[j] > v[i]. Cu alte cuvinte pentru fiecare element din vectorul v vom căuta primul element înapoi mai mare decît el.
Soluție elegantă: parcurgem v și menținem un vector s de elemente interesante, în care așezăm la rînd elemente din v, astfel: la pasul i vom șterge din s ultimele elemente, cele mai mici decît v[i]. Ultimul element rămas în s este chiar w[i]. Apoi îl adăugăm pe v[i].
Exemplu:
Fie vectorul de înălțimi ''v = [9 3 4 5 1 2 2]''
Vectorul s = []
Pasul 1:
s este gol, nu există nici un element mai mare ca 9
w = [X]
Adăugăm v[1] la s:
s = [9]
Pasul 2:
Scoatem din s toate elementele mai mici sau egale cu v[2] (nici unul)
Ultimul element din s este w[2]
w = [X 9]
Adăugăm v[2] la s:
s = [9 3]
Pasul 3:
Scoatem din s toate elementele mai mici sau egale cu v[3]
s = [9]
Ultimul element din s este w[3]
w = [X 9 9]
Adăugăm v[3] la s:
s = [9 4]
Pasul 4:
Scoatem din s toate elementele mai mici sau egale cu v[4]
s = [9]
Ultimul element din s este w[4]
w = [X 9 9 9]
Adăugăm v[4] la s:
s = [9 5]
Pasul 5:
Scoatem din s toate elementele mai mici sau egale cu v[5] (nici unul)
s = [9 5]
Ultimul element din s este w[5]
w = [X 9 9 9 5]
Adăugăm v[5] la s:
s = [9 5 1]
Pasul 6:
Scoatem din s toate elementele mai mici sau egale cu v[6]
s = [9 5]
Ultimul element din s este w[6]
w = [X 9 9 9 5 5]
Adăugăm v[6] la s:
s = [9 5 2]
Pasul 7:
Scoatem din s toate elementele mai mici sau egale cu v[7]
s = [9 5]
Ultimul element din s este w[7]
w = [X 9 9 9 5 5 5]
Adăugăm v[7] la s:
s = [9 5 2]
Ce complexitate are acest algoritm? Ar părea că la fiecare pas putem scoate din vectorul s n elemente, caz în care algoritmul ar avea complexitate O(n2). Să încercăm să calculăm numărul total de operații.
Deși nu știm cîte operații vom face la fiecare pas, observăm următorul lucru: fiecare element din vectorul v este adăugat fix o dată și scos fix o dată. Atunci cînd eliminăm elemente din s scoatem acele elemente adăugate anterior. Drept pentru care numărul total de operații va fi 2n. Complexitatea amortizată a adăugării unui element în s este, de fapt O(1), iar întregul algoritm are complexitate O(n).
Problema bibliotecarului (coada implementată cu două stive)
Un bibliotecar primește cărți una cîte una și le returnează în aceeași ordine, la cerere. În spatele ghișeului el are doi subalterni. Bibliotecarul trebuie să dea cărțile primite unuia din subalterni. Poate de asemenea să ceară înapoi cărți de la subalterni. Fiecare subaltern ține o stivă de cărți. Atunci cînd bibliotecarul îi dă o carte subalternul o pune peste toate celelalte, în stiva sa. Atunci cînd bibliotecarul îi cere o carte o ia pe prima din stivă și i-o returnează. Voi trebuie să găsiți algoritmul de funcționare a bibliotecarului astfel încît după un număr mare de depuneri și cereri de cărți numărul total de operații (înmînări de cărți) să fie cît mai mic ca complexitate. Puteți presupune că vor fi 500000 de depuneri de cărți și 500000 de cereri, în orice ordine coerentă.
Rezolvarea directă, evidentă, este, surprinzător, și cea corectă: bibliotecarul va da toate cărțile primite subalternului 1. Cînd i se cere o carte, i-o va cere subalternului 2. Dacă subalternul 2 nu are cărți atunci el îi va cere, pe rînd cărți subalternului 1 și i le va da subalternului 2, pînă ce subalternul 1 nu mai are cărți. Apoi returnează cartea pe care i-o va da subalternul 2.
Funcționează corect acest algoritm? Desigur, urmăriți un exemplu și vă veți convinge. Dar pare foarte ineficient! Pentru o carte cerută este posibil ca bibliotecarul să facă n operații! Să facem același calcul ca și mai devreme: orice carte va fi depusă la primul subaltern, apoi scoasă și depusă la cel de-al doilea subaltern și apoi returnată. Drept pentru care numărul total de operații va fi 3n, iar costul amortizat al unei operații de depunere sau de scoatere va fi O(1).
Concluzii
Cu aceasta am încheiat exemplele de analiză amortizată. Remarcați ce au ele în comun: de cele mai multe ori în analiza amortizată avem o stivă. Un vector în care depunem la coadă elemente și din care ștergem tot de la coadă toate elementele mai mari ca elementul pe care îl adăugăm. Evident poate fi pe dos în cazul cînd ne interesează minime.
Oare ne folosește la ceva analiza amortizată, sau este doar ceva pur academic? Ei bine, ea se dă destul de frecvent la olimpiadă (este posibil să nu o fi remarcat pînă acum pentru că nu știați semnalmentele după care să vă uitați). În lecția următoare vom vedea probleme cu analiză amortizată date la olimpiada de informatică și alte concursuri.
Concurs
Pentru a ne dezmorți creierele vom da următorul concurs:
Concursul începe joi 20 noiembrie 2014 la ora 17:00 și ține trei ore jumate. Problemele de la concurs vă rămîn ca temă.
Temă
Clasa a 7-a
Clasa a 8-a
Rezolvări aici [2]
