0

因此，我从《算法第 4 版》一书中得到了这个计数算法，该算法在算法分析一章中使用，它们计算每个循环的频率，内部循环中的 if 语句和开头的声明。

他们将每个部分分为 A、B、C、D 和 E 部分。他们说每个部分都有以下频率：

E  = X (depends on input)
D = (N^3)/6 - (N^2)/2 + N/3
C = (N^2)/2 - N/2
B = N
A = 1

我知道所有这些频率都来自部分和，但我不明白他们是如何得出每个答案的，如果有人能解释我为什么每个频率都是这样的，我将不胜感激。

public static int count(int[] a)
{
   int N = a.length; // Part A
   int cnt = 0;  // Part A

   for(int i = 0; i < N; i++)  //Part A
      for(int j = i+1; j < N; j++) // Part B
         for(int k = j+1; k < N; k++) // Part C
            if(a[i] + a[j] + a[k] == 0  // Part D
               cnt++; // Part E

   return cnt;
}
4

1 回答 1

0

A 部分应该很明显：前三行执行一次。

B 部分（外循环的主体）为外循环的每次迭代执行一次，总共执行一次N。

C 部分（第二个循环的主体）N - i - 1为外部循环的每次迭代执行次数，i从 0 到N-1. 当你加起来 sum( i=0.. N-1){ i} 你得到N*(N-1)/2or (N^2)/2 - N/2.

D 部分（第三个循环的主体）i - j - 1为第二个循环的每次迭代执行次数，其中i从 0 变化到N-1与之前一样，j从 0 变化到i - 1。当你把这个加起来的时候，你会得到 D 的结果。

E 部分（if语句的主体）从 0（例如，所有a[i]值都是正数）到 D 次（例如，所有a[i]值都为零）执行。因此，您可以在 X 上设置界限，但如果不对输入做出一些假设，就不能说更多。

于 2016-03-30T04:29:45.690 回答