Как рассчитать частоту блоков подсчета алгоритма?

Question

Итак, у меня есть этот алгоритм подсчета из книги Algorithms 4th edition, который используется в главе анализа алгоритмов, в которой они вычисляют частоту каждого цикла, если оператор во внутреннем цикле и из объявлений в начале.

Каждую часть они делят на части 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, Когда вы складываете сумму (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, но не можете сказать больше, не делая некоторых предположений относительно ввода.