Szacowanie rozwiązania rekurencji

[matmatmm]

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

Jakbyś dobrze podstawił, to byś dostał (przy założeniu, że chodzi o liczby naturalne):

\(\displaystyle{ T(1)=T(\lfloor \frac{3}{4}\rfloor)+T(\lfloor \frac{1}{4}\rfloor)+4=2T(0)+4}\)

czyli nie znając \(\displaystyle{ T(0)}\) nie wiadomo ile wynosi \(\displaystyle{ T(1)}\).

A treść z pierwszego posta w ogóle nie mówi o dziedzinie, więc jest niepełna.

Dodano po 8 minutach 14 sekundach:
Dobra przeoczyłem coś. Warunek początkowy nie jest konieczny, bo \(\displaystyle{ T(0)}\) da się obliczyć z równania. Podstawiając \(\displaystyle{ n=0}\) dostajemy

\(\displaystyle{ T(0)=T(0)+T(0)+4\cdot 0}\)
\(\displaystyle{ T(0)=0}\)

Także \(\displaystyle{ T(1)=2T(0)+4=4}\) i dalej już da się policzyć kolejne wartości.

[Mefrix]

Z tym podstawianiem to rzeczywiście głupoty popisałem. Zastanawiam się jeszcze czy jeśli w poleceniu nie ma podłóg, to znaczy, że sam powinienem je dopisać przy rozwiązywaniu? Patrząc na wszystkie inne podobne rozwiązania w internecie podłoga (lub sufit) zawsze w zadanej rekurencji występuje, a tutaj nie.

[matmatmm]

Ja na Twoim miejscu bym próbował dopytać o dokładną treść, bo dziedzina nie jest podana.

[Mefrix]

Zapytałem prowadzącego zajęcia czy w mogę użyć rozwiązania z użyciem podłóg. W odpowiedzi dostałem, że "ciężko powiedzieć czy można użyć tam podłogi, bo nie jest to jasne z treści zadania". Zaproponowano mi również rozwiązanie z założeniem, że n jest potęgą czwórki i porównanie czy wyniki będą się bardzo różniły z rozwiązaniem z użyciem podłóg. Na końcu dodano, że mógłbym zostawić to rozwiązanie z użyciem podłóg, ale należałoby to jakoś "skomentować".

Myślę, że zostanę więc przy rozwiązaniu z podłogami, tylko nie wiem do końca jak miałbym to "skomentować". Może trzeba dopisać np., że stosuję podłogi, bo nie będzie to miało większego wpływu na złożoność albo może coś w stylu "parametry określające egzemplarze problemów dla algorytmów są niemal wyłącznie liczbami naturalnymi". Które uzasadnianie byłoby właściwe (o ile jakiekolwiek z tych dwóch jest właściwe)?

[matmatmm]

Ja bym go raczej zapytał jaka jest dziedzina funkcji \(\displaystyle{ T}\), bo w treści nie jest to podane, a ma to znaczenie.

Skomentuj, że pod założeniem, że dziedziną są liczby naturalne, wyrażenie \(\displaystyle{ T\left(\frac{1}{4}n\right)}\) nie zawsze ma sens, a z podłogami już tak.

[Mefrix]

Czy jeśli już przybliżam, to nie powinienem dla \(\displaystyle{ T(\frac{3}{4} \cdot n)}\) użyć sufitu zamiast podłogi?

Dodano po 31 minutach 4 sekundach:
Chociaż może nie ma to w zasadzie żadnego znaczenia.

[matmatmm]

Jak użyjesz sufitu dla \(\displaystyle{ \frac{3}{4}n}\), to dostaniesz

\(\displaystyle{ T(0)=0}\)

\(\displaystyle{ T(1)=T(0)+T(1)+4}\)
\(\displaystyle{ T(0)=-4}\)

Sprzeczność.

Z podłogą jest lepiej bo zasada indukcji gwarantuje ci, że taka funkcja \(\displaystyle{ T}\) istnieje.