複雜性分析 - 以考慮非對數因子

只是爲了我的考試快速準備，比如我有：複雜性分析 - 以考慮非對數因子

f(x) = 5x<sup>2</sup> + 4x * log(x) + 2

會大O是O(x<sup>2</sup> + x * log(x))或者我應該考慮非對數係數如5或4？

同樣，考慮下面的代碼

for (int i = 0; i < block.length; i++) 
    for (int j = 0; j < block.length; j++) 
     for (int k = 0; k < 5; k++) 
      g(); //assume worst case time performance of g() is O(1)

所以會大O爲O（5N ）或爲O（n ）？

來源

2012-06-21 Mountain

複雜的f(x) = 5x^2 + 4xlogx + 2是O(x^2)因爲

O(g(x) + k(x)) = max(O(g(x), k(x)) 
// and O(X^2) > O(xlogx) 

//additionally coeffs are disregarded 
O(c*g(x)) = O(g(x))

所以，如果你有一個和你只是選擇最大的複雜性，因爲在這一天結束的時候ñ趨於無窮大的最大組成部分將給予最計算量。這也不要緊，如果你有任何coeffs，因爲你試圖大致估計會發生什麼。

您的其他樣本見下文

for (int i = 0; i < block.length; i++) 
    for (int j = 0; j < block.length; j++) 
     for (int k = 0; k < 5; k++) 
      g(); //assume worst case time performance of g() is O(1)

先轉換推理循環到資金和順利實施的資金從1左

Sum (i=0,n) 
    Sum(j=0, n) 
     Sum(k=0, k=5) 
      1

計數器O（1）至5仍然是O（1），請記住你忽視了coeffs

Sum(k=0, k=5) 1 = O(5k) = O(1)

所以，你最終用中指總和，它計算O（1）n倍的功能，這給O（n）的

Sum(j=0, n) 1 = O(n)

最後你到了最左邊的總和，並注意你算的複雜性ン -times，即n+n+n...，其等於或n*nn^2

Sum (i=0,n) n = O(n^2)

所以最終的答案是O（n^2）。

來源

2012-06-21 12:10:43 oleksii

所以對於嵌套循環問題，考慮到O（log（5n^2））== O（log（n）+ log（n）+ log（5）），我應該忽略log（5）並保持log（n）+ log（n ）=> O（log（n^2））？ – Mountain

@Mountain我爲第二部分添加了推理。我不太確定你爲什麼要在那裏登錄？ – oleksii

哦，對不起，我只是搞砸了一點，儘管過夜的工作太多...... :)無論如何，你更新回答我的問題，非常感謝！ – Mountain

O(x**2)因爲：

lim n^2 if (x->8) = 8

lim 5n^2 if (x->8) = 8

8 is infinity

，但如果你有幾個表現的總和，你需要了解發展最快的功能。這將是對你的問題的答案。

表達前的任何其他常數會給你相同的答案。在這種情況下，您應該使用asymptotic analysis 我可能會給你一個建議。如果您遇到幾個函數的和你需要：

分解的成分的表達

想象每個元素

理解增長最快的因素，其不超過無限

的地塊

這個元素會給你答案

來源

2012-06-21 12:11:11

複雜性分析 - 以考慮非對數因子

回答

相關問題