多步骤算法最坏时间复杂度分析：取最长复杂度是否正确？

我需编写算法检查未排序正整数数组是否包含x和x²，若存在则返回其索引。我的方案是先用归并排序数组，再对x和x²分别执行二分查找。我得出该算法最坏时间复杂度为O(n log n)，因归并排序最坏复杂度为O(n log n)，二分查找为O(log n)。我想确认：分析多步骤算法整体效率时，是否只需取运行时间最长步骤的复杂度？还是有更复杂情况？

核心结论 #

大多数情况下，多步骤串行执行的算法，整体时间复杂度确实由量级最大的步骤主导，但也存在几种需要额外考虑的复杂场景：

• 串行步骤的常规情况：像你的方案里，归并排序（O(n log n)）和两次二分查找（O(log n)）是串行执行的。当n足够大时，O(n log n)的增长速度远快于O(log n)，后者的耗时可以忽略不计，所以整体复杂度取O(n log n)是完全正确的。
• 嵌套执行的情况：如果某个步骤是嵌套在另一个步骤的循环内部，就不能直接取最大值，而是要把两个步骤的复杂度相乘。比如要是你遍历数组的每个元素（O(n)），每个元素都做一次二分查找（O(log n)），那整体复杂度就是O(n log n)，而非取其中较大的那个。
• 输入规模变化的情况：如果后续步骤的输入规模不是原数组的n，而是经过前一步处理后缩小的规模，就得重新计算。比如先把数组过滤成仅包含小于100的元素（假设规模是O(k)），再对这个子数组做O(k log k)的排序，那整体复杂度就要看k和n的关系——如果k是n的常数分之一，那还是O(n log n)；如果k是固定值，那整体就是O(n)。
• 多同量级步骤叠加：如果有多个步骤的复杂度量级相同，比如先归并排序（O(n log n)），再做一次O(n log n)的遍历统计，整体复杂度依然是O(n log n)，因为大O表示法忽略常数系数，叠加后量级不变。

针对你的算法来说，因为是串行执行且归并排序的复杂度量级最高，所以你得出的O(n log n)结论完全正确。

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