如何确定的时间复杂度为O（M + N）或O（Math.max（M，N））

Question

我会在这个代码，但我竭力要了解它是如何为O（M + N ）而不是O（Math.max（m，n））。或者是O（Math.max（m，n））下的O（m + n）呢？

int i = 0, j = 0, res = 0; 
    while (i < houses.length) { 
     while (j < heaters.length - 1 
      && Math.abs(heaters[j + 1] - houses[i]) <= Math.abs(heaters[j] - houses[i])) { 
      j++; 
     } 
     res = Math.max(res, Math.abs(heaters[j] - houses[i])); 
     i++; 
    } 

有一个关于CTCI的例子，其中函数返回一个n大小的数组。它说，由于计算N> LOGN大O字时，导致O（n）的整体因调用堆栈的log（n）的空间复杂度是小巫见大巫。在这个例子中没有提到O（n + logn）（对于那些好奇的人来说是4.4）。

任何解释，将不胜感激！

Answer 1

正如您已经猜到的，在Big-O-Notation这两个是相同的。

两个功能，m + n和max(m, n)，都是元素集合O(m + n) = O(max(m, n)。

---

让我们来算一算：

m + n <= max(m, n) + max(m, n) = 2 * max(m, n)也
max(m, n) <= m + n只要min(m, n) >= 0（但m, n >= 0已经）

所以这两个功能是由其他功能（加上一个常数因子）为界，因此O(m + n)或O(max(m, n))，集合是相等的。

这里是正规（1维）定义（从Wikipedia）：

---

直观它也有意义作为两种功能仅仅意味着在两个线性增长变量，仅此而已。

---

[...]导致O（N）的整体。没有提到O（n + logn）[012]

我不确定这是否是一个问题。只要注意这两个集再次同n <= n + log(n)也n + log(n) <= n + n = 2 * n，在正线性。