Ondřej Čepek

Algoritmy a datové struktury I

Přepsal Petr Baudiš v ak. roce 2004/2005

“If I am given a formula, and I am ignorant of its meaning, it cannot teach me anything. But if I already know it, what does the formula teach me?”

— ST. AUGUSTINE

◯^{c} 2004/2005 Ondřej Čepek, Petr Baudiš Verze 1/L:1.616. Tato verze není garantována, nemusí být kompletní a může obsahovat chyby. Aktuální verzi vždy najdete na http://math.or.cz/. Sazba v programu TEX.

Ondřej Čepek — Algoritmy a datové struktury I 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)

Stromy — Ondřej Čepek — Algoritmy a datové struktury I

Stromy

Dynamické množiny

Dynamická množina: Množinu prvků, která se mění v čase.

Prvek dynamické množiny

• přístup přes ukazatel

• obsahuje: klíč, ukazatel na další prvky, příp. další data

Operace na dynamické množině

Nechť S je dynamická množina prvků, k je hodnota klíče a x je ukazatel na prvek.

Slovníkové operace:

Find(S, k) Vrací ukazatel na prvek v S s klíčem k, pokud existuje, jinak vrací nil

Insert(S, x) Do S vloží prvek, na který ukazuje x

Delete(S, x) Z S odstraní prvek, na který ukazuje x

Min(S) Vrátí ukazatel na prvek S s minimálním klíčem

Max(S) Vrátí ukazatel na prvek S s maximálním klíčem

Succ(S, x)

Vrátí ukazatel na v pořadí další prvek za x v S podle uspořádání klíčů (pokud x obsahuje max. klíč, vrátí nil)

Prec(S, x)

Vrátí ukazatel na v pořadí předchozí prvek za x v S podle uspořádání klíčů

Binární vyhledávací stromy

Dynamická datová struktura podporující všechny uvedené operace. Binární strom: Každý prvek má tři ukazatele: rodič, levý, pravý. V BVS pak pro každý prvek x platí:

(i) Každý prvek v levém podstromu má klíč ≤ klíč x (ii) Každý prvek v pravém podstromu má klíč ≥ klíč x

… implementace operací…

Červeno–černé stromy

...definice...

LEMMA 1:

Nechť x je libovolný uzel. Pak podstrom s kořenem x obsahuje alespoň 2^{bh(x)} − 1 interních uzlů.

DŮKAZ:

Indukcí podle h(x):

Ondřej Čepek — Algoritmy a datové struktury I Stromy —

(i) h(x) = 0: Podstrom s kořenem x na 2^{0} − 1 = 1 − 1 = 0.

(ii) Nechť tvrzení platí pro 1, …, h(x) − 1 a h(x) > 0. x je interní (h(x) > 0), tedy x má dva syny y a z. Pak platí:

\begin{aligned}h(y) & < h(x) \\ h(z) & < h(x) \end{aligned}

Také platí:

bh(z) = bh(y) = \{ \begin{matrix}bh(x) & pokud y je červený \\ bh(x) − 1 & pokud y je černý \end{matrix}

Z indukčního předpokladu víme, že podstrom s kořenem y má alespoň 2^{bh(y)} − 1 interních uzlů, kterých je alespoň 2^{bh(y)−1} − 1. Totéž platí pro podstrom s kořenem z.

Tedy x má alespoň 2^{bh(x)−1} − 1 + 2^{bh(x)−1} − 1 + 1 = 2^{bh(x)} − 1. Q.E.D.

LEMMA 2:

Nechť h je výška červeno–černého stromu s n interními uzly. Pak h ≤ 2 log_{2}(n + 1).

DŮKAZ:

Díky vlastnosti 3 na větvi délky 4 musí být alespoň h/2 černých vrcholů (nepočítaje kořen):

bh(kořen) ≥ h/2
n ≥ 2^{bh(kořen )} − 1 ≥ 2^{h/2} − 1
n + 1 ≥ 2^{h/2}
log_{2}(n + 1) ≥ h/2

Q.E.D.