1

これは、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)||のように見えます。

4

2 に答える 2

3

Big Oを定義するために使用される定数乗数のすべての選択についても、nの後続の値n*sin(n)よりも大きくなり小さくなり続ける関数であることを示していると思います。f(n) = 1f(n) ≠ O(g(n)) and g(n) ≠ O(f(n))

のような単純に選択された関数g(n) = 2*sin(n)は、ここではうまくいきません。これも交互に繰り返すと思うかもしれませんf(n) = 1が、g(n) = O(f(n)) : M*f(n) > g(n) for M = 3など

于 2012-02-18T12:53:05.587 に答える
2

最初は真実ではありません:f(n) ≠ O(g(n))これからそれはこれに続きません:f(n) = w(g(n))。2つの関数は、ある時点で交差してから場所を叩き、もう一方は大きくなる可能性があります(単純な単語を使用する場合)。

彼らが選択した関数はまさにこの場合です。n<=1の場合、最初のf(n)> g(n)であり、g(n)> f(n)(たとえば、pi / 2)であるnsが存在します。

于 2012-02-18T12:24:28.903 に答える