算法时间复杂度:循环中i/= 2 [英] Algorithm Time Complexity: i/=2 in loops

问题描述

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).

I'm a very new to the time complexities calculations. For this algorithm, I get the answer to be O(nlogn), but the answer is apparently O(n).

我的逻辑是外循环呈指数下降，并且将发生log_base2_(N)次.内循环在变成一个几何和时将总共运行N次(第一次迭代是N/2次，然后是N/4，然后是N/8 ...).如果我将它们放在一起并作为嵌套循环的结果乘以它们，那就是我要使用O(NlogN)的地方.我缺少明显的东西吗?

My logic was the outer loop has an exponential decline and will occur log_base2_(N) times. The inner loop will run a total of N times as it becomes a geometric sum (first iteration it is N/2 times, then N/4, then N/8 ...). If I put these together and multiply them as a result of the nested loop, that's where I'm coming up with O(NlogN). Am I missing something obvious?

推荐答案

外部循环总共运行log(n)次.现在，如果您观察到内循环，则它第一次运行n次，然后运行n/2次，依此类推，所以它构成了系列

The outer loop would run a total of log(n) times. Now if you observe the inner loop it first time it runs n times, next n/2 times and so on, so it makes the series

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

总和为(2 * n)，这就是O(n)

the sum of this would be (2*n), That means it is O(n)

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

Hence the time complexity is O(n) since outer loop runs O(logn) times and inner loop runs O(n) times.

它不是O(nlogn)，因为内部循环每次都不会执行n步，实际上，所有已执行步骤的总和为O(n)

It is not O(nlogn) since the inner loop does not take n steps each time, in fact the sum of all steps taken would be O(n)

这篇关于算法时间复杂度:循环中i/= 2的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！