Naučte se

Notace (známější pod označením O-notace) se používá v matematice k porovnávání asymptotického chování členů posloupností, či k porovnání rychlosti růstu dvou posloupností. Vyjádříme pomocí ní rychlost růstu poslopnosti v nekonečnu. Tato notace se velmi často využívá v informatice k porovnávání časových a paměťových složitostí algoritmů. U každého algoritmu jsme schopni určit horní odhad složitosti, dolní odhady (až na triviální -- velikost vstupu, výstupu) jsou složitější.

Byla vynalezena Paulem Bachmannem a Edmundem Landauem (německý matematik, 1877 – 1938) a dalšími.

Často se můžete setkat se zápisem an = O(bn), který není příliš šťastný vzhledem k tomu, že nejde o rovnost. Lepší je ho chápat ve smyslu an ∈ O(bn).

Asymptoticky rovné ∼

Vyjadřuje, že posloupnosti $(a_n)_{n=1}^\infty$ a $(b_n)_{n=1}^\infty$ mají stejné asymptotické chování v nekonečnu, tedy mají stejnou množinu hromadných bodů. Což znamená, že hodnoty velkých indexů posloupnosti jsou takřka stejné a liší se pouze multiplikativními a aditivními konstantami.

Řekneme, že an ∼ bn se pro velká n chovají stejně, právě když existuje posloupnost $(c_n)_{n=1}^\infty$ a $n_0$ ∈ ℕ taková, že

  • $\displaystyle\lim_{n\to\infty} c_n = 1$ a $a_n =: c_n b_n$, pro každé $n ≥ n_0$.

Pokud je bn kladné, tzn. bn > 0 pak lze definici přeformulovat do praktičtějšího tvaru

  • $\displaystyle\lim_{n\to\infty} \frac{a_n}{b_n} = 1$.

Tohle je častý předpoklad, protože nebudete mít zápornou dobu běhu programu.

Rychlost růstu O()

Horní asymptotický odhad, vyjadřuje, že posloupnost an neroste rychleji než bn, až na konstantu.

Značení an ∈ O(bn) říká, že je $a_n$ je asymptoticky omezená $b_n$, právě když existuje c < 0 a $n_0$ ∈ ℕ taková, že

  • $|a_n| ≤ c|b_n|$ pro všechna $n ≥ n_0$.

Alternativně platí $a_n ∈ O(b_n) ⇔ (\frac{a_n}{b_n})_{n=1}^\infty$ je omezená

Vlastnosti

Θ je silnější podmínka, než O a Ω a říká nám, že Θ je současně asymptotickou horní i dolní mezí.

  • f(n) ∈ Θ(g(n)) ⇒ f(n) ∈ O(g(n))
  • f(n) ∈ Θ(g(n)) ⇒ f(n) ∈ Ω(g(n))
  • f(n) ∈ Θ(g(n)) ⇔ f(n) ∈ O(g(n)) ∧ f(n) ∈ Ω(g(n))

 

f(n) ∈ Θ(g(n)) ⇒

Pozor, v tvrzení opačná implikace neplatí. Lze nalézt funkce f(n), g(n) takové, že f(n) = Θ(g(n)), ale limita jejich podílu neexistuje.

 

Chceme-li asymptotickou těsnou mez vyjádřit ekvivalentním tvrzením, pak lze říci jen
f(n) ∈ Θ(g(x)) ⇔ podíly

Zákony asymptotické aritmetiky

Tranzitivita
  • f(n) ∈ Θ(g(n)) ∧ g(n) ∈ Θ(h(n)) ⇒ h(n) ∈ Θ(f(n))
  • f(n) ∈ O(g(n)) ∧ g(n) ∈ O(h(n)) ⇒ f(n) ∈ O(h(n))
  • (podobně pro Ω, o, ω)
Reflexivita
  • f(n) ∈ O(f(n))
  • f(n) ∈ Ω(f(n))
  • f(n) ∈ Θ(f(n))
Symetrie
  • f(n) ∈ Θ(g(n)) ⇔ g(n) ∈ Θ(f(n))

Transpoziční symetrie
  • f(n) ∈ O(g(n)) ⇔ g(n) ∈ Ω(f(n))
  • f(n) ∈ o(g(n)) ⇔ g(n) ∈ ω(f(n))

Související