Clasele 9-10 lecția 1 - 18 sep 2015

Analiză amortizată

Analiză amortizată

• analizează un algoritm care face pe o structură de date diverse operații cu diverse costuri
• încercăm să găsim o limită cât mai strânsă pentru costul mediu al unei operații
• există trei metode:

Analiză agregată

• calculează costul total al celor n operații și împarte la n pentru a afla costul mediu al unei operații

Metoda contabilității

• cere credit suplimentar pentru operațiile ieftine, încercând ca prin aceasta să plătească operațiile mai scumpe
• ne duce cu gândul la un contabil 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

Metoda potențialului

• 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)$

• deși poate părea magică, însumând costul total pentru operațiile 1, 2, ..., 'n', obținem:

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

• 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

Temă

Pentru data viitoare nu veți avea temă.