Zadania 4

a)    ^Co oblicza rekurencyjny ?

nodm<n/2,

b)    Napisz równanie reku ren cyjne na liczbę kroków algorytmu w funkcji n, gdy n—2'* oraz r.

c)    Rozwiąż to równanie,

cl) Czy rozwiążą niejest sabliniowe, liniowe, superwieloniiunowe, czy wykładnicze ? e) Napisz równoważny algorytm itcracyjny. a) N\VD (największy wspólny dzielnik),

3 b)T(n)=T(r/ł)+],

Jg c) TCnJ-Otrrlogn^OOogn) (w funkcji rozmiaru danych Cfn)),

d) Subiiniowe,

^ e) funciion NVvD(n,m:integer); nwdtinteger; fcegin

while m>0 do begjn T=m;

m=n rnod m; n=T;

end;

return n; end;

|/ 32. Oszacuj liczbę kroków wykonywanych przez poniższą procedurę zagadka. Czy lic2ba ta, wyrażona jako funkcja rozmiaru danych jest: subliniowa, wielomianowa, superwielomiauowa, wykładnicza, czy superwyldadnicza ?

procedurę zagadkufnrimeger): begin

for i:=0 to sqr(n) mod 9 do j:=l;    } 0(1)

k:=l;    *    } 0(1)

while k<n do begin j:=j4-2; k:=k+j; end end;

pętla while    i=l j=3    k=4

2    5    44-5

3    7    4*5+7

k=.. i-elementów

ciąg arytmetyczny S_n=((ai +a_n)n)/2_J S_ri=(( 1 +2i-1 )i)/2=r,

k=r>n - warunek zakończenia pętli

złożoność obliczeniowa 0($qrt(n)),

rozmiar danych - liczba bitów potrzebna na zapisanie n

S=log₂n, n=2^s, złożoność obliczeni o wa(S)=0(5qrt(2^s)) - wykładnicza 13. W historii problemu znajdowania maksymalnego przepływaj w sieci znane są następujące cora2 lepsze algorytmy

Forda-Fuikersnna (1956) Edmondsona-Karpa (1969)

Di nica    (1970)

Karzanowa    (1974)

Cherkaskyego    (1977)

Shiloacba    (3 979)

Sleatora-Tarjana (19S0) Gotdbcrga-Tarjana (19S3)

w