1 00:00:00,000 --> 00:00:03,332 >> [MUSIC nagpe-play] 2 00:00:03,332 --> 00:00:06,490 >> ANDI PENG: Maligayang pagdating sa week 3 ng section. 3 00:00:06,490 --> 00:00:09,550 Salamat, guys, para sa lahat ng mga darating na ito nang mas maaga ang oras ng simula sa araw na ito. 4 00:00:09,550 --> 00:00:11,466 Mayroon kaming isang magaling, maliit matalik na ngayon. 5 00:00:11,466 --> 00:00:14,570 Kaya sana kami ay kumuha sa matapos, marahil, maaga, 6 00:00:14,570 --> 00:00:15,780 Medyo maaga ngayon. 7 00:00:15,780 --> 00:00:22,057 Kaya mabilis, ilan lang anunsyo para sa agenda ngayong araw. 8 00:00:22,057 --> 00:00:23,890 Bago namin simulan, hindi namin pagpunta sa pumunta lamang sa paglipas ng 9 00:00:23,890 --> 00:00:28,910 ilang maikling logistical isyu, pset katanungan, debrief, mga bagay na tulad ng. 10 00:00:28,910 --> 00:00:30,250 At pagkatapos ay makikita namin sumisid karapatan sa. 11 00:00:30,250 --> 00:00:34,710 Gagamitin namin ang isang debugger tinatawag GDB sa simulan debunking ang aming code, na si David 12 00:00:34,710 --> 00:00:36,550 ipinaliwanag sa lecture ng ibang mga araw. 13 00:00:36,550 --> 00:00:39,420 Kami ay pumunta sa ibabaw ng apat na mga uri ng mga uri. 14 00:00:39,420 --> 00:00:42,310 Kami ay pumunta sa paglipas ng mga ito medyo mabilis dahil ang mga ito pretty intensive. 15 00:00:42,310 --> 00:00:45,710 Ngunit alam na ang lahat ng mga slide at source code ay palaging online. 16 00:00:45,710 --> 00:00:50,810 Kaya huwag mag-atubiling, sa iyong pagbasa, upang bumalik at tingnan kung iyon. 17 00:00:50,810 --> 00:00:53,930 >> Kami ay pumunta sa pamamagitan ng asymptotic pagtatanda, na 18 00:00:53,930 --> 00:00:55,944 ay lamang ng isang magarbong paraan na sabihing "runtimes," 19 00:00:55,944 --> 00:00:58,360 kung saan mayroon kaming ang malaking O, kung saan David ipinaliwanag sa panayam. 20 00:00:58,360 --> 00:01:01,550 At mayroon din kaming Omega, na ay ang mas mababang nakatali runtime. 21 00:01:01,550 --> 00:01:06,450 At kami na makipag-usap ng kaunti pang sa malalim tungkol sa kung paano ang mga trabaho. 22 00:01:06,450 --> 00:01:10,160 At sa wakas, kami ay pumunta sa paglipas ng binary paghahanap, dahil ang isang pulutong ng sa iyo na nag 23 00:01:10,160 --> 00:01:15,190 glanced sa iyong psets marahil alam na iyon ay isang katanungan na sa iyong pset. 24 00:01:15,190 --> 00:01:17,470 Kaya ikaw ay masaya ang lahat na sumasaklaw namin ito ngayon. 25 00:01:17,470 --> 00:01:20,610 >> At sa wakas, sa bawat iyong mga feedback section, ako talaga 26 00:01:20,610 --> 00:01:23,000 kaliwa tungkol sa 15 minuto sa sa dulo upang pumunta lamang sa ibabaw 27 00:01:23,000 --> 00:01:27,730 Logistics ng pset3, anumang mga katanungan, marahil isang piraso ng guidance, kung ikaw ay, 28 00:01:27,730 --> 00:01:28,990 bago namin simulan ang programming. 29 00:01:28,990 --> 00:01:30,890 Kaya sabihin subukan upang makakuha ng sa pamamagitan ipaalam ang materyal medyo mabilis. 30 00:01:30,890 --> 00:01:33,880 At pagkatapos ay maaari naming gumastos ng ilang oras pagkuha ng higit pang mga tanong para sa pset. 31 00:01:33,880 --> 00:01:35,230 SIGE. 32 00:01:35,230 --> 00:01:39,570 >> Mabilis, kaya lamang ng ilang announcements bago namin simulan ang araw na ito. 33 00:01:39,570 --> 00:01:45,410 Una, maligayang pagdating sa paggawa ng ito sa pamamagitan ng dalawang ng iyong psets. 34 00:01:45,410 --> 00:01:49,432 Kinuha ko ang isang pagtingin sa your-- oo, sabihin makakuha ng isang ikot ng papuri para sa isa. 35 00:01:49,432 --> 00:01:51,140 Sa totoo lang, ako ay talagang, talagang impressed. 36 00:01:51,140 --> 00:01:55,800 Gradong ko ang unang pset para sa iyo guys noong nakaraang linggo at ang iyong guys ay hindi kapani-paniwala. 37 00:01:55,800 --> 00:01:58,290 >> Style ay sa puntong bukod sa ilang mga komento. 38 00:01:58,290 --> 00:02:00,660 Tiyakin na ikaw ay palaging pagkomento sa iyong code. 39 00:02:00,660 --> 00:02:03,040 Ngunit ang iyong psets ay sa punto. 40 00:02:03,040 --> 00:02:05,549 At panatilihin ito up. 41 00:02:05,549 --> 00:02:08,090 At ito ay mabuti para sa mga baytang na makita na ikaw guys ay paglagay 42 00:02:08,090 --> 00:02:10,704 sa mas maraming pagsisikap sa iyong estilo at ang iyong mga disenyo sa iyong code 43 00:02:10,704 --> 00:02:12,120 na nais namin para sa iyo na makita. 44 00:02:12,120 --> 00:02:16,450 Kaya ako pagpasa kasama ang aking pasasalamat para sa ang magpahinga ng ang TAS. 45 00:02:16,450 --> 00:02:19,210 >> Subalit may mga ilang mga katanungan debrief 46 00:02:19,210 --> 00:02:22,010 Gusto ko lang pumunta sa paglipas na gagawing parehong aking buhay 47 00:02:22,010 --> 00:02:24,900 at ng maraming iba pang mga TAS 'buhay ng kaunti mas madali. 48 00:02:24,900 --> 00:02:28,220 Una, napansin ko na ito nakaraang week-- kung ilan sa inyo 49 00:02:28,220 --> 00:02:32,301 ay tumatakbo check50 sa ang iyong code bago mo isumite? 50 00:02:32,301 --> 00:02:32,800 SIGE. 51 00:02:32,800 --> 00:02:36,690 Kaya lahat ng tao ay dapat na ginagawa check50, because-- isang secret-- namin talagang 52 00:02:36,690 --> 00:02:41,540 tumakbo check50 bilang bahagi ng aming kawastuhan script para sa pagsubok ang iyong mga code. 53 00:02:41,540 --> 00:02:45,480 Kaya kung ang iyong code ay hindi pagtupad check50, sa lahat ng posibilidad, 54 00:02:45,480 --> 00:02:47,570 marahil ito ay pagpunta sa mabibigo ang aming check rin. 55 00:02:47,570 --> 00:02:49,320 Minsan mo guys May karapatan mga sagot. 56 00:02:49,320 --> 00:02:52,200 Tulad ng, sa sakim, ang ilan sa ikaw ay may karapatan na numero, 57 00:02:52,200 --> 00:02:53,960 i-print out mo lamang ng ilang dagdag na mga bagay-bagay. 58 00:02:53,960 --> 00:02:55,940 At na ang dagdag na mga bagay-bagay talagang nabigo ang check, 59 00:02:55,940 --> 00:02:58,440 dahil ang computer ay hindi talaga alam kung ano ito ay naghahanap para sa. 60 00:02:58,440 --> 00:03:00,981 At kaya ito ay tatakbo lamang sa pamamagitan ng, makita na ang iyong output ay hindi 61 00:03:00,981 --> 00:03:03,810 tumutugma sa kung ano ang inaasahan namin ang sagot upang maging, at markahan ito ay mali. 62 00:03:03,810 --> 00:03:06,560 >> At alam ko na nangyari sa ang ilan sa inyong mga kaso sa linggong ito. 63 00:03:06,560 --> 00:03:09,870 Kaya nagpunta ako sa likod at manu-mano nang muli code ng lahat. 64 00:03:09,870 --> 00:03:12,780 Sa hinaharap bagaman, mangyaring, mangyaring tiyakin 65 00:03:12,780 --> 00:03:14,570 na ikaw ay nagpapatakbo ng check 50 sa iyong code. 66 00:03:14,570 --> 00:03:17,970 Dahil ito ay uri ng isang sakit para sa TA na kailangang bumalik at mano-manong regrade 67 00:03:17,970 --> 00:03:21,197 bawat solong pset para sa bawat single, maliit na hindi nakuha ng pagkakataon. 68 00:03:21,197 --> 00:03:22,530 Kaya ako ay hindi mag-alis ng anumang mga puntos. 69 00:03:22,530 --> 00:03:25,210 Sa tingin ko kinuha ko off siguro isa o dalawang para sa disenyo. 70 00:03:25,210 --> 00:03:27,710 Sa hinaharap bagaman, kung ikaw ay nanghihina check50, 71 00:03:27,710 --> 00:03:31,330 puntos dadalhin off para sa kawastuhan. 72 00:03:31,330 --> 00:03:35,020 >> Higit pa rito, psets ay dahil Biyernes sa tanghali. 73 00:03:35,020 --> 00:03:38,990 Sa tingin ko ay may isang pitong minutong late panahon ng palugit na bigyan ka namin. 74 00:03:38,990 --> 00:03:42,434 Per Harvard oras, sila ay pinapayagan na pitong minuto huli na ang lahat. 75 00:03:42,434 --> 00:03:44,350 Kaya dito sa Yale, bibigyan namin ng sumunod pati na rin sa mga iyon. 76 00:03:44,350 --> 00:03:47,910 Ngunit medyo marami, sa 12:07, kung ang iyong pset ay hindi sa, 77 00:03:47,910 --> 00:03:49,720 ito ay pagpunta sa ay minarkahan bilang late. 78 00:03:49,720 --> 00:03:53,160 At kaya habang ito ay minarkahan bilang huli, ang TA-- Ako 79 00:03:53,160 --> 00:03:54,870 pagpunta pa rin na pagmamarka iyong psets. 80 00:03:54,870 --> 00:03:56,760 Kaya makikita mo pa rin ang lumitaw ang isang grado. 81 00:03:56,760 --> 00:03:58,820 Gayunpaman, alam na sa sa katapusan ng semestre, 82 00:03:58,820 --> 00:04:02,270 lahat ng late psets ay lamang ay awtomatikong zeroed sa pamamagitan ng mga computer. 83 00:04:02,270 --> 00:04:04,490 >> Ginagawa namin ito para sa dalawang kadahilanan. 84 00:04:04,490 --> 00:04:09,220 One, minsan na nakukuha namin paumanhin, tulad ng paliwanag dean, 85 00:04:09,220 --> 00:04:10,762 sa susunod na hindi ko alam tungkol sa pa. 86 00:04:10,762 --> 00:04:13,761 Kaya gusto naming makasiguro na kami ay pagmamarka ang lahat ng bagay kung sakali, tulad ng, ako 87 00:04:13,761 --> 00:04:15,080 nawawala excuse isang dean. 88 00:04:15,080 --> 00:04:17,000 At pangalawa, panatilihin sa isip, maaari mo pa ring 89 00:04:17,000 --> 00:04:19,370 drop isa pset na ay may ganap na puntos saklaw. 90 00:04:19,370 --> 00:04:21,430 At kaya gusto namin na grade ang lahat ng iyong psets lamang 91 00:04:21,430 --> 00:04:24,730 tiyakin na ang iyong saklaw ng doon at sinusubukan ang mga ito. 92 00:04:24,730 --> 00:04:29,150 Kaya kahit na ito ay huli, makikita mo pa rin makakuha ng credit para sa saklaw ng mga puntos, sa tingin ko. 93 00:04:29,150 --> 00:04:33,730 >> Kaya moral ng kuwento ay, gumawa Siguraduhin na ang iyong psets ay sa on-time. 94 00:04:33,730 --> 00:04:38,350 At kung sila ay hindi sa on-time, alam na ito ay hindi mahusay. 95 00:04:38,350 --> 00:04:41,678 Oo, bago ko ilipat sa, ay hindi magkaroon ng kahit sino anumang mga katanungan tungkol pset feedback? 96 00:04:41,678 --> 00:04:42,178 Oo. 97 00:04:42,178 --> 00:04:43,630 >> Madla: sabihin mo ba kami maaaring i-drop ang isa sa mga psets? 98 00:04:43,630 --> 00:04:44,296 >> ANDI PENG: Oo. 99 00:04:44,296 --> 00:04:47,050 Kaya may siyam psets pangkalahatang sa kabuuan ng semestre. 100 00:04:47,050 --> 00:04:50,610 At kung mayroon kang scope points-- kaya scope ay makatarungan, 101 00:04:50,610 --> 00:04:53,567 medyo marami, ikaw ay sinusubukan ang Ang problema, ikaw ay paglalagay sa oras, 102 00:04:53,567 --> 00:04:56,150 ikaw ay nagpapakita na na sa iyo nagpakita nabasa mo na ang spec. 103 00:04:56,150 --> 00:04:57,191 Iyan ay medyo magkano ang saklaw. 104 00:04:57,191 --> 00:04:59,370 At kung ikaw ay tuparin saklaw ng mga puntos, kami ay 105 00:04:59,370 --> 00:05:03,360 maaaring i-drop ang pinakamababang isa sa labas ng buong saklaw. 106 00:05:03,360 --> 00:05:06,790 Kaya na sa iyong kalamangan sa kumpletuhin at subukan ang bawat pset. 107 00:05:06,790 --> 00:05:10,320 >> Kahit upload-- kung wala sa mga ito sa trabaho, i-upload ang mga ito lahat. 108 00:05:10,320 --> 00:05:13,711 At pagkatapos ay gagamitin namin inaasahan namin na maaaring magbibigay sa iyo ang ilan sa mga puntos pabalik. 109 00:05:13,711 --> 00:05:14,210 Cool. 110 00:05:14,210 --> 00:05:16,780 Anumang iba pang mga katanungan? 111 00:05:16,780 --> 00:05:17,840 Great. 112 00:05:17,840 --> 00:05:21,960 >> Pangalawa, opisina hours-- ng ilang mabilis na mga tala tungkol sa mga oras ng opisina. 113 00:05:21,960 --> 00:05:24,300 Kaya una, dumating ng maaga sa linggo. 114 00:05:24,300 --> 00:05:26,909 Walang isa ay kailanman sa oras ng opisina tuwing Lunes. 115 00:05:26,909 --> 00:05:28,700 Christabel ang dumating sa oras ng opisina kagabi. 116 00:05:28,700 --> 00:05:29,691 Oo, Christabel. 117 00:05:29,691 --> 00:05:32,190 At ano ang mayroon kami sa opisina oras kagabi, Christabel? 118 00:05:32,190 --> 00:05:33,020 >> Madla: Nagkaroon kami ng ice cream. 119 00:05:33,020 --> 00:05:36,160 >> ANDI PENG: So na tama, kami ay nagkaroon ng ice cream sa oras ng opisina kagabi. 120 00:05:36,160 --> 00:05:39,390 Habang hindi ko pangako mo na kakailanganin naming ice cream sa oras ng opisina 121 00:05:39,390 --> 00:05:43,230 bawat linggo, kung ano ang maaari kong pangako sa iyo ay na magkakaroon ng makabuluhang isang 122 00:05:43,230 --> 00:05:45,380 mas mahusay na mag-aaral sa TA ratio. 123 00:05:45,380 --> 00:05:47,650 Tulad ng legit, ito ay tulad ng tatlong sa isa. 124 00:05:47,650 --> 00:05:50,350 Sapagkat, kaibahan na may Huwebes, nakuha mo na ang tungkol sa 150 125 00:05:50,350 --> 00:05:52,830 talagang pagkabalisa sa mga bata at walang ice cream. 126 00:05:52,830 --> 00:05:55,360 At ito lang ang hindi produktibong para sa sinuman. 127 00:05:55,360 --> 00:05:58,730 Kaya moral ng kuwento ay, dumating nang maaga sa mga oras ng opisina at magandang bagay 128 00:05:58,730 --> 00:06:00,310 mangyayari. 129 00:06:00,310 --> 00:06:02,110 >> Gayundin, dumating handa upang magtanong. 130 00:06:02,110 --> 00:06:03,200 Alam mo? 131 00:06:03,200 --> 00:06:05,420 Hindi alintana ng kung ano ang TAS, ako mag-isip, ay sinasabi, 132 00:06:05,420 --> 00:06:10,710 ay nakakakuha kami ng ilang mga mag-aaral na papasok sa Huwebes sa, tulad ng, 10:50 133 00:06:10,710 --> 00:06:15,100 hindi pagkakaroon ng basahin ang spec pagiging tulad tulungan mo ako, tulungan mo ako. 134 00:06:15,100 --> 00:06:18,200 Sa kasamaang palad sa puntong iyon, may hindi marami ang maaari naming gawin upang makatulong sa iyo. 135 00:06:18,200 --> 00:06:19,590 Kaya mangyaring bumalik sa unang bahagi ng linggo. 136 00:06:19,590 --> 00:06:22,040 Halika maaga sa oras ng opisina. 137 00:06:22,040 --> 00:06:23,350 Halika na handa na magtanong. 138 00:06:23,350 --> 00:06:25,310 Tiyakin na ikaw, tulad ng isang mag-aaral, ay kung saan 139 00:06:25,310 --> 00:06:27,620 kailangan mo upang maging sa gayon na ang Maaaring gabay sa iyo TAS kasama, 140 00:06:27,620 --> 00:06:32,850 na kung saan ay kung ano ang mga oras ng opisina dapat na inilaan para sa. 141 00:06:32,850 --> 00:06:37,380 >> Pangalawa, kaya alam ko na propesor nais na sorpresa sa amin sa mga pagsubok. 142 00:06:37,380 --> 00:06:39,439 Nagkaroon na ako ng isang propesor sa mga tulad ng, yo, sa daan, 143 00:06:39,439 --> 00:06:41,230 tandaan na midterm mayroon ka sa susunod na Lunes. 144 00:06:41,230 --> 00:06:42,855 Oo, hindi ko alam kung tungkol na midterm. 145 00:06:42,855 --> 00:06:45,630 Kaya ako pagpunta upang ma-na TA na nagpapaalala sa inyo ang lahat ng pagsusulit na 146 00:06:45,630 --> 00:06:47,270 0-- dahil, alam mo, hindi namin CS. 147 00:06:47,270 --> 00:06:50,730 Ngayon na kami tapos array, makakakuha ka ng kung bakit ito ay pagsusulit 0, hindi magtatanong 1, eh? 148 00:06:50,730 --> 00:06:51,320 SIGE. 149 00:06:51,320 --> 00:06:52,490 Oh, Nakatanggap ako ng ilang chuckles na ang isa. 150 00:06:52,490 --> 00:06:53,120 SIGE. 151 00:06:53,120 --> 00:06:59,710 >> Kaya pagsusulit 0 ay Oktubre 14 kung ikaw ay nasa section Lunes-Miyerkules 152 00:06:59,710 --> 00:07:02,920 at Oktubre 15 kung ikaw ay nasa ang seksyon Martes-Huwebes. 153 00:07:02,920 --> 00:07:05,630 Ito ay hindi akma para sa sa mga mo sa Harvard 154 00:07:05,630 --> 00:07:10,350 who-- tingin ko makikita mo ang lahat maging pagkuha ng iyong mga pagsusulit sa ika-14. 155 00:07:10,350 --> 00:07:13,560 >> Kaya oo, sa susunod na linggo, kung David, sa panayam, pag-uusapan, 156 00:07:13,560 --> 00:07:15,747 oo, kaya tungkol na pagsusulit sa susunod na linggo, ikaw ang lahat 157 00:07:15,747 --> 00:07:17,580 hindi nagulat dahil ikaw ay dumating sa section 158 00:07:17,580 --> 00:07:19,664 at alam mo na ang iyong quiz 0 ay sa loob ng dalawang linggo. 159 00:07:19,664 --> 00:07:21,580 At kami ay may review session at lahat ng bagay. 160 00:07:21,580 --> 00:07:26,360 Kaya huwag mag-alala tungkol sa pagiging natakot para doon. 161 00:07:26,360 --> 00:07:29,890 Ang anumang mga katanungan before-- anumang mga katanungan sa lahat ng tungkol logistical mga isyu, 162 00:07:29,890 --> 00:07:32,591 pagmamarka, mga oras ng opisina, mga seksyon? 163 00:07:32,591 --> 00:07:33,090 Oo. 164 00:07:33,090 --> 00:07:35,100 >> Madla: Kaya ang pagsusulit ay magiging panahon ng panayam? 165 00:07:35,100 --> 00:07:35,766 >> ANDI PENG: Oo. 166 00:07:35,766 --> 00:07:39,460 Kaya ang pagsusulit, tingin ko, ay 60 minuto na inilaan sa na puwang ng oras 167 00:07:39,460 --> 00:07:42,240 na ikaw lang ang dadalhin sa lecture hall. 168 00:07:42,240 --> 00:07:44,810 Kaya hindi mo na kailangang dumating sa on, tulad ng, ang isang random na 07:00. 169 00:07:44,810 --> 00:07:46,140 Lahat ng ito ay mabuti. 170 00:07:46,140 --> 00:07:47,100 Oo. 171 00:07:47,100 --> 00:07:50,060 Cool. 172 00:07:50,060 --> 00:07:50,840 >> Lahat tama. 173 00:07:50,840 --> 00:07:54,330 Kaya kami ay pagpunta sa ipakilala ang isang konsepto sa iyo 174 00:07:54,330 --> 00:08:00,760 this week na si David ay mayroon na uri ng baliw sa lecture ito nakaraang linggo. 175 00:08:00,760 --> 00:08:02,010 Ito ay tinatawag na GDB. 176 00:08:02,010 --> 00:08:05,570 At kung paano marami sa inyo, habang sa ang mga kurso ng pagsulat ng iyong psets, 177 00:08:05,570 --> 00:08:09,981 napansin ang isang malaking button na nagsasabing "Debug" sa tuktok ng iyong IDE? 178 00:08:09,981 --> 00:08:10,480 SIGE. 179 00:08:10,480 --> 00:08:13,770 Kaya ngayon makikita namin talagang makakuha upang makatuklas ang misteryo ng kung ano na button talagang 180 00:08:13,770 --> 00:08:14,270 ay. 181 00:08:14,270 --> 00:08:16,790 At ginagarantiya ko sa inyo, ito ay isang maganda, magandang bagay. 182 00:08:16,790 --> 00:08:20,740 >> Kaya hanggang ngayon, sa tingin ko mayroong nangyaring dalawang bagay 183 00:08:20,740 --> 00:08:23,320 mga mag-aaral ay karaniwang ginagawa kapag debugging psets. 184 00:08:23,320 --> 00:08:27,635 One, alinman sa mga ito idagdag sa printf () - kaya ang bawat ilang mga linya, 185 00:08:27,635 --> 00:08:29,760 idagdag sila sa isang printf () - oh, kung ano ang mga variable na ito? 186 00:08:29,760 --> 00:08:32,551 Oh, kung ano ang mga variable na ito now-- at ang uri ng iyong nakikita sa paglala 187 00:08:32,551 --> 00:08:33,940 ng iyong mga code na ito ay tumatakbo. 188 00:08:33,940 --> 00:08:37,030 O kids gawin ang ikalawang paraan ay na isulat ang mga ito lamang ang buong bagay 189 00:08:37,030 --> 00:08:38,610 at pagkatapos ay pumunta tulad nito sa dulo. 190 00:08:38,610 --> 00:08:39,970 Sana ito gumagana. 191 00:08:39,970 --> 00:08:44,851 Ginagarantiya ko sa iyo, GDB ay mas mahusay sa pareho ng mga pamamaraan. 192 00:08:44,851 --> 00:08:45,350 Oo. 193 00:08:45,350 --> 00:08:46,980 Kaya ito ay ang iyong bagong pinakamatalik na kaibigan. 194 00:08:46,980 --> 00:08:51,780 Dahil ito ay isang magandang bagay na biswal na nagpapakita sa parehong 195 00:08:51,780 --> 00:08:54,850 kung ano ang iyong code ay ginagawa sa isang tiyak na punto 196 00:08:54,850 --> 00:08:57,486 pati na rin ang kung ano ang lahat ng iyong variable ay dala, 197 00:08:57,486 --> 00:08:59,610 tulad ng kung ano ang kanilang mga halaga ay, sa mga tiyak na punto. 198 00:08:59,610 --> 00:09:02,670 At sa ganitong paraan, maaari mong tunay itakda breakpoints sa iyong code. 199 00:09:02,670 --> 00:09:04,350 Maaari kang magpatakbo ng sa pamamagitan ng linya sa pamamagitan ng linya. 200 00:09:04,350 --> 00:09:07,324 At GDB ay na lang ay para sa mo, ipinapakita para sa iyo, 201 00:09:07,324 --> 00:09:09,490 kung ano ang lahat ng iyong mga variable ay, kung ano ang ginagawa nila, 202 00:09:09,490 --> 00:09:10,656 kung ano ang nangyayari sa code. 203 00:09:10,656 --> 00:09:13,240 At sa paraan, ito ay kaya mas madali upang makita ang 204 00:09:13,240 --> 00:09:17,120 kung ano ang nangyayari sa halip ng printf-ing o pagsusulat ang iyong mga pahayag. 205 00:09:17,120 --> 00:09:19,160 >> Kaya gagawin namin ang isang halimbawa ng ito sa ibang pagkakataon. 206 00:09:19,160 --> 00:09:20,660 Kaya ito ay tila medyo abstract. 207 00:09:20,660 --> 00:09:23,490 Huwag mag-alala, ipapakita namin ang mga halimbawa. 208 00:09:23,490 --> 00:09:29,170 At kaya mahalagang, tatlong pinakamalaking, pinaka-ginagamit na mga pagpapaandar na kailangan mo sa GDB 209 00:09:29,170 --> 00:09:32,500 ay ang Susunod, Tumawid, at Hakbang sa mga pindutan. 210 00:09:32,500 --> 00:09:34,860 Pupunta ako sa tumuloy doon, talaga, ngayon. 211 00:09:34,860 --> 00:09:40,930 >> Kaya maaari makita ka guys lahat na o ang dapat kong mag-zoom in ng kaunti? 212 00:09:40,930 --> 00:09:43,220 213 00:09:43,220 --> 00:09:44,470 Sa likod, maaari mong makita na? 214 00:09:44,470 --> 00:09:45,730 Dapat ko bang mag-zoom in? 215 00:09:45,730 --> 00:09:46,480 Kahit kaunti lang? 216 00:09:46,480 --> 00:09:49,390 OK, cool. 217 00:09:49,390 --> 00:09:50,280 Mayroon kaming pumunta. 218 00:09:50,280 --> 00:09:50,960 SIGE. 219 00:09:50,960 --> 00:09:57,000 >> Kaya ko, dito, ang aking pagpapatupad para sa matakaw. 220 00:09:57,000 --> 00:10:01,430 At habang ang isang pulutong ng mga ka guys sinulat matakaw sa habang loop form-- na 221 00:10:01,430 --> 00:10:04,890 ay isang ganap na katanggap-tanggap na paraan upang gawin it-- isa pang paraan upang gawin ito ay upang i 222 00:10:04,890 --> 00:10:06,280 hatiin sa modulo. 223 00:10:06,280 --> 00:10:09,290 Dahil pagkatapos ay maaari kang magkaroon ng iyong halaga at pagkatapos ay ang iyong mga naiwan. 224 00:10:09,290 --> 00:10:11,150 At pagkatapos ay maaari mo lamang idagdag ang lahat ng ito nang magkasama. 225 00:10:11,150 --> 00:10:13,390 Sinusuportahan ba ng logic ng kung ano ang ako paggawa dito magkaroon ng kahulugan sa lahat ng tao, 226 00:10:13,390 --> 00:10:14,117 bago tayo magsimula? 227 00:10:14,117 --> 00:10:16,760 228 00:10:16,760 --> 00:10:17,980 Medyo? 229 00:10:17,980 --> 00:10:18,710 Cool. 230 00:10:18,710 --> 00:10:19,210 Great. 231 00:10:19,210 --> 00:10:21,290 Ito ay isang medyo sexy piraso ng code, nais kong sabihin. 232 00:10:21,290 --> 00:10:23,502 Tulad ng sinabi ko, David, sa magbigay ng panayam, matapos ang ilang panahon, 233 00:10:23,502 --> 00:10:25,960 Makikita mo ang lahat ay magsisimulang makakita ng code bilang isang bagay na maganda. 234 00:10:25,960 --> 00:10:29,950 At kung minsan kapag nakita mo ang maganda code, ito ay tulad ng isang kahanga-hangang pakiramdam. 235 00:10:29,950 --> 00:10:35,410 >> Kaya gayunpaman, habang ang code na ito ay tunay maganda, ito ay hindi gumagana ng maayos. 236 00:10:35,410 --> 00:10:37,750 Tumakbo ni check50 sa mga ito upang ipaalam sa. 237 00:10:37,750 --> 00:10:39,440 Suriin 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 Ay na pset2? 241 00:10:44,990 --> 00:10:46,870 Oo. 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 SIGE. 245 00:10:52,890 --> 00:10:53,900 Kaya tumakbo kami check50. 246 00:10:53,900 --> 00:11:01,550 247 00:11:01,550 --> 00:11:07,170 >> At bilang ay maaaring makita dito sa iyo guys, ito ay bagsak ng ilang mga kaso. 248 00:11:07,170 --> 00:11:10,165 At para sa ilan sa inyo, sa kurso ng paggawa ng iyong hanay ng problema, 249 00:11:10,165 --> 00:11:11,110 ikaw ay tulad ng, ah, bakit hindi ito gumagana. 250 00:11:11,110 --> 00:11:13,318 Bakit ay gumagana ito para sa ilang halaga ngunit hindi para sa iba? 251 00:11:13,318 --> 00:11:17,760 Well, GDB ay pagpunta upang makatulong sa iyo na figure kung bakit ang mga input ay hindi gumagana. 252 00:11:17,760 --> 00:11:18,320 >> SIGE. 253 00:11:18,320 --> 00:11:21,640 Kaya tingnan natin, isa sa mga checks ko ay nanghihina sa check50 254 00:11:21,640 --> 00:11:24,920 ay ang halaga ng 0.41 input. 255 00:11:24,920 --> 00:11:27,830 Kaya na ang mga tamang sagot dapat ay sa pagkuha ay isang 4. 256 00:11:27,830 --> 00:11:33,090 Ngunit sa halip na kung ano ang ako pag-print out ay ang 3-n, na kung saan ay hindi tama. 257 00:11:33,090 --> 00:11:36,190 Patakbuhin lamang ni ito ng mano-mano upang ipaalam sa, lang tiyakin na check50 ay gumagana. 258 00:11:36,190 --> 00:11:36,940 Ni gawin ./greedy Hayaan. 259 00:11:36,940 --> 00:11:40,130 260 00:11:40,130 --> 00:11:43,340 Oops, kailangan kong gumawa ng matakaw. 261 00:11:43,340 --> 00:11:43,840 Mayroon kaming pumunta. 262 00:11:43,840 --> 00:11:44,381 ./greedy Now. 263 00:11:44,381 --> 00:11:46,950 264 00:11:46,950 --> 00:11:47,670 >> Magkano ang utang? 265 00:11:47,670 --> 00:11:49,550 Ni gawin 0.41 Hayaan. 266 00:11:49,550 --> 00:11:52,590 And yep, nakikita natin dito na ito ay outputting 3 267 00:11:52,590 --> 00:11:55,160 kapag ang tamang sagot, sa katunayan, ay dapat na 4. 268 00:11:55,160 --> 00:12:01,460 Kaya sabihin ipasok GDB at makita kung paano namin maaaring pumunta tungkol sa pag-aayos ng problemang ito. 269 00:12:01,460 --> 00:12:03,992 >> Kaya ang unang hakbang sa palaging pag-debug ang iyong code 270 00:12:03,992 --> 00:12:05,950 ay upang itakda ang isang breakpoint, o ng isang punto kung saan mo 271 00:12:05,950 --> 00:12:09,079 gusto ang computer o ang debugger upang simulan ang naghahanap sa. 272 00:12:09,079 --> 00:12:11,120 Kaya kung hindi mo talaga malaman kung ano ang iyong problema ay, 273 00:12:11,120 --> 00:12:14,670 kadalasan, ang pangkaraniwang bagay na gusto naming gawin ay itakda ang aming mga breakpoint sa pangunahing. 274 00:12:14,670 --> 00:12:18,520 Kaya kung maaari makita ang mga ito sa iyo guys red button doon, 275 00:12:18,520 --> 00:12:22,860 yep, noon ay ako pagtatakda ng isang breakpoint para sa mga pangunahing pag-andar. 276 00:12:22,860 --> 00:12:24,130 I-click ko na. 277 00:12:24,130 --> 00:12:26,130 >> At pagkatapos ay ako maaaring pumunta ng hanggang sa button aking Debug. 278 00:12:26,130 --> 00:12:27,036 Pindutin ko ang pindutan na iyon. 279 00:12:27,036 --> 00:12:31,710 280 00:12:31,710 --> 00:12:36,555 Hayaan akong mag-zoom back out kung ako. 281 00:12:36,555 --> 00:12:38,020 Mayroon kaming pumunta. 282 00:12:38,020 --> 00:12:40,730 Kaya kami, dito, ang isang panel sa kanan. 283 00:12:40,730 --> 00:12:43,680 Sorry, guys sa likod, ikaw ay hindi talaga makita talagang mahusay. 284 00:12:43,680 --> 00:12:49,090 Ngunit mahalagang, ang lahat ng karapatang ito panel ay ginagawa 285 00:12:49,090 --> 00:12:53,130 ay iingat subaybayan ng parehong mga naka-highlight line, kung saan ay ang linya ng code 286 00:12:53,130 --> 00:12:56,640 na ang computer ay kasalukuyang tumatakbo, pati na rin ang lahat ng iyong mga variable 287 00:12:56,640 --> 00:12:57,600 dito sa baba. 288 00:12:57,600 --> 00:13:00,487 >> Kaya nakuha mo cents, mga barya, n, lahat ng ipinahayag sa iba't-ibang mga bagay-bagay 289 00:13:00,487 --> 00:13:01,070 sa puntong ito. 290 00:13:01,070 --> 00:13:04,850 Huwag mag-alala, dahil kami ay hindi tunay initialize ang mga ito sa anumang mga variable pa. 291 00:13:04,850 --> 00:13:07,200 Kaya sa iyong computer, ang iyong lang ang nakakakita ng computer, 292 00:13:07,200 --> 00:13:14,376 oh, 32,767 ang huling ginamit na mga function ng na puwang ng memory sa aking computer. 293 00:13:14,376 --> 00:13:16,000 At kaya na kung saan cents sa kasalukuyan ay. 294 00:13:16,000 --> 00:13:19,360 Ngunit walang isang beses na tumakbo ang code, dapat itong maging initialize. 295 00:13:19,360 --> 00:13:24,110 >> Kaya sabihin pumunta sa pamamagitan ng, linya sa pamamagitan ng line, kung ano ang nangyayari sa dito. 296 00:13:24,110 --> 00:13:25,350 SIGE. 297 00:13:25,350 --> 00:13:29,400 Kaya dito ay ang tatlong buttons na ako lang naipaliwanag. 298 00:13:29,400 --> 00:13:34,090 Kayo ay may Play, o ang Run function, button, ikaw ay may mga hakbang na button sa loob, 299 00:13:34,090 --> 00:13:36,600 at magkakaroon ka rin ng Hakbang sa button. 300 00:13:36,600 --> 00:13:41,260 At mahalagang, ang lahat ng tatlong mga ang mga ito pumunta lamang sa pamamagitan ng iyong code 301 00:13:41,260 --> 00:13:42,690 at gawin ang iba't-ibang mga bagay-bagay. 302 00:13:42,690 --> 00:13:45,680 >> Kaya kadalasan, kapag kayo ay ang pag-debug, Hindi natin nais na pindutin lang Play, 303 00:13:45,680 --> 00:13:47,930 dahil Play ay lamang tumakbo ang iyong code sa dulo ng mga ito. 304 00:13:47,930 --> 00:13:49,070 At pagkatapos ay sa iyo ay hindi talaga malaman kung ano ang iyong problema 305 00:13:49,070 --> 00:13:51,432 ay maliban kung magtatakda ka ng maramihang breakpoints. 306 00:13:51,432 --> 00:13:53,890 Kung itinakda mo ang maramihang breakpoints, ito ay awtomatikong lamang 307 00:13:53,890 --> 00:13:56,030 tumakbo mula sa isang breakpoint, sa susunod na, sa susunod. 308 00:13:56,030 --> 00:13:58,030 Ngunit sa kasong ito na namin isa lamang na, dahil tayo 309 00:13:58,030 --> 00:13:59,970 nais na trabaho ang aming paraan mula sa tuktok pababa sa ilalim. 310 00:13:59,970 --> 00:14:04,830 Kaya kami ay pagpunta upang huwag pansinin ang pindutan na ngayon para sa mga layunin ng programang ito. 311 00:14:04,830 --> 00:14:08,230 >> Kaya ang Step paglipas ng function lamang mga hakbang sa paglipas ng bawat isang linya 312 00:14:08,230 --> 00:14:11,510 at nagsasabi sa iyo kung ano ang ang computer ay ginagawa. 313 00:14:11,510 --> 00:14:14,630 Ang Hakbang sa function na napupunta sa aktwal na pag-andar 314 00:14:14,630 --> 00:14:16,000 na sa iyong linya ng code. 315 00:14:16,000 --> 00:14:19,070 Kaya halimbawa, tulad ng printf (), iyon ay isang function, right? 316 00:14:19,070 --> 00:14:21,980 Kung Nais kong pisikal na hakbang sa function printf (), 317 00:14:21,980 --> 00:14:25,610 Gusto ko talagang pumunta sa mga piraso ng code na kung saan printf () ay isinulat at makita 318 00:14:25,610 --> 00:14:26,730 kung ano ang nangyayari doon. 319 00:14:26,730 --> 00:14:29,924 >> Ngunit karaniwan, ipinapalagay namin na ang code na bigyan ka namin gumagana. 320 00:14:29,924 --> 00:14:31,340 Ipinapalagay namin ang printf () ay gumagana. 321 00:14:31,340 --> 00:14:33,170 Ipinapalagay namin na GetInt () ay gumagana. 322 00:14:33,170 --> 00:14:35,170 Kaya walang kailangan upang hakbang sa mga pag-andar. 323 00:14:35,170 --> 00:14:37,170 Ngunit kung may mga pag-andar na sinulat mo sa iyong sarili 324 00:14:37,170 --> 00:14:39,060 na nais mong suriin kung ano ang nangyayari, 325 00:14:39,060 --> 00:14:41,200 Gusto mo nais na hakbang sa na function. 326 00:14:41,200 --> 00:14:43,940 >> Kaya ngayon lang kami sa hakbang sa paglipas ng ito piraso ng code. 327 00:14:43,940 --> 00:14:44,485 Kaya sabihin makita. 328 00:14:44,485 --> 00:14:46,547 Oh, i-print, "Oh hai, kung paano maraming pagbabago ang utang? " 329 00:14:46,547 --> 00:14:47,130 Hindi namin pakialam. 330 00:14:47,130 --> 00:14:49,830 Alam namin na ang gumagana, kaya kami na hakbang sa ibabaw nito. 331 00:14:49,830 --> 00:14:53,290 >> Kaya n, na kung saan ay ang aming float na na namin initialized-- o declared-- 332 00:14:53,290 --> 00:14:56,810 up sa tuktok, hindi namin ngayon pinapantayan na sa GetFloat (). 333 00:14:56,810 --> 00:14:57,810 Kaya ng hakbang sa ibabaw na ipaalam. 334 00:14:57,810 --> 00:14:59,580 At nakita namin sa ibaba dito, ang programa 335 00:14:59,580 --> 00:15:03,360 ay pagdikta sa akin upang input isang halaga. 336 00:15:03,360 --> 00:15:08,580 Kaya ng input hayaan ang mga halaga na gusto namin upang subukan dito, na kung saan ay 0.41. 337 00:15:08,580 --> 00:15:09,160 Great. 338 00:15:09,160 --> 00:15:12,780 >> Kaya ngayon n-- gagawin mo guys makita dito, sa bottom-- ito ay 339 00:15:12,780 --> 00:15:15,140 stored-- dahil tayo hindi pa bilugan, ito ay 340 00:15:15,140 --> 00:15:19,540 naka-imbak sa mga ito tulad ng mga higanteng float na .4099999996, 341 00:15:19,540 --> 00:15:22,550 na kung saan ay malapit na sapat upang aming mga layunin, sa ngayon, sa 0.41. 342 00:15:22,550 --> 00:15:26,090 At pagkatapos ay makikita namin makita sa susunod, bilang namin patuloy tuntong sa programa, 343 00:15:26,090 --> 00:15:29,850 matapos dito, n ay naging bilugan at cents ay naging 41. 344 00:15:29,850 --> 00:15:30,350 Great. 345 00:15:30,350 --> 00:15:32,230 Upang malaman namin na nagtatrabaho sa aming mga rounding ni. 346 00:15:32,230 --> 00:15:34,700 Alam namin na kami ay may mga tamang bilang ng mga cents, 347 00:15:34,700 --> 00:15:36,990 upang malaman namin na iyon ang hindi talaga ang problema. 348 00:15:36,990 --> 00:15:40,050 >> Kaya patuloy kaming tuntong on sa programang ito. 349 00:15:40,050 --> 00:15:40,900 Pumunta kami dito. 350 00:15:40,900 --> 00:15:46,139 At kaya pagkatapos ito linya ng code, kami ay dapat malaman kung gaano karaming mga quarters namin. 351 00:15:46,139 --> 00:15:46,680 Hakbang namin ang higit sa. 352 00:15:46,680 --> 00:15:52,040 At nakita mo kami, sa katunayan, ay may isa quarter dahil na-awas namin 25 353 00:15:52,040 --> 00:15:53,790 mula sa aming unang halaga ng 41. 354 00:15:53,790 --> 00:15:55,890 At kami ay may 16 kaliwa para sa aming cents. 355 00:15:55,890 --> 00:15:58,830 >> Ba ang lahat maunawaan kung paano ang programa ay tuntong sa pamamagitan ng 356 00:15:58,830 --> 00:16:02,980 at bakit cents naging 16 na ngayon at kung bakit, ngayon, barya ay naging 1? 357 00:16:02,980 --> 00:16:04,610 Lahat ng tao sumusunod na Ay na logic? 358 00:16:04,610 --> 00:16:05,110 Cool. 359 00:16:05,110 --> 00:16:07,860 Kaya bilang ng mga puntong ito, ang working program, di ba? 360 00:16:07,860 --> 00:16:09,797 Alam namin na ito ay ginagawa nang eksakto kung ano ang aming nais ito sa. 361 00:16:09,797 --> 00:16:11,880 At kami ay hindi talaga kailangang i-print out, o, anong 362 00:16:11,880 --> 00:16:14,430 ay cents sa puntong ito, kung ano ang mga barya sa puntong ito. 363 00:16:14,430 --> 00:16:17,170 >> Kami ay patuloy na pagpunta sa pamamagitan ng programa. 364 00:16:17,170 --> 00:16:18,100 Tumawid. 365 00:16:18,100 --> 00:16:18,620 Cool. 366 00:16:18,620 --> 00:16:19,700 Pumunta kami sa paglipas ng dimes. 367 00:16:19,700 --> 00:16:20,200 Great. 368 00:16:20,200 --> 00:16:22,367 Nakita namin na ito ay kinuha off $ 0.10 para sa isang magagamit ng lahat. 369 00:16:22,367 --> 00:16:23,450 At ngayon kami ay may dalawang mga barya. 370 00:16:23,450 --> 00:16:25,260 Tama iyan. 371 00:16:25,260 --> 00:16:31,555 >> Pumunta kami ng mahigit sa pennies at makikita natin na nakuha na iniwan namin sa paglipas ng cents. 372 00:16:31,555 --> 00:16:32,680 Hmm, iyan ay kakaiba. 373 00:16:32,680 --> 00:16:37,540 Up dito sa programa, ako ay dapat sa may bawas aking pennies. 374 00:16:37,540 --> 00:16:39,400 Marahil ko lang ay hindi paggawa na linya sa kanan. 375 00:16:39,400 --> 00:16:42,190 At ay, maaari mong makita ang dito, dahil alam namin 376 00:16:42,190 --> 00:16:44,360 na tayo ay tuntong pamamagitan ng mga linya 32 at 33, 377 00:16:44,360 --> 00:16:50,560 na kung saan ang aming programa hindi wasto nagkaroon variable tumakbo. 378 00:16:50,560 --> 00:16:55,136 Kaya maaari naming tumingin at makita, oh, Ako pagbabawas cents dito, 379 00:16:55,136 --> 00:16:57,010 ngunit hindi ako talaga pagdagdag sa aking barya halaga. 380 00:16:57,010 --> 00:16:57,860 Magdaragdag ako sa cents. 381 00:16:57,860 --> 00:17:00,234 At hindi ko nais upang idagdag sa cents, gusto kong idagdag sa mga barya. 382 00:17:00,234 --> 00:17:05,420 Kaya kung babaguhin namin na sa barya, Nakakuha kami ng isang gumaganang program. 383 00:17:05,420 --> 00:17:06,730 Maaari ko bang patakbuhin check50. 384 00:17:06,730 --> 00:17:11,063 Maaari mo lamang lumabas sa labas ng GDB karapatan dito at pagkatapos ay patakbuhin muli check50. 385 00:17:11,063 --> 00:17:11,938 Hindi ko na lang gawin ito. 386 00:17:11,938 --> 00:17:14,822 387 00:17:14,822 --> 00:17:18,480 Kailangan ko bang gumawa ng matakaw. 388 00:17:18,480 --> 00:17:19,940 0.41. 389 00:17:19,940 --> 00:17:22,819 At dito, ito ay pag-print ang mga tamang sagot. 390 00:17:22,819 --> 00:17:26,569 >> Kaya bilang maaari mong makita ang isang lalaki, GDB ay isang talagang malakas na tool 391 00:17:26,569 --> 00:17:29,940 para kapag kami ay may kaya magkano ang code nangyayari at kaya maraming mga variable 392 00:17:29,940 --> 00:17:32,510 na ito ay mahirap para sa atin, tulad ng isang tao, upang subaybayan. 393 00:17:32,510 --> 00:17:35,360 Ang computer, sa GDB debugger, ay may kakayahan 394 00:17:35,360 --> 00:17:37,020 upang subaybayan ang lahat ng bagay. 395 00:17:37,020 --> 00:17:40,480 Alam ko, sa Visionaire, guys marahil ay maaaring magkaroon ng ilang mga hit segmentation faults 396 00:17:40,480 --> 00:17:43,150 dahil kayo ay tumatakbo sa labas ng hangganan ng iyong array. 397 00:17:43,150 --> 00:17:46,510 Sa halimbawa ng Caesar, na ang kung ano mismo ang naipatupad ko dito. 398 00:17:46,510 --> 00:17:50,060 >> Kaya Nakalimutan ko upang suriin para sa ano ang mangyayari kung ako ay 399 00:17:50,060 --> 00:17:52,510 ay hindi magkakaroon ng dalawang argumento command line. 400 00:17:52,510 --> 00:17:53,880 Katatapos ko lamang ay hindi ilalagay sa check iyon. 401 00:17:53,880 --> 00:17:57,380 At kaya kung nagpatakbo ako Debug-- ako magse-set aking breakpoint mag-right doon. 402 00:17:57,380 --> 00:17:58,055 Tumakbo ako Debug. 403 00:17:58,055 --> 00:18:15,880 404 00:18:15,880 --> 00:18:16,550 >> SIGE. 405 00:18:16,550 --> 00:18:17,050 Oo. 406 00:18:17,050 --> 00:18:20,350 Kaya talaga, GDB ay dapat na may nagsabi sa akin doon 407 00:18:20,350 --> 00:18:22,300 ay isang segmentation fault doon. 408 00:18:22,300 --> 00:18:24,883 Hindi ko alam kung ano ang nangyayari may karapatan, ngunit kapag nagpatakbo ako ng ito, 409 00:18:24,883 --> 00:18:25,590 ito ay gumagana. 410 00:18:25,590 --> 00:18:29,410 Kapag nagpatakbo ka ng mga linya ng code sa pamamagitan ng at GDB baka biglang lang umalis sa iyo, 411 00:18:29,410 --> 00:18:31,540 pumunta up at tingnan kung ano ang pulang error ay. 412 00:18:31,540 --> 00:18:33,930 Makikita ito ang magsasabi sa iyo, hey, ikaw nagkaroon ng segmentation fault, 413 00:18:33,930 --> 00:18:38,550 na nangangahulugan na sinubukan mong i-access space sa isang array na ay hindi umiiral. 414 00:18:38,550 --> 00:18:39,050 Oo. 415 00:18:39,050 --> 00:18:43,280 >> Kaya sa susunod na problema itakda sa linggong ito, ikaw guys 416 00:18:43,280 --> 00:18:45,600 ay malamang na magkaroon ng maraming variable lumulutang sa paligid. 417 00:18:45,600 --> 00:18:48,560 Hindi ka pagpunta sa maging sigurado kung ano ang ibig sabihin ng mga ito sa isang tuldok. 418 00:18:48,560 --> 00:18:53,560 Kaya GDB ay talagang makakatulong sa iyo sa pag-uunawa kung ano ang mga ito ay katumbas ng lahat ng 419 00:18:53,560 --> 00:18:55,940 at ng kakayahang mag-biswal. 420 00:18:55,940 --> 00:19:01,995 Kahit sino nalilito Ay sa kung paano anumang na ay nagtatrabaho? 421 00:19:01,995 --> 00:19:02,495 Cool. 422 00:19:02,495 --> 00:19:10,121 423 00:19:10,121 --> 00:19:10,620 Lahat tama. 424 00:19:10,620 --> 00:19:14,260 Kaya matapos na, kami ay pagpunta sa sumisid karapatan 425 00:19:14,260 --> 00:19:17,562 sa apat na iba't ibang mga uri ng mga uri para sa linggong ito. 426 00:19:17,562 --> 00:19:19,520 Ilan sa inyo, first sa lahat, bago tayo magsimula, 427 00:19:19,520 --> 00:19:23,020 nabasa ko ang buong spec para pset3? 428 00:19:23,020 --> 00:19:23,824 SIGE. 429 00:19:23,824 --> 00:19:24,740 Ako ay maipagmamalaki ng sa iyo guys. 430 00:19:24,740 --> 00:19:29,110 Iyan ay tulad ng kalahati ng mga klase, na ay makabuluhang higit sa huling pagkakataon. 431 00:19:29,110 --> 00:19:33,950 >> Kaya iyan, dahil kapag makipag-usap namin tungkol sa mga nilalaman 432 00:19:33,950 --> 00:19:36,170 sa lecture-- o sorry, sa section-- gusto ko 433 00:19:36,170 --> 00:19:38,210 na may kaugnayan sa isang pulutong ng mga na bumalik sa kung ano ang pset ay 434 00:19:38,210 --> 00:19:40,210 at kung paano mo nais na ipatupad na sa iyong pset. 435 00:19:40,210 --> 00:19:42,400 Kaya't kung ikaw ay dumating sa pagkakaroon basahin ang spec, makikita ito 436 00:19:42,400 --> 00:19:45,510 maging isang pulutong mas madali para sa iyo upang maunawaan kung ano ang sinasabi ko kapag sinasabi ko, 437 00:19:45,510 --> 00:19:48,720 oh hey, ito ay maaaring maging isang tunay na ito magandang lugar upang ipatupad ang uri na ito. 438 00:19:48,720 --> 00:19:52,870 Kaya mga mo na nabasa ko ang pagsasapalaran alam na, bilang bahagi ng iyong pset, 439 00:19:52,870 --> 00:19:54,900 ikaw ay pagpunta sa may sa magsulat ng isang uri ng pag-uuri. 440 00:19:54,900 --> 00:19:58,670 Kaya ito ay maaaring maging kapaki-pakinabang para sa isang pulutong ng sa iyo ngayon. 441 00:19:58,670 --> 00:20:01,760 >> Kaya makikita namin magsimula sa, mahalagang, ang pinaka-simpleng uri 442 00:20:01,760 --> 00:20:04,580 ng mga uri, ang uri ng pagpili. 443 00:20:04,580 --> 00:20:06,800 Ang tipikal na algorithm para sa kung paano gusto namin pumunta tungkol sa mga ito 444 00:20:06,800 --> 00:20:10,460 is-- nagpatuloy si David sa pamamagitan ng mga lahat sa lecture, kaya ko makikita mabilis ilipat kasama 445 00:20:10,460 --> 00:20:13,900 here-- ay mahalagang, ikaw magkaroon ng isang hanay ng mga halaga. 446 00:20:13,900 --> 00:20:17,170 At pagkatapos mo ang Pinakamaliit unsorted halaga 447 00:20:17,170 --> 00:20:20,200 at magpalit ka na ng halaga sa ang unang unsorted halaga. 448 00:20:20,200 --> 00:20:22,700 At pagkatapos mo lamang panatilihin ang paulit-ulit na sa ibang bahagi ng iyong listahan. 449 00:20:22,700 --> 00:20:25,740 >> At narito ang isang visual na paliwanag ng kung paano na gumagana. 450 00:20:25,740 --> 00:20:30,460 Kaya halimbawa, kung kami ay upang simulan may isang hanay ng limang mga sangkap, index 451 00:20:30,460 --> 00:20:35,910 0 hanggang 4, na may 3, 5, 2, 6, at 4 na mga halaga inilagay sa array-- kaya sa ngayon, 452 00:20:35,910 --> 00:20:38,530 lang kami ng pagpunta sa ipalagay na ang mga ito ang lahat ng unsorted 453 00:20:38,530 --> 00:20:41,130 dahil hindi pa namin nasubukan kung hindi man. 454 00:20:41,130 --> 00:20:44,130 >> Kaya kung paano gagawin ang isang uri seleksyon trabaho ay na gagawin muna ito 455 00:20:44,130 --> 00:20:46,800 tumakbo sa pamamagitan ng kabuuan ng unsorted array. 456 00:20:46,800 --> 00:20:49,120 Mas piliin ang pinakamaliit na halaga. 457 00:20:49,120 --> 00:20:51,750 Sa kasong ito, 3, right ngayon, ay ang pinakamaliit. 458 00:20:51,750 --> 00:20:52,680 Ito ay makakakuha ng hanggang 5. 459 00:20:52,680 --> 00:20:55,620 Nope, 5 ay hindi mas malaki than-- o paumanhin, ay hindi mas than-- 3. 460 00:20:55,620 --> 00:20:57,779 Kaya ang minimum na halaga ay pa rin 3. 461 00:20:57,779 --> 00:20:58,695 At pagkatapos mong makakuha ng hanggang 2. 462 00:20:58,695 --> 00:21:00,990 Ang computer na nakikita, oh, 2 ay mas mababa sa 3. 463 00:21:00,990 --> 00:21:02,750 2 ay dapat na ngayon ay ang minimum na halaga. 464 00:21:02,750 --> 00:21:06,630 At kaya 2 swaps sa na unang halaga. 465 00:21:06,630 --> 00:21:10,702 >> Kaya pagkatapos ng isa pass, namin katunayan makita na ang 2 at ang 3 ay swapped. 466 00:21:10,702 --> 00:21:13,910 At lamang kami ay pagpunta sa patuloy na paggawa ito muli gamit ang natitirang bahagi ng array. 467 00:21:13,910 --> 00:21:17,660 Kaya kami ay pagpunta upang tumakbo lamang sa pamamagitan ng ang huling apat na ini-index ng array. 468 00:21:17,660 --> 00:21:20,670 Susubukan naming makita na ang 3 ay mga susunod na minimum na halaga. 469 00:21:20,670 --> 00:21:23,240 Kaya kami ay pagpunta sa swap na may 4 na. 470 00:21:23,240 --> 00:21:26,900 At pagkatapos lamang kami ay pagpunta sa panatilihin tumatakbo sa pamamagitan ng hanggang sa, sa huli, ikaw 471 00:21:26,900 --> 00:21:33,730 makapunta sa isang inayos array na 2, 3, 4, 5, at 6 ay pinagsunod-sunod sa lahat. 472 00:21:33,730 --> 00:21:37,530 Ba ang lahat maunawaan ang lohika ng kung paano gumagana ang isang uri ng pagpili? 473 00:21:37,530 --> 00:21:39,669 >> Ikaw lamang ang ilang mga uri ng isang minimum na halaga. 474 00:21:39,669 --> 00:21:41,210 Ikaw ay nag-iingat subaybayan ng kung ano na. 475 00:21:41,210 --> 00:21:45,170 At kapag nalaman mo ito, swap mo ito sa unang halaga sa array-- 476 00:21:45,170 --> 00:21:48,740 o, hindi ito ang unang value-- ang susunod na halaga sa array. 477 00:21:48,740 --> 00:21:50,150 Cool. 478 00:21:50,150 --> 00:21:55,460 >> Kaya bilang mo guys uri ng Nakita mula sa isang maikling sulyap, 479 00:21:55,460 --> 00:21:58,450 kami ay pagpunta sa Pseudocode this out. 480 00:21:58,450 --> 00:22:02,510 Kaya't kung ikaw guys sa likod nais na bumuo ng isang grupo, lahat ng tao sa isang table 481 00:22:02,510 --> 00:22:06,170 maaaring bumuo ng isang maliit na partner, pupuntahan ko upang bigyan ka ng mga guys tulad ng tatlong minuto 482 00:22:06,170 --> 00:22:08,190 upang makipag-usap lamang sa pamamagitan ng ang logic, sa wikang Ingles, 483 00:22:08,190 --> 00:22:14,161 ng kung paano namin maaaring magagawang ipatupad pseudocode na magsulat ng isang uri selection. 484 00:22:14,161 --> 00:22:14,910 At may kendi. 485 00:22:14,910 --> 00:22:16,118 Mangyari lamang na dumating up at makakuha ng kendi. 486 00:22:16,118 --> 00:22:19,520 Kung ikaw ay nasa likod at gusto mong kendi, maaari kong magtapon ng kendi sa inyo. 487 00:22:19,520 --> 00:22:22,850 Sa totoo lang, gawin you-- cool. 488 00:22:22,850 --> 00:22:23,552 Pasensya na. 489 00:22:23,552 --> 00:22:26,751 490 00:22:26,751 --> 00:22:27,250 SIGE. 491 00:22:27,250 --> 00:25:23,880 492 00:25:23,880 --> 00:25:27,140 >> Kaya kung nais namin na, tulad ng isang klase, write pseudocode 493 00:25:27,140 --> 00:25:30,466 para sa kung paano ang isa ay maaaring lapitan ang problemang ito, lamang mag-atubili. 494 00:25:30,466 --> 00:25:32,340 Kukunin ko pumunta lamang sa paligid at, sa pagkakasunud-sunod, tanungin grupo 495 00:25:32,340 --> 00:25:35,065 para sa susunod na linya ng kung ano ang dapat naming gawin. 496 00:25:35,065 --> 00:25:37,840 Kaya kung nais mong guys na simulan off, ano ang unang bagay 497 00:25:37,840 --> 00:25:40,600 na gawin kapag sinusubukan mong ipatupad ang isang paraan upang malutas ang program na ito 498 00:25:40,600 --> 00:25:43,480 upang pili uriin isang listahan? 499 00:25:43,480 --> 00:25:46,349 Sabihin lamang ipagpalagay natin magkaroon ng isang array, ang lahat ng karapatan? 500 00:25:46,349 --> 00:25:49,088 >> Madla: Gusto mong gumawa ng ilang mga uri ng [hindi marinig] na ikaw ay 501 00:25:49,088 --> 00:25:50,420 tumatakbo sa pamamagitan ng iyong buong array. 502 00:25:50,420 --> 00:25:51,128 >> ANDI PENG: Kanan. 503 00:25:51,128 --> 00:25:54,100 Kaya ikaw ay pagpunta sa gusto mong umulit sa pamamagitan ng bawat space, di ba? 504 00:25:54,100 --> 00:26:05,490 So, malaki. 505 00:26:05,490 --> 00:26:08,600 Kung ikaw guys na nais na magbigay sa akin ang susunod line-- oo, sa likod. 506 00:26:08,600 --> 00:26:11,414 507 00:26:11,414 --> 00:26:13,290 >> Madla: Suriin ang mga ito lahat para sa pinakamaliit na. 508 00:26:13,290 --> 00:26:14,248 >> ANDI PENG: Mayroon kaming pumunta. 509 00:26:14,248 --> 00:26:17,438 Kaya gusto namin upang pumunta sa pamamagitan at suriin upang makita kung ano ang minimum na halaga ay, di ba? 510 00:26:17,438 --> 00:26:22,110 511 00:26:22,110 --> 00:26:24,840 Pupunta ako sa paikliin na sa "min." 512 00:26:24,840 --> 00:26:27,658 Ano ang gusto mong guys na gawin pagkatapos nakakita ka ng minimum na halaga? 513 00:26:27,658 --> 00:26:28,533 >> Madla: [hindi marinig] 514 00:26:28,533 --> 00:26:29,942 515 00:26:29,942 --> 00:26:33,150 ANDI PENG: Kaya ikaw ay pagpunta sa nais na lumipat ito sa unang ng na array, 516 00:26:33,150 --> 00:26:33,650 right? 517 00:26:33,650 --> 00:26:45,120 518 00:26:45,120 --> 00:26:46,850 Iyon ang simula, ako pagpunta sa sabihin. 519 00:26:46,850 --> 00:26:47,220 Lahat tama. 520 00:26:47,220 --> 00:26:50,386 Kaya ngayon na ikaw ay swapped ang unang isa, ano ang gusto mong gawin pagkatapos na? 521 00:26:50,386 --> 00:26:54,840 Kaya ngayon ay alam natin na ang isang ito dito ay dapat na ang pinakamaliit na halaga, di ba? 522 00:26:54,840 --> 00:26:58,310 Pagkatapos ay mayroon kang isang karagdagang pahinga ng array na unsorted. 523 00:26:58,310 --> 00:27:01,569 Kaya kung ano ang gusto mong gawin dito, kung ikaw guys nais na magbigay sa akin ang mga susunod na linya? 524 00:27:01,569 --> 00:27:04,610 Madla: Kaya nga ang gusto mong umulit sa pamamagitan ng mga naiwan ng array. 525 00:27:04,610 --> 00:27:05,276 ANDI PENG: Oo. 526 00:27:05,276 --> 00:27:09,857 At kaya kung ano ang ibig iterating sa pamamagitan ng uri ng magpahiwatig kami ay marahil na kailangan? 527 00:27:09,857 --> 00:27:10,440 Anong uri of-- 528 00:27:10,440 --> 00:27:12,057 >> Madla: Oh, ang isang karagdagang variable? 529 00:27:12,057 --> 00:27:13,890 ANDI PENG: Malamang isa pa para sa loop, di ba? 530 00:27:13,890 --> 00:27:28,914 Kaya marahil kami ay pagpunta sa gusto upang umulit through-- malaki. 531 00:27:28,914 --> 00:27:31,830 At pagkatapos ikaw ay pagpunta sa bumalik at marahil suriin muli ang minimum, 532 00:27:31,830 --> 00:27:32,100 right? 533 00:27:32,100 --> 00:27:34,975 At ikaw ay pagpunta upang panatilihin ang paulit-ulit na ito, dahil ang mga loop lamang ang pagpunta 534 00:27:34,975 --> 00:27:36,010 upang panatilihing tumatakbo, di ba? 535 00:27:36,010 --> 00:27:39,190 >> Kaya bilang ka guys ay maaaring makita, kami ay Mayroon lamang ng isang pangkalahatang pseudocode 536 00:27:39,190 --> 00:27:41,480 ng kung paano namin gusto ang program na ito upang tumingin. 537 00:27:41,480 --> 00:27:46,646 Umulit na ito dito, kung ano ang ginagawa namin karaniwang kailangan upang isulat sa aming code 538 00:27:46,646 --> 00:27:49,270 kung gusto naming upang umulit sa pamamagitan ng isang array, kung anong uri ng istraktura? 539 00:27:49,270 --> 00:27:51,030 Sa tingin ko Christabel na sinabi ito bago. 540 00:27:51,030 --> 00:27:51,500 >> Madla: A para sa loop. 541 00:27:51,500 --> 00:27:52,160 >> ANDI PENG: A para sa loop? 542 00:27:52,160 --> 00:27:52,770 Mismong. 543 00:27:52,770 --> 00:27:56,060 Kaya ito ay marahil pagpunta sa isang para sa loop. 544 00:27:56,060 --> 00:27:59,240 Ano ang isang check dito pagpunta upang magpahiwatig? 545 00:27:59,240 --> 00:28:02,536 Kadalasan, kung nais mong suriin kung ang isang bagay ay isang bagay else-- 546 00:28:02,536 --> 00:28:03,270 >> Madla: Kung. 547 00:28:03,270 --> 00:28:06,790 >> ANDI PENG: Isang kung, di ba? 548 00:28:06,790 --> 00:28:10,790 At pagkatapos ay ang swap dito, ipapakita namin pumunta sa ibang pagkakataon, dahil David 549 00:28:10,790 --> 00:28:12,770 dumaan na sa lecture rin. 550 00:28:12,770 --> 00:28:14,580 At pagkatapos ay ang ikalawang umulit implies-- 551 00:28:14,580 --> 00:28:15,120 >> Madla: Ang isa pang para sa loop. 552 00:28:15,120 --> 00:28:16,745 >> ANDI PENG: --another para sa loop, eksakto. 553 00:28:16,745 --> 00:28:19,870 554 00:28:19,870 --> 00:28:22,000 Kaya kung kami ay naghahanap sa tama ito, kami 555 00:28:22,000 --> 00:28:24,680 maaaring makita na hindi namin marahil pagpunta sa kailangan ng isang nested para sa loop 556 00:28:24,680 --> 00:28:28,330 sa isang kondisyon na pahayag sa doon at pagkatapos ng isang aktwal na piraso ng code na 557 00:28:28,330 --> 00:28:31,360 pagpunta sa swap ang mga halaga. 558 00:28:31,360 --> 00:28:35,980 Kaya ko na sa pangkalahatan ay lamang na nakasulat isang pseudocode code dito. 559 00:28:35,980 --> 00:28:38,910 At pagkatapos ay aktwal na kami ay pagpunta sa pisikal na, tulad ng isang klase, 560 00:28:38,910 --> 00:28:40,700 subukan upang ipatupad ito ngayon. 561 00:28:40,700 --> 00:28:42,486 Bumalik tayo sa ganitong IDE. 562 00:28:42,486 --> 00:28:49,243 563 00:28:49,243 --> 00:28:50,230 >> Naku. 564 00:28:50,230 --> 00:28:51,754 Bakit na not-- may ito ay. 565 00:28:51,754 --> 00:28:52,253 SIGE. 566 00:28:52,253 --> 00:28:55,834 567 00:28:55,834 --> 00:28:57,500 Paumanhin, hayaan mo akong subukan na mag-zoom in pa ng kaunti. 568 00:28:57,500 --> 00:28:59,310 Mayroon kaming pumunta. 569 00:28:59,310 --> 00:29:05,060 Lahat ako paggawa dito ay na aking nilikha isang programa na tinatawag na "pagpili / sort.c." 570 00:29:05,060 --> 00:29:10,860 Lumikha ako ng isang array ng siyam halaga, 4, 8, 2, 1, 6, 9, 7, 5, 3. 571 00:29:10,860 --> 00:29:14,370 Sa kasalukuyan, tulad ng maaari mong makita, ang mga ito ay unordered. 572 00:29:14,370 --> 00:29:17,880 n ay magiging ang numero na ay nagsasabi sa iyo ang halaga ng mga halaga 573 00:29:17,880 --> 00:29:18,920 mayroon ka sa iyong array. 574 00:29:18,920 --> 00:29:20,670 Sa kasong ito, kami ay may siyam na mga halaga. 575 00:29:20,670 --> 00:29:23,760 At lamang ako got isang para sa loop dito na mga print out ang unsorted array. 576 00:29:23,760 --> 00:29:28,370 >> At sa dulo, nakuha rin ako ng isang para sa loop na ang mga kopya lamang ito muli. 577 00:29:28,370 --> 00:29:32,070 Kaya theoretically, kung ang program na ito ay gumagana nang tama, sa dulo, 578 00:29:32,070 --> 00:29:35,670 dapat mong makita ang isang naka-print para sa loop na kung saan ang 1, 2, 3, 4, 5, 6, 7, 8, 579 00:29:35,670 --> 00:29:39,310 9 ay ang lahat ng tama sa order. 580 00:29:39,310 --> 00:29:43,410 >> Kaya namin nakuha ang aming pseudocode dito. 581 00:29:43,410 --> 00:29:46,090 Gusto ba to-- lang ako pagpunta sa pumunta humingi ng volunteers-- 582 00:29:46,090 --> 00:29:49,540 sabihin sa akin kung ano mismo ang mag-type kung gusto naming, una, umulit lang 583 00:29:49,540 --> 00:29:52,840 sa pamamagitan ng simula ng array? 584 00:29:52,840 --> 00:29:55,204 Ano ang mga linya ng code Ako marahil pagpunta sa kailangan dito? 585 00:29:55,204 --> 00:29:56,990 >> Madla: [hindi marinig] 586 00:29:56,990 --> 00:29:59,010 >> ANDI PENG: Oo, sa palagay libreng to-- Paumanhin, ikaw ay 587 00:29:59,010 --> 00:30:02,318 Hindi mo na kailangang tumayo up-- pakiramdam free na itaas ang iyong boses ng kaunti. 588 00:30:02,318 --> 00:30:08,190 >> Madla: Para sa int i katumbas 0-- 589 00:30:08,190 --> 00:30:10,690 >> ANDI PENG: Oo, mabuti. 590 00:30:10,690 --> 00:30:15,220 >> Madla: i ay mas mababa sa haba ng array. 591 00:30:15,220 --> 00:30:19,630 >> ANDI PENG: Kaya panatilihin sa bale dito, dahil kami ay 592 00:30:19,630 --> 00:30:23,060 hindi magkaroon ng isang function na Sinasabi sa amin ang haba ng isang array, 593 00:30:23,060 --> 00:30:25,790 kami ay mayroon ng isang halaga na ang mga tindahan na iyon. 594 00:30:25,790 --> 00:30:27,920 Right? 595 00:30:27,920 --> 00:30:31,010 Isa pang bagay na panatilihin sa mind-- sa isang array 596 00:30:31,010 --> 00:30:33,940 ng siyam na mga halaga, ano ang mga ini-index? 597 00:30:33,940 --> 00:30:38,720 Sabihin lang sabihin ang array na ito ay 0 hanggang 3. 598 00:30:38,720 --> 00:30:41,500 Ang makikita mo na ang huling index ay aktwal na 3. 599 00:30:41,500 --> 00:30:45,530 Ito ay hindi 4, kahit na may apat na mga halaga sa array. 600 00:30:45,530 --> 00:30:49,866 >> Kaya sa dito, mayroon kaming upang maging maingat ng kung ano ang aming mga kondisyon para sa ang haba 601 00:30:49,866 --> 00:30:50,490 ay magiging. 602 00:30:50,490 --> 00:30:51,948 >> Madla: Hindi ba ito ay n minus 1? 603 00:30:51,948 --> 00:30:54,440 ANDI PENG: Ito ay pagpunta n minus 1, eksakto. 604 00:30:54,440 --> 00:30:57,379 Ba na magkaroon ng kahulugan, bakit ito ay n minus 1, lahat ng tao? 605 00:30:57,379 --> 00:30:58,920 Ito ay dahil ang array ay zero-index. 606 00:30:58,920 --> 00:31:02,010 Sila magsimula sa 0 at tumakbo hanggang sa n minus 1. 607 00:31:02,010 --> 00:31:03,210 Oo, ito ay isang bit mapanlinlang. 608 00:31:03,210 --> 00:31:03,730 SIGE. 609 00:31:03,730 --> 00:31:05,929 At then-- 610 00:31:05,929 --> 00:31:08,054 Madla: Isnt'1 na nakuha na pag-aalaga ng kahit na, 611 00:31:08,054 --> 00:31:11,400 sa pamamagitan ng hindi lamang sinasabi "mas mababa sa o katumbas ng "at lamang na nagsasabing" mas mababa kaysa? " 612 00:31:11,400 --> 00:31:13,108 >> ANDI PENG: Iyan ay isang talagang mahusay na tanong. 613 00:31:13,108 --> 00:31:13,630 So, yes. 614 00:31:13,630 --> 00:31:17,410 Ngunit din, ang mga paraan na hindi namin pagpapatupad ng pagsuri ng mga karapatan, 615 00:31:17,410 --> 00:31:19,120 kailangan mong ihambing ang dalawang mga halaga. 616 00:31:19,120 --> 00:31:21,009 Kaya talagang gusto ninyong iwan ang "sa" walang laman. 617 00:31:21,009 --> 00:31:23,050 Dahil kung ikaw ay ihambing ang isang ito, hindi ka pagpunta 618 00:31:23,050 --> 00:31:25,530 magkaroon ng anumang bagay matapos na ito upang ihambing sa, right? 619 00:31:25,530 --> 00:31:27,460 Oo. 620 00:31:27,460 --> 00:31:29,297 Kaya i ++. 621 00:31:29,297 --> 00:31:30,380 Magdagdag ng aming mga bracket sa Hayaan. 622 00:31:30,380 --> 00:31:30,880 Oops. 623 00:31:30,880 --> 00:31:33,950 624 00:31:33,950 --> 00:31:34,710 Great. 625 00:31:34,710 --> 00:31:39,117 Kaya kami ay may simula ng aming mga panlabas na loop. 626 00:31:39,117 --> 00:31:41,450 Kaya ngayon marahil gusto naming lumikha ng isang variable para sa pagsunod 627 00:31:41,450 --> 00:31:43,085 subaybayan ng pinakamaliit na halaga, di ba? 628 00:31:43,085 --> 00:31:45,751 Nais ba ng sinuman upang bigyan ako ang linya ng code na gawin iyon? 629 00:31:45,751 --> 00:31:48,700 630 00:31:48,700 --> 00:31:53,570 Ano ang kailangan namin kung kami ay pagpunta sa nais na mag-imbak ng isang bagay? 631 00:31:53,570 --> 00:31:55,047 >> Right. 632 00:31:55,047 --> 00:31:57,630 Siguro isang mas mahusay na pangalan para sa na Gusto be-- "temp" lubos works-- 633 00:31:57,630 --> 00:32:00,655 marahil ng isang mas aptly pinangalanan ay magiging, kung nais namin na ang pinakamaliit value-- 634 00:32:00,655 --> 00:32:01,624 >> Madla: Min. 635 00:32:01,624 --> 00:32:02,790 ANDI PENG: min, doon pumunta kami. 636 00:32:02,790 --> 00:32:05,230 min ay magiging mabuti. 637 00:32:05,230 --> 00:32:08,340 At kaya dito, kung ano ang ginagawa namin Gusto upang magpasimula ito sa? 638 00:32:08,340 --> 00:32:09,620 Ito ay isang bit mapanlinlang. 639 00:32:09,620 --> 00:32:13,580 Dahil sa ngayon sa simula ng array na ito, 640 00:32:13,580 --> 00:32:15,730 hindi mo pa tumingin sa anumang bagay, di ba? 641 00:32:15,730 --> 00:32:19,200 Kaya kung ano, nang awtomatiko, kung hindi namin lamang sa i katumbas ng 0, 642 00:32:19,200 --> 00:32:22,302 kung ano ang gusto namin upang magpasimula ang aming unang minimum na halaga sa? 643 00:32:22,302 --> 00:32:22,802 Madla: i. 644 00:32:22,802 --> 00:32:24,790 ANDI PENG: i, eksakto. 645 00:32:24,790 --> 00:32:27,040 Christabel, bakit gusto namin upang magpasimula ito upang i? 646 00:32:27,040 --> 00:32:28,510 >> Madla: Dahil, well, kami ay nagsisimula sa 0. 647 00:32:28,510 --> 00:32:31,660 Kaya dahil mayroon kaming walang upang ihambing ito sa, ang minimum ay humantong sa pagiging 0. 648 00:32:31,660 --> 00:32:32,451 >> ANDI PENG: Eksakto. 649 00:32:32,451 --> 00:32:34,400 Kaya siya ay akmang-akma. 650 00:32:34,400 --> 00:32:36,780 Dahil kami ay hindi tunay tumingin sa kahit ano pa, 651 00:32:36,780 --> 00:32:38,680 hindi namin alam kung ano ang aming mga minimum na halaga ay. 652 00:32:38,680 --> 00:32:41,960 Gusto naming upang magpasimula lamang ito sa i, na kung saan, sa kasalukuyan, ay dito mismo. 653 00:32:41,960 --> 00:32:44,750 At habang patuloy naming ilipat pababa ang array na ito, 654 00:32:44,750 --> 00:32:48,122 kami ay makikita na, sa bawat karagdagang pass, dinadagdagan i. 655 00:32:48,122 --> 00:32:49,830 At kaya sa puntong iyon, i ay marahil pagpunta 656 00:32:49,830 --> 00:32:52,329 na gusto mong maging ang minimum, dahil ito ay pagpunta sa maging kahit anong 657 00:32:52,329 --> 00:32:54,520 ay ang simula ng unsorted array. 658 00:32:54,520 --> 00:32:55,270 Cool. 659 00:32:55,270 --> 00:32:58,720 >> Kaya ngayon gusto naming idagdag isang para sa loop dito na 660 00:32:58,720 --> 00:33:03,225 pagpunta sa ulitin sa pamamagitan ng unsorted, o sa ibang bahagi ng array na ito. 661 00:33:03,225 --> 00:33:05,808 Nais ba ng sinuman upang bigyan ako ng isang linya ng code na gawin iyon? 662 00:33:05,808 --> 00:33:08,870 663 00:33:08,870 --> 00:33:11,330 Hint-- ano ang kailangan pababa namin dito? 664 00:33:11,330 --> 00:33:17,320 665 00:33:17,320 --> 00:33:18,820 Ano kaya ang nangyari upang pumunta sa para sa loop? 666 00:33:18,820 --> 00:33:19,465 Oo. 667 00:33:19,465 --> 00:33:21,590 Madla: Kaya gusto namin nais na magkaroon ng isang iba't ibang mga integer, 668 00:33:21,590 --> 00:33:25,080 dahil kami ay tumatakbo sa pamamagitan ng pahinga ng array sa halip na ang i, kaya siguro 669 00:33:25,080 --> 00:33:25,760 j. 670 00:33:25,760 --> 00:33:27,301 >> ANDI PENG: Oo, j tunog mabuti sa akin. 671 00:33:27,301 --> 00:33:27,850 Katumbas? 672 00:33:27,850 --> 00:33:33,930 >> Madla: Kaya ay i plus 1, dahil ikaw ay simula sa susunod na halaga. 673 00:33:33,930 --> 00:33:40,395 At pagkatapos ay sa end-- kaya muli, j ay mas mababa sa n minus 1, at pagkatapos 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 >> At pagkatapos in dito, kami ay pagpunta sa nais upang suriin upang makita kung ang aming mga kondisyon ay natutugunan, 677 00:33:52,750 --> 00:33:53,250 right? 678 00:33:53,250 --> 00:33:55,740 Dahil ang nais mong baguhin ang minimum na halaga 679 00:33:55,740 --> 00:33:58,700 kung ito ay aktwal na mas maliit kaysa sa kung ano ikaw ay paghahambing nito sa, right? 680 00:33:58,700 --> 00:34:01,146 Kaya kung ano ang kami ay pagpunta sa gusto dito? 681 00:34:01,146 --> 00:34:04,160 682 00:34:04,160 --> 00:34:04,897 Suriin upang makita. 683 00:34:04,897 --> 00:34:06,730 Anong uri ng mga pahayag kami ay marahil pagpunta 684 00:34:06,730 --> 00:34:08,389 gusto ti gamitin kung tayo nais na suriin ang isang bagay? 685 00:34:08,389 --> 00:34:09,360 >> Madla: Isang pahayag kung. 686 00:34:09,360 --> 00:34:10,485 >> ANDI PENG: Ang isang kung pahayag. 687 00:34:10,485 --> 00:34:13,155 Kaya if-- at kung ano ang magiging kondisyon na gusto natin sa loob 688 00:34:13,155 --> 00:34:13,988 ng aming mga pahayag kung? 689 00:34:13,988 --> 00:34:18,255 690 00:34:18,255 --> 00:34:22,960 >> Madla: Kung ang halaga ng j ay mas mababa kaysa sa halaga ng i-- 691 00:34:22,960 --> 00:34:24,600 >> ANDI PENG: Eksakto. 692 00:34:24,600 --> 00:34:27,480 Kaya if-- kaya ito array ay tinatawag na "array." 693 00:34:27,480 --> 00:34:27,980 Great. 694 00:34:27,980 --> 00:34:30,465 Kaya kung array-- kung ano ang na? 695 00:34:30,465 --> 00:34:31,090 Sabihin na muli. 696 00:34:31,090 --> 00:34:39,590 >> Madla: Kung array-j ay mas mababa sa array-i, at pagkatapos namin ay magbabago sa min. 697 00:34:39,590 --> 00:34:41,590 Kaya ang min ay j. 698 00:34:41,590 --> 00:34:44,590 699 00:34:44,590 --> 00:34:47,249 >> ANDI PENG: Ba na magkaroon ng kahulugan? 700 00:34:47,249 --> 00:34:48,670 SIGE. 701 00:34:48,670 --> 00:34:52,929 At ngayon down dito, kami ay tunay na nais na ipatupad ang swap, di ba? 702 00:34:52,929 --> 00:34:58,285 Kaya isipin, sa panayam, na si David, nang siya ay sinusubukan upang magpalitan the-- kung ano ang 703 00:34:58,285 --> 00:34:59,996 it-- orange juice at milk-- 704 00:34:59,996 --> 00:35:01,150 >> Madla: Iyon ay gross. 705 00:35:01,150 --> 00:35:02,816 >> ANDI PENG: Oo, na ay uri ng gross. 706 00:35:02,816 --> 00:35:05,310 Ngunit ito ay isang medyo magandang konsepto ng oras na nagpapakita. 707 00:35:05,310 --> 00:35:08,430 Kaya sa tingin ng iyong mga halaga dito. 708 00:35:08,430 --> 00:35:10,794 Nakuha mo na ang isang array ng min, isang array ng i, 709 00:35:10,794 --> 00:35:12,460 o ano pa man namin na sinusubukan mong magpalit dito. 710 00:35:12,460 --> 00:35:15,310 At marahil ay hindi maaaring ibuhos ang mga ito sa bawat isa at sa parehong oras, tama? 711 00:35:15,310 --> 00:35:17,180 Kaya kung ano ang kami ay pagpunta na kailangan upang lumikha dito 712 00:35:17,180 --> 00:35:19,126 upang magpalitan ng tama ang mga halaga? 713 00:35:19,126 --> 00:35:19,820 >> Madla: Ang isang pansamantalang variable. 714 00:35:19,820 --> 00:35:21,370 >> ANDI PENG: Ang isang pansamantalang variable. 715 00:35:21,370 --> 00:35:22,570 Kaya sabihin gawin int temp. 716 00:35:22,570 --> 00:35:25,681 Tingnan, ito ay isang mas mahusay time to-- aba, ano ang na? 717 00:35:25,681 --> 00:35:26,180 SIGE. 718 00:35:26,180 --> 00:35:29,800 Kaya ito ay naging isang mas mahusay na oras sa pangalan ng variable na "temp." 719 00:35:29,800 --> 00:35:30,730 Kaya sabihin gawin int temp. 720 00:35:30,730 --> 00:35:32,563 Ano ang mga namin pagpunta sa set temp pantay na dito? 721 00:35:32,563 --> 00:35:34,752 722 00:35:34,752 --> 00:35:35,335 Madla: Min? 723 00:35:35,335 --> 00:35:38,508 724 00:35:38,508 --> 00:35:39,716 ANDI PENG: Ito ay isang bit mapanlinlang. 725 00:35:39,716 --> 00:35:43,110 726 00:35:43,110 --> 00:35:44,880 Ito ang tunay ay hindi mahalaga sa dulo. 727 00:35:44,880 --> 00:35:47,690 Hindi mahalaga kung ano ang sunod kang pumili upang magpalit in 728 00:35:47,690 --> 00:35:50,862 hangga't ginagawa mo ba na ikaw ay pagpapanatili ng track ng kung ano ang iyong pagpapalit. 729 00:35:50,862 --> 00:35:52,250 >> Madla: Ito ay maaaring maging array-i. 730 00:35:52,250 --> 00:35:53,666 >> ANDI PENG: Oo, gawin ang array-i ipaalam. 731 00:35:53,666 --> 00:35:55,950 732 00:35:55,950 --> 00:35:59,305 At pagkatapos ay kung ano ang susunod na linya ng code gusto naming magkaroon dito? 733 00:35:59,305 --> 00:36:00,680 Madla: array-i katumbas ng array-j. 734 00:36:00,680 --> 00:36:07,154 735 00:36:07,154 --> 00:36:08,070 ANDI PENG: At sa wakas? 736 00:36:08,070 --> 00:36:12,070 Madla: array-j katumbas array-i. 737 00:36:12,070 --> 00:36:14,525 Madla: O array-j equals array-temp-- o, 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 Kaya sabihin patakbuhin ito at makita kung ito ay pagpunta sa trabaho. 741 00:36:21,510 --> 00:36:37,520 742 00:36:37,520 --> 00:36:39,335 Saan na nangyayari? 743 00:36:39,335 --> 00:36:40,210 Oh, na ang isang problema. 744 00:36:40,210 --> 00:36:44,320 Tingnan, sa 40 na linya, hindi namin sinusubukan mong gamitin ang array-j? 745 00:36:44,320 --> 00:36:47,022 Ngunit kung saan ang j umiiral lamang sa? 746 00:36:47,022 --> 00:36:48,402 >> Madla: Sa para sa loop. 747 00:36:48,402 --> 00:36:49,110 ANDI PENG: Kanan. 748 00:36:49,110 --> 00:36:51,730 Kaya kung ano ang kami ay pagpunta sa kailangan mong gawin? 749 00:36:51,730 --> 00:36:53,170 >> Madla: Tukuyin ang mga ito sa labas the-- 750 00:36:53,170 --> 00:36:57,777 751 00:36:57,777 --> 00:37:00,610 Madla: Oo, ako hulaan ikaw ay gumamit ng isa pang kung statement, di ba? 752 00:37:00,610 --> 00:37:05,230 Kaya tulad ng, kung ang minimum-- lahat ng karapatan, hayaan mo akong mag-isip. 753 00:37:05,230 --> 00:37:08,170 754 00:37:08,170 --> 00:37:09,990 >> ANDI PENG: Guys, subukan upang tingnan Natin 755 00:37:09,990 --> 00:37:11,270 makita, kung ano ang isang bagay na maaari naming gawin dito? 756 00:37:11,270 --> 00:37:11,811 >> Madla: OK. 757 00:37:11,811 --> 00:37:15,900 Kaya kung ang minimum ay hindi katumbas ng j-- kaya kung ang minimum pa rin ang i-- 758 00:37:15,900 --> 00:37:17,570 pagkatapos ay hindi namin ay may upang magpalitan. 759 00:37:17,570 --> 00:37:22,450 760 00:37:22,450 --> 00:37:24,712 >> ANDI PENG: ba na pantay-pantay na i? 761 00:37:24,712 --> 00:37:25,920 Ano ang gusto mong sabihin dito? 762 00:37:25,920 --> 00:37:30,494 >> Madla: O oo, kung ang minimum ay hindi katumbas i, oo. 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 Well na malulutas nito, uri ng, ang aming mga problema. 766 00:37:42,040 --> 00:37:47,265 Ngunit iyon ay hindi pa rin malutas ang problema ng kung ano ang mangyayari kung j-- dahil j 767 00:37:47,265 --> 00:37:49,890 ay hindi na umiiral sa labas ng mga ito, kung ano ang mo gusto naming gawin dito? 768 00:37:49,890 --> 00:37:50,698 Ipinahahayag ito sa labas? 769 00:37:50,698 --> 00:37:59,410 770 00:37:59,410 --> 00:38:02,730 Subukan tumatakbo natin ito. 771 00:38:02,730 --> 00:38:04,435 Naku. 772 00:38:04,435 --> 00:38:06,200 Ang aming mga uri ang hindi gumagana. 773 00:38:06,200 --> 00:38:10,060 >> Tulad ng iyong nakikita, ang aming paunang array nagkaroon ng mga halaga. 774 00:38:10,060 --> 00:38:14,800 At pagkatapos ito ay dapat magkaroon ay sa 1, 2, 3, 4, 5, 6, 7, 8, 9. 775 00:38:14,800 --> 00:38:15,530 Hindi gumagana. 776 00:38:15,530 --> 00:38:16,030 Ahh. 777 00:38:16,030 --> 00:38:17,184 Ano ang gagawin namin? 778 00:38:17,184 --> 00:38:17,850 Madla: Debug. 779 00:38:17,850 --> 00:38:21,787 780 00:38:21,787 --> 00:38:23,370 ANDI PENG: Lahat ng mga karapatan, maaari naming subukan na. 781 00:38:23,370 --> 00:38:25,030 Maaari naming i-debug. 782 00:38:25,030 --> 00:38:26,042 Mag-zoom out ng kaunti. 783 00:38:26,042 --> 00:38:31,177 784 00:38:31,177 --> 00:38:33,656 Itakda ang aming mga breakpoint Hayaan. 785 00:38:33,656 --> 00:38:37,280 Sabihin pumunta like-- OK. 786 00:38:37,280 --> 00:38:40,444 >> So dahil na alam namin na mga linyang ito, 15 hanggang 22, 787 00:38:40,444 --> 00:38:43,610 ay working-- dahil ang lahat ng ginagawa ko lamang iterating sa pamamagitan at printing-- 788 00:38:43,610 --> 00:38:45,406 Maaari kong magpatuloy at laktawan iyon. 789 00:38:45,406 --> 00:38:47,280 Magsimula tayo sa 25 linya Hayaan. 790 00:38:47,280 --> 00:38:48,712 Oop, hayaan mo akong magtanggal ng mga iyon. 791 00:38:48,712 --> 00:38:51,598 792 00:38:51,598 --> 00:38:54,057 >> Madla: Kaya ang breakpoint ni kung saan ang pag-debug ay nagsisimula? 793 00:38:54,057 --> 00:38:54,890 ANDI PENG: O hinto. 794 00:38:54,890 --> 00:38:55,670 Madla: O hinto. 795 00:38:55,670 --> 00:38:55,930 ANDI PENG: Oo. 796 00:38:55,930 --> 00:38:58,640 Maaari kang magtakda ng maramihang breakpoints at Maaari lamang ito tumalon mula sa isa sa iba pang. 797 00:38:58,640 --> 00:39:01,590 Ngunit sa kasong ito hindi namin alam kung saan ang mga error ay nangyayari. 798 00:39:01,590 --> 00:39:03,780 Kaya nais lang namin sa simulan mula sa itaas pababa. 799 00:39:03,780 --> 00:39:05,020 Yep. 800 00:39:05,020 --> 00:39:05,550 SIGE. 801 00:39:05,550 --> 00:39:08,460 >> Kaya ito linya dito, maaari naming hakbang sa. 802 00:39:08,460 --> 00:39:11,499 Maaari mong makita sa ibaba rito, Nakakuha kami ng isang array. 803 00:39:11,499 --> 00:39:13,290 Ang mga ay ang mga halaga na sa array. 804 00:39:13,290 --> 00:39:16,360 Nakikita mo ba na, kung paano index 0, ito tumutugon sa value-- oh, 805 00:39:16,360 --> 00:39:17,526 Pupunta ako sa subukan upang mag-zoom in. 806 00:39:17,526 --> 00:39:20,650 Paumanhin, ito ay talagang mahirap upang see-- sa array index 0, 807 00:39:20,650 --> 00:39:24,090 kami ay may isang halaga ng 4 at pagkatapos ay iba pa at iba pa. 808 00:39:24,090 --> 00:39:25,670 Mayroon kaming aming mga lokal na variable. 809 00:39:25,670 --> 00:39:28,570 Sa ngayon ay i katumbas ng 0, na kung saan gusto naming ito upang maging. 810 00:39:28,570 --> 00:39:31,540 811 00:39:31,540 --> 00:39:33,690 >> At ni panatilihin tuntong sa pamamagitan ng kaya hayaan. 812 00:39:33,690 --> 00:39:36,850 Ang aming minimum ay katumbas ng 0, kung saan gusto rin naming ito upang maging. 813 00:39:36,850 --> 00:39:39,470 814 00:39:39,470 --> 00:39:45,560 At pagkatapos ay ipasok namin ang aming ikalawang para sa loop, kung array-j ay mas mababa sa array-i, 815 00:39:45,560 --> 00:39:46,380 na kung saan ito ay hindi. 816 00:39:46,380 --> 00:39:48,130 Kaya nakita mo kung paano na nilaktawan sa paglipas na? 817 00:39:48,130 --> 00:39:52,430 >> Madla: Kaya dapat ang kung minimum, ang lahat ng hindi na- dapat na 818 00:39:52,430 --> 00:39:55,424 maging sa loob ng unang para sa loop? 819 00:39:55,424 --> 00:39:57,340 ANDI PENG: Hindi, dahil gusto mo pa ring subukan. 820 00:39:57,340 --> 00:40:00,329 Gusto mong gawin ang isang paghahambing ng bawat oras, kahit na matapos na patakbuhin mo sa pamamagitan nito. 821 00:40:00,329 --> 00:40:02,620 Ayaw mo lamang na gawin ito sa unang pass-through. 822 00:40:02,620 --> 00:40:05,240 Gusto mong gawin ito na may bawat karagdagang muli pass. 823 00:40:05,240 --> 00:40:07,198 Kaya nais mong suriin para sa ang iyong kalagayan sa loob. 824 00:40:07,198 --> 00:40:11,610 825 00:40:11,610 --> 00:40:13,746 Kaya kami ay lamang ng pagpunta sa patuloy na tumatakbo sa pamamagitan dito. 826 00:40:13,746 --> 00:40:17,337 827 00:40:17,337 --> 00:40:18,420 Bibigyan kita ng isang lalaki na isang hint. 828 00:40:18,420 --> 00:40:23,910 Ito ay may sa gawin sa ang katunayan na kapag naka-check ang iyong mga kondisyon, 829 00:40:23,910 --> 00:40:26,600 hindi naka-check para sa tamang index. 830 00:40:26,600 --> 00:40:32,510 Kaya ngayon naka-check para sa array index ng j ay mas mababa sa array 831 00:40:32,510 --> 00:40:33,970 index ng i. 832 00:40:33,970 --> 00:40:36,580 Ngunit ano ang ginagawa mo up sa simula ng para sa loop? 833 00:40:36,580 --> 00:40:38,260 Hindi ka ba pagtatakda j katumbas i? 834 00:40:38,260 --> 00:40:41,260 835 00:40:41,260 --> 00:40:45,415 >> Oo, kaya maaari namin talagang lumabas ang debugger dito. 836 00:40:45,415 --> 00:40:47,040 Kaya sabihin kumuha ng isang pagtingin sa aming pseudocode. 837 00:40:47,040 --> 00:40:50,070 838 00:40:50,070 --> 00:40:52,580 For-- kami ng pagpunta sa magsimula sa katumbas i 0. 839 00:40:52,580 --> 00:40:54,760 Kami ay pagpunta sa pumunta hanggang sa n minus 1. 840 00:40:54,760 --> 00:40:58,040 Ating tingnan Hayaan, ay mayroon kaming ang mga karapatan? 841 00:40:58,040 --> 00:40:59,580 Oo, na karapatan. 842 00:40:59,580 --> 00:41:02,080 >> Kaya nga ang loob dito, hindi namin pagpunta upang lumikha ng isang minimum na halaga ng 843 00:41:02,080 --> 00:41:03,630 at itakda na katumbas ng i. 844 00:41:03,630 --> 00:41:04,950 Ibig namin gawin iyon? 845 00:41:04,950 --> 00:41:06,270 Oo, ginawa na. 846 00:41:06,270 --> 00:41:10,430 Ngayon sa aming panloob na para sa loop, hindi namin pagpunta sa gawin j i katumbas sa n 1 minus. 847 00:41:10,430 --> 00:41:11,950 Ibig namin gawin iyon? 848 00:41:11,950 --> 00:41:15,540 Sa katunayan, ginawa namin na. 849 00:41:15,540 --> 00:41:19,922 >> Kaya gayunpaman, kung ano ang namin ang paghahambing dito? 850 00:41:19,922 --> 00:41:20,925 >> Madla: j plus 1. 851 00:41:20,925 --> 00:41:21,716 ANDI PENG: Eksakto. 852 00:41:21,716 --> 00:41:24,184 853 00:41:24,184 --> 00:41:27,350 At pagkatapos ikaw ay pagpunta sa nais na itakda ang iyong minimum na katumbas j plus 1 rin. 854 00:41:27,350 --> 00:41:31,057 855 00:41:31,057 --> 00:41:32,640 Kaya nagpunta ako sa pamamagitan na talagang mabilis. 856 00:41:32,640 --> 00:41:36,190 Naiintindihan ba ninyo guys kung bakit ito ay j plus 1? 857 00:41:36,190 --> 00:41:36,890 SIGE. 858 00:41:36,890 --> 00:41:40,700 >> Kaya sa inyong array, in iyong unang pass sa pamamagitan ng, 859 00:41:40,700 --> 00:41:44,850 iyong para sa loop, para sa int i katumbas ng 0, sabihin lamang 860 00:41:44,850 --> 00:41:46,740 ipalagay na ito ay hindi pa nabago. 861 00:41:46,740 --> 00:41:53,180 862 00:41:53,180 --> 00:41:56,760 Mayroon kaming isang array ng, ganap, apat na lang unsorted elemento, tama? 863 00:41:56,760 --> 00:42:00,760 Kaya gusto namin upang magpasimula pantay i sa 0. 864 00:42:00,760 --> 00:42:03,650 At i ay pagpunta sa makatarungan tumakbo ito sa pamamagitan ng loop. 865 00:42:03,650 --> 00:42:08,560 At kaya sa unang pass, kami ay pagpunta upang magpasimula ng isang variable na tinatawag na "min" 866 00:42:08,560 --> 00:42:11,245 na rin i katumbas, dahil hindi namin ay may isang minimum na halaga. 867 00:42:11,245 --> 00:42:12,870 Kaya na sa kasalukuyan ay katumbas ng 0 rin. 868 00:42:12,870 --> 00:42:16,182 869 00:42:16,182 --> 00:42:17,640 At pagkatapos kami ay pagpunta upang pumunta sa pamamagitan ng. 870 00:42:17,640 --> 00:42:19,270 At gusto namin na umulit muli. 871 00:42:19,270 --> 00:42:22,900 Ngayon na nalaman namin kung ano ang aming minimum ay, gusto naming upang umulit sa pamamagitan 872 00:42:22,900 --> 00:42:25,190 muli upang makita kung ito ay ang paghahambing, di ba? 873 00:42:25,190 --> 00:42:40,440 Kaya j, dito, ay pagpunta sa pantay na i, na kung saan ay 0. 874 00:42:40,440 --> 00:42:46,320 At pagkatapos ay kung array j plus i, na ay ang isa na ang susunod sa ibabaw, tulad ng mas mababa 875 00:42:46,320 --> 00:42:49,270 kaysa sa kung ano ang iyong kasalukuyang minimum halaga ay, gusto mong magpalit. 876 00:42:49,270 --> 00:42:56,850 >> Kaya sabihin lamang sabihin na namin got, i, 2, 5, 1, 8. 877 00:42:56,850 --> 00:43:01,610 Sa ngayon, i ay katumbas ng 0 at j ay katumbas sa 0. 878 00:43:01,610 --> 00:43:05,210 At iyon ang aming minimum na halaga. 879 00:43:05,210 --> 00:43:09,950 Kung array-j plus i-- kaya kung ang isa na pagkatapos ng isa kaming naghahanap sa 880 00:43:09,950 --> 00:43:13,450 ay mas malaki kaysa sa isa bago ito, ito ay pagpunta sa maging ang minimum. 881 00:43:13,450 --> 00:43:18,120 >> Kaya dito makikita natin na 5 ay hindi mas mababa kaysa sa na. 882 00:43:18,120 --> 00:43:19,730 Kaya ito ay pagpunta sa hindi 5. 883 00:43:19,730 --> 00:43:23,580 Nakita namin na 1 ay mas mababa sa 2, di ba? 884 00:43:23,580 --> 00:43:32,970 Kaya ngayon ay alam namin na ang aming minimum ay magiging halaga ng index sa 0, 1, 2. 885 00:43:32,970 --> 00:43:34,030 Oo? 886 00:43:34,030 --> 00:43:39,170 At pagkatapos ay kapag ikaw ay makakuha ng down dito, maaari mong ipagpalit ang tamang halaga. 887 00:43:39,170 --> 00:43:42,610 >> Kaya kapag ikaw guys ay lamang ang pagkakaroon ng j bago, hindi na kayo ay naghahanap sa isa 888 00:43:42,610 --> 00:43:43,260 pagkatapos na ito. 889 00:43:43,260 --> 00:43:44,520 Ikaw ay naghahanap sa sa parehong halaga, na kung saan 890 00:43:44,520 --> 00:43:46,290 ang dahilan kung bakit ito lamang ay hindi gumagawa ng anumang bagay. 891 00:43:46,290 --> 00:43:49,721 Ba na magkaroon ng kahulugan sa lahat ng tao, bakit kailangan natin na plus 1 doon? 892 00:43:49,721 --> 00:43:50,220 SIGE. 893 00:43:50,220 --> 00:43:53,345 Ngayon tatakbo lang sa pamamagitan nito na gumawa ng ipaalam Siguraduhin na ang natitirang bahagi ng code ay tama. 894 00:43:53,345 --> 00:44:04,424 895 00:44:04,424 --> 00:44:05,340 Bakit na nangyayari? 896 00:44:05,340 --> 00:44:14,780 897 00:44:14,780 --> 00:44:16,364 Ah, ito ay ang min dito mismo. 898 00:44:16,364 --> 00:44:17,780 Kami ay paghahambing ng maling halaga. 899 00:44:17,780 --> 00:44:24,944 900 00:44:24,944 --> 00:44:25,906 Oh hindi. 901 00:44:25,906 --> 00:44:30,720 902 00:44:30,720 --> 00:44:33,482 >> Oh oo, pababa dito tayo ay pagpapalit ang maling halaga pati na rin. 903 00:44:33,482 --> 00:44:34,940 Dahil kami ay naghahanap sa i at j. 904 00:44:34,940 --> 00:44:36,440 Iyon ang mga bago namin checking. 905 00:44:36,440 --> 00:44:39,160 Kami ay talagang nais na magpalit ng mga minimum, ang kasalukuyang minimum, 906 00:44:39,160 --> 00:44:40,550 sa ano man ang isa sa labas ay. 907 00:44:40,550 --> 00:44:59,510 908 00:44:59,510 --> 00:45:05,402 At bilang ay maaaring makita ka guys down dito, mayroon kaming isang pinagsunod-sunod array. 909 00:45:05,402 --> 00:45:07,110 Lamang nagkaroon ito upang gawin sa ang katotohanan na kapag 910 00:45:07,110 --> 00:45:09,350 checking namin ay ang halaga namin ay paghahambing, 911 00:45:09,350 --> 00:45:11,226 hindi namin ay naghahanap sa tamang halaga. 912 00:45:11,226 --> 00:45:13,850 Kami ay naghahanap sa parehong isa dito, hindi aktwal na pagpapalit ito. 913 00:45:13,850 --> 00:45:17,135 Ikaw ay may na tingnan ang isa sa tabi na ito at pagkatapos ay maaari mong ipagpalit. 914 00:45:17,135 --> 00:45:19,260 Kaya na kung ano ang uri ng bugging aming code bago. 915 00:45:19,260 --> 00:45:22,460 At kung ano ang ginawa ko dito ay ang lahat ng bagay ang debugger ay may ginagawa para sa iyo 916 00:45:22,460 --> 00:45:23,810 Ginawa ko lang ito sa board, dahil sa ito ay mas madali 917 00:45:23,810 --> 00:45:26,320 upang makita ang sa halip na sinusubukan upang mag-zoom in sa debugger. 918 00:45:26,320 --> 00:45:29,391 Ba na magkaroon ng kahulugan sa lahat ng tao? 919 00:45:29,391 --> 00:45:29,890 Cool. 920 00:45:29,890 --> 00:45:34,800 921 00:45:34,800 --> 00:45:35,410 >> Lahat tama. 922 00:45:35,410 --> 00:45:41,070 Maaari naming ilipat sa sa pakikipag-usap tungkol asymptotic pagtatanda, na 923 00:45:41,070 --> 00:45:44,580 ay lamang ng isang magarbong paraan ng sinasabi ng runtimes ng lahat ng mga uri. 924 00:45:44,580 --> 00:45:47,650 Kaya alam ko David, sa panayam, hinawakan sa runtimes. 925 00:45:47,650 --> 00:45:52,124 At siya nagpunta sa pamamagitan ng buong formula ng kung paano kinakalkula ang runtimes. 926 00:45:52,124 --> 00:45:53,040 Huwag mag-alala tungkol sa na. 927 00:45:53,040 --> 00:45:54,660 Kung ikaw ay talagang kakaiba sa kung paano na gumagana, 928 00:45:54,660 --> 00:45:55,810 mag-atubili na makipag-usap sa akin pagkatapos ng section. 929 00:45:55,810 --> 00:45:57,560 Maaari naming sa pamamagitan ng paglalakad ang mga formula na magkasama. 930 00:45:57,560 --> 00:46:00,689 Ngunit ang lahat ng ka guys kung talagang alam na n nakalapat sa higit sa 2 931 00:46:00,689 --> 00:46:01,980 ay ang mga parehong bagay tulad n nakalapat. 932 00:46:01,980 --> 00:46:04,710 Dahil ang pinakamalaking bilang, ang exponent, lumalaki ang pinaka. 933 00:46:04,710 --> 00:46:06,590 At kaya para sa aming mga layunin, lahat ng pag-aalaga namin ang tungkol sa 934 00:46:06,590 --> 00:46:09,470 ay na giant numero na lumalaki. 935 00:46:09,470 --> 00:46:13,340 >> Kaya kung ano ang pinakamahusay na kaso runtime ng pagpili ng uri? 936 00:46:13,340 --> 00:46:15,830 Kung ikaw ay pagpunta sa may upang umulit sa pamamagitan ng isang listahan 937 00:46:15,830 --> 00:46:18,712 at pagkatapos ay ulitin sa pamamagitan ng ang natitirang bahagi ng listahan na iyon, 938 00:46:18,712 --> 00:46:20,420 kung gaano karaming beses ang marahil ka ng pagpunta sa, 939 00:46:20,420 --> 00:46:24,612 sa pinakamalala case-- sa pinakamahusay na kaso, sorry-- tumakbo sa pamamagitan ng? 940 00:46:24,612 --> 00:46:27,070 Siguro ang mas magandang tanong ay na magtanong, kung ano ay ang pinakamasama kaso 941 00:46:27,070 --> 00:46:28,153 runtime ng pagpili ng uri. 942 00:46:28,153 --> 00:46:29,366 Madla: n nakalapat. 943 00:46:29,366 --> 00:46:30,740 ANDI PENG: Ito ay n nakalapat, right. 944 00:46:30,740 --> 00:46:36,986 Kaya isang madaling paraan upang isipin ng mga ito ay tulad ng, anumang oras na mayroon kang dalawang nested para sa mga loop, 945 00:46:36,986 --> 00:46:38,110 ito ay pagpunta sa maging n nakalapat. 946 00:46:38,110 --> 00:46:40,386 Dahil hindi lamang ikaw ay tumatakbo muli sa pamamagitan ng, 947 00:46:40,386 --> 00:46:42,260 kailangan mong pumunta sa likod paligid at tumakbo sa pamamagitan nito 948 00:46:42,260 --> 00:46:44,980 sa sandaling muli sa loob para sa bawat halaga. 949 00:46:44,980 --> 00:46:48,640 Kaya sa kasong iyon, ikaw ay nagpapatakbo ng n beses n nakalapat, na is-- Paumanhin, 950 00:46:48,640 --> 00:46:50,505 n beses n, na kung saan ay katumbas n nakalapat. 951 00:46:50,505 --> 00:46:53,230 952 00:46:53,230 --> 00:46:56,360 >> At ang uri ay din ng isang bit natatangi sa kamalayan 953 00:46:56,360 --> 00:46:59,774 na ito ay hindi mahalaga kung ang mga mga halaga ay nasa order. 954 00:46:59,774 --> 00:47:01,440 Ito ay pagpunta pa rin upang tumakbo sa pamamagitan pa rin. 955 00:47:01,440 --> 00:47:03,872 Sabihin lang sabihin na ito ay 1, 2, 3, 4. 956 00:47:03,872 --> 00:47:07,080 Kahit na o hindi ito ay sa order, pa rin ito ay may bumangga sa pamamagitan ng 957 00:47:07,080 --> 00:47:08,620 at pa rin naka-check ang minimum na halaga. 958 00:47:08,620 --> 00:47:10,100 Itong ginawa ang parehong bilang ng mga tseke 959 00:47:10,100 --> 00:47:12,780 ng lahat ng oras, kahit na ito ay hindi aktwal na hawakan ng kahit ano. 960 00:47:12,780 --> 00:47:16,940 >> Kaya sa ganoong kaso, ang mga pinakamahusay at pinakamasamang runtimes ay talagang katumbas. 961 00:47:16,940 --> 00:47:19,160 Kaya ang inaasahan runtime ng pagpili ng uri, 962 00:47:19,160 --> 00:47:23,790 na maitalaga kami sa pamamagitan ng mga simbolo ng theta, theta, sa kasong ito, 963 00:47:23,790 --> 00:47:24,790 ay n din nakalapat. 964 00:47:24,790 --> 00:47:26,480 Lahat ng tatlong ng mga ito ay magiging n nakalapat. 965 00:47:26,480 --> 00:47:29,653 Ay malinaw sa lahat ng tao sa kung bakit ang runtime ay n nakalapat? 966 00:47:29,653 --> 00:47:33,360 967 00:47:33,360 --> 00:47:33,980 >> Lahat tama. 968 00:47:33,980 --> 00:47:39,120 Kaya lang ako pagpunta sa mabilis na tumakbo sa pamamagitan ng ang natitirang bahagi ng mga masama. 969 00:47:39,120 --> 00:47:41,137 Ang algorithm para sa bubble sort-- tandaan, 970 00:47:41,137 --> 00:47:43,220 ito ay ang unang isa Tumawid David sa panayam. 971 00:47:43,220 --> 00:47:46,000 Totoo, ikaw hakbang sa pamamagitan ng buong listahan 972 00:47:46,000 --> 00:47:48,950 at swap-- ka ikaw lamang paghambingin ang dalawang sa isang pagkakataon. 973 00:47:48,950 --> 00:47:51,350 At kung ang isa ay mas malaki, kaysa mo lamang palitan ang mga ito. 974 00:47:51,350 --> 00:47:53,590 Kaya kung ang mga ito ay mas malaki, gusto mo magpalit. 975 00:47:53,590 --> 00:47:56,180 Mayroon akong opisyal na karapatan dito. 976 00:47:56,180 --> 00:47:59,100 >> Kaya sabihin lamang sabihin na kayo ay nagkaroon ng 8, 6, 4, 2. 977 00:47:59,100 --> 00:48:00,571 Gusto mong ihambing ang 8 at 6. 978 00:48:00,571 --> 00:48:01,570 Gusto mo kailangan upang magpalitan ng mga ito. 979 00:48:01,570 --> 00:48:02,610 Gusto mong ihambing ang 8 at isang 4. 980 00:48:02,610 --> 00:48:03,609 Gusto mo kailangan upang magpalitan ng mga ito. 981 00:48:03,609 --> 00:48:07,000 Kung ikaw ay may upang magpalit ng 8 at ang 2, magbabago rin ang mga ito. 982 00:48:07,000 --> 00:48:10,760 Kaya sa ganoong kahulugan, maaari mong makita, play out sa loob ng mahabang panahon, 983 00:48:10,760 --> 00:48:13,730 kung paano ang mga halaga ng uri ng bubble sa ang mga dulo, na kung saan ay kung bakit ang tawag namin ito 984 00:48:13,730 --> 00:48:15,320 sort bubble. 985 00:48:15,320 --> 00:48:19,950 >> Nais tumakbo lang namin sa pamamagitan sa muli ang aming pangalawang pass, at ang aming ikatlong pass, 986 00:48:19,950 --> 00:48:21,150 at ang aming ika-apat na pass. 987 00:48:21,150 --> 00:48:25,820 Mahalaga, bubble ay tumatakbo lamang uri hanggang hindi mo na gumawa ng anumang higit swaps. 988 00:48:25,820 --> 00:48:31,109 Kaya sa na kahulugan, ito ay lamang ang pangkalahatang pseudocode para dito. 989 00:48:31,109 --> 00:48:32,650 Huwag mag-alala, ang mga ito ay ang lahat ay online. 990 00:48:32,650 --> 00:48:34,990 Wala kaming upang aktwal na pumunta sa paglipas ng ito. 991 00:48:34,990 --> 00:48:38,134 >> Magpasimula lang namin ng counter variable na nagsisimula sa 0. 992 00:48:38,134 --> 00:48:39,800 At umulit kami sa pamamagitan ng buong array. 993 00:48:39,800 --> 00:48:43,420 At kung ang isa halaga is-- kung ito halaga ay mas mataas kaysa sa halaga na iyon, 994 00:48:43,420 --> 00:48:44,610 ikaw ay pagpunta sa swap sa kanila. 995 00:48:44,610 --> 00:48:46,860 At pagkatapos ay ikaw lamang pagpunta sa panatilihin ang pagpunta. 996 00:48:46,860 --> 00:48:47,970 At ikaw ay pagpunta sa count. 997 00:48:47,970 --> 00:48:50,845 At lamang ikaw ay pagpunta sa patuloy na paggawa ito habang ang counter ay mas malaki 998 00:48:50,845 --> 00:48:53,345 kaysa sa 0, na nangangahulugan na ang sa bawat oras na ikaw ay may upang magpalitan, 999 00:48:53,345 --> 00:48:55,220 alam mo na gusto mong puntahan bumalik at suriin muli. 1000 00:48:55,220 --> 00:48:59,510 Gusto mong panatilihin ang checking hanggang malaman mo na hindi mo na kailangang magpalit anymore. 1001 00:48:59,510 --> 00:49:05,570 >> Kaya kung ano ang pinakamahusay at pinakamasamang kaso runtimes para bubble sort? 1002 00:49:05,570 --> 00:49:09,300 At hint-- ito ay tunay na naiiba mula sa mga uri sa kamalayan seleksyon 1003 00:49:09,300 --> 00:49:11,810 na ang mga dalawang mga sagot ay hindi pareho. 1004 00:49:11,810 --> 00:49:14,709 Mag-isip tungkol sa kung ano ang mangyayari sa isang kaso kung ito ay mayroon na pinagsunod-sunod. 1005 00:49:14,709 --> 00:49:16,500 At sa tingin tungkol sa kung ano ang mangyayari kung ito ay 1006 00:49:16,500 --> 00:49:18,372 sa kaso na kung saan hindi ito ay pinagsunod-sunod. 1007 00:49:18,372 --> 00:49:20,580 At maaari mong uri ng tumakbo sa pamamagitan ng kung bakit na ang nangyayari. 1008 00:49:20,580 --> 00:49:22,954 Bibigyan kita ng isang lalaki, tulad ng, 30 segundo upang isipin ang tungkol na. 1009 00:49:22,954 --> 00:49:52,330 1010 00:49:52,330 --> 00:49:53,540 >> SIGE. 1011 00:49:53,540 --> 00:49:57,462 Kahit sino ay may isang hula sa kung ano ang pinakamasama kaso runtime ng bubble sort ay? 1012 00:49:57,462 --> 00:49:57,962 Oo. 1013 00:49:57,962 --> 00:50:07,810 >> Madla: Gusto ito ay, tulad ng, n ulit n minus 1 o isang bagay tulad na? 1014 00:50:07,810 --> 00:50:10,650 Tulad ng, sa bawat panahon na ito ay tumatakbo, ito lang, gusto, isa swap mas mababa 1015 00:50:10,650 --> 00:50:10,960 na anuman ito. 1016 00:50:10,960 --> 00:50:12,668 >> ANDI PENG: Oo, kaya hindi lubos na karapatan sa iyo. 1017 00:50:12,668 --> 00:50:15,940 At ito ay isang kaso kung saan ang iyong mga Ang sagot ay talagang mas kumplikadong 1018 00:50:15,940 --> 00:50:17,240 kaysa sa isa kailangan namin na magbigay sa. 1019 00:50:17,240 --> 00:50:19,772 Kaya ito ay pagpunta sa run-- Ako Buburahin ang lahat ng ito dito. 1020 00:50:19,772 --> 00:50:20,480 Mabuti ba ang lahat? 1021 00:50:20,480 --> 00:50:21,869 Maaari ko bang burahin ito? 1022 00:50:21,869 --> 00:50:22,368 SIGE. 1023 00:50:22,368 --> 00:50:27,904 1024 00:50:27,904 --> 00:50:30,320 Ikaw ay pagpunta upang tumakbo sa pamamagitan n beses sa unang pagkakataon, i-right? 1025 00:50:30,320 --> 00:50:33,200 At sila ay pagpunta upang tumakbo sa pamamagitan n minus 1 sa pangalawang pagkakataon, di ba? 1026 00:50:33,200 --> 00:50:37,130 At pagkatapos ikaw ay pagpunta sa panatilihin tuloy, n mine 2, at iba pa. 1027 00:50:37,130 --> 00:50:40,210 Ginawa ito ni David sa isang panayam, kung saan, kung iyong idinagdag up sa lahat ng mga halaga, 1028 00:50:40,210 --> 00:50:48,080 makakakuha ka ng isang bagay na like-- yeah-- higit sa 2, na mahalagang lamang binabawasan 1029 00:50:48,080 --> 00:50:49,784 pababa sa n nakalapat. 1030 00:50:49,784 --> 00:50:51,700 Ikaw ay pagpunta upang makakuha ng isang kakaiba maliit na bahagi sa doon. 1031 00:50:51,700 --> 00:50:53,892 At kaya lamang malaman na ang n nakalapat laging 1032 00:50:53,892 --> 00:50:55,350 tumatagal ng higit na kahalagahan sa mga maliit na bahagi. 1033 00:50:55,350 --> 00:50:58,450 At kaya sa kasong ito, ang pinakamasama runtime ay n nakalapat. 1034 00:50:58,450 --> 00:51:00,210 Kung ito ay sa pababang order, mag-isip, ikaw ay 1035 00:51:00,210 --> 00:51:02,530 kailangang gumawa ng isang magpalitan ng bawat solong oras. 1036 00:51:02,530 --> 00:51:05,170 >> Ano ang gusto ay, potensyal na, ang pinakamahusay na runtime kaso? 1037 00:51:05,170 --> 00:51:08,580 Sabihin lang sabihin, kung ang listahan ay mayroon na sa pagkakasunud-sunod, ano ang magiging runtime? 1038 00:51:08,580 --> 00:51:09,565 >> Madla: n. 1039 00:51:09,565 --> 00:51:10,690 ANDI PENG: Ito ay n, eksakto. 1040 00:51:10,690 --> 00:51:11,600 At kung bakit ito ay n? 1041 00:51:11,600 --> 00:51:13,850 Madla: Dahil ikaw lamang kung suriin sa bawat beses. 1042 00:51:13,850 --> 00:51:14,770 ANDI PENG: Eksakto. 1043 00:51:14,770 --> 00:51:17,150 Kaya sa posibleng pinakamahusay na runtime, kung ang listahan na ito ay mayroon na 1044 00:51:17,150 --> 00:51:20,270 sorted-- sabihin natin 1, 2, 3, 4-- mo ay pumunta lamang sa pamamagitan ng, na iyong nais na tingnan, 1045 00:51:20,270 --> 00:51:21,720 Gusto mo makita, oh, ang lahat ng mga ito ay mag-pan out. 1046 00:51:21,720 --> 00:51:22,636 Hindi ko na kailangang magpalit. 1047 00:51:22,636 --> 00:51:23,370 Tapos na ako. 1048 00:51:23,370 --> 00:51:26,500 Kaya sa kasong iyon, ito ay n lang o ang bilang ng mga hakbang mo lamang 1049 00:51:26,500 --> 00:51:29,870 nagkaroon upang suriin sa unang listahan. 1050 00:51:29,870 --> 00:51:33,990 >> At pagkatapos, kami ay pindutin ngayon uuri, kung saan 1051 00:51:33,990 --> 00:51:39,260 ang algorithm ay mahalagang upang hatiin ito sa isang inayos at unsorted bahagi. 1052 00:51:39,260 --> 00:51:42,810 At pagkatapos ay isa-isa, unsorted mga halaga ay 1053 00:51:42,810 --> 00:51:46,880 nakapasok sa kanilang mga naaangkop na mga posisyon sa simula ng listahan. 1054 00:51:46,880 --> 00:51:52,120 >> Kaya halimbawa, kami ay may isang listahan ng 3, 5, 2, 6, 4 muli. 1055 00:51:52,120 --> 00:51:54,750 Alam namin na ito ay kasalukuyang unsorted dahil hindi namin lamang 1056 00:51:54,750 --> 00:51:57,030 nagsimula ang pagtingin sa mga ito. 1057 00:51:57,030 --> 00:52:00,610 Tinitingnan namin at alam namin na sa unang halaga ay inayos, right? 1058 00:52:00,610 --> 00:52:04,190 Kung lamang ikaw ay naghahanap sa isang hanay ng mga laki ng isa, alam mo na ito ay pinagsunod-sunod. 1059 00:52:04,190 --> 00:52:08,230 >> Kaya nga nalalaman natin na ang iba pang apat ay unsorted. 1060 00:52:08,230 --> 00:52:10,980 Pumunta kami sa pamamagitan ng at nakita namin ang halaga. 1061 00:52:10,980 --> 00:52:11,730 Bumalik tayo. 1062 00:52:11,730 --> 00:52:13,130 Tingnan na halaga ng 5? 1063 00:52:13,130 --> 00:52:14,110 Kumuha kami ng isang pagtingin sa mga ito. 1064 00:52:14,110 --> 00:52:15,204 Inihambing namin ito sa 3. 1065 00:52:15,204 --> 00:52:17,870 Alam namin na ito ay mas malaki kaysa sa 3, upang malaman namin na na pinagsunod-sunod. 1066 00:52:17,870 --> 00:52:22,940 Kaya alam namin ngayon na ang unang dalawang ay pinagsunod-sunod at ang huling tatlong ay hindi. 1067 00:52:22,940 --> 00:52:24,270 >> Kumuha kami ng isang pagtingin sa 2. 1068 00:52:24,270 --> 00:52:25,720 Una naming suriin ito sa 5. 1069 00:52:25,720 --> 00:52:26,700 Ito ba ay mas mababa sa 5? 1070 00:52:26,700 --> 00:52:27,240 Hindi iyon. 1071 00:52:27,240 --> 00:52:29,510 Kaya kami ay may upang panatilihin ang naghahanap down. 1072 00:52:29,510 --> 00:52:30,940 Pagkatapos mong suriin ang 2 off 3. 1073 00:52:30,940 --> 00:52:31,850 Ito ba ay mas mababa kaysa sa? 1074 00:52:31,850 --> 00:52:32,350 Hindi. 1075 00:52:32,350 --> 00:52:35,430 Kaya alam mo ng 2 ay may na nakapasok sa harap at 3 at 5 1076 00:52:35,430 --> 00:52:38,200 parehong may upang maging hunhon out. 1077 00:52:38,200 --> 00:52:42,190 Gawin ito muli sa 6 at 4. 1078 00:52:42,190 --> 00:52:48,962 At kami lamang panatilihin ang mahalagang suri, kung saan namin lamang suriin, suriin, suriin. 1079 00:52:48,962 --> 00:52:51,170 At hanggang sa ito ay nasa tamang posisyon, namin uri ng lamang 1080 00:52:51,170 --> 00:52:54,890 ipasok ito sa tamang posisyon, na kung saan ay kung saan ang pangalan ng ito nanggaling. 1081 00:52:54,890 --> 00:52:59,830 >> Kaya ito lamang ang algorithm, pseudocode per se, uri ng, 1082 00:52:59,830 --> 00:53:04,990 sa kung paano namin ipatupad isang uri pagpapasok. 1083 00:53:04,990 --> 00:53:05,954 Pseudocode ay dito. 1084 00:53:05,954 --> 00:53:06,620 Lahat ng ito ay online. 1085 00:53:06,620 --> 00:53:10,720 Huwag mag-alala kung ikaw guys ay sinusubukan mong kopyahin ito pababa. 1086 00:53:10,720 --> 00:53:14,500 Kaya muli, parehong question-- ano ay ang pinakamahusay at pinakamasamang runtimes 1087 00:53:14,500 --> 00:53:16,120 para sa uri pagpapasok? 1088 00:53:16,120 --> 00:53:17,750 Ito ay halos kapareho sa huling tanong. 1089 00:53:17,750 --> 00:53:20,479 Bibigyan kita ng isang lalaki, tulad ng, 30 segundo upang isipin ang tungkol sa mga ito pati na rin. 1090 00:53:20,479 --> 00:53:47,150 1091 00:53:47,150 --> 00:53:50,071 >> OK sinumang gusto ba sa bigyan ako ang pinakamasama runtime? 1092 00:53:50,071 --> 00:53:50,570 Oo. 1093 00:53:50,570 --> 00:53:51,490 >> Madla: n nakalapat. 1094 00:53:51,490 --> 00:53:52,573 >> ANDI PENG: Ito ay n nakalapat. 1095 00:53:52,573 --> 00:53:53,730 At bakit ito n nakalapat? 1096 00:53:53,730 --> 00:53:57,562 >> Madla: Dahil sa reverse order, mayroon kang 1097 00:53:57,562 --> 00:54:02,619 upang pumunta sa pamamagitan n beses n, na is-- 1098 00:54:02,619 --> 00:54:03,660 ANDI PENG: Oo, eksakto. 1099 00:54:03,660 --> 00:54:06,610 Kaya parehong bagay tulad ng sa bubble sort. 1100 00:54:06,610 --> 00:54:08,720 Kung ang listahan na ito ay nasa pababang pagkakasunud-sunod, ikaw ay 1101 00:54:08,720 --> 00:54:11,240 pagpunta sa may upang suriin ang unang beses. 1102 00:54:11,240 --> 00:54:13,470 At pagkatapos ay sa bawat karagdagang halaga, ikaw ay 1103 00:54:13,470 --> 00:54:16,390 pagpunta sa may upang suriin ito kumpara bawat solong halaga, di ba? 1104 00:54:16,390 --> 00:54:20,290 At kaya sa kabuuan, ikaw ay pagpunta sa gumawa isang n pass ulit ng isa pang n pumasa, na 1105 00:54:20,290 --> 00:54:21,750 ay n nakalapat. 1106 00:54:21,750 --> 00:54:22,860 Ano ang tungkol sa mga pinakamahusay na kaso? 1107 00:54:22,860 --> 00:54:24,360 Oo. 1108 00:54:24,360 --> 00:54:28,840 >> Madla: n minus 1, dahil ang unang isa ay naka nakalapat. 1109 00:54:28,840 --> 00:54:30,270 >> ANDI PENG: So, malapit na. 1110 00:54:30,270 --> 00:54:31,850 Ang sagot ay talagang n. 1111 00:54:31,850 --> 00:54:37,189 Dahil habang ang una ay ayun, maaaring hindi ito actually-- ito 1112 00:54:37,189 --> 00:54:38,980 lucked lang namin sa labas, sa Halimbawa na, na ang 2 1113 00:54:38,980 --> 00:54:40,930 nangyari na ang pinakamaliit na bilang. 1114 00:54:40,930 --> 00:54:43,680 Ngunit iyon ay hindi palaging ang kaso. 1115 00:54:43,680 --> 00:54:48,040 Kung 2 na pinagsunod-sunod sa simula ngunit tumingin ka at mayroong isang 1 dito, 1116 00:54:48,040 --> 00:54:49,144 ang 1 ay pagpunta sa paga ito. 1117 00:54:49,144 --> 00:54:51,060 At ito ay pagpunta sa dulo up pagiging bumped anyways. 1118 00:54:51,060 --> 00:54:56,250 >> Kaya sa mga pinakamahusay na kaso sitwasyon, ito ay talagang lamang magiging n. 1119 00:54:56,250 --> 00:54:59,090 Kung ikaw ay may 1, 2, 3, 4, 5, 6, 7, 8, ikaw ay 1120 00:54:59,090 --> 00:55:00,940 pagpunta upang tumakbo sa pamamagitan na ang buong listahan ng isang beses 1121 00:55:00,940 --> 00:55:03,430 upang suriin upang makita kung fine ang lahat. 1122 00:55:03,430 --> 00:55:07,390 Ay malinaw na lahat ng tao sa pagtakbo mga oras ng pagpipilian pati na rin? 1123 00:55:07,390 --> 00:55:09,960 Alam ko ako pagpunta sa pamamagitan ng mabilis talaga ang mga ito. 1124 00:55:09,960 --> 00:55:13,330 Ngunit lamang malaman na kung alam mo ang pangkalahatang konsepto, dapat ay handa na. 1125 00:55:13,330 --> 00:55:16,070 SIGE. 1126 00:55:16,070 --> 00:55:19,790 Kaya kukunin ko na lang magbibigay sa iyo ng isang lalaki siguro, tulad ng, isang minuto upang makipag-usap sa iyong mga kapitbahay 1127 00:55:19,790 --> 00:55:21,890 sa kung ano lang ang ilan sa mga pangunahing pagkakaiba 1128 00:55:21,890 --> 00:55:23,540 pagitan ng mga uri ng mga uri. 1129 00:55:23,540 --> 00:56:24,571 1130 00:56:24,571 --> 00:56:25,570 Susubukan naming pumunta sa paglipas na sa lalong madaling panahon. 1131 00:56:25,570 --> 00:56:26,444 Madla: Oh, OK. 1132 00:56:26,444 --> 00:56:27,320 ANDI PENG: Oo. 1133 00:56:27,320 --> 00:56:28,380 SIGE. 1134 00:56:28,380 --> 00:56:33,420 Cool, ni reconvene bilang isang klase ipaalam. 1135 00:56:33,420 --> 00:56:34,330 SIGE. 1136 00:56:34,330 --> 00:56:37,579 Kaya ito ay uri ng isang open-ended na tanong sa kamalayan 1137 00:56:37,579 --> 00:56:39,120 na mayroong maraming mga kasagutan sa mga ito. 1138 00:56:39,120 --> 00:56:40,746 At kami ay pumunta sa paglipas ng ilan sa mga ito sa madaling sabi. 1139 00:56:40,746 --> 00:56:43,411 Nais ko lamang na makakuha ka ng isang lalaki nag-iisip tungkol sa kung ano differentiated 1140 00:56:43,411 --> 00:56:44,530 lahat ng tatlong mga uri ng mga uri. 1141 00:56:44,530 --> 00:56:47,440 At narinig ko, din, ang isang malaking question-- ano ang sumanib uri gawin? 1142 00:56:47,440 --> 00:56:50,110 Mahusay na katanungan, dahil na kung ano ang pinag sumasaklaw namin sa susunod. 1143 00:56:50,110 --> 00:56:52,850 >> Kaya sumanib-uuri ay ang isang uri na pag-andar 1144 00:56:52,850 --> 00:56:56,100 tunay naiiba mula sa iba pang mga uri. 1145 00:56:56,100 --> 00:56:58,180 Tulad see-- ka guys ang ginawa ni David na demo 1146 00:56:58,180 --> 00:57:01,130 kung saan siya ay nagkaroon ng lahat ng mga cool mga ingay ng mga nakakakita kung paano pagsamahin 1147 00:57:01,130 --> 00:57:04,010 sort tumakbo, tulad ng, walang katapusan mas mabilis kaysa sa iba pang mga dalawang uri? 1148 00:57:04,010 --> 00:57:04,510 SIGE. 1149 00:57:04,510 --> 00:57:07,580 Kaya na dahil merge sort nagpapatupad na hatiin 1150 00:57:07,580 --> 00:57:11,020 at mapaglabanan konsepto na kami usapan tungkol sa isang pulutong sa lecture. 1151 00:57:11,020 --> 00:57:14,550 Sa kahulugan na tulad namin sa trabaho mas matalinong, hindi mahirap, kapag hatiin mo 1152 00:57:14,550 --> 00:57:18,120 at mapaglabanan ang mga problema, at masira ang mga ito down, at pagkatapos ay ilagay ang mga ito nang sama-sama, 1153 00:57:18,120 --> 00:57:19,930 magandang bagay na laging mangyayari. 1154 00:57:19,930 --> 00:57:21,960 >> Kaya ang paraan na sumanib sort mahalagang gumagana 1155 00:57:21,960 --> 00:57:24,660 ay na ito naghihiwalay ang isang unsorted array sa kalahati. 1156 00:57:24,660 --> 00:57:26,500 At pagkatapos ito ay nakuha ng dalawang kalahati ng array. 1157 00:57:26,500 --> 00:57:28,220 At kusa itong isinasaayos lamang ang mga dalawang halves. 1158 00:57:28,220 --> 00:57:31,750 Ito ay para mapigil lang naghahati sa kalahati, sa kalahati, sa kalahati hanggang ang lahat ay inayos 1159 00:57:31,750 --> 00:57:33,680 at pagkatapos ay recursively inilalagay ang lahat ng ito nang magkasama. 1160 00:57:33,680 --> 00:57:36,550 >> Kaya na talagang abstract. 1161 00:57:36,550 --> 00:57:38,750 Kaya ito ay lamang ng isang piraso ng pseudocode. 1162 00:57:38,750 --> 00:57:41,040 Ba na magkaroon ng kahulugan sa ang paraan na ito ay tumatakbo? 1163 00:57:41,040 --> 00:57:43,870 Kaya sabihin lamang sabihin mayroon kang isang ang dami ng n elemento, tama? 1164 00:57:43,870 --> 00:57:45,450 Kung ang n ay mas mababa sa 2, maaari kang bumalik. 1165 00:57:45,450 --> 00:57:49,040 Dahil alam mo na kung may lamang ng isang bagay, ito ay dapat na pinagsunod-sunod. 1166 00:57:49,040 --> 00:57:52,600 Iba Pa, mong ayusin ang kaliwang kalahati, at pagkatapos mong ayusin ang kanang kalahati, 1167 00:57:52,600 --> 00:57:54,140 at pagkatapos mong pagsamahin. 1168 00:57:54,140 --> 00:57:56,979 >> Kaya habang mukhang talagang madali na, sa katotohanan, ang pag-iisip tungkol sa mga ito ay 1169 00:57:56,979 --> 00:58:00,270 uri ng mahirap. Dahil ikaw ay tulad ng, well, na uri ng mga tumatakbo sa sarili nito. 1170 00:58:00,270 --> 00:58:00,769 Right? 1171 00:58:00,769 --> 00:58:02,430 Ito ay tumatakbo sa sarili nito. 1172 00:58:02,430 --> 00:58:05,479 Kaya sa na kahulugan, hinawakan David sa recursion sa klase. 1173 00:58:05,479 --> 00:58:07,270 At iyon ay isang konsepto kami makipag-usap tungkol sa higit pa. 1174 00:58:07,270 --> 00:58:11,430 Ito ay na ito, ang mga ito ng dalawang linya dito, talagang ay lamang ang programa 1175 00:58:11,430 --> 00:58:13,860 nagsasabi ito upang magpatakbo ng sarili nito may iba't ibang mga input. 1176 00:58:13,860 --> 00:58:17,230 Kaya sa halip na tumakbo ang sarili sa ang kabuuan ng n elemento, 1177 00:58:17,230 --> 00:58:20,530 maaari mong break na ito down sa mga kaliwang kalahati at ang kanang kalahati 1178 00:58:20,530 --> 00:58:22,680 at pagkatapos ay patakbuhin itong muli. 1179 00:58:22,680 --> 00:58:26,050 >> At pagkatapos ay titingnan namin ito biswal, dahil ako ay isang visual learner. 1180 00:58:26,050 --> 00:58:27,270 Ito ay gumagana mas mahusay para sa akin. 1181 00:58:27,270 --> 00:58:29,890 Kaya kami ay tumingin sa isang visual na halimbawa dito. 1182 00:58:29,890 --> 00:58:36,237 >> Ipagpalagay natin na mayroon kami ng isang array, anim elemento, 3, 5, 2, 6, 4, 1, hindi nakaayos. 1183 00:58:36,237 --> 00:58:37,820 Lahat ng karapatan, mayroong isang pulutong sa pahinang ito. 1184 00:58:37,820 --> 00:58:43,179 Kaya kung maaari pagtingin mo guys sa unang hakbang dito, 3, 5, 2, 6, 4, 1, 1185 00:58:43,179 --> 00:58:44,220 maaari mong hatiin ito sa kalahati. 1186 00:58:44,220 --> 00:58:45,976 Ikaw ay may 3, 5, 2, 6, 4, 1. 1187 00:58:45,976 --> 00:58:48,850 Alam mo na ang mga aren't-- mo hindi alam kung sila ay inayos o hindi, 1188 00:58:48,850 --> 00:58:52,517 kaya patuloy mong paglabag sa kanila down, sa kalahati, sa kalahati, sa kalahati, hanggang sa huli, 1189 00:58:52,517 --> 00:58:53,600 mayroon ka lamang isang element. 1190 00:58:53,600 --> 00:58:56,790 At ang isang elemento ay palaging nakaayos, di ba? 1191 00:58:56,790 --> 00:59:01,560 >> Upang malaman namin na 3, 5, 2, 4, 6, 1, sa pamamagitan ng kanilang sarili, ay nakaayos. 1192 00:59:01,560 --> 00:59:05,870 At ngayon, maaari naming ilagay ang mga ito pabalik sama-sama. 1193 00:59:05,870 --> 00:59:07,510 Upang malaman namin ang 3, 5. 1194 00:59:07,510 --> 00:59:08,510 Inilalagay namin ang mga magkasama. 1195 00:59:08,510 --> 00:59:09,617 Alam namin na ang pinagsunod-sunod na. 1196 00:59:09,617 --> 00:59:10,450 Ang 2 pa rin doon. 1197 00:59:10,450 --> 00:59:11,830 Maaari naming ilagay ang 4 at ang 6 na magkasama. 1198 00:59:11,830 --> 00:59:13,996 Alam namin na na pinagsunod-sunod, kaya ilagay natin na magkasama. 1199 00:59:13,996 --> 00:59:14,940 At ang 1 ay may. 1200 00:59:14,940 --> 00:59:18,720 >> At pagkatapos ay tumingin ka lamang sa ang dalawang halves karapatan dito. 1201 00:59:18,720 --> 00:59:21,300 Ikaw ay may 3, 5, 2, 2, 3, 5. 1202 00:59:21,300 --> 00:59:23,465 Maaari mo lamang ihambing ang simula ng lahat ng bagay. 1203 00:59:23,465 --> 00:59:26,340 Dahil alam mo na ito ay inayos at alam mo na na pinagsunod-sunod. 1204 00:59:26,340 --> 00:59:29,360 Kaya nga hindi mo kahit na may sa ihambing ang 5, ihambing mo ang mga 3. 1205 00:59:29,360 --> 00:59:32,070 At ang 2 ay mas mababa sa 3, kaya kung 2 ay dapat pumunta sa dulo. 1206 00:59:32,070 --> 00:59:33,120 >> Parehong bagay sa banda roon. 1207 00:59:33,120 --> 00:59:34,740 Ang 1 ay dapat pumunta dito. 1208 00:59:34,740 --> 00:59:37,330 At pagkatapos ay kapag pumunta sa iyo upang ilagay dalawang mga halaga sa mga sama-sama, 1209 00:59:37,330 --> 00:59:39,950 alam sa iyo na ito ay inayos at alam mo na na pinagsunod-sunod. 1210 00:59:39,950 --> 00:59:43,240 Kaya pagkatapos ay ang 1 at ang 2, ang 1 ay mas mababa sa 2. 1211 00:59:43,240 --> 00:59:45,570 Iyon ay nagsasabi sa iyo na ang 1 dapat pumunta sa dulo ng ito 1212 00:59:45,570 --> 00:59:47,480 walang kahit na naghahanap sa 3 o 5. 1213 00:59:47,480 --> 00:59:50,100 At pagkatapos ay ang 4, maaari mo lamang suriin, ito ay pumunta sa dito mismo. 1214 00:59:50,100 --> 00:59:51,480 Hindi mo na kailangang hanapin ang 5. 1215 00:59:51,480 --> 00:59:52,570 Parehong bagay na may 6. 1216 00:59:52,570 --> 00:59:55,860 Alam mo na ang 6-- ito lamang ay hindi kailangang tumingin. 1217 00:59:55,860 --> 00:59:57,870 >> At kaya sa paraang iyon, ikaw ay lamang sa pag-save ang iyong sarili 1218 00:59:57,870 --> 00:59:59,526 isang pulutong ng mga hakbang na ito kapag ikaw ay paghahambing. 1219 00:59:59,526 --> 01:00:02,150 Wala kang upang ihambing ang bawat elemento laban sa iba pang mga elemento. 1220 01:00:02,150 --> 01:00:05,230 Lamang ihambing mo laban sa mga na kailangan mo upang ihambing ito laban. 1221 01:00:05,230 --> 01:00:06,870 Kaya na uri ng isang abstract na konsepto. 1222 01:00:06,870 --> 01:00:10,540 Huwag mag-alala kung ito ay hindi lubos na pagpindot sa iyo karapatan pa. 1223 01:00:10,540 --> 01:00:14,740 Ngunit sa pangkalahatan, ito ay kung paano gumagana ang isang uri merge. 1224 01:00:14,740 --> 01:00:17,750 Tanong, mabilis na katanungan, bago ako lumipat sa? 1225 01:00:17,750 --> 01:00:18,550 Oo. 1226 01:00:18,550 --> 01:00:22,230 >> Madla: Kaya sinabi mo na ikaw ay kumuha ng ang 1, at pagkatapos ay ang 4, at ang 6 1227 01:00:22,230 --> 01:00:23,860 at ilagay ang mga ito sa. 1228 01:00:23,860 --> 01:00:26,800 Kaya hindi those-- ay hindi Naghahanap ka ba sa kanila 1229 01:00:26,800 --> 01:00:28,544 bilang hiwalay na mga elemento, hindi gaya ng buo? 1230 01:00:28,544 --> 01:00:29,210 ANDI PENG: Oo. 1231 01:00:29,210 --> 01:00:32,020 Kaya kung ano ang nangyayari ay na ikaw talaga 1232 01:00:32,020 --> 01:00:33,650 ay ang paglikha ng isang bagong tatak ng array. 1233 01:00:33,650 --> 01:00:36,690 Kaya alam mo na, dito, mayroon akong dalawang array ng laki 3, di ba? 1234 01:00:36,690 --> 01:00:39,600 Kaya alam mo na ang aking pinagsunod-sunod array pangangailangan na magkaroon ng anim na mga sangkap. 1235 01:00:39,600 --> 01:00:42,270 Kaya gumawa ka na lamang ng isang bagong halaga ng memorya. 1236 01:00:42,270 --> 01:00:44,270 Kaya ikaw ay uri ng tulad ng pagiging mapag-aksaya ng memory, 1237 01:00:44,270 --> 01:00:46,186 ngunit iyon ay hindi mahalaga dahil ito ay kaya maliit. 1238 01:00:46,186 --> 01:00:48,590 Kaya tingnan mo ang 1 at titingnan mo ang 2. 1239 01:00:48,590 --> 01:00:50,770 At alam mo na ang 1 ay mas mababa sa 2. 1240 01:00:50,770 --> 01:00:53,840 Kaya alam mo na ang 1 ay dapat pumunta sa ang simula ng lahat ng mga iyon. 1241 01:00:53,840 --> 01:00:55,850 >> Hindi mo na kailangan na tingnan ang 3 at ang 5. 1242 01:00:55,850 --> 01:00:57,400 Kaya alam mo 1 napupunta doon. 1243 01:00:57,400 --> 01:00:59,300 Pagkatapos talaga ikaw tumaga off ang 1. 1244 01:00:59,300 --> 01:01:00,370 Ito ay, tulad ng, mga patay na sa amin. 1245 01:01:00,370 --> 01:01:03,690 Pagkatapos kami na lang 2, 3, 5, at pagkatapos ay 4 at 6. 1246 01:01:03,690 --> 01:01:06,270 At pagkatapos mong malaman na, ikaw ihambing ang 4 at ang 2, 1247 01:01:06,270 --> 01:01:07,560 oh, ang 2 ay dapat pumunta sa doon. 1248 01:01:07,560 --> 01:01:09,685 Kaya gumawa ng mapa sa iyo ang 2 down, tumaga off mo ito. 1249 01:01:09,685 --> 01:01:12,060 Kaya pagkatapos mo na lang ang 3 at ang 5 sa 4 at ang 6. 1250 01:01:12,060 --> 01:01:14,650 At mo lamang panatilihin ang pagpuputol ito off hanggang sa inilagay mo ang mga ito sa array. 1251 01:01:14,650 --> 01:01:17,110 >> Madla: Kaya ikaw ay laging lamang paghahambing ng [hindi marinig]? 1252 01:01:17,110 --> 01:01:17,710 >> ANDI PENG: Eksakto. 1253 01:01:17,710 --> 01:01:19,590 Kaya sa kamalayan, ikaw ay lamang sa paghahambing, mahalagang, 1254 01:01:19,590 --> 01:01:21,240 isang numero laban sa iba pang numero. 1255 01:01:21,240 --> 01:01:22,990 At dahil alam mo na ito ay inayos, mo 1256 01:01:22,990 --> 01:01:24,350 Hindi mo na kailangang hanapin sa pamamagitan ng lahat ng mga numero. 1257 01:01:24,350 --> 01:01:25,870 Ikaw lamang ang may upang tumingin sa ang unang isa. 1258 01:01:25,870 --> 01:01:27,582 At pagkatapos ay maaari mo lamang gumawa ng mapa down ang mga ito, dahil alam mo 1259 01:01:27,582 --> 01:01:29,640 pag-aari nila kung saan kailangan nilang nabibilang. 1260 01:01:29,640 --> 01:01:31,030 Oo. 1261 01:01:31,030 --> 01:01:32,920 Magandang tanong. 1262 01:01:32,920 --> 01:01:35,290 >> At pagkatapos ay kung anuman sa iyo ay isang bit mapaglunggati, 1263 01:01:35,290 --> 01:01:38,660 huwag mag-atubiling tingnan ang code na ito. 1264 01:01:38,660 --> 01:01:40,680 Ito ay talagang ang pisikal na pagpapatupad 1265 01:01:40,680 --> 01:01:42,150 ng kung paano namin magsulat pagsasama-uuri. 1266 01:01:42,150 --> 01:01:44,070 At maaari mong makita, ito ay masyadong maikli. 1267 01:01:44,070 --> 01:01:46,310 Ngunit ang mga ideya sa likod mga ito pretty complex. 1268 01:01:46,310 --> 01:01:50,865 Kaya kung sa tingin mo ay tulad ng pagguhit this out sa iyong mga araling-bahay sa gabing ito, huwag mag-atubiling. 1269 01:01:50,865 --> 01:01:54,050 1270 01:01:54,050 --> 01:01:54,740 >> SIGE. 1271 01:01:54,740 --> 01:01:58,070 Kaya din nagpunta si David sa mga ito sa panayam. 1272 01:01:58,070 --> 01:02:00,660 Ano ang mga pinakamahusay na kaso runtimes, pinakamasama runtimes kaso, 1273 01:02:00,660 --> 01:02:05,680 at ang inaasahang runtimes ng pagsasama-uuri? 1274 01:02:05,680 --> 01:02:07,260 Ang isang pares segundo mag-isip. 1275 01:02:07,260 --> 01:02:11,198 Ito ay medyo mahirap, ngunit ang uri ng intuitive kung sa tingin mo ang tungkol dito. 1276 01:02:11,198 --> 01:02:20,090 1277 01:02:20,090 --> 01:02:23,054 Lahat tama. 1278 01:02:23,054 --> 01:02:25,269 >> Madla: ang pinakamasama kaso n log n Ay? 1279 01:02:25,269 --> 01:02:26,060 ANDI PENG: Eksakto. 1280 01:02:26,060 --> 01:02:29,380 At bakit ito n log n. 1281 01:02:29,380 --> 01:02:32,230 >> Madla: Ay hindi ito sapagkat ito nagiging exponentially mas mabilis, 1282 01:02:32,230 --> 01:02:35,390 kaya ito ay tulad ng isang function ng na sa halip na lamang simpleng pagiging n 1283 01:02:35,390 --> 01:02:37,529 nakalapat o isang bagay? 1284 01:02:37,529 --> 01:02:38,320 ANDI PENG: Eksakto. 1285 01:02:38,320 --> 01:02:40,750 Kaya ang dahilan kung bakit ang mga runtime sa mga ito ay n log 1286 01:02:40,750 --> 01:02:44,310 n ay because-- kung ano ang iyong paggawa sa lahat ng mga hakbang na ito? 1287 01:02:44,310 --> 01:02:46,190 Lamang ka pagpuputol ito sa kalahati, di ba? 1288 01:02:46,190 --> 01:02:48,750 At kaya kapag kami ay gumagawa ng mga mag-log, ang lahat na ito ay ginagawa 1289 01:02:48,750 --> 01:02:53,150 ay naghahati ng isang problema sa kalahati, sa kalahati, sa kalahati, sa mas maraming mga halves. 1290 01:02:53,150 --> 01:02:56,430 At sa na kahulugan, maaari mong uri ng maalis ang mga linear na modelo 1291 01:02:56,430 --> 01:02:57,510 na hindi namin ginagamit. 1292 01:02:57,510 --> 01:03:00,254 Dahil kapag tumaga mga bagay-bagay sa kalahati, ito ay isang mag-log. 1293 01:03:00,254 --> 01:03:02,420 Iyan na lamang ang mathematical paraan ng kumakatawan sa mga ito. 1294 01:03:02,420 --> 01:03:06,310 >> At pagkatapos ay sa wakas, sa dulo, ikaw ay paggawa ng lamang ng isang huling pass sa pamamagitan ng 1295 01:03:06,310 --> 01:03:07,930 upang ilagay ang lahat ng mga ito sa pagkakasunud-sunod, i-right? 1296 01:03:07,930 --> 01:03:10,330 At kaya kung mayroon lamang sa iyo upang suriin ang isang bagay, na ang n. 1297 01:03:10,330 --> 01:03:13,420 At kaya ikaw ay uri ng multiply ang dalawang magkasama. 1298 01:03:13,420 --> 01:03:17,660 Kaya ito ay tulad nakuha mo na ang final suriin para n down dito sa isang log ng n 1299 01:03:17,660 --> 01:03:18,390 dito sa taas. 1300 01:03:18,390 --> 01:03:21,060 At kung ikaw ay paramihin kanila, na n log n. 1301 01:03:21,060 --> 01:03:26,100 >> At upang ang mga pinakamahusay na kaso at pinakamasama kaso at inaasahan ay ang lahat n log n. 1302 01:03:26,100 --> 01:03:27,943 Ito ay tulad ng iba pang mga uri din. 1303 01:03:27,943 --> 01:03:30,090 Ito ay tulad ng pagpili ng uri sa kahulugan na ito 1304 01:03:30,090 --> 01:03:32,131 hindi mahalaga kung ano ang iyong listahan ay, ito lamang ay pagpunta 1305 01:03:32,131 --> 01:03:34,801 upang gawin ang parehong bagay sa bawat isang oras. 1306 01:03:34,801 --> 01:03:35,300 SIGE. 1307 01:03:35,300 --> 01:03:39,950 Kaya bilang maaari mong makita ang isang lalaki, kahit na ang uri na kami ay wala through-- n 1308 01:03:39,950 --> 01:03:41,660 nakalapat, ito ay hindi masyadong mahusay. 1309 01:03:41,660 --> 01:03:47,060 At kahit na ito n log n ay hindi ang pinaka mahusay. 1310 01:03:47,060 --> 01:03:49,720 Kung ikaw guys ay kakaiba, mayroong mga mekanismo uri 1311 01:03:49,720 --> 01:03:54,310 na kaya mahusay na ang mga ito halos mahalagang flat sa runtime. 1312 01:03:54,310 --> 01:03:55,420 >> Mayroon kang ilang mga mag-log n ni. 1313 01:03:55,420 --> 01:03:58,190 Mayroon kang ilang mga mag-log-log n ni. 1314 01:03:58,190 --> 01:04:00,330 Hindi namin hawakan sa kanila sa ganitong klase ngayon. 1315 01:04:00,330 --> 01:04:02,663 Ngunit kung ikaw guys ay kakaiba, huwag mag-atubili sa google, kung ano ang 1316 01:04:02,663 --> 01:04:04,392 ang pinaka mahusay na pag-uuri mekanismo. 1317 01:04:04,392 --> 01:04:06,350 Hindi ko alam, may mga ang ilang mga talagang nakakatawa iyan, 1318 01:04:06,350 --> 01:04:09,860 like-- mayroong ilang mga talagang funny mga na gumawa ng mga tao. 1319 01:04:09,860 --> 01:04:12,210 At iniisip mo kung paano sila kailanman naisip na iyon. 1320 01:04:12,210 --> 01:04:15,730 Kaya google, kung mayroon kang ilang mga bakanteng panahon, sa, ano ang ilang mga nakakatawang paraan 1321 01:04:15,730 --> 01:04:17,730 na people-- pati na rin mabisa ways-- tao 1322 01:04:17,730 --> 01:04:20,371 ay maaaring ipatupad ng masama. 1323 01:04:20,371 --> 01:04:20,870 SIGE. 1324 01:04:20,870 --> 01:04:22,880 At dito ay lamang ng isang madaling-magamit na maliit na chart. 1325 01:04:22,880 --> 01:04:26,850 Alam ko ang lahat ng sa iyo, bago na pagsusulit 0, ay magiging sa iyong room marahil sinusubukan 1326 01:04:26,850 --> 01:04:27,960 kabisaduhin iyon. 1327 01:04:27,960 --> 01:04:30,940 Kaya na magaling sa doon para sa iyo guys. 1328 01:04:30,940 --> 01:04:37,120 Lang huwag kalimutan ang logic na made-- kung bakit ang mga numero ay nagaganap. 1329 01:04:37,120 --> 01:04:39,870 Kung palaging ikaw ay nawala, kailangan lang gumawa Siguraduhin na alam mo kung ano ang mga uri ay. 1330 01:04:39,870 --> 01:04:40,820 At maaari mong patakbuhin sa pamamagitan ng ang mga ito sa iyong isip 1331 01:04:40,820 --> 01:04:42,903 upang malaman kung bakit ang mga mga sagot ay ang mga sagot. 1332 01:04:42,903 --> 01:04:46,250 1333 01:04:46,250 --> 01:04:47,600 >> Lahat tama. 1334 01:04:47,600 --> 01:04:49,680 Kaya kami ay pagpunta upang ilipat on, sa wakas, upang maghanap. 1335 01:04:49,680 --> 01:04:51,638 Dahil bilang mga mo na basahin ang pset, 1336 01:04:51,638 --> 01:04:55,175 searching ay bahagi rin ng Nagtatakda ang problemang ito linggong ito. 1337 01:04:55,175 --> 01:04:57,300 Hihilingin sa iyo na ipatupad dalawang uri ng mga paghahanap. 1338 01:04:57,300 --> 01:05:00,070 Ang isa ay isang linear paghahanap at ang isa ay isang binary paghahanap. 1339 01:05:00,070 --> 01:05:01,760 >> Kaya ang haba ng paghahanap ay medyo madali. 1340 01:05:01,760 --> 01:05:04,070 Ikaw lamang ang nais na elemento sa paghahanap ng isang listahan upang makita kung nakuha mo ito. 1341 01:05:04,070 --> 01:05:05,444 Ikaw lamang ang may upang umulit sa pamamagitan ng. 1342 01:05:05,444 --> 01:05:08,170 At kung ito ay katumbas ng isang bagay, maaari kang bumalik lang ito, di ba? 1343 01:05:08,170 --> 01:05:10,890 Ngunit ang isa na hindi namin pinaka interesado sa pakikipag-usap tungkol 1344 01:05:10,890 --> 01:05:14,550 ay binary paghahanap, kanan, kung saan ay ang hatiin at mapaglabanan mekanismo kung saan 1345 01:05:14,550 --> 01:05:18,190 David ay nagpapakita sa panayam. 1346 01:05:18,190 --> 01:05:20,810 >> Tandaan ang mga halimbawa ng telepono ng libro na siya mapigil ang nagdadala up, 1347 01:05:20,810 --> 01:05:23,960 ang isa na siya ang uri ng nahirapan ng kaunti sa ito nakaraang taon, 1348 01:05:23,960 --> 01:05:27,530 kung saan mo hatiin ang problema sa kalahati, sa kalahati, sa kalahati, muli at muli, 1349 01:05:27,530 --> 01:05:30,730 hanggang sa mahanap mo kung ano ang iyong hinahanap? 1350 01:05:30,730 --> 01:05:33,727 At nakuha mo na ang runtime ng na pati na rin. 1351 01:05:33,727 --> 01:05:35,810 At maaari mong makita, ito ay makabuluhang mas mahusay 1352 01:05:35,810 --> 01:05:39,080 kaysa sa anumang iba pang uri ng paghahanap. 1353 01:05:39,080 --> 01:05:41,880 >> Kaya ang paraan na gusto namin pumunta tungkol sa pagpapatupad ng isang binary search 1354 01:05:41,880 --> 01:05:46,510 ay, kung kami ay may isang array, index 0 hanggang 6, pitong elemento, 1355 01:05:46,510 --> 01:05:49,790 maaari naming tumingin sa gitna, right-- Paumanhin, kung ang aming mga tanong first-- 1356 01:05:49,790 --> 01:05:53,840 kung gusto naming tanungin ang tanong ng, ay ang array na naglalaman ng mga elemento ng 7, 1357 01:05:53,840 --> 01:05:56,840 malinaw naman, ang pagiging tao, at pagkakaroon tulad ng isang maliit na hanay, ito ay madali para sa amin 1358 01:05:56,840 --> 01:05:58,210 sabihin ninyo ang oo. 1359 01:05:58,210 --> 01:06:05,750 Ngunit ang mga paraan upang ipatupad ang isang binary search ay upang tumingin sa gitna. 1360 01:06:05,750 --> 01:06:08,020 >> Alam namin na ang index 3 ay gitna, dahil tayo 1361 01:06:08,020 --> 01:06:09,270 kung may mga pitong elemento. 1362 01:06:09,270 --> 01:06:10,670 Ano 7 hinati sa 2? 1363 01:06:10,670 --> 01:06:12,850 Maaari mong tumaga off na ang dagdag na 1. 1364 01:06:12,850 --> 01:06:14,850 Nakuha mo na ang 3 sa gitna. 1365 01:06:14,850 --> 01:06:17,590 Kaya ay ang dami ng mga 3 katumbas ng 7? 1366 01:06:17,590 --> 01:06:18,900 Ito ay hindi, tama? 1367 01:06:18,900 --> 01:06:21,050 Ngunit maaari naming gawin ang isang pares ng mga tseke. 1368 01:06:21,050 --> 01:06:25,380 Ay array of 3 mas mababa sa 7 o ay ang dami ng mga 3 mas malaki kaysa sa 7? 1369 01:06:25,380 --> 01:06:27,240 >> At nalalaman natin na ito ay mas mababa kaysa sa 7. 1370 01:06:27,240 --> 01:06:30,259 Upang malaman namin na, oh, ito ay dapat na hindi sa kaliwang kalahati. 1371 01:06:30,259 --> 01:06:32,300 Alam namin na ito ay dapat na sa kanang kalahati, di ba? 1372 01:06:32,300 --> 01:06:34,662 Kaya maaari lang namin tumaga off ang kalahati ng array. 1373 01:06:34,662 --> 01:06:36,370 Hindi namin kahit na may sa tingnan ang mga ito anymore. 1374 01:06:36,370 --> 01:06:38,711 Dahil alam namin na kalahati ng aming problem-- 1375 01:06:38,711 --> 01:06:41,210 Alam namin na ang mga sagot ay nasa ang kanang kalahati ng aming mga problema. 1376 01:06:41,210 --> 01:06:42,580 Kaya tingnan lang namin sa na ngayon. 1377 01:06:42,580 --> 01:06:44,860 >> Kaya ngayon tinitingnan namin ang mga gitna ng kung ano ang natitira. 1378 01:06:44,860 --> 01:06:46,880 Iyon index 5. 1379 01:06:46,880 --> 01:06:50,200 Ginagawa namin ang parehong muli check at nakita namin na ito ay mas maliit. 1380 01:06:50,200 --> 01:06:52,050 Kaya tingnan natin sa kaliwa ng na. 1381 01:06:52,050 --> 01:06:53,430 At pagkatapos ay namin makita ang check na iyon. 1382 01:06:53,430 --> 01:06:57,600 Ay ang halaga ng array sa index 4 na katumbas ng 7? 1383 01:06:57,600 --> 01:06:58,260 Ito ay. 1384 01:06:58,260 --> 01:07:03,580 Kaya maaari naming nagbabalik ng tunay, dahil natagpuan namin ang mga halaga sa aming listahan. 1385 01:07:03,580 --> 01:07:06,738 Sinusuportahan ba ng paraan nagpunta ako sa pamamagitan na magkaroon ng kahulugan sa lahat ng tao? 1386 01:07:06,738 --> 01:07:08,760 SIGE. 1387 01:07:08,760 --> 01:07:11,670 Bibigyan kita ng isang lalaki na siguro, tulad ng, tatlo, apat na minuto upang malaman kung 1388 01:07:11,670 --> 01:07:13,270 kung paano mag-Pseudocode ito in. 1389 01:07:13,270 --> 01:07:18,070 >> Kaya akala tinanong ko sa iyo na magsulat ng isang function na tinatawag na search () na ibabalik 1390 01:07:18,070 --> 01:07:20,640 isang halaga, isang Boolean halaga, iyon ay totoo o false-- gusto, 1391 01:07:20,640 --> 01:07:22,970 tunay na kung nahanap mo ang halaga, huwad na kung ikaw ay hindi. 1392 01:07:22,970 --> 01:07:25,230 At pagkatapos ay kayo ay lumipas sa ang halaga sa iyo 1393 01:07:25,230 --> 01:07:28,410 hinahanap sa mga halaga, na ay ang array-- oh, talagang ilagay ko 1394 01:07:28,410 --> 01:07:29,410 na sa maling lugar. 1395 01:07:29,410 --> 01:07:29,580 SIGE. 1396 01:07:29,580 --> 01:07:31,829 Anyways, na dapat magkaroon ng naging sa kanan ng halaga. 1397 01:07:31,829 --> 01:07:36,280 At pagkatapos int n ay ang bilang ng mga elemento sa array na. 1398 01:07:36,280 --> 01:07:39,430 Paano mo pumunta tungkol sa pagsubok sa pseudocode na problema sa? 1399 01:07:39,430 --> 01:07:41,630 Bibigyan kita ng isang lalaki tulad ng tatlong minuto upang gawin iyon. 1400 01:07:41,630 --> 01:08:00,137 1401 01:08:00,137 --> 01:08:02,595 Hindi, tingin ko ay may only-- oo, mayroong isang karapatan up dito. 1402 01:08:02,595 --> 01:08:03,261 Madla: Maaari ko bang? 1403 01:08:03,261 --> 01:08:04,388 ANDI PENG: Oo, nakuha ko sa iyo. 1404 01:08:04,388 --> 01:08:09,410 1405 01:08:09,410 --> 01:08:11,050 Ay na working? 1406 01:08:11,050 --> 01:08:12,290 OK, cool. 1407 01:08:12,290 --> 01:10:43,590 1408 01:10:43,590 --> 01:10:44,720 >> SIGE. 1409 01:10:44,720 --> 01:10:47,630 Lahat ng mga karapatan guys, hindi namin pagpunta upang bigyang-laya ang mga ito sa. 1410 01:10:47,630 --> 01:10:49,730 SIGE. 1411 01:10:49,730 --> 01:10:54,020 Kaya akala namin nakuha ang kaibig-ibig maliit na array na may n mga halaga sa loob nito. 1412 01:10:54,020 --> 01:10:55,170 Hindi ko gumuhit ng mga linya. 1413 01:10:55,170 --> 01:10:58,649 Ngunit kung paano namin pumunta tungkol sa sinusubukang isulat ito? 1414 01:10:58,649 --> 01:11:00,440 Sinumang gusto ba sa bigyan ako ang unang linya? 1415 01:11:00,440 --> 01:11:02,814 Kung nais mong ibigay sa akin ang unang linya ng pseudocode. 1416 01:11:02,814 --> 01:11:06,563 1417 01:11:06,563 --> 01:11:08,430 >> Madla: [hindi marinig] 1418 01:11:08,430 --> 01:11:10,138 Madla: Gusto mo gusto upang umulit through-- 1419 01:11:10,138 --> 01:11:11,094 Madla: lamang ng isa pang para sa loop? 1420 01:11:11,094 --> 01:11:11,760 Madla: --for. 1421 01:11:11,760 --> 01:11:15,880 1422 01:11:15,880 --> 01:11:17,780 >> ANDI PENG: Kaya ang isang ito ay isang bit mapanlinlang. 1423 01:11:17,780 --> 01:11:23,130 Isipin about-- gusto mong upang panatilihing tumatakbo ito loop 1424 01:11:23,130 --> 01:11:27,950 paulit-ulit-ulit hanggang kailan? 1425 01:11:27,950 --> 01:11:30,819 >> Madla: Hanggang sa [hindi marinig] halaga ay katumbas ng halaga. 1426 01:11:30,819 --> 01:11:31,610 ANDI PENG: Eksakto. 1427 01:11:31,610 --> 01:11:33,900 Kaya maaari mong talagang lamang write-- maaari naming kahit na gawing simple ito ng mas maraming. 1428 01:11:33,900 --> 01:11:35,630 Maaari lang namin gawin ang isang habang loop, di ba? 1429 01:11:35,630 --> 01:11:39,380 Kaya maaari mo na lang ay loop-- alam namin na ito ay isang habang. 1430 01:11:39,380 --> 01:11:42,850 Ngunit para sa ngayon, ako pagpunta sabihin ang "loop" - sa pamamagitan ng kung ano? 1431 01:11:42,850 --> 01:11:46,640 Umikot until-- kung ano ang ang aming pagtatapos na kalagayan? 1432 01:11:46,640 --> 01:11:47,510 Sa tingin ko narinig ko ito. 1433 01:11:47,510 --> 01:11:48,530 Narinig ko ang isang tao sabihin ito. 1434 01:11:48,530 --> 01:11:51,255 >> Madla: Values ​​katumbas gitna. 1435 01:11:51,255 --> 01:11:52,255 ANDI PENG: Sabihin mo ulit ito. 1436 01:11:52,255 --> 01:11:54,470 Madla: O, hanggang sa halaga ang iyong hinahanap 1437 01:11:54,470 --> 01:11:58,470 para sa ay pantay-pantay sa gitna halaga. 1438 01:11:58,470 --> 01:12:00,280 >> ANDI PENG: Paano kung ito ay hindi doon? 1439 01:12:00,280 --> 01:12:03,113 Paano kung ang halaga ng iyong hinahanap para sa ay hindi tunay na sa array na ito? 1440 01:12:03,113 --> 01:12:05,890 Madla: Bumalik ka 1. 1441 01:12:05,890 --> 01:12:08,850 >> ANDI PENG: Ngunit kung ano ang gusto namin na loop hanggang kung kami ay may isang kondisyon? 1442 01:12:08,850 --> 01:12:09,350 Oo. 1443 01:12:09,350 --> 01:12:11,239 >> Madla: Hanggang mayroong isa lamang na halaga? 1444 01:12:11,239 --> 01:12:13,530 ANDI PENG: Maaari kang loop until-- upang malaman mo na ikaw ay 1445 01:12:13,530 --> 01:12:15,714 pagpunta sa magkaroon ng isang max na halaga, i-right? 1446 01:12:15,714 --> 01:12:18,130 At alam mo na ikaw ay pagpunta na magkaroon ng isang halaga min, di ba? 1447 01:12:18,130 --> 01:12:20,379 Dahil din, na isang bagay Nakalimutan ko na sabihin sa bago, 1448 01:12:20,379 --> 01:12:22,640 na ang isang bagay na kritikal na tungkol sa binary paghahanap 1449 01:12:22,640 --> 01:12:24,182 ay na ang iyong array na pinagsunod-sunod. 1450 01:12:24,182 --> 01:12:26,973 Dahil walang paraan ng paggawa ng na ito kung ang mga ito ay lamang ng random na mga halaga. 1451 01:12:26,973 --> 01:12:29,190 Hindi mo alam kung ang isa ay mas malaki kaysa sa isa, i-right? 1452 01:12:29,190 --> 01:12:32,720 >> Kaya alam mo na ang iyong mga max at iyong mins ang narito, di ba? 1453 01:12:32,720 --> 01:12:35,590 Kung ikaw ay pupunta sa pag-aayos iyong max sa iyong mins at ang mid-- 1454 01:12:35,590 --> 01:12:38,470 akala ni lamang ipaalam sa iyong mid halaga ay tama here-- 1455 01:12:38,470 --> 01:12:43,910 ikaw ay pagpunta sa isa lamang loop hanggang ang iyong minimum ay 1456 01:12:43,910 --> 01:12:47,510 tungkol sa parehong bilang iyong max, kanan, o kung ang iyong max ay hindi ang parehong bilang iyong min. 1457 01:12:47,510 --> 01:12:48,040 Right? 1458 01:12:48,040 --> 01:12:51,340 Dahil kapag nangyari iyon, alam mo na huli mo na pindutin ang parehong halaga. 1459 01:12:51,340 --> 01:12:59,135 Kaya nais mong loop hanggang ang iyong min ay mas mababa sa o katumbas ng to-- Oops, 1460 01:12:59,135 --> 01:13:01,510 hindi mas mababa sa o katumbas ng, ang iba pang paraan around-- max ay. 1461 01:13:01,510 --> 01:13:15,110 1462 01:13:15,110 --> 01:13:16,160 >> Ang ibig na magkaroon ng kahulugan? 1463 01:13:16,160 --> 01:13:18,810 Kinuha ko ng ilang pagsubok upang makakuha ng karapatan. 1464 01:13:18,810 --> 01:13:21,869 Ngunit loop hanggang ang iyong max na halaga ay mahalagang halos mas mababa 1465 01:13:21,869 --> 01:13:23,410 kaysa sa o katumbas ng iyong minimum, di ba? 1466 01:13:23,410 --> 01:13:25,201 Na kapag alam mo na iyong converged. 1467 01:13:25,201 --> 01:13:29,290 Madla: Kapag ang sa iyong maximum halaga na mas mababa kaysa sa minimum na? 1468 01:13:29,290 --> 01:13:31,040 ANDI PENG: Kung patuloy mong pag-aayos ng mga ito, na 1469 01:13:31,040 --> 01:13:32,380 ay kung ano ang kami ay pagpunta na ginagawa sa mga ito. 1470 01:13:32,380 --> 01:13:33,460 Ba na magkaroon ng kahulugan? 1471 01:13:33,460 --> 01:13:35,750 Minimum at max ay lamang integer na tayo ay marahil 1472 01:13:35,750 --> 01:13:39,260 pagpunta sa nais na lumikha upang panatilihin subaybayan ng kung saan kami ay naghahanap. 1473 01:13:39,260 --> 01:13:41,790 Dahil umiiral ang array hindi alintana ng kung anong ginagawa namin. 1474 01:13:41,790 --> 01:13:45,030 Tulad ng, hindi namin hindi aktwal na pisikal na pagpuputol off ang array, di ba? 1475 01:13:45,030 --> 01:13:47,261 Lang kami ng pag-aayos na kung saan kami ay naghahanap. 1476 01:13:47,261 --> 01:13:48,136 Ba na magkaroon ng kahulugan? 1477 01:13:48,136 --> 01:13:48,472 >> Madla: Oo. 1478 01:13:48,472 --> 01:13:49,110 >> ANDI PENG: OK. 1479 01:13:49,110 --> 01:13:57,090 Kaya kung iyon ang kondisyon para sa aming loop, kung ano ang gusto namin sa loob ng loop na ito? 1480 01:13:57,090 --> 01:13:58,700 Ano kami ay pagpunta sa ma-kulang na gawin? 1481 01:13:58,700 --> 01:14:02,390 Kaya ngayon, mayroon ka namin isang max at isang min, kanan, 1482 01:14:02,390 --> 01:14:04,962 Malamang na nilikha up dito lugar. 1483 01:14:04,962 --> 01:14:07,170 Kami ay pagpunta sa marahil nais upang mahanap ang isang gitnang, di ba? 1484 01:14:07,170 --> 01:14:08,450 Paano kami magiging maaaring upang mahanap ang gitna? 1485 01:14:08,450 --> 01:14:09,491 Ano ang mathematical-- 1486 01:14:09,491 --> 01:14:11,079 Madla: Max plus min hinati sa 2. 1487 01:14:11,079 --> 01:14:11,870 ANDI PENG: Eksakto. 1488 01:14:11,870 --> 01:14:20,300 1489 01:14:20,300 --> 01:14:21,620 Ba na magkaroon ng kahulugan? 1490 01:14:21,620 --> 01:14:25,780 At gawin mo guys makita kung bakit namin Hindi lang use-- kung bakit namin ginawa ito 1491 01:14:25,780 --> 01:14:27,850 sa halip ng paggawa ng lamang n hinati sa 2? 1492 01:14:27,850 --> 01:14:30,310 Ito ay dahil n ay isang halaga na pupuntahan manatiling pareho. 1493 01:14:30,310 --> 01:14:30,979 Right? 1494 01:14:30,979 --> 01:14:34,020 Ngunit bilang ayusin namin ang aming minimum at maximum na mga halaga, sila ay pagpunta upang baguhin. 1495 01:14:34,020 --> 01:14:36,040 At bilang isang resulta, ang aming gitnang ay pagpunta sa baguhin masyadong. 1496 01:14:36,040 --> 01:14:37,873 Kaya na ang dahilan kung bakit gusto naming upang gawin ito karapatan dito. 1497 01:14:37,873 --> 01:14:38,510 SIGE. 1498 01:14:38,510 --> 01:14:41,600 >> At pagkatapos ay, ngayon na nalaman namin our-- oo. 1499 01:14:41,600 --> 01:14:44,270 >> Madla: lamang ng isang mabilis question-- kapag sinabi mong min at max, 1500 01:14:44,270 --> 01:14:46,410 tayo sa pagpapalagay na na ito ay inayos? 1501 01:14:46,410 --> 01:14:48,400 >> ANDI PENG: Oo, na talagang isang precondition para sa isang binary paghahanap, 1502 01:14:48,400 --> 01:14:49,816 na kailangan mong malaman kung ito ay pinagsunod-sunod. 1503 01:14:49,816 --> 01:14:53,660 Aling ang dahilan kung bakit ang uri, isulat mo sa iyong itakda ang problema bago ang iyong binary paghahanap. 1504 01:14:53,660 --> 01:14:55,910 SIGE. 1505 01:14:55,910 --> 01:14:58,876 Kaya ngayon na alam namin kung saan ang aming midpoint ay, kung ano ang gusto mong gawin dito? 1506 01:14:58,876 --> 01:15:01,789 1507 01:15:01,789 --> 01:15:04,319 >> Madla: Gusto naming ihambing na sa iba pang isa. 1508 01:15:04,319 --> 01:15:05,110 ANDI PENG: Eksakto. 1509 01:15:05,110 --> 01:15:12,280 Kaya ikaw ay pagpunta upang ihambing kalagitnaan sa halaga, i-right? 1510 01:15:12,280 --> 01:15:14,900 1511 01:15:14,900 --> 01:15:18,670 At ano ang na sabihin sa amin kapag kami ihambing? 1512 01:15:18,670 --> 01:15:22,226 Ano ang gusto naming gawin pagkatapos? 1513 01:15:22,226 --> 01:15:25,389 >> Madla: Kung ang halaga ay mas malaki kaysa sa mid, gusto naming i-cut-off ito. 1514 01:15:25,389 --> 01:15:26,180 ANDI PENG: Eksakto. 1515 01:15:26,180 --> 01:15:33,940 Kaya kung ang halaga ay mas malaki kaysa sa mid, hindi namin 1516 01:15:33,940 --> 01:15:36,550 pagpunta sa nais na baguhin ang mga minimum at maxes, di ba? 1517 01:15:36,550 --> 01:15:38,980 Ano ang gusto namin upang baguhin? 1518 01:15:38,980 --> 01:15:42,145 Kaya kung alam namin ang halaga ay isang lugar sa dito, kung ano ang ginagawa namin sa inyo na baguhin? 1519 01:15:42,145 --> 01:15:44,758 Gusto naming baguhin ang aming mga minimum na mid, di ba? 1520 01:15:44,758 --> 01:15:49,420 1521 01:15:49,420 --> 01:15:54,292 At pagkatapos ng iba pa, kung ito ay sa ito kalahati, ano ang gusto namin upang baguhin? 1522 01:15:54,292 --> 01:15:55,306 >> Madla: Ang iyong maximum. 1523 01:15:55,306 --> 01:15:55,972 ANDI PENG: Oo. 1524 01:15:55,972 --> 01:16:02,597 1525 01:16:02,597 --> 01:16:04,680 At pagkatapos lamang ikaw ay pagpunta upang panatilihin ang looping, di ba? 1526 01:16:04,680 --> 01:16:08,920 Dahil ngayon, pagkatapos ng isang pag-ulit sa pamamagitan ng, mayroon ka ng isang max dito. 1527 01:16:08,920 --> 01:16:10,760 At pagkatapos ay maaari mong muling kalkulahin ang isang kalagitnaan. 1528 01:16:10,760 --> 01:16:11,990 At pagkatapos ay maaari mong ihambing. 1529 01:16:11,990 --> 01:16:14,766 At ikaw ay pagpunta upang panatilihin ang pagpunta hanggang sa min at ang maxes 1530 01:16:14,766 --> 01:16:15,890 may mahalagang converged. 1531 01:16:15,890 --> 01:16:17,890 At na kapag alam mo na ikaw ay pindutin ang dulo nito. 1532 01:16:17,890 --> 01:16:20,280 At alinman na iyong natagpuan ito o hindi mo pa sa puntong iyon. 1533 01:16:20,280 --> 01:16:23,170 >> Ba ito gumawa ng kahulugan sa lahat ng tao? 1534 01:16:23,170 --> 01:16:26,020 1535 01:16:26,020 --> 01:16:26,770 SIGE. 1536 01:16:26,770 --> 01:16:27,900 Ito ay medyo mahalaga, dahil magkakaroon ka ng 1537 01:16:27,900 --> 01:16:29,760 na isulat ito sa iyong code na ngayong gabi. 1538 01:16:29,760 --> 01:16:32,660 Ngunit mayroon kang guys isang magandang magandang kahulugan ng kung ano ang dapat mong ginagawa, 1539 01:16:32,660 --> 01:16:34,051 na kung saan ay mabuti. 1540 01:16:34,051 --> 01:16:34,550 SIGE. 1541 01:16:34,550 --> 01:16:38,840 Kaya mayroon kami tungkol sa pitong section minuto ang natitira. 1542 01:16:38,840 --> 01:16:43,170 Kaya kami ay pagpunta sa makipag-usap tungkol sa pset na ito na makikita ginagawa namin. 1543 01:16:43,170 --> 01:16:46,410 Kaya ang pset ay nahahati sa dalawang halves. 1544 01:16:46,410 --> 01:16:50,230 Ang unang kalahati ay nagsasangkot pagpapatupad ng isang mahanap 1545 01:16:50,230 --> 01:16:54,210 kung saan ka magsulat ng isang linear paghahanap, ang isang binary paghahanap, at isang pag-uuri algorithm. 1546 01:16:54,210 --> 01:16:56,690 >> Kaya ito ay ang unang oras sa isang pset kung saan 1547 01:16:56,690 --> 01:17:00,050 kami ay magiging pagbibigay sa iyo ng isang lalaki kung ano ang tinatawag code ng pamamahagi, na kung saan ay code 1548 01:17:00,050 --> 01:17:02,740 na tayo ay may pre-nakasulat, ngunit iniwan lamang ng ilang mga piraso off 1549 01:17:02,740 --> 01:17:04,635 para sa iyo upang tapusin ang pagsusulat. 1550 01:17:04,635 --> 01:17:07,510 Kaya ikaw lalaki, kapag tiningnan mo ang mga ito code, maaari kang makakuha ng talagang natakot. 1551 01:17:07,510 --> 01:17:08,630 Kung ikaw ay tulad lamang, ahh, ako hindi alam kung ano na ang ginagawa, 1552 01:17:08,630 --> 01:17:11,670 Hindi ko alam, tulad ng, na tila kaya kumplikado, ahh, magpahinga. 1553 01:17:11,670 --> 01:17:12,170 Ito ay OK. 1554 01:17:12,170 --> 01:17:12,930 Basahin ang spec. 1555 01:17:12,930 --> 01:17:16,920 Spec ay magpapaliwanag nang eksakto sa iyo kung ano ang lahat ng mga programang ito ay ginagawa. 1556 01:17:16,920 --> 01:17:20,560 >> Halimbawa, generate.c ay isang programa na darating sa iyong pset. 1557 01:17:20,560 --> 01:17:24,060 Hindi mo talagang may sa hawakan ito, ngunit dapat mong maunawaan kung ano ang ginagawa nito. 1558 01:17:24,060 --> 01:17:28,550 At generate.c, ang lahat ng ito ay ginagawa ay alinman sa pagbuo ng mga random na numero 1559 01:17:28,550 --> 01:17:32,400 o maaari mong bigyan ito ng isang binhi, tulad ng isang nakasaayos number na ito ay tumatagal, 1560 01:17:32,400 --> 01:17:34,140 at ito ay bumubuo ng mas maraming numero. 1561 01:17:34,140 --> 01:17:37,170 Kaya mayroong isang tiyak na paraan upang ipatupad generate.c kung saan 1562 01:17:37,170 --> 01:17:42,760 maaari ka lamang magkaroon ng isang bungkos ng mga numero para sa iyo na subukan ang iyong mga iba pang mga pamamaraan sa. 1563 01:17:42,760 --> 01:17:45,900 >> Kaya kung nais mong, para sa Halimbawa, subukan ang iyong mahanap, 1564 01:17:45,900 --> 01:17:48,970 Gusto mo nais na tumakbo generate.c, makabuo ng grupo ng mga numero, 1565 01:17:48,970 --> 01:17:50,880 at pagkatapos ay patakbuhin ang iyong mga function katulong. 1566 01:17:50,880 --> 01:17:53,930 Ang iyong function Katulong ay kung saan ikaw ay aktwal na pisikal na pagsusulat ng code. 1567 01:17:53,930 --> 01:17:59,330 At sa tingin ng mga Katulong bilang isang file library sumusulat ka na find ang tumatawag. 1568 01:17:59,330 --> 01:18:02,950 At kaya sa loob helpers.c, makikita mo gawin ang paghahanap at pag-uuri. 1569 01:18:02,950 --> 01:18:06,500 >> At pagkatapos ang iyong pagpunta sa mahalagang lamang ilagay ang mga ito sa lahat ng sama-sama. 1570 01:18:06,500 --> 01:18:10,350 Spec ay magsasabi sa iyo kung paano ilagay na sa linya ng command. 1571 01:18:10,350 --> 01:18:14,880 At makikita mo na ang pagsubok kung o hindi ang iyong uri-uriin at paghahanap ay gumagana. 1572 01:18:14,880 --> 01:18:15,870 Cool. 1573 01:18:15,870 --> 01:18:18,720 Nagsimula na ang sinuman at Nakatagpo ng mga problema o mga katanungan 1574 01:18:18,720 --> 01:18:20,520 Mayroon ngayon sila sa mga ito? 1575 01:18:20,520 --> 01:18:21,020 SIGE. 1576 01:18:21,020 --> 01:18:21,476 >> Madla: Maghintay. 1577 01:18:21,476 --> 01:18:21,932 May tanong ako. 1578 01:18:21,932 --> 01:18:22,844 >> ANDI PENG: Oo. 1579 01:18:22,844 --> 01:18:28,390 >> Madla: Kaya sinimulan ko ang paggawa ang haba ng paghahanap sa helpers.c 1580 01:18:28,390 --> 01:18:29,670 at ito ay hindi talaga gumagana. 1581 01:18:29,670 --> 01:18:34,590 Ngunit pagkatapos ay sa ibang pagkakataon, natagpuan ko ang lang namin kung tanggalin ang mga ito at gawin binary paghahanap. 1582 01:18:34,590 --> 01:18:36,991 Kaya ang bagay na ito kung ito ay hindi gumagana? 1583 01:18:36,991 --> 01:18:39,700 1584 01:18:39,700 --> 01:18:41,510 >> ANDI PENG: Maikling sagot ay hindi. 1585 01:18:41,510 --> 01:18:42,642 Ngunit dahil hindi namin not-- 1586 01:18:42,642 --> 01:18:44,350 Madla: Subalit walang sinuman ang talagang suri. 1587 01:18:44,350 --> 01:18:46,058 ANDI PENG: Kami ay hindi kailanman pagpunta upang makita na. 1588 01:18:46,058 --> 01:18:49,590 Ngunit malamang na gusto mong magkaroon ng siguraduhin na ang iyong paghahanap ay gumagana. 1589 01:18:49,590 --> 01:18:51,700 Dahil kung ang iyong linear search ay hindi gumagana, 1590 01:18:51,700 --> 01:18:54,410 pagkatapos pagkakataon ay ang iyong binary paghahanap ay hindi pumapasok sa trabaho pati na rin. 1591 01:18:54,410 --> 01:18:56,646 Dahil ikaw ay may katulad na logic sa pareho ng mga ito. 1592 01:18:56,646 --> 01:18:58,020 At hindi, ito ay hindi talagang mahalaga. 1593 01:18:58,020 --> 01:19:01,300 Kaya ang tanging mga makikita mo naman sa mga uri at binary paghahanap. 1594 01:19:01,300 --> 01:19:02,490 Oo. 1595 01:19:02,490 --> 01:19:06,610 >> At din, ang isang pulutong ng mga bata ay sinusubukan upang makatipon helpers.c. 1596 01:19:06,610 --> 01:19:09,550 Hindi ka talagang pinapayagan upang gawin iyon, dahil helpers.c 1597 01:19:09,550 --> 01:19:11,200 hindi magkaroon ng isang pangunahing pag-andar. 1598 01:19:11,200 --> 01:19:13,550 At kaya dapat mo lamang maging tunay na pag-ipon 1599 01:19:13,550 --> 01:19:18,670 bumuo at hanapin, dahil mahanap tawag helpers.c at ang mga function sa loob nito. 1600 01:19:18,670 --> 01:19:20,790 Kaya na gumagawa ng pag-debug isang sakit sa puwit. 1601 01:19:20,790 --> 01:19:22,422 Ngunit iyon lamang ang kung ano ang mayroon kaming gawin. 1602 01:19:22,422 --> 01:19:23,880 Madla: Gagawin mo lamang ang lahat, di ba? 1603 01:19:23,880 --> 01:19:27,290 ANDI PENG: Maaari mo lamang gumawa ng lahat pati na rin, oo. 1604 01:19:27,290 --> 01:19:28,060 SIGE. 1605 01:19:28,060 --> 01:19:32,570 Kaya na ito sa mga tuntunin ng kung ano ang ang pset ay humihingi sa inyo ang lahat ng dapat gawin. 1606 01:19:32,570 --> 01:19:35,160 Kung mayroon kang anumang mga katanungan, huwag mag atubiling magtanong sa akin pagkatapos ng seksyon. 1607 01:19:35,160 --> 01:19:37,580 Kukunin ko dito para sa, tulad ng, mga 20 minuto. 1608 01:19:37,580 --> 01:19:40,500 >> At oo, ang pset ni talagang hindi na masama. 1609 01:19:40,500 --> 01:19:41,680 Ikaw guys ay dapat na OK. 1610 01:19:41,680 --> 01:19:43,250 Ang mga ito, sundin lamang ang mga alituntunin. 1611 01:19:43,250 --> 01:19:47,840 Uri ng magkaroon ng isang pakiramdam ng pagkakaroon ng, lohikal, kung ano dapat mangyari at ikaw ay multa. 1612 01:19:47,840 --> 01:19:48,690 Huwag masyadong natakot. 1613 01:19:48,690 --> 01:19:50,220 May isang pulutong ng code na nakasulat doon. 1614 01:19:50,220 --> 01:19:53,011 Huwag masyadong natakot kung wala ka maunawaan kung ano ang ibig sabihin ng lahat ng iyon. 1615 01:19:53,011 --> 01:19:54,749 Kung ito ay isang pulutong, ito ay ganap fine. 1616 01:19:54,749 --> 01:19:55,790 At dumating sa oras ng opisina. 1617 01:19:55,790 --> 01:19:57,520 Tutulungan ka namin tingnan. 1618 01:19:57,520 --> 01:20:00,810 >> Madla: Gamit ang dagdag na pag-andar, ang pagtingin namin sa mga up? 1619 01:20:00,810 --> 01:20:03,417 >> ANDI PENG: Oo, ang mga ito ay sa code. 1620 01:20:03,417 --> 01:20:05,750 Sa laro ng 15, kalahati ng na ito ay isinulat para sa iyo. 1621 01:20:05,750 --> 01:20:09,310 Kaya ang mga function ay mayroon na sa code. 1622 01:20:09,310 --> 01:20:12,020 Yep. 1623 01:20:12,020 --> 01:20:12,520 Lahat tama. 1624 01:20:12,520 --> 01:20:14,000 Well, best of luck. 1625 01:20:14,000 --> 01:20:15,180 Ito ay isang kasuklam-suklam na araw. 1626 01:20:15,180 --> 01:20:19,370 Kaya sana ka guys ay hindi pakiramdam masyadong masamang tungkol sa manatili sa loob at sa coding. 1627 01:20:19,370 --> 01:20:22,133