6 , 12 , 1 , .
1. . . + CD. .: , 2014. 272.
2. .., .. . .: -. , 2004. 304 .
3. , . ., , . .: .. .: , 2000. 384 .
4. .., . Java. - .: , 2003. 671 .
1
1.1.
, .
:
1) ( );
2) ( , );
3) ( , );
4) ( , ).
( ):
1) ( , , );
2) ( , );
3) ( );
4) .
, :
a) ( );
b) .
( n, n2 ..). , .
1. ( )
. , . , .
1. : <-- b, , 1;
2. a[i ]: ( (a)+ i * ), , 2;
3. : (*, /, -, +), , 1;
4. : a < b, , 1;
5. (l 1) {or - |, and - &&, not -!} (l 2), , 1;
.
1. k
, .
|
|
Θ =f1+f2++fk,
fk k - .
2.
If () // then
else
.
, Then () Else (1- ) :
Θ = fthenp + felse(1-p),
fthen felse .
3.
for (i=1; i<= n;i++){
}
:
Θ =1+3* n + n * f ,
f ,
n ,
3* n .
, , . , , . Θ , ().
.
1. n* n.
SumM (A, n; Sum)
Sum <-- 0
For i <-- 1 to n
For j <-- 1 to n
Sum <-- Sum + A[i,j]
end for
Return (Sum)
End
n , , -. :
Θ (n)=1+ f i = 1 + 1+ 3* n + n * f j =
1 + 1+ 3* n + n *(1+ 3* n + n *(2 + 2 + 1 + 1))
= 2 + 3 n + n *(1 + 3 n + 6 n) = 9n2+4 n +2. (1.1)
1.1.
.
(1.1) . , , . Θ (n) , n , f(n). .
Θ ().
f(n) = Θ(g(n)), c1, c2 >0 n 0 , c1*g(n)<=f(n)<=c2*g(n), n>n 0.
g(n) - f(n). , Θ , , g(n) .. c1 c2.
, Θ , . , .
Ο (), , , g(n).
f(n) = Ο(g(n)), c >0 n 0 , 0<= f(n)<=cg(n), n>n 0.
Ω (), , , g(n).
|
|
f(n)= Ω(g(n)), c>0 n0 , 0<= cg(n)<=f(n), n>n 0.
, , . . , , , , .
, Θ (n) (. (1.1)). . .
a) ;
b)
c) .
, 1 ( ) O (n2), 2 ( ) O (n). :
for (i=1; i<= n;i++)
for (j=1; j<= n;j++)
for (k=1; k<= n;k++)
{ }
O (n3), .. .