Что является доказательством (N-1) + (N-2) + (N-3) +... + 1 = N * (N-1)/2

Ответ 1

Смотрите числа треугольников.

Ответ 2

Начните с треугольника...

    *
   **
  ***
 ****

представляющий 1 + 2 + 3 + 4. Сократите треугольник пополам по одному измерению...

     *
    **
  * **
 ** **

Поверните меньшую часть на 180 градусов и вставьте ее поверх большей части...

    **
    * 

     *
    **
    **
    **

Закройте промежуток, чтобы получить прямоугольник.

На первый взгляд это работает только в том случае, если основание прямоугольника имеет четную длину, но если он имеет нечетную длину, вы просто сокращаете средний столбец пополам - он по-прежнему работает с половинной шириной в два раза -tall (все еще целая область) на одной стороне вашего прямоугольника.

Независимо от основания треугольника ширина вашего прямоугольника (base / 2), а высота - (base + 1), давая ((base + 1) * base) / 2.

Однако мой base является вашим n-1, так как сортировка пузырьков сравнивает пару элементов за раз и, следовательно, выполняет итерацию только (n-1) позиций для первого цикла.

Ответ 3

Попробуйте сделать пары чисел из набора. Первый + последний; второй + предыдущий. Это означает n-1 + 1; n-2 + 2. Результат всегда равен n. И поскольку вы добавляете два числа вместе, есть только (n-1)/2 пары, которые могут быть сделаны из (n-1) чисел.

Итак, это как (N-1)/2 * N.

Ответ 4

(N-1) + (N-2) +...+ 2 + 1 представляет собой сумму элементов N-1. Теперь измените порядок элементов так, чтобы после первого числа было последним, затем вторым, затем вторым, а затем (N-1) + 1 + (N-2) + 2 +... Порядок упорядочения элементов теперь показывает, что каждая из этих пар равна N (N-1 + 1 - N, N-2 + 2 - N). Поскольку существует N-1 элементов, существует (N-1)/2 таких пар. Таким образом, вы добавляете N (N-1)/2 раза, поэтому общее значение N*(N-1)/2.

Ответ 5

Я знаю, что мы (n-1) * (n раз), но почему деление на 2?

Это только (n - 1) * n, если вы используете наивный bubblesort. Вы можете получить значительную экономию, если заметите следующее:

• После каждого сравнения и замены наибольший элемент, с которым вы столкнулись, будет находиться в последнем месте, где вы были.

• После первого прохода наибольший элемент будет в последней позиции; после прохождения k ^th наибольший элемент k ^th будет находиться в последней позиции k ^th.

Таким образом, вам не нужно сортировать все это каждый раз: вам нужно только отсортировать n - 2 элемента во второй раз, n - 3 элемента в третий раз и т.д. Это означает, что общее количество сравнений/свопов, которые вам нужно сделать, это (n - 1) + (n - 2) + .... Это арифметическая серия, а уравнение для общего количества раз (n - 1) * n/2.

Пример:, если размер списка равен N = 5, тогда вы делаете 4 + 3 + 2 + 1 = 10 свопов - и обратите внимание, что 10 совпадает с размером 4 * 5/2.

Ответ 6

Это довольно распространенное доказательство. Один из способов доказать это - использовать математическую индукцию. Вот ссылка: http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html

Ответ 7

Сумма арифметической прогрессии

Ответ 8

Предположим, что n = 2. Тогда мы имеем 2-1 = 1 в левой части и 2 * 1/2 = 1 с правой стороны.

Обозначим f (n) = (n-1) + (n-2) + (n-3) +... + 1

Предположим, что мы проверили до n = k. Тогда мы должны проверить для n = k + 1.

в левой части имеем k + (k-1) + (k-2) +... + 1, поэтому f (k) + k

В правой части мы имеем (k + 1) * k/2 = (k ^ 2 + k)/2 = (k ^ 2 + 2k - k)/2 = k + (k-1) k/2 = kf (k)

Таким образом, это необходимо для каждого k, и это завершает доказательство.

Ответ 9

Здесь доказательство по индукции, учитывая члены N, но это то же самое для N - 1:

Для N = 0 формула, очевидно, истинна.

Предположим, что 1 + 2 + 3 + ... + N = N(N + 1) / 2 истинно для некоторого естественного N.

Мы докажем, что 1 + 2 + 3 + ... + N + (N + 1) = (N + 1)(N + 2) / 2 также верно, используя наше предыдущее предположение:

1 + 2 + 3 + ... + N + (N + 1) = (N(N + 1) / 2) + (N + 1) = (N + 1)((N / 2) + 1) = (N + 1)(N + 2) / 2.

Таким образом, формула выполняется для всех N.