1 00:00:00,000 --> 00:00:11,100 >> [MUSIC PLAYING] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. Malan: Baiklah. 3 00:00:11,490 --> 00:00:12,170 Jadi selamat datang kembali. 4 00:00:12,170 --> 00:00:15,180 Ini adalah CS50, dan adalah akhir minggu ketiga. 5 00:00:15,180 --> 00:00:17,770 >> Jadi ingat dalam beberapa minggu terakhir, kita telah menghabiskan cukup banyak 6 00:00:17,770 --> 00:00:20,820 waktu di C, pada pemrograman, pada sintaks. 7 00:00:20,820 --> 00:00:24,680 Dan itu cukup normal, jika Anda masih berjuang dengan masalah Set 2, menjadi 8 00:00:24,680 --> 00:00:25,950 membenturkan kepala ke dinding. 9 00:00:25,950 --> 00:00:28,310 Ini pesan kesalahan yang rumit yang tampak dan bug yang Anda 10 00:00:28,310 --> 00:00:29,220 tak bisa mengejar. 11 00:00:29,220 --> 00:00:32,310 Karena, yakinlah, bahwa hanya dalam waktu beberapa minggu Anda akan melihat kembali 12 00:00:32,310 --> 00:00:35,930 hal-hal seperti Caesar, dan [? V-genair,?] bahkan mungkin Crack, dan 13 00:00:35,930 --> 00:00:40,050 menyadari betapa jauh Anda telah datang dalam waktu singkat. 14 00:00:40,050 --> 00:00:43,670 Jadi kalau itu bisa menghibur, bertahan di sana untuk saat ini. 15 00:00:43,670 --> 00:00:46,610 >> Hari ini, meskipun, kita mulai transisi untuk hal-hal tingkat yang lebih tinggi. 16 00:00:46,610 --> 00:00:49,820 Dan kita mulai untuk mengambil begitu saja bahwa kalian tahu bagaimana program, atau 17 00:00:49,820 --> 00:00:52,090 paling awal dari bahwa tingkat kenyamanan. 18 00:00:52,090 --> 00:00:56,520 Dan kita akan mulai untuk mempertimbangkan bagaimana kita bisa pergi tentang merancang program yang lebih 19 00:00:56,520 --> 00:00:57,440 efektif. 20 00:00:57,440 --> 00:01:01,090 Bagaimana kita bisa pergi tentang optimalisasi efisiensi algoritma kami, dan 21 00:01:01,090 --> 00:01:03,110 umumnya memecahkan lebih masalah yang menarik. 22 00:01:03,110 --> 00:01:06,850 Dan mulai mengambil begitu saja bahwa, jika kita ingin, kita bisa kode apa pun 23 00:01:06,850 --> 00:01:08,350 contoh yang kita miliki dalam pikiran. 24 00:01:08,350 --> 00:01:11,430 Jadi hari ini, kita tidak menyentuh keyboard untuk segala bentuk kode. 25 00:01:11,430 --> 00:01:15,150 Ini akan menjadi tingkat yang lebih tinggi, dan akhirnya, sekitar pemecahan masalah. 26 00:01:15,150 --> 00:01:20,490 >> Jadi untuk sampai ke titik itu, saya mengusulkan bahwa tujuh berikut 27 00:01:20,490 --> 00:01:24,290 persegi panjang mewakili tujuh pintu, di belakang yang merupakan sejumlah besar 28 00:01:24,290 --> 00:01:26,340 nomor, di antaranya adalah nomor 50. 29 00:01:26,340 --> 00:01:30,470 Biarkan aku memproyeksikan ini tentang hal ini layar di sini juga. 30 00:01:30,470 --> 00:01:36,770 Dan mengusulkan bahwa kita membutuhkan sukarelawan untuk membantu menemukan saya nomor di depan 31 00:01:36,770 --> 00:01:38,140 internet di sini untuk melihat. 32 00:01:38,140 --> 00:01:40,755 Ayo up, di pink. 33 00:01:40,755 --> 00:01:43,050 Baik. 34 00:01:43,050 --> 00:01:43,930 Siapa nama Anda? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [Tak terdengar] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. Malan: Maaf? 37 00:01:45,170 --> 00:01:45,860 >> JENNIFER: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> DAVID J. Malan: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Baiklah, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Senang bertemu Anda. 41 00:01:47,630 --> 00:01:48,370 Ayo up. 42 00:01:48,370 --> 00:01:52,430 Jadi ini di sini adalah tujuh pintu, dan apa Saya ingin Anda lakukan bagi kita di sini, 43 00:01:52,430 --> 00:01:56,560 di depan semua teman-teman sekelas Anda, adalah menemukan kami nomor, 50. 44 00:01:56,560 --> 00:02:00,860 Untuk menemukan nomor, Anda bisa mengintip di balik salah satu pintu ini dengan hanya menekan 45 00:02:00,860 --> 00:02:03,030 pada salah satu pintu, dan akan mengungkapkan jumlahnya. 46 00:02:03,030 --> 00:02:06,080 Dan mari kita lihat seberapa cepat Anda dapat menemukan kami nomor, 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Baik dilakukan. 54 00:02:17,350 --> 00:02:18,040 Baik. 55 00:02:18,040 --> 00:02:19,906 Tepuk tangan untuk Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Tepuk Tangan] 57 00:02:21,530 --> 00:02:22,320 >> Baik. 58 00:02:22,320 --> 00:02:25,254 Jadi apa strategi Anda untuk menemukan nomor tersebut, 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Um, saya pikir mungkin jika - 60 00:02:27,222 --> 00:02:27,714 [Tak terdengar] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. Malan: Oh. 62 00:02:28,206 --> 00:02:29,630 Berikan satu detik. 63 00:02:29,630 --> 00:02:32,420 Jadi itu strategi Anda untuk menemukan nomor tersebut, 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Jadi aku hanya mulai di mulai melihat apa nomor pertama 65 00:02:34,760 --> 00:02:38,590 adalah, dan kemudian aku berpikir, mungkin jika mereka diurutkan, aku hanya akan terus 66 00:02:38,590 --> 00:02:39,970 menekan lebih tinggi? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. Malan: OK. 68 00:02:40,140 --> 00:02:42,910 Dan kita tampaknya telah menemukan bahwa untuk menjadi kasus. 69 00:02:42,910 --> 00:02:45,670 Meskipun, mari kita mengupas lapisan-lapisan hanya sedikit, dan Anda ingin pergi 70 00:02:45,670 --> 00:02:47,640 depan dan mengungkapkan pintu lain Anda bisa memilih? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Oh, sayang. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. Malan: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Jadi saya hanya beruntung. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. Malan: Jadi Anda beruntung. 76 00:02:55,270 --> 00:02:55,710 Baik. 77 00:02:55,710 --> 00:02:56,795 Jadi tidak buruk. 78 00:02:56,795 --> 00:02:58,750 Tapi itu menarik wawasan, kan? 79 00:02:58,750 --> 00:03:01,870 Jika Anda diasumsikan, dan Anda tidak mendapatkan, memang, sedikit beruntung ada. 80 00:03:01,870 --> 00:03:05,350 Tetapi jika Anda berasumsi bahwa jumlahnya diurutkan, Anda bisa lebih tepat 81 00:03:05,350 --> 00:03:08,750 seperti bagaimana yang mempengaruhi perilaku Anda? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Jadi, jika mereka diurutkan, saya pikir mungkin terkecil hingga terbesar. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. Malan: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: Atau jika ini akhirnya menjadi benar-benar besar, maka terbesar ke terkecil. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. Malan: OK. 86 00:03:15,540 --> 00:03:18,170 Jadi terbesar ke terkecil, atau terkecil hingga terbesar. 87 00:03:18,170 --> 00:03:21,990 Tapi biarkan aku mengusulkan, misalkan Anda memiliki mendapat sial, dan menganggap bahwa mereka 88 00:03:21,990 --> 00:03:26,840 tidak, pada kenyataannya, diurutkan, berapa banyak pintu-pintu yang mungkin Anda harus mengintip 89 00:03:26,840 --> 00:03:28,590 belakang dalam kasus terburuk? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Semua dari mereka. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. Malan: Semua dari mereka. 92 00:03:30,420 --> 00:03:31,740 Jadi mari kita generalisasi bahwa sebagai n. 93 00:03:31,740 --> 00:03:34,790 Kebetulan ada 7, tapi mari lebih umumnya mengatakan ada pintu n pada 94 00:03:34,790 --> 00:03:35,650 layar di sini. 95 00:03:35,650 --> 00:03:40,110 Jadi dalam kasus terburuk, Anda harus untuk melihat ke belakang 7 pintu, atau n pintu. 96 00:03:40,110 --> 00:03:44,140 Dan jadi ini benar-benar, itu sedikit beruntung hari ini, tetapi itu benar-benar linier 97 00:03:44,140 --> 00:03:46,440 Algoritma macam, meskipun Anda adalah jenis melompat-lompat. 98 00:03:46,440 --> 00:03:47,080 Apakah itu adil? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Ya. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. Malan: Nah, biarkan aku melihat apakah Anda Perubahan strategi jika saya memindahkan kita ke 101 00:03:50,000 --> 00:03:52,190 Contoh kedua kami di sini dengan 7 pintu yang berbeda. 102 00:03:52,190 --> 00:03:55,240 Angka yang sama, tapi ini saat mereka diurutkan. 103 00:03:55,240 --> 00:03:58,350 Apa strategi Anda di sini akan menjadi, mencoba untuk memadamkan pikiran Anda apa yang 104 00:03:58,350 --> 00:03:59,310 nomor lain - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. Malan: - sebelumnya? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Mari kita mulai dengan yang pertama. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. Malan: Baiklah. 109 00:04:03,540 --> 00:04:05,190 Mulailah dengan yang pertama. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Sekarang di mana Anda akan pergi, dan mengapa? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 benar-benar kecil. 113 00:04:10,040 --> 00:04:12,500 Jadi jika mereka pun mungkin terkecil sampai terbesar, seharusnya 114 00:04:12,500 --> 00:04:13,290 menjadi dua kali lipat, dan -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. Malan: OK. 116 00:04:13,670 --> 00:04:15,990 Mari kita lihat, yang menurut Anda? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Coba yang terakhir. 118 00:04:19,050 --> 00:04:19,500 Nice. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. Malan: Sangat baik dilakukan. 120 00:04:20,880 --> 00:04:21,860 Baik. 121 00:04:21,860 --> 00:04:23,010 >> [Tepuk Tangan] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. Malan: OK. 123 00:04:24,310 --> 00:04:26,790 Jadi Anda benar-benar melakukan hal ini mengerikan, karena kau 124 00:04:26,790 --> 00:04:27,700 melakukannya dengan sangat baik. 125 00:04:27,700 --> 00:04:31,150 Yang membuat kita mampu membuat titik-titik tertentu. 126 00:04:31,150 --> 00:04:32,565 Jadi mari kita coba untuk memutar kembali di sini. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. Malan: Sangat baik dilakukan, namun. 129 00:04:35,980 --> 00:04:39,060 Jadi Anda mulai dari awal, Anda melihat bahwa itu adalah 4, maka Anda 130 00:04:39,060 --> 00:04:40,240 pindah ke akhir. 131 00:04:40,240 --> 00:04:42,320 Tapi bagaimana kalau Anda tidak beruntung ada, dan anggaplah 50 132 00:04:42,320 --> 00:04:42,890 berada di tempat lain. 133 00:04:42,890 --> 00:04:46,190 Apa langkah ketiga Anda telah? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Kembali ke awal. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. Malan: Kembali ke awal. 136 00:04:48,320 --> 00:04:51,320 OK, jadi Anda pasti sudah menyentuh pintu ini, yang 8. 137 00:04:51,320 --> 00:04:51,660 Baik. 138 00:04:51,660 --> 00:04:52,650 Jadi itu bukan 50. 139 00:04:52,650 --> 00:04:55,380 Di mana Anda akan tampak selanjutnya? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Jika saya tidak tahu mereka beres. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. Malan: Benar. 142 00:04:57,005 --> 00:04:58,490 Nah, jika Anda tidak tahu mereka diurutkan - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Oh, memang tahu, ya. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. Malan: - tetapi Anda tidak tahu di mana 50 adalah belum? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Hanya terus. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. Malan: Baiklah. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Terus. 149 00:05:03,800 --> 00:05:05,270 OK, saya bisa bekerja dengan. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. Malan: Sekarang, jika Anda hanya akan terus, apa yang Anda 152 00:05:07,210 --> 00:05:09,680 algoritma devolving mundur ke. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: The linier -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. Malan: Ini adalah jenis linier. 155 00:05:11,820 --> 00:05:13,480 Tapi biarkan aku mengusulkan, biarkan saya ditempatkan pada pusatnya. 156 00:05:13,480 --> 00:05:14,900 Biarkan aku refresh halaman. 157 00:05:14,900 --> 00:05:17,120 nomor yang sama, pengaturan yang sama, pintu yang sama. 158 00:05:17,120 --> 00:05:21,350 Tetapi berpikir kembali ke hari pertama dalam kelas ketika kita merobek buku telepon di 159 00:05:21,350 --> 00:05:25,480 setengah, semacam, dan apa yang Strategi kami di sana? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Mulai tengah. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. Malan: OK. 162 00:05:26,690 --> 00:05:27,610 Jadi mulai dari tengah. 163 00:05:27,610 --> 00:05:28,790 Jadi mari kita pergi ke depan dan mensimulasikan itu. 164 00:05:28,790 --> 00:05:30,720 Mulai dari tengah oleh mengungkapkan pintu itu. 165 00:05:30,720 --> 00:05:31,660 Jadi jumlah 16. 166 00:05:31,660 --> 00:05:35,290 Jadi apa yang akan orang yang kuat telah dilakukan, yang merobek buku telepon dalam setengah, 167 00:05:35,290 --> 00:05:38,450 untuk sampai ke menebak berikutnya? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Pergi dalam setengah ini. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. Malan: Dan mengapa ke kanan? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Jika mereka semacam terkecil sampai terbesar, kemudian 50 harus 171 00:05:43,900 --> 00:05:44,720 pada akhir itu. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. Malan: Baik. 173 00:05:44,920 --> 00:05:45,390 Benar-benar masuk akal. 174 00:05:45,390 --> 00:05:48,380 Jadi seperti buku telepon, Anda pergi ke tepat sebagai lawan ke kiri, tapi di sini 175 00:05:48,380 --> 00:05:49,500 adalah takeaway kunci. 176 00:05:49,500 --> 00:05:53,930 Sekarang Anda dapat membuang, atau merobek, setengah dari masalah ini, meninggalkan Anda tidak 177 00:05:53,930 --> 00:05:55,970 dengan 7 pintu, tapi benar-benar hanya 3. 178 00:05:55,970 --> 00:05:57,870 Yang kira-kira setengah dari ukuran masalah. 179 00:05:57,870 --> 00:05:58,350 Baik. 180 00:05:58,350 --> 00:06:01,890 Jadi sekarang apa yang akan Anda miliki dilakukan setelah Anda pergi kan? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Jadi 16 masih cukup kecil, relatif terhadap 50, jadi mungkin aku akan mencoba, 182 00:06:05,870 --> 00:06:06,700 seperti, yang satu ini. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. Malan: Baiklah. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Baiklah, jadi sekarang apa yang Anda naluri memberitahu Anda? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Saya dapat membuang ini dan kemudian hanya - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. Malan: OK. 188 00:06:12,360 --> 00:06:14,212 Baik, Anda dapat membuang kiri setengah sana. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - memilih satu ini. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. Malan: Dan kanan. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Ya. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. Malan: Jadi meskipun sulit untuk melihat mungkin, ketika hanya ada 193 00:06:17,820 --> 00:06:21,320 7 pintu, pikirkan, sekarang, konsistensi dari 194 00:06:21,320 --> 00:06:22,620 Algoritma Anda hanya diterapkan. 195 00:06:22,620 --> 00:06:24,510 Dalam kasus sebelumnya, Anda lakukan beruntung, yang besar. 196 00:06:24,510 --> 00:06:26,540 Tapi Anda tidak menggunakan heuristik, Aku akan mengatakan. 197 00:06:26,540 --> 00:06:29,150 Anda menggunakan semacam naluri Anda, dan mengetahui disortir, jika itu cukup 198 00:06:29,150 --> 00:06:31,600 kecil di awal, jelas, kami sudah harus pergi lebih ke kanan. 199 00:06:31,600 --> 00:06:34,990 Tapi dalam beberapa hal, Anda beruntung, karena mungkin ini adalah nomor 100, 200 00:06:34,990 --> 00:06:36,220 dan mungkin 50 lebih di tengah. 201 00:06:36,220 --> 00:06:37,910 Mungkin 50 bahkan di sini. 202 00:06:37,910 --> 00:06:40,960 >> Tapi apa yang Anda lakukan sedikit berbeda kali ini adalah, Anda melakukan hal yang sama 203 00:06:40,960 --> 00:06:42,150 lagi dan lagi. 204 00:06:42,150 --> 00:06:45,310 Dan saya berpendapat bahwa apa yang baru saja tidak, meskipun dipengaruhi oleh telepon 205 00:06:45,310 --> 00:06:48,100 buku misalnya, adalah sesuatu yang jauh lebih algoritmik, dan masih banyak 206 00:06:48,100 --> 00:06:49,930 kurang istimewa cased. 207 00:06:49,930 --> 00:06:51,620 Banyak kurang naluriah. 208 00:06:51,620 --> 00:06:57,160 Jadi pada akhir hari, bagaimana Anda menggambarkan efisiensi 209 00:06:57,160 --> 00:07:00,530 algoritma pertama, di mana Anda pergi kiri ke kanan, versus 210 00:07:00,530 --> 00:07:03,430 algoritma kedua di sini? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: Yang satu ini harus, seperti, mungkin membagi waktu, atau bahkan lebih, ya. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. Malan: OK, bahkan mungkin lebih. 213 00:07:07,320 --> 00:07:10,150 Mari kita menekan sedikit lebih keras pada itu. 214 00:07:10,150 --> 00:07:13,030 Apa benar-benar, jika kita melanjutkan terapi ini logika, kita pasti dibelah dua 215 00:07:13,030 --> 00:07:15,830 waktu berjalan dengan algoritma kedua ini dengan membuang setengah dari 216 00:07:15,830 --> 00:07:18,470 angka, tapi apa yang kita lakukan pada berikutnya iterasi, ketika Jennifer mengungkapkan 217 00:07:18,470 --> 00:07:20,615 angka kedua? 218 00:07:20,615 --> 00:07:22,830 >> Kami dibelah dua jumlah pintu lagi. 219 00:07:22,830 --> 00:07:25,270 Lalu apa yang kita lakukan setelah itu, jika ada pintu lagi untuk bermain dengan? 220 00:07:25,270 --> 00:07:27,520 Kami akan membagi mereka, dan sekali lagi, dan lagi, dan lagi. 221 00:07:27,520 --> 00:07:30,420 Dan ini hanya seperti kalian semua berdiri pada minggu pertama 222 00:07:30,420 --> 00:07:33,000 kelas, setengah dari Anda duduk, setengah Anda duduk, setengah dari Anda 223 00:07:33,000 --> 00:07:35,440 duduk, sampai satu satunya jiwa berdiri. 224 00:07:35,440 --> 00:07:39,050 Dan kita mengatakan bahwa waktu berjalan itu, jumlah langkah yang dibutuhkan adalah 225 00:07:39,050 --> 00:07:40,430 pada urutan apa? 226 00:07:40,430 --> 00:07:41,230 >> SPEAKER 1: [Tak terdengar] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. Malan: Jadi log basis 2 dari n, atau hanya lebih sederhana, log n. 228 00:07:43,970 --> 00:07:45,060 Jadi sesuatu yang logaritmik. 229 00:07:45,060 --> 00:07:48,380 Dan grafik itu bukan garis lurus yang baru saja lebih buruk dan lebih buruk, itu 230 00:07:48,380 --> 00:07:52,490 kurva ini menarik yang tidak begitu buruk dari waktu ke waktu. 231 00:07:52,490 --> 00:07:53,910 Jadi mari kita berpegang pada ide ini. 232 00:07:53,910 --> 00:07:54,690 Mari kita terima Jennifer. 233 00:07:54,690 --> 00:07:56,150 Terima kasih banyak untuk datang ke atas. 234 00:07:56,150 --> 00:07:57,400 Dan, satu detik. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Tidak ada lampu meja hari ini, tapi kami punya CS50 bola stres. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. Malan: Baiklah, di sini. 239 00:08:04,410 --> 00:08:06,545 Terima kasih untuk menimbulkan stres di sini. 240 00:08:06,545 --> 00:08:07,350 Baik. 241 00:08:07,350 --> 00:08:10,620 Jadi mari kita lihat apakah kita tidak bisa sekarang memformalkan ini sedikit lebih. 242 00:08:10,620 --> 00:08:14,820 Jadi sekali lagi, apa yang kita lakukan adalah dasarnya hal yang sama seperti yang kita lakukan 243 00:08:14,820 --> 00:08:16,660 dalam minggu pertama. 244 00:08:16,660 --> 00:08:23,780 Namun, bukannya akhir hanya dengan linear algoritma, yang kita digambarkan 245 00:08:23,780 --> 00:08:27,210 sebelumnya sebagai garis lurus ini, dimana, jika kita menempatkan satu pintu lebih 246 00:08:27,210 --> 00:08:29,610 layar, maka Jennifer akan harus melihat, berpotensi, 247 00:08:29,610 --> 00:08:30,600 di belakang salah satu pintu lagi. 248 00:08:30,600 --> 00:08:33,490 Jika kita menempatkan dua pintu lagi, dia mungkin untuk melihat ke belakang dua pintu lagi. 249 00:08:33,490 --> 00:08:35,990 >> Dan, ada ini linier hubungan antara ukuran 250 00:08:35,990 --> 00:08:39,059 masalah pada, katakanlah, sumbu x, dan jumlah waktu yang dibutuhkan untuk 251 00:08:39,059 --> 00:08:40,440 memecahkan on y tersebut. 252 00:08:40,440 --> 00:08:43,330 Tapi gambar saya menyinggung sebelumnya adalah jalur hijau. 253 00:08:43,330 --> 00:08:45,970 Hijau sengaja, karena itu hanya merasa lebih baik. 254 00:08:45,970 --> 00:08:49,790 Secara teori, algoritma, ketika kita melakukannya dengan buku telepon, ketika kita melakukannya 255 00:08:49,790 --> 00:08:52,420 dengan kalian menghitung sama lain, dan dalam kasus kedua, ketika Jennifer hanya 256 00:08:52,420 --> 00:08:55,250 melakukannya di sini, itu semacam dari fundamental baik. 257 00:08:55,250 --> 00:08:57,180 Karena itu bukan hanya dua kali lebih cepat. 258 00:08:57,180 --> 00:08:58,870 Itu tidak bahkan empat kali lebih cepat. 259 00:08:58,870 --> 00:09:03,290 Itu sepenuhnya tergantung pada apa yang ukuran masukan itu, untuk berapa banyak 260 00:09:03,290 --> 00:09:05,220 langkah akhirnya mengambil. 261 00:09:05,220 --> 00:09:08,040 >> Dan jadi ide sederhana ini bahwa kita semua mengambil untuk diberikan dengan buku telepon, 262 00:09:08,040 --> 00:09:10,200 sama dapat diterapkan untuk sesuatu seperti ini. 263 00:09:10,200 --> 00:09:12,380 Dan ini mungkin akan lebih santai dikenal sebagai, seperti yang mungkin Anda 264 00:09:12,380 --> 00:09:13,940 bayangkan, membagi dan menaklukkan. 265 00:09:13,940 --> 00:09:16,390 Tidak seperti apa yang kita lakukan, tentu saja, dengan buku telepon. 266 00:09:16,390 --> 00:09:18,300 >> Tapi pseudocode, ingat, adalah ini. 267 00:09:18,300 --> 00:09:21,800 Jadi kita tidak akan melakukan ini lagi, tapi ingat bahwa minggu pertama, kita semua berdiri 268 00:09:21,800 --> 00:09:25,140 dan kemudian setengah dari Anda duduk, setengah dari Anda duduk, setengah dari Anda duduk. 269 00:09:25,140 --> 00:09:29,280 Algoritma yang diterapkan dalam sedikit cara curang, dalam itu, 270 00:09:29,280 --> 00:09:32,870 tidak hanya satu saya menghitung, fundamental, lebih efisien. 271 00:09:32,870 --> 00:09:35,830 Dalam hal ini, saya memanfaatkan sumber daya sekunder. 272 00:09:35,830 --> 00:09:39,470 Begitulah, beberapa CPU, beberapa otak, beberapa orang pintar di 273 00:09:39,470 --> 00:09:42,740 Ruangan yang membantu saya mendapatkan dari sesuatu linier untuk sesuatu 274 00:09:42,740 --> 00:09:45,190 logaritmik, dari sesuatu merah untuk sesuatu yang hijau. 275 00:09:45,190 --> 00:09:48,650 >> Tapi dalam kasus ini, Jennifer sendiri bisa mendasar meningkatkan atas 276 00:09:48,650 --> 00:09:52,370 kinerja algoritma pertama oleh, lagi, hanya berpikir sedikit lebih keras. 277 00:09:52,370 --> 00:09:56,650 Dan sekarang, ketika tiba saatnya untuk melaksanakan hal-hal ini, mencari tahu 278 00:09:56,650 --> 00:10:00,670 apa baris kode Anda dapat menulis seperti bahwa Anda dapat mengulangi lagi, dan 279 00:10:00,670 --> 00:10:03,350 lagi, dan lagi, semacam dengan cara perulangan. 280 00:10:03,350 --> 00:10:06,370 Karena Anda tidak akan memiliki mewah, seperti Jennifer lakukan pada awalnya, untuk 281 00:10:06,370 --> 00:10:10,460 hanya memiliki sejumlah besar seandainya dan berkata, hmm, jika nomor ini pertama adalah 4, 282 00:10:10,460 --> 00:10:11,800 biarkan aku melompat semua jalan sampai akhir. 283 00:10:11,800 --> 00:10:14,180 Ooh, jika nomor yang terlalu besar, membiarkan saya pindah kembali sewenang-wenang 284 00:10:14,180 --> 00:10:15,220 untuk elemen kedua. 285 00:10:15,220 --> 00:10:18,210 Anda akan menemukan bahwa itu akan menjadi jauh lebih sulit untuk memformalkan apa yang kita manusia 286 00:10:18,210 --> 00:10:21,270 mengambil untuk diberikan sebagai sangat wajar heuristik, tetapi komputer hanya 287 00:10:21,270 --> 00:10:23,260 akan melakukan apa yang Anda katakan untuk dilakukan. 288 00:10:23,260 --> 00:10:25,280 >> Sekarang ini memiliki sangat menarik implikasi. 289 00:10:25,280 --> 00:10:29,950 Grafik ini semacam dimaksudkan untuk semacam membanjiri visual, tapi perhatikan, di mana 290 00:10:29,950 --> 00:10:32,230 adalah garis lurus dalam grafik ini? 291 00:10:32,230 --> 00:10:35,330 Dimana grafik linear yang kita sebut n? 292 00:10:35,330 --> 00:10:37,580 Yah, itu semacam arah bawah gambar ini, kan? 293 00:10:37,580 --> 00:10:40,500 Jadi yang kita lakukan adalah kita sudah semacam diperbesar keluar untuk sumbu x dan 294 00:10:40,500 --> 00:10:44,780 y-axis untuk mencoba untuk mendapatkan rasa apa jenis lain dari kurva terlihat seperti. 295 00:10:44,780 --> 00:10:47,760 >> Dan spesifik dari matematika ekspresi saat ini tidak akan begitu penting 296 00:10:47,760 --> 00:10:52,440 banyak, tapi melihat bahwa ada banyak algoritma yang jauh lebih buruk daripada 297 00:10:52,440 --> 00:10:53,470 sesuatu yang linear. 298 00:10:53,470 --> 00:10:55,410 Memang, n potong dadu terlihat sangat buruk. 299 00:10:55,410 --> 00:10:58,400 2 sampai n terlihat sangat buruk. n kuadrat terlihat sangat buruk. 300 00:10:58,400 --> 00:11:01,630 Dan kita akan melihat apa yang beberapa dari mereka mungkin dalam realitas hari ini. 301 00:11:01,630 --> 00:11:05,430 Dan log n tidak merasa buruk, tapi lebih baik dari n adalah log basis 2 dari n. 302 00:11:05,430 --> 00:11:08,080 Tapi kau tahu, itu akan menjadi lebih lebih menakjubkan jika Jennifer, atau jika kita, 303 00:11:08,080 --> 00:11:12,910 bahwa minggu pertama, telah datang dengan sesuatu yang log log n. 304 00:11:12,910 --> 00:11:15,880 >> Jadi dengan kata lain, ada ini seluruh berbagai solusi yang mungkin untuk 305 00:11:15,880 --> 00:11:18,570 masalah, tetapi bahkan di sini, pemberitahuan apa yang akan terjadi. 306 00:11:18,570 --> 00:11:22,910 Ketika saya zoom out, yang kurva ini akan terbukti menjadi mutlak 307 00:11:22,910 --> 00:11:26,630 terburuk dari orang-orang di layar sekarang? 308 00:11:26,630 --> 00:11:28,680 Jadi n potong dadu terlihat cantik buruk saat ini. 309 00:11:28,680 --> 00:11:32,470 Tetapi jika kita zoom out dan melihat lebih banyak x dan sumbu y, siapa yang akan 310 00:11:32,470 --> 00:11:34,550 mendominasi pada akhirnya? 311 00:11:34,550 --> 00:11:37,120 Jadi itu benar-benar ternyata bahwa 2 ke n, dan Anda dapat mengetahui ini hanya dengan 312 00:11:37,120 --> 00:11:39,990 mencolokkan beberapa semakin besar angka, dan Anda akan melihat bahwa 2 ke 313 00:11:39,990 --> 00:11:42,070 n, memang, akan lebih besar jauh lebih cepat. 314 00:11:42,070 --> 00:11:45,530 Jika kita benar-benar zoom out, 2 ke algoritma n benar-benar menyebalkan. 315 00:11:45,530 --> 00:11:48,170 Maksud saya ini akan mengambil sedikit waktu untuk 316 00:11:48,170 --> 00:11:49,460 komputer untuk churn melalui. 317 00:11:49,460 --> 00:11:52,500 >> Tapi Anda akan melihat dari waktu ke waktu, terutama masalah set masa depan dan bahkan 318 00:11:52,500 --> 00:11:55,600 proyek akhir, adalah data Anda set mendapat besar, oke? 319 00:11:55,600 --> 00:11:58,300 Bahkan dalam versi pertama dari Facebook, sebagai jumlah teman, dan 320 00:11:58,300 --> 00:12:01,840 jumlah pengguna terdaftar mendapat besar, Anda bisa menyortir telepon dalam dan 321 00:12:01,840 --> 00:12:05,530 melaksanakan sesuatu dengan pencarian linear, atau penyortiran sangat sederhana 322 00:12:05,530 --> 00:12:07,030 algoritma, seperti yang akan kita lihat saat ini. 323 00:12:07,030 --> 00:12:09,280 Anda harus mulai berpikir keras dan keras tentang masalah ini. 324 00:12:09,280 --> 00:12:12,070 Dan jenis masalah tempat-tempat seperti Facebook, dan Google, dan Microsoft, 325 00:12:12,070 --> 00:12:16,350 dan lain-lain bekerja pada adalah persis ini semacam semacam data yang besar pertanyaan 326 00:12:16,350 --> 00:12:18,530 semakin hari ini. 327 00:12:18,530 --> 00:12:18,900 >> Baik. 328 00:12:18,900 --> 00:12:23,800 Jadi keberhasilan Jennifer dalam kedua algoritma, terus terang, dia luar biasa 329 00:12:23,800 --> 00:12:26,110 juga pertama kalinya, tapi mari kita menuliskannya sebagai keberuntungan sehingga kita 330 00:12:26,110 --> 00:12:27,000 dapat membuat hal ini. 331 00:12:27,000 --> 00:12:30,970 Dalam kasus kedua, ia memanfaatkan suatu algoritma yang diulang lagi dan 332 00:12:30,970 --> 00:12:34,670 lagi, tapi ia mengambil untuk diberikan asumsi tertentu yang kita diperbolehkan 333 00:12:34,670 --> 00:12:39,370 , tapi dia dieksploitasi beberapa detail kedua kalinya bahwa dia tidak memiliki 334 00:12:39,370 --> 00:12:39,840 pertama kalinya. 335 00:12:39,840 --> 00:12:41,800 Yang adalah apa? 336 00:12:41,800 --> 00:12:43,050 >> Bahwa daftar diurutkan. 337 00:12:43,050 --> 00:12:46,350 Jadi, segera setelah daftar itu diurutkan, kita mengklaim bahwa Jennifer mampu melakukan 338 00:12:46,350 --> 00:12:47,480 fundamental yang lebih baik. 339 00:12:47,480 --> 00:12:51,450 7 pintu, ya, tidak menarik, tapi rasa itu kami 7 juta pintu. 340 00:12:51,450 --> 00:12:54,080 Log n pasti akan untuk melakukan banyak, banyak 341 00:12:54,080 --> 00:12:55,610 lebih cepat dalam jangka panjang. 342 00:12:55,610 --> 00:12:58,880 Tapi dia harus memiliki pintu diurutkan untuknya. 343 00:12:58,880 --> 00:13:02,320 Sekarang, saya mengambil kebebasan melakukan itu di muka pada layar komputer 344 00:13:02,320 --> 00:13:05,160 di sini, tapi anggaplah bahwa Jennifer harus melakukan itu sendiri? 345 00:13:05,160 --> 00:13:10,120 Misalkan bahwa pintu tersebut Data direpresentasikan dalam database, atau 346 00:13:10,120 --> 00:13:14,260 teman terdaftar untuk Facebook, atau setiap halaman web di internet yang 347 00:13:14,260 --> 00:13:16,880 berbagai situs mungkin perlu indeks atau cari berakhir. 348 00:13:16,880 --> 00:13:20,940 >> Misalkan Anda hanya memiliki data mentah menetapkan dan itu diserahkan kepada Anda, atau 349 00:13:20,940 --> 00:13:23,010 Jennifer untuk melakukan pemilahan itu? 350 00:13:23,010 --> 00:13:26,950 Artinya, bukan, mengharuskan kita menjawab pertanyaan, baik, berapa banyak waktu 351 00:13:26,950 --> 00:13:31,080 akan mengambil Jennifer, atau bahkan me, untuk mengurutkan angka-angka di muka jadi 352 00:13:31,080 --> 00:13:32,680 bahwa dia bisa mengambil keuntungan dari itu? 353 00:13:32,680 --> 00:13:32,880 Benar? 354 00:13:32,880 --> 00:13:36,620 Karena implikasinya, tentu saja, adalah jika dibutuhkan saya cukup lama untuk memilah 355 00:13:36,620 --> 00:13:40,800 angka, siapa sih yang peduli bahwa Anda dapat menemukan nomor seperti 50 begitu cepat, 356 00:13:40,800 --> 00:13:44,850 seperti dalam kasus Jennifer, jika kita lebih dari kewalahan jumlah total waktu 357 00:13:44,850 --> 00:13:46,920 butuh dengan memilah hal-hal di muka? 358 00:13:46,920 --> 00:13:49,320 >> Jadi mari kita lihat jika kita tidak bisa dengan cat gambar di sini. 359 00:13:49,320 --> 00:13:51,370 Saya memiliki seluruh banyak lebih banyak stres bola, jika yang membantu 360 00:13:51,370 --> 00:13:52,270 memecahkan es di sini. 361 00:13:52,270 --> 00:13:55,690 Dan jika Anda tidak keberatan, kami membutuhkan tujuh relawan - 362 00:13:55,690 --> 00:13:57,060 pada, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Jadi kita tidak harus menghabiskan pada lampu meja, tampaknya. 365 00:13:59,250 --> 00:13:59,690 Baik. 366 00:13:59,690 --> 00:14:01,530 Jadi bagaimana dengan Anda dua di depan. 367 00:14:01,530 --> 00:14:04,160 Bagaimana Anda dua orang di belakang. 368 00:14:04,160 --> 00:14:04,870 Jadi itu empat. 369 00:14:04,870 --> 00:14:09,890 Bagaimana dengan Anda di depan lima, enam dan tujuh. 370 00:14:09,890 --> 00:14:10,320 Disana. 371 00:14:10,320 --> 00:14:13,260 Teman Anda yang menunjuk Anda keluar, sehingga Anda mendapatkan hadiah. 372 00:14:13,260 --> 00:14:13,700 >> Baik. 373 00:14:13,700 --> 00:14:14,410 Ayo up. 374 00:14:14,410 --> 00:14:17,120 Dan kenapa tidak kita miliki Anda orang datang ke sini. 375 00:14:17,120 --> 00:14:18,960 Aku akan memberikan masing-masing nomor. 376 00:14:18,960 --> 00:14:22,150 Dan pergi ke depan dan mengatur diri identik dengan apa yang 377 00:14:22,150 --> 00:14:25,180 digambarkan di layar. 378 00:14:25,180 --> 00:14:26,530 >> [Interposing SUARA] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. Malan: Oop, maaf. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Baik. 382 00:14:32,180 --> 00:14:32,750 Nah, di sini kita pergi. 383 00:14:32,750 --> 00:14:34,180 Nomor lima. 384 00:14:34,180 --> 00:14:35,136 Nomor enam. 385 00:14:35,136 --> 00:14:37,770 Satu, dua, tiga, empat, lima, enam, tujuh. 386 00:14:37,770 --> 00:14:39,410 Oh, ini canggung. 387 00:14:39,410 --> 00:14:41,210 >> SPEAKER 2: Saya hanya akan mendapatkan -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. Malan: Good deal. 389 00:14:41,900 --> 00:14:43,130 Baik. 390 00:14:43,130 --> 00:14:44,611 Terima kasih atas partisipasinya. 391 00:14:44,611 --> 00:14:47,200 >> [Tepuk Tangan] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Baik. 394 00:14:48,860 --> 00:14:51,970 Jadi kita memiliki empat, dua, enam, satu, tiga, tujuh, lima. 395 00:14:51,970 --> 00:14:56,010 Sempurna sehingga kita memiliki tujuh sukarelawan di sini yang sama lebar dengan 396 00:14:56,010 --> 00:14:57,430 array kita bermain dengan sebelumnya. 397 00:14:57,430 --> 00:14:59,470 Dan saya memilih tujuh alasan yang akan hanya 398 00:14:59,470 --> 00:15:00,840 nyaman dalam sedikit. 399 00:15:00,840 --> 00:15:04,400 Dan aku akan mengusulkan yang pertama kita mengurutkan tujuh relawan. 400 00:15:04,400 --> 00:15:06,786 Jika Anda ingin, pertama, untuk menyapa sekalipun. 401 00:15:06,786 --> 00:15:08,970 Karena ini akan menjadi canggung beberapa menit. 402 00:15:08,970 --> 00:15:10,370 Memperkenalkan diri. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Hi, aku Grace. 404 00:15:10,980 --> 00:15:14,190 Saya seorang mahasiswa di Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Hi. 406 00:15:14,620 --> 00:15:15,620 Aku Branson. 407 00:15:15,620 --> 00:15:16,920 Saya seorang mahasiswa di Weld. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> Gabe: Hi. 410 00:15:20,230 --> 00:15:21,040 Aku Gabe. 411 00:15:21,040 --> 00:15:22,300 Saya junior di Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Aku Neil. 414 00:15:25,980 --> 00:15:29,090 Saya seorang mahasiswa di Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Saya Jason. 416 00:15:29,550 --> 00:15:32,816 Saya seorang mahasiswa di Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Aku Mike. 418 00:15:33,700 --> 00:15:37,360 Saya seorang mahasiswa di Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Aku Jess. 420 00:15:37,990 --> 00:15:40,313 Saya seorang mahasiswa di Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. Malan: Excellent. 422 00:15:41,300 --> 00:15:41,850 Baik. 423 00:15:41,850 --> 00:15:44,190 Nah, terima kasih kepada semua kami relawan di sini sejauh ini. 424 00:15:44,190 --> 00:15:47,110 Dan tantangan di tangan sekarang akan untuk memilah orang-orang ini, tapi kemudian 425 00:15:47,110 --> 00:15:50,250 kita akan harus berpikir sedikit keras tentang seberapa efisien kita benar-benar 426 00:15:50,250 --> 00:15:51,110 mengurutkannya. 427 00:15:51,110 --> 00:15:52,580 Jadi mari kita coba pertama ini. 428 00:15:52,580 --> 00:15:55,970 Kalian dapat melihat nomor masing-masing hanya dengan menempatkan sekitar sudut. 429 00:15:55,970 --> 00:15:59,380 Pergi ke depan dan mengambil beberapa detik, dan semacam dirimu dari terkecil di 430 00:15:59,380 --> 00:16:01,240 kiri ke terbesar di sebelah kanan. 431 00:16:01,240 --> 00:16:02,490 Go. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Baik. 435 00:16:08,030 --> 00:16:09,370 Itu benar-benar sangat cepat. 436 00:16:09,370 --> 00:16:14,040 Sekarang seseorang di sini, apa algoritma bahwa orang-orang yang diterapkan? 437 00:16:14,040 --> 00:16:14,900 >> SPEAKER 1: Sedikitnya untuk terbesar. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. Malan: OK. 439 00:16:15,000 --> 00:16:18,070 Setidaknya untuk terbesar benar-benar semacam ini obyektif, tapi aku tidak yakin itu 440 00:16:18,070 --> 00:16:18,890 benar-benar sebuah algoritma. 441 00:16:18,890 --> 00:16:21,810 Setidaknya untuk terbesar tidak memberitahu saya langkah-demi-langkah apa yang harus dilakukan. 442 00:16:21,810 --> 00:16:22,833 Ya? 443 00:16:22,833 --> 00:16:24,083 >> SPEAKER 1: [Tak terdengar] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. Malan: OK. 446 00:16:26,280 --> 00:16:28,920 Jadi jika Anda melihat seseorang lebih kecil dari nomor, kemudian pindah ke 447 00:16:28,920 --> 00:16:29,680 hak dari mereka. 448 00:16:29,680 --> 00:16:32,800 Jadi yang sekarang semakin ekspresif, lebih seperti sebuah algoritma, karena Anda 449 00:16:32,800 --> 00:16:35,410 bisa mengatakan, jika hal ini, maka itu. 450 00:16:35,410 --> 00:16:37,050 Jadi kita memiliki semacam membangun bersyarat. 451 00:16:37,050 --> 00:16:39,700 Dan orang-orang ini tampaknya melakukan itu beberapa kali, karena beberapa dari Anda pindah sedikit 452 00:16:39,700 --> 00:16:40,420 dari kejauhan. 453 00:16:40,420 --> 00:16:43,410 Jadi ada mungkin semacam looping terjadi dalam pikiran mereka. 454 00:16:43,410 --> 00:16:44,610 >> Tapi mari kita coba untuk meresmikan itu. 455 00:16:44,610 --> 00:16:47,540 Jika kalian bisa me-reset kembali untuk pengaturan ini. 456 00:16:47,540 --> 00:16:50,650 Mari kita lihat apakah kita tidak dapat memformalkan ini bit, dan kemudian mengajukan pertanyaan, hanya 457 00:16:50,650 --> 00:16:51,580 seberapa efisien ini? 458 00:16:51,580 --> 00:16:54,220 Tentu saja, ketika kita melakukan ini lebih lambat, itu akan merasa lebih baik dari 459 00:16:54,220 --> 00:16:57,210 algoritma, tapi mari kita lihat apakah kita bisa memasukkan jari kita pada langkah-langkah yang tepat. 460 00:16:57,210 --> 00:16:58,670 >> Jadi Anda dua orang empat dan dua. 461 00:16:58,670 --> 00:17:01,020 Atau Anda urutan yang benar atau salah? 462 00:17:01,020 --> 00:17:01,900 Jelas tidak benar. 463 00:17:01,900 --> 00:17:02,710 Jadi kita bertukar. 464 00:17:02,710 --> 00:17:05,170 Sekarang aku akan minggir di sini dan berkata, 4-6. 465 00:17:05,170 --> 00:17:06,240 Apakah Anda benar atau salah? 466 00:17:06,240 --> 00:17:06,599 >> Gabe: Benar. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. Malan: Benar. 468 00:17:07,180 --> 00:17:08,300 Enam dan satu? 469 00:17:08,300 --> 00:17:08,609 Tidak. 470 00:17:08,609 --> 00:17:09,630 Swap. 471 00:17:09,630 --> 00:17:10,490 Jadi itulah dua swap. 472 00:17:10,490 --> 00:17:11,710 Enam dan tiga? 473 00:17:11,710 --> 00:17:11,980 Tidak. 474 00:17:11,980 --> 00:17:13,000 Swap. 475 00:17:13,000 --> 00:17:13,930 Enam dan tujuh? 476 00:17:13,930 --> 00:17:14,630 Terlihat bagus. 477 00:17:14,630 --> 00:17:15,396 Tujuh dan lima? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [Tak terdengar] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. Malan: OK, swap. 480 00:17:17,089 --> 00:17:19,770 Dan diurutkan. 481 00:17:19,770 --> 00:17:19,980 Baik. 482 00:17:19,980 --> 00:17:21,440 Jadi jelas tidak, kan? 483 00:17:21,440 --> 00:17:22,470 Jadi ada yang lebih terjadi. 484 00:17:22,470 --> 00:17:24,920 Tapi, memang, orang-orang, bahkan hanya naluriah. 485 00:17:24,920 --> 00:17:25,450 terus bergerak. 486 00:17:25,450 --> 00:17:27,710 Mereka tidak berhenti begitu saja, setelah mereka dikoreksi satu masalah. 487 00:17:27,710 --> 00:17:27,839 Jadi. 488 00:17:27,839 --> 00:17:29,390 Memang, aku akan memiliki untuk melakukan hal yang sama. 489 00:17:29,390 --> 00:17:32,720 Aku akan harus semacam mundur kembali ke awal masalah ini, 490 00:17:32,720 --> 00:17:35,630 atau awal dari array ini orang, mari kita mulai memanggil mereka. 491 00:17:35,630 --> 00:17:38,366 >> Dan sekarang apa yang harus saya algoritma di kedua pass menjadi? 492 00:17:38,366 --> 00:17:39,220 >> SPEAKER 1: Sama saja. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. Malan: Sama saja. 494 00:17:39,940 --> 00:17:41,460 Dan ini, aku mulai suka, kan? 495 00:17:41,460 --> 00:17:44,720 Segera setelah Anda dapat menemukan diri Anda melakukan hal yang sama lagi dan lagi, itu 496 00:17:44,720 --> 00:17:47,890 menjadi lebih seperti sebuah algoritma, dan kurang naluri manusia. 497 00:17:47,890 --> 00:17:48,680 >> Jadi sekarang, di sini kita pergi lagi. 498 00:17:48,680 --> 00:17:49,870 Dua dan empat? 499 00:17:49,870 --> 00:17:50,220 Tidak. 500 00:17:50,220 --> 00:17:51,050 Empat dan satu? 501 00:17:51,050 --> 00:17:53,380 Ah, memang ada beberapa bekerja masih harus dilakukan. 502 00:17:53,380 --> 00:17:53,620 Untuk dan tiga? 503 00:17:53,620 --> 00:17:54,572 Baik. 504 00:17:54,572 --> 00:17:56,000 Empat dan enam? 505 00:17:56,000 --> 00:17:58,380 Enam dan lima? 506 00:17:58,380 --> 00:17:59,470 Enam dan tujuh? 507 00:17:59,470 --> 00:18:00,970 OK, sekarang, dilakukan. 508 00:18:00,970 --> 00:18:01,550 OK, tidak ada. 509 00:18:01,550 --> 00:18:02,710 Aku harus kembali. 510 00:18:02,710 --> 00:18:05,130 >> Jadi sekarang, sekali lagi, kita melakukan ini sedikit lebih sengaja. 511 00:18:05,130 --> 00:18:08,700 Dan sekarang, hanya ada satu otak eksekusi algoritma ini. 512 00:18:08,700 --> 00:18:10,290 Satu CPU, jika Anda mau. 513 00:18:10,290 --> 00:18:13,090 Dan terus terang, itulah satu-satunya sumber daya kita akan memiliki akses ke. 514 00:18:13,090 --> 00:18:16,280 Dan sekali kita kembali ke keyboard dan memiliki sesuatu seperti C pada kami 515 00:18:16,280 --> 00:18:19,600 pembuangan, kita hanya menulis program yang dapat melakukan satu hal pada suatu waktu. 516 00:18:19,600 --> 00:18:22,900 Padahal, orang-orang ini beberapa saat yang lalu, kami leveraged kekuatan otak kolektif mereka 517 00:18:22,900 --> 00:18:24,180 seperti kalian lakukan di minggu nol. 518 00:18:24,180 --> 00:18:24,980 Jadi mari kita terus melakukan hal ini. 519 00:18:24,980 --> 00:18:26,260 >> Dua dan satu. 520 00:18:26,260 --> 00:18:26,945 Dua dan tiga. 521 00:18:26,945 --> 00:18:27,460 Tiga dan empat. 522 00:18:27,460 --> 00:18:28,310 Empat dan lima. 523 00:18:28,310 --> 00:18:28,620 Lima dan enam. 524 00:18:28,620 --> 00:18:30,510 Enam dan tujuh. 525 00:18:30,510 --> 00:18:31,880 Selesai? 526 00:18:31,880 --> 00:18:34,560 Jadi saya, tapi biarkan aku bermain advokat setan. 527 00:18:34,560 --> 00:18:37,950 Apakah saya, jenis komputer yang hanya membuat lulus melalui array ini 528 00:18:37,950 --> 00:18:40,225 orang, tahu bahwa aku sudah selesai? 529 00:18:40,225 --> 00:18:40,670 >> SPEAKER 1: No 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. Malan: Jadi mengapa? 531 00:18:41,050 --> 00:18:46,900 Apa yang harus saya lakukan untuk menyimpulkan tegas bahwa saya lakukan? 532 00:18:46,900 --> 00:18:48,230 Mungkin satu lulus lagi. 533 00:18:48,230 --> 00:18:48,430 Benar? 534 00:18:48,430 --> 00:18:51,760 Karena semua saya tahu dari yang sebelumnya lulus adalah bahwa saya dikoreksi kesalahan. 535 00:18:51,760 --> 00:18:53,920 Dan itu berarti, mungkin ada masih kesalahan lain 536 00:18:53,920 --> 00:18:54,840 yang saya butuhkan untuk memperbaiki. 537 00:18:54,840 --> 00:18:58,680 Jadi saya hanya bisa yakin dengan memutar, dan kemudian memeriksa, 1-2, dua 538 00:18:58,680 --> 00:19:00,940 tiga, tiga dan empat, empat dan lima, lima dan enam, enam dan tujuh. 539 00:19:00,940 --> 00:19:02,510 OK, sekarang saya tidak melakukan pekerjaan. 540 00:19:02,510 --> 00:19:05,990 >> Aku pasti ingat bahwa saya tidak melakukan bekerja dengan sesuatu seperti variabel, 541 00:19:05,990 --> 00:19:06,975 seperti int. 542 00:19:06,975 --> 00:19:12,490 Sebut saja swap, dan jika swap adalah 0 setelah saya sampai di sini, dan itu dimulai pada 0, maka 543 00:19:12,490 --> 00:19:15,520 Aku hanya akan menjadi bodoh untuk terus bolak-balik, memeriksa lagi, dan 544 00:19:15,520 --> 00:19:16,450 lagi, dan lagi, kan? 545 00:19:16,450 --> 00:19:18,450 Karena Anda terjebak di beberapa jenis loop tak terbatas. 546 00:19:18,450 --> 00:19:21,250 Jadi, segera setelah ada 0 swap, kita dapat mengklaim bahwa ini 547 00:19:21,250 --> 00:19:23,810 Algoritma ini memang lengkap. 548 00:19:23,810 --> 00:19:25,400 >> Sekarang, mari kita menempatkan nama ini. 549 00:19:25,400 --> 00:19:28,930 Algoritma yang saya usulkan kita hanya diimplementasikan adalah sesuatu yang disebut gelembung 550 00:19:28,930 --> 00:19:32,800 semacam, yang dikenal sebagai tersebut dalam arti bahwa angka-angka yang agak lebih besar 551 00:19:32,800 --> 00:19:37,990 gelembung jalan mereka ke atas, atau naik ke akhir array angka. 552 00:19:37,990 --> 00:19:40,270 Tapi bagaimana efisien adalah algoritma ini? 553 00:19:40,270 --> 00:19:44,600 Berapa banyak langkah aku secara fisik harus mengambil, misalnya, untuk memilah ini 554 00:19:44,600 --> 00:19:45,850 tujuh manusia? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Empat sampai lima? 557 00:19:49,550 --> 00:19:51,420 OK, terlalu banyak pada akhirnya akan menjadi jawabannya. 558 00:19:51,420 --> 00:19:54,960 Tetapi bahkan kemudian, jumlah tertentu tidak begitu menarik. 559 00:19:54,960 --> 00:19:56,670 Mari kita generalisasi sebagai n. 560 00:19:56,670 --> 00:20:00,520 Jadi jika aku n orang di sini, dan mereka itu, semacam, dalam urutan acak di 561 00:20:00,520 --> 00:20:02,180 dimulai, dalam urutan asli. 562 00:20:02,180 --> 00:20:04,910 Nah, berapa banyak langkah yang saya punya untuk mengambil pada lulus pertama? 563 00:20:04,910 --> 00:20:09,810 Itu salah satu, dua, tiga, empat, lima, enam, dan mereka tujuh orang, sehingga 564 00:20:09,810 --> 00:20:13,670 itu adalah tujuh, enam -, sehingga n minus one langkah pertama kalinya. 565 00:20:13,670 --> 00:20:16,280 >> Sekarang, berapa banyak langkah yang saya punya untuk mengambil ketika saya memutar ulang? 566 00:20:16,280 --> 00:20:19,310 Nah, sebenarnya kita bisa dua kali lipat jika kita benar-benar ingin, tetapi untuk sekarang, aku 567 00:20:19,310 --> 00:20:22,300 hanya akan mengatakan, oke, lain n dikurangi 1. 568 00:20:22,300 --> 00:20:25,240 Jadi n dikurangi 1 akan mendapatkan menjengkelkan untuk melacak, jadi mari kita 569 00:20:25,240 --> 00:20:26,400 hanya mengumpulkan sedikit. 570 00:20:26,400 --> 00:20:27,770 Jadi 2n langkah. 571 00:20:27,770 --> 00:20:29,310 Jadi 14 langkah, memberi atau mengambil. 572 00:20:29,310 --> 00:20:31,930 >> Berapa kali saya ambil langkah waktu berikutnya? 573 00:20:31,930 --> 00:20:33,740 Nah, itu 3n. 574 00:20:33,740 --> 00:20:34,510 benar-benar. 575 00:20:34,510 --> 00:20:37,920 Dan sekarang, dalam kasus terburuk, untuk Misalnya, berapa kali akan saya 576 00:20:37,920 --> 00:20:41,730 pergi bolak-balik, bolak-balik, eksekusi algoritma ini, swapping 577 00:20:41,730 --> 00:20:44,620 orang pada setiap lulus, kira-kira? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Ini sebenarnya n kuadrat, kan? 580 00:20:50,010 --> 00:20:53,000 >> Karena dalam kasus terburuk, Anda dapat jenis dari berpikir tentang hal ini secara intuitif, 581 00:20:53,000 --> 00:20:54,800 meskipun mungkin mengambil sedikit sedikit waktu untuk meresap 582 00:20:54,800 --> 00:20:57,590 Dalam kasus terburuk, apa yang akan ini tujuh orang telah tampak seperti, di 583 00:20:57,590 --> 00:21:00,230 syarat dari perjanjian jumlah mereka? 584 00:21:00,230 --> 00:21:01,460 Benar-benar mundur, kan? 585 00:21:01,460 --> 00:21:02,815 Dan hanya untuk mensimulasikan itu, siapa nama Anda lagi? 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> DAVID J. Malan: Mike? 588 00:21:03,640 --> 00:21:08,100 OK, Mike, bisakah kau bergabung dengan saya di atas di sini untuk hanya satu detik? 589 00:21:08,100 --> 00:21:08,880 Sebenarnya, tidak. 590 00:21:08,880 --> 00:21:10,150 Maaf Mike, mari kita mundur. 591 00:21:10,150 --> 00:21:10,910 Apa nama Anda lagi? 592 00:21:10,910 --> 00:21:11,180 >> NEIL: Neil. 593 00:21:11,180 --> 00:21:11,640 >> DAVID J. Malan: Neil. 594 00:21:11,640 --> 00:21:13,750 OK, Neil, Anda datang dengan saya, jika Anda tidak keberatan. 595 00:21:13,750 --> 00:21:17,150 Jadi aku akan mengusulkan, hanya untuk kesederhanaan, bahwa Neil sekarang dalam bukunya 596 00:21:17,150 --> 00:21:18,510 mungkin kasus terburuk. 597 00:21:18,510 --> 00:21:20,720 Tapi mengingat bagaimana saya menerapkan algoritma saya. 598 00:21:20,720 --> 00:21:24,530 Saya membandingkan, membandingkan, membandingkan, membandingkan, membandingkan, oh. 599 00:21:24,530 --> 00:21:26,640 Sekarang orang-orang ini keluar ketertiban, jadi aku memperbaikinya. 600 00:21:26,640 --> 00:21:27,980 Jadi kalian bertukar. 601 00:21:27,980 --> 00:21:31,630 Tapi mempertimbangkan sekarang, seberapa jauh lagi Neil tidak harus pergi? 602 00:21:31,630 --> 00:21:32,690 Ini kira-kira n. 603 00:21:32,690 --> 00:21:33,570 Kau tahu, itu tidak benar-benar n. 604 00:21:33,570 --> 00:21:36,040 Ini seperti, n dikurangi 1, tapi aku mendapatkan melacak kesal kecil 605 00:21:36,040 --> 00:21:37,550 nomor, jadi mari kita sebut saja n. 606 00:21:37,550 --> 00:21:42,860 >> Jadi jika Neil bergerak satu langkah maksimal masing-masing waktu, dan untuk memindahkan Neil satu langkah, 607 00:21:42,860 --> 00:21:46,580 Saya harus membuat ini benar-benar membosankan lulus bolak-balik, ini kira-kira 608 00:21:46,580 --> 00:21:52,080 melakukan hal ini, n langkah, total n kali, karena itu akan membawa saya 609 00:21:52,080 --> 00:21:55,820 bahwa banyak langkah untuk mendapatkan Neil semua cara untuk mana ia berada. 610 00:21:55,820 --> 00:21:58,620 Jangankan orang lain jika kalian semua mis-memerintahkan juga. 611 00:21:58,620 --> 00:22:01,100 >> Jadi mari kita sebut bubble sort n kuadrat. 612 00:22:01,100 --> 00:22:04,860 Waktu berjalan dari algoritma ini, kinerja algoritma ini, 613 00:22:04,860 --> 00:22:07,120 efisiensi algoritma ini, kami hanya akan menjelaskan lebih 614 00:22:07,120 --> 00:22:08,800 umumnya sebagai n kuadrat. 615 00:22:08,800 --> 00:22:11,650 Yang bagus, karena saya bisa melakukan Contoh yang sama dengan delapan orang, sembilan 616 00:22:11,650 --> 00:22:15,450 orang, satu juta orang, dan bahwa Jawabannya tidak akan berubah. 617 00:22:15,450 --> 00:22:18,870 >> Jadi jika kalian tidak keberatan, mari kita ulang Anda ke tempat Anda memulai. 618 00:22:18,870 --> 00:22:22,510 Dan mari kita coba dua pendekatan lain dan melihat apakah kita tidak bisa melakukan fundamental 619 00:22:22,510 --> 00:22:23,820 lebih baik dari ini. 620 00:22:23,820 --> 00:22:27,130 Jadi, kali ini, saya akan mengusulkan semacam algoritma yang berbeda. 621 00:22:27,130 --> 00:22:29,950 Itu sangat pintar dari kita terakhir kali, dan kalian benar memiliki 622 00:22:29,950 --> 00:22:32,470 naluri kanan hanya jenis swapping berpasangan. 623 00:22:32,470 --> 00:22:36,500 Tapi kalau aku benar-benar ingin untuk pendekatan ini sederhana, dan tujuan saya adalah untuk memindahkan 624 00:22:36,500 --> 00:22:39,800 semua nomor kecil dengan cara ini, dan mendorong semua nomor besar yang 625 00:22:39,800 --> 00:22:43,030 way, kenapa tidak saya hanya melakukan itu di paling naif cara yang mungkin dan melihat apakah saya 626 00:22:43,030 --> 00:22:45,730 bisa lebih baik dari apa yang merupakan cukup algoritma yang kompleks? 627 00:22:45,730 --> 00:22:46,620 >> Jadi mari kita lihat. 628 00:22:46,620 --> 00:22:48,940 Empat adalah angka yang cukup kecil, jadi aku akan meninggalkan Anda di sana saat. 629 00:22:48,940 --> 00:22:50,610 Ooh, nomor dua adalah lebih baik. 630 00:22:50,610 --> 00:22:52,230 Jadi bisa Anda hanya melangkah maju sebentar? 631 00:22:52,230 --> 00:22:55,670 Ini adalah saat saya bernomor terkecil kandidat, dan aku akan ingat 632 00:22:55,670 --> 00:22:57,000 bahwa dengan, seperti, variabel. 633 00:22:57,000 --> 00:22:57,930 Tapi aku akan tetap memeriksa. 634 00:22:57,930 --> 00:22:59,890 Apakah ada seseorang yang nomor lebih kecil? 635 00:22:59,890 --> 00:23:00,460 Enam, no. 636 00:23:00,460 --> 00:23:01,390 Oh, ada Neil lagi. 637 00:23:01,390 --> 00:23:04,050 >> Jadi saya akan mendorong Anda kembali semacam konseptual. 638 00:23:04,050 --> 00:23:05,120 Neil akan datang ke depan. 639 00:23:05,120 --> 00:23:08,440 Dan sekarang, variabel yang saya gunakan untuk melacak yang memiliki terkecil 640 00:23:08,440 --> 00:23:11,390 Jumlah diperbarui mengandung Lokasi Neil. 641 00:23:11,390 --> 00:23:12,110 Nah, mari kita lihat. 642 00:23:12,110 --> 00:23:13,960 Tiga, tujuh, lima. 643 00:23:13,960 --> 00:23:15,590 Oke, aku tahu Neil adalah yang terkecil. 644 00:23:15,590 --> 00:23:18,110 Apa hal yang paling sederhana untuk saya lakukan sekarang? 645 00:23:18,110 --> 00:23:21,410 Aku tidak akan membuang-buang waktu saya dengan hanya menggelegak Neil satu tempat ke kiri. 646 00:23:21,410 --> 00:23:25,350 Mengapa saya tidak hanya menempatkan Neil mana ia milik, yang tentu saja di mana? 647 00:23:25,350 --> 00:23:26,160 >> Sepanjang perjalanan di awal. 648 00:23:26,160 --> 00:23:27,720 Jadi Neil, ikut aku. 649 00:23:27,720 --> 00:23:28,910 Dan apa nama Anda lagi? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Grace. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. Malan: Grace. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Jadi Grace, sayangnya, Anda jenis di jalan. 654 00:23:32,490 --> 00:23:34,290 Jadi bagaimana kita mengatasi masalah ini? 655 00:23:34,290 --> 00:23:34,490 Benar? 656 00:23:34,490 --> 00:23:37,500 Jika ini adalah sebuah array, ada hanya tujuh lokasi. 657 00:23:37,500 --> 00:23:40,830 Ingat bahwa, dengan Rob, kita berbicara tentang menyatakan usia, dan kami hanya memiliki 658 00:23:40,830 --> 00:23:41,740 jumlah terbatas usia? 659 00:23:41,740 --> 00:23:42,535 Ide yang sama di sini. 660 00:23:42,535 --> 00:23:44,300 Kami hanya memiliki jumlah terbatas ints. 661 00:23:44,300 --> 00:23:47,590 Rahmat adalah jenis di kami cara, jadi bagaimana kita memperbaikinya? 662 00:23:47,590 --> 00:23:49,555 >> Cara termudah adalah seperti, Grace, maaf. 663 00:23:49,555 --> 00:23:51,870 Anda akan harus pergi ke ada sehingga kita bisa membuat ruang. 664 00:23:51,870 --> 00:23:55,290 Sekarang, jika Anda berpikir tentang hal ini, mungkin kami hanya membuat masalah lebih buruk. 665 00:23:55,290 --> 00:23:58,510 Dan mungkin kita lakukan, karena bagaimana jika Rahmat berada di tempat yang tepat? 666 00:23:58,510 --> 00:24:01,730 Tapi kita tahu dia tidak, karena jika tidak, ia akan menjadi 667 00:24:01,730 --> 00:24:03,980 berdiri ke depan bukannya Neil saat ini, kan? 668 00:24:03,980 --> 00:24:05,550 Kami sudah memeriksa nomor keluar. 669 00:24:05,550 --> 00:24:05,770 >> Baik. 670 00:24:05,770 --> 00:24:09,110 Jadi sekarang, Neil ada di tempat yang tepat, dan Aku bisa melakukan optimasi sedikit. 671 00:24:09,110 --> 00:24:11,740 Untuk menit berikutnya, aku akan mengabaikan Neil semua bersama-sama, agar tidak 672 00:24:11,740 --> 00:24:15,280 membuang-buang waktu, atau tanpa sengaja menukar dia ke tempat yang salah. 673 00:24:15,280 --> 00:24:17,805 Jadi sekarang, bagaimana saya menemukan berikutnya elemen yang terkecil? 674 00:24:17,805 --> 00:24:18,480 Dua. 675 00:24:18,480 --> 00:24:20,225 Itu angka yang cukup baik, jika Anda ingin melangkah maju dan 676 00:24:20,225 --> 00:24:21,100 Aku akan mengingat Anda. 677 00:24:21,100 --> 00:24:21,980 Enam, tidak baik. 678 00:24:21,980 --> 00:24:24,820 Empat, tiga, tujuh, lima, tidak baik. 679 00:24:24,820 --> 00:24:26,800 Jadi biarkan aku memindahkan Anda ke tempat yang tepat Anda. 680 00:24:26,800 --> 00:24:28,470 Dan kita hanya beruntung saat ini. 681 00:24:28,470 --> 00:24:31,350 >> Sekarang, aku akan mengabaikan dua orang, dan sekarang melakukan satu lagi 682 00:24:31,350 --> 00:24:32,260 melewati ini. 683 00:24:32,260 --> 00:24:33,490 Enam, bahwa sejumlah cukup kecil. 684 00:24:33,490 --> 00:24:34,300 Ayo maju. 685 00:24:34,300 --> 00:24:35,220 Oh, maaf. 686 00:24:35,220 --> 00:24:37,640 Nomor Grace lebih baik, sehingga langkah di depan. 687 00:24:37,640 --> 00:24:38,260 Empat. 688 00:24:38,260 --> 00:24:39,120 Maaf, Grace. 689 00:24:39,120 --> 00:24:39,950 Kembali lagi. 690 00:24:39,950 --> 00:24:41,550 Nomor tiga adalah lebih baik. 691 00:24:41,550 --> 00:24:42,290 Tujuh. 692 00:24:42,290 --> 00:24:42,720 Lima. 693 00:24:42,720 --> 00:24:43,550 Dan sekarang apa nama Anda lagi? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. Malan: Jason. 696 00:24:44,420 --> 00:24:47,050 Jadi Jason kini terkecil Unsur Aku telah memilih. 697 00:24:47,050 --> 00:24:49,160 Mana dia akan pergi? 698 00:24:49,160 --> 00:24:50,380 Jadi di mana enam adalah. 699 00:24:50,380 --> 00:24:51,210 Dan nama Anda lagi? 700 00:24:51,210 --> 00:24:51,710 >> Gabe: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> DAVID J. Malan: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe ada di jalan. 703 00:24:53,220 --> 00:24:54,640 Apa hal termudah untuk melakukannya? 704 00:24:54,640 --> 00:24:58,390 Swap dua orang dan melanjutkan. 705 00:24:58,390 --> 00:24:59,020 Jadi sekarang mari kita lihat. 706 00:24:59,020 --> 00:25:00,170 Siapa yang terkecil? 707 00:25:00,170 --> 00:25:01,030 Empat. 708 00:25:01,030 --> 00:25:01,990 Biarkan aku hanya jenis cheat. 709 00:25:01,990 --> 00:25:03,090 Lima akan menjadi yang terkecil. 710 00:25:03,090 --> 00:25:05,220 Saya menemukan berikutnya, jika, Anda ingin melangkah ke depan, apa yang harus saya lakukan dengan 711 00:25:05,220 --> 00:25:06,820 orang-orang ini, dengan Gabe? 712 00:25:06,820 --> 00:25:08,450 Swap lagi. 713 00:25:08,450 --> 00:25:10,740 Jadi sekarang, masih sedikit rusak. 714 00:25:10,740 --> 00:25:14,140 Saya menemukan Gabe menjadi yang terkecil, sehingga Aku pop dia, memindahkan kalian atas. 715 00:25:14,140 --> 00:25:15,190 Dan dilakukan. 716 00:25:15,190 --> 00:25:17,200 >> Jadi jawabannya adalah sama. 717 00:25:17,200 --> 00:25:18,600 Hasil akhirnya adalah sama. 718 00:25:18,600 --> 00:25:22,730 Manakah dari kedua algoritma lebih baik? 719 00:25:22,730 --> 00:25:23,500 Yang kedua, saya mendengar. 720 00:25:23,500 --> 00:25:24,252 Kenapa? 721 00:25:24,252 --> 00:25:25,900 >> SPEAKER 3: Ini langkah n [Tak terdengar]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. Malan: Ini langkah n paling banyak. 723 00:25:27,600 --> 00:25:28,490 Menarik. 724 00:25:28,490 --> 00:25:30,610 Jadi, apakah itu meskipun? 725 00:25:30,610 --> 00:25:33,630 Jadi, bagaimana saya menemukan unsur terkecil? 726 00:25:33,630 --> 00:25:37,060 Berapa banyak langkah yang harus saya ambil yang menemukan elemen terkecil? 727 00:25:37,060 --> 00:25:39,220 Saya punya terlihat sepanjang jalan di akhir, kan? 728 00:25:39,220 --> 00:25:41,530 Karena dalam kasus terburuk, apa jika Neil di sini? 729 00:25:41,530 --> 00:25:45,700 Jadi hanya menemukan elemen terkecil membawaku n langkah, atau n dikurangi 1. 730 00:25:45,700 --> 00:25:46,100 Tapi, OK. 731 00:25:46,100 --> 00:25:46,980 Jadi memperbaiki Neil. 732 00:25:46,980 --> 00:25:48,740 Ingat bahwa, satu menit atau lebih yang lalu. 733 00:25:48,740 --> 00:25:51,680 >> Tapi bagaimana saya menemukan berikutnya unsur terkecil? 734 00:25:51,680 --> 00:25:54,830 Ini n dikurangi 1, atau n minus 2 benar-benar, dari sejumlah langkah. 735 00:25:54,830 --> 00:25:55,440 Jadi OK. 736 00:25:55,440 --> 00:25:57,390 Jadi aku n minus 2. 737 00:25:57,390 --> 00:25:57,600 Baik. 738 00:25:57,600 --> 00:25:59,130 Sehingga terasa sedikit lebih baik. 739 00:25:59,130 --> 00:25:59,730 Baik. 740 00:25:59,730 --> 00:26:03,270 Berapa banyak langkah waktu berikutnya untuk menemukan nomor tiga? 741 00:26:03,270 --> 00:26:04,420 Jadi n minus 4. 742 00:26:04,420 --> 00:26:07,670 Jadi itu menurun, satu lebih sedikit langkah pada setiap iterasi. 743 00:26:07,670 --> 00:26:08,740 Jadi ini tidak merasa lebih baik, kan? 744 00:26:08,740 --> 00:26:13,450 Jika terakhir kali itu kira-kira n kali n, kali ini n dikurangi 1, ditambah n dikurangi 745 00:26:13,450 --> 00:26:16,500 2, ditambah n dikurangi 3, ditambah n minus 4, titik, titik, titik. 746 00:26:16,500 --> 00:26:18,750 Tetapi jika Anda ingat dari sekolah tinggi Anda buku teks, cheat kecil 747 00:26:18,750 --> 00:26:24,380 lembar di bagian belakang yang memiliki formula, jika Anda menambahkan rangkaian angka, 748 00:26:24,380 --> 00:26:31,280 berapakah jumlah total langkah akan saya ambil di sini? 749 00:26:31,280 --> 00:26:36,580 >> Ini adalah salah satu dari mereka, seperti, n dikurangi 1, kali n, dibagi 2. 750 00:26:36,580 --> 00:26:39,040 Jadi biarkan aku melihat apakah saya bisa menarik up ini untuk sesaat. 751 00:26:39,040 --> 00:26:42,230 Dan lagi, aku agak pembulatan beberapa angka hanya untuk menjaga hidup kita sederhana, 752 00:26:42,230 --> 00:26:47,830 tapi seingat saya, itu adalah sesuatu seperti jika Saya lakukan n dikurangi 1 hal, maka n dikurangi 753 00:26:47,830 --> 00:26:53,570 2, maka n minus 3, itu kira-kira sesuatu seperti ini lebih dari 2, dan jika saya 754 00:26:53,570 --> 00:26:55,510 kalikan hal ini, itu sebenarnya n persegi. 755 00:26:55,510 --> 00:26:58,940 Itu tidak merasa terlalu baik. n dikurangi n lebih dari 2. 756 00:26:58,940 --> 00:27:00,350 >> Tapi ada satu hal. 757 00:27:00,350 --> 00:27:03,720 Dalam ilmu komputer, ketika masalah mulai mendapatkan menarik adalah ketika n 758 00:27:03,720 --> 00:27:04,700 akan benar-benar besar. 759 00:27:04,700 --> 00:27:08,110 Dan ketika n jadi sangat besar, yang dari nilai-nilai ini akan mendominasi semua 760 00:27:08,110 --> 00:27:09,750 dari yang lain? 761 00:27:09,750 --> 00:27:10,990 Ini semacam n kuadrat, kan? 762 00:27:10,990 --> 00:27:13,340 Ya, membaginya dengan 2 cukup bagus. 763 00:27:13,340 --> 00:27:16,740 Tetapi jika Anda sedang berbicara tentang miliaran dari bagian data, atau triliunan 764 00:27:16,740 --> 00:27:18,700 bagian data, OK, jadi Anda dua kali lebih cepat. 765 00:27:18,700 --> 00:27:22,440 Tapi siapa yang benar-benar peduli jika itu angka yang besar, jika faktor ini adalah apa yang 766 00:27:22,440 --> 00:27:23,040 besar dan lebih besar. 767 00:27:23,040 --> 00:27:25,990 Dan tentunya, itu membuat lebih dari perbedaan dari orang ini. 768 00:27:25,990 --> 00:27:29,120 Jadi meskipun kalian benar, algoritma kedua, kita akan menyebutnya 769 00:27:29,120 --> 00:27:32,970 selection sort, adalah, dalam dunia nyata, bit lebih cepat berpotensi, karena saya 770 00:27:32,970 --> 00:27:35,360 mengambil sedikit dan lebih sedikit langkah setiap kali. 771 00:27:35,360 --> 00:27:37,340 >> Ini tidak benar-benar fundamental lebih cepat. 772 00:27:37,340 --> 00:27:41,430 Karena jika kita benar-benar bermain ini untuk nilai-nilai n yang besar, pada akhir 773 00:27:41,430 --> 00:27:44,750 hari, untuk cukup besar n, itu masih akan merasa cukup lambat. 774 00:27:44,750 --> 00:27:46,770 Nah, biarkan aku mengambil satu lulus terakhir pada saat itu. 775 00:27:46,770 --> 00:27:48,920 Itulah apa yang saya sebut selection sort. 776 00:27:48,920 --> 00:27:51,040 Bisakah kalian ulang dirimu untuk terakhir kalinya? 777 00:27:51,040 --> 00:27:53,550 Dan dalam kasus terakhir ini, aku akan untuk mengusulkan sesuatu 778 00:27:53,550 --> 00:27:54,970 disebut insertion sort. 779 00:27:54,970 --> 00:27:57,470 Insertion sort ini, secara konseptual, sedikit berbeda. 780 00:27:57,470 --> 00:28:00,980 >> Daripada pergi bolak-balik dan memilih elemen terkecil, aku 781 00:28:00,980 --> 00:28:05,030 hanya akan berurusan dengan masing-masing orang seperti saya bertemu dengan mereka, dan masukkan 782 00:28:05,030 --> 00:28:06,850 mereka ke tempat yang benar. 783 00:28:06,850 --> 00:28:10,160 Jadi aku hanya akan mulai dengan Grace, dan saya melihat bahwa dia nomor empat. 784 00:28:10,160 --> 00:28:11,720 Di mana nomor empat milik? 785 00:28:11,720 --> 00:28:14,940 Aku belum mulai memilah apa-apa, sehingga Rahmat mendapat untuk tinggal di sana. 786 00:28:14,940 --> 00:28:18,355 Dan sekarang aku akan mengklaim, jika Anda bisa mengambil langkah ke kanan, ini 787 00:28:18,355 --> 00:28:21,650 daftar diurutkan, ini adalah saya Daftar tersisa disortir. 788 00:28:21,650 --> 00:28:23,260 Jadi sekarang aku akan melanjutkan berikutnya, dan apa nama Anda lagi? 789 00:28:23,260 --> 00:28:23,700 >> BRANSON: Branson. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. Malan: Branson. 791 00:28:24,150 --> 00:28:25,375 Jadi Branson adalah nomor dua. 792 00:28:25,375 --> 00:28:27,490 Jadi aku akan membawa Anda keluar sejenak. 793 00:28:27,490 --> 00:28:30,940 Dan sekarang, di mana Anda berada dalam array ini? 794 00:28:30,940 --> 00:28:32,360 Jadi di sebelah kanan Grace. 795 00:28:32,360 --> 00:28:35,670 Jadi sekali lagi, kita semacam membuat Rahmat melakukan banyak pekerjaan di sini. 796 00:28:35,670 --> 00:28:37,290 Di mana kita menempatkan Anda? 797 00:28:37,290 --> 00:28:40,120 Jadi kita akan geser Anda ke kiri, dan masukkan Branson sana. 798 00:28:40,120 --> 00:28:41,680 Tapi sekarang saya menyatakan bahwa kalian selesai. 799 00:28:41,680 --> 00:28:43,240 Tapi perhatikan, aku tidak menggunakan ruang ekstra. 800 00:28:43,240 --> 00:28:45,130 Ini masih 2 elemen di sini, di sini 5. 801 00:28:45,130 --> 00:28:47,910 Jumlah ukuran array adalah 7, jadi saya tidak curang, oke? 802 00:28:47,910 --> 00:28:51,950 >> Jadi sekarang kita miliki, dengan Gabe sini, para nomor enam, di mana Anda berada? 803 00:28:51,950 --> 00:28:52,650 Anda beruntung lagi. 804 00:28:52,650 --> 00:28:53,820 Jadi Anda bisa tinggal di sana. 805 00:28:53,820 --> 00:28:57,210 Hanya mengambil langkah sedikit ke kanan hanya untuk membuat jelas bahwa Anda diurutkan. 806 00:28:57,210 --> 00:29:00,520 Dan sekarang kami memiliki Neil lagi, nomor satu, ke mana Anda pergi? 807 00:29:00,520 --> 00:29:03,540 Dan sekarang adalah di mana kita akan mulai melihat bahwa algoritma ini, meskipun pada pertama 808 00:29:03,540 --> 00:29:05,950 sekilas, terasa cukup pintar, menonton apa yang akan terjadi. 809 00:29:05,950 --> 00:29:07,370 Jika Anda bisa melangkah maju. 810 00:29:07,370 --> 00:29:09,260 >> Di mana kita ingin menempatkan Neil? 811 00:29:09,260 --> 00:29:11,830 Jadi jelas di sini, jadi bagaimana kita mendapatkan Neil sana? 812 00:29:11,830 --> 00:29:12,970 Mari kita lakukan ini langkah-demi-langkah. 813 00:29:12,970 --> 00:29:15,620 Gabe, di mana Anda harus pergi? 814 00:29:15,620 --> 00:29:19,590 Yap, jadi mengambil satu langkah besar, atau dua setengah-langkah untuk membuat 815 00:29:19,590 --> 00:29:20,820 satu langkah di sana. 816 00:29:20,820 --> 00:29:21,750 Grace, di mana Anda pergi? 817 00:29:21,750 --> 00:29:22,510 Baik. 818 00:29:22,510 --> 00:29:23,500 Jadi langkah lain. 819 00:29:23,500 --> 00:29:24,960 Dan akhirnya, Branson? 820 00:29:24,960 --> 00:29:25,460 Langkah lain. 821 00:29:25,460 --> 00:29:27,190 Dan sekarang kita dapat menempatkan Neil ke tempatnya. 822 00:29:27,190 --> 00:29:28,440 >> Jadi sekarang, lanjutkan logika ini. 823 00:29:28,440 --> 00:29:32,420 Meskipun kita tidak bergeser Neil lebih, dan lebih, dan lebih, untuk menempatkan dia 824 00:29:32,420 --> 00:29:36,420 mana ia pergi, dalam kasus terburuk, nomor berikutnya mungkin kita hadapi bisa 825 00:29:36,420 --> 00:29:42,220 menjadi nomor, mengatakan, ada sejumlah nol, maka kita akan menggeser semua 826 00:29:42,220 --> 00:29:42,730 orang-orang ini. 827 00:29:42,730 --> 00:29:44,950 Misalkan ada sejumlah, negatif satu, maka kita harus bergeser 828 00:29:44,950 --> 00:29:46,080 semua orang-orang ini. 829 00:29:46,080 --> 00:29:48,500 Jadi kami benar-benar hanya semacam membalik masalah sekitar, sehingga kita 830 00:29:48,500 --> 00:29:52,620 mentransfer beban dari proses seleksi sehingga penyisipan 831 00:29:52,620 --> 00:29:56,930 proses, sehingga kalian hanya punya untuk bergerak kira-kira n dikurangi sesuatu 832 00:29:56,930 --> 00:29:57,940 sejumlah langkah. 833 00:29:57,940 --> 00:30:01,200 Dan bahwa sejumlah langkah hanya akan meningkat karena saya memilih nomor lainnya, 834 00:30:01,200 --> 00:30:04,730 jika saya harus terus mendorong kalian kembali, dan kembali, dan kembali. 835 00:30:04,730 --> 00:30:08,320 >> Jadi hal yang menyedihkan sekarang adalah semua ini algoritma n kuadrat. 836 00:30:08,320 --> 00:30:10,570 Mari kita pergi ke depan dan berkat ini guys, dan memvisualisasikan sedikit 837 00:30:10,570 --> 00:30:11,090 berbeda. 838 00:30:11,090 --> 00:30:12,312 Sangat baik dilakukan. 839 00:30:12,312 --> 00:30:14,120 >> [Tepuk Tangan] 840 00:30:14,120 --> 00:30:15,030 >> Baik. 841 00:30:15,030 --> 00:30:16,280 Di sana Anda pergi. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Terima kasih untuk - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [Tak terdengar] menjaga angka. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. Malan: Tidak, Anda mungkin menjaga angka juga. 846 00:30:21,990 --> 00:30:23,440 Baik. 847 00:30:23,440 --> 00:30:24,100 Baik dilakukan. 848 00:30:24,100 --> 00:30:25,300 Baik. 849 00:30:25,300 --> 00:30:30,510 Jadi mari kita lihat apakah kita tidak bisa sekarang meringkas lebih cepat, dan lebih visual, 850 00:30:30,510 --> 00:30:33,410 apa yang baru saja terjadi di sini sebagai berikut. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Aku akan pergi ke depan dan menarik Firefox. 853 00:30:38,770 --> 00:30:41,310 Kami akan menghubungkan demonstrasi ini di website kursus itu. 854 00:30:41,310 --> 00:30:43,870 Java adalah sedikit mengganggu untuk mendapatkan kerja di beberapa browser hari ini. 855 00:30:43,870 --> 00:30:46,760 Jadi jika Anda bermain dengan ini di rumah, menyadari bahwa Anda mungkin perlu menggunakan Firefox 856 00:30:46,760 --> 00:30:47,990 untuk mendapatkannya bekerja. 857 00:30:47,990 --> 00:30:50,440 Dan apa yang akan saya lakukan dengan ini demonstrasi adalah sebagai berikut. 858 00:30:50,440 --> 00:30:54,875 >> Di bagian bawah, saya memiliki sejumlah besar pilihan menu, termasuk start dan 859 00:30:54,875 --> 00:30:55,840 tombol berhenti. 860 00:30:55,840 --> 00:30:59,450 Juga, sebagai samping, tampaknya ada sebuah bug dalam program ini, dimana Anda 861 00:30:59,450 --> 00:31:03,720 tidak bisa benar-benar melihat awal atau menghentikan tombol kecuali Anda memegang Command atau Alt 862 00:31:03,720 --> 00:31:06,560 plus dan zoom in, yang anehnya menunjukkan lebih banyak tombol. 863 00:31:06,560 --> 00:31:09,090 FYI Jadi jika Anda bermain dengan ini di rumah. 864 00:31:09,090 --> 00:31:12,870 Sekarang aku akan klik Start hanya dalam saat, setelah menentukan penundaan, 865 00:31:12,870 --> 00:31:16,810 seperti, 200 milidetik di sini, hanya sehingga kita bisa melihat apa yang terjadi. 866 00:31:16,810 --> 00:31:20,180 >> Jadi saya mengklaim bahwa ini adalah visualisasi dari algoritma pertama 867 00:31:20,180 --> 00:31:23,730 orang-orang itu, bubble sort, dimana kami bertukar orang berpasangan. 868 00:31:23,730 --> 00:31:27,490 Wawasan kunci visualisasi ini adalah bahwa tinggi bar 869 00:31:27,490 --> 00:31:30,510 merupakan ukuran nomor. 870 00:31:30,510 --> 00:31:32,210 Jadi lebih tinggi bar, besar angkanya. 871 00:31:32,210 --> 00:31:33,680 Shorter bar, lebih kecil jumlahnya. 872 00:31:33,680 --> 00:31:38,630 Dan jika Anda perhatikan, kita akan melalui iterasi pertama algoritma ini, 873 00:31:38,630 --> 00:31:42,620 swapping jumlah besar dan kecil, sehingga sejumlah kecil datang pertama dan 874 00:31:42,620 --> 00:31:44,280 jumlah yang besar pergi ke kanan. 875 00:31:44,280 --> 00:31:48,770 >> Dan segera setelah kami mendapatkan akhir array banyak lebih dari tujuh nomor, kami 876 00:31:48,770 --> 00:31:49,900 akan kembali ke awal. 877 00:31:49,900 --> 00:31:51,140 Dan mengantisipasi ini. 878 00:31:51,140 --> 00:31:54,860 Di paling kiri, bahwa si kecil akan untuk swap ke samping, dan ini 879 00:31:54,860 --> 00:31:56,010 Proses berulang. 880 00:31:56,010 --> 00:31:59,450 Sekarang visualisasi ini dengan cepat mendapat membosankan, jadi biarkan aku pergi ke depan dan berhenti 881 00:31:59,450 --> 00:32:04,170 , ubah delay sesuatu yang jauh cepat hanya untuk mendapatkan sekarang, merasakan 882 00:32:04,170 --> 00:32:05,060 algoritma ini. 883 00:32:05,060 --> 00:32:07,840 >> Jadi meskipun aku sudah melesat itu, ini adalah seperti upgrade prosesor saya, membeli 884 00:32:07,840 --> 00:32:08,580 komputer baru. 885 00:32:08,580 --> 00:32:12,980 Saya belum berubah secara mendasar saya algoritma, tapi Anda memang bisa melihat lebih banyak 886 00:32:12,980 --> 00:32:16,800 jelas daripada dengan manusia, bahwa besar nomor menggelegak ke atas, 887 00:32:16,800 --> 00:32:20,900 dan jumlah kecil menggelegak turun ke bawah. 888 00:32:20,900 --> 00:32:22,390 Dan sekarang hal ini di sini diurutkan. 889 00:32:22,390 --> 00:32:25,260 Dan sebagai samping, dalam kotak, ada hanya beberapa pembukuan sana untuk 890 00:32:25,260 --> 00:32:28,010 membantu Anda menghitung berapa banyak perbandingan, atau berapa banyak swap memiliki 891 00:32:28,010 --> 00:32:28,950 sebenarnya sudah dilakukan. 892 00:32:28,950 --> 00:32:30,750 >> Nah, mari kita mencoba salah satu yang lain kita melihat. 893 00:32:30,750 --> 00:32:37,116 Mari saya klik pada bubble sort sini, dan membiarkan saya memilih, dan ini halaman web secara keseluruhan 894 00:32:37,116 --> 00:32:38,936 adalah sedikit buggy. 895 00:32:38,936 --> 00:32:41,155 Mari kita menerima risiko dan jalankan lagi. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Di sana kami pergi. 898 00:32:45,030 --> 00:32:47,180 Jadi mari kita melakukan semacam seleksi. 899 00:32:47,180 --> 00:32:49,140 Aku tidak tahu mengapa menu muncul di sana. 900 00:32:49,140 --> 00:32:54,070 Mari kita zoom in untuk memperbaikinya bug, mengubahnya ke 50. 901 00:32:54,070 --> 00:32:56,020 Ah, mari kita benar-benar melakukan yang jauh lebih cepat. 902 00:32:56,020 --> 00:32:59,160 Lima milidetik atau lebih, dan Start. 903 00:32:59,160 --> 00:33:00,470 >> Jadi ini adalah semacam seleksi. 904 00:33:00,470 --> 00:33:03,070 Jadi sekali lagi, berpikir tentang apa yang kita lakukan dengan manusia di sini. 905 00:33:03,070 --> 00:33:08,490 Kami pergi melalui array dan dipilih elemen terkecil lagi, 906 00:33:08,490 --> 00:33:09,250 dan lagi, dan lagi. 907 00:33:09,250 --> 00:33:11,110 Sekarang saya menyatakan bahwa masih sangat buruk. 908 00:33:11,110 --> 00:33:15,010 Itu masih n kuadrat, memberi atau mengambil, tapi itu, di dunia nyata, sedikit 909 00:33:15,010 --> 00:33:18,280 lebih cepat, karena saya memang mengambil sedikit lebih sedikit langkah setiap waktu. 910 00:33:18,280 --> 00:33:19,800 Tapi kita hanya berbicara apa? 911 00:33:19,800 --> 00:33:21,830 Mungkin 40 atau jadi bar di sini? 912 00:33:21,830 --> 00:33:23,200 Kita tidak berbicara 40 juta. 913 00:33:23,200 --> 00:33:27,430 Jadi itu tidak benar-benar jelas bagi saya bahwa memang keuntungan yang signifikan. 914 00:33:27,430 --> 00:33:32,530 >> Sekarang saya kembali dan mengubah kami algoritma ketiga, yang pilih 915 00:33:32,530 --> 00:33:33,180 insertion sort. 916 00:33:33,180 --> 00:33:36,380 Dan sekarang itu benar-benar kereta karena Menu benar-benar tidak harus di sana. 917 00:33:36,380 --> 00:33:40,840 Jadi sekarang kita akan gulir kembali ke sini dan mulai algoritma ini. 918 00:33:40,840 --> 00:33:43,270 Whoop, mulai dan berhenti. 919 00:33:43,270 --> 00:33:47,160 Jadi ini satu jenis memiliki pola yang cukup untuk itu, dimana kita lagi 920 00:33:47,160 --> 00:33:50,240 memasukkan manusia, atau kasus ini, bar menjadi 921 00:33:50,240 --> 00:33:52,620 lokasi yang sesuai mereka. 922 00:33:52,620 --> 00:33:55,430 Dan itu sudah dilakukan sebelum Aku berbalik. 923 00:33:55,430 --> 00:33:58,940 Tapi yang satu ini juga, secara teori, masih n kuadrat. 924 00:33:58,940 --> 00:34:01,430 >> Jadi mari kita lihat jika kita tidak bisa meringkas tersebut sebagai berikut. 925 00:34:01,430 --> 00:34:04,750 Aku akan pergi ke depan dan hanya untuk memberikan kita semacam cara umum berbicara 926 00:34:04,750 --> 00:34:08,489 tentang hal ini, izinkan saya memperkenalkan hanya sedikit notasi sini. 927 00:34:08,489 --> 00:34:12,480 Kau akan melihat sesuatu yang disebut besar O, karena secara harfiah besar 928 00:34:12,480 --> 00:34:16,320 O. Dan ini adalah cara yang komputer ilmuwan atau ahli matematika bahkan menggunakan 929 00:34:16,320 --> 00:34:19,230 untuk menggambarkan waktu berjalan dari beberapa algoritma. 930 00:34:19,230 --> 00:34:21,400 Berapa banyak langkah apakah itu benar-benar mengambil? 931 00:34:21,400 --> 00:34:25,080 >> Sekarang aku akan mempermalukan diri sendiri dengan tulisan tangan saya di sini hanya dalam beberapa saat. 932 00:34:25,080 --> 00:34:29,020 Tapi biarkan aku pergi ke depan dan mengatakan bahwa ini akan menjadi O besar di sini. 933 00:34:29,020 --> 00:34:33,610 Dan biarkan saya memperkenalkan satu lagi simbol, omega modal. 934 00:34:33,610 --> 00:34:37,080 Omega akan menjadi sebaliknya, dasarnya, dari big O. Sedangkan O besar 935 00:34:37,080 --> 00:34:40,790 berarti, dalam kasus terburuk, berapa banyak waktu mungkin beberapa algoritma ambil, di 936 00:34:40,790 --> 00:34:43,480 hal n, omega akan menjadi berapa banyak waktu mungkin itu 937 00:34:43,480 --> 00:34:45,409 mengambil dalam kasus terbaik. 938 00:34:45,409 --> 00:34:48,090 Dan kita akan melihat apa yang kita maksud dengan kasus terbaik hanya dalam beberapa saat. 939 00:34:48,090 --> 00:34:49,940 >> Jadi mari kita mulai sesuatu yang sederhana. 940 00:34:49,940 --> 00:34:54,719 Mari saya mulai dengan pencarian linear. 941 00:34:54,719 --> 00:34:55,679 Jadi tidak penyortiran. 942 00:34:55,679 --> 00:34:58,000 Kita akan menyebutnya pencarian linear. 943 00:34:58,000 --> 00:35:01,140 Dan sekarang, membuat sedikit tabel keluar dari ini. 944 00:35:01,140 --> 00:35:06,600 Dan sekarang, dalam kasus pencarian linear, dalam kasus terburuk, berapa banyak langkah yang 945 00:35:06,600 --> 00:35:11,770 itu akan membawa saya untuk menemukan jumlah pilihan sewenang-wenang? 946 00:35:11,770 --> 00:35:14,540 Dan ada jumlah pintu n atau n jumlah total. 947 00:35:14,540 --> 00:35:15,940 Kasus terburuk. 948 00:35:15,940 --> 00:35:18,800 Berapa banyak langkah yang akan saya harus ambil untuk mencari nomor 50 dalam array 949 00:35:18,800 --> 00:35:20,830 n pintu? 950 00:35:20,830 --> 00:35:21,410 Dan mengapa? 951 00:35:21,410 --> 00:35:23,680 Karena mungkin semua cara di atas ke akhir. 952 00:35:23,680 --> 00:35:27,120 Begitu banyak seperti Jennifer dihadapi, nomor 50 itu semua cara di atas, sehingga dalam 953 00:35:27,120 --> 00:35:30,760 kasus terburuk pencarian linear adalah O besar n, kita akan mengatakan. 954 00:35:30,760 --> 00:35:33,430 >> Bagaimana dengan kasus terbaik, jika Anda benar-benar beruntung? 955 00:35:33,430 --> 00:35:36,200 Ini hanya akan mengambil satu langkah, atau sejumlah konstan langkah. 956 00:35:36,200 --> 00:35:37,830 Jadi kami akan menjelaskan bahwa sebagai 1. 957 00:35:37,830 --> 00:35:39,010 Jadi ini cukup baik. 958 00:35:39,010 --> 00:35:41,210 Sekarang bagaimana jika kita melakukan sesuatu seperti pencarian biner? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Jadi pencarian biner, yang terburuk kasus, mengambil berapa banyak waktu? 961 00:35:47,846 --> 00:35:49,250 >> [Interposing SUARA] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. Malan: Jadi sebenarnya, saya mendengarnya di beberapa tempat. 963 00:35:51,310 --> 00:35:56,390 Jadi itu benar-benar log n, memberi atau mengambil, karena seperti yang kita membagi daftar dalam setengah 964 00:35:56,390 --> 00:36:00,730 lagi, dan lagi, dan lagi, kami dapat untuk menemukan, pada akhirnya, nilai, 965 00:36:00,730 --> 00:36:04,750 jika itu ada, tapi ada menangkap. 966 00:36:04,750 --> 00:36:08,590 Apa asumsi bahwa kita harus mengambil untuk diberikan untuk pencarian biner? 967 00:36:08,590 --> 00:36:09,700 Itu harus diurutkan. 968 00:36:09,700 --> 00:36:12,770 Ini tidak diurutkan, Anda dapat membagi hal dalam setengah lagi dan lagi, dan Anda 969 00:36:12,770 --> 00:36:15,490 bisa ke kiri, dan Anda dapat pergi ke kanan, dan Anda dapat pergi kiri dan kanan, tapi kau 970 00:36:15,490 --> 00:36:18,070 tidak akan menemukan elemen jika Daftar ini tidak diurutkan, karena 971 00:36:18,070 --> 00:36:18,790 Anda mungkin kehilangan itu. 972 00:36:18,790 --> 00:36:22,120 Karena heuristik Anda, untuk pergi kiri atau kanan yang akan cacat jika 973 00:36:22,120 --> 00:36:23,420 memang tidak diurutkan. 974 00:36:23,420 --> 00:36:26,110 Jadi ada semacam biaya tersembunyi menggunakan sesuatu seperti ini. 975 00:36:26,110 --> 00:36:29,250 >> Sekarang, mari kita pergi ke pemilahan kami algoritma tidak mencari - 976 00:36:29,250 --> 00:36:31,140 oh, benar-benar membiarkan kita masuk kosong. 977 00:36:31,140 --> 00:36:33,190 Pencarian biner dalam kasus terbaik? 978 00:36:33,190 --> 00:36:36,290 Ini juga 1 jika itu hanya kebetulan di bagian paling tengah dari array, atau 979 00:36:36,290 --> 00:36:37,810 tengah buku telepon. 980 00:36:37,810 --> 00:36:39,710 Sekarang mari kita lakukan bubble sort. 981 00:36:39,710 --> 00:36:42,570 Jadi sekali lagi, sekarang kita memasuki macam, bukan pencarian. 982 00:36:42,570 --> 00:36:47,220 >> Dalam kasus terburuk, berapa banyak langkah yang kita klaim bubble sort akan mengambil? 983 00:36:47,220 --> 00:36:48,410 n kuadrat. 984 00:36:48,410 --> 00:36:49,200 Jadi aku akan menggambar itu. 985 00:36:49,200 --> 00:36:51,710 Ooh, tulisan tangan saya terlihat lebih buruk ketika itu diproyeksikan sebesar itu. 986 00:36:51,710 --> 00:36:52,510 Baik. 987 00:36:52,510 --> 00:36:53,570 Jadi itu n kuadrat. 988 00:36:53,570 --> 00:36:59,460 Dan dalam kasus terbaik dari bubble sort, berapa banyak langkah itu akan berlangsung? 989 00:36:59,460 --> 00:37:00,980 1, aku mendengar. 990 00:37:00,980 --> 00:37:01,760 >> SPEAKER 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. Malan: n, aku mendengar. 992 00:37:03,286 --> 00:37:04,200 >> SPEAKER 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. Malan: 2, saya mendengar. 994 00:37:05,010 --> 00:37:06,670 Apakah saya mendengar 3? 995 00:37:06,670 --> 00:37:07,080 Baik. 996 00:37:07,080 --> 00:37:11,390 Begitulah yang saya dengar 1, n, 2, tetapi mari kita memilih terpisah setidaknya pertama mereka 997 00:37:11,390 --> 00:37:12,330 saran, 1. 998 00:37:12,330 --> 00:37:15,370 Ini bukan naluri buruk, karena itu jenis mengikuti pola di sini. 999 00:37:15,370 --> 00:37:19,670 Tapi jika hanya membutuhkan 1 langkah, bagaimana dalam dunia bisa saya mengklaim bahwa daftar 1000 00:37:19,670 --> 00:37:22,900 diurutkan, karena jika saya hanya diperbolehkan untuk mengambil 1 langkah, berapa banyak elemen 1001 00:37:22,900 --> 00:37:25,230 Aku benar-benar bisa memeriksa untuk memastikan? 1002 00:37:25,230 --> 00:37:28,270 Yah, hanya 1, yang berarti ada n dikurangi 1 elemen yang bisa keluar dari 1003 00:37:28,270 --> 00:37:31,310 ketertiban, dan aku hanya akan pada iman setelah melihat 1 elemen yang 1004 00:37:31,310 --> 00:37:31,850 hal yang diurutkan. 1005 00:37:31,850 --> 00:37:33,930 Jadi 1 yang tidak benar di sini. 1006 00:37:33,930 --> 00:37:35,710 Jadi minimal, berapa banyak aku harus melihat? 1007 00:37:35,710 --> 00:37:36,680 >> [Interposing SUARA] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. Malan: n dikurangi 1, atau benar-benar, n, karena saya perlu melihat setiap 1009 00:37:40,160 --> 00:37:42,190 Unsur memastikan bahwa itu tidak rusak. 1010 00:37:42,190 --> 00:37:44,750 Tapi sekali lagi, kita akan mengurutkan gelombang kami tangan di angka yang lebih kecil dan 1011 00:37:44,750 --> 00:37:47,100 berasumsi bahwa, sebagai n mendapat besar, mereka menarik pula. 1012 00:37:47,100 --> 00:37:48,380 Jadi itulah bubble sort. 1013 00:37:48,380 --> 00:37:49,830 Dan sekarang, mari kita lakukan ini dua terakhir. 1014 00:37:49,830 --> 00:37:53,520 Selection sort, dan kemudian kita akan melakukan insertion sort. 1015 00:37:53,520 --> 00:37:57,160 Dan kemudian kita akan meniup Anda pikiran dengan sesuatu yang jauh 1016 00:37:57,160 --> 00:37:58,926 lebih baik dari semua ini. 1017 00:37:58,926 --> 00:38:00,410 Baik. 1018 00:38:00,410 --> 00:38:04,700 >> Apa kasus terburuk berjalan waktu selection sort? 1019 00:38:04,700 --> 00:38:05,680 >> SPEAKER 4: n kuadrat. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. Malan: n persegi, kudengar. 1021 00:38:06,710 --> 00:38:09,790 Tapi mengapa n kuadrat, intuitif? 1022 00:38:09,790 --> 00:38:11,170 >> SPEAKER 4: Karena kami hanya melakukannya. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. Malan: Karena kami hanya melakukannya. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Jawaban yang bagus. 1026 00:38:13,380 --> 00:38:16,660 Tapi intuitif, mengapa pemilihan semacam n kuadrat? 1027 00:38:16,660 --> 00:38:18,980 Apa yang harus kita lakukan lagi dan lagi? 1028 00:38:18,980 --> 00:38:22,570 Kita harus menjaga pemindaian melalui, adalah Anda yang terkecil, adalah Anda 1029 00:38:22,570 --> 00:38:24,020 terkecil, kau yang terkecil. 1030 00:38:24,020 --> 00:38:27,480 Dan memang, kita mampu mengambil n langkah, maka n dikurangi 1, maka n minus 2. 1031 00:38:27,480 --> 00:38:30,700 Tetapi jika Anda jenis menambahkan mereka semuanya, atau mengambil pada iman bahwa saya telah menambahkan 1032 00:38:30,700 --> 00:38:34,810 mereka di muka, kita mendapatkan kira-kira n kuadrat minus beberapa nomor lebih kecil. 1033 00:38:34,810 --> 00:38:36,730 Jadi aku akan menelepon n kuadrat ini. 1034 00:38:36,730 --> 00:38:39,530 Tetapi dengan semacam seleksi yang terbaik kasus, berapa banyak langkah itu 1035 00:38:39,530 --> 00:38:40,632 akan membawa saya? 1036 00:38:40,632 --> 00:38:41,840 >> SPEAKER 5: [Tak terdengar] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. Malan: Ini sayangnya masih n kuadrat, kan? 1038 00:38:44,350 --> 00:38:49,590 Karena jika aku memilih terkecil elemen, dan kami memiliki tujuh orang di sini, 1039 00:38:49,590 --> 00:38:53,280 Aku hanya tahu, setelah saya sampai ke sangat end, bahwa saya telah menemukan terkecil 1040 00:38:53,280 --> 00:38:55,670 nomor, di mana pun ia atau ia mungkin telah. 1041 00:38:55,670 --> 00:38:58,820 Tapi bagaimana saya menemukan berikutnya nomor terkecil? 1042 00:38:58,820 --> 00:39:00,160 Aku harus melakukan lulus lain. 1043 00:39:00,160 --> 00:39:04,810 Jadi dalam kasus terbaik, apa input ke selection sort? 1044 00:39:04,810 --> 00:39:07,830 Ini adalah daftar semacam sudah, nomor satu, nomor dua, nomor tiga, nomor empat. 1045 00:39:07,830 --> 00:39:08,600 Tapi aku komputer. 1046 00:39:08,600 --> 00:39:10,190 Saya hanya dapat melihat satu hal pada suatu waktu. 1047 00:39:10,190 --> 00:39:12,465 Aku tidak bisa semacam mengambil langkah kembali seperti manusia dan berkata, 1048 00:39:12,465 --> 00:39:14,030 ooh, ini terlihat benar. 1049 00:39:14,030 --> 00:39:17,580 >> Aku hanya bisa mengadili ketepatan dalam Pilihan semacam dengan memilih 1050 00:39:17,580 --> 00:39:18,370 nomor terkecil. 1051 00:39:18,370 --> 00:39:21,390 Tetapi bahkan jika saya menemukan nomor satu pertama, jika saya tidak tahu apa-apa lagi tentang 1052 00:39:21,390 --> 00:39:24,460 nomor lain, yang tidak saya lakukan, semua yang saya tahu bahwa saya telah menyerahkan sebuah array 1053 00:39:24,460 --> 00:39:27,930 atau satu set pintu belakang yang angka, satu-satunya cara saya tahu bahwa salah satu 1054 00:39:27,930 --> 00:39:28,680 adalah yang terkecil? 1055 00:39:28,680 --> 00:39:32,440 Jika saya mendapatkan semua jalan di sini dan menyadari, sialan, salah satu memang yang terkecil. 1056 00:39:32,440 --> 00:39:34,870 >> Tapi bagaimana saya kemudian menentukan bahwa keduanya adalah terkecil berikutnya? 1057 00:39:34,870 --> 00:39:38,350 Dengan melakukan inefisiensi yang sama lagi dan lagi. 1058 00:39:38,350 --> 00:39:42,210 Jadi akhirnya, dengan insertion sort, bagaimana, dalam kasus terburuk, 1059 00:39:42,210 --> 00:39:44,990 Apakah kita mengatakan itu melakukan? 1060 00:39:44,990 --> 00:39:49,100 Ini juga adalah n kuadrat. 1061 00:39:49,100 --> 00:39:53,020 Dan bagaimana dengan kasus terbaik? 1062 00:39:53,020 --> 00:39:56,282 Kami akan meninggalkan bahwa sebagai Cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Kita akan mengisi yang kosong waktu berikutnya, tapi pertama-tama saya mengusulkan agar kita 1064 00:40:00,090 --> 00:40:02,620 dasarnya melakukan lebih baik dari semua ini, oke? 1065 00:40:02,620 --> 00:40:05,220 >> Jadi pikirkan sendiri apa penyisipan semacam akan menjadi. 1066 00:40:05,220 --> 00:40:06,910 Nah, yang tidak sangat dramatis, karena aku satu-satunya 1067 00:40:06,910 --> 00:40:08,970 yang melihat perubahan. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Jadi di sini kita memiliki sedikit Demonstrasi yang berbeda. 1071 00:40:12,615 --> 00:40:16,580 Jika saya memperbesar sini, Anda akan melihat bahwa pada kiri kita memiliki bubble sort, dalam 1072 00:40:16,580 --> 00:40:20,740 tengah kita memiliki semacam seleksi, dan paling kanan, kita memiliki sesuatu yang kita 1073 00:40:20,740 --> 00:40:23,380 belum melihat belum disebut menggabungkan semacam. 1074 00:40:23,380 --> 00:40:26,080 Tapi mempertimbangkan apa yang telah kita lakukan di sini sejauh ini. 1075 00:40:26,080 --> 00:40:29,200 Ketika Jennifer pertama kali muncul di atas panggung, kami pergi melalui array angka 1076 00:40:29,200 --> 00:40:33,750 lagi, dan lagi, dengan pencarian linear, dan kami punya waktu berjalan linear, O besar 1077 00:40:33,750 --> 00:40:35,100 n, sehingga untuk berbicara. 1078 00:40:35,100 --> 00:40:41,000 >> Ketika kita sekarang mempertimbangkan minggu pertama kelas, ketika kami telah membagi dan menaklukkan, 1079 00:40:41,000 --> 00:40:43,740 dan kami telah merobek buku telepon, dan Jennifer, dan kita secara kolektif 1080 00:40:43,740 --> 00:40:47,500 leveraged bahwa wawasan kunci, yang adalah ulangi sendiri lagi dan lagi oleh 1081 00:40:47,500 --> 00:40:50,930 entah bagaimana membuang, membuang, membuang, setengah dari masalah, atau 1082 00:40:50,930 --> 00:40:55,320 umumnya, membagi masalah dalam setengah, dan kemudian mengobati bagian yang lebih kecil dari 1083 00:40:55,320 --> 00:40:59,630 masalah sebagai konseptual setara yang lain, kami entah bagaimana melakukan 1084 00:40:59,630 --> 00:41:00,910 fundamental yang lebih baik. 1085 00:41:00,910 --> 00:41:04,720 Tetapi dengan bubble sort, dengan seleksi semacam, dengan insertion sort, kita sudah dapat 1086 00:41:04,720 --> 00:41:06,560 ada wawasan sehingga Jennifer lakukan. 1087 00:41:06,560 --> 00:41:10,220 Kami cukup banyak hanya berjalan kembali dan sebagainya sejumlah besar kali, dan kami 1088 00:41:10,220 --> 00:41:12,650 hal tweak sedikit, swapping dalam urutan ini, mungkin 1089 00:41:12,650 --> 00:41:13,730 memasukkan atau memilih. 1090 00:41:13,730 --> 00:41:16,950 Tetapi pada akhir hari, saya melakukan banyak canggung berjalan kembali dan sebagainya. 1091 00:41:16,950 --> 00:41:21,160 Kami tidak benar-benar memanfaatkan sesuatu pintar seperti Jennifer lakukan seperti membagi 1092 00:41:21,160 --> 00:41:22,040 dan menaklukkan. 1093 00:41:22,040 --> 00:41:25,620 >> Jadi menggabungkan semacam, sebaliknya, yang kita tidak akan melihat sampai minggu depan, itu akan 1094 00:41:25,620 --> 00:41:29,540 untuk memanfaatkan ide kunci dengan membagi input, dan kemudian mengurangi separuh, dan kemudian 1095 00:41:29,540 --> 00:41:30,580 mengurangi separuh, dan kemudian membagi dua. 1096 00:41:30,580 --> 00:41:34,590 Dan pada setiap iterasi dari loop itu, menyortir kiri setengah, dan hak 1097 00:41:34,590 --> 00:41:38,200 setengah, maka kiri setengah dari setengah kiri, dan bagian kanan kiri, kemudian 1098 00:41:38,200 --> 00:41:40,990 kiri setengah dari bagian kanan, dan bagian kanan bagian kanan. 1099 00:41:40,990 --> 00:41:42,840 Dan mengulangi lagi dan lagi. 1100 00:41:42,840 --> 00:41:46,170 >> Jadi, Anda akan melihat ini secara visual, tapi ini adalah apa yang menanti kita minggu depan. 1101 00:41:46,170 --> 00:41:49,760 Dan secara umum, ketika kita berpikir sedikit sedikit lebih keras pada masalah tersebut. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Kami memiliki n kuadrat di sebelah kiri, n kuadrat di tengah, dan n 1104 00:41:57,970 --> 00:41:59,400 log n di sebelah kanan. 1105 00:41:59,400 --> 00:42:00,590 Jadi ada cliffhanger sesungguhnya. 1106 00:42:00,590 --> 00:42:02,040 Kita akan melihat Anda pada hari Senin. 1107 00:42:02,040 --> 00:42:05,163 >> [Tepuk Tangan]