2

練習問題を解いていて、次の問題に出くわしました

以下の分割統治アルゴリズムに対応する繰り返しを書き留め、分割、征服、および結合のそれぞれのコンポーネントを正確にラベル付けします。

1. Foo (p, r):
2.     if p = r
3.          return (1)
4.     else
5.         s ← 1
6.         for i = p to r
7.             s ← s * i
8.         q ← Foo(p, r − 1) * s
9.     return (q)

私の答えの試み。

  1. T(n) を Foo が p から r に渡って行った作業とすると、T(n) は Foo(p, r) と同等になります。ここで、n は r - p + 1 です。

  2. 次の繰り返しを取得します T(n) = T(n - 1) + Θ(n) + Θ(1)

  3. 分割部分は、r-1 操作に対応する定数 Θ(1) になります。

  4. 征服部分は、サブ問題を再帰的に解決する T(n - 1) です。

  5. 結合部分は、T(n - 1) * s の乗算演算の定数 Θ(1) です。

しかし、私は Θ(n) について言及しなかったので、それは間違っているようです。行 6、7 の Θ(n) は、分割、征服、結合のどの部分に該当しますか?

4

1 に答える 1

1

sはpからrに蓄積されるため、これは「結合」部分に分類されるように見えます。したがって、組み合わせによってΘ（n）が得られます。

要素を組み合わせて元に戻すときは、基本的に、n個の要素の上にバックアップを圧縮する必要があります。

于 2012-06-08T00:03:32.880 に答える