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í

Party

Představte si, že plánujete party pro \(n\) lidí. Jak dlouho budou trvat následující činnosti (v závislosti na \(n\))?

  1. Úklid domu před party.
  2. Nandat každému porci jídla na talíř.
  3. Nandat každému polévku, hlavní jídlo a dezert.
  4. Každý s každým si podá ruku.

Při zvaní hostů napíšete do pozvánky, že každý z nich může pozvat další dva kamarády. Tuto pozvánku pošlete dvěma svým kamarádům. Kolik lidí dorazí v závislosti na \(k\) udávajícím, jak vzdálené kamarády pozvete (\(k=1\) moji dva kamarádi, \(k=2\) kamarádi mých kamarádů, …)?

Asymptotická notace

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í