自定义mergeArr有序数组合并函数的时间复杂度咨询

你的判断是对的，这个函数的时间复杂度确实是O(n²)，核心原因就是你提到的shift()方法：

• JavaScript的数组是基于动态数组实现的，shift()删除第一个元素后，后面所有元素都要向前挪动一位，这个操作的时间复杂度是O(k)（k是当前数组的长度）。
• 整个while循环会执行m+n次（m、n分别是两个输入数组的长度，记总长度为n）。最差情况下，比如其中一个数组的所有元素都比另一个小，那就要对这个数组执行m次shift()，每次挪动的元素数量从m递减到1，总操作次数是m+(m-1)+...+1 = m(m+1)/2，加上另一个数组的操作，整体时间复杂度就是O(n²)级别。

另外还有两个需要注意的点：

1. 逻辑漏洞：你用!arr2[0]或!arr1[0]来判断数组是否遍历完是有问题的——如果数组里包含0、空字符串这类假值，会误判数组已经空了，导致元素漏加。正确的判断应该是检查数组的剩余长度，或者用指针判断是否越界。

2. 优化方向：可以用双指针法把时间复杂度降到O(n)，完全避免shift()带来的数组挪动开销：
   用两个指针分别指向两个数组的起始位置，每次比较指针指向的元素，把较小的加入结果数组，然后移动对应指针；当其中一个数组遍历完后，直接把另一个数组的剩余元素追加到结果里即可。每个元素只会被访问一次，没有额外的挪动成本。

优化后的代码示例：

const mergeArr = (arr1, arr2) => {
    let mergedArr = [];
    let i = 0, j = 0;
    const len1 = arr1.length, len2 = arr2.length;
    
    while (i < len1 && j < len2) {
        if (arr1[i] <= arr2[j]) {
            mergedArr.push(arr1[i]);
            i++;
        } else {
            mergedArr.push(arr2[j]);
            j++;
        }
    }
    
    // 追加剩余元素
    while (i < len1) mergedArr.push(arr1[i++]);
    while (j < len2) mergedArr.push(arr2[j++]);
    
    return mergedArr;
};

内容的提问来源于stack exchange，提问作者Abram Boutros