同时查找数组最大值与最小值的时间复杂度、最优方案及遍历复用问题问询

咱们来一步步拆解你的问题，先逐个分析三个方案的时间复杂度，再聊最优选择和后续的遍历复用问题～

一、三个方案的时间复杂度分析 #

• Option 1：你说的没错，这个方案确实是**O(n)**的时间复杂度。Math.max(...a)和Math.min(...a)内部都会完整遍历一次数组，所以总共是2次线性遍历——虽然常数系数是2，但渐近复杂度还是O(n)，不过实际运行时两次遍历会带来额外的内存和操作开销。
• Option 2：这个方案的时间复杂度同样是O(n)，但效率比Option 1更高。它只需要遍历数组一次，每个元素做两次比较（分别更新max和min），总共n次迭代，没有额外的遍历开销，实际操作量是Option 1的一半。
• Option 3：这个方案的时间复杂度是O(n log n)。JavaScript里的sort方法通常采用Timsort这类高效排序算法，其时间复杂度是O(n log n)，这比前两个线性复杂度的方案慢得多——排序的开销远大于单纯找最大最小值，哪怕后续取首尾是O(1)操作，整体性能也差很多。

二、哪个方案最好？有没有更优的方法？ #

在这三个方案里，Option 2是最优选择，因为它只需要一次线性遍历，时间复杂度最低且实际运行效率最高。

当然还有进一步优化的空间：可以采用「成对比较」的策略，每次从数组里取两个元素，先比较这两个元素的大小，然后把较大的和当前max比较，较小的和当前min比较。这样每两个元素只需要3次比较（而原来的每个元素两次，两个就是4次），总比较次数降到3n/2次，比Option 2的2n次更少。举个例子：

let a = [...Array(1000000)].map(() => Math.round(1000000 * Math.random()));
let max = Number.MIN_SAFE_INTEGER, min = Number.MAX_SAFE_INTEGER;
const len = a.length;
let i = 0;
// 处理成对的元素
if (len % 2 === 0) {
  if (a[0] > a[1]) {
    max = a[0];
    min = a[1];
  } else {
    max = a[1];
    min = a[0];
  }
  i = 2;
} else {
  max = min = a[0];
  i = 1;
}
for (; i < len; i += 2) {
  const first = a[i];
  const second = a[i + 1];
  if (first > second) {
    if (first > max) max = first;
    if (second < min) min = second;
  } else {
    if (second > max) max = second;
    if (first < min) min = first;
  }
}

不过这个优化的渐近复杂度还是O(n)，只是减少了实际的比较次数，在数组极大的时候能体现出性能优势。

三、遍历复用的问题：如果已经要做其他遍历操作，是否合并处理？ #

绝对应该合并处理！比如你需要把每个元素乘以10，同时找最大最小值，完全可以在同一次forEach（或者for循环）里完成所有操作：

let a = [...Array(1000000)].map(() => Math.round(1000000 * Math.random()));
let max = Number.MIN_SAFE_INTEGER, min = Number.MAX_SAFE_INTEGER;
const transformed = [];
a.forEach(v => {
  const newValue = v * 10;
  transformed.push(newValue);
  max = Math.max(max, newValue);
  min = Math.min(min, newValue);
});

这样只需要一次遍历，避免了额外的两次遍历（一次处理乘10，一次找最大最小）。虽然时间复杂度还是O(n)，但实际运行时减少了数组的访问次数，内存和CPU开销都会更低，尤其是数组规模很大的时候，这种合并操作的优势会非常明显。

备注：内容来源于stack exchange，提问作者Rewind