Решить повторение: T (n) = T (n - 1) + T (n - 2) + 3

Question

T (1) = T (2) = 1, а для n> 2 T (n) = T (n - 1) + T (n - 2) + 3.

Что Iveсделано до сих пор:

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

Я не уверен, правильно ли это, и если да, то как мне избавиться от T (n-4).

Answer 1

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

Два метода, которые я могу предложить:

---

1. Подстановка + стандартная теорема

Произведите следующую подстановку переменных:

Это в правильной форме для метода Акра-Бацци , с параметрами:

---

2. Формула Фибоначчи

Ряд Фибоначчи имеет явную формулу, которую можно получить, угадав решение вида Fn = a^n. Используя это как аналогию, замените аналогичное выражение для T(n):

Уравнение постоянных и экспоненциальных членов:

Возьмите положительный корень, потому что отрицательный корень имеет абсолютное значение меньше 1 и, следовательно, будет уменьшаться до нуля с увеличением n:

Что соответствует (1) .