Ako vedieť odhadnúť rýchlosť programu bez jeho spustenia? Na algoritmus sa budeme dívať ako na postupnosť krokov. Budeme sa snažiť odhadnúť, koľko krokov algoritmus potrebuje v závislosti od veľkosti vstupu, ktorý mu dáme. Našťastie to však vôbec nie je také ťažké ako sa môže na prvý pohľad zdať. Skúste si to sami. Tu vidíte tri programy, ktoré všetky rátajú tú istú vec -- súčet prvých $n$ čísiel.
# prvy program
print((1+n)*n//2)
# druhy program
sucet = 0
for i in range(1,n+1):
sucet += i
print(sucet)
# treti program
sucet = 0
for i in range(1,n+1):
for j in range(i):
sucet += 1
print(sucet)
Myslím, že aj vám je na prvý pohľad jasné, ktorý z týchto programov je najrýchlejší a naopak, ktorý je najhorší. Vynásobiť dve čísla je totiž určite jednoduchšie a rýchlejšie, ako pričítavať po jednotkách k výsledku.
Keď sa pozrieme na druhý a tretí program, vieme veľmi ľahko povedať, koľko sčítaní, ktorý z nich potrebuje. Druhý spraví $n$ sčítaní, tretí spraví $n(n-1)/2$ sčítaní. A dá sa predpokladať, že sčítanie trvá na konkrétnom počítači vždy rovnako dlho. Zrazu teda vieme bez ohľadu na rýchlosť konkrétneho počítača povedať, ktorý je rýchlejší. Jeden totiž urobí o dosť viac sčítaní ako druhý. Operáciu sčítanie potom nazvime elementárnou operáciou -- to znamená, že táto operácia trvá počítaču krátky čas, ktorý je naviac nemenný. Aj keď je to prekvapivé, počítaču trvá rovnako dlho vyrátať $1+1$ ako $1574123+478413$.
Nezastavme sa však len pri sčítaní.
Je aj viac operácií, ktoré vie počítač vykonávať veľmi rýchlo,
a teda môžu byť považované za elementárne.
Väčšinou do nich patria všetky aritmetické operácie ako sčítanie, odčítanie,
násobenie, delenie, zvyšok po delení, všetky logické operácie -- and, or, xor, ...
Ďalej tam patrí aj príkaz priradenia (=), alebo náhľad do poľa (A[i])
či inicializovanie jednej premennej, načítanie alebo výpis jedného znaku.
Reálne je to bohužiaľ trošku komplikovanejšie,
napríklad zvyšok po delení je náročnejší ako bitový and.
Ale nám stačí takáto abstrakcia.
Pri veľkých vstupoch to málokedy hrá hlavnú úlohu a dodáva to oveľa lepšiu možnosť sa vyjadrovať.
A o tom, ako je to v skutočnosti, sa môžeme pobaviť neskôr.
Vieme teda už počítať elementárne operácie programov. Zrazu je nám úplne jasné, prečo je prvý program najrýchlejší. Stačí mu predsa spraviť len pár operácií aj pre veľké $n$. A aj u zvyšných dvoch je jasné, ktorý je lepší. Tu však problémy nekončia. Predstavme si, že máme dva programy, ktoré na vstupe dostanú jedno číslo $n$ a niečo s ním rátajú. Prvý urobí $20n$ operácií, druhý $n^2$. Ktorý z nich je rýchlejší? Pre $n<20$ je to program druhý, potom už vždy vyhrá program prvý. Intuitívne je teda prvý program lepší, veď na väčšine vstupov je rýchlejší. My si však túto intuíciu v ďalšom texte poriadne definujeme.
A presne takýto odhad ako sme videli vyššie (závislosť počtu operácii od vstupu) je to, čomu sa začalo hovoriť časová zložitosť algoritmu. Nie je to presné, ale dáva nám to o nej dostatočne veľa informácií. Napríklad vieme povedať, že ak náš program vykoná $n^2$ operácií v závislosti od čísla $n$ na vstupe, tak ak pre $n=200$ pobeží na našom počítači tento program $0.1$ sekundy, tak pre $n=400$ (teda dvakrát také veľké) pobeží náš program rádovo $0.4$ sekundy (teda $2^2$-krát tak dlho).
Matematicky sa zložitosť zapisuje použitím veľkého $O$. Napríklad výrok časová zložitosť programu je $O\left(n^2\right)$ znamená to isté, ako náš vyššie uvedený záver, že program vykoná nanajvýš rádovo $n^2$ krokov.
Na záver: Značenie $O(f(n))$, ktoré sme si tu predstavili, sa dá formálne definovať, počítanie zložitosti je predsa len o niečo exaktnejšia oblasť, ako by sa mohlo zdať. Pre jednoduché programy si však vystačíme s takýmto intuitívnym chápaním "veľkého $O$". Viac na túto tému nájdete v nasledujúcom článku Úvod do teórie časovej zložitosti.