如何確定的時間複雜度爲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，在正線性。