これは、MIT OpenCourseアルゴリズム入門の割り当てによる漸近表記の問題です
。次の各ステートメントについて、漸近的に非負の関数fおよびgについて、常に真であるか、決して真ではないか、場合によっては真であるかを判断します。それが常に真実であるか、決して真実ではない場合は、その理由を説明してください。時々真である場合は、それが真である例と偽である例を1つ挙げてください。
f(n) ≠ O(g(n)) and g(n) ≠ O(f(n)) (both are Big-O notes)
私はそれが決して真実ではないと思います。これが私の証拠です:
f(n) ≠ O(g(n))
=> f(n) = w(g(n)) (little-omega note)
=> g(n) = o(f(n)) (little-o note)
=> g(n) = O(f(n)) (big-O note)
結果はと矛盾しg(n) ≠ O(f(n)) (Big-O note)
ます。同じく、
g(n) ≠ O(f(n))
=> g(n) = w(f(n)) (little-omega note)
=> f(n) = o(g(n)) (little-o note)
=> f(n) = O(g(n)) (big-O note)
これはと矛盾しf(n) ≠ O(g(n)) (Big-O note)
ます。
解決策はそれが時々真実であると言います:
For f(n) = 1 and g(n) = ||n*sin(n)|| it is true,
while for any f(n) = O(g(n)), e.g. f(n) = g(n) = 1, it is not true.
証明のどこで間違ったことをしましたか?また、解決策がわかりません。私にはベクトルノルム||n*sin(n)||
のように見えます。