遍历字典列表并迭代每个字典键的Big O时间复杂度是多少？

你给出的示例代码如下：

n = [
  { 'a': a, 'b': b, ...},
  { 'a': a, 'b': b, ...},
]

def solve(n):
  for item in n:
     for key in item:
       ....

你初步得出的O(n²)结论并不完全正确，核心问题是没有明确定义复杂度的统计变量

• 首先定义两个独立的统计变量：
  • L：外层列表的长度，即列表中存储的字典总数
  • K：单个字典包含的键值对数量，最坏情况下取所有字典的最大键数
• 双重循环的总操作次数等于所有字典的键值对总数，通用的无场景假设的时间复杂度应为O(L*K)
• 分场景细化复杂度结论：
  1. 如果每个字典的键数是固定常数（比如所有字典固定只有a、b两个键），则K是可省略的常数项，时间复杂度为O(L)
  2. 只有当单字典键数K和列表长度L正相关，且增长速率和L一致时（比如列表长度为10时每个字典有10个键，列表长度为100时每个字典有100个键），总操作次数才近似为L²，此时时间复杂度才是O(L²)
  3. 如果把所有字典的总键数记作N，那么无论什么场景，这个遍历操作的时间复杂度都可以表述为O(N)，因为本质上你只是把所有字典的所有键都遍历了一次，每个键仅被处理一次
• 你之前的误区在于混淆了变量定义：你把外层列表的变量名n默认当成了唯一的规模变量，同时把单字典的键数也默认等同于n，才会得出平方级的复杂度结论，这个推导前提是不成立的。

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