用几何序列表达时间复杂度的困惑

Question

我有这个代码。

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

它的时间复杂度是 O(n) 我已经明白了原因，但我不明白为什么他们要把分析代码得出的这个数学表达式中的n去掉。

n(1 + 1/2 + 1/4 + 1/8 + …)

里面的括号可以看成是log(n) 所以不是n(log(n))? 只看表达式，不考虑算法）。

比如我在分析埃拉托斯特尼的筛子，我得到的表达式也是类似的。

n/2 + n/3 + n/5 + n/7 + … = n(1/2 + 1/3 + 1/5 +…)

所以括号里的内容可以看作是： loglogn 和外面的n，最后是。nlogogn

之间有什么区别。

n(1 + 1/2 + 1/4 + 1/8 + …)

到这里来 O(nloglogn)

并从这里得到。

n(1/2 + 1/3 + 1/5 +…)

O(n)?

Answer 1

第一序列收敛为2。https: /www.wolframalpha.cominput?i=1+%2B+1%2F2+%2B+1%2F4+%2B+1%2F8+%2B... ... 因此，它归结为O(n)。

第二个数列比较难分析，但可以证明与log(log(n))等价(至少没有那么快)，因此结果为O(nlog(logn))。举例证明。https:/medium.com@chenfelixtime-complexity-sieve-of-eratosthenes-fb0184da81dc。 .