Cum se evaluează complexitatea unui algoritm sau se…

Analiza complexității algoritmului se face prin analiză asymptotică, care permite descrierea eficienței algoritmului în funcție de dimensiunea datelor de intrare ($n$). Pașii principali:

Definirea operațiilor de bază: Se identifică operațiile a căror timp de execuție depinde semnificativ de $n$ (de exemplu, comparații, atribuiri, operații aritmetice).
Calculul numărului de operații: Se calculează numărul de operații de bază în funcție de $n$. Poate fi o formulă exactă sau o estimare.
Determinarea clasei asymptotice: Se folosesc notările Big O ($O$), Omega ($\Omega$) și Theta ($\Theta$) pentru a descrie comportamentul asimptotic superior, inferior și exact, respectiv.

$O(f(n))$: Algoritmul rulează în timp care nu depășește o constantă înmulțită cu $f(n)$ pentru $n$ mari. Este folosit pentru a descrie cel mai rău caz.
$\Omega(f(n))$: Algoritmul rulează în cel puțin o constantă înmulțită cu $f(n)$ pentru $n$ mari. Este folosit pentru cel mai bun caz.
$\Theta(f(n))$: Algoritmul rulează în timp proporțional cu $f(n)$ pentru $n$ mari. Este folosit pentru cazul mediu sau când cel mai bun și cel mai rău caz au același ordin asimptotic.

Cel mai frecvent, se folosește Big O pentru a descrie limita superioară a timpului de execuție, ceea ce este important pentru înțelegerea scalabilității algoritmului în cel mai rău scenariu.

Neglijarea constantelor și termenilor de ordin inferior: În determinarea asimptoticii, se ignoră multiplicatorii constanți și termenii de ordin inferior, deoarece pentru $n$ mari, domina funcția cu cel mai mare exponent. De exemplu, pentru $3n^2 + 5n + 10$, asimptotic va fi $O(n^2)$.

Tipuri tipice de clase asimptotice (în ordinea creșterii complexității):

$O(1)$: Complexitate constantă (timpul de execuție nu depinde de $n$).
$O(\log n)$: Complexitate logaritmică (timpul de execuție crește foarte lent odată cu $n$, caracteristic pentru algoritmii de căutare binară).
$O(n)$: Complexitate liniară (timpul de execuție este proporțional direct cu $n$, caracteristic pentru o simplă parcurgere).
$O(n \log n)$: Complexitate liniar-logaritmică (caracteristic pentru algoritmi de sortare eficienți, precum Quick Sort sau Merge Sort).
$O(n^2)$: Complexitate pătratică (timpul de execuție crește cu pătratul lui $n$, caracteristic pentru algoritmi de sortare simpli, precum Bubble Sort).
$O(n^c)$ (pentru $c > 1$): Complexitate polinomială.
$O(c^n)$ (pentru $c > 1$): Complexitate exponențială (timpul crește foarte rapid odată cu $n$, caracteristic pentru enumerarea tuturor posibilităților).
$O(n!)$: Complexitate factorială (cel mai înalt clasă de complexitate, crește extrem de rapid).

Pentru determinarea asimptoticii structurilor ciclice:

Blocuri de cod secvențiale: Se adună complexitatea blocurilor. $O(A+B) = O(\max(A, B))$.
Cicluri încorporate: Se multiplică numărul de iterații ale ciclurilor. Un ciclu cu $n$ iterații, în interiorul căruia există alt ciclu cu $m$ iterații, are complexitatea $O(n \times m)$. Dacă $m=n$, complexitatea este $O(n^2)$.
Cicluri cu reducerea dimensiunii datelor de intrare: De exemplu, împărțirea la 2 la fiecare iterație duce la complexitate logaritmică ($O(\log n)$).

Exemplu:

Parcurgerea simplă a unui array:

# Recalcularea operațiilor de bază (comparații, atribuiri)
# Operația principală - comparația în buclă
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 atribuire (în afara buclei)
    for i in range(1, len(arr)): # Se execută de $n-1$ ori
        # În interiorul buclei:
        # 1 comparație (if arr[i] > max_val)
        # potențial 1 atribuire (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Dacă dimensiunea array-ului este $n = \texttt{len(arr)}$, bucla se execută de $n-1$ ori. În fiecare iterație, se execută un număr constant de operații. Numărul total de operații este proporțional cu $n$. Complexitatea asymptotică: $O(n)$.

Exemplu: Sortarea prin inserție (Insertion Sort)

# Recalcularea operațiilor de bază
# Operațiile principale: comparații și atribuiri/mutări de elemente

def insertion_sort(arr):
    # Bucla exterioară se execută de $n-1$ ori
    for i in range(1, len(arr)):
        key = arr[i] # 1 atribuire
        j = i - 1 # 1 atribuire
        # Bucla interioară se execută în cel mai rău caz de $i$ ori
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 atribuire (mutare)
            j -= 1 # 1 scădere și 1 atribuire
        arr[j + 1] = key # 1 atribuire

Bucla exterioară se execută de $n-1$ ori. În cel mai rău caz (array sortat invers), bucla interioară se execută în medie de $i$ ori (sau până la $i$ ori). Suma operațiilor în toate iterațiile buclei exterioare: $1 + 2 + ... + (n-1) \approx n^2/2$. Complexitatea asimptotică: $O(n^2)$ în cel mai rău și mediu caz, $O(n)$ în cel mai bun caz (array deja sortat). În evaluarea complexității, de obicei, se consideră cel mai rău caz (Big $O$).

Cum se evaluează complexitatea unui algoritm sau se determină asimptota sa?