Note de curs, clasele 9-10, 24 mai 2013

From Algopedia
Jump to: navigation, search

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 CR(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

Exemple, toate analizate prin cele trei metode

Nearest neighbor

Problema: 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].

Soluție: Menținem o stivă de elemente „interesante” din V văzute până acum. La pasul i, ștergem din stivă toate elementele mai mari ca V[i] (operație numită multipop, apoi inserăm V[i].

Analiză agregată: Operațiile push sunt clar O(1). Fiecare operație multipop poate fi O(n), dar costul tuturor operațiilor multipop nu poate depăși O(n), căci nu putem scoate din stivă mai multe elemente decât am introdus. Deci costul mediu al unei operații este O(1).

Metoda contabilității: La introducerea în stivă a unui element plătim $2. Costul instantaneu este $1, iar $1 rămâne într-o „pușculiță” alăturată elementului. Când elementul este scos din stivă, contabilul consumă și al doilea dolar. Deci costul per element este $2.

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

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 / 2k 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 din contor după a i-a operație

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

Simularea unui quack folosind trei stive

Problema: Se cere să implementăm un quack, adică un hibrid între stivă și coadă, folosind trei stive ca structură internă. Operațiile pe quack sunt push (adaugă în stânga), pop (scoate din stânga) și pull (scoate din dreapta).

Soluție: Folosim S și T pentru a stoca elementele din quack. Adăugarea în stânga se face adăugând în S. Scoaterea din stânga, respectiv din dreapta, se fac scoțând din S, respectiv din T. Dacă dorim să extragem din S, dar S este goală, mutăm jumătate din elementele din T în S, folosind a treia stivă ca spațiu de manevră.

Analiză amortizată: Devine mai complicată! Există elemente care pot trece prin O(log n) înjumătățiri. Deci costul total este o sumă de logaritmi. Ca și la heap, totuși, suma de logaritmi este de fapt O(n).

Metoda contabilității: Nu este clar cum s-ar aplica aici. Dacă cerem log(n) dolari de la fiecare element inserat, vom avea un cost total de O(n log n).

Metoda potențialului: \Phi (i)=||S|-|T|| la momentul i.

Delete-Larger-Half

Problema: Să concepem o structură care stochează numere și admite două operații: (1) insert(x) inserează x în structură și (2) deleteLargerHalf() șterge jumătate dintre elementele existente în structură, cele mai mari.

Soluție: Stocăm elementele într-un vector nesortat. Pentru deleteLargerHalf(), căutăm medianul în vector și reducem dimensiunea vectorului la jumătate.

Analiză amortizată: Și mai greu de dus la capăt.

Metoda contabilității: Un element poate rezista la infinit în structură. Cât credit să cerem la inserare? Din fericire, există un artificiu ingenios. Creditul la inserare este $3. Inserarea costă $1. Ștergerea este gratuită (căci trebuie doar calculat k = k / 2). Pentru deleteLargerHalf(), toate elementele plătesc câte $1 pentru găsirea medianului în O(k). Elementele care vor fi șterse plătesc ultimul lor dolar elementelor care rămân în vector.

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

Teme

Incrementarea unui contor Fibonacci

Această problemă este grea. Dacă nu vă vine nicio idee, căutați pe Internet algoritmul și, mai ales, calculul de complexitate.

Să considerăm un număr format din cifre de 0 și 1 într-o bază variabilă: Cifra de pe poziția i semnifică Fi, al i-lea număr Fibonacci. De exemplu, 1011011 = 13 + 5 + 3 + 1 + 1 = 23. O cifră din acest număr se mai numește și „fit” (de la Fibonacci bit). Remarcăm că reprezentarea nu este unică. De exemplu, 10000000 = 21 de asemenea.

Să se găsească un algoritm care să permită incrementarea și decrementarea unui contor pe k fiți în O(1) amortizat.

Înmulțirea a două numere mari

Această problemă nu se leagă de lecția de astăzi, ci de lecția următoare, The Master Theorem.

Pentru a înmulți două numere mari x și y (de n cifre fiecare), algoritmul naiv face O(n2) operații. Să considerăm acum următoarea îmbunătățire: Scriem x = ab și y = cd, unde a, b, c, d au câte n / 2 cifre fiecare. Atunci:

x\cdot y=a\cdot c\cdot 10^{n}+(a\cdot d+b\cdot c)\cdot 10^{{n/2}}+b\cdot d

Acum putem să calculăm produsele a\cdot c, a\cdot d, b\cdot c și b\cdot d, ceea ce duce la recurența:

T(n)=4T(n/2)+O(n)

O a doua îmbunătățire este să calculăm (a+b)\cdot (c+d), a\cdot c și b\cdot d, după care calculăm a\cdot d+b\cdot c prin diferență. Acest algoritm face mai multe adunări și scăderi, dar mai puține înmulțiri, iar complexitatea lui este exprimată recurent ca:

T(n)=3T(n/2)+O(n)

Încercați să eliminați recurența și să calculați T(n) pentru cele două variante.