rownanie rekurencyjne

[coldrain]

witam

w ksiazce Wprowadzenie do algorytmow pojawia sie takie rownanie rekurencyjne:
\(\displaystyle{ T(n) = 2T( \sqrt{n}) + lgn}\)

Autor rozwiazujac je podstawia \(\displaystyle{ m = lgn}\) z czego wychodzi mu:

\(\displaystyle{ T(2 ^{m} ) = 2T( 2^{ \frac{m}{2} } )+m}\)

Nie moge zrozumiec, skad sie to bierze. Rozumiem, ze za \(\displaystyle{ lgn}\) podstawil wartosc \(\displaystyle{ m}\) ale skad wzielo sie np: \(\displaystyle{ T( 2^{m})}\)?

[Sylwek]

\(\displaystyle{ \log_a b = c \iff a^c=b}\), a w zadaniu chodzi o logarytm binarny (o podstawie 2), czyli: \(\displaystyle{ \log_2 n =m \iff n=2^m}\)

[coldrain]

hmm nie wiedzialem, ze tak wolno robic.
Tzn majac np rownanie \(\displaystyle{ 2T(n^{2})+logn}\) i chcac podstawic za \(\displaystyle{ logn}\) zmienna L to musze rowniesz przeksztalcic wszystkie zmienne \(\displaystyle{ n}\)?

mam jeszcze drugie pytanie.
Rozwiazujac rekurencje postaci \(\displaystyle{ T(n) = 2T( \frac{n}{2}) + n}\) metoda podstawiania zgaduje sie rozwiazanie a nastepnie je udowadnia poprzez indukcje matematyczna.
Czyli zgadujac, ze rozwiazaniem bedzie \(\displaystyle{ O(nlgn)}\) podstawiam to do swojego rownania rekurencyjnego i otrzymuje \(\displaystyle{ T(n) qslant 2(c \frac{n}{2}lg \frac{n}{2} ) + n}\) i w kolejnych krokach:
2. \(\displaystyle{ cnlg (\frac{n}{2}) + n}\)
3. \(\displaystyle{ cnlgn - cnlg2+n}\)
4. \(\displaystyle{ cnlgn - cn+n}\)
5. \(\displaystyle{ cnlgn}\)

dlaczego w kroku 4 zostalo pominiete \(\displaystyle{ lg2}\)?
dlaczego w kroku 5 zostalo pominiete \(\displaystyle{ cn+n}\)?