1.2.
, - . .
1. O (k*f) = O (f),
2. O (f*g) = O (f)* O (g),
3. O (f+g) = Max ( O (f), O (g)).
k , f g - .
, , , O ( 2 *n) = O (n). . , O (( 10 *n)* n) = O (n)* O (n) = O (n2). () . , O (n4 + n2) = O (n4).
-:
a) (1) , , .
b) (n) , , n ,
c) (n2), (n3), , , n ,
d) (log(n)) , , , -,
e) ( 2 n) , , .
. , .
1.3.
()
(). , . , java System.CurrentTimeMillis (), System.nanoTime() . .
, , :
long start = System.nanoTime();
// ,
long end = System.nanoTime();
long traceTime = end-start;
traceTime .
. , . (, 1000 10 000 ), traceTime .
2. ()
|
|
. , , , .. (1). , , . n, (n) ..
, , . , . , ( ) . n. (n). . , .
. , . , , , -. , . -, .
.
2