Asymptotická časová složitost algoritmů

Efektivita algoritmů

Co to vlastně složitost (efektivita) algoritmu je a k čemu v praxi slouží? Můžeme si ji definovat jako funkci vyjadřující počet kroků algoritmu (resp. velikost potřebné paměti) v závislosti na velikosti vstupních dat. Jako velikost vstupních dat obvykle stačí uvažovat např. počet zpracovaných čísel, nikoliv konkrétní hodnoty (jedná-li se o hodnoty „standardní“ velikosti). Obecně by se musela uvažovat velikost vstupních dat v bitech. Pokud bychom tedy chtěli setřídit čísla a₁, a₂, … , a_n, velikost vstupních dat by byla rovna počtu prvků posloupnosti tedy |D| = n.

Krok algoritmu je operace proveditelná v konstantním (tj. na velikosti dat nezávislém) čase, patří mezi ně primárně aritmetické operace (sčítání, odčítání, násobení…), porovnání dvou hodnot a přiřazení (to však pouze pro jednoduché datové typy, nikoliv pro pole). Složitost často slouží jako kritérium pro porovnávání kvality programů a algoritmů a zjištění praktické použitelnosti.

Rozeznáváme dva typy složitostí:

1. Časovou – odpovídá počtu vykonaných operací resp. rychlosti výpočtu
2. Prostorovou – odpovídá velikosti datových struktur využívaných algoritmem.

Obě kritéria obvykle míří proti sobě, neboť není možno najednou optimalizovat paměť i čas, proto si vždy programátor musí zvolit, čemu dá přednost. V dnešní době se obvykle preferuje čas.

Asymptotická časová složitost

Přesné vyjádření funkce časové složitosti (např. 3.N² + 2.N – 4) je jednak obtížné, jednak většinou zbytečné. Podstatnější je řádová rychlost růstu této funkce pro rostoucí N. Z tohoto důvodu se zavedl pojem asymptotická časová složitost. U asymptotické složitosti zanedbáme pomaleji rostoucí členy a konstanty, ve výše zmíněném příkladě by proto vyšla asymptotická časová složitost O(N²).

Symbol O(N²) značí, že je naše funkce f(n) asymptoticky menší nebo rovna funkci g(n)= N² V takovémto případně mluvíme o horním odhadu a vztah značíme f(n) ∈ O(g(n)) a definujeme ho následovně:

∃ c>0 ∃ n₀>0 ∀ n≥n₀ : 0 ≤ f(n) ≤ c g(n)

Obdobně můžeme definovat dolní odhad f(n) ∈ Ω(g(n)): f(n) je asymptoticky větší nebo rovno g(n), pokud ∃ c>0 ∃ n₀>0 ∀ n≥n₀ : 0 ≤ c g(n) ≤ f(n). Pokud se horní odhad rovná odhadu dolnímu, říkáme že jsou funkce asymptoticky stejné a mluvíme o o přesném odhadu f(n) ∈ Θ(g(n)).

Cílem programátora by mělo být najít vždy algoritmus s co nejmenší asymptotickou časovou složitostí, tedy co nejrychlejší pro velká N. Pro malá N může být zvolené řešení i horší než jiný algoritmus, ale pro malá N to nevadí, neboť doba výpočtu bude vždy dostatečně krátká. Polynomiální algoritmy jsou obvykle zvládnutelné i pro velká N, algoritmy s exponenciální složitostí jsou již pro větší N časově nezvládnutelné a proto jsou použitelné jen v případě, že vstupní data budou vždy malá. Následující tabulka demonstruje dobu, po kterou by trvalo provádění f(n) operací pro vstupní data velikosti n za předpokladu, že použitý hardware je schopen vykonat 1 milion operací za sekundu.

Složitost algoritmu v různých případech

Pro každá vstupní data velikosti N nemusí trvat výpočet stejně dlouho, rozdíl může být jen v konstantě, nebo i v asymptotické složitosti. Proto v praxi určujeme i časovou složitost algoritmu v nejhorším případě což odpovídá maximálnímu počtu operací vykonaných algoritmem pro nějaká data velikosti N. Tato složitost se nejčastěji používá pro hodnocení algoritmů. Opakem je časová složitost algoritmu v nejlepším případě, které se naopak prakticky nepoužívá. Důležitým pojmem je však časová složitost algoritmu v průměrném případě, což je průměrný (očekávaný) počet operací vykonaných algoritmem pro data velikosti N (průměr pro všechna možná vstupní data velikosti N). Tato vlastnost dobře charakterizuje kvalitu algoritmu, ale je obtížné odvodit ji.

Posledním pojmem se kterým se můžeme v praxi setkat je složitost problému. Složitost problému je definována jako složitost nejlepšího algoritmu (z hlediska časové složitosti), kterým lze řešit daný problém. Nelze ji obvykle odvodit ze složitosti nějakého konkrétního algoritmu, charakterizuje totiž problém obecně. Určuje, jaký nejlepší algoritmus řešící problém může v principu existovat, odvození je však obtížné a pro řadu problémů neznámé.

Příklady složitostí:

• QuickSort – v průměru T(n) = Θ (n log n), v nejhorším případě T(n)=O(n²)
• Counting Sort, Radix Sort – třídění v lineárním čase – T(n)=O(n)
• Borůvkův algoritmus pro nalezení minimální kostry grafu – T(n)= Θ (m log m)
• Dijkstrův algoritmus pro nalezení nejkratší cesty – T(n)= Θ ((n+m)log n)
• BFS – prohledávání grafu do šířky – T(n)=O(n+m)
• Strassenův algoritmus pro násobení matic – T(n)= Θ (n^x)
• Blumův algoritmus pro hledání k-tého z n prvků – T(n) = O(n)

Master Theorem

V poslední části se budeme zabývat výpočtem složitosti u algoritmů typu „Rozděl a panuj“. Jedná se o metodu pro návrh algoritmů, která se využívá například pro binární vyhledávání nebo MergeSort.

Typicky má algoritmu 3 kroky:

1. ROZDĚL úlohu na několik podúloh stejného typu, ale menšího rozsahu
2. VYŘEŠ podúlohy, a to:
   1. rekurzivně dalším dělením pro podúlohy dostatečně velkého rozsahu
   2. přímo pro podúlohy malého rozsahu (často triviální)
3. SJEDNOŤ řešení podúloh do řešení původní úlohy

Mergesort – Ukázka řazení pole metodou rozděl a panuj

Analýza časové náročnosti:

T(n) – doba zpracování úlohy velikosti n (předpoklad: pokud n < k tak T(n) = Θ (1))
D(n) – doba na rozdělení úlohy velikosti n na a podúloh stejné velikosti n/c
S(n)  – doba na sjednocení řešení podúloh do řešení původní úlohy velikosti n

Rekurentní rovnice pak bude T(n) = D(n) + aT(n/c) + S(n) pro n ≥ k.

Master Therorem je „kuchařka“, díky které můžeme poměrně jednoduše zjistit asymptotickou složitost této rekurentní rovnice. Nechť a ≥ 1, c > 1, d ≥ 0 jsou reálná čísla a nechť T : N −> N je neklesající funkce taková, že pro všechna n ve tvaru ck (kde k ∈ N) platí T(n) = aT(n/c) + F(n), kde pro funkci F : N −> N platí F(n) = Θ (n^d). Označme x = log_c a. Potom

• je-li x < d, potom platí T(n) = Θ (n^d)
• je-li x = d, potom platí T(n) = Θ (n^d log n) = Θ (n^x log n)
• je-li x > d, potom platí T(n) = Θ (n^x)