時間複雜度最小漸近運行時間

f（n）= n^3/logn的時間複雜度是多少？而對於一個雙系列（2個和）？我知道它是多項式或多項式。時間複雜度最小漸近運行時間

這可能會更好地服務於理論計算機科學堆棧交換 –

@PeterKlipfel理論計算機科學堆棧交換僅適用於研究級別的問題。我懷疑他們會喜歡這個問題。這是非常基本的東西。 – Nabla

@PeterKlipfel然而有http://cs.stackexchange.com，這是爲普通觀衆。 – Nabla

f(n) = n^3/log(n)顯然是Θ(n^3/log(n))，這也是o(n^3)，但是ω(n^2)。因此，該函數不會比多項式增長得快，但比多對數更快（因爲所有多對數函數的增長都比二次函數慢，實際上比任何功率都慢）。

實際上對於所有的ε > 0：f(n) in ω(n^(3-ε))。

所有這些陳述的證明應該非常簡單。

第二個問題取決於總和限制和內部術語。

2014-02-06 20:45:42 Nabla

它是：（sum i = 1 to n）（sum j = 1 to i）of j – user3251244

@ user3251244請加上以及和內部項的複雜性（可能是常數）到你的問題（見編輯按鈕）。 – Nabla

回答