0

私が研究したことから: 別の関数に関して関数の複雑さを決定するように求められました。すなわち を与えられf(n)、g(n)を決定しO(f(n()ます。そのような場合、私は値を代入し、それらの両方を比較して複雑さに到達します - を使用しO(), Theta and Omega notationsます。

ただし、 ではsubstitution method for solving recurrences、すべての標準ドキュメントに次の行があります。

• [Assume that T(1) = Θ(1).]

•Guess O(n3) . (Prove O and Ω separately.)

•Assume that T(k) ≤ ck3 for k < n .

•Prove T(n) ≤ cn3 by induction.

(f(n) 以外に) 他に何も指定されていない場合、O と Ω を見つけるにはどうすればよいですか? 私は間違っているかもしれません (間違いなくそうです)。上記に関する情報は大歓迎です。

上記の仮定のいくつかは、この問題に関するものT(n) = 4T(n/2) + n です:

4

1 に答える 1

2

その特定の再発はマスター定理によって解決できますが、代入法からいくらかのフィードバックを得ることができます。の最初の推測を試してみましょうcn^3。

T(n)  = 4T(n/2) + n
     <= 4c(n/2)^3 + n
      = cn^3/2 + n

すべての関連するcように選択すると仮定すると、n <= cn^3/2n

T(n) <= cn^3/2 + n
     <= cn^3/2 + cn^3/2
      = cn^3,

そうTですO(n^3)。この導出の興味深い部分は、線形項を一掃するために 3 次項を使用したところです。そのようなやり過ぎは、多くの場合、より低く推測できる兆候です。試してみましょうcn。

T(n)  = 4T(n/2) + n
     <= 4cn/2 + n
      = 2cn + n

これはうまくいきません。右辺と必要な境界の間のギャップは ですcn + n。これは、必要な境界の大きなシータです。これは通常、より高い推測を行う必要があることを意味します。試してみましょうcn^2。

T(n)  = 4T(n/2) + n
     <= 4c(n/2)^2 + n
      = cn^2 + n

それも最初は失敗に見えます。ただし、私たちの推測とは異なりn、赤字は境界自体のほとんどではありません。cn^2 - h(n)という形の境界を考えることで、それを閉じることhができるかもしれませんo(n^2)。なぜ引き算？候補限界として使用hすると、赤字になります。を引くhと、余剰になります。の一般的な選択肢はh、低次多項式またはlog nです。試してみましょうcn^2 - n。

T(n)  = 4T(n/2) + n
     <= 4(c(n/2)^2 - n/2) + n
      = cn^2 - 2n + n
      = cn^2 - n

それがたまたま再発の正確な解決策であり、私の側ではかなり幸運でした. 代わりに推測していたらcn^2 - 2n、少しクレジットが残っていたでしょう。

T(n)  = 4T(n/2) + n
     <= 4(c(n/2)^2 - 2n/2) + n
      = cn^2 - 4n + n
      = cn^2 - 3n,

よりわずかに小さいですcn^2 - 2n。

于 2013-04-17T14:10:47.527 に答える