Rekurencja 2T

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Kogut18
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 21 lis 2017, o 22:01
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 2 razy

Rekurencja 2T

Post autor: Kogut18 »

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(\(\displaystyle{ \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 = \(\displaystyle{ 2^{k}}\)
T(\(\displaystyle{ 2^{k}}\)) = 2T(\(\displaystyle{ \frac{2^k}{2}}\)) + \(\displaystyle{ 2^{k}}\) = 2T(\(\displaystyle{ \frac{2^(k-1)}{2}}\)) + \(\displaystyle{ 2^{k}}\)

I dalej nie wiem co z tym zrobić.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Rekurencja 2T

Post autor: Premislav »

Jeżeli \(\displaystyle{ t(n)=2t\left( \frac n 2\right) +n}\), to dla \(\displaystyle{ n=2^k}\) otrzymamy
\(\displaystyle{ t\left( 2^k\right) =2t\left( 2^{k-1}\right) +2^k}\).
Podzielmy stronami przez \(\displaystyle{ 2^k}\), a otrzymamy:
\(\displaystyle{ \frac{t\left( 2^k\right) }{2^k}= \frac{t\left( 2^{k-1}\right) }{2^{k-1}}+1}\)
Oznaczmy teraz \(\displaystyle{ a_k= \frac{t\left( 2^k\right) }{2^k}}\), wówczas dostajemy
\(\displaystyle{ a_k=a_{k-1}+1, \ k>1}\), ponadto
\(\displaystyle{ a_1= \frac{t(1)}{2^1} =0}\)
Stąd łatwo wywnioskować (poziom podstawówki w zasadzie), że \(\displaystyle{ a_k=k-1}\), czyli
\(\displaystyle{ \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.
Kogut18
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 21 lis 2017, o 22:01
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 2 razy

Re: Rekurencja 2T

Post autor: Kogut18 »

\(\displaystyle{ \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 ?
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Rekurencja 2T

Post autor: Premislav »

Słyszałeś o dzieleniu?

\(\displaystyle{ 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}\)
Kogut18
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 21 lis 2017, o 22:01
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 2 razy

Re: Rekurencja 2T

Post autor: Kogut18 »

okej i (k-1) * \(\displaystyle{ 2^{k}}\) jak to się ma do naszego przykładu a ?
Oraz jak obliczyć coś takiego lg(\(\displaystyle{ 2^{k}}\)) ?
ODPOWIEDZ