Kaip įvertinti algoritmo sudėtingumą arba nustatyti…

Algoritmų sudėtingumo įvertinimui naudojama asymptotinė analizė, leidžianti aprašyti algoritmo efektyvumą priklausomai nuo įvesties duomenų dydžio ($n$). Pagrindiniai žingsniai:

Pagrindinių operacijų nustatymas: Išskiriamos operacijos, kurių vykdymo laikas žymiai priklauso nuo $n$ (pvz., palyginimai, priskyrimai, aritmetinės operacijos).
Operacijų skaičiaus skaičiavimas: Apskaičiuojamas pagrindinių operacijų kiekis priklausomai nuo $n$. Tai gali būti tiksli formulė arba įvertinimas.
Asymptotinės klasės nustatymas: Naudojami Didžiojo O ($O$), Omega ($\Omega$) ir Teta ($\Theta$) žymėjimai, apibūdinantys viršutinį, apatinį ir tikslų asymptotinį elgesį atitinkamai.

$O(f(n))$: Algoritmas vykdomas per laiką, neviršijantį konstantos, padaugintos iš $f(n)$, dideliems $n$. Naudojama apibūdinti ** blogiausiam ** atvejui.
$\Omega(f(n))$: Algoritmas vykdomas per laiką, ne mažiau kaip konstantos, padaugintos iš $f(n)$, dideliems $n$. Naudojama apibūdinti ** geriausiam ** atvejui.
$\Theta(f(n))$: Algoritmas vykdomas per laiką, proporcingą $f(n)$, dideliems $n$. Naudojama apibūdinti ** vidutiniam ** atvejui arba kai geriausias ir blogiausias atvejai turi tą patį asymptotinį tvarką.

Dažniausiai naudojamas Didžiojo $O$ žymėjimas apibūdinti viršutinę vykdymo laiko ribą, kas svarbu siekiant suprasti algoritmo mastelio keičiamumą blogiausiu atveju.

Konstantų ir mažesnių narių ignoravimas: Nustatant asymptotiką ignoruojami konstantiniai koeficientai ir žemesnio tvarkos nariai, nes dideliems $n$ dominuoja didžiausio laipsnio funkcija. Pavyzdžiui, $3n^2 + 5n + 10$ asymptotika bus $O(n^2)$.

Tipinės asymptotinės klasės (mažėjimo tvarka pagal sudėtingumą):

$O(1)$: Konstanta (vykdymo laikas nepriklauso nuo $n$).
$O(\log n)$: Logaritminė sudėtingumas (vykdymo laikas labai lėtai auga su $n$, būdingas dvejetinio paieškos algoritmo sudėtingumui).
$O(n)$: Linijinis sudėtingumas (vykdymo laikas tiesiog proporcingas $n$), būdingas paprastam peržiūrai.
$O(n \log n)$: Linijinis-logaritminis sudėtingumas (efektyvių rūšiavimo algoritmų, tokių kaip Quick Sort ar Merge Sort, būdingas).
$O(n^2)$: Kvadratinis sudėtingumas (vykdymo laikas auga kvadratu $n$, būdingas paprastiems rūšiavimo algoritmams, pvz., Bubble Sort).
$O(n^c)$ (c > 1): Polinominis sudėtingumas.
$O(c^n)$ (c > 1): Eksponentinis sudėtingumas (vykdymo laikas labai greitai auga su $n$, būdingas visų galimų variantų peržiūrai).
$O(n!)$: Faktorialinis sudėtingumas (aukščiausia sudėtingumo klasė, labai greitai augantis).

Norint nustatyti ciklinių struktūrų asymptotiką:

Eiliški kodo blokai: Sudėtingumas sudedamas. $O(A+B) = O(\max(A, B))$.
Įdėti ciklai: Dauginama ciklų iteracijų skaičius. Ciklas su $n$ iteracijų, kurio viduje yra kitas ciklas su $m$ iteracijų, turi sudėtingumą $O(n \times m)$. Jei $m=n$, sudėtingumas $O(n^2)$.
Ciklai su duomenų dydžio mažinimu: Pvz., dalijimas iš 2 kiekvienoje iteracijoje lemia logaritminį sudėtingumą ($O(\log n)$).

Pavyzdys:

Paprastas masyvo peržiūrėjimas:

# Pagrindinių operacijų skaičiavimas (palyginimai, priskyrimai)
# Pagrindinė operacija - palyginimas cikle
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 priskyrimas (už ciklo)
    for i in range(1, len(arr)): # Ciklas vyksta $len(arr) - 1$ kartų
        # Viduje ciklo:
        # 1 palyginimas (if arr[i] > max_val)
        # galimai 1 priskyrimas (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Jei masyvo dydis $n = \texttt{len(arr)}$, ciklas vyksta $n-1$ kartą. Kiekvienoje iteracijoje vykdomas pastovus operacijų skaičius. Bendra operacijų skaičius proporcingas $n$. Asimptotinė sudėtingumas: $O(n)$.

Pavyzdys: įterpimo rūšiavimas (Insertion Sort)

# Pagrindinių operacijų skaičiavimas
# Pagrindinės operacijos: palyginimai ir priskyrimai/perkėlimai
def insertion_sort(arr):
    # Išorinis ciklas vyksta $n-1$ kartų
    for i in range(1, len(arr)):
        key = arr[i] # 1 priskyrimas
        j = i - 1 # 1 priskyrimas
        # Vidinis ciklas vyksta blogiausiu atveju $i$ kartų
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 priskyrimas (perkėlimas)
            j -= 1 # 1 atėmimas ir 1 priskyrimas
        arr[j + 1] = key # 1 priskyrimas

Išorinis ciklas vyksta $n-1$ kartą. Vidinis ciklas blogiausiu atveju (masyvas atvirkščiai surūšiuotas) vyksta vidutiniškai $i/2$ kartų (arba iki $i$ kartų). Bendra operacijų skaičius visoms išorinio ciklo iteracijoms viduje: $1 + 2 + ... + (n-1) \approx n^2/2$. Asimptotinė sudėtingumas: $O(n^2)$ blogiausiu ir vidutiniu atveju, $O(n)$ geriausiu atveju (jei masyvas jau surūšiuotas). Vertinant sudėtingumą dažnai laikoma blogiausio atvejo (Didžiojo $O$).

Kaip įvertinti algoritmo sudėtingumą arba nustatyti jo asimptotą?