data-structures - 是 O(L1 + L2) 还是 O(max(L1, L2))？

Question

我们有两个长度为 L1 和 L2 的列表。我们一个接一个地遍历了这两个列表。整体操作的时间复杂度是多少？

是 O(L1 + L2) 还是 O(max(L1, L2))？
两者有什么区别？

Answer 1

第一个 O(L1 + L2) 是合适的。例如，在使用 V 作为顶点数，使用 E 作为边数的图算法中，许多操作都以 O(V + E) 的形式表示，例如图的深度优先搜索。当然，在这种情况下，E 的范围可能从 O(V) 到 O(V^2)。如果 L1 和 L2 相对于彼此是固定的，那么 O(max(L1, L2)) = O(L1) 或 O(L2) 可能更合适。

Answer 2

两者没有区别。不失一般性，假设 L1 = O(L2)；如果不是，那么 L2 = O(L1) 你可以交换符号。

O(L1 + L2) = O(2*L2) = O(L2)。类似地，O(max(L1, L2)) = O(L2)。所以在这两种情况下，复杂度都是 O(L2)。