マスターメソッドを使用して再帰を解く

私が書き込んだアルゴリズムの複雑さを知るために、漸化関係を解くことを試みています。これは、式..マスターメソッドを使用して再帰を解く

T（N）= T（N-1）+Θ（n）の

であると私はO（N2）への答えを見つけたが、私ならば、私はわからないんだけどそれは正しかった。誰かが確認してもらえますか？

更新：式がT（n）= T（n-1）+Θ（nlogn）の場合はどうなりますか？それはまだO（n2）になるのだろうか？

2012-02-29 questions

forallは

T(n) <= c*(n^2)あなたはO（N^2）について正しいが、これは次のようになり方程式ではありません。

今、あなたの仕事は、それを証明するために2つの定数cとn0を見つけることですマスターメソッドで解決しました。 – interjay

それはコメントするのが遅れた..しかし、まだこの答えを探しに来ている人のために。 http://techieme.in/solving-recurrences-master-method/ – dharam

O（N）+ O（N-1）+ ... + O（1）= O（N *（N + 1）/ 2）です。だから、複雑さは二次的です。

2012-02-29 22:16:37

方程式がT（n）= T（n-1）+Θ（nlogn）ならば？それはまだO（n2）になるのだろうか？ – questions

@ user1241347：私の推測はO（（N^2）* log（N））です。しかし、私はそれを計算していません。 –

はい、正しいと思います。

ただし、再発の形態はマスター方式には適合しません。バインディングを正しく推測しているので、ここでは置換方法が適しています。 n >= n0

2012-02-29 22:21:20 pad

方程式がT（n）= T（n-1）+Θ（nlogn）ならば？それはまだO（n2）になるのだろうか？ – questions

@ user1241347：いいえ、そうはなりません。新しいバウンドは 'O（（n^2）* logn）'でなければなりません。 – pad

答えて