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í

Vážení kuliček

Máme 7 stejně vypadajících zlatých koulí, ale jedna z nich je vadná. Je totiž vyrobená z kočičího zlata a tedy je lehčí než ty ostatní (všechny ostatní váží stejně). Naším úkolem je tuto vadnou kouli najít.

Máme k dispozici rovnoramenné váhy, kde na každou misku můžeme dát několik koulí najednou a váhy nám řeknou, která miska je lehčí. Pokud jsou obě misky stejně těžké, váhy zůstanou stát.

Jelikož nechceme váhy zbytečně opotřebit, tak hledáme způsob jak najít vadnou kouli na co nejmenší počet vážení. Zkuste také zdůvodnit, že na méně vážení lehčí kuličku najít nelze.

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ů, …)?