Метод подстановки для решения повторяемости

Прежде всего извините за такой простой вопрос.

Но у меня возникают трудности с пониманием метода замены для решения повторений. Я следую Введению в Algo.s -CLRS. Поскольку я не могу найти достаточно примеров, и двусмысленность является главной проблемой. Особенно шаг индукции. В учебниках мы должны доказать, что f (n) подразумевает f (n + 1), но в CLRS этот шаг отсутствует или может быть Я не получаю пример. Пожалуйста, объясните шаг за шагом, как доказать, что O (n ^ 2) является решением рекуррентной функции T (n) = T (n-1) + n.

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


recurrence substitution algorithm induction
person Arjun Thakur    schedule 09.01.2013    source источник

Ответы (1)


arrow_upward
7
arrow_downward

В методе подстановки просто замените любое вхождение T(k) на T(k-1) + k и сделайте это итеративно.

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

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

Обратите внимание, что метод подстановки обычно используется, чтобы получить интуитивное представление о сложности, чтобы формально доказать ее — вам, вероятно, понадобится другой инструмент — например, математическая индукция.

Формальное доказательство будет выглядеть примерно так:

Claim: T(n) <= n^2
Base: T(1) = 1 <= 1^2
Hypothesis: the claim is true for each `k < n` for some `n`.
T(n) = T(n-1) + n <= (hypothesis) (n-1)^2 + n = n^2-2n + 1 < n^2 (for n > 1)
person amit    schedule 09.01.2013