Korektnost a složitost algoritmu

Note	Parciální a totální korektnost, důkazy korektnosti. Asymptotická složitost, O-notace. Zdůvodnění korektnosti a složitosti základních algoritmů (např. řadicí algoritmy, binární vyhledávání). IB002, IB102/IB107

Algoritmy

Algoritmus je posloupnost příkazů, kterou je schopen provést Turingův stroj nebo jeho ekvivalent.

Vstupní podmínka

Ze všech možných vstupů pro daný algoritmus vymezujeme ty, pro které je algoritmus definován.

Výstupní podmínka

Pro každý vstup daného algoritmu splňující vstupní podmínku určuje, jak má vypadat odpovídající výsledek.

Invariant cyklu

Invariant cyklu je tvrzení cyklu v algoritmu, které platí před a po vykonání každé jeho iterace.

Přesněji:

# check invariant holds
while condition:
    # check (condition and invariant) holds
    # do, what must be done
# check (!condition and invariant) holds

Délka výpočtu

Délka výpočtu konkrétního algoritmu na daném vstupu odpovídá počtu elementárních operací, ze kterých se výpočet skládá.

Note	Co je elementární operace? Záleží na algoritmu.

Korektnost

Algoritmus je parciálně korektní, pokud pro každý vstup, který splňuje vstupní podmínku a algoritmus na něm skončí, výstup splňuje výstupní podmínku.

Algoritmus je úplný (konvergentní), pokud pro každý vstup, jenž splňuje vstupní podmínku, výpočet skončí.

Algoritmus je totálně korektní, právě když je parciálně korektní a úplný.

Dokazovaní korektnosti

U iterativního algoritmu

Pro každý cyklus algoritmu stanovíme invariant. Začínáme od nejvíce zanořených cyklů. Pro každý invariant dokážeme konečnost cyklu a jeho efekt. Činíme tak ve třech fázích:

inicializace — platnost invariantu před vykonáním cyklu.
iterace — invariant platí před i po každé iteraci,
ukončení — cyklus skončí a platný invariant garantuje požadovaný efekt cyklu.

U rekurzivního algoritmu

Pomocí matematické indukce.

Složitost

Složitost vyjadřuje náročnost algoritmu na zdroje výpočtu (čas, paměť, počet procesorů, atd.).

Časová složitost algoritmu: Funkce $f : N \to N$ taková, že pro vstup délky $n$ daný algoritmus provede výpočet o délce nejvýše $f (n)$ . Obvykle vyjadřujeme asymptoticky.

Asymptotická notace

Geometricky, asymptota křivky je přímka taková, že její vzdálenost od křivky se limitně blíží 0 v nekonečnu.

Note	Podstatné je, že asymptota je od určitého bodu nad nebo pod svojí křivkou a setkává se s ní až v nekonečnu.

$O (g)$ notace

Je množina funkcí rostoucích stejně rychle jako $g$ , nebo pomaleji.

O (g) = {f : (\exists c, n_{0} \in N^{+}) (\forall n \geq n_{0}) (f (n) \leq c \cdot g (n))}

Note	Geometricky, jsou to všechny funkce $f$ , kterou jsou od nějakého bodu pod $c \cdot g$ .

$Ω (g)$ notace

Je množina funkcí rostoucích stejně rychle jako $g$ , nebo rychleji.

Ω (g) = {f : (\exists c, n_{0} \in N^{+}) (\forall n \geq n_{0}) (f (n) \geq c \cdot g (n))}

Note	Geometricky, jsou to všechny funkce $f$ , kterou jsou od nějakého bodu nad $c \cdot g$ .

$Θ (g)$ notace

Je množina funkcí rostoucích stejně rychle jako $g$ .

Θ (g) = O (g) \cap Ω (g)

Note	Existuje i $o$ a $ω$ , kde je rozdíl v tom, že $n_{0} = 0$ .

Vlastnosti

Vlastnost	Formulka	Poznámka
Tranzitivita	$f \in Θ (g) \land g \in Θ (h) ⟹ f \in Θ (h)$	Stejně pro $O, Ω$
Reflexivita	$f \in Θ (f)$	Stejně pro $O, Ω$
Symetrie	$f \in Θ (g) ⟺ g \in Θ (f)$
Transpozice	$f \in O (g) ⟺ g \in Ω (f)$

Vlastnost

Formulka

Poznámka

Tranzitivita

$f \in Θ (g) \land g \in Θ (h) ⟹ f \in Θ (h)$

Stejně pro $O, Ω$

Reflexivita

$f \in Θ (f)$

Stejně pro $O, Ω$

Symetrie

$f \in Θ (g) ⟺ g \in Θ (f)$

Transpozice

$f \in O (g) ⟺ g \in Ω (f)$

Korektnost a složitost základních algoritmů

Binární vyhledávání

def binsearch(x: int, S: List[int]) -> int:
    f = 0
    l = len(S) - 1
    i = (f + l) // 2
    while f != l:
        if S[i] == x:
            return i
        if x < S[i]:
            l = i
        else:
            f = i
        i = (f + l) // 2
    return -1

Invariant: Na začátku každé iterace platí, že jestli se $x$ nalézá v $S$ , tak se nalézá mezi pozicemi $f$ (first) a $l$ (last).
Inicializace: Na začátku je $i = ⌊ \frac{f + l}{2} ⌋$ , takže tvrzení platí.
Iterace: Pokud $x \neq = S [i]$ a $x < S [i]$ , nachází se $x$ mezi pozicemi $f$ a $i$ . Pokud $x > S [i]$ , pak mezi $i$ a $l$ . Pokud je vrácena hodnota $i$ , invariant také platí.
Ukončení: Cyklus končí buď protože $S [i] = x$ , nebo protože $f = l \neq = x$ .
Složitost: $O (l o g_{2} (n))$

Řadicí algoritmy

Algoritmus Složitost Poznámka

Algoritmus	Složitost	Poznámka
Bubble sort	$Θ (n^{2})$	invariant: rozsah `a[n-i-1:]` je ve finální pozici
Insert sort	$Θ (n^{2})$
Merge sort	$Θ (n \cdot l o g_{2} (n))$
Quick sort	$Θ (n^{2})$	očekávaná složitost $Θ (n \cdot l o g_{2} (n))$
Heap sort	$Θ (n \cdot l o g_{2} (n))$
Counting sort	$Θ (n + k)$	hodnoty z intervalu 0..k
Radix sort	$Θ (d (n + k))$	čísla z d číslic, číslicové řazení $Θ (n)$
Bucket sort	$Θ (n) + \sum_{n = 0}^{n - 1} O (n_{i}^{2})$

Bubble sort

$Θ (n^{2})$

invariant: rozsah a[n-i-1:] je ve finální pozici

Insert sort

$Θ (n^{2})$

Merge sort

$Θ (n \cdot l o g_{2} (n))$

Quick sort

$Θ (n^{2})$

očekávaná složitost $Θ (n \cdot l o g_{2} (n))$

Heap sort

$Θ (n \cdot l o g_{2} (n))$

Counting sort

$Θ (n + k)$

hodnoty z intervalu 0..k

Radix sort

$Θ (d (n + k))$

čísla z d číslic, číslicové řazení $Θ (n)$

Bucket sort

$Θ (n) + \sum_{n = 0}^{n - 1} O (n_{i}^{2})$