Clasa a 7-a Lecția 12: Analiză amortizată (1)

Înregistrare video curs

Despre analiza amortizată

Citat din CLRS: Î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.

Pentru a înțelege conceptul cât mai bine, iată un clip preluat de pe canalul NerdFirst:

În continuare vom lua 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ă operațiune de 2ⁿ 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, 2ⁿ.

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:

Failed to parse (syntax error): {\displaystyle T(n) = 2^n + 2^{n-1} + 2^{n-2} + \cdots + 2^1 \\[1em] }

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:

Failed to parse (syntax error): {\displaystyle 111\ldots110_{(2)} + 2_{(10)} = 100\ldots0_{(2)} \quad \text{(1 urmat de } n+1 \text{ zerouri)} \\[1em] }

Acest număr este 2n+1. Rezultă că:

T(n)+2=2n+1

și deci Failed to parse (syntax error): {\displaystyle T(n) = 2n + 1 - 2 \\[1em] }

Acesta este numărul total de operații, pentru toate incrementările. Împărțind la numărul de incrementări, care este 2ⁿ, 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:

Permutări cu liste

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 $n$ vom așeza $n$ cifre;
pentru fiecare cifră de pe nivelul $n$ , pe nivelul $n-1$ vom așeza $n-1$ cifre;
pentru fiecare cifră de pe nivelul $n-1$ , pe nivelul $n-2$ vom așeza $n-2$ cifre;
...
pentru fiecare cifră de pe nivelul $2$ , pe nivelul $1$ vom așeza o cifră.

Observație: ceea ce am denumit nivelul $n$ este de fapt prima poziție în vectorul în care generăm permutările, nivelul $n-1$ este de fapt a doua poziție, și așa mai departe, nivelul $1$ fiind ultima poziție din vector.

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 $k$ operații. Apoi, pentru fiecare element așezat vom chema recursiv funcția, deci vom avea $k$ apeluri la nivelul $k-1$ :

{\begin{aligned}T(k)&=k+k\cdot T(k-1)\\[1em]T(k)&=k+k\cdot \left((k-1)+(k-1)\cdot \left((k-2)+(k-2)\cdot \left(\cdots +3\cdot (2+2\cdot T(1))\cdots \right)\right)\right)\\[1em]T(k)&=k+k(k-1)+k(k-1)(k-2)+\cdots +k(k-1)(k-2)\cdots 3+k(k-1)(k-2)\cdots 3\cdot 2+k(k-1)(k-2)\cdots 3\cdot 2\cdot T(1)\\[1em]\end{aligned}}

Dar $T(1)$ este $1$ , deoarece vom așeza un singur element. Așa încât:

{\begin{aligned}T(k)&=k+k(k-1)+k(k-1)(k-2)+\cdots +k(k-1)(k-2)\cdots 3+k(k-1)(k-2)\cdots 3\cdot 2+k(k-1)(k-2)\cdots 3\cdot 2\cdot 1\\[1em]T(k)&={\frac {k!}{(k-1)!}}+{\frac {k!}{(k-2)!}}+{\frac {k!}{(k-3)!}}+\cdots +{\frac {k!}{2!}}+{\frac {k!}{1!}}+{\frac {k!}{0!}}\\[1em]T(k)&=k!\left({\frac {1}{(k-1)!}}+{\frac {1}{(k-2)!}}+{\frac {1}{(k-3)!}}+\cdots +{\frac {1}{2!}}+{\frac {1}{1!}}+{\frac {1}{0!}}\right)\\[1em]\end{aligned}}

Suma:

Failed to parse (syntax error): {\displaystyle \frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \cdots + \frac{1}{(k - 1)!} \\[1em]}

va fi studiată în clasa a zecea. Se demonstrează că ea este mai mică decât o constantă $e=2.71828...$ . Drept pentru care:

Failed to parse (syntax error): {\displaystyle T(k) \approx e \cdot k! \\[1em]}

Numărul total de operații se obține pentru $k=n$ :

Failed to parse (syntax error): {\displaystyle T(n) = e \cdot n! \\[1em]}

Deoarece avem $n!$ permutări rezultă că generarea unei permutări ne costă O(e) = 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.

Permutări cu vector de frecvență

Să considerăm acum primul algoritm, 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 sunt 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$ :

{\begin{aligned}T(k)&=n+k\cdot T(k-1)\\[1em]T(k)&=n+k\left(n+(k-1)\left[n+(k-2)\left(\cdots +3(n+2\cdot T(1))\cdots \right)\right]\right)\\[1em]T(k)&=n+kn+k(k-1)n+k(k-1)(k-2)n+\cdots +k(k-1)(k-2)\cdots 3\cdot n+k(k-1)(k-2)\cdots 3\cdot 2\cdot T(1)\end{aligned}}

Dar $T(1)$ este $n$ , deoarece vom parcurge toate elementele și vom așeza unul singur. Așa încât:

{\begin{aligned}T(k)&=n+n\left(k+k(k-1)+k(k-1)(k-2)+\cdots +k(k-1)(k-2)\cdots 3+k(k-1)(k-2)\cdots 3\cdot 2\right)\\[1em]T(k)&=n+n\left({\frac {k!}{(k-1)!}}+{\frac {k!}{(k-2)!}}+{\frac {k!}{(k-3)!}}+\cdots +{\frac {k!}{2!}}+{\frac {k!}{1!}}\right)\\[1em]T(k)&=n+nk!\left({\frac {1}{(k-1)!}}+{\frac {1}{(k-2)!}}+{\frac {1}{(k-3)!}}+\cdots +{\frac {1}{2!}}+{\frac {1}{1!}}\right)\end{aligned}}

Suma dintre paranteze este, din nou, mai mică decât $e-1$ , unde $e$ este constanta $e=2.71828....$ . Drept pentru care:

Failed to parse (syntax error): {\displaystyle T(k) \approx n + (e - 1) \cdot n \cdot k! \\[1em]}

Numărul total de operații se obține pentru $k=n$ :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(n) = n + (e - 1) \cdot n \cdot n! \\[1em]}

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 Failed to parse (syntax error): {\displaystyle (e-1)·n} , adică O(n). De unde rezultă că acest algoritm este inferior celui cu liste.

Ar trebui să vedem că algoritmul cu liste este de $x$ ori mai rapid, unde $x={\frac {(e-1)\cdot n}{e}}=\left(1-{\frac {1}{e}}\right)\cdot n$ . Pentru n=10 numărul $x$ este circa $6.32$ . În realitate vom obține mai puțin deoarece algoritmul cu liste are o constantă multiplicativă ceva mai mare. Pe algoritmii prezentați am măsurat circa $3.8$ .

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. 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 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 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ția forță brută este ca pentru fiecare indice i să căutăm spre stânga primul indice j unde găsim un element mai mare. Această soluție este O(n2).

Soluție elegantă: parcurgem v și menținem o stivă 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 = [7 3 2 5 4 3 9 7]
 Stiva s = []
 Vectorul w = []

Pasul 0:

 Scoatem din s toate elementele mai mici sau egale cu v[0] == 7
 s este goală, nu există nici un element mai mare ca v[0] == 7
 Calculăm w[0] = vîrful stivei = nu există, deci îl vom marca cu X 
   (X este o valoare ce indică lipsa unui element mai mare ca v[0] la stînga)
 Adăugăm v[0] == 7 la s
 Obținem:
   v = [7 3 2 5 4 3 9 7]
   w = [X]
   s = [7]

Pasul 1:

 Scoatem din s toate elementele mai mici sau egale cu v[1] == 3
 Nu există astfel de elemente, deci stiva rămîne nemodificată
 Calculăm w[1] = vîrful stivei = 7
 Adăugăm v[1] == 3 la s
 Obținem:
   v = [7 3 2 5 4 3 9 7]
   w = [X 7]
   s = [7 3]

Pasul 2:

 Scoatem din s toate elementele mai mici sau egale cu v[2] == 2
 Nu există astfel de elemente, deci stiva rămîne nemodificată
 Calculăm w[2] = vîrful stivei = 3
 Adăugăm v[2] == 2 la s
 Obținem:
   v = [7 3 2 5 4 3 9 7]
   w = [X 7 3]
   s = [7 3 2]

Pasul 3:

 Scoatem din s toate elementele mai mici sau egale cu v[3] == 5
 Vom elimina ultimele două elemente, 3 și 2, deci stiva devine s = [7]
 Calculăm w[3] = vîrful stivei = 7
 Adăugăm v[3] == 5 la s
 Obținem:
   v = [7 3 2 5 4 3 9 7]
   w = [X 7 3 7]
   s = [7 5]

Pasul 4:

 Scoatem din s toate elementele mai mici sau egale cu v[4] == 4
 Nu există astfel de elemente, deci stiva rămîne nemodificată
 Calculăm w[4] = vîrful stivei = 5
 Adăugăm v[4] == 4 la s
 Obținem:
   v = [7 3 2 5 4 3 9 7]
   w = [X 7 3 7 5]
   s = [7 5 4]

Pasul 5:

 Scoatem din s toate elementele mai mici sau egale cu v[5] == 3
 Nu există astfel de elemente, deci stiva rămîne nemodificată
 Calculăm w[5] = vîrful stivei = 4
 Adăugăm v[5] == 3 la s
 Obținem:
   v = [7 3 2 5 4 3 9 7]
   w = [X 7 3 7 5 4]
   s = [7 5 4 3]

Pasul 6:

 Scoatem din s toate elementele mai mici sau egale cu v[6] == 9
 Vom elimina toate elementele din s, deci stiva devine vidă
 Calculăm w[6] = vîrful stivei = nu există, deci îl vom marca cu X
 Adăugăm v[6] == 9 la s
 Obținem:
   v = [7 3 2 5 4 3 9 7]
   w = [X 7 3 7 5 4 X]
   s = [9]

Pasul 7:

 Scoatem din s toate elementele mai mici sau egale cu v[7] == 7
 Nu există astfel de elemente, deci stiva rămîne nemodificată
 Calculăm w[7] = vîrful stivei = 9
 Adăugăm v[7] == 7 la s
 Obținem:
   v = [7 3 2 5 4 3 9 7]
   w = [X 7 3 7 5 4 X 9]
   s = [9 7]

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

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 din punct de vedere al complexității. 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).

Problema StrGen

Problema strgen a fost dată la testul de evaluare Nerdvana din 1 noiembrie 2023.

Am dat această problemă în ideea rezolvării cu liste, dar am menționat atunci că există o rezolvare cu două stive și analiză amortizată. Să o reluăm.

Soluție cu două stive

Există o soluție eficientă ce folosește două stive. Prima stivă este cea în care adăugăm atunci când inserăm un caracter. La momentul avansului poziției scoatem un caracter din prima stivă și îl depunem într-o a doua stivă.

Dacă nu vom ajunge să reluăm poziția de la 1, înseamnă că șirul nostru final este format din caracterele din stiva 2 afișate în sens invers scoaterii din stivă, urmate de caracterele din stiva 1 afișate în sensul scoaterii din stivă.

Ce facem dacă poziția se reia de la 1? Înseamnă că stiva 1 devine goală. Caz în care vom scoate elementele din stiva 2, unul câte unul, și le vom depune în stiva 1. Astfel stiva 2 devine goală, iar stiva 1 conține caracterele șirului curent.

La final afișăm stiva 2 în sens invers și stiva 1 în sens direct.

Iată un program posibil (26 de linii de cod efectiv):

#include 

#define MAXL 2000000

char stiva1[MAXL + 1] = { '$' }, stiva2[MAXL + 1];

int main() {
  FILE *fin, *fout;
  char ch;
  int i, n1 = 1, n2 = 0;

  fin = fopen( "strgen.in", "r" );
  while ( (ch = fgetc( fin )) != '\n' )
    if ( ch == '>' ) {
      stiva2[n2++] = stiva1[--n1]; 
      if ( n1 == 0 )
        while ( n2 > 0 )
          stiva1[n1++] = stiva2[--n2];
    } else
      stiva1[n1++] = ch;
  fclose( fin );

  fout = fopen( "strgen.out", "w" );
  for ( i = 0; i = 0; i-- )
    fputc( stiva1[i], fout );
  fputc( '\n', fout );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

La prima vedere pare că fiecare operație poate fi O(N) ceea ce ar rezulta într-o complexitate de O(N2). În realitate nu este așa, deoarece pentru fiecare caracter scos din stiva 2 și inserat în stiva 1 vom avea o operație de scoatere din stivă ce se va efectua în O(1). Suma tuturor operațiilor nu poate depăși O(N).

Câtă memorie folosim? Desigur tot O(N), circa 2 bytes per element, deci 2MB (mai puțină decât în soluția cu listă).

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.

Temă 12

Tema

Tema 13 presupune să se rezolve următoarele probleme (program C trimis la nerdarena):

Tower, dată la Shumen 2016 juniori
NrTri, dată pregătire Vianu clasa a 9-a

Tema opțională

Tema 13 opțională presupune să rezolvați următoarele probleme (program C trimis la nerdarena):

NrTri1, problemă identică cu NrTri cu limitele modificate.

Clasa a 7-a Lecția 12: Analiză amortizată (1)

Contents

Înregistrare video curs

Despre analiza amortizată

Incrementarea unui contor binar

Permutări

Permutări cu liste

Permutări cu vector de frecvență

Clădiri vizibile

Problema bibliotecarului

Problema StrGen

Concluzii

Temă 12

Tema opțională

Navigation menu

Page actions

Page actions

Personal tools

Navigation

Search

Tools