Landauova notace

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 a_n = O(b_n), který není příliš šťastný vzhledem k tomu, že nejde o rovnost. Lepší je ho chápat ve smyslu a_n ∈ O(b_n).

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 a_n ∼ b_n 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 b_n kladné, tzn. b_n > 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 a_n neroste rychleji než b_n, až na konstantu.

Značení $a_n ∈ O(b_n)$ ří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)) ⇒ \lim\limits_{n \to \infty} \frac{f(n)}{g(n)} ∈ (0, ∞)$

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 $\frac{f(n)}{g(n)}$ a $\frac{g(n)}{f(n)}$ jsou omezené

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))$