f（n）やg（n）などの両方の関数はありますか。
f(n) != O(g(n)) and
g(n) != O(f(n)).
上記の要件を満たす機能はありますか？
10685 次
2 に答える
3
f(n)=n and g(n)=n^(1 + sin(x)).
f(n) は O(g(n)) ではなく、g(n) は O(f(n)) ではありません。
于 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。
2つの非負の関数が、無限大に近づくにつれてf(n)/g(n)（おそらく無限大の）限界を持つプロパティを持っているn場合、一方は大きい-もう一方は大きいということになります。制限が0の場合f(n)はO(g(n))、であり、制限が有限の場合はそれぞれが大きく、もう一方は大きく、制限が無限の場合g(n)はですO(f(n))。しかし、私は怠惰すぎて証拠を書いて確認することができません。
于 2013-03-21T11:50:09.577 に答える