pto2

	25	4. Dana jest procedura A"
		............

procedurę AT(var /:array[l...n] of integer);-    .    .

procedurę Y(j,k,/ńnteger);    -    ........

var Imp.i: integer; begin

while j<-k and k<l do

if r[/]<=/[A+1 ] then j++ else begin

tmp:=l[k+1]; for i:-k downto j do /[/'+1 ]:=/[/}; l{j]:=tmp\    {przesunięcie cykliczne ciągu /[/],...,/[i+l]}

_/++; k++;

end;

end;{ Y}

procedurę ZOjdntcger);

var A:integer;

begin

if i<j then begin

losuj ke{i,...j-\}\

Z(i,ky,Z(k+lj)\ Y{i.kj)\

end;

cnd;{Z}

begin

2(1,n);

end;{Al

a)    Co robi procedura XI

b)    Oszacuj jej pesymistyczną złożoność obliczeniową (w sensie symbolu 0).

Odpowiedzi uzasadnij.

5. W historii problemu minimaksowego pełnego skojarzenia grafu spójnego znane są dwa najlepsze algorytmy: Al o złożoności 0( mJn\ogn )

A2 o złożoności 0( n^fnin ).

a)    Podaj przedział zmienności m (w sensie oszacowania asymptotycznego), dla którego algorytm drugi jest asymptotycznie szybszy od pierwszego.

Programista wpadł na pomysł zaimplementowania obu powyższych algorytmów i napisał następującą procedurę:

procedurę zagadka(G:graf)\

begin

n:~liczba wierzchołków w G;

»i:=liczba krawędzi w G;    {/«, n obliczane w stałym czasie}

if m<=n²/log₂rt then Al else A2

end;

b)    Oszacuj czas działania zagadki dla przypadku grafu rzadkiego i grafu gęstego w funkcji u.