1 00:00:00,000 --> 00:00:11,100 2 00:00:11,100 --> 00:00:12,300 >> SPEAKER 1: Hei visiem! 3 00:00:12,300 --> 00:00:13,890 Laipni lūdzam atpakaļ uz sadaļu. 4 00:00:13,890 --> 00:00:17,480 Tik priecīgs redzēt tik daudzi no jums abiem šeit un ikviens, kurš ir skatoties online. 5 00:00:17,480 --> 00:00:18,760 6 00:00:18,760 --> 00:00:20,920 Tātad, kā parasti welcome atpakaļ. 7 00:00:20,920 --> 00:00:24,360 Es ceru, ka jums visiem bija jauki nedēļas nogalē, pilns ar atpūtu, relaksāciju. 8 00:00:24,360 --> 00:00:26,026 Tas bija skaisti out vakar. 9 00:00:26,026 --> 00:00:27,525 Tātad, es ceru, ka jums patika ārā. 10 00:00:27,525 --> 00:00:28,840 11 00:00:28,840 --> 00:00:30,610 >> Tātad pirmais pāris paziņojumiem. 12 00:00:30,610 --> 00:00:31,920 13 00:00:31,920 --> 00:00:32,700 Šķirošanas. 14 00:00:32,700 --> 00:00:37,350 Tātad, lielākā daļa no jums būtu gotten e-pastu no manis par savu Scratch PSET, 15 00:00:37,350 --> 00:00:39,920 kā arī šķirošanai pēc PSET 1. 16 00:00:39,920 --> 00:00:41,000 17 00:00:41,000 --> 00:00:42,220 Tātad, tikai pāris lietas. 18 00:00:42,220 --> 00:00:45,150 Pārliecinieties, lai izmantotu check50 in style50. 19 00:00:45,150 --> 00:00:47,250 Tie ir paredzēti, lai resursi jums, puiši, 20 00:00:47,250 --> 00:00:50,660 lai pārliecinātos, ka jūs saņemat tik daudz punktus, kā jūs varat 21 00:00:50,660 --> 00:00:52,390 bez nevajadzīgi zaudēt tiem. 22 00:00:52,390 --> 00:00:54,407 Tātad, lietas, piemēram, stilu ir ļoti svarīgi. 23 00:00:54,407 --> 00:00:55,740 Mēs gatavojamies pacelties par to. 24 00:00:55,740 --> 00:00:58,115 Daži no jums, iespējams, jau pamanīju, ka no jūsu PSET. 25 00:00:58,115 --> 00:00:58,920 26 00:00:58,920 --> 00:01:01,450 Un check50 ir tikai ļoti viegls veids, kā pārliecināties 27 00:01:01,450 --> 00:01:05,050 ka mēs esam patiešām atgriešanās ko ir jānosūta atpakaļ lietotājam, 28 00:01:05,050 --> 00:01:06,690 un ka viss strādā pareizi. 29 00:01:06,690 --> 00:01:08,690 30 00:01:08,690 --> 00:01:12,040 >> Par otro piezīmi, pārliecinieties, ka jūsu augšupielādējot lietas uz pareizo mapi. 31 00:01:12,040 --> 00:01:14,470 Tas padara manu dzīvi tikai mazliet grūtāk 32 00:01:14,470 --> 00:01:18,836 ja jūs augšupielādēt PSET 2 uz PSET 1 jo, kad es lejupielādēt lietas, 33 00:01:18,836 --> 00:01:20,085 tie nav lejupielādēt pareizi. 34 00:01:20,085 --> 00:01:21,690 35 00:01:21,690 --> 00:01:24,560 Un es zinu, tas ir mazliet ļodzīgs sistēmā, lai saņemtu izmantoti, lai, 36 00:01:24,560 --> 00:01:26,950 bet vienkārši super uzmanīgiem, ja tikai man, 37 00:01:26,950 --> 00:01:30,080 tā, ka tad, kad jūs saņemat e-pastus pie kā 02:00 un es esmu šķirošanu. 38 00:01:30,080 --> 00:01:33,710 Ja nevar izraisīt man ir jāskatās visapkārt jūsu PSET. 39 00:01:33,710 --> 00:01:34,440 Atdzist. 40 00:01:34,440 --> 00:01:37,270 >> Es zinu, tas ir agri, bet es pilnīgi got pacēlies aizsargs 41 00:01:37,270 --> 00:01:40,800 ar eseju, kas ir saistīts ar šo piektdien, šā manas profesori bija tieši tāpat, oh yeah. 42 00:01:40,800 --> 00:01:42,550 Atcerieties, ka jums ir eseja dēļ piektdien. 43 00:01:42,550 --> 00:01:45,780 Tātad, es zinu, neviens patīk domāt par midterms, 44 00:01:45,780 --> 00:01:50,620 bet jūsu pirmais viktorīna ir oktobrī 15, kas Oktobris ir sākot no šīs nedēļas. 45 00:01:50,620 --> 00:01:53,290 Tātad, tas varētu būt ātrāk nekā jūs gaidīts ir viss. 46 00:01:53,290 --> 00:01:57,510 Tāpēc, ka jūs neesat nometusi aizsargu Es minēju nākamnedēļ sadaļu šo oh, 47 00:01:57,510 --> 00:02:00,560 Jūsu viktorīna nākamnedēļ, es domāju Es gribētu dot jums mazliet vairāk 48 00:02:00,560 --> 00:02:01,500 ar galvu uz augšu tagad. 49 00:02:01,500 --> 00:02:02,970 50 00:02:02,970 --> 00:02:04,660 >> Tātad, jūsu problēma noteikt, skaits ir trīs. 51 00:02:04,660 --> 00:02:07,070 Cik cilvēki ir izlasījis spec aiz ziņkārības? 52 00:02:07,070 --> 00:02:08,560 53 00:02:08,560 --> 00:02:09,199 OK. 54 00:02:09,199 --> 00:02:10,229 Mēs saņēmām pāris. 55 00:02:10,229 --> 00:02:12,320 Veida leju no pēdējās nedēļā, bet tas ir OK. 56 00:02:12,320 --> 00:02:13,650 Es zinu, tas bija skaisti out. 57 00:02:13,650 --> 00:02:15,120 58 00:02:15,120 --> 00:02:16,660 Tik Break Out. 59 00:02:16,660 --> 00:02:21,010 Noteikti pēc jums izdarīt šodien lasīt jūsu spec vismaz 60 00:02:21,010 --> 00:02:25,240 mēģināt tāpat lejupielādējot izplatīšanas kodu un skriešana 61 00:02:25,240 --> 00:02:27,430 tāpat kā pirmajā, lieta, ka viņi lūdz jums. 62 00:02:27,430 --> 00:02:28,681 63 00:02:28,681 --> 00:02:32,590 Tāpēc, ka mēs izmantojam izplatīšanas kodu un bibliotēku 64 00:02:32,590 --> 00:02:36,790 ka mēs esam tikai bijuši using-- --It ir tikai otrā reize, kad mēs esam darījuši šo PSET, 65 00:02:36,790 --> 00:02:38,650 trakas lietas var notikt ar savu ierīci, 66 00:02:38,650 --> 00:02:41,370 un jūs vēlaties, lai atrastu, ka kas tagad pret vēlāk. 67 00:02:41,370 --> 00:02:45,570 >> Jo, ja tas ir ceturtdienas vakarā, vai tas ir Svētdienas nakts un kādu iemeslu dēļ 68 00:02:45,570 --> 00:02:48,912 jūsu ierīce vienkārši nav vēlas darboties ar bibliotēku 69 00:02:48,912 --> 00:02:50,620 vai ar izplatīšanu kodu, tas nozīmē 70 00:02:50,620 --> 00:02:52,309 Jūs nevarat pat sākt darīt kodēšana. 71 00:02:52,309 --> 00:02:54,100 Jo jūs nevarat pārbaudīt lai redzētu, vai tas darbojas. 72 00:02:54,100 --> 00:02:55,975 Jūsu nav gonna būt iespējai lai redzētu, vai tas apkopo. 73 00:02:55,975 --> 00:03:00,500 Jūs vēlaties rūpēties par tiem sākumā nedēļā, kad jūs joprojām varat e-pastu man 74 00:03:00,500 --> 00:03:03,100 vai viens no pārējiem TFS, un mēs varam iegūt to, kas noteikts. 75 00:03:03,100 --> 00:03:05,410 Jo tie ir jautājumi, kas gatavojas pārtraukt jums 76 00:03:05,410 --> 00:03:07,120 no jebkādu reālu progresu. 77 00:03:07,120 --> 00:03:10,055 Tas nav kā vienu bug, ka Jūs varat vienkārši veida izlaist. 78 00:03:10,055 --> 00:03:10,712 79 00:03:10,712 --> 00:03:13,420 Ja jums ir problēmas ar jūsu ierīce vai izplatīšana kods, 80 00:03:13,420 --> 00:03:16,211 jūs tiešām vēlaties, lai iegūtu, ka jāņem rūp ātrāk nekā vēlāk. 81 00:03:16,211 --> 00:03:20,410 Tātad, pat ja jūs ne gonna reāli sākt kodēšanu, lejupielādēt izplatīšanu 82 00:03:20,410 --> 00:03:24,040 kods, lasīt spec, pārliecinieties viss strādā tur. 83 00:03:24,040 --> 00:03:25,134 OK? 84 00:03:25,134 --> 00:03:27,675 Ja jūs varat darīt, ka es sola savu dzīvi būs vieglāk. 85 00:03:27,675 --> 00:03:28,800 86 00:03:28,800 --> 00:03:31,410 Un tāpēc jūs, iespējams, gatavojas to izdarīt tieši tagad taisnība? 87 00:03:31,410 --> 00:03:32,100 OK. 88 00:03:32,100 --> 00:03:33,950 Tātad, kādi jautājumi tur? 89 00:03:33,950 --> 00:03:35,850 Jebkuras loģistikas lietas? 90 00:03:35,850 --> 00:03:36,910 Ikvienam ir labs? 91 00:03:36,910 --> 00:03:38,270 OK. 92 00:03:38,270 --> 00:03:41,700 >> Atruna par tiem Jūs istabā un internetā. 93 00:03:41,700 --> 00:03:45,437 Es esmu būs mēģina pārslēgties starp PowerPoint ierīcē 94 00:03:45,437 --> 00:03:47,270 jo mēs gatavojamies lai dara dažas kodēšana 95 00:03:47,270 --> 00:03:53,630 šodien tautas pieprasījums anonīms ierosinājums aptauja Es izsūtīti pagājušajā nedēļā. 96 00:03:53,630 --> 00:03:55,480 Tātad, mēs darīsim zināmu kodēšanu. 97 00:03:55,480 --> 00:03:57,800 Tātad, ja jūs puiši arī vēlaties uguns jūsu ierīces, 98 00:03:57,800 --> 00:04:02,910 un jums vajadzētu būt saņēmu e-pastu no manis, ar parauga failu. 99 00:04:02,910 --> 00:04:04,310 Lūdzu, jūtieties brīvi, lai to izdarītu. 100 00:04:04,310 --> 00:04:07,340 >> Tātad, mēs esam gatavojas runāt par GDB, kas ir atkļūdotājs. 101 00:04:07,340 --> 00:04:09,970 Tas notiek, lai palīdzētu jums veida izdomāt, kur 102 00:04:09,970 --> 00:04:11,860 lietas notiek nepareizi savu kodu. 103 00:04:11,860 --> 00:04:15,370 Tas patiešām ir tikai veids, kā jūs soli caur savu kodu, kā tas notiek, 104 00:04:15,370 --> 00:04:19,100 un varēs izdrukāt mainīgos vai redzēt to, kas patiesībā notiek 105 00:04:19,100 --> 00:04:22,980 ar kapuci verses savu programmu tikai darbojas, tas ir, piemēram faulting, 106 00:04:22,980 --> 00:04:25,030 un jūs, piemēram, nav ideju to, kas tikko notika šeit. 107 00:04:25,030 --> 00:04:26,730 Es nezinu, ko līnija tas neizdevās. 108 00:04:26,730 --> 00:04:29,040 Es nezinu, kur tas gāja greizi. 109 00:04:29,040 --> 00:04:31,280 Tātad, GDB notiek, lai palīdzētu jums ar to. 110 00:04:31,280 --> 00:04:35,240 Arī tad, ja jūs nolemjat turpināt jā, un ņem 61, 111 00:04:35,240 --> 00:04:38,430 tas tiešām, tiešām ir jūsu labākais draugs, izraisīt Es varu jums pateikt 112 00:04:38,430 --> 00:04:40,840 jo es eju caur šo klasi. 113 00:04:40,840 --> 00:04:43,620 >> Mēs ejam apskatīt bināro meklēšana, kas, ja jūs guys atcerēties 114 00:04:43,620 --> 00:04:47,540 liels tālruni grāmatu piemērs izrāde no klases. 115 00:04:47,540 --> 00:04:50,620 Mēs būsim īstenošanai ka, un ejot cauri, ka mazliet vairāk, 116 00:04:50,620 --> 00:04:54,650 un tad mēs ejam cauri četriem dažādu veidu, kas ir burbulis, 117 00:04:54,650 --> 00:04:56,285 Atlase, ievietošana, un apvienot. 118 00:04:56,285 --> 00:04:57,830 119 00:04:57,830 --> 00:04:58,330 Atdzist. 120 00:04:58,330 --> 00:05:00,390 Tātad, GDB kā jau minēju, ir atkļūdotājs. 121 00:05:00,390 --> 00:05:01,400 122 00:05:01,400 --> 00:05:09,370 Un tie ir sava veida liels lietas, lielie funkcijas vai komandas 123 00:05:09,370 --> 00:05:13,240 ka jūs izmantojat laikā GDB, un es staigāt Jūs caur demo tā sekundē. 124 00:05:13,240 --> 00:05:15,360 >> Tātad, tas ir ne tikai gatavojas palikt abstrakts. 125 00:05:15,360 --> 00:05:18,000 Es mēģināšu, un padarīt to par betona cik vien iespējams, lai jūs puiši. 126 00:05:18,000 --> 00:05:19,870 Tātad, pauze. 127 00:05:19,870 --> 00:05:22,200 Tas būs vai nu būs pārtraukums piemēram, daži skaits, kas 128 00:05:22,200 --> 00:05:26,900 pārstāv līniju savu programmu, vai jūs varat nosaukt funkciju. 129 00:05:26,900 --> 00:05:30,150 Tātad, ja jūs sakāt pauze galvenais, tas apstāsies pie galvenā, 130 00:05:30,150 --> 00:05:32,400 un ļauj staigāt pa šo funkciju. 131 00:05:32,400 --> 00:05:36,350 >> Tāpat, ja jums ir kāds ārējs darboties kā Swap vai Cube, 132 00:05:36,350 --> 00:05:38,450 ka mēs paskatījās pagājušajā nedēļā. 133 00:05:38,450 --> 00:05:41,780 Ja jūs sakāt pauze viens no tiem, kad jūsu programma hits, ka, 134 00:05:41,780 --> 00:05:44,290 tas būs jāgaida, lai jūs varētu pateikt to, ko darīt. 135 00:05:44,290 --> 00:05:47,860 Pirms tas būs tikai izpildīt, lai jūs reāli varētu pastiprināt iekšpusē funkciju 136 00:05:47,860 --> 00:05:49,020 un redzēt, kas notiek. 137 00:05:49,020 --> 00:05:50,370 138 00:05:50,370 --> 00:05:53,515 Tātad, Next, tikai Lēcieni pār Nākamais līnija iet pāri funkcijas. 139 00:05:53,515 --> 00:05:54,730 140 00:05:54,730 --> 00:05:55,560 Soli. 141 00:05:55,560 --> 00:05:56,810 Tie visi ir nedaudz abstrakti. 142 00:05:56,810 --> 00:06:00,530 Tātad, es esmu tikai gatavojas palaist caur tiem, bet jūs redzēsiet tos izmantošanai sekundē. 143 00:06:00,530 --> 00:06:01,810 >> Soli funkciju. 144 00:06:01,810 --> 00:06:04,170 Tā kā es jau teicu, kā ar Swap, tas būtu 145 00:06:04,170 --> 00:06:07,110 ļauj faktiski it kā jūs esat tāpat kā fiziski pastiprināšanu iekšā, 146 00:06:07,110 --> 00:06:10,990 Jūs varat sajaukt ar šiem mainīgajiem, drukas , kādi viņi ir, redzēt, kas notiek. 147 00:06:10,990 --> 00:06:12,140 148 00:06:12,140 --> 00:06:14,830 Saraksts tiks burtiski vienkārši izdrukāt ārā apkārtējo kodu. 149 00:06:14,830 --> 00:06:17,570 Tātad, ja jūs veida aizmirst kur jums ir jūsu programmā, 150 00:06:17,570 --> 00:06:19,880 vai jūs domājām kas notiek ap to, 151 00:06:19,880 --> 00:06:23,790 tas vienkārši izdrukāt segments no patīk piecas vai sešas līnijas ap to. 152 00:06:23,790 --> 00:06:26,080 Tātad, jūs varat saņemt orientēta par to, kur jūs esat. 153 00:06:26,080 --> 00:06:27,230 154 00:06:27,230 --> 00:06:28,650 >> Izdrukāt kādu mainīgs. 155 00:06:28,650 --> 00:06:34,590 Tātad, ja jums ir, piemēram, atslēgu ar ķeizaru, ka mēs apskatīt. 156 00:06:34,590 --> 00:06:36,220 Jūs varat teikt, Print atslēga jebkurā brīdī. 157 00:06:36,220 --> 00:06:40,070 Tas jums pateiks, kāda vērtība ir tik ka varbūt kaut kur pa ceļam, 158 00:06:40,070 --> 00:06:42,070 Jūs pārrakstīja savu atslēgu. 159 00:06:42,070 --> 00:06:45,495 Jūs faktiski var teikt, ka, jo jūs faktiski var novērot šo vērtību. 160 00:06:45,495 --> 00:06:46,500 161 00:06:46,500 --> 00:06:48,780 >> Jo vietējie, tikai izdrukas savu vietējo mainīgie. 162 00:06:48,780 --> 00:06:53,120 Tātad, jebkurā laikā jūs esat ietvaros cilpu, un jūs vienkārši vēlaties redzēt, piemēram, oh. 163 00:06:53,120 --> 00:06:54,270 Kas ir mana es? 164 00:06:54,270 --> 00:06:57,020 Kas tas ir galvenās vērtības ka es sāktu šeit? 165 00:06:57,020 --> 00:06:58,537 Kāds ir vēstījums šajā brīdī? 166 00:06:58,537 --> 00:07:00,370 Tas būs tikai drukāt visu no tiem, tā, ka jums 167 00:07:00,370 --> 00:07:04,330 nav atsevišķi saka, Print I. Print Message. 168 00:07:04,330 --> 00:07:04,970 Print Key. 169 00:07:04,970 --> 00:07:06,190 170 00:07:06,190 --> 00:07:07,700 Un tad Display. 171 00:07:07,700 --> 00:07:10,370 Kas, ka tas ir, kā jūs soli, izmantojot programmu, 172 00:07:10,370 --> 00:07:13,980 tas būs tikai pārliecinieties, ka tā ir attēlot kādu noteiktu mainīgo 173 00:07:13,980 --> 00:07:14,780 ikvienā vietā. 174 00:07:14,780 --> 00:07:17,160 Tā, ka jūs also-- --it ir veida īsceļu kur 175 00:07:17,160 --> 00:07:19,530 jums nav, lai saglabātu turpinās, piemēram, oh. 176 00:07:19,530 --> 00:07:23,150 Print Key vai Print I. Tas vienkārši automātiski darīt to you. 177 00:07:23,150 --> 00:07:25,959 >> Tātad, ar to, ka mēs ejam lai redzētu, kā tas notiek. 178 00:07:25,959 --> 00:07:28,000 Es esmu gatavojas izmēģināt un slēdzis pār manu ierīci. 179 00:07:28,000 --> 00:07:30,200 180 00:07:30,200 --> 00:07:31,271 Redzēt, ja es varētu darīt. 181 00:07:31,271 --> 00:07:31,770 Viss. 182 00:07:31,770 --> 00:07:40,970 183 00:07:40,970 --> 00:07:42,370 Mēs esam tikai gatavojas atspoguļot to. 184 00:07:42,370 --> 00:07:44,530 Tur nekas traks par manu klēpjdators anyways. 185 00:07:44,530 --> 00:07:49,600 186 00:07:49,600 --> 00:07:50,100 OK. 187 00:07:50,100 --> 00:07:57,030 188 00:07:57,030 --> 00:08:01,054 Tas ir nepieciešams, lai šis viens. 189 00:08:01,054 --> 00:08:01,795 Tas ir tik niecīga. 190 00:08:01,795 --> 00:08:03,730 191 00:08:03,730 --> 00:08:05,120 Let 's redzēt, ja mēs varam izdarīt. 192 00:08:05,120 --> 00:08:09,970 193 00:08:09,970 --> 00:08:10,940 >> OK. 194 00:08:10,940 --> 00:08:15,305 Alise ir acīmredzami cīnās šeit tikai mazliet, 195 00:08:15,305 --> 00:08:17,995 bet mēs saņemsiet to tādā Momento. 196 00:08:17,995 --> 00:08:20,810 197 00:08:20,810 --> 00:08:22,020 OK. 198 00:08:22,020 --> 00:08:25,900 Mēs esam tikai gatavojas palielināt. 199 00:08:25,900 --> 00:08:28,770 200 00:08:28,770 --> 00:08:29,380 OK. 201 00:08:29,380 --> 00:08:31,679 Var ikviens veida redzat? 202 00:08:31,679 --> 00:08:32,470 Varbūt mazliet? 203 00:08:32,470 --> 00:08:33,594 Es zinu, tas ir pārāk mazs. 204 00:08:33,594 --> 00:08:34,570 205 00:08:34,570 --> 00:08:37,530 Jūs nevar gluži izrēķināt kā padarīt šo lielāks. 206 00:08:37,530 --> 00:08:38,350 Ja kāds zina. 207 00:08:38,350 --> 00:08:40,309 Vai kāds zina, kā padarīt to lielāks? 208 00:08:40,309 --> 00:08:40,932 OK. 209 00:08:40,932 --> 00:08:42,140 Mēs ejam, lai roll ar to. 210 00:08:42,140 --> 00:08:45,801 Nav svarīgi, anyways, jo tas ir tikai tas ir kods, kas jūs guys vajadzētu 211 00:08:45,801 --> 00:08:46,300 ir. 212 00:08:46,300 --> 00:08:48,310 >> Kas ir vēl svarīgāk ir terminālis šeit. 213 00:08:48,310 --> 00:08:52,840 214 00:08:52,840 --> 00:08:58,690 Un mēs esam šeit Kāpēc tas ir tik mazs? 215 00:08:58,690 --> 00:09:02,325 216 00:09:02,325 --> 00:09:02,825 Iestatījumus. 217 00:09:02,825 --> 00:09:07,920 218 00:09:07,920 --> 00:09:08,420 Oh. 219 00:09:08,420 --> 00:09:09,500 True Ike. 220 00:09:09,500 --> 00:09:10,880 Kā tas ir? 221 00:09:10,880 --> 00:09:11,770 No turienes ārā. 222 00:09:11,770 --> 00:09:19,370 223 00:09:19,370 --> 00:09:21,810 Ir tā, ka labāk par visiem? 224 00:09:21,810 --> 00:09:22,525 OK ,. 225 00:09:22,525 --> 00:09:23,025 Atdzist. 226 00:09:23,025 --> 00:09:25,830 227 00:09:25,830 --> 00:09:28,220 >> Jūs zināt, kad tu esi CS klases tehniskas grūtības 228 00:09:28,220 --> 00:09:32,971 ir sava veida daļa the-- Tātad, pieņemsim skaidrs tas. 229 00:09:32,971 --> 00:09:33,470 OK. 230 00:09:33,470 --> 00:09:38,060 Tātad, tepat sadaļā, kas mums bija šeit. 231 00:09:38,060 --> 00:09:40,830 Cēzars ir izpildāmais fails. 232 00:09:40,830 --> 00:09:41,800 Tāpēc es to. 233 00:09:41,800 --> 00:09:46,370 Tātad, viena lieta ir saprast, ar GDB ir ka tas darbojas tikai izpildāmos failus. 234 00:09:46,370 --> 00:09:48,040 Tātad, jūs nevarat palaist to uz dotsy. 235 00:09:48,040 --> 00:09:50,532 Jums ir, lai faktiski padarītu Pārliecinieties, ka jūsu kods apkopo, 236 00:09:50,532 --> 00:09:51,865 un ka tas faktiski var darboties. 237 00:09:51,865 --> 00:09:52,970 238 00:09:52,970 --> 00:09:56,186 >> Tātad, pārliecinieties, ka, ja tas tā nav sastādīt, saņemt to apkopot, 239 00:09:56,186 --> 00:09:57,810 lai jūs varētu veida palaist caur to. 240 00:09:57,810 --> 00:10:04,590 Tātad, lai sāktu GDB, viss, kas jums jādara, Gloria tips GDB, un tad tikai 241 00:10:04,590 --> 00:10:06,250 failu, ka jūs vēlaties. 242 00:10:06,250 --> 00:10:08,240 Es vienmēr kļūdaini Cēzaru. 243 00:10:08,240 --> 00:10:11,730 Bet jūs vēlaties, lai pārliecinātos jo tas ir izpildāms, 244 00:10:11,730 --> 00:10:14,210 TI dot flash tā, ka nozīmē, ka jūs esat gatavojas 245 00:10:14,210 --> 00:10:19,240 palaist CSI jūs gatavojas izpildīt šo failus vai nu ar atkļūdotājs. 246 00:10:19,240 --> 00:10:19,910 OK. 247 00:10:19,910 --> 00:10:22,885 Tātad, jūs, jūs saņemsiet šāda veida buldurēšana. 248 00:10:22,885 --> 00:10:24,250 249 00:10:24,250 --> 00:10:25,750 Tas ir tikai visas lietas par atkļūdotājs. 250 00:10:25,750 --> 00:10:28,200 Jums nav tiešām ir jāuztraucas par to tieši tagad. 251 00:10:28,200 --> 00:10:31,460 Un, kā jūs redzat, mums ir šis atvērt parens, IKP, tuvu parens, 252 00:10:31,460 --> 00:10:34,690 un tikko veida izskatās Mūsu komandrindas, vai ne? 253 00:10:34,690 --> 00:10:37,010 >> Tātad, ko mēs gribam, lai do-- --So, Pirmā lieta 254 00:10:37,010 --> 00:10:39,570 ir, mēs gribam, lai izvēlētos vieta lauzt. 255 00:10:39,570 --> 00:10:42,332 Tātad, ir viena kļūda šajā Caesar programmā 256 00:10:42,332 --> 00:10:44,290 ka es ieviest, ka mēs ejam, lai uzzinātu. 257 00:10:44,290 --> 00:10:45,330 258 00:10:45,330 --> 00:10:56,350 Tas Kas tas ir nepieciešams, ievadi Barfoo visos cepures, un kādu iemeslu dēļ 259 00:10:56,350 --> 00:11:01,950 tas nemaina A. Tas vienkārši atstāj tas vien, ir viss pārējais pareizi, 260 00:11:01,950 --> 00:11:03,980 bet otrā vēstule Paliek nemainīgs. 261 00:11:03,980 --> 00:11:07,120 Tātad, mēs ejam, lai mēģinātu saprast, kāpēc tas ir. 262 00:11:07,120 --> 00:11:10,440 Tātad, pirmā lieta, ko jūs parasti vēlas darīt, kad sākat GDB 263 00:11:10,440 --> 00:11:12,010 ir izdomāt, kur to lauzt. 264 00:11:12,010 --> 00:11:14,956 >> Tātad Cēzars ir diezgan īss programma. 265 00:11:14,956 --> 00:11:16,330 Mums vienkārši ir viena funkcija, vai ne? 266 00:11:16,330 --> 00:11:18,520 Kāda bija mūsu funkcija Cēzara? 267 00:11:18,520 --> 00:11:19,590 268 00:11:19,590 --> 00:11:24,350 Tur ir tikai viena funkcija, Main labi? 269 00:11:24,350 --> 00:11:26,490 Galvenais ir funkcija visiem jūsu programmas. 270 00:11:26,490 --> 00:11:29,230 Ja jums nebija Main, es varētu būt mazliet noraizējies tieši tagad, 271 00:11:29,230 --> 00:11:31,000 bet es ceru, ka jūs visi bija Main tur. 272 00:11:31,000 --> 00:11:34,150 Tātad, ko mēs varam darīt, ir, mēs varam vienkārši pauze Main, tieši tāpat. 273 00:11:34,150 --> 00:11:35,190 Tātad, tā saka, OK. 274 00:11:35,190 --> 00:11:37,430 Mēs, kas mūsu pārtraukumpunkts vienu tur. 275 00:11:37,430 --> 00:11:42,870 >> Tātad, tagad ir atcerēties, Caesar aizņem viens komandrindas argumentu tiesības 276 00:11:42,870 --> 00:11:45,150 un mēs neesam darījuši, ka nekur vēl. 277 00:11:45,150 --> 00:11:47,560 Tātad, ko jūs darāt, ir tad, kad jūs tiešām iet palaist 278 00:11:47,560 --> 00:11:51,540 programma, jebkura programma, kas jūs esat darbojas GDB kas nepieciešams komandrindu 279 00:11:51,540 --> 00:11:55,010 argumenti, jūs gatavojas ievadi kad jūs pirmo reizi sākt rādīt to. 280 00:11:55,010 --> 00:11:59,280 Tātad, šajā gadījumā, mēs darām Palaist ar atslēgu trīs. 281 00:11:59,280 --> 00:12:00,770 282 00:12:00,770 --> 00:12:02,040 Un tas faktiski sākt. 283 00:12:02,040 --> 00:12:08,480 >> Tātad, ja jūs redzat šeit, mēs esam Ja RC nav vienāds ar 2. 284 00:12:08,480 --> 00:12:12,210 Tātad, ja jūs puiši visi ir ka fails, es izsūtīti uz augšu 285 00:12:12,210 --> 00:12:15,100 jūs redzēsiet, ka tas ir tāpat kā Pirmā līnija mūsu galvenais uzdevums, vai ne? 286 00:12:15,100 --> 00:12:17,890 Tas pārbaudi, lai redzētu, vai mēs esam pareizais vairāki argumenti. 287 00:12:17,890 --> 00:12:20,620 Tātad, ja jūs domājām ja RC ir pareiza, 288 00:12:20,620 --> 00:12:23,250 jūs varat darīt kaut ko tāpat kā Print RC. 289 00:12:23,250 --> 00:12:24,380 290 00:12:24,380 --> 00:12:28,640 RC ir divi, kas ir tas, ko mēs gaidīts, vai ne? 291 00:12:28,640 --> 00:12:32,010 >> Tātad, mēs varam doties tālāk, un turpināsies līdz. 292 00:12:32,010 --> 00:12:33,200 Tātad, mums ir dažas taustiņu tur. 293 00:12:33,200 --> 00:12:34,260 294 00:12:34,260 --> 00:12:37,090 Un mēs varam izdrukāt savu atslēgu lai pārliecinātos, ka ir pareizi. 295 00:12:37,090 --> 00:12:38,380 296 00:12:38,380 --> 00:12:39,500 Interesanti. 297 00:12:39,500 --> 00:12:41,210 Ne gluži tas, ko mēs gaidīts. 298 00:12:41,210 --> 00:12:44,810 Tātad, viena lieta, lai realizētu ar GDB arī ir 299 00:12:44,810 --> 00:12:49,000 ka tas nav, kamēr jūs faktiski hit Nākamais, ka līnija, kas jūs tikko redzēju 300 00:12:49,000 --> 00:12:50,720 faktiski izpildīts. 301 00:12:50,720 --> 00:12:53,870 Tātad, šajā gadījumā Key nav piešķirts vēl. 302 00:12:53,870 --> 00:12:57,050 Tātad, Key ir daži atkritumu vērtība ka jūs redzēt uz grunts tur. 303 00:12:57,050 --> 00:13:03,680 Negatīvs $ 120-- --It s viens miljards un kaut nepāra lietas pareizi? 304 00:13:03,680 --> 00:13:05,340 Tas nav atslēga, kas mums gaidāms. 305 00:13:05,340 --> 00:13:10,720 Bet, ja mēs hit Tālāk, un tad mēs mēģināt un Print atslēgu, tas ir trīs. 306 00:13:10,720 --> 00:13:11,710 >> Ikvienam redzēt, ka? 307 00:13:11,710 --> 00:13:13,780 Tātad, ja jums kaut kas ka jūs, piemēram, jāgaida. 308 00:13:13,780 --> 00:13:15,540 Tas ir pilnīgi nepareizi, un es nezinu 309 00:13:15,540 --> 00:13:20,150 kā tas varētu notikt, jo viss, ko es gribu darīt, ir piešķirtu numuru, mainīgs, 310 00:13:20,150 --> 00:13:22,900 mēģināt hitting Tālāk, mēģiniet drukāt atkal, un redzēt, ja tas darbojas. 311 00:13:22,900 --> 00:13:27,830 Tāpēc, ka tas ir tikai gatavojas izpildīt un faktiski piešķirt kaut pēc tevis 312 00:13:27,830 --> 00:13:29,340 hit Next. 313 00:13:29,340 --> 00:13:30,336 Jēga visiem? 314 00:13:30,336 --> 00:13:30,836 Uh huh? 315 00:13:30,836 --> 00:13:33,220 >> SPEAKER 2: Kad jūs nejauši skaitļi, ko tas nozīmē? 316 00:13:33,220 --> 00:13:34,790 >> SPEAKER 1: Tas ir tikai izlases. 317 00:13:34,790 --> 00:13:35,710 Tas ir tikai atkritumu. 318 00:13:35,710 --> 00:13:38,320 Tas ir tikai kaut kas jūsu dators nejauši piešķirt. 319 00:13:38,320 --> 00:13:39,721 320 00:13:39,721 --> 00:13:40,220 Atdzist. 321 00:13:40,220 --> 00:13:45,760 Tātad, tagad mēs varam virzīties cauri, un tā Tagad mums ir šī teksta GetString. 322 00:13:45,760 --> 00:13:48,600 Tātad, ļaujiet man tikai iepazīstināt ko notiks, kad mēs hit Next šeit. 323 00:13:48,600 --> 00:13:51,320 Mūsu GDB veida pazūd, vai ne? 324 00:13:51,320 --> 00:13:55,720 Tas ir tāpēc, ka GetString tagad izpildes, vai ne? 325 00:13:55,720 --> 00:14:01,460 Tātad, kad mēs redzējām teksta vienāds GetString, atveriet parens un parens, 326 00:14:01,460 --> 00:14:04,380 un mēs hit Tālāk, kas ir faktiski izpildīts tagad. 327 00:14:04,380 --> 00:14:06,580 Tātad, tas ir gaida mums ieejas kaut ko. 328 00:14:06,580 --> 00:14:13,560 >> Tātad, mēs ejam, lai ievadītu mūsu pārtiku, kas ir tas, kas tas ir nedarot, kā es tev teicu 329 00:14:13,560 --> 00:14:18,020 un ka tikai saka, ka tā ir gatavo izpildes, ka slēgta 330 00:14:18,020 --> 00:14:19,980 kronšteins nozīmē, ka tas ir iziešanas no šīs cilpas. 331 00:14:19,980 --> 00:14:21,170 332 00:14:21,170 --> 00:14:25,420 Tātad, mēs varam hit Next, un tagad, kā es esmu pārliecināts, ka jūs visi esat pazīstami no Cēzara, 333 00:14:25,420 --> 00:14:27,260 tas ir, kāda ir šī pozīcija gatavojas to darīt. 334 00:14:27,260 --> 00:14:32,030 Tas ir par Int es vienāds ar 0, N ir vienāds Strlen, teksta, un pēc tam 335 00:14:32,030 --> 00:14:33,960 I ir mazāk nekā n, I, plus, plus. 336 00:14:33,960 --> 00:14:35,210 Kas tas ir cilpa gatavojas darīt? 337 00:14:35,210 --> 00:14:37,900 338 00:14:37,900 --> 00:14:39,160 Atveriet savu ziņu. 339 00:14:39,160 --> 00:14:39,770 Atdzist. 340 00:14:39,770 --> 00:14:41,330 Tātad, sāksim darīt. 341 00:14:41,330 --> 00:14:47,210 >> Tātad, ja šis nosacījums spēles, mūsu pirmo? 342 00:14:47,210 --> 00:14:52,250 Ja tas ir B, tas ir teksta I. Mums var iegūt informāciju par mūsu vietējiem. 343 00:14:52,250 --> 00:14:53,610 344 00:14:53,610 --> 00:14:57,970 Tātad, es ir nulle, un ja sešu, kas mēs sagaidām, un mūsu galvenais ir trīs. 345 00:14:57,970 --> 00:14:59,227 Viss, kas ir jēga, vai ne? 346 00:14:59,227 --> 00:15:01,310 Šie skaitļi ir visi tieši to, ko viņiem vajadzētu būt. 347 00:15:01,310 --> 00:15:02,590 348 00:15:02,590 --> 00:15:03,870 Tātad, smirdēt? 349 00:15:03,870 --> 00:15:05,620 SPEAKER 3: Man ir izlases numuri raktuvē. 350 00:15:05,620 --> 00:15:09,156 351 00:15:09,156 --> 00:15:12,030 SPEAKER 1: Nu, mēs varam check-- --we var tērzēt par to, ka sekundē. 352 00:15:12,030 --> 00:15:14,110 353 00:15:14,110 --> 00:15:15,750 Bet jums vajadzētu iegūt to. 354 00:15:15,750 --> 00:15:17,700 355 00:15:17,700 --> 00:15:20,130 Tātad, ja mums ir kapitāls B mūsu pirmā, 356 00:15:20,130 --> 00:15:22,080 šis nosacījums būtu noķert to, labi? 357 00:15:22,080 --> 00:15:27,120 Tātad, ja mēs hit Tālāk, mēs redzam ka šis Ja faktiski izpilda. 358 00:15:27,120 --> 00:15:29,220 Jo, ja jūs pēc gar savu kodu, 359 00:15:29,220 --> 00:15:33,460 šī līnija šeit, kur teksta es aizstāj ar šo aritmētikā, 360 00:15:33,460 --> 00:15:35,720 izpilda tikai tad, ja IF nosacījums ir pareizi vai ne? 361 00:15:35,720 --> 00:15:36,905 362 00:15:36,905 --> 00:15:40,240 >> GDB ir tikai gatavojas, lai parādītu jums lietas, kas ir faktiski izpildītāji. 363 00:15:40,240 --> 00:15:45,140 Tātad, ja šis Ja nosacījums nav izpildīts, tas ir tikai gatavojas, lai pārietu uz nākamo rindiņu. 364 00:15:45,140 --> 00:15:46,540 OK? 365 00:15:46,540 --> 00:15:48,510 Tātad, mums ir, ka. 366 00:15:48,510 --> 00:15:51,171 Tas kronšteins nozīmē, ka tas ir slēgts no šīs cilpas tagad. 367 00:15:51,171 --> 00:15:52,420 Tātad, tas notiek, lai sāktu no jauna. 368 00:15:52,420 --> 00:15:54,760 369 00:15:54,760 --> 00:15:56,280 Tieši tāpat. 370 00:15:56,280 --> 00:15:59,120 Tāpēc, ka mēs varam iegūt informāciju par mūsu vietējiem šeit 371 00:15:59,120 --> 00:16:02,575 un mēs redzam, ka mūsu pirmais vēstule ir mainījies, vai ne? 372 00:16:02,575 --> 00:16:05,150 Tas tagad ir E, kā tam vajadzētu būt. 373 00:16:05,150 --> 00:16:07,360 Tātad, mēs varam turpināt. 374 00:16:07,360 --> 00:16:08,500 >> Un mums ir šo pārbaudi. 375 00:16:08,500 --> 00:16:09,916 Un ja šajā pārbaudē vajadzētu strādāt, vai ne? 376 00:16:09,916 --> 00:16:12,570 Tas ir A. Būtu jāmaina trīs burti uz priekšu. 377 00:16:12,570 --> 00:16:14,320 378 00:16:14,320 --> 00:16:16,530 Bet, ja pamanāt, mēs dabūt kaut ko citu. 379 00:16:16,530 --> 00:16:17,580 380 00:16:17,580 --> 00:16:22,860 Tātad šajā gadījumā šeit, tas nozvejotas tas, un tāpēc šī pozīcija izpildīts, 381 00:16:22,860 --> 00:16:28,620 kas paredzēja mainīt mūsu B. Tomēr, šajā gadījumā šeit, 382 00:16:28,620 --> 00:16:32,860 mums ir, ka tas ir tikai izlaistas to, un devās uz [? L siff. ?] 383 00:16:32,860 --> 00:16:34,660 Tātad, kaut kas notiek tur. 384 00:16:34,660 --> 00:16:37,780 Ko tas stāsta jums ir tas, ka, mēs zinām, ka tas būtu nozvejas šeit 385 00:16:37,780 --> 00:16:39,200 bet tas nav. 386 00:16:39,200 --> 00:16:42,210 Vai kāds redzēt, ko mūsu Problēma ir šajā rindā? 387 00:16:42,210 --> 00:16:45,380 388 00:16:45,380 --> 00:16:46,969 Tas ir ļoti minūti lieta. 389 00:16:46,969 --> 00:16:48,510 Un jūs varētu arī apskatīt savu kodu. 390 00:16:48,510 --> 00:16:49,980 391 00:16:49,980 --> 00:16:54,940 Tas ir arī line-- aizmirst to, ko līnija tas ir jo there-- bet tas ir [nedzirdama]. 392 00:16:54,940 --> 00:16:55,480 Jā? 393 00:16:55,480 --> 00:16:58,639 >> SPEAKER 4: Tas ir par vairāk nekā lapa, ja jūs lasīt to grāmatu. 394 00:16:58,639 --> 00:16:59,430 SPEAKER 1: Tieši tā. 395 00:16:59,430 --> 00:17:02,620 Tātad, atkļūdotājs nevarēja pateikt Jums, ka, bet atkļūdotājs 396 00:17:02,620 --> 00:17:05,880 varētu saņemt jūs uz leju, lai līnijas ka jūs zināt, nedarbojas. 397 00:17:05,880 --> 00:17:09,319 Un dažreiz, kad īpaši vēlāk semestrī, kad 398 00:17:09,319 --> 00:17:12,910 jums ir darīšana ar simts, kas ir simts dažas rindiņas kodu, un jūs 399 00:17:12,910 --> 00:17:16,190 nezinu, kur tas nedarot, šis ir lielisks veids, kā to darīt. 400 00:17:16,190 --> 00:17:17,900 401 00:17:17,900 --> 00:17:18,989 Tātad, mēs noskaidrojām mūsu kļūdu. 402 00:17:18,989 --> 00:17:21,530 Jūs varat noteikt to savā failā, un tad jūs varētu palaist to no jauna, 403 00:17:21,530 --> 00:17:23,029 un viss darbosies perfekti. 404 00:17:23,029 --> 00:17:24,970 405 00:17:24,970 --> 00:17:30,590 Un lielākais lieta ir tas var šķist, OK. 406 00:17:30,590 --> 00:17:31,090 Yeah. 407 00:17:31,090 --> 00:17:31,370 Atdzist. 408 00:17:31,370 --> 00:17:32,744 Jūs zināja, ko jūs meklējat. 409 00:17:32,744 --> 00:17:34,910 Tātad, jūs zinātu, ko darīt. 410 00:17:34,910 --> 00:17:39,021 >> GDB var būt super noderīgi, jo jums var izdrukāt visas šīs lietas, kas jums 411 00:17:39,021 --> 00:17:39,520 nebūtu. 412 00:17:39,520 --> 00:17:41,160 Tas ir daudz noderīgāks nekā printf. 413 00:17:41,160 --> 00:17:43,440 Cik daudzi no jums izmantot piemēram printf paziņojumiem 414 00:17:43,440 --> 00:17:46,200 izdomāt, kur kļūda bija, vai ne? 415 00:17:46,200 --> 00:17:48,450 Tātad, ar šo, jums nav ir saglabāt atgriežās, 416 00:17:48,450 --> 00:17:51,139 un patīk komentējot Printf, vai komentējot, 417 00:17:51,139 --> 00:17:52,930 un izdomāt, ko Jums vajadzētu drukāšanas. 418 00:17:52,930 --> 00:17:55,670 Tas faktiski tikai ļauj jums soli pa, izdrukāt lietas 419 00:17:55,670 --> 00:18:00,000 kā jūs iet cauri, tāpēc, jūs varat vērot, kā tie mainās reālā laikā, 420 00:18:00,000 --> 00:18:02,190 kā jūsu programma darbojas. 421 00:18:02,190 --> 00:18:04,390 >> Un tas prasa nedaudz mazliet jāpierod. 422 00:18:04,390 --> 00:18:07,850 Es ļoti ieteiktu tikai veida būt mazliet neapmierinātas ar to 423 00:18:07,850 --> 00:18:08,930 tieši tagad. 424 00:18:08,930 --> 00:18:13,450 Ja jūs pavadīt stundas pa nākamnedēļ mācīties, kā izmantot GDB, 425 00:18:13,450 --> 00:18:16,140 jūs ietaupīsiet sev tik daudz laika vēlāk. 426 00:18:16,140 --> 00:18:18,750 Un burtiski. mēs pateikt šo cilvēku katru gadu, 427 00:18:18,750 --> 00:18:23,890 un es atceros, kad es paņēmu klasē, man bija, piemēram, man būs labi. 428 00:18:23,890 --> 00:18:24,700 Nē. 429 00:18:24,700 --> 00:18:27,030 PSET 6 nāca un man bija piemēram, es esmu gonna mācīties 430 00:18:27,030 --> 00:18:29,500 kā izmantot GDB, jo man nav zināt, kas notiek šeit. 431 00:18:29,500 --> 00:18:32,940 >> Tātad, ja jūs lietojat laiks, lai izmantot to par mazākām programmām 432 00:18:32,940 --> 00:18:35,697 ka jūs esat būs strādā, piemēram, strādājot 433 00:18:35,697 --> 00:18:37,530 ar kaut ko līdzīgu Visionare, kā šis. 434 00:18:37,530 --> 00:18:38,800 435 00:18:38,800 --> 00:18:42,850 Vai, ja vēlaties papildus praksi, es esmu pārliecināts, ka Es varētu nākt klajā ar buggy programmām, 436 00:18:42,850 --> 00:18:45,300 jums atkļūdot, ja vēlaties. 437 00:18:45,300 --> 00:18:49,300 >> Bet, ja jūs vienkārši aizņemt kādu laiku, lai saņemtu pieraduši pie tā, tikai spēlēt aptuveni ar to, 438 00:18:49,300 --> 00:18:50,550 tas tiešām kalpos jums labi. 439 00:18:50,550 --> 00:18:52,591 Un tas patiešām ir viens no tās lietas, ka jūs vienkārši 440 00:18:52,591 --> 00:18:57,340 ir izmēģināt, un saņemt rokas netīras ar, pirms jūs patiešām saprast. 441 00:18:57,340 --> 00:19:02,090 Es tiešām tikai saprot to vienu reizi Man bija atkļūdošanas lietas ar to, 442 00:19:02,090 --> 00:19:08,170 un tas ir daudz jaukāk ir ideja par kā atkļūdot ātrāk nekā vēlāk. 443 00:19:08,170 --> 00:19:08,850 OK. 444 00:19:08,850 --> 00:19:09,625 Atdzist. 445 00:19:09,625 --> 00:19:12,960 Es zinu, ka ir veids kā crash kurss GDB, 446 00:19:12,960 --> 00:19:16,400 un es noteikti strādās par iegūt tos meklēt lielāku nākamreiz. 447 00:19:16,400 --> 00:19:17,590 448 00:19:17,590 --> 00:19:18,280 Atdzist. 449 00:19:18,280 --> 00:19:20,390 >> Tātad, ja mēs ejam atpakaļ uz mūsu PowerPoint. 450 00:19:20,390 --> 00:19:27,194 451 00:19:27,194 --> 00:19:28,110 Tas notiek uz darbu? 452 00:19:28,110 --> 00:19:29,711 453 00:19:29,711 --> 00:19:30,210 AWH. 454 00:19:30,210 --> 00:19:31,101 Jā. 455 00:19:31,101 --> 00:19:31,600 OK. 456 00:19:31,600 --> 00:19:35,480 Tātad, ja jums kādreiz ir nepieciešams kāds no tie atkal, tur ir saraksts. 457 00:19:35,480 --> 00:19:37,160 458 00:19:37,160 --> 00:19:40,830 Tātad Binary Meklēt, kurā ikviens atceras lielo briļļu Dāvida 459 00:19:40,830 --> 00:19:42,259 lielisks tālruņu grāmatas uz pusēm. 460 00:19:42,259 --> 00:19:44,050 Man nav īsti iegūt telefonu grāmatas vairs, 461 00:19:44,050 --> 00:19:46,530 tāpēc, ka, piemēram, ja jūs saņem telefona grāmatas šajās dienās? 462 00:19:46,530 --> 00:19:48,220 Es tiešām nezinu. 463 00:19:48,220 --> 00:19:49,840 464 00:19:49,840 --> 00:19:50,590 Binary Meklēt. 465 00:19:50,590 --> 00:19:52,464 Vai kāds atceras Kā Binary meklēšanas darbus? 466 00:19:52,464 --> 00:19:54,380 467 00:19:54,380 --> 00:19:55,220 Ikviens vispār? 468 00:19:55,220 --> 00:19:56,325 Yeah? 469 00:19:56,325 --> 00:19:58,283 SPEAKER 5: Jūs zināt, kad paskatās kuriem puse 470 00:19:58,283 --> 00:20:01,146 tas būtu, pamatojoties uz to, un atbrīvoties no otra puse. 471 00:20:01,146 --> 00:20:01,896 >> SPEAKER 1 Tieši tā. 472 00:20:01,896 --> 00:20:06,290 Tātad, bināro meklēšanu, tas ir sava veida a-- --we patīk, lai izsauktu to sadalīt un iekarot. 473 00:20:06,290 --> 00:20:09,170 Tātad, ko jūs darīt, ir jūs meklēt pa vidu, 474 00:20:09,170 --> 00:20:11,990 un jūs redzēsiet, ja tas atbilst to, ko jūs meklējat. 475 00:20:11,990 --> 00:20:15,420 Un, ja tas tā nav, tad jūs mēģināt izdomāt, tas būs jāatstāj 476 00:20:15,420 --> 00:20:16,450 puse jeb labajā pusē. 477 00:20:16,450 --> 00:20:19,325 Tātad, tas varētu būt, ja jūs meklējat kaut ko, kas ir alphabetized, 478 00:20:19,325 --> 00:20:20,720 jūs redzat, oh. 479 00:20:20,720 --> 00:20:22,750 Vai Allison nonāk līdz M? 480 00:20:22,750 --> 00:20:23,250 Jā. 481 00:20:23,250 --> 00:20:25,030 Tātad, mēs ejam, lai apskatīt pirmajā pusē. 482 00:20:25,030 --> 00:20:26,450 >> Vai tas varētu būt, piemēram, ar skaitļiem. 483 00:20:26,450 --> 00:20:28,830 Jebkas, ka jūs varat salīdzināt, tas var būt sakārtoti. 484 00:20:28,830 --> 00:20:29,920 485 00:20:29,920 --> 00:20:31,260 Jūs varat izmantot bināro meklēšanu. 486 00:20:31,260 --> 00:20:32,340 487 00:20:32,340 --> 00:20:37,455 Tātad, kāds atceras šo Grafikā vai kas tas ir? 488 00:20:37,455 --> 00:20:39,520 Tas ir Asimptotiskā sarežģītība. 489 00:20:39,520 --> 00:20:42,830 Tātad, šis diagramma tikai aprakstīts, cik ilgi tas 490 00:20:42,830 --> 00:20:46,230 ņem jums, lai atrisinātu problēmu, kā jūs palielināt vairākas lietas 491 00:20:46,230 --> 00:20:47,090 ka jūs izmantojat. 492 00:20:47,090 --> 00:20:51,260 >> Tātad, mēs ir N, kas ir lineārs laiks. 493 00:20:51,260 --> 00:20:54,560 Ja N virs diviem, kas ir nedaudz labāk, tomēr aug super ātri. 494 00:20:54,560 --> 00:20:58,360 Un tad mēs esam saitā, kas ir tas, ko mēs uzskatām bināro meklēšanu. 495 00:20:58,360 --> 00:21:03,630 Ja mēs pamanām, kā jūsu problēma kļūst daudz un daudz lielāka, 496 00:21:03,630 --> 00:21:06,600 laiks, kas nepieciešams, lai jūs to atrisināt nav īsti palielināties, ka daudz. 497 00:21:06,600 --> 00:21:09,010 Tas ir tāpat kā salīdzināt šeit sākumā. 498 00:21:09,010 --> 00:21:10,060 Jūs, piemēram, OK. 499 00:21:10,060 --> 00:21:13,000 Jebkas šeit nav īsti jautājums, kuriem viens mēs izmantojam, 500 00:21:13,000 --> 00:21:16,220 bet jums, lai miljons, miljards. 501 00:21:16,220 --> 00:21:20,010 Jūs mēģināt atrast some-- --you're mēģinot atrast adatu siena kaudzē. 502 00:21:20,010 --> 00:21:21,550 >> Es domāju, ka jūs vēlaties šo problēmu. 503 00:21:21,550 --> 00:21:25,850 Vēlaties šo sarežģītību, nevis lineāra, jo visiem jums 504 00:21:25,850 --> 00:21:30,049 zināt jūsu gonna meklējot caur katrs indivīds adatu, lieta siena, 505 00:21:30,049 --> 00:21:31,340 mēģina meklēt savu adatu. 506 00:21:31,340 --> 00:21:34,730 Un tas nav pārāk jautri, manuprāt. 507 00:21:34,730 --> 00:21:35,500 Man patīk ātri. 508 00:21:35,500 --> 00:21:36,620 Man patīk efektīva. 509 00:21:36,620 --> 00:21:40,450 Un kā hardworking studentu pilsētās puiši ir, jūs zināt strādāt gudrāk, 510 00:21:40,450 --> 00:21:43,010 nav grūtāk tipa lieta, kā jūs var padarīt šos algoritmus. 511 00:21:43,010 --> 00:21:45,110 512 00:21:45,110 --> 00:21:47,910 >> Tātad, mēs ejam staigāt izmantojot tikai ātri piemērs. 513 00:21:47,910 --> 00:21:51,090 Es domāju, ka jūs guys ir jābūt roku uz bināro meklēšanu, 514 00:21:51,090 --> 00:21:54,352 bet ja kāds ir nedaudz izplūdušas, vēlamies stiprināt to, 515 00:21:54,352 --> 00:21:56,310 mēs ejam, lai tikai iet izmantojot piemēru šeit. 516 00:21:56,310 --> 00:21:59,490 Tātad, mēs meklējam, ja masīvs satur septiņus. 517 00:21:59,490 --> 00:22:00,540 518 00:22:00,540 --> 00:22:06,010 >> Tātad, pirmā lieta, ko mēs darām, ir izskatās pa vidu, vai ne? 519 00:22:06,010 --> 00:22:09,340 Un arī jūs esat būs kodēšanas Binārā Meklēt tikai sekundē. 520 00:22:09,340 --> 00:22:11,310 Tātad, tas būs jautri. 521 00:22:11,310 --> 00:22:13,710 Tātad mēs skatāmies vidū maz bloki 3. 522 00:22:13,710 --> 00:22:15,501 Vai 3 vienāds 7? 523 00:22:15,501 --> 00:22:16,000 Nav. 524 00:22:16,000 --> 00:22:18,670 525 00:22:18,670 --> 00:22:19,550 Tas ir sešas. 526 00:22:19,550 --> 00:22:21,480 Tātad, tas ir mazāk nekā vai lielāks par septiņiem? 527 00:22:21,480 --> 00:22:23,080 528 00:22:23,080 --> 00:22:23,960 Mazāk nekā. 529 00:22:23,960 --> 00:22:24,570 Jā. 530 00:22:24,570 --> 00:22:25,170 Nice darba puiši. 531 00:22:25,170 --> 00:22:25,569 532 00:22:25,569 --> 00:22:27,360 Man šķiet, es, piemēram, es būtu ir candy jo es 533 00:22:27,360 --> 00:22:29,460 vēlaties, lai mest to ārā pagalmos. 534 00:22:29,460 --> 00:22:30,270 Tas ir tas, ko es esmu gatavojas darīt nākamnedēļ. 535 00:22:30,270 --> 00:22:31,436 Tas saglabās jums puiši asas. 536 00:22:31,436 --> 00:22:32,560 537 00:22:32,560 --> 00:22:34,690 >> Tātad, mēs izmetam, ka pirmo pusi, vai ne? 538 00:22:34,690 --> 00:22:35,670 tas bija mazāk nekā. 539 00:22:35,670 --> 00:22:39,325 mēs zinām, ka viss šajā kreisajā pusē 540 00:22:39,325 --> 00:22:41,700 būs mazāks nekā tas, ko mēs patiesībā meklējam. 541 00:22:41,700 --> 00:22:43,491 Tātad, nav nepieciešams pievērst uzmanību. 542 00:22:43,491 --> 00:22:45,120 Vienkārši aizmirst par to. 543 00:22:45,120 --> 00:22:48,720 Tātad, tagad mēs skatāmies mūsu labajā pusē, un mēs skatāmies vidū tur, 544 00:22:48,720 --> 00:22:50,510 un tagad tas ir deviņi. 545 00:22:50,510 --> 00:22:55,510 Tātad, 9 is-- --Everyone? 546 00:22:55,510 --> 00:22:57,470 Lielāks nekā tas, ko mēs esam meklē, vai ne? 547 00:22:57,470 --> 00:22:59,860 Tātad, mēs ejam, lai mest prom, viss labi. 548 00:22:59,860 --> 00:23:00,970 549 00:23:00,970 --> 00:23:01,940 Tāpat. 550 00:23:01,940 --> 00:23:03,700 Tagad, visi mēs esam atstāti ar ir viens. 551 00:23:03,700 --> 00:23:07,760 Tātad mēs pārbaudām, tas ir viens, ko mēs meklējam? tas ir. 552 00:23:07,760 --> 00:23:08,970 Mēs noskaidrojām, ko mēs vēlējāmies. 553 00:23:08,970 --> 00:23:10,440 554 00:23:10,440 --> 00:23:11,690 Tāpēc mēs esam darījuši. 555 00:23:11,690 --> 00:23:12,550 Bilineāra Meklēt. 556 00:23:12,550 --> 00:23:15,740 >> Un, ja pamanāt, mēs bija septiņi ieejas tur. 557 00:23:15,740 --> 00:23:24,320 Tas tikai bija mums kā trīs reizes, bet, ja jūs darāt, piemēram, miljarda, 558 00:23:24,320 --> 00:23:28,190 jūs guys zināt, cik soļus tas būtu jāveic, ja mums bija četru miljardu lietas? 559 00:23:28,190 --> 00:23:29,940 560 00:23:29,940 --> 00:23:30,455 Jebkurš guesses? 561 00:23:30,455 --> 00:23:32,286 562 00:23:32,286 --> 00:23:33,960 Tas ir 32. 563 00:23:33,960 --> 00:23:37,110 32 soļi, lai atrastu kaut ko ar četru miljardu 564 00:23:37,110 --> 00:23:39,650 elements masīvs jo pilnvaru diviem. 565 00:23:39,650 --> 00:23:43,550 Tātad divi ir 32, ir līdz četriem miljardiem. 566 00:23:43,550 --> 00:23:50,430 >> Tātad, diezgan traks, kā jūs joprojām laikā piemēram, diezgan nelielu skaitu soļiem 567 00:23:50,430 --> 00:23:52,650 lai atrastu kaut ko četru miljardu elementi. 568 00:23:52,650 --> 00:23:55,730 Tātad uz šo piezīmi, mēs esam gatavojas kodu šo 569 00:23:55,730 --> 00:23:58,950 Tātad jūs puiši faktiski var veida redzēt, kā tas darbojas. 570 00:23:58,950 --> 00:24:01,520 Labi, lai jūs guys var kodu. 571 00:24:01,520 --> 00:24:04,100 Es esmu gatavojas let you guys runāt mazliet. 572 00:24:04,100 --> 00:24:07,970 Iepazīt cilvēkus ap jums, kas ir ko kāds vēlējās no pēdējā sadaļā. 573 00:24:07,970 --> 00:24:10,280 >> Tātad iepazīt cilvēkus ap jums. 574 00:24:10,280 --> 00:24:11,305 Runāt mazliet. 575 00:24:11,305 --> 00:24:12,580 576 00:24:12,580 --> 00:24:15,730 Un viss, ko es gribu no jums puiši tagad ir tikai 577 00:24:15,730 --> 00:24:17,575 mēģināt izveidot izklāstu pseudocode. 578 00:24:17,575 --> 00:24:18,075 OK? 579 00:24:18,075 --> 00:24:20,825 580 00:24:20,825 --> 00:24:21,325 Paga. 581 00:24:21,325 --> 00:24:23,320 582 00:24:23,320 --> 00:24:29,520 Viss, ko es gribu no jums puiši ir jūs tikai gatavojas aizpildīt to, kamēr gadījumā. 583 00:24:29,520 --> 00:24:32,170 Tāpēc man ir izveidojušas šos augšējā un apakšējā robeža, kas 584 00:24:32,170 --> 00:24:35,250 pārstāv sākumu un beigas mūsu masīvs. 585 00:24:35,250 --> 00:24:40,440 Un jūs gatavojas, lai faktiski cilpas cauri un izdomāt 586 00:24:40,440 --> 00:24:42,470 tas, ko mēs darām šajā kamēr cilpa. 587 00:24:42,470 --> 00:24:45,810 >> Tātad, ja jūs varat izdomāt out-- man ir mājienu there-- kādi ir gadījumi 588 00:24:45,810 --> 00:24:46,640 ka mēs esam šeit? 589 00:24:46,640 --> 00:24:48,100 590 00:24:48,100 --> 00:24:51,560 Tātad, ja jūs vēlaties, lai noskaidrotu lietas, mēs pseudocode tiem 591 00:24:51,560 --> 00:24:53,350 un tad mēs patiesībā kodu tiem. 592 00:24:53,350 --> 00:24:55,330 Un tas būs, es domāju, cerams, tas būs 593 00:24:55,330 --> 00:24:56,788 būt mazliet vieglāk, nekā jūs sagaida. 594 00:24:56,788 --> 00:24:57,554 595 00:24:57,554 --> 00:25:00,220 Tāpēc, ka tas nav tik daudz kodu, patiesībā, kas ir tiešām foršs. 596 00:25:00,220 --> 00:25:34,110 597 00:25:34,110 --> 00:25:35,018 >> Mm-hm? 598 00:25:35,018 --> 00:25:35,893 >> STUDENTU: [dzirdams]? 599 00:25:35,893 --> 00:25:36,984 600 00:25:36,984 --> 00:25:37,650 Instruktors: Jā. 601 00:25:37,650 --> 00:25:38,595 Tur bija kaut kas atrast vidū. 602 00:25:38,595 --> 00:25:39,552 >> STUDENTU: Tātad, mēs varam izmantot to. 603 00:25:39,552 --> 00:25:39,770 OK. 604 00:25:39,770 --> 00:25:40,603 >> Instruktors: Perfect. 605 00:25:40,603 --> 00:25:42,950 Tā ka ir pirmā lieta, kas mums jādara. 606 00:25:42,950 --> 00:25:44,330 Tāpēc atrast vidū. 607 00:25:44,330 --> 00:25:45,415 608 00:25:45,415 --> 00:25:45,915 Lieliski. 609 00:25:45,915 --> 00:25:47,770 610 00:25:47,770 --> 00:25:55,010 Tātad jums ir ideja par to, kā mēs varētu faktiski atrast vidū ar kodu? 611 00:25:55,010 --> 00:25:55,980 >> STUDENTU: Jā. 612 00:25:55,980 --> 00:25:57,000 n vairāk nekā 2? 613 00:25:57,000 --> 00:25:58,500 614 00:25:58,500 --> 00:25:59,500 Instruktors: Tātad n vairāk nekā 2. 615 00:25:59,500 --> 00:26:05,170 Tik viena lieta atcerēties ir tas, ka jūsu augšējā un apakšējā robeža mainīt. 616 00:26:05,170 --> 00:26:08,110 Mēs turpinām constricting daļu masīva mēs meklējam. 617 00:26:08,110 --> 00:26:11,970 Tātad n vairāk nekā 2 darbosies tikai pirmā lieta, ko mēs darām. 618 00:26:11,970 --> 00:26:17,810 Tātad, ņemot vērā augšējo un apakšējo, kā varētu mēs šo vidējo elementu? 619 00:26:17,810 --> 00:26:20,640 Jo mēs gribam vidū starp augšējo un apakšējo, labi? 620 00:26:20,640 --> 00:26:21,730 621 00:26:21,730 --> 00:26:22,494 Mm-hm? 622 00:26:22,494 --> 00:26:23,369 >> STUDENTU: [dzirdams]. 623 00:26:23,369 --> 00:26:26,170 624 00:26:26,170 --> 00:26:28,080 >> Instruktors: Tātad mums ir dažas vidū. 625 00:26:28,080 --> 00:26:32,730 Un tas būs augšējais plus zemāka nekā 2. 626 00:26:32,730 --> 00:26:34,740 627 00:26:34,740 --> 00:26:35,690 Awesome. 628 00:26:35,690 --> 00:26:36,570 Tur mēs ejam. 629 00:26:36,570 --> 00:26:37,280 Viena rinda uz leju. 630 00:26:37,280 --> 00:26:38,560 Jūs guys ir pa ceļam. 631 00:26:38,560 --> 00:26:41,400 Tāpēc tagad, ka mums ir mūsu vidū, ko mēs vēlamies darīt? 632 00:26:41,400 --> 00:26:45,050 633 00:26:45,050 --> 00:26:45,900 Tikai kopumā. 634 00:26:45,900 --> 00:26:47,734 Jums nav kodu to. 635 00:26:47,734 --> 00:26:48,335 Jā. 636 00:26:48,335 --> 00:26:49,210 STUDENTU: [dzirdams]? 637 00:26:49,210 --> 00:27:00,310 638 00:27:00,310 --> 00:27:10,310 Instruktors: Tātad, tas ir arī tāpēc, ka tu esi atrast vidējo starp diviem 639 00:27:10,310 --> 00:27:10,810 no tiem. 640 00:27:10,810 --> 00:27:11,890 641 00:27:11,890 --> 00:27:17,370 Tātad, ja jūs domājat par to kā sava veida un pieaug no sāniem, 642 00:27:17,370 --> 00:27:21,640 domā par to, kā jūs pieeja vidū, jūs vēlaties, piemēram, ka. 643 00:27:21,640 --> 00:27:27,150 Tātad, ja tu būtu abās pusēs vidū, un mums ir, piemēram, 5 un 7. 644 00:27:27,150 --> 00:27:31,440 Kad jūs pievienot tos kopā, jums get 12, jūs sadalīt pa 2, ir 6. 645 00:27:31,440 --> 00:27:33,726 >> Dažreiz tas ir grūti izskaidrot, kāpēc tas darbojas, 646 00:27:33,726 --> 00:27:35,600 bet, ja jūs strādājat ar piemērs reizēm, 647 00:27:35,600 --> 00:27:37,962 tas tev palīdzēs jums saprast, ja tas būtu plus vai mīnus. 648 00:27:37,962 --> 00:27:38,846 Jā. 649 00:27:38,846 --> 00:27:40,830 >> STUDENTU: [dzirdams] tieši vidū 650 00:27:40,830 --> 00:27:43,950 ja tie bija gadījums, kad tur ir daudz mazāku skaitu 651 00:27:43,950 --> 00:27:45,860 un kā viena liela skaita? 652 00:27:45,860 --> 00:27:49,750 >> Instruktors: Tātad viss, kas jums nepieciešams ir vidū masīva. 653 00:27:49,750 --> 00:27:53,010 Tātad, ja jums bija ķekars nelielā skaitā un tad īsti liels skaits 654 00:27:53,010 --> 00:27:54,799 beigās, tas nav svarīgi. 655 00:27:54,799 --> 00:27:56,840 Viss, ka jautājumus ir, ka viņi šķiro, jūs vienkārši 656 00:27:56,840 --> 00:27:59,339 vēlaties apskatīt vidū masīvs, jo tu esi vēl 657 00:27:59,339 --> 00:28:00,700 sagriešana savu problēmu pusi. 658 00:28:00,700 --> 00:28:03,020 659 00:28:03,020 --> 00:28:03,680 Atdzist. 660 00:28:03,680 --> 00:28:06,430 Tāpēc tagad, ka mēs esam vidū, ko mēs darīt tālāk? 661 00:28:06,430 --> 00:28:07,150 >> STUDENTU: Salīdzināt. 662 00:28:07,150 --> 00:28:08,150 Instruktors: salīdzināt. 663 00:28:08,150 --> 00:28:11,670 Tāpēc salīdzināt vidū uz value_wanted. 664 00:28:11,670 --> 00:28:14,300 665 00:28:14,300 --> 00:28:15,160 Atdzist. 666 00:28:15,160 --> 00:28:17,950 Tātad jūs redzat, šeit mums ir šī vērtība mēs vēlamies šeit. 667 00:28:17,950 --> 00:28:22,012 668 00:28:22,012 --> 00:28:23,095 Atcerieties, tas ir masīvs. 669 00:28:23,095 --> 00:28:24,100 670 00:28:24,100 --> 00:28:26,970 Tā vidus attiecas uz indeksu. 671 00:28:26,970 --> 00:28:29,785 Tāpēc mēs vēlamies darīt vērtības vidū. 672 00:28:29,785 --> 00:28:32,380 673 00:28:32,380 --> 00:28:35,650 Neaizmirstiet, ja vēlaties salīdzināt, dubultā vienāds. 674 00:28:35,650 --> 00:28:38,250 Jums viena vienāds esat tikai gatavojas pārdalīt to, 675 00:28:38,250 --> 00:28:41,090 un tad, protams, tas ir būs vērtību, ko vēlaties. 676 00:28:41,090 --> 00:28:42,300 Tāpēc nav darīt. 677 00:28:42,300 --> 00:28:44,350 >> Tātad mēs ejam, lai redzētu, vai vērtības, kas pa vidu 678 00:28:44,350 --> 00:28:46,460 ir vienāds ar vērtību, mēs vēlas. 679 00:28:46,460 --> 00:28:47,749 680 00:28:47,749 --> 00:28:48,790 Neaizmirstiet lencēm. 681 00:28:48,790 --> 00:28:50,520 682 00:28:50,520 --> 00:28:52,235 Dropbox vajadzētu iet prom. 683 00:28:52,235 --> 00:28:54,140 684 00:28:54,140 --> 00:28:56,200 Tātad, ko mēs darām šajā gadījumā? 685 00:28:56,200 --> 00:28:59,360 Ja tas ir tas, ko mēs vēlamies, lai atgrieztos? 686 00:28:59,360 --> 00:29:01,510 687 00:29:01,510 --> 00:29:02,626 Mēs cenšamies pateikt. 688 00:29:02,626 --> 00:29:03,440 >> STUDENTU: Print off. 689 00:29:03,440 --> 00:29:05,314 >> Instruktors: Nu, mēs negribu izdrukāt. 690 00:29:05,314 --> 00:29:08,220 Tātad tas ir bool šeit, tāpēc mēs vēlas atgriezties patiess vai nepatiess. 691 00:29:08,220 --> 00:29:12,280 Mēs sakot, tas ir skaitlis [? RRA? ?] Tātad, ja tas ir, 692 00:29:12,280 --> 00:29:13,788 mēs vienkārši atgriezties tā ir taisnība. 693 00:29:13,788 --> 00:29:16,780 694 00:29:16,780 --> 00:29:17,760 Ja es varētu izskaidrot taisnība. 695 00:29:17,760 --> 00:29:18,830 696 00:29:18,830 --> 00:29:20,805 >> STUDENTU: Kāpēc nebūtu jūs atgriezties nulle? 697 00:29:20,805 --> 00:29:22,930 Instruktors: Tātad jūs varētu atgriešanās nulle, ja jūs vēlējāties. 698 00:29:22,930 --> 00:29:26,780 Bet šajā gadījumā, jo Mūsu funkcija atgriež bool, 699 00:29:26,780 --> 00:29:28,962 mums ir nepieciešams, lai atgrieztos vai nu patiess vai nepatiess. 700 00:29:28,962 --> 00:29:30,920 STUDENTU: Kad esat sakot Būla izteiksme, 701 00:29:30,920 --> 00:29:33,450 Jūs varat iestatīt tā, kas vienāds ar viltus? 702 00:29:33,450 --> 00:29:39,860 Piemēram, ja es gribu teikt, ja šis nosacījums nav izpildīts, piemēram, ir augšējā vienāds nepatiesa. 703 00:29:39,860 --> 00:29:42,332 Vai tas saprast, ja jūs vienkārši likt false, no otras puses? 704 00:29:42,332 --> 00:29:43,040 Instruktors: Jā. 705 00:29:43,040 --> 00:29:44,820 Tik tiešām, ja jūs esat kādreiz kaut ko dara 706 00:29:44,820 --> 00:29:49,600 tāpat ir augšējā vai apakšējā, kas atgriež patiess vai nepatiess 707 00:29:49,600 --> 00:29:53,850 un tas ir faktiski slikti stils teiksim vienāds vienāds patiess vai vienāds 708 00:29:53,850 --> 00:29:54,840 vienāds nepatiesa. 709 00:29:54,840 --> 00:30:00,210 Jūs vēlaties izmantot šo rezultātu kā pati kā jūsu čeku. 710 00:30:00,210 --> 00:30:04,720 711 00:30:04,720 --> 00:30:05,860 Nav tas, ko es gribēju. 712 00:30:05,860 --> 00:30:08,150 713 00:30:08,150 --> 00:30:09,240 Tas ir tas, ko es gribēju. 714 00:30:09,240 --> 00:30:13,205 Tātad, ja jūs esat jautā par kaut ko, piemēram, saglabāt to C. 715 00:30:13,205 --> 00:30:16,320 716 00:30:16,320 --> 00:30:25,150 >> Tātad, ja mums ir int galvenais (spēkā neesošs) un kaut kas līdzīgs šim. 717 00:30:25,150 --> 00:30:31,922 Un jums ir, ja ir augšējā par kādu ievades un jūs 718 00:30:31,922 --> 00:30:33,630 jautā, ja jūs varat darīt kaut kas līdzīgs šim? 719 00:30:33,630 --> 00:30:35,010 720 00:30:35,010 --> 00:30:35,679 Taisnība? 721 00:30:35,679 --> 00:30:37,470 STUDENTU: Es centos to darīt [nedzirdama]. 722 00:30:37,470 --> 00:30:38,450 Jo, ja it's-- 723 00:30:38,450 --> 00:30:39,200 Instruktors: Labais. 724 00:30:39,200 --> 00:30:41,197 Tātad jūs vēlaties, ka tas ir viltus, vai ne? 725 00:30:41,197 --> 00:30:41,780 STUDENTU: Jā. 726 00:30:41,780 --> 00:30:45,960 Instruktors: Tātad šajā gadījumā jums vēlas to izpildīt, ja tā nav taisnība. 727 00:30:45,960 --> 00:30:50,510 Tik cool lieta, ko jūs darīt, ir šī. 728 00:30:50,510 --> 00:30:52,900 729 00:30:52,900 --> 00:30:55,650 Līdz ar to atcerēties izsaukuma punkts noliedz lietas? 730 00:30:55,650 --> 00:30:58,270 Tajā teikts [dzirdams] nozīmē ne. 731 00:30:58,270 --> 00:31:03,590 Tātad, ja mēs skatāmies tikai šī daļa šeit, jūs 732 00:31:03,590 --> 00:31:05,740 saka, ka novērtē to viltus kā jūs to vēlaties. 733 00:31:05,740 --> 00:31:06,790 734 00:31:06,790 --> 00:31:09,880 Nav nepatiesa ir taisnība, kas nozīmē, ka šis varētu izpildīt. 735 00:31:09,880 --> 00:31:11,037 Vai tas ir jēga? 736 00:31:11,037 --> 00:31:11,620 STUDENTU: Jā. 737 00:31:11,620 --> 00:31:12,453 Instruktors: satriecošs. 738 00:31:12,453 --> 00:31:13,800 739 00:31:13,800 --> 00:31:14,300 OK. 740 00:31:14,300 --> 00:31:16,330 Lai mēs varētu vienkārši atgriezties taisnība šajā gadījumā. 741 00:31:16,330 --> 00:31:20,357 Tāpēc tagad mums ir divi citi gadījumi šajā lietā. 742 00:31:20,357 --> 00:31:21,565 Kādas ir mūsu divas citas lietas? 743 00:31:21,565 --> 00:31:31,610 744 00:31:31,610 --> 00:31:32,900 Pieņemsim tikai darīt to šādā veidā. 745 00:31:32,900 --> 00:31:40,660 Tāpēc sāksim ar cits ja vērtības pie vidu 746 00:31:40,660 --> 00:31:43,230 ir mazāka nekā vērtība, kas mēs vēlas. 747 00:31:43,230 --> 00:31:47,200 748 00:31:47,200 --> 00:31:52,020 Tātad, mūsu vērtība vidū ir mazāks nekā vērtība, ka mēs meklējam. 749 00:31:52,020 --> 00:31:53,765 750 00:31:53,765 --> 00:31:56,720 >> Tātad, kas saistās do you domāju, ka mēs vēlamies atjaunināt? 751 00:31:56,720 --> 00:31:57,870 752 00:31:57,870 --> 00:31:58,780 Augšējā vai apakšējā? 753 00:31:58,780 --> 00:32:01,440 754 00:32:01,440 --> 00:32:01,940 Upper? 755 00:32:01,940 --> 00:32:03,230 756 00:32:03,230 --> 00:32:06,470 Tā, kurā pusē no masīva mēs gribam būt apskatot? 757 00:32:06,470 --> 00:32:07,500 >> STUDENTU: zemāka. 758 00:32:07,500 --> 00:32:09,750 >> Instruktors: Mēs mēs ejam kas meklē kreisi. 759 00:32:09,750 --> 00:32:11,120 Tātad, kas cits, ja mazliet vērtība ir mazāka. 760 00:32:11,120 --> 00:32:14,730 Tik jūsu vidū vērtību šeit ir mazāks nekā tas, ko mēs gribam. 761 00:32:14,730 --> 00:32:17,202 Tāpēc mēs vēlamies, lai labajā pusē mūsu masīvs. 762 00:32:17,202 --> 00:32:18,910 Tātad mēs ejam atjaunināt mūsu apakšējo robežu. 763 00:32:18,910 --> 00:32:20,210 764 00:32:20,210 --> 00:32:23,020 Tāpēc mēs atkārtoti piešķirt mūsu zemāka. 765 00:32:23,020 --> 00:32:25,221 Un ko jūs domājat, ka zemāka vajadzētu būt? 766 00:32:25,221 --> 00:32:26,304 STUDENTU: vidējā vērtība? 767 00:32:26,304 --> 00:32:27,446 768 00:32:27,446 --> 00:32:28,820 Instruktors: Tātad vidējā value-- 769 00:32:28,820 --> 00:32:30,136 STUDENTU: Plus 1. 770 00:32:30,136 --> 00:32:31,010 Instruktors: --plus 1. 771 00:32:31,010 --> 00:32:32,300 772 00:32:32,300 --> 00:32:34,380 Var kāds man pateikt, kāpēc mums ir, ka plus 1? 773 00:32:34,380 --> 00:32:35,730 >> STUDENTU: [? Nav vērtības?] ir vairāk vienāds ar to. 774 00:32:35,730 --> 00:32:36,120 >> Instruktors: Labais. 775 00:32:36,120 --> 00:32:38,661 Jo mēs jau zinām, ka Mūsu vidējā vērtība nav vienāds ar 776 00:32:38,661 --> 00:32:42,750 tas, un mēs vēlamies izslēgt no visiem turpmākajiem meklējumiem. 777 00:32:42,750 --> 00:32:46,360 Ja esat aizmirsis, ka plus 1, šis patiks cilpa bezgalīgi. 778 00:32:46,360 --> 00:32:49,620 Un jūs vienkārši nozvejotas bezgalīga cilpa, un tad jūs segfault 779 00:32:49,620 --> 00:32:50,370 un lietas iet slikti. 780 00:32:50,370 --> 00:32:54,780 Tāpēc vienmēr pārliecinieties, ka jūs neesat tostarp vērtību, ka jūs vienkārši 781 00:32:54,780 --> 00:32:55,380 paskatījās. 782 00:32:55,380 --> 00:32:58,530 Tāpēc mēs rūpējamies, ka ar plus 1. 783 00:32:58,530 --> 00:33:04,840 >> Tāpēc tagad mums ir mūsu pēdējā stāvokli ko es vienmēr par drošības labad 784 00:33:04,840 --> 00:33:12,664 Jūs varat pārbaudīt šeit, cits, ja vērtība vidū ir lielāka nekā vērtība, 785 00:33:12,664 --> 00:33:13,163 mēs gribam. 786 00:33:13,163 --> 00:33:16,260 787 00:33:16,260 --> 00:33:20,230 Tas nozīmē, ka mēs gribam kreisajā pusē. 788 00:33:20,230 --> 00:33:21,350 789 00:33:21,350 --> 00:33:23,260 Tātad kuriem viens mēs gatavojas atjaunināt? 790 00:33:23,260 --> 00:33:23,760 Upper. 791 00:33:23,760 --> 00:33:25,470 792 00:33:25,470 --> 00:33:26,970 Un kas ir tas viens būs vienāds? 793 00:33:26,970 --> 00:33:31,630 794 00:33:31,630 --> 00:33:33,690 Tuvo mīnus 1, jo, Protams, mēs vēlamies 795 00:33:33,690 --> 00:33:38,370 lai pārliecinātos, ka mēs neesam Aplūkojot šo vērtību vidū vēlreiz. 796 00:33:38,370 --> 00:33:41,830 797 00:33:41,830 --> 00:33:45,110 Un tad mums ir tā. 798 00:33:45,110 --> 00:33:45,610 Viss. 799 00:33:45,610 --> 00:33:46,820 Tas ir viss, binārā meklēšana ir. 800 00:33:46,820 --> 00:33:48,190 Tas nav tik slikti, vai ne? 801 00:33:48,190 --> 00:33:51,590 Tas ir tāpat kā 10 rindiņas kodu ar atstarpēm. 802 00:33:51,590 --> 00:33:57,510 Tik ļoti spēcīgs, ļoti noderīga, jums būs to lietot vienā no jūsu vēlāk psets. 803 00:33:57,510 --> 00:33:59,360 Varbūt ne tas viens, bet vēlāk. 804 00:33:59,360 --> 00:34:00,670 Tāpēc apgūt. 805 00:34:00,670 --> 00:34:01,510 Love it. 806 00:34:01,510 --> 00:34:02,980 Tas būs pret jums labi. 807 00:34:02,980 --> 00:34:05,370 Tātad, vai kāds ir jebkurš jautājumi par bināro meklēšanu? 808 00:34:05,370 --> 00:34:06,196 Jā. 809 00:34:06,196 --> 00:34:09,840 >> STUDENTU: Vai tas ir svarīgi vai jūsu n ir pāra vai nepāra? 810 00:34:09,840 --> 00:34:10,750 >> Instruktors: Nē. 811 00:34:10,750 --> 00:34:18,150 Jo mēs meta to uz vidu, kā int, tas būs tikai saīsināt to. 812 00:34:18,150 --> 00:34:21,600 Tātad, tas paliks vesels skaitlis, un tas būs beidzot kārtot caur visu. 813 00:34:21,600 --> 00:34:23,909 Tātad jums nav jāuztraucas par to. 814 00:34:23,909 --> 00:34:24,580 Ikvienam labs? 815 00:34:24,580 --> 00:34:25,659 816 00:34:25,659 --> 00:34:26,850 Awesome. 817 00:34:26,850 --> 00:34:27,919 Atdzist. 818 00:34:27,919 --> 00:34:30,836 Tātad, jūs puiši dabūja to. 819 00:34:30,836 --> 00:34:33,380 820 00:34:33,380 --> 00:34:33,880 Slaidrādi. 821 00:34:33,880 --> 00:34:35,719 822 00:34:35,719 --> 00:34:43,270 Tā kā mēs runājām par to, es zinu David minēja sarežģītības runtimes. 823 00:34:43,270 --> 00:34:44,420 824 00:34:44,420 --> 00:34:50,340 >> Tātad labākajā gadījumā, tas ir tikai viens, ko mēs saucam par pastāvīgu laiku. 825 00:34:50,340 --> 00:34:51,909 Vai kāds man pateikt, kāpēc tas varētu būt? 826 00:34:51,909 --> 00:34:52,969 827 00:34:52,969 --> 00:34:55,800 Kāda veida scenārija tas var radīt? 828 00:34:55,800 --> 00:34:58,260 829 00:34:58,260 --> 00:34:58,760 Mm-hm. 830 00:34:58,760 --> 00:34:59,926 >> STUDENTU: [dzirdams] first-- 831 00:34:59,926 --> 00:35:00,789 832 00:35:00,789 --> 00:35:03,830 Instruktors: Tātad vidū ir Pirmais elements, ka mēs nonākam pie, vai ne? 833 00:35:03,830 --> 00:35:08,167 Tātad, vai nu masīvs no vienas vai ko mēs meklējam tikai 834 00:35:08,167 --> 00:35:09,750 notiek, ir nokrāsa plakanzivs vidū. 835 00:35:09,750 --> 00:35:11,190 836 00:35:11,190 --> 00:35:13,380 Tātad tas ir mūsu labākais gadījums. 837 00:35:13,380 --> 00:35:17,540 Nokļūsiet reālām problēmām, iespējams, nav gatavojas sasniegt [dzirdams], ka bieži. 838 00:35:17,540 --> 00:35:18,667 839 00:35:18,667 --> 00:35:19,750 Kas par mūsu sliktākajā gadījumā? 840 00:35:19,750 --> 00:35:21,270 Mūsu sliktākajā gadījumā ir log n. 841 00:35:21,270 --> 00:35:25,360 Un tas ir jādara ar visu pilnvaras divu lieta, ka es runāju par. 842 00:35:25,360 --> 00:35:30,930 >> Tātad sliktākajā gadījumā tas nozīmētu ka mums bija karbonāde masīvs leju 843 00:35:30,930 --> 00:35:33,270 līdz brīdim, kad tas bija viens elements. 844 00:35:33,270 --> 00:35:34,810 845 00:35:34,810 --> 00:35:38,930 Tāpēc mums bija karbonāde to uz leju pusi tik reižu, cik mēs, iespējams, varētu. 846 00:35:38,930 --> 00:35:41,430 Tieši tāpēc tas ir žurnāls, jo n jūs vienkārši glabāt dalot ar divi. 847 00:35:41,430 --> 00:35:42,890 848 00:35:42,890 --> 00:35:45,830 Tātad pieņēmumus, lietas, kas jums vajag zināt, ja jūs esat kādreiz 849 00:35:45,830 --> 00:35:48,050 gatavojas izmantot bināro meklēšanu. 850 00:35:48,050 --> 00:35:50,680 Jūsu elementi ir sakārtoti. 851 00:35:50,680 --> 00:35:53,890 Tie ir sakārtoti, jo tas ir vienīgais veids, kā jūs 852 00:35:53,890 --> 00:35:57,060 var zināt, ja jums ir iespēja izsviest pusi no tā. 853 00:35:57,060 --> 00:36:00,260 >> Ja jums bija šis jumbled maisā skaitļu un jūs sakāt, 854 00:36:00,260 --> 00:36:05,380 Labi, es esmu gatavojas, lai pārbaudītu vidū skaits un es meklēju 855 00:36:05,380 --> 00:36:08,510 ir mazāks par to, ka es esmu tikai gatavojas patvaļīgi izsviest pusi. 856 00:36:08,510 --> 00:36:11,130 Jūs nezināt, ja Jūsu numurus šajā otrajā pusē. 857 00:36:11,130 --> 00:36:12,655 Tavs saraksts ir sakārtots. 858 00:36:12,655 --> 00:36:14,030 859 00:36:14,030 --> 00:36:16,560 Kā arī, tas var būt iet uz priekšu mazliet, 860 00:36:16,560 --> 00:36:18,360 bet jums ir brīva piekļuve. 861 00:36:18,360 --> 00:36:21,940 Jums ir nepieciešams, lai varētu vienkārši doties uz šo elementu vidū. 862 00:36:21,940 --> 00:36:25,110 Ja jums ir, lai šķērsotu ar kaut ko 863 00:36:25,110 --> 00:36:28,630 vai tas aizņem jums papildu pasākumus nokļūt, ka vidējā elementa, 864 00:36:28,630 --> 00:36:31,750 tas nav log n vairs, jo jūs pievienojat vairāk darba tajā. 865 00:36:31,750 --> 00:36:34,800 Un tas liks nedaudz vairāk jēgas divām nedēļām, 866 00:36:34,800 --> 00:36:37,950 bet es tikko veida gribēju iesākt, sniegt jums guys priekšstatu par to, kas ir 867 00:36:37,950 --> 00:36:38,999 nākt. 868 00:36:38,999 --> 00:36:40,790 Bet tie ir divi svarīgi pieņēmumi 869 00:36:40,790 --> 00:36:44,804 kas jums ir nepieciešams, lai bināro sarakstā. 870 00:36:44,804 --> 00:36:45,720 Pārliecinieties, ka tas ir sakārtots. 871 00:36:45,720 --> 00:36:47,920 Tas ir liels vienu jūs guys tiesības tagad. 872 00:36:47,920 --> 00:36:52,170 Un par to mēs varam iedziļināties pārējās mūsu veidu. 873 00:36:52,170 --> 00:36:56,444 Tātad četri sorts-- burbulis, ievietošanas, atlase, un apvienot. 874 00:36:56,444 --> 00:36:57,485 Viņi visa veida atdzist. 875 00:36:57,485 --> 00:37:02,860 Ja jūs puiši nolemj ņemt CS 124, jūs uzzināt par visu veidu veidu. 876 00:37:02,860 --> 00:37:07,575 Un, ja jūs esat xkcd ventilatoru, tur ir tiešām foršs komikss par 877 00:37:07,575 --> 00:37:11,530 tāpat īsti neefektīvu veidu, ko es ļoti iesakām jums skatīsies. 878 00:37:11,530 --> 00:37:16,170 Viens no tiem ir kā panikas veida, kas ir tāpat kā, ak nē, atgriezties izlases masīvs. 879 00:37:16,170 --> 00:37:16,991 Shutdown sistēma. 880 00:37:16,991 --> 00:37:17,490 Atstāt. 881 00:37:17,490 --> 00:37:19,070 882 00:37:19,070 --> 00:37:21,500 Tātad geeky humors vienmēr ir laba. 883 00:37:21,500 --> 00:37:22,620 884 00:37:22,620 --> 00:37:25,750 >> Tātad vai kāds atceras veida veida kā tikai vispārēju priekšstatu 885 00:37:25,750 --> 00:37:27,810 par to, kā burbulis veida darbi. 886 00:37:27,810 --> 00:37:31,130 887 00:37:31,130 --> 00:37:32,155 Jūs atceraties? 888 00:37:32,155 --> 00:37:32,755 >> STUDENTU: Jā. 889 00:37:32,755 --> 00:37:33,970 >> Instruktors: Iet par to. 890 00:37:33,970 --> 00:37:38,980 >> STUDENTU: Tātad jūs iet cauri, un ja tas ir lielāks, tad jūs mijmaiņas divas. 891 00:37:38,980 --> 00:37:39,820 >> Instruktors: Mm-hm. 892 00:37:39,820 --> 00:37:40,564 Tieši tā. 893 00:37:40,564 --> 00:37:41,730 Tātad jūs vienkārši atkārtot, izmantojot. 894 00:37:41,730 --> 00:37:43,050 Jūs pārbaudīt divus numurus. 895 00:37:43,050 --> 00:37:46,510 Ja kāds pirms ir lielāks nekā pēc tam vienu, 896 00:37:46,510 --> 00:37:50,230 jūs vienkārši mijmaiņas tos tā, ka Šādā veidā viss no augstāku numuru 897 00:37:50,230 --> 00:37:54,990 burbulis up beigās saraksta un visi zemākas skaits burbulis uz leju. 898 00:37:54,990 --> 00:37:59,355 >> Vai viņš parādīs puiši forši skaņas efektu šķirošanas video? 899 00:37:59,355 --> 00:38:00,480 Tas ir sava veida atdzist. 900 00:38:00,480 --> 00:38:01,510 901 00:38:01,510 --> 00:38:05,200 Lai Robert tikko teica, algoritmu ka jūs vienkārši soli pa sarakstu, 902 00:38:05,200 --> 00:38:07,930 pārnešana blakus vērtības ja viņi nav kārtībā. 903 00:38:07,930 --> 00:38:10,975 Un tad tikai glabāt atkārtojot kamēr jums nav nekādas mijmaiņas darījumus. 904 00:38:10,975 --> 00:38:11,990 905 00:38:11,990 --> 00:38:12,740 Tātad nav slikti, vai ne? 906 00:38:12,740 --> 00:38:14,080 907 00:38:14,080 --> 00:38:16,319 Tātad mums vienkārši ir ātri piemērs šeit. 908 00:38:16,319 --> 00:38:18,360 Tātad tas notiek, lai sakārtotu tos augošā secībā. 909 00:38:18,360 --> 00:38:19,470 910 00:38:19,470 --> 00:38:23,470 Tātad, kad mēs ejam cauri pirmais laiks, mēs skatāmies caur astoņiem 911 00:38:23,470 --> 00:38:26,880 un seši ir acīmredzami nav Lai mēs mijmaiņas tiem. 912 00:38:26,880 --> 00:38:27,985 >> Tātad apskatīt nākamo. 913 00:38:27,985 --> 00:38:29,430 Astoņi un četri nav kārtībā. 914 00:38:29,430 --> 00:38:30,450 Mijmaiņas tiem. 915 00:38:30,450 --> 00:38:32,530 Un tad astoņi un divi, mijmaiņas tiem. 916 00:38:32,530 --> 00:38:33,470 Tur mēs ejam. 917 00:38:33,470 --> 00:38:39,519 Tātad, pēc jūsu pirmā caurlaide, jums zināt, ka jūsu lielākais skaits 918 00:38:39,519 --> 00:38:41,810 būs visu ceļu augšpusē, jo tas ir tikai 919 00:38:41,810 --> 00:38:44,210 būs pastāvīgi lielāks nekā viss pārējais 920 00:38:44,210 --> 00:38:46,810 un tas ir tikai gatavojas burbuli up visu ceļu līdz beigām tur. 921 00:38:46,810 --> 00:38:48,226 Vai tas ir jēga visiem? 922 00:38:48,226 --> 00:38:48,560 923 00:38:48,560 --> 00:38:49,060 Atdzist. 924 00:38:49,060 --> 00:38:51,310 925 00:38:51,310 --> 00:38:53,920 >> Tātad, tad mēs skatāmies uz mūsu otro caurlaide. 926 00:38:53,920 --> 00:38:54,980 Seši un četri, slēdzis. 927 00:38:54,980 --> 00:38:55,920 Seši un divi, slēdzis. 928 00:38:55,920 --> 00:38:58,700 Un tagad mums ir dažas lietas kārtībā. 929 00:38:58,700 --> 00:39:02,240 Tātad par katru pass, ka mēs veikt caur mūsu visu sarakstu, 930 00:39:02,240 --> 00:39:06,320 mēs zinām, ka, piemēram, ka daudzi numuriem beigās būs sakārtoti. 931 00:39:06,320 --> 00:39:07,690 932 00:39:07,690 --> 00:39:09,610 Tātad mēs trešo caurlaide, kas ir viens swap. 933 00:39:09,610 --> 00:39:10,860 934 00:39:10,860 --> 00:39:15,910 Un pēc tam mūsu ceturtais caurlaide, mums ir nulle slots. 935 00:39:15,910 --> 00:39:18,570 Un tā mēs zinām, ka mūsu masīvs ir sakārtota. 936 00:39:18,570 --> 00:39:20,900 >> Un tas ir liels lieta ar burbulis kārtošanas. 937 00:39:20,900 --> 00:39:23,720 Mēs zinām, ka tad, kad mēs ir nulle mijmaiņas darījumus, kas 938 00:39:23,720 --> 00:39:26,497 nozīmē, ka viss ir pilnīgā kārtībā. 939 00:39:26,497 --> 00:39:27,580 Tas ir veids, kā mēs pārbaudām. 940 00:39:27,580 --> 00:39:28,740 941 00:39:28,740 --> 00:39:36,480 Tāpēc mēs arī gatavojamies kodu burbulis kārtošanas kas arī nav tik slikti. 942 00:39:36,480 --> 00:39:38,120 Neviens no tiem ir, ka slikti. 943 00:39:38,120 --> 00:39:40,210 Es zinu, viņi var likties mazliet biedējošu. 944 00:39:40,210 --> 00:39:42,124 Es zinu, kad es paņēmu klase, pat tad, kad es 945 00:39:42,124 --> 00:39:44,290 mācīja šo klasi pirmo reizi pagājušajā gadā, 946 00:39:44,290 --> 00:39:46,165 Man bija tāpat, kā es varu darīt? 947 00:39:46,165 --> 00:39:48,540 Tas ir jēga, teorētiski, bet Kā mēs patiešām to dara? 948 00:39:48,540 --> 00:39:51,420 Kas ir iemesls, kāpēc es arī gribu staigāt izmantojot kodu ar jums puiši šeit. 949 00:39:51,420 --> 00:39:54,915 Tāpēc man ir pseudocode par jums puiši šoreiz. 950 00:39:54,915 --> 00:39:55,950 951 00:39:55,950 --> 00:39:58,970 Tik vienkārši paturiet to prātā, kā mēs esam par pāreju pāri. 952 00:39:58,970 --> 00:40:04,210 Tātad mums ir dažas skaitītājs, kas seko mūsu mijmaiņas darījumu, 953 00:40:04,210 --> 00:40:08,370 jo mums ir nepieciešams, lai pārliecinātos, ka ka mēs pārbaudīt to. 954 00:40:08,370 --> 00:40:11,830 Un mēs atkārtot visu masīvs kā mēs to tikko darījām ar šo piemēru. 955 00:40:11,830 --> 00:40:12,900 956 00:40:12,900 --> 00:40:17,325 Ja elements pirms ir lielāks nekā pēc tam, kad mēs esam pie elements 957 00:40:17,325 --> 00:40:20,760 mēs mijmaiņas tiem, un mēs pieauguma OUR counter jo, tiklīdz mēs swap, 958 00:40:20,760 --> 00:40:23,850 mēs vēlamies, lai mūsu counter zina, ka. 959 00:40:23,850 --> 00:40:26,247 Kādi jautājumi tur? 960 00:40:26,247 --> 00:40:27,580 Kaut kas šķiet smieklīgi nekā šeit. 961 00:40:27,580 --> 00:40:29,225 962 00:40:29,225 --> 00:40:32,350 STUDENTU: Vai jūs nosakāt skaitītāju uz nulli katru reizi, kad iet caur cilpu? 963 00:40:32,350 --> 00:40:34,339 Vai tu glabāt notiek atpakaļ uz nulli katru reizi? 964 00:40:34,339 --> 00:40:35,505 Instruktors: Ne vienmēr. 965 00:40:35,505 --> 00:40:39,710 Tātad, kas notiek, ir mēs ejam cauri šeit. 966 00:40:39,710 --> 00:40:43,830 Tā darīt, bet, atceries, tas veiks reizi bez neizdoties. 967 00:40:43,830 --> 00:40:46,480 Tātad, tas notiek, lai uzstādītu skaitītājs ir vienāds ar nulli, 968 00:40:46,480 --> 00:40:48,070 tad tas būs atkārtot, izmantojot. 969 00:40:48,070 --> 00:40:50,590 Kā tas vairākkārt uzsvērts cauri, tas tiks atjaunināta skaitītājs. 970 00:40:50,590 --> 00:40:51,870 971 00:40:51,870 --> 00:40:56,900 Kā tas aktualizē skaitītājs, kad tas ir izdarīts, kad tas ir sasnieguši masīva, 972 00:40:56,900 --> 00:41:00,830 ja mūsu saraksts nav sakārtots, skaitītājs ir atjaunoti. 973 00:41:00,830 --> 00:41:01,840 974 00:41:01,840 --> 00:41:07,150 >> Tātad tā pārbauda stāvokli un tā saka, OK, ir pretrunā lielāka par nulli. 975 00:41:07,150 --> 00:41:09,290 Ja tā ir, darīt to vēlreiz. 976 00:41:09,290 --> 00:41:14,340 Vēlaties atiestatīt tā, ka tad, kad jūs iet cauri, skaitītājs ir vienāds ar nulli. 977 00:41:14,340 --> 00:41:18,240 Ja jūs iet cauri sakārtots masīvs, nekas nemainās, 978 00:41:18,240 --> 00:41:21,355 tas neizdodas, un jūs atgriezt sakārtoti sarakstu. 979 00:41:21,355 --> 00:41:23,104 980 00:41:23,104 --> 00:41:24,020 Vai tas ir jēga? 981 00:41:24,020 --> 00:41:24,940 982 00:41:24,940 --> 00:41:26,356 STUDENTU: Tas varētu kādā mazliet. 983 00:41:26,356 --> 00:41:27,147 Instruktors: OK. 984 00:41:27,147 --> 00:41:28,980 Ja tur ir kāda cita jautājums, kas nāk uz augšu. 985 00:41:28,980 --> 00:41:30,180 986 00:41:30,180 --> 00:41:30,680 Jā. 987 00:41:30,680 --> 00:41:33,760 >> STUDENTU: Kas būtu funkcija būt pārnešana elementus? 988 00:41:33,760 --> 00:41:36,900 >> Instruktors: Tātad mēs faktiski varam rakstīt ka, ja mēs ejam uz labo tagad. 989 00:41:36,900 --> 00:41:37,801 990 00:41:37,801 --> 00:41:38,300 Atdzist. 991 00:41:38,300 --> 00:41:42,155 Tātad uz šo piezīmi, Alison notiek lai pārslēgtos atpakaļ uz ierīci. 992 00:41:42,155 --> 00:41:43,080 Tas būs jautri. 993 00:41:43,080 --> 00:41:45,170 994 00:41:45,170 --> 00:41:47,390 Un mums ir jauka burbulis veida lieta šeit. 995 00:41:47,390 --> 00:41:50,800 Tāpēc es jau darīju riteņbraukšana caur masīvs. 996 00:41:50,800 --> 00:41:53,030 Mums ir mūsu mijmaiņas darījumus, kas ir vienāda ar nulli. 997 00:41:53,030 --> 00:41:54,480 998 00:41:54,480 --> 00:41:58,440 Tāpēc mēs vēlamies, lai mijmaiņas blakus elementus, ja viņi no rīkojuma. 999 00:41:58,440 --> 00:42:03,020 Tātad pirmā lieta, mums ir nepieciešams, lai Vai ir atkārtot, izmantojot mūsu masīvs. 1000 00:42:03,020 --> 00:42:04,500 1001 00:42:04,500 --> 00:42:08,260 >> Tātad, kā jūs domājat, ka mēs varētu atkārtot, izmantojot mūsu masīvu? 1002 00:42:08,260 --> 00:42:09,720 1003 00:42:09,720 --> 00:42:13,990 Mēs esam par, un es ir vienāds ar 0. 1004 00:42:13,990 --> 00:42:16,950 1005 00:42:16,950 --> 00:42:22,454 Mēs vēlamies, i būs mazāk nekā n mīnus 1 mīnus k. 1006 00:42:22,454 --> 00:42:23,870 Un es paskaidrošu, ka sekundē. 1007 00:42:23,870 --> 00:42:26,280 1008 00:42:26,280 --> 00:42:32,830 Tātad šī ir optimizācija šeit, kur, atceros, kā es teicu pēc katras caurlaide 1009 00:42:32,830 --> 00:42:36,655 caur masīva mēs zinām, ka viss ir on-- 1010 00:42:36,655 --> 00:42:43,590 1011 00:42:43,590 --> 00:42:46,295 >> Tātad, pēc tam, kad vienā piegājienā mums zinu, ka tas ir sakārtots. 1012 00:42:46,295 --> 00:42:47,370 1013 00:42:47,370 --> 00:42:50,060 Pēc divām caurlaidēm mēs zinām ka tas viss ir sakārtots. 1014 00:42:50,060 --> 00:42:52,750 Pēc trīs caurlaides mums zinu, ka ir sakārtoti. 1015 00:42:52,750 --> 00:42:55,620 Tātad, kā es esmu atkārtojot caur masīvs šeit 1016 00:42:55,620 --> 00:43:01,090 tas ir pārliecināties, lai tikai iet caur to, ko mēs zinām, ir nešķirotas. 1017 00:43:01,090 --> 00:43:01,644 OK? 1018 00:43:01,644 --> 00:43:02,810 Tas ir tikai optimizāciju. 1019 00:43:02,810 --> 00:43:04,430 1020 00:43:04,430 --> 00:43:08,210 Jūs varētu uzrakstīt to naivi vienkārši atkārtojot caur visu, 1021 00:43:08,210 --> 00:43:09,970 tas vienkārši nepieciešams ilgāks laiks. 1022 00:43:09,970 --> 00:43:12,470 Ar šo četru cilpu tā ir tikai jauka optimizācija 1023 00:43:12,470 --> 00:43:18,460 jo mēs zinām, ka pēc katras pilnas atkārtojuma caur masīvs šeit 1024 00:43:18,460 --> 00:43:24,050 tāpat kā katru pilnu cilpa šeit, mēs zinām ka vēl viens no šiem elementiem 1025 00:43:24,050 --> 00:43:25,760 tiks sakārtots beigās. 1026 00:43:25,760 --> 00:43:28,294 >> Tāpēc mums nav jāuztraucas par tiem. 1027 00:43:28,294 --> 00:43:29,710 Vai tas ir jēga visiem? 1028 00:43:29,710 --> 00:43:30,950 Ka atdzist maz triks? 1029 00:43:30,950 --> 00:43:32,060 1030 00:43:32,060 --> 00:43:37,270 Tātad, šajā gadījumā, ja mēs atkārtojot cauri, 1031 00:43:37,270 --> 00:43:50,590 mēs zinām, ka mēs vēlamies, lai pārbaudītu, vai masīvs n un n + 1 ir kārtībā. 1032 00:43:50,590 --> 00:43:52,640 1033 00:43:52,640 --> 00:43:53,559 OK. 1034 00:43:53,559 --> 00:43:54,600 Tātad, šeit ir pseudocode. 1035 00:43:54,600 --> 00:43:57,540 Mēs vēlamies, lai pārbaudītu, vai masīvs n un n plus 1 ir kārtībā. 1036 00:43:57,540 --> 00:43:59,520 Tātad, ko mēs varbūt esam tur? 1037 00:43:59,520 --> 00:44:01,090 1038 00:44:01,090 --> 00:44:03,120 Tas būs daži nosacījumu. 1039 00:44:03,120 --> 00:44:04,220 Tas ir, ja. 1040 00:44:04,220 --> 00:44:07,066 >> STUDENTU: Ja masīvs n mazāk nekā masīvs n plus 1. 1041 00:44:07,066 --> 00:44:07,816 Instruktors: Mm-hm. 1042 00:44:07,816 --> 00:44:09,000 1043 00:44:09,000 --> 00:44:10,699 Nu, ir mazāks vai lielāks nekā. 1044 00:44:10,699 --> 00:44:11,615 STUDENTU: Lielāka nekā. 1045 00:44:11,615 --> 00:44:15,850 1046 00:44:15,850 --> 00:44:17,620 Tad mēs gribam, lai mijmaiņas tiem. 1047 00:44:17,620 --> 00:44:18,570 Tieši tā. 1048 00:44:18,570 --> 00:44:23,570 Tāpēc tagad mēs nokļūt, kas ir mehānisms pārnešana viņiem? 1049 00:44:23,570 --> 00:44:24,840 1050 00:44:24,840 --> 00:44:28,137 Tātad, mēs devāmies caur šo īsi, tipa mijmaiņas funkciju pagājušajā nedēļā. 1051 00:44:28,137 --> 00:44:29,595 Vai kāds atceras, kā tas strādā? 1052 00:44:29,595 --> 00:44:32,300 1053 00:44:32,300 --> 00:44:34,950 Tātad, mēs varam ne tikai pārcelt tos, vai ne? 1054 00:44:34,950 --> 00:44:36,640 Jo viens no viņiem būs pazust. 1055 00:44:36,640 --> 00:44:41,696 Ja mēs teikt, ir vienāda ar B un pēc tam B ir vienāds ar A, visi tie abi pēkšņi 1056 00:44:41,696 --> 00:44:43,150 ir tikai vienāda ar B 1057 00:44:43,150 --> 00:44:45,720 >> Tātad, kas mums ir jādara, ir mums ir pagaidu mainīgo, kas ir 1058 00:44:45,720 --> 00:44:49,055 gatavojas rīkot mūsējais brītiņa mēs esam procesā pārnešana. 1059 00:44:49,055 --> 00:44:50,200 1060 00:44:50,200 --> 00:44:56,464 Tātad, kas mums ir, ir mums būs dažas int temp ir vienāds kuri paredzēti, lai jūs varētu piešķirt to 1061 00:44:56,464 --> 00:44:59,130 uz kuru jūs vēlaties, vienkārši pārliecinieties, ka jums sekot līdzi it-- 1062 00:44:59,130 --> 00:45:01,840 tāpēc šajā gadījumā, es esmu gatavojas piešķirt to masīva n plus 1. 1063 00:45:01,840 --> 00:45:03,360 1064 00:45:03,360 --> 00:45:07,674 Tāpēc, ka gatavojas rīkot neatkarīgi vērtība ir šajā otrajā blokā 1065 00:45:07,674 --> 00:45:08,590 ka mēs meklējam. 1066 00:45:08,590 --> 00:45:09,700 1067 00:45:09,700 --> 00:45:13,240 >> Un tad mēs varam darīt, ir, mēs varam iet priekšu un Piešķirt masīvs n plus 1, 1068 00:45:13,240 --> 00:45:14,990 jo mēs zinām, mēs ir šo vērtību glabājas. 1069 00:45:14,990 --> 00:45:16,645 1070 00:45:16,645 --> 00:45:19,270 Tas ir arī viens liels things-- Es nezinu, vai kāds no jums 1071 00:45:19,270 --> 00:45:23,780 bija problēmas, kur, ja jūs slēdzis divas rindas kods pēkšņi viss strādāja. 1072 00:45:23,780 --> 00:45:25,880 Rīkojums ir ļoti svarīgi CS. 1073 00:45:25,880 --> 00:45:29,450 Tātad, pārliecinieties, ka jūs diagramma lietas, ja iespējams, 1074 00:45:29,450 --> 00:45:31,230 par to, kas patiesībā notiek. 1075 00:45:31,230 --> 00:45:34,256 Tāpēc tagad mēs ejam pārdalīt masīvs n plus 1, 1076 00:45:34,256 --> 00:45:36,005 jo mēs zinām, mēs ir šo vērtību glabājas. 1077 00:45:36,005 --> 00:45:37,090 1078 00:45:37,090 --> 00:45:41,560 >> Un mēs varam piešķirt, ka masīvu n vai šajā gadījumā masīva i. 1079 00:45:41,560 --> 00:45:50,540 1080 00:45:50,540 --> 00:45:51,465 Pārāk daudz mainīgie. 1081 00:45:51,465 --> 00:45:54,230 1082 00:45:54,230 --> 00:45:55,470 OK. 1083 00:45:55,470 --> 00:46:01,500 Tāpēc tagad mēs esam no jauna masīvs I plus 1 līdz vienādai to, kas masīvā i. 1084 00:46:01,500 --> 00:46:08,240 Un tagad mēs varam doties atpakaļ un piešķirt masīvs I ko? 1085 00:46:08,240 --> 00:46:10,680 1086 00:46:10,680 --> 00:46:11,180 Ikviens? 1087 00:46:11,180 --> 00:46:13,490 1088 00:46:13,490 --> 00:46:14,010 >> STUDENTU: 10. 1089 00:46:14,010 --> 00:46:14,680 >> Instruktors: 10. 1090 00:46:14,680 --> 00:46:15,180 Tieši tā. 1091 00:46:15,180 --> 00:46:16,930 1092 00:46:16,930 --> 00:46:18,640 Un viena pēdējā lieta. 1093 00:46:18,640 --> 00:46:21,840 Ja mēs esam samainīti to tagad, Kas mums jādara? 1094 00:46:21,840 --> 00:46:23,740 Kas ir viena lieta kas notiek, lai pastāstītu mums 1095 00:46:23,740 --> 00:46:27,542 Ja mēs kādreiz pārtraukt šo programmu? 1096 00:46:27,542 --> 00:46:29,250 Kas saka, ka mums ir sakārtoti sarakstu? 1097 00:46:29,250 --> 00:46:31,560 1098 00:46:31,560 --> 00:46:33,750 Ja mums nav jāveic nekādas mijmaiņas darījumus, vai ne? 1099 00:46:33,750 --> 00:46:36,900 Ja mijmaiņas darījumiem ir vienāds ar nulles beigās to. 1100 00:46:36,900 --> 00:46:42,975 Tātad, ja jūs veikt mijmaiņas, kā mēs tikko bija šeit, mēs vēlamies atjaunināt mijmaiņas darījumus. 1101 00:46:42,975 --> 00:46:45,002 1102 00:46:45,002 --> 00:46:47,210 Un es zinu, tur bija Jautājums agrāk par jūs varat 1103 00:46:47,210 --> 00:46:49,689 izmantot nulle vai viens tā vietā no patiess vai nepatiess. 1104 00:46:49,689 --> 00:46:50,980 Un tas, ko tas dara šeit. 1105 00:46:50,980 --> 00:46:52,750 Tātad šis saka, ja ne mijmaiņas darījumus. 1106 00:46:52,750 --> 00:47:01,310 Tātad, ja mijmaiņas līgumi ir nulle, kas is-- es vienmēr saņemt savu patiesības un mani falses sajaukti. 1107 00:47:01,310 --> 00:47:03,960 Mēs vēlamies, lai mēs novērtētu taisnība un tas nav. 1108 00:47:03,960 --> 00:47:07,680 1109 00:47:07,680 --> 00:47:09,630 Tātad, ja tas ir nulle, tad tas ir viltus. 1110 00:47:09,630 --> 00:47:12,560 Ja jūs noliegt to ar [? sprādziena?] tas kļūst taisnība. 1111 00:47:12,560 --> 00:47:13,975 Tātad šī līnija izpilda. 1112 00:47:13,975 --> 00:47:15,060 1113 00:47:15,060 --> 00:47:17,370 >> Patiesības un viltus un nullēm un tiem get crazy. 1114 00:47:17,370 --> 00:47:20,690 Tikai ja tu lēnām staigāt caur to tas būs jēga. 1115 00:47:20,690 --> 00:47:23,320 Bet tas, ko šis mazais mazliet koda šeit dara. 1116 00:47:23,320 --> 00:47:26,490 Tātad tas pārbauda, mēs esam izdarījuši nekādus mijmaiņas darījumus. 1117 00:47:26,490 --> 00:47:30,054 Tātad, ja tas ir kaut kas papildus nulle, tas būs viltus 1118 00:47:30,054 --> 00:47:31,970 un viss ir gatavojas izpildīt vēlreiz. 1119 00:47:31,970 --> 00:47:33,150 1120 00:47:33,150 --> 00:47:33,650 Forši? 1121 00:47:33,650 --> 00:47:34,660 1122 00:47:34,660 --> 00:47:36,000 >> STUDENTU: Kāda pauze darīt? 1123 00:47:36,000 --> 00:47:38,990 >> Instruktors: Break tikko pauzes jūs no cilpas. 1124 00:47:38,990 --> 00:47:41,570 Tātad šajā gadījumā tas būtu tāpat kā beigt programmu 1125 00:47:41,570 --> 00:47:43,828 un jūs vienkārši jūsu sakārtoti sarakstu. 1126 00:47:43,828 --> 00:47:44,536 STUDENTU: Amazing. 1127 00:47:44,536 --> 00:47:48,094 1128 00:47:48,094 --> 00:47:49,010 Instruktors: Es atvainojos? 1129 00:47:49,010 --> 00:47:52,110 STUDENTU: Jo agrāk mēs izmantoja rakstīts 1 pār rakstīts nulle 1130 00:47:52,110 --> 00:47:54,170 iesniegt, ka, ja kas strādā vai ne. 1131 00:47:54,170 --> 00:47:54,878 >> Instruktors: Jā. 1132 00:47:54,878 --> 00:47:56,410 Lai jūs varētu atgriezties nulle vai 1. 1133 00:47:56,410 --> 00:47:58,950 Šajā gadījumā, jo mēs neesam reāli darīt kaut ko ar funkciju, 1134 00:47:58,950 --> 00:48:00,150 Mēs vienkārši gribam, lai izjauktu. 1135 00:48:00,150 --> 00:48:02,680 Mums nav īsti rūp to. 1136 00:48:02,680 --> 00:48:06,960 Bremzes ir arī labi, ja tas ir izmantots, lai izrauties 1137 00:48:06,960 --> 00:48:10,710 četru cilpas vai apstākļiem, kas Jūs nevēlaties, lai saglabātu izpildes. 1138 00:48:10,710 --> 00:48:12,110 Tā vienkārši notiek, jūs no tām. 1139 00:48:12,110 --> 00:48:13,587 1140 00:48:13,587 --> 00:48:14,795 Tas ir mazliet nianse lieta. 1141 00:48:14,795 --> 00:48:16,737 1142 00:48:16,737 --> 00:48:18,445 Es jūtos kā tur ir daudz roku vicināšanu, 1143 00:48:18,445 --> 00:48:19,740 tāpat kā jūs uzzināt par to drīz. 1144 00:48:19,740 --> 00:48:20,955 >> Bet jūs varēsiet uzzināt par to drīz. 1145 00:48:20,955 --> 00:48:21,500 Es apsolu. 1146 00:48:21,500 --> 00:48:22,670 1147 00:48:22,670 --> 00:48:23,170 OK. 1148 00:48:23,170 --> 00:48:24,840 Lai vai ikviens saņemt burbuļu veida? 1149 00:48:24,840 --> 00:48:25,550 Ne pārāk slikti. 1150 00:48:25,550 --> 00:48:31,910 Atkārtot, izmantojot, mijmaiņas lietas izmantojot temp mainīgs, un mēs visi, kas tur? 1151 00:48:31,910 --> 00:48:32,960 Atdzist. 1152 00:48:32,960 --> 00:48:34,080 Awesome. 1153 00:48:34,080 --> 00:48:34,807 OK. 1154 00:48:34,807 --> 00:48:35,765 Atpakaļ uz PowerPoint. 1155 00:48:35,765 --> 00:48:38,140 1156 00:48:38,140 --> 00:48:40,130 Kādi jautājumi kopumā par šiem tik tālu? 1157 00:48:40,130 --> 00:48:41,200 1158 00:48:41,200 --> 00:48:41,700 Atdzist. 1159 00:48:41,700 --> 00:48:43,110 1160 00:48:43,110 --> 00:48:43,695 Mm-hm. 1161 00:48:43,695 --> 00:48:45,279 >> STUDENTU: [dzirdams] int galvenais parasti. 1162 00:48:45,279 --> 00:48:46,695 Vai jums ir, ka par šo? 1163 00:48:46,695 --> 00:48:48,400 1164 00:48:48,400 --> 00:48:53,550 >> Instruktors: Tātad mēs vienkārši meklējam tikai faktiskajā šķirošanas algoritmu. 1165 00:48:53,550 --> 00:48:54,559 1166 00:48:54,559 --> 00:48:56,350 Ja jums bija tā laikā piemēram, plašākas programmas, 1167 00:48:56,350 --> 00:48:57,891 jums būtu int galvenais kaut kur. 1168 00:48:57,891 --> 00:49:00,070 1169 00:49:00,070 --> 00:49:02,880 Atkarībā no tā, kur jūs izmantot šo algoritmu, 1170 00:49:02,880 --> 00:49:05,860 tas varētu noteikt, kas ir tiek atdoti to. 1171 00:49:05,860 --> 00:49:09,960 Bet mūsu gadījumā, mēs esam stingri meklē veidus, kā to dara reāli 1172 00:49:09,960 --> 00:49:11,300 atkārtot, izmantojot masīvu. 1173 00:49:11,300 --> 00:49:12,570 Tāpēc mums nav jāuztraucas par to. 1174 00:49:12,570 --> 00:49:14,150 1175 00:49:14,150 --> 00:49:19,830 >> Tātad mēs runājam par labāko lietu un vissliktākie scenāriji bināro meklēšanu. 1176 00:49:19,830 --> 00:49:22,470 Tātad, tas ir arī svarīgi darīt ka katrā no mūsu veidu. 1177 00:49:22,470 --> 00:49:24,200 1178 00:49:24,200 --> 00:49:27,560 Tātad, ko jūs domājat, ir sliktākais gadījums runtime burbuļiem veida? 1179 00:49:27,560 --> 00:49:29,560 1180 00:49:29,560 --> 00:49:30,700 Jūs guys atceries? 1181 00:49:30,700 --> 00:49:31,784 >> STUDENTU: N mīnus 1. 1182 00:49:31,784 --> 00:49:32,700 Instruktors: N mīnus 1. 1183 00:49:32,700 --> 00:49:35,070 Tātad tas nozīmē, ka ir n mīnus 1 salīdzinājumi. 1184 00:49:35,070 --> 00:49:40,060 Tik viena lieta saprast, ir ka uz pirmo atkārtošanu, 1185 00:49:40,060 --> 00:49:43,360 mēs ejam cauri, mēs salīdzinām šie two-- tā ka ir 1. 1186 00:49:43,360 --> 00:49:46,685 Šie divi, trīs, četri. 1187 00:49:46,685 --> 00:49:48,070 1188 00:49:48,070 --> 00:49:55,050 Tātad, pēc viena atkārtojuma mums jau ir četri salīdzinājumus. 1189 00:49:55,050 --> 00:49:58,230 Kad es runāju par runtime un n. 1190 00:49:58,230 --> 00:50:04,680 N apzīmē skaitu salīdzināšanu atkarībā no tā, cik elementiem 1191 00:50:04,680 --> 00:50:05,570 mums ir. 1192 00:50:05,570 --> 00:50:06,430 OK? 1193 00:50:06,430 --> 00:50:08,860 >> Tātad mēs ejam cauri, mums ir četri. 1194 00:50:08,860 --> 00:50:11,780 Nākamreiz, kad jūs zināt, mums nav ir rūpēties par to. 1195 00:50:11,780 --> 00:50:15,140 Mēs salīdzinām šīs divas, šie divi, šie divi, 1196 00:50:15,140 --> 00:50:20,050 un, ja mums nav, ka optimizācijas ar četriem cilpa, kas man rakstīja, 1197 00:50:20,050 --> 00:50:22,750 jums būtu salīdzināt šeit anyways. 1198 00:50:22,750 --> 00:50:26,170 Tātad jums būtu palaist caur masīva 1199 00:50:26,170 --> 00:50:34,380 un veikt salīdzinājumus n n reizes, jo katru reizi, kad mēs 1200 00:50:34,380 --> 00:50:36,670 palaist caur to mēs kārtošanas viena lieta. 1201 00:50:36,670 --> 00:50:38,300 1202 00:50:38,300 --> 00:50:41,475 >> Un katru reizi, kad mēs palaist cauri masīvs, mēs n salīdzinājumus. 1203 00:50:41,475 --> 00:50:42,920 1204 00:50:42,920 --> 00:50:46,330 Tātad mūsu runtime ir tas, faktiski n rūtiņām, kas 1205 00:50:46,330 --> 00:50:48,400 ir daudz sliktāks mūsu log beigām, jo ​​tas 1206 00:50:48,400 --> 00:50:51,965 nozīmē, ja mums bija četri miljards elementi, tas ir 1207 00:50:51,965 --> 00:50:55,260 gatavojas veikt mums četru miljardu brusas, nevis 32. 1208 00:50:55,260 --> 00:51:01,240 Tāpēc ne labākais runtime, bet dažām lietām, 1209 00:51:01,240 --> 00:51:04,610 jūs zināt, ja jūs laikā zināma virkne elementu 1210 00:51:04,610 --> 00:51:06,540 burbulis kārtošanas var labi izmantot. 1211 00:51:06,540 --> 00:51:07,530 >> OK. 1212 00:51:07,530 --> 00:51:12,290 Tāpēc tagad to, kas ir labākais gadījums runtime? 1213 00:51:12,290 --> 00:51:14,357 1214 00:51:14,357 --> 00:51:14,940 STUDENTU: Zero? 1215 00:51:14,940 --> 00:51:16,420 Vai 1? 1216 00:51:16,420 --> 00:51:18,140 >> Instruktors: Tātad 1 būtu viens salīdzinājums. 1217 00:51:18,140 --> 00:51:19,114 Pa labi. 1218 00:51:19,114 --> 00:51:20,002 >> STUDENTU: N mīnus 1? 1219 00:51:20,002 --> 00:51:21,380 1220 00:51:21,380 --> 00:51:22,320 >> Instruktors: Tātad, jā. 1221 00:51:22,320 --> 00:51:22,990 Tātad n mīnus 1. 1222 00:51:22,990 --> 00:51:26,510 Ikreiz, kad jums ir koncepcija, piemēram, n mīnus 1, mums ir tendence tikai piliens to izslēgtu 1223 00:51:26,510 --> 00:51:31,680 un mēs tikai teikt n tāpēc, ka jums ir lai salīdzinātu katru these-- katra pāra. 1224 00:51:31,680 --> 00:51:36,470 Tātad tas būtu n mīnus 1, ko mēs mēs gribētu tikai teikt, ir aptuveni n. 1225 00:51:36,470 --> 00:51:39,280 Ja jums ir darīšana ar runtime, viss ir tuvina. 1226 00:51:39,280 --> 00:51:43,860 Tik ilgi, kamēr eksponents ir pareizi, tu esi diezgan labi. 1227 00:51:43,860 --> 00:51:45,700 >> Tas, kā mēs galā ar to. 1228 00:51:45,700 --> 00:51:47,410 1229 00:51:47,410 --> 00:51:51,780 Tā, ka labākajā gadījumā ir n, kas nozīmē, ka saraksts ir jau sakārtots, 1230 00:51:51,780 --> 00:51:54,320 un viss, kas mums jādara, ir palaist cauri un pārbaudiet, vai tas ir sakārtoti. 1231 00:51:54,320 --> 00:51:56,110 1232 00:51:56,110 --> 00:51:56,855 Atdzist. 1233 00:51:56,855 --> 00:51:57,355 Labi. 1234 00:51:57,355 --> 00:51:58,980 1235 00:51:58,980 --> 00:52:01,920 Tātad, kā jūs redzēt šeit, mēs vienkārši ir dažas vairāk grafikus. 1236 00:52:01,920 --> 00:52:02,660 Tātad n brusas. 1237 00:52:02,660 --> 00:52:03,780 1238 00:52:03,780 --> 00:52:05,120 Jautri. 1239 00:52:05,120 --> 00:52:09,730 Daudz sliktāk, nekā n, kā mēs redzam, un daudz, daudz sliktāk, nekā log 2 n. 1240 00:52:09,730 --> 00:52:12,060 Un tad jūs arī nokļūt log baļķiem. 1241 00:52:12,060 --> 00:52:18,020 Un jūs lietojat 124, jūs nokļūt piemēram, log zvaigzne, kas ir kā traks. 1242 00:52:18,020 --> 00:52:20,172 Tātad, ja jūs interesē, lookup log zvaigzne. 1243 00:52:20,172 --> 00:52:20,880 Tas ir sava veida jautrību. 1244 00:52:20,880 --> 00:52:22,800 1245 00:52:22,800 --> 00:52:24,220 Tāpēc mums ir šo lielisko diagrammu. 1246 00:52:24,220 --> 00:52:25,360 1247 00:52:25,360 --> 00:52:28,720 Tikai galvu uz augšu, tas brīnišķīgi diagramma ir 1248 00:52:28,720 --> 00:52:31,350 Jūsu vidusposmā, jo mēs ilgi uzdot jums šos thins. 1249 00:52:31,350 --> 00:52:36,090 Tātad tikai galvu uz augšu, ir šo par jūsu vidusposma jūsu jauku apkrāptu lapas 1250 00:52:36,090 --> 00:52:36,616 tur. 1251 00:52:36,616 --> 00:52:37,990 Tātad mēs vienkārši paskatījās burbulis veida. 1252 00:52:37,990 --> 00:52:39,510 1253 00:52:39,510 --> 00:52:42,370 Sliktākajā gadījumā, n brusas, labākajā gadījumā, n. 1254 00:52:42,370 --> 00:52:43,367 1255 00:52:43,367 --> 00:52:44,950 Un mēs ejam apskatīt citiem. 1256 00:52:44,950 --> 00:52:47,940 >> Un, kā jūs varat redzēt, vienīgais viens, ka tiešām labi 1257 00:52:47,940 --> 00:52:50,910 ir apvienot kārtot, ko mēs nokļūt, kāpēc. 1258 00:52:50,910 --> 00:52:52,690 1259 00:52:52,690 --> 00:52:55,215 Tāpēc mēs esam gatavojas doties uz nākamais here-- izvēle kārtošanas. 1260 00:52:55,215 --> 00:52:56,360 1261 00:52:56,360 --> 00:52:58,420 Vai kāds atceras, kā atlase kārtošanas strādāja? 1262 00:52:58,420 --> 00:53:05,200 1263 00:53:05,200 --> 00:53:05,700 Iet uz to. 1264 00:53:05,700 --> 00:53:08,210 >> STUDENTU: Būtībā iet cauri pasūtījumu un izveidot jaunu sarakstu. 1265 00:53:08,210 --> 00:53:11,001 Un, tāpat kā jūs liekot elementus in, nodot tos pareizajā vietā 1266 00:53:11,001 --> 00:53:11,750 jaunajā sarakstā. 1267 00:53:11,750 --> 00:53:14,040 >> Instruktors: Tāpēc, ka skaņas vairāk kā ievietošanas veida. 1268 00:53:14,040 --> 00:53:15,040 Bet tu esi patiešām tuvu. 1269 00:53:15,040 --> 00:53:15,915 Viņi ir ļoti līdzīgi. 1270 00:53:15,915 --> 00:53:17,440 Pat man viņus jaukt reizēm. 1271 00:53:17,440 --> 00:53:18,981 Pirms šajā sadaļā man bija, piemēram, jāgaida. 1272 00:53:18,981 --> 00:53:20,130 1273 00:53:20,130 --> 00:53:20,630 OK. 1274 00:53:20,630 --> 00:53:24,141 Tātad, ko jūs vēlaties darīt, ir izvēle kārtot, 1275 00:53:24,141 --> 00:53:25,890 kā jūs varat iedomāties par to un to, kā 1276 00:53:25,890 --> 00:53:30,140 Es pārliecinos, ka man mēģiniet nav iegūt viņiem jaukt, tas iet cauri 1277 00:53:30,140 --> 00:53:33,280 un tas izvēlas mazākais skaits un tā 1278 00:53:33,280 --> 00:53:36,070 liek, ka sākumā savu sarakstu. 1279 00:53:36,070 --> 00:53:37,730 Tā mijmaiņas to ar šīs pirmās vietas. 1280 00:53:37,730 --> 00:53:42,600 1281 00:53:42,600 --> 00:53:45,370 Viņi tiešām ir piemērs par mani. 1282 00:53:45,370 --> 00:53:46,540 Awesome. 1283 00:53:46,540 --> 00:53:50,130 Tik vienkārši veids, kā domāt par it-- atlases kārtot, izvēlētos mazāko vērtību. 1284 00:53:50,130 --> 00:53:51,940 Un mēs ejam palaist caur piemēru 1285 00:53:51,940 --> 00:53:55,320 ka es domāju, ka palīdzēs, jo Es domāju, Visuals vienmēr palīdzēt. 1286 00:53:55,320 --> 00:53:58,510 Tātad sākam ar kaut ko tas ir pilnīgi nešķirotas. 1287 00:53:58,510 --> 00:54:00,730 Red būs nešķiroti, zaļā tiks sakārtoti. 1288 00:54:00,730 --> 00:54:02,190 Tas viss jēga sekundē. 1289 00:54:02,190 --> 00:54:08,950 >> Tātad mēs ejam cauri, un mēs atkārtot no sākuma līdz beigām. 1290 00:54:08,950 --> 00:54:12,320 Un mēs sakām, OK, 2 ir Mūsu mazākais skaitlis. 1291 00:54:12,320 --> 00:54:15,680 Tāpēc mēs esam gatavojas pieņemt 2. un mēs braucam lai to pārvietotu uz priekšu mūsu masīva 1292 00:54:15,680 --> 00:54:17,734 jo tas ir Vismazāk mēs esam. 1293 00:54:17,734 --> 00:54:19,150 Tātad tas, ko tas dara šeit. 1294 00:54:19,150 --> 00:54:20,820 Tas ir tikai gatavojas mijmaiņas šīs divas. 1295 00:54:20,820 --> 00:54:21,850 1296 00:54:21,850 --> 00:54:25,450 Tāpēc tagad mums ir sakārtoti daļa, un nešķirotas sastāvdaļa. 1297 00:54:25,450 --> 00:54:27,810 Un, kas ir labi atcerēties par atlases veida 1298 00:54:27,810 --> 00:54:30,690 ir, mēs esam tikai izvēloties no nešķirotiem daļas. 1299 00:54:30,690 --> 00:54:32,220 1300 00:54:32,220 --> 00:54:34,527 >> Šķiroto daļa jūs vienkārši atstāt vienatnē. 1301 00:54:34,527 --> 00:54:35,660 Mm-hm? 1302 00:54:35,660 --> 00:54:38,452 >> STUDENTU: Kā tas zina, kas ir mazākais bez salīdzinot 1303 00:54:38,452 --> 00:54:39,868 uz jebkuru citu vērtību masīvā. 1304 00:54:39,868 --> 00:54:41,250 Instruktors: Tas salīdzināt to. 1305 00:54:41,250 --> 00:54:42,041 Mums patīk izlaidis to. 1306 00:54:42,041 --> 00:54:43,850 Tas ir tikai vispārīgs visaptverošs. 1307 00:54:43,850 --> 00:54:44,831 Yeah. 1308 00:54:44,831 --> 00:54:47,205 Kad mēs rakstīt kodu es esmu pārliecināts, ka jums būs vairāk apmierināti. 1309 00:54:47,205 --> 00:54:48,696 1310 00:54:48,696 --> 00:54:53,030 Bet vispirms jums saglabāt šo elements, jo mazākais. 1311 00:54:53,030 --> 00:54:56,110 Jūs salīdzināt un jūs saka, OK, tas ir mazāks? 1312 00:54:56,110 --> 00:54:56,660 Jā. 1313 00:54:56,660 --> 00:54:57,460 Paturiet to. 1314 00:54:57,460 --> 00:54:58,640 Lūk, tas ir mazāks? 1315 00:54:58,640 --> 00:54:59,660 Nē? 1316 00:54:59,660 --> 00:55:02,510 >> Šis ir jūsu mazākais, pārdalīt to savā vērtību. 1317 00:55:02,510 --> 00:55:06,340 Un jūs būsiet daudz laimīgāki kad mēs ejam cauri kodu. 1318 00:55:06,340 --> 00:55:07,510 1319 00:55:07,510 --> 00:55:13,970 Tātad mēs ejam cauri, mēs swap to, lai pēc tam mēs skatāmies uz šo nešķirotiem daļu. 1320 00:55:13,970 --> 00:55:15,810 Tātad mēs ejam, lai izvēlētos trīs out. 1321 00:55:15,810 --> 00:55:18,890 Mēs ejam, lai nodot to pie beigas mūsu šķirotas porcijas. 1322 00:55:18,890 --> 00:55:20,267 1323 00:55:20,267 --> 00:55:23,100 Un mēs esam tikai gatavojas, lai saglabātu darot ka to dara, un dara to. 1324 00:55:23,100 --> 00:55:24,130 1325 00:55:24,130 --> 00:55:27,420 Tātad šī ir mūsu veida pseudocode šeit. 1326 00:55:27,420 --> 00:55:29,470 1327 00:55:29,470 --> 00:55:31,380 Mēs kodēt to šeit sekundē. 1328 00:55:31,380 --> 00:55:34,140 1329 00:55:34,140 --> 00:55:37,270 Bet tikai kaut staigāt pa augstā līmenī. 1330 00:55:37,270 --> 00:55:40,275 Jūs gatavojas aiziet no i ir vienāds ar 0 līdz n mīnus 2. 1331 00:55:40,275 --> 00:55:41,570 1332 00:55:41,570 --> 00:55:43,530 Tas ir cits optimizāciju. 1333 00:55:43,530 --> 00:55:45,020 Neuztraucieties pārāk daudz par to. 1334 00:55:45,020 --> 00:55:46,620 Tātad, kā jūs sakāt. 1335 00:55:46,620 --> 00:55:49,660 1336 00:55:49,660 --> 00:55:54,406 Kā Jēkabs tika sakot, kā mēs sekot līdzi tam, ko mūsu minimālais ir? 1337 00:55:54,406 --> 00:55:55,030 Kā mēs zinām? 1338 00:55:55,030 --> 00:55:57,060 Mums ir, lai salīdzinātu viss mūsu sarakstā. 1339 00:55:57,060 --> 00:55:59,600 >> Tātad minimālā vienāds i. 1340 00:55:59,600 --> 00:56:03,870 Tas ir tikai saprotams, šajā gadījumā indekss mūsu minimālās vērtības. 1341 00:56:03,870 --> 00:56:07,660 Tātad tas būs atkārtot, izmantojot un tas iet no j vienāds i plus 1. 1342 00:56:07,660 --> 00:56:11,420 Tātad mēs jau zinām, ka tas ir mūsu pirmais elements. 1343 00:56:11,420 --> 00:56:13,240 Mums nevajag, lai salīdzinātu to ar sevi. 1344 00:56:13,240 --> 00:56:16,970 Tātad mēs sākam salīdzinot to ar nākamo viens, kas ir iemesls, kāpēc tas ir man plus 1 līdz n 1345 00:56:16,970 --> 00:56:20,110 mīnus 1, kas ir gals masīva tur. 1346 00:56:20,110 --> 00:56:25,090 Un mēs teicām, ja masīvs at j ir mazāks nekā masīvs min, 1347 00:56:25,090 --> 00:56:29,200 tad mēs pārdalīt kur Mūsu minimālais indeksiem. 1348 00:56:29,200 --> 00:56:37,470 >> Un ja min nav vienāds ar i, kā to, kur mēs bijām atpakaļ vairāk nekā šeit. 1349 00:56:37,470 --> 00:56:38,950 1350 00:56:38,950 --> 00:56:41,790 Tātad, kā tad, kad mēs pirmo reizi bija šo vienu. 1351 00:56:41,790 --> 00:56:49,310 Šajā gadījumā, tā sākas nulle, tas galu galā ir divi. 1352 00:56:49,310 --> 00:56:53,010 Tātad min nebūtu vienāds i beigās. 1353 00:56:53,010 --> 00:56:55,720 Tas ļauj mums zināt, ka mums ir nepieciešams, lai mijmaiņas tiem. 1354 00:56:55,720 --> 00:56:57,420 1355 00:56:57,420 --> 00:57:00,470 Es jūtos kā konkrētu piemēru palīdzēs daudz vairāk nekā šis. 1356 00:57:00,470 --> 00:57:04,970 Tāpēc es ņemšu kods tas ar jums, puiši tieši tagad, un es domāju, ka tā būs labāk. 1357 00:57:04,970 --> 00:57:07,380 1358 00:57:07,380 --> 00:57:11,350 >> Kārto tendence strādāt, ka veids, ka tas bieži vien ir labāk, tikai, lai redzētu tos. 1359 00:57:11,350 --> 00:57:12,780 1360 00:57:12,780 --> 00:57:17,280 Tātad, ko mēs vēlamies darīt, ir mēs vispirms gribam mazākais 1361 00:57:17,280 --> 00:57:19,890 elements savā nostājā masīvā. 1362 00:57:19,890 --> 00:57:21,280 Tieši tas, ko Jēkabs teica. 1363 00:57:21,280 --> 00:57:23,090 Jums ir nepieciešams, lai saglabātu, ka kaut kā. 1364 00:57:23,090 --> 00:57:25,900 Tāpēc mēs esam gatavojas sākt šeit atkārtojot pār masīva. 1365 00:57:25,900 --> 00:57:28,970 Mēs ejam, lai saka, tas ir mūsu Pirmais tikai sākt. 1366 00:57:28,970 --> 00:57:38,308 Tātad mēs nāksies int mazākais ir vienāds ar bloku pie i. 1367 00:57:38,308 --> 00:57:40,500 1368 00:57:40,500 --> 00:57:45,050 >> Tik viena lieta, lai paziņojuma, ik reizi tas cilpa izpilda, 1369 00:57:45,050 --> 00:57:48,550 mēs sākam vienu soli tālāk. 1370 00:57:48,550 --> 00:57:54,780 1371 00:57:54,780 --> 00:57:57,440 Kad mēs sākam mēs skatāmies uz šo vienu. 1372 00:57:57,440 --> 00:58:00,840 Nākamajā reizē, kad mēs atkārtot, izmantojot, mēs sākot šo vienu 1373 00:58:00,840 --> 00:58:02,680 un tas mūsu mazāko vērtību piešķiršanu. 1374 00:58:02,680 --> 00:58:10,450 Tātad, tas ir ļoti līdzīgs burbulis kārtot kur mēs zinām, ka pēc tam, kad vienā piegājienā, 1375 00:58:10,450 --> 00:58:11,700 šis pēdējais elements ir sakārtots. 1376 00:58:11,700 --> 00:58:12,810 1377 00:58:12,810 --> 00:58:15,120 Ar atlases veida, tas ir tikai pretējo. 1378 00:58:15,120 --> 00:58:18,950 >> Katrā pass, mēs zinām, ka Pirmais ir sakārtoti. 1379 00:58:18,950 --> 00:58:21,360 Pēc tam, kad otrās pass, Otrs tiks sakārtoti. 1380 00:58:21,360 --> 00:58:26,470 Un, kā jūs redzēja ar slaidu piemēriem, Mūsu sakārtoti daļa vienkārši turpina pieaugt. 1381 00:58:26,470 --> 00:58:34,020 Tātad, nosakot mūsu vismazākais lai bloki i, visi tā dara 1382 00:58:34,020 --> 00:58:37,340 ir sašaurināšanos, ko mēs meklējam, lai tādējādi 1383 00:58:37,340 --> 00:58:40,164 lai līdz minimumam samazinātu salīdzinājumi mēs. 1384 00:58:40,164 --> 00:58:41,770 Vai tas ir jēga visiem? 1385 00:58:41,770 --> 00:58:42,920 1386 00:58:42,920 --> 00:58:46,380 Vai jums ir nepieciešams mani, lai palaistu cauri, ka atkal lēnāk vai dažādās vārdiem? 1387 00:58:46,380 --> 00:58:47,180 Es esmu laimīgs. 1388 00:58:47,180 --> 00:58:48,095 1389 00:58:48,095 --> 00:58:48,595 OK. 1390 00:58:48,595 --> 00:58:50,060 1391 00:58:50,060 --> 00:58:55,540 >> Tātad mēs esam glabāšanai vērtība šajā brīdī, 1392 00:58:55,540 --> 00:58:57,840 bet mēs arī vēlamies, lai saglabātu indeksu. 1393 00:58:57,840 --> 00:59:01,010 Tātad mēs ejam, lai saglabātu nostāja mazākais 1394 00:59:01,010 --> 00:59:02,770 viens, kas ir tikai būs i. 1395 00:59:02,770 --> 00:59:04,357 1396 00:59:04,357 --> 00:59:05,440 Tāpēc tagad Jēkabs ir izpildīts. 1397 00:59:05,440 --> 00:59:06,870 Mums ir lietas saglabāti. 1398 00:59:06,870 --> 00:59:08,240 1399 00:59:08,240 --> 00:59:11,870 Un tagad mums ir jāskatās caur nešķiroti daļa masīva. 1400 00:59:11,870 --> 00:59:18,170 Tātad, šajā gadījumā tas būtu mūsu nešķirotas. 1401 00:59:18,170 --> 00:59:20,980 1402 00:59:20,980 --> 00:59:22,462 Tas ir i. 1403 00:59:22,462 --> 00:59:25,430 1404 00:59:25,430 --> 00:59:26,210 OK. 1405 00:59:26,210 --> 00:59:30,040 >> Tātad, ko mēs gatavojamies darīt būs par cilpu. 1406 00:59:30,040 --> 00:59:32,066 Ikreiz, kad jums ir nepieciešams atkārtot, izmantojot masīvu, 1407 00:59:32,066 --> 00:59:33,440 jūsu prāts varētu doties uz cilpu. 1408 00:59:33,440 --> 00:59:34,760 1409 00:59:34,760 --> 00:59:38,090 Tātad kādu int k equals-- ko mēs domājam 1410 00:59:38,090 --> 00:59:39,700 k gatavojas vienāds sākt ar? 1411 00:59:39,700 --> 00:59:41,580 1412 00:59:41,580 --> 00:59:44,766 Tas ir tas, ko mēs, kas par mūsu mazākajiem vērtība, un mēs gribam, lai salīdzinātu to. 1413 00:59:44,766 --> 00:59:47,090 Ko mēs vēlamies, lai salīdzinātu to ar? 1414 00:59:47,090 --> 00:59:48,730 Tas būs tas nākamais, vai ne? 1415 00:59:48,730 --> 00:59:53,200 Tāpēc mēs vēlamies k tiks inicializēts I plus 1, lai sāktu. 1416 00:59:53,200 --> 00:59:55,350 1417 00:59:55,350 --> 01:00:02,800 >> Un mēs gribam k šajā gadījumā mēs jau lielums saglabāti šeit, 1418 01:00:02,800 --> 01:00:03,930 tāpēc mēs varam tikai izmantot izmēru. 1419 01:00:03,930 --> 01:00:06,240 Izmērs ir izmērs masīva. 1420 01:00:06,240 --> 01:00:09,620 Un mēs vienkārši vēlamies atjaunināt k pa vienam katru reizi. 1421 01:00:09,620 --> 01:00:17,410 1422 01:00:17,410 --> 01:00:17,910 Atdzist. 1423 01:00:17,910 --> 01:00:19,650 1424 01:00:19,650 --> 01:00:23,430 Tāpēc tagad mums ir jāatrod mazākais elements šeit. 1425 01:00:23,430 --> 01:00:24,470 1426 01:00:24,470 --> 01:00:31,380 Tātad, ja mēs atkārtot, izmantojot, mēs gribu teikt, ja masīvs pie k 1427 01:00:31,380 --> 01:00:37,080 ir mazāks nekā mūsu mazāko value-- tas ir, ja mēs esam patiešām 1428 01:00:37,080 --> 01:00:42,950 sekot, kas ir mazākais here-- 1429 01:00:42,950 --> 01:00:47,740 tad mēs gribam pārdalīt ko mūsu mazākā vērtība ir. 1430 01:00:47,740 --> 01:00:50,645 >> Tas nozīmē, ka, ak, mēs atkārtojot cauri šeit. 1431 01:00:50,645 --> 01:00:51,699 1432 01:00:51,699 --> 01:00:53,740 Kāda vērtība ir šeit ir nav mūsu mazākais lieta. 1433 01:00:53,740 --> 01:00:54,448 Mēs to nevēlamies. 1434 01:00:54,448 --> 01:00:56,100 Mēs vēlamies pārdalīt to. 1435 01:00:56,100 --> 01:01:02,050 Tātad, ja mēs pārformējot, ko darīt Jūs domājat, ka varētu būt šajā kodeksā šeit? 1436 01:01:02,050 --> 01:01:04,160 Mēs vēlamies pārdalīt Mazākais un amats. 1437 01:01:04,160 --> 01:01:05,740 1438 01:01:05,740 --> 01:01:07,010 Tātad, kas ir mazākais tagad? 1439 01:01:07,010 --> 01:01:08,422 1440 01:01:08,422 --> 01:01:09,130 STUDENTU: Array k. 1441 01:01:09,130 --> 01:01:09,963 Instruktors: Array k. 1442 01:01:09,963 --> 01:01:13,480 1443 01:01:13,480 --> 01:01:15,956 Un kāda ir nostāja tagad? 1444 01:01:15,956 --> 01:01:20,940 1445 01:01:20,940 --> 01:01:23,000 Kas ir indeksi Mūsu vismazākā vērtība? 1446 01:01:23,000 --> 01:01:24,030 1447 01:01:24,030 --> 01:01:24,530 Tas ir tikai k. 1448 01:01:24,530 --> 01:01:25,690 1449 01:01:25,690 --> 01:01:27,790 Tik masīvs k, k, tie sakrīt. 1450 01:01:27,790 --> 01:01:31,670 1451 01:01:31,670 --> 01:01:33,120 Tāpēc mēs vēlējāmies pārdalīt to. 1452 01:01:33,120 --> 01:01:34,390 1453 01:01:34,390 --> 01:01:39,950 Un tad pēc tam mēs atradām mūsu mazākais, tik beigās šis cilpas 1454 01:01:39,950 --> 01:01:45,100 šeit mēs esam atraduši to, ko mūsu mazākais vērtība ir, tāpēc mēs vienkārši apmainītu to. 1455 01:01:45,100 --> 01:01:47,100 1456 01:01:47,100 --> 01:01:50,816 Šajā gadījumā, tāpat kā teikt, ka mūsu mazākā vērtība ir šeit. 1457 01:01:50,816 --> 01:01:51,940 Tas ir mūsu mazākā vērtība. 1458 01:01:51,940 --> 01:01:57,690 >> Mēs vienkārši vēlamies, lai apmainītu to šeit, kas ir ko tas mijmaiņas funkcija apakšā 1459 01:01:57,690 --> 01:02:01,270 darīja, ko mēs tikko rakstīja augšu kopā pāris minūtes atpakaļ. 1460 01:02:01,270 --> 01:02:02,775 Tāpēc tas izskatās pazīstami. 1461 01:02:02,775 --> 01:02:04,320 1462 01:02:04,320 --> 01:02:08,030 Un tad tas būs tikai atkārtot cauri, līdz tas sasniedz visu ceļu 1463 01:02:08,030 --> 01:02:13,100 līdz beigām, kas nozīmē, ka jums ir nulle elementi, kas ir nešķiroti 1464 01:02:13,100 --> 01:02:14,800 un viss pārējais ir sakārtota. 1465 01:02:14,800 --> 01:02:16,216 1466 01:02:16,216 --> 01:02:16,715 Jēga? 1467 01:02:16,715 --> 01:02:18,010 1468 01:02:18,010 --> 01:02:19,280 Nedaudz vairāk konkrētāk? 1469 01:02:19,280 --> 01:02:19,990 Kods palīdzēt? 1470 01:02:19,990 --> 01:02:21,720 1471 01:02:21,720 --> 01:02:26,410 >> STUDENTU: Par izmēru, jūs nekad tiešām definēt to vai mainīt to, 1472 01:02:26,410 --> 01:02:27,340 kā tas zina? 1473 01:02:27,340 --> 01:02:32,380 >> Instruktors: Tātad viena lieta paziņojums šeit ir int izmērs. 1474 01:02:32,380 --> 01:02:35,680 Tātad mēs esam sakot, šajā sort-- veida ir funkcija šajā case-- tas ir 1475 01:02:35,680 --> 01:02:40,770 atlase kārtot, tas ir pagājis kas ar funkciju. 1476 01:02:40,770 --> 01:02:43,460 Tātad, ja tas nav nodots in, jūs varētu darīt kaut ko 1477 01:02:43,460 --> 01:02:47,840 piemēram, ar garumu masīva vai jūs varētu atkārtot, izmantojot 1478 01:02:47,840 --> 01:02:49,390 atrast garumu. 1479 01:02:49,390 --> 01:02:52,680 Bet tāpēc, ka tas ir pagājis in, mēs varam vienkārši izmantot. 1480 01:02:52,680 --> 01:02:55,720 Jūs vienkārši pieņemt, ka lietotājs tev derīgu izmēru, kas 1481 01:02:55,720 --> 01:02:57,698 faktiski pārstāv izmērs jūsu masīvs. 1482 01:02:57,698 --> 01:02:59,461 1483 01:02:59,461 --> 01:02:59,960 Forši? 1484 01:02:59,960 --> 01:03:01,610 1485 01:03:01,610 --> 01:03:05,870 >> Ja jums puiši ir problēmas ar šīm vai vēlaties vairāk prakses kodēšanas veidu 1486 01:03:05,870 --> 01:03:08,050 par savu, jums vajadzētu doties uz study.cs50. 1487 01:03:08,050 --> 01:03:11,560 1488 01:03:11,560 --> 01:03:12,670 Tas ir instruments. 1489 01:03:12,670 --> 01:03:15,040 Viņi ir pārbaudītājs, kas jūs faktiski var rakstīt. 1490 01:03:15,040 --> 01:03:16,180 Viņi dara pseudocode. 1491 01:03:16,180 --> 01:03:19,310 Viņi ir vairāk video un diapozitīvus tostarp tiem, es izmantot šeit. 1492 01:03:19,310 --> 01:03:23,150 Tātad, ja jūs joprojām sajūta nedaudz izplūdušas, izmēģināt šo out. 1493 01:03:23,150 --> 01:03:25,670 Kā vienmēr, nāk runāt ar mani, too. 1494 01:03:25,670 --> 01:03:26,320 Jautājums? 1495 01:03:26,320 --> 01:03:28,611 >> STUDENTU: Vai Jūs sakāt lielums ir iepriekš definēti? 1496 01:03:28,611 --> 01:03:29,234 1497 01:03:29,234 --> 01:03:29,900 Instruktors: Jā. 1498 01:03:29,900 --> 01:03:35,570 Lielums ir iepriekš definēts augšu šeit funkciju deklarācijā. 1499 01:03:35,570 --> 01:03:39,060 Tātad jūs pieņemt, ka tas ir bijis pieņemts lietotājs, un vienkāršības dēļ, 1500 01:03:39,060 --> 01:03:41,896 mēs esam gatavojas pieņemt, ka lietotājs deva mums pareizo izmēru. 1501 01:03:41,896 --> 01:03:43,240 Atdzist. 1502 01:03:43,240 --> 01:03:44,390 Tā ka ir izvēle kārtošanas. 1503 01:03:44,390 --> 01:03:45,590 1504 01:03:45,590 --> 01:03:47,640 Puiši, es zinu, ka mēs esam mācīšanās daudz šodien. 1505 01:03:47,640 --> 01:03:49,710 Tas ir blīvs dati sadaļā. 1506 01:03:49,710 --> 01:03:51,880 1507 01:03:51,880 --> 01:03:57,340 Tātad ar to, ka mēs ejam doties uz ievietošanas veida. 1508 01:03:57,340 --> 01:04:01,550 1509 01:04:01,550 --> 01:04:02,510 >> OK. 1510 01:04:02,510 --> 01:04:06,100 Tātad, pirms tam mums ir jādara Mūsu runtime analīze šeit. 1511 01:04:06,100 --> 01:04:10,190 Tātad labākajā gadījumā, apmierināt, jo es jums parādīja 1512 01:04:10,190 --> 01:04:11,960 Man jau tabula veida deva to prom. 1513 01:04:11,960 --> 01:04:15,430 Bet labākajā gadījumā runtime, ko mēs domājam? 1514 01:04:15,430 --> 01:04:17,310 1515 01:04:17,310 --> 01:04:18,130 Viss sakārtots. 1516 01:04:18,130 --> 01:04:21,040 1517 01:04:21,040 --> 01:04:22,070 N brusas. 1518 01:04:22,070 --> 01:04:24,780 Kāds ir izskaidrojums kāpēc jūs domājat? 1519 01:04:24,780 --> 01:04:29,060 1520 01:04:29,060 --> 01:04:30,519 >> STUDENTU: Jūs esat salīdzinot through-- 1521 01:04:30,519 --> 01:04:31,268 Instruktors: Labais. 1522 01:04:31,268 --> 01:04:32,540 Jūs salīdzināt cauri. 1523 01:04:32,540 --> 01:04:35,630 Katrā atkārtojuma, lai gan mēs esam decrementing to ar vienu, 1524 01:04:35,630 --> 01:04:38,950 jūs joprojām meklē caur viss, lai atrastu mazāko vienu. 1525 01:04:38,950 --> 01:04:42,390 Tātad, pat ja jūsu vismazākā vērtība ir šeit sākumā, 1526 01:04:42,390 --> 01:04:44,710 jūs joprojām salīdzinot pret visu pārējo 1527 01:04:44,710 --> 01:04:46,550 lai pārliecinātos, ka tas ir mazākais lieta. 1528 01:04:46,550 --> 01:04:49,820 Tātad, jūs galu galā darbojas cauri aptuveni n kvadrātā reizes. 1529 01:04:49,820 --> 01:04:51,090 1530 01:04:51,090 --> 01:04:51,590 Labi. 1531 01:04:51,590 --> 01:04:52,785 Un, kas ir sliktākajā gadījumā? 1532 01:04:52,785 --> 01:04:54,350 1533 01:04:54,350 --> 01:04:57,980 Arī n brusas, jo jūs gatavojas lai dara, ka pati procedūra. 1534 01:04:57,980 --> 01:05:01,670 Tātad šajā gadījumā, atlasi kārtošanas ir kaut kas 1535 01:05:01,670 --> 01:05:04,010 ka mēs arī saucam paredzamā runtime. 1536 01:05:04,010 --> 01:05:07,400 Tātad citiem, mēs tikai zinām augšējās un apakšējās robežas. 1537 01:05:07,400 --> 01:05:11,180 Atkarībā no tā, cik traki mūsu saraksts ir vai cik nešķirotu tas ir, 1538 01:05:11,180 --> 01:05:15,350 tās atšķiras no n vai n rūtiņām. 1539 01:05:15,350 --> 01:05:16,550 Mēs nezinām. 1540 01:05:16,550 --> 01:05:22,820 >> Bet tāpēc, ka atlases veida ir tas pats sliktāko un labākajā gadījumā, kas stāsta mums, ka 1541 01:05:22,820 --> 01:05:25,880 Nav svarīgi, kāda ieejas veida mēs ir, vai tas ir pilnīgi 1542 01:05:25,880 --> 01:05:29,130 šķirots vai pilnībā reverse sakārtots, tas ir 1543 01:05:29,130 --> 01:05:30,740 gatavojas veikt tikpat daudz laika. 1544 01:05:30,740 --> 01:05:33,760 Tātad šajā gadījumā, ja jums atceros no mūsu galda, 1545 01:05:33,760 --> 01:05:38,610 tas tiešām bija vērtību, šie divu veidu nav, 1546 01:05:38,610 --> 01:05:40,390 kas ir sagaidāms runtime. 1547 01:05:40,390 --> 01:05:43,350 Tātad mēs zinām, ka ikreiz, kad mēs palaist atlases veida, 1548 01:05:43,350 --> 01:05:45,380 tas ir garantēta palaist n brusas laiku. 1549 01:05:45,380 --> 01:05:46,630 Nav mainīgums tur. 1550 01:05:46,630 --> 01:05:47,630 Tas ir tikai gaidāms. 1551 01:05:47,630 --> 01:05:48,820 1552 01:05:48,820 --> 01:05:52,140 Un atkal, ja jūs vēlaties, lai uzzinātu vairāk, ņem CS 124 pavasarī. 1553 01:05:52,140 --> 01:05:55,370 1554 01:05:55,370 --> 01:05:56,712 Labi. 1555 01:05:56,712 --> 01:05:57,545 Mēs esam redzējuši šo vienu. 1556 01:05:57,545 --> 01:05:58,530 1557 01:05:58,530 --> 01:05:59,030 Atdzist. 1558 01:05:59,030 --> 01:06:00,930 Tā ievietošanas kārtošanas. 1559 01:06:00,930 --> 01:06:03,330 Un es esmu, iespējams, gatavojas aizsvilties caur šo. 1560 01:06:03,330 --> 01:06:05,440 Man nebūs jūs guys kods to. 1561 01:06:05,440 --> 01:06:06,580 Mēs vienkārši staigāt pa to. 1562 01:06:06,580 --> 01:06:10,500 Tātad ievietošanas kārtošanas ir laipns no līdzīga atlases veida 1563 01:06:10,500 --> 01:06:14,460 jo mums ir gan nešķiroti un sakārtoti daļu no masīva. 1564 01:06:14,460 --> 01:06:20,260 >> Bet to, kas ir atšķirīgs ir tas, ka kā mums iet pa vienai, 1565 01:06:20,260 --> 01:06:24,210 mēs vienkārši veikt neatkarīgi numurs ir nākamais mūsu nešķiroti, 1566 01:06:24,210 --> 01:06:28,507 un pareizi šķirot to mūsu šķirotiem masīvs. 1567 01:06:28,507 --> 01:06:30,090 Tas būs daudz lietderīgāk ar piemēru. 1568 01:06:30,090 --> 01:06:31,140 1569 01:06:31,140 --> 01:06:35,430 Tātad viss sākas kā nešķirotu, tāpat kā ar atlases veida. 1570 01:06:35,430 --> 01:06:38,740 Un mēs ejam, lai sakārtotu šo augošā secībā kā mēs esam bijuši. 1571 01:06:38,740 --> 01:06:40,360 1572 01:06:40,360 --> 01:06:43,340 Tātad mūsu pirmā loka mēs uzņemtu pirmo vērtību 1573 01:06:43,340 --> 01:06:46,700 un mēs sakām, OK, jūs esat Tagad sarakstā ar sevi. 1574 01:06:46,700 --> 01:06:49,150 >> Jo jums ir sarakstā ar sevi, jums ir sakārtoti. 1575 01:06:49,150 --> 01:06:52,460 Apsveicam ir Pirmais elements šajā masīvā. 1576 01:06:52,460 --> 01:06:54,800 Jūs jau sakārtoti visu par savu. 1577 01:06:54,800 --> 01:06:58,900 Tāpēc tagad mums ir sakārtoti un nešķirotas masīvs. 1578 01:06:58,900 --> 01:07:01,760 Tāpēc tagad mēs pirmo reizi. 1579 01:07:01,760 --> 01:07:05,600 Kas notiek starp šeit un šeit ir tas, ka mēs sakām, 1580 01:07:05,600 --> 01:07:08,890 Labi, mēs ejam apskatīt Pirmā vērtība mūsu nešķirotos masīva 1581 01:07:08,890 --> 01:07:13,270 un mēs braucam, lai ievadītu to tās pareiza vieta šķirotas masīvā. 1582 01:07:13,270 --> 01:07:21,460 >> Tātad, ko mēs darām, ir mēs 5 un mēs sakām, OK, 5 ir lielāka par 3, 1583 01:07:21,460 --> 01:07:24,630 tāpēc mēs vienkārši ievietojiet to tiesības pa labi no tā. 1584 01:07:24,630 --> 01:07:25,130 Mēs esam labi. 1585 01:07:25,130 --> 01:07:26,200 1586 01:07:26,200 --> 01:07:28,420 Tātad, tad mēs ejam uz mūsu nākamo. 1587 01:07:28,420 --> 01:07:29,720 Un mēs 2. 1588 01:07:29,720 --> 01:07:34,330 Mēs sakām, OK, 2 ir mazāk par 3, tāpēc mēs zinām, ka tā 1589 01:07:34,330 --> 01:07:36,220 jābūt pie priekšā mūsu sarakstā tagad. 1590 01:07:36,220 --> 01:07:41,800 Tātad, ko mēs darām, ir mēs push 3. un 5. leju un mēs virzāmies 2 vērā, ka pirmajā slotā. 1591 01:07:41,800 --> 01:07:42,990 1592 01:07:42,990 --> 01:07:45,870 Tātad mēs esam tikai tā ievietošanas pareizajā vietā, tam vajadzētu būt. 1593 01:07:45,870 --> 01:07:46,960 1594 01:07:46,960 --> 01:07:49,470 >> Tad mēs skatāmies mūsu nākamais, un mēs sakām 6. 1595 01:07:49,470 --> 01:07:53,620 OK, 6 ir lielāks nekā viss mūsu šķirotas masīvā, 1596 01:07:53,620 --> 01:07:56,000 tāpēc mēs vienkārši trāpi uz beigām. 1597 01:07:56,000 --> 01:07:56,960 Un tad mēs skatāmies 4. 1598 01:07:56,960 --> 01:07:58,130 1599 01:07:58,130 --> 01:08:03,020 4, ir mazāka par 6, tas ir mazāk par 5, bet tas ir lielāks par 3. 1600 01:08:03,020 --> 01:08:06,270 Tātad mēs vienkārši ievietojiet to labi vidū starp 3 un 5. 1601 01:08:06,270 --> 01:08:07,380 1602 01:08:07,380 --> 01:08:10,530 Tāpēc, lai padarītu ka nedaudz nedaudz vairāk betona, 1603 01:08:10,530 --> 01:08:12,280 šeit ir sava veida ideja par to, kas noticis. 1604 01:08:12,280 --> 01:08:16,430 Tātad katram nešķirotiem elementu, mēs noteikt, kur šajā šķirotas daļu 1605 01:08:16,430 --> 01:08:17,090 tas ir. 1606 01:08:17,090 --> 01:08:20,680 >> Tātad, paturot prātā, ka šķiroti un nešķiroti, 1607 01:08:20,680 --> 01:08:26,080 mums ir traversa cauri un skaitlis , kur tas iederas šķirotas masīvā. 1608 01:08:26,080 --> 01:08:31,460 Un mēs ievietojiet to novirzot elementi, pa labi no tā uz leju. 1609 01:08:31,460 --> 01:08:34,910 Un tad mēs tikai glabāt atkārtojot caur kamēr mēs 1610 01:08:34,910 --> 01:08:39,270 ir pilnīgi sakārtoti sarakstu kur šķirotas tagad ir nulle 1611 01:08:39,270 --> 01:08:41,720 un šķiroto aizņem veselums mūsu sarakstā. 1612 01:08:41,720 --> 01:08:43,146 1613 01:08:43,146 --> 01:08:45,854 Tātad, atkal, lai padarītu lietas vēl vairāk betona, mums ir pseudocode. 1614 01:08:45,854 --> 01:08:47,979 1615 01:08:47,979 --> 01:08:52,410 >> Tātad būtībā par i ir ir vienāds ar 0 līdz n mīnus 1, 1616 01:08:52,410 --> 01:08:54,790 tas ir tikai garums mūsu masīvs. 1617 01:08:54,790 --> 01:09:00,979 Mums ir kāds elements, kas ir vienāda ar Pirmais masīvs vai pirmie indeksi. 1618 01:09:00,979 --> 01:09:03,200 Mēs, kas j, kas ir līdzvērtīga. 1619 01:09:03,200 --> 01:09:04,649 1620 01:09:04,649 --> 01:09:09,210 Tātad, kamēr j ir lielāks nekā nulle un masīvs, j mīnus 1 1621 01:09:09,210 --> 01:09:11,660 ir lielāks nekā elements, lai visi, kas dara 1622 01:09:11,660 --> 01:09:17,479 ir pārliecināties, ka Jūsu j tiešām pārstāv 1623 01:09:17,479 --> 01:09:20,010 nešķiroti daļa masīva. 1624 01:09:20,010 --> 01:09:30,745 >> Tāpēc, kamēr vēl ir lietas, kārtot un j mīnus viens is-- ko 1625 01:09:30,745 --> 01:09:31,840 ir elements viņas? 1626 01:09:31,840 --> 01:09:34,760 J nekad netika šeit definēts. 1627 01:09:34,760 --> 01:09:35,677 Tas ir sava veida kaitinošas. 1628 01:09:35,677 --> 01:09:36,176 OK. 1629 01:09:36,176 --> 01:09:36,689 Anyways. 1630 01:09:36,689 --> 01:09:39,899 Tātad j mīnus 1, jūs pārbaudīt elements pirms tā. 1631 01:09:39,899 --> 01:09:46,460 Jūs sakāt, OK, ir elements Pirms kur es am-- pieņemsim 1632 01:09:46,460 --> 01:09:47,540 faktiski izdarīt šo out. 1633 01:09:47,540 --> 01:09:52,580 1634 01:09:52,580 --> 01:09:56,830 Tātad, teiksim, tas ir piemēram, par mūsu otro caurlaide. 1635 01:09:56,830 --> 01:09:59,525 Tāpēc es būs vienāds 1, kas ir šeit. 1636 01:09:59,525 --> 01:10:03,310 1637 01:10:03,310 --> 01:10:06,025 >> Tāpēc es būs vienāds ar 1. 1638 01:10:06,025 --> 01:10:09,510 1639 01:10:09,510 --> 01:10:13,702 Tas ir 2, 4, 5, 6, 7. 1640 01:10:13,702 --> 01:10:16,060 1641 01:10:16,060 --> 01:10:16,750 Labi. 1642 01:10:16,750 --> 01:10:20,945 Tātad, mūsu elements, kas šajā gadījumā būs vienāds ar 4. 1643 01:10:20,945 --> 01:10:22,110 1644 01:10:22,110 --> 01:10:24,946 Un mums ir dažas J, kas ir būs vienāds ar 1. 1645 01:10:24,946 --> 01:10:29,770 1646 01:10:29,770 --> 01:10:30,971 Ak, j ir decrementing. 1647 01:10:30,971 --> 01:10:31,720 Ka tas, ko tas ir. 1648 01:10:31,720 --> 01:10:35,680 Tātad, j ir vienāds ar i, lai to, ko tas ir teiciens ir, ka mēs virzāmies uz priekšu, 1649 01:10:35,680 --> 01:10:37,530 mēs esam tikai pārliecinoties ka mēs esam nav beigusies 1650 01:10:37,530 --> 01:10:43,520 indeksējot šādā veidā, kad mēs cenšamies ievietot lietas mūsu sakārtoti sarakstā. 1651 01:10:43,520 --> 01:10:49,850 >> Tātad, ja j ir vienāds ar 1, šajā gadījumā un masīvs j mīnus one-- tāpēc masīvs j mīnus 1 1652 01:10:49,850 --> 01:10:54,610 ir 2 Šajā case--, ja tas ir lielāks nekā elements, 1653 01:10:54,610 --> 01:10:57,700 tad tas viss dara mainās lietas leju. 1654 01:10:57,700 --> 01:11:04,790 Tātad šajā gadījumā, masīvs j mīnus viens būtu masīvs nulle, kas ir 2. 1655 01:11:04,790 --> 01:11:08,430 2, ir ne lielāks par 4, tāpēc tas neveic. 1656 01:11:08,430 --> 01:11:11,460 Tāpēc pāreja nav uz leju. 1657 01:11:11,460 --> 01:11:18,790 Kas tas šeit ir tikai pārvietot savu sakārtoti masīvs leju. 1658 01:11:18,790 --> 01:11:22,340 1659 01:11:22,340 --> 01:11:26,400 Šajā gadījumā, faktiski, mēs varētu do-- pieņemsim padara šo 3. 1660 01:11:26,400 --> 01:11:28,080 1661 01:11:28,080 --> 01:11:31,970 Tātad, ja mēs esam staigāt cauri ar šis piemērs, mēs esam tagad šeit. 1662 01:11:31,970 --> 01:11:32,740 Tas ir sakārtots. 1663 01:11:32,740 --> 01:11:34,492 1664 01:11:34,492 --> 01:11:35,200 Tas ir nešķirotas. 1665 01:11:35,200 --> 01:11:39,090 1666 01:11:39,090 --> 01:11:39,860 Forši? 1667 01:11:39,860 --> 01:11:46,620 Tātad, i ir vienāds ar 2, lai Mūsu elements ir vienāds ar 3. 1668 01:11:46,620 --> 01:11:47,920 1669 01:11:47,920 --> 01:11:52,270 Un mūsu j ir vienāds ar 2. 1670 01:11:52,270 --> 01:12:00,620 Tātad mēs skatāmies caur un mēs saka, OK, ir masīvs j mīnus viens 1671 01:12:00,620 --> 01:12:03,470 lielāks nekā elements ka mēs meklējam? 1672 01:12:03,470 --> 01:12:05,540 Un atbilde ir jā, vai ne? 1673 01:12:05,540 --> 01:12:11,275 4 ir lielāka par 3 un j ir 2, lai šis kods izpilda. 1674 01:12:11,275 --> 01:12:12,510 1675 01:12:12,510 --> 01:12:18,550 >> Tāpēc tagad, ko mēs darām masīvs at 2, tāpēc tieši šeit, mēs mijmaiņas tiem. 1676 01:12:18,550 --> 01:12:25,620 Tātad mēs tikai teikt, OK, masīvs pie 2 tagad būs 3. 1677 01:12:25,620 --> 01:12:28,130 1678 01:12:28,130 --> 01:12:32,340 Un j gatavojas vienāds j mīnus 1, kas ir 1. 1679 01:12:32,340 --> 01:12:34,590 1680 01:12:34,590 --> 01:12:37,200 Tas ir briesmīgs, bet jūs guys saņemsiet ideja. 1681 01:12:37,200 --> 01:12:38,360 J tagad ir vienāds ar 1. 1682 01:12:38,360 --> 01:12:44,360 Un masīvs j ir tikai būs vienāda ar mūsu elementu, kas bija 4. 1683 01:12:44,360 --> 01:12:45,950 1684 01:12:45,950 --> 01:12:48,570 Es izdzēsti kaut man nevajadzētu ir vai miswrote kaut ko, 1685 01:12:48,570 --> 01:12:49,910 bet jūs guys ideja. 1686 01:12:49,910 --> 01:12:50,640 >> Tā kustēties n. 1687 01:12:50,640 --> 01:12:51,920 1688 01:12:51,920 --> 01:12:57,960 Un tad, ja tas tā būtu, tas būtu cilpa atkal un tā teiktu, OK, j ir 1 tagad. 1689 01:12:57,960 --> 01:13:00,665 Un masīvs j mīnus 1 tagad ir 2. 1690 01:13:00,665 --> 01:13:01,750 1691 01:13:01,750 --> 01:13:03,760 Ir par 2 mazāk nekā mūsu elements? 1692 01:13:03,760 --> 01:13:04,540 Nē? 1693 01:13:04,540 --> 01:13:07,970 Tas nozīmē, ka mēs esam ievietota šo elementu 1694 01:13:07,970 --> 01:13:10,110 pareizajā vietas mūsu šķirotiem masīvs. 1695 01:13:10,110 --> 01:13:14,400 Tad mēs varam pieņemt to, un mēs sakām, Labi, mūsu sakārtots masīvs ir šeit. 1696 01:13:14,400 --> 01:13:19,940 Un tas būtu nepieciešams šo numuru 6 un jābūt piemēram, OK, ir 6 mazāks nekā šo numuru? 1697 01:13:19,940 --> 01:13:20,480 Nē? 1698 01:13:20,480 --> 01:13:21,080 Atdzist. 1699 01:13:21,080 --> 01:13:22,680 Mēs esam labi. 1700 01:13:22,680 --> 01:13:23,530 >> Darīt to vēlreiz. 1701 01:13:23,530 --> 01:13:24,740 Mēs sakām 7. 1702 01:13:24,740 --> 01:13:29,010 Ir 7 mazāk nekā beigās Mūsu šķirotas masīva? 1703 01:13:29,010 --> 01:13:29,520 Nē. 1704 01:13:29,520 --> 01:13:30,430 Tātad mēs esam labi. 1705 01:13:30,430 --> 01:13:32,760 Tātad tas būtu sakārtoti. 1706 01:13:32,760 --> 01:13:38,610 Būtībā tas viss dara tas ir saprotams pārņemšanu 1707 01:13:38,610 --> 01:13:42,060 no pirmā elementa Jūsu nešķiroti masīvs, 1708 01:13:42,060 --> 01:13:46,010 izdomāt, kur tas notiek Jūsu šķirotiem masīvs. 1709 01:13:46,010 --> 01:13:48,780 Un tas tikai rūpējas mijmaiņas darījumu, lai to izdarītu. 1710 01:13:48,780 --> 01:13:51,300 Jūs būtībā vienkārši pārnešana līdz brīdim, kad tas ir īstajā vietā. 1711 01:13:51,300 --> 01:13:53,600 1712 01:13:53,600 --> 01:13:56,990 Vizuālais tēls ir tas, ka tu esi virzās viss uz leju, darot to. 1713 01:13:56,990 --> 01:13:59,420 >> Tātad, tas ir tāpat kā pusi burbulis šķirot-esque. 1714 01:13:59,420 --> 01:14:02,280 1715 01:14:02,280 --> 01:14:03,420 Pārbaudiet pētījumu 50. 1716 01:14:03,420 --> 01:14:06,000 Es ļoti ieteiktu mēģināt kodēt šo par savu. 1717 01:14:06,000 --> 01:14:07,220 1718 01:14:07,220 --> 01:14:12,450 Ja jums ir kādi jautājumi vai vēlaties sk parauga kodu par ievietošanas veida, 1719 01:14:12,450 --> 01:14:13,750 lūdzu, ļaujiet man zināt. 1720 01:14:13,750 --> 01:14:14,500 Es esmu vienmēr apkārt. 1721 01:14:14,500 --> 01:14:16,600 1722 01:14:16,600 --> 01:14:20,200 Tātad sliktākajā gadījumā runtime un labākajā gadījumā runtime. 1723 01:14:20,200 --> 01:14:30,700 Kā jūs puisis redzēja no galda man jau parādīja, jums, tas ir gan n brusas un n. 1724 01:14:30,700 --> 01:14:35,590 >> Tā veida iet nost no tā, ko mēs runājām aptuveni ar mūsu iepriekšējiem veidu, sliktākajā 1725 01:14:35,590 --> 01:14:38,760 lieta runtime ir tas, ka tad, ja tas ir pilnīgi Nesašķirotas, 1726 01:14:38,760 --> 01:14:42,530 mums ir salīdzināt visus šos n reizes. 1727 01:14:42,530 --> 01:14:47,020 Mēs darām visu daudz salīdzinājumu jo, ja tas ir apgrieztā secībā, 1728 01:14:47,020 --> 01:14:50,360 mēs ejam teikt, OK, šis ir tas pats, tas ir labi, 1729 01:14:50,360 --> 01:14:54,650 un tas viens būs jāsalīdzina pret pirmo, lai tiktu pārvietots atpakaļ. 1730 01:14:54,650 --> 01:14:56,710 Un, kā mēs pret astes gals, mums ir 1731 01:14:56,710 --> 01:14:59,440 salīdzināt, salīdzināt, un salīdzināt pret visu. 1732 01:14:59,440 --> 01:15:03,030 >> Tātad tas beidzas ar to, aptuveni n brusas. 1733 01:15:03,030 --> 01:15:09,510 Ja tas ir pareizs, tad jūs saka, OK, 2, jūs labi. 1734 01:15:09,510 --> 01:15:11,330 3, jūs, salīdzinot ar 2. 1735 01:15:11,330 --> 01:15:12,310 Jūs labi. 1736 01:15:12,310 --> 01:15:14,150 4, jūs vienkārši salīdzināt ar asti. 1737 01:15:14,150 --> 01:15:14,990 Jūs labi. 1738 01:15:14,990 --> 01:15:17,140 6, salīdzināt ar astes, jūs esat labi. 1739 01:15:17,140 --> 01:15:20,870 Tātad katru vietas, ja tas ir jau šķirots, jūs gūstat vienu salīdzinājumu. 1740 01:15:20,870 --> 01:15:22,320 Tāpēc tas ir tikai n. 1741 01:15:22,320 --> 01:15:26,840 Un tāpēc mums ir labākajā gadījumā runtime N un vissliktākajām Runtime n 1742 01:15:26,840 --> 01:15:28,680 brusas, mums nav gaidīto runtime. 1743 01:15:28,680 --> 01:15:31,290 1744 01:15:31,290 --> 01:15:34,020 >> Tas tikai atkarīgs haoss mūsu sarakstā tur. 1745 01:15:34,020 --> 01:15:35,860 1746 01:15:35,860 --> 01:15:39,530 Un atkal, cits grafiku un citā tabulā. 1747 01:15:39,530 --> 01:15:41,170 Tāpēc atšķirības starp veidu. 1748 01:15:41,170 --> 01:15:44,180 Es esmu tikai gatavojas brīze cauri, es justies kā mēs esam plaši runājuši 1749 01:15:44,180 --> 01:15:46,570 par to, kā viņi visu veidu no atšķiras un saistīt kopā. 1750 01:15:46,570 --> 01:15:50,564 Tātad apvienot kārtošanas ir pēdējais Es nesa jums puiši ar. 1751 01:15:50,564 --> 01:15:52,105 Mums ir diezgan krāsainu attēlu. 1752 01:15:52,105 --> 01:15:53,860 1753 01:15:53,860 --> 01:15:56,040 Tātad apvienot kārtošanas ir rekursīvs algoritms. 1754 01:15:56,040 --> 01:15:59,910 Tātad jūs guys zināt, ko rekursīvs funkcija ir? 1755 01:15:59,910 --> 01:16:01,550 1756 01:16:01,550 --> 01:16:03,320 >> Ikviens grib teikt? 1757 01:16:03,320 --> 01:16:04,739 Vēlaties izmēģināt? 1758 01:16:04,739 --> 01:16:07,280 Tātad rekursīvo funkcija ir tikai funkcija, kas sevi dēvē. 1759 01:16:07,280 --> 01:16:08,570 1760 01:16:08,570 --> 01:16:11,590 Tātad, ja jūs puiši ir pazīstami ar Fibonači secība, 1761 01:16:11,590 --> 01:16:15,670 kas ir uzskatāms rekursīvs jo Jūs lietojat iepriekšējo divu 1762 01:16:15,670 --> 01:16:17,530 un pievienot tos kopā lai saņemtu savu nākamo. 1763 01:16:17,530 --> 01:16:21,440 Tātad rekursīvs, es vienmēr domāju, ka no recursion kā, piemēram, spirāli 1764 01:16:21,440 --> 01:16:24,430 lai jūs, piemēram, spirāli uz leju tajā. 1765 01:16:24,430 --> 01:16:27,150 Bet tas ir tikai funkcija kas sevi dēvē. 1766 01:16:27,150 --> 01:16:32,660 >> Un, patiesībā, ļoti ātri es var parādīt, ko tas izskatās. 1767 01:16:32,660 --> 01:16:34,260 1768 01:16:34,260 --> 01:16:41,840 Tātad rekursīvs šeit, ja mēs skatāmies, tas ir rekursīvs veids Apkopojot pār masīvu. 1769 01:16:41,840 --> 01:16:45,900 1770 01:16:45,900 --> 01:16:47,880 Tātad viss, kas mums jādara, ir mums ir summa funkcija 1771 01:16:47,880 --> 01:16:52,210 summa, kas ņem izmēru un masīvs. 1772 01:16:52,210 --> 01:16:55,210 Un, ja pamanāt, izmērs samazinājumi pa vienam katru reizi. 1773 01:16:55,210 --> 01:17:00,365 Un viss, tas ir, ja x ir vienāds ar zero-- tādēļ, ja izmērs masīva 1774 01:17:00,365 --> 01:17:02,710 ir vienāds ar zero-- tas atgriež nulli. 1775 01:17:02,710 --> 01:17:10,440 >> Pretējā gadījumā tas rezumē šo masīva pēdējais elements, 1776 01:17:10,440 --> 01:17:14,790 un tad ņem summu pārējā masīva. 1777 01:17:14,790 --> 01:17:17,555 Tātad tas ir tikai laužot to uz leju mazākās un mazākās problēmas. 1778 01:17:17,555 --> 01:17:18,990 1779 01:17:18,990 --> 01:17:21,890 Garš stāsts īss, rekursijas, funkcija, kas sevi dēvē. 1780 01:17:21,890 --> 01:17:25,740 Ja tas viss jums no šīs, tas ko rekursīvs funkcija. 1781 01:17:25,740 --> 01:17:29,870 Ja esat lietojis 51, jūs saņemsiet ļoti, ļoti apmierināti ar recursion. 1782 01:17:29,870 --> 01:17:31,110 1783 01:17:31,110 --> 01:17:32,370 Tas ir patiešām foršs. 1784 01:17:32,370 --> 01:17:34,660 Tajā bija jēga, piemēram, 03:00 viena nakts. 1785 01:17:34,660 --> 01:17:37,900 Un man bija, piemēram, kāpēc es neesmu nekad izmantot šo? 1786 01:17:37,900 --> 01:17:39,170 1787 01:17:39,170 --> 01:17:42,430 >> Tātad sapludināšanas kārtošanas, būtībā ko tā gatavojas darīt, ir tā 1788 01:17:42,430 --> 01:17:45,620 gatavojas lauzt to uz leju, un lauzt to uz leju, līdz tas ir tikai atsevišķus elementus. 1789 01:17:45,620 --> 01:17:47,570 Atsevišķus elementus ir viegli sakārtot. 1790 01:17:47,570 --> 01:17:48,070 Mēs redzam, ka. 1791 01:17:48,070 --> 01:17:50,760 Ja jums ir viens elements, tas ir jau uzskatīja sakārtots. 1792 01:17:50,760 --> 01:17:53,800 Tā tālāk ieejā n elementiem, ja n ir mazāks par 2, 1793 01:17:53,800 --> 01:17:58,120 vienkārši atgriezties jo tas nozīmē, tas ir vai nu 0 vai 1, kā mēs esam redzējuši. 1794 01:17:58,120 --> 01:18:00,050 Tie tiek uzskatīti šķirotas elementi. 1795 01:18:00,050 --> 01:18:02,170 >> Pretējā lauzt to pusi. 1796 01:18:02,170 --> 01:18:06,336 Kārtot pirmo pusgadu, šķirot otrā puse, un pēc tam apvienot tos kopā. 1797 01:18:06,336 --> 01:18:07,460 Kāpēc to sauc sapludināšanas kārtošanas. 1798 01:18:07,460 --> 01:18:08,700 1799 01:18:08,700 --> 01:18:12,155 Tāpēc mēs esam šeit mēs sakārtotu šos. 1800 01:18:12,155 --> 01:18:13,410 1801 01:18:13,410 --> 01:18:17,210 Tāpēc mēs turpinām viņus līdz masīva izmērs ir 1. 1802 01:18:17,210 --> 01:18:20,790 Tad, kad tas ir 1, mēs vienkārši atgriezties jo tas ir sakārtots masīvs, 1803 01:18:20,790 --> 01:18:23,940 un tas ir sakārtots masīvs, un tas ir sakārtots masīvs, mēs visi sakārtots. 1804 01:18:23,940 --> 01:18:25,390 1805 01:18:25,390 --> 01:18:29,420 Tātad, ko mēs darām, ir mums sākt apvienojot tos kopā. 1806 01:18:29,420 --> 01:18:31,820 >> Tātad, kā jūs varat domāt par apvienošanu ir 1807 01:18:31,820 --> 01:18:36,240 jūs vienkārši izņemt mazāks skaits katrai no apakšprogrammām bloki 1808 01:18:36,240 --> 01:18:38,330 un vienkārši pievienot to parādījās masīvs. 1809 01:18:38,330 --> 01:18:44,290 Tātad, ja paskatās šeit, kad mums ir šie komplekti mums ir 4, 6, un 1. 1810 01:18:44,290 --> 01:18:47,280 Kad mēs vēlamies apvienot tos, mēs skatāmies uz šiem pirmajiem diviem 1811 01:18:47,280 --> 01:18:50,730 un mēs sakām, OK, 1 ir mazāks, tā iet uz priekšu. 1812 01:18:50,730 --> 01:18:54,330 4 un 6, tur nekas, lai salīdzinātu to, vienkārši trāpi uz beigām. 1813 01:18:54,330 --> 01:18:58,020 >> Kad mēs apvienot šos divus, mēs vienkārši ņem mazāko no šīm divām, 1814 01:18:58,020 --> 01:18:59,310 tāpēc tas ir 1. 1815 01:18:59,310 --> 01:19:01,690 Un tagad mēs mazāko no šīm divām, SO2. 1816 01:19:01,690 --> 01:19:03,330 Mazāko no šiem diviem, 3. 1817 01:19:03,330 --> 01:19:06,260 Mazāko no šīm divām, 4., 5., 6. 1818 01:19:06,260 --> 01:19:08,630 Tātad jūs vienkārši novelkot tiem. 1819 01:19:08,630 --> 01:19:11,210 Un tāpēc, ka tie esam iepriekš sašķiroti, 1820 01:19:11,210 --> 01:19:14,300 Jums vienkārši ir viens salīdzinājums katru reizi tur. 1821 01:19:14,300 --> 01:19:19,610 Tātad vairāk kodu šeit, tikai pārstāvība. 1822 01:19:19,610 --> 01:19:24,410 Tātad, jūs sākat vidū un kārtot pa kreisi un pa labi 1823 01:19:24,410 --> 01:19:26,180 un tad jūs vienkārši apvienot tos. 1824 01:19:26,180 --> 01:19:30,080 >> Un mums nav kodu par apvienot tieši šeit. 1825 01:19:30,080 --> 01:19:34,110 Bet, atkal, ja jums iet tālāk studēt 50, tas būs tur. 1826 01:19:34,110 --> 01:19:36,860 Pretējā nāk runāt ar mani ja jūs joprojām sajaukt. 1827 01:19:36,860 --> 01:19:42,340 Tik foršs lieta šeit ir tas, ka labākajā gadījumā, sliktākajā gadījumā, un sagaidāms runtime 1828 01:19:42,340 --> 01:19:46,250 ir visas log n, kas ir daudz labāk, nekā mēs esam 1829 01:19:46,250 --> 01:19:48,000 uzskatīta par pārējo mūsu veidu. 1830 01:19:48,000 --> 01:19:51,840 Mēs esam redzējuši n kvadrātā un ko mēs patiesībā 1831 01:19:51,840 --> 01:19:54,380 nokļūt ir n log n, kas ir lieliski. 1832 01:19:54,380 --> 01:19:55,830 >> Paskaties, cik daudz labāk tas ir. 1833 01:19:55,830 --> 01:19:56,780 Šāds jauka līkni. 1834 01:19:56,780 --> 01:19:58,130 1835 01:19:58,130 --> 01:20:00,120 Tik daudz efektīvāku. 1836 01:20:00,120 --> 01:20:03,510 Ja jūs kādreiz iespējams, izmantot apvienot kārtošanas. 1837 01:20:03,510 --> 01:20:04,810 Tas ietaupīs jūsu laiku. 1838 01:20:04,810 --> 01:20:07,670 Tad atkal, kā mēs teicām, ja jūs uz leju šajā apakšējā reģionā, 1839 01:20:07,670 --> 01:20:09,480 tas nenozīmē, ka uzņēmums daudz atšķirību. 1840 01:20:09,480 --> 01:20:11,360 Jums līdz tūkstošiem un tūkstošiem ieejas, 1841 01:20:11,360 --> 01:20:13,318 Jūs noteikti vēlaties efektīvāku algoritmu. 1842 01:20:13,318 --> 01:20:14,730 1843 01:20:14,730 --> 01:20:19,400 Un atkal, mūsu skaisto tabula visu veidu, ka jūs puiši šodien iemācījušies. 1844 01:20:19,400 --> 01:20:21,157 >> Tāpēc es zinu, tas ir bijis blīvs dienā. 1845 01:20:21,157 --> 01:20:23,490 Tas ne vienmēr notiek lai palīdzētu jums ar savu PSET. 1846 01:20:23,490 --> 01:20:28,250 Bet es tikai gribu, lai atruna šī sadaļa ir ne tikai par psets. 1847 01:20:28,250 --> 01:20:31,240 Viss šis materiāls ir godīgi spēle jūsu midterms. 1848 01:20:31,240 --> 01:20:35,430 Un arī tad, ja jūs turpināt ar CS, Tie ir patiešām svarīgi pamati 1849 01:20:35,430 --> 01:20:37,870 kas jums būtu jāzina. 1850 01:20:37,870 --> 01:20:41,700 Tātad, dažas dienas būs nedaudz vairāk PSET palīdzība, 1851 01:20:41,700 --> 01:20:44,600 bet dažas nedēļas būs daudz faktiskais saturs 1852 01:20:44,600 --> 01:20:46,600 ka var nelikties super noderīga, lai jūs tieši tagad, 1853 01:20:46,600 --> 01:20:51,215 bet es apsolu, ja jūs turpināt gada būs ļoti, ļoti noderīgs. 1854 01:20:51,215 --> 01:20:52,560 1855 01:20:52,560 --> 01:20:54,250 >> Tā ka ir to sadaļā. 1856 01:20:54,250 --> 01:20:55,250 Leju, lai vadu. 1857 01:20:55,250 --> 01:20:56,570 Es to darīju vienas minūtes laikā. 1858 01:20:56,570 --> 01:20:58,262 1859 01:20:58,262 --> 01:20:58,970 Bet tur jums iet. 1860 01:20:58,970 --> 01:21:01,240 Un man būs virtuļus vai konfektes. 1861 01:21:01,240 --> 01:21:03,464 Vai kāds ir alerģija pret kaut ko, starp citu? 1862 01:21:03,464 --> 01:21:05,307 1863 01:21:05,307 --> 01:21:05,890 Olas un piens. 1864 01:21:05,890 --> 01:21:08,120 Tātad donuts ir nē? 1865 01:21:08,120 --> 01:21:09,400 1866 01:21:09,400 --> 01:21:10,160 OK. 1867 01:21:10,160 --> 01:21:10,770 Labi. 1868 01:21:10,770 --> 01:21:12,120 Šokolādes nē? 1869 01:21:12,120 --> 01:21:12,620 Zvaigžņu dzimšanas. 1870 01:21:12,620 --> 01:21:13,837 1871 01:21:13,837 --> 01:21:14,670 Starbursts ir labi. 1872 01:21:14,670 --> 01:21:15,170 OK. 1873 01:21:15,170 --> 01:21:17,045 Mēs ejam, lai būtu Starburst nākamnedēļ tad. 1874 01:21:17,045 --> 01:21:18,240 Tas ir tas, ko es nopirkšu. 1875 01:21:18,240 --> 01:21:19,690 Jums puiši ir lieliska nedēļa. 1876 01:21:19,690 --> 01:21:20,460 Lasīt jūsu spec. 1877 01:21:20,460 --> 01:21:22,130 >> Let me know, ja jums ir kādi jautājumi. 1878 01:21:22,130 --> 01:21:25,300 PSET divas pakāpes būtu kas jums ar ceturtdien. 1879 01:21:25,300 --> 01:21:28,320 Ja jums ir kādi jautājumi par to, kā es kaut ko šķiro 1880 01:21:28,320 --> 01:21:32,250 vai kāpēc es šķiro kaut kā es tomēr, lūdzu, rakstiet man, nāc ar mani runāt. 1881 01:21:32,250 --> 01:21:34,210 Es esmu mazliet traks tas nedēļā, bet es apsolu 1882 01:21:34,210 --> 01:21:36,340 Es joprojām būs atbildēsim 24 stundu laikā. 1883 01:21:36,340 --> 01:21:38,240 Tā ir lieliska nedēļu, ikvienam. 1884 01:21:38,240 --> 01:21:40,090 Good luck par savu PSET. 1885 01:21:40,090 --> 01:21:41,248