algorithm - マスターメソッドを使用して再発を解決する

Question

私が書いたアルゴリズムの複雑さを調べるために再帰関係を解こうとしています。これが等式..

T(n) = T(n-1) + Θ(n)

そして、O(n2) の答えを見つけましたが、それが正しかったかどうかはわかりません。誰か確認してくれませんか？

更新: 式が T(n) = T(n-1)+Θ(nlogn) の場合はどうなりますか? それでも O(n2) でしょうか?

Answer 1

はい、あなたはそれを正しく推測します。

しかし、再帰の形はMasterメソッドには合いません。境界を正しく推測したので、ここでは置換法が適しています。

ここで、あなたの仕事は 2 つの定数cを見つけて、それn0を証明することです。

T(n) <= c*(n^2)すべてのためにn >= n0

Answer 2

O(N)+O(N-1)+...+O(1) = O(N*(N+1)/2) です。そうです、全体の複雑さは二次です。