是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)。