将两个有序数组合并成一个更大的有序数组的时间复杂度是多少？

Question

下面的代码是我对以下问题的解决方案：

给定 2 个按升序排序的整数数组，编写一个函数，将这两个数组合并为一个更大的排序数组。例如，给定数组 arr1 = [[0， 3， 4， 31] 和 arr2 = [4， 6， 30]，求解函数应返回数组 [0， 3， 4， 4， 6， 30， 31]。

我的解决方案：

function mergeSortedArrays(arr1, arr2) {
    // Check input
    if (arr1.length === 0 && arr2.length === 0) {
        return arr1;
    } else if (arr1.length === 0) {
        return arr2;
    } else if (arr2.length === 0) {
        return arr1;
    }

    // Initialize variables
    let i = 0, j = 0;
    const mergedArray = [];

    // Loop through & compare
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] <= arr2[j]) {
            mergedArray.push(arr1[i]);
            i++;
        } else {
            mergedArray.push(arr2[j]);
            j++;
        }
    }

    if (j < arr2.length) {
        while (j < arr2.length) {
            mergedArray.push(arr2[j]);
            j++;
        }
    } else if (i < arr1.length) {
        while (i < arr1.length) {
            mergedArray.push(arr1[i]);
            i++;
        }
    }

    return mergedArray; // O(1)
}

上面的解决方案运行良好。然而，我在分析我所使用的算法的最坏情况时间复杂度时遇到了一些麻烦。乍一看，它似乎具有线性时间复杂度O(n ),但是进一步观察，比较两个数组之间的元素的第一个循环中的迭代次数并不仅仅受两个数组中任一个的长度限制。更具体地说，它似乎与每个数组的上限和下限有关。

TLDR:上面这个函数的时间复杂度是多少？

Answer 1

该算法的时间复杂度将为O（arr1.length arr2.length），因为实际上我们正在迭代两个数组一次。

Answer 2

在第一个while循环中，在每次迭代中，都会递增i或j。while循环可以运行的最大次数为（arr.length-1）（arr.length-1），因为任何更多的循环都将超出测试条件。

让我们将I和j的最终状态称为k和l，其中k或l将等于它们各自的上限，而另一个将严格小于它们的上限。这意味着while循环已经运行了k ^ 1次

在循环之后，您将执行另外两个互斥的同时循环，每个循环都从k/l开始，直到达到上限。这意味着这两个循环将运行（arr.length-k）或（arr2.length-l）次。

所以你运行的最终结果是第一个while循环：（k l）第二组循环：

   if k != arr.length (implies l == arr2.length): (arr.length - k) 
   if l != arr2.length (implies k == arr.length): (arr2.length - l)

所以total是

  if k != arr.length: (k + l) + (arr.length - k) = l + arr.length = arr2.length + arr.length
  if l != arr2.length: (k + l) + (arr2.length - l) = k + arr2.length = arr.length + arr2.length

两者都导致总执行计数为 arr.length arr2.length，因此复杂度为 O（m n）

Answer 3

o(m ^ n ),其中m和n是各自阵列的大小。