algorithm - 这个算法的严格上限是多少？

Question

我实现了一种算法来解决 NP-hard 优化问题。该算法的复杂度为 O(sum (k = 1 to n) of k^n)。我知道 O(n^(n+1)) 是一个上限，但我不知道它是否是一个紧的。哪个是此算法的严格上限:O(n^n)、O(n^(n+1)) 或其他？

谢谢

Answer 1

答案是O(sum<sub>k=1</sub><sup>n</sup> k<sup>n</sup>) = O(n<sup>n</sup>) .要验证这一点，请注意总和可以，累积大小的误差项 O(n<sup>n</sup>) , 被平行积分取代。 (总和是阶跃函数的积分。将阶跃函数与连续函数之间的差异涂上阴影，然后将它们滑过。由于函数是单调递增的，因此这些误差的总和适合最后一项。)求解定数积分，你结束评估 x<sup>n+1</sup>/(n+1)在n和 1 .结果是 O(n<sup>n</sup>)术语与您之前相同大小的错误术语一起使用。