请问下述示例代码的时间复杂度Big O是O(N)还是O(N²)？

arr = [
  [1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1],
  [1, 1]
]

def count_ones(outer_array):
  count = 0
  for inner_array in outer_array:
    for number in inner_array:
      count += 1
  return count

count_ones(arr)

结论 #

这段代码的时间复杂度为 O(N)，其中N为二维数组中所有元素的总个数。

分析过程 #

• 代码核心逻辑是遍历二维数组的每一个元素，每个元素会被恰好访问1次，对应执行1次count +=1操作，没有任何重复访问或者冗余操作。
• 很多人看到两层嵌套循环会误以为是O(n²)，这个结论是错的：只有当两层循环的遍历次数正相关（比如外层循环跑n次，内层循环每次固定跑n次）时才会得到平方复杂度。这段代码的内层循环遍历次数只和当前内层数组的长度有关，总遍历次数就是所有内层数组的长度之和，也就是二维数组的总元素数，和总元素数完全线性相关。
• 以题目给出的示例数组计算：总元素数为5+6+2=13，代码刚好会执行13次计数操作，完全符合线性复杂度的特征。

内容的提问来源于stack exchange，提问作者Hello Planet Earth