Ako odhadovať zložitosť?

Už vieme, že skutočný čas, ktorý program potrebuje, závisí od konkrétneho počítača. Preto si potrebujeme nájsť iný spôsob, ako odhadnúť rýchlosť programu len tak, že sa pozrieme na jeho kód. Ako na to?

Budeme sa pozerať na algoritmus ako na postupnosť krokov. Naším cieľom je odhadnúť, koľko takýchto krokov program potrebuje v závislosti od veľkosti vstupu, ktorý mu dáme. Neznie to zložito, však? A naozaj to nie je také ťažké, ako sa možno na prvý pohľad zdá.

Pozrime sa na príklad. Tu sú tri rôzne programy, ktoré všetky vypočítajú to isté – súčet prvých $n$ čísel:

# Program 1
print(n * (n + 1) // 2)

# Program 2
sucet = 0
for i in range(1, n + 1):
    sucet += i
print(sucet)

# Program 3
sucet = 0
for i in range(1, n + 1):
    for j in range(i):
        sucet += 1
print(sucet)

Intuitívne asi cítiš, ktorý program je najrýchlejší a ktorý najpomalší, však? Vynásobiť dve čísla je určite rýchlejšie ako pridávať jedno číslo k druhému opakovane.

Späť k elementárnym operáciam

Keď sa pozrieme na programy, vieme ľahko určiť, koľko operácií urobí každý z nich.

  • Program 1 je najefektívnejší. Bez ohľadu na veľkosť $n$, vždy vykoná len niekoľko základných operácií: jedno sčítanie (n + 1), jedno násobenie (* n), a jedno celočíselné delenie (// 2). Počet operácií je teda vždy rovnaký (3), nezávisle od $n$.
  • Program 2 urobí $n$ sčítaní. (Predstav si, že pre n=5 sčíta 1+2+3+4+5, teda 5 sčítaní).
  • Program 3 urobí $(n+1)n/2$ sčítaní. Prečo? Pozrime sa na vnútorný cyklus for j in range(i):
  • Keď je $i$ rovné 1, vnútorný cyklus prebehne 1-krát (j bude 0).
  • Keď je $i$ rovné 2, vnútorný cyklus prebehne 2-krát (j bude 0, 1).
  • Keď je $i$ rovné 3, vnútorný cyklus prebehne 3-krát (j bude 0, 1, 2).
  • ...
  • Keď je $i$ rovné $n$, vnútorný cyklus prebehne $n$-krát. Celkový počet spustenia vnútorného cyklu bude teda $1 + 2 + 3 + \dots + n$. Toto je známy súčet prvých $n$ čísiel, ktorý možno vypočítať ako $n(n+1)/2$. Preto Program 3 vykoná oveľa viac opeácií. (Pre $n=5$ je to 10 sčítaní).

Keďže sčítanie je jednou s elementárnych operácií, zrazu vieme bez ohľadu na rýchlosť počítača povedať, ktorý program je rýchlejší. Jeden totiž urobí oveľa viac sčítaní ako tie ostatné.

Sčítanie je elementárna operácia, čo znamená, že počítaču trvý jej vykonanie krátky a nemenný čas. Aj keď je to možno prekvapivé, počítaču trvá rovnako dlho vypočítať $1+1$ ako $1574123+478413$. (Aspoň pre rozumne veľké čísla)

Ďalej