最坏的情况应该是O(n)（将所有n-1元素复制到新数组）。

链接列表将O(1)用于单个删除。

对于那些感兴趣的人，我已经制作了这个懒惰的基准测试。（请不要在 Windows XP/Vista 上运行）。但是，正如您从中可以看到的，它看起来相当稳定（即O(1)），所以谁知道他们在幕后做了什么来使这种疯狂快速。请注意，无论如何，实际splice速度非常快。

直接在 V8 shell 中重新运行扩展基准测试，提示O(n). 请注意，您需要巨大的数组大小才能获得可能影响您的代码的运行时。这应该是预期的，就像您查看它用于memmove创建新数组的 V8 代码一样。

我接受了评论中的建议，并编写了一个简单的测试，对大小为 3,000 的数据集数组进行时间拼接，每个数组包含 3,000 个项目。该测试将简单地拼接

• 第一个数组中的第一项
• 第二个数组中的第二个项目
• 第三个数组中的第三个项目
• ...
• 第 3000 个数组中的第 3000 个项目

我预先构建了数组以保持简单。

最奇怪的是，当你增加数据集的大小时，拼接过程甚至需要超过 1ms 的次数会线性增长。

我在我的机器上测试了 300,000 的数据集（但 SO 片段往往会在 3,000 之后崩溃）。

我还注意到，splice()对于给定的数据集（在我的情况下为 30,000），花费超过 1 毫秒的s数量是随机的。所以我运行了 1000 次测试并绘制了结果的数量，它看起来像一个标准分布；让我相信随机性只是由调度程序中断引起的。

这违背了我的假设和@Ivan的猜测，即splice()从数组的开头 ing 将具有O(n)时间复杂度

let data = []
const results = []
const dataSet = 3000

function spliceIt(i) {
  data[i].splice(i, 1)
}

function test() {
  for (let i=0; i < dataSet; i++) {
    let start = Date.now()
    spliceIt(i); 
    let end = Date.now()
    results.push(end - start)
  }
}

function setup() {
  data = (new Array(dataSet)).fill().map(arr => new Array(dataSet).fill().map(el => 0))
}

setup()
test()
// console.log("data before test", data)
// console.log("data after test", data)
// console.log("all results: ", results)
console.log("results that took more than 1ms: ", results.filter(r => r >= 1))

你好！

我自己做了一个实验，想分享我的发现。实验很简单，我们在一个大小为 n 的数组上运行 100 次拼接操作，并计算每个拼接函数花费的平均时间。然后我们改变了 n 的大小，以检查它的行为。

这张图总结了我们对大数字的发现：

对于大数字，它似乎是线性的。

我们还检查了“小”数字（它们仍然很大但没有那么大）：

在这种情况下，它似乎是恒定的。

如果我必须决定一个选项，我会说它是 O(n)，因为这就是它在处理大数时的表现。但请记住，线性行为仅适用于非常大的数字。

但是，很难给出明确的答案，因为 javascript 中的数组实现在很大程度上取决于数组的声明和操作方式。

我推荐这个 stackoverflow 讨论和这个 quora 讨论来了解数组是如何工作的。

我在节点 v10.15.3 中运行它，使用的代码如下：

const f = async () => {
  const n = 80000000;
  const tries = 100;
  const array = [];
  for (let i = 0; i < n; i++) { // build initial array
    array.push(i);
  }
  
  let sum = 0;
  for (let i = 0; i < tries; i++) {
    const index = Math.floor(Math.random() * (n));
    const start = new Date();
    array.splice(index, 1); // UNCOMMENT FOR OPTION A
    // array.splice(index, 0, -1); // UNCOMMENT FOR OPTION B
    const time = new Date().getTime() - start.getTime();
    sum += time;
    array.push(-2); // UNCOMMENT FOR OPTION A, to keep it of size n
    // array.pop(); // UNCOMMENT FOR OPTION B, to keep it of size n

  }
  console.log('for an array of size', n, 'the average time of', tries, 'splices was:', sum / tries);
 };
f();

注意代码有一个选项B，我们对三参数拼接函数做了同样的实验来插入一个元素。它的工作原理类似。