[Algorytmy] Równanie rekurencyjne

secter
Użytkownik
Użytkownik
Posty: 28
Rejestracja: 6 lip 2017, o 16:16
Płeć: Mężczyzna
Lokalizacja: Stąporków
Podziękował: 9 razy

[Algorytmy] Równanie rekurencyjne

Post autor: secter »

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?
Fibik
Użytkownik
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

Post autor: Fibik »

\(\displaystyle{ T(0) = T(0) + T(0) + 0 = 2T(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 .
Awatar użytkownika
Zordon
Użytkownik
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

Post autor: Zordon »

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...
Fibik
Użytkownik
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

Post autor: Fibik »

No to nawijaj dalej, a zobaczymy co z tego wyjdzie.

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 .
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

Więcej pokory Fibik

\(\displaystyle{ T(n)=- \frac{5}{\ln 108}n \ln n}\)
Fibik
Użytkownik
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

Post autor: Fibik »

Bzdury opowiadasz... coś jak pi = 7 bo w zaokrągleniu.
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

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...
ODPOWIEDZ