Я получил эту формулу из структуры данных книга в алгоритме сортировки пузырьков.Что является доказательством (N-1) + (N-2) + (N-3) + ... + 1 = N * (N-1)/2
Я знаю, что мы (n-1) * (n раз), но почему деление на 2?
Может ли кто-нибудь объяснить это мне или дать подробное доказательство этого.
Спасибо
См triangle numbers.
Спасибо Мне понравились эти методы, объясняющие доказательство этой формулы, особенно метод номер три, который может можно найти по адресу http://betterexplained.com/articles/techniques-for-adding-the-numbers-1-to-100/ – skystar7
Попробуйте сделать пары чисел из набора. Первый + последний; второй + предыдущий. Это означает n-1 + 1; n-2 + 2. Результат всегда равен n. И поскольку вы добавляете два числа вместе, есть только (n-1)/2 пары, которые могут быть сделаны из (n-1) чисел.
Так что, как (N-1)/2 * Н.
Сумма арифметической прогрессии
(А1 + AN)/2 * N = (1 + (N-1))/2 * (N-1) = N * (N-1)/2
Я знаю, что мы (n-1) * (n раз), но почему деление на 2?
Это только (n - 1) * n, если вы используете наивный пузырь. Вы можете получить значительную экономию, если вы обратите внимание на следующее:
После каждого сравнения и замены, наибольший элемент вы столкнулись будет в последнем месте вы были в.
После первого прохода наибольший элемент будет находиться в последнем положении; после k th pass, k th наибольший элемент будет в k th последняя позиция.
Таким образом, вы не должны сортировать все это дело каждый раз: вам нужно только сортировать п - 2 элементов во второй раз через, п - 3 элемента в третий раз, и так далее. Это означает, что общее количество сравнений/свопов, которые вам нужно сделать, это (n - 1) + (n - 2) + .... Это arithmetic series, и уравнение для общего количества раз (п - 1) * п/2.
Пример: если размер списка является N = 5, то вы делаете 4 + 3 + 2 + 1 = 10 свопов - и обратите внимание, что 10 совпадает с 4 * 5/2.
Но также написано, что n (n - 1)/2 или O (n^2) или n^2. Таким образом, квадрат n i.e квадрат 5 равен 25. Но n (n-1)/2 равно 10. Так как это возможно? – Harinder
@Harinder: "или O (n^2) или n^2 ...". Нет, O (n^2) == n^2 неверно. 'n^2 + 1,000,000' также является« O (n^2) », но явно не равно« n^2 ». –
Это то, чего я не понимаю. Например, посмотрите на это http://www.sparknotes.com/cs/sorting/bubble/section1.rhtml. В конце также говорится, что средний и худший случай n^2 – Harinder
(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.
Предположим, что n = 2. Тогда с левой стороны имеем 2-1 = 1 и 2 * 1/2 = 1 с правой стороны.
Обозначим f (n) = (n-1) + (n-2) + (n-3) + ...+1
Теперь предположим, что мы проверили до n = k. Тогда мы должны проверить для n = k + 1.
на левой стороне мы имеем к + (к-1) + (к-2) + ... + 1, так что е (к) + к
На правой стороне мы тогда имеем (к +1) * k/2 = (k^2 + k)/2 = (k^2 + 2k - k)/2 = k + (k-1) k/2 = k f (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.
«Предположим, что P (N) верно для всех естественных N". Это не правильное доказательство по индукции. Вы пытаетесь доказать, что P (N) => P (N + 1), поэтому вы должны предположить, что P (N) истинно для * some * N. Если вы принимаете его для * all * N, то вы задаете вопрос , –
Это довольно распространенное доказательство. Один из способов доказать это - использовать математическую индукцию. Вот ссылка: http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html
Начать с треугольником ...
*
**
***
****
, представляющий 1 + 2 + 3 + 4 до сих пор. Разрежьте треугольник пополам по одному измерению ...
*
**
* **
** **
Поверните меньшую часть на 180 градусов, и вставить его на вершине большей части ...
**
*
*
**
**
**
Закройте зазор, чтобы получить прямоугольник.
На первый взгляд это работает только в том случае, если основание прямоугольника имеет четную длину, но если оно имеет нечетную длину, вы просто сокращаете средний столбец пополам - он по-прежнему работает с полуобъемной шириной в два раза, (по-прежнему целая область) на одной стороне вашего прямоугольника.
Независимо от основания треугольника ширина вашего прямоугольника (base/2) и высота (base + 1), что дает ((base + 1) * base)/2.
Однако мой base является вашим n-1, так как сортировка пузырьков сравнивает пару элементов за раз и поэтому выполняет итерацию только (n-1) позиций для первого цикла.
http://mathoverflow.net/ –
... предназначен только для математических вопросов на уровне исследований. – rjh
@PascalThivent: этот вопрос будет закрыт в течение нескольких секунд на mathoverflow. – sepp2k