时间复杂度：O(logN) 还是 O(N)？

Question

3

我原以为以下代码的时间复杂度是O(log N)，但答案却说是O(N)。我想知道为什么：

int count = 0;
for (int i = N; i > 0; i /= 2) {
    for (int j = 0; j < i; j++) {
        count += 1;
    }
}

对于内部的for循环，它运行了这么多次： N + N/2 + N/4 ...

在我看来，这似乎是logN。请帮助我理解为什么会是这样。谢谢。

- TonyGW

2个回答

0

根据代码片段，逐步进行，我们得到：

- Mohamed Ennahdi El Idrissi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Pei Guo · Accepted Answer

1, 1/2, 1/4, 1/8... 1/2 ** n是一个等比数列，其中a = 1，r = 1/2（a为第一项，r为公比）。

它的总和可以使用以下公式计算：

在这种情况下，总和的极限为2，因此：

n + n/2 + n/4 ... = n(1 + 1/2 + 1/4...) -> n * 2

因此，复杂度为O(N)。