[Powered by Google Translate] [Gabung Susun] [Rob Bowden - Universiti Harvard] [Ini adalah CS50. - CS50.TV] Mari kita bercakap tentang apapun merge. Setakat ini anda telah melihat isih gelembung, apapun kemasukan, dan apapun pemilihan. Walaupun saya akan jenis gelombang tangan saya pada apa yang saya maksudkan dengan lebih baik, bergabung apapun amnya melakukan lebih baik daripada mana-mana ini 3 jenis. 

Tetapi sebelum bercakap tentang apapun bergabung, mari kita bercakap tentang penggabungan 2 disusun senarai. Kami akan memanggil proses mengambil 2 disusun senarai, seperti ini, dan membuat senarai tunggal yang disusun daripada mereka - penggabungan senarai. Bagaimana kita boleh melakukan ini? Nah, satu idea adalah untuk hanya berpegang satu senarai ke akhir senarai lain dan kemudian menyusun senarai yang terhasil. 

Walaupun ini berfungsi, ia banyak kerja yang tidak perlu. Kita boleh melakukannya lebih cepat daripada sekadar sorting. Perhatikan bahawa satu idea yang salah adalah untuk hanya mengambil seli cawan setiap dari senarai. Walaupun yang mungkin kelihatan seperti kerja pada mulanya, melakukan bahawa kita berakhir dengan 4, 8, 15, 23, 16 - notis bahawa 16 dan 23 adalah keluar dari tempat. Ini adalah kerana 2 elemen yang sepatutnya muncul berturut-turut dalam senarai digabungkan berada dalam senarai awal yang sama. Kedua-dua 15 dan 16 dalam senarai di sebelah kiri. Helah ini adalah untuk mengambil kesempatan daripada hakikat bahawa kedua-dua senarai sudah disusun. Ini bermakna bahawa jika kita hanya melihat elemen pertama kedua-dua senarai - di sini, 4 dan 8 - salah seorang daripada mereka juga mesti menjadi elemen pertama senarai digabungkan. Nah, mengapa? Kedua-dua senarai ini sudah disusun, dan sebagainya sama ada 4 atau 8 mesti menjadi elemen terkecil apabila kita menggabungkan 2 senarai. Dalam kes ini, yang terkecil ialah 4, jadi kita boleh mengambil 4 dan menjadikan ia elemen pertama senarai digabungkan kami. Sekarang kita terus menggabungkan baki 3 elemen senarai pertama dan 4 elemen senarai kedua. 

Sekali lagi, kita hanya perlu melihat elemen pertama kedua-dua senarai. Yang lebih kecil daripada 2 mesti menjadi elemen kedua senarai digabungkan kami. Masa ini, antara 8 dan 15 yang terkecil ialah 8, dan supaya kita memasukkan sebagai unsur kedua senarai diisih kami. Kita boleh terus membandingkan elemen pertama kedua-dua senarai dan mengeluarkan lebih kecil daripada 2. Perbandingan 15 dan 23, 15 adalah lebih kecil dan supaya elemen ketiga kami. Sekarang membandingkan 16 dan 23, 16 adalah lebih kecil. Jadi itulah elemen keempat. 

Notis bahawa 2 unsur datang dari senarai yang sama dalam satu baris. Ini adalah mengapa senarai digabungkan tidak boleh hanya elemen alternatif dari 2 senarai. Perbandingan 50 dan 23, 23 adalah kecil, jadi kita memilih bahawa. Antara 50 dan 42, 42 adalah lebih kecil. Antara 50 dan 108, 50 adalah lebih kecil. Dan, akhirnya, kita hanya mempunyai 108, jadi ia mesti pergi pada akhir senarai kami. Perhatikan bahawa kita mempunyai bagus, senarai disusun. Setiap kali kita berbanding pertama 2 elemen 2 senarai kita dapat menentukan elemen seterusnya senarai digabungkan. Ini bermakna bahawa jika senarai akhir mengandungi sebanyak n nombor, di mana n di sini ialah 8, maka kita perlu pada kebanyakan perbandingan n untuk mendapatkan semua nombor-nombor tersebut ke tempat yang betul. Algoritma tersebut dikatakan untuk menjalankan dalam masa linear, tetapi jangan bimbang tentang itu di sini. 

Menggunakan algoritma kami untuk bergabung, kita boleh membuat algoritma merge cepat apapun. Jadi, mari kita menetapkan semula senarai kami. Terdapat 2 langkah besar dalam proses merge apapun. Pertama, terus berpecah senarai cawan ke bahagian sehingga kita mempunyai sekumpulan senarai dengan hanya cawan 1 di dalamnya. Jangan bimbang jika senarai mengandungi nombor ganjil dan anda tidak boleh membuat potongan sempurna bersih di antara mereka. Hanya sewenang-wenangnya memilih yang senarai untuk termasuk cawan tambahan. Jadi, mari kita berpecah senarai ini. Sekarang kita mempunyai 2 senarai. Sekarang kita mempunyai 4 senarai. 

Dan sekarang kita mempunyai 8 senarai dengan secawan tunggal dalam setiap senarai. Jadi itulah ia untuk langkah 1. Bagi langkah 2, kita berkali-kali bergabung pasang senarai menggunakan algoritma merge kita belajar sebelum. Menghimpunkan 108 dan 15, kita berakhir dengan senarai 15, 108. Menghimpunkan 50 dan 4, kita berakhir dengan 4, 50. Menghimpunkan 8 dan 42, kita berakhir dengan 8, 42. Dan penggabungan 23 dan 16, kita berakhir dengan 16, 23. Sekarang semua senarai kami adalah saiz 2. Perhatikan bahawa setiap satu daripada 4 senarai diisih. 

Jadi, kita boleh memulakan penggabungan pasang senarai lagi. Menghimpunkan 15 dan 108 dan 4 dan 50 - mula-mula mengambil 4, maka tempoh 15, maka 50, maka 108. Menghimpunkan 8, 42 dan 16, 23, kita mula-mula mengambil 8, kemudian 16, kemudian 23, kemudian 42 orang. Jadi sekarang kita mempunyai hanya 2 senarai saiz 4, setiap yang disusun. Jadi sekarang kita bergabung ini 2 senarai. Mula-mula kita mengambil masa 4. Kemudian kita mengambil 8. Maka kita mengambil 15 dan 16, kemudian 23, kemudian 42, kemudian 50, kemudian 108. Dan kami sudah selesai. Kami kini mempunyai senarai yang disusun. Jadi bagaimana pantas ini, sebenarnya? Dari segi teknikal, apapun merge O (n log n), sedangkan semua apapun gelembung, apapun kemasukan, dan apapun pemilihan adalah O (n ²). Malah, seperti yang anda akan belajar tidak lama lagi, anda tidak akan dapat tampil dengan sejenis yang melakukan lebih baik daripada O (n log n) dalam kes umum. Sekali lagi, jangan bimbang tentang perkara ini tatatanda O besar jika anda tidak pernah melihat lagi. 

Hanya tahu bahawa ini bermakna jika kita mahu untuk menyusun senarai yang benar-benar besar apapun isih gelembung, apapun kemasukan, dan pemilihan yang berpotensi boleh mengambil ketara lagi daripada bergabung apapun. Ia tidak bermakna bahawa apapun merge akan lebih cepat untuk semua senarai atau walaupun untuk senarai mana-mana satu di bawah saiz tertentu. Sebagai contoh, jenis kemasukan mungkin jenis terpantas untuk semua senarai yang lebih kecil daripada 5 elemen. Dalam amalan, apapun merge adalah biasanya lebih cepat untuk senarai sebagai kecil sebagai 50 unsur. 

Tetapi ini kelajuan tambahan tidak datang tanpa harga. Tidak seperti jenis lain, yang mengambil senarai dan mengubah suai senarai di tempat sehingga kita mendapat senarai yang disusun, apapun merge memerlukan beberapa ruang tambahan untuk bergabung 2 senarai bersama-sama. Kita tidak boleh segera menggunakan senarai yang sedang digabungkan untuk menyimpan senarai yang digabungkan kerana kita mungkin mengatasi unsur-unsur yang masih perlu digabungkan. Ruang ini adalah sedikit harga, tetapi ia biasanya tidak munasabah. Dan itulah untuk apapun merge. 

Nama saya adalah Rob Bowden, dan ini adalah CS50. [CS50.TV] - Dan pemilihan apapun. [Ketawa] Oh, mendapat untuk mengambil terlalu kerana saya beralih bagaimana saya membentangkan. Senarai di sebelah kiri. Itu adalah kesilapan menaip. [Misspoke] saya diskrukan sehingga - [Ketawa] Saya tidak tahu apa -