Как получается формула N*(N-1) / 2?

Question

[Qubc]

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

9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45
Когда я смотрю на эти цифры, то я вижу арифметическую прогрессию. Следовательно, я вижу задачу как "найти n-ый член последовательности". Далее, я вспоминаю формулу суммы n-членов арифметической прогрессии (которая выводится через произведение полусуммы крайних членов):
S = (a_1 + a_n)*n/2

Но правильный ответ это:
(N–1) + (N–2) + (N–3) + ... + 1 = N*(N–1)/2

В чём моя ошибка?

Comments

[Lynn «Кофеман»]

> Следовательно, я вижу задачу как "найти n-ый член последовательности".

Тут я потерял нить рассуждений.

В любом случае, а что есть N?

Answer 1

[Wataru]

Ну вы подставьте в формулу число. Допустим, N=3: 1+2+3 = 6. N(N-1)/2= 3*2/2 = 3. Не сходится!
Правильная формула, все-таки N(N+1)/2.

А разница в том, что в учебнике получается сумма от 1 до N-1. Т.е. в формулу прогрессии от 1 до N надо подставить N-1. Вот и получается (N-1)(N-1+1)/2 = (N-1)N/2

Comments

[Qubc]

Спасибо, я так и попробовал, но подумал что это очень странно. Казалось, есть более правильный подход. Спасибо.

Answer 2

[code_panik]

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