algorithm - 用最小或最大运算符表达算法的复杂性是否正确？

Question

我有一个算法可以在另一个堆栈中创建两个不同大小的有序堆栈的交集。该堆栈也应该订购。第一个的大小为n，另一个的大小为m。

while not empty(S1) and not empty(s2)
   //checks and possibly adds top element of S1 or S2 to S3, removes 
   //top element from only one of the stacks or from both if equal

我知道在最好的情况下，该算法具有 Θ(min(m, n)) 复杂度。以这种方式表达这种复杂性是否正确，还是我应该只使用 +、-、/、* 等运算符？我的意思是像 O(m + n) 这样的东西。

我是否应该考虑其中一个堆栈可以更小的事实？我们在计算算法的复杂度时通常会这样做吗？

Answer 1

是的，你可以使用它。

您可能还会发现这个 link 很有用