比較運行時間如何確定要丟棄的值

例如。 O（N（N + 1））這會簡單地簡化到n^2 由於N^2 + N你會下降所述n比較運行時間如何確定要丟棄的值

另外 2000N^2 將簡單地是n^2

也 0.001n^3將簡單地是n^3

這是正確的嗎？

2016-10-01 mike lansing

我相信這三種情況都是正確的。編輯：要回答你的問題，只需減少常量。「O（n）」等人並不真正關心他們，即使他們*是顯着的。這篇文章已經被很好的覆蓋了：http://stackoverflow.com/questions/22188851/why-is-constant-always-dropped-from-big-o-analysis – Manhattan

O(n(n+1))將簡化爲O(n^2)因爲n(n+1)小於或等於n^2一個常數因子，對於足夠大的n：

n(n + 1) <= n^2 + n <= n^2 + n^2 <= 2n^2

其他的簡化是正確的，因爲你只是刪除常數因子。

基本上，您可以從表達式中移除一個常數因子和任何生長較慢的項。

來源

2016-10-02 00:23:53 fgb

比較運行時間如何確定要丟棄的值

回答

相關問題