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})}\)?
rownanie rekurencyjne
- Sylwek
- Użytkownik
- Posty: 2716
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 160 razy
- Pomógł: 657 razy
rownanie rekurencyjne
\(\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}\)
rownanie rekurencyjne
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}\)?
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}\)?