Složitost algoritmu (časová a paměťová)

1. Asymptotická horní mez ($f$ roste nejvýše tak rychle jako $g$)
   • Pro libovolné funkce $f,g:\mathbb{N}\to \mathbb{N}$ znamená zápis $f\in O(g)$ toto: $(\exists k\in \mathbb{N})(\exists n_0\in \mathbb{N})(\forall n\ge n_0):f(n)\le k\ast g(n)$
2. Asymptotická oboustranná mez ($f$ roste stejně rychle jako $g$)
   • Pro libovolné funkce $f,g:\mathbb{N}\to \mathbb{N}$ zápis $f\in \Theta (g)$ znamená, že $f\in O(g)$ a $g\in O(f)$
   • Zápis $(\exists k_1\in \mathbb{N})(\exists k_2\in \mathbb{N})(\exists n_0\in \mathbb{N})(\forall n\ge n_0):k_1\ast g(n)\le f(n)\le k_2\ast g(n)$
3. Asymptotická ostrá horní mez ($frostepomalejine\check{z}$g$)
   • Pro libovolné funkce $f,g:\mathbb{N}\to \mathbb{N}$ zápis $f\in o(g)$ znamená, že $(\forall k\in \mathbb{N})(\exists n_0\in \mathbb{N})(\forall n\ge n_0):k\ast f(n)<g(n)$

Definice časové složitosti

• Velikost vstupu TS rozumíme počet buněk (vstupní pásky), které daný vstup zabírá.
• Délka výpočtu TS $M$ pro konkrétní vstup se definuje jako počet provedení instrukcí, které $M$ pro daný vstup vykoná, než se zastaví.
• Časovou složitostí TS $M$ rozumíme funkci $T_M:\mathbb{N}\to \mathbb{N}$, kde $T_M(n)$ znamená délku výpočtu $M$ nad vstupem velikosti $n$ v nejhorším případě; tedy $T_M(n)=\max \{k\mid k\text{ je deˊlka vyˊpocˇtu }M\text{ nad (neˇjakyˊm) vstupem velikosti }n\}$

Definice paměťové složitosti

• Velikostí paměti TS $M$ potřebné při výpočtu pro konkrétní vstup rozumíme číslo $p+1$, kde $p$ je maximum z adres buněk, jež jsou během výpočtu (nad daným vstupem) navštíveny.
• Paměťovou složisostí TS $M$ rozumíme funkci $S_M:\mathbb{N}\to \mathbb{N}$, kde $S_M(n)$ znamená velikost potřebné paměti při výpočtu $M$ nad vstupem velikosti $n$ v nejhorším případě; tedy $S_M(n)=\max \{k\mid k\text{ je velikost pameˇti potrˇebneˊ prˇi vyˊpocˇtu }M\text{ nad vstupem velikosti }n\}$

• Savitchova věta
  • Je-li problém $P$ rozhodován nedeterministickým TS s prostorovou složitostí $O(n^k)$, pak je také rozhodován deterministickým TS s prostorovou složitostí $O(n^{2k})$

Navigace

Předchozí: Riceova věta Následující: Třída P, třída NP, důvody jejich zavedení, jejich vzájemný vztah Celý okruh: 1. Teoretické základy informatiky