代码Θ（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

回答