如何判断时间复杂度是O(m + n)还是O(Math.max(m, n))

Question

我正在检查这段代码，但我很难理解它是 O(m + n) 而不是 O(Math.max(m, n))。还是 O(m + n) 在 O(Math.max(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 上有一个示例，其中函数 returns 是一个 n 大小的数组。它表示，由于 n > logn，在计算大 O 时，由于堆栈调用导致的 log(n) 的 space 复杂性相形见绌，导致整体 O(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))，集合相等。

这是正式的（一维）定义（来自Wikipedia）：

直觉上它也有意义，因为这两个函数只是意味着两个变量的线性增长，仅此而已。

[...] resulting in O(n) overall. O(n + logn) isn't mentioned [...]

我不确定这是否是一个问题。请注意，这两个集合再次与 n <= n + log(n) 和 n + log(n) <= n + n = 2 * n 相同， 在 n.

中是线性的

如何判断时间复杂度是O(m + n)还是O(Math.max(m, n))

How to determine if the time complexity is O(m + n) or O(Math.max(m, n))

java

performance

time

time-complexity

space-complexity