使用min/max运算符表述算法复杂度是否正确规范？

• 首先明确：算法复杂度的渐近表述完全允许使用min、max运算符，不存在只能使用加减乘除算术运算符的规则，你用Θ(min(m, n))描述该算法的最佳情况时间复杂度是规范、正确的。

对你的复杂度推导的验证 #

你写的核心循环本质是双指针思路的有序结构求交集逻辑，循环终止条件是两个栈中任意一个被弹空。最佳场景下，规模更小的栈处理完成后就会直接终止循环：
假设min(m,n) = k，如果长度为k的短栈所有元素的取值范围，和长栈的取值范围完全无重叠（比如短栈所有元素都小于长栈的最小元素，或都大于长栈的最大元素），那么循环只会执行k次，弹空短栈后直接结束，总操作数确实是Θ(min(m, n))量级，这个推导没有问题。

为什么常见的同类算法复杂度多写为O(m+n) #

你平时看到的O(m+n)一般是这类算法的最坏情况时间复杂度：当两个栈的元素完全交错（比如一个栈存所有正奇数、另一个存所有正偶数，最终交集为空），你需要把两个栈的所有元素都弹出比较完成才会终止循环，这时候总操作次数是m+n量级，O(m+n)是对最坏场景的开销描述，和你针对最佳场景用min的表述没有冲突，二者描述的是不同输入下的开销边界。

复杂度分析是否需要考虑两个输入的规模差异 #

当然需要。渐近复杂度分析的核心目标是精准刻画不同输入特征下的开销边界，只要你明确标注对应的分析场景（最佳/最坏/平均，或是特定输入分布），完全可以根据两个输入的大小关系用min、max做表述，这在正式的算法分析写作中是非常通用的写法，不存在不规范的问题。

内容的提问来源于stack exchange，提问作者Valikeny