下面的代码是我对以下问题的解决方案：
给定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：上面函数的时间复杂度是多少？
O(m+n(，其中m和n是各自数组的大小。
在第一个while循环中，在每次迭代中，i或j都会递增。while循环可以运行的最大次数是(arr.length-1(+(arr2.length-1(，因为任何时间都会超出测试条件。
让我们把i和j的最终状态称为k和l，其中k或l将等于它们各自的上界，另一个将严格小于它们的上界。这意味着当循环运行k+l次时
循环之后，您将执行另外两个互斥的while循环，每个循环从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)
所以总数是
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(
此算法的时间复杂度将为O(arr1.length+arr2.length(，因为实际上我们只迭代两个数组一次。
好吧，因为它只有2个数组，算法是直接的，并且你在所有索引上对arr1和arr2进行迭代，最坏的情况实际上是O(n+m(，其中n=arr1.length和m=arr2.length。但请注意，这不仅是最差的情况，而且是所需的确切时间，这意味着它也是θ(m+n(