为什么指定嵌套循环代码的时间复杂度是O(n)而非O(log n)

第二段代码时间复杂度为O(n)的推导 #

我们可以通过累加所有内层循环的总执行次数来计算复杂度：

• 外层第一次循环时x = n，内层循环需要执行n次
• 外层第二次循环时x = n/2，内层循环需要执行n/2次
• 外层第三次循环时x = n/4，内层循环需要执行n/4次
• 以此类推，直到x减小到0为止

所有内层循环的总执行次数为公比是1/2的等比数列求和：
n + n/2 + n/4 + n/8 + ... + 1
按照等比数列求和公式计算可得总次数无限趋近于2n，即总执行次数始终小于等于2n，属于线性规模，因此整体时间复杂度为O(n)。

和第一段代码的差异对比 #

第一段代码的内层循环不管外层x的取值是多少，每次都固定执行n次，外层总执行次数为n * log₂n，因此复杂度是O(n log n)；第二段代码的内层循环次数会跟随x的取值同步递减，累加后的总规模没有达到n log n的量级。

内容的提问来源于stack exchange，提问作者MD TAHMID HOSSAIN