5

私は現在、最初の離散数学クラスを受講していますが、少し問題があります。これはビッグ オーとの初めての出会いであり、この特定の問題を理解するのに少し苦労しています。

n <= O(n)n >= k のすべての値に当てはまる定数があることを数学的に証明できるため、その証明を理解しています

もしf、g、hがf(n) = O(g(n))とg(n) = O(h(n))

クラスで与えられたbig ohの定義を使ってそれを証明してくださいf(n) = O(h(n))

私の答えは

|f(n)| <= U1|g(n)| for all n >= k

|g(n)| <= U2|h(n)| for all n >= j

したがって

|f(n)| <= U3|h(n)| for all n >= i

したがって、f(x)=O(h(x))

私はオフィスアワーに教授に会おうとしましたが、彼女は私の校正が間違っていると言いましたが、その理由については教えてくれませんでした. 私はこれに非常に長い時間を費やしてきたので、何をすべきかさえわかりません。どんな助けでも素晴らしいでしょう...

わかった！これをもう一度試してみましょう。

|f(n)| <= U1|g(n)| for all n >= k

|g(n)| <= U2|h(n)| for all n >= j

iのいずれかの最大値に等しくしますk ∨ j。

等しくU3するU1 * U2

f(n) <= U3|h(n)| for all n >= i

したがって

f(n) = O(h(n))

より良い？

4

3 に答える 3

3

Big O 定義の使用:

f = O(g) iff exist c, n0 > 0 such that forall n >= n0 then 0 <= f(n) <= cg(n)

g = O(h) iff exist k, n1 > 0 such that forall n >= n1 then 0 <= g(n) <= kh(n)

cここで、最後の不等式を取り、すべてのメンバーを:で割ります。2 番目の不等式: に0 <= f(n)/c <= g(n)代入できます。最後に、すべてのメンバーを で乗算すると、次の定義が得られます。g(n)0 <= f(n)/c <= kh(n)c0 <= f(n) <= kch(n)f = O(h)

f = O(h) iff exist j, n2 > 0 such that forall n >= n2 then 0 <= f(n) <= jh(n)

私たちの場合はn2 = max(n0, n1)、 とj = ckです。

于 2013-01-20T17:38:09.530 に答える
1

Bachmann–Landau 記法の極限解釈を使用できます。

次に、次の推論を使用できます。

推論

于 2013-01-20T17:34:51.297 に答える
0

2番目の不等式を最初の不等式に代入すると、 になるはずU3 = U1 * U2ですが、「i」と呼ばれるものが重要なポイントです。私は、あなたがn >= argmax{ k, j }.

于 2013-01-20T17:27:41.463 に答える