Ako meriame efektívnosť algoritmov?

Prečo nemeriame skutočný čas?

Hneď na začiatku narazíme na dôležitú otázku: Prečo nemôžeme jednoducho zmerať, koľko času program naozaj beží? Prečo potrebujeme "časovú zložitosť"?

Dôvod je jednoduchý: skutočný čas závisí od počítača, na ktorom program spúšťaš. Ten istý program pobeží inak rýchlo na tvojom počítači, starom počítači a na výkonnom serveri.

Naším cieľom je teda nájsť spôsob, ako odhadnúť rýchlosť programu len tak, že sa naň pozrieme, bez toho, aby sme ho museli spúšťať na konkrétnom počítači. Chceme oddeliť rýchlosť samotného algoritmu od rýchlosti konkrétneho zariadenia.

Ako meriame čas behu algoritmov?

Už vieme, že nechceme merať skutočný čas, pretože ten závisí od mnohých vecí, napríklad od rýchlosti konkrétneho počítača. Preto sa pozrieme na to, ako sa čas behu algoritmu meria v teórii:

• Čas behu algoritmu ($t_A(x)$): Toto je jednoducho čas, ktorý algoritmus A potrebuje na vyriešenie konkrétneho vstupu x.
• Najhorší čas behu algoritmu ($T_A(n)$): Predstav si, že pre vstup určitej veľkosti $n$ existuje nejaký "najhorší" prípad, ktorý trvá najdlhšie. Najhorší čas behu $T_A(n)$ je najväčší čas, ktorý algoritmus A potrebuje na vyriešenie akéhokoľvek vstupu veľkosti $n$. Matematicky to zapíšeme ako:

$$ T_A(n) = max(t_A(x) \text{pre všetky vstupy} x \text{s veľkosťou} n $$

Ako meriame "čas" bez hodín?

Skutočný čas vykonávania programu závisí od mnohých vecí, ako je rýchlosť procesora, disku, pamäte alebo vyrovnávacej pamäte (cache). Aby sme sa týmto detailom vyhli a mohli algoritmy analyzovať "čisto", nebudeme merať reálny čas. Namiesto toho budeme počítať elementárne operácie.

Elementárna operácia je taká operácia, ktorej vykonanie trvá vždy približne rovnaký, veľmi krátky čas. Tento čas závisí len od toho, ako je operácia implementovaná (či už priamo v hardvéri, alebo ako základná funkcia v softvéri), a nie od konkrétnych hodnôt, s ktorými operácia pracuje.

Príklady elementárnych operácií:

• Jednoduché matematické operácie (sčítanie, odčítanie, násobenie, delenie).
• Porovnávanie dvoch čísel.
• Operácie na riadenie toku programu (napríklad podmienky).

Príklady NEelementárnych operácií:

• Nájdenie najväčšieho čísla v zozname.
• Zistenie, či reťazec obsahuje iný podreťazec.
• Spojenie dvoch reťazcov (pretože dĺžka reťazcov môže byť rôzna a tým aj čas operácie).
• Výpočet faktoriálu.

Je dôležité si uvedomiť, že mnohé programovacie jazyky ponúkajú funkcie alebo príkazy, ktoré sa na prvý pohľad zdajú jednoduché, ale v skutočnosti nie sú elementárnymi operáciami, pretože za nimi prebieha viac zložitých krokov.