Složitost, asymptotická notace (\(\mathcal{O}, \mathcal{\Omega}, \mathcal{\Theta}\))
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í
Asymptotická notace
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)\).