请求分析Python函数时间复杂度，疑惑内层循环复杂度判定

要搞清楚这种循环的时间复杂度，核心是统计所有内层循环的总操作次数，而非单独看某一层的表现。

假设你的代码是这类典型结构（外层循环变量指数增长，内层循环次数随外层变量增大而递减）：

def func(n):
    i = 1
    while i < n:
        j = n
        while j > i:
            j -= i  # 或其他步长为i的操作
        i *= 2

步骤1：计算外层循环的迭代次数 #

外层循环中i从1开始，每次翻倍，直到i >= n。这个过程的迭代次数是log₂n次（因为当2^k ≈ n时，k就是log₂n）。

步骤2：计算单次外层循环对应的内层循环次数 #

当外层循环执行到第k次时，i的值为2^k，此时内层循环的次数约为n/(2^k)（比如j从n开始，每次减i直到j <= i，实际次数是floor(n/i)，近似为n/i）。

步骤3：求和得到总操作次数 #

把每次内层循环的次数累加，总次数为：
n/1 + n/2 + n/4 + ... + n/(2^{log₂n})

这是首项为n、公比为1/2的等比数列，求和结果为：
n*(1 - (1/2)^{log₂n +1})/(1 - 1/2) = 2n*(1 - 1/(2n)) = 2n -1

显然总操作次数的量级是O(n)，而非你猜测的O(logn)——因为等比数列的和趋近于2n，属于线性级别。

如果你的代码是其他结构（比如外层i线性增长，内层循环次数为n-i），总次数会是n(n-1)/2，复杂度为O(n²)，但从你的描述来看，更符合第一种指数外层循环的情况，最终复杂度为O(n)。

内容的提问来源于stack exchange，提问作者Roei Sharon