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

Question

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

例如:

n = [
{ 'a': a, 'b': b, ...},
{ 'a': a, 'b': b, ...},
]
def solve(n):
for item in n:
for key in item:
....

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

正确吗?

Answer 1

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

• nis n (list length)
• k每个列表元素的项数(可以与n不同)

所以，你的复杂度确实是n²，但是只有当k近似等于n