algorithm - このアルゴリズムの厳密な上限は?

Question

NP 困難な最適化問題を解くアルゴリズムを実装しました。このアルゴリズムの複雑さは ですO(sum (k = 1 to n) of k^n)。O(n^(n+1)) が上限であることはわかっていますが、きついかどうかはわかりません。このアルゴリズムの厳密な上限はどれですか: O(n^n)、O(n^(n+1))または他の何か?

ありがとう

Answer 1

答えはです。それを確認するには、累積サイズ の誤差項を使用して、合計を並列積分に置き換えることができることに注意してください。(合計はステップ関数の積分です。ステップ関数と連続関数の差に影を付けてから、それらをスライドさせます。関数は単調増加なので、これらの誤差の合計は最後の項に収まります。)と で評価することになります。それは、同じサイズの以前の誤差項と一致する項になります。O(sumk=1n kn) = O(nn)O(nn)xn+1/(n+1)n1O(nn)