Časová složitost

Když v programu začneme používat cykly, může se stát, že program bude běžet dlouho. Může se také stát, že program dokonce nikdy neskončí a bude běžet donekonečna. V úvodní kapitole jsme zmínili, že algoritmus je nějaký popis řešení úlohy a to, co úlohu řeší, je implementace v nějakém programovacím jazyce (tedy program, který lze spustit). Vzhledem k tomu, že implementací může být mnoho, může se stát, že jedna bude běžet rychleji a nějaká zas pomaleji. To svádí k zavedení konceptu časové složitosti algoritmu (anglicky time complexity), která nám umožní porovnávat rychlosti algoritmů. Budeme se zaměřovat na nejhorší případ, tedy situaci, kdy algoritmus provede nejvíce možný počet kroků a je tedy nejpomalejší. ¹

Krokování algoritmů

Nejdříve se ale zaměříme na to, jak můžeme časovou složitost vůbec vyjádřit. Protože je algoritmus deterministický (neupravuje se za běhu), můžeme vždy na základě velikosti vstupu určit, kolik “kroků” algoritmus provede.² Za krok budeme považovat nedělitelné operace, tedy například přiřazení do proměnné a aritmetické operace.

Pojďme zkusit analyzovat jednoduchý algoritmus, který hledá, jestli je zadané číslo v seznamu. Program tohoto algoritmu by vypadal takto:

hledane_cislo = 13

seznam = [...]

for cislo in seznam:
    if cislo == hledane_cislo:
        print("Hledané číslo je v seznamu.")
        break

Zde záměrně ponecháváme seznam neznámé délky (tento kód se nespustí, protože [...] je neplatný výraz), abychom nebyli ovlivněni konkrétní délkou seznamu; vždy se snažíme najít obecné řešení.

Označme délku seznamu písmenem $n$, to je náš vstup. Podívejme se dovnitř smyčky: porovnáme jestli je momentální cislo rovno hledanému číslo, a pokud ano, ukončíme smyčku. Porovnání zabere jeden krok a dva řádky uvnitř zaberou dva kroky. I když se neprovedou vždy (jen pokud najdeme hledaný prvek), započítáme je vždy – to nám říká, kolik kroků algoritmus provede v nejhorším případě, což je to, co nás zajímá. Vnitřek smyčky se provede $n$krát, protože procházíme seznam prvek po prvku, a pokud se znovu díváme na nejhorší případ, celkový počet kroků je $n\cdot 3=3n$.

Také bychom se na problém nejhoršího případu mohli podívat takto: najděte vstup, na kterém udělá algoritmus co nejvíce kroků. V tomto případě to znamená, že prvek v seznamu vůbec není, ale to my nezjistíme, dokud neprojdeme celý seznam.

Podívejme se na další příklad. Bude podobný prvnímu, ale vstup omezíme předpokladem uspořádanosti seznamu (tedy seznam je seřazený od nejmenšího po největší; pozor, neznamená to, že seznam obsahuje všechna čísla od 1 do $n$). Znovu hledáme, jestli je prvek v seznamu nebo ne.

U uspořádané posloupnosti můžeme použít trik: pokud se podíváme doprostřed seznamu, můžeme zjistit, jestli je náš hledaný prvek v prvcích nalevo nebo napravo od středu. Tím eliminujeme polovinu možností, které by algoritmus musel prohledávat a můžeme si to dovolit právě kvůli tomu, že seznam je uspořádaný. V této polovině se zase můžeme podívat doprostřed a postup opakovat. Tomuto postupu se říká binární vyhledávání. Napišme nejdříve program a poté ho analyzujme:

hledane_cislo = 13

seznam = [...]

levy = 0
pravy = len(seznam) - 1

while levy <= pravy:
    stred = (levy + pravy) // 2
    if seznam[stred] == hledane_cislo:
        print(f"Nalezeno na indexu {stred}.")
        break
    elif seznam[stred] < hledane_cislo:
        levy = stred + 1
    else:
        pravy = stred - 1

Program využívá takzvané metody dvou jezdců: udržujeme si indexy levy a pravy, které určují hranice toho, kde se má vyhledávat. V případě, že je střed právě prohledávaného podseznamu roven hledanému číslu, algoritmus končí úspěchem. Pokud je střed menší než hledané číslo (tedy hledané číslo je větší, než je střed), víme, že máme postup opakovat na pravé polovině, protože se v levé polovině nacházet nemůže. Analogicky pro hledání na levé polovině.

Přistupme k analýze. Uvnitř while smyčky se provedou nejhůře 3 kroky. Kolikrát se ale nejhůře provede smyčka sama? Označme písmenem $c$ počet provedených opakování cyklu a $n$ počet prvků v seznamu. Na začátku pracujeme se seznamem o velikosti $n$, po jednom cyklu o velikosti $\frac{n}{2}$, po druhém cyklu o velikosti $\frac{n}{4}$, a tak dále. Můžeme tedy říct, že po $c$ opakováních cyklu pracujeme se seznamem o velikosti $\frac{n}{2^c}$. Náš algoritmus se v nejhorším případě zastaví, když se dostaneme na seznam velikosti 1 (už nemůžeme seznam dělit dál). Chceme tedy vyjádřit $c$ v závislosti na $n$ tehdy, kdy se dostaneme na seznam velikosti 1. Řešíme tedy rovnici

$$\begin{array}{rl}\frac{n}{2^c}& \approx 1\\ n& \approx 2^c\\ c& \approx {\log }_{2}n\end{array}$$

To je zajímavé zjištění – počet opakování cyklu je závislé ne lineárně, ale logaritmicky na velikosti vstupního seznamu! Celkový počet kroků algoritmu je v nejhorším případě okolo $3\cdot {\log }_{2}n$.

Uvažme úpravu prvního algoritmu tak, aby byl omezen stejnou podmínkou pro vstup – používáme ho jen pro setřízené seznamy. Kód se nijak nezmění. Nyní máme dva programy pro stejnou úlohu hledání existence prvku v poli. Druhý algoritmus je ale výrazně rychlejší. Pro seznam o 10 000 prvcích provede první algoritmus okolo 20 000 kroků, zatímco druhý provede (po zaokrouhlení) pouze 42 kroků! To je výrazně rychlejší.

Od přesnosti k asymptoticitě

Dosud jsme rychlost algoritmu vyjadřovali v přesném počtu kroků. To může být ale občas krkolomné, protože nám vlastně nejde moc o přesný počet kroků, ale spíše o to, jak se bude rychlost algoritmu vyvíjet na velkých vstupech. Když poté do ruky dostaneme více algoritmů pro řešení stejné úlohy, vybereme ten, který úlohu s “velkým” zadáním bude řešit nejrychleji.

Potřeba analýzy pro velké vstupy donutila teoretické informatiky zavést koncept asymptotické³ časové složitosti. Spočívá v tom, že se na výrazy popisující počet kroků algoritmů budeme dívat jako na křivky a budeme pozorovat, jak rychle rostou.

Červenou křivkou je znázorněn první algoritmus s počtem kroků $3n$, modrou druhý s počtem kroků $3{\log }_{2}n$. Na ose $x$ je velikost vstupu, na ose $y$ počet kroků. Jak můžeme z grafu vidět, počet kroků binárního vyhledávání pro velké vstupy,⁴ a dokonce ani v nekonečnu, nikdy nepřesáhne počet kroků vyhledávání lineárního. To je definice toho, že funkce $3{\log }_{2}n$ je asymptoticky menší, než funkce $3n$.

Ve světě asymptot můžeme dokonce ignorovat aditivní a multiplikativní konstanty a zaměřit se pouze na “tvar” funkce. Z funkce $3n$ se tedy stane $n$ a z funkce $3{\log }_{2}n$ se stane ${\log }_{2}n$. Protože je základ logaritmu také nepotřebný, můžeme psát pouze $\log n$. Abychom uvedli další příklady, z funkce $n+3n+5$ se stane $n$ a z funkce $3{\log }_{4}n+8{\log }_{5}n$ se stane $\log n$. Poslední způsob, jakým můžeme funkce pro náš účel takto “zjednodušit” je odstranění pomalu rostoucích členů. Funkci $5+n+n^3+n^7$ můžeme zjednodušit na prosté $n^7$, protože část výrazu, který nejvíce přispívá růstu pro velké hodnoty $n$, je právě člen $n^7$.

Protože je toto zjednodušování běžné, zavedli pro něj pánové Bachmann a Landau speciální zápis (anglicky big O notation, my mu budeme říkat velké O). Pomocí něj můžeme napsat například toto:

• $5+n+n^3+n^7\in \mathcal{O}(n^7)$
• $3n\in \mathcal{O}(n)$

Pojďme se také podívat na porovnání růstu běžných funkcí:

$$c<\log n<\sqrt{n}<n<n\log n<n^2<n^3<2^n<3^n<5^n<10^n$$

Za použití velkého O můžeme tedy napsat $n\in \mathcal{O}(n\log n)$ a také $n\log n\in \mathcal{O}(n\log n)$. Co už neplatí je $n^2\notin \mathcal{O}(n\log n)$, protože $n^2$ roste rychleji, než $n\log n$.

Symbol $\in$ používáme proto, že velké O tvoří množinu funkcí, které rostou stejně nebo rychleji, než funkce nalevo od $\in$.

Pro naše dva algoritmy tedy můžeme říct, že první algoritmus běží v čase $\mathcal{O}(n)$ a druhý v čase $\mathcal{O}(\log n)$. Protože funkce $\log n$ roste pomaleji, než funkce $n$, je druhý algoritmus rychlejší.

Složitost běžných operací

Běžné aritmetické operace bereme jako operace s konstantní složitostí, tedy že provedou konstantní počet kroků bez ohledu na velikost vstupu. Tyto operace tedy budou velmi rychlé; konstantní složitost zapíšeme jako $\mathcal{O}(1)$.

Operace s lineární časovou složitostí $\mathcal{O}(n)$, kde $n$ je velikost vstupu, většinou tvoří iterace přes všechny prvky v nějakém datovém struktuře (seznam, slovník, atd.). Důležité je, že klíčové slovo in, které používáme ke zjištění toho, zda je prvek v seznamu či ne, má lineární časovou složitost, protože v nejhorším případě musí prohledat všechny prvky v seznamu.

1. Může se zdát, že toto jde proti požadavku determinismu. To však není pravda, protože algoritmus sice může provést jen daný počet kroků v závislosti na vstupu, ale tento počet kroků se právě od tohoto vstupu odvíjí! Může se tedy stát, že pro nějaký vstup provede jeden krok, ale pro jiný tisíce – to nemusí být na škodu, my se jen snažíme o vyjádření toho, jak algoritmus funguje zaprvé v obecnosti a zadruhé pro nejhorší, nejpomalejší případ. ↩

2. Závislost na velikosti vstupu je zde velmi důležitá. Představte si, že dělíte dvě čísla pod sebou. Vydělit dvouciferné číslo jednociferným je jednodušší, než vydělit tisíciciferné číslo dvaceticiferným. Stále však opakujeme ty stejné kroky, jen nám to trvá déle, protože vstup je větší. ↩

3. Asymptotou v geometrii označujeme přímku, které se v nějaké křivce blíží, aniž by s ní měla společný bod. Asymptota může být libovolně blízko, ale nikdy se dané křivky nedotkne. ↩

4. Slovo velké je zde důležité, protože například třeba tyto naše dvě funkce se pro malá $n$ potkají, dvakrát protnou a modrá je dokonce větší, než červená. To nám však nevadí, protože se nesoustředíme na malé vstupy. ↩