关于一段C代码时间复杂度为O(n)而非O(n logn)的疑问

先拆解代码各部分的时间消耗：

• 第一个do-while循环：不管初始n是什么，最多执行3次就能让n被3整除，这部分是常数时间O(1)，完全可以忽略。

重点看嵌套循环部分，你之前的误解在于把内层循环当成了“线性操作”，但实际上内层循环的执行次数是随着外层变量j的减小而指数级缩减的，总操作次数是一个等比数列的和：

1. 外层for循环：j从调整后的n（3的倍数）开始，每次除以3，直到j>0，迭代次数是log₃n，也就是O(logn)次。
2. 内层while循环：每次k从j开始，k-=3直到k≤0，执行次数是⌈j/3⌉，约等于j/3次。

把每次外层循环对应的内层执行次数加起来，总操作次数为：

n/3 + n/(3²) + n/(3³) + ... + 1

这是首项为n/3、公比为1/3的等比数列，用等比数列求和公式计算：
总和 = (n/3) * (1 - (1/3)^k) / (1 - 1/3)，当k足够大时，(1/3)^k趋近于0，总和趋近于n/2，也就是**O(n)**的量级。

为什么不是O(n logn)？因为内层循环的执行次数不是每次都保持O(n)，而是每次都变为上一次的1/3，累加起来的总和是线性的，远小于n * logn的量级。

举个具体例子验证：

• 当n=9时，外层j依次为9、3、1，内层执行次数分别是3、1、1，总和5，约等于9/2=4.5；
• 当n=27时，内层执行次数分别是9、3、1、1，总和14，约等于27/2=13.5。

可以看到总操作次数始终和n呈线性关系，而非线性乘对数的关系。

内容的提问来源于stack exchange，提问作者3xhaust