, , , , .
.
.
, , , , , . () .
() n . , (), 1. () . () , . , . () . [2]
.18.
. 18
Pascal 1, MaxMin.pas.
.
. , . . . , . [6,7]
.
. X = 6, 10 :
3 5 6 8 12 15 17 18 20 25.
1- . : m = = 5.
6 < [5], , 5.
3 5 6 8 12 15 17 18 20 25.
2- . 4 , : m = = 2.
6 > [2], , :
3 5 6 8 12 15 17 18 20 25;
3- . , m = = 3.
3 5 6 8 12 15 17 18 20 25;
[3] = 6. , 3.
- .19:
|
1, Binar.pas.
.
k - X . q. X : , X [ q ], X [ q ] X [ q ]. , , . k*N, . . N2, .
|
|
, , . , : . , . , (, , ), , ( ). , , t . , .
, t , , . S, , . , S ≤ . , t S. t .
.
, . . ( ), ( ). ( ) . , , , . . . , . , , . , n .
,
, . , , P:
. , . . , :
|
|
, :
k .
:
. T(n) n . f(n).
, T(n) = O(f(n)), |T(n)| ≤ C|f(n)| n > n0. T(n) , f(n) . f(n), , . . |T(n)| ≥ C1|f(n)|.
T(n) = Θ(f(n)) , T(n) f(n). , ,
T(n) = Θ(p(n)), , p(n) = Θ(n k), T(n) = Θ(n k). , . k = 1 T(n) = Θ(n) .
A1 A2 , k1 < k2, , . , , . ,
n < 10 , , . , , n0 ( n0 = 10), n > n0 .
, . , .
. , , , , . , :
, ( ), , , , , . , . 106 /.
n | |||||
0.00001 | 0.00002 | 0.00003 | 0.00004 | 0.00005 | |
0.0001 | 0.0004 | 0.0009 | 0.00016 | 0.00025 | |
0.001 | 0.008 | 0.0027 | 0.0064 | 0.125 | |
0.1 | 3.2 | 24.3 | 1.7 | 5.3 | |
0.001 | 1.0 | 17.9 | 12,7 | 35,7 | |
0.059 | 58 | 6.5 | 385500 | 200 |
. ,
.
. , ( ). , . , , , , . . Θ (1).
|
|
, , . . . , .
B n(B) A n(A) ( B A), B A n(A) n(B).
: Θ(AB) = Θ(A) Θ(B).
, . . ni(B) i , , .
,
Θ(A + B) = Θ(A) + Θ(B) = max{Θ(A), Θ(B)}.
, . , . , .[11]
. . . 15
. , , , : n − 1, , , 1 . n − 1 , , , n/2 . ( )
Θ(n) Θ(n) = Θ(n2),
( )
Θ(1) Θ(n) = Θ(n).
: , , . . .