În continuare vom prezenta o analiză succintă a utilizărilor funcțiilor logaritmice și

exponențiale în analiza algoritmilor informatici.

Pentru analiza unui algoritm se folosesc 2 mărimi: complexitatea de timp și de
spațiu. Pornind de la asumarea că un calculator modern are nevoie de o cantitate
constantă de timp pentru a efectua orice operație, putem defini complexitatea de
timp ca fiind echivalentă cu numărul de operații necesare de efectuat.

numere[1] = 2 + 3;

Această linie de cod face 3 operații: adunarea numerelor 2 si 3, indexarea

elementului cu numărul 1 din variabila numere și atribuirea valorii 5 acestui
element. Astfel, putem observa complexitatea procesului de numărare a operațiilor
necesare unui program

while(n--)
Numere[n] = n+1;

Acest ciclu face câte 4 operații la fiecare iterație: cele 3 operații descrise mai sus și
operația de decrementare a variabilei n. Astfel, putem spune că complexitatea de
timp a fragmentului de cod este 4 ⋅ 𝑛.

Din cauza dificultății sporite a determinării numărului exact de operații în

programele mai complicate, a fost introdusă notația marelui O, care discreditează
constantele, coeficienții și termenii care nu sunt de grad maxim. Astfel,
complexitatea de timp a primului fragment este O(1), iar a celui de al doilea - O(n).

În continuare, vom introduce introduce problema P vs NP. Ca o definiție

informală, aceasta întreabă dacă fiecare problemă ale cărei soluții pot fi verificate
rapid de un calculator poate fi și rezolvată rapid de un calculator.

În tipul P sunt incluse problemele care pot fi soluționate și a căror soluție poate fi
verificată cu o complexitate de timp polinomial: 𝑂(𝑛𝑘 ), unde k nu depinde de n .
Un exemplu trivial de problemă de tip P este: Se dă un set de n numere întregi și
un număr x, să se determine dacă printre numerele din set există un număr care să
fie egal cu x. Această problemă poate fi rezolvată prin simpla parcurgere a șirului,
si verificarea respectării condiției pentru fiecare element, astfel având o
complexitate O(n).

Clasa de probleme NP cuprinde probleme care pot fi verificate în timp polinomial,

dar al căror răspuns nu poate fi determinat în timp polinomial. NP în aceste
circumstanțe înseamnă „timp nedeterminist polinomial”. Cel mai frecvent, aceste
probleme pot fi rezolvate doar în timp exponențial 𝑂(𝑘 𝑛 ) unde k este o constantă,
𝑘 ≠ 0.
Fie problema sumei elementelor submulțimilor, un exemplu de problemă ușor de
verificat, dar al cărui răspuns poate fi dificil de calculat. Dată fiind o mulțime de
numere întregi, există vreo submulțime nevidă a ei ale cărei elemente au suma 0?
De exemplu, există o submulțime a mulțimii {−2, −3, 15, 14, 7, −10} ale cărei
elemente adunate dau 0? Răspunsul este „da, pentru că submulțimea {−2, −3, −10,
15} are suma zero” și poate fi rapid verificat efectuând trei adunări; dar nu există
niciun algoritm cunoscut care să găsească această submulțime în timp polinomial
(există doar unul care îl găsește în timp exponențial, și care efectuează 2𝑛 − 𝑛 − 1
încercări, astfel având o complexitate 𝑂(2𝑛 ).
De asemea, problemele din categoria P aparțin prin definiție și categoriei NP, de
aceea pentru a denumi problemele care nu au o soluție polinomială se folosește și
termenul de NP - completă.
Trebuie de notat că acest tip de probleme poate fi rezolvat într-un context din viața
reală într-un timp pseudo-polinomial, folosind 𝑂(𝑛2 ) timp si 𝑂(𝑛2 ) spațiu, însă
arătarea acestor metoda nu se numără printre scopurile acestei prezentări.
Astfel, rezolvarea problemei P vs NP poate duce la 2 concluzii:
● P = NP: Dacă acest fapt ar fi demonstrat, toate problemele cu solutii
exponentiale anterior imposibil de rezolvat la scala larga ar putea fi rezolvate
în timp polinomial. Demonstrarea P = NP ar insemna ca ar disparea
diferentele de dificultate intre a verifica veridicitatea unei idei și propriu-zis
descoperirea faptului respectiv. Consecințele unei asemenea descoperiri ar fi
monumentale
● 𝑃 ≠ 𝑁𝑃: Majoritatea oamenilor de știință din domeniu mizează pe această
posibilitate, nimeni însă nu a reușit să aducă o demonstrație riguroasă a
acestei relații.
Această problemă este inclusă printre cele 7 probleme pentru premiul mileniului,
acordându-se $1 000 000 pentru cine urmează să o rezolve.

În continuare vom arăta aplicările funcțiilor matematice studiate într-o problemă

clasică a informaticii: sortarea unui set de n elemente. Pentru a facilita explicația,
vom folosi numere întregi ca elemente ale setului. Se cere sortarea în ordine
crescătoare a acestor elemente folosind două operații:
● Compararea a două elemente și determinarea celui cu o valoare mai mare.
● Schimbarea cu locul a oricăror două elemente.
O soluție naivă, dar ușor implementabilă, a acestei probleme este parcurgerea de n
ori a setului, la fiecare parcurgere comparându-se elementele adiacente, și
schimbându-se cu locul dacă e cazul.
Pentru că la fiecare dintre cele n iterații se vor efectua un maxim de n comparări și
schimbări, acest algoritm are o complexitate de timp 𝑂(𝑛2 ).
Acest algoritm de sortare se numește sortare cu bule (bubble sort).
Aceasta este o implementare generică în limbajul C++ a algoritmului sortare cu
bule:

void swap(int *xp, int *yp)

{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

void bubbleSort(int arr[], int n)

{
int i, j;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}

Această schemă ilustrează ce se întâmplă în una dintre cele n iterații.

Un algoritm mult mai eficient de sortare a elementelor unui set este așa-numitul
quicksort.
Într-o iterație, acesta alege un oarecare element din set, pe care îl vom numi pivot
în continuare, și compară restul elementelor cu acesta, punându-le la stânga dacă
sunt mai mici și la dreapta dacă sunt mai mari. Astfel elementul pivot a ajuns în
locul său final în setul sortat. În următoare iterație, se va repeta acest algoritm cu
cele 2 jumătăți ale setului, din dreapta și stânga pivotului.
Acest ciclu va continua, până când cel mai mare subset obținut va conține 2
elemente, setul fiind sortat odată cu aranjarea în ordine a acestor elemente.
În dependență de cât de aproape este elementul pivot de mijlocul subsetului căruia
îi aparține, complexitatea de timp a algoritmului quicksort variază între 𝑂(𝑛2 )- cel
mai rău caz, în practică nu este înâlnit niciodată și 𝑂(𝑛) - cel mai bun caz, de
asemenea neîntâlnit în scenarii practice.
Analizând secvența de operații, putem determina că în medie, acest algoritm va
avea o eficiență exprimată ca 𝑂(𝑛 ⋅ log 2 𝑛), efectuând câte n operații de fiecare
dată când setul este împărțit în 2 subseturi.
O implementare generică a algoritmului quicksort, care alege mereu ultimul
element ca pivot:

void swap(int* a, int* b)

{
int t = *a;
*a = *b;
*b = t;
}
int partition (int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++)
{

if (arr[j] < pivot)

{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

void quickSort(int arr[], int low, int high)

{
if (low < high){
int pi = partition(arr, low, high)
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
Algoritmul respectiv poate fi descris prin următoarea schemă:

Așadar am determinat câteva dependențe logaritmice, exponențiale și polinomiale

între volumul de date pe care un algoritm trebuie să îl parcurgă și timpul necesar.
Aceste dependențe sunt extrem de importante în crearea aplicațiilor și a sistemelor
computerizate, creând diferențe enorme ale timpului de execuție în cazul
volumului mare de date.
Ținând cont că un calculator modern poate efectua până la aproximativ 108 operații
într-un timp acceptabil, în cazul unui algoritm exponential 𝑂(𝑘 𝑛 ) obișnuit,
executat pe un calculator de putere medie, n maxim poate fi 20. În același timp,
pentru un algoritm logaritmic 𝑂(log 𝑘 𝑛) numărul maxim n poate ajunge la
8
10100000000 𝑠𝑎𝑢 1010 , atât de mare fiind diferenta.
 Bibliografie:
 [Link]
 [Link]
 [Link]
 [Link]
 Khan academy
 Good Vibrations with Freeball