Zadania 8

Co z tego wynika ?

Otóż zamiast stałej 2 mogę wstawić dowolna stalą i w ten sposób z pomocą powyższego algorytmu skonstruować algorytm o dowolnie dobrym przybliżeniu. A mając taki algorytm każdy problem sumy podzbioru mogę rozwiązać optymalnie.

]/ 2-1. Uporządkuj podane funkcje pod względem tempa wzrostu :

2^Asqrt(Iogn), 2n, sqrt(n), logn, lcglogn, n/logn, sqrt(a)iogn, (1/3)% (3/2)% 17, (sil)*"*'

>%• (I/3)% 17, ioziogn, logn. 2^Asqrt(logn), sart(n), sqrt(n)logn, n/logn, 2n, (3/2)% (n/2)^!ciF

V 25. Graf G zapisano w postaci macierzy sąsiedztwa wierzchołków. Napisz program rozstrzygający, czy graf G jest cyklem i oszacuj jego złożoność obliczeniową.

Graf jest cyklem, gdy m-n i stopień każdego wierzchołka -2.

procedurę Czycyklfn: integer,M:itiatrix) :bcolea n; begin

fori:=l to n-1 do begin

stcpień:=0; forj:=i+I to n do

if M[ij]=l then stopień:=stopień+l; if stopień<>2 return(false);

end:

if m<>n then retum(false); retum(true); end;

y 26. Dana jest procedura mnożenia dwóch liczb procedurę razy(x,y:integer):integer; begin

if n=l then return(x*v)    } 0(1)

else

begin

podziel ciąg bitów s i y na połowy tj. .tI, %2 i yl, y2; )0(n)

a:=razy(xl-rx2,yl+y^r2);

b:=razy(xl,vl);

e:=razy(x2,y2);

retu m (brt-2ⁿ-r(a-b-c)* 2^-f-c);

} T(n/2)

} T(n/2)

} T(n/2)

} 0(3/2 n)

end;

C

end;

gdzie x i y są dwoma liczbami binarnymi n-bitowymi (n=2^k). Zakładając, że dodawania i przesunięcia mogą być wykonywane w czasie liniowym, oszacuj złożoność obliczeniowy tej procedury.

T(n)={ 1

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

wersja 1

U(n)=T(n)/(5/2) 5/2 U(n)=(2/5

U(n)={ 1

3T(n/2)-n

3 “5/2 T(n/2)-5/2 n

!    wersja2

[ T(n)=3T(n/2)-:o/2 n=3(3T(n/4)^5/4 n)+5/2 n= j =ogólnie=3^!T(l)-onC(cd i=I do k) (3/2)-

■5/2 n j =3'^l-r(3/2)^;-0(3')

3, d(b)-2. a>d(b)=^U(n)“0(n^A!og23)

| suma=>S’_v-⁼ai *((q^k-1 )/(q-1 ))=

! =3/2 *(((3/2)^k-l)/(3/2 -1))=

a=3, d(b)=2. a>d( T(n)- 0(n^AIog₂3)

)-0(n^AIog_;3)    | -3 *((3/2)^k-1 )=0((3/2)^k)

] kr-Iogm

T(n)~0(3^A!og₂n)~0(n^Alog₂3)

27. Studenci chcą ustalić, jakie jest najwyższe piętro wieżowca, z którego można wypchnąć profesora tak, aby przeżył. Grupa studentów postanowiła rozwiązać ten problem metodą wielokrotnego sukcesywnego podwajania piętra, bez stosowania blsekcji w osturnim etapie. Oszacuj liczbę kroków tej metody i napisz, czy jest ona subliniowa,