为何该算法的时间复杂度为O(n)而非O(n²)？

嘿，我来帮你拆解这个疑惑！你的误区在于混淆了嵌套循环和互斥分支循环的时间复杂度计算逻辑，咱们一步步理清楚：

• 首先明确时间复杂度的核心：我们计算的是最坏情况下，代码执行的总操作次数的量级，重点看「所有可能执行路径中，操作次数最多的那条路径」。
• 你提到的两个O(n)循环，应该是处于互斥的分支里（比如if/else结构）——也就是说，程序只会执行其中一个循环，不会同时执行两个。举个类似的代码例子：

  def process_list(arr):
      if some_condition:
          # 第一个循环：O(n)操作
          for _ in range(n):
              pass
      else:
          # else分支的循环：O(n)操作
          for item in arr:
              print(item)
  

  在这个例子里，不管走if还是else分支，最多只会执行一个O(n)的循环，总操作次数是n级别的，所以整体复杂度是O(n)。
• 那什么时候才会是O(n²)？只有当两个循环是嵌套关系的时候——也就是一个循环完全包含另一个循环，比如：

  def nested_loop(arr):
      for i in arr:
          # 外层循环执行n次，内层循环每次也执行n次，总操作n*n次
          for j in arr:
              print(i,j)
  

  这种情况下，总操作次数是n×n，才会对应O(n²)的复杂度。

简单来说：你的两个O(n)循环是互斥执行的，并非嵌套结构，所以最坏情况的总操作次数是线性的O(n)，而不是平方级的O(n²)。

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