2

次のアルゴリズムがあるとします。

procedure(n)
   if n == 1 then break
   R = generaterandom()
   procedure(n/2)

これで、このアルゴリズムの複雑さはわかりましたが、ランダムジェネレーターlog(n)を呼び出しますか、または呼び出しのために呼び出されないためです.log(n)log(n)-1n==1

これが明らかである場合は申し訳ありませんが、私は周りを見回しており、正確な答えがどこにも述べられていません.

4

2 に答える 2

1

ジェネレーターへの ceil(log(n)) 呼び出しがあります

誘導を使用した証明:

仮説： それぞれのジェネレーターへの呼び出し
がありますceil(log(k))k<n

ベース:
log_2(1) = 0 => 0 回の呼び出し

ステップ:
任意のn>1場合は 1 つの呼び出しがあり、次に仮説からceil(log(n/2)再帰呼び出しでさらに呼び出しがあります。 これにより、呼び出し
の合計が得られますceil(log(n/2))+1 = ceil(log(n/2)) + log(2) = ceil(log(n/2 * 2)) = ceil(log(n))

QED

注: ここでは、すべてのログは基数 2 です。

于 2013-02-22T08:46:43.063 に答える
-1

マスターの定理により、メソッドは T(n) = T(n/2) + O(1) のように記述できます。関数呼び出しごとに n を半分に分割しているためです。これは正確に O(log n) です。-複雑さの分析を求めていないことに気づきましたが、前述したように、考え方は同じです（つまり、呼び出しの数を見つけることはその複雑さに相当します）

于 2013-02-22T09:05:57.883 に答える