Samozřejmě nás zajímá, jak dlouho program poběží. Konkrétně by se hodila nějaká záruka ve stylu – zpracovat megabajt dat bude trvat nejvýše půl minuty. Dopočítat se k něčemu takhle konkrétnímu by byla strašná dřina, proto si v následujících několika odstavcích vyrobíme teorii, která sice nebude vůbec tak přesná, ale půjde spočítat snadno.

Časová složitost

Na začátku byl program, který řeší nějakou konkrétní úlohu, například hledání cesty v bludišti. Důležité je, že ten program zvládne libovolně složité zadání, akorát ho to zpomalí: třeba to znamená, že bludiště může být libovolně velké. Spíš než skutečná rychlost programu nám následující propočty řeknou, jak se program popasuje s hodně velkým zadáním. Nedozvíme se žádný konkrétní čas, jen ho zhruba odhadneme jako nějakou funkci.

Když program spustíme se zadáním velikosti N, dejme tomu, že poběží nejvýš t(N) vteřin. To je ten skutečný čas, který pro většinu smysluplných programů nedovedeme spočítat přesně. Namísto toho si vycucáme z prstu nějakou úhledně vypadající funkci f(N) a zkusíme dokázat, že platí nerovnice t(N) ≤ c · f(N). V té nerovnici navíc vystupuje číslo c, což by vlastně mohlo být nějaké opravdové číslo – jakmile dopíšeme program, mohli bychom říct, že pro jakékoliv zadání velikosti N poběží nanejvýš f(N) · 42.0 vteřin. Protože jsme ale líní, a dopočítávat se tam k té čtyřicet dvojce by nám mohlo zabrat pár let, tak prohlásíme prostě, že pro náš program nějaké číslo existuje a dál nás to nezajímá. Hodnota c se pochopitelně nesmí měnit, když měníme N, protože jinak by ta nerovnice platila úplně vždycky.

Tyhle konstrukce vypadají možná nepřehledně, ale v matematice je to úplně normální postup – horko těžko definujeme nějaké číslo, a vzápětí řekneme, že nás vlastně nezajímá. Je zvykem namísto naší nerovnice psát rovnítko a velké O, například „čas = O(N2)“ znamená, že se dá najít nějaké dost vysoké c a pak bude zaručeně platit čas ≤ c · N2. Když se to napíše tak, žádné céčko už ani není vidět.

Ještě jedna formální poznámka se týká funkcí, které vracejí občas i nulu nebo dokonce záporná čísla. Násobení nuly dá vždycky nulu, ať si vybereme c jakékoliv. Pro takové případy si v definici navíc dovolujeme podle potřeby ignorovat, co se děje na malém zadání.

Ještě probereme paměťovou složitost a ukážeme si, k čemu může být dolní odhad složitosti.