1 00:00:00,000 --> 00:00:05,760 2 00:00:05,760 --> 00:00:08,900 >> DOUG LLOYD: Jadi dalam CS50 kita belajar tentang pelbagai menyusun dan mencari 3 00:00:08,900 --> 00:00:09,442 algoritma. 4 00:00:09,442 --> 00:00:11,400 Dan kadang-kadang ia boleh menjadi sedikit rumit untuk menjaga 5 00:00:11,400 --> 00:00:14,161 mengesan apa algoritma tidak apa. 6 00:00:14,161 --> 00:00:15,910 Kami telah benar-benar hanya skim permukaan juga, 7 00:00:15,910 --> 00:00:18,740 terdapat banyak pencarian lain dan menyusun algoritma. 8 00:00:18,740 --> 00:00:21,780 Jadi, dalam video ini mari kita hanya mengambil masa beberapa minit 9 00:00:21,780 --> 00:00:24,980 untuk mencuba dan menyuling setiap algoritma turun kepada unsur-unsur teras 10 00:00:24,980 --> 00:00:27,810 supaya anda boleh ingat yang paling maklumat penting tentang mereka 11 00:00:27,810 --> 00:00:31,970 dan dapat menyatakan dengan jelas perbezaan, jika perlu. 12 00:00:31,970 --> 00:00:34,220 >> Yang pertama adalah jenis pemilihan. 13 00:00:34,220 --> 00:00:38,210 Idea asas di sebalik jenis pemilihan ialah mencari unsur terisih yang paling kecil 14 00:00:38,210 --> 00:00:42,890 dalam array dan tukar dengan unsur terisih pertama array itu. 15 00:00:42,890 --> 00:00:46,620 Kami berkata, kes terburuk yang masa berjalan itu telah n kuasa dua. 16 00:00:46,620 --> 00:00:50,060 Dan jika anda mahu untuk menarik balik mengapa, mengambil yang melihat video jenis pemilihan. 17 00:00:50,060 --> 00:00:54,560 Terbaik-kes masa jangka juga n kuasa dua. 18 00:00:54,560 --> 00:00:58,910 >> Semacam gelembung, idea di sebalik yang satu adalah untuk menukar pasangan bersebelahan. 19 00:00:58,910 --> 00:01:01,730 Jadi itulah kunci yang membantu anda ingat perbezaan di sini. 20 00:01:01,730 --> 00:01:04,920 Pemilihan jenis iaitu, setakat ini, mencari gelembung smallest-- 21 00:01:04,920 --> 00:01:06,790 MENGASINGKAN menukar pasangan bersebelahan. 22 00:01:06,790 --> 00:01:08,710 Kami menukar pasangan bersebelahan elemen jika mereka 23 00:01:08,710 --> 00:01:12,530 adalah daripada perintah, yang berkesan gelembung unsur-unsur yang lebih besar ke kanan, 24 00:01:12,530 --> 00:01:17,060 dan pada masa yang sama ia juga bermula untuk bergerak unsur-unsur yang lebih kecil ke kiri. 25 00:01:17,060 --> 00:01:20,180 The terburuk masa kes jangka semacam gelembung adalah n kuasa dua. 26 00:01:20,180 --> 00:01:23,476 Terbaik-kes masa jangka gelembung jenis adalah n. 27 00:01:23,476 --> 00:01:25,350 Kerana dalam keadaan yang kita tidak actually-- 28 00:01:25,350 --> 00:01:27,141 kita mungkin tidak perlu membuat apa-apa pertukaran pada semua. 29 00:01:27,141 --> 00:01:31,026 Kita hanya perlu membuat satu lulus dalam semua unsur-unsur n. 30 00:01:31,026 --> 00:01:34,600 >> Dalam jenis kemasukan, yang Idea asas di sini beralih. 31 00:01:34,600 --> 00:01:36,630 Itulah kata kunci untuk jenis kemasukan. 32 00:01:36,630 --> 00:01:39,630 Kita akan melangkah sekali melalui array dari kiri ke kanan. 33 00:01:39,630 --> 00:01:41,670 Dan seperti yang kita lakukan, kita berada akan beralih unsur-unsur 34 00:01:41,670 --> 00:01:46,260 kita telah pun melihat untuk memberi ruang kepada yang lebih kecil yang perlu dimuatkan di suatu tempat 35 00:01:46,260 --> 00:01:48,080 kembali bahawa sebahagian disusun. 36 00:01:48,080 --> 00:01:51,600 Oleh itu, kita membina array disusun satu elemen pada satu masa, kiri ke kanan, 37 00:01:51,600 --> 00:01:54,740 dan kita beralih perkara untuk membuat bilik. 38 00:01:54,740 --> 00:01:58,650 Kali jangka kes terburuk daripada jenis kemasukan adalah n kuasa dua. 39 00:01:58,650 --> 00:02:02,380 Terbaik-kes yang dikendalikan masa adalah n. 40 00:02:02,380 --> 00:02:05,380 >> Bergabung sort-- kata kunci di sini adalah berpecah dan bergabung. 41 00:02:05,380 --> 00:02:08,949 Kami berpecah array penuh, sama ada itu enam elemen, lapan elemen, 42 00:02:08,949 --> 00:02:13,790 10000 elements-- kita berpecah turun sebanyak separuh, separuh, separuh, 43 00:02:13,790 --> 00:02:17,720 sehingga kita di bawah pelbagai n satu tatasusunan unsur. 44 00:02:17,720 --> 00:02:19,470 Satu set n satu tatasusunan unsur. 45 00:02:19,470 --> 00:02:22,640 Oleh itu, kita bermula dengan satu Pelbagai 1000-elemen, 46 00:02:22,640 --> 00:02:26,550 dan kita sampai ke tahap di mana kita mempunyai 1,000 tatasusunan satu elemen. 47 00:02:26,550 --> 00:02:30,990 Kemudian kita mula untuk menggabungkan mereka sub tatasusunan kembali bersama-sama dalam susunan yang betul. 48 00:02:30,990 --> 00:02:34,860 Oleh itu, kita mengambil dua tatasusunan satu elemen dan mewujudkan pelbagai dua unsur. 49 00:02:34,860 --> 00:02:38,180 Kami mengambil dua tatasusunan dua unsur dan mewujudkan pelbagai empat elemen 50 00:02:38,180 --> 00:02:43,900 dan sebagainya dan sebagainya sehingga kami telah lagi dibina semula satu n unsur tatasusunan. 51 00:02:43,900 --> 00:02:48,410 >> Kali jangka kes terburuk daripada bergabung MENGASINGKAN n kali log n. 52 00:02:48,410 --> 00:02:52,390 Kami mempunyai n unsur, tetapi proses recombining ini 53 00:02:52,390 --> 00:02:56,960 mengambil log n langkah-langkah untuk mendapatkan menyandarkan kepada pelbagai penuh. 54 00:02:56,960 --> 00:03:01,160 Kes terbaik masa berjalan juga n log n kerana proses ini tidak benar-benar 55 00:03:01,160 --> 00:03:04,090 peduli sama ada array adalah disusun atau tidak untuk memulakan dengan. 56 00:03:04,090 --> 00:03:07,590 Proses ini adalah yang sama, ada ada cara untuk perkara litar pintas. 57 00:03:07,590 --> 00:03:11,610 Jadi n n dalam kes paling teruk log, n log n dalam hal yang terbaik. 58 00:03:11,610 --> 00:03:13,960 >> Kita bercakap kira-kira dua mencari algoritma. 59 00:03:13,960 --> 00:03:16,230 Jadi carian linear adalah kira-kira iterating. 60 00:03:16,230 --> 00:03:19,500 Kita teruskan seluruh array sekali, dari kiri ke kanan, 61 00:03:19,500 --> 00:03:21,950 cuba untuk mencari nombor yang kita cari. 62 00:03:21,950 --> 00:03:24,550 Masa yang paling buruk jalankan adalah O besar n. 63 00:03:24,550 --> 00:03:27,610 Ia mungkin membawa kita iterating di setiap elemen tunggal 64 00:03:27,610 --> 00:03:30,660 untuk mencari elemen yang kita sedang untuk, sama ada dalam kedudukan yang terakhir, 65 00:03:30,660 --> 00:03:31,630 atau tidak sama sekali. 66 00:03:31,630 --> 00:03:34,720 Tetapi kita tidak boleh mengesahkan bahawa sehingga kita telah melihat segala-galanya. 67 00:03:34,720 --> 00:03:36,730 m terbaik kes, kita dapati dengan segera. 68 00:03:36,730 --> 00:03:41,060 Kali jangka kes terbaik daripada carian linear adalah omega 1. 69 00:03:41,060 --> 00:03:43,689 >> Akhir sekali, terdapat carian binari, yang memerlukan lokasi yang pelbagai. 70 00:03:43,689 --> 00:03:45,605 Ingat itulah yang sangat pertimbangan yang penting 71 00:03:45,605 --> 00:03:47,155 apabila bekerja dengan carian binari. 72 00:03:47,155 --> 00:03:50,180 Ia adalah pra-syarat untuk menggunakan kitab itu array bahawa anda melihat melalui 73 00:03:50,180 --> 00:03:52,160 mesti disusun. 74 00:03:52,160 --> 00:03:54,500 Jika tidak, kata kunci adalah pecah dan perintah. 75 00:03:54,500 --> 00:03:58,310 Split array ke dalam separuh dan menghapuskan separuh daripada unsur-unsur 76 00:03:58,310 --> 00:04:00,780 setiap kali apabila anda meneruskan melalui. 77 00:04:00,780 --> 00:04:04,330 Oleh kerana jurang ini dan menakluk dan perkara-perkara membelah dalam pendekatan separuh, 78 00:04:04,330 --> 00:04:07,450 masa jangka kes terburuk carian binari adalah 79 00:04:07,450 --> 00:04:11,730 log n, yang sebahagian besarnya lebih baik daripada carian linear ini n. 80 00:04:11,730 --> 00:04:13,570 Terbaik-kes menjalankan masa masih salah. 81 00:04:13,570 --> 00:04:17,010 >> Kita mungkin merasa segera kali pertama kami membuat pembahagian, tetapi, 82 00:04:17,010 --> 00:04:19,339 lagi, ingat bahawa walaupun carian binari adalah 83 00:04:19,339 --> 00:04:24,030 jauh lebih baik daripada carian linear selaku log n berbanding n, 84 00:04:24,030 --> 00:04:27,110 anda mungkin perlu melalui kerja menyusun pelbagai anda pertama, yang 85 00:04:27,110 --> 00:04:32,010 mungkin membuat ia kurang berkesan bergantung kepada saiz iterating yang disusun. 86 00:04:32,010 --> 00:04:35,250 >> Saya Doug Lloyd, ini adalah CS50. 87 00:04:35,250 --> 00:04:36,757