Merjenje kompleksnosti algoritmov

Za primerjavo različnih algoritmov uporabljamo dva merila:



• Prostorsko zahtevnost algoritma, s katero definiramo velikostni red zahtev po pomnilniškem prostoru.
• Časovno zahtevnost algoritma, s katerim definiramo velikostni red zahtevnosti procesiranja algoritma.

Veliki O:

 

Kompleksnost O(1) se imenuje:	konstantna kompleksnost
Kompleksnost O(N) se imenuje:	linearna kompleksnost
Kompleksnost O(NK) se imenuje:	polinomska kompleksnost
Kompleksnost O(YN)  se imenuje:	eksponentna kompleksnost

 

Kakšne je O, če je število operacij definirano z n?

 

n2 + 3n + 99 =	O(n2)
99n4 + 10n6 + 331256 =	O(n6)
3n + 25n2 - 64n3 =	O(n3)
n! + n2 =	O(n!)
9932 =	O(1)
7 * log2(n) + 10n =	O(n)
n*log2n + 4n =	O(n*log2n)

 

Rast kompleksnosti funkcij

 

log(n)	n	n*log(n)	n2	n3	2n
0	1	0	1	1	2
1	2	2	4	8	4
2	4	8	16	64	16
3	8	24	64	512	256
4	16	64	256	4096	65536
5	32	160	1024	32768	4294967296
6	64	384	4096	262144	(glej 1)
7	128	896	16384	2097152	(glej 2)
8	256	2048	65536	16777216	????

 

 

(1) Računalnik, ki izvaja 1 GFLOP operacij na sekundo bi to izvajal 5000 let

(2) Aproksimativno 500 miljard let

 

• Enostavne operacije – branje, pisanje, primerjave, pogoji, prireditveni stavki,
• Zaporedje operacij -- S1; S2;

 

Štejemo operacije, ki jih mora računalnik izvesti.

                                                O(1)

                                   O(S1) + O(S2)