Расчет количества раз, когда выполняется оператор if.

Question

Этот код подсчитывает, сколько целых тройных сумм равно 0: полный код here.

initialise an int array of length n 
int cnt = 0 // cnt is the number of triples that sum to 0 
for (int i = 0; i < n; i++) { 
    for (int j = i+1; j < n; j++) { 
     for (int k = j+1; k < n; k++) { 
      if (array[i]+array[j]+array[k] == 0) { 
       cnt++; 
      } 
     } 
    } 
} 

Теперь из книги алгоритмов Роберт Седжвик, я прочитал, что:

• Инициализация из cnt в 0 выполняется ровно один раз.
• cnt++ выполняется от 0 до количества раз, когда найдена тройка.
• Оператор if выполнен n(n-1)(n-2)/6 раз.

Я сделал несколько экспериментов, и все они верны. Но я полностью не знаю, как они вычисляют количество раз, когда оператор if был выполнен. Я не уверен, но я думаю, что:

• n средство от i to n
• (n-1) средство от i+1 до n
• (n-2) средство от j+1 до n
• /6 Я не знаю, что это это для.

Может кто-нибудь объяснить, как вычислить это?

Answer 1

Это сумма сумм.

1. Внутренний цикл выполняется n-j-1 раз каждый раз, когда он охвачен
2. Средний цикл выполняется n-i-1 раз каждый раз, когда он охвачен
3. Внешний цикл выполняется n раз.

Sum all of these и вы получаете общее количество раз, когда вызывается cnt++.

---

Обратите внимание, что количество раз, средний цикл выполняется каждый раз, когда НЕ n-1, это n-i-1, где i является индекс внешнего цикла. Аналогично для среднего цикла.

Фактор /6 исходит из его учета в формуле суммирования.

Answer 2

В основе этой формулы происходит от суммы прогрессии:

1+2 = 3 
1+2+3 = 6 
1+2+3+4 = 10 

Там существует формулу:

Sum(1..N) == N*(N+1)/2 

1+2+3+4 = 4*5/2 = 10 

с рекурсивной прогрессией (как в данном случае), вы получите другую формулу для сумм.

Answer 3

Это может рассматриваться как проблема combinatorial. Чтобы выбрать 3 уникальных предмета из n предметов (k=3 в связанной статье), вы можете выбрать n!/(n-3)! = n*(n-1)*(n-2). Однако в коде порядок 3 пунктов не имеет значения. Для каждой комбинации из 3 предметов есть 3! = 6 перестановки. Поэтому нам нужно разделить на 6, чтобы получить только бесплатные возможности. Итак, мы получаем n!/(3!(n-3)!) = n(n-1)(n-2)/6

Answer 4

В вашем коде, где i пробегает от 0 до n, j от i до n, k от j до n, оператор if выполняется примерно n^3/6 раз. Чтобы понять, почему это так, посмотрите на этот код, который, очевидно, будет выполнять, если заявление так же, как часто:

int cnt = 0 // cnt is the number of triples that sum to 0 
for (int i = 0; i < n; i++) { 
    for (int j = 0; j < n; j++) { 
     for (int k = 0; k < n; k++) { 
      if (j > i && k > j) { 
       if (array[i]+array[j]+array[k] == 0) { 
        cnt++; 
       } 
      } 
     } 
    } 
} 

Внутренний цикл Теперь, очевидно, выполняет п^3 раза. Оператор if выполняется, если i < j < k. Мы игнорируем случай, когда i == j или i == k или j == k. Три переменные i, j и k могут быть отсортированы в шести разных порядках (i < j < k, i < k < j, j < i < k и т. Д.). Поскольку каждый из этих шести разных порядков сортировки происходит одинаково часто, около n^3/6 раз мы имеем порядок i < j < k.

Answer 5

Первый цикл выполняется для N раз (от 0 до N-1)

Время для выполнения внешнего цикла является:

Fi(0) + Fi(1) + Fi(2)...Fi(N-1) 

Когда i является 0, средний цикл выполняется N-1 раз (от 1 до N- 1)
Когда i является 1, средний цикл выполняется N-2 раз (от 2 до N-1)
...

Время для выполнения среднего цикла составляет:

Fi(0) = Fj(1) + Fj(2) ... Fj(N-1) 
Fi(1) = Fj(2) + Fj(3) ... Fj(N-1) 
Fi(0) + Fi(1) + Fi(2)...Fi(N-1) = Fj(1) + 2Fj(2) + ... (N-1)Fj(N-1) 

теперь к внутренней большей петле:

Когда j является 1, внутренний цикл выполняет N-2 раз (от 2 до N-2)
Когда j является 2, внутренний цикл выполняется N-3 раз (от 3 до N-2)
...

Fj(1) = Fk(2) + Fk(3) ... Fk(N-1) = 2 + 3 + ... N-1 
Fj(2) = Fk(3) + Fk(4) ... Fk(N-1) = 3 + 4 + ... N-1 
Fj(1) + 2Fj(2) + ... (N-1)Fj(N-1) = (2 + 3 + ... N-1) + (3 + 4 + ... N-1) ... (N-1) 
    = 1 x 2 + 2 x 3 + 3 x 4 .... (N-2) x (N-1) 
    = 1x1 + 2x2 + 3x3 + 4x4 .... (N-1)*(N-1) - (1 + 2 + 3 + 4 + N-1) 
    = (N-1) N (N+1)/6 - N (N-1)/2 
    = N (N-1) ((N+1)/2 - 1/2) 
    = N (N-1) (N-2)/6 

Вы также можете проверить: Формула для вычисления суммы квадратов first N natural numbers и суммы first N natural numbers.

---

Альтернативное объяснение:

Вы найти все пары троек. Это можно сделать в ^N C способов. то есть (N) * (N-1) * (N-2)/(1 * 2 * 3) способов.