赤で強調表示されている次の不等式が、この漸近解析の問題でどのように導出されたかを理解するのに問題があります。誰かがこれらの不平等の性質と、それらがどのようになったかを説明できますか.
次の図に問題と解決策があります。赤くハイライトされた部分は、私が理解に苦しむ部分です。
問題と解決策の図
1 に答える
0
準備
上の画像の赤いマークのセクションの上の部分は、まさに Big-Θ 表記の定義f(n)ですΘ(g(n))。
f(n) = (n + a)^b, b > 0 (+)
g(n) = n^b (++)
以下で成り立つことを示すときに参照を単純化するために、この不等式を繰り返します。
f(n) is in Θ(g(n)) with f(n) and g(n) as in (+) and (++), respectively
<=>
c_1⋅n^b ≤ (n + a)^b ≤ c_2⋅n^b, for some positive constants c_1, c2 (*)
for n ≥ n_0, with n_0 constant > 0
c_1したがって、いくつかのc_2などn_0を見つけたいと思い(*)ます。
解決策（徹底的に説明）
から、次の 2 つの不等式が成り立つ場合に が成り立つb > 0ことを証明できます。(*)
n + a ≥ k_1⋅n, for n > n_0 (i)
n + a ≤ k_2⋅n, for n > n_0 (ii)
いくつかの正の定数k_1およびk_2(それぞれ および および にc_1関連するc_2) 。k_1^b = c_1k_2^b = c_2
(ii)保持することを示す
(ii)ある正の定数 が成り立つことを示すことから始めましょうk_1。これを行うには、(は単なる定数であるため)を自由に選択できます。 n_0n_0 ≥ |a|a
=> n ≥ |a| ≥ a, since n ≥ n_0 ≥ |a|
Hence:
n + a ≤ n + |a| ≤ n + n = 2⋅n, for n ≥ n_0 ≥ |a| (II)
ここで、 でが成り立つことを(II)示しました。(ii)k_1 = 2n_0abs(a)n_0 ≥ |a|
(i)保持することを示す
を示すため(i)に、次の不等式が常に成り立つことに注意することから始めます。
n + a ≥ n - |a| (†)
a(実際には が負の場合は等しい)。(II)ここで、任意の に当てはまる上記を思い出してn_0 ≥ |a|ください。では、n0atを修正することを選択しましょう2⋅|a|(繰り返しますが、不等式(*)が成り立つことを示したい定数を自由に選択できます)。
Choose n_0 as n_0 = 2⋅|a| (††)
したがって、から(†)：
n + a ≥ n - |a| ≥ n - n/2 = n/2 (†††)
^
|
Why? Since from (††): |a| = n_0/2 < n/2, since n>n_0
We repeat (†††) without the middle stuff:
n + a ≥ (1/2)⋅n, for n > n_0 = 2⋅|a| (I)
そして(I)今は単純(i)にk_2 = 1/2とn_0 = 2⋅|a|です。
まとめ
要約します：
(I) & (II) => (1/2)⋅n ≤ n + a ≤ 2⋅n
With b>0, this yields:
((1/2)⋅n)^b ≤ (n + a)^b ≤ (2⋅n)^b (**)
で、 が成り立つ(**)ことを示しました。(*)
c_1 = k_1^b = (1/2)^b = 2^(-b)
c_2 = k_2^b = 2^b (note that the solution you posted has an error here)
n_0 = 2⋅|a|
したがって、f(n)as in(+)が inΘ(g(n))であり、g(n)as in であることを示しました(++)。
c_1最後に、定数、c_2( k_1、k_2) およびn_0inの選択は一意ではないことに注意してください。それが成り立つか (存在する場合)、または存在しないこと(*)を示す方法は無限にあります。(*)この場合、ソリューションの作成者による特定の選択は当然のことですが、他の定数セットをいくつでも選択できます。
于 2016-02-04T23:16:16.047 に答える