如何证明下列函数 h.g(n) = O(f(n))
How to prove the following functions h.g(n) = O(f(n))
鉴于此，
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，这将很容易证明。
我尝试了不同的函数多项式、对数、指数函数 none 其中的一个有效。
假设 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)。这意味着我们可以从 [O(1):o(x)] 中选择任何 h(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
鉴于此，
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，这将很容易证明。
我尝试了不同的函数多项式、对数、指数函数 none 其中的一个有效。
假设 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)。这意味着我们可以从 [O(1):o(x)] 中选择任何 h(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