complexity-theory - 渐近符号的除法运算

Question

认为

S(n) = Big-Oh(f(n)) & T(n) = Big-Oh(f(n)) 

两个 f(n) 完全属于同一类。

我的问题是:为什么 S(n)/T(n) = Big-Oh(1) 不正确？

Answer 1

考虑 S(n) = n^2 和 T(n) = n 。那么 S 和 T 都是 O(n^2) 但 S(n) / T(n) = n 不是 O(1) 。

这是另一个例子。考虑 S(n) = sin(n) 和 T(n) = cos(n) 。然后 S 和 T 是 O(1) 但 S(n) / T(n) = tan(n) 不是 O(1) 。第二个例子很重要，因为它表明即使你有一个严格的界限，结论仍然可能失败。

为什么会这样？因为明显的“证明”完全失败了。显而易见的“证据”如下。有常量 C_S 和 C_T 以及 N_S 和 N_T ，其中 n >= N_S 表示 |S(n)| <= C_S * f(n) ， n >= N_T 表示 |T(n)| <= C_T * f(n) 。让 N = max(N_S, N_T) 。然后对于 n >= N 我们有

|S(n) / T(n)| <= (C_S * f(n)) / (C_T * f(n)) = C_S / C_T.

这是完全错误的。 |T(n)| <= C_T * f(n) 并不意味着 1 / |T(n)| <= 1 / (C_T * f(n)) 。事实上，正确的是 1 / |T(n)| >= 1 / (C_T * f(n)) 。不等式反过来，这表明“定理”存在严重问题。直观的想法是，如果 T 是“小”(即有界)，那么 1 / T 是“大”。但是我们试图证明 1 / T 是“小”的，我们就是做不到这一点。正如我们的反例所示，“证明”存在致命缺陷。

然而，这里有一个定理是正确的。即，如果 S(n) 是 O(f(n)) 并且 T(n) 是 Ω(f(n)) ，那么 S(n) / T(n) 就是 O(1) 。上面的“证明”适用于这个定理(感谢 Simone 将想法推广到这个陈述)。