合并两个排序的链表——理解为什么它是 O(1) vs. O(N) space 复杂度

Question

我见过的迭代合并两个排序链表的大多数实现如下。

Create a dummy node. Point it to the linked list head that has the smaller value. Move that head to its next node. Move dummy pointer to its next node. Repeat.

我不明白为什么这个过程 space 复杂度为 O(1) 而不是 O(N)？当我们将虚拟节点指向两个链表中的现有节点时，我们实际上是在创建一个新的链表——一个将两个现有列表交织在一起的链表。因此，这不是仍然需要 O(N) space 吗？虚拟节点是它自己的链表的头部，它与原来的两个链表是分开的，即使它使用相同的节点...

Answer 1

你完全正确，你将需要 Θ(n) 存储 space 来保存合并两个总长度为 n 的列表的结果。但是，在函数启动运行之前，有多少存储空间 space 已经存在，又有多少存储空间 space 是新的？你已经有两个列表，总共有 n 个元素，所以在你开始这个算法之前你已经在使用 Θ(n) space ，当你完成后你有相同的列表，只是重新连接以便下一个指针可能指向不同的地方。因此，您需要为此过程分配的 内存量不是 Θ(n)，而是 Θ(1)。

更一般地说，在测量 space 复杂性时忽略问题输入使用的 space 是很常见的，因为在某种意义上 space 成本是不可避免的，没有什么你可以做些什么来消除它。

一个前进的建议：如果你写像 O(1) 或 O(n) 这样的东西，那么明确你是在测量时间还是 space 通常是个好主意。例如，更清楚地说过程需要 O(n) 内存 或 O(1) 时间 而不是说过程 "is" O(n) 或 "is" O(1)，因为当你这样做时不清楚你用大 O 符号测量的是什么。

Answer 2

跟进 templatetypedef 的回答，因为相同的节点被用于输入和输出，所以那里没有额外的 space 使用。

只有在不支持指向指针的指针的语言中才需要虚拟节点 and/or 以简化代码。在 C / C++ 的情况下，你可以使用这样的东西：

NODE *merge(NODE *pSrc1, NODE *pSrc2){
    NODE *pDst = NULL;            // ptr to destination (merged) list
    NODE *ppDst = &pDst;          // ptr to pDst or some next pointer
    // ...
        *ppDst = ...              // add a node to the destination list
        // ...
        ppDst = &((*ppDst)->next) // advance ppDst
    // ...
    return pDst;                  // return ptr to merged list
}

合并两个排序的链表——理解为什么它是 O(1) vs. O(N) space 复杂度

Merging two sorted linked list--understanding why it's O(1) vs. O(N) space complexity

data-structures

merge

linked-list

big-o

space-complexity