什么是(N-1)+(N-2)+(N-3)+ ... + 1 = N*(N-1)/ 2的证明

Question

我从气泡排序算法的数据结构书中得到了这个公式.

我知道我们是(n-1)*(n次),但为什么除以2？

任何人都可以向我解释这个或给出详细的证据.

谢谢

Answer 1

从三角形开始......

    *
   **
  ***
 ****

到目前为止代表1 + 2 + 3 + 4.沿着一个维度将三角形切成两半......

     *
    **
  * **
 ** **

将较小的部分旋转180度,并将其粘在较大部分的顶部......

    **
    * 

     *
    **
    **
    **

缩小间隙以获得矩形.

乍一看,这只有在矩形底部长度均匀的情况下才有效 - 但如果它有一个奇怪的长度,你只需将中间一列切成两半 - 它仍然适用于半单位宽度的两倍高(矩形的一边是条整数区域.

无论三角形的底部是什么,矩形的宽度(base / 2)和高度都是(base + 1)给定的((base + 1) * base) / 2.

但是,我base是你的n-1,因为冒泡排序一次比较一对项目,因此只迭代第一个循环的(n-1)个位置.

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

Answer 3

尝试从集合中制作成对的数字.第一个+最后一个; 第二个+前一个.这意味着n-1 + 1; n-2 + 2.结果总是n.由于您要将两个数字相加,因此只有(n-1)/ 2对可以由(n-1)个数组成.

所以就像(N-1)/ 2*N.

Answer 4

查看三角形数字.

Answer 5

我知道我们是 (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 相同。