rekurencja uniwersalna (wersja podstawowa)

[111sadysta]

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)}\)

[paladin]

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).

[111sadysta]

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)

[paladin]

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.

[111sadysta]

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)

[paladin]

Tak. Odpowiedź w iii) jest w związku z tym \(\displaystyle{ n^2 \log n}\), w (iv) już dojdziesz sam