szukanie zaawansowane
 [ Posty: 7 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 23 cze 2018, o 00:57 
Użytkownik

Posty: 26
Lokalizacja: Stąporków
Dzień dobry.
Mam do rozwiązania takie równanie rekurencyjne i nie wiem jak się za nie zabrać:
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?
Góra
Mężczyzna Offline
PostNapisane: 4 paź 2018, o 18:07 
Użytkownik

Posty: 960
Lokalizacja: Wrocław
T(0) = T(0) + T(0) + 0 = 2T(0),
zatem: T(n) = 0. :)
Góra
Mężczyzna Offline
PostNapisane: 4 paź 2018, o 22:22 
Gość Specjalny
Avatar użytkownika

Posty: 4977
Lokalizacja: Kraków
To będzie O(n\log n). Można to udowodnić przez indukcję. Czyli dla pewnej stałej c>0 zachodzi
T(n) \leq c \cdot n \log n
I tę stałą wyznaczasz w kroku indukcyjnym...
Góra
Mężczyzna Offline
PostNapisane: 5 paź 2018, o 20:15 
Użytkownik

Posty: 960
Lokalizacja: Wrocław
No to nawijaj dalej, a zobaczymy co z tego wyjdzie. :)

Zakładam w ciemno, że zmieścimy się w czasie o(n).
Góra
Mężczyzna Online
PostNapisane: 8 paź 2018, o 13:01 
Użytkownik
Avatar użytkownika

Posty: 3390
Lokalizacja: blisko
Więcej pokory Fibik

T(n)=- \frac{5}{\ln 108}n \ln n
Góra
Mężczyzna Offline
PostNapisane: 26 paź 2018, o 23:07 
Użytkownik

Posty: 960
Lokalizacja: Wrocław
Bzdury opowiadasz... coś jak pi = 7 bo w zaokrągleniu. :)
Góra
Mężczyzna Online
PostNapisane: 29 paź 2018, o 14:27 
Użytkownik
Avatar użytkownika

Posty: 3390
Lokalizacja: blisko
Gdzie widzisz tę bzdurę? pokaż...

Ja już tę bzdurę poprawiłem powinno być tak:


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...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 7 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Algorytmy genetycze  MatS  21
 Algorytmy sortowania  Anonymous  0
 Algorytmy: Wyznacznik macierzy i Macierz odwrotna  Kristofer  3
 algorytmy w php  basia  6
 [Algorytm]Równanie pierwszego stopnia  Anonymous  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl