代碼Θ（nLogn）的時間複雜度如何？

-4

int n; 
int i, j, k = 0; 
    for (i = n/2; i <= n; i++) { 
     for (j = 2; j <= n; j = j * 2) { 
      k = k + n/2; 
     } 
    }

只需要計算代碼片段的時間複雜度和答案是Θ（nLogn），但你能解釋它是如何Θ（nLogn）代碼Θ（nLogn）的時間複雜度如何？

所以你所有的信息的。爲什麼你不能計算？ –

你的提示是不是O（n！）但是，嚴重的是，如果你不能通過檢查找出它，在那裏放一些printf調用來跟蹤它被調用的頻率，看看你是否自己找不到模式循環大小？ –

「......你能解釋它是怎麼樣的嗎？」（你能解釋它怎麼可能是任何東西*但是*Θ（nLogn）？ – WhozCraig

這真的不是那麼難。

外環運行n/2次。這就是O(n)的複雜性。

內循環僅取決於n。它不依賴於第一個循環中的i。因此，對於內部循環的複雜性，我們可以完全忽略外部循環。多幸運！ j每次乘以2所以我們有logarithm base 2。那是O(log(n))。

的循環嵌套，所以我們大量繁殖，從而結尾：

O(n log(n))

2016-04-25 17:22:01 bolov

回答