如何计算这个计数算法语句块的频率？

Question

所以我在算法分析一章中使用了算法第 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;
}

Answer 1

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

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

C 部分（第二个循环的主体）在外循环的每次迭代中执行 N - i - 1 次，其中 i 从 0 到 N-1。当你加起来 sum(i=0..N-1){i} 你得到 N*(N-1)/2 或 (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 上设置界限，但如果不对输入做出一些假设就不能说更多。

如何计算这个计数算法语句块的频率？

how to calculate frequency of this count algorithm statement blocks?

algorithm

for-loop

code-complexity