(N-1) + (N-2) +...+ 2 + 1 is a sum of N-1 items. Now reorder the items so, that after the first comes the last, then the second, then the second to last, i.e. (N-1) + 1 + (N-2) + 2 +... The way the items are ordered now you can see that each of those pairs is equal to N (N-1+1 is N, N-2+2 is N). Since there are N-1 items, there are (N-1)/2 such pairs. So you're adding N (N-1)/2 times, so the total value is N*(N-1)/2.
但是，我的 base 是您的 n-1，因为冒泡排序一次比较一对项目，因此仅迭代 (n-1) 个位置第一个循环。
Start with the triangle...
*
**
***
****
representing 1+2+3+4 so far. Cut the triangle in half along one dimension...
*
**
* **
** **
Rotate the smaller part 180 degrees, and stick it on top of the bigger part...
**
*
*
**
**
**
Close the gap to get a rectangle.
At first sight this only works if the base of the rectangle has an even length - but if it has an odd length, you just cut the middle column in half - it still works with a half-unit-wide twice-as-tall (still integer area) strip on one side of your rectangle.
Whatever the base of the triangle, the width of your rectangle is (base / 2) and the height is (base + 1), giving ((base + 1) * base) / 2.
However, my base is your n-1, since the bubble sort compares a pair of items at a time, and therefore iterates over only (n-1) positions for the first loop.
Try to make pairs of numbers from the set. The first + the last; the second + the one before last. It means n-1 + 1; n-2 + 2. The result is always n. And since you are adding two numbers together, there are only (n-1)/2 pairs that can be made from (n-1) numbers.
I know that we are (n-1) * (n times), but why the division by 2?
It's only (n - 1) * n if you use a naive bubblesort. You can get a significant savings if you notice the following:
After each compare-and-swap, the largest element you've encountered will be in the last spot you were at.
After the first pass, the largest element will be in the last position; after the kth pass, the kth largest element will be in the kth last position.
Thus you don't have to sort the whole thing every time: you only need to sort n - 2 elements the second time through, n - 3 elements the third time, and so on. That means that the total number of compare/swaps you have to do is (n - 1) + (n - 2) + .... This is an arithmetic series, and the equation for the total number of times is (n - 1)*n / 2.
Example: if the size of the list is N = 5, then you do 4 + 3 + 2 + 1 = 10 swaps -- and notice that 10 is the same as 4 * 5 / 2.
发布评论
评论（9）
(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-1) + (N-2) +...+ 2 + 1is a sum of N-1 items. Now reorder the items so, that after the first comes the last, then the second, then the second to last, i.e.(N-1) + 1 + (N-2) + 2 +... The way the items are ordered now you can see that each of those pairs is equal to N (N-1+1 is N, N-2+2 is N). Since there are N-1 items, there are (N-1)/2 such pairs. So you're adding N (N-1)/2 times, so the total value isN*(N-1)/2.从三角形开始...
到目前为止代表 1+2+3+4。将三角形沿一维切成两半...
将较小的部分旋转 180 度，然后将其粘贴在较大的部分顶部...
缩小间隙以获得一个矩形。
乍一看，只有当矩形的底部长度为偶数时，这才有效 - 但如果它的长度为奇数，你只需将中间的列切成两半 - 它仍然适用于半单位宽两倍高的情况（仍然是整数区域）在矩形的一侧进行条带。
无论三角形的底边是多少，矩形的宽度都是
(base / 2)，高度是(base + 1)，给出((base + 1) * 基) / 2。但是，我的
base是您的n-1，因为冒泡排序一次比较一对项目，因此仅迭代 (n-1) 个位置第一个循环。Start with the triangle...
representing 1+2+3+4 so far. Cut the triangle in half along one dimension...
Rotate the smaller part 180 degrees, and stick it on top of the bigger part...
Close the gap to get a rectangle.
At first sight this only works if the base of the rectangle has an even length - but if it has an odd length, you just cut the middle column in half - it still works with a half-unit-wide twice-as-tall (still integer area) strip on one side of your rectangle.
Whatever the base of the triangle, the width of your rectangle is
(base / 2)and the height is(base + 1), giving((base + 1) * base) / 2.However, my
baseis yourn-1, since the bubble sort compares a pair of items at a time, and therefore iterates over only (n-1) positions for the first loop.尝试从集合中生成数字对。第一个+最后一个；第二个 + 前一个。意思是n-1+1； n-2 + 2。结果始终为 n。由于您要将两个数字相加，因此 (n-1) 个数字只能组成 (n-1)/2 对。
所以它就像 (N-1)/2 * N。
Try to make pairs of numbers from the set. The first + the last; the second + the one before last. It means n-1 + 1; n-2 + 2. The result is always n. And since you are adding two numbers together, there are only (n-1)/2 pairs that can be made from (n-1) numbers.
So it is like (N-1)/2 * N.
请参阅三角形数字。
See triangle numbers.
如果您使用朴素的冒泡排序，则只有
(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 相同。
It's only
(n - 1) * nif you use a naive bubblesort. You can get a significant savings if you notice the following:After each compare-and-swap, the largest element you've encountered will be in the last spot you were at.
After the first pass, the largest element will be in the last position; after the kth pass, the kth largest element will be in the kth last position.
Thus you don't have to sort the whole thing every time: you only need to sort n - 2 elements the second time through, n - 3 elements the third time, and so on. That means that the total number of compare/swaps you have to do is
(n - 1) + (n - 2) + .... This is an arithmetic series, and the equation for the total number of times is (n - 1)*n / 2.Example: if the size of the list is N = 5, then you do 4 + 3 + 2 + 1 = 10 swaps -- and notice that 10 is the same as 4 * 5 / 2.
等差数列之和
(A1+AN)/2*N = (1 + (N-1))/2*(N-1) = N*(N-1)/2
Sum of arithmetical progression
(A1+AN)/2*N = (1 + (N-1))/2*(N-1) = N*(N-1)/2
这是一个很常见的证明。证明这一点的一种方法是使用数学归纳法。这是一个链接： http://zimmer.csufresno.edu/~larryc /proofs/proofs.mathinduction.html
This is a pretty common proof. One way to prove this is to use mathematical induction. Here is a link: http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html
假设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 = kf(k)
所以这必须成立每一个 k，这就结束了证明。
Assume n=2. Then we have 2-1 = 1 on the left side and 2*1/2 = 1 on the right side.
Denote f(n) = (n-1)+(n-2)+(n-3)+...+1
Now assume we have tested up to n=k. Then we have to test for n=k+1.
on the left side we have k+(k-1)+(k-2)+...+1, so it's f(k)+k
On the right side we then have (k+1)*k/2 = (k^2+k)/2 = (k^2 +2k - k)/2 = k+(k-1)k/2 = kf(k)
So this have to hold for every k, and this concludes the proof.
这是一个归纳证明，考虑了
N项，但对于N - 1是相同的：对于
N = 0，公式显然是正确的。假设对于某些自然
N来说，1 + 2 + 3 + ... + N = N(N + 1) / 2成立。我们将使用之前的假设来证明
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。Here's a proof by induction, considering
Nterms, but it's the same forN - 1:For
N = 0the formula is obviously true.Suppose
1 + 2 + 3 + ... + N = N(N + 1) / 2is true for some naturalN.We'll prove
1 + 2 + 3 + ... + N + (N + 1) = (N + 1)(N + 2) / 2is also true by using our previous assumption:1 + 2 + 3 + ... + N + (N + 1) = (N(N + 1) / 2) + (N + 1).= (N + 1)((N / 2) + 1)
= (N + 1)(N + 2) / 2
So the formula holds for all
N.