1

非常によく似た複雑さの例。これらの質問がどのように異なるかを理解しようとしています。試験は明日 :( 複雑さを見つけるための近道はここにあります。

ケース 1:

void doit(int N) { 
   while (N) {
      for (int j = 0; j < N; j += 1) {}
   N = N / 2;   
   }
}

ケース 2:

void doit(int N) { 
   while (N) {
      for (int j = 0; j < N; j *= 4) {}
   N = N / 2;   
   }
}

ケース 3:

void doit(int N) { 
   while (N) {
      for (int j = 0; j < N; j *= 2) {}
   N = N / 2;   
   }
}

どうもありがとう！

4

2 に答える 2

4 
void doit(int N) { 
   while (N) {
     for (int j = 0; j < N; j += 1) {}
   N = N / 2;   
   }
}

この O() を見つけるには、繰り返しごとに N を 2 で除算していることに注意してください。したがって、(あなたの知性を侮辱するためではなく、完全を期すために) ループを通る最後のゼロ以外の反復では、N=1 になります。その前は N=a(2)、その前は N=a(4)... ここで 0< a < N (これらは非包括的境界であることに注意してください)。したがって、このループは合計で log(N) 回実行されます。つまり、N=a2^(floor(log(N))) となる最初の反復を意味します。

なぜ私たちはそれを気にするのですか？さて、それは素敵な閉じた形を持つ幾何級数です:

Sum = \sum_{k=0}^{\log(N)} a2^k = a*\frac{1-2^{\log N +1}}{1-2} = 2aN-a = O(N).

誰かがそのラテックス表記を正しく表示する方法を理解できれば、本当に感謝しています。

于 2012-12-12T06:08:55.800 に答える
3

あなたはすでに番号1への答えを持っています- O(n)@NickOによって与えられたように、ここに別の説明があります。

内側のループの外側の繰り返し回数を T(N) とし、外側のループ回数を とするh。ご了承くださいh = log_2(N)

T(N) = N + N/2 + ... + N / (2^i) + ... + 2 + 1
     < 2N (sum of geometric series)
     in O(N)

番号 3:ですO((logN)^2)

内側のループの外側の繰り返し回数を T(N) とし、外側のループ回数を とするh。ご了承くださいh = log_2(N)

T(N) = log(N) + log(N/2) + log(N/4) + ... + log(1)   (because log(a*b) = log(a) + log(b)
     = log(N * (N/2) * (N/4) * ... * 1)
     = log(N^h * (1 * 1/2 * 1/4 * .... * 1/N))
     = log(N^h) + log(1 * 1/2 * 1/4 * .... * 1/N)    (because log(a*b) = log(a) + log(b))
     < log(N^h) + log(1)
     = log(N^h)                                      (log(1) = 0)
     = h * log(N)                                    (log(a^b) = b*log(a))
     = (log(N))^2                                    (because h=log_2(N))

2号は3号とほぼ同じです。

(2,3: j0 からではなく 1 から始まると仮定します。そうでない場合は、@WhozCraig が決して壊れない理由を示します)

于 2012-12-12T06:41:37.653 に答える