谷歌浏览器中的array.splice()的时间复杂度是多少？

Question

如果我使用splice()方法从一个数组中删除一个元素，就像这样：

arr.splice(i, 1);

由于它将i后面的所有元素都移动了一次，所以在最坏情况下，这会是O(n)吗？或者说，在链表的某些神奇操作下，时间是常数？

- Ivan

---

移位不是 O(n^2)，而是 O(n) 对吧？ - David Tang

只有当实现是重新分配动态数组而不是链表时才成立。 - Delan Azabani

为什么不简单地运行一个快速测试并绘制函数运行时间随 n 增加的变化曲线呢？ - Ed S.

O(N) 是空间复杂度还是时间复杂度？ - kikkpunk

@EdS。我应该如何运行快速测试并绘制随着n的增加所需的时间？我以前从未这样做过，你有什么建议吗？比如说我应该使用什么工具？脚本应该是什么样子的？ - ilikechocolate

Answer 1

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

对于单个删除，链表应该是O(1)。

对于那些感兴趣的人，我做了这个懒散制作的基准测试。（请勿在Windows XP/Vista上运行）。 从这里可以看出它看起来相当稳定（即O(1)），所以谁知道他们在幕后做了什么使它变得非常快。请注意，无论如何，实际的splice非常快。

在V8 shell中重新运行扩展的基准测试，表明为O(n)。请注意，您需要巨大的数组大小才能获得可能会影响您的代码的运行时。这是预期的，因为如果您查看V8代码，它使用memmove创建新数组。

- Andrew Marshall

---

将来进行基准测试时，您可能希望使用jsperf。它比编写jsFiddle更容易，并且（我认为）更准确。 - Matt Ball

即使只有一个列表，在任意位置进行插入/删除操作的时间复杂度也是线性的。因为您必须首先迭代到该位置，这需要您遵循所有链接。除非您仅在开头附近进行切片，否则它会占据复杂度的主导地位。 - leemes

Answer 2

¡嗨！

我自己做了一个实验，想分享一下我的发现。实验非常简单，我们对大小为n的数组运行100个切片操作，并计算每个切片函数所花费的平均时间。然后我们改变了n的大小，以检查其表现如何。

以下图表总结了我们针对大数字的发现：

对于大数字，它似乎呈线性增长。

我们还使用“小”数字进行了检查（尽管它们仍然相当大）：

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

如果让我选择一个选项，我会说它是O(n)，因为对于大数字来说，它的行为就是这样。请记住，线性行为只显示为非常大的数字。

然而，要给出一个明确的答案很难，因为JavaScript中的数组实现非常依赖于数组的声明和操作方式。

我建议阅读这个stackoverflow讨论和这个quora讨论，以了解数组的工作原理。

我在node 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，我们对三个参数的splice函数进行了相同的实验以插入一个元素。它的工作方式类似。

- Antonio

Answer 3

测试

我采纳了评论中的建议，并编写了一个简单的测试，用于计时对一个大小为3,000的数据集数组进行分片，其中每个数组中包含3,000个条目。测试只需将：

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

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

结果：

最奇怪的事情是，在增加数据集大小时，splice过程的执行时间超过1ms的次数呈线性增长趋势。

我甚至在我的机器上测试了一个大小为300,000的数据集（但SO代码段在3,000之后容易崩溃）。

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

这与我的假设和@Ivan的猜测相反，即从数组开头进行splice()将具有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))

- Artur Grigio

---

我希望有人能够参与讨论，也许我的测试有误，或者我的数据集太小了。splice()如何可能具有O(1)时间复杂度？ - Artur Grigio

我的想法是Javascript数组在底层存储为链表，这是我认为它们能够使任意对象存储在数组中的唯一方式。这意味着splice相当于删除已知内存位置上的对象，并简单地设置2个指针。但这可能取决于解释器的实现。耶，Javascript :) - Evan Kleiner