Recepty z programátorské kuchařky
Složitost

V této kuchařce se můžete dočíst o základech časové a paměťové složitosti. Po přečtení byste měli být schopni sami rozebrat složitost jednoduchých algoritmů. To se hodí třeba při návrhu algoritmů a řešení algoritmických úloh, které můžete potkat například v KSP.

Nejdříve si ujasníme, co to ta složitost vlastně je, a ukážeme si pár příkladů. Pak si řekneme, s jakou přesností budeme složitost chtít určovat, a zavedeme si asymptotickou složitost. Na závěr si ukážeme běžné třídy složitosti.

Základní přehled

Pokud řešíme nějakou programátorskou úlohu, často nás napadne více různých řešení a potřebujeme se rozhodnout, které z nich je „nejlepší“. Abychom to mohli posoudit, potřebujeme si zavést měřítka, podle kterých budeme různé algoritmy porovnávat. Nás u každého algoritmu budou zajímat dvě vlastnosti: čas, po který algoritmus běží, a paměť, kterou při tom spotřebuje.

Čas nebudeme měřit v sekundách (protože stejný program na různých počítačích běží rozdílnou dobu), ale v počtu provedených operací. Pro jednoduchost budeme předpokládat, že aritmetické operace, přiřazování, porovnávání apod. nás stojí jednotkový čas. Ona to není úplná pravda, tyto operace se ve skutečnosti přeloží na procesorové instrukce, které se teprve zpracovávají. Ale nám postačí vědět, že těch instrukcí bude vždy konstantní počet. A později se dozvíme, proč nám na takové konstantě nezáleží.

Množství použité paměti můžeme zjistit tak, že prostě spočítáme, kolik bytů paměti náš program použil. Nám obvykle bude stačit menší přesnost, takže všechna čísla budeme považovat za stejně velká a velikost jednoho prohlásíme za jednotku prostoru.

Jak čas, tak paměť se obvykle liší podle toho, jaký vstup náš program zrovna dostal – na velké vstupy spotřebuje více času i paměti než na ty malé. Budeme proto oba parametry určovat v závislosti na velikosti vstupu a hledat funkci, která nám tuto závislost popíše. Takové funkci se odborně říká časová (případně paměťová, někdy též prostorová) složitost algoritmu/programu.

Nyní si na příkladu ukážeme, jak se časová a paměťová složitost dá určovat intuitivně, a pak si vše podrobně vysvětlíme.

Představme si, že máme danou posloupnost N celých čísel, ze které chceme vybrat maximum. Použijeme algoritmus, který za maximum prohlásí nejprve první číslo posloupnosti. Pak toto maximum postupně porovnává s dalšími čísly v posloupnosti, a pokud je některé větší, učiní z něj nové maximum. Zapsat bychom to mohli třeba takto:

def maximum(pole):
    docasne_max = pole[0]
    for prvek in pole:
        if(prvek > docasne_max):
            docasne_max = prvek
    return docasne_max

Není těžké nahlédnout, že algoritmus provede maximálně N-1 porovnání. Intuitivně časová složitost bude lineárně záviset na N, protože porovnání dvou čísel nám zabere „jednotkový čas“, a paměťová složitost bude také na N záviset lineárně, protože si každé číslo z posloupnosti budeme uchovávat v paměti.

Pokud bychom si nepamatovali celou posloupnost, ale vždy jen poslední přečtený člen, stačilo by nám jen konstantně mnoho proměnných, takže paměťová složitost by klesla na konstantní (nezávislou na N) a časová by zůstala stejná.

Jiný příklad: Mějme dané číslo K. Naším úkolem je vypsat tabulku všech násobků čísel od 1 do K:

def vypis_nasobky(do_cisla):
    for i in range(1, do_cisla):
        for j in range(1, do_cisla):
            print(i*j, end=' ')
        print()

vypis_nasobky(5)

Tabulka má velikost K² a na každém jejím políčku strávíme jen konstantní čas. Proto časová složitost bude záviset na čísle K kvadraticky, tedy bude K². Paměťová složitost bude buď konstantní, pokud hodnoty budeme jen vypisovat, anebo kvadratická, pokud si tabulku budeme ukládat do paměti. Můžeme si také všimnout, že tabulku nemusíme vypisovat celou, ale bude nám stačit jen její dolní trojúhelníková část – i tak budeme muset spočítat (K · K-K)/2 + K = K²/2 + K/2 hodnot, což je stále řádově kvadratické vzhledem ke K.

U výběru algoritmu tedy bereme v potaz čas a paměť. Který z těchto faktorů je pro nás důležitější, se musíme rozhodnout vždy u konkrétního příkladu. Často také platí, že čím více času se snažíme ušetřit, tím více paměti nás to pak stojí. To kvůli chytré reprezentaci dat v paměti a různým vyhledávacím strukturám, o kterých se můžete dočíst v našich dalších kuchařkách.

Nás u valné většiny algoritmů bude nejdříve zajímat časová složitost a až poté složitost paměťová. Paměti mají totiž dnešní počítače dost, a tak se málokdy stane, že vymyslíme algoritmus, který má dokonalý čas, ale nestačí nám na něj paměť. Ale přesto doporučujeme dávat si na paměťová omezení pozor.

Než se pustíme do podrobnějšího vysvětlování, ještě si ukážeme tzv. „metodu kouknu a vidím“, kterou můžeme použít na určování časové složitosti u těch nejjednodušších algoritmů. Spočívá jen v tom, že se podíváme, kolik nejvíc obsahuje náš program vnořených cyklů. Řekněme, že jich je k a že každý běží od 1 do N. Potom za časovou složitost prohlásíme N^k.

Vzhledem k čemu budeme složitosti určovat?

Složitosti obvykle určujeme vzhledem k velikosti vstupu (např. počet čísel, případně znaků na vstupu). Tento počet si označme N. Časovou i paměťovou složitost pak vyjádříme vzhledem k tomuto N. To je vidět třeba na výběru maxima v předchozím textu.

Pokud by existovalo několik vstupů stejné velikosti, pro které náš algoritmus běží různě dlouho, bude časová složitost popisovat ten nejhorší z nich (takový, na kterém algoritmus poběží nejpomaleji). Stejně tak pro paměťovou složitost použijeme ten ze vstupů délky N, na který spotřebujeme nejvíce paměti. Dostaneme tzv. složitosti v nejhorším případě. Podrobněji si o tom povíme později.

Někdy se nám hodí určit složitost v závislosti na více než jedné proměnné. Pokud bychom například chtěli vypisovat všechny dvojice podstatného a přídavného jména ze zadaného slovníku, strávíme tím čas, který bude záviset nejen na celkové velikosti slovníku, ale i na tom, kolik obsahuje podstatných a kolik přídavných jmen. Rozmyslete si, jaká složitost vyjde, pokud víte, že velikost slovníku je S, podstatných jmen je A a přídavných jmen B.

Častým příkladem, kde si velikost vstupu potřebujeme rozdělit do více proměnných, jsou algoritmy pracující s grafy (viz grafová kuchařka). V případě grafů obvykle vyjadřujeme složitost pomocí proměnných N a M, kde N je počet vrcholů grafu a M je počet jeho hran. I pro více proměnných vybíráme nejhorší případ.

Ne vždy ale určujeme složitosti v závislosti na velikosti vstupů. Například pokud je velikost vstupu konstantní, složitost určíme vzhledem k hodnotám proměnných na vstupu. Třeba u příkladu s tabulkou násobků jsme složitost určili vzhledem k velikosti tabulky, kterou jsme dostali na vstupu. Jiným příkladem může být vypsání všech prvočísel menších než dané N.

Asymptotická složitost

V této části textu se budeme věnovat pouze časové složitosti. Všechna pravidla, která si řekneme, pak budou platit i pro paměťovou složitost.

U určování časové složitosti nás bude především zajímat, jak se algoritmy chovají pro velké vstupy. Mějme například algoritmus A o časové složitosti 4N a algoritmus B o složitosti N². Tehdy je sice pro N=1,2,3 algoritmus B rychlejší než A, ale pro všechna větší N ho už algoritmus A předběhne. Takže pokud bychom si měli mezi těmito algoritmy zvolit, vybereme si algoritmus A.

U složitosti nás obvykle nebude zajímat, jak se chová na malých vstupech, protože na těch je rychlý téměř každý algoritmus. Rozhodující pro nás bude složitost na maximálních vstupech (pokud nějaké omezení existuje) anebo složitost pro „hodně velké vstupy“. Proto si zavedeme tzv. asymptotickou časovou složitost.

Představme si, že máme algoritmus se složitostí n²/4 + 6n + 12. Pod asymptotikou si můžeme představit, že nás zajímá jen nejvýznamnější člen výrazu, podle kterého se pak pro velké vstupy chová celý výraz. To znamená, že:

• Konstanty u jednotlivých členů můžeme škrtnout (např. 6n se chová podobně jako n). Tím dostáváme n² + n + 1.
• Pro velká n je n + 1 oproti n² nevýznamné, tak ho můžeme také škrtnout. Dostáváme tak složitost n². Obecně škrtáme všechny členy, které jsou pro dost velké n menší než nějaký neškrtnutý člen.

Tahle pravidla sice většinou fungují, ale škrtat ve výpočtech přece nemůžeme jen tak. Proto si nyní zavedeme operátor O (velké O), díky kterému budeme umět popsat, co přesně naše „škrtání“ znamená, a používat ho korektně.

Definice: Mějme funkce f: N →R⁺ a g: N →R⁺. Řekneme, že f ∈O(g), pokud ∃n₀ ∈N a ∃c ∈R⁺ tak, že ∀n ≥ n₀ platí f(n) ≤ c · g(n).

Nyní slovy: Mějme f a g funkce z přirozených do kladných reálných čísel. Řekneme, že funkce f patří do třídy O(g), pokud existují konstanty n₀ a c takové, že f je pro dost velká n (totiž pro n≥ n₀) menší než c · g(n).

Někdy také píšeme, že f=O(g) nebo říkáme, že program má složitost O(f).

A zde je použití: n²/4 + 6n + 12 ∈O(n²), protože například pro c=10 platí pro všechna n>1 (tedy n₀=2):

Pokud vám tento způsob nevyhovuje a více se vám líbí metoda pomocí „škrtání“, klidně ji používejte, akorát všude pište O(… ). Někdy také říkáme, že se konstanty a méně významné členy v O ztrácí.

Ještě poznamenejme, že operátor O(… ) znamená asymptotický horní odhad funkce. Takže pokud funkce patří do O(N), tak pak patří i do O(N²), O(N³), …

Nejhorší a průměrný případ

Opět si vše vysvětlíme jen na časové složitosti.

Velká část algoritmů běží pro různé vstupy stejné velikosti různou dobu. U takových algoritmů pak můžeme rozlišovat složitost v nejhorším případě (tu už známe), v nejlepším případě a třeba i průměrnou časovou složitost.

Vše si ukážeme na algoritmu BubbleSort (bublinkovém třidění), o kterém se můžete dočíst v kuchařce o třídících algoritmech. Funguje tak, že se dívá na všechny dvojice sousedních prvků, a kdykoliv je dvojice ve špatném pořadí, tak ji prohodí. Zde je kód algoritmu v Pythonu 3:

def bubble_sort(pole):
    setrideno = False
    while not setrideno:
        setrideno = True
        for i in range(0, len(pole)-1):
            if pole[i] > pole[i+1]:
                pole[i], pole[i+1] = pole[i+1], pole[i]
                setrideno = False
    return pole

Časová složitost v nejhorším případě činí O(N²) – v každém průchodu vnějším cyklem nám totiž největší hodnota „probublá“ na konec a ostatní se posunou o jednu pozici doleva. Rozmyslete si, proč. Průchodů je proto nejvýše N-1 a každý z nich trvá O(N). Tento nejhorší případ může doopravdy nastat, pokud necháme setřídit klesající posloupnost. Tam provedeme přesně N-1 průchodů.

Naopak v nejlepším případě bude časová složitost pouze O(N). To nastane, pokud na vstupu dostaneme už setříděnou posloupnost. U té algoritmus pouze zkontroluje všechny dvojice a pak se ihned zastaví.

Průměrná časová složitost nám udává, jak dlouho náš algoritmus běží průměrně. Co to ale znamená, není snadné definovat ani spočítat. U třídícího algoritmu bychom mohli počítat průměr přes všechny možnosti, jak mohou být prvky na vstupu zamíchané (tedy přes všechny jejich permutace). To nám někdy může dát přesnější odhad chování algoritmu.

Zrovna u BubbleSortu a mnoha jiných algoritmů vyjde průměrná časová složitost stejně jako složitost v nejhorším případě. Jedním z nejznámějších příkladů algoritmu, který je v průměru asymptoticky lepší, je třídící algoritmus QuickSort (opět viz třídicí kuchařka). Jeho průměrná časová složitost činí O(N ·  log N), zatímco v nejhorším případě může běžet až kvadraticky dlouho.

Často používané složitosti

Na závěr si ukážeme často se vyskytující časové složitosti algoritmů (ty paměťové jsou obdobné). Seřadili jsme je od nejrychlejších a ke každé připsali příklad algoritmu.

• O(1) – konstantní (třeba zjištění, jestli je číslo sudé)
• O(log N) – logaritmická (binární vyhledávání); všimněte si, že na základu logaritmu nám nezáleží, protože platí log_a n = log_b n / log_b a, takže logaritmy o různých základech se liší jen konstanta-krát, což se „schová do O-čka“
• O(N) – lineární (hledání maxima z N čísel)
• O(N ·  log N) – lineárně-logaritmická (nejlepší algoritmy na třidění pomocí porovnávání)
• O(N²) – kvadratická (BubbleSort)
• O(N³) – kubická (násobení matic podle definice)
• O(2^N) – exponenciální (nalezení všech posloupností délky N složených z nul a jedniček; pokud je chceme i vypsat, dostaneme O(N · 2^N))
• O(N!) – faktoriálová, N! = 1 · 2 · 3 · …  · N (nalezení všech permutací N prvků, tedy například všech přesmyček slova o N různých písmenech)

Složitosti ještě často rozdělujeme na polynomiální a nepolynomiální. Polynomiální říkáme těm, které patří do O(N^k) pro nějaké k. Naopak nepolynomiální jsou ty, pro něž žádné takové k neexistuje.

Do polynomiálních algoritmů patří například i algoritmus se složitostí O(log N). A to proto, že O(log N) ⊂ O(N) (každý algoritmus, který seběhne v čase O(log N), seběhne i v O(N)).

Nepolynomiální jsou z naší tabulky třídy O(2^N) a O(N!). Takové algoritmy jsou extrémně pomalé a snažíme se jim co nejvíce vyhýbat.

Pro představu o tom, jak se složitost projevuje na opravdovém počítači, se podíváme, jak dlouho poběží algoritmy na počítači, který provede 10⁹ (miliardu) operací za sekundu. Tento počítač je srovnatelný s těmi, které dnes běžně používáme. Podívejme se, jak dlouho na něm poběží algoritmy s následujícími složitostmi:

Pro představu: 1 000 s je asi tak čtvrt hodiny, 1 000 000 s je necelých 12 dní, 10⁹ s je 31 let a 10¹⁸ s je asi tak stáří Vesmíru. Takže nepolynomiální algoritmy začnou být velmi brzy nepoužitelné.

Karel Tesař a Martin Mareš