Jak odhadnout složitost algoritmu nebo určit jeho…

Hodnocení složitosti algoritmu se provádí pomocí asymptotické analýzy, která umožňuje popsat efektivitu algoritmu v závislosti na velikosti vstupních dat ($n$). Hlavní kroky:

Definice základních operací: Vyberou se operace, jejichž doba běhu závisí podstatně na $n$ (například porovnání, přiřazení, aritmetické operace).
Počet operací: Vypočítá se počet základních operací v závislosti na $n$. Může jít o přesnou formuli nebo odhad.
Určení asymptotické třídy: Používají se označení Velké O ($O$), Omega ($\Omega$) a Theta ($\Theta$) pro popis horního, dolního a přesného asymptotického chování.

$O(f(n))$: Algoritmus běží v čase, který nepřekračuje konstantu násobenou $f(n)$ pro velká $n$. Používá se pro popis nejhoršího případu.
$\Omega(f(n))$: Algoritmus běží v čase, který je nejméně konstantou násobenou $f(n)$ pro velká $n$. Používá se pro nejlepší případ.
$\Theta(f(n))$: Algoritmus běží v čase úměrném $f(n)$ pro velká $n$. Používá se pro průměrný případ nebo když nejlepší a nejhorší případy mají stejný asymptotický řád.

Nejčastěji používané je Velké O pro popis horní hranice doby běhu, což je důležité pro pochopení škálovatelnosti algoritmu v nejhorším scénáři.

Ignorování konstant a nižších členů: Při určování asymptotiky jsou ignorovány konstantní násobky a členy nižšího řádu, protože při velkých $n$ dominuje funkce s největším exponentem. Například pro $3n^2 + 5n + 10$ bude asymptotika $O(n^2)$.

Typické asymptotické třídy (v pořadí vzrůstající složitosti):

$O(1)$: Konstantní složitost (doba běhu nezávisí na $n$).
$O(\log n)$: Logaritmická složitost (doba běhu roste velmi pomalu s růstem $n$, charakteristické pro binární vyhledávání).
$O(n)$: Lineární složitost (doba běhu přímo úměrná $n$, charakteristické pro jednoduché prohledávání).
$O(n \log n)$: Lineárně-logaritmická složitost (charakteristická pro efektivní třídicí algoritmy, jako je Quick Sort nebo Merge Sort).
$O(n^2)$: Kvadratická složitost (doba běhu roste s druhou mocninou $n$, charakteristická pro jednoduché třídicí algoritmy, jako je Bubble Sort).
$O(n^c)$ (pro $c > 1$): Polynomiální složitost.
$O(c^n)$ (pro $c > 1$): Exponenciální složitost (doba běhu roste velmi rychle s růstem $n$, charakteristická pro prohledávání všech možných variant).
$O(n!)$: Faktoriální složitost (nejvyšší třída složitosti, roste extrémně rychle).

Pro určení asymptotiky cyklických struktur:

Sekvenční bloky kódu: Složitost bloků se sčítá. $O(A+B) = O(\max(A, B))$.
Vnořené smyčky: Počet iterací se násobí. Smyčka s $n$ iteracemi uvnitř které je jiná s $m$ iteracemi má složitost $O(n \times m)$. Pokud $m=n$, složitost je $O(n^2)$.
Smyčky s redukcí velikosti vstupních dat: Například dělení na 2 při každé iteraci vede k logaritmické složitosti ($O(\log n)$).

Příklad:

Jednoduché prohledávání pole:

# Přepočet základních operací (porovnání, přiřazení)
# Hlavní operace - porovnání v cyklu
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 přiřazení (mimo cyklus)
    for i in range(1, len(arr)): # Provádí se $n-1$ krát
        # Uvnitř cyklu:
        # 1 porovnání (if arr[i] > max_val)
        # potenciálně 1 přiřazení (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Pokud je velikost pole $n = \texttt{len(arr)}$, cyklus se provádí $n-1$ krát. V každé iteraci se provádí konstantní počet operací. Celkový počet operací je úměrný $n$. Asymptotická složitost: $O(n)$.

Příklad: Vkládací třídění (Insertion Sort)

# Přepočet základních operací
# Hlavní operace: porovnání a přiřazení/přesuny prvků

def insertion_sort(arr):
    # Vnější cyklus se provádí $n-1$ krát
    for i in range(1, len(arr)):
        key = arr[i] # 1 přiřazení
        j = i - 1 # 1 přiřazení
        # Vnitřní cyklus se v nejhorším případě provádí $i$ krát
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 přiřazení (přesun)
            j -= 1 # 1 odečtení a 1 přiřazení
        arr[j + 1] = key # 1 přiřazení

Vnější cyklus se provádí $n-1$ krát. V nejhorším případě (pole je seřazeno v opačném pořadí) se vnitřní cyklus provádí v průměru $i$ krát (nebo až $i$ krát). Celkový počet operací ve všech iteracích vnějšího cyklu: $1 + 2 + ... + (n-1) \approx n^2/2$. Asymptotická složitost: $O(n^2)$ v nejhorším a průměrném případě, $O(n)$ v nejlepším případě (pole je již seřazeno). Při odhadu složitosti se obvykle uvažuje nejhorší případ (Velké $O$).

Jak odhadnout složitost algoritmu nebo určit jeho asymptotu?