Dzień dobry.
Mam do rozwiązania takie równanie rekurencyjne i nie wiem jak się za nie zabrać:
\(\displaystyle{ T\left(n \right)=T\left( \frac{2}{5}n \right)+T\left( \frac{3}{5}n \right) +n}\)
Mógłby ktoś napisać jak rozwiązywać tego typu równania?
[Algorytmy] Równanie rekurencyjne
-
- Użytkownik
- Posty: 953
- Rejestracja: 27 wrz 2005, o 22:56
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 11 razy
- Pomógł: 74 razy
Re: [Algorytmy] Równanie rekurencyjne
\(\displaystyle{ T(0) = T(0) + T(0) + 0 = 2T(0),}\)
zatem: \(\displaystyle{ T(n) = 0.}\)
zatem: \(\displaystyle{ T(n) = 0.}\)
Ostatnio zmieniony 4 paź 2018, o 19:27 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
Powód: Brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Re: [Algorytmy] Równanie rekurencyjne
To będzie \(\displaystyle{ O(n\log n)}\). Można to udowodnić przez indukcję. Czyli dla pewnej stałej \(\displaystyle{ c>0}\) zachodzi
\(\displaystyle{ T(n) \leq c \cdot n \log n}\)
I tę stałą wyznaczasz w kroku indukcyjnym...
\(\displaystyle{ T(n) \leq c \cdot n \log n}\)
I tę stałą wyznaczasz w kroku indukcyjnym...
-
- Użytkownik
- Posty: 953
- Rejestracja: 27 wrz 2005, o 22:56
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 11 razy
- Pomógł: 74 razy
Re: [Algorytmy] Równanie rekurencyjne
No to nawijaj dalej, a zobaczymy co z tego wyjdzie.
Zakładam w ciemno, że zmieścimy się w czasie \(\displaystyle{ o(n)}\).
Zakładam w ciemno, że zmieścimy się w czasie \(\displaystyle{ o(n)}\).
Ostatnio zmieniony 5 paź 2018, o 21:25 przez Afish, łącznie zmieniany 1 raz.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
- arek1357
- Użytkownik
- Posty: 5703
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 129 razy
- Pomógł: 524 razy
Re: [Algorytmy] Równanie rekurencyjne
Gdzie widzisz tę bzdurę? pokaż...
Ja już tę bzdurę poprawiłem powinno być tak:
\(\displaystyle{ T(n)= \frac{5}{5 \ln 5-3 \ln 3-2 \ln 2}n \ln n}\)
Dalej twierdzę :więcej pokory, pycha idzie przed upadkiem...
Ja już tę bzdurę poprawiłem powinno być tak:
\(\displaystyle{ T(n)= \frac{5}{5 \ln 5-3 \ln 3-2 \ln 2}n \ln n}\)
Dalej twierdzę :więcej pokory, pycha idzie przed upadkiem...