Sprytna rekurencja

0

Mam do wykazania dokładne asymptotyczne oszacowanie na rekurencje

T(n) = T(n-sqrt(n)) + 1

Odpowiedz to T(n) = Theta(sqrt(n)).

Przyjszyjmy się najpierw ograniczeniu górnemu, jeżeli pokażę, że operacja n -> n-sqrt(n) po O(sqrt(n)) krokach zmniejsza n o co najmniej n/2, to wystarczy zeby wykazac ze laczny czas jest O(sqrt(n)) (przesumowanie sumy), jednak nie wiem jak dokonać tego kroku, jakieś pomysły?

0

Matematyczny formalizm nie jest moją mocną stroną, ale można np. podstawić pod n k2, wtedy masz T(k2) = T(k^2 - k) + 1. Mentalne rozwinięcie tego przypomina mi wzór 1 + 2 + ... n = (n +1) * n / 2. Jakoś z tego formalny dowód już się chyba da stworzyć.

0

To raczej nie prowadzi do rozwiazania. Jednak znalazłem już ładną metodę.

0

Próbowałem coś wczoraj wymyślić, ale nie miałem szczególnie weny więc dałem sobie spokój. Tym niemniej:

To raczej nie prowadzi do rozwiazania. Jednak znalazłem już ładną metodę.
Jeśli zadałeś pytanie na forum i znalazłeś samodzielnie rozwiązanie, dobrym zwyczajem jest pochwalenie się nim.
Tak, tym razem nikt na forum się nie popisał wiedzą, ale być może ktoś inny w przyszłości (za rok, dwa) zajrzy tutaj mając taki sam problem - możesz go uratować :>.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0