Как решить: T (n) = T (n - 1) + n
У меня есть разработанное следующее:
T(n) = T(n - 1) + n = O(n^2)
Теперь, когда я разрабатываю это, я нахожу, что связанное очень свободно. Я сделал что-то не так, или это просто тот путь?
3 ответа
Подумайте об этом так:
На каждой "итерации" рекурсии вы выполняете O (n) работу.
На каждой итерации нужно выполнить n-1 работу, пока n = базовый случай. (Я предполагаю, что базовый случай - это O (n) работа)
Следовательно, предполагая, что базовый случай является константой, не зависящей от n, существует O (n) итераций рекурсии.
Если у вас есть n итераций O (n) работы каждая, O (n) * O (n) = O (n ^ 2).
Ваш анализ верен. Если вам нужна дополнительная информация об этом способе решения рекурсий, загляните в Деревья рекурсий. Они очень интуитивно понятны по сравнению с другими методами.
Выглядит правильно, но будет зависеть от базового случая T (1). Предполагая, что вы сделаете n шагов, чтобы получить от T (n) до T (0), и каждый раз, когда член n находится где-то между 0 и n для среднего значения n / 2, поэтому n * n / 2 = (n ^ 2) / 2 = O (п ^ 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) - ожидаемый результат.