再帰関係を使用してネストされたループの複雑さを判断するテキストのセクションに取り組んでいます。この特定の例では、カウント変数が 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 に等しくなければならないことがわかっています。式を思いつくことができないようです...どんな助けでも大歓迎です!