31

この式は、バブル ソート アルゴリズムのデータ構造の本から取得しました。

(n-1) * (n 回) であることはわかっていますが、なぜ 2 で割るのか?

誰か私にこれを説明するか、詳細な証拠を教えてください。

ありがとうございました

4

9 に答える 9

34

(N-1) + (N-2) +...+ 2 + 1N-1 個の項目の合計です。ここで、最初の項目の後に最後、2 番目、最後から 2 番目になるように項目を並べ替えます(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度回転させて、大きいパーツの上に貼り付けて……

    **
    * 

     *
    **
    **
    **

ギャップを閉じて長方形を取得します。

一見すると、これは長方形の底辺の長さが偶数の場合にのみ機能しますが、長さが奇数の場合は、中央の列を半分にカットするだけで、幅が半分で高さが 2 倍 (まだ整数領域) 長方形の片側にストリップします。

三角形の底辺が何であれ、長方形の幅は(base / 2)で、高さはであり(base + 1)、 を与え((base + 1) * base) / 2ます。

ただし、 mybaseは your です。n-1バブル ソートは一度に 1 組の項目を比較するため、最初のループでは (n-1) の位置だけを反復します。

于 2010-03-20T17:22:23.940 に答える
8

セットから数字のペアを作成してみてください。最初 + 最後; 2 番目 + 1 つ前の 1 つ。これは n-1 + 1 を意味します。n-2 + 2。結果は常に n です。また、2 つの数字を足し合わせているので、(n-1) 個の数字から作成できるペアは (n-1)/2 個しかありません。

つまり、(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番目の最後の位置になります。

したがって、毎回すべてをソートする必要はありません。2 回目は n - 2 要素、3 回目は 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

これはかなり一般的な証明です。これを証明する 1 つの方法は、数学的帰納法を使用することです。ここにリンクがあります: 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 に答える