Как решить T (n) = T (n-3) + n ^ 2, используя итерацию?

Question

Как я могу решить T (n) = T (n-3) + n ^ 2, используя итерацию? По основной теореме ответ O (n ^ 3), но у меня возникли проблемы с решением путем итерации.

Answer 1

T(3) = T(0) + 3²
T(6) = T(3) + 6² = T(0) + 3² + 6²
T(9) = T(6) + 9² = T(0) + 3² + 6² + 9²
...

В общем, T(3N) - это сумма T(0) и в девять раз больше суммы натуральных квадратов до N. Хорошо известная формула Фолхабера оправдывает O(N³).

Аналогичные результаты имеют место для T(3N+1) и T(3N+2).

Answer 2

По прямому разрешению повторения:

Это линейное повторение первого порядка. Сначала мы решим однородную часть,

T(n) = T(n - 3)

, которая решается константой (точнее, тремя константами, поскольку три переплетенные последовательности образуют решение).

Теперь для неоднородной части мы используем ансац T(n) = an³ + bn² + cn + d, потому что мы знаем, что разность двух кубических полиномов является квадратичной.

Тогда

a(n³ - (n-3)³) + b(n² - (n-3)²) + c(n - (n-3)) = 9an² + 3(-9a + 2b)n + 3(9a - 3b + c) = n²

дает

a = 1/9, b = 1/2, c = 1/2.

Наконец

T(n) = (2n³ + 9n² + 9n)/18 + T(0)

и аналогично для двух других последовательностей.

Answer 3

Просто попробуйте расширить уравнение:

T(n) = n^2 + (n-3)^2 + (n-6)^2 + ... + 1 = \Theta(n^3)