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, f_1, f_2, g: \mathbb{N} \to \mathbb{R}^+\). Dokažte nebo vyvraťte tato tvrzení:

  1. \(f_1 \in \mathcal{O}(g) \wedge f_2 \in \mathcal{O}(g) \implies f_1 + f_2 \in \mathcal{O}(g)\),

  2. \(f \in \mathcal{O}(g) \implies \frac1f \in \mathcal{O}\left(\frac1g\right)\).

Úlohy se seznamem čísel

Je dán seznam čísel.

  1. Zjistěte, jestli jsou všechna čísla navzájem různá.

  2. Vypište všechna opakující se čísla (ale každé jen jednou).

  3. Najděte dvojici s co nejmenším rozdílem.

Jaká je časová složitost vašich řešení (vzhledem k počtu čísel \(N\))?

Umíte předchozí úkoly vyřešit efektivněji, pokud víte, ze všechna zadaná čísla leží v předem daném rozsahu \(0\) až \(R\) (např. \(0\) až \(100\))? Jaká pak bude časová složitost vašeho řešení vzhledem k \(N\) a \(R\)?