Каково доказательство (N–1) + (N–2) + (N–3) + + 1= N*(N–1)/2

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

(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.

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

    *
   **
  ***
 ****

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

     *
    **
  * **
 ** **

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

    **
    * 

     *
    **
    **
    **

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

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

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

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

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

Так что это как (N-1)/2 * N.

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

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

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

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

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

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

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

(A1+AN)/2*N = (1 + (N-1))/2*(N-1) = N*(N-1)/2

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

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

Вот доказательство по индукции с учетом 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.