Is it O(L1 + L2) or O(max(L1, L2))?

Question

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

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

Answer 1

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

Answer 2

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

O(L1 + L2) = O(2*L2) = O(L2)。同理，O(max(L1, L2)) = O(L2)。在这两种情况下，复杂度都是0 (L2)