Skorzystaj z rekurencji uniwersalnej i podaj dokładne asymptotyczne oszacowane dla poniższych rekurencji. We wszystkich przypadkach zakładamy, że\(\displaystyle{ T(1)= \Theta (1)}\)
i) \(\displaystyle{ T(n)=2T(n/2)+n^2}\)
ii) \(\displaystyle{ T(n)=2T(n/2)+5}\)
Korzystam z następującego twierdzenia
Niech \(\displaystyle{ a \ge 1, b>1}\). Załóżmy, że
\(\displaystyle{ T(n)=aT( \frac{n}{b} )+f(n)}\),
gdzie\(\displaystyle{ f: N o [0, infty )}\), \(\displaystyle{ T(1)= \Theta (1)}\) i \(\displaystyle{ \frac{n}{b}}\) może oznaczać \(\displaystyle{ \lfloor \frac{n}{b} \rfloor}\) lub \(\displaystyle{ \lceil \frac{n}{b} \rceil}\).
Wówczas:
(a) jeżeli \(\displaystyle{ \bigvee_{ \epsilon >0}f(n)=O(n^{log_ba- \epsilon})}\), to \(\displaystyle{ T(n)= \Theta (n^{log_ba})}\),
(b) jeżeli \(\displaystyle{ f(n)= \Theta (n^{log_ba})}\), to \(\displaystyle{ T(n)= \Theta (n^{log_ba}lgn)}\),
(c) jeżeli \(\displaystyle{ \bigvee_{ \epsilon >0}f(n)= \Omega (n^{log_ba+ \epsilon})}\) oraz \(\displaystyle{ \bigvee _{c_1<1} \bigvee _{n_0 \in N} \bigwedge _{n \ge n_0} af ( \frac{n}{b} ) \le cf(n)}\) , to \(\displaystyle{ T(n)= \Theta (f(n))}\)
Moje rozwiązanie
i) \(\displaystyle{ T(n)=2T(n/2)+n^2}\)
\(\displaystyle{ a=2, b=2 , f(n)=n^2}\)
\(\displaystyle{ log_ba=log_22=1 \Rightarrow n^{log_ba}=n^1=n}\)
który podpunkt z twierdzenia tu działa?
ii) \(\displaystyle{ T(n)=2T(n/2)+5}\)
\(\displaystyle{ a=2, b=2 , f(n)=5}\)
\(\displaystyle{ log_ba=log_22=1 \Rightarrow n^{log_ba}=n^1=n}\)
który podpunkt z twierdzenia tu działa?
wydaje mi się, że (b)
\(\displaystyle{ T(n)=O(n^{log_ba} \cdot lgn) = \Theta(nlgn)}\)
rekurencja uniwersalna (wersja podstawowa)
-
- Użytkownik
- Posty: 556
- Rejestracja: 15 mar 2009, o 18:13
- Płeć: Kobieta
- Podziękował: 57 razy
- Pomógł: 30 razy
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
rekurencja uniwersalna (wersja podstawowa)
Nie. W pierwszym porównujesz \(\displaystyle{ f(n)}\) (czyli \(\displaystyle{ n^2}\)) i \(\displaystyle{ n^{log_ba}}\), czyli \(\displaystyle{ n}\). Większy wykładnik ma to pierwsze, więc działa podpunkt a).
W drugim analogicznie działa c).
W drugim analogicznie działa c).
-
- Użytkownik
- Posty: 556
- Rejestracja: 15 mar 2009, o 18:13
- Płeć: Kobieta
- Podziękował: 57 razy
- Pomógł: 30 razy
rekurencja uniwersalna (wersja podstawowa)
a kiedy jest (b)?
-- 16 lis 2009, o 22:55 --
iii) \(\displaystyle{ T(n)=2T(n/2)+n^2}\)
\(\displaystyle{ a=4, b=2 , f(n)=n^2}\)
\(\displaystyle{ log_ba=log_24=2 \Rightarrow n^{log_ba}=n^2}\)
czyli (b)
-- 16 lis 2009, o 22:55 --
iii) \(\displaystyle{ T(n)=2T(n/2)+n^2}\)
\(\displaystyle{ a=4, b=2 , f(n)=n^2}\)
\(\displaystyle{ log_ba=log_24=2 \Rightarrow n^{log_ba}=n^2}\)
czyli (b)
Ostatnio zmieniony 16 lis 2009, o 22:57 przez 111sadysta, łącznie zmieniany 1 raz.
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
rekurencja uniwersalna (wersja podstawowa)
b) działa, jeśli wykładniki wyjdą dokładnie równe. Na przykład przy klasycznym równaniu MergeSorta:
\(\displaystyle{ T(n) = 2T(n/2) + n}\)
Tutaj \(\displaystyle{ f(n) = n}\) i \(\displaystyle{ n^{log_ba} = n}\). Przy czym stała przy \(\displaystyle{ f(n)}\) nie ma znaczenia: równanie \(\displaystyle{ T(n) = 2T(n/2) + 20 n}\) robiłoby się tak samo.
\(\displaystyle{ T(n) = 2T(n/2) + n}\)
Tutaj \(\displaystyle{ f(n) = n}\) i \(\displaystyle{ n^{log_ba} = n}\). Przy czym stała przy \(\displaystyle{ f(n)}\) nie ma znaczenia: równanie \(\displaystyle{ T(n) = 2T(n/2) + 20 n}\) robiłoby się tak samo.
-
- Użytkownik
- Posty: 556
- Rejestracja: 15 mar 2009, o 18:13
- Płeć: Kobieta
- Podziękował: 57 razy
- Pomógł: 30 razy
rekurencja uniwersalna (wersja podstawowa)
iii) \(\displaystyle{ T(n)=4T(n/2)+n^2}\)
\(\displaystyle{ a=4, b=2 , f(n)=n^2}\)
\(\displaystyle{ log_ba=log_24=2 \Rightarrow n^{log_ba}=n^2}\)
czyli (b)
iv) \(\displaystyle{ T(n)=4T(n/2)+n}\)
\(\displaystyle{ a=4, b=2 , f(n)=n}\)
\(\displaystyle{ log_ba=log_24=2 \Rightarrow n^{log_ba}=n^2}\)
czyli (c)
\(\displaystyle{ a=4, b=2 , f(n)=n^2}\)
\(\displaystyle{ log_ba=log_24=2 \Rightarrow n^{log_ba}=n^2}\)
czyli (b)
iv) \(\displaystyle{ T(n)=4T(n/2)+n}\)
\(\displaystyle{ a=4, b=2 , f(n)=n}\)
\(\displaystyle{ log_ba=log_24=2 \Rightarrow n^{log_ba}=n^2}\)
czyli (c)
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
rekurencja uniwersalna (wersja podstawowa)
Tak. Odpowiedź w iii) jest w związku z tym \(\displaystyle{ n^2 \log n}\), w (iv) już dojdziesz sam