Szacowanie rozwiązania rekurencji

[Faelivrin]

Witam,
Chciałbym prosić o pomoc w rozwiązaniu poniższego zadania.

Należy znaleźć takie stałe \(\displaystyle{ n_{0}}\) i \(\displaystyle{ c}\), że dla wszystkich \(\displaystyle{ n \ge n_{0}}\) zachodzi \(\displaystyle{ T(n) \le cn \log n}\)

dla

\(\displaystyle{ T(n) = T(3/4n) + T(1/4n) + 4n}\)

[arek1357]

Jaką dziedzinę obejmuje to odwzorowanie T?

[Faelivrin]

W zadaniu nie było nic więcej podane. Ale dziedziną są chyba wszystkie liczby dodatnie.

[arek1357]

Trochę mnie to dziwi ale jak podstawisz:

\(\displaystyle{ n=4x}\)

masz:

\(\displaystyle{ T(4x)=T(3x)+T(x)+16x}\)

Rozwiązaniem tego równania jest właśnie funkcja:

\(\displaystyle{ T(x)=ax \ln x}\)

dla:

\(\displaystyle{ a= \frac{16}{4 \ln 4-3 \ln 3}}\)

[piotr159]

Czy mógłby ktoś to wytłumaczyć krok po kroku?

[Mefrix]

Również potrzebuję jakiegoś wytłumaczenia. W jaki sposób obliczyć te stałe? Można to zrobić z użyciem indukcji?

[arek1357]

Stałą obliczyłem podstawiając do wzoru...

Dodano po 8 godzinach 21 minutach 17 sekundach:
Rozwiązanie raczej zgadłem...

[Mefrix]

Muszę zrobić sprawozdanie z tego zadania, więc potrzebowałem jakichś konkretnych obliczeń. Spróbowałem zadanie rozwiązać używając metody rozwiązywania rekurencji przez podstawianie -

Kod: Zaznacz cały

https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture3.pdf

(substitution method - strona pierwsza)
Wykonałem następujące obliczenia i uzyskałem taki sam wynik, jednak nie mam pewności jak sformułować odpowiedź.

$$T(n)=T\left(\frac{3}{4}n\right)+T\left(\frac{1}{4}n\right)+4n.$$
$$T(n)\leq c\frac{3}{4}n\log\frac{3}{4}n+c\frac{1}{4}n\log\frac{1}{4}n+4n$$
$$\ldots\ldots\ldots$$
$$\leq cn\left(\frac{3}{4}\log3+\log n -\log4\right)+4n$$
$$\leq cn\log n+cn\frac{3}{4}\log3-cn\log4+4n$$

Z nierówności w takiej postaci można już wyznaczyć c.
$$cn\frac{3}{4}\log3-cn\log4+4n\leq0$$
$$c\frac{3}{4}\log3-c\log4+4\leq0$$
$$\ldots\ldots\ldots$$
$$16\leq c\left(4\log4-3\log3\right)$$
$$c\geq\frac{16}{4\log4-3\log3}$$

Jeśli chodzi natomiast o \(\displaystyle{ n}\) to dla \(\displaystyle{ n=1, n\log n = 0}\) więc chyba \(\displaystyle{ n_{0}=2}\).

Zadanie mówi, żeby wyznaczyć \(\displaystyle{ c}\) oraz \(\displaystyle{ n_{0}}\). Czy to oznacza, że \(\displaystyle{ c=\frac{16}{4\log4-3\log3}}\)? Czy może \(\displaystyle{ c\geq\frac{16}{4\log4-3\log3}? }\) Czy \(\displaystyle{ n_{0}=2}\) to prawidłowe rozwiązanie? Nie jestem pewien czy dobrze to rozumiem.

[matmatmm]

Podstawowe pytanie brzmi: jaka jest dziedzina tej funkcji?

Jeśli mają być to liczby dodatnie, to ciekawi mnie, czy rozwiązanie \(\displaystyle{ T(x)=ax\ln x}\) jest jedynym rozwiązaniem (w co wątpię).

Jeśli mają być to liczby naturalne, to zadanie jest źle sformułowane, bo
1. \(\displaystyle{ \frac{3}{4}n,\frac{1}{4}n}\) nie muszą być naturalne.
2. Nie ma warunku początkowego.

Mefrix, Ty zdaje się rozwiązujesz dla naturalnych, więc zakładam, że masz treść zmodyfikowaną przez uzupełnienie podłogami.

Wykonałem następujące obliczenia i uzyskałem taki sam wynik, jednak nie mam pewności jak sformułować odpowiedź.

$$T(n)=T\left(\frac{3}{4}n\right)+T\left(\frac{1}{4}n\right)+4n.$$
$$T(n)\leq c\frac{3}{4}n\log\frac{3}{4}n+c\frac{1}{4}n\log\frac{1}{4}n+4n$$
$$\ldots\ldots\ldots$$

Wykonałeś jakieś obliczenia, ale ciężko się domyślić, co tak naprawdę liczysz. Z trudem doszedłem do wniosku, że to ma być krok indukcyjny w dowodzie nierówności z treści zadania.

Jeśli chodzi natomiast o \(\displaystyle{ n}\) to dla \(\displaystyle{ n=1, n\log n = 0}\) więc chyba \(\displaystyle{ n_{0}=2}\).

Skąd ten wniosek? Bez warunku początkowego nie wiesz ile wynosi \(\displaystyle{ T(2)}\).

Zadanie mówi, żeby wyznaczyć \(\displaystyle{ c}\) oraz \(\displaystyle{ n_{0}}\). Czy to oznacza, że \(\displaystyle{ c=\frac{16}{4\log4-3\log3}}\)? Czy może \(\displaystyle{ c\geq\frac{16}{4\log4-3\log3}? }\)

Ja interpretowałbym treść tak, że wystarczy wskazać jedną parę \(\displaystyle{ c}\) i \(\displaystyle{ n_0}\).

[arek1357]

I do czego doprowadziło to rozumowanie?

Do niczego...

A jakie ma znaczenie jaka dziedzina skoro zadziała dla rzeczywistych tym bardziej zadziała dla naturalnych, bla, bla, bla...

Dodano po 38 sekundach:
Liczą się konkrety...

[matmatmm]

A potrafisz pokazać, że w rzeczywistych twoja funkcja jest jedynym rozwiązaniem? Bo w naturalnych bez warunku początkowego to gołym okiem widać, że jest więcej rozwiązań. Kolejne pytanie czy każda określona na naturalnych rozszerza się do rzeczywistych itd itp bla, bla...

[arek1357]

Ja nie twierdzę że to jedyne rozwiązanie...

Dodano po 2 minutach 18 sekundach:
Ale pokaż inne chętnie zobaczę...choćby w naturalnych...

[Mefrix]

Czy ktoś może podpowiedzieć w takim razie jak wyznaczyć \(\displaystyle{ n_{0}}\)?

Dodano po 1 godzinie 9 minutach 15 sekundach:
Po obliczeniu
$$c\geq\frac{16}{4\log4-3\log3}$$
w swoim sprawozdaniu zamierzam napisać następująco:
"Zastosowanie indukcji matematycznej wymaga warunku bazowego, a więc należy sprawdzić poprawność nierówności
$$T(n) \leq cn\log n$$
dla kolejnych wartości n. Sprawdzamy najpierw dla n=1.
$$T(1) \leq c1\log 1$$
$$T(1) \leq 0$$
Powyższa nierówność nie jest spełniona dla n=1.
Teraz sprawdzamy dla n=2 oraz n=3.
$$T(2) \leq c2 \log 2$$
$$\frac{3}{4}*2+\frac{1}{4}*2+4*2 \leq c2 \log 2$$
$$10 \leq c2 \log 2$$
Następnie sprawdzamy dla n=3.
$$T(3) \leq c3 \log 3$$
$$\frac{3}{4}*3+\frac{1}{4}*3+4*3 \leq c3 \log 3$$
$$15 \leq c3 \log 3$$
Powyższe nierówności dla n=2 oraz n=3 są spełnione gdy
$$c \geq \frac{10}{2 \log 2}.$$
Wartość \(\displaystyle{ n_0}\) wynosi więc 2."
Czy to co napisałem jest poprawne?

[matmatmm]

$$T(1) \leq 0$$
Powyższa nierówność nie jest spełniona dla n=1.

Z czego według Ciebie to wynika? Skąd wiesz ile wynosi \(\displaystyle{ T(1)}\)?

Poprawnie postawiona treść zadania powinna zawierać konkretny warunek początkowy. Na przykład:

\(\displaystyle{ T(n) = T(\lfloor\frac{3}{4}n\rfloor) + T(\lfloor\frac{1}{4}n\rfloor) + 4n}\) dla \(\displaystyle{ n>0,n\in\NN}\)
\(\displaystyle{ T(0)=-13\sqrt{3}+2\pi^2}\)

Liczba \(\displaystyle{ -13\sqrt{3}+2\pi^2}\) jest zupełnie przypadkowa.

[Mefrix]

Treść zadania jest w moim przypadku identyczna jak u osoby, która założyła ten wątek. Zadanie to jest natomiast rozwiązywane od lat na uczelni, więc wydaje mi się, że jest sformułowane dobrze. T(1) obliczyłem podstawiając po prostu 1 za n w początkowym wzorze. Czyli
$$T(1) = \frac{3}{4}*1 + \frac{1}{4} *1 +4*1=5.$$
Myślałem, że mogę to w ten sposób obliczyć. Zadanie to jest natomiast z przedmiotu "Algorytmy i Struktury Danych" więc zakładam, że n reprezentuje tutaj jakąś liczbę danych, tak więc musi należeć do naturalnych (o ile ma to jakiś sens).