1 00:00:00,000 --> 00:00:03,332 >> [MUSIC PLAYING] 2 00:00:03,332 --> 00:00:06,490 >> ANDI PENG: Selamat Datang di minggu 3 bagian. 3 00:00:06,490 --> 00:00:09,550 Terima kasih, kalian, untuk semua datang untuk ini sebelumnya waktu mulai hari ini. 4 00:00:09,550 --> 00:00:11,466 Kami punya bagus, sedikit Kelompok intim hari ini. 5 00:00:11,466 --> 00:00:14,570 Jadi mudah-mudahan kita akan mendapatkan selesai, mungkin, awal, 6 00:00:14,570 --> 00:00:15,780 sedikit sedikit lebih awal hari ini. 7 00:00:15,780 --> 00:00:22,057 Begitu cepat, hanya beberapa pengumuman untuk agenda hari ini. 8 00:00:22,057 --> 00:00:23,890 Sebelum kita mulai, kami akan hanya pergi 9 00:00:23,890 --> 00:00:28,910 beberapa masalah logistik singkat, pset pertanyaan, menanyai, hal-hal seperti itu. 10 00:00:28,910 --> 00:00:30,250 Dan kemudian kita akan menyelam tepat di. 11 00:00:30,250 --> 00:00:34,710 Kami akan menggunakan debugger GDB untuk disebut mulai membongkar kode kita, yang David 12 00:00:34,710 --> 00:00:36,550 dijelaskan dalam ceramah hari lain. 13 00:00:36,550 --> 00:00:39,420 Kami akan pergi selama empat jenis macam. 14 00:00:39,420 --> 00:00:42,310 Kami akan pergi atas mereka cukup cepat karena mereka cukup intensif. 15 00:00:42,310 --> 00:00:45,710 Tapi tahu bahwa semua slide dan kode sumber selalu online. 16 00:00:45,710 --> 00:00:50,810 Jadi jangan ragu, di teliti, untuk kembali dan lihatlah itu. 17 00:00:50,810 --> 00:00:53,930 >> Kami akan pergi melalui notasi asimtotik, yang 18 00:00:53,930 --> 00:00:55,944 hanya cara mewah mengatakan "runtimes," 19 00:00:55,944 --> 00:00:58,360 di mana kita memiliki O besar, yang David menjelaskan dalam kuliah. 20 00:00:58,360 --> 00:01:01,550 Dan kami juga memiliki Omega, yang adalah runtime terikat lebih rendah. 21 00:01:01,550 --> 00:01:06,450 Dan kita akan berbicara sedikit lebih mendalam tentang bagaimana mereka bekerja. 22 00:01:06,450 --> 00:01:10,160 Dan terakhir, kita akan pergi lebih dari pencarian biner, karena banyak yang telah Anda 23 00:01:10,160 --> 00:01:15,190 melirik psets Anda mungkin tahu bahwa itu adalah pertanyaan yang ada di pset Anda. 24 00:01:15,190 --> 00:01:17,470 Jadi Anda semua akan senang bahwa kita menutupi hari ini. 25 00:01:17,470 --> 00:01:20,610 >> Dan terakhir, per Anda bagian umpan balik, aku benar-benar 26 00:01:20,610 --> 00:01:23,000 meninggalkan sekitar 15 menit pada akhirnya hanya pergi 27 00:01:23,000 --> 00:01:27,730 logistik pset3, pertanyaan, mungkin sedikit bimbingan, jika Anda mau, 28 00:01:27,730 --> 00:01:28,990 sebelum kita mulai pemrograman. 29 00:01:28,990 --> 00:01:30,890 Jadi mari kita coba untuk melewati bahan cukup cepat. 30 00:01:30,890 --> 00:01:33,880 Dan kemudian kita bisa menghabiskan beberapa waktu mengambil lebih banyak pertanyaan untuk pset tersebut. 31 00:01:33,880 --> 00:01:35,230 OKE. 32 00:01:35,230 --> 00:01:39,570 >> Cepat, sehingga hanya beberapa pengumuman sebelum kita mulai hari ini. 33 00:01:39,570 --> 00:01:45,410 Pertama, selamat datang untuk membuat melalui dua psets Anda. 34 00:01:45,410 --> 00:01:49,432 Aku mengambil melihat your-- yeah, mari kita mendapatkan tepuk tangan untuk yang satu. 35 00:01:49,432 --> 00:01:51,140 Sebenarnya, aku benar-benar, benar-benar terkesan. 36 00:01:51,140 --> 00:01:55,800 Saya dinilai yang pset pertama untuk kalian minggu dan Anda lalu kalian lakukan luar biasa. 37 00:01:55,800 --> 00:01:58,290 >> Gaya adalah pada titik selain beberapa komentar. 38 00:01:58,290 --> 00:02:00,660 Pastikan Anda selalu komentar kode Anda. 39 00:02:00,660 --> 00:02:03,040 Tapi psets Anda berada di titik. 40 00:02:03,040 --> 00:02:05,549 Dan tetap up. 41 00:02:05,549 --> 00:02:08,090 Dan itu baik untuk anak kelas untuk melihat bahwa kalian menempatkan 42 00:02:08,090 --> 00:02:10,704 di banyak usaha dalam gaya Anda dan desain Anda dalam kode Anda 43 00:02:10,704 --> 00:02:12,120 bahwa kita ingin bagi Anda untuk melihat. 44 00:02:12,120 --> 00:02:16,450 Jadi aku melewati sepanjang terima kasih untuk sisa TA. 45 00:02:16,450 --> 00:02:19,210 >> Namun ada beberapa pertanyaan menanyai 46 00:02:19,210 --> 00:02:22,010 Aku hanya ingin pergi lebih dari itu akan membuat kedua hidupku 47 00:02:22,010 --> 00:02:24,900 dan banyak yang lain TA 'hidup sedikit lebih mudah. 48 00:02:24,900 --> 00:02:28,220 Pertama, saya perhatikan ini masa lalu week-- berapa banyak dari Anda 49 00:02:28,220 --> 00:02:32,301 telah berjalan check50 pada kode Anda sebelum Anda mengirimkan? 50 00:02:32,301 --> 00:02:32,800 OKE. 51 00:02:32,800 --> 00:02:36,690 Jadi setiap orang harus melakukan check50, because-- sebuah secret-- kita benar-benar 52 00:02:36,690 --> 00:02:41,540 menjalankan check50 sebagai bagian dari kebenaran kami script untuk menguji kode Anda. 53 00:02:41,540 --> 00:02:45,480 Jadi jika kode Anda gagal check50, kemungkinan besar, 54 00:02:45,480 --> 00:02:47,570 itu mungkin akan gagal kami cek juga. 55 00:02:47,570 --> 00:02:49,320 Kadang-kadang kalian memiliki jawaban yang tepat. 56 00:02:49,320 --> 00:02:52,200 Seperti, di serakah, beberapa Anda memiliki nomor yang tepat, 57 00:02:52,200 --> 00:02:53,960 Anda hanya mencetak beberapa hal ekstra. 58 00:02:53,960 --> 00:02:55,940 Dan bahwa hal ekstra sebenarnya gagal cek, 59 00:02:55,940 --> 00:02:58,440 karena komputer tidak benar-benar tahu apa itu cari. 60 00:02:58,440 --> 00:03:00,981 Dan sehingga hanya akan berjalan melalui, melihat bahwa output Anda tidak 61 00:03:00,981 --> 00:03:03,810 sesuai dengan apa yang kita harapkan jawabannya menjadi, dan menandainya salah. 62 00:03:03,810 --> 00:03:06,560 >> Dan aku tahu yang terjadi di beberapa kasus Anda minggu ini. 63 00:03:06,560 --> 00:03:09,870 Jadi aku kembali dan manual regraded kode semua orang. 64 00:03:09,870 --> 00:03:12,780 Di masa depan meskipun, silahkan, pastikan 65 00:03:12,780 --> 00:03:14,570 bahwa Anda menjalankan memeriksa 50 pada kode Anda. 66 00:03:14,570 --> 00:03:17,970 Karena itu jenis sakit untuk TA harus kembali dan manual regrade 67 00:03:17,970 --> 00:03:21,197 setiap pset tunggal untuk setiap tunggal, sedikit terjawab misalnya. 68 00:03:21,197 --> 00:03:22,530 Jadi saya tidak melepas poin. 69 00:03:22,530 --> 00:03:25,210 Saya pikir saya melepas mungkin satu atau dua untuk desain. 70 00:03:25,210 --> 00:03:27,710 Di masa depan meskipun, jika Anda gagal check50, 71 00:03:27,710 --> 00:03:31,330 poin akan diambil off untuk kebenaran. 72 00:03:31,330 --> 00:03:35,020 >> Selanjutnya, psets adalah karena Jumat pada siang hari. 73 00:03:35,020 --> 00:03:38,990 Saya pikir ada tujuh menit akhir masa tenggang bahwa kita memberikan. 74 00:03:38,990 --> 00:03:42,434 Per waktu Harvard, mereka diizinkan untuk tujuh menit terlambat untuk semuanya. 75 00:03:42,434 --> 00:03:44,350 Jadi di sini di Yale, kita akan mematuhi itu juga. 76 00:03:44,350 --> 00:03:47,910 Tapi cukup banyak, di 00:07, jika pset Anda tidak di, 77 00:03:47,910 --> 00:03:49,720 itu akan ditandai sebagai akhir. 78 00:03:49,720 --> 00:03:53,160 Dan sementara itu ditandai sebagai an, TA-- aku 79 00:03:53,160 --> 00:03:54,870 masih akan kadar psets Anda. 80 00:03:54,870 --> 00:03:56,760 Sehingga Anda masih akan melihat kelas yang muncul. 81 00:03:56,760 --> 00:03:58,820 Namun, tahu bahwa pada akhir semester, 82 00:03:58,820 --> 00:04:02,270 semua psets akhir hanya akan otomatis memusatkan perhatian oleh komputer. 83 00:04:02,270 --> 00:04:04,490 >> Kami melakukan ini karena dua alasan. 84 00:04:04,490 --> 00:04:09,220 Satu, kadang-kadang kita mendapatkan dimaafkan, seperti alasan dekan, 85 00:04:09,220 --> 00:04:10,762 nanti bahwa saya tidak tahu tentang belum. 86 00:04:10,762 --> 00:04:13,761 Jadi kami ingin memastikan bahwa kami sedang kadar semuanya hanya dalam kasus, seperti, aku 87 00:04:13,761 --> 00:04:15,080 hilang alasan seorang dekan. 88 00:04:15,080 --> 00:04:17,000 Dan kedua, perlu pikiran, Anda masih bisa 89 00:04:17,000 --> 00:04:19,370 menjatuhkan salah pset yang memiliki ruang lingkup poin penuh. 90 00:04:19,370 --> 00:04:21,430 Dan jadi kami ingin kelas semua psets Anda hanya 91 00:04:21,430 --> 00:04:24,730 memastikan bahwa ruang lingkup Anda ada dan Anda mencoba mereka. 92 00:04:24,730 --> 00:04:29,150 Jadi, bahkan jika terlambat, Anda masih akan mendapatkan kredit untuk poin lingkup, saya pikir. 93 00:04:29,150 --> 00:04:33,730 >> Jadi moral dari cerita ini adalah, membuat Pastikan psets Anda berada di tepat waktu. 94 00:04:33,730 --> 00:04:38,350 Dan jika mereka tidak dalam tepat waktu, tahu bahwa itu tidak besar. 95 00:04:38,350 --> 00:04:41,678 Ya, sebelum saya melanjutkan, apakah ada yang punya pertanyaan tentang tanggapan pset? 96 00:04:41,678 --> 00:04:42,178 Ya. 97 00:04:42,178 --> 00:04:43,630 >> AUDIENCE: Apakah Anda mengatakan kami bisa drop salah satu psets? 98 00:04:43,630 --> 00:04:44,296 >> ANDI PENG: Ya. 99 00:04:44,296 --> 00:04:47,050 Jadi ada sembilan psets keseluruhan selama semester. 100 00:04:47,050 --> 00:04:50,610 Dan jika Anda memiliki ruang lingkup points-- sehingga lingkup hanya, 101 00:04:50,610 --> 00:04:53,567 cukup banyak, yang Anda mencoba yang masalah, yang Anda menempatkan dalam waktu, 102 00:04:53,567 --> 00:04:56,150 yang Anda menunjukkan bahwa Anda telah menunjukkan Anda sudah membaca spec. 103 00:04:56,150 --> 00:04:57,191 Itu cukup banyak ruang lingkup. 104 00:04:57,191 --> 00:04:59,370 Dan jika Anda memenuhi poin lingkup, kami 105 00:04:59,370 --> 00:05:03,360 bisa drop terendah satu dari lingkup penuh. 106 00:05:03,360 --> 00:05:06,790 Jadi yang ada di keuntungan Anda untuk melengkapi dan mencoba setiap pset. 107 00:05:06,790 --> 00:05:10,320 >> Bahkan upload-- jika tidak ada mereka bekerja, meng-upload mereka semua. 108 00:05:10,320 --> 00:05:13,711 Dan kemudian kita mudah-mudahan akan dapat memberikan beberapa titik-titik kembali. 109 00:05:13,711 --> 00:05:14,210 Keren. 110 00:05:14,210 --> 00:05:16,780 Ada pertanyaan lain? 111 00:05:16,780 --> 00:05:17,840 Besar. 112 00:05:17,840 --> 00:05:21,960 >> Kedua, kantor hours-- beberapa catatan singkat tentang jam kantor. 113 00:05:21,960 --> 00:05:24,300 Jadi pertama, datang di awal minggu. 114 00:05:24,300 --> 00:05:26,909 Tidak ada yang pernah di jam kantor pada hari Senin. 115 00:05:26,909 --> 00:05:28,700 Christabel datang ke jam kantor tadi malam. 116 00:05:28,700 --> 00:05:29,691 Ya, Christabel. 117 00:05:29,691 --> 00:05:32,190 Dan apa yang kita miliki di kantor jam semalam, Christabel? 118 00:05:32,190 --> 00:05:33,020 >> AUDIENCE: Kami memiliki es krim. 119 00:05:33,020 --> 00:05:36,160 >> ANDI PENG: Jadi itu benar, kami memiliki es krim pada jam-jam kantor tadi malam. 120 00:05:36,160 --> 00:05:39,390 Sementara saya tidak bisa menjanjikan Anda bahwa kita akan memiliki es krim di jam kantor 121 00:05:39,390 --> 00:05:43,230 setiap minggu, apa yang bisa saya berjanji Anda adalah bahwa akan ada secara signifikan 122 00:05:43,230 --> 00:05:45,380 siswa yang lebih baik untuk rasio TA. 123 00:05:45,380 --> 00:05:47,650 Seperti legit, itu seperti 3-1. 124 00:05:47,650 --> 00:05:50,350 Padahal, kontras bahwa dengan Kamis, Anda punya sekitar 150 125 00:05:50,350 --> 00:05:52,830 benar-benar menekankan anak-anak dan tidak ada es krim. 126 00:05:52,830 --> 00:05:55,360 Dan itu tidak produktif bagi siapa pun. 127 00:05:55,360 --> 00:05:58,730 Jadi moral dari cerita ini adalah, datang lebih awal untuk jam kantor dan hal-hal yang baik 128 00:05:58,730 --> 00:06:00,310 akan terjadi. 129 00:06:00,310 --> 00:06:02,110 >> Juga, datang siap untuk mengajukan pertanyaan. 130 00:06:02,110 --> 00:06:03,200 Kamu tahu? 131 00:06:03,200 --> 00:06:05,420 Terlepas dari apa TA, saya berpikir, telah mengatakan, 132 00:06:05,420 --> 00:06:10,710 kita sudah mendapatkan beberapa siswa yang datang pada hari Kamis di, seperti, 10:50 133 00:06:10,710 --> 00:06:15,100 tidak membaca spec menjadi seperti membantu saya, membantu saya. 134 00:06:15,100 --> 00:06:18,200 Sayangnya pada saat itu, ada tidak banyak yang bisa kita lakukan untuk membantu Anda. 135 00:06:18,200 --> 00:06:19,590 Jadi silakan datang di awal minggu. 136 00:06:19,590 --> 00:06:22,040 Datang lebih awal untuk jam kantor. 137 00:06:22,040 --> 00:06:23,350 Ayo siap untuk mengajukan pertanyaan. 138 00:06:23,350 --> 00:06:25,310 Pastikan bahwa Anda, sebagai mahasiswa, yang mana 139 00:06:25,310 --> 00:06:27,620 Anda perlu sehingga TA dapat memandu Anda sepanjang, 140 00:06:27,620 --> 00:06:32,850 yang adalah apa jam kantor harus dialokasikan untuk. 141 00:06:32,850 --> 00:06:37,380 >> Kedua, jadi aku tahu profesor ingin mengejutkan kita dengan tes. 142 00:06:37,380 --> 00:06:39,439 Aku punya seorang profesor mereka seperti, yo, dengan cara, 143 00:06:39,439 --> 00:06:41,230 ingat paruh waktu yang Anda memiliki Senin depan. 144 00:06:41,230 --> 00:06:42,855 Ya, saya tidak tahu tentang ujian tengah semester itu. 145 00:06:42,855 --> 00:06:45,630 Jadi saya akan menjadi yang TA yang mengingatkan Anda semua kuis yang 146 00:06:45,630 --> 00:06:47,270 0-- karena, kau tahu, kami CS. 147 00:06:47,270 --> 00:06:50,730 Sekarang kita sudah array dilakukan, Anda mendapatkan mengapa hal itu kuis 0, tidak kuis 1, eh? 148 00:06:50,730 --> 00:06:51,320 OKE. 149 00:06:51,320 --> 00:06:52,490 Oh, aku punya beberapa terkekeh yang satu itu. 150 00:06:52,490 --> 00:06:53,120 OKE. 151 00:06:53,120 --> 00:06:59,710 >> Jadi kuis 0 akan 14 Oktober jika Anda berada di bagian Senin-Rabu 152 00:06:59,710 --> 00:07:02,920 dan 15 Oktober jika Anda berada di bagian Selasa-Kamis. 153 00:07:02,920 --> 00:07:05,630 Ini tidak berlaku untuk Bagi Anda di Harvard 154 00:07:05,630 --> 00:07:10,350 who-- Saya pikir Anda semua akan mengambil kuis Anda pada tanggal 14. 155 00:07:10,350 --> 00:07:13,560 >> Jadi ya, minggu depan, jika David, dalam kuliah, pergi, 156 00:07:13,560 --> 00:07:15,747 yeah, jadi tentang itu kuis minggu depan, semua 157 00:07:15,747 --> 00:07:17,580 tidak akan terkejut karena Anda datang ke bagian 158 00:07:17,580 --> 00:07:19,664 dan Anda tahu bahwa Anda kuis 0 adalah dalam dua minggu. 159 00:07:19,664 --> 00:07:21,580 Dan kita akan memiliki review sesi dan segala sesuatu. 160 00:07:21,580 --> 00:07:26,360 Sehingga tidak ada kekhawatiran tentang yang takut untuk itu. 161 00:07:26,360 --> 00:07:29,890 Pertanyaan before-- pertanyaan sama sekali mengenai masalah logistik, 162 00:07:29,890 --> 00:07:32,591 grading, jam kantor, bagian? 163 00:07:32,591 --> 00:07:33,090 Ya. 164 00:07:33,090 --> 00:07:35,100 >> AUDIENCE: Jadi kuis ini akan selama kuliah? 165 00:07:35,100 --> 00:07:35,766 >> ANDI PENG: Ya. 166 00:07:35,766 --> 00:07:39,460 Jadi kuis, saya pikir, adalah 60 menit dialokasikan dalam slot waktu 167 00:07:39,460 --> 00:07:42,240 Anda hanya akan mengambil di ruang kuliah. 168 00:07:42,240 --> 00:07:44,810 Jadi Anda tidak perlu datang pada, seperti, acak 07:00. 169 00:07:44,810 --> 00:07:46,140 Itu semua baik. 170 00:07:46,140 --> 00:07:47,100 Ya. 171 00:07:47,100 --> 00:07:50,060 Keren. 172 00:07:50,060 --> 00:07:50,840 >> Baiklah. 173 00:07:50,840 --> 00:07:54,330 Jadi kita akan memperkenalkan konsep untuk Anda 174 00:07:54,330 --> 00:08:00,760 pekan ini bahwa David memiliki sudah jenis dari menyentuh dalam kuliah minggu terakhir ini. 175 00:08:00,760 --> 00:08:02,010 Ini disebut GDB. 176 00:08:02,010 --> 00:08:05,570 Dan berapa banyak dari Anda, sementara di kursus menulis psets Anda, 177 00:08:05,570 --> 00:08:09,981 telah melihat tombol besar yang mengatakan "Debug" pada bagian atas IDE Anda? 178 00:08:09,981 --> 00:08:10,480 OKE. 179 00:08:10,480 --> 00:08:13,770 Jadi sekarang kita benar-benar akan mendapatkan untuk menggali misteri apa tombol yang benar-benar 180 00:08:13,770 --> 00:08:14,270 tidak. 181 00:08:14,270 --> 00:08:16,790 Dan saya jamin, itu adalah indah, hal yang indah. 182 00:08:16,790 --> 00:08:20,740 >> Jadi sampai sekarang, saya pikir sudah ada dua hal 183 00:08:20,740 --> 00:08:23,320 siswa telah biasanya lakukan ketika debugging psets. 184 00:08:23,320 --> 00:08:27,635 Satu, mereka baik menambahkan printf () - sehingga setiap beberapa baris, 185 00:08:27,635 --> 00:08:29,760 mereka menambahkan dalam printf () - oh, apa variabel ini? 186 00:08:29,760 --> 00:08:32,551 Oh, apa variabel ini sekarang-- dan Anda jenis melihat perkembangan yang 187 00:08:32,551 --> 00:08:33,940 kode Anda seperti berjalan. 188 00:08:33,940 --> 00:08:37,030 Atau metode kedua anak-anak lakukan adalah bahwa mereka hanya menulis semuanya 189 00:08:37,030 --> 00:08:38,610 dan kemudian pergi seperti ini di akhir. 190 00:08:38,610 --> 00:08:39,970 Mudah-mudahan itu bekerja. 191 00:08:39,970 --> 00:08:44,851 Saya jamin, GDB lebih baik dari kedua metode tersebut. 192 00:08:44,851 --> 00:08:45,350 Ya. 193 00:08:45,350 --> 00:08:46,980 Jadi ini akan menjadi sahabat baru Anda. 194 00:08:46,980 --> 00:08:51,780 Karena itu adalah hal yang indah yang secara visual menampilkan kedua 195 00:08:51,780 --> 00:08:54,850 apa kode Anda lakukan pada titik tertentu 196 00:08:54,850 --> 00:08:57,486 serta apa semua Anda variabel membawa, 197 00:08:57,486 --> 00:08:59,610 seperti apa nilai-nilai mereka, pada titik tertentu. 198 00:08:59,610 --> 00:09:02,670 Dan dengan cara ini, Anda bisa benar-benar mengatur breakpoints dalam kode Anda. 199 00:09:02,670 --> 00:09:04,350 Anda dapat dijalankan melalui baris demi baris. 200 00:09:04,350 --> 00:09:07,324 Dan GDB hanya akan memiliki untuk Anda, ditampilkan untuk Anda, 201 00:09:07,324 --> 00:09:09,490 apa semua variabel Anda yang, apa yang mereka lakukan, 202 00:09:09,490 --> 00:09:10,656 apa yang terjadi dalam kode. 203 00:09:10,656 --> 00:09:13,240 Dan sedemikian rupa, itu jadi lebih mudah untuk melihat 204 00:09:13,240 --> 00:09:17,120 apa yang terjadi bukannya printf-ing atau menuliskan laporan Anda. 205 00:09:17,120 --> 00:09:19,160 >> Jadi kami akan melakukan contoh ini nanti. 206 00:09:19,160 --> 00:09:20,660 Jadi ini tampaknya sedikit abstrak. 207 00:09:20,660 --> 00:09:23,490 Jangan khawatir, kami akan melakukan contoh. 208 00:09:23,490 --> 00:09:29,170 Dan pada dasarnya, tiga terbesar, fungsi yang paling sering digunakan Anda harus di GDB 209 00:09:29,170 --> 00:09:32,500 Berikutnya adalah, Langkah lebih, dan Langkah ke tombol. 210 00:09:32,500 --> 00:09:34,860 Aku akan kepala ada, sebenarnya, sekarang. 211 00:09:34,860 --> 00:09:40,930 >> Jadi bisa kalian semua melihat bahwa atau saya harus memperbesar sedikit? 212 00:09:40,930 --> 00:09:43,220 213 00:09:43,220 --> 00:09:44,470 Di bagian belakang, bisa Anda lihat itu? 214 00:09:44,470 --> 00:09:45,730 Haruskah saya memperbesar? 215 00:09:45,730 --> 00:09:46,480 Sedikit saja? 216 00:09:46,480 --> 00:09:49,390 OK keren. 217 00:09:49,390 --> 00:09:50,280 Di sana kami pergi. 218 00:09:50,280 --> 00:09:50,960 OKE. 219 00:09:50,960 --> 00:09:57,000 >> Jadi saya punya, di sini, saya implementasi untuk serakah. 220 00:09:57,000 --> 00:10:01,430 Dan sementara banyak dari kalian menulis serakah sementara lingkaran form-- yang 221 00:10:01,430 --> 00:10:04,890 adalah cara yang bisa diterima untuk melakukan itu-- cara lain untuk melakukannya adalah dengan hanya 222 00:10:04,890 --> 00:10:06,280 membagi dalam Modulo. 223 00:10:06,280 --> 00:10:09,290 Karena Anda dapat memiliki Anda nilai dan kemudian memiliki sisanya Anda. 224 00:10:09,290 --> 00:10:11,150 Dan kemudian Anda bisa hanya menambahkannya semua bersama-sama. 225 00:10:11,150 --> 00:10:13,390 Apakah logika apa yang saya lakukan di sini masuk akal untuk semua orang, 226 00:10:13,390 --> 00:10:14,117 sebelum kita mulai? 227 00:10:14,117 --> 00:10:16,760 228 00:10:16,760 --> 00:10:17,980 Seperti? 229 00:10:17,980 --> 00:10:18,710 Keren. 230 00:10:18,710 --> 00:10:19,210 Besar. 231 00:10:19,210 --> 00:10:21,290 Itu sepotong yang cukup seksi kode, saya akan mengatakan. 232 00:10:21,290 --> 00:10:23,502 Seperti saya katakan, David, di kuliah, setelah beberapa saat, 233 00:10:23,502 --> 00:10:25,960 Anda semua akan mulai melihat kode sebagai sesuatu yang indah. 234 00:10:25,960 --> 00:10:29,950 Dan kadang-kadang ketika Anda melihat indah kode, itu seperti perasaan yang luar biasa. 235 00:10:29,950 --> 00:10:35,410 >> Jadi bagaimanapun, sementara kode ini sangat indah, itu tidak bekerja dengan benar. 236 00:10:35,410 --> 00:10:37,750 Jadi mari kita jalankan check50 ini. 237 00:10:37,750 --> 00:10:39,440 Periksa 50 20-- oop. 238 00:10:39,440 --> 00:10:43,221 239 00:10:43,221 --> 00:10:43,720 2? 240 00:10:43,720 --> 00:10:44,990 Apakah pset2 itu? 241 00:10:44,990 --> 00:10:46,870 Ya. 242 00:10:46,870 --> 00:10:47,520 Oh, pset1. 243 00:10:47,520 --> 00:10:50,970 244 00:10:50,970 --> 00:10:52,890 OKE. 245 00:10:52,890 --> 00:10:53,900 Jadi kita jalankan check50. 246 00:10:53,900 --> 00:11:01,550 247 00:11:01,550 --> 00:11:07,170 >> Dan seperti yang kalian lihat di sini, itu gagal beberapa kasus. 248 00:11:07,170 --> 00:11:10,165 Dan bagi sebagian dari Anda, dalam Tentu saja melakukan set masalah Anda, 249 00:11:10,165 --> 00:11:11,110 Anda seperti, ah, mengapa tidak bekerja. 250 00:11:11,110 --> 00:11:13,318 Mengapa bekerja untuk beberapa nilai tetapi tidak untuk orang lain? 251 00:11:13,318 --> 00:11:17,760 Nah, GDB akan membantu Anda sosok mengapa masukan mereka tidak bekerja. 252 00:11:17,760 --> 00:11:18,320 >> OKE. 253 00:11:18,320 --> 00:11:21,640 Jadi mari kita lihat, salah satu cek aku gagal di check50 254 00:11:21,640 --> 00:11:24,920 adalah nilai masukan dari 0,41. 255 00:11:24,920 --> 00:11:27,830 Jadi jawaban yang benar yang Anda harus mendapatkan adalah 4. 256 00:11:27,830 --> 00:11:33,090 Tapi bukannya apa yang saya mencetak adalah 3-n, yang tidak benar. 257 00:11:33,090 --> 00:11:36,190 Jadi mari kita jalankan ini secara manual, hanya memastikan bahwa check50 bekerja. 258 00:11:36,190 --> 00:11:36,940 Mari kita lakukan ./greedy. 259 00:11:36,940 --> 00:11:40,130 260 00:11:40,130 --> 00:11:43,340 Ups, saya harus membuat serakah. 261 00:11:43,340 --> 00:11:43,840 Di sana kami pergi. 262 00:11:43,840 --> 00:11:44,381 Sekarang ./greedy. 263 00:11:44,381 --> 00:11:46,950 264 00:11:46,950 --> 00:11:47,670 >> Berapa banyak yang berutang? 265 00:11:47,670 --> 00:11:49,550 Mari kita lakukan 0,41. 266 00:11:49,550 --> 00:11:52,590 Dan yep, kita lihat di sini bahwa itu keluaran 3 267 00:11:52,590 --> 00:11:55,160 ketika jawaban yang benar, pada kenyataannya, harus 4. 268 00:11:55,160 --> 00:12:01,460 Jadi mari kita masukkan GDB dan melihat bagaimana kami bisa pergi tentang memperbaiki masalah ini. 269 00:12:01,460 --> 00:12:03,992 >> Jadi langkah pertama dalam selalu debugging kode Anda 270 00:12:03,992 --> 00:12:05,950 adalah untuk mengatur breakpoint, atau titik di mana Anda 271 00:12:05,950 --> 00:12:09,079 ingin komputer atau debugger untuk mulai melihat. 272 00:12:09,079 --> 00:12:11,120 Jadi, jika Anda tidak benar-benar tahu apa masalah Anda, 273 00:12:11,120 --> 00:12:14,670 biasanya, hal khas kita ingin lakukan adalah untuk mengatur breakpoint kami di utama. 274 00:12:14,670 --> 00:12:18,520 Jadi jika kalian bisa melihat ini tombol merah di sana, 275 00:12:18,520 --> 00:12:22,860 yep, yang saya menetapkan breakpoint untuk fungsi utama. 276 00:12:22,860 --> 00:12:24,130 Saya klik itu. 277 00:12:24,130 --> 00:12:26,130 >> Dan kemudian saya bisa pergi ke tombol Debug saya. 278 00:12:26,130 --> 00:12:27,036 Aku menekan tombol itu. 279 00:12:27,036 --> 00:12:31,710 280 00:12:31,710 --> 00:12:36,555 Biarkan aku tampilannya kembali jika saya bisa. 281 00:12:36,555 --> 00:12:38,020 Di sana kami pergi. 282 00:12:38,020 --> 00:12:40,730 Jadi kita miliki, di sini, sebuah panel di sebelah kanan. 283 00:12:40,730 --> 00:12:43,680 Maaf, orang di belakang, Anda tidak bisa benar-benar melihat dengan sangat baik. 284 00:12:43,680 --> 00:12:49,090 Tapi pada dasarnya, semua panel kanan ini adalah melakukan 285 00:12:49,090 --> 00:12:53,130 adalah melacak kedua disorot line, yang merupakan baris kode 286 00:12:53,130 --> 00:12:56,640 bahwa komputer saat ini berjalan, serta semua variabel Anda 287 00:12:56,640 --> 00:12:57,600 dibawah sini. 288 00:12:57,600 --> 00:13:00,487 >> Jadi Anda punya sen, koin, n, semua dinyatakan hal yang berbeda 289 00:13:00,487 --> 00:13:01,070 pada pokoknya. 290 00:13:01,070 --> 00:13:04,850 Jangan khawatir, karena kita belum benar-benar diinisialisasi mereka untuk variabel apa pun. 291 00:13:04,850 --> 00:13:07,200 Jadi di komputer Anda, Anda komputer hanya melihat, 292 00:13:07,200 --> 00:13:14,376 oh, 32.767 adalah fungsi yang terakhir digunakan itu ruang memori di komputer saya. 293 00:13:14,376 --> 00:13:16,000 Dan di situlah sen saat ini. 294 00:13:16,000 --> 00:13:19,360 Tapi tidak bahwa setelah Anda menjalankan kode, itu harus menjadi diinisialisasi. 295 00:13:19,360 --> 00:13:24,110 >> Jadi mari kita pergi melalui, baris demi line, apa yang terjadi di sini. 296 00:13:24,110 --> 00:13:25,350 OKE. 297 00:13:25,350 --> 00:13:29,400 Jadi di sini adalah tiga tombol yang saya hanya menjelaskan. 298 00:13:29,400 --> 00:13:34,090 Anda memiliki Play, atau fungsi Run, tombol, Anda memiliki tombol Langkah lebih, 299 00:13:34,090 --> 00:13:36,600 dan Anda juga memiliki Langkah ke tombol. 300 00:13:36,600 --> 00:13:41,260 Dan pada dasarnya, semua tiga mereka hanya pergi melalui kode Anda 301 00:13:41,260 --> 00:13:42,690 dan melakukan hal-hal yang berbeda. 302 00:13:42,690 --> 00:13:45,680 >> Jadi biasanya, ketika Anda debugging, kita tidak ingin hanya memukul Play, 303 00:13:45,680 --> 00:13:47,930 karena Putar hanya akan berjalan kode Anda untuk akhir itu. 304 00:13:47,930 --> 00:13:49,070 Dan kemudian Anda tidak akan benar-benar tahu apa masalah Anda 305 00:13:49,070 --> 00:13:51,432 kecuali Anda mengatur beberapa breakpoints. 306 00:13:51,432 --> 00:13:53,890 Jika Anda menetapkan beberapa breakpoints, itu hanya akan otomatis 307 00:13:53,890 --> 00:13:56,030 berlari dari satu breakpoint, ke depan, ke yang berikutnya. 308 00:13:56,030 --> 00:13:58,030 Tapi dalam kasus ini kita sudah hanya satu itu, karena kita 309 00:13:58,030 --> 00:13:59,970 ingin bekerja dengan cara kami dari atas ke bawah. 310 00:13:59,970 --> 00:14:04,830 Jadi kita akan mengabaikan tombol yang sekarang untuk tujuan program ini. 311 00:14:04,830 --> 00:14:08,230 >> Jadi Langkah atas fungsi hanya langkah lebih setiap baris 312 00:14:08,230 --> 00:14:11,510 dan memberitahu Anda apa komputer lakukan. 313 00:14:11,510 --> 00:14:14,630 Langkah ke dalam fungsi berjalan ke dalam fungsi yang sebenarnya 314 00:14:14,630 --> 00:14:16,000 yang ada di baris Anda kode. 315 00:14:16,000 --> 00:14:19,070 Jadi misalnya, seperti printf (), yang fungsi, kan? 316 00:14:19,070 --> 00:14:21,980 Jika saya ingin secara fisik langkah ke dalam printf () fungsi, 317 00:14:21,980 --> 00:14:25,610 Aku akan benar-benar pergi ke sepotong kode di mana printf () ditulis dan melihat 318 00:14:25,610 --> 00:14:26,730 Apa yang sedang terjadi di sana. 319 00:14:26,730 --> 00:14:29,924 >> Tapi biasanya, kita berasumsi bahwa kode yang kami berikan Anda bekerja. 320 00:14:29,924 --> 00:14:31,340 Kami menganggap printf () bekerja. 321 00:14:31,340 --> 00:14:33,170 Kami berasumsi bahwa getInt () bekerja. 322 00:14:33,170 --> 00:14:35,170 Jadi tidak perlu untuk melangkah ke fungsi-fungsi. 323 00:14:35,170 --> 00:14:37,170 Tetapi jika ada fungsi yang Anda tulis sendiri 324 00:14:37,170 --> 00:14:39,060 yang Anda ingin memeriksa apa yang terjadi, 325 00:14:39,060 --> 00:14:41,200 Anda akan ingin melangkah ke dalam fungsi itu. 326 00:14:41,200 --> 00:14:43,940 >> Jadi sekarang kita hanya akan melangkahi potongan kode ini. 327 00:14:43,940 --> 00:14:44,485 Jadi mari kita lihat. 328 00:14:44,485 --> 00:14:46,547 Oh, cetak, "Oh hai, bagaimana banyak perubahan yang berutang? " 329 00:14:46,547 --> 00:14:47,130 Kami tidak peduli. 330 00:14:47,130 --> 00:14:49,830 Kita tahu bahwa bekerja, jadi kita melangkah di atasnya. 331 00:14:49,830 --> 00:14:53,290 >> Jadi n, yang mengambang kami yang kita sudah initialized-- atau declared-- 332 00:14:53,290 --> 00:14:56,810 di atas, kita sekarang menyamai bahwa untuk GetFloat (). 333 00:14:56,810 --> 00:14:57,810 Jadi mari kita melangkah lebih dari itu. 334 00:14:57,810 --> 00:14:59,580 Dan kita lihat pada bawah sini, program 335 00:14:59,580 --> 00:15:03,360 mendorong saya untuk memasukkan nilai. 336 00:15:03,360 --> 00:15:08,580 Jadi mari kita masukan nilai yang kita inginkan untuk menguji di sini, yang merupakan 0,41. 337 00:15:08,580 --> 00:15:09,160 Besar. 338 00:15:09,160 --> 00:15:12,780 >> Jadi sekarang n-- yang kalian lihat di sini, di bottom-- itu 339 00:15:12,780 --> 00:15:15,140 stored-- karena kita belum bulat belum, itu 340 00:15:15,140 --> 00:15:19,540 disimpan dalam raksasa seperti ini mengambang yang ,4099999996, 341 00:15:19,540 --> 00:15:22,550 yang cukup dekat dengan kami tujuan, sekarang, untuk 0,41. 342 00:15:22,550 --> 00:15:26,090 Dan kemudian kita akan lihat nanti, seperti yang kita terus melangkahi program, 343 00:15:26,090 --> 00:15:29,850 setelah di sini, n telah menjadi bulat dan sen menjadi 41. 344 00:15:29,850 --> 00:15:30,350 Besar. 345 00:15:30,350 --> 00:15:32,230 Jadi kita tahu bahwa kerja pembulatan kita. 346 00:15:32,230 --> 00:15:34,700 Kita tahu bahwa kita memiliki jumlah yang benar dari sen, 347 00:15:34,700 --> 00:15:36,990 sehingga kita tahu bahwa itu tidak benar-benar masalah. 348 00:15:36,990 --> 00:15:40,050 >> Jadi kami terus melangkah di dalam program ini. 349 00:15:40,050 --> 00:15:40,900 Kami pergi di sini. 350 00:15:40,900 --> 00:15:46,139 Dan jadi setelah baris kode ini, kita harus tahu berapa banyak tempat yang kita miliki. 351 00:15:46,139 --> 00:15:46,680 Kita melangkah lebih. 352 00:15:46,680 --> 00:15:52,040 Dan Anda melihat kami, pada kenyataannya, memiliki satu kuartal karena kami telah dikurangi 25 353 00:15:52,040 --> 00:15:53,790 dari nilai awal kami 41. 354 00:15:53,790 --> 00:15:55,890 Dan kami memiliki 16 kiri untuk sen kami. 355 00:15:55,890 --> 00:15:58,830 >> Apakah semua orang mengerti bagaimana program ini melangkah melalui 356 00:15:58,830 --> 00:16:02,980 dan mengapa sen kini telah menjadi 16 dan mengapa, sekarang, koin telah menjadi 1? 357 00:16:02,980 --> 00:16:04,610 Apakah semua orang mengikuti logika itu? 358 00:16:04,610 --> 00:16:05,110 Keren. 359 00:16:05,110 --> 00:16:07,860 Sehingga dari titik ini, kerja program, kan? 360 00:16:07,860 --> 00:16:09,797 Kami tahu itu melakukan persis apa yang kita inginkan. 361 00:16:09,797 --> 00:16:11,880 Dan kita tidak benar-benar harus mencetak, oh, apa 362 00:16:11,880 --> 00:16:14,430 adalah sen pada titik ini, apa koin pada saat ini. 363 00:16:14,430 --> 00:16:17,170 >> Kami terus akan melalui program. 364 00:16:17,170 --> 00:16:18,100 Langkah selesai. 365 00:16:18,100 --> 00:16:18,620 Keren. 366 00:16:18,620 --> 00:16:19,700 Kami pergi dime. 367 00:16:19,700 --> 00:16:20,200 Besar. 368 00:16:20,200 --> 00:16:22,367 Kita melihat bahwa itu diambil off $ 0,10 untuk sepeser pun. 369 00:16:22,367 --> 00:16:23,450 Dan sekarang kami memiliki dua koin. 370 00:16:23,450 --> 00:16:25,260 Itu benar. 371 00:16:25,260 --> 00:16:31,555 >> Kami pergi ke uang dan kami melihat bahwa kita sudah mendapat tersisa sen. 372 00:16:31,555 --> 00:16:32,680 Hmm, itu aneh. 373 00:16:32,680 --> 00:16:37,540 Sampai di sini di program ini, saya seharusnya telah dikurangi uang saya. 374 00:16:37,540 --> 00:16:39,400 Mungkin aku hanya tidak melakukan itu garis kanan. 375 00:16:39,400 --> 00:16:42,190 Dan sayangnya, Anda dapat melihat di sini, karena kita tahu 376 00:16:42,190 --> 00:16:44,360 bahwa kita melangkah melalui jalur 32 dan 33, 377 00:16:44,360 --> 00:16:50,560 situlah program kami benar memiliki variabel menjalankan. 378 00:16:50,560 --> 00:16:55,136 Jadi kita dapat melihat dan melihat, oh, Saya mengurangkan sen di sini, 379 00:16:55,136 --> 00:16:57,010 tapi aku tidak benar-benar menambah nilai koin saya. 380 00:16:57,010 --> 00:16:57,860 Saya menambahkan untuk sen. 381 00:16:57,860 --> 00:17:00,234 Dan aku tidak ingin menambah sen, saya ingin menambah koin. 382 00:17:00,234 --> 00:17:05,420 Jadi jika kita mengubah itu untuk koin, kami punya program kerja. 383 00:17:05,420 --> 00:17:06,730 Saya bisa menjalankan check50. 384 00:17:06,730 --> 00:17:11,063 Anda hanya dapat keluar dari GDB tepat di sini dan kemudian jalankan check50 lagi. 385 00:17:11,063 --> 00:17:11,938 Aku hanya bisa melakukan ini. 386 00:17:11,938 --> 00:17:14,822 387 00:17:14,822 --> 00:17:18,480 Saya harus membuat serakah. 388 00:17:18,480 --> 00:17:19,940 0.41. 389 00:17:19,940 --> 00:17:22,819 Dan di sini, itu printing keluar jawaban yang benar. 390 00:17:22,819 --> 00:17:26,569 >> Sehingga kalian bisa lihat, GDB adalah alat yang sangat kuat 391 00:17:26,569 --> 00:17:29,940 ketika kita memiliki begitu banyak kode terjadi dan begitu banyak variabel 392 00:17:29,940 --> 00:17:32,510 bahwa sulit bagi kami, karena manusia, untuk melacak. 393 00:17:32,510 --> 00:17:35,360 Komputer, dalam GDB debugger, memiliki kemampuan 394 00:17:35,360 --> 00:17:37,020 untuk melacak segala sesuatu. 395 00:17:37,020 --> 00:17:40,480 Aku tahu, di Visionaire, kalian mungkin mungkin telah memukul beberapa kesalahan segmentasi 396 00:17:40,480 --> 00:17:43,150 karena Anda sedang berlari di luar batas dari array Anda. 397 00:17:43,150 --> 00:17:46,510 Dalam contoh Caesar, yang persis apa yang saya telah menerapkan sini. 398 00:17:46,510 --> 00:17:50,060 >> Jadi saya lupa untuk memeriksa apa yang akan terjadi jika saya 399 00:17:50,060 --> 00:17:52,510 tidak memiliki dua argumen baris perintah. 400 00:17:52,510 --> 00:17:53,880 Aku hanya tidak dimasukkan ke dalam cek. 401 00:17:53,880 --> 00:17:57,380 Dan jadi jika saya menjalankan Debug-- saya set breakpoint saya ke kanan ada. 402 00:17:57,380 --> 00:17:58,055 Saya menjalankan Debug. 403 00:17:58,055 --> 00:18:15,880 404 00:18:15,880 --> 00:18:16,550 >> OKE. 405 00:18:16,550 --> 00:18:17,050 Ya. 406 00:18:17,050 --> 00:18:20,350 Jadi sebenarnya, GDB seharusnya telah mengatakan kepada saya ada 407 00:18:20,350 --> 00:18:22,300 adalah kesalahan segmentasi ada. 408 00:18:22,300 --> 00:18:24,883 Aku tidak tahu apa yang sedang terjadi di sana, tapi ketika aku berlari itu, 409 00:18:24,883 --> 00:18:25,590 itu bekerja. 410 00:18:25,590 --> 00:18:29,410 Ketika Anda menjalankan baris kode melalui dan GDB mungkin saja tiba-tiba berhenti pada Anda, 411 00:18:29,410 --> 00:18:31,540 naik dan melihat apa kesalahan merah. 412 00:18:31,540 --> 00:18:33,930 Ini akan memberitahu Anda, hei, Anda memiliki kesalahan segmentasi, 413 00:18:33,930 --> 00:18:38,550 yang berarti bahwa Anda mencoba untuk mengakses ruang dalam array yang tidak ada. 414 00:18:38,550 --> 00:18:39,050 Ya. 415 00:18:39,050 --> 00:18:43,280 >> Jadi dalam masalah berikutnya set minggu ini, kalian 416 00:18:43,280 --> 00:18:45,600 mungkin akan memiliki banyak variabel mengambang sekitar. 417 00:18:45,600 --> 00:18:48,560 Anda tidak akan menjadi yakin apa mereka semua berarti pada titik tertentu. 418 00:18:48,560 --> 00:18:53,560 Jadi GDB akan sangat membantu Anda dalam mencari apa mereka semua menyamai 419 00:18:53,560 --> 00:18:55,940 dan mampu melihat bahwa secara visual. 420 00:18:55,940 --> 00:19:01,995 Apakah ada yang bingung tentang bagaimana semua itu bekerja? 421 00:19:01,995 --> 00:19:02,495 Keren. 422 00:19:02,495 --> 00:19:10,121 423 00:19:10,121 --> 00:19:10,620 Baiklah. 424 00:19:10,620 --> 00:19:14,260 Jadi setelah itu, kita akan menyelam tepat 425 00:19:14,260 --> 00:19:17,562 ke empat yang berbeda jenis macam untuk minggu ini. 426 00:19:17,562 --> 00:19:19,520 Berapa banyak dari Anda, pertama tama, sebelum kita mulai, 427 00:19:19,520 --> 00:19:23,020 telah membaca seluruh spec untuk pset3? 428 00:19:23,020 --> 00:19:23,824 OKE. 429 00:19:23,824 --> 00:19:24,740 Aku bangga kalian. 430 00:19:24,740 --> 00:19:29,110 Itu seperti setengah dari kelas, yang secara signifikan lebih dari terakhir kali. 431 00:19:29,110 --> 00:19:33,950 >> Jadi itu bagus, karena ketika kita berbicara tentang isi 432 00:19:33,950 --> 00:19:36,170 di lecture-- atau menyesal, di section-- Saya suka 433 00:19:36,170 --> 00:19:38,210 untuk berhubungan banyak yang kembali ke apa pset adalah 434 00:19:38,210 --> 00:19:40,210 dan bagaimana Anda ingin menerapkan bahwa dalam pset Anda. 435 00:19:40,210 --> 00:19:42,400 Jadi, jika Anda datang memiliki membaca spec, itu akan 436 00:19:42,400 --> 00:19:45,510 menjadi jauh lebih mudah bagi Anda untuk memahami apa yang saya bicarakan ketika saya mengatakan, 437 00:19:45,510 --> 00:19:48,720 oh hey, mungkin ini benar-benar tempat yang baik untuk melaksanakan semacam ini. 438 00:19:48,720 --> 00:19:52,870 Jadi bagi anda yang telah membaca spek tahu bahwa, sebagai bagian dari pset Anda, 439 00:19:52,870 --> 00:19:54,900 Anda akan harus menulis jenis macam. 440 00:19:54,900 --> 00:19:58,670 Jadi ini mungkin sangat membantu untuk banyak hari ini. 441 00:19:58,670 --> 00:20:01,760 >> Jadi kita akan mulai dengan, dasarnya, jenis yang paling sederhana 442 00:20:01,760 --> 00:20:04,580 semacam, semacam seleksi. 443 00:20:04,580 --> 00:20:06,800 Algoritma khas untuk bagaimana kita akan pergi tentang ini 444 00:20:06,800 --> 00:20:10,460 is-- David pergi melalui ini semua di kuliah, jadi saya cepat akan bergerak sepanjang 445 00:20:10,460 --> 00:20:13,900 sini-dasarnya, Anda memiliki sebuah array nilai. 446 00:20:13,900 --> 00:20:17,170 Dan kemudian Anda menemukan Nilai disortir terkecil 447 00:20:17,170 --> 00:20:20,200 dan Anda swap yang nilai dengan nilai disortir pertama. 448 00:20:20,200 --> 00:20:22,700 Dan kemudian Anda hanya terus mengulangi dengan sisa daftar Anda. 449 00:20:22,700 --> 00:20:25,740 >> Dan inilah penjelasan visual yang bagaimana yang akan bekerja. 450 00:20:25,740 --> 00:20:30,460 Jadi misalnya, jika kita mulai dengan array lima elemen, indeks 451 00:20:30,460 --> 00:20:35,910 0-4, dengan 3, 5, 2, 6, dan 4 nilai-nilai ditempatkan di array-- sehingga sekarang, 452 00:20:35,910 --> 00:20:38,530 kami hanya akan menganggap bahwa mereka semua disortir 453 00:20:38,530 --> 00:20:41,130 karena kita belum diuji sebaliknya. 454 00:20:41,130 --> 00:20:44,130 >> Jadi bagaimana semacam seleksi akan kerja adalah bahwa hal itu akan pertama 455 00:20:44,130 --> 00:20:46,800 dijalankan melalui keseluruhan yang dari array disortir. 456 00:20:46,800 --> 00:20:49,120 Ini akan memilih nilai terkecil. 457 00:20:49,120 --> 00:20:51,750 Dalam hal ini, 3, tepat sekarang, adalah yang terkecil. 458 00:20:51,750 --> 00:20:52,680 Sampai ke 5. 459 00:20:52,680 --> 00:20:55,620 Tidak, 5 tidak lebih besar than-- atau maaf, tidak kurang than-- 3. 460 00:20:55,620 --> 00:20:57,779 Jadi nilai minimum masih 3. 461 00:20:57,779 --> 00:20:58,695 Dan kemudian Anda bisa 2. 462 00:20:58,695 --> 00:21:00,990 Komputer melihat, oh, 2 kurang dari 3. 463 00:21:00,990 --> 00:21:02,750 2 sekarang harus nilai minimum. 464 00:21:02,750 --> 00:21:06,630 Dan 2 swap dengan nilai pertama. 465 00:21:06,630 --> 00:21:10,702 >> Jadi setelah satu lulus, kita memang melihat bahwa 2 dan 3 tertukar. 466 00:21:10,702 --> 00:21:13,910 Dan kami hanya akan terus melakukan ini lagi dengan sisa array. 467 00:21:13,910 --> 00:21:17,660 Jadi kita akan jalankan melalui empat indeks terakhir array. 468 00:21:17,660 --> 00:21:20,670 Kita akan melihat bahwa 3 adalah nilai minimum berikutnya. 469 00:21:20,670 --> 00:21:23,240 Jadi kita akan menukar itu dengan 4. 470 00:21:23,240 --> 00:21:26,900 Dan kemudian kita hanya akan terus berjalan melalui sampai, akhirnya, Anda 471 00:21:26,900 --> 00:21:33,730 sampai ke array diurutkan di mana 2, 3, 4, 5, dan 6 semua diurutkan. 472 00:21:33,730 --> 00:21:37,530 Apakah setiap orang memahami logika bagaimana semacam seleksi bekerja? 473 00:21:37,530 --> 00:21:39,669 >> Anda hanya memiliki semacam dari nilai minimum. 474 00:21:39,669 --> 00:21:41,210 Anda melacak apa itu. 475 00:21:41,210 --> 00:21:45,170 Dan setiap kali Anda menemukannya, Anda swap dengan nilai pertama di array-- yang 476 00:21:45,170 --> 00:21:48,740 atau, bukan value-- pertama nilai berikutnya dalam array. 477 00:21:48,740 --> 00:21:50,150 Keren. 478 00:21:50,150 --> 00:21:55,460 >> Sehingga kalian jenis melihat dari sekilas singkat, 479 00:21:55,460 --> 00:21:58,450 kita akan pseudocode ini. 480 00:21:58,450 --> 00:22:02,510 Jadi jika kalian di belakang ingin membentuk kelompok, semua orang di meja 481 00:22:02,510 --> 00:22:06,170 dapat membentuk mitra kecil, aku akan untuk memberikan orang-orang seperti tiga menit 482 00:22:06,170 --> 00:22:08,190 hanya berbicara melalui logika, dalam bahasa Inggris, 483 00:22:08,190 --> 00:22:14,161 bagaimana kita mungkin bisa menerapkan pseudocode untuk menulis semacam seleksi. 484 00:22:14,161 --> 00:22:14,910 Dan ada permen. 485 00:22:14,910 --> 00:22:16,118 Silahkan datang dan mendapatkan permen. 486 00:22:16,118 --> 00:22:19,520 Jika Anda berada di belakang dan Anda ingin permen, aku bisa melemparkan permen pada Anda. 487 00:22:19,520 --> 00:22:22,850 Sebenarnya, lakukan keren you--. 488 00:22:22,850 --> 00:22:23,552 Oh maaf. 489 00:22:23,552 --> 00:22:26,751 490 00:22:26,751 --> 00:22:27,250 OKE. 491 00:22:27,250 --> 00:25:23,880 492 00:25:23,880 --> 00:25:27,140 >> Jadi jika kita ingin, sebagai kelas, menulis pseudocode 493 00:25:27,140 --> 00:25:30,466 bagaimana mungkin satu pendekatan masalah ini, hanya merasa bebas. 494 00:25:30,466 --> 00:25:32,340 Aku hanya akan pergi berkeliling dan, dalam rangka, meminta kelompok 495 00:25:32,340 --> 00:25:35,065 untuk baris berikutnya apa yang harus kita lakukan. 496 00:25:35,065 --> 00:25:37,840 Jadi jika kalian ingin memulai off, apa hal pertama 497 00:25:37,840 --> 00:25:40,600 yang harus dilakukan ketika Anda mencoba untuk menerapkan cara untuk memecahkan program ini 498 00:25:40,600 --> 00:25:43,480 selektif memilah daftar? 499 00:25:43,480 --> 00:25:46,349 Mari kita asumsikan kita memiliki sebuah array, oke? 500 00:25:46,349 --> 00:25:49,088 >> AUDIENCE: Anda ingin membuat beberapa semacam [tak terdengar] bahwa Anda 501 00:25:49,088 --> 00:25:50,420 berjalan melalui seluruh array Anda. 502 00:25:50,420 --> 00:25:51,128 >> ANDI PENG: Benar. 503 00:25:51,128 --> 00:25:54,100 Jadi Anda akan ingin beralih melalui setiap ruang, kan? 504 00:25:54,100 --> 00:26:05,490 Sangat bagus. 505 00:26:05,490 --> 00:26:08,600 Jika kalian ingin memberi saya selanjutnya line-- yeah, di belakang. 506 00:26:08,600 --> 00:26:11,414 507 00:26:11,414 --> 00:26:13,290 >> AUDIENCE: Memeriksa mereka semua untuk yang terkecil. 508 00:26:13,290 --> 00:26:14,248 >> ANDI PENG: Ada kita pergi. 509 00:26:14,248 --> 00:26:17,438 Jadi kami ingin pergi melalui dan memeriksa untuk melihat apa nilai minimum, kan? 510 00:26:17,438 --> 00:26:22,110 511 00:26:22,110 --> 00:26:24,840 Aku akan menyingkat ke "min." 512 00:26:24,840 --> 00:26:27,658 Apa yang kalian ingin lakukan setelah Anda telah menemukan nilai minimum? 513 00:26:27,658 --> 00:26:28,533 >> AUDIENCE: [tidak terdengar] 514 00:26:28,533 --> 00:26:29,942 515 00:26:29,942 --> 00:26:33,150 ANDI PENG: Jadi Anda akan ingin beralih dengan yang pertama dari array, 516 00:26:33,150 --> 00:26:33,650 benar? 517 00:26:33,650 --> 00:26:45,120 518 00:26:45,120 --> 00:26:46,850 Itu awalnya, aku akan mengatakan. 519 00:26:46,850 --> 00:26:47,220 Baiklah. 520 00:26:47,220 --> 00:26:50,386 Jadi sekarang bahwa Anda telah bertukar pertama satu, apa yang Anda ingin lakukan setelah itu? 521 00:26:50,386 --> 00:26:54,840 Jadi sekarang kita tahu bahwa satu ini di sini harus menjadi nilai terkecil, kan? 522 00:26:54,840 --> 00:26:58,310 Maka Anda memiliki sisa tambahan dari array yang tidak dipisahkan. 523 00:26:58,310 --> 00:27:01,569 Jadi apa yang ingin Anda lakukan di sini, jika Anda orang ingin memberikan baris berikutnya? 524 00:27:01,569 --> 00:27:04,610 AUDIENCE: Jadi Anda ingin iterate melalui sisa array. 525 00:27:04,610 --> 00:27:05,276 ANDI PENG: Ya. 526 00:27:05,276 --> 00:27:09,857 Dan jadi apa iterasi melalui jenis menyiratkan kita mungkin perlu? 527 00:27:09,857 --> 00:27:10,440 Jenis of-- apa 528 00:27:10,440 --> 00:27:12,057 >> AUDIENCE: Oh, variabel tambahan? 529 00:27:12,057 --> 00:27:13,890 ANDI PENG: Mungkin lain untuk loop, kan? 530 00:27:13,890 --> 00:27:28,914 Jadi kita mungkin akan ingin iterate through-- besar. 531 00:27:28,914 --> 00:27:31,830 Dan kemudian Anda akan kembali dan mungkin memeriksa minimum lagi, 532 00:27:31,830 --> 00:27:32,100 benar? 533 00:27:32,100 --> 00:27:34,975 Dan Anda akan terus mengulangi ini, karena loop hanya akan 534 00:27:34,975 --> 00:27:36,010 untuk terus berjalan, kan? 535 00:27:36,010 --> 00:27:39,190 >> Sehingga kalian bisa lihat, kita hanya memiliki pseudo umum 536 00:27:39,190 --> 00:27:41,480 bagaimana kita ingin program ini untuk mencari. 537 00:27:41,480 --> 00:27:46,646 Iterate ini di sini, apa yang kita lakukan biasanya perlu menulis dalam kode kami 538 00:27:46,646 --> 00:27:49,270 jika kita ingin iterate melalui array, apa jenis struktur? 539 00:27:49,270 --> 00:27:51,030 Saya pikir Christabel sudah mengatakan ini sebelumnya. 540 00:27:51,030 --> 00:27:51,500 >> AUDIENCE: A untuk loop. 541 00:27:51,500 --> 00:27:52,160 >> ANDI PENG: A untuk loop? 542 00:27:52,160 --> 00:27:52,770 Tepat. 543 00:27:52,770 --> 00:27:56,060 Jadi ini mungkin akan menjadi untuk loop. 544 00:27:56,060 --> 00:27:59,240 Apa cek di sini akan menyiratkan? 545 00:27:59,240 --> 00:28:02,536 Biasanya, jika Anda ingin memeriksa jika ada sesuatu yang sesuatu else-- 546 00:28:02,536 --> 00:28:03,270 >> AUDIENCE: Jika. 547 00:28:03,270 --> 00:28:06,790 >> ANDI PENG: Sebuah jika, kan? 548 00:28:06,790 --> 00:28:10,790 Dan kemudian swap sini, kita akan pergi kemudian, karena David 549 00:28:10,790 --> 00:28:12,770 pergi melalui bahwa dalam kuliah juga. 550 00:28:12,770 --> 00:28:14,580 Dan kemudian iterate kedua implies-- 551 00:28:14,580 --> 00:28:15,120 >> AUDIENCE: lain untuk loop. 552 00:28:15,120 --> 00:28:16,745 >> ANDI PENG: --another untuk loop, persis. 553 00:28:16,745 --> 00:28:19,870 554 00:28:19,870 --> 00:28:22,000 Jadi jika kita cari ini benar, kita 555 00:28:22,000 --> 00:28:24,680 dapat melihat bahwa kita mungkin akan membutuhkan bersarang untuk loop 556 00:28:24,680 --> 00:28:28,330 dengan pernyataan kondisional dalam ada dan kemudian sepotong sebenarnya kode itu 557 00:28:28,330 --> 00:28:31,360 akan menukar nilai-nilai. 558 00:28:31,360 --> 00:28:35,980 Jadi saya baru saja umumnya ditulis kode pseudo sini. 559 00:28:35,980 --> 00:28:38,910 Dan kemudian kita benar-benar akan secara fisik, sebagai kelas, 560 00:28:38,910 --> 00:28:40,700 mencoba untuk menerapkan hari ini. 561 00:28:40,700 --> 00:28:42,486 Mari kita kembali ke IDE ini. 562 00:28:42,486 --> 00:28:49,243 563 00:28:49,243 --> 00:28:50,230 >> Uh oh. 564 00:28:50,230 --> 00:28:51,754 Kenapa begitu not-- ada itu. 565 00:28:51,754 --> 00:28:52,253 OKE. 566 00:28:52,253 --> 00:28:55,834 567 00:28:55,834 --> 00:28:57,500 Maaf, saya mencoba untuk memperbesar sedikit lebih. 568 00:28:57,500 --> 00:28:59,310 Di sana kami pergi. 569 00:28:59,310 --> 00:29:05,060 Semua yang saya lakukan di sini adalah saya buat sebuah program yang disebut "seleksi / sort.c." 570 00:29:05,060 --> 00:29:10,860 Saya telah membuat sebuah array dari sembilan nilai-nilai, 4, 8, 2, 1, 6, 9, 7, 5, 3. 571 00:29:10,860 --> 00:29:14,370 Saat ini, yang Anda bisa lihat, mereka unordered. 572 00:29:14,370 --> 00:29:17,880 n akan menjadi nomor yang memberitahu Anda jumlah nilai 573 00:29:17,880 --> 00:29:18,920 Anda memiliki dalam array Anda. 574 00:29:18,920 --> 00:29:20,670 Dalam hal ini, kita memiliki sembilan nilai. 575 00:29:20,670 --> 00:29:23,760 Dan saya baru saja mendapat untuk loop di sini yang mencetak array disortir. 576 00:29:23,760 --> 00:29:28,370 >> Dan pada akhirnya, saya juga punya untuk loop yang hanya print keluar lagi. 577 00:29:28,370 --> 00:29:32,070 Jadi secara teoritis, jika program ini bekerja dengan benar, pada akhirnya, 578 00:29:32,070 --> 00:29:35,670 Anda akan melihat dicetak untuk loop di mana 1, 2, 3, 4, 5, 6, 7, 8, 579 00:29:35,670 --> 00:29:39,310 9 semua benar agar. 580 00:29:39,310 --> 00:29:43,410 >> Jadi kita punya pseudo kami di sini. 581 00:29:43,410 --> 00:29:46,090 Apakah ada yang ingin to-- aku hanya akan pergi meminta volunteers-- 582 00:29:46,090 --> 00:29:49,540 ceritakan apa untuk mengetik jika kami ingin, pertama, hanya iterate 583 00:29:49,540 --> 00:29:52,840 melalui awal array ini? 584 00:29:52,840 --> 00:29:55,204 Apa baris kode saya mungkin akan butuhkan di sini? 585 00:29:55,204 --> 00:29:56,990 >> AUDIENCE: [tidak terdengar] 586 00:29:56,990 --> 00:29:59,010 >> ANDI PENG: Ya, merasa gratis to-- maaf, Anda 587 00:29:59,010 --> 00:30:02,318 tidak harus berdiri nuansa up-- bebas untuk meningkatkan suara Anda sedikit. 588 00:30:02,318 --> 00:30:08,190 >> AUDIENCE: Untuk int i sama 0-- 589 00:30:08,190 --> 00:30:10,690 >> ANDI PENG: Ya, baik. 590 00:30:10,690 --> 00:30:15,220 >> AUDIENCE: i kurang dari panjang array. 591 00:30:15,220 --> 00:30:19,630 >> ANDI PENG: Jadi perlu keberatan di sini, karena kami 592 00:30:19,630 --> 00:30:23,060 tidak memiliki fungsi yang memberitahu kita panjang array, 593 00:30:23,060 --> 00:30:25,790 kita sudah memiliki nilai yang menyimpan itu. 594 00:30:25,790 --> 00:30:27,920 Benar? 595 00:30:27,920 --> 00:30:31,010 Satu hal yang perlu di mind-- dalam array 596 00:30:31,010 --> 00:30:33,940 dari sembilan nilai, apa indeks? 597 00:30:33,940 --> 00:30:38,720 Anggap saja array ini adalah 0-3. 598 00:30:38,720 --> 00:30:41,500 Anda melihat bahwa yang terakhir Indeks sebenarnya 3. 599 00:30:41,500 --> 00:30:45,530 Ini bukan 4, meskipun ada empat nilai dalam array. 600 00:30:45,530 --> 00:30:49,866 >> Jadi di sini, kita harus sangat berhati-hati apa kondisi kita untuk panjang 601 00:30:49,866 --> 00:30:50,490 akan menjadi. 602 00:30:50,490 --> 00:30:51,948 >> AUDIENCE: Bukankah n minus 1? 603 00:30:51,948 --> 00:30:54,440 ANDI PENG: Ini akan n minus 1, persis. 604 00:30:54,440 --> 00:30:57,379 Apakah itu masuk akal, mengapa itu n minus 1, setiap orang? 605 00:30:57,379 --> 00:30:58,920 Itu karena array adalah nol-diindeks. 606 00:30:58,920 --> 00:31:02,010 Mereka mulai 0 dan berjalan sampai n minus 1. 607 00:31:02,010 --> 00:31:03,210 Ya, itu sedikit rumit. 608 00:31:03,210 --> 00:31:03,730 OKE. 609 00:31:03,730 --> 00:31:05,929 Dan kemudian-- 610 00:31:05,929 --> 00:31:08,054 AUDIENCE: Isnt'1 yang sudah diurus meskipun, 611 00:31:08,054 --> 00:31:11,400 dengan hanya tidak mengatakan "kurang dari atau sama dengan "dan hanya mengatakan" kurang dari? " 612 00:31:11,400 --> 00:31:13,108 >> ANDI PENG: Itu Pertanyaan benar-benar baik. 613 00:31:13,108 --> 00:31:13,630 Jadi iya. 614 00:31:13,630 --> 00:31:17,410 Tapi juga, cara yang kami melaksanakan hak memeriksa, 615 00:31:17,410 --> 00:31:19,120 Anda perlu membandingkan dua nilai. 616 00:31:19,120 --> 00:31:21,009 Jadi Anda benar-benar ingin meninggalkan "untuk" kosong. 617 00:31:21,009 --> 00:31:23,050 Karena jika Anda membandingkan yang satu ini, Anda tidak akan 618 00:31:23,050 --> 00:31:25,530 memiliki apa-apa setelah itu untuk membandingkan, kan? 619 00:31:25,530 --> 00:31:27,460 Ya. 620 00:31:27,460 --> 00:31:29,297 Jadi i ++. 621 00:31:29,297 --> 00:31:30,380 Mari menambahkan kurung kami di. 622 00:31:30,380 --> 00:31:30,880 Whoops. 623 00:31:30,880 --> 00:31:33,950 624 00:31:33,950 --> 00:31:34,710 Besar. 625 00:31:34,710 --> 00:31:39,117 Jadi kita memiliki awal loop luar kita. 626 00:31:39,117 --> 00:31:41,450 Jadi sekarang kita mungkin ingin membuat variabel untuk menjaga 627 00:31:41,450 --> 00:31:43,085 track dari nilai terkecil, kan? 628 00:31:43,085 --> 00:31:45,751 Apakah ada yang ingin memberi saya baris kode yang akan melakukan itu? 629 00:31:45,751 --> 00:31:48,700 630 00:31:48,700 --> 00:31:53,570 Apa yang kita butuhkan jika kita akan ingin menyimpan sesuatu? 631 00:31:53,570 --> 00:31:55,047 >> Benar. 632 00:31:55,047 --> 00:31:57,630 Mungkin nama yang lebih baik untuk itu akan be-- "temp" benar-benar works-- 633 00:31:57,630 --> 00:32:00,655 mungkin lebih tepat bernama akan, jika kita ingin value-- terkecil 634 00:32:00,655 --> 00:32:01,624 >> AUDIENCE: Min. 635 00:32:01,624 --> 00:32:02,790 ANDI PENG: min, ada kita pergi. 636 00:32:02,790 --> 00:32:05,230 min akan baik. 637 00:32:05,230 --> 00:32:08,340 Dan jadi di sini, apa yang kita lakukan ingin menginisialisasi ke? 638 00:32:08,340 --> 00:32:09,620 Ini adalah sedikit rumit. 639 00:32:09,620 --> 00:32:13,580 Karena sekarang di mulai dari array ini, 640 00:32:13,580 --> 00:32:15,730 Anda belum melihat apa-apa, kan? 641 00:32:15,730 --> 00:32:19,200 Jadi apa, secara otomatis, jika kami hanya pada i sama dengan 0, 642 00:32:19,200 --> 00:32:22,302 apa yang kita ingin menginisialisasi nilai minimum pertama kita ke? 643 00:32:22,302 --> 00:32:22,802 AUDIENCE: i. 644 00:32:22,802 --> 00:32:24,790 ANDI PENG: i, persis. 645 00:32:24,790 --> 00:32:27,040 Christabel, mengapa kita ingin untuk menginisialisasi ke saya? 646 00:32:27,040 --> 00:32:28,510 >> AUDIENCE: Karena, baik, kita mulai dengan 0. 647 00:32:28,510 --> 00:32:31,660 Jadi karena kita punya apa-apa untuk membandingkan untuk, minimal akan berakhir menjadi 0. 648 00:32:31,660 --> 00:32:32,451 >> ANDI PENG: Tepat. 649 00:32:32,451 --> 00:32:34,400 Jadi dia tepat. 650 00:32:34,400 --> 00:32:36,780 Karena kita tidak benar-benar memandang apa pun, 651 00:32:36,780 --> 00:32:38,680 kita tidak tahu apa nilai minimum kami adalah. 652 00:32:38,680 --> 00:32:41,960 Kami hanya ingin menginisialisasi ke i, yang, saat ini, ada di sini. 653 00:32:41,960 --> 00:32:44,750 Dan seperti yang kita terus bergerak ke bawah array ini, 654 00:32:44,750 --> 00:32:48,122 kita akan melihat bahwa, dengan masing-masing tambahan lulus, saya akan menambahkan. 655 00:32:48,122 --> 00:32:49,830 Dan pada saat itu, i mungkin akan 656 00:32:49,830 --> 00:32:52,329 ingin menjadi minimum, karena itu akan menjadi apa pun 657 00:32:52,329 --> 00:32:54,520 adalah awal dari array disortir. 658 00:32:54,520 --> 00:32:55,270 Keren. 659 00:32:55,270 --> 00:32:58,720 >> Jadi sekarang kita ingin menambahkan untuk loop di sini itu 660 00:32:58,720 --> 00:33:03,225 akan iterate melalui disortir, atau sisa array ini. 661 00:33:03,225 --> 00:33:05,808 Apakah ada yang ingin memberi saya baris kode yang akan melakukan itu? 662 00:33:05,808 --> 00:33:08,870 663 00:33:08,870 --> 00:33:11,330 Hint-- apa yang kita butuhkan di sini? 664 00:33:11,330 --> 00:33:17,320 665 00:33:17,320 --> 00:33:18,820 Apa yang akan masuk ini untuk loop? 666 00:33:18,820 --> 00:33:19,465 Ya. 667 00:33:19,465 --> 00:33:21,590 AUDIENCE: Jadi kita akan ingin memiliki bilangan bulat yang berbeda, 668 00:33:21,590 --> 00:33:25,080 karena kita berjalan melalui sisanya dari array bukan saya, jadi mungkin 669 00:33:25,080 --> 00:33:25,760 j. 670 00:33:25,760 --> 00:33:27,301 >> ANDI PENG: Ya, j terdengar baik padaku. 671 00:33:27,301 --> 00:33:27,850 Sama? 672 00:33:27,850 --> 00:33:33,930 >> AUDIENCE: Jadi akan saya ditambah 1, karena Anda mulai di nilai berikutnya. 673 00:33:33,930 --> 00:33:40,395 Dan kemudian ke end-- jadi lagi, j adalah kurang dari n minus 1, dan kemudian j ++. 674 00:33:40,395 --> 00:33:41,103 ANDI PENG: Great. 675 00:33:41,103 --> 00:33:48,510 676 00:33:48,510 --> 00:33:52,750 >> Dan kemudian di sini, kita akan ingin untuk memeriksa untuk melihat apakah kondisi kita terpenuhi, 677 00:33:52,750 --> 00:33:53,250 benar? 678 00:33:53,250 --> 00:33:55,740 Karena Anda ingin mengubah nilai minimum 679 00:33:55,740 --> 00:33:58,700 jika itu benar-benar lebih kecil dari apa yang Anda membandingkannya dengan, kan? 680 00:33:58,700 --> 00:34:01,146 Jadi apa yang akan kita inginkan dalam sini? 681 00:34:01,146 --> 00:34:04,160 682 00:34:04,160 --> 00:34:04,897 Periksa untuk melihat. 683 00:34:04,897 --> 00:34:06,730 Apa jenis pernyataan kita mungkin akan 684 00:34:06,730 --> 00:34:08,389 ti ingin menggunakan jika kita ingin memeriksa sesuatu? 685 00:34:08,389 --> 00:34:09,360 >> AUDIENCE: Sebuah jika pernyataan. 686 00:34:09,360 --> 00:34:10,485 >> ANDI PENG: Sebuah jika pernyataan. 687 00:34:10,485 --> 00:34:13,155 Jadi if-- dan apa yang akan menjadi kondisi yang kita inginkan dalam 688 00:34:13,155 --> 00:34:13,988 dari jika pernyataan kita? 689 00:34:13,988 --> 00:34:18,255 690 00:34:18,255 --> 00:34:22,960 >> AUDIENCE: Jika nilai j kurang dari nilai Aku-- 691 00:34:22,960 --> 00:34:24,600 >> ANDI PENG: Tepat. 692 00:34:24,600 --> 00:34:27,480 Jadi if-- jadi array ini disebut "array." 693 00:34:27,480 --> 00:34:27,980 Besar. 694 00:34:27,980 --> 00:34:30,465 Jadi jika array-- apa itu? 695 00:34:30,465 --> 00:34:31,090 Katakan itu lagi. 696 00:34:31,090 --> 00:34:39,590 >> AUDIENCE: Jika array-j kurang dari array i, maka kita akan mengubah min. 697 00:34:39,590 --> 00:34:41,590 Jadi min akan j. 698 00:34:41,590 --> 00:34:44,590 699 00:34:44,590 --> 00:34:47,249 >> ANDI PENG: Apakah itu masuk akal? 700 00:34:47,249 --> 00:34:48,670 OKE. 701 00:34:48,670 --> 00:34:52,929 Dan sekarang di sini, kita benar-benar ingin menerapkan swap, kan? 702 00:34:52,929 --> 00:34:58,285 Jadi ingat, dalam kuliah, bahwa David, ketika ia berusaha untuk swap the-- apa yang 703 00:34:58,285 --> 00:34:59,996 jus jeruk itu-- dan milk-- 704 00:34:59,996 --> 00:35:01,150 >> AUDIENCE: Itu kotor. 705 00:35:01,150 --> 00:35:02,816 >> ANDI PENG: Ya, itu agak kotor. 706 00:35:02,816 --> 00:35:05,310 Tapi itu cukup bagus Konsep menunjukkan waktu. 707 00:35:05,310 --> 00:35:08,430 Jadi pikirkan nilai-nilai Anda di sini. 708 00:35:08,430 --> 00:35:10,794 Anda punya sebuah array min, array i, 709 00:35:10,794 --> 00:35:12,460 atau apa pun kita mencoba untuk swap sini. 710 00:35:12,460 --> 00:35:15,310 Dan Anda mungkin tidak dapat tuangkan ke satu sama lain pada saat yang sama, kan? 711 00:35:15,310 --> 00:35:17,180 Jadi apa yang akan kita perlu untuk membuat di sini 712 00:35:17,180 --> 00:35:19,126 untuk menukar nilai-nilai benar? 713 00:35:19,126 --> 00:35:19,820 >> AUDIENCE: Sebuah variabel sementara. 714 00:35:19,820 --> 00:35:21,370 >> ANDI PENG: Sebuah variabel sementara. 715 00:35:21,370 --> 00:35:22,570 Jadi mari kita lakukan int temp. 716 00:35:22,570 --> 00:35:25,681 Lihat, ini akan menjadi lebih baik waktu to-- whoa, apa itu? 717 00:35:25,681 --> 00:35:26,180 OKE. 718 00:35:26,180 --> 00:35:29,800 Jadi ini akan menjadi lebih baik waktu untuk nama variabel "temp." 719 00:35:29,800 --> 00:35:30,730 Jadi mari kita lakukan int temp. 720 00:35:30,730 --> 00:35:32,563 Apa yang akan kita mengatur suhu sama dengan di sini? 721 00:35:32,563 --> 00:35:34,752 722 00:35:34,752 --> 00:35:35,335 AUDIENCE: Min? 723 00:35:35,335 --> 00:35:38,508 724 00:35:38,508 --> 00:35:39,716 ANDI PENG: Ini agak rumit. 725 00:35:39,716 --> 00:35:43,110 726 00:35:43,110 --> 00:35:44,880 Ini sebenarnya tidak masalah pada akhirnya. 727 00:35:44,880 --> 00:35:47,690 Tidak peduli apa Agar Anda memilih untuk swap di 728 00:35:47,690 --> 00:35:50,862 asalkan Anda memastikan Anda melacak apa yang Anda swapping. 729 00:35:50,862 --> 00:35:52,250 >> AUDIENCE: Ini bisa menjadi array i. 730 00:35:52,250 --> 00:35:53,666 >> ANDI PENG: Ya, mari kita lakukan array i. 731 00:35:53,666 --> 00:35:55,950 732 00:35:55,950 --> 00:35:59,305 Dan kemudian apa baris berikutnya kode kita ingin miliki di sini? 733 00:35:59,305 --> 00:36:00,680 AUDIENCE: array-i sama dengan array j. 734 00:36:00,680 --> 00:36:07,154 735 00:36:07,154 --> 00:36:08,070 ANDI PENG: Dan terakhir? 736 00:36:08,070 --> 00:36:12,070 AUDIENCE: array-j sama dengan berbagai-i. 737 00:36:12,070 --> 00:36:14,525 AUDIENCE: Atau array j equals array temp-- atau, temp. 738 00:36:14,525 --> 00:36:17,135 739 00:36:17,135 --> 00:36:19,430 >> ANDI PENG: OK. 740 00:36:19,430 --> 00:36:21,510 Jadi mari kita jalankan ini dan melihat jika itu akan bekerja. 741 00:36:21,510 --> 00:36:37,520 742 00:36:37,520 --> 00:36:39,335 Dimana yang terjadi? 743 00:36:39,335 --> 00:36:40,210 Oh, itu masalah. 744 00:36:40,210 --> 00:36:44,320 Lihat, pada baris 40, kita mencoba untuk menggunakan array j? 745 00:36:44,320 --> 00:36:47,022 Tapi mana j hanya ada di? 746 00:36:47,022 --> 00:36:48,402 >> AUDIENCE: Dalam untuk loop. 747 00:36:48,402 --> 00:36:49,110 ANDI PENG: Benar. 748 00:36:49,110 --> 00:36:51,730 Jadi apa yang akan kita lakukan? 749 00:36:51,730 --> 00:36:53,170 >> AUDIENCE: Tentukan luar the-- 750 00:36:53,170 --> 00:36:57,777 751 00:36:57,777 --> 00:37:00,610 AUDIENCE: Ya, saya rasa Anda harus menggunakan lain jika pernyataan, kan? 752 00:37:00,610 --> 00:37:05,230 Jadi seperti, jika minimum-- yang semua benar, biarkan aku berpikir. 753 00:37:05,230 --> 00:37:08,170 754 00:37:08,170 --> 00:37:09,990 >> ANDI PENG: Guys, coba untuk melihat Mari 755 00:37:09,990 --> 00:37:11,270 lihat, apa yang bisa kita lakukan di sini? 756 00:37:11,270 --> 00:37:11,811 >> AUDIENCE: OK. 757 00:37:11,811 --> 00:37:15,900 Jadi jika minimum tidak sama j-- jadi jika minimum masih Aku-- 758 00:37:15,900 --> 00:37:17,570 maka kita tidak perlu menukar. 759 00:37:17,570 --> 00:37:22,450 760 00:37:22,450 --> 00:37:24,712 >> ANDI PENG: Apakah itu sama saya? 761 00:37:24,712 --> 00:37:25,920 Apa yang Anda ingin katakan di sini? 762 00:37:25,920 --> 00:37:30,494 >> AUDIENCE: Atau ya, jika minimum tidak saya tidak sama, ya. 763 00:37:30,494 --> 00:37:39,627 764 00:37:39,627 --> 00:37:40,210 ANDI PENG: OK. 765 00:37:40,210 --> 00:37:42,040 Nah yang memecahkan, jenis, masalah kita. 766 00:37:42,040 --> 00:37:47,265 Tapi itu masih tidak memecahkan masalah apa yang terjadi jika j-- sejak j 767 00:37:47,265 --> 00:37:49,890 tidak ada di luar itu, apa Anda yang ingin kita lakukan dengan itu? 768 00:37:49,890 --> 00:37:50,698 Mendeklarasikan luar? 769 00:37:50,698 --> 00:37:59,410 770 00:37:59,410 --> 00:38:02,730 Mari kita coba jalankan ini. 771 00:38:02,730 --> 00:38:04,435 Uh oh. 772 00:38:04,435 --> 00:38:06,200 Semacam kami tidak bekerja. 773 00:38:06,200 --> 00:38:10,060 >> Seperti yang Anda lihat, kami awal Array memiliki nilai-nilai. 774 00:38:10,060 --> 00:38:14,800 Dan setelah itu harus memiliki berada di 1, 2, 3, 4, 5, 6, 7, 8, 9. 775 00:38:14,800 --> 00:38:15,530 Ini tidak bekerja. 776 00:38:15,530 --> 00:38:16,030 Ahh. 777 00:38:16,030 --> 00:38:17,184 Apa yang kita lakukan? 778 00:38:17,184 --> 00:38:17,850 AUDIENCE: Debug. 779 00:38:17,850 --> 00:38:21,787 780 00:38:21,787 --> 00:38:23,370 ANDI PENG: Baiklah, kita dapat mencoba itu. 781 00:38:23,370 --> 00:38:25,030 Kami bisa debug. 782 00:38:25,030 --> 00:38:26,042 Zoom out sedikit. 783 00:38:26,042 --> 00:38:31,177 784 00:38:31,177 --> 00:38:33,656 Mari kita mengatur breakpoint kami. 785 00:38:33,656 --> 00:38:37,280 Mari kita pergi like-- OK. 786 00:38:37,280 --> 00:38:40,444 >> Jadi karena kita sudah tahu bahwa garis-garis ini, 15 sampai 22, 787 00:38:40,444 --> 00:38:43,610 yang working-- karena semua saya lakukan adalah hanya iterasi melalui dan printing-- 788 00:38:43,610 --> 00:38:45,406 Aku bisa pergi ke depan dan melewatkan itu. 789 00:38:45,406 --> 00:38:47,280 Mari kita mulai dari garis 25. 790 00:38:47,280 --> 00:38:48,712 Oop, biarkan aku menyingkirkan itu. 791 00:38:48,712 --> 00:38:51,598 792 00:38:51,598 --> 00:38:54,057 >> AUDIENCE: Jadi breakpoint ini mana debugging dimulai? 793 00:38:54,057 --> 00:38:54,890 ANDI PENG: Atau berhenti. 794 00:38:54,890 --> 00:38:55,670 AUDIENCE: Atau berhenti. 795 00:38:55,670 --> 00:38:55,930 ANDI PENG: Ya. 796 00:38:55,930 --> 00:38:58,640 Anda dapat mengatur beberapa breakpoints dan itu hanya bisa melompat dari satu ke yang lain. 797 00:38:58,640 --> 00:39:01,590 Tapi dalam kasus ini kita tidak tahu di mana kesalahan yang terjadi. 798 00:39:01,590 --> 00:39:03,780 Jadi kami hanya ingin mulai dari atas ke bawah. 799 00:39:03,780 --> 00:39:05,020 Yep. 800 00:39:05,020 --> 00:39:05,550 OKE. 801 00:39:05,550 --> 00:39:08,460 >> Jadi baris ini di sini, kita dapat melangkah di. 802 00:39:08,460 --> 00:39:11,499 Anda dapat melihat di sini, kita punya array. 803 00:39:11,499 --> 00:39:13,290 Mereka adalah nilai-nilai yang dalam array. 804 00:39:13,290 --> 00:39:16,360 Apakah Anda melihat bahwa, bagaimana indeks 0, itu sesuai dengan value-- oh, 805 00:39:16,360 --> 00:39:17,526 Aku akan mencoba untuk memperbesar. 806 00:39:17,526 --> 00:39:20,650 Maaf, itu benar-benar sulit untuk see-- di indeks array 0, 807 00:39:20,650 --> 00:39:24,090 kami memiliki nilai 4 dan kemudian sebagainya dan sebagainya. 808 00:39:24,090 --> 00:39:25,670 Kami memiliki variabel lokal kami. 809 00:39:25,670 --> 00:39:28,570 Sekarang saya adalah sama dengan 0, yang kita inginkan. 810 00:39:28,570 --> 00:39:31,540 811 00:39:31,540 --> 00:39:33,690 >> Dan jadi mari kita terus melangkah melalui. 812 00:39:33,690 --> 00:39:36,850 Minimum kami adalah sama dengan 0, yang kami juga ingin menjadi. 813 00:39:36,850 --> 00:39:39,470 814 00:39:39,470 --> 00:39:45,560 Dan kemudian kita masukkan kedua kami untuk lingkaran, jika array-j kurang dari array i, 815 00:39:45,560 --> 00:39:46,380 yang itu tidak. 816 00:39:46,380 --> 00:39:48,130 Jadi apakah Anda melihat bagaimana yang dilewati lebih dari itu? 817 00:39:48,130 --> 00:39:52,430 >> AUDIENCE: Jadi seharusnya jika minimum, semua itu-- tidak harus yang 818 00:39:52,430 --> 00:39:55,424 berada di dalam yang pertama untuk loop? 819 00:39:55,424 --> 00:39:57,340 ANDI PENG: Tidak, karena Anda masih ingin menguji. 820 00:39:57,340 --> 00:40:00,329 Anda ingin melakukan perbandingan setiap waktu, bahkan setelah Anda berjalan melalui itu. 821 00:40:00,329 --> 00:40:02,620 Anda tidak hanya ingin melakukannya pada pertama pass-through. 822 00:40:02,620 --> 00:40:05,240 Anda ingin melakukannya dengan setiap lulus tambahan lagi. 823 00:40:05,240 --> 00:40:07,198 Jadi, Anda ingin memeriksa kondisi Anda di dalam. 824 00:40:07,198 --> 00:40:11,610 825 00:40:11,610 --> 00:40:13,746 Jadi kita hanya akan terus berjalan lewat sini. 826 00:40:13,746 --> 00:40:17,337 827 00:40:17,337 --> 00:40:18,420 Saya akan memberikan kalian petunjuk. 828 00:40:18,420 --> 00:40:23,910 Ini ada hubungannya dengan fakta bahwa ketika Anda sedang memeriksa bersyarat Anda, 829 00:40:23,910 --> 00:40:26,600 Anda tidak memeriksa untuk indeks yang benar. 830 00:40:26,600 --> 00:40:32,510 Jadi sekarang Anda sedang memeriksa untuk Indeks array j kurang dari array yang 831 00:40:32,510 --> 00:40:33,970 indeks i. 832 00:40:33,970 --> 00:40:36,580 Tapi apa yang Anda lakukan di awal untuk loop? 833 00:40:36,580 --> 00:40:38,260 Apakah Anda tidak menetapkan j sama dengan saya? 834 00:40:38,260 --> 00:40:41,260 835 00:40:41,260 --> 00:40:45,415 >> Ya, jadi kita benar-benar dapat keluar debugger di sini. 836 00:40:45,415 --> 00:40:47,040 Jadi mari kita lihat pseudocode kami. 837 00:40:47,040 --> 00:40:50,070 838 00:40:50,070 --> 00:40:52,580 For-- kita akan mulai dari i sama dengan 0. 839 00:40:52,580 --> 00:40:54,760 Kita akan pergi ke n minus 1. 840 00:40:54,760 --> 00:40:58,040 Mari kita periksa, apakah kita memiliki hak itu? 841 00:40:58,040 --> 00:40:59,580 Ya, itu benar. 842 00:40:59,580 --> 00:41:02,080 >> Jadi dalam sini, kami akan menciptakan nilai minimum 843 00:41:02,080 --> 00:41:03,630 dan menetapkan bahwa sama dengan saya. 844 00:41:03,630 --> 00:41:04,950 Apakah kita melakukan itu? 845 00:41:04,950 --> 00:41:06,270 Yap, melakukan itu. 846 00:41:06,270 --> 00:41:10,430 Sekarang dalam batin untuk loop kami, kami akan melakukan j sama saya ke n 1 dikurangi. 847 00:41:10,430 --> 00:41:11,950 Apakah kita melakukan itu? 848 00:41:11,950 --> 00:41:15,540 Memang, kami melakukan itu. 849 00:41:15,540 --> 00:41:19,922 >> Jadi bagaimanapun, apa yang kita membandingkan di sini? 850 00:41:19,922 --> 00:41:20,925 >> AUDIENCE: j ditambah 1. 851 00:41:20,925 --> 00:41:21,716 ANDI PENG: Tepat. 852 00:41:21,716 --> 00:41:24,184 853 00:41:24,184 --> 00:41:27,350 Dan kemudian Anda akan ingin mengatur minimum Anda sama dengan j ditambah 1 juga. 854 00:41:27,350 --> 00:41:31,057 855 00:41:31,057 --> 00:41:32,640 Jadi saya pergi melalui yang benar-benar cepat. 856 00:41:32,640 --> 00:41:36,190 Apakah kalian mengerti mengapa j ditambah 1? 857 00:41:36,190 --> 00:41:36,890 OKE. 858 00:41:36,890 --> 00:41:40,700 >> Jadi dalam array, di lulus pertama Anda melalui, 859 00:41:40,700 --> 00:41:44,850 Anda untuk loop, untuk int i sama dengan 0, mari kita 860 00:41:44,850 --> 00:41:46,740 menganggap ini belum berubah belum. 861 00:41:46,740 --> 00:41:53,180 862 00:41:53,180 --> 00:41:56,760 Kami memiliki sebuah array, benar-benar, hanya empat elemen disortir, kan? 863 00:41:56,760 --> 00:42:00,760 Jadi kita ingin menginisialisasi saya sama dengan 0. 864 00:42:00,760 --> 00:42:03,650 Dan saya akan hanya dijalankan melalui lingkaran ini. 865 00:42:03,650 --> 00:42:08,560 Dan di lulus pertama, kita akan untuk menginisialisasi sebuah variabel yang disebut "min" 866 00:42:08,560 --> 00:42:11,245 yang juga sama dengan saya, karena kita tidak memiliki nilai minimum. 867 00:42:11,245 --> 00:42:12,870 Jadi itulah saat sama dengan 0 juga. 868 00:42:12,870 --> 00:42:16,182 869 00:42:16,182 --> 00:42:17,640 Dan kemudian kita akan pergi melalui. 870 00:42:17,640 --> 00:42:19,270 Dan kami ingin beralih lagi. 871 00:42:19,270 --> 00:42:22,900 Sekarang kita telah menemukan apa yang minimum kami adalah, kami ingin iterate melalui 872 00:42:22,900 --> 00:42:25,190 lagi untuk melihat apakah itu membandingkan, kan? 873 00:42:25,190 --> 00:42:40,440 Jadi j, di sini, akan untuk i sama, yaitu 0. 874 00:42:40,440 --> 00:42:46,320 Dan kemudian jika j berbagai plus saya, yang adalah salah satu yang selanjutnya lebih, kurang 875 00:42:46,320 --> 00:42:49,270 dari apa yang minimum saat Nilai adalah, Anda ingin menukar. 876 00:42:49,270 --> 00:42:56,850 >> Jadi mari kita hanya mengatakan kita sudah punya, seperti, 2, 5, 1, 8. 877 00:42:56,850 --> 00:43:01,610 Sekarang, saya adalah sama dengan 0 dan j sama dengan 0. 878 00:43:01,610 --> 00:43:05,210 Dan itulah nilai minimum kami. 879 00:43:05,210 --> 00:43:09,950 Jika array-j ditambah Aku-- sehingga jika satu itu setelah salah satu kita sedang melihat 880 00:43:09,950 --> 00:43:13,450 lebih besar dari yang sebelumnya itu, itu akan menjadi minimum. 881 00:43:13,450 --> 00:43:18,120 >> Jadi di sini kita melihat bahwa 5 tidak kurang dari itu. 882 00:43:18,120 --> 00:43:19,730 Jadi itu akan tidak 5. 883 00:43:19,730 --> 00:43:23,580 Kita melihat bahwa 1 kurang dari 2, kan? 884 00:43:23,580 --> 00:43:32,970 Jadi sekarang kita tahu bahwa minimum kami adalah akan menjadi nilai indeks pada 0, 1, 2. 885 00:43:32,970 --> 00:43:34,030 Ya? 886 00:43:34,030 --> 00:43:39,170 Dan kemudian ketika Anda mendapatkan di sini, Anda dapat menukar nilai-nilai yang benar. 887 00:43:39,170 --> 00:43:42,610 >> Jadi ketika kalian hanya memiliki j sebelumnya, Anda tidak melihat satu 888 00:43:42,610 --> 00:43:43,260 setelah itu. 889 00:43:43,260 --> 00:43:44,520 Anda sedang melihat nilai yang sama, yang 890 00:43:44,520 --> 00:43:46,290 mengapa hal itu tidak melakukan apa-apa. 891 00:43:46,290 --> 00:43:49,721 Apakah itu masuk akal untuk semua orang, mengapa kita membutuhkan itu ditambah 1 ada? 892 00:43:49,721 --> 00:43:50,220 OKE. 893 00:43:50,220 --> 00:43:53,345 Sekarang mari kita jalankan melalui itu untuk membuat Pastikan sisa kode sudah benar. 894 00:43:53,345 --> 00:44:04,424 895 00:44:04,424 --> 00:44:05,340 Mengapa itu terjadi? 896 00:44:05,340 --> 00:44:14,780 897 00:44:14,780 --> 00:44:16,364 Ah, itu adalah min di sini. 898 00:44:16,364 --> 00:44:17,780 Kami membandingkan nilai yang salah. 899 00:44:17,780 --> 00:44:24,944 900 00:44:24,944 --> 00:44:25,906 Oh tidak. 901 00:44:25,906 --> 00:44:30,720 902 00:44:30,720 --> 00:44:33,482 >> Oh ya, di sini kami menukar nilai yang salah juga. 903 00:44:33,482 --> 00:44:34,940 Karena kami sedang mencari di i dan j. 904 00:44:34,940 --> 00:44:36,440 Mereka adalah orang-orang kami memeriksa. 905 00:44:36,440 --> 00:44:39,160 Kami benar-benar ingin menukar minimum, minimum saat ini, 906 00:44:39,160 --> 00:44:40,550 dengan apa pun yang luar. 907 00:44:40,550 --> 00:44:59,510 908 00:44:59,510 --> 00:45:05,402 Dan seperti yang kalian dapat melihat ke bawah di sini, kami memiliki array diurutkan. 909 00:45:05,402 --> 00:45:07,110 Itu hanya ada hubungannya dengan fakta bahwa ketika 910 00:45:07,110 --> 00:45:09,350 kami memeriksa nilai kami membandingkan, 911 00:45:09,350 --> 00:45:11,226 kami tidak melihat nilai-nilai yang tepat. 912 00:45:11,226 --> 00:45:13,850 Kami sedang mencari di satu sama sini, tidak benar-benar swapping itu. 913 00:45:13,850 --> 00:45:17,135 Anda harus melihat satu berikutnya untuk itu dan kemudian Anda dapat swap. 914 00:45:17,135 --> 00:45:19,260 Jadi itulah yang agak mengganggu kode kita sebelumnya. 915 00:45:19,260 --> 00:45:22,460 Dan apa yang saya lakukan di sini adalah segalanya debugger bisa dilakukan untuk Anda 916 00:45:22,460 --> 00:45:23,810 Saya hanya melakukannya pada papan, karena lebih mudah 917 00:45:23,810 --> 00:45:26,320 untuk melihat daripada mencoba untuk memperbesar debugger. 918 00:45:26,320 --> 00:45:29,391 Apakah itu masuk akal untuk semua orang? 919 00:45:29,391 --> 00:45:29,890 Keren. 920 00:45:29,890 --> 00:45:34,800 921 00:45:34,800 --> 00:45:35,410 >> Baiklah. 922 00:45:35,410 --> 00:45:41,070 Kita bisa beralih ke berbicara tentang notasi asimtotik, yang 923 00:45:41,070 --> 00:45:44,580 adalah cara mewah mengatakan runtimes dari semua jenis ini. 924 00:45:44,580 --> 00:45:47,650 Jadi saya tahu David, dalam kuliah, disinggung runtimes. 925 00:45:47,650 --> 00:45:52,124 Dan ia pergi melalui seluruh rumus bagaimana menghitung runtimes. 926 00:45:52,124 --> 00:45:53,040 Jangan khawatir tentang itu. 927 00:45:53,040 --> 00:45:54,660 Jika Anda benar-benar ingin tahu bagaimana yang bekerja, 928 00:45:54,660 --> 00:45:55,810 merasa bebas untuk berbicara dengan saya setelah bagian. 929 00:45:55,810 --> 00:45:57,560 Kita bisa berjalan melalui rumus bersama-sama. 930 00:45:57,560 --> 00:46:00,689 Tapi semua kalian harus benar-benar tahu adalah bahwa n kuadrat lebih dari 2 931 00:46:00,689 --> 00:46:01,980 adalah hal yang sama seperti n kuadrat. 932 00:46:01,980 --> 00:46:04,710 Karena jumlah terbesar, eksponen, tumbuh paling. 933 00:46:04,710 --> 00:46:06,590 Dan untuk tujuan kita, semua kita peduli 934 00:46:06,590 --> 00:46:09,470 adalah bahwa jumlah raksasa yang tumbuh. 935 00:46:09,470 --> 00:46:13,340 >> Jadi apa adalah kasus terbaik runtime seleksi semacam? 936 00:46:13,340 --> 00:46:15,830 Jika Anda akan memiliki iterate melalui daftar 937 00:46:15,830 --> 00:46:18,712 dan kemudian iterate melalui sisa daftar itu, 938 00:46:18,712 --> 00:46:20,420 berapa kali adalah Anda akan mungkin, 939 00:46:20,420 --> 00:46:24,612 di case-- terburuk di kasus terbaik, sorry-- dijalankan melalui? 940 00:46:24,612 --> 00:46:27,070 Mungkin pertanyaan yang lebih baik adalah bertanya, apa kasus terburuk 941 00:46:27,070 --> 00:46:28,153 runtime seleksi semacam. 942 00:46:28,153 --> 00:46:29,366 AUDIENCE: n kuadrat. 943 00:46:29,366 --> 00:46:30,740 ANDI PENG: Ini n kuadrat, benar. 944 00:46:30,740 --> 00:46:36,986 Jadi cara mudah untuk memikirkan ini seperti, setiap kali Anda memiliki dua bersarang untuk loop, 945 00:46:36,986 --> 00:46:38,110 itu akan n kuadrat. 946 00:46:38,110 --> 00:46:40,386 Karena bukan saja Anda berjalan melalui sekali lagi, 947 00:46:40,386 --> 00:46:42,260 Anda harus kembali sekitar dan berjalan melalui itu 948 00:46:42,260 --> 00:46:44,980 sekali lagi dalam untuk setiap nilai. 949 00:46:44,980 --> 00:46:48,640 Jadi dalam hal ini, Anda menjalankan n kali n kuadrat, yang is-- maaf, 950 00:46:48,640 --> 00:46:50,505 n kali n, yang equals n kuadrat. 951 00:46:50,505 --> 00:46:53,230 952 00:46:53,230 --> 00:46:56,360 >> Dan semacam ini juga sedikit unik dalam arti 953 00:46:56,360 --> 00:46:59,774 bahwa tidak masalah jika ini nilai-nilai yang sudah dalam rangka. 954 00:46:59,774 --> 00:47:01,440 Ini masih akan berjalan melalui anyways. 955 00:47:01,440 --> 00:47:03,872 Anggap saja ini adalah 1, 2, 3, 4. 956 00:47:03,872 --> 00:47:07,080 Terlepas dari apakah atau tidak itu adalah di order, itu masih akan berlari melalui 957 00:47:07,080 --> 00:47:08,620 dan masih memeriksa nilai minimum. 958 00:47:08,620 --> 00:47:10,100 Ini akan membuat jumlah yang sama cek 959 00:47:10,100 --> 00:47:12,780 setiap saat, bahkan jika itu tidak benar-benar menyentuh apa pun. 960 00:47:12,780 --> 00:47:16,940 >> Jadi dalam kasus seperti itu, yang terbaik dan terburuk runtimes sebenarnya setara. 961 00:47:16,940 --> 00:47:19,160 Jadi runtime yang diharapkan seleksi semacam, 962 00:47:19,160 --> 00:47:23,790 yang kami menunjuk dengan simbol theta, theta, dalam hal ini, 963 00:47:23,790 --> 00:47:24,790 juga akan n kuadrat. 964 00:47:24,790 --> 00:47:26,480 Semua tiga ini akan n kuadrat. 965 00:47:26,480 --> 00:47:29,653 Apakah setiap orang yang jelas tentang mengapa runtime n kuadrat? 966 00:47:29,653 --> 00:47:33,360 967 00:47:33,360 --> 00:47:33,980 >> Baiklah. 968 00:47:33,980 --> 00:47:39,120 Jadi aku hanya akan cepat menjalankan melalui sisa macam. 969 00:47:39,120 --> 00:47:41,137 Algoritma untuk gelembung sort-- ingat, 970 00:47:41,137 --> 00:47:43,220 ini adalah yang pertama David pergi dalam kuliah. 971 00:47:43,220 --> 00:47:46,000 Pada dasarnya, Anda melangkah melalui seluruh daftar 972 00:47:46,000 --> 00:47:48,950 dan Anda swap-- Anda hanya membandingkan dua pada satu waktu. 973 00:47:48,950 --> 00:47:51,350 Dan jika salah satu yang lebih besar, daripada Anda hanya swap mereka. 974 00:47:51,350 --> 00:47:53,590 Jadi jika ini adalah lebih besar, Anda akan menukar. 975 00:47:53,590 --> 00:47:56,180 Aku punya resmi di sini. 976 00:47:56,180 --> 00:47:59,100 >> Jadi katakan saja Anda memiliki 8, 6, 4, 2. 977 00:47:59,100 --> 00:48:00,571 Anda akan membandingkan 8 dan 6. 978 00:48:00,571 --> 00:48:01,570 Anda akan perlu untuk swap mereka. 979 00:48:01,570 --> 00:48:02,610 Anda akan membandingkan 8 dan 4. 980 00:48:02,610 --> 00:48:03,609 Anda akan perlu untuk swap mereka. 981 00:48:03,609 --> 00:48:07,000 Jika Anda harus menukar 8 dan 2, mengubah mereka juga. 982 00:48:07,000 --> 00:48:10,760 Jadi dalam arti seperti itu, Anda dapat melihat, dimainkan selama periode waktu yang panjang, 983 00:48:10,760 --> 00:48:13,730 bagaimana nilai-nilai semacam gelembung untuk ujungnya, itulah sebabnya kami menyebutnya 984 00:48:13,730 --> 00:48:15,320 bubble sort. 985 00:48:15,320 --> 00:48:19,950 >> Kami hanya akan dijalankan melalui lagi pada lulus kedua kami, dan lulus ketiga kami, 986 00:48:19,950 --> 00:48:21,150 dan lulus keempat kami. 987 00:48:21,150 --> 00:48:25,820 Pada dasarnya, bubble sort hanya berjalan sampai Anda tidak membuat swap lebih. 988 00:48:25,820 --> 00:48:31,109 Jadi dalam hal ini, ini hanya pseudocode umum untuk itu. 989 00:48:31,109 --> 00:48:32,650 Jangan khawatir, ini semua akan online. 990 00:48:32,650 --> 00:48:34,990 Kami tidak harus benar-benar pergi ini. 991 00:48:34,990 --> 00:48:38,134 >> Kami hanya menginisialisasi counter variabel yang dimulai pada 0. 992 00:48:38,134 --> 00:48:39,800 Dan kita iterate melalui seluruh array. 993 00:48:39,800 --> 00:48:43,420 Dan jika salah satu nilai is-- jika ini nilai lebih besar dari nilai tersebut, 994 00:48:43,420 --> 00:48:44,610 Anda akan swap mereka. 995 00:48:44,610 --> 00:48:46,860 Dan kemudian Anda hanya akan terus berjalan. 996 00:48:46,860 --> 00:48:47,970 Dan kau akan menghitung. 997 00:48:47,970 --> 00:48:50,845 Dan Anda hanya akan terus melakukan ini sementara counter lebih besar 998 00:48:50,845 --> 00:48:53,345 dari 0, yang berarti bahwa setiap kali Anda harus swap, 999 00:48:53,345 --> 00:48:55,220 Anda tahu bahwa Anda ingin pergi kembali dan periksa lagi. 1000 00:48:55,220 --> 00:48:59,510 Anda ingin menyimpan memeriksa sampai Anda tahu Anda tidak perlu menukar lagi. 1001 00:48:59,510 --> 00:49:05,570 >> Jadi apa yang terbaik dan terburuk kasus runtimes untuk bubble sort? 1002 00:49:05,570 --> 00:49:09,300 Dan hint-- ini sebenarnya berbeda dari pemilihan semacam dalam arti 1003 00:49:09,300 --> 00:49:11,810 bahwa kedua jawaban yang tidak sama. 1004 00:49:11,810 --> 00:49:14,709 Pikirkan tentang apa yang akan terjadi di kasus jika itu sudah diurutkan. 1005 00:49:14,709 --> 00:49:16,500 Dan berpikir tentang apa akan terjadi jika itu 1006 00:49:16,500 --> 00:49:18,372 dalam kasus di mana itu tidak diurutkan. 1007 00:49:18,372 --> 00:49:20,580 Dan Anda dapat jenis lari melalui mengapa yang terjadi. 1008 00:49:20,580 --> 00:49:22,954 Saya akan memberikan kalian, seperti, 30 detik untuk berpikir tentang itu. 1009 00:49:22,954 --> 00:49:52,330 1010 00:49:52,330 --> 00:49:53,540 >> OKE. 1011 00:49:53,540 --> 00:49:57,462 Apakah ada yang punya menebak apa yang kasus terburuk runtime dari bubble sort adalah? 1012 00:49:57,462 --> 00:49:57,962 Ya. 1013 00:49:57,962 --> 00:50:07,810 >> AUDIENCE: Akan itu, seperti, n kali n minus 1 atau sesuatu seperti itu? 1014 00:50:07,810 --> 00:50:10,650 Seperti, setiap kali berjalan, itu hanya, seperti, satu Swap kurang 1015 00:50:10,650 --> 00:50:10,960 bahwa apa pun itu. 1016 00:50:10,960 --> 00:50:12,668 >> ANDI PENG: Ya, jadi Anda benar-benar tepat. 1017 00:50:12,668 --> 00:50:15,940 Dan ini adalah kasus di mana Anda Jawabannya sebenarnya lebih kompleks 1018 00:50:15,940 --> 00:50:17,240 dari satu yang kita perlu memberikan. 1019 00:50:17,240 --> 00:50:19,772 Jadi itu akan run-- saya akan menghapus semua ini di sini. 1020 00:50:19,772 --> 00:50:20,480 Apakah semua orang baik? 1021 00:50:20,480 --> 00:50:21,869 Dapatkah saya menghapus ini? 1022 00:50:21,869 --> 00:50:22,368 OKE. 1023 00:50:22,368 --> 00:50:27,904 1024 00:50:27,904 --> 00:50:30,320 Anda akan berjalan melalui n kali pertama kalinya, kan? 1025 00:50:30,320 --> 00:50:33,200 Dan mereka akan berjalan melalui n minus 1 kedua kalinya, kan? 1026 00:50:33,200 --> 00:50:37,130 Dan kemudian Anda akan tetap akan, n tambang 2, dan lain-lain. 1027 00:50:37,130 --> 00:50:40,210 David melakukan ini dalam sebuah kuliah, di mana, jika Anda menambahkan semua nilai-nilai, 1028 00:50:40,210 --> 00:50:48,080 Anda mendapatkan sesuatu yang like-- yeah lebih dari 2, yang pada dasarnya hanya mengurangi 1029 00:50:48,080 --> 00:50:49,784 ke n kuadrat. 1030 00:50:49,784 --> 00:50:51,700 Anda akan mendapatkan fraksi aneh di sana. 1031 00:50:51,700 --> 00:50:53,892 Dan hanya tahu bahwa n kuadrat selalu 1032 00:50:53,892 --> 00:50:55,350 lebih diutamakan daripada fraksi. 1033 00:50:55,350 --> 00:50:58,450 Dan dalam hal ini, yang terburuk runtime akan n kuadrat. 1034 00:50:58,450 --> 00:51:00,210 Jika itu di turun order, berpikir, Anda 1035 00:51:00,210 --> 00:51:02,530 harus membuat swap setiap saat. 1036 00:51:02,530 --> 00:51:05,170 >> Apa yang akan menjadi, berpotensi, yang terbaik kasus runtime? 1037 00:51:05,170 --> 00:51:08,580 Katakan saja, jika daftar itu sudah dalam rangka, apa yang akan runtime itu? 1038 00:51:08,580 --> 00:51:09,565 >> AUDIENCE: n. 1039 00:51:09,565 --> 00:51:10,690 ANDI PENG: Ini n, persis. 1040 00:51:10,690 --> 00:51:11,600 Dan mengapa itu n? 1041 00:51:11,600 --> 00:51:13,850 AUDIENCE: Karena Anda hanya harus memeriksa setiap sekali. 1042 00:51:13,850 --> 00:51:14,770 ANDI PENG: Tepat. 1043 00:51:14,770 --> 00:51:17,150 Jadi dalam runtime terbaik, jika daftar ini sudah 1044 00:51:17,150 --> 00:51:20,270 sorted-- katakanlah 1, 2, 3, 4-- Anda akan hanya pergi melalui, Anda akan memeriksa, 1045 00:51:20,270 --> 00:51:21,720 Anda akan melihat, oh, mereka semua berjalan dengan baik. 1046 00:51:21,720 --> 00:51:22,636 Saya tidak perlu menukar. 1047 00:51:22,636 --> 00:51:23,370 Saya selesai. 1048 00:51:23,370 --> 00:51:26,500 Jadi dalam hal ini, itu hanya n atau jumlah langkah Anda hanya 1049 00:51:26,500 --> 00:51:29,870 harus memeriksa dalam daftar pertama. 1050 00:51:29,870 --> 00:51:33,990 >> Dan setelah itu, kita sekarang memukul insertion sort, di mana 1051 00:51:33,990 --> 00:51:39,260 algoritma dasarnya untuk membagi menjadi bagian diurutkan dan disortir. 1052 00:51:39,260 --> 00:51:42,810 Dan kemudian satu per satu, nilai-nilai yang disortir 1053 00:51:42,810 --> 00:51:46,880 dimasukkan ke dalam mereka yang sesuai posisi di awal daftar. 1054 00:51:46,880 --> 00:51:52,120 >> Jadi misalnya, kita memiliki daftar 3, 5, 2, 6, 4 lagi. 1055 00:51:52,120 --> 00:51:54,750 Kita tahu bahwa itu saat disortir karena kita baru saja 1056 00:51:54,750 --> 00:51:57,030 mulai melihat itu. 1057 00:51:57,030 --> 00:52:00,610 Kami melihat dan kita tahu bahwa nilai pertama diurutkan, kan? 1058 00:52:00,610 --> 00:52:04,190 Jika Anda hanya melihat sebuah array ukuran satu, Anda tahu bahwa itu diurutkan. 1059 00:52:04,190 --> 00:52:08,230 >> Jadi kita tahu bahwa empat lainnya yang tidak dipisahkan. 1060 00:52:08,230 --> 00:52:10,980 Kami pergi melalui dan kami melihat nilai itu. 1061 00:52:10,980 --> 00:52:11,730 Ayo kembali. 1062 00:52:11,730 --> 00:52:13,130 Melihat bahwa nilai 5? 1063 00:52:13,130 --> 00:52:14,110 Kami mengambil melihat itu. 1064 00:52:14,110 --> 00:52:15,204 Kami membandingkannya dengan 3. 1065 00:52:15,204 --> 00:52:17,870 Kita tahu bahwa itu lebih besar dari 3, jadi kita tahu bahwa yang diurutkan. 1066 00:52:17,870 --> 00:52:22,940 Jadi sekarang kita tahu bahwa dua yang pertama diurutkan dan tiga terakhir tidak. 1067 00:52:22,940 --> 00:52:24,270 >> Kita lihat pada 2. 1068 00:52:24,270 --> 00:52:25,720 Kami periksa dulu dengan 5. 1069 00:52:25,720 --> 00:52:26,700 Apakah itu kurang dari 5? 1070 00:52:26,700 --> 00:52:27,240 Itu bukan. 1071 00:52:27,240 --> 00:52:29,510 Jadi kita harus terus melihat ke bawah. 1072 00:52:29,510 --> 00:52:30,940 Kemudian Anda memeriksa 2 dari 3. 1073 00:52:30,940 --> 00:52:31,850 Apakah itu kurang dari? 1074 00:52:31,850 --> 00:52:32,350 Tidak. 1075 00:52:32,350 --> 00:52:35,430 Jadi Anda tahu 2 harus dimasukkan ke depan dan 3 dan 5 1076 00:52:35,430 --> 00:52:38,200 keduanya harus didorong keluar. 1077 00:52:38,200 --> 00:52:42,190 Melakukan ini lagi dengan 6 dan 4. 1078 00:52:42,190 --> 00:52:48,962 Dan kami hanya tetap memeriksa dasarnya, di mana kita hanya memeriksa, memeriksa, periksa. 1079 00:52:48,962 --> 00:52:51,170 Dan sampai itu di kanan posisi, kita hanya jenis 1080 00:52:51,170 --> 00:52:54,890 masukkan ke dalam posisi yang tepat, yang mana nama itu berasal. 1081 00:52:54,890 --> 00:52:59,830 >> Jadi itu hanya algoritma, pseudocode per se, jenis, 1082 00:52:59,830 --> 00:53:04,990 bagaimana kita akan menerapkan semacam penyisipan. 1083 00:53:04,990 --> 00:53:05,954 Pseudo sini. 1084 00:53:05,954 --> 00:53:06,620 Ini semua online. 1085 00:53:06,620 --> 00:53:10,720 Jangan khawatir jika kalian mencoba untuk menyalin ini turun. 1086 00:53:10,720 --> 00:53:14,500 Jadi sekali lagi, sama question-- apa akan menjadi yang terbaik dan terburuk runtimes 1087 00:53:14,500 --> 00:53:16,120 untuk insertion sort? 1088 00:53:16,120 --> 00:53:17,750 Ini sangat mirip dengan pertanyaan terakhir. 1089 00:53:17,750 --> 00:53:20,479 Saya akan memberikan kalian, seperti, 30 detik untuk berpikir tentang ini juga. 1090 00:53:20,479 --> 00:53:47,150 1091 00:53:47,150 --> 00:53:50,071 >> OK Apakah ada yang ingin memberi saya runtime terburuk? 1092 00:53:50,071 --> 00:53:50,570 Ya. 1093 00:53:50,570 --> 00:53:51,490 >> AUDIENCE: n kuadrat. 1094 00:53:51,490 --> 00:53:52,573 >> ANDI PENG: Ini n kuadrat. 1095 00:53:52,573 --> 00:53:53,730 Dan mengapa itu n kuadrat? 1096 00:53:53,730 --> 00:53:57,562 >> AUDIENCE: Karena di urutan terbalik, Anda memiliki 1097 00:53:57,562 --> 00:54:02,619 untuk pergi melalui n kali n, yang is-- 1098 00:54:02,619 --> 00:54:03,660 ANDI PENG: Ya, persis. 1099 00:54:03,660 --> 00:54:06,610 Hal sehingga sama seperti dalam semacam gelembung. 1100 00:54:06,610 --> 00:54:08,720 Jika daftar ini di urutan, Anda 1101 00:54:08,720 --> 00:54:11,240 akan harus memeriksa sekali pertama. 1102 00:54:11,240 --> 00:54:13,470 Dan kemudian dengan setiap nilai tambah, Anda 1103 00:54:13,470 --> 00:54:16,390 akan harus memeriksa terhadap setiap nilai tunggal, kan? 1104 00:54:16,390 --> 00:54:20,290 Dan sama sekali, Anda akan membuat n lulus kali lain n lulus, yang 1105 00:54:20,290 --> 00:54:21,750 adalah n kuadrat. 1106 00:54:21,750 --> 00:54:22,860 Bagaimana dengan kasus terbaik? 1107 00:54:22,860 --> 00:54:24,360 Ya. 1108 00:54:24,360 --> 00:54:28,840 >> AUDIENCE: n minus 1, karena Yang pertama sudah kuadrat. 1109 00:54:28,840 --> 00:54:30,270 >> ANDI PENG: Jadi, dekat. 1110 00:54:30,270 --> 00:54:31,850 Jawabannya sebenarnya n. 1111 00:54:31,850 --> 00:54:37,189 Karena sementara yang pertama adalah diurutkan, mungkin tidak actually-- itu 1112 00:54:37,189 --> 00:54:38,980 kami hanya beruntung, di contoh itu, yang 2 1113 00:54:38,980 --> 00:54:40,930 kebetulan nomor terkecil. 1114 00:54:40,930 --> 00:54:43,680 Tapi itu tidak akan selalu terjadi. 1115 00:54:43,680 --> 00:54:48,040 Jika 2 sudah diurutkan di awal tetapi Anda melihat dan ada 1 di sini, 1116 00:54:48,040 --> 00:54:49,144 1 akan benjolan itu. 1117 00:54:49,144 --> 00:54:51,060 Dan itu akan berakhir up yang bertemu lagian. 1118 00:54:51,060 --> 00:54:56,250 >> Jadi dalam skenario kasus terbaik, itu sebenarnya hanya akan menjadi n. 1119 00:54:56,250 --> 00:54:59,090 Jika Anda memiliki 1, 2, 3, 4, 5, 6, 7, 8, Anda 1120 00:54:59,090 --> 00:55:00,940 akan dijalankan melalui bahwa seluruh daftar sekali 1121 00:55:00,940 --> 00:55:03,430 untuk memeriksa untuk melihat apakah semuanya baik-baik saja. 1122 00:55:03,430 --> 00:55:07,390 Apakah setiap orang yang jelas tentang berjalan kali seleksi juga? 1123 00:55:07,390 --> 00:55:09,960 Aku tahu aku akan melalui ini benar-benar cepat. 1124 00:55:09,960 --> 00:55:13,330 Tapi hanya tahu bahwa jika Anda tahu konsep umum, Anda harus baik. 1125 00:55:13,330 --> 00:55:16,070 OKE. 1126 00:55:16,070 --> 00:55:19,790 Jadi saya hanya akan memberikan kalian mungkin, seperti, satu menit untuk berbicara dengan tetangga Anda 1127 00:55:19,790 --> 00:55:21,890 apa adalah beberapa perbedaan utama 1128 00:55:21,890 --> 00:55:23,540 antara jenis macam. 1129 00:55:23,540 --> 00:56:24,571 1130 00:56:24,571 --> 00:56:25,570 Kami akan pergi lebih dari itu segera. 1131 00:56:25,570 --> 00:56:26,444 AUDIENCE: Oh, OK. 1132 00:56:26,444 --> 00:56:27,320 ANDI PENG: Ya. 1133 00:56:27,320 --> 00:56:28,380 OKE. 1134 00:56:28,380 --> 00:56:33,420 Keren, mari kita mulai lagi sebagai kelas. 1135 00:56:33,420 --> 00:56:34,330 OKE. 1136 00:56:34,330 --> 00:56:37,579 Jadi ini semacam sebuah pertanyaan terbuka dalam arti 1137 00:56:37,579 --> 00:56:39,120 bahwa ada banyak jawaban mereka. 1138 00:56:39,120 --> 00:56:40,746 Dan kita akan membahas beberapa dari mereka sebentar. 1139 00:56:40,746 --> 00:56:43,411 Aku hanya ingin kalian berpikir tentang apa yang dibedakan 1140 00:56:43,411 --> 00:56:44,530 ketiga jenis macam. 1141 00:56:44,530 --> 00:56:47,440 Dan aku mendengar, juga, besar question-- apa semacam penggabungan lakukan? 1142 00:56:47,440 --> 00:56:50,110 Pertanyaan besar, karena itulah apa yang kita meliputi berikutnya. 1143 00:56:50,110 --> 00:56:52,850 >> Jadi menggabungkan semacam adalah satu jenis yang berfungsi 1144 00:56:52,850 --> 00:56:56,100 sangat berbeda dari jenis lain. 1145 00:56:56,100 --> 00:56:58,180 Seperti kalian bisa see-- Daud melakukan demo yang 1146 00:56:58,180 --> 00:57:01,130 di mana ia memiliki semua yang keren suara dari melihat bagaimana menggabungkan 1147 00:57:01,130 --> 00:57:04,010 semacam berlari, seperti, jauh lebih cepat dari dua jenis lainnya? 1148 00:57:04,010 --> 00:57:04,510 OKE. 1149 00:57:04,510 --> 00:57:07,580 Jadi itu karena merge semacam mengimplementasikan membagi bahwa 1150 00:57:07,580 --> 00:57:11,020 dan konsep yang kami telah menaklukkan berbicara tentang banyak dalam kuliah. 1151 00:57:11,020 --> 00:57:14,550 Dalam arti bahwa kita ingin bekerja cerdas, bukan lebih keras, ketika Anda membagi 1152 00:57:14,550 --> 00:57:18,120 dan menaklukkan masalah, dan istirahat mereka bawah, dan kemudian menempatkan mereka bersama-sama, 1153 00:57:18,120 --> 00:57:19,930 hal-hal baik selalu terjadi. 1154 00:57:19,930 --> 00:57:21,960 >> Jadi cara yang menggabungkan semacam dasarnya bekerja 1155 00:57:21,960 --> 00:57:24,660 adalah bahwa hal itu membagi sebuah Array disortir di setengah. 1156 00:57:24,660 --> 00:57:26,500 Dan kemudian itu punya dua bagian dari array. 1157 00:57:26,500 --> 00:57:28,220 Dan itu hanya macam dua bagian. 1158 00:57:28,220 --> 00:57:31,750 Itu hanya terus membagi dua, di setengah, setengah sampai semuanya diurutkan 1159 00:57:31,750 --> 00:57:33,680 dan kemudian secara rekursif menempatkan itu semua bersama-sama. 1160 00:57:33,680 --> 00:57:36,550 >> Jadi itu benar-benar abstrak. 1161 00:57:36,550 --> 00:57:38,750 Jadi ini hanya sedikit pseudocode. 1162 00:57:38,750 --> 00:57:41,040 Apakah itu masuk akal dalam cara itu berjalan? 1163 00:57:41,040 --> 00:57:43,870 Jadi katakan saja Anda memiliki array elemen n, kan? 1164 00:57:43,870 --> 00:57:45,450 Jika n adalah kurang dari 2, Anda dapat kembali. 1165 00:57:45,450 --> 00:57:49,040 Karena Anda tahu bahwa jika ada hanya satu hal, itu harus dipilah. 1166 00:57:49,040 --> 00:57:52,600 Lain, Anda menyortir kiri setengah, dan kemudian Anda menyortir bagian kanan, 1167 00:57:52,600 --> 00:57:54,140 dan kemudian Anda bergabung. 1168 00:57:54,140 --> 00:57:56,979 >> Jadi sementara yang terlihat benar-benar mudah, dalam kenyataannya, berpikir tentang itu 1169 00:57:56,979 --> 00:58:00,270 agak sulit. Karena Anda seperti, baik, yang semacam berjalan pada itu sendiri. 1170 00:58:00,270 --> 00:58:00,769 Benar? 1171 00:58:00,769 --> 00:58:02,430 Itu berjalan dengan sendirinya. 1172 00:58:02,430 --> 00:58:05,479 Jadi dalam hal ini, David menyentuh pada rekursi di kelas. 1173 00:58:05,479 --> 00:58:07,270 Dan itu sebuah konsep kita akan berbicara tentang lebih. 1174 00:58:07,270 --> 00:58:11,430 Ini yang ini, dua baris di sini, benar-benar hanya program 1175 00:58:11,430 --> 00:58:13,860 mengatakan hal itu untuk menjalankan sendiri dengan input yang berbeda. 1176 00:58:13,860 --> 00:58:17,230 Jadi, daripada berjalan sendiri dengan keseluruhan elemen n, 1177 00:58:17,230 --> 00:58:20,530 Anda dapat memecahnya ke dalam setengah kiri dan kanan setengah 1178 00:58:20,530 --> 00:58:22,680 dan kemudian jalankan lagi. 1179 00:58:22,680 --> 00:58:26,050 >> Dan kemudian kita akan melihat secara visual, karena aku seorang pelajar visual. 1180 00:58:26,050 --> 00:58:27,270 Ia bekerja lebih baik bagi saya. 1181 00:58:27,270 --> 00:58:29,890 Jadi kita akan melihat contoh visual di sini. 1182 00:58:29,890 --> 00:58:36,237 >> Katakanlah kita memiliki sebuah array, enam elemen, 3, 5, 2, 6, 4, 1, tidak diurutkan. 1183 00:58:36,237 --> 00:58:37,820 Baiklah, ada banyak di halaman ini. 1184 00:58:37,820 --> 00:58:43,179 Jadi jika kalian dapat melihat Langkah pertama di sini, 3, 5, 2, 6, 4, 1, 1185 00:58:43,179 --> 00:58:44,220 Anda dapat membagi menjadi dua. 1186 00:58:44,220 --> 00:58:45,976 Anda memiliki 3, 5, 2, 6, 4, 1. 1187 00:58:45,976 --> 00:58:48,850 Anda tahu bahwa ini aren't-- Anda tidak tahu apakah mereka diurutkan atau tidak, 1188 00:58:48,850 --> 00:58:52,517 sehingga Anda tetap melanggar mereka, dalam setengah, dalam setengah, setengah, sampai akhirnya, 1189 00:58:52,517 --> 00:58:53,600 Anda hanya memiliki satu elemen. 1190 00:58:53,600 --> 00:58:56,790 Dan salah satu unsur selalu diurutkan, kan? 1191 00:58:56,790 --> 00:59:01,560 >> Jadi kita tahu bahwa 3, 5, 2, 4, 6, 1, dengan sendirinya, diurutkan. 1192 00:59:01,560 --> 00:59:05,870 Dan sekarang kita bisa menempatkan mereka kembali bersama-sama. 1193 00:59:05,870 --> 00:59:07,510 Jadi kita tahu 3, 5. 1194 00:59:07,510 --> 00:59:08,510 Kami menempatkan mereka bersama-sama. 1195 00:59:08,510 --> 00:59:09,617 Kita tahu itu diurutkan. 1196 00:59:09,617 --> 00:59:10,450 2 masih ada. 1197 00:59:10,450 --> 00:59:11,830 Kita bisa menempatkan 4 dan 6 bersama-sama. 1198 00:59:11,830 --> 00:59:13,996 Kita tahu bahwa yang diurutkan, sehingga kami menempatkan bersama-sama. 1199 00:59:13,996 --> 00:59:14,940 Dan 1 ada. 1200 00:59:14,940 --> 00:59:18,720 >> Dan kemudian Anda hanya melihat dua bagian ini di sini. 1201 00:59:18,720 --> 00:59:21,300 Anda memiliki 3, 5, 2, 2, 3, 5. 1202 00:59:21,300 --> 00:59:23,465 Anda hanya dapat membandingkan mulai dari segala sesuatu. 1203 00:59:23,465 --> 00:59:26,340 Karena Anda tahu bahwa ini diurutkan dan Anda tahu bahwa yang diurutkan. 1204 00:59:26,340 --> 00:59:29,360 Jadi Anda bahkan tidak perlu membandingkan 5, Anda hanya membandingkan 3. 1205 00:59:29,360 --> 00:59:32,070 Dan 2 adalah kurang dari 3, sehingga Anda tahu 2 harus pergi pada akhirnya. 1206 00:59:32,070 --> 00:59:33,120 >> Hal yang sama di sana. 1207 00:59:33,120 --> 00:59:34,740 1 harus pergi di sini. 1208 00:59:34,740 --> 00:59:37,330 Dan kemudian ketika Anda pergi untuk menempatkan kedua nilai bersama-sama, 1209 00:59:37,330 --> 00:59:39,950 Anda tahu bahwa ini diurutkan dan Anda tahu bahwa yang diurutkan. 1210 00:59:39,950 --> 00:59:43,240 Jadi maka 1 dan 2, 1 kurang dari 2. 1211 00:59:43,240 --> 00:59:45,570 Yang memberitahu Anda bahwa 1 harus pergi pada akhir ini 1212 00:59:45,570 --> 00:59:47,480 bahkan tanpa melihat 3 atau 5. 1213 00:59:47,480 --> 00:59:50,100 Dan kemudian 4, Anda bisa hanya periksa, ia pergi tepat di sini. 1214 00:59:50,100 --> 00:59:51,480 Anda tidak harus melihat 5. 1215 00:59:51,480 --> 00:59:52,570 Hal yang sama dengan 6. 1216 00:59:52,570 --> 00:59:55,860 Anda tahu bahwa itu hanya 6-- tidak perlu tampak. 1217 00:59:55,860 --> 00:59:57,870 >> Dan dengan cara itu, Anda hanya menyelamatkan diri 1218 00:59:57,870 --> 00:59:59,526 banyak langkah-langkah ketika Anda membandingkan. 1219 00:59:59,526 --> 01:00:02,150 Anda tidak harus membandingkan setiap unsur terhadap unsur-unsur lainnya. 1220 01:00:02,150 --> 01:00:05,230 Anda hanya membandingkan terhadap orang-orang bahwa Anda perlu untuk membandingkannya dengan. 1221 01:00:05,230 --> 01:00:06,870 Jadi itu semacam konsep abstrak. 1222 01:00:06,870 --> 01:00:10,540 Jangan khawatir jika tidak cukup memukul Anda benar belum. 1223 01:00:10,540 --> 01:00:14,740 Tapi pada umumnya, ini adalah bagaimana semacam gabungan bekerja. 1224 01:00:14,740 --> 01:00:17,750 Pertanyaan, pertanyaan cepat, sebelum saya melanjutkan? 1225 01:00:17,750 --> 01:00:18,550 Ya. 1226 01:00:18,550 --> 01:00:22,230 >> AUDIENCE: Jadi Anda mengatakan bahwa Anda mengambil 1, dan kemudian 4, dan 6 1227 01:00:22,230 --> 01:00:23,860 dan menempatkan mereka dalam. 1228 01:00:23,860 --> 01:00:26,800 Jadi tidak those-- tidak Anda melihat mereka 1229 01:00:26,800 --> 01:00:28,544 sebagai elemen yang terpisah, bukan sebagai keseluruhan? 1230 01:00:28,544 --> 01:00:29,210 ANDI PENG: Ya. 1231 01:00:29,210 --> 01:00:32,020 Jadi apa yang terjadi adalah bahwa Anda pada dasarnya 1232 01:00:32,020 --> 01:00:33,650 menciptakan array baru. 1233 01:00:33,650 --> 01:00:36,690 Jadi Anda tahu bahwa, di sini, saya harus dua array ukuran 3, kan? 1234 01:00:36,690 --> 01:00:39,600 Jadi Anda tahu bahwa array diurutkan saya perlu memiliki enam elemen. 1235 01:00:39,600 --> 01:00:42,270 Jadi Anda hanya membuat Jumlah memory baru. 1236 01:00:42,270 --> 01:00:44,270 Jadi Anda jenis seperti menjadi boros memori, 1237 01:00:44,270 --> 01:00:46,186 tapi itu tidak masalah karena begitu kecil. 1238 01:00:46,186 --> 01:00:48,590 Jadi Anda melihat 1 dan Anda melihat 2. 1239 01:00:48,590 --> 01:00:50,770 Dan Anda tahu bahwa 1 kurang dari 2. 1240 01:00:50,770 --> 01:00:53,840 Jadi Anda tahu bahwa 1 harus pergi di awal semua orang. 1241 01:00:53,840 --> 01:00:55,850 >> Anda bahkan tidak perlu melihat 3 dan 5. 1242 01:00:55,850 --> 01:00:57,400 Jadi, Anda tahu 1 pergi ke sana. 1243 01:00:57,400 --> 01:00:59,300 Maka Anda pada dasarnya memenggal 1. 1244 01:00:59,300 --> 01:01:00,370 Ini, seperti, mati untuk kita. 1245 01:01:00,370 --> 01:01:03,690 Kemudian kita hanya perlu 2, 3, 5, dan kemudian 4 dan 6. 1246 01:01:03,690 --> 01:01:06,270 Dan kemudian Anda tahu bahwa, Anda membandingkan 4 dan 2, 1247 01:01:06,270 --> 01:01:07,560 oh, 2 harus masuk ke sana. 1248 01:01:07,560 --> 01:01:09,685 Jadi Anda celepuk 2 bawah, Anda memotong off. 1249 01:01:09,685 --> 01:01:12,060 Jadi Anda hanya memiliki 3 dan 5 dalam 4 dan 6. 1250 01:01:12,060 --> 01:01:14,650 Dan Anda hanya terus memotong off sampai Anda menempatkan mereka dalam array. 1251 01:01:14,650 --> 01:01:17,110 >> AUDIENCE: Jadi Anda hanya selalu membandingkan [tidak terdengar]? 1252 01:01:17,110 --> 01:01:17,710 >> ANDI PENG: Tepat. 1253 01:01:17,710 --> 01:01:19,590 Jadi dalam hal ini, Anda hanya membandingkan, pada dasarnya, 1254 01:01:19,590 --> 01:01:21,240 satu nomor terhadap nomor lain. 1255 01:01:21,240 --> 01:01:22,990 Dan karena Anda tahu bahwa itu diurutkan, Anda 1256 01:01:22,990 --> 01:01:24,350 tidak harus melihat melalui semua nomor. 1257 01:01:24,350 --> 01:01:25,870 Anda hanya perlu melihat yang pertama. 1258 01:01:25,870 --> 01:01:27,582 Dan kemudian Anda hanya dapat celepuk mereka turun, karena Anda tahu 1259 01:01:27,582 --> 01:01:29,640 mereka milik di mana mereka harus berada. 1260 01:01:29,640 --> 01:01:31,030 Ya. 1261 01:01:31,030 --> 01:01:32,920 Pertanyaan bagus. 1262 01:01:32,920 --> 01:01:35,290 >> Dan kemudian jika salah satu dari Anda agak ambisius, 1263 01:01:35,290 --> 01:01:38,660 merasa bebas untuk melihat kode ini. 1264 01:01:38,660 --> 01:01:40,680 Ini sebenarnya adalah pelaksanaan fisik 1265 01:01:40,680 --> 01:01:42,150 bagaimana kita akan menulis merge sort. 1266 01:01:42,150 --> 01:01:44,070 Dan Anda dapat melihat, itu sangat singkat. 1267 01:01:44,070 --> 01:01:46,310 Tapi ide dibalik itu cukup kompleks. 1268 01:01:46,310 --> 01:01:50,865 Jadi jika Anda merasa seperti menggambar ini keluar PR malam ini Anda, jangan ragu untuk. 1269 01:01:50,865 --> 01:01:54,050 1270 01:01:54,050 --> 01:01:54,740 >> OKE. 1271 01:01:54,740 --> 01:01:58,070 Jadi David juga pergi ini di kuliah. 1272 01:01:58,070 --> 01:02:00,660 Apa kasus terbaik runtimes, runtimes kasus terburuk, 1273 01:02:00,660 --> 01:02:05,680 dan runtimes diharapkan dari merge semacam? 1274 01:02:05,680 --> 01:02:07,260 Beberapa detik untuk berpikir. 1275 01:02:07,260 --> 01:02:11,198 Ini cukup sulit, tetapi jenis intuitif jika Anda berpikir tentang hal itu. 1276 01:02:11,198 --> 01:02:20,090 1277 01:02:20,090 --> 01:02:23,054 Baiklah. 1278 01:02:23,054 --> 01:02:25,269 >> AUDIENCE: Apakah kasus terburuk n log n? 1279 01:02:25,269 --> 01:02:26,060 ANDI PENG: Tepat. 1280 01:02:26,060 --> 01:02:29,380 Dan mengapa itu n log n. 1281 01:02:29,380 --> 01:02:32,230 >> AUDIENCE: Bukankah karena menjadi eksponensial lebih cepat, 1282 01:02:32,230 --> 01:02:35,390 jadi seperti fungsi yang bukan hanya sekadar n 1283 01:02:35,390 --> 01:02:37,529 kuadrat atau sesuatu? 1284 01:02:37,529 --> 01:02:38,320 ANDI PENG: Tepat. 1285 01:02:38,320 --> 01:02:40,750 Jadi alasan mengapa runtime di ini n log 1286 01:02:40,750 --> 01:02:44,310 n adalah because-- apa yang Anda lakukan di semua langkah ini? 1287 01:02:44,310 --> 01:02:46,190 Kau hanya memotong menjadi dua, kan? 1288 01:02:46,190 --> 01:02:48,750 Dan jadi ketika kita sedang melakukan log, semua yang dilakukannya 1289 01:02:48,750 --> 01:02:53,150 adalah membagi masalah di setengah, dalam setengah, setengah, lebih bagian. 1290 01:02:53,150 --> 01:02:56,430 Dan dalam arti itu, Anda dapat jenis dari menghilangkan model linier 1291 01:02:56,430 --> 01:02:57,510 bahwa kita telah menggunakan. 1292 01:02:57,510 --> 01:03:00,254 Karena ketika Anda memotong hal dalam setengah, itu log. 1293 01:03:00,254 --> 01:03:02,420 Itu hanya matematika cara untuk mewakili itu. 1294 01:03:02,420 --> 01:03:06,310 >> Dan akhirnya, di akhir, Anda hanya membuat satu lulus lalu melalui 1295 01:03:06,310 --> 01:03:07,930 untuk menempatkan mereka semua dalam rangka, kan? 1296 01:03:07,930 --> 01:03:10,330 Dan jadi jika Anda hanya harus memeriksa satu hal, itu n. 1297 01:03:10,330 --> 01:03:13,420 Dan sehingga Anda jenis mengalikan dua bersama-sama. 1298 01:03:13,420 --> 01:03:17,660 Jadi seperti Anda punya yang akhir memeriksa n di sini dengan log n 1299 01:03:17,660 --> 01:03:18,390 di sini. 1300 01:03:18,390 --> 01:03:21,060 Dan jika Anda kalikan mereka, yang n log n. 1301 01:03:21,060 --> 01:03:26,100 >> Dan kasus terbaik dan terburuk kasus dan diharapkan semua n log n. 1302 01:03:26,100 --> 01:03:27,943 Ini juga seperti jenis lain. 1303 01:03:27,943 --> 01:03:30,090 Ini seperti semacam seleksi dalam arti bahwa hal itu 1304 01:03:30,090 --> 01:03:32,131 tidak peduli apa Anda daftar adalah, itu hanya akan 1305 01:03:32,131 --> 01:03:34,801 untuk melakukan hal yang sama setiap waktu. 1306 01:03:34,801 --> 01:03:35,300 OKE. 1307 01:03:35,300 --> 01:03:39,950 Sehingga kalian bisa melihat, meskipun macam yang kita sudah through-- n 1308 01:03:39,950 --> 01:03:41,660 kuadrat, itu tidak sangat efisien. 1309 01:03:41,660 --> 01:03:47,060 Dan bahkan n log ini n adalah bukan yang paling efisien. 1310 01:03:47,060 --> 01:03:49,720 Jika kalian ingin tahu, ada mekanisme semacam 1311 01:03:49,720 --> 01:03:54,310 yang begitu efisien bahwa mereka hampir dasarnya datar di runtime. 1312 01:03:54,310 --> 01:03:55,420 >> Anda punya beberapa log n. 1313 01:03:55,420 --> 01:03:58,190 Anda punya beberapa log log n. 1314 01:03:58,190 --> 01:04:00,330 Kami tidak menyentuh mereka di kelas ini sekarang. 1315 01:04:00,330 --> 01:04:02,663 Tetapi jika kalian ingin tahu, merasa bebas untuk google, apa 1316 01:04:02,663 --> 01:04:04,392 penyortiran mekanisme yang paling efisien. 1317 01:04:04,392 --> 01:04:06,350 Saya tidak tahu, ada beberapa yang benar-benar lucu, 1318 01:04:06,350 --> 01:04:09,860 like-- ada beberapa benar-benar yang lucu yang dilakukan orang. 1319 01:04:09,860 --> 01:04:12,210 Dan Anda bertanya-tanya bagaimana mereka pernah memikirkan hal itu. 1320 01:04:12,210 --> 01:04:15,730 Jadi google, jika Anda memiliki beberapa cadangan waktu, pada, apa adalah beberapa cara yang lucu 1321 01:04:15,730 --> 01:04:17,730 yang people-- serta orang ways-- efisien 1322 01:04:17,730 --> 01:04:20,371 telah mampu menerapkan macam. 1323 01:04:20,371 --> 01:04:20,870 OKE. 1324 01:04:20,870 --> 01:04:22,880 Dan di sini hanya grafik sedikit berguna. 1325 01:04:22,880 --> 01:04:26,850 Aku tahu kalian semua, sebelum itu kuis 0, akan berada di kamar Anda mungkin mencoba 1326 01:04:26,850 --> 01:04:27,960 menghafal itu. 1327 01:04:27,960 --> 01:04:30,940 Jadi itu bagus di sana untuk kalian. 1328 01:04:30,940 --> 01:04:37,120 Hanya jangan lupa logika bahwa made-- mengapa angka-angka yang terjadi. 1329 01:04:37,120 --> 01:04:39,870 Jika Anda selalu kalah, hanya membuat Pastikan Anda tahu apa jenis yang. 1330 01:04:39,870 --> 01:04:40,820 Dan Anda dapat menjalankan melalui mereka dalam pikiran Anda 1331 01:04:40,820 --> 01:04:42,903 untuk mencari tahu mengapa orang-orang jawaban adalah mereka jawaban. 1332 01:04:42,903 --> 01:04:46,250 1333 01:04:46,250 --> 01:04:47,600 >> Baiklah. 1334 01:04:47,600 --> 01:04:49,680 Jadi kita akan pindah pada akhirnya, untuk pencarian. 1335 01:04:49,680 --> 01:04:51,638 Karena orang-orang dari Anda yang telah membaca pset itu, 1336 01:04:51,638 --> 01:04:55,175 pencarian juga merupakan bagian dari masalah minggu ini menetapkan. 1337 01:04:55,175 --> 01:04:57,300 Anda akan diminta untuk menerapkan dua jenis pencarian. 1338 01:04:57,300 --> 01:05:00,070 Salah satunya adalah pencarian linear dan satu adalah pencarian biner. 1339 01:05:00,070 --> 01:05:01,760 >> Jadi pencarian linear cukup mudah. 1340 01:05:01,760 --> 01:05:04,070 Anda hanya ingin mencari elemen dari daftar untuk melihat apakah Anda mendapatkannya. 1341 01:05:04,070 --> 01:05:05,444 Anda hanya perlu iterate melalui. 1342 01:05:05,444 --> 01:05:08,170 Dan jika itu sama dengan sesuatu, Anda hanya dapat kembali, kan? 1343 01:05:08,170 --> 01:05:10,890 Tapi satu yang kita paling tertarik membicarakan 1344 01:05:10,890 --> 01:05:14,550 adalah pencarian biner, yang benar, yang merupakan membagi dan menaklukkan mekanisme yang 1345 01:05:14,550 --> 01:05:18,190 Daud menunjukkan dalam kuliah. 1346 01:05:18,190 --> 01:05:20,810 >> Ingat contoh buku telepon bahwa ia terus membesarkan, 1347 01:05:20,810 --> 01:05:23,960 salah satu yang ia jenis berjuang sedikit di tahun terakhir ini, 1348 01:05:23,960 --> 01:05:27,530 di mana Anda membagi masalah dalam setengah, dalam setengah, setengah, lagi dan lagi, 1349 01:05:27,530 --> 01:05:30,730 sampai Anda menemukan apa yang Anda cari? 1350 01:05:30,730 --> 01:05:33,727 Dan Anda punya runtime dari itu juga. 1351 01:05:33,727 --> 01:05:35,810 Dan Anda dapat melihat, itu secara signifikan lebih efisien 1352 01:05:35,810 --> 01:05:39,080 daripada jenis lain dari pencarian. 1353 01:05:39,080 --> 01:05:41,880 >> Jadi cara kita akan pergi tentang melaksanakan pencarian biner 1354 01:05:41,880 --> 01:05:46,510 adalah, jika kita memiliki sebuah array, Indeks 0-6, tujuh elemen, 1355 01:05:46,510 --> 01:05:49,790 kita dapat melihat di tengah, right-- maaf, jika pertanyaan kami first-- 1356 01:05:49,790 --> 01:05:53,840 jika kita ingin mengajukan pertanyaan dari, apakah array mengandung unsur 7, 1357 01:05:53,840 --> 01:05:56,840 jelas, menjadi manusia, dan memiliki seperti array kecil, mudah bagi kita 1358 01:05:56,840 --> 01:05:58,210 untuk mengatakan ya. 1359 01:05:58,210 --> 01:06:05,750 Tetapi cara untuk menerapkan biner pencarian akan melihat di tengah. 1360 01:06:05,750 --> 01:06:08,020 >> Kita tahu bahwa indeks 3 adalah tengah, karena kita 1361 01:06:08,020 --> 01:06:09,270 tahu ada tujuh elemen. 1362 01:06:09,270 --> 01:06:10,670 Apa 7 dibagi 2? 1363 01:06:10,670 --> 01:06:12,850 Anda dapat memotong ekstra 1. 1364 01:06:12,850 --> 01:06:14,850 Anda punya 3 di tengah. 1365 01:06:14,850 --> 01:06:17,590 Jadi adalah array 3 sama dengan 7? 1366 01:06:17,590 --> 01:06:18,900 Hal ini tidak, kan? 1367 01:06:18,900 --> 01:06:21,050 Tapi kita bisa melakukan beberapa pemeriksaan. 1368 01:06:21,050 --> 01:06:25,380 Apakah array 3 kurang dari 7 atau adalah array 3 lebih besar dari 7? 1369 01:06:25,380 --> 01:06:27,240 >> Dan kita tahu bahwa itu kurang dari 7. 1370 01:06:27,240 --> 01:06:30,259 Jadi kita tahu bahwa, oh, itu harus tidak berada di kiri setengah. 1371 01:06:30,259 --> 01:06:32,300 Kita tahu bahwa hal itu harus di bagian kanan, kan? 1372 01:06:32,300 --> 01:06:34,662 Jadi kami hanya bisa memenggal setengah array. 1373 01:06:34,662 --> 01:06:36,370 Kami bahkan tidak perlu melihat lagi. 1374 01:06:36,370 --> 01:06:38,711 Karena kita tahu bahwa setengah dari problem-- kami 1375 01:06:38,711 --> 01:06:41,210 kita tahu bahwa jawabannya adalah di kanan setengah dari masalah kita. 1376 01:06:41,210 --> 01:06:42,580 Jadi kita hanya melihat itu sekarang. 1377 01:06:42,580 --> 01:06:44,860 >> Jadi sekarang kita melihat tengah apa yang tersisa. 1378 01:06:44,860 --> 01:06:46,880 Indeks yang 5. 1379 01:06:46,880 --> 01:06:50,200 Kami melakukan cek sama lagi dan kita melihat bahwa itu lebih kecil. 1380 01:06:50,200 --> 01:06:52,050 Jadi kita melihat di sebelah kiri itu. 1381 01:06:52,050 --> 01:06:53,430 Dan kemudian kita melihat bahwa cek. 1382 01:06:53,430 --> 01:06:57,600 Apakah nilai array di Indeks 4 sama dengan 7? 1383 01:06:57,600 --> 01:06:58,260 Ini. 1384 01:06:58,260 --> 01:07:03,580 Jadi kita bisa kembali benar, karena kami menemukan nilai dalam daftar kami. 1385 01:07:03,580 --> 01:07:06,738 Apakah cara saya pergi melalui yang masuk akal untuk semua orang? 1386 01:07:06,738 --> 01:07:08,760 OKE. 1387 01:07:08,760 --> 01:07:11,670 Saya akan memberikan kalian mungkin, seperti, tiga, empat menit untuk mencari tahu 1388 01:07:11,670 --> 01:07:13,270 bagaimana pseudocode ini di. 1389 01:07:13,270 --> 01:07:18,070 >> Jadi bayangkan saya meminta Anda untuk menulis fungsi yang disebut pencarian () yang kembali 1390 01:07:18,070 --> 01:07:20,640 nilai, nilai Boolean, itu benar atau false-- seperti, 1391 01:07:20,640 --> 01:07:22,970 benar jika Anda menemukan nilai, false jika Anda tidak. 1392 01:07:22,970 --> 01:07:25,230 Dan kemudian Anda disahkan pada nilai Anda 1393 01:07:25,230 --> 01:07:28,410 sedang mencari ke dalam nilai-nilai, yang adalah array-- oh, saya pasti menempatkan 1394 01:07:28,410 --> 01:07:29,410 bahwa di tempat yang salah. 1395 01:07:29,410 --> 01:07:29,580 OKE. 1396 01:07:29,580 --> 01:07:31,829 Anyways, yang harus memiliki pernah ke kanan nilai. 1397 01:07:31,829 --> 01:07:36,280 Dan kemudian int n adalah nomor elemen dalam array itu. 1398 01:07:36,280 --> 01:07:39,430 Bagaimana Anda pergi tentang mencoba untuk pseudocode bahwa masalah di? 1399 01:07:39,430 --> 01:07:41,630 Saya akan memberikan orang-orang seperti tiga menit untuk melakukan itu. 1400 01:07:41,630 --> 01:08:00,137 1401 01:08:00,137 --> 01:08:02,595 Tidak, saya pikir ada only-- yeah, ada satu yang tepat di sini. 1402 01:08:02,595 --> 01:08:03,261 AUDIENCE: Dapatkah saya? 1403 01:08:03,261 --> 01:08:04,388 ANDI PENG: Ya, saya punya Anda. 1404 01:08:04,388 --> 01:08:09,410 1405 01:08:09,410 --> 01:08:11,050 Apakah kerja itu? 1406 01:08:11,050 --> 01:08:12,290 OK keren. 1407 01:08:12,290 --> 01:10:43,590 1408 01:10:43,590 --> 01:10:44,720 >> OKE. 1409 01:10:44,720 --> 01:10:47,630 Semua orang yang tepat, kita akan mengekang dalam. 1410 01:10:47,630 --> 01:10:49,730 OKE. 1411 01:10:49,730 --> 01:10:54,020 Jadi asumsikan kita punya ini indah sedikit array dengan nilai n di dalamnya. 1412 01:10:54,020 --> 01:10:55,170 Aku tidak menggambar garis. 1413 01:10:55,170 --> 01:10:58,649 Tapi bagaimana kita akan pergi tentang mencoba untuk menulis ini? 1414 01:10:58,649 --> 01:11:00,440 Apakah ada yang ingin memberikan baris pertama? 1415 01:11:00,440 --> 01:11:02,814 Jika Anda ingin memberi saya baris pertama dari pseudocode ini. 1416 01:11:02,814 --> 01:11:06,563 1417 01:11:06,563 --> 01:11:08,430 >> AUDIENCE: [tidak terdengar] 1418 01:11:08,430 --> 01:11:10,138 AUDIENCE: Anda ingin iterate through-- 1419 01:11:10,138 --> 01:11:11,094 AUDIENCE: Just another untuk loop? 1420 01:11:11,094 --> 01:11:11,760 AUDIENCE: --Untuk. 1421 01:11:11,760 --> 01:11:15,880 1422 01:11:15,880 --> 01:11:17,780 >> ANDI PENG: Jadi yang satu ini agak sulit. 1423 01:11:17,780 --> 01:11:23,130 Pikirkan about-- Anda ingin terus berjalan lingkaran ini 1424 01:11:23,130 --> 01:11:27,950 berulang-ulang sampai kapan? 1425 01:11:27,950 --> 01:11:30,819 >> AUDIENCE: Sampai [tidak terdengar] nilai sama dengan nilai tersebut. 1426 01:11:30,819 --> 01:11:31,610 ANDI PENG: Tepat. 1427 01:11:31,610 --> 01:11:33,900 Jadi Anda benar-benar bisa hanya write-- kita bahkan dapat menyederhanakan lebih. 1428 01:11:33,900 --> 01:11:35,630 Kami hanya bisa melakukan loop sementara, kan? 1429 01:11:35,630 --> 01:11:39,380 Jadi Anda hanya dapat memiliki loop-- kita tahu bahwa itu sementara. 1430 01:11:39,380 --> 01:11:42,850 Tapi untuk sekarang, aku akan mengatakan "loop" - melalui apa? 1431 01:11:42,850 --> 01:11:46,640 Lingkaran until-- apa kondisi kita berakhir? 1432 01:11:46,640 --> 01:11:47,510 Saya pikir saya mendengar itu. 1433 01:11:47,510 --> 01:11:48,530 Aku mendengar seseorang mengatakan itu. 1434 01:11:48,530 --> 01:11:51,255 >> AUDIENCE: Nilai sama tengah. 1435 01:11:51,255 --> 01:11:52,255 ANDI PENG: Katakan lagi. 1436 01:11:52,255 --> 01:11:54,470 AUDIENCE: Atau, sampai Nilai yang Anda cari 1437 01:11:54,470 --> 01:11:58,470 adalah sama dengan nilai tengah. 1438 01:11:58,470 --> 01:12:00,280 >> ANDI PENG: Bagaimana jika itu tidak di sana? 1439 01:12:00,280 --> 01:12:03,113 Bagaimana jika nilai yang Anda cari adalah tidak benar-benar dalam array ini? 1440 01:12:03,113 --> 01:12:05,890 AUDIENCE: Anda kembali 1. 1441 01:12:05,890 --> 01:12:08,850 >> ANDI PENG: Tapi apa yang kita ingin loop sampai jika kita memiliki kondisi? 1442 01:12:08,850 --> 01:12:09,350 Ya. 1443 01:12:09,350 --> 01:12:11,239 >> AUDIENCE: Sampai hanya ada satu nilai? 1444 01:12:11,239 --> 01:12:13,530 ANDI PENG: Anda dapat loop until-- sehingga Anda tahu bahwa Anda 1445 01:12:13,530 --> 01:12:15,714 akan memiliki nilai max, kan? 1446 01:12:15,714 --> 01:12:18,130 Dan Anda tahu bahwa Anda akan memiliki nilai min, kan? 1447 01:12:18,130 --> 01:12:20,379 Karena juga, itu sesuatu Aku lupa mengatakan sebelumnya, 1448 01:12:20,379 --> 01:12:22,640 bahwa sesuatu yang kritis tentang pencarian biner 1449 01:12:22,640 --> 01:12:24,182 adalah bahwa array Anda sudah diurutkan. 1450 01:12:24,182 --> 01:12:26,973 Karena tidak ada cara untuk melakukan ini jika mereka nilai hanya acak. 1451 01:12:26,973 --> 01:12:29,190 Anda tidak tahu jika salah satu yang lebih besar dari yang lain, kan? 1452 01:12:29,190 --> 01:12:32,720 >> Jadi, Anda tahu bahwa Anda dan max menit Anda di sini, kan? 1453 01:12:32,720 --> 01:12:35,590 Jika Anda akan menyesuaikan maks Anda di menit Anda dan mid-- 1454 01:12:35,590 --> 01:12:38,470 mari kita hanya berasumsi Anda Nilai pertengahan adalah di sini-benar 1455 01:12:38,470 --> 01:12:43,910 Anda akan dasarnya lingkaran sampai minimum Anda 1456 01:12:43,910 --> 01:12:47,510 hampir sama dengan max Anda, kanan, atau jika max Anda tidak sama dengan min Anda. 1457 01:12:47,510 --> 01:12:48,040 Benar? 1458 01:12:48,040 --> 01:12:51,340 Karena ketika itu terjadi, Anda tahu bahwa Anda telah akhirnya memukul nilai yang sama. 1459 01:12:51,340 --> 01:12:59,135 Jadi Anda ingin loop sampai menit Anda kurang dari atau sama to-- oops, 1460 01:12:59,135 --> 01:13:01,510 tidak kurang dari atau sama dengan, cara lain around-- max adalah. 1461 01:13:01,510 --> 01:13:15,110 1462 01:13:15,110 --> 01:13:16,160 >> Apakah itu masuk akal? 1463 01:13:16,160 --> 01:13:18,810 Aku mengambil beberapa mencoba untuk mendapatkan hak itu. 1464 01:13:18,810 --> 01:13:21,869 Tapi loop sampai nilai maks Anda pada dasarnya hampir kurang 1465 01:13:21,869 --> 01:13:23,410 dari atau sama dengan minimum Anda, kan? 1466 01:13:23,410 --> 01:13:25,201 Saat itulah Anda tahu bahwa Anda telah berkumpul. 1467 01:13:25,201 --> 01:13:29,290 AUDIENCE: Ketika akan maksimum nilai kurang dari minimum? 1468 01:13:29,290 --> 01:13:31,040 ANDI PENG: Jika Anda terus menyesuaikan itu, yang 1469 01:13:31,040 --> 01:13:32,380 adalah apa yang kita akan akan melakukan dalam hal ini. 1470 01:13:32,380 --> 01:13:33,460 Apakah itu masuk akal? 1471 01:13:33,460 --> 01:13:35,750 Minimum dan maksimum hanya bilangan bulat bahwa kita mungkin 1472 01:13:35,750 --> 01:13:39,260 akan ingin membuat tetap melacak di mana kita cari. 1473 01:13:39,260 --> 01:13:41,790 Karena array ada terlepas dari apa yang kita lakukan. 1474 01:13:41,790 --> 01:13:45,030 Seperti, kita tidak benar-benar secara fisik memenggal array, kan? 1475 01:13:45,030 --> 01:13:47,261 Kami hanya menyesuaikan di mana kita cari. 1476 01:13:47,261 --> 01:13:48,136 Apakah itu masuk akal? 1477 01:13:48,136 --> 01:13:48,472 >> AUDIENCE: Ya. 1478 01:13:48,472 --> 01:13:49,110 >> ANDI PENG: OK. 1479 01:13:49,110 --> 01:13:57,090 Jadi kalau itu kondisi untuk loop kami, apa yang kita inginkan dalam lingkaran ini? 1480 01:13:57,090 --> 01:13:58,700 Apa yang kita akan ingin lakukan? 1481 01:13:58,700 --> 01:14:02,390 Jadi sekarang, kita punya maks dan min, tepat, 1482 01:14:02,390 --> 01:14:04,962 mungkin dibuat di sini di suatu tempat. 1483 01:14:04,962 --> 01:14:07,170 Kita akan mungkin ingin untuk menemukan tengah, kanan? 1484 01:14:07,170 --> 01:14:08,450 Bagaimana kita akan menjadi dapat menemukan tengah? 1485 01:14:08,450 --> 01:14:09,491 Apa yang mathematical-- 1486 01:14:09,491 --> 01:14:11,079 AUDIENCE: Max ditambah min dibagi 2. 1487 01:14:11,079 --> 01:14:11,870 ANDI PENG: Tepat. 1488 01:14:11,870 --> 01:14:20,300 1489 01:14:20,300 --> 01:14:21,620 Apakah itu masuk akal? 1490 01:14:21,620 --> 01:14:25,780 Dan kalian melihat mengapa kami tidak hanya use-- mengapa kita melakukan ini 1491 01:14:25,780 --> 01:14:27,850 bukannya melakukan hanya n dibagi 2? 1492 01:14:27,850 --> 01:14:30,310 Itu karena n adalah nilai itu akan tetap sama. 1493 01:14:30,310 --> 01:14:30,979 Benar? 1494 01:14:30,979 --> 01:14:34,020 Tapi seperti yang kita menyesuaikan minimum dan nilai maksimum, mereka akan berubah. 1495 01:14:34,020 --> 01:14:36,040 Dan sebagai hasilnya, kami tengah akan berubah juga. 1496 01:14:36,040 --> 01:14:37,873 Jadi itu sebabnya kami ingin melakukan ini dengan benar di sini. 1497 01:14:37,873 --> 01:14:38,510 OKE. 1498 01:14:38,510 --> 01:14:41,600 >> Dan kemudian, sekarang kami telah menemukan our-- ya. 1499 01:14:41,600 --> 01:14:44,270 >> AUDIENCE: Hanya question-- cepat ketika Anda mengatakan min dan max, 1500 01:14:44,270 --> 01:14:46,410 kita mengasumsikan bahwa itu sudah diurutkan? 1501 01:14:46,410 --> 01:14:48,400 >> ANDI PENG: Ya, itu benar-benar prasyarat untuk pencarian biner, 1502 01:14:48,400 --> 01:14:49,816 bahwa Anda harus tahu itu diurutkan. 1503 01:14:49,816 --> 01:14:53,660 Itulah sebabnya semacam, Anda menulis di Anda Masalah ditetapkan sebelum pencarian biner Anda. 1504 01:14:53,660 --> 01:14:55,910 OKE. 1505 01:14:55,910 --> 01:14:58,876 Jadi sekarang kita tahu di mana titik tengah kami adalah, apa yang Anda ingin lakukan di sini? 1506 01:14:58,876 --> 01:15:01,789 1507 01:15:01,789 --> 01:15:04,319 >> AUDIENCE: Kami ingin membandingkan bahwa untuk yang lain. 1508 01:15:04,319 --> 01:15:05,110 ANDI PENG: Tepat. 1509 01:15:05,110 --> 01:15:12,280 Jadi Anda akan membandingkan pertengahan hingga nilai, kan? 1510 01:15:12,280 --> 01:15:14,900 1511 01:15:14,900 --> 01:15:18,670 Dan apa yang memberitahu kita ketika kita membandingkan? 1512 01:15:18,670 --> 01:15:22,226 Apa yang ingin kita lakukan setelah itu? 1513 01:15:22,226 --> 01:15:25,389 >> AUDIENCE: Jika nilai lebih besar dari pertengahan, kita ingin memotongnya. 1514 01:15:25,389 --> 01:15:26,180 ANDI PENG: Tepat. 1515 01:15:26,180 --> 01:15:33,940 Jadi jika nilai lebih besar dari pertengahan, kami 1516 01:15:33,940 --> 01:15:36,550 akan ingin mengubah ini minimum dan Maxes, kan? 1517 01:15:36,550 --> 01:15:38,980 Apa yang kita ingin berubah? 1518 01:15:38,980 --> 01:15:42,145 Jadi jika kita tahu nilai adalah suatu tempat di sini, apa yang Anda kita berubah? 1519 01:15:42,145 --> 01:15:44,758 Kami ingin mengubah kami minimum menjadi pertengahan, kan? 1520 01:15:44,758 --> 01:15:49,420 1521 01:15:49,420 --> 01:15:54,292 Dan kemudian yang lain, jika dalam ini setengah, apa yang kita ingin berubah? 1522 01:15:54,292 --> 01:15:55,306 >> AUDIENCE: maksimum Anda. 1523 01:15:55,306 --> 01:15:55,972 ANDI PENG: Ya. 1524 01:15:55,972 --> 01:16:02,597 1525 01:16:02,597 --> 01:16:04,680 Dan kemudian Anda hanya akan untuk menjaga perulangan, kan? 1526 01:16:04,680 --> 01:16:08,920 Karena sekarang, setelah satu iterasi melalui, Anda punya max di sini. 1527 01:16:08,920 --> 01:16:10,760 Dan kemudian Anda dapat menghitung ulang pertengahan. 1528 01:16:10,760 --> 01:16:11,990 Dan kemudian Anda dapat membandingkan. 1529 01:16:11,990 --> 01:16:14,766 Dan Anda akan terus sampai menit dan Maxes 1530 01:16:14,766 --> 01:16:15,890 telah dasarnya berkumpul. 1531 01:16:15,890 --> 01:16:17,890 Dan saat itulah Anda tahu bahwa Anda telah memukul akhir itu. 1532 01:16:17,890 --> 01:16:20,280 Dan baik Anda telah menemukan itu atau Anda belum pada saat itu. 1533 01:16:20,280 --> 01:16:23,170 >> Apakah ini masuk akal untuk semua orang? 1534 01:16:23,170 --> 01:16:26,020 1535 01:16:26,020 --> 01:16:26,770 OKE. 1536 01:16:26,770 --> 01:16:27,900 Ini sangat penting, karena Anda akan memiliki 1537 01:16:27,900 --> 01:16:29,760 untuk menulis ini dalam kode malam Anda. 1538 01:16:29,760 --> 01:16:32,660 Tapi kalian memiliki cukup bagus rasa apa yang seharusnya Anda lakukan, 1539 01:16:32,660 --> 01:16:34,051 yang mana yang bagus. 1540 01:16:34,051 --> 01:16:34,550 OKE. 1541 01:16:34,550 --> 01:16:38,840 Jadi kita punya sekitar tujuh menit tersisa bagian. 1542 01:16:38,840 --> 01:16:43,170 Jadi kita akan berbicara tentang pset ini yang akan kita lakukan. 1543 01:16:43,170 --> 01:16:46,410 Jadi pset dibagi menjadi dua bagian. 1544 01:16:46,410 --> 01:16:50,230 Babak pertama melibatkan menerapkan find 1545 01:16:50,230 --> 01:16:54,210 di mana Anda menulis pencarian linear, sebuah pencarian biner, dan algoritma sorting. 1546 01:16:54,210 --> 01:16:56,690 >> Jadi ini adalah pertama waktu di mana pset 1547 01:16:56,690 --> 01:17:00,050 kami akan memberikan kalian apa yang disebut kode distribusi, yang merupakan kode 1548 01:17:00,050 --> 01:17:02,740 bahwa kita telah pra-ditulis, tetapi hanya meninggalkan beberapa potongan off 1549 01:17:02,740 --> 01:17:04,635 bagi Anda untuk menyelesaikan menulis. 1550 01:17:04,635 --> 01:17:07,510 Jadi kalian, ketika Anda melihat ini kode, Anda mungkin akan benar-benar takut. 1551 01:17:07,510 --> 01:17:08,630 Jika Anda hanya suka, ahh, aku tidak tahu apa yang dilakukan, 1552 01:17:08,630 --> 01:17:11,670 Saya tidak tahu, seperti, yang tampaknya begitu rumit, ahh, bersantai. 1553 01:17:11,670 --> 01:17:12,170 Tidak apa-apa. 1554 01:17:12,170 --> 01:17:12,930 Baca spec. 1555 01:17:12,930 --> 01:17:16,920 Spec akan menjelaskan kepada Anda persis apa semua program ini lakukan. 1556 01:17:16,920 --> 01:17:20,560 >> Misalnya, generate.c adalah sebuah program yang akan datang dengan pset Anda. 1557 01:17:20,560 --> 01:17:24,060 Anda tidak benar-benar harus menyentuhnya, tapi Anda harus memahami apa yang dilakukannya. 1558 01:17:24,060 --> 01:17:28,550 Dan generate.c, semua itu lakukan adalah baik menghasilkan angka acak 1559 01:17:28,550 --> 01:17:32,400 atau Anda dapat memberikan benih, seperti Jumlah diatur sebelumnya bahwa dibutuhkan, 1560 01:17:32,400 --> 01:17:34,140 dan menghasilkan angka lebih. 1561 01:17:34,140 --> 01:17:37,170 Jadi ada cara khusus untuk menerapkan generate.c di mana 1562 01:17:37,170 --> 01:17:42,760 Anda hanya dapat membuat sekelompok angka bagi Anda untuk menguji metode Anda yang lain pada. 1563 01:17:42,760 --> 01:17:45,900 >> Jadi jika Anda ingin, untuk Misalnya, menguji menemukan Anda, 1564 01:17:45,900 --> 01:17:48,970 Anda akan ingin menjalankan generate.c, menghasilkan sekelompok angka, 1565 01:17:48,970 --> 01:17:50,880 dan kemudian menjalankan fungsi pembantu Anda. 1566 01:17:50,880 --> 01:17:53,930 Fungsi pembantu Anda adalah di mana Anda sebenarnya secara fisik menulis kode. 1567 01:17:53,930 --> 01:17:59,330 Dan memikirkan pembantu sebagai file library Anda menulis menemukan yang menelepon. 1568 01:17:59,330 --> 01:18:02,950 Dan dalam helpers.c, Anda akan melakukan pencarian dan menyortir. 1569 01:18:02,950 --> 01:18:06,500 >> Dan kemudian Anda akan dasarnya hanya menempatkan mereka semua bersama-sama. 1570 01:18:06,500 --> 01:18:10,350 Spec akan memberitahu Anda bagaimana untuk menempatkan bahwa pada baris perintah. 1571 01:18:10,350 --> 01:18:14,880 Dan Anda akan dapat menguji apakah tidak semacam Anda dan pencari kerja. 1572 01:18:14,880 --> 01:18:15,870 Keren. 1573 01:18:15,870 --> 01:18:18,720 Apakah ada yang sudah dimulai dan masalah yang dihadapi atau pertanyaan 1574 01:18:18,720 --> 01:18:20,520 mereka miliki sekarang dengan ini? 1575 01:18:20,520 --> 01:18:21,020 OKE. 1576 01:18:21,020 --> 01:18:21,476 >> AUDIENCE: Tunggu. 1577 01:18:21,476 --> 01:18:21,932 Saya punya pertanyaan. 1578 01:18:21,932 --> 01:18:22,844 >> ANDI PENG: Ya. 1579 01:18:22,844 --> 01:18:28,390 >> AUDIENCE: Jadi saya mulai melakukan pencarian linear di helpers.c 1580 01:18:28,390 --> 01:18:29,670 dan itu tidak benar-benar bekerja. 1581 01:18:29,670 --> 01:18:34,590 Tapi kemudian, saya menemukan kami hanya harus menghapusnya dan melakukan pencarian biner. 1582 01:18:34,590 --> 01:18:36,991 Jadi tidak masalah jika tidak bekerja? 1583 01:18:36,991 --> 01:18:39,700 1584 01:18:39,700 --> 01:18:41,510 >> ANDI PENG: Jawaban singkat adalah tidak. 1585 01:18:41,510 --> 01:18:42,642 Tapi karena kami not-- 1586 01:18:42,642 --> 01:18:44,350 AUDIENCE: Tapi ada satu benar-benar memeriksa. 1587 01:18:44,350 --> 01:18:46,058 ANDI PENG: Kami tidak pernah akan melihat itu. 1588 01:18:46,058 --> 01:18:49,590 Tapi Anda mungkin ingin membuat yakin pencarian Anda bekerja. 1589 01:18:49,590 --> 01:18:51,700 Karena jika Anda linear pencarian tidak bekerja, 1590 01:18:51,700 --> 01:18:54,410 maka kemungkinan biner Anda pencarian tidak akan bekerja dengan baik. 1591 01:18:54,410 --> 01:18:56,646 Karena Anda memiliki yang sama logika dalam keduanya. 1592 01:18:56,646 --> 01:18:58,020 Dan tidak, itu tidak terlalu penting. 1593 01:18:58,020 --> 01:19:01,300 Jadi satu-satunya Anda akan berubah di adalah semacam dan pencarian biner. 1594 01:19:01,300 --> 01:19:02,490 Ya. 1595 01:19:02,490 --> 01:19:06,610 >> Dan juga, banyak anak-anak yang mencoba untuk mengkompilasi helpers.c. 1596 01:19:06,610 --> 01:19:09,550 Anda tidak benar-benar diperbolehkan untuk melakukan itu, karena helpers.c 1597 01:19:09,550 --> 01:19:11,200 tidak memiliki fungsi utama. 1598 01:19:11,200 --> 01:19:13,550 Dan sehingga Anda hanya harus akan benar-benar kompilasi 1599 01:19:13,550 --> 01:19:18,670 menghasilkan dan menemukan, karena menemukan panggilan helpers.c dan fungsi di dalamnya. 1600 01:19:18,670 --> 01:19:20,790 Sehingga membuat debugging rasa sakit di pantat. 1601 01:19:20,790 --> 01:19:22,422 Tapi itulah yang harus kita lakukan. 1602 01:19:22,422 --> 01:19:23,880 AUDIENCE: Anda hanya membuat semua, kan? 1603 01:19:23,880 --> 01:19:27,290 ANDI PENG: Anda hanya dapat membuat semua juga, ya. 1604 01:19:27,290 --> 01:19:28,060 OKE. 1605 01:19:28,060 --> 01:19:32,570 Jadi itu dalam hal apa pset yang meminta Anda semua untuk melakukan. 1606 01:19:32,570 --> 01:19:35,160 Jika Anda memiliki pertanyaan, merasa bebas untuk bertanya kepada saya setelah bagian. 1607 01:19:35,160 --> 01:19:37,580 Saya akan berada di sini untuk, seperti, 20 menit. 1608 01:19:37,580 --> 01:19:40,500 >> Dan yeah, pset ini benar-benar tidak buruk. 1609 01:19:40,500 --> 01:19:41,680 Kalian harus OK. 1610 01:19:41,680 --> 01:19:43,250 Ini, hanya mengikuti pedoman. 1611 01:19:43,250 --> 01:19:47,840 Jenis memiliki rasa, secara logis, apa harus terjadi dan Anda akan baik-baik saja. 1612 01:19:47,840 --> 01:19:48,690 Jangan terlalu takut. 1613 01:19:48,690 --> 01:19:50,220 Ada banyak kode sudah tertulis di sana. 1614 01:19:50,220 --> 01:19:53,011 Jangan terlalu takut jika Anda tidak mengerti apa semua itu berarti. 1615 01:19:53,011 --> 01:19:54,749 Jika itu banyak, itu benar-benar baik-baik saja. 1616 01:19:54,749 --> 01:19:55,790 Dan datang ke kantor jam. 1617 01:19:55,790 --> 01:19:57,520 Kami akan membantu anda melihat. 1618 01:19:57,520 --> 01:20:00,810 >> AUDIENCE: Dengan tambahan fungsi, kita melihat orang-up? 1619 01:20:00,810 --> 01:20:03,417 >> ANDI PENG: Ya, mereka adalah dalam kode. 1620 01:20:03,417 --> 01:20:05,750 Dalam permainan 15, setengah dari itu sudah ditulis untuk Anda. 1621 01:20:05,750 --> 01:20:09,310 Jadi fungsi-fungsi yang sudah dalam kode. 1622 01:20:09,310 --> 01:20:12,020 Yep. 1623 01:20:12,020 --> 01:20:12,520 Baiklah. 1624 01:20:12,520 --> 01:20:14,000 Nah, terbaik keberuntungan. 1625 01:20:14,000 --> 01:20:15,180 Ini hari menjijikkan. 1626 01:20:15,180 --> 01:20:19,370 Jadi mudah-mudahan kalian tidak merasa terlalu buruk tentang tinggal di dalam dan coding. 1627 01:20:19,370 --> 01:20:22,133