1 00:00:00,000 --> 00:00:11,100 2 00:00:11,100 --> 00:00:12,300 >> SPEAKER 1: Ahoj všetci! 3 00:00:12,300 --> 00:00:13,890 Vitajte späť na časti. 4 00:00:13,890 --> 00:00:17,480 Tak rád, že sa tak veľa z vás aj tu, a každý, kto sa pozerá online. 5 00:00:17,480 --> 00:00:18,760 6 00:00:18,760 --> 00:00:20,920 Takže ako obvykle vitajte späť. 7 00:00:20,920 --> 00:00:24,360 Dúfam, že ste všetci mali krásne víkend plný oddychu, relaxácie. 8 00:00:24,360 --> 00:00:26,026 To včera bola krásna von. 9 00:00:26,026 --> 00:00:27,525 Takže dúfam, že sa vám to páčilo vonku. 10 00:00:27,525 --> 00:00:28,840 11 00:00:28,840 --> 00:00:30,610 >> Takže najprv pár oznámenia. 12 00:00:30,610 --> 00:00:31,920 13 00:00:31,920 --> 00:00:32,700 Triedenie. 14 00:00:32,700 --> 00:00:37,350 Takže väčšina z vás by mal dostať napíšte mi o vašom Scratch pset, 15 00:00:37,350 --> 00:00:39,920 ako aj triedenie pre pset 1. 16 00:00:39,920 --> 00:00:41,000 17 00:00:41,000 --> 00:00:42,220 Takže, len pár vecí. 18 00:00:42,220 --> 00:00:45,150 Uistite sa, že používate check50 v style50. 19 00:00:45,150 --> 00:00:47,250 Tie majú byť prostriedky pre vás, 20 00:00:47,250 --> 00:00:50,660 aby sa ubezpečil, že ste stále čo najviac bodov, ako môžete 21 00:00:50,660 --> 00:00:52,390 bez toho, aby zbytočne ich straty. 22 00:00:52,390 --> 00:00:54,407 Takže veci, ako je štýl sú veľmi dôležité. 23 00:00:54,407 --> 00:00:55,740 Chystáme sa zložiť za to. 24 00:00:55,740 --> 00:00:58,115 Niektorí z vás možno už si všimol, že z vášho pset. 25 00:00:58,115 --> 00:00:58,920 26 00:00:58,920 --> 00:01:01,450 A check50 je len Naozaj jednoduchý spôsob, aby sa ubezpečil, 27 00:01:01,450 --> 00:01:05,050 že sme vlastne vracia to, čo musí byť sa vrátil k užívateľovi, 28 00:01:05,050 --> 00:01:06,690 a že všetko funguje správne. 29 00:01:06,690 --> 00:01:08,690 30 00:01:08,690 --> 00:01:12,040 >> Na druhú poznámku, uistite sa, že nahrať veci do správnej zložky. 31 00:01:12,040 --> 00:01:14,470 To je môj život len trochu zložitejšie 32 00:01:14,470 --> 00:01:18,836 ak nahráte pset 2 do pset 1 pretože keď som stiahnuť niečo, 33 00:01:18,836 --> 00:01:20,085 nemajú sťahovať správne. 34 00:01:20,085 --> 00:01:21,690 35 00:01:21,690 --> 00:01:24,560 A ja viem, že je to trochu blbo v systéme zvyknúť, 36 00:01:24,560 --> 00:01:26,950 ale len byť super pozor, aj keď len pre mňa, 37 00:01:26,950 --> 00:01:30,080 tak, že keď ste sa dostal e-maily v ako 2 A.M. a ja som triedenia. 38 00:01:30,080 --> 00:01:33,710 Ak nie, pretože som sa pozrieť všade okolo pre pset. 39 00:01:33,710 --> 00:01:34,440 V pohode. 40 00:01:34,440 --> 00:01:37,270 >> Ja viem, že je to skoro, ale ja úplne dostal vzlietlo stráž 41 00:01:37,270 --> 00:01:40,800 eseje, ktorá je v dôsledku tejto piatok, že moji profesori boli len radi, oh yeah. 42 00:01:40,800 --> 00:01:42,550 Pamätajte si, že máte esej kvôli v piatok. 43 00:01:42,550 --> 00:01:45,780 Takže viem, že nikto rád premýšľať o tom, midterms, 44 00:01:45,780 --> 00:01:50,620 ale váš prvý kvíz je 15. októbra, ktorý októbra sa začína tento týždeň. 45 00:01:50,620 --> 00:01:53,290 Tak, to by mohlo byť skôr ako ste očakávali, je všetko. 46 00:01:53,290 --> 00:01:57,510 Tak, že nie ste hádzať nepripraveného keď Zmieňujem sa o časť budúci týždeň, že oh, 47 00:01:57,510 --> 00:02:00,560 Váš test budúci týždeň, myslel som, Ja by som vám trochu viac 48 00:02:00,560 --> 00:02:01,500 z hláv sa teraz. 49 00:02:01,500 --> 00:02:02,970 50 00:02:02,970 --> 00:02:04,660 >> Takže nastaviť váš problém, číslo tri. 51 00:02:04,660 --> 00:02:07,070 Ako ľudia čítať spec zo zvedavosti? 52 00:02:07,070 --> 00:02:08,560 53 00:02:08,560 --> 00:02:09,199 OK. 54 00:02:09,199 --> 00:02:10,229 Máme pár. 55 00:02:10,229 --> 00:02:12,320 Druh dole z posledného týždenne, ale to je v poriadku. 56 00:02:12,320 --> 00:02:13,650 Viem, že to bolo krásne von. 57 00:02:13,650 --> 00:02:15,120 58 00:02:15,120 --> 00:02:16,660 Tak Break Out. 59 00:02:16,660 --> 00:02:21,010 Rozhodne po stihnúť dnes čítať spec aspoň 60 00:02:21,010 --> 00:02:25,240 skúste ako stiahnutie Distribúcia kód a prevádzku 61 00:02:25,240 --> 00:02:27,430 ako prvý počiatočné vec, ktorá vás žiadajú, aby ste. 62 00:02:27,430 --> 00:02:28,681 63 00:02:28,681 --> 00:02:32,590 Pretože sme pomocou distribúcia kód a knižnice 64 00:02:32,590 --> 00:02:36,790 že sme ešte len using-- --It len Druhýkrát sme urobili túto pset, 65 00:02:36,790 --> 00:02:38,650 bláznivé veci sa môže stať s prístrojom, 66 00:02:38,650 --> 00:02:41,370 a chcete zistiť, že vonku proti neskôr. 67 00:02:41,370 --> 00:02:45,570 >> Vzhľadom k tomu, či je to vo štvrtok v noci, alebo je to V stredu v noci a z nejakého dôvodu 68 00:02:45,570 --> 00:02:48,912 Váš spotrebič jednoducho nie je chcete spustiť s knižnicou 69 00:02:48,912 --> 00:02:50,620 alebo distribúcie kód, to znamená 70 00:02:50,620 --> 00:02:52,309 nemôžete ani začať robiť kódovanie. 71 00:02:52,309 --> 00:02:54,100 Pretože nie je možné kontrolovať aby zistil, či to funguje. 72 00:02:54,100 --> 00:02:55,975 Váš nebudem môcť aby zistil, či to prekladá. 73 00:02:55,975 --> 00:03:00,500 Chcete sa postarať o tie, ktoré na začiatku roka týždeň, kedy môžete mi ešte e-mail 74 00:03:00,500 --> 00:03:03,100 alebo jeden z ďalších TFS a môžeme dostať tie, ktoré stanovuje. 75 00:03:03,100 --> 00:03:05,410 Vzhľadom k tomu, to sú otázky, ktoré ťa zastaviť 76 00:03:05,410 --> 00:03:07,120 v tom, aby žiadny skutočný pokrok. 77 00:03:07,120 --> 00:03:10,055 Nie je to ako jednu chybu, že môžete len tak preskočiť. 78 00:03:10,055 --> 00:03:10,712 79 00:03:10,712 --> 00:03:13,420 Ak máte problémy so svojím zariadenie alebo distribúcia kód, 80 00:03:13,420 --> 00:03:16,211 Naozaj chcete, aby si to vziať starostlivosť o skôr skôr ako neskôr. 81 00:03:16,211 --> 00:03:20,410 Takže aj keď ste nebudeš v skutočnosti začať písať kód, stiahnite si distribúciu 82 00:03:20,410 --> 00:03:24,040 kód, prečítajte si spec, uistite sa, všetko, čo sa tam pracuje. 83 00:03:24,040 --> 00:03:25,134 OK? 84 00:03:25,134 --> 00:03:27,675 Ak sa vám jednoducho to, že som Sľubujem svoj život bude jednoduchší. 85 00:03:27,675 --> 00:03:28,800 86 00:03:28,800 --> 00:03:31,410 A tak budete pravdepodobne to urobiť teraz hneď? 87 00:03:31,410 --> 00:03:32,100 OK. 88 00:03:32,100 --> 00:03:33,950 Takže tam nejaké otázky? 89 00:03:33,950 --> 00:03:35,850 Všetky logistické veci? 90 00:03:35,850 --> 00:03:36,910 Každý, kto je dobrý? 91 00:03:36,910 --> 00:03:38,270 OK. 92 00:03:38,270 --> 00:03:41,700 >> Disclaimer pre tých, Ste v miestnosti a on-line. 93 00:03:41,700 --> 00:03:45,437 Budem sa snažiť prepínať medzi PowerPoint v zariadení 94 00:03:45,437 --> 00:03:47,270 Pretože sa chystáme bude robiť nejaké kódovanie 95 00:03:47,270 --> 00:03:53,630 dnes populárnej dopytu anonymný návrh hlasovania som poslal minulý týždeň. 96 00:03:53,630 --> 00:03:55,480 Takže budeme robiť nejaké kódovanie. 97 00:03:55,480 --> 00:03:57,800 Takže ak vy tiež chcieť strieľať vaše zariadenie, 98 00:03:57,800 --> 00:04:02,910 a mali ste dostali e-mail odo mňa, s ukážkový súbor. 99 00:04:02,910 --> 00:04:04,310 Prosím, neváhajte to urobiť. 100 00:04:04,310 --> 00:04:07,340 >> Takže, budeme hovoriť o GDB, ktorý je debugger. 101 00:04:07,340 --> 00:04:09,970 Bude to, aby vám pomohol druh zistiť, kde 102 00:04:09,970 --> 00:04:11,860 veci idú zle v kóde. 103 00:04:11,860 --> 00:04:15,370 Je to naozaj len spôsob, ako krok prostredníctvom kódu, ako je to sa deje, 104 00:04:15,370 --> 00:04:19,100 a musí byť schopný vytlačiť premenné alebo zistiť, čo sa vlastne deje 105 00:04:19,100 --> 00:04:22,980 Pod kapotou verše program práve beží, je to ako chybující, 106 00:04:22,980 --> 00:04:25,030 a ty si ako, žiadny nápad čo sa tu práve stalo. 107 00:04:25,030 --> 00:04:26,730 Ja neviem, čo riadok to prepadlo na. 108 00:04:26,730 --> 00:04:29,040 Neviem, kde sa stala chyba. 109 00:04:29,040 --> 00:04:31,280 Takže, GDB bude, aby vám pomohol s tým. 110 00:04:31,280 --> 00:04:35,240 Tiež, ak sa rozhodnete pokračovať áno, a vziať 61, 111 00:04:35,240 --> 00:04:38,430 to bude naozaj, ale naozaj byť vaša najlepší priateľ, pretože som vám povedať, 112 00:04:38,430 --> 00:04:40,840 preto, že som prechádzal tejto triedy. 113 00:04:40,840 --> 00:04:43,620 >> Ideme sa pozrieť na binárne Hľadania, ktoré, ak vy pamätať 114 00:04:43,620 --> 00:04:47,540 veľký telefónny zoznam príkladov Podívaná z triedy. 115 00:04:47,540 --> 00:04:50,620 Budeme sa vykonáva to, a prechádzke, že trochu viac, 116 00:04:50,620 --> 00:04:54,650 a potom ideme cez štyri rôzne druhy, ktoré sú Bubble, 117 00:04:54,650 --> 00:04:56,285 Výber, vkladanie, a zlúčiť. 118 00:04:56,285 --> 00:04:57,830 119 00:04:57,830 --> 00:04:58,330 V pohode. 120 00:04:58,330 --> 00:05:00,390 Takže, GDB, ako som už spomenul, je debugger. 121 00:05:00,390 --> 00:05:01,400 122 00:05:01,400 --> 00:05:09,370 A tie sú trochu veľký veci, veľké funkcie alebo príkazy 123 00:05:09,370 --> 00:05:13,240 ktoré používate v GDB, a ja budem chodiť si cez demo sa prevedie do druhej. 124 00:05:13,240 --> 00:05:15,360 >> Takže, to nie je len Zostaneš abstraktné. 125 00:05:15,360 --> 00:05:18,000 Pokúsim sa, aby to ako betón ako je to možné pre vás. 126 00:05:18,000 --> 00:05:19,870 Takže, zlomiť. 127 00:05:19,870 --> 00:05:22,200 To bude prestávka buď ako, nejaké číslo, ktoré 128 00:05:22,200 --> 00:05:26,900 predstavuje riadok v programe, alebo môžete pomenovať funkciu. 129 00:05:26,900 --> 00:05:30,150 Takže, ak povieš rozbiť hlavné, sa zastaví na hlavné, 130 00:05:30,150 --> 00:05:32,400 a umožní vám prejsť túto funkciu. 131 00:05:32,400 --> 00:05:36,350 >> Rovnako tak, ak máte nejaké externé fungujú ako Swap alebo kocka, 132 00:05:36,350 --> 00:05:38,450 že sme sa pozreli na minulý týždeň. 133 00:05:38,450 --> 00:05:41,780 Ak poviete rozbiť jeden z tých, keď váš program zasiahne to, 134 00:05:41,780 --> 00:05:44,290 to na teba čakať na hovorí, čo má robiť. 135 00:05:44,290 --> 00:05:47,860 Než to bude len spustiť, takže vám by sa skutočne krok vnútri funkcie 136 00:05:47,860 --> 00:05:49,020 a uvidíte, čo sa deje. 137 00:05:49,020 --> 00:05:50,370 138 00:05:50,370 --> 00:05:53,515 Takže ďalší, jednoducho preskočí ďalší riadok, prejde funkcie. 139 00:05:53,515 --> 00:05:54,730 140 00:05:54,730 --> 00:05:55,560 Krok. 141 00:05:55,560 --> 00:05:56,810 To všetko sú trochu abstraktné. 142 00:05:56,810 --> 00:06:00,530 Tak som len tak bežať cez ne, ale vy ich uvidíte v použitie v druhej. 143 00:06:00,530 --> 00:06:01,810 >> Vstúpte do funkcie. 144 00:06:01,810 --> 00:06:04,170 Takže ako som hovoril, ako u Swap, by to 145 00:06:04,170 --> 00:06:07,110 umožňujú skutočne, ako keby ste ako fyzicky krokovanie vnútri, 146 00:06:07,110 --> 00:06:10,990 môžete si s týmito premennými, tlač to, čo oni sú, čo sa deje. 147 00:06:10,990 --> 00:06:12,140 148 00:06:12,140 --> 00:06:14,830 Zoznam bude doslova len vytlačiť z okolitého kódu. 149 00:06:14,830 --> 00:06:17,570 Takže, ak ste trochu zabudnúť kde ste vo vašom programe, 150 00:06:17,570 --> 00:06:19,880 alebo ste zvedaví, čo sa deje okolo neho, 151 00:06:19,880 --> 00:06:23,790 to bude len vytlačiť segmente podobných päť alebo šesť riadkov okolo neho. 152 00:06:23,790 --> 00:06:26,080 Takže môžete lepšie zorientovať o tom, kde sa práve nachádzate. 153 00:06:26,080 --> 00:06:27,230 154 00:06:27,230 --> 00:06:28,650 >> Vytlačiť nejaké premenné. 155 00:06:28,650 --> 00:06:34,590 Takže, ak máte kľúč ako v Caesar, že sa pozrieme na. 156 00:06:34,590 --> 00:06:36,220 Môžete povedať, že PRINT na každom mieste. 157 00:06:36,220 --> 00:06:40,070 To vám poviem, čo je hodnota, takže že možno niekde na ceste, 158 00:06:40,070 --> 00:06:42,070 k prepisu kľúč. 159 00:06:42,070 --> 00:06:45,495 Môžete si skutočne povedať, že preto, že môžete skutočne sledovať túto hodnotu. 160 00:06:45,495 --> 00:06:46,500 161 00:06:46,500 --> 00:06:48,780 >> V miestnych obyvateľov, len výtlačky z vašich lokálnych premenných. 162 00:06:48,780 --> 00:06:53,120 Takže, kedykoľvek ste v slučke, a vy jednoducho chcete vidieť podobné, oh. 163 00:06:53,120 --> 00:06:54,270 Aká je moja ja? 164 00:06:54,270 --> 00:06:57,020 Aká je táto hodnota kľúča že som inicializovať tu? 165 00:06:57,020 --> 00:06:58,537 Čo je správa v tomto bode? 166 00:06:58,537 --> 00:07:00,370 To bude len vytlačiť všetko z tých, takže vás 167 00:07:00,370 --> 00:07:04,330 Nemusíte sa jednotlivo povedať, tlač I. Print Message. 168 00:07:04,330 --> 00:07:04,970 Print Key. 169 00:07:04,970 --> 00:07:06,190 170 00:07:06,190 --> 00:07:07,700 A potom displej. 171 00:07:07,700 --> 00:07:10,370 Čo to robí, je ako vy krok v rámci programu, 172 00:07:10,370 --> 00:07:13,980 to bude len uistiť, že je to zobrazovať len niektoré premenné 173 00:07:13,980 --> 00:07:14,780 v každom bode. 174 00:07:14,780 --> 00:07:17,160 Aby ste also-- --it to druh zástupca kde 175 00:07:17,160 --> 00:07:19,530 nemusíte ísť ďalej, ako, oh. 176 00:07:19,530 --> 00:07:23,150 Print Key alebo Tlač I. Proste automaticky to pre vás. 177 00:07:23,150 --> 00:07:25,959 >> Takže, s tým, že budeme vidieť, ako to ide. 178 00:07:25,959 --> 00:07:28,000 Budem sa snažiť a spínače k môjmu prístroju. 179 00:07:28,000 --> 00:07:30,200 180 00:07:30,200 --> 00:07:31,271 Uvidíme, či to zvládnem. 181 00:07:31,271 --> 00:07:31,770 All. 182 00:07:31,770 --> 00:07:40,970 183 00:07:40,970 --> 00:07:42,370 Sme len bude zrkadliť. 184 00:07:42,370 --> 00:07:44,530 Nie je nič, čo blázon na mojom notebooku kdekoľvek. 185 00:07:44,530 --> 00:07:49,600 186 00:07:49,600 --> 00:07:50,100 OK. 187 00:07:50,100 --> 00:07:57,030 188 00:07:57,030 --> 00:08:01,054 To musí byť táto. 189 00:08:01,054 --> 00:08:01,795 Je to tak malé. 190 00:08:01,795 --> 00:08:03,730 191 00:08:03,730 --> 00:08:05,120 Uvidíme, či to môžeme urobiť. 192 00:08:05,120 --> 00:08:09,970 193 00:08:09,970 --> 00:08:10,940 >> OK. 194 00:08:10,940 --> 00:08:15,305 Alice sa samozrejme snaží tu len trochu, 195 00:08:15,305 --> 00:08:17,995 ale my si to v Momento. 196 00:08:17,995 --> 00:08:20,810 197 00:08:20,810 --> 00:08:22,020 OK. 198 00:08:22,020 --> 00:08:25,900 Sme len porastie to. 199 00:08:25,900 --> 00:08:28,770 200 00:08:28,770 --> 00:08:29,380 OK. 201 00:08:29,380 --> 00:08:31,679 Môže každý druh vidieť, že? 202 00:08:31,679 --> 00:08:32,470 Možno trochu? 203 00:08:32,470 --> 00:08:33,594 Ja viem, je to trochu malý. 204 00:08:33,594 --> 00:08:34,570 205 00:08:34,570 --> 00:08:37,530 Nemôžete celkom prísť na to, ako sa robí to väčšia. 206 00:08:37,530 --> 00:08:38,350 Ak niekto pozná. 207 00:08:38,350 --> 00:08:40,309 Vie niekto, ako na to väčšie? 208 00:08:40,309 --> 00:08:40,932 OK. 209 00:08:40,932 --> 00:08:42,140 Chystáme sa vrátiť s ním. 210 00:08:42,140 --> 00:08:45,801 Nezáleží na tom tak ako tak, pretože je to len To je kód, ktorý vy by 211 00:08:45,801 --> 00:08:46,300 majú. 212 00:08:46,300 --> 00:08:48,310 >> Čo je dôležitejšie, je terminál tu. 213 00:08:48,310 --> 00:08:52,840 214 00:08:52,840 --> 00:08:58,690 A máme tu Prečo je to tak malý? 215 00:08:58,690 --> 00:09:02,325 216 00:09:02,325 --> 00:09:02,825 Nastavenie. 217 00:09:02,825 --> 00:09:07,920 218 00:09:07,920 --> 00:09:08,420 Oh. 219 00:09:08,420 --> 00:09:09,500 Pravda Ike. 220 00:09:09,500 --> 00:09:10,880 Ako je to? 221 00:09:10,880 --> 00:09:11,770 Odtiaľ. 222 00:09:11,770 --> 00:09:19,370 223 00:09:19,370 --> 00:09:21,810 Je to lepšie pre všetkých? 224 00:09:21,810 --> 00:09:22,525 OK,. 225 00:09:22,525 --> 00:09:23,025 V pohode. 226 00:09:23,025 --> 00:09:25,830 227 00:09:25,830 --> 00:09:28,220 >> Viete, kedy ste v SK triedy technické problémy 228 00:09:28,220 --> 00:09:32,971 sú trochu súčasťou the-- Takže, poďme vyčistiť to. 229 00:09:32,971 --> 00:09:33,470 OK. 230 00:09:33,470 --> 00:09:38,060 Takže, tu v sekcii ktoré sme tu mali. 231 00:09:38,060 --> 00:09:40,830 Caesar je spustiteľný súbor. 232 00:09:40,830 --> 00:09:41,800 Tak som urobil to. 233 00:09:41,800 --> 00:09:46,370 Takže jedna vec je si uvedomiť, s GDB je že to funguje len na spustiteľné súbory. 234 00:09:46,370 --> 00:09:48,040 Takže nemôžete spustiť na DOTS. 235 00:09:48,040 --> 00:09:50,532 Musíte vlastne robiť Uistite sa, že váš kód skompiluje, 236 00:09:50,532 --> 00:09:51,865 a že to môže byť v skutočnosti spustiť. 237 00:09:51,865 --> 00:09:52,970 238 00:09:52,970 --> 00:09:56,186 >> Takže, uistite sa, že ak sa tak nestane zostaviť si to skompilovať, 239 00:09:56,186 --> 00:09:57,810 takže môžete trochu prejsť. 240 00:09:57,810 --> 00:10:04,590 Tak pre začiatok GDB, všetko, čo urobiť, Typ Gloria GDB, a potom už len 241 00:10:04,590 --> 00:10:06,250 súbor, ktorý chcete. 242 00:10:06,250 --> 00:10:08,240 Vždy som chybne Caesara. 243 00:10:08,240 --> 00:10:11,730 Ale vy chcete byť istý, pretože je to spustiteľný, 244 00:10:11,730 --> 00:10:14,210 TI dot blesk tak, aby znamená, že ideš 245 00:10:14,210 --> 00:10:19,240 spustiť CSI budete vykonávať to súbory buď v debuggeri. 246 00:10:19,240 --> 00:10:19,910 OK. 247 00:10:19,910 --> 00:10:22,885 Takže, to, že sa dostanete tento druh blabol. 248 00:10:22,885 --> 00:10:24,250 249 00:10:24,250 --> 00:10:25,750 Je to len všetko o debuggera. 250 00:10:25,750 --> 00:10:28,200 Tie naozaj nemajú na starať o to práve teraz. 251 00:10:28,200 --> 00:10:31,460 A ako vidíte, máme to otvorené parens, HDP, v blízkosti parens, 252 00:10:31,460 --> 00:10:34,690 a len tak vyzerá naše príkazového riadku, je to tak? 253 00:10:34,690 --> 00:10:37,010 >> Takže, čo chceme do-- -SO, Prvá vec, 254 00:10:37,010 --> 00:10:39,570 ich chceme vybrať miesto, kde je zlomiť. 255 00:10:39,570 --> 00:10:42,332 Takže, tam je jedna chyba v tomto programe Caesar 256 00:10:42,332 --> 00:10:44,290 že som sa predstaviť, že ideme zistiť. 257 00:10:44,290 --> 00:10:45,330 258 00:10:45,330 --> 00:10:56,350 To, čo to je, že sa vstup Barfoo vo všetkých čiapky, a z nejakého dôvodu 259 00:10:56,350 --> 00:11:01,950 nemení A. Je to jednoducho odíde je sám, je všetko ostatné v poriadku, 260 00:11:01,950 --> 00:11:03,980 ale druhý list Zostáva bezo zmeny. 261 00:11:03,980 --> 00:11:07,120 Takže, budeme sa snažiť a prísť na to, prečo to tak je. 262 00:11:07,120 --> 00:11:10,440 Takže prvá vec, ktorú zvyčajne chcem robiť pri každom spustení na GDB 263 00:11:10,440 --> 00:11:12,010 je prísť na to, kde ju zlomiť. 264 00:11:12,010 --> 00:11:14,956 >> Takže Caesar je celkom krátky program. 265 00:11:14,956 --> 00:11:16,330 Máme len jednu funkciu, nie? 266 00:11:16,330 --> 00:11:18,520 Aké bolo naše funkcie v Caesar? 267 00:11:18,520 --> 00:11:19,590 268 00:11:19,590 --> 00:11:24,350 Je tu len jedna funkcia, hlavné je to tak? 269 00:11:24,350 --> 00:11:26,490 Hlavné je funkcia pre všetky programy. 270 00:11:26,490 --> 00:11:29,230 Ak ste nemali Main, mohol by som je hneď trochu strach teraz, 271 00:11:29,230 --> 00:11:31,000 ale dúfam, že ste všetci mali Main tam. 272 00:11:31,000 --> 00:11:34,150 Takže, čo môžeme urobiť, je, môžeme proste rozbiť Main, rovnako ako to. 273 00:11:34,150 --> 00:11:35,190 Tak, to hovorí, OK. 274 00:11:35,190 --> 00:11:37,430 Tam My sme nastavili zarážky jeden. 275 00:11:37,430 --> 00:11:42,870 >> Tak, teraz vec na zapamätanie je Caesar trvá jeden argument príkazového riadku právo 276 00:11:42,870 --> 00:11:45,150 a my sme to ešte neurobili kdekoľvek. 277 00:11:45,150 --> 00:11:47,560 Takže, čo robíte, ak je ste vlastne ísť spustiť 278 00:11:47,560 --> 00:11:51,540 program, program, ktorý ste beží v GDB, ktorý potrebuje príkazový riadok 279 00:11:51,540 --> 00:11:55,010 argumenty, budete na zadanie pri prvom spustení beží to. 280 00:11:55,010 --> 00:11:59,280 Takže v tomto prípade, my Beh s kľúčom tri. 281 00:11:59,280 --> 00:12:00,770 282 00:12:00,770 --> 00:12:02,040 A to sa skutočne začať. 283 00:12:02,040 --> 00:12:08,480 >> Takže, ak tu vidíte, máme Ak je RC sa nerovná 2. 284 00:12:08,480 --> 00:12:12,210 Takže ak vy všetci majú že súbor, ktorý som poslal hore 285 00:12:12,210 --> 00:12:15,100 uvidíte, že to je ako Prvý riadok naše hlavné funkcie, nie? 286 00:12:15,100 --> 00:12:17,890 Je to kontroluje, či je k dispozícii správny počet argumentov. 287 00:12:17,890 --> 00:12:20,620 Takže, ak ste premýšľal, RC ak je správne, 288 00:12:20,620 --> 00:12:23,250 môžete robiť niečo len ako Print RC. 289 00:12:23,250 --> 00:12:24,380 290 00:12:24,380 --> 00:12:28,640 RC je dve, čo je to, čo sme očakávali, že jo? 291 00:12:28,640 --> 00:12:32,010 >> Takže môžeme ísť ďalej, a pokračovať cez. 292 00:12:32,010 --> 00:12:33,200 Takže, máme tam nejaký kľúč. 293 00:12:33,200 --> 00:12:34,260 294 00:12:34,260 --> 00:12:37,090 A môžeme vytlačiť náš kľúč aby sa ubezpečil, že je to správne. 295 00:12:37,090 --> 00:12:38,380 296 00:12:38,380 --> 00:12:39,500 Zaujímavé. 297 00:12:39,500 --> 00:12:41,210 Nie tak celkom, čo sme očakávali. 298 00:12:41,210 --> 00:12:44,810 Takže jedna vec je si uvedomiť, s GDB tiež, je 299 00:12:44,810 --> 00:12:49,000 že to nie je, kým sa skutočne hit Ďalej, že riadok, ktorý ste práve videli 300 00:12:49,000 --> 00:12:50,720 je v skutočnosti vykonaný. 301 00:12:50,720 --> 00:12:53,870 Takže v tomto prípade kľúčom nebolo pridelené doteraz. 302 00:12:53,870 --> 00:12:57,050 Takže kľúč je nejaký odpad hodnota ktoré vidíte na tam dole. 303 00:12:57,050 --> 00:13:03,680 Negatívne --It je jeden miliárd dolárov 120-- a niečo divného veci do poriadku? 304 00:13:03,680 --> 00:13:05,340 Nie je to kľúč, ktorý sme očakávali. 305 00:13:05,340 --> 00:13:10,720 Ale keď sme narazili na Ďalšie a potom sme pokúsiť Print kľúč, je to tri. 306 00:13:10,720 --> 00:13:11,710 >> Všetci vidia, že? 307 00:13:11,710 --> 00:13:13,780 Takže, ak máte niečo že ste ako, počkajte. 308 00:13:13,780 --> 00:13:15,540 To je úplne zle, a ja neviem, 309 00:13:15,540 --> 00:13:20,150 ako by sa to stalo, pretože všetko, čo chcem urobiť, je priradiť číslo, premenná, 310 00:13:20,150 --> 00:13:22,900 skúste biť Ďalšie, skúste tlačiť znova, a uvidíme, či to funguje. 311 00:13:22,900 --> 00:13:27,830 Vzhľadom k tomu, že to len bude vykonávať a vlastne priradiť niečo po vás 312 00:13:27,830 --> 00:13:29,340 Ďalší hit. 313 00:13:29,340 --> 00:13:30,336 Zmysel pre každého? 314 00:13:30,336 --> 00:13:30,836 Hm? 315 00:13:30,836 --> 00:13:33,220 >> SPEAKER 2: Pri náhodnej čísla, čo to znamená? 316 00:13:33,220 --> 00:13:34,790 >> SPEAKER 1: Je to len náhodný. 317 00:13:34,790 --> 00:13:35,710 Je to len odpad. 318 00:13:35,710 --> 00:13:38,320 Je to proste niečo, že vaša Počítač bude náhodne priradí. 319 00:13:38,320 --> 00:13:39,721 320 00:13:39,721 --> 00:13:40,220 V pohode. 321 00:13:40,220 --> 00:13:45,760 Tak, teraz sa môžeme pohybovať, a tak teraz máme tento obyčajný text getString. 322 00:13:45,760 --> 00:13:48,600 Takže, dovoľte mi predstaviť, čo sa stane, keď sme narazili Ďalšie tu. 323 00:13:48,600 --> 00:13:51,320 Naše GDB druh zmizne, že jo? 324 00:13:51,320 --> 00:13:55,720 To preto, že getString Teraz je realizovať, nie? 325 00:13:55,720 --> 00:14:01,460 Takže, keď sme videli, obyčajný text rovná GetString, otvorené parens a parens, 326 00:14:01,460 --> 00:14:04,380 a my hit Ďalšia, ktorá má Teraz skutočne popravený. 327 00:14:04,380 --> 00:14:06,580 Takže, je to čakanie na nám vstup niečo. 328 00:14:06,580 --> 00:14:13,560 >> Takže ideme na vstup naše jedlo, ktoré je to, čo to nedarí, ako som vám povedal, 329 00:14:13,560 --> 00:14:18,020 a to len hovorí, že je to po spustení, že zatvorené 330 00:14:18,020 --> 00:14:19,980 držiak znamená, že je vystupujúce z tejto slučky. 331 00:14:19,980 --> 00:14:21,170 332 00:14:21,170 --> 00:14:25,420 Takže môžeme zasiahnuť Ďalšie a teraz, keď som istý, že ste všetci oboznámení od Caesara, 333 00:14:25,420 --> 00:14:27,260 je to, čo je táto linka bude robiť. 334 00:14:27,260 --> 00:14:32,030 Je to pre int i = 0, N sa rovná Strlen, obyčajný text, a potom 335 00:14:32,030 --> 00:14:33,960 Aj je menšie ako n, I, plus, plus. 336 00:14:33,960 --> 00:14:35,210 Čo je to slučka robiť? 337 00:14:35,210 --> 00:14:37,900 338 00:14:37,900 --> 00:14:39,160 Otvorte správu. 339 00:14:39,160 --> 00:14:39,770 V pohode. 340 00:14:39,770 --> 00:14:41,330 Takže, poďme začať robiť to. 341 00:14:41,330 --> 00:14:47,210 >> Takže, ak by táto podmienka zápas, pre naše prvé? 342 00:14:47,210 --> 00:14:52,250 Ak je to B, je to obyčajný text I. sme môžete získať informácie o našich miestnych obyvateľov. 343 00:14:52,250 --> 00:14:53,610 344 00:14:53,610 --> 00:14:57,970 Takže, je nula, a ak je šesť, ktoré očakávame, a naším hlavným je tri. 345 00:14:57,970 --> 00:14:59,227 Všetko, čo dáva zmysel, nie? 346 00:14:59,227 --> 00:15:01,310 Tieto čísla sú presne to, čo by malo byť. 347 00:15:01,310 --> 00:15:02,590 348 00:15:02,590 --> 00:15:03,870 Takže, hučanie? 349 00:15:03,870 --> 00:15:05,620 SPEAKER 3: Mám náhodné čísla pre môj. 350 00:15:05,620 --> 00:15:09,156 351 00:15:09,156 --> 00:15:12,030 SPEAKER 1: No, môžeme check-- --we môžete chatovať o tom v sekunde. 352 00:15:12,030 --> 00:15:14,110 353 00:15:14,110 --> 00:15:15,750 Ale mali by ste byť stále to. 354 00:15:15,750 --> 00:15:17,700 355 00:15:17,700 --> 00:15:20,130 Takže, ak máme kapitál B pre naše prvé, 356 00:15:20,130 --> 00:15:22,080 táto podmienka by ho chytiť, nie? 357 00:15:22,080 --> 00:15:27,120 Takže, keď sme narazili na Next, vidíme, že, ak skutočne vykonáva. 358 00:15:27,120 --> 00:15:29,220 Pretože ak ste po spolu v kóde, 359 00:15:29,220 --> 00:15:33,460 tento riadok tu, kde obyčajný text I sa nahrádza takto aritmetike, 360 00:15:33,460 --> 00:15:35,720 vykoná len v prípade if Podmienkou je správne v poriadku? 361 00:15:35,720 --> 00:15:36,905 362 00:15:36,905 --> 00:15:40,240 >> GDB bude len ukázať vám, veci, ktoré sú skutočne vykonávanie. 363 00:15:40,240 --> 00:15:45,140 Takže ak táto podmienka Pokiaľ nebola splnená, je to len tak preskočiť na ďalší riadok. 364 00:15:45,140 --> 00:15:46,540 OK? 365 00:15:46,540 --> 00:15:48,510 Takže, máme to. 366 00:15:48,510 --> 00:15:51,171 Tento držiak znamená, že je zatvorené z tejto slučky teraz. 367 00:15:51,171 --> 00:15:52,420 Takže, bude to začať znova. 368 00:15:52,420 --> 00:15:54,760 369 00:15:54,760 --> 00:15:56,280 Rovnako ako, že. 370 00:15:56,280 --> 00:15:59,120 Tak, že sa môžeme dostať informácie o našich miestnych obyvateľov tu, 371 00:15:59,120 --> 00:16:02,575 a vidíme, že naše prvé list zmenilo, že? 372 00:16:02,575 --> 00:16:05,150 Teraz je E, ako to má byť. 373 00:16:05,150 --> 00:16:07,360 Áno, môžeme pokračovať ďalej. 374 00:16:07,360 --> 00:16:08,500 >> A máme túto kontrolu. 375 00:16:08,500 --> 00:16:09,916 A ak táto kontrola by mala fungovať, nie? 376 00:16:09,916 --> 00:16:12,570 Je to A. Je treba zmeniť tri písmená vpred. 377 00:16:12,570 --> 00:16:14,320 378 00:16:14,320 --> 00:16:16,530 Ale ak si všimnete, my niečo iné. 379 00:16:16,530 --> 00:16:17,580 380 00:16:17,580 --> 00:16:22,860 Takže v tomto prípade tu, to chytil to, a tak táto linka vykonaný, 381 00:16:22,860 --> 00:16:28,620 ktoré upravovalo našu B. Ale v tomto prípade je tu, 382 00:16:28,620 --> 00:16:32,860 sme, že to jednoducho preskočí ju, a šiel na [? L Koná. ?] 383 00:16:32,860 --> 00:16:34,660 Takže niečo sa tam deje. 384 00:16:34,660 --> 00:16:37,780 Čo, že to hovorím, je to, vieme, že by mal zachytiť tú, 385 00:16:37,780 --> 00:16:39,200 ale nie je tomu tak. 386 00:16:39,200 --> 00:16:42,210 Môže niekto vidieť, čo naši Problém je v tomto riadku? 387 00:16:42,210 --> 00:16:45,380 388 00:16:45,380 --> 00:16:46,969 Je to veľmi minútu vec. 389 00:16:46,969 --> 00:16:48,510 A môžete sa tiež pozrieť na váš kód. 390 00:16:48,510 --> 00:16:49,980 391 00:16:49,980 --> 00:16:54,940 Je to tiež line-- zabudnúť na to, čo vedenie je v there-- ale je to v [nepočuteľné]. 392 00:16:54,940 --> 00:16:55,480 Áno? 393 00:16:55,480 --> 00:16:58,639 >> SPEAKER 4: Je to na viac ako strana, pokiaľ ju čítal v knihe. 394 00:16:58,639 --> 00:16:59,430 SPEAKER 1: Presne tak. 395 00:16:59,430 --> 00:17:02,620 Takže, debugger nemohol povedať si to, ale debugger 396 00:17:02,620 --> 00:17:05,880 Tie by mohli získať až na líniu že viete, nie je funkčná. 397 00:17:05,880 --> 00:17:09,319 A niekedy, keď najmä neskôr v semestri, kedy 398 00:17:09,319 --> 00:17:12,910 máte čo do činenia s sto, a sto pár riadkov kódu, a vy 399 00:17:12,910 --> 00:17:16,190 Neviem, kde sa to nedarí, je to skvelý spôsob, ako to urobiť. 400 00:17:16,190 --> 00:17:17,900 401 00:17:17,900 --> 00:17:18,989 Takže sme našli chybu. 402 00:17:18,989 --> 00:17:21,530 Môžete opraviť v súbore, a potom je možné ho znova spustiť, 403 00:17:21,530 --> 00:17:23,029 a všetko bude perfektne fungovať. 404 00:17:23,029 --> 00:17:24,970 405 00:17:24,970 --> 00:17:30,590 A najväčšia vec je to môže zdať, OK. 406 00:17:30,590 --> 00:17:31,090 Jo. 407 00:17:31,090 --> 00:17:31,370 V pohode. 408 00:17:31,370 --> 00:17:32,744 Vedeli ste, čo hľadáte. 409 00:17:32,744 --> 00:17:34,910 Takže ste vedel, čo má robiť. 410 00:17:34,910 --> 00:17:39,021 >> GDB môže byť super užitočné, pretože vám môžete vytlačiť všetky tieto veci, ktoré ste 411 00:17:39,021 --> 00:17:39,520 nie. 412 00:17:39,520 --> 00:17:41,160 Je to oveľa užitočnejšie než printf. 413 00:17:41,160 --> 00:17:43,440 Ako mnohí z vás používajú ako vyhlásenie printf 414 00:17:43,440 --> 00:17:46,200 zistiť, kde chyba bola, že jo? 415 00:17:46,200 --> 00:17:48,450 Takže, s tým, že nie musí neustále vracať, 416 00:17:48,450 --> 00:17:51,139 a ako komentovanie na Printf alebo okomentovaní, 417 00:17:51,139 --> 00:17:52,930 a zistiť, čo mali by ste byť tlač. 418 00:17:52,930 --> 00:17:55,670 To vlastne len vám umožní krokovať, vytlačte veci 419 00:17:55,670 --> 00:18:00,000 ako ste prechádza, takže môžete pozorovať, ako sa mení v reálnom čase, 420 00:18:00,000 --> 00:18:02,190 ako váš program beží. 421 00:18:02,190 --> 00:18:04,390 >> A to trvať trochu trochu zvykať. 422 00:18:04,390 --> 00:18:07,850 Ja by som Veľmi odporúčam len tak z toho trochu frustrovaný s ním 423 00:18:07,850 --> 00:18:08,930 práve teraz. 424 00:18:08,930 --> 00:18:13,450 Ak máte stráviť hodinu po Budúci týždeň ale naučiť sa používať GDB, 425 00:18:13,450 --> 00:18:16,140 ušetríte sami toľko času neskôr. 426 00:18:16,140 --> 00:18:18,750 A to doslova. povieme to ľudí každý rok, 427 00:18:18,750 --> 00:18:23,890 a spomínam si, keď som sa triedy, bol som rád, že budem v poriadku. 428 00:18:23,890 --> 00:18:24,700 Nie. 429 00:18:24,700 --> 00:18:27,030 Pset 6 prišla a ja som bol ako, ja som chcel učiť 430 00:18:27,030 --> 00:18:29,500 ako používať GDB, pretože sa mi nepáči vedieť, čo sa tu deje. 431 00:18:29,500 --> 00:18:32,940 >> Takže ak budete mať tak čas použiť na menšie programy 432 00:18:32,940 --> 00:18:35,697 že budete mať pracuje, rovnako ako pracovné 433 00:18:35,697 --> 00:18:37,530 cez niečo ako Visionary, ako je tento. 434 00:18:37,530 --> 00:18:38,800 435 00:18:38,800 --> 00:18:42,850 Alebo ak chcete ďalšie praxi, som si istý, Nemohol som prísť s buggy programy, 436 00:18:42,850 --> 00:18:45,300 pre vás ladiť, ak chcete. 437 00:18:45,300 --> 00:18:49,300 >> Ale ak si len vziať nejaký čas, aby si na to zvyknutí, len hrať sa s ním, 438 00:18:49,300 --> 00:18:50,550 to bude naozaj slúžiť dobre. 439 00:18:50,550 --> 00:18:52,591 A je to naozaj jedna z tie veci, ktoré ste práve 440 00:18:52,591 --> 00:18:57,340 musieť skúsiť a dostať svoje špinavé ruky sa predtým, než sa naozaj pochopiť. 441 00:18:57,340 --> 00:19:02,090 Naozaj len raz pochopil Musel som ladiť veci s ním, 442 00:19:02,090 --> 00:19:08,170 a je to oveľa príjemnejšie mať predstavu o tom, ladenie skôr skôr ako neskôr. 443 00:19:08,170 --> 00:19:08,850 OK. 444 00:19:08,850 --> 00:19:09,625 V pohode. 445 00:19:09,625 --> 00:19:12,960 Viem, že je to niečo ako rýchlokurz v GDB, 446 00:19:12,960 --> 00:19:16,400 a ja budem určite pracovať na získanie Tieto vyzerať väčšie nabudúce. 447 00:19:16,400 --> 00:19:17,590 448 00:19:17,590 --> 00:19:18,280 V pohode. 449 00:19:18,280 --> 00:19:20,390 >> Takže, ak sa vrátime k našej aplikácii PowerPoint. 450 00:19:20,390 --> 00:19:27,194 451 00:19:27,194 --> 00:19:28,110 Je to bude fungovať? 452 00:19:28,110 --> 00:19:29,711 453 00:19:29,711 --> 00:19:30,210 AWH. 454 00:19:30,210 --> 00:19:31,101 Áno. 455 00:19:31,101 --> 00:19:31,600 OK. 456 00:19:31,600 --> 00:19:35,480 Takže, ak ste niekedy potrebovať niektorý z ty zase, tam je zoznam. 457 00:19:35,480 --> 00:19:37,160 458 00:19:37,160 --> 00:19:40,830 Tak binárne vyhľadávanie, ktoré každý spomína na skvelú podívanou Davida 459 00:19:40,830 --> 00:19:42,259 kopírovanie telefónnych zoznamov na polovicu. 460 00:19:42,259 --> 00:19:44,050 Nemám naozaj dostať telefónne zoznamy už, 461 00:19:44,050 --> 00:19:46,530 pretože rovnako ako kde sa vám si telefónne zoznamy v týchto dňoch? 462 00:19:46,530 --> 00:19:48,220 Ja naozaj neviem. 463 00:19:48,220 --> 00:19:49,840 464 00:19:49,840 --> 00:19:50,590 Binárne vyhľadávanie. 465 00:19:50,590 --> 00:19:52,464 Pamätá si niekto, Ako Binárne hľadaní práce? 466 00:19:52,464 --> 00:19:54,380 467 00:19:54,380 --> 00:19:55,220 Vôbec niekto? 468 00:19:55,220 --> 00:19:56,325 Jo? 469 00:19:56,325 --> 00:19:58,283 SPEAKER 5: Viete, kedy sa pozriete na ktorých polovica 470 00:19:58,283 --> 00:20:01,146 to by bolo v, na tom základe, a zbaviť druhej polovice. 471 00:20:01,146 --> 00:20:01,896 >> SPEAKER 1 Presne tak. 472 00:20:01,896 --> 00:20:06,290 Takže, binárne vyhľadávanie, je to celkom je-- --we chcel volať to rozdeľ a panuj. 473 00:20:06,290 --> 00:20:09,170 Takže, čo budete robiť, je budete vyzerať v stredu, 474 00:20:09,170 --> 00:20:11,990 a uvidíte, či to zodpovedá to, čo hľadáte. 475 00:20:11,990 --> 00:20:15,420 A ak to tak nie je, skúste sa zistiť, je, že bude ponechaný 476 00:20:15,420 --> 00:20:16,450 polpenzia alebo pravú polovicu. 477 00:20:16,450 --> 00:20:19,325 Takže by to mohlo byť, ak hľadáte na niečo, čo je podľa abecedy, 478 00:20:19,325 --> 00:20:20,720 vidíš, oh. 479 00:20:20,720 --> 00:20:22,750 Má Allison prísť pred M? 480 00:20:22,750 --> 00:20:23,250 Áno. 481 00:20:23,250 --> 00:20:25,030 Takže ideme na pozrite sa na prvom polroku. 482 00:20:25,030 --> 00:20:26,450 >> Alebo by to mohlo byť ako s číslami. 483 00:20:26,450 --> 00:20:28,830 Čokoľvek, čo môžete nákupný, to môže byť triedené. 484 00:20:28,830 --> 00:20:29,920 485 00:20:29,920 --> 00:20:31,260 Môžete použiť binárne vyhľadávanie na. 486 00:20:31,260 --> 00:20:32,340 487 00:20:32,340 --> 00:20:37,455 Takže, niekto pamätať graf alebo čo to je? 488 00:20:37,455 --> 00:20:39,520 Je to asymptotickej zložitosť. 489 00:20:39,520 --> 00:20:42,830 Takže, tento graf len opisuje, ako dlho 490 00:20:42,830 --> 00:20:46,230 dostanete vyriešiť problém, ako zvýšite počet vecí 491 00:20:46,230 --> 00:20:47,090 ktorý používate. 492 00:20:47,090 --> 00:20:51,260 >> Takže máme N, čo je lineárny čas. 493 00:20:51,260 --> 00:20:54,560 Ak N viac ako dva, čo je o niečo lepšie, stále rastie super rýchly. 494 00:20:54,560 --> 00:20:58,360 A potom sme Prihlásenie, ktorý je to, čo považujeme za binárne vyhľadávanie. 495 00:20:58,360 --> 00:21:03,630 Ak si všimneme, ako váš problém dostane oveľa a oveľa väčší, 496 00:21:03,630 --> 00:21:06,600 Čas, ktorý zaberie vám to vyriešiť nie je naozaj zvyšuje, že veľa. 497 00:21:06,600 --> 00:21:09,010 Je to ako porovnateľné tu na začiatku. 498 00:21:09,010 --> 00:21:10,060 Si ako, OK. 499 00:21:10,060 --> 00:21:13,000 Niečo tu nie je naozaj ohľadu na to, ktorý z nich používame, 500 00:21:13,000 --> 00:21:16,220 ale dostanete sa k miliónu, miliarda. 501 00:21:16,220 --> 00:21:20,010 Snažíte sa nájsť some-- --you're sa snaží nájsť ihlu v kope sena. 502 00:21:20,010 --> 00:21:21,550 >> Myslím si, že chcete tento problém. 503 00:21:21,550 --> 00:21:25,850 Chcete túto zložitosť, nie lineárny, pretože za všetko, čo 504 00:21:25,850 --> 00:21:30,049 viete, že vaša bude sa prehľadávať každý jednotlivec ihla, čo sena, 505 00:21:30,049 --> 00:21:31,340 snaží hľadať ihlu. 506 00:21:31,340 --> 00:21:34,730 A to nie je podľa môjho názoru príliš zábavné. 507 00:21:34,730 --> 00:21:35,500 Rýchlo, že som rád. 508 00:21:35,500 --> 00:21:36,620 Mám rád efektívna. 509 00:21:36,620 --> 00:21:40,450 A ako pracovití študenti vám prináša chlapci, viete pracovať chytrejšie, 510 00:21:40,450 --> 00:21:43,010 nie ťažšie typ vec, ako sa vám môže tvoriť tieto algoritmy. 511 00:21:43,010 --> 00:21:45,110 512 00:21:45,110 --> 00:21:47,910 >> Takže, ideme na prechádzku cez len rýchly príklad. 513 00:21:47,910 --> 00:21:51,090 Myslím si, že chlapci by mali mať ruku na binárne vyhľadávanie, 514 00:21:51,090 --> 00:21:54,352 ale v prípade, že niekto je trochu rozmazaný, chcete ho posilniť, 515 00:21:54,352 --> 00:21:56,310 budeme jednoducho ísť cez príklad. 516 00:21:56,310 --> 00:21:59,490 Takže, hľadáme ak pole obsahuje sedem. 517 00:21:59,490 --> 00:22:00,540 518 00:22:00,540 --> 00:22:06,010 >> Takže prvá vec, ktorú robíme, je hľadať v stredu, nie? 519 00:22:06,010 --> 00:22:09,340 A tiež budete sa kódovanie Binary Search pár sekúnd. 520 00:22:09,340 --> 00:22:11,310 Takže, to bude sranda. 521 00:22:11,310 --> 00:22:13,710 Tak sme sa pozrieť do stredné malé pole 3. 522 00:22:13,710 --> 00:22:15,501 Má 3 sa rovná 7? 523 00:22:15,501 --> 00:22:16,000 Nie je. 524 00:22:16,000 --> 00:22:18,670 525 00:22:18,670 --> 00:22:19,550 Je to šesť. 526 00:22:19,550 --> 00:22:21,480 Takže, to je menej ako alebo väčší ako sedem? 527 00:22:21,480 --> 00:22:23,080 528 00:22:23,080 --> 00:22:23,960 Menej ako. 529 00:22:23,960 --> 00:22:24,570 Áno. 530 00:22:24,570 --> 00:22:25,170 Dobrá práca chlapci. 531 00:22:25,170 --> 00:22:25,569 532 00:22:25,569 --> 00:22:27,360 Mám pocit, že by som mal mať sladkosti, pretože som 533 00:22:27,360 --> 00:22:29,460 chcú vyhodiť do dvorov. 534 00:22:29,460 --> 00:22:30,270 To je to, čo budem robiť budúci týždeň. 535 00:22:30,270 --> 00:22:31,436 Bude vás chlapci ostré. 536 00:22:31,436 --> 00:22:32,560 537 00:22:32,560 --> 00:22:34,690 >> Takže, vyhodíme, že prvá polovica, je to tak? 538 00:22:34,690 --> 00:22:35,670 to bolo menej ako. 539 00:22:35,670 --> 00:22:39,325 vieme, že všetko, na tej ľavej strane 540 00:22:39,325 --> 00:22:41,700 bude menšia ako to, čo sú vlastne hľadáme. 541 00:22:41,700 --> 00:22:43,491 Takže, nie je potrebné, aby venovať pozornosť. 542 00:22:43,491 --> 00:22:45,120 Proste na to zabudni. 543 00:22:45,120 --> 00:22:48,720 Tak, teraz sa pozrieme na našu pravej strane, a my sa v stredu tam, 544 00:22:48,720 --> 00:22:50,510 a teraz je to deväť. 545 00:22:50,510 --> 00:22:55,510 Takže, 9 je-- --Everyone? 546 00:22:55,510 --> 00:22:57,470 Väčšie, než to, čo sme hľadať, že jo? 547 00:22:57,470 --> 00:22:59,860 Takže ideme hodiť preč všetko vpravo. 548 00:22:59,860 --> 00:23:00,970 549 00:23:00,970 --> 00:23:01,940 Takhle. 550 00:23:01,940 --> 00:23:03,700 Teraz všetko, čo ste odišiel s jedným. 551 00:23:03,700 --> 00:23:07,760 Tak sme sa zistiť, je to jedno, čo hľadáme? to je. 552 00:23:07,760 --> 00:23:08,970 Zistili sme, čo sme chceli. 553 00:23:08,970 --> 00:23:10,440 554 00:23:10,440 --> 00:23:11,690 Takže sme hotoví. 555 00:23:11,690 --> 00:23:12,550 Bilineárne Search. 556 00:23:12,550 --> 00:23:15,740 >> A ak si všimnete, my mal tam sedem vstupov. 557 00:23:15,740 --> 00:23:24,320 To nám trvalo len ako trikrát, ale ak robíte ako miliardy 558 00:23:24,320 --> 00:23:28,190 vy viete, koľko krokov to by trvať, ak sme mali štyri miliardy veci? 559 00:23:28,190 --> 00:23:29,940 560 00:23:29,940 --> 00:23:30,455 Akékoľvek odhady? 561 00:23:30,455 --> 00:23:32,286 562 00:23:32,286 --> 00:23:33,960 Je to 32. 563 00:23:33,960 --> 00:23:37,110 32 krokov, ako nájsť niečo, vo štyri miliardy 564 00:23:37,110 --> 00:23:39,650 prvok poľa, pretože sily dva. 565 00:23:39,650 --> 00:23:43,550 Takže dva je 32, je na štyri miliardy korún. 566 00:23:43,550 --> 00:23:50,430 >> Tak dosť šialené, ako ste stále v ako pomerne malom počte krokov 567 00:23:50,430 --> 00:23:52,650 nájsť niečo, čo v štyrmi miliardami prvky. 568 00:23:52,650 --> 00:23:55,730 Takže v takom prípade, že sme bude kód tejto 569 00:23:55,730 --> 00:23:58,950 tak vy môžete naozaj druh vidieť, ako to funguje. 570 00:23:58,950 --> 00:24:01,520 Dobre, takže vy môžete kódovať. 571 00:24:01,520 --> 00:24:04,100 Idem si chlapci nechať hovoriť trochu. 572 00:24:04,100 --> 00:24:07,970 Spoznajte ľudí okolo seba, čo je to, čo by niekto chcel z poslednej časti. 573 00:24:07,970 --> 00:24:10,280 >> Takže spoznať ľudí okolo seba. 574 00:24:10,280 --> 00:24:11,305 Hovoriť trochu. 575 00:24:11,305 --> 00:24:12,580 576 00:24:12,580 --> 00:24:15,730 A všetko, čo chcem od vás Chlapci práve teraz je len 577 00:24:15,730 --> 00:24:17,575 pokúsiť sa vytvoriť náčrt pseudokódu. 578 00:24:17,575 --> 00:24:18,075 OK? 579 00:24:18,075 --> 00:24:20,825 580 00:24:20,825 --> 00:24:21,325 Whoa. 581 00:24:21,325 --> 00:24:23,320 582 00:24:23,320 --> 00:24:29,520 Jediné, čo chcem od vás, je, že ste len tak pre vyplnenie tejto chvíli prípadu. 583 00:24:29,520 --> 00:24:32,170 Tak som si stanovili tieto vyššie a dolné medze, ktoré 584 00:24:32,170 --> 00:24:35,250 predstavujú začiatok a koniec nášho poľa. 585 00:24:35,250 --> 00:24:40,440 A budete skutočne prechádzať a prísť na to, 586 00:24:40,440 --> 00:24:42,470 to, čo robíme v rámci tohto cyklu while. 587 00:24:42,470 --> 00:24:45,810 >> Takže ak môžete prísť out-- mám nápoveda there-- aké sú prípady, 588 00:24:45,810 --> 00:24:46,640 že tu máme? 589 00:24:46,640 --> 00:24:48,100 590 00:24:48,100 --> 00:24:51,560 Takže ak chcete zistiť, prípady, budeme pseudokódu ty 591 00:24:51,560 --> 00:24:53,350 a potom budeme vlastne kód je. 592 00:24:53,350 --> 00:24:55,330 A to bude, som si, dúfajme, že to bude 593 00:24:55,330 --> 00:24:56,788 byť o niečo ľahšie, než ste očakávali. 594 00:24:56,788 --> 00:24:57,554 595 00:24:57,554 --> 00:25:00,220 Vzhľadom k tomu, že to nie je tak moc kód, v skutočnosti, čo je naozaj cool. 596 00:25:00,220 --> 00:25:34,110 597 00:25:34,110 --> 00:25:35,018 >> Mm-hm? 598 00:25:35,018 --> 00:25:35,893 >> STUDENT: [nepočuteľné]? 599 00:25:35,893 --> 00:25:36,984 600 00:25:36,984 --> 00:25:37,650 Inštruktor: Áno. 601 00:25:37,650 --> 00:25:38,595 Tam bolo niečo nájsť v stredu. 602 00:25:38,595 --> 00:25:39,552 >> Žiak: Takže môžeme použiť. 603 00:25:39,552 --> 00:25:39,770 OK. 604 00:25:39,770 --> 00:25:40,603 >> Inštruktor: Perfect. 605 00:25:40,603 --> 00:25:42,950 Tak to je prvá vec, ktorú musíme urobiť. 606 00:25:42,950 --> 00:25:44,330 Takže nájsť stred. 607 00:25:44,330 --> 00:25:45,415 608 00:25:45,415 --> 00:25:45,915 Skvelé. 609 00:25:45,915 --> 00:25:47,770 610 00:25:47,770 --> 00:25:55,010 Takže máte predstavu o tom, ako by sme mohli skutočne nájsť stred s kódom? 611 00:25:55,010 --> 00:25:55,980 >> STUDENT: Jo. 612 00:25:55,980 --> 00:25:57,000 n nad 2? 613 00:25:57,000 --> 00:25:58,500 614 00:25:58,500 --> 00:25:59,500 Inštruktor: Takže n nad 2. 615 00:25:59,500 --> 00:26:05,170 Takže jedna vec na zapamätanie je, že Vaša horná a dolná hranica meniť. 616 00:26:05,170 --> 00:26:08,110 Neustále škrtiť časť matice sa pozeráme na. 617 00:26:08,110 --> 00:26:11,970 Tak n nad 2 bude fungovať iba prvá vec, ktorú robíme. 618 00:26:11,970 --> 00:26:17,810 Tak pričom horné a dolné do úvahy, ako by sme mohli dostať, že prostredný prvok? 619 00:26:17,810 --> 00:26:20,640 Pretože chceme, aby stredná medzi hornou a dolnou, že jo? 620 00:26:20,640 --> 00:26:21,730 621 00:26:21,730 --> 00:26:22,494 Mm-hm? 622 00:26:22,494 --> 00:26:23,369 >> STUDENT: [nepočuteľné]. 623 00:26:23,369 --> 00:26:26,170 624 00:26:26,170 --> 00:26:28,080 >> Inštruktor: Takže máme nejaký stred. 625 00:26:28,080 --> 00:26:32,730 A to bude horná a dolná nad 2. 626 00:26:32,730 --> 00:26:34,740 627 00:26:34,740 --> 00:26:35,690 Úžasné. 628 00:26:35,690 --> 00:26:36,570 Tak ideme. 629 00:26:36,570 --> 00:26:37,280 Jeden riadok dole. 630 00:26:37,280 --> 00:26:38,560 Vy ste na vašej ceste. 631 00:26:38,560 --> 00:26:41,400 Takže teraz, že máme prostredný, čo chceme robiť? 632 00:26:41,400 --> 00:26:45,050 633 00:26:45,050 --> 00:26:45,900 Len všeobecne. 634 00:26:45,900 --> 00:26:47,734 Nemusíte to kód. 635 00:26:47,734 --> 00:26:48,335 Áno. 636 00:26:48,335 --> 00:26:49,210 STUDENT: [nepočuteľné]? 637 00:26:49,210 --> 00:27:00,310 638 00:27:00,310 --> 00:27:10,310 Inštruktor: Takže je to navyše preto, že ste nájdenie priemer medzi dvoma 639 00:27:10,310 --> 00:27:10,810 z nich. 640 00:27:10,810 --> 00:27:11,890 641 00:27:11,890 --> 00:27:17,370 Takže ak si myslíte, že z nich ako druh zvýšenie v zo strán, 642 00:27:17,370 --> 00:27:21,640 premýšľať o tom, ako sa budete blížiť stredná, chcete takto. 643 00:27:21,640 --> 00:27:27,150 Takže ak ste boli na oboch stranách strednej a máme ako 5 a 7. 644 00:27:27,150 --> 00:27:31,440 Keď je sčítame vám získať 12, rozdeliť o 2, 6. 645 00:27:31,440 --> 00:27:33,726 >> Niekedy je to ťažké vysvetliť, prečo to funguje, 646 00:27:33,726 --> 00:27:35,600 ale ak budete pracovať cez Príklad niekedy, 647 00:27:35,600 --> 00:27:37,962 to vám pomôže zistiť, či by malo byť plus alebo mínus. 648 00:27:37,962 --> 00:27:38,846 Áno. 649 00:27:38,846 --> 00:27:40,830 >> STUDENT: [nepočuteľné] presne v strede 650 00:27:40,830 --> 00:27:43,950 keby mali prípad, kedy je tu veľa menších čísel 651 00:27:43,950 --> 00:27:45,860 a ako jeden veľký počet? 652 00:27:45,860 --> 00:27:49,750 >> Inštruktor: Takže všetko, čo potrebujete je uprostred poľa. 653 00:27:49,750 --> 00:27:53,010 Takže ak ste mali veľa malých čísiel a potom jeden naozaj veľký počet 654 00:27:53,010 --> 00:27:54,799 Na konci, na tom nezáleží. 655 00:27:54,799 --> 00:27:56,840 Všetko, na čom záleží, je, že oni sú radené, ktoré ste práve 656 00:27:56,840 --> 00:27:59,339 Chcete sa pozrieť na stredu pole, pretože ste stále 657 00:27:59,339 --> 00:28:00,700 krájanie váš problém na polovicu. 658 00:28:00,700 --> 00:28:03,020 659 00:28:03,020 --> 00:28:03,680 V pohode. 660 00:28:03,680 --> 00:28:06,430 Takže teraz, že máme prostredný, čo budeme robiť ďalej? 661 00:28:06,430 --> 00:28:07,150 >> STUDENT: Porovnajte. 662 00:28:07,150 --> 00:28:08,150 Inštruktor: porovnať. 663 00:28:08,150 --> 00:28:11,670 Takže porovnávať stredné až value_wanted. 664 00:28:11,670 --> 00:28:14,300 665 00:28:14,300 --> 00:28:15,160 V pohode. 666 00:28:15,160 --> 00:28:17,950 Takže vidíte, tu máme táto hodnota chceme tu. 667 00:28:17,950 --> 00:28:22,012 668 00:28:22,012 --> 00:28:23,095 Pamätajte, je to pole. 669 00:28:23,095 --> 00:28:24,100 670 00:28:24,100 --> 00:28:26,970 Takže stredná odkazuje na indexe. 671 00:28:26,970 --> 00:28:29,785 Takže chceme robiť hodnôt uprostred. 672 00:28:29,785 --> 00:28:32,380 673 00:28:32,380 --> 00:28:35,650 Nezabudnite, ak chcete porovnať, dvojlôžkové rovná. 674 00:28:35,650 --> 00:28:38,250 Robíte single rovná ste len tak ju preradiť, 675 00:28:38,250 --> 00:28:41,090 a potom, samozrejme, je to Bude na hodnotu, ktorú chcete. 676 00:28:41,090 --> 00:28:42,300 Takže nerobte to. 677 00:28:42,300 --> 00:28:44,350 >> Takže ideme zistiť, či hodnoty na stred 678 00:28:44,350 --> 00:28:46,460 je rovná hodnote chceme. 679 00:28:46,460 --> 00:28:47,749 680 00:28:47,749 --> 00:28:48,790 Nezabudnite na svoje rovnátka. 681 00:28:48,790 --> 00:28:50,520 682 00:28:50,520 --> 00:28:52,235 Dropbox mal ísť preč. 683 00:28:52,235 --> 00:28:54,140 684 00:28:54,140 --> 00:28:56,200 Tak čo budeme robiť v tomto prípade? 685 00:28:56,200 --> 00:28:59,360 Ak je to, čo chceme vrátiť? 686 00:28:59,360 --> 00:29:01,510 687 00:29:01,510 --> 00:29:02,626 Snažíme sa povedať. 688 00:29:02,626 --> 00:29:03,440 >> STUDENT: Tlač off. 689 00:29:03,440 --> 00:29:05,314 >> Inštruktor: No, my sme nechcete vytlačiť. 690 00:29:05,314 --> 00:29:08,220 Tak to je bool tu, a tak sme chcete vrátiť hodnotu true alebo false. 691 00:29:08,220 --> 00:29:12,280 Hovoríme, je toto číslo [? RRA? ?] Takže ak je to, 692 00:29:12,280 --> 00:29:13,788 len sme sa vrátiť to pravda. 693 00:29:13,788 --> 00:29:16,780 694 00:29:16,780 --> 00:29:17,760 Keď sa mi podarí kúzlo pravda. 695 00:29:17,760 --> 00:29:18,830 696 00:29:18,830 --> 00:29:20,805 >> STUDENT: Prečo by sa teda vrátite nula? 697 00:29:20,805 --> 00:29:22,930 Inštruktor: Takže by ste mohli vráti nulu, ak ste chceli. 698 00:29:22,930 --> 00:29:26,780 Ale v tomto prípade použiteľné, pretože naša funkcia vracia hodnotu typu bool, 699 00:29:26,780 --> 00:29:28,962 Musíme sa vrátiť buď true alebo false. 700 00:29:28,962 --> 00:29:30,920 STUDENT: Keď ste riekol: boolean výrazu, 701 00:29:30,920 --> 00:29:33,450 Môžete je rovná false? 702 00:29:33,450 --> 00:29:39,860 Rovnako ako keď som chcel povedať, ak je táto podmienka nie je splnená, ako je horná rovná false. 703 00:29:39,860 --> 00:29:42,332 Bude to, ak ste práve pochopili dať falošný na strane druhej? 704 00:29:42,332 --> 00:29:43,040 Inštruktor: Jo. 705 00:29:43,040 --> 00:29:44,820 Takže v skutočnosti, ak ste niekedy niečo 706 00:29:44,820 --> 00:29:49,600 ako je horná alebo je nižšia, ktorá vracia true alebo false 707 00:29:49,600 --> 00:29:53,850 a je to vlastne zlé štýl povedzme rovná rovná pravda alebo rovné 708 00:29:53,850 --> 00:29:54,840 rovná false. 709 00:29:54,840 --> 00:30:00,210 Ak chcete použiť tento výsledok ako sám ako kontrola. 710 00:30:00,210 --> 00:30:04,720 711 00:30:04,720 --> 00:30:05,860 Nie to, čo som chcel. 712 00:30:05,860 --> 00:30:08,150 713 00:30:08,150 --> 00:30:09,240 To je to, čo som chcel. 714 00:30:09,240 --> 00:30:13,205 Takže v prípade, že sa pýtate o niečom, ako je uloženie tejto vc. 715 00:30:13,205 --> 00:30:16,320 716 00:30:16,320 --> 00:30:25,150 >> Takže ak máme int main (void) a niečo také. 717 00:30:25,150 --> 00:30:31,922 A ak máte je horná nejakého vstupu a ste 718 00:30:31,922 --> 00:30:33,630 s otázkou, či môžete robiť niečo také? 719 00:30:33,630 --> 00:30:35,010 720 00:30:35,010 --> 00:30:35,679 Je to tak? 721 00:30:35,679 --> 00:30:37,470 STUDENT: Snažil som sa ako to urobiť, [nepočuteľné]. 722 00:30:37,470 --> 00:30:38,450 Pretože ak it's-- 723 00:30:38,450 --> 00:30:39,200 Inštruktor: Správne. 724 00:30:39,200 --> 00:30:41,197 Takže vy chcete to, že je falošný, nie? 725 00:30:41,197 --> 00:30:41,780 STUDENT: Jo. 726 00:30:41,780 --> 00:30:45,960 Inštruktor: Takže v tomto prípade, Chcete to vykonať, ak to nie je pravda. 727 00:30:45,960 --> 00:30:50,510 Takže v pohode vec, ktorú urobiť, je to. 728 00:30:50,510 --> 00:30:52,900 729 00:30:52,900 --> 00:30:55,650 Takže pamätajte výkrik bod popiera veci? 730 00:30:55,650 --> 00:30:58,270 To hovorí, že [nepočuteľné] znamená nie. 731 00:30:58,270 --> 00:31:03,590 Takže ak sa pozrieme na práve táto časť tu, mali by ste 732 00:31:03,590 --> 00:31:05,740 hovoria, že je vyhodnotený false, ako chcete, aby. 733 00:31:05,740 --> 00:31:06,790 734 00:31:06,790 --> 00:31:09,880 Nie falošný je pravda, ktorá znamená, že tento by sa spustiť. 735 00:31:09,880 --> 00:31:11,037 Dáva to zmysel? 736 00:31:11,037 --> 00:31:11,620 STUDENT: Jo. 737 00:31:11,620 --> 00:31:12,453 Inštruktor: Úžasné. 738 00:31:12,453 --> 00:31:13,800 739 00:31:13,800 --> 00:31:14,300 OK. 740 00:31:14,300 --> 00:31:16,330 Takže sme mohli len vrátiť platí v tomto prípade. 741 00:31:16,330 --> 00:31:20,357 Takže teraz máme ďalšie dve prípady, v tomto prípade. 742 00:31:20,357 --> 00:31:21,565 Aké sú naše dva ďalšie prípady? 743 00:31:21,565 --> 00:31:31,610 744 00:31:31,610 --> 00:31:32,900 Povedzme to urobiť takto. 745 00:31:32,900 --> 00:31:40,660 Takže začnime s iný ak hodnoty na stred 746 00:31:40,660 --> 00:31:43,230 je menšia ako hodnota, ktorú chceme. 747 00:31:43,230 --> 00:31:47,200 748 00:31:47,200 --> 00:31:52,020 Takže naše hodnoty v strede, je menej ako hodnota, ktorú hľadáme pre. 749 00:31:52,020 --> 00:31:53,765 750 00:31:53,765 --> 00:31:56,720 >> Tak ktorý viazaný vás robiť , Že chceme aktualizovať? 751 00:31:56,720 --> 00:31:57,870 752 00:31:57,870 --> 00:31:58,780 Hornej alebo dolnej? 753 00:31:58,780 --> 00:32:01,440 754 00:32:01,440 --> 00:32:01,940 Horné? 755 00:32:01,940 --> 00:32:03,230 756 00:32:03,230 --> 00:32:06,470 Takže, na ktorej strane poľa sa budeme pozerať na? 757 00:32:06,470 --> 00:32:07,500 >> STUDENT: nižšia. 758 00:32:07,500 --> 00:32:09,750 >> Inštruktor: My ideme že sa pozerá na ľavej strane. 759 00:32:09,750 --> 00:32:11,120 Takže else if málo hodnota je menšia. 760 00:32:11,120 --> 00:32:14,730 Tak tu vašej strednou hodnotou je menej ako to, čo chceme. 761 00:32:14,730 --> 00:32:17,202 A tak chceme, aby sa Pravá strana našu ponuku. 762 00:32:17,202 --> 00:32:18,910 Takže ideme na aktualizovať naše dolná hranica. 763 00:32:18,910 --> 00:32:20,210 764 00:32:20,210 --> 00:32:23,020 Takže budeme priradiť naša nižšia. 765 00:32:23,020 --> 00:32:25,221 A čo si myslíte, že by mala byť nižšia? 766 00:32:25,221 --> 00:32:26,304 STUDENT: stredná hodnota? 767 00:32:26,304 --> 00:32:27,446 768 00:32:27,446 --> 00:32:28,820 Inštruktor: Takže stredná value-- 769 00:32:28,820 --> 00:32:30,136 STUDENT: Plus 1. 770 00:32:30,136 --> 00:32:31,010 Inštruktor: --plus 1. 771 00:32:31,010 --> 00:32:32,300 772 00:32:32,300 --> 00:32:34,380 Môže mi niekto povedať, prečo máme to plus 1? 773 00:32:34,380 --> 00:32:35,730 >> STUDENT: [? Žiadna hodnota?] je rovný neho. 774 00:32:35,730 --> 00:32:36,120 >> Inštruktor: Správne. 775 00:32:36,120 --> 00:32:38,661 Pretože už vieme, že Naša stredná hodnota nie je rovná 776 00:32:38,661 --> 00:32:42,750 to a chceme vylúčiť zo všetkých následných vyhľadávania. 777 00:32:42,750 --> 00:32:46,360 Ak zabudnete, že plus 1, táto bude páčiť slučky na dobu neurčitú. 778 00:32:46,360 --> 00:32:49,620 A budete len byť zachytené nekonečnej slučky, a potom budete segfault 779 00:32:49,620 --> 00:32:50,370 a veci idú zle. 780 00:32:50,370 --> 00:32:54,780 Takže vždy uistite, že nie ste vrátane hodnoty, ktoré ste práve 781 00:32:54,780 --> 00:32:55,380 Pozrel sa na. 782 00:32:55,380 --> 00:32:58,530 Tak sme sa o to postarať sa znamienkom plus 1. 783 00:32:58,530 --> 00:33:04,840 >> Takže teraz máme poslednú podmienku ktorý som vždy z bezpečnostných dôvodov 784 00:33:04,840 --> 00:33:12,664 si môžete pozrieť tu, else if hodnota na prostredný je väčšia ako hodnota 785 00:33:12,664 --> 00:33:13,163 chceme. 786 00:33:13,163 --> 00:33:16,260 787 00:33:16,260 --> 00:33:20,230 To znamená, že chceme ľavá polovica. 788 00:33:20,230 --> 00:33:21,350 789 00:33:21,350 --> 00:33:23,260 Takže, ktorý z nich sa budeme aktualizovať? 790 00:33:23,260 --> 00:33:23,760 Horný. 791 00:33:23,760 --> 00:33:25,470 792 00:33:25,470 --> 00:33:26,970 A čo je toto bude rovnať? 793 00:33:26,970 --> 00:33:31,630 794 00:33:31,630 --> 00:33:33,690 Stredná mínus 1, pretože Samozrejme, chceme 795 00:33:33,690 --> 00:33:38,370 aby sa ubezpečil, že nie sme pri pohľade na tejto strednej hodnote znova. 796 00:33:38,370 --> 00:33:41,830 797 00:33:41,830 --> 00:33:45,110 A potom sme si to. 798 00:33:45,110 --> 00:33:45,610 To je všetko. 799 00:33:45,610 --> 00:33:46,820 To je všetko, binárne vyhľadávanie. 800 00:33:46,820 --> 00:33:48,190 Nie je to tak zlé, nie? 801 00:33:48,190 --> 00:33:51,590 Je to ako 10 riadkov kód s medzerou. 802 00:33:51,590 --> 00:33:57,510 Tak veľmi silný, veľmi užitočné, budete byť použitie v jednej zo svojich neskorších psets. 803 00:33:57,510 --> 00:33:59,360 Možno nie tento, ale neskôr. 804 00:33:59,360 --> 00:34:00,670 Tak sa to naučiť. 805 00:34:00,670 --> 00:34:01,510 Milovať. 806 00:34:01,510 --> 00:34:02,980 To vám dobre liečiť. 807 00:34:02,980 --> 00:34:05,370 Takže má niekto akékoľvek Otázky týkajúce sa binárne hľadanie? 808 00:34:05,370 --> 00:34:06,196 Áno. 809 00:34:06,196 --> 00:34:09,840 >> STUDENT: Záleží na tom, či je váš n je párne alebo nepárne? 810 00:34:09,840 --> 00:34:10,750 >> Inštruktor: Nie 811 00:34:10,750 --> 00:34:18,150 Pretože sme obsadil ju do stredu as int, bude to len skrátiť ho. 812 00:34:18,150 --> 00:34:21,600 Tak to zostane celé číslo a to bude nakoniec roztriediť všetko. 813 00:34:21,600 --> 00:34:23,909 Takže nemusíte mať strach o tom. 814 00:34:23,909 --> 00:34:24,580 Každý dobrý? 815 00:34:24,580 --> 00:34:25,659 816 00:34:25,659 --> 00:34:26,850 Úžasné. 817 00:34:26,850 --> 00:34:27,919 V pohode. 818 00:34:27,919 --> 00:34:30,836 Takže, vy ste dostali to. 819 00:34:30,836 --> 00:34:33,380 820 00:34:33,380 --> 00:34:33,880 Slideshow. 821 00:34:33,880 --> 00:34:35,719 822 00:34:35,719 --> 00:34:43,270 Tak, ako sme hovorili o, ja viem, David spomenul zložitosť doby chodu. 823 00:34:43,270 --> 00:34:44,420 824 00:34:44,420 --> 00:34:50,340 >> Takže v najlepšom prípade, je to len jeden, ktorý nazývame konštantný čas. 825 00:34:50,340 --> 00:34:51,909 Môže mi niekto povedať, prečo by to mohlo byť? 826 00:34:51,909 --> 00:34:52,969 827 00:34:52,969 --> 00:34:55,800 Aký typ scenára by to znamenalo? 828 00:34:55,800 --> 00:34:58,260 829 00:34:58,260 --> 00:34:58,760 Mm-hm. 830 00:34:58,760 --> 00:34:59,926 >> STUDENT: [nepočuteľné] first-- 831 00:34:59,926 --> 00:35:00,789 832 00:35:00,789 --> 00:35:03,830 Inštruktor: Takže stredná bytia Prvým prvkom, ktorý sa dostávame k, nie? 833 00:35:03,830 --> 00:35:08,167 Takže buď pole jednej alebo čo sme hľadali len 834 00:35:08,167 --> 00:35:09,750 sa stane, že plácnutí DAB v stredu. 835 00:35:09,750 --> 00:35:11,190 836 00:35:11,190 --> 00:35:13,380 Tak to je naša najlepšia prípad. 837 00:35:13,380 --> 00:35:17,540 Sa dostanete do skutočné problémy, pravdepodobne nie bude dosiahnuť [nepočuteľné], ktoré sa často. 838 00:35:17,540 --> 00:35:18,667 839 00:35:18,667 --> 00:35:19,750 Čo o našom najhoršom prípade? 840 00:35:19,750 --> 00:35:21,270 Náš najhorší prípad je log n. 841 00:35:21,270 --> 00:35:25,360 A že má čo do činenia s celým právomoci dve veci, ktoré som hovoril. 842 00:35:25,360 --> 00:35:30,930 >> Takže v najhoršom prípade by to znamenalo že sme museli kosiť polia dole 843 00:35:30,930 --> 00:35:33,270 kým nebolo súčasťou jednej. 844 00:35:33,270 --> 00:35:34,810 845 00:35:34,810 --> 00:35:38,930 Takže sme museli rozsekať ho na polovicu toľkokrát, koľkokrát, ako sme len mohli. 846 00:35:38,930 --> 00:35:41,430 To je dôvod, prečo je to log n, pretože stačí držať delenie dvoma. 847 00:35:41,430 --> 00:35:42,890 848 00:35:42,890 --> 00:35:45,830 Takže predpoklady, veci, ktoré Potrebujem vedieť, či ste niekedy 849 00:35:45,830 --> 00:35:48,050 bude používať binárne vyhľadávanie. 850 00:35:48,050 --> 00:35:50,680 Vaša prvky musia byť radené. 851 00:35:50,680 --> 00:35:53,890 Musia byť triedené, pretože že je to jediný spôsob, ako 852 00:35:53,890 --> 00:35:57,060 môžete vedieť, či ste schopní vyhodiť polovicu. 853 00:35:57,060 --> 00:36:00,260 >> Ak ste mali túto neusporiadané vrece čísel a vy hovoríte, 854 00:36:00,260 --> 00:36:05,380 OK, idem skontrolovať stred číslo a číslo Zháňam 855 00:36:05,380 --> 00:36:08,510 je menej ako to, že som jednoducho ísť ľubovoľne vyhodiť jednu polovicu. 856 00:36:08,510 --> 00:36:11,130 Tie by, ak nie vedieť vaše Čísla v tomto druhom polroku. 857 00:36:11,130 --> 00:36:12,655 Váš zoznam musí byť vyriešené. 858 00:36:12,655 --> 00:36:14,030 859 00:36:14,030 --> 00:36:16,560 Rovnako tak to môže byť pokračuje trochu, 860 00:36:16,560 --> 00:36:18,360 ale musíte mať náhodný prístup. 861 00:36:18,360 --> 00:36:21,940 Musíte byť schopní len ísť do tej prostrednej prvok. 862 00:36:21,940 --> 00:36:25,110 Ak máte prechádzať niečím 863 00:36:25,110 --> 00:36:28,630 alebo to trvá vám ďalšie kroky aby som sa dostal do stredného prvku, 864 00:36:28,630 --> 00:36:31,750 to sa prihlásiť n už preto, pridávate viac práce do neho. 865 00:36:31,750 --> 00:36:34,800 A to bude trochu väčší zmysel za dva týždne, 866 00:36:34,800 --> 00:36:37,950 ale ja som tak nejako chcel začínať, dať Vy predstavu o tom, čo je 867 00:36:37,950 --> 00:36:38,999 prísť. 868 00:36:38,999 --> 00:36:40,790 Ale to sú dva dôležité predpoklady 869 00:36:40,790 --> 00:36:44,804 ktoré budete potrebovať pre binárne zoznamu. 870 00:36:44,804 --> 00:36:45,720 Uistite sa, že je to triediť. 871 00:36:45,720 --> 00:36:47,920 To je ten veľký pre vy práve teraz. 872 00:36:47,920 --> 00:36:52,170 A na to môžeme ísť do zvyšok našich druhov. 873 00:36:52,170 --> 00:36:56,444 Takže štyri sorts-- bublina, vloženie, výber a korešpondencie. 874 00:36:56,444 --> 00:36:57,485 Sú to všetko celkom fajn. 875 00:36:57,485 --> 00:37:02,860 Ak vy rozhodnete pre CS 124, Dozviete sa o všetkých možných druhov. 876 00:37:02,860 --> 00:37:07,575 A ak ste fanúšik xkcd tu Je to naozaj v pohode komiks o 877 00:37:07,575 --> 00:37:11,530 ako veľmi neefektívne druhov, ktoré som Veľmi odporúčam vám ísť pozrieť. 878 00:37:11,530 --> 00:37:16,170 Jedným z nich je ako panickej druhu, ktorý je rád, oh nie, vráti náhodné polia. 879 00:37:16,170 --> 00:37:16,991 Vypnutie systému. 880 00:37:16,991 --> 00:37:17,490 Odísť. 881 00:37:17,490 --> 00:37:19,070 882 00:37:19,070 --> 00:37:21,500 Takže geek humor je vždy dobré. 883 00:37:21,500 --> 00:37:22,620 884 00:37:22,620 --> 00:37:25,750 >> Takže má niekto pamätať druh ako sa len všeobecnú predstavu 885 00:37:25,750 --> 00:37:27,810 o tom, ako bublina trochu funguje. 886 00:37:27,810 --> 00:37:31,130 887 00:37:31,130 --> 00:37:32,155 Pamätáš? 888 00:37:32,155 --> 00:37:32,755 >> STUDENT: Jo. 889 00:37:32,755 --> 00:37:33,970 >> Inštruktor: Choď do toho. 890 00:37:33,970 --> 00:37:38,980 >> Žiak: Takže ideš skrz ak je väčšia, potom vymeniť dva. 891 00:37:38,980 --> 00:37:39,820 >> Inštruktor: Mm-hm. 892 00:37:39,820 --> 00:37:40,564 Presne tak. 893 00:37:40,564 --> 00:37:41,730 Takže stačí iterovat. 894 00:37:41,730 --> 00:37:43,050 Môžete skontrolovať dve čísla. 895 00:37:43,050 --> 00:37:46,510 Ak pred jeden je väčší než je potom, 896 00:37:46,510 --> 00:37:50,230 stačí vymeniť ich tak, aby v Týmto spôsobom všetky vyšších čísel 897 00:37:50,230 --> 00:37:54,990 bublina až ku koncu zoznamu a všetky nižšie počty bublina dole. 898 00:37:54,990 --> 00:37:59,355 >> Povedal vám ukázať chlapci v pohode zvukový efekt triedenia video? 899 00:37:59,355 --> 00:38:00,480 Je to celkom v pohode. 900 00:38:00,480 --> 00:38:01,510 901 00:38:01,510 --> 00:38:05,200 Tak len povedal Robert, algoritmus ktorý ste práve krok v zozname, 902 00:38:05,200 --> 00:38:07,930 vymení susedné hodnoty v prípade, že nie ste v poriadku. 903 00:38:07,930 --> 00:38:10,975 A potom už len stále opakovať kým nemáte žiadne swapy. 904 00:38:10,975 --> 00:38:11,990 905 00:38:11,990 --> 00:38:12,740 Takže to nie je zlé, nie? 906 00:38:12,740 --> 00:38:14,080 907 00:38:14,080 --> 00:38:16,319 Tak sme si dať rýchly príklad tu. 908 00:38:16,319 --> 00:38:18,360 Takže to bude triediť je vo vzostupnom poradí. 909 00:38:18,360 --> 00:38:19,470 910 00:38:19,470 --> 00:38:23,470 Takže keď sme sa prejsť prvý Tentoraz sme sa pozrieť cez osem 911 00:38:23,470 --> 00:38:26,880 a šesť očividne nie sú v poradí, sme ich vymeniť. 912 00:38:26,880 --> 00:38:27,985 >> Tak sa pozrite na ten budúci. 913 00:38:27,985 --> 00:38:29,430 Osem a štyri nie je v poriadku. 914 00:38:29,430 --> 00:38:30,450 Vymeňte ich. 915 00:38:30,450 --> 00:38:32,530 A potom osem a dve, vymeňte ich. 916 00:38:32,530 --> 00:38:33,470 Tak ideme. 917 00:38:33,470 --> 00:38:39,519 Takže po prvom prechode, viete, že váš najväčší počet 918 00:38:39,519 --> 00:38:41,810 bude po celú cestu na vrchole, pretože je to len 919 00:38:41,810 --> 00:38:44,210 bude neustále väčší než všetko ostatné 920 00:38:44,210 --> 00:38:46,810 a to len tak, aby bubliny sa celú cestu až tam do konca. 921 00:38:46,810 --> 00:38:48,226 Má to zmysel pre každého? 922 00:38:48,226 --> 00:38:48,560 923 00:38:48,560 --> 00:38:49,060 V pohode. 924 00:38:49,060 --> 00:38:51,310 925 00:38:51,310 --> 00:38:53,920 >> Takže sa pozrieme na našu druhom prechode. 926 00:38:53,920 --> 00:38:54,980 Šesť a štyri, switch. 927 00:38:54,980 --> 00:38:55,920 Šesť a dve, switch. 928 00:38:55,920 --> 00:38:58,700 A teraz tu máme pár vecí do poriadku. 929 00:38:58,700 --> 00:39:02,240 Takže pre každý priechod, ktoré sme aby po celú dobu nášho zoznamu, 930 00:39:02,240 --> 00:39:06,320 Vieme, že rovnako ako, že veľa čísel na konci bude musieť byť zoradené. 931 00:39:06,320 --> 00:39:07,690 932 00:39:07,690 --> 00:39:09,610 Takže robíme tretej prihrávku, ktorý je jedným swap. 933 00:39:09,610 --> 00:39:10,860 934 00:39:10,860 --> 00:39:15,910 A potom sa na náš štvrtý prejsť, máme nulové štrbiny. 935 00:39:15,910 --> 00:39:18,570 A tak vieme, že naše pole bolo radené. 936 00:39:18,570 --> 00:39:20,900 >> A to je veľký vec bublinkové druhu. 937 00:39:20,900 --> 00:39:23,720 Vieme, že keď sme majú nulovú swapy, ktoré 938 00:39:23,720 --> 00:39:26,497 znamená, že všetko, čo je úplne poradí. 939 00:39:26,497 --> 00:39:27,580 Je to trochu ako skontrolovať. 940 00:39:27,580 --> 00:39:28,740 941 00:39:28,740 --> 00:39:36,480 Tak sme sa tiež bude kód bublinu druh, ktorý tiež nie je tak zlé. 942 00:39:36,480 --> 00:39:38,120 Žiadny z nich nie je tak zlé. 943 00:39:38,120 --> 00:39:40,210 Viem, že sa môže zdať trochu desivé. 944 00:39:40,210 --> 00:39:42,124 Viem, že keď som sa trieda, aj keď som 945 00:39:42,124 --> 00:39:44,290 učil triedu pre prvýkrát v minulom roku, 946 00:39:44,290 --> 00:39:46,165 Bol som rád, ako to mám urobiť? 947 00:39:46,165 --> 00:39:48,540 To dáva zmysel v teórii, ale ako to vlastne urobiť? 948 00:39:48,540 --> 00:39:51,420 Čo je dôvod, prečo aj ja chcem ísť prostredníctvom kódu s vami tu. 949 00:39:51,420 --> 00:39:54,915 Takže mám pseudokódu pre vás tentoraz. 950 00:39:54,915 --> 00:39:55,950 951 00:39:55,950 --> 00:39:58,970 Takže stačí mať na pamäti, ako chystáme sa prejsť cez. 952 00:39:58,970 --> 00:40:04,210 Takže máme nejaké počítadlo, ktoré udržuje naše swapov, 953 00:40:04,210 --> 00:40:08,370 pretože musíme uistiť, že sme overiť, že. 954 00:40:08,370 --> 00:40:11,830 A my opakovať celý rad ako sme práve urobil s týmto príkladom. 955 00:40:11,830 --> 00:40:12,900 956 00:40:12,900 --> 00:40:17,325 Ak je prvok predtým, než je väčšia než prvok neskôr, kde sme v, 957 00:40:17,325 --> 00:40:20,760 sme vymeniť je a my zvýšiť otázky counter pretože akonáhle sme sa vymeniť, 958 00:40:20,760 --> 00:40:23,850 Chceme, aby naše counter vedieť. 959 00:40:23,850 --> 00:40:26,247 Nejaké otázky? 960 00:40:26,247 --> 00:40:27,580 Niečo sa zdá smiešne sem. 961 00:40:27,580 --> 00:40:29,225 962 00:40:29,225 --> 00:40:32,350 STUDENT: Myslíte si nastaviť počítadlo na nulu zakaždým, keď idete cez slučku? 963 00:40:32,350 --> 00:40:34,339 Nezdá sa vám ísť ďalej späť na nulu zakaždým? 964 00:40:34,339 --> 00:40:35,505 Inštruktor: Nie nevyhnutne. 965 00:40:35,505 --> 00:40:39,710 Takže čo sa stane, je, že sme prejsť tu. 966 00:40:39,710 --> 00:40:43,830 Tak robiť, keď, pamätajte, že táto bude vykonávať raz bez výnimky. 967 00:40:43,830 --> 00:40:46,480 Takže to bude nastavenie čítač rovný nule, 968 00:40:46,480 --> 00:40:48,070 potom to bude iterovat. 969 00:40:48,070 --> 00:40:50,590 Ako to prejde, to bude aktualizovať počítadlo. 970 00:40:50,590 --> 00:40:51,870 971 00:40:51,870 --> 00:40:56,900 Ako sa aktualizuje čítač, keď sa to robí, keď to dosiahne konca poľa, 972 00:40:56,900 --> 00:41:00,830 ak náš zoznam nie je triedené, čítača boli aktualizované. 973 00:41:00,830 --> 00:41:01,840 974 00:41:01,840 --> 00:41:07,150 >> Tak sa kontroluje stav a to hovorí: OK, je čítač väčší ako nula. 975 00:41:07,150 --> 00:41:09,290 Ak je, urobiť to znova. 976 00:41:09,290 --> 00:41:14,340 Ak chcete obnoviť tak, že keď vás prejsť, čítač je rovná nule. 977 00:41:14,340 --> 00:41:18,240 Ak pôjdete cez triedených polia, nič sa nezmení, 978 00:41:18,240 --> 00:41:21,355 tento postup zlyhá, a vrátiť zoradený zoznam. 979 00:41:21,355 --> 00:41:23,104 980 00:41:23,104 --> 00:41:24,020 Má to zmysel? 981 00:41:24,020 --> 00:41:24,940 982 00:41:24,940 --> 00:41:26,356 STUDENT: Mohlo by sa trochu. 983 00:41:26,356 --> 00:41:27,147 Inštruktor: OK. 984 00:41:27,147 --> 00:41:28,980 Ak existuje akákoľvek iná otázka, ktorá príde. 985 00:41:28,980 --> 00:41:30,180 986 00:41:30,180 --> 00:41:30,680 Áno. 987 00:41:30,680 --> 00:41:33,760 >> STUDENT: Čo by funkcia byť pre prečerpanie prvky? 988 00:41:33,760 --> 00:41:36,900 >> Inštruktor: Takže vlastne môžeme napísať že ak budeme práve teraz. 989 00:41:36,900 --> 00:41:37,801 990 00:41:37,801 --> 00:41:38,300 V pohode. 991 00:41:38,300 --> 00:41:42,155 Takže v takom prípade, Alison sa deje prepnúť späť do prístroja. 992 00:41:42,155 --> 00:41:43,080 To bude sranda. 993 00:41:43,080 --> 00:41:45,170 994 00:41:45,170 --> 00:41:47,390 A máme pekný bubble sort, čo tu. 995 00:41:47,390 --> 00:41:50,800 Tak som to už urobil na bicykli cez pole. 996 00:41:50,800 --> 00:41:53,030 Máme swapy, ktoré sú rovné nule. 997 00:41:53,030 --> 00:41:54,480 998 00:41:54,480 --> 00:41:58,440 Takže chceme vymeniť priľahlé prvky, pokiaľ sú mimo prevádzky. 999 00:41:58,440 --> 00:42:03,020 Takže prvá vec, ktorú musíme to je iterovat našu ponuku. 1000 00:42:03,020 --> 00:42:04,500 1001 00:42:04,500 --> 00:42:08,260 >> Tak ako si myslíte, že by sme mohli iterovat našej ponuku? 1002 00:42:08,260 --> 00:42:09,720 1003 00:42:09,720 --> 00:42:13,990 Máme pre a i = 0. 1004 00:42:13,990 --> 00:42:16,950 1005 00:42:16,950 --> 00:42:22,454 Chceme byť aj nižšia ako n mínus 1 mínus k. 1006 00:42:22,454 --> 00:42:23,870 A ja budem vysvetľovať, že v sekunde. 1007 00:42:23,870 --> 00:42:26,280 1008 00:42:26,280 --> 00:42:32,830 Tak toto je optimalizácia tu, kde Spomínam si, ako som povedal, po každom priechode 1009 00:42:32,830 --> 00:42:36,655 cez pole my viem, že to, čo je on-- 1010 00:42:36,655 --> 00:42:43,590 1011 00:42:43,590 --> 00:42:46,295 >> Takže po jednom prechode sme viem, že to je radený. 1012 00:42:46,295 --> 00:42:47,370 1013 00:42:47,370 --> 00:42:50,060 Po dvoch priechodoch vieme, že to všetko je usporiadaný. 1014 00:42:50,060 --> 00:42:52,750 Po troch priechodoch sme viem, že je triediť. 1015 00:42:52,750 --> 00:42:55,620 Tak, ako som iterácie cez pole tu 1016 00:42:55,620 --> 00:43:01,090 Je to uistite sa, ísť len prostredníctvom toho, čo vieme, je netriedený. 1017 00:43:01,090 --> 00:43:01,644 OK? 1018 00:43:01,644 --> 00:43:02,810 To je len optimalizácia. 1019 00:43:02,810 --> 00:43:04,430 1020 00:43:04,430 --> 00:43:08,210 Dalo by sa napísať naivne len iterácie cez všetko, 1021 00:43:08,210 --> 00:43:09,970 by to jednoducho trvať dlhšie. 1022 00:43:09,970 --> 00:43:12,470 S týmto štyri slučky je len pekný optimalizácia 1023 00:43:12,470 --> 00:43:18,460 pretože vieme, že po každej plnej iteráciu cez pole tu, 1024 00:43:18,460 --> 00:43:24,050 ako každú celú slučku tu vieme, že jeden z týchto prvkov 1025 00:43:24,050 --> 00:43:25,760 budú rozdelené na konci. 1026 00:43:25,760 --> 00:43:28,294 >> Tak sme sa nemuseli starať o tie. 1027 00:43:28,294 --> 00:43:29,710 Má to zmysel pre každého? 1028 00:43:29,710 --> 00:43:30,950 Že v pohode malý trik? 1029 00:43:30,950 --> 00:43:32,060 1030 00:43:32,060 --> 00:43:37,270 Takže v tomto prípade, ak sme iterácie, 1031 00:43:37,270 --> 00:43:50,590 vieme, že chceme zistiť, či polia n a n + 1 sú v poriadku. 1032 00:43:50,590 --> 00:43:52,640 1033 00:43:52,640 --> 00:43:53,559 OK. 1034 00:43:53,559 --> 00:43:54,600 Tak tu je pseudokódu. 1035 00:43:54,600 --> 00:43:57,540 Chceme zistiť, či pole n a n a 1 sú v poriadku. 1036 00:43:57,540 --> 00:43:59,520 Takže to, čo môžeme mať, že? 1037 00:43:59,520 --> 00:44:01,090 1038 00:44:01,090 --> 00:44:03,120 Bude to mať nejaký podmienené. 1039 00:44:03,120 --> 00:44:04,220 Ak bude. 1040 00:44:04,220 --> 00:44:07,066 >> STUDENT: Ak je pole n je menej ako pole n plus 1. 1041 00:44:07,066 --> 00:44:07,816 Inštruktor: Mm-hm. 1042 00:44:07,816 --> 00:44:09,000 1043 00:44:09,000 --> 00:44:10,699 No, menšia alebo väčšia ako. 1044 00:44:10,699 --> 00:44:11,615 STUDENT: Väčšie ako. 1045 00:44:11,615 --> 00:44:15,850 1046 00:44:15,850 --> 00:44:17,620 Potom ich chceme vymeniť. 1047 00:44:17,620 --> 00:44:18,570 Presne tak. 1048 00:44:18,570 --> 00:44:23,570 Takže teraz sme sa dostali do toho, čo je Mechanizmus je vymieňať? 1049 00:44:23,570 --> 00:44:24,840 1050 00:44:24,840 --> 00:44:28,137 Tak sme šli cez túto krátku dobu, typ funkcie odkladacieho minulý týždeň. 1051 00:44:28,137 --> 00:44:29,595 Pamätá si niekto, ako to funguje? 1052 00:44:29,595 --> 00:44:32,300 1053 00:44:32,300 --> 00:44:34,950 Takže môžeme nielen priradiť im, že jo? 1054 00:44:34,950 --> 00:44:36,640 Vzhľadom k tomu, jeden z nich sa stratí. 1055 00:44:36,640 --> 00:44:41,696 Ak sme povedali, sa rovná B a B je rovná A, všetky náhle obaja 1056 00:44:41,696 --> 00:44:43,150 sú len rovná B. 1057 00:44:43,150 --> 00:44:45,720 >> Takže to, čo musíme urobiť, je, že sme majú dočasné premenné, ktoré je 1058 00:44:45,720 --> 00:44:49,055 bude držať jeden z našich chvíľu sme v procese vymieňať. 1059 00:44:49,055 --> 00:44:50,200 1060 00:44:50,200 --> 00:44:56,464 Takže to, čo máme, je, že budeme musieť nejakú int teplota je rovná to-- môžete priradiť 1061 00:44:56,464 --> 00:44:59,130 sa podľa toho, čo potrebujete, stačí uistite sa, že budete mať prehľad o to-- 1062 00:44:59,130 --> 00:45:01,840 takže v tomto prípade budem priradiť k poľu n plus 1. 1063 00:45:01,840 --> 00:45:03,360 1064 00:45:03,360 --> 00:45:07,674 Tak, že to bude držať bez ohľadu na hodnota je v tomto druhom bloku 1065 00:45:07,674 --> 00:45:08,590 že sa pozeráme. 1066 00:45:08,590 --> 00:45:09,700 1067 00:45:09,700 --> 00:45:13,240 >> A potom, čo môžeme urobiť je, že môže ísť dopredu a Preradiť pole n + 1, 1068 00:45:13,240 --> 00:45:14,990 pretože my vieme, majú túto hodnotu uloženú. 1069 00:45:14,990 --> 00:45:16,645 1070 00:45:16,645 --> 00:45:19,270 To je tiež jeden z veľkých things-- nemám, ak niekto z vás vedieť, 1071 00:45:19,270 --> 00:45:23,780 mal problémy, kde keď prepnete dvaja riadkov kódu náhle veci fungujú. 1072 00:45:23,780 --> 00:45:25,880 Objednávka je veľmi dôležité v CS. 1073 00:45:25,880 --> 00:45:29,450 Takže sa uistite, diagram veci, ak je to možné 1074 00:45:29,450 --> 00:45:31,230 pokiaľ ide o to, čo sa skutočne deje. 1075 00:45:31,230 --> 00:45:34,256 Takže teraz budeme priradenie pole n + 1, 1076 00:45:34,256 --> 00:45:36,005 pretože my vieme, majú túto hodnotu uloženú. 1077 00:45:36,005 --> 00:45:37,090 1078 00:45:37,090 --> 00:45:41,560 >> A môžeme priradiť, že na poli n, alebo v tomto prípade aj pole. 1079 00:45:41,560 --> 00:45:50,540 1080 00:45:50,540 --> 00:45:51,465 Príliš veľa premenných. 1081 00:45:51,465 --> 00:45:54,230 1082 00:45:54,230 --> 00:45:55,470 OK. 1083 00:45:55,470 --> 00:46:01,500 Takže teraz sme prevelený pole I plus 1 sa rovná, čo je v poli i. 1084 00:46:01,500 --> 00:46:08,240 A teraz sa môžeme vrátiť a priradiť polia som sa, čo? 1085 00:46:08,240 --> 00:46:10,680 1086 00:46:10,680 --> 00:46:11,180 Každý, kto? 1087 00:46:11,180 --> 00:46:13,490 1088 00:46:13,490 --> 00:46:14,010 >> STUDENT: 10. 1089 00:46:14,010 --> 00:46:14,680 >> Inštruktor: 10. 1090 00:46:14,680 --> 00:46:15,180 Presne tak. 1091 00:46:15,180 --> 00:46:16,930 1092 00:46:16,930 --> 00:46:18,640 A ešte jedna posledná vec. 1093 00:46:18,640 --> 00:46:21,840 Ak sme vymenili hneď, Čo musíme urobiť? 1094 00:46:21,840 --> 00:46:23,740 Čo je jedna vec, , Čo sa deje, aby nám povedali 1095 00:46:23,740 --> 00:46:27,542 či sa niekedy ukončiť tento program? 1096 00:46:27,542 --> 00:46:29,250 Čo nám hovorí, že majú zoradený zoznam? 1097 00:46:29,250 --> 00:46:31,560 1098 00:46:31,560 --> 00:46:33,750 Ak nebudeme vykonávať žiadne swapy, že jo? 1099 00:46:33,750 --> 00:46:36,900 Ak swapov sa rovná nulu na konci tohto. 1100 00:46:36,900 --> 00:46:42,975 Takže kedykoľvek vykonať výmenu, ako my práve tu urobil, chceme aktualizovať swapy. 1101 00:46:42,975 --> 00:46:45,002 1102 00:46:45,002 --> 00:46:47,210 A viem, že tam bol Otázka skôr o môžete 1103 00:46:47,210 --> 00:46:49,689 použiť nula alebo jedna, miesto true alebo false. 1104 00:46:49,689 --> 00:46:50,980 A to je to, čo to robí tu. 1105 00:46:50,980 --> 00:46:52,750 Tak to hovorí, ak nie swapy. 1106 00:46:52,750 --> 00:47:01,310 Takže ak swapov je nula, čo je-- vždycky dostať moje pravdy a mojej falses poplietol. 1107 00:47:01,310 --> 00:47:03,960 Chceme, aby sme mohli zhodnotiť na hodnotu true, a to nie je. 1108 00:47:03,960 --> 00:47:07,680 1109 00:47:07,680 --> 00:47:09,630 Takže ak je to nula, potom je to falošné. 1110 00:47:09,630 --> 00:47:12,560 Ak to popierajú s [? bang?] sa stáva pravdou. 1111 00:47:12,560 --> 00:47:13,975 Takže tento riadok spustí. 1112 00:47:13,975 --> 00:47:15,060 1113 00:47:15,060 --> 00:47:17,370 >> Pravdy a falošné a núl a jednotiek si blázon. 1114 00:47:17,370 --> 00:47:20,690 Len ak ste pomaly chodiť cez to, že bude mať zmysel. 1115 00:47:20,690 --> 00:47:23,320 Ale to je to, čo tento malý bit kódu tu robí. 1116 00:47:23,320 --> 00:47:26,490 Takže to skontroluje, sme urobili nejaké swapy. 1117 00:47:26,490 --> 00:47:30,054 Takže ak je to niečo naviac nula, bude to, že je falošný 1118 00:47:30,054 --> 00:47:31,970 a celá vec je bude znovu spustiť. 1119 00:47:31,970 --> 00:47:33,150 1120 00:47:33,150 --> 00:47:33,650 V pohode? 1121 00:47:33,650 --> 00:47:34,660 1122 00:47:34,660 --> 00:47:36,000 >> Študent: Čo je prestávka robiť? 1123 00:47:36,000 --> 00:47:38,990 >> Inštruktor: Prestávka len vypukne vás zo slučky. 1124 00:47:38,990 --> 00:47:41,570 Takže v tomto prípade by rovnako ako ukončenie programu 1125 00:47:41,570 --> 00:47:43,828 a tie by len mať svoj zoradený zoznam. 1126 00:47:43,828 --> 00:47:44,536 STUDENT: Amazing. 1127 00:47:44,536 --> 00:47:48,094 1128 00:47:48,094 --> 00:47:49,010 Inštruktor: Ospravedlňujem sa? 1129 00:47:49,010 --> 00:47:52,110 STUDENT: Pretože predtým sme použité písomné 1 prepísané nulu 1130 00:47:52,110 --> 00:47:54,170 predstaviť, že v prípade, že bude fungovať, alebo nie. 1131 00:47:54,170 --> 00:47:54,878 >> Inštruktor: Jo. 1132 00:47:54,878 --> 00:47:56,410 Takže sa môžete vrátiť nula alebo jedna. 1133 00:47:56,410 --> 00:47:58,950 V tomto prípade, pretože nie sme v skutočnosti robiť niečo s funkciou, 1134 00:47:58,950 --> 00:48:00,150 chceme len to zlomiť. 1135 00:48:00,150 --> 00:48:02,680 Sme naozaj nestarám o to. 1136 00:48:02,680 --> 00:48:06,960 Brzda je tiež dobré, ak je použitá pre prepukajú 1137 00:48:06,960 --> 00:48:10,710 zo štyroch slučiek alebo podmienok, ktoré Nechcete, aby vykonávanie. 1138 00:48:10,710 --> 00:48:12,110 Stačí len tí z nich. 1139 00:48:12,110 --> 00:48:13,587 1140 00:48:13,587 --> 00:48:14,795 Je to trochu nuansy vec. 1141 00:48:14,795 --> 00:48:16,737 1142 00:48:16,737 --> 00:48:18,445 Mám pocit, že je tu veľa ručnej onduláciu, 1143 00:48:18,445 --> 00:48:19,740 rovnako ako sa dozviete o tom čoskoro. 1144 00:48:19,740 --> 00:48:20,955 >> Ale vy sa dozviete o tom čoskoro. 1145 00:48:20,955 --> 00:48:21,500 Sľubujem. 1146 00:48:21,500 --> 00:48:22,670 1147 00:48:22,670 --> 00:48:23,170 OK. 1148 00:48:23,170 --> 00:48:24,840 Takže sa všetci dostať Bublinkové triedenie? 1149 00:48:24,840 --> 00:48:25,550 Nie je to tak zlé. 1150 00:48:25,550 --> 00:48:31,910 Iterovat, výmenné veci pomocou temp variabilný, a všetci tam nastaviť? 1151 00:48:31,910 --> 00:48:32,960 V pohode. 1152 00:48:32,960 --> 00:48:34,080 Úžasné. 1153 00:48:34,080 --> 00:48:34,807 OK. 1154 00:48:34,807 --> 00:48:35,765 Späť na PowerPoint. 1155 00:48:35,765 --> 00:48:38,140 1156 00:48:38,140 --> 00:48:40,130 Akékoľvek otázky všeobecne o nich tak ďaleko? 1157 00:48:40,130 --> 00:48:41,200 1158 00:48:41,200 --> 00:48:41,700 V pohode. 1159 00:48:41,700 --> 00:48:43,110 1160 00:48:43,110 --> 00:48:43,695 Mm-hm. 1161 00:48:43,695 --> 00:48:45,279 >> STUDENT: [nepočuteľné] int main zvyčajne. 1162 00:48:45,279 --> 00:48:46,695 Máte mať to za to? 1163 00:48:46,695 --> 00:48:48,400 1164 00:48:48,400 --> 00:48:53,550 >> Inštruktor: Tak sme boli len hľadáte len na skutočný triedenie algoritmu. 1165 00:48:53,550 --> 00:48:54,559 1166 00:48:54,559 --> 00:48:56,350 Ak ste ju mal v rámci ako väčšieho programu, 1167 00:48:56,350 --> 00:48:57,891 budete mať int main niekde. 1168 00:48:57,891 --> 00:49:00,070 1169 00:49:00,070 --> 00:49:02,880 V závislosti na tom, kde ste použitie tohto algoritmu, 1170 00:49:02,880 --> 00:49:05,860 by to zistiť, čo je vrátenej to. 1171 00:49:05,860 --> 00:49:09,960 Ale pre náš prípad, my sme striktne pri pohľade na to, ako to robí v skutočnosti 1172 00:49:09,960 --> 00:49:11,300 iterovat poľa. 1173 00:49:11,300 --> 00:49:12,570 Tak sme sa nemusíte starať o to. 1174 00:49:12,570 --> 00:49:14,150 1175 00:49:14,150 --> 00:49:19,830 >> Tak sme hovorili o najlepšom prípade a najhorších scenárov pre binárne vyhľadávanie. 1176 00:49:19,830 --> 00:49:22,470 Tak to je tiež dôležité, aby sa že pre každý z našich druhov. 1177 00:49:22,470 --> 00:49:24,200 1178 00:49:24,200 --> 00:49:27,560 Takže to, čo si myslíte, že je to najhoršie, Prípad runtime bublinkovej druhu? 1179 00:49:27,560 --> 00:49:29,560 1180 00:49:29,560 --> 00:49:30,700 Vy pamätáte? 1181 00:49:30,700 --> 00:49:31,784 >> STUDENT: N mínus 1. 1182 00:49:31,784 --> 00:49:32,700 Inštruktor: N mínus 1. 1183 00:49:32,700 --> 00:49:35,070 Takže to znamená, že existujú n mínus 1 porovnanie. 1184 00:49:35,070 --> 00:49:40,060 Takže jedna vec je uvedomiť si, že na prvú iteráciu, 1185 00:49:40,060 --> 00:49:43,360 prejdeme, budeme porovnávať Tieto two-- tak to je 1. 1186 00:49:43,360 --> 00:49:46,685 Tieto dva, tri, štyri. 1187 00:49:46,685 --> 00:49:48,070 1188 00:49:48,070 --> 00:49:55,050 Takže po jednom prechode sme už štyri porovnanie. 1189 00:49:55,050 --> 00:49:58,230 Keď hovorím o behu a n. 1190 00:49:58,230 --> 00:50:04,680 N predstavuje počet porovnaní v závislosti na tom, ako veľa prvkov 1191 00:50:04,680 --> 00:50:05,570 máme. 1192 00:50:05,570 --> 00:50:06,430 OK? 1193 00:50:06,430 --> 00:50:08,860 >> Tak sme sa prejsť, máme štyri. 1194 00:50:08,860 --> 00:50:11,780 Až sa nabudúce budete vedieť, že nie musí sa postarať o to. 1195 00:50:11,780 --> 00:50:15,140 Porovnáme tieto dva, tieto dve, tieto dva, 1196 00:50:15,140 --> 00:50:20,050 a keď sme nemali, že optimalizácia so štyrmi slučky, ktoré som napísal, 1197 00:50:20,050 --> 00:50:22,750 by ste sa nákupný tu tak ako tak. 1198 00:50:22,750 --> 00:50:26,170 Takže budete musieť prejsť pole 1199 00:50:26,170 --> 00:50:34,380 a aby n n porovnanie časy, pretože zakaždým, keď 1200 00:50:34,380 --> 00:50:36,670 beh cez to triedime jednu vec. 1201 00:50:36,670 --> 00:50:38,300 1202 00:50:38,300 --> 00:50:41,475 >> A zakaždým, keď sme sa prejsť pole, robíme n porovnanie. 1203 00:50:41,475 --> 00:50:42,920 1204 00:50:42,920 --> 00:50:46,330 Takže naša runtime je to v skutočnosti n na druhú, čo 1205 00:50:46,330 --> 00:50:48,400 je oveľa horšia v našej Prihlásenie koniec, pretože to 1206 00:50:48,400 --> 00:50:51,965 znamená, že ak sme mali štyri miliardy prvky, je to 1207 00:50:51,965 --> 00:50:55,260 bude nám trvať štyri miliardy štvorcový miesto 32. 1208 00:50:55,260 --> 00:51:01,240 Takže nie je najlepší runtime, ale niektoré veci, 1209 00:51:01,240 --> 00:51:04,610 viete, ak ste v určitý sortiment prvkov 1210 00:51:04,610 --> 00:51:06,540 bublina druh môže byť v pohode použiť. 1211 00:51:06,540 --> 00:51:07,530 >> OK. 1212 00:51:07,530 --> 00:51:12,290 Takže teraz to, čo je v najlepšom prípade runtime? 1213 00:51:12,290 --> 00:51:14,357 1214 00:51:14,357 --> 00:51:14,940 STUDENT: Zero? 1215 00:51:14,940 --> 00:51:16,420 Alebo 1? 1216 00:51:16,420 --> 00:51:18,140 >> Inštruktor: Takže 1 by byť jeden porovnanie. 1217 00:51:18,140 --> 00:51:19,114 Presne tak. 1218 00:51:19,114 --> 00:51:20,002 >> STUDENT: N mínus 1? 1219 00:51:20,002 --> 00:51:21,380 1220 00:51:21,380 --> 00:51:22,320 >> Inštruktor: Tak jo. 1221 00:51:22,320 --> 00:51:22,990 Tak n mínus 1. 1222 00:51:22,990 --> 00:51:26,510 Kedykoľvek budete mať predstavu, ako n mínus 1, máme tendenciu nechaj ho 1223 00:51:26,510 --> 00:51:31,680 a my sme len povedať, n, pretože máte porovnať každý z these-- každého páru. 1224 00:51:31,680 --> 00:51:36,470 Bolo by teda n mínus 1, ktoré sme práve povedal je približne n. 1225 00:51:36,470 --> 00:51:39,280 Keď máte čo do činenia s behu, všetko je v zbližuje. 1226 00:51:39,280 --> 00:51:43,860 Tak dlho, ako je exponent správne, že ste celkom dobrý. 1227 00:51:43,860 --> 00:51:45,700 >> To je to, ako sa s tým vysporiadať. 1228 00:51:45,700 --> 00:51:47,410 1229 00:51:47,410 --> 00:51:51,780 Tak, že najlepšom prípade je n, ktorý znamená, že zoznam už je zoradený, 1230 00:51:51,780 --> 00:51:54,320 a všetko, čo urobiť, je spustiť pomocou a skontrolujte, či je to triediť. 1231 00:51:54,320 --> 00:51:56,110 1232 00:51:56,110 --> 00:51:56,855 V pohode. 1233 00:51:56,855 --> 00:51:57,355 Dobrá. 1234 00:51:57,355 --> 00:51:58,980 1235 00:51:58,980 --> 00:52:01,920 Takže ako vidíte tu, aby sme len nejaké ďalšie grafy. 1236 00:52:01,920 --> 00:52:02,660 Tak n na druhú. 1237 00:52:02,660 --> 00:52:03,780 1238 00:52:03,780 --> 00:52:05,120 Fun. 1239 00:52:05,120 --> 00:52:09,730 Oveľa horšie ako n, ako vidíme, a oveľa, oveľa horšie, než log 2n. 1240 00:52:09,730 --> 00:52:12,060 A potom sa môžete tiež dostať do protokolov protokolu. 1241 00:52:12,060 --> 00:52:18,020 A budete mať 124, sa dostanete do ako log Star, ktorého sa ako blázon. 1242 00:52:18,020 --> 00:52:20,172 Takže ak máte záujem, vyhľadávanie log hviezda. 1243 00:52:20,172 --> 00:52:20,880 Je to celkom sranda. 1244 00:52:20,880 --> 00:52:22,800 1245 00:52:22,800 --> 00:52:24,220 Takže máme tento skvelý graf. 1246 00:52:24,220 --> 00:52:25,360 1247 00:52:25,360 --> 00:52:28,720 Len heads up, to nádherný graf mať 1248 00:52:28,720 --> 00:52:31,350 pre strednodobé, pretože sme dlho sa vás opýtať na tieto tenšie. 1249 00:52:31,350 --> 00:52:36,090 Takže len heads up, mať to na vašom v polovici obdobia na svojom peknom ťahák 1250 00:52:36,090 --> 00:52:36,616 tu. 1251 00:52:36,616 --> 00:52:37,990 Tak sme sa len pozrel na bubliny druhu. 1252 00:52:37,990 --> 00:52:39,510 1253 00:52:39,510 --> 00:52:42,370 V najhoršom prípade, n na druhú, najlepšia vec, n. 1254 00:52:42,370 --> 00:52:43,367 1255 00:52:43,367 --> 00:52:44,950 A budeme sa pozrieť na ostatné. 1256 00:52:44,950 --> 00:52:47,940 >> A ako môžete vidieť, len ten, ktorý naozaj robí dobre 1257 00:52:47,940 --> 00:52:50,910 je merge sort, ktorý budeme mať na to, prečo. 1258 00:52:50,910 --> 00:52:52,690 1259 00:52:52,690 --> 00:52:55,215 Takže sme ísť do budúci here-- výber sort. 1260 00:52:55,215 --> 00:52:56,360 1261 00:52:56,360 --> 00:52:58,420 Pamätá si niekto, ako Výber sort pracoval? 1262 00:52:58,420 --> 00:53:05,200 1263 00:53:05,200 --> 00:53:05,700 Ísť na to. 1264 00:53:05,700 --> 00:53:08,210 >> STUDENT: V podstate prejsť poradí a vytvoriť nový zoznam. 1265 00:53:08,210 --> 00:53:11,001 A rovnako ako vy uvedenie prvky in, dal ich na správnom mieste 1266 00:53:11,001 --> 00:53:11,750 v novom zozname. 1267 00:53:11,750 --> 00:53:14,040 >> Inštruktor: Takže zvuky spíš vkladanie druhu. 1268 00:53:14,040 --> 00:53:15,040 Ale ty si naozaj blízko. 1269 00:53:15,040 --> 00:53:15,915 Sú veľmi podobné. 1270 00:53:15,915 --> 00:53:17,440 Dokonca som si ich poplietol niekedy. 1271 00:53:17,440 --> 00:53:18,981 Pred tejto sekcii bol som rád, počkajte. 1272 00:53:18,981 --> 00:53:20,130 1273 00:53:20,130 --> 00:53:20,630 OK. 1274 00:53:20,630 --> 00:53:24,141 Takže to, čo chcete urobiť, je výber triediť, 1275 00:53:24,141 --> 00:53:25,890 spôsob, ako si môžete myslieť o ňom a spôsobe 1276 00:53:25,890 --> 00:53:30,140 Môžem uistiť, že som sa pokúsiť sa dostať je poplietol, je to prechádza 1277 00:53:30,140 --> 00:53:33,280 a vyberie Najmenšie číslo, a to 1278 00:53:33,280 --> 00:53:36,070 uvádza, že na začiatku zoznamu. 1279 00:53:36,070 --> 00:53:37,730 To swapy s týmto prvom mieste. 1280 00:53:37,730 --> 00:53:42,600 1281 00:53:42,600 --> 00:53:45,370 Sú to vlastne máme príklad pre mňa. 1282 00:53:45,370 --> 00:53:46,540 Úžasné. 1283 00:53:46,540 --> 00:53:50,130 Takže len spôsob, ako myslieť na to-- výbere druh, vyberte najmenšiu hodnotu. 1284 00:53:50,130 --> 00:53:51,940 A budeme sa spustiť pomocou príkladu 1285 00:53:51,940 --> 00:53:55,320 si myslím, že pomôže, pretože Myslím si, že vizuálna vždy pomôcť. 1286 00:53:55,320 --> 00:53:58,510 Takže začneme s niečím že je úplne netriedený. 1287 00:53:58,510 --> 00:54:00,730 Red bude netriedený, zelená bude triediť. 1288 00:54:00,730 --> 00:54:02,190 To všetko dáva zmysel v sekunde. 1289 00:54:02,190 --> 00:54:08,950 >> Tak sme sa prejsť a my iterovat od začiatku až do konca. 1290 00:54:08,950 --> 00:54:12,320 A my hovoríme, OK, 2 naše najmenšie číslo. 1291 00:54:12,320 --> 00:54:15,680 Takže budeme mať 2 a ideme presunúť do prednej časti našej ponuku 1292 00:54:15,680 --> 00:54:17,734 pretože je to najmenšie číslo máme. 1293 00:54:17,734 --> 00:54:19,150 Takže to je to, čo to robí. 1294 00:54:19,150 --> 00:54:20,820 Je to len tak vymeniť tie dva. 1295 00:54:20,820 --> 00:54:21,850 1296 00:54:21,850 --> 00:54:25,450 Takže teraz sme radené časť a netriedené časť. 1297 00:54:25,450 --> 00:54:27,810 A čo je dobré si uvedomiť, o výbere druhu 1298 00:54:27,810 --> 00:54:30,690 je, že sme už len výber z netriedeného časti. 1299 00:54:30,690 --> 00:54:32,220 1300 00:54:32,220 --> 00:54:34,527 >> Vytriedený časť, ktorú jednoducho nechať na pokoji. 1301 00:54:34,527 --> 00:54:35,660 Mm-hm? 1302 00:54:35,660 --> 00:54:38,452 >> STUDENT: Ako to vieš, čo je najmenší bez porovnania 1303 00:54:38,452 --> 00:54:39,868 na každej iné hodnoty v poli. 1304 00:54:39,868 --> 00:54:41,250 Inštruktor: Robí porovnať. 1305 00:54:41,250 --> 00:54:42,041 Radi preskočí to. 1306 00:54:42,041 --> 00:54:43,850 To je len všeobecná celkovo. 1307 00:54:43,850 --> 00:54:44,831 Jo. 1308 00:54:44,831 --> 00:54:47,205 Keď sme písať kód Som istí, že budete viac spokojní. 1309 00:54:47,205 --> 00:54:48,696 1310 00:54:48,696 --> 00:54:53,030 Ale uložiť tento prvý prvok najmenší. 1311 00:54:53,030 --> 00:54:56,110 Môžete porovnať a hovoria, OK, je to menšie? 1312 00:54:56,110 --> 00:54:56,660 Áno. 1313 00:54:56,660 --> 00:54:57,460 Nechaj si to. 1314 00:54:57,460 --> 00:54:58,640 Tu je to menšie? 1315 00:54:58,640 --> 00:54:59,660 Nie? 1316 00:54:59,660 --> 00:55:02,510 >> To je vaše najmenšie, priradiť ju k svojmu hodnotu. 1317 00:55:02,510 --> 00:55:06,340 A budete oveľa šťastnejší keď ideme cez kód. 1318 00:55:06,340 --> 00:55:07,510 1319 00:55:07,510 --> 00:55:13,970 Tak sme sa prejsť, sme to vymeniť, tak potom sa pozrieme na tomto netriedeného časti. 1320 00:55:13,970 --> 00:55:15,810 Takže ideme vybrať tri z. 1321 00:55:15,810 --> 00:55:18,890 Chystáme sa dať na na koniec našej triedeného časti. 1322 00:55:18,890 --> 00:55:20,267 1323 00:55:20,267 --> 00:55:23,100 A my sme len tak, aby robil to, že robí to, a robiť, že. 1324 00:55:23,100 --> 00:55:24,130 1325 00:55:24,130 --> 00:55:27,420 Tak toto je náš druh pseudokódu tu. 1326 00:55:27,420 --> 00:55:29,470 1327 00:55:29,470 --> 00:55:31,380 Budeme kód to tu v sekunde. 1328 00:55:31,380 --> 00:55:34,140 1329 00:55:34,140 --> 00:55:37,270 Ale len niečo chodiť cez na vysokej úrovni. 1330 00:55:37,270 --> 00:55:40,275 Budeš chodiť od i = 0 pre n mínus 2. 1331 00:55:40,275 --> 00:55:41,570 1332 00:55:41,570 --> 00:55:43,530 To je ďalšia optimalizácia. 1333 00:55:43,530 --> 00:55:45,020 Nebojte sa príliš veľa o tom. 1334 00:55:45,020 --> 00:55:46,620 Tak ako si hovoril. 1335 00:55:46,620 --> 00:55:49,660 1336 00:55:49,660 --> 00:55:54,406 Ako Jacob hovoril, ako my sledovať, čo náš minimum je? 1337 00:55:54,406 --> 00:55:55,030 Ako to vieme? 1338 00:55:55,030 --> 00:55:57,060 Musíme porovnať všetko v našom zozname. 1339 00:55:57,060 --> 00:55:59,600 >> Takže minimálne rovná i. 1340 00:55:59,600 --> 00:56:03,870 Je to len hovorím, v tomto prípade index nášho minimálnu hodnotu. 1341 00:56:03,870 --> 00:56:07,660 Takže to bude iterovat a to ide od j je rovný i + 1. 1342 00:56:07,660 --> 00:56:11,420 Takže už vieme, že to je náš prvý prvok. 1343 00:56:11,420 --> 00:56:13,240 Nepotrebujeme porovnať ju k sebe. 1344 00:56:13,240 --> 00:56:16,970 Takže začneme porovnajte ju s ďalšie ten, ktorý je dôvod, prečo je aj a 1 až n 1345 00:56:16,970 --> 00:56:20,110 mínus 1, čo je koniec poľa tam. 1346 00:56:20,110 --> 00:56:25,090 A my, ak pole v uvedenom j je menšie ako pole min, 1347 00:56:25,090 --> 00:56:29,200 potom preradiť, kde Naša minimálna indexy je. 1348 00:56:29,200 --> 00:56:37,470 >> A v prípade, min nie je rovné I, ako je tam, kam sme sa vrátili sem. 1349 00:56:37,470 --> 00:56:38,950 1350 00:56:38,950 --> 00:56:41,790 Tak, ako keď sme prvýkrát robili tento. 1351 00:56:41,790 --> 00:56:49,310 V tomto prípade by bol štart na nula, bolo by to skončí tým, že dvaja. 1352 00:56:49,310 --> 00:56:53,010 Takže by min nerovná aj na konci. 1353 00:56:53,010 --> 00:56:55,720 To nám umožňuje vedieť, že musíme ich vymeniť. 1354 00:56:55,720 --> 00:56:57,420 1355 00:56:57,420 --> 00:57:00,470 Cítim sa ako konkrétny príklad pomôže oveľa viac než to. 1356 00:57:00,470 --> 00:57:04,970 Takže budem kódu to s vami práve teraz a myslím, že to bude lepšie. 1357 00:57:04,970 --> 00:57:07,380 1358 00:57:07,380 --> 00:57:11,350 >> Druhy majú tendenciu pracovať týmto spôsobom v tom je to často lepšie, len je vidieť. 1359 00:57:11,350 --> 00:57:12,780 1360 00:57:12,780 --> 00:57:17,280 Takže to, čo chceme urobiť, je najprv chcem najmenší 1361 00:57:17,280 --> 00:57:19,890 časť v jej polohe v poli. 1362 00:57:19,890 --> 00:57:21,280 Presne to, čo Jacob hovoril. 1363 00:57:21,280 --> 00:57:23,090 Musíte uložiť, že nejako. 1364 00:57:23,090 --> 00:57:25,900 Takže budeme začnite tu iterácie cez pole. 1365 00:57:25,900 --> 00:57:28,970 Budeme hovoriť, že je to naša Prvý z nich len začať. 1366 00:57:28,970 --> 00:57:38,308 Takže budeme mať int najmenších je rovná poľa v i. 1367 00:57:38,308 --> 00:57:40,500 1368 00:57:40,500 --> 00:57:45,050 >> Takže jedna vec je si všimnúť, každý keď sa to spustí slučka, 1369 00:57:45,050 --> 00:57:48,550 začíname o krok ďalej. 1370 00:57:48,550 --> 00:57:54,780 1371 00:57:54,780 --> 00:57:57,440 Keď začneme sa pozrieme na tento jeden. 1372 00:57:57,440 --> 00:58:00,840 Nabudúce budeme iterovat, začíname na tomto jednom 1373 00:58:00,840 --> 00:58:02,680 a priradenie je náš najmenší hodnota. 1374 00:58:02,680 --> 00:58:10,450 Takže je to veľmi podobné bubliny druhu kde vieme, že po jednom priechodu, 1375 00:58:10,450 --> 00:58:11,700 Tento posledný prvok je triedený. 1376 00:58:11,700 --> 00:58:12,810 1377 00:58:12,810 --> 00:58:15,120 Pri výbere druhu, že je to práve naopak. 1378 00:58:15,120 --> 00:58:18,950 >> Pri každom priechode, vieme, že Prvý z nich je usporiadaný. 1379 00:58:18,950 --> 00:58:21,360 Po druhom prechode, druhá bude triediť. 1380 00:58:21,360 --> 00:58:26,470 A ako si videl s príkladmi prezentácií, naše radené časť jednoducho stále rastie. 1381 00:58:26,470 --> 00:58:34,020 Takže nastavením naši najmenší z na pole i všetko to robí 1382 00:58:34,020 --> 00:58:37,340 sa obmedzí, čo sa pozeráme na to, ako 1383 00:58:37,340 --> 00:58:40,164 minimalizovať počet porovnávanie robíme. 1384 00:58:40,164 --> 00:58:41,770 Znamená to, že zmysel pre každého? 1385 00:58:41,770 --> 00:58:42,920 1386 00:58:42,920 --> 00:58:46,380 Páči sa mi treba prejsť, že opäť pomalšie alebo inými slovami? 1387 00:58:46,380 --> 00:58:47,180 Som rád, že. 1388 00:58:47,180 --> 00:58:48,095 1389 00:58:48,095 --> 00:58:48,595 OK. 1390 00:58:48,595 --> 00:58:50,060 1391 00:58:50,060 --> 00:58:55,540 >> Takže sme skladovanie hodnota v tomto bode, 1392 00:58:55,540 --> 00:58:57,840 ale tiež chceme uložiť index. 1393 00:58:57,840 --> 00:59:01,010 Takže budeme ukladať pozície najmenší 1394 00:59:01,010 --> 00:59:02,770 jeden, ktorý sa len bude aj. 1395 00:59:02,770 --> 00:59:04,357 1396 00:59:04,357 --> 00:59:05,440 Takže teraz Jacob je spokojný. 1397 00:59:05,440 --> 00:59:06,870 Máme veci uložené. 1398 00:59:06,870 --> 00:59:08,240 1399 00:59:08,240 --> 00:59:11,870 A teraz sa musíme pozerať cez netriedeného časť poľa. 1400 00:59:11,870 --> 00:59:18,170 Takže v tomto prípade, že tento Bude nám netriedený. 1401 00:59:18,170 --> 00:59:20,980 1402 00:59:20,980 --> 00:59:22,462 To je aj. 1403 00:59:22,462 --> 00:59:25,430 1404 00:59:25,430 --> 00:59:26,210 OK. 1405 00:59:26,210 --> 00:59:30,040 >> Takže to, čo budeme robiť bude pre slučke. 1406 00:59:30,040 --> 00:59:32,066 Kedykoľvek budete potrebovať iterovat cez pole, 1407 00:59:32,066 --> 00:59:33,440 vaša myseľ môže ísť do pre slučke. 1408 00:59:33,440 --> 00:59:34,760 1409 00:59:34,760 --> 00:59:38,090 Tak pre niektoré int k equals--, čo si myslíme, že 1410 00:59:38,090 --> 00:59:39,700 k sa bude rovnať začať? 1411 00:59:39,700 --> 00:59:41,580 1412 00:59:41,580 --> 00:59:44,766 To je to, čo sme si stanovili ako našich najmenších hodnotu a chceme porovnávať. 1413 00:59:44,766 --> 00:59:47,090 Čo chceme porovnávať to? 1414 00:59:47,090 --> 00:59:48,730 Je to bude to budúci, je to tak? 1415 00:59:48,730 --> 00:59:53,200 Tak sme sa chceme k nutné inicializovať aby aj plus 1 na štart. 1416 00:59:53,200 --> 00:59:55,350 1417 00:59:55,350 --> 01:00:02,800 >> A my chceme k v tomto prípade už veľkosť uložené tu, 1418 01:00:02,800 --> 01:00:03,930 takže stačí použiť veľkosť. 1419 01:00:03,930 --> 01:00:06,240 Veľkosť je veľkosť poľa. 1420 01:00:06,240 --> 01:00:09,620 A my jednoducho chceme, aby aktualizovať K niektorým zakaždým. 1421 01:00:09,620 --> 01:00:17,410 1422 01:00:17,410 --> 01:00:17,910 V pohode. 1423 01:00:17,910 --> 01:00:19,650 1424 01:00:19,650 --> 01:00:23,430 Takže teraz musíme nájsť najmenší prvok tu. 1425 01:00:23,430 --> 01:00:24,470 1426 01:00:24,470 --> 01:00:31,380 Takže ak budeme iterovat sme chcem povedať, ak je pole na k 1427 01:00:31,380 --> 01:00:37,080 je nižšia než naše najmenšie value-- to je miesto, kde sme vlastne 1428 01:00:37,080 --> 01:00:42,950 sledovanie toho, čo je najmenší here-- 1429 01:00:42,950 --> 01:00:47,740 potom chceme priradiť čo naša najmenšia hodnota je. 1430 01:00:47,740 --> 01:00:50,645 >> To znamená, že, oh, my sme iterácie tu. 1431 01:00:50,645 --> 01:00:51,699 1432 01:00:51,699 --> 01:00:53,740 Či už je hodnota tu nie je naša najmenšia vec. 1433 01:00:53,740 --> 01:00:54,448 Nechceme ho. 1434 01:00:54,448 --> 01:00:56,100 Chceme ju priradiť. 1435 01:00:56,100 --> 01:01:02,050 Takže ak sme ho prerozdeľujú, čo robiť si myslíte, že by mohlo byť v tomto kóde tu? 1436 01:01:02,050 --> 01:01:04,160 Chceme priradiť Najmenší a pozície. 1437 01:01:04,160 --> 01:01:05,740 1438 01:01:05,740 --> 01:01:07,010 Takže to, čo je najmenší teraz? 1439 01:01:07,010 --> 01:01:08,422 1440 01:01:08,422 --> 01:01:09,130 STUDENT: Array k. 1441 01:01:09,130 --> 01:01:09,963 Inštruktor: Array k. 1442 01:01:09,963 --> 01:01:13,480 1443 01:01:13,480 --> 01:01:15,956 A aká je pozícia teraz? 1444 01:01:15,956 --> 01:01:20,940 1445 01:01:20,940 --> 01:01:23,000 Čo je na indexy naša najmenšia hodnota? 1446 01:01:23,000 --> 01:01:24,030 1447 01:01:24,030 --> 01:01:24,530 Je to len k. 1448 01:01:24,530 --> 01:01:25,690 1449 01:01:25,690 --> 01:01:27,790 Takže pole k, k, sa zhodujú so. 1450 01:01:27,790 --> 01:01:31,670 1451 01:01:31,670 --> 01:01:33,120 Takže sme chceli priradiť to. 1452 01:01:33,120 --> 01:01:34,390 1453 01:01:34,390 --> 01:01:39,950 A potom sme našli našich najmenších, takže na konci tohto cyklu for 1454 01:01:39,950 --> 01:01:45,100 tu sme našli to, čo naše najmenšie je hodnota, takže sme jednoducho vymeniť ju. 1455 01:01:45,100 --> 01:01:47,100 1456 01:01:47,100 --> 01:01:50,816 V tomto prípade, rovnako ako že naše Najmenšia hodnota je tu. 1457 01:01:50,816 --> 01:01:51,940 Toto je náš najmenší hodnota. 1458 01:01:51,940 --> 01:01:57,690 >> Chceme len, aby ho vymeniť tú, ktorá je čo, že funkcia odkladacia na dne 1459 01:01:57,690 --> 01:02:01,270 áno, ktoré sme práve spísal spolu pred pár minútami. 1460 01:02:01,270 --> 01:02:02,775 Tak by to malo vyzerať povedome. 1461 01:02:02,775 --> 01:02:04,320 1462 01:02:04,320 --> 01:02:08,030 A potom to bude len opakovať až kým nedosiahne celú cestu 1463 01:02:08,030 --> 01:02:13,100 až do konca, čo znamená, že majú nulovú prvky, ktoré nie sú roztriedené 1464 01:02:13,100 --> 01:02:14,800 a všetko, čo bolo radené. 1465 01:02:14,800 --> 01:02:16,216 1466 01:02:16,216 --> 01:02:16,715 Zmysel? 1467 01:02:16,715 --> 01:02:18,010 1468 01:02:18,010 --> 01:02:19,280 Trochu konkrétnejšie? 1469 01:02:19,280 --> 01:02:19,990 Kód pomôcť? 1470 01:02:19,990 --> 01:02:21,720 1471 01:02:21,720 --> 01:02:26,410 >> STUDENT: Pre veľkosti, nikdy Naozaj ho definovať alebo zmeniť, 1472 01:02:26,410 --> 01:02:27,340 ako to vieš? 1473 01:02:27,340 --> 01:02:32,380 >> Inštruktor: Takže jedna vec je Všimnite si, tu je veľkosť int. 1474 01:02:32,380 --> 01:02:35,680 Takže hovoríme v tomto sort-- druhu je funkcia v tomto case-- je to 1475 01:02:35,680 --> 01:02:40,770 výber triediť, je odovzdávaný v s funkciou. 1476 01:02:40,770 --> 01:02:43,460 Takže ak to nebol prijatý vo by ste niečo 1477 01:02:43,460 --> 01:02:47,840 ako s dĺžkou poľa alebo by ste iterovat 1478 01:02:47,840 --> 01:02:49,390 nájsť dĺžku. 1479 01:02:49,390 --> 01:02:52,680 Ale pretože je odovzdávaný v, môžeme len použiť. 1480 01:02:52,680 --> 01:02:55,720 Ste len predpokladať, že užívateľ vám dal platnú veľkosť, ktorá 1481 01:02:55,720 --> 01:02:57,698 vlastne predstavuje Veľkosť vášho poľa. 1482 01:02:57,698 --> 01:02:59,461 1483 01:02:59,461 --> 01:02:59,960 V pohode? 1484 01:02:59,960 --> 01:03:01,610 1485 01:03:01,610 --> 01:03:05,870 >> Ak vy máte nejaké problémy s týmito alebo chcete viac praxe kódovanie druhov 1486 01:03:05,870 --> 01:03:08,050 na vlastnú päsť, mali by ste prejsť na study.cs50. 1487 01:03:08,050 --> 01:03:11,560 1488 01:03:11,560 --> 01:03:12,670 Je to nástroj. 1489 01:03:12,670 --> 01:03:15,040 Majú checker, ktorý môžete skutočne písať. 1490 01:03:15,040 --> 01:03:16,180 Robia pseudokódu. 1491 01:03:16,180 --> 01:03:19,310 Majú viac videí a snímok vrátane tých, ktoré používam tu. 1492 01:03:19,310 --> 01:03:23,150 Takže ak ste stále pocit, trochu rozmazaný, skúste to von. 1493 01:03:23,150 --> 01:03:25,670 Ako vždy, poď so mnou hovoriť, taky. 1494 01:03:25,670 --> 01:03:26,320 Otázka? 1495 01:03:26,320 --> 01:03:28,611 >> STUDENT: Chceš povedať, že Veľkosť je definované vyššie? 1496 01:03:28,611 --> 01:03:29,234 1497 01:03:29,234 --> 01:03:29,900 Inštruktor: Áno. 1498 01:03:29,900 --> 01:03:35,570 Veľkosť je definované vyššie up tu v deklarácii funkcie. 1499 01:03:35,570 --> 01:03:39,060 Takže možno predpokladať, že to bolo odovzdané do užívateľom, a pre jednoduchosť, 1500 01:03:39,060 --> 01:03:41,896 budeme predpokladať, že Užívateľ nám správnu veľkosť. 1501 01:03:41,896 --> 01:03:43,240 V pohode. 1502 01:03:43,240 --> 01:03:44,390 Tak to je výber sort. 1503 01:03:44,390 --> 01:03:45,590 1504 01:03:45,590 --> 01:03:47,640 Chlapi, viem, že učíme dnes veľa. 1505 01:03:47,640 --> 01:03:49,710 Je to hustý dát pre sekciu. 1506 01:03:49,710 --> 01:03:51,880 1507 01:03:51,880 --> 01:03:57,340 Takže s tým budeme ísť na vloženie druhu. 1508 01:03:57,340 --> 01:04:01,550 1509 01:04:01,550 --> 01:04:02,510 >> OK. 1510 01:04:02,510 --> 01:04:06,100 Takže ako to, čo musíme urobiť naše runtime analýza tu. 1511 01:04:06,100 --> 01:04:10,190 Takže v najlepšom prípade, udelená, pretože som vám ukázal 1512 01:04:10,190 --> 01:04:11,960 tabuľka Už som druh dal preč. 1513 01:04:11,960 --> 01:04:15,430 Ale najlepšom prípade runtime, čo si myslíme, že? 1514 01:04:15,430 --> 01:04:17,310 1515 01:04:17,310 --> 01:04:18,130 Všetko radené. 1516 01:04:18,130 --> 01:04:21,040 1517 01:04:21,040 --> 01:04:22,070 N druhú. 1518 01:04:22,070 --> 01:04:24,780 Každý, kto má vysvetlenie prečo si myslíte, že? 1519 01:04:24,780 --> 01:04:29,060 1520 01:04:29,060 --> 01:04:30,519 >> STUDENT: Ste nákupný through-- 1521 01:04:30,519 --> 01:04:31,268 Inštruktor: Správne. 1522 01:04:31,268 --> 01:04:32,540 Ste nákupný prejsť. 1523 01:04:32,540 --> 01:04:35,630 V každej iterácii, aj keď sme dekrementování to po druhom, 1524 01:04:35,630 --> 01:04:38,950 ste stále prehľadávať všetko nájsť najmenší jeden. 1525 01:04:38,950 --> 01:04:42,390 Takže aj keď vaše najmenšie hodnota je tu na začiatku, 1526 01:04:42,390 --> 01:04:44,710 ste stále porovnávanie proti všiam 1527 01:04:44,710 --> 01:04:46,550 aby sa ubezpečil, že je to najmenšie vec. 1528 01:04:46,550 --> 01:04:49,820 Takže skončíte prechádzajúcej približne n na druhú krát. 1529 01:04:49,820 --> 01:04:51,090 1530 01:04:51,090 --> 01:04:51,590 Dobrá. 1531 01:04:51,590 --> 01:04:52,785 A čo je najhoršie? 1532 01:04:52,785 --> 01:04:54,350 1533 01:04:54,350 --> 01:04:57,980 Tiež n na druhú, pretože budete bude robiť, že rovnaký postup. 1534 01:04:57,980 --> 01:05:01,670 Takže v tomto prípade výber druh má niečo 1535 01:05:01,670 --> 01:05:04,010 že sme tiež volať očakávané runtime. 1536 01:05:04,010 --> 01:05:07,400 Takže ostatní, sme len viem, horná a dolná hranica. 1537 01:05:07,400 --> 01:05:11,180 V závislosti na tom, ako blázon naše Zoznam je netriedený alebo ako to je, 1538 01:05:11,180 --> 01:05:15,350 sa líši medzi n alebo n na druhú. 1539 01:05:15,350 --> 01:05:16,550 Nevieme. 1540 01:05:16,550 --> 01:05:22,820 >> Ale pretože výber druh má rovnaké najhorší a najlepší prípad, že nám hovorí, že 1541 01:05:22,820 --> 01:05:25,880 bez ohľadu na to, aký typ vstupu sme majú, či už je to úplne 1542 01:05:25,880 --> 01:05:29,130 radené alebo úplne reverznej radené, je to 1543 01:05:29,130 --> 01:05:30,740 bude trvať rovnakú dobu. 1544 01:05:30,740 --> 01:05:33,760 Takže v tomto prípade, ak vás pamätať z nášho stola, 1545 01:05:33,760 --> 01:05:38,610 v skutočnosti mala hodnotu, ktorá Tieto dva druhy nemajú, 1546 01:05:38,610 --> 01:05:40,390 čo je predpokladaná doba zálohovania. 1547 01:05:40,390 --> 01:05:43,350 Takže vieme, že vždy, keď narazíme výber druhu, 1548 01:05:43,350 --> 01:05:45,380 je zaručené, aby spustiť n na druhú dobu. 1549 01:05:45,380 --> 01:05:46,630 Nie je tam žiadna variabilita. 1550 01:05:46,630 --> 01:05:47,630 Je to od nich očakáva. 1551 01:05:47,630 --> 01:05:48,820 1552 01:05:48,820 --> 01:05:52,140 A opäť, ak sa chcete dozvedieť, viac, vziať CS 124 na jar. 1553 01:05:52,140 --> 01:05:55,370 1554 01:05:55,370 --> 01:05:56,712 Dobrá. 1555 01:05:56,712 --> 01:05:57,545 Videli sme toto. 1556 01:05:57,545 --> 01:05:58,530 1557 01:05:58,530 --> 01:05:59,030 V pohode. 1558 01:05:59,030 --> 01:06:00,930 Takže vloženie sort. 1559 01:06:00,930 --> 01:06:03,330 A ja asi bude na požiar cez to. 1560 01:06:03,330 --> 01:06:05,440 Nebudem mať vy to kód. 1561 01:06:05,440 --> 01:06:06,580 Budeme sa len prechádzať cez to. 1562 01:06:06,580 --> 01:06:10,500 Takže vloženie druh je druh o podobný výbere druhu 1563 01:06:10,500 --> 01:06:14,460 v tom, že máme obaja netriedené a zoradená časť poľa. 1564 01:06:14,460 --> 01:06:20,260 >> Ale to, čo je, je, že ako sme sa prejsť jeden po druhom, 1565 01:06:20,260 --> 01:06:24,210 sme jednoducho vziať bez ohľadu na počet je ďalší v našom netriedený, 1566 01:06:24,210 --> 01:06:28,507 a správne triediť do nášho triedeného poľa. 1567 01:06:28,507 --> 01:06:30,090 Bude to väčší zmysel na príklade. 1568 01:06:30,090 --> 01:06:31,140 1569 01:06:31,140 --> 01:06:35,430 Takže všetko, čo začína ako netriedený, Rovnako ako pri výbere druhu. 1570 01:06:35,430 --> 01:06:38,740 A budeme triediť na túto vzostupne, ako sme boli. 1571 01:06:38,740 --> 01:06:40,360 1572 01:06:40,360 --> 01:06:43,340 Takže na našom prvom prechode Vezmeme prvú hodnotu 1573 01:06:43,340 --> 01:06:46,700 a hovoríme, OK, ste teraz v zozname sami. 1574 01:06:46,700 --> 01:06:49,150 >> Pretože ste v zozname sami, ste radené. 1575 01:06:49,150 --> 01:06:52,460 Gratulujeme k bytiu prvý prvok v tomto poli. 1576 01:06:52,460 --> 01:06:54,800 Ste už je zoradený všetko na vlastnú päsť. 1577 01:06:54,800 --> 01:06:58,900 Takže teraz sme radené a netriedené poľa. 1578 01:06:58,900 --> 01:07:01,760 Takže teraz sme sa prvýkrát. 1579 01:07:01,760 --> 01:07:05,600 Čo sa stane medzi tu a tu je to, že hovoríme, 1580 01:07:05,600 --> 01:07:08,890 OK, ideme sa pozrieť na Prvá hodnota našej netriedený pole 1581 01:07:08,890 --> 01:07:13,270 a budeme vstup je vo svojom správne miesto v triedenom poli. 1582 01:07:13,270 --> 01:07:21,460 >> Takže to, čo robíme, je berieme 5 a hovoríme, OK, 5 je vyššia ako 3, 1583 01:07:21,460 --> 01:07:24,630 takže stačí vložiť ju priamo na pravej strane, že. 1584 01:07:24,630 --> 01:07:25,130 Sme dobre. 1585 01:07:25,130 --> 01:07:26,200 1586 01:07:26,200 --> 01:07:28,420 Takže ideme na naše ďalšie. 1587 01:07:28,420 --> 01:07:29,720 A vezmeme 2. 1588 01:07:29,720 --> 01:07:34,330 My hovoríme, OK, 2 menšie ako 3, takže vieme, že to 1589 01:07:34,330 --> 01:07:36,220 musí byť v Predná časť nášho zoznamu teraz. 1590 01:07:36,220 --> 01:07:41,800 Takže to, čo robíme, je, že sme tlačiť 3 a 5 sa a prejdeme 2 do toho prvého slotu. 1591 01:07:41,800 --> 01:07:42,990 1592 01:07:42,990 --> 01:07:45,870 Takže sme jednoducho vložením do správne miesto, to by malo byť. 1593 01:07:45,870 --> 01:07:46,960 1594 01:07:46,960 --> 01:07:49,470 >> Potom sa pozrieme na naše budúci, a hovoríme 6. 1595 01:07:49,470 --> 01:07:53,620 OK, 6 je väčšia než všetko v našom triedenom poli, 1596 01:07:53,620 --> 01:07:56,000 tak sme jednoducho označiť ju až do konca. 1597 01:07:56,000 --> 01:07:56,960 A potom sa pozrieme na 4. 1598 01:07:56,960 --> 01:07:58,130 1599 01:07:58,130 --> 01:08:03,020 4 je menšie ako 6, je to menej ako 5, ale je to menej ako 3. 1600 01:08:03,020 --> 01:08:06,270 Tak sme jednoducho vložte ju priamo do uprostred medzi 3 a 5. 1601 01:08:06,270 --> 01:08:07,380 1602 01:08:07,380 --> 01:08:10,530 Tak, aby sa to trochu trochu konkrétnejší, 1603 01:08:10,530 --> 01:08:12,280 Tu je druh predstava o tom, čo sa stalo. 1604 01:08:12,280 --> 01:08:16,430 Takže pre každý prvok netriedeného, ​​sme určiť, kde v triedenom časti 1605 01:08:16,430 --> 01:08:17,090 to je. 1606 01:08:17,090 --> 01:08:20,680 >> Tak, aby sa nezabúdalo na triedené a netriedené, 1607 01:08:20,680 --> 01:08:26,080 musíme prejsť skrz a obr , Kde sa zmestí do triedeného poľa. 1608 01:08:26,080 --> 01:08:31,460 A my ho vložiť posunutím prvky vpravo dole. 1609 01:08:31,460 --> 01:08:34,910 A potom sme jednoducho udržať iterácie, až kým 1610 01:08:34,910 --> 01:08:39,270 majú úplne zoradený zoznam kde netriedené je teraz nulová 1611 01:08:39,270 --> 01:08:41,720 a triedený zaberá celistvosť nášho zoznamu. 1612 01:08:41,720 --> 01:08:43,146 1613 01:08:43,146 --> 01:08:45,854 Takže, ešte raz, aby sa veci ešte konkrétnejšie, máme pseudokódu. 1614 01:08:45,854 --> 01:08:47,979 1615 01:08:47,979 --> 01:08:52,410 >> Takže v podstate pre i je presne 0 do n mínus 1, 1616 01:08:52,410 --> 01:08:54,790 to je len dĺžka nášho poľa. 1617 01:08:54,790 --> 01:09:00,979 Máme nejaký prvok, ktorý sa rovná Prvé pole alebo prvý indexy. 1618 01:09:00,979 --> 01:09:03,200 Nastavili sme j, ktorá sa rovná. 1619 01:09:03,200 --> 01:09:04,649 1620 01:09:04,649 --> 01:09:09,210 Takže zatiaľ čo j je väčšia než nula a polia, j mínus 1 1621 01:09:09,210 --> 01:09:11,660 je väčšia než prvok, takže všetko, čo robí 1622 01:09:11,660 --> 01:09:17,479 je zabezpečiť, aby Váš j Vás naozaj zastupuje 1623 01:09:17,479 --> 01:09:20,010 netriedeného časť poľa. 1624 01:09:20,010 --> 01:09:30,745 >> Takže zatiaľ čo tam je ešte veci triediť a j mínus jedna je-- čo 1625 01:09:30,745 --> 01:09:31,840 je jej súčasťou? 1626 01:09:31,840 --> 01:09:34,760 J tu nebola definovaná. 1627 01:09:34,760 --> 01:09:35,677 Je to trochu nepríjemné. 1628 01:09:35,677 --> 01:09:36,176 OK. 1629 01:09:36,176 --> 01:09:36,689 Tak ako tak. 1630 01:09:36,689 --> 01:09:39,899 Tak j mínus 1, máte kontrolu prvok pred ním. 1631 01:09:39,899 --> 01:09:46,460 Hovoríte, že, OK, je element predtým, než tam, kde som am-- poďme 1632 01:09:46,460 --> 01:09:47,540 skutočne čerpať na to. 1633 01:09:47,540 --> 01:09:52,580 1634 01:09:52,580 --> 01:09:56,830 Takže povedzme, že je to ako na našom druhom prechode. 1635 01:09:56,830 --> 01:09:59,525 Takže aj sa bude rovnať 1, ktorý je tu. 1636 01:09:59,525 --> 01:10:03,310 1637 01:10:03,310 --> 01:10:06,025 >> Takže aj bude rovný 1. 1638 01:10:06,025 --> 01:10:09,510 1639 01:10:09,510 --> 01:10:13,702 To by bolo 2, 4, 5, 6, 7. 1640 01:10:13,702 --> 01:10:16,060 1641 01:10:16,060 --> 01:10:16,750 Dobrá. 1642 01:10:16,750 --> 01:10:20,945 Takže naše prvkom v tomto prípade bude rovná 4. 1643 01:10:20,945 --> 01:10:22,110 1644 01:10:22,110 --> 01:10:24,946 A máme nejaké j, ktorý je bude rovný 1. 1645 01:10:24,946 --> 01:10:29,770 1646 01:10:29,770 --> 01:10:30,971 Oh, j je dekrementování. 1647 01:10:30,971 --> 01:10:31,720 To je to, čo to je. 1648 01:10:31,720 --> 01:10:35,680 Tak j je rovný aj tak, čo to je Hovorí sa, že, ako sme vpred, 1649 01:10:35,680 --> 01:10:37,530 sme len uistiť že nie sme cez 1650 01:10:37,530 --> 01:10:43,520 indexovanie týmto spôsobom, keď sa snažíme vložiť veci do nášho zoznamu zoradené. 1651 01:10:43,520 --> 01:10:49,850 >> Takže keď j je rovný 1, v tomto prípade, a array j mínus one-- tak array j mínus 1 1652 01:10:49,850 --> 01:10:54,610 je 2 v tomto case--, ak je to väčšie ako prvok, 1653 01:10:54,610 --> 01:10:57,700 potom to všetko robí sa presúva veci dolu. 1654 01:10:57,700 --> 01:11:04,790 Takže v tomto prípade, pole j mínus jedna by poľa nulová, čo je 2. 1655 01:11:04,790 --> 01:11:08,430 2 nie je väčší ako 4, tak to nevykoná. 1656 01:11:08,430 --> 01:11:11,460 Takže posun nepohybuje nadol. 1657 01:11:11,460 --> 01:11:18,790 Čo to však je tu len pohybom zoradené polia dole. 1658 01:11:18,790 --> 01:11:22,340 1659 01:11:22,340 --> 01:11:26,400 V tomto prípade, v skutočnosti, sme by do-- urobme túto tri. 1660 01:11:26,400 --> 01:11:28,080 1661 01:11:28,080 --> 01:11:31,970 Takže ak sme sa prejsť s tento príklad, my sme teraz tu. 1662 01:11:31,970 --> 01:11:32,740 To je zoradený. 1663 01:11:32,740 --> 01:11:34,492 1664 01:11:34,492 --> 01:11:35,200 To je netriedený. 1665 01:11:35,200 --> 01:11:39,090 1666 01:11:39,090 --> 01:11:39,860 V pohode? 1667 01:11:39,860 --> 01:11:46,620 Takže aj je rovná 2, takže náš prvok je rovné 3. 1668 01:11:46,620 --> 01:11:47,920 1669 01:11:47,920 --> 01:11:52,270 A naša j je rovný 2. 1670 01:11:52,270 --> 01:12:00,620 Tak sme sa pozrieť a my hovoria, OK, je pole j mínus jedna 1671 01:12:00,620 --> 01:12:03,470 väčšie ako prvok že sa pozeráme? 1672 01:12:03,470 --> 01:12:05,540 A odpoveď je áno, je to tak? 1673 01:12:05,540 --> 01:12:11,275 4 je väčší ako 3, a j je 2, takže tento kód spustí. 1674 01:12:11,275 --> 01:12:12,510 1675 01:12:12,510 --> 01:12:18,550 >> Takže teraz to, čo robíme poľa na 2, tak tu sme sa ich vymeniť. 1676 01:12:18,550 --> 01:12:25,620 Tak sme sa len povedať, OK, polia na 2 sa teraz bude 3. 1677 01:12:25,620 --> 01:12:28,130 1678 01:12:28,130 --> 01:12:32,340 A j bude rovnať j mínus 1, čo je 1. 1679 01:12:32,340 --> 01:12:34,590 1680 01:12:34,590 --> 01:12:37,200 To je hrozné, ale vy dostanete nápad. 1681 01:12:37,200 --> 01:12:38,360 J je teraz rovný 1. 1682 01:12:38,360 --> 01:12:44,360 A pole j sa len bude rovná našej prvku, ktorý bol 4. 1683 01:12:44,360 --> 01:12:45,950 1684 01:12:45,950 --> 01:12:48,570 Aj vymazať niečo, čo som nemal majú alebo miswrote niečo, 1685 01:12:48,570 --> 01:12:49,910 ale vy dostanete nápad. 1686 01:12:49,910 --> 01:12:50,640 >> To sa pohybujú n. 1687 01:12:50,640 --> 01:12:51,920 1688 01:12:51,920 --> 01:12:57,960 A potom, ak to tak bolo, bolo by to slučka znova, a to by som povedal, OK, j je 1 teraz. 1689 01:12:57,960 --> 01:13:00,665 A pole j mínus 1 je teraz 2. 1690 01:13:00,665 --> 01:13:01,750 1691 01:13:01,750 --> 01:13:03,760 Je 2 menšie než naše prvok? 1692 01:13:03,760 --> 01:13:04,540 Nie? 1693 01:13:04,540 --> 01:13:07,970 To znamená, že máme vkladá tento prvok 1694 01:13:07,970 --> 01:13:10,110 v správnom mieste v našom triedeného poli. 1695 01:13:10,110 --> 01:13:14,400 Potom sa môžeme vziať a hovoríme, OK, naša zoradené poľa je tu. 1696 01:13:14,400 --> 01:13:19,940 A to by sa toto číslo 6 a musí byť ako, OK, 6 menšie ako toto číslo? 1697 01:13:19,940 --> 01:13:20,480 Nie? 1698 01:13:20,480 --> 01:13:21,080 V pohode. 1699 01:13:21,080 --> 01:13:22,680 Sme v poriadku. 1700 01:13:22,680 --> 01:13:23,530 >> Urob to znova. 1701 01:13:23,530 --> 01:13:24,740 Hovoríme 7. 1702 01:13:24,740 --> 01:13:29,010 Je menšia ako 7 do konca našej triedeného poľa? 1703 01:13:29,010 --> 01:13:29,520 Nie. 1704 01:13:29,520 --> 01:13:30,430 Takže sme v pohode. 1705 01:13:30,430 --> 01:13:32,760 Takže by to byť triedené. 1706 01:13:32,760 --> 01:13:38,610 V podstate to všetko robí Je to hovorí vziať 1707 01:13:38,610 --> 01:13:42,060 Prvý prvok Váš netriedené polia, 1708 01:13:42,060 --> 01:13:46,010 zistiť, kde to ide v triedenom poli. 1709 01:13:46,010 --> 01:13:48,780 A to len stará swapov k tomu, že. 1710 01:13:48,780 --> 01:13:51,300 Vy ste v podstate len vymení kým je to na správnom mieste. 1711 01:13:51,300 --> 01:13:53,600 1712 01:13:53,600 --> 01:13:56,990 Vizuálnej image je to, že ste pohybujúce sa všetko sa tým, že. 1713 01:13:56,990 --> 01:13:59,420 >> Takže je to ako polovica bublina trochu v štýle. 1714 01:13:59,420 --> 01:14:02,280 1715 01:14:02,280 --> 01:14:03,420 Pozrite sa na štúdii 50. 1716 01:14:03,420 --> 01:14:06,000 Vrelo odporúčam sa snaží kódovať na vlastnú päsť. 1717 01:14:06,000 --> 01:14:07,220 1718 01:14:07,220 --> 01:14:12,450 Ak máte nejaké otázky, alebo ak chcete pozri ukážkový kód pre vloženie druhu, 1719 01:14:12,450 --> 01:14:13,750 dajte mi prosím vedieť. 1720 01:14:13,750 --> 01:14:14,500 Vždy som sa okolo seba. 1721 01:14:14,500 --> 01:14:16,600 1722 01:14:16,600 --> 01:14:20,200 Takže v najhoršom prípade runtime a najlepšom prípade runtime. 1723 01:14:20,200 --> 01:14:30,700 Ako ste chlap videl z tabuľky už som vám ukázal, že to tak n na druhú a n. 1724 01:14:30,700 --> 01:14:35,590 >> Tak láskavý a šiel preč z toho, čo sme sa rozprávali o s našimi predchádzajúcimi druhmi, najhoršie 1725 01:14:35,590 --> 01:14:38,760 prípad runtime je, že ak je to úplne netriedeného 1726 01:14:38,760 --> 01:14:42,530 musíme porovnať všetky tieto n-krát. 1727 01:14:42,530 --> 01:14:47,020 Robíme veľa porovnanie pretože ak je to v opačnom poradí, 1728 01:14:47,020 --> 01:14:50,360 budeme hovoriť, OK, to je rovnaký, to je dobré, 1729 01:14:50,360 --> 01:14:54,650 a ten bude musieť byť v porovnaní proti prvej sa presunúť späť. 1730 01:14:54,650 --> 01:14:56,710 A ako sa dostaneme k koniec chvosta, máme 1731 01:14:56,710 --> 01:14:59,440 porovnávať, porovnávať a porovnať proti všetkému. 1732 01:14:59,440 --> 01:15:03,030 >> Takže to nakoniec bola n približne štvorcový. 1733 01:15:03,030 --> 01:15:09,510 Ak je to v poriadku, tak si hovoria, OK, 2, si dobrý. 1734 01:15:09,510 --> 01:15:11,330 3, ste v porovnaní s 2. 1735 01:15:11,330 --> 01:15:12,310 Si dobrá. 1736 01:15:12,310 --> 01:15:14,150 4, stačí porovnať na chvoste. 1737 01:15:14,150 --> 01:15:14,990 Si dobrá. 1738 01:15:14,990 --> 01:15:17,140 6, v porovnaní s chvostom, že si v poriadku. 1739 01:15:17,140 --> 01:15:20,870 Takže pre každé miesto, ak je už radené, robíš jednu porovnanie. 1740 01:15:20,870 --> 01:15:22,320 Takže je to len n. 1741 01:15:22,320 --> 01:15:26,840 A pretože máme najlepšiu prípadovú runtime n a najhoršom prípade behu n 1742 01:15:26,840 --> 01:15:28,680 štvorcový, nemáme očakávaný runtime. 1743 01:15:28,680 --> 01:15:31,290 1744 01:15:31,290 --> 01:15:34,020 >> Záleží len na chaos nášho zoznamu tu. 1745 01:15:34,020 --> 01:15:35,860 1746 01:15:35,860 --> 01:15:39,530 A opäť ďalší graf a ďalšie tabuľky. 1747 01:15:39,530 --> 01:15:41,170 Takže rozdiely medzi druhmi. 1748 01:15:41,170 --> 01:15:44,180 Ja som jednoducho ísť vánok cez, I pocit, že sme hovorili značne 1749 01:15:44,180 --> 01:15:46,570 o tom, ako všetky druhy o líšiť a prepojiť. 1750 01:15:46,570 --> 01:15:50,564 Takže Merge sort je posledná Aj sa niesol vám chalani s. 1751 01:15:50,564 --> 01:15:52,105 Máme dosť farebný obraz. 1752 01:15:52,105 --> 01:15:53,860 1753 01:15:53,860 --> 01:15:56,040 Takže zlúčiť druh je rekurzívny algoritmus. 1754 01:15:56,040 --> 01:15:59,910 Tak si chlapci vedia, čo rekurzívne funkcie? 1755 01:15:59,910 --> 01:16:01,550 1756 01:16:01,550 --> 01:16:03,320 >> Každý, kto chcel povedať? 1757 01:16:03,320 --> 01:16:04,739 Ak chcete to skúsiť? 1758 01:16:04,739 --> 01:16:07,280 Tak rekurzívne funkcie je len funkcia, ktorá volá sama seba. 1759 01:16:07,280 --> 01:16:08,570 1760 01:16:08,570 --> 01:16:11,590 Takže ak vy ste oboznámení s Fibonacci sekvencie, 1761 01:16:11,590 --> 01:16:15,670 ktorá je považovaná za rekurzívny, pretože budete mať predchádzajúce dva 1762 01:16:15,670 --> 01:16:17,530 a pridajte ich spolu dostať svoje ďalšie. 1763 01:16:17,530 --> 01:16:21,440 Tak rekurzívne, Vždy si myslím, rekurzia ako ako špirála 1764 01:16:21,440 --> 01:16:24,430 takže ste ako po špirále dole do neho. 1765 01:16:24,430 --> 01:16:27,150 Ale je to len funkcia ktorá volá sama seba. 1766 01:16:27,150 --> 01:16:32,660 >> A v skutočnosti, veľmi rýchlo som môže ukázať, ako to vyzerá. 1767 01:16:32,660 --> 01:16:34,260 1768 01:16:34,260 --> 01:16:41,840 Tak tu rekurzívny, ak sa pozrieme, je to rekurzívny spôsob, ako zhrnúť cez pole. 1769 01:16:41,840 --> 01:16:45,900 1770 01:16:45,900 --> 01:16:47,880 Takže všetko, čo robíme, je máme funkciu sum 1771 01:16:47,880 --> 01:16:52,210 čiastka, ktorá má veľkosť a polia. 1772 01:16:52,210 --> 01:16:55,210 A ak si všimnete, veľkosť úbytky podľa jedného zakaždým. 1773 01:16:55,210 --> 01:17:00,365 A to všetko robí, je, ak x je rovné zero-- takže ak veľkosť poľa 1774 01:17:00,365 --> 01:17:02,710 je rovný zero-- vráti nulu. 1775 01:17:02,710 --> 01:17:10,440 >> Inak to zhŕňa tento posledný prvok poľa, 1776 01:17:10,440 --> 01:17:14,790 a potom vezme súčet zvyšok poľa. 1777 01:17:14,790 --> 01:17:17,555 Takže je to len rozobrať to do menších a menších problémov. 1778 01:17:17,555 --> 01:17:18,990 1779 01:17:18,990 --> 01:17:21,890 Dlhý príbeh krátky, rekurzia, funkcia, ktorá volá sama seba. 1780 01:17:21,890 --> 01:17:25,740 Ak je to všetko, čo máš z toho, že to, čo rekurzívne funkcie. 1781 01:17:25,740 --> 01:17:29,870 Ak budete mať 51, dostanete veľmi, veľmi pohodlné s rekurzia. 1782 01:17:29,870 --> 01:17:31,110 1783 01:17:31,110 --> 01:17:32,370 Je to naozaj cool. 1784 01:17:32,370 --> 01:17:34,660 Dávalo to zmysel, ako 3 AM jednu noc. 1785 01:17:34,660 --> 01:17:37,900 A bol som rád, prečo Nikdy som použiť? 1786 01:17:37,900 --> 01:17:39,170 1787 01:17:39,170 --> 01:17:42,430 >> Takže pre zlúčenie druhu, v podstate čo to bude robiť, je, že je to 1788 01:17:42,430 --> 01:17:45,620 chystá vyraziť a zlomiť to nadol, kým je to len jednotlivé prvky. 1789 01:17:45,620 --> 01:17:47,570 Jednotlivé prvky sú ľahko vyriešiť. 1790 01:17:47,570 --> 01:17:48,070 Vidíme, že. 1791 01:17:48,070 --> 01:17:50,760 Ak máte jeden prvok, je to už považovaný za triedený. 1792 01:17:50,760 --> 01:17:53,800 A tak na vstupe n prvkov, ak n je menšie ako 2, 1793 01:17:53,800 --> 01:17:58,120 len vrátiť pretože to znamená to je buď 0 alebo 1, ako sme videli. 1794 01:17:58,120 --> 01:18:00,050 Tie sú považované za triedené prvky. 1795 01:18:00,050 --> 01:18:02,170 >> Inak rozbiť na polovicu. 1796 01:18:02,170 --> 01:18:06,336 Zoradiť prvú polovicu, triediť druhý polovice, a potom spojiť ich dohromady. 1797 01:18:06,336 --> 01:18:07,460 Prečo sa to volá merge sort. 1798 01:18:07,460 --> 01:18:08,700 1799 01:18:08,700 --> 01:18:12,155 Takže máme tu budeme triediť tieto. 1800 01:18:12,155 --> 01:18:13,410 1801 01:18:13,410 --> 01:18:17,210 Tak sme sa držať s nimi kým sa veľkosť poľa je 1. 1802 01:18:17,210 --> 01:18:20,790 Takže keď je to 1, práve sme sa vrátiť pretože sa jedná o zotriedené pole, 1803 01:18:20,790 --> 01:18:23,940 a to je triedeného poľa, a to je zotriedené pole, sme všetci radené. 1804 01:18:23,940 --> 01:18:25,390 1805 01:18:25,390 --> 01:18:29,420 Takže to, čo robíme, je, že sme začať zlúčenie dohromady. 1806 01:18:29,420 --> 01:18:31,820 >> Takže spôsob, ako môžete premýšľať o zlučovaní je 1807 01:18:31,820 --> 01:18:36,240 stačí odstrániť menšie Počet každej z čiastkových polí 1808 01:18:36,240 --> 01:18:38,330 a len pripojiť ho k objavili poľa. 1809 01:18:38,330 --> 01:18:44,290 Takže, keď sa pozriete tu, keď máme Tieto sady máme 4, 6, a 1. 1810 01:18:44,290 --> 01:18:47,280 Keď chceme zlúčiť tieto, Pozrieme sa na týchto prvých dvoch 1811 01:18:47,280 --> 01:18:50,730 a hovoríme, OK, 1 menšia, to ide dopredu. 1812 01:18:50,730 --> 01:18:54,330 4 a 6, nie je nič k porovnaniu to, stačí označiť ju až do konca. 1813 01:18:54,330 --> 01:18:58,020 >> Keď sme sa spojiť tieto dve, práve sme mať menšie jeden z týchto dvoch, 1814 01:18:58,020 --> 01:18:59,310 takže je to jedno. 1815 01:18:59,310 --> 01:19:01,690 A teraz sme sa menšia z týchto dvoch, SO 2. 1816 01:19:01,690 --> 01:19:03,330 Menšia z týchto dvoch, 3. 1817 01:19:03,330 --> 01:19:06,260 Menšia z týchto dvoch, 4, 5, 6. 1818 01:19:06,260 --> 01:19:08,630 Takže ste práve vyzliekol tie. 1819 01:19:08,630 --> 01:19:11,210 A pretože som boli radené skôr, 1820 01:19:11,210 --> 01:19:14,300 stačí jedno Porovnanie zakaždým, keď. 1821 01:19:14,300 --> 01:19:19,610 Takže viac kódu, proste reprezentácie. 1822 01:19:19,610 --> 01:19:24,410 Takže začnete v stredu a triediť vľavo a vpravo 1823 01:19:24,410 --> 01:19:26,180 a potom stačí spojiť tie. 1824 01:19:26,180 --> 01:19:30,080 >> A my nemáme kód pre zlúčenie tady. 1825 01:19:30,080 --> 01:19:34,110 Ale opäť, keď idete na štúdium 50, bude to tam. 1826 01:19:34,110 --> 01:19:36,860 V opačnom prípade príde so mnou hovoriť ak ste stále zmätená. 1827 01:19:36,860 --> 01:19:42,340 Tak super vec je, že najlepší prípad, v najhoršom prípade, a očakáva, že runtime 1828 01:19:42,340 --> 01:19:46,250 sú v protokole n, ktoré je oveľa lepší, než sme 1829 01:19:46,250 --> 01:19:48,000 vidieť po zvyšok našich druhov. 1830 01:19:48,000 --> 01:19:51,840 Videli sme n na druhú a to, čo sme vlastne 1831 01:19:51,840 --> 01:19:54,380 sem je n log n, čo je skvelé. 1832 01:19:54,380 --> 01:19:55,830 >> Pozrite sa, ako ďaleko lepšie to je. 1833 01:19:55,830 --> 01:19:56,780 Taká pekná krivka. 1834 01:19:56,780 --> 01:19:58,130 1835 01:19:58,130 --> 01:20:00,120 Tak oveľa efektívnejšie. 1836 01:20:00,120 --> 01:20:03,510 Ak ste niekedy možné, použite zlúčiť druh. 1837 01:20:03,510 --> 01:20:04,810 To vám ušetrí čas. 1838 01:20:04,810 --> 01:20:07,670 Potom znova, ako sme povedali, ak je ste v tejto nižšej regióne, 1839 01:20:07,670 --> 01:20:09,480 to neznamená, že to veľký rozdiel. 1840 01:20:09,480 --> 01:20:11,360 Získate až tisíce a tisíce vstupov, 1841 01:20:11,360 --> 01:20:13,318 budete určite chcieť efektívnejší algoritmus. 1842 01:20:13,318 --> 01:20:14,730 1843 01:20:14,730 --> 01:20:19,400 A opäť, naša milá tabuľka všetkých druhy, ktoré chlapci sa dnes dozvedel. 1844 01:20:19,400 --> 01:20:21,157 >> Takže viem, že to bol hustý deň. 1845 01:20:21,157 --> 01:20:23,490 To nemusí nutne ísť ktoré vám pomôžu s vašou pset. 1846 01:20:23,490 --> 01:20:28,250 Ale len chcem, aby disclaimer že oddiel nie je len o psets. 1847 01:20:28,250 --> 01:20:31,240 To všetko materiál je fér Hra pre vaše midterms. 1848 01:20:31,240 --> 01:20:35,430 A tiež ak si pokračovať s CS, Toto sú naozaj dôležité základy 1849 01:20:35,430 --> 01:20:37,870 ktoré budete potrebovať vedieť. 1850 01:20:37,870 --> 01:20:41,700 Takže pár dní bude trochu pset pomoc, 1851 01:20:41,700 --> 01:20:44,600 ale niekoľko týždňov bude oveľa skutočný obsah 1852 01:20:44,600 --> 01:20:46,600 že sa môže zdať Super užitočné pre vás práve teraz, 1853 01:20:46,600 --> 01:20:51,215 ale sľubujem, že ak budete pokračovať na bude veľmi, veľmi užitočné. 1854 01:20:51,215 --> 01:20:52,560 1855 01:20:52,560 --> 01:20:54,250 >> Tak to je pre sekciu. 1856 01:20:54,250 --> 01:20:55,250 Dole drôtu. 1857 01:20:55,250 --> 01:20:56,570 Urobil som to počas jednej minúty. 1858 01:20:56,570 --> 01:20:58,262 1859 01:20:58,262 --> 01:20:58,970 Ale tam idete. 1860 01:20:58,970 --> 01:21:01,240 A ja budem mať šišky alebo cukríky. 1861 01:21:01,240 --> 01:21:03,464 Je niekto alergický na niečo, mimochodom? 1862 01:21:03,464 --> 01:21:05,307 1863 01:21:05,307 --> 01:21:05,890 Vajec a mlieka. 1864 01:21:05,890 --> 01:21:08,120 Takže šišky sú nie? 1865 01:21:08,120 --> 01:21:09,400 1866 01:21:09,400 --> 01:21:10,160 OK. 1867 01:21:10,160 --> 01:21:10,770 Dobrá. 1868 01:21:10,770 --> 01:21:12,120 Čokoláda nie? 1869 01:21:12,120 --> 01:21:12,620 Starburst. 1870 01:21:12,620 --> 01:21:13,837 1871 01:21:13,837 --> 01:21:14,670 Starburst sú dobré. 1872 01:21:14,670 --> 01:21:15,170 OK. 1873 01:21:15,170 --> 01:21:17,045 Budeme mať Starburst budúci týždeň potom. 1874 01:21:17,045 --> 01:21:18,240 To je to, čo budem mať. 1875 01:21:18,240 --> 01:21:19,690 Vy máte skvelý týždeň. 1876 01:21:19,690 --> 01:21:20,460 Čítať vaše špec. 1877 01:21:20,460 --> 01:21:22,130 >> Dajte mi vedieť, ak máte akékoľvek otázky. 1878 01:21:22,130 --> 01:21:25,300 Pset dva stupne by mala byť k tebe do štvrtka. 1879 01:21:25,300 --> 01:21:28,320 Ak máte nejaké otázky o tom, ako som sa triedi niečo 1880 01:21:28,320 --> 01:21:32,250 alebo prečo som sa triedi niečo tak, ako som sa, prosím, napíšte mi, poď so mnou hovoriť. 1881 01:21:32,250 --> 01:21:34,210 Som trochu blázon to týždeň, ale sľubujem, 1882 01:21:34,210 --> 01:21:36,340 Budem ešte odpovedať do 24 hodín. 1883 01:21:36,340 --> 01:21:38,240 Takže majú veľký týždeň, všetci. 1884 01:21:38,240 --> 01:21:40,090 Veľa šťastia na vašej pset. 1885 01:21:40,090 --> 01:21:41,248