..
..
2000
681.142.2
... : . : - , 2000. 62.
, , . . NP- NP- . , , , .
. 11. .: 9 .
- .
:
.., .
,
, ;
..,
- ;
..,
- .
, 2000
.., 2000
( ) , , , , , NP - NP - . - .
, , , , . , , .
. .
|
|
, . .
, , , , . , .
: () . . , , : 5 10 10000 . , . : , , , , , , , .. , .
, , , . , , , .
O -. ?
. f(n) g(n) . , f(n) = O(g(n)) (: f(n) O- g(n)), C > 0 N, n > N : |f(n)/g(n)| < C. , n ¥ f(n) , g(n), , , , .[1]
O- ? , f(n) , , . g(n) , f(n) = O(g(n)), , , .
, : O(n2 ). , n, , 10 , 102= 100 . T (n) (.. ) T (n) (.. ). T (n) .
|
|
O - n. (, ) , .
O - . :
f(n) = O(k×g(n)), k , f(n) = O(g(n)) (.. ).
f(n) = O(g1(n)+g2(n)) g2(n)/g1(n) 0, f(n) = O(g1(n)) (.. ).
, O(g(n)) , , , g(n). f(n) = O(g(n)) , Î, . , , : f(n) O- g(n), O-.
, , . , , , .
(, ), O(n) , . , (, ).
(, n ), O(n2). , , ( , , ).
n k n-1, k n-2 .., O(kn).
n , O(log2(n)). , O- ( ), O(log(n)).
, : n (.. T(n) = n + 2T(n/2)), O(n×log(n)).
, , , , , , . , , , , . , . , - . , , .