私は試験でこの問題を間違えました: O(n)でもOmega(n)でもない関数を挙げてください。
YouTube を通じて自分でこのことを学ぼうとした後、これが正しい答えかもしれないと考えています。
(n 3 (1 + sin n)) は O(n) でも Omega(n) でもありません。
それは正確でしょうか?
O(n)でもOmega(n)でもない関数を挙げてください
言うf ∈ O(g)
ことは商を意味する
f(x)/g(x)
はすべて十分に大きい に対して上から有界x
です。
f ∈ Ω(g)
一方、商を意味します
f(x)/g(x)
十分に大きいすべてx
の
したがって、どちらO(n)
でもない関数を見つけるということは、そのようなΩ(n)
関数を見つけることを意味します。f
f(x)/x
は任意に大きくなり、間隔ごとに任意にゼロに近づきます[y, ∞)
。
私はこれが正しい答えかもしれないと考えています:
(n^3 (1 + sin n))
O(n) でも Omega(n) でもありません。
それを商に当てはめましょう。
(n^3*(1 + sin n))/n = n^2*(1 + sin n)
はn^2
無限に成長し、1 + sin n
約 6 分の 3 で係数が 1 より大きくなりn
ます。したがって、間隔ごと[y, ∞)
に商は任意に大きくなります。任意K > 0
の 、 let N_0 = y + K + 1
、およびそのようなN_1
最小のものを指定します。それから。N_0 + i, i = 0, 1, ..., 4
sin (N_0+i) > 0
f(N_1)/N_1 > (y + K + 1)² > K² + K > K
そのΩ(n)
部分については、証明するのはそれほど簡単ではありませんが、満足していると思います.
しかし、関数を少し修正して、証明が簡単になるように、成長する関数と振動する関数を乗算するという考えを保持することができます。
の代わりに をsin n
選択cos (π*n)
し、ゼロをオフセットするために高速減少関数を追加します。
f'(n) = n^3*(1 + cos (π*n) + 1/n^4)
今、
/ n^3*(2 + 1/n^4), if n is even
f'(n) = <
\ 1/n , if n is odd
f'
そして、 は上からも下からも の正の定数倍数によって制限されていないことは明らかですn
。
二分探索のようなものを考えます。これは、O(log N)とΩ(logN)の両方です。オメガは下限として定義されているため、関数自体を超えることはできません。したがって、O(log N)は間違いなくΩ(N)ではありません。
削除された回答に対するコメントのいくつかは、いくつかの...明確化に値すると思います-おそらく完全な修正ですら。CLRSから引用すると、「Ω表記は関数の下限を一定の係数内に与えます。」
N 2はNと一定の係数以上異なるため、N 2はΩ(N)ではありません。