Algoritmizace – 3. cvičení

Složitost ($\mathcal{O}$)

Definice

Nechť $f, g: \mathbb{N} \to \mathbb{R}^+$.

• $f \in \mathcal{O}(g) \iff \exists c > 0, \exists n_0: \forall n > n_0: f(n) \leq c \cdot g(n)$.
• $f \in \mathcal{\Omega}(g) \iff \exists c > 0, \exists n_0: \forall n > n_0: f(n) \geq c \cdot g(n)$.
• $f \in \mathcal{\Theta}(g) \iff f \in \mathcal{O}(g) \wedge f \in \mathcal{\Omega}(g)$.

Úlohy

Nechť $f, g: \mathbb{N} \to \mathbb{R}^+$. Dokažte nebo vyvraťte tato tvrzení:

1. $n^2 \in \mathcal{O}(n^3)$,
2. $n^3 \in \mathcal{O}(n^2)$
3. $f \in \mathcal{O}(g) \implies g \in \mathcal{O}(f)$,
4. $f \in \mathcal{O}(g) \implies g \in \mathcal{\Omega}(f)$,
5. $f \in \mathcal{O}(g) \vee g \in \mathcal{O}(f)$,

Vzorová řešení a moje poznámky (ne úplně vzorové řešení, ale všechny hlavní myšlenky by tam měly být).