szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Rekurencja 2T
PostNapisane: 9 lut 2018, o 14:02 
Użytkownik

Posty: 7
Lokalizacja: Polska
Witam
Niedługo mam egzamin z matematyki dyskretnej 2.
I nie wiem jak zrobić poniższe zadanie.
Prosiłbym o pomoc.

Rozważmy następującą rekurencję t(1) = 0, t(n) = 2t(\frac{n}{2}) + n dla n > 1 oraz n będącego potęgą liczby 2. Wówczas
(a), t(n) = n * lg(n) , (b) t(n) = lg(n), (c) = n * lgn + 1

W przykładzie a doszedłem do takiego momentu:
T(1) = 0
n = 2^{k}
T(2^{k}) = 2T(\frac{2^k}{2}) + 2^{k} = 2T(\frac{2^(k-1)}{2}) + 2^{k}

I dalej nie wiem co z tym zrobić.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 9 lut 2018, o 14:15 
Użytkownik
Avatar użytkownika

Posty: 12445
Lokalizacja: czasem Warschau, czasem Breslau
Jeżeli t(n)=2t\left( \frac n 2\right) +n, to dla n=2^k otrzymamy
t\left( 2^k\right) =2t\left( 2^{k-1}\right) +2^k.
Podzielmy stronami przez 2^k, a otrzymamy:
\frac{t\left( 2^k\right) }{2^k}= \frac{t\left( 2^{k-1}\right) }{2^{k-1}}+1
Oznaczmy teraz a_k= \frac{t\left( 2^k\right) }{2^k}, wówczas dostajemy
a_k=a_{k-1}+1, \ k>1, ponadto
a_1= \frac{t(1)}{2^1} =0
Stąd łatwo wywnioskować (poziom podstawówki w zasadzie), że a_k=k-1, czyli
\frac{t\left( 2^k\right) }{2^k} =k-1\\ t\left( 2^k\right)=(k-1)\cdot 2^k
i dalej powinieneś sobie poradzić.

-- 9 lut 2018, o 13:16 --

Nie jest to rezultat jakiejś konkretnej metody, tylko efekt chwili zastanowienia, więc obawiam się, że średnio to pomoże w przygotowaniach do egzaminu. :|
Góra
Mężczyzna Offline
PostNapisane: 9 lut 2018, o 14:28 
Użytkownik

Posty: 7
Lokalizacja: Polska
\frac{t\left( 2^k\right) }{2^k}= \frac{t\left( 2^{k-1}\right) }{2^{k-1}}+1
Skąd się wziął wynik po prawej stronie ?
Góra
Mężczyzna Offline
PostNapisane: 9 lut 2018, o 14:44 
Użytkownik
Avatar użytkownika

Posty: 12445
Lokalizacja: czasem Warschau, czasem Breslau
Słyszałeś o dzieleniu?

t\left( 2^k\right) =2t\left( 2^{k-1}\right) +2^k \bigg|: 2^k\\ \frac{t\left( 2^k\right) }{2^k}= \frac{2t\left( 2^{k-1}\right) }{2^k}+1\\ \frac{t\left( 2^k\right) }{2^k}= \frac{t\left( 2^{k-1}\right) }{2^{k-1}}+1\ldots
Góra
Mężczyzna Offline
PostNapisane: 9 lut 2018, o 15:27 
Użytkownik

Posty: 7
Lokalizacja: Polska
okej i (k-1) * 2^{k} jak to się ma do naszego przykładu a ?
Oraz jak obliczyć coś takiego lg(2^{k}) ?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rekurencja -> Czynnik sumacyjny -> problem z ciągiem  dong  0
 rekurencja rownanie niejednorodne  superja  2
 Opinia - Rekurencja  combinev2  2
 Fraktale vel. rekurencja w trójkącie.  szampek  8
 rekurencja i funkcja tworzaca  Gogeta  8
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl