amortized-analysis - 循环时间复杂度分析：

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 的一半。下一次迭代覆盖四分之一，然后是八分之一，以此类推。您可以通过以下函数表示系数。如您所见，它是一个无限级数，总和为一。因此整个函数是 O(n)