1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [MUSIC PLAYING] 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 Minggu 4, awal daripadanya, sudah. 6 00:00:18,120 --> 00:00:21,320 Dan Anda akan ingat bahwa minggu lalu, kami menempatkan kode disisihkan untuk hanya sedikit 7 00:00:21,320 --> 00:00:24,240 dan kami mulai berbicara lebih sedikit tingkat tinggi, hal-hal seperti 8 00:00:24,240 --> 00:00:28,130 pencarian dan menyortir, yang meskipun ide yang agak sederhana, yang 9 00:00:28,130 --> 00:00:31,840 perwakilan dari kelas masalah Anda akan mulai untuk memecahkan khususnya 10 00:00:31,840 --> 00:00:34,820 setelah Anda mulai berpikir tentang akhir proyek dan solusi yang menarik Anda 11 00:00:34,820 --> 00:00:36,760 mungkin harus masalah di dunia nyata. 12 00:00:36,760 --> 00:00:39,490 Sekarang bubble sort adalah salah satu yang paling sederhana algoritma tersebut, dan 13 00:00:39,490 --> 00:00:42,900 bekerja dengan memiliki angka-angka kecil dalam daftar atau dalam bentuk array 14 00:00:42,900 --> 00:00:46,530 gelembung jalan mereka ke atas, dan jumlah besar bergerak dengan cara mereka ke 15 00:00:46,530 --> 00:00:47,930 akhir daftar itu. 16 00:00:47,930 --> 00:00:50,650 >> Dan ingat bahwa kita bisa membayangkan bubble sort sedikit 17 00:00:50,650 --> 00:00:52,310 sesuatu seperti ini. 18 00:00:52,310 --> 00:00:53,640 Jadi biarkan aku pergi ke depan dan klik Start. 19 00:00:53,640 --> 00:00:55,350 Aku sudah dipilih sebelumnya bubble sort. 20 00:00:55,350 --> 00:00:58,920 Dan jika Anda ingat bahwa tinggi biru garis mewakili angka yang besar, kecil 21 00:00:58,920 --> 00:01:03,300 garis biru mewakili angka kecil, seperti kita melalui ini lagi dan lagi dan 22 00:01:03,300 --> 00:01:07,680 lagi, membandingkan dua bar sebelah setiap lainnya dalam warna merah, kita akan menukar 23 00:01:07,680 --> 00:01:11,010 terbesar dan terkecil jika mereka rusak. 24 00:01:11,010 --> 00:01:14,150 >> Jadi ini akan terus dan terus dan pergi , dan Anda akan melihat bahwa semakin besar 25 00:01:14,150 --> 00:01:16,700 elemen yang membuat jalan mereka ke kanan, 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 Tapi kita mulai mengukur efisiensi, yang 28 00:01:21,380 --> 00:01:22,970 kualitas algoritma ini. 29 00:01:22,970 --> 00:01:25,200 Dan kita mengatakan bahwa yang terburuk kasus, algoritma ini mengambil 30 00:01:25,200 --> 00:01:27,940 kira-kira berapa banyak langkah? 31 00:01:27,940 --> 00:01:28,980 >> Jadi n kuadrat. 32 00:01:28,980 --> 00:01:30,402 Dan apa n? 33 00:01:30,402 --> 00:01:31,650 >> AUDIENCE: Jumlah elemen. 34 00:01:31,650 --> 00:01:32,790 >> DAVID Malan: Jadi n adalah jumlah elemen. 35 00:01:32,790 --> 00:01:33,730 Dan jadi kita akan melakukan hal ini sering. 36 00:01:33,730 --> 00:01:36,650 Setiap kali kita ingin berbicara tentang ukuran dari masalah atau ukuran 37 00:01:36,650 --> 00:01:39,140 masukan, atau jumlah waktu yang dibutuhkan untuk menghasilkan output, kita akan hanya 38 00:01:39,140 --> 00:01:41,610 umum apapun input adalah sebagai n. 39 00:01:41,610 --> 00:01:45,970 Jadi kembali pada Minggu 0, halaman nomor dalam buku telepon adalah n. 40 00:01:45,970 --> 00:01:47,550 Jumlah mahasiswa di ruang n. 41 00:01:47,550 --> 00:01:49,630 Jadi di sini, juga, kita mengikuti pola. 42 00:01:49,630 --> 00:01:52,800 >> Sekarang n kuadrat tidak terlalu cepat, jadi kami mencoba untuk berbuat lebih baik. 43 00:01:52,800 --> 00:01:55,970 Dan jadi kita melihat beberapa algoritma lain, di antaranya 44 00:01:55,970 --> 00:01:57,690 adalah semacam seleksi. 45 00:01:57,690 --> 00:01:59,180 Jadi semacam seleksi sedikit berbeda. 46 00:01:59,180 --> 00:02:03,130 Itu hampir sederhana, saya berani mengatakan, dimana saya mulai pada awal 47 00:02:03,130 --> 00:02:06,740 daftar relawan kami dan aku hanya lagi dan lagi dan lagi pergi melalui 48 00:02:06,740 --> 00:02:10,060 daftar, mencabut terkecil elemen pada suatu waktu dan menempatkan dia atau 49 00:02:10,060 --> 00:02:13,040 nya di awal daftar. 50 00:02:13,040 --> 00:02:16,410 >> Tapi ini juga, sekali kita mulai berpikir melalui matematika dan lebih besar 51 00:02:16,410 --> 00:02:19,860 gambar, berpikir tentang berapa kali Aku akan bolak-balik dan kembali 52 00:02:19,860 --> 00:02:24,090 dan sebagainya, kami mengatakan dalam kasus terburuk, selection sort, juga, adalah apa? 53 00:02:24,090 --> 00:02:24,960 n kuadrat. 54 00:02:24,960 --> 00:02:27,490 Sekarang di dunia nyata, itu mungkin benar-benar menjadi sedikit lebih cepat. 55 00:02:27,490 --> 00:02:30,620 Karena sekali lagi, saya tidak harus menjaga backtracking setelah saya telah mengurutkan 56 00:02:30,620 --> 00:02:31,880 terkecil unsur. 57 00:02:31,880 --> 00:02:35,090 Tetapi jika kita berpikir tentang n sangat besar, dan jika Anda melakukan semacam keluar matematika sebagai 58 00:02:35,090 --> 00:02:39,170 Saya lakukan pada papan, dengan n kuadrat dikurangi sesuatu, segala sesuatu yang lain 59 00:02:39,170 --> 00:02:41,850 selain n kuadrat, setelah n akan benar-benar besar, tidak 60 00:02:41,850 --> 00:02:42,850 benar-benar peduli sebanyak. 61 00:02:42,850 --> 00:02:45,470 Jadi sebagai ilmuwan komputer, kita semacam menutup mata untuk yang lebih kecil 62 00:02:45,470 --> 00:02:49,220 faktor dan fokus hanya pada faktor dalam ekspresi yang akan membuat 63 00:02:49,220 --> 00:02:50,330 perbedaan terbesar. 64 00:02:50,330 --> 00:02:52,840 >> Nah, terakhir, kita melihat pada insertion sort. 65 00:02:52,840 --> 00:02:56,620 Dan ini adalah serupa dalam roh, tetapi daripada pergi melalui iteratif dan 66 00:02:56,620 --> 00:03:01,250 pilih elemen terkecil pada waktu, saya malah mengambil tangan saya 67 00:03:01,250 --> 00:03:04,070 ditangani, dan saya memutuskan, semua benar, Anda berada di sini. 68 00:03:04,070 --> 00:03:06,160 Kemudian saya pindah ke elemen berikutnya dan memutuskan bahwa ia atau 69 00:03:06,160 --> 00:03:07,470 dia berada di sini. 70 00:03:07,470 --> 00:03:08,810 Dan kemudian aku pindah dan terus. 71 00:03:08,810 --> 00:03:11,780 Dan saya mungkin untuk, sepanjang jalan, menggeser orang-orang untuk 72 00:03:11,780 --> 00:03:13,030 membuat ruang bagi mereka. 73 00:03:13,030 --> 00:03:16,880 Jadi itu semacam pembalikan jiwa semacam seleksi yang kita 74 00:03:16,880 --> 00:03:18,630 disebut insertion sort. 75 00:03:18,630 --> 00:03:20,810 >> Jadi topik ini terjadi di dunia nyata. 76 00:03:20,810 --> 00:03:23,640 Hanya beberapa tahun yang lalu, ketika tertentu senator mencalonkan diri sebagai presiden, 77 00:03:23,640 --> 00:03:27,160 Eric Schmidt, pada saat CEO Google, benar-benar memiliki kesempatan 78 00:03:27,160 --> 00:03:28,040 mewawancarainya. 79 00:03:28,040 --> 00:03:32,010 Dan kami pikir kami akan berbagi YouTube ini klip untuk Anda di sini, jika kita bisa muncul 80 00:03:32,010 --> 00:03:32,950 volume. 81 00:03:32,950 --> 00:03:39,360 >> [VIDEO PEMUTARAN] 82 00:03:39,360 --> 00:03:44,620 >> -Sekarang, Senator, kau di sini di Google, dan saya suka berpikir tentang presiden 83 00:03:44,620 --> 00:03:46,042 sebagai wawancara kerja. 84 00:03:46,042 --> 00:03:47,770 >> [Tertawa] 85 00:03:47,770 --> 00:03:50,800 >> -Sekarang sulit untuk mendapatkan pekerjaan sebagai presiden. 86 00:03:50,800 --> 00:03:52,480 Dan Anda akan melalui kerasnya sekarang. 87 00:03:52,480 --> 00:03:54,330 Ini juga sulit untuk mendapatkan pekerjaan di Google. 88 00:03:54,330 --> 00:03:59,610 Kami memiliki pertanyaan dan kami meminta kami pertanyaan kandidat. 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 >> [Tertawa] 91 00:04:05,325 --> 00:04:06,400 -Kalian pikir aku bercanda? 92 00:04:06,400 --> 00:04:08,750 Ada di sini. 93 00:04:08,750 --> 00:04:12,110 Apa cara yang paling efisien untuk mengurutkan bilangan bulat dua juta-bit? 94 00:04:12,110 --> 00:04:15,810 >> [Tertawa] 95 00:04:15,810 --> 00:04:18,260 >> -Well, uh - 96 00:04:18,260 --> 00:04:19,029 >> -Maafkan aku. 97 00:04:19,029 --> 00:04:19,745 Mungkin kita harus - 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 - 100 00:04:21,470 --> 00:04:22,185 OK. 101 00:04:22,185 --> 00:04:25,328 >> -Saya pikir semacam gelembung akan menjadi cara yang salah untuk pergi. 102 00:04:25,328 --> 00:04:26,792 >> [Tertawa] 103 00:04:26,792 --> 00:04:28,510 >> [Bersorak DAN Tepuk Tangan] 104 00:04:28,510 --> 00:04:31,211 >> -Ayolah, yang mengatakan kepadanya ini? 105 00:04:31,211 --> 00:04:32,155 OK. 106 00:04:32,155 --> 00:04:33,350 >> [END VIDEO PEMUTARAN] 107 00:04:33,350 --> 00:04:35,070 >> DAVID Malan: Jadi di sana Anda memilikinya. 108 00:04:35,070 --> 00:04:39,600 Jadi kita mulai untuk mengukur ini berjalan kali, sehingga untuk berbicara, dengan sesuatu 109 00:04:39,600 --> 00:04:43,480 disebut notasi asimtotik, yang hanya mengacu semacam kami untuk mengubah 110 00:04:43,480 --> 00:04:47,420 mata terhadap faktor-faktor yang lebih kecil dan hanya melihat pada saat berjalan, 111 00:04:47,420 --> 00:04:51,250 kinerja algoritma ini, sebagai n jadi sangat besar dari waktu ke waktu. 112 00:04:51,250 --> 00:04:55,110 Dan jadi kami memperkenalkan big O. Dan O besar mewakili sesuatu yang kita pikir 113 00:04:55,110 --> 00:04:57,000 sebagai batas atas. 114 00:04:57,000 --> 00:04:59,570 Dan sebenarnya, Barry, bisa kita menurunkan dari mic sedikit? 115 00:04:59,570 --> 00:05:01,040 >> Kami pikir ini adalah batas atas. 116 00:05:01,040 --> 00:05:04,710 O begitu besar dari n berarti kuadrat bahwa dalam kasus terburuk, sesuatu seperti 117 00:05:04,710 --> 00:05:07,780 selection sort akan mengambil n langkah kuadrat. 118 00:05:07,780 --> 00:05:10,310 Atau sesuatu seperti insertion sort akan n langkah kuadrat. 119 00:05:10,310 --> 00:05:15,150 Sekarang untuk sesuatu seperti penyisipan semacam, apa kasus terburuk? 120 00:05:15,150 --> 00:05:18,200 Mengingat sebuah array, apa hal terburuk skenario yang mungkin bahwa Anda mungkin menemukan 121 00:05:18,200 --> 00:05:20,650 diri Anda dihadapkan dengan? 122 00:05:20,650 --> 00:05:21,860 >> Ini benar-benar mundur, kan? 123 00:05:21,860 --> 00:05:24,530 Karena jika itu benar-benar mundur, Anda harus melakukan banyak pekerjaan. 124 00:05:24,530 --> 00:05:26,420 Karena jika Anda benar-benar mundur, Anda akan menemukan 125 00:05:26,420 --> 00:05:28,840 elemen terbesar di sini, meskipun itu milik sana. 126 00:05:28,840 --> 00:05:31,140 Jadi Anda akan mengatakan, oke, pada saat ini dalam waktu, Anda berada di sini, 127 00:05:31,140 --> 00:05:32,310 sehingga Anda biarkan saja. 128 00:05:32,310 --> 00:05:35,425 >> Lalu Anda menyadari, oh, sialan, aku harus memindahkan elemen 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 Lalu aku harus melakukannya lagi dan lagi dan lagi. 131 00:05:38,770 --> 00:05:41,410 Dan jika aku berjalan bolak-balik, Anda akan semacam merasa kinerja 132 00:05:41,410 --> 00:05:45,540 algoritma itu, karena terus aku menyeret orang lain ke dalam 133 00:05:45,540 --> 00:05:46,510 array untuk membuat ruang untuk itu. 134 00:05:46,510 --> 00:05:47,750 Jadi itulah kasus terburuk. 135 00:05:47,750 --> 00:05:48,570 >> Sebaliknya - 136 00:05:48,570 --> 00:05:50,320 dan ini adalah Cliffhanger terakhir kali - 137 00:05:50,320 --> 00:05:54,065 kita mengatakan bahwa insertion sort adalah omega apa? 138 00:05:54,065 --> 00:05:57,530 Apa menjalankan kasus terbaik waktu insertion sort? 139 00:05:57,530 --> 00:05:58,520 Jadi itu benar-benar n. 140 00:05:58,520 --> 00:06:00,980 Itu adalah kosong yang kami meninggalkan di papan terakhir kali. 141 00:06:00,980 --> 00:06:03,160 >> Dan itu omega n karena mengapa? 142 00:06:03,160 --> 00:06:06,630 Nah, dalam kasus terbaik, apa insertion sort akan diserahkan? 143 00:06:06,630 --> 00:06:09,830 Nah, daftar yang benar-benar diurutkan sudah, pekerjaan minimal yang dapat dilakukan. 144 00:06:09,830 --> 00:06:12,460 Tapi apa yang rapi tentang insertion sort adalah bahwa karena itu dimulai di sini dan 145 00:06:12,460 --> 00:06:15,340 memutuskan, oh, Anda adalah nomor satu, Anda berada di sini. 146 00:06:15,340 --> 00:06:16,970 Oh, apa keberuntungan. 147 00:06:16,970 --> 00:06:17,740 >> Kau nomor dua. 148 00:06:17,740 --> 00:06:19,030 Anda juga termasuk di sini. 149 00:06:19,030 --> 00:06:21,010 Nomor tiga, bahkan lebih baik, Anda berada di sini. 150 00:06:21,010 --> 00:06:25,210 Begitu sampai ke ujung pseudocode daftar, per insertion sort ini 151 00:06:25,210 --> 00:06:28,010 bahwa kami berjalan melalui lisan terakhir kali, hal itu dilakukan. 152 00:06:28,010 --> 00:06:32,790 Tapi semacam seleksi, sebaliknya, terus melakukan apa? 153 00:06:32,790 --> 00:06:35,260 >> Terus melalui daftar lagi dan lagi dan lagi. 154 00:06:35,260 --> 00:06:39,160 Karena wawasan kunci hanya ada setelah Anda telah melihat semua jalan ke 155 00:06:39,160 --> 00:06:42,500 akhir daftar Anda bisa yakin bahwa elemen yang Anda pilih adalah 156 00:06:42,500 --> 00:06:45,560 memang elemen terkecil saat ini. 157 00:06:45,560 --> 00:06:48,920 Jadi ini berbeda mental yang model akhir sampai menghasilkan beberapa dunia nyata sangat 158 00:06:48,920 --> 00:06:53,130 perbedaan bagi kami, serta ini teoritis perbedaan asimtotik. 159 00:06:53,130 --> 00:06:56,910 >> Jadi hanya untuk rekap, maka, O besar n kuadrat, kami telah melihat beberapa seperti 160 00:06:56,910 --> 00:06:58,350 algoritma sejauh ini. 161 00:06:58,350 --> 00:06:59,580 Big O n? 162 00:06:59,580 --> 00:07:02,870 Apakah yang dimaksud dengan algoritma yang bisa dikatakan O besar n? 163 00:07:02,870 --> 00:07:06,930 Dalam kasus terburuk, dibutuhkan sejumlah linear langkah. 164 00:07:06,930 --> 00:07:07,810 >> OK, pencarian linear. 165 00:07:07,810 --> 00:07:10,470 Dan dalam kasus terburuk, di mana elemen yang Anda cari ketika 166 00:07:10,470 --> 00:07:12,950 menerapkan pencarian linear? 167 00:07:12,950 --> 00:07:14,680 >> OK, dalam kasus terburuk, itu bahkan tidak ada. 168 00:07:14,680 --> 00:07:17,000 Atau dalam kasus terburuk kedua, itu sepanjang jalan pada akhirnya, yang 169 00:07:17,000 --> 00:07:18,880 plus atau minus perbedaan satu langkah. 170 00:07:18,880 --> 00:07:21,180 Jadi pada akhir hari, kita dapat mengatakan itu linear. 171 00:07:21,180 --> 00:07:23,910 Big O n akan pencarian linear, karena dalam kasus terburuk, 172 00:07:23,910 --> 00:07:26,610 elemen bahkan tidak ada atau itu semua jalan di ujung. 173 00:07:26,610 --> 00:07:29,370 >> Nah, O besar log n. 174 00:07:29,370 --> 00:07:32,760 Kami tidak berbicara dengan sangat rinci tentang ini, tapi kami sudah melihat ini sebelumnya. 175 00:07:32,760 --> 00:07:36,840 Apa yang berjalan dalam apa yang disebut logaritmik waktu, dalam kasus terburuk? 176 00:07:36,840 --> 00:07:38,500 >> Ya, pencarian agar biner. 177 00:07:38,500 --> 00:07:42,930 Dan pencarian biner dalam kasus terburuk mungkin memiliki elemen di suatu tempat di 178 00:07:42,930 --> 00:07:45,640 tengah, atau di suatu tempat dalam array. 179 00:07:45,640 --> 00:07:48,040 Tapi Anda hanya menemukannya sekali Anda membagi daftar dua, di 180 00:07:48,040 --> 00:07:48,940 setengah, setengah, setengah. 181 00:07:48,940 --> 00:07:50,200 Dan kemudian voila, itu ada. 182 00:07:50,200 --> 00:07:52,500 Atau lagi, kasus terburuk, itu bahkan tidak ada. 183 00:07:52,500 --> 00:07:56,770 Tapi Anda tidak tahu bahwa itu tidak ada sampai Anda mencapai semacam yang lalu 184 00:07:56,770 --> 00:08:00,470 paling bawah elemen dengan mengurangi separuh dan mengurangi separuh dan pemangkasan. 185 00:08:00,470 --> 00:08:01,400 >> Big O dari 1. 186 00:08:01,400 --> 00:08:03,540 Jadi kita bisa O besar 2, O besar dari 3. 187 00:08:03,540 --> 00:08:06,260 Setiap kali Anda ingin hanya nomor konstan, kita hanya semacam hanya menyederhanakan 188 00:08:06,260 --> 00:08:07,280 bahwa O besar 1. 189 00:08:07,280 --> 00:08:10,440 Meskipun jika realistis, dibutuhkan 2 atau bahkan 100 langkah, jika itu adalah 190 00:08:10,440 --> 00:08:13,680 jumlah konstan langkah, kita hanya mengatakan O besar 1. 191 00:08:13,680 --> 00:08:15,930 Apakah yang dimaksud dengan algoritma yang di O besar dari 1? 192 00:08:15,930 --> 00:08:18,350 >> AUDIENCE: Menemukan panjang dari variabel. 193 00:08:18,350 --> 00:08:21,090 >> DAVID Malan: Menemukan panjang variabel? 194 00:08:21,090 --> 00:08:23,870 >> AUDIENCE: Tidak, panjang jika sudah diurutkan. 195 00:08:23,870 --> 00:08:24,160 >> DAVID Malan: Baik. 196 00:08:24,160 --> 00:08:27,850 OK, sehingga menemukan sesuatu yang panjang jika panjang sesuatu yang, seperti 197 00:08:27,850 --> 00:08:30,020 array, disimpan dalam beberapa variabel. 198 00:08:30,020 --> 00:08:33,380 Karena Anda hanya dapat membaca variabel, atau mencetak variabel, atau 199 00:08:33,380 --> 00:08:34,960 umumnya hanya mengakses variabel tersebut. 200 00:08:34,960 --> 00:08:37,299 Dan voila, yang membutuhkan waktu konstan. 201 00:08:37,299 --> 00:08:38,909 >> Sebaliknya, pikirkan kembali untuk menggaruk. 202 00:08:38,909 --> 00:08:42,460 Pikirkan kembali ke minggu pertama C, menelepon hanya printf dan pencetakan 203 00:08:42,460 --> 00:08:46,240 sesuatu di layar ini bisa dibilang waktu yang konstan, karena hanya membutuhkan 204 00:08:46,240 --> 00:08:50,880 beberapa jumlah siklus CPU untuk menunjukkan bahwa teks pada layar. 205 00:08:50,880 --> 00:08:52,720 Atau menunggu - apakah itu? 206 00:08:52,720 --> 00:08:56,430 Bagaimana lagi kita mungkin model kinerja printf? 207 00:08:56,430 --> 00:09:00,420 Apakah seseorang ingin setuju, bahwa mungkin itu bukan waktu yang sangat konstan? 208 00:09:00,420 --> 00:09:03,600 Dalam arti mungkin printf yang berjalan waktu, benar-benar mencetak string pada 209 00:09:03,600 --> 00:09:05,580 layar, menjadi sesuatu selain konstan. 210 00:09:05,580 --> 00:09:07,860 >> AUDIENCE: [Tak terdengar]. 211 00:09:07,860 --> 00:09:08,230 >> DAVID Malan: Ya. 212 00:09:08,230 --> 00:09:09,300 Jadi itu tergantung pada perspektif kita. 213 00:09:09,300 --> 00:09:13,390 Jika kita benar-benar berpikir dari input ke printf sebagai string, dan 214 00:09:13,390 --> 00:09:16,380 karena itu kami mengukur ukuran yang input dengan panjang - jadi mari kita sebut 215 00:09:16,380 --> 00:09:17,780 bahwa panjang n juga - 216 00:09:17,780 --> 00:09:21,990 bisa dibilang, printf itu sendiri O besar n karena itu akan membawa Anda langkah n 217 00:09:21,990 --> 00:09:24,750 untuk mencetak masing-masing n karakter, yang paling mungkin. 218 00:09:24,750 --> 00:09:27,730 Setidaknya sejauh yang kita asumsikan bahwa mungkin itu menggunakan untuk loop 219 00:09:27,730 --> 00:09:28,560 bawah tenda. 220 00:09:28,560 --> 00:09:30,860 >> Tapi kita harus lihat itu kode untuk memahami dengan lebih baik. 221 00:09:30,860 --> 00:09:33,650 Dan memang, setelah kalian mulai menganalisis algoritma Anda sendiri, Anda akan 222 00:09:33,650 --> 00:09:34,900 harfiah melakukan hal itu. 223 00:09:34,900 --> 00:09:37,765 Urutkan bola mata kode Anda dan berpikir tentang - baik-baik saja, saya punya lingkaran ini 224 00:09:37,765 --> 00:09:41,870 sini atau saya memiliki loop bersarang di sini, yang akan melakukan hal-hal n n kali, 225 00:09:41,870 --> 00:09:46,050 dan Anda dapat semacam alasan cara Anda melalui kode, bahkan jika itu 226 00:09:46,050 --> 00:09:47,980 pseudocode dan bukan kode yang sebenarnya. 227 00:09:47,980 --> 00:09:49,730 >> Jadi apa tentang omega kuadrat dari n? 228 00:09:49,730 --> 00:09:53,582 Apa algoritma yang dalam terbaik kasus, masih mengambil langkah n kuadrat? 229 00:09:53,582 --> 00:09:54,014 Ya? 230 00:09:54,014 --> 00:09:54,880 >> AUDIENCE: [Tak terdengar]. 231 00:09:54,880 --> 00:09:55,900 >> DAVID Malan: Jadi pemilihan jenis. 232 00:09:55,900 --> 00:09:59,150 Karena dalam masalah yang benar-benar berkurang dengan fakta itu lagi, saya tidak tahu 233 00:09:59,150 --> 00:10:02,600 Saya telah menemukan terkecil saat ini sampai Aku sudah memeriksa semua elemen sialan. 234 00:10:02,600 --> 00:10:08,050 Jadi omega, katakanlah, n, kita hanya datang dengan satu. 235 00:10:08,050 --> 00:10:09,300 Insertion sort. 236 00:10:09,300 --> 00:10:12,370 Jika daftar kebetulan diurutkan sudah, dalam kasus terbaik kita hanya 237 00:10:12,370 --> 00:10:15,090 untuk membuat satu lulus melalui itu, di mana titik kami yakin. 238 00:10:15,090 --> 00:10:17,890 Dan kemudian yang bisa dikatakan harus linier, pasti. 239 00:10:17,890 --> 00:10:20,570 >> Bagaimana omega dari 1? 240 00:10:20,570 --> 00:10:23,790 Apa, dalam kasus terbaik, mungkin mengambil sejumlah konstan langkah? 241 00:10:23,790 --> 00:10:27,220 Jadi pencarian linear, jika Anda hanya beruntung dan unsur yang Anda cari 242 00:10:27,220 --> 00:10:31,000 tepat di awal daftar, kalau itu di mana Anda memulai Anda 243 00:10:31,000 --> 00:10:33,070 linear traversal dari daftar itu. 244 00:10:33,070 --> 00:10:35,180 >> Dan ini benar dari beberapa hal. 245 00:10:35,180 --> 00:10:37,660 Sebagai contoh, bahkan biner pencarian omega dari 1. 246 00:10:37,660 --> 00:10:40,310 Karena apa jika Anda mendapatkan benar-benar sangat beruntung dan memukul-oleskan di tengah 247 00:10:40,310 --> 00:10:42,950 array adalah nomor Anda sedang mencari? 248 00:10:42,950 --> 00:10:45,730 Jadi Anda bisa mendapatkan beruntung di sana, juga. 249 00:10:45,730 --> 00:10:49,190 >> Yang satu ini, terakhir, omega n log n. 250 00:10:49,190 --> 00:10:52,573 Jadi n log n, kita tidak benar-benar berbicara tentang, tapi - 251 00:10:52,573 --> 00:10:53,300 >> AUDIENCE: Merge sort? 252 00:10:53,300 --> 00:10:53,960 >> DAVID Malan: Merge sort. 253 00:10:53,960 --> 00:10:56,920 Itu cliffhanger dari terakhir kali, di mana kita mengusulkan, dan kami menunjukkan 254 00:10:56,920 --> 00:10:58,600 visual, bahwa ada algoritma. 255 00:10:58,600 --> 00:11:02,470 Dan menggabungkan semacam hanya satu seperti algoritma yang secara fundamental lebih cepat 256 00:11:02,470 --> 00:11:03,450 dari beberapa orang-orang lainnya. 257 00:11:03,450 --> 00:11:07,800 Bahkan, menggabungkan pendek tidak hanya di kasus terbaik n log n, di terburuk 258 00:11:07,800 --> 00:11:09,460 kasus n log n. 259 00:11:09,460 --> 00:11:14,540 Dan ketika Anda memiliki kebetulan ini omega dan O besar menjadi hal yang sama? 260 00:11:14,540 --> 00:11:17,310 Kami benar-benar bisa menggambarkan bahwa apa yang disebut theta, meskipun itu adalah 261 00:11:17,310 --> 00:11:18,220 sedikit kurang umum. 262 00:11:18,220 --> 00:11:21,730 Tapi itu hanya berarti dua batas, dalam hal ini, adalah sama. 263 00:11:21,730 --> 00:11:25,770 >> Jadi menggabungkan semacam, apa ini benar-benar mendidih ke bagi kita? 264 00:11:25,770 --> 00:11:27,000 Nah, mengingat motivasi. 265 00:11:27,000 --> 00:11:30,340 Biarkan aku menarik animasi lain yang kita tidak melihat terakhir kali. 266 00:11:30,340 --> 00:11:33,390 Yang satu ini, ide yang sama, tetapi itu sedikit lebih besar. 267 00:11:33,390 --> 00:11:36,160 Dan aku akan pergi ke depan dan menunjukkan pertama - kami memiliki insertion sort pada 268 00:11:36,160 --> 00:11:39,410 kiri atas, maka pemilihan semacam, bubble sort, beberapa jenis lain - 269 00:11:39,410 --> 00:11:42,670 shell dan cepat - bahwa kita belum bicara tentang, dan tumpukan dan menggabungkan semacam. 270 00:11:42,670 --> 00:11:47,090 >> Jadi setidaknya mencoba untuk fokus mata Anda pada tiga di sebelah kiri dan kemudian 271 00:11:47,090 --> 00:11:49,120 menggabungkan semacam ketika saya klik ini panah hijau. 272 00:11:49,120 --> 00:11:51,900 Tapi aku akan membiarkan semua dari mereka menjalankan, hanya untuk memberikan rasa keragaman 273 00:11:51,900 --> 00:11:53,980 algoritma yang ada di dunia. 274 00:11:53,980 --> 00:11:56,180 Aku akan membiarkan menjalankan ini hanya beberapa detik. 275 00:11:56,180 --> 00:11:59,640 Dan jika Anda fokus mata Anda - memilih sebuah algoritma, fokus pada itu untuk hanya 276 00:11:59,640 --> 00:12:02,970 detik - Anda akan mulai melihat pola yang itu menerapkan. 277 00:12:02,970 --> 00:12:04,530 >> Merge sort, pemberitahuan, dilakukan. 278 00:12:04,530 --> 00:12:06,430 Heap sort, quick sort, shell - 279 00:12:06,430 --> 00:12:09,480 jadi sepertinya kami memperkenalkan tiga algoritma terburuk pekan lalu. 280 00:12:09,480 --> 00:12:12,960 Tapi itu baik bahwa kita di sini hari ini untuk melihat merge sort, yang merupakan salah satu 281 00:12:12,960 --> 00:12:16,500 yang lebih mudah adalah dengan melihat, bahkan meskipun mungkin akan menekuk pikiran Anda 282 00:12:16,500 --> 00:12:17,490 hanya sedikit. 283 00:12:17,490 --> 00:12:21,130 Di sini kita bisa melihat betapa selection sort menyebalkan. 284 00:12:21,130 --> 00:12:24,600 >> Tapi di sisi lain, itu sangat mudah untuk menerapkan. 285 00:12:24,600 --> 00:12:28,160 Dan mungkin untuk P Set 3, itulah salah satu algoritma Anda memilih untuk mengimplementasikan 286 00:12:28,160 --> 00:12:28,960 untuk edisi standar. 287 00:12:28,960 --> 00:12:30,970 Baik-baik saja, sempurna benar. 288 00:12:30,970 --> 00:12:35,210 >> Tapi sekali lagi, seperti n mendapat besar, jika Anda memilih untuk menerapkan algoritma yang lebih cepat 289 00:12:35,210 --> 00:12:39,020 seperti menggabungkan semacam, kemungkinan besar dalam yang lebih besar dan input yang lebih besar, kode Anda hanya 290 00:12:39,020 --> 00:12:39,800 akan berjalan lebih cepat. 291 00:12:39,800 --> 00:12:41,090 Website Anda akan bekerja lebih baik. 292 00:12:41,090 --> 00:12:42,650 Pengguna Anda akan lebih bahagia. 293 00:12:42,650 --> 00:12:45,280 Dan jadi ada efek ini untuk benar-benar memberikan 294 00:12:45,280 --> 00:12:47,350 kami beberapa berpikir lebih dalam. 295 00:12:47,350 --> 00:12:49,990 >> Jadi mari kita lihat apa yang menggabungkan semacam sebenarnya semua tentang. 296 00:12:49,990 --> 00:12:52,992 Yang keren adalah bahwa menggabungkan semacam ini hanya ini. 297 00:12:52,992 --> 00:12:56,300 Ini, sekali lagi, apa yang telah kita disebut pseudocode, makhluk pseudocode 298 00:12:56,300 --> 00:12:57,720 Inggris-seperti sintaks. 299 00:12:57,720 --> 00:12:59,890 Dan kesederhanaan adalah semacam menarik. 300 00:12:59,890 --> 00:13:02,840 >> Jadi pada masukan dari n elemen - sehingga hanya berarti, inilah sebuah array. 301 00:13:02,840 --> 00:13:04,000 Itu punya hal-hal n di dalamnya. 302 00:13:04,000 --> 00:13:05,370 Itu semua kita mengatakan ada. 303 00:13:05,370 --> 00:13:07,560 >> Jika n kurang dari 2, kembali. 304 00:13:07,560 --> 00:13:08,640 Jadi itu hanya kasus sepele. 305 00:13:08,640 --> 00:13:12,580 Jika n kurang dari 2, maka jelas itu 1 atau 0, dalam hal hal 306 00:13:12,580 --> 00:13:14,780 sudah diurutkan atau tidak ada, jadi hanya kembali. 307 00:13:14,780 --> 00:13:15,900 Tidak ada yang dapat dilakukan. 308 00:13:15,900 --> 00:13:18,360 Jadi itu kasus sederhana untuk merobek. 309 00:13:18,360 --> 00:13:20,110 >> Lain, kita memiliki tiga langkah. 310 00:13:20,110 --> 00:13:23,650 Urutkan kiri setengah dari elemen, semacam bagian kanan elemen, 311 00:13:23,650 --> 00:13:26,650 dan kemudian menggabungkan bagian diurutkan. 312 00:13:26,650 --> 00:13:29,400 Apa yang menarik di sini adalah bahwa Aku agak punting, kan? 313 00:13:29,400 --> 00:13:32,300 Ada semacam definisi melingkar algoritma ini. 314 00:13:32,300 --> 00:13:35,986 Dalam arti apakah algoritma ini melingkar definisi? 315 00:13:35,986 --> 00:13:37,850 >> AUDIENCE: [Tak terdengar]. 316 00:13:37,850 --> 00:13:41,670 >> DAVID Malan: Ya, algoritma sorting saya, dua langkah perusahaan adalah "semacam 317 00:13:41,670 --> 00:13:44,640 sesuatu. "Dan sehingga menimbulkan pertanyaan, baik, apa yang akan saya gunakan 318 00:13:44,640 --> 00:13:46,460 untuk menyortir kiri setengah dan bagian kanan? 319 00:13:46,460 --> 00:13:49,600 Dan keindahan di sini adalah bahwa meskipun lagi, ini adalah pikiran-lipatan 320 00:13:49,600 --> 00:13:54,030 Bagian berpotensi, Anda dapat menggunakan yang sama algoritma untuk mengurutkan kiri setengah. 321 00:13:54,030 --> 00:13:54,700 >> Tapi tunggu sebentar. 322 00:13:54,700 --> 00:13:57,070 Ketika Anda diminta untuk mengurutkan kiri setengah, apa dua 323 00:13:57,070 --> 00:13:58,240 langkah akan selanjutnya? 324 00:13:58,240 --> 00:14:00,550 Kita akan mengurutkan kiri setengah dari setengah kiri dan kanan 325 00:14:00,550 --> 00:14:01,420 setengah dari kiri setengah. 326 00:14:01,420 --> 00:14:04,430 Sialan, bagaimana cara saya mengurutkan dua bagian, atau tempat, sekarang? 327 00:14:04,430 --> 00:14:05,260 >> Tapi itu OK. 328 00:14:05,260 --> 00:14:07,830 Kami memiliki algoritma sorting sini. 329 00:14:07,830 --> 00:14:10,660 Dan meskipun Anda mungkin khawatir pada pertama ini adalah jenis tak terbatas 330 00:14:10,660 --> 00:14:12,780 lingkaran, itu adalah siklus yang tidak pernah akan berakhir - itu akan 331 00:14:12,780 --> 00:14:15,770 berakhir setelah apa yang terjadi? 332 00:14:15,770 --> 00:14:16,970 Setelah n kurang dari 2. 333 00:14:16,970 --> 00:14:19,180 Yang akhirnya akan terjadi, karena jika Anda terus mengurangi separuh dan 334 00:14:19,180 --> 00:14:23,020 mengurangi separuh mengurangi separuh bagian 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 Pada saat itu, algoritma ini mengatakan Anda sudah selesai. 337 00:14:28,500 --> 00:14:31,020 >> Jadi sihir yang nyata dalam hal ini algoritma tampaknya berada di 338 00:14:31,020 --> 00:14:33,470 langkah terakhir, penggabungan. 339 00:14:33,470 --> 00:14:37,190 Itu ide yang sederhana hanya penggabungan dua hal, itulah yang akhirnya akan 340 00:14:37,190 --> 00:14:40,920 untuk memungkinkan kita untuk mengurutkan array, katakanlah, delapan elemen. 341 00:14:40,920 --> 00:14:44,410 Jadi saya memiliki delapan bola stres lebih up di sini, delapan lembar 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 bisa tetap. 344 00:14:46,140 --> 00:14:46,960 >> [Tertawa] 345 00:14:46,960 --> 00:14:48,970 >> DAVID Malan: Jika kita bisa mengambil delapan relawan, dan mari kita lihat apakah kita bisa 346 00:14:48,970 --> 00:14:51,430 memainkan permainan ini keluar, jadi. 347 00:14:51,430 --> 00:14:52,500 Wow, OK. 348 00:14:52,500 --> 00:14:53,565 Ilmu komputer semakin menyenangkan. 349 00:14:53,565 --> 00:14:54,320 Baik. 350 00:14:54,320 --> 00:14:57,770 Jadi bagaimana dengan 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 kita akan melakukannya Anda tiga berturut-turut ini? 353 00:15:02,220 --> 00:15:03,390 Dan empat di depan. 354 00:15:03,390 --> 00:15:04,920 Jadi Anda delapan, datang ke atas. 355 00:15:04,920 --> 00:15:12,060 >> [Tertawa] 356 00:15:12,060 --> 00:15:13,450 >> DAVID Malan: Aku sebenarnya tidak yakin apa itu. 357 00:15:13,450 --> 00:15:14,810 Apakah bola stres? 358 00:15:14,810 --> 00:15:16,510 Lampu meja? 359 00:15:16,510 --> 00:15:18,650 Materi? 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 ke atas. 363 00:15:21,310 --> 00:15:22,310 Siapa yang mau - 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 menempatkan Anda di lokasi - 367 00:15:26,460 --> 00:15:27,940 Anda berada di satu lokasi. 368 00:15:27,940 --> 00:15:28,670 Uh-oh, tunggu dulu. 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 baik. 371 00:15:31,310 --> 00:15:35,130 Baiklah, sehingga semua orang memiliki kursi, tapi tidak pada Google Glass. 372 00:15:35,130 --> 00:15:36,475 Biarkan aku mengantri tersebut. 373 00:15:36,475 --> 00:15:37,115 Siapa 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 bisa terlihat seperti geek, kalau itu OK. 377 00:15:42,000 --> 00:15:44,625 Yah, saya lakukan juga, saya kira, untuk sesaat. 378 00:15:44,625 --> 00:15:45,875 Baiklah, standby. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Kami sudah mencoba untuk datang dengan menggunakan kasus untuk Google Glass, dan kami 381 00:15:50,950 --> 00:15:53,750 pikir akan menyenangkan untuk hanya melakukan ini ketika orang-orang di atas panggung. 382 00:15:53,750 --> 00:15:57,120 Kami akan merekam dunia dari sudut pandang mereka. 383 00:15:57,120 --> 00:15:58,410 Baik. 384 00:15:58,410 --> 00:15:59,830 Tidak mungkin apa yang dimaksudkan Google. 385 00:15:59,830 --> 00:16:02,260 Baiklah, jika Anda tidak keberatan memakai ini untuk menit berikutnya canggung, 386 00:16:02,260 --> 00:16:03,150 itu akan menjadi indah. 387 00:16:03,150 --> 00:16:08,620 >> Baiklah, sehingga kita memiliki sebuah array elemen, dan bahwa array, sesuai dengan 388 00:16:08,620 --> 00:16:11,480 potongan kertas di orang-orang ini ' tangan, saat ini dipilah. 389 00:16:11,480 --> 00:16:12,050 >> MICHELLE: Oh, itu kan aneh. 390 00:16:12,050 --> 00:16:12,810 >> DAVID Malan: Ini cukup banyak acak. 391 00:16:12,810 --> 00:16:15,760 Dan hanya dalam beberapa saat, kita akan mencoba untuk melaksanakan menggabungkan semacam bersama-sama 392 00:16:15,760 --> 00:16:17,950 dan melihat mana yang Patut diketahui. 393 00:16:17,950 --> 00:16:21,970 Dan trik di sini dengan merge sort adalah sesuatu yang kita belum dianggap belum. 394 00:16:21,970 --> 00:16:24,030 Kami benar-benar membutuhkan beberapa ruang tambahan. 395 00:16:24,030 --> 00:16:26,650 Jadi apa yang akan menjadi sangat menarik tentang ini adalah bahwa 396 00:16:26,650 --> 00:16:29,270 orang ini akan bergerak di sekitar sedikit bit, karena aku akan berasumsi bahwa 397 00:16:29,270 --> 00:16:31,880 ada sebuah array tambahan ruang, mengatakan, tepat di belakang mereka. 398 00:16:31,880 --> 00:16:34,570 >> Jadi, jika mereka berada di belakang kursi mereka, itu array sekunder. 399 00:16:34,570 --> 00:16:36,960 Jika mereka duduk di sini, itu array primer. 400 00:16:36,960 --> 00:16:40,170 Tapi ini adalah sumber daya yang kita miliki tidak memanfaatkan sejauh ini dengan gelembung 401 00:16:40,170 --> 00:16:42,040 semacam, dengan semacam seleksi, dengan insertion sort. 402 00:16:42,040 --> 00:16:44,600 Ingat minggu lalu, semua orang hanya jenis beringsut di tempat. 403 00:16:44,600 --> 00:16:46,840 Mereka tidak menggunakan memori tambahan. 404 00:16:46,840 --> 00:16:49,310 Kami membuat ruang untuk orang-orang dengan memindahkan orang. 405 00:16:49,310 --> 00:16:50,580 >> Jadi ini adalah wawasan kunci, terlalu. 406 00:16:50,580 --> 00:16:53,410 Ada trade-off ini, secara umum dalam ilmu komputer, sumber daya. 407 00:16:53,410 --> 00:16:55,800 Jika Anda ingin mempercepat sesuatu seperti waktu, Anda akan 408 00:16:55,800 --> 00:16:56,900 harus membayar harga. 409 00:16:56,900 --> 00:17:00,750 Dan salah satu harga tersebut sangat sering ruang, jumlah memori atau hard 410 00:17:00,750 --> 00:17:01,700 ruang disk yang Anda gunakan. 411 00:17:01,700 --> 00:17:03,640 Atau, terus terang, jumlah waktu programmer. 412 00:17:03,640 --> 00:17:06,700 Berapa banyak waktu yang diperlukan, manusia, untuk benar-benar menerapkan lagi 413 00:17:06,700 --> 00:17:07,829 algoritma rumit. 414 00:17:07,829 --> 00:17:09,760 Tapi untuk hari ini, trade-off adalah waktu dan ruang. 415 00:17:09,760 --> 00:17:11,930 >> Jadi, jika kalian hanya bisa menahan Anda angka sehingga kita dapat melihat bahwa Anda 416 00:17:11,930 --> 00:17:15,839 memang pencocokan 4, 2, 6, 1, 3, 7, 8. 417 00:17:15,839 --> 00:17:16,599 Luar biasa. 418 00:17:16,599 --> 00:17:19,520 Jadi aku akan mencoba untuk mengatur hal, jika kalian bisa hanya 419 00:17:19,520 --> 00:17:21,800 mengikuti langkah saya di sini. 420 00:17:21,800 --> 00:17:26,650 >> Jadi saya akan mengimplementasikan, pertama, Langkah pertama pseudocode, yang merupakan 421 00:17:26,650 --> 00:17:29,440 pada masukan dari n elemen, jika n kurang dari 2, kemudian kembali. 422 00:17:29,440 --> 00:17:31,370 Jelas, yang tidak berlaku, jadi kami pindah. 423 00:17:31,370 --> 00:17:33,340 Jadi mengurutkan kiri setengah dari elemen. 424 00:17:33,340 --> 00:17:36,220 Jadi itu berarti aku akan fokus saya perhatian untuk hanya sejenak di ini 425 00:17:36,220 --> 00:17:37,310 empat orang di sini. 426 00:17:37,310 --> 00:17:39,774 Baiklah, apa yang harus saya lakukan selanjutnya? 427 00:17:39,774 --> 00:17:40,570 >> AUDIENCE: Urutkan kiri setengah. 428 00:17:40,570 --> 00:17:42,780 >> DAVID Malan: Jadi sekarang saya harus mengurutkan kiri setengah dari orang-orang ini. 429 00:17:42,780 --> 00:17:45,580 Karena sekali lagi, berasumsi untuk diri sendiri Tujuannya adalah untuk memilah kiri setengah. 430 00:17:45,580 --> 00:17:46,440 Bagaimana Anda melakukannya? 431 00:17:46,440 --> 00:17:49,140 Cukup ikuti petunjuk, bahkan meskipun kita melakukannya lagi. 432 00:17:49,140 --> 00:17:50,160 Jadi mengurutkan kiri setengah. 433 00:17:50,160 --> 00:17:52,030 Sekarang aku menyortir dua orang. 434 00:17:52,030 --> 00:17:53,563 Apa yang terjadi selanjutnya? 435 00:17:53,563 --> 00:17:54,510 >> AUDIENCE: Urutkan kiri setengah. 436 00:17:54,510 --> 00:17:55,460 >> DAVID Malan: Urutkan kiri setengah. 437 00:17:55,460 --> 00:18:00,680 Jadi sekarang ini, kursi ini di sini, adalah daftar ukuran 1. 438 00:18:00,680 --> 00:18:01,365 Dan siapa namamu 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 jadi dia sudah disortir, karena daftar adalah ukuran 1. 442 00:18:07,470 --> 00:18:09,490 Apa yang harus saya lakukan selanjutnya? 443 00:18:09,490 --> 00:18:13,680 OK, kembali, karena daftar itu adalah ukuran 1, yaitu kurang dari 2. 444 00:18:13,680 --> 00:18:14,320 Lalu apa langkah selanjutnya? 445 00:18:14,320 --> 00:18:17,490 Dan sekarang Anda harus jenis mundur dalam pikiran Anda. 446 00:18:17,490 --> 00:18:19,340 >> Urutkan bagian kanan, yang - 447 00:18:19,340 --> 00:18:19,570 siapa namamu? 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 apa yang kita lakukan sekarang kami memiliki daftar ukuran 1? 451 00:18:23,210 --> 00:18:24,440 >> AUDIENCE: Kembali. 452 00:18:24,440 --> 00:18:24,760 >> DAVID Malan: Hati-hati. 453 00:18:24,760 --> 00:18:29,540 Kita kembali dulu, dan sekarang ketiga langkah - dan jika aku agak menggambarkan dengan 454 00:18:29,540 --> 00:18:33,490 merangkul dua kursi sekarang, sekarang saya harus menggabungkan kedua elemen. 455 00:18:33,490 --> 00:18:35,530 Jadi sekarang sayangnya, elemen yang rusak. 456 00:18:35,530 --> 00:18:39,920 Tapi di situlah proses penggabungan mulai mendapatkan menarik. 457 00:18:39,920 --> 00:18:42,410 >> Jadi, jika kalian bisa berdiri untuk hanya Sesaat, aku akan membutuhkan Anda, dalam 458 00:18:42,410 --> 00:18:44,170 saat, untuk melangkah di belakang kursi Anda. 459 00:18:44,170 --> 00:18:46,480 Dan jika Linda, karena 2 adalah lebih kecil dari 4, kenapa 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 pada kenyataannya jika itu hanya sebuah array kita hanya bisa memindahkannya secara real time 464 00:18:53,820 --> 00:18:55,360 dari kursi ini ke tempat ini. 465 00:18:55,360 --> 00:18:57,770 Jadi bayangkan jika mengambil beberapa konstanta jumlah 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 menempatkan Anda dalam lokasi pertama di sini. 468 00:19:01,490 --> 00:19:03,930 >> Dan sekarang jika Anda bisa datang, 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 meskipun ini terasa seperti itu mengambil beberapa saat, apa yang bagus saat ini adalah 471 00:19:09,120 --> 00:19:14,710 bahwa kiri setengah dari kiri setengah sekarang diurutkan. 472 00:19:14,710 --> 00:19:18,010 Jadi apa langkah berikutnya, jika kita sekarang mundur lebih jauh dalam cerita itu? 473 00:19:18,010 --> 00:19:18,980 >> AUDIENCE: setengah Kanan. 474 00:19:18,980 --> 00:19:19,900 >> DAVID Malan: Urutkan kanan setengah. 475 00:19:19,900 --> 00:19:21,320 Jadi kalian harus melakukan ini, juga. 476 00:19:21,320 --> 00:19:23,510 Jadi, jika Anda bisa berdiri untuk sesaat? 477 00:19:23,510 --> 00:19:25,192 Dan siapa namamu? 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 sekarang kiri setengah dari setengah benar. 481 00:19:29,720 --> 00:19:31,400 Dan jadi dia daftar ukuran 1. 482 00:19:31,400 --> 00:19:32,380 Dia jelas diurutkan. 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 jelas daftar ukuran 1. 486 00:19:35,340 --> 00:19:36,050 Dia sudah diurutkan. 487 00:19:36,050 --> 00:19:38,690 Jadi sekarang keajaiban terjadi, proses penggabungan. 488 00:19:38,690 --> 00:19:39,790 Jadi siapa yang akan datang pertama? 489 00:19:39,790 --> 00:19:41,560 Jelas Michelle. 490 00:19:41,560 --> 00:19:43,280 Jadi, jika Anda bisa datang sekitar kembali. 491 00:19:43,280 --> 00:19:47,090 Ruang yang kita miliki untuk sekarang tepat di belakang kursi ini di sini. 492 00:19:47,090 --> 00:19:51,580 Dan sekarang jika Anda bisa kembali juga, kita sekarang memiliki, harus jelas, dua 493 00:19:51,580 --> 00:19:53,810 bagian, masing-masing ukuran 2 - 494 00:19:53,810 --> 00:19:57,090 dan hanya untuk kepentingan penggambaran itu, jika Anda bisa membuat sedikit ruang - 495 00:19:57,090 --> 00:19:59,780 satu kiri setengah di sini, satu setengah di sini. 496 00:19:59,780 --> 00:20:01,160 >> Rewind lanjut dalam cerita. 497 00:20:01,160 --> 00:20:02,270 Apa langkah selanjutnya? 498 00:20:02,270 --> 00:20:03,030 >> AUDIENCE: Gabung. 499 00:20:03,030 --> 00:20:04,160 >> DAVID Malan: Jadi sekarang kita harus bergabung. 500 00:20:04,160 --> 00:20:07,490 Jadi OK, jadi sekarang, untungnya, kami hanya membebaskan empat kursi. 501 00:20:07,490 --> 00:20:11,480 Jadi kita telah menggunakan dua kali lebih banyak memori, tetapi kami dapat memberikan flip-menjatuhkan diri antara 502 00:20:11,480 --> 00:20:12,330 dua array. 503 00:20:12,330 --> 00:20:14,190 Jadi nomor yang akan datang pertama? 504 00:20:14,190 --> 00:20:14,850 Jadi Michelle, jelas. 505 00:20:14,850 --> 00:20:16,680 Jadi datang dan mengambil duduk di sini. 506 00:20:16,680 --> 00:20:19,120 Dan kemudian nomor 2 jelas selanjutnya, sehingga Anda datang ke sini. 507 00:20:19,120 --> 00:20:21,520 Nomor 4, nomor 6. 508 00:20:21,520 --> 00:20:23,390 Dan lagi, meskipun ada sedikit berjalan terlibat, 509 00:20:23,390 --> 00:20:26,010 benar-benar, ini bisa terjadi secara instan, dengan memindahkan satu - 510 00:20:26,010 --> 00:20:26,880 OK, baik dimainkan. 511 00:20:26,880 --> 00:20:28,350 >> [Tertawa] 512 00:20:28,350 --> 00:20:29,680 >> DAVID Malan: Dan sekarang kita dalam kondisi yang cukup baik. 513 00:20:29,680 --> 00:20:34,910 Kiri setengah dari seluruh masukan sekarang telah diurutkan. 514 00:20:34,910 --> 00:20:37,370 Baiklah, jadi orang-orang ini memiliki keuntungan dari saya - 515 00:20:37,370 --> 00:20:40,340 bagaimana itu berakhir semua gadis di kiri dan semua anak laki-laki di sebelah kanan? 516 00:20:40,340 --> 00:20:42,450 >> OK, jadi orang-orang 'berbalik sekarang. 517 00:20:42,450 --> 00:20:44,680 Jadi saya tidak akan memandu Anda melalui langkah-langkah ini. 518 00:20:44,680 --> 00:20:46,550 Kita akan melihat apakah kita dapat mengajukan permohonan kembali pseudocode yang sama. 519 00:20:46,550 --> 00:20:50,050 Jika Anda ingin untuk terus maju dan berdiri, dan kalian, biarlah saya memberikan mic. 520 00:20:50,050 --> 00:20:52,990 Lihat jika Anda tidak bisa meniru apa yang kita hanya lakukan di sini pada 521 00:20:52,990 --> 00:20:53,880 ujung daftar. 522 00:20:53,880 --> 00:20:59,530 Siapa yang perlu berbicara pertama, berdasarkan algoritma? 523 00:20:59,530 --> 00:21:03,210 Jadi menjelaskan apa yang Anda lakukan sebelum Anda membuat gerakan kaki. 524 00:21:03,210 --> 00:21:05,930 >> SPEAKER 1: Baiklah, jadi karena Saya kiri setengah dari 525 00:21:05,930 --> 00:21:07,790 kiri setengah, aku kembali. 526 00:21:07,790 --> 00:21:08,730 Benar? 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 mic pergi ke depan? 530 00:21:11,800 --> 00:21:12,920 >> SPEAKER 1: nomor berikutnya. 531 00:21:12,920 --> 00:21:14,720 >> SPEAKER 2: Jadi saya bagian kanan dari kiri setengah dari 532 00:21:14,720 --> 00:21:17,830 kiri setengah, dan aku 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 di samping untuk kalian berdua? 536 00:21:21,855 --> 00:21:23,740 >> SPEAKER 2: Kami ingin melihat siapa yang lebih kecil. 537 00:21:23,740 --> 00:21:24,200 >> DAVID Malan: Tepat. 538 00:21:24,200 --> 00:21:24,940 Kami ingin menggabungkan. 539 00:21:24,940 --> 00:21:27,590 Ruang kita akan gunakan untuk menggabungkan Anda ke dalam, meskipun mereka 540 00:21:27,590 --> 00:21:30,250 jelas diurutkan sudah, kita akan untuk 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 sekarang mic berjalan orang-orang ini, OK? 544 00:21:38,570 --> 00:21:43,590 >> SPEAKER 3: Jadi aku setengah kanan kiri setengah, dan n saya kurang dari 545 00:21:43,590 --> 00:21:45,048 1, jadi aku 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: Aku kanan setengah dari bagian kanan bagian kanan, dan aku 548 00:21:49,450 --> 00:21:51,740 juga salah satu orang, jadi aku akan kembali. 549 00:21:51,740 --> 00:21:52,990 Jadi sekarang kita menggabungkan. 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 pergi dulu, kemudian 8. 554 00:21:59,200 --> 00:22:01,240 Dan sekarang penonton, yang merupakan langkah kita harus mundur sekarang 555 00:22:01,240 --> 00:22:02,200 kembali ke dalam pikiran kita? 556 00:22:02,200 --> 00:22:02,940 >> AUDIENCE: Gabung. 557 00:22:02,940 --> 00:22:07,270 >> DAVID Malan: Penggabungan setengah kiri dan kanan setengah dari kiri setengah asli. 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 antara Anda dua orang. 561 00:22:11,690 --> 00:22:13,800 Jadi sekarang itu dua daftar, kiri dan kanan. 562 00:22:13,800 --> 00:22:18,320 Jadi bagaimana kita sekarang menggabungkan kalian ke barisan depan kursi lagi? 563 00:22:18,320 --> 00:22:19,600 >> 3 pergi 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 sekarang kita? 568 00:22:28,710 --> 00:22:29,650 >> AUDIENCE: Tidak dilakukan. 569 00:22:29,650 --> 00:22:32,440 >> DAVID Malan: Tidak dilakukan, karena jelas, ada satu langkah yang tersisa. 570 00:22:32,440 --> 00:22:35,720 Tapi sekali lagi, alasan saya menggunakan ini jargon seperti "mundur dalam pikiran Anda," 571 00:22:35,720 --> 00:22:37,160 itu karena itu benar-benar apa yang terjadi. 572 00:22:37,160 --> 00:22:39,610 Kita akan melalui semua langkah ini, tapi kami semacam berhenti untuk 573 00:22:39,610 --> 00:22:42,480 saat, menyelam lebih dalam algoritma, berhenti sejenak, 574 00:22:42,480 --> 00:22:45,840 menyelam lebih dalam algoritma, dan sekarang kita harus semacam mundur dalam kami 575 00:22:45,840 --> 00:22:49,430 pikiran dan membatalkan semua lapisan ini bahwa kita sudah semacam ditahan. 576 00:22:49,430 --> 00:22:51,790 >> Jadi sekarang kita memiliki dua daftar ukuran 4. 577 00:22:51,790 --> 00:22:54,790 Jika kalian bisa berdiri untuk terakhir kalinya dan membuat sedikit ruang di sini untuk 578 00:22:54,790 --> 00:22:57,230 membuat jelas bahwa ini adalah kiri setengah dari aslinya, 579 00:22:57,230 --> 00:22:58,620 kanan setengah dari aslinya. 580 00:22:58,620 --> 00:23:01,060 Siapa angka pertama yang kita perlu untuk menarik ke belakang? 581 00:23:01,060 --> 00:23:01,870 Michelle, tentu saja. 582 00:23:01,870 --> 00:23:03,230 >> Jadi kita menempatkan Michelle sini. 583 00:23:03,230 --> 00:23:05,080 Dan siapa yang memiliki nomor 2? 584 00:23:05,080 --> 00:23:06,440 Nomor 2 datang pada kembali juga. 585 00:23:06,440 --> 00:23:07,800 Nomor 3? 586 00:23:07,800 --> 00:23:08,510 Luar biasa. 587 00:23:08,510 --> 00:23:16,570 Angka 4, angka 5, angka 6, nomor 7, dan nomor 8. 588 00:23:16,570 --> 00:23:18,850 >> OK, jadi rasanya seperti banyak langkah-langkah, pasti. 589 00:23:18,850 --> 00:23:22,390 Tapi sekarang mari kita lihat apakah kita tidak dapat mengkonfirmasi semacam intuitif bahwa ini 590 00:23:22,390 --> 00:23:26,190 algoritma fundamental, terutama karena n jadi sangat besar, seperti yang kita lihat 591 00:23:26,190 --> 00:23:29,170 dengan animasi, adalah fundamental lebih cepat. 592 00:23:29,170 --> 00:23:33,400 Jadi saya mengklaim algoritma ini, yang terburuk kasus dan bahkan dalam kasus terbaik, 593 00:23:33,400 --> 00:23:36,160 adalah O besar n kali log n. 594 00:23:36,160 --> 00:23:39,160 Artinya, ada beberapa aspek ini algoritma yang mengambil n langkah, tetapi 595 00:23:39,160 --> 00:23:43,110 ada aspek lain di suatu tempat di bahwa iterasi, perulangan itu, yang 596 00:23:43,110 --> 00:23:44,410 mengambil log n langkah. 597 00:23:44,410 --> 00:23:49,154 Dapatkah kita menempatkan jari kita pada apa yang mereka dua nomor maksud? 598 00:23:49,154 --> 00:23:51,320 Nah, di mana - 599 00:23:51,320 --> 00:23:54,160 mana 'd mic pergi? 600 00:23:54,160 --> 00:23:58,660 >> SPEAKER 1: Apakah log n menjadi melanggar kita menjadi dua - 601 00:23:58,660 --> 00:23:59,630 membaginya dengan dua, pada dasarnya. 602 00:23:59,630 --> 00:24:00,120 >> DAVID Malan: Tepat. 603 00:24:00,120 --> 00:24:03,000 Setiap kali kita melihat dalam algoritma sehingga Sejauh ini, sudah ada pola 604 00:24:03,000 --> 00:24:04,200 membagi, membagi, membagi. 605 00:24:04,200 --> 00:24:05,700 Dan itu biasanya berkurang untuk sesuatu yang 606 00:24:05,700 --> 00:24:07,100 logaritmik, log basis 2. 607 00:24:07,100 --> 00:24:10,180 Tapi itu benar-benar bisa menjadi apa pun, tapi log basis 2. 608 00:24:10,180 --> 00:24:11,330 >> Sekarang bagaimana dengan n? 609 00:24:11,330 --> 00:24:14,550 Saya dapat melihat bahwa kami jenis dibagi Anda guys - Anda dibagi, dibagi Anda, 610 00:24:14,550 --> 00:24:15,910 Anda dibagi, dibagi Anda. 611 00:24:15,910 --> 00:24:18,760 Dimana akhirnya datang? 612 00:24:18,760 --> 00:24:19,810 >> Jadi penggabungan. 613 00:24:19,810 --> 00:24:20,610 Karena berpikir tentang hal ini. 614 00:24:20,610 --> 00:24:25,420 Ketika Anda menggabungkan delapan orang bersama-sama, dimana setengah dari mereka adalah satu set dari empat 615 00:24:25,420 --> 00:24:27,770 dan setengah lainnya adalah lain set empat, bagaimana Anda pergi 616 00:24:27,770 --> 00:24:28,820 tentang melakukan penggabungan? 617 00:24:28,820 --> 00:24:30,830 Nah, kalian melakukannya cukup intuitif. 618 00:24:30,830 --> 00:24:34,140 >> Tapi kalau aku malah melakukannya sedikit lebih metodis, aku mungkin telah menunjuk 619 00:24:34,140 --> 00:24:38,090 orang paling kiri pertama dengan kiri saya tangan, menunjuk orang 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 Daftar, menunjuk elemen terkecil setiap kali, menggerakkan jari saya di atas dan 622 00:24:46,990 --> 00:24:48,970 lebih sesuai kebutuhan seluruh daftar. 623 00:24:48,970 --> 00:24:51,890 Tapi apa kunci tentang penggabungan ini proses saya membandingkan pasangan ini 624 00:24:51,890 --> 00:24:53,460 elemen. 625 00:24:53,460 --> 00:24:57,270 Dari paruh kanan dan dari kiri setengah, aku tidak pernah backtracking. 626 00:24:57,270 --> 00:25:00,570 >> Jadi penggabungan itu sendiri adalah mengambil tidak lebih dari n langkah. 627 00:25:00,570 --> 00:25:03,250 Dan berapa kali aku memiliki untuk melakukan itu penggabungan? 628 00:25:03,250 --> 00:25:07,150 Yah, tidak lebih dari n, dan kami hanya melihat bahwa dengan penggabungan akhir. 629 00:25:07,150 --> 00:25:13,120 Dan jadi jika Anda melakukan sesuatu yang memerlukan log n langkah n kali, atau sebaliknya, 630 00:25:13,120 --> 00:25:15,210 itu akan memberi kita n kali log n. 631 00:25:15,210 --> 00:25:16,310 >> Dan mengapa ini lebih baik? 632 00:25:16,310 --> 00:25:19,600 Nah, jika kita sudah tahu bahwa log n lebih baik daripada n - benar? 633 00:25:19,600 --> 00:25:22,590 Kita telah melihat dalam pencarian biner, buku telepon Misalnya, log n pasti 634 00:25:22,590 --> 00:25:23,760 lebih baik daripada linear. 635 00:25:23,760 --> 00:25:28,420 Jadi itu berarti n kali log n adalah jelas lebih baik daripada yang lain n kali 636 00:25:28,420 --> 00:25:30,390 n, AKA n kuadrat. 637 00:25:30,390 --> 00:25:32,400 Dan itulah yang akhirnya kita rasakan. 638 00:25:32,400 --> 00:25:34,928 >> Begitu besar putaran tepuk tangan, jika kita bisa, untuk orang-orang. 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 dapat menyimpan nomor, 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 mengirimkan rekaman, Michelle. 644 00:25:47,290 --> 00:25:48,343 Terima kasih. 645 00:25:48,343 --> 00:25:49,250 Baik. 646 00:25:49,250 --> 00:25:50,400 Membantu diri Anda sendiri untuk bola stres. 647 00:25:50,400 --> 00:25:54,110 >> Dan biarkan aku berhenti, sementara itu, teman kita Rob Bowden untuk menawarkan 648 00:25:54,110 --> 00:25:59,520 perspektif yang agak berbeda tentang hal ini, karena Anda dapat berpikir tentang ini 649 00:25:59,520 --> 00:26:01,280 langkah-langkah yang terjadi dalam agak cara yang berbeda. 650 00:26:01,280 --> 00:26:04,750 Bahkan, set-up untuk apa Rob tentang untuk menunjukkan kepada kita mengasumsikan bahwa kita sudah 651 00:26:04,750 --> 00:26:09,030 sudah dilakukan sampai membagi dari daftar besar menjadi delapan daftar kecil, 652 00:26:09,030 --> 00:26:10,570 masing-masing ukuran 1. 653 00:26:10,570 --> 00:26:13,350 >> Jadi kami mengubah pseudocode a sedikit hanya untuk semacam mendapatkannya di 654 00:26:13,350 --> 00:26:15,320 Ide inti cara kerja penggabungan. 655 00:26:15,320 --> 00:26:17,600 Tapi waktu berjalan apa dia akan lakukan adalah masih 656 00:26:17,600 --> 00:26:19,110 akan menjadi sama. 657 00:26:19,110 --> 00:26:23,540 Dan lagi, set-up di sini adalah bahwa dia dimulai dengan delapan daftar ukuran 1. 658 00:26:23,540 --> 00:26:27,730 Jadi, Anda telah melewatkan bagian di mana dia benar-benar melakukan log n, n log, log n 659 00:26:27,730 --> 00:26:31,205 membagi input. 660 00:26:31,205 --> 00:26:32,120 >> [VIDEO PEMUTARAN] 661 00:26:32,120 --> 00:26:33,615 >> -Itu saja untuk langkah pertama. 662 00:26:33,615 --> 00:26:38,270 Untuk langkah kedua, berulang kali menggabungkan pasang daftar. 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 dari komputer saya. 665 00:26:41,270 --> 00:26:42,520 Mari kita coba lagi. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Hanya sewenang-wenang memilih mana - sekarang kita memiliki empat daftar. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 Pelajari sebelumnya. 670 00:26:52,120 --> 00:26:53,040 >> DAVID Malan: Di sana kami pergi. 671 00:26:53,040 --> 00:27:00,510 >> Menggabung-108 dan 15, kita akhirnya dengan daftar 15, 108. 672 00:27:00,510 --> 00:27:07,170 Menggabung 50 dan 4, kita berakhir dengan 4, 50. 673 00:27:07,170 --> 00:27:12,990 Penggabungan 8 dan 42, kami berakhir dengan 8, 42. 674 00:27:12,990 --> 00:27:19,970 Dan penggabungan 23 dan 16, kami berakhir dengan 16, 23. 675 00:27:19,970 --> 00:27:23,270 >> Sekarang semua daftar kami adalah ukuran 2. 676 00:27:23,270 --> 00:27:26,690 Perhatikan bahwa masing-masing empat daftar diurutkan. 677 00:27:26,690 --> 00:27:29,450 Jadi kita bisa mulai menggabungkan pasang daftar lagi. 678 00:27:29,450 --> 00:27:38,420 Menggabung 15 dan 108 dan 4 dan 50, kami pertama kita 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, pertama kita 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 hanya memiliki dua daftar ukuran 4, masing-masing yang diurutkan. 683 00:27:57,600 --> 00:28:01,170 Jadi sekarang kita menggabungkan kedua daftar. 684 00:28:01,170 --> 00:28:11,835 Pertama, kita mengambil 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 >> [END VIDEO PEMUTARAN] 687 00:28:19,872 --> 00:28:23,430 >> DAVID Malan: Sekali lagi, pemberitahuan, ia tidak pernah menyentuh secangkir diberikan lebih dari satu kali 688 00:28:23,430 --> 00:28:24,860 setelah maju 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 selalu bergerak ke samping, dan di situlah kami mendapat n kami. 691 00:28:29,850 --> 00:28:33,290 >> Mengapa tidak membiarkan saya menarik satu animasi yang kita lihat sebelumnya, tapi kali ini 692 00:28:33,290 --> 00:28:35,110 fokus hanya pada merge sort. 693 00:28:35,110 --> 00:28:38,030 Biarkan aku pergi ke depan dan tampilannya dalam hal ini di sini. 694 00:28:38,030 --> 00:28:42,530 Pertama biarkan saya memilih input acak, memperbesar ini, dan Anda dapat semacam melihat 695 00:28:42,530 --> 00:28:46,600 apa yang kita mengambil untuk diberikan, sebelumnya, menggabungkan semacam benar-benar melakukan. 696 00:28:46,600 --> 00:28:50,330 >> Jadi perhatikan bahwa Anda mendapatkan bagian ini atau ini atau kuartal ini perdelapan 697 00:28:50,330 --> 00:28:53,140 Masalah yang tiba-tiba mulai mengambil bentuk yang baik. 698 00:28:53,140 --> 00:28:57,070 Dan akhirnya, Anda lihat di akhir yang bam, 699 00:28:57,070 --> 00:28:58,860 semuanya digabungkan. 700 00:28:58,860 --> 00:29:01,690 >> Jadi ini hanya tiga yang berbeda mengambil ide yang sama. 701 00:29:01,690 --> 00:29:05,980 Tapi wawasan kunci, seperti membagi dan menaklukkan di kelas pertama, 702 00:29:05,980 --> 00:29:10,640 adalah bahwa kami memutuskan untuk entah bagaimana membagi masalah menjadi sesuatu yang besar, menjadi 703 00:29:10,640 --> 00:29:14,760 sesuatu semacam identik dalam roh, 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 >> Sekarang lagi menyenangkan cara untuk semacam berpikir tentang ini, meskipun itu tidak 706 00:29:18,420 --> 00:29:20,520 akan memberikan intuitif yang 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 video seseorang menempatkan bersama-sama yang terkait berbeda 709 00:29:25,400 --> 00:29:29,970 suara dengan berbagai operasi untuk insertion sort, untuk menggabungkan menyortir, dan 710 00:29:29,970 --> 00:29:31,150 untuk beberapa orang lain. 711 00:29:31,150 --> 00:29:32,330 Jadi suatu saat, aku akan memukul Play. 712 00:29:32,330 --> 00:29:33,600 Ini sekitar satu menit yang panjang. 713 00:29:33,600 --> 00:29:37,410 Dan meskipun Anda masih dapat melihat pola terjadi, kali ini Anda bisa 714 00:29:37,410 --> 00:29:41,420 juga mendengar bagaimana algoritma ini tampil berbeda dan dengan 715 00:29:41,420 --> 00:29:43,950 pola agak berbeda. 716 00:29:43,950 --> 00:29:45,830 >> Ini adalah insertion sort. 717 00:29:45,830 --> 00:29:50,400 >> [NADA BERMAIN] 718 00:29:50,400 --> 00:29:52,400 >> DAVID Malan: Ini lagi mencoba untuk menyisipkan setiap elemen 719 00:29:52,400 --> 00:29:52,900 ke tempatnya. 720 00:29:52,900 --> 00:29:54,628 Ini adalah bubble sort. 721 00:29:54,628 --> 00:30:10,097 >> [NADA BERMAIN] 722 00:30:10,097 --> 00:30:13,630 >> DAVID Malan: Dan Anda dapat semacam merasa bagaimana relatif sedikit bekerja itu 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 terdengar seperti tediousness. 725 00:30:20,470 --> 00:30:21,472 >> [NADA BERMAIN] 726 00:30:21,472 --> 00:30:25,222 >> DAVID Malan: Ini adalah semacam seleksi, di mana kita memilih elemen yang kita inginkan dengan 727 00:30:25,222 --> 00:30:28,845 akan melalui lagi dan lagi dan lagi dan meletakkannya di awal. 728 00:30:28,845 --> 00:30:37,674 >> [NADA BERMAIN] 729 00:30:37,674 --> 00:30:43,970 >> DAVID Malan: Ini adalah menggabungkan semacam, yang Anda benar-benar bisa mulai merasakan. 730 00:30:43,970 --> 00:30:51,810 >> [NADA BERMAIN] 731 00:30:51,810 --> 00:30:54,770 >> [Tertawa] 732 00:30:54,770 --> 00:30:58,395 >> DAVID Malan: Sesuatu yang disebut gnome semacam, yang kita belum melihat. 733 00:30:58,395 --> 00:31:13,630 >> [NADA BERMAIN] 734 00:31:13,630 --> 00:31:17,910 >> DAVID Malan: Jadi biarkan aku lihat, sekarang, terganggu karena Anda mudah-mudahan adalah dengan 735 00:31:17,910 --> 00:31:21,110 musik, jika aku bisa menyelipkan sedikit sedikit matematika di sini. 736 00:31:21,110 --> 00:31:24,850 Jadi ada cara keempat yang kita bisa berpikir tentang apa artinya ini 737 00:31:24,850 --> 00:31:29,210 fungsi menjadi lebih cepat dari yang yang pernah kita lihat sebelumnya. 738 00:31:29,210 --> 00:31:32,470 Dan jika Anda datang di kursus dari latar belakang matematika, Anda 739 00:31:32,470 --> 00:31:36,030 benar-benar tahu mungkin sudah Anda dapat menampar istilah di teknik ini - 740 00:31:36,030 --> 00:31:40,400 yaitu rekursi, fungsi yang entah bagaimana menyebut dirinya. 741 00:31:40,400 --> 00:31:44,780 >> Dan lagi, ingat bahwa merge sort pseudocode adalah rekursif dalam arti 742 00:31:44,780 --> 00:31:48,460 bahwa salah satu langkah merge semacam ini adalah untuk memanggil sort - 743 00:31:48,460 --> 00:31:49,740 yaitu, sendiri. 744 00:31:49,740 --> 00:31:52,480 Tapi untungnya, karena kami terus memanggil macam, atau menggabungkan semacam, 745 00:31:52,480 --> 00:31:55,880 khusus, pada kecil dan lebih kecil dan daftar yang lebih kecil, kita akhirnya 746 00:31:55,880 --> 00:32:00,005 dipercaya keluar berkat apa yang akan kita sebut kasus dasar, kasus keras-kode yang 747 00:32:00,005 --> 00:32:04,270 mengatakan jika daftar kecil, kurang dari 2 dalam kasus itu, hanya kembali segera. 748 00:32:04,270 --> 00:32:07,550 Jika kita tidak memiliki kasus khusus, algoritma akan pernah keluar bawah, 749 00:32:07,550 --> 00:32:11,010 dan Anda memang akan masuk ke sebuah infinite loop benar-benar selamanya. 750 00:32:11,010 --> 00:32:14,330 >> Tapi misalkan kita ingin sekarang menempatkan beberapa nomor ini, sekali lagi, menggunakan n 751 00:32:14,330 --> 00:32:15,660 sebagai ukuran input. 752 00:32:15,660 --> 00:32:18,680 Dan saya ingin bertanya, apa total waktu yang terlibat dalam 753 00:32:18,680 --> 00:32:19,800 menjalankan merge sort? 754 00:32:19,800 --> 00:32:22,960 Atau lebih umum, apa biaya itu dalam waktu? 755 00:32:22,960 --> 00:32:24,730 >> Yah itu cukup mudah untuk mengukur itu. 756 00:32:24,730 --> 00:32:29,010 Jika n kurang dari 2, waktu yang terlibat dalam memilah n elemen, 757 00:32:29,010 --> 00:32:30,480 dimana n adalah 2, adalah 0. 758 00:32:30,480 --> 00:32:31,410 Karena kami hanya kembali. 759 00:32:31,410 --> 00:32:32,510 Tidak ada pekerjaan yang harus dilakukan. 760 00:32:32,510 --> 00:32:35,660 Sekarang bisa dibilang, mungkin itu salah satu langkah atau dua langkah-langkah untuk mengetahui jumlah 761 00:32:35,660 --> 00:32:38,420 bekerja, tapi itu cukup dekat untuk 0 yang Aku hanya akan mengatakan tidak kerja 762 00:32:38,420 --> 00:32:40,940 diperlukan jika daftar sangat kecil akan menarik. 763 00:32:40,940 --> 00:32:42,580 >> Tapi kasus ini menarik. 764 00:32:42,580 --> 00:32:47,320 Rekursif kasus ini adalah cabang dari pseudocode yang mengatakan lain, semacam 765 00:32:47,320 --> 00:32:52,000 kiri setengah, mengurutkan kanan setengah, menggabungkan dua bagian. 766 00:32:52,000 --> 00:32:55,530 Sekarang mengapa ungkapan ini merupakan biaya itu? 767 00:32:55,530 --> 00:32:58,690 Nah, T n hanya berarti waktu untuk memilah elemen n. 768 00:32:58,690 --> 00:33:03,070 Dan kemudian di sisi kanan dari tanda sama dengan di sana, T n dibagi 769 00:33:03,070 --> 00:33:06,600 oleh 2 ini mengacu pada biaya apa? 770 00:33:06,600 --> 00:33:07,570 Sorting kiri setengah. 771 00:33:07,570 --> 00:33:10,990 T lain dari n dibagi 2 yaitu mungkin mengacu pada biaya 772 00:33:10,990 --> 00:33:12,390 mengurutkan bagian kanan. 773 00:33:12,390 --> 00:33:14,590 >> Dan kemudian ditambah n? 774 00:33:14,590 --> 00:33:15,420 Adalah penggabungan. 775 00:33:15,420 --> 00:33:19,120 Karena jika Anda memiliki dua daftar, satu dari berukuran n lebih dari 2 dan satu lagi berukuran n 776 00:33:19,120 --> 00:33:22,580 lebih dari 2, Anda harus menyentuh dasarnya masing-masing elemen, seperti Rob 777 00:33:22,580 --> 00:33:24,990 menyentuh setiap cangkir, dan hanya seperti kita menunjuk masing-masing 778 00:33:24,990 --> 00:33:26,310 relawan di atas panggung. 779 00:33:26,310 --> 00:33:28,790 Jadi n adalah biaya penggabungan. 780 00:33:28,790 --> 00:33:31,780 >> Sekarang sayangnya, formula ini juga sendiri rekursif. 781 00:33:31,780 --> 00:33:36,390 Jadi jika mengajukan pertanyaan, jika n adalah, katakanlah, 16, jika ada 16 orang di atas panggung 782 00:33:36,390 --> 00:33:40,670 atau 16 cangkir dalam video, berapa banyak jumlah langkah yang diperlukan untuk mengurutkan mereka 783 00:33:40,670 --> 00:33:41,550 dengan merge sort? 784 00:33:41,550 --> 00:33:45,790 Ini sebenarnya bukan jawaban yang jelas, karena sekarang Anda harus semacam 785 00:33:45,790 --> 00:33:48,500 rekursif menjawab formula ini. 786 00:33:48,500 --> 00:33:51,190 >> Tapi itu OK, karena biar mengusulkan bahwa kita melakukan hal berikut. 787 00:33:51,190 --> 00:33:56,670 Waktu yang terlibat untuk mengurutkan 16 orang atau 16 cangkir akan diwakili 788 00:33:56,670 --> 00:33:58,020 umumnya sebagai T dari 16. 789 00:33:58,020 --> 00:34:01,400 Tapi itu sama, menurut kami rumus sebelumnya, 2 kali jumlah 790 00:34:01,400 --> 00:34:04,780 waktu yang diperlukan untuk menyortir 8 cangkir ditambah 16. 791 00:34:04,780 --> 00:34:08,590 Dan lagi, ditambah 16 adalah waktu untuk bergabung, dan dua kali T dari 8 adalah 792 00:34:08,590 --> 00:34:10,790 waktu untuk memilah kiri setengah dan setengah benar. 793 00:34:10,790 --> 00:34:11,989 >> Tapi sekali lagi, ini tidak cukup. 794 00:34:11,989 --> 00:34:13,210 Kita harus menyelam lebih dalam. 795 00:34:13,210 --> 00:34:16,409 Ini berarti kita harus menjawab Pertanyaannya, apakah T dari 8? 796 00:34:16,409 --> 00:34:19,610 Nah T dari 8 hanya 2 kali T dari 4 ditambah 8. 797 00:34:19,610 --> 00:34:20,520 Nah, apa T dari 4? 798 00:34:20,520 --> 00:34:23,780 T dari 4 hanya 2 kali dari T 2 ditambah 4. 799 00:34:23,780 --> 00:34:25,489 Nah, apa T dari 2? 800 00:34:25,489 --> 00:34:29,030 T 2 adalah hanya 2 kali dari T 1 ditambah 2. 801 00:34:29,030 --> 00:34:31,940 >> Dan sekali lagi, kami tidak mendapatkan jenis terjebak dalam siklus ini. 802 00:34:31,940 --> 00:34:34,790 Tapi itu akan memukul bahwa disebut kasus dasar. 803 00:34:34,790 --> 00:34:37,310 Karena apa T dari 1, apakah kita mengklaim? 804 00:34:37,310 --> 00:34:37,810 0. 805 00:34:37,810 --> 00:34:39,730 Jadi sekarang akhirnya kita bisa bekerja mundur. 806 00:34:39,730 --> 00:34:44,290 >> Jika T 1 adalah 0, sekarang saya bisa kembali naik satu berbaris dengan orang ini di sini, dan saya bisa 807 00:34:44,290 --> 00:34:46,330 plug in 0 untuk T dari 1. 808 00:34:46,330 --> 00:34:51,770 Jadi itu berarti itu sama dengan 2 kali nol, atau dikenal sebagai 0, ditambah 2. 809 00:34:51,770 --> 00:34:53,739 Dan sehingga ekspresi keseluruhan adalah 2. 810 00:34:53,739 --> 00:34:58,740 >> Sekarang jika saya mengambil T 2, yang jawabannya adalah 2, hubungkan ke garis tengah, T 811 00:34:58,740 --> 00:35:02,740 4, yang memberi saya 2 kali 2 ditambah 4, jadi 8. 812 00:35:02,740 --> 00:35:07,080 Jika saya kemudian pasang di 8 dengan sebelumnya line, yang memberikan saya 2 kali 8, 16. 813 00:35:07,080 --> 00:35:12,470 Dan jika kita kemudian melanjutkan bahwa dengan 24, menambahkan dalam 16, akhirnya kami mendapatkan 814 00:35:12,470 --> 00:35:13,820 nilai 64. 815 00:35:13,820 --> 00:35:18,480 >> Sekarang bahwa dalam dan dari dirinya sendiri semacam berbicara ada notasi n, yang 816 00:35:18,480 --> 00:35:20,700 big O, omega bahwa kita sudah telah berbicara tentang. 817 00:35:20,700 --> 00:35:24,890 Tapi ternyata bahwa 64 memang 16, ukuran input, 818 00:35:24,890 --> 00:35:27,110 log basis 2 dari 16. 819 00:35:27,110 --> 00:35:30,200 Dan jika ini sedikit asing, hanya berpikir kembali, dan itu akan kembali 820 00:35:30,200 --> 00:35:30,700 Anda akhirnya. 821 00:35:30,700 --> 00:35:33,775 Jika ini adalah log basis 2, itu seperti 2 diangkat ke apa yang memberi Anda 16? 822 00:35:33,775 --> 00:35:36,380 Oh, itu 4, jadi 16 kali 4. 823 00:35:36,380 --> 00:35:39,380 >> Dan sekali lagi, ini bukan masalah besar jika hal ini adalah semacam memori kabur sekarang. 824 00:35:39,380 --> 00:35:43,720 Tetapi untuk sekarang, mengambil iman bahwa 16 log 16 adalah 64. 825 00:35:43,720 --> 00:35:46,590 Dan memang, dengan kewarasan sederhana memeriksa, kami telah dikonfirmasi - 826 00:35:46,590 --> 00:35:48,250 tetapi tidak terbukti secara formal - 827 00:35:48,250 --> 00:35:52,800 bahwa waktu berjalan dari merge semacam ini 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 Ini jelas lebih baik daripada algoritma yang telah kita lihat sejauh ini, dan 830 00:35:57,260 --> 00:36:00,710 itu karena kami telah mempengaruhi, satu, teknik yang disebut rekursi. 831 00:36:00,710 --> 00:36:03,880 Tapi yang lebih menarik dari itu, bahwa gagasan membagi dan menaklukkan. 832 00:36:03,880 --> 00:36:07,460 Sekali lagi, benar-benar minggu 0 hal-hal yang bahkan sekarang 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 latihan menyenangkan, jika Anda sudah pernah melakukan ini - dan Anda mungkin 835 00:36:11,750 --> 00:36:14,660 tidak akan, karena semacam normal orang tidak berpikir untuk melakukan hal ini. 836 00:36:14,660 --> 00:36:20,650 Tetapi jika aku pergi ke google.com dan jika Saya ingin 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 >> [Tertawa] 840 00:36:29,058 --> 00:36:32,030 [Tertawa MORE] 841 00:36:32,030 --> 00:36:33,385 DAVID Malan: Bad joke perlahan-lahan menyebar. 842 00:36:33,385 --> 00:36:34,450 [Tertawa] 843 00:36:34,450 --> 00:36:36,970 DAVID Malan: Hanya dalam kasus, itu ada. 844 00:36:36,970 --> 00:36:38,710 Aku tidak mengejanya salah, dan ada lelucon. 845 00:36:38,710 --> 00:36:40,810 Baik. 846 00:36:40,810 --> 00:36:42,950 Jelaskan kepada orang-orang di sebelah Anda jika belum cukup diklik dulu. 847 00:36:42,950 --> 00:36:47,650 Tapi rekursi, lebih umum, mengacu dengan proses fungsi panggilan 848 00:36:47,650 --> 00:36:51,430 sendiri, atau lebih umum, membagi masalah menjadi sesuatu yang dapat 849 00:36:51,430 --> 00:36:56,220 dipecahkan sedikit demi sedikit dengan memecahkan identik masalah perwakilan. 850 00:36:56,220 --> 00:36:58,400 >> Nah, mari kita ubah gigi untuk sesaat. 851 00:36:58,400 --> 00:37:00,840 Kami ingin berakhir pada cliffhangers tertentu, jadi mari kita mulai untuk mengatur 852 00:37:00,840 --> 00:37:05,870 panggung, selama beberapa menit, pada ide yang sangat sederhana - 853 00:37:05,870 --> 00:37:07,620 bahwa swapping dua elemen, kan? 854 00:37:07,620 --> 00:37:10,040 Semua algoritma ini kita sudah berbicara tentang masa lalu beberapa 855 00:37:10,040 --> 00:37:12,420 kuliah melibatkan beberapa semacam swapping. 856 00:37:12,420 --> 00:37:14,630 Hari itu divisualisasikan oleh mereka mendapatkan keluar dari kursi mereka dan 857 00:37:14,630 --> 00:37:18,570 berjalan-jalan, tapi dalam kode, kita akan hanya mengambil sebuah elemen dari satu array 858 00:37:18,570 --> 00:37:20,370 dan celepuk menjadi lain. 859 00:37:20,370 --> 00:37:21,880 >> Jadi bagaimana kita pergi tentang melakukan ini? 860 00:37:21,880 --> 00:37:24,850 Nah, biarkan aku pergi ke depan dan menulis program cepat di sini. 861 00:37:24,850 --> 00:37:31,600 Aku akan pergi ke depan dan melakukan ini sebagai berikut. 862 00:37:31,600 --> 00:37:33,910 Mari kita sebut ini - 863 00:37:33,910 --> 00:37:38,070 apa yang kita ingin memanggil satu ini? 864 00:37:38,070 --> 00:37:38,650 >> Sebenarnya, tidak. 865 00:37:38,650 --> 00:37:39,420 Mari saya mundur. 866 00:37:39,420 --> 00:37:41,220 Saya tidak ingin melakukan itu Belum cliffhanger. 867 00:37:41,220 --> 00:37:42,270 Ini akan merusak kesenangan. 868 00:37:42,270 --> 00:37:43,600 Mari kita lakukan ini sebagai gantinya. 869 00:37:43,600 --> 00:37:47,430 >> Misalkan saya ingin menulis sedikit Program dan bahwa kini merangkul ini 870 00:37:47,430 --> 00:37:48,700 gagasan rekursi. 871 00:37:48,700 --> 00:37:50,370 Aku agak mendapat depan sendiri ada. 872 00:37:50,370 --> 00:37:51,420 Aku akan melakukan hal berikut. 873 00:37:51,420 --> 00:38:00,220 >> Pertama, cepat meliputi standar io.h, serta termasuk dari cs50.h. 874 00:38:00,220 --> 00:38:03,200 Dan kemudian aku akan pergi ke depan dan menyatakan void main int 875 00:38:03,200 --> 00:38:04,360 dengan cara yang biasa. 876 00:38:04,360 --> 00:38:07,920 Aku sadar bahwa aku sudah misnamed file, sehingga biarkan aku hanya menambahkan ekstensi c. sini jadi 877 00:38:07,920 --> 00:38:09,510 bahwa kita dapat mengkompilasi dengan benar. 878 00:38:09,510 --> 00:38:10,970 Mulai fungsi ini. 879 00:38:10,970 --> 00:38:13,290 >> Dan fungsi saya ingin menulis, cukup sederhana, adalah salah satu yang meminta 880 00:38:13,290 --> 00:38:16,210 pengguna untuk nomor dan kemudian menambahkan sampai semua angka antara itu 881 00:38:16,210 --> 00:38:19,920 jumlah dan, katakanlah, 0. 882 00:38:19,920 --> 00:38:22,510 Jadi pertama aku akan pergi ke depan dan menyatakan int n. 883 00:38:22,510 --> 00:38:24,760 Lalu aku menyalin beberapa kode yang kami telah digunakan untuk sementara waktu. 884 00:38:24,760 --> 00:38:26,660 Sementara ada sesuatu yang benar. 885 00:38:26,660 --> 00:38:28,000 Aku akan datang kembali ke dalam sekejap. 886 00:38:28,000 --> 00:38:29,010 >> Apa yang ingin saya lakukan? 887 00:38:29,010 --> 00:38:33,460 Saya ingin mengatakan printf positif silahkan integer. 888 00:38:33,460 --> 00:38:36,130 Dan kemudian aku akan mengatakan n mendapat mendapatkan int. 889 00:38:36,130 --> 00:38:38,800 Jadi sekali lagi, beberapa kode boilerplate bahwa kami telah digunakan sebelumnya. 890 00:38:38,800 --> 00:38:40,810 Dan aku akan melakukan hal ini sedangkan n kurang dari 1. 891 00:38:40,810 --> 00:38:44,120 Jadi, ini akan memastikan bahwa pengguna memberi saya bilangan bulat positif. 892 00:38:44,120 --> 00:38:45,490 >> Dan sekarang aku akan melakukan hal berikut. 893 00:38:45,490 --> 00:38:51,020 Saya ingin menambahkan semua nomor antara 1 dan dan n, atau 0 dan n, 894 00:38:51,020 --> 00:38:52,570 ekuivalen, untuk mendapatkan jumlah total. 895 00:38:52,570 --> 00:38:55,100 Jadi simbol sigma besar Anda mungkin ingat. 896 00:38:55,100 --> 00:38:59,050 Jadi aku akan melakukan ini dengan panggilan pertama fungsi yang disebut sigma, 897 00:38:59,050 --> 00:39:06,030 lewat di n, dan kemudian aku akan printf mengatakan, jawabannya ada di sana. 898 00:39:06,030 --> 00:39:08,180 >> Jadi singkatnya, saya mendapatkan dan int dari pengguna. 899 00:39:08,180 --> 00:39:09,280 Saya memastikan itu positif. 900 00:39:09,280 --> 00:39:12,700 Saya menyatakan yang disebut jawaban variabel tipe int dan toko di dalamnya pengembalian 901 00:39:12,700 --> 00:39:15,610 nilai sigma, lewat di n sebagai masukan. 902 00:39:15,610 --> 00:39:17,060 Dan kemudian saya mencetak jawaban itu. 903 00:39:17,060 --> 00:39:19,550 >> Sayangnya, meskipun sigma terdengar seperti sesuatu yang mungkin dalam 904 00:39:19,550 --> 00:39:24,040 file math.h, deklarasi, itu sebenarnya tidak. 905 00:39:24,040 --> 00:39:24,690 Jadi itu OK. 906 00:39:24,690 --> 00:39:26,170 Saya bisa menerapkan ini sendiri. 907 00:39:26,170 --> 00:39:29,160 Aku akan melaksanakan fungsi yang disebut sigma, dan itu akan mengambil 908 00:39:29,160 --> 00:39:29,900 Parameter - 909 00:39:29,900 --> 00:39:32,100 mari kita sebut saja m, hanya jadi berbeda. 910 00:39:32,100 --> 00:39:35,910 Dan kemudian di sini, aku akan mengatakan, baik, jika m adalah kurang dari 1 - ini adalah 911 00:39:35,910 --> 00:39:38,180 sangat menarik Program. 912 00:39:38,180 --> 00:39:41,700 Jadi aku akan pergi ke depan dan segera mengembalikan 0. 913 00:39:41,700 --> 00:39:45,920 Itu hanya tidak masuk akal untuk menambahkan semua angka antara 1 dan m jika m 914 00:39:45,920 --> 00:39:48,470 itu sendiri 0 atau negatif. 915 00:39:48,470 --> 00:39:50,900 >> Dan kemudian aku akan pergi ke depan dan melakukan hal ini sangat iteratif. 916 00:39:50,900 --> 00:39:53,090 Aku akan melakukan hal semacam ini tua-sekolah, dan aku akan pergi ke depan 917 00:39:53,090 --> 00:39:57,150 dan mengatakan bahwa aku akan menyatakan jumlah untuk menjadi 0. 918 00:39:57,150 --> 00:39:59,630 Lalu aku akan memiliki untuk loop int - 919 00:39:59,630 --> 00:40:02,820 dan biarkan aku melakukannya untuk mencocokkan kami kode distribusi, sehingga Anda memiliki salinan 920 00:40:02,820 --> 00:40:07,500 di rumah. int i mendapat 1 pada hingga i adalah kurang dari 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 dalam hal ini untuk loop - 923 00:40:11,430 --> 00:40:12,440 kita hampir sampai - 924 00:40:12,440 --> 00:40:15,810 sum sum mendapat ditambah 1. 925 00:40:15,810 --> 00:40:17,670 Dan kemudian aku akan kembali jumlah tersebut. 926 00:40:17,670 --> 00:40:19,420 >> Jadi saya melakukan ini dengan cepat, cukup diakui. 927 00:40:19,420 --> 00:40:22,775 Tapi sekali lagi, fungsi utama cukup langsung, berbasis pada kode kita sudah 928 00:40:22,775 --> 00:40:23,190 ditulis sejauh ini. 929 00:40:23,190 --> 00:40:25,610 Menggunakan dual loop untuk mendapatkan positif int dari pengguna. 930 00:40:25,610 --> 00:40:29,870 Saya kemudian lulus int bahwa untuk fungsi baru disebut sigma, menyebutnya, sekali lagi, n. 931 00:40:29,870 --> 00:40:33,100 Dan saya menyimpan nilai kembali, jawabannya dari kotak hitam saat ini 932 00:40:33,100 --> 00:40:35,460 dikenal sebagai sigma, dalam variabel disebut jawaban. 933 00:40:35,460 --> 00:40:36,580 Lalu aku mencetaknya. 934 00:40:36,580 --> 00:40:39,090 >> Jika sekarang kita melanjutkan cerita, bagaimana sigma dilaksanakan? 935 00:40:39,090 --> 00:40:40,840 Saya mengusulkan untuk menerapkan sebagai berikut. 936 00:40:40,840 --> 00:40:43,560 Pertama, sedikit pemeriksaan kesalahan memastikan bahwa pengguna tidak 937 00:40:43,560 --> 00:40:46,480 bermain-main dengan saya dan lewat di beberapa negatif atau nilai 0. 938 00:40:46,480 --> 00:40:49,710 Kemudian saya mendeklarasikan variabel disebut jumlah dan set ke 0. 939 00:40:49,710 --> 00:40:55,910 >> Dan sekarang aku mulai bergerak dari i sama 1 sepanjang jalan sampai dengan dan termasuk m, 940 00:40:55,910 --> 00:41:00,130 karena saya ingin memasukkan semua nomor dari satu melalui m, inklusif. 941 00:41:00,130 --> 00:41:04,350 Dan dalam hal ini untuk loop, saya hanya melakukan sum mendapatkan apapun sekarang, ditambah 942 00:41:04,350 --> 00:41:08,900 nilai i. 943 00:41:08,900 --> 00:41:10,370 Ditambah nilai i. 944 00:41:10,370 --> 00:41:14,090 >> Sebagai samping, jika Anda sudah tidak melihat ini sebelumnya, ada beberapa gula sintaksis 945 00:41:14,090 --> 00:41:14,870 untuk baris ini. 946 00:41:14,870 --> 00:41:21,120 Saya bisa menulis ulang ini sebagai ditambah sama dengan i, hanya untuk menyelamatkan diri beberapa keystrokes 947 00:41:21,120 --> 00:41:22,570 dan untuk melihat sedikit lebih dingin. 948 00:41:22,570 --> 00:41:23,140 Tapi itu semua. 949 00:41:23,140 --> 00:41:24,660 Ini fungsional hal yang sama. 950 00:41:24,660 --> 00:41:26,710 >> Sayangnya, kode ini tidak akan mengkompilasi belum. 951 00:41:26,710 --> 00:41:31,600 Jika saya jalankan make sigma 0, bagaimana am Aku akan dimarahi? 952 00:41:31,600 --> 00:41:33,473 Apa itu akan tidak suka? 953 00:41:33,473 --> 00:41:35,740 >> AUDIENCE: [Tak terdengar]. 954 00:41:35,740 --> 00:41:37,800 >> DAVID Malan: Ya, saya tidak menyatakan fungsi di bagian atas, kan? 955 00:41:37,800 --> 00:41:40,590 C adalah jenis bodoh, dalam hal ini hanya melakukan apa yang Anda kirim ke lakukan, dan Anda 956 00:41:40,590 --> 00:41:41,880 harus melakukannya dalam urutan itu. 957 00:41:41,880 --> 00:41:45,910 Dan jadi jika saya tekan Enter di sini, aku akan mendapatkan peringatan tentang sigma implisit 958 00:41:45,910 --> 00:41:46,860 deklarasi. 959 00:41:46,860 --> 00:41:48,120 >> Oh, tidak masalah. 960 00:41:48,120 --> 00:41:50,370 Aku bisa naik ke atas, dan saya bisa mengatakan, baiklah, tunggu sebentar. 961 00:41:50,370 --> 00:41:54,240 Sigma adalah fungsi yang mengembalikan int dan mereka mengharapkan 962 00:41:54,240 --> 00:41:56,620 int sebagai masukan, koma. 963 00:41:56,620 --> 00:41:59,550 Atau aku bisa menempatkan seluruh fungsi atas utama, tapi secara umum, aku akan 964 00:41:59,550 --> 00:42:02,260 merekomendasikan melawan itu, karena itu bagus untuk selalu memiliki utama di bagian atas sehingga 965 00:42:02,260 --> 00:42:06,310 Anda bisa menyelam kanan dan tahu apa Program lakukan dengan membaca utama pertama. 966 00:42:06,310 --> 00:42:07,930 >> Jadi sekarang biarkan aku membersihkan layar. 967 00:42:07,930 --> 00:42:09,330 Remake sigma 0. 968 00:42:09,330 --> 00:42:10,340 Semua tampaknya untuk memeriksa. 969 00:42:10,340 --> 00:42:11,970 Biarkan aku menjalankan sigma 0. 970 00:42:11,970 --> 00:42:12,770 Inter positif. 971 00:42:12,770 --> 00:42:15,580 Aku akan memberikan nomor 3 untuk tetap sederhana. 972 00:42:15,580 --> 00:42:18,710 Jadi yang harus memberi saya 3 ditambah 2 ditambah 1, jadi 6. 973 00:42:18,710 --> 00:42:20,750 Masukkan, dan memang saya mendapatkan 6. 974 00:42:20,750 --> 00:42:21,820 >> Aku bisa 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 tangen, aku akan melakukan sesuatu yang konyol seperti benar-benar besar 977 00:42:27,690 --> 00:42:30,375 nomor, Oh, yang benar-benar bekerja - 978 00:42:30,375 --> 00:42:31,600 eh, saya tidak berpikir itu benar. 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 berantakan dengan itu. 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 terjadi? 985 00:42:44,970 --> 00:42:46,050 Kode tidak seburuk itu. 986 00:42:46,050 --> 00:42:48,470 Ini masih linier. 987 00:42:48,470 --> 00:42:50,810 Bersiul adalah efek yang baik, meskipun. 988 00:42:50,810 --> 00:42:52,060 Apa yang terjadi? 989 00:42:52,060 --> 00:42:54,700 990 00:42:54,700 --> 00:42:55,620 >> Tidak yakin apakah aku mendengarnya. 991 00:42:55,620 --> 00:42:57,620 Jadi ternyata - dan ini sebagai samping. 992 00:42:57,620 --> 00:42:59,400 Ini bukan inti untuk gagasan rekursi. 993 00:42:59,400 --> 00:43:02,480 Ternyata, karena saya sedang mencoba untuk mewakili seperti sejumlah besar, kebanyakan 994 00:43:02,480 --> 00:43:06,980 kemungkinan itu sedang disalahtafsirkan oleh C sebagai angka tidak positif, 995 00:43:06,980 --> 00:43:09,980 tapi angka negatif. 996 00:43:09,980 --> 00:43:12,690 >> Kami belum membicarakan hal ini, tetapi ternyata ada angka negatif 997 00:43:12,690 --> 00:43:14,210 di dunia di samping ke nomor positif. 998 00:43:14,210 --> 00:43:16,290 Dan cara-cara yang dapat Anda mewakili angka negatif 999 00:43:16,290 --> 00:43:19,530 dasarnya adalah, Anda menggunakan salah satu bit khusus untuk menunjukkan 1000 00:43:19,530 --> 00:43:20,400 positif atas negatif. 1001 00:43:20,400 --> 00:43:22,950 Ini sedikit lebih kompleks dari itu, tapi itu ide dasar. 1002 00:43:22,950 --> 00:43:26,740 >> Saking sayangnya, jika C membingungkan satu dari bit dengan benar-benar berarti, 1003 00:43:26,740 --> 00:43:30,790 oh, ini adalah angka negatif, loop saya di sini, misalnya, sebenarnya tidak pernah 1004 00:43:30,790 --> 00:43:31,740 akan mengakhiri. 1005 00:43:31,740 --> 00:43:33,850 Jadi jika saya benar-benar mencetak sesuatu lagi dan lagi, kita akan 1006 00:43:33,850 --> 00:43:34,650 melihat jauh. 1007 00:43:34,650 --> 00:43:36,220 Tapi sekali lagi, ini adalah selain titik. 1008 00:43:36,220 --> 00:43:38,590 Ini benar-benar hanya semacam keingintahuan intelektual yang 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 yang benar pelaksanaan jika kita asumsikan bahwa 1011 00:43:43,400 --> 00:43:45,970 pengguna akan memberikan ints yang cocok dalam ints. 1012 00:43:45,970 --> 00:43:49,370 >> Tapi saya mengklaim bahwa kode ini, terus terang, bisa dilakukan jauh lebih sederhana. 1013 00:43:49,370 --> 00:43:54,060 Jika tujuan di tangan adalah untuk mengambil nomor seperti m dan menjumlahkan semua 1014 00:43:54,060 --> 00:43:59,510 angka antara 1 dan, atau sebaliknya antara 1 dan, saya menyatakan 1015 00:43:59,510 --> 00:44:03,380 bahwa saya dapat meminjam ide ini yang menggabungkan semacam punya, yang mengambil masalah 1016 00:44:03,380 --> 00:44:05,660 ini ukuran dan membaginya menjadi sesuatu yang lebih kecil. 1017 00:44:05,660 --> 00:44:09,875 Mungkin bukan setengah, tetapi lebih kecil, tapi representatif sama. 1018 00:44:09,875 --> 00:44:12,130 Ide yang sama, tapi masalah kecil. 1019 00:44:12,130 --> 00:44:15,470 >> Aku sebenarnya - biarkan aku menyimpan file ini dengan nomor versi yang berbeda. 1020 00:44:15,470 --> 00:44:17,670 Kami akan memanggil versi ini 1 bukan 0. 1021 00:44:17,670 --> 00:44:20,790 Dan saya menyatakan bahwa saya benar-benar dapat reimplement ini semacam ini 1022 00:44:20,790 --> 00:44:22,160 pikiran-lipatan jalan. 1023 00:44:22,160 --> 00:44:23,710 >> Aku akan meninggalkan bagian dari itu sendiri. 1024 00:44:23,710 --> 00:44:27,710 Aku akan mengatakan jika m kurang dari atau bahkan sama dengan 0 - 1025 00:44:27,710 --> 00:44:29,280 Aku hanya akan menjadi sedikit lebih anal saat ini 1026 00:44:29,280 --> 00:44:30,520 dengan kesalahan saya memeriksa - 1027 00:44:30,520 --> 00:44:33,190 Aku akan pergi ke depan dan kembali 0. 1028 00:44:33,190 --> 00:44:34,490 Ini adalah sewenang-wenang. 1029 00:44:34,490 --> 00:44:37,500 Saya hanya hanya memutuskan jika pengguna memberi saya angka negatif, aku 1030 00:44:37,500 --> 00:44:41,490 kembali 0, dan mereka harus membaca dokumentasi lebih dekat. 1031 00:44:41,490 --> 00:44:42,170 >> Lain - 1032 00:44:42,170 --> 00:44:44,070 perhatikan apa yang akan saya lakukan. 1033 00:44:44,070 --> 00:44:49,260 Lain saya akan kembali m ditambah - 1034 00:44:49,260 --> 00:44:51,010 apa yang sigma m? 1035 00:44:51,010 --> 00:44:56,710 Nah, sigma m + m dikurangi 1, ditambah m minus 2, ditambah m dikurangi 3. 1036 00:44:56,710 --> 00:44:58,030 Saya tidak ingin menulis semua yang keluar. 1037 00:44:58,030 --> 00:44:59,120 Mengapa tidak aku hanya tendangan? 1038 00:44:59,120 --> 00:45:05,080 Secara rekursif menyebut diriku dengan sedikit masalah kecil, titik koma, 1039 00:45:05,080 --> 00:45:06,840 dan menyebutnya sehari? 1040 00:45:06,840 --> 00:45:07,040 >> Benar? 1041 00:45:07,040 --> 00:45:10,980 Sekarang di sini, juga, Anda mungkin merasa khawatir atau bahwa ini adalah infinite loop bahwa aku 1042 00:45:10,980 --> 00:45:15,450 merangsang, dimana saya menerapkan sigma dengan menghubungi sigma. 1043 00:45:15,450 --> 00:45:20,342 Tapi itu sangat OK, karena saya berpikir ke depan sebuah menambahkan baris mana? 1044 00:45:20,342 --> 00:45:22,600 >> AUDIENCE: [Tak terdengar]. 1045 00:45:22,600 --> 00:45:25,430 >> DAVID Malan: 23 sampai dengan 26, yang jika kondisi saya. 1046 00:45:25,430 --> 00:45:28,390 Karena apa yang bagus tentang pengurangan di sini, karena saya terus 1047 00:45:28,390 --> 00:45:31,180 menyerahkan masalah kecil sigma, lebih kecil masalah, lebih kecil - itu tidak 1048 00:45:31,180 --> 00:45:31,870 setengah ukuran. 1049 00:45:31,870 --> 00:45:34,380 Ini hanya langkah kecil yang lebih kecil, tapi itu OK. 1050 00:45:34,380 --> 00:45:38,050 Karena pada akhirnya, kami akan bekerja perjalanan ke 1 atau 0. 1051 00:45:38,050 --> 00:45:41,630 Dan setelah kita memukul 0, sigma tidak akan menyebut dirinya lagi. 1052 00:45:41,630 --> 00:45:43,590 Ini akan segera mengembalikan 0. 1053 00:45:43,590 --> 00:45:47,960 >> Jadi efeknya, jika Anda semacam angin ini dalam pikiran Anda, adalah dengan menambahkan m ditambah 1054 00:45:47,960 --> 00:45:52,740 m dikurangi 1, ditambah m minus 2, ditambah m dikurangi 3, ditambah titik, titik, titik, m dikurangi 1055 00:45:52,740 --> 00:45:57,820 m, akhirnya memberikan Anda 0, dan Efek akhirnya menambahkan semua 1056 00:45:57,820 --> 00:45:59,070 hal-hal ini bersama-sama. 1057 00:45:59,070 --> 00:46:02,380 Jadi kita tidak, dengan rekursi, memecahkan masalah yang kita 1058 00:46:02,380 --> 00:46:03,470 tidak bisa memecahkan sebelumnya. 1059 00:46:03,470 --> 00:46:06,840 Memang, versi 0 ini, dan setiap Masalahnya sampai saat ini, telah dipecahkan 1060 00:46:06,840 --> 00:46:09,980 dengan hanya menggunakan untuk loop atau saat loop atau konstruksi serupa. 1061 00:46:09,980 --> 00:46:13,150 >> Tapi rekursi, aku yakin, memberi kita cara berpikir yang berbeda tentang 1062 00:46:13,150 --> 00:46:17,010 masalah, dimana jika kita bisa mengambil Masalahnya, membaginya dari sesuatu 1063 00:46:17,010 --> 00:46:22,340 agak besar menjadi sesuatu yang agak kecil, saya menyatakan bahwa kita bisa mengatasinya 1064 00:46:22,340 --> 00:46:26,040 mungkin sedikit lebih elegan dalam hal dari desain, dengan kode kurang, 1065 00:46:26,040 --> 00:46:30,980 dan bahkan mungkin memecahkan masalah yang akan lebih sulit, karena kita akhirnya akan 1066 00:46:30,980 --> 00:46:33,280 lihat, memecahkan murni iteratif. 1067 00:46:33,280 --> 00:46:35,980 >> Tapi cliffhanger yang saya lakukan ingin meninggalkan kita pada adalah ini. 1068 00:46:35,980 --> 00:46:40,720 Biarkan aku pergi ke depan dan membuka up file dari - 1069 00:46:40,720 --> 00:46:44,300 sebenarnya, biarkan aku pergi dan lakukan sangat cepat ini. 1070 00:46:44,300 --> 00:46:46,875 Biarkan aku pergi ke depan dan mengusulkan berikut. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Diantara kode hari ini adalah file ini di sini. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 Yang ini, NOSWAP. 1075 00:47:03,050 --> 00:47:06,260 >> Jadi ini adalah sebuah program kecil yang bodoh Aku melecut bahwa klaim untuk melakukan 1076 00:47:06,260 --> 00:47:06,940 berikut. 1077 00:47:06,940 --> 00:47:10,140 Dalam utama, pertama menyatakan sebuah int disebut x dan memberikannya 1078 00:47:10,140 --> 00:47:11,100 nilai 1. 1079 00:47:11,100 --> 00:47:13,520 Kemudian menyatakan sebuah y int dan memberikannya nilai 2. 1080 00:47:13,520 --> 00:47:15,310 Kemudian ia akan mencetak apa x dan y adalah. 1081 00:47:15,310 --> 00:47:17,781 Lalu ia berkata, swapping, dot dot dot. 1082 00:47:17,781 --> 00:47:21,670 >> Kemudian mengaku memanggil fungsi disebut swap, lewat di x dan 1083 00:47:21,670 --> 00:47:24,290 y, ide yang merupakan yang diharapkan x dan y akan datang kembali 1084 00:47:24,290 --> 00:47:25,620 berbeda, sebaliknya. 1085 00:47:25,620 --> 00:47:27,110 Kemudian mengklaim bertukar! 1086 00:47:27,110 --> 00:47:28,420 dengan tanda seru. 1087 00:47:28,420 --> 00:47:30,190 Kemudian mencetak x dan y. 1088 00:47:30,190 --> 00:47:33,480 >> Tapi ternyata bahwa ini sangat demonstrasi sederhana turun 1089 00:47:33,480 --> 00:47:35,570 di sini sebenarnya kereta. 1090 00:47:35,570 --> 00:47:38,870 Meskipun saya menyatakan sementara variabel dan untuk sementara menempatkan di 1091 00:47:38,870 --> 00:47:42,010 itu, maka aku pemindahan a nilai b - 1092 00:47:42,010 --> 00:47:45,080 yang terasa wajar, karena saya sudah menyimpan salinan di temp. 1093 00:47:45,080 --> 00:47:48,410 Kemudian saya update b untuk sama apa pun yang ada di temp. 1094 00:47:48,410 --> 00:47:51,610 Ini semacam permainan cangkang bergerak ke b dan b menjadi dengan menggunakan 1095 00:47:51,610 --> 00:47:54,360 tengah-manusia yang disebut suhu terasa sangat masuk akal. 1096 00:47:54,360 --> 00:47:57,270 >> Tapi saya mengklaim bahwa ketika saya menjalankan ini kode, seperti yang akan saya lakukan sekarang - 1097 00:47:57,270 --> 00:47:59,490 biarkan aku pergi ke depan dan paste di sini. 1098 00:47:59,490 --> 00:48:01,995 Aku akan menelepon noswap.c ini. 1099 00:48:01,995 --> 00:48:05,630 Dan seperti namanya, ini bukan akan menjadi program yang benar. 1100 00:48:05,630 --> 00:48:09,460 Membuat NOSWAP. / Tanpa swap. 1101 00:48:09,460 --> 00:48:12,110 x 1, y adalah 2, swapping, bertukar. 1102 00:48:12,110 --> 00:48:14,220 x 1, y adalah 2. 1103 00:48:14,220 --> 00:48:16,920 Ini adalah fundamental salah, bahkan meskipun ini tampaknya sempurna 1104 00:48:16,920 --> 00:48:17,730 masuk akal untuk saya. 1105 00:48:17,730 --> 00:48:21,330 Dan ada alasan, tapi kami tidak akan mengungkapkan alasannya dulu. 1106 00:48:21,330 --> 00:48:24,610 >> Untuk saat ini Cliffhanger kedua saya ingin untuk meninggalkan Anda dengan adalah ini, 1107 00:48:24,610 --> 00:48:27,120 pengumuman macam pada kode kupon. 1108 00:48:27,120 --> 00:48:31,590 Inovasi kami dengan hari-hari akhir tahun ini telah menimbulkan sejumlah non-sepele 1109 00:48:31,590 --> 00:48:33,830 pertanyaan, yang bukan maksud kami. 1110 00:48:33,830 --> 00:48:36,590 Tujuan dari kode kupon, dimana jika Anda melakukan bagian dari masalah 1111 00:48:36,590 --> 00:48:39,850 ditetapkan di awal, sehingga mendapatkan satu hari ekstra, benar-benar untuk membantu kalian membantu 1112 00:48:39,850 --> 00:48:42,420 sendiri mulai awal, semacam dari incentivizing dengan Anda. 1113 00:48:42,420 --> 00:48:44,880 Membantu kita mendistribusikan beban di jam kantor lebih baik sehingga 1114 00:48:44,880 --> 00:48:45,740 itu semacam menang-menang. 1115 00:48:45,740 --> 00:48:48,860 >> Sayangnya, saya pikir instruksi saya belum, sampai saat ini, sangat jelas, sehingga 1116 00:48:48,860 --> 00:48:52,230 Aku kembali akhir pekan ini dan diperbarui spec di besar, teks lebih berani untuk 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 lebih terbuka, dengan default, masalah set disebabkan Kamis 1119 00:48:56,900 --> 00:48:58,400 pada siang hari, per silabus. 1120 00:48:58,400 --> 00:49:02,030 Jika Anda mulai awal, menyelesaikan bagian dari permasalahan yang disampaikan oleh Rabu pukul 12:00 1121 00:49:02,030 --> 00:49:05,170 PM, bagian yang berhubungan dengan kupon kode, idenya adalah bahwa Anda dapat memperpanjang 1122 00:49:05,170 --> 00:49:07,710 batas waktu Anda untuk P mengatur sampai Jumat. 1123 00:49:07,710 --> 00:49:10,890 Artinya, sedikit dari bagian kecil dari P mengatur relatif terhadap apa yang biasanya adalah 1124 00:49:10,890 --> 00:49:13,200 masalah yang lebih besar, dan Anda membeli diri satu hari ekstra. 1125 00:49:13,200 --> 00:49:15,190 Sekali lagi, itu membuat Anda berpikir tentang sejumlah masalah, membawa Anda ke 1126 00:49:15,190 --> 00:49:16,380 jam kantor lebih cepat. 1127 00:49:16,380 --> 00:49:20,670 Tapi masalah kode kupon masih diperlukan, bahkan jika Anda tidak mengirimkannya. 1128 00:49:20,670 --> 00:49:23,340 >> Tapi yang lebih compellingly adalah ini. 1129 00:49:23,340 --> 00:49:26,520 (STAGE WHISPER) Dan orang-orang itu meninggalkan dini akan menyesal. 1130 00:49:26,520 --> 00:49:28,620 Sebagaimana orang-orang di balkon. 1131 00:49:28,620 --> 00:49:32,510 Saya mohon maaf sebelumnya kepada orang-orang di balkon untuk alasan-alasan yang akan 1132 00:49:32,510 --> 00:49:33,920 jelas hanya dalam beberapa saat. 1133 00:49:33,920 --> 00:49:37,050 >> Jadi kita beruntung untuk memiliki salah satu Mantan rekan pengajar kepala CS50 yang di 1134 00:49:37,050 --> 00:49:39,302 sebuah perusahaan bernama dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 Mereka telah sangat bermurah hati menyumbangkan kode kupon di sini selama ini banyak ruang, 1136 00:49:45,500 --> 00:49:48,180 yang naik dari biasanya 2 gigabyte. 1137 00:49:48,180 --> 00:49:51,740 Jadi apa yang saya pikir kami akan melakukan hal ini catatan akhir adalah melakukan sedikit giveaway, 1138 00:49:51,740 --> 00:49:55,380 dimana hanya dalam beberapa saat, kami akan mengungkapkan pemenang dan yang memiliki kupon 1139 00:49:55,380 --> 00:49:57,980 kode yang Anda dapat pergi ke mereka website, ketik dalam, dan voila, mendapatkan 1140 00:49:57,980 --> 00:50:01,370 lebih jauh Dropbox ruang untuk Anda alat dan untuk file pribadi Anda. 1141 00:50:01,370 --> 00:50:05,690 >> Dan pertama-tama, yang ingin berpartisipasi dalam gambar ini? 1142 00:50:05,690 --> 00:50:09,630 OK, sekarang yang membuatnya bahkan lebih menyenangkan. 1143 00:50:09,630 --> 00:50:14,010 Orang yang menerima ini 25-gigabyte kode kupon - yang jauh 1144 00:50:14,010 --> 00:50:16,150 lebih menarik daripada akhir hari sekarang, mungkin - 1145 00:50:16,150 --> 00:50:20,620 adalah orang yang duduk di atas bantalan kursi di bawahnya ada 1146 00:50:20,620 --> 00:50:21,620 kode kupon. 1147 00:50:21,620 --> 00:50:23,480 Sekarang Anda dapat melihat di bawah bantalan kursi Anda. 1148 00:50:23,480 --> 00:50:28,710 1149 00:50:28,710 --> 00:50:29,680 >> [VIDEO PEMUTARAN] 1150 00:50:29,680 --> 00:50:31,620 >> -Satu, dua, tiga. 1151 00:50:31,620 --> 00:50:35,015 >> [BERTERIAK] 1152 00:50:35,015 --> 00:50:35,985 >> -Anda mendapatkan mobil! 1153 00:50:35,985 --> 00:50:36,670 Anda mendapatkan mobil! 1154 00:50:36,670 --> 00:50:37,970 >> DAVID Malan: Kita akan melihat Anda Rabu. 1155 00:50:37,970 --> 00:50:38,904 >> -Anda mendapatkan mobil! 1156 00:50:38,904 --> 00:50:39,371 Anda mendapatkan mobil! 1157 00:50:39,371 --> 00:50:40,305 Anda mendapatkan mobil! 1158 00:50:40,305 --> 00:50:41,706 Anda mendapatkan mobil! 1159 00:50:41,706 --> 00:50:43,107 Anda mendapatkan mobil! 1160 00:50:43,107 --> 00:50:45,530 >> DAVID Malan: Balcony orang, datang di sini ke depan, 1161 00:50:45,530 --> 00:50:46,866 di mana kita memiliki ekstra. 1162 00:50:46,866 --> 00:50:50,282 >> -Semua orang mendapat mobil! 1163 00:50:50,282 --> 00:50:52,234 Semua orang mendapat mobil! 1164 00:50:52,234 --> 00:50:52,722 >> [END VIDEO PEMUTARAN] 1165 00:50:52,722 --> 00:50:54,590 >> Narator: Pada CS50 berikutnya - 1166 00:50:54,590 --> 00:51:00,374 >> SPEAKER 5: Oh my gosh gosh gosh gosh gosh gosh gosh gosh gosh gosh - 1167 00:51:00,374 --> 00:51:02,106 >> [Ukelele drama]