今日は TA と会う予定でしたが、時間がありませんでした。私はアルゴリズム分析のクラスにいて、再帰関係を始めましたが、この問題を正しく行っているかどうか 100% 確信が持てません。私は立ち往生し、何をすべきかわからないところまで来ました。たぶん私はこれを間違ってやっています、誰が知っていますか。質問は上限または下限を気にしません。シータが必要なだけです。
問題はこれです：
T(n) = T(n-1) + cn^(2)
これは私がこれまでに持っているものです....
=T(n-2) + (n-1)^(2) + cn^(2)
=T(n-3) + (n-2)^(2) + 2cn^(2)
=T(n-4) + (n-3)^(2) + 3cn^(2)
したがって、この時点で、K を一般化して方程式に代入するつもりでした。
T(n-k) + (n-k+1)^(2) + c(K-1)^(2)
ここで、1 の基本ケースを写真に取り入れ始めます。以前のいくつかのより単純な問題では、一般化された k 方程式を 1 に設定し、K について解くことができました。次に、K を方程式に戻して最終的な答えを得ることができました。
しかし、私は (n-k+1)^(2) 部分に完全に行き詰まっています。つまり、実際にこれをすべて無効にする必要がありますか? 私はそれをして、k^(2)-2kn-2k+n^(2) +2n +1 = 1 を得ました。問題。
これを解決する方法について誰か助けてもらえますか？大変ありがたく存じます。