以下具有 2 个 for 循环的代码的时间复杂度是多少？
What is time complexity of following code having 2 for loops?
int count = 0;
for (int i = N; i > 0; i /= 2) {
for (int j = 0; j < i; j++) {
count += 1;
}
}
外循环运行 logn 次，内循环运行 logn 次，答案应该是 O(logn * logn)，而不是 O(n)，我不明白怎么回事？
如果您注意到 i 的步骤将是 N，N/2、N/4 ...
因此计数内循环将执行
N + N/2 + N/4 + N/8 +.... 次
那个系列的总和是O(N)
在此处阅读有关该系列的更多信息https://en.wikipedia.org/wiki/1/2_%2B_1/4_%2B_1/8_%2B_1/16_%2B_%E2%8B%AF
int count = 0;
for (int i = N; i > 0; i /= 2) {
for (int j = 0; j < i; j++) {
count += 1;
}
}
外循环运行 logn 次，内循环运行 logn 次，答案应该是 O(logn * logn)，而不是 O(n)，我不明白怎么回事？
如果您注意到 i 的步骤将是 N，N/2、N/4 ...
因此计数内循环将执行
N + N/2 + N/4 + N/8 +.... 次
那个系列的总和是O(N)
在此处阅读有关该系列的更多信息https://en.wikipedia.org/wiki/1/2_%2B_1/4_%2B_1/8_%2B_1/16_%2B_%E2%8B%AF