[Algorytmy] złozonośc obliczeniowa i dopasowanie wzorca

[lisio]

Witam,
kolejna porcja zadań do mnie dotarła i z dwoma mam problem. Oto one:
Zadanie 11 Dopasowanie wzorca

Dane sa łancuch S[1..n] i wzorzec P[0 ..m − 1], gdzie 1 <= m <= n. Ponizszy
algorytm wyznacza pozycje L wystepowania wzorca P w łancuchu S, tzn.
L = p jesli S[p .. p + m − 1] = P, a L = n − m + 1 jesli wzorzec P nie jest
podciagiem S.

Kod: Zaznacz cały

Dopasuj(P, S, m, n)
1 L <- 0
2 dopasowano <- false
3 while L<= n − m ^ ¬dopasowano
4   do L<-L+ 1
5      r <-  0
6      dopasowano <-  true
7      while r < m ^ dopasowano
8         do dopasowano <-  (P[r] = S[L + r])
9             r  <- r + 1
10 return L

Ile porównan symboli łancucha i wzorca (instrukcji w wierszu 8) wykonuje
powyzszy algorytm w przypadku pesymistycznym?


drugie:

Algorytm wyznacza yz, gdzie y, z należy do N.

Kod: Zaznacz cały

Mnóz(y, z)
1 if z = 0
2 then return 0
3 else if odd(z)
4 then return Mnóz(2 · y, [z/2]) + y
5 else return Mnóz(2 · y, [z/2])

Jaka jest jego złożoność obliczeniowa? (tu wygląda na liniowy, problem taki, że po obliczeniach wychodzi mi =z/(pierwiastek z 4 o stopniu z). Więc chyba będzie o wielomianowej złożoności obliczeniowej)

Z góry dziękuje, za wszelakie podpowiedzi które naprowadza na rozwiązanie.

[Xitami]

1. Konkurs poboczny.
Na ile sposobów można interpretować podany algorytm?
Może każdy kurs należałoby rozpoczynać od Pythona?

2. to samo, ale zapisane iteracyjnie

Kod: Zaznacz cały

mnoz(y, z)
    r=0;
    while z != 0 
        if odd(z)
            r=r+y
        y=2y
        z=z/2
    return r

W każdym kroku z dzieli się przez dwa, ile razy może się tak podzielić?

[lisio]

Jakoś nie wpadłem na pomysł przedstawienia tego iteracyjni z/2=O(z). Dzięki wielki.

No właśnie co do pseudokodu
Jeżeli dobrze zrozumiałem zadanie. Odpowiedź to n porównań. Wiąże
się to z tym, że n to długość łańcucha S, w którym wyszukujemy
wzorca P. Najgorszy wariant, to ten, gdy mamy wzorzec P na końcu
łańcucha S. W takiej sytuacji algorytm będzie musiał porównać każdy
znak łańcucha S. Przykład najgorszej sytuacji:
P =　abcde
S = xxxxxxxxxxabcde
Problem w tym iż nie wiem czy do końca o to chodzi.

[Xitami]

nie O(z) tylko O(log z)