Как решить: t (n) = t (n - 1) + n

Question

У меня сработало следующее:

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

Теперь, когда я разрабатываю это, я обнаружил, что граница очень свободна. Я сделал что -то не так или так?

Answer 1

Подумай об этом так:
В каждой «итерации» рекурсии вы выполняете O (n).
Каждая итерация имеет работу N-1, до n = базовый корпус. (Я предполагаю, что базовый случай - это (n) работа)
Следовательно, предполагая, что базовое дело является постоянным независимым от n, существуют O (n) итерации рекурсии.
Если у вас есть итерации O (n) работать каждый, O (n)*O (n) = O (n^2).
Ваш анализ верен. Если вам нужна дополнительная информация об этом способе решения рекурсий, посмотрите на рекурсионные деревья. Они очень интуитивно понятны по сравнению с другими методами.

Answer 2

Вам также нужен базовый случай для вашего отношения рецидива.

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

Чтобы решить это, вы можете сначала угадать решение, а затем доказать, что оно работает с использованием индукции.

T(n) = (n + 1) * n / 2 + c - 1

Сначала базовый корпус. Когда n = 1 это дает C по мере необходимости.

Для других n:

  T(n)
= (n + 1) * n / 2 + c - 1
= ((n - 1) + 2) * n / 2 + c - 1
= ((n - 1) * n / 2) + (2 * n / 2) + c - 1
= (n * (n - 1) / 2) + c - 1) + (2 * n / 2)
= T(n - 1) + n

Итак, решение работает.

Чтобы получить предположение в первую очередь, обратите внимание, что ваши отношения рецидивов генерируют Треугольные числа Когда c = 1:

T(1) = 1:

*

T(2) = 3:

*
**

T(3) = 6:

*
**
***

T(4) = 10:

*
**
***
****

etc..

Интуитивно треугольник составляет примерно половину квадрата, а в обозначениях Big-O константы можно игнорировать, поэтому O (n^2) является ожидаемым результатом.

Answer 3

Решение довольно легко для этого. Вы должны развернуть рекурсию:

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

У вас есть арифметическая прогрессия, а сумма 1/2*n*(n-1). Анкет Технически вам здесь не хватает граничного условия, но с любым постоянным граничным условием вы видите, что рекурсия O(n^2).

Answer 4

Взгляните правильно, но будет зависеть от базового случая t (1). Предполагая, что вы будете делать n шагов, чтобы получить t (n) до t (0), и каждый раз, когда n -член находится от 0 до N для среднего значения N/2, поэтому n * n/2 = (n^2)/2 = O (n^2).