這個算法的上界是什麼？

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)在n和1。這出來一個O(nn)期限去與您以前的相同大小的錯誤期限。