再発を解決するための代替方法

Question

まず、このような基本的な質問をおかけして申し訳ありません。

しかし、私は再発を解決するための置換方法を理解することが困難です.Algo.sCLRSの紹介に従っています。私はf（n）がf（n + 1）を意味することを証明しなければならないが、CLRSではこのステップが欠落しているか、またはそうであるかもしれないことを証明する必要があるテキストブックでは、私は例を得ていない。 O（n^2）= T（n-1）+ n

私が理解したい代替方法の一般的なステップ。もしあなたが強い数学的帰納法についていくつかの光を当てて、代用法についての資料へのリンクを提供することができれば助けになるでしょう。

Answer 1

置換方法では、T(k)の出現をT(k-1) + kに置き換えて繰り返し実行します。 sum of arithmetic progressionから

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)であることを得ることができます。

通常、置換方法は、複雑さが何であるかを直感的に理解するために使用されます。正式に証明するには、おそらくmathematical inductionのような別のツールが必要です。

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) 

：

正式な証明はそのような何かを行きます