不在 O(g) 中的函数 f 和不在 O(f) 中的函数
Functions f not in O(g) and g not in O(f)
问题是：
Show or disprove that for two functions f,g, if f is not in O(g) then g is in 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 都成立；所以还有n大于n0的条件不成立，矛盾
相反的证明是类似的，除了你将两边除以 n'^2。
我认为您确定的那种反例对此很好；一个以渐近递增的量振荡的函数和一个位于中间某处的函数。
问题是：
Show or disprove that for two functions f,g, if f is not in O(g) then g is in 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 都成立；所以还有n大于n0的条件不成立，矛盾
相反的证明是类似的，除了你将两边除以 n'^2。
我认为您确定的那种反例对此很好；一个以渐近递增的量振荡的函数和一个位于中间某处的函数。