Príklady použitia

  • $1.5N^2 -0.5N = O\left( N^2 \right)$.
  • $47N \log N = O\left( N^2 \right)$.
  • $N \log N + 1\,000\,047N = \Theta\left( N \log N \right)$.
  • Všetky polynómy stupňa $k$ sú $O\left( N^k \right)$.
  • Časová zložitosť algoritmu z Príkladu 2 je $\Theta\left( N^2 \right)$.
  • Ak nejaký algoritmus je $O\left( N^2 \right)$, tak je aj $O\left( N^5 \right)$.
  • Každý triediaci algoritmus založený na porovnávaní triedených prvkov je $ \Omega\left( N \log N \right)$.
  • MergeSort spustený na poli s $N$ prvkami spraví rádovo $N \log N$ porovnaní. Preto jeho časová zložitosť je $\Theta\left( N \log N \right)$. Ak uveríme aj predchádzajúcemu tvrdeniu, dostávame, že MergeSort je optimálny všeobecný triediaci algoritmus.
  • Algoritmus z Príkladu 2 potrebuje $\Theta\left( N \right)$ bajtov pamäte.
  • Funkcia udávajúca počet tvojich zubov v závislosti od času je $O\left( 1 \right)$.
  • Algoritmus, ktorý hrá šach tak, že vyskúša úplne všetky možnosti, je $O\left( 1 \right)$, lebo strom možností, ktorý musí prezrieť, je konečný. (Samozrejme, v tomto prípade sa v našom $O\left( 1 \right)$ skrýva neuveriteľne veľká konštanta.)
  • Tvrdenie "Časová zložitosť tohto algoritmu je aspoň $O\left( N^2 \right)$" nemá zmysel. (Vlastne hovorí: "Časová zložitosť tohto algoritmu je aspoň nanajvýš rádovo kvadratická." Huh?) Jeho autor pravdepodobne chcel povedať: "Časová zložitosť tohto algoritmu je $\Omega\left( N^2 \right)$".

Keď neformálne hovoríme o zložitosti algoritmu, namiesto formálneho zápisu $\Theta\left( f\left( n \right)\right)$ môžeme jednoducho povedať, do akej triedy funkcii $f$ patrí. Napr. ak $f(N) = \Theta(N)$, hovoríme, že algoritmus je lineárny. Ďalšie príklady:

  • $f\left( N \right)= \Theta\left( \log N \right)$: logaritmický
  • $f\left( N \right)= \Theta\left( N^2 \right)$: kvadratický
  • $f\left( N \right)= \Theta\left( N^3 \right)$: kubický
  • $f\left( N \right)= O\left( N^k \right)$ pre nejaké $k$: polynomiálny
  • $f\left( N \right)= O\left( c^N \right)$ a $f\left( N \right)= \Omega\left( d^N \right)$ pre nejaké $c,d > 1$: exponenciálny

Pri úlohách o grafoch zložitosť $\Theta\left( N + M \right)$ voláme "lineárna od veľkosti grafu".

Späť Ďalej