Решение рекуррентных уравнений

Мой профессор дал мне несколько практических задач. Но они не являются домашним заданием или оцениваются, они предназначены для практики перед предстоящим тестом. Я бы спросил своего профессора, но она печально известна тем, что не очень помогает. Но я борюсь с этой проблемой и надеялся получить помощь.

Проблема заключается в следующем:

T(n) = 1 if n = 1

T(n-1) + n(n-1) if n>= 2

Она дает подсказку использовать суммирование и принять n = 2 ^ k

Пока это то, что у меня есть:

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

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

T(n-2) = T(n-3) + n-2(n-3)

Следовательно...

T(n) = T(n-3) + n(n-1) + n-1(n-2) + n-2(n-3)

это о том, когда я зашел в тупик, но я попытался продвинуться вперед и угадать, какое суммирование использовать.

T(n) = T(n-k) + (n(n+1)(2n+1))/6


recurrence iteration relation algorithm big-o
person bugdoctor9    schedule 13.04.2017    source источник
comment
Я голосую за то, чтобы закрыть этот вопрос как не по теме, потому что это вопрос математики, а не вопрос программирования.   -  person Raymond Chen    schedule 13.04.2017

Ответы (1)


arrow_upward
1
arrow_downward

Ну, телескопируя сериал, T(n) = 1 + sum(i(i-1) for i = 2..n). Это n(n-1)(n+1)/3 + 1 согласно Wolfram Alpha.

Или, если вы хотите сделать это вручную,

sum(i(i-1) for i = 2..n)
= sum(i(i-1) for i = 1..n) 
= sum(i^2 for i = 1..n) - sum(i for i = 1..n)

А затем используйте хорошо известные уравнения для сумм последовательных квадратов и сумм последовательных целых чисел.

person Paul Hankin    schedule 13.04.2017
comment
Так что это действительно будет O (n ^ 3) в любом случае, верно? - person bugdoctor9; 13.04.2017
comment
Да, n(n-1)(n+1)/3 + 1 равно O(n^3). - person Paul Hankin; 13.04.2017