如何考虑合并k排序链表的复杂性？

Question

我试图更好地理解大O表示法，以便能够更清楚地解释它，因此，我需要对下面给出的关于问题的分析提供一些反馈:将k排序的链接列表合并为一个。

索赔#1:

var merge2Lists = function(list1, list2) {
        if (!list1) {
            return list2;
        }
        if (!list2) {
            return list1;
        }

        if (list1.val <= list2.val) {
            list1.next = merge2Lists(list1.next, list2);
            return list1;
        }
        else {
            list2.next = merge2Lists(list2.next, list1);
            return list2;
        }
    };

下面给出的两个解决方案都使用了上面提到的merge2Lists。这个函数的复杂性应该是O (n1 + n2)，其中n1和n2分别是list1和list2中的元素数。或者我们可以说，在最坏的情况下，这两个列表都有相同数量的元素，我们必须至少检查它们一次，所以我们可以称之为O(n)。

索赔#2

// Solution: 1
var mergeKLists = function(lists) {
    let len = lists.length, interval = 1, i;
    while (interval < len) {
        for (i = 0; i < len; i += interval*2) {
            lists[i] = merge2Lists(lists[i], lists[i+interval])
        }  
        interval *= 2;
    }
    return (len > 0) ? lists[0]: lists;
}

假设我的输入中有10个列表要合并。上面的解决方案采用了这10个列表，在while循环的第一次迭代中，它合并了10/2 =5对。在下一次迭代中，它合并10/4 =3对。接下来，它将10/8 =2对合并，最后在list 0中得到最终排序列表。

由于要合并的对的数量在每一步被减半，它的时间复杂度应该是log(k)，其中k是输入中的列表数。另一种描述它的方法可以是，如果我们将输入大小加倍(即从10增加到20)，那么增加的操作数不会增加一倍--这意味着它绝对不是O(n)。操作的数量可能只增加1，这意味着它应该是log(k)。

连同声明1，总复杂性应该变成：O (n * log k)。不过，我不知道怎么解释清楚。

空间复杂性应该是O(1)，因为我们的内存在输入大小方面保持不变。

索赔#3

// Solution: 2
var mergeKLists = function(lists) {
    let len = lists.length;
    if (!len) return lists;

    while (lists.length > 1) {
        lists.push(merge2Lists(lists[0], lists[1]));
        lists.shift();
        lists.shift();
    }
    return lists[0];
};

在这里，mergeKLists在while循环的每一次迭代中只合并1对。如果我们有10个列表，在第一次迭代之后，我们只会合并1对。在第二次迭代中，我们将合并另一对，等等。看来我们总共做了10次手术。因此它的复杂性应该是O (k)，其中k是输入中的列表数。

如果将输入的大小从10增加到20，则增加的运算数将是10，这与我们推导出的O(k)的复杂性是一致的。

此外，我们使用shift()函数2次从数组中丢弃不需要的列表。shift()本身的复杂性是O (m)，其中m是数组移位的元素数。在最坏的情况下，shift将不得不将m个元素向左移动。因此，该解决方案的时间复杂性将成为O (k + m)。

连同声明#1，总复杂性应该变成：O (n * (k+m))。

空间复杂度应该是O(1)，因为对于每个被推入数组的新元素，我们从数组中丢弃元素，即获得的空间相对于输入没有增加。

1. 这些说法正确吗？如果没有，你能帮我更好地理解吗？
2. 是否有一个更清楚的方式来解释上面的索赔？
3. 我注意到，至少在LeetCode上，对于同一组测试用例，解决方案2的运行速度比解决方案1快30 of。它是否只是一个LeetCode错误或网络延迟，因为它的日志(K)时间复杂性，我期望解决方案1运行得更快。

Answer 1

索赔1

Claim1看起来是正确的(但是那里的代码可以简化，将if (list2.val < list1.val)替换为“there”)。我还会在代码中对您要加入列表的某个地方进行评论--更改传入的参数。

索赔2：

这部分我认为你是对的，但解释得很糟糕。当你说"ts时间复杂度应该是log(k)，其中k是输入中的列表数“，我非常困惑。您的意思是遍历该循环日志(K)次数，但是每个循环(内循环)的时间(从上面)是有界的O(N)，其中N是所有列表的长度之和(因为您不知道要对哪个列表进行操作)。

而且-我从来没见过你在哪里清楚地定义了'n‘，但我想，你说的n是和n(子-i)。

索赔3：

在这里引入一个新的变量“m”不是个好主意。它以'n‘为界，每次在循环中变化(所以不是问题的函数，而是解的函数)，所以它不是一个很好的分析对象。

你看完k次是对的。如果我们继续假设'n‘是所有列表的长度之和，那么n就是要合并的两个列表参数的长度的上限。

如果我们假设您的“列表”是使用一个向量来实现的(如果它也是一个链接列表，它不需要也会更好地执行)，那么总的复杂性就变成了

O (K*k) (对于长度为k倍的数组的移位)加上k合并的O (k * N)。

或-O (k*(k+n))

顺便说一句--如果你用链表来表示“列表”--它就变成了O(k*n) --因为链表操作--推到前面，从前面弹出--都是O(1)。