这段代码的时间复杂度是多少？如何？在大O

Question

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

我遇到了这个问题，这就是我的想法。外循环将运行、N/2 次，内循环将运行 logN 次，因此它应该是 N/2*logN。但这不是正确的答案。正确答案是 O(NlogN)，谁能告诉我我错过了什么？任何帮助将不胜感激。

Answer 1

让我们看一下这段代码。

首先，你可以注意到内部循环不依赖于外部，所以它的复杂度不会在任何迭代中改变。

for (j = 2; j <= n; j = j * 2) {
    k = k + n/2;
}

我想，你的知识足以理解，这个循环的复杂度是O(log n)。

现在我们需要了解这个循环将执行多少次。所以我们应该看看外部循环

for (i  = n/2; i <= n; i++) {

并找出 n / 2 次迭代，或 O(n) Big-O符号。

结合这些复杂性，您会发现，您的 O(log n) 循环将执行 O(n) 次，所以总复杂度将是 O(n) * O(log n) = O(n log n).

what is the time complexity of this code and how? in Big-O