. . , , . , , .
. f(x). tT(x), , f(x), f(x) . f(x) , tT(x) . tT(x) .
, , f(x) . sT(x), , f(x) . f(x) , ST(x) . ST(x) () .
ST(x) tT(x) .
( ).
, , IÎ , . α,
IÎ α(I) . I α(I). ,
- ( ).
-: , f(n) g(n) f(n)=O(g(n)), , f(n)≤C*g(n) nÎN.
, ,
. , . , , , . . , , , >0.
, , , . , .
. , , , .
|
|
. 100 1000 :
100 | 1000 | ||
n | N1 | 100 N1 | 1000 N1 |
n2 | N2 | 10 N2 | 31,6 N2 |
n3 | N3 | 4,64 N3 | 10 N3 |
2n | N4 | 6,64+N4 | 9,97+N4 |
3n | N5 | 4,19+N5 | 6,29+N5 |
, , .
, , . : , , .
, , . , O(n1000) n. . , , , , . , ,
.
.
={1,2,, n} , . R (, , ).
, R , AR ,
- R 2.
, , . , (n2).
2. R , iRj jRi.
, R
R:(i1,j1);(i2,j2);(it,jt),
,
.
, R , AR i- i- . O(n2), R.
3. R , i1,i2,,in ,
(*)
, R.
n! (*), , , n.
|
|
4. f(x1,,xn) x1,,xn . f(x1,,xn) , x1,..., xn, , f(x1,,xn)=1.
f(x1,,xn) ,
a1,,at .
f .
. , .
O(n3), .
f(x1,,xn) , .. :
.
.
. 2n .
NP
NP , .. һ. , I NP , I
, (I) , I, , (I), I . (I) I.
.
1. ={1,2,,n}. R , : (R)=i1i2in. (R), R, (*) R . , NP.
2. .
f(x1,,xn) , . , f(x1,,xn), , f(x1,,xn) .
.
NP .
.
:
-3 | -2 | -1 | n | ||||||||||||
* | x1 | x2 | ... | xn | |||||||||||
| |||
,
() (), . , , qY qN, һ . :
1- . x=x1xn I, 1. 0 *. 1. () -1,-2,-3,. 1- ()*q1x.
2- . ()*q1x. qY, , ()*q1x.
, x, (), ()*q1x .
|
|
( ) t1(x) 1, .., , ;
t2(x) - 2, .., , , tT .
, .
, .
NP , , , .
NP. , . , (1992).
. ÎNP, , O(2p(n)), n .
.
1. O(n) . . , .
2. , (nc), ( ). , , , . . , (n 1000000) . - , . 3: O(n3), O(n2), O(n log(n)), .
: .
3. , (n), ( E).
: f(x1,,xn) g(x1,,xn). 2n.
4. NP- .
: . n n! . n! , 2n.
. , , , . , , NP .
, . NP . .
.
1. . , . .
2. . .
3. . .
4. .
5. .
6. . .
, NP , .