1 00:00:00,000 --> 00:00:02,000 [Powered by Google Translate] [Gabung Susun] 2 00:00:02,000 --> 00:00:04,000 [Rob Bowden - Universiti Harvard] 3 00:00:04,000 --> 00:00:07,000 [Ini adalah CS50. - CS50.TV] 4 00:00:07,000 --> 00:00:09,000 Mari kita bercakap tentang apapun merge. 5 00:00:09,000 --> 00:00:14,000 Setakat ini anda telah melihat isih gelembung, apapun kemasukan, dan apapun pemilihan. 6 00:00:14,000 --> 00:00:17,000 Walaupun saya akan jenis gelombang tangan saya pada apa yang saya maksudkan dengan lebih baik, 7 00:00:17,000 --> 00:00:21,000 bergabung apapun amnya melakukan lebih baik daripada mana-mana ini 3 jenis. 8 00:00:22,000 --> 00:00:27,000 >> Tetapi sebelum bercakap tentang apapun bergabung, mari kita bercakap tentang penggabungan 2 disusun senarai. 9 00:00:27,000 --> 00:00:31,000 Kami akan memanggil proses mengambil 2 disusun senarai, seperti ini, 10 00:00:31,000 --> 00:00:35,000 dan membuat senarai tunggal yang disusun daripada mereka - penggabungan senarai. 11 00:00:35,000 --> 00:00:37,750 Bagaimana kita boleh melakukan ini? 12 00:00:37,750 --> 00:00:41,290 Nah, satu idea adalah untuk hanya berpegang satu senarai ke akhir senarai lain 13 00:00:41,290 --> 00:00:43,830 dan kemudian menyusun senarai yang terhasil. 14 00:00:43,830 --> 00:00:47,220 >> Walaupun ini berfungsi, ia banyak kerja yang tidak perlu. 15 00:00:47,220 --> 00:00:49,900 Kita boleh melakukannya lebih cepat daripada sekadar sorting. 16 00:00:49,900 --> 00:00:54,100 Perhatikan bahawa satu idea yang salah adalah untuk hanya mengambil seli cawan setiap dari senarai. 17 00:00:54,100 --> 00:00:56,460 Walaupun yang mungkin kelihatan seperti kerja pada mulanya, 18 00:00:56,460 --> 00:01:05,760 melakukan bahawa kita berakhir dengan 4, 8, 15, 23, 16 - notis bahawa 16 dan 23 adalah keluar dari tempat. 19 00:01:05,760 --> 00:01:09,380 Ini adalah kerana 2 elemen yang sepatutnya muncul berturut-turut dalam senarai digabungkan 20 00:01:09,380 --> 00:01:11,720 berada dalam senarai awal yang sama. 21 00:01:11,720 --> 00:01:14,850 Kedua-dua 15 dan 16 dalam senarai di sebelah kiri. 22 00:01:14,850 --> 00:01:19,810 Helah ini adalah untuk mengambil kesempatan daripada hakikat bahawa kedua-dua senarai sudah disusun. 23 00:01:19,810 --> 00:01:23,320 Ini bermakna bahawa jika kita hanya melihat elemen pertama kedua-dua senarai - 24 00:01:23,320 --> 00:01:29,580 di sini, 4 dan 8 - salah seorang daripada mereka juga mesti menjadi elemen pertama senarai digabungkan. 25 00:01:29,580 --> 00:01:31,620 Nah, mengapa? 26 00:01:31,620 --> 00:01:33,520 Kedua-dua senarai ini sudah disusun, 27 00:01:33,520 --> 00:01:38,410 dan sebagainya sama ada 4 atau 8 mesti menjadi elemen terkecil apabila kita menggabungkan 2 senarai. 28 00:01:38,410 --> 00:01:41,770 Dalam kes ini, yang terkecil ialah 4, 29 00:01:41,770 --> 00:01:46,370 jadi kita boleh mengambil 4 dan menjadikan ia elemen pertama senarai digabungkan kami. 30 00:01:46,370 --> 00:01:50,710 Sekarang kita terus menggabungkan baki 3 elemen senarai pertama 31 00:01:50,710 --> 00:01:52,920 dan 4 elemen senarai kedua. 32 00:01:52,920 --> 00:01:57,150 >> Sekali lagi, kita hanya perlu melihat elemen pertama kedua-dua senarai. 33 00:01:57,150 --> 00:02:01,060 Yang lebih kecil daripada 2 mesti menjadi elemen kedua senarai digabungkan kami. 34 00:02:01,060 --> 00:02:05,440 Masa ini, antara 8 dan 15 yang terkecil ialah 8, dan supaya kita memasukkan 35 00:02:05,440 --> 00:02:09,240 sebagai unsur kedua senarai diisih kami. 36 00:02:09,240 --> 00:02:12,180 Kita boleh terus membandingkan elemen pertama kedua-dua senarai 37 00:02:12,180 --> 00:02:14,420 dan mengeluarkan lebih kecil daripada 2. 38 00:02:14,420 --> 00:02:19,460 Perbandingan 15 dan 23, 15 adalah lebih kecil dan supaya elemen ketiga kami. 39 00:02:21,000 --> 00:02:23,910 Sekarang membandingkan 16 dan 23, 16 adalah lebih kecil. 40 00:02:23,910 --> 00:02:26,820 Jadi itulah elemen keempat. 41 00:02:26,820 --> 00:02:30,390 >> Notis bahawa 2 unsur datang dari senarai yang sama dalam satu baris. 42 00:02:30,390 --> 00:02:34,400 Ini adalah mengapa senarai digabungkan tidak boleh hanya elemen alternatif dari 2 senarai. 43 00:02:34,400 --> 00:02:40,020 Perbandingan 50 dan 23, 23 adalah kecil, jadi kita memilih bahawa. 44 00:02:40,770 --> 00:02:44,070 Antara 50 dan 42, 42 adalah lebih kecil. 45 00:02:44,070 --> 00:02:48,290 Antara 50 dan 108, 50 adalah lebih kecil. 46 00:02:48,290 --> 00:02:52,330 Dan, akhirnya, kita hanya mempunyai 108, jadi ia mesti pergi pada akhir senarai kami. 47 00:02:53,750 --> 00:02:56,180 Perhatikan bahawa kita mempunyai bagus, senarai disusun. 48 00:02:56,180 --> 00:02:59,040 Setiap kali kita berbanding pertama 2 elemen 2 senarai 49 00:02:59,040 --> 00:03:02,730 kita dapat menentukan elemen seterusnya senarai digabungkan. 50 00:03:02,730 --> 00:03:08,070 Ini bermakna bahawa jika senarai akhir mengandungi sebanyak n nombor, di mana n di sini ialah 8, 51 00:03:08,070 --> 00:03:12,610 maka kita perlu pada kebanyakan perbandingan n untuk mendapatkan semua nombor-nombor tersebut ke tempat yang betul. 52 00:03:13,230 --> 00:03:16,230 Algoritma tersebut dikatakan untuk menjalankan dalam masa linear, 53 00:03:16,230 --> 00:03:18,090 tetapi jangan bimbang tentang itu di sini. 54 00:03:18,570 --> 00:03:22,810 >> Menggunakan algoritma kami untuk bergabung, kita boleh membuat algoritma merge cepat apapun. 55 00:03:22,810 --> 00:03:25,170 Jadi, mari kita menetapkan semula senarai kami. 56 00:03:35,210 --> 00:03:37,750 Terdapat 2 langkah besar dalam proses merge apapun. 57 00:03:37,750 --> 00:03:41,500 Pertama, terus berpecah senarai cawan ke bahagian 58 00:03:41,500 --> 00:03:44,860 sehingga kita mempunyai sekumpulan senarai dengan hanya cawan 1 di dalamnya. 59 00:03:44,860 --> 00:03:47,350 Jangan bimbang jika senarai mengandungi nombor ganjil 60 00:03:47,350 --> 00:03:49,880 dan anda tidak boleh membuat potongan sempurna bersih di antara mereka. 61 00:03:49,880 --> 00:03:53,750 Hanya sewenang-wenangnya memilih yang senarai untuk termasuk cawan tambahan. 62 00:03:53,750 --> 00:03:56,240 Jadi, mari kita berpecah senarai ini. 63 00:03:58,140 --> 00:04:01,310 Sekarang kita mempunyai 2 senarai. 64 00:04:04,120 --> 00:04:06,570 Sekarang kita mempunyai 4 senarai. 65 00:04:10,350 --> 00:04:13,870 >> Dan sekarang kita mempunyai 8 senarai dengan secawan tunggal dalam setiap senarai. 66 00:04:13,870 --> 00:04:16,630 Jadi itulah ia untuk langkah 1. 67 00:04:16,630 --> 00:04:22,230 Bagi langkah 2, kita berkali-kali bergabung pasang senarai menggunakan algoritma merge kita belajar sebelum. 68 00:04:22,230 --> 00:04:29,160 Menghimpunkan 108 dan 15, kita berakhir dengan senarai 15, 108. 69 00:04:30,330 --> 00:04:36,250 Menghimpunkan 50 dan 4, kita berakhir dengan 4, 50. 70 00:04:36,960 --> 00:04:41,400 Menghimpunkan 8 dan 42, kita berakhir dengan 8, 42. 71 00:04:42,790 --> 00:04:48,130 Dan penggabungan 23 dan 16, kita berakhir dengan 16, 23. 72 00:04:49,740 --> 00:04:52,450 Sekarang semua senarai kami adalah saiz 2. 73 00:04:53,020 --> 00:04:56,180 Perhatikan bahawa setiap satu daripada 4 senarai diisih. 74 00:04:56,180 --> 00:04:59,160 >> Jadi, kita boleh memulakan penggabungan pasang senarai lagi. 75 00:04:59,160 --> 00:05:03,240 Menghimpunkan 15 dan 108 dan 4 dan 50 - 76 00:05:03,240 --> 00:05:11,170 mula-mula mengambil 4, maka tempoh 15, maka 50, maka 108. 77 00:05:11,170 --> 00:05:15,120 Menghimpunkan 8, 42 dan 16, 23, 78 00:05:15,120 --> 00:05:22,440 kita mula-mula mengambil 8, kemudian 16, kemudian 23, kemudian 42 orang. 79 00:05:22,440 --> 00:05:27,370 Jadi sekarang kita mempunyai hanya 2 senarai saiz 4, setiap yang disusun. 80 00:05:27,370 --> 00:05:30,980 Jadi sekarang kita bergabung ini 2 senarai. 81 00:05:30,980 --> 00:05:33,440 Mula-mula kita mengambil masa 4. 82 00:05:33,440 --> 00:05:36,580 Kemudian kita mengambil 8. 83 00:05:36,580 --> 00:05:50,700 Maka kita mengambil 15 dan 16, kemudian 23, kemudian 42, kemudian 50, kemudian 108. 84 00:05:50,700 --> 00:05:52,220 Dan kami sudah selesai. 85 00:05:52,220 --> 00:05:54,900 Kami kini mempunyai senarai yang disusun. 86 00:05:54,900 --> 00:05:57,890 Jadi bagaimana pantas ini, sebenarnya? 87 00:05:57,890 --> 00:06:02,000 Dari segi teknikal, apapun merge O (n log n), 88 00:06:02,000 --> 00:06:07,380 sedangkan semua apapun gelembung, apapun kemasukan, dan apapun pemilihan adalah O (n ²). 89 00:06:07,380 --> 00:06:11,120 Malah, seperti yang anda akan belajar tidak lama lagi, anda tidak akan dapat tampil dengan sejenis 90 00:06:11,120 --> 00:06:14,820 yang melakukan lebih baik daripada O (n log n) dalam kes umum. 91 00:06:14,820 --> 00:06:19,120 Sekali lagi, jangan bimbang tentang perkara ini tatatanda O besar jika anda tidak pernah melihat lagi. 92 00:06:19,120 --> 00:06:23,490 >> Hanya tahu bahawa ini bermakna jika kita mahu untuk menyusun senarai yang benar-benar besar 93 00:06:23,490 --> 00:06:26,820 apapun isih gelembung, apapun kemasukan, dan pemilihan yang berpotensi boleh mengambil 94 00:06:26,820 --> 00:06:29,500 ketara lagi daripada bergabung apapun. 95 00:06:29,500 --> 00:06:33,210 Ia tidak bermakna bahawa apapun merge akan lebih cepat untuk semua senarai 96 00:06:33,210 --> 00:06:36,220 atau walaupun untuk senarai mana-mana satu di bawah saiz tertentu. 97 00:06:36,220 --> 00:06:41,950 Sebagai contoh, jenis kemasukan mungkin jenis terpantas untuk semua senarai yang lebih kecil daripada 5 elemen. 98 00:06:41,950 --> 00:06:47,360 Dalam amalan, apapun merge adalah biasanya lebih cepat untuk senarai sebagai kecil sebagai 50 unsur. 99 00:06:47,360 --> 00:06:51,120 >> Tetapi ini kelajuan tambahan tidak datang tanpa harga. 100 00:06:51,120 --> 00:06:54,770 Tidak seperti jenis lain, yang mengambil senarai dan mengubah suai senarai di tempat 101 00:06:54,770 --> 00:06:58,740 sehingga kita mendapat senarai yang disusun, apapun merge memerlukan beberapa ruang tambahan 102 00:06:58,740 --> 00:07:00,900 untuk bergabung 2 senarai bersama-sama. 103 00:07:00,900 --> 00:07:04,690 Kita tidak boleh segera menggunakan senarai yang sedang digabungkan untuk menyimpan senarai yang digabungkan 104 00:07:04,690 --> 00:07:08,880 kerana kita mungkin mengatasi unsur-unsur yang masih perlu digabungkan. 105 00:07:08,880 --> 00:07:13,540 Ruang ini adalah sedikit harga, tetapi ia biasanya tidak munasabah. 106 00:07:13,540 --> 00:07:15,330 Dan itulah untuk apapun merge. 107 00:07:15,330 --> 00:07:18,490 >> Nama saya adalah Rob Bowden, dan ini adalah CS50. 108 00:07:18,490 --> 00:07:20,500 [CS50.TV] 109 00:07:20,500 --> 00:07:24,000 - Dan pemilihan apapun. 110 00:07:24,000 --> 00:07:25,880 [Ketawa] 111 00:07:25,880 --> 00:07:31,480 Oh, mendapat untuk mengambil terlalu kerana saya beralih bagaimana saya membentangkan. 112 00:07:31,480 --> 00:07:35,680 Senarai di sebelah kiri. Itu adalah kesilapan menaip. 113 00:07:35,680 --> 00:07:39,290 [Misspoke] saya diskrukan sehingga - 114 00:07:39,290 --> 00:07:41,190 [Ketawa] 115 00:07:41,190 --> 00:07:44,190 Saya tidak tahu apa -