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(N+M)和O(N) + O(M)有什么区别？有吗？如果它们不同，如果有人能提供两者的简单例子，我将不胜感激。

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.