big-o - O(N) + O(M) 和 O(N + M) 之间有什么区别。有没有？

Question

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

Given two sorted Linked Lists, merge them into a third list in sorted order. Let's assume we are using descending ordering.

我遇到的答案之一(显然不是最有效的)是以下递归解决方案:

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(N+M) 和有什么不一样和 O(N) + O(M) ? 有没有？如果它们不同，如​​果有人可以提供两者的简单示例，我将不胜感激。

Answer 1

O(N) + O(M)表示以 cN + dM 为界的函数一些 c和 d .
O(N + M)表示以 e(N + M) 为界的函数一些 e .

它们是等价的，因为:
cN + dM <= (c + d)(N + M)一些 c和 d .

和
e(N + M) <= eN + eM一些 e .