, . , 1 ., 10 ., 2 . 5 . . , . . O(f(n)), N, , f(N). , A[NxN] .
for i:=1 to N do
begin
max:=A[i,1];
for j:=1 to N do
begin
if A[i,j]>max then
max:=A[i,j]
end;
writeln(max);
end;
i 1 N. i, j 1 N. N , N . N*N. O(N^2).
, , . , N^3+N. O(N^3). N. , N=100, N^3+N=1000100 N=1000000 100, 0,01%.
O . 3N^3 , O(N^3). O(N) .
. .
, . (, ), . O(N) , . , .
: Slow O(N^3) Fast O(N^2).
procedure Slow;
var
i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do
{- }
end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
Slow;
end;
procedure Both;
begin
Fast;
end;
Fast Slow, . O(N^2)*O(N^3)=O(N^5).
, : O(N^2)+O(N^3)=O(N^3). :
procedure Slow;
var
i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do
{- }
end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
{- }
end;
procedure Both;
begin
Fast;
Slow;
end;
|
|
|
, , . . , . , , . : function Factorial(n: Word): integer;
begin
if n > 1 then
Factorial:=n*Factorial(n-1)
else
Factorial:=1;
end;
N , , O(N).
, , . , , . :
procedure DoubleRecursive(N: integer);
begin
if N>0 then
begin
DoubleRecursive(N-1);
DoubleRecursive(N-1);
end;
end;
, , O(2N)=O(N). . , , O(2^(N+1)-1)=O(2^N). , .
. , . .
