Algoritmizace – 3. cvičení
Složitost (O)
Definice
Nechť f,g:N→R+.
- f∈O(g)⟺∃c>0,∃n0∈N:∀n>n0:f(n)≤c⋅g(n).
- f∈Ω(g)⟺∃d>0,∃m0∈N:∀m>m0:f(m)≥d⋅g(m).
- f∈Θ(g)⟺f∈O(g)∧f∈Ω(g).
Úlohy
Nechť f,g:N→R+. Dokažte nebo vyvraťte tato tvrzení:
- n2∈O(n3),
- n3∈O(n2),
- f∈O(g)⟹g∈O(f),
- f∈O(g)⟹g∈Ω(f),
- f∈O(g)∨g∈O(f).
Vzorová řešení