代码 Θ(nLogn) 的时间复杂度如何？

Question

 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)

Answer 1

真的没有那么难。

外循环运行 n/2 次。那就是 O(n) 复杂度。

内部循环再次仅依赖于 n。它不依赖于第一个循环中的 i 。所以对于内层循环的复杂性我们完全可以忽略外层循环。多么幸运！ j 每次乘以 2，所以我们有 logarithm base 2。即O(log(n)).

循环是嵌套的，因此我们相乘，因此结束于：

O(n log(n))

How is time complexity of the code Θ(nLogn)?