關於爲O（n^2logn）

-1

void function(int n) { 
    int i, j , k ; 
    for (i = n/2 ; i <= n ; i ++) 
     for (j = 1; j + n/2 <= n; j++) 
      for (k = 1; k <=n ; k = k*2) 
       count ++; 
}

外環執行n/2的時間，中間循環執行n/2個時間和內LLOP執行LOGN時間。關於爲O（n^2logn）

上述函數的複雜度是O（n^2logn），但是n/2和n/2將如何變成n^2？

謝謝

來源

2013-03-12 vinay ss

循環是嵌套的，所以它們的所有計數都會相乘。（n/2）*（n/2）是n^2/4，但常量對於大O無關緊要; n^2/4 = O（n^2）並且是這樣寫的。

來源

2013-03-12 05:33:17 hobbs

謝謝你，這是有道理的。 – 2013-03-12 05:35:24

對於大O符號，省略了常量：「如果f（x）是幾個因素的乘積，則省略任何常數（產品中不依賴於x的項）。（n/2）*（n/2）* logn = 1/4（n^2logn），而1（n/2）*（n^2logn）/4被丟棄以給出O（n^2logn）。

參考： http://en.wikipedia.org/wiki/Big_oh_notation

來源

2013-03-12 05:35:33 wilsonmichaelpatrick

你的算法的確切迭代次數，而其增長的複雜性順序來推斷如下所示：

enter image description here

支持性文件：here

來源

2014-04-04 15:14:47

關於爲O（n^2logn）

回答

相關問題