1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Predvaja glasba] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. Malan: To je CS50. 5 00:00:12,550 --> 00:00:14,612 In to je začetek tritedenskega. 6 00:00:14,612 --> 00:00:16,820 Torej imamo veliko razburljivo Stvari za kritje danes. 7 00:00:16,820 --> 00:00:20,160 Veliko priložnosti za prostovoljci na odru. 8 00:00:20,160 --> 00:00:22,780 In končno, danes je Ne gre kode sploh. 9 00:00:22,780 --> 00:00:24,820 Ampak to je o idejah, in gre algoritmov, 10 00:00:24,820 --> 00:00:28,420 in dejansko prinaša nazaj nekatere smo se naučili od ničelne teden, 11 00:00:28,420 --> 00:00:31,910 kjer odpoklic smo uvedli to pošastnost. 12 00:00:31,910 --> 00:00:33,880 In zadolževanje navdih od tistega, za začetek 13 00:00:33,880 --> 00:00:36,879 za reševanje vedno bolj prefinjene Težave z algoritmom. 14 00:00:36,879 --> 00:00:38,420 Najprej pa nekaj objav. 15 00:00:38,420 --> 00:00:42,020 Torej, ena, če bi želeli, da se pridružijo Osebje in sošolci CS50 je na kosilu 16 00:00:42,020 --> 00:00:44,670 ta petek, tako tukaj kot v Cambridge, in v New Haven, 17 00:00:44,670 --> 00:00:48,060 obiščite tečaj je spletna stran, kjer je mogoče najti URL. 18 00:00:48,060 --> 00:00:50,390 Predavanje je to sreda bo ne bo tukaj v Sanders. 19 00:00:50,390 --> 00:00:53,610 To bo na spletu le, da uglasiti na spletni CS50 je, 20 00:00:53,610 --> 00:00:55,850 ali tukaj v Cambridgeu ali New Haven, kot tudi. 21 00:00:55,850 --> 00:00:58,110 >> In potem je problem določiti dva je že v vaših rokah. 22 00:00:58,110 --> 00:01:03,067 Če še niste končal v še, dovolite mi, ponuditi močno določa predlog 23 00:01:03,067 --> 00:01:05,150 da, še posebej zdaj, ko problem določa vnaprej, 24 00:01:05,150 --> 00:01:08,669 si res želite začeti zdaj, če ne Praćakati bit na vikend ali pred 25 00:01:08,669 --> 00:01:10,710 ko so prvič šla ven na Petkih, ker boste 26 00:01:10,710 --> 00:01:14,380 ugotovili, da oni niso nujno daljša ali bolj zahtevna na 27 00:01:14,380 --> 00:01:14,950 sebi. 28 00:01:14,950 --> 00:01:17,575 Mislim, da boste ugotovili, da je v splošno, se nagibajo k približno traja 29 00:01:17,575 --> 00:01:18,892 približno enakem času. 30 00:01:18,892 --> 00:01:20,850 Ampak to seveda odvisno od na študenta, in 31 00:01:20,850 --> 00:01:22,880 odvisno od miselnosti s katero se ji približati. 32 00:01:22,880 --> 00:01:24,910 Ampak vedno, si boste teči navzgor proti neki zid, 33 00:01:24,910 --> 00:01:26,350 in boš udaril nekateri bug, in ste pravkar 34 00:01:26,350 --> 00:01:27,950 ne bo lahko prebolela na neki točki. 35 00:01:27,950 --> 00:01:31,380 In to je zelo dragocen, da bi lahko odmakniti, pridi nazaj naslednji dan, 36 00:01:31,380 --> 00:01:35,286 pojdite na uradnih ur, post na CS50 Razprava ali podobno, da dejansko dobili deblokiranje. 37 00:01:35,286 --> 00:01:36,160 Tako da se vodijo v mislih. 38 00:01:36,160 --> 00:01:40,830 Začenši najzgodnejši možni meri je najboljša stvar, ki jo lahko narediš. 39 00:01:40,830 --> 00:01:44,160 Torej, tukaj je, kjer smo začeli razred, več kot v ničelni tednu. 40 00:01:44,160 --> 00:01:47,441 In lahko smo dobili prostovoljca tukaj, da mi pomaga najti mikrofoni? 41 00:01:47,441 --> 00:01:47,940 V REDU. 42 00:01:47,940 --> 00:01:48,900 Stoje že. 43 00:01:48,900 --> 00:01:50,080 Pridi gor. 44 00:01:50,080 --> 00:01:53,707 Ugani, to je, kako se bo na delo. 45 00:01:53,707 --> 00:01:54,415 Kako ti je ime? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 DAVID J. Malan: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Pridi gor. 49 00:01:57,910 --> 00:01:58,619 Me veseli. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Lepo vas je spoznati. 51 00:01:59,910 --> 00:02:02,772 DAVID J. Malan: In si tu pri nas v ničelno tednu, seveda. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: sem bil. 53 00:02:03,028 --> 00:02:03,160 Sem bil. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. Malan: Torej lahko greš naprej in ugotovite, za nas Mike Smith, 55 00:02:05,868 --> 00:02:08,639 tako hitro, kot si lahko? 56 00:02:08,639 --> 00:02:10,639 Kakor hitro je mogoče. 57 00:02:10,639 --> 00:02:13,756 Dobesedno strga težave na pol, kot ga potrebujete, da. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. Malan: Dobesedno solzenje problem na pol. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Oh. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Zelo dobro. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. Malan: OK. 65 00:02:23,700 --> 00:02:24,200 Dobro. 66 00:02:24,200 --> 00:02:24,701 Hvala. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Zelo dobro. 68 00:02:25,700 --> 00:02:26,210 V REDU. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. Malan: In zdaj, ste ga whittled navzdol 70 00:02:27,610 --> 00:02:29,320 polovici velikost problema. 71 00:02:29,320 --> 00:02:31,267 Zdaj smo do četrtine. 72 00:02:31,267 --> 00:02:33,475 Ali ste pozorni na na kateri strani smo vodenje? 73 00:02:33,475 --> 00:02:34,405 >> [Smeh] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Ja, jaz think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. Malan: Kaj oddelek smo v? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: rute, tako. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. Malan: OK. 78 00:02:39,941 --> 00:02:42,810 Ampak Mike Smith se dogaja da bo po loncev. 79 00:02:42,810 --> 00:02:44,130 SO- 80 00:02:44,130 --> 00:02:48,180 >> [Smeh] 81 00:02:48,180 --> 00:02:48,742 >> V redu. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Kje smo iskali? 83 00:02:50,200 --> 00:02:52,049 DAVID J. Malan: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN ESTRADA: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 DAVID J. Malan: Zdaj smo v kirurški. 86 00:02:54,760 --> 00:02:57,840 Zdaj, zdravniki. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- pojdimo z realnim. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. Malan: Real. 91 00:03:00,970 --> 00:03:01,470 V REDU. 92 00:03:01,470 --> 00:03:03,700 Če potrebujete Real. 93 00:03:03,700 --> 00:03:05,250 Zdaj, v katero smer je Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Ta način. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. Malan: V katero smer? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Počakajte. 97 00:03:08,240 --> 00:03:08,790 M is-- kajne? 98 00:03:08,790 --> 00:03:09,110 Začeli smo with-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. Malan: Ja. 100 00:03:10,090 --> 00:03:10,650 Oni so levo. 101 00:03:10,650 --> 00:03:11,430 Vaša pravica. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Ja. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. Malan: Torej, Mike je tukaj. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Kaj? 105 00:03:13,990 --> 00:03:14,665 >> [Smeh] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Slab zgled, fantje. 108 00:03:18,330 --> 00:03:18,830 Žal mi je. 109 00:03:18,830 --> 00:03:21,610 DAVID J. Malan: To bo naučil vas, da skok iz svojega stola. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Oh. 111 00:03:22,318 --> 00:03:22,890 Oh. 112 00:03:22,890 --> 00:03:23,390 Imam te. 113 00:03:23,390 --> 00:03:24,670 Imam te. 114 00:03:24,670 --> 00:03:25,170 Oh. 115 00:03:25,170 --> 00:03:25,669 Oh. 116 00:03:25,669 --> 00:03:26,812 Ta is-- OK, imam te. 117 00:03:26,812 --> 00:03:27,520 Smith tukaj? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. Malan: Smith, hvala. 119 00:03:28,894 --> 00:03:30,535 Torej bom naprej iskal gor Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, ja. 121 00:03:30,790 --> 00:03:31,340 Ne ne ne. 122 00:03:31,340 --> 00:03:31,600 O, ne. 123 00:03:31,600 --> 00:03:31,940 To je moje. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. Malan: Oh, ti imaš Smith. 125 00:03:32,580 --> 00:03:33,415 V REDU. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Ja, dobil Smith tukaj. 127 00:03:34,040 --> 00:03:34,700 Oprostite, fantje. 128 00:03:34,700 --> 00:03:35,860 Mislil sem Michael-- smo iskali Mihaela. 129 00:03:35,860 --> 00:03:36,550 Žal mi je. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. Malan: To je v redu. 131 00:03:37,550 --> 00:03:39,950 Vse je v redu, zdaj smo v Paccini in Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini in sinovi. 133 00:03:41,242 --> 00:03:43,158 DAVID J. Malan: Samo ti in sem v zvezi s tem. 134 00:03:43,158 --> 00:03:44,050 V REDU. 135 00:03:44,050 --> 00:03:45,130 Najdi nam Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Smith. 137 00:03:45,830 --> 00:03:46,310 >> ALAN ESTRADA: Smith. 138 00:03:46,310 --> 00:03:46,750 >> DAVID J. Malan: Smith. 139 00:03:46,750 --> 00:03:47,728 Mi smo v R za smeti. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Zanič. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 To bo trajalo nekaj časa. 143 00:03:52,480 --> 00:03:54,340 >> [Smeh] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. Malan: Čevlji. 146 00:03:56,720 --> 00:03:58,080 Mi smo v čevljih. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Zdaj smo gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. Malan: Lepo. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [Smeh] 151 00:04:03,620 --> 00:04:05,440 Oh, to je super. 152 00:04:05,440 --> 00:04:06,910 [Smeh] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. Malan: To je v redu. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, to je dobro. 156 00:04:11,365 --> 00:04:14,425 Mislim, da ne bom imajo PSAT prijatelji po tem. 157 00:04:14,425 --> 00:04:15,300 DAVID J. Malan: Dobro. 158 00:04:15,300 --> 00:04:16,078 Sporting. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporting. 160 00:04:17,036 --> 00:04:18,668 Um, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 DAVID J. Malan: OK. 162 00:04:19,459 --> 00:04:21,600 Torej, kaj je trgati to na pol. 163 00:04:21,600 --> 00:04:22,270 To je v redu. 164 00:04:22,270 --> 00:04:25,606 Ta se konča slabo vseeno, ker Mike Smith ne bo v rumenih straneh. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. Malan: Ne, to je v redu. 167 00:04:27,140 --> 00:04:28,930 Ampak kaj je pretvarjal, kot da je na tej strani. 168 00:04:28,930 --> 00:04:33,260 Torej sedaj, ko ste whittled problem navzdol na eni strani, in smo ugotovili, Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Vzklikati] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 OK, hvala. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 V REDU. 174 00:04:41,200 --> 00:04:43,646 To je bil izjemen. 175 00:04:43,646 --> 00:04:45,954 Ampak to je še vedno hitrejši kot linearno iskanje, 176 00:04:45,954 --> 00:04:47,870 kjer smo začeti izvajati začetek knjige, 177 00:04:47,870 --> 00:04:51,210 in gremo svojo pot od leve proti desni, sčasoma iščejo Mike Smith. 178 00:04:51,210 --> 00:04:53,540 In tako, če je telefon knjige imeli morda 1000 strani, 179 00:04:53,540 --> 00:04:56,300 Morda bi bilo treba nam 10 ali tako stran solze. 180 00:04:56,300 --> 00:04:59,380 >> Ampak ste morda vzvodom dotaknili domnevo 181 00:04:59,380 --> 00:05:03,602 Med vse to, kar pomeni, da je telefonski imenik vnaprej, kaj? 182 00:05:03,602 --> 00:05:04,310 OBČINSTVO: Urejeno. 183 00:05:04,310 --> 00:05:05,000 DAVID J. Malan: To je urejeno. 184 00:05:05,000 --> 00:05:05,160 Prav? 185 00:05:05,160 --> 00:05:07,909 To je urejeno po abecedi, zato da so vsi od teh imen in številk 186 00:05:07,909 --> 00:05:11,230 so razvrščene od A k Z-ih, in po abecedi vmes. 187 00:05:11,230 --> 00:05:13,100 Ampak danes, zdaj vprašati, Vprašanje, dobro, 188 00:05:13,100 --> 00:05:16,170 kako je Verizon ali telefon Družba je dobil v tej državi? 189 00:05:16,170 --> 00:05:19,560 >> Ker je to ena stvar za spodbuditev ta domneva, zato 190 00:05:19,560 --> 00:05:22,570 rešiti problem z Algoritem učinkoviteje. 191 00:05:22,570 --> 00:05:24,900 Ampak mi nikoli zares vprašal ničelno tednu, no, 192 00:05:24,900 --> 00:05:27,790 koliko je to storil stroški Verizon ali kdo drug 193 00:05:27,790 --> 00:05:29,620 da bi dobili ta telefonski imenik, v urejenem stanju? 194 00:05:29,620 --> 00:05:29,780 >> Prav? 195 00:05:29,780 --> 00:05:31,529 Ni važno, če je looking up Mike Smith 196 00:05:31,529 --> 00:05:35,190 je super hiter, če vas je potrebno leto za razvrščanje strani na začetku. 197 00:05:35,190 --> 00:05:35,690 Prav? 198 00:05:35,690 --> 00:05:38,620 Boste lahko tudi samo presejanje skozi randomizirani imeniku, 199 00:05:38,620 --> 00:05:40,690 če se dogaja, da je super drago, da ga rešiti. 200 00:05:40,690 --> 00:05:42,350 Torej, če imamo lahko še prostovoljca. 201 00:05:42,350 --> 00:05:46,350 Oglejmo si oglejte tukaj na kako might-- pridi up-- kako 202 00:05:46,350 --> 00:05:48,100 bomo morda lotili sortiranje teh. 203 00:05:48,100 --> 00:05:51,990 >> In če Jordanija bi dejansko Pridružite se nam tukaj na odru. 204 00:05:51,990 --> 00:05:55,100 Pridi gor samo za trenutek. 205 00:05:55,100 --> 00:05:56,359 Kako ti je ime? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. Malan: Caroline, pridi gor. 208 00:05:58,691 --> 00:06:02,070 In se boste pridružili mene in Jordanijo tukaj. 209 00:06:02,070 --> 00:06:03,800 Caroline, hvala. 210 00:06:03,800 --> 00:06:04,300 V redu. 211 00:06:04,300 --> 00:06:08,330 Torej, kaj imamo tukaj Caroline je 26 modrih knjig 212 00:06:08,330 --> 00:06:10,747 da FAS uporablja za upravljanje nekatere končne izpite. 213 00:06:10,747 --> 00:06:13,330 Ti so že težko najti, ampak, kaj smo naredili v vnaprej 214 00:06:13,330 --> 00:06:15,800 je, da smo dal ime nekoga na sprednji strani vsakega od njih, 215 00:06:15,800 --> 00:06:18,133 vendar smo hranijo preprosto s potem gašenju polna imena. 216 00:06:18,133 --> 00:06:22,720 Torej bi mi dal osebo z imenom L, D, J, B, vse od A do Z, 217 00:06:22,720 --> 00:06:24,090 ampak oni so v naključnem vrstnem redu. 218 00:06:24,090 --> 00:06:26,890 In tudi če bi jih, govoril Vaš pot skozi problem kot ti 219 00:06:26,890 --> 00:06:31,620 ne to, lahko greš naprej in razvrstiti ti za nas, od A do Ž 220 00:06:31,620 --> 00:06:34,070 >> OBČINSTVO: OK, tako da je L, kot je srednji. 221 00:06:34,070 --> 00:06:35,050 C se začenja. 222 00:06:35,050 --> 00:06:42,410 B. J pred L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. Malan: Drži, da je pomislili za eno sekundo. 224 00:06:45,140 --> 00:06:48,910 Ker v nasprotnem primeru je to le zanimivo, da ti, jaz in Jordanijo. 225 00:06:48,910 --> 00:06:49,724 Tam gremo. 226 00:06:49,724 --> 00:06:50,640 OBČINSTVO: [neslišno]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. Malan: OK. 229 00:06:58,090 --> 00:06:59,310 Kaj delaš? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M prihaja po O. 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. Malan: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. Malan: O, dober. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> DAVID J. Malan: E, F. Ja. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V. 237 00:07:07,620 --> 00:07:10,689 >> DAVID J. Malan: V, T, U, V. Torej je Izgleda, da ste making-- nadaljuj. 238 00:07:10,689 --> 00:07:12,730 Izgleda, da delaš velik kup tukaj, 239 00:07:12,730 --> 00:07:13,910 in nekako velik kup tam. 240 00:07:13,910 --> 00:07:16,230 Torej, v prvi polovici abecede, Druga polovica abecede. 241 00:07:16,230 --> 00:07:16,460 V REDU. 242 00:07:16,460 --> 00:07:16,960 Dobro. 243 00:07:16,960 --> 00:07:19,680 Vrsta razdelitev problema na dva dela. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Ja. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. Malan: OK. 247 00:07:22,980 --> 00:07:25,070 K. Torej ste nekako izbiro jih enega za drugim, 248 00:07:25,070 --> 00:07:27,620 ga je dala levo ali desno, ali Z dogaja na tleh. 249 00:07:27,620 --> 00:07:28,012 V REDU. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z dogaja na tleh. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. Malan: OK. 252 00:07:29,360 --> 00:07:30,920 Y se dogaja na tleh. 253 00:07:30,920 --> 00:07:31,735 Zdaj bomo lahko X. 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 DAVID J. Malan: G se dogaja levo. 256 00:07:33,700 --> 00:07:36,017 S se dogaja prav. 257 00:07:36,017 --> 00:07:37,642 Vredu, A bo vse tekme. 258 00:07:37,642 --> 00:07:38,790 >> CAROLINE: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> DAVID J. Malan: Zdaj, dobro. 260 00:07:39,873 --> 00:07:43,260 Imamo A, B, C. W dogaja tam dol. 261 00:07:43,260 --> 00:07:45,566 Vse je v redu, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, J, J. 263 00:07:46,611 --> 00:07:47,860 DAVID J. Malan: H, I, J. Good. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: V centru, sem gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. Malan: OK. 266 00:07:50,000 --> 00:07:52,375 Torej, zdaj, gremo na vrsto za združevanje teh različnih podporniki. 267 00:07:52,375 --> 00:08:00,730 Torej A do C, potem pa vidim, D, in E in F in G in H in I. Nica. 268 00:08:00,730 --> 00:08:05,540 J, K. In potem ta pile z glavo navzdol, ampak to je v redu. 269 00:08:05,540 --> 00:08:06,040 Sure. 270 00:08:06,040 --> 00:08:07,240 Režemo lahko nekatere kotičke. 271 00:08:07,240 --> 00:08:07,950 V REDU. 272 00:08:07,950 --> 00:08:10,530 In potem moramo W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Ja. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. Malan: Odlično. 275 00:08:11,880 --> 00:08:14,122 Tako velika hvala Caroline za razvrščanje teh. 276 00:08:14,122 --> 00:08:15,030 >> [Vzklikati] 277 00:08:15,030 --> 00:08:17,287 >> Hvala. 278 00:08:17,287 --> 00:08:18,120 Najlepša hvala. 279 00:08:18,120 --> 00:08:22,910 Torej, zdaj pa menijo, za trenutek kako Caroline šla o tem, da je 280 00:08:22,910 --> 00:08:26,040 in kaj točno smo bili sposobni to-- kako smo 281 00:08:26,040 --> 00:08:28,409 mogli rešiti, da problem, ko smo bili tik 282 00:08:28,409 --> 00:08:29,950 saj cel kup naključnih vhodov. 283 00:08:29,950 --> 00:08:31,610 >> No, izgleda, da obstaja je bil malo sistema tam? 284 00:08:31,610 --> 00:08:32,110 Prav. 285 00:08:32,110 --> 00:08:34,495 Torej prejšnjih pismih v abecedi, ona 286 00:08:34,495 --> 00:08:37,120 je dajanje na levi, in slej črk v abecedi, 287 00:08:37,120 --> 00:08:38,270 ona je dajanje v desno. 288 00:08:38,270 --> 00:08:40,500 In takoj, ko je ugotovila, nekateri proksimalne pisma, tisti, 289 00:08:40,500 --> 00:08:43,124 da gremo desno drug poleg drugega, ona bi dal tistim v redu. 290 00:08:43,124 --> 00:08:46,750 In tako smo nekako imeli ti mali kupov sortiranih vložkov, ki se pojavljajo. 291 00:08:46,750 --> 00:08:50,540 >> In tako, da je precej všeč, kar večina od nas ljudi bi naredil. 292 00:08:50,540 --> 00:08:53,530 Mi bi nekako odbirati skozi njo, in sva nekako imajo mehanizem. 293 00:08:53,530 --> 00:08:56,930 Morda pa bi bilo težko napisati je določen v formuli po sebi. 294 00:08:56,930 --> 00:08:59,010 Se mu je zdelo malo bolj ekološki kot to. 295 00:08:59,010 --> 00:09:02,560 Torej, da vidimo, če bomo lahko zdaj veže problem z manj vložkov. 296 00:09:02,560 --> 00:09:05,170 >> Namesto, 26., dajmo nekaj narediti veliko manj 297 00:09:05,170 --> 00:09:09,890 s pravkar rekel, sedem, zadaj ta vrata, tako rekoč. 298 00:09:09,890 --> 00:09:11,300 Obstajajo le sedem številk? 299 00:09:11,300 --> 00:09:15,240 In če je cilj zdaj z je najti vrednost 300 00:09:15,240 --> 00:09:17,850 Poglejmo, kako učinkovito moremo iti o tem. 301 00:09:17,850 --> 00:09:22,460 In poglejmo, če bomo lahko zdaj začeti uporabljati nekaj številk, 302 00:09:22,460 --> 00:09:26,310 ali nekatere formule, ki opisuje učinkovitost našega imenika 303 00:09:26,310 --> 00:09:31,060 algoritem, naš izpit knjiga algoritem, in bolj splošno, iskanju informacij. 304 00:09:31,060 --> 00:09:34,770 >> Torej za to, naj gredo naprej, in na zaslonu na dotik tukaj, 305 00:09:34,770 --> 00:09:41,100 nepripravljena spletni brskalnik, ki ima točno teh sedem vrata. 306 00:09:41,100 --> 00:09:46,670 In če bi lahko dobil eno drugo prostovoljno pridi sem, 307 00:09:46,670 --> 00:09:48,480 Sem dal ta ista vrata tukaj. 308 00:09:48,480 --> 00:09:49,170 Hitro prostovoljec. 309 00:09:49,170 --> 00:09:51,130 >> Ta one-- demos se dogaja k hitrejši in hitrejši zdaj. 310 00:09:51,130 --> 00:09:51,600 Pridi dol. 311 00:09:51,600 --> 00:09:52,308 Kako ti je ime? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> DAVID J. Malan: Trevor? 314 00:09:53,998 --> 00:09:55,770 V redu je, Trevor, pridi dol. 315 00:09:55,770 --> 00:09:59,212 Torej je Trevor tukaj prostovoljno narediti podoben problem, ampak tisti, ki je 316 00:09:59,212 --> 00:10:02,170 ožji obseg, in da se dogaja da nam omogočajo, da bi poskušali formalizirati zdaj 317 00:10:02,170 --> 00:10:03,970 postopek za sortiranje te številke. 318 00:10:03,970 --> 00:10:05,500 >> Torej, Trevor, lepo, da sva se spoznala. 319 00:10:05,500 --> 00:10:08,720 Torej, tukaj je niz, tako da govorijo, seznam sedmih vratih. 320 00:10:08,720 --> 00:10:10,327 Pojdi naprej in nam najti številko 50. 321 00:10:10,327 --> 00:10:12,410 In nato po dejstvu, nam je povedal, kako si ga našel. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Morala be-- vso pravico. 324 00:10:20,040 --> 00:10:21,945 Ja, to je tista tukaj? 325 00:10:21,945 --> 00:10:24,680 Uh-oh. 326 00:10:24,680 --> 00:10:25,560 V REDU. 327 00:10:25,560 --> 00:10:26,680 Ste kliknili, da je eden. 328 00:10:26,680 --> 00:10:28,690 Dobro. 329 00:10:28,690 --> 00:10:29,780 >> In dobro. 330 00:10:29,780 --> 00:10:30,970 Zdaj ste kliknili, da je eden. 331 00:10:30,970 --> 00:10:34,060 In naj ti dam mikrofon, tako da ga imate v samo trenutek. 332 00:10:34,060 --> 00:10:37,000 Pojdi naprej in kliknite soseda, ki jih nameravate. 333 00:10:37,000 --> 00:10:39,812 Ja, dobro. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Lahko sem unclick vrata? 335 00:10:41,020 --> 00:10:42,620 DAVID J. Malan: Ne, ne moreš unclick. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Tale. 338 00:10:43,974 --> 00:10:45,640 DAVID J. Malan: Kam želite iti? 339 00:10:45,640 --> 00:10:46,410 Kateri? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: To je ena. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. Malan: No. 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Tale. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. Malan: Da. 345 00:10:49,020 --> 00:10:49,700 To je bilo dobro. 346 00:10:49,700 --> 00:10:50,380 V redu. 347 00:10:50,380 --> 00:10:53,900 Torej, kaj je bil tvoj algoritem ali Postopek za početje to, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: sem šel skozi vrata, dokler sem našel 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. Malan: OK. 350 00:10:56,940 --> 00:10:58,150 Odlično algoritem. 351 00:10:58,150 --> 00:10:59,540 Tako da je v redu. 352 00:10:59,540 --> 00:11:03,120 Ker v bistvu, če sem razkril, kaj je v ozadju teh dveh drugih vratih, kaj 353 00:11:03,120 --> 00:11:06,954 bomo ugotovili, tukaj je, da imamo le naključno vhod. 354 00:11:06,954 --> 00:11:08,870 Tako da je bil dejansko kot dobra, kot bi lahko dobili. 355 00:11:08,870 --> 00:11:12,509 In v resnici, imaš boljši kot izčrpno iskanje celotno paleto, 356 00:11:12,509 --> 00:11:15,300 ker bi bilo res nesrečni, če bi zadeli številko 357 00:11:15,300 --> 00:11:16,604 50 v zadnjem vrat. 358 00:11:16,604 --> 00:11:18,520 Toda kaj, če bomo namesto ti je dal predpostavko. 359 00:11:18,520 --> 00:11:20,630 Recimo, da sem nekako vse ta vrata vsem, 360 00:11:20,630 --> 00:11:23,500 tako da imate številke razporejene tokrat 361 00:11:23,500 --> 00:11:29,730 vendar tokrat je dejansko different-- ta čas, 362 00:11:29,730 --> 00:11:32,640 to je dejansko razporejene za vas. 363 00:11:32,640 --> 00:11:35,380 In zdaj je cilj pri roki je udaril številko 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. Malan: Kaj je svoj algoritem bo? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: No, če je to razporejene, da je bodisi dogaja 367 00:11:39,628 --> 00:11:42,710 da be-- če največja do največjih, spušča, bo to prvi, 368 00:11:42,710 --> 00:11:44,751 ali če je nasprotno, bo zadnja. 369 00:11:44,751 --> 00:11:48,897 Torej, jaz bom samo izkoristiti ta vrata, in potem samo dotaknite zadnja vrata. 370 00:11:48,897 --> 00:11:49,980 DAVID J. Malan: Odlično. 371 00:11:49,980 --> 00:11:50,270 V redu. 372 00:11:50,270 --> 00:11:51,150 Tako smo ugotovili, številko 50. 373 00:11:51,150 --> 00:11:52,970 Torej takoj, ko boste vedeli, so bile razporejene smo 374 00:11:52,970 --> 00:11:55,040 bili sposobni vzvoda te predpostavke. 375 00:11:55,040 --> 00:11:57,040 Torej, oni preveč všeč primer telefonski imenik. 376 00:11:57,040 --> 00:11:59,540 Takoj, ko imate, tudi z majhen problem, kot je ta, 377 00:11:59,540 --> 00:12:02,380 vaši vložki vnaprej razporejene, smo lahko dejansko našli vrednost nedvomno 378 00:12:02,380 --> 00:12:03,130 učinkoviteje. 379 00:12:03,130 --> 00:12:05,800 >> In ti, če je ni povedal razporejene majhnih do velikih, ali velik, da majhne, 380 00:12:05,800 --> 00:12:08,080 in tako je bilo zelo smiselno začeti na enem koncu ali drugo 381 00:12:08,080 --> 00:12:09,750 da bi dejansko ugotovili, da ciljne vrednosti. 382 00:12:09,750 --> 00:12:11,400 Torej, hvala za Trevor kot dobro. 383 00:12:11,400 --> 00:12:13,260 In bom propose-- lepo naredil. 384 00:12:13,260 --> 00:12:16,960 Imamo malo posnetek, pravzaprav, da je med naših najljubših trenutkov v CS50, 385 00:12:16,960 --> 00:12:19,700 pri čemer včasih ti demos Ne čisto gredo po načrtu. 386 00:12:19,700 --> 00:12:22,050 In res zdaj sem potegnil napačen vmesnik 387 00:12:22,050 --> 00:12:23,508 s katero za uporabo zaslona na dotik. 388 00:12:23,508 --> 00:12:24,660 Tako da je bila moja krivda obstaja. 389 00:12:24,660 --> 00:12:26,600 >> Torej bo to za naslednje leto posnetek kot 390 00:12:26,600 --> 00:12:28,570 zakaj sem se tako, da kliknete na svojem zaslonu. 391 00:12:28,570 --> 00:12:31,390 Ampak kaj je na hitro pogledamo kaj se je zgodilo lani 392 00:12:31,390 --> 00:12:34,770 z Jay, ki je pritekel, veliko kot Trevor tukaj, prostovoljno, 393 00:12:34,770 --> 00:12:39,380 in v tem kratkem posnetku, boste videli, kako ta isti demo ni povsem 394 00:12:39,380 --> 00:12:41,074 razkrije enake naučili. 395 00:12:41,074 --> 00:12:41,740 [VIDEO PREDVAJANJE] 396 00:12:41,740 --> 00:12:45,360 -Vse Želim, da sedaj storiti je, najti zame in za nas, 397 00:12:45,360 --> 00:12:51,674 Res, številka 50 en korak naenkrat. 398 00:12:51,674 --> 00:12:52,450 >> -V Številka 50? 399 00:12:52,450 --> 00:12:53,190 >> -V Številka 50. 400 00:12:53,190 --> 00:12:55,356 In lahko pokažejo, kaj je za vsakim od teh vrat 401 00:12:55,356 --> 00:12:58,540 zgolj z dotikom s prstom. 402 00:12:58,540 --> 00:13:00,910 Prekleto. 403 00:13:00,910 --> 00:13:02,870 >> [Smeh] 404 00:13:02,870 --> 00:13:03,806 >> [END PREDVAJANJE] 405 00:13:03,806 --> 00:13:05,430 DAVID J. Malan: Torej, da je šlo zelo dobro. 406 00:13:05,430 --> 00:13:06,796 Tisti, ki so bili nerazvrščenih vrata. 407 00:13:06,796 --> 00:13:08,670 Jay seveda vse to našel prehitro. 408 00:13:08,670 --> 00:13:12,910 Trevor naredil veliko boljše delo v smislu teachable trenutku 409 00:13:12,910 --> 00:13:15,850 tako rekoč, letos v traja dlje, da ga najdejo. 410 00:13:15,850 --> 00:13:17,950 Seveda, nato pa smo dali Jay druga priložnost, 411 00:13:17,950 --> 00:13:20,320 pri čemer smo razporejene vrata, tako kot smo naredili za Trevor, 412 00:13:20,320 --> 00:13:22,300 in storil Trevor super tudi tokrat. 413 00:13:22,300 --> 00:13:26,124 Ampak Jay je to naredil pol tako hitro. 414 00:13:26,124 --> 00:13:26,790 [VIDEO PREDVAJANJE] 415 00:13:26,790 --> 00:13:29,650 -V Cilj zdaj je, da tudi nas najdete številko 50, 416 00:13:29,650 --> 00:13:33,030 ampak to algorithmically, in nam je povedal, kako boš o tem. 417 00:13:33,030 --> 00:13:33,660 >> -V REDU. 418 00:13:33,660 --> 00:13:35,604 >> In če boste ugotovili, da obdržite film. 419 00:13:35,604 --> 00:13:37,228 Če ga ne najdeš, jo dal nazaj. 420 00:13:37,228 --> 00:13:38,044 >> -Man. 421 00:13:38,044 --> 00:13:38,860 >> Oh! 422 00:13:38,860 --> 00:13:40,800 >> - [Neslišno] OK. 423 00:13:40,800 --> 00:13:46,236 Torej grem preveriti konce najprej ugotoviti, če there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Aplavz] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [END PREDVAJANJE] 427 00:13:55,729 --> 00:13:56,520 DAVID J. Malan: OK. 428 00:13:56,520 --> 00:13:59,760 Torej je jasno sortiranje vrata vodi k večji učinkovitosti. 429 00:13:59,760 --> 00:14:01,680 In tako, dvakrat hitreje je tisto, kar sem mislil tam. 430 00:14:01,680 --> 00:14:03,270 In tako Jay imaš srečo obakrat. 431 00:14:03,270 --> 00:14:06,685 In je prišel tudi srečo, da je zadnji leto, sem naročil nekaj Blu-ray diskov 432 00:14:06,685 --> 00:14:07,560 dejansko dati ven. 433 00:14:07,560 --> 00:14:09,768 Žal mi je letos smo niso imeli enake, Trevor. 434 00:14:09,768 --> 00:14:11,540 Ampak še vedno bolje, je bilo nekaj let nazaj. 435 00:14:11,540 --> 00:14:14,820 In nekateri od vas bi to vedeli, kolega, Sean, ki je, ko je bil v CS50, 436 00:14:14,820 --> 00:14:17,780 je izpodbijala z natančno isti problem, čeprav v SD, 437 00:14:17,780 --> 00:14:19,360 kot boste kmalu videli, nazaj v dan. 438 00:14:19,360 --> 00:14:22,622 In boste ugotovili, da ne samo, da je trajalo malo dlje, kot Jay, 439 00:14:22,622 --> 00:14:25,580 malo dlje, kot Trevor, je bilo dejansko je to čudovita priložnost 440 00:14:25,580 --> 00:14:29,820 da sodelujejo skoraj vsi v Množica a la Cena je desno, spodbujanje 441 00:14:29,820 --> 00:14:31,889 mu, da bi našli številko smo išče. 442 00:14:31,889 --> 00:14:32,930 Poglejmo. na hitro pogledamo. 443 00:14:32,930 --> 00:14:33,320 >> [VIDEO PREDVAJANJE] 444 00:14:33,320 --> 00:14:33,820 >> -V REDU. 445 00:14:33,820 --> 00:14:36,680 Torej, vaša naloga tukaj, Sean, je naslednja. 446 00:14:36,680 --> 00:14:40,860 Imam skriva ti vrata številka sedem. 447 00:14:40,860 --> 00:14:45,120 Ampak spravljen v nekaterih od teh vrat kakor tudi druge negativne številke. 448 00:14:45,120 --> 00:14:47,500 In vaš cilj je, da razmišljajo tega zgornji vrstici številk 449 00:14:47,500 --> 00:14:50,390 kot le niz, ali pa samo Zaporedje lističe 450 00:14:50,390 --> 00:14:51,510 s številkami stojijo za njimi. 451 00:14:51,510 --> 00:14:55,540 In vaš cilj je, da samo z uporabo vrh matrika tu našli mi številko sedem. 452 00:14:55,540 --> 00:14:58,570 In mi se potem dogaja, da kritika kako iti na to početje. 453 00:14:58,570 --> 00:14:59,070 -V redu. 454 00:14:59,070 --> 00:15:00,850 -Poišči Nam številko sedem, prosim. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 No. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Pet, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Smeh] 461 00:15:24,770 --> 00:15:25,910 >> To ni trik vprašanje. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Ena. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Smeh] 466 00:15:34,695 --> 00:15:37,861 Na tej točki, vaša ocena ni zelo dobro, tako da boste lahko tudi nadaljujem. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Tri. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Smeh] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Nadaljuj. 473 00:15:47,774 --> 00:15:50,690 Iskreno povedano, ne morem pomagati, ampak se sprašujem, kaj si celo razmišljal o tem, SO- 474 00:15:50,690 --> 00:15:51,959 >> [Smeh] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Samo zgornji vrstici, tako imaš tri levo. 477 00:15:55,020 --> 00:15:56,200 Torej mi našli sedem. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Smeh] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Seven. 484 00:16:26,946 --> 00:16:28,780 >> [Aplavz] 485 00:16:28,780 --> 00:16:29,426 >> V redu. 486 00:16:29,426 --> 00:16:30,360 >> [END PREDVAJANJE] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. Malan: Torej smo lahko gledam te ves dan. 488 00:16:31,840 --> 00:16:34,090 In seveda, nekateri Letošnje demos morda 489 00:16:34,090 --> 00:16:36,330 bo sedaj končajo v naslednjem Letošnji video kot dobro. 490 00:16:36,330 --> 00:16:39,040 Torej, zdaj pa je dejansko osredotočiti na algoritmih 491 00:16:39,040 --> 00:16:42,140 tukaj, in videli, če ne moremo zdaj začeti formalizirati 492 00:16:42,140 --> 00:16:46,650 kako lahko gremo približno pridobivanje našo podatkov v tem stanju, da je to urejeno, 493 00:16:46,650 --> 00:16:50,054 tako da je na koncu, lahko smo dejansko je bolj učinkovito iskanje. 494 00:16:50,054 --> 00:16:52,470 In čeprav gremo uporabljati dokaj majhne podatkovne nize, 495 00:16:52,470 --> 00:16:54,511 kot osem številk mi imajo tukaj na krovu, 496 00:16:54,511 --> 00:16:58,230 končno posrečilo, da bi te iste ideje 1.000 vnosov, milijon vhodi, 497 00:16:58,230 --> 00:17:02,100 4 milijarde vhodi, saj algoritmi se bodo v osnovi enaka. 498 00:17:02,100 --> 00:17:05,359 >> In zato je to naša zadnja priložnost za prostovoljce danes, 499 00:17:05,359 --> 00:17:09,790 vendar morda najbolj zahteven, za katerega smo potrebovali osem prostovoljcev 500 00:17:09,790 --> 00:17:12,960 da pridejo in nas sprehod skozi Proces razvrščanja, kar bo kmalu 501 00:17:12,960 --> 00:17:15,212 se na teh glasbe tu stoji. 502 00:17:15,212 --> 00:17:16,170 Naj začnem spet tukaj. 503 00:17:16,170 --> 00:17:19,692 >> Torej, ena v turquoise-- zelena je to? 504 00:17:19,692 --> 00:17:21,130 Ali si storila? 505 00:17:21,130 --> 00:17:21,630 Dva. 506 00:17:21,630 --> 00:17:23,069 Pridi dol. 507 00:17:23,069 --> 00:17:23,569 V REDU. 508 00:17:23,569 --> 00:17:24,420 Tri. 509 00:17:24,420 --> 00:17:25,400 Four. 510 00:17:25,400 --> 00:17:27,247 Naj me-- OK, pet. 511 00:17:27,247 --> 00:17:28,830 Bili ste imenuje svojega prijatelja. 512 00:17:28,830 --> 00:17:31,340 Šest, sedem in osem. 513 00:17:31,340 --> 00:17:32,130 Pridi gor. 514 00:17:32,130 --> 00:17:32,630 V redu. 515 00:17:32,630 --> 00:17:33,190 Najlepša hvala. 516 00:17:33,190 --> 00:17:33,689 Pridi gor. 517 00:17:33,689 --> 00:17:34,790 Pridi gor. 518 00:17:34,790 --> 00:17:35,330 >> V redu. 519 00:17:35,330 --> 00:17:38,890 Torej, kaj smo here-- in to imelo je med bolj nerodnih tiste, 520 00:17:38,890 --> 00:17:42,390 saj bo to zahtevajo, da humor me za samo malo časa. 521 00:17:42,390 --> 00:17:43,442 Vam mora biti številka ena. 522 00:17:43,442 --> 00:17:44,150 Kako ti je ime? 523 00:17:44,150 --> 00:17:44,610 >> ANNAN: Annan. 524 00:17:44,610 --> 00:17:45,526 >> DAVID J. Malan: Annan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 Kako ti je ime? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. Malan: Joseph, ste številka dve. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, številka tri. 530 00:17:52,260 --> 00:17:53,722 Stefan, številka štiri. 531 00:17:53,722 --> 00:17:54,430 Cynthia: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. Malan: Cynthia, številka pet. 533 00:17:57,548 --> 00:17:58,452 [Neslišno] 534 00:17:58,452 --> 00:17:59,618 DAVID J. Malan: [neslišno]. 535 00:17:59,618 --> 00:18:00,391 David, številka šest. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. Malan: Matt številka sedem. 538 00:18:02,160 --> 00:18:02,850 In? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. Malan: Waverly, številka osem. 541 00:18:04,470 --> 00:18:04,970 V redu. 542 00:18:04,970 --> 00:18:06,510 Če could-- Ops. 543 00:18:06,510 --> 00:18:08,820 Če vas vse, kar si Prvi izziv je 544 00:18:08,820 --> 00:18:10,820 osem glasbenih stojala tu sooča občinstvo. 545 00:18:10,820 --> 00:18:14,200 Če bi si dal svoje številke na ti glasba stoji na tak način, 546 00:18:14,200 --> 00:18:16,560 da ravnini s Iste številke na krovu. 547 00:18:16,560 --> 00:18:19,560 Torej bi sami videti kot da jih dajanje vaše številke na teh glasbe 548 00:18:19,560 --> 00:18:21,960 stoji tukaj. 549 00:18:21,960 --> 00:18:25,980 Odlično doslej. 550 00:18:25,980 --> 00:18:26,600 >> Odlično. 551 00:18:26,600 --> 00:18:26,890 V REDU. 552 00:18:26,890 --> 00:18:29,556 Torej sedaj, bomo vprašati Vprašanje v nekaj različnih načinov. 553 00:18:29,556 --> 00:18:31,610 Kako lahko gremo o sortiranje ti ljudje tu gor? 554 00:18:31,610 --> 00:18:34,500 Ker smo imeli nekaj pristopov prej, s čimer smo 555 00:18:34,500 --> 00:18:36,360 vrsta kar dve različni vedra. 556 00:18:36,360 --> 00:18:38,842 In potem smo bili na splošno piecing stvari skupaj. 557 00:18:38,842 --> 00:18:41,050 Takoj, ko smo videli dve številki ki je pripadal skupaj, 558 00:18:41,050 --> 00:18:41,975 smo jih skupaj. 559 00:18:41,975 --> 00:18:43,350 Dve črki, ki sodijo skupaj. 560 00:18:43,350 --> 00:18:45,058 >> Ampak poglejmo, če bomo ni mogoče formalizirati to, 561 00:18:45,058 --> 00:18:48,044 tako, da smo na koncu še nekaj psevdo-kodo, ki jo bo, 562 00:18:48,044 --> 00:18:49,710 s katero lahko rešili te probleme. 563 00:18:49,710 --> 00:18:51,870 Torej sedaj, gledam ven Na teh številkah tukaj. 564 00:18:51,870 --> 00:18:55,030 In vidim cel kup napak. 565 00:18:55,030 --> 00:18:57,750 Konec koncev, hočem ena na levo in osem na desni strani. 566 00:18:57,750 --> 00:19:00,650 >> In tako gledam ti dve, štiri in dve. 567 00:19:00,650 --> 00:19:02,930 In v čem je problem, seveda? 568 00:19:02,930 --> 00:19:04,261 Ja. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Dva očitno pride pred štiri, tako da boste vedeli, kaj? 571 00:19:07,160 --> 00:19:10,210 Dovolite mi, da najprej sprejmejo požrešen pristop, Če bo, podobno kot problem 572 00:19:10,210 --> 00:19:13,790 nastavite one-- če se spomnimo iz Standard Edition problematičnih Set One, 573 00:19:13,790 --> 00:19:16,820 kjer sem samo lokalno rešiti problem da je prav tukaj pred mano 574 00:19:16,820 --> 00:19:17,690 in videli, kje me vodi. 575 00:19:17,690 --> 00:19:17,870 >> V REDU. 576 00:19:17,870 --> 00:19:20,161 Torej, dve leti in štiri, pusti me naprej in samo ti zamenjali dva. 577 00:19:20,161 --> 00:19:22,400 Če lahko fizično premikanje sami in vaš prispevek, 578 00:19:22,400 --> 00:19:25,040 Zdi se mi, da so gotten seznam v boljšem stanju. 579 00:19:25,040 --> 00:19:26,330 >> Zdaj, oni so dobri. 580 00:19:26,330 --> 00:19:28,480 Grem, da se premaknete naprej, štiri in šest, izgleda dobro. 581 00:19:28,480 --> 00:19:29,110 Ni problem. 582 00:19:29,110 --> 00:19:30,440 Šest in osem, OK. 583 00:19:30,440 --> 00:19:31,860 Osem in ena, še ena težava. 584 00:19:31,860 --> 00:19:34,750 Ker kaj je res približno osem in ena? 585 00:19:34,750 --> 00:19:36,990 Eden pride pred osem, in tako, kaj naj storimo? 586 00:19:36,990 --> 00:19:38,090 Oglejmo swap teh dveh. 587 00:19:38,090 --> 00:19:39,316 Ena in osem. 588 00:19:39,316 --> 00:19:40,690 In zdaj, bom nadaljuj. 589 00:19:40,690 --> 00:19:42,030 Grem, da pogled v prihodnost. 590 00:19:42,030 --> 00:19:42,840 In poglejmo, kaj se dogaja. 591 00:19:42,840 --> 00:19:44,680 Osem in tri, od Seveda je v okvari. 592 00:19:44,680 --> 00:19:45,815 Oglejmo swap. 593 00:19:45,815 --> 00:19:46,940 Osem in sedem, seveda. 594 00:19:46,940 --> 00:19:47,481 Ne deluje. 595 00:19:47,481 --> 00:19:48,280 Oglejmo swap. 596 00:19:48,280 --> 00:19:49,940 Osem pet, seveda, kaj je swap. 597 00:19:49,940 --> 00:19:50,560 V redu. 598 00:19:50,560 --> 00:19:51,880 Seznam je razvrščen. 599 00:19:51,880 --> 00:19:53,060 ja? 600 00:19:53,060 --> 00:19:54,280 >> OK, očitno ne. 601 00:19:54,280 --> 00:19:55,860 Ampak to je malo bolje, kajne? 602 00:19:55,860 --> 00:19:57,270 Ker je obvestilo, kaj se je zgodilo. 603 00:19:57,270 --> 00:20:01,749 Vsakič, ko smo izvedli zamenjavo, manjša Število vrsta prodrla na ta način, 604 00:20:01,749 --> 00:20:03,790 in večje število prodrla na ta način, ali pa bomo 605 00:20:03,790 --> 00:20:06,880 začetek rekoč mehurčkih na levo ali mehurčkih v desno. 606 00:20:06,880 --> 00:20:10,080 >> Zdaj, to ni dovolj, saj kvečjemu nekaj morda 607 00:20:10,080 --> 00:20:11,990 se premakne za eno mesto naprej, ali v najslabšem primeru 608 00:20:11,990 --> 00:20:13,880 število morda nadalje premakne za eno mesto. 609 00:20:13,880 --> 00:20:16,369 Torej, veste kaj, ta vrsta od delal precej dobro doslej. 610 00:20:16,369 --> 00:20:17,410 Naj samo poskusite znova. 611 00:20:17,410 --> 00:20:18,880 Dva in štiri, oni so OK. 612 00:20:18,880 --> 00:20:20,180 Štiri in šest, oni so OK. 613 00:20:20,180 --> 00:20:21,790 Šest in ena, v okvari. 614 00:20:21,790 --> 00:20:23,007 Torej, kaj je vaju zamenjali. 615 00:20:23,007 --> 00:20:25,840 In zdaj, opazili problem je se začne, da bi dobili boljše spet malo. 616 00:20:25,840 --> 00:20:27,006 Šest in tri, v okvari. 617 00:20:27,006 --> 00:20:28,100 Naj vaju zamenjali. 618 00:20:28,100 --> 00:20:29,730 Šest in sedem, da si dober. 619 00:20:29,730 --> 00:20:32,230 Sedem in pet, seveda v okvari. 620 00:20:32,230 --> 00:20:33,920 Sedem in osem, v redu. 621 00:20:33,920 --> 00:20:36,470 In zdaj, morda moram storite to še nekajkrat. 622 00:20:36,470 --> 00:20:39,830 In v resnici, mislim zase morda kolikokrat maksimalno 623 00:20:39,830 --> 00:20:41,330 Morda moram hoditi sem in tja? 624 00:20:41,330 --> 00:20:42,390 >> Vrnili se bomo na to. 625 00:20:42,390 --> 00:20:43,700 Torej, dve in štiri so še vedno v redu. 626 00:20:43,700 --> 00:20:44,940 Štiri in eno, nope. 627 00:20:44,940 --> 00:20:45,747 Torej, kaj je swap. 628 00:20:45,747 --> 00:20:47,830 In spet, opazili vizualno ena vrsta mehurčki 629 00:20:47,830 --> 00:20:49,163 na levi, če je treba. 630 00:20:49,163 --> 00:20:50,010 Štiri in tri swap. 631 00:20:50,010 --> 00:20:51,330 Štiri in šest. 632 00:20:51,330 --> 00:20:53,100 Šest in pet swap. 633 00:20:53,100 --> 00:20:53,959 Šest in sedem. 634 00:20:53,959 --> 00:20:55,000 Sedem in osem so dobri. 635 00:20:55,000 --> 00:20:55,500 >> Dobro. 636 00:20:55,500 --> 00:20:58,460 Mi smo dobili še boljši. 637 00:20:58,460 --> 00:20:59,130 Torej, poglejmo. 638 00:20:59,130 --> 00:21:00,940 Zdaj imamo dva in enega. 639 00:21:00,940 --> 00:21:02,520 Seveda, zamenjali. 640 00:21:02,520 --> 00:21:07,520 Dva in tri, tri in štiri, štiri in pet, šest in sedem, sedem in osem. 641 00:21:07,520 --> 00:21:08,020 Dobro. 642 00:21:08,020 --> 00:21:08,730 In veste kaj? 643 00:21:08,730 --> 00:21:11,190 Ker sem naredil eno spremembo tam, Naj narediti eno preverjanje prištevnosti. 644 00:21:11,190 --> 00:21:13,023 Naj gredo vse nazaj na začetek. 645 00:21:13,023 --> 00:21:13,680 V REDU. 646 00:21:13,680 --> 00:21:14,750 Eno, dvo Ja, vidiš? 647 00:21:14,750 --> 00:21:15,870 Nekaj ​​je bilo narobe. 648 00:21:15,870 --> 00:21:18,420 Tri, štiri, pet, šest, sedem, osem. 649 00:21:18,420 --> 00:21:21,920 In v tej zadnji priložnost, so ste zadovoljni z mojim zdaj 650 00:21:21,920 --> 00:21:23,830 ki zahtevajo je urejeno? 651 00:21:23,830 --> 00:21:24,330 V REDU. 652 00:21:24,330 --> 00:21:25,880 Vizualno, to je popolnoma res. 653 00:21:25,880 --> 00:21:28,410 Vendar funkcionalno, kaj se je tudi pravkar zgodilo 654 00:21:28,410 --> 00:21:31,870 V tem zadnjem priložnost, ki vam omogoča Za potrditev, da je ta seznam dejansko 655 00:21:31,870 --> 00:21:32,660 razporejene? 656 00:21:32,660 --> 00:21:34,477 >> Kaj sem naredil ali ne naredil to zadnjo točno? 657 00:21:34,477 --> 00:21:35,810 OBČINSTVO: ni bilo sprememb. 658 00:21:35,810 --> 00:21:36,120 DAVID J. Malan: Oprostite? 659 00:21:36,120 --> 00:21:37,070 OBČINSTVO: nobenih sprememb. 660 00:21:37,070 --> 00:21:38,653 DAVID J. Malan: ni bilo sprememb. 661 00:21:38,653 --> 00:21:41,947 Zato bi bilo neumno od mene, da narediti, da isti algoritem znova 662 00:21:41,947 --> 00:21:43,780 Če nisem, da vsaka spremeni prvič. 663 00:21:43,780 --> 00:21:45,160 In se je stanje ni spremenilo. 664 00:21:45,160 --> 00:21:47,576 Zagotovo ne bom, da bi koli spremeni drugič. 665 00:21:47,576 --> 00:21:49,820 In tako, da je zdaj varno povedati, je seznam razporejene. 666 00:21:49,820 --> 00:21:52,069 >> In res je to sedaj nekaj, kar bomo na splošno 667 00:21:52,069 --> 00:21:56,900 klic mehurček vrste, pri čemer paroma, ponovno popraviti napake, 668 00:21:56,900 --> 00:22:00,210 in spet, in spet, in vam nadaljuj naprej in nazaj, 669 00:22:00,210 --> 00:22:03,370 in naprej in nazaj, dokler vas da takšne zamenjave ne, na kateri točki 670 00:22:03,370 --> 00:22:07,089 ste lahko prepričani, ja končal določitvi vseh napak. 671 00:22:07,089 --> 00:22:08,630 Oglejmo reset in poskusite drug pristop. 672 00:22:08,630 --> 00:22:11,590 Če bi vidva segajo v vrstni red ste bili pred nekaj trenutki, 673 00:22:11,590 --> 00:22:13,780 ki je videti, kot je ta. 674 00:22:13,780 --> 00:22:17,640 Zdaj, vzemimo za pristop, malo več kot izpit knjigo, 675 00:22:17,640 --> 00:22:21,122 s katerim smo bili ves čas izberete črko abecede 676 00:22:21,122 --> 00:22:22,830 da smo nekako želeli da se ukvarjajo z naslednjo. 677 00:22:22,830 --> 00:22:26,420 Mogoče je bila visoka pismo, kot A, ali nizko črko Z. 678 00:22:26,420 --> 00:22:28,170 >> Torej, vsi se je vrnil v tem vrstnem redu. 679 00:22:28,170 --> 00:22:29,800 In sedaj mi je to naredil. 680 00:22:29,800 --> 00:22:34,880 Poglejmo, vem, da sem imel osem številk tukaj. 681 00:22:34,880 --> 00:22:37,410 Grem, da gredo naprej in samo namerno izberite 682 00:22:37,410 --> 00:22:38,520 najmanjši elementi. 683 00:22:38,520 --> 00:22:38,760 Prav? 684 00:22:38,760 --> 00:22:39,801 To se zdi intuitivno preveč. 685 00:22:39,801 --> 00:22:42,560 Zakaj ne najdem najmanjši element, ga dal, kamor spada, 686 00:22:42,560 --> 00:22:45,280 nato pa dobil naslednji najmanjši element, dal je, kamor spada, in ponovite. 687 00:22:45,280 --> 00:22:46,820 >> Ker intuitivno, da bi bilo preveč dela. 688 00:22:46,820 --> 00:22:48,441 Torej štiri, da je precej majhno število. 689 00:22:48,441 --> 00:22:49,940 Grem, da se spomnimo, kje je to. 690 00:22:49,940 --> 00:22:50,523 Počakaj minuto. 691 00:22:50,523 --> 00:22:51,577 Dva manjša. 692 00:22:51,577 --> 00:22:53,910 Naj se zdaj spomnim, kjer dva je, in pozabi na štiri. 693 00:22:53,910 --> 00:22:55,050 Bomo ukvarjajo s tem kasneje. 694 00:22:55,050 --> 00:22:56,460 Šest, me ne zanima. 695 00:22:56,460 --> 00:22:57,810 Osem, jaz ne zanima. 696 00:22:57,810 --> 00:22:59,780 Ena je moja nova majhna številka. 697 00:22:59,780 --> 00:23:01,470 Tako da bom, da se spomnimo, kjer je ena. 698 00:23:01,470 --> 00:23:02,534 Tri, me ne zanima. 699 00:23:02,534 --> 00:23:03,450 Seven, me ne zanima. 700 00:23:03,450 --> 00:23:04,530 Pet, me ne zanima. 701 00:23:04,530 --> 00:23:07,390 >> Torej, ne da bi padli oder letos, 702 00:23:07,390 --> 00:23:09,890 Grem, da zgrabite število one-- in kaj se vam je že ime? 703 00:23:09,890 --> 00:23:10,150 >> ANNAN: Annan. 704 00:23:10,150 --> 00:23:11,220 >> DAVID J. Malan: Annan. 705 00:23:11,220 --> 00:23:13,540 In če mi lahko pridružite na začetek seznama 706 00:23:13,540 --> 00:23:14,870 kaj je dal vam, kamor spadaš. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- kako ti je ime? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. Malan: Stefan je na poti. 710 00:23:18,191 --> 00:23:23,490 Torej, preden Stefan reši to problem, kaj naj storimo? 711 00:23:23,490 --> 00:23:25,412 Kaj naj naredimo z Stefan? 712 00:23:25,412 --> 00:23:27,269 >> OBČINSTVO: [neslišno]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. Malan: OK. 714 00:23:28,060 --> 00:23:28,850 Tako smo lahko storili. 715 00:23:28,850 --> 00:23:31,730 Mi lahko nekako vzeli Stefan in njegov štiri, in samo dal v spremenljivko 716 00:23:31,730 --> 00:23:33,530 in imajo na njej nekaj časa, 717 00:23:33,530 --> 00:23:35,220 s čimer se odpira prostor za eno številko. 718 00:23:35,220 --> 00:23:36,280 In to ni slabo. 719 00:23:36,280 --> 00:23:39,270 Jaz lahko predlagam, zakaj ne smo pravkar dal Stefan tukaj? 720 00:23:39,270 --> 00:23:41,610 Zakaj bi to kršilo eno idej smo začeli 721 00:23:41,610 --> 00:23:44,830 govorim o zadnjem trenutku, prejšnji teden? 722 00:23:44,830 --> 00:23:45,330 Ja? 723 00:23:45,330 --> 00:23:45,740 >> OBČINSTVO: [neslišno]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. Malan: Ni indeks za to. 725 00:23:46,860 --> 00:23:49,735 Če menite, da o tem, res, kot matrika, to je kot negativnega, 726 00:23:49,735 --> 00:23:52,900 tako da ni pomnilnika dejansko tukaj, če je to res matrika, 727 00:23:52,900 --> 00:23:55,090 kot smo izjavil prejšnji teden v predavanju. 728 00:23:55,090 --> 00:23:56,250 Zato tega ne smemo storiti. 729 00:23:56,250 --> 00:23:57,340 Mi lahko ga shranite v spremenljivko. 730 00:23:57,340 --> 00:23:57,820 >> Ali veste, kaj? 731 00:23:57,820 --> 00:23:59,153 Slišal sem, da je nekdo drug jo predlagamo. 732 00:23:59,153 --> 00:24:01,020 Kaj lahko storimo z Stefan? 733 00:24:01,020 --> 00:24:03,770 Zakaj ne bi samo ga izselijo in ga postavil nad tem, kje je bil številka ena. 734 00:24:03,770 --> 00:24:05,170 Torej, če želite iti tja. 735 00:24:05,170 --> 00:24:07,300 In res je to zelo dobra rešitev. 736 00:24:07,300 --> 00:24:10,480 Zdaj pa na eni strani, sem imel nekako made problem slabše. 737 00:24:10,480 --> 00:24:13,650 Štiri je zdaj dlje od koder bi moralo biti. 738 00:24:13,650 --> 00:24:14,900 Moralo bi biti proti temu polovico. 739 00:24:14,900 --> 00:24:16,100 >> Ampak veš kaj? 740 00:24:16,100 --> 00:24:17,630 To bi lahko bila slaba sreča. 741 00:24:17,630 --> 00:24:18,822 Morda številka osem je bilo tukaj. 742 00:24:18,822 --> 00:24:20,530 In tako, mogoče mi bi gotten srečo, 743 00:24:20,530 --> 00:24:22,460 in potisnil osem bližje koncu. 744 00:24:22,460 --> 00:24:24,710 Torej, na koncu dneva, Nekako vsi povprečja ven. 745 00:24:24,710 --> 00:24:26,085 Mi ne potrebujemo približno štiri skrbi. 746 00:24:26,085 --> 00:24:29,400 Mene zanima zdaj je izbiro najmanjši element. 747 00:24:29,400 --> 00:24:32,030 >> In zdaj, kaj bom storiti je, da pozabi številka ena 748 00:24:32,030 --> 00:24:35,160 trajno, ker vem, da je seznam za mano je zdaj razporejene. 749 00:24:35,160 --> 00:24:36,720 Torej moj seznam je bil prej velikosti osem. 750 00:24:36,720 --> 00:24:37,720 Zdaj, to je velikosti sedem. 751 00:24:37,720 --> 00:24:40,340 Torej, moj problem je pridobivanje manjši, čeprav linearno. 752 00:24:40,340 --> 00:24:43,022 Torej sedaj, bom izberite Sedanji najmanjši element, dva. 753 00:24:43,022 --> 00:24:46,520 Šest, osem, štiri, tri, sedem, pet. 754 00:24:46,520 --> 00:24:47,770 To je bil najmanjši element. 755 00:24:47,770 --> 00:24:49,416 Torej, kaj sem storila with-- kaj vam je že ime? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. Malan: Joseph? 758 00:24:50,085 --> 00:24:52,000 Bomo zapustili Jožefa v mestu. 759 00:24:52,000 --> 00:24:54,842 Zdaj pa grem, da se pretvarjamo da ti fantje are-- dobro, 760 00:24:54,842 --> 00:24:56,550 Vem, da ti dve so že razporejene. 761 00:24:56,550 --> 00:24:58,424 Osredotočimo se zdaj na Preostanek seznama. 762 00:24:58,424 --> 00:25:00,080 Šest je trenutno najmanjši. 763 00:25:00,080 --> 00:25:01,190 Osem je večji. 764 00:25:01,190 --> 00:25:02,970 Štiri je zdaj trenutna najmanjša. 765 00:25:02,970 --> 00:25:04,762 Tri je zdaj trenutna najmanjša. 766 00:25:04,762 --> 00:25:07,720 In zdaj, bom izbrati tri, kdo is-- kaj je vaše ime? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. Malan: Serena, če bi lahko zgrabite vašo številko in swap with-- 769 00:25:10,620 --> 00:25:11,550 KALSANG: Kalsang. 770 00:25:11,550 --> 00:25:12,940 DAVID J. Malan: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Pridi nazaj, in smo bodo zamenjali tiste dva. 772 00:25:15,220 --> 00:25:17,360 In zdaj, kaj je dal to na avtopilot. 773 00:25:17,360 --> 00:25:21,589 Jaz bom šel in ga pustite, da vas fantje da izberete naslednjo najmanjšo elemente. 774 00:25:21,589 --> 00:25:22,380 Dun, dun, dun, dun. 775 00:25:22,380 --> 00:25:24,560 Številka štiri, kaj morate storiti? 776 00:25:24,560 --> 00:25:26,261 Odlično. 777 00:25:26,261 --> 00:25:27,760 Zdaj pa grem, da bi drugo sredino. 778 00:25:27,760 --> 00:25:28,590 Dun, dun, dun, dun. 779 00:25:28,590 --> 00:25:31,465 Vidim, pet je naslednji najmanjši. 780 00:25:31,465 --> 00:25:32,840 Zdaj bom vzeti drugo sredino. 781 00:25:32,840 --> 00:25:33,631 Dun, dun, dun, dun. 782 00:25:33,631 --> 00:25:34,880 Šest je najmanjši. 783 00:25:34,880 --> 00:25:35,520 Dobro. 784 00:25:35,520 --> 00:25:36,585 Sedem je najmanjši. 785 00:25:36,585 --> 00:25:37,085 Ni sprememb. 786 00:25:37,085 --> 00:25:38,630 Osem je najmanjši. 787 00:25:38,630 --> 00:25:39,170 Končano. 788 00:25:39,170 --> 00:25:43,900 >> Torej, kaj smo pravkar storili s ponavljajočim selekcioniranje enega elementa za drugim 789 00:25:43,900 --> 00:25:47,230 je izvajati nekaj, da smo dogaja, da formalizira kot izbirni vrste. 790 00:25:47,230 --> 00:25:49,120 In to je morda celo enostavneje razložiti, 791 00:25:49,120 --> 00:25:51,310 s tem, da dobesedno vse vas želite storiti, je samo vztrajati 792 00:25:51,310 --> 00:25:54,700 gre naprej in nazaj po seznamu izbiro, naslednji najmanjši element, 793 00:25:54,700 --> 00:25:55,720 dokler ste končali. 794 00:25:55,720 --> 00:25:58,650 >> Tako da je še lažje, morda intuitivno, kot zadnji. 795 00:25:58,650 --> 00:26:00,020 Poskusimo še zadnjič eno. 796 00:26:00,020 --> 00:26:03,060 Če bi vidva sami ponastaviti v naslednjih položajih 797 00:26:03,060 --> 00:26:08,600 eno končno čas, da vidimo, če ne moremo zdaj formalizirati en drug pristop. 798 00:26:08,600 --> 00:26:12,857 Pravzaprav bi nekdo tam rad predlagal 799 00:26:12,857 --> 00:26:14,440 kako še lahko gremo o tem? 800 00:26:14,440 --> 00:26:17,439 Brez premetavala iz Buzzwords ali vrste odgovorov, ki so že znane, 801 00:26:17,439 --> 00:26:19,689 samo intuitivno, kaj lahko storimo? 802 00:26:19,689 --> 00:26:21,635 >> OBČINSTVO: [neslišno]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. Malan: Ja. 804 00:26:22,510 --> 00:26:24,620 Torej je bil odlični intuicija tam. 805 00:26:24,620 --> 00:26:28,020 Dobre stvari se zdi, da doslej zgodilo v računalništvu, ko delimo 806 00:26:28,020 --> 00:26:30,832 in osvojiti problem delitve je na pol in pol in pol. 807 00:26:30,832 --> 00:26:32,540 In tako v resnici smo lahko začnete, da to storim. 808 00:26:32,540 --> 00:26:35,754 In v resnici, da se dogaja, da se bomo glej, eden od naših najboljših rešitev še ni. 809 00:26:35,754 --> 00:26:37,420 Ampak kaj je prišel nazaj, da je pred dolgo. 810 00:26:37,420 --> 00:26:40,500 Dejstvo je, da bomo storili da je malo kasneje ta teden. 811 00:26:40,500 --> 00:26:42,180 Kaj še lahko storimo, da bi rešila to? 812 00:26:42,180 --> 00:26:44,647 Torej vsi tukaj v navidezno naključnem vrstnem redu. 813 00:26:44,647 --> 00:26:45,230 Veš kaj? 814 00:26:45,230 --> 00:26:48,320 Namesto da gredo naprej in nazaj, sem in tja, in nazaj 815 00:26:48,320 --> 00:26:50,624 vsakič, ta občutek Delam veliko hoje. 816 00:26:50,624 --> 00:26:52,790 Zakaj ne samo začeti na začetek seznama 817 00:26:52,790 --> 00:26:54,960 in samo dal štiri, kamor spada? 818 00:26:54,960 --> 00:26:59,680 Zato mi dovolite, prevzeti za trenutek, da moj seznam je samo to prvi element. 819 00:26:59,680 --> 00:27:04,937 Je štiri razporejene v tem trenutku, če je vse, kar sem mar je vse tukaj? 820 00:27:04,937 --> 00:27:06,520 To je nekako površno res, kajne? 821 00:27:06,520 --> 00:27:10,000 Tako kot seznam, ki vsebuje eno številko, in da je številka štiri je očitno razporejene. 822 00:27:10,000 --> 00:27:13,070 >> Torej, povej mi samo določi, da je ta seznam razporejene. 823 00:27:13,070 --> 00:27:15,090 Ampak zdaj imam preostanek tega seznama. 824 00:27:15,090 --> 00:27:17,240 Torej, zdaj, jaz srečati dva. 825 00:27:17,240 --> 00:27:21,690 Kje dva očitno pripadajo glede na štiri? 826 00:27:21,690 --> 00:27:22,580 Pred štirimi. 827 00:27:22,580 --> 00:27:23,862 Torej, kaj lahko storim tukaj? 828 00:27:23,862 --> 00:27:24,820 Kakšen je že ime? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. Malan: Joseph, če bi lahko korak nazaj 831 00:27:26,030 --> 00:27:27,790 za trenutek s svojo številko. 832 00:27:27,790 --> 00:27:31,130 In zdaj, kaj naj Stefan tukaj storiti? 833 00:27:31,130 --> 00:27:33,720 Oglejmo premik Stefana tukaj. 834 00:27:33,720 --> 00:27:35,520 In zdaj, kaj Joseph pridejo sem. 835 00:27:35,520 --> 00:27:39,660 In zdaj, mi zatrjujejo, da vse, tukaj je razvrščen. 836 00:27:39,660 --> 00:27:42,474 Torej, podoben rezultat, vendar bistveno drugačen pristop. 837 00:27:42,474 --> 00:27:44,140 Nisem niti pogledal, kaj je tam dol. 838 00:27:44,140 --> 00:27:46,310 Pravkar sem voditi ob elemente kot oni Izročil mi, 839 00:27:46,310 --> 00:27:47,240 in se z njimi spopasti. 840 00:27:47,240 --> 00:27:48,330 >> Torej sedaj, vidim številko šest. 841 00:27:48,330 --> 00:27:51,110 Kje številka šest pripada? 842 00:27:51,110 --> 00:27:53,250 Imamo dve, štiri, šest. 843 00:27:53,250 --> 00:27:54,800 Točno kje je zdaj. 844 00:27:54,800 --> 00:27:57,750 Torej, pustimo, da sam, in zdaj trdijo, da je ta del seznama 845 00:27:57,750 --> 00:27:58,772 je zdaj razporejene. 846 00:27:58,772 --> 00:28:01,230 In tako je to v osnovi meni razlikuje po tem, da sem samo 847 00:28:01,230 --> 00:28:05,230 premikanje po seznamu tukaj linearno, in jaz nikoli podvojitev nazaj. 848 00:28:05,230 --> 00:28:05,730 Da. 849 00:28:05,730 --> 00:28:06,230 V redu. 850 00:28:06,230 --> 00:28:08,190 Torej osem, kam spadaš? 851 00:28:08,190 --> 00:28:08,730 Točno tukaj. 852 00:28:08,730 --> 00:28:09,310 Popolna. 853 00:28:09,310 --> 00:28:10,210 Torej, zdaj, one. 854 00:28:10,210 --> 00:28:10,900 Uh-oh. 855 00:28:10,900 --> 00:28:13,010 To se počuti, kot da je bo drag. 856 00:28:13,010 --> 00:28:15,690 Sedaj v prejšnjem algoritem, Pravkar sem zamenjal ljudi. 857 00:28:15,690 --> 00:28:18,648 Torej, jaz bi mu dal vso pot na začetek, nato pa se preselil Jožefa. 858 00:28:18,648 --> 00:28:21,450 Ampak, če sem premakniti Jožefa, zdaj kaj se dogaja, da se motim? 859 00:28:21,450 --> 00:28:24,250 >> Zdaj, Sem nekako undone-- Sem sprejeti en korak naprej in nato 860 00:28:24,250 --> 00:28:26,300 en korak nazaj, ker zdaj Joseph bi bila v okvari. 861 00:28:26,300 --> 00:28:26,830 Torej, kaj je to. 862 00:28:26,830 --> 00:28:29,150 Če bi lahko številka ena in korak nazaj za trenutek. 863 00:28:29,150 --> 00:28:30,490 Kako lahko put-- kaj vam je že ime? 864 00:28:30,490 --> 00:28:31,130 >> ANNAN: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. Malan: Annan v mestu? 866 00:28:32,610 --> 00:28:36,091 Kaj se mora zgoditi v zvezi z na dve, štiri, šest, osem? 867 00:28:36,091 --> 00:28:37,570 Vsi morali preusmeriti. 868 00:28:37,570 --> 00:28:42,590 Torej, če osem bi želeli preusmeriti najprej, nato pa šest, nato štiri, nato pa dve. 869 00:28:42,590 --> 00:28:45,380 In potem Annan, če bi radi pridejo sem, dobro. 870 00:28:45,380 --> 00:28:47,760 Ampak tukaj, ki smo jih pravkar vrsta plačala ceno 871 00:28:47,760 --> 00:28:49,510 v neki določeni točki v algoritmu. 872 00:28:49,510 --> 00:28:52,550 Ker zadnjem času z izborom razvrščanje, in celo mehurček razvrščanje, 873 00:28:52,550 --> 00:28:54,700 Jaz sem hodil nazaj in naprej, naprej in nazaj, 874 00:28:54,700 --> 00:28:58,360 ki je vsekakor sešteva čas pametno in dobesedno postopno. 875 00:28:58,360 --> 00:29:00,660 >> Vstavljanje razvrščanje, sprva pogled, izgleda, da je 876 00:29:00,660 --> 00:29:05,150 super pametnejši, s tem, da sem samo tako počasen, postopen napredek, 877 00:29:05,150 --> 00:29:07,120 ampak ne bom to naprej in nazaj. 878 00:29:07,120 --> 00:29:09,410 Ampak, če je nekdo res od naročila, obvestila 879 00:29:09,410 --> 00:29:10,840 vse delo sem moral storiti. 880 00:29:10,840 --> 00:29:14,750 Sem imel, da se premaknete polovica seznama samo da bi naredili prostor za številko ena. 881 00:29:14,750 --> 00:29:16,790 Torej, to je isti znesek dela doslej ga 882 00:29:16,790 --> 00:29:18,690 meni, samo drugačna vrsta dela. 883 00:29:18,690 --> 00:29:19,370 >> Poglejmo naprej. 884 00:29:19,370 --> 00:29:22,657 Zdaj vemo, da je vsakdo med eno in osem so razporejene. 885 00:29:22,657 --> 00:29:23,740 Tukaj imam številko tri. 886 00:29:23,740 --> 00:29:25,864 Če vam je všeč, da poberem številka tri, korak nazaj eno. 887 00:29:25,864 --> 00:29:28,260 In kaj vi morate storiti? 888 00:29:28,260 --> 00:29:28,760 Ja. 889 00:29:28,760 --> 00:29:33,070 Torej, to je še ena, dva, tri korake. 890 00:29:33,070 --> 00:29:36,010 Tri enote časa, da je samo strošek mi, tako da tri Sedaj lahko fit. 891 00:29:36,010 --> 00:29:37,460 Končno, sedem. 892 00:29:37,460 --> 00:29:39,730 >> Pojdimo naprej in imajo boste naredili korak nazaj. 893 00:29:39,730 --> 00:29:42,780 To je samo nas bo stalo ena enota časa, ampak to je v redu. 894 00:29:42,780 --> 00:29:44,170 In zdaj, pet se dogaja, da je malo dražja. 895 00:29:44,170 --> 00:29:45,340 Če želite korak nazaj. 896 00:29:45,340 --> 00:29:48,380 Moramo se premakniti osem, sedem in šest. 897 00:29:48,380 --> 00:29:50,749 In potem se vsi zdaj razporejene. 898 00:29:50,749 --> 00:29:52,290 Tako velik roko našim prostovoljcem tukaj. 899 00:29:52,290 --> 00:29:53,554 Najlepša hvala. 900 00:29:53,554 --> 00:29:56,220 >> [Aplavz] 901 00:29:56,220 --> 00:29:56,860 >> Hvala vsem. 902 00:29:56,860 --> 00:29:57,520 Hvala vsem. 903 00:29:57,520 --> 00:30:02,940 Torej, kaj je zdaj vidim, kako dragi vsi so bili. 904 00:30:02,940 --> 00:30:06,210 Oglejmo si morda Najpreprostejša med njimi, mehurček nekako. 905 00:30:06,210 --> 00:30:09,950 In rečem najenostavnejši, samo zato, ker ga lahko rešili pohlepno jih pravkar 906 00:30:09,950 --> 00:30:11,660 popraviti parna problem tukaj. 907 00:30:11,660 --> 00:30:13,720 Fix parna težave tu, znova in znova 908 00:30:13,720 --> 00:30:17,680 in spet ponovimo toliko krat, kot si dejansko morali. 909 00:30:17,680 --> 00:30:21,050 >> Tako se izkaže, da z mehurček vrste, dobro, 910 00:30:21,050 --> 00:30:25,820 koliko korakov moram prevzeti prvi akcije tega algoritem? 911 00:30:25,820 --> 00:30:30,850 Jaz bi take-- dajmo see-- eno, dva, tri, štiri, pet, šest, sedem. 912 00:30:30,850 --> 00:30:32,190 In tam je tukaj osem elementov. 913 00:30:32,190 --> 00:30:35,280 Torej, to je, kot n minus 1 korakov do dobili od začetka seznama 914 00:30:35,280 --> 00:30:36,380 na koncu seznama. 915 00:30:36,380 --> 00:30:41,350 >> Toda z izbirnim vrste, se spomni, da sem znova izbiri elemente 916 00:30:41,350 --> 00:30:44,590 in spet, da je najmanjša, Jo bom v mestu, 917 00:30:44,590 --> 00:30:46,616 potem pa nisem videti spet za mano. 918 00:30:46,616 --> 00:30:49,490 Zato mislim, da je malo bolj jasno Takrat prvič, bom morda 919 00:30:49,490 --> 00:30:52,680 morali sprejeti vse n minus 1 korake najti najmanjši element. 920 00:30:52,680 --> 00:30:55,920 Potem sem jih dal v mestu, in jaz izselijo kdor je bil tu že prej. 921 00:30:55,920 --> 00:30:57,500 >> Ampak potem nimam za da gledamo na ta element, 922 00:30:57,500 --> 00:30:59,040 ker vem, da je že najmanjša. 923 00:30:59,040 --> 00:31:01,581 Torej, zdaj sem lahko ogledate na samo sedem elementi, nato šest elementov, 924 00:31:01,581 --> 00:31:03,290 nato pet elementov, nato štirje elementi. 925 00:31:03,290 --> 00:31:06,900 In tako matematično, če je n število elementov ali številk 926 00:31:06,900 --> 00:31:11,990 da smo začeli, si lahko predstavljate da je to isto kot n minus 1, 927 00:31:11,990 --> 00:31:14,250 plus n minus 2 koraka, plus n minus 3 koraki, 928 00:31:14,250 --> 00:31:16,780 plus n minus 4 koraki, vse pot navzdol na samo enem koraku. 929 00:31:16,780 --> 00:31:18,160 In jaz sem na moji zadnji osebo. 930 00:31:18,160 --> 00:31:20,650 >> In če se spomnimo, da je veliko od stats knjige ali math knjig 931 00:31:20,650 --> 00:31:24,730 imajo te formule, na Trde platnice nazaj ali pred njimi, 932 00:31:24,730 --> 00:31:27,690 se izkaže, da te serije lahko izrazimo bolj preprosto 933 00:31:27,690 --> 00:31:28,857 kot n-krat n minus 1 več kot 2. 934 00:31:28,857 --> 00:31:31,273 In to je v redu, če to ni v ospredju svojega uma. 935 00:31:31,273 --> 00:31:32,420 Ampak to je res. 936 00:31:32,420 --> 00:31:34,449 To je samo enostavnejši način pisanja. 937 00:31:34,449 --> 00:31:36,240 In potem, če menite, nazaj v osnovni šoli, 938 00:31:36,240 --> 00:31:38,698 ko ste šele začeli množenjem stvari, je to seveda, 939 00:31:38,698 --> 00:31:41,820 je le n kvadrat minus n deljeno z 2. 940 00:31:41,820 --> 00:31:44,772 Vse sem naredil, je razširila izrazi tam. 941 00:31:44,772 --> 00:31:46,730 In tako da je Reportaža to malo drugače. 942 00:31:46,730 --> 00:31:49,780 To je n kvadrat deljeno z 2 minus n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Torej še enkrat, jaz sem samo nekako uporabe nekateri aritmetična pravila obstajajo. 944 00:31:53,270 --> 00:31:57,140 Ampak obvestilo, da zdaj največji izraz V tem izrazu, tako rekoč, 945 00:31:57,140 --> 00:31:58,540 je, da n kvadrat. 946 00:31:58,540 --> 00:32:02,910 Torej, ja, to je n kvadrat deljeno s 2, minus n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Vendar na splošno, če je n bo veliko vrednost, 948 00:32:05,080 --> 00:32:08,740 Bom trdijo, da n kvadrat se bo prevladujoči faktor. 949 00:32:08,740 --> 00:32:10,490 To je le, da bo treba večji prispeva 950 00:32:10,490 --> 00:32:12,877 na število korakov od n / 2. 951 00:32:12,877 --> 00:32:13,960 Torej, kaj mislim s tem? 952 00:32:13,960 --> 00:32:16,795 Poskusimo preprost primer, celo čeprav je math dobi malo velik. 953 00:32:16,795 --> 00:32:20,210 >> Torej Predvidevam smo imeli 1 milijon ljudi na odru, ali 1 milijon stvari 954 00:32:20,210 --> 00:32:21,320 ki ga želimo rešiti. 955 00:32:21,320 --> 00:32:23,730 Oglejmo priključite milijon v natanko to formulo 956 00:32:23,730 --> 00:32:27,230 da vidite, koliko korakov je potrebnih skupaj razvrstiti milijon elemente uporabi recimo, 957 00:32:27,230 --> 00:32:28,560 Izbor vrste. 958 00:32:28,560 --> 00:32:30,760 >> Tako bi imeli isto formulo kot prej. 959 00:32:30,760 --> 00:32:34,120 Želel priključite milijon, tako da sem dobil milijon na kvadrat deljeno z 2, 960 00:32:34,120 --> 00:32:35,990 minus milijona deljeno z 2. 961 00:32:35,990 --> 00:32:40,180 Če naredim to math vnaprej Tu imamo 500 milijard 962 00:32:40,180 --> 00:32:47,460 minus 500.000, kar nam daje 499999500000, 963 00:32:47,460 --> 00:32:49,270 ki je precej darn velik. 964 00:32:49,270 --> 00:32:54,370 >> V bistvu, če primerjate zdaj 499000000000, 999000000, 965 00:32:54,370 --> 00:33:01,210 500.000 zoper naše prvotne vrednosti, 500 milijard, to je tako prekleto blizu. 966 00:33:01,210 --> 00:33:06,850 Prav? n kvadrat deljeno z 2 daje us-- ali bolje, n kvadrat deljeno z 2 967 00:33:06,850 --> 00:33:08,370 nam je dal 500 milijard. 968 00:33:08,370 --> 00:33:13,510 To je precej darn blizu da 499,999,500,000, 969 00:33:13,510 --> 00:33:17,970 kar pomeni, da se odšteje off 500.000, ali bolj splošno, odštevanjem off 970 00:33:17,970 --> 00:33:20,010 n kvadrat, ni res velik posel. 971 00:33:20,010 --> 00:33:22,490 N kvadrat si ti številke rastejo zelo hitro. 972 00:33:22,490 --> 00:33:25,790 >> Zdaj, da je to pomembno le, če kot mi, kot računalniški znanstveniki, 973 00:33:25,790 --> 00:33:29,350 se na splošno ne bo toliko skrbi o nianse teh formul 974 00:33:29,350 --> 00:33:31,400 in točno tisto, kar natančnih odgovorov. 975 00:33:31,400 --> 00:33:33,390 Želimo le, da je vseeno, veš kaj? 976 00:33:33,390 --> 00:33:37,810 Ob koncu dneva, ta formula je reda n razčetverjen. 977 00:33:37,810 --> 00:33:39,350 >> Ja, mi delimo z 2 noter. 978 00:33:39,350 --> 00:33:41,360 Ja, mi odšteje off n minus 2. 979 00:33:41,360 --> 00:33:46,860 Toda na koncu dneva, izraz da nas res boli in nas stane 980 00:33:46,860 --> 00:33:48,995 veliko stopnic je, da izraz kvadrat. 981 00:33:48,995 --> 00:33:51,370 In kaj računalniški znanstvenik se dogaja, da na splošno storiti 982 00:33:51,370 --> 00:33:54,160 se prezreti vse tiste manjše pogoji naročilo, 983 00:33:54,160 --> 00:33:56,900 in samo pogled na tisto, ki največ prispeva k stroškom. 984 00:33:56,900 --> 00:34:00,530 >> In to je lepo, ker smo lahko zdaj govori v veliko večji splošnosti 985 00:34:00,530 --> 00:34:02,470 o algoritmi, in jih lahko primerja. 986 00:34:02,470 --> 00:34:04,550 In dejstvo, da sem uporabo te O namerno. 987 00:34:04,550 --> 00:34:06,680 Ko sem rekel, o vrstnem redu o, sem posebej 988 00:34:06,680 --> 00:34:09,560 ki se nanaša na nekaj, imenovani veliki O. In big O 989 00:34:09,560 --> 00:34:14,090 je zapis da računalniški znanstvenik uporablja za opis 990 00:34:14,090 --> 00:34:16,710 zgornja vezan na nekaj. 991 00:34:16,710 --> 00:34:21,150 >> Torej, če ste rekli, da je algoritem je v velikem O n kvadrat, 992 00:34:21,150 --> 00:34:23,380 kot sem predlagal samo Trenutek nazaj, da sredstva 993 00:34:23,380 --> 00:34:27,710 da glede na njeno delovanje čas ali njeno učinkovitost, 994 00:34:27,710 --> 00:34:30,090 je potrebno na naročilo n kvadrat korake. 995 00:34:30,090 --> 00:34:31,420 Morda več, morda manj. 996 00:34:31,420 --> 00:34:33,435 Vendar je na red n kvadrat. 997 00:34:33,435 --> 00:34:34,560 In, da je zgornja meja. 998 00:34:34,560 --> 00:34:36,530 To se ne bo bolj boleče kot to. 999 00:34:36,530 --> 00:34:40,800 To se ne bo n kubikov ali 2 v N, ali nekaj veliko večjega. 1000 00:34:40,800 --> 00:34:43,800 To je zgornja meja na vse, kar je ta strošek. 1001 00:34:43,800 --> 00:34:46,150 Torej, glede na to, kaj je upoštevati le nekaj primerov. 1002 00:34:46,150 --> 00:34:49,820 In to je samo končen seznam zelo pogosti tekoči časi 1003 00:34:49,820 --> 00:34:52,870 za algoritme, ki je pomenilo, da je ponazarjajo nekatere stvari, ki smo jih 1004 00:34:52,870 --> 00:34:53,600 že videli. 1005 00:34:53,600 --> 00:34:58,060 >> Tako na primer, v primeru Izbor vrste, kaj jaz tukaj trdijo, 1006 00:34:58,060 --> 00:35:02,250 je ta izbor Razvrsti je tek Čas je za vrstni red n kvadrat. 1007 00:35:02,250 --> 00:35:06,260 V najslabšem primeru, bom imela cel kup naključnih števil tukaj. 1008 00:35:06,260 --> 00:35:08,600 In kot smo videli matematično, če hodi 1009 00:35:08,600 --> 00:35:11,310 po seznamu, skozi seznam, da izberete naslednjo manjšo 1010 00:35:11,310 --> 00:35:14,410 znova in znova element, če I dejansko zapišite vse korake 1011 00:35:14,410 --> 00:35:18,750 Vzela bom, kot sem predlagal formulaically pred tem, to je o vrstnem redu n kvadrat 1012 00:35:18,750 --> 00:35:20,370 koraki, da sem jemljejo. 1013 00:35:20,370 --> 00:35:24,520 >> In se izkaže, da je mehurček razvrščanje in vstavljanje sortiranje 1014 00:35:24,520 --> 00:35:27,370 so prav tako počasi v najslabšem primeru. 1015 00:35:27,370 --> 00:35:32,040 Razmislite, na primer, vstavljanje razvrščanje, zelo zadnja algoritem smo ga obravnavali, 1016 00:35:32,040 --> 00:35:35,500 ki je imel nam pogled na elementu, in ga nato vstavite, kamor spada. 1017 00:35:35,500 --> 00:35:38,720 In potem smo pogledal na naslednji element, in jo vstavili, kamor spada. 1018 00:35:38,720 --> 00:35:40,990 >> Tako menijo najboljši možni scenarij. 1019 00:35:40,990 --> 00:35:45,590 Recimo, da sem moji prostovoljci line up dobesedno, kot je ta, ena do osem, 1020 00:35:45,590 --> 00:35:47,440 že razporejene. 1021 00:35:47,440 --> 00:35:51,300 Koliko korakov je vstavljanje vrste bo trajalo, da razvrstite osem ljudi, 1022 00:35:51,300 --> 00:35:55,640 če pridejo na odru videti takole? 1023 00:35:55,640 --> 00:35:57,410 >> Osem ljudi je že urejeno. 1024 00:35:57,410 --> 00:35:58,760 In uporabljam vstavljanje vrste. 1025 00:35:58,760 --> 00:36:02,180 Ta zadnji algoritmov. 1026 00:36:02,180 --> 00:36:03,640 No, dajmo reenact resnično hitro. 1027 00:36:03,640 --> 00:36:05,504 Torej, če začnem tukaj, vidim enega. 1028 00:36:05,504 --> 00:36:06,420 Kje nekdo pripada? 1029 00:36:06,420 --> 00:36:07,730 Spada tukaj. 1030 00:36:07,730 --> 00:36:08,330 Vidim dva. 1031 00:36:08,330 --> 00:36:09,660 Kje dve pripadajo? 1032 00:36:09,660 --> 00:36:10,260 Točno tukaj. 1033 00:36:10,260 --> 00:36:10,900 Vidim tri. 1034 00:36:10,900 --> 00:36:11,920 Kje tri pripada? 1035 00:36:11,920 --> 00:36:12,480 Točno tukaj. 1036 00:36:12,480 --> 00:36:13,100 >> Vidim štiri. 1037 00:36:13,100 --> 00:36:13,600 Točno tukaj. 1038 00:36:13,600 --> 00:36:15,660 Pet, šest, sedem, osem. 1039 00:36:15,660 --> 00:36:17,320 Nobenega razloga ni, da se ponavljam. 1040 00:36:17,320 --> 00:36:21,260 In tako, koliko korakov je, da v smislu n? 1041 00:36:21,260 --> 00:36:23,870 To je velikostnega reda n koraki, kajne? n minus 1. 1042 00:36:23,870 --> 00:36:27,567 Ampak sem vzel linearno številko stopnic, in zdaj sem naredil. 1043 00:36:27,567 --> 00:36:28,900 Torej, to je najboljši primer, čeprav. 1044 00:36:28,900 --> 00:36:29,983 Kaj najslabšem primeru? 1045 00:36:29,983 --> 00:36:32,730 Kaj osem je bilo tam, in sedem bili tam dol, 1046 00:36:32,730 --> 00:36:35,840 in ena in dva sta tukaj, tako da so seznam resnično obrnil? 1047 00:36:35,840 --> 00:36:38,300 >> No, kaj se dogaja v resnici če je to število? 1048 00:36:38,300 --> 00:36:41,300 In bomo naredili le nekaj primerov. 1049 00:36:41,300 --> 00:36:49,300 Kaj pa, če, seveda, številka osem je tu, in number-- Ops. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Pa kaj, če dejansko število osem je vso pot tja, 1052 00:36:56,430 --> 00:36:57,790 in sem s pomočjo vstavljanja vrste? 1053 00:36:57,790 --> 00:36:58,290 >> V REDU. 1054 00:36:58,290 --> 00:37:00,280 Trdim, v trenutku, ko je na mestu. 1055 00:37:00,280 --> 00:37:03,152 Toda zdaj, seven-- kje sedem iti? 1056 00:37:03,152 --> 00:37:04,360 Seveda gre tukaj. 1057 00:37:04,360 --> 00:37:06,760 Tako da sem moral premakniti osem več kot enem mestu. 1058 00:37:06,760 --> 00:37:08,554 Zdaj šest, kjer ne gre? 1059 00:37:08,554 --> 00:37:09,220 No, v redu. 1060 00:37:09,220 --> 00:37:13,150 Zdaj pa moram premakniti osem več kraj in sedem več kot v mestu, 1061 00:37:13,150 --> 00:37:14,440 in potem sem Pljuskanje navzdol šest. 1062 00:37:14,440 --> 00:37:16,870 >> Torej prvič, je strošek me en korak popraviti stvari, 1063 00:37:16,870 --> 00:37:18,570 potem me to stalo dva koraka popraviti stvari. 1064 00:37:18,570 --> 00:37:20,370 Koliko korakov je bo trajalo, da se določi 1065 00:37:20,370 --> 00:37:22,720 Stvari bi dal pet na pravem mestu? 1066 00:37:22,720 --> 00:37:23,340 Tri. 1067 00:37:23,340 --> 00:37:29,520 Ker zdaj moram premakniti en, dva, tri. 1068 00:37:29,520 --> 00:37:32,430 Koliko korakov je bo trajalo postaviti štiri na pravem mestu? 1069 00:37:32,430 --> 00:37:36,040 4 plus 5, plus 6 plus 7. 1070 00:37:36,040 --> 00:37:40,260 >> In tako je matematično enaka kar smo opisali v izbirnem vrste. 1071 00:37:40,260 --> 00:37:42,130 Imamo to serijo da je samo povečuje. 1072 00:37:42,130 --> 00:37:45,650 1 plus 2 plus 3 plus 4, ali nasprotno, 7 plus 6 1073 00:37:45,650 --> 00:37:52,610 plus 5 plus 4 sešteje za današnjo namene, o vrstnem redu n kvadrat. 1074 00:37:52,610 --> 00:37:57,640 >> Zato mi dovolite, določajo tudi, da bubble vrsta je tudi v n kvadrat. 1075 00:37:57,640 --> 00:38:01,340 Ker z mehurček vrste, vsak ko sem šel skozi seznam, 1076 00:38:01,340 --> 00:38:03,100 Jaz sem ob približno koliko korakov? 1077 00:38:03,100 --> 00:38:06,260 Vsakič, ko sem dobesedno hoje od tam do tam? 1078 00:38:06,260 --> 00:38:07,960 Približno n koraki. 1079 00:38:07,960 --> 00:38:12,650 Ampak kolikokrat sem lahko morali iti skozi seznam? 1080 00:38:12,650 --> 00:38:13,920 >> No, v grobem n čas. 1081 00:38:13,920 --> 00:38:15,680 Mogoče n minus 1, vendar približno n krat. 1082 00:38:15,680 --> 00:38:16,430 No, zakaj je to? 1083 00:38:16,430 --> 00:38:19,560 No, z mehurček vrste, če začnemo z mehurček vrste, 1084 00:38:19,560 --> 00:38:23,570 s seznama v najslabši možni Položaj, ki je spet v celoti 1085 00:38:23,570 --> 00:38:25,550 nazaj, kaj se bo zgodilo? 1086 00:38:25,550 --> 00:38:28,830 Sem šel skozi seznam in število eden pripada vso pot tja. 1087 00:38:28,830 --> 00:38:33,280 >> Ampak s mehurček vrste, kako daleč pa eno premaknete na mojem prvem prehodu skozi seznamu? 1088 00:38:33,280 --> 00:38:36,620 Koliko lise pa je dobil bližje na pravem mestu? 1089 00:38:36,620 --> 00:38:37,240 Samo en. 1090 00:38:37,240 --> 00:38:40,281 Torej, če vas nekako razlog skozi to, vsakič preko tega algoritma, 1091 00:38:40,281 --> 00:38:41,880 Ob približno n korakov Davidovi. 1092 00:38:41,880 --> 00:38:44,940 Toda koliko vozovnice skozi seznam je to 1093 00:38:44,940 --> 00:38:49,060 bo trajalo za eno mehurček levo, kamor spada? 1094 00:38:49,060 --> 00:38:51,840 >> Ima, da se premaknete, kot so, n prostori ta način. 1095 00:38:51,840 --> 00:38:57,960 Torej samo narediti sortiranje seznama, Moram hoditi sem in tja n-krat. 1096 00:38:57,960 --> 00:39:01,540 In vsakič, ko sem gledaš n elementov. 1097 00:39:01,540 --> 00:39:05,410 Stori n stvari, n-krat na vrstni red n kvadrat. 1098 00:39:05,410 --> 00:39:07,220 >> Zdaj pa bomo videli v nekaj od hlače, ki 1099 00:39:07,220 --> 00:39:10,440 so vgrajeni v CS50 je naslednji problem nastavljen, drugačen pristop pri teh, 1100 00:39:10,440 --> 00:39:13,490 vendar za zdaj, kaj je samo razmisliti nekatere druge takta 1101 00:39:13,490 --> 00:39:16,840 še posebej, če sortiranje tisti sprejmejo malo časa, da se potopi v. 1102 00:39:16,840 --> 00:39:21,790 Kaj je algoritem, ki smo jih že videli da je o vrstnem redu n korakov? 1103 00:39:21,790 --> 00:39:27,560 >> Kaj naj bi linearno številko od korakov, ki smo jih videli doslej? 1104 00:39:27,560 --> 00:39:29,350 Kaj je to? 1105 00:39:29,350 --> 00:39:30,480 Iskanje telefon imenik. 1106 00:39:30,480 --> 00:39:31,390 Prvi algoritem. 1107 00:39:31,390 --> 00:39:31,560 Prav? 1108 00:39:31,560 --> 00:39:33,650 Kje smo linearno išče Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Prav zares. 1110 00:39:34,150 --> 00:39:37,180 Od ničelne tednu, ko sem začel obrača eno stran naenkrat, 1111 00:39:37,180 --> 00:39:40,095 in sem celo rekel, da je bila vrsta linearnega občutek algoritma 1112 00:39:40,095 --> 00:39:42,720 in smo imeli tisto sliko na plošča z ravnimi rdečo črto 1113 00:39:42,720 --> 00:39:44,678 in ravno rumena linijo, to so bili dejansko 1114 00:39:44,678 --> 00:39:46,810 algoritmi, ki so v velikem O n. 1115 00:39:46,810 --> 00:39:50,680 >> Ker, da bi našli Mike Smith v telefonu Knjiga n strani, v najslabšem primeru, 1116 00:39:50,680 --> 00:39:52,422 me n korake lahko traja. 1117 00:39:52,422 --> 00:39:53,630 Kaj pa ob navzočnosti? 1118 00:39:53,630 --> 00:39:55,790 Ena dva tri štiri pet šest. 1119 00:39:55,790 --> 00:39:59,420 Kaj je čas za to tekmovanje v teku Algoritem za sprejemanje udeležbo? 1120 00:39:59,420 --> 00:40:03,070 Big O n, ker v teoriji sem morali izpostaviti vse v sobi. 1121 00:40:03,070 --> 00:40:05,861 >> Zdaj kot prahi, kaj približno drugi optimizacija od ničelne teden? 1122 00:40:05,861 --> 00:40:08,117 Dve, ​​štiri, šest, osem, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Računalniški znanstvenik bi zavedaš, počakaj malo, 1124 00:40:10,200 --> 00:40:12,320 da je o vrstnem redu n deljeno s dveh korakih. 1125 00:40:12,320 --> 00:40:12,820 Prav? 1126 00:40:12,820 --> 00:40:14,444 Ker delam dve osebi naenkrat. 1127 00:40:14,444 --> 00:40:17,015 Ampak bomo prezreti ti nižje pogoji naročilo, 1128 00:40:17,015 --> 00:40:19,140 in smo le, da bo mečejo razkoraka z 2, 1129 00:40:19,140 --> 00:40:21,830 in samo reči, velik O n ta algoritmom, kot tudi. 1130 00:40:21,830 --> 00:40:22,760 >> Kaj pa tale? 1131 00:40:22,760 --> 00:40:26,170 Bomo preskočili nekatere od njih, ampak kaj je algoritem, ki je dnevnik n? 1132 00:40:26,170 --> 00:40:29,900 To je trajalo približno log n korakov? 1133 00:40:29,900 --> 00:40:30,870 Razkorak in vladaj. 1134 00:40:30,870 --> 00:40:31,369 Točno tako. 1135 00:40:31,369 --> 00:40:33,900 Tako kot na primer telefonskega imenika v nič teden in že danes, 1136 00:40:33,900 --> 00:40:36,191 kjer smo razdelili problem znova in znova in znova. 1137 00:40:36,191 --> 00:40:39,070 Jo narisal smo na ladji v tednu nič kot upognjena zelene črte, 1138 00:40:39,070 --> 00:40:41,460 in mi je povedal, da je dan, da je logaritemski algoritem. 1139 00:40:41,460 --> 00:40:44,970 >> In res se je število korakov je potrebno za opravljanje deli in vladaj, 1140 00:40:44,970 --> 00:40:48,610 ali binarno iskanje, kot bomo začeti kliče, tako kot v telefonskem imeniku, 1141 00:40:48,610 --> 00:40:50,680 je reda log in korakov. 1142 00:40:50,680 --> 00:40:52,470 In to je malo čudno eno. 1143 00:40:52,470 --> 00:40:54,910 >> Kaj je en korak, ali natančneje 1144 00:40:54,910 --> 00:40:56,240 konstantno število korakov? 1145 00:40:56,240 --> 00:40:58,865 Mogoče je dva, morda je tri, toda računalniški znanstvenik pravkar 1146 00:40:58,865 --> 00:41:01,423 ga poenostavlja kot veliki O 1, nekateri konstantno število korakov. 1147 00:41:01,423 --> 00:41:04,256 Kaj je nekaj, kar bi lahko storili, da je konstantno število korakov? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Kaj je čas ploskati teče? 1150 00:41:10,930 --> 00:41:11,920 Constant čas. 1151 00:41:11,920 --> 00:41:12,420 Prav? 1152 00:41:12,420 --> 00:41:15,490 Všeč, kaj je čas teče delaš karkoli, da ima samo eno 1153 00:41:15,490 --> 00:41:18,570 delovanje, kot so tiskanje F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Da bi lahko rekli, da je stalen čas razen če je manj igralcev primeru s tiskalno F, 1155 00:41:24,110 --> 00:41:28,260 kaj bi lahko čas teče tiska F dejansko? 1156 00:41:28,260 --> 00:41:28,790 In zakaj? 1157 00:41:28,790 --> 00:41:30,550 Kaj je merilna n v tem primeru? 1158 00:41:30,550 --> 00:41:32,251 >> OBČINSTVO: [neslišno]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. Malan: Točno tako. 1160 00:41:33,250 --> 00:41:34,900 Število znakov želimo natisniti. 1161 00:41:34,900 --> 00:41:36,191 Torej, to je zelo kontekstno občutljivi. 1162 00:41:36,191 --> 00:41:39,910 Danes smo se osredotoča veliko na črke in številke tukaj na krovu. 1163 00:41:39,910 --> 00:41:43,540 Ampak to je lahko tudi znaki v dejanskem nizu. 1164 00:41:43,540 --> 00:41:46,420 Tako se izkaže, da je še ukrep, ki se bo začelo skrbeti, 1165 00:41:46,420 --> 00:41:48,530 in da je nasprotno z velikim O, tako rekoč. 1166 00:41:48,530 --> 00:41:50,120 >> To je omega zapis. 1167 00:41:50,120 --> 00:41:53,380 Ker je velik O pomeni, kaj se je Zgornji vezani na svojem tekaškem času? 1168 00:41:53,380 --> 00:41:55,580 Maksimalno, koliko časa Morda kaj vzeti? 1169 00:41:55,580 --> 00:41:59,250 Omega-- Žal to vedno znova up-- je nasprotje tega, 1170 00:41:59,250 --> 00:42:02,960 pri čemer je spodnja meja Količina časa nečesa lahko traja. 1171 00:42:02,960 --> 00:42:10,480 >> So. na primer, kaj je algoritem da je vedno n Squared korake? 1172 00:42:10,480 --> 00:42:15,600 No, eden od algoritmov, ki smo jih videli Danes, v resnici, morda tudi to. 1173 00:42:15,600 --> 00:42:16,720 Izbor vrste. 1174 00:42:16,720 --> 00:42:18,270 Izbor vrste je precej neumno. 1175 00:42:18,270 --> 00:42:21,760 Tudi če algorithm-- žal, tudi če je matrika že razporejene, 1176 00:42:21,760 --> 00:42:24,150 Izbor vrsta se bo hodi po seznamu 1177 00:42:24,150 --> 00:42:28,907 se prepričajte, da ima najmanjši element znova in znova in znova. 1178 00:42:28,907 --> 00:42:31,740 In čeprav ste ljudje v publika ve, da, počakaj malo, 1179 00:42:31,740 --> 00:42:33,948 ste že opravili najmanjši element, računalnik 1180 00:42:33,948 --> 00:42:37,300 ne ve, da dokler ne izgleda vse skozi seznam. 1181 00:42:37,300 --> 00:42:40,240 Podobno nižjo mejo, ki lahko upoštevajo tudi 1182 00:42:40,240 --> 00:42:42,000 lahko linearen čas. 1183 00:42:42,000 --> 00:42:48,260 >> Koliko časa traja, da se sortiranje n elementov v najboljši 1184 00:42:48,260 --> 00:42:52,420 primer s pomočjo nekaj podobnega mehurček vrste? 1185 00:42:52,420 --> 00:42:54,280 Recimo, da vaš seznam je že urejeno. 1186 00:42:54,280 --> 00:42:56,696 Rekli smo, mehurček nekako popelje na vrstni red n kvadrat korake. 1187 00:42:56,696 --> 00:42:59,640 Ampak kaj, če ga je že urejeno? 1188 00:42:59,640 --> 00:43:02,310 Kaj pa, če se zavedaš, po ena podaja skozi niz 1189 00:43:02,310 --> 00:43:03,540 da ste naredili nobenih zamenjav? 1190 00:43:03,540 --> 00:43:05,970 Ali morate hraniti izdelavo več prelazov? 1191 00:43:05,970 --> 00:43:06,470 >> No. 1192 00:43:06,470 --> 00:43:10,340 Torej nižja vezan na mehurček vrste bi lahko rekli, da je linearna. 1193 00:43:10,340 --> 00:43:11,830 Omega n. 1194 00:43:11,830 --> 00:43:14,450 In bomo lahko ogledate na drugi o njih, kot tudi. 1195 00:43:14,450 --> 00:43:17,990 Torej, kaj je na hitro pogledamo na samo vizualizacijo tukaj 1196 00:43:17,990 --> 00:43:20,790 da vidim, kako ti razlikovati sami. 1197 00:43:20,790 --> 00:43:24,592 Jaz bom šel dol v to Stran, ki je na voljo na spletni strani C50 je, 1198 00:43:24,592 --> 00:43:27,550 vendar pa bo bolečina priti delajo, saj uporablja tehnologijo z imenom 1199 00:43:27,550 --> 00:43:30,560 Java programčki, ki je v veliki meri podprta v teh dneh, 1200 00:43:30,560 --> 00:43:32,730 vsaj Chrome in nekaterih drugih. 1201 00:43:32,730 --> 00:43:37,070 >> In naj me iti naprej in pospešila ta in razložiti, kaj se dogaja. 1202 00:43:37,070 --> 00:43:40,840 To je dokaz balona nekako, prvi algoritem smo pogledal. 1203 00:43:40,840 --> 00:43:43,950 In to je vizualizacija tem, da vsak teh palic predstavlja število. 1204 00:43:43,950 --> 00:43:45,710 Večji kot je bar, večje število. 1205 00:43:45,710 --> 00:43:47,520 Manjša kot je bar, manjše število. 1206 00:43:47,520 --> 00:43:50,353 In kaj si lahko ogledate vizualno, čeprav čeprav to se dogaja, super hitro, 1207 00:43:50,353 --> 00:43:53,699 je, da je rdeče bar, kot sem jaz, hoja naprej in nazaj določitev problemov. 1208 00:43:53,699 --> 00:43:56,740 Vidite lahko, da je večji elementi so res prepihavanje do desne, 1209 00:43:56,740 --> 00:43:59,650 in manjše elemente so prepihavanje navzgor na levi strani. 1210 00:43:59,650 --> 00:44:01,870 In tukaj, če bomo dejansko bolj pozorno, 1211 00:44:01,870 --> 00:44:04,330 bomo lahko dejansko štetje število primerjav in zamenjav 1212 00:44:04,330 --> 00:44:05,350 ki so bile narejene. 1213 00:44:05,350 --> 00:44:07,360 >> Toda namesto da bi si oglejmo na drugi algoritem 1214 00:44:07,360 --> 00:44:11,240 smo pogledal prej z našimi prostovoljci, izbor sort. 1215 00:44:11,240 --> 00:44:13,500 Vizualno, da ima zelo drugačen učinek. 1216 00:44:13,500 --> 00:44:16,820 Ampak to je, še enkrat, zelo intuitivno, v da se držimo izberete naslednjo manjšo 1217 00:44:16,820 --> 00:44:18,660 element, in imamo malo srečen. 1218 00:44:18,660 --> 00:44:20,110 Ki bistveno hitreje počutil. 1219 00:44:20,110 --> 00:44:22,840 Ampak, če bomo to spet in spet tekel in spet z veliko vhodov, 1220 00:44:22,840 --> 00:44:26,680 bomo videli, da je to res še vedno v veliki O n kvadrat. 1221 00:44:26,680 --> 00:44:29,920 >> Naredimo eno zadnjo tukaj, vstavljanje razvrščanje, 1222 00:44:29,920 --> 00:44:33,180 ki je bil tretji algoritem smo pogledal in odpoklic 1223 00:44:33,180 --> 00:44:36,700 da to imamo opravka z elementi, saj jim naleti, 1224 00:44:36,700 --> 00:44:39,290 potem pa morda premiki stvari kot da bi naredili prostor, 1225 00:44:39,290 --> 00:44:41,660 vstavljanje elementov, kamor sodijo. 1226 00:44:41,660 --> 00:44:45,330 >> In tudi to konča, s katero se končni rezultat. Zdaj vsi trije tistih 1227 00:44:45,330 --> 00:44:46,490 počutil precej hitro. 1228 00:44:46,490 --> 00:44:48,740 In res, sem jih tekel na zelo dober posnetek. 1229 00:44:48,740 --> 00:44:52,510 Ampak v bistvu, oni vse precej grozno, če sem iskren. 1230 00:44:52,510 --> 00:44:56,960 Vse te algoritmov doslej da je vožnja v veliki O n kvadrat 1231 00:44:56,960 --> 00:44:59,270 traja kar nekaj Čas je, da teče na koncu. 1232 00:44:59,270 --> 00:45:01,920 >> In res, lahko vidimo, in občutek je to nazadnje 1233 00:45:01,920 --> 00:45:04,090 če potegnem to tretji in zadnji demo. 1234 00:45:04,090 --> 00:45:05,840 To je še en vizualizacija, ki se dogaja 1235 00:45:05,840 --> 00:45:08,500 pokazati mehurček vrste na levi strani, Izbira nekako v sredini, 1236 00:45:08,500 --> 00:45:13,410 in kaj, kot eden od naših ročno postavlja prej predlagal, 1237 00:45:13,410 --> 00:45:15,020 združiti vrste na desni strani. 1238 00:45:15,020 --> 00:45:16,937 Deli in vladaj Strategija na desni strani. 1239 00:45:16,937 --> 00:45:19,520 In to je v resnici, kaj smo dogaja, da pogled na sredo. 1240 00:45:19,520 --> 00:45:21,990 Ampak kaj je čas te teči vzporedno. 1241 00:45:21,990 --> 00:45:26,765 To je približno enako število Elementi, vse teče istočasno. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble vrsta vs izbor Razvrsti vs zlivanjem. 1244 00:45:34,440 --> 00:45:36,760 >> Zdaj, oni vse teče v teoriji hkrati. 1245 00:45:36,760 --> 00:45:39,830 CPU teče pri enako hitrostjo, vendar pa 1246 00:45:39,830 --> 00:45:44,014 lahko občutite, kako dolgočasno je to Zelo hitro bo postala, 1247 00:45:44,014 --> 00:45:45,930 in kako hitro, ko vbrizgamo malo tedna 1248 00:45:45,930 --> 00:45:49,330 algoritmi ZERO lahko smo pospešili stvari. 1249 00:45:49,330 --> 00:45:51,760 >> In sedaj dajmo primerjati ti v eni zadnjem obliki. 1250 00:45:51,760 --> 00:45:55,710 Grem, da gredo naprej na spletni strani CS50 je, kjer je 1251 00:45:55,710 --> 00:45:59,020 imamo to končno povezavo za danes, kjer je nekdo na internetu 1252 00:45:59,020 --> 00:46:03,960 vljudno dal skupaj video, ki ujame, kaj drugačnega razvrščanja 1253 00:46:03,960 --> 00:46:07,510 algoritmi sliši. 1254 00:46:07,510 --> 00:46:09,577 To je vstavljanje vrsta. 1255 00:46:09,577 --> 00:46:12,072 >> [Piskajoči] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> S katerim ste uporabo frekvence ki temelji na višino bar vrat. 1258 00:46:16,850 --> 00:46:19,826 To je mehurček vrste. 1259 00:46:19,826 --> 00:46:21,822 >> [Zviti piskajoči] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Prihaja naslednji is-- prihajajo up zraven is-- izbor vrste, 1262 00:46:45,774 --> 00:46:48,820 kjer še enkrat, bomo izbiro Naslednji najmanjši element, 1263 00:46:48,820 --> 00:46:51,820 in smo lahko videli, da raste od leve proti desni. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Zlivanjem, naš zmagovalec doslej danes. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Opazili, kako je to tako, da stvari v [neslišno] polovice in četrtine. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome vrste, ki smo jih imeli, ne govori, in ustvarja vizualno 1270 00:47:21,660 --> 00:47:24,450 in audally malo drugačno obliko in zvok. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Greš naprej in nazaj, čiščenje stvari. 1273 00:47:30,160 --> 00:47:32,230 Tudi odjaviti Urejanje kopice na spletni Ta tip je. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> In to je to. 1276 00:47:36,810 --> 00:47:38,210 Vam bomo videli naslednjič. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [WHOOSHING IN MUSIC] 1279 00:47:48,334 --> 00:50:24,839