2

私は、再帰関数を開発し、漸近的な時間の複雑さを分析するように依頼されました。

f(N) = 0, if N < N1

f(N1) = C1

f(N)= A1 + M1*f(M2*N/D1 - S1) Op M3*f(M4*N/D2 - S2), if N > N1

次のように仮定します。

s1 = s2 = 0

m2 = m4 = 1

d1 = d2 > 1

//the user enters N1 C1 A1 M1 M2 M3 M4 D1 D2 S1 S2 and then ARG

int Recursion_Plus(int ARG)
{

    if (ARG < n1)
    {
        return 0;
    }

    else if(ARG == n1)
   {
    return c1;
   }

   else if(ARG > n1 )
   {

    return a1 + m1 
    * 
    Recursion_Plus(m2*ARG/d1 - s1) 
    + 
    m3*Recursion_Plus(m4*ARG/d2 - s2);

   }

}

インストラクターのプログラムに対して再帰関数をテストしましたが、まったく同じように機能するため、壁にぶつかった分析に進みました。

私はこれに頭を悩ませているので、我慢してください。

部分的な解決策での私の試み:

2 つの比較 (ARG < N1 の場合 & ARG == N1 の場合) には 1 単位の時間がかかります

a1 & m1 & m3 は、再帰呼び出しの外にあるため重要ではありません

a1 + m1* _ = 時間の 1 単位 (加算)

m1* _ = 時間の 1 単位 (乗算)

2 つの再帰呼び出しを合計すると、時間の 1 単位になります

m3* _ = 時間の 1 単位 (乗算)

与えられた指示から、両方の再帰関数は毎回同じ # を使用して呼び出され、d1 = d2 > 1 であるため、再帰関数が呼び出すすべての連続する数値は最後の数値よりも小さくなります。

したがって、ARG が (n1 と比較して) 大きいほど、基本ケースに到達するのに時間がかかり、結果が大きくなります。では、アルゴリズムは O(ARG) 時間かかりますか?

私が正しい軌道に乗っているかどうかを誰かに知らせていただければ幸いです。ありがとう

4

2 に答える 2

3

再帰呼び出しは次のとおりです。

f(N)= A1 + M1*f(M2*N/D1 - S1) Op M3*f(M4*N/D2 - S2), if N > N1

と

s1 = s2 = 0
m2 = m4 = 1
d1 = d2 > 1

我々は持っています

f(N)= A1 + M1*f(N/D1) Op M3*f(N/D1), if N > N1

再帰呼び出しは、漸近的な複雑さを取得するための重要なポイントであり、残りは「単なる」定数です。

したがって、ポイントは次のような T を見つけることです。

T(n)=2*T(n/D)

T(n) を見つけたら、Recursion_Plus の呼び出し回数を取得します。漸近的な複雑さについて話しているので、最後の呼び出し (つまりn<N1) を気にする必要はありません。

ここでは数学について説明します。ここでは正式な解決策については説明しませんが、少しの直感で結果を得ることができます。

T の各呼び出しは、T の 2 つの呼び出しを誘発しますが、D による # 除算を使用し、次に D^2 による # 除算を使用して 4 つの呼び出しを行います ...

複雑さは2^(logD(n))（logD(n)=ln(N)/ln(D) )

具体的事例 ：with D=2, the complexity is n

于 2013-09-30T16:25:08.160 に答える
0

再帰の各レベルで関数を 2 回呼び出すことに注意してください。したがって、最初の呼び出しからc1自分自身を 2 回呼び出します:c21とc22、次にそれらの呼び出しのそれぞれから、自分自身を 2 回呼び出します: c211、c212、c221、c222など。再帰の各レベルで、さらに 2 回呼び出します。N レベルでは 2^n 回の呼び出しがあるため、指数関数的に複雑になります。

編集：申し訳ありませんが、悪いです。そこで論点が分かれていることに気づきませんでした。その場合、N レベルは存在せず、log d (N) のみが存在し、残りは Tony が書いたとおりです。

于 2013-09-30T04:01:42.520 に答える