0

アルゴリズム：

for (int i = 0; i < 2*n; i += 2)  
    for (int j = n; j >i; j--)  
        foo();

foo（）が呼び出された回数を調べたい。 

# of foo() calls for the second loop as i changes:

1st loop:   n - 0
2nd loop:   n - 2
3rd loop:   n - 4
nth loop:   n - f(x); f(x) = last term +2; where f(0) = 0

  Total # calls = Summation(n - f(x)) from [i = 0] to [i = n/2 (where f(x) == n)]
= Summation(n) - summation(f(x))
= (n/2)(n+n)/2 - (n/2)(0 + n)/2
= n^2/2        - n^2/4
= n^2/4

私はすべての作業を行いましたが、私の方程式は常に少しずれた値を示します。

n = 5の場合：記録されたfoo（）呼び出しは9ですが、私の方程式は6
になります。n= 6の場合：記録されたfoo（）呼び出しは16ですが、私の方程式は9になります。

私は何を間違えましたか？

4

2 に答える 2

1

経験的なアプローチがうまく機能する場合もあります。http://codepad.org/zpBDNkujを参照してください。

#include <stdio.h>

int count(int n) {
  int i, j, times = 0;
  for (i = 0; i < 2 * n; i += 2)  
    for (j = n; j > i; j--)  
      times++;
  return times;
}

int main() {
  int i;
  for (i = 0; i < 20; i++)
    printf("%2d%10d\n", i, count(i)); 
  return 0;
}

 0         0
 1         1
 2         2
 3         4
 4         6
 5         9
 6        12
 7        16
 8        20
 9        25
10        30
11        36
12        42
13        49
14        56
15        64
16        72
17        81
18        90
19       100

出力を見ると、T（n）がT（n-1）、T（n-2）などからどのように生成されるかを推測でき、Tの再帰的定義を作成できます。これは次のように見えます。あなたが取ったアプローチ。

出力から直接パターンを理解しようとすることで、より速くクローズに到達できる可能性があります。たとえば、出力から次のことがわかります。

  • nが奇数の場合、T（n）はceil（n / 2）**2です。
  • nが偶数の場合、T（n）は（n / 2）*（n / 2 + 1）

補遺

コードパッドに少し追加しました。http://codepad.org/aEnFZ1Daを参照してください

これは、T（n）が漸近的にn^2/4に収束することを示しています。これはあなたが得た答えと一致します。nの値が小さい場合、正確にn ^ 2/4が表示されなかったため、結果が「ビットオフ」であると言っていた可能性があります。これで結構です。重要なのは、限界では複雑さがn^2/4であるということです。もちろん、THETA（n ^ 2）...とだけ言うこともできます。

于 2012-04-15T05:02:29.127 に答える
0

合計にはn/2+1項があります。i = 0が最初の項で、i = n / 2が最後の項です！

だからあなたは持っているべきです

合計（n）=（n / 2 + 1）（n + n）/ 2

と

summation（f（x））=（n / 2 + 1）（0 + n）/2。

于 2012-04-15T06:03:37.827 に答える