3

これは私のアルゴリズムのクラスの古い宿題です。私は問題の解決策を持っていますが、試行錯誤を繰り返しても、解決策にたどり着くために正しい方向に考える方法を理解できません。

function h(N) {
    if (N==1) return 3;
    else { 
        sum = 1;
        i = 0;
        while (i < h(N-1))
            sum = sum + i;
            i = i + 1;
        return sum;
   }
}

私によると、h(N-1) は while ループで繰り返し呼び出されるため、while ループは h(N-1) によって返される回数だけ実行する必要があります。それに加えて、while ループ内の関数呼び出し h(N-1) もその回数だけ発生します。したがって、私によれば、次のようなものを取得する必要があります。

T(N) = T(N-1)*H(N-1) + C*H(N-1) + D

ここで、
1. T(N) は実行時間です
。2. T(N-1)*H(N-1) は、h(N-1) への 1 回の再帰呼び出しに T(N-1) がかかるためです。比較が行われるたびに再計算され、H(N-1) 回と呼ばれます。(ここで、H(N-1) は呼び出しから返された値です)
3. C*H(N-1) は while ループ内のステートメントの実行時間です (while ループは H(N-1) を実行するため)。回。

教授から満足のいく回答が得られませんでした。誰かがこれを理解するのを手伝ってくれれば幸いです.

ありがとうございました！

4

2 に答える 2

2

whileこれを2つのステップで理解してみてください。最初に、ループを。に置き換えるこの単純な関数について考えてみましょうif。

function g(N) {
    if (N==1) return 3;
    else { 
        sum = 1;
        i = 0;
        if(i < g(N-1))
            sum = sum + i;
            i = i + 1;
        return sum;
   }
}

ここで、再発が発生します。

G(N) = G(N-1) + O(1)

ここまでは順調ですね？ここで、g（N）を計算する作業には、より小さな問題g（N-1）と一定量の作業を解くことが含まれます。

それでは、元の関数h（N）に戻りましょう。変化したこと？ここで、h（N）を計算する作業には、サブ問題h（N-1）、h（N-1）回の解決が含まれます。そして、それらの各時間（つまり、whileループ）で、一定量の作業を行います。また、h（N）で1回だけ実行される、つまりwhileループの外で実行される一定量の作業もあります。したがって、基本的に次のようになります。

H(N) = H(N - 1) *{H(N - 1) + O(1)}  + O(1)

を代入することで上記を書き換えることができT(n) = H(n) + O(1)ます。したがって、次のようになります。

T(N) = H(N - 1) * T(N - 1)  + O(1)
于 2012-05-13T11:46:08.183 に答える
1

h（N）を実行する際に、h（N-1）の値がループの各反復で再計算されると想定します（これはおそらくほとんどの言語とほとんどのコンパイラーに当てはまります）

ここに画像の説明を入力してください

于 2012-05-12T08:45:43.637 に答える