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)意味着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.