-3

私はテストのために勉強していて、この質問に出くわしました.私はこのコースがあまり得意ではなく、完全に困惑しています. 助けていただければ幸いです。

時間 O(n) で実行されるアルゴリズム isprime(n) にアクセスできるとします (たとえば、n 未満のすべての数で割り切れる可能性を力ずくでチェックします)。次のコードは、入力引数以下の素数の数を計算します。

boolean numprimes(int n) {
    if (n == 1) {
        return 0;
    } else if (isprime(n)) {
        return numprimes(n − 1) + 1;
    } else {
        return numprimes(n − 1);
    }
}

目標は、num 素数の実行時間を分析することです。次の手順を実行して、この目標を達成します。

(a) サイズ n のインスタンスでのアルゴリズムの実行時間 T (n) の再帰的定義を記述します。

(b) T (n) の再帰的な定義を解いて、置換を繰り返し、推測を行い、推測を帰納法で証明し、最後に推測に基づいて閉じた from を演繹する方法を使用して閉形式を取得します。または、反復置換を使用して閉形式を推測し、帰納法によって閉形式が正しいことを証明することもできます。

どうもありがとう、私は本当に助けに感謝します!

4

2 に答える 2

1

a) 素数のテストは O(n) 時間で実行されるため、再帰は次のようになります。

T(n) = T(n-1) + O(n)

b) 部分 a が解決されたので、残りは十分に簡単なはずです。これを解決するためにあなたが何をしたかを教えていただければ、さらにお手伝いできます。

于 2013-10-16T01:59:36.270 に答える
1

ヒントとして、再発は次のようになります。

T(1) = 1

T(n) = T(n - 1) + O(n)

これが成り立つのは、( size の入力に対してn - 1) 常に 1 つの再帰呼び出しが行われ、個々の呼び出しが O(n) の作業を行うためです。

これを次のように書き換えると

T(1) ≤ 1

T(n) ≤ T(n - 1) + kn

反復を開始できます。ヒントとして、最終結果は O(n 2 );になるはずです。詳細はお任せします。

お役に立てれば！

于 2013-10-16T01:59:36.777 に答える