为什么O(n)复杂度的有序数组平方排序算法实际运行比O(nlogn)的慢

复杂度分析结论 #

你的时间复杂度分析完全正确：

• sortedSquaredArrayNormal 先遍历数组计算平方（O(n)），再调用内置排序（O(nlogn)），整体时间复杂度为O(nlogn)
• sortedSquaredArrayBetter 仅遍历一次数组完成双指针比较和赋值，整体时间复杂度为O(n)

实际运行速度反常的原因 #

你观测到的运行结果是正常的，核心原因有两个：

1. 底层实现语言的性能差异
   Python内置的list.sort()方法是基于C语言实现的Timsort算法，执行效率极高；而你自己编写的双指针逻辑是纯Python代码，所有循环、条件判断、数值运算都在Python字节码层面执行，单步操作的开销比C实现的代码高数十倍甚至上百倍。
2. 渐近复杂度的适用场景
   O(n)优于O(nlogn)是渐近复杂度的结论，只有当输入规模n足够大、大到常数项开销可以忽略的时候，复杂度的优势才会体现出来。你当前测试用的10万、甚至百万级别的输入规模下，C实现的排序的常数项优势仍然能覆盖O(nlogn)的理论复杂度劣势，只有当n达到千万甚至更高量级时，纯Python实现的双指针方法的速度才会反超内置排序的方案。

验证方法 #

你可以尝试将测试数组的长度调整到10^7量级，此时再做测试就能观测到双指针方法的速度优势。如果要在小规模数据下也发挥双指针的性能，可以用C扩展、numpy向量化操作等方式改写双指针逻辑，降低Python循环的开销。

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