array.splice(...array.splice()) 的时间复杂度是多少

Question

我正在解决旋转数组的 leetcode 问题之一。我通过使用两个 for 循环解决了 O(N)，但我的运行时间比这个解决方案低。

我的解决方案：运行时间 80ms

var rotate = function(nums, k) {

    let a = Array.from({length:nums.length})

    for (let i = 0; i < nums.length; i++) {
      a[(i + k) % nums.length] = nums[i];
    }
    for (let i = 0; i < nums.length; i++) {
      nums[i] = a[i];
    }


};

其他解决方案：运行时 52 毫秒

var rotate = function(nums, k) {
      return nums.splice(0,0,...nums.splice(nums.length - k))
};

这怎么可能。据我所知，拼接是 O(N)，在此解决方案中，拼接也再次用于拼接。所以这个解决方案应该是 O(N2) 而我的解决方案应该比这个更快？

Answer 1

Array#splice is O(n) because it can shift up to each array element per call. See: What's the time complexity of array.splice in Google Chrome?

在确定一个算法的time complexity时，只要每个O(n)次操作是串联的，并且O(n)次操作的次数是一个常数因子（这里就是这种情况），它仍然是 O(n)。 O(n²) 是嵌套循环的结果；也就是说，对于每个 n 我们执行另一个 O(n) 操作。

此代码仅使用对 Array#splice 的两次连续调用以及 O(n) 的传播，总共 O(3n) 相当于 O(n)。

"My runtime was slower" -- 时间复杂度和运行时间是完全不同的东西。大部分运行时间取决于实施细节、大 O 忽略的固定开销费用（常数因素）、LC 的测试用例有多大、测试用例的组成、LC 的测试用例测量的不准确性等。使用你自己的基准控制非常大的随机输入更加确定。两个 O(n) 代码很少表现出相同的性能特征——时间复杂度只与算法的增长率有关。

对于这个特殊的比较，请记住内置函数是高度优化的。我假设它在 NodeJS (V8) 中运行，那么多 builtins are written in C++ (or Torque)（并且 V8 在这方面并不是唯一的）。

在较低级别本机实现内置意味着内存可能 compact and regular so cache accesses benefit from locality, less pointer chasing, opportunities for stack allocation，等等。for 高级代码中的循环更难优化。它们涉及索引变量、执行比较、分支等等，所有这些都需要以一种可能不是最佳的方式有效地转换为字节码。在 JS 中内置实现的情况下，设计人员做了大量工作以使其尽可能高效。

在 Array#splice 的情况下，它是 written in Torque which is translated to efficient assembly。

在您的代码中，let a = Array.from({length:nums.length})。产生两个对象的分配开销。

简而言之：公平地进行基准测试，不要将复杂性和速度混为一谈，并尽可能使用内置函数（使用探查器来确定何时不使用的罕见情况）。

array.splice(...array.splice()) 的时间复杂度是多少

what is the time complexity of array.splice(...array.splice())

javascript

arrays

splice