是否有诸如 f(n) 和 g(n) 之类的函数？
f(n) != O(g(n)) and
g(n) != O(f(n)).
是否有满足上述要求的功能？
10685 次
2 回答
3
于 2013-03-21T11:40:52.350 回答
1
考虑：
f(n) = 0 if n is odd, else n*n
g(n) = n
那么对于奇数值g(n)来说是大于大于的常数因子f(n)（所以g(n)不是O(f(n))，而对于偶数值f(n)来说是大于一个常数因子大于g(n)（所以f(n)不是O(g(n))）。
请注意，f(n)随着接近无穷大，它在无穷大处没有限制n，所以在某种意义上，这是一个廉价的例子。但是您可以通过替换0, n, n*n为n, n*n, n*n*n.
我认为，如果两个非负函数具有在接近无穷大时f(n)/g(n)具有（可能是无限）极限的属性n，那么其中一个是大 O 另一个。如果极限是 0 那么f(n)是O(g(n))，如果极限是有限的那么每个都是 big-O 另一个，如果极限是无限的那么g(n)是O(f(n))。但是我懒得写证明来确认。
于 2013-03-21T11:50:09.577 回答