3

再帰関係を使用してネストされたループの複雑さを判断するテキストのセクションに取り組んでいます。この特定の例では、カウント変数が n の関数としてインクリメントされる回数を決定しようとしています。

これは私が分析しているループです:

for (int i = 1; i <= n; i++) {
     int j = n;
     while (j > 0) {
           count++;
           j = j / 2;
     }
}

最初の行は n の各値に対してのみ実行されるため、単純に n と同等であることは理解していると思いますが、残りの部分で問題が発生しています。答えは n(n/2) のようなものになると思いますが、この例では整数除算を使用しているため、それを数学的に表現する方法がわかりません。

紙の上で何度か手作業でループを実行したので、カウント変数は 1 ～ 6 の n 値に対して 1、4、6、12、15、および 18 に等しくなければならないことがわかっています。式を思いつくことができないようです...どんな助けでも大歓迎です!

4

3 に答える 3

2

ループは fornの範囲で実行されます[1, n]。jn に設定されている変数に対して毎回 2 で除算するため、内側のループが実行される回数はfloor(l2(n)) + 1,、l2 がバイナリログ関数である場合です。1 から n までのすべての値を合計します ( を掛けnます)。

于 2012-11-16T02:31:09.373 に答える
0

内側のjループは、カウントする最初のセット ビットの位置を追加します。

2 で割るたびに、すべてのビットがゼロになるまで右シフトと同じになります。

したがって、2 はバイナリで 10 になり、内側のループの値は 2 になります。4 はバイナリで 100 になり、内部ループの値は 3 になります。

外側のループは、最初に設定されたビットの位置を数値自体で乗算するだけのようです。

これは n = 13 の例です。

バイナリの 13 は 1101 であるため、最初に設定されたビットは位置 4 にあります。

4 * 13 = 52. 52 が最終的な答えです。

于 2012-11-16T02:31:58.317 に答える
0

for (int i = 1; i <= n; i++) {

上部のこのループは、ループを n 回通過します。

 int j = n;
 while (j > 0) {
       count++;
       j = j / 2;
 }

ここでのこのループは、ループ log(n) timesを通過します。毎回 2 で除算しているため、基数 2 の対数であることに注意してください。

したがって、カウントの総数はn * 天井 (log(n))です。

于 2016-11-11T05:01:07.690 に答える