Apa bukti dari (N–1) + (N–2) + (N–3) + + 1= N*(N–1)/2 [ditutup]

Rumus ini saya dapatkan dari buku struktur data pada algoritma bubble sort.

Saya tahu kita (n-1) * (n kali), tapi mengapa dibagi 2?

Adakah yang bisa menjelaskan hal ini kepada saya atau memberikan bukti rincinya.

Terima kasih


formula proof
person skystar7    schedule 20.03.2010    source sumber
comment
mathoverflow.net   -  person Pascal Thivent    schedule 20.03.2010
comment
...hanya untuk soal matematika tingkat penelitian.   -  person rjh    schedule 20.03.2010
comment
@PascalThivent: Pertanyaan ini akan ditutup dalam hitungan detik pada mathoverflow.   -  person sepp2k    schedule 20.03.2010
comment
@Stephan, begitulah rumusnya jika N ditambahkan di sebelah kiri. Jika tidak, berarti N hilang, jadi 2N harus dikurangi pada pembilangnya.   -  person Johannes Schaub - litb    schedule 20.03.2010
comment
Diluar topic? - apakah analisis algoritma tidak ada hubungannya dengan pemrograman? Seperti yang dikatakan Skystar, konteksnya adalah analisis suatu algoritma.   -  person Steve314    schedule 20.03.2010
comment
Karena salah satu cara cepat menjumlahkan angka adalah dengan membuat daftar angka secara menaik, lalu di bawahnya menurun. Anda menyadari sepanjang waktu Anda menjumlahkan N+1 (pasangan pertama 1,n, pasangan kedua 2,n-1...) n kali. Oleh karena itu n*(n+1). Anda sebenarnya telah menjumlahkan semua angka dua kali, jadi Anda membaginya menjadi dua untuk mendapatkan jawabannya.   -  person    schedule 20.03.2010
comment
@rjh @sepp2k Maaf, lupakan apa yang saya katakan.   -  person Pascal Thivent    schedule 20.03.2010
comment
Itu terlalu mendasar untuk mathoverflow.net; itu dianggap Matematika tingkat A/mungkin GCSE di Inggris.   -  person    schedule 20.03.2010
comment
Stephan202: Hanya jika serialnya dimulai pada n.   -  person Ken    schedule 20.03.2010
comment
Wow, saya sangat keberatan dengan penutupan ini.   -  person Steven Oxley    schedule 20.03.2010
comment
@litb, @Ken: Anda benar. Saya tidak mengamati bahwa N itu sendiri tidak disertakan (biasanya demikian, dengan pernyataan masalah ini). Doh!   -  person Stephan202    schedule 20.03.2010
comment
Ini pada intinya adalah pertanyaan matematika. Pada dasarnya identitas aljabar. Itu tidak mematikannya sebagai topik SO, tapi tolok ukur pribadi saya untuk pertanyaan matematika yang termasuk dalam SO adalah Apakah matematika akan dilakukan oleh suatu program atau akankah matematika diterjemahkan ke dalam kode? Dalam hal ini jawabannya adalah Tidak, jadi saya juga akan memilih untuk menutup topik. YMMV.   -  person dmckee --- ex-moderator kitten    schedule 21.03.2010
comment
Apakah kamu aku?!?! Saya baru saja mencari ini, kata-kata Anda persis seperti yang saya pikirkan :D   -  person yuudachi    schedule 25.05.2010
comment
math.stackexchange.com   -  person phuclv    schedule 06.05.2017

Jawaban (9)


arrow_upward
7
arrow_downward

Lihat bilangan segitiga.

person Viral Shah    schedule 20.03.2010
comment
Terima kasih saya menyukai teknik ini dalam menjelaskan pembuktian rumus ini terutama teknik nomor tiga, yang dapat ditemukan di betterexplained.com/articles/ - person skystar7; 21.03.2010

arrow_upward
27
arrow_downward

(N-1) + (N-2) +...+ 2 + 1 adalah jumlah dari N-1 item. Sekarang susun ulang item-itemnya sehingga setelah item pertama muncul item terakhir, lalu item kedua, lalu item kedua hingga terakhir, yaitu (N-1) + 1 + (N-2) + 2 +... Cara mengurutkan item sekarang Anda dapat melihat bahwa masing-masing pasangan tersebut sama dengan N (N-1+1 adalah N, N-2+2 adalah N). Karena ada N-1 item, maka ada (N-1)/2 pasangan tersebut. Jadi Anda menambahkan N (N-1)/2 kali, sehingga nilai totalnya adalah N*(N-1)/2.

person sepp2k    schedule 20.03.2010

arrow_upward
24
arrow_downward

Mulailah dengan segitiga...

    *
   **
  ***
 ****

mewakili 1+2+3+4 sejauh ini. Potong segitiga menjadi dua sepanjang satu dimensi...

     *
    **
  * **
 ** **

Putar bagian yang lebih kecil 180 derajat, dan tempelkan di atas bagian yang lebih besar...

    **
    * 

     *
    **
    **
    **

Tutup celahnya untuk mendapatkan persegi panjang.

Pada pandangan pertama ini hanya berfungsi jika alas persegi panjang memiliki panjang genap - tetapi jika panjangnya ganjil, Anda cukup memotong kolom tengah menjadi dua - ini masih berfungsi dengan lebar setengah unit dua kali lebih tinggi ( masih bilangan bulat area) strip di satu sisi persegi panjang Anda.

Apapun alas segitiganya, lebar persegi panjang Anda adalah (base / 2) dan tingginya (base + 1), sehingga menghasilkan ((base + 1) * base) / 2.

Namun, base saya adalah n-1 Anda, karena pengurutan gelembung membandingkan sepasang item pada satu waktu, dan oleh karena itu hanya mengulangi posisi (n-1) untuk loop pertama.

person Steve314    schedule 20.03.2010

arrow_upward
8
arrow_downward

Cobalah untuk membuat pasangan angka dari himpunan tersebut. Yang pertama + yang terakhir; yang kedua + yang sebelumnya terakhir. Artinya n-1 + 1; n-2 + 2. Hasilnya selalu n. Dan karena Anda menjumlahkan dua bilangan, hanya ada (n-1)/2 pasangan yang dapat dibuat dari (n-1) bilangan.

Jadi seperti (N-1)/2*N.

person gius    schedule 20.03.2010

arrow_upward
5
arrow_downward

Saya tahu kita (n-1) * (n kali), tapi mengapa dibagi 2?

Hanya (n - 1) * n jika Anda menggunakan bubblesort yang naif. Anda bisa mendapatkan penghematan yang signifikan jika memperhatikan hal berikut:

  • Setelah setiap perbandingan dan pertukaran, elemen terbesar yang Anda temui akan berada di tempat terakhir Anda berada.

  • Setelah lintasan pertama, elemen terbesar akan berada di posisi terakhir; setelah lintasan ke-kth, elemen terbesar ke-kth akan berada di posisi terakhir ke-k.

Jadi Anda tidak perlu mengurutkan semuanya setiap saat: Anda hanya perlu mengurutkan n - 2 elemen untuk kedua kalinya, n - 3 elemen untuk ketiga kalinya, dan seterusnya. Artinya jumlah perbandingan/swap yang harus Anda lakukan adalah (n - 1) + (n - 2) + .... Ini adalah deret aritmatika, dan persamaan jumlah totalnya kali adalah (n - 1)*n / 2.

Contoh: jika ukuran daftarnya adalah N = 5, maka Anda melakukan pertukaran 4 + 3 + 2 + 1 = 10 -- dan perhatikan bahwa 10 sama dengan 4 * 5/2.

person John Feminella    schedule 20.03.2010
comment
Tetapi juga tertulis bahwa n(n - 1)/2 atau O(n^2) atau n^2. Jadi kuadrat n yaitu kuadrat 5 adalah 25. Tapi n(n-1)/2 adalah 10. Jadi bagaimana mungkin? - person Harinder; 15.03.2015
comment
@Harinder: atau O(n^2) atau n^2 .... Tidak, O(n^2) == n^2 tidak benar. n^2 + 1,000,000 juga O(n^2) tetapi jelas tidak sama dengan n^2. - person John Feminella; 15.03.2015
comment
Inilah yang saya tidak mengerti. Misalnya lihat ini sparknotes.com/cs/sorting/bubble/section1.rhtml . Pada akhirnya juga dikatakan bahwa kasus rata-rata dan terburuk adalah n^2 - person Harinder; 15.03.2015
comment
Dan apakah ini benar n(n - 1)/2 atau O(n^2)?? Jika ya, bagaimana jadinya O(n^2) - person Harinder; 15.03.2015
comment
@Harinder: Anda harus mengajukan pertanyaan SO terpisah. Komentar tidak terlalu bagus untuk menjawab sesuatu secara panjang lebar. - person John Feminella; 15.03.2015

arrow_upward
2
arrow_downward

Jumlah perkembangan aritmatika

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

person ShPavel    schedule 20.03.2010

arrow_upward
2
arrow_downward

Ini adalah bukti yang cukup umum. Salah satu cara untuk membuktikannya adalah dengan menggunakan induksi matematika. Berikut tautannya: http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html

person John Kane    schedule 20.03.2010

arrow_upward
1
arrow_downward

Asumsikan n=2. Maka kita memiliki 2-1 = 1 di sisi kiri dan 2*1/2 = 1 di sisi kanan.

Dinyatakan f(n) = (n-1)+(n-2)+(n-3)+...+1

Sekarang asumsikan kita telah menguji hingga n=k. Kemudian kita harus menguji n=k+1.

di sisi kiri kita memiliki k+(k-1)+(k-2)+...+1, jadi f(k)+k

Di sisi kanan kita memiliki (k+1)*k/2 = (k^2+k)/2 = (k^2 +2k - k)/2 = k+(k-1)k/ 2 = kf(k)

Jadi ini harus berlaku untuk setiap k, dan ini menyimpulkan pembuktiannya.

person martiert    schedule 20.03.2010

arrow_upward
0
arrow_downward

Berikut pembuktian dengan induksi, dengan mempertimbangkan suku N, tetapi untuk suku N - 1 sama saja:

Untuk N = 0 rumusnya jelas benar.

Misalkan 1 + 2 + 3 + ... + N = N(N + 1) / 2 benar untuk beberapa N alami.

Kami akan membuktikan 1 + 2 + 3 + ... + N + (N + 1) = (N + 1)(N + 2) / 2 juga benar dengan menggunakan asumsi kami sebelumnya:

1 + 2 + 3 + ... + N + (N + 1) = (N(N + 1) / 2) + (N + 1) = (N + 1)((N / 2) + 1) = (N + 1)(N + 2) / 2.

Jadi rumusnya berlaku untuk semua N.

person IVlad    schedule 20.03.2010
comment
Misalkan P(N) benar untuk semua N alami. Itu bukan pembuktian yang benar dengan induksi. Anda ingin membuktikan P(N) =› P(N+1), jadi Anda harus berasumsi bahwa P(N) benar untuk beberapa N. Jika Anda berasumsi demikian untuk semua< /i> N, lalu kamu bertanya. - person Steve Jessop; 20.03.2010