Clasele 9-10 lecția 12 - 3 dec 2014

Analiză amortizată

Uneori avem de calculat complexitatea unui algoritm care face, pe o structură de date, diverse operații cu diverse costuri. Metoda naivă obține răspunsul înmulțind numărul de operații cu costul celei mai scumpe operații. Dar această abordare este pesimistă. Adesea putem demonstra că, în medie, costul unei operații este cu mult mai mic.

Exemplu: stiva ordonată

Recapitulăm conceptul de stivă ordonată, prezentat în lecția despre algoritmi pe vectori și matrice.

Să considerăm problema celui mai apropiat vecin: Dându-se un vector V, să se calculeze un alt vector W unde W(i) este cel mai mare indice j < i pentru care V[j] < V[i]. Când nu există un astfel de j, atunci V[i] = 0.

Codul care rezolvă problema este:

  v[0] = INFINITY; // santinelă
  s.push(0);
  for (i = 1; i <= n; i++) {
    while (v[i] < v[s.top()]) {
      s.pop();
    }
    w[i] = s.top();
    s.push(i);
  }

La prima vedere, avem două bucle imbricate, deci complexitatea algoritmului este $O(n^{2})$. Totuși, după cum am arătat, numărul total de apeluri al lui s.pop() este $O(n)$. Procedeul prin care demonstrăm aceasta se numește analiză amortizată.

Există trei metode de analiză amortizată. Pe cea de-a treia o menționăm superficial.

Analiză agregată

Această metodă calculează pur și simplu costul total al celor n operații (și, eventual, împarte la n pentru a afla costul mediu al unei operații).

Numărul total de apeluri al lui s.pop() nu îl poate depăși pe cel al lui s.push. Dar acesta din urmă este exact n, căci apelăm s.push() exact o dată pentru fiecare iterație din for. Așadar, complexitatea algoritmului este $O(n)$.

Metoda contabilului

Atunci când intuim că numărul de operații scumpe este mic, putem „cere credit suplimentar” pentru operațiile ieftine, încercând ca prin aceasta să plătim operațiile mai scumpe. Această metodă ne duce cu gândul la un contabil (sau, mai degrabă, un magaziner) care nu dorește să dea nimic pe datorie. Imediat ce îi prezentăm un element pentru inserarea în structură, contabilul ne cere să plătim și transformările viitoare pe care le poate suferi elementul.

Echivalent, metoda urmărește evoluția unui element prin structura de date, pe toată durata vieții lui.

Pentru stiva ordonată, să ne închipuim că, la inserarea unui element în stivă, contabilul ne cere doi lei. Primul este costul inserării propriu-zise în stivă. Al doilea leu stă alături de element pe stivă, urmând să-l cheltuim când scoatem elementul din stivă. Astfel, operațiile ieftine plătesc în avans pentru operațiile scumpe, cum ar fi cele în care multe elemente sunt scoase simultan de pe stivă.

Metoda potențialului

Să notăm cu Φ(i) numărul de elemente din stivă după examinarea primelor i elemente din V. Cum variază Φ pe măsură ce avansăm prin vector?

• Când V[i] ≤ V[i-1], nu scoatem nimic din stivă, iar Φ(i) = Φ(i - 1) + 1
• Când elementul V[i] cauzează eliminarea multor elemente din stivă, Φ(i) poate fi mult mai mic decât Φ(i-1).

Observăm, deci, că operațiile relativ ușoare sunt însoțite de o creștere ușoară a lui Φ, iar operațiile scumpe sunt însoțite de o cădere, posibil mare, a lui Φ. Să vedem la ce ne ajută aceasta.

Fie $C_{R}(i)$ costul real al iterației i (un push și zero sau mai multe pop-uri). De asemenea, fie $C_{A}(i)$ costul amortizat al iterației i, definit ca:

$C_{A}(i)=C_{R}(i)+\Phi (i)-\Phi (i-1)$

Cu aceste definiții, care este costul amortizat pentru operația i? Fie k numărul de elemente scoase de pe stivă la acest pas. Fiecare scoatere creează un efort de o unitate, dar acea unitate este anulată de căderea lui Φ, tot cu o unitate. La final, punem pe stivă elementul i, cu efort 1, ceea ce crește și potențialul tot cu 1. Așadar,

$C_{A}(i)=k-k+1+1=2$ pentru i = 1, 2, ..., n.

Să însumăm aceste relații pentru operațiile 1, 2, ..., n. Observăm că valorile Φ formează o sumă telescopică, iar termenii se anulează:

$\sum _{i=1}^{n}C_{A}(i)=\sum _{i=1}^{n}C_{R}(i)+\Phi (n)-\Phi (0)$

Știm că Φ(0) = 1, iar Φ(n) ≤ 1, așadar:

$2n>=\sum _{i=1}^{n}C_{R}(i)$

Așadar, am demonstrat că suma costurilor reale nu depășește 2n!

În general, metoda potențialului funcționează astfel:

• Alegem o funcție Φ cu valori pozitive. Această funcție se numește potențial și asociază fiecărei stări a structurii de date un număr nenegativ. Fie C_R(i) costul real al operației cu numărul i. Atunci definim costul amortizat ca

$C_{A}(i)=C_{R}(i)+\Phi (i)-\Phi (i-1)$

• așadar, suma costurilor amortizate este o limită superioară pentru suma costurilor reale, cu condiția ca potențialul final să fie mai mare decât cel inițial
• cum alegem funcția-potențial? Aici este arta.
• empiric, dorim ca potențialul să „echilibreze” costurile amortizate, atunci când costurile reale variază asimptotic
• vrem ca operațiile ieftine să fie însoțite de o creștere (mică) de potențial, iar operațiile scumpe să fie însoțite de o cădere mare de potențial
• intuitiv, potențialul mare al structurii indică posibilitatea ca următoarea operație să fie scumpă, iar potențialul mic indică probabilitatea ca următoarele câteva operații să fie ieftine

Alte exemple, toate analizate prin cele trei metode

Incrementarea unui contor binar

Problema: Un vector de k elemente stochează valori de 0 sau 1, reprezentând un număr binar. Inițial, toate elementele sunt 0. Incrementăm contorul de n ori. Care este costul mediu per incrementare?

Analiză agregată: Există operații de cost k, dar acestea sunt puține (o fracție de 1 / 2^k din numărul total). 1/2 dintre incrementări se fac cu cost real 1, 1/4 se fac cu cost real 2 etc. Suma acestor costuri este o sumă de puteri a lui 2 care nu depășește 2 n.

Metoda contabilității: Fiecare operație de incrementare schimbă toți biții de 1 la sfârșitul numărului în 0 și (opțional) ultimul bit de 0 în 1. Când modificăm un bit din 0 în 1, plătim $2, din care $1 este consumat, iar $1 este depozitat alături de bit. Când bitul trece din nou pe 0, este consumat și acest dolar. Deoarece la fiecare incrementare schimbăm cel mult un bit din 0 în 1, vom plăti cel mult $2.

Metoda potențialului: Φ(i) este numărul de biți 1 din contor după a i-a operație

Extensii: Dar dacă costul incrementării celui de-al i-lea bit este 2ⁱ? Dar dacă permitem atât incrementare, cât și decrementare?

Simularea unei cozi folosind două stive

Problema: Se cere să implementăm o coadă, dar ni se cere să folosim numai două stive ca structură internă.

Soluție: Fie S și T cele două stive. Pentru a adăuga elemente în coadă, le adăugăm la S. Pentru a extrage elemente din coadă, le extragem din T; dacă T este goală, mutăm toate elementele din S în T.

Analiză agregată: Suma costurilor mutărilor din S în T este O(n), căci fiecare element este mutat o singură dată (nu se mai întoarce în S).

Metoda contabilității: Inserarea costă $3, din care unul este costul imediat, iar $2 rămân lângă element. Mutarea din S în T costă $1. Extragerea din T costă ultimul $1.

Metoda potențialului: Φ(i) este numărul de elemente din stiva S după a i-a operație

Stivă cu backup (Cormen)

Problema: O stivă poate stoca maxim k elemente. După fiecare k operații, facem o copie a întregii stive, pentru backup. Să se arate că costul amortizat al operațiilor pe stivă este tot O(1).

Analiză amortizată: Costul a k operații este k pentru operațiile propriu-zise (push și pop) și k pentru copierea stivei la final. Deci costul amortizat este constant, 2.

Metoda contabilității: La fiecare operație de push sau pop cerem $2: unul pentru operația în sine, iar celălalt este depozitat, în ordine, pe câte o căsuță din stivă. După k operații vom avea $k acumulați, suficienți ca să plătim pentru operația de backup.

Metoda potențialului: Φ(i) este numărul de operații simple trecute de la ultima operație de backup. Atunci operația scumpă (backup) este însoțită de o cădere de potențial de la k la 0, iar costul amortizat este 2 pentru toate operațiile.

Teme de gândire

• Simularea unui deque folosind trei stive: Să se implementeze un deque, adică o coadă unde putem insera și șterge la oricare din capete, folosind trei stive ca structură internă.
• Stivă dinamică, numai push: O stivă poate numai să crească (se fac doar operații push). Ea este dimensionată pentru un singur element. Când stiva se umple, ea își dublează capacitatea pentru a putea găzdui noi elemente. Calculați costul amortizat al n operații push.
• Stivă dinamică: Generalizați problema anterioară pentru a admite și contractarea stivei. Dacă stiva se golește, este păcat să menținem ocupat tot spațiul pe care l-am alocat la punctul de maxim. Găsiți un algoritm de contractare a stivei care să ducă la un cost amortizat O(1) pentru operațiile push și pop.

The Master Theorem

The Master Theorem ne oferă o rețetă pentru calculul complexității algoritmilor recursivi.

• introducere: calculul complexității merge sort prin vizualizarea grafică a arborelui de apeluri
  • costul exprimat recurent este T(n) = 2 T(n/2) + n, iar cel nerecurent este T(n) = Θ(n log n)
• una mai grea: T(n) = 2 T(n/2) + O(n log n)
  • încă mai putem face calculul de mână, folosind o sumă de logaritmi sau schimbarea de variabilă h = log₂ n
  • rezultă că T(n) = Θ(n log² n).

Generalizare: Fie recurența T(n) = aT(n/b) + f(n), unde:

• a >= 1, constant
• b > 1, constant
• f(n) asimptotic pozitivă

Fie x = log_b a. Atunci:

1. dacă f(n) = O(n^{x - ε}), pentru ε > 0, atunci T(n) = Θ(n^x)
2. dacă f(n) = Θ(n^x), atunci T(n) = Θ(n^x log n)
   • Cazul 2 extins: dacă f(n) = Θ(n^x log^k n), atunci T(n) = Θ(n^x log^k+1 n)
3. dacă f(n) = Ω(n^{x + ε}), pentru ε > 0, și dacă f(n) satisface condiția de regularitate, atunci T(n) = Θ(f(n))
   • condiția de regularitate: există c < 1 a.î., pentru orice n suficient de mare, a f(n / b) <= c f(n)

Intuitiv, MT arată dacă este mai scump să rezolvăm cazurile de bază (frunzele din arborele de apeluri) sau să combinăm subarborii.

• noțiune de logaritmi: a^{log_b n} = n^{log_b a}
• MT nu acoperă toate cazurile; exemple când nu se poate:
  • a este de forma 2ⁿ: a trebuie să fie constant
  • f(n) este n/log n sau n log n: diferența nu este polinomială (nu există ε)
  • a = 0,5: nu putem avea mai puțin de o subproblemă
  • f(n) = -n log n: f(n) trebuie să fie asimptotic pozitiv
• exemple deja cunoscute (verificăm că MT dă ceea ce știm deja că este corect):
  • căutarea binară T(n) = T(n / 2) + 1
  • traversarea unui arbore binar: T(n) = 2 T(n / 2) + 1
    • traversarea unui arbore k-ar: T(n) = k T(n / k) + 1
  • merge sort
  • înmulțirea a două numere mari prin divide et impera: T(n) = 4 T(n / 2) + n
    • cu numai 3 înmulțiri: T(n) = 3 T(n / 2) + n
• alte exemple:
  • T(n) = 2 T(2n/3) + O(n) sau O(1)
  • T(n) = T(2n/3) + O(n)
  • T(n) = T(99n/100) + O(n)
  • T(n) = T(99n/100) + O(1)
  • T(n) = 2 T(n/2) + O(n log n) - cazul 3 nu merge, dar merge cazul 2
  • T(n) = 4 T(n/2) + O(n² log n)
  • T(n) = T(sqrt(n)) + 1, prin calcul direct, căci nu se aplică MT.

La final, am făcut o mini-demonstrație cu arbori. Cazul al doilea este ușor de demonstrat.

• presupunem că n este putere a lui b, a este întreg.
• pe fiecare nivel efortul este a^k f(n/b^k); calculăm suma acestor costuri când f(n) = n^{log_b a}
• există a^{log_b n} = n^{log_b a} frunze, fiecare cu efort Θ(1)

Temă

• Tema 9 juniori