求解两列表最小绝对差时直接遍历与先排序后遍历的时间复杂度对比

你对两种算法的时间复杂度推导都是正确的，第二种解法效率更高的核心原因是不同阶的时间复杂度的渐近增长速度差异极大，你对复杂度比较的方式存在误区。

• 首先明确时间复杂度的比较逻辑：时间复杂度描述的是输入规模无限增大时，算法执行时间的增长趋势，不是简单将两个复杂度做除法看结果是否大于0。O(mn)属于二阶多项式复杂度，而O(nlogn + mlogm)属于线性对数阶复杂度，线性对数阶的增长速度远低于二阶多项式。
  我们可以用实际数值直观对比差异：
  当两个列表长度n=m=1000时：
  • 暴力解法的运算量级是1000*1000 = 1,000,000次
  • 排序+双指针解法的运算量级是1000*log₂1000 + 1000*log₂1000 ≈ 20,000次，仅为暴力解法的2%
    当n=m=10000时：
  • 暴力解法运算量级是10^8次
  • 排序解法运算量级约为280,000次，仅为暴力解法的0.28%
    输入规模越大，两种解法的效率差距越明显。
• 其次解释你提到的除法误区：你将第二种解法的复杂度除以mn，得到的结果并不是固定大于0的常数，当输入规模趋向无穷大时，这个比值会无限趋近于0。以n=m的场景为例：
  比值 = (nlogn + mlogm)/mn = 2logn /n
  logn的增长速度远慢于n，因此当n趋向无穷时，这个比值会无限趋近于0，说明暴力解法的时间开销增长会远远快于排序解法。
  另外补充特殊场景：只有当两个列表的长度都极小时（比如均小于10），暴力解法的实际运行速度可能和排序解法持平甚至更快，因为排序本身存在常数级的额外开销。但算法题和实际生产场景中的输入规模通常远大于这个阈值，因此第二种解法会被公认为效率更高的方案。

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