1 00:00:00,000 --> 00:00:03,332 >> [Prehrávanie hudby] 2 00:00:03,332 --> 00:00:06,490 >> ANDI PENG: Vitajte na týždeň 3 oddielu. 3 00:00:06,490 --> 00:00:09,550 Vďaka, chlapci, pre všetky prichádzajúce do tohto skoršieho štartu čas dnes. 4 00:00:09,550 --> 00:00:11,466 Máme pekný, malý intímne skupina dnes. 5 00:00:11,466 --> 00:00:14,570 Takže dúfajme, že sa dostaneme povrch, možno skoro, 6 00:00:14,570 --> 00:00:15,780 trochu brzo dnes. 7 00:00:15,780 --> 00:00:22,057 Tak rýchlo, len niektoré Oznámenia pre relácie dnešného dňa. 8 00:00:22,057 --> 00:00:23,890 Než začneme, my sme bude jednoducho ísť cez 9 00:00:23,890 --> 00:00:28,910 niekoľko krátkych logistické problémy, pset Otázky, Rozprava, také veci. 10 00:00:28,910 --> 00:00:30,250 A potom budeme ponor priamo. 11 00:00:30,250 --> 00:00:34,710 Budeme používať debugger s názvom GDB na začať odhaľovať náš kód, ktorý David 12 00:00:34,710 --> 00:00:36,550 vysvetlené v prednáške na druhý deň. 13 00:00:36,550 --> 00:00:39,420 Pôjdeme cez štyri typy druhov. 14 00:00:39,420 --> 00:00:42,310 Pôjdeme cez ne celkom rýchlo pretože sú to celkom náročné. 15 00:00:42,310 --> 00:00:45,710 Ale viem, že všetky snímky a Zdrojový kód je vždy on-line. 16 00:00:45,710 --> 00:00:50,810 Tak neváhajte, vo Vašom prečítaniu, aby vrátiť a pozrieť sa na to. 17 00:00:50,810 --> 00:00:53,930 >> Prejdeme asymptotickej notácie, ktorý 18 00:00:53,930 --> 00:00:55,944 je len ozdobný spôsob, ako hovoriť "runtime" 19 00:00:55,944 --> 00:00:58,360 kde máme veľký O, ktorý David je vysvetlené v prednáške. 20 00:00:58,360 --> 00:01:01,550 A máme aj Omega, ktorý je dolná hranica runtime. 21 00:01:01,550 --> 00:01:06,450 A budeme hovoriť trochu viac do hĺbky o tom, ako tieto práce. 22 00:01:06,450 --> 00:01:10,160 A konečne, pôjdeme cez binárne vyhľadávanie, pretože mnoho z vás, ktorí už 23 00:01:10,160 --> 00:01:15,190 Pozrel sa na svoje psets pravdepodobne viete, že to je otázka, ktorá je vo vašej pset. 24 00:01:15,190 --> 00:01:17,470 Takže budete všetci radi že budeme rozprávať to dnes. 25 00:01:17,470 --> 00:01:20,610 >> A konečne, podľa vašich oddiel spätná väzba, som vlastne 26 00:01:20,610 --> 00:01:23,000 odišiel asi 15 minút pri koniec jednoducho ísť cez 27 00:01:23,000 --> 00:01:27,730 logistika pset3, nejaké otázky, možno trochu poradenstvo, ak chcete, 28 00:01:27,730 --> 00:01:28,990 Než začneme programovanie. 29 00:01:28,990 --> 00:01:30,890 Takže poďme sa pokúsiť sa dostať cez materiál celkom rýchlo. 30 00:01:30,890 --> 00:01:33,880 A potom môžeme stráviť nejaký čas pričom ďalšie otázky pre pset. 31 00:01:33,880 --> 00:01:35,230 OK. 32 00:01:35,230 --> 00:01:39,570 >> Rýchlo, takže len pár oznámenia Než začneme dnes. 33 00:01:39,570 --> 00:01:45,410 Po prvé, vitajte na to, to prostredníctvom dvoch svojich psets. 34 00:01:45,410 --> 00:01:49,432 Som sa pozrieť na your-- jo, poďme získať potlesk pre tento jeden. 35 00:01:49,432 --> 00:01:51,140 Vlastne, bol som naozaj, naozaj ohromený. 36 00:01:51,140 --> 00:01:55,800 Triedené som prvý pset pre vás Minulý týždeň a vy ste urobili neuveriteľný. 37 00:01:55,800 --> 00:01:58,290 >> Štýl bol na mieste okrem niekoľkých komentárov. 38 00:01:58,290 --> 00:02:00,660 Uistite sa, že ste vždy komentovanie váš kód. 39 00:02:00,660 --> 00:02:03,040 Ale vaša psets boli na mieste. 40 00:02:03,040 --> 00:02:05,549 A tak ďalej. 41 00:02:05,549 --> 00:02:08,090 A to je dobré pre porovnávač na vidieť, že chlapci sú uvedení 42 00:02:08,090 --> 00:02:10,704 v ako veľa úsilia vo vašom štýle a váš návrh v kóde 43 00:02:10,704 --> 00:02:12,120 že by sme chceli pre vás vidieť. 44 00:02:12,120 --> 00:02:16,450 Takže som išiel po mojej vďačnosti pre zvyšok TA. 45 00:02:16,450 --> 00:02:19,210 >> Existujú však Niekoľko otázok Rozprava 46 00:02:19,210 --> 00:02:22,010 Ja len chcem ísť cez to by sa aj môj život 47 00:02:22,010 --> 00:02:24,900 a mnoho iný TA "život trochu jednoduchšie. 48 00:02:24,900 --> 00:02:28,220 Po prvé, som si všimol minulosť week-- koľko z vás 49 00:02:28,220 --> 00:02:32,301 Boli beží na check50 váš kód Pred odoslaním? 50 00:02:32,301 --> 00:02:32,800 OK. 51 00:02:32,800 --> 00:02:36,690 Takže každý by mal robiť check50, protože-- secret-- sme vlastne 52 00:02:36,690 --> 00:02:41,540 bežať check50 ako súčasť nášho správnosti skripty pre testovanie kódu. 53 00:02:41,540 --> 00:02:45,480 Takže ak váš kód zlyháva check50, so všetkou pravdepodobnosťou, 54 00:02:45,480 --> 00:02:47,570 to asi bude zlyhať našu kontrolu rovnako. 55 00:02:47,570 --> 00:02:49,320 Niekedy vy majú správne odpovede. 56 00:02:49,320 --> 00:02:52,200 Rovnako ako v chamtivý, niektoré máte správne číslo, 57 00:02:52,200 --> 00:02:53,960 stačí vytlačiť nejaké extra veci. 58 00:02:53,960 --> 00:02:55,940 A to navyše vec skutočne zlyhá šek, 59 00:02:55,940 --> 00:02:58,440 pretože počítač nie je Naozaj viete, čo to hľadá. 60 00:02:58,440 --> 00:03:00,981 A tak to bude len prejsť, vidieť, že váš výstup nie je 61 00:03:00,981 --> 00:03:03,810 zodpovedať tomu, čo očakávame odpoveď byť, a označiť je to zle. 62 00:03:03,810 --> 00:03:06,560 >> A ja viem, že sa stalo v niektoré z vašich prípadov tento týždeň. 63 00:03:06,560 --> 00:03:09,870 Tak som sa vrátil a ručne nestal kód každého. 64 00:03:09,870 --> 00:03:12,780 V budúcnosti však, prosím, uistite sa, 65 00:03:12,780 --> 00:03:14,570 že utekáš skontrolovať 50 na vašom kóde. 66 00:03:14,570 --> 00:03:17,970 Vzhľadom k tomu, že je to tak trochu bolesti CK musieť vrátiť späť a ručne preradenie do inej triedy 67 00:03:17,970 --> 00:03:21,197 každý pset pre každého slobodný, malý minul inštancie. 68 00:03:21,197 --> 00:03:22,530 Takže som nemal vzlietnuť žiadne body. 69 00:03:22,530 --> 00:03:25,210 Myslím, že som si vzal voľno možná jeden alebo dva pre dizajn. 70 00:03:25,210 --> 00:03:27,710 V budúcnosti aj keď, ak ste nedarí check50, 71 00:03:27,710 --> 00:03:31,330 budú prijaté body off správnosť. 72 00:03:31,330 --> 00:03:35,020 >> Okrem toho, sú psets vzhľadom piatok napoludnie. 73 00:03:35,020 --> 00:03:38,990 Myslím, že je to sedem minút neskoré doba odkladu, že sme dať. 74 00:03:38,990 --> 00:03:42,434 Per Harvard času, oni majú dovolené bolo sedem minút neskoro na všetko. 75 00:03:42,434 --> 00:03:44,350 Tak tu na Yale, budeme držať sa, že rovnako. 76 00:03:44,350 --> 00:03:47,910 Ale celkom veľa, na 12:07, ak vaše pset nie je, 77 00:03:47,910 --> 00:03:49,720 to bude označený ako neskoro. 78 00:03:49,720 --> 00:03:53,160 A tak, keď je označená ako neskoro, TA-- ja som 79 00:03:53,160 --> 00:03:54,870 Stále bude triedenie vaše psets. 80 00:03:54,870 --> 00:03:56,760 Takže budete stále vidieť stupeň objaviť. 81 00:03:56,760 --> 00:03:58,820 Avšak, viem, že sa na koniec semestra, 82 00:03:58,820 --> 00:04:02,270 všetky neskorej psets bude len automaticky vynulovaná počítačom. 83 00:04:02,270 --> 00:04:04,490 >> Robíme to z dvoch dôvodov. 84 00:04:04,490 --> 00:04:09,220 Raz, niekedy dostaneme ospravedlnila, ako výhovorky dekana 85 00:04:09,220 --> 00:04:10,762 neskôr, že neviem o doteraz. 86 00:04:10,762 --> 00:04:13,761 Tak sme radi, aby sa uistil, že sme triedenie všetko len v prípade, rovnako ako, že som 87 00:04:13,761 --> 00:04:15,080 Chýba dekana výhovorku. 88 00:04:15,080 --> 00:04:17,000 A za druhé, majte na myseľ, stále sa môžete 89 00:04:17,000 --> 00:04:19,370 odpojiť jedného pset že má plnej šírke bodov. 90 00:04:19,370 --> 00:04:21,430 A tak sme radi stupeň všetky vaše psets len 91 00:04:21,430 --> 00:04:24,730 aby sa ubezpečil, že váš priestor je tam a vy ich skúšať. 92 00:04:24,730 --> 00:04:29,150 Takže aj keď je to neskoro, budete stále získať úver na pôsobnosti bodov, myslím. 93 00:04:29,150 --> 00:04:33,730 >> Takže morálne príbehu je, aby že vaše psets sú v on-včas. 94 00:04:33,730 --> 00:04:38,350 A ak nie sú v on-včas, viem, že to nie je veľký. 95 00:04:38,350 --> 00:04:41,678 Jo, než som ísť ďalej, nemá niekto mať Akékoľvek otázky týkajúce pset spätnú väzbu? 96 00:04:41,678 --> 00:04:42,178 Jo. 97 00:04:42,178 --> 00:04:43,630 >> Divákov: Vedeli ste, že sme môžu klesnúť jeden z psets? 98 00:04:43,630 --> 00:04:44,296 >> ANDI PENG: Jo. 99 00:04:44,296 --> 00:04:47,050 Takže je tu deväť psets celkovo v priebehu semestra. 100 00:04:47,050 --> 00:04:50,610 A ak máte priestor points-- takže rozsah je len, 101 00:04:50,610 --> 00:04:53,567 celkom veľa, ste pokusom o Problém, ste uvedení v čase, 102 00:04:53,567 --> 00:04:56,150 sa vám ukazujú, že ste preukázal, že ste čítal spec. 103 00:04:56,150 --> 00:04:57,191 To je celkom veľký priestor. 104 00:04:57,191 --> 00:04:59,370 A ak ste sa plnia rozsah bodov, my 105 00:04:59,370 --> 00:05:03,360 môžu klesnúť najnižšiu jedným z plného rozsahu. 106 00:05:03,360 --> 00:05:06,790 Tak to je vo svoj prospech, aby dokončiť a skúsiť každý pset. 107 00:05:06,790 --> 00:05:10,320 >> Aj upload-- ak žiadny z je pracovať, je nahrať všetky. 108 00:05:10,320 --> 00:05:13,711 A potom budeme snáď môcť aby vám niektoré z týchto bodov späť. 109 00:05:13,711 --> 00:05:14,210 Super. 110 00:05:14,210 --> 00:05:16,780 Nejaké ďalšie otázky? 111 00:05:16,780 --> 00:05:17,840 Skvelé. 112 00:05:17,840 --> 00:05:21,960 >> Po druhé, kancelária hours-- pár rýchle poznámky o úradných hodinách. 113 00:05:21,960 --> 00:05:24,300 Takže najprv, príde na začiatku týždňa. 114 00:05:24,300 --> 00:05:26,909 Nikto nie je nikdy v úradné hodiny na pondelok. 115 00:05:26,909 --> 00:05:28,700 Christabel prišiel úradné hodiny minulú noc. 116 00:05:28,700 --> 00:05:29,691 Jo, Christabel. 117 00:05:29,691 --> 00:05:32,190 A to, čo sme sa v kancelárii hodiny v noci, Christabel? 118 00:05:32,190 --> 00:05:33,020 >> Divákov: Mali sme zmrzlinu. 119 00:05:33,020 --> 00:05:36,160 >> ANDI PENG: Tak to je v poriadku, mali sme zmrzlina v úradných hodinách minulú noc. 120 00:05:36,160 --> 00:05:39,390 Aj keď nemôžem sľúbiť, že budeme mať zmrzlinu na úradné hodiny 121 00:05:39,390 --> 00:05:43,230 každý týždeň, čo som vám sľúbiť, je to, že tam bude významne 122 00:05:43,230 --> 00:05:45,380 lepší študentka pomer TA. 123 00:05:45,380 --> 00:05:47,650 Rovnako ako legitímne, je to ako tri ku jednej. 124 00:05:47,650 --> 00:05:50,350 Vzhľadom k tomu, že kontrast s Štvrtok, máte asi 150 125 00:05:50,350 --> 00:05:52,830 naozaj zdôraznil, deti a žiadnu zmrzlinu. 126 00:05:52,830 --> 00:05:55,360 A to jednoducho nie je produktívne pre nikoho. 127 00:05:55,360 --> 00:05:58,730 Takže Ponaučenie z príbehu je, príde čoskoro na pracovný čas a dobrých vecí 128 00:05:58,730 --> 00:06:00,310 stane sa. 129 00:06:00,310 --> 00:06:02,110 >> Tiež, príďte pripravení klásť otázky. 130 00:06:02,110 --> 00:06:03,200 Ty vieš? 131 00:06:03,200 --> 00:06:05,420 Bez ohľadu na to, čo TA, ja myslím, hovorili, 132 00:06:05,420 --> 00:06:10,710 sme sa dostať pár študentov ktorí prídu na štvrtok v, ako, 10:50 133 00:06:10,710 --> 00:06:15,100 nie po prečítaní spec bytia ako pomôž mi, pomôž mi. 134 00:06:15,100 --> 00:06:18,200 Bohužiaľ v tomto bode, je tu nie je moc, čo môžeme urobiť, aby vám pomohol. 135 00:06:18,200 --> 00:06:19,590 Tak príďte na začiatku týždňa. 136 00:06:19,590 --> 00:06:22,040 Príďte skoro na úradné hodiny. 137 00:06:22,040 --> 00:06:23,350 Príďte pripravení klásť otázky. 138 00:06:23,350 --> 00:06:25,310 Uistite sa, že vás, ako študent, sú miesta, kde 139 00:06:25,310 --> 00:06:27,620 musíte byť tak, že TA môže vás spolu, 140 00:06:27,620 --> 00:06:32,850 čo je to, čo úradné hodiny by mali byť pridelené pre. 141 00:06:32,850 --> 00:06:37,380 >> Po druhé, takže viem, že profesormi rád, aby nás prekvapil s testami. 142 00:06:37,380 --> 00:06:39,439 Mal som profesora tie ako, yo, mimochodom, 143 00:06:39,439 --> 00:06:41,230 pamätajte, že v polovici obdobia Máte budúci pondelok. 144 00:06:41,230 --> 00:06:42,855 Jo, som nevedel o tom strednodobom horizonte. 145 00:06:42,855 --> 00:06:45,630 Takže ja budem, že TA ktorá vám pripomína, všetci, že kvíz 146 00:06:45,630 --> 00:06:47,270 0-- pretože, viete, že sme CS. 147 00:06:47,270 --> 00:06:50,730 Teraz, keď sme urobili pole, dostanete prečo je to kvíz 0, nie kvíz 1, eh? 148 00:06:50,730 --> 00:06:51,320 OK. 149 00:06:51,320 --> 00:06:52,490 Oh, dostal som nejaké smiech na tomto jeden. 150 00:06:52,490 --> 00:06:53,120 OK. 151 00:06:53,120 --> 00:06:59,710 >> Takže kvíz 0 bude 14.októbra, pokiaľ ste v sekcii pondelok streda 152 00:06:59,710 --> 00:07:02,920 15. októbra, ak ste v sekcia utorok štvrtok. 153 00:07:02,920 --> 00:07:05,630 To neplatí pre tí z vás na Harvarde 154 00:07:05,630 --> 00:07:10,350 who-- Myslím, že budete všetci pričom vaše kvízy na 14 .. 155 00:07:10,350 --> 00:07:13,560 >> Tak jo, budúci týždeň, ak David, v prednáške, ide, 156 00:07:13,560 --> 00:07:15,747 jo, tak o tom kvíz budúci týždeň, vy všetci 157 00:07:15,747 --> 00:07:17,580 nebude v šoku, pretože ste prišli na časti 158 00:07:17,580 --> 00:07:19,664 a viete, že vaše kvíz 0 je za dva týždne. 159 00:07:19,664 --> 00:07:21,580 A budeme mať kontrolu zasadnutie a všetko. 160 00:07:21,580 --> 00:07:26,360 Takže žiadne obavy o sa báť za to. 161 00:07:26,360 --> 00:07:29,890 Akékoľvek otázky before-- otázky vo všetkých otázkach týkajúcich sa logistických, 162 00:07:29,890 --> 00:07:32,591 triedenie, úradné hodiny, profily? 163 00:07:32,591 --> 00:07:33,090 Jo. 164 00:07:33,090 --> 00:07:35,100 >> Divákov: Takže je kvíz bude v priebehu prednášky? 165 00:07:35,100 --> 00:07:35,766 >> ANDI PENG: Jo. 166 00:07:35,766 --> 00:07:39,460 Takže kvízu, myslím si, je 60 minút pridelené v tomto časovom úseku 167 00:07:39,460 --> 00:07:42,240 že budete len vziať v prednáškovej sále. 168 00:07:42,240 --> 00:07:44,810 Takže nemusíte prísť o, rovnako ako, náhodný 7:00 PM. 169 00:07:44,810 --> 00:07:46,140 Je to všetko dobré. 170 00:07:46,140 --> 00:07:47,100 Jo. 171 00:07:47,100 --> 00:07:50,060 Super. 172 00:07:50,060 --> 00:07:50,840 >> Dobre. 173 00:07:50,840 --> 00:07:54,330 Takže budeme zaviesť koncept pre vás 174 00:07:54,330 --> 00:08:00,760 tento týždeň, že David má už druh z dotkla v prednáške minulý týždeň. 175 00:08:00,760 --> 00:08:02,010 Hovorí sa tomu GDB. 176 00:08:02,010 --> 00:08:05,570 A koľko z vás, zatiaľ čo v priebeh písanie psets, 177 00:08:05,570 --> 00:08:09,981 zaznamenali veľké tlačidlo, ktoré hovorí, "Debug" v hornej časti vášho IDE? 178 00:08:09,981 --> 00:08:10,480 OK. 179 00:08:10,480 --> 00:08:13,770 Takže teraz budeme skutočne dostať odkryť záhada, čo týmto tlačidlom skutočne 180 00:08:13,770 --> 00:08:14,270 robí. 181 00:08:14,270 --> 00:08:16,790 A ja vám zaručiť, je to krásna, krásna vec. 182 00:08:16,790 --> 00:08:20,740 >> Takže až do teraz, myslím, že tam bolo dve veci 183 00:08:20,740 --> 00:08:23,320 Študenti boli typicky robí pri ladení psets. 184 00:08:23,320 --> 00:08:27,635 Jeden z nich, buď pridať printf () - tak každých pár riadkov, 185 00:08:27,635 --> 00:08:29,760 pridávajú v printf () - ach, čo je to premenná? 186 00:08:29,760 --> 00:08:32,551 Ach, ako je táto premenná now-- a tak nejako vidieť progresiu 187 00:08:32,551 --> 00:08:33,940 z kódu, ako to beží. 188 00:08:33,940 --> 00:08:37,030 Alebo druhá metóda deti urobiť, je že stačí napísať celú vec 189 00:08:37,030 --> 00:08:38,610 a potom ísť takto na konci. 190 00:08:38,610 --> 00:08:39,970 Dúfajme, že to funguje. 191 00:08:39,970 --> 00:08:44,851 Ja vám zaručiť, GDB je lepšie než obaja z týchto metód. 192 00:08:44,851 --> 00:08:45,350 Jo. 193 00:08:45,350 --> 00:08:46,980 Takže to bude váš nový najlepší priateľ. 194 00:08:46,980 --> 00:08:51,780 Vzhľadom k tomu, že je to krásna vec ktorý vizuálne zobrazuje oba 195 00:08:51,780 --> 00:08:54,850 čo váš kód robí v určitom bode 196 00:08:54,850 --> 00:08:57,486 rovnako ako to, čo všetky vaše premenné sú účtovné, 197 00:08:57,486 --> 00:08:59,610 ako to, čo ich hodnoty, v tomto konkrétnom bode. 198 00:08:59,610 --> 00:09:02,670 A týmto spôsobom, môžete si naozaj nastaviť zarážky v kóde. 199 00:09:02,670 --> 00:09:04,350 Môžete spustiť cez riadok po riadku. 200 00:09:04,350 --> 00:09:07,324 A GDB budú mať len pre vy, zobrazí sa pre vás, 201 00:09:07,324 --> 00:09:09,490 čo všetky vaše premenné sú, čo robia, 202 00:09:09,490 --> 00:09:10,656 čo sa deje v kóde. 203 00:09:10,656 --> 00:09:13,240 A takým spôsobom, že je to tak oveľa jednoduchšie vidieť 204 00:09:13,240 --> 00:09:17,120 čo sa deje, namiesto printf-ing alebo písanie sa vaše vyhlásenie. 205 00:09:17,120 --> 00:09:19,160 >> Takže urobíme príklad neskôr. 206 00:09:19,160 --> 00:09:20,660 Takže to vyzerá trochu abstraktné. 207 00:09:20,660 --> 00:09:23,490 Žiadne starosti, urobíme príklady. 208 00:09:23,490 --> 00:09:29,170 A tak v podstate, tri najväčšie, najpoužívanejšie funkcie, ktoré budete potrebovať v GDB 209 00:09:29,170 --> 00:09:32,500 sú ďalšie, prekročiť, a krok do tlačidiel. 210 00:09:32,500 --> 00:09:34,860 Idem cez hlavu tam, v skutočnosti, práve teraz. 211 00:09:34,860 --> 00:09:40,930 >> Takže môžete vidieť, že chlapci všetko alebo by som mal priblížiť trochu? 212 00:09:40,930 --> 00:09:43,220 213 00:09:43,220 --> 00:09:44,470 V zadnej, môžete vidieť, že? 214 00:09:44,470 --> 00:09:45,730 Mám priblížiť? 215 00:09:45,730 --> 00:09:46,480 Len trošku? 216 00:09:46,480 --> 00:09:49,390 OK v pohode. 217 00:09:49,390 --> 00:09:50,280 Tam sme ísť. 218 00:09:50,280 --> 00:09:50,960 OK. 219 00:09:50,960 --> 00:09:57,000 >> Tak som si, tu, moji implementácie pre chamtivý. 220 00:09:57,000 --> 00:10:01,430 A aj keď veľa z vás napísal chamtivý v while form-- že 221 00:10:01,430 --> 00:10:04,890 je úplne prijateľný spôsob, ako robiť to-- iný spôsob, ako to urobiť, je jednoducho 222 00:10:04,890 --> 00:10:06,280 rozdeliť v modulo. 223 00:10:06,280 --> 00:10:09,290 Vzhľadom k tomu, potom môžete mať svoj hodnota a potom mať svoje zostávajúce. 224 00:10:09,290 --> 00:10:11,150 A potom stačí pridať to všetko dohromady. 225 00:10:11,150 --> 00:10:13,390 Má logiku, čo robím tu zmysel pre každého, 226 00:10:13,390 --> 00:10:14,117 Ako začneme? 227 00:10:14,117 --> 00:10:16,760 228 00:10:16,760 --> 00:10:17,980 Druh? 229 00:10:17,980 --> 00:10:18,710 Super. 230 00:10:18,710 --> 00:10:19,210 Skvelé. 231 00:10:19,210 --> 00:10:21,290 Je to celkom sexi kus kódu, povedal by som. 232 00:10:21,290 --> 00:10:23,502 Ako som povedal, David, v prednáška, po chvíli, 233 00:10:23,502 --> 00:10:25,960 všetci začnete vidieť kód ako niečo, čo je krásne. 234 00:10:25,960 --> 00:10:29,950 A niekedy, keď vidíte, krásna kód, je to tak nádherný pocit. 235 00:10:29,950 --> 00:10:35,410 >> Takže sa však, keď tento kód je veľmi krásne, že nefunguje správne. 236 00:10:35,410 --> 00:10:37,750 Takže poďme bežať check50 na túto tému. 237 00:10:37,750 --> 00:10:39,440 Skontrolujte, či 50 20-- OOP. 238 00:10:39,440 --> 00:10:43,221 239 00:10:43,221 --> 00:10:43,720 2? 240 00:10:43,720 --> 00:10:44,990 Je to pset2? 241 00:10:44,990 --> 00:10:46,870 Jo. 242 00:10:46,870 --> 00:10:47,520 Oh, pset1. 243 00:10:47,520 --> 00:10:50,970 244 00:10:50,970 --> 00:10:52,890 OK. 245 00:10:52,890 --> 00:10:53,900 Tak sme sa spustiť check50. 246 00:10:53,900 --> 00:11:01,550 247 00:11:01,550 --> 00:11:07,170 >> A ako vy môžete vidieť tu, to nedarí niekoľko prípadov. 248 00:11:07,170 --> 00:11:10,165 A pre niektoré z vás, v Priebeh robí váš problém súpravy, 249 00:11:10,165 --> 00:11:11,110 ste ako, ehm, prečo je to tak nefunguje. 250 00:11:11,110 --> 00:11:13,318 Prečo to funguje pre niektoré hodnoty, ale nie pre ostatné? 251 00:11:13,318 --> 00:11:17,760 No, GDB bude vám pomôže zistiť out, prečo tieto vstupy boli nefunguje. 252 00:11:17,760 --> 00:11:18,320 >> OK. 253 00:11:18,320 --> 00:11:21,640 Tak uvidíme, jeden z Kontroly som bol neúspešný v check50 254 00:11:21,640 --> 00:11:24,920 bola vstupná hodnota 0,41. 255 00:11:24,920 --> 00:11:27,830 Takže správna odpoveď, že mali by ste sa dostať je 4. 256 00:11:27,830 --> 00:11:33,090 Ale namiesto toho, čo som vytlačenie je 3-n, čo je nesprávny. 257 00:11:33,090 --> 00:11:36,190 Takže poďme stačí spustiť tento ručne, len Uistite sa, že check50 funguje. 258 00:11:36,190 --> 00:11:36,940 Urobme ./greedy. 259 00:11:36,940 --> 00:11:40,130 260 00:11:40,130 --> 00:11:43,340 Jejda, musím urobiť chamtivý. 261 00:11:43,340 --> 00:11:43,840 Tam sme ísť. 262 00:11:43,840 --> 00:11:44,381 Teraz ./greedy. 263 00:11:44,381 --> 00:11:46,950 264 00:11:46,950 --> 00:11:47,670 >> Koľko je dlhuje? 265 00:11:47,670 --> 00:11:49,550 Urobme 0,41. 266 00:11:49,550 --> 00:11:52,590 A jo, vidíme tu že je to výstup 3 267 00:11:52,590 --> 00:11:55,160 keď správna odpoveď, v skutočnosti by malo byť 4. 268 00:11:55,160 --> 00:12:01,460 Takže poďme vstúpiť GDB a vidieť, ako môže ísť o tom, ktorým tento problém. 269 00:12:01,460 --> 00:12:03,992 >> Takže prvý krok v Vždy ladenie kódu 270 00:12:03,992 --> 00:12:05,950 je nastaviť zarážku, alebo bod, na ktorý 271 00:12:05,950 --> 00:12:09,079 Chcete v počítači alebo debugger začať uvažovať. 272 00:12:09,079 --> 00:12:11,120 Takže ak nemáte naozaj viete, čo je tvoj problém, 273 00:12:11,120 --> 00:12:14,670 Zvyčajne, typický, čo chceme urobiť, je nastaviť náš zarážku na hlavnú. 274 00:12:14,670 --> 00:12:18,520 Takže ak vy môžete vidieť červené tlačidlo priamo tam, 275 00:12:18,520 --> 00:12:22,860 Jo, to som bol ja nastavenia breakpoint pre hlavnú funkciu. 276 00:12:22,860 --> 00:12:24,130 Aj kliknite na to. 277 00:12:24,130 --> 00:12:26,130 >> A potom môžem ísť až na môjho tlačidlo Debug. 278 00:12:26,130 --> 00:12:27,036 Trafil som ten gombík. 279 00:12:27,036 --> 00:12:31,710 280 00:12:31,710 --> 00:12:36,555 Dovoľte mi, aby som zoom späť, či môžem. 281 00:12:36,555 --> 00:12:38,020 Tam sme ísť. 282 00:12:38,020 --> 00:12:40,730 Takže máme tu, panel na pravej strane. 283 00:12:40,730 --> 00:12:43,680 Je mi ľúto, chlapci v chrbte, vy Nemôžete naozaj vidieť naozaj dobre. 284 00:12:43,680 --> 00:12:49,090 Ale v podstate všetky toto právo panel robí 285 00:12:49,090 --> 00:12:53,130 je sledovanie ako zvýraznené línie, čo je riadok kódu 286 00:12:53,130 --> 00:12:56,640 že počítač je v súčasnosti beží, rovnako ako všetky vaše premenné 287 00:12:56,640 --> 00:12:57,600 tu dole. 288 00:12:57,600 --> 00:13:00,487 >> Takže ste dostali centov, mincí, n, všetky vyhlásený rôzne veci 289 00:13:00,487 --> 00:13:01,070 v tomto bode. 290 00:13:01,070 --> 00:13:04,850 Žiadne starosti, pretože sme vlastne inicializuje je na všetkých premenných doteraz. 291 00:13:04,850 --> 00:13:07,200 Takže vo vašom počítači, vaše Počítač je len vidieť, 292 00:13:07,200 --> 00:13:14,376 oh, 32767 bol naposledy použitý funkcie tohto pamäťového priestoru v mojom počítači. 293 00:13:14,376 --> 00:13:16,000 A tak to je, kde je v súčasnej dobe centov. 294 00:13:16,000 --> 00:13:19,360 Ale nie, že akonáhle sa spustiť kód, by sa mala stať inicializovaný. 295 00:13:19,360 --> 00:13:24,110 >> Takže poďme prejsť, riadok linka, čo sa tu deje. 296 00:13:24,110 --> 00:13:25,350 OK. 297 00:13:25,350 --> 00:13:29,400 Tak tu sú tri Tlačidla, ktoré som práve vysvetlil. 298 00:13:29,400 --> 00:13:34,090 Máte Play, alebo funkcia Run, tlačidlo, budete mať krok nad tlačidlom, 299 00:13:34,090 --> 00:13:36,600 a máte tiež krok do tlačidla. 300 00:13:36,600 --> 00:13:41,260 A v podstate, všetci traja je jednoducho ísť cez váš kód 301 00:13:41,260 --> 00:13:42,690 a robiť rôzne veci. 302 00:13:42,690 --> 00:13:45,680 >> Takže obvykle, keď ste ladenie, Nechceme, aby jednoducho stlačiť Play, 303 00:13:45,680 --> 00:13:47,930 pretože Play bude práve beží váš kód k jeho koncu. 304 00:13:47,930 --> 00:13:49,070 A potom nebudete v skutočnosti viete, čo je tvoj problém 305 00:13:49,070 --> 00:13:51,432 je, ak si nastaviť viac zarážky. 306 00:13:51,432 --> 00:13:53,890 Ak nastavíte viac zarážky, to bude len automaticky 307 00:13:53,890 --> 00:13:56,030 spustiť z jednej zarážky, na ďalšie, na ďalšie. 308 00:13:56,030 --> 00:13:58,030 Ale v tomto prípade máme len, že jeden, pretože my 309 00:13:58,030 --> 00:13:59,970 Chcete pracovať našu cestu od zhora nadol nadol. 310 00:13:59,970 --> 00:14:04,830 Takže budeme ignorovať ten gombík teraz na účely tohto programu. 311 00:14:04,830 --> 00:14:08,230 >> Takže Krok cez funkciu len Kroky nad každým jednu linku 312 00:14:08,230 --> 00:14:11,510 a povie vám, čo počítač robí. 313 00:14:11,510 --> 00:14:14,630 Step do funkcie pokračuje do skutočnú funkciu 314 00:14:14,630 --> 00:14:16,000 že je na vašom riadku kódu. 315 00:14:16,000 --> 00:14:19,070 Tak napríklad, rovnako ako printf (), že je funkcia, že jo? 316 00:14:19,070 --> 00:14:21,980 Keby som chcel fyzicky krok do funkcie printf (), 317 00:14:21,980 --> 00:14:25,610 Ja by som skutočne ísť do kusu smerovacie číslo, kde printf () bol napísaný a vidieť 318 00:14:25,610 --> 00:14:26,730 čo sa tam deje. 319 00:14:26,730 --> 00:14:29,924 >> Ale zvyčajne, budeme predpokladať, že kód, ktorý dáme vám funguje. 320 00:14:29,924 --> 00:14:31,340 Predpokladáme, printf () pracuje. 321 00:14:31,340 --> 00:14:33,170 Predpokladáme, že GetInt () funguje. 322 00:14:33,170 --> 00:14:35,170 Takže nie je potrebné krok do týchto funkcií. 323 00:14:35,170 --> 00:14:37,170 Ale či je tu funkcia že píšete sami 324 00:14:37,170 --> 00:14:39,060 že chcete skontrolovať čo sa deje, 325 00:14:39,060 --> 00:14:41,200 by ste chceli kroku do tejto funkcie. 326 00:14:41,200 --> 00:14:43,940 >> Takže teraz sme len tak prekročiť tento kus kódu. 327 00:14:43,940 --> 00:14:44,485 Takže poďme sa pozrieť. 328 00:14:44,485 --> 00:14:46,547 Oh, print, "Ach hai, ako mnoho zmien je dlžný? " 329 00:14:46,547 --> 00:14:47,130 Nezaujíma nás. 330 00:14:47,130 --> 00:14:49,830 Vieme, že to funguje, tak sme krok nad ním. 331 00:14:49,830 --> 00:14:53,290 >> Takže n, čo je naša float, že máme initialized-- alebo declared-- 332 00:14:53,290 --> 00:14:56,810 up na vrchole, sme teraz rovnajúcej sa, že pre GetFloat (). 333 00:14:56,810 --> 00:14:57,810 Takže poďme krok cez to. 334 00:14:57,810 --> 00:14:59,580 A vidíme u dno tu, program 335 00:14:59,580 --> 00:15:03,360 nabáda ma na vstup hodnotu. 336 00:15:03,360 --> 00:15:08,580 Takže poďme Zadajte hodnotu chceme testovať tu, čo je 0,41. 337 00:15:08,580 --> 00:15:09,160 Skvelé. 338 00:15:09,160 --> 00:15:12,780 >> Takže teraz n- si chlapci vidieť tu, u bottom-- je to 339 00:15:12,780 --> 00:15:15,140 stored-- pretože my Zatiaľ nie sú zaoblené, to je 340 00:15:15,140 --> 00:15:19,540 uložené v tomto ako obrie float, že je, 4099999996, 341 00:15:19,540 --> 00:15:22,550 čo je dosť blízko, aby naše účely, práve teraz, na 0,41. 342 00:15:22,550 --> 00:15:26,090 A potom sa uvidí neskôr, keď sme pokračovať prekročil programu, 343 00:15:26,090 --> 00:15:29,850 po tu, n sa stal zaoblené a centov stal 41. 344 00:15:29,850 --> 00:15:30,350 Skvelé. 345 00:15:30,350 --> 00:15:32,230 Takže vieme, že naše zaokrúhlenie má prácu. 346 00:15:32,230 --> 00:15:34,700 Vieme, že máme správny počet centov, 347 00:15:34,700 --> 00:15:36,990 takže vieme, že je to nie je naozaj problém. 348 00:15:36,990 --> 00:15:40,050 >> Takže budeme pokračovať krokovanie Na v tomto programe. 349 00:15:40,050 --> 00:15:40,900 Ideme sem. 350 00:15:40,900 --> 00:15:46,139 A tak po tomto riadku kódu, my by mali vedieť, koľko štvrtiny máme. 351 00:15:46,139 --> 00:15:46,680 Sme prekročiť. 352 00:15:46,680 --> 00:15:52,040 A vidíte my, v skutočnosti, mať jeden štvrťroku, pretože sme sa odpočíta 25 353 00:15:52,040 --> 00:15:53,790 z našej počiatočnej hodnoty 41. 354 00:15:53,790 --> 00:15:55,890 A máme 16 doľava pre naše centov. 355 00:15:55,890 --> 00:15:58,830 >> Má každý pochopiť, ako Program je krokovanie 356 00:15:58,830 --> 00:16:02,980 a prečo centov je dnes 16 a prečo, teraz, mince sa stala 1? 357 00:16:02,980 --> 00:16:04,610 Je každý nasledujúci, že logika? 358 00:16:04,610 --> 00:16:05,110 Super. 359 00:16:05,110 --> 00:16:07,860 Tak, aby na tomto okamihu pracovný program je, že jo? 360 00:16:07,860 --> 00:16:09,797 Vieme, že to robí presne to, to, čo chceme, aby to. 361 00:16:09,797 --> 00:16:11,880 A my nie v skutočnosti musieť vytlačiť, ach, čo 362 00:16:11,880 --> 00:16:14,430 Je centov v tomto bode, čo je mincí v tomto bode. 363 00:16:14,430 --> 00:16:17,170 >> Aj naďalej sa prostredníctvom programu. 364 00:16:17,170 --> 00:16:18,100 Krok cez. 365 00:16:18,100 --> 00:16:18,620 Super. 366 00:16:18,620 --> 00:16:19,700 Ideme cez desaťhalierniky. 367 00:16:19,700 --> 00:16:20,200 Skvelé. 368 00:16:20,200 --> 00:16:22,367 Vidíme, že je to vziať off 0,10 $ za desetník. 369 00:16:22,367 --> 00:16:23,450 A teraz máme dve mince. 370 00:16:23,450 --> 00:16:25,260 To je správne. 371 00:16:25,260 --> 00:16:31,555 >> Ideme cez haliere a vidíme, že sme sa dostali zostane centov. 372 00:16:31,555 --> 00:16:32,680 Hmm, to je divné. 373 00:16:32,680 --> 00:16:37,540 Tu hore na programe, mal som k odpočítať svoje haliere. 374 00:16:37,540 --> 00:16:39,400 Možno som jednoducho nebol tým, že linka práva. 375 00:16:39,400 --> 00:16:42,190 A beda, môžete vidieť tu, pretože vieme, 376 00:16:42,190 --> 00:16:44,360 že sme posilnenie potrubím 32 a 33, 377 00:16:44,360 --> 00:16:50,560 že je miesto, kde náš program nesprávne mal premenných spustiť. 378 00:16:50,560 --> 00:16:55,136 Takže môžeme pozerať a vidieť, oh, Som odpočítaním centov tu, 379 00:16:55,136 --> 00:16:57,010 ale ja nie som v skutočnosti pridať do môjho hodnotou mince. 380 00:16:57,010 --> 00:16:57,860 Som pridanie do centov. 381 00:16:57,860 --> 00:17:00,234 A ja nechcem pridať do centov, chcem pridať do mincí. 382 00:17:00,234 --> 00:17:05,420 Takže keď sme sa zmeniť na mince, máme pracovný program. 383 00:17:05,420 --> 00:17:06,730 Môžem bežať check50. 384 00:17:06,730 --> 00:17:11,063 Stačí si len opustíte GDB práva tu a spustite check50 znova. 385 00:17:11,063 --> 00:17:11,938 Mohol by som to urobiť. 386 00:17:11,938 --> 00:17:14,822 387 00:17:14,822 --> 00:17:18,480 Musím urobiť chamtivý. 388 00:17:18,480 --> 00:17:19,940 0.41. 389 00:17:19,940 --> 00:17:22,819 A tu je to tlač out správnu odpoveď. 390 00:17:22,819 --> 00:17:26,569 >> Tak ako vy môžete vidieť, GDB je naozaj mocný nástroj 391 00:17:26,569 --> 00:17:29,940 pretože keď máme toľko kód deje, a tak veľa premenných 392 00:17:29,940 --> 00:17:32,510 že je to pre nás ťažké, ako človek, sledovať. 393 00:17:32,510 --> 00:17:35,360 Počítač, v GDB debugger, má schopnosť 394 00:17:35,360 --> 00:17:37,020 udržiavať prehľad o všetkom. 395 00:17:37,020 --> 00:17:40,480 Ja viem, v Visionaire, vy pravdepodobne mohol zasiahnuť niektoré segmentácia chyby 396 00:17:40,480 --> 00:17:43,150 pretože ste používali mimo hranice svojho poľa. 397 00:17:43,150 --> 00:17:46,510 V príklade Caesara, to je presne to, čo som tu vykonaná. 398 00:17:46,510 --> 00:17:50,060 >> Tak som zabudol skontrolovať čo by sa mohlo stať, keby mi 399 00:17:50,060 --> 00:17:52,510 nemal dva argumenty príkazového riadka. 400 00:17:52,510 --> 00:17:53,880 Len som to dať do tejto kontroly. 401 00:17:53,880 --> 00:17:57,380 A tak, keď som bežať Debug-- nastavím môj bod prerušenia tam doprava. 402 00:17:57,380 --> 00:17:58,055 Bežím ladenie. 403 00:17:58,055 --> 00:18:15,880 404 00:18:15,880 --> 00:18:16,550 >> OK. 405 00:18:16,550 --> 00:18:17,050 Jo. 406 00:18:17,050 --> 00:18:20,350 Takže vlastne, GDB mal sa mi tam povedal, 407 00:18:20,350 --> 00:18:22,300 Bola to chyba, tam segmentácie. 408 00:18:22,300 --> 00:18:24,883 Ja neviem, čo sa deje práve tam, ale keď som bežal, 409 00:18:24,883 --> 00:18:25,590 že to funguje. 410 00:18:25,590 --> 00:18:29,410 Pri spustení riadkov kódu a cez GDB mohol len náhle skončiť na vás, 411 00:18:29,410 --> 00:18:31,540 ísť hore a pozrieť sa, čo je červená chyba je. 412 00:18:31,540 --> 00:18:33,930 To vám poviem, Hej, mal poruchu segmentáciu, 413 00:18:33,930 --> 00:18:38,550 čo znamená, že ste sa pokúsili o prístup priestory v poli, ktoré neexistuje. 414 00:18:38,550 --> 00:18:39,050 Jo. 415 00:18:39,050 --> 00:18:43,280 >> Takže ďalší problém Nastavte tento týždeň, vy 416 00:18:43,280 --> 00:18:45,600 bude pravdepodobne mať veľa Premenné plávajúce okolo. 417 00:18:45,600 --> 00:18:48,560 Vy nebudete byť istí, čo všetci na mysli v určitom okamihu. 418 00:18:48,560 --> 00:18:53,560 Takže GDB vám naozaj pomôže v premýšľaním čo oni sú všetci rovná 419 00:18:53,560 --> 00:18:55,940 a sú schopní vidieť, že vizuálne. 420 00:18:55,940 --> 00:19:01,995 Je niekto zmätený o tom, ako niečo z toho pracuje? 421 00:19:01,995 --> 00:19:02,495 Super. 422 00:19:02,495 --> 00:19:10,121 423 00:19:10,121 --> 00:19:10,620 Dobre. 424 00:19:10,620 --> 00:19:14,260 Takže po tom, my sme bude potápať doprava 425 00:19:14,260 --> 00:19:17,562 do sú štyri rôzne typy druhov pre tento týždeň. 426 00:19:17,562 --> 00:19:19,520 Ako mnohí z vás, najprv zo všetkého, ako začneme, 427 00:19:19,520 --> 00:19:23,020 Prečítal celý spec pre pset3? 428 00:19:23,020 --> 00:19:23,824 OK. 429 00:19:23,824 --> 00:19:24,740 Som hrdý na vás chlapci. 430 00:19:24,740 --> 00:19:29,110 To je ako polovica triedy, ktorá je výrazne viac ako minule. 431 00:19:29,110 --> 00:19:33,950 >> Tak to je skvelé, pretože keď hovoríme o obsahu 432 00:19:33,950 --> 00:19:36,170 v lecture-- alebo ľúto, v section-- sa mi páči 433 00:19:36,170 --> 00:19:38,210 týkať veľa ktorý späť na to, čo je pset 434 00:19:38,210 --> 00:19:40,210 a ako chcete implementovať, že vo vašom pset. 435 00:19:40,210 --> 00:19:42,400 Takže ak prídete s čítať spec, to bude 436 00:19:42,400 --> 00:19:45,510 bolo oveľa jednoduchšie pre vás pochopiť čo hovorím, keď hovorím, 437 00:19:45,510 --> 00:19:48,720 oh hej, mohlo by to byť naozaj dobré miesto na vykonanie tohto druhu. 438 00:19:48,720 --> 00:19:52,870 Takže tí z vás, ktorí si prečítať spec vedia, že, ako súčasť vášho pset, 439 00:19:52,870 --> 00:19:54,900 budete musieť napísať typ druhu. 440 00:19:54,900 --> 00:19:58,670 Takže to môže byť veľmi užitočné pre mnoho z vás dnes. 441 00:19:58,670 --> 00:20:01,760 >> Takže budeme začať s, v podstate, najviac jednoduchý typ 442 00:20:01,760 --> 00:20:04,580 Sort, výber triedenia. 443 00:20:04,580 --> 00:20:06,800 Typický algoritmus pre ako by sme ísť o to 444 00:20:06,800 --> 00:20:10,460 je-- David prešiel to všetko v prednáška, tak som si rýchlo pohybovať pozdĺž 445 00:20:10,460 --> 00:20:13,900 here-- je v podstate, vy majú celý rad hodnôt. 446 00:20:13,900 --> 00:20:17,170 A potom nájdete podrobnosti Najmenšia hodnota netriedený 447 00:20:17,170 --> 00:20:20,200 a zamieňať túto hodnotu s Prvý netriedený hodnota. 448 00:20:20,200 --> 00:20:22,700 A potom si len stále opakovať so zvyškom vášho zoznamu. 449 00:20:22,700 --> 00:20:25,740 >> A tu je vizuálny vysvetlenie o tom, ako to by mohlo fungovať. 450 00:20:25,740 --> 00:20:30,460 Tak napríklad, keď sme boli na začiatok s radom piatich elementov, index 451 00:20:30,460 --> 00:20:35,910 0 až 4, s 3, 5, 2, 6, a 4 Hodnoty umiestnené v array-- tak práve teraz, 452 00:20:35,910 --> 00:20:38,530 my len tak predpokladať, že sú všetci netriedený 453 00:20:38,530 --> 00:20:41,130 preto, že neboli testované inak. 454 00:20:41,130 --> 00:20:44,130 >> Tak, ako sa výber druhu by Práca je to, že by ako prvý 455 00:20:44,130 --> 00:20:46,800 prejsť celok z netriedeného poľa. 456 00:20:46,800 --> 00:20:49,120 To by vybrať najmenšiu hodnotu. 457 00:20:49,120 --> 00:20:51,750 V tomto prípade, 3, pravá Teraz, je najmenšia. 458 00:20:51,750 --> 00:20:52,680 To dostane až 5. 459 00:20:52,680 --> 00:20:55,620 Nie, 5 nie je väčšia than-- alebo ľúto, nie je menšia than-- 3. 460 00:20:55,620 --> 00:20:57,779 Takže minimálna hodnota je stále 3. 461 00:20:57,779 --> 00:20:58,695 A potom sa dostanete na 2. 462 00:20:58,695 --> 00:21:00,990 Počítač vidí, oh, 2 je menšia ako 3. 463 00:21:00,990 --> 00:21:02,750 2 teraz musí byť minimálna hodnota. 464 00:21:02,750 --> 00:21:06,630 A tak 2 swapy s týmto prvým hodnotou. 465 00:21:06,630 --> 00:21:10,702 >> Takže po jednom priechodu, môžeme skutočne vidieť že 2 a 3 sú prehodené. 466 00:21:10,702 --> 00:21:13,910 A my sme len tak v tom pokračovať To opäť so zvyškom poľa. 467 00:21:13,910 --> 00:21:17,660 Takže budeme len prejsť posledné štyri indexy poľa. 468 00:21:17,660 --> 00:21:20,670 Uvidíme, že 3 je ďalšie minimálna hodnota. 469 00:21:20,670 --> 00:21:23,240 Takže ideme na swap, ktorý sa 4. 470 00:21:23,240 --> 00:21:26,900 A potom sme to len tak, aby beh cez kým nie, nakoniec, vy 471 00:21:26,900 --> 00:21:33,730 dostať sa do triedeného poľa, v ktorom 2, 3, 4, 5, a 6 sú všetky zoradené. 472 00:21:33,730 --> 00:21:37,530 Rozumejú logiku o tom, ako výber triedenie funguje? 473 00:21:37,530 --> 00:21:39,669 >> Proste mať nejaký na minimálnu hodnotu. 474 00:21:39,669 --> 00:21:41,210 Ste sledovanie, čo to je. 475 00:21:41,210 --> 00:21:45,170 A keď ju nájdete, je zamieňať s prvou hodnotou v array-- 476 00:21:45,170 --> 00:21:48,740 alebo, nie je prvý value-- ďalšia hodnota v matici. 477 00:21:48,740 --> 00:21:50,150 Super. 478 00:21:50,150 --> 00:21:55,460 >> Takže ako chlapci druh Videl z krátkej zazrel, 479 00:21:55,460 --> 00:21:58,450 ideme pseudocode to. 480 00:21:58,450 --> 00:22:02,510 Takže ak vy vzadu chcú tvoria skupinu, všetci pri stole 481 00:22:02,510 --> 00:22:06,170 môžu tvoriť trochu partnera, idem dať sa vám bude páčiť tri minúty 482 00:22:06,170 --> 00:22:08,190 len prebrať logika, v angličtine, 483 00:22:08,190 --> 00:22:14,161 o tom, ako by sme mohli byť schopní implementovať pseudokód napísať výberom Triediť. 484 00:22:14,161 --> 00:22:14,910 A je tu cukrík. 485 00:22:14,910 --> 00:22:16,118 Prosím, prísť a dostať cukríky. 486 00:22:16,118 --> 00:22:19,520 Ak ste do chrbta a chcete cukrovinky, môžem hodiť cukroví na vás. 487 00:22:19,520 --> 00:22:22,850 V skutočnosti, robiť vás-- chladu. 488 00:22:22,850 --> 00:22:23,552 Oh, prepáč. 489 00:22:23,552 --> 00:22:26,751 490 00:22:26,751 --> 00:22:27,250 OK. 491 00:22:27,250 --> 00:25:23,880 492 00:25:23,880 --> 00:25:27,140 >> Takže ak by sme chceli, as trieda, zápis pseudokód 493 00:25:27,140 --> 00:25:30,466 na to, ako by sa dalo pristupovať tento problém, stačí pokojne. 494 00:25:30,466 --> 00:25:32,340 Budem jednoducho ísť okolo a, v poriadku, spýtajte sa skupiny 495 00:25:32,340 --> 00:25:35,065 na ďalší riadok Čo by sme mali robiť. 496 00:25:35,065 --> 00:25:37,840 Takže ak vy chcete začať off, čo je prvá vec, 497 00:25:37,840 --> 00:25:40,600 robiť, keď sa snažíte vykonávať spôsob, ako vyriešiť tento program 498 00:25:40,600 --> 00:25:43,480 selektívne zoradiť zoznam? 499 00:25:43,480 --> 00:25:46,349 Poďme len predpokladať, my majú celý rad, v poriadku? 500 00:25:46,349 --> 00:25:49,088 >> Divákov: Chcete vytvoriť niektoré druh [nepočuteľný], že ste 501 00:25:49,088 --> 00:25:50,420 beh cez celé tvoje pole. 502 00:25:50,420 --> 00:25:51,128 >> ANDI PENG: Správne. 503 00:25:51,128 --> 00:25:54,100 Takže budete chcieť opakovať cez všetky priestoru, je to tak? 504 00:25:54,100 --> 00:26:05,490 Takže, skvelé. 505 00:26:05,490 --> 00:26:08,600 Ak si chcú chalani mi dať ďalšie line-- jo, do chrbta. 506 00:26:08,600 --> 00:26:11,414 507 00:26:11,414 --> 00:26:13,290 >> Publikum: Pozrite sa na ne všetko pre najmenších. 508 00:26:13,290 --> 00:26:14,248 >> ANDI PENG: Ideme na to. 509 00:26:14,248 --> 00:26:17,438 Takže chceme prejsť a skontrolovať, vidieť, čo je minimálna hodnota, že jo? 510 00:26:17,438 --> 00:26:22,110 511 00:26:22,110 --> 00:26:24,840 Chystám sa skrátiť, že na "min." 512 00:26:24,840 --> 00:26:27,658 Čo vy chcete robiť po ste našli minimálnu hodnotu? 513 00:26:27,658 --> 00:26:28,533 >> Divákov: [Nepočuteľné] 514 00:26:28,533 --> 00:26:29,942 515 00:26:29,942 --> 00:26:33,150 ANDI PENG: Takže vy budete chcieť spínač je s prvým z tohto poľa, 516 00:26:33,150 --> 00:26:33,650 v poriadku? 517 00:26:33,650 --> 00:26:45,120 518 00:26:45,120 --> 00:26:46,850 To je začiatok, budem hovoriť. 519 00:26:46,850 --> 00:26:47,220 Dobre. 520 00:26:47,220 --> 00:26:50,386 Takže teraz, že ste vymenili prvé človek, čo chcete robiť po tom? 521 00:26:50,386 --> 00:26:54,840 Takže teraz vieme, že toto tu musí byť najmenšia hodnota, je to tak? 522 00:26:54,840 --> 00:26:58,310 Potom budete mať ďalšie odpočinok matice, ktorá je netriedený. 523 00:26:58,310 --> 00:27:01,569 Takže to, čo chcete robiť tu, ak máte chlapci chcú, aby mi ďalší riadok? 524 00:27:01,569 --> 00:27:04,610 Divákov: Takže chcete iterácii po zvyšok poľa. 525 00:27:04,610 --> 00:27:05,276 ANDI PENG: Jo. 526 00:27:05,276 --> 00:27:09,857 A tak to, čo robí iterácie druh znamenať pravdepodobne budeme potrebovať? 527 00:27:09,857 --> 00:27:10,440 Aký typ of-- 528 00:27:10,440 --> 00:27:12,057 >> Publikum: Oh, ďalší premenná? 529 00:27:12,057 --> 00:27:13,890 ANDI PENG: Pravdepodobne ďalšie pre sláčiky, je to tak? 530 00:27:13,890 --> 00:27:28,914 Takže sme pravdepodobne bude chcieť prechádzať through-- skvele. 531 00:27:28,914 --> 00:27:31,830 A potom ste sa vrátiť a Pravdepodobne skontrolovať minimálna znovu, 532 00:27:31,830 --> 00:27:32,100 v poriadku? 533 00:27:32,100 --> 00:27:34,975 A ty budeš stále opakovať to, pretože slučiek len tak 534 00:27:34,975 --> 00:27:36,010 zachovať systémom, nie? 535 00:27:36,010 --> 00:27:39,190 >> Tak ako vy môžete vidieť, my Len majú všeobecnú pseudocode 536 00:27:39,190 --> 00:27:41,480 o tom, ako chceme, aby tento program vyzerať. 537 00:27:41,480 --> 00:27:46,646 Tento ITERATE tu, čo máme typicky musieť napísať do nášho kódu 538 00:27:46,646 --> 00:27:49,270 ak chceme iterovat prostredníctvom pole, aký typ konštrukcie? 539 00:27:49,270 --> 00:27:51,030 Myslím si, že Christabel už povedal skôr. 540 00:27:51,030 --> 00:27:51,500 >> Divákov: A pre sláčiky. 541 00:27:51,500 --> 00:27:52,160 >> ANDI PENG: A pre sláčiky? 542 00:27:52,160 --> 00:27:52,770 Presne tak. 543 00:27:52,770 --> 00:27:56,060 Takže je to pravdepodobne Bude to pre slučku. 544 00:27:56,060 --> 00:27:59,240 Čo je to šek tu bude znamenať? 545 00:27:59,240 --> 00:28:02,536 Zvyčajne, ak chcete skontrolovať ak niečo je niečo else-- 546 00:28:02,536 --> 00:28:03,270 >> Divákov: Ak. 547 00:28:03,270 --> 00:28:06,790 >> ANDI PENG: if, že jo? 548 00:28:06,790 --> 00:28:10,790 A potom odkladacie tu, budeme prejsť neskôr, pretože David 549 00:28:10,790 --> 00:28:12,770 prešiel, že v prednáške rovnako. 550 00:28:12,770 --> 00:28:14,580 A potom druhá ITERATE implies-- 551 00:28:14,580 --> 00:28:15,120 >> Divákov: Ďalším pre sláčiky. 552 00:28:15,120 --> 00:28:16,745 >> ANDI PENG: --another pre sláčiky, presne tak. 553 00:28:16,745 --> 00:28:19,870 554 00:28:19,870 --> 00:28:22,000 Takže ak sa pozeráme na to správne, 555 00:28:22,000 --> 00:28:24,680 je vidieť, že sme pravdepodobne bude potrebovať vnorené pre sláčiky 556 00:28:24,680 --> 00:28:28,330 s podmieneného príkazu v tú a potom skutočný kus kódu, ktorý je 557 00:28:28,330 --> 00:28:31,360 chystá vymeniť hodnôt. 558 00:28:31,360 --> 00:28:35,980 Tak som práve všeobecne písaný kód tu pseudokód. 559 00:28:35,980 --> 00:28:38,910 A potom sme to vlastne bude fyzicky, ako trieda, 560 00:28:38,910 --> 00:28:40,700 pokúsiť sa realizovať to dnes. 561 00:28:40,700 --> 00:28:42,486 Vráťme sa do tohto IDE. 562 00:28:42,486 --> 00:28:49,243 563 00:28:49,243 --> 00:28:50,230 >> Uh Oh. 564 00:28:50,230 --> 00:28:51,754 Prečo je to ne-- je to tak. 565 00:28:51,754 --> 00:28:52,253 OK. 566 00:28:52,253 --> 00:28:55,834 567 00:28:55,834 --> 00:28:57,500 Ospravedlňujeme sa, ale dovoľte mi, aby som sa snaží priblížiť trochu viac. 568 00:28:57,500 --> 00:28:59,310 Tam sme ísť. 569 00:28:59,310 --> 00:29:05,060 Všetko, čo robím tu je, ktoré som vytvoril program s názvom "výber / sort.c." 570 00:29:05,060 --> 00:29:10,860 Som vytvoril rad deviatich hodnoty, 4, 8, 2, 1, 6, 9, 7, 5, 3. 571 00:29:10,860 --> 00:29:14,370 V súčasnej dobe, ako môžete vidieť, že sú neusporiadané. 572 00:29:14,370 --> 00:29:17,880 n bude číslo, ktoré vám povie množstvo hodnôt 573 00:29:17,880 --> 00:29:18,920 máte v poli. 574 00:29:18,920 --> 00:29:20,670 V tomto prípade sme majú deväť hodnoty. 575 00:29:20,670 --> 00:29:23,760 A ja som práve dostal na slučku tu že vytlačí netriedeného poľa. 576 00:29:23,760 --> 00:29:28,370 >> A na záver, som sa tiež dostal na slučky, že práve tlačí to znova. 577 00:29:28,370 --> 00:29:32,070 Takže teoreticky, ak je tento program pracuje správne, na konci, 578 00:29:32,070 --> 00:29:35,670 mali by ste vidieť tlačený pre sláčiky , V ktorom 1, 2, 3, 4, 5, 6, 7, 8, 579 00:29:35,670 --> 00:29:39,310 9 sú správne, aby. 580 00:29:39,310 --> 00:29:43,410 >> Takže máme našu pseudocode tu. 581 00:29:43,410 --> 00:29:46,090 Má niekto chcel to-- som len ísť požiadať o volunteers-- 582 00:29:46,090 --> 00:29:49,540 povedz mi presne, čo mám písať, pokiaľ Ak chceme, ako prvý, len opakovať 583 00:29:49,540 --> 00:29:52,840 prostredníctvom začiatku tohto poľa? 584 00:29:52,840 --> 00:29:55,204 Aký je riadok kódu, že som pravdepodobne bude potrebovať tu? 585 00:29:55,204 --> 00:29:56,990 >> Divákov: [Nepočuteľné] 586 00:29:56,990 --> 00:29:59,010 >> ANDI PENG: Jo, pocit zadarmo to-- Je nám ľúto, 587 00:29:59,010 --> 00:30:02,318 Nemusíte sa stať up-- pocit zatiaľ zvýšiť váš hlas trochu. 588 00:30:02,318 --> 00:30:08,190 >> Obecenstvo: pre int i rovná 0-- 589 00:30:08,190 --> 00:30:10,690 >> ANDI PENG: Jo, dobrý. 590 00:30:10,690 --> 00:30:15,220 >> Divákov: i je menšia ako dĺžka poľa. 591 00:30:15,220 --> 00:30:19,630 >> ANDI PENG: Takže majte na myseľ tu, pretože sme 592 00:30:19,630 --> 00:30:23,060 nemajú funkciu, ktorá us hovorí, že dĺžka poľa, 593 00:30:23,060 --> 00:30:25,790 už máme hodnota, ktorá ukladá, že. 594 00:30:25,790 --> 00:30:27,920 Je to tak? 595 00:30:27,920 --> 00:30:31,010 Ďalšia vec, ktorú majte v mind-- v poli 596 00:30:31,010 --> 00:30:33,940 deviatich hodnôt, aké sú indexy? 597 00:30:33,940 --> 00:30:38,720 Povedzme, že to pole bolo 0 až 3. 598 00:30:38,720 --> 00:30:41,500 Vidíte, že posledný index je v skutočnosti 3. 599 00:30:41,500 --> 00:30:45,530 Nie je to 4, aj keď tam je štyri hodnoty v poli. 600 00:30:45,530 --> 00:30:49,866 >> Takže tu, musíme byť veľmi opatrní na to, čo naše podmienky pre dĺžku 601 00:30:49,866 --> 00:30:50,490 bude. 602 00:30:50,490 --> 00:30:51,948 >> Divákov: Nebolo by to n mínus 1? 603 00:30:51,948 --> 00:30:54,440 ANDI PENG: Ide to n mínus 1, presne tak. 604 00:30:54,440 --> 00:30:57,379 Dáva to zmysel, prečo to je n mínus 1, všetci? 605 00:30:57,379 --> 00:30:58,920 Je to preto, že pole sú nula-indexované. 606 00:30:58,920 --> 00:31:02,010 Začnú na 0 a prevádzkovať až n mínus 1. 607 00:31:02,010 --> 00:31:03,210 Jo, je to trochu zložitejšie. 608 00:31:03,210 --> 00:31:03,730 OK. 609 00:31:03,730 --> 00:31:05,929 A potom-- 610 00:31:05,929 --> 00:31:08,054 Publikum: Isnt'1 že už postarané aj keď, 611 00:31:08,054 --> 00:31:11,400 jednoduchým nehovorí "menšie ako alebo presne "a len povedal:" menej ako? " 612 00:31:11,400 --> 00:31:13,108 >> ANDI PENG: To je naozaj dobrá otázka. 613 00:31:13,108 --> 00:31:13,630 Áno, áno. 614 00:31:13,630 --> 00:31:17,410 Ale tiež spôsob, akým sme vykonávanie kontroly právo, 615 00:31:17,410 --> 00:31:19,120 je potrebné porovnať dve hodnoty. 616 00:31:19,120 --> 00:31:21,009 Takže ste vlastne chcete nechajte "na" prázdny. 617 00:31:21,009 --> 00:31:23,050 Vzhľadom k tomu, ak si porovnať toto, vy nebudete 618 00:31:23,050 --> 00:31:25,530 nič po ňom porovnať, že jo? 619 00:31:25,530 --> 00:31:27,460 Jo. 620 00:31:27,460 --> 00:31:29,297 Takže aj ++. 621 00:31:29,297 --> 00:31:30,380 Poďme pridať naše držiaky. 622 00:31:30,380 --> 00:31:30,880 Jejda. 623 00:31:30,880 --> 00:31:33,950 624 00:31:33,950 --> 00:31:34,710 Skvelé. 625 00:31:34,710 --> 00:31:39,117 Takže máme začiatok našej vonkajšej slučky. 626 00:31:39,117 --> 00:31:41,450 Takže teraz pravdepodobne chcieť vytvoriť premennú pre vedenie 627 00:31:41,450 --> 00:31:43,085 Trať najmenšiu hodnotu, je to tak? 628 00:31:43,085 --> 00:31:45,751 Má niekto chcel mi dať riadok kódu, ktorý by to robil? 629 00:31:45,751 --> 00:31:48,700 630 00:31:48,700 --> 00:31:53,570 Čo budeme potrebovať, ak ideme chcieť uložiť niečo? 631 00:31:53,570 --> 00:31:55,047 >> Správne. 632 00:31:55,047 --> 00:31:57,630 Možno, že lepší názov pre to by be-- "temp" úplne works-- 633 00:31:57,630 --> 00:32:00,655 možno viac vhodne pomenovaný by bolo, ak chceme, aby najmenšie value-- 634 00:32:00,655 --> 00:32:01,624 >> Divákov: Min. 635 00:32:01,624 --> 00:32:02,790 ANDI PENG: min, tam ideme. 636 00:32:02,790 --> 00:32:05,230 min by bolo dobré. 637 00:32:05,230 --> 00:32:08,340 A tak tu to, čo my Chcete inicializovať ju? 638 00:32:08,340 --> 00:32:09,620 To je trochu zložitejšie. 639 00:32:09,620 --> 00:32:13,580 Pretože práve teraz u začiatok tohto poľa, 640 00:32:13,580 --> 00:32:15,730 ste sa pozrel na čokoľvek, že jo? 641 00:32:15,730 --> 00:32:19,200 Tak čo, automaticky, pokiaľ sme len na i rovná 0, 642 00:32:19,200 --> 00:32:22,302 to, čo chceme inicializovať naša prvá minimálna hodnota to? 643 00:32:22,302 --> 00:32:22,802 Divákov: i. 644 00:32:22,802 --> 00:32:24,790 ANDI PENG: i, presne tak. 645 00:32:24,790 --> 00:32:27,040 Christabel, prečo chceme, inicializovať to aj? 646 00:32:27,040 --> 00:32:28,510 >> Publikum: Vzhľadom k tomu, no, začíname s 0. 647 00:32:28,510 --> 00:32:31,660 Takže, pretože máme s čím porovnávať to je minimálny skončí na 0. 648 00:32:31,660 --> 00:32:32,451 >> ANDI PENG: Presne tak. 649 00:32:32,451 --> 00:32:34,400 Takže ona je presne to pravé. 650 00:32:34,400 --> 00:32:36,780 Pretože máme vlastne napriek tomu sa pozrel na čokoľvek, 651 00:32:36,780 --> 00:32:38,680 nevieme, čo naše minimálna hodnota. 652 00:32:38,680 --> 00:32:41,960 Chceme len inicializovať ju i, ktorá v súčasnej dobe, je tu. 653 00:32:41,960 --> 00:32:44,750 A ako budeme pokračovať presunúť dole toto pole, 654 00:32:44,750 --> 00:32:48,122 uvidíme, že s každým Ďalší priechod, aj zvýši. 655 00:32:48,122 --> 00:32:49,830 A tak sa v tomto bode, aj sa pravdepodobne bude 656 00:32:49,830 --> 00:32:52,329 že chcú byť minimálne, pretože to bude čokoľvek 657 00:32:52,329 --> 00:32:54,520 je začiatok netriedeného pole. 658 00:32:54,520 --> 00:32:55,270 Super. 659 00:32:55,270 --> 00:32:58,720 >> Takže teraz chcete pridať slučky for tu to je 660 00:32:58,720 --> 00:33:03,225 bude iterovat netriedený, alebo zvyšok tohto poľa. 661 00:33:03,225 --> 00:33:05,808 Má niekto chcel mi dať riadok kódu, ktorý by to robil? 662 00:33:05,808 --> 00:33:08,870 663 00:33:08,870 --> 00:33:11,330 Hint-- čo potrebujeme tu dole? 664 00:33:11,330 --> 00:33:17,320 665 00:33:17,320 --> 00:33:18,820 Čo sa deje ísť to pre sláčiky? 666 00:33:18,820 --> 00:33:19,465 Jo. 667 00:33:19,465 --> 00:33:21,590 Divákov: Tak sme chceli majú iný celé číslo, 668 00:33:21,590 --> 00:33:25,080 preto, že sme beží cez zvyšok matice namiesto I, možno 669 00:33:25,080 --> 00:33:25,760 j. 670 00:33:25,760 --> 00:33:27,301 >> ANDI PENG: Jo, j znie dobre. 671 00:33:27,301 --> 00:33:27,850 Rovná? 672 00:33:27,850 --> 00:33:33,930 >> Divákov: Takže by bolo aj plus 1, pretože začínate na ďalšiu hodnotu. 673 00:33:33,930 --> 00:33:40,395 A potom sa to znova end--, j je menej ako n mínus 1 a potom j ++. 674 00:33:40,395 --> 00:33:41,103 ANDI PENG: Skvelé. 675 00:33:41,103 --> 00:33:48,510 676 00:33:48,510 --> 00:33:52,750 >> A potom tu, budeme chcieť skontrolovať, či je splnená podmienka naša, 677 00:33:52,750 --> 00:33:53,250 v poriadku? 678 00:33:53,250 --> 00:33:55,740 Vzhľadom k tomu, že chcete zmeniť minimálnu hodnotu 679 00:33:55,740 --> 00:33:58,700 ak je to v skutočnosti menší, než to, čo ste prirovnal ju k, nie? 680 00:33:58,700 --> 00:34:01,146 Takže to, čo budeme chcieť v tú? 681 00:34:01,146 --> 00:34:04,160 682 00:34:04,160 --> 00:34:04,897 Skontrolujte. 683 00:34:04,897 --> 00:34:06,730 Aký typ vyhlásenia sme pravdepodobne bude 684 00:34:06,730 --> 00:34:08,389 tí chcete použiť, keby sme chcete skontrolovať niečo? 685 00:34:08,389 --> 00:34:09,360 >> Divákov: if. 686 00:34:09,360 --> 00:34:10,485 >> ANDI PENG: if. 687 00:34:10,485 --> 00:34:13,155 Tak if-- a čo to bude podmienka, že chceme dovnútra 688 00:34:13,155 --> 00:34:13,988 našej if? 689 00:34:13,988 --> 00:34:18,255 690 00:34:18,255 --> 00:34:22,960 >> AUDIENCE: V prípade, že hodnota j je menšia ako hodnota ja- 691 00:34:22,960 --> 00:34:24,600 >> ANDI PENG: Presne tak. 692 00:34:24,600 --> 00:34:27,480 Tak if-- tak toto pole sa nazýva "pole." 693 00:34:27,480 --> 00:34:27,980 Skvelé. 694 00:34:27,980 --> 00:34:30,465 Takže ak array-- čo to bolo? 695 00:34:30,465 --> 00:34:31,090 Zopakuj to. 696 00:34:31,090 --> 00:34:39,590 >> Divákov: Ak je pole-j je menšia ako array-i, potom by sme zmeniť min. 697 00:34:39,590 --> 00:34:41,590 Takže min by j. 698 00:34:41,590 --> 00:34:44,590 699 00:34:44,590 --> 00:34:47,249 >> ANDI PENG: Dáva to zmysel? 700 00:34:47,249 --> 00:34:48,670 OK. 701 00:34:48,670 --> 00:34:52,929 A teraz tu dole, sme vlastne chcú realizovať swap, že jo? 702 00:34:52,929 --> 00:34:58,285 Takže spomínate, v prednáške, že Dávid, keď sa snažil vymeniť the-- to, čo bolo 703 00:34:58,285 --> 00:34:59,996 to-- pomarančový džús a milk-- 704 00:34:59,996 --> 00:35:01,150 >> Divákov: To bolo hrubé. 705 00:35:01,150 --> 00:35:02,816 >> ANDI PENG: Jo, to bolo celkom hrubý. 706 00:35:02,816 --> 00:35:05,310 Ale bol to celkom dobrý koncept demonštrovať čas. 707 00:35:05,310 --> 00:35:08,430 Takže myslíte, že z vašich hodnôt tu. 708 00:35:08,430 --> 00:35:10,794 Máte poľa min, rad i, 709 00:35:10,794 --> 00:35:12,460 alebo čo sme sa pokúšali vymeniť tu. 710 00:35:12,460 --> 00:35:15,310 A ty asi nedá naliať ich do navzájom v rovnakú dobu, že? 711 00:35:15,310 --> 00:35:17,180 Tak čo s tým budeme musieť vytvoriť tu 712 00:35:17,180 --> 00:35:19,126 aby správne vymeniť hodnoty? 713 00:35:19,126 --> 00:35:19,820 >> Divákov: dočasné premenné. 714 00:35:19,820 --> 00:35:21,370 >> ANDI PENG: dočasné premenné. 715 00:35:21,370 --> 00:35:22,570 Takže poďme robiť int temp. 716 00:35:22,570 --> 00:35:25,681 Vidíš, to bude lepšie čas to-- hej, čo to bolo? 717 00:35:25,681 --> 00:35:26,180 OK. 718 00:35:26,180 --> 00:35:29,800 Takže by to bolo lepšie čas pomenovať premennú "Temp." 719 00:35:29,800 --> 00:35:30,730 Takže poďme robiť int temp. 720 00:35:30,730 --> 00:35:32,563 Čo budeme SET TEMP rovno tu? 721 00:35:32,563 --> 00:35:34,752 722 00:35:34,752 --> 00:35:35,335 Publikum: Min? 723 00:35:35,335 --> 00:35:38,508 724 00:35:38,508 --> 00:35:39,716 ANDI PENG: Je to trochu zložitejšie. 725 00:35:39,716 --> 00:35:43,110 726 00:35:43,110 --> 00:35:44,880 V skutočnosti nezáleží na tom, do konca roka. 727 00:35:44,880 --> 00:35:47,690 Nezáleží na tom, čo Poradie sa rozhodnete vymeniť v 728 00:35:47,690 --> 00:35:50,862 tak dlho, ako budete robiť istý, že ste sledovanie, čo ste swapovanie. 729 00:35:50,862 --> 00:35:52,250 >> Divákov: Mohlo by to byť array-i. 730 00:35:52,250 --> 00:35:53,666 >> ANDI PENG: Jo, poďme robiť pole-I. 731 00:35:53,666 --> 00:35:55,950 732 00:35:55,950 --> 00:35:59,305 A čo potom je ďalší riadok kódu chceme mať tu? 733 00:35:59,305 --> 00:36:00,680 Divákov: array-i rovná array-J. 734 00:36:00,680 --> 00:36:07,154 735 00:36:07,154 --> 00:36:08,070 ANDI PENG: A konečne? 736 00:36:08,070 --> 00:36:12,070 Divákov: array-j sa rovná array-i. 737 00:36:12,070 --> 00:36:14,525 Divákov: Alebo array-j rovná array-temp-- alebo teplota. 738 00:36:14,525 --> 00:36:17,135 739 00:36:17,135 --> 00:36:19,430 >> ANDI PENG: OK. 740 00:36:19,430 --> 00:36:21,510 Takže poďme bežať to a uvidíme, či to bude fungovať. 741 00:36:21,510 --> 00:36:37,520 742 00:36:37,520 --> 00:36:39,335 Tam, kde sa deje, že? 743 00:36:39,335 --> 00:36:40,210 Oh, to je problém. 744 00:36:40,210 --> 00:36:44,320 Pozri, na linke 40, my sme sa snaží používať pole-J? 745 00:36:44,320 --> 00:36:47,022 Ale kde j existujú iba v? 746 00:36:47,022 --> 00:36:48,402 >> Publikum: V cykle for. 747 00:36:48,402 --> 00:36:49,110 ANDI PENG: Správne. 748 00:36:49,110 --> 00:36:51,730 Tak čo s tým budeme musieť urobiť? 749 00:36:51,730 --> 00:36:53,170 >> Divákov: Definovať to vonku the-- 750 00:36:53,170 --> 00:36:57,777 751 00:36:57,777 --> 00:37:00,610 Publikum: Hej, myslím, že máš použiť iný if, že jo? 752 00:37:00,610 --> 00:37:05,230 Tak, ako v prípade, že minimum-- v poriadku, nechajte ma premýšľať. 753 00:37:05,230 --> 00:37:08,170 754 00:37:08,170 --> 00:37:09,990 >> ANDI peng: Chlapci, vyskúšajte sa pozrieť Poďme 755 00:37:09,990 --> 00:37:11,270 pozri, čo sa niečo, čo môžeme robiť? 756 00:37:11,270 --> 00:37:11,811 >> Divákov: OK. 757 00:37:11,811 --> 00:37:15,900 Takže v prípade, že minimálna nerovná j-- takže v prípade, že minimum je stále já-- 758 00:37:15,900 --> 00:37:17,570 potom by sme nemuseli vymeniť. 759 00:37:17,570 --> 00:37:22,450 760 00:37:22,450 --> 00:37:24,712 >> ANDI PENG: Znamená to, že rovné i? 761 00:37:24,712 --> 00:37:25,920 Čo chceš povedať tu? 762 00:37:25,920 --> 00:37:30,494 >> Publikum: Alebo jo, v prípade, že Minimálna nerovná i, jo. 763 00:37:30,494 --> 00:37:39,627 764 00:37:39,627 --> 00:37:40,210 ANDI PENG: OK. 765 00:37:40,210 --> 00:37:42,040 No, to rieši, druh, naše problémy. 766 00:37:42,040 --> 00:37:47,265 Ale to stále ešte nerieši problém z toho, čo sa stane, keď j-- od j 767 00:37:47,265 --> 00:37:49,890 neexistuje mimo neho, čo si chceme s tým robiť? 768 00:37:49,890 --> 00:37:50,698 Deklarovať to vonku? 769 00:37:50,698 --> 00:37:59,410 770 00:37:59,410 --> 00:38:02,730 Poďme skúsiť spustiť tento. 771 00:38:02,730 --> 00:38:04,435 Uh Oh. 772 00:38:04,435 --> 00:38:06,200 Náš druh nefunguje. 773 00:38:06,200 --> 00:38:10,060 >> Ako vidíte, naša pôvodná array mal tieto hodnoty. 774 00:38:10,060 --> 00:38:14,800 A potom by mal mať bol v 1, 2, 3, 4, 5, 6, 7, 8, 9. 775 00:38:14,800 --> 00:38:15,530 Nefunguje to. 776 00:38:15,530 --> 00:38:16,030 Ahh. 777 00:38:16,030 --> 00:38:17,184 Čo budeme robiť? 778 00:38:17,184 --> 00:38:17,850 Divákov: Debug. 779 00:38:17,850 --> 00:38:21,787 780 00:38:21,787 --> 00:38:23,370 ANDI PENG: Dobre, môžeme to skúsiť. 781 00:38:23,370 --> 00:38:25,030 Môžeme ladiť. 782 00:38:25,030 --> 00:38:26,042 Oddialenie trochu. 783 00:38:26,042 --> 00:38:31,177 784 00:38:31,177 --> 00:38:33,656 Vydajme našu zarážku. 785 00:38:33,656 --> 00:38:37,280 Poďme jako-- OK. 786 00:38:37,280 --> 00:38:40,444 >> Takže preto, že už vieme, že tieto riadky, 15 až 22, 787 00:38:40,444 --> 00:38:43,610 sú working-- pretože všetko, čo robím, je Len iterácie a printing-- 788 00:38:43,610 --> 00:38:45,406 Môžem ísť dopredu a vynechať to. 789 00:38:45,406 --> 00:38:47,280 Začnime na riadku 25. 790 00:38:47,280 --> 00:38:48,712 OOP, dovoľte mi, aby som sa zbaviť toho. 791 00:38:48,712 --> 00:38:51,598 792 00:38:51,598 --> 00:38:54,057 >> Divákov: Takže je zarážka kde začína ladenie? 793 00:38:54,057 --> 00:38:54,890 ANDI PENG: Or zastaví. 794 00:38:54,890 --> 00:38:55,670 Divákov: Or zastaví. 795 00:38:55,670 --> 00:38:55,930 ANDI PENG: Jo. 796 00:38:55,930 --> 00:38:58,640 Môžete nastaviť viac zarážky a to môže len skočiť z jedného na druhého. 797 00:38:58,640 --> 00:39:01,590 Ale v tomto prípade nevieme, kde je táto chyba deje. 798 00:39:01,590 --> 00:39:03,780 Tak sme sa len chcete začať od zhora nadol. 799 00:39:03,780 --> 00:39:05,020 Jo. 800 00:39:05,020 --> 00:39:05,550 OK. 801 00:39:05,550 --> 00:39:08,460 >> Takže táto linka tu, môžeme zasiahnuť. 802 00:39:08,460 --> 00:39:11,499 Môžete vidieť tu dole, máme pole. 803 00:39:11,499 --> 00:39:13,290 To sú hodnoty ktoré sú v poli. 804 00:39:13,290 --> 00:39:16,360 Vidíte, že, ako sa index 0, to zodpovedá value-- oh, 805 00:39:16,360 --> 00:39:17,526 Budem sa snažiť priblížiť. 806 00:39:17,526 --> 00:39:20,650 Ospravedlňujeme sa, ale je to naozaj ťažké na see-- na indexe pole 0, 807 00:39:20,650 --> 00:39:24,090 máme hodnotu 4 a potom tak ďalej a tak ďalej. 808 00:39:24,090 --> 00:39:25,670 Máme lokálne premenné. 809 00:39:25,670 --> 00:39:28,570 Práve teraz som sa rovná 0, čo chceme, aby to bolo. 810 00:39:28,570 --> 00:39:31,540 811 00:39:31,540 --> 00:39:33,690 >> A tak sa poďme držať krokovanie. 812 00:39:33,690 --> 00:39:36,850 Naše minimum je rovné 0, čo tiež chceme, aby to bolo. 813 00:39:36,850 --> 00:39:39,470 814 00:39:39,470 --> 00:39:45,560 A potom sme sa vstúpiť na náš druhý pre slučky, ak array-j je menšie ako pole-i, 815 00:39:45,560 --> 00:39:46,380 čo nebolo. 816 00:39:46,380 --> 00:39:48,130 Takže ste vidieť, ako že preskočil, že? 817 00:39:48,130 --> 00:39:52,430 >> Divákov: Takže ak by v prípade, minimum, všetko that-- nie že by to 818 00:39:52,430 --> 00:39:55,424 byť vnútri prvého cyklu for? 819 00:39:55,424 --> 00:39:57,340 ANDI PENG: Nie, pretože si napriek tomu chcete testovať. 820 00:39:57,340 --> 00:40:00,329 Chcete urobiť porovnanie každý čas, dokonca aj po spustení cez to. 821 00:40:00,329 --> 00:40:02,620 Nemusíte len chcem, aby to na prvé premietanie. 822 00:40:02,620 --> 00:40:05,240 Ak chcete to s každý ďalší zase priechod. 823 00:40:05,240 --> 00:40:07,198 Takže vy chcete skontrolovať Váš zdravotný stav vo vnútri. 824 00:40:07,198 --> 00:40:11,610 825 00:40:11,610 --> 00:40:13,746 Takže sme len tak udržujú v prevádzke tadiaľ. 826 00:40:13,746 --> 00:40:17,337 827 00:40:17,337 --> 00:40:18,420 Dám vám chlapci nápovedu. 828 00:40:18,420 --> 00:40:23,910 To má čo do činenia s tým, že pri máte kontrolu svoj podmienečný, 829 00:40:23,910 --> 00:40:26,600 nie ste kontrolu pre správne indexu. 830 00:40:26,600 --> 00:40:32,510 Takže teraz ste kontrola index poľa j je menšie ako pole 831 00:40:32,510 --> 00:40:33,970 index i. 832 00:40:33,970 --> 00:40:36,580 Ale to, čo robíš sa na počiatku pre slučky? 833 00:40:36,580 --> 00:40:38,260 Nie si nastavenie j rovnajúcu sa aj? 834 00:40:38,260 --> 00:40:41,260 835 00:40:41,260 --> 00:40:45,415 >> Jo, takže môžeme vlastne ukončite ladiaci tu. 836 00:40:45,415 --> 00:40:47,040 Takže poďme sa pozrieť na našu pseudokódu. 837 00:40:47,040 --> 00:40:50,070 838 00:40:50,070 --> 00:40:52,580 For-- ideme začiatok i rovná 0. 839 00:40:52,580 --> 00:40:54,760 Chystáme sa ísť až na n mínus 1. 840 00:40:54,760 --> 00:40:58,040 Poďme zistiť, sme mať toto právo? 841 00:40:58,040 --> 00:40:59,580 Jo, že mal pravdu. 842 00:40:59,580 --> 00:41:02,080 >> Takže tu vnútri, my sme bude vytvoriť minimálnu hodnotu 843 00:41:02,080 --> 00:41:03,630 a nastaviť, aby sa rovná aj. 844 00:41:03,630 --> 00:41:04,950 Vedeli sme to urobiť? 845 00:41:04,950 --> 00:41:06,270 Jo, to urobil. 846 00:41:06,270 --> 00:41:10,430 Teraz v našom vnútornom pre sláčiky, my sme robiť j rovná aj na n mínus 1. 847 00:41:10,430 --> 00:41:11,950 Vedeli sme to urobiť? 848 00:41:11,950 --> 00:41:15,540 Skutočne, my sme robili to. 849 00:41:15,540 --> 00:41:19,922 >> Tak Avšak to, čo sme porovnávanie tu? 850 00:41:19,922 --> 00:41:20,925 >> Divákov: j plus 1. 851 00:41:20,925 --> 00:41:21,716 ANDI PENG: Presne tak. 852 00:41:21,716 --> 00:41:24,184 853 00:41:24,184 --> 00:41:27,350 A potom budete chcieť nastaviť vaše minimálne rovná j plus 1 i. 854 00:41:27,350 --> 00:41:31,057 855 00:41:31,057 --> 00:41:32,640 Tak som šiel cez to naozaj rýchlo. 856 00:41:32,640 --> 00:41:36,190 Myslíte si chlapci pochopili prečo je to j plus 1? 857 00:41:36,190 --> 00:41:36,890 OK. 858 00:41:36,890 --> 00:41:40,700 >> Takže vo vašom poli, v vaše prvé priechod, 859 00:41:40,700 --> 00:41:44,850 Váš pre sláčiky, pre int i = 0, nech to jednoducho 860 00:41:44,850 --> 00:41:46,740 Predpokladám, že to ešte nebol zmenený. 861 00:41:46,740 --> 00:41:53,180 862 00:41:53,180 --> 00:41:56,760 Máme rad, úplne, len štyri netriedené prvky, nie? 863 00:41:56,760 --> 00:42:00,760 Takže chceme inicializovať aj rovná 0. 864 00:42:00,760 --> 00:42:03,650 A ja sa chystá práve prejsť tejto slučky. 865 00:42:03,650 --> 00:42:08,560 A tak sa v prvom prechode, ideme inicializovať premennú s názvom "min" 866 00:42:08,560 --> 00:42:11,245 že tiež sa rovná i, pretože nemáme minimálnu hodnotu. 867 00:42:11,245 --> 00:42:12,870 Tak, že je v súčasnej dobe presne 0 i. 868 00:42:12,870 --> 00:42:16,182 869 00:42:16,182 --> 00:42:17,640 A potom budeme prejsť. 870 00:42:17,640 --> 00:42:19,270 A my chceme, aby sa znovu opakovať. 871 00:42:19,270 --> 00:42:22,900 Teraz, keď sme našli to, čo náš minimálny je, chceme iterovat 872 00:42:22,900 --> 00:42:25,190 znovu vidieť, či je to porovnanie, je to tak? 873 00:42:25,190 --> 00:42:40,440 Tak j, tu, sa deje na rovné aj, čo je 0. 874 00:42:40,440 --> 00:42:46,320 A potom, ak array j a i, ktorý je ten, ktorý je ďalší nad, as menej 875 00:42:46,320 --> 00:42:49,270 než to, čo aktuálne minimum je hodnota, ktoré chcete vymeniť. 876 00:42:49,270 --> 00:42:56,850 >> Takže povedzme, že máme má, rovnako ako, 2, 5, 1, 8. 877 00:42:56,850 --> 00:43:01,610 Práve teraz, aj je rovné 0 a j je rovné 0. 878 00:43:01,610 --> 00:43:05,210 A to je náš minimálna hodnota. 879 00:43:05,210 --> 00:43:09,950 Ak je pole-j a ja-, takže v prípade, že raz to je po jednom pozeráme 880 00:43:09,950 --> 00:43:13,450 je väčší ako ten pred tým, to bude stáť minimum. 881 00:43:13,450 --> 00:43:18,120 >> Takže tu vidíme, že 5 nie je menšia ako to. 882 00:43:18,120 --> 00:43:19,730 Takže to bude nebyť 5. 883 00:43:19,730 --> 00:43:23,580 Vidíme, že 1 je menšia ako 2, nie? 884 00:43:23,580 --> 00:43:32,970 Takže teraz vieme, že naše minimum je bude hodnota indexu pri 0, 1, 2. 885 00:43:32,970 --> 00:43:34,030 Jo? 886 00:43:34,030 --> 00:43:39,170 A potom, keď sa dostanete sem, môžete vymeniť správne hodnoty. 887 00:43:39,170 --> 00:43:42,610 >> Takže keď vy ste boli len mať j Ako ste sa nepozerali na jednom 888 00:43:42,610 --> 00:43:43,260 po ňom. 889 00:43:43,260 --> 00:43:44,520 Vy ste pri pohľade na rovnaká hodnota, ktorá 890 00:43:44,520 --> 00:43:46,290 je dôvod, prečo to jednoducho nič nerobím. 891 00:43:46,290 --> 00:43:49,721 Znamená to, že zmysel pre každého, Preto sme potrebovali, aby plus 1 tam? 892 00:43:49,721 --> 00:43:50,220 OK. 893 00:43:50,220 --> 00:43:53,345 Teraz stačí spustiť cez neho, aby sa Uistite sa, že zvyšok je kód správny. 894 00:43:53,345 --> 00:44:04,424 895 00:44:04,424 --> 00:44:05,340 Prečo sa deje, že? 896 00:44:05,340 --> 00:44:14,780 897 00:44:14,780 --> 00:44:16,364 Ach, to je min tu. 898 00:44:16,364 --> 00:44:17,780 Boli sme nákupný nesprávnu hodnotu. 899 00:44:17,780 --> 00:44:24,944 900 00:44:24,944 --> 00:44:25,906 Ale nie. 901 00:44:25,906 --> 00:44:30,720 902 00:44:30,720 --> 00:44:33,482 >> Ach jo, tu dole sme boli vymení nesprávne hodnoty rovnako. 903 00:44:33,482 --> 00:44:34,940 Pretože sme sa pozerali na i a j. 904 00:44:34,940 --> 00:44:36,440 To sú tie, ktoré sme kontrolovali. 905 00:44:36,440 --> 00:44:39,160 Vlastne chceme swap minimum, súčasná minimálna, 906 00:44:39,160 --> 00:44:40,550 s tým, čo jeden vonku je. 907 00:44:40,550 --> 00:44:59,510 908 00:44:59,510 --> 00:45:05,402 A ako vy môžete vidieť dole tu, máme zoradené pole. 909 00:45:05,402 --> 00:45:07,110 Je to jednoducho musel urobiť s skutočnosť, že, keď 910 00:45:07,110 --> 00:45:09,350 sme boli zaškrtnutím Hodnoty sme porovnávanie 911 00:45:09,350 --> 00:45:11,226 sme sa nepozerali na správnych hodnotách. 912 00:45:11,226 --> 00:45:13,850 Pozerali sme sa na rovnakej jednom tu, nie v skutočnosti ju vymeniť. 913 00:45:13,850 --> 00:45:17,135 Musíte sa pozrieť na ten budúci k nej a potom môžete vymeniť. 914 00:45:17,135 --> 00:45:19,260 Takže to je to, čo bolo celkom Pred odpočúvanie náš kód. 915 00:45:19,260 --> 00:45:22,460 A to, čo tu urobil som všetko, čo je ladiaci program mohol urobiť pre teba 916 00:45:22,460 --> 00:45:23,810 Len som to urobil na doska, pretože je to jednoduchšie, 917 00:45:23,810 --> 00:45:26,320 vidieť, skôr než sa snažiť priblížite debuggera. 918 00:45:26,320 --> 00:45:29,391 Znamená to, že zmysel pre všetkých? 919 00:45:29,391 --> 00:45:29,890 Super. 920 00:45:29,890 --> 00:45:34,800 921 00:45:34,800 --> 00:45:35,410 >> Dobre. 922 00:45:35,410 --> 00:45:41,070 Môžeme prejsť k hovoriť o asymptotickej notácie, ktorý 923 00:45:41,070 --> 00:45:44,580 je len fantázia spôsob, ako hovoriť runtimes všetkých týchto druhov. 924 00:45:44,580 --> 00:45:47,650 Takže viem, Davida, v prednáške, dotkla runtime. 925 00:45:47,650 --> 00:45:52,124 A išiel cez celý vzorca o tom, ako vypočítať doby chodu. 926 00:45:52,124 --> 00:45:53,040 Žiadne obavy o tom. 927 00:45:53,040 --> 00:45:54,660 Ak ste naozaj zvedavý na, ako to funguje, 928 00:45:54,660 --> 00:45:55,810 neváhajte sa mnou hovoriť po bode. 929 00:45:55,810 --> 00:45:57,560 Môžeme prejsť formula dohromady. 930 00:45:57,560 --> 00:46:00,689 Ale vy všetci chalani majú naozaj viem, je, že n na druhú nad 2 931 00:46:00,689 --> 00:46:01,980 je to isté ako n na druhú. 932 00:46:01,980 --> 00:46:04,710 Vzhľadom k tomu, najväčšieho počtu, exponent, rastie najviac. 933 00:46:04,710 --> 00:46:06,590 A tak sa pre naše účely, všetko sa staráme o 934 00:46:06,590 --> 00:46:09,470 je to, že obrie číslo, ktoré rastie. 935 00:46:09,470 --> 00:46:13,340 >> Takže to, čo je najlepšie prípad runtime výberového druhu? 936 00:46:13,340 --> 00:46:15,830 Ak sa chystáte mať iterovat zoznamom 937 00:46:15,830 --> 00:46:18,712 a potom iterovat zvyšok tohto zoznamu, 938 00:46:18,712 --> 00:46:20,420 koľkokrát sú budete pravdepodobne, 939 00:46:20,420 --> 00:46:24,612 v najhoršom case-- v najlepšom prípade, sorry-- prebehnúť? 940 00:46:24,612 --> 00:46:27,070 Možno lepšia otázka je sa opýtať, čo je najhorší prípad 941 00:46:27,070 --> 00:46:28,153 runtime výberového druhu. 942 00:46:28,153 --> 00:46:29,366 Divákov: n na druhú. 943 00:46:29,366 --> 00:46:30,740 ANDI PENG: Je to n na druhú, vpravo. 944 00:46:30,740 --> 00:46:36,986 Tak jednoduchý spôsob, ako myslieť, je to ako, kedykoľvek budete mať dvoch vnorených pre slučky, 945 00:46:36,986 --> 00:46:38,110 to bude n druhú. 946 00:46:38,110 --> 00:46:40,386 Pretože sú nielen vám preteká opäť, 947 00:46:40,386 --> 00:46:42,260 musíte sa vrátiť okolo a skrz nej prechádzajú 948 00:46:42,260 --> 00:46:44,980 opäť dovnútra pre každú hodnotu. 949 00:46:44,980 --> 00:46:48,640 Takže v tomto prípade, vediete n časy n na druhú, čo je-- ľúto, 950 00:46:48,640 --> 00:46:50,505 n krát n, ktorý sa rovná n na druhú. 951 00:46:50,505 --> 00:46:53,230 952 00:46:53,230 --> 00:46:56,360 >> A druh je tiež trochu unikátna v tom zmysle 953 00:46:56,360 --> 00:46:59,774 že ak nemá tieto nevadí hodnoty sú už v poriadku. 954 00:46:59,774 --> 00:47:01,440 Je to stále bude prebehnúť tak ako tak. 955 00:47:01,440 --> 00:47:03,872 Povedzme, že to bolo 1, 2, 3, 4. 956 00:47:03,872 --> 00:47:07,080 Bez ohľadu na to, či to bolo v poriadok, to ešte by prebehol 957 00:47:07,080 --> 00:47:08,620 a ešte skontroloval minimálnu hodnotu. 958 00:47:08,620 --> 00:47:10,100 To by robili Rovnaký počet kontrol 959 00:47:10,100 --> 00:47:12,780 zakaždým, aj keď je robil nie vlastne sa ničoho dotknúť. 960 00:47:12,780 --> 00:47:16,940 >> Takže v tomto prípade, že najlepšie a najhoršie runtime sú skutočne rovnocenné. 961 00:47:16,940 --> 00:47:19,160 Takže očakávané runtime výberového druhu, 962 00:47:19,160 --> 00:47:23,790 ktoré označujeme symbolom of theta, theta, v tomto prípade, 963 00:47:23,790 --> 00:47:24,790 by tiež bolo n druhú. 964 00:47:24,790 --> 00:47:26,480 Všetci traja z nich by sa n druhú. 965 00:47:26,480 --> 00:47:29,653 Je každý jasné, prečo runtime je n na druhú? 966 00:47:29,653 --> 00:47:33,360 967 00:47:33,360 --> 00:47:33,980 >> Dobre. 968 00:47:33,980 --> 00:47:39,120 Takže ja som jednoducho ísť rýchlo spúšťať cez zvyšok druhov. 969 00:47:39,120 --> 00:47:41,137 Algoritmus pre bublina sort-- pamätať, 970 00:47:41,137 --> 00:47:43,220 to bol prvý David prešiel na prednáške. 971 00:47:43,220 --> 00:47:46,000 V podstate si krok celý zoznam 972 00:47:46,000 --> 00:47:48,950 a vy ste práve swap-- Porovnať dve naraz. 973 00:47:48,950 --> 00:47:51,350 A ak jeden je väčší, ako ste práve ich vymeniť. 974 00:47:51,350 --> 00:47:53,590 Takže ak sú väčšie, mali by ste vymeniť. 975 00:47:53,590 --> 00:47:56,180 Mám oficiálne tu. 976 00:47:56,180 --> 00:47:59,100 >> Takže povedzme, že ste mali 8, 6, 4, 2. 977 00:47:59,100 --> 00:48:00,571 Vy by ste porovnať 8 a 6. 978 00:48:00,571 --> 00:48:01,570 Vy by ste potrebné ich vymeniť. 979 00:48:01,570 --> 00:48:02,610 Tie by sa porovnávať 8 a 4. 980 00:48:02,610 --> 00:48:03,609 Vy by ste potrebné ich vymeniť. 981 00:48:03,609 --> 00:48:07,000 Ak musíte vymeniť 8 a je 2, zmena je tiež. 982 00:48:07,000 --> 00:48:10,760 Takže v tom zmysle, môžete vidieť, odohrávajúce sa po dlhú dobu, 983 00:48:10,760 --> 00:48:13,730 ako hodnoty druh bublinu konca, čo je dôvod, prečo hovoríme 984 00:48:13,730 --> 00:48:15,320 bublinkové radenie. 985 00:48:15,320 --> 00:48:19,950 >> Radi by sme len prejsť znovu náš druhý priechod, a naše tretie priechod, 986 00:48:19,950 --> 00:48:21,150 a náš štvrtom priechodu. 987 00:48:21,150 --> 00:48:25,820 V podstate, bublinkové radenie práve beží kým neurobíte žiadne ďalšie swapy. 988 00:48:25,820 --> 00:48:31,109 Takže v tomto zmysle, je to len všeobecný pseudokód pre neho. 989 00:48:31,109 --> 00:48:32,650 Žiadne starosti, to všetko bude on-line. 990 00:48:32,650 --> 00:48:34,990 Nemusíme sa vlastne ísť cez tento. 991 00:48:34,990 --> 00:48:38,134 >> Práve sme inicializovať čítač premenná, ktorá začína na 0 ° C. 992 00:48:38,134 --> 00:48:39,800 A my iterovat celé pole. 993 00:48:39,800 --> 00:48:43,420 A ak jedna hodnota je--, pokiaľ to hodnota je väčšia ako táto hodnota, 994 00:48:43,420 --> 00:48:44,610 budete sa ich vymeniť. 995 00:48:44,610 --> 00:48:46,860 A potom ste len bude pokračovať. 996 00:48:46,860 --> 00:48:47,970 A budete počítať. 997 00:48:47,970 --> 00:48:50,845 A vy len tak, aby robil to, keď prebieha meranie, je väčšia 998 00:48:50,845 --> 00:48:53,345 ako 0, čo znamená, že zakaždým, budete musieť vymeniť, 999 00:48:53,345 --> 00:48:55,220 viete, že chcete ísť späť a znovu skontrolujte. 1000 00:48:55,220 --> 00:48:59,510 Chcete zachovať kontrolu, kým nebudete vedieť že vy nemusíte vymeniť ešte. 1001 00:48:59,510 --> 00:49:05,570 >> Takže aké sú najlepšie a najhoršie puzdro behové moduly pre bubble druhu? 1002 00:49:05,570 --> 00:49:09,300 A hint-- je to vlastne líši od výberu druhu v tom zmysle, 1003 00:49:09,300 --> 00:49:11,810 že tieto dve odpovede nie sú rovnaké. 1004 00:49:11,810 --> 00:49:14,709 Premýšľajte o tom, čo by sa stalo v prípad, ak to bolo už zoradené. 1005 00:49:14,709 --> 00:49:16,500 A premýšľať o tom, čo by sa stalo, keby to bolo 1006 00:49:16,500 --> 00:49:18,372 v prípade, v ktorom nebola zoradené. 1007 00:49:18,372 --> 00:49:20,580 A môžete trochu spustiť cez prečo sa to deje. 1008 00:49:20,580 --> 00:49:22,954 Dám ti chalani, ako, 30 sekúnd o tom premýšľať. 1009 00:49:22,954 --> 00:49:52,330 1010 00:49:52,330 --> 00:49:53,540 >> OK. 1011 00:49:53,540 --> 00:49:57,462 Má niekto uhádnuť, čo je Najhorší prípad runtime bublinkovej druhu je? 1012 00:49:57,462 --> 00:49:57,962 Jo. 1013 00:49:57,962 --> 00:50:07,810 >> Divákov: Bolo by to, ako, n krát n mínus 1, alebo niečo také? 1014 00:50:07,810 --> 00:50:10,650 Rovnako ako zakaždým, keď beží, je to len, ako, jeden menej odkladacia 1015 00:50:10,650 --> 00:50:10,960 že to, čo to bolo. 1016 00:50:10,960 --> 00:50:12,668 >> ANDI PENG: Jo, tak máš úplnú pravdu. 1017 00:50:12,668 --> 00:50:15,940 A to je prípad, kedy vaše Odpoveď bola v skutočnosti oveľa zložitejšie 1018 00:50:15,940 --> 00:50:17,240 než je tá, ktorú treba dať. 1019 00:50:17,240 --> 00:50:19,772 Takže to bude run-- Som chystá vymazať všetko tu. 1020 00:50:19,772 --> 00:50:20,480 Sú všetci dobre? 1021 00:50:20,480 --> 00:50:21,869 Môžem vymazať to? 1022 00:50:21,869 --> 00:50:22,368 OK. 1023 00:50:22,368 --> 00:50:27,904 1024 00:50:27,904 --> 00:50:30,320 Budete prejsť n Časy sa prvýkrát, že? 1025 00:50:30,320 --> 00:50:33,200 A idú prejsť n mínus 1 druhýkrát, je to tak? 1026 00:50:33,200 --> 00:50:37,130 A potom budete mať deje, n Mine 2, a tak ďalej. 1027 00:50:37,130 --> 00:50:40,210 David to urobil v prednáške, kde, Ak ste pridali všetky tieto hodnoty, 1028 00:50:40,210 --> 00:50:48,080 dostanete niečo, čo je jako-- yeah-- nad 2, ktorý v podstate len znižuje 1029 00:50:48,080 --> 00:50:49,784 až n na druhú. 1030 00:50:49,784 --> 00:50:51,700 Budeš sa dostať divný frakcie tam. 1031 00:50:51,700 --> 00:50:53,892 A tak len viem, že n na druhú vždy 1032 00:50:53,892 --> 00:50:55,350 má prednosť pred frakcie. 1033 00:50:55,350 --> 00:50:58,450 A tak v tomto prípade, najhoršie runtime by n druhú. 1034 00:50:58,450 --> 00:51:00,210 Ak by to bolo v zostupnom objednávka, myslieť si, 1035 00:51:00,210 --> 00:51:02,530 musieť urobiť swap zakaždým. 1036 00:51:02,530 --> 00:51:05,170 >> Aký by mal byť, potenciálne, najlepšom prípade runtime? 1037 00:51:05,170 --> 00:51:08,580 Povedzme, v prípade, že zoznam bol už v poriadku, čo by runtime byť? 1038 00:51:08,580 --> 00:51:09,565 >> Divákov: n. 1039 00:51:09,565 --> 00:51:10,690 ANDI PENG: Je to n, presne tak. 1040 00:51:10,690 --> 00:51:11,600 A prečo je to n? 1041 00:51:11,600 --> 00:51:13,850 Divákov: Pretože ste práve musieť skontrolovať každý raz. 1042 00:51:13,850 --> 00:51:14,770 ANDI PENG: Presne tak. 1043 00:51:14,770 --> 00:51:17,150 Takže v tom najlepšom možnom behu, Pokiaľ tento zoznam bol už 1044 00:51:17,150 --> 00:51:20,270 sorted-- povedzme 1, 2, 3, 4-- vy by len prejsť, mali by ste skontrolovať, 1045 00:51:20,270 --> 00:51:21,720 by ste vidieť, oh, všetci vyjsť. 1046 00:51:21,720 --> 00:51:22,636 Nemusel som sa vymeniť. 1047 00:51:22,636 --> 00:51:23,370 Skončil som. 1048 00:51:23,370 --> 00:51:26,500 Takže v tomto prípade, je to len n alebo počet krokov, ktoré práve 1049 00:51:26,500 --> 00:51:29,870 musel skontrolovať v prvom zozname. 1050 00:51:29,870 --> 00:51:33,990 >> A potom, čo sme teraz hit insertion sort, kde 1051 00:51:33,990 --> 00:51:39,260 algoritmus je v podstate rozdeliť to do triedeného aj netriedeného časť. 1052 00:51:39,260 --> 00:51:42,810 A potom jeden po druhom, netriedeného hodnoty 1053 00:51:42,810 --> 00:51:46,880 vložené do ich vhodnej pozície v začiatku zoznamu. 1054 00:51:46,880 --> 00:51:52,120 >> Tak napríklad, máme Zoznam 3, 5, 2, 6, 4 znova. 1055 00:51:52,120 --> 00:51:54,750 Vieme, že je to v súčasnej dobe netriedený preto, že sme jednoducho 1056 00:51:54,750 --> 00:51:57,030 začal na to pozerať. 1057 00:51:57,030 --> 00:52:00,610 Sme sa pozrieť, a my vieme, že Prvá hodnota je triedený, že jo? 1058 00:52:00,610 --> 00:52:04,190 Ak ste len pri pohľade na rad veľkosť jedného, ​​viete, že je to triediť. 1059 00:52:04,190 --> 00:52:08,230 >> Takže vieme, že ďalšie štyri sú netriedený. 1060 00:52:08,230 --> 00:52:10,980 Prechádzame a vidíme, že hodnoty. 1061 00:52:10,980 --> 00:52:11,730 Poďme späť. 1062 00:52:11,730 --> 00:52:13,130 Vidíte tú hodnotu 5? 1063 00:52:13,130 --> 00:52:14,110 Pozrieme sa na to. 1064 00:52:14,110 --> 00:52:15,204 My porovnať ju s 3. 1065 00:52:15,204 --> 00:52:17,870 Vieme, že to je väčšia než 3, takže vieme, že to je triediť. 1066 00:52:17,870 --> 00:52:22,940 Takže vieme, že prvé dva sú radené a posledné tri nie sú. 1067 00:52:22,940 --> 00:52:24,270 >> Sme sa pozrieť na 2. 1068 00:52:24,270 --> 00:52:25,720 Prvý sme skontrolovať s 5. 1069 00:52:25,720 --> 00:52:26,700 Je to menej ako 5? 1070 00:52:26,700 --> 00:52:27,240 To nie je. 1071 00:52:27,240 --> 00:52:29,510 Takže musíme hľadať ďalej nadol. 1072 00:52:29,510 --> 00:52:30,940 Potom môžete skontrolovať 2 VYP 3. 1073 00:52:30,940 --> 00:52:31,850 Je to menej ako? 1074 00:52:31,850 --> 00:52:32,350 Nie. 1075 00:52:32,350 --> 00:52:35,430 Takže viete, 2 musí byť vložená Na prednej a 3 a 5 1076 00:52:35,430 --> 00:52:38,200 obaja majú byť vytlačený. 1077 00:52:38,200 --> 00:52:42,190 Urobte to opäť s 6 a 4. 1078 00:52:42,190 --> 00:52:48,962 A my sme jednoducho udržať kontrolu v podstate, kde sme len skontrolovať, skontrolovať, skontrolovať. 1079 00:52:48,962 --> 00:52:51,170 A kým to je v práve postavenie, sme trochu proste 1080 00:52:51,170 --> 00:52:54,890 vložte ju do správnej polohy, čo je miesto, kde názov pochádza. 1081 00:52:54,890 --> 00:52:59,830 >> Tak to je len algoritmus, pseudokód per sa, druh, 1082 00:52:59,830 --> 00:53:04,990 o tom, ako by sme realizovať inzercia triedenia. 1083 00:53:04,990 --> 00:53:05,954 Pseudokód je tu. 1084 00:53:05,954 --> 00:53:06,620 Je to všetko online. 1085 00:53:06,620 --> 00:53:10,720 Žiadne starosti, či vy ste sa snaží kopírovať to dole. 1086 00:53:10,720 --> 00:53:14,500 Takže ešte raz, čo rovnaký question-- by bolo najlepšie a najhoršie runtime 1087 00:53:14,500 --> 00:53:16,120 vkladanie druhu? 1088 00:53:16,120 --> 00:53:17,750 Je to veľmi podobné na poslednú otázku. 1089 00:53:17,750 --> 00:53:20,479 Dám ti chalani, ako, 30 sekúnd premýšľať o tom rovnako. 1090 00:53:20,479 --> 00:53:47,150 1091 00:53:47,150 --> 00:53:50,071 >> OK Má niekto chcel daj mi najhoršie runtime? 1092 00:53:50,071 --> 00:53:50,570 Jo. 1093 00:53:50,570 --> 00:53:51,490 >> Divákov: n na druhú. 1094 00:53:51,490 --> 00:53:52,573 >> ANDI PENG: Je to n na druhú. 1095 00:53:52,573 --> 00:53:53,730 A prečo je to n na druhú? 1096 00:53:53,730 --> 00:53:57,562 >> Publikum: Pretože v obrátenom poradí, máte 1097 00:53:57,562 --> 00:54:02,619 prejsť n n časy, čo je-- 1098 00:54:02,619 --> 00:54:03,660 ANDI PENG: Jo, presne tak. 1099 00:54:03,660 --> 00:54:06,610 Takže to isté ako v bubline druhu. 1100 00:54:06,610 --> 00:54:08,720 Pokiaľ tento zoznam je v zostupnom poradí, ty si 1101 00:54:08,720 --> 00:54:11,240 bude musieť skontrolovať prvý raz. 1102 00:54:11,240 --> 00:54:13,470 A potom sa s každým ďalšie hodnotu, že ste 1103 00:54:13,470 --> 00:54:16,390 musieť pozrieť sa na to proti každý hodnota, je to tak? 1104 00:54:16,390 --> 00:54:20,290 A tak úplne, budete robiť an časy n prihrávka ďalšie n pasu, ktorý 1105 00:54:20,290 --> 00:54:21,750 n je na druhú. 1106 00:54:21,750 --> 00:54:22,860 A čo najlepšom prípade? 1107 00:54:22,860 --> 00:54:24,360 Jo. 1108 00:54:24,360 --> 00:54:28,840 >> Divákov: n mínus 1, pretože Prvý z nich je už na druhú. 1109 00:54:28,840 --> 00:54:30,270 >> ANDI PENG: Tak blízko. 1110 00:54:30,270 --> 00:54:31,850 Odpoveď je vlastne n. 1111 00:54:31,850 --> 00:54:37,189 Vzhľadom k tomu, pričom prvý z nich je radené, nemusí to actually-- 1112 00:54:37,189 --> 00:54:38,980 sme jednoducho kľučku, v že príklad, že 2 1113 00:54:38,980 --> 00:54:40,930 sa stalo, že je najmenší číslo. 1114 00:54:40,930 --> 00:54:43,680 Ale to nie je tak byť vždy. 1115 00:54:43,680 --> 00:54:48,040 V prípade 2 sa už zoradená na začiatku ale vyzeráš, a tam je 1 tu, 1116 00:54:48,040 --> 00:54:49,144 1 bude to rana. 1117 00:54:49,144 --> 00:54:51,060 A to skončí bytia odpichov tak ako tak. 1118 00:54:51,060 --> 00:54:56,250 >> Takže v najlepšom prípade, je to vlastne len bude n. 1119 00:54:56,250 --> 00:54:59,090 Ak máte 1, 2, 3, 4, 5, 6, 7, 8, ty si 1120 00:54:59,090 --> 00:55:00,940 sa prejsť že celý zoznam raz 1121 00:55:00,940 --> 00:55:03,430 skontrolovať, či je všetko v poriadku. 1122 00:55:03,430 --> 00:55:07,390 Je každý jasno v chode časy výberu rovnako? 1123 00:55:07,390 --> 00:55:09,960 Ja viem, že som prechádzal ty naozaj rýchlo. 1124 00:55:09,960 --> 00:55:13,330 Ale viem, že ak viete, všeobecné koncepty, mali by ste byť dobre. 1125 00:55:13,330 --> 00:55:16,070 OK. 1126 00:55:16,070 --> 00:55:19,790 Tak som si len dať chlapci možno, rovnako ako, minútu sa poraďte so svojím susedom 1127 00:55:19,790 --> 00:55:21,890 o tom, čo to sú len niektoré z hlavných rozdielov 1128 00:55:21,890 --> 00:55:23,540 medzi týmito typmi druhov. 1129 00:55:23,540 --> 00:56:24,571 1130 00:56:24,571 --> 00:56:25,570 Pôjdeme cez to skoro. 1131 00:56:25,570 --> 00:56:26,444 Publikum: Oh, OK. 1132 00:56:26,444 --> 00:56:27,320 ANDI PENG: Jo. 1133 00:56:27,320 --> 00:56:28,380 OK. 1134 00:56:28,380 --> 00:56:33,420 Cool, poďme znovu zídu ako trieda. 1135 00:56:33,420 --> 00:56:34,330 OK. 1136 00:56:34,330 --> 00:56:37,579 Takže to bolo celkom otvorená otázka v tom zmysle, 1137 00:56:37,579 --> 00:56:39,120 že je tu veľa odpovedí na ne. 1138 00:56:39,120 --> 00:56:40,746 A pôjdeme cez niektoré z nich stručne. 1139 00:56:40,746 --> 00:56:43,411 Chcel som, aby vám chlapci premýšľať o tom, čo diferencované 1140 00:56:43,411 --> 00:56:44,530 všetky tri typy druhov. 1141 00:56:44,530 --> 00:56:47,440 A ja som počul tiež, veľký question-- čo merge sort robiť? 1142 00:56:47,440 --> 00:56:50,110 Výborná otázka, pretože to je to, čo sme pokrývať ďalšie. 1143 00:56:50,110 --> 00:56:52,850 >> Tak zlúčiť sort človek druh, ktorý funguje 1144 00:56:52,850 --> 00:56:56,100 veľmi odlišne od ostatných druhov. 1145 00:56:56,100 --> 00:56:58,180 Ako vy môžete see-- David urobil, že demo 1146 00:56:58,180 --> 00:57:01,130 kde mal všetko v pohode zvuky keď vidí, ako zlúčiť 1147 00:57:01,130 --> 00:57:04,010 triedenie bežal, ako, nekonečne rýchlejšie, než ostatní dva typy? 1148 00:57:04,010 --> 00:57:04,510 OK. 1149 00:57:04,510 --> 00:57:07,580 Tak to je preto, že zlúčenie triediť implementuje, ktoré rozdeľujú 1150 00:57:07,580 --> 00:57:11,020 a podmaniť si predstavu, že sme hovoril o veľa v prednáške. 1151 00:57:11,020 --> 00:57:14,550 V tom zmysle, že sme chceli pracovať múdrejší, nie ťažšie, keď ste rozdeliť 1152 00:57:14,550 --> 00:57:18,120 a podmaniť si problémy, a rozdeľujú ich nadol, a potom dať dohromady, 1153 00:57:18,120 --> 00:57:19,930 dobré veci sa vždy stane. 1154 00:57:19,930 --> 00:57:21,960 >> Tak tak, že zlúčenie sort v podstate funguje 1155 00:57:21,960 --> 00:57:24,660 je, že sa rozdeľuje netriedené poľa na polovicu. 1156 00:57:24,660 --> 00:57:26,500 A potom to má dve polovice polí. 1157 00:57:26,500 --> 00:57:28,220 A to len triedi tieto dve polovice. 1158 00:57:28,220 --> 00:57:31,750 Je to jednoducho stále delenie na polovicu, v polovica, v polovici kým všetko je radený 1159 00:57:31,750 --> 00:57:33,680 a potom rekurzívne dáva to všetko dohromady. 1160 00:57:33,680 --> 00:57:36,550 >> Tak to je naozaj abstraktné. 1161 00:57:36,550 --> 00:57:38,750 Tak to je len trochu pseudokódu. 1162 00:57:38,750 --> 00:57:41,040 Znamená to, že zmysel v ako to beží? 1163 00:57:41,040 --> 00:57:43,870 Takže povedzme, že máte poľa n elementy, že jo? 1164 00:57:43,870 --> 00:57:45,450 Ak n je menší ako 2, môžete sa vrátiť. 1165 00:57:45,450 --> 00:57:49,040 Vzhľadom k tomu, viete, že či existuje len jedna vec, musí byť radené. 1166 00:57:49,040 --> 00:57:52,600 Else, radiť ľavú polovicu, a potom radiť pravú polovicu, 1167 00:57:52,600 --> 00:57:54,140 a potom zlúčiť. 1168 00:57:54,140 --> 00:57:56,979 >> Takže zatiaľ čo to vyzerá veľmi jednoduché, v skutočnosti, premýšľal o tom to 1169 00:57:56,979 --> 00:58:00,270 trochu ťažké. Vzhľadom k tomu, že ste rád, No, to je trochu beh na seba. 1170 00:58:00,270 --> 00:58:00,769 Je to tak? 1171 00:58:00,769 --> 00:58:02,430 Je to beh na seba. 1172 00:58:02,430 --> 00:58:05,479 Takže v tomto zmysle, David dotkol pri rekurziu v triede. 1173 00:58:05,479 --> 00:58:07,270 A to je pojem budeme hovoriť o viac. 1174 00:58:07,270 --> 00:58:11,430 Je to, že toto, tieto dve linky Tu, v skutočnosti je len program 1175 00:58:11,430 --> 00:58:13,860 hovoriť, aby sa spúšťal sám s rôznym vstupom. 1176 00:58:13,860 --> 00:58:17,230 Takže skôr ako bežať seba s celistvosť n elementy, 1177 00:58:17,230 --> 00:58:20,530 môžete zlomiť to do ľavú polovicu a pravá polovica 1178 00:58:20,530 --> 00:58:22,680 a spustite ho znova. 1179 00:58:22,680 --> 00:58:26,050 >> A potom sa pozrieme na to vizuálne, preto, že som vizuálny žiak. 1180 00:58:26,050 --> 00:58:27,270 Funguje to pre mňa lepšie. 1181 00:58:27,270 --> 00:58:29,890 Takže sa pozrieme na vizuálne príklad tu. 1182 00:58:29,890 --> 00:58:36,237 >> Povedzme, že máme celý rad, šesť prvky, 3, 5, 2, 6, 4, 1, sa netriedia. 1183 00:58:36,237 --> 00:58:37,820 Dobre, je tu veľa na tejto stránke. 1184 00:58:37,820 --> 00:58:43,179 Takže ak vy môžete pozrieť na Prvý krok sa tu, 3, 5, 2, 6, 4, 1, 1185 00:58:43,179 --> 00:58:44,220 môžete rozdeliť ho na polovicu. 1186 00:58:44,220 --> 00:58:45,976 Máte 3, 5, 2, 6, 4, 1. 1187 00:58:45,976 --> 00:58:48,850 Viete, že tieto aren't-- vás Neviem, či sú radené, alebo nie, 1188 00:58:48,850 --> 00:58:52,517 takže si udržať lámanie je dole, na polovicu, na polovicu, na polovicu, až nakoniec, 1189 00:58:52,517 --> 00:58:53,600 máte len jeden prvok. 1190 00:58:53,600 --> 00:58:56,790 A jeden prvok je vždy radené, že jo? 1191 00:58:56,790 --> 00:59:01,560 >> Takže vieme, že 3, 5, 2, 4, 6, 1 samy o sebe, sú zoradené. 1192 00:59:01,560 --> 00:59:05,870 A teraz môžeme dať ich dohromady. 1193 00:59:05,870 --> 00:59:07,510 Takže vieme, na 3, 5. 1194 00:59:07,510 --> 00:59:08,510 Dali sme dohromady tie. 1195 00:59:08,510 --> 00:59:09,617 Vieme, že je to triediť. 1196 00:59:09,617 --> 00:59:10,450 Na 2 je tam stále. 1197 00:59:10,450 --> 00:59:11,830 Môžeme dať 4 a 6 dohromady. 1198 00:59:11,830 --> 00:59:13,996 Vieme, že to je zoradená, tak sme dali, že spoločne. 1199 00:59:13,996 --> 00:59:14,940 A 1 je tam. 1200 00:59:14,940 --> 00:59:18,720 >> A potom sa stačí pozrieť sa na tieto dve polovice tu. 1201 00:59:18,720 --> 00:59:21,300 Máte 3, 5, 2, 2, 3, 5. 1202 00:59:21,300 --> 00:59:23,465 Len si môžete porovnať začiatok všetkého. 1203 00:59:23,465 --> 00:59:26,340 Vzhľadom k tomu, viete, že to je radený a viete, že to je triediť. 1204 00:59:26,340 --> 00:59:29,360 Takže vy nemusíte ani na porovnať 5, stačí porovnať 3. 1205 00:59:29,360 --> 00:59:32,070 A 2 je menšia ako 3, takže Viete 2 musí ísť na konci. 1206 00:59:32,070 --> 00:59:33,120 >> To isté tam. 1207 00:59:33,120 --> 00:59:34,740 1 musí ísť sem. 1208 00:59:34,740 --> 00:59:37,330 A potom, keď idete dať tieto dve hodnoty dohromady, 1209 00:59:37,330 --> 00:59:39,950 viete, že to je zoradená a viete, že je triedený. 1210 00:59:39,950 --> 00:59:43,240 Takže potom 1 a 2 je 1 je menšia ako 2. 1211 00:59:43,240 --> 00:59:45,570 To vám povie, že 1 by mal ísť na konci tohto 1212 00:59:45,570 --> 00:59:47,480 bez pri pohľade na 3 alebo 5. 1213 00:59:47,480 --> 00:59:50,100 A potom na 4, môžete len skontrolujte, že ide priamo tu. 1214 00:59:50,100 --> 00:59:51,480 Nemusíte sa pozrieť na 5. 1215 00:59:51,480 --> 00:59:52,570 To isté sa 6. 1216 00:59:52,570 --> 00:59:55,860 Viete, že to jednoducho 6-- nemusí byť díval. 1217 00:59:55,860 --> 00:59:57,870 >> A tak sa týmto spôsobom, ste len ukladanie sami 1218 00:59:57,870 --> 00:59:59,526 veľa krokov, keď ste porovnávanie. 1219 00:59:59,526 --> 01:00:02,150 Nemusíte porovnať každý prvok s inými prvkami. 1220 01:00:02,150 --> 01:00:05,230 Práve ste porovnať proti tým, že musíte porovnať ju proti. 1221 01:00:05,230 --> 01:00:06,870 Tak to je trochu abstraktný pojem. 1222 01:00:06,870 --> 01:00:10,540 Žiadne starosti, ak to nie je docela ťa biť ešte v poriadku. 1223 01:00:10,540 --> 01:00:14,740 Ale všeobecne, to je ako zlúčenie triedenie funguje. 1224 01:00:14,740 --> 01:00:17,750 Otázky, rýchlych otázok, Než som sa presunúť na? 1225 01:00:17,750 --> 01:00:18,550 Jo. 1226 01:00:18,550 --> 01:00:22,230 >> Divákov: Takže ste povedal, že ste užili polohách 1, a potom 4 a 6 1227 01:00:22,230 --> 01:00:23,860 a dať ich do. 1228 01:00:23,860 --> 01:00:26,800 Takže nie sú those-- nie sú Pozeráte sa na ne 1229 01:00:26,800 --> 01:00:28,544 ako samostatné prvky, nie ako celku? 1230 01:00:28,544 --> 01:00:29,210 ANDI PENG: Jo. 1231 01:00:29,210 --> 01:00:32,020 Takže to, čo sa deje je to, že ste v podstate 1232 01:00:32,020 --> 01:00:33,650 vytvárajú úplne nové pole. 1233 01:00:33,650 --> 01:00:36,690 Takže viete, že tu, mám dve polia o veľkosti 3, nie? 1234 01:00:36,690 --> 01:00:39,600 Takže viete, že môj triedeného array musí mať šesť prvkov. 1235 01:00:39,600 --> 01:00:42,270 Takže si stačí vytvoriť nová množstvo pamäte. 1236 01:00:42,270 --> 01:00:44,270 Takže ste niečo ako že plytvanie pamäti, 1237 01:00:44,270 --> 01:00:46,186 ale to nevadí, pretože je to tak malý. 1238 01:00:46,186 --> 01:00:48,590 Takže sa pozrieť na 1 a sa pozriete na 2. 1239 01:00:48,590 --> 01:00:50,770 A viete, že 1 je menšia ako 2. 1240 01:00:50,770 --> 01:00:53,840 Takže viete, že 1 by mal ísť do počiatok všetkých z nich. 1241 01:00:53,840 --> 01:00:55,850 >> Nemusíte ani potreba pozrite sa na 3 a 5. 1242 01:00:55,850 --> 01:00:57,400 Takže viete 1 je tam. 1243 01:00:57,400 --> 01:00:59,300 Potom ste v podstate odseknú na 1. 1244 01:00:59,300 --> 01:01:00,370 Je to, ako, mŕtvy k nám. 1245 01:01:00,370 --> 01:01:03,690 Potom sme proste 2, 3, 5, a potom sa 4 a 6. 1246 01:01:03,690 --> 01:01:06,270 A potom viete, že, vás porovnať 4 a 2, 1247 01:01:06,270 --> 01:01:07,560 Ach, tá 2 by malo ísť tam. 1248 01:01:07,560 --> 01:01:09,685 Takže ste PLOP na 2 dole, si nakrájame ho. 1249 01:01:09,685 --> 01:01:12,060 Takže stačí mať 3 a 5 v 4 a 6. 1250 01:01:12,060 --> 01:01:14,650 A vy ste len držať sekanie ho kým sa dať je v poli. 1251 01:01:14,650 --> 01:01:17,110 >> Divákov: Takže ste len vždy nákupný [nepočuteľných]? 1252 01:01:17,110 --> 01:01:17,710 >> ANDI PENG: Presne tak. 1253 01:01:17,710 --> 01:01:19,590 Takže v tomto zmysle, že ste len porovnanie, v podstate, 1254 01:01:19,590 --> 01:01:21,240 jedno číslo proti iné číslo. 1255 01:01:21,240 --> 01:01:22,990 A pretože viete, že to radené, vás 1256 01:01:22,990 --> 01:01:24,350 Nemusíte sa pozerať skrz všetky čísla. 1257 01:01:24,350 --> 01:01:25,870 Stačí sa len pozrieť na prvý z nich. 1258 01:01:25,870 --> 01:01:27,582 A potom sa môžete len PLOP je dole, pretože viete, 1259 01:01:27,582 --> 01:01:29,640 oni patrí tam, kam potrebujú patriť. 1260 01:01:29,640 --> 01:01:31,030 Jo. 1261 01:01:31,030 --> 01:01:32,920 Dobrá otázka. 1262 01:01:32,920 --> 01:01:35,290 >> A potom, ak niekto z vás sú trochu ambiciózny, 1263 01:01:35,290 --> 01:01:38,660 neváhajte sa pozrieť na tento kód. 1264 01:01:38,660 --> 01:01:40,680 To je vlastne fyzická realizácia 1265 01:01:40,680 --> 01:01:42,150 o tom, ako by sme napísať merge sort. 1266 01:01:42,150 --> 01:01:44,070 A môžete vidieť, že je to veľmi krátka. 1267 01:01:44,070 --> 01:01:46,310 Ale nápady za to sú celkom zložité. 1268 01:01:46,310 --> 01:01:50,865 Takže ak máte pocit, ako kreslenie na to vo svoje domáce úlohy dnes večer, neváhajte. 1269 01:01:50,865 --> 01:01:54,050 1270 01:01:54,050 --> 01:01:54,740 >> OK. 1271 01:01:54,740 --> 01:01:58,070 Tak aj Dávid prešiel toto v prednáške. 1272 01:01:58,070 --> 01:02:00,660 Aké sú najlepšie vec runtime, najhorší prípad runtimes, 1273 01:02:00,660 --> 01:02:05,680 a očakávané runtimes korešpondencia druhu? 1274 01:02:05,680 --> 01:02:07,260 Pár sekúnd premýšľať. 1275 01:02:07,260 --> 01:02:11,198 To je celkom ťažké, ale druh intuitívne, ak si myslíte o tom. 1276 01:02:11,198 --> 01:02:20,090 1277 01:02:20,090 --> 01:02:23,054 Dobre. 1278 01:02:23,054 --> 01:02:25,269 >> Divákov: Je najhorší prípad n log n? 1279 01:02:25,269 --> 01:02:26,060 ANDI PENG: Presne tak. 1280 01:02:26,060 --> 01:02:29,380 A prečo je to n log n. 1281 01:02:29,380 --> 01:02:32,230 >> Divákov: Nie je to preto, že sa stáva exponenciálne rýchlejší, 1282 01:02:32,230 --> 01:02:35,390 takže je to ako funkciu, ktorá nie len jednoducho byť n 1283 01:02:35,390 --> 01:02:37,529 na druhú, alebo tak niečo? 1284 01:02:37,529 --> 01:02:38,320 ANDI PENG: Presne tak. 1285 01:02:38,320 --> 01:02:40,750 Takže dôvod, prečo runtime v tejto oblasti je n log 1286 01:02:40,750 --> 01:02:44,310 n je protože-- to, čo ste robí vo všetkých týchto krokov? 1287 01:02:44,310 --> 01:02:46,190 Iba sekanie ho v polovici, že jo? 1288 01:02:46,190 --> 01:02:48,750 A tak, keď robíme log, všetko, čo to robí 1289 01:02:48,750 --> 01:02:53,150 rozdeľuje problém na polovicu, na polovicu, na polovicu, vo viacerých polovice. 1290 01:02:53,150 --> 01:02:56,430 A v tomto zmysle, môžete druh z eliminovať lineárny model 1291 01:02:56,430 --> 01:02:57,510 že sme používali. 1292 01:02:57,510 --> 01:03:00,254 Pretože keď si nakrájame veci v polovici, je to protokol. 1293 01:03:00,254 --> 01:03:02,420 To je len matematický spôsob, ako reprezentovať to. 1294 01:03:02,420 --> 01:03:06,310 >> A potom konečne, na konci, ste len aby jeden posledný priechod 1295 01:03:06,310 --> 01:03:07,930 dať všetky z nich v poriadku, nie? 1296 01:03:07,930 --> 01:03:10,330 A tak, keď stačí, aby skontrolovať jednu vec, to je n. 1297 01:03:10,330 --> 01:03:13,420 A tak ste trochu vynásobením dvaja spolu. 1298 01:03:13,420 --> 01:03:17,660 Takže je to ako, že máš, že konečné skontrolujte, či n tu s log n 1299 01:03:17,660 --> 01:03:18,390 tady. 1300 01:03:18,390 --> 01:03:21,060 A ak sa množiť je, že je n log n. 1301 01:03:21,060 --> 01:03:26,100 >> A tak to najlepšie a najhoršie prípad prípad, a očakáva, že sú všetci n log n. 1302 01:03:26,100 --> 01:03:27,943 Je to tiež ako iného druhu. 1303 01:03:27,943 --> 01:03:30,090 Je to ako výber druhu v tom zmysle, že 1304 01:03:30,090 --> 01:03:32,131 Nezáleží na tom, aké sú vaše Zoznam je, je to len bude 1305 01:03:32,131 --> 01:03:34,801 sa urobiť to isté zakaždým. 1306 01:03:34,801 --> 01:03:35,300 OK. 1307 01:03:35,300 --> 01:03:39,950 Tak ako vy môžete vidieť, aj keď že druhy, ktoré sme preč through-- n 1308 01:03:39,950 --> 01:03:41,660 štvorcový, to nie je moc efektívne. 1309 01:03:41,660 --> 01:03:47,060 A aj to n log n je nie je najúčinnejší. 1310 01:03:47,060 --> 01:03:49,720 Ak vy ste zvedaví, tam je radenie mechanizmy, 1311 01:03:49,720 --> 01:03:54,310 že sú tak účinné, že sú Takmer v podstate byt v behu. 1312 01:03:54,310 --> 01:03:55,420 >> Máte nejaký protokol n je. 1313 01:03:55,420 --> 01:03:58,190 Máte nejaké log log n je. 1314 01:03:58,190 --> 01:04:00,330 My nedotýkajte sa na ne v tejto triede práve teraz. 1315 01:04:00,330 --> 01:04:02,663 Ale ak vy ste zvedaví, neváhajte google, čo je 1316 01:04:02,663 --> 01:04:04,392 najvýkonnejšie triediace mechanizmy. 1317 01:04:04,392 --> 01:04:06,350 Ja neviem, existujú niektorí z nich naozaj na smiech, 1318 01:04:06,350 --> 01:04:09,860 jako-- tam je nejaké naozaj legrační tie, ktoré ľudia robia. 1319 01:04:09,860 --> 01:04:12,210 A vy ste vedel, ako by vôbec nenapadlo. 1320 01:04:12,210 --> 01:04:15,730 Takže google, ak máte trochu voľného čas, na to, čo sú niektoré vtipné spôsoby, 1321 01:04:15,730 --> 01:04:17,730 že people-- ako aj efektívna ways-- ľudia 1322 01:04:17,730 --> 01:04:20,371 boli schopní realizovať najrôznejšie. 1323 01:04:20,371 --> 01:04:20,870 OK. 1324 01:04:20,870 --> 01:04:22,880 A tu je len šikovný malý graf. 1325 01:04:22,880 --> 01:04:26,850 Viem, že vás všetkých, pred týmto kvízu 0, bude vo vašom izbe pravdepodobne snaží 1326 01:04:26,850 --> 01:04:27,960 zapamätať to. 1327 01:04:27,960 --> 01:04:30,940 Tak to je pekné tam pre vás. 1328 01:04:30,940 --> 01:04:37,120 Len nezabudnite na logiku, ktorá made-- prečo tieto čísla boli vyskytujúce. 1329 01:04:37,120 --> 01:04:39,870 Ak ste vždy prehral, ​​len aby istí, že viete, čo druhy sú. 1330 01:04:39,870 --> 01:04:40,820 A môžete prejsť je vo vašej mysli 1331 01:04:40,820 --> 01:04:42,903 prísť na to, prečo tí, Odpovede sú tieto odpovede. 1332 01:04:42,903 --> 01:04:46,250 1333 01:04:46,250 --> 01:04:47,600 >> Dobre. 1334 01:04:47,600 --> 01:04:49,680 Takže budeme pohybovať na, konečne, na vyhľadávanie. 1335 01:04:49,680 --> 01:04:51,638 Vzhľadom k tomu, ako tí z vás, ktorí po prečítaní pset, 1336 01:04:51,638 --> 01:04:55,175 Vyhľadávanie je tiež súčasťou tento týždeň problém sady. 1337 01:04:55,175 --> 01:04:57,300 Budete vyzvaní na implementáciu dva typy vyhľadávania. 1338 01:04:57,300 --> 01:05:00,070 Jedným z nich je lineárny vyhľadávanie a jeden je binárne vyhľadávanie. 1339 01:05:00,070 --> 01:05:01,760 >> Takže lineárne hľadanie je pomerne jednoduché. 1340 01:05:01,760 --> 01:05:04,070 Len chcete hľadať prvok zo zoznamu, či ste to. 1341 01:05:04,070 --> 01:05:05,444 Musíte len iterovat. 1342 01:05:05,444 --> 01:05:08,170 A keď sa rovná niečo, stačí vrátiť, nie? 1343 01:05:08,170 --> 01:05:10,890 Ale ten, ktorý sme najviac záujem hovoriť o 1344 01:05:10,890 --> 01:05:14,550 je binárne vyhľadávanie, vpravo, čo je rozdeľ a panuj mechanizmus, ktorý 1345 01:05:14,550 --> 01:05:18,190 David demonštroval v prednáške. 1346 01:05:18,190 --> 01:05:20,810 >> Spomeňte si na telefónny zoznam príklad že sa stále vychovávať, 1347 01:05:20,810 --> 01:05:23,960 ten, že sa druh snažil trochu na tento posledný rok, 1348 01:05:23,960 --> 01:05:27,530 kde rozdeliť problém na polovicu, na polovicu, na polovicu, znovu a znovu, 1349 01:05:27,530 --> 01:05:30,730 kým nenájdete to, čo hľadáte? 1350 01:05:30,730 --> 01:05:33,727 A vy ste dostal runtime of že rovnako. 1351 01:05:33,727 --> 01:05:35,810 A môžete vidieť, je to významne účinnejší 1352 01:05:35,810 --> 01:05:39,080 než akýkoľvek iný typ vyhľadávania. 1353 01:05:39,080 --> 01:05:41,880 >> Takže spôsob, akým by sme ísť o vykonávanie binárneho vyhľadávania 1354 01:05:41,880 --> 01:05:46,510 je, ak by sme mali poľa, index 0 až 6, sedem prvky, 1355 01:05:46,510 --> 01:05:49,790 sa môžeme pozrieť v stredu, right-- Ospravedlňujem sa, ak náš dotaz first-- 1356 01:05:49,790 --> 01:05:53,840 ak chceme položiť otázku, robí polia obsahujú prvok 7, 1357 01:05:53,840 --> 01:05:56,840 Je zrejmé, že sú ľudia, a majúci taká malá pole, je to pre nás ľahké 1358 01:05:56,840 --> 01:05:58,210 povedať áno. 1359 01:05:58,210 --> 01:06:05,750 Ale spôsob realizovať binárny Hľadanie by sa pozrieť do stredu. 1360 01:06:05,750 --> 01:06:08,020 >> Vieme, že index 3 prostredný, pretože my 1361 01:06:08,020 --> 01:06:09,270 viem, je ich tam sedem prvky. 1362 01:06:09,270 --> 01:06:10,670 Aké 7 deleno 2? 1363 01:06:10,670 --> 01:06:12,850 Môžete stopnúť, ktoré navyše 1. 1364 01:06:12,850 --> 01:06:14,850 Máte 3 v stredu. 1365 01:06:14,850 --> 01:06:17,590 Tak je pole 3 rovná 7? 1366 01:06:17,590 --> 01:06:18,900 To nie je, že jo? 1367 01:06:18,900 --> 01:06:21,050 Ale môžeme urobiť pár kontrol. 1368 01:06:21,050 --> 01:06:25,380 Je pole 3 menšie ako 7, alebo je pole 3 väčšie ako 7? 1369 01:06:25,380 --> 01:06:27,240 >> A my vieme, že je to menej ako 7. 1370 01:06:27,240 --> 01:06:30,259 Takže vieme, že, oh, to musí nemusí byť v ľavej polovici. 1371 01:06:30,259 --> 01:06:32,300 Vieme, že to musí byť v pravej polovici, že jo? 1372 01:06:32,300 --> 01:06:34,662 Takže môžeme len stopnúť polovicu poľa. 1373 01:06:34,662 --> 01:06:36,370 Nemáme dokonca ani pozri sa na to ešte. 1374 01:06:36,370 --> 01:06:38,711 Pretože vieme, že polovica našej problem-- 1375 01:06:38,711 --> 01:06:41,210 vieme, že odpoveď je v pravá polovica nášho problému. 1376 01:06:41,210 --> 01:06:42,580 Tak sme sa len pozrieť na to teraz. 1377 01:06:42,580 --> 01:06:44,860 >> Takže teraz sme sa pozrieť na Uprostred toho, čo zostalo. 1378 01:06:44,860 --> 01:06:46,880 To index 5. 1379 01:06:46,880 --> 01:06:50,200 Robíme rovnakú kontrolu znova a vidíme, že je to menšie. 1380 01:06:50,200 --> 01:06:52,050 Takže sa pozrieme na ľavej strane to. 1381 01:06:52,050 --> 01:06:53,430 A potom vidíme, ten šek. 1382 01:06:53,430 --> 01:06:57,600 Je hodnota poľa v index 4 rovná 7? 1383 01:06:57,600 --> 01:06:58,260 To je. 1384 01:06:58,260 --> 01:07:03,580 Takže sa môžeme vrátiť pravda, pretože sme zistili, že hodnotu v našom zozname. 1385 01:07:03,580 --> 01:07:06,738 Má tak, ako som išiel cez že zmysel pre všetkých? 1386 01:07:06,738 --> 01:07:08,760 OK. 1387 01:07:08,760 --> 01:07:11,670 Dám ti chlapci možno, rovnako ako, tri, štyri minúty prísť na to, 1388 01:07:11,670 --> 01:07:13,270 ako sa to v pseudokódu. 1389 01:07:13,270 --> 01:07:18,070 >> Tak si predstavte som vás požiadal, aby ste napísať Funkcia tzv search (), ktorý sa vrátil 1390 01:07:18,070 --> 01:07:20,640 hodnotu, logickú hodnotu, to bola pravda alebo false-- podobne, 1391 01:07:20,640 --> 01:07:22,970 true, ak ste našli hodnota, false, ak ste to neurobili. 1392 01:07:22,970 --> 01:07:25,230 A potom ste boli prešiel v hodnoty, ktorú 1393 01:07:25,230 --> 01:07:28,410 Hľadali do hodnôt, ktoré je array-- oh, rozhodne som dal 1394 01:07:28,410 --> 01:07:29,410 že na zlom mieste. 1395 01:07:29,410 --> 01:07:29,580 OK. 1396 01:07:29,580 --> 01:07:31,829 Tak ako tak, že by mal mať bolo na pravej strane hodnôt. 1397 01:07:31,829 --> 01:07:36,280 A potom int n je číslo prvkov v tomto poli. 1398 01:07:36,280 --> 01:07:39,430 Ako by ste ísť o snahe pseudokódu tento problém v? 1399 01:07:39,430 --> 01:07:41,630 Dám sa vám bude páčiť tri minúty na to. 1400 01:07:41,630 --> 01:08:00,137 1401 01:08:00,137 --> 01:08:02,595 Nie, myslím, že je only-- jo, je tu ešte jedna priamo tu. 1402 01:08:02,595 --> 01:08:03,261 Divákov: Môžem? 1403 01:08:03,261 --> 01:08:04,388 ANDI PENG: Jo, mám ťa. 1404 01:08:04,388 --> 01:08:09,410 1405 01:08:09,410 --> 01:08:11,050 Je to pracovné? 1406 01:08:11,050 --> 01:08:12,290 OK v pohode. 1407 01:08:12,290 --> 01:10:43,590 1408 01:10:43,590 --> 01:10:44,720 >> OK. 1409 01:10:44,720 --> 01:10:47,630 Tak jo chlapi, my sme bude udržať na uzde ho. 1410 01:10:47,630 --> 01:10:49,730 OK. 1411 01:10:49,730 --> 01:10:54,020 Takže predpokladáme, máme tento krásny malá polia s n hodnôt v ňom. 1412 01:10:54,020 --> 01:10:55,170 Nechcel som kresliť čiary. 1413 01:10:55,170 --> 01:10:58,649 Ale ako by sme ísť o snaží písať to? 1414 01:10:58,649 --> 01:11:00,440 Má niekto chcel daj mi prvý riadok? 1415 01:11:00,440 --> 01:11:02,814 Ak chcete mi dať Prvý riadok tohto pseudokódu. 1416 01:11:02,814 --> 01:11:06,563 1417 01:11:06,563 --> 01:11:08,430 >> Divákov: [Nepočuteľné] 1418 01:11:08,430 --> 01:11:10,138 Divákov: by ste chceli prechádzať through-- 1419 01:11:10,138 --> 01:11:11,094 Divákov: Len ďalší pre sláčiky? 1420 01:11:11,094 --> 01:11:11,760 Divákov: --for. 1421 01:11:11,760 --> 01:11:15,880 1422 01:11:15,880 --> 01:11:17,780 >> ANDI PENG: Tak toto je trochu zložitejšie. 1423 01:11:17,780 --> 01:11:23,130 Myslíš, že about-- chcete sa udržujú v prevádzke tejto slučky 1424 01:11:23,130 --> 01:11:27,950 znova a znova, do kedy? 1425 01:11:27,950 --> 01:11:30,819 >> Divákov: Do [nepočuteľných] hodnota sa rovná tejto hodnote. 1426 01:11:30,819 --> 01:11:31,610 ANDI PENG: Presne tak. 1427 01:11:31,610 --> 01:11:33,900 Takže môžete vlastne len write-- môžeme ešte zjednodušiť ju viac. 1428 01:11:33,900 --> 01:11:35,630 Môžeme len robiť while, že jo? 1429 01:11:35,630 --> 01:11:39,380 Takže môžete mať len loop-- vieme, že je to za to. 1430 01:11:39,380 --> 01:11:42,850 Ale práve teraz, idem hovoriť "slučka" - tým, čo? 1431 01:11:42,850 --> 01:11:46,640 Loop until-- čo je náš ukončenie stavu? 1432 01:11:46,640 --> 01:11:47,510 Myslím, že som to počula. 1433 01:11:47,510 --> 01:11:48,530 Počul som, niekto to povedať. 1434 01:11:48,530 --> 01:11:51,255 >> Divákov: Hodnoty sa rovná stred. 1435 01:11:51,255 --> 01:11:52,255 ANDI PENG: Povedz to znova. 1436 01:11:52,255 --> 01:11:54,470 Publikum: Alebo, kým sa Hodnota, ktorú hľadáte 1437 01:11:54,470 --> 01:11:58,470 k je rovná strednej hodnote. 1438 01:11:58,470 --> 01:12:00,280 >> ANDI PENG: Čo keď to nie je tam? 1439 01:12:00,280 --> 01:12:03,113 Čo ak je hodnota hľadáte pre nie je vlastne v tomto poli? 1440 01:12:03,113 --> 01:12:05,890 Divákov: Vrátite 1. 1441 01:12:05,890 --> 01:12:08,850 >> ANDI PENG: Ale to, čo chceme slučky, až keď máme stav? 1442 01:12:08,850 --> 01:12:09,350 Jo. 1443 01:12:09,350 --> 01:12:11,239 >> Divákov: Kým je tu len jedna hodnota? 1444 01:12:11,239 --> 01:12:13,530 ANDI PENG: Môžete slučka until-- takže viete, že ste 1445 01:12:13,530 --> 01:12:15,714 bude mať maximálnu hodnotu, je to tak? 1446 01:12:15,714 --> 01:12:18,130 A viete, že budete mať hodnotu min, že jo? 1447 01:12:18,130 --> 01:12:20,379 Vzhľadom k tomu tiež, to je niečo, Zabudol som povedať predtým, 1448 01:12:20,379 --> 01:12:22,640 že niečo, čo je kriticky binárne vyhľadávanie 1449 01:12:22,640 --> 01:12:24,182 je, že vaše pole už je zoradený. 1450 01:12:24,182 --> 01:12:26,973 Pretože neexistuje žiadny spôsob, ako robiť , Ak sú to len náhodné hodnoty. 1451 01:12:26,973 --> 01:12:29,190 Neviete, ak je to väčšie ako ostatné, nie? 1452 01:12:29,190 --> 01:12:32,720 >> Takže viete, že vaše maximálne a Vaše min tu, nie? 1453 01:12:32,720 --> 01:12:35,590 Pokiaľ bude nastavenie Váš max vo vašich minút a mid-- 1454 01:12:35,590 --> 01:12:38,470 nech to len predpokladať stredná hodnota je správne here-- 1455 01:12:38,470 --> 01:12:43,910 budete v podstate slučka kým je minimum 1456 01:12:43,910 --> 01:12:47,510 zhruba rovnaký ako max, vpravo, alebo ak vaše maximálna nie je rovnaký ako min. 1457 01:12:47,510 --> 01:12:48,040 Je to tak? 1458 01:12:48,040 --> 01:12:51,340 Vzhľadom k tomu, keď sa to stane, viete, že že ste nakoniec narazila na rovnakú hodnotu. 1459 01:12:51,340 --> 01:12:59,135 Takže chcete, aby slučke, kým vašej min je menší alebo rovný to-- oops, 1460 01:12:59,135 --> 01:13:01,510 nie menej ako alebo rovné, na druhú stranu around-- Max. 1461 01:13:01,510 --> 01:13:15,110 1462 01:13:15,110 --> 01:13:16,160 >> Vedeli, že zmysel? 1463 01:13:16,160 --> 01:13:18,810 Vzal som niekoľko pokusov dostať toto právo. 1464 01:13:18,810 --> 01:13:21,869 Ale slučka, kým vaše maximálne hodnoty je v podstate takmer nižšej 1465 01:13:21,869 --> 01:13:23,410 než alebo rovná vašej minimum, že jo? 1466 01:13:23,410 --> 01:13:25,201 To je, keď viete, že ste sa zblížil. 1467 01:13:25,201 --> 01:13:29,290 Divákov: Ak by vaše maximálne hodnota bola nižšia, než je minimum? 1468 01:13:29,290 --> 01:13:31,040 ANDI PENG: Ak sa budete držať prispôsobí, čo 1469 01:13:31,040 --> 01:13:32,380 je to, čo sa chystáme je potrebné robiť v tomto. 1470 01:13:32,380 --> 01:13:33,460 Dáva to zmysel? 1471 01:13:33,460 --> 01:13:35,750 Minimálna a max sú len celé čísla, že sme pravdepodobne 1472 01:13:35,750 --> 01:13:39,260 bude chcieť vytvoriť, aby trať, kde sa pozeráme. 1473 01:13:39,260 --> 01:13:41,790 Vzhľadom k tomu, pole existuje bez ohľadu na to, čo robíme. 1474 01:13:41,790 --> 01:13:45,030 Rovnako ako, nie sme v skutočnosti fyzicky sekanie mimo poľa, nie? 1475 01:13:45,030 --> 01:13:47,261 Sme len nastavenie kde sa pozeráme. 1476 01:13:47,261 --> 01:13:48,136 Dáva to zmysel? 1477 01:13:48,136 --> 01:13:48,472 >> Divákov: Jo. 1478 01:13:48,472 --> 01:13:49,110 >> ANDI PENG: OK. 1479 01:13:49,110 --> 01:13:57,090 Takže ak to je podmienka pre naše slučku, to, čo chceme v tejto slučky? 1480 01:13:57,090 --> 01:13:58,700 Čo budeme sa chcieť robiť? 1481 01:13:58,700 --> 01:14:02,390 Takže teraz, máme max a min, pravý, 1482 01:14:02,390 --> 01:14:04,962 pravdepodobne vytvoril tu niekde. 1483 01:14:04,962 --> 01:14:07,170 Budeme chcieť nájsť strednú, že jo? 1484 01:14:07,170 --> 01:14:08,450 Ako sme bude schopný nájsť uprostred? 1485 01:14:08,450 --> 01:14:09,491 Čo je mathematical-- 1486 01:14:09,491 --> 01:14:11,079 Divákov: Max a min deleným 2. 1487 01:14:11,079 --> 01:14:11,870 ANDI PENG: Presne tak. 1488 01:14:11,870 --> 01:14:20,300 1489 01:14:20,300 --> 01:14:21,620 Dáva to zmysel? 1490 01:14:21,620 --> 01:14:25,780 A to vy, prečo by sme nebol len use--, prečo sme to urobili 1491 01:14:25,780 --> 01:14:27,850 namiesto toho robí len n deleno 2? 1492 01:14:27,850 --> 01:14:30,310 Je to preto, že n je hodnota že to bude zostať rovnaké. 1493 01:14:30,310 --> 01:14:30,979 Je to tak? 1494 01:14:30,979 --> 01:14:34,020 Ale ako sme prispôsobiť našu minimum a maximálnej hodnoty, sa chystajú zmeniť. 1495 01:14:34,020 --> 01:14:36,040 A ako výsledok, naše middle bude príliš meniť. 1496 01:14:36,040 --> 01:14:37,873 Takže to je dôvod, prečo chceme, to urobiť tu. 1497 01:14:37,873 --> 01:14:38,510 OK. 1498 01:14:38,510 --> 01:14:41,600 >> A potom, že teraz sme našli our-- jo. 1499 01:14:41,600 --> 01:14:44,270 >> Divákov: Len rýchly question-- keď hovoríte, min a max, 1500 01:14:44,270 --> 01:14:46,410 sme za predpokladu, že to už je zoradený? 1501 01:14:46,410 --> 01:14:48,400 >> ANDI PENG: Jo, to je vlastne Predpokladom pre binárne vyhľadávanie, 1502 01:14:48,400 --> 01:14:49,816 že musíte vedieť, že to triediť. 1503 01:14:49,816 --> 01:14:53,660 Čo je dôvod, prečo triediť, píšete vo vašom problém nastaviť pred binárneho vyhľadávania. 1504 01:14:53,660 --> 01:14:55,910 OK. 1505 01:14:55,910 --> 01:14:58,876 Takže teraz, keď vieme, kde naša stred je, čo chceš robiť? 1506 01:14:58,876 --> 01:15:01,789 1507 01:15:01,789 --> 01:15:04,319 >> Divákov: Chceme porovnať že do druhej. 1508 01:15:04,319 --> 01:15:05,110 ANDI PENG: Presne tak. 1509 01:15:05,110 --> 01:15:12,280 Takže budete porovnávať strednej hodnote, že jo? 1510 01:15:12,280 --> 01:15:14,900 1511 01:15:14,900 --> 01:15:18,670 A čo to povedať nás, keď sme porovnať? 1512 01:15:18,670 --> 01:15:22,226 Čo chceme robiť potom? 1513 01:15:22,226 --> 01:15:25,389 >> Divákov: Ak je hodnota väčšia ako polovice, chceme znížiť ju. 1514 01:15:25,389 --> 01:15:26,180 ANDI PENG: Presne tak. 1515 01:15:26,180 --> 01:15:33,940 Takže ak je táto hodnota väčšia než polovici, my sme 1516 01:15:33,940 --> 01:15:36,550 bude chcieť zmeniť tieto minimálne a maxes, že jo? 1517 01:15:36,550 --> 01:15:38,980 Čo chceme zmeniť? 1518 01:15:38,980 --> 01:15:42,145 Takže ak vieme, že hodnota je niekde tu to, čo robiť, tí, zmeniť? 1519 01:15:42,145 --> 01:15:44,758 Chceme zmeniť naše Minimálna byť stredná, že jo? 1520 01:15:44,758 --> 01:15:49,420 1521 01:15:49,420 --> 01:15:54,292 A potom ešte, ak je to v tomto polovica, čo chceme zmeniť? 1522 01:15:54,292 --> 01:15:55,306 >> Divákov: Vaše maximálne. 1523 01:15:55,306 --> 01:15:55,972 ANDI PENG: Jo. 1524 01:15:55,972 --> 01:16:02,597 1525 01:16:02,597 --> 01:16:04,680 A potom ste len tak aby looping, že jo? 1526 01:16:04,680 --> 01:16:08,920 Pretože teraz, po jednom prechode vďaka, máte max sem. 1527 01:16:08,920 --> 01:16:10,760 A potom môžete prepočítať v polovici. 1528 01:16:10,760 --> 01:16:11,990 A potom si môžete porovnať. 1529 01:16:11,990 --> 01:16:14,766 A budete ďalej kým min a maxes 1530 01:16:14,766 --> 01:16:15,890 majú v podstate konvergovanej. 1531 01:16:15,890 --> 01:16:17,890 A to je, keď viete, že že ste narazila na koniec. 1532 01:16:17,890 --> 01:16:20,280 A to buď ste ho našli alebo nemáte v tomto bode. 1533 01:16:20,280 --> 01:16:23,170 >> Má to zmysel, aby všetky? 1534 01:16:23,170 --> 01:16:26,020 1535 01:16:26,020 --> 01:16:26,770 OK. 1536 01:16:26,770 --> 01:16:27,900 To je docela dôležité, pretože budete mať 1537 01:16:27,900 --> 01:16:29,760 písať to v kóde večer. 1538 01:16:29,760 --> 01:16:32,660 Ale vy máte celkom dobrý zmysel pre to, čo by ste mali robiť, 1539 01:16:32,660 --> 01:16:34,051 čo je dobré. 1540 01:16:34,051 --> 01:16:34,550 OK. 1541 01:16:34,550 --> 01:16:38,840 Takže máme asi sedem minút ľavej časti. 1542 01:16:38,840 --> 01:16:43,170 Takže budeme hovoriť o tento pset, že budeme robiť. 1543 01:16:43,170 --> 01:16:46,410 Takže pset je rozdelená na dve polovice. 1544 01:16:46,410 --> 01:16:50,230 Prvá polovica sa týka vykonávanie find 1545 01:16:50,230 --> 01:16:54,210 v ktorom píšete lineárny hľadania, je binárne vyhľadávanie a triedenie algoritmus. 1546 01:16:54,210 --> 01:16:56,690 >> Tak toto je prvý tentoraz v pset kde 1547 01:16:56,690 --> 01:17:00,050 budeme dávať vám chlapci, čo sa nazýva Distribúcia kód, čo je kód 1548 01:17:00,050 --> 01:17:02,740 že sme pre-písaný, ale práve opustil niekoľko kúskov off 1549 01:17:02,740 --> 01:17:04,635 pre vás až do konca písania. 1550 01:17:04,635 --> 01:17:07,510 Takže vás chlapci, keď sa pozriete na to kód, by ste mohli dostať naozaj strach. 1551 01:17:07,510 --> 01:17:08,630 Ak ste rovnako ako ja, ach, Neviem, čo to robí, 1552 01:17:08,630 --> 01:17:11,670 Ja neviem, rovnako ako, že sa zdá tak zložité, ehm, relaxovať. 1553 01:17:11,670 --> 01:17:12,170 Je to v poriadku. 1554 01:17:12,170 --> 01:17:12,930 Prečítajte si špec. 1555 01:17:12,930 --> 01:17:16,920 Spec vám vysvetlí presne Čo všetky tieto programy robia. 1556 01:17:16,920 --> 01:17:20,560 >> Napríklad, generate.c je program že príde s pset. 1557 01:17:20,560 --> 01:17:24,060 Nemusíte skutočne sa ho dotknúť, ale mali by ste pochopiť, čo to robí. 1558 01:17:24,060 --> 01:17:28,550 A generate.c, všetko, čo robí, je buď generovanie náhodných čísel 1559 01:17:28,550 --> 01:17:32,400 alebo si môžete dať semeno, ako keď vopred dohodnuté číslo, ktoré je potrebné, 1560 01:17:32,400 --> 01:17:34,140 a to generuje viac čísel. 1561 01:17:34,140 --> 01:17:37,170 Takže tam je špecifický spôsob, ako implementovať generate.c v ktorom 1562 01:17:37,170 --> 01:17:42,760 stačí urobiť veľa čísel pre vás otestovať svoje iné metódy na. 1563 01:17:42,760 --> 01:17:45,900 >> Takže ak by ste chceli, pre Príkladom, otestujte nález, 1564 01:17:45,900 --> 01:17:48,970 budete chcieť spustiť generate.c, generujú veľa čísel, 1565 01:17:48,970 --> 01:17:50,880 a potom spustiť funkciu pomocníkov. 1566 01:17:50,880 --> 01:17:53,930 Váš pomocníci funkcia je miesto, kde ste vlastne fyzicky písania kódu. 1567 01:17:53,930 --> 01:17:59,330 A myslieť pomocníkov ako súbor knižnice píšete, že nález volá. 1568 01:17:59,330 --> 01:18:02,950 A tak sa v rámci helpers.c, budete robiť vyhľadávanie a radenie. 1569 01:18:02,950 --> 01:18:06,500 >> A potom budete v podstate stačí dať ich všetky dohromady. 1570 01:18:06,500 --> 01:18:10,350 Spec vám poradí, ako sa dať, že na príkazovom riadku. 1571 01:18:10,350 --> 01:18:14,880 A budete môcť vyskúšať, či nie je váš triediť a hľadať pracujú. 1572 01:18:14,880 --> 01:18:15,870 Super. 1573 01:18:15,870 --> 01:18:18,720 Má už niekto začal a stretávalo s problémami alebo otázky 1574 01:18:18,720 --> 01:18:20,520 majú práve teraz s tým? 1575 01:18:20,520 --> 01:18:21,020 OK. 1576 01:18:21,020 --> 01:18:21,476 >> Divákov: Počkajte. 1577 01:18:21,476 --> 01:18:21,932 Mám otázku. 1578 01:18:21,932 --> 01:18:22,844 >> ANDI PENG: Jo. 1579 01:18:22,844 --> 01:18:28,390 >> Divákov: Tak som začal robiť lineárne hľadanie v helpers.c 1580 01:18:28,390 --> 01:18:29,670 a to nebolo naozaj funguje. 1581 01:18:29,670 --> 01:18:34,590 Ale neskôr som zistil, že sme práve musíš ju zmazať a urobiť binárne vyhľadávanie. 1582 01:18:34,590 --> 01:18:36,991 Takže to je jedno, či to nebude fungovať? 1583 01:18:36,991 --> 01:18:39,700 1584 01:18:39,700 --> 01:18:41,510 >> ANDI PENG: Krátka odpoveď znie nie. 1585 01:18:41,510 --> 01:18:42,642 Ale pretože sme ne-- 1586 01:18:42,642 --> 01:18:44,350 Divákov: Ale nikto v skutočnosti kontrola. 1587 01:18:44,350 --> 01:18:46,058 ANDI PENG: Sme Nikdy ide vidieť, že. 1588 01:18:46,058 --> 01:18:49,590 Ale pravdepodobne budete chcieť, aby sa istí, že vaše hľadanie funguje. 1589 01:18:49,590 --> 01:18:51,700 Pretože ak vaše lineárne Hľadanie nefunguje, 1590 01:18:51,700 --> 01:18:54,410 potom je šanca sú vaše binárne vyhľadávanie nebude fungovať rovnako. 1591 01:18:54,410 --> 01:18:56,646 Pretože máte podobnú Logika v oboch z nich. 1592 01:18:56,646 --> 01:18:58,020 A nie, to naozaj nezáleží. 1593 01:18:58,020 --> 01:19:01,300 Takže len tie, ktoré budete zase v sú triediť a binárne vyhľadávanie. 1594 01:19:01,300 --> 01:19:02,490 Jo. 1595 01:19:02,490 --> 01:19:06,610 >> A tiež, veľa detí bolo snaží sa zostaviť helpers.c. 1596 01:19:06,610 --> 01:19:09,550 Nie ste vlastne dovolené to urobiť, pretože helpers.c 1597 01:19:09,550 --> 01:19:11,200 nemá hlavnú funkciu. 1598 01:19:11,200 --> 01:19:13,550 A tak by ste mali iba byť v skutočnosti kompilácie 1599 01:19:13,550 --> 01:19:18,670 vytvorenie a nájsť, pretože nájsť hovory helpers.c a funkcie v nej. 1600 01:19:18,670 --> 01:19:20,790 Takže to robí ladenie ako osina v zadku. 1601 01:19:20,790 --> 01:19:22,422 Ale to je to, čo musíme urobiť. 1602 01:19:22,422 --> 01:19:23,880 Divákov: Len Urobíte všetko, že jo? 1603 01:19:23,880 --> 01:19:27,290 ANDI PENG: stačí robiť všetko rovnako, jo. 1604 01:19:27,290 --> 01:19:28,060 OK. 1605 01:19:28,060 --> 01:19:32,570 Tak to je, pokiaľ ide o to, čo pset žiada, aby ste všetci robiť. 1606 01:19:32,570 --> 01:19:35,160 Ak máte akékoľvek otázky, pocit zadarmo a opýtajte sa ma po bode. 1607 01:19:35,160 --> 01:19:37,580 Budem tu, rovnako ako, 20 minút. 1608 01:19:37,580 --> 01:19:40,500 >> A áno, je to pset naozaj nie je tak zlé. 1609 01:19:40,500 --> 01:19:41,680 Mali by ste byť v poriadku. 1610 01:19:41,680 --> 01:19:43,250 Tie, len riadiť sa pokynmi. 1611 01:19:43,250 --> 01:19:47,840 Druh majú pocit, logicky, čo Deje sa to, a budete v pohode. 1612 01:19:47,840 --> 01:19:48,690 Nebuďte príliš veľký strach. 1613 01:19:48,690 --> 01:19:50,220 Je tu veľa kódu už písali tu. 1614 01:19:50,220 --> 01:19:53,011 Nebuďte príliš veľký strach, ak nemáte pochopiť, čo to všetko znamená. 1615 01:19:53,011 --> 01:19:54,749 Ak je to veľa, je to úplne v poriadku. 1616 01:19:54,749 --> 01:19:55,790 A prišiel úradné hodiny. 1617 01:19:55,790 --> 01:19:57,520 Pomôžeme vám sa pozrieť. 1618 01:19:57,520 --> 01:20:00,810 >> Divákov: S extra funkcie, sa pozrieme na tie? 1619 01:20:00,810 --> 01:20:03,417 >> ANDI PENG: Jo, tie, ktoré sú v kóde. 1620 01:20:03,417 --> 01:20:05,750 V hre 15 polovica je to už napísal pre teba. 1621 01:20:05,750 --> 01:20:09,310 Takže tieto funkcie sú už v kóde. 1622 01:20:09,310 --> 01:20:12,020 Jo. 1623 01:20:12,020 --> 01:20:12,520 Dobre. 1624 01:20:12,520 --> 01:20:14,000 No, veľa šťastia. 1625 01:20:14,000 --> 01:20:15,180 Je to nechutné deň. 1626 01:20:15,180 --> 01:20:19,370 Takže dúfajme, že vy sa necíti príliš zlé na tom, zostať vnútri a kódovanie. 1627 01:20:19,370 --> 01:20:22,133