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

1. Asymptotická horní mez ($f$ roste nejvýše tak rychle jako $g$) … $O(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$) … $\Theta (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)$
   • $(\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 (f roste pomaleji než $g$) … $o(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 NTS s prostorovou složitostí $O(n^k)$, pak je také rozhodován deterministickým TS s prostorovou složitostí $O(n^{2k})$. Čili pořád si zachová polynomickou časovou složitost.

• Pro každou nekonstantní funkce $f:\mathbb{N}\to \mathbb{N}$ splňující $f(n)\le n$ platí: NPSPACE($f(n)$) $\subseteq$ PSPACE($f(n{)}^2$)

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