1 00:00:00,000 --> 00:00:11,100 >> [Bermain muzik] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. MALAN: Baiklah. 3 00:00:11,490 --> 00:00:12,170 Jadi mengalu-alukan kembali. 4 00:00:12,170 --> 00:00:15,180 Ini adalah CS50, dan adalah hujung minggu tiga. 5 00:00:15,180 --> 00:00:17,770 >> Jadi ingat dalam beberapa minggu yang lalu, kita telah membelanjakan agak sedikit 6 00:00:17,770 --> 00:00:20,820 masa di C, pengaturcaraan, pada sintaksis. 7 00:00:20,820 --> 00:00:24,680 Dan ia adalah perkara biasa, jika anda masih bergelut dengan Set Masalah 2, menjadi 8 00:00:24,680 --> 00:00:25,950 terhantuk kepala anda ke dinding. 9 00:00:25,950 --> 00:00:28,310 Ia adalah mesej ralat samar-cari dan pepijat yang anda 10 00:00:28,310 --> 00:00:29,220 tidak boleh agak mengejar ke bawah. 11 00:00:29,220 --> 00:00:32,310 Kerana, yakinlah, bahawa hanya dalam masa beberapa minggu anda akan melihat kembali pada 12 00:00:32,310 --> 00:00:35,930 perkara-perkara seperti Caesar, dan [? V-genair,?] mungkin juga Retak, dan 13 00:00:35,930 --> 00:00:40,050 menyedari betapa jauh anda telah datang dalam tempoh masa yang singkat. 14 00:00:40,050 --> 00:00:43,670 Jadi jika itu apa-apa saguhati, hang di sana buat masa ini. 15 00:00:43,670 --> 00:00:46,610 >> Hari ini, walaupun, kita mula peralihan ke tahap yang lebih tinggi perkara. 16 00:00:46,610 --> 00:00:49,820 Dan kita mula mengambil mudah bahawa anda semua tahu bagaimana untuk program, atau sekurang- 17 00:00:49,820 --> 00:00:52,090 kurangnya permulaan bahawa tahap keselesaan. 18 00:00:52,090 --> 00:00:56,520 Dan kita akan mula memikirkan bagaimana kita boleh pergi tentang bentuk program yang lebih 19 00:00:56,520 --> 00:00:57,440 berkesan. 20 00:00:57,440 --> 00:01:01,090 Bagaimana kita boleh pergi tentang mengoptimumkan kecekapan algoritma kami, dan 21 00:01:01,090 --> 00:01:03,110 umumnya menyelesaikan lebih masalah yang menarik. 22 00:01:03,110 --> 00:01:06,850 Dan mula mengambil mudah bahawa, jika kita mahu, kita boleh mana-mana kod 23 00:01:06,850 --> 00:01:08,350 satu contoh yang kita ada dalam fikiran. 24 00:01:08,350 --> 00:01:11,430 Jadi hari ini, kita tidak menyentuh papan kekunci apa-apa bentuk kod. 25 00:01:11,430 --> 00:01:15,150 Ia akan menjadi tahap yang lebih tinggi, dan akhirnya, kira-kira penyelesaian masalah. 26 00:01:15,150 --> 00:01:20,490 >> Jadi, untuk sampai ke tahap ini, biarlah saya mencadangkan bahawa tujuh berikut 27 00:01:20,490 --> 00:01:24,290 segi empat tepat mewakili tujuh pintu, di belakang yang sejumlah besar 28 00:01:24,290 --> 00:01:26,340 nombor, antaranya adalah nombor 50. 29 00:01:26,340 --> 00:01:30,470 Biar saya projek ini pada ini skrin di sini juga. 30 00:01:30,470 --> 00:01:36,770 Dan mencadangkan bahawa kita perlu sukarela untuk membantu mencari saya beberapa di hadapan 31 00:01:36,770 --> 00:01:38,140 internet di sini untuk melihat. 32 00:01:38,140 --> 00:01:40,755 Datang pada sehingga, dalam merah jambu. 33 00:01:40,755 --> 00:01:43,050 Baiklah. 34 00:01:43,050 --> 00:01:43,930 Apa nama anda? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [didengar] 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 Nice untuk bertemu dengan kamu. 41 00:01:47,630 --> 00:01:48,370 Ayuh up. 42 00:01:48,370 --> 00:01:52,430 Jadi ini di sini adalah tujuh pintu, dan apa Saya ingin anda lakukan untuk kita di sini, 43 00:01:52,430 --> 00:01:56,560 di hadapan semua rakan sekelas anda, adalah mencari kita bilangan, 50. 44 00:01:56,560 --> 00:02:00,860 Untuk mengetahui nombor, anda boleh main belakang mana-mana pintu dengan hanya menoreh 45 00:02:00,860 --> 00:02:03,030 di salah satu pintu, dan ia akan mendedahkan nombor. 46 00:02:03,030 --> 00:02:06,080 Dan mari kita lihat berapa cepat anda boleh mencari kami nombor, 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 Baiklah. 55 00:02:18,040 --> 00:02:19,906 Pusingan tepukan untuk Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Tepuk tangan] 57 00:02:21,530 --> 00:02:22,320 >> Baiklah. 58 00:02:22,320 --> 00:02:25,254 Jadi apa yang strategi anda untuk mencari nombor, 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Um, saya fikir mungkin jika - 60 00:02:27,222 --> 00:02:27,714 [Didengar] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. MALAN: Oh. 62 00:02:28,206 --> 00:02:29,630 Memberikan satu saat. 63 00:02:29,630 --> 00:02:32,420 Jadi adalah strategi anda untuk mencari nombor, 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Jadi saya hanya bermula pada mula melihat apa yang nombor pertama 65 00:02:34,760 --> 00:02:38,590 adalah, dan kemudian saya fikir, mungkin jika mereka disusun, saya hanya akan terus 66 00:02:38,590 --> 00:02:39,970 mengetuk 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 seolah-olah telah menemui bahawa untuk menjadi kes itu. 69 00:02:42,910 --> 00:02:45,670 Walaupun, mari kita mengupas kembali lapisan hanya sedikit, dan anda mahu pergi 70 00:02:45,670 --> 00:02:47,640 hadapan dan mendedahkan pintu lain anda boleh 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 mendapat bertuah. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. MALAN: Jadi anda mendapat bertuah. 76 00:02:55,270 --> 00:02:55,710 Baiklah. 77 00:02:55,710 --> 00:02:56,795 Jadi tidak buruk. 78 00:02:56,795 --> 00:02:58,750 Tetapi itulah yang menarik wawasan, bukan? 79 00:02:58,750 --> 00:03:01,870 Jika anda diambil, dan anda tidak dapat, sememangnya, agak bernasib baik di sana. 80 00:03:01,870 --> 00:03:05,350 Tetapi jika anda menganggap bahawa nombor yang disusun, anda boleh menjadi lebih tepat 81 00:03:05,350 --> 00:03:08,750 tentang bagaimana yang mempengaruhi tingkah laku anda? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Jadi, jika mereka telah diselesaikan, saya fikir 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 kepada 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 kepada terkecil, atau kecik hingga besar. 87 00:03:18,170 --> 00:03:21,990 Tetapi biarlah saya mencadangkan, andaikan anda mempunyai mendapat malang, dan menganggap bahawa mereka 88 00:03:21,990 --> 00:03:26,840 tidak, sebenarnya, disusun, berapa ramai pintu-pintu yang anda mungkin terpaksa mengintip 89 00:03:26,840 --> 00:03:28,590 belakang dalam kes paling teruk? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Semua daripada mereka. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. MALAN: Semua daripada mereka. 92 00:03:30,420 --> 00:03:31,740 Jadi mari kita umum bahawa n. 93 00:03:31,740 --> 00:03:34,790 Terdapat berlaku kepada 7, tetapi mari lagi umumnya mengatakan ada n pintu pada 94 00:03:34,790 --> 00:03:35,650 skrin di sini. 95 00:03:35,650 --> 00:03:40,110 Jadi dalam kes paling teruk, anda perlu ke belakang 7 pintu, atau n pintu. 96 00:03:40,110 --> 00:03:44,140 Dan hal ini benar-benar, ia adalah sedikit nasib hari ini, tetapi ia adalah benar-benar satu linear 97 00:03:44,140 --> 00:03:46,440 algoritma pelbagai, walaupun anda adalah jenis ponteng sekitar. 98 00:03:46,440 --> 00:03:47,080 Adakah adil? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Ya. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. MALAN: Baiklah, biarlah saya melihat jika anda perubahan strategi jika saya menggerakkan kita untuk 101 00:03:50,000 --> 00:03:52,190 Contoh kedua kami di sini dengan 7 pintu yang berbeza. 102 00:03:52,190 --> 00:03:55,240 Nombor yang sama, tetapi ini kali mereka disusun. 103 00:03:55,240 --> 00:03:58,350 Apakah strategi anda di sini akan menjadi, cuba untuk meletakkan keluar dari fikiran anda apa 104 00:03:58,350 --> 00:03:59,310 nombor-nombor lain adalah - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. MALAN: - lebih awal? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Mari kita mulakan 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 Mulakan 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 adalah benar-benar kecil. 113 00:04:10,040 --> 00:04:12,500 Jadi, jika mereka mungkin jenis yang paling kecil hingga terbesar, ia perlu 114 00:04:12,500 --> 00:04:13,290 menjadi dua kali ganda, 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 anda fikir? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Cuba 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 Baiklah. 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 sebenarnya melakukan ini teruk, kerana anda 124 00:04:26,790 --> 00:04:27,700 melakukannya dengan baik. 125 00:04:27,700 --> 00:04:31,150 Yang meninggalkan kita tidak dapat membuat mata tertentu. 126 00:04:31,150 --> 00:04:32,565 Jadi mari kita cuba untuk melancarkan 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, tetap. 129 00:04:35,980 --> 00:04:39,060 Jadi anda bermula pada awal, anda melihat bahawa ia adalah 4, maka anda 130 00:04:39,060 --> 00:04:40,240 berpindah ke akhir. 131 00:04:40,240 --> 00:04:42,320 Tetapi andaikan anda tidak bernasib baik sana, dan andaikan 50 132 00:04:42,320 --> 00:04:42,890 adalah di tempat lain. 133 00:04:42,890 --> 00:04:46,190 Apakah langkah yang ketiga anda telah? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Pergi balik ke permulaan. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. MALAN: Kembali untuk permulaan. 136 00:04:48,320 --> 00:04:51,320 OK, jadi anda akan telah menyentuh pintu ini, yang 8. 137 00:04:51,320 --> 00:04:51,660 Baiklah. 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 kelihatan akan datang? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Jika saya tidak tahu mereka disusun. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. MALAN: Betul. 142 00:04:57,005 --> 00:04:58,490 Nah, jika anda tidak tahu mereka telah disusun - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Oh, tidak tahu, ya. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. MALAN: - tetapi anda tidak tahu di mana 50 adalah lagi? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Hanya menyimpan berterusan. 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 Teruskan usaha. 149 00:05:03,800 --> 00:05:05,270 OK, saya boleh 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 pergi, apa yang anda 152 00:05:07,210 --> 00:05:09,680 algoritma devolving disokong ke dalam. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: The linear -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. MALAN: Ia adalah jenis linear. 155 00:05:11,820 --> 00:05:13,480 Tetapi biarlah saya mencadangkan, biarlah saya meletakkan di tempat kejadian. 156 00:05:13,480 --> 00:05:14,900 Biar saya menyegarkan halaman. 157 00:05:14,900 --> 00:05:17,120 Bilangan yang sama, perkiraan sama, pintu yang sama. 158 00:05:17,120 --> 00:05:21,350 Tetapi berfikir kembali kepada hari pertama dalam kelas apabila kita mengoyakkan buku telefon di 159 00:05:21,350 --> 00:05:25,480 separuh, jenis, dan apa yang strategi kami di sana? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Mula di tengah-tengah. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. MALAN: OK. 162 00:05:26,690 --> 00:05:27,610 Jadi bermula di tengah-tengah. 163 00:05:27,610 --> 00:05:28,790 Jadi mari kita pergi ke hadapan dan meniru itu. 164 00:05:28,790 --> 00:05:30,720 Mula di tengah-tengah oleh mendedahkan pintu itu. 165 00:05:30,720 --> 00:05:31,660 Jadi nombor 16. 166 00:05:31,660 --> 00:05:35,290 Jadi apa yang akan lelaki yang kuat telah dilakukan, yang mengoyakkan buku telefon pada separuh, 167 00:05:35,290 --> 00:05:38,450 untuk mendapatkan rasa yang akan datang? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Pergi pada separuh ini. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. MALAN: Dan mengapa di sebelah kanan? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Jika mereka jenis yang paling kecil hingga terbesar, maka 50 hendaklah 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 munasabah. 174 00:05:45,390 --> 00:05:48,380 Jadi seperti buku telefon, anda pergi ke betul bertentangan dengan kiri, tetapi di sini 175 00:05:48,380 --> 00:05:49,500 adalah Fleet utama. 176 00:05:49,500 --> 00:05:53,930 Anda kini boleh buang, atau mengoyakkan, separuh daripada masalah ini, meninggalkan anda tidak 177 00:05:53,930 --> 00:05:55,970 dengan 7 pintu, tetapi benar-benar dengan hanya 3. 178 00:05:55,970 --> 00:05:57,870 Yang merupakan kira-kira separuh daripada saiz masalah. 179 00:05:57,870 --> 00:05:58,350 Baiklah. 180 00:05:58,350 --> 00:06:01,890 Jadi sekarang apa yang anda akan mempunyai dilakukan selepas anda betul? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Jadi 16 masih agak kecil, berbanding dengan 50, jadi mungkin saya akan cuba, 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 boleh buang 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 boleh buang separuh kiri 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, walaupun ia sukar untuk melihat mungkin, apabila ada sahaja 193 00:06:17,820 --> 00:06:21,320 7 pintu, memikirkan, sekarang, yang konsisten 194 00:06:21,320 --> 00:06:22,620 Algoritma anda hanya digunakan. 195 00:06:22,620 --> 00:06:24,510 Dalam kes sebelum ini, anda pula bernasib baik, yang hebat. 196 00:06:24,510 --> 00:06:26,540 Tetapi anda tidak menggunakan heuristik a, Saya akan berkata. 197 00:06:26,540 --> 00:06:29,150 Anda menggunakan jenis naluri anda, dan mengetahui ia disusun, jika ia cukup 198 00:06:29,150 --> 00:06:31,600 kecil pada permulaan, jelas, kami telah mendapat untuk pergi lebih ke kanan. 199 00:06:31,600 --> 00:06:34,990 Tetapi dalam erti kata lain, anda mendapat bernasib baik, kerana mungkin ini adalah nombor 100, 200 00:06:34,990 --> 00:06:36,220 50 dan mungkin lebih di tengah-tengah. 201 00:06:36,220 --> 00:06:37,910 Mungkin 50 pun di sini. 202 00:06:37,910 --> 00:06:40,960 >> Tetapi apa yang anda lakukan sedikit berbeza kali ini, anda melakukan perkara 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 akan berhujah bahawa apa yang anda hanya tidak, walaupun dipengaruhi oleh telefon 205 00:06:45,310 --> 00:06:48,100 contoh buku, adalah sesuatu yang lebih lebih algoritma, dan banyak 206 00:06:48,100 --> 00:06:49,930 kurang khas bingkai. 207 00:06:49,930 --> 00:06:51,620 Apalagi naluri. 208 00:06:51,620 --> 00:06:57,160 Jadi pada akhir hari, bagaimana akan anda menggambarkan kecekapan 209 00:06:57,160 --> 00:07:00,530 algoritma pertama, di mana anda pergi kiri ke kanan, berbanding 210 00:07:00,530 --> 00:07:03,430 algoritma kedua di sini? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: Yang ini harus, seperti, mungkin mengurangkan separuh masa, atau lebih, ya. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. MALAN: OK, mungkin lebih. 213 00:07:07,320 --> 00:07:10,150 Mari kita menolak sedikit sukar pada itu. 214 00:07:10,150 --> 00:07:13,030 Apa yang benar-benar, jika kita terus ini logik, kita pasti yang separuh 215 00:07:13,030 --> 00:07:15,830 berjalan masa dengan algoritma kedua ini dengan membuang separuh daripada 216 00:07:15,830 --> 00:07:18,470 nombor, tetapi apa yang kita lakukan pada seterusnya lelaran, apabila Jennifer mendedahkan 217 00:07:18,470 --> 00:07:20,615 nombor kedua? 218 00:07:20,615 --> 00:07:22,830 >> Kami separuh bilangan pintu lagi. 219 00:07:22,830 --> 00:07:25,270 Dan kemudian apa yang kita lakukan selepas itu, jika terdapat lebih banyak pintu untuk bermain dengan? 220 00:07:25,270 --> 00:07:27,520 Kami akan mengurangkan separuh mereka, dan sekali lagi, dan sekali lagi, dan lagi. 221 00:07:27,520 --> 00:07:30,420 Dan ini adalah sama seperti kalian semua berdiri pada minggu pertama 222 00:07:30,420 --> 00:07:33,000 kelas, separuh daripada anda duduk, separuh anda duduk, separuh daripada anda 223 00:07:33,000 --> 00:07:35,440 duduk, sehingga satu-satunya jiwa berdiri. 224 00:07:35,440 --> 00:07:39,050 Dan kita berkata bahawa masa berjalan itu, beberapa langkah yang diambil adalah 225 00:07:39,050 --> 00:07:40,430 atas perintah apa? 226 00:07:40,430 --> 00:07:41,230 >> SPEAKER 1: [didengar] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. MALAN: Jadi log base 2 n, atau hanya lebih mudah, log n. 228 00:07:43,970 --> 00:07:45,060 Jadi sesuatu logaritma. 229 00:07:45,060 --> 00:07:48,380 Dan graf yang bukan satu garis lurus yang hanya mendapat lebih teruk dan lebih teruk, ia adalah 230 00:07:48,380 --> 00:07:52,490 keluk yang menarik ini yang tidak begitu buruk dari masa ke masa. 231 00:07:52,490 --> 00:07:53,910 Jadi mari kita berpegang kepada idea ini. 232 00:07:53,910 --> 00:07:54,690 Mari kita mengucapkan terima kasih kepada Jennifer. 233 00:07:54,690 --> 00:07:56,150 Terima kasih banyak untuk datang di atas. 234 00:07:56,150 --> 00:07:57,400 Dan, salah satu saat. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Tiada lampu meja hari ini, tetapi kita tidak mempunyai CS50 bola tekanan. 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 kerana menanggung tekanan di sini. 240 00:08:06,545 --> 00:08:07,350 Baiklah. 241 00:08:07,350 --> 00:08:10,620 Jadi mari kita lihat jika kita tidak boleh sekarang merasmikan ini sedikit lebih. 242 00:08:10,620 --> 00:08:14,820 Jadi sekali lagi, apa yang kita lakukan ialah dasarnya perkara yang sama seperti yang kita lakukan 243 00:08:14,820 --> 00:08:16,660 dalam minggu yang pertama. 244 00:08:16,660 --> 00:08:23,780 Tetapi bukannya berakhir dengan hanya linear algoritma, yang kita digambarkan 245 00:08:23,780 --> 00:08:27,210 sebelum ini sebagai garis lurus, di mana, jika kita meletakkan satu pintu lanjut mengenai 246 00:08:27,210 --> 00:08:29,610 skrin, kemudian Jennifer akan terpaksa melihat, berpotensi, 247 00:08:29,610 --> 00:08:30,600 di sebalik satu pintu lagi. 248 00:08:30,600 --> 00:08:33,490 Jika kita meletakkan dua pintu, dia mungkin mempunyai ke belakang dua lagi pintu. 249 00:08:33,490 --> 00:08:35,990 >> Dan sebagainya, ada ini linear Hubungan antara saiz 250 00:08:35,990 --> 00:08:39,059 masalah di, berkata, paksi-x, dan jumlah masa yang diperlukan untuk 251 00:08:39,059 --> 00:08:40,440 menyelesaikan pada paksi. 252 00:08:40,440 --> 00:08:43,330 Tetapi gambaran yang saya merujuk kepada awal adalah garis hijau. 253 00:08:43,330 --> 00:08:45,970 Green sengaja, kerana ia hanya berasa lebih baik. 254 00:08:45,970 --> 00:08:49,790 Dalam teori, algoritma, apabila kita melakukannya dengan buku telefon, apabila kita melakukannya 255 00:08:49,790 --> 00:08:52,420 dengan anda semua mengira sama lain, dan dalam kes kedua, apabila Jennifer hanya 256 00:08:52,420 --> 00:08:55,250 adakah ia di sini, ia adalah jenis daripada asasnya yang lebih baik. 257 00:08:55,250 --> 00:08:57,180 Kerana ia bukan sahaja dua kali lebih cepat. 258 00:08:57,180 --> 00:08:58,870 Ia tidak pun empat kali dengan cepat. 259 00:08:58,870 --> 00:09:03,290 Ia adalah bergantung sepenuhnya kepada apa yang saiz input itu, untuk berapa banyak 260 00:09:03,290 --> 00:09:05,220 langkah-langkah yang ia akhirnya mengambil. 261 00:09:05,220 --> 00:09:08,040 >> Dan sebagainya idea ini mudah yang kita semua mengambil untuk diberikan dengan buku telefon, 262 00:09:08,040 --> 00:09:10,200 boleh juga digunakan kepada sesuatu yang seperti ini. 263 00:09:10,200 --> 00:09:12,380 Dan ini mungkin lebih bersahaja dikenali sebagai, kerana anda mungkin 264 00:09:12,380 --> 00:09:13,940 bayangkan, membahagi dan menakluk. 265 00:09:13,940 --> 00:09:16,390 Tidak seperti apa yang kami lakukan, sudah tentu, dengan buku telefon. 266 00:09:16,390 --> 00:09:18,300 >> Tetapi pseudokod itu, ingat, adalah ini. 267 00:09:18,300 --> 00:09:21,800 Jadi kita tidak akan melakukan ini sekali lagi, tetapi ingat bahawa minggu pertama, kita semua berdiri 268 00:09:21,800 --> 00:09:25,140 dan kemudian separuh daripada anda duduk, separuh daripada anda duduk, separuh daripada anda duduk. 269 00:09:25,140 --> 00:09:29,280 Bahawa algoritma telah dilaksanakan dalam sedikit cara menipu, dalam itu, ia 270 00:09:29,280 --> 00:09:32,870 tidak hanya salah satu daripada saya mengira, asasnya, lebih cekap. 271 00:09:32,870 --> 00:09:35,830 Dalam kes itu, saya telah menggunakan sumber sekunder. 272 00:09:35,830 --> 00:09:39,470 Jenis, pelbagai CPU, pelbagai otak, beberapa orang pintar dalam 273 00:09:39,470 --> 00:09:42,740 bilik telah membantu saya dapat daripada sesuatu linear kepada sesuatu 274 00:09:42,740 --> 00:09:45,190 logaritma, dari sesuatu merah kepada sesuatu yang hijau. 275 00:09:45,190 --> 00:09:48,650 >> Tetapi dalam kes ini, Jennifer sahaja boleh asasnya menambah baik 276 00:09:48,650 --> 00:09:52,370 prestasi algoritma pertama oleh, sekali lagi, hanya memikirkan sedikit lebih keras. 277 00:09:52,370 --> 00:09:56,650 Dan sekarang, apabila ia datang masa untuk melaksanakan perkara-perkara ini, memikirkan 278 00:09:56,650 --> 00:10:00,670 apa baris kod anda boleh menulis apa-apa bahawa anda boleh mengulangi sekali lagi, dan 279 00:10:00,670 --> 00:10:03,350 sekali lagi, dan sekali lagi, jenis dengan cara yang menggelung. 280 00:10:03,350 --> 00:10:06,370 Kerana anda tidak akan mempunyai mewah, seperti Jennifer lakukan pada pertama, 281 00:10:06,370 --> 00:10:10,460 hanya mempunyai sejumlah besar IFS dan berkata, hmm, jika nombor pertama ini adalah 4, 282 00:10:10,460 --> 00:10:11,800 biarlah saya melompat sepanjang jalan ke akhir. 283 00:10:11,800 --> 00:10:14,180 Aduh, jika nombor yang terlalu besar, biarlah saya bergerak kembali sewenang-wenangnya 284 00:10:14,180 --> 00:10:15,220 kepada elemen kedua. 285 00:10:15,220 --> 00:10:18,210 Anda akan mendapati bahawa ia akan menjadi lebih sukar untuk merasmikan apa yang kita manusia 286 00:10:18,210 --> 00:10:21,270 ambil untuk diberikan sebagai sangat munasabah heuristik, tetapi komputer hanya 287 00:10:21,270 --> 00:10:23,260 akan melakukan apa yang anda beritahu ia lakukan. 288 00:10:23,260 --> 00:10:25,280 >> Sekarang ini telah sangat menarik implikasi. 289 00:10:25,280 --> 00:10:29,950 Graf ini semacam bertujuan untuk menyusun daripada mengatasi visual, tetapi notis, di mana 290 00:10:29,950 --> 00:10:32,230 adalah garis lurus dalam graf ini? 291 00:10:32,230 --> 00:10:35,330 Di manakah graf linear yang kita panggil n? 292 00:10:35,330 --> 00:10:37,580 Nah, itu jenis ke arah bawah gambar ini, bukan? 293 00:10:37,580 --> 00:10:40,500 Jadi semua yang kita lakukan ialah kita telah jenis dizum keluar ke x-paksi dan 294 00:10:40,500 --> 00:10:44,780 paksi-y cuba untuk mendapatkan rasa apa lain-lain jenis keluk kelihatan seperti. 295 00:10:44,780 --> 00:10:47,760 >> Dan khusus matematik ungkapan hari ini tidak akan perkara itu 296 00:10:47,760 --> 00:10:52,440 banyak, tetapi notis bahawa terdapat banyak algoritma yang jauh lebih teruk daripada 297 00:10:52,440 --> 00:10:53,470 sesuatu yang linear. 298 00:10:53,470 --> 00:10:55,410 Sesungguhnya, n cubed kelihatan cukup buruk. 299 00:10:55,410 --> 00:10:58,400 2 hingga n kelihatan cukup buruk. n kuasa dua kelihatan cukup buruk. 300 00:10:58,400 --> 00:11:01,630 Dan kita akan melihat apa yang beberapa orang mungkin dalam realiti hari ini. 301 00:11:01,630 --> 00:11:05,430 Dan log n tidak berasa seperti tidak baik, tetapi lebih baik daripada n log asas 2 n. 302 00:11:05,430 --> 00:11:08,080 Tetapi anda tahu, ia akan menjadi lebih lebih hebat jika Jennifer, atau jika kita, 303 00:11:08,080 --> 00:11:12,910 bahawa minggu pertama, telah tampil dengan sesuatu yang log log n. 304 00:11:12,910 --> 00:11:15,880 >> Jadi, dalam erti kata lain, ada keseluruhan ini pelbagai penyelesaian yang mungkin untuk 305 00:11:15,880 --> 00:11:18,570 masalah, tetapi di sini, notis apa yang akan berlaku. 306 00:11:18,570 --> 00:11:22,910 Apabila saya zum keluar, yang mana satu keluk akan membuktikan untuk menjadi mutlak 307 00:11:22,910 --> 00:11:26,630 paling teruk orang-orang yang pada skrin sekarang? 308 00:11:26,630 --> 00:11:28,680 Jadi n cubed kelihatan cantik buruk pada masa ini. 309 00:11:28,680 --> 00:11:32,470 Tetapi jika kita zum keluar dan melihat lebih banyak x dan paksi-y, yang akan 310 00:11:32,470 --> 00:11:34,550 menguasai akhirnya? 311 00:11:34,550 --> 00:11:37,120 Jadi ia sebenarnya ternyata bahawa 2 kepada n, dan anda boleh memikirkan ini hanya dengan 312 00:11:37,120 --> 00:11:39,990 memasang dalam beberapa semakin besar nombor, dan anda akan melihat bahawa 2 kepada 313 00:11:39,990 --> 00:11:42,070 n, sesungguhnya semakin besar lebih cepat. 314 00:11:42,070 --> 00:11:45,530 Jika kita benar-benar zum keluar, 2 kepada n algoritma benar-benar menghisap. 315 00:11:45,530 --> 00:11:48,170 Maksud saya, ini akan mengambil agak sedikit masa untuk 316 00:11:48,170 --> 00:11:49,460 komputer untuk melahirkan melalui. 317 00:11:49,460 --> 00:11:52,500 >> Tetapi anda akan melihat dari masa ke masa, terutamanya dengan set masalah masa depan dan juga 318 00:11:52,500 --> 00:11:55,600 projek akhir, adalah data anda set mendapat besar, betul? 319 00:11:55,600 --> 00:11:58,300 Malah dalam versi pertama Facebook, kerana bilangan kawan-kawan, dan 320 00:11:58,300 --> 00:12:01,840 bilangan pengguna berdaftar mendapat besar, anda boleh menyusun telefon dalam dan 321 00:12:01,840 --> 00:12:05,530 melaksanakan sesuatu dengan carian linear, atau pengasingan sangat mudah 322 00:12:05,530 --> 00:12:07,030 algoritma, seperti yang kita akan lihat hari ini. 323 00:12:07,030 --> 00:12:09,280 Anda perlu mula berfikir sukar dan lebih keras mengenai masalah ini. 324 00:12:09,280 --> 00:12:12,070 Dan jenis masalah tempat seperti Facebook, dan Google, dan Microsoft, 325 00:12:12,070 --> 00:12:16,350 dan lain-lain kerja-kerja betul-betul ini jenis jenis data yang besar soalan-soalan 326 00:12:16,350 --> 00:12:18,530 semakin hari ini. 327 00:12:18,530 --> 00:12:18,900 >> Baiklah. 328 00:12:18,900 --> 00:12:23,800 Jadi kejayaan Jennifer dalam yang kedua algoritma, terus-terang, dia menakjubkan 329 00:12:23,800 --> 00:12:26,110 baik kali pertama, tetapi mari menulis sebagai nasib supaya kita 330 00:12:26,110 --> 00:12:27,000 boleh membuat hal ini. 331 00:12:27,000 --> 00:12:30,970 Dalam kes kedua, dia memanfaatkan satu algoritma yang berulang lagi dan 332 00:12:30,970 --> 00:12:34,670 sekali lagi, tetapi dia mengambil masa untuk diberikan andaian tertentu yang kita dibenarkan 333 00:12:34,670 --> 00:12:39,370 , tetapi dia dieksploitasi beberapa terperinci kali kedua dia tidak mempunyai 334 00:12:39,370 --> 00:12:39,840 kali pertama. 335 00:12:39,840 --> 00:12:41,800 Iaitu apa? 336 00:12:41,800 --> 00:12:43,050 >> Bahawa senarai itu disusun. 337 00:12:43,050 --> 00:12:46,350 Jadi sebaik sahaja senarai itu disusun, kami mendakwa bahawa Jennifer berupaya untuk melakukan 338 00:12:46,350 --> 00:12:47,480 asasnya yang lebih baik. 339 00:12:47,480 --> 00:12:51,450 7 pintu, ya, tidak begitu menarik, tetapi rasa ia kami 7 juta pintu. 340 00:12:51,450 --> 00:12:54,080 Log n pasti akan untuk melaksanakan banyak, lebih 341 00:12:54,080 --> 00:12:55,610 cepat dalam jangka masa panjang. 342 00:12:55,610 --> 00:12:58,880 Tetapi dia terpaksa mempunyai pintu disusun untuk beliau. 343 00:12:58,880 --> 00:13:02,320 Sekarang, saya mengambil kebebasan berbuat demikian terlebih dahulu pada skrin komputer 344 00:13:02,320 --> 00:13:05,160 di sini, tetapi rasa Jennifer bahawa terpaksa melakukannya sendiri? 345 00:13:05,160 --> 00:13:10,120 Katakan bahawa pintu berkenaan data diwakili dalam pangkalan data, atau 346 00:13:10,120 --> 00:13:14,260 rakan-rakan mendaftar untuk Facebook, atau mana-mana laman web di internet yang 347 00:13:14,260 --> 00:13:16,880 pelbagai laman web mungkin perlu kepada indeks atau cari lebih. 348 00:13:16,880 --> 00:13:20,940 >> Katakan anda hanya mempunyai data mentah ditetapkan dan ianya dibiarkan untuk anda, atau untuk 349 00:13:20,940 --> 00:13:23,010 Jennifer untuk melakukan pengasingan itu? 350 00:13:23,010 --> 00:13:26,950 Itu, sebaliknya, memerlukan kita menjawab soalan, baik, berapa banyak masa 351 00:13:26,950 --> 00:13:31,080 akan mengambil Jennifer, atau saya, untuk menyusun nombor-nombor tersebut terlebih dahulu supaya 352 00:13:31,080 --> 00:13:32,680 bahawa dia boleh mengambil kesempatan daripada itu? 353 00:13:32,680 --> 00:13:32,880 Betul? 354 00:13:32,880 --> 00:13:36,620 Kerana implikasi, sudah tentu, adalah jika ia mengambil masa saya yang agak lama untuk menyelesaikan 355 00:13:36,620 --> 00:13:40,800 nombor, yang palang pintu yang peduli bahawa anda boleh menemui beberapa seperti 50 dengan begitu pantas, 356 00:13:40,800 --> 00:13:44,850 seperti dalam kes Jennifer, jika kita lebih daripada terharu jumlah keseluruhan masa 357 00:13:44,850 --> 00:13:46,920 ia mengambil masa oleh sorting perkara terlebih dahulu? 358 00:13:46,920 --> 00:13:49,320 >> Jadi mari kita lihat jika kita tidak boleh yang gambaran di sini. 359 00:13:49,320 --> 00:13:51,370 Saya mempunyai sejumlah besar tekanan yang lebih bola, jika yang membantu 360 00:13:51,370 --> 00:13:52,270 memecahkan ais di sini. 361 00:13:52,270 --> 00:13:55,690 Dan jika anda tidak keberatan, kita perlu tujuh sukarelawan - 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 Oleh itu, kita tidak perlu untuk menghabiskan pada lampu meja, ia seolah-olah. 365 00:13:59,250 --> 00:13:59,690 Baiklah. 366 00:13:59,690 --> 00:14:01,530 Jadi bagaimana pula kamu berdua di hadapan. 367 00:14:01,530 --> 00:14:04,160 Bagaimana pula dengan anda dua lelaki di belakang. 368 00:14:04,160 --> 00:14:04,870 Itulah empat. 369 00:14:04,870 --> 00:14:09,890 Bagaimana pula dengan anda di hadapan lima, enam dan tujuh. 370 00:14:09,890 --> 00:14:10,320 Di sana. 371 00:14:10,320 --> 00:14:13,260 Rakan anda yang menunjukkan anda keluar, supaya anda mendapat hadiah. 372 00:14:13,260 --> 00:14:13,700 >> Baiklah. 373 00:14:13,700 --> 00:14:14,410 Ayuh up. 374 00:14:14,410 --> 00:14:17,120 Dan mengapa tidak, kita perlu anda lelaki datang di sini. 375 00:14:17,120 --> 00:14:18,960 Saya akan memberikan anda setiap nombor. 376 00:14:18,960 --> 00:14:22,150 Dan pergi ke depan dan mengatur diri sepercaman kepada apa yang 377 00:14:22,150 --> 00:14:25,180 yang digambarkan pada skrin. 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 Baiklah. 382 00:14:32,180 --> 00:14:32,750 Nah, di sini kita pergi. 383 00:14:32,750 --> 00:14:34,180 Nombor lima. 384 00:14:34,180 --> 00:14:35,136 Bilangan 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 adalah janggal. 387 00:14:39,410 --> 00:14:41,210 >> SPEAKER 2: saya hanya akan mendapat -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. MALAN: perjanjian yang baik. 389 00:14:41,900 --> 00:14:43,130 Baiklah. 390 00:14:43,130 --> 00:14:44,611 Terima kasih kerana mengambil bahagian. 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 Baiklah. 394 00:14:48,860 --> 00:14:51,970 Oleh itu, kita mempunyai empat, dua, enam, satu, tiga, tujuh, lima. 395 00:14:51,970 --> 00:14:56,010 Perfect jadi kami mempunyai tujuh sukarelawan di sini yang sama lebar kepada 396 00:14:56,010 --> 00:14:57,430 array yang kita sedang bermain dengan lebih awal. 397 00:14:57,430 --> 00:14:59,470 Dan saya memilih tujuh atas sebab-sebab yang akan hanya 398 00:14:59,470 --> 00:15:00,840 mudah sedikit. 399 00:15:00,840 --> 00:15:04,400 Dan saya akan mencadangkan pertama yang kita menyusun tujuh sukarelawan. 400 00:15:04,400 --> 00:15:06,786 Jika anda ingin, pertama, untuk bertanya khabar walaupun. 401 00:15:06,786 --> 00:15:08,970 Kerana ini akan menjadi satu janggal beberapa minit. 402 00:15:08,970 --> 00:15:10,370 Perkenalkan diri kamu sendiri. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Hi, saya Grace. 404 00:15:10,980 --> 00:15:14,190 Saya seorang mahasiswa tingkat kedua di Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> Branson: Hi. 406 00:15:14,620 --> 00:15:15,620 Saya Branson. 407 00:15:15,620 --> 00:15:16,920 Saya bayat 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 Saya Gabe. 411 00:15:21,040 --> 00:15:22,300 Saya seorang junior di Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Saya Neil. 414 00:15:25,980 --> 00:15:29,090 Saya bayat di Matthews. 415 00:15:29,090 --> 00:15:29,550 >> Jason: Saya Jason. 416 00:15:29,550 --> 00:15:32,816 Saya bayat di Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Saya Mike. 418 00:15:33,700 --> 00:15:37,360 Saya bayat di Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Saya Jess. 420 00:15:37,990 --> 00:15:40,313 Saya seorang mahasiswa tingkat kedua di Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. MALAN: Excellent. 422 00:15:41,300 --> 00:15:41,850 Baiklah. 423 00:15:41,850 --> 00:15:44,190 Well, terima kasih kepada semua kami sukarelawan di sini setakat ini. 424 00:15:44,190 --> 00:15:47,110 Dan cabaran yang ada sekarang akan sebagai untuk menyusun daripada lelaki ini, tetapi kemudian 425 00:15:47,110 --> 00:15:50,250 kita akan perlu berfikir sedikit keras tentang bagaimana cekap kita sebenarnya 426 00:15:50,250 --> 00:15:51,110 disusun mereka. 427 00:15:51,110 --> 00:15:52,580 Jadi mari kita mula-mula cuba ini. 428 00:15:52,580 --> 00:15:55,970 Kamu boleh melihat nombor masing-masing hanya dengan meletakkan sekitar sudut. 429 00:15:55,970 --> 00:15:59,380 Teruskan dan mengambil beberapa saat, dan jenis dirimu dari kecik pada 430 00:15:59,380 --> 00:16:01,240 dibiarkan 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 adalah benar-benar cepat darn. 436 00:16:09,370 --> 00:16:14,040 Sekarang seseorang di sini, apa yang algoritma bahawa lelaki digunakan? 437 00:16:14,040 --> 00:16:14,900 >> SPEAKER 1 kurangnya untuk terbesar. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. MALAN: OK. 439 00:16:15,000 --> 00:16:18,070 Kurangnya terbesar adalah benar-benar menyelesaikan satu objektif, tetapi saya tidak pasti itu 440 00:16:18,070 --> 00:16:18,890 benar-benar satu algoritma. 441 00:16:18,890 --> 00:16:21,810 Kurangnya terbesar tidak memberitahu saya langkah demi langkah apa yang perlu dilakukan. 442 00:16:21,810 --> 00:16:22,833 Ya? 443 00:16:22,833 --> 00:16:24,083 >> SPEAKER 1: [didengar] 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 yang lebih kecil daripada nombor anda, kemudian bergerak ke 447 00:16:28,920 --> 00:16:29,680 hak mereka. 448 00:16:29,680 --> 00:16:32,800 Jadi yang kini semakin ekspresif, lebih seperti algoritma, kerana anda 449 00:16:32,800 --> 00:16:35,410 boleh berkata, jika ini, maka itu. 450 00:16:35,410 --> 00:16:37,050 Oleh itu, kita mempunyai beberapa jenis membina bersyarat. 451 00:16:37,050 --> 00:16:39,700 Dan lelaki ini seolah-olah untuk berbuat demikian beberapa kali, kerana sesetengah daripada anda berpindah sedikit 452 00:16:39,700 --> 00:16:40,420 dari jauh. 453 00:16:40,420 --> 00:16:43,410 Jadi ada mungkin beberapa jenis gelung yang berlaku di dalam fikiran mereka. 454 00:16:43,410 --> 00:16:44,610 >> Tetapi mari kita cuba untuk merasmikan itu. 455 00:16:44,610 --> 00:16:47,540 Jika anda semua boleh menetapkan semula kembali kepada perkiraan ini. 456 00:16:47,540 --> 00:16:50,650 Mari kita lihat jika kita tidak boleh merasmikan ini bit, dan kemudian bertanya soalan, hanya 457 00:16:50,650 --> 00:16:51,580 bagaimana cekap ini? 458 00:16:51,580 --> 00:16:54,220 Sudah tentu, apabila kita melakukan ini lebih perlahan, ia akan berasa seolah-baik 459 00:16:54,220 --> 00:16:57,210 algoritma, tetapi mari kita lihat jika kita boleh meletakkan jari kami pada langkah-langkah yang tepat. 460 00:16:57,210 --> 00:16:58,670 >> Jadi, anda dua lelaki empat dan dua. 461 00:16:58,670 --> 00:17:01,020 Atau anda susunan yang betul atau tidak betul? 462 00:17:01,020 --> 00:17:01,900 Jelas sekali tidak betul. 463 00:17:01,900 --> 00:17:02,710 Jadi kita bertukar. 464 00:17:02,710 --> 00:17:05,170 Sekarang saya akan bergerak ke tepi di sini dan berkata, empat hingga enam. 465 00:17:05,170 --> 00:17:06,240 Adakah anda betul atau salah? 466 00:17:06,240 --> 00:17:06,599 >> Gabe: Betul. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. MALAN: Betul. 468 00:17:07,180 --> 00:17:08,300 Enam dan satu? 469 00:17:08,300 --> 00:17:08,609 Nope. 470 00:17:08,609 --> 00:17:09,630 Swap. 471 00:17:09,630 --> 00:17:10,490 Itulah dua swap. 472 00:17:10,490 --> 00:17:11,710 Enam dan tiga? 473 00:17:11,710 --> 00:17:11,980 Nope. 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 Kelihatan baik. 477 00:17:14,630 --> 00:17:15,396 Tujuh dan lima? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [didengar] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. MALAN: OK, menukar. 480 00:17:17,089 --> 00:17:19,770 Dan disusun. 481 00:17:19,770 --> 00:17:19,980 Baiklah. 482 00:17:19,980 --> 00:17:21,440 Jadi jelas tidak, kan? 483 00:17:21,440 --> 00:17:22,470 Jadi ada adalah lebih berlaku. 484 00:17:22,470 --> 00:17:24,920 Tetapi, sesungguhnya, orang-orang ini, walaupun hanya naluri. 485 00:17:24,920 --> 00:17:25,450 disimpan bergerak. 486 00:17:25,450 --> 00:17:27,710 Mereka tidak hanya berhenti, apabila mereka diperbetulkan satu masalah. 487 00:17:27,710 --> 00:17:27,839 Jadi. 488 00:17:27,839 --> 00:17:29,390 Malah, saya akan mempunyai untuk melakukan perkara yang sama. 489 00:17:29,390 --> 00:17:32,720 Saya akan perlu menyelesaikan satu memundurkan kembali untuk permulaan masalah ini, 490 00:17:32,720 --> 00:17:35,630 atau awal pelbagai ini orang, mari kita mula memanggil mereka. 491 00:17:35,630 --> 00:17:38,366 >> Dan kini apa yang perlu saya algoritma pada lulus kedua menjadi? 492 00:17:38,366 --> 00:17:39,220 >> SPEAKER 1: Perkara yang sama. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. MALAN: Perkara yang sama. 494 00:17:39,940 --> 00:17:41,460 Dan ini, saya mula suka, kan? 495 00:17:41,460 --> 00:17:44,720 Sebaik sahaja anda boleh mendapati diri anda melakukan perkara yang sama sekali lagi dan sekali lagi, itu 496 00:17:44,720 --> 00:17:47,890 menjadi lebih seperti 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 No 500 00:17:50,220 --> 00:17:51,050 Empat dan satu? 501 00:17:51,050 --> 00:17:53,380 Ah, ada sememangnya merupakan beberapa kerja masih perlu 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. 509 00:18:01,550 --> 00:18:02,710 Saya perlu pergi ke belakang. 510 00:18:02,710 --> 00:18:05,130 >> Jadi sekarang, sekali lagi, kita lakukan ini sedikit lebih sengaja. 511 00:18:05,130 --> 00:18:08,700 Dan kini, terdapat hanya satu otak melaksanakan algoritma ini. 512 00:18:08,700 --> 00:18:10,290 Satu CPU, jika anda akan. 513 00:18:10,290 --> 00:18:13,090 Dan terus-terang, itulah satu-satunya sumber kita akan mempunyai akses kepada. 514 00:18:13,090 --> 00:18:16,280 Dan apabila kita kembali ke papan kekunci dan mempunyai sesuatu seperti C pada kami 515 00:18:16,280 --> 00:18:19,600 pelupusan, kita hanya menulis program yang boleh melakukan satu perkara pada satu masa. 516 00:18:19,600 --> 00:18:22,900 Manakala, lelaki ini masa yang lalu, kita dimanfaatkan otak kolektif mereka 517 00:18:22,900 --> 00:18:24,180 seperti kamu lakukan pada sifar minggu. 518 00:18:24,180 --> 00:18:24,980 Jadi mari kita terus melakukan 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, tetapi biarlah saya bermain peguam bela syaitan. 527 00:18:34,560 --> 00:18:37,950 Adakah saya, jenis komputer yang hanya dibuat pas melalui pelbagai ini 528 00:18:37,950 --> 00:18:40,225 orang, tahu bahawa saya lakukan? 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 perlu saya lakukan untuk kesimpulan tegas bahawa saya dilakukan? 532 00:18:46,900 --> 00:18:48,230 Mungkin salah satu pas lagi. 533 00:18:48,230 --> 00:18:48,430 Betul? 534 00:18:48,430 --> 00:18:51,760 Kerana semua yang saya tahu dari yang sebelumnya pas adalah bahawa saya diperbetulkan kesilapan. 535 00:18:51,760 --> 00:18:53,920 Dan yang bermakna, mungkin ada masih kesilapan lain 536 00:18:53,920 --> 00:18:54,840 yang saya perlukan untuk membetulkan. 537 00:18:54,840 --> 00:18:58,680 Jadi saya hanya boleh pasti oleh gulung semula, dan kemudian memeriksa, satu kepada dua, 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 kerja. 540 00:19:02,510 --> 00:19:05,990 >> Saya pasti boleh ingat bahawa saya tidak bekerja dengan sesuatu seperti pembolehubah, 541 00:19:05,990 --> 00:19:06,975 suka int an. 542 00:19:06,975 --> 00:19:12,490 Memanggilnya swap, dan jika swap adalah 0 sekali saya mendapatkan di sini, dan ia bermula pada 0, maka 543 00:19:12,490 --> 00:19:15,520 Saya hanya akan menjadi bodoh untuk terus pergi ke belakang dan sebagainya, menyemak semula, dan 544 00:19:15,520 --> 00:19:16,450 sekali lagi, dan sekali lagi, bukan? 545 00:19:16,450 --> 00:19:18,450 Kerana anda terjebak dalam beberapa jenis gelung tak terhingga. 546 00:19:18,450 --> 00:19:21,250 Jadi sebaik sahaja ada 0 swap, kita boleh mengatakan bahawa ini 547 00:19:21,250 --> 00:19:23,810 algoritma memang lengkap. 548 00:19:23,810 --> 00:19:25,400 >> Sekarang, mari kita meletakkan nama pada ini. 549 00:19:25,400 --> 00:19:28,930 Algoritma yang saya mencadangkan kita hanya dilaksanakan adalah sesuatu yang dipanggil gelembung 550 00:19:28,930 --> 00:19:32,800 jenis, yang dikenali sebagai apa-apa dalam erti kata bahawa nombor-nombor yang lebih besar daripada jenis 551 00:19:32,800 --> 00:19:37,990 buih mereka untuk sampai ke atas, atau sehingga untuk akhir pelbagai nombor. 552 00:19:37,990 --> 00:19:40,270 Tetapi bagaimana berkesan adalah algoritma ini? 553 00:19:40,270 --> 00:19:44,600 Berapa banyak langkah-langkah yang tidak saya secara fizikal perlu mengambil, sebagai contoh, untuk menyelesaikan 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 hingga lima? 557 00:19:49,550 --> 00:19:51,420 OK, terlalu banyak akhirnya akan menjadi jawapannya. 558 00:19:51,420 --> 00:19:54,960 Tetapi kemudian, bilangan tertentu tidak begitu menarik. 559 00:19:54,960 --> 00:19:56,670 Mari umum sebagai n. 560 00:19:56,670 --> 00:20:00,520 Jadi, jika saya n orang di sini, dan mereka adalah, jenis, dalam susunan rawak di 561 00:20:00,520 --> 00:20:02,180 permulaan, dalam susunan asal. 562 00:20:02,180 --> 00:20:04,910 Nah, berapa banyak langkah-langkah yang tidak saya mempunyai untuk mengambil pas pertama? 563 00:20:04,910 --> 00:20:09,810 Ia adalah salah satu, dua, tiga, empat, lima, enam, dan mereka tujuh orang, maka 564 00:20:09,810 --> 00:20:13,670 itulah tujuh, enam -, supaya n minus one langkah kali pertama. 565 00:20:13,670 --> 00:20:16,280 >> Sekarang, berapa banyak langkah-langkah yang tidak saya mempunyai untuk mengambil apabila saya digulung? 566 00:20:16,280 --> 00:20:19,310 Nah, kita sebenarnya boleh dua kali ganda jika kita benar-benar mahu, tetapi untuk sekarang, saya 567 00:20:19,310 --> 00:20:22,300 hanya akan berkata, semua betul, lain n tolak 1. 568 00:20:22,300 --> 00:20:25,240 Jadi n tolak 1 akan mendapat menjengkelkan untuk mengesan, jadi mari kita 569 00:20:25,240 --> 00:20:26,400 hanya pusingan 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-langkah, memberi atau mengambil. 572 00:20:29,310 --> 00:20:31,930 >> Berapa kali saya mengambil satu langkah masa depan? 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 kini, dalam kes paling teruk, untuk contoh, berapa kali saya akan mempunyai 576 00:20:37,920 --> 00:20:41,730 pergi ke belakang dan sebagainya, belakang dan sebagainya, melaksanakan algoritma ini, bertukar-tukar 577 00:20:41,730 --> 00:20:44,620 orang-orang di setiap laluan, kira-kira? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Ini sebenarnya n kuasa dua, bukan? 580 00:20:50,010 --> 00:20:53,000 >> Kerana dalam kes paling teruk, anda boleh jenis daripada berfikir tentang perkara ini intuitif, 581 00:20:53,000 --> 00:20:54,800 walaupun ia mungkin mengambil sedikit sedikit masa untuk tenggelam masuk 582 00:20:54,800 --> 00:20:57,590 Dalam kes terburuk, apa yang akan ini tujuh orang kelihatan seperti, dalam 583 00:20:57,590 --> 00:21:00,230 segi susunan nombor mereka? 584 00:21:00,230 --> 00:21:01,460 Sepenuhnya ke belakang, bukan? 585 00:21:01,460 --> 00:21:02,815 Dan hanya untuk meniru itu, apakah 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, anda hanya boleh menyertai saya lebih di sini hanya satu kedua? 589 00:21:08,100 --> 00:21:08,880 Sebenarnya, tidak. 590 00:21:08,880 --> 00:21:10,150 Maaf Mike, memutar balik mari. 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, saya akan mencadangkan, hanya untuk kesederhanaan, yang Neil kini beliau 596 00:21:17,150 --> 00:21:18,510 kes terburuk mungkin. 597 00:21:18,510 --> 00:21:20,720 Tetapi ingat bagaimana saya telah melaksanakan 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 Kini mereka berada di luar perintah, jadi saya menetapkan. 600 00:21:26,640 --> 00:21:27,980 Jadi kamu menukar. 601 00:21:27,980 --> 00:21:31,630 Tetapi menganggap sekarang, berapa banyak lebih jauh Neil tidak perlu pergi? 602 00:21:31,630 --> 00:21:32,690 Ia kira-kira n. 603 00:21:32,690 --> 00:21:33,570 Anda tahu, ia tidak benar-benar n. 604 00:21:33,570 --> 00:21:36,040 Ia seperti, n tolak 1, tetapi saya mendapat trek menyimpan marah yang sedikit 605 00:21:36,040 --> 00:21:37,550 nombor, jadi mari kita hanya memanggilnya n. 606 00:21:37,550 --> 00:21:42,860 >> Jadi jika Neil bergerak satu langkah maksima setiap masa, dan untuk bergerak Neil satu langkah, 607 00:21:42,860 --> 00:21:46,580 Saya mempunyai untuk membuat pas benar-benar membosankan ini ke belakang dan sebagainya, ini adalah kira-kira 608 00:21:46,580 --> 00:21:52,080 melakukan ini, n langkah, sebanyak n kali, kerana ia akan membawa saya 609 00:21:52,080 --> 00:21:55,820 bahawa banyak langkah-langkah untuk mendapatkan Neil semua jalan ke mana dia tergolong. 610 00:21:55,820 --> 00:21:58,620 Apatah lagi orang lain jika anda semua semuanya salah diperintahkan juga. 611 00:21:58,620 --> 00:22:01,100 >> Jadi mari kita panggil jenis gelembung n kuasa dua. 612 00:22:01,100 --> 00:22:04,860 Masa berjalan algoritma ini, Prestasi algoritma ini, 613 00:22:04,860 --> 00:22:07,120 keberkesanan algoritma ini, kami hanya akan menerangkan lebih 614 00:22:07,120 --> 00:22:08,800 amnya n kuasa dua. 615 00:22:08,800 --> 00:22:11,650 Yang bagus, kerana saya boleh melakukan contoh yang sama dengan lapan orang, sembilan 616 00:22:11,650 --> 00:22:15,450 orang, satu juta orang, dan bahawa jawapan tidak akan berubah. 617 00:22:15,450 --> 00:22:18,870 >> Jadi, jika anda semua tidak keberatan, mari kita semula anda ke mana anda bermula. 618 00:22:18,870 --> 00:22:22,510 Dan mari kita cuba dua pendekatan yang lain dan lihat jika kita tidak boleh melakukan asasnya 619 00:22:22,510 --> 00:22:23,820 yang lebih baik daripada ini. 620 00:22:23,820 --> 00:22:27,130 Jadi kali ini, saya akan mencadangkan sejenis algoritma yang berbeza. 621 00:22:27,130 --> 00:22:29,950 Itu adalah sangat pandai daripada kita masa lalu, dan anda semua adalah hak untuk mempunyai 622 00:22:29,950 --> 00:22:32,470 naluri kanan hanya jenis daripada bertukar-tukar pasangan demi pasangan. 623 00:22:32,470 --> 00:22:36,500 Tetapi jika saya benar-benar mahu untuk pendekatan ini semata-mata, dan matlamat saya adalah untuk menggerakkan 624 00:22:36,500 --> 00:22:39,800 semua nombor sedikit cara ini, dan menolak semua nombor besar yang 625 00:22:39,800 --> 00:22:43,030 cara, mengapa tidak saya hanya berbuat demikian dalam paling naif cara yang mungkin dan lihat jika saya 626 00:22:43,030 --> 00:22:45,730 boleh melakukan lebih baik daripada apa yang merupakan agak algoritma 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 nombor yang agak kecil, jadi saya akan meninggalkan anda ada masa. 629 00:22:48,940 --> 00:22:50,610 Ooh, nombor dua adalah lebih baik. 630 00:22:50,610 --> 00:22:52,230 Jadi anda hanya boleh melangkah ke hadapan untuk seketika? 631 00:22:52,230 --> 00:22:55,670 Ini sedang bernombor paling kecil saya calon, dan saya akan ingat 632 00:22:55,670 --> 00:22:57,000 dengan, seperti, pembolehubah. 633 00:22:57,000 --> 00:22:57,930 Tetapi saya akan terus menyemak. 634 00:22:57,930 --> 00:22:59,890 Adakah terdapat seseorang yang nombor adalah lebih kecil? 635 00:22:59,890 --> 00:23:00,460 Enam, tidak. 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 menolak anda kembali jenis konsep. 638 00:23:04,050 --> 00:23:05,120 Neil akan tampil ke hadapan. 639 00:23:05,120 --> 00:23:08,440 Dan kini, berubah-ubah yang saya gunakan untuk menjejaki yang mempunyai terkecil 640 00:23:08,440 --> 00:23:11,390 nombor dikemaskini untuk mengandungi Neil lokasi itu. 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 OK, saya tahu Neil adalah yang paling kecil. 644 00:23:15,590 --> 00:23:18,110 Apakah perkara yang paling mudah bagi saya lakukan sekarang? 645 00:23:18,110 --> 00:23:21,410 Saya tidak akan membuang masa saya dengan hanya menggelegak Neil satu tempat ke kiri. 646 00:23:21,410 --> 00:23:25,350 Kenapa saya tidak hanya meletakkan Neil di mana beliau milik, yang sudah tentu di mana? 647 00:23:25,350 --> 00:23:26,160 >> Semua jalan pada permulaan. 648 00:23:26,160 --> 00:23:27,720 Jadi Neil, datang dengan saya. 649 00:23:27,720 --> 00:23:28,910 Dan apakah nama anda lagi? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Rahmat. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. MALAN: Rahmat. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Jadi Grace, malangnya, anda jenis di jalan. 654 00:23:32,490 --> 00:23:34,290 Jadi bagaimana kita menyelesaikan masalah ini? 655 00:23:34,290 --> 00:23:34,490 Betul? 656 00:23:34,490 --> 00:23:37,500 Jika ini adalah array, terdapat hanya tujuh lokasi. 657 00:23:37,500 --> 00:23:40,830 Ingat bahawa, dengan Rob, kita bercakap tentang mengisytiharkan peringkat umur, dan kita hanya mempunyai 658 00:23:40,830 --> 00:23:41,740 beberapa terhingga peringkat umur? 659 00:23:41,740 --> 00:23:42,535 Idea yang sama di sini. 660 00:23:42,535 --> 00:23:44,300 Kita hanya mempunyai beberapa terhingga Ints. 661 00:23:44,300 --> 00:23:47,590 Grace adalah jenis dalam kami cara, jadi bagaimana kita menetapkan? 662 00:23:47,590 --> 00:23:49,555 >> Cara yang paling mudah adalah seperti, Grace, maaf. 663 00:23:49,555 --> 00:23:51,870 Anda akan perlu pergi ke ada supaya kita boleh membuat bilik. 664 00:23:51,870 --> 00:23:55,290 Sekarang, jika anda berfikir tentang perkara ini, mungkin kita hanya membuat masalah lebih teruk. 665 00:23:55,290 --> 00:23:58,510 Dan mungkin kita lakukan, kerana apa yang jika Rahmat berada di tempat yang betul? 666 00:23:58,510 --> 00:24:01,730 Tetapi kita tahu dia tidak, kerana sebaliknya, dia akan menjadi 667 00:24:01,730 --> 00:24:03,980 berdiri di hadapan dan bukannya Neil pada masa ini, bukan? 668 00:24:03,980 --> 00:24:05,550 Kita sudah diperiksa nombor dia keluar. 669 00:24:05,550 --> 00:24:05,770 >> Baiklah. 670 00:24:05,770 --> 00:24:09,110 Jadi sekarang, Neil adalah di tempat yang betul, dan Boleh saya lakukan pengoptimuman sedikit. 671 00:24:09,110 --> 00:24:11,740 Untuk minit seterusnya, saya akan mengabaikan Neil semua bersama-sama, supaya tidak 672 00:24:11,740 --> 00:24:15,280 membuang masa, atau tidak sengaja menukar ke tempat yang salah. 673 00:24:15,280 --> 00:24:17,805 Jadi sekarang, bagaimana saya mencari seterusnya elemen itulah yang paling kecil? 674 00:24:17,805 --> 00:24:18,480 Dua. 675 00:24:18,480 --> 00:24:20,225 Itulah beberapa cukup baik, jika anda mahu melangkah ke hadapan dan 676 00:24:20,225 --> 00:24:21,100 Saya akan mengingati 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 biarlah saya bergerak anda untuk tempat yang tepat anda. 680 00:24:26,800 --> 00:24:28,470 Dan kita hanya mendapat bernasib baik kali ini. 681 00:24:28,470 --> 00:24:31,350 >> Sekarang, saya akan mengabaikan dua lelaki, dan kini melakukan satu lagi 682 00:24:31,350 --> 00:24:32,260 melalui ini. 683 00:24:32,260 --> 00:24:33,490 Enam, bahawa beberapa agak kecil. 684 00:24:33,490 --> 00:24:34,300 Ayuh ke hadapan. 685 00:24:34,300 --> 00:24:35,220 Oh, maaf. 686 00:24:35,220 --> 00:24:37,640 Bilangan Grace adalah lebih baik, jadi langkah di hadapan. 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 Nombor tiga adalah lebih baik. 691 00:24:41,550 --> 00:24:42,290 Tujuh. 692 00:24:42,290 --> 00:24:42,720 Five. 693 00:24:42,720 --> 00:24:43,550 Dan kini 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 yang paling kecil elemen saya dipilih. 697 00:24:47,050 --> 00:24:49,160 Di 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 sekali 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 adalah di jalan. 703 00:24:53,220 --> 00:24:54,640 Apakah perkara yang paling mudah untuk dilakukan? 704 00:24:54,640 --> 00:24:58,390 Menukar kedua-dua lelaki dan berterusan. 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 paling kecil? 707 00:25:00,170 --> 00:25:01,030 Empat. 708 00:25:01,030 --> 00:25:01,990 Biar saya hanya jenis menipu. 709 00:25:01,990 --> 00:25:03,090 Lima akan menjadi yang paling kecil. 710 00:25:03,090 --> 00:25:05,220 Saya dapati akan datang, jika, anda mahu melangkah ke hadapan, apa yang saya perlu lakukan dengan 711 00:25:05,220 --> 00:25:06,820 lelaki ini, dengan Gabe? 712 00:25:06,820 --> 00:25:08,450 Bertukar lagi. 713 00:25:08,450 --> 00:25:10,740 Jadi sekarang, masih sedikit daripada perintah. 714 00:25:10,740 --> 00:25:14,140 Saya dapati Gabe menjadi kecil, jadi Saya pop dia keluar, bergerak anda semua lebih. 715 00:25:14,140 --> 00:25:15,190 Dan dilakukan. 716 00:25:15,190 --> 00:25:17,200 >> Jadi jawapannya adalah sama. 717 00:25:17,200 --> 00:25:18,600 Keputusan akhir adalah sama. 718 00:25:18,600 --> 00:25:22,730 Antara kedua-dua algoritma yang lebih baik? 719 00:25:22,730 --> 00:25:23,500 Yang kedua, saya mendengar. 720 00:25:23,500 --> 00:25:24,252 Mengapa? 721 00:25:24,252 --> 00:25:25,900 >> SPEAKER 3: Ia n langkah [didengar]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. MALAN: Ia langkah n paling banyak. 723 00:25:27,600 --> 00:25:28,490 Menarik. 724 00:25:28,490 --> 00:25:30,610 Jadi adakah ia walaupun? 725 00:25:30,610 --> 00:25:33,630 Jadi bagaimana saya mencari elemen terkecil? 726 00:25:33,630 --> 00:25:37,060 Berapa banyak langkah-langkah yang tidak saya perlu mengambil mendapati elemen terkecil? 727 00:25:37,060 --> 00:25:39,220 Saya telah kelihatan sepanjang jalan pada akhirnya, bukan? 728 00:25:39,220 --> 00:25:41,530 Kerana dalam kes paling teruk, apa jika Neil adalah di sini? 729 00:25:41,530 --> 00:25:45,700 Jadi hanya mencari elemen terkecil mengambil langkah-langkah yang saya n, atau n tolak 1. 730 00:25:45,700 --> 00:25:46,100 Tetapi, OK. 731 00:25:46,100 --> 00:25:46,980 Jadi menetapkan Neil. 732 00:25:46,980 --> 00:25:48,740 Ingat bahawa, satu minit atau lebih yang lalu. 733 00:25:48,740 --> 00:25:51,680 >> Tetapi bagaimana saya mendapati seterusnya elemen terkecil? 734 00:25:51,680 --> 00:25:54,830 Ia n tolak 1, atau n tolak 2 benar-benar, daripada bilangan langkah-langkah. 735 00:25:54,830 --> 00:25:55,440 Jadi OK. 736 00:25:55,440 --> 00:25:57,390 Jadi saya n tolak 2. 737 00:25:57,390 --> 00:25:57,600 Baiklah. 738 00:25:57,600 --> 00:25:59,130 Jadi yang merasakan sedikit lebih baik. 739 00:25:59,130 --> 00:25:59,730 Baiklah. 740 00:25:59,730 --> 00:26:03,270 Berapa banyak langkah-langkah masa depan mencari nombor tiga? 741 00:26:03,270 --> 00:26:04,420 Jadi n tolak 4. 742 00:26:04,420 --> 00:26:07,670 Jadi ia berkurangan, satu kurang melangkah pada setiap lelaran. 743 00:26:07,670 --> 00:26:08,740 Jadi ini tidak berasa lebih baik, bukan? 744 00:26:08,740 --> 00:26:13,450 Jika masa lalu, ia adalah kira-kira n kali n, masa ini, ia n tolak 1, ditambah n tolak 745 00:26:13,450 --> 00:26:16,500 2, ditambah n tolak 3, campur n tolak 4, dot, dot, dot. 746 00:26:16,500 --> 00:26:18,750 Tetapi jika anda ingat dari sekolah tinggi anda buku teks, menipu sedikit 747 00:26:18,750 --> 00:26:24,380 kunci di belakang yang mempunyai formula, jika anda menambah siri nombor, 748 00:26:24,380 --> 00:26:31,280 apakah jumlah langkah-langkah yang akan menjadi yang saya ambil di sini? 749 00:26:31,280 --> 00:26:36,580 >> Ini adalah salah satu dari orang-orang, seperti, n tolak 1, kali n, dibahagikan dengan 2. 750 00:26:36,580 --> 00:26:39,040 Jadi biarlah saya melihat jika saya boleh tarik sehingga ini hanya seketika. 751 00:26:39,040 --> 00:26:42,230 Dan sekali lagi, saya jenis pembundaran beberapa nombor hanya untuk menjaga hidup kita mudah, 752 00:26:42,230 --> 00:26:47,830 tetapi seperti yang saya ingat, ia adalah sesuatu seperti jika Saya n tolak 1 perkara, maka n tolak 753 00:26:47,830 --> 00:26:53,570 2, maka n tolak 3, ia adalah kira-kira sesuatu seperti ini lebih 2, dan jika saya 754 00:26:53,570 --> 00:26:55,510 membiak di luar ini, itulah sebenarnya n persegi. 755 00:26:55,510 --> 00:26:58,940 Itu tidak berasa terlalu baik. n tolak n lebih 2. 756 00:26:58,940 --> 00:27:00,350 >> Tetapi di sini perkara itu. 757 00:27:00,350 --> 00:27:03,720 Dalam sains komputer, apabila masalah mula mendapat menarik ialah apabila n 758 00:27:03,720 --> 00:27:04,700 mendapat benar-benar besar. 759 00:27:04,700 --> 00:27:08,110 Dan apabila n menjadi benar-benar besar, yang mana satu nilai-nilai ini akan menguasai semua 760 00:27:08,110 --> 00:27:09,750 yang lain? 761 00:27:09,750 --> 00:27:10,990 Ia adalah jenis n kuasa dua, bukan? 762 00:27:10,990 --> 00:27:13,340 Ya, membahagikan oleh 2 adalah cukup baik. 763 00:27:13,340 --> 00:27:16,740 Tetapi jika anda bercakap tentang berbilion-bilion keping data, atau berjuta-juta 764 00:27:16,740 --> 00:27:18,700 keping data, OK, jadi anda dua kali lebih cepat. 765 00:27:18,700 --> 00:27:22,440 Tetapi yang benar-benar peduli jika jumlah yang besar, jika faktor ini adalah apa yang mendapat 766 00:27:22,440 --> 00:27:23,040 yang lebih besar dan lebih besar. 767 00:27:23,040 --> 00:27:25,990 Dan sesungguhnya, ia membuatkan lebih perbezaan daripada lelaki ini. 768 00:27:25,990 --> 00:27:29,120 Jadi, walaupun anda semua adalah betul, algoritma kedua, kami akan memanggilnya 769 00:27:29,120 --> 00:27:32,970 jenis pemilihan, adalah, dalam dunia sebenar, sedikit lebih cepat berpotensi, kerana saya 770 00:27:32,970 --> 00:27:35,360 mengambil kurang dan kurang langkah setiap kali. 771 00:27:35,360 --> 00:27:37,340 >> Ia tidak benar-benar asas cepat. 772 00:27:37,340 --> 00:27:41,430 Kerana jika kita benar-benar bermain ini keluar untuk nilai n yang besar, pada akhir 773 00:27:41,430 --> 00:27:44,750 hari, untuk n cukup besar, ia masih akan berasa cukup perlahan. 774 00:27:44,750 --> 00:27:46,770 Baiklah, biar saya mengambil satu pas lepas pada itu. 775 00:27:46,770 --> 00:27:48,920 Itulah yang saya akan memanggil jenis pilihan. 776 00:27:48,920 --> 00:27:51,040 Bolehkah anda semua semula diri satu masa lalu? 777 00:27:51,040 --> 00:27:53,550 Dan dalam kes ini lepas, saya akan untuk mencadangkan sesuatu 778 00:27:53,550 --> 00:27:54,970 dipanggil jenis kemasukan. 779 00:27:54,970 --> 00:27:57,470 Jenis kemasukan menjadi konsep, sedikit berbeza. 780 00:27:57,470 --> 00:28:00,980 >> Daripada pergi ke belakang dan sebagainya dan memilih elemen terkecil, saya 781 00:28:00,980 --> 00:28:05,030 hanya akan berurusan dengan masing-masing lelaki kerana saya bertemu dengan mereka, dan memasukkan 782 00:28:05,030 --> 00:28:06,850 mereka ke tempat yang betul. 783 00:28:06,850 --> 00:28:10,160 Jadi, saya hanya akan bermula dengan Grace, dan saya melihat bahawa dia adalah nombor empat. 784 00:28:10,160 --> 00:28:11,720 Di manakah nombor empat tergolong? 785 00:28:11,720 --> 00:28:14,940 Saya belum mula menyusun apa-apa, jadi Grace mendapat untuk tinggal di sana. 786 00:28:14,940 --> 00:28:18,355 Dan sekarang saya akan mendakwa, jika anda boleh mengambil langkah ke kanan anda, ini 787 00:28:18,355 --> 00:28:21,650 senarai disusun saya, ini adalah saya senarai baki Unsorted. 788 00:28:21,650 --> 00:28:23,260 Jadi sekarang saya akan meneruskan akan datang, dan apa nama 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 nombor dua. 792 00:28:25,375 --> 00:28:27,490 Jadi, saya akan membawa anda keluar untuk seketika. 793 00:28:27,490 --> 00:28:30,940 Dan sekarang, di manakah anda tergolong dalam pelbagai ini? 794 00:28:30,940 --> 00:28:32,360 Jadi untuk hak Rahmat. 795 00:28:32,360 --> 00:28:35,670 Jadi sekali lagi, kita jenis membuat Grace melakukan banyak kerja di sini. 796 00:28:35,670 --> 00:28:37,290 Di manakah kita meletakkan anda? 797 00:28:37,290 --> 00:28:40,120 Jadi, kita akan ke slaid anda ke kiri, dan memasukkan Branson sana. 798 00:28:40,120 --> 00:28:41,680 Tetapi sekarang saya mendakwa bahawa anda semua telah selesai. 799 00:28:41,680 --> 00:28:43,240 Tetapi notis, saya tidak menggunakan ruang tambahan. 800 00:28:43,240 --> 00:28:45,130 Ia masih 2 unsur-unsur di sini, 5 di sini. 801 00:28:45,130 --> 00:28:47,910 Jumlah saiz array adalah 7, jadi saya tidak menipu, semua betul? 802 00:28:47,910 --> 00:28:51,950 >> Jadi sekarang kita mempunyai, dengan Gabe di sini, nombor enam, di mana anda tergolong? 803 00:28:51,950 --> 00:28:52,650 Anda bernasib baik lagi. 804 00:28:52,650 --> 00:28:53,820 Jadi anda mendapat untuk tinggal di sana. 805 00:28:53,820 --> 00:28:57,210 Hanya mengambil satu langkah yang sedikit ke kanan hanya untuk membuat jelas bahawa anda disusun. 806 00:28:57,210 --> 00:29:00,520 Dan sekarang kita mempunyai Neil lagi, bilangan satu, di mana anda pergi? 807 00:29:00,520 --> 00:29:03,540 Dan kini adalah di mana kita akan mula melihat bahawa algoritma ini, walaupun pada pertama 808 00:29:03,540 --> 00:29:05,950 pandangan, berasa cukup bijak, menonton apa yang akan berlaku. 809 00:29:05,950 --> 00:29:07,370 Jika anda boleh melangkah ke hadapan. 810 00:29:07,370 --> 00:29:09,260 >> Di mana kita mahu meletakkan 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 melakukan ini langkah demi langkah. 813 00:29:12,970 --> 00:29:15,620 Gabe, di mana anda perlu pergi? 814 00:29:15,620 --> 00:29:19,590 Ya, supaya mengambil satu langkah yang besar, atau dua setengah langkah-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 yang lain. 819 00:29:23,500 --> 00:29:24,960 Dan akhirnya, Branson? 820 00:29:24,960 --> 00:29:25,460 Satu lagi langkah. 821 00:29:25,460 --> 00:29:27,190 Dan sekarang kita boleh meletakkan Neil ke tempatnya. 822 00:29:27,190 --> 00:29:28,440 >> Jadi sekarang, terus logik ini. 823 00:29:28,440 --> 00:29:32,420 Walaupun kita tidak beralih Neil atas, dan ke atas, dan ke atas, untuk meletakkan dia 824 00:29:32,420 --> 00:29:36,420 mana dia pergi, dalam kes paling teruk, nombor yang berikutnya kita mungkin menghadapi boleh 825 00:29:36,420 --> 00:29:42,220 menjadi nombor, berkata, terdapat sebilangan sifar, maka kita akan beralih semua 826 00:29:42,220 --> 00:29:42,730 lelaki ini. 827 00:29:42,730 --> 00:29:44,950 Katakan bahawa ada beberapa, negatif satu, maka kita perlu beralih 828 00:29:44,950 --> 00:29:46,080 semua lelaki. 829 00:29:46,080 --> 00:29:48,500 Oleh itu, kita benar-benar hanya jenis Melibas masalah di sekeliling, seperti yang kita 830 00:29:48,500 --> 00:29:52,620 memindahkan perbelanjaan daripada proses pemilihan supaya kemasukan 831 00:29:52,620 --> 00:29:56,930 proses, seperti yang anda lelaki hanya mempunyai untuk bergerak kira-kira n tolak sesuatu 832 00:29:56,930 --> 00:29:57,940 beberapa langkah. 833 00:29:57,940 --> 00:30:01,200 Dan bilangan yang langkah-langkah yang hanya akan meningkat kerana saya memilih lebih nombor, 834 00:30:01,200 --> 00:30:04,730 jika saya perlu menyimpan shoving kamu belakang, dan kembali, dan kembali. 835 00:30:04,730 --> 00:30:08,320 >> Jadi perkara yang menyedihkan sekarang ialah semua ini algoritma n kuasa dua. 836 00:30:08,320 --> 00:30:10,570 Mari kita pergi ke hadapan dan terima kasih kepada lelaki, dan menggambarkan ini sedikit 837 00:30:10,570 --> 00:30:11,090 berbeza. 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 >> Baiklah. 841 00:30:15,030 --> 00:30:16,280 Terdapat anda pergi. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Terima kasih kerana - 844 00:30:18,470 --> 00:30:19,190 >> Branson: [didengar] menyimpan nombor. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. MALAN: Tidak, anda boleh menyimpan nombor juga. 846 00:30:21,990 --> 00:30:23,440 Baiklah. 847 00:30:23,440 --> 00:30:24,100 Baik dilakukan. 848 00:30:24,100 --> 00:30:25,300 Baiklah. 849 00:30:25,300 --> 00:30:30,510 Jadi mari kita lihat jika kita tidak boleh kini merumuskan lebih cepat, dan lebih visual, 850 00:30:30,510 --> 00:30:33,410 apa yang hanya berlaku di sini seperti berikut. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Saya akan pergi ke hadapan dan tarik sehingga Firefox. 853 00:30:38,770 --> 00:30:41,310 Kami akan menghubungkan demonstrasi ini di laman web kursus ini. 854 00:30:41,310 --> 00:30:43,870 Java adalah sedikit menjengkelkan untuk mendapatkan kerja dalam sesetengah pelayar hari ini. 855 00:30:43,870 --> 00:30:46,760 Jadi, jika anda bermain dengan ini di rumah, menyedari bahawa anda mungkin perlu menggunakan Firefox 856 00:30:46,760 --> 00:30:47,990 untuk mendapatkan ia bekerja. 857 00:30:47,990 --> 00:30:50,440 Dan apa yang saya akan lakukan dengan ini demonstrasi adalah seperti berikut. 858 00:30:50,440 --> 00:30:54,875 >> Di bahagian bawah, saya mempunyai sejumlah besar pilihan menu, termasuk permulaan dan 859 00:30:54,875 --> 00:30:55,840 butang berhenti. 860 00:30:55,840 --> 00:30:59,450 Juga, sebagai diketepikan, terdapat seolah-olah menjadi bug dalam program-program ini, di mana anda 861 00:30:59,450 --> 00:31:03,720 tidak boleh benar-benar melihat permulaan atau berhenti butang melainkan jika anda memegang Perintah atau Alt 862 00:31:03,720 --> 00:31:06,560 campur dan zoom in, yang ingin tahu menunjukkan kepada anda lebih banyak butang. 863 00:31:06,560 --> 00:31:09,090 Jadi hanya FYI jika anda bermain dengan ini di rumah. 864 00:31:09,090 --> 00:31:12,870 Sekarang saya akan klik Mula dalam hanya masa, selepas menyatakan kelewatan, 865 00:31:12,870 --> 00:31:16,810 seperti, 200 milisaat di sini, hanya supaya kita dapat melihat apa yang berlaku. 866 00:31:16,810 --> 00:31:20,180 >> Jadi saya mendakwa bahawa ini adalah visualisasi a algoritma yang pertama 867 00:31:20,180 --> 00:31:23,730 lelaki ini lakukan, jenis buih, di mana kita orang bertukar pasangan-bijak. 868 00:31:23,730 --> 00:31:27,490 Wawasan utama untuk visualisasi ini ialah ketinggian bar 869 00:31:27,490 --> 00:31:30,510 mewakili saiz nombor. 870 00:31:30,510 --> 00:31:32,210 Oleh itu, lebih tinggi bar, lebih besar nombor. 871 00:31:32,210 --> 00:31:33,680 Pendek bar, bilangan yang lebih kecil. 872 00:31:33,680 --> 00:31:38,630 Dan jika anda notis, kita akan melalui lelaran pertama algoritma ini, 873 00:31:38,630 --> 00:31:42,620 bertukar-tukar nombor besar dan kecil, supaya sebilangan kecil datang pertama dan 874 00:31:42,620 --> 00:31:44,280 bilangan besar pergi ke kanan. 875 00:31:44,280 --> 00:31:48,770 >> Dan sebaik sahaja kita mendapat akhir pelbagai banyak lebih nombor daripada tujuh, kami 876 00:31:48,770 --> 00:31:49,900 akan kembali ke permulaan. 877 00:31:49,900 --> 00:31:51,140 Dan menjangka ini. 878 00:31:51,140 --> 00:31:54,860 Pada yang jauh kiri, lelaki yang sedikit akan untuk menukar ke tepi, dan ini 879 00:31:54,860 --> 00:31:56,010 proses mengulangi. 880 00:31:56,010 --> 00:31:59,450 Sekarang visualisasi ini dengan cepat mendapat membosankan, jadi biarlah saya pergi ke hadapan dan berhenti 881 00:31:59,450 --> 00:32:04,170 ia, tukar kelewatan sesuatu yang lebih cepat hanya untuk mendapatkan sekarang, rasa untuk 882 00:32:04,170 --> 00:32:05,060 algoritma ini. 883 00:32:05,060 --> 00:32:07,840 >> Jadi, walaupun saya telah dipercepatkan ia, ini adalah seperti menaik taraf pemproses saya, membeli 884 00:32:07,840 --> 00:32:08,580 sebuah komputer baru. 885 00:32:08,580 --> 00:32:12,980 Saya tidak asasnya berubah saya algoritma, tetapi anda benar-benar boleh melihat lebih banyak 886 00:32:12,980 --> 00:32:16,800 jelas daripada dengan manusia, yang besar nombor-nombor itu menggelegak sehingga ke atas, 887 00:32:16,800 --> 00:32:20,900 dan nombor-nombor kecil yang menggelegak turun ke bawah. 888 00:32:20,900 --> 00:32:22,390 Dan sekarang perkara ini di sini disusun. 889 00:32:22,390 --> 00:32:25,260 Dan sebagai diketepikan, di dataran, ada hanya beberapa simpan kira di sana untuk 890 00:32:25,260 --> 00:32:28,010 membantu anda mengira berapa banyak perbandingan, atau berapa banyak swap mempunyai 891 00:32:28,010 --> 00:32:28,950 sebenarnya telah dilakukan. 892 00:32:28,950 --> 00:32:30,750 >> Nah, mari kita cuba salah satu yang lain yang kita lihat. 893 00:32:30,750 --> 00:32:37,116 Biar saya klik pada jenis buih di sini, dan biarlah saya memilih, dan laman web ini secara keseluruhan 894 00:32:37,116 --> 00:32:38,936 adalah sebuah kereta kecil. 895 00:32:38,936 --> 00:32:41,155 Mari kita menerima risiko dan berjalan lagi. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Ada kita pergi. 898 00:32:45,030 --> 00:32:47,180 Jadi mari kita buat jenis pilihan. 899 00:32:47,180 --> 00:32:49,140 Saya tidak tahu mengapa menu muncul di sana. 900 00:32:49,140 --> 00:32:54,070 Mari kita zoom dalam untuk menetapkan bahawa bug, menukar ini kepada 50. 901 00:32:54,070 --> 00:32:56,020 Ah, mari kita benar-benar melakukan yang lebih cepat. 902 00:32:56,020 --> 00:32:59,160 Lima milisaat atau lebih, dan Mula. 903 00:32:59,160 --> 00:33:00,470 >> Jadi ini adalah jenis pilihan. 904 00:33:00,470 --> 00:33:03,070 Jadi sekali lagi, berfikir tentang apa yang kita lakukan dengan manusia di sini. 905 00:33:03,070 --> 00:33:08,490 Kami telah melalui pelbagai dan dipilih unsur yang paling kecil lagi, 906 00:33:08,490 --> 00:33:09,250 dan sekali lagi, dan lagi. 907 00:33:09,250 --> 00:33:11,110 Sekarang saya mendakwa bahawa masih cukup buruk. 908 00:33:11,110 --> 00:33:15,010 Ia masih n kuasa dua, memberi atau mengambil, tetapi ia adalah, dalam dunia sebenar, sedikit 909 00:33:15,010 --> 00:33:18,280 lebih cepat, kerana saya memang mengambil sedikit kurang langkah-langkah setiap kali. 910 00:33:18,280 --> 00:33:19,800 Tetapi kita hanya bercakap 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 Kami tidak bercakap 40 juta. 913 00:33:23,200 --> 00:33:27,430 Jadi ia tidak benar-benar jelas bagi saya bahawa sememangnya keuntungan yang ketara. 914 00:33:27,430 --> 00:33:32,530 >> Izinkan saya kembali dan menukar kepada kami algoritma ketiga, yang telah memilih 915 00:33:32,530 --> 00:33:33,180 jenis kemasukan. 916 00:33:33,180 --> 00:33:36,380 Dan kini ia benar-benar kereta kerana menu benar-benar tidak perlu di bawah sana. 917 00:33:36,380 --> 00:33:40,840 Jadi sekarang kita akan skrol kembali di sini dan mula algoritma ini. 918 00:33:40,840 --> 00:33:43,270 Sorak, mula dan berhenti. 919 00:33:43,270 --> 00:33:47,160 Jadi jenis ini salah satu mempunyai corak cantik kepadanya, di mana kita sekali lagi 920 00:33:47,160 --> 00:33:50,240 memasukkan manusia, atau dalam kes ini, ke dalam bar 921 00:33:50,240 --> 00:33:52,620 lokasi yang sesuai mereka. 922 00:33:52,620 --> 00:33:55,430 Dan ia sudah dilakukan sebelum Saya menoleh. 923 00:33:55,430 --> 00:33:58,940 Tetapi yang satu ini juga, dalam teori, masih n kuasa dua. 924 00:33:58,940 --> 00:34:01,430 >> Jadi mari kita lihat jika kita tidak boleh merumuskan ini seperti berikut. 925 00:34:01,430 --> 00:34:04,750 Saya akan pergi ke hadapan dan hanya untuk memberi kita jenis cara biasa bercakap 926 00:34:04,750 --> 00:34:08,489 mengenai perkara-perkara ini, izinkan saya memperkenalkan hanya sedikit catatan di sini. 927 00:34:08,489 --> 00:34:12,480 Anda akan melihat sesuatu yang dipanggil besar O, kerana ia adalah benar-benar besar-besaran 928 00:34:12,480 --> 00:34:16,320 O. Dan ini adalah cara yang komputer ahli sains atau ahli matematik juga menggunakan 929 00:34:16,320 --> 00:34:19,230 untuk menggambarkan masa larian beberapa algoritma. 930 00:34:19,230 --> 00:34:21,400 Berapa banyak langkah-langkah yang ia benar-benar mengambil? 931 00:34:21,400 --> 00:34:25,080 >> Sekarang saya akan memalukan diri saya dengan tulisan saya di sini hanya seketika. 932 00:34:25,080 --> 00:34:29,020 Tetapi biarlah saya pergi ke hadapan dan mengatakan bahawa ini akan menjadi O besar di sini. 933 00:34:29,020 --> 00:34:33,610 Dan izinkan saya memperkenalkan satu lagi simbol, omega modal. 934 00:34:33,610 --> 00:34:37,080 Omega akan menjadi sebaliknya, pada asasnya, daripada besar O. Manakala besar O 935 00:34:37,080 --> 00:34:40,790 bermakna, dalam kes paling teruk, berapa banyak masa beberapa algoritma mungkin mengambil masa, dalam 936 00:34:40,790 --> 00:34:43,480 segi n, Omega akan menjadi berapa banyak masa ia mungkin 937 00:34:43,480 --> 00:34:45,409 mengambil mana-mana yang terbaik. 938 00:34:45,409 --> 00:34:48,090 Dan kita akan melihat apa yang kita maksudkan dengan hal terbaik dalam seketika. 939 00:34:48,090 --> 00:34:49,940 >> Jadi mari kita mulakan sesuatu yang mudah. 940 00:34:49,940 --> 00:34:54,719 Biar saya mulakan dengan carian linear. 941 00:34:54,719 --> 00:34:55,679 Jadi tidak sorting. 942 00:34:55,679 --> 00:34:58,000 Kami akan memanggil carian ini linear. 943 00:34:58,000 --> 00:35:01,140 Dan kini, membuat sedikit jadual keluar dari ini. 944 00:35:01,140 --> 00:35:06,600 Dan kini, dalam kes carian linear, dalam kes paling teruk, berapa banyak langkah-langkah yang 945 00:35:06,600 --> 00:35:11,770 ia akan membawa saya untuk mencari beberapa pilihan sewenang-wenangnya? 946 00:35:11,770 --> 00:35:14,540 Dan ada jumlah pintu n atau n jumlah nombor. 947 00:35:14,540 --> 00:35:15,940 Kes terburuk. 948 00:35:15,940 --> 00:35:18,800 Berapa banyak langkah-langkah yang saya akan perlu ambil untuk mencari nombor 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 Kerana ia mungkin semua cara lebih ke akhir. 952 00:35:23,680 --> 00:35:27,120 Begitu banyak seperti Jennifer dihadapi, Bilangan 50 adalah semua cara di atas, maka dalam 953 00:35:27,120 --> 00:35:30,760 kes terburuk carian linear adalah besar O n, kami akan katakan. 954 00:35:30,760 --> 00:35:33,430 >> Apa kira-kira mana-mana yang terbaik, jika anda mendapat benar-benar bertuah? 955 00:35:33,430 --> 00:35:36,200 Ia hanya akan mengambil satu langkah, atau nombor berterusan langkah-langkah. 956 00:35:36,200 --> 00:35:37,830 Jadi kita akan menggambarkan bahawa sebagai 1. 957 00:35:37,830 --> 00:35:39,010 Jadi ini adalah cukup baik. 958 00:35:39,010 --> 00:35:41,210 Sekarang apa jika kita melakukan sesuatu yang suka carian binari? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Carian supaya perduaan, yang paling teruk kes, mengambil berapa banyak masa? 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 mendengar dalam satu tempat pasangan. 963 00:35:51,310 --> 00:35:56,390 Jadi ia sebenarnya log n, memberi atau mengambil, kerana seperti yang kita membahagikan senarai pada separuh 964 00:35:56,390 --> 00:36:00,730 sekali lagi, dan sekali lagi, dan sekali lagi, kami dapat untuk mencari, akhirnya, nilai, 965 00:36:00,730 --> 00:36:04,750 jika ia di sana, tetapi ada tangkapan. 966 00:36:04,750 --> 00:36:08,590 Apakah andaian bahawa kita perlu mengambil mudah untuk carian binari? 967 00:36:08,590 --> 00:36:09,700 Ia perlu disusun. 968 00:36:09,700 --> 00:36:12,770 Ia tidak disusun, anda boleh berpecah perkara pada separuh lagi dan lagi, dan anda 969 00:36:12,770 --> 00:36:15,490 boleh pergi kiri, dan anda boleh pergi ke kanan, dan anda boleh pergi ke kiri dan kanan, tetapi anda 970 00:36:15,490 --> 00:36:18,070 tidak akan mendapati elemen jika senarai itu tidak diselesaikan, kerana 971 00:36:18,070 --> 00:36:18,790 anda mungkin ketinggalan. 972 00:36:18,790 --> 00:36:22,120 Kerana heuristik anda, untuk pergi kiri atau kanan akan menjadi cacat jika ia 973 00:36:22,120 --> 00:36:23,420 sememangnya tidak disusun. 974 00:36:23,420 --> 00:36:26,110 Jadi ada jenis kos tersembunyi untuk menggunakan sesuatu seperti ini. 975 00:36:26,110 --> 00:36:29,250 >> Sekarang, mari kita pergi ke sorting kami algoritma tidak mencari - 976 00:36:29,250 --> 00:36:31,140 oh, sebenarnya mari kita pergi kosong ini. 977 00:36:31,140 --> 00:36:33,190 Carian binari dalam kes ini? 978 00:36:33,190 --> 00:36:36,290 Ia juga 1 jika ia hanya berlaku untuk menjadi di tengah-tengah sangat pelbagai, atau 979 00:36:36,290 --> 00:36:37,810 tengah-tengah buku telefon. 980 00:36:37,810 --> 00:36:39,710 Sekarang mari kita buat apapun gelembung. 981 00:36:39,710 --> 00:36:42,570 Jadi sekali lagi, sekarang kita sedang memasuki pelbagai, bukan carian. 982 00:36:42,570 --> 00:36:47,220 >> Dalam kes terburuk, berapa banyak langkah-langkah yang kita tuntutan gelembung jenis akan mengambil? 983 00:36:47,220 --> 00:36:48,410 n kuasa dua. 984 00:36:48,410 --> 00:36:49,200 Jadi saya akan menarik itu. 985 00:36:49,200 --> 00:36:51,710 Aduh, tulisan saya kelihatan lebih teruk apabila ia dijangka bahawa besar. 986 00:36:51,710 --> 00:36:52,510 Baiklah. 987 00:36:52,510 --> 00:36:53,570 Jadi itu n kuasa dua. 988 00:36:53,570 --> 00:36:59,460 Dan dalam kes yang terbaik daripada jenis buih, berapa banyak langkah-langkah yang ia akan mengambil? 989 00:36:59,460 --> 00:37:00,980 1, saya dengar. 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, saya 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 dengar. 994 00:37:05,010 --> 00:37:06,670 Adakah saya mendengar 3? 995 00:37:06,670 --> 00:37:07,080 Baiklah. 996 00:37:07,080 --> 00:37:11,390 Jadi, saya telah mendengar 1, n, 2, tetapi mari kita mengambil selain sekurang-kurangnya orang yang awal pertama 997 00:37:11,390 --> 00:37:12,330 cadangan, 1. 998 00:37:12,330 --> 00:37:15,370 Ia bukan naluri yang tidak baik, kerana ia jenis corak di sini. 999 00:37:15,370 --> 00:37:19,670 Tetapi jika ia hanya mengambil 1 langkah, bagaimana dalam dunia saya boleh mendakwa bahawa senarai 1000 00:37:19,670 --> 00:37:22,900 disusun, kerana jika saya hanya dibenarkan mengambil 1 langkah, bagaimana banyak unsur 1001 00:37:22,900 --> 00:37:25,230 Saya sebenarnya boleh memeriksa untuk memastikan? 1002 00:37:25,230 --> 00:37:28,270 Nah, hanya 1, yang bermaksud ada n tolak 1 unsur-unsur yang boleh keluar dari 1003 00:37:28,270 --> 00:37:31,310 perintah, dan saya hanya berlaku selepas iman melihat 1 elemen bahawa 1004 00:37:31,310 --> 00:37:31,850 benda disusun. 1005 00:37:31,850 --> 00:37:33,930 Jadi 1 tidak betul di sini. 1006 00:37:33,930 --> 00:37:35,710 Jadi minimum, berapa banyak saya perlu 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 tolak 1, atau benar-benar, n, kerana saya perlu melihat setiap 1009 00:37:40,160 --> 00:37:42,190 elemen memastikan bahawa ia tidak keluar perintah. 1010 00:37:42,190 --> 00:37:44,750 Tetapi sekali lagi, kita akan menyelesaikan gelombang kami tangan di nombor yang lebih kecil dan 1011 00:37:44,750 --> 00:37:47,100 menganggap bahawa, sebagai n mendapat besar, mereka tidak menarik juga. 1012 00:37:47,100 --> 00:37:48,380 Jadi itulah jenis gelembung. 1013 00:37:48,380 --> 00:37:49,830 Dan kini, mari kita buat kedua-dua lepas. 1014 00:37:49,830 --> 00:37:53,520 Pemilihan jenis, dan kemudian kami akan melakukan jenis kemasukan. 1015 00:37:53,520 --> 00:37:57,160 Dan kemudian kita akan meniup anda minda dengan sesuatu yang lebih 1016 00:37:57,160 --> 00:37:58,926 lebih baik daripada semua ini. 1017 00:37:58,926 --> 00:38:00,410 Baiklah. 1018 00:38:00,410 --> 00:38:04,700 >> Apakah kes terburuk berjalan masa jenis pilihan? 1019 00:38:04,700 --> 00:38:05,680 >> SPEAKER 4: n kuasa dua. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. MALAN: n persegi, saya mendengar. 1021 00:38:06,710 --> 00:38:09,790 Tetapi mengapa n kuasa dua, intuitif? 1022 00:38:09,790 --> 00:38:11,170 >> SPEAKER 4: Kerana kita hanya melakukannya. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. MALAN: Kerana kita hanya melakukannya. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Baik jawapan. 1026 00:38:13,380 --> 00:38:16,660 Tetapi intuitif, mengapa pemilihan jenis n kuasa dua? 1027 00:38:16,660 --> 00:38:18,980 Apa yang perlu kita lakukan lagi dan lagi? 1028 00:38:18,980 --> 00:38:22,570 Kami terpaksa menyimpan imbasan melalui, adalah anda yang paling kecil, yang anda 1029 00:38:22,570 --> 00:38:24,020 kecil, adakah anda yang paling kecil. 1030 00:38:24,020 --> 00:38:27,480 Dan diberikan, kita dapat mengambil n langkah-langkah, maka n tolak 1, maka n tolak 2. 1031 00:38:27,480 --> 00:38:30,700 Tetapi jika anda jenis menambah mereka semuanya, atau mengambil ia pada kepercayaan bahawa saya telah menambah 1032 00:38:30,700 --> 00:38:34,810 mereka terlebih dahulu, kita akan mendapat kira-kira n kuasa dua tolak beberapa nombor yang lebih kecil. 1033 00:38:34,810 --> 00:38:36,730 Jadi, saya akan memanggil n ini kuasa dua. 1034 00:38:36,730 --> 00:38:39,530 Tetapi dengan jenis pemilihan dalam yang terbaik kes, berapa banyak langkah-langkah yang ia 1035 00:38:39,530 --> 00:38:40,632 akan mengambil saya? 1036 00:38:40,632 --> 00:38:41,840 >> SPEAKER 5: [didengar] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. MALAN: Ia malangnya masih n kuasa dua, bukan? 1038 00:38:44,350 --> 00:38:49,590 Kerana jika saya memilih yang paling kecil unsur, dan kami mempunyai tujuh orang di sini, 1039 00:38:49,590 --> 00:38:53,280 Saya hanya tahu, apabila saya sampai ke sangat akhir tahun, yang saya dapati yang paling kecil 1040 00:38:53,280 --> 00:38:55,670 nombor, di mana sahaja dia atau dia mungkin telah. 1041 00:38:55,670 --> 00:38:58,820 Tetapi bagaimana saya mendapati seterusnya bilangan paling kecil? 1042 00:38:58,820 --> 00:39:00,160 Saya perlu melakukan pas lain. 1043 00:39:00,160 --> 00:39:04,810 Jadi, dalam kes ini, apakah input untuk menyusun pemilihan? 1044 00:39:04,810 --> 00:39:07,830 Ia merupakan satu senarai jenis pun, nombor satu, nombor dua, nombor tiga, nombor empat. 1045 00:39:07,830 --> 00:39:08,600 Tetapi saya komputer. 1046 00:39:08,600 --> 00:39:10,190 Saya hanya boleh melihat pada satu-satu perkara pada satu masa. 1047 00:39:10,190 --> 00:39:12,465 Saya tidak boleh menyusun daripada mengambil langkah kembali seperti manusia dan berkata, 1048 00:39:12,465 --> 00:39:14,030 aduh, ini kelihatan betul. 1049 00:39:14,030 --> 00:39:17,580 >> Saya hanya boleh mengadili kebenaran dalam jenis pilihan dengan memilih 1050 00:39:17,580 --> 00:39:18,370 bilangan terkecil. 1051 00:39:18,370 --> 00:39:21,390 Tetapi, jika saya mencari nombor yang pertama, jika saya tidak tahu apa-apa lagi mengenai 1052 00:39:21,390 --> 00:39:24,460 nombor-nombor lain, yang saya tidak lakukan, semua saya tahu bahawa saya telah menyerahkan array 1053 00:39:24,460 --> 00:39:27,930 atau satu set pintu belakang yang nombor, satu-satunya cara yang saya tahu bahawa salah satu 1054 00:39:27,930 --> 00:39:28,680 adalah yang paling kecil? 1055 00:39:28,680 --> 00:39:32,440 Jika saya mendapat sepanjang jalan di sini dan sedar, damn, salah sememangnya yang paling kecil. 1056 00:39:32,440 --> 00:39:34,870 >> Tetapi bagaimana saya kemudian menentukan bahawa kedua-dua adalah yang paling kecil akan datang? 1057 00:39:34,870 --> 00:39:38,350 Dengan melakukan ketidakcekapan yang sama lagi dan lagi. 1058 00:39:38,350 --> 00:39:42,210 Jadi akhirnya, dengan jenis kemasukan, bagaimana, dalam kes terburuk, 1059 00:39:42,210 --> 00:39:44,990 adakah kita mengatakan ia melakukan? 1060 00:39:44,990 --> 00:39:49,100 Ia juga adalah n kuasa dua. 1061 00:39:49,100 --> 00:39:53,020 Dan bagaimana pula dengan kes yang terbaik? 1062 00:39:53,020 --> 00:39:56,282 Kami akan meninggalkan bahawa cliffhanger a. 1063 00:39:56,282 --> 00:40:00,090 Kami akan mengisi yang kosong masa akan datang, tetapi pada mulanya, biarlah saya mencadangkan supaya kita 1064 00:40:00,090 --> 00:40:02,620 asasnya melakukan lebih baik daripada semua ini, betul? 1065 00:40:02,620 --> 00:40:05,220 >> Jadi berfikir untuk diri sendiri apa kemasukan jenis yang akan menjadi. 1066 00:40:05,220 --> 00:40:06,910 Nah, yang tidak begitu dramatik, kerana saya satu-satunya 1067 00:40:06,910 --> 00:40:08,970 yang menyaksikan perubahan itu. 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 mempunyai yang agak demonstrasi yang berbeza. 1071 00:40:12,615 --> 00:40:16,580 Jika saya mengezum masuk di sini, anda akan melihat bahawa pada kiri kita mempunyai jenis gelembung, dalam 1072 00:40:16,580 --> 00:40:20,740 tengah kita mempunyai jenis pilihan, dan pada jauh betul, kita mempunyai sesuatu yang kita 1073 00:40:20,740 --> 00:40:23,380 tidak melihat lagi dipanggil bergabung jenis. 1074 00:40:23,380 --> 00:40:26,080 Tetapi menganggap apa yang kita telah lakukan di sini setakat hari ini. 1075 00:40:26,080 --> 00:40:29,200 Apabila Jennifer pertama datang di atas pentas, kita pergi melalui pelbagai nombor 1076 00:40:29,200 --> 00:40:33,750 sekali lagi, dan sekali lagi, dengan carian linear, dan kita ada masa linear berjalan, besar O 1077 00:40:33,750 --> 00:40:35,100 n, jadi untuk bercakap. 1078 00:40:35,100 --> 00:40:41,000 >> Apabila kita kini menganggap minggu pertama kelas, apabila kita telah membahagi dan menakluk, 1079 00:40:41,000 --> 00:40:43,740 dan kami telah buku telefon berair, dan Jennifer, dan kita secara kolektif 1080 00:40:43,740 --> 00:40:47,500 dimanfaatkan bahawa wawasan utama, iaitu untuk mengulangi diri lagi dan lagi oleh 1081 00:40:47,500 --> 00:40:50,930 entah bagaimana membuang, membuang, membuang, separuh daripada masalah, atau 1082 00:40:50,930 --> 00:40:55,320 secara amnya, membahagikan masalah pada separuh, dan kemudian merawat sekeping kecil 1083 00:40:55,320 --> 00:40:59,630 masalah seperti konsep bersamaan kepada yang lain, kita entah bagaimana tidak 1084 00:40:59,630 --> 00:41:00,910 asasnya yang lebih baik. 1085 00:41:00,910 --> 00:41:04,720 Tetapi dengan jenis buih, dengan pilihan jenis, dengan jenis kemasukan, kita telah boleh 1086 00:41:04,720 --> 00:41:06,560 ada pandangan itu bahawa Jennifer lakukan. 1087 00:41:06,560 --> 00:41:10,220 Kami cukup banyak hanya berjalan ke belakang dan sebagainya sejumlah besar masa, dan kita 1088 00:41:10,220 --> 00:41:12,650 perkara mengagak sedikit, bertukar-tukar dalam usaha 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 banyak daripada berjalan janggal belakang dan sebagainya. 1091 00:41:16,950 --> 00:41:21,160 Kami tidak benar-benar memanfaatkan sesuatu pintar seperti Jennifer tidak seperti membahagikan 1092 00:41:21,160 --> 00:41:22,040 dan menakluk. 1093 00:41:22,040 --> 00:41:25,620 >> Jadi bergabung jenis, sebaliknya, yang kita tidak akan melihat sehingga minggu depan, ia akan 1094 00:41:25,620 --> 00:41:29,540 untuk memanfaatkan bahawa idea utama dengan membahagikan input, dan kemudian mengurangkan separuh, dan kemudian 1095 00:41:29,540 --> 00:41:30,580 mengurangkan separuh, dan kemudian mengurangkan separuh. 1096 00:41:30,580 --> 00:41:34,590 Dan pada setiap lelaran gelung itu, menyusun separuh kiri, dan kanan 1097 00:41:34,590 --> 00:41:38,200 separuh, kemudian sebelah kiri separuh separuh kiri, dan separuh kanan kiri, kemudian 1098 00:41:38,200 --> 00:41:40,990 separuh kiri separuh yang betul, dan separuh benar separuh betul. 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 visual, tetapi ini adalah apa yang menanti kita minggu depan. 1101 00:41:46,170 --> 00:41:49,760 Dan secara umum, apabila kita berfikir sedikit agak sukar pada mana-mana masalah tersebut. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Kami telah n kuasa dua di sebelah kiri, n kuasa di tengah-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 sebenar anda. 1106 00:42:00,590 --> 00:42:02,040 Kami akan melihat anda pada hari Isnin. 1107 00:42:02,040 --> 00:42:05,163 >> [Tepuk tangan]