这个算法的时间复杂度是多少？

Question

我有一个不同长度的列表列表，我的算法在子列表中的每个元素上运行。

我的时间复杂度应该是多少？

我不知道是否可以写成 O(n * m)，因为 n 是父列表的长度，m 是子列表的平均长度，或者可能是 O(n)，因为 n 是总元素的数量。

请解释一下符号的含义（例如n是父列表的长度）。

Answer 1

如果您有

n

个子列表，每个子列表包含

m

个元素，则

n*m

表示正在处理的元素总数，因此它的复杂度为

O(n*m)

。

如果子列表的元素数量不等，可以将其总结为

O(N)

，其中

N

是数组中元素的总数。

Answer 2

您可以定义变量，因此完全可以说“O(n)，其中 n 是输入的大小”。

您的情况似乎与“稀疏”矩阵方法类似：稀疏矩阵具有明确定义的宽度和高度，以及（非零元素的）总大小。 算法性能描述可以酌情使用所有三个参数。

最终应该是关于什么方便描述算法。

Answer 3

您总共执行了 N 次操作。 因此，除非您的算法访问其中的一些其他元素，否则它会成为 O(N) 操作。 从一个子列表转换到下一个子列表的行为即使需要相当长的时间，也是一个 O(m) 操作。但由于 m 小于 N，您可以忽略它，因为当 N 变得非常大时，它会压倒 O(m) 时间。 事实上，“顺序”分析的全部目的是展示算法在极端条件下的响应能力。