问题是:
显示或证明对于两个函数f,g,如果f不在O(g)中,则g在O(f)中。
我的反例:
Let f(n) be f(n) = n^2 : if n is even
or n^4 : if n is odd
Let g(n) be g(n) = n^3
这是f不在O(g)中且g不在O(f)中的示例。我的例子错了吗?如果是这样,为什么?您还有其他示例吗?
您的反例工作。一个证明可能看起来像这样:
假设f为O(g)。然后有一个正常数c和一个n0,使得对于n> = n0,f(n)<= c * g(n)。令n'为大于或等于n0的奇数整数。那么我们有n'^ 4 <= c * n'^ 3。将两侧除以n'^ 3得出n'<= c。但是,这对于所有n'> n0都不成立。所以甚至有大于n0的n不能满足条件,这是一个矛盾。]
相反的证明是相似的,除了将两边都除以n'^ 2。
我认为您确定的这种反例是一个很好的例子;一个以渐近递增的方式振荡的函数,以及一个在中间某处出现的函数。