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

Question

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

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

有没有人能给我解释一下或者提供详细的证据。

谢谢

Answer 1

参见triangle numbers。

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)个这样的对(N-1)/2。所以你要把N(N-1)个/2相加，所以总值是N*(N-1)/2。

Answer 3

从三角形开始。

    *
   **
  ***
 ****

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

     *
    **
  * **
 ** **

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

    **
    * 

     *
    **
    **
    **

闭合间隙以获得矩形。

乍一看，只有当矩形的底部有偶数长度时才有效-但如果它有奇数长度，您只需将中间的柱子切成两半-它仍然适用于矩形一侧的两倍高(仍然是整数区域)的半个单位宽的条带。

无论三角形的底边是什么，矩形的宽度都是(base / 2)，高度是(base + 1)，这就是((base + 1) * base) / 2。

然而，我的base是您的n-1，因为冒泡排序一次比较一对项，因此在第一个循环中只迭代(n-1)个位置。