循环时间复杂度分析：

Question

为什么时间复杂度是O(n)而不是O(nlogn)？难道你不需要将外循环的复杂度乘以内循环的复杂度吗？

    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;
    }

Answer 1

在循环的第一次迭代中，内部循环覆盖n的一半，下一次迭代覆盖四分之一，然后是八分之一，依此类推。你可以用下面的函数来表示系数。如你所见，这是一个无穷级数，求和为1。因此，整个函数是O(n)。

​

​