algorithm - 非効率な分割統治アルゴリズムの複雑さ

Question

size のインスタンスは、それぞれsize のインスタンスにn分割されます。ここで、 は smallで、はです。この操作 (インスタンスへの分割) の計算コストは​​単位であり、p≥2n-aaintegerpconstantC(0)=1.

このデザインの複雑さを見つけようとしています。単語を方程式に入れるのに問題があります。再帰は次のようになります。

C(n) = (n-a)*C(n/p) + 1

これは正しいです？

Answer 1

まあ、これは学校の課題のように見えるので、特に「非効率な分割統治アルゴリズム」という文言のために、私も直接答えません.

私のアドバイスは、例としてa=1andを使用することです。p=2この場合、サイズ の部分問題を 2 つ解いてからn-1、1 単位の時間をかけて解を組み合わせる必要があります。を解くのに 1 単位の時間がかかる場合n=1、つまりC(1)=1、

C(1)=1
C(2) = 2*C(1) + 1 = 3
C(3) = 2*C(2) + 1 = 7
C(4) = 2*C(3) + 1 = 15

などだからあなたは得るC(n) =2^n - 1。が 1 でない場合、これは基本的に同じことです: の代わりにaべき乗するだけです。n/an

ところで、「定数」aなのに「小さな整数」と呼ぶのはおかしくないですか？pもちろん、どちらの表現も同じ意味です。漸近的な動作に関する限り、すべての定数は「小さい」です。

Answer 2

Shashank が書いたように、C(n) = p⋅C(na) + 1 が正しいです。

言いたいのは、これが結果として

C(n) = Σ _i=0,...,n/a p ⁱ = p ^{n/a + 1} - 1

したがって、C(n) は O(p ^n/a ) にあり、これは n で指数関数的です。