Zadania 5

o zlożonościach : 0(n*m), 0{mn!oj!(n²/ni», ?, 0(n²sqrt(m)), O(nmlogm), 0(nm²), 0(n³), 0(mnlng²n), gdzie ? oznacza, że w publikacji brak jest informacji na temat złożoności obliczeniowej. Uporządkuj te złożoności i wypisz obok odpowiednich nazivi.sk. Uwaga grafy spotykane w praktyce sq rządkie, ij. maja m=o(nlogn).

₍    0(n^Jłog²n), C(n'logn), 0(n7₇ 0(n²sqrt(nlogn)X CCnfiog^i), CCn²!og(n!ogn))_; 0(n²Iogn!og(n/logn))

, '~+‘ ?_: 0(nm²). 0(n^_m), 0(n“). 0(rrsqn(m)). 0(nmiog"n), O(nmiogm), 0(mnIogCn²/m))

\f 14. Graf spójny zapisano w postaci macierzy sąsiedztwa wierzchołków. Naszkicuj algorytm rozpoznający, czy graf ten ma cyk] i oszacuj jego złożoność obliczeniową.

Graf spójny będzie miał cykl ca> m>n. function cykl(n:integer, M:matrL\):bcolean; fcegin m:=0;

for i:=l to n-1 do    { C(;r/2)=0(n^:)

for j;=i-H to n do

if M[i.j]=l then m-H-; {zliczanie ilości krawędzi) if m<n then return (fal se) retom true;

end;

T(n)=0(ir) - złożoność kwadratowa

15. Poniższa procedura definiuje funkcję p{n), n>0. Zakładając, że 2T(n)>3T(n-l) dła wszystkich n napisz odpowiednie równanie i oszacuj liczbę kroków T(n) tej procedury. Odpowiedz, czy T(n) wyrażona jako funkcja rozmiaru danych jest wielomianowa, superwielomianowa, wykładnicza, czy superwykladnicza. Napisz procedurę q(n), która oblicza wartość tej samej funkcji lecz w czasie 0(1). function p(n:int£ger):Integer; begin

if n<2 tben return(2*n)

else rerurx»(2*p(a-2)-p(n-2))

end;

T(n)-łiczba kroków, operacja podstawowa - mnożenie T(n)={ 1    n<2

T(n-l>!-T(n-2)+l    n>2

oraz 27(n)>37(n-l)

2T(n-l)>3T(n-2)

T(n-2)<2/3 T(n-l)

n

T(n)=T(E-l)-rT(n-2)-rl T(n)<T(n-l)-r2/3 7(n-l)+1=5/3 T(n-l)-1 a=5/3, d(n)=l = ć(a)=C(a7n^c)

T(n)=C((5/3)ⁿ), wg rozmiaru danvch n=2^J'

T(n)=0((5/3)^A2²)

Funkcja p cbłicza wartość 2*n function q(n:in!eger);integer, begin

rctom(2*r>);

end;

^ 16. Napisz dowolny algorytm o następującej złożoności obliczeniowej (rysunek) procedurę nic(n;integer);

, begin case

n<10 : for i;=l :o n do for j:=l to n do a:=a^J,I: break;

n=10 : for i:= 1 to 5 do i:-=3;

n>10 : for i;=i to 2*(n mod 10) do