Попытка подсчитать количество операций в коде - PullRequest
0 голосов
/ 13 марта 2020

Я недавно читал Книгу алгоритмов Седжвика, и я наткнулся на пример, который я не совсем понимаю ...

The code in question

Использование этого В коде Седжвик упоминает, что оператор if выполняется точно N x (N-1) (N-2) / 6 раз .

Я не совсем понимаю, почему это так ... Я вижу, что есть тройные вложенные циклы, каждый с верхней границей, которая увеличивается, но почему значение делится на шесть?

1 Ответ

4 голосов
/ 13 марта 2020

Я прошу вас понять, что я не очень хорош в математике, поэтому объяснение может быть немного глупым.

Для того, чтобы 'if(a[i] + j[i] + k[i]) оператор' внутри кода был выполнен Переменные i, j, и k, которые указывают индекс массива 'a' в Tripple для l oop, должны соответствовать условию оператора (0<= i <j<k <N), верно?

Например, N равно 4. enter image description here Кажется, что оно доступно через перестановку (4P3 = 4 ^ 3), которая выбирает три из четырех, но если 4 выбрано в «i», как показано на рисунке выше, вы можете видеть, что прогресс заблокирован в «j» для -l oop (j = 4 + 1; j <4; j ++). </p>

Итак, мы можем не получите число раз, когда оператор if будет выполняться с простой последовательностью.

Нам нужна комбинация ( nCr ) .

Когда индекс переходит от 0 к N-1, число случаев (i, j, k), которые удовлетворяют i < j < k (=> если оператор может выполняться), можно получить по формуле nC3.

enter image description here Согласно этой формуле, если выражение равно , выполнить точно N x (N-1) (N-2) / 6 раз

Я надеюсь, вы понимаете это ну, а если нет, пожалуйста, оставьте комментарий! Хорошего дня!

...