Złożoność algorytmów
Mariusz:
Oblicz złożoność czasową podanych algorytmów
Chodzi mi o dokładną złożoność bo asymptotyczną mają mniej więcej taką samą
const maxA=2000
type TElem=integer; (*Może byc wasz ulubiony typ
byleby miał wyróżnione pole kluczowe które można by było
porównywać*)
TArray=array[1..maxA]of TElem;
THArray=array[1..maxA div 2+1]of TElem;
(*Algorytm 1*)
procedure p1(l,r:integer;var A:TArray);
var x:TElem;
i,j:integer;
b:boolean;
begin
x:=A[l];
i:=l;
j:=2*i;
b:=false;
while((j<=r)and(not b))do
begin
if((j<r)and(A[j]<A[j+1])then
j:=j+1;
if(x<A[j])then
begin
A[i]:=A[j];
i:=j;
end
else
b:=true;
end;
A[i]:=x;
end;
procedure p2(n:integer;A:TArray);
var i:integer;
begin
for i:=n div 2 downto 1 do
p1(i,n,A);
end;
procedure p3(n:integer;A:TArray);
var x:TElem;
i:integer;
begin
p2(n,A);
for i:=n downto 2 do
begin
x:=A[1];
A[1]:=A[i];
A[i]:=x;
p1(1,i−1,A);
end;
end;
(*Algorytm 2*)
procedure p1(var A:TArray; p,q,r:integer);
var i,j,k,n1:integer;
B:THArray;
begin
n1:=q−p+1;
for k:=p to q do
B[k−p+1]:=A[k];
i:=1;
j:=q+1;
k:=p;
while((i<=n1)and(j<=r))do
begin
if(B[i]<=A[j])then
begin
A[k]:=B[i];
i:=i+1;
end
else
begin
A[k]:=A[j];
j:=j+1;
end;
k:=k+1;
end;
while(i<=n1) do
begin
A[k]:=B[i];
i:=i+1;
k:=k+1;
end;
end;
procedure p2(n:Integer;A:TArray);
var l,m,r,s:integer;
begin
s:=1;
while(s<=n)do
begin
l:=1;
while(l+s<=n)do
begin
m:=l+s−1;
if(l+2*s−1<n)then
r:=l+2*s−1
else
r:=n;
p1(A,l,m,r);
l:=l+2*s;
end;
s:=s*2;
end;
end;
(*Algorytm 3*)
procedure p1(var A:TArray;l,r:integer);
var x,y:TElem;
i,j:integer;
begin
x:=A[(l+r)div 2];
i:=l;
j:=r;
repeat
while(A[i]<x)do i:=i+1;
while(x<A[j])do j:=j−1;
if(i<=j)then
begin
y:=A[i];
A[i]:=A[j];
A[j]:=y;
i:=i+1;
j:=j−1;
end;
until(i>j);
if(l<j)then p1(A,l,j);
if(i<r)then p1(A,i,r);
end;