O(N) + O(M)和O(N + M)有什么区别？是否有任何区别？

Question

我正在解决面试练习中的问题，但似乎无法找出以下问题的时间和空间复杂度答案：

给定两个已排序的链表，将它们合并到第三个链表中以排序顺序。假设我们使用降序排序。

我遇到的一个答案显然不是最有效的，是以下递归解决方案：

Node mergeLists(Node head1, Node head2) {
    if (head1 == null) {
        return head2;
    } else if (head2 == null) {
        return head1;
    }

    Node newHead = null;
    if(head1.data < head2.data) {
        newHead = head1;
        newHead.next = mergeLists(head1.next, head2);
    } else {
        newHead = head2;
        newHead.next = mergeLists(head1, head2.next);
    }

    return newHead;
}

现在，当我分析这个函数的复杂度时，遇到了一个问题。我不确定是O(M + N)还是O(M) + O(N)。我无法得出一个直观的答案。对我来说，这个函数的运行时间和空间复杂度似乎是O(N) + O(M)或O(max(N,M))，因为较大的值会驱动渐近曲线（或递归调用和堆栈帧创建）。

总之：

在大O符号表示法中，O(N+M)和O(N) + O(M)有什么区别？它们是否有任何区别？如果它们不同，我将感激有人提供简单的示例。

- nem035

---

你在哪里看到“O(n)+O(m)”？ - Dai

我们无论M和N是多少，都要检查每个列表的所有节点？显然，我不确定哪个是答案，因为我在这里提问 :) 从技术上讲，正如我上面所说，我认为答案是O(max(N,M))，因为较大的值将是渐近界限。 - nem035

Answer 1

O(N) + O(M) 表示被一些 c 和 d 限制为 cN + dM 的函数。

O(N + M) 表示被一些 e 限制为 e(N + M) 的函数。

它们是等价的，因为:

cN + dM <= (c + d)(N + M) 对于一些 c 和 d 成立。

和

e(N + M) <= eN + eM 对于一些 e 成立。

- fgb