algorithm - 为什么复杂性函数的减法是它们中最小值的大O？

Question

设 f(n) 和 g(n) 复杂度函数。为什么这个说法成立？我怎样才能证明呢？

• f(n) - g(n) 是 O(min(f(n),g(n)))

Answer 1

这个提议显然是错误的。考虑f(n)=n和g(n)=0。min(f(n),g(n))是零n>=0，但是f(n)-g(n) = n，不是O(0)。

对于每一个n>=0，也是f(n)-g(n) <= f(n)如此。我认为这是一般可以做出的最强有力的陈述，没有下限是 的正函数。f(n)-g(n)O(f(n))g(n)n

==================================================== =========================

上面的第二段是不正确的，因为正如@Dukeling 在评论中指出的那样，g(n)可能大到f(n)-g(n)负数，绝对幅度可能大于f(n). 在这种情况下会发生什么取决于 big-O 的定义。

NIST网页将其定义如下：“正式定义：f(n) = O(g(n)) 表示存在正常数 c 和 k，因此对于所有 n，0 ≤ f(n) ≤ cg(n ) ≥ k。对于函数 f，c 和 k 的值必须是固定的，并且不能依赖于 n。"

根据该定义，对于每个正数k至少有一个n>=k为f(n)负数的函数不是大 O 任何东西。

维基百科页面将其定义如下（转换为 ASCII）：f(x) = O(g(x))当且仅当存在正实数M和实数x_0使得

|f(x)| <=  M |g(x)|  for all x>x_0

这个定义确实允许使用 big-O 表示法来处理对大参数值负的函数，方法是使用它的绝对值。有了这个定义，f(n)-g(n)就是O(max(f(n),g(n)))。

Answer 2

The statement is actually false. First, note that O deals with magnitudes, so the sign of f and/or g is irrelevant. The correct relationship is

O(|f(n)| + |g(n)|)

(see here for instance). If |f| grows faster than |g|, then |f| is going to asymptotically dominate |f-g|, and likewise if the converse is true.

If there are other facts about f and g that are not in your post (e.g., that both functions are always negative), then it may be possible that O(|f| + |g|) = O(min(f, g)) (= O(|min(f, g)|)).