Matematyka.pl

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?

\(\displaystyle{ T(0) = T(0) + T(0) + 0 = 2T(0),}\)
zatem: \(\displaystyle{ T(n) = 0.}\)

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

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

Zakładam w ciemno, że zmieścimy się w czasie \(\displaystyle{ o(n)}\).

Więcej pokory Fibik

\(\displaystyle{ T(n)=- \frac{5}{\ln 108}n \ln n}\)

Bzdury opowiadasz... coś jak pi = 7 bo w zaokrągleniu.

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