渐近符号的除法运算 [英] 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屋!