我实现了一种算法来解决 NP-hard 优化问题。该算法的复杂度为 O(sum (k = 1 to n) of k^n)
。我知道 O(n^(n+1)
) 是一个上限,但我不知道它是否是一个紧的。哪个是此算法的严格上限:O(n^n)
、O(n^(n+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>)
术语与您之前相同大小的错误术语一起使用。
关于algorithm - 这个算法的严格上限是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17368630/