假设
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).
这是另一个例子.考虑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的想法推广到这个陈述).