鉴于，
令f（n）= O（g（n）），令g（n）= O（h（n）），f（n），g（n）和h（n）的函数可能是什么下面的真实hg（n）= O（f（n））。
我已经尝试过所有可能的解决方案。例如，令f（n）= g（n）= h（n）= n。
因此，f（n）是g（n）的大O，这是正确的，而g（n）是h（n）的大O，但是hg = 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）
忽略以下内容-错误地理解了问题
这不能回答问题，但可能会有帮助
显然，这三个功能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）或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或h（x）<= c / a
这三个功能都是O(1)。一个例子是f(x)=1/(x^3), g(x)=1/x^2,h(x)=1/x
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句