Witam
Chciałem rozwiązać dwa równania rekurencyjne. Prześledziłem trochę rozwiązań i wiem ze można to rozwiązać metodą uniwersalną, przez iterację i podstawienie. Jednak metoda uniwersalna i podstawienie nie przemawia do mnie, bo raczej nie będę umiał tego zastosować na egzaminie.
Równanie które potrzebuje rozwiązać jest bardzo popularne i jest kilka rozwiązań ale nie potrafiłem zrozumieć żadnego z nich.
\(\displaystyle{ \begin{cases} T \left( 1 \right) = 1 \\ T \left( n \right) = 2T \left( \frac{n}{2} \right) + n\end{cases}}\)
A więc metodą iteracyjną doprowadziłem równanie do następującej postaci
\(\displaystyle{ T \left( n \right) = n + 2T \left( \frac{n}{2} \right) \\
T \left( n \right) = n + 2 \left( \frac{n}{2} + 2 \left( \frac{n}{8} \right) \right) \\
T \left( n \right) = n + 2 \left( \frac{n}{2} + 2 \left( \frac{n}{4} + 2T \left( \frac{n}{8} \right) \right) \right) \\
T \left( n \right) = n + n + n + 8T \left( \frac{n}{8} \right) \\
... \\
T \left( n \right) = n + n + n + ... + 2^{i}T \left( \frac{n}{2^i} \right)}\)
Szukamy warunku brzegowego a więc
\(\displaystyle{ i = \log _2 n}\)
Podstawiająć (tutaj zaczynają sie schody ze zrozumieniem dlaczego tak to jest rozpisane)
\(\displaystyle{ T \left( n \right) \le n \sum_{i=1}^{\log _2 n} 1 + 2^{\log _2 n} \\
= n \log n + n \\
= O \left( n \log n \right)}\)
Skąd nagle z tej sumy zostało rozpisane \(\displaystyle{ n \log n}\). Jakim sposobem to nagle zostało uogólnione do ostatniego wyrazu ciągu i dlaczego pojawił się tam znak mniejszości. Dlaczego z \(\displaystyle{ \log _2 n}\) dostaliśmy nagle \(\displaystyle{ \log n}\) ? I dlaczego ta suma jest prowadzona od \(\displaystyle{ i = 1}\) do \(\displaystyle{ \log _2 n}\) a nie do na przykład k-tego kroku ?
Czy istnieje jakiś inny sposób rozwiązywania tego bardziej intuicyjny ?
Zdaje sobie sprawę z tego, że nie jest to trudne zadanie jednak dawno nie rozwiązywałem jakichkolwiek zadań a na studiach nagle wróciły takie powiedzmy podstawy i cieżko mi się połapać ? Będę bardzo wdzięczny za jakąkolwiek podpowiedz która pomoże mi zrozumieć dlaczego to zadanie zostało rozwiązane w taki a nie inny sposób.
Pozdrawiam,
Piorek
Rozwiązanie równań rekurencyjnych.
-
Piotrek122
- Użytkownik
- Posty: 1
- Rejestracja: 24 cze 2019, o 23:14
- Płeć: Mężczyzna
- Lokalizacja: Katowice
Rozwiązanie równań rekurencyjnych.
Ostatnio zmieniony 25 cze 2019, o 00:10 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości. Punkt 2.7 instrukcji LaTeX-a. Funkcje matematyczne należy zapisywać: sinus - \sin, logarytm - \log, logarytm naturalny - \ln itd.
Powód: Poprawa wiadomości. Punkt 2.7 instrukcji LaTeX-a. Funkcje matematyczne należy zapisywać: sinus - \sin, logarytm - \log, logarytm naturalny - \ln itd.
-
janusz47
- Użytkownik
- Posty: 7917
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1671 razy
Rozwiązanie równań rekurencyjnych.
\(\displaystyle{ T(n) = 2\cdotT\left(\frac{n}{2}\right) + n \ \ (1)}\)
\(\displaystyle{ T\left(\frac{n}{2}\right) = 2\cdot T\left(\frac{n}{2^2}\right) +\frac{n}{2}= 2\cdot \left[ 2\cdot T \left(\frac{n}{2^2}\right)+ \frac{n}{2} \right]+n = 2^2\cdot T \left(\frac{n}{2^2}\right) +2n \ \ (2)}\)
\(\displaystyle{ \left(\frac{n}{2^2}\right) = 2\cdot T\left(\frac{n}{2^3}\right) + \frac{n}{2^2}}\)
\(\displaystyle{ T(n) = 2^2\cdot \left[ 2\cdot T \left(\frac{n}{2^3}\right) + \frac{n}{2^2}\right] + 2n}\)
\(\displaystyle{ T(n) =2^3 \cdot T \left(\frac{n}{2^3}\right) + 3n \ \ (3)}\)
Na podstawie \(\displaystyle{ (1), (2), (3)}\) ( przez indukcję)
...............................................................................................................
\(\displaystyle{ T(k) = 2^{k}\cdot T\left( \frac{n}{2^{k}}\right) + k\cdot n}\)
\(\displaystyle{ T\left( \frac{n}{2^{k}}\right) = T(1)}\)
\(\displaystyle{ \frac{n}{2k} = 1}\)
\(\displaystyle{ n = 2^{k}}\)
\(\displaystyle{ k = \log(n)}\)
Stąd
\(\displaystyle{ T(n) = 2^{k}\cdot T(1) +k\cdot n}\)
\(\displaystyle{ T(n) = n\cdot 1 + n\cdot \log(n) = O(n\log(n)).}\)
\(\displaystyle{ T\left(\frac{n}{2}\right) = 2\cdot T\left(\frac{n}{2^2}\right) +\frac{n}{2}= 2\cdot \left[ 2\cdot T \left(\frac{n}{2^2}\right)+ \frac{n}{2} \right]+n = 2^2\cdot T \left(\frac{n}{2^2}\right) +2n \ \ (2)}\)
\(\displaystyle{ \left(\frac{n}{2^2}\right) = 2\cdot T\left(\frac{n}{2^3}\right) + \frac{n}{2^2}}\)
\(\displaystyle{ T(n) = 2^2\cdot \left[ 2\cdot T \left(\frac{n}{2^3}\right) + \frac{n}{2^2}\right] + 2n}\)
\(\displaystyle{ T(n) =2^3 \cdot T \left(\frac{n}{2^3}\right) + 3n \ \ (3)}\)
Na podstawie \(\displaystyle{ (1), (2), (3)}\) ( przez indukcję)
...............................................................................................................
\(\displaystyle{ T(k) = 2^{k}\cdot T\left( \frac{n}{2^{k}}\right) + k\cdot n}\)
\(\displaystyle{ T\left( \frac{n}{2^{k}}\right) = T(1)}\)
\(\displaystyle{ \frac{n}{2k} = 1}\)
\(\displaystyle{ n = 2^{k}}\)
\(\displaystyle{ k = \log(n)}\)
Stąd
\(\displaystyle{ T(n) = 2^{k}\cdot T(1) +k\cdot n}\)
\(\displaystyle{ T(n) = n\cdot 1 + n\cdot \log(n) = O(n\log(n)).}\)