1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [Bermain muzik] 3 00:00:10,800 --> 00:00:13,500 DAVID MALAN: Baiklah. 4 00:00:13,500 --> 00:00:14,670 Baiklah, selamat datang kembali. 5 00:00:14,670 --> 00:00:18,120 Jadi, ini adalah Minggu 4, permulaan itu, sudah. 6 00:00:18,120 --> 00:00:21,320 Dan anda akan ingat bahawa minggu lepas, kita meletakkan kod diperuntukkan untuk hanya sedikit 7 00:00:21,320 --> 00:00:24,240 dan kita mula bercakap lebih sedikit peringkat tinggi, kira-kira perkara-perkara seperti 8 00:00:24,240 --> 00:00:28,130 mencari dan menyusun, yang walaupun idea-idea yang agak mudah, adalah 9 00:00:28,130 --> 00:00:31,840 wakil kelas masalah anda akan mula untuk menyelesaikan terutamanya 10 00:00:31,840 --> 00:00:34,820 kerana anda mula berfikir tentang akhir projek dan penyelesaian yang menarik anda 11 00:00:34,820 --> 00:00:36,760 mungkin mempunyai masalah sebenar. 12 00:00:36,760 --> 00:00:39,490 Sekarang jenis buih adalah salah satu yang paling mudah algoritma itu, dan ia 13 00:00:39,490 --> 00:00:42,900 bekerja dengan mempunyai nombor-nombor kecil dalam senarai atau dalam pelbagai jenis 14 00:00:42,900 --> 00:00:46,530 buih mereka untuk sampai ke atas, dan jumlah yang besar bergerak dengan cara mereka turun ke 15 00:00:46,530 --> 00:00:47,930 akhir senarai itu. 16 00:00:47,930 --> 00:00:50,650 >> Dan ingat bahawa kita boleh menggambarkan gelembung yang amat sedikit 17 00:00:50,650 --> 00:00:52,310 sesuatu seperti ini. 18 00:00:52,310 --> 00:00:53,640 Jadi biarlah saya pergi ke hadapan dan klik Mula. 19 00:00:53,640 --> 00:00:55,350 Saya diprapilih jenis gelembung. 20 00:00:55,350 --> 00:00:58,920 Dan jika anda masih ingat bahawa biru tinggi garis mewakili nombor besar, kecil 21 00:00:58,920 --> 00:01:03,300 garis biru mewakili jumlah yang kecil, kerana kita pergi melalui ini sekali lagi dan lagi dan 22 00:01:03,300 --> 00:01:07,680 lagi, membandingkan dua bar di sebelah setiap lain dalam merah, kita akan menukar 23 00:01:07,680 --> 00:01:11,010 terbesar dan yang paling kecil jika mereka berada di luar perintah. 24 00:01:11,010 --> 00:01:14,150 >> Jadi ini akan pergi dan pergi dan pergi pada, dan anda akan melihat bahawa yang lebih besar 25 00:01:14,150 --> 00:01:16,700 unsur-unsur yang membuat cara mereka ke betul, dan unsur-unsur yang lebih kecil 26 00:01:16,700 --> 00:01:17,900 membuat jalan mereka ke kiri. 27 00:01:17,900 --> 00:01:21,380 Tetapi kita mula mengira kecekapan, yang 28 00:01:21,380 --> 00:01:22,970 kualiti algoritma ini. 29 00:01:22,970 --> 00:01:25,200 Dan kita berkata bahawa dalam yang paling teruk kes, algoritma ini mengambil 30 00:01:25,200 --> 00:01:27,940 kira-kira berapa banyak langkah-langkah? 31 00:01:27,940 --> 00:01:28,980 >> Jadi n kuasa dua. 32 00:01:28,980 --> 00:01:30,402 Dan apa yang n? 33 00:01:30,402 --> 00:01:31,650 >> PENONTON: Bilangan unsur-unsur. 34 00:01:31,650 --> 00:01:32,790 >> DAVID MALAN: Jadi n adalah beberapa elemen. 35 00:01:32,790 --> 00:01:33,730 Dan dengan itu kita akan melakukan ini kerap. 36 00:01:33,730 --> 00:01:36,650 Bila-bila masa kita mahu bercakap tentang saiz satu masalah atau saiz yang 37 00:01:36,650 --> 00:01:39,140 input, atau jumlah masa yang diperlukan untuk menghasilkan output, kita akan hanya 38 00:01:39,140 --> 00:01:41,610 umum apa sahaja input adalah seperti n. 39 00:01:41,610 --> 00:01:45,970 Jadi kembali dalam Minggu 0, bilangan muka surat di dalam buku telefon adalah n. 40 00:01:45,970 --> 00:01:47,550 Bilangan pelajar dalam bilik itu n. 41 00:01:47,550 --> 00:01:49,630 Jadi di sini, juga, kami sedang mengikuti corak itu. 42 00:01:49,630 --> 00:01:52,800 >> Sekarang n kuasa dua tidak begitu cepat, jadi kami cuba untuk melakukan yang lebih baik. 43 00:01:52,800 --> 00:01:55,970 Dan supaya kita melihat beberapa algoritma yang lain, antaranya 44 00:01:55,970 --> 00:01:57,690 adalah jenis pilihan. 45 00:01:57,690 --> 00:01:59,180 Jadi apapun pemilihan adalah sedikit berbeza. 46 00:01:59,180 --> 00:02:03,130 Ia adalah hampir mudah, saya berani mengatakan, di mana saya bermula pada permulaan 47 00:02:03,130 --> 00:02:06,740 senarai sukarelawan kami dan saya sekali lagi dan lagi dan lagi telah melalui 48 00:02:06,740 --> 00:02:10,060 senarai, memetik daripada yang paling kecil elemen pada satu masa dan meletakkan dia atau 49 00:02:10,060 --> 00:02:13,040 beliau pada awal senarai. 50 00:02:13,040 --> 00:02:16,410 >> Tetapi ini juga, apabila kita mula berfikir melalui matematik dan lebih besar 51 00:02:16,410 --> 00:02:19,860 gambar, berfikir tentang berapa kali Saya telah pergi ke belakang dan sebagainya dan belakang 52 00:02:19,860 --> 00:02:24,090 dan sebagainya, kita berkata dalam kes terburuk, jenis pilihan, juga, adalah apa? 53 00:02:24,090 --> 00:02:24,960 n kuasa dua. 54 00:02:24,960 --> 00:02:27,490 Kini di dunia sebenar, ia mungkin benar-benar menjadi sedikit lebih cepat. 55 00:02:27,490 --> 00:02:30,620 Kerana sekali lagi, saya tidak perlu menyimpan berundur apabila saya telah disusun yang 56 00:02:30,620 --> 00:02:31,880 unsur-unsur yang paling kecil. 57 00:02:31,880 --> 00:02:35,090 Tetapi jika kita berfikir tentang yang sangat besar n, dan jika anda jenis keluar melakukan matematik sebagai 58 00:02:35,090 --> 00:02:39,170 Saya di papan, dengan n kuasa dua tolak sesuatu, segala-galanya 59 00:02:39,170 --> 00:02:41,850 selain n kuasa dua, sekali n mendapat benar-benar besar, tidak 60 00:02:41,850 --> 00:02:42,850 benar-benar perkara yang banyak. 61 00:02:42,850 --> 00:02:45,470 Jadi sebagai saintis komputer, kita menyelesaikan satu menutup mata kepada yang lebih kecil 62 00:02:45,470 --> 00:02:49,220 faktor dan tumpuan hanya pada faktor dalam satu ungkapan yang akan membuat 63 00:02:49,220 --> 00:02:50,330 perbezaan terbesar. 64 00:02:50,330 --> 00:02:52,840 >> Nah, akhirnya, kita melihat pada jenis kemasukan. 65 00:02:52,840 --> 00:02:56,620 Dan ini adalah sama dalam semangat, tetapi bukannya melalui iterative dan 66 00:02:56,620 --> 00:03:01,250 pilih salah satu elemen yang paling kecil di masa, saya sebaliknya mengambil tangan saya 67 00:03:01,250 --> 00:03:04,070 telah diuruskan, dan saya membuat keputusan, semua betul, anda tergolong di sini. 68 00:03:04,070 --> 00:03:06,160 Kemudian saya berpindah ke elemen yang seterusnya dan memutuskan bahawa dia atau 69 00:03:06,160 --> 00:03:07,470 dia tergolong di sini. 70 00:03:07,470 --> 00:03:08,810 Dan kemudian saya berpindah dan pada. 71 00:03:08,810 --> 00:03:11,780 Dan saya mungkin kepada, sepanjang jalan, beralih lelaki ini untuk 72 00:03:11,780 --> 00:03:13,030 memberi ruang untuk mereka. 73 00:03:13,030 --> 00:03:16,880 Jadi yang jenis pembalikan mental satu jenis pilihan yang kita 74 00:03:16,880 --> 00:03:18,630 dipanggil jenis kemasukan. 75 00:03:18,630 --> 00:03:20,810 >> Jadi topik-topik ini berlaku dalam dunia sebenar. 76 00:03:20,810 --> 00:03:23,640 Hanya beberapa tahun yang lalu, apabila tertentu senator telah menjalankan untuk presiden, 77 00:03:23,640 --> 00:03:27,160 Eric Schmidt, pada masa itu Ketua Pegawai Eksekutif Google, sebenarnya mempunyai peluang 78 00:03:27,160 --> 00:03:28,040 menemubual beliau. 79 00:03:28,040 --> 00:03:32,010 Dan kita fikir kita akan berkongsi YouTube klip untuk anda di sini, jika kita boleh bertukar sehingga 80 00:03:32,010 --> 00:03:32,950 kelantangan. 81 00:03:32,950 --> 00:03:39,360 >> [MAIN SEMULA VIDEO] 82 00:03:39,360 --> 00:03:44,620 >> -Sekarang, Senator, anda berada di sini di Google, dan saya suka untuk berfikir presiden 83 00:03:44,620 --> 00:03:46,042 seperti temu duga kerja. 84 00:03:46,042 --> 00:03:47,770 >> [Ketawa] 85 00:03:47,770 --> 00:03:50,800 >> -Kini ia Adalah sukar untuk mendapatkan kerja sebagai presiden. 86 00:03:50,800 --> 00:03:52,480 Dan anda akan melalui menggigil sekarang. 87 00:03:52,480 --> 00:03:54,330 Ia juga sukar untuk mendapatkan pekerjaan di Google. 88 00:03:54,330 --> 00:03:59,610 Kami mempunyai soalan dan kita minta calon-calon kita soalan. 89 00:03:59,610 --> 00:04:02,250 Dan yang satu ini dari Larry Schwimmer. 90 00:04:02,250 --> 00:04:05,325 >> [Ketawa] 91 00:04:05,325 --> 00:04:06,400 -Kamu fikir saya bergurau? 92 00:04:06,400 --> 00:04:08,750 Ia adalah di sini. 93 00:04:08,750 --> 00:04:12,110 Apakah cara yang paling berkesan untuk menyelesaikan satu juta dua integer-bit? 94 00:04:12,110 --> 00:04:15,810 >> [Ketawa] 95 00:04:15,810 --> 00:04:18,260 >> -Well, uh - 96 00:04:18,260 --> 00:04:19,029 >> : Saya minta maaf. 97 00:04:19,029 --> 00:04:19,745 Mungkin kita perlu - 98 00:04:19,745 --> 00:04:21,000 >> -Tidak, tidak, tidak, tidak, tidak. 99 00:04:21,000 --> 00:04:21,470 >> -Itu bukan satu - 100 00:04:21,470 --> 00:04:22,185 OK. 101 00:04:22,185 --> 00:04:25,328 >> -Saya rasa jenis gelembung akan menjadi cara yang salah untuk pergi. 102 00:04:25,328 --> 00:04:26,792 >> [Ketawa] 103 00:04:26,792 --> 00:04:28,510 >> [Bersorak dan tepukan] 104 00:04:28,510 --> 00:04:31,211 >> -Ayuh, yang memberitahu dia ini? 105 00:04:31,211 --> 00:04:32,155 OK. 106 00:04:32,155 --> 00:04:33,350 >> [AKHIR VIDEO MAIN SEMULA] 107 00:04:33,350 --> 00:04:35,070 >> DAVID MALAN: Jadi ada anda mempunyai ia. 108 00:04:35,070 --> 00:04:39,600 Oleh itu, kita mula mengira ini berjalan kali, jadi untuk bercakap, dengan sesuatu 109 00:04:39,600 --> 00:04:43,480 dipanggil notasi asimptot, yang merupakan hanya merujuk kepada jenis kita beralih 110 00:04:43,480 --> 00:04:47,420 mata yang buta kepada faktor-faktor yang lebih kecil dan hanya melihat pada masa yang berjalan, 111 00:04:47,420 --> 00:04:51,250 prestasi ini algoritma, sebagai n mendapat benar-benar besar dari masa ke masa. 112 00:04:51,250 --> 00:04:55,110 Dan supaya kita diperkenalkan besar O. Dan besar O sesuatu yang diwakili sehingga kami menyangka bahawa 113 00:04:55,110 --> 00:04:57,000 sebagai satu terikat atas. 114 00:04:57,000 --> 00:04:59,570 Dan sebenarnya, Barry, kita boleh mengurangkan daripada mikrofon sedikit? 115 00:04:59,570 --> 00:05:01,040 >> Kami fikir ini adalah terikat atas. 116 00:05:01,040 --> 00:05:04,710 Begitu besar O n cara kuasa bahawa dalam kes terburuk, sesuatu seperti 117 00:05:04,710 --> 00:05:07,780 jenis pilihan akan mengambil n langkah persegi. 118 00:05:07,780 --> 00:05:10,310 Atau sesuatu seperti jenis kemasukan n akan langkah-langkah dua. 119 00:05:10,310 --> 00:05:15,150 Sekarang untuk sesuatu seperti memasukkan apapun, apa yang mana-mana yang paling teruk? 120 00:05:15,150 --> 00:05:18,200 Memandangkan pelbagai, apa yang paling teruk senario yang mungkin anda mungkin mendapati 121 00:05:18,200 --> 00:05:20,650 diri anda berhadapan dengan? 122 00:05:20,650 --> 00:05:21,860 >> Ia adalah benar-benar ke belakang, bukan? 123 00:05:21,860 --> 00:05:24,530 Kerana jika ia adalah benar-benar ke belakang, anda perlu melakukan banyak keseluruhan kerja. 124 00:05:24,530 --> 00:05:26,420 Kerana jika anda benar-benar ke belakang, anda akan mencari 125 00:05:26,420 --> 00:05:28,840 unsur terbesar di sini, walaupun ia tergolong di bawah sana. 126 00:05:28,840 --> 00:05:31,140 Jadi, anda akan berkata, semua betul, di masa ini dalam masa, anda tergolong di sini, 127 00:05:31,140 --> 00:05:32,310 jadi anda biarkan dia bersendirian. 128 00:05:32,310 --> 00:05:35,425 >> Kemudian anda sedar, oh, celaka, saya perlu bergerak elemen ini sedikit lebih kecil untuk 129 00:05:35,425 --> 00:05:36,470 di sebelah kiri anda. 130 00:05:36,470 --> 00:05:38,770 Kemudian saya perlu berbuat demikian lagi dan lagi dan lagi. 131 00:05:38,770 --> 00:05:41,410 Dan jika saya berjalan ke belakang dan sebagainya, anda akan menyusun daripada rasa prestasi 132 00:05:41,410 --> 00:05:45,540 algoritma itu, kerana saya sentiasa shuffling orang lain ke dalam 133 00:05:45,540 --> 00:05:46,510 pelbagai untuk memberi ruang untuk itu. 134 00:05:46,510 --> 00:05:47,750 Itulah kes yang paling teruk. 135 00:05:47,750 --> 00:05:48,570 >> Sebaliknya - 136 00:05:48,570 --> 00:05:50,320 dan ini adalah cliffhanger masa lalu - 137 00:05:50,320 --> 00:05:54,065 kita katakan bahawa jenis kemasukan merupakan omega apa? 138 00:05:54,065 --> 00:05:57,530 Apakah berjalan kes terbaik masa jenis kemasukan? 139 00:05:57,530 --> 00:05:58,520 Jadi ia sebenarnya n. 140 00:05:58,520 --> 00:06:00,980 Itu adalah kosong yang kami meninggalkan di papan masa lalu. 141 00:06:00,980 --> 00:06:03,160 >> Dan ia omega n kerana mengapa? 142 00:06:03,160 --> 00:06:06,630 Nah, dalam kes yang terbaik, apa yang jenis kemasukan akan diserahkan? 143 00:06:06,630 --> 00:06:09,830 Nah, senarai itu benar-benar disusun sudah, kerja-kerja yang minimum yang perlu dilakukan. 144 00:06:09,830 --> 00:06:12,460 Tetapi apa yang kemas mengenai jenis kemasukan ialah kerana ia bermula di sini dan 145 00:06:12,460 --> 00:06:15,340 memutuskan, oh, anda bilangan satu, anda tergolong di sini. 146 00:06:15,340 --> 00:06:16,970 Oh, apa nasib yang baik. 147 00:06:16,970 --> 00:06:17,740 >> Anda nombor dua. 148 00:06:17,740 --> 00:06:19,030 Anda juga tergolong di sini. 149 00:06:19,030 --> 00:06:21,010 Nombor tiga, lebih baik, anda tergolong di sini. 150 00:06:21,010 --> 00:06:25,210 Sebaik sahaja ia sampai ke akhir pseudokod senarai, setiap kemasukan jenis ini 151 00:06:25,210 --> 00:06:28,010 yang kita berjalan melalui lisan masa lalu, ia dilakukan. 152 00:06:28,010 --> 00:06:32,790 Tetapi jenis pilihan, sebaliknya, disimpan melakukan apa? 153 00:06:32,790 --> 00:06:35,260 >> Terus berjalan melalui senarai lagi dan lagi dan lagi. 154 00:06:35,260 --> 00:06:39,160 Kerana wawasan utama terdapat hanya sekali anda telah melihat semua jalan ke 155 00:06:39,160 --> 00:06:42,500 akhir senarai yang anda boleh yakin elemen yang dipilih adalah 156 00:06:42,500 --> 00:06:45,560 sesungguhnya unsur kini terkecil. 157 00:06:45,560 --> 00:06:48,920 Jadi ini yang berbeza mental model akhir sehingga menghasilkan beberapa sangat dunia sebenar 158 00:06:48,920 --> 00:06:53,130 perbezaan untuk kita, serta ini perbezaan asimptot teori. 159 00:06:53,130 --> 00:06:56,910 >> Jadi untuk menggulung, maka, besar O n kuasa, kita telah melihat apa-apa beberapa 160 00:06:56,910 --> 00:06:58,350 algoritma setakat ini. 161 00:06:58,350 --> 00:06:59,580 Big O n? 162 00:06:59,580 --> 00:07:02,870 Apa algoritma yang boleh dikatakan besar O n? 163 00:07:02,870 --> 00:07:06,930 Dalam kes terburuk, ia mengambil masa beberapa linear langkah. 164 00:07:06,930 --> 00:07:07,810 >> OK, carian linear. 165 00:07:07,810 --> 00:07:10,470 Dan dalam kes paling teruk, di mana adalah unsur yang anda cari apabila 166 00:07:10,470 --> 00:07:12,950 memohon carian linear? 167 00:07:12,950 --> 00:07:14,680 >> OK, dalam kes paling teruk, ia tidak walaupun di sana. 168 00:07:14,680 --> 00:07:17,000 Atau dalam kes kedua paling teruk, ia sepanjang jalan pada akhirnya, yang merupakan 169 00:07:17,000 --> 00:07:18,880 campur-atau-tolak perbezaan satu langkah. 170 00:07:18,880 --> 00:07:21,180 Jadi, pada akhir hari, kita boleh mengatakan ia adalah linear. 171 00:07:21,180 --> 00:07:23,910 Big O n akan menjadi carian linear, kerana dalam kes yang paling teruk, 172 00:07:23,910 --> 00:07:26,610 unsur tidak walaupun di sana atau ia sepanjang jalan pada akhir. 173 00:07:26,610 --> 00:07:29,370 >> Nah, besar O log n. 174 00:07:29,370 --> 00:07:32,760 Kami tidak bercakap secara terperinci mengenai ini, tetapi kita telah melihat sebelum ini. 175 00:07:32,760 --> 00:07:36,840 Apa yang wujud dalam apa yang dipanggil logaritma masa, di mana-mana yang paling teruk? 176 00:07:36,840 --> 00:07:38,500 >> Ya, carian supaya binari. 177 00:07:38,500 --> 00:07:42,930 Dan carian binari dalam kes terburuk mungkin mempunyai elemen di suatu tempat di 178 00:07:42,930 --> 00:07:45,640 tengah-tengah, atau di tempat di dalam array. 179 00:07:45,640 --> 00:07:48,040 Tetapi anda hanya mendapati ia sebaik sahaja anda membahagikan senarai pada separuh, dalam 180 00:07:48,040 --> 00:07:48,940 separuh, pada separuh, pada separuh. 181 00:07:48,940 --> 00:07:50,200 Dan kemudian Voilà, ia adalah di sana. 182 00:07:50,200 --> 00:07:52,500 Atau sekali lagi, kes paling teruk, ia tidak walaupun di sana. 183 00:07:52,500 --> 00:07:56,770 Tetapi anda tidak tahu bahawa ia tidak ada sehingga anda mencapai bentuk yang terakhir 184 00:07:56,770 --> 00:08:00,470 bawah kebanyakan unsur dengan mengurangkan separuh dan mengurangkan separuh dan mengurangkan separuh. 185 00:08:00,470 --> 00:08:01,400 >> Big O 1. 186 00:08:01,400 --> 00:08:03,540 Jadi kita boleh besar O 2, besar O 3. 187 00:08:03,540 --> 00:08:06,260 Bila-bila masa yang anda mahu hanya sebilangan yang berterusan, kita hanya menyelesaikan hanya memudahkan 188 00:08:06,260 --> 00:08:07,280 yang sebesar O 1. 189 00:08:07,280 --> 00:08:10,440 Walaupun jika realistik, ia mengambil masa 2 atau 100 langkah-langkah, jika ia adalah 190 00:08:10,440 --> 00:08:13,680 bilangan berterusan langkah-langkah, kita hanya mengatakan O besar daripada 1. 191 00:08:13,680 --> 00:08:15,930 Apa algoritma itu dalam besar O 1? 192 00:08:15,930 --> 00:08:18,350 >> PENONTON: Mencari panjang pembolehubah a. 193 00:08:18,350 --> 00:08:21,090 >> DAVID MALAN: Mencari panjang pembolehubah? 194 00:08:21,090 --> 00:08:23,870 >> PENONTON: Tidak, panjang jika ia sudah disusun. 195 00:08:23,870 --> 00:08:24,160 >> DAVID MALAN: Baik. 196 00:08:24,160 --> 00:08:27,850 OK, jadi mencari panjang sesuatu jika panjang sesuatu itu, seperti 197 00:08:27,850 --> 00:08:30,020 array, disimpan di dalam beberapa berubah-ubah. 198 00:08:30,020 --> 00:08:33,380 Kerana anda hanya boleh membaca pembolehubah, atau mencetak berubah-ubah, atau 199 00:08:33,380 --> 00:08:34,960 hanya umumnya mengakses berubah-ubah itu. 200 00:08:34,960 --> 00:08:37,299 Dan Voilà, yang mengambil masa yang berterusan. 201 00:08:37,299 --> 00:08:38,909 >> Sebaliknya, berfikir kembali ke awal. 202 00:08:38,909 --> 00:08:42,460 Fikirkan kembali untuk minggu pertama C, memanggil hanya printf dan mencetak 203 00:08:42,460 --> 00:08:46,240 sesuatu pada skrin boleh dikatakan masa yang berterusan, kerana ia hanya mengambil 204 00:08:46,240 --> 00:08:50,880 beberapa nombor kitaran CPU untuk menunjukkan bahawa teks pada skrin. 205 00:08:50,880 --> 00:08:52,720 Atau tunggu - bukan? 206 00:08:52,720 --> 00:08:56,430 Bagaimana lagi kita mungkin model prestasi printf? 207 00:08:56,430 --> 00:09:00,420 Seseorang ingin untuk tidak bersetuju, bahawa mungkin ia bukan masa benar-benar berterusan? 208 00:09:00,420 --> 00:09:03,600 Dalam apa rasa mungkin printf berjalan masa, sebenarnya mencetak tali di 209 00:09:03,600 --> 00:09:05,580 skrin, sesuatu selain daripada berterusan. 210 00:09:05,580 --> 00:09:07,860 >> PENONTON: [didengar]. 211 00:09:07,860 --> 00:09:08,230 >> DAVID MALAN: Ya. 212 00:09:08,230 --> 00:09:09,300 Jadi ia bergantung kepada perspektif kita. 213 00:09:09,300 --> 00:09:13,390 Jika kita benar-benar berfikir daripada input kepada printf sebagai tali, dan 214 00:09:13,390 --> 00:09:16,380 Oleh itu, kita mengukur saiz yang input oleh panjangnya - jadi mari kita memanggilnya 215 00:09:16,380 --> 00:09:17,780 panjang yang n juga - 216 00:09:17,780 --> 00:09:21,990 boleh dikatakan, printf itu sendiri besar O n kerana ia akan mengambil langkah-langkah yang anda n 217 00:09:21,990 --> 00:09:24,750 untuk mencetak setiap orang n watak-watak, yang paling mungkin. 218 00:09:24,750 --> 00:09:27,730 Sekurang-kurangnya ke tahap yang kita anggap bahawa mungkin ia menggunakan untuk gelung 219 00:09:27,730 --> 00:09:28,560 di bawah hood. 220 00:09:28,560 --> 00:09:30,860 >> Tetapi kita perlu melihat bahawa kod untuk memahami dengan lebih baik. 221 00:09:30,860 --> 00:09:33,650 Dan sesungguhnya, apabila anda semua mula menganalisis algoritma anda sendiri, anda akan 222 00:09:33,650 --> 00:09:34,900 benar-benar berbuat demikian. 223 00:09:34,900 --> 00:09:37,765 Jenis biji mata kod anda dan berfikir tentang - semua hak, saya mempunyai gelung ini 224 00:09:37,765 --> 00:09:41,870 di sini atau saya mempunyai gelung bersarang di sini, yang akan melakukan perkara-perkara n n kali, 225 00:09:41,870 --> 00:09:46,050 dan anda boleh menyelesaikan sebab cara anda melalui kod, walaupun ia 226 00:09:46,050 --> 00:09:47,980 pseudokod dan tidak kod sebenar. 227 00:09:47,980 --> 00:09:49,730 >> Jadi apa yang kira-kira omega n kuasa dua? 228 00:09:49,730 --> 00:09:53,582 Apakah algoritma yang dalam yang terbaik kes, masih mengambil langkah-langkah n kuasa dua? 229 00:09:53,582 --> 00:09:54,014 Ya? 230 00:09:54,014 --> 00:09:54,880 >> PENONTON: [didengar]. 231 00:09:54,880 --> 00:09:55,900 >> DAVID MALAN: jenis pemilihan Jadi. 232 00:09:55,900 --> 00:09:59,150 Kerana dalam masalah yang benar-benar dikurangkan kepada hakikat bahawa sekali lagi, saya tidak tahu 233 00:09:59,150 --> 00:10:02,600 Saya dapati yang paling kecil semasa sehingga Saya telah memeriksa semua elemen-elemen darn. 234 00:10:02,600 --> 00:10:08,050 Jadi omega, berkata, n, kita hanya datang dengan satu. 235 00:10:08,050 --> 00:10:09,300 Jenis kemasukan. 236 00:10:09,300 --> 00:10:12,370 Jika senarai yang berlaku diselesaikan pun, dalam kes ini, kita hanya perlu 237 00:10:12,370 --> 00:10:15,090 untuk membuat satu pas melaluinya, di mana titik kita pasti. 238 00:10:15,090 --> 00:10:17,890 Dan kemudian yang boleh dikatakan menjadi linear, yang pasti. 239 00:10:17,890 --> 00:10:20,570 >> Bagaimana pula dengan omega 1? 240 00:10:20,570 --> 00:10:23,790 Apa, dalam kes yang terbaik, mungkin mengambil beberapa langkah-langkah yang berterusan? 241 00:10:23,790 --> 00:10:27,220 Carian linear Jadi, jika anda hanya mendapatkan bertuah dan elemen yang anda cari 242 00:10:27,220 --> 00:10:31,000 tepat pada awal senarai, jika itu di mana anda mula anda 243 00:10:31,000 --> 00:10:33,070 linear traversal senarai itu. 244 00:10:33,070 --> 00:10:35,180 >> Dan ini adalah benar daripada beberapa perkara. 245 00:10:35,180 --> 00:10:37,660 Sebagai contoh, walaupun binari carian omega daripada 1. 246 00:10:37,660 --> 00:10:40,310 Kerana apa yang jika anda mendapat benar-benar darn bertuah dan berbau-dab di tengah-tengah 247 00:10:40,310 --> 00:10:42,950 pelbagai anda adalah bilangan yang anda cari? 248 00:10:42,950 --> 00:10:45,730 Jadi, anda boleh mendapatkan bertuah di sana, juga. 249 00:10:45,730 --> 00:10:49,190 >> Yang ini, akhirnya, omega n log n. 250 00:10:49,190 --> 00:10:52,573 Jadi n log n, kita tidak benar-benar bercakap tentang lagi, tetapi - 251 00:10:52,573 --> 00:10:53,300 >> PENONTON: Gabung apapun? 252 00:10:53,300 --> 00:10:53,960 >> DAVID MALAN: jenis Gabung. 253 00:10:53,960 --> 00:10:56,920 Itu adalah cliffhanger masa lalu, di mana kami mencadangkan, dan kita menunjukkan 254 00:10:56,920 --> 00:10:58,600 visual, bahawa terdapat algoritma. 255 00:10:58,600 --> 00:11:02,470 Dan bergabung jenis hanya satu itu algoritma yang asasnya lebih cepat 256 00:11:02,470 --> 00:11:03,450 daripada beberapa lelaki lain. 257 00:11:03,450 --> 00:11:07,800 Malah, bergabung pendek bukan sahaja di kes terbaik n n log, yang paling teruk 258 00:11:07,800 --> 00:11:09,460 kes n n log. 259 00:11:09,460 --> 00:11:14,540 Dan apabila anda mempunyai kebetulan ini omega dan besar O menjadi perkara yang sama? 260 00:11:14,540 --> 00:11:17,310 Kita sebenarnya boleh menggambarkan bahawa apa yang dipanggil theta, walaupun ia adalah satu 261 00:11:17,310 --> 00:11:18,220 sedikit kurang biasa. 262 00:11:18,220 --> 00:11:21,730 Tetapi itu hanya bermakna kedua-dua batas, dalam kes ini, adalah sama. 263 00:11:21,730 --> 00:11:25,770 >> Jadi bergabung apapun, apakah ini benar-benar mendidih ke untuk kita? 264 00:11:25,770 --> 00:11:27,000 Well, ingat motivasi. 265 00:11:27,000 --> 00:11:30,340 Biar saya tarik sehingga animasi lain yang kita tidak melihat pada masa lalu. 266 00:11:30,340 --> 00:11:33,390 Yang ini, idea yang sama, tetapi ia sedikit lebih besar. 267 00:11:33,390 --> 00:11:36,160 Dan saya akan pergi ke hadapan dan menunjukkan pertama - kami mempunyai jenis kemasukan pada 268 00:11:36,160 --> 00:11:39,410 atas sebelah kiri, maka jenis pemilihan, jenis gelembung, beberapa jenis lain - 269 00:11:39,410 --> 00:11:42,670 shell dan cepat - bahawa kita tidak bercakap kira-kira, dan timbunan dan bergabung jenis. 270 00:11:42,670 --> 00:11:47,090 >> Jadi sekurang-kurangnya cuba untuk memberi tumpuan mata anda pada tiga teratas di sebelah kiri dan kemudian 271 00:11:47,090 --> 00:11:49,120 bergabung jenis apabila saya klik ini arrow hijau. 272 00:11:49,120 --> 00:11:51,900 Tetapi saya akan memberitahu semua mereka berjalan, hanya untuk memberi anda rasa kepelbagaian 273 00:11:51,900 --> 00:11:53,980 algoritma yang wujud di dunia. 274 00:11:53,980 --> 00:11:56,180 Saya akan membiarkan jangka ini hanya beberapa saat. 275 00:11:56,180 --> 00:11:59,640 Dan jika anda memberi tumpuan mata anda - memilih satu algoritma, memberi tumpuan kepada ia untuk hanya 276 00:11:59,640 --> 00:12:02,970 saat - anda akan mula melihat corak yang ia melaksanakan. 277 00:12:02,970 --> 00:12:04,530 >> Gabung jenis, notis, dilakukan. 278 00:12:04,530 --> 00:12:06,430 Jenis timbunan, jenis cepat, shell - 279 00:12:06,430 --> 00:12:09,480 jadi ia seolah-olah kita memperkenalkan tiga algoritma yang paling teruk minggu lepas. 280 00:12:09,480 --> 00:12:12,960 Tetapi itu adalah baik bahawa kita di sini hari ini untuk melihat merge jenis, yang merupakan salah satu 281 00:12:12,960 --> 00:12:16,500 orang-orang yang lebih mudah adalah untuk melihat, walaupun walaupun ia mungkin akan bengkok fikiran anda 282 00:12:16,500 --> 00:12:17,490 hanya sedikit. 283 00:12:17,490 --> 00:12:21,130 Di sini kita dapat melihat betapa banyak jenis pilihan menghisap. 284 00:12:21,130 --> 00:12:24,600 >> Tetapi di sebelah flip, ia benar-benar mudah untuk dilaksanakan. 285 00:12:24,600 --> 00:12:28,160 Dan mungkin untuk P Set 3, itu salah satu daripada algoritma anda memilih untuk melaksanakan 286 00:12:28,160 --> 00:12:28,960 untuk edisi standard. 287 00:12:28,960 --> 00:12:30,970 Betul-betul halus, sempurna betul. 288 00:12:30,970 --> 00:12:35,210 >> Tetapi sekali lagi, sebagai n mendapat besar, jika anda memilih untuk melaksanakan algoritma yang lebih cepat 289 00:12:35,210 --> 00:12:39,020 suka bergabung apapun, kemungkinan berada dalam yang lebih besar dan input yang lebih besar, kod anda hanya 290 00:12:39,020 --> 00:12:39,800 akan berjalan lebih cepat. 291 00:12:39,800 --> 00:12:41,090 Laman web anda akan bekerja lebih baik. 292 00:12:41,090 --> 00:12:42,650 Pengguna anda akan menjadi lebih bahagia. 293 00:12:42,650 --> 00:12:45,280 Dan begitu juga ada kesan-kesan ini sebenarnya memberi 294 00:12:45,280 --> 00:12:47,350 kami sedikit lebih berfikir. 295 00:12:47,350 --> 00:12:49,990 >> Jadi mari kita lihat apa yang bergabung apapun yang sebenarnya semua tentang. 296 00:12:49,990 --> 00:12:52,992 Perkara yang sejuk adalah yang bergabung apapun hanya ini. 297 00:12:52,992 --> 00:12:56,300 Ini adalah, sekali lagi, apa yang kita telah dipanggil pseudokod, makhluk pseudokod 298 00:12:56,300 --> 00:12:57,720 Sintaksis Bahasa Inggeris-seperti. 299 00:12:57,720 --> 00:12:59,890 Dan kesederhanaan adalah jenis yang menarik. 300 00:12:59,890 --> 00:13:02,840 >> Maka pada input n elemen - supaya hanya bermakna, di sini adalah array. 301 00:13:02,840 --> 00:13:04,000 Ia mempunyai perkara n di dalamnya. 302 00:13:04,000 --> 00:13:05,370 Itu semua kita katakan di sana. 303 00:13:05,370 --> 00:13:07,560 >> Jika n adalah kurang daripada 2, kembali. 304 00:13:07,560 --> 00:13:08,640 Jadi itu hanya kes remeh. 305 00:13:08,640 --> 00:13:12,580 Jika n adalah kurang daripada 2, maka jelas ia 1 atau 0, di mana perkara yang 306 00:13:12,580 --> 00:13:14,780 sudah disusun atau tidak wujud, jadi hanya kembali. 307 00:13:14,780 --> 00:13:15,900 Tiada apa-apa yang perlu dilakukan. 308 00:13:15,900 --> 00:13:18,360 Jadi itu adalah satu kes yang mudah untuk memetik off. 309 00:13:18,360 --> 00:13:20,110 >> Yang lain, kami mempunyai tiga langkah. 310 00:13:20,110 --> 00:13:23,650 Menyelesaikan separuh kiri elemen, jenis separuh yang betul unsur-unsur, 311 00:13:23,650 --> 00:13:26,650 dan kemudian menggabungkan bahagian disusun. 312 00:13:26,650 --> 00:13:29,400 Apa yang menarik di sini ialah Saya jenis punting, bukan? 313 00:13:29,400 --> 00:13:32,300 Ada jenis definisi pekeliling untuk algoritma ini. 314 00:13:32,300 --> 00:13:35,986 Dalam apa rasa adalah algoritma ini yang pekeliling definisi? 315 00:13:35,986 --> 00:13:37,850 >> PENONTON: [didengar]. 316 00:13:37,850 --> 00:13:41,670 >> DAVID MALAN: Ya, algoritma sorting saya, dua langkah-langkah yang "jenis 317 00:13:41,670 --> 00:13:44,640 sesuatu. "Dan supaya menimbulkan soalan, baik, apa yang saya akan menggunakan 318 00:13:44,640 --> 00:13:46,460 untuk menyelesaikan separuh kiri dan separuh yang betul? 319 00:13:46,460 --> 00:13:49,600 Dan kecantikan di sini ialah bahawa walaupun sekali lagi, ini adalah-lentur minda 320 00:13:49,600 --> 00:13:54,030 sebahagian yang berpotensi, anda boleh menggunakan sama algoritma untuk menyelesaikan separuh kiri. 321 00:13:54,030 --> 00:13:54,700 >> Tetapi tunggu satu minit. 322 00:13:54,700 --> 00:13:57,070 Apabila anda diberitahu untuk menyusun separuh kiri, apakah dua 323 00:13:57,070 --> 00:13:58,240 langkah-langkah yang akan datang? 324 00:13:58,240 --> 00:14:00,550 Kami akan menyelesaikan separuh kiri separuh kiri dan kanan 325 00:14:00,550 --> 00:14:01,420 separuh daripada separuh kiri. 326 00:14:01,420 --> 00:14:04,430 Damn, bagaimana saya boleh menyelesaikan kedua-dua bahagian, atau pihak, sekarang? 327 00:14:04,430 --> 00:14:05,260 >> Tetapi itu OK. 328 00:14:05,260 --> 00:14:07,830 Kami mempunyai algoritma sorting di sini. 329 00:14:07,830 --> 00:14:10,660 Dan walaupun anda mungkin bimbang sama pertama ini adalah jenis yang tidak terhad 330 00:14:10,660 --> 00:14:12,780 gelung, ia adalah satu kitaran yang tidak pernah akan berakhir - ia akan 331 00:14:12,780 --> 00:14:15,770 akhir sekali apa yang berlaku? 332 00:14:15,770 --> 00:14:16,970 Setelah n adalah kurang daripada 2. 333 00:14:16,970 --> 00:14:19,180 Yang akhirnya akan berlaku, kerana jika anda menyimpan dan mengurangkan separuh 334 00:14:19,180 --> 00:14:23,020 mengurangkan separuh dalam mengurangkan separuh bahagian ini, pasti akhirnya anda akan berakhir 335 00:14:23,020 --> 00:14:25,350 dengan hanya 1 atau 0 elemen. 336 00:14:25,350 --> 00:14:28,500 Di mana titik, algoritma ini kata anda selesai. 337 00:14:28,500 --> 00:14:31,020 >> Jadi sihir sebenar dalam ini algoritma seolah-olah berada di dalam 338 00:14:31,020 --> 00:14:33,470 langkah terakhir, bercantum. 339 00:14:33,470 --> 00:14:37,190 Itulah idea yang mudah hanya penggabungan dua perkara, itulah apa yang akhirnya akan 340 00:14:37,190 --> 00:14:40,920 untuk membolehkan kita untuk menyelesaikan pelbagai, katakan, lapan elemen. 341 00:14:40,920 --> 00:14:44,410 Jadi saya mempunyai lapan lebih bola tekanan sehingga di sini, lapan keping kertas, dan satu 342 00:14:44,410 --> 00:14:45,500 Google Kaca - 343 00:14:45,500 --> 00:14:46,140 yang saya dapat menyimpan. 344 00:14:46,140 --> 00:14:46,960 >> [Ketawa] 345 00:14:46,960 --> 00:14:48,970 >> DAVID MALAN: Jika kita boleh mengambil lapan sukarelawan, dan mari kita lihat jika kita boleh 346 00:14:48,970 --> 00:14:51,430 bermain ini keluar, jadi. 347 00:14:51,430 --> 00:14:52,500 Wow, OK. 348 00:14:52,500 --> 00:14:53,565 Sains komputer semakin menyeronokkan. 349 00:14:53,565 --> 00:14:54,320 Baiklah. 350 00:14:54,320 --> 00:14:57,770 Jadi bagaimana pula anda tiga, tangan terbesar di sana. 351 00:14:57,770 --> 00:14:58,580 Empat di belakang. 352 00:14:58,580 --> 00:15:02,220 Dan bagaimana pula kita akan adakah anda tiga berturut-turut ini? 353 00:15:02,220 --> 00:15:03,390 Dan empat di hadapan. 354 00:15:03,390 --> 00:15:04,920 Jadi anda lapan, datang ke atas. 355 00:15:04,920 --> 00:15:12,060 >> [Ketawa] 356 00:15:12,060 --> 00:15:13,450 >> DAVID MALAN: Saya sebenarnya tidak pasti apa yang ia adalah. 357 00:15:13,450 --> 00:15:14,810 Adakah ia bola tekanan? 358 00:15:14,810 --> 00:15:16,510 Lampu meja? 359 00:15:16,510 --> 00:15:18,650 Bahan? 360 00:15:18,650 --> 00:15:19,680 Internet? 361 00:15:19,680 --> 00:15:20,160 >> OK. 362 00:15:20,160 --> 00:15:21,310 Jadi datang di atas. 363 00:15:21,310 --> 00:15:22,310 Siapa yang akan suka - 364 00:15:22,310 --> 00:15:23,570 terus datang. 365 00:15:23,570 --> 00:15:24,240 Mari kita lihat. 366 00:15:24,240 --> 00:15:26,460 Dan ini meletakkan anda dalam location - 367 00:15:26,460 --> 00:15:27,940 anda berada di lokasi satu. 368 00:15:27,940 --> 00:15:28,670 Uh-oh, tunggu satu minit. 369 00:15:28,670 --> 00:15:30,760 1, 2, 3, 4, 5, 6, 7 - oh, baik. 370 00:15:30,760 --> 00:15:31,310 Baiklah, kita yang baik. 371 00:15:31,310 --> 00:15:35,130 Baiklah, supaya semua orang mempunyai tempat duduk, tetapi tidak pada kaca Google. 372 00:15:35,130 --> 00:15:36,475 Biar saya beratur ini. 373 00:15:36,475 --> 00:15:37,115 Apa nama anda? 374 00:15:37,115 --> 00:15:37,440 >> Michelle: Michelle. 375 00:15:37,440 --> 00:15:38,090 >> DAVID MALAN: Michelle? 376 00:15:38,090 --> 00:15:42,000 Baiklah, anda boleh kelihatan seperti geek, jika itu OK. 377 00:15:42,000 --> 00:15:44,625 Well, saya lakukan juga, saya rasa, hanya untuk seketika. 378 00:15:44,625 --> 00:15:45,875 Baiklah, siap sedia. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Kami telah cuba untuk tampil dengan menggunakan kes Google Glass, dan kami 381 00:15:50,950 --> 00:15:53,750 fikir ia akan menjadi seronok untuk hanya melakukan ini apabila orang di atas pentas. 382 00:15:53,750 --> 00:15:57,120 Kami akan mencatat dunia dari perspektif mereka. 383 00:15:57,120 --> 00:15:58,410 Baiklah. 384 00:15:58,410 --> 00:15:59,830 Tidak mungkin apa yang Google dimaksudkan. 385 00:15:59,830 --> 00:16:02,260 Baiklah, jika anda tidak keberatan memakai ini untuk minit janggal akan datang, 386 00:16:02,260 --> 00:16:03,150 yang akan menjadi indah. 387 00:16:03,150 --> 00:16:08,620 >> Baiklah, jadi kita ada di sini pelbagai unsur-unsur, dan lokasi itu, sebagai satu 388 00:16:08,620 --> 00:16:11,480 keping kertas dalam orang ' tangan, kini Unsorted. 389 00:16:11,480 --> 00:16:12,050 >> Michelle: Oh, yang begitu pelik. 390 00:16:12,050 --> 00:16:12,810 >> DAVID MALAN: Ia cukup banyak rawak. 391 00:16:12,810 --> 00:16:15,760 Dan hanya seketika, kita akan cuba untuk melaksanakan bergabung bersama-sama jenis 392 00:16:15,760 --> 00:16:17,950 dan melihat di mana bahawa wawasan utama adalah. 393 00:16:17,950 --> 00:16:21,970 Dan helah di sini dengan merge jenis adalah sesuatu yang kita tidak dianggap yet. 394 00:16:21,970 --> 00:16:24,030 Kami benar-benar memerlukan beberapa ruang tambahan. 395 00:16:24,030 --> 00:16:26,650 Jadi apa yang akan menjadi terutamanya menarik mengenai ini adalah bahawa 396 00:16:26,650 --> 00:16:29,270 lelaki akan bergerak sedikit bit, kerana saya akan menganggap bahawa 397 00:16:29,270 --> 00:16:31,880 terdapat pelbagai tambahan ruang, berkata, di belakang mereka. 398 00:16:31,880 --> 00:16:34,570 >> Jadi, jika mereka berada di belakang kerusi mereka, itulah pelbagai menengah. 399 00:16:34,570 --> 00:16:36,960 Jika mereka sedang duduk di sini, itu array utama. 400 00:16:36,960 --> 00:16:40,170 Tetapi ini adalah satu sumber yang kita ada tidak dimanfaatkan setakat ini dengan gelembung 401 00:16:40,170 --> 00:16:42,040 jenis, dengan jenis pemilihan, dengan jenis kemasukan. 402 00:16:42,040 --> 00:16:44,600 Ingat minggu lepas, semua orang hanya jenis shuffled di tempat. 403 00:16:44,600 --> 00:16:46,840 Mereka tidak menggunakan apa-apa memori tambahan. 404 00:16:46,840 --> 00:16:49,310 Kami membuat ruang untuk rakyat dengan bergerak orang di sekeliling. 405 00:16:49,310 --> 00:16:50,580 >> Jadi ini adalah satu wawasan utama, juga. 406 00:16:50,580 --> 00:16:53,410 Ada ini trade-off, secara umum di sains komputer, sumber. 407 00:16:53,410 --> 00:16:55,800 Jika anda mahu mempercepatkan sesuatu seperti masa, anda akan 408 00:16:55,800 --> 00:16:56,900 perlu membayar harga. 409 00:16:56,900 --> 00:17:00,750 Dan salah satu daripada mereka harga adalah sangat kerap ruang, jumlah memori atau keras 410 00:17:00,750 --> 00:17:01,700 ruang cakera yang anda gunakan. 411 00:17:01,700 --> 00:17:03,640 Atau, terus-terang, jumlah masa pengaturcara. 412 00:17:03,640 --> 00:17:06,700 Berapa banyak masa ia akan membawa anda, manusia, untuk benar-benar melaksanakan lebih banyak 413 00:17:06,700 --> 00:17:07,829 algoritma rumit. 414 00:17:07,829 --> 00:17:09,760 Tetapi hari ini, perdagangan-off adalah masa dan ruang. 415 00:17:09,760 --> 00:17:11,930 >> Jadi, jika anda semua hanya boleh memegang sehingga anda nombor supaya kita boleh melihat bahawa anda 416 00:17:11,930 --> 00:17:15,839 memang sepadan 4, 2, 6, 1, 3, 7, 8. 417 00:17:15,839 --> 00:17:16,599 Excellent. 418 00:17:16,599 --> 00:17:19,520 Jadi, saya akan cuba untuk mengatur perkara, jika anda semua boleh hanya 419 00:17:19,520 --> 00:17:21,800 mengikuti jejak saya di sini. 420 00:17:21,800 --> 00:17:26,650 >> Oleh itu, saya akan melaksanakan, pertama, langkah pertama pseudokod, yang merupakan 421 00:17:26,650 --> 00:17:29,440 input n unsur, jika n kurang daripada 2, kemudian kembali. 422 00:17:29,440 --> 00:17:31,370 Jelas sekali, yang tidak memohon, jadi kita bergerak ke atas. 423 00:17:31,370 --> 00:17:33,340 Jadi menyusun separuh kiri unsur-unsur. 424 00:17:33,340 --> 00:17:36,220 Jadi ini bermakna saya akan memberi tumpuan saya perhatian untuk hanya seketika atas 425 00:17:36,220 --> 00:17:37,310 empat lelaki di sini. 426 00:17:37,310 --> 00:17:39,774 Baiklah, apa yang saya lakukan seterusnya? 427 00:17:39,774 --> 00:17:40,570 >> PENONTON: Susun separuh kiri. 428 00:17:40,570 --> 00:17:42,780 >> DAVID MALAN: Jadi sekarang saya perlu menyelesaikan separuh kiri lelaki ini. 429 00:17:42,780 --> 00:17:45,580 Kerana sekali lagi, anggap diri anda matlamat adalah untuk menyelesaikan separuh kiri. 430 00:17:45,580 --> 00:17:46,440 Bagaimana anda berbuat demikian? 431 00:17:46,440 --> 00:17:49,140 Hanya ikut arahan, walaupun walaupun kita lakukan sekali lagi. 432 00:17:49,140 --> 00:17:50,160 Jadi menyusun separuh kiri. 433 00:17:50,160 --> 00:17:52,030 Sekarang saya mengasingkan kedua-dua lelaki. 434 00:17:52,030 --> 00:17:53,563 Apa yang datang seterusnya? 435 00:17:53,563 --> 00:17:54,510 >> PENONTON: Susun separuh kiri. 436 00:17:54,510 --> 00:17:55,460 >> DAVID MALAN: Susun separuh kiri. 437 00:17:55,460 --> 00:18:00,680 Jadi sekarang ini, kerusi ini di sini, adalah senarai saiz 1. 438 00:18:00,680 --> 00:18:01,365 Dan apa nama lagi? 439 00:18:01,365 --> 00:18:02,390 >> PRINCESS DAISY: Princess Daisy. 440 00:18:02,390 --> 00:18:03,690 >> DAVID MALAN: Princess Daisy di sini. 441 00:18:03,690 --> 00:18:07,470 Dan supaya dia sudah disusun, kerana senarai adalah saiz 1. 442 00:18:07,470 --> 00:18:09,490 Apa yang saya lakukan seterusnya? 443 00:18:09,490 --> 00:18:13,680 OK, kembali, kerana senarai itu adalah saiz 1, yang kurang daripada 2. 444 00:18:13,680 --> 00:18:14,320 Kemudian apa langkah seterusnya? 445 00:18:14,320 --> 00:18:17,490 Dan sekarang anda perlu jenis mundur dalam fikiran anda. 446 00:18:17,490 --> 00:18:19,340 >> Menyelesaikan separuh yang betul, yang - 447 00:18:19,340 --> 00:18:19,570 apa nama anda? 448 00:18:19,570 --> 00:18:20,220 >> LINDA: Linda. 449 00:18:20,220 --> 00:18:20,980 >> DAVID MALAN: Linda. 450 00:18:20,980 --> 00:18:23,210 Dan supaya apa yang kita lakukan sekarang bahawa kami mempunyai senarai saiz 1? 451 00:18:23,210 --> 00:18:24,440 >> PENONTON: Return. 452 00:18:24,440 --> 00:18:24,760 >> DAVID MALAN: Berhati-hati. 453 00:18:24,760 --> 00:18:29,540 Kita kembali pertama, dan kini ketiga langkah - dan jika saya jenis menggambarkan ia dengan 454 00:18:29,540 --> 00:18:33,490 memeluk dua kerusi sekarang, sekarang saya perlu menggabungkan kedua-dua elemen. 455 00:18:33,490 --> 00:18:35,530 Jadi sekarang malangnya, unsur-unsur berada di luar perintah. 456 00:18:35,530 --> 00:18:39,920 Tetapi itu di mana proses penggabungan mula mendapat menarik. 457 00:18:39,920 --> 00:18:42,410 >> Jadi, jika anda semua boleh berdiri hanya seketika, saya akan memerlukan anda, dalam 458 00:18:42,410 --> 00:18:44,170 masa, untuk melangkah di belakang kerusi anda. 459 00:18:44,170 --> 00:18:46,480 Dan jika Linda, kerana 2 adalah lebih kecil daripada 4, mengapa tidak 460 00:18:46,480 --> 00:18:48,130 anda datang sekitar pertama? 461 00:18:48,130 --> 00:18:48,690 Tinggal di sana. 462 00:18:48,690 --> 00:18:50,520 Jadi Linda, anda datang sekitar pertama. 463 00:18:50,520 --> 00:18:53,820 >> Sekarang dalam realiti jika ia hanya array kita hanya boleh bergerak beliau dalam masa nyata 464 00:18:53,820 --> 00:18:55,360 dari kerusi ini ke tempat ini. 465 00:18:55,360 --> 00:18:57,770 Cuba bayangkan, yang mengambil beberapa berterusan beberapa langkah 1. 466 00:18:57,770 --> 00:18:58,480 Dan sekarang - 467 00:18:58,480 --> 00:19:01,490 tetapi kita perlu meletakkan anda dalam lokasi pertama di sini. 468 00:19:01,490 --> 00:19:03,930 >> Dan sekarang jika anda boleh datang sekitar, juga, kita akan 469 00:19:03,930 --> 00:19:06,300 berada di lokasi dua. 470 00:19:06,300 --> 00:19:09,120 Dan walaupun ini berasa seperti ia adalah mengambil sedikit masa, apa yang baik sekarang ialah 471 00:19:09,120 --> 00:19:14,710 bahawa separuh kiri separuh kiri kini disusun. 472 00:19:14,710 --> 00:19:18,010 Jadi apa langkah seterusnya, jika kita kini memundurkan lagi dalam cerita? 473 00:19:18,010 --> 00:19:18,980 >> PENONTON: separuh kanan. 474 00:19:18,980 --> 00:19:19,900 >> DAVID MALAN: Susun separuh betul. 475 00:19:19,900 --> 00:19:21,320 Jadi anda lelaki itu mempunyai untuk melakukan ini, juga. 476 00:19:21,320 --> 00:19:23,510 Jadi, jika anda boleh berdiri hanya untuk seketika? 477 00:19:23,510 --> 00:19:25,192 Dan apa nama anda? 478 00:19:25,192 --> 00:19:25,540 >> JESS: Jess. 479 00:19:25,540 --> 00:19:25,870 >> DAVID MALAN: Jess. 480 00:19:25,870 --> 00:19:29,720 OK, jadi Jess kini kiri separuh daripada separuh yang betul. 481 00:19:29,720 --> 00:19:31,400 Dan supaya dia adalah senarai saiz 1. 482 00:19:31,400 --> 00:19:32,380 Dia jelas disusun. 483 00:19:32,380 --> 00:19:33,070 Dan nama anda lagi? 484 00:19:33,070 --> 00:19:33,630 >> Michelle: Michelle. 485 00:19:33,630 --> 00:19:35,340 >> DAVID MALAN: Michelle adalah jelas senarai saiz 1. 486 00:19:35,340 --> 00:19:36,050 Dia sudah disusun. 487 00:19:36,050 --> 00:19:38,690 Jadi sekarang keajaiban berlaku, proses penggabungan. 488 00:19:38,690 --> 00:19:39,790 Jadi siapa yang akan datang terlebih dahulu? 489 00:19:39,790 --> 00:19:41,560 Jelas Michelle. 490 00:19:41,560 --> 00:19:43,280 Jadi, jika anda boleh datang sekitar belakang. 491 00:19:43,280 --> 00:19:47,090 Ruang yang kita ada untuk dia sekarang tepat di belakang kerusi ini di sini. 492 00:19:47,090 --> 00:19:51,580 Dan sekarang jika anda boleh kembali juga, kita kini mempunyai, jelas, dua 493 00:19:51,580 --> 00:19:53,810 bahagian, setiap saiz 2 - 494 00:19:53,810 --> 00:19:57,090 dan hanya demi gambaran, jika anda boleh membuat sedikit ruang - 495 00:19:57,090 --> 00:19:59,780 salah satu ditinggalkan separuh di sini, satu setengah di sini. 496 00:19:59,780 --> 00:20:01,160 >> Memundurkan lagi dalam cerita. 497 00:20:01,160 --> 00:20:02,270 Apakah langkah yang akan datang? 498 00:20:02,270 --> 00:20:03,030 >> PENONTON: Gabung. 499 00:20:03,030 --> 00:20:04,160 >> DAVID MALAN: Jadi sekarang kita perlu bergabung. 500 00:20:04,160 --> 00:20:07,490 Jadi OK, jadi sekarang, bersyukur, kita hanya dibebaskan empat kerusi. 501 00:20:07,490 --> 00:20:11,480 Oleh itu, kita telah menggunakan dua kali ganda memori banyak, tetapi kita boleh memberi flip-flopping antara 502 00:20:11,480 --> 00:20:12,330 dua tatasusunan. 503 00:20:12,330 --> 00:20:14,190 Jadi yang nombor akan datang terlebih dahulu? 504 00:20:14,190 --> 00:20:14,850 Jadi Michelle, jelas. 505 00:20:14,850 --> 00:20:16,680 Jadi datang sekitar dan mengambil tempat duduk anda di sini. 506 00:20:16,680 --> 00:20:19,120 Dan kemudian nombor 2 jelas seterusnya, jadi anda datang ke sini. 507 00:20:19,120 --> 00:20:21,520 Nombor 4, nombor 6. 508 00:20:21,520 --> 00:20:23,390 Dan sekali lagi, walaupun terdapat sedikit berjalan kaki yang terlibat, 509 00:20:23,390 --> 00:20:26,010 benar-benar, ini boleh berlaku serta-merta, dengan bergerak satu - 510 00:20:26,010 --> 00:20:26,880 OK, juga dimainkan. 511 00:20:26,880 --> 00:20:28,350 >> [Ketawa] 512 00:20:28,350 --> 00:20:29,680 >> DAVID MALAN: Dan kini kami dalam bentuk yang agak baik. 513 00:20:29,680 --> 00:20:34,910 Separuh kiri keseluruhan input kini telah disusun. 514 00:20:34,910 --> 00:20:37,370 Baiklah, jadi ini lelaki mempunyai kelebihan saya - 515 00:20:37,370 --> 00:20:40,340 bagaimana ia berakhir dengan semua gadis-gadis di kiri dan semua anak lelaki di sebelah kanan? 516 00:20:40,340 --> 00:20:42,450 >> OK, jadi lelaki 'berubah sekarang. 517 00:20:42,450 --> 00:20:44,680 Jadi, saya tidak akan berjalan anda melalui langkah-langkah ini. 518 00:20:44,680 --> 00:20:46,550 Kita akan melihat jika kita boleh memohon semula pseudokod yang sama. 519 00:20:46,550 --> 00:20:50,050 Jika anda mahu pergi ke hadapan dan berdiri, dan anda semua, biarlah saya memberikan mikrofon itu. 520 00:20:50,050 --> 00:20:52,990 Lihat jika anda tidak boleh meniru apa kita lakukan di sini pada 521 00:20:52,990 --> 00:20:53,880 hujung lain senarai. 522 00:20:53,880 --> 00:20:59,530 Siapa yang memerlukan untuk bercakap pertama, berdasarkan algoritma? 523 00:20:59,530 --> 00:21:03,210 Jadi menjelaskan apa yang anda lakukan sebelum anda membuat apa-apa pergerakan kaki. 524 00:21:03,210 --> 00:21:05,930 >> SPEAKER 1: Baiklah, jadi sejak Saya separuh kiri 525 00:21:05,930 --> 00:21:07,790 separuh kiri, saya kembali. 526 00:21:07,790 --> 00:21:08,730 Betul? 527 00:21:08,730 --> 00:21:09,250 >> DAVID MALAN: Baik. 528 00:21:09,250 --> 00:21:10,350 >> SPEAKER 1: Dan kemudian - 529 00:21:10,350 --> 00:21:11,800 >> DAVID MALAN: Siapa yang mikrofon pergi ke depan? 530 00:21:11,800 --> 00:21:12,920 >> SPEAKER 1: bilangan Next. 531 00:21:12,920 --> 00:21:14,720 >> SPEAKER 2: Jadi saya separuh betul separuh kiri 532 00:21:14,720 --> 00:21:17,830 separuh kiri, dan saya kembali. 533 00:21:17,830 --> 00:21:18,050 >> DAVID MALAN: Baik. 534 00:21:18,050 --> 00:21:18,550 Anda kembali. 535 00:21:18,550 --> 00:21:21,855 Jadi sekarang apa yang sehingga seterusnya untuk kamu berdua? 536 00:21:21,855 --> 00:21:23,740 >> SPEAKER 2: Kami mahu melihat siapa yang lebih kecil. 537 00:21:23,740 --> 00:21:24,200 >> DAVID MALAN: Tepat sekali. 538 00:21:24,200 --> 00:21:24,940 Kami mahu bergabung. 539 00:21:24,940 --> 00:21:27,590 Ruang yang kita akan gunakan untuk bergabung anda ke dalam, walaupun mereka 540 00:21:27,590 --> 00:21:30,250 jelas sudah disusun, kita akan mengikuti algoritma yang sama. 541 00:21:30,250 --> 00:21:31,560 Jadi yang pergi di belakang pertama? 542 00:21:31,560 --> 00:21:35,720 Jadi 3, dan kemudian 7. 543 00:21:35,720 --> 00:21:38,570 Dan kini mikrofon pergi kepada lelaki, OK? 544 00:21:38,570 --> 00:21:43,590 >> SPEAKER 3: Jadi saya separuh kanan separuh kiri, dan n saya adalah kurang daripada 545 00:21:43,590 --> 00:21:45,048 1, jadi saya hanya akan lulus - 546 00:21:45,048 --> 00:21:46,380 >> DAVID MALAN: Baik. 547 00:21:46,380 --> 00:21:49,450 >> SPEAKER 4: Saya separuh kanan bahagian kanan separuh yang betul, dan saya 548 00:21:49,450 --> 00:21:51,740 juga satu orang, jadi saya akan kembali. 549 00:21:51,740 --> 00:21:52,990 Jadi sekarang kita bergabung. 550 00:21:52,990 --> 00:21:55,140 551 00:21:55,140 --> 00:21:56,150 >> SPEAKER 3: Jadi kita kembali. 552 00:21:56,150 --> 00:21:57,160 >> DAVID MALAN: Jadi anda pergi ke belakang. 553 00:21:57,160 --> 00:21:59,200 Jadi 5 dulu, maka 8. 554 00:21:59,200 --> 00:22:01,240 Dan sekarang penonton, yang merupakan melangkah kita perlu sekarang memundurkan 555 00:22:01,240 --> 00:22:02,200 kembali ke dalam fikiran kita? 556 00:22:02,200 --> 00:22:02,940 >> PENONTON: Gabung. 557 00:22:02,940 --> 00:22:07,270 >> DAVID MALAN: Menggabungkan separuh kiri dan kanan separuh daripada separuh kiri asal. 558 00:22:07,270 --> 00:22:08,840 Jadi sekarang - 559 00:22:08,840 --> 00:22:10,520 dan hanya untuk membuat ini jelas, membuat sedikit ruang 560 00:22:10,520 --> 00:22:11,690 di antara kamu dua lelaki. 561 00:22:11,690 --> 00:22:13,800 Jadi sekarang adalah dua senarai, kiri dan kanan. 562 00:22:13,800 --> 00:22:18,320 Jadi bagaimana kita kini bergabung kamu ke barisan hadapan tempat duduk lagi? 563 00:22:18,320 --> 00:22:19,600 >> 3 dulu. 564 00:22:19,600 --> 00:22:20,850 Kemudian 5, jelas. 565 00:22:20,850 --> 00:22:23,110 566 00:22:23,110 --> 00:22:27,330 Kemudian 7, dan sekarang 8. 567 00:22:27,330 --> 00:22:28,710 OK, dan kini kita? 568 00:22:28,710 --> 00:22:29,650 >> PENONTON: Tidak dilakukan. 569 00:22:29,650 --> 00:22:32,440 >> DAVID MALAN: Tidak dilakukan, kerana jelas, ada satu langkah yang tinggal. 570 00:22:32,440 --> 00:22:35,720 Tetapi sekali lagi, sebab saya menggunakan ini istilah seperti "gulung semula dalam fikiran anda," 571 00:22:35,720 --> 00:22:37,160 ia adalah kerana itu benar-benar apa yang berlaku. 572 00:22:37,160 --> 00:22:39,610 Kita akan melalui semua langkah-langkah ini, tetapi kami jenis berhenti untuk 573 00:22:39,610 --> 00:22:42,480 masa, menyelam jauh ke dalam algoritma, berhenti seketika, 574 00:22:42,480 --> 00:22:45,840 menyelam jauh ke dalam algoritma, dan sekarang kita perlu menyusun satu gulung dalam kami 575 00:22:45,840 --> 00:22:49,430 fikiran dan membatalkan semua lapisan bahawa kita telah jenis ditunda. 576 00:22:49,430 --> 00:22:51,790 >> Jadi sekarang kita mempunyai dua senarai saiz 4. 577 00:22:51,790 --> 00:22:54,790 Jika anda semua boleh berdiri kali terakhir dan membuat sedikit ruang di sini untuk 578 00:22:54,790 --> 00:22:57,230 membuat jelas bahawa ini adalah kiri separuh daripada yang asal, 579 00:22:57,230 --> 00:22:58,620 bahagian kanan yang asal. 580 00:22:58,620 --> 00:23:01,060 Siapa bilangan pertama yang kita perlu tarik ke belakang? 581 00:23:01,060 --> 00:23:01,870 Michelle, sudah tentu. 582 00:23:01,870 --> 00:23:03,230 >> Jadi kita meletakkan Michelle sini. 583 00:23:03,230 --> 00:23:05,080 Dan yang mempunyai nombor 2? 584 00:23:05,080 --> 00:23:06,440 Nombor 2 datang di belakang juga. 585 00:23:06,440 --> 00:23:07,800 Bilangan 3? 586 00:23:07,800 --> 00:23:08,510 Excellent. 587 00:23:08,510 --> 00:23:16,570 Nombor 4, 5 nombor, nombor 6, nombor 7 dan nombor 8. 588 00:23:16,570 --> 00:23:18,850 >> OK, jadi ia berasa seperti banyak langkah-langkah, yang pasti. 589 00:23:18,850 --> 00:23:22,390 Tetapi sekarang mari kita lihat jika kita tidak boleh mengesahkan jenis intuitif bahawa ini 590 00:23:22,390 --> 00:23:26,190 algoritma asas, terutamanya n mendapat benar-benar besar, seperti yang kita telah melihat 591 00:23:26,190 --> 00:23:29,170 dengan animasi, adalah asasnya lebih cepat. 592 00:23:29,170 --> 00:23:33,400 Jadi saya menuntut algoritma ini, yang paling teruk kes dan juga di mana-mana yang terbaik, 593 00:23:33,400 --> 00:23:36,160 adalah besar O n kali log n. 594 00:23:36,160 --> 00:23:39,160 Iaitu, terdapat beberapa aspek ini algoritma yang mengambil langkah-langkah n, tetapi 595 00:23:39,160 --> 00:23:43,110 ada aspek lain di suatu tempat di lelaran itu, gelung itu, bahawa 596 00:23:43,110 --> 00:23:44,410 mengambil langkah-langkah yang log n. 597 00:23:44,410 --> 00:23:49,154 Bolehkah kita meletakkan jari kami pada apa yang mereka dua nombor adalah merujuk kepada? 598 00:23:49,154 --> 00:23:51,320 Nah, di mana - 599 00:23:51,320 --> 00:23:54,160 Dari mana asalnya mikrofon pergi? 600 00:23:54,160 --> 00:23:58,660 >> SPEAKER 1: Adakah yang log n menjadi memecahkan kita kepada dua - 601 00:23:58,660 --> 00:23:59,630 terbahagi kepada dua, pada asasnya. 602 00:23:59,630 --> 00:24:00,120 >> DAVID MALAN: Tepat sekali. 603 00:24:00,120 --> 00:24:03,000 Mana-mana masa yang kita lihat dalam mana-mana algoritma itu setakat ini, telah ada corak 604 00:24:03,000 --> 00:24:04,200 membahagikan, membahagikan, membahagikan. 605 00:24:04,200 --> 00:24:05,700 Dan ia biasanya dikurangkan kepada sesuatu yang 606 00:24:05,700 --> 00:24:07,100 logaritma, log asas 2. 607 00:24:07,100 --> 00:24:10,180 Tetapi ia benar-benar boleh menjadi apa-apa, tetapi log asas 2. 608 00:24:10,180 --> 00:24:11,330 >> Sekarang apa tentang n? 609 00:24:11,330 --> 00:24:14,550 Saya boleh melihat bahawa kita jenis dibahagikan anda lelaki - dibahagikan anda, dibahagikan anda, 610 00:24:14,550 --> 00:24:15,910 dibahagikan anda, dibahagikan anda. 611 00:24:15,910 --> 00:24:18,760 Di manakah akhirnya datang? 612 00:24:18,760 --> 00:24:19,810 >> Jadi ia adalah penggabungan. 613 00:24:19,810 --> 00:24:20,610 Kerana berfikir mengenainya. 614 00:24:20,610 --> 00:24:25,420 Apabila anda menggabungkan lapan orang bersama-sama, di mana separuh daripada mereka adalah satu set empat 615 00:24:25,420 --> 00:24:27,770 dan separuh lagi adalah satu lagi set empat, bagaimana anda pergi 616 00:24:27,770 --> 00:24:28,820 melakukan penggabungan? 617 00:24:28,820 --> 00:24:30,830 Nah, kalian melakukannya agak intuitif. 618 00:24:30,830 --> 00:24:34,140 >> Tetapi jika saya bukan melakukannya lebih sedikit teratur, saya mungkin telah menunjuk ke arah 619 00:24:34,140 --> 00:24:38,090 orang yang paling kiri pertama dengan kiri saya tangan, menunjuk pada orang yang paling kiri 620 00:24:38,090 --> 00:24:42,080 itu setengah dengan tangan kanan saya, dan hanya kemudian berjalan melalui 621 00:24:42,080 --> 00:24:46,990 senarai, menghala ke arah elemen terkecil setiap kali, menggerakkan jari saya ke atas dan 622 00:24:46,990 --> 00:24:48,970 lebih seperti yang diperlukan seluruh senarai. 623 00:24:48,970 --> 00:24:51,890 Tetapi apa yang penting tentang penggabungan ini proses adalah saya membandingkan kedua-pasangan 624 00:24:51,890 --> 00:24:53,460 unsur-unsur. 625 00:24:53,460 --> 00:24:57,270 Dari separuh kanan dan di sebelah kiri setengah, saya tidak pernah berundur. 626 00:24:57,270 --> 00:25:00,570 >> Jadi bergabung itu sendiri mengambil tidak lebih daripada n langkah. 627 00:25:00,570 --> 00:25:03,250 Dan berapa kali pula saya mempunyai untuk berbuat demikian bergabung? 628 00:25:03,250 --> 00:25:07,150 Well, tidak lebih daripada n, dan kita hanya melihat bahawa dengan bergabung akhir. 629 00:25:07,150 --> 00:25:13,120 Dan jadi jika anda melakukan sesuatu yang mengambil log n langkah n kali, atau sebaliknya, 630 00:25:13,120 --> 00:25:15,210 ia akan memberikan kita n kali log n. 631 00:25:15,210 --> 00:25:16,310 >> Dan mengapa ini yang lebih baik? 632 00:25:16,310 --> 00:25:19,600 Nah, jika kita sudah tahu bahawa log n adalah lebih baik daripada n - betul? 633 00:25:19,600 --> 00:25:22,590 Kita lihat dalam carian binari, buku telefon Sebagai contoh, log n memang 634 00:25:22,590 --> 00:25:23,760 lebih baik daripada linear. 635 00:25:23,760 --> 00:25:28,420 Ini bermakna n kali log n pasti lebih baik daripada n masa lain 636 00:25:28,420 --> 00:25:30,390 n, AKA n kuasa dua. 637 00:25:30,390 --> 00:25:32,400 Dan itulah yang kita akhirnya rasa. 638 00:25:32,400 --> 00:25:34,928 >> Pusingan begitu besar tepukan, jika kita boleh, bagi lelaki ini. 639 00:25:34,928 --> 00:25:38,920 >> [Tepuk tangan] 640 00:25:38,920 --> 00:25:41,550 >> DAVID MALAN: Dan hadiah perpisahan anda - anda boleh menyimpan nombor, 641 00:25:41,550 --> 00:25:44,010 jika anda ingin. 642 00:25:44,010 --> 00:25:45,620 Dan hadiah perpisahan anda, seperti biasa. 643 00:25:45,620 --> 00:25:47,290 Oh, dan kami akan menghantar kepada anda rakaman itu, Michelle. 644 00:25:47,290 --> 00:25:48,343 Terima kasih. 645 00:25:48,343 --> 00:25:49,250 Baiklah. 646 00:25:49,250 --> 00:25:50,400 Membantu diri anda dengan bola tekanan. 647 00:25:50,400 --> 00:25:54,110 >> Dan biarlah saya tarik sehingga, dalam masa yang sama, rakan kami Rob Bowden untuk menawarkan 648 00:25:54,110 --> 00:25:59,520 perspektif yang agak berbeza mengenai perkara ini, kerana anda boleh berfikir tentang ini 649 00:25:59,520 --> 00:26:01,280 langkah-langkah yang berlaku dalam yang agak cara yang berbeza. 650 00:26:01,280 --> 00:26:04,750 Malah, set-up untuk apa yang kira-kira Rob untuk menunjukkan kepada kita menganggap bahawa kita telah 651 00:26:04,750 --> 00:26:09,030 telah dilakukan yang membahagikan daripada senarai yang besar kepada lapan senarai kecil, 652 00:26:09,030 --> 00:26:10,570 setiap saiz 1. 653 00:26:10,570 --> 00:26:13,350 >> Jadi kita sedang berubah pseudokod suatu sedikit hanya untuk menyelesaikan daripada mendapatkan di 654 00:26:13,350 --> 00:26:15,320 idea teras bagaimana kerja-kerja bercantum. 655 00:26:15,320 --> 00:26:17,600 Tetapi masa menjalankan apa dia kira-kira untuk melakukan masih 656 00:26:17,600 --> 00:26:19,110 akan menjadi sama. 657 00:26:19,110 --> 00:26:23,540 Dan sekali lagi, set-up di sini adalah bahawa dia bermula dengan lapan senarai saiz 1. 658 00:26:23,540 --> 00:26:27,730 Jadi, anda telah terlepas bahagian di mana dia sebenarnya yang telah dilakukan log n, log n, log n 659 00:26:27,730 --> 00:26:31,205 membahagikan input. 660 00:26:31,205 --> 00:26:32,120 >> [MAIN SEMULA VIDEO] 661 00:26:32,120 --> 00:26:33,615 >> -Itu sahaja untuk satu langkah. 662 00:26:33,615 --> 00:26:38,270 Untuk langkah dua, berkali-kali bergabung pasang senarai. 663 00:26:38,270 --> 00:26:39,210 >> DAVID MALAN: Hm. 664 00:26:39,210 --> 00:26:41,270 Hanya audio akan datang daripada komputer saya. 665 00:26:41,270 --> 00:26:42,520 Mari kita cuba ini lagi. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Hanya sewenang-wenangnya memilih yang - sekarang kita mempunyai empat senarai. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 Belajar sebelum ini. 670 00:26:52,120 --> 00:26:53,040 >> DAVID MALAN: Ada kita pergi. 671 00:26:53,040 --> 00:27:00,510 >> Menghimpunkan-108 dan 15, kita akhirnya dengan senarai 15, 108. 672 00:27:00,510 --> 00:27:07,170 Menghimpunkan 50 dan 4, kita berakhir dengan 4, 50. 673 00:27:07,170 --> 00:27:12,990 Penggabungan 8 dan 42, kita berakhir dengan 8, 42. 674 00:27:12,990 --> 00:27:19,970 Dan penggabungan 23 dan 16, kita berakhir dengan 16, 23. 675 00:27:19,970 --> 00:27:23,270 >> Sekarang semua senarai kami saiz 2. 676 00:27:23,270 --> 00:27:26,690 Perhatikan bahawa setiap empat senarai yang disusun. 677 00:27:26,690 --> 00:27:29,450 Oleh itu, kita boleh mula bergabung pasang senarai lagi. 678 00:27:29,450 --> 00:27:38,420 Menghimpunkan 15 dan 108 dan 4 dan 50, kita pertama mengambil masa 4, maka 15, maka 679 00:27:38,420 --> 00:27:41,500 50, maka 108. 680 00:27:41,500 --> 00:27:50,610 Penggabungan 8, 42 dan 16, 23, kita mula-mula mengambil 8, maka 16, maka 23, 681 00:27:50,610 --> 00:27:52,700 maka 42. 682 00:27:52,700 --> 00:27:57,600 >> Jadi sekarang kita mempunyai hanya dua senarai saiz 4, setiap yang disusun. 683 00:27:57,600 --> 00:28:01,170 Jadi sekarang kita menggabungkan kedua-dua senarai. 684 00:28:01,170 --> 00:28:11,835 Pertama, kita mengambil masa 4, maka kita mengambil 8, maka kita mengambil 15, kemudian 16, kemudian 685 00:28:11,835 --> 00:28:19,456 23, kemudian 42, kemudian 50, kemudian 108. 686 00:28:19,456 --> 00:28:19,872 >> [AKHIR VIDEO MAIN SEMULA] 687 00:28:19,872 --> 00:28:23,430 >> DAVID MALAN: Sekali lagi, notis, dia tidak pernah menyentuh cawan yang diberikan lebih daripada satu masa 688 00:28:23,430 --> 00:28:24,860 selepas mara di luar itu. 689 00:28:24,860 --> 00:28:26,200 Jadi dia tidak pernah mengulangi. 690 00:28:26,200 --> 00:28:29,850 Jadi dia sentiasa bergerak ke tepi, dan di mana kita mendapat n kami. 691 00:28:29,850 --> 00:28:33,290 >> Mengapa tidak membiarkan saya tarik sehingga satu animasi yang kita lihat sebelum ini, tetapi kali ini 692 00:28:33,290 --> 00:28:35,110 hanya menumpukan pada merge jenis. 693 00:28:35,110 --> 00:28:38,030 Biar saya pergi ke hadapan dan zum di atas ini di sini. 694 00:28:38,030 --> 00:28:42,530 Pertama izinkan saya memilih input rawak, membesarkan ini, dan anda boleh menyusun daripada melihat 695 00:28:42,530 --> 00:28:46,600 apa yang kita mengambil untuk diberikan, sebelum ini, bergabung jenis sebenarnya lakukan. 696 00:28:46,600 --> 00:28:50,330 >> Jadi melihat bahawa anda mendapatkan ini bahagian atau pihak ini atau ini eighths daripada 697 00:28:50,330 --> 00:28:53,140 masalah yang tiba-tiba mula mengambil keadaan yang baik. 698 00:28:53,140 --> 00:28:57,070 Dan kemudian akhirnya, anda lihat di akhir sangat yang bam, 699 00:28:57,070 --> 00:28:58,860 semuanya digabungkan bersama-sama. 700 00:28:58,860 --> 00:29:01,690 >> Jadi ini adalah hanya tiga berbeza mengambil idea yang sama. 701 00:29:01,690 --> 00:29:05,980 Tetapi pandangan utama, seperti jurang dan menakluk di dalam kelas yang pertama, 702 00:29:05,980 --> 00:29:10,640 adalah bahawa kita memutuskan untuk entah bagaimana membahagikan masalah ini menjadi sesuatu yang besar, ke dalam 703 00:29:10,640 --> 00:29:14,760 sesuatu jenis sama dalam semangat, tetapi lebih kecil dan lebih kecil dan lebih kecil 704 00:29:14,760 --> 00:29:15,660 dan lebih kecil. 705 00:29:15,660 --> 00:29:18,420 >> Kini satu lagi cara yang menyeronokkan untuk menyusun daripada berfikir kira-kira ini, walaupun ia bukan 706 00:29:18,420 --> 00:29:20,520 akan memberi anda intuitif sama pemahaman, adalah 707 00:29:20,520 --> 00:29:21,640 animasi berikut. 708 00:29:21,640 --> 00:29:25,400 Jadi ini adalah satu video seseorang meletakkan bersama-sama yang berkaitan yang berbeza 709 00:29:25,400 --> 00:29:29,970 bunyi dengan pelbagai operasi untuk jenis kemasukan, untuk bergabung jenis, dan 710 00:29:29,970 --> 00:29:31,150 untuk beberapa orang lain. 711 00:29:31,150 --> 00:29:32,330 Jadi, dalam masa, saya akan melanda Play. 712 00:29:32,330 --> 00:29:33,600 Ia kira-kira satu minit panjang. 713 00:29:33,600 --> 00:29:37,410 Dan walaupun anda masih boleh melihat corak berlaku, kali ini anda boleh 714 00:29:37,410 --> 00:29:41,420 juga mendengar bagaimana algoritma adalah melaksanakan berbeza dan dengan 715 00:29:41,420 --> 00:29:43,950 corak yang agak berbeza. 716 00:29:43,950 --> 00:29:45,830 >> Ini adalah jenis kemasukan. 717 00:29:45,830 --> 00:29:50,400 >> [TONES DITAYANGKAN] 718 00:29:50,400 --> 00:29:52,400 >> DAVID MALAN: Ia sekali lagi cuba untuk memasukkan setiap elemen 719 00:29:52,400 --> 00:29:52,900 ke mana ia tergolong. 720 00:29:52,900 --> 00:29:54,628 Ini adalah jenis gelembung. 721 00:29:54,628 --> 00:30:10,097 >> [TONES DITAYANGKAN] 722 00:30:10,097 --> 00:30:13,630 >> DAVID MALAN: Dan anda boleh menyusun satu rasa bagaimana agak sedikit bekerja ia melakukan 723 00:30:13,630 --> 00:30:15,834 pada setiap langkah. 724 00:30:15,834 --> 00:30:20,470 Ini adalah apa yang tediousness bunyi seperti. 725 00:30:20,470 --> 00:30:21,472 >> [TONES DITAYANGKAN] 726 00:30:21,472 --> 00:30:25,222 >> DAVID MALAN: Ini adalah jenis pilihan, di mana kita pilih unsur yang kita mahu dengan 727 00:30:25,222 --> 00:30:28,845 melalui sekali lagi dan lagi dan lagi dan meletakkan ia pada permulaan. 728 00:30:28,845 --> 00:30:37,674 >> [TONES DITAYANGKAN] 729 00:30:37,674 --> 00:30:43,970 >> DAVID MALAN: Ini adalah bergabung jenis, yang anda benar-benar boleh mula rasa. 730 00:30:43,970 --> 00:30:51,810 >> [TONES DITAYANGKAN] 731 00:30:51,810 --> 00:30:54,770 >> [Ketawa] 732 00:30:54,770 --> 00:30:58,395 >> DAVID MALAN: Sesuatu dipanggil gnome jenis, yang mana kami tidak melihat. 733 00:30:58,395 --> 00:31:13,630 >> [TONES DITAYANGKAN] 734 00:31:13,630 --> 00:31:17,910 >> DAVID MALAN: Jadi biarlah saya lihat, sekarang, terganggu kerana anda adalah diharapkan oleh 735 00:31:17,910 --> 00:31:21,110 muzik, jika saya boleh tergelincir sedikit sedikit matematik di sini. 736 00:31:21,110 --> 00:31:24,850 Jadi ada cara yang keempat yang kita boleh berfikir tentang apa yang ia bermaksud 737 00:31:24,850 --> 00:31:29,210 fungsi untuk lebih cepat daripada orang-orang yang bahawa kami telah dilihat sebelum ini. 738 00:31:29,210 --> 00:31:32,470 Dan jika anda datang pada kursus dari latar belakang matematik, anda 739 00:31:32,470 --> 00:31:36,030 sebenarnya tahu mungkin sudah bahawa anda boleh menampar tempoh pada teknik ini - 740 00:31:36,030 --> 00:31:40,400 iaitu rekursi, fungsi yang entah bagaimana panggilan sendiri. 741 00:31:40,400 --> 00:31:44,780 >> Dan sekali lagi, ingat bahawa jenis merge pseudokod adalah rekursi dalam erti kata 742 00:31:44,780 --> 00:31:48,460 bahawa salah satu langkah-langkah merge jenis ini adalah untuk memanggil jenis - 743 00:31:48,460 --> 00:31:49,740 yang, sendiri. 744 00:31:49,740 --> 00:31:52,480 Tetapi bersyukur, kerana kita disimpan memanggil jenis, atau bergabung jenis, 745 00:31:52,480 --> 00:31:55,880 secara khusus, bagi yang lebih kecil dan lebih kecil dan senarai yang lebih kecil, akhirnya kita 746 00:31:55,880 --> 00:32:00,005 berdasar keluar terima kasih kepada apa yang kita akan memanggil kes asas, kes berkod keras yang 747 00:32:00,005 --> 00:32:04,270 berkata, jika senarai itu adalah kecil, kurang daripada 2 dalam kes itu, hanya kembali dengan segera. 748 00:32:04,270 --> 00:32:07,550 Jika kita tidak mempunyai kes khas, algoritma tidak akan berakhir tidak, 749 00:32:07,550 --> 00:32:11,010 dan anda benar-benar akan masuk ke dalam satu gelung tidak terhingga yang benar-benar selama-lamanya. 750 00:32:11,010 --> 00:32:14,330 >> Tetapi menganggap bahawa kita mahu kini meletakkan beberapa nombor di atas ini, sekali lagi, dengan menggunakan n 751 00:32:14,330 --> 00:32:15,660 memandangkan saiz input. 752 00:32:15,660 --> 00:32:18,680 Dan saya mahu bertanya kepada anda, apa yang jumlah masa yang terlibat dalam 753 00:32:18,680 --> 00:32:19,800 berjalan jenis merge? 754 00:32:19,800 --> 00:32:22,960 Atau lebih secara amnya, apa yang kos dalam masa? 755 00:32:22,960 --> 00:32:24,730 >> Baik ia agak mudah untuk mengukur itu. 756 00:32:24,730 --> 00:32:29,010 Jika n adalah kurang daripada 2, masa yang terlibat dalam menyusun n elemen, 757 00:32:29,010 --> 00:32:30,480 di mana n adalah 2, adalah 0. 758 00:32:30,480 --> 00:32:31,410 Kerana kita hanya kembali. 759 00:32:31,410 --> 00:32:32,510 Tidak ada kerja yang perlu dilakukan. 760 00:32:32,510 --> 00:32:35,660 Sekarang boleh dikatakan, mungkin ia adalah satu langkah atau dua langkah-langkah untuk memikirkan jumlah 761 00:32:35,660 --> 00:32:38,420 bekerja, tetapi ia cukup dekat dengan 0 yang Saya hanya akan mengatakan tidak kerja 762 00:32:38,420 --> 00:32:40,940 diperlukan jika senarai adalah begitu kecil untuk tidak menarik. 763 00:32:40,940 --> 00:32:42,580 >> Tetapi kes ini adalah menarik. 764 00:32:42,580 --> 00:32:47,320 Kes rekursi adalah cawangan pseudokod yang berkata lain, jenis 765 00:32:47,320 --> 00:32:52,000 separuh kiri, menyusun hak separuh, menggabungkan kedua-dua bahagian. 766 00:32:52,000 --> 00:32:55,530 Sekarang mengapa ungkapan ini mewakili perbelanjaan yang? 767 00:32:55,530 --> 00:32:58,690 Nah, T n hanya bermakna masa untuk menyelesaikan elemen n. 768 00:32:58,690 --> 00:33:03,070 Dan kemudian di sebelah kanan yang tanda sama ada, T n dibahagikan 769 00:33:03,070 --> 00:33:06,600 sebanyak 2 adalah merujuk kepada kos apa? 770 00:33:06,600 --> 00:33:07,570 Menyusun separuh kiri. 771 00:33:07,570 --> 00:33:10,990 T lain n dibahagikan dengan 2 ialah mungkin merujuk kepada kos untuk 772 00:33:10,990 --> 00:33:12,390 menyelesaikan separuh betul. 773 00:33:12,390 --> 00:33:14,590 >> Dan kemudian n campur? 774 00:33:14,590 --> 00:33:15,420 Adakah penggabungan. 775 00:33:15,420 --> 00:33:19,120 Kerana jika anda mempunyai dua senarai, salah satu saiz n lebih daripada 2 dan satu lagi saiz n 776 00:33:19,120 --> 00:33:22,580 lebih 2, anda perlu dasarnya menyentuh setiap unsur-unsur, seperti Rob 777 00:33:22,580 --> 00:33:24,990 menyentuh setiap cawan, dan hanya seperti yang kita berkata pada setiap 778 00:33:24,990 --> 00:33:26,310 sukarelawan di atas pentas. 779 00:33:26,310 --> 00:33:28,790 Jadi n perbelanjaan bercantum. 780 00:33:28,790 --> 00:33:31,780 >> Sekarang malangnya, formula ini juga dirinya rekursi. 781 00:33:31,780 --> 00:33:36,390 Jadi jika bertanya, jika n, berkata, 16, jika ada 16 orang di atas pentas 782 00:33:36,390 --> 00:33:40,670 atau 16 cawan dalam video, berapa jumlah langkah-langkah yang diperlukan untuk menyusun mereka 783 00:33:40,670 --> 00:33:41,550 dengan jenis merge? 784 00:33:41,550 --> 00:33:45,790 Ini sebenarnya bukan satu jawapan yang jelas, kerana sekarang anda perlu menyelesaikan satu 785 00:33:45,790 --> 00:33:48,500 Recursively menjawab formula ini. 786 00:33:48,500 --> 00:33:51,190 >> Tetapi itu OK, kerana biarlah saya mencadangkan yang kita lakukan yang berikut. 787 00:33:51,190 --> 00:33:56,670 Masa yang terlibat untuk menyelesaikan 16 orang atau 16 cawan akan diwakili 788 00:33:56,670 --> 00:33:58,020 umum sebagai T 16. 789 00:33:58,020 --> 00:34:01,400 Tetapi yang sama, menurut kami formula sebelumnya, 2 kali ganda 790 00:34:01,400 --> 00:34:04,780 masa yang diperlukan untuk menyelesaikan 8 cawan campur 16. 791 00:34:04,780 --> 00:34:08,590 Dan sekali lagi, ditambah 16 adalah masa untuk bergabung, dan T dua kali ganda 8 adalah 792 00:34:08,590 --> 00:34:10,790 masa untuk menyelesaikan separuh kiri dan bahagian kanan. 793 00:34:10,790 --> 00:34:11,989 >> Tetapi sekali lagi, ini tidak mencukupi. 794 00:34:11,989 --> 00:34:13,210 Kita perlu menyelam dalam lebih mendalam. 795 00:34:13,210 --> 00:34:16,409 Ini bermakna kita perlu menjawab soalan, apakah T 8? 796 00:34:16,409 --> 00:34:19,610 Well T 8 hanya 2 kali T 4 ditambah 8. 797 00:34:19,610 --> 00:34:20,520 Nah, apa yang T dari 4? 798 00:34:20,520 --> 00:34:23,780 T 4 hanya 2 kali T 2 ditambah 4. 799 00:34:23,780 --> 00:34:25,489 Nah, apa yang T 2? 800 00:34:25,489 --> 00:34:29,030 T 2 hanya 2 kali T 1 plus 2. 801 00:34:29,030 --> 00:34:31,940 >> Dan sekali lagi, kami mendapat jenis terperangkap dalam kitaran ini. 802 00:34:31,940 --> 00:34:34,790 Tetapi ia adalah kira-kira untuk memukul yang dipanggil kes asas. 803 00:34:34,790 --> 00:34:37,310 Kerana apa yang T 1, adakah kita membuat tuntutan? 804 00:34:37,310 --> 00:34:37,810 0. 805 00:34:37,810 --> 00:34:39,730 Jadi sekarang akhirnya, kita boleh bekerja ke belakang. 806 00:34:39,730 --> 00:34:44,290 >> Jika T 1 adalah 0, saya kini boleh kembali sehingga satu beratur dengan lelaki ini di sini, dan saya boleh 807 00:34:44,290 --> 00:34:46,330 pasangkan 0 for T 1. 808 00:34:46,330 --> 00:34:51,770 Ini bermakna ia sama 2 kali sifar, atau dikenali sebagai 0, ditambah 2. 809 00:34:51,770 --> 00:34:53,739 Dan supaya ungkapan keseluruhan ialah 2. 810 00:34:53,739 --> 00:34:58,740 >> Sekarang, jika saya mengambil T 2, jawapan yang 2, palam ke dalam barisan tengah, T 811 00:34:58,740 --> 00:35:02,740 4, yang memberikan saya 2 kali 2 plus 4, jadi 8. 812 00:35:02,740 --> 00:35:07,080 Jika saya kemudian palam dalam 8 hingga sebelumnya line, yang memberikan saya 2 kali 8, 16. 813 00:35:07,080 --> 00:35:12,470 Dan jika kita kemudian terus bahawa dengan 24, sambil menambah dalam 16, kami akhirnya mendapat 814 00:35:12,470 --> 00:35:13,820 nilai 64. 815 00:35:13,820 --> 00:35:18,480 >> Sekarang dalam dan dengan sendirinya jenis bercakap tiada notasi n itu, 816 00:35:18,480 --> 00:35:20,700 besar O, omega yang kita telah telah bercakap tentang. 817 00:35:20,700 --> 00:35:24,890 Tetapi ternyata bahawa 64 memang 16, saiz input, 818 00:35:24,890 --> 00:35:27,110 log asas 2 of 16. 819 00:35:27,110 --> 00:35:30,200 Dan jika ini adalah sedikit yang tidak dikenali, hanya berfikir kembali, dan ia akan kembali 820 00:35:30,200 --> 00:35:30,700 untuk anda akhirnya. 821 00:35:30,700 --> 00:35:33,775 Jika ini adalah log asas 2, ia seperti 2 dinaikkan kepada apa yang memberikan anda 16? 822 00:35:33,775 --> 00:35:36,380 Oh, itu 4, jadi ia adalah 16 kali 4. 823 00:35:36,380 --> 00:35:39,380 >> Dan sekali lagi, ia bukan satu masalah besar jika ini adalah jenis memori yang kabur sekarang. 824 00:35:39,380 --> 00:35:43,720 Tetapi untuk sekarang, mengambil iman bahawa 16 log 16 adalah 64. 825 00:35:43,720 --> 00:35:46,590 Dan begitu sesungguhnya, dengan kewarasan ini mudah memeriksa, kami telah disahkan - 826 00:35:46,590 --> 00:35:48,250 tetapi tidak dibuktikan secara rasmi - 827 00:35:48,250 --> 00:35:52,800 bahawa masa berjalan merge apapun memang n log n. 828 00:35:52,800 --> 00:35:53,790 >> Jadi tidak buruk. 829 00:35:53,790 --> 00:35:57,260 Ia pasti lebih baik daripada algoritma yang kita lihat setakat ini, dan 830 00:35:57,260 --> 00:36:00,710 ia adalah kerana kita telah dimanfaatkan, satu, teknik yang dipanggil rekursi. 831 00:36:00,710 --> 00:36:03,880 Tetapi yang lebih menarik daripada itu, bahawa konsep membahagikan dan menakluk. 832 00:36:03,880 --> 00:36:07,460 Sekali lagi, yang benar-benar minggu 0 barangan yang walaupun kini berulang dalam 833 00:36:07,460 --> 00:36:08,740 cara yang lebih menarik. 834 00:36:08,740 --> 00:36:11,750 >> Sekarang sedikit senaman menyeronokkan, jika anda telah pernah dilakukan ini - dan anda mungkin 835 00:36:11,750 --> 00:36:14,660 tidak perlu, kerana jenis normal orang tidak berfikir untuk melakukan ini. 836 00:36:14,660 --> 00:36:20,650 Tetapi jika saya pergi ke google.com dan jika Saya mahu belajar sesuatu tentang 837 00:36:20,650 --> 00:36:22,356 rekursi, Enter. 838 00:36:22,356 --> 00:36:25,106 839 00:36:25,106 --> 00:36:29,058 >> [Ketawa] 840 00:36:29,058 --> 00:36:32,030 [Ketawa MORE] 841 00:36:32,030 --> 00:36:33,385 DAVID MALAN: jenaka Bad perlahan-lahan merebak. 842 00:36:33,385 --> 00:36:34,450 [Ketawa] 843 00:36:34,450 --> 00:36:36,970 DAVID MALAN: Hanya dalam kes ini, ia adalah di sana. 844 00:36:36,970 --> 00:36:38,710 Saya tidak menyatakan ia salah, dan ada jenaka. 845 00:36:38,710 --> 00:36:40,810 Baiklah. 846 00:36:40,810 --> 00:36:42,950 Menjelaskan kepada orang-orang datang kepada anda jika ia tidak cukup klik hanya lagi. 847 00:36:42,950 --> 00:36:47,650 Tetapi rekursi, secara umum, merujuk kepada proses fungsi memanggil 848 00:36:47,650 --> 00:36:51,430 sendiri, atau lebih amnya, membahagikan masalah menjadi sesuatu yang boleh 849 00:36:51,430 --> 00:36:56,220 diselesaikan sedikit demi sedikit dengan menyelesaikan sama masalah wakil. 850 00:36:56,220 --> 00:36:58,400 >> Nah, mari kita gear perubahan hanya untuk seketika. 851 00:36:58,400 --> 00:37:00,840 Kami ingin berakhir pada cliffhangers tertentu, jadi mari kita mulakan untuk menetapkan 852 00:37:00,840 --> 00:37:05,870 pentas, untuk beberapa minit, pada idea yang sangat mudah - 853 00:37:05,870 --> 00:37:07,620 bahawa bertukar-tukar dua unsur, bukan? 854 00:37:07,620 --> 00:37:10,040 Semua ini algoritma kita telah bercakap tentang pasangan yang lalu 855 00:37:10,040 --> 00:37:12,420 kuliah melibatkan beberapa jenis bertukar-tukar. 856 00:37:12,420 --> 00:37:14,630 Hari ini ia telah dilihat oleh mereka mendapat keluar dari kerusi mereka dan 857 00:37:14,630 --> 00:37:18,570 berjalan di sekitar, tetapi dalam kod, kita akan hanya mengambil elemen dari satu array 858 00:37:18,570 --> 00:37:20,370 dan mencebur ke dalam yang lain. 859 00:37:20,370 --> 00:37:21,880 >> Jadi bagaimana kita pergi tentang melakukan perkara ini? 860 00:37:21,880 --> 00:37:24,850 Baiklah, biar saya pergi ke hadapan dan menulis program cepat di sini. 861 00:37:24,850 --> 00:37:31,600 Saya akan pergi ke hadapan dan melakukan ini sebagai berikut. 862 00:37:31,600 --> 00:37:33,910 Mari kita panggil ini - 863 00:37:33,910 --> 00:37:38,070 apa yang kita mahu memanggil satu ini? 864 00:37:38,070 --> 00:37:38,650 >> Sebenarnya, tidak. 865 00:37:38,650 --> 00:37:39,420 Biar saya putar balik. 866 00:37:39,420 --> 00:37:41,220 Saya tidak mahu berbuat demikian cliffhanger yet. 867 00:37:41,220 --> 00:37:42,270 Ia akan merosakkan keseronokan. 868 00:37:42,270 --> 00:37:43,600 Mari kita buat ini sebaliknya. 869 00:37:43,600 --> 00:37:47,430 >> Katakan bahawa saya mahu menulis sedikit program dan bahawa sekarang ini merangkumi 870 00:37:47,430 --> 00:37:48,700 Idea rekursi. 871 00:37:48,700 --> 00:37:50,370 Saya jenis mendapat lebih awal daripada diri saya di sana. 872 00:37:50,370 --> 00:37:51,420 Saya akan melakukan yang berikut. 873 00:37:51,420 --> 00:38:00,220 >> Pertama, cepat termasuk standard io.h, serta termasuk daripada cs50.h. 874 00:38:00,220 --> 00:38:03,200 Dan kemudian saya akan pergi ke hadapan dan mengisytiharkan int sah utama 875 00:38:03,200 --> 00:38:04,360 dengan cara yang biasa. 876 00:38:04,360 --> 00:38:07,920 Saya sedar saya telah misnamed fail, jadi biarlah saya menambah. c lanjutan di sini supaya 877 00:38:07,920 --> 00:38:09,510 bahawa kita boleh menyusun dengan betul. 878 00:38:09,510 --> 00:38:10,970 Mula fungsi ini. 879 00:38:10,970 --> 00:38:13,290 >> Dan fungsi yang saya mahu menulis, agak semata-mata, adalah salah satu yang meminta 880 00:38:13,290 --> 00:38:16,210 pengguna untuk nombor dan kemudian menambah sehingga semua nombor antara yang 881 00:38:16,210 --> 00:38:19,920 bilangan dan, berkata, 0. 882 00:38:19,920 --> 00:38:22,510 Jadi pertama saya akan pergi ke hadapan dan mengisytiharkan n int. 883 00:38:22,510 --> 00:38:24,760 Kemudian saya tulis kod ada yang kita telah digunakan untuk sementara waktu. 884 00:38:24,760 --> 00:38:26,660 Walaupun sesuatu itu benar. 885 00:38:26,660 --> 00:38:28,000 Saya akan kembali ke bahawa dalam seketika. 886 00:38:28,000 --> 00:38:29,010 >> Apa yang saya mahu lakukan? 887 00:38:29,010 --> 00:38:33,460 Saya ingin katakan printf positif integer sila. 888 00:38:33,460 --> 00:38:36,130 Dan kemudian saya akan mengatakan n mendapat mendapatkan int. 889 00:38:36,130 --> 00:38:38,800 Jadi sekali lagi, beberapa kod boilerplate bahawa kami telah digunakan sebelum ini. 890 00:38:38,800 --> 00:38:40,810 Dan saya akan melakukan ini manakala n adalah kurang daripada 1. 891 00:38:40,810 --> 00:38:44,120 Jadi ini akan memastikan bahawa pengguna memberi saya integer positif. 892 00:38:44,120 --> 00:38:45,490 >> Dan sekarang saya akan melakukan yang berikut. 893 00:38:45,490 --> 00:38:51,020 Saya mahu untuk menambah sehingga semua nombor antara 1 dan dan n, atau 0 dan n, 894 00:38:51,020 --> 00:38:52,570 setara, untuk mendapatkan jumlah wang. 895 00:38:52,570 --> 00:38:55,100 Jadi simbol sigma besar yang mungkin anda ingat. 896 00:38:55,100 --> 00:38:59,050 Jadi, saya akan melakukan ini dengan panggilan pertama fungsi yang dipanggil sigma, 897 00:38:59,050 --> 00:39:06,030 lulus dalam n, dan kemudian saya akan printf berkata, jawapan yang tepat di sana. 898 00:39:06,030 --> 00:39:08,180 >> Jadi dalam jangka pendek, saya mendapat dan int dari pengguna. 899 00:39:08,180 --> 00:39:09,280 Saya memastikan ia adalah positif. 900 00:39:09,280 --> 00:39:12,700 Saya mengaku jawapan yang berubah-ubah yang dipanggil daripada int jenis dan kedai di dalamnya pulangan 901 00:39:12,700 --> 00:39:15,610 nilai sigma, lulus dalam n sebagai input. 902 00:39:15,610 --> 00:39:17,060 Dan kemudian saya mencetak di atas jawapan itu. 903 00:39:17,060 --> 00:39:19,550 >> Malangnya, walaupun sigma bunyi seperti sesuatu yang mungkin dalam 904 00:39:19,550 --> 00:39:24,040 fail math.h, perisytiharan itu, ia sebenarnya tidak. 905 00:39:24,040 --> 00:39:24,690 Jadi, itu OK. 906 00:39:24,690 --> 00:39:26,170 Saya boleh melaksanakan ini sendiri. 907 00:39:26,170 --> 00:39:29,160 Saya akan melaksanakan fungsi yang dipanggil sigma, dan ia akan mengambil 908 00:39:29,160 --> 00:39:29,900 parameter - 909 00:39:29,900 --> 00:39:32,100 mari kita hanya memanggilnya m, hanya jadi ia berbeza. 910 00:39:32,100 --> 00:39:35,910 Dan kemudian di sini, saya akan berkata, baik, jika m adalah kurang daripada 1 - ini adalah 911 00:39:35,910 --> 00:39:38,180 program yang sangat menarik. 912 00:39:38,180 --> 00:39:41,700 Jadi, saya akan pergi ke hadapan dan serta-merta mengembalikan 0. 913 00:39:41,700 --> 00:39:45,920 Ia hanya tidak masuk akal untuk menambah semua nombor antara 1 dan m jika m 914 00:39:45,920 --> 00:39:48,470 sendiri ialah 0 atau negatif. 915 00:39:48,470 --> 00:39:50,900 >> Dan kemudian saya akan pergi ke hadapan dan melakukan ini sangat iterative. 916 00:39:50,900 --> 00:39:53,090 Saya akan melakukan seperti ini lama-sekolah, dan saya akan pergi ke hadapan 917 00:39:53,090 --> 00:39:57,150 dan mengatakan bahawa saya akan mengisytiharkan jumlah wang yang menjadi 0. 918 00:39:57,150 --> 00:39:59,630 Kemudian saya akan mempunyai untuk gelung int - 919 00:39:59,630 --> 00:40:02,820 dan biarlah saya melakukannya untuk perlawanan kami kod pengedaran, supaya anda mempunyai salinan 920 00:40:02,820 --> 00:40:07,500 di rumah. int i mendapat 1 pada sehingga i adalah kurang daripada atau sama dengan m. 921 00:40:07,500 --> 00:40:09,430 i plus plus. 922 00:40:09,430 --> 00:40:11,430 Dan kemudian di dalam ini untuk gelung - 923 00:40:11,430 --> 00:40:12,440 kita sudah hampir - 924 00:40:12,440 --> 00:40:15,810 jumlah mendapat jumlah campur 1. 925 00:40:15,810 --> 00:40:17,670 Dan kemudian saya akan kembali jumlah. 926 00:40:17,670 --> 00:40:19,420 >> Jadi saya melakukan ini dengan cepat, agak diakui. 927 00:40:19,420 --> 00:40:22,775 Tetapi sekali lagi, fungsi utama agak mudah, berdasarkan kod yang kami telah 928 00:40:22,775 --> 00:40:23,190 ditulis setakat ini. 929 00:40:23,190 --> 00:40:25,610 Menggunakan gelung dwi untuk mendapatkan yang positif int dari pengguna. 930 00:40:25,610 --> 00:40:29,870 Saya kemudian lulus int itu kepada fungsi baru dipanggil sigma, memanggil ia, sekali lagi, n. 931 00:40:29,870 --> 00:40:33,100 Dan saya menyimpan nilai pulangan, jawapan dari kotak hitam kini 932 00:40:33,100 --> 00:40:35,460 dikenali sebagai sigma, di ubah dipanggil jawapan. 933 00:40:35,460 --> 00:40:36,580 Kemudian saya mencetaknya. 934 00:40:36,580 --> 00:40:39,090 >> Jika kita terus cerita, bagaimana sigma dilaksanakan? 935 00:40:39,090 --> 00:40:40,840 Saya mencadangkan untuk melaksanakan seperti berikut. 936 00:40:40,840 --> 00:40:43,560 Pertama, sedikit kesilapan semakan memastikan bahawa pengguna tidak 937 00:40:43,560 --> 00:40:46,480 main dengan saya dan lulus dalam beberapa nilai negatif atau 0. 938 00:40:46,480 --> 00:40:49,710 Kemudian saya mengisytiharkan pembolehubah yang dipanggil kesimpulan dan menetapkan kepada 0. 939 00:40:49,710 --> 00:40:55,910 >> Dan sekarang saya mula bergerak dari i sama 1 semua jalan sehingga dan termasuk m, 940 00:40:55,910 --> 00:41:00,130 kerana saya ingin termasuk semua nombor satu melalui m, termasuk. 941 00:41:00,130 --> 00:41:04,350 Dan di dalam ini untuk gelung, saya hanya melakukan jumlah mendapat apa-apa sekarang, ditambah dengan 942 00:41:04,350 --> 00:41:08,900 nilai i. 943 00:41:08,900 --> 00:41:10,370 Plus nilai i. 944 00:41:10,370 --> 00:41:14,090 >> Sebagai mengetepikan, jika anda tidak melihat ini sebelum ini, terdapat beberapa gula sintaktik 945 00:41:14,090 --> 00:41:14,870 untuk syarikat ini. 946 00:41:14,870 --> 00:41:21,120 Saya boleh menulis semula ini sebagai campur sama i, hanya untuk menyelamatkan diri saya beberapa ketukan kekunci 947 00:41:21,120 --> 00:41:22,570 dan melihat lebih sejuk sedikit. 948 00:41:22,570 --> 00:41:23,140 Tetapi itu semua. 949 00:41:23,140 --> 00:41:24,660 Ia adalah fungsi yang sama. 950 00:41:24,660 --> 00:41:26,710 >> Malangnya, kod ini ini tidak akan menyusun yet. 951 00:41:26,710 --> 00:41:31,600 Jika saya berjalan membuat sigma 0, bagaimana am Saya akan mendapatkan menjerit? 952 00:41:31,600 --> 00:41:33,473 Apa yang ia akan tidak suka? 953 00:41:33,473 --> 00:41:35,740 >> PENONTON: [didengar]. 954 00:41:35,740 --> 00:41:37,800 >> DAVID MALAN: Ya, saya tidak mengisytiharkan fungsi top up, kan? 955 00:41:37,800 --> 00:41:40,590 C adalah jenis bodoh, kerana ia hanya melakukan apa yang anda beritahu kepada lakukan, dan anda 956 00:41:40,590 --> 00:41:41,880 perlu melakukannya dalam perintah itu. 957 00:41:41,880 --> 00:41:45,910 Dan jadi jika saya tekan Enter sini, saya akan mendapat amaran mengenai sigma tersirat 958 00:41:45,910 --> 00:41:46,860 perisytiharan. 959 00:41:46,860 --> 00:41:48,120 >> Oh, tidak menjadi masalah. 960 00:41:48,120 --> 00:41:50,370 Saya boleh naik ke atas, dan saya boleh berkata, semua hak, tunggu satu minit. 961 00:41:50,370 --> 00:41:54,240 Sigma adalah satu fungsi yang mengembalikan int an dan ia menjangka 962 00:41:54,240 --> 00:41:56,620 int sebagai input, koma bertitik. 963 00:41:56,620 --> 00:41:59,550 Atau saya boleh meletakkan fungsi keseluruhan atas utama, tetapi secara umum, saya akan 964 00:41:59,550 --> 00:42:02,260 mencadangkan terhadap itu, kerana ia adalah bagus untuk sentiasa mempunyai utama di atas supaya 965 00:42:02,260 --> 00:42:06,310 anda boleh menyelam kanan dalam dan tahu apa program yang melakukan dengan membaca utama pertama. 966 00:42:06,310 --> 00:42:07,930 >> Jadi sekarang biarlah saya mengosongkan skrin. 967 00:42:07,930 --> 00:42:09,330 Remake sigma 0. 968 00:42:09,330 --> 00:42:10,340 Semua seolah-olah untuk menyemak. 969 00:42:10,340 --> 00:42:11,970 Izinkan saya menjalankan sigma 0. 970 00:42:11,970 --> 00:42:12,770 Antara positif. 971 00:42:12,770 --> 00:42:15,580 Saya akan memberikan nombor 3 untuk memastikan ia mudah. 972 00:42:15,580 --> 00:42:18,710 Jadi yang perlu memberikan saya 3 campur 2 campur 1, jadi 6. 973 00:42:18,710 --> 00:42:20,750 Memasuki, dan sesungguhnya saya mendapat 6. 974 00:42:20,750 --> 00:42:21,820 >> Saya boleh melakukan sesuatu yang lebih besar - 975 00:42:21,820 --> 00:42:24,080 50, 12, 75. 976 00:42:24,080 --> 00:42:27,690 Sama seperti menyimpang, saya akan melakukan sesuatu yang tidak masuk akal seperti yang benar-benar besar 977 00:42:27,690 --> 00:42:30,375 nombor, Oh, yang benar-benar bekerja di luar - 978 00:42:30,375 --> 00:42:31,600 eh, saya tidak fikir itu betul. 979 00:42:31,600 --> 00:42:32,810 Mari kita lihat. 980 00:42:32,810 --> 00:42:34,060 Mari kita benar-benar kucar-kacir dengan ia. 981 00:42:34,060 --> 00:42:37,150 982 00:42:37,150 --> 00:42:38,400 >> Itulah masalah. 983 00:42:38,400 --> 00:42:43,180 984 00:42:43,180 --> 00:42:44,970 Apa yang berlaku? 985 00:42:44,970 --> 00:42:46,050 Kod ini bukan yang buruk. 986 00:42:46,050 --> 00:42:48,470 Ia masih linear. 987 00:42:48,470 --> 00:42:50,810 Whistling adalah kesan yang baik, walaupun. 988 00:42:50,810 --> 00:42:52,060 Apa yang berlaku? 989 00:42:52,060 --> 00:42:54,700 990 00:42:54,700 --> 00:42:55,620 >> Tidak pasti jika saya mendengarnya. 991 00:42:55,620 --> 00:42:57,620 Jadi ia ternyata - dan ini adalah sebagai diketepikan. 992 00:42:57,620 --> 00:42:59,400 Ini bukan adalah teras kepada Idea rekursi. 993 00:42:59,400 --> 00:43:02,480 Rupa-rupanya, kerana saya cuba untuk mewakili satu jumlah yang besar, yang paling 994 00:43:02,480 --> 00:43:06,980 mungkin ia sedang disalah tafsir oleh C sebagai nombor tidak positif, 995 00:43:06,980 --> 00:43:09,980 tetapi bilangan negatif. 996 00:43:09,980 --> 00:43:12,690 >> Kita tidak bercakap tentang perkara ini, tetapi ia ternyata terdapat nombor negatif 997 00:43:12,690 --> 00:43:14,210 di dunia di samping kepada nombor positif. 998 00:43:14,210 --> 00:43:16,290 Dan cara-cara di mana anda boleh mewakili nombor negatif 999 00:43:16,290 --> 00:43:19,530 dasarnya ialah, anda menggunakan salah satu sedikit khas untuk menunjukkan 1000 00:43:19,530 --> 00:43:20,400 positif dalam negatif. 1001 00:43:20,400 --> 00:43:22,950 Ia sedikit lebih kompleks daripada itu, tetapi itulah idea asas. 1002 00:43:22,950 --> 00:43:26,740 >> Lebih malang lagi, jika C adalah mengelirukan satu mereka bit yang sebenarnya bermaksud, 1003 00:43:26,740 --> 00:43:30,790 oh, ini adalah satu nombor negatif, gelung saya di sini, misalnya, adalah sebenarnya tidak pernah 1004 00:43:30,790 --> 00:43:31,740 akan menamatkan. 1005 00:43:31,740 --> 00:43:33,850 Jadi jika saya sebenarnya mencetak sesuatu lagi dan lagi, kita akan 1006 00:43:33,850 --> 00:43:34,650 lihat banyak keseluruhan. 1007 00:43:34,650 --> 00:43:36,220 Tetapi sekali lagi, ini adalah selain titik. 1008 00:43:36,220 --> 00:43:38,590 Ini adalah benar-benar hanya satu bentuk rasa ingin tahu bahawa kita akan datang 1009 00:43:38,590 --> 00:43:39,550 kembali ke akhirnya. 1010 00:43:39,550 --> 00:43:43,400 Tetapi untuk sekarang, ini adalah betul pelaksanaan jika kita menganggap bahawa 1011 00:43:43,400 --> 00:43:45,970 pengguna akan menyediakan Ints yang patut dalam Ints. 1012 00:43:45,970 --> 00:43:49,370 >> Tetapi saya mendakwa bahawa kod ini, terus-terang, boleh dilakukan lebih banyak lagi semata-mata. 1013 00:43:49,370 --> 00:43:54,060 Jika matlamat di tangan adalah untuk mengambil nombor seperti m dan menambah sehingga semua 1014 00:43:54,060 --> 00:43:59,510 nombor antara ia dan 1, atau sebaliknya antara 1 dan, saya menuntut 1015 00:43:59,510 --> 00:44:03,380 bahawa saya boleh meminjam idea ini yang bergabung apapun yang telah, yang mengambil masalah 1016 00:44:03,380 --> 00:44:05,660 saiz ini dan membahagikan menjadi sesuatu yang lebih kecil. 1017 00:44:05,660 --> 00:44:09,875 Mungkin bukan separuh, tetapi lebih kecil, tetapi representatively yang sama. 1018 00:44:09,875 --> 00:44:12,130 Idea yang sama, tetapi masalah yang lebih kecil. 1019 00:44:12,130 --> 00:44:15,470 >> Jadi, saya sebenarnya - biarlah saya simpan fail ini dengan nombor versi yang berbeza. 1020 00:44:15,470 --> 00:44:17,670 Kami akan memanggil versi ini 1 daripada 0. 1021 00:44:17,670 --> 00:44:20,790 Dan saya mendakwa bahawa saya boleh sebenarnya reimplement ini dalam jenis ini 1022 00:44:20,790 --> 00:44:22,160 fikiran-lentur cara. 1023 00:44:22,160 --> 00:44:23,710 >> Saya akan meninggalkan sebahagian daripadanya sahaja. 1024 00:44:23,710 --> 00:44:27,710 Saya akan mengatakan jika m adalah kurang daripada atau sama dengan 0 - 1025 00:44:27,710 --> 00:44:29,280 Saya hanya akan menjadi sedikit lebih dubur masa ini 1026 00:44:29,280 --> 00:44:30,520 dengan memeriksa kesilapan saya - 1027 00:44:30,520 --> 00:44:33,190 Saya akan pergi ke hadapan dan kembali 0. 1028 00:44:33,190 --> 00:44:34,490 Ini adalah sewenang-wenangnya. 1029 00:44:34,490 --> 00:44:37,500 Saya hanya sekadar membuat keputusan jika pengguna memberi saya nombor negatif, saya 1030 00:44:37,500 --> 00:44:41,490 kembali 0, dan mereka harus telah membaca dokumentasi yang lebih rapat. 1031 00:44:41,490 --> 00:44:42,170 >> Yang lain - 1032 00:44:42,170 --> 00:44:44,070 melihat apa yang saya akan lakukan. 1033 00:44:44,070 --> 00:44:49,260 Yang lain saya akan kembali m plus - 1034 00:44:49,260 --> 00:44:51,010 apakah sigma m? 1035 00:44:51,010 --> 00:44:56,710 Nah, sigma m plus m tolak 1, plus m tolak 2, ditambah tolak m 3. 1036 00:44:56,710 --> 00:44:58,030 Saya tidak mahu menulis semua bahawa. 1037 00:44:58,030 --> 00:44:59,120 Mengapa tidak saya hanya menyepak bola? 1038 00:44:59,120 --> 00:45:05,080 Recursively memanggil diri saya dengan sedikit masalah yang lebih kecil, koma bertitik, 1039 00:45:05,080 --> 00:45:06,840 dan memanggilnya sehari? 1040 00:45:06,840 --> 00:45:07,040 >> Betul? 1041 00:45:07,040 --> 00:45:10,980 Sekarang di sini, juga, anda mungkin berasa bimbang atau bahawa ini adalah satu gelung tak terhingga bahawa saya 1042 00:45:10,980 --> 00:45:15,450 mendorong, di mana saya melaksanakan sigma dengan menghubungi sigma. 1043 00:45:15,450 --> 00:45:20,342 Tetapi itu sempurna OK, kerana saya fikir hadapan satu ditambah yang baris? 1044 00:45:20,342 --> 00:45:22,600 >> PENONTON: [didengar]. 1045 00:45:22,600 --> 00:45:25,430 >> DAVID MALAN: 23 hingga 26, yang adalah keadaan saya jika. 1046 00:45:25,430 --> 00:45:28,390 Kerana apa yang bagus tentang penolakan di sini, kerana saya terus 1047 00:45:28,390 --> 00:45:31,180 menyerahkan sigma masalah yang lebih kecil, lebih kecil masalah, yang lebih kecil - ia tidak 1048 00:45:31,180 --> 00:45:31,870 separuh saiz. 1049 00:45:31,870 --> 00:45:34,380 Ia hanya satu langkah bayi yang lebih kecil, tetapi itulah OK. 1050 00:45:34,380 --> 00:45:38,050 Kerana akhirnya, kita akan bekerja cara kami ke 1 atau 0. 1051 00:45:38,050 --> 00:45:41,630 Dan apabila kita mencapai 0, sigma tidak akan memanggil dirinya lagi. 1052 00:45:41,630 --> 00:45:43,590 Ia akan segera kembali 0. 1053 00:45:43,590 --> 00:45:47,960 >> Jadi kesan, jika anda jenis angin ini dalam fikiran anda, adalah untuk menambah m plus 1054 00:45:47,960 --> 00:45:52,740 m tolak 1, ditambah m tolak 2, ditambah m tolak 3, ditambah dot, dot, dot, m tolak 1055 00:45:52,740 --> 00:45:57,820 m, akhirnya memberikan anda 0, dan kesan akhirnya menambah semua 1056 00:45:57,820 --> 00:45:59,070 perkara-perkara ini bersama-sama. 1057 00:45:59,070 --> 00:46:02,380 Oleh itu, kita tidak mempunyai, dengan rekursi, menyelesaikan masalah yang kita 1058 00:46:02,380 --> 00:46:03,470 tidak dapat menyelesaikan sebelum ini. 1059 00:46:03,470 --> 00:46:06,840 Malah, versi 0 daripada ini, dan setiap masalah setakat ini, telah larut 1060 00:46:06,840 --> 00:46:09,980 dengan hanya menggunakan untuk gelung atau semasa gelung atau membina yang sama. 1061 00:46:09,980 --> 00:46:13,150 >> Tetapi rekursi, saya berani untuk menegaskan, memberikan kita cara yang berbeza berfikir tentang 1062 00:46:13,150 --> 00:46:17,010 masalah, di mana jika kita boleh mengambil masalah, bahagikan ia daripada sesuatu 1063 00:46:17,010 --> 00:46:22,340 agak besar ke dalam sesuatu yang agak lebih kecil, saya mendakwa bahawa kita boleh menyelesaikannya 1064 00:46:22,340 --> 00:46:26,040 mungkin sedikit lebih elegan dari segi reka bentuk, dengan kod kurang, 1065 00:46:26,040 --> 00:46:30,980 dan mungkin juga menyelesaikan masalah yang akan menjadi lebih sukar, seperti yang kita akan akhirnya 1066 00:46:30,980 --> 00:46:33,280 lihat, penyelesaian semata-mata secara berulang. 1067 00:46:33,280 --> 00:46:35,980 >> Tetapi cliffhanger yang saya lakukan mahu meninggalkan kami pada adalah ini. 1068 00:46:35,980 --> 00:46:40,720 Biar saya pergi ke hadapan dan membuka sehingga fail dari - 1069 00:46:40,720 --> 00:46:44,300 sebenarnya, saya pergi dan berpuasa sebenar ini. 1070 00:46:44,300 --> 00:46:46,875 Biar saya pergi ke hadapan dan mencadangkan berikut. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Antara kod hari ini adalah fail ini di sini. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 Yang satu ini di sini, noswap. 1075 00:47:03,050 --> 00:47:06,260 >> Jadi ini adalah satu program kecil yang bodoh Saya disebat sehingga bahawa tuntutan untuk melakukan 1076 00:47:06,260 --> 00:47:06,940 berikut. 1077 00:47:06,940 --> 00:47:10,140 Di utama, ia mula-mula mengisytiharkan satu int dipanggil x dan menyerahkan ia 1078 00:47:10,140 --> 00:47:11,100 nilai 1. 1079 00:47:11,100 --> 00:47:13,520 Kemudian ia mengisytiharkan an y dan int menyerahkan ia nilai 2. 1080 00:47:13,520 --> 00:47:15,310 Kemudian ia mencetak apa x dan y adalah. 1081 00:47:15,310 --> 00:47:17,781 Kemudian ia berkata, bertukar-tukar, dot dot dot. 1082 00:47:17,781 --> 00:47:21,670 >> Kemudian ia mendakwa memanggil fungsi dipanggil swap, lulus dalam x dan 1083 00:47:21,670 --> 00:47:24,290 y, idea yang yang diharapkan x dan y akan kembali 1084 00:47:24,290 --> 00:47:25,620 yang berbeza, sebaliknya. 1085 00:47:25,620 --> 00:47:27,110 Kemudian ia mendakwa bertukar! 1086 00:47:27,110 --> 00:47:28,420 dengan tanda seru. 1087 00:47:28,420 --> 00:47:30,190 Kemudian ia mencetak keluar x dan y. 1088 00:47:30,190 --> 00:47:33,480 >> Tetapi ternyata bahawa ini sangat demonstrasi mudah turun 1089 00:47:33,480 --> 00:47:35,570 di sini adalah sebenarnya kereta. 1090 00:47:35,570 --> 00:47:38,870 Walaupun saya mengisytiharkan sementara berubah dan meletakkan sementara di 1091 00:47:38,870 --> 00:47:42,010 , maka saya penguntukan semula nilai yang b - 1092 00:47:42,010 --> 00:47:45,080 yang merasakan yang munasabah, kerana saya telah disimpan satu salinan dalam temp. 1093 00:47:45,080 --> 00:47:48,410 Kemudian saya mengemaskini b untuk sama Apa sahaja di dalam temp. 1094 00:47:48,410 --> 00:47:51,610 Ini jenis permainan shell menggerakkan ke b dan b ke dalam dengan menggunakan ini 1095 00:47:51,610 --> 00:47:54,360 tengah-lelaki yang dipanggil suhu merasakan sempurna yang munasabah. 1096 00:47:54,360 --> 00:47:57,270 >> Tetapi saya mengatakan bahawa apabila saya berjalan ini kod, seperti yang saya akan lakukan sekarang - 1097 00:47:57,270 --> 00:47:59,490 izinkan saya pergi ke hadapan dan tampalkannya di sini. 1098 00:47:59,490 --> 00:48:01,995 Saya akan panggil noswap.c ini. 1099 00:48:01,995 --> 00:48:05,630 Dan seperti namanya, ini tidak akan menjadi satu program yang betul. 1100 00:48:05,630 --> 00:48:09,460 Buat noswap. / Tiada swap. 1101 00:48:09,460 --> 00:48:12,110 x 1, y ialah 2, bertukar-tukar, bertukar. 1102 00:48:12,110 --> 00:48:14,220 x 1, y ialah 2. 1103 00:48:14,220 --> 00:48:16,920 Ini adalah asas yang salah, walaupun walaupun ini seolah-olah sempurna 1104 00:48:16,920 --> 00:48:17,730 munasabah untuk saya. 1105 00:48:17,730 --> 00:48:21,330 Dan tidak ada sebab, tetapi kita tidak akan mendedahkan sebab hanya lagi. 1106 00:48:21,330 --> 00:48:24,610 >> Buat masa cliffhanger kedua saya mahu meninggalkan anda dengan adalah ini, 1107 00:48:24,610 --> 00:48:27,120 pengumuman pelbagai pada kod kupon. 1108 00:48:27,120 --> 00:48:31,590 Inovasi kami dengan hari-hari akhir tahun ini telah menimbulkan beberapa bukan remeh 1109 00:48:31,590 --> 00:48:33,830 soalan, yang merupakan bukan niat kita. 1110 00:48:33,830 --> 00:48:36,590 Tujuan kod kupon, di mana jika anda sebahagian daripada masalah 1111 00:48:36,590 --> 00:48:39,850 set awal, dengan itu mendapat satu hari, adalah benar-benar untuk membantu anda semua membantu 1112 00:48:39,850 --> 00:48:42,420 diri anda bermula awal, jenis oleh incentivizing anda. 1113 00:48:42,420 --> 00:48:44,880 Membantu kita mengagihkan beban di seluruh waktu pejabat yang lebih baik supaya 1114 00:48:44,880 --> 00:48:45,740 ia adalah sejenis menang-menang. 1115 00:48:45,740 --> 00:48:48,860 >> Malangnya, saya fikir arahan saya belum, setakat ini, sangat jelas, jadi 1116 00:48:48,860 --> 00:48:52,230 Saya kembali pada hujung minggu ini dan dikemaskini spec dalam yang lebih besar, lebih berani untuk teks 1117 00:48:52,230 --> 00:48:53,600 menjelaskan peluru seperti ini. 1118 00:48:53,600 --> 00:48:56,900 Dan hanya untuk mengatakan ia lebih kepada umum, dengan lalai, set masalah adalah disebabkan Khamis 1119 00:48:56,900 --> 00:48:58,400 pada tengah hari, setiap sukatan pelajaran. 1120 00:48:58,400 --> 00:49:02,030 Jika anda bermula awal, kemasan sebahagian daripada masalah yang ditetapkan oleh Rabu di 12:00 1121 00:49:02,030 --> 00:49:05,170 PM, bahagian yang berkaitan dengan kupon kod, idea adalah bahawa anda boleh melanjutkan 1122 00:49:05,170 --> 00:49:07,710 tarikh akhir anda untuk P ditetapkan sehingga Jumaat. 1123 00:49:07,710 --> 00:49:10,890 Iaitu, sedikit daripada sebahagian kecil daripada P ditetapkan berbanding dengan apa yang biasanya adalah 1124 00:49:10,890 --> 00:49:13,200 masalah yang lebih besar, dan anda membeli diri anda satu hari. 1125 00:49:13,200 --> 00:49:15,190 Sekali lagi, ia membawa anda berfikir tentang set masalah, membawa anda ke 1126 00:49:15,190 --> 00:49:16,380 waktu pejabat lebih awal. 1127 00:49:16,380 --> 00:49:20,670 Tetapi masalah kod kupon masih diperlukan, walaupun anda tidak hantar. 1128 00:49:20,670 --> 00:49:23,340 >> Tetapi yang lebih compellingly adalah ini. 1129 00:49:23,340 --> 00:49:26,520 (Berbisik STAGE) Dan orang-orang penduduk meninggalkan awal adalah gonna menyesal. 1130 00:49:26,520 --> 00:49:28,620 Begitu juga dengan orang di balkoni. 1131 00:49:28,620 --> 00:49:32,510 Saya memohon maaf terlebih dahulu kepada orang-orang di balkoni atas sebab-sebab yang akan 1132 00:49:32,510 --> 00:49:33,920 jelas dalam seketika. 1133 00:49:33,920 --> 00:49:37,050 >> Oleh itu, kita bernasib baik kerana mempunyai salah satu daripada Bekas rakan-rakan pengajaran kepala CS50 di 1134 00:49:37,050 --> 00:49:39,302 sebuah syarikat yang dipanggil dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 Mereka telah sangat bermurah hati menderma kod kupon di sini untuk ruang ini banyak, 1136 00:49:45,500 --> 00:49:48,180 yang meningkat daripada biasa 2 gigabait. 1137 00:49:48,180 --> 00:49:51,740 Jadi apa yang saya fikir kita akan lakukan pada ini nota terakhir adalah melakukan sedikit giveaway, 1138 00:49:51,740 --> 00:49:55,380 mana dalam hanya seketika, kita akan mendedahkan pemenang dan yang mempunyai kupon 1139 00:49:55,380 --> 00:49:57,980 kod yang anda boleh pergi ke mereka laman web, menaip dalam, dan Voilà, mendapatkan 1140 00:49:57,980 --> 00:50:01,370 banyak seluruh lebih Dropbox ruang untuk anda perkakas dan untuk fail peribadi anda. 1141 00:50:01,370 --> 00:50:05,690 >> Dan pertama, yang ingin menyertai dalam lukisan ini? 1142 00:50:05,690 --> 00:50:09,630 OK, sekarang yang menjadikan ia lebih menyeronokkan. 1143 00:50:09,630 --> 00:50:14,010 Orang yang menerima ini 25-gigabit kod kupon - yang jauh 1144 00:50:14,010 --> 00:50:16,150 lebih menarik daripada lewat hari kini, mungkin - 1145 00:50:16,150 --> 00:50:20,620 adalah orang yang duduk di atas kusyen kerusi yang mengalir di bawahnya ada 1146 00:50:20,620 --> 00:50:21,620 kod kupon. 1147 00:50:21,620 --> 00:50:23,480 Anda kini boleh melihat di bawah kusyen tempat duduk anda. 1148 00:50:23,480 --> 00:50:28,710 1149 00:50:28,710 --> 00:50:29,680 >> [MAIN SEMULA VIDEO] 1150 00:50:29,680 --> 00:50:31,620 >> Satu, dua, tiga. 1151 00:50:31,620 --> 00:50:35,015 >> [Menjerit] 1152 00:50:35,015 --> 00:50:35,985 >> -Anda akan mendapat kereta! 1153 00:50:35,985 --> 00:50:36,670 Anda akan mendapat kereta! 1154 00:50:36,670 --> 00:50:37,970 >> DAVID MALAN: Kita akan melihat anda pada Rabu. 1155 00:50:37,970 --> 00:50:38,904 >> -Anda akan mendapat kereta! 1156 00:50:38,904 --> 00:50:39,371 Anda akan mendapat kereta! 1157 00:50:39,371 --> 00:50:40,305 Anda akan mendapat kereta! 1158 00:50:40,305 --> 00:50:41,706 Anda akan mendapat kereta! 1159 00:50:41,706 --> 00:50:43,107 Anda akan mendapat kereta! 1160 00:50:43,107 --> 00:50:45,530 >> DAVID MALAN: orang beranda, datang ke sini ke hadapan, 1161 00:50:45,530 --> 00:50:46,866 di mana kita mempunyai tambahan. 1162 00:50:46,866 --> 00:50:50,282 >> -Semua orang mendapat kereta! 1163 00:50:50,282 --> 00:50:52,234 Semua orang mendapat kereta! 1164 00:50:52,234 --> 00:50:52,722 >> [AKHIR VIDEO MAIN SEMULA] 1165 00:50:52,722 --> 00:50:54,590 >> Pencerita: Pada CS50 seterusnya - 1166 00:50:54,590 --> 00:51:00,374 >> SPEAKER 5: Oh cuilah duilah Astaga Astaga Astaga Astaga Astaga Astaga Astaga Astaga - 1167 00:51:00,374 --> 00:51:02,106 >> [Memainkan UKELELE]