同时查找数组中最大和最小元素的最优时间复杂度是多少？

先纠正你对时间复杂度的认知错误 #

• 大O记号表征的是算法随数据规模增长的渐近趋势，计算时会忽略所有常数系数，你提到的O(2N)本质就是线性复杂度O(N)，和O(N)属于同一复杂度等级，不存在量级差异。
• 你推导的2N > N*log(N)完全不符合实际增长规律：算法分析中log默认以2为底计算，当N=4时，2N=8、NlogN=8，两者数值相等；只要N>4，NlogN的增长速度就会超过2N：N=8时2N=16、NlogN=24；N=1024时2N=2048、NlogN=10240，数据量越大，两者的性能差距会越明显。
• 别忽略算法的常数项开销：就算不看渐近复杂度，快排、归并排序的单步操作成本远高于简单遍历——排序过程要做大量元素交换、递归/辅助空间维护、分支跳转，实际执行的CPU指令数是线性遍历的十几倍到几十倍，哪怕是N很小的场景，排序也不会比遍历更快。另外快排存在最坏O(N²)的时间复杂度，遇到极端数据时性能会直接暴跌。

找最值的最优实现甚至不需要两次遍历 #

你完全可以用单次遍历同时拿到最大值和最小值，保持O(1)额外空间、O(N)时间复杂度，比两次遍历的效率还高：

• 边界处理：如果数组长度为1，直接返回该元素同时作为最大、最小值
• 初始化：比较数组前两个元素，较大值设为初始max，较小值设为初始min
• 遍历：从第三个元素开始逐个访问，每拿到一个元素先和当前max比较，更大就更新max；再和当前min比较，更小就更新min
• 遍历结束后直接返回max和min即可
  这个方案的总比较次数最多为3*floor(N/2)，比两次遍历需要的2N-2次比较少了近三分之一，是目前无序数组找全局最大最小值的最优通用实现。

什么场景适合用排序取最值的方案？ #

只有当你除了获取最大最小值之外，后续逻辑还需要用到有序数组时，提前排序才是划算的选择。如果仅仅是为了拿两个最值就对整个数组排序，属于完全不必要的性能浪费。

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