— Složitost —

Složitost

Složitostí míníme závislost na “velikosti” vstupních dat. Časová složitost nechť je funkce f(|D|) udávající počet kroků algoritmu. Intuitivně: nejsou podstatné

multiplikativní a aditivní konstanty, podstatná je “kategorie”, kam algoritmus patří.

Krokem algoritmu myslíme operaci stroje, kterou zvládneme v konstantním čase. Pro nás:

• aritmetické operace

• porovnání dvou hodnot

• přiřazení (ovšem pouze jednoduchých typů — skalárů)

Třídy složitosti:

• f(n) = cn (lineární): hledání maxima posloupnosti

• f(n) = cn logn: vytvoření binární haldy z n prvků

• f(n) = cn^{2} (kvadratický): bubble sort

• f(n) = cn^{3} (kubický): vytisknout všechny trojice z n vstupních čísel

• f(n) = 2^{n} (exponenciální): vytisknout všechny podmnožiny z množiny n prvků

• f(n) = n!: problém obchodního cestujícího

Asymptotická složitosti

Intuitivně: zkoumá chování algoritmu na “velkých datech”, t.j. nebere v úvahu multiplikativní a aditivní konstanty, a zařazuje algoritmy do “kategorií”’.

Rigorózně:

f(n) je asymptoticky menší nebo rovno g(n):

f(n) = O(g(n)) ⟺ ∃ c > 0, ∃ n_{0} > 0, ∀n ≥ n_{0} : 0 ≤ f(n) ≤ cg(n)

(Znaménko “=” nelze brát ve výrazu f(n) = O(g(n)) doslova, spíše je zde ve významu f(n) ∈ O(g(n)).)

f(n) je asymptoticky větší nebo rovno g(n):

f(n) = Ω(g(n)) ⟺ ∃ c > 0, ∃ n_{0} > 0, ∀n ≥ n_{0} : 0 ≤ cg(n) ≤ f(n)

f(n) je asymptoticky stejné jako g(n):

f(n) = Θ(g(n)) ⟺ ∃ c > 0, ∃ n_{0} > 0, ∀n ≥ n_{0} : 0 ≤ c_{1}g(n) ≤ f(n) ≤ c_{2}g(n)

f(n) = Θ(g(n)) ⟺ f(n) = O(g(n)) ∧ f(n) = Ω(g(n))

(Asymptotická rovnost je vyhrazena pro lim_{n→∞} f(n)/g(n) = 1 .)

Pro úplnost:

f(n) je asymptoticky ostře menší g(n):

f(n) = o(g(n)) ⟺ ∀c > 0, ∃ n_{0} > 0, ∀n ≥ n_{0} : 0 ≤ f(n) < cg(n)

(Zásadní rozdíl je v kvantifikátoru konstanty! Jinak bychom ostrou nerovnost získali pouhým snížením konstanty.)

f(n) je asymptoticky ostře větší g(n):

f(n) = ω(g(n)) ⟺ ∀c > 0, ∃ n_{0} > 0, ∀n ≥ n_{0} : 0 ≤ cg(n) < f(n)

/L:1.616 1