10.4.
. ? . . : ' ( ) . ', . ' ' '. , , ' ', . ' . ' . , . . , . . , . , , , . , . f(n) 0(g(n)), K n0 , f(n)(K*g(n)) n>n0. : , :
ij ( ) =
= 2 + 5* + 100.
:
( ) = 1,1* 2.
O ( ). :
1. O(*f)= O(f).
2. O(f*g) = O(f)* O(g) O (f/g)= O(f) /O(g).
3. O(f+g) O(f) O(g). , f g .
,
O(1,5*N)=O(N).
,
O((17*N)*N)= O(17*N)*O(N) = O(N)*O(N) = O(N*N)= O(N2).
, ,
O(N5 + N2) = O(N5).
10.4.1.
O(1)
. - , , .
O(N)
, .
|
|
|
O(N2), O(N3), O(Na)
. O( N2) , O (N3)
O(Log(N))
, N. , .
O(N*log(N))
, , , , ᒺ .
O(2N)
. , - .
10.4.2.
. , .
,
... O(1)
... O(1)
S1;... O(1)
S2... O(2)
IF THEN...
S1 O(1) (2)
ELSE ()
S2 (* *)
FOR I:=l N DO... O(N * 1)
S1
END
. (1), (2) () SI, S2 .
. , , , . , .
. , .
For i:=1 to N do
Begin
...
End;
O(N), N , O (1). , .
For i:=1 to N do
For j:=1 to N do
Begin
...
End;
O(N2).
10.4.3.
ϳ (. 1.26). : ( , , ) ( ).
0(H)= 0(1)+ 0(1)+0(1)=0(1);
0(I)= 0(N)*(0(F)+ 0(J)) = 0(N)*0 ( ) = 0(N);
0(G) = 0(N)*(0(C) + 0(I)+ 0(K)) = 0(N)*(0(l)+ 0(N) + + 0(1)) = 0(N2);
0(E) = 0(N)*(0(B) + 0(G) + 0(L)) = 0(N)*0(N2) = 0(N3);
0(D)= 0(A)+ 0(E)= 0(1)+ 0(N3)= 0(N3)
, 0(N3).
, 90% 10%
Writeln('B ');
A Readln(N);
small:=l;
While small < N do
begin
B { next:=small;
While next <= N do
Begin
C { last:=next;
While last<=N do
Begin
D if (last<=small*2) and (next<=small*2) and
(last*last=small*small-next*next) then
E G begin
I F writeln(small);
H writeln(next);
writeln(last);
end;
J { inc(last);
end;
k { inc(next);
end;
L { inc(small);
end;
. 1.26. ϳ
. , 90 % . . . . . 90 % , 30 %- 27 %- .
|
|
|
10.4.4.
.
function search(low, high, key: integer): integer; var
mid, data: integer;
Begin
while low<=high do
Begin
mid:=(low+high) div 2;
data:=a[mid];
if key=data then
search:=mid
Else
if key < data then
high:=mid-1
Else
low:=mid+1;
End;
search:=-1;
End;
. . ,
n n/21 n/22 n/23 n/24... n/2n.
- n,
n/2m<2 n< 2m + 1
n , n/2m<2,
n/2m-1>=2 2m<=n.
,
2m<=n<2m + 1.
³
m<= log2n < m + 1.
, O(log2n).
10.5.5.
f(n) ( ) . , , , , f(n) O(g(n)) , g(n) n,
lim f(n)/g(n)= const ≠ 0
f(n) g(n) .
. :
| N | ʳ |
N .
г. ( ). :
an an log2n an2 an3 n an!
---------------------------------------------------------- >
) = an,
an = 54;
6 = 54;
a=54/6 ( 1 <= < = 2).
= 1 ;
) = an log2 n,
an log2 n= 54;
n log2 6= 54;
54 9
=------ =------ ( > 2 );
6log2 6 log2 6
) = an2,
an2 = 54;
36= 54;
= ------- = 1,5 ( < 2 ).
, Oe(1,5n2).
lim Oe(n) /Om(n) = const ≠ 0;
lim 1.5n2/X = const ≠ 0;
lim 1.5n2/n2 = const ≠ 0;
, 0(n2).
:
1. .
2. .
3. .
4. .
5. .
6. .
7. .
8.
˳:
.. Delphi. Delphi. 2006 . - 1152 .
2. .. Delphi 2006. : Delphi, , Win32 .NET, 2006 . - 1152 .
