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

Question

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

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

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

Answer 1

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

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 2

Думайте об этом так:
В каждой «итерации» рекурсии вы выполняете O (n) работу.
Каждая итерация имеет n-1 работу, пока n = базовый случай. (Я предполагаю, что базовый случай - O (n) работа)
Следовательно, предполагая, что базовый случай является постоянной независимой от n, существует O (n) итераций рекурсии.
Если у вас есть n итераций по O (n), каждая из которых O (n) * O (n) = 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).