Złożoność obliczeniowa algorytmów

[Kriziol]

Może ktoś pomóc przy takich zadaniach bo kompletnie nie wiem jak to ruszyć a mam jeszcze kilka takich przykładów do zrobienia. Prosił bym o rozwiązanie i wytłumaczenie jak to się robi. Z góry dzięki za pomoc.
1) Mnożenie

Poniższy algorytm wyznacza \(\displaystyle{ z \cdot y,}\)gdzie \(\displaystyle{ z,y \in N}\)

Kod: Zaznacz cały

Mnoz(y, z)
1 x:=0;
2 While z>0 do   
3       if odd(z) then  
4               x:=x+y
5         y:= 2 * y
6         z:= z div 2
7 return x

Należy określić ile razy zostanie wykonane dodawanie (instrukcja w wierszu 4) w przypadku pesymistycznym.

2) Rekurencja

Kod: Zaznacz cały

G(n)
if n = 0 v n = 1 
    then return 3 * n
    else return G(n-1)+2 * G(n-2)

Wykaż że powyższy algorytm zwraca wartość \(\displaystyle{ 2^{n} -(-1) ^{n}}\)

3)
Dopasowanie wzorca

Dane są: łańcuch S[1...n] i wzorzec P[0...m-1] gdzie 1<=m<=n. Poniższy algorytm wyznacza pozycję I występowania wzorca P w łańcuchu S tzn. I=p jeśli S[p... p+m-1]=P,
a I=n-m+1 jeśli wzorzec P nie jest podciągiem S,

Kod: Zaznacz cały

Dopasuj(P,S,m,n)
1 I:=0
2 dopasowano:=fale
3 while I<=n-m^ 
eg dopasowano do
4      I:=I+1
5      r:=0
6      dopasowano:=true;
7      while r<m^dopasowano do
8               dopasowano:=(P[r] = S[I+r])
9               r:=r+1
10 return I

Ile razy (wiersz 8) wykona powyższy algorytm w przypadku pesymistycznym?

[norwimaj]

Może ktoś pomóc przy takich zadaniach bo kompletnie nie wiem jak to ruszyć a mam jeszcze kilka takich przykładów do zrobienia. Prosił bym o rozwiązanie i wytłumaczenie jak to się robi. Z góry dzięki za pomoc.
1) Mnożenie

Poniższy algorytm wyznacza \(\displaystyle{ z\cdot y}\), gdzie \(\displaystyle{ z,y \in N}\)

Kod: Zaznacz cały

Mnoz(y, z)
x:=0;
While z>0 do   if odd(z) then  x:=x+y
    y:= 2*y
    z:= z div 2
return x

Należy określić ile razy zostanie wykonane dodawanie (instrukcja w wierszu 4) w przypadku pesymistycznym.

To jest algorytm mnożenia rosyjskich chłopów, ale mniejsza o to.
Za każdym obrotem pętli \(\displaystyle{ z}\) zmniejsza się \(\displaystyle{ 2}\) razy. Zatem liczba obrotów pętli, to \(\displaystyle{ \left\lfloor\log_2 z\right\rfloor +1}\). Tyle też maksymalnie może być wykonane dodawanie, o które chodzi.

2) Rekurencja

Kod: Zaznacz cały

G(n)
if n = 0 v n = 1 
    then return 3*n
    else return G(n-1)+2*G(n-2)

Wykaż że powyższy algorytm zwraca wartość \(\displaystyle{ 2^{n} -(-1) ^{n}}\)

Dowód przez indukcję po \(\displaystyle{ n}\).

[Kriziol]

ok to 2 zadanie raczej już wiem jak zrobić
ale jak Ci wyszedł log w tym pierwszym wyniku?

[norwimaj]

Najpierw rozważ przypadek, że \(\displaystyle{ z=2^n}\) dla \(\displaystyle{ n\in\mathbb{N}}\). Wtedy jest \(\displaystyle{ n+1}\) obrotów pętli.

[Kriziol]

Ok a polecenie if odd(z) nie będzie miało tutaj jakiegoś większego znaczenia??

[norwimaj]

Linia

Kod: Zaznacz cały

if odd(z) then

może tylko zmniejszyć liczbę wykonań linii

Kod: Zaznacz cały

 x:=x+y

To przypisanie wykona się dokładnie tyle razy, ile jest jedynek w zapisie binarnym liczby \(\displaystyle{ z}\). Dla liczby \(\displaystyle{ z=2^n}\) rzeczywiście jest to zaledwie \(\displaystyle{ 1}\), ale dla \(\displaystyle{ z=2^n-1}\) jest to \(\displaystyle{ n}\).