Ako odhadnúť zložitosť algoritmu alebo určiť jeho…

Pre hodnotenia zložitosti algoritmu sa využíva asymptotickú analýzu, ktorá umožňuje popísať efektívnosť algoritmu v závislosti od veľkosti vstupných dát ($n$). Hlavné kroky:

Určenie základných operácií: Vyberajú sa operácie, ktorých čas vykonania značne závisí od $n$ (napríklad porovnania, priradenia, aritmetické operácie).
Počítanie počtu operácií: Vypočíta sa počet základných operácií v závislosti od $n$. Môže ísť o presnú formulu alebo odhad.
Určenie asymptotickej triedy: Používajú sa označenia Veľké O ($O$), Omega ($\Omega$) a Theta ($\Theta$) na opis horného, dolného a presného asymptotického správania.

$O(f(n))$: Algoritmus sa vykonáva za čas, ktorý neprekračuje konštantu, násobenú $f(n)$, pri veľkých $n$. Používa sa na opis najhoršieho prípadu.
$\Omega(f(n))$: Algoritmus sa vykonáva za čas, ktorý nie je menší ako konštanta, násobená $f(n)$, pri veľkých $n$. Používa sa na opis najlepšieho prípadu.
$\Theta(f(n))$: Algoritmus sa vykonáva za čas, úmerný $f(n)$, pri veľkých $n$. Používa sa na opis stredného prípadu alebo keď najlepší a najhorší prípad majú rovnaký asymptotický poriadok.

Najčastejšie sa používa Veľké $O$ na opis hornej hranice času vykonávania, čo je dôležité pre pochopenie škálovateľnosti algoritmu v najhoršom scenári.

Ignorovanie konštánt a nižších členov: Pri určovaní asymptotiky sa ignorujú konštantné násobitele a členy nižšieho rádu, pretože pri veľkých $n$ dominuje funkcia s najväčším exponentom. Napríklad, pre $3n^2 + 5n + 10$, bude asymptotika $O(n^2)$.

Typické asymptotické triedy (v poradí rastu zložitosti):

$O(1)$: Konštantná zložitosť (čas vykonania nezávisí od $n$).
$O(\log n)$: Logaritmická zložitosť (čas vykonania rastie veľmi pomaly s rastom $n$, charakteristická pre algoritmy binárneho vyhľadávania).
$O(n)$: Lineárna zložitosť (čas vykonania je priamo úmerný $n$, charakteristická pre jednoduché prehľadávanie).
$O(n \log n)$: Lineárno-logaritmická zložitosť (charakteristická pre efektívne algoritmy triedenia, ako sú Quick Sort alebo Merge Sort).
$O(n^2)$: Kvadratická zložitosť (čas vykonania rastie s druhou mocninou $n$, charakteristická pre jednoduché algoritmy triedenia, ako je Bubble Sort).
$O(n^c)$ (pre $c > 1$): Polynomiálna zložitosť.
$O(c^n)$ (pre $c > 1$): Exponenciálna zložitosť (čas vykonania rastie veľmi rýchlo s rastom $n$, charakteristická pre prehľadávanie všetkých možných kombinácií).
$O(n!)$: Faktorálna zložitosť (najvyššia trieda zložitosti, rastie mimoriadne rýchlo).

Na určenie asymptotiky cyklických štruktúr:

Sekvencálne bloky kódu: Zložitosť blokov sa sčíta. $O(A+B) = O(\max(A, B))$.
Vložené cykly: Počet iterácií sa násobí. Cykly s $n$ iteráciami, v ktorých je ďalší cyklus s $m$ iteráciami, majú zložitosť $O(n \times m)$. Ak je $m=n$, zložitosť je $O(n^2)$.
Cykly so znižovaním veľkosti vstupných dát: Napríklad delenie na 2 pri každej iterácii vedie k logaritmickej zložitosti ($O(\log n)$).

Príklad:

Jednoduché prehľadávanie poľa:

# Počítanie základných operácií (porovnania, priradenia)
# V tomto prípade je hlavná operácia porovnanie v cykle
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 priradenie (mimo cyklu)
    for i in range(1, len(arr)): # Cyklus sa vykoná $len(arr) - 1$ krát
        # Vo vnútri cyklu:
        # 1 porovnanie (if arr[i] > max_val)
        # potenciálne 1 priradenie (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Ak je veľkosť poľa $n = \texttt{len(arr)}$, cyklus sa vykoná $n-1$ krát. V každej iterácii sa vykoná konštantný počet operácií. Celkový počet operácií je úmerný $n$. Asymptotická zložitosť: $O(n)$.

Príklad: Triedenie vložením (Insertion Sort)

# Počítanie základných operácií
# Hlavné operácie: porovnania a priradenia/presuny prvkov
def insertion_sort(arr):
    # Vonkajší cyklus sa vykoná $n-1$ krát
    for i in range(1, len(arr)):
        key = arr[i] # 1 priradenie
        j = i - 1 # 1 priradenie
        # Vnútorný cyklus sa v najhoršom prípade vykoná $i$ krát
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 priradenie (presun)
            j -= 1 # 1 odčítanie a 1 priradenie
        arr[j + 1] = key # 1 priradenie

Vonkajší cyklus sa vykoná $n-1$ krát. V najhoršom prípade (pole je v opačnom poradí) sa vnútorný cyklus v priemere vykoná $i/2$ krát (alebo až $i$ krát). Celkový počet operácií vo vnútornej slučke pre všetky iterácie vonkajšej je: $1 + 2 + ... + (n-1) \approx n^2/2$. Asymptotická zložitosť je: $O(n^2)$ v najhoršom a priemernom prípade, $O(n)$ v najlepšom prípade (keď je pole už zoradené). Pri odhade zložitosti sa zvyčajne uvažuje najhorší prípad (Veľké $O$).

Ako odhadnúť zložitosť algoritmu alebo určiť jeho asymptotu?