复杂度分析：合并两个列表的大O复杂度

Question

复杂度分析：合并两个列表的大O复杂度

algorithmmergetime-complexitysingly-linked-list

5

给定两个已排序的单向链表，合并这两个链表。

例子: list1: 1 2 3 5 7 list2: 0 4 6 7 10 ---> 0 1 2 3 4 5 6 7 7 10

尽管解决方案非常简单，并且有多种不同的实现方法，包括使用或不使用递归（请参见此处http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/，查看Method 3），但是，

我在想这种实现的O复杂度会是多少：

如果其中一个列表为空，则返回另一个列表；否则，使用sortedInsert函数将第二个列表的每个节点插入到第一个列表中。该函数基本上会扫描列表直到找到正确的位置。由于两个列表都已经排序，因此无需每次将节点与第一个列表中的所有节点进行比较，可以从最后添加的节点开始比较。

例如：继续前面的示例，如果已添加了4，则下一次比较可以安全地从4开始： list1: 0 1 2 3 4 5 7 list2: 6 7 10 现在将6与4进行比较，而不是与1 2 3 4...进行比较。

如果我将一个元素与第一个列表中的所有元素进行比较，则复杂度为O(m * n)，其中m = #list2，n = #list1，但是考虑到这种“优化”，复杂度会是多少？

实施方案：

// Insert a new node in a sorted list
int sortedInsert(struct ListNode **head, struct ListNode* newNode) {
    int headUpdated = 0;
    struct ListNode *current;

    // The list is empty or the new element has to be added as first element
    if (*head == NULL || (*head)->data >= newNode->data) {
        newNode->next = *head;
        *head = newNode;
        headUpdated = 1;
    }
    else {
        // Locate the node before the point of insertion
        current = *head;
        while (current->next != NULL && current->next->data < newNode->data)
            current = current->next;

        newNode->next = current->next;
        current->next = newNode;
    }

    return headUpdated;
}


struct ListNode *mergeLists(struct ListNode *head1, struct ListNode *head2) {
    if (head1 == NULL)
        return head2;

    if (head2 == NULL)
        return head1;

    // Store the node in the first list where to start the comparisons
    struct ListNode *first = head1;

    while (head2) {
        struct ListNode *head2Next = head2->next;

        printf("Adding %d starting comparison from %d\n", head2->data, first->data);
        if (sortedInsert(&first, head2))
            head1 = first;

        first = head2;
        head2 = head2Next;
    }

    return head1;
}

- ggould75

@H2CO3 不是的，每个比较都会跟随一个插入或者 current = current->next。总共有 n 次插入操作，最多会有 m + n - 1 次节点遍历操作。 - Daniel Fischer

如果你坐下来计算操作的顺序，你会发现你的版本等同于标准的列表合并，只是写法不同。 - Raymond Chen

@DanielFischer 噢，有两个因素，对不起，是我的错误。 - user529758

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Fischer · Accepted Answer

实际上，您这里的合并算法是O(m + n)，而不是O(m * n)。

因为您有一个指向上一个插入节点的指针，并从那个节点开始查找下一个要插入的位置，所以总共需要的操作次数是m和n的和。

current = current->next

sortedInsert 中的操作次数最多为m + n - 1（结果长度减一）。插入操作（重新链接next指针）的次数为n（第二个列表的长度）。每次比较都会进行一次插入操作。

current->next->data < newNode->data

下一步操作要么是插入，要么是 current = current->next，因此比较次数最多为

m + 2*n - 1

假设结果列表从第一个列表中开始有m0个元素，然后从第二个列表中有n1个元素，接着是来自第一个列表的m1个元素，第二个列表中有n2个元素，以此类推，最后从第一个列表中有m_r个元素。其中m0和m_r可以为0，所有其他数字都是严格正数。

第一个n_1块的第一个元素与m_0块的每个元素和m_1块的第一个元素进行比较。该块的所有其他元素与它们在第二个列表中的前一个元素进行比较，以及m_1块的第一个元素（除非r=1且m_1=0，在这种情况下比较较少）。

这使得m_0 + 1 + (n_1 - 1)*2 = m_0 + 2*n_1 - 1次比较（或更少）。

对于后面的n_k块，将第一个元素与n_(k-1)块的最后一个元素、m_(k-1)块的所有元素以及m_k块的第一个元素（如果存在）进行比较。该块的进一步元素都与它们在列表2中的前一个元素进行比较，以及m_k块的第一个元素（如果存在），这样就完成了比较。

 1 + m_(k-1) + 1 + (n_k - 1)*2 = m_(k-1) + 2*n_k

比较（或更少）。由于所有的比较都涉及到第二个列表中至少一个元素，因此总的比较次数最多为

m_0 + 2*n_1 - 1 + m_1 + 2*n_2 + m_2 + 2*n_3 + ... + m_(r-1) + 2*n_r <= m + 2*n - 1.

我们可以通过初始化来稍微改善它。

    struct ListNode *first = head1;

并且移除

    if (!first)
        first = head1;

循环测试。