对旋转数组的复杂度分析

Question

一开始我对数组slice和concat的复杂度存在误解,我认为他们都是O(n)的时间复杂度,因为相当于是把原数组(某个部分或者全部)数据一个一个加到新数组上面,老师讲他们都是O(1)的,我很好奇.
所以我按照自己的想法把slice和concat实现了一下,代码如下:

function mySlice(arr: number[], start: number, end: number) {
    const newArr = [];

    for (let i = start; i <= end; ++i) {
        newArr.push(arr[i]);
    }

    return newArr;
}

function myConcat(arr1: number[], arr2: number[]) {
    const newArr = [];

    for (let i = 0; i < arr1.length; i++) {
        const element = arr1[i];
        newArr.push(element);
    }

    for (let i = 0; i < arr2.length; i++) {
        const element = arr2[i];
        newArr.push(element);
    }

    return newArr;
}

这个实现的复杂度很明显是O(n)的嘛. 然后我用自己写的这两个API替换掉原数组的API.

export function rotate3(arr: number[], k: number): number[] {
    const length = arr.length;
    const step = Math.abs(k % length);
    if (!step || !length) {
        return arr;
    }

    const part1 = mySlice(arr, length - step, length - 1);
    const part2 = mySlice(arr, 0, length - step - 1);
    const part3 = myConcat(part1, part2);

    return part3;
}

这段代码也是通过了单元测试的,然后进行性能测试的时候.它的用时是6ms,而用了原生API的算法的用时是0.5ms,显然不是一个数量级,所以原生的复杂度肯定不是O(n),应该是O(1),
所以,为什么原生的slice和concat复杂度是O(1)的,可以解释一下吗?

Answer 1

双越 2022-05-01 10:02:46

slice 和 concat 都是底层代码实现的，底层代码可以直接操作内存，而 JS 不能操作内存。

如果你会 C 或者 C++ ，就可以通过操作内存来实现 O(1) 的复杂度

• 提问者 weixin_宝慕林8180759 #1

  是不是可以这样理解：concat和slice都是直接把需要操作那部分一次性移动到新数组里面，所以相当于只做了一次操作，而我的实现，因为不能做到这种高级的做法，就是你说的js没有办法操作内存，所以就只能是大o n的时间复杂度

• 提问者 weixin_宝慕林8180759 #2

  然后我又有新的疑问了，关于unshift和shift的，这两个API速度慢，是On，但是如果我这样实现unshift：
  function myUnshift(arr1, num){
  return [num].concat(arr1)
  }
  这样实现时间复杂度是O1了吗？虽然空间复杂度是On了，如果前端是重时间，轻空间的，那我这个实现岂不是比原生方法更好？

• 双越 回复 提问者 weixin_宝慕林8180759 #3

  但 unshift 是在现有数组修改的，不能新建一个数组，这是前提。

点开查看后面1条评论