以下是合并k个链表的时间复杂度

Question

http://www.geeksforgeeks.org/merge-k-sorted-linked-lists/

参考链接： 请解释分治策略如何实现O(nk Log k)的复杂度。 此外，我以稍微不同的方式编写了相同的代码。唯一的区别在于合并模式。我将第一个2个链表结果合并，然后将它们的结果与其他链表合并。

这样的复杂度是多少？

Node * mergek(){
    int n;
    puts("Enter number of linked list you want to enter");
    scanf("%d",&n);
    Node ** arr=malloc(sizeof(Node *)*n);
    int i=0;
    for(i=0;i<n;i++){
        arr[i] = takeInput();
    }
    for(i=0;i<n;i++){
        print(arr[i]);
    }
    Node * temp=NULL;
    for(i=0;i<n;i++){
        if(i==0){
            temp=merge(arr[i],arr[i+1]);
            i=i+1;
        }   
        else{
            temp=merge(arr[i],temp);
        }   
    }
    return temp;    
}

我想知道这个问题是否具有相同的复杂度，即O(nklog(k))复杂度。

合并次数保持不变。

- Anonymous

---

你的代码实际上并没有执行合并操作，因为你没有展示你的 merge() 代码。我们只知道它是 O(n) * O(merge)。 - Mark Lakata

Answer 1

尽管合并的数量保持不变，但实际上合并的模式使时间复杂度变得更糟。假设您有一个merge()函数，在O(n + m)时间（其中n =第一个列表的大小，m =第二个列表的大小）和O(1)空间中 合并两个排序的链接列表，请考虑以下分析，其中我认为每个列表平均有n个元素。

• 第一次合并将是O(n + n)，因为我们正在合并两个n大小的列表
• 第二次合并将是O(2n + n)，因为我们现在正在将一个n大小的列表与我们的2n大小的列表合并
• 第三次合并将是O(3n + n)......等等。

此时，我们必须加起来大O符号中的所有加法，得到：

O(2n + 3n + 4n + 5n + ... + kn)

所有这些n项的总和本质上是n*(k(k+1))/2，因为(k(k+1))/2是前k个数字的总和。通过将常数因子和低阶项从(k(k+1))/2中取出，我们可以看到O((k(k+1))/2) = O(k^2)，从而给出算法O(n*k^2)的时间复杂度。

我写了一篇关于这个问题的小文章，并进一步分析了复杂度差异的程度。你应该在这里查看它。

---

回答你关于分治法如何实际上产生O(nk*log(k))的问题，想一想归并排序是如何工作的。

如果我们有n个项目，归并排序会做n次工作，直到将n个项目成对合并在一起形成一个完整的列表。这个数字是log(n)（以2为底数的对数），因此它需要进行与nlog(n)成比例的步骤（再次意识到我们正在做n量级的工作，因为总是有n个元素在发挥作用，而且要做log(n)次）。归并排序必须将列表拆分为单个元素，然后再将它们合并在一起，原因是单个单位是我们可以得到的最小的东西，根据定义，它已经排序好了，而不需要我们做任何排序工作。

在我们的情况下，每个列表都已经排序，因此我们可以将每个大小为~n的k个列表视为按定义排序的元素。没有必要进一步拆分已排序的列表。由于有k个列表，每个列表都有n个元素，因此总共会有n*k个元素参与。幸运的是，由于每个列表已经排序，我们只需要合并k个“元素”，而不是所有n*k个列表元素。因此，相同的逻辑仍然适用，即我们必须合并k个元素/列表。由于每个列表合并需要O(n)时间，而不是处理n*k个单独元素时的O(1)时间，因此它需要与O(nk*log(k))成比例的时间。

- Dominic Farolino