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(sumk=1n kn) = O(nn)O(nn)xn+1/(n+1)n1O(nn)