算法复杂度咨询：嵌套While循环的时间复杂度推导是否正确？

首先看你给出的代码：

m = 12
while m>0:
  n = 0
  while n<m:
     n+=1 
  m/=3

你的推导结果是错误的，下面是正确的复杂度分析：

• 外层循环轮数：初始m为N（这里N=12），每轮m变为原来的1/3，直到m趋近于0。循环轮数是log₃N级别的（渐近复杂度只看主导项，后续处理小数m的循环可忽略）。
• 每轮内层循环执行次数：第一轮是N次，第二轮是N/3次，第三轮是N/9次……最后几轮当m小于1时，内层执行1次。

总执行次数是首项为N、公比为1/3的等比数列求和：
$$N + \frac{N}{3} + \frac{N}{9} + \frac{N}{27} + ...$$

根据等比数列求和公式，无穷项的和为 $\frac{N}{1 - \frac{1}{3}} = \frac{3}{2}N$，这是线性规模的结果，因此该算法的时间复杂度是O(N)（N为初始m的值）。

你推导的错误在于，错误地将每轮内层循环的次数都等同于N+1，再乘以循环轮数log₃N。但实际内层循环次数是逐次按1/3比例递减的，并非始终保持与初始N同规模的次数。

内容的提问来源于stack exchange，提问作者Francisco Minchala Fajardo