跳到主要内容

0. 时间复杂度分析

Array 的时间复杂度​

  • pop()、push() ：在数组尾部操作，时间复杂度为O(1)；
  • forEach()、map()、shift()、unshift()：需要遍历 / 在数组头部操作，时间复杂度为 O(n)；
  • splice()、concat()、find() 方法的时间时间复杂度为O(n)。
    • 最优情况可能为O(1)，如 splice() 在数组尾部操作、find() 第一个元素就符合条件。

不是十分确定的解释：

  • JS 数组是用 HashTable 实现的（上网查资料至少 V8 引擎中是）：
  • 每个元素都有一个对应的 hash 值，用 key / index 经过 hash function 计算出来的值；
  • 在数组中间进行操作：需要将操作元素的 后面元素 hash 值改变；
  • 在数组头部进行操作：增加 / 删除，需要将数组 全部元素 对应的 hash 值改变。

array.splice() 性能测试：

// 测试一：头部添加
const array1 = [];
for (let i = 0; i < 1000000; i++) array1.push(i);

const start1 = new Date().getTime()
for (let i = 0; i < 100000; i++) array1.splice(0, 0, i);
const end1 = new Date().getTime();
console.log(`Add 10^5 numbers to the head of array: ${end1 - start1} ms`);

// 测试二：尾部添加
const array2 = [];
for (let i = 0; i < 1000000; i++) array2.push(i);

const start2 = new Date().getTime()
for (let i = 0; i < 100000; i++) array2.splice(array2.length, 0, i);
const end2 = new Date().getTime();
console.log(`Add 10^5 numbers to the tail of array: ${end2 - start2} ms`);

// Add 10^5 numbers to the head of array: 29162 ms
// Add 10^5 numbers to the tail of array: 11 ms