c - 下面合并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)) 复杂度。

合并次数保持不变。

Answer 1

虽然合并的数量保持不变，但合并的模式实际上使时间复杂度变差了很多。假设您有一个 merge() 函数到 merge two sorted linked lists在 O(n + m) 时间(其中 n = 第一个列表的大小，m = 第二个列表的大小)和 O(1) 空间中，考虑以下分析，其中我假设每个列表平均有 n 个元素。

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

此时我们必须将 Big-Oh 中的所有加法加起来得到:

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)。

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

---

要回答关于分而治之方法实际上如何产生 O(nk*log(k)) 的其他问题，请考虑合并排序的工作原理。

如果我们有 $n$ 项，归并排序会做 n 的工作，与将 n 项成对合并成一个整体所需的次数一样多列表。这个数字是 log(n)(n 的以 2 为底的对数)，因此它需要的步数与 nlog(n) 成比例(再次意识到我们正在做n 的工作量，因为总是有 n 元素在起作用，log(n) 次)。合并排序必须在合并列表之前将列表分解为单个元素的原因是因为单个单元是我们可以获得的最小的东西，根据定义，它是排序的，我们不需要做任何排序工作。

在我们的例子中，每个列表都已经排序，因此我们可以将每个 k 列表(大小为 ~n)视为按定义排序的元素。没有必要进一步分解排序列表。因为有 k 列表，每个列表都有 n 元素，所以总会有 n*k 元素在起作用。幸运的是，因为每个列表都已经排序，所以我们只需将 k 个“元素”合并在一起，而不是所有 n*k 列表元素。所以相同的逻辑很普遍，因为我们必须将 k 元素/列表合并在一起。由于每个列表需要 O(n) 时间来合并，而不是 O(1) 处理 n*k 单个元素时，它花费的时间与 O(nk*log(k)) 成正比。