遍历字典列表的大 O 时间复杂度

Big O time complexity of looping over a list of dictionaries

我试图计算出遍历字典列表然后进一步遍历每个字典键的时间复杂度。

一个例子是:

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

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

我倾向于说这是 O(n^2),其中最坏的情况受列表大小和每个字典中键值对数量的影响。

这是正确的吗?

您的运行时复杂度是 O(n) * O(k) 其中:

  • n为n(列表长度)
  • k 每个列表元素的项目数(可能与 n 不同)

所以,你的复杂度确实是但是只有当k约等于n