1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Glazbom] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. Malan: Ovo je CS50. 5 00:00:12,550 --> 00:00:14,612 I ovo je početak tjedna tri. 6 00:00:14,612 --> 00:00:16,820 Dakle, imamo puno uzbudljivije stvari za pokrivanje danas. 7 00:00:16,820 --> 00:00:20,160 Puno mogućnosti za volontira na pozornicu. 8 00:00:20,160 --> 00:00:22,780 I na kraju, danas je Ne radi se o koda na sve. 9 00:00:22,780 --> 00:00:24,820 No, riječ je o idejama, a riječ je o algoritmima, 10 00:00:24,820 --> 00:00:28,420 i zapravo vraćaju neke od Što smo naučili iz tjedna nula, 11 00:00:28,420 --> 00:00:31,910 pri čemu Podsjetimo, mi uveo ovu monstruoznost. 12 00:00:31,910 --> 00:00:33,880 I zaduživanje inspiracija toga, za početak 13 00:00:33,880 --> 00:00:36,879 riješiti sve sofisticiraniji Problemi algoritamski. 14 00:00:36,879 --> 00:00:38,420 Ali prvo, nekoliko obavijesti. 15 00:00:38,420 --> 00:00:42,020 Dakle, jedan, ako želite da se pridruže Osoblje i kolege CS50 je na ručak 16 00:00:42,020 --> 00:00:44,670 ovog petka, i ovdje iu Cambridge, au New Havenu, 17 00:00:44,670 --> 00:00:48,060 posjetite tečaj je web stranice, gdje URL može naći. 18 00:00:48,060 --> 00:00:50,390 Predavanje će se ove srijede ne mora biti ovdje u Sandersa. 19 00:00:50,390 --> 00:00:53,610 To će biti samo online, tako da naštimati na CS50 web stranici, 20 00:00:53,610 --> 00:00:55,850 je li ovdje u Cambridgeu ili New Haven, kao dobro. 21 00:00:55,850 --> 00:00:58,110 >> A onda je problem postaviti dva već je u vašim rukama. 22 00:00:58,110 --> 00:01:03,067 Ako niste ronili još, dopustite mi ponuditi snažno sastavljeno prijedlog 23 00:01:03,067 --> 00:01:05,150 da, pogotovo sada, kao što je problem postavlja unaprijed, 24 00:01:05,150 --> 00:01:08,669 vi stvarno želite početi sada, ako ne i praćakati malo na vikend ili prije 25 00:01:08,669 --> 00:01:10,710 kada su se prvi put izaći na Petkom, jer ćete 26 00:01:10,710 --> 00:01:14,380 da oni nisu nužno sve više i više izazovan po 27 00:01:14,380 --> 00:01:14,950 sebi. 28 00:01:14,950 --> 00:01:17,575 Mislim da ćete naći da je u Općenito, oni imaju tendenciju da se grubo 29 00:01:17,575 --> 00:01:18,892 oko istom vremenu. 30 00:01:18,892 --> 00:01:20,850 No, to svakako ovisi na student, i to 31 00:01:20,850 --> 00:01:22,880 ovisi o razmišljanje s kojima ste ga približiti. 32 00:01:22,880 --> 00:01:24,910 Ali uvijek, ti ​​ćeš pokrenuti protiv nekog zida, 33 00:01:24,910 --> 00:01:26,350 a ti ćeš pogoditi neki bug, a ti si samo 34 00:01:26,350 --> 00:01:27,950 neće biti u mogućnosti dobiti preko nje u nekom trenutku. 35 00:01:27,950 --> 00:01:31,380 I to je iznimno važno biti u mogućnosti korak dalje, vratiti sljedeći dan, 36 00:01:31,380 --> 00:01:35,286 ići radnog vremena, post o CS50 Raspravite ili slično, da se zapravo dobiti deblokiran. 37 00:01:35,286 --> 00:01:36,160 Pa imajte to na umu. 38 00:01:36,160 --> 00:01:40,830 Počevši najranije moguće, je najbolja stvar koju možete učiniti. 39 00:01:40,830 --> 00:01:44,160 Dakle, ovdje gdje smo počeli klasa, više u tjednu nula. 40 00:01:44,160 --> 00:01:47,441 I možemo dobiti volonter ovdje da mi pomogne pronaći mikrofone? 41 00:01:47,441 --> 00:01:47,940 U REDU. 42 00:01:47,940 --> 00:01:48,900 Stojeći već. 43 00:01:48,900 --> 00:01:50,080 Dođi gore. 44 00:01:50,080 --> 00:01:53,707 Pogodite koji je kako to ide na posao. 45 00:01:53,707 --> 00:01:54,415 Kako se zoveš? 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 Dođi gore. 49 00:01:57,910 --> 00:01:58,619 Drago mi je. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Lijepo da zadovolji vas. 51 00:01:59,910 --> 00:02:02,772 DAVID J. Malan: A ti si ovdje s nama u tjednu nula, naravno. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: bio sam. 53 00:02:03,028 --> 00:02:03,160 Bio sam. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. Malan: Pa mogao si otići naprijed i pronaći za nas Mike Smith, 55 00:02:05,868 --> 00:02:08,639 kao brz kao možete? 56 00:02:08,639 --> 00:02:10,639 Kao brz kao možete. 57 00:02:10,639 --> 00:02:13,756 Doslovno suzenje problem na pola kao što je potrebno. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Hm. 59 00:02:15,130 --> 00:02:17,380 DAVID J. Malan: Doslovno suzenje problem na pola. 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 Jako dobro. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. Malan: U redu. 65 00:02:23,700 --> 00:02:24,200 Dobra. 66 00:02:24,200 --> 00:02:24,701 Hvala. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Vrlo dobro. 68 00:02:25,700 --> 00:02:26,210 U REDU. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. Malan: I tako sada, ste ga reducirane 70 00:02:27,610 --> 00:02:29,320 pola veličine problema. 71 00:02:29,320 --> 00:02:31,267 Sada smo dolje na četvrtine. 72 00:02:31,267 --> 00:02:33,475 Jeste li plaćati pozornost na kojoj strani smo čuvanje? 73 00:02:33,475 --> 00:02:34,405 >> [Smijeha] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Da, ja think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. Malan: Što poglavlje smo u? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: auspusi, tako. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. Malan: U redu. 78 00:02:39,941 --> 00:02:42,810 Ali Mike Smith ide da se nakon ispušne cijevi. 79 00:02:42,810 --> 00:02:44,130 So-- 80 00:02:44,130 --> 00:02:48,180 >> [Smijeha] 81 00:02:48,180 --> 00:02:48,742 >> U redu. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Gdje se gleda? 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: Sada smo u kirurška. 86 00:02:54,760 --> 00:02:57,840 Sada, liječnici. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- idemo s Real. 89 00:02:59,856 --> 00:03:00,370 Nekretnine. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. Malan: Real. 91 00:03:00,970 --> 00:03:01,470 U REDU. 92 00:03:01,470 --> 00:03:03,700 Ako trebate pravi. 93 00:03:03,700 --> 00:03:05,250 Sada, na koji način je Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Ovaj način. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. Malan: Na koji način? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Čekaj. 97 00:03:08,240 --> 00:03:08,790 M is-- pravo? 98 00:03:08,790 --> 00:03:09,110 Počeli smo with-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. Malan: Da. 100 00:03:10,090 --> 00:03:10,650 Oni lijevo. 101 00:03:10,650 --> 00:03:11,430 Vaše pravo. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Da. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. Malan: Pa Mike je ovdje. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Što? 105 00:03:13,990 --> 00:03:14,665 >> [Smijeha] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Loš primjer, dečki. 108 00:03:18,330 --> 00:03:18,830 Oprostite. 109 00:03:18,830 --> 00:03:21,610 DAVID J. Malan: To će učiti da skok iz svog naslonjača. 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 Te imam. 113 00:03:23,390 --> 00:03:24,670 Te imam. 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 Ovo is-- redu, ja ti imam. 117 00:03:26,812 --> 00:03:27,520 Smith je ovdje? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. Malan: Smith, hvala. 119 00:03:28,894 --> 00:03:30,535 Dakle, ja ću držati obličje gore Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: O, da. 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, imaš Smith. 125 00:03:32,580 --> 00:03:33,415 U REDU. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Da, dobio Smith ovdje. 127 00:03:34,040 --> 00:03:34,700 Žao nam je, momci. 128 00:03:34,700 --> 00:03:35,860 Mislio sam Michael-- smo su u potrazi za Michaela. 129 00:03:35,860 --> 00:03:36,550 Oprostite. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. Malan: To je u redu. 131 00:03:37,550 --> 00:03:39,950 U redu, sada smo u Paccini i sinovi. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini i sinovi. 133 00:03:41,242 --> 00:03:43,158 DAVID J. Malan: Samo vi i ja se u ovo. 134 00:03:43,158 --> 00:03:44,050 U REDU. 135 00:03:44,050 --> 00:03:45,130 Pronađite nas 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 u R za smeće. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Glupost. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Ovo će potrajati. 143 00:03:52,480 --> 00:03:54,340 >> [Smijeha] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. Malan: Cipele. 146 00:03:56,720 --> 00:03:58,080 Mi smo u cipele. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Sad smo gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. Malan: Lijepo. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [Smijeha] 151 00:04:03,620 --> 00:04:05,440 Oh, ovo je super. 152 00:04:05,440 --> 00:04:06,910 [Smijeha] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. Malan: To je u 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 Ne mislim da ću imaju PSAT prijatelja nakon ovog. 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: U redu. 162 00:04:19,459 --> 00:04:21,600 Tako ćemo suzu to na pola. 163 00:04:21,600 --> 00:04:22,270 Uredu je. 164 00:04:22,270 --> 00:04:25,606 To završava loše u svakom slučaju, jer je Mike Smith neće biti u žute stranice. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Ah. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. Malan: Ne, to je u redu. 167 00:04:27,140 --> 00:04:28,930 Ali neka je pretvarati se kao on je na ovoj stranici. 168 00:04:28,930 --> 00:04:33,260 Tako sada ste whittled problem dolje na jednoj stranici, a pronašli smo Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Pljeskati] 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 U REDU. 174 00:04:41,200 --> 00:04:43,646 To je izvanredno. 175 00:04:43,646 --> 00:04:45,954 Ali to je još brži nego linearno pretraživanje, 176 00:04:45,954 --> 00:04:47,870 u kojoj smo početi na početku knjige, 177 00:04:47,870 --> 00:04:51,210 i mi premjestiti naš put s lijeva na desno, vremenom u potrazi za Mike Smith. 178 00:04:51,210 --> 00:04:53,540 I tako, ako je telefonski imenik je možda 1.000 stranica, 179 00:04:53,540 --> 00:04:56,300 možda bi uzeti nas 10-ak stranica suze. 180 00:04:56,300 --> 00:04:59,380 >> Ali možda ste utjecati dotaknuo pretpostavku 181 00:04:59,380 --> 00:05:03,602 u sve to, što će reći da je telefonski imenik unaprijed je što? 182 00:05:03,602 --> 00:05:04,310 PUBLIKA: Poredano. 183 00:05:04,310 --> 00:05:05,000 DAVID J. Malan: To je riješeno. 184 00:05:05,000 --> 00:05:05,160 Pravo? 185 00:05:05,160 --> 00:05:07,909 To je razvrstani po abecednom redu, tako da da su svi od tih imena i brojeva 186 00:05:07,909 --> 00:05:11,230 su razvrstani iz A-a na Z-a, a po abecednom između. 187 00:05:11,230 --> 00:05:13,100 Ali danas, mi sada pitati pitanje, dobro, 188 00:05:13,100 --> 00:05:16,170 kako je bio Verizon ili telefon Tvrtka je ući u to stanje? 189 00:05:16,170 --> 00:05:19,560 >> Budući da je jedna stvar utjecati Ta pretpostavka, i stoga, 190 00:05:19,560 --> 00:05:22,570 rješavanje problema s Algoritam učinkovitije. 191 00:05:22,570 --> 00:05:24,900 Ali mi nikada stvarno pitao u tjednu nula, dobro, 192 00:05:24,900 --> 00:05:27,790 koliko je to učinio troškova Verizon ili netko drugi 193 00:05:27,790 --> 00:05:29,620 da biste dobili taj telefonski imenik u sortiranog bi? 194 00:05:29,620 --> 00:05:29,780 >> Pravo? 195 00:05:29,780 --> 00:05:31,529 Nije važno ako gleda gore Mike Smith 196 00:05:31,529 --> 00:05:35,190 je super brzo, ako Vam je potrebno godine sortirati stranice početku. 197 00:05:35,190 --> 00:05:35,690 Pravo? 198 00:05:35,690 --> 00:05:38,620 Možda i samo prosijati kroz slučajnom telefonskom imeniku, 199 00:05:38,620 --> 00:05:40,690 ako će biti super skupo to riješiti. 200 00:05:40,690 --> 00:05:42,350 Dakle, ako možemo imati još jedan volonter. 201 00:05:42,350 --> 00:05:46,350 Idemo uzeti pogledati ovdje kako smo might-- hajde up-- tome 202 00:05:46,350 --> 00:05:48,100 bismo mogli ići o razvrstavanju tih. 203 00:05:48,100 --> 00:05:51,990 >> A ako Jordan moze pridružite nam se ovdje na pozornici. 204 00:05:51,990 --> 00:05:55,100 Hajde se samo na trenutak. 205 00:05:55,100 --> 00:05:56,359 Kako se zoveš? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. Malan: Caroline, dođi gore. 208 00:05:58,691 --> 00:06:02,070 A vi ćete se pridružiti po meni i Jordana ovdje. 209 00:06:02,070 --> 00:06:03,800 Caroline, hvala. 210 00:06:03,800 --> 00:06:04,300 U redu. 211 00:06:04,300 --> 00:06:08,330 Pa što imamo ovdje Caroline je 26 plave knjige 212 00:06:08,330 --> 00:06:10,747 da FAS koristi za administriranje određene završne ispite. 213 00:06:10,747 --> 00:06:13,330 To su sve teško naći, ali ono što smo učinili u unaprijed 214 00:06:13,330 --> 00:06:15,800 je da smo stavili nečije ime Na prednjoj strani svakog od njih, 215 00:06:15,800 --> 00:06:18,133 ali smo zadržao je jednostavan, zatim stavljanjem van puna imena. 216 00:06:18,133 --> 00:06:22,720 Tako bismo staviti osobu s imenom L, D, J, B, skroz A do Z, 217 00:06:22,720 --> 00:06:24,090 ali oni su u slučajnim redoslijedom. 218 00:06:24,090 --> 00:06:26,890 I tako, ako bi, u razgovoru svoj blog put kroz problem kao i vi 219 00:06:26,890 --> 00:06:31,620 to učiniti, možete ići naprijed i sortirati to za nas, od A do Z. 220 00:06:31,620 --> 00:06:34,070 >> PUBLIKA: OK, L je kao, srednji. 221 00:06:34,070 --> 00:06:35,050 C je početak. 222 00:06:35,050 --> 00:06:42,410 B. J prije L. B, P 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. Malan: Držite da Mislio za jednu sekundu. 224 00:06:45,140 --> 00:06:48,910 Jer inače, to je samo zanimljivo ti, ja i Jordanu. 225 00:06:48,910 --> 00:06:49,724 Idemo tamo. 226 00:06:49,724 --> 00:06:50,640 PUBLIKA: [nečujan]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. Malan: U redu. 229 00:06:58,090 --> 00:06:59,310 Što radiš? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M dolazi nakon O. 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. Malan: U redu. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. Malan: O, dobro. 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. Da. 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, tako da Izgleda kao da ste making-- zadržati ide. 238 00:07:10,689 --> 00:07:12,730 Izgleda radite velika hrpa ovdje, 239 00:07:12,730 --> 00:07:13,910 i vrsta velikog hrpu tamo. 240 00:07:13,910 --> 00:07:16,230 Tako je prva polovica abecede, Druga polovica abecede. 241 00:07:16,230 --> 00:07:16,460 U REDU. 242 00:07:16,460 --> 00:07:16,960 Dobra. 243 00:07:16,960 --> 00:07:19,680 Vrsta cijepanje problem na dva dijela. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Da. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. Malan: U redu. 247 00:07:22,980 --> 00:07:25,070 K. Znači vrsta odabira ih jedan za drugim, 248 00:07:25,070 --> 00:07:27,620 stavljajući ga bilo lijevo ili desno, ili Z događa na podu. 249 00:07:27,620 --> 00:07:28,012 U REDU. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z događa na podu. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. Malan: U redu. 252 00:07:29,360 --> 00:07:30,920 Y se događa na podu. 253 00:07:30,920 --> 00:07:31,735 Sada možemo staviti 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 ide lijevo. 256 00:07:33,700 --> 00:07:36,017 S ide dobro. 257 00:07:36,017 --> 00:07:37,642 U redu, A ide sve na putu utakmice. 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: Sada, dobro. 260 00:07:39,873 --> 00:07:43,260 Imamo A, B, C W događa tamo dolje. 261 00:07:43,260 --> 00:07:45,566 U redu, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, J 263 00:07:46,611 --> 00:07:47,860 DAVID J. Malan: H, I, J dobro. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: U centru, ja sam gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. Malan: U redu. 266 00:07:50,000 --> 00:07:52,375 Tako sada, idemo u naturi od spojiti ove različite hrpe. 267 00:07:52,375 --> 00:08:00,730 Tako A do C, onda vidim D i E i F i G i H i I. Nice. 268 00:08:00,730 --> 00:08:05,540 J, K. A onda, ovo je gomila naopako, ali to je u redu. 269 00:08:05,540 --> 00:08:06,040 Naravno. 270 00:08:06,040 --> 00:08:07,240 Možemo smanjiti neke ugla. 271 00:08:07,240 --> 00:08:07,950 U REDU. 272 00:08:07,950 --> 00:08:10,530 I onda moramo W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Da. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. Malan: Izvrsno. 275 00:08:11,880 --> 00:08:14,122 Dakle, velika hvala Caroline za razvrstavanje tih. 276 00:08:14,122 --> 00:08:15,030 >> [Pljeskati] 277 00:08:15,030 --> 00:08:17,287 >> Hvala. 278 00:08:17,287 --> 00:08:18,120 Puno hvala. 279 00:08:18,120 --> 00:08:22,910 Dakle, sada ćemo razmotriti trenutak Kako je Caroline, prošao zemljom čineći to, 280 00:08:22,910 --> 00:08:26,040 i što točno smo mogli su to-- kako smo 281 00:08:26,040 --> 00:08:28,409 bili u mogućnosti riješiti to problem kada smo bili samo 282 00:08:28,409 --> 00:08:29,950 dati cijela hrpa slučajnih ulaza. 283 00:08:29,950 --> 00:08:31,610 >> Pa, izgleda da postoji je malo sustava tamo? 284 00:08:31,610 --> 00:08:32,110 Tako je. 285 00:08:32,110 --> 00:08:34,495 Dakle ranijim pismima u pismu, ona 286 00:08:34,495 --> 00:08:37,120 je stavljanje na lijevo, a kasnije slova abecede, 287 00:08:37,120 --> 00:08:38,270 ona je stavljala u desno. 288 00:08:38,270 --> 00:08:40,500 I čim je pronašao neki proksimalnih pisma, one 289 00:08:40,500 --> 00:08:43,124 koji ide tik jedna do druge, ona bi stavio one u red. 290 00:08:43,124 --> 00:08:46,750 I tako smo nekako imali ove male gomile sortiranog ulaza događa. 291 00:08:46,750 --> 00:08:50,540 >> I tako to je vrlo slično onome što većina nas ljudi će učiniti. 292 00:08:50,540 --> 00:08:53,530 Mi bi vrsta prosijati kroz njega, i mi bismo vrsta imaju mehanizam. 293 00:08:53,530 --> 00:08:56,930 Ali, to bi moglo biti teško napisati je dolje u formuli po sebi. 294 00:08:56,930 --> 00:08:59,010 Ona osjeća malo više organski od toga. 295 00:08:59,010 --> 00:09:02,560 Dakle, neka je vidjeti ako mi može sada vezan problem s manje ulaza. 296 00:09:02,560 --> 00:09:05,170 >> Umjesto 26, neka je nešto daleko manje 297 00:09:05,170 --> 00:09:09,890 sa samo reći, sedam, iza ta vrata, da tako kažemo. 298 00:09:09,890 --> 00:09:11,300 Postoje samo sedam brojeva? 299 00:09:11,300 --> 00:09:15,240 A ako je cilj sada Ruka je pronaći vrijednost, 300 00:09:15,240 --> 00:09:17,850 da vidimo kako učinkovito možemo ići o događaj ovaj. 301 00:09:17,850 --> 00:09:22,460 I neka je vidjeti ako mi može sada početi primjenjivati ​​neke brojeve, 302 00:09:22,460 --> 00:09:26,310 ili neke formule s kojima se opisuju učinkovitost našeg telefonskog imenika 303 00:09:26,310 --> 00:09:31,060 Algoritam, naš ispit Knjiga algoritam, i općenito, pronalaženje informacija. 304 00:09:31,060 --> 00:09:34,770 >> Pa za to, neka mi ići naprijed i na zaslonu osjetljivom na dodir ovdje, 305 00:09:34,770 --> 00:09:41,100 dići web preglednik koji ima upravo ovih sedam vrata. 306 00:09:41,100 --> 00:09:46,670 A ako smo mogli dobiti još jedan dobrovoljno doći ovamo, 307 00:09:46,670 --> 00:09:48,480 Ja sam stavio ove iste vrata ovamo. 308 00:09:48,480 --> 00:09:49,170 Brzo volonter. 309 00:09:49,170 --> 00:09:51,130 >> Ovaj one-- demo idu za brže i brže sada. 310 00:09:51,130 --> 00:09:51,600 Dođi dolje. 311 00:09:51,600 --> 00:09:52,308 Kako se zoveš? 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 U redu, Trevor, hajde dolje. 315 00:09:55,770 --> 00:09:59,212 Dakle, Trevor je volontirala ovdje da napraviti sličan problem, ali onaj koji je 316 00:09:59,212 --> 00:10:02,170 uša u djelokrugu, te da će kako bi nam omogućiti da pokušati formalizirati sada 317 00:10:02,170 --> 00:10:03,970 postupak za razvrstavanje tih brojeva. 318 00:10:03,970 --> 00:10:05,500 >> Dakle Trevor, lijepo da zadovolji vas. 319 00:10:05,500 --> 00:10:08,720 Dakle ovdje je niz, tako da govori, popis sedam vrata. 320 00:10:08,720 --> 00:10:10,327 Idi naprijed i pronaći nam broj 50. 321 00:10:10,327 --> 00:10:12,410 I onda, nakon toga, recite nam kako ste ga pronašli. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Ukoliko be-- redu. 324 00:10:20,040 --> 00:10:21,945 Da, to je jedan ovdje? 325 00:10:21,945 --> 00:10:24,680 Uh oh. 326 00:10:24,680 --> 00:10:25,560 U REDU. 327 00:10:25,560 --> 00:10:26,680 Vi kliknuli da je jedan. 328 00:10:26,680 --> 00:10:28,690 Dobra. 329 00:10:28,690 --> 00:10:29,780 >> I dobro. 330 00:10:29,780 --> 00:10:30,970 Sada ste kliknuli da je jedan. 331 00:10:30,970 --> 00:10:34,060 I neka mi vam dati mikrofon, tako da ga imate u samo trenutak. 332 00:10:34,060 --> 00:10:37,000 Idi naprijed i kliknite na pokraj vrata koja namjeravate. 333 00:10:37,000 --> 00:10:39,812 Da dobro. 334 00:10:39,812 --> 00:10:41,020 Trevor: Mogu li poništite vrata? 335 00:10:41,020 --> 00:10:42,620 DAVID J. Malan: Ne, ne mogu poništite. 336 00:10:42,620 --> 00:10:43,119 Trevor: U redu. 337 00:10:43,119 --> 00:10:43,974 Ovaj. 338 00:10:43,974 --> 00:10:45,640 DAVID J. Malan: Kamo želite ići? 339 00:10:45,640 --> 00:10:46,410 Koji? 340 00:10:46,410 --> 00:10:47,230 >> Trevor: To je jedan. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. Malan: Ne 342 00:10:48,042 --> 00:10:48,450 >> Trevor: U redu. 343 00:10:48,450 --> 00:10:48,735 Ovaj. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. Malan: Da. 345 00:10:49,020 --> 00:10:49,700 To je dobro. 346 00:10:49,700 --> 00:10:50,380 U redu. 347 00:10:50,380 --> 00:10:53,900 Dakle, ono što je tvoj algoritam ili Postupak za to, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> Trevor: Upravo sam prošao kroz vrata dok nisam pronašao 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. Malan: U redu. 350 00:10:56,940 --> 00:10:58,150 Izvrsna algoritam. 351 00:10:58,150 --> 00:10:59,540 Dakle, to je u redu. 352 00:10:59,540 --> 00:11:03,120 Jer zapravo, ako sam otkriti što je iza tih dvaju drugih vrata, što 353 00:11:03,120 --> 00:11:06,954 ćemo ovdje naći je da imamo samo slučajni ulaz. 354 00:11:06,954 --> 00:11:08,870 Tako da je zapravo kao dobri kao što ste mogli dobiti. 355 00:11:08,870 --> 00:11:12,509 A u stvari, imaš bolji od iscrpno traži cijeli niz, 356 00:11:12,509 --> 00:11:15,300 jer to bi bilo stvarno nesretni ako su hit broj 357 00:11:15,300 --> 00:11:16,604 50 u zadnji vratima. 358 00:11:16,604 --> 00:11:18,520 Ali što ako smo umjesto dao pretpostavku. 359 00:11:18,520 --> 00:11:20,630 Pretpostavimo da vrsta sve ta vrata širom, 360 00:11:20,630 --> 00:11:23,500 tako da imate Brojevi razvrstani ovaj put, 361 00:11:23,500 --> 00:11:29,730 ali ovaj put to je zapravo different-- ovaj put, 362 00:11:29,730 --> 00:11:32,640 to je zapravo izdvojiti za vas. 363 00:11:32,640 --> 00:11:35,380 I sada je cilj pri ruci je pogoditi broj 50. 364 00:11:35,380 --> 00:11:36,090 >> Trevor: U redu. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. Malan: Što je algoritam će biti? 366 00:11:37,670 --> 00:11:39,628 >> Trevor: Pa, ako je to razvrstani, to je bilo ide 367 00:11:39,628 --> 00:11:42,710 da be-- ako najveći do najvećih, spušta, to će biti prvi, 368 00:11:42,710 --> 00:11:44,751 ili ako je suprotno, to će biti posljednja. 369 00:11:44,751 --> 00:11:48,897 Pa samo ću iskoristiti ovu vrata, a onda samo dodirnite posljednja vrata. 370 00:11:48,897 --> 00:11:49,980 DAVID J. Malan: Izvrsno. 371 00:11:49,980 --> 00:11:50,270 U redu. 372 00:11:50,270 --> 00:11:51,150 Tako smo otkrili broj 50. 373 00:11:51,150 --> 00:11:52,970 Dakle, čim je znao su razvrstani smo 374 00:11:52,970 --> 00:11:55,040 bili u mogućnosti iskoristiti ovu pretpostavku. 375 00:11:55,040 --> 00:11:57,040 Dakle, oni su previše poput telefonski imenik primjer. 376 00:11:57,040 --> 00:11:59,540 Čim imate, čak i sa mali problem kao što je ovaj, 377 00:11:59,540 --> 00:12:02,380 Vaši unosi unaprijed razvrstani, možemo zapravo pronaći vrijednost nedvojbeno 378 00:12:02,380 --> 00:12:03,130 učinkovitije. 379 00:12:03,130 --> 00:12:05,800 >> I nisam ti ako je to reći razvrstani male do velike ili velike za male, 380 00:12:05,800 --> 00:12:08,080 i tako da je vrlo razumna započeti na jednom kraju ili drugi 381 00:12:08,080 --> 00:12:09,750 zapravo pronaći tu ciljanu vrijednost. 382 00:12:09,750 --> 00:12:11,400 Dakle zahvaliti Trevor kao dobro. 383 00:12:11,400 --> 00:12:13,260 A ja ću propose-- lijepo učinili. 384 00:12:13,260 --> 00:12:16,960 Imamo malo isječak, zapravo, da je jedan je od naših najdražih trenutaka u CS50, 385 00:12:16,960 --> 00:12:19,700 pri čemu se ponekad ove demonstracije ne sasvim ide prema planu. 386 00:12:19,700 --> 00:12:22,050 I doista upravo sada, ja izvukao krivi sučelje 387 00:12:22,050 --> 00:12:23,508 s kojima se koristiti zaslon osjetljiv na dodir. 388 00:12:23,508 --> 00:12:24,660 Tako da je moja krivnja postoji. 389 00:12:24,660 --> 00:12:26,600 >> Dakle, to će učiniti za iduće godine isječak kao 390 00:12:26,600 --> 00:12:28,570 zašto sam se klikom na vlastitom zaslonu. 391 00:12:28,570 --> 00:12:31,390 Ali neka je uzeti brzo pogledati na ono što se dogodilo prošle godine 392 00:12:31,390 --> 00:12:34,770 s Jay, koji je došao do, mnogo kao Trevor ovdje dobrovoljno, 393 00:12:34,770 --> 00:12:39,380 iu ovom kratkom isječku, vidjet ćete kako je taj isti demo nije sasvim 394 00:12:39,380 --> 00:12:41,074 otkrivaju iste lekcije naučene. 395 00:12:41,074 --> 00:12:41,740 [VIDEO PLAYBACK] 396 00:12:41,740 --> 00:12:45,360 -Sve Što želim da učinite je naći za mene, i za nas, 397 00:12:45,360 --> 00:12:51,674 zapravo, broj 50 korak po korak. 398 00:12:51,674 --> 00:12:52,450 >> -Ponuditelj Broj 50? 399 00:12:52,450 --> 00:12:53,190 >> -Ponuditelj Broj 50. 400 00:12:53,190 --> 00:12:55,356 A možete otkriti što je iza svakog od tih vrata 401 00:12:55,356 --> 00:12:58,540 jednostavnim dodirom s prstom. 402 00:12:58,540 --> 00:13:00,910 Prokletstvo. 403 00:13:00,910 --> 00:13:02,870 >> [Smijeha] 404 00:13:02,870 --> 00:13:03,806 >> [END PLAYBACK] 405 00:13:03,806 --> 00:13:05,430 DAVID J. Malan: Tako da je otišao vrlo dobro. 406 00:13:05,430 --> 00:13:06,796 Oni su bili Nesortirani vrata. 407 00:13:06,796 --> 00:13:08,670 I Jay, naravno, sve to pronašao prebrzo. 408 00:13:08,670 --> 00:13:12,910 Trevor nije puno bolji posao u smislu nastavnu trenutku 409 00:13:12,910 --> 00:13:15,850 da se tako izrazim, ove godine u traje dulje da biste ga pronašli. 410 00:13:15,850 --> 00:13:17,950 Naravno, onda mi je dao Jay drugu priliku, 411 00:13:17,950 --> 00:13:20,320 pri čemu smo razvrstani vrata, baš kao što smo učinili za Trevora, 412 00:13:20,320 --> 00:13:22,300 i Trevor nije super i ovaj put. 413 00:13:22,300 --> 00:13:26,124 Ali Jay je to učinio upola brže. 414 00:13:26,124 --> 00:13:26,790 [VIDEO PLAYBACK] 415 00:13:26,790 --> 00:13:29,650 -Ponuditelj Cilj sada je također Pronađite nas na broj 50, 416 00:13:29,650 --> 00:13:33,030 ali to algoritamski i recite nam kako idete o tome. 417 00:13:33,030 --> 00:13:33,660 >> -U REDU. 418 00:13:33,660 --> 00:13:35,604 >> -I Ako ga pronaći, što bi film. 419 00:13:35,604 --> 00:13:37,228 Ako ne pronađete, možete ga vratiti. 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 >> - [Nečujan] OK. 423 00:13:40,800 --> 00:13:46,236 Tako ću provjeriti krajeve Prvo, ako there's-- odrediti Oh. 424 00:13:46,236 --> 00:13:48,646 >> [PLJESAK] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [END PLAYBACK] 427 00:13:55,729 --> 00:13:56,520 DAVID J. Malan: U redu. 428 00:13:56,520 --> 00:13:59,760 Dakle, sortiranje vrata jasno dovodi do veće učinkovitosti. 429 00:13:59,760 --> 00:14:01,680 I tako, dva puta brže je ono što sam mislio tamo. 430 00:14:01,680 --> 00:14:03,270 I tako je Jay posrećilo oba puta. 431 00:14:03,270 --> 00:14:06,685 I on je također imao sreće u da je prošle godine, naredio sam neke Blu-ray diskova 432 00:14:06,685 --> 00:14:07,560 zapravo dati. 433 00:14:07,560 --> 00:14:09,768 Žao mi je ove godine, što nisu imali isti, Trevor. 434 00:14:09,768 --> 00:14:11,540 Ali još bolje je prije nekoliko godina. 435 00:14:11,540 --> 00:14:14,820 A neki od vas možda znaju kolega, Sean, koji je kad je bio u CS50, 436 00:14:14,820 --> 00:14:17,780 bio izazvan s točno isti problem, iako u SD, 437 00:14:17,780 --> 00:14:19,360 kao što ćete uskoro vidjeti, natrag u dan. 438 00:14:19,360 --> 00:14:22,622 I vidjet ćete da ne samo da je potrebno malo više vremena nego što Jay, 439 00:14:22,622 --> 00:14:25,580 malo duže nego što Trevor, bilo je zapravo ovo izvrsna prilika 440 00:14:25,580 --> 00:14:29,820 angažirati gotovo svi u Publika la cjena ispravna, poticanje 441 00:14:29,820 --> 00:14:31,889 ga naći broj smo tražili. 442 00:14:31,889 --> 00:14:32,930 Idemo. uzeti brzo pogledati. 443 00:14:32,930 --> 00:14:33,320 >> [VIDEO PLAYBACK] 444 00:14:33,320 --> 00:14:33,820 >> -U REDU. 445 00:14:33,820 --> 00:14:36,680 Dakle, vaš zadatak ovdje, Sean, je sljedeći. 446 00:14:36,680 --> 00:14:40,860 Ja sam skriven iza njih Vrata broj sedam. 447 00:14:40,860 --> 00:14:45,120 No, tucked daleko u nekim od tih vrata kao i druge negativne brojeve. 448 00:14:45,120 --> 00:14:47,500 I vaš cilj je da mislite ove gornjem retku brojeva 449 00:14:47,500 --> 00:14:50,390 samo kao niz, ili samo Slijed papirica 450 00:14:50,390 --> 00:14:51,510 s brojevima iza njih. 451 00:14:51,510 --> 00:14:55,540 I vaš cilj je, samo pomoću vrh Niz ovdje, pronašli mi broj sedam. 452 00:14:55,540 --> 00:14:58,570 I onda se ide na kritike Kako idete o tome radi. 453 00:14:58,570 --> 00:14:59,070 -U redu. 454 00:14:59,070 --> 00:15:00,850 -Find Nam broj sedam, molim. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Ne. 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 >> [Smijeha] 461 00:15:24,770 --> 00:15:25,910 >> To nije trik pitanje. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Jedna. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Smijeha] 466 00:15:34,695 --> 00:15:37,861 U ovom trenutku, vaš rezultat nije vrlo dobro, pa možda i zadržati ide. 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 >> [Smijeha] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Idi na. 473 00:15:47,774 --> 00:15:50,690 Iskreno, ja ne mogu pomoći, ali pitam ono što čak i razmišljati o, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Smijeha] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Samo prvi red, pa imaš tri lijevo. 477 00:15:55,020 --> 00:15:56,200 Tako me naći sedam. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Smijeha] 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 Sedam. 484 00:16:26,946 --> 00:16:28,780 >> [PLJESAK] 485 00:16:28,780 --> 00:16:29,426 >> U redu. 486 00:16:29,426 --> 00:16:30,360 >> [END PLAYBACK] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. Malan: Tako smo mogli Pogledajte ove povazdan. 488 00:16:31,840 --> 00:16:34,090 I naravno, neke ovogodišnje demonstracije možda 489 00:16:34,090 --> 00:16:36,330 Sada će završiti u sljedeća Ovogodišnji videa, kao dobro. 490 00:16:36,330 --> 00:16:39,040 Pa sada neka je zapravo usredotočiti na algoritme 491 00:16:39,040 --> 00:16:42,140 ovdje, i vidjeti ako ne možemo sada početi formalizirati 492 00:16:42,140 --> 00:16:46,650 kako možemo ići o uzimajući naše podatke u takvom stanju da je to riješeno, 493 00:16:46,650 --> 00:16:50,054 tako da je u konačnici, možemo zapravo to učinkovitije tražiti. 494 00:16:50,054 --> 00:16:52,470 I iako ćemo koristiti relativno male skupove podataka, 495 00:16:52,470 --> 00:16:54,511 kao osam brojeva mi ima ovdje na brodu, 496 00:16:54,511 --> 00:16:58,230 u konačnici ti isti ideje mogu prijaviti 1.000 ulaza, milijun ulaza, 497 00:16:58,230 --> 00:17:02,100 4 milijarde ulaza, jer su algoritmi će biti u osnovi isti. 498 00:17:02,100 --> 00:17:05,359 >> I tako je to naša zadnja prilika za volontere danas, 499 00:17:05,359 --> 00:17:09,790 ali možda najviše uključeni jedan, za što nam je potrebno osam volontera 500 00:17:09,790 --> 00:17:12,960 da se i nas provesti kroz proces sortiranja što će uskoro 501 00:17:12,960 --> 00:17:15,212 biti na ovim glazbe stoji ovdje. 502 00:17:15,212 --> 00:17:16,170 Pocnimo ovdje. 503 00:17:16,170 --> 00:17:19,692 >> Dakle, jedna u zelenom turquoise-- je to? 504 00:17:19,692 --> 00:17:21,130 Jeste li počinio? 505 00:17:21,130 --> 00:17:21,630 Dva. 506 00:17:21,630 --> 00:17:23,069 Dođi dolje. 507 00:17:23,069 --> 00:17:23,569 U REDU. 508 00:17:23,569 --> 00:17:24,420 Tri. 509 00:17:24,420 --> 00:17:25,400 Četiri. 510 00:17:25,400 --> 00:17:27,247 Neka me-- redu, pet. 511 00:17:27,247 --> 00:17:28,830 Vi ste se imenuje svog prijatelja. 512 00:17:28,830 --> 00:17:31,340 Šest, sedam i osam. 513 00:17:31,340 --> 00:17:32,130 Dođi gore. 514 00:17:32,130 --> 00:17:32,630 U redu. 515 00:17:32,630 --> 00:17:33,190 Hvala vam puno. 516 00:17:33,190 --> 00:17:33,689 Dođi gore. 517 00:17:33,689 --> 00:17:34,790 Dođi gore. 518 00:17:34,790 --> 00:17:35,330 >> U redu. 519 00:17:35,330 --> 00:17:38,890 Dakle, ono što mi here-- i to ima je među one više nespretan, 520 00:17:38,890 --> 00:17:42,390 jer to će zahtijevati da humor ja za samo malo vremena. 521 00:17:42,390 --> 00:17:43,442 Ti ćeš biti broj jedan. 522 00:17:43,442 --> 00:17:44,150 Kako se zoveš? 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 se zoveš? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Josip. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. Malan: Josip, ti si broj dva. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, broj tri. 530 00:17:52,260 --> 00:17:53,722 Stefan, broj četiri. 531 00:17:53,722 --> 00:17:54,430 Cynthia: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. Malan: Cynthia, broj pet. 533 00:17:57,548 --> 00:17:58,452 [Nečujan] 534 00:17:58,452 --> 00:17:59,618 DAVID J. Malan: [nečujan]. 535 00:17:59,618 --> 00:18:00,391 David broj šest. 536 00:18:00,391 --> 00:18:00,890 Matt: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. Malan: Mattov broj sedam. 538 00:18:02,160 --> 00:18:02,850 I? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. Malan: Waverly, broj osam. 541 00:18:04,470 --> 00:18:04,970 U redu. 542 00:18:04,970 --> 00:18:06,510 Ako could-- Ups. 543 00:18:06,510 --> 00:18:08,820 Ako vas sve, kao svoj Prvi izazov, postoji 544 00:18:08,820 --> 00:18:10,820 osam glazbene tribine Ovdje pred publiku. 545 00:18:10,820 --> 00:18:14,200 Ako bi mogao staviti brojeve na ovi glazbe stoji na takav način 546 00:18:14,200 --> 00:18:16,560 da se postroje sa Isti brojevi na brodu. 547 00:18:16,560 --> 00:18:19,560 Tako bi i sami izgledaju kao da su od stavljajući svoje brojeve na ovim glazbe 548 00:18:19,560 --> 00:18:21,960 stoji ovdje. 549 00:18:21,960 --> 00:18:25,980 Izvrsna dosad. 550 00:18:25,980 --> 00:18:26,600 >> Izvrsno. 551 00:18:26,600 --> 00:18:26,890 U REDU. 552 00:18:26,890 --> 00:18:29,556 Tako sada, idemo pitati pitanje u nekoliko različitih načina. 553 00:18:29,556 --> 00:18:31,610 Kako možemo ići o razvrstavanju ti ljudi ovdje? 554 00:18:31,610 --> 00:18:34,500 Budući da smo imali nekoliko pristupa ranije, pri čemu smo 555 00:18:34,500 --> 00:18:36,360 vrsta izrade dva različita kante. 556 00:18:36,360 --> 00:18:38,842 A onda smo općenito komad stvari zajedno. 557 00:18:38,842 --> 00:18:41,050 Čim smo vidjeli dva broja koji su pripadali zajedno, 558 00:18:41,050 --> 00:18:41,975 smo ih zajedno. 559 00:18:41,975 --> 00:18:43,350 Dva slova koja idu zajedno. 560 00:18:43,350 --> 00:18:45,058 >> Ali neka je vidjeti ako mi ne može formalizirati to, 561 00:18:45,058 --> 00:18:48,044 tako da smo u konačnici imati neki pseudo-kod hoćete, 562 00:18:48,044 --> 00:18:49,710 s kojima možete riješiti te probleme. 563 00:18:49,710 --> 00:18:51,870 Pa sad, ja sam u potrazi na tim brojevima ovdje. 564 00:18:51,870 --> 00:18:55,030 I vidim hrpu pogrešaka. 565 00:18:55,030 --> 00:18:57,750 Na kraju, želim jedan na lijevo i osam na desnoj strani. 566 00:18:57,750 --> 00:19:00,650 >> I tako gledam ove dvije, četiri i dva. 567 00:19:00,650 --> 00:19:02,930 I u čemu je problem, očito? 568 00:19:02,930 --> 00:19:04,261 Da. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Dva očito dolazi prije četiri, tako da znate što? 571 00:19:07,160 --> 00:19:10,210 Dopustite mi prvo uzeti pohlepni pristup, ako će, baš kao i problema 572 00:19:10,210 --> 00:19:13,790 postaviti one-- ako se sjećate iz Standard Edition problema postaviti jednu, 573 00:19:13,790 --> 00:19:16,820 gdje sam samo lokalno riješiti problem to je upravo ovdje ispred mene 574 00:19:16,820 --> 00:19:17,690 i vidjeti kamo će me vodi. 575 00:19:17,690 --> 00:19:17,870 >> U REDU. 576 00:19:17,870 --> 00:19:20,161 Dakle, dva i četiri, pustite me naprijed i samo zamijeniti vas dvoje. 577 00:19:20,161 --> 00:19:22,400 Ako može fizički pomicati sebe i vaš rad, 578 00:19:22,400 --> 00:19:25,040 Izgleda da sam stečen popis u boljem stanju. 579 00:19:25,040 --> 00:19:26,330 >> Sada, oni su dobri. 580 00:19:26,330 --> 00:19:28,480 Idem dalje, četiri i šest, izgleda dobro. 581 00:19:28,480 --> 00:19:29,110 Nije problem. 582 00:19:29,110 --> 00:19:30,440 Šest i osam, u redu. 583 00:19:30,440 --> 00:19:31,860 Osam i jedan, drugi problem. 584 00:19:31,860 --> 00:19:34,750 Jer ono što je istina o osam i jedan? 585 00:19:34,750 --> 00:19:36,990 Jedan dolazi prije osam, pa što da radimo? 586 00:19:36,990 --> 00:19:38,090 Idemo mijenjati ove dvije. 587 00:19:38,090 --> 00:19:39,316 Od jedne do osam. 588 00:19:39,316 --> 00:19:40,690 I sada, ja ću nastaviti. 589 00:19:40,690 --> 00:19:42,030 Idem da gleda naprijed. 590 00:19:42,030 --> 00:19:42,840 I da vidimo što se događa. 591 00:19:42,840 --> 00:19:44,680 Osam i tri, od Naravno, iz reda. 592 00:19:44,680 --> 00:19:45,815 Idemo zamjenu. 593 00:19:45,815 --> 00:19:46,940 Osam i sedam, naravno. 594 00:19:46,940 --> 00:19:47,481 Iz reda. 595 00:19:47,481 --> 00:19:48,280 Idemo zamjenu. 596 00:19:48,280 --> 00:19:49,940 Osam i pet, naravno, neka zamjena. 597 00:19:49,940 --> 00:19:50,560 U redu. 598 00:19:50,560 --> 00:19:51,880 Popis je sortiran. 599 00:19:51,880 --> 00:19:53,060 Da? 600 00:19:53,060 --> 00:19:54,280 >> U redu, očito nije. 601 00:19:54,280 --> 00:19:55,860 Ali, to je malo bolje, zar ne? 602 00:19:55,860 --> 00:19:57,270 Zbog obavijesti što se dogodilo. 603 00:19:57,270 --> 00:20:01,749 Svaki put smo izvršili zamjenu, a manji Broj vrsta procjednim na taj način, 604 00:20:01,749 --> 00:20:03,790 i veći broj procjednim na ovaj način, ili ćemo 605 00:20:03,790 --> 00:20:06,880 početi govoriti u mjehurićima na lijevo ili u obliku mjehurića na desnoj strani. 606 00:20:06,880 --> 00:20:10,080 >> Sada, to nije dovoljno, jer u najboljem broj možda 607 00:20:10,080 --> 00:20:11,990 su se preselili jedan spot naprijed, ili u najgorem slučaju, 608 00:20:11,990 --> 00:20:13,880 broj može imati dalje preselio prvo mjesto. 609 00:20:13,880 --> 00:20:16,369 Pa znate što, ova vrsta od radio prilično dobro do sada. 610 00:20:16,369 --> 00:20:17,410 Dopustite mi samo probati ponovno. 611 00:20:17,410 --> 00:20:18,880 Dva i četiri, oni su u redu. 612 00:20:18,880 --> 00:20:20,180 Četiri i šest, oni su u redu. 613 00:20:20,180 --> 00:20:21,790 Šest i jedan, iz reda. 614 00:20:21,790 --> 00:20:23,007 Tako ćemo vas dvije zamijeniti. 615 00:20:23,007 --> 00:20:25,840 A sada, primijetiti problem je počinju da se malo bolje opet. 616 00:20:25,840 --> 00:20:27,006 Šest i tri, iz reda. 617 00:20:27,006 --> 00:20:28,100 Ajmo vas dvojica zamijene. 618 00:20:28,100 --> 00:20:29,730 Šest i sedam, ti si dobar. 619 00:20:29,730 --> 00:20:32,230 Sedam i pet, naravno, iz reda. 620 00:20:32,230 --> 00:20:33,920 Sedam i osam, u redu. 621 00:20:33,920 --> 00:20:36,470 I sad, ja možda trebati učiniti još nekoliko puta. 622 00:20:36,470 --> 00:20:39,830 A u stvari, mislim za sebe možda koliko puta maksimalno 623 00:20:39,830 --> 00:20:41,330 Možda sam prošetati natrag i naprijed? 624 00:20:41,330 --> 00:20:42,390 >> Mi ćemo se vratiti na to. 625 00:20:42,390 --> 00:20:43,700 Dakle, dva i četiri su još uvijek u redu. 626 00:20:43,700 --> 00:20:44,940 Četiri i jedan, nope. 627 00:20:44,940 --> 00:20:45,747 Dakle, neka je swap. 628 00:20:45,747 --> 00:20:47,830 I opet, primijetit vizualno jedna je vrsta mjehurića 629 00:20:47,830 --> 00:20:49,163 lijevo, gdje bi trebao biti. 630 00:20:49,163 --> 00:20:50,010 Četiri i tri zamjena. 631 00:20:50,010 --> 00:20:51,330 Četiri i šest. 632 00:20:51,330 --> 00:20:53,100 Šest i pet zamjena. 633 00:20:53,100 --> 00:20:53,959 Šest i sedam. 634 00:20:53,959 --> 00:20:55,000 Sedam i osam su dobri. 635 00:20:55,000 --> 00:20:55,500 >> Dobra. 636 00:20:55,500 --> 00:20:58,460 Mi dobivamo još bolji. 637 00:20:58,460 --> 00:20:59,130 Tako ćemo vidjeti. 638 00:20:59,130 --> 00:21:00,940 Sada imamo dva i jedan. 639 00:21:00,940 --> 00:21:02,520 Naravno, zamjenu. 640 00:21:02,520 --> 00:21:07,520 Dva i tri, tri i četiri, a četiri pet, šest i sedam, sedam i osam. 641 00:21:07,520 --> 00:21:08,020 Dobra. 642 00:21:08,020 --> 00:21:08,730 I znate što? 643 00:21:08,730 --> 00:21:11,190 Zato sam napravio jednu promjenu postoji, neka mi učiniti jednu duševne ček. 644 00:21:11,190 --> 00:21:13,023 Dopustite mi da ide sve na putu natrag na početak. 645 00:21:13,023 --> 00:21:13,680 U REDU. 646 00:21:13,680 --> 00:21:14,750 Jedan, two-- Yup, vidjet? 647 00:21:14,750 --> 00:21:15,870 Nešto nije bilo u redu. 648 00:21:15,870 --> 00:21:18,420 Tri, četiri, pet, šest, sedam, osam. 649 00:21:18,420 --> 00:21:21,920 I u ovom posljednjem prolazu, su li zadovoljni s mojim sada 650 00:21:21,920 --> 00:21:23,830 tvrdeći da razvrstava? 651 00:21:23,830 --> 00:21:24,330 U REDU. 652 00:21:24,330 --> 00:21:25,880 Vizualno, to je apsolutno točno. 653 00:21:25,880 --> 00:21:28,410 No, ono što funkcionalno nije također samo dogodilo 654 00:21:28,410 --> 00:21:31,870 u tom zadnjem prolazu koji vam omogućuje potvrditi da je ovaj popis je zaista 655 00:21:31,870 --> 00:21:32,660 razvrstani? 656 00:21:32,660 --> 00:21:34,477 >> Što sam učiniti ili ne učiniti ovo posljednje točno? 657 00:21:34,477 --> 00:21:35,810 PUBLIKA: Nije bilo promjena. 658 00:21:35,810 --> 00:21:36,120 DAVID J. Malan: Žao nam je? 659 00:21:36,120 --> 00:21:37,070 PUBLIKA: Nema promjena. 660 00:21:37,070 --> 00:21:38,653 DAVID J. Malan: nije bilo promjena. 661 00:21:38,653 --> 00:21:41,947 Dakle, to bi bilo glupo od mene učiniti da isti algoritam ponovno 662 00:21:41,947 --> 00:21:43,780 ako nisam napraviti bilo mijenja prvi put. 663 00:21:43,780 --> 00:21:45,160 A država nije promijenilo. 664 00:21:45,160 --> 00:21:47,576 Sigurno neću napraviti Sve promjene po drugi put. 665 00:21:47,576 --> 00:21:49,820 I tako, to je sigurno sada reći, Popis je sortiran. 666 00:21:49,820 --> 00:21:52,069 >> I doista, ovo je sad nešto što ćemo općenito 667 00:21:52,069 --> 00:21:56,900 Poziv bubble sort, pri čemu parovima, opet ispraviti pogreške, 668 00:21:56,900 --> 00:22:00,210 i opet, i opet, i ti zadržati ide natrag i naprijed, 669 00:22:00,210 --> 00:22:03,370 i natrag i naprijed, dok ne ne pravimo takve zamjene, u kojem trenutku 670 00:22:03,370 --> 00:22:07,089 možete biti sigurni, da, ja završio popravljajući sve pogreške. 671 00:22:07,089 --> 00:22:08,630 Idemo resetirati i probati drugi pristup. 672 00:22:08,630 --> 00:22:11,590 Ako ti dečki mogli vratiti u redoslijed ste bili prije nekoliko trenutaka, 673 00:22:11,590 --> 00:22:13,780 koji je izgledao ovako. 674 00:22:13,780 --> 00:22:17,640 Sada, neka je uzeti pristupu malo više poput ispita knjige, 675 00:22:17,640 --> 00:22:21,122 gdje smo bili stalno odabirom slovo abecede 676 00:22:21,122 --> 00:22:22,830 da smo vrsta htjeli baviti sljedeći. 677 00:22:22,830 --> 00:22:26,420 Možda je to bila visoka pismo, Poput, ili niskim slova Z. 678 00:22:26,420 --> 00:22:28,170 >> Dakle, svi su još u tom cilju. 679 00:22:28,170 --> 00:22:29,800 I sada neka mi to učiniti. 680 00:22:29,800 --> 00:22:34,880 Pogledajmo znam imam osam brojeva ovdje. 681 00:22:34,880 --> 00:22:37,410 Ja ću ići naprijed i Samo namjerno odabrali 682 00:22:37,410 --> 00:22:38,520 najmanji elementi. 683 00:22:38,520 --> 00:22:38,760 Pravo? 684 00:22:38,760 --> 00:22:39,801 To se čini intuitivno previše. 685 00:22:39,801 --> 00:22:42,560 Zašto ne mogu naći najmanji Element, stavite ga gdje mu je i mjesto, 686 00:22:42,560 --> 00:22:45,280 onda se sljedeći najmanji element, stavio je gdje mu je i mjesto, a samo ponoviti. 687 00:22:45,280 --> 00:22:46,820 >> Jer intuitivno, koja bi trebala raditi previše. 688 00:22:46,820 --> 00:22:48,441 Dakle četiri, to je prilično mali broj. 689 00:22:48,441 --> 00:22:49,940 Idem se sjetiti gdje je to. 690 00:22:49,940 --> 00:22:50,523 Čekaj malo. 691 00:22:50,523 --> 00:22:51,577 Dva manja. 692 00:22:51,577 --> 00:22:53,910 Dopustite mi sada sjetiti gdje dva je, i zaboraviti o četiri. 693 00:22:53,910 --> 00:22:55,050 Mi ćemo se bave kasnije. 694 00:22:55,050 --> 00:22:56,460 Šest, ne zanima me. 695 00:22:56,460 --> 00:22:57,810 Osam, nisam zainteresiran. 696 00:22:57,810 --> 00:22:59,780 Jedan je moj novi mali broj. 697 00:22:59,780 --> 00:23:01,470 Zato ću se sjetiti gdje se nalazi. 698 00:23:01,470 --> 00:23:02,534 Tri, ne zanima. 699 00:23:02,534 --> 00:23:03,450 Sedam, nije zainteresiran. 700 00:23:03,450 --> 00:23:04,530 Pet, ne zanima. 701 00:23:04,530 --> 00:23:07,390 >> Dakle, bez pada off pozornica ove godine, 702 00:23:07,390 --> 00:23:09,890 Idem zgrabite broj one-- i što je vaše ime ponovo? 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 A ako bi mogao mi se pridružiti na početak popisa, 706 00:23:13,540 --> 00:23:14,870 neka vas staviti gdje ti je mjesto. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- što je vaše 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 putu. 710 00:23:18,191 --> 00:23:23,490 Dakle, prije nego što je Stefan rješava taj Problem, što nam je činiti? 711 00:23:23,490 --> 00:23:25,412 Što ćemo učiniti s Stefan? 712 00:23:25,412 --> 00:23:27,269 >> PUBLIKA: [nečujan]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. Malan: U redu. 714 00:23:28,060 --> 00:23:28,850 Tako smo mogli učiniti. 715 00:23:28,850 --> 00:23:31,730 Mogli bismo vrsta uzeti Stefana i njegovog četiri, i samo ga stavite u varijablu 716 00:23:31,730 --> 00:23:33,530 i držite na njemu za neki iznos vremena, 717 00:23:33,530 --> 00:23:35,220 time prostor za broj jedan. 718 00:23:35,220 --> 00:23:36,280 I to nije loše. 719 00:23:36,280 --> 00:23:39,270 Mogao bih predložiti, zašto ne upravo smo stavili Stefana ovdje? 720 00:23:39,270 --> 00:23:41,610 Zašto bi to krši jedno od ideja smo počeli 721 00:23:41,610 --> 00:23:44,830 govori o posljednjem vremenu, prošli tjedan? 722 00:23:44,830 --> 00:23:45,330 Da? 723 00:23:45,330 --> 00:23:45,740 >> PUBLIKA: [nečujan]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. Malan: Nema indeks za to. 725 00:23:46,860 --> 00:23:49,735 Ako mislite da je to, doista, kao niz, ovo je kao negativne jedan, 726 00:23:49,735 --> 00:23:52,900 tako da nema memorije zapravo ovdje ako je to doista niz, 727 00:23:52,900 --> 00:23:55,090 kao što smo proglasili prošlog tjedna u predavanju. 728 00:23:55,090 --> 00:23:56,250 Dakle, mi ne bi trebali to učiniti. 729 00:23:56,250 --> 00:23:57,340 Možemo ga pohraniti u varijablu. 730 00:23:57,340 --> 00:23:57,820 >> Ili znaš što? 731 00:23:57,820 --> 00:23:59,153 Čuo sam netko drugi to sugeriraju. 732 00:23:59,153 --> 00:24:01,020 Što još možemo učiniti s Stefan? 733 00:24:01,020 --> 00:24:03,770 Zašto ne bismo jednostavno ga iseliti i stavite ga tamo gdje je broj jedan. 734 00:24:03,770 --> 00:24:05,170 Dakle, ako želite ići tamo. 735 00:24:05,170 --> 00:24:07,300 I doista, ovo je prilično dobro rješenje. 736 00:24:07,300 --> 00:24:10,480 Sada, s jedne strane, imam vrsta od samog problema gore. 737 00:24:10,480 --> 00:24:13,650 Četiri je sada dalje odakle bi trebao biti. 738 00:24:13,650 --> 00:24:14,900 To bi trebao biti prema Vezni. 739 00:24:14,900 --> 00:24:16,100 >> Ali znate što? 740 00:24:16,100 --> 00:24:17,630 To je mogla biti loša sreća. 741 00:24:17,630 --> 00:24:18,822 Možda broj osam bio ovdje. 742 00:24:18,822 --> 00:24:20,530 I tako, možda bismo dobivši sretni, 743 00:24:20,530 --> 00:24:22,460 i gurnula osam bliže kraju. 744 00:24:22,460 --> 00:24:24,710 Tako je na kraju krajeva, To je vrsta sve prosjeci van. 745 00:24:24,710 --> 00:24:26,085 Ne trebate brinuti oko četiri. 746 00:24:26,085 --> 00:24:29,400 Sve mi je stalo sada je odabirom najmanji element. 747 00:24:29,400 --> 00:24:32,030 >> A sada, što ću učiniti je zaboraviti broj jedan 748 00:24:32,030 --> 00:24:35,160 stalno, jer znam da Popis iza mene je sada riješeno. 749 00:24:35,160 --> 00:24:36,720 Dakle, moj popis je prethodno veličine osam. 750 00:24:36,720 --> 00:24:37,720 Sada, to je veličine sedam. 751 00:24:37,720 --> 00:24:40,340 Dakle, moj problem je dobivanje manja, iako linearno. 752 00:24:40,340 --> 00:24:43,022 Pa sad, ja idem za odabir trenutna najmanji element, dva. 753 00:24:43,022 --> 00:24:46,520 Šest, osam, četiri, tri, sedam, pet. 754 00:24:46,520 --> 00:24:47,770 To je najmanji element. 755 00:24:47,770 --> 00:24:49,416 Pa što ću učiniti with-- što je vaše ime ponovo? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Josip. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. Malan: Josip? 758 00:24:50,085 --> 00:24:52,000 Idemo ostaviti Josipa na mjestu. 759 00:24:52,000 --> 00:24:54,842 Sada ću se pretvarati da su ti dečki are-- dobro, 760 00:24:54,842 --> 00:24:56,550 Znam da ove dvije već razvrstani. 761 00:24:56,550 --> 00:24:58,424 Idemo sada usredotočiti na Ostatak popisa. 762 00:24:58,424 --> 00:25:00,080 Šest je trenutno najmanji. 763 00:25:00,080 --> 00:25:01,190 Osam je veći. 764 00:25:01,190 --> 00:25:02,970 Četiri je sada trenutni najmanji. 765 00:25:02,970 --> 00:25:04,762 Tri je sada trenutni najmanji. 766 00:25:04,762 --> 00:25:07,720 I tako sada, ja ću odabrati tri, tko is-- što je vaše ime ponovo? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. Malan: Serena, ako bi zgrabite svoj broj i 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 Dođi natrag, a mi smo će zamijeniti one dvije. 772 00:25:15,220 --> 00:25:17,360 I sada, neka je stavi ovo na autopilotu. 773 00:25:17,360 --> 00:25:21,589 Ja ću ići i prepustiti vama odaberite sljedeći najmanji elementi. 774 00:25:21,589 --> 00:25:22,380 Dun, mrk, mrk, mrk. 775 00:25:22,380 --> 00:25:24,560 Broj četiri, što bi trebalo učiniti? 776 00:25:24,560 --> 00:25:26,261 Izvrsno. 777 00:25:26,261 --> 00:25:27,760 Sada ću napraviti još sredinu. 778 00:25:27,760 --> 00:25:28,590 Dun, mrk, mrk, mrk. 779 00:25:28,590 --> 00:25:31,465 Vidim pet je sljedeći najmanji. 780 00:25:31,465 --> 00:25:32,840 Sada ću uzeti još sredinu. 781 00:25:32,840 --> 00:25:33,631 Dun, mrk, mrk, mrk. 782 00:25:33,631 --> 00:25:34,880 Šest je najmanji. 783 00:25:34,880 --> 00:25:35,520 Dobra. 784 00:25:35,520 --> 00:25:36,585 Sedam je najmanji. 785 00:25:36,585 --> 00:25:37,085 Bez promjena. 786 00:25:37,085 --> 00:25:38,630 Osam je najmanji. 787 00:25:38,630 --> 00:25:39,170 Gotovo. 788 00:25:39,170 --> 00:25:43,900 >> Dakle, ono što smo upravo učinio iterativno odabira jednog elementa za drugim 789 00:25:43,900 --> 00:25:47,230 se provesti nešto što smo će formalizirati kao izbor vrste. 790 00:25:47,230 --> 00:25:49,120 I to je možda čak i jednostavnije objasniti, 791 00:25:49,120 --> 00:25:51,310 u koji doslovno sve vas želim se samo zadržati 792 00:25:51,310 --> 00:25:54,700 ide natrag i naprijed kroz popis odabira, sljedeći najmanji element, 793 00:25:54,700 --> 00:25:55,720 dok ste učinili. 794 00:25:55,720 --> 00:25:58,650 >> Dakle, to je još jednostavnije, možda intuitivno, nego prošle. 795 00:25:58,650 --> 00:26:00,020 Pokušajmo jedan zadnji. 796 00:26:00,020 --> 00:26:03,060 Ako vi sami mogli poništiti u sljedećim položajima 797 00:26:03,060 --> 00:26:08,600 posljednji put, neka je vidjeti ako ne možemo Sada formalizirati jedan drugi pristup. 798 00:26:08,600 --> 00:26:12,857 U stvari, netko bi tamo bih predložiti 799 00:26:12,857 --> 00:26:14,440 kako drugačije možemo ići o događaj ovaj? 800 00:26:14,440 --> 00:26:17,439 Bez bacanje iz poštapalice ili vrsta odgovora koji su već poznati, 801 00:26:17,439 --> 00:26:19,689 Samo intuitivno, što možemo učiniti? 802 00:26:19,689 --> 00:26:21,635 >> PUBLIKA: [nečujan]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. Malan: Da. 804 00:26:22,510 --> 00:26:24,620 Dakle, postoji neka velika intuicija tamo. 805 00:26:24,620 --> 00:26:28,020 Dobre stvari čini se dogoditi do sada u računalnoj znanosti, kada podijelimo 806 00:26:28,020 --> 00:26:30,832 i osvojiti problem dijeljenja je na pola i pola-pola. 807 00:26:30,832 --> 00:26:32,540 I tako doista smo mogla početi raditi. 808 00:26:32,540 --> 00:26:35,754 A u stvari, to će biti, ćemo vidi, jedan od naših najboljih rješenja još. 809 00:26:35,754 --> 00:26:37,420 Ali neka se vratiti na to prije dugo. 810 00:26:37,420 --> 00:26:40,500 U stvari, idemo raditi da malo kasnije ovog tjedna. 811 00:26:40,500 --> 00:26:42,180 Što drugo bi moglo radimo riješiti ovo? 812 00:26:42,180 --> 00:26:44,647 Dakle, svatko je ovdje u naizgled nasumičnim redoslijedom. 813 00:26:44,647 --> 00:26:45,230 Znaš što? 814 00:26:45,230 --> 00:26:48,320 Umjesto ići naprijed i natrag, natrag i naprijed, natrag i naprijed 815 00:26:48,320 --> 00:26:50,624 svaki put, to se osjeća kao Radim puno hodanja. 816 00:26:50,624 --> 00:26:52,790 Zašto ne bih jednostavno početi na početak popisa, 817 00:26:52,790 --> 00:26:54,960 i samo staviti četiri gdje pripada? 818 00:26:54,960 --> 00:26:59,680 Pa neka mi pretpostavljamo na trenutak da moj popis je samo to prvi element. 819 00:26:59,680 --> 00:27:04,937 Je četiri razvrstani u ovom trenutku u vremenu, ako sve što je stalo je sve tu? 820 00:27:04,937 --> 00:27:06,520 To je vrsta trivijalno istinito, zar ne? 821 00:27:06,520 --> 00:27:10,000 Kao popisa koji sadrži jedan broj, a da broj četiri je očito razvrstani. 822 00:27:10,000 --> 00:27:13,070 >> Pa neka mi samo propisuje da je ovaj popis je sortiran. 823 00:27:13,070 --> 00:27:15,090 Ali sada imam ostatak ovog popisa. 824 00:27:15,090 --> 00:27:17,240 Pa sad, sam susret dva. 825 00:27:17,240 --> 00:27:21,690 Gdje se dvoje očito pripada s obzirom na četiri? 826 00:27:21,690 --> 00:27:22,580 Prije četiri. 827 00:27:22,580 --> 00:27:23,862 Pa što mogu učiniti ovdje? 828 00:27:23,862 --> 00:27:24,820 Kako se zoveš opet? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Josip. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. Malan: Josip, ako bi mogao korak natrag 831 00:27:26,030 --> 00:27:27,790 samo na trenutak sa svojim brojem. 832 00:27:27,790 --> 00:27:31,130 A sada ono što bi trebalo Stefan učiniti ovdje? 833 00:27:31,130 --> 00:27:33,720 Idemo pomak Stefana ovdje. 834 00:27:33,720 --> 00:27:35,520 A sada, neka dođe Josip ovdje. 835 00:27:35,520 --> 00:27:39,660 A sada, dopustite mi tvrde da ovdje sve je riješeno. 836 00:27:39,660 --> 00:27:42,474 Dakle, slično kao rezultat, ali bitno drugačiji pristup. 837 00:27:42,474 --> 00:27:44,140 Nisam ni gledao što je tamo dolje. 838 00:27:44,140 --> 00:27:46,310 Ja samo držati uzimajući elemente kao oni predao meni, 839 00:27:46,310 --> 00:27:47,240 i nositi se s njima. 840 00:27:47,240 --> 00:27:48,330 >> Pa sad, vidim broj šest. 841 00:27:48,330 --> 00:27:51,110 Odakle broj šest pripada? 842 00:27:51,110 --> 00:27:53,250 Imamo dvije, četiri, šest. 843 00:27:53,250 --> 00:27:54,800 Točno gdje je ona sada. 844 00:27:54,800 --> 00:27:57,750 Tako ćemo ostaviti na miru, a sad tvrde da je ovaj dio popisa 845 00:27:57,750 --> 00:27:58,772 sada je riješeno. 846 00:27:58,772 --> 00:28:01,230 I tako, to se osjeća bitno razlikuje po tome što sam upravo 847 00:28:01,230 --> 00:28:05,230 kreće kroz popis ovdje linearno, a ja nikada neću udvostručenje natrag. 848 00:28:05,230 --> 00:28:05,730 Da. 849 00:28:05,730 --> 00:28:06,230 U redu. 850 00:28:06,230 --> 00:28:08,190 Dakle osam, gdje si ti? 851 00:28:08,190 --> 00:28:08,730 Upravo ovdje. 852 00:28:08,730 --> 00:28:09,310 Savršeno. 853 00:28:09,310 --> 00:28:10,210 Tako sada, jedan. 854 00:28:10,210 --> 00:28:10,900 Uh oh. 855 00:28:10,900 --> 00:28:13,010 To se osjeća kao da je će biti skuplji. 856 00:28:13,010 --> 00:28:15,690 Sada, u prethodnom algoritmu, Upravo sam zamijenio ljude. 857 00:28:15,690 --> 00:28:18,648 Tako sam mogao ga skroz na početak, ali onda se preselio Josipa. 858 00:28:18,648 --> 00:28:21,450 Ali ako sam premjestiti Josipa, sada ono će biti u redu? 859 00:28:21,450 --> 00:28:24,250 >> Sada, ja sam nekako undone-- imam uzeti jedan korak naprijed i zatim 860 00:28:24,250 --> 00:28:26,300 jedan korak natrag, jer sada Josip će biti iz reda. 861 00:28:26,300 --> 00:28:26,830 Tako ćemo to učiniti. 862 00:28:26,830 --> 00:28:29,150 Ako bi mogao preuzeti broj jedan i korak natrag za samo trenutak. 863 00:28:29,150 --> 00:28:30,490 Kako možemo put-- ono je svoje ime ponovno? 864 00:28:30,490 --> 00:28:31,130 >> Annan: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. Malan: Annan u mjestu? 866 00:28:32,610 --> 00:28:36,091 Ono što treba da se desi u odnosu za dvije, četiri, šest, osam i? 867 00:28:36,091 --> 00:28:37,570 Svi oni trebaju pomaknuti. 868 00:28:37,570 --> 00:28:42,590 Dakle, ako osam bih pomak Prvo, zatim šest, zatim četiri, zatim dva. 869 00:28:42,590 --> 00:28:45,380 A onda Annan, ako želite željeli doći ovdje, dobro. 870 00:28:45,380 --> 00:28:47,760 Ali ovdje, upravo smo vrsta platio cijenu 871 00:28:47,760 --> 00:28:49,510 na drugom mjestu u algoritmu. 872 00:28:49,510 --> 00:28:52,550 Dok zadnji put s izborom sortirati, pa čak i mjehur vrsta, 873 00:28:52,550 --> 00:28:54,700 Hodam natrag naprijed, natrag i naprijed, 874 00:28:54,700 --> 00:28:58,360 što svakako se zbroje Vremenski gledano, i doslovno postupno. 875 00:28:58,360 --> 00:29:00,660 >> Ubacivanje vrsta, na prvi pogled, izgleda kao da je 876 00:29:00,660 --> 00:29:05,150 super pametniji, u to sam samo što sporo, inkrementalni napredak, 877 00:29:05,150 --> 00:29:07,120 ali neću to natrag i naprijed. 878 00:29:07,120 --> 00:29:09,410 Ali ako je netko doista iz reda, obavijesti 879 00:29:09,410 --> 00:29:10,840 sve djelo samo sam morao učiniti. 880 00:29:10,840 --> 00:29:14,750 Morao sam da se presele pola popisa samo da bi se napravilo mjesta za broj jedan. 881 00:29:14,750 --> 00:29:16,790 Tako da je isti iznos rada do sada je 882 00:29:16,790 --> 00:29:18,690 osjeća, samo drugačiji tip posla. 883 00:29:18,690 --> 00:29:19,370 >> Idemo dalje. 884 00:29:19,370 --> 00:29:22,657 Dakle, sada znamo da su svi od jedne do osam su razvrstani. 885 00:29:22,657 --> 00:29:23,740 Evo, ja imam broj tri. 886 00:29:23,740 --> 00:29:25,864 Ako želite pokupiti broj tri, korak natrag jedan. 887 00:29:25,864 --> 00:29:28,260 A što vi trebate učiniti? 888 00:29:28,260 --> 00:29:28,760 Yep. 889 00:29:28,760 --> 00:29:33,070 Dakle, to je još jedan, dva, tri koraka. 890 00:29:33,070 --> 00:29:36,010 Tri jedinice vremena koji samo koštaju mene, tako da tri može sada stati. 891 00:29:36,010 --> 00:29:37,460 Konačno, sedam. 892 00:29:37,460 --> 00:29:39,730 >> Idemo naprijed i imati što se korak unatrag. 893 00:29:39,730 --> 00:29:42,780 To je samo ide da nas košta jedna jedinica vremena, ali to je u redu. 894 00:29:42,780 --> 00:29:44,170 A sada, pet će biti malo skuplji. 895 00:29:44,170 --> 00:29:45,340 Ako želite korak natrag. 896 00:29:45,340 --> 00:29:48,380 Moramo premjestiti osam, i sedam, a šest. 897 00:29:48,380 --> 00:29:50,749 A onda su svi sada riješeno. 898 00:29:50,749 --> 00:29:52,290 Tako velika ruka našim volonterima ovdje. 899 00:29:52,290 --> 00:29:53,554 Hvala vam puno. 900 00:29:53,554 --> 00:29:56,220 >> [PLJESAK] 901 00:29:56,220 --> 00:29:56,860 >> Hvala svima. 902 00:29:56,860 --> 00:29:57,520 Hvala svima. 903 00:29:57,520 --> 00:30:02,940 Pa da vidimo sad koliko skupi sve to bilo. 904 00:30:02,940 --> 00:30:06,210 Razmotrimo možda Najjednostavniji od njih, mjehur vrsta. 905 00:30:06,210 --> 00:30:09,950 A ja kažem najjednostavnije, samo zato možete ga riješiti pohlepno tako jednostavno 906 00:30:09,950 --> 00:30:11,660 popraviti u parovima problem ovdje. 907 00:30:11,660 --> 00:30:13,720 Fix u parovima problema Ovdje, opet i opet 908 00:30:13,720 --> 00:30:17,680 i opet, ponavlja onoliko puta koliko je zapravo potrebno. 909 00:30:17,680 --> 00:30:21,050 >> Tako ispada da je sa mjehurić vrsta, dobro, 910 00:30:21,050 --> 00:30:25,820 koliko koraka moram preuzeti Prvi prolaz tog algoritma? 911 00:30:25,820 --> 00:30:30,850 Možda take-- idemo see-- jedan, dva, tri, četiri, pet, šest, sedam. 912 00:30:30,850 --> 00:30:32,190 I tu je osam elemenata ovdje. 913 00:30:32,190 --> 00:30:35,280 Dakle, to je kao n minus 1 koraka do dobiti od početka popisa 914 00:30:35,280 --> 00:30:36,380 na kraju liste. 915 00:30:36,380 --> 00:30:41,350 >> Ali odabira vrste, podsjetiti da sam i opet odabirom elemenata 916 00:30:41,350 --> 00:30:44,590 i opet to je najmanja, Ja sam stavljajući ga na mjesto, 917 00:30:44,590 --> 00:30:46,616 ali onda nisam gleda iza mene opet. 918 00:30:46,616 --> 00:30:49,490 Dakle, mislim da je malo jasnije Tada je prvi put, mogao bih 919 00:30:49,490 --> 00:30:52,680 moraju poduzeti sve n minus 1 korake pronaći najmanji element. 920 00:30:52,680 --> 00:30:55,920 Onda sam ih staviti na mjesto, a ja deložirati tko je bio ovdje prije. 921 00:30:55,920 --> 00:30:57,500 >> Ali onda ja ne moram zadržati gledajući tog elementa, 922 00:30:57,500 --> 00:30:59,040 jer znam da je Već najmanji. 923 00:30:59,040 --> 00:31:01,581 Pa sad, ja mogu gledati na samo sedam elementi, zatim šest elementi, 924 00:31:01,581 --> 00:31:03,290 onda pet elemenata, zatim četiri elementa. 925 00:31:03,290 --> 00:31:06,900 I tako matematički, ako je n broj elemenata ili brojeva 926 00:31:06,900 --> 00:31:11,990 da smo započeli s, što možete zamisliti da je to isto kao n minus 1, 927 00:31:11,990 --> 00:31:14,250 plus n minus 2 koraka, plus n minus 3 koraka, 928 00:31:14,250 --> 00:31:16,780 plus minus N 4 koraka, sve Način dolje samo jednom koraku. 929 00:31:16,780 --> 00:31:18,160 I ja sam na moj zadnji osobi. 930 00:31:18,160 --> 00:31:20,650 >> A ako se sjetiti da je puno od statistike knjige ili matematičke knjige 931 00:31:20,650 --> 00:31:24,730 imaju one formule na Tvrdi leđa ili ispred njih, 932 00:31:24,730 --> 00:31:27,690 ispada da ove serije može se izraziti jednostavnije 933 00:31:27,690 --> 00:31:28,857 kao n puta n minus 1 preko 2. 934 00:31:28,857 --> 00:31:31,273 I to je u redu, ako to nije na čelu vašeg uma. 935 00:31:31,273 --> 00:31:32,420 No, to je zaista istina. 936 00:31:32,420 --> 00:31:34,449 To je samo jednostavniji način pisanja. 937 00:31:34,449 --> 00:31:36,240 A onda ako mislite natrag na osnovnoj školi, 938 00:31:36,240 --> 00:31:38,698 kada samo početi množenjem stvari, taj naravno, 939 00:31:38,698 --> 00:31:41,820 samo je n kvadrat minus n podijeljena 2. 940 00:31:41,820 --> 00:31:44,772 Sve što sam učinio je proširiti izrazi tamo. 941 00:31:44,772 --> 00:31:46,730 I tako ćemo prepisati ovu malo drugačije. 942 00:31:46,730 --> 00:31:49,780 To je n kvadrat podijeljen 2 minus n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Pa opet, ja sam samo vrsta primjene neki aritmetički pravila postoje. 944 00:31:53,270 --> 00:31:57,140 Ali primijetite da sada najveći izraz u ovom izrazu, da se tako izrazim, 945 00:31:57,140 --> 00:31:58,540 je da n na kvadrat. 946 00:31:58,540 --> 00:32:02,910 Pa da, to je n kvadrat podijeljen 2, minus n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Ali općenito, ako je n će biti velika vrijednost, 948 00:32:05,080 --> 00:32:08,740 Idem tvrde da n na kvadrat će biti dominantan čimbenik. 949 00:32:08,740 --> 00:32:10,490 To samo će biti veći doprinos 950 00:32:10,490 --> 00:32:12,877 broju koraka od N / 2. 951 00:32:12,877 --> 00:32:13,960 Dakle, što mi znači ova? 952 00:32:13,960 --> 00:32:16,795 Pokušajmo jednostavan primjer, čak iako math dobiva malo velika. 953 00:32:16,795 --> 00:32:20,210 >> Dakle, pretpostavimo da smo imali 1 milijuna ljudi na pozornici, ili 1 milijun stvari 954 00:32:20,210 --> 00:32:21,320 da želimo sortirati. 955 00:32:21,320 --> 00:32:23,730 Idemo plug milijun u točno toj formuli 956 00:32:23,730 --> 00:32:27,230 vidjeti koliko koraka je potrebno ukupno sortirati milijuna elemente pomoću recimo, 957 00:32:27,230 --> 00:32:28,560 Izbor vrsta. 958 00:32:28,560 --> 00:32:30,760 >> Tako ćemo imati istu formulu kao i prije. 959 00:32:30,760 --> 00:32:34,120 Ja bih plug milijuna, tako da sam se milijuna kvadrat podijeljeno sa 2, 960 00:32:34,120 --> 00:32:35,990 minus milijuna podijeljena 2. 961 00:32:35,990 --> 00:32:40,180 Ako ja tu matematiku unaprijed Ovdje imamo 500 milijardi 962 00:32:40,180 --> 00:32:47,460 minus 500.000, što daje nam 499999500000, 963 00:32:47,460 --> 00:32:49,270 što je prilično darn velika. 964 00:32:49,270 --> 00:32:54,370 >> U stvari, ako usporedite sada 499.000.000.000, 999 milijuna, 965 00:32:54,370 --> 00:33:01,210 500.000 protiv naše izvorne vrijednosti, 500 milijardi, to je tako prokleto blizu. 966 00:33:01,210 --> 00:33:06,850 Pravo? n na kvadrat podijeljen 2 daje us-- odnosno, n na kvadrat podijeljen 2 967 00:33:06,850 --> 00:33:08,370 dao nam 500 milijardi. 968 00:33:08,370 --> 00:33:13,510 To je prilično darn blizu na 499,999,500,000, 969 00:33:13,510 --> 00:33:17,970 što znači oduzimanjem off 500.000, ili općenitije, oduzimanjem off 970 00:33:17,970 --> 00:33:20,010 n na kvadrat, nije stvarno velika stvar. 971 00:33:20,010 --> 00:33:22,490 N na kvadrat čini to brojevi rastu jako brzo. 972 00:33:22,490 --> 00:33:25,790 >> Sada, ovo je važno samo ukoliko kao i mi, kao i računalnih znanstvenika, 973 00:33:25,790 --> 00:33:29,350 općenito neće brinuti toliko o nijansama tih formula 974 00:33:29,350 --> 00:33:31,400 i upravo ono što Točni odgovori su. 975 00:33:31,400 --> 00:33:33,390 Mi se brinemo samo to, znate što? 976 00:33:33,390 --> 00:33:37,810 Na kraju krajeva, ovaj formula je na red od n kvadrata. 977 00:33:37,810 --> 00:33:39,350 >> Da, mi smo dijeljenjem s 2 unutra. 978 00:33:39,350 --> 00:33:41,360 Da, mi smo oduzimanjem off n minus 2. 979 00:33:41,360 --> 00:33:46,860 Ali na kraju dana, pojam da nas stvarno boli i košta nas 980 00:33:46,860 --> 00:33:48,995 puno koraka je da trg pojam. 981 00:33:48,995 --> 00:33:51,370 I tako ono što računalni znanstvenik će općenito napraviti 982 00:33:51,370 --> 00:33:54,160 je ignorirati sve one manji pojmovi reda, 983 00:33:54,160 --> 00:33:56,900 i samo pogledajte onaj koji doprinosi najviše cijeni. 984 00:33:56,900 --> 00:34:00,530 >> I to je lijepo, jer možemo sada govoriti u mnogo većoj općenitosti 985 00:34:00,530 --> 00:34:02,470 o algoritmima, a može ih usporediti. 986 00:34:02,470 --> 00:34:04,550 A činjenica da sam Korištenjem ovog O je namjerno. 987 00:34:04,550 --> 00:34:06,680 Kada kažem na red od, ja sam konkretno 988 00:34:06,680 --> 00:34:09,560 koji se odnosi na nešto pozvao veliki O. I veliko O 989 00:34:09,560 --> 00:34:14,090 je zapis da računalo Znanstvenik koristi za opisivanje 990 00:34:14,090 --> 00:34:16,710 gornju granicu na nešto. 991 00:34:16,710 --> 00:34:21,150 >> Dakle, ako ti kažeš da je algoritam je u velikoj O n na kvadrat, 992 00:34:21,150 --> 00:34:23,380 kao što sam predložio samo Prije trenutak, to znači 993 00:34:23,380 --> 00:34:27,710 da u smislu njegovog trčanja Vrijeme i njegova učinkovitost, 994 00:34:27,710 --> 00:34:30,090 to traje na red n na kvadrat korake. 995 00:34:30,090 --> 00:34:31,420 Možda i više, možda i manje. 996 00:34:31,420 --> 00:34:33,435 Ali to je na red n na kvadrat. 997 00:34:33,435 --> 00:34:34,560 I to je gornja granica. 998 00:34:34,560 --> 00:34:36,530 To neće biti bolniji od toga. 999 00:34:36,530 --> 00:34:40,800 To neće biti n kubu ili 2 do n, ili nešto mnogo veće. 1000 00:34:40,800 --> 00:34:43,800 Ovo je gornja granica na što god to je trošak. 1001 00:34:43,800 --> 00:34:46,150 Pa s obzirom da je, neka je razmotriti samo nekoliko primjera. 1002 00:34:46,150 --> 00:34:49,820 A to je samo konačni popis vrlo česte trčanje puta 1003 00:34:49,820 --> 00:34:52,870 za algoritme koji je trebao biti ilustracije nekih stvari koje smo 1004 00:34:52,870 --> 00:34:53,600 već vidjeli. 1005 00:34:53,600 --> 00:34:58,060 >> Tako na primjer, u slučaju Izbor vrsta, što sam tvrdio ovdje 1006 00:34:58,060 --> 00:35:02,250 je da je izbor sortirati je trčanje Vrijeme je na red od n na kvadrat. 1007 00:35:02,250 --> 00:35:06,260 U najgorem slučaju, ja ću imati cijela hrpa slučajnih brojeva ovdje. 1008 00:35:06,260 --> 00:35:08,600 A kao što smo vidjeli matematički, ako sam držati hodanje 1009 00:35:08,600 --> 00:35:11,310 kroz popis, kroz Popis, odabirom sljedeći najmanji 1010 00:35:11,310 --> 00:35:14,410 i opet je element, ako sam zapravo napiši sve korake 1011 00:35:14,410 --> 00:35:18,750 Vodim kao što sam predložio formulaically prije, to je po nalogu n na kvadrat 1012 00:35:18,750 --> 00:35:20,370 koraka koje uzimam. 1013 00:35:20,370 --> 00:35:24,520 >> I ispada da mjehur sortiranje i umetanje sortiranje 1014 00:35:24,520 --> 00:35:27,370 su jednako spori u najgorem slučaju. 1015 00:35:27,370 --> 00:35:32,040 Razmislite, na primjer, umetanje vrsta, vrlo zadnji algoritam možemo rješavati, 1016 00:35:32,040 --> 00:35:35,500 koji nas je, pogledajte elementa, a zatim ga umetnite gdje mu je i mjesto. 1017 00:35:35,500 --> 00:35:38,720 A onda smo pogledali sljedećeg elementa, i umetnut gdje mu je i mjesto. 1018 00:35:38,720 --> 00:35:40,990 >> Dakle, razmislite najbolji mogući scenarij. 1019 00:35:40,990 --> 00:35:45,590 Pretpostavimo da je moja volonteri redati doslovce ovako, jedan do osam, 1020 00:35:45,590 --> 00:35:47,440 već riješeno. 1021 00:35:47,440 --> 00:35:51,300 Koliko koraka je umetanje vrsta će potrajati sortiranje osam osoba, 1022 00:35:51,300 --> 00:35:55,640 ako stignu na pozornici izgleda ovako? 1023 00:35:55,640 --> 00:35:57,410 >> Osam ljudi već riješeno. 1024 00:35:57,410 --> 00:35:58,760 I ja koristiti za umetanje vrsta. 1025 00:35:58,760 --> 00:36:02,180 Taj posljednji od algoritama. 1026 00:36:02,180 --> 00:36:03,640 Pa, neka je reenact jako brzo. 1027 00:36:03,640 --> 00:36:05,504 Dakle, ako počnem ovdje, vidim jedan. 1028 00:36:05,504 --> 00:36:06,420 Gdje je jedan pripada? 1029 00:36:06,420 --> 00:36:07,730 Spada ovdje. 1030 00:36:07,730 --> 00:36:08,330 Vidim dva. 1031 00:36:08,330 --> 00:36:09,660 Gdje se dvojica pripadaju? 1032 00:36:09,660 --> 00:36:10,260 Upravo ovdje. 1033 00:36:10,260 --> 00:36:10,900 Vidim tri. 1034 00:36:10,900 --> 00:36:11,920 Gdje tri pripada? 1035 00:36:11,920 --> 00:36:12,480 Upravo ovdje. 1036 00:36:12,480 --> 00:36:13,100 >> Vidim četiri. 1037 00:36:13,100 --> 00:36:13,600 Upravo ovdje. 1038 00:36:13,600 --> 00:36:15,660 Pet, šest, sedam, osam. 1039 00:36:15,660 --> 00:36:17,320 Nema razloga da se ponavljam. 1040 00:36:17,320 --> 00:36:21,260 I tako, koliko koraka da je u pogledu n? 1041 00:36:21,260 --> 00:36:23,870 To je na red n koraka, zar ne? n minus 1. 1042 00:36:23,870 --> 00:36:27,567 Ali sam uzeo linearni niz koraka, a sada sam učinio. 1043 00:36:27,567 --> 00:36:28,900 Tako da je najbolji slučaj, ipak. 1044 00:36:28,900 --> 00:36:29,983 Što o najgorem slučaju? 1045 00:36:29,983 --> 00:36:32,730 Ono osam su tamo, a sedam su tamo dolje, 1046 00:36:32,730 --> 00:36:35,840 i jedan i dva su ovdje, tako da da je popis zaista bili preokrenuti? 1047 00:36:35,840 --> 00:36:38,300 >> Pa, što će se dogoditi, istina ako je to broj? 1048 00:36:38,300 --> 00:36:41,300 I mi ćemo učiniti samo par primjera. 1049 00:36:41,300 --> 00:36:49,300 Što ako, doista, broj osam je ovdje, a number-- Ups. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Pa što ako je, doista, broj osam je sve ovdje, 1052 00:36:56,430 --> 00:36:57,790 i ja sam koristeći umetanje vrsta? 1053 00:36:57,790 --> 00:36:58,290 >> U REDU. 1054 00:36:58,290 --> 00:37:00,280 Ja tvrdim u ovom trenutku to je na mjestu. 1055 00:37:00,280 --> 00:37:03,152 Ali sada, seven-- gdje se sedam ići? 1056 00:37:03,152 --> 00:37:04,360 Naravno, to ide ovdje. 1057 00:37:04,360 --> 00:37:06,760 Pa moram premjestiti osam nad jednom mjestu. 1058 00:37:06,760 --> 00:37:08,554 Sada šest, gdje to ide? 1059 00:37:08,554 --> 00:37:09,220 Pa, u redu. 1060 00:37:09,220 --> 00:37:13,150 Sada moram premjestiti osam više mjesto, a sedam više mjesta, 1061 00:37:13,150 --> 00:37:14,440 a onda sam pasti dolje šest. 1062 00:37:14,440 --> 00:37:16,870 >> Dakle, prvi put, to trošak ja jedan korak popraviti stvari, 1063 00:37:16,870 --> 00:37:18,570 onda me koštalo dva koraka popraviti stvari. 1064 00:37:18,570 --> 00:37:20,370 Koliko koraka je to događa da se popraviti 1065 00:37:20,370 --> 00:37:22,720 stvari koje treba staviti pet na pravom mjestu? 1066 00:37:22,720 --> 00:37:23,340 Tri. 1067 00:37:23,340 --> 00:37:29,520 Jer sada moram premjestiti jedan, dva, tri. 1068 00:37:29,520 --> 00:37:32,430 Koliko koraka je da će potrajati staviti četiri na pravom mjestu? 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 >> I tako je matematički istovjetan ono što je opisano za odabir vrste. 1071 00:37:40,260 --> 00:37:42,130 Imamo ovu seriju to je samo raste. 1072 00:37:42,130 --> 00:37:45,650 1 plus 2 plus 3 plus 4, ili obratno, 7 plus 6 1073 00:37:45,650 --> 00:37:52,610 plus 5 plus 4 dodaje se za današnje svrhe na red n na kvadrat. 1074 00:37:52,610 --> 00:37:57,640 >> Pa neka mi propisuje da previše mjehurić sorta je također na n na kvadrat. 1075 00:37:57,640 --> 00:38:01,340 Jer mjehurića vrste, svaki Vrijeme idem kroz popis, 1076 00:38:01,340 --> 00:38:03,100 Vodim otprilike koliko koraka? 1077 00:38:03,100 --> 00:38:06,260 Svaki put kad sam doslovno hoda od tamo do tamo? 1078 00:38:06,260 --> 00:38:07,960 Oko n koraka. 1079 00:38:07,960 --> 00:38:12,650 Ali koliko puta sam možda morate proći kroz popis? 1080 00:38:12,650 --> 00:38:13,920 >> Pa, otprilike nje vrijeme. 1081 00:38:13,920 --> 00:38:15,680 Možda n minus 1, ali otprilike n puta. 1082 00:38:15,680 --> 00:38:16,430 Pa, zašto je to tako? 1083 00:38:16,430 --> 00:38:19,560 Pa, s bubble sort, ako možemo početi s bubble sort, 1084 00:38:19,560 --> 00:38:23,570 s popisa u najgore moguće Situacija, što je opet posve 1085 00:38:23,570 --> 00:38:25,550 unatrag, što će se dogoditi? 1086 00:38:25,550 --> 00:38:28,830 Idem kroz popis, i broj on pripada sve tamo. 1087 00:38:28,830 --> 00:38:33,280 >> No, s bubble sort, koliko se jedan premjestiti na moj prvi proći kroz popis? 1088 00:38:33,280 --> 00:38:36,620 Koliko mrlje on doći bliže ispravnom mjestu? 1089 00:38:36,620 --> 00:38:37,240 Samo jedan. 1090 00:38:37,240 --> 00:38:40,281 Dakle, ako ste vrsta razlog kroz to, svaki put kroz ovaj algoritam, 1091 00:38:40,281 --> 00:38:41,880 Davidovi uzimanje otprilike n koraka. 1092 00:38:41,880 --> 00:38:44,940 No, koliko prolazi kroz popis je to 1093 00:38:44,940 --> 00:38:49,060 uzeti za jedan balon u lijevo, gdje joj je i mjesto? 1094 00:38:49,060 --> 00:38:51,840 >> On je dobio da se presele poput, n prostori ovaj način. 1095 00:38:51,840 --> 00:38:57,960 Tako je samo napraviti sortiranje popisa, Moram prošetati natrag i naprijed n puta. 1096 00:38:57,960 --> 00:39:01,540 I svaki put, ja sam gledajući n elemenata. 1097 00:39:01,540 --> 00:39:05,410 Dakle, to n stvari n puta na redoslijed n na kvadrat. 1098 00:39:05,410 --> 00:39:07,220 >> Sada ćemo vidjeti u nekim od gaćice koje 1099 00:39:07,220 --> 00:39:10,440 su ugrađeni u CS50 je sljedeći problem postaviti, drugi pristup na njih, 1100 00:39:10,440 --> 00:39:13,490 ali za sada, neka je samo uzeti u obzir neke druge trčanje puta, 1101 00:39:13,490 --> 00:39:16,840 pogotovo ako su one sortiranje potrajati malo vremena da sjedne. 1102 00:39:16,840 --> 00:39:21,790 Što je algoritam smo već vidjeli koji vodi na red n koraka? 1103 00:39:21,790 --> 00:39:27,560 >> Što treba uzeti linearnu broj od koraka koje smo do sada vidjeli? 1104 00:39:27,560 --> 00:39:29,350 Što je to? 1105 00:39:29,350 --> 00:39:30,480 Potraga telefonski imenik. 1106 00:39:30,480 --> 00:39:31,390 Prvi algoritam. 1107 00:39:31,390 --> 00:39:31,560 Pravo? 1108 00:39:31,560 --> 00:39:33,650 Gdje smo linearno u potrazi za Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Doista. 1110 00:39:34,150 --> 00:39:37,180 Iz tjedna nula, kad sam počeo okreće jednu stranicu u isto vrijeme, 1111 00:39:37,180 --> 00:39:40,095 pa čak i sam rekao da je to neka vrsta linearnog osjećaj algoritma, 1112 00:39:40,095 --> 00:39:42,720 i imali smo tu sliku o ploča s ravnom crvene linije 1113 00:39:42,720 --> 00:39:44,678 i ravno žuta linije, oni su doista 1114 00:39:44,678 --> 00:39:46,810 algoritmi koji su u velikom O n. 1115 00:39:46,810 --> 00:39:50,680 >> Budući da pronađete Mike Smith u telefonu Knjiga od n stranica, u najgorem slučaju, 1116 00:39:50,680 --> 00:39:52,422 Možda me n korake poduzeti. 1117 00:39:52,422 --> 00:39:53,630 Što je uzimanje pohađanje? 1118 00:39:53,630 --> 00:39:55,790 Jedan dva tri četiri pet šest. 1119 00:39:55,790 --> 00:39:59,420 Što je vrijeme rada ove algoritam za uzimanje pohađanje? 1120 00:39:59,420 --> 00:40:03,070 Big O n, jer u teoriji sam moraju ukazati svima u sobi. 1121 00:40:03,070 --> 00:40:05,861 >> Sada kao stranu, što je Drugi optimizacija iz tjedna nula? 1122 00:40:05,861 --> 00:40:08,117 Dvije, četiri, šest, osam, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Računalni znanstvenik shvatiti, pričekajte minutu, 1124 00:40:10,200 --> 00:40:12,320 to je na red n podijeljena u dva koraka. 1125 00:40:12,320 --> 00:40:12,820 Pravo? 1126 00:40:12,820 --> 00:40:14,444 Jer ja radim dvoje ljudi u isto vrijeme. 1127 00:40:14,444 --> 00:40:17,015 Ali ćemo zanemariti oni niži pojmovi reda, 1128 00:40:17,015 --> 00:40:19,140 i samo ćemo se odbaciti razdijelite po 2, 1129 00:40:19,140 --> 00:40:21,830 i samo reći veliko O n za taj algoritam kao dobro. 1130 00:40:21,830 --> 00:40:22,760 >> Što je s ovim? 1131 00:40:22,760 --> 00:40:26,170 Mi ćemo preskočiti neke od njih, ali ono je algoritam koji je log n? 1132 00:40:26,170 --> 00:40:29,900 To je otprilike prijavite n koraka? 1133 00:40:29,900 --> 00:40:30,870 Podijeli pa vladaj. 1134 00:40:30,870 --> 00:40:31,369 Točno. 1135 00:40:31,369 --> 00:40:33,900 Poput telefonski imenik, primjerice u tjedan nula i ranije danas, 1136 00:40:33,900 --> 00:40:36,191 gdje smo podijeljeni problem opet i opet i opet. 1137 00:40:36,191 --> 00:40:39,070 To nacrtao smo na brodu u tjednu nula kao zakrivljena zelene linije, 1138 00:40:39,070 --> 00:40:41,460 i rekao mi da je dan logaritamska algoritam. 1139 00:40:41,460 --> 00:40:44,970 >> I doista, broj IT koraka potrebno izvršiti podijeli pa vladaj, 1140 00:40:44,970 --> 00:40:48,610 ili binarno traženje kako ćemo početi nazvavši ga, kao u telefonskom imeniku, 1141 00:40:48,610 --> 00:40:50,680 je na red i zapisnik koraka. 1142 00:40:50,680 --> 00:40:52,470 A to je malo čudan jedan. 1143 00:40:52,470 --> 00:40:54,910 >> Ono traje jedan korak, ili još specifičnije 1144 00:40:54,910 --> 00:40:56,240 konstantan broj koraka? 1145 00:40:56,240 --> 00:40:58,865 Možda je to dvoje, možda je to tri, ali računalni znanstvenik jednostavno 1146 00:40:58,865 --> 00:41:01,423 To pojednostavljuje kao veliki O 1, neki konstantni broj koraka. 1147 00:41:01,423 --> 00:41:04,256 Što je nešto što bi mogao učiniti da ima konstantan broj koraka? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Što je vrijeme rada klicati? 1150 00:41:10,930 --> 00:41:11,920 Stalna vrijeme. 1151 00:41:11,920 --> 00:41:12,420 Pravo? 1152 00:41:12,420 --> 00:41:15,490 Kao što je vrijeme rada radi ništa da traje samo jedan 1153 00:41:15,490 --> 00:41:18,570 rad, kao što su ispis F Hello World. 1154 00:41:18,570 --> 00:41:24,110 To bi se moglo reći da je vremenska konstanta, osim manje kutak slučaju s ispisa F, 1155 00:41:24,110 --> 00:41:28,260 Ono što se može prikazivati ​​vrijeme tiska F zapravo biti? 1156 00:41:28,260 --> 00:41:28,790 I zašto? 1157 00:41:28,790 --> 00:41:30,550 Što je n mjerenje u tom slučaju? 1158 00:41:30,550 --> 00:41:32,251 >> PUBLIKA: [nečujan]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. Malan: Točno. 1160 00:41:33,250 --> 00:41:34,900 Broj znakova želimo ispisati. 1161 00:41:34,900 --> 00:41:36,191 Dakle, to je vrlo kontekstu. 1162 00:41:36,191 --> 00:41:39,910 Danas smo bili s naglaskom puno na slova i brojeve ovdje na brodu. 1163 00:41:39,910 --> 00:41:43,540 Ali to također može biti likovi u stvarnom nizu. 1164 00:41:43,540 --> 00:41:46,420 Tako ispada postoji još jedan mjera koja će se početi brinuti o, 1165 00:41:46,420 --> 00:41:48,530 a to je suprotno velikog O, da tako kažemo. 1166 00:41:48,530 --> 00:41:50,120 >> To je omega zapis. 1167 00:41:50,120 --> 00:41:53,380 Dok veliki O znači što je gornja granica na trčanja vrijeme? 1168 00:41:53,380 --> 00:41:55,580 Maksimalno, koliko vremena Možda se nešto poduzeti? 1169 00:41:55,580 --> 00:41:59,250 Omega-- žao to čuva dolaze up-- je suprotno od toga, 1170 00:41:59,250 --> 00:42:02,960 pri čemu je donja granica na količinu vremena nešto može potrajati. 1171 00:42:02,960 --> 00:42:10,480 >> So. Na primjer, ono što je algoritam koja se uvijek nje kvadratnom korake? 1172 00:42:10,480 --> 00:42:15,600 Pa, jedan od algoritama smo vidjeli Danas, u stvari, može biti da je kao dobro. 1173 00:42:15,600 --> 00:42:16,720 Sortirati Izbor. 1174 00:42:16,720 --> 00:42:18,270 Izbor vrsta je prilično glupo. 1175 00:42:18,270 --> 00:42:21,760 Čak i ako je algorithm-- žao, čak ako je polje već razvrstani, 1176 00:42:21,760 --> 00:42:24,150 Izbor vrsta će Produæite kroz popis 1177 00:42:24,150 --> 00:42:28,907 kako bi bili sigurni da ima najmanji Element opet i opet i opet. 1178 00:42:28,907 --> 00:42:31,740 A čak i ako se ljudi u Publika zna da, pričekajte minutu, 1179 00:42:31,740 --> 00:42:33,948 već prošlo najmanji element, računalo 1180 00:42:33,948 --> 00:42:37,300 ne zna da je do izgleda sve na putu kroz popis. 1181 00:42:37,300 --> 00:42:40,240 Slično tome, donju granicu koja može se također uzeti u obzir 1182 00:42:40,240 --> 00:42:42,000 Možda linearno vrijeme. 1183 00:42:42,000 --> 00:42:48,260 >> Koliko vremena je potrebno da sortirati n elementi u najbolji 1184 00:42:48,260 --> 00:42:52,420 Slučaj korištenjem nešto poput mjehurića vrste? 1185 00:42:52,420 --> 00:42:54,280 Pretpostavimo vaš popis je već riješeno. 1186 00:42:54,280 --> 00:42:56,696 Rekli smo mjehurić vrsta preuzima redoslijed n na kvadrat korake. 1187 00:42:56,696 --> 00:42:59,640 Ali što ako je već razvrstani? 1188 00:42:59,640 --> 00:43:02,310 Što ako ste shvatili nakon jedan prolaz kroz niz 1189 00:43:02,310 --> 00:43:03,540 da ste napravili nema zamjene? 1190 00:43:03,540 --> 00:43:05,970 Da li je potrebno da bi što više prolazi? 1191 00:43:05,970 --> 00:43:06,470 >> Ne. 1192 00:43:06,470 --> 00:43:10,340 Dakle donju granicu mjehurić vrste moglo bi se reći da je linearna. 1193 00:43:10,340 --> 00:43:11,830 Omega n. 1194 00:43:11,830 --> 00:43:14,450 I možemo gledati na drugi od njih kao dobro. 1195 00:43:14,450 --> 00:43:17,990 Tako ćemo uzeti brzo pogledati na samo vizualizacija ovdje 1196 00:43:17,990 --> 00:43:20,790 vidjeti kako oni se razlikuju. 1197 00:43:20,790 --> 00:43:24,592 Ja ću ići ovdje u ovo stranica koja je dostupna na web stranici C50, 1198 00:43:24,592 --> 00:43:27,550 ali to će biti bol da se radi, jer koristi tehnologiju pod nazivom 1199 00:43:27,550 --> 00:43:30,560 Java apleti, što je uglavnom nepodržan ovih dana, 1200 00:43:30,560 --> 00:43:32,730 najmanje Chrome i nekih drugih. 1201 00:43:32,730 --> 00:43:37,070 >> I neka mi ići naprijed i ubrzati taj i objasniti što se događa. 1202 00:43:37,070 --> 00:43:40,840 To je demonstracija mjehura vrsta, prvi algoritam smo pogledali. 1203 00:43:40,840 --> 00:43:43,950 I to je vizualizacija, što je svaki tih šipki predstavlja broj. 1204 00:43:43,950 --> 00:43:45,710 Veći bar, veći broj. 1205 00:43:45,710 --> 00:43:47,520 Manji bar, Što je manji broj. 1206 00:43:47,520 --> 00:43:50,353 A što možete vidjeti vizualno, čak iako je to ide super brzo, 1207 00:43:50,353 --> 00:43:53,699 je da je crvena traka je poput mene, hodanje natrag i naprijed popravljanja problema. 1208 00:43:53,699 --> 00:43:56,740 Možete vidjeti da su veći elementi su doista mjehurića gore desno, 1209 00:43:56,740 --> 00:43:59,650 i manji elementi su mjehurića gore lijevo. 1210 00:43:59,650 --> 00:44:01,870 I ovdje, ako zapravo pobliže, 1211 00:44:01,870 --> 00:44:04,330 zapravo možemo brojati Broj usporedbe i zamjene 1212 00:44:04,330 --> 00:44:05,350 koje su napravili. 1213 00:44:05,350 --> 00:44:07,360 >> No, umjesto toga, pogledajmo u drugom algoritmu 1214 00:44:07,360 --> 00:44:11,240 Gledali smo ranije s našim volonteri, izbor vrste. 1215 00:44:11,240 --> 00:44:13,500 Vizualno ima vrlo različit učinak. 1216 00:44:13,500 --> 00:44:16,820 No, to je, opet, vrlo intuitivno, u da držimo odabirom sljedeći najmanji 1217 00:44:16,820 --> 00:44:18,660 Element, a dobili smo malo sreće. 1218 00:44:18,660 --> 00:44:20,110 To osjetio bitno brže. 1219 00:44:20,110 --> 00:44:22,840 Ali ako mi ran to opet i opet a opet s puno ulaza, 1220 00:44:22,840 --> 00:44:26,680 vidjeli bismo da je doista još uvijek u velikoj O n na kvadrat. 1221 00:44:26,680 --> 00:44:29,920 >> Idemo napraviti jedan posljednji Ovdje, umetanje vrsta, 1222 00:44:29,920 --> 00:44:33,180 koji je bio treći algoritam Gledali smo, i opoziva 1223 00:44:33,180 --> 00:44:36,700 da je ovo jedan se bavi Elementi kao što ih susreće, 1224 00:44:36,700 --> 00:44:39,290 ali onda možda smjene više stvari kako bi napravili mjesta, 1225 00:44:39,290 --> 00:44:41,660 umetanje elemenata gdje pripadaju. 1226 00:44:41,660 --> 00:44:45,330 >> I to također završava dajući Konačni rezultat. Sada su sve tri od njih 1227 00:44:45,330 --> 00:44:46,490 Osjećao se vrlo brzo. 1228 00:44:46,490 --> 00:44:48,740 I doista, trčao sam ih u prilično dobrom isječak. 1229 00:44:48,740 --> 00:44:52,510 Ali bitno, oni su svi prilično strašno, da budem iskren. 1230 00:44:52,510 --> 00:44:56,960 Sve ove algoritama do sada koji rade u velikim O n na kvadrat 1231 00:44:56,960 --> 00:44:59,270 potrajati vrlo malo vrijeme za trčanje na kraju. 1232 00:44:59,270 --> 00:45:01,920 >> I doista, možemo vidjeti i osjetiti to na kraju 1233 00:45:01,920 --> 00:45:04,090 ako sam podići ovaj treći i konačni demo. 1234 00:45:04,090 --> 00:45:05,840 Ovo je još jedna vizualizacija koja se događa 1235 00:45:05,840 --> 00:45:08,500 pokazati mjehurić vrsta na lijevoj strani, Izbor vrsta u sredini, 1236 00:45:08,500 --> 00:45:13,410 i nešto, kao jedan od naših ruka podiže ranije predložili, 1237 00:45:13,410 --> 00:45:15,020 spajanje vrsta na desnoj strani. 1238 00:45:15,020 --> 00:45:16,937 Podijeli pa vladaj Strategija na desnoj strani. 1239 00:45:16,937 --> 00:45:19,520 I to je, zapravo, ono što smo ide pogledati u srijedu. 1240 00:45:19,520 --> 00:45:21,990 Ali neka vremena ove izvoditi paralelno. 1241 00:45:21,990 --> 00:45:26,765 To je otprilike isti broj Elementi, sve radi istovremeno. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble sort vs izbor sortirati vs spajanje vrste. 1244 00:45:34,440 --> 00:45:36,760 >> Sada, svi oni prikazuju teoretski istovremeno. 1245 00:45:36,760 --> 00:45:39,830 CPU radi na ista brzina, ali 1246 00:45:39,830 --> 00:45:44,014 Možete osjetiti kako je to dosadno vrlo brzo će postati, 1247 00:45:44,014 --> 00:45:45,930 i koliko brzo kada smo se uvelo malo tjedna 1248 00:45:45,930 --> 00:45:49,330 Algoritmi Zero-a mogu ćemo ubrzati. 1249 00:45:49,330 --> 00:45:51,760 >> A sada ćemo usporediti te u jednom prošlom obliku. 1250 00:45:51,760 --> 00:45:55,710 Idem samo naprijed na CS50 web stranice, gdje 1251 00:45:55,710 --> 00:45:59,020 imamo konačnu link za danas, gdje je netko na internetu 1252 00:45:59,020 --> 00:46:03,960 Ljubazno sastaviti video koji bilježi ono drugačiji sortiranje 1253 00:46:03,960 --> 00:46:07,510 Algoritmi zvučati. 1254 00:46:07,510 --> 00:46:09,577 To je umetanje vrsta. 1255 00:46:09,577 --> 00:46:12,072 >> [Bip] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Čime ste primjeni učestalost na temelju visine bar bar. 1258 00:46:16,850 --> 00:46:19,826 To je balon vrsta. 1259 00:46:19,826 --> 00:46:21,822 >> [Deformiran bip] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Dolazi do sljedećeg is-- dolaze pokraj is-- odabir vrsta, 1262 00:46:45,774 --> 00:46:48,820 gdje opet smo odabir sljedeći najmanji element, 1263 00:46:48,820 --> 00:46:51,820 i možemo vidjeti da raste s lijeva na desno. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Spoji vrsta, naš pobjednik do sada i danas. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Obavijest o tome kako je to dijeljenjem stvari u [nečujan] polovice i četvrtine. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome vrsta, koje nemamo govorio o, i stvara vizualno 1270 00:47:21,660 --> 00:47:24,450 i audally malo različitih oblika i zvuka. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Ide naprijed i natrag, čišćenje stvari. 1273 00:47:30,160 --> 00:47:32,230 Također provjerite heapsort na ovog tipa web stranice. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> I to je to. 1276 00:47:36,810 --> 00:47:38,210 Mi ćemo vas vidjeti sljedeći put. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing i glazba] 1279 00:47:48,334 --> 00:50:24,839