/ janturon.cz / Od kodéra k analytikovi / Časová složitost algoritmu

Časová složitost algoritmu

Teorie

Při rozhodování mezi dvěma podobnými algoritmy potřebujeme nějaké objektivní měřítko kvality. Čitelnost a udržitelnost, které byly probrány, jsou nezbytné. Stejně důležitá je ale efektivita algoritmu. Zde ale pozor na antivzor Paralýza analýzou: efektivitu je třeba řešit jen tam, kde výkon nedostačuje: snaha zrychlit program o 20ms tam, kde sekunda nehraje roli je sice dobré intelektuální cvičení, ale neekonomické, protože nesouvisí s požadavky na aplikaci.

Pomalost je nejčastěji způsobená přílišným množstvím vykonaných příkazů. Ty netrvají stejné časové kvantum: některé jsou překládány do řádově většího počtu mikroinstrukcí, jiné zahrnují čekání na odezvu sítě. Příkazy, jejichž doba vykonávání se řádově liší od ostatních příkazů, proto před úvahami ohodnotíme odpovídajícím koeficientem.

Časová složitost je ohodnocený součet kroků algoritmu v závislosti na délce vstupu (je to tedy funkce). Délkou vstupu může být délka řetězce, pole či souboru nebo třeba velikost čísla. Pokud délka výpočtu nezávisí na délce vstupu, algoritmus skončí vždy po stejném počtu kroků a jeho časová složitost je konstantní.

Uvedené popisuje časovou složitost algoritmu. Určení paměťové složitosti je podobné, pouze si místo počtu kroků všímáme počtu bajtů použité paměti. Následující text je proto jen v kontextu časové složitosti. Délka vstupu bude dále označována jako N.

Následující algoritmus tisknoucí násobilku šesti

cout << "Násobilka 6" << endl; for(int i=1; i<=10; i++) cout << i << 'x' << 6 << '=' << i*6 << endl;

kde každý operátor << představuje příkaz pro zápis na standardní výstup bude mít časovou složitost 8N + 3 (2 příkazy před cyklem, 1 inicializace for; 2 opakující se v závorce for, 6 opakujících se v těle for), počítáme-li s délkou vstupu jako počet řádků s pravidly.

Někdy délka výpočtu závisí na konkrétních hodnotách vstupu (viz např. funkci indexOf z kapitoly Vzory řešení: Návrat z funkce). V tom případě vyhodnocujeme průměrný dohad nebo (pamětlivi Murphyho zákona) nejhorší případ.

Tohle všechno je spousta počítání odvádějící nás od cíle: Který algoritmus je rychlejší? Určující je proto pouze řád (či třída) časové složitosti, který je zde lineární (obyčejný cyklus). Dva vnořené cykly by pak měly kvadratickou časovou složitost.

Počítáme-li s malými často se opakujícími vstupy, kvadratická složitost může být lepší než lineární, např. N2 < 50N pro všechna N menší než 50. Ať už jsou ale koeficienty jakékoliv, od jisté hodnoty výše je lineární složitost vždy lepší než kvadratická. Pokud tato "jistá hodnota" není nepřiměřeně vysoká a za předpokladu, že pracujeme s daty alespoň v řádech kilobajtů, je třída časové složitosti určující pro rychlost algoritmu.

Asymptotickou třídu složitosti nejhoršího případu značíme velkým omikron, průměrného odhadu velkým theta a (pokud je to podstatné) nejlepšího odhadu velkým omega. Pro výšeuvedený algoritmus platí Ο(N), Θ(N), Ω(N).

Pro představu následující tabulka uvádí délku výpočtu v závislosti na délce vstupu při práci na stroji vykonávajícím milion operací za sekundu.

4,5ms
N102040605001000
lg(n)3,3μs4,3μs5,3μs5,9μs9μs10μs
n10μs20μs40μs60μs0,5ms1ms
n lg(n)33μs8,6μs212μs354μs4,5ms10ms
n2100μs400μs1,6ms3,6ms250ms1s
n31ms8ms64ms200ms125s17min
2n1ms1s13d37ky10137y

Je vidět, že pro délku vstupu v řádech stovek je exponenciální časová složitost prakticky neřešitelná, i kdybychom do výpočtu zapojili všechny stroje na světě a měli na to celý čas vesmíru.

Praxe

Ukázky, jak rozpoznat časovou složitost.

Konstantní

Výpočet nezávislý na délce vstupu.

int constant(int data) { return 42; }

Lineární

Jednoduchý cyklus úměrný délce vstupu:

void linear(int data) { for(int i=0; i<data; i++) cout << i; }

Lineární rekurze:

int factorial(int n) { if(n<1) return 1; return n * factorial(n-1); }

Kvadratická

Dva vnořené cykly úměrné délce vstupu

void matrix(int data) { for(int i=0; i<data; i++) { for(int j=0; j<data; j++) cout << i*j << ' '; cout << endl; } }

Pozor, tohle je lineární!

void matrix(int data) { for(int i=0; i<data; i++) { for(int j=0; j<100000; j++) cout << i*j << ' '; cout << endl; } }

Logaritmická

(Při základu 2): průchod stromem od kořene k listu, rekurzivní půlení intervalu.

void halves(int data) { cout << data << ' '; if(data>1) halves(data/2); }

Exponenciální

(Při základu 2): dvojnásobné rekurzivní volání při každé iteraci.

void exponencial(data) { cout << data << ' '; if(data<=1) return; exponencial(data-1); exponencial(data-1); }