大小为n与n²的两个有序序列查找公共元素的最优时间复杂度求解

核心思路 #

你提到的常规O(m+n)双指针法确实是有序序列求交集的通用最优解，但它的适用前提是两个序列长度接近。本题中两个序列长度差距极大，我们可以换更高效的思路：

• 选择长度更短的序列A（大小为n）遍历
• 对A中的每一个元素，在有序的长序列B（大小为n²）中做二分查找，判断元素是否存在

时间复杂度计算 #

二分查找长度为n²的有序序列的单次时间复杂度为O(log(n²)) = O(logn)，遍历A的n个元素总时间为O(n * logn)，对比双指针法的O(n + n²) = O(n²)，前者效率高出一个量级。

最终结论 #

符合要求的选项是Theta(nlgn)：

• 最坏情况下我们需要完成所有n次二分查找，每次查找的时间稳定在logn量级，整体时间复杂度和nlgn严格同阶，因此用紧界Theta表示更准确
• 只有当两个序列长度差小于log级时，双指针的O(m+n)方案才更优，本题场景显然不满足该前提

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