Složitost
Složitost algoritmu vyjadřuje n/Erónost algoritmu na různ0 zdroje v průběhu výpočtu: čas výpočtu, velikost paměti, počet procesorů apod. Podle toho rozlišujeme rúzr\0míry složitosti.
Míry složitosti:   - časov/E
- prostorov/E (paněťov/E)
- procesorov/E (hardwarov/E)
Pro definici časov0 resp. prostorov0 složitosti zavedeme pojmyd0//ca výpočtu resp. množství výpočtem spotřebováno parrěti. K přesn0 definici obou pojmů však potřebujeme tzv. výpočetní model. Jeho definice z/Evisí navýpočetním paradigmatu.
Například pro Turingův stroj d0lkou výpočtu počet výpočetních kroků, tj. vnitřních přechodů. Pro RAM je to počet provedených instrukcí. Pro funkcion/Elní jazyk je to poet jednokrokových redukcí.
Složitost probl0mu'\e je zavedena jako složitost optim/Elního algoritmiřešícího tento probl0m. Na řešení nějak0ho probl0mu můžeme použít mnoho různých algoritmů Časovou složitostí probl0mu pak rozumímečasovou složitost algoritmu, který řeší daný probl0m (i na „nejpomalejších datech") nejrychleji. Prostorovou složitostí probl0mu rozumíme prostorovou složitost algoritmu, který řeší daný probl0m (i na nejm0ě příznivých datech) v nejmenší paměti apod.
Příklad:
• Řešíme probl0m: sďadit vzestupně n-prvkovou posloupnost celých čísel.
• K řešení použijeme algoritmus řazení vkl/Ed/Ením.
• Naše konkr0tní posloupnosti, kter0 budou vstupem, jsou3, 6, 9,... , 3n (tj. jsou už seřazen0).
Rozlišujeme tři pojmy:
• časovou složitost probl0mu
• časovou složitost algoritmu
• d0lku výpočtu
_)
D0lka výpočtu algoritmem ilnsSort na rostoucí posloupnosti d0lkyn je 6n — 4 (tolik se provede výpočetních kroků).
Časov/E složitost algoritmuilnsSort je vyj/Eatena kvadratickým polynomem an2 + bn + c, jak později uvidíme. Je tedy větší než d0lka výpočtu na našich (příznivých) datech. Na jiných posloupnostech d0lkyn stejný algoritmus str/Evčasu více. V nejhorším případě až kvadraticky mnoho, proto je časov/E složitost algoritmiřazení vkl/Ed/Ením kvadratick/E.
Časov/E složitost probl0mu vzestupn0ho sazení posloupnosti je však lepší než kvadratick/E: existují algoritmy, kter0n-prvkovou posloupnost seřadí v čase c n log n (c je konstanta), a to i v nejhorším případě (tj. i pro „nejzlomyslněji zadan0" vstupní posloupnosti). Proto ječasov/E složitost probl0muřazení vyj/Eatena funkcí c n log n (v proměnn0n).
D0lka výpočtu výrazů
D0lku výpočtu výrazu e označíme r(e).
r (e) je rovna součtu d0lek vyhodnocení všech operací, kter0 výraze obsahuje.
Vyhodnocení element/Erních aritmetických, logických, reáčních operací nad skal/Erními operandy je konstantní. Proto i d0lku výpočtu výrazu, který obsahuje pouze tyto jednoduch0 operace, považujeme za konstantní.
Obsahuje-li však výraz e vol/Ení složijších funkcí, je nutno započítat d0lku jejich výpočtu do r(e).
26
Přesněji:
r (c) = O, je-li c konstanta,
r (v) = 1, je-li c odkaz na hodnotu skal/Erní (pepisovateln0) pronněnn0. Tedy zpřístupnění obsahu proměnn0 považujeme za jednotkovou operaci.
r(op a) = 1 + r(a), kde op je primitivní un/Erní oper/Etor, který vyhodnocuje svůj opand, například not.
r(a 0 b) = 1 + r (a) + r (6), kde 0 je některý z primitivních bin/Erních oper/Etoru, kter0 vyhodnocují oba svoje operandy, například +,—,*, /, div, mod, <,<,>,>,....
Pozor, někter0 oper/Etory a jazykov0 konstrukce nemusí vždy vyhodroovat všechny svoje operandy. Podle toho se pak určuje d0lka výpočtu výrazů:
r(a kk b) = 1 + r(a) + r{b)   pro a pravdiv0 r(a kk b) = 1 + r(a)   pro a nepravdiv0
r(a I I b) = 1 + r(a) + r{b)   pro a nepravdiv0 r (a I I 6) = 1 + r(a)   pro a pravdiv0
r(if a then 6 else c) = 1 + r(a) + r(6)   pro a pravdiv0 r(if a then b else c) = 1 + r(a) + r (c)   pro a nepravdiv0
D0lka výpočtu vol/Ení funkce
Deklarace:
Vol/Ení hodnotou (striktní aplikace):
r(f (ai,..., an)) = 1 + r(ai) + • • • + r(an) + r(e"), kde výraz e" vznikne z výrazu e nahrazením každ0ho výskytu^ hodnotou výrazu a^.
Vol/Ení jm0nem (norm/Elní aplikace):
r(f (ai,...,an)) = 1 + r(e/), kde výraz e' vznikne z výrazu e nahrazením každ0ho výskytu X{ celým nevyhodnoceným výrazem a{.
Bude-li n/Es zajímat pouze tzv'asymptoticko c/7ov/E/7složitosti algoritmů, budeme ztotožňovat složitosti lišící se jen kladnou multiplikativní konstantou. Pro takov0 případy bude užitečn/E n/Esledující
Úmluva: Je-li e výraz obsahující jen skal/Erní konstanty a pronšnn0 a element/Erní operace (na skal/Erních hodnot/Ech), klademe d0lku jeho výptw rovnu jedn0.
Výraz e zejm0na nesmí obsahovat vektorov0 operace (nap. aritmetick0 operace na „dlouhých" číslech) ani vol/Ení uživatelských funkcí.
27
Tuto oemluvu zav/Edíme proto, že proÓKly zjišťov/Ení asymptotick0ho chov/Ení algoritmů je praktičtější například uvažovat d0lku prirazení x: =a* (b+c+d) rovnu jedn0, než ji počítat jako 1 + 1 + 2 + 5. Stejně víme, že součet je roven konstantě, a to n/Em stáí.
U tzv. „čistých" výrazů předpokl/Ed/Eme, že nemají vedlejší efekty. To však nemusí v^ofclatit. D0lka výpočtu výrazů, kter0 obsahují vol/Ení funkcí, z/Evisí najen naamotn0m výrazu, ale i na stavu, v němž se výraz vyhodnocuje. Stavem rozumíme okamžitý obsah programových (přepisovatelných) proměnných. V jazycích s vedlejšími efekty se stav během výpočtu mění.
Příklad:
var a:Integer;
function f (n:Integer):Integer; var i,k:Integer; begin k := 0;
for i:=0 to n*a do
k := k+i; a := k;
f:=a   {return a}
end
Glob/Elní pepisovateln/E prorěnn/Ea m/E na zá/Etku hodnotu 2, pak ve výrazuf (4) +f (4) trv/E každ0 vyhodnocení stejn0ho podvýrazf (4) různou dobu. (Jakou?)
D0lka výpočtu příkazů
Nechť S je množina stavů, a G S. Každý příkaz p funguje jako stavový transform/Etor v{p) : S —■> S.
D0lku výpočtu příkazu p ve stavu a označíme r(p, a). Pr/Ezdný píkaz
r(skip, cr) = 0 pro libovolný stav <r Přiřazovací příkaz
r(v:=e,cr) = 1 +r(e, a), je-li v jednoduch/E pepisovateln/E pronénn/E Sekvence
k
r(beginpi; ...; Pk end, cr0) = ^r(^,^_i),   kde Gi — v{pí){(Jí-i)
Větvení
Nechť a je stav, p, q příkazy, e výraz aa' = i/(e)(a).
r(if e thenp else g, a) = r(e, a) + r(p, a7) pro pravdiv0e,
r(if e thenp else g, a) = r(e, a) + r(g, a7) pro nepravdiv0(
Pokud výraz e nem/E vedlejší efekty, pakr = a a
r(if e thenp else g, a) = r(e, a) + r(p, a) pro pravdiv0e,
r(if e thenp else g, a) = r(e, a) + r(g, a) pro nepravdiv0e
\
Cyklus while
Nechť t = (while e do s) je příkaz cyklu a an je stav takový, že ze stavu cíq příkaz cyklu t zopakuje pr/Eé n-kr/Et sv0ěMo s.
Pro 0 < i < n označme g\ — v{e){pi), pro 0 < i < n označme cr^+i = v(s)(ai),
a nechť pro 0 < i < n je fi(e)((Ti) = pravda, fi(e)(an) = nepravda. Pak
0<i<n
Pokud výraz e nem/E vedlejší efekty, pakr^ = o\ a r(ŕ,o-0)= 5ľ (r(e'^) + r(si(Ji)) +r(e,an)
0<i<n
_)
T značí množinu všech hodnot typu T, tzv. domOnu
Stejn0 rozšření definice d0lky výpočtu se vztahuje i na výrazy s vedlejšími efekty.
Příkazy můžeme považovat za výrazy, kter0 mají speci/Elní hénotu • typu Com. S0mantika každ0ho příkazu je pak konstantní funkce, tj. pro libovolný příkaz p a stav a je fi(p)(a) = •.
Nechť f je funkce definovan/E
a <r0 je stav, ve kter0m začne výpočet. Pak buďto, v případě vol/Ení jm0nem,
r(f (ai,..., an), do) = 1 + r(e', <r0), kde výraz e' vznikne z výrazu e (těla funkce f) nahrazením každ0ho výskytu^ výrazem clí anebo, v případě vol/Ení hodnotou,
r(f (ai,... ,an),cr0) = 1 + r(ai, cr0) + r(a2, 01) H-----h r(an, (Jn-i) + T(e", crn),
kde (Ji = (pro 0 < i < n) a výraz e" vznikne z těla e takto:
e" =  begin   x1:=fi(a1)(a0);
xn:=/i(an)(crn_!);
e
end
D0lku výpočtu příkazu cyklu for můžeme odvodit tak, že si cyklus for vyj/Edme pomocí cyklu while.
Nechť t = (f or i:=etoe' do s) je příkaz cyklu a a je stav takový, že ze stavu a příkaz cyklu t zopakuje pr/E« n-kr/Et sv0ětlo s.
Označíme cr0 = v(i: =e)(cr),
pro 0 < i < n označíme <j\ = v{\. < e'){<Ji),
aproO < i < n označíme o" — iy(s)(ai), 0{+\ = u(± :=succ(i)
Pak
r(t,a) = r(i:=e)(cr)
+ - e/'°"i) +r(s'crí) +^(i*=succ(i),cr-/))
0<ž<n
+ r(i < e',crn)
Většinou n/Es víc než d0lka jednoho konkr0tního výpiíbu zajím/E, jak se daný algoritmus chov/E obecě, tj. jak vypad/E množina d0lek všech možných výpčtů — pro množinu všech přípustných vstupních dat (vyhovujících vstupní podmínce).
Časov/E složitost algoritmu
Je-li In množina všech vstupních dat pro algoritmus A, pak pro x E In zavedeme číslo x\ G N, kter0 nazveme velikost vstupní hodnoty x.
Poč/Etění stav výpočtu, který odpovíd/E umíšení hodnoty x na vstupu, označíme ax. Časovou složitost algoritmu A zavedeme jako jako funkci Ta ' N —> N takto:
Ta(tí) — max{r(A, ax) \ \x\ — n}
Časov/E složitost algoritmu je tedy funkce, kter/E pro každovelikost vstupních dat je rovna 60\cenejdelšího výpočtu na všech možných datech t0to velikosti.
31
Velikost vstupních dat odpovíd/E potu bitů, kterými je vstupní oedaj vyj/Eřén. V praxi m/E často tyto významy:
číslo n d0lka jeho bitov0ho z/Episu, tpog2 n\
posloupnost čísel     počet jejích prvků
graf počet uzlů + počet hran
Protože množina v definici složitosti je většinou nekonečn/E, musíme hledan0 maximum určit analýzou nej horšího případu.
J
32
V některých případech je výhodnější rozdělit velikost dat na dvě čísla (graf) a upravit defi složitosti TA : N x N N
Příklad:   Algoritmus řazení vkl/Ed/Ením (imperativní verze - Pascal)
1 const MAX = 999;
2 type Elem = Integer;
3 Posl = array [1..MAX] of Elem;
4 procedure ilnsSort (n:Integer; var A:Posl);
5 var i, j  : Integer;    x : Elem;
6 begin
7 for i := 2 to n do
8 begin
9 x := A[i] ;    j  : = i-1;
10 while (j>0) && (A[j]>x) do
11 begin
12 A[j+1]   := A[j] ;
13 j  := j-1
14 end;
15 A[j+1]   := x
16 end
17 end
Příklad:   Analýza nejhoršího případu
Algoritmus: ilnsSort
Vstup: posloupnost celých čísel A = (ai,..., an) d0lkyn.
Výstup: posloupnost celých čísel B, kter/E je permutací posloupnostiA a přitom je neklesající.
Označme q d0lku výpočtu příkazu nebo testu na i-t0mř/Edku algoritmuilnsSort, přičemž na sedm0mř/Edku (v z/Ehlaví cyklu for) jsoiíitelement/Erní akcejC7)initJ C7)testJ C7)inc.
Pak d0lka výpočtu je
n     / i — l
T(n) = C7jinit +       ( C7'test + c9 + Xľ^Cl° + Cl2 + Cl3)
i=2 ^ j=£
+ Cio + Ci5 + C7?inc ) + C7
,test
kde £ je hodnota, při kter0 se vnifní cyklus algoritmu zopakuje nejvícekr/Et, tj. nejmenší možn/E hodnotaj, při níž je ještě splněna podmínka za while (na 10. ř/Edku algoritmu).
Takov0 minim/Elní možn(§ je zřejmě rovno 1, a to v každ0m průchodu vnějším cyklem for. Situace, kdy v každ0m průchodu vnějším cyklem je £ = 1, nastane, když vstupní posloupnost A je klesající.
Po dosazení £ = 1 a po oepra>é dost/Ev/Eme
rrí   x       Cio + C12 + Ci3 2
Tw =-ô-™
+ (C7,test + C7,inc + Cg +
ClO C12
Cl3
+ ci5)n
2 2
+ (C7,init — c7,inc ~ Cg — C\q — C15)
což je kvadratický polynom v proměnn0n.
Podle dřívější oemluvy lze všechny konstanty považovat za jedrôky (resp. cg = 2), takže po
3 2 9
dosazení lze pracovat s polynomem   —n H—n — 4.
2 2
Abychom mohli při porovn/Ev/Ení složitostí algoritmů abstrahovat od ryahsti konkr0tního počítače, budeme chtít srovn/Evat funkce podle toho, „jak rychle rGtou", přičemž za významný rozdíl v rychlosti růstu nepovažujeme například případ, kdy jedna funkce m/Ec-kr/Et větší hodnoty než druh/E (pro ějakou kladnou konstantu c).
Rychlost růstu funkcí
Nechť g : N —> N. Zavedeme množiny funkcí:
Množina funkcí rostoucích nejvýše tak rychle jako g :
O (g) = {f I 3c> (EnnVn > n0. 0 < /(n) < c • #(n)}
Množina funkcí rostoucích aspoň tak rychle jako g :
Q{g) = {/ | 3c> 03n0Vn > n0. 0 < /(n) > c • ^(n)}
Množina funkcí rostoucích stejně rychle jako g :
O(g) = O(g) n Í2(g)
34
Množina funkcí rostoucích pomaleji než g :
o (g) = {/ | Vc > 03nnVn > no- 0 < f(n) < c • g(n)}
Množina funkcí rostoucích rychleji než g :
uj(g) = {/ | Vc > 03nnVn > no- 0 < c • g (n) < f (n)}
n
n
f e (2(g) Vn >n'.0< c'g(n) < f (n) f e 0(h) & Vn > n", f (n) < c"h(n)
36
Protože se budeme zabývat především funkcemi vyjadřujícími složitost algoritmu (kter/E je vždy nez/Eporn/E), omezíme se d/Ele na nez/Eporn0 funkce.
Vlastnosti množin O, i?, (9, o, u
Věta:   Jsou-li /, g : N —» N dvě funkce, pak / G 0(g) pr/Eé když 3ci > 03c2 > 03nnVn > no. c\ • g(n) < /(n) < C2 •
Věta:   Pro každ0 dvě kladn0 funkce/, g : N —» N platí:
/ G ^ 5 G «(/)
/ G 0(0) O p G / G 6(g) & g G 6>(/) / G / G
1
V důkazu prvních dvou tvrzení stačí obr/Etit nerovnost a uv/Ežit kladnou konstantu-.
c
Třetí tvrzení je trivi/Elní.
Čtvrt0 tvrzenířík/E, že jist/E vlastnost platí pro všechna kladn^Ale kladn/Ecísla existují, například c = 1. Tedy platí tak0 slabší vlastnost pronějakOc > 0.
Důkaz p/Et0ho tvrzení je analogický.
Věta:   Pro každ0 dvě kladn0 funkce/, g : N —» N platí:
/ e o(g) &  lim ^ = 0
f e u)(g) &  lim ^ = oo
n^oo g[n)
38
/(»)
Rovnost lim
n^oo g[n)
= 0 je ekvivalentní s podmínkou Vc > OžInoVn > no-
f(n)
9ÍP)
< c.
Obě funkce jsou kladnO, tedy absolutní hodnotu nemusíme uvažo/at a nerovnost lze vyn/Esobičíslem g(n), čímž dostaneme podmínku pro / G o(g). Úprava byla ekvivalentní, takže ekvivalentní jsou i obě podmínky v prvním tvrzení.
/(»)
Rovnost lim
n^oo g[n)
Vc > OžInoVn > no.
= oo je ekvivalentní s podmínkou f in)
> c. Obě funkce jsou kladnO, tedy absolutní hodnotu
nemusíme uvažovat a nerovnost lze vyn/EsobiĎíslem g(n), čímž dostaneme podmínku pro / G oo(g). Úprava byla ekvivalentní, takže ekvivalentní jsou i obě podmínky v prvním tvrzení.
Jsou-li /, g : N —)> N dvě kladn0 funkce, pak platí
lim M < oo ^ f e 0(ff)
9{n)
n—>oo
lim M > o =► / e /?(<?)
n—»00
Obr/Ecen0 implikace však obece neplatí, protože uveden0 limity nemusí existovat.
Pro funkce /, g však platí silnější tvrzení:
f (n)
lim sup ^4 < oo O / e O (g)
n—>oo
liminf        > O      / G !ž(g)
g{n)
n—>oo
Cvičení: Rozhodněte a zdůvodněte, zda pro každou kladnou funkci g platí 0{g) = o{g) U 9(g), (i(g) = uj{g) U 6{g).
Věta:   Nechť f,g,h:N—>N jsou tři kladn0 funkce a nechť funkceg : N —» N je definovZEnag(n) = f(n) + g(n).
Pak platí:
fe 0(h)Age 0(h) ^ gG 0(h)
f e íž(h) Age íž(h)     q e íž(h) f e 6{h) Age 6{h) ^ gG 6{h) f e o(h) Age o(h) ^ gG o(h) f e u{h) Age u{h) ^ gG u{h)
_)
Pozn/Emka: Platí řada podobných odvozených vlastností, například
/ G Í2(h) Age 0{h) => q G Í2(h) f G 9(h) Age 0(h) => q G 9(h) f G 9(h) Age o(h) ^ q G 9(h)
apod.
Cvičení:   Formulujte a dokažte další vlastnosti, kter0 z vaty vyplývají.
Věta:   Nechť /, h : N —> N jsou dvě kladn0 funkce,c, d konstanty, c > 0, a nechť funkce p : N —> N je definovZEnap(n) = c • /(n) + d.
Pak platí:
/ g O(h) => p e O(h)
f e Q{h) => p e S2(h) f e 6{h) => p e 6{h) f e o(h) ^ p e o(h) f e u(h) ^ p e u(h)
_J
Důkaz: Nejprve nechť d = 0; tvrzení obdržíme vhodnou volbou kladn0 konstanty v definidch tříd O, Í2, 0, o, co. Pro obecn0<i ^ 0 jde o speci/Elní pípad předchozí věty, kdy funkce g z jejích předpokladů je konstantní.
Věta:   Nechť N     N jsou tři funkce, pak
f e O(g) A g e 0(h) / G 0(h)
f e o(g) A g e O(h) / e o(fe)
f e O(g) A g e o(h) / e o(fe)
feí2(g)Ageí2(h) / G
f eu(g)Age Q{h) => f e u(h) /€ Í2(g) Ag eu(h) => f e u(h)
Důsledek: Relace „rusí nejvýše tak rychle" tvoří předuspoř/Ed/Erría množině všech funkcí N ->■ N.
Pozn/Emka: Relace „růstpr/Eě tak rychle"Xvoť\ ekvivalenci na množině všech funkcí
N ->■ N.
Tyto relace však nejsou oepln0. Existují dvojice funkcí, ktif) nejsou porovnateln0.
Pozn/Emka: Předuspoř/Ed/En[í0žpolouspoř/Ed/Elpíe bin/Erní relace, kter/E je reflexivní a transitivní. Uspoř/Ed/Er]é bin/Erní relace, kter/E je reflexivní, antisymetrick/E arhisativní. Ekvivalence je bin/Erní relace, kter/E je reflexivní, symetrick/E a trariraiití.
Cvičení:   Najděte příklad dvojice funkcí /, g : N —)> N, kter0 nejsou porovnateln0, tj. fÍO(g),fííi(g).
Cvičení:   Dokažte tvrzení:
Je-li kladn/E funkce/ skoro všude majorizov/Ena funkcí^ (tj. f(n) < g(n) pro skoro všechna n), pak / G O(g).
Cvičení:   Dokažte tvrzení:
Pro každou kladnou funkci g je o(g) C\uú(g) = 0.
Růst jednoduchých funkcí
Def:   Kladný polynom je polynom s kladným vedoucím koeficientem.
Věta: Kladný polynom vyššího stupně roste vždy rychleji než polynom nižšího stupně. Dva kladn0 polynomy stejn0ho stupě rostou stejně rychle.
Pozn/Emka: Předchozí větu lze zobecnit i na mocninn0 funkce s neceločíselnými exponenty: jestliže 0 < a < b, pakna G o{nb).
Věta: Exponenci/Elní funkce se z/Ekladera > 1 roste rychleji než libovolný polynom. Logaritmick0 funkce rostou pomaleji než funkce line/Erní.
42
Cvičení:   Dokažte, že pro každ0 pŕirozen0číslo k platí (n + 1)   G O (n ). (Vhodnou kladnou konstantu c z definice množiny O určete podle binomick0 vaty.)
Věta:   Nechť 1 < a < b. Pak
loga e 0(log6) an e o(bn)
Pozn/Emka: Roste-li funkce logaritmicky, pak na z/Ekladu logaritmu nežíleží. (Jen musí být větší než 1, což je však nutn/E podmínka k tomu, aby funkce vůbe rostla.)
Věta:   Platin! e 0(nn), n\ e 0(2n).
Důkaz plyne z definice faktori/Elu.
43
Pozn/Emka: Místo „(9(log)" se často píše „(9(log n)", podobně jako ,,o(n2)" místo
,,o(f), kde /(n) = n2 pro každ0n",
a dokonce „(9(1)" místo ,,0(g), kde g(n) = c > 0".
Mnozí autoři zach/Ezejí ve zneužív/Ení notace ještd/Ele (nap. pracují s množinami funkcí, jako by to byla čísla).
Pozn/Emka: Z tzv. Stirlingovy aproximace
V&(n/e)n < n! < v/2^(n/e)ne1/^12n^ vyplývají silnější tvrzení o růstu faktori/Elu:
n\ e o(nn),     n\ e tv(2n)
Def: Řekneme, že funkce / roste nejvýše poly logaritmicky, když existuje číslo k > 0 tak, že f e O ((logrc)*).
Def:   Řekneme, že funkce / roste nejvýše poíynomi/Eíě, když existuje číslo k > 0 tak, že f e 0(nk).
Funkce / roste roste aspoň polynomi/Elě, když existuje číslo £ > 0 tak, že f E Q{n£)
Def:   Řekneme, že funkce / roste nejvýše exponenci/Eíě, když existuje číslo a > 1 tak, že f E 0(an).
Funkce / roste aspoň exponenci/Elě, když existuje číslo a > 1 tak, že f E fl(an).
Def:   Řekneme, že funkce / roste aspoň dvojitě exponenci/Elě, když existuje číslo
aa ).
44
Pozn/Emka: Existují funkce, kter0 rostou rychleji než všechny&-n/Esobě exponenci/Elní funkce, a to dokonce pro Iibovoln0&.
Naopak existují kladn0 funkce, kter0 rostou (tedy rychlejhež konstantní), ale rostou pomaleji než funkce log o • • • o log, kde logaritmus můžeme složit sama se sebou libovolněkr/Et.
Def:   Fibonacciho funkce F : N —>■ N je definovan/E rekursivě:
F(0) = 0 F(l) = 1 F(n + 2)   =   F(n) + F(n + 1)
pro všechna íiGN.
1 + \/5   „    1 - \/5 Věta:   Nechť <ý? = —-—, (p = —-—. Pak pro každ0n platí
Důsledek:   Pro Fibonacciho funkci F platí i*1 E 0((pn), kde <p =-
45
Důkaz Věty - indukcí podle n.
(i) Pro n = 0 a n = 1 tvrzení platí:
<n0 _ -0       11 UD1 - in1
(ii) Předpokl/Edejme, že pro ějak0n > 0 platí F(n) = -——,
V5
F(n + 1) =---, a uk/Ežeme, žeF(n + 2) =---
F(n + 2) = F(n) + F(n + 1) = ^   _^   + ^ ^
4(l + v^)"-4(l-v^)" + 2(l + v^)"+1-2(l-y^)"+1
2"+2\/5
n
(4 + 2(1 + VŠ)) (1 + y/5)   - (4 + 2(1 - y/5)) (1 - VŠ)
2"+2\/5
(1 + 2^+5) (1 + VE)n - (l-2>/5 + 5) (l->/5)
2«+2\/5
(l + V5)"+2-(l-V5)"+2 2"+2\/5
n
14VŠ
n+2
n+2
Lemma:   Funkce log (n!) roste stejně rychle jako funkce n • log n. Důkaz: Nejdříve uk/Ežeme, že logn! G O (n log n).
n n
log2n! =      log2/c <      log2n = n log n, takže log2n! G O (n log n).
k=i k=i
n n
D/Ele funkci lo§n! ohraničíme i zdola: 2 log2n! = 2     log2/c > 2 log2/c >
k=l k=[n/2}
n
n
n
L2J
= 2
n
L2J
2 log2
&=Ln/2j
Dohromady log n! G 0(n log n)
log2
L 2 J
G 0(n log n), takže log2n! G i?(n log n)
Cvičení:   Dokažte, že d0lky výpočtů podle nějak0ho algoritmus jsou v množině O(g), pr/E« když časov/E složitost algoritmuA je v O(g) a d0lky nejkratších výpočtů patří do ft(g).
Cvičení:   Seřaďte podle rychlosti růstu funkce (v proměnn0n): log nn, log (log n), ny/ři,
ologon