渐近符号的除法运算 [英] Division operation on asymptotic notation

问题描述

假设

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

都 f（n）完全属于同一类。

我的问题是：为什么 S（n）/ T（n）= Big-Oh（1）是

推荐答案

考虑 S（n）= n ^ 2 和 T（n）= n 。然后 S 和 T 均为 O（n ^ 2），但 S（n）/ T（n）= n 不是 O（1）。

Consider S(n) = n^2 and T(n) = n. Then both S and T are O(n^2) but S(n) / T(n) = n which is not O(1).

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

Here's another example. Consider S(n) = sin(n) and T(n) = cos(n). Then S and T are O(1) but S(n) / T(n) = tan(n) is not O(1). This second example is important because it shows that even if you have a tight bound, the conclusion can still fail.

为什么会这样？因为明显的证明完全失败了。显而易见的证明如下。有常量 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 ，我们有

Why is this happening? Because the obvious "proof" completely fails. The obvious "proof" is the following. There are constants C_S and C_T and N_S and N_T where n >= N_S implies |S(n)| <= C_S * f(n) and n >= N_T implies |T(n)| <= C_T * f(n). Let N = max(N_S, N_T). Then for n >= N we have

|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 是小的，而我们做不到。如我们的反例所示，证明存在致命缺陷。

This is completely and utterly wrong. It is not the case that |T(n)| <= C_T * f(n) implies that 1 / |T(n)| <= 1 / (C_T * f(n)). In fact, what is true is that 1 / |T(n)| >= 1 / (C_T * f(n)). The inequality reverses, and that suggests there is a serious problem with the "theorem." The intuitive idea is that if T is "small" (i.e., bounded) then 1 / T is "big." But we're trying to show that 1 / T is "small" and we just can't do that. As our counterexamples show, the "proof" is fatally flawed.

但是，这里有一个定理是正确的。即，如果 S（n）是 O（f（n））和 T（ n）是Ω（f（n）），然后 S（n）/ T（n）是 O（1）。上述证明适用于该定理（感谢归因于 Simone ，以将其概括为该语句）。

However, there is a theorem here that is true. Namely, if S(n) is O(f(n)) and T(n) is Ω(f(n)), then S(n) / T(n) is O(1). The above "proof" works for this theorem (thanks are due to Simone for the idea to generalize to this statement).

这篇关于渐近符号的除法运算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！