Witam,
proszę o pomoc z rozwiązaniem zadania. Muszę dokonać oszacowania dla następującej funkcji
\(\displaystyle{ T \left( n \right) =25T \left( \frac{n}{5} \right) +7n^{3} - 2n^{2} + 3 }\)
Z powyższego wyliczyłem:
\(\displaystyle{ a= 25, b=5, f\left( n\right)=7n^{3} - 2n^{2} + 3 }\)
\(\displaystyle{ x = \log _{b}{a} = \log _{5}{25} = 2 }\)
\(\displaystyle{ n ^{x} = n ^{2} }\)
\(\displaystyle{ \Theta \left( f\left( n\right) \right) = \Theta \left( 7n^{3} - 2n^{2} + 3\right) = \Theta \left(n^{3} \right) }\)
\(\displaystyle{ f\left( n\right) = \Omega\left( n ^{x + \epsilon} \right) = \Omega\left( n ^{2+ \epsilon} \right) }\) dla np. \(\displaystyle{ \epsilon = 0,5 }\)
Natomiast mam problem z udowodnieniem, że istnieje takie c mniejsze od 1 i dostatecznie dużych n, że zachodzi warunek
\(\displaystyle{ af\left( \frac{n}{b} \right) \le cf\left( n\right) }\)
Gdyż
\(\displaystyle{ 25f\left( \frac{n}{5} \right) = 25 \cdot 7 \cdot \left( \frac{n}{5} \right)^{3} - 25 \cdot 2 \cdot \left( \frac{n}{5} \right)^{2} + 3 }\)
i wtedy wychodzi że \(\displaystyle{ 1,4 n^{3} }\), co jednoznacznie wskazuje że nie istnieje takie C, które spełniałoby ten warunek.
Czy gdzieś popełniłem błąd w obliczeniach? Będę niezwykle wdzięczny za pomoc
Twierdzenie o rekursji uniwersalnej
-
- Użytkownik
- Posty: 30
- Rejestracja: 19 lis 2018, o 13:04
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 14 razy
-
- Użytkownik
- Posty: 30
- Rejestracja: 19 lis 2018, o 13:04
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 14 razy
Re: Twierdzenie o rekursji uniwersalnej
O tym wiem, ale niestety mogę stosować wyłącznie przedstawioną metodę do rozwiązań tego zadania.
Taki wymóg od wykładowcy i nie jestem w stanie tego przeskoczyć
Taki wymóg od wykładowcy i nie jestem w stanie tego przeskoczyć
- Dasio11
- Moderator
- Posty: 10223
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2361 razy
Re: Twierdzenie o rekursji uniwersalnej
W jaki sposób tak Ci wychodzi?Sakurzasty pisze: ↑22 lis 2019, o 10:11\(\displaystyle{ 25f\left( \frac{n}{5} \right) = 25 \cdot 7 \cdot \left( \frac{n}{5} \right)^{3} - 25 \cdot 2 \cdot \left( \frac{n}{5} \right)^{2} + 3 }\)
i wtedy wychodzi że \(\displaystyle{ 1,4 n^{3} }\), co jednoznacznie wskazuje że nie istnieje takie C, które spełniałoby ten warunek.
Zauważ, że
\(\displaystyle{ \lim_{n \to \infty} \frac{25 f \left( \frac{n}{5} \right)}{f(n)} = \lim_{n \to \infty} \frac{ \frac{7}{5} n^3 - 2n^2 + 75}{7n^3 - 2n^2 + 3} = \frac{1}{5}}\),
więc dla dostatecznie dużych \(\displaystyle{ n}\) powyższy iloraz jest mniejszy od \(\displaystyle{ \frac{1}{2}}\), czyli \(\displaystyle{ 25 f \left( \frac{n}{5} \right) \le \frac{1}{2} f(n)}\).