как рассчитать частоту этих блоков алгоритма счетного счета?

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

Каждая часть они делят его в части А, В, С, D и Е. Они сказали, что каждый из них имеет следующую частоту:

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; 
}

источник

2016-03-30 ravelinx

Часть 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, но не можете сказать больше, не делая некоторые предположения о вводе.

источник

2016-03-30 04:29:45

@TedHoop Можете ли вы объяснить, как вы вычислили частичную сумму второго цикла и пришли к ответу? – ravelinx

@ravelinx - Вы имеете в виду 'N * (N-1)/2'? Это классическая сумма арифметической серии. Рассмотрим 0 + 1 + 2 + ... + '(N-1)'. Существуют термины «N», и если вы группируете числа парами с обоих концов (0 и «(N-1)»; 1 и «(N-2)» и т. Д.), То легко видеть, что среднее значение каждая пара является точно '(N-1)/2'. (Вы должны убедить себя, что это работает как для четного, так и для нечетного «N».) Так как существуют значения «N» со средним значением «(N-1)/2', то сумма должна быть« N * (N- 1)/2'. Предположительно, это рассуждение заключается в том, как Карл Гаусс установил формулу арифметических рядов, когда ему было 9 лет. –

@TedHoop да Я понимаю N * (N-1)/2, но тот, который я не понимаю, является (N^3)/6 - (N^2)/2 + N/3, что для цикла isnt сумма от суммы внутренней частоты петли? – ravelinx

как рассчитать частоту этих блоков алгоритма счетного счета?

ответ

Смежные вопросы