Pod odhadom časovej zložitosti rozumieme odhad času, ktorý bude program trvať, v závislosti od vstupných premenných. Tento čas je priamo úmerný počtu elementárnych operácií, ktoré program vykonáva - priradenie jednoduchej premennej, porovnanie jednoduchých premenných, aritmetické operácie, atď. Väčšinou sa zaujímame o to, ako dlho beží program v priemernom, alebo najhoršom prípade (čiže si všímame priemerný, alebo maximálny čas vykonávania programu). Analogicky odhad pamäťovej zložitosti je odhad veľkosti použitej pamäti v bajtoch v závislosti od vstupných premenných.
Väčšinou nás nezaujímajú presné hodnoty (niekto má rýchlejší počítač, na niektorých počítačoch má integer 2 a na iných 4 bajty a pod.), preto používame tzv. \(O\)-notáciu. Hovoríme, že funkcia \(f(n)\) (napr. čas behu programu v milisekundách v závislosti od veľkosti vstupu \(n\)) je \(O(g(n))\) (\(g(n)\) je tiež funkcia), ak existuje taká konštanta \(c\), že pre všetky dostatočne veľké \(n~(n>n_0)\) je \(f(n) \leq c \cdot g(n)\).
Napríklad, ak program pre vstup veľkosti \(n\) nebeží nikdy viac ako \(T(n)=\frac{1}{2}n^3 + 5n\log(n) + 83\) mikrosekúnd, môžeme povedať, že má časovú zložitosť \(O(n^3)\). Ak program potrebuje najviac \(M(n) = 3n\log_2(n) + 150n + 15\) bajtov pamäti, povieme, že má pamäťovú zložitosť \(O(n\log(n))\). (Poznamenávame, že ak je nejaká funkcia \(O(n^2)\), tak je aj \(O(n^3)\)) atď. Vždy sa však snažíme nájsť čo najmenšie horné ohraničenie, t.j. funkciu, ktorá čo najpomalšie rastie.)
Niekoľko príkladov (v pseudokóde)
sucet = 0
for i in 1..n:
for j in 1..m:
for k in 1..j:
sucet = i+j+k
Predchádzajúci program má časovú zložitosť \(O(n\cdot m^2)\). Posledný riadok programu sa vykoná \( \frac{1}{2} n \cdot m(m+1)\)-krát.
nacitaj n cisel do pola A
b = 0
e = n
while e-b > 1:
m = (b+e)/2
pocet = 0
for i in 1..n:
if A[i] < m: pocet += 1
if pocet > n/2: e = m
else: b = m
Predchádzajúci program má časovú zložitosť \(O(n\log(n))\). Vnútro while-cyklu sa vykoná \(O(n\log n)\)-krát, pretože \((e-b)\) sa po každom kroku zmenší na polovicu. Vnútro while-cyklu má časovú zložitosť \(O(n)\).
Čas poslednej úpravy: 10. február 2015 20:04