为何这段Python代码的时间复杂度是O(n log n)而非O(n²)？

首先明确前提：设nums_lst的长度为n，外层循环总共执行n次。我们拆分两个分支分别计算复杂度：

• 前10次循环（i < 10）：每次执行一个遍历整个列表的内层循环，时间复杂度是O(n)，总操作次数为10 * n。但当n足够大时，这部分属于低阶项，增长速度远慢于n log n，在大O表示法中可以直接忽略。
• 剩余n-10次循环（i >= 10）：每次执行的while循环中，j从1开始每次乘以2，直到j >= n，循环次数是log₂n（即O(log n)）。当n很大时，n-10可以近似看作n，这部分总操作次数约为n * log n，是整个代码的复杂度主导项。

把两部分加起来，总操作次数的大O表示只保留增长最快的主导项，因此最终时间复杂度是O(n log n)。

你之前的误区在于，错误地认为所有外层循环都执行最坏情况的O(n)分支，但实际上只有固定的10次是O(n)，剩下的绝大多数循环都是O(log n)分支，不能直接用“最坏情况×总循环次数”来计算，必须分情况统计各分支的实际执行次数和对应复杂度。

for i in range( len(nums_lst)):
  if i < 10:
      for k in range( len(nums_lst)):
          print(nums_lst[0])
  else:
      j = 1
      while j < len(nums_lst):
          print(nums_lst[0])
          j *= 2

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