Complexitatea algoritmilor pentru admitere

Dacă o instrucțiune se execută $3n+7$ ori, acesta este numărul exact în modelul ales. Ordinul de creștere este liniar: $\Theta(n)$. Notația $O(n)$ exprimă o limită superioară asimptotică; $\Theta(n)$ descrie o limită strânsă, de sus și de jos.

Un algoritm liniar este și $O(n^2)$, însă răspunsul cel mai informativ este limita strânsă. Citește dacă problema cere numărul exact de execuții sau complexitatea.

La admitere se folosește frecvent modelul în care o operație aritmetică pe un întreg de dimensiune fixă costă o unitate. Exemplificările de aici presupun că valorile încap în tipurile folosite.

Două parcurgeri consecutive cu $n$ pași fiecare au $n+n=2n$ pași, deci ordin liniar. Dacă pentru fiecare dintre cei $n$ pași exteriori rulează alți $n$ pași interiori, obții $n\cdot n=n^2$.

O limită interioară variabilă cere o sumă. Pentru $i=1,2,\ldots,n$, dacă bucla interioară rulează de $i$ ori, numărul total este:

$1+2+\cdots+n=\frac{n(n+1)}{2}.$

Ordinul rămâne $\Theta(n^2)$, deși numărul exact nu este $n^2$. Pentru o sumă de costuri, termenul cu creșterea dominantă stabilește ordinul: $n^2+100n+20$ este $\Theta(n^2)$.

Urmărește o buclă care împarte repetat o valoare pozitivă la 2:

for (int k = n; k > 0; k /= 2) {
  ++pasi;
}

Pentru n = 13, valorile sunt 13, 6, 3 și 1: patru pași. Împărțirea între întregi trunchiază rezultatul. Pentru n >= 1, numărul de pași este partea întreagă a lui log₂(n), plus 1. Ordinul este logaritmic. Pentru n = 0, bucla nu rulează.

Dacă rulezi această buclă pentru fiecare dintre cele n elemente ale unui vector, cu același n inițial de fiecare dată, costul total este de ordinul n log n.

O buclă cu un contor poate face $n^2$ operații și folosi doar $O(1)$ memorie auxiliară. Un vector suplimentar cu $n$ elemente ocupă $O(n)$ memorie auxiliară, chiar dacă îl completezi într-o singură parcurgere.

La funcțiile recursive, include stiva apelurilor. Un lanț de $n$ apeluri cu un număr constant de variabile locale ocupă $O(n)$ memorie auxiliară. Vezi urmărirea apelurilor recursive.

Dacă algoritmul poate termina anticipat, precizează cazul analizat. Căutarea liniară într-un vector poate găsi elementul la prima poziție, dar în cazul cel mai defavorabil verifică toate cele $n$ poziții.

Pentru un întreg n >= 1, suficient de mic încât calculele să încapă în tipurile folosite, de câte ori se execută ++s? Care sunt costurile în timp și memorie auxiliară?

long long s = 0;
for (int i = 1; i <= n; ++i) {
  for (int j = 1; j <= i; ++j) {
    ++s;
  }
}
for (int k = n; k > 0; k /= 2) {
  ++s;
}

Prima parte execută incrementarea de $1+2+\cdots+n=n(n+1)/2$ ori. A doua parte adaugă $\lfloor\log_2 n\rfloor+1$ incrementări. Buclele sunt consecutive, deci aduni:

$s=\frac{n(n+1)}{2}+\lfloor\log_2 n\rfloor+1.$

Pentru $n=8$, prima parte dă 36, iar a doua are valorile $k=8,4,2,1$, deci 4 pași. Rezultatul este 40.

Timpul este $\Theta(n^2)$, iar memoria auxiliară este $O(1)$: numărul de variabile nu crește cu $n$.