1 00:00:00,000 --> 00:00:11,100 2 00:00:11,100 --> 00:00:12,300 >> SPEAKER 1: Hey everyone! 3 00:00:12,300 --> 00:00:13,890 Selamat datang kembali ke bagian. 4 00:00:13,890 --> 00:00:17,480 Sangat senang melihat begitu banyak dari Anda berdua di sini, dan semua orang yang menonton secara online. 5 00:00:17,480 --> 00:00:18,760 6 00:00:18,760 --> 00:00:20,920 Jadi, sebagai Selamat datang biasa kembali. 7 00:00:20,920 --> 00:00:24,360 Saya harap Anda semua memiliki yang indah akhir pekan, penuh istirahat, relaksasi. 8 00:00:24,360 --> 00:00:26,026 Itu indah kemarin. 9 00:00:26,026 --> 00:00:27,525 Jadi, saya harap Anda menikmati alam bebas. 10 00:00:27,525 --> 00:00:28,840 11 00:00:28,840 --> 00:00:30,610 >> Jadi pertama beberapa pengumuman. 12 00:00:30,610 --> 00:00:31,920 13 00:00:31,920 --> 00:00:32,700 Grading. 14 00:00:32,700 --> 00:00:37,350 Jadi, sebagian besar dari Anda harus mendapatkan sebuah email dari saya tentang Pset Scratch Anda, 15 00:00:37,350 --> 00:00:39,920 serta gradasi untuk Pset 1. 16 00:00:39,920 --> 00:00:41,000 17 00:00:41,000 --> 00:00:42,220 Jadi, hanya beberapa hal. 18 00:00:42,220 --> 00:00:45,150 Pastikan untuk menggunakan check50 di style50. 19 00:00:45,150 --> 00:00:47,250 Ini dimaksudkan untuk menjadi sumber daya untuk kalian, 20 00:00:47,250 --> 00:00:50,660 untuk memastikan bahwa Anda mendapatkan poin sebanyak yang Anda bisa 21 00:00:50,660 --> 00:00:52,390 tanpa sia-sia kehilangan mereka. 22 00:00:52,390 --> 00:00:54,407 Jadi, hal-hal seperti gaya sangat penting. 23 00:00:54,407 --> 00:00:55,740 Kita akan lepas landas untuk itu. 24 00:00:55,740 --> 00:00:58,115 Beberapa dari Anda mungkin sudah melihat bahwa dari Pset Anda. 25 00:00:58,115 --> 00:00:58,920 26 00:00:58,920 --> 00:01:01,450 Dan check50 hanya cara yang sangat mudah untuk memastikan 27 00:01:01,450 --> 00:01:05,050 bahwa kita benar-benar kembali apa perlu kembali ke pengguna, 28 00:01:05,050 --> 00:01:06,690 dan bahwa segala sesuatu bekerja dengan baik. 29 00:01:06,690 --> 00:01:08,690 30 00:01:08,690 --> 00:01:12,040 >> Pada catatan kedua, pastikan Anda meng-upload hal-hal ke folder yang benar. 31 00:01:12,040 --> 00:01:14,470 Itu membuat hidup saya hanya sedikit lebih sulit 32 00:01:14,470 --> 00:01:18,836 jika Anda meng-upload Pset 2 ke Pset 1 karena ketika saya men-download hal-hal, 33 00:01:18,836 --> 00:01:20,085 mereka tidak men-download dengan benar. 34 00:01:20,085 --> 00:01:21,690 35 00:01:21,690 --> 00:01:24,560 Dan aku tahu itu miring sedikit dalam suatu sistem untuk membiasakan diri, 36 00:01:24,560 --> 00:01:26,950 tetapi hanya menjadi super hati-hati, jika hanya untuk saya, 37 00:01:26,950 --> 00:01:30,080 sehingga ketika Anda mendapatkan email di seperti 2:00 dan aku grading. 38 00:01:30,080 --> 00:01:33,710 Jika tidak menyebabkan saya harus melihat semua sekitar untuk Pset Anda. 39 00:01:33,710 --> 00:01:34,440 Keren. 40 00:01:34,440 --> 00:01:37,270 >> Aku tahu itu lebih awal, tapi aku benar-benar mendapat lengah 41 00:01:37,270 --> 00:01:40,800 oleh esai itu karena hari Jumat ini, bahwa profesor saya hanya suka, oh yeah. 42 00:01:40,800 --> 00:01:42,550 Ingat, Anda memiliki esai tempo pada Jumat. 43 00:01:42,550 --> 00:01:45,780 Jadi, saya tahu tidak ada yang suka untuk berpikir tentang ujian tengah semester, 44 00:01:45,780 --> 00:01:50,620 tapi kuis pertama Anda adalah pada 15 Oktober, yang Oktober mulai minggu ini. 45 00:01:50,620 --> 00:01:53,290 Jadi, mungkin lebih cepat dari yang Anda harapkan semua. 46 00:01:53,290 --> 00:01:57,510 Sehingga Anda tidak dilemparkan lengah ketika Saya menyebutkan bagian minggu depan yang oh, 47 00:01:57,510 --> 00:02:00,560 kuis minggu berikutnya, saya pikir Saya akan memberikan Anda sedikit lebih 48 00:02:00,560 --> 00:02:01,500 dari kepala sampai sekarang. 49 00:02:01,500 --> 00:02:02,970 50 00:02:02,970 --> 00:02:04,660 >> Jadi, masalah Anda mengatur, nomor tiga. 51 00:02:04,660 --> 00:02:07,070 Bagaimana orang telah membaca spec keluar dari rasa ingin tahu? 52 00:02:07,070 --> 00:02:08,560 53 00:02:08,560 --> 00:02:09,199 OK. 54 00:02:09,199 --> 00:02:10,229 Kami punya beberapa. 55 00:02:10,229 --> 00:02:12,320 Jenis turun dari lalu minggu tapi itu OK. 56 00:02:12,320 --> 00:02:13,650 Aku tahu itu keluar indah. 57 00:02:13,650 --> 00:02:15,120 58 00:02:15,120 --> 00:02:16,660 Jadi Break Out. 59 00:02:16,660 --> 00:02:21,010 Pasti setelah Anda selesai hari ini membaca spec setidaknya 60 00:02:21,010 --> 00:02:25,240 coba seperti men-download Kode distribusi dan berjalan 61 00:02:25,240 --> 00:02:27,430 seperti awal pertama hal yang mereka meminta Anda untuk. 62 00:02:27,430 --> 00:02:28,681 63 00:02:28,681 --> 00:02:32,590 Karena kita menggunakan Kode distribusi dan perpustakaan 64 00:02:32,590 --> 00:02:36,790 bahwa kita hanya pernah using-- --Itu hanya kedua kalinya kami sudah melakukan Pset ini, 65 00:02:36,790 --> 00:02:38,650 hal-hal gila bisa terjadi dengan alat Anda, 66 00:02:38,650 --> 00:02:41,370 dan Anda ingin menemukan bahwa keluar sekarang dibandingkan nanti. 67 00:02:41,370 --> 00:02:45,570 >> Karena jika itu Kamis malam atau itu Rabu malam dan untuk beberapa alasan 68 00:02:45,570 --> 00:02:48,912 alat Anda hanya tidak ingin menjalankan dengan perpustakaan 69 00:02:48,912 --> 00:02:50,620 atau dengan distribusi kode, yang berarti 70 00:02:50,620 --> 00:02:52,309 Anda bahkan tidak dapat mulai melakukan coding. 71 00:02:52,309 --> 00:02:54,100 Karena Anda tidak dapat memeriksa untuk melihat apakah ia bekerja. 72 00:02:54,100 --> 00:02:55,975 Anda tidak akan dapat untuk melihat apakah mengkompilasi. 73 00:02:55,975 --> 00:03:00,500 Anda ingin mengurus mereka di awal minggu itu, ketika Anda masih bisa email saya 74 00:03:00,500 --> 00:03:03,100 atau salah satu dari TF lainnya, dan kita bisa mendapatkan mereka tetap. 75 00:03:03,100 --> 00:03:05,410 Karena mereka adalah isu-isu yang akan menghentikan Anda 76 00:03:05,410 --> 00:03:07,120 dari membuat kemajuan nyata. 77 00:03:07,120 --> 00:03:10,055 Ini tidak seperti salah satu bug, yang Anda dapat hanya jenis melewatkan. 78 00:03:10,055 --> 00:03:10,712 79 00:03:10,712 --> 00:03:13,420 Jika Anda mengalami masalah dengan Anda alat atau kode distribusi, 80 00:03:13,420 --> 00:03:16,211 Anda benar-benar ingin mendapatkan yang diambil peduli lebih awal daripada kemudian. 81 00:03:16,211 --> 00:03:20,410 Jadi bahkan jika Anda tidak benar-benar gonna mulai coding, download distribusi 82 00:03:20,410 --> 00:03:24,040 kode, membaca spec, pastikan semuanya bekerja di sana. 83 00:03:24,040 --> 00:03:25,134 OK? 84 00:03:25,134 --> 00:03:27,675 Jika Anda hanya dapat melakukan itu, saya berjanji hidup Anda akan lebih mudah. 85 00:03:27,675 --> 00:03:28,800 86 00:03:28,800 --> 00:03:31,410 Dan Anda mungkin akan untuk melakukannya sekarang kan? 87 00:03:31,410 --> 00:03:32,100 OK. 88 00:03:32,100 --> 00:03:33,950 Jadi, pertanyaan di sana? 89 00:03:33,950 --> 00:03:35,850 Setiap hal logistik? 90 00:03:35,850 --> 00:03:36,910 Semua orang baik? 91 00:03:36,910 --> 00:03:38,270 OK. 92 00:03:38,270 --> 00:03:41,700 >> Disclaimer bagi Anda di kamar dan online. 93 00:03:41,700 --> 00:03:45,437 Aku akan mencoba untuk beralih antara PowerPoint di alat 94 00:03:45,437 --> 00:03:47,270 karena kita akan menjadi melakukan beberapa coding 95 00:03:47,270 --> 00:03:53,630 hari ini oleh permintaan populer dari anonim jajak pendapat saran saya mengirimkan minggu lalu. 96 00:03:53,630 --> 00:03:55,480 Jadi, kita akan melakukan beberapa coding. 97 00:03:55,480 --> 00:03:57,800 Jadi, jika kalian juga ingin untuk menjalankan peralatan Anda, 98 00:03:57,800 --> 00:04:02,910 dan Anda harus punya email dari saya, dengan contoh file. 99 00:04:02,910 --> 00:04:04,310 Jangan ragu untuk melakukan itu. 100 00:04:04,310 --> 00:04:07,340 >> Jadi, kita akan berbicara tentang GDB, yang merupakan debugger. 101 00:04:07,340 --> 00:04:09,970 Ini akan membantu Anda jenis mencari tahu di mana 102 00:04:09,970 --> 00:04:11,860 hal-hal yang tidak beres dalam kode Anda. 103 00:04:11,860 --> 00:04:15,370 Ini benar-benar hanya satu cara bagi Anda untuk melangkah melalui kode Anda seperti itu terjadi, 104 00:04:15,370 --> 00:04:19,100 dan mampu mencetak variabel atau melihat apa yang sebenarnya terjadi 105 00:04:19,100 --> 00:04:22,980 di bawah tenda ayat program Anda hanya berjalan, itu seperti faulting, 106 00:04:22,980 --> 00:04:25,030 dan Anda seperti, tidak tahu apa yang baru saja terjadi di sini. 107 00:04:25,030 --> 00:04:26,730 Aku tidak tahu apa garis itu gagal. 108 00:04:26,730 --> 00:04:29,040 Aku tidak tahu di mana itu salah. 109 00:04:29,040 --> 00:04:31,280 Jadi, GDB akan membantu Anda dengan itu. 110 00:04:31,280 --> 00:04:35,240 Juga, jika Anda memutuskan untuk terus ya, dan mengambil 61, 111 00:04:35,240 --> 00:04:38,430 itu akan benar-benar, benar-benar akan Anda sahabat, karena aku dapat memberitahu Anda 112 00:04:38,430 --> 00:04:40,840 karena aku akan melalui kelas itu. 113 00:04:40,840 --> 00:04:43,620 >> Kita akan melihat biner pencarian, yang jika kalian ingat 114 00:04:43,620 --> 00:04:47,540 besar buku telepon contoh tontonan dari kelas. 115 00:04:47,540 --> 00:04:50,620 Kami akan menerapkan itu, dan berjalan melalui itu sedikit lebih, 116 00:04:50,620 --> 00:04:54,650 dan kemudian kita akan melalui empat berbagai macam, yaitu Bubble, 117 00:04:54,650 --> 00:04:56,285 Seleksi, penyisipan, dan Merge. 118 00:04:56,285 --> 00:04:57,830 119 00:04:57,830 --> 00:04:58,330 Keren. 120 00:04:58,330 --> 00:05:00,390 Jadi, GDB seperti yang saya sebutkan, adalah debugger. 121 00:05:00,390 --> 00:05:01,400 122 00:05:01,400 --> 00:05:09,370 Dan ini adalah jenis besar hal, fungsi besar atau perintah 123 00:05:09,370 --> 00:05:13,240 yang Anda gunakan dalam GDB, dan saya akan berjalan Anda melalui demo itu dalam hitungan detik. 124 00:05:13,240 --> 00:05:15,360 >> Jadi, ini bukan hanya akan tinggal abstrak. 125 00:05:15,360 --> 00:05:18,000 Saya akan mencoba dan membuatnya sebagai beton mungkin bagi kalian. 126 00:05:18,000 --> 00:05:19,870 Jadi, istirahat. 127 00:05:19,870 --> 00:05:22,200 Itu baik akan istirahat seperti, beberapa nomor, yang 128 00:05:22,200 --> 00:05:26,900 merupakan garis dalam program Anda, atau Anda dapat nama fungsi. 129 00:05:26,900 --> 00:05:30,150 Jadi, jika Anda mengatakan istirahat utama, itu akan berhenti di utama, 130 00:05:30,150 --> 00:05:32,400 dan membiarkan Anda berjalan melalui fungsi tersebut. 131 00:05:32,400 --> 00:05:36,350 >> Demikian juga, jika Anda memiliki beberapa eksternal berfungsi seperti Swap atau Cube, 132 00:05:36,350 --> 00:05:38,450 bahwa kita melihat pekan lalu. 133 00:05:38,450 --> 00:05:41,780 Jika Anda mengatakan melanggar salah satu dari mereka, setiap kali program Anda memukul itu, 134 00:05:41,780 --> 00:05:44,290 itu akan menunggu Anda untuk memberitahu apa yang harus dilakukan. 135 00:05:44,290 --> 00:05:47,860 Sebelum itu hanya akan mengeksekusi sehingga Anda benar-benar bisa melangkah di dalam fungsi 136 00:05:47,860 --> 00:05:49,020 dan melihat apa yang terjadi. 137 00:05:49,020 --> 00:05:50,370 138 00:05:50,370 --> 00:05:53,515 Jadi, Next, hanya melompat di atas baris berikutnya, berjalan di atas fungsi. 139 00:05:53,515 --> 00:05:54,730 140 00:05:54,730 --> 00:05:55,560 Langkah. 141 00:05:55,560 --> 00:05:56,810 Ini semua adalah abstrak kecil. 142 00:05:56,810 --> 00:06:00,530 Jadi, aku hanya akan berjalan melalui mereka, tetapi Anda akan melihat mereka digunakan dalam satu detik. 143 00:06:00,530 --> 00:06:01,810 >> Masuki fungsi. 144 00:06:01,810 --> 00:06:04,170 Jadi seperti yang saya katakan, seperti dengan Swap, itu akan 145 00:06:04,170 --> 00:06:07,110 memungkinkan Anda untuk benar-benar seolah-olah Anda seperti fisik melangkah di dalam, 146 00:06:07,110 --> 00:06:10,990 Anda bisa main dengan variabel, cetak tahu apa yang mereka, lihat apa yang terjadi. 147 00:06:10,990 --> 00:06:12,140 148 00:06:12,140 --> 00:06:14,830 Daftar harfiah akan hanya mencetak out kode sekitarnya. 149 00:06:14,830 --> 00:06:17,570 Jadi, jika Anda jenis lupa di mana Anda berada dalam program Anda, 150 00:06:17,570 --> 00:06:19,880 atau Anda bertanya-tanya apa yang terjadi di sekitarnya, 151 00:06:19,880 --> 00:06:23,790 ini hanya akan mencetak segmen dari seperti lima atau enam baris di sekitarnya. 152 00:06:23,790 --> 00:06:26,080 Jadi, Anda dapat mendapatkan berorientasi tentang di mana Anda berada. 153 00:06:26,080 --> 00:06:27,230 154 00:06:27,230 --> 00:06:28,650 >> Mencetak beberapa variabel. 155 00:06:28,650 --> 00:06:34,590 Jadi, jika Anda memiliki kunci seperti di Caesar, bahwa kita akan melihat. 156 00:06:34,590 --> 00:06:36,220 Anda dapat mengatakan Cetak Key pada titik apapun. 157 00:06:36,220 --> 00:06:40,070 Ini akan memberitahu Anda apa nilai begitu itu, mungkin di suatu tempat di sepanjang jalan, 158 00:06:40,070 --> 00:06:42,070 Anda menimpa kunci Anda. 159 00:06:42,070 --> 00:06:45,495 Anda benar-benar bisa mengatakan bahwa karena Anda benar-benar dapat mengamati nilai tersebut. 160 00:06:45,495 --> 00:06:46,500 161 00:06:46,500 --> 00:06:48,780 >> Dalam penduduk setempat, hanya cetakan out variabel lokal Anda. 162 00:06:48,780 --> 00:06:53,120 Jadi, kapan Anda berada dalam satu lingkaran, dan Anda hanya ingin melihat seperti, oh. 163 00:06:53,120 --> 00:06:54,270 Apa saya? 164 00:06:54,270 --> 00:06:57,020 Apa nilai kunci ini bahwa saya menginisialisasi sini? 165 00:06:57,020 --> 00:06:58,537 Apa pesan pada saat ini? 166 00:06:58,537 --> 00:07:00,370 Itu hanya akan mencetak semua dari mereka, sehingga Anda 167 00:07:00,370 --> 00:07:04,330 tidak perlu secara individual mengatakan, Print I. Print Pesan. 168 00:07:04,330 --> 00:07:04,970 Cetak Key. 169 00:07:04,970 --> 00:07:06,190 170 00:07:06,190 --> 00:07:07,700 Dan kemudian Tampilan. 171 00:07:07,700 --> 00:07:10,370 Apa yang dilakukan adalah seperti yang Anda langkah melalui program ini, 172 00:07:10,370 --> 00:07:13,980 itu hanya akan memastikan bahwa itu menampilkan beberapa variabel tertentu 173 00:07:13,980 --> 00:07:14,780 di setiap titik. 174 00:07:14,780 --> 00:07:17,160 Sehingga Anda also-- --Itu adalah jenis jalan pintas mana 175 00:07:17,160 --> 00:07:19,530 Anda tidak harus terus seperti, oh. 176 00:07:19,530 --> 00:07:23,150 Cetak Key atau Print I. Itu hanya otomatis akan melakukannya untuk Anda. 177 00:07:23,150 --> 00:07:25,959 >> Jadi, dengan itu, kita akan untuk melihat bagaimana ini berjalan. 178 00:07:25,959 --> 00:07:28,000 Aku akan mencoba dan beralih ke alat saya. 179 00:07:28,000 --> 00:07:30,200 180 00:07:30,200 --> 00:07:31,271 Lihat apakah saya bisa melakukan ini. 181 00:07:31,271 --> 00:07:31,770 Semua. 182 00:07:31,770 --> 00:07:40,970 183 00:07:40,970 --> 00:07:42,370 Kami hanya akan cermin itu. 184 00:07:42,370 --> 00:07:44,530 Tidak ada yang gila di laptop saya anyways. 185 00:07:44,530 --> 00:07:49,600 186 00:07:49,600 --> 00:07:50,100 OK. 187 00:07:50,100 --> 00:07:57,030 188 00:07:57,030 --> 00:08:01,054 Hal ini perlu menjadi satu ini. 189 00:08:01,054 --> 00:08:01,795 Ini sangat kecil. 190 00:08:01,795 --> 00:08:03,730 191 00:08:03,730 --> 00:08:05,120 Mari kita lihat apakah kita bisa melakukan ini. 192 00:08:05,120 --> 00:08:09,970 193 00:08:09,970 --> 00:08:10,940 >> OK. 194 00:08:10,940 --> 00:08:15,305 Alice jelas berjuang di sini hanya sedikit, 195 00:08:15,305 --> 00:08:17,995 namun kami akan mendapatkannya di momento. 196 00:08:17,995 --> 00:08:20,810 197 00:08:20,810 --> 00:08:22,020 OK. 198 00:08:22,020 --> 00:08:25,900 Kami hanya akan meningkatkan ini. 199 00:08:25,900 --> 00:08:28,770 200 00:08:28,770 --> 00:08:29,380 OK. 201 00:08:29,380 --> 00:08:31,679 Dapatkah orang semacam melihat bahwa? 202 00:08:31,679 --> 00:08:32,470 Mungkin sedikit? 203 00:08:32,470 --> 00:08:33,594 Aku tahu itu agak kecil. 204 00:08:33,594 --> 00:08:34,570 205 00:08:34,570 --> 00:08:37,530 Anda tidak bisa mencari tahu bagaimana membuat ini lebih besar. 206 00:08:37,530 --> 00:08:38,350 Jika ada yang tahu. 207 00:08:38,350 --> 00:08:40,309 Apakah ada yang tahu bagaimana membuatnya lebih besar? 208 00:08:40,309 --> 00:08:40,932 OK. 209 00:08:40,932 --> 00:08:42,140 Kita akan roll dengan itu. 210 00:08:42,140 --> 00:08:45,801 Tidak peduli lagian karena itu hanya itulah kode yang kalian harus 211 00:08:45,801 --> 00:08:46,300 memiliki. 212 00:08:46,300 --> 00:08:48,310 >> Apa yang lebih penting adalah terminal sini. 213 00:08:48,310 --> 00:08:52,840 214 00:08:52,840 --> 00:08:58,690 Dan kita miliki di sini Mengapa begitu kecil? 215 00:08:58,690 --> 00:09:02,325 216 00:09:02,325 --> 00:09:02,825 Pengaturan. 217 00:09:02,825 --> 00:09:07,920 218 00:09:07,920 --> 00:09:08,420 Oh. 219 00:09:08,420 --> 00:09:09,500 Benar Ike. 220 00:09:09,500 --> 00:09:10,880 Bagaimana ini? 221 00:09:10,880 --> 00:09:11,770 Keluar dari sana. 222 00:09:11,770 --> 00:09:19,370 223 00:09:19,370 --> 00:09:21,810 Apakah itu baik bagi semua orang? 224 00:09:21,810 --> 00:09:22,525 OK ,. 225 00:09:22,525 --> 00:09:23,025 Keren. 226 00:09:23,025 --> 00:09:25,830 227 00:09:25,830 --> 00:09:28,220 >> Anda tahu ketika Anda berada di CS kesulitan teknis kelas 228 00:09:28,220 --> 00:09:32,971 adalah jenis bagian dari the-- Jadi, mari kita membersihkan ini. 229 00:09:32,971 --> 00:09:33,470 OK. 230 00:09:33,470 --> 00:09:38,060 Jadi, di sini, di bagian, yang kami punya di sini. 231 00:09:38,060 --> 00:09:40,830 Caesar adalah file eksekusi. 232 00:09:40,830 --> 00:09:41,800 Jadi saya membuatnya. 233 00:09:41,800 --> 00:09:46,370 Jadi, satu hal yang perlu disadari dengan GDB adalah bahwa ia hanya bekerja pada file yang dapat dieksekusi. 234 00:09:46,370 --> 00:09:48,040 Jadi, Anda tidak dapat menjalankannya pada dotsy a. 235 00:09:48,040 --> 00:09:50,532 Anda harus benar-benar membuat memastikan bahwa kode Anda mengkompilasi, 236 00:09:50,532 --> 00:09:51,865 dan bahwa hal itu dapat benar-benar dijalankan. 237 00:09:51,865 --> 00:09:52,970 238 00:09:52,970 --> 00:09:56,186 >> Jadi, pastikan bahwa jika tidak kompilasi, mendapatkannya untuk mengkompilasi, 239 00:09:56,186 --> 00:09:57,810 sehingga Anda dapat jenis berjalan melalui itu. 240 00:09:57,810 --> 00:10:04,590 Jadi, untuk memulai GDB, semua yang Anda lakukan, Gloria Jenis GDB, dan kemudian hanya 241 00:10:04,590 --> 00:10:06,250 mengajukan yang Anda inginkan. 242 00:10:06,250 --> 00:10:08,240 Saya selalu misspell Caesar. 243 00:10:08,240 --> 00:10:11,730 Tapi Anda ingin memastikan karena itu dieksekusi, 244 00:10:11,730 --> 00:10:14,210 ti itu dot kilat sehingga berarti Anda akan 245 00:10:14,210 --> 00:10:19,240 untuk menjalankan CSI Anda akan mengeksekusi ini file baik dengan debugger. 246 00:10:19,240 --> 00:10:19,910 OK. 247 00:10:19,910 --> 00:10:22,885 Jadi, Anda melakukan itu, Anda mendapatkan semacam ini omong kosong. 248 00:10:22,885 --> 00:10:24,250 249 00:10:24,250 --> 00:10:25,750 Hanya saja semua hal tentang debugger. 250 00:10:25,750 --> 00:10:28,200 Anda tidak benar-benar harus khawatir tentang hal itu sekarang. 251 00:10:28,200 --> 00:10:31,460 Dan seperti yang Anda lihat, kami punya ini parens terbuka, PDB, parens dekat, 252 00:10:31,460 --> 00:10:34,690 dan hanya jenis terlihat seperti baris perintah kita, kan? 253 00:10:34,690 --> 00:10:37,010 >> Jadi, apa yang ingin kita do-- --So, Hal pertama 254 00:10:37,010 --> 00:10:39,570 adalah kita ingin memilih tempat untuk memecahkannya. 255 00:10:39,570 --> 00:10:42,332 Jadi, ada satu bug dalam program Caesar ini 256 00:10:42,332 --> 00:10:44,290 bahwa saya memperkenalkan, bahwa kita akan mencari tahu. 257 00:10:44,290 --> 00:10:45,330 258 00:10:45,330 --> 00:10:56,350 Itu Apa yang dilakukannya adalah dibutuhkan input Barfoo dalam semua topi, dan untuk beberapa alasan 259 00:10:56,350 --> 00:11:01,950 itu tidak mengubah A. Itu hanya daun sendiri, Apakah segala sesuatu yang lain benar, 260 00:11:01,950 --> 00:11:03,980 tapi surat kedua A tetap tidak berubah. 261 00:11:03,980 --> 00:11:07,120 Jadi, kita akan mencoba dan mencari tahu mengapa itu. 262 00:11:07,120 --> 00:11:10,440 Jadi, hal pertama yang Anda biasanya ingin melakukan setiap kali Anda mulai pada GDB 263 00:11:10,440 --> 00:11:12,010 adalah mencari tahu di mana untuk memecahkannya. 264 00:11:12,010 --> 00:11:14,956 >> Jadi Caesar adalah program yang cukup singkat. 265 00:11:14,956 --> 00:11:16,330 Kami hanya memiliki satu fungsi, kan? 266 00:11:16,330 --> 00:11:18,520 Apa fungsi kita di Caesar? 267 00:11:18,520 --> 00:11:19,590 268 00:11:19,590 --> 00:11:24,350 Hanya ada satu fungsi, hak Main? 269 00:11:24,350 --> 00:11:26,490 Utama adalah fungsi untuk semua program Anda. 270 00:11:26,490 --> 00:11:29,230 Jika Anda tidak memiliki Main, aku mungkin menjadi sedikit khawatir sekarang, 271 00:11:29,230 --> 00:11:31,000 tapi saya harap Anda semua memiliki Main di sana. 272 00:11:31,000 --> 00:11:34,150 Jadi, apa yang bisa kita lakukan adalah kita bisa hanya istirahat Main, begitu saja. 273 00:11:34,150 --> 00:11:35,190 Jadi, ia mengatakan, OK. 274 00:11:35,190 --> 00:11:37,430 Kami menetapkan satu breakpoint kami di sana. 275 00:11:37,430 --> 00:11:42,870 >> Jadi, sekarang hal yang perlu diingat adalah Caesar mengambil satu perintah argumen baris yang tepat 276 00:11:42,870 --> 00:11:45,150 dan kami tidak melakukan hal itu di mana saja belum. 277 00:11:45,150 --> 00:11:47,560 Jadi, apa yang Anda lakukan adalah ketika Anda benar-benar pergi untuk menjalankan 278 00:11:47,560 --> 00:11:51,540 program, program apapun yang Anda berjalan di GDB yang perlu baris perintah 279 00:11:51,540 --> 00:11:55,010 argumen, Anda akan masukan ketika Anda pertama kali mulai menjalankannya. 280 00:11:55,010 --> 00:11:59,280 Jadi, dalam hal ini, kita lakukan Jalankan dengan kunci tiga. 281 00:11:59,280 --> 00:12:00,770 282 00:12:00,770 --> 00:12:02,040 Dan itu benar-benar akan dimulai. 283 00:12:02,040 --> 00:12:08,480 >> Jadi, jika Anda lihat di sini, kita memiliki Jika RC tidak sama dengan 2. 284 00:12:08,480 --> 00:12:12,210 Jadi, jika kalian semua memiliki bahwa file yang saya dikirim up 285 00:12:12,210 --> 00:12:15,100 Anda akan melihat bahwa itu seperti baris pertama fungsi utama kita, kan? 286 00:12:15,100 --> 00:12:17,890 Ini memeriksa untuk melihat apakah kita memiliki jumlah argumen yang benar. 287 00:12:17,890 --> 00:12:20,620 Jadi, jika Anda bertanya-tanya jika RC benar, 288 00:12:20,620 --> 00:12:23,250 Anda dapat melakukan sesuatu seperti Print RC. 289 00:12:23,250 --> 00:12:24,380 290 00:12:24,380 --> 00:12:28,640 RC adalah dua, yaitu apa yang kita harapkan, kan? 291 00:12:28,640 --> 00:12:32,010 >> Jadi, kita bisa pergi berikutnya, dan terus melalui. 292 00:12:32,010 --> 00:12:33,200 Jadi, kami memiliki beberapa kunci di sana. 293 00:12:33,200 --> 00:12:34,260 294 00:12:34,260 --> 00:12:37,090 Dan kita dapat mencetak kunci kami untuk memastikan itu benar. 295 00:12:37,090 --> 00:12:38,380 296 00:12:38,380 --> 00:12:39,500 Menarik. 297 00:12:39,500 --> 00:12:41,210 Tidak cukup apa yang kami harapkan. 298 00:12:41,210 --> 00:12:44,810 Jadi, satu hal untuk mewujudkan dengan GDB juga, adalah 299 00:12:44,810 --> 00:12:49,000 bahwa itu tidak sampai Anda benar-benar memukul Berikutnya, bahwa garis yang baru saja Anda lihat 300 00:12:49,000 --> 00:12:50,720 benar-benar dijalankan. 301 00:12:50,720 --> 00:12:53,870 Jadi, dalam hal ini Key belum ditetapkan belum. 302 00:12:53,870 --> 00:12:57,050 Jadi, Key adalah beberapa nilai sampah yang Anda lihat di bawah sana. 303 00:12:57,050 --> 00:13:03,680 Negatif $ 120-- --Itu ini satu miliar dan sesuatu hal yang aneh kan? 304 00:13:03,680 --> 00:13:05,340 Ini bukan kunci yang kami harapkan. 305 00:13:05,340 --> 00:13:10,720 Tetapi jika kita memukul Berikutnya, lalu kita mencoba dan tombol Print, itu tiga. 306 00:13:10,720 --> 00:13:11,710 >> Semua orang melihat itu? 307 00:13:11,710 --> 00:13:13,780 Jadi, jika Anda mendapatkan sesuatu bahwa Anda seperti, tunggu. 308 00:13:13,780 --> 00:13:15,540 Ini benar-benar salah, dan saya tidak tahu 309 00:13:15,540 --> 00:13:20,150 bagaimana ini akan terjadi karena semua yang saya inginkan lakukan adalah menetapkan nomor, variabel, 310 00:13:20,150 --> 00:13:22,900 mencoba memukul Selanjutnya, coba pencetakan lagi, dan melihat apakah yang bekerja. 311 00:13:22,900 --> 00:13:27,830 Karena itu hanya akan mengeksekusi dan benar-benar menetapkan sesuatu setelah Anda 312 00:13:27,830 --> 00:13:29,340 tekan Next. 313 00:13:29,340 --> 00:13:30,336 Masuk akal untuk semua orang? 314 00:13:30,336 --> 00:13:30,836 Uh huh? 315 00:13:30,836 --> 00:13:33,220 >> SPEAKER 2: Ketika Anda acak nomor apa artinya? 316 00:13:33,220 --> 00:13:34,790 >> SPEAKER 1: Ini hanya acak. 317 00:13:34,790 --> 00:13:35,710 Ini hanya sampah. 318 00:13:35,710 --> 00:13:38,320 Ini hanya sesuatu yang Anda komputer secara acak akan menetapkan. 319 00:13:38,320 --> 00:13:39,721 320 00:13:39,721 --> 00:13:40,220 Keren. 321 00:13:40,220 --> 00:13:45,760 Jadi, sekarang kita dapat bergerak melalui, dan sebagainya sekarang kita memiliki ini GetString teks biasa. 322 00:13:45,760 --> 00:13:48,600 Jadi, biarkan aku hanya memperkenalkan apa akan terjadi ketika kita memukul Berikutnya sini. 323 00:13:48,600 --> 00:13:51,320 GDB kami jenis menghilang, kan? 324 00:13:51,320 --> 00:13:55,720 Itu karena GetString sekarang mengeksekusi, kan? 325 00:13:55,720 --> 00:14:01,460 Jadi, ketika kita melihat teks biasa sama GetString, parens terbuka dan parens, 326 00:14:01,460 --> 00:14:04,380 dan kita memukul Selanjutnya, yang memiliki sebenarnya dieksekusi sekarang. 327 00:14:04,380 --> 00:14:06,580 Jadi, itu menunggu kita masukan sesuatu. 328 00:14:06,580 --> 00:14:13,560 >> Jadi, kita akan masukan makanan kami yang adalah apa itu gagal seperti yang saya katakan 329 00:14:13,560 --> 00:14:18,020 dan bahwa hanya mengatakan bahwa itu selesai mengeksekusi, yang ditutup 330 00:14:18,020 --> 00:14:19,980 braket berarti itu keluar dari lingkaran itu. 331 00:14:19,980 --> 00:14:21,170 332 00:14:21,170 --> 00:14:25,420 Jadi, kita bisa tekan Next, dan sekarang, karena saya yakin kita semua sudah familiar dari Caesar, 333 00:14:25,420 --> 00:14:27,260 ini, apa baris ini akan dilakukan. 334 00:14:27,260 --> 00:14:32,030 Ini untuk Int I sama dengan 0, N sama Strlen, teks biasa, dan kemudian 335 00:14:32,030 --> 00:14:33,960 Saya kurang dari n, I, ditambah, plus. 336 00:14:33,960 --> 00:14:35,210 Apa lingkaran ini akan dilakukan? 337 00:14:35,210 --> 00:14:37,900 338 00:14:37,900 --> 00:14:39,160 Buka pesan Anda. 339 00:14:39,160 --> 00:14:39,770 Keren. 340 00:14:39,770 --> 00:14:41,330 Jadi, mari kita mulai melakukan hal itu. 341 00:14:41,330 --> 00:14:47,210 >> Jadi, harus kondisi ini cocok, untuk pertama kita? 342 00:14:47,210 --> 00:14:52,250 Jika itu adalah B, itu teks biasa I. Kami dapat memperoleh informasi tentang penduduk setempat kami. 343 00:14:52,250 --> 00:14:53,610 344 00:14:53,610 --> 00:14:57,970 Jadi, saya adalah nol, dan jika enam, yang kami berharap, dan kunci kami adalah tiga. 345 00:14:57,970 --> 00:14:59,227 Semua yang masuk akal, kan? 346 00:14:59,227 --> 00:15:01,310 Angka-angka itu semua persis apa yang mereka seharusnya. 347 00:15:01,310 --> 00:15:02,590 348 00:15:02,590 --> 00:15:03,870 Jadi, bersenandung? 349 00:15:03,870 --> 00:15:05,620 SPEAKER 3: Saya memiliki nomor acak untuk tambang. 350 00:15:05,620 --> 00:15:09,156 351 00:15:09,156 --> 00:15:12,030 SPEAKER 1: Yah, kita bisa check-- --Kami dapat chatting tentang bahwa dalam satu detik. 352 00:15:12,030 --> 00:15:14,110 353 00:15:14,110 --> 00:15:15,750 Tapi Anda harus mendapatkan ini. 354 00:15:15,750 --> 00:15:17,700 355 00:15:17,700 --> 00:15:20,130 Jadi, jika kita memiliki modal B untuk pertama kami, 356 00:15:20,130 --> 00:15:22,080 Kondisi ini harus menangkapnya, kan? 357 00:15:22,080 --> 00:15:27,120 Jadi, jika kita memukul Selanjutnya, kita lihat bahwa Jika ini benar-benar dijalankan. 358 00:15:27,120 --> 00:15:29,220 Karena jika Anda mengikuti bersama dalam kode Anda, 359 00:15:29,220 --> 00:15:33,460 baris ini di sini, di mana teks biasa saya diganti dengan aritmatika ini, 360 00:15:33,460 --> 00:15:35,720 hanya mengeksekusi jika Jika Kondisi yang tepat yang benar? 361 00:15:35,720 --> 00:15:36,905 362 00:15:36,905 --> 00:15:40,240 >> GDB hanya akan menampilkan hal-hal yang benar-benar melaksanakan. 363 00:15:40,240 --> 00:15:45,140 Jadi jika kondisi Jika ini tidak terpenuhi, itu hanya akan melompat ke baris berikutnya. 364 00:15:45,140 --> 00:15:46,540 OK? 365 00:15:46,540 --> 00:15:48,510 Jadi, kita mendapati bahwa. 366 00:15:48,510 --> 00:15:51,171 Braket ini berarti itu ditutup keluar dari lingkaran itu sekarang. 367 00:15:51,171 --> 00:15:52,420 Jadi, itu akan mulai lagi. 368 00:15:52,420 --> 00:15:54,760 369 00:15:54,760 --> 00:15:56,280 Hanya seperti itu. 370 00:15:56,280 --> 00:15:59,120 Jadi, kita bisa mendapatkan info tentang penduduk setempat kami di sini, 371 00:15:59,120 --> 00:16:02,575 dan kita melihat bahwa pertama kami surat telah berubah, kan? 372 00:16:02,575 --> 00:16:05,150 Sekarang E, sebagaimana mestinya. 373 00:16:05,150 --> 00:16:07,360 Jadi, kita dapat melanjutkan. 374 00:16:07,360 --> 00:16:08,500 >> Dan kami memiliki cek ini. 375 00:16:08,500 --> 00:16:09,916 Dan cek ini harus bekerja, kan? 376 00:16:09,916 --> 00:16:12,570 Ini A. Ini harus diubah tiga huruf depan. 377 00:16:12,570 --> 00:16:14,320 378 00:16:14,320 --> 00:16:16,530 Tetapi jika Anda melihat, kita mendapatkan sesuatu yang berbeda. 379 00:16:16,530 --> 00:16:17,580 380 00:16:17,580 --> 00:16:22,860 Jadi dalam hal ini di sini, itu tertangkap itu, dan baris ini dieksekusi, 381 00:16:22,860 --> 00:16:28,620 yang dimodifikasi kami B. Tapi, dalam hal ini di sini, 382 00:16:28,620 --> 00:16:32,860 kita mendapati bahwa itu hanya melewatkan itu, dan pergi ke [itu? L SIFF. ?] 383 00:16:32,860 --> 00:16:34,660 Jadi sesuatu yang terjadi di sana. 384 00:16:34,660 --> 00:16:37,780 Apa yang memberitahu Anda adalah bahwa, kita tahu bahwa itu harus menangkap sini, 385 00:16:37,780 --> 00:16:39,200 tapi tidak. 386 00:16:39,200 --> 00:16:42,210 Dapatkah orang melihat apa yang kami Masalah ini sejalan itu? 387 00:16:42,210 --> 00:16:45,380 388 00:16:45,380 --> 00:16:46,969 Ini adalah hal yang sangat menit. 389 00:16:46,969 --> 00:16:48,510 Dan Anda juga bisa melihat kode Anda. 390 00:16:48,510 --> 00:16:49,980 391 00:16:49,980 --> 00:16:54,940 Ini juga line-- melupakan apa garis itu di besar-- tapi itu di [tidak terdengar]. 392 00:16:54,940 --> 00:16:55,480 Ya? 393 00:16:55,480 --> 00:16:58,639 >> SPEAKER 4: Ini pada lebih besar dari Halaman jika Anda membacanya di buku. 394 00:16:58,639 --> 00:16:59,430 SPEAKER 1: Tepat. 395 00:16:59,430 --> 00:17:02,620 Jadi, debugger tidak tahu Anda itu, tapi debugger 396 00:17:02,620 --> 00:17:05,880 bisa membuat Anda turun ke saluran Anda tahu tidak berfungsi. 397 00:17:05,880 --> 00:17:09,319 Dan kadang-kadang, ketika terutama kemudian di semester, ketika 398 00:17:09,319 --> 00:17:12,910 Anda sedang berhadapan dengan seratus, ratus beberapa baris kode, dan Anda 399 00:17:12,910 --> 00:17:16,190 tidak tahu di mana itu gagal, ini adalah cara yang bagus untuk melakukannya. 400 00:17:16,190 --> 00:17:17,900 401 00:17:17,900 --> 00:17:18,989 Jadi, kami menemukan bug kami. 402 00:17:18,989 --> 00:17:21,530 Anda dapat memperbaikinya dalam file Anda, dan kemudian Anda bisa menjalankannya lagi, 403 00:17:21,530 --> 00:17:23,029 dan semuanya akan bekerja dengan sempurna. 404 00:17:23,029 --> 00:17:24,970 405 00:17:24,970 --> 00:17:30,590 Dan yang terbesar adalah ini dapat tampak seperti, OK. 406 00:17:30,590 --> 00:17:31,090 Ya. 407 00:17:31,090 --> 00:17:31,370 Keren. 408 00:17:31,370 --> 00:17:32,744 Kau tahu apa yang Anda cari. 409 00:17:32,744 --> 00:17:34,910 Jadi, Anda tahu apa yang harus dilakukan. 410 00:17:34,910 --> 00:17:39,021 >> GDB dapat super membantu karena Anda dapat mencetak semua hal yang Anda 411 00:17:39,021 --> 00:17:39,520 tidak. 412 00:17:39,520 --> 00:17:41,160 Ini jauh lebih berguna daripada printf. 413 00:17:41,160 --> 00:17:43,440 Berapa banyak dari Anda menggunakan seperti pernyataan printf 414 00:17:43,440 --> 00:17:46,200 untuk mencari tahu di mana bug itu, kan? 415 00:17:46,200 --> 00:17:48,450 Jadi, dengan ini, Anda tidak harus terus kembali, 416 00:17:48,450 --> 00:17:51,139 dan seperti komentar di Printf, atau komentar dari, 417 00:17:51,139 --> 00:17:52,930 dan mencari tahu apa Anda harus mencetak. 418 00:17:52,930 --> 00:17:55,670 Ini benar-benar hanya memungkinkan Anda untuk langkah melalui, mencetak hal-hal 419 00:17:55,670 --> 00:18:00,000 karena Anda akan melalui, jadi, Anda dapat mengamati bagaimana mereka berubah secara real time, 420 00:18:00,000 --> 00:18:02,190 sebagai program anda berjalan. 421 00:18:02,190 --> 00:18:04,390 >> Dan itu tidak mengambil sedikit sedikit membiasakan diri. 422 00:18:04,390 --> 00:18:07,850 Saya akan sangat menyarankan hanya jenis menjadi sedikit frustrasi dengan itu 423 00:18:07,850 --> 00:18:08,930 untuk sekarang. 424 00:18:08,930 --> 00:18:13,450 Jika Anda menghabiskan satu jam di atas minggu depan belajar bagaimana menggunakan GDB, 425 00:18:13,450 --> 00:18:16,140 Anda akan menghemat begitu banyak waktu di kemudian hari. 426 00:18:16,140 --> 00:18:18,750 Dan secara harfiah. kita memberitahu ini untuk orang setiap tahun, 427 00:18:18,750 --> 00:18:23,890 dan saya ingat ketika saya mengambil kelas, aku seperti, aku akan baik-baik saja. 428 00:18:23,890 --> 00:18:24,700 Nomor 429 00:18:24,700 --> 00:18:27,030 Pset 6 datang dan aku seperti, aku akan belajar 430 00:18:27,030 --> 00:18:29,500 bagaimana menggunakan GDB karena saya tidak melakukan tahu apa yang terjadi di sini. 431 00:18:29,500 --> 00:18:32,940 >> Jadi jika Anda meluangkan waktu sehingga menggunakannya pada program yang lebih kecil 432 00:18:32,940 --> 00:18:35,697 bahwa Anda akan menjadi bekerja, seperti bekerja 433 00:18:35,697 --> 00:18:37,530 melalui sesuatu seperti Visionare, seperti ini. 434 00:18:37,530 --> 00:18:38,800 435 00:18:38,800 --> 00:18:42,850 Atau jika Anda ingin latihan ekstra, saya yakin Aku bisa datang dengan program buggy, 436 00:18:42,850 --> 00:18:45,300 bagi Anda untuk men-debug jika Anda ingin. 437 00:18:45,300 --> 00:18:49,300 >> Tetapi jika Anda hanya mengambil beberapa waktu untuk mendapatkan digunakan untuk itu, hanya bermain-main dengan hal itu, 438 00:18:49,300 --> 00:18:50,550 itu benar-benar akan melayani Anda dengan baik. 439 00:18:50,550 --> 00:18:52,591 Dan itu benar-benar salah satu dari hal-hal yang baru saja Anda 440 00:18:52,591 --> 00:18:57,340 harus mencoba, dan mendapatkan tangan Anda kotor dengan, sebelum Anda benar-benar memahaminya. 441 00:18:57,340 --> 00:19:02,090 Aku benar-benar hanya mengerti sekali Aku harus men-debug hal dengan itu, 442 00:19:02,090 --> 00:19:08,170 dan itu jauh lebih baik untuk memiliki gagasan tentang bagaimana debug lebih awal daripada kemudian. 443 00:19:08,170 --> 00:19:08,850 OK. 444 00:19:08,850 --> 00:19:09,625 Keren. 445 00:19:09,625 --> 00:19:12,960 Aku tahu itu jenis seperti kursus kilat di GDB, 446 00:19:12,960 --> 00:19:16,400 dan saya pasti akan bekerja untuk mendapatkan ini untuk terlihat lebih besar waktu berikutnya. 447 00:19:16,400 --> 00:19:17,590 448 00:19:17,590 --> 00:19:18,280 Keren. 449 00:19:18,280 --> 00:19:20,390 >> Jadi, jika kita kembali ke PowerPoint kami. 450 00:19:20,390 --> 00:19:27,194 451 00:19:27,194 --> 00:19:28,110 Apakah ini akan berhasil? 452 00:19:28,110 --> 00:19:29,711 453 00:19:29,711 --> 00:19:30,210 Awh. 454 00:19:30,210 --> 00:19:31,101 Ya. 455 00:19:31,101 --> 00:19:31,600 OK. 456 00:19:31,600 --> 00:19:35,480 Jadi, jika Anda pernah membutuhkan semua mereka lagi, ada daftar. 457 00:19:35,480 --> 00:19:37,160 458 00:19:37,160 --> 00:19:40,830 Cari begitu Binary, yang semua orang ingat tontonan besar David 459 00:19:40,830 --> 00:19:42,259 merobek buku telepon di setengah. 460 00:19:42,259 --> 00:19:44,050 Saya tidak benar-benar mendapatkan buku telepon lagi, 461 00:19:44,050 --> 00:19:46,530 karena seperti di mana Anda mendapatkan buku-buku telepon hari ini? 462 00:19:46,530 --> 00:19:48,220 Aku benar-benar tidak tahu. 463 00:19:48,220 --> 00:19:49,840 464 00:19:49,840 --> 00:19:50,590 The Binary Search. 465 00:19:50,590 --> 00:19:52,464 Apakah ada yang ingat bagaimana Binary Search bekerja? 466 00:19:52,464 --> 00:19:54,380 467 00:19:54,380 --> 00:19:55,220 Siapapun sama sekali? 468 00:19:55,220 --> 00:19:56,325 Ya? 469 00:19:56,325 --> 00:19:58,283 SPEAKER 5: Anda tahu kapan Anda melihat di mana setengah 470 00:19:58,283 --> 00:20:01,146 itu akan di, Berdasarkan itu, dan menyingkirkan setengah lainnya. 471 00:20:01,146 --> 00:20:01,896 >> SPEAKER 1 Persis. 472 00:20:01,896 --> 00:20:06,290 Jadi, Binary Search, itu jenis a-- --Kami suka menyebutnya membagi dan menaklukkan. 473 00:20:06,290 --> 00:20:09,170 Jadi, apa yang akan Anda lakukan adalah Anda akan melihat di tengah, 474 00:20:09,170 --> 00:20:11,990 dan Anda akan melihat apakah itu cocok apa yang Anda cari. 475 00:20:11,990 --> 00:20:15,420 Dan jika tidak, maka Anda mencoba untuk mencari tahu, apakah akan dibiarkan 476 00:20:15,420 --> 00:20:16,450 setengah atau setengah benar. 477 00:20:16,450 --> 00:20:19,325 Jadi, mungkin ini jika Anda sedang mencari sesuatu yang menurut abjad, 478 00:20:19,325 --> 00:20:20,720 Anda lihat, oh. 479 00:20:20,720 --> 00:20:22,750 Apakah Allison datang sebelum M? 480 00:20:22,750 --> 00:20:23,250 Ya. 481 00:20:23,250 --> 00:20:25,030 Jadi, kita akan melihat babak pertama. 482 00:20:25,030 --> 00:20:26,450 >> Atau bisa juga seperti dengan angka. 483 00:20:26,450 --> 00:20:28,830 Apa pun yang Anda bisa bandingkan, dapat diurutkan. 484 00:20:28,830 --> 00:20:29,920 485 00:20:29,920 --> 00:20:31,260 Anda dapat menggunakan pencarian biner pada. 486 00:20:31,260 --> 00:20:32,340 487 00:20:32,340 --> 00:20:37,455 Jadi, ada yang ingat ini grafik atau apa ini? 488 00:20:37,455 --> 00:20:39,520 Ini Kompleksitas Asymptotic. 489 00:20:39,520 --> 00:20:42,830 Jadi, grafik ini hanya menjelaskan berapa lama 490 00:20:42,830 --> 00:20:46,230 membawa Anda untuk memecahkan masalah karena Anda meningkatkan jumlah hal-hal 491 00:20:46,230 --> 00:20:47,090 yang Anda gunakan. 492 00:20:47,090 --> 00:20:51,260 >> Jadi, kita memiliki N, yang merupakan waktu linier. 493 00:20:51,260 --> 00:20:54,560 Jika N lebih dari dua, yang sedikit lebih baik, masih tumbuh super cepat. 494 00:20:54,560 --> 00:20:58,360 Dan kemudian kami telah Login, yang apa yang kita anggap Binary Search. 495 00:20:58,360 --> 00:21:03,630 Jika kita perhatikan, sebagai masalah Anda mendapat banyak dan jauh lebih besar, 496 00:21:03,630 --> 00:21:06,600 waktu yang dibutuhkan Anda untuk memecahkannya tidak benar-benar meningkat banyak. 497 00:21:06,600 --> 00:21:09,010 Ini seperti sebanding di sini di awal. 498 00:21:09,010 --> 00:21:10,060 Kau seperti, OK. 499 00:21:10,060 --> 00:21:13,000 Apa pun di sini tidak benar-benar penting yang mana yang kita gunakan, 500 00:21:13,000 --> 00:21:16,220 tapi Anda keluar untuk satu juta, satu miliar. 501 00:21:16,220 --> 00:21:20,010 Anda mencoba untuk menemukan --you're some-- berusaha mencari jarum di tumpukan jerami. 502 00:21:20,010 --> 00:21:21,550 >> Saya pikir Anda ingin masalah ini. 503 00:21:21,550 --> 00:21:25,850 Anda ingin kompleksitas ini, tidak linier karena untuk semua Anda 504 00:21:25,850 --> 00:21:30,049 tahu akan Anda dapat mencari melalui setiap jarum individu, hal jerami, 505 00:21:30,049 --> 00:21:31,340 mencoba untuk mencari jarum Anda. 506 00:21:31,340 --> 00:21:34,730 Dan itu tidak terlalu menyenangkan menurut pendapat saya. 507 00:21:34,730 --> 00:21:35,500 Saya suka cepat. 508 00:21:35,500 --> 00:21:36,620 Saya suka efisien. 509 00:21:36,620 --> 00:21:40,450 Dan siswa sebagai pekerja keras Anda orang ini, Anda tahu bekerja lebih cerdas, 510 00:21:40,450 --> 00:21:43,010 bukan lebih keras jenis hal, bagaimana Anda dapat membuat algoritma ini. 511 00:21:43,010 --> 00:21:45,110 512 00:21:45,110 --> 00:21:47,910 >> Jadi, kita akan berjalan melalui hanya contoh cepat. 513 00:21:47,910 --> 00:21:51,090 Saya pikir kalian harus memiliki tangan pada Binary Search, 514 00:21:51,090 --> 00:21:54,352 tetapi dalam kasus ada yang sedikit fuzzy, ingin memperkuat itu, 515 00:21:54,352 --> 00:21:56,310 kita akan hanya pergi melalui contoh di sini. 516 00:21:56,310 --> 00:21:59,490 Jadi, kita cari jika array berisi tujuh. 517 00:21:59,490 --> 00:22:00,540 518 00:22:00,540 --> 00:22:06,010 >> Jadi, hal pertama yang kita lakukan adalah terlihat di tengah, kan? 519 00:22:06,010 --> 00:22:09,340 Dan juga Anda akan coding Pencarian biner hanya dalam hitungan detik. 520 00:22:09,340 --> 00:22:11,310 Jadi, itu akan menyenangkan. 521 00:22:11,310 --> 00:22:13,710 Jadi kita melihat di tengah array kecil 3. 522 00:22:13,710 --> 00:22:15,501 Apakah 3 sama 7? 523 00:22:15,501 --> 00:22:16,000 Tidak. 524 00:22:16,000 --> 00:22:18,670 525 00:22:18,670 --> 00:22:19,550 Ini enam. 526 00:22:19,550 --> 00:22:21,480 Jadi, apakah itu kurang dari atau lebih besar dari tujuh? 527 00:22:21,480 --> 00:22:23,080 528 00:22:23,080 --> 00:22:23,960 Kurang dari. 529 00:22:23,960 --> 00:22:24,570 Ya. 530 00:22:24,570 --> 00:22:25,170 Bagus job guys. 531 00:22:25,170 --> 00:22:25,569 532 00:22:25,569 --> 00:22:27,360 Aku merasa aku seperti aku harus memiliki permen karena saya 533 00:22:27,360 --> 00:22:29,460 ingin membuangnya keluar ke meter. 534 00:22:29,460 --> 00:22:30,270 Itu yang akan saya lakukan minggu depan. 535 00:22:30,270 --> 00:22:31,436 Ini akan membuat kalian tajam. 536 00:22:31,436 --> 00:22:32,560 537 00:22:32,560 --> 00:22:34,690 >> Jadi, kita buang jauh-jauh babak pertama, kan? 538 00:22:34,690 --> 00:22:35,670 itu kurang dari. 539 00:22:35,670 --> 00:22:39,325 kita tahu bahwa segala sesuatu di sisi kiri 540 00:22:39,325 --> 00:22:41,700 akan menjadi kurang dari apa kita benar-benar mencari. 541 00:22:41,700 --> 00:22:43,491 Jadi, tidak perlu untuk memperhatikan itu. 542 00:22:43,491 --> 00:22:45,120 Lupakan saja. 543 00:22:45,120 --> 00:22:48,720 Jadi, sekarang kita melihat sisi kanan kami, dan kami melihat tengah sana, 544 00:22:48,720 --> 00:22:50,510 dan sekarang sembilan. 545 00:22:50,510 --> 00:22:55,510 Jadi, 9 is-- --Everyone? 546 00:22:55,510 --> 00:22:57,470 Lebih besar dari apa yang kita cari, kan? 547 00:22:57,470 --> 00:22:59,860 Jadi, kita akan melemparkan segala sesuatu ke kanan. 548 00:22:59,860 --> 00:23:00,970 549 00:23:00,970 --> 00:23:01,940 Seperti itu. 550 00:23:01,940 --> 00:23:03,700 Sekarang, semua kami pergi dengan adalah satu. 551 00:23:03,700 --> 00:23:07,760 Jadi kita periksa, satu ini apa kita cari? itu. 552 00:23:07,760 --> 00:23:08,970 Kami menemukan apa yang kita inginkan. 553 00:23:08,970 --> 00:23:10,440 554 00:23:10,440 --> 00:23:11,690 Jadi kita sudah selesai. 555 00:23:11,690 --> 00:23:12,550 Bilinear Search. 556 00:23:12,550 --> 00:23:15,740 >> Dan jika Anda perhatikan, kita memiliki tujuh input ada. 557 00:23:15,740 --> 00:23:24,320 Hanya kami butuh seperti tiga kali, tetapi jika Anda melakukan seperti miliar, 558 00:23:24,320 --> 00:23:28,190 kalian tahu berapa banyak langkah itu akan mengambil jika kita memiliki empat miliar hal? 559 00:23:28,190 --> 00:23:29,940 560 00:23:29,940 --> 00:23:30,455 Setiap tebakan? 561 00:23:30,455 --> 00:23:32,286 562 00:23:32,286 --> 00:23:33,960 Ini 32. 563 00:23:33,960 --> 00:23:37,110 32 langkah untuk menemukan sesuatu dalam empat miliar 564 00:23:37,110 --> 00:23:39,650 elemen array karena kekuasaan dua. 565 00:23:39,650 --> 00:23:43,550 Jadi dua adalah 32, adalah empat miliar. 566 00:23:43,550 --> 00:23:50,430 >> Bagaimana begitu cukup gila kau masih dalam seperti jumlah yang cukup kecil dari langkah-langkah 567 00:23:50,430 --> 00:23:52,650 untuk menemukan sesuatu di empat miliar elemen. 568 00:23:52,650 --> 00:23:55,730 Jadi pada catatan, kami tidak akan kode ini 569 00:23:55,730 --> 00:23:58,950 sehingga kalian benar-benar bisa jenis melihat bagaimana ini bekerja. 570 00:23:58,950 --> 00:24:01,520 Baiklah, jadi kalian dapat kode. 571 00:24:01,520 --> 00:24:04,100 Aku akan membiarkan kalian berbicara untuk sedikit. 572 00:24:04,100 --> 00:24:07,970 Kenali orang di sekitar Anda, yang apa yang orang inginkan dari bagian terakhir. 573 00:24:07,970 --> 00:24:10,280 >> Jadi mengenal orang-orang di sekitar Anda. 574 00:24:10,280 --> 00:24:11,305 Bicara untuk sedikit. 575 00:24:11,305 --> 00:24:12,580 576 00:24:12,580 --> 00:24:15,730 Dan semua yang saya inginkan dari Anda orang sekarang hanya 577 00:24:15,730 --> 00:24:17,575 mencoba untuk membuat garis besar pseudocode. 578 00:24:17,575 --> 00:24:18,075 OK? 579 00:24:18,075 --> 00:24:20,825 580 00:24:20,825 --> 00:24:21,325 Whoa. 581 00:24:21,325 --> 00:24:23,320 582 00:24:23,320 --> 00:24:29,520 Semua yang saya inginkan dari kalian adalah Anda hanya akan mengisi dalam kasus ini sementara. 583 00:24:29,520 --> 00:24:32,170 Jadi saya telah menetapkan ini atas dan batas bawah yang 584 00:24:32,170 --> 00:24:35,250 mewakili awal dan akhir array kita. 585 00:24:35,250 --> 00:24:40,440 Dan Anda akan benar-benar loop melalui dan mencari tahu 586 00:24:40,440 --> 00:24:42,470 apa yang kita lakukan dalam while loop ini. 587 00:24:42,470 --> 00:24:45,810 >> Jadi jika Anda dapat mengetahui out-- Saya memiliki petunjuk besar-- apa kasus 588 00:24:45,810 --> 00:24:46,640 yang kita miliki di sini? 589 00:24:46,640 --> 00:24:48,100 590 00:24:48,100 --> 00:24:51,560 Jadi jika Anda ingin mengetahui kasus, kita akan pseudo mereka 591 00:24:51,560 --> 00:24:53,350 dan kemudian kita benar-benar akan kode mereka. 592 00:24:53,350 --> 00:24:55,330 Dan itu akan menjadi, saya berpikir, mudah-mudahan itu akan 593 00:24:55,330 --> 00:24:56,788 menjadi sedikit lebih mudah dari yang Anda harapkan. 594 00:24:56,788 --> 00:24:57,554 595 00:24:57,554 --> 00:25:00,220 Karena itu bukan kode banyak, sebenarnya, yang benar-benar keren. 596 00:25:00,220 --> 00:25:34,110 597 00:25:34,110 --> 00:25:35,018 >> Mm-hm? 598 00:25:35,018 --> 00:25:35,893 >> SISWA: [tak terdengar]? 599 00:25:35,893 --> 00:25:36,984 600 00:25:36,984 --> 00:25:37,650 INSTRUKTUR: Ya. 601 00:25:37,650 --> 00:25:38,595 Ada sesuatu untuk menemukan di tengah. 602 00:25:38,595 --> 00:25:39,552 >> SISWA: Jadi kita bisa menggunakan itu. 603 00:25:39,552 --> 00:25:39,770 OK. 604 00:25:39,770 --> 00:25:40,603 >> INSTRUKTUR: Perfect. 605 00:25:40,603 --> 00:25:42,950 Jadi itulah hal pertama yang perlu kita lakukan. 606 00:25:42,950 --> 00:25:44,330 Jadi menemukan tengah. 607 00:25:44,330 --> 00:25:45,415 608 00:25:45,415 --> 00:25:45,915 Besar. 609 00:25:45,915 --> 00:25:47,770 610 00:25:47,770 --> 00:25:55,010 Jadi Anda memiliki gagasan tentang bagaimana kita mungkin benar-benar menemukan tengah dengan kode? 611 00:25:55,010 --> 00:25:55,980 >> SISWA: Ya. 612 00:25:55,980 --> 00:25:57,000 n lebih dari 2? 613 00:25:57,000 --> 00:25:58,500 614 00:25:58,500 --> 00:25:59,500 INSTRUKTUR: Jadi n lebih dari 2. 615 00:25:59,500 --> 00:26:05,170 Jadi, satu hal yang perlu diingat adalah bahwa batas atas dan bawah Anda. 616 00:26:05,170 --> 00:26:08,110 Kami terus konstriksi bagian dari array yang kita cari untuk. 617 00:26:08,110 --> 00:26:11,970 Jadi n lebih dari 2 hanya akan bekerja untuk hal pertama yang kita lakukan. 618 00:26:11,970 --> 00:26:17,810 Jadi mengambil atas dan bawah ke rekening, bagaimana kita bisa mendapatkan elemen tengah? 619 00:26:17,810 --> 00:26:20,640 Karena kami ingin tengah antara atas dan bawah, kanan? 620 00:26:20,640 --> 00:26:21,730 621 00:26:21,730 --> 00:26:22,494 Mm-hm? 622 00:26:22,494 --> 00:26:23,369 >> SISWA: [tak terdengar]. 623 00:26:23,369 --> 00:26:26,170 624 00:26:26,170 --> 00:26:28,080 >> INSTRUKTUR: Jadi kita memiliki beberapa tengah. 625 00:26:28,080 --> 00:26:32,730 Dan itu akan menjadi bagian atas ditambah lebih rendah lebih dari 2. 626 00:26:32,730 --> 00:26:34,740 627 00:26:34,740 --> 00:26:35,690 Mengagumkan. 628 00:26:35,690 --> 00:26:36,570 Di sana kami pergi. 629 00:26:36,570 --> 00:26:37,280 Satu ke bawah garis. 630 00:26:37,280 --> 00:26:38,560 Kalian berada di jalan. 631 00:26:38,560 --> 00:26:41,400 Jadi sekarang kita memiliki kita tengah, apa yang kita ingin lakukan? 632 00:26:41,400 --> 00:26:45,050 633 00:26:45,050 --> 00:26:45,900 Hanya secara umum. 634 00:26:45,900 --> 00:26:47,734 Anda tidak harus kode itu. 635 00:26:47,734 --> 00:26:48,335 Ya. 636 00:26:48,335 --> 00:26:49,210 SISWA: [tak terdengar]? 637 00:26:49,210 --> 00:27:00,310 638 00:27:00,310 --> 00:27:10,310 INSTRUKTUR: Jadi ditambah karena Anda menemukan rata-rata antara dua 639 00:27:10,310 --> 00:27:10,810 dari mereka. 640 00:27:10,810 --> 00:27:11,890 641 00:27:11,890 --> 00:27:17,370 Jadi jika Anda menganggap mereka sebagai jenis peningkatan di dari sisi, 642 00:27:17,370 --> 00:27:21,640 berpikir tentang hal ini saat Anda mendekati tengah, Anda ingin seperti itu. 643 00:27:21,640 --> 00:27:27,150 Jadi jika Anda berada di kedua sisi tengah, dan kami punya seperti 5 dan 7. 644 00:27:27,150 --> 00:27:31,440 Ketika Anda menambahkan mereka bersama-sama Anda mendapatkan 12, Anda membagi dengan 2, adalah 6. 645 00:27:31,440 --> 00:27:33,726 >> Kadang-kadang sulit untuk menjelaskan mengapa yang bekerja, 646 00:27:33,726 --> 00:27:35,600 tetapi jika Anda bekerja melalui contoh kadang-kadang, 647 00:27:35,600 --> 00:27:37,962 itu akan membantu Anda mengetahui apakah itu harus plus atau minus. 648 00:27:37,962 --> 00:27:38,846 Ya. 649 00:27:38,846 --> 00:27:40,830 >> SISWA: [tidak terdengar] persis di tengah 650 00:27:40,830 --> 00:27:43,950 jika mereka memiliki kasus di mana ada banyak nomor yang lebih kecil 651 00:27:43,950 --> 00:27:45,860 dan seperti sejumlah besar? 652 00:27:45,860 --> 00:27:49,750 >> INSTRUKTUR: Jadi semua yang Anda butuhkan adalah tengah array. 653 00:27:49,750 --> 00:27:53,010 Jadi jika Anda memiliki sekelompok angka kecil dan kemudian satu nomor yang benar-benar besar 654 00:27:53,010 --> 00:27:54,799 pada akhirnya, itu tidak masalah. 655 00:27:54,799 --> 00:27:56,840 Yang penting adalah bahwa mereka diurutkan, Anda hanya 656 00:27:56,840 --> 00:27:59,339 ingin melihat tengah array karena Anda masih 657 00:27:59,339 --> 00:28:00,700 mengiris masalah Anda di setengah. 658 00:28:00,700 --> 00:28:03,020 659 00:28:03,020 --> 00:28:03,680 Keren. 660 00:28:03,680 --> 00:28:06,430 Jadi sekarang kita memiliki tengah, apa yang kita lakukan selanjutnya? 661 00:28:06,430 --> 00:28:07,150 >> SISWA: Bandingkan. 662 00:28:07,150 --> 00:28:08,150 INSTRUKTUR: The bandingkan. 663 00:28:08,150 --> 00:28:11,670 Jadi bandingkan menengah ke value_wanted. 664 00:28:11,670 --> 00:28:14,300 665 00:28:14,300 --> 00:28:15,160 Keren. 666 00:28:15,160 --> 00:28:17,950 Jadi Anda lihat di sini kita memiliki nilai ini kami ingin di sini. 667 00:28:17,950 --> 00:28:22,012 668 00:28:22,012 --> 00:28:23,095 Ingat ini adalah array. 669 00:28:23,095 --> 00:28:24,100 670 00:28:24,100 --> 00:28:26,970 Jadi menengah mengacu pada indeks. 671 00:28:26,970 --> 00:28:29,785 Jadi kami ingin melakukan nilai-nilai menengah. 672 00:28:29,785 --> 00:28:32,380 673 00:28:32,380 --> 00:28:35,650 Jangan lupa jika Anda ingin untuk membandingkan, ganda sederajat. 674 00:28:35,650 --> 00:28:38,250 Anda melakukan satu sama kau hanya akan menetapkan kembali, 675 00:28:38,250 --> 00:28:41,090 dan kemudian, tentu saja, itu akan menjadi nilai yang Anda inginkan. 676 00:28:41,090 --> 00:28:42,300 Jadi jangan lakukan itu. 677 00:28:42,300 --> 00:28:44,350 >> Jadi kita akan melihat apakah nilai-nilai di tengah 678 00:28:44,350 --> 00:28:46,460 adalah sama dengan nilai yang kita inginkan. 679 00:28:46,460 --> 00:28:47,749 680 00:28:47,749 --> 00:28:48,790 Jangan lupa kawat gigi Anda. 681 00:28:48,790 --> 00:28:50,520 682 00:28:50,520 --> 00:28:52,235 Dropbox harus pergi. 683 00:28:52,235 --> 00:28:54,140 684 00:28:54,140 --> 00:28:56,200 Jadi apa yang kita lakukan dalam kasus ini? 685 00:28:56,200 --> 00:28:59,360 Jika itu apa yang kita ingin kembali? 686 00:28:59,360 --> 00:29:01,510 687 00:29:01,510 --> 00:29:02,626 Kami mencoba untuk mengatakan. 688 00:29:02,626 --> 00:29:03,440 >> SISWA: Cetak off. 689 00:29:03,440 --> 00:29:05,314 >> INSTRUKTUR: Yah, kita tidak ingin mencetak. 690 00:29:05,314 --> 00:29:08,220 Jadi ini adalah bool sini, jadi kami ingin kembali benar atau salah. 691 00:29:08,220 --> 00:29:12,280 Kami katakan, adalah nomor ini sebuah [? RRA? ?] Jadi jika, 692 00:29:12,280 --> 00:29:13,788 kita hanya mengembalikannya benar. 693 00:29:13,788 --> 00:29:16,780 694 00:29:16,780 --> 00:29:17,760 Jika saya bisa mengeja benar. 695 00:29:17,760 --> 00:29:18,830 696 00:29:18,830 --> 00:29:20,805 >> SISWA: Mengapa Anda tidak akan kembali nol? 697 00:29:20,805 --> 00:29:22,930 INSTRUKTUR: Jadi Anda bisa kembali nol jika Anda inginkan. 698 00:29:22,930 --> 00:29:26,780 Tapi dalam kasus ini karena fungsi kita mengembalikan bool, 699 00:29:26,780 --> 00:29:28,962 kita perlu kembali bisa benar atau salah. 700 00:29:28,962 --> 00:29:30,920 SISWA: Saat Anda mengatakan ekspresi boolean, 701 00:29:30,920 --> 00:29:33,450 dapat Anda mengaturnya sama dengan palsu? 702 00:29:33,450 --> 00:29:39,860 Seperti jika saya ingin mengatakan, jika kondisi ini tidak terpenuhi, seperti tersebut diatas sama palsu. 703 00:29:39,860 --> 00:29:42,332 Apakah akan mengerti jika Anda hanya menempatkan palsu di sisi lain? 704 00:29:42,332 --> 00:29:43,040 INSTRUKTUR: Ya. 705 00:29:43,040 --> 00:29:44,820 Jadi sebenarnya jika Anda pernah melakukan sesuatu 706 00:29:44,820 --> 00:29:49,600 seperti adalah atas atau lebih rendah, yang mengembalikan benar atau salah 707 00:29:49,600 --> 00:29:53,850 dan itu adalah gaya benar-benar buruk untuk katakanlah sama sama benar atau sederajat 708 00:29:53,850 --> 00:29:54,840 sama palsu. 709 00:29:54,840 --> 00:30:00,210 Anda ingin menggunakan hasil tersebut sebagai dirinya sebagai cek Anda. 710 00:30:00,210 --> 00:30:04,720 711 00:30:04,720 --> 00:30:05,860 Tidak apa yang saya inginkan. 712 00:30:05,860 --> 00:30:08,150 713 00:30:08,150 --> 00:30:09,240 Itulah apa yang saya inginkan. 714 00:30:09,240 --> 00:30:13,205 Jadi dalam kasus Anda bertanya tentang sesuatu seperti menyimpan ini dalam c. 715 00:30:13,205 --> 00:30:16,320 716 00:30:16,320 --> 00:30:25,150 >> Jadi jika kita memiliki int main (void) dan sesuatu seperti ini. 717 00:30:25,150 --> 00:30:31,922 Dan Anda miliki jika adalah atas dari beberapa masukan dan Anda 718 00:30:31,922 --> 00:30:33,630 menanyakan apakah Anda dapat melakukan sesuatu seperti ini? 719 00:30:33,630 --> 00:30:35,010 720 00:30:35,010 --> 00:30:35,679 Benar? 721 00:30:35,679 --> 00:30:37,470 SISWA: Saya mencoba untuk melakukannya [tidak terdengar]. 722 00:30:37,470 --> 00:30:38,450 Karena jika it's-- 723 00:30:38,450 --> 00:30:39,200 INSTRUKTUR: Benar. 724 00:30:39,200 --> 00:30:41,197 Jadi, Anda ingin hal ini menjadi salah, kan? 725 00:30:41,197 --> 00:30:41,780 SISWA: Ya. 726 00:30:41,780 --> 00:30:45,960 INSTRUKTUR: Jadi dalam hal ini Anda ingin mengeksekusi jika itu tidak benar. 727 00:30:45,960 --> 00:30:50,510 Jadi hal yang keren yang Anda lakukan ada ini. 728 00:30:50,510 --> 00:30:52,900 729 00:30:52,900 --> 00:30:55,650 Jadi ingat seru Titik meniadakan hal-hal? 730 00:30:55,650 --> 00:30:58,270 Dikatakan [tak terdengar] berarti tidak. 731 00:30:58,270 --> 00:31:03,590 Jadi jika kita melihat hanya bagian ini di sini, Anda lebih 732 00:31:03,590 --> 00:31:05,740 mengatakan bahwa mengevaluasi ke palsu seperti yang Anda inginkan. 733 00:31:05,740 --> 00:31:06,790 734 00:31:06,790 --> 00:31:09,880 Tidak salah memang benar yang berarti ini akan mengeksekusi. 735 00:31:09,880 --> 00:31:11,037 Apakah itu masuk akal? 736 00:31:11,037 --> 00:31:11,620 SISWA: Ya. 737 00:31:11,620 --> 00:31:12,453 INSTRUKTUR: Awesome. 738 00:31:12,453 --> 00:31:13,800 739 00:31:13,800 --> 00:31:14,300 OK. 740 00:31:14,300 --> 00:31:16,330 Jadi kita hanya bisa kembali benar dalam kasus ini. 741 00:31:16,330 --> 00:31:20,357 Jadi sekarang kita memiliki dua lainnya kasus dalam kasus ini. 742 00:31:20,357 --> 00:31:21,565 Apa dua kasus kami yang lain? 743 00:31:21,565 --> 00:31:31,610 744 00:31:31,610 --> 00:31:32,900 Mari kita melakukannya dengan cara ini. 745 00:31:32,900 --> 00:31:40,660 Jadi mari kita mulai dengan yang lain jika nilai-nilai di tengah 746 00:31:40,660 --> 00:31:43,230 kurang dari nilai yang kita inginkan. 747 00:31:43,230 --> 00:31:47,200 748 00:31:47,200 --> 00:31:52,020 Jadi nilai kita di tengah kurang dari nilai yang kita cari. 749 00:31:52,020 --> 00:31:53,765 750 00:31:53,765 --> 00:31:56,720 >> Jadi yang terikat apakah Anda pikir kita ingin memperbarui? 751 00:31:56,720 --> 00:31:57,870 752 00:31:57,870 --> 00:31:58,780 Atas atau bawah? 753 00:31:58,780 --> 00:32:01,440 754 00:32:01,440 --> 00:32:01,940 Atas? 755 00:32:01,940 --> 00:32:03,230 756 00:32:03,230 --> 00:32:06,470 Jadi sisi mana dari array kita akan melihat? 757 00:32:06,470 --> 00:32:07,500 >> SISWA: Semakin rendah. 758 00:32:07,500 --> 00:32:09,750 >> INSTRUKTUR: Kita kita akan untuk melihat kiri. 759 00:32:09,750 --> 00:32:11,120 Jadi lain jika sedikit nilai kurang. 760 00:32:11,120 --> 00:32:14,730 Jadi nilai tengah Anda di sini kurang dari apa yang kita inginkan. 761 00:32:14,730 --> 00:32:17,202 Jadi kami ingin mengambil sisi kanan array kita. 762 00:32:17,202 --> 00:32:18,910 Jadi kita akan memperbarui batas bawah kami. 763 00:32:18,910 --> 00:32:20,210 764 00:32:20,210 --> 00:32:23,020 Jadi kita akan menetapkan kembali lebih rendah kami. 765 00:32:23,020 --> 00:32:25,221 Dan bagaimana menurutmu lebih rendah harus? 766 00:32:25,221 --> 00:32:26,304 SISWA: Nilai tengah? 767 00:32:26,304 --> 00:32:27,446 768 00:32:27,446 --> 00:32:28,820 INSTRUKTUR: Jadi value-- tengah 769 00:32:28,820 --> 00:32:30,136 SISWA: Ditambah 1. 770 00:32:30,136 --> 00:32:31,010 INSTRUKTUR: --plus 1. 771 00:32:31,010 --> 00:32:32,300 772 00:32:32,300 --> 00:32:34,380 Bisa ada yang bilang saya mengapa kami memiliki itu ditambah 1? 773 00:32:34,380 --> 00:32:35,730 >> SISWA: [? Tidak ada nilai?] lebih sama dengan itu. 774 00:32:35,730 --> 00:32:36,120 >> INSTRUKTUR: Benar. 775 00:32:36,120 --> 00:32:38,661 Karena kita sudah tahu bahwa nilai tengah kami tidak sama dengan 776 00:32:38,661 --> 00:32:42,750 dan kami ingin mengecualikan itu dari semua pencarian berikutnya. 777 00:32:42,750 --> 00:32:46,360 Jika Anda lupa bahwa ditambah 1, ini akan seperti lingkaran tanpa batas. 778 00:32:46,360 --> 00:32:49,620 Dan Anda hanya akan terjebak dalam infinite loop dan kemudian Anda akan segfault 779 00:32:49,620 --> 00:32:50,370 dan hal-hal buruk. 780 00:32:50,370 --> 00:32:54,780 Jadi selalu pastikan bahwa Anda tidak termasuk nilai yang baru saja Anda 781 00:32:54,780 --> 00:32:55,380 memandang. 782 00:32:55,380 --> 00:32:58,530 Jadi kita berhati-hati itu dengan ditambah 1. 783 00:32:58,530 --> 00:33:04,840 >> Jadi sekarang kita memiliki kondisi terakhir kami yang saya selalu demi keamanan 784 00:33:04,840 --> 00:33:12,664 Anda dapat memeriksa di sini, lain jika nilai pada tengah lebih besar dari nilai 785 00:33:12,664 --> 00:33:13,163 kita inginkan. 786 00:33:13,163 --> 00:33:16,260 787 00:33:16,260 --> 00:33:20,230 Itu berarti bahwa kita ingin setengah tangan kiri. 788 00:33:20,230 --> 00:33:21,350 789 00:33:21,350 --> 00:33:23,260 Jadi mana yang akan kita update? 790 00:33:23,260 --> 00:33:23,760 Atas. 791 00:33:23,760 --> 00:33:25,470 792 00:33:25,470 --> 00:33:26,970 Dan apakah yang satu ini akan sama? 793 00:33:26,970 --> 00:33:31,630 794 00:33:31,630 --> 00:33:33,690 Tengah minus 1 karena, Tentu saja, kami ingin 795 00:33:33,690 --> 00:33:38,370 untuk memastikan bahwa kita tidak melihat bahwa nilai tengah lagi. 796 00:33:38,370 --> 00:33:41,830 797 00:33:41,830 --> 00:33:45,110 Dan kemudian kami memilikinya. 798 00:33:45,110 --> 00:33:45,610 Itu saja. 799 00:33:45,610 --> 00:33:46,820 Itu semua pencarian biner adalah. 800 00:33:46,820 --> 00:33:48,190 Ini tidak terlalu buruk, kan? 801 00:33:48,190 --> 00:33:51,590 Hal ini seperti 10 baris kode dengan spasi. 802 00:33:51,590 --> 00:33:57,510 Jadi sangat kuat, sangat berguna, Anda akan akan menggunakannya di salah satu psets Anda nanti. 803 00:33:57,510 --> 00:33:59,360 Mungkin tidak satu ini, tapi nanti. 804 00:33:59,360 --> 00:34:00,670 Jadi mempelajarinya. 805 00:34:00,670 --> 00:34:01,510 Love it. 806 00:34:01,510 --> 00:34:02,980 Ini akan memperlakukan Anda dengan baik. 807 00:34:02,980 --> 00:34:05,370 Jadi tidak ada yang punya pertanyaan pada pencarian biner? 808 00:34:05,370 --> 00:34:06,196 Ya. 809 00:34:06,196 --> 00:34:09,840 >> SISWA: Apa itu penting apakah n Anda bahkan atau ganjil? 810 00:34:09,840 --> 00:34:10,750 >> INSTRUKTUR: No. 811 00:34:10,750 --> 00:34:18,150 Karena kita melemparkannya ke tengah sebagai int, itu hanya akan memotong itu. 812 00:34:18,150 --> 00:34:21,600 Sehingga akan tetap integer dan akan akhirnya memilah-milah semuanya. 813 00:34:21,600 --> 00:34:23,909 Jadi Anda tidak perlu khawatir tentang itu. 814 00:34:23,909 --> 00:34:24,580 Semua orang baik? 815 00:34:24,580 --> 00:34:25,659 816 00:34:25,659 --> 00:34:26,850 Mengagumkan. 817 00:34:26,850 --> 00:34:27,919 Keren. 818 00:34:27,919 --> 00:34:30,836 Jadi, kalian punya ini. 819 00:34:30,836 --> 00:34:33,380 820 00:34:33,380 --> 00:34:33,880 Slideshow. 821 00:34:33,880 --> 00:34:35,719 822 00:34:35,719 --> 00:34:43,270 Jadi seperti yang kita bicarakan, saya tahu David menyebutkan runtimes kompleksitas. 823 00:34:43,270 --> 00:34:44,420 824 00:34:44,420 --> 00:34:50,340 >> Jadi dalam kasus terbaik, itu hanya satu, yang kita sebut waktu yang konstan. 825 00:34:50,340 --> 00:34:51,909 Bisa ada yang bilang saya mengapa yang mungkin? 826 00:34:51,909 --> 00:34:52,969 827 00:34:52,969 --> 00:34:55,800 Apa jenis skenario apakah itu memerlukan? 828 00:34:55,800 --> 00:34:58,260 829 00:34:58,260 --> 00:34:58,760 Mm-hm. 830 00:34:58,760 --> 00:34:59,926 >> SISWA: [tak terdengar] first-- 831 00:34:59,926 --> 00:35:00,789 832 00:35:00,789 --> 00:35:03,830 INSTRUKTUR: Jadi tengah menjadi elemen pertama yang kita datang ke, kan? 833 00:35:03,830 --> 00:35:08,167 Jadi baik array satu atau apapun yang kita sedang mencari hanya 834 00:35:08,167 --> 00:35:09,750 kebetulan smack setetes di tengah. 835 00:35:09,750 --> 00:35:11,190 836 00:35:11,190 --> 00:35:13,380 Jadi itu yang terjadi yang terbaik. 837 00:35:13,380 --> 00:35:17,540 Anda masuk ke masalah nyata, mungkin tidak akan mencapai [tak terdengar] yang sering. 838 00:35:17,540 --> 00:35:18,667 839 00:35:18,667 --> 00:35:19,750 Bagaimana dengan kasus terburuk kami? 840 00:35:19,750 --> 00:35:21,270 Kasus terburuk kami adalah log n. 841 00:35:21,270 --> 00:35:25,360 Dan yang ada hubungannya dengan keseluruhan kekuatan dari dua hal yang saya bicarakan. 842 00:35:25,360 --> 00:35:30,930 >> Jadi dalam kasus terburuk itu berarti bahwa kita harus memotong array turun 843 00:35:30,930 --> 00:35:33,270 sampai itu unsur satu. 844 00:35:33,270 --> 00:35:34,810 845 00:35:34,810 --> 00:35:38,930 Jadi kami harus menebang setengah sebanyak yang kita bisa. 846 00:35:38,930 --> 00:35:41,430 Itulah mengapa log n karena Anda hanya terus membagi dua. 847 00:35:41,430 --> 00:35:42,890 848 00:35:42,890 --> 00:35:45,830 Jadi asumsi, hal yang perlu tahu jika Anda pernah 849 00:35:45,830 --> 00:35:48,050 akan menggunakan pencarian biner. 850 00:35:48,050 --> 00:35:50,680 Elemen Anda harus dipilah. 851 00:35:50,680 --> 00:35:53,890 Mereka harus diurutkan karena itulah satu-satunya cara Anda 852 00:35:53,890 --> 00:35:57,060 dapat tahu apakah Anda mampu untuk membuang setengah dari itu. 853 00:35:57,060 --> 00:36:00,260 >> Jika Anda memiliki tas campur aduk ini angka dan kau mengatakan, 854 00:36:00,260 --> 00:36:05,380 OK, aku akan memeriksa tengah jumlah dan nomor yang saya cari 855 00:36:05,380 --> 00:36:08,510 kurang dari itu, aku hanya akan untuk sewenang-wenang membuang satu setengah. 856 00:36:08,510 --> 00:36:11,130 Anda tidak akan tahu jika Anda angka dalam setengah lainnya. 857 00:36:11,130 --> 00:36:12,655 Daftar Anda harus diurutkan. 858 00:36:12,655 --> 00:36:14,030 859 00:36:14,030 --> 00:36:16,560 Selain itu, ini mungkin akan maju sedikit, 860 00:36:16,560 --> 00:36:18,360 tetapi Anda harus memiliki akses acak. 861 00:36:18,360 --> 00:36:21,940 Anda harus dapat langsung pergi ke elemen tengah. 862 00:36:21,940 --> 00:36:25,110 Jika Anda harus melintasi melalui sesuatu 863 00:36:25,110 --> 00:36:28,630 atau membawa Anda langkah tambahan untuk sampai ke elemen tengah, 864 00:36:28,630 --> 00:36:31,750 itu tidak log n lagi karena Anda menambahkan lebih banyak pekerjaan ke dalamnya. 865 00:36:31,750 --> 00:36:34,800 Dan ini akan membuat sedikit lebih masuk akal dalam dua minggu, 866 00:36:34,800 --> 00:36:37,950 tapi aku hanya jenis ingin pengantar, memberikan kalian gambaran tentang apa yang 867 00:36:37,950 --> 00:36:38,999 untuk datang. 868 00:36:38,999 --> 00:36:40,790 Tapi mereka adalah dua asumsi penting 869 00:36:40,790 --> 00:36:44,804 yang Anda butuhkan untuk daftar biner. 870 00:36:44,804 --> 00:36:45,720 Pastikan itu diurutkan. 871 00:36:45,720 --> 00:36:47,920 Itulah yang besar untuk kalian sekarang. 872 00:36:47,920 --> 00:36:52,170 Dan pada bahwa kita dapat masuk ke sisa macam kami. 873 00:36:52,170 --> 00:36:56,444 Jadi empat gelembung sorts--, penyisipan, seleksi, dan gabungan. 874 00:36:56,444 --> 00:36:57,485 Mereka semua agak dingin. 875 00:36:57,485 --> 00:37:02,860 Jika kalian memutuskan untuk mengambil CS 124, Anda akan belajar tentang segala macam macam. 876 00:37:02,860 --> 00:37:07,575 Dan jika Anda seorang penggemar XKCD, ada adalah tentang komik benar-benar keren 877 00:37:07,575 --> 00:37:11,530 seperti macam benar-benar tidak efektif, yang saya sangat menyarankan Anda akan melihat. 878 00:37:11,530 --> 00:37:16,170 Salah satunya adalah seperti panik semacam, yang seperti, oh tidak, kembali acak array. 879 00:37:16,170 --> 00:37:16,991 Sistem Shutdown. 880 00:37:16,991 --> 00:37:17,490 Tinggalkan. 881 00:37:17,490 --> 00:37:19,070 882 00:37:19,070 --> 00:37:21,500 Jadi humor culun selalu baik. 883 00:37:21,500 --> 00:37:22,620 884 00:37:22,620 --> 00:37:25,750 >> Jadi tidak ada yang ingat jenis seperti hanya ide umum 885 00:37:25,750 --> 00:37:27,810 bagaimana bubble sort bekerja. 886 00:37:27,810 --> 00:37:31,130 887 00:37:31,130 --> 00:37:32,155 Kau ingat? 888 00:37:32,155 --> 00:37:32,755 >> SISWA: Ya. 889 00:37:32,755 --> 00:37:33,970 >> INSTRUKTUR: Pergi untuk itu. 890 00:37:33,970 --> 00:37:38,980 >> SISWA: Jadi Anda akan melalui dan jika itu lebih besar, maka Anda menukar dua. 891 00:37:38,980 --> 00:37:39,820 >> INSTRUKTUR: Mm-hm. 892 00:37:39,820 --> 00:37:40,564 Tepat. 893 00:37:40,564 --> 00:37:41,730 Jadi Anda hanya iterate melalui. 894 00:37:41,730 --> 00:37:43,050 Anda memeriksa dua nomor. 895 00:37:43,050 --> 00:37:46,510 Jika salah satu sebelum lebih besar daripada yang setelah itu, 896 00:37:46,510 --> 00:37:50,230 Anda hanya swap mereka sehingga dalam cara ini semua nomor yang lebih tinggi 897 00:37:50,230 --> 00:37:54,990 gelembung menjelang akhir daftar dan semua angka yang lebih rendah gelembung bawah. 898 00:37:54,990 --> 00:37:59,355 >> Apakah dia menunjukkan kalian cool efek suara menyortir Video? 899 00:37:59,355 --> 00:38:00,480 Ini agak dingin. 900 00:38:00,480 --> 00:38:01,510 901 00:38:01,510 --> 00:38:05,200 Jadi seperti Robert hanya mengatakan, algoritma bahwa Anda hanya melangkah melalui daftar, 902 00:38:05,200 --> 00:38:07,930 swapping nilai-nilai yang berdekatan jika mereka tidak dalam rangka. 903 00:38:07,930 --> 00:38:10,975 Dan kemudian hanya terus mengulangi sampai Anda tidak melakukan swap. 904 00:38:10,975 --> 00:38:11,990 905 00:38:11,990 --> 00:38:12,740 Jadi tidak buruk, kan? 906 00:38:12,740 --> 00:38:14,080 907 00:38:14,080 --> 00:38:16,319 Jadi kita hanya memiliki contoh cepat di sini. 908 00:38:16,319 --> 00:38:18,360 Jadi ini akan mengurutkan mereka dalam urutan menaik. 909 00:38:18,360 --> 00:38:19,470 910 00:38:19,470 --> 00:38:23,470 Jadi ketika kita pergi melalui pertama waktu, kita melihat melalui delapan 911 00:38:23,470 --> 00:38:26,880 dan enam jelas tidak dalam rangka, kita swap mereka. 912 00:38:26,880 --> 00:38:27,985 >> Jadi melihat yang berikutnya. 913 00:38:27,985 --> 00:38:29,430 Delapan dan empat tidak dalam urutan. 914 00:38:29,430 --> 00:38:30,450 Swap mereka. 915 00:38:30,450 --> 00:38:32,530 Dan kemudian delapan dan dua, swap mereka. 916 00:38:32,530 --> 00:38:33,470 Di sana kami pergi. 917 00:38:33,470 --> 00:38:39,519 Jadi setelah lulus pertama Anda, Anda tahu bahwa jumlah terbesar Anda 918 00:38:39,519 --> 00:38:41,810 akan menjadi semua jalan di bagian atas karena itu hanya 919 00:38:41,810 --> 00:38:44,210 akan terus-menerus lebih besar dari segala sesuatu yang lain 920 00:38:44,210 --> 00:38:46,810 dan itu hanya akan gelembung up semua jalan ke ujung sana. 921 00:38:46,810 --> 00:38:48,226 Apakah itu masuk akal untuk semua orang? 922 00:38:48,226 --> 00:38:48,560 923 00:38:48,560 --> 00:38:49,060 Keren. 924 00:38:49,060 --> 00:38:51,310 925 00:38:51,310 --> 00:38:53,920 >> Jadi kita melihat lulus kedua kami. 926 00:38:53,920 --> 00:38:54,980 Enam dan empat, switch. 927 00:38:54,980 --> 00:38:55,920 Enam dan dua, switch. 928 00:38:55,920 --> 00:38:58,700 Dan sekarang kami memiliki beberapa hal dalam rangka. 929 00:38:58,700 --> 00:39:02,240 Jadi untuk setiap pass yang kita membuat melalui seluruh daftar kami, 930 00:39:02,240 --> 00:39:06,320 kita tahu bahwa seperti itu banyak nomor pada akhirnya akan telah disortir. 931 00:39:06,320 --> 00:39:07,690 932 00:39:07,690 --> 00:39:09,610 Jadi kita lakukan lulus ketiga, yang merupakan salah satu swap. 933 00:39:09,610 --> 00:39:10,860 934 00:39:10,860 --> 00:39:15,910 Dan kemudian pada keempat kami lulus, kita memiliki nol slot. 935 00:39:15,910 --> 00:39:18,570 Dan kita tahu bahwa kita Array telah disortir. 936 00:39:18,570 --> 00:39:20,900 >> Dan itu adalah besar hal dengan bubble sort. 937 00:39:20,900 --> 00:39:23,720 Kita tahu bahwa ketika kita memiliki nol swap, yang 938 00:39:23,720 --> 00:39:26,497 berarti bahwa segala sesuatu adalah secara lengkap. 939 00:39:26,497 --> 00:39:27,580 Ini semacam bagaimana kita memeriksa. 940 00:39:27,580 --> 00:39:28,740 941 00:39:28,740 --> 00:39:36,480 Jadi kita juga akan kode gelembung semacam yang juga tidak terlalu buruk. 942 00:39:36,480 --> 00:39:38,120 Tak satu pun dari ini adalah bahwa buruk. 943 00:39:38,120 --> 00:39:40,210 Aku tahu mereka bisa tampak sedikit menakutkan. 944 00:39:40,210 --> 00:39:42,124 Aku tahu ketika saya mengambil kelas, bahkan ketika saya 945 00:39:42,124 --> 00:39:44,290 mengajar kelas untuk pertama kalinya tahun lalu, 946 00:39:44,290 --> 00:39:46,165 Aku seperti, bagaimana saya melakukan ini? 947 00:39:46,165 --> 00:39:48,540 Masuk akal dalam teori, tetapi bagaimana kita benar-benar melakukan ini? 948 00:39:48,540 --> 00:39:51,420 Itulah sebabnya aku juga ingin berjalan melalui kode dengan kalian di sini. 949 00:39:51,420 --> 00:39:54,915 Jadi saya memiliki pseudocode sebuah untuk kalian saat ini. 950 00:39:54,915 --> 00:39:55,950 951 00:39:55,950 --> 00:39:58,970 Jadi hanya ingatlah ini sebagai kami tidak akan transisi berakhir. 952 00:39:58,970 --> 00:40:04,210 Jadi kita memiliki beberapa counter yang melacak swap kita, 953 00:40:04,210 --> 00:40:08,370 karena kita perlu memastikan bahwa kita memeriksa itu. 954 00:40:08,370 --> 00:40:11,830 Dan kita iterate seluruh array seperti yang kita hanya melakukan dengan contoh ini. 955 00:40:11,830 --> 00:40:12,900 956 00:40:12,900 --> 00:40:17,325 Jika elemen sebelum lebih besar dari unsur setelah mana kita berada di, 957 00:40:17,325 --> 00:40:20,760 kita swap mereka dan kami kenaikan kami kontra karena segera setelah kami bertukar, 958 00:40:20,760 --> 00:40:23,850 kami ingin membiarkan counter kami tahu itu. 959 00:40:23,850 --> 00:40:26,247 Ada pertanyaan di sana? 960 00:40:26,247 --> 00:40:27,580 Sesuatu tampaknya lucu di sini. 961 00:40:27,580 --> 00:40:29,225 962 00:40:29,225 --> 00:40:32,350 SISWA: Apakah Anda mengatur counter ke nol setiap kali Anda pergi melalui loop? 963 00:40:32,350 --> 00:40:34,339 Apakah Anda tidak terus kembali ke nol setiap kali? 964 00:40:34,339 --> 00:40:35,505 INSTRUKTUR: Belum tentu. 965 00:40:35,505 --> 00:40:39,710 Jadi apa yang terjadi adalah kita pergi ke sini. 966 00:40:39,710 --> 00:40:43,830 Begitu juga saat, ingat, ini akan mengeksekusi sekali tanpa gagal. 967 00:40:43,830 --> 00:40:46,480 Jadi itu akan mengatur kontra sama dengan nol, 968 00:40:46,480 --> 00:40:48,070 maka itu akan beralih melalui. 969 00:40:48,070 --> 00:40:50,590 Seperti iterates melalui, itu akan memperbarui counter. 970 00:40:50,590 --> 00:40:51,870 971 00:40:51,870 --> 00:40:56,900 Seperti update counter, bila dilakukan, ketika itu mencapai akhir dari array, 972 00:40:56,900 --> 00:41:00,830 jika daftar kami belum disortir, counter akan telah diperbarui. 973 00:41:00,830 --> 00:41:01,840 974 00:41:01,840 --> 00:41:07,150 >> Jadi cek kondisi dan berkata, OK, adalah kontra besar dari nol. 975 00:41:07,150 --> 00:41:09,290 Jika ya, lakukan lagi. 976 00:41:09,290 --> 00:41:14,340 Anda ingin me-reset sehingga ketika Anda pergi melalui, counter sama dengan nol. 977 00:41:14,340 --> 00:41:18,240 Jika Anda pergi melalui diurutkan array, tidak ada perubahan, 978 00:41:18,240 --> 00:41:21,355 ini gagal, dan Anda mengembalikan daftar diurutkan. 979 00:41:21,355 --> 00:41:23,104 980 00:41:23,104 --> 00:41:24,020 Apakah itu masuk akal? 981 00:41:24,020 --> 00:41:24,940 982 00:41:24,940 --> 00:41:26,356 SISWA: Ini mungkin dalam sedikit. 983 00:41:26,356 --> 00:41:27,147 INSTRUKTUR: OK. 984 00:41:27,147 --> 00:41:28,980 Jika ada yang lain Pertanyaan yang muncul. 985 00:41:28,980 --> 00:41:30,180 986 00:41:30,180 --> 00:41:30,680 Ya. 987 00:41:30,680 --> 00:41:33,760 >> SISWA: Apa yang akan fungsi bagi swapping elemen? 988 00:41:33,760 --> 00:41:36,900 >> INSTRUKTUR: Jadi kita benar-benar bisa menulis bahwa jika kita akan ke kanan sekarang. 989 00:41:36,900 --> 00:41:37,801 990 00:41:37,801 --> 00:41:38,300 Keren. 991 00:41:38,300 --> 00:41:42,155 Maka pada catatan itu, Alison akan untuk beralih kembali ke alat. 992 00:41:42,155 --> 00:41:43,080 Ini akan menyenangkan. 993 00:41:43,080 --> 00:41:45,170 994 00:41:45,170 --> 00:41:47,390 Dan kami memiliki bagus kami bubble sort hal di sini. 995 00:41:47,390 --> 00:41:50,800 Jadi saya sudah melakukan bersepeda melalui array. 996 00:41:50,800 --> 00:41:53,030 Kami memiliki swap kami yang sama dengan nol. 997 00:41:53,030 --> 00:41:54,480 998 00:41:54,480 --> 00:41:58,440 Jadi kita ingin menukar berdekatan elemen jika mereka rusak. 999 00:41:58,440 --> 00:42:03,020 Jadi, hal pertama yang perlu kita lakukan adalah iterate melalui array kita. 1000 00:42:03,020 --> 00:42:04,500 1001 00:42:04,500 --> 00:42:08,260 >> Jadi bagaimana Anda pikir kita mungkin iterate melalui array kita? 1002 00:42:08,260 --> 00:42:09,720 1003 00:42:09,720 --> 00:42:13,990 Kami memiliki untuk dan i sama dengan 0. 1004 00:42:13,990 --> 00:42:16,950 1005 00:42:16,950 --> 00:42:22,454 Kami ingin saya menjadi kurang dari n minus 1 dikurangi k. 1006 00:42:22,454 --> 00:42:23,870 Dan saya akan menjelaskan bahwa dalam satu detik. 1007 00:42:23,870 --> 00:42:26,280 1008 00:42:26,280 --> 00:42:32,830 Jadi ini adalah optimasi di sini di mana, ingat bagaimana aku mengatakan setelah setiap lulus 1009 00:42:32,830 --> 00:42:36,655 melalui kami array yang tahu bahwa apa pun yang on-- 1010 00:42:36,655 --> 00:42:43,590 1011 00:42:43,590 --> 00:42:46,295 >> Jadi setelah satu lulus kami tahu bahwa ini diurutkan. 1012 00:42:46,295 --> 00:42:47,370 1013 00:42:47,370 --> 00:42:50,060 Setelah dua melewati kita tahu bahwa semua ini diurutkan. 1014 00:42:50,060 --> 00:42:52,750 Setelah tiga lewat kami tahu yang diurutkan. 1015 00:42:52,750 --> 00:42:55,620 Jadi cara saya iterasi melalui array sini, 1016 00:42:55,620 --> 00:43:01,090 adalah itu pastikan untuk hanya pergi melalui apa yang kita tahu adalah tidak disortir. 1017 00:43:01,090 --> 00:43:01,644 OK? 1018 00:43:01,644 --> 00:43:02,810 Itu hanya sebuah optimasi. 1019 00:43:02,810 --> 00:43:04,430 1020 00:43:04,430 --> 00:43:08,210 Anda bisa menulis itu naif hanya iterasi melalui segala sesuatu, 1021 00:43:08,210 --> 00:43:09,970 itu hanya akan memakan waktu lebih lama. 1022 00:43:09,970 --> 00:43:12,470 Dengan empat lingkaran ini itu hanya optimasi bagus 1023 00:43:12,470 --> 00:43:18,460 karena kita tahu bahwa setelah setiap penuh iterasi melalui array sini, 1024 00:43:18,460 --> 00:43:24,050 seperti setiap lingkaran penuh di sini, kita tahu bahwa satu lagi dari unsur-unsur 1025 00:43:24,050 --> 00:43:25,760 akan diurutkan di akhir. 1026 00:43:25,760 --> 00:43:28,294 >> Jadi kita tidak perlu khawatir tentang mereka. 1027 00:43:28,294 --> 00:43:29,710 Apakah itu masuk akal untuk semua orang? 1028 00:43:29,710 --> 00:43:30,950 Itu sedikit trik keren? 1029 00:43:30,950 --> 00:43:32,060 1030 00:43:32,060 --> 00:43:37,270 Jadi dalam hal ini, jika kita iterasi melalui, 1031 00:43:37,270 --> 00:43:50,590 kita tahu bahwa kita ingin memeriksa apakah Array n dan n ditambah 1 adalah dalam rangka. 1032 00:43:50,590 --> 00:43:52,640 1033 00:43:52,640 --> 00:43:53,559 OK. 1034 00:43:53,559 --> 00:43:54,600 Jadi, inilah pseudocode. 1035 00:43:54,600 --> 00:43:57,540 Kami ingin memeriksa apakah array n dan n ditambah 1 adalah dalam rangka. 1036 00:43:57,540 --> 00:43:59,520 Jadi apa yang kita miliki di sana? 1037 00:43:59,520 --> 00:44:01,090 1038 00:44:01,090 --> 00:44:03,120 Ini akan menjadi beberapa bersyarat. 1039 00:44:03,120 --> 00:44:04,220 Ini akan menjadi jika. 1040 00:44:04,220 --> 00:44:07,066 >> SISWA: Jika array n adalah kurang dari array yang n ditambah 1. 1041 00:44:07,066 --> 00:44:07,816 INSTRUKTUR: Mm-hm. 1042 00:44:07,816 --> 00:44:09,000 1043 00:44:09,000 --> 00:44:10,699 Nah, kurang dari atau lebih besar dari. 1044 00:44:10,699 --> 00:44:11,615 SISWA: Lebih besar dari. 1045 00:44:11,615 --> 00:44:15,850 1046 00:44:15,850 --> 00:44:17,620 Kemudian kita ingin menukar mereka. 1047 00:44:17,620 --> 00:44:18,570 Tepat. 1048 00:44:18,570 --> 00:44:23,570 Jadi sekarang kita masuk ke apa mekanisme untuk swapping mereka? 1049 00:44:23,570 --> 00:44:24,840 1050 00:44:24,840 --> 00:44:28,137 Jadi kami pergi melalui singkat ini, jenis fungsi pertukaran pekan lalu. 1051 00:44:28,137 --> 00:44:29,595 Apakah ada yang ingat bagaimana ia bekerja? 1052 00:44:29,595 --> 00:44:32,300 1053 00:44:32,300 --> 00:44:34,950 Jadi kita tidak bisa hanya menetapkan kembali mereka, kan? 1054 00:44:34,950 --> 00:44:36,640 Karena salah satu dari mereka akan tersesat. 1055 00:44:36,640 --> 00:44:41,696 Jika kita mengatakan A sama dengan B dan kemudian B sama dengan A, semua tiba-tiba keduanya 1056 00:44:41,696 --> 00:44:43,150 hanya sama dengan B. 1057 00:44:43,150 --> 00:44:45,720 >> Jadi apa yang harus kita lakukan adalah kita memiliki variabel sementara itu 1058 00:44:45,720 --> 00:44:49,055 akan mengadakan salah satu dari kita sementara kami sedang dalam proses swapping. 1059 00:44:49,055 --> 00:44:50,200 1060 00:44:50,200 --> 00:44:56,464 Jadi apa yang kita miliki adalah kita akan memiliki beberapa int suhu sama to-- Anda dapat menetapkan 1061 00:44:56,464 --> 00:44:59,130 ke mana yang Anda inginkan, hanya pastikan Anda melacak itu-- 1062 00:44:59,130 --> 00:45:01,840 sehingga dalam kasus ini, aku akan menetapkan ke berbagai n ditambah 1. 1063 00:45:01,840 --> 00:45:03,360 1064 00:45:03,360 --> 00:45:07,674 Sehingga akan terus apapun Nilai adalah dalam blok kedua 1065 00:45:07,674 --> 00:45:08,590 bahwa kita sedang melihat. 1066 00:45:08,590 --> 00:45:09,700 1067 00:45:09,700 --> 00:45:13,240 >> Dan kemudian bisa kita lakukan adalah kita bisa pergi depan dan array yang Reassign n ditambah 1, 1068 00:45:13,240 --> 00:45:14,990 karena kita tahu kita memiliki nilai yang disimpan. 1069 00:45:14,990 --> 00:45:16,645 1070 00:45:16,645 --> 00:45:19,270 Ini juga salah satu besar things-- Saya tidak tahu apakah ada di antara kalian 1071 00:45:19,270 --> 00:45:23,780 memiliki masalah di mana jika Anda beralih dua baris kode tiba-tiba hal-hal bekerja. 1072 00:45:23,780 --> 00:45:25,880 Order sangat penting dalam CS. 1073 00:45:25,880 --> 00:45:29,450 Jadi, pastikan Anda diagram hal-hal jika mungkin 1074 00:45:29,450 --> 00:45:31,230 seperti apa yang sebenarnya terjadi. 1075 00:45:31,230 --> 00:45:34,256 Jadi sekarang kita akan menetapkan kembali susunan n ditambah 1, 1076 00:45:34,256 --> 00:45:36,005 karena kita tahu kita memiliki nilai yang disimpan. 1077 00:45:36,005 --> 00:45:37,090 1078 00:45:37,090 --> 00:45:41,560 >> Dan kita dapat menetapkan bahwa array n atau dalam hal ini berbagai i. 1079 00:45:41,560 --> 00:45:50,540 1080 00:45:50,540 --> 00:45:51,465 Terlalu banyak variabel. 1081 00:45:51,465 --> 00:45:54,230 1082 00:45:54,230 --> 00:45:55,470 OK. 1083 00:45:55,470 --> 00:46:01,500 Jadi sekarang kita sudah ditugaskan kembali array yang i ditambah 1 untuk sama apa yang ada di berbagai i. 1084 00:46:01,500 --> 00:46:08,240 Dan sekarang kita dapat kembali dan menetapkan susunan i apa? 1085 00:46:08,240 --> 00:46:10,680 1086 00:46:10,680 --> 00:46:11,180 Siapa? 1087 00:46:11,180 --> 00:46:13,490 1088 00:46:13,490 --> 00:46:14,010 >> SISWA: 10. 1089 00:46:14,010 --> 00:46:14,680 >> INSTRUKTUR: 10. 1090 00:46:14,680 --> 00:46:15,180 Tepat. 1091 00:46:15,180 --> 00:46:16,930 1092 00:46:16,930 --> 00:46:18,640 Dan satu hal lagi. 1093 00:46:18,640 --> 00:46:21,840 Jika kita telah bertukar sekarang, apa yang perlu kita lakukan? 1094 00:46:21,840 --> 00:46:23,740 Apa satu hal yang akan memberitahu kita 1095 00:46:23,740 --> 00:46:27,542 jika kita pernah mengakhiri program ini? 1096 00:46:27,542 --> 00:46:29,250 Apa memberitahu kita bahwa kita memiliki daftar diurutkan? 1097 00:46:29,250 --> 00:46:31,560 1098 00:46:31,560 --> 00:46:33,750 Jika kita tidak melakukan apapun swap, kan? 1099 00:46:33,750 --> 00:46:36,900 Jika swap sama dengan nol pada akhir ini. 1100 00:46:36,900 --> 00:46:42,975 Jadi, setiap kali Anda melakukan swap, seperti yang kita hanya melakukan di sini, kami ingin memperbarui swap. 1101 00:46:42,975 --> 00:46:45,002 1102 00:46:45,002 --> 00:46:47,210 Dan aku tahu ada pertanyaan sebelumnya tentang dapat Anda 1103 00:46:47,210 --> 00:46:49,689 menggunakan nol atau satu daripada dari benar atau salah. 1104 00:46:49,689 --> 00:46:50,980 Dan itulah yang ini tidak di sini. 1105 00:46:50,980 --> 00:46:52,750 Jadi ini mengatakan jika tidak swap. 1106 00:46:52,750 --> 00:47:01,310 Jadi, jika swap adalah nol, yang is-- saya selalu mendapatkan kebenaran dan kesalahan-kesalahan saya campur aduk. 1107 00:47:01,310 --> 00:47:03,960 Kami ingin kita untuk mengevaluasi untuk benar dan tidak. 1108 00:47:03,960 --> 00:47:07,680 1109 00:47:07,680 --> 00:47:09,630 Jadi jika itu nol, maka itu palsu. 1110 00:47:09,630 --> 00:47:12,560 Jika Anda meniadakan itu dengan [? Bang?] menjadi benar. 1111 00:47:12,560 --> 00:47:13,975 Jadi baris ini dijalankan. 1112 00:47:13,975 --> 00:47:15,060 1113 00:47:15,060 --> 00:47:17,370 >> Kebenaran dan palsu dan angka satu dan nol gila. 1114 00:47:17,370 --> 00:47:20,690 Hanya jika Anda berjalan perlahan-lahan melalui itu akan masuk akal. 1115 00:47:20,690 --> 00:47:23,320 Tapi itulah yang sedikit ini sedikit kode di sini tidak. 1116 00:47:23,320 --> 00:47:26,490 Jadi ini memeriksa untuk melihat telah kita lakukan setiap swap. 1117 00:47:26,490 --> 00:47:30,054 Jadi jika apa-apa selain nol, itu akan menjadi palsu 1118 00:47:30,054 --> 00:47:31,970 dan semuanya adalah akan mengeksekusi lagi. 1119 00:47:31,970 --> 00:47:33,150 1120 00:47:33,150 --> 00:47:33,650 Keren? 1121 00:47:33,650 --> 00:47:34,660 1122 00:47:34,660 --> 00:47:36,000 >> SISWA: Apa istirahat lakukan? 1123 00:47:36,000 --> 00:47:38,990 >> INSTRUKTUR: Break hanya istirahat Anda keluar dari loop. 1124 00:47:38,990 --> 00:47:41,570 Jadi dalam hal ini akan hanya ingin mengakhiri program 1125 00:47:41,570 --> 00:47:43,828 dan Anda akan hanya memiliki daftar diurutkan. 1126 00:47:43,828 --> 00:47:44,536 SISWA: Amazing. 1127 00:47:44,536 --> 00:47:48,094 1128 00:47:48,094 --> 00:47:49,010 INSTRUKTUR: Maaf? 1129 00:47:49,010 --> 00:47:52,110 SISWA: Karena sebelumnya kami digunakan ditulis 1 lebih ditulis nol 1130 00:47:52,110 --> 00:47:54,170 untuk menyajikan bahwa jika yang akan bekerja atau tidak. 1131 00:47:54,170 --> 00:47:54,878 >> INSTRUKTUR: Ya. 1132 00:47:54,878 --> 00:47:56,410 Sehingga Anda dapat kembali nol atau 1. 1133 00:47:56,410 --> 00:47:58,950 Dalam hal ini, karena kita tidak benar-benar melakukan apa-apa dengan fungsi, 1134 00:47:58,950 --> 00:48:00,150 kami hanya ingin istirahat. 1135 00:48:00,150 --> 00:48:02,680 Kami tidak benar-benar peduli tentang hal itu. 1136 00:48:02,680 --> 00:48:06,960 Rem juga baik jika itu digunakan untuk melanggar 1137 00:48:06,960 --> 00:48:10,710 dari empat loop atau kondisi yang Anda tidak ingin terus mengeksekusi. 1138 00:48:10,710 --> 00:48:12,110 Itu hanya akan membawa Anda keluar dari mereka. 1139 00:48:12,110 --> 00:48:13,587 1140 00:48:13,587 --> 00:48:14,795 Itu adalah sedikit dari hal nuansa. 1141 00:48:14,795 --> 00:48:16,737 1142 00:48:16,737 --> 00:48:18,445 Aku merasa seperti ada banyak melambaikan tangan, 1143 00:48:18,445 --> 00:48:19,740 seperti Anda akan belajar tentang hal ini segera. 1144 00:48:19,740 --> 00:48:20,955 >> Tapi Anda akan belajar tentang hal ini segera. 1145 00:48:20,955 --> 00:48:21,500 Aku berjanji. 1146 00:48:21,500 --> 00:48:22,670 1147 00:48:22,670 --> 00:48:23,170 OK. 1148 00:48:23,170 --> 00:48:24,840 Jadi tidak semua orang mendapatkan bubble sort? 1149 00:48:24,840 --> 00:48:25,550 Tidak terlalu buruk. 1150 00:48:25,550 --> 00:48:31,910 Iterate melalui, hal Swap menggunakan variabel temp, dan kami sudah siap di sana? 1151 00:48:31,910 --> 00:48:32,960 Keren. 1152 00:48:32,960 --> 00:48:34,080 Mengagumkan. 1153 00:48:34,080 --> 00:48:34,807 OK. 1154 00:48:34,807 --> 00:48:35,765 Kembali ke PowerPoint. 1155 00:48:35,765 --> 00:48:38,140 1156 00:48:38,140 --> 00:48:40,130 Ada pertanyaan secara umum tentang ini sejauh ini? 1157 00:48:40,130 --> 00:48:41,200 1158 00:48:41,200 --> 00:48:41,700 Keren. 1159 00:48:41,700 --> 00:48:43,110 1160 00:48:43,110 --> 00:48:43,695 Mm-hm. 1161 00:48:43,695 --> 00:48:45,279 >> SISWA: [tak terdengar] int main biasanya. 1162 00:48:45,279 --> 00:48:46,695 Apakah Anda harus memiliki untuk ini? 1163 00:48:46,695 --> 00:48:48,400 1164 00:48:48,400 --> 00:48:53,550 >> INSTRUKTUR: Jadi kami hanya mencari hanya di algoritma sorting yang sebenarnya. 1165 00:48:53,550 --> 00:48:54,559 1166 00:48:54,559 --> 00:48:56,350 Jika Anda punya itu dalam seperti program yang lebih besar, 1167 00:48:56,350 --> 00:48:57,891 Anda akan memiliki tempat utama int. 1168 00:48:57,891 --> 00:49:00,070 1169 00:49:00,070 --> 00:49:02,880 Tergantung di mana Anda menggunakan algoritma ini, 1170 00:49:02,880 --> 00:49:05,860 itu akan menentukan apa yang dikembalikan oleh itu. 1171 00:49:05,860 --> 00:49:09,960 Tapi untuk kasus kami, kami benar-benar melihat bagaimana hal ini benar-benar 1172 00:49:09,960 --> 00:49:11,300 iterate melalui array. 1173 00:49:11,300 --> 00:49:12,570 Jadi kita tidak khawatir tentang hal itu. 1174 00:49:12,570 --> 00:49:14,150 1175 00:49:14,150 --> 00:49:19,830 >> Jadi kami berbicara tentang kasus terbaik dan skenario kasus terburuk untuk pencarian biner. 1176 00:49:19,830 --> 00:49:22,470 Jadi itu juga penting untuk dilakukan bahwa untuk setiap macam kami. 1177 00:49:22,470 --> 00:49:24,200 1178 00:49:24,200 --> 00:49:27,560 Jadi apa yang menurut Anda adalah yang terburuk kasus runtime dari bubble sort? 1179 00:49:27,560 --> 00:49:29,560 1180 00:49:29,560 --> 00:49:30,700 Kalian ingat? 1181 00:49:30,700 --> 00:49:31,784 >> SISWA: N minus 1. 1182 00:49:31,784 --> 00:49:32,700 INSTRUKTUR: N minus 1. 1183 00:49:32,700 --> 00:49:35,070 Jadi itu berarti ada n minus 1 perbandingan. 1184 00:49:35,070 --> 00:49:40,060 Jadi satu hal yang harus disadari adalah bahwa pada iterasi pertama, 1185 00:49:40,060 --> 00:49:43,360 kita pergi melalui, kita membandingkan two-- ini jadi itu 1. 1186 00:49:43,360 --> 00:49:46,685 Kedua, tiga, empat. 1187 00:49:46,685 --> 00:49:48,070 1188 00:49:48,070 --> 00:49:55,050 Jadi setelah satu iterasi kita telah memiliki empat perbandingan. 1189 00:49:55,050 --> 00:49:58,230 Ketika saya sedang berbicara tentang runtime dan n. 1190 00:49:58,230 --> 00:50:04,680 N merupakan jumlah perbandingan sebagai fungsi dari berapa banyak elemen 1191 00:50:04,680 --> 00:50:05,570 kami. 1192 00:50:05,570 --> 00:50:06,430 OK? 1193 00:50:06,430 --> 00:50:08,860 >> Jadi kami pergi melalui, kita memiliki empat. 1194 00:50:08,860 --> 00:50:11,780 Lain kali Anda tahu kami tidak harus mengurus ini. 1195 00:50:11,780 --> 00:50:15,140 Kami membandingkan dua ini, kedua, kedua, 1196 00:50:15,140 --> 00:50:20,050 dan jika kita tidak memiliki optimasi yang dengan empat lingkaran yang saya tulis, 1197 00:50:20,050 --> 00:50:22,750 Anda akan membandingkan di sini anyways. 1198 00:50:22,750 --> 00:50:26,170 Jadi, Anda harus dijalankan melalui array 1199 00:50:26,170 --> 00:50:34,380 dan membuat perbandingan n n kali, karena setiap kali kita 1200 00:50:34,380 --> 00:50:36,670 menjalankan melalui itu kita semacam satu hal. 1201 00:50:36,670 --> 00:50:38,300 1202 00:50:38,300 --> 00:50:41,475 >> Dan setiap kali kita jalankan melalui array, kita membuat perbandingan n. 1203 00:50:41,475 --> 00:50:42,920 1204 00:50:42,920 --> 00:50:46,330 Jadi runtime kami untuk ini adalah sebenarnya n kuadrat, yang 1205 00:50:46,330 --> 00:50:48,400 jauh lebih buruk dalam kami log end karena 1206 00:50:48,400 --> 00:50:51,965 berarti jika kita memiliki empat miliar elemen, itu 1207 00:50:51,965 --> 00:50:55,260 akan membawa kita empat miliar squared bukan 32. 1208 00:50:55,260 --> 00:51:01,240 Jadi bukan runtime terbaik, tapi untuk beberapa hal, 1209 00:51:01,240 --> 00:51:04,610 Anda tahu, jika Anda dalam jarak tertentu dari elemen 1210 00:51:04,610 --> 00:51:06,540 bubble sort mungkin baik untuk digunakan. 1211 00:51:06,540 --> 00:51:07,530 >> OK. 1212 00:51:07,530 --> 00:51:12,290 Jadi sekarang apa yang terjadi runtime terbaik? 1213 00:51:12,290 --> 00:51:14,357 1214 00:51:14,357 --> 00:51:14,940 SISWA: Zero? 1215 00:51:14,940 --> 00:51:16,420 Atau 1? 1216 00:51:16,420 --> 00:51:18,140 >> INSTRUKTUR: Jadi 1 akan menjadi salah satu perbandingan. 1217 00:51:18,140 --> 00:51:19,114 Tepat. 1218 00:51:19,114 --> 00:51:20,002 >> SISWA: N minus 1? 1219 00:51:20,002 --> 00:51:21,380 1220 00:51:21,380 --> 00:51:22,320 >> INSTRUKTUR: Jadi, ya. 1221 00:51:22,320 --> 00:51:22,990 Jadi n minus 1. 1222 00:51:22,990 --> 00:51:26,510 Setiap kali Anda memiliki konsep seperti n minus 1, kita cenderung untuk hanya drop off 1223 00:51:26,510 --> 00:51:31,680 dan kami hanya mengatakan n karena Anda memiliki untuk membandingkan masing-masing these-- masing-masing pasangan. 1224 00:51:31,680 --> 00:51:36,470 Jadi akan n minus 1, yang kami kita hanya akan mengatakan kira-kira n. 1225 00:51:36,470 --> 00:51:39,280 Ketika Anda sedang berhadapan dengan runtime, segala sesuatu adalah dalam mendekati. 1226 00:51:39,280 --> 00:51:43,860 Selama eksponen benar, kau cukup baik. 1227 00:51:43,860 --> 00:51:45,700 >> Begitulah cara kita menghadapinya. 1228 00:51:45,700 --> 00:51:47,410 1229 00:51:47,410 --> 00:51:51,780 Sehingga kasus terbaik adalah n, yang berarti bahwa daftar tersebut sudah diurutkan, 1230 00:51:51,780 --> 00:51:54,320 dan semua yang kita lakukan dijalankan melalui dan memeriksa bahwa itu diurutkan. 1231 00:51:54,320 --> 00:51:56,110 1232 00:51:56,110 --> 00:51:56,855 Keren. 1233 00:51:56,855 --> 00:51:57,355 Baik. 1234 00:51:57,355 --> 00:51:58,980 1235 00:51:58,980 --> 00:52:01,920 Jadi seperti yang Anda lihat di sini, kita hanya memiliki beberapa grafik lebih. 1236 00:52:01,920 --> 00:52:02,660 Jadi n kuadrat. 1237 00:52:02,660 --> 00:52:03,780 1238 00:52:03,780 --> 00:52:05,120 Fun. 1239 00:52:05,120 --> 00:52:09,730 Jauh lebih buruk daripada n seperti yang kita lihat, dan jauh, jauh lebih buruk daripada log 2n. 1240 00:52:09,730 --> 00:52:12,060 Dan kemudian Anda juga masuk ke log log. 1241 00:52:12,060 --> 00:52:18,020 Dan Anda mengambil 124, Anda masuk ke seperti bintang log, yang seperti orang gila. 1242 00:52:18,020 --> 00:52:20,172 Jadi jika Anda tertarik, lookup log star. 1243 00:52:20,172 --> 00:52:20,880 Ini semacam menyenangkan. 1244 00:52:20,880 --> 00:52:22,800 1245 00:52:22,800 --> 00:52:24,220 Jadi kita memiliki grafik yang besar ini. 1246 00:52:24,220 --> 00:52:25,360 1247 00:52:25,360 --> 00:52:28,720 Hanya kepala up, ini grafik indah untuk memiliki 1248 00:52:28,720 --> 00:52:31,350 untuk jangka menengah Anda karena kami lama untuk meminta Anda menipis ini. 1249 00:52:31,350 --> 00:52:36,090 Jadi hanya kepala sampai, memiliki ini pada Anda jangka menengah pada bagus lembar contekan Anda 1250 00:52:36,090 --> 00:52:36,616 di sana. 1251 00:52:36,616 --> 00:52:37,990 Jadi kami hanya melihat bubble sort. 1252 00:52:37,990 --> 00:52:39,510 1253 00:52:39,510 --> 00:52:42,370 Kasus terburuk, n kuadrat, kasus terbaik, n. 1254 00:52:42,370 --> 00:52:43,367 1255 00:52:43,367 --> 00:52:44,950 Dan kita akan melihat orang lain. 1256 00:52:44,950 --> 00:52:47,940 >> Dan seperti yang Anda lihat, satu-satunya salah satu yang benar-benar baik 1257 00:52:47,940 --> 00:52:50,910 adalah semacam penggabungan, yang akan kita masuk ke mengapa. 1258 00:52:50,910 --> 00:52:52,690 1259 00:52:52,690 --> 00:52:55,215 Jadi kita akan pergi ke berikutnya satu di sini-jenis pilihan. 1260 00:52:55,215 --> 00:52:56,360 1261 00:52:56,360 --> 00:52:58,420 Apakah ada yang ingat bagaimana Temukan semacam bekerja? 1262 00:52:58,420 --> 00:53:05,200 1263 00:53:05,200 --> 00:53:05,700 Pergi untuk itu. 1264 00:53:05,700 --> 00:53:08,210 >> SISWA: Pada dasarnya melalui perintah dan membuat daftar baru. 1265 00:53:08,210 --> 00:53:11,001 Dan seperti Anda meletakkan elemen di, menempatkan mereka di tempat yang tepat 1266 00:53:11,001 --> 00:53:11,750 dalam daftar baru. 1267 00:53:11,750 --> 00:53:14,040 >> INSTRUKTUR: Sehingga suara lebih seperti insertion sort. 1268 00:53:14,040 --> 00:53:15,040 Tapi kau benar-benar dekat. 1269 00:53:15,040 --> 00:53:15,915 Mereka sangat mirip. 1270 00:53:15,915 --> 00:53:17,440 Bahkan aku mendapatkan mereka bercampur kadang-kadang. 1271 00:53:17,440 --> 00:53:18,981 Sebelum bagian ini aku seperti, menunggu. 1272 00:53:18,981 --> 00:53:20,130 1273 00:53:20,130 --> 00:53:20,630 OK. 1274 00:53:20,630 --> 00:53:24,141 Jadi apa yang ingin Anda lakukan adalah semacam seleksi, 1275 00:53:24,141 --> 00:53:25,890 cara yang dapat Anda pikirkan tentang hal itu dan cara 1276 00:53:25,890 --> 00:53:30,140 Saya memastikan bahwa saya mencoba untuk tidak mendapatkan mereka bercampur, itu berjalan melalui 1277 00:53:30,140 --> 00:53:33,280 dan memilih nomor terkecil dan 1278 00:53:33,280 --> 00:53:36,070 menempatkan bahwa pada awal daftar. 1279 00:53:36,070 --> 00:53:37,730 Hal swap dengan tempat itu pertama. 1280 00:53:37,730 --> 00:53:42,600 1281 00:53:42,600 --> 00:53:45,370 Mereka benar-benar memiliki sebuah contoh bagi saya. 1282 00:53:45,370 --> 00:53:46,540 Mengagumkan. 1283 00:53:46,540 --> 00:53:50,130 Jadi hanya cara untuk memikirkan pilihan itu-- semacam, pilih nilai terkecil. 1284 00:53:50,130 --> 00:53:51,940 Dan kita akan dijalankan melalui contoh 1285 00:53:51,940 --> 00:53:55,320 yang saya pikir akan membantu karena Saya pikir visual selalu membantu. 1286 00:53:55,320 --> 00:53:58,510 Jadi kita mulai dengan sesuatu yang benar-benar dipisahkan. 1287 00:53:58,510 --> 00:54:00,730 Red akan disortir, hijau akan diurutkan. 1288 00:54:00,730 --> 00:54:02,190 Itu semua akan masuk akal dalam satu detik. 1289 00:54:02,190 --> 00:54:08,950 >> Jadi kita pergi melalui dan kita iterate dari awal sampai akhir. 1290 00:54:08,950 --> 00:54:12,320 Dan kita katakan, OK, 2 adalah nomor terkecil kami. 1291 00:54:12,320 --> 00:54:15,680 Jadi kita akan mengambil 2 dan kita akan untuk memindahkannya ke depan array kita 1292 00:54:15,680 --> 00:54:17,734 karena itu adalah Jumlah terkecil yang kita miliki. 1293 00:54:17,734 --> 00:54:19,150 Jadi itulah apa ini lakukan di sini. 1294 00:54:19,150 --> 00:54:20,820 Ini hanya akan menukar kedua. 1295 00:54:20,820 --> 00:54:21,850 1296 00:54:21,850 --> 00:54:25,450 Jadi sekarang kami telah a diurutkan bagian dan bagian yang tidak dipisahkan. 1297 00:54:25,450 --> 00:54:27,810 Dan apa yang baik untuk diingat tentang seleksi semacam 1298 00:54:27,810 --> 00:54:30,690 adalah kita hanya memilih dari bagian yang tidak dipisahkan. 1299 00:54:30,690 --> 00:54:32,220 1300 00:54:32,220 --> 00:54:34,527 >> Bagian diurutkan Anda biarkan saja. 1301 00:54:34,527 --> 00:54:35,660 Mm-hm? 1302 00:54:35,660 --> 00:54:38,452 >> SISWA: Bagaimana cara mengetahui apa yang terkecil tanpa membandingkannya 1303 00:54:38,452 --> 00:54:39,868 untuk setiap nilai lain dalam array. 1304 00:54:39,868 --> 00:54:41,250 INSTRUKTUR: Itu membandingkannya. 1305 00:54:41,250 --> 00:54:42,041 Kami suka melewatkan itu. 1306 00:54:42,041 --> 00:54:43,850 Ini adalah keseluruhan hanya umum. 1307 00:54:43,850 --> 00:54:44,831 Ya. 1308 00:54:44,831 --> 00:54:47,205 Ketika kita menulis kode saya yakin Anda akan lebih puas. 1309 00:54:47,205 --> 00:54:48,696 1310 00:54:48,696 --> 00:54:53,030 Tapi Anda menyimpan ini pertama unsur sebagai terkecil. 1311 00:54:53,030 --> 00:54:56,110 Anda membandingkan dan Anda mengatakan, OK, itu lebih kecil? 1312 00:54:56,110 --> 00:54:56,660 Ya. 1313 00:54:56,660 --> 00:54:57,460 Menyimpannya. 1314 00:54:57,460 --> 00:54:58,640 Berikut adalah lebih kecil? 1315 00:54:58,640 --> 00:54:59,660 Tidak ada? 1316 00:54:59,660 --> 00:55:02,510 >> Ini adalah terkecil Anda, menetapkan kembali ke nilai Anda. 1317 00:55:02,510 --> 00:55:06,340 Dan Anda akan jauh lebih bahagia ketika kita pergi melalui kode. 1318 00:55:06,340 --> 00:55:07,510 1319 00:55:07,510 --> 00:55:13,970 Jadi kita pergi melalui, kita swap, jadi kemudian kita melihat bagian disortir ini. 1320 00:55:13,970 --> 00:55:15,810 Jadi kita akan memilih tiga. 1321 00:55:15,810 --> 00:55:18,890 Kita akan meletakkannya di di akhir bagian diurutkan kami. 1322 00:55:18,890 --> 00:55:20,267 1323 00:55:20,267 --> 00:55:23,100 Dan kita hanya akan terus melakukan bahwa, melakukan hal itu, dan melakukan hal itu. 1324 00:55:23,100 --> 00:55:24,130 1325 00:55:24,130 --> 00:55:27,420 Jadi ini semacam kami pseudocode sini. 1326 00:55:27,420 --> 00:55:29,470 1327 00:55:29,470 --> 00:55:31,380 Kami akan kode itu di sini dalam satu detik. 1328 00:55:31,380 --> 00:55:34,140 1329 00:55:34,140 --> 00:55:37,270 Tetapi hanya sesuatu untuk berjalan melalui pada tingkat tinggi. 1330 00:55:37,270 --> 00:55:40,275 Anda akan pergi dari i sama dengan 0 untuk n minus 2. 1331 00:55:40,275 --> 00:55:41,570 1332 00:55:41,570 --> 00:55:43,530 Itu optimasi lain. 1333 00:55:43,530 --> 00:55:45,020 Jangan khawatir terlalu banyak tentang hal itu. 1334 00:55:45,020 --> 00:55:46,620 Jadi seperti yang Anda katakan. 1335 00:55:46,620 --> 00:55:49,660 1336 00:55:49,660 --> 00:55:54,406 Seperti Yakub berkata, bagaimana kita melacak apa minimum kami adalah? 1337 00:55:54,406 --> 00:55:55,030 Bagaimana kita tahu? 1338 00:55:55,030 --> 00:55:57,060 Kami harus membandingkan segala sesuatu dalam daftar kami. 1339 00:55:57,060 --> 00:55:59,600 >> Jadi minimal sama dengan i. 1340 00:55:59,600 --> 00:56:03,870 Ini hanya mengatakan dalam kasus ini indeks nilai minimum kami. 1341 00:56:03,870 --> 00:56:07,660 Jadi itu akan beralih melalui dan pergi dari j sama dengan i ditambah 1. 1342 00:56:07,660 --> 00:56:11,420 Jadi kita sudah tahu bahwa itu elemen pertama kami. 1343 00:56:11,420 --> 00:56:13,240 Kita tidak perlu membandingkannya dengan dirinya sendiri. 1344 00:56:13,240 --> 00:56:16,970 Jadi kita mulai membandingkannya dengan berikutnya salah satu yang mengapa itu i ditambah 1 sampai n 1345 00:56:16,970 --> 00:56:20,110 minus 1, yang merupakan akhir array sana. 1346 00:56:20,110 --> 00:56:25,090 Dan kami mengatakan jika array di j kurang dari array yang min, 1347 00:56:25,090 --> 00:56:29,200 maka kita menetapkan kembali di mana indeks minimum kami adalah. 1348 00:56:29,200 --> 00:56:37,470 >> Dan jika min tidak sama dengan i, seperti di mana kami kembali ke sini. 1349 00:56:37,470 --> 00:56:38,950 1350 00:56:38,950 --> 00:56:41,790 Jadi seperti ketika kami pertama kali melakukan satu ini. 1351 00:56:41,790 --> 00:56:49,310 Dalam hal ini, itu akan mulai nol, itu akan berakhir menjadi dua. 1352 00:56:49,310 --> 00:56:53,010 Jadi min tidak akan sama i pada akhirnya. 1353 00:56:53,010 --> 00:56:55,720 Itu memungkinkan kita tahu bahwa kita perlu swap mereka. 1354 00:56:55,720 --> 00:56:57,420 1355 00:56:57,420 --> 00:57:00,470 Aku merasa seperti contoh konkret akan membantu lebih dari ini. 1356 00:57:00,470 --> 00:57:04,970 Jadi saya akan kode ini dengan kalian sekarang dan saya pikir itu akan lebih baik. 1357 00:57:04,970 --> 00:57:07,380 1358 00:57:07,380 --> 00:57:11,350 >> Macam cenderung bekerja seperti itu dalam itu sering lebih baik hanya untuk melihat mereka. 1359 00:57:11,350 --> 00:57:12,780 1360 00:57:12,780 --> 00:57:17,280 Jadi apa yang ingin kita lakukan adalah pertama kita ingin terkecil 1361 00:57:17,280 --> 00:57:19,890 elemen dalam posisinya dalam array. 1362 00:57:19,890 --> 00:57:21,280 Persis apa yang dikatakan Jacob. 1363 00:57:21,280 --> 00:57:23,090 Anda perlu untuk menyimpan yang entah bagaimana. 1364 00:57:23,090 --> 00:57:25,900 Jadi kita akan mulai di sini iterasi array. 1365 00:57:25,900 --> 00:57:28,970 Kita akan mengatakan itu kami pertama hanya untuk memulai dengan. 1366 00:57:28,970 --> 00:57:38,308 Jadi kita akan memiliki int terkecil sama dengan berbagai at i. 1367 00:57:38,308 --> 00:57:40,500 1368 00:57:40,500 --> 00:57:45,050 >> Jadi satu hal untuk melihat, setiap lingkaran waktu ini dijalankan, 1369 00:57:45,050 --> 00:57:48,550 kita mulai satu langkah lebih jauh. 1370 00:57:48,550 --> 00:57:54,780 1371 00:57:54,780 --> 00:57:57,440 Ketika kita mulai kita melihat yang satu ini. 1372 00:57:57,440 --> 00:58:00,840 Lain kali kita iterate melalui, kita mulai di satu ini 1373 00:58:00,840 --> 00:58:02,680 dan menetapkan nilai terkecil kami. 1374 00:58:02,680 --> 00:58:10,450 Jadi itu sangat mirip dengan bubble sort di mana kita tahu bahwa setelah satu lulus, 1375 00:58:10,450 --> 00:58:11,700 Unsur terakhir ini diurutkan. 1376 00:58:11,700 --> 00:58:12,810 1377 00:58:12,810 --> 00:58:15,120 Dengan pemilihan jenis, itu justru sebaliknya. 1378 00:58:15,120 --> 00:58:18,950 >> Pada setiap lulus, kita tahu bahwa yang pertama diurutkan. 1379 00:58:18,950 --> 00:58:21,360 Setelah lulus kedua, kedua akan diurutkan. 1380 00:58:21,360 --> 00:58:26,470 Dan seperti yang Anda lihat dengan contoh slide, bagian kami diurutkan hanya terus tumbuh. 1381 00:58:26,470 --> 00:58:34,020 Jadi dengan menetapkan satu terkecil kami untuk array i, semua yang dilakukannya 1382 00:58:34,020 --> 00:58:37,340 adalah konstriksi apa kita sedang melihat sehingga 1383 00:58:37,340 --> 00:58:40,164 untuk meminimalkan jumlah perbandingan kita buat. 1384 00:58:40,164 --> 00:58:41,770 Apakah itu masuk akal untuk semua orang? 1385 00:58:41,770 --> 00:58:42,920 1386 00:58:42,920 --> 00:58:46,380 Apakah Anda perlu saya untuk menjalankan melalui itu lagi lambat atau dengan kata yang berbeda? 1387 00:58:46,380 --> 00:58:47,180 Saya senang untuk. 1388 00:58:47,180 --> 00:58:48,095 1389 00:58:48,095 --> 00:58:48,595 OK. 1390 00:58:48,595 --> 00:58:50,060 1391 00:58:50,060 --> 00:58:55,540 >> Jadi kita menyimpan nilai pada saat ini, 1392 00:58:55,540 --> 00:58:57,840 tapi kami juga ingin menyimpan indeks. 1393 00:58:57,840 --> 00:59:01,010 Jadi kita akan menyimpan posisi terkecil 1394 00:59:01,010 --> 00:59:02,770 satu, yang hanya akan menjadi i. 1395 00:59:02,770 --> 00:59:04,357 1396 00:59:04,357 --> 00:59:05,440 Jadi sekarang Yakub puas. 1397 00:59:05,440 --> 00:59:06,870 Kami memiliki hal-hal yang tersimpan. 1398 00:59:06,870 --> 00:59:08,240 1399 00:59:08,240 --> 00:59:11,870 Dan sekarang kita perlu melihat melalui bagian disortir dari array. 1400 00:59:11,870 --> 00:59:18,170 Jadi dalam hal ini ini akan disortir kami. 1401 00:59:18,170 --> 00:59:20,980 1402 00:59:20,980 --> 00:59:22,462 Ini adalah i. 1403 00:59:22,462 --> 00:59:25,430 1404 00:59:25,430 --> 00:59:26,210 OK. 1405 00:59:26,210 --> 00:59:30,040 >> Jadi apa yang kita akan lakukan akan menjadi untuk loop. 1406 00:59:30,040 --> 00:59:32,066 Setiap kali Anda perlu iterate melalui sebuah array, 1407 00:59:32,066 --> 00:59:33,440 pikiran Anda bisa pergi ke untuk loop. 1408 00:59:33,440 --> 00:59:34,760 1409 00:59:34,760 --> 00:59:38,090 Jadi untuk beberapa int k equals-- apa yang kita pikirkan 1410 00:59:38,090 --> 00:59:39,700 k akan sama untuk memulai dengan? 1411 00:59:39,700 --> 00:59:41,580 1412 00:59:41,580 --> 00:59:44,766 Ini adalah apa yang kita ditetapkan sebagai terkecil kami nilai dan kami ingin membandingkannya. 1413 00:59:44,766 --> 00:59:47,090 Apa yang kita ingin membandingkannya dengan? 1414 00:59:47,090 --> 00:59:48,730 Ini akan menjadi salah satu berikutnya ini, kan? 1415 00:59:48,730 --> 00:59:53,200 Jadi kami ingin k diinisialisasi untuk i ditambah 1 untuk memulai. 1416 00:59:53,200 --> 00:59:55,350 1417 00:59:55,350 --> 01:00:02,800 >> Dan kami ingin k dalam hal ini kita sudah memiliki ukuran yang tersimpan di sini, 1418 01:00:02,800 --> 01:00:03,930 jadi kami hanya bisa menggunakan ukuran. 1419 01:00:03,930 --> 01:00:06,240 Ukuran menjadi ukuran array. 1420 01:00:06,240 --> 01:00:09,620 Dan kami hanya ingin memperbarui k per satu setiap kali. 1421 01:00:09,620 --> 01:00:17,410 1422 01:00:17,410 --> 01:00:17,910 Keren. 1423 01:00:17,910 --> 01:00:19,650 1424 01:00:19,650 --> 01:00:23,430 Jadi sekarang kita perlu menemukan elemen terkecil sini. 1425 01:00:23,430 --> 01:00:24,470 1426 01:00:24,470 --> 01:00:31,380 Jadi jika kita iterate melalui, kita ingin mengatakan, jika array di k 1427 01:00:31,380 --> 01:00:37,080 kurang dari value-- terkecil kami ini adalah di mana kita benar-benar 1428 01:00:37,080 --> 01:00:42,950 melacak apa yang di sini-terkecil 1429 01:00:42,950 --> 01:00:47,740 maka kita ingin menetapkan kembali apa nilai terkecil kita. 1430 01:00:47,740 --> 01:00:50,645 >> Ini berarti bahwa, oh, kami iterasi melalui sini. 1431 01:00:50,645 --> 01:00:51,699 1432 01:00:51,699 --> 01:00:53,740 Apapun nilai di sini adalah tidak hal terkecil kami. 1433 01:00:53,740 --> 01:00:54,448 Kami tidak ingin itu. 1434 01:00:54,448 --> 01:00:56,100 Kami ingin menetapkan kembali. 1435 01:00:56,100 --> 01:01:02,050 Jadi jika kita pemindahan itu, apa yang dilakukan Anda berpikir mungkin dalam kode ini di sini? 1436 01:01:02,050 --> 01:01:04,160 Kami ingin menetapkan kembali terkecil dan posisi. 1437 01:01:04,160 --> 01:01:05,740 1438 01:01:05,740 --> 01:01:07,010 Jadi apa yang terkecil sekarang? 1439 01:01:07,010 --> 01:01:08,422 1440 01:01:08,422 --> 01:01:09,130 SISWA: Array k. 1441 01:01:09,130 --> 01:01:09,963 INSTRUKTUR: Array k. 1442 01:01:09,963 --> 01:01:13,480 1443 01:01:13,480 --> 01:01:15,956 Dan apa posisi sekarang? 1444 01:01:15,956 --> 01:01:20,940 1445 01:01:20,940 --> 01:01:23,000 Apa indeks nilai terkecil kita? 1446 01:01:23,000 --> 01:01:24,030 1447 01:01:24,030 --> 01:01:24,530 Hanya saja k. 1448 01:01:24,530 --> 01:01:25,690 1449 01:01:25,690 --> 01:01:27,790 Jadi Array k, k, mereka cocok. 1450 01:01:27,790 --> 01:01:31,670 1451 01:01:31,670 --> 01:01:33,120 Jadi kita ingin menetapkan kembali itu. 1452 01:01:33,120 --> 01:01:34,390 1453 01:01:34,390 --> 01:01:39,950 Dan kemudian setelah kami menemukan terkecil kami, sehingga pada akhir ini untuk loop 1454 01:01:39,950 --> 01:01:45,100 di sini kami telah menemukan apa yang terkecil kami Nilai adalah, jadi kami hanya swap. 1455 01:01:45,100 --> 01:01:47,100 1456 01:01:47,100 --> 01:01:50,816 Dalam hal ini, seperti mengatakan kami Nilai terkecil adalah di sini. 1457 01:01:50,816 --> 01:01:51,940 Ini adalah nilai terkecil kita. 1458 01:01:51,940 --> 01:01:57,690 >> Kami hanya ingin menukar sini, yang apa fungsi swap yang di bagian bawah 1459 01:01:57,690 --> 01:02:01,270 lakukan, yang kita hanya menuliskan bersama-sama beberapa menit yang lalu. 1460 01:02:01,270 --> 01:02:02,775 Jadi harus tampak akrab. 1461 01:02:02,775 --> 01:02:04,320 1462 01:02:04,320 --> 01:02:08,030 Dan kemudian itu hanya akan iterate melalui sampai mencapai semua jalan 1463 01:02:08,030 --> 01:02:13,100 sampai akhir, yang berarti bahwa Anda memiliki nol elemen yang unsorted 1464 01:02:13,100 --> 01:02:14,800 dan segala sesuatu yang lain telah disortir. 1465 01:02:14,800 --> 01:02:16,216 1466 01:02:16,216 --> 01:02:16,715 Masuk akal? 1467 01:02:16,715 --> 01:02:18,010 1468 01:02:18,010 --> 01:02:19,280 Sedikit lebih konkret? 1469 01:02:19,280 --> 01:02:19,990 Kode bantuan? 1470 01:02:19,990 --> 01:02:21,720 1471 01:02:21,720 --> 01:02:26,410 >> SISWA: Untuk ukuran, Anda tidak pernah benar-benar mendefinisikannya atau mengubahnya, 1472 01:02:26,410 --> 01:02:27,340 bagaimana cara tahu? 1473 01:02:27,340 --> 01:02:32,380 >> INSTRUKTUR: Jadi satu hal untuk perhatikan di sini adalah ukuran int. 1474 01:02:32,380 --> 01:02:35,680 Jadi kami katakan dalam semacam sort-- ini adalah fungsi dalam case-- itu 1475 01:02:35,680 --> 01:02:40,770 selection sort, itu berlalu dengan fungsi. 1476 01:02:40,770 --> 01:02:43,460 Jadi, jika tidak disahkan , Anda akan melakukan sesuatu 1477 01:02:43,460 --> 01:02:47,840 seperti dengan panjang array atau Anda akan iterate melalui 1478 01:02:47,840 --> 01:02:49,390 untuk menemukan panjang. 1479 01:02:49,390 --> 01:02:52,680 Tetapi karena itu berlalu di, kita hanya bisa menggunakannya. 1480 01:02:52,680 --> 01:02:55,720 Anda hanya berasumsi bahwa pengguna memberi Anda ukuran yang valid yang 1481 01:02:55,720 --> 01:02:57,698 sebenarnya merupakan ukuran array Anda. 1482 01:02:57,698 --> 01:02:59,461 1483 01:02:59,461 --> 01:02:59,960 Keren? 1484 01:02:59,960 --> 01:03:01,610 1485 01:03:01,610 --> 01:03:05,870 >> Jika kalian memiliki masalah dengan ini atau ingin lebih banyak latihan coding macam 1486 01:03:05,870 --> 01:03:08,050 Anda sendiri, Anda harus pergi ke study.cs50. 1487 01:03:08,050 --> 01:03:11,560 1488 01:03:11,560 --> 01:03:12,670 Ini alat. 1489 01:03:12,670 --> 01:03:15,040 Mereka memiliki checker yang Anda benar-benar dapat menulis. 1490 01:03:15,040 --> 01:03:16,180 Mereka melakukan pseudocode. 1491 01:03:16,180 --> 01:03:19,310 Mereka memiliki lebih banyak video dan slide termasuk yang saya gunakan di sini. 1492 01:03:19,310 --> 01:03:23,150 Jadi jika Anda masih merasa agak kabur, mencoba yang keluar. 1493 01:03:23,150 --> 01:03:25,670 Seperti biasa, datang bicara padaku juga. 1494 01:03:25,670 --> 01:03:26,320 Pertanyaan? 1495 01:03:26,320 --> 01:03:28,611 >> SISWA: Apakah Anda mengatakan Ukuran yang didefinisikan sebelumnya? 1496 01:03:28,611 --> 01:03:29,234 1497 01:03:29,234 --> 01:03:29,900 INSTRUKTUR: Ya. 1498 01:03:29,900 --> 01:03:35,570 Ukuran yang sebelumnya didefinisikan up di sini di deklarasi fungsi. 1499 01:03:35,570 --> 01:03:39,060 Jadi Anda menganggap bahwa itu sudah berlalu dalam oleh pengguna, dan untuk mudahnya, 1500 01:03:39,060 --> 01:03:41,896 kita akan berasumsi bahwa pengguna memberi kami ukuran yang benar. 1501 01:03:41,896 --> 01:03:43,240 Keren. 1502 01:03:43,240 --> 01:03:44,390 Jadi itu semacam seleksi. 1503 01:03:44,390 --> 01:03:45,590 1504 01:03:45,590 --> 01:03:47,640 Guys, aku tahu kita belajar banyak hari ini. 1505 01:03:47,640 --> 01:03:49,710 Ini adalah data yang padat untuk bagian. 1506 01:03:49,710 --> 01:03:51,880 1507 01:03:51,880 --> 01:03:57,340 Maka dengan itu, kita akan untuk pergi ke insertion sort. 1508 01:03:57,340 --> 01:04:01,550 1509 01:04:01,550 --> 01:04:02,510 >> OK. 1510 01:04:02,510 --> 01:04:06,100 Jadi sebelum itu harus kita lakukan analisis runtime kami di sini. 1511 01:04:06,100 --> 01:04:10,190 Jadi dalam kasus terbaik, diberikan karena saya menunjukkan Anda 1512 01:04:10,190 --> 01:04:11,960 tabel saya sudah jenis beri tahu. 1513 01:04:11,960 --> 01:04:15,430 Tapi kasus runtime terbaik, apa yang kita pikirkan? 1514 01:04:15,430 --> 01:04:17,310 1515 01:04:17,310 --> 01:04:18,130 Semuanya diurutkan. 1516 01:04:18,130 --> 01:04:21,040 1517 01:04:21,040 --> 01:04:22,070 N kuadrat. 1518 01:04:22,070 --> 01:04:24,780 Ada yang punya penjelasan mengapa menurut Anda? 1519 01:04:24,780 --> 01:04:29,060 1520 01:04:29,060 --> 01:04:30,519 >> SISWA: Kau membandingkan through-- 1521 01:04:30,519 --> 01:04:31,268 INSTRUKTUR: Benar. 1522 01:04:31,268 --> 01:04:32,540 Anda membandingkan melalui. 1523 01:04:32,540 --> 01:04:35,630 Pada setiap iterasi, meskipun kita decrementing ini dengan satu, 1524 01:04:35,630 --> 01:04:38,950 Anda masih mencari melalui segalanya untuk menemukan satu yang terkecil. 1525 01:04:38,950 --> 01:04:42,390 Jadi bahkan jika nilai terkecil Anda di sini di awal, 1526 01:04:42,390 --> 01:04:44,710 Anda masih membandingkannya terhadap segala sesuatu yang lain 1527 01:04:44,710 --> 01:04:46,550 untuk memastikan itu adalah hal terkecil. 1528 01:04:46,550 --> 01:04:49,820 Jadi Anda akan berakhir berjalan melalui kira-kira n kuadrat kali. 1529 01:04:49,820 --> 01:04:51,090 1530 01:04:51,090 --> 01:04:51,590 Baik. 1531 01:04:51,590 --> 01:04:52,785 Dan apa kasus terburuk? 1532 01:04:52,785 --> 01:04:54,350 1533 01:04:54,350 --> 01:04:57,980 Juga n kuadrat karena Anda akan untuk melakukan itu prosedur yang sama. 1534 01:04:57,980 --> 01:05:01,670 Jadi dalam hal ini, pilihan semacam memiliki sesuatu 1535 01:05:01,670 --> 01:05:04,010 bahwa kita juga panggilan runtime yang diharapkan. 1536 01:05:04,010 --> 01:05:07,400 Jadi dalam orang lain, kita hanya tahu batas atas dan bawah. 1537 01:05:07,400 --> 01:05:11,180 Tergantung pada seberapa gila daftar atau bagaimana unsorted itu, 1538 01:05:11,180 --> 01:05:15,350 mereka bervariasi antara n atau n kuadrat. 1539 01:05:15,350 --> 01:05:16,550 Kita tidak tahu. 1540 01:05:16,550 --> 01:05:22,820 >> Tetapi karena pilihan jenis memiliki sama terburuk dan kasus terbaik, yang memberitahu kita bahwa 1541 01:05:22,820 --> 01:05:25,880 Jenis tidak peduli apa input yang kita miliki, apakah itu benar-benar 1542 01:05:25,880 --> 01:05:29,130 diurutkan atau benar-benar membalikkan diurutkan, itu 1543 01:05:29,130 --> 01:05:30,740 akan mengambil jumlah waktu yang sama. 1544 01:05:30,740 --> 01:05:33,760 Jadi dalam hal ini, jika Anda ingat dari meja kami, 1545 01:05:33,760 --> 01:05:38,610 itu benar-benar memiliki nilai yang dua jenis ini tidak memiliki, 1546 01:05:38,610 --> 01:05:40,390 yang merupakan runtime diharapkan. 1547 01:05:40,390 --> 01:05:43,350 Jadi kita tahu bahwa setiap kali kita menjalankan semacam seleksi, 1548 01:05:43,350 --> 01:05:45,380 itu dijamin menjalankan waktu n kuadrat. 1549 01:05:45,380 --> 01:05:46,630 Tidak ada variabilitas sana. 1550 01:05:46,630 --> 01:05:47,630 Hanya saja diharapkan. 1551 01:05:47,630 --> 01:05:48,820 1552 01:05:48,820 --> 01:05:52,140 Dan, sekali lagi, jika Anda ingin belajar lebih, mengambil CS 124 di musim semi. 1553 01:05:52,140 --> 01:05:55,370 1554 01:05:55,370 --> 01:05:56,712 Baik. 1555 01:05:56,712 --> 01:05:57,545 Kami telah melihat yang satu ini. 1556 01:05:57,545 --> 01:05:58,530 1557 01:05:58,530 --> 01:05:59,030 Keren. 1558 01:05:59,030 --> 01:06:00,930 Semacam Jadi penyisipan. 1559 01:06:00,930 --> 01:06:03,330 Dan aku mungkin akan untuk merintis melalui ini. 1560 01:06:03,330 --> 01:06:05,440 Aku tidak akan memiliki kalian kode itu. 1561 01:06:05,440 --> 01:06:06,580 Kami hanya akan berjalan melalui itu. 1562 01:06:06,580 --> 01:06:10,500 Jadi insertion sort adalah jenis dari mirip dengan selection sort 1563 01:06:10,500 --> 01:06:14,460 dalam bahwa kita memiliki kedua unsorted dan diurutkan bagian dari array. 1564 01:06:14,460 --> 01:06:20,260 >> Tapi apa yang berbeda adalah bahwa seperti yang kita pergi melalui satu per satu, 1565 01:06:20,260 --> 01:06:24,210 kami hanya mengambil nomor apapun adalah berikutnya dalam unsorted kami, 1566 01:06:24,210 --> 01:06:28,507 dan benar semacam itu ke array diurutkan kami. 1567 01:06:28,507 --> 01:06:30,090 Ini akan lebih masuk akal dengan sebuah contoh. 1568 01:06:30,090 --> 01:06:31,140 1569 01:06:31,140 --> 01:06:35,430 Jadi semuanya dimulai sebagai disortir, hanya suka dengan pilihan semacam. 1570 01:06:35,430 --> 01:06:38,740 Dan kita akan menyelesaikan masalah ini dalam urutan menaik seperti yang kita telah. 1571 01:06:38,740 --> 01:06:40,360 1572 01:06:40,360 --> 01:06:43,340 Jadi pada lulus pertama kami kita mengambil nilai pertama 1573 01:06:43,340 --> 01:06:46,700 dan kita katakan, OK, Anda sekarang dalam daftar sendiri. 1574 01:06:46,700 --> 01:06:49,150 >> Karena Anda berada dalam daftar sendiri, Anda diurutkan. 1575 01:06:49,150 --> 01:06:52,460 Selamat untuk menjadi elemen pertama dalam array ini. 1576 01:06:52,460 --> 01:06:54,800 Anda sudah diurutkan semua pada Anda sendiri. 1577 01:06:54,800 --> 01:06:58,900 Jadi sekarang kami telah a diurutkan dan sebuah array disortir. 1578 01:06:58,900 --> 01:07:01,760 Jadi sekarang kita ambil yang pertama. 1579 01:07:01,760 --> 01:07:05,600 Apa yang terjadi antara sini dan di sini adalah bahwa kita berkata, 1580 01:07:05,600 --> 01:07:08,890 OK, kita akan melihat nilai pertama dari array disortir kami 1581 01:07:08,890 --> 01:07:13,270 dan kita akan masukan dalam nya tempat yang benar dalam array diurutkan. 1582 01:07:13,270 --> 01:07:21,460 >> Jadi apa yang kita lakukan adalah kita mengambil 5 dan kita katakan, OK, 5 lebih besar dari 3, 1583 01:07:21,460 --> 01:07:24,630 jadi kami hanya memasukkan benar di sebelah kanan itu. 1584 01:07:24,630 --> 01:07:25,130 Kita baik. 1585 01:07:25,130 --> 01:07:26,200 1586 01:07:26,200 --> 01:07:28,420 Jadi kami pergi ke satu kami berikutnya. 1587 01:07:28,420 --> 01:07:29,720 Dan kita mengambil 2. 1588 01:07:29,720 --> 01:07:34,330 Kita berkata, OK, 2 kurang dari 3, jadi kita tahu bahwa itu 1589 01:07:34,330 --> 01:07:36,220 perlu di depan daftar kami sekarang. 1590 01:07:36,220 --> 01:07:41,800 Jadi apa yang kita lakukan adalah kita mendorong 3 dan 5 ke bawah dan kami pindah 2 ke slot pertama. 1591 01:07:41,800 --> 01:07:42,990 1592 01:07:42,990 --> 01:07:45,870 Jadi kami hanya memasukkan ke tempat yang benar seharusnya. 1593 01:07:45,870 --> 01:07:46,960 1594 01:07:46,960 --> 01:07:49,470 >> Kemudian kita melihat kami berikutnya, dan kita katakan 6. 1595 01:07:49,470 --> 01:07:53,620 OK, 6 lebih besar dari segala sesuatu dalam array diurutkan kami, 1596 01:07:53,620 --> 01:07:56,000 jadi kami hanya tag pada akhir. 1597 01:07:56,000 --> 01:07:56,960 Dan kemudian kita melihat 4. 1598 01:07:56,960 --> 01:07:58,130 1599 01:07:58,130 --> 01:08:03,020 4 kurang dari 6, itu kurang dari 5 tapi itu lebih besar dari 3. 1600 01:08:03,020 --> 01:08:06,270 Jadi kami hanya masukkan langsung ke tengah-tengah antara 3 dan 5. 1601 01:08:06,270 --> 01:08:07,380 1602 01:08:07,380 --> 01:08:10,530 Jadi untuk membuat sedikit sedikit lebih konkret, 1603 01:08:10,530 --> 01:08:12,280 di sini adalah jenis yang ide apa yang terjadi. 1604 01:08:12,280 --> 01:08:16,430 Jadi untuk setiap elemen disortir, kita menentukan di mana di bagian diurutkan 1605 01:08:16,430 --> 01:08:17,090 itu. 1606 01:08:17,090 --> 01:08:20,680 >> Jadi mengingat disortir dan disortir, 1607 01:08:20,680 --> 01:08:26,080 kita harus melintasi melalui dan angka tahu di mana cocok dalam array diurutkan. 1608 01:08:26,080 --> 01:08:31,460 Dan kita masukkan dengan menggeser elemen di sebelah kanan bawah. 1609 01:08:31,460 --> 01:08:34,910 Dan kemudian kami terus iterasi melalui sampai kita 1610 01:08:34,910 --> 01:08:39,270 memiliki daftar benar-benar diurutkan mana disortir sekarang nol 1611 01:08:39,270 --> 01:08:41,720 dan diurutkan memakan keseluruhan daftar kami. 1612 01:08:41,720 --> 01:08:43,146 1613 01:08:43,146 --> 01:08:45,854 Jadi, sekali lagi, untuk membuat sesuatu yang lebih konkret, kita memiliki pseudocode. 1614 01:08:45,854 --> 01:08:47,979 1615 01:08:47,979 --> 01:08:52,410 >> Jadi pada dasarnya untuk i adalah sama dengan 0 sampai n minus 1, 1616 01:08:52,410 --> 01:08:54,790 itu hanya panjang array kami. 1617 01:08:54,790 --> 01:09:00,979 Kami memiliki beberapa unsur yaitu sebesar array pertama atau indeks pertama. 1618 01:09:00,979 --> 01:09:03,200 Kami menetapkan j sama dengan itu. 1619 01:09:03,200 --> 01:09:04,649 1620 01:09:04,649 --> 01:09:09,210 Jadi sementara j lebih besar dari nol dan array, j minus 1 1621 01:09:09,210 --> 01:09:11,660 lebih besar dari elemen, sehingga semua yang melakukan 1622 01:09:11,660 --> 01:09:17,479 adalah memastikan bahwa j Anda benar-benar mewakili 1623 01:09:17,479 --> 01:09:20,010 bagian disortir dari array. 1624 01:09:20,010 --> 01:09:30,745 >> Jadi sementara masih ada hal-hal untuk memilah dan j minus satu is-- apa 1625 01:09:30,745 --> 01:09:31,840 adalah elemen nya? 1626 01:09:31,840 --> 01:09:34,760 J tidak pernah didefinisikan di sini. 1627 01:09:34,760 --> 01:09:35,677 Ini agak menjengkelkan. 1628 01:09:35,677 --> 01:09:36,176 OK. 1629 01:09:36,176 --> 01:09:36,689 Anyways. 1630 01:09:36,689 --> 01:09:39,899 Jadi j minus 1, Anda sedang memeriksa elemen sebelum. 1631 01:09:39,899 --> 01:09:46,460 Anda mengatakan, OK, adalah elemen sebelum mana pun aku am-- mari 1632 01:09:46,460 --> 01:09:47,540 benar-benar menarik ini. 1633 01:09:47,540 --> 01:09:52,580 1634 01:09:52,580 --> 01:09:56,830 Jadi, mari kita mengatakan ini adalah seperti pada lulus kedua kami. 1635 01:09:56,830 --> 01:09:59,525 Jadi saya akan menjadi sama 1, yang ada di sini. 1636 01:09:59,525 --> 01:10:03,310 1637 01:10:03,310 --> 01:10:06,025 >> Jadi saya akan menjadi sama dengan 1. 1638 01:10:06,025 --> 01:10:09,510 1639 01:10:09,510 --> 01:10:13,702 Ini akan menjadi 2, 4, 5, 6, 7. 1640 01:10:13,702 --> 01:10:16,060 1641 01:10:16,060 --> 01:10:16,750 Baik. 1642 01:10:16,750 --> 01:10:20,945 Jadi unsur kami dalam hal ini akan menjadi sama dengan 4. 1643 01:10:20,945 --> 01:10:22,110 1644 01:10:22,110 --> 01:10:24,946 Dan kami memiliki beberapa j yang akan sama dengan 1. 1645 01:10:24,946 --> 01:10:29,770 1646 01:10:29,770 --> 01:10:30,971 Oh, j decrementing. 1647 01:10:30,971 --> 01:10:31,720 Itulah apa itu. 1648 01:10:31,720 --> 01:10:35,680 Jadi j sama dengan saya, jadi apa ini katakan adalah bahwa kita bergerak maju, 1649 01:10:35,680 --> 01:10:37,530 kami hanya memastikan bahwa kita tidak lebih dari 1650 01:10:37,530 --> 01:10:43,520 pengindeksan dengan cara ini ketika kita mencoba untuk memasukkan sesuatu ke dalam daftar diurutkan kami. 1651 01:10:43,520 --> 01:10:49,850 >> Jadi, ketika j sama dengan 1 dalam kasus ini dan Array j dikurangi satu-- sehingga berbagai j dikurangi 1 1652 01:10:49,850 --> 01:10:54,610 adalah 2 di case-- ini kalau itu lebih besar dari elemen, 1653 01:10:54,610 --> 01:10:57,700 maka semua ini adalah melakukan bergeser segalanya. 1654 01:10:57,700 --> 01:11:04,790 Jadi dalam hal ini, berbagai j minus satu akan Array nol, yaitu 2. 1655 01:11:04,790 --> 01:11:08,430 2 tidak lebih besar dari 4, jadi ini tidak mengeksekusi. 1656 01:11:08,430 --> 01:11:11,460 Jadi pergeseran tidak bergerak ke bawah. 1657 01:11:11,460 --> 01:11:18,790 Apa yang dilakukan di sini hanya bergerak array diurutkan ke bawah. 1658 01:11:18,790 --> 01:11:22,340 1659 01:11:22,340 --> 01:11:26,400 Dalam hal ini, sebenarnya, kita bisa do-- mari kita membuat 3 ini. 1660 01:11:26,400 --> 01:11:28,080 1661 01:11:28,080 --> 01:11:31,970 Jadi jika kita berjalan melalui dengan contoh ini, kami sekarang di sini. 1662 01:11:31,970 --> 01:11:32,740 Hal ini diurutkan. 1663 01:11:32,740 --> 01:11:34,492 1664 01:11:34,492 --> 01:11:35,200 Hal ini tidak dipisahkan. 1665 01:11:35,200 --> 01:11:39,090 1666 01:11:39,090 --> 01:11:39,860 Keren? 1667 01:11:39,860 --> 01:11:46,620 Jadi saya sama dengan 2, sehingga Elemen kami adalah sama dengan 3. 1668 01:11:46,620 --> 01:11:47,920 1669 01:11:47,920 --> 01:11:52,270 Dan j kami adalah sama dengan 2. 1670 01:11:52,270 --> 01:12:00,620 Jadi kita melihat melalui dan kami mengatakan, OK, adalah array yang j minus satu 1671 01:12:00,620 --> 01:12:03,470 lebih besar dari elemen bahwa kita sedang melihat? 1672 01:12:03,470 --> 01:12:05,540 Dan jawabannya adalah ya, kan? 1673 01:12:05,540 --> 01:12:11,275 4 lebih besar dari 3 dan j adalah 2, sehingga kode ini dijalankan. 1674 01:12:11,275 --> 01:12:12,510 1675 01:12:12,510 --> 01:12:18,550 >> Jadi sekarang apa yang kita lakukan array di 2, jadi di sini, kita swap mereka. 1676 01:12:18,550 --> 01:12:25,620 Jadi kita hanya mengatakan, OK, susunan pada 2 sekarang akan menjadi 3. 1677 01:12:25,620 --> 01:12:28,130 1678 01:12:28,130 --> 01:12:32,340 Dan j akan sama j minus 1, yang adalah 1. 1679 01:12:32,340 --> 01:12:34,590 1680 01:12:34,590 --> 01:12:37,200 Itu mengerikan, tapi kalian mendapatkan ide. 1681 01:12:37,200 --> 01:12:38,360 J sekarang sama dengan 1. 1682 01:12:38,360 --> 01:12:44,360 Dan berbagai j hanya akan menjadi sama dengan elemen kami, yang 4. 1683 01:12:44,360 --> 01:12:45,950 1684 01:12:45,950 --> 01:12:48,570 Aku terhapus sesuatu yang saya tidak seharusnya memiliki atau sesuatu miswrote, 1685 01:12:48,570 --> 01:12:49,910 tapi kalian mendapatkan ide. 1686 01:12:49,910 --> 01:12:50,640 >> Bergerak di n. 1687 01:12:50,640 --> 01:12:51,920 1688 01:12:51,920 --> 01:12:57,960 Dan kemudian jika ini, itu akan loop lagi dan itu akan berkata, OK, j adalah 1 sekarang. 1689 01:12:57,960 --> 01:13:00,665 Dan berbagai j minus 1 sekarang 2. 1690 01:13:00,665 --> 01:13:01,750 1691 01:13:01,750 --> 01:13:03,760 Apakah 2 kurang dari elemen kami? 1692 01:13:03,760 --> 01:13:04,540 Tidak ada? 1693 01:13:04,540 --> 01:13:07,970 Itu berarti bahwa kita sudah dimasukkan unsur ini 1694 01:13:07,970 --> 01:13:10,110 di tempat yang benar dalam array diurutkan kami. 1695 01:13:10,110 --> 01:13:14,400 Kemudian kita bisa mengambil ini dan kita katakan, OK, array diurutkan kami di sini. 1696 01:13:14,400 --> 01:13:19,940 Dan itu akan mengambil nomor ini 6 dan menjadi seperti, OK, adalah 6 kurang dari angka ini? 1697 01:13:19,940 --> 01:13:20,480 Tidak ada? 1698 01:13:20,480 --> 01:13:21,080 Keren. 1699 01:13:21,080 --> 01:13:22,680 Kami baik-baik. 1700 01:13:22,680 --> 01:13:23,530 >> Melakukannya lagi. 1701 01:13:23,530 --> 01:13:24,740 Kita mengatakan 7. 1702 01:13:24,740 --> 01:13:29,010 Adalah 7 kurang dari akhir array diurutkan kita? 1703 01:13:29,010 --> 01:13:29,520 Nomor 1704 01:13:29,520 --> 01:13:30,430 Jadi kita baik-baik saja. 1705 01:13:30,430 --> 01:13:32,760 Jadi ini akan diurutkan. 1706 01:13:32,760 --> 01:13:38,610 Pada dasarnya semua ini tidak adalah itu mengatakan take 1707 01:13:38,610 --> 01:13:42,060 elemen pertama dari Array unsorted Anda, 1708 01:13:42,060 --> 01:13:46,010 mencari tahu di mana ia pergi dalam array diurutkan Anda. 1709 01:13:46,010 --> 01:13:48,780 Dan ini hanya membutuhkan perawatan swap untuk melakukan itu. 1710 01:13:48,780 --> 01:13:51,300 Anda pada dasarnya hanya swapping sampai itu di tempat yang tepat. 1711 01:13:51,300 --> 01:13:53,600 1712 01:13:53,600 --> 01:13:56,990 Gambar visual adalah bahwa Anda bergerak semuanya turun dengan melakukan itu. 1713 01:13:56,990 --> 01:13:59,420 >> Jadi seperti setengah bubble sort-esque. 1714 01:13:59,420 --> 01:14:02,280 1715 01:14:02,280 --> 01:14:03,420 Periksa studi 50. 1716 01:14:03,420 --> 01:14:06,000 Saya sangat merekomendasikan mencoba kode ini pada Anda sendiri. 1717 01:14:06,000 --> 01:14:07,220 1718 01:14:07,220 --> 01:14:12,450 Jika Anda memiliki masalah apapun atau Anda ingin lihat contoh kode untuk jenis penyisipan, 1719 01:14:12,450 --> 01:14:13,750 tolong beritahu saya. 1720 01:14:13,750 --> 01:14:14,500 Aku selalu sekitar. 1721 01:14:14,500 --> 01:14:16,600 1722 01:14:16,600 --> 01:14:20,200 Jadi kasus terburuk runtime dan kasus runtime terbaik. 1723 01:14:20,200 --> 01:14:30,700 Sebagai pria yang Anda lihat dari meja saya sudah menunjukkan Anda, itu baik n kuadrat dan n. 1724 01:14:30,700 --> 01:14:35,590 >> Jadi semacam pergi dari apa yang kita bicarakan tentang dengan macam kami sebelumnya, terburuk 1725 01:14:35,590 --> 01:14:38,760 kasus runtime adalah bahwa jika itu benar-benar unsorted, 1726 01:14:38,760 --> 01:14:42,530 kita harus membandingkan semua kali n ini. 1727 01:14:42,530 --> 01:14:47,020 Kami melakukan banyak perbandingan karena jika itu dalam urutan terbalik, 1728 01:14:47,020 --> 01:14:50,360 kita akan mengatakan, OK, ini adalah sama, ini baik, 1729 01:14:50,360 --> 01:14:54,650 dan yang satu ini harus dibandingkan terhadap yang pertama untuk dipindahkan kembali. 1730 01:14:54,650 --> 01:14:56,710 Dan seperti yang kita dapatkan terhadap ujung ekor, kita harus 1731 01:14:56,710 --> 01:14:59,440 untuk membandingkan, membandingkan, dan membandingkan terhadap segala sesuatu. 1732 01:14:59,440 --> 01:15:03,030 >> Jadi akhirnya menjadi sekitar n kuadrat. 1733 01:15:03,030 --> 01:15:09,510 Jika benar maka Anda mengatakan, OK, 2, kau baik. 1734 01:15:09,510 --> 01:15:11,330 3, Anda dibandingkan dengan 2. 1735 01:15:11,330 --> 01:15:12,310 Anda baik. 1736 01:15:12,310 --> 01:15:14,150 4, Anda hanya dibandingkan dengan ekor. 1737 01:15:14,150 --> 01:15:14,990 Anda baik. 1738 01:15:14,990 --> 01:15:17,140 6, dibandingkan dengan ekor, kau baik-baik saja. 1739 01:15:17,140 --> 01:15:20,870 Jadi untuk setiap titik jika sudah diurutkan, Anda membuat satu perbandingan. 1740 01:15:20,870 --> 01:15:22,320 Jadi itu hanya n. 1741 01:15:22,320 --> 01:15:26,840 Dan karena kita memiliki kasus runtime terbaik n dan kasus runtime terburuk n 1742 01:15:26,840 --> 01:15:28,680 kuadrat, kami tidak memiliki runtime yang diharapkan. 1743 01:15:28,680 --> 01:15:31,290 1744 01:15:31,290 --> 01:15:34,020 >> Itu hanya tergantung pada kekacauan daftar kami di sana. 1745 01:15:34,020 --> 01:15:35,860 1746 01:15:35,860 --> 01:15:39,530 Dan lagi, lain grafik dan tabel lain. 1747 01:15:39,530 --> 01:15:41,170 Jadi perbedaan antara macam. 1748 01:15:41,170 --> 01:15:44,180 Aku hanya akan angin melalui, saya merasa seperti kami sudah bicara secara ekstensif 1749 01:15:44,180 --> 01:15:46,570 tentang bagaimana mereka semua jenis dari beragam dan menghubungkan bersama. 1750 01:15:46,570 --> 01:15:50,564 Jadi menggabungkan semacam ini yang terakhir Aku akan membuat Anda bosan orang dengan. 1751 01:15:50,564 --> 01:15:52,105 Kami memiliki gambaran yang cukup berwarna-warni. 1752 01:15:52,105 --> 01:15:53,860 1753 01:15:53,860 --> 01:15:56,040 Jadi menggabungkan semacam merupakan algoritma rekursif. 1754 01:15:56,040 --> 01:15:59,910 Jadi kalian tahu apa fungsi rekursif adalah? 1755 01:15:59,910 --> 01:16:01,550 1756 01:16:01,550 --> 01:16:03,320 >> Siapapun ingin mengatakan? 1757 01:16:03,320 --> 01:16:04,739 Anda ingin mencoba? 1758 01:16:04,739 --> 01:16:07,280 Jadi fungsi rekursif hanya fungsi yang memanggil dirinya sendiri. 1759 01:16:07,280 --> 01:16:08,570 1760 01:16:08,570 --> 01:16:11,590 Jadi jika kalian sudah familiar dengan deret Fibonacci, 1761 01:16:11,590 --> 01:16:15,670 yang dianggap rekursif karena Anda mengambil dua sebelumnya 1762 01:16:15,670 --> 01:16:17,530 dan menambahkan mereka bersama-sama untuk mendapatkan satu berikutnya. 1763 01:16:17,530 --> 01:16:21,440 Jadi rekursif, saya selalu berpikir rekursi sebagai seperti spiral 1764 01:16:21,440 --> 01:16:24,430 sehingga Anda seperti spiral ke dalamnya. 1765 01:16:24,430 --> 01:16:27,150 Tapi itu hanya fungsi yang menyebut dirinya. 1766 01:16:27,150 --> 01:16:32,660 >> Dan, sebenarnya, benar-benar cepat saya dapat menunjukkan apa yang terlihat seperti. 1767 01:16:32,660 --> 01:16:34,260 1768 01:16:34,260 --> 01:16:41,840 Jadi rekursif sini, jika kita melihat, ini adalah cara rekursif untuk jumlah lebih dari satu array. 1769 01:16:41,840 --> 01:16:45,900 1770 01:16:45,900 --> 01:16:47,880 Jadi semua yang kita lakukan adalah kita memiliki fungsi sum 1771 01:16:47,880 --> 01:16:52,210 sum yang mengambil ukuran dan array. 1772 01:16:52,210 --> 01:16:55,210 Dan jika Anda perhatikan, ukuran decrements per satu setiap kali. 1773 01:16:55,210 --> 01:17:00,365 Dan semua hal ini adalah jika x sama dengan zero-- jadi jika ukuran array 1774 01:17:00,365 --> 01:17:02,710 sama dengan zero-- ia mengembalikan nol. 1775 01:17:02,710 --> 01:17:10,440 >> Selain itu sums ini elemen terakhir dari array, 1776 01:17:10,440 --> 01:17:14,790 dan kemudian mengambil sejumlah sisa array. 1777 01:17:14,790 --> 01:17:17,555 Jadi itu hanya memecahnya masalah kecil dan lebih kecil. 1778 01:17:17,555 --> 01:17:18,990 1779 01:17:18,990 --> 01:17:21,890 Singkat cerita, rekursi, fungsi yang memanggil dirinya sendiri. 1780 01:17:21,890 --> 01:17:25,740 Jika itu semua yang Anda keluar dari ini, itulah yang fungsi rekursif adalah. 1781 01:17:25,740 --> 01:17:29,870 Jika Anda mengambil 51, Anda akan menjadi sangat, sangat nyaman dengan rekursi. 1782 01:17:29,870 --> 01:17:31,110 1783 01:17:31,110 --> 01:17:32,370 Ini sangat keren. 1784 01:17:32,370 --> 01:17:34,660 Masuk akal pada seperti 03:00 satu malam. 1785 01:17:34,660 --> 01:17:37,900 Dan aku seperti, mengapa aku tak pernah menggunakan ini? 1786 01:17:37,900 --> 01:17:39,170 1787 01:17:39,170 --> 01:17:42,430 >> Jadi untuk merge sort, pada dasarnya apa yang akan lakukan adalah itu 1788 01:17:42,430 --> 01:17:45,620 akan memecahnya dan istirahat bawah sampai itu elemen hanya satu. 1789 01:17:45,620 --> 01:17:47,570 Unsur-unsur tunggal yang mudah untuk menyortir. 1790 01:17:47,570 --> 01:17:48,070 Kita melihat bahwa. 1791 01:17:48,070 --> 01:17:50,760 Jika Anda memiliki satu elemen, itu sudah dianggap diurutkan. 1792 01:17:50,760 --> 01:17:53,800 Jadi pada masukan dari elemen n, jika n kurang dari 2, 1793 01:17:53,800 --> 01:17:58,120 hanya kembali karena itu berarti itu 0 atau 1 seperti yang kita lihat. 1794 01:17:58,120 --> 01:18:00,050 Mereka dianggap elemen diurutkan. 1795 01:18:00,050 --> 01:18:02,170 >> Jika tidak istirahat menjadi dua. 1796 01:18:02,170 --> 01:18:06,336 Urutkan babak pertama, memilah kedua setengah, dan kemudian menggabungkan mereka bersama-sama. 1797 01:18:06,336 --> 01:18:07,460 Mengapa ini disebut merge sort. 1798 01:18:07,460 --> 01:18:08,700 1799 01:18:08,700 --> 01:18:12,155 Jadi kita miliki di sini kita akan mengurutkan ini. 1800 01:18:12,155 --> 01:18:13,410 1801 01:18:13,410 --> 01:18:17,210 Sehingga kita tetap memiliki mereka sampai ukuran array 1. 1802 01:18:17,210 --> 01:18:20,790 Jadi ketika itu 1, kita hanya kembali karena ini adalah array diurutkan, 1803 01:18:20,790 --> 01:18:23,940 dan ini adalah array diurutkan, dan itu array diurutkan, kita semua diurutkan. 1804 01:18:23,940 --> 01:18:25,390 1805 01:18:25,390 --> 01:18:29,420 Jadi apa yang kita lakukan adalah kita mulai menggabungkan mereka bersama-sama. 1806 01:18:29,420 --> 01:18:31,820 >> Jadi cara Anda dapat berpikir tentang penggabungan adalah 1807 01:18:31,820 --> 01:18:36,240 Anda hanya menghapus lebih kecil jumlah masing-masing sub array 1808 01:18:36,240 --> 01:18:38,330 dan hanya menambahkan ke array muncul. 1809 01:18:38,330 --> 01:18:44,290 Jadi jika Anda melihat di sini, ketika kita memiliki set ini kami memiliki 4, 6, dan 1. 1810 01:18:44,290 --> 01:18:47,280 Ketika kita ingin menggabungkan ini, kita melihat ini pertama dua 1811 01:18:47,280 --> 01:18:50,730 dan kita katakan, OK, 1 lebih kecil, ia pergi ke depan. 1812 01:18:50,730 --> 01:18:54,330 4 dan 6, tidak ada untuk membandingkan untuk, hanya tag pada akhir. 1813 01:18:54,330 --> 01:18:58,020 >> Ketika kita menggabungkan kedua, kami hanya mengambil salah satu yang lebih kecil dari dua, 1814 01:18:58,020 --> 01:18:59,310 jadi 1. 1815 01:18:59,310 --> 01:19:01,690 Dan sekarang kita mengambil lebih kecil dari dua, jadi 2. 1816 01:19:01,690 --> 01:19:03,330 Lebih kecil dari dua, 3. 1817 01:19:03,330 --> 01:19:06,260 Lebih kecil dari dua, 4, 5, 6. 1818 01:19:06,260 --> 01:19:08,630 Jadi Anda hanya menarik dari ini. 1819 01:19:08,630 --> 01:19:11,210 Dan karena mereka sudah telah diurutkan sebelumnya, 1820 01:19:11,210 --> 01:19:14,300 Anda hanya memiliki satu perbandingan setiap waktu di sana. 1821 01:19:14,300 --> 01:19:19,610 Jadi kode lebih di sini, hanya representasi. 1822 01:19:19,610 --> 01:19:24,410 Jadi Anda mulai dari tengah dan Anda semacam kiri dan kanan 1823 01:19:24,410 --> 01:19:26,180 dan kemudian Anda hanya gabungkan. 1824 01:19:26,180 --> 01:19:30,080 >> Dan kita tidak memiliki kode untuk menggabungkan di sini. 1825 01:19:30,080 --> 01:19:34,110 Tapi, sekali lagi, jika Anda pergi pada mempelajari 50, itu akan berada di sana. 1826 01:19:34,110 --> 01:19:36,860 Jika tidak datang bicara padaku jika Anda masih bingung. 1827 01:19:36,860 --> 01:19:42,340 Jadi hal yang keren di sini adalah bahwa kasus terbaik, kasus terburuk, dan runtime yang diharapkan 1828 01:19:42,340 --> 01:19:46,250 semua dalam log n, yang jauh lebih baik daripada kita sudah 1829 01:19:46,250 --> 01:19:48,000 terlihat untuk sisa macam kami. 1830 01:19:48,000 --> 01:19:51,840 Kami telah melihat n kuadrat dan apa yang kita benar-benar 1831 01:19:51,840 --> 01:19:54,380 mendapatkan di sini adalah n log n, yang sangat bagus. 1832 01:19:54,380 --> 01:19:55,830 >> Lihatlah betapa jauh lebih baik itu. 1833 01:19:55,830 --> 01:19:56,780 Seperti kurva bagus. 1834 01:19:56,780 --> 01:19:58,130 1835 01:19:58,130 --> 01:20:00,120 Jadi jauh lebih efisien. 1836 01:20:00,120 --> 01:20:03,510 Jika Anda pernah bisa, gunakan menggabungkan semacam. 1837 01:20:03,510 --> 01:20:04,810 Ini akan menghemat waktu Anda. 1838 01:20:04,810 --> 01:20:07,670 Kemudian lagi, seperti yang kita katakan, jika Anda turun di daerah yang lebih rendah ini, 1839 01:20:07,670 --> 01:20:09,480 itu tidak membuat banyak perbedaan. 1840 01:20:09,480 --> 01:20:11,360 Anda bangun untuk ribuan dan ribuan input, 1841 01:20:11,360 --> 01:20:13,318 Anda pasti ingin algoritma yang lebih efisien. 1842 01:20:13,318 --> 01:20:14,730 1843 01:20:14,730 --> 01:20:19,400 Dan, sekali lagi, meja yang indah kami semua macam yang kalian pelajari hari ini. 1844 01:20:19,400 --> 01:20:21,157 >> Jadi saya tahu itu merupakan hari yang padat. 1845 01:20:21,157 --> 01:20:23,490 Hal ini belum tentu akan untuk membantu Anda dengan pset Anda. 1846 01:20:23,490 --> 01:20:28,250 Tapi aku hanya ingin membuat disclaimer Bagian yang tidak hanya tentang psets. 1847 01:20:28,250 --> 01:20:31,240 Semua bahan ini adil game untuk ujian tengah semester Anda. 1848 01:20:31,240 --> 01:20:35,430 Dan juga jika Anda melanjutkan dengan CS, ini adalah fundamental sangat penting 1849 01:20:35,430 --> 01:20:37,870 bahwa Anda akan perlu tahu. 1850 01:20:37,870 --> 01:20:41,700 Jadi beberapa hari akan menjadi sedikit pset bantuan lebih lanjut, 1851 01:20:41,700 --> 01:20:44,600 tetapi beberapa minggu akan konten jauh lebih aktual 1852 01:20:44,600 --> 01:20:46,600 yang mungkin tidak tampak Super berguna bagi Anda sekarang, 1853 01:20:46,600 --> 01:20:51,215 tapi aku berjanji jika Anda terus pada akan sangat, sangat berguna. 1854 01:20:51,215 --> 01:20:52,560 1855 01:20:52,560 --> 01:20:54,250 >> Jadi itu saja untuk bagian. 1856 01:20:54,250 --> 01:20:55,250 Ke kawat. 1857 01:20:55,250 --> 01:20:56,570 Aku melakukannya dalam satu menit. 1858 01:20:56,570 --> 01:20:58,262 1859 01:20:58,262 --> 01:20:58,970 Tapi ada Anda pergi. 1860 01:20:58,970 --> 01:21:01,240 Dan saya akan memiliki donat atau permen. 1861 01:21:01,240 --> 01:21:03,464 Apakah ada yang alergi terhadap apa-apa, by the way? 1862 01:21:03,464 --> 01:21:05,307 1863 01:21:05,307 --> 01:21:05,890 Telur dan susu. 1864 01:21:05,890 --> 01:21:08,120 Jadi donat adalah tidak? 1865 01:21:08,120 --> 01:21:09,400 1866 01:21:09,400 --> 01:21:10,160 OK. 1867 01:21:10,160 --> 01:21:10,770 Baik. 1868 01:21:10,770 --> 01:21:12,120 Chocolate ada? 1869 01:21:12,120 --> 01:21:12,620 Starburst. 1870 01:21:12,620 --> 01:21:13,837 1871 01:21:13,837 --> 01:21:14,670 Starbursts baik. 1872 01:21:14,670 --> 01:21:15,170 OK. 1873 01:21:15,170 --> 01:21:17,045 Kita akan memiliki Starburst minggu depan kemudian. 1874 01:21:17,045 --> 01:21:18,240 Itulah yang akan saya dapatkan. 1875 01:21:18,240 --> 01:21:19,690 Kalian memiliki minggu yang besar. 1876 01:21:19,690 --> 01:21:20,460 Membaca spec Anda. 1877 01:21:20,460 --> 01:21:22,130 >> Let me know jika Anda memiliki pertanyaan. 1878 01:21:22,130 --> 01:21:25,300 Pset dua kelas harus kepada Anda pada hari Kamis. 1879 01:21:25,300 --> 01:21:28,320 Jika Anda memiliki pertanyaan tentang bagaimana saya dinilai sesuatu 1880 01:21:28,320 --> 01:21:32,250 atau mengapa saya dinilai sesuatu cara saya tidak, silakan email saya, datang bicara padaku. 1881 01:21:32,250 --> 01:21:34,210 Aku ini gila sedikit Minggu, tapi aku berjanji 1882 01:21:34,210 --> 01:21:36,340 Saya masih akan menjawab dalam waktu 24 jam. 1883 01:21:36,340 --> 01:21:38,240 Jadi memiliki minggu yang besar, semua orang. 1884 01:21:38,240 --> 01:21:40,090 Good luck pada pset Anda. 1885 01:21:40,090 --> 01:21:41,248