#time-complexity #recurrence
#временная сложность #повторение
Вопрос:
T(1)=5 ,
и для всех n>=2: T(n)=2T(n-1) (3*n 1).
Я пытался решить эту проблему, но у меня проблема с 3 * n 1. Когда я ставлю n-1, n-2, …, я не знаю, как определить формулу для этой задачи.
Комментарии:
1. Возможно, я ошибаюсь, но похоже
((2^n)*n)2. Когда я ставлю n-2, я не получу 3 * n-5
3. Я голосую за закрытие этого вопроса, потому что это вопрос математики, а не вопрос компьютерного программирования.
4. Такие проблемы могут быть решены с помощью систем компьютерной алгебры, например wolframalpha.com/input/?i=T(n)=2T(n-1)+(3 *n+1) даст вам ответ. Учитывая ответ, легко проверить, что это ответ.
Ответ №1:
Поскольку существует только (3*n 1) как термин, а не T(3*n 1) это разрешимо. Первое впечатление: у вас есть 2T(n-1) как промежуточный термин, так что решение примерно такое 2^n .
С помощью простого анализа данных Excel я нашел решение T(n)=-7-3n 15 * 2^(n-1) , я попытаюсь решить его вручную и обновлю свой ответ, если найду правильный путь.
Редактировать: это было сложнее, чем ожидалось…
Объяснение:
- первый шаг — получить формулу суммы для
n. Вы можете вывести этот шаблон из первых несколькихT(n). - Как только вы получите шаблон, попробуйте избавиться от суммы.
- Чтобы решить суммы, попробуйте получить их в том же формате,
sum_(i=1)^n (1) = nчто и илиsum_(i=0)^n (2^i) = 2^(n 1)-1 - для этого вы можете манипулировать индексом, например,
sum_(i=2)^n (n-i) = sum_(i=0)^(n-2) (i)или включать / исключать элементы из суммы. - самой сложной частью было решить
sum_(i=0)^n ((n-i)*(2^i)). Идея здесь состоит в том, чтобы преобразовать умножение (в зависимости отi) в сумму (также в зависимости отi). - пожалуйста, обратите внимание на изменение индексов.
sum_(i=0)^n (2^i)это не то же самое, чтоsum_(i=1)^n (2^i) - Путь не самый эффективный, упрощайте по своему усмотрению.