Informace níže se nevztahují k současnému semestru.
Stránka pro aktuální semestr je zde.
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 \in \mathbb{N}: \forall n > n_0: f(n) \leq c \cdot g(n)\).
- \(f \in \mathcal{\Omega}(g) \iff \exists d > 0, \exists m_0 \in \mathbb{N}: \forall m > m_0: f(m) \geq d \cdot g(m)\).
- \(f \in \mathcal{\Theta}(g) \iff f \in \mathcal{O}(g) \wedge f \in \mathcal{\Omega}(g)\).
Úlohy na procvičení
Nechť \(f, g: \mathbb{N} \to \mathbb{R}^+\). Dokažte nebo vyvraťte tato tvrzení:
- \(n^2 \in \mathcal{O}(n^3)\),
- \(n^3 \in \mathcal{O}(n^2)\),
- \(f \in \mathcal{O}(g) \implies g \in \mathcal{O}(f)\),
- \(f \in \mathcal{O}(g) \implies g \in \mathcal{\Omega}(f)\),
- \(f \in \mathcal{O}(g) \vee g \in \mathcal{O}(f)\).