同时最大/最小搜索的操作顺序

Question

以下同时求数组最大值/最小值的方法的阶数 O(n) 是多少？哪个最好？还有更好的办法吗？

如果我出于其他原因必须预先循环数组（例如，将每个元素乘以 10），那么最好使用选项 2 并在将同一 forEach 中的每个元素相乘的同时找到最大值/最小值？

选项 1：

// This is surely 2n
let a = [...Array(1000000)].map(() => Math.round(1000000 * Math.random()));
let max = Math.max(...a);
let min = Math.min(...a);

选项2：

// What order is this?
let a = [...Array(1000000)].map(() => Math.round(1000000 * Math.random()));
let max = Number.MIN_SAFE_INTEGER, min = Number.MAX_SAFE_INTEGER;
a.forEach(v => {max = Math.max(max, v); min = Math.min(min, v);});

选项 3：

// Is this 3n/2?
let a = [...Array(1000000)].map(() => Math.round(1000000 * Math.random()));
a.sort((x,y) => x - y);
let max = a[a.length - 1];
let min = a[0];

Answer 1

大 O 表示法不包括系数，因为它只涉及系数的缩放方式。 O(n) 的行为与 n 随着 O(2n) 的增加而增加相同。

选项 1 是 O(n) 选项 2 是 O(n)

选项 3 取决于 JavaScript 引擎对

Array.prototype.sort

的实现，但肯定高于保证的 O(n)。一般为 O(nlogn) 平均值。 查看此答案了解更多详情