Príklady

Prejdime si zopár príkladov programov a skúsme určiť ich časovú zložitosť v O-notácií.

1. príklad

x = 0
for i in range(4 * n):
    x = x + 2 * i
Riešenie Tento program má časovú zložitosť $O(n)$. Prejdime si riadky programu: - `x = 0`: Táto operácia sa vykoná len raz, a keďže ide o elementárnu operáciu, jej časová zložitosť je $O(1)$. - `for i in range(4 * n)`: Toto je hlavný cyklus programu. Určuje, koľkokrát sa zopakujú operácie vo vnútri. Cyklus sa vykoná $4n$ krát (pre $i$ od 0 po $4n-1$). Keďže počet opakovaní je $4n$ a konštantu zanedbávame, zložitosť tohto cyklu je $O(n)$. - `x = x + 2 * i`: Operácie vo vnútri cyklu (násobenie, sčítanie a priradenie) sú elementárne operácie, každá z nich trvá konštantný čas, teda $O(1)$. Keďže sa operácie vo vnútri cyklu opakujú $4n$-krát, celková časová zložitosť programu je daná počtom jeho opakovaní. V O-notácií zanedbávame konštanty, takže celková zložitosť programu je $O(n)$.

2. príklad

j = 1
while j*j <= n:
  j += 1
Riešenie Tento program má časovú zložitosť $O(\sqrt{n})$. Znovu, časová zložitosť bude závisieť od počtu opakovaní cyklu. Podmienka cyklu kontroluje, či je $j^2$ menšie alebo rovné $n$. Cyklus pokračuje, kým je táto podmienka splnená. - Premenná $j$ sa v každej iterácií zvyšuje o 1. - Cyklus sa zastaví, keď $j^2$ prekročí $n$, čiže $j \approx \sqrt{n}$. - Napríklad, pre $n=10$ cyklus pobeží až kým $j$ nebude 10. Ak potom $j$ dosiahne hodnotu 11, $11^2 = 121$, čo je väčšie ako $10^2$, a cyklus sa zastaví.

3. príklad

a = 0
k = n * n
while k > 1:
    for j in range(0, n * n, 1):
        a += 1
    k /= 2
Riešenie Tento program má zložitosť $O(n^2 log(n))$. Začnime analýzou vnútorného `for`-cyklu. Operácia v ňom (`a += 1`) trvá konštantný čas. Samotný cyklus sa vykoná $n^2$-krát, teda jeho celková časová zložitosť je $O(n^2)$. Vonkajší cyklus je o niečo komplexnejší. Premenná $k$ začne na hodnote $n^2$. V každej iterácií cyklu sa hodnota $k$ vydelí dvomi (`k /= 2`). Tento cyklus bude bežať pokým sa hodnota $k$ nezníži na 1 alebo menej. Koľkokrát musíme $n^2$ vydeliť dvomi, kým dostaneme $k = 1$? Je to ekvivalentné nájdeniu riešenia v rovnici $2^x = n^2$. Riešením tejto rovnice je $x=log_2(n^2)$. Pomocou vlastností logaritmov je to ekvivalentné s $x=2 log_2(n)$. Konštantný faktor 2 a základ logaritmu zanedbáme, takže vonkajší cyklus sa vykoná $O(log(n))$-krát. Celková časová zložitosť: Keďže vnútorný cyklus ($O(n^2)$) sa vykoná pri každej iterácií vonkajšieho cyklu ($O(log(n))$), celková zložitosť bude súčinom zložitostí týchto cyklov, teda $O(n^2 log(n))$.

4. príklad

arr = [...] # len(arr) = n
blocks = 0
i = 0
while i < len(arr):
    blocks += 1
    j = i + 1
    while j < len(arr) and arr[i] == arr[j]:
        j += 1
    i = j
Riešenie Tento program má časovú zložitosť $O(n)$. Začnime analýzou dvoch cyklov, ktoré vidíme: vonkajší while cyklus s premennou $i$ a vnútorný while cyklus s premennou $j$. Vnútorný cyklus: `while j < len(arr) and arr[i] == arr[j]` - Operácia vo vnútri cyklu (`j += 1`) trvá konštantný čas, teda $O(1)$. - Tento cyklus sa spúšťa pre každú iteráciu vonkajšieho cyklu. - Kľúčové pozorovanie: Premenná $j$ sa nikdy neresetuje na 0 v rámci vonkajšieho cyklu. Namiesto toho začína od $i + 1$ a pokračuje v posúvaní dopredu. Po skončení vnútorného cyklu sa hodnota $j$ priradí do premennej $i$. To znamená, že $i$ "preskočí" všetky prvky, ktoré už boli spracované vnútorným cyklom $j$. Vonkajší cyklus: `while i < len(arr)` - Operácie vo vnútri tohto cyklu (ako `blocks += 1`, `j = i + 1`) trvajú konštantný čas, teda $O(1)$. - Hlavným faktorom je to, koľkokrát sa vykoná vnútorný cyklus. Aj keď tu máme dva vnorené while cykly, celková časová zložitosť nie je $O(n^2)$. Prečo? Predstavte si, že ukazovatele $i$ a $j$ začínajú na nule a pohybujú sa smerom ku koncu poľa. Každý z týchto ukazovateľov ($i$ aj $j$) prejde celým poľom maximálne raz. - Ukazovateľ $j$ sa v každej iterácii vnútorného cyklu posúva dopredu o 1. Celkovo sa $j$ posunie od 0 po `len(arr) - 1)` len raz za celý beh algoritmu. - Ukazovateľ $i$ sa posúva na pozíciu, kde sa zastavil $j$, čo znamená, že aj $i$ prejde poľom len raz (preskakuje už spracované bloky). Pretože každý prvok poľa `arr` je navštívený a spracovaný len konštantný počet krát, celkový počet operácií je priamo úmerný dĺžke poľa $n$. Celková časová zložitosť tohto algoritmu je teda $O(n)$.

5. príklad

x = 0
for i in range(n):
    for j in range(m):
        x += 1
Riešenie Tento program má časovú zložitosť $O(nm)$. Rozoberme si jednotlivé časti: - `for i in range(n)`: Tento vonkajší cyklus sa vykoná $n$-krát. - `for j in range(m)`: Tento vnútorný cyklus sa vykoná $m$-krát pre každú iteráciu vonkajšieho cyklu. - `x += 1`: Operácia s konštantnou časovou zložitosťou $O(1)$. Celková časová zložitosť: Vzhľadom na to, že vnútorný cyklus beží $m$-krát pre každú z $n$ iterácií vonkajšieho cyklu, operácia `x += 1` sa vykoná celkovo $n \cdot m$ krát. Preto je celková časová zložitosť programu $O(nm)$.
Späť Ďalej