31

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

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

谁能给我解释一下或给出详细的证明。

谢谢

4

9 回答 9

34

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

于 2010-03-20T17:14:05.600 回答
28

从三角形开始...

    *
   **
  ***
 ****

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

     *
    **
  * **
 ** **

将较小的部分旋转 180 度，然后将其粘在较大的部分上...

    **
    * 

     *
    **
    **
    **

缩小间隙得到一个矩形。

乍一看，这只适用于矩形的底边长度为偶数的情况——但如果它的长度为奇数，你只需将中间的列切成两半——它仍然适用于半单位宽的两倍高（仍然是整数区域）带在矩形的一侧。

无论三角形的底边是什么，矩形的宽度是(base / 2)，高度是(base + 1)，给出((base + 1) * base) / 2.

但是， my baseis your n-1，因为冒泡排序一次比较一对项目，因此在第一个循环中仅迭代 (n-1) 个位置。

于 2010-03-20T17:22:23.940 回答
8

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

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

于 2010-03-20T17:12:15.220 回答
7

见三角形数字。

于 2010-03-20T17:10:20.970 回答
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 相同。

于 2010-03-20T17:13:02.963 回答
2

算术级数之和

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

于 2010-03-20T17:12:51.607 回答
2

这是一个很常见的证明。证明这一点的一种方法是使用数学归纳法。这是一个链接：http: //zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html

于 2010-03-20T17:17:02.670 回答
1

假设 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 = k f(k)

所以这必须对每个 k 成立，这就是证明的结论。

于 2010-03-20T17:15:19.050 回答
0

这是一个归纳证明，考虑到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。

于 2010-03-20T17:16:33.667 回答