初めまして、こんな初歩的な質問で申し訳ありません。
しかし、再発を解決するための置換方法を理解するのに苦労しています.Algo.s -CLRSの紹介に従っています。十分な例を見つけることができず、あいまいさが主な懸念事項です。特に誘導ステップです。教科書では、f(n) が f(n+1) を意味することを証明する必要がありますが、CLRS では、このステップが欠落しているか、そうである可能性があります。私は例を取得していません。O(n^2) が再帰関数 T(n)=T(n-1)+n の解であることを証明する方法を順を追って説明してください
私が理解したいのは、置換法の一般的な手順です。強力な数学的帰納法に光を当て、置換法に関する資料へのリンクを提供できれば、それも役立ちます。
T(k)置換法では、出現するbyを単純に置換し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)