问答

当前位置
  • 首页
  • 问答
  • 104. Merge K Sorted Lists - merge 2x2解法的时间复杂度

104. Merge K Sorted Lists - merge 2x2解法的时间复杂度

  • Ta: 刘助教

看了好几个问答平台上的相关提问都没找到确切的答案,所以就自己提问了。
以下是九章给出的三个解法的时空复杂度的总结:
1.divide & conquer: 时:O(nklogk) 空:O(1)
2.heap: 时:O(nklogk) 空:O(k)
3.merge 2x2: 时:O(nklogk) ?空:O(1)
k为链表数量
n为每个链表里结点的数量(如果是一样的),或者平均结点数量(如果不一样)

两个问题,第一个问题是,第三种解法的时间复杂度是不是O(nklogk)?因为我看到有其他的意见,比如https://www.jiuzhang.com/qa/3908/ 和 https://www.jiuzhang.com/qa/2544/ 。

我觉得是O(nklogk)是因为首先while循环会运行logk次,代表logk轮合并;每一轮合并都会运行for循环k/2次,因为每次会处理合并两个链表,k是当前for循环里待合并链表的数量,所以是O(k);然后每次for循环合并都要遍历两个链表,即2n个元素,所以是O(n);所以随后乘起来得出O(nklogk)。对吗?

第二个问题是,我写了一下另外一种比较慢的解法。就是链表1 和 2 先合并,再和3合并,再和4合并,这种时间复杂度是不是T(k)=n+2n+3n+...+kn=O(nk^2)?然后空间复杂度是O(1)。

```
public ListNode mergeKLists(List lists) {
if (lists == null || lists.isEmpty()) {
return null;
}
ListNode result = null;
for (int i = 0; i < lists.size(); i++) {
result = mergeTwoLists(lists.get(i), result);
}
return result;
}

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            cur.next = l1; //here, dummy.next is updated to be l1 which is head to be returned
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next; //head won't be changed because cur is not pointing to head anymore since this line
    }
    if (l1 == null) {
        cur.next = l2;
    }
    if (l2 == null) {
        cur.next = l1;
    }
    return dummy.next;
}

1 个回复

2019-09-13 carry

因为每次merge操作中,时间复杂度都只与两个数组的元素数量之和有关O(n + m)。
鉴于此,对于链表1 和 2 先合并,再和3合并,再和4合并。。。,时间复杂度就是T(k)=n+2n+3n+...+kn=O(nk^2)。
对于merge 2 x 2中,两个两个合并,然后在前一次合并的结果中,两个两个合并。那么每一轮合并的时间复杂度还是O(nk),轮数T = log k。所以最后的时间复杂度T(k)=O(nk log k)。

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1