time - ネストされた for ループの複雑さ

Question

すべてのケース (広告) の成長関数は何ですか?
ネストされた各 for ループの実行時間を見つけるのに苦労しています。それらのいくつかを見つけたと思いますが、よくわかりません。

a)

for(i = 1; i*i <= N; i = 2*i);

b)

for(i = 1; i <= N; i = 2*i);
    for(j = 1; j <= i; j = j+1);

c)

for(i = 1; i*i <= N; i=i+1);
    for(j=1; j <= i ; j=j+1);

d)

for(i = 1; i*i <= N; i=i+1)
    for(j = 1; j <= i ; j = 2*j);

Answer 1

これは私が得たものです：

成長：

1. O(log(sqrt(N)))
2. O(N)
3. O(N)
4. O(log(sqrt(N)!)) = O(sqrt(N)*log(sqrt(N)))スターリングの近似を使用

正確な数値: ([X]は X の整数部分)

1. [log([sqrt(N)])]+1
2. 2^([log(N)]+1)
3. [sqrt(N)]*[sqrt(N)+1]/2
4. よくわかりません。

そして、ここにちょっとしたチェックがあります: カウンタを使って for ループを実装しました。これは for の出力ですN=10000000:

a(N)= 12           a(10*N)= 14
b(N)= 16777216     b(10*N)= 134217728
c(N)= 5000703      c(10*N)= 50005000
d(N)= 33861        d(10*N)= 123631

編集：要求に応じて、説明
まず第一に、いくつかの考慮事項：

• 私たちは整数を扱っているので、あなたが見る（sqrtそしてlog基本的に）実際の関数は、実際には整数部分を取るべきです。
• ほとんどの場合、コンピュータ サイエンスでは、log = log base 2

今：

1. iは 1 からsqrt(N)になりますが、2 の累乗のみを「使用」しますlog(M)。1 と M の間には (実際には +1) 2 の累乗があるM = sqrt(N)ため、式が得られます。

2. i前と同じように、から1までN2 の累乗になります。すべてのためにjsiがあります。iすべての js を合計すると、次のようになりますi。
   1 + 2 + 4 + 8 + 16 + ... + 2^log(N) = 2N - 1 = O(N)

3. iから1までsqrt(N)です。それぞれiにijsがあります。前と同様に、各 の js の数を合計しますi。
   1 + 2 + 3 + 4 + 5 + ... + sqrt(N) = sqrt(N) * sqrt(N+1) / 2 = O(N)

4. iから1までsqrt(N)です。for everyiはjからまで2 の累乗のみ1を使用するため、 jsは for every になります。i ごとにすべての js を合計すると、次のようになります。iilog(i)

   log(1) + log(2) + log(3) + log(4) + log(5) + ... + log(sqrt(N))
   対数の性質についてlog(a) + log(b) = log(a*b)。これを私たちの合計に適用してください:
   log(1*2*3*4*5*..*sqrt(N)) = log( sqrt(N)! )
   これが結果です. 階乗が大きな数の問題であることを考えると、スターリングの近似を使用できますln(N!) -> N*log(N) - N。

整数部分を使用した違いの例

2 を考えてみましょう。 の整数部分は、2 倍log(N)になるまで同じままNです。これは、たとえば、このforサイクルが N=に対して同じ数の操作 ( 131072) を実行することを意味します。（あと1回）になると操作回数が2倍になります（）。N=65536131071N131072262144

Answer 2

シグマ記法を使用して、コード フラグメントを正式に解決できます。

a)

b)

c)

d)