Рецидивовые отношения домашние задания борьба
-
27-10-2019 - |
Вопрос
Вот вопрос:
Решите рецидив путем получения тета, связанной с t (n), учитывая, что t (1) = тета (1).
T(n) = n + T(n-3)
Попытка решения:
T(n) = T(n-6) + (n-3) + n
= T(n-9) + (n-6) + (n-3) + n
= T(n-(n-1)) + [(n-n) + (n-(n-3)) + (n-(n-6)) + ... + n]
= T(1) + [0 + 3 + 6 + ... + n]
= theta(1) = 3[1 + 2 + 3 + ... + n/3]
= theta(1) + [(n/3)(n/3 + 1)]/2
= theta(1) + (n^2+3n)/6
Когда я дважды проверяю, чтобы увидеть, соответствует ли решение рецидив, оно не работает.
Решение
Проблема заключалась в том, что вы получили неправильное суммирование. Он не начинается с 0, поскольку ваша последняя t-функция была t (n-(n-1)), что означает, что предыдущий был t (n- (n-4)). Таким образом, суммирование начинается в 4 и поднимается до н.
Если вы не знаете, как найти суммирование этого, я бы посоветовал вам посмотреть на некоторые доказательства из формулы суммирования. Это то, как выглядит решение.
T(n) = T(n-3) + n
= T(n-6) + (n-3) + n
= T(n-(n-1)) + [ (n-(n-4)) + (n-(n-7)) + ... + n]
= T(1) + [4 + 7 + ... + n]
= theta(1) + (4 + n) * (n - 1)/6
Не связан с StackOverflow