鉴于此，
Let f(n) = O(g(n)), let g(n) = O(h(n)), what could be the functions of f(n), g(n) and h(n) to make the following true h.g(n) = O(f(n)).
我已经尝试过所有可能的解决方案。例如让 f(n) = g(n) = h(n) = n。
所以 f(n) 是 g(n) 的大 O 是真的，g(n) 是 h(n) 的大 O，但是 h.g = O(f(n)) 那当然是假的。因为我要得到 n^2，如果它是 Ω 符号而不是 Big O，这将很容易证明。
我尝试了不同的函数多项式、对数、指数函数，但都没有用。
最佳答案
假设h(x)是OMEGA(x) ，这意味着必须存在一些恒定的正值 x', a,b,c,d这样对于任何 x>x' ，以下成立:
f(x) <= a*g(x), g(x) <= b*h(x)和 d*f(x) >= h(g(x)) >= c*g(x) >= c*a*f(x) ，这意味着事实上 g和 f渐近等价并且都是o(x) ，但是 h(x)实际上是 Theta(x) (否则矛盾)-这导致一组解决方案
现在假设 h(x)是o(x) ，这意味着所有 f,g,h实际上是o(x) .这意味着我们可以选择任何 h(x)来自 [O(1):o(x)] , 然后选择任何 g(x) , 这样 g(x)是[O(1):o(h)]然后选择任何 f来自 [OMEGA[h(g(x)), o(g(x))] 的范围由于 h 而必须存在正在o(x) .这些导致第二组解决方案(无限数量，基于 h(x) 的选择)
注意:假设所有函数都递增且至少为 o(1)
IGNORE THE FOLLOWING - incorrectly understood the question
这没有回答问题，但可能有帮助
显然所有三个函数f,g,h是 O(1) .很容易看出原因:
必须存在一些恒定的正值 x', a,b,c这样对于任何 x>x' ，以下成立:
f(x) <= a*g(x), g(x) <= b*h(x), h(x)*g(x) <= c*f(x) , 所以
c*f(x) >= h(x)*g(x) >= a*b*f(x)*f(x), or f(x) =< c/(b*a)
所以我们可以得出结论 f(x)实际上是O(1)
此外，
C >= c*f(x) >= h(x)*g(x) >= g(x)*g(x)*b
所以 g(x)是O(1)也。
最后
c*f(x) >= h(x)*g(x) >= h(x)*f(x)*a, or h(x) <= c/a
三个函数都是O(1) .一个例子是 f(x)=1/(x^3), g(x)=1/x^2,h(x)=1/x
关于algorithm - 如何证明下列函数 h.g(n) = O(f(n))，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36168685/