Časovna zahtevnost algoritma

Iz E-študij, proste zakladnice študentskega znanja

Skoči na: navigacija, iskanje

Časovna zahtevnost algoritma je (poleg preverjanja pravilnosti) najpomembnejši del analize algoritma.

Na zahtevnost vplivajo

število podatkov
velikost posameznega podatka
vrstni red podatkov
druge lastnosti posameznega podatka
relacije med posameznimi podatki

Večinoma je preprosto ugotoviti katera lastnost vhodnih podatkov vpliva na časovno zahtevnost, pri bolj zapletenih algoritmih pa je potrebna posebna analiza za določanje ustreznega parametra velikosti podatkov. Temu parametru pravimo velikost problema:

n: velikost problema

Ker je časovna zahtevnost algoritma funkcija parametra n, jo označujemo:

T(n): časovna zahtevnost

Pri določanju časovne zahtevnosti lahko iščemo:

velikostni red funkcije T(n)
dejanski pričakovani čas izvajanja

Vsebina

1 Velikostni red časovne zahtevnosti
2 Amortizirana analiza časovne zahtevnosti
- 2.1 Povezave
3 Ocena dejanskega časa izvajanja
4 Razlike med razredi zahtevnosti
5 Povezave

Velikostni red časovne zahtevnosti

Za določitev velikostnega reda lahko čas izvajanja abstrahiramo v enote in namesto merjenja časa predpostavimo, da je čas izvajanja vseh osnovnih operacij enak eni časovni enoti. Ker nas zanima samo velikostni red izvajanja operacij si pomagamo z asimptotičnim zapisom s funkcijami:

O(·)

Za računanje najslabšega možnega primera (worst case scenario).

Če želimo oceniti časovno zahtevnost algoritma v povprečju moramo izračunati matematično upanje.

Ω(·)

Θ(·)

Amortizirana analiza časovne zahtevnosti

Amortizirana analiza je natančnejša analiza, ki omogoča, da dobimo bolj natančno oceno časovne zahtevnosti, ker upoštevamo spreminjanje stanja v abstraktnem podatkovnem tipu. Pri npr. dodajanju elementov v tabelo, se tabela daljša, in je zato preiskovanje takšne tabele vse bolj časovno zahtevno.

Osnovna ideja je vpeljava funkcije, katero imenujemo potencial.

$\!\phi(S)$: potencial stanja S

Potencial stanja oceni relativno zapletenost stanja S glede na operacije, katere izvajamo nad abstraktnim podatkovnim tipom.

potencial: funkcija ki oceni kompleksnost podatkovne strukture

m: število operacij

$\! S_0, S_1, ... , S_m$

amortiziran čas i-te operacije

i = 1 ... m

definiramo kot dejanski čas + razliko v potencialu

$\! a_i = t_i + \Phi (S_i) - \Phi(S_{i-1})$

na koncu nas zanima vsota vseh časov:

$\! \sum_{i=1}^m t_i = \sum_{i=1}^m a_i + \Phi (S_o) - \Phi (S_m)$

$\! \sum_{i=1}^m t_i \le \sum_{i=1}^m a_i$

potencial moramo vedno izbrati tako, da je potencial na koncu vedno večji ali enak potencialu na začetku, na ta način imamo garantirano da je zgornja razlika negativna ali enaka nič - s tem dobimo zgornjo mejo

$\! \Phi (S_m) \ge \Phi(S_0)$

algoritem ki prišteva 1 binarnemu števcu

          .-k-.
          
1 0 1 1 0 1 1 1
             +1
---------------
1 0 1 1 1 0 0 0

algoritem od desne proti levi spreminja enke v ničle, prvo ničlo pa spremeni v enko

najslabši možni primer: vsi biti so enke

število bitov: $\! \log_2(n)$

časovna zahtevnost $\! O(\log_2(n))$

v polovici primerov bomo samo prvi bit spremenili v 1

v četrtini primerov bomo spremenili drugi bit v 1

najslabši možni primer je samo 1, zato je zgornja meja slaba ocena časovne zahtevnosti

z amortizirano analizo definiramo nek potencial:

$\! \Phi$

število enic v števcu

zanima nas amortiziran čas:

a_i = t_i+1-k

$t i = k + 1$

$\! \Phi (S_{i-1}) \rightarrow \Phi(S_i)$

k-1

število enic v novem stanju

$\! \Phi (S_{i-1}) = \Phi(S_i) + k-1$

zaporedje m operacij ima časovno zahtevnost:

$\! O(m \cdot 2) \Rightarrow O(m)$

v povprečju je ena operacija reda konstante:

$\! O(2) \Rightarrow O(1)$

posamezna operacija je lahko počasna

Povezave

Ocena dejanskega časa izvajanja

Zanimajo nas dejanske sekunde, ne samo asimptote. Zato so konstante prav tako pomembne.

Ta čas lahko dobimo le tako da ga izmerimo pri različnih velikostih problema.

Dobimo tabelo in graf

n v relaciji s T(N)

iz tega želimo dobiti funkcijo, ki bo uporabna za napoved

zanima nas zgornja meja

Če algoritem poznamo imamo asimptotično oceno (nek O).

Če vemo da ima kvadratično časovno zahtevnost:

$\! T(n) = a \cdot n^2 + b \cdot n + c$

imamo enačbo s 3 neznankami

potrebujemo tri meritve:

n_1 - T(n_1)

n_2 - T(n_2)

n_3 - T(n_3)

Če želimo vedeti ali so konstante a,b,c res (vsaj približno) konstantne naredimo še več meritev in sistem enačb rešujemo z različnimi množicami teh velikosti. Navadno jemljemo zaporedne 3.

Če konstante niso konstante, potem predpostavka funkcije (vse ostalo razen konstant) ni pravilna (lahko raste hitreje, počasneje...)

Algoritem za katerega ne vemo kakšna časovna funkcija stoji za njim

n	T(n)	c	e
5	13,8
6	83,6
7	388,6
8	1796,2
9	8753,6
10	44421,4

Rast funkcije očitno ni linearna, zato ne moremo predpostaviti funkcije, ki raste linearno ali počasneje.

Predpostavimo da gre za polinom katerega stopnje še ne vemo.

Predpostavimo, da bo naša funkcija

$\! T(n) = c \cdot n^e + ...$ (člene nižjega reda spustimo)

ocenjujemo po 2 vrstici tabele skupaj:

c	e
$\! 1,7 * 10^{-6}$	9,88
$\! 1,5 \cdot 10^{-6}$	9,97
$\! 8 \cdot 10^{-8}$	11,46
$\! 1,3 \cdot 10^{-9}$	13,45
$\! 1,7 \cdot 10^{-11}$	15

rast je hitrejša od polinomske, najverjetneje eksponentna

za osnovo vzamemo

$\! T(n) = c \cdot 2^{e \cdot n} + ...$

c₁	e₁
$\! 1,7 * 10^{-3}$	2,60
$\! 8,3 \cdot 10^{-3}$	2,22
$\! 8,6 \cdot 10^{-3}$	2,21
$\! 5,6 \cdot 10^{-3}$	2,28
$\! 3,9 \cdot 10^{-3}$	2,34

ker nam manjkajo členi nižjega reda konstante niso konstantne, ohranjajo pa velikostni red, zato je hipoteza relativno dobra

Razlike med razredi zahtevnosti

Funkcije, katere pridejo v praksi v poštev za ocenjevanje časovne zahtevnosti:

f(n)

konstanten algoritem

$\! 1$

raste izredno počasi - najhitrejši algoritmi

$\! \log n$

linearna funkcija

$\! n$

$\! n \cdot \log n$

polinomi

$\! n^2$

$\! n^3$

$\! n^4$

eksponentni algoritmi - najpočasnejši algoritmi

$\! 2^n$

asimptotične relacije

$\! a > b > 0, c > 0 \Rightarrow n^a > c \cdot n^b$

od nekega n-ja naprej zagotovo prevlada funkcija ki ima večji eksponent

$\! a > 0 , b > 1, c > 0 \Rightarrow n^a > c \log_b n$

polinom prevlada nad logaritmom pri čemer je lahko a poljubno majhen

$\! a > 1, b > 0, c>0 \Rightarrow a^n > c \cdot n^b$

ko je n zadosti velik, bo zagotovo eksponentna funkcija prevladala polinomsko funkcijo

$\! a > 1, c > 0 \Rightarrow n! > c \cdot a^n$

faktoriela prevlada eksponentno funkcijo ker hitreje raste

$\! c > 0 \Rightarrow n \log n > c \log n!$

f(n)	f(n+1) - f(n)	10x hitrejši računalnik izračuna problem v času n₀
$\! 1$	0	/
$\! \log n$	$O \left( \frac{1}{n} \right)$	$\! n_0^{10}$
$\! n$	O(1)	$\! 10 n_0$
$\! n \cdot \log n$	O(log n)	$\! < 10 n_0$
$\! n^2$	O(n)	$\! 3,16 \cdot n_0$
$\! n^3$	$\! O(n^2)$	$\! 2,15 \cdot n_0$
$\! n^4$	$\! O(n^3)$	$\! 1,78 \cdot n_0$
$\! 2^n$	$\! O(2 ^n)$	$\! \le n_0 + 4$
$\! n!$	$\! O( (n+1)! )$	$\! \le n_0 + 1$