算法时间复杂度:循环中i/= 2

Question

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

我是时间复杂度计算的新手.对于这个算法,我得到的答案是O(nlogn),但答案显然是O(n).

我的逻辑是外部循环具有指数下降并且将发生log_base2_(N)次.内环将成为几何和总共运行N次(第一次迭代是N/2次,然后是N/4,然后是N/8 ......).如果我将这些放在一起并将它们作为嵌套循环的结果加倍,那就是我想出的O(NlogN).我错过了一些明显的东西吗

Answer 1

外循环总共运行log(n)次.现在如果你观察内循环它第一次运行n次,接下来n/2次,依此类推,所以它就是系列

n(1 + 1/2 + 1/4 + 1/8 + 1/16 + ...)

这个的总和是(2*n),这意味着它是O(n)

因此,时间复杂度为O(n),因为外循环运行O(logn)次,内循环运行O(n)次.

它不是O(nlogn),因为内部循环每次不需要n个步骤,实际上所有步骤的总和将是O(n)