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

The summation has n/2+1 terms; i=0 is the first term and i=n/2 is the last one!

So you should have

summation(n) = (n/2+1) (n+n)/2

and

summation(f(x)) = (n/2+1) (0+n)/2.

于 2012-04-15T06:03:37.827 回答