1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Bermain muzik] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. MALAN: Ini adalah CS50. 5 00:00:12,550 --> 00:00:14,612 Dan ini adalah permulaan minggu tiga. 6 00:00:14,612 --> 00:00:16,820 Jadi kita telah mendapat banyak menarik perkara yang melindungi hari ini. 7 00:00:16,820 --> 00:00:20,160 Banyak peluang-peluang untuk sukarelawan di atas pentas. 8 00:00:20,160 --> 00:00:22,780 Dan akhirnya, hari ini adalah tidak tentang kod sama sekali. 9 00:00:22,780 --> 00:00:24,820 Tetapi ia adalah tentang idea-idea, dan ia mengenai algoritma, 10 00:00:24,820 --> 00:00:28,420 dan benar-benar membawa kembali beberapa pengajaran daripada minggu sifar, 11 00:00:28,420 --> 00:00:31,910 mana ingat, kita diperkenalkan barang ganjil ini. 12 00:00:31,910 --> 00:00:33,880 Dan inspirasi pinjaman itu, untuk memulakan 13 00:00:33,880 --> 00:00:36,879 untuk menyelesaikan yang lebih canggih masalah algorithmically. 14 00:00:36,879 --> 00:00:38,420 Tetapi pertama, beberapa pengumuman. 15 00:00:38,420 --> 00:00:42,020 Jadi salah, jika anda ingin menyertai Kakitangan dan rakan-rakan sekelas CS50 di makan tengah hari 16 00:00:42,020 --> 00:00:44,670 Jumaat ini, dan di dalam Cambridge, dan di New Haven, 17 00:00:44,670 --> 00:00:48,060 sila layari kursus ini laman web, di mana URL yang boleh didapati. 18 00:00:48,060 --> 00:00:50,390 Kuliah Rabu ini akan tidak berada di sini di Sanders. 19 00:00:50,390 --> 00:00:53,610 Ia akan berada dalam talian sahaja, jadi menonton di laman web CS50, 20 00:00:53,610 --> 00:00:55,850 sama ada di sini di Cambridge atau New Haven juga. 21 00:00:55,850 --> 00:00:58,110 >> Dan kemudian masalah menetapkan dua sudah di tangan anda. 22 00:00:58,110 --> 00:01:03,067 Jika anda belum menyelam dalam lagi, izinkan saya untuk menawarkan cadangan kuat worded 23 00:01:03,067 --> 00:01:05,150 itu, terutamanya sekarang, kerana masalah ini menetapkan terlebih dahulu, 24 00:01:05,150 --> 00:01:08,669 anda benar-benar ingin memulakan sekarang, jika tidak cuba-cuba sedikit di hujung minggu atau sebelum 25 00:01:08,669 --> 00:01:10,710 apabila mereka mula-mula keluar pada Jumaat, kerana anda akan 26 00:01:10,710 --> 00:01:14,380 mendapati bahawa mereka tidak semestinya semakin panjang atau lebih mencabar setiap 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Saya rasa anda akan mendapati bahawa, dalam Secara umum, mereka cenderung untuk mengambil lebih kurang 29 00:01:17,575 --> 00:01:18,892 sekitar jumlah sama. 30 00:01:18,892 --> 00:01:20,850 Tetapi ia sudah tentu bergantung ke atas pelajar, dan ia 31 00:01:20,850 --> 00:01:22,880 bergantung kepada pemikiran yang anda mendekatinya. 32 00:01:22,880 --> 00:01:24,910 Tetapi selalunya, anda akan untuk menjalankan menentang beberapa dinding, 33 00:01:24,910 --> 00:01:26,350 dan anda akan melanda beberapa bug, dan anda hanya 34 00:01:26,350 --> 00:01:27,950 tidak akan dapat mendapat lebih pada satu ketika. 35 00:01:27,950 --> 00:01:31,380 Dan ia sangat berharga yang dapat untuk melangkah jauh, kembali pada hari berikutnya, 36 00:01:31,380 --> 00:01:35,286 pergi ke waktu pejabat, paparkan dalam CS50 Bincangkan atau seumpamanya, untuk benar-benar mendapatkan dinyahsekat. 37 00:01:35,286 --> 00:01:36,160 Jadi menyimpan bahawa dalam fikiran. 38 00:01:36,160 --> 00:01:40,830 Bermula awal yang mungkin adalah perkara yang terbaik anda boleh lakukan. 39 00:01:40,830 --> 00:01:44,160 Jadi di sini adalah di mana kita bermula kelas, lebih dalam seminggu sifar. 40 00:01:44,160 --> 00:01:47,441 Dan kita boleh mendapatkan sukarelawan di sini untuk membantu saya mencari mics? 41 00:01:47,441 --> 00:01:47,940 OKAY. 42 00:01:47,940 --> 00:01:48,900 Berdiri sudah. 43 00:01:48,900 --> 00:01:50,080 Naiklah. 44 00:01:50,080 --> 00:01:53,707 Rasa itu bagaimana ia akan bekerja. 45 00:01:53,707 --> 00:01:54,415 Siapa nama anda? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 DAVID J. MALAN: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Naiklah. 49 00:01:57,910 --> 00:01:58,619 Gembira Mengenali Anda. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Selamat berkenalan. 51 00:01:59,910 --> 00:02:02,772 DAVID J. MALAN: Dan anda berada di sini dengan kami dalam minggu sifar, sudah tentu. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: saya. 53 00:02:03,028 --> 00:02:03,160 Saya telah. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. MALAN: Jadi boleh anda pergi hadapan dan mencari untuk kita Mike Smith, 55 00:02:05,868 --> 00:02:08,639 secepat yang anda boleh? 56 00:02:08,639 --> 00:02:10,639 Secepat yang anda boleh. 57 00:02:10,639 --> 00:02:13,756 Secara harfiah mengoyak masalah pada separuh yang anda perlukan untuk. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. MALAN: Secara lisan mengoyak masalah pada separuh. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Oh. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Sangat bagus. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. MALAN: OK. 65 00:02:23,700 --> 00:02:24,200 Yang baik. 66 00:02:24,200 --> 00:02:24,701 Terima kasih. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Sangat baik. 68 00:02:25,700 --> 00:02:26,210 OKAY. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. MALAN: Dan sehingga kini, anda telah dikecutkan ke bawah 70 00:02:27,610 --> 00:02:29,320 untuk separuh saiz masalah. 71 00:02:29,320 --> 00:02:31,267 Kini, kami turun ke suku. 72 00:02:31,267 --> 00:02:33,475 Adakah anda memberi perhatian kepada pihak mana kita menjaga? 73 00:02:33,475 --> 00:02:34,405 >> [LAUGHING] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Ya, saya think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. MALAN: Apa bahagian kita dalam? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA Mufflers, demikian. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. MALAN: OK. 78 00:02:39,941 --> 00:02:42,810 Tetapi Mike Smith akan menjadi selepas Mufflers. 79 00:02:42,810 --> 00:02:44,130 So-- 80 00:02:44,130 --> 00:02:48,180 >> [LAUGHING] 81 00:02:48,180 --> 00:02:48,742 >> Baiklah. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Di mana yang kita cari? 83 00:02:50,200 --> 00:02:52,049 DAVID J. MALAN: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN ESTRADA: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 DAVID J. MALAN: Sekarang, kita berada dalam pembedahan. 86 00:02:54,760 --> 00:02:57,840 Kini, pakar-pakar perubatan. 87 00:02:57,840 --> 00:02:58,340 Sekarang-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- mari kita pergi dengan nyata. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. MALAN: Real. 91 00:03:00,970 --> 00:03:01,470 OKAY. 92 00:03:01,470 --> 00:03:03,700 Jika anda memerlukan Real. 93 00:03:03,700 --> 00:03:05,250 Kini, jalan mana Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Dengan cara ini. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. MALAN: Arah mana? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Tunggu. 97 00:03:08,240 --> 00:03:08,790 Hak M is--? 98 00:03:08,790 --> 00:03:09,110 Kami bermula with-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. MALAN: Ya. 100 00:03:10,090 --> 00:03:10,650 Mereka ditinggalkan. 101 00:03:10,650 --> 00:03:11,430 Kanan anda. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Ya. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. MALAN: Jadi Mike di sini. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Apa? 105 00:03:13,990 --> 00:03:14,665 >> [LAUGHING] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Contoh buruk, guys. 108 00:03:18,330 --> 00:03:18,830 Maaf. 109 00:03:18,830 --> 00:03:21,610 DAVID J. MALAN: ini akan mengajar anda untuk melompat keluar dari kerusi anda. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Oh. 111 00:03:22,318 --> 00:03:22,890 Oh. 112 00:03:22,890 --> 00:03:23,390 Saya mendapat anda. 113 00:03:23,390 --> 00:03:24,670 Saya mendapat anda. 114 00:03:24,670 --> 00:03:25,170 Oh. 115 00:03:25,170 --> 00:03:25,669 Oh. 116 00:03:25,669 --> 00:03:26,812 Ini is-- OK, saya mendapat anda. 117 00:03:26,812 --> 00:03:27,520 Smith di sini? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. MALAN: Smith, terima kasih. 119 00:03:28,894 --> 00:03:30,535 Jadi saya akan terus mencari sehingga Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, ya. 121 00:03:30,790 --> 00:03:31,340 Tidak, tidak, tidak. 122 00:03:31,340 --> 00:03:31,600 Oh tidak. 123 00:03:31,600 --> 00:03:31,940 Ini adalah saya. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. MALAN: Oh, anda mendapat Smith. 125 00:03:32,580 --> 00:03:33,415 OKAY. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Ya, saya mendapat Smith di sini. 127 00:03:34,040 --> 00:03:34,700 Maaf, guys. 128 00:03:34,700 --> 00:03:35,860 Saya fikir kita Michael-- cari Michael. 129 00:03:35,860 --> 00:03:36,550 Maaf. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. MALAN: Tidak mengapa. 131 00:03:37,550 --> 00:03:39,950 Baiklah, sekarang kita ke dalam Paccini dan Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini dan anak. 133 00:03:41,242 --> 00:03:43,158 DAVID J. MALAN: Hanya anda dan saya adalah di dalam perkara ini. 134 00:03:43,158 --> 00:03:44,050 OKAY. 135 00:03:44,050 --> 00:03:45,130 Cari kami Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Smith. 137 00:03:45,830 --> 00:03:46,310 >> ALAN ESTRADA: Smith. 138 00:03:46,310 --> 00:03:46,750 >> DAVID J. MALAN: Smith. 139 00:03:46,750 --> 00:03:47,728 Kami berada dalam R untuk sampah. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Sampah. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Ini akan mengambil sedikit masa. 143 00:03:52,480 --> 00:03:54,340 >> [LAUGHING] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. MALAN: Shoes. 146 00:03:56,720 --> 00:03:58,080 Kami berada dalam kasut. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Sekarang kita gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. MALAN: Nice. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: yang- 150 00:04:01,980 --> 00:04:03,620 [LAUGHING] 151 00:04:03,620 --> 00:04:05,440 Oh, ini adalah besar. 152 00:04:05,440 --> 00:04:06,910 [LAUGHING] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. MALAN: Tidak mengapa. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, ini adalah baik. 156 00:04:11,365 --> 00:04:14,425 Saya tidak fikir saya akan mempunyai teman PSAT selepas ini. 157 00:04:14,425 --> 00:04:15,300 DAVID J. MALAN: Baik. 158 00:04:15,300 --> 00:04:16,078 Sukan. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sukan. 160 00:04:17,036 --> 00:04:18,668 Um, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 DAVID J. MALAN: OK. 162 00:04:19,459 --> 00:04:21,600 Jadi mari kita air mata ini pada separuh. 163 00:04:21,600 --> 00:04:22,270 Tidak mengapa. 164 00:04:22,270 --> 00:04:25,606 Ini berakhir dengan baik juga, kerana Mike Smith tidak akan berada di halaman kuning. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. MALAN: Tidak, ia adalah OK. 167 00:04:27,140 --> 00:04:28,930 Tetapi mari kita berpura-pura seperti dia di laman ini. 168 00:04:28,930 --> 00:04:33,260 Oleh sebab itu, anda telah dikecutkan masalah ke bawah untuk satu halaman, dan kami mendapati Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Bersorak] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Baiklah Terima kasih. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 OKAY. 174 00:04:41,200 --> 00:04:43,646 Itu adalah luar biasa. 175 00:04:43,646 --> 00:04:45,954 Tetapi ia masih lebih cepat daripada carian linear, 176 00:04:45,954 --> 00:04:47,870 di mana kita bermula pada permulaan buku ini, 177 00:04:47,870 --> 00:04:51,210 dan kita bergerak perjalanan dari kiri ke kanan, akhirnya mencari Mike Smith. 178 00:04:51,210 --> 00:04:53,540 Justeru, jika buku telefon mempunyai mungkin 1000 muka surat, 179 00:04:53,540 --> 00:04:56,300 mungkin ia akan mengambil kami 10 atau lebih air mata halaman. 180 00:04:56,300 --> 00:04:59,380 >> Tetapi anda mungkin telah memanfaatkan menyentuh andaian 181 00:04:59,380 --> 00:05:03,602 ketika semua itu, yang mengatakan bahawa buku telefon terlebih dahulu adalah apa? 182 00:05:03,602 --> 00:05:04,310 PENONTON: Susun. 183 00:05:04,310 --> 00:05:05,000 DAVID J. MALAN: Ia disusun. 184 00:05:05,000 --> 00:05:05,160 Betul? 185 00:05:05,160 --> 00:05:07,909 Ia disusun mengikut abjad, supaya bahawa semua nama-nama dan nombor 186 00:05:07,909 --> 00:05:11,230 yang disusun dari A ke Z, dan mengikut abjad di antara. 187 00:05:11,230 --> 00:05:13,100 Tetapi hari ini, kita meminta soalan, baik, 188 00:05:13,100 --> 00:05:16,170 bagaimanakah Verizon atau telefon syarikat mendapatkan ke dalam negeri itu? 189 00:05:16,170 --> 00:05:19,560 >> Kerana ia adalah satu perkara untuk memanfaatkan andaian itu, dan oleh itu, 190 00:05:19,560 --> 00:05:22,570 menyelesaikan masalah dengan algoritma dengan lebih cekap. 191 00:05:22,570 --> 00:05:24,900 Tetapi kita tidak pernah benar-benar ditanya dalam minggu sifar, baik, 192 00:05:24,900 --> 00:05:27,790 berapa banyak ia lakukan kos Verizon atau orang lain 193 00:05:27,790 --> 00:05:29,620 untuk mendapatkan bahawa buku telefon untuk disusun? 194 00:05:29,620 --> 00:05:29,780 >> Betul? 195 00:05:29,780 --> 00:05:31,529 Ia tidak kira jika melihat ke atas Mike Smith 196 00:05:31,529 --> 00:05:35,190 adalah super cepat, jika ia mengambil masa anda tahun untuk menyusun halaman mulanya. 197 00:05:35,190 --> 00:05:35,690 Betul? 198 00:05:35,690 --> 00:05:38,620 Anda mungkin juga hanya menapis melalui buku telefon rawak, 199 00:05:38,620 --> 00:05:40,690 jika ia akan menjadi super mahal untuk mengatasinya. 200 00:05:40,690 --> 00:05:42,350 Jadi, jika kita boleh mempunyai sukarelawan lain. 201 00:05:42,350 --> 00:05:46,350 Mari kita melihat di sini di bagaimana kita might-- datang pada up-- bagaimana 202 00:05:46,350 --> 00:05:48,100 kita mungkin pergi tentang menyusun ini. 203 00:05:48,100 --> 00:05:51,990 >> Dan jika Jordan boleh sebenarnya sertai kami di sini di atas pentas. 204 00:05:51,990 --> 00:05:55,100 Naiklah hanya untuk seketika. 205 00:05:55,100 --> 00:05:56,359 Siapa nama anda? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. MALAN: Caroline, datang ke atas. 208 00:05:58,691 --> 00:06:02,070 Dan anda akan menyertai oleh saya dan Jordan di sini. 209 00:06:02,070 --> 00:06:03,800 Caroline, terima kasih. 210 00:06:03,800 --> 00:06:04,300 Baiklah. 211 00:06:04,300 --> 00:06:08,330 Jadi apa yang kita ada di sini untuk Caroline adalah 26 buku biru 212 00:06:08,330 --> 00:06:10,747 bahawa FAS menggunakan untuk mentadbir peperiksaan akhir tertentu. 213 00:06:10,747 --> 00:06:13,330 Ini semakin sukar untuk mencari, tetapi apa yang kita lakukan terlebih dahulu 214 00:06:13,330 --> 00:06:15,800 adalah bahawa kita telah meletakkan nama seseorang di hadapan masing-masing, 215 00:06:15,800 --> 00:06:18,133 tetapi kami telah disimpan mudah oleh kemudian meletakkan nama-nama penuh. 216 00:06:18,133 --> 00:06:22,720 Oleh itu, kita akan meletakkan orang dengan nama yang L, D, J, B, sepanjang jalan A hingga Z, 217 00:06:22,720 --> 00:06:24,090 tetapi mereka berada dalam susunan rawak. 218 00:06:24,090 --> 00:06:26,890 Dan jadi jika anda akan, bercakap anda jalan melalui masalah seperti yang anda 219 00:06:26,890 --> 00:06:31,620 melakukannya, anda boleh pergi ke hadapan dan menyusun ini untuk kita, dari A ke Z. 220 00:06:31,620 --> 00:06:34,070 >> PENONTON: OK, jadi L adalah seperti, tengah-tengah. 221 00:06:34,070 --> 00:06:35,050 C adalah permulaan. 222 00:06:35,050 --> 00:06:42,410 B. J sebelum L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. MALAN: Kekal yang berfikir untuk satu saat. 224 00:06:45,140 --> 00:06:48,910 Kerana jika tidak, ini hanya menarik kepada anda, saya, dan Jordan. 225 00:06:48,910 --> 00:06:49,724 Di sana kami pergi. 226 00:06:49,724 --> 00:06:50,640 PENONTON: [didengar]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. MALAN: OK. 229 00:06:58,090 --> 00:06:59,310 Apa yang anda lakukan? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M datang selepas O. 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. MALAN: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. MALAN: O, Baik. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> DAVID J. MALAN: E, F. Yeah. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V 237 00:07:07,620 --> 00:07:10,689 >> DAVID J. MALAN: V, T, U, V. Oleh itu, ia kelihatan seperti anda making-- terus. 238 00:07:10,689 --> 00:07:12,730 Ia kelihatan seperti anda membuat longgokan besar di sini, 239 00:07:12,730 --> 00:07:13,910 dan jenis longgokan besar di sana. 240 00:07:13,910 --> 00:07:16,230 Jadi separuh pertama abjad, Separuh kedua abjad. 241 00:07:16,230 --> 00:07:16,460 OKAY. 242 00:07:16,460 --> 00:07:16,960 Yang baik. 243 00:07:16,960 --> 00:07:19,680 Jenis membelah masalah ini dalam dua. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Yeah. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. MALAN: OK. 247 00:07:22,980 --> 00:07:25,070 K. Jadi anda jenis memilih mereka satu demi satu, 248 00:07:25,070 --> 00:07:27,620 meletakkan ia sama ada kiri atau kanan, atau Z yang berlaku di lantai. 249 00:07:27,620 --> 00:07:28,012 OKAY. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z yang berlaku di lantai. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. MALAN: OK. 252 00:07:29,360 --> 00:07:30,920 Y akan di atas lantai. 253 00:07:30,920 --> 00:07:31,735 Sekarang kita boleh meletakkan X. 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 DAVID J. MALAN: G akan ke kiri. 256 00:07:33,700 --> 00:07:36,017 S akan betul. 257 00:07:36,017 --> 00:07:37,642 Baiklah, A akan sepanjang jalan kiri. 258 00:07:37,642 --> 00:07:38,790 >> CAROLINE: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> DAVID J. MALAN: Sekarang, baik. 260 00:07:39,873 --> 00:07:43,260 Kami telah mendapat A, B, C. W yang sedang berlaku di bawah sana. 261 00:07:43,260 --> 00:07:45,566 Baiklah, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, J. 263 00:07:46,611 --> 00:07:47,860 DAVID J. MALAN: H, I, J. baik. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: Di bahagian tengah, saya gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. MALAN: OK. 266 00:07:50,000 --> 00:07:52,375 Oleh sebab itu, kita akan jenis daripada bergabung ini pelbagai buasir. 267 00:07:52,375 --> 00:08:00,730 Jadi A hingga C, maka saya lihat A, dan E, dan F dan G, dan H dan I. Nice. 268 00:08:00,730 --> 00:08:05,540 J, K. Dan kemudian, cerucuk ini adalah terbalik, tetapi itu OK. 269 00:08:05,540 --> 00:08:06,040 Pasti. 270 00:08:06,040 --> 00:08:07,240 Kita boleh memotong beberapa sudut. 271 00:08:07,240 --> 00:08:07,950 OKAY. 272 00:08:07,950 --> 00:08:10,530 Dan kemudian kita perlu W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Ya. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. MALAN: Cemerlang. 275 00:08:11,880 --> 00:08:14,122 Jadi terima kasih kepada Caroline untuk menyusun ini. 276 00:08:14,122 --> 00:08:15,030 >> [Bersorak] 277 00:08:15,030 --> 00:08:17,287 >> Terima kasih. 278 00:08:17,287 --> 00:08:18,120 Terima kasih banyak. 279 00:08:18,120 --> 00:08:22,910 Jadi sekarang mari kita mempertimbangkan untuk seketika bagaimana Caroline pergi tentang berbuat demikian, 280 00:08:22,910 --> 00:08:26,040 dan apa sebenarnya kita dapat supaya- bagaimana kita 281 00:08:26,040 --> 00:08:28,409 dapat menyelesaikan itu masalah apabila kami hanya 282 00:08:28,409 --> 00:08:29,950 diberikan sejumlah besar input rawak. 283 00:08:29,950 --> 00:08:31,610 >> Nah, ia kelihatan seperti ada adalah sedikit sistem di sana? 284 00:08:31,610 --> 00:08:32,110 Betul. 285 00:08:32,110 --> 00:08:34,495 Jadi huruf awal dalam abjad, dia 286 00:08:34,495 --> 00:08:37,120 adalah meletakkan ke kiri, dan surat kemudian dalam abjad, 287 00:08:37,120 --> 00:08:38,270 dia meletakkan ke kanan. 288 00:08:38,270 --> 00:08:40,500 Dan sebaik sahaja dia mendapati beberapa surat proksimal, orang-orang yang 289 00:08:40,500 --> 00:08:43,124 yang pergi betul-betul bersebelahan antara satu sama lain, dia akan meletakkan mereka dalam perintah. 290 00:08:43,124 --> 00:08:46,750 Dan supaya kita jenis mempunyai ini kecil timbunan input disusun berlaku. 291 00:08:46,750 --> 00:08:50,540 >> Dan supaya cukup seperti apa kebanyakan kita manusia akan lakukan. 292 00:08:50,540 --> 00:08:53,530 Kami akan semacam menapis melaluinya, dan kita akan jenis mempunyai satu mekanisme. 293 00:08:53,530 --> 00:08:56,930 Tetapi ia mungkin sukar untuk menulis menurunkan ke atas formula semata-mata. 294 00:08:56,930 --> 00:08:59,010 Ia merasakan lebih sedikit organik daripada itu. 295 00:08:59,010 --> 00:09:02,560 Jadi mari kita lihat jika kita boleh sekarang terikat masalah ini dengan sedikit input. 296 00:09:02,560 --> 00:09:05,170 >> Daripada 26, mari kita melakukan sesuatu yang jauh lebih kecil 297 00:09:05,170 --> 00:09:09,890 dengan hanya berkata, tujuh, di belakang pintu-pintu ini, jadi untuk bercakap. 298 00:09:09,890 --> 00:09:11,300 Adakah terdapat hanya tujuh nombor? 299 00:09:11,300 --> 00:09:15,240 Dan jika matlamat sekarang di tangan adalah untuk mencari nilai, 300 00:09:15,240 --> 00:09:17,850 mari kita lihat bagaimana cekap kita boleh pergi tentang melakukan ini. 301 00:09:17,850 --> 00:09:22,460 Dan mari kita lihat jika kita boleh sekarang mula memohon beberapa nombor, 302 00:09:22,460 --> 00:09:26,310 atau beberapa formula yang boleh digunakan untuk menggambarkan kecekapan buku telefon kami 303 00:09:26,310 --> 00:09:31,060 algoritma, algoritma buku peperiksaan kami, dan lebih umum, mencari maklumat. 304 00:09:31,060 --> 00:09:34,770 >> Jadi untuk ini, saya pergi ke hadapan, dan pada skrin sentuh di sini, 305 00:09:34,770 --> 00:09:41,100 meletakkan pelayar web yang mempunyai betul-betul tujuh pintu. 306 00:09:41,100 --> 00:09:46,670 Dan jika kita boleh mendapatkan satu lain secara sukarela untuk datang ke sini, 307 00:09:46,670 --> 00:09:48,480 Saya telah meletakkan ini pintu sama di sini. 308 00:09:48,480 --> 00:09:49,170 Sukarelawan Pantas. 309 00:09:49,170 --> 00:09:51,130 >> Ini demo one-- akan untuk yang lebih cepat dan lebih cepat sekarang. 310 00:09:51,130 --> 00:09:51,600 Ayuh ke bawah. 311 00:09:51,600 --> 00:09:52,308 Siapa nama anda? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> DAVID J. MALAN: Trevor? 314 00:09:53,998 --> 00:09:55,770 Baiklah, Trevor, datang ke atas ke bawah. 315 00:09:55,770 --> 00:09:59,212 Jadi Trevor secara sukarela di sini untuk melakukan masalah yang sama, tetapi satu yang 316 00:09:59,212 --> 00:10:02,170 sempit dalam skop, dan perkara yang berlaku untuk membolehkan kita untuk mencuba untuk merasmikan sekarang 317 00:10:02,170 --> 00:10:03,970 proses untuk menyusun nombor-nombor ini. 318 00:10:03,970 --> 00:10:05,500 >> Jadi Trevor, baik untuk bertemu dengan kamu. 319 00:10:05,500 --> 00:10:08,720 Jadi di sini adalah pelbagai, jadi untuk berkata-kata, senarai tujuh pintu. 320 00:10:08,720 --> 00:10:10,327 Teruskan dan mencari kami jumlah 50. 321 00:10:10,327 --> 00:10:12,410 Dan kemudian selepas fakta, memberitahu kami bagaimana anda menjumpainya. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Sekiranya adalah- hak semua. 324 00:10:20,040 --> 00:10:21,945 Ya, ini adalah salah di sini? 325 00:10:21,945 --> 00:10:24,680 Uh-oh. 326 00:10:24,680 --> 00:10:25,560 OKAY. 327 00:10:25,560 --> 00:10:26,680 Anda klik salah satu. 328 00:10:26,680 --> 00:10:28,690 Yang baik. 329 00:10:28,690 --> 00:10:29,780 >> Dan baik. 330 00:10:29,780 --> 00:10:30,970 Sekarang anda klik salah satu. 331 00:10:30,970 --> 00:10:34,060 Dan biarlah saya memberikan anda mikrofon, supaya anda mempunyai dalam hanya seketika. 332 00:10:34,060 --> 00:10:37,000 Teruskan dan klik sebelah yang anda berniat. 333 00:10:37,000 --> 00:10:39,812 Ya baik. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Bolehkah saya Nyahklik pintu? 335 00:10:41,020 --> 00:10:42,620 DAVID J. MALAN: Tidak, anda tidak boleh Nyahklik. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Satu ini. 338 00:10:43,974 --> 00:10:45,640 DAVID J. MALAN: Di manakah anda mahu pergi? 339 00:10:45,640 --> 00:10:46,410 Yang mana satu? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Yang itu. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. MALAN: No. 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Satu ini. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. MALAN: Ya. 345 00:10:49,020 --> 00:10:49,700 Itu adalah baik. 346 00:10:49,700 --> 00:10:50,380 Baiklah. 347 00:10:50,380 --> 00:10:53,900 Oleh itu, apa algoritma atau prosedur untuk melakukan ini, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Saya hanya pergi melalui pintu sehingga saya mendapati 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. MALAN: OK. 350 00:10:56,940 --> 00:10:58,150 Algoritma yang sangat baik. 351 00:10:58,150 --> 00:10:59,540 Jadi itulah denda. 352 00:10:59,540 --> 00:11:03,120 Kerana sebenarnya, jika saya mendedahkan apa yang di belakang kedua-dua pintu yang lain, apa yang 353 00:11:03,120 --> 00:11:06,954 kita akan dapati di sini adalah bahawa kita hanya mempunyai input rawak. 354 00:11:06,954 --> 00:11:08,870 Jadi yang sebenarnya sebagai baik seperti yang anda boleh mendapatkan. 355 00:11:08,870 --> 00:11:12,509 Dan sebenarnya, anda mendapat lebih baik daripada mendalam mencari seluruh array, 356 00:11:12,509 --> 00:11:15,300 kerana ia akan menjadi benar-benar malang jika anda telah mencecah bilangan yang 357 00:11:15,300 --> 00:11:16,604 50 di pintu yang terakhir. 358 00:11:16,604 --> 00:11:18,520 Tetapi bagaimana jika kita bukannya memberikan anda satu andaian. 359 00:11:18,520 --> 00:11:20,630 Kira saya semacam semua pintu-pintu ini di sekeliling, 360 00:11:20,630 --> 00:11:23,500 supaya anda mempunyai nombor disusun masa ini, 361 00:11:23,500 --> 00:11:29,730 tetapi kali ini ia sebenarnya yang different-- masa ini, 362 00:11:29,730 --> 00:11:32,640 ia sebenarnya disusun untuk anda. 363 00:11:32,640 --> 00:11:35,380 Dan kini matlamat di tangan adalah untuk memukul bilangan 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. MALAN: Apa algoritma anda akan menjadi? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Nah, jika ia disusun, ia sama ada akan 367 00:11:39,628 --> 00:11:42,710 untuk adalah- jika terbesar untuk terbesar, turun, ia akan menjadi yang pertama, 368 00:11:42,710 --> 00:11:44,751 atau jika ia adalah sebaliknya, ia akan menjadi yang terakhir. 369 00:11:44,751 --> 00:11:48,897 Jadi saya hanya akan ketuk pintu ini, dan kemudian hanya ketuk pintu lepas. 370 00:11:48,897 --> 00:11:49,980 DAVID J. MALAN: Cemerlang. 371 00:11:49,980 --> 00:11:50,270 Baiklah. 372 00:11:50,270 --> 00:11:51,150 Oleh itu, kita mendapati jumlah 50. 373 00:11:51,150 --> 00:11:52,970 Jadi sebaik sahaja anda tahu mereka telah disusun, kita 374 00:11:52,970 --> 00:11:55,040 dapat memanfaatkan andaian ini. 375 00:11:55,040 --> 00:11:57,040 Jadi mereka terlalu banyak seperti contoh buku telefon. 376 00:11:57,040 --> 00:11:59,540 Sebaik sahaja anda mempunyai, walaupun dengan masalah kecil seperti ini, 377 00:11:59,540 --> 00:12:02,380 input anda pra-disusun, kita boleh sebenarnya mencari nilai boleh dikatakan 378 00:12:02,380 --> 00:12:03,130 dengan lebih cekap. 379 00:12:03,130 --> 00:12:05,800 >> Dan saya tidak memberitahu anda jika ia disusun kecil kepada yang besar, atau besar ke kecil, 380 00:12:05,800 --> 00:12:08,080 dan jadi ia adalah sangat wajar bermula pada satu hujung atau yang lain 381 00:12:08,080 --> 00:12:09,750 untuk benar-benar mendapati bahawa nilai sasaran. 382 00:12:09,750 --> 00:12:11,400 Jadi terima kasih kepada Trevor juga. 383 00:12:11,400 --> 00:12:13,260 Dan saya akan propose-- baik dilakukan. 384 00:12:13,260 --> 00:12:16,960 Kami mempunyai music sedikit, sebenarnya, yang adalah antara detik-detik kegemaran kami di CS50, 385 00:12:16,960 --> 00:12:19,700 di mana kadang-kadang demo ini tidak cukup pergi mengikut perancangan. 386 00:12:19,700 --> 00:12:22,050 Dan sesungguhnya sekarang, saya ditarik ke atas antara muka salah 387 00:12:22,050 --> 00:12:23,508 yang boleh digunakan untuk menggunakan skrin sentuh. 388 00:12:23,508 --> 00:12:24,660 Supaya adalah kesilapan saya di sana. 389 00:12:24,660 --> 00:12:26,600 >> Jadi ini akan menjadikan music tahun depan sebagai 390 00:12:26,600 --> 00:12:28,570 mengapa saya klik pada skrin saya sendiri. 391 00:12:28,570 --> 00:12:31,390 Tetapi mari kita lihat yang cepat apa yang berlaku pada tahun lepas 392 00:12:31,390 --> 00:12:34,770 dengan Jay, yang datang, banyak seperti Trevor sini, secara sukarela, 393 00:12:34,770 --> 00:12:39,380 dan dalam klip pendek ini, anda akan melihat bagaimana ini demo sama tidak cukup 394 00:12:39,380 --> 00:12:41,074 mendedahkan pelajaran yang sama dipelajari. 395 00:12:41,074 --> 00:12:41,740 [VIDEO MAIN SEMULA] 396 00:12:41,740 --> 00:12:45,360 -Semua Saya mahu anda lakukan sekarang ialah untuk mencari untuk saya, dan bagi kami, 397 00:12:45,360 --> 00:12:51,674 benar-benar, jumlah 50 satu langkah pada satu masa. 398 00:12:51,674 --> 00:12:52,450 >> -The Nombor 50? 399 00:12:52,450 --> 00:12:53,190 >> -The Nombor 50. 400 00:12:53,190 --> 00:12:55,356 Dan anda boleh mendedahkan apa yang di belakang setiap pintu-pintu ini 401 00:12:55,356 --> 00:12:58,540 hanya dengan menyentuhnya dengan jari. 402 00:12:58,540 --> 00:13:00,910 Tak guna. 403 00:13:00,910 --> 00:13:02,870 >> [LAUGHING] 404 00:13:02,870 --> 00:13:03,806 >> [AKHIR MAIN SEMULA] 405 00:13:03,806 --> 00:13:05,430 DAVID J. MALAN: Jadi yang pergi dengan baik. 406 00:13:05,430 --> 00:13:06,796 Mereka itulah pintu terisih. 407 00:13:06,796 --> 00:13:08,670 And Jay, sudah tentu, mendapati ia terlalu cepat. 408 00:13:08,670 --> 00:13:12,910 Trevor melakukan kerja yang lebih baik dari segi masa yang diajar, 409 00:13:12,910 --> 00:13:15,850 boleh dikatakan, tahun ini di mengambil masa yang lama untuk merasa. 410 00:13:15,850 --> 00:13:17,950 Sudah tentu, kita memberi Jay peluang kedua, 411 00:13:17,950 --> 00:13:20,320 mana kita disusun pintu, seperti yang kita lakukan untuk Trevor, 412 00:13:20,320 --> 00:13:22,300 dan Trevor lakukan super baik kali ini. 413 00:13:22,300 --> 00:13:26,124 Tetapi Jay melakukannya separuh cepat. 414 00:13:26,124 --> 00:13:26,790 [VIDEO MAIN SEMULA] 415 00:13:26,790 --> 00:13:29,650 Matlamat -The sekarang adalah untuk juga mencari kami nombor 50, 416 00:13:29,650 --> 00:13:33,030 tetapi melakukannya algorithmically, dan memberitahu kami bagaimana anda akan mengenainya. 417 00:13:33,030 --> 00:13:33,660 >> -OKAY. 418 00:13:33,660 --> 00:13:35,604 >> -Dan Jika anda merasa, anda menyimpan filem. 419 00:13:35,604 --> 00:13:37,228 Jika anda tidak merasa, anda memberikan kembali. 420 00:13:37,228 --> 00:13:38,044 >> -man. 421 00:13:38,044 --> 00:13:38,860 >> -Oh! 422 00:13:38,860 --> 00:13:40,800 >> - [Didengar] OK. 423 00:13:40,800 --> 00:13:46,236 Jadi, saya akan menyemak hujung pertama untuk menentukan jika there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Tepuk tangan] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [AKHIR MAIN SEMULA] 427 00:13:55,729 --> 00:13:56,520 DAVID J. MALAN: OK. 428 00:13:56,520 --> 00:13:59,760 Jadi menyusun pintu jelas membawa kepada kecekapan yang lebih tinggi. 429 00:13:59,760 --> 00:14:01,680 Dan sebagainya, dua kali lebih cepat apa yang saya maksudkan di sana. 430 00:14:01,680 --> 00:14:03,270 Dan sebagainya Jay bernasib baik kedua-dua kali. 431 00:14:03,270 --> 00:14:06,685 Dan dia juga bernasib baik kerana lepas tahun, saya mengarahkan beberapa cakera Blu-ray 432 00:14:06,685 --> 00:14:07,560 untuk benar-benar memberi. 433 00:14:07,560 --> 00:14:09,768 Saya minta maaf tahun ini, kami tidak mempunyai yang sama, Trevor. 434 00:14:09,768 --> 00:14:11,540 Tetapi lebih baik lagi adalah beberapa tahun lalu. 435 00:14:11,540 --> 00:14:14,820 Dan sebahagian daripada anda mungkin tahu ini rakan-rakan, Sean, yang ketika ia ada di CS50, 436 00:14:14,820 --> 00:14:17,780 telah dicabar dengan tepat Masalah yang sama, walaupun dalam SD, 437 00:14:17,780 --> 00:14:19,360 kerana anda tidak lama lagi akan melihat, pada zaman dahulu. 438 00:14:19,360 --> 00:14:22,622 Dan anda akan mendapati bahawa bukan sahaja melakukan ia mengambil masa lebih lama daripada Jay, 439 00:14:22,622 --> 00:14:25,580 lebih lama daripada Trevor, ia sebenarnya peluang ini indah 440 00:14:25,580 --> 00:14:29,820 untuk melibatkan hampir semua orang dalam orang ramai la Harganya kanan, menggalakkan 441 00:14:29,820 --> 00:14:31,889 beliau untuk mencari nombor yang kita cari. 442 00:14:31,889 --> 00:14:32,930 Mari kita. mengambil melihat cepat. 443 00:14:32,930 --> 00:14:33,320 >> [VIDEO MAIN SEMULA] 444 00:14:33,320 --> 00:14:33,820 >> -OKAY. 445 00:14:33,820 --> 00:14:36,680 Jadi tugas anda di sini, Sean, adalah seperti berikut. 446 00:14:36,680 --> 00:14:40,860 Saya telah tersembunyi di sebalik ini pintu nombor tujuh. 447 00:14:40,860 --> 00:14:45,120 Tetapi terletak jauh di beberapa pintu-pintu ini dan juga adalah nombor negatif yang lain. 448 00:14:45,120 --> 00:14:47,500 Dan matlamat anda adalah untuk berfikir ini baris atas nombor 449 00:14:47,500 --> 00:14:50,390 kerana hanya pelbagai, atau hanya urutan keping kertas 450 00:14:50,390 --> 00:14:51,510 dengan nombor di belakang mereka. 451 00:14:51,510 --> 00:14:55,540 Dan matlamat anda adalah, hanya menggunakan bahagian atas lokasi di sini, mendapati aku sebagai nombor tujuh. 452 00:14:55,540 --> 00:14:58,570 Dan kami kemudian pergi untuk mengkritik bagaimana anda pergi tentang melakukannya. 453 00:14:58,570 --> 00:14:59,070 -Semua Betul. 454 00:14:59,070 --> 00:15:00,850 Kita-Cari nombor tujuh, sila. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 No. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Lima, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [LAUGHING] 461 00:15:24,770 --> 00:15:25,910 >> Ia bukan satu soalan helah. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 One. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [LAUGHING] 466 00:15:34,695 --> 00:15:37,861 Pada ketika ini, skor anda tidak begitu yang baik, jadi anda mungkin juga menyimpan berterusan. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Tiga. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [LAUGHING] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Teruskan. 473 00:15:47,774 --> 00:15:50,690 Terus terang, saya tidak boleh membantu tetapi tertanya-tanya apa yang anda berfikir tentang, so-- 474 00:15:50,690 --> 00:15:51,959 >> [LAUGHING] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Hanya baris atas, jadi anda mempunyai tiga kiri. 477 00:15:55,020 --> 00:15:56,200 Jadi mencari saya tujuh. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [LAUGHING] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Tujuh. 484 00:16:26,946 --> 00:16:28,780 >> [Tepuk tangan] 485 00:16:28,780 --> 00:16:29,426 >> Baiklah. 486 00:16:29,426 --> 00:16:30,360 >> [AKHIR MAIN SEMULA] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. MALAN: Jadi kita boleh menonton sepanjang hari. 488 00:16:31,840 --> 00:16:34,090 Dan sudah tentu, beberapa demo tahun ini mungkin 489 00:16:34,090 --> 00:16:36,330 sekarang akan berakhir di depan video tahun ini juga. 490 00:16:36,330 --> 00:16:39,040 Jadi sekarang mari kita sebenarnya menumpukan kepada algoritma 491 00:16:39,040 --> 00:16:42,140 di sini, dan lihat jika kita tidak boleh kini bermula untuk merasmikan 492 00:16:42,140 --> 00:16:46,650 bagaimana kita boleh pergi tentang mendapatkan data kami ke negeri ini bahawa ia disusun, 493 00:16:46,650 --> 00:16:50,054 supaya akhirnya, kita boleh sebenarnya mencari ia lebih cekap. 494 00:16:50,054 --> 00:16:52,470 Dan walaupun kita akan untuk menggunakan set data yang agak kecil, 495 00:16:52,470 --> 00:16:54,511 seperti yang kita lapan nombor ada di atas kapal, 496 00:16:54,511 --> 00:16:58,230 akhirnya idea-idea yang sama boleh memohon 1,000 input, satu juta input, 497 00:16:58,230 --> 00:17:02,100 4000000000 input, kerana algoritma akan menjadi asas yang sama. 498 00:17:02,100 --> 00:17:05,359 >> Dan jadi ini adalah terakhir kami peluang untuk sukarelawan hari ini, 499 00:17:05,359 --> 00:17:09,790 tetapi mungkin salah satu yang paling terlibat, yang mana kita memerlukan lapan sukarelawan 500 00:17:09,790 --> 00:17:12,960 untuk datang dan berjalan kita melalui proses mengasingkan apa yang akan tidak lama lagi 501 00:17:12,960 --> 00:17:15,212 berada di muzik ini berdiri di sini. 502 00:17:15,212 --> 00:17:16,170 Biar saya mulakan semula di sini. 503 00:17:16,170 --> 00:17:19,692 >> Jadi, satu dalam hijau turquoise-- ia? 504 00:17:19,692 --> 00:17:21,130 Adakah anda melakukan? 505 00:17:21,130 --> 00:17:21,630 Dua. 506 00:17:21,630 --> 00:17:23,069 Ayuh ke bawah. 507 00:17:23,069 --> 00:17:23,569 OKAY. 508 00:17:23,569 --> 00:17:24,420 Tiga. 509 00:17:24,420 --> 00:17:25,400 Empat. 510 00:17:25,400 --> 00:17:27,247 Mari me-- OK, lima. 511 00:17:27,247 --> 00:17:28,830 Anda sedang dicalonkan oleh rakan anda. 512 00:17:28,830 --> 00:17:31,340 Enam, tujuh dan lapan. 513 00:17:31,340 --> 00:17:32,130 Naiklah. 514 00:17:32,130 --> 00:17:32,630 Baiklah. 515 00:17:32,630 --> 00:17:33,190 Terima kasih banyak-banyak. 516 00:17:33,190 --> 00:17:33,689 Naiklah. 517 00:17:33,689 --> 00:17:34,790 Naiklah. 518 00:17:34,790 --> 00:17:35,330 >> Baiklah. 519 00:17:35,330 --> 00:17:38,890 Jadi apa yang kita ada sini-- dan ini merupakan antara yang lebih janggal, 520 00:17:38,890 --> 00:17:42,390 kerana ini akan memerlukan anda humor saya untuk hanya sedikit masa. 521 00:17:42,390 --> 00:17:43,442 Anda hendaklah menjadi nombor satu. 522 00:17:43,442 --> 00:17:44,150 Siapa nama anda? 523 00:17:44,150 --> 00:17:44,610 >> ANNAN: Annan. 524 00:17:44,610 --> 00:17:45,526 >> DAVID J. MALAN: Annan. 525 00:17:45,526 --> 00:17:46,092 Daud. 526 00:17:46,092 --> 00:17:46,800 Siapa nama anda? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Yusuf. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. MALAN: Joseph, anda adalah nombor dua. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, nombor tiga. 530 00:17:52,260 --> 00:17:53,722 Stefan, nombor empat. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. MALAN: Cynthia, nombor lima. 533 00:17:57,548 --> 00:17:58,452 [Didengar] 534 00:17:58,452 --> 00:17:59,618 DAVID J. MALAN: [didengar]. 535 00:17:59,618 --> 00:18:00,391 David, nombor enam. 536 00:18:00,391 --> 00:18:00,890 MATT: Mat. 537 00:18:00,890 --> 00:18:02,160 DAVID J. MALAN: nombor Matt tujuh. 538 00:18:02,160 --> 00:18:02,850 Dan? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. MALAN: Waverly, nombor lapan. 541 00:18:04,470 --> 00:18:04,970 Baiklah. 542 00:18:04,970 --> 00:18:06,510 Jika anda could-- whoops. 543 00:18:06,510 --> 00:18:08,820 Jika anda semua, kerana anda Cabaran pertama, terdapat 544 00:18:08,820 --> 00:18:10,820 lapan tempat duduk penonton muzik di sini menghadapi audiens. 545 00:18:10,820 --> 00:18:14,200 Jika anda boleh meletakkan nombor pada muzik ini berdiri dalam apa-apa cara yang 546 00:18:14,200 --> 00:18:16,560 bahawa mereka beratur dengan nombor yang sama di papan tulis. 547 00:18:16,560 --> 00:18:19,560 Oleh itu, kamu kelihatan seperti dengan meletakkan nombor pada muzik ini 548 00:18:19,560 --> 00:18:21,960 berdiri di sini. 549 00:18:21,960 --> 00:18:25,980 Cemerlang setakat ini. 550 00:18:25,980 --> 00:18:26,600 >> Sangat baik. 551 00:18:26,600 --> 00:18:26,890 OKAY. 552 00:18:26,890 --> 00:18:29,556 Oleh sebab itu, kita akan meminta soalan dalam beberapa cara yang berbeza. 553 00:18:29,556 --> 00:18:31,610 Bagaimana kita boleh pergi tentang menyusun orang ini di sini? 554 00:18:31,610 --> 00:18:34,500 Kerana kami mempunyai beberapa pendekatan sebelum ini, di mana kita berada 555 00:18:34,500 --> 00:18:36,360 sejenis membuat dua baldi yang berbeza. 556 00:18:36,360 --> 00:18:38,842 Dan kemudian kita secara amnya piecing perkara bersama-sama. 557 00:18:38,842 --> 00:18:41,050 Sebaik sahaja kami melihat dua nombor milik bersama-sama, 558 00:18:41,050 --> 00:18:41,975 kita meletakkan mereka bersama-sama. 559 00:18:41,975 --> 00:18:43,350 Dua huruf yang tergolong bersama-sama. 560 00:18:43,350 --> 00:18:45,058 >> Tetapi mari kita lihat jika kita tidak boleh merasmikan ini, 561 00:18:45,058 --> 00:18:48,044 supaya kita akhirnya mempunyai beberapa pseudo-kod anda akan, 562 00:18:48,044 --> 00:18:49,710 yang mana anda boleh menyelesaikan masalah ini. 563 00:18:49,710 --> 00:18:51,870 Oleh sebab itu, saya melihat keluar di nombor-nombor di sini. 564 00:18:51,870 --> 00:18:55,030 Dan saya lihat sejumlah besar kesilapan. 565 00:18:55,030 --> 00:18:57,750 Akhirnya, saya ingin satu di kiri dan lapan di sebelah kanan. 566 00:18:57,750 --> 00:19:00,650 >> Dan jadi saya melihat kedua-dua, empat dan dua. 567 00:19:00,650 --> 00:19:02,930 Dan apa masalahnya, jelas? 568 00:19:02,930 --> 00:19:04,261 Yeah. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Dua jelas datang sebelum empat, supaya anda tahu apa? 571 00:19:07,160 --> 00:19:10,210 Terlebih dahulu saya mengambil pendekatan tamak, jika anda akan, banyak masalah seperti 572 00:19:10,210 --> 00:19:13,790 menetapkan one-- jika anda masih ingat dari Standard Edition Masalah Set One, 573 00:19:13,790 --> 00:19:16,820 di mana saya hanya dalam negara menyelesaikan masalah ini bahawa di sini di depan saya 574 00:19:16,820 --> 00:19:17,690 dan melihat di mana ia membawa saya. 575 00:19:17,690 --> 00:19:17,870 >> OKAY. 576 00:19:17,870 --> 00:19:20,161 Jadi dua dan empat, saya pergi hadapan dan hanya menukar kamu berdua. 577 00:19:20,161 --> 00:19:22,400 Jika anda secara fizikal boleh bergerak Peliharalah diri kamu dan kertas anda, 578 00:19:22,400 --> 00:19:25,040 Saya seolah-olah telah mendapat senarai dalam keadaan yang lebih baik. 579 00:19:25,040 --> 00:19:26,330 >> Sekarang, mereka yang baik. 580 00:19:26,330 --> 00:19:28,480 Saya akan bergerak ke atas, empat dan enam, kelihatan baik. 581 00:19:28,480 --> 00:19:29,110 Tidak menjadi masalah. 582 00:19:29,110 --> 00:19:30,440 Enam dan lapan, OK. 583 00:19:30,440 --> 00:19:31,860 Lapan dan satu, satu lagi masalah. 584 00:19:31,860 --> 00:19:34,750 Kerana apa yang benar tentang lapan dan satu? 585 00:19:34,750 --> 00:19:36,990 Seorang pun yang datang sebelum lapan, dan sebagainya apa yang patut kita buat? 586 00:19:36,990 --> 00:19:38,090 Mari kita menukar kedua-dua. 587 00:19:38,090 --> 00:19:39,316 Satu hingga lapan. 588 00:19:39,316 --> 00:19:40,690 Dan sekarang, saya akan terus pergi. 589 00:19:40,690 --> 00:19:42,030 Saya akan terus mencari di hadapan. 590 00:19:42,030 --> 00:19:42,840 Dan mari kita lihat apa yang berlaku. 591 00:19:42,840 --> 00:19:44,680 Lapan dan tiga, sudah Sudah tentu, daripada perintah. 592 00:19:44,680 --> 00:19:45,815 Mari kita swap. 593 00:19:45,815 --> 00:19:46,940 Lapan dan tujuh tahun, sudah tentu. 594 00:19:46,940 --> 00:19:47,481 Telah habis. 595 00:19:47,481 --> 00:19:48,280 Mari kita swap. 596 00:19:48,280 --> 00:19:49,940 Swap lapan dan lima, sudah tentu, mari kita. 597 00:19:49,940 --> 00:19:50,560 Baiklah. 598 00:19:50,560 --> 00:19:51,880 Senarai disusun. 599 00:19:51,880 --> 00:19:53,060 ya? 600 00:19:53,060 --> 00:19:54,280 >> OK, jelas tidak. 601 00:19:54,280 --> 00:19:55,860 Tetapi ia adalah sedikit lebih baik, bukan? 602 00:19:55,860 --> 00:19:57,270 Oleh kerana notis apa yang berlaku. 603 00:19:57,270 --> 00:20:01,749 Setiap kali kami melakukan swap, yang lebih kecil beberapa jenis meresap cara itu, 604 00:20:01,749 --> 00:20:03,790 dan nombor yang lebih besar meresap cara ini, atau kita akan 605 00:20:03,790 --> 00:20:06,880 mula pepatah dipam kepada kiri atau dipam ke kanan. 606 00:20:06,880 --> 00:20:10,080 >> Kini, ia tidak mencukupi, kerana yang terbaik sebilangan mungkin 607 00:20:10,080 --> 00:20:11,990 telah berpindah satu tempat ke hadapan, atau paling teruk, 608 00:20:11,990 --> 00:20:13,880 bilangan yang mungkin mempunyai bergerak satu tempat lagi. 609 00:20:13,880 --> 00:20:16,369 Supaya anda tahu apa, jenis ini daripada bekerja dengan baik setakat ini. 610 00:20:16,369 --> 00:20:17,410 Biar saya cuba sekali lagi. 611 00:20:17,410 --> 00:20:18,880 Dua dan empat, mereka OK. 612 00:20:18,880 --> 00:20:20,180 Empat hingga enam, mereka OK. 613 00:20:20,180 --> 00:20:21,790 Enam dan satu, keluar perintah. 614 00:20:21,790 --> 00:20:23,007 Jadi mari kita menukar kamu berdua. 615 00:20:23,007 --> 00:20:25,840 Dan kini, melihat masalah ini mula mendapat sedikit lebih baik lagi. 616 00:20:25,840 --> 00:20:27,006 Enam dan tiga, keluar perintah. 617 00:20:27,006 --> 00:20:28,100 Mari kita menukar kamu berdua. 618 00:20:28,100 --> 00:20:29,730 Enam dan tujuh, anda baik. 619 00:20:29,730 --> 00:20:32,230 Tujuh dan lima, sudah tentu, daripada perintah. 620 00:20:32,230 --> 00:20:33,920 Tujuh dan lapan, teratur. 621 00:20:33,920 --> 00:20:36,470 Dan sekarang, saya mungkin perlu melakukan ini beberapa kali. 622 00:20:36,470 --> 00:20:39,830 Dan sebenarnya, berfikir untuk diri kamu sendiri mungkin berapa kali maksima 623 00:20:39,830 --> 00:20:41,330 mungkin saya perlu berjalan kaki ke belakang dan sebagainya? 624 00:20:41,330 --> 00:20:42,390 >> Kami akan kembali kepada itu. 625 00:20:42,390 --> 00:20:43,700 Jadi dua dan empat masih OK. 626 00:20:43,700 --> 00:20:44,940 Empat dan satu, nope. 627 00:20:44,940 --> 00:20:45,747 Jadi, mari kita swap. 628 00:20:45,747 --> 00:20:47,830 Dan sekali lagi, melihat visual satu adalah jenis menggelegak 629 00:20:47,830 --> 00:20:49,163 ke kiri, di mana ia sepatutnya. 630 00:20:49,163 --> 00:20:50,010 Empat dan tiga swap. 631 00:20:50,010 --> 00:20:51,330 Empat dan enam. 632 00:20:51,330 --> 00:20:53,100 Enam dan lima swap. 633 00:20:53,100 --> 00:20:53,959 Enam dan tujuh. 634 00:20:53,959 --> 00:20:55,000 Tujuh dan lapan bagus. 635 00:20:55,000 --> 00:20:55,500 >> Yang baik. 636 00:20:55,500 --> 00:20:58,460 Kami mendapat lebih baik. 637 00:20:58,460 --> 00:20:59,130 Jadi mari kita lihat. 638 00:20:59,130 --> 00:21:00,940 Sekarang, kita mempunyai dua dan satu. 639 00:21:00,940 --> 00:21:02,520 Sudah tentu, menukar. 640 00:21:02,520 --> 00:21:07,520 Dua dan tiga, tiga dan empat, empat dan enam dan tujuh lapan lima, tujuh dan. 641 00:21:07,520 --> 00:21:08,020 Yang baik. 642 00:21:08,020 --> 00:21:08,730 Dan anda tahu apa? 643 00:21:08,730 --> 00:21:11,190 Kerana saya membuat satu perubahan di sana, biarlah saya lakukan salah kewarasan cek. 644 00:21:11,190 --> 00:21:13,023 Biar saya pergi sepanjang jalan kembali ke permulaan. 645 00:21:13,023 --> 00:21:13,680 OKAY. 646 00:21:13,680 --> 00:21:14,750 Satu, two-- yup, lihat? 647 00:21:14,750 --> 00:21:15,870 Sesuatu yang salah. 648 00:21:15,870 --> 00:21:18,420 Tiga, empat, lima, enam, tujuh, lapan. 649 00:21:18,420 --> 00:21:21,920 Dan dalam pas terakhir ini, adalah anda selesa dengan saya sekarang 650 00:21:21,920 --> 00:21:23,830 mengaku ia disusun? 651 00:21:23,830 --> 00:21:24,330 OKAY. 652 00:21:24,330 --> 00:21:25,880 Visual, itu sememangnya benar. 653 00:21:25,880 --> 00:21:28,410 Tetapi fungsi, apa itu juga hanya berlaku 654 00:21:28,410 --> 00:21:31,870 dalam pas lepas yang membolehkan anda mengesahkan bahawa senarai ini memang 655 00:21:31,870 --> 00:21:32,660 disusun? 656 00:21:32,660 --> 00:21:34,477 >> Apa yang saya buat atau tidak pas lepas ini? 657 00:21:34,477 --> 00:21:35,810 PENONTON: Tiada sebarang perubahan. 658 00:21:35,810 --> 00:21:36,120 DAVID J. MALAN: Maaf? 659 00:21:36,120 --> 00:21:37,070 PENONTON: Tiada perubahan. 660 00:21:37,070 --> 00:21:38,653 DAVID J. MALAN: Tiada sebarang perubahan. 661 00:21:38,653 --> 00:21:41,947 Jadi ia akan menjadi bodoh saya melakukan algoritma yang sama sekali lagi 662 00:21:41,947 --> 00:21:43,780 jika saya tidak membuat apa-apa perubahan kali pertama. 663 00:21:43,780 --> 00:21:45,160 Dan negeri ini tidak pernah berubah. 664 00:21:45,160 --> 00:21:47,576 Sesungguhnya, saya tidak akan membuat apa-apa perubahan kali kedua. 665 00:21:47,576 --> 00:21:49,820 Dan sebagainya, ia adalah selamat sekarang berkata, senarai disusun. 666 00:21:49,820 --> 00:21:52,069 >> Dan sesungguhnya, ini kini sesuatu yang kita akan umumnya 667 00:21:52,069 --> 00:21:56,900 panggilan gelembung jenis, di mana dari segi pasangan, anda membetulkan kesilapan sekali lagi, 668 00:21:56,900 --> 00:22:00,210 dan lagi, dan lagi, dan anda terus pergi ke belakang dan sebagainya, 669 00:22:00,210 --> 00:22:03,370 dan belakang dan sebagainya, sehingga anda tidak membuat pertukaran tersebut, di mana titik 670 00:22:03,370 --> 00:22:07,089 anda boleh yakin, ya, saya selesai memasang semua kesilapan. 671 00:22:07,089 --> 00:22:08,630 Mari kita menetapkan semula dan cuba pendekatan lain. 672 00:22:08,630 --> 00:22:11,590 Jika anda semua boleh kembali ke dalam perintah itu anda adalah masa yang lalu, 673 00:22:11,590 --> 00:22:13,780 yang kelihatan seperti ini. 674 00:22:13,780 --> 00:22:17,640 Sekarang, mari kita mengambil pendekatan yang sedikit lebih seperti buku peperiksaan, 675 00:22:17,640 --> 00:22:21,122 di mana kami sentiasa memilih huruf abjad 676 00:22:21,122 --> 00:22:22,830 yang kita jenis mahu menangani depan. 677 00:22:22,830 --> 00:22:26,420 Mungkin ia adalah surat yang tinggi, seperti A, atau Z. surat yang rendah 678 00:22:26,420 --> 00:22:28,170 >> Jadi semua orang yang kembali teratur ini. 679 00:22:28,170 --> 00:22:29,800 Dan sekarang mari saya melakukan ini. 680 00:22:29,800 --> 00:22:34,880 Mari kita lihat Saya tahu saya mempunyai lapan nombor tersebut di sini. 681 00:22:34,880 --> 00:22:37,410 Saya akan pergi ke depan dan hanya sengaja pilih 682 00:22:37,410 --> 00:22:38,520 unsur-unsur yang paling kecil. 683 00:22:38,520 --> 00:22:38,760 Betul? 684 00:22:38,760 --> 00:22:39,801 Ini seolah-olah intuitif juga. 685 00:22:39,801 --> 00:22:42,560 Kenapa saya tidak mencari yang paling kecil elemen, meletakkan ia di mana ia tergolong, 686 00:22:42,560 --> 00:22:45,280 kemudian mendapatkan unsur yang paling kecil yang akan datang, meletakkan ia di mana ia tergolong, dan hanya mengulangi. 687 00:22:45,280 --> 00:22:46,820 >> Kerana intuitif, yang perlu bekerja juga. 688 00:22:46,820 --> 00:22:48,441 Jadi empat, itu adalah satu jumlah yang cukup kecil. 689 00:22:48,441 --> 00:22:49,940 Saya akan ingat di mana ini adalah. 690 00:22:49,940 --> 00:22:50,523 Tunggu sekejap. 691 00:22:50,523 --> 00:22:51,577 Dua adalah lebih kecil. 692 00:22:51,577 --> 00:22:53,910 Kini saya akan ingat di mana dua adalah, dan melupakan empat. 693 00:22:53,910 --> 00:22:55,050 Kami akan berurusan dengan itu kemudian. 694 00:22:55,050 --> 00:22:56,460 Enam, saya tidak berminat. 695 00:22:56,460 --> 00:22:57,810 Lapan, saya tidak berminat. 696 00:22:57,810 --> 00:22:59,780 Satu adalah nombor baru saya kecil. 697 00:22:59,780 --> 00:23:01,470 Jadi, saya akan ingat di mana seseorang itu. 698 00:23:01,470 --> 00:23:02,534 Tiga, tidak berminat. 699 00:23:02,534 --> 00:23:03,450 Tujuh, tidak berminat. 700 00:23:03,450 --> 00:23:04,530 Lima, tidak berminat. 701 00:23:04,530 --> 00:23:07,390 >> Jadi tanpa terjatuh dari peringkat tahun ini, 702 00:23:07,390 --> 00:23:09,890 Saya akan merebut nombor one-- dan apa yang nama anda lagi? 703 00:23:09,890 --> 00:23:10,150 >> ANNAN: Annan. 704 00:23:10,150 --> 00:23:11,220 >> DAVID J. MALAN: Annan. 705 00:23:11,220 --> 00:23:13,540 Dan jika anda boleh bersama dengan saya di awal senarai, 706 00:23:13,540 --> 00:23:14,870 mari kita meletakkan anda di mana anda berada. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- apa nama anda? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. MALAN: Stefan adalah di jalan. 710 00:23:18,191 --> 00:23:23,490 Jadi sebelum Stefan menyelesaikan ini masalah, apa yang patut kita buat? 711 00:23:23,490 --> 00:23:25,412 Apa yang kita lakukan dengan Stefan? 712 00:23:25,412 --> 00:23:27,269 >> PENONTON: [didengar]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. MALAN: OK. 714 00:23:28,060 --> 00:23:28,850 Oleh itu, kita boleh berbuat demikian. 715 00:23:28,850 --> 00:23:31,730 Kita boleh semacam mengambil Stefan dan beliau empat, dan hanya meletakkan ia dalam pembolehubah 716 00:23:31,730 --> 00:23:33,530 dan berpegang kepadanya untuk beberapa jumlah masa, 717 00:23:33,530 --> 00:23:35,220 dan dengan itu membuat ruang untuk nombor satu. 718 00:23:35,220 --> 00:23:36,280 Dan itu bukan tidak baik. 719 00:23:36,280 --> 00:23:39,270 Saya boleh mencadangkan, mengapa tidak melakukan kita hanya meletakkan Stefan di sini? 720 00:23:39,270 --> 00:23:41,610 Mengapa ini mungkin melanggar salah satu daripada idea-idea kami mula 721 00:23:41,610 --> 00:23:44,830 bercakap tentang masa lalu, minggu lepas? 722 00:23:44,830 --> 00:23:45,330 Ya? 723 00:23:45,330 --> 00:23:45,740 >> PENONTON: [didengar]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. MALAN: Tidak ada indeks untuk itu. 725 00:23:46,860 --> 00:23:49,735 Jika anda berfikir ini, sesungguhnya, sebagai lokasi, ini adalah seperti yang negatif, 726 00:23:49,735 --> 00:23:52,900 jadi tidak ada memori sebenarnya di sini jika ini memang pelbagai, 727 00:23:52,900 --> 00:23:55,090 seperti kita mengisytiharkan minggu lepas dalam kuliah. 728 00:23:55,090 --> 00:23:56,250 Oleh itu, kita tidak boleh melakukan ini. 729 00:23:56,250 --> 00:23:57,340 Kita mungkin menyimpannya dalam pembolehubah. 730 00:23:57,340 --> 00:23:57,820 >> Atau anda tahu apa? 731 00:23:57,820 --> 00:23:59,153 Saya mendengar orang lain mencadangkan ia. 732 00:23:59,153 --> 00:24:01,020 Apa lagi yang kita boleh lakukan dengan Stefan? 733 00:24:01,020 --> 00:24:03,770 Apa kata kita hanya mengusir dia dan meletakkan dia lebih di mana nombor satu itu. 734 00:24:03,770 --> 00:24:05,170 Jadi, jika anda mahu pergi ke sana. 735 00:24:05,170 --> 00:24:07,300 Dan sesungguhnya, ini adalah satu penyelesaian yang cukup baik. 736 00:24:07,300 --> 00:24:10,480 Sekarang dalam satu tangan, saya telah baik hati daripada memberikan masalah yang lebih teruk. 737 00:24:10,480 --> 00:24:13,650 Empat kini lebih jauh dari mana ia sepatutnya. 738 00:24:13,650 --> 00:24:14,900 Ia perlu ke arah separuh ini. 739 00:24:14,900 --> 00:24:16,100 >> Tetapi anda tahu apa? 740 00:24:16,100 --> 00:24:17,630 Yang boleh menjadi nasib malang. 741 00:24:17,630 --> 00:24:18,822 Nombor lapan Mungkin berada di sini. 742 00:24:18,822 --> 00:24:20,530 Dan sebagainya, mungkin kita akan telah mendapat bernasib baik, 743 00:24:20,530 --> 00:24:22,460 dan menolak lapan lebih dekat kepada akhir. 744 00:24:22,460 --> 00:24:24,710 Jadi pada akhir hari, ia jenis semua Purata keluar. 745 00:24:24,710 --> 00:24:26,085 Kita tidak perlu mengambil berat tentang empat. 746 00:24:26,085 --> 00:24:29,400 Apa yang saya mengambil berat tentang sekarang adalah memilih elemen yang paling kecil. 747 00:24:29,400 --> 00:24:32,030 >> Dan sekarang, apa yang saya akan lakukan adalah melupakan nombor satu 748 00:24:32,030 --> 00:24:35,160 selama-lamanya, kerana saya tahu Senarai di belakang saya kini disusun. 749 00:24:35,160 --> 00:24:36,720 Jadi senarai saya sebelum ini saiz lapan. 750 00:24:36,720 --> 00:24:37,720 Kini, ia saiz tujuh. 751 00:24:37,720 --> 00:24:40,340 Jadi masalah saya semakin lebih kecil, walaupun secara linear. 752 00:24:40,340 --> 00:24:43,022 Oleh sebab itu, saya akan memilih unsur semasa kecil, dua. 753 00:24:43,022 --> 00:24:46,520 Enam, lapan, empat, tiga, tujuh, lima. 754 00:24:46,520 --> 00:24:47,770 Itu adalah unsur yang paling kecil. 755 00:24:47,770 --> 00:24:49,416 Jadi apa yang saya akan lakukan with-- apakah nama anda lagi? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Yusuf. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. MALAN: Yusuf? 758 00:24:50,085 --> 00:24:52,000 Kita akan meninggalkan Yusuf di tempat. 759 00:24:52,000 --> 00:24:54,842 Sekarang, saya akan berpura-pura bahawa lelaki ini ialah- baik, 760 00:24:54,842 --> 00:24:56,550 Saya tahu bahawa kedua-dua sudah disusun. 761 00:24:56,550 --> 00:24:58,424 Sekarang mari kita memberi tumpuan kepada baki senarai. 762 00:24:58,424 --> 00:25:00,080 Enam yang paling kecil semasa. 763 00:25:00,080 --> 00:25:01,190 Lapan adalah lebih besar. 764 00:25:01,190 --> 00:25:02,970 Empat kini yang paling kecil semasa. 765 00:25:02,970 --> 00:25:04,762 Tiga kini yang paling kecil semasa. 766 00:25:04,762 --> 00:25:07,720 Dan sekarang, saya akan memilih tiga, yang is-- apa nama anda lagi? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. MALAN: Serena, jika anda boleh merebut bilangan dan swap anda with-- 769 00:25:10,620 --> 00:25:11,550 KALSANG: Kalsang. 770 00:25:11,550 --> 00:25:12,940 DAVID J. MALAN: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Ayuh kembali, dan kami akan menukar kedua-dua. 772 00:25:15,220 --> 00:25:17,360 Dan sekarang, mari kita meletakkan ini secara autopilot. 773 00:25:17,360 --> 00:25:21,589 Saya akan pergi dan serahkan kepada anda semua untuk memilih unsur-unsur kecil yang akan datang. 774 00:25:21,589 --> 00:25:22,380 Dun, dun, dun, dun. 775 00:25:22,380 --> 00:25:24,560 Nombor empat, apa yang perlu anda lakukan? 776 00:25:24,560 --> 00:25:26,261 Sangat baik. 777 00:25:26,261 --> 00:25:27,760 Sekarang, saya akan membuat pas lain. 778 00:25:27,760 --> 00:25:28,590 Dun, dun, dun, dun. 779 00:25:28,590 --> 00:25:31,465 Saya melihat lima yang paling kecil yang akan datang. 780 00:25:31,465 --> 00:25:32,840 Sekarang, saya akan mengambil pas lain. 781 00:25:32,840 --> 00:25:33,631 Dun, dun, dun, dun. 782 00:25:33,631 --> 00:25:34,880 Enam yang paling kecil. 783 00:25:34,880 --> 00:25:35,520 Yang baik. 784 00:25:35,520 --> 00:25:36,585 Tujuh adalah yang paling kecil. 785 00:25:36,585 --> 00:25:37,085 Tiada perubahan. 786 00:25:37,085 --> 00:25:38,630 Lapan adalah yang paling kecil. 787 00:25:38,630 --> 00:25:39,170 Selesai. 788 00:25:39,170 --> 00:25:43,900 >> Jadi apa yang kita baru sahaja dilakukan oleh secara berulang memilih salah satu elemen demi satu 789 00:25:43,900 --> 00:25:47,230 adalah melaksanakan sesuatu yang kita akan merasmikan sebagai jenis pemilihan. 790 00:25:47,230 --> 00:25:49,120 Dan ia mungkin juga lebih mudah untuk menjelaskan, 791 00:25:49,120 --> 00:25:51,310 dalam yang benar-benar semua yang anda mahu lakukan adalah hanya menyimpan 792 00:25:51,310 --> 00:25:54,700 pergi dan balik melalui senarai memilih, elemen yang paling kecil akan datang, 793 00:25:54,700 --> 00:25:55,720 sehingga anda selesai. 794 00:25:55,720 --> 00:25:58,650 >> Jadi ia adalah lebih mudah, mungkin intuitif, daripada lepas. 795 00:25:58,650 --> 00:26:00,020 Mari kita cuba salah satu lepas. 796 00:26:00,020 --> 00:26:03,060 Jika anda semua boleh menetapkan semula diri ke dalam jawatan-jawatan berikut 797 00:26:03,060 --> 00:26:08,600 satu masa akhir, mari kita lihat jika kita tidak boleh sekarang merasmikan satu pendekatan lain. 798 00:26:08,600 --> 00:26:12,857 Malah, akan seseorang di luar sana suka untuk mencadangkan 799 00:26:12,857 --> 00:26:14,440 bagaimana lagi kita boleh pergi tentang melakukan ini? 800 00:26:14,440 --> 00:26:17,439 Tanpa melambung keluar buzzwords atau jenis jawapan yang sudah diketahui, 801 00:26:17,439 --> 00:26:19,689 hanya mengikut gerak hati, apa yang kita boleh buat? 802 00:26:19,689 --> 00:26:21,635 >> PENONTON: [didengar]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. MALAN: Ya. 804 00:26:22,510 --> 00:26:24,620 Jadi ada beberapa gerak hati besar di sana. 805 00:26:24,620 --> 00:26:28,020 Perkara-perkara baik seolah-olah berlaku setakat ini dalam bidang sains komputer apabila kita membahagikan 806 00:26:28,020 --> 00:26:30,832 dan menakluk masalah membahagikan pada separuh dan separuh dan separuh. 807 00:26:30,832 --> 00:26:32,540 Dan sebagainya sesungguhnya kami boleh mula berbuat demikian. 808 00:26:32,540 --> 00:26:35,754 Dan sebenarnya, yang akan menjadi, kami akan lihat, salah satu penyelesaian yang terbaik lagi. 809 00:26:35,754 --> 00:26:37,420 Tetapi mari kita kembali kepada yang lama. 810 00:26:37,420 --> 00:26:40,500 Malah, kita akan lakukan yang sedikit pada minggu ini. 811 00:26:40,500 --> 00:26:42,180 Apa lagi yang boleh kita lakukan untuk menyelesaikan masalah ini? 812 00:26:42,180 --> 00:26:44,647 Jadi semua orang di sini di perintah seolah-olah rawak. 813 00:26:44,647 --> 00:26:45,230 Awak tahu tak? 814 00:26:45,230 --> 00:26:48,320 Daripada pergi ke belakang dan sebagainya, belakang dan sebagainya, ke belakang dan sebagainya 815 00:26:48,320 --> 00:26:50,624 setiap kali, ini berasa seperti Saya melakukan banyak berjalan. 816 00:26:50,624 --> 00:26:52,790 Mengapa saya tidak hanya bermula pada awal senarai, 817 00:26:52,790 --> 00:26:54,960 dan hanya meletakkan empat di mana ia tergolong? 818 00:26:54,960 --> 00:26:59,680 Jadi biarlah saya menganggap buat masa ini yang senarai saya hanya elemen pertama ini. 819 00:26:59,680 --> 00:27:04,937 Apakah empat disusun pada masa ini dalam masa, jika semua saya mengambil berat tentang adalah segala-galanya di sini? 820 00:27:04,937 --> 00:27:06,520 Ini adalah jenis trivially benar, bukan? 821 00:27:06,520 --> 00:27:10,000 Seperti senarai yang mengandungi satu nombor, dan yang nombor empat jelas disusun. 822 00:27:10,000 --> 00:27:13,070 >> Jadi biarlah saya hanya menetapkan bahawa senarai ini disusun. 823 00:27:13,070 --> 00:27:15,090 Tetapi sekarang saya mempunyai yang lain dalam senarai ini. 824 00:27:15,090 --> 00:27:17,240 Oleh sebab itu, saya menghadapi dua. 825 00:27:17,240 --> 00:27:21,690 Di manakah dua jelas milik berkenaan dengan empat? 826 00:27:21,690 --> 00:27:22,580 Sebelum empat. 827 00:27:22,580 --> 00:27:23,862 Jadi apa yang boleh saya lakukan di sini? 828 00:27:23,862 --> 00:27:24,820 Apa nama anda lagi? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Yusuf. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. MALAN: Joseph, jika anda boleh langkah ke belakang 831 00:27:26,030 --> 00:27:27,790 hanya untuk seketika dengan nombor anda. 832 00:27:27,790 --> 00:27:31,130 Dan kini apa yang perlu Stefan lakukan di sini? 833 00:27:31,130 --> 00:27:33,720 Mari kita beralih Stefan di sini. 834 00:27:33,720 --> 00:27:35,520 Dan sekarang, mari Yusuf datang di sini. 835 00:27:35,520 --> 00:27:39,660 Dan sekarang, saya mendakwa bahawa segala-galanya di sini disusun. 836 00:27:39,660 --> 00:27:42,474 Jadi, hasilnya sama, tetapi pendekatan dasar yang berbeza. 837 00:27:42,474 --> 00:27:44,140 Saya belum pun melihat apa yang di bawah sana. 838 00:27:44,140 --> 00:27:46,310 Saya hanya terus mengambil unsur-unsur kerana mereka diserahkan kepada saya, 839 00:27:46,310 --> 00:27:47,240 dan berurusan dengan mereka. 840 00:27:47,240 --> 00:27:48,330 >> Oleh sebab itu, saya melihat nombor enam. 841 00:27:48,330 --> 00:27:51,110 Di manakah nombor enam tuanmu? 842 00:27:51,110 --> 00:27:53,250 Kami mempunyai dua, empat, enam. 843 00:27:53,250 --> 00:27:54,800 Tepat di mana dia sekarang. 844 00:27:54,800 --> 00:27:57,750 Jadi mari kita meninggalkan itu sahaja, dan sekarang mendakwa bahawa ini sebahagian daripada senarai 845 00:27:57,750 --> 00:27:58,772 kini disusun. 846 00:27:58,772 --> 00:28:01,230 Dan sebagainya, ini berasa asasnya berbeza dalam bahawa saya hanya 847 00:28:01,230 --> 00:28:05,230 bergerak melalui senarai di sini linear, dan saya tidak pernah berpatah balik. 848 00:28:05,230 --> 00:28:05,730 Ya. 849 00:28:05,730 --> 00:28:06,230 Baiklah. 850 00:28:06,230 --> 00:28:08,190 Jadi lapan, di mana tuanmu? 851 00:28:08,190 --> 00:28:08,730 Di sini. 852 00:28:08,730 --> 00:28:09,310 Perfect. 853 00:28:09,310 --> 00:28:10,210 Oleh sebab itu, satu. 854 00:28:10,210 --> 00:28:10,900 Uh-oh. 855 00:28:10,900 --> 00:28:13,010 Ini berasa seperti ia akan menjadi mahal. 856 00:28:13,010 --> 00:28:15,690 Sekarang, dalam algoritma sebelumnya, Saya hanya bertukar orang. 857 00:28:15,690 --> 00:28:18,648 Jadi saya dapat dihukum sepanjang jalan di mulanya, tetapi kemudian berpindah Yusuf. 858 00:28:18,648 --> 00:28:21,450 Tetapi jika saya bergerak Joseph, kini apa yang akan menjadi salah? 859 00:28:21,450 --> 00:28:24,250 >> Sekarang, saya telah semacam undone-- saya telah mengambil satu langkah ke hadapan dan kemudian 860 00:28:24,250 --> 00:28:26,300 satu langkah ke belakang, kerana sekarang Joseph akan keluar perintah. 861 00:28:26,300 --> 00:28:26,830 Jadi mari kita buat ini. 862 00:28:26,830 --> 00:28:29,150 Jika anda boleh mengambil nombor satu dan langkah ke belakang hanya untuk seketika. 863 00:28:29,150 --> 00:28:30,490 Bagaimana kita boleh put-- apa adalah nama anda lagi? 864 00:28:30,490 --> 00:28:31,130 >> ANNAN: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. MALAN: Annan di tempat? 866 00:28:32,610 --> 00:28:36,091 Apa yang perlu berlaku berkenaan kepada dua, empat, enam dan lapan? 867 00:28:36,091 --> 00:28:37,570 Mereka semua perlu beralih. 868 00:28:37,570 --> 00:28:42,590 Jadi, jika lapan ingin beralih pertama, kemudian enam, kemudian empat, kemudian dua. 869 00:28:42,590 --> 00:28:45,380 Dan kemudian Annan, jika anda lebih suka untuk datang di sini, baik. 870 00:28:45,380 --> 00:28:47,760 Tetapi di sini, kami baru sahaja jenis membayar harga yang 871 00:28:47,760 --> 00:28:49,510 pada titik yang berbeza dalam algoritma. 872 00:28:49,510 --> 00:28:52,550 Sedangkan masa lalu dengan pilihan jenis, dan walaupun gelembung jenis, 873 00:28:52,550 --> 00:28:54,700 Aku berjalan ke belakang dan sebagainya, belakang dan sebagainya, 874 00:28:54,700 --> 00:28:58,360 yang sudah pasti menjumlahkan masa-bijak, dan benar-benar langkah demi langkah. 875 00:28:58,360 --> 00:29:00,660 >> Jenis kemasukan, pada mulanya pandang, kelihatan seperti ia 876 00:29:00,660 --> 00:29:05,150 super bijak, kerana saya hanya membuat perlahan, kemajuan tambahan, 877 00:29:05,150 --> 00:29:07,120 tetapi saya tidak akan ini dan ke belakang. 878 00:29:07,120 --> 00:29:09,410 Tetapi jika seseorang itu memang daripada perintah, notis 879 00:29:09,410 --> 00:29:10,840 semua kerja yang saya hanya terpaksa lakukan. 880 00:29:10,840 --> 00:29:14,750 Saya terpaksa berpindah separuh daripada senarai itu hanya untuk memberi ruang kepada nombor satu. 881 00:29:14,750 --> 00:29:16,790 Jadi ia adalah jumlah yang sama kerja setakat ini ia 882 00:29:16,790 --> 00:29:18,690 merasakan, hanya berlainan jenis kerja. 883 00:29:18,690 --> 00:29:19,370 >> Mari kita terus. 884 00:29:19,370 --> 00:29:22,657 Jadi sekarang kita tahu bahawa semua orang antara satu dan lapan disusun. 885 00:29:22,657 --> 00:29:23,740 Di sini, saya mempunyai nombor tiga. 886 00:29:23,740 --> 00:29:25,864 Jika anda suka untuk mengambil nombor tiga, langkah ke belakang satu. 887 00:29:25,864 --> 00:29:28,260 Dan apa yang anda semua perlu lakukan? 888 00:29:28,260 --> 00:29:28,760 Ya. 889 00:29:28,760 --> 00:29:33,070 Jadi, itu satu sama lain, dua, tiga langkah. 890 00:29:33,070 --> 00:29:36,010 Tiga unit masa itu hanya kos saya, supaya tiga kini patut. 891 00:29:36,010 --> 00:29:37,460 Akhir sekali, tujuh. 892 00:29:37,460 --> 00:29:39,730 >> Mari kita pergi ke hadapan dan mempunyai anda mengambil kembali langkah. 893 00:29:39,730 --> 00:29:42,780 Ini hanya akan kos kita satu unit masa, tetapi tidak apa-apa. 894 00:29:42,780 --> 00:29:44,170 Dan kini, lima yang akan menjadi sedikit lebih mahal. 895 00:29:44,170 --> 00:29:45,340 Jika anda lebih suka untuk langkah ke belakang. 896 00:29:45,340 --> 00:29:48,380 Kita perlu bergerak lapan, dan tujuh, dan enam. 897 00:29:48,380 --> 00:29:50,749 Dan kemudian semua orang kini disusun. 898 00:29:50,749 --> 00:29:52,290 Jadi tangan besar kepada sukarelawan kami di sini. 899 00:29:52,290 --> 00:29:53,554 Terima kasih banyak-banyak. 900 00:29:53,554 --> 00:29:56,220 >> [Tepuk tangan] 901 00:29:56,220 --> 00:29:56,860 >> Terima kasih semua. 902 00:29:56,860 --> 00:29:57,520 Terima kasih semua. 903 00:29:57,520 --> 00:30:02,940 Jadi mari kita lihat sekarang betapa mahal semua itu adalah. 904 00:30:02,940 --> 00:30:06,210 Mari kita pertimbangkan mungkin paling mudah ini, gelembung macam. 905 00:30:06,210 --> 00:30:09,950 Aku berkata paling mudah, hanya kerana anda boleh menyelesaikannya dgn rakus dengan hanya 906 00:30:09,950 --> 00:30:11,660 menyelesaikan masalah dari segi pasangan di sini. 907 00:30:11,660 --> 00:30:13,720 Menyelesaikan masalah dari segi pasangan di sini, sekali lagi dan sekali lagi 908 00:30:13,720 --> 00:30:17,680 dan sekali lagi, mengulangi sebanyak kali yang anda benar-benar perlu. 909 00:30:17,680 --> 00:30:21,050 >> Jadi ia ternyata bahawa dengan sejenis gelembung, baik, 910 00:30:21,050 --> 00:30:25,820 berapa banyak langkah yang perlu saya mengambil pas pertama algoritma itu? 911 00:30:25,820 --> 00:30:30,850 Saya mungkin take-- mari see-- satu, dua, tiga, empat, lima, enam, tujuh. 912 00:30:30,850 --> 00:30:32,190 Dan ada lapan elemen di sini. 913 00:30:32,190 --> 00:30:35,280 Jadi ia seperti n tolak 1 langkah-langkah untuk dapat dari awal senarai 914 00:30:35,280 --> 00:30:36,380 ke akhir senarai. 915 00:30:36,380 --> 00:30:41,350 >> Tetapi dengan jenis pemilihan, ingat bahawa saya memilih unsur-unsur lagi dan lagi 916 00:30:41,350 --> 00:30:44,590 dan sekali lagi bahawa yang paling kecil, Saya meletakkan di tempat, 917 00:30:44,590 --> 00:30:46,616 tetapi kemudian saya tidak mencari di belakang saya lagi. 918 00:30:46,616 --> 00:30:49,490 Jadi saya fikir ia sedikit lebih jelas maka yang pertama kali, saya mungkin 919 00:30:49,490 --> 00:30:52,680 perlu mengambil semua n tolak 1 langkah-langkah untuk mencari elemen yang paling kecil. 920 00:30:52,680 --> 00:30:55,920 Kemudian saya meletakkan mereka di tempat, dan saya mengusir sesiapa yang berada di sini sebelum ini. 921 00:30:55,920 --> 00:30:57,500 >> Tetapi saya tidak perlu menjaga melihat unsur ini, 922 00:30:57,500 --> 00:30:59,040 kerana saya tahu ia pun yang paling kecil. 923 00:30:59,040 --> 00:31:01,581 Jadi sekarang, saya boleh melihat hanya tujuh unsur-unsur, maka enam elemen, 924 00:31:01,581 --> 00:31:03,290 kemudian lima elemen, kemudian empat elemen. 925 00:31:03,290 --> 00:31:06,900 Dan sebagainya secara matematik, jika n ialah bilangan elemen atau nombor 926 00:31:06,900 --> 00:31:11,990 yang kami bermula dengan, anda boleh bayangkan bahawa ini adalah sama seperti n tolak 1, 927 00:31:11,990 --> 00:31:14,250 tambah n tolak 2 langkah, tambah n tolak 3 langkah, 928 00:31:14,250 --> 00:31:16,780 tambah n tolak 4 langkah, semua cara turun ke hanya satu langkah. 929 00:31:16,780 --> 00:31:18,160 Dan saya kepada orang terakhir saya. 930 00:31:18,160 --> 00:31:20,650 >> Dan jika anda masih ingat bahawa banyak daripada stats buku atau buku matematik 931 00:31:20,650 --> 00:31:24,730 mempunyai orang-orang formula pada Paperback belakang atau hadapan mereka, 932 00:31:24,730 --> 00:31:27,690 ternyata bahawa siri ini boleh dinyatakan lebih mudah 933 00:31:27,690 --> 00:31:28,857 sebagai n kali n tolak 1 lebih 2. 934 00:31:28,857 --> 00:31:31,273 Dan ia adalah baik jika itu tidak di barisan hadapan dalam fikiran anda. 935 00:31:31,273 --> 00:31:32,420 Tetapi ini adalah benar. 936 00:31:32,420 --> 00:31:34,449 Itu hanya cara yang lebih mudah untuk menulisnya. 937 00:31:34,449 --> 00:31:36,240 Dan kemudian jika anda berfikir kembali ke sekolah gred, 938 00:31:36,240 --> 00:31:38,698 apabila anda hanya mula membiak perkara, ini sudah tentu, 939 00:31:38,698 --> 00:31:41,820 hanya n kuasa dua tolak n dibahagikan dengan 2. 940 00:31:41,820 --> 00:31:44,772 Apa yang saya lakukan adalah mengembangkan ungkapan di sana. 941 00:31:44,772 --> 00:31:46,730 Dan jadi mari kita menulis semula ini sedikit berbeza. 942 00:31:46,730 --> 00:31:49,780 Itu n kuasa dua dibahagikan dengan 2 tolak n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Jadi sekali lagi, saya hanya jenis memohon beberapa aritmetik memerintah di sana. 944 00:31:53,270 --> 00:31:57,140 Tetapi perhatikan sekarang bahawa istilah yang paling besar dalam ungkapan ini, boleh dikatakan, 945 00:31:57,140 --> 00:31:58,540 ialah n kuasa dua. 946 00:31:58,540 --> 00:32:02,910 Jadi ya, ia adalah n kuasa dua dibahagikan dengan 2, tolak n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Tetapi secara amnya, jika n akan menjadi satu nilai yang besar, 948 00:32:05,080 --> 00:32:08,740 Saya akan mendakwa bahawa n kuasa akan menjadi faktor yang dominan. 949 00:32:08,740 --> 00:32:10,490 Ia hanya akan menjadi penyumbang yang lebih besar 950 00:32:10,490 --> 00:32:12,877 untuk bilangan langkah daripada n / 2. 951 00:32:12,877 --> 00:32:13,960 Jadi, apa yang saya maksudkan dengan ini? 952 00:32:13,960 --> 00:32:16,795 Mari kita cuba contoh yang mudah, walaupun walaupun matematik mendapat besar sedikit. 953 00:32:16,795 --> 00:32:20,210 >> Jadi andaikan kita mempunyai 1 juta orang di atas pentas, atau 1 juta perkara 954 00:32:20,210 --> 00:32:21,320 yang kita mahu untuk menyusun. 955 00:32:21,320 --> 00:32:23,730 Mari kita pasang juta ke dalam formula yang betul-betul 956 00:32:23,730 --> 00:32:27,230 untuk melihat berapa banyak langkah-langkah yang diperlukan jumlah untuk menyusun satu juta elemen menggunakan katakan, 957 00:32:27,230 --> 00:32:28,560 jenis pemilihan. 958 00:32:28,560 --> 00:32:30,760 >> Oleh itu, kita akan mempunyai formula yang sama seperti sebelum ini. 959 00:32:30,760 --> 00:32:34,120 Saya sedang pasang juta, supaya saya dapat satu juta dibahagikan dengan kuasa dua 2, 960 00:32:34,120 --> 00:32:35,990 tolak satu juta dibahagikan dengan 2. 961 00:32:35,990 --> 00:32:40,180 Jika saya melakukan matematik yang lebih awal di sini, kami mempunyai 500 bilion 962 00:32:40,180 --> 00:32:47,460 tolak 500,000, yang memberikan kita 499999500000, 963 00:32:47,460 --> 00:32:49,270 yang cukup darn besar. 964 00:32:49,270 --> 00:32:54,370 >> Malah, jika anda membandingkan sekarang 499000000000, 999 juta, 965 00:32:54,370 --> 00:33:01,210 500,000 berbanding nilai asal kita, 500 bilion, ia begitu sialan rapat. 966 00:33:01,210 --> 00:33:06,850 Betul? n kuasa dua dibahagikan dengan 2 memberikan us-- atau sebaliknya, n kuasa dua bahagi 2 967 00:33:06,850 --> 00:33:08,370 memberikan kita 500 bilion. 968 00:33:08,370 --> 00:33:13,510 Itulah darn cukup dekat untuk 499999500000, 969 00:33:13,510 --> 00:33:17,970 yang mengatakan menolak kira 500,000, atau lebih umum, menolak off 970 00:33:17,970 --> 00:33:20,010 n kuasa dua, tidak benar-benar masalah besar. 971 00:33:20,010 --> 00:33:22,490 N kuasa dua membuat ini nombor berkembang dengan pantas. 972 00:33:22,490 --> 00:33:25,790 >> Sekarang, ini adalah penting hanya setakat seperti yang kita, sebagai saintis komputer, 973 00:33:25,790 --> 00:33:29,350 secara amnya tidak akan mengambil berat tentang nuansa formula ini 974 00:33:29,350 --> 00:33:31,400 dan apa yang jawapan yang tepat berada. 975 00:33:31,400 --> 00:33:33,390 Kami mengambil berat sahaja, anda tahu apa? 976 00:33:33,390 --> 00:33:37,810 Pada akhir hari, formula ini adalah pada perintah itu n kuasa dua. 977 00:33:37,810 --> 00:33:39,350 >> Ya, kita membahagi dengan 2 di sana. 978 00:33:39,350 --> 00:33:41,360 Ya, kami menolak off n tolak 2. 979 00:33:41,360 --> 00:33:46,860 Tetapi pada akhir hari, istilah yang benar-benar menyakitkan kita dan kos kami 980 00:33:46,860 --> 00:33:48,995 banyak langkah-langkah adalah bahawa istilah persegi. 981 00:33:48,995 --> 00:33:51,370 Dan supaya apa yang seorang saintis komputer akan pada amnya melaksanakan 982 00:33:51,370 --> 00:33:54,160 adalah mengabaikan semua orang-orang terma-terma perintah yang lebih kecil, 983 00:33:54,160 --> 00:33:56,900 dan hanya melihat satu yang menyumbang paling banyak kepada kos. 984 00:33:56,900 --> 00:34:00,530 >> Dan ini adalah bagus, kerana kita boleh sekarang bercakap dalam keluasan lebih besar 985 00:34:00,530 --> 00:34:02,470 mengenai algoritma, dan boleh membandingkan mereka. 986 00:34:02,470 --> 00:34:04,550 Dan hakikat bahawa saya menggunakan O ini adalah sengaja. 987 00:34:04,550 --> 00:34:06,680 Apabila saya katakan pada perintah itu daripada, saya secara khusus 988 00:34:06,680 --> 00:34:09,560 merujuk kepada sesuatu dipanggil O. besar dan besar O 989 00:34:09,560 --> 00:34:14,090 notasi yang komputer saintis menggunakan untuk menggambarkan 990 00:34:14,090 --> 00:34:16,710 yang atas terikat pada sesuatu. 991 00:34:16,710 --> 00:34:21,150 >> Jadi, jika anda mengatakan bahawa algoritma adalah di O besar n kuasa dua, 992 00:34:21,150 --> 00:34:23,380 seperti yang saya dicadangkan hanya masa lalu, cara yang 993 00:34:23,380 --> 00:34:27,710 bahawa dari segi perjalanan Pertubuhan masa atau kecekapan, 994 00:34:27,710 --> 00:34:30,090 yang diperlukan pada perintah itu n kuasa dua langkah. 995 00:34:30,090 --> 00:34:31,420 Mungkin lebih, mungkin kurang. 996 00:34:31,420 --> 00:34:33,435 Tetapi ia adalah atas perintah n kuasa dua. 997 00:34:33,435 --> 00:34:34,560 Dan itu atas terikat. 998 00:34:34,560 --> 00:34:36,530 Ia tidak akan menjadi lebih menyakitkan daripada itu. 999 00:34:36,530 --> 00:34:40,800 Ia tidak akan menjadi n cubed, atau 2 untuk n, atau sesuatu yang lebih besar. 1000 00:34:40,800 --> 00:34:43,800 Ini adalah had atas pada apa sahaja kos yang. 1001 00:34:43,800 --> 00:34:46,150 Jadi memandangkan itu, mari kita mempertimbangkan hanya beberapa contoh. 1002 00:34:46,150 --> 00:34:49,820 Dan ini adalah hanya satu senarai terhingga masa-masa yang biasa berjalan 1003 00:34:49,820 --> 00:34:52,870 untuk algoritma yang bertujuan untuk menjadi penerangan mengenai beberapa perkara yang kami telah 1004 00:34:52,870 --> 00:34:53,600 dilihat sudah. 1005 00:34:53,600 --> 00:34:58,060 >> Jadi misalnya, dalam hal jenis pemilihan, apa yang saya menuntut di sini 1006 00:34:58,060 --> 00:35:02,250 SEMAKIN bahawa pemilihan jenis ini masa adalah atas perintah n kuasa dua. 1007 00:35:02,250 --> 00:35:06,260 Dalam kes terburuk, saya akan mempunyai sejumlah besar nombor rawak di sini. 1008 00:35:06,260 --> 00:35:08,600 Dan seperti yang kita lihat secara matematik, jika saya terus berjalan 1009 00:35:08,600 --> 00:35:11,310 melalui senarai, melalui senarai, memilih seterusnya terkecil 1010 00:35:11,310 --> 00:35:14,410 elemen lagi dan lagi, jika saya sebenarnya menulis semua langkah-langkah 1011 00:35:14,410 --> 00:35:18,750 Saya mengambil sebagai saya mencadangkan formulaically sebelum ini, ia adalah atas perintah n kuasa dua 1012 00:35:18,750 --> 00:35:20,370 langkah-langkah yang saya ambil. 1013 00:35:20,370 --> 00:35:24,520 >> Dan ternyata gelembung yang menyusun dan memasukkan jenis 1014 00:35:24,520 --> 00:35:27,370 hanya sebagai perlahan dalam kes yang paling teruk. 1015 00:35:27,370 --> 00:35:32,040 Pertimbangkan, sebagai contoh, jenis kemasukan, algoritma yang terakhir kita ditangani, 1016 00:35:32,040 --> 00:35:35,500 yang mempunyai kita lihat unsur, dan kemudian masukkannya mana ia tergolong. 1017 00:35:35,500 --> 00:35:38,720 Dan kemudian kita melihat elemen yang akan datang, dan memasukkannya dengan mana ia tergolong. 1018 00:35:38,720 --> 00:35:40,990 >> Oleh itu fikirkanlah senario yang terbaik. 1019 00:35:40,990 --> 00:35:45,590 Katakan saya telah sukarelawan saya beratur literal seperti ini, satu melalui lapan, 1020 00:35:45,590 --> 00:35:47,440 sudah disusun. 1021 00:35:47,440 --> 00:35:51,300 Berapa banyak langkah adalah jenis kemasukan akan mengambil untuk menyusun lapan orang, 1022 00:35:51,300 --> 00:35:55,640 jika mereka tiba di atas pentas kelihatan seperti ini? 1023 00:35:55,640 --> 00:35:57,410 >> Lapan orang sudah disusun. 1024 00:35:57,410 --> 00:35:58,760 Dan saya menggunakan jenis kemasukan. 1025 00:35:58,760 --> 00:36:02,180 Yang terakhir algoritma. 1026 00:36:02,180 --> 00:36:03,640 Nah, mari kita melakonkan semula cepat nyata. 1027 00:36:03,640 --> 00:36:05,504 Jadi, jika saya bermula di sini, saya melihat satu. 1028 00:36:05,504 --> 00:36:06,420 Di manakah seseorang tuanmu? 1029 00:36:06,420 --> 00:36:07,730 Ia tergolong di sini. 1030 00:36:07,730 --> 00:36:08,330 Saya melihat dua. 1031 00:36:08,330 --> 00:36:09,660 Di manakah dua tuanmu? 1032 00:36:09,660 --> 00:36:10,260 Di sini. 1033 00:36:10,260 --> 00:36:10,900 Saya melihat tiga. 1034 00:36:10,900 --> 00:36:11,920 Di manakah tiga tuanmu? 1035 00:36:11,920 --> 00:36:12,480 Di sini. 1036 00:36:12,480 --> 00:36:13,100 >> Ada empat. 1037 00:36:13,100 --> 00:36:13,600 Di sini. 1038 00:36:13,600 --> 00:36:15,660 Lima, enam, tujuh, lapan. 1039 00:36:15,660 --> 00:36:17,320 Tiada sebab untuk mengulangi diri saya sendiri. 1040 00:36:17,320 --> 00:36:21,260 Dan langkah-langkah ya, berapa adalah bahawa dari segi n? 1041 00:36:21,260 --> 00:36:23,870 Ia adalah atas perintah n langkah-langkah, bukan? n tolak 1. 1042 00:36:23,870 --> 00:36:27,567 Tetapi saya mengambil beberapa linear langkah-langkah, dan kini saya dilakukan. 1043 00:36:27,567 --> 00:36:28,900 Jadi itulah kes ini, walaupun. 1044 00:36:28,900 --> 00:36:29,983 Bagaimana pula dengan kes yang paling teruk? 1045 00:36:29,983 --> 00:36:32,730 Apa lapan adalah di sana, dan tujuh adalah di bawah sana, 1046 00:36:32,730 --> 00:36:35,840 dan satu dan dua adalah di sini, jadi bahawa senarai itu telah benar-benar diterbalikkan? 1047 00:36:35,840 --> 00:36:38,300 >> Nah, apa yang berlaku memang jika ini adalah bilangan? 1048 00:36:38,300 --> 00:36:41,300 Dan kami akan melakukan hanya beberapa contoh. 1049 00:36:41,300 --> 00:36:49,300 Bagaimana jika, sesungguhnya, nombor lapan di sini, dan yang whoops number--. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Jadi apa jika, sesungguhnya, bilangan lapan adalah sepanjang jalan di sini, 1052 00:36:56,430 --> 00:36:57,790 dan saya menggunakan jenis kemasukan? 1053 00:36:57,790 --> 00:36:58,290 >> OKAY. 1054 00:36:58,290 --> 00:37:00,280 Saya menuntut pada masa ini ia adalah di tempat. 1055 00:37:00,280 --> 00:37:03,152 Tetapi sekarang, seven-- di manakah tujuh pergi? 1056 00:37:03,152 --> 00:37:04,360 Sudah tentu, ia pergi di sini. 1057 00:37:04,360 --> 00:37:06,760 Jadi saya perlu bergerak lapan lebih satu tempat. 1058 00:37:06,760 --> 00:37:08,554 Kini enam, di mana ia pergi? 1059 00:37:08,554 --> 00:37:09,220 Nah, baiklah. 1060 00:37:09,220 --> 00:37:13,150 Sekarang, saya perlu bergerak lapan lebih tempat, dan tujuh lebih tempat, 1061 00:37:13,150 --> 00:37:14,440 dan kemudian saya mencebur ke bawah enam. 1062 00:37:14,440 --> 00:37:16,870 >> Jadi kali pertama, ia kos saya satu langkah untuk menetapkan perkara-perkara, 1063 00:37:16,870 --> 00:37:18,570 maka ia kos saya dua langkah untuk menetapkan perkara-perkara. 1064 00:37:18,570 --> 00:37:20,370 Berapa banyak langkah yang ia akan ambil untuk membaiki 1065 00:37:20,370 --> 00:37:22,720 perkara yang perlu meletakkan lima di tempat yang betul? 1066 00:37:22,720 --> 00:37:23,340 Tiga. 1067 00:37:23,340 --> 00:37:29,520 Kerana sekarang saya perlu bergerak satu, dua, tiga. 1068 00:37:29,520 --> 00:37:32,430 Berapa banyak langkah yang ia akan mengambil untuk meletakkan empat di tempat yang betul? 1069 00:37:32,430 --> 00:37:36,040 4 plus 5, ditambah 6, ditambah 7. 1070 00:37:36,040 --> 00:37:40,260 >> Oleh karena itu, secara matematik sama dengan apa yang kita diterangkan untuk jenis pemilihan. 1071 00:37:40,260 --> 00:37:42,130 Kami mempunyai siri ini yang hanya meningkat. 1072 00:37:42,130 --> 00:37:45,650 1 tambah 2 tambah 3 tambah 4, atau sebaliknya, 7 plus 6 1073 00:37:45,650 --> 00:37:52,610 ditambah 5 ditambah 4 menambah sehingga untuk hari ini tujuan ke atas perintah n kuasa dua. 1074 00:37:52,610 --> 00:37:57,640 >> Jadi biarlah saya menetapkan juga bahawa gelembung jenis juga dalam n kuasa dua. 1075 00:37:57,640 --> 00:38:01,340 Kerana dengan gelembung jenis, masing-masing kali saya pergi melalui senarai, 1076 00:38:01,340 --> 00:38:03,100 Saya mengambil kira-kira berapa banyak langkah? 1077 00:38:03,100 --> 00:38:06,260 Setiap kali saya benar-benar berjalan dari sana ke sana? 1078 00:38:06,260 --> 00:38:07,960 Secara kasar n langkah. 1079 00:38:07,960 --> 00:38:12,650 Tetapi berapa kali mungkin saya perlu melalui senarai? 1080 00:38:12,650 --> 00:38:13,920 >> Well, secara kasar n masa. 1081 00:38:13,920 --> 00:38:15,680 Mungkin n tolak 1, tetapi secara kasar n kali. 1082 00:38:15,680 --> 00:38:16,430 Nah, mengapa? 1083 00:38:16,430 --> 00:38:19,560 Nah, dengan semacam gelembung, jika kita mulakan dengan jenis gelembung, 1084 00:38:19,560 --> 00:38:23,570 dengan senarai dalam yang paling teruk mungkin keadaan, yang sekali lagi adalah 1085 00:38:23,570 --> 00:38:25,550 ke belakang, apa yang akan berlaku? 1086 00:38:25,550 --> 00:38:28,830 Saya memeriksa senarai, dan nombor salah tergolong sepanjang jalan di sana. 1087 00:38:28,830 --> 00:38:33,280 >> Tetapi dengan jenis gelembung, sejauh melakukan satu bergerak pas pertama saya melalui senarai? 1088 00:38:33,280 --> 00:38:36,620 Berapa banyak tempat dia mendapatkan lebih dekat ke tempat yang betul? 1089 00:38:36,620 --> 00:38:37,240 Hanya satu. 1090 00:38:37,240 --> 00:38:40,281 Jadi, jika anda jenis sebab melalui ini, setiap kali melalui algoritma ini, 1091 00:38:40,281 --> 00:38:41,880 Mengambil secara kasar n langkah Daud. 1092 00:38:41,880 --> 00:38:44,940 Tetapi berapa ramai pas melalui senarai adalah ia 1093 00:38:44,940 --> 00:38:49,060 akan mengambil selama satu hingga gelembung ke kiri di mana ia tergolong? 1094 00:38:49,060 --> 00:38:51,840 >> Dia ada untuk bergerak seperti, n ruang dengan cara ini. 1095 00:38:51,840 --> 00:38:57,960 Jadi hanya untuk melakukan pengasingan senarai, Saya perlu berjalan kaki berulang-alik n kali. 1096 00:38:57,960 --> 00:39:01,540 Dan setiap kali, saya melihat n unsur-unsur. 1097 00:39:01,540 --> 00:39:05,410 Begitu n perkara n kali pada perintah n kuasa dua. 1098 00:39:05,410 --> 00:39:07,220 >> Sekarang, kita akan melihat dalam beberapa daripada seluar pendek yang 1099 00:39:07,220 --> 00:39:10,440 tertanam dalam Masalah seterusnya CS50 ditetapkan, pendekatan lain pada ini, 1100 00:39:10,440 --> 00:39:13,490 tetapi buat masa ini, mari kita mempertimbangkan beberapa masa yang lain sedang berjalan, 1101 00:39:13,490 --> 00:39:16,840 terutamanya jika orang-orang yang menyusun mengambil sedikit masa untuk tenggelam dalam. 1102 00:39:16,840 --> 00:39:21,790 Apa yang algoritma kita lihat sudah yang mengambil atas perintah n langkah? 1103 00:39:21,790 --> 00:39:27,560 >> Apakah yang perlu mengambil beberapa linear daripada beberapa langkah yang kita lihat setakat ini? 1104 00:39:27,560 --> 00:39:29,350 Apa itu? 1105 00:39:29,350 --> 00:39:30,480 Pencarian direktori telefon. 1106 00:39:30,480 --> 00:39:31,390 Algoritma pertama. 1107 00:39:31,390 --> 00:39:31,560 Betul? 1108 00:39:31,560 --> 00:39:33,650 Di mana kita berada linear mencari Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Sesungguhnya. 1110 00:39:34,150 --> 00:39:37,180 Dari minggu sifar, apabila saya mula menjadikan satu halaman pada satu masa, 1111 00:39:37,180 --> 00:39:40,095 dan saya juga berkata bahawa ia adalah jenis algoritma perasaan linear, 1112 00:39:40,095 --> 00:39:42,720 dan kami bahawa gambar pada papan dengan garis merah yang lurus 1113 00:39:42,720 --> 00:39:44,678 dan kuning lurus line, mereka sememangnya 1114 00:39:44,678 --> 00:39:46,810 algoritma yang ada di O besar n. 1115 00:39:46,810 --> 00:39:50,680 >> Kerana untuk mencari Mike Smith dalam telefon buku n muka surat, dalam kes paling teruk, 1116 00:39:50,680 --> 00:39:52,422 mungkin mengambil masa saya n langkah. 1117 00:39:52,422 --> 00:39:53,630 Bagaimana pula dengan mengambil kehadiran? 1118 00:39:53,630 --> 00:39:55,790 Satu dua tiga empat lima enam. 1119 00:39:55,790 --> 00:39:59,420 Apa yang masa berjalan ini algoritma untuk mengambil kehadiran? 1120 00:39:59,420 --> 00:40:03,070 O Big n, kerana dalam teori saya perlu menunjukkan semua orang di dalam bilik. 1121 00:40:03,070 --> 00:40:05,861 >> Sekarang sebagai diketepikan, bagaimana pula dengan pengoptimuman lain dari minggu sifar? 1122 00:40:05,861 --> 00:40:08,117 Dua, empat, enam, lapan, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Seorang saintis komputer akan sedar, tunggu satu minit, 1124 00:40:10,200 --> 00:40:12,320 itu atas perintah n dibahagikan dengan dua langkah. 1125 00:40:12,320 --> 00:40:12,820 Betul? 1126 00:40:12,820 --> 00:40:14,444 Kerana saya lakukan dua orang pada satu masa. 1127 00:40:14,444 --> 00:40:17,015 Tetapi kita akan mengabaikan terma perintah yang lebih rendah, 1128 00:40:17,015 --> 00:40:19,140 dan kami hanya akan buang jurang dengan 2, 1129 00:40:19,140 --> 00:40:21,830 dan hanya berkata, Wahai besar n untuk algoritma itu juga. 1130 00:40:21,830 --> 00:40:22,760 >> Bagaimana dengan yang ini? 1131 00:40:22,760 --> 00:40:26,170 Kami akan melewati beberapa ini, tetapi apa yang adalah satu algoritma yang telah log n? 1132 00:40:26,170 --> 00:40:29,900 Yang telah mengambil kira-kira log n langkah? 1133 00:40:29,900 --> 00:40:30,870 Ini pecah dan perintah. 1134 00:40:30,870 --> 00:40:31,369 Tepat sekali. 1135 00:40:31,369 --> 00:40:33,900 Seperti contoh buku telefon di minggu sifar dan awal hari ini, 1136 00:40:33,900 --> 00:40:36,191 di mana kita dibahagikan masalah lagi dan lagi dan lagi. 1137 00:40:36,191 --> 00:40:39,070 Kita menarik ke atas pesawat pada minggu sifar dalam garisan hijau melengkung, 1138 00:40:39,070 --> 00:40:41,460 dan kami berkata hari itu ia algoritma logaritma. 1139 00:40:41,460 --> 00:40:44,970 >> Dan sesungguhnya, bilangan langkah-langkah yang yang diperlukan untuk melaksanakan pecah dan menakluk, 1140 00:40:44,970 --> 00:40:48,610 atau carian binari seperti yang kita akan mula memanggil ia, seperti dalam buku telefon, 1141 00:40:48,610 --> 00:40:50,680 adalah atas perintah log dan langkah-langkah. 1142 00:40:50,680 --> 00:40:52,470 Dan ini adalah sedikit satu yang pelik. 1143 00:40:52,470 --> 00:40:54,910 >> Apa yang mengambil satu langkah, atau lebih khusus 1144 00:40:54,910 --> 00:40:56,240 beberapa langkah berterusan? 1145 00:40:56,240 --> 00:40:58,865 Mungkin ia dua, mungkin ia adalah tiga, tetapi seorang saintis komputer hanya 1146 00:40:58,865 --> 00:41:01,423 memudahkan ia sebagai O besar 1, beberapa nombor tetap langkah. 1147 00:41:01,423 --> 00:41:04,256 Apakah sesuatu yang anda boleh berbuat demikian mengambil beberapa langkah-langkah yang berterusan? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Apa yang masa berjalan bertepuk tangan? 1150 00:41:10,930 --> 00:41:11,920 Masa yang berterusan. 1151 00:41:11,920 --> 00:41:12,420 Betul? 1152 00:41:12,420 --> 00:41:15,490 Seperti, apa yang masa berjalan melakukan apa-apa yang mengambil masa hanya satu 1153 00:41:15,490 --> 00:41:18,570 operasi, seperti mencetak F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Yang mungkin dikatakan sebagai masa yang berterusan, melainkan jika kurang kes sudut dengan cap F, 1155 00:41:24,110 --> 00:41:28,260 apa mungkin masa yang berjalan cetak F sebenarnya berlaku? 1156 00:41:28,260 --> 00:41:28,790 Dan mengapa? 1157 00:41:28,790 --> 00:41:30,550 Apakah n pengukur dalam kes itu? 1158 00:41:30,550 --> 00:41:32,251 >> PENONTON: [didengar]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. MALAN: Tepat sekali. 1160 00:41:33,250 --> 00:41:34,900 Bilangan aksara kita ingin cetak. 1161 00:41:34,900 --> 00:41:36,191 Jadi ia amat peka konteks. 1162 00:41:36,191 --> 00:41:39,910 Hari ini, kita telah memberi tumpuan banyak pada huruf dan nombor di atas kapal. 1163 00:41:39,910 --> 00:41:43,540 Tetapi ia juga mungkin watak-watak dalam rentetan yang sebenar. 1164 00:41:43,540 --> 00:41:46,420 Jadi, ternyata terdapat satu lagi langkah yang akan mula mengambil berat tentang, 1165 00:41:46,420 --> 00:41:48,530 dan itu bertentangan dengan O besar, jadi untuk bercakap. 1166 00:41:48,530 --> 00:41:50,120 >> Itulah notasi omega. 1167 00:41:50,120 --> 00:41:53,380 Manakala O besar bermakna apa yang, yang atas terikat pada masa anda berjalan? 1168 00:41:53,380 --> 00:41:55,580 Maksima, berapa banyak masa mungkin sesuatu yang diambil? 1169 00:41:55,580 --> 00:41:59,250 Omega-- maaf ini terus datang up-- adalah bertentangan dengan itu, 1170 00:41:59,250 --> 00:42:02,960 di mana ia adalah lebih rendah terikat pada jumlah masa sesuatu yang mungkin mengambil masa. 1171 00:42:02,960 --> 00:42:10,480 >> So. misalnya, apa yang algoritma yang mengambil langkah-langkah sentiasa n kuasa? 1172 00:42:10,480 --> 00:42:15,600 Nah, salah satu daripada algoritma yang kami telah lihat hari ini, sebenarnya, mungkin itu juga. 1173 00:42:15,600 --> 00:42:16,720 Jenis pemilihan. 1174 00:42:16,720 --> 00:42:18,270 Pemilihan jenis agak bodoh. 1175 00:42:18,270 --> 00:42:21,760 Walaupun maaf algorithm--, walaupun jika array sudah disusun, 1176 00:42:21,760 --> 00:42:24,150 jenis pemilihan akan terus berjalan melalui senarai 1177 00:42:24,150 --> 00:42:28,907 memastikan ia mempunyai yang paling kecil elemen lagi dan lagi dan lagi. 1178 00:42:28,907 --> 00:42:31,740 Juga, meskipun manusia dalam penonton tahu bahawa, tunggu satu minit, 1179 00:42:31,740 --> 00:42:33,948 anda sudah lulus unsur yang paling kecil, komputer 1180 00:42:33,948 --> 00:42:37,300 tidak tahu bahawa sehingga ia kelihatan sepanjang jalan melalui senarai. 1181 00:42:37,300 --> 00:42:40,240 Begitu juga, terikat yang lebih rendah mungkin juga diambil kira 1182 00:42:40,240 --> 00:42:42,000 mungkin masa linear. 1183 00:42:42,000 --> 00:42:48,260 >> Berapa banyak masa yang diperlukan untuk jenis n elemen dalam yang terbaik 1184 00:42:48,260 --> 00:42:52,420 kes menggunakan sesuatu seperti jenis gelembung? 1185 00:42:52,420 --> 00:42:54,280 Katakan senarai anda sudah disusun. 1186 00:42:54,280 --> 00:42:56,696 Kami berkata semacam gelembung mengambil perintah n kuasa dua langkah. 1187 00:42:56,696 --> 00:42:59,640 Tetapi bagaimana jika ia sudah disusun? 1188 00:42:59,640 --> 00:43:02,310 Bagaimana jika anda sedar selepas satu pas melalui array 1189 00:43:02,310 --> 00:43:03,540 yang anda telah membuat sebarang pertukaran? 1190 00:43:03,540 --> 00:43:05,970 Adakah anda perlu untuk terus membuat lebih pas? 1191 00:43:05,970 --> 00:43:06,470 >> No. 1192 00:43:06,470 --> 00:43:10,340 Jadi terikat lebih rendah pada gelembung jenis mungkin dikatakan linear. 1193 00:43:10,340 --> 00:43:11,830 Omega n. 1194 00:43:11,830 --> 00:43:14,450 Dan kita boleh melihat yang lain dari ini juga. 1195 00:43:14,450 --> 00:43:17,990 Jadi mari kita lihat cepat pada hanya visualisasi di sini 1196 00:43:17,990 --> 00:43:20,790 untuk melihat bagaimana membezakan diri mereka. 1197 00:43:20,790 --> 00:43:24,592 Saya akan pergi ke sini ke dalam ini halaman yang boleh didapati di laman web C50-kanak, 1198 00:43:24,592 --> 00:43:27,550 tetapi ia akan menjadi sakit untuk mendapatkan kerja, kerana ia menggunakan teknologi yang dipanggil 1199 00:43:27,550 --> 00:43:30,560 Java applet, yang merupakan sebahagian besarnya disokong hari ini, 1200 00:43:30,560 --> 00:43:32,730 sekurang-kurangnya oleh Chrome dan lain-lain yang tertentu. 1201 00:43:32,730 --> 00:43:37,070 >> Dan biarlah saya pergi ke hadapan dan mempercepatkan ini dan menjelaskan apa yang berlaku. 1202 00:43:37,070 --> 00:43:40,840 Ini adalah demonstrasi gelembung jenis, algoritma pertama kita melihat. 1203 00:43:40,840 --> 00:43:43,950 Dan ia adalah satu visualisasi di mana setiap bar ini mewakili nombor. 1204 00:43:43,950 --> 00:43:45,710 Semakin besar bar, yang lebih besar nombor. 1205 00:43:45,710 --> 00:43:47,520 Semakin kecil bar, yang lebih kecil nombor. 1206 00:43:47,520 --> 00:43:50,353 Dan apa yang anda lihat secara visual, walaupun walaupun ini akan super cepat, 1207 00:43:50,353 --> 00:43:53,699 adalah bahawa bar merah adalah seperti saya, berjalan berulang-alik menetapkan masalah. 1208 00:43:53,699 --> 00:43:56,740 Anda boleh melihat bahawa unsur-unsur yang lebih besar memang menggelegak sehingga ke kanan, 1209 00:43:56,740 --> 00:43:59,650 dan unsur-unsur yang lebih kecil sedang menggelegak sehingga kiri. 1210 00:43:59,650 --> 00:44:01,870 Dan turun di sini, jika kita benar-benar melihat dengan lebih dekat, 1211 00:44:01,870 --> 00:44:04,330 kita sebenarnya boleh mengira beberapa perbandingan dan swap 1212 00:44:04,330 --> 00:44:05,350 yang sedang dibuat. 1213 00:44:05,350 --> 00:44:07,360 >> Tetapi sebaliknya, mari kita lihat di algoritma kedua 1214 00:44:07,360 --> 00:44:11,240 kita melihat lebih awal dengan kami sukarelawan, jenis pemilihan. 1215 00:44:11,240 --> 00:44:13,500 Visual, ia mempunyai kesan yang sangat berbeza. 1216 00:44:13,500 --> 00:44:16,820 Tetapi ia adalah, sekali lagi, sangat intuitif, dalam bahawa kita terus memilih seterusnya terkecil 1217 00:44:16,820 --> 00:44:18,660 elemen, dan kami mendapat sedikit bertuah. 1218 00:44:18,660 --> 00:44:20,110 Yang merasakan asasnya lebih cepat. 1219 00:44:20,110 --> 00:44:22,840 Tetapi jika kita berlari ini lagi dan lagi dan sekali lagi dengan banyak input, 1220 00:44:22,840 --> 00:44:26,680 kita akan melihat bahawa itu memang masih di O besar n kuasa dua. 1221 00:44:26,680 --> 00:44:29,920 >> Mari kita buat satu yang terakhir gula-jenis kemasukan, 1222 00:44:29,920 --> 00:44:33,180 yang merupakan algoritma ketiga kita melihat, dan ingat 1223 00:44:33,180 --> 00:44:36,700 yang satu ini memperkatakan unsur-unsur sebagai ia menghadapi mereka, 1224 00:44:36,700 --> 00:44:39,290 tetapi kemudian ia mungkin perubahan perkara yang lebih untuk memberi ruang, 1225 00:44:39,290 --> 00:44:41,660 memasukkan unsur-unsur mana mereka berada. 1226 00:44:41,660 --> 00:44:45,330 >> Dan ini juga berakhir memberikan Keputusan akhir. Sekarang semua tiga daripada 1227 00:44:45,330 --> 00:44:46,490 berasa cukup cepat. 1228 00:44:46,490 --> 00:44:48,740 Dan sesungguhnya, saya berlari mereka pada klip yang cukup baik. 1229 00:44:48,740 --> 00:44:52,510 Tetapi asasnya, mereka semua cukup dahsyat, untuk bersikap jujur. 1230 00:44:52,510 --> 00:44:56,960 Semua algoritma ini setakat ini yang berjalan di O besar n kuasa dua 1231 00:44:56,960 --> 00:44:59,270 mengambil agak sedikit masa untuk menjalankan pada akhirnya. 1232 00:44:59,270 --> 00:45:01,920 >> Dan sesungguhnya, kita dapat melihat dan rasa ini akhir sekali 1233 00:45:01,920 --> 00:45:04,090 jika saya tarik demo ketiga dan terakhir ini. 1234 00:45:04,090 --> 00:45:05,840 Ini merupakan satu lagi visualisasi yang akan 1235 00:45:05,840 --> 00:45:08,500 untuk menunjukkan jenis gelembung di sebelah kiri, jenis pemilihan di tengah, 1236 00:45:08,500 --> 00:45:13,410 dan sesuatu, sebagai salah satu daripada kami tangan menimbulkan sebelum ini mencadangkan, 1237 00:45:13,410 --> 00:45:15,020 bergabung apapun di sebelah kanan. 1238 00:45:15,020 --> 00:45:16,937 A pecah dan perintah strategi di sebelah kanan. 1239 00:45:16,937 --> 00:45:19,520 Dan itu, sebenarnya, apa yang kita akan melihat pada hari Rabu. 1240 00:45:19,520 --> 00:45:21,990 Tetapi mari kita masa ini untuk dijalankan secara selari. 1241 00:45:21,990 --> 00:45:26,765 Ia adalah kira-kira jumlah yang sama elemen, semua berjalan pada masa yang sama. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble jenis vs pilihan jenis vs merge. 1244 00:45:34,440 --> 00:45:36,760 >> Kini, mereka semua berjalan dalam teori pada masa yang sama. 1245 00:45:36,760 --> 00:45:39,830 CPU sedang berjalan di kelajuan yang sama, tetapi anda 1246 00:45:39,830 --> 00:45:44,014 dapat merasakan bagaimana membosankan ini adalah dengan cepat akan menjadi, 1247 00:45:44,014 --> 00:45:45,930 dan betapa cepat ketika kita menyuntik sedikit minggu 1248 00:45:45,930 --> 00:45:49,330 algoritma sifar boleh kita mempercepatkan perkara. 1249 00:45:49,330 --> 00:45:51,760 >> Dan sekarang mari kita bandingkan ini dalam satu bentuk lepas. 1250 00:45:51,760 --> 00:45:55,710 Saya akan pergi ke hadapan ke laman web CS50, di mana 1251 00:45:55,710 --> 00:45:59,020 kami mempunyai pautan akhir ini untuk hari ini, di mana seseorang di internet 1252 00:45:59,020 --> 00:46:03,960 sila meletakkan bersama-sama video yang menangkap apa pengasingan yang berbeza 1253 00:46:03,960 --> 00:46:07,510 algoritma bunyi seperti. 1254 00:46:07,510 --> 00:46:09,577 Ini adalah jenis sisipan. 1255 00:46:09,577 --> 00:46:12,072 >> [Bip] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Di mana anda memohon frekuensi yang berdasarkan ketinggian bar bar. 1258 00:46:16,850 --> 00:46:19,826 Ini adalah jenis gelembung. 1259 00:46:19,826 --> 00:46:21,822 >> [Bip sesat] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Datang berikut is-- datang sehingga is-- pilihan jenis datang, 1262 00:46:45,774 --> 00:46:48,820 di mana lagi, kita memilih unsur terkecil yang akan datang, 1263 00:46:48,820 --> 00:46:51,820 dan kita dapat melihat ia berkembang dari kiri ke kanan. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Bergabung apapun, pemenang kami setakat hari ini. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Perhatikan bagaimana ia membahagikan perkara ke dalam [didengar] separuh dan pihak. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Jenis Gnome, yang kita tidak mempunyai bercakap tentang, dan mewujudkan visual 1270 00:47:21,660 --> 00:47:24,450 dan audally sedikit bentuk yang berbeza dan bunyi. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Pergi dan balik, membersihkan keadaan. 1273 00:47:30,160 --> 00:47:32,230 Juga menyemak heapsort di laman web ini lelaki itu. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Dan itu sahaja. 1276 00:47:36,810 --> 00:47:38,210 Kita akan lihat masa depan. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing DAN MUZIK] 1279 00:47:48,334 --> 00:50:24,839