1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Musik spiller] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. MALAN: Dette er CS50. 5 00:00:12,550 --> 00:00:14,612 Og dette er starten på ugen tre. 6 00:00:14,612 --> 00:00:16,820 Så vi har fået en masse spændende ting til at dække i dag. 7 00:00:16,820 --> 00:00:20,160 En masse af muligheder for frivillige op på scenen. 8 00:00:20,160 --> 00:00:22,780 Og endelig, i dag er ikke om koden på alle. 9 00:00:22,780 --> 00:00:24,820 Men det handler om ideer, og det handler om algoritmer, 10 00:00:24,820 --> 00:00:28,420 og faktisk bringe tilbage nogle af erfaringerne fra uge nul, 11 00:00:28,420 --> 00:00:31,910 hvor tilbagekaldelse, vi indført denne misfoster. 12 00:00:31,910 --> 00:00:33,880 Og låntagning inspiration fra, at starte 13 00:00:33,880 --> 00:00:36,879 at løse stadigt mere sofistikerede problemer algoritmisk. 14 00:00:36,879 --> 00:00:38,420 Men først et par meddelelser. 15 00:00:38,420 --> 00:00:42,020 Så en, hvis du ønsker at deltage CS50 medarbejdere og klassekammerater til frokost 16 00:00:42,020 --> 00:00:44,670 denne fredag, både her og i Cambridge, og i New Haven, 17 00:00:44,670 --> 00:00:48,060 kan du besøge kursets hjemmeside, hvor der kan findes en URL. 18 00:00:48,060 --> 00:00:50,390 Forelæsning denne onsdag vil ikke være her i Sanders. 19 00:00:50,390 --> 00:00:53,610 Det vil være online kun, så tune ind på CS50 hjemmeside, 20 00:00:53,610 --> 00:00:55,850 om her i Cambridge eller New Haven så godt. 21 00:00:55,850 --> 00:00:58,110 >> Og så problem indstille to allerede er i dine hænder. 22 00:00:58,110 --> 00:01:03,067 Hvis du ikke har dykket ind endnu, lad mig at tilbyde den stærkt formuleret forslag 23 00:01:03,067 --> 00:01:05,150 at, især nu, da problemet sætter forvejen, 24 00:01:05,150 --> 00:01:08,669 du virkelig ønsker at starte nu, hvis ikke fuske lidt i weekenden eller før 25 00:01:08,669 --> 00:01:10,710 når de først gå ud på Fredage, fordi du vil 26 00:01:10,710 --> 00:01:14,380 finder, at de er ikke nødvendigvis bliver længere eller mere udfordrende pr 27 00:01:14,380 --> 00:01:14,950 SE. 28 00:01:14,950 --> 00:01:17,575 Jeg tror, ​​du vil finde, at der i Generelt har de en tendens til at tage ca. 29 00:01:17,575 --> 00:01:18,892 omkring samme mængde tid. 30 00:01:18,892 --> 00:01:20,850 Men det helt sikkert afhænger på den studerendes, og det 31 00:01:20,850 --> 00:01:22,880 afhænger af den tankegang som du nærmer dig det. 32 00:01:22,880 --> 00:01:24,910 Men altid, du vil at køre op mod nogle vægge, 33 00:01:24,910 --> 00:01:26,350 og du kommer til at ramme nogle fejl, og du er bare 34 00:01:26,350 --> 00:01:27,950 ikke vil være i stand til at komme over det på et tidspunkt. 35 00:01:27,950 --> 00:01:31,380 Og det er enormt værdifuldt at være i stand til at træde væk, kom tilbage næste dag, 36 00:01:31,380 --> 00:01:35,286 gå til kontortid, indlæg på CS50 Diskuter eller lignende, til rent faktisk at få blokeringen. 37 00:01:35,286 --> 00:01:36,160 Så holder det i tankerne. 38 00:01:36,160 --> 00:01:40,830 Startende tidligst muligt er det bedste, du kan gøre. 39 00:01:40,830 --> 00:01:44,160 Så her er, hvor vi startede klassen over i uge nul. 40 00:01:44,160 --> 00:01:47,441 Og kan vi få en frivillig her for at hjælpe mig med at finde mikrofoner? 41 00:01:47,441 --> 00:01:47,940 OK. 42 00:01:47,940 --> 00:01:48,900 Stående op allerede. 43 00:01:48,900 --> 00:01:50,080 Kom op. 44 00:01:50,080 --> 00:01:53,707 Gæt det er, hvordan det kommer til at fungere. 45 00:01:53,707 --> 00:01:54,415 Hvad er dit navn? 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 Kom op. 49 00:01:57,910 --> 00:01:58,619 Dejligt at møde dig. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Rart at møde dig. 51 00:01:59,910 --> 00:02:02,772 DAVID J. MALAN: Og du var her med os i uge nul, selvfølgelig. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: jeg var. 53 00:02:03,028 --> 00:02:03,160 Jeg var. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. MALAN: Så kan du gå videre og finde for os Mike Smith, 55 00:02:05,868 --> 00:02:08,639 så hurtigt som du kan? 56 00:02:08,639 --> 00:02:10,639 Så hurtigt som du kan. 57 00:02:10,639 --> 00:02:13,756 Bogstaveligt talt rive problemet i halvdelen som du har brug for. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. MALAN: Bogstaveligt rive problemet i halve. 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 Meget godt. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. MALAN: OK. 65 00:02:23,700 --> 00:02:24,200 Godt. 66 00:02:24,200 --> 00:02:24,701 Tak. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Meget godt. 68 00:02:25,700 --> 00:02:26,210 OK. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. MALAN: Og så nu, du har skåret det ned 70 00:02:27,610 --> 00:02:29,320 til halvdelen af ​​problemets omfang. 71 00:02:29,320 --> 00:02:31,267 Nu er vi nede på et kvartal. 72 00:02:31,267 --> 00:02:33,475 Er du opmærksom på hvilken side vi holder? 73 00:02:33,475 --> 00:02:34,405 >> [LAUGHING] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Ja, jeg tror-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. MALAN: Hvilke afsnit er vi i? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: lyddæmper, så. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. MALAN: OK. 78 00:02:39,941 --> 00:02:42,810 Men Mike Smith går at være efter Lyddæmpere. 79 00:02:42,810 --> 00:02:44,130 So-- 80 00:02:44,130 --> 00:02:48,180 >> [LAUGHING] 81 00:02:48,180 --> 00:02:48,742 >> Okay. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Hvor er vi på udkig? 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: Nu er vi i kirurgisk. 86 00:02:54,760 --> 00:02:57,840 Nu læger. 87 00:02:57,840 --> 00:02:58,340 Nu-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- lad os gå med rigtige. 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 OK. 92 00:03:01,470 --> 00:03:03,700 Hvis du har brug for Real. 93 00:03:03,700 --> 00:03:05,250 Nu hvilken vej er Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Denne vej. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. MALAN: Hvilken vej? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Vent. 97 00:03:08,240 --> 00:03:08,790 M is-- ret? 98 00:03:08,790 --> 00:03:09,110 Vi startede med-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. MALAN: Ja. 100 00:03:10,090 --> 00:03:10,650 De er forladt. 101 00:03:10,650 --> 00:03:11,430 Din højre. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Ja. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. MALAN: Så Mike herinde. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Hvad? 105 00:03:13,990 --> 00:03:14,665 >> [LAUGHING] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Dårligt eksempel, gutter. 108 00:03:18,330 --> 00:03:18,830 Undskyld. 109 00:03:18,830 --> 00:03:21,610 DAVID J. MALAN: Dette vil lære dig til at springe ud af din stol. 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 Jeg har dig. 113 00:03:23,390 --> 00:03:24,670 Jeg har dig. 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 Dette is-- OK, jeg har dig. 117 00:03:26,812 --> 00:03:27,520 Smith lige her? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. MALAN: Smith, tak. 119 00:03:28,894 --> 00:03:30,535 Så jeg vil holde udkig op Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, yeah. 121 00:03:30,790 --> 00:03:31,340 Nej Nej Nej. 122 00:03:31,340 --> 00:03:31,600 Åh nej. 123 00:03:31,600 --> 00:03:31,940 Dette er min. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. MALAN: Åh, du fik Smith. 125 00:03:32,580 --> 00:03:33,415 OK. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Ja, jeg fik Smith lige her. 127 00:03:34,040 --> 00:03:34,700 Beklager, gutter. 128 00:03:34,700 --> 00:03:35,860 Jeg troede Michael-- vi ledte efter Michael. 129 00:03:35,860 --> 00:03:36,550 Undskyld. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. MALAN: Det er OK. 131 00:03:37,550 --> 00:03:39,950 Okay, nu er vi ind Paccini and Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini og sønner. 133 00:03:41,242 --> 00:03:43,158 DAVID J. MALAN: Kun du og jeg er i på dette. 134 00:03:43,158 --> 00:03:44,050 OK. 135 00:03:44,050 --> 00:03:45,130 Find os 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 Vi er i R for vrøvl. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Dårligt. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Dette kommer til at tage et stykke tid. 143 00:03:52,480 --> 00:03:54,340 >> [LAUGHING] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. MALAN: Sko. 146 00:03:56,720 --> 00:03:58,080 Vi er i sko. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Nu er vi gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. MALAN: Nice. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [LAUGHING] 151 00:04:03,620 --> 00:04:05,440 Åh, det er fantastisk. 152 00:04:05,440 --> 00:04:06,910 [LAUGHING] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. MALAN: Det er OK. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Åh, det er godt. 156 00:04:11,365 --> 00:04:14,425 Jeg tror ikke, jeg har tænkt mig at har PSAT buddies efter dette. 157 00:04:14,425 --> 00:04:15,300 DAVID J. MALAN: Godt. 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 Så lad os rive det i halve. 163 00:04:21,600 --> 00:04:22,270 Det er ok. 164 00:04:22,270 --> 00:04:25,606 Dette ender dårligt alligevel, fordi Mike Smith vil ikke være i de gule sider. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. MALAN: Nej, det er OK. 167 00:04:27,140 --> 00:04:28,930 Men lad os lade som han er på denne side. 168 00:04:28,930 --> 00:04:33,260 Så nu har du skåret problemet ned til én side, og vi fandt Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Jublende] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Ok tak. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 OK. 174 00:04:41,200 --> 00:04:43,646 Det var ekstraordinært. 175 00:04:43,646 --> 00:04:45,954 Men det var stadig hurtigere end lineær søgning, 176 00:04:45,954 --> 00:04:47,870 hvor vi starter på begyndelsen af ​​bogen, 177 00:04:47,870 --> 00:04:51,210 og vi flytter vores vej fra venstre mod højre, sidst på udkig efter Mike Smith. 178 00:04:51,210 --> 00:04:53,540 Og så, hvis telefonbogen havde måske 1.000 sider, 179 00:04:53,540 --> 00:04:56,300 måske det ville have taget os 10 eller deromkring siden tårer. 180 00:04:56,300 --> 00:04:59,380 >> Men du måske har gearede rørt en antagelse 181 00:04:59,380 --> 00:05:03,602 under alt dette, hvilket vil sige at telefonbogen på forhånd var, hvad? 182 00:05:03,602 --> 00:05:04,310 PUBLIKUM: Sorteret. 183 00:05:04,310 --> 00:05:05,000 DAVID J. MALAN: Det er ordnet. 184 00:05:05,000 --> 00:05:05,160 Højre? 185 00:05:05,160 --> 00:05:07,909 Det er sorteret alfabetisk, så at alle disse navne og numre 186 00:05:07,909 --> 00:05:11,230 sorteres fra A'er til Z s, og alfabetisk i mellem. 187 00:05:11,230 --> 00:05:13,100 Men i dag, vi nu spørger spørgsmålet, ja, 188 00:05:13,100 --> 00:05:16,170 hvordan gjorde Verizon eller telefonen Virksomheden får det ind i denne stat? 189 00:05:16,170 --> 00:05:19,560 >> Fordi det er én ting at udnytte dette synspunkt, og derfor 190 00:05:19,560 --> 00:05:22,570 løse et problem med en algoritme mere effektivt. 191 00:05:22,570 --> 00:05:24,900 Men vi har aldrig rigtig spurgte i uge nul, godt, 192 00:05:24,900 --> 00:05:27,790 hvor meget kostede det Verizon eller en anden 193 00:05:27,790 --> 00:05:29,620 at få den telefon bog i sorteret orden? 194 00:05:29,620 --> 00:05:29,780 >> Højre? 195 00:05:29,780 --> 00:05:31,529 Det betyder ikke noget, hvis se op Mike Smith 196 00:05:31,529 --> 00:05:35,190 er super hurtig, hvis det tager dig en år for at sortere siderne i første omgang. 197 00:05:35,190 --> 00:05:35,690 Højre? 198 00:05:35,690 --> 00:05:38,620 Du kan lige så godt bare finkæmme gennem en randomiseret telefonbog, 199 00:05:38,620 --> 00:05:40,690 hvis det vil være super dyrt at sortere det. 200 00:05:40,690 --> 00:05:42,350 Så hvis vi kan få en anden frivillig. 201 00:05:42,350 --> 00:05:46,350 Lad os tage et kig op her på hvordan vi might-- komme på up-- hvordan 202 00:05:46,350 --> 00:05:48,100 vi måske gå om sortering disse. 203 00:05:48,100 --> 00:05:51,990 >> Og hvis Jordan kunne faktisk slutte sig til os heroppe på scenen. 204 00:05:51,990 --> 00:05:55,100 Kom nu op for bare et øjeblik. 205 00:05:55,100 --> 00:05:56,359 Hvad er dit navn? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. MALAN: Caroline, kom op. 208 00:05:58,691 --> 00:06:02,070 Og du vil blive forenet af mig og Jordan her. 209 00:06:02,070 --> 00:06:03,800 Caroline, tak. 210 00:06:03,800 --> 00:06:04,300 Okay. 211 00:06:04,300 --> 00:06:08,330 Så hvad vi har her Caroline er 26 blå bøger 212 00:06:08,330 --> 00:06:10,747 at FAS bruger at administrere visse afsluttende eksamener. 213 00:06:10,747 --> 00:06:13,330 Disse bliver svært at finde, men hvad vi har gjort i forvejen 214 00:06:13,330 --> 00:06:15,800 er, at vi har lagt en persons navn på forsiden af ​​hver af disse, 215 00:06:15,800 --> 00:06:18,133 men vi har holdt det simpelt ved derefter lægge ud fulde navne. 216 00:06:18,133 --> 00:06:22,720 Så vi ville sætte personen med navnet L, D, J, B, hele vejen A til Z, 217 00:06:22,720 --> 00:06:24,090 men de er i tilfældig rækkefølge. 218 00:06:24,090 --> 00:06:26,890 Og så hvis du ville, taler din vej gennem problem som du 219 00:06:26,890 --> 00:06:31,620 gør det, kan du gå videre og sortere disse for os, fra A til Z. 220 00:06:31,620 --> 00:06:34,070 >> PUBLIKUM: OK, så L er ligesom, midten. 221 00:06:34,070 --> 00:06:35,050 C er begyndt. 222 00:06:35,050 --> 00:06:42,410 B. J før L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. MALAN: Hold, at tænkte et sekund. 224 00:06:45,140 --> 00:06:48,910 Fordi ellers dette kun interessant for dig, mig og Jordan. 225 00:06:48,910 --> 00:06:49,724 Der vi går. 226 00:06:49,724 --> 00:06:50,640 PUBLIKUM: [uhørligt]. 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 Hvad laver du? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M kommer efter 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, Good. 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. Så det ser ud som du er making-- holde ud. 238 00:07:10,689 --> 00:07:12,730 Det ser ud som du gør en stor bunke herovre, 239 00:07:12,730 --> 00:07:13,910 og sådan en stor bunke derovre. 240 00:07:13,910 --> 00:07:16,230 Så den første halvdel af alfabetet, anden halvdel af alfabetet. 241 00:07:16,230 --> 00:07:16,460 OK. 242 00:07:16,460 --> 00:07:16,960 Godt. 243 00:07:16,960 --> 00:07:19,680 Slags opdele problemet i to. 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. Så du slags at vælge dem en efter en, 248 00:07:25,070 --> 00:07:27,620 sætte det enten venstre eller højre, eller Z er foregår på gulvet. 249 00:07:27,620 --> 00:07:28,012 OK. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z der foregår på gulvet. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. MALAN: OK. 252 00:07:29,360 --> 00:07:30,920 Y går på gulvet. 253 00:07:30,920 --> 00:07:31,735 Nu kan vi sætte 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 kommer forladt. 256 00:07:33,700 --> 00:07:36,017 S går til højre. 257 00:07:36,017 --> 00:07:37,642 Okay, er en gå hele vejen til venstre. 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: Nu, godt. 260 00:07:39,873 --> 00:07:43,260 Vi har A, B, C. W 's går dernede. 261 00:07:43,260 --> 00:07:45,566 Okay, 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 Godt. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: I centrum, jeg gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. MALAN: OK. 266 00:07:50,000 --> 00:07:52,375 Så nu, vi vil slags af flette disse forskellige bunker. 267 00:07:52,375 --> 00:08:00,730 Så A til C, så ser jeg D, og E og F og G, og H og I. Nice. 268 00:08:00,730 --> 00:08:05,540 J, K. Og så, denne bunke er på hovedet, men det er OK. 269 00:08:05,540 --> 00:08:06,040 Sikker. 270 00:08:06,040 --> 00:08:07,240 Vi kan skære nogle hjørner. 271 00:08:07,240 --> 00:08:07,950 OK. 272 00:08:07,950 --> 00:08:10,530 Og så har vi brug 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: Excellent. 275 00:08:11,880 --> 00:08:14,122 Så en stor tak til Caroline til sortering disse. 276 00:08:14,122 --> 00:08:15,030 >> [Jublende] 277 00:08:15,030 --> 00:08:17,287 >> Tak. 278 00:08:17,287 --> 00:08:18,120 Mange tak. 279 00:08:18,120 --> 00:08:22,910 Så lad os nu overveje et øjeblik hvordan Caroline gik om at gøre det, 280 00:08:22,910 --> 00:08:26,040 og hvad vi var i stand at-- hvordan vi 281 00:08:26,040 --> 00:08:28,409 var i stand til at løse dette problem, når vi var bare 282 00:08:28,409 --> 00:08:29,950 givet en hel masse tilfældige input. 283 00:08:29,950 --> 00:08:31,610 >> Tja, det ligner der var lidt af et system der? 284 00:08:31,610 --> 00:08:32,110 Højre. 285 00:08:32,110 --> 00:08:34,495 Så de tidligere breve i alfabetet, hun 286 00:08:34,495 --> 00:08:37,120 var at sætte til venstre, og senere bogstaver i alfabetet, 287 00:08:37,120 --> 00:08:38,270 hun lagde i den højre. 288 00:08:38,270 --> 00:08:40,500 Og så snart hun fandt nogle proksimale breve, dem 289 00:08:40,500 --> 00:08:43,124 der går lige ved siden af ​​hinanden, hun ville sætte dem i orden. 290 00:08:43,124 --> 00:08:46,750 Og så vi slags havde disse små bunker af sorterede input, der forekommer. 291 00:08:46,750 --> 00:08:50,540 >> Og så det er helt ligesom hvad de fleste af os mennesker ville gøre. 292 00:08:50,540 --> 00:08:53,530 Vi ville slags finkæmme gennem det, og vi ville slags have en mekanisme. 293 00:08:53,530 --> 00:08:56,930 Men det kan være svært at skrive den ned i en formel per se. 294 00:08:56,930 --> 00:08:59,010 Det føltes lidt mere organisk end det. 295 00:08:59,010 --> 00:09:02,560 Så lad os se om vi kan nu bundet problemet med færre indgange. 296 00:09:02,560 --> 00:09:05,170 >> I stedet for 26, lad os gøre noget langt færre 297 00:09:05,170 --> 00:09:09,890 med blot sige, syv, bag disse døre, så at sige. 298 00:09:09,890 --> 00:09:11,300 Er der kun syv numre? 299 00:09:11,300 --> 00:09:15,240 Og hvis målet nu på hånd er at finde en værdi, 300 00:09:15,240 --> 00:09:17,850 lad os se, hvor effektivt vi kan gå om at gøre dette. 301 00:09:17,850 --> 00:09:22,460 Og lad os se om vi kan nu begynde at anvende nogle tal, 302 00:09:22,460 --> 00:09:26,310 eller nogle formler med til at beskrive effektiviteten af ​​vores telefonbog 303 00:09:26,310 --> 00:09:31,060 algoritme, vores prøve bog algoritme, og mere generelt, at finde oplysninger. 304 00:09:31,060 --> 00:09:34,770 >> Så for dette, så lad mig gå videre, og på berøringsskærmen herovre, 305 00:09:34,770 --> 00:09:41,100 udbudt en webbrowser, der har netop disse syv døre. 306 00:09:41,100 --> 00:09:46,670 Og hvis vi kunne få en anden frivilligt til at komme på herovre, 307 00:09:46,670 --> 00:09:48,480 Jeg har lagt de samme døre herovre. 308 00:09:48,480 --> 00:09:49,170 Hurtig frivillig. 309 00:09:49,170 --> 00:09:51,130 >> Denne en-- demoer går til en hurtigere og hurtigere nu. 310 00:09:51,130 --> 00:09:51,600 Kom ned. 311 00:09:51,600 --> 00:09:52,308 Hvad er dit navn? 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 Okay, Trevor, kom ned. 315 00:09:55,770 --> 00:09:59,212 Så Trevor har meldt sig frivilligt her gøre et lignende problem, men en, der er 316 00:09:59,212 --> 00:10:02,170 smallere i omfang, og der kommer at tillade os at forsøge at formalisere nu 317 00:10:02,170 --> 00:10:03,970 fremgangsmåden til sortering disse numre. 318 00:10:03,970 --> 00:10:05,500 >> Så Trevor, rart at møde dig. 319 00:10:05,500 --> 00:10:08,720 Så her er et array, så at tale, en liste over syv døre. 320 00:10:08,720 --> 00:10:10,327 Gå videre og finder os nummer 50. 321 00:10:10,327 --> 00:10:12,410 Og så efter den kendsgerning, fortælle os, hvordan du fandt den. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Bør være-- okay. 324 00:10:20,040 --> 00:10:21,945 Ja, det er den her? 325 00:10:21,945 --> 00:10:24,680 Uh-oh. 326 00:10:24,680 --> 00:10:25,560 OK. 327 00:10:25,560 --> 00:10:26,680 Du klikkede at en. 328 00:10:26,680 --> 00:10:28,690 Godt. 329 00:10:28,690 --> 00:10:29,780 >> Og god. 330 00:10:29,780 --> 00:10:30,970 Nu du klikkede at en. 331 00:10:30,970 --> 00:10:34,060 Og lad mig give dig mikrofonen, så du har det på bare et øjeblik. 332 00:10:34,060 --> 00:10:37,000 Gå videre og klik på næste dør, du ønsker. 333 00:10:37,000 --> 00:10:39,812 Ja, godt. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Kan jeg derefter fjerne markeringen en dør? 335 00:10:41,020 --> 00:10:42,620 DAVID J. MALAN: Nej, du kan ikke derefter fjerne markeringen. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Denne. 338 00:10:43,974 --> 00:10:45,640 DAVID J. MALAN: Hvor skal du hen? 339 00:10:45,640 --> 00:10:46,410 Hvilken en? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: At man. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. MALAN: Nej. 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Denne. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. MALAN: Ja. 345 00:10:49,020 --> 00:10:49,700 Det var godt. 346 00:10:49,700 --> 00:10:50,380 Okay. 347 00:10:50,380 --> 00:10:53,900 Hvad var din algoritme eller procedure til at gøre dette, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Jeg gik bare igennem døre, indtil jeg fandt en 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. MALAN: OK. 350 00:10:56,940 --> 00:10:58,150 Fremragende algoritme. 351 00:10:58,150 --> 00:10:59,540 Så det er fint. 352 00:10:59,540 --> 00:11:03,120 Fordi i virkeligheden, hvis jeg afslører, hvad der er bag disse to andre døre, hvad 353 00:11:03,120 --> 00:11:06,954 Vi finder her, er, at vi kun har tilfældige input. 354 00:11:06,954 --> 00:11:08,870 Så det var faktisk så god, som du kunne få. 355 00:11:08,870 --> 00:11:12,509 Og i virkeligheden, du fik bedre end udtømmende søgning hele array, 356 00:11:12,509 --> 00:11:15,300 fordi det ville have været rigtig uheldig hvis du havde ramt nummeret 357 00:11:15,300 --> 00:11:16,604 50 i allersidste dør. 358 00:11:16,604 --> 00:11:18,520 Men hvad hvis vi i stedet gav dig en antagelse. 359 00:11:18,520 --> 00:11:20,630 Antag jeg sortere alle disse døre rundt, 360 00:11:20,630 --> 00:11:23,500 så du har den numre sorteres denne gang, 361 00:11:23,500 --> 00:11:29,730 men denne gang er det faktisk a different-- denne gang, 362 00:11:29,730 --> 00:11:32,640 Det er faktisk sorteret for dig. 363 00:11:32,640 --> 00:11:35,380 Og nu målet ved hånden er at ramme nummer 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. MALAN: Hvad er din algoritme kommer til at være? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Tja, hvis det er sorteres, er det enten går 367 00:11:39,628 --> 00:11:42,710 at være-- hvis største til den største, faldende, vil det være den første, 368 00:11:42,710 --> 00:11:44,751 eller hvis det er det modsatte, vil det være den sidste. 369 00:11:44,751 --> 00:11:48,897 Så jeg vil bare trykke på denne dør, og så bare trykke på den sidste dør. 370 00:11:48,897 --> 00:11:49,980 DAVID J. MALAN: Excellent. 371 00:11:49,980 --> 00:11:50,270 Okay. 372 00:11:50,270 --> 00:11:51,150 Så vi fandt nummer 50. 373 00:11:51,150 --> 00:11:52,970 Så så snart du vidste de blev sorteret, vi 374 00:11:52,970 --> 00:11:55,040 var i stand til at udnytte denne antagelse. 375 00:11:55,040 --> 00:11:57,040 Så de er for meget som telefonbogen eksempel. 376 00:11:57,040 --> 00:11:59,540 Så snart du har, selv med et lille problem som dette, 377 00:11:59,540 --> 00:12:02,380 dine input pre-sorteret, vi kan faktisk finde værdien velsagtens 378 00:12:02,380 --> 00:12:03,130 mere effektivt. 379 00:12:03,130 --> 00:12:05,800 >> Og jeg har ikke fortælle dig, hvis det var sorteres små til store, eller store til små, 380 00:12:05,800 --> 00:12:08,080 og så det var meget rimelig at starte på den ene ende eller den anden 381 00:12:08,080 --> 00:12:09,750 faktisk finde, at målværdien. 382 00:12:09,750 --> 00:12:11,400 Så tak til Trevor så godt. 383 00:12:11,400 --> 00:12:13,260 Og jeg vil propose-- pænt gjort. 384 00:12:13,260 --> 00:12:16,960 Vi har et lille klip, faktisk, at er blandt vores foretrukne øjeblikke i CS50, 385 00:12:16,960 --> 00:12:19,700 hvorved nogle gange disse demoer ikke helt går efter planen. 386 00:12:19,700 --> 00:12:22,050 Og faktisk lige nu, jeg trukket op den forkerte grænseflade 387 00:12:22,050 --> 00:12:23,508 med til at bruge den berøringsfølsomme skærm. 388 00:12:23,508 --> 00:12:24,660 Så det var min skyld der. 389 00:12:24,660 --> 00:12:26,600 >> Så dette vil gøre for næste års klip som 390 00:12:26,600 --> 00:12:28,570 til hvorfor jeg klikke på min egen skærm. 391 00:12:28,570 --> 00:12:31,390 Men lad os tage et hurtigt kig på, hvad der skete sidste år 392 00:12:31,390 --> 00:12:34,770 med Jay, der kom løbende, meget ligesom Trevor her, meldte, 393 00:12:34,770 --> 00:12:39,380 og i denne korte klip, vil du se hvordan dette samme demo ikke helt 394 00:12:39,380 --> 00:12:41,074 afslører de samme erfaringer. 395 00:12:41,074 --> 00:12:41,740 [VIDEO PLAYBACK] 396 00:12:41,740 --> 00:12:45,360 -Alle Jeg vil have dig til at gøre nu, er at finde for mig, og for os, 397 00:12:45,360 --> 00:12:51,674 virkelig er antallet 50 et skridt ad gangen. 398 00:12:51,674 --> 00:12:52,450 >> -Den Nummer 50? 399 00:12:52,450 --> 00:12:53,190 >> -Den Nummer 50. 400 00:12:53,190 --> 00:12:55,356 Og du kan afsløre, hvad der er bag hver af disse døre 401 00:12:55,356 --> 00:12:58,540 blot ved at røre den med en finger. 402 00:12:58,540 --> 00:13:00,910 For pokker. 403 00:13:00,910 --> 00:13:02,870 >> [LAUGHING] 404 00:13:02,870 --> 00:13:03,806 >> [END AFSPIL] 405 00:13:03,806 --> 00:13:05,430 DAVID J. MALAN: Så gik meget godt. 406 00:13:05,430 --> 00:13:06,796 Det var de usorterede døre. 407 00:13:06,796 --> 00:13:08,670 Og Jay, selvfølgelig, fandt det alt for hurtigt. 408 00:13:08,670 --> 00:13:12,910 Trevor gjorde et meget bedre job i form af en lærenem øjeblik, 409 00:13:12,910 --> 00:13:15,850 så at sige, i år i tager længere tid at finde den. 410 00:13:15,850 --> 00:13:17,950 Selvfølgelig derefter gav vi Jay en ny chance, 411 00:13:17,950 --> 00:13:20,320 hvorved vi sorteret dørene, ligesom vi gjorde for Trevor, 412 00:13:20,320 --> 00:13:22,300 og Trevor gjorde super godt denne gang. 413 00:13:22,300 --> 00:13:26,124 Men Jay gjorde det halvt så hurtigt. 414 00:13:26,124 --> 00:13:26,790 [VIDEO PLAYBACK] 415 00:13:26,790 --> 00:13:29,650 -Den Mål er nu at også finder os nummer 50, 416 00:13:29,650 --> 00:13:33,030 men gør det algoritmisk, og fortælle os, hvordan du kommer over det. 417 00:13:33,030 --> 00:13:33,660 >> -OK. 418 00:13:33,660 --> 00:13:35,604 >> -Og Hvis du finder det, du holder filmen. 419 00:13:35,604 --> 00:13:37,228 Hvis du ikke kan finde det, du give det tilbage. 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 >> - [Uhørligt] OK. 423 00:13:40,800 --> 00:13:46,236 Så jeg har tænkt mig at kontrollere enderne først til, hvis there's-- bestemme Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Applaus] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [END AFSPIL] 427 00:13:55,729 --> 00:13:56,520 DAVID J. MALAN: OK. 428 00:13:56,520 --> 00:13:59,760 Så sortering døre klart fører til større effektivitet. 429 00:13:59,760 --> 00:14:01,680 Og ja, dobbelt så hurtigt er, hvad jeg mente der. 430 00:14:01,680 --> 00:14:03,270 Og så Jay fik heldig begge gange. 431 00:14:03,270 --> 00:14:06,685 Og han også fik heldig i den sidste år, jeg bestilte nogle Blu-ray-diske 432 00:14:06,685 --> 00:14:07,560 til rent faktisk at give ud. 433 00:14:07,560 --> 00:14:09,768 Jeg er ked af dette år, vi havde ikke den samme, Trevor. 434 00:14:09,768 --> 00:14:11,540 Men endnu bedre var et par år tilbage. 435 00:14:11,540 --> 00:14:14,820 Og nogle af jer måske kender denne fyr, Sean, som da han var i CS50, 436 00:14:14,820 --> 00:14:17,780 blev udfordret med den nøjagtige samme problem, dog i SD, 437 00:14:17,780 --> 00:14:19,360 som du snart vil se, tilbage i dag. 438 00:14:19,360 --> 00:14:22,622 Og du opdage, at ikke kun gjorde han tage lidt længere tid end Jay, 439 00:14:22,622 --> 00:14:25,580 lidt længere end Trevor, var det faktisk denne vidunderlige mulighed 440 00:14:25,580 --> 00:14:29,820 til at engagere sig næsten alle i crowd a la Price is Right, fremme 441 00:14:29,820 --> 00:14:31,889 ham til at finde nummeret vi søgte. 442 00:14:31,889 --> 00:14:32,930 Lad os. tage et hurtigt kig. 443 00:14:32,930 --> 00:14:33,320 >> [VIDEO PLAYBACK] 444 00:14:33,320 --> 00:14:33,820 >> -OK. 445 00:14:33,820 --> 00:14:36,680 Så din opgave her, Sean, er følgende. 446 00:14:36,680 --> 00:14:40,860 Jeg har skjult bag disse døre nummer syv. 447 00:14:40,860 --> 00:14:45,120 Men gemt væk i nogle af disse døre samt andre negative tal. 448 00:14:45,120 --> 00:14:47,500 Og dit mål er at tænke af denne top talrække 449 00:14:47,500 --> 00:14:50,390 som blot et array, eller bare sekvens af stykker papir 450 00:14:50,390 --> 00:14:51,510 med tal bag dem. 451 00:14:51,510 --> 00:14:55,540 Og dit mål er, kun at bruge toppen matrix her, finde mig det nummer syv. 452 00:14:55,540 --> 00:14:58,570 Og vi derefter gå til kritik hvordan du går om at gøre det. 453 00:14:58,570 --> 00:14:59,070 -Okay. 454 00:14:59,070 --> 00:15:00,850 -Find Os nummer syv, tak. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Nej. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Fem, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [LAUGHING] 461 00:15:24,770 --> 00:15:25,910 >> Det er ikke et trick spørgsmål. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 One. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [LAUGHING] 466 00:15:34,695 --> 00:15:37,861 På dette tidspunkt, din score er ikke meget godt, så du kan lige så godt holde ud. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Tre. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [LAUGHING] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Fortsæt. 473 00:15:47,774 --> 00:15:50,690 Helt ærligt, kan jeg ikke hjælpe, men spekulerer hvad du selv tænker, so-- 474 00:15:50,690 --> 00:15:51,959 >> [LAUGHING] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Kun den øverste række, så du har fået tre venstre. 477 00:15:55,020 --> 00:15:56,200 Så find mig syv. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [LAUGHING] 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 Syv. 484 00:16:26,946 --> 00:16:28,780 >> [Applaus] 485 00:16:28,780 --> 00:16:29,426 >> Okay. 486 00:16:29,426 --> 00:16:30,360 >> [END AFSPIL] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. MALAN: Så vi kunne se disse hele dagen lang. 488 00:16:31,840 --> 00:16:34,090 Og nogle af selvfølgelig dette års demoer måske 489 00:16:34,090 --> 00:16:36,330 vil nu ende i næste års video så godt. 490 00:16:36,330 --> 00:16:39,040 Så lad os nu faktisk fokusere på de algoritmer 491 00:16:39,040 --> 00:16:42,140 her, og se om vi ikke kan nu begynde at formalisere 492 00:16:42,140 --> 00:16:46,650 hvordan vi kan gå om at få vores data ind i denne tilstand, at det er sorteret, 493 00:16:46,650 --> 00:16:50,054 så i sidste ende, kan vi faktisk søg det mere effektivt. 494 00:16:50,054 --> 00:16:52,470 Og selv om vi skal hen at bruge forholdsvis små datasæt, 495 00:16:52,470 --> 00:16:54,511 ligesom otte numre, vi har her på brættet, 496 00:16:54,511 --> 00:16:58,230 i sidste ende de samme ideer kunne gælde til 1.000 indgange, en million indgange, 497 00:16:58,230 --> 00:17:02,100 4 milliarder indgange, fordi algoritmerne vil være grundlæggende de samme. 498 00:17:02,100 --> 00:17:05,359 >> Og så dette er vores sidste mulighed for frivillige i dag, 499 00:17:05,359 --> 00:17:09,790 men måske den mest involverede en, som vi har brug for otte frivillige 500 00:17:09,790 --> 00:17:12,960 til at komme op og gå os gennem processen med sortering, hvad der snart 501 00:17:12,960 --> 00:17:15,212 være på disse musikken står her. 502 00:17:15,212 --> 00:17:16,170 Lad mig starte tilbage her. 503 00:17:16,170 --> 00:17:19,692 >> Så man i turquoise-- grønne er det? 504 00:17:19,692 --> 00:17:21,130 Er du begår? 505 00:17:21,130 --> 00:17:21,630 To. 506 00:17:21,630 --> 00:17:23,069 Kom ned. 507 00:17:23,069 --> 00:17:23,569 OK. 508 00:17:23,569 --> 00:17:24,420 Tre. 509 00:17:24,420 --> 00:17:25,400 Fire. 510 00:17:25,400 --> 00:17:27,247 Lad mig-- OK, fem. 511 00:17:27,247 --> 00:17:28,830 Du bliver udpeget af din ven. 512 00:17:28,830 --> 00:17:31,340 Seks, syv, og otte. 513 00:17:31,340 --> 00:17:32,130 Kom op. 514 00:17:32,130 --> 00:17:32,630 Okay. 515 00:17:32,630 --> 00:17:33,190 Mange tak. 516 00:17:33,190 --> 00:17:33,689 Kom op. 517 00:17:33,689 --> 00:17:34,790 Kom op. 518 00:17:34,790 --> 00:17:35,330 >> Okay. 519 00:17:35,330 --> 00:17:38,890 Så det, vi har her-- og dette er blandt de mere akavet dem, 520 00:17:38,890 --> 00:17:42,390 da dette vil kræve, at du humor mig for bare en lille smule tid. 521 00:17:42,390 --> 00:17:43,442 Du skal være nummer et. 522 00:17:43,442 --> 00:17:44,150 Hvad er dit navn? 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 Hvad er dit navn? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. MALAN: Joseph, du er nummer to. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, nummer tre. 530 00:17:52,260 --> 00:17:53,722 Stefan nummer fire. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. MALAN: Cynthia, nummer fem. 533 00:17:57,548 --> 00:17:58,452 [Uhørligt] 534 00:17:58,452 --> 00:17:59,618 DAVID J. MALAN: [uhørligt]. 535 00:17:59,618 --> 00:18:00,391 David nummer seks. 536 00:18:00,391 --> 00:18:00,890 MAT: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. MALAN: Matt nummer syv. 538 00:18:02,160 --> 00:18:02,850 Og? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. MALAN: Waverly, nummer otte. 541 00:18:04,470 --> 00:18:04,970 Okay. 542 00:18:04,970 --> 00:18:06,510 Hvis du could-- hovsa. 543 00:18:06,510 --> 00:18:08,820 Hvis du alt, som din første udfordring, der 544 00:18:08,820 --> 00:18:10,820 er otte musik stande her overfor publikum. 545 00:18:10,820 --> 00:18:14,200 Hvis du kunne sætte dine numre på disse musikken står på en sådan måde 546 00:18:14,200 --> 00:18:16,560 at de i linje med samme tal på tavlen. 547 00:18:16,560 --> 00:18:19,560 Så gør jer selv til at ligne, at ved sætte dine numre på disse musik 548 00:18:19,560 --> 00:18:21,960 står her. 549 00:18:21,960 --> 00:18:25,980 Fremragende hidtil. 550 00:18:25,980 --> 00:18:26,600 >> Fremragende. 551 00:18:26,600 --> 00:18:26,890 OK. 552 00:18:26,890 --> 00:18:29,556 Så nu, vi vil bede spørgsmål i et par forskellige måder. 553 00:18:29,556 --> 00:18:31,610 Hvordan kan vi gå om sortering disse folk her? 554 00:18:31,610 --> 00:18:34,500 Fordi vi havde et par tilgange tidligere, hvorved vi var 555 00:18:34,500 --> 00:18:36,360 slags gør to forskellige spande. 556 00:18:36,360 --> 00:18:38,842 Og så var vi generelt patchwork ting sammen. 557 00:18:38,842 --> 00:18:41,050 Så snart vi så to numre som tilhørte sammen, 558 00:18:41,050 --> 00:18:41,975 vi sætter dem sammen. 559 00:18:41,975 --> 00:18:43,350 To bogstaver, der hører sammen. 560 00:18:43,350 --> 00:18:45,058 >> Men lad os se, om vi kan ikke formalisere dette, 561 00:18:45,058 --> 00:18:48,044 således at vi i sidste ende har nogle pseudo-kode, du vil, 562 00:18:48,044 --> 00:18:49,710 som du kan løse disse problemer. 563 00:18:49,710 --> 00:18:51,870 Så nu, jeg kigger ud på disse numre her. 564 00:18:51,870 --> 00:18:55,030 Og jeg ser en hel masse fejl. 565 00:18:55,030 --> 00:18:57,750 I sidste ende, jeg ønsker en på venstre og otte til højre. 566 00:18:57,750 --> 00:19:00,650 >> Og så jeg kigger på disse to, fire og to. 567 00:19:00,650 --> 00:19:02,930 Og hvad er problemet, naturligvis? 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 To naturligvis kommer før fire, så ved du hvad? 571 00:19:07,160 --> 00:19:10,210 Lad mig først tage en grådig tilgang, hvis du vil, meget gerne problem 572 00:19:10,210 --> 00:19:13,790 sæt en-- hvis du husker fra Standard Edition af Problem Set One, 573 00:19:13,790 --> 00:19:16,820 hvor jeg bare lokalt løse problemet det er lige her foran mig 574 00:19:16,820 --> 00:19:17,690 og se, hvor det fører mig. 575 00:19:17,690 --> 00:19:17,870 >> OK. 576 00:19:17,870 --> 00:19:20,161 Så to og fire, lad mig gå videre og bare bytte dig to. 577 00:19:20,161 --> 00:19:22,400 Hvis du fysisk kan bevæge jer selv og dit papir, 578 00:19:22,400 --> 00:19:25,040 Jeg synes at have fået den listen i en bedre tilstand. 579 00:19:25,040 --> 00:19:26,330 >> Nu, de er gode. 580 00:19:26,330 --> 00:19:28,480 Jeg har tænkt mig at komme videre, fire og seks, ser godt ud. 581 00:19:28,480 --> 00:19:29,110 Ikke et problem. 582 00:19:29,110 --> 00:19:30,440 Seks og otte, OK. 583 00:19:30,440 --> 00:19:31,860 Otte en, et andet problem. 584 00:19:31,860 --> 00:19:34,750 For hvad er sandt omkring otte og en? 585 00:19:34,750 --> 00:19:36,990 Man kommer før otte, og så hvad skal vi gøre? 586 00:19:36,990 --> 00:19:38,090 Lad os bytte disse to. 587 00:19:38,090 --> 00:19:39,316 One og otte. 588 00:19:39,316 --> 00:19:40,690 Og nu, jeg har tænkt mig at holde ud. 589 00:19:40,690 --> 00:19:42,030 Jeg har tænkt mig at holde se fremad. 590 00:19:42,030 --> 00:19:42,840 Og lad os se hvad der sker. 591 00:19:42,840 --> 00:19:44,680 Otte og tre, af naturligvis ude af drift. 592 00:19:44,680 --> 00:19:45,815 Lad os bytte. 593 00:19:45,815 --> 00:19:46,940 Otte og syv, selvfølgelig. 594 00:19:46,940 --> 00:19:47,481 Virker ikke. 595 00:19:47,481 --> 00:19:48,280 Lad os bytte. 596 00:19:48,280 --> 00:19:49,940 Otte og fem, selvfølgelig, lad os bytte. 597 00:19:49,940 --> 00:19:50,560 Okay. 598 00:19:50,560 --> 00:19:51,880 Listen er sorteret. 599 00:19:51,880 --> 00:19:53,060 Ja? 600 00:19:53,060 --> 00:19:54,280 >> OK, naturligvis ikke. 601 00:19:54,280 --> 00:19:55,860 Men det er lidt bedre, ikke? 602 00:19:55,860 --> 00:19:57,270 Fordi varsel, hvad der skete. 603 00:19:57,270 --> 00:20:01,749 Hver gang vi udførte en swap, en mindre Antallet slags sivet den måde, 604 00:20:01,749 --> 00:20:03,790 og et større antal nedsives på denne måde, eller vi 605 00:20:03,790 --> 00:20:06,880 begynde at sige boblede til venstre eller boblet til højre. 606 00:20:06,880 --> 00:20:10,080 >> Nu er det ikke nok, fordi i bedste fald en række måske 607 00:20:10,080 --> 00:20:11,990 har flyttet ét sted frem, eller i værste fald, 608 00:20:11,990 --> 00:20:13,880 en række kan have flyttet et sted yderligere. 609 00:20:13,880 --> 00:20:16,369 Så du ved, hvad denne form af fungerede temmelig godt indtil videre. 610 00:20:16,369 --> 00:20:17,410 Lad mig bare prøve det igen. 611 00:20:17,410 --> 00:20:18,880 To og fire, de er OK. 612 00:20:18,880 --> 00:20:20,180 Fire og seks, de er OK. 613 00:20:20,180 --> 00:20:21,790 Seks og en, ude af drift. 614 00:20:21,790 --> 00:20:23,007 Så lad os bytte dig to. 615 00:20:23,007 --> 00:20:25,840 Og nu, mærke problemet er begynder at få lidt bedre igen. 616 00:20:25,840 --> 00:20:27,006 Seks og tre, ude af drift. 617 00:20:27,006 --> 00:20:28,100 Lad os bytte dig to. 618 00:20:28,100 --> 00:20:29,730 Seks og syv, du er god. 619 00:20:29,730 --> 00:20:32,230 Syv og fem naturligvis ude af drift. 620 00:20:32,230 --> 00:20:33,920 Syv og otte, i orden. 621 00:20:33,920 --> 00:20:36,470 Og nu, kan jeg nødt til at gøre dette et par gange mere. 622 00:20:36,470 --> 00:20:39,830 Og i virkeligheden, tror for jer selv måske hvor mange gange maksimalt 623 00:20:39,830 --> 00:20:41,330 jeg måske nødt til at gå frem og tilbage? 624 00:20:41,330 --> 00:20:42,390 >> Vi vil komme tilbage til det. 625 00:20:42,390 --> 00:20:43,700 Så to og fire er stadig OK. 626 00:20:43,700 --> 00:20:44,940 Fire og en, nej. 627 00:20:44,940 --> 00:20:45,747 Så lad os bytte. 628 00:20:45,747 --> 00:20:47,830 Og igen, mærke visuelt en er slags boblende 629 00:20:47,830 --> 00:20:49,163 til venstre, hvor det burde være. 630 00:20:49,163 --> 00:20:50,010 Fire og tre swap. 631 00:20:50,010 --> 00:20:51,330 Fire og seks. 632 00:20:51,330 --> 00:20:53,100 Seks og fem swap. 633 00:20:53,100 --> 00:20:53,959 Seks og syv. 634 00:20:53,959 --> 00:20:55,000 Syv og otte er gode. 635 00:20:55,000 --> 00:20:55,500 >> Godt. 636 00:20:55,500 --> 00:20:58,460 Vi får endnu bedre. 637 00:20:58,460 --> 00:20:59,130 Så lad os se. 638 00:20:59,130 --> 00:21:00,940 Nu har vi to og en. 639 00:21:00,940 --> 00:21:02,520 Selvfølgelig, bytte. 640 00:21:02,520 --> 00:21:07,520 To og tre, tre og fire, fire og fem, seks og syv, syv og otte. 641 00:21:07,520 --> 00:21:08,020 Godt. 642 00:21:08,020 --> 00:21:08,730 Og ved du hvad? 643 00:21:08,730 --> 00:21:11,190 Fordi jeg lavet én ændring der, lad mig gøre én tilregnelighed check. 644 00:21:11,190 --> 00:21:13,023 Lad mig gå hele vejen tilbage til begyndelsen. 645 00:21:13,023 --> 00:21:13,680 OK. 646 00:21:13,680 --> 00:21:14,750 En, to-- yup, se? 647 00:21:14,750 --> 00:21:15,870 Noget var galt. 648 00:21:15,870 --> 00:21:18,420 Tre, fire, fem, seks, syv, otte. 649 00:21:18,420 --> 00:21:21,920 Og i denne sidste aflevering, er dig komfortabel med min nu 650 00:21:21,920 --> 00:21:23,830 hævdede, at det sorteres? 651 00:21:23,830 --> 00:21:24,330 OK. 652 00:21:24,330 --> 00:21:25,880 Visuelt, det er helt rigtigt. 653 00:21:25,880 --> 00:21:28,410 Men funktionelt, hvad gjorde også bare ske 654 00:21:28,410 --> 00:21:31,870 i den sidste aflevering, der giver dig at bekræfte, at denne liste er faktisk 655 00:21:31,870 --> 00:21:32,660 sorteres? 656 00:21:32,660 --> 00:21:34,477 >> Hvad gjorde jeg gøre eller ikke gøre det sidste pass? 657 00:21:34,477 --> 00:21:35,810 PUBLIKUM: Der var ingen ændringer. 658 00:21:35,810 --> 00:21:36,120 DAVID J. MALAN: Beklager? 659 00:21:36,120 --> 00:21:37,070 PUBLIKUM: Ingen ændringer. 660 00:21:37,070 --> 00:21:38,653 DAVID J. MALAN: Der var ingen ændringer. 661 00:21:38,653 --> 00:21:41,947 Så det ville være dumt af mig at gøre det samme algoritme igen 662 00:21:41,947 --> 00:21:43,780 hvis jeg ikke gøre nogen ændrer første gang. 663 00:21:43,780 --> 00:21:45,160 Og staten har ikke ændret sig. 664 00:21:45,160 --> 00:21:47,576 Sikkert, jeg ikke vil gøre foretage ændringer anden gang. 665 00:21:47,576 --> 00:21:49,820 Og så, det er sikkert nu at sige, er listen sorteres. 666 00:21:49,820 --> 00:21:52,069 >> Og ja, det er nu noget, som vi får generelt 667 00:21:52,069 --> 00:21:56,900 opkald boble sortere, hvorved parvis, du rette fejl igen, 668 00:21:56,900 --> 00:22:00,210 og igen og igen, og du holde gå frem og tilbage, 669 00:22:00,210 --> 00:22:03,370 og frem og tilbage, indtil du foretage sådanne swaps, på hvilket tidspunkt 670 00:22:03,370 --> 00:22:07,089 du kan være sikker, yeah, jeg færdig fastsættelse alle de fejltagelser. 671 00:22:07,089 --> 00:22:08,630 Lad os nulstillet og prøve en anden tilgang. 672 00:22:08,630 --> 00:22:11,590 Hvis du fyre kunne gå tilbage i den rækkefølge, du var for et øjeblik siden, 673 00:22:11,590 --> 00:22:13,780 der lignede dette. 674 00:22:13,780 --> 00:22:17,640 Lad os nu tage en tilgang et lidt mere ligesom eksamen bog, 675 00:22:17,640 --> 00:22:21,122 hvorved vi var konstant vælge bogstav i alfabetet 676 00:22:21,122 --> 00:22:22,830 at vi slags ønskede at behandle næste. 677 00:22:22,830 --> 00:22:26,420 Måske var det en høj bogstav, som A, eller en lav brev Z. 678 00:22:26,420 --> 00:22:28,170 >> Så alle er tilbage i denne rækkefølge. 679 00:22:28,170 --> 00:22:29,800 Og lad mig gøre det. 680 00:22:29,800 --> 00:22:34,880 Lad os se, jeg ved, jeg har otte numre her. 681 00:22:34,880 --> 00:22:37,410 Jeg har tænkt mig at gå videre og bare bevidst vælger 682 00:22:37,410 --> 00:22:38,520 de mindste elementer. 683 00:22:38,520 --> 00:22:38,760 Højre? 684 00:22:38,760 --> 00:22:39,801 Dette synes også intuitiv. 685 00:22:39,801 --> 00:22:42,560 Hvorfor kan jeg ikke finde den mindste element, sætte den hvor den hører, 686 00:22:42,560 --> 00:22:45,280 derefter få den næstmindste element, sætte den, hvor det hører hjemme, og bare gentage. 687 00:22:45,280 --> 00:22:46,820 >> Fordi intuitivt, der bør arbejde også. 688 00:22:46,820 --> 00:22:48,441 Så fire, det er en temmelig lille antal. 689 00:22:48,441 --> 00:22:49,940 Jeg har tænkt mig at huske, hvor det er. 690 00:22:49,940 --> 00:22:50,523 Vent et minut. 691 00:22:50,523 --> 00:22:51,577 To er mindre. 692 00:22:51,577 --> 00:22:53,910 Lad mig nu huske, hvor to er, og glemme alt om fire. 693 00:22:53,910 --> 00:22:55,050 Vi vil beskæftige sig med det senere. 694 00:22:55,050 --> 00:22:56,460 Seks, jeg er ikke interesseret. 695 00:22:56,460 --> 00:22:57,810 Otte, jeg er ikke interesseret i. 696 00:22:57,810 --> 00:22:59,780 Den ene er min nye lille antal. 697 00:22:59,780 --> 00:23:01,470 Så jeg har tænkt mig at huske, hvor man er. 698 00:23:01,470 --> 00:23:02,534 Tre, ikke interesseret. 699 00:23:02,534 --> 00:23:03,450 Syv, ikke interesseret. 700 00:23:03,450 --> 00:23:04,530 Fem, ikke interesseret. 701 00:23:04,530 --> 00:23:07,390 >> Så uden at falde ned scenen i år, 702 00:23:07,390 --> 00:23:09,890 Jeg har tænkt mig at få fat i nummer en-- og hvad var dit navn igen? 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 Og hvis du kunne slutte sig til mig på begyndelsen af ​​listen, 706 00:23:13,540 --> 00:23:14,870 lad os sætte dig, hvor du hører til. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- hvad er dit navn? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. MALAN: Stefan er i vejen. 710 00:23:18,191 --> 00:23:23,490 Så før Stefan løser dette problem, hvad skal vi gøre? 711 00:23:23,490 --> 00:23:25,412 Hvad gør vi med Stefan? 712 00:23:25,412 --> 00:23:27,269 >> PUBLIKUM: [uhørligt]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. MALAN: OK. 714 00:23:28,060 --> 00:23:28,850 Så vi kunne gøre det. 715 00:23:28,850 --> 00:23:31,730 Vi kunne slags tage Stefan og hans fire, og bare sætte det i en variabel 716 00:23:31,730 --> 00:23:33,530 og holde på det for en vis mængde tid, 717 00:23:33,530 --> 00:23:35,220 hvorved plads til nummer et. 718 00:23:35,220 --> 00:23:36,280 Og det er ikke dårligt. 719 00:23:36,280 --> 00:23:39,270 Jeg kunne foreslå, hvorfor ikke vi bare sætte Stefan her? 720 00:23:39,270 --> 00:23:41,610 Hvorfor kan dette krænke en af de idéer vi startede 721 00:23:41,610 --> 00:23:44,830 taler om sidste gang, i sidste uge? 722 00:23:44,830 --> 00:23:45,330 Ja? 723 00:23:45,330 --> 00:23:45,740 >> PUBLIKUM: [uhørligt]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. MALAN: Der er ingen indeks for det. 725 00:23:46,860 --> 00:23:49,735 Hvis du tænker på dette, ja, som en array, det er ligesom negativ, 726 00:23:49,735 --> 00:23:52,900 så der er ingen hukommelse faktisk her, hvis dette er faktisk et array, 727 00:23:52,900 --> 00:23:55,090 ligesom vi erklærede i sidste uge i forelæsning. 728 00:23:55,090 --> 00:23:56,250 Så vi skal ikke gøre dette. 729 00:23:56,250 --> 00:23:57,340 Vi kunne gemme det i en variabel. 730 00:23:57,340 --> 00:23:57,820 >> Eller ved du hvad? 731 00:23:57,820 --> 00:23:59,153 Jeg hørte en anden foreslå det. 732 00:23:59,153 --> 00:24:01,020 Hvad andet kunne vi gøre med Stefan? 733 00:24:01,020 --> 00:24:03,770 Hvorfor gør vi ikke bare smide ham og sætte ham over, hvor nummer et var. 734 00:24:03,770 --> 00:24:05,170 Så hvis du ønsker at gå derovre. 735 00:24:05,170 --> 00:24:07,300 Og ja, det er en temmelig god løsning. 736 00:24:07,300 --> 00:24:10,480 Nu på den ene side, har jeg slags af gjort problemet værre. 737 00:24:10,480 --> 00:24:13,650 Fire er nu længere væk hvorfra det skulle være. 738 00:24:13,650 --> 00:24:14,900 Det bør være mod dette halve. 739 00:24:14,900 --> 00:24:16,100 >> Men ved du hvad? 740 00:24:16,100 --> 00:24:17,630 Det kunne have været uheld. 741 00:24:17,630 --> 00:24:18,822 Måske nummer otte var her. 742 00:24:18,822 --> 00:24:20,530 Og så, måske vi ville har fået heldig, 743 00:24:20,530 --> 00:24:22,460 og skubbede otte tættere på slutningen. 744 00:24:22,460 --> 00:24:24,710 Så i slutningen af ​​dagen, Den slags alle gennemsnit ud. 745 00:24:24,710 --> 00:24:26,085 Vi behøver ikke at bekymre sig om fire. 746 00:24:26,085 --> 00:24:29,400 Alt jeg holder lige nu er vælge den mindste element. 747 00:24:29,400 --> 00:24:32,030 >> Og nu, hvad jeg har tænkt mig at gøre, er at glemme alt om nummer et 748 00:24:32,030 --> 00:24:35,160 permanent, fordi jeg ved det Listen bag mig nu sorteres. 749 00:24:35,160 --> 00:24:36,720 Så min liste var tidligere størrelse otte. 750 00:24:36,720 --> 00:24:37,720 Nu er det i størrelse syv. 751 00:24:37,720 --> 00:24:40,340 Så mit problem er at få mindre, end lineært. 752 00:24:40,340 --> 00:24:43,022 Så nu, jeg skal til at vælge det nuværende mindste element, to. 753 00:24:43,022 --> 00:24:46,520 Seks, otte, fire, tre, syv, fem. 754 00:24:46,520 --> 00:24:47,770 Det var det mindste element. 755 00:24:47,770 --> 00:24:49,416 Så hvad skal jeg gøre med-- Hvad var dit navn igen? 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 Vi kommer til at forlade Josef på plads. 759 00:24:52,000 --> 00:24:54,842 Nu, jeg har tænkt mig at foregive at disse fyre are-- godt, 760 00:24:54,842 --> 00:24:56,550 Jeg ved, at disse to allerede sorteret. 761 00:24:56,550 --> 00:24:58,424 Lad os nu fokusere på den Resten af ​​listen. 762 00:24:58,424 --> 00:25:00,080 Seks er den nuværende mindste. 763 00:25:00,080 --> 00:25:01,190 Otte er større. 764 00:25:01,190 --> 00:25:02,970 Fire er nu den aktuelle mindste. 765 00:25:02,970 --> 00:25:04,762 Tre er nu den aktuelle mindste. 766 00:25:04,762 --> 00:25:07,720 Og så nu, jeg har tænkt mig at vælge tre, hvem is-- hvad er dit navn igen? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. MALAN: Serena, hvis du kunne Grib dit nummer og swap med-- 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 Kom tilbage, og vi er kommer til at bytte de to. 772 00:25:15,220 --> 00:25:17,360 Og nu, lad os sætte dette på autopilot. 773 00:25:17,360 --> 00:25:21,589 Jeg har tænkt mig at gå og overlade det til jer at vælge den næste mindste elementer. 774 00:25:21,589 --> 00:25:22,380 Dun, dun, dun, dun. 775 00:25:22,380 --> 00:25:24,560 Nummer fire, hvad skal du gøre? 776 00:25:24,560 --> 00:25:26,261 Fremragende. 777 00:25:26,261 --> 00:25:27,760 Nu, jeg har tænkt mig at gøre en anden bolden. 778 00:25:27,760 --> 00:25:28,590 Dun, dun, dun, dun. 779 00:25:28,590 --> 00:25:31,465 Jeg ser fem er den næstmindste. 780 00:25:31,465 --> 00:25:32,840 Nu, jeg har tænkt mig at tage en anden pass. 781 00:25:32,840 --> 00:25:33,631 Dun, dun, dun, dun. 782 00:25:33,631 --> 00:25:34,880 Seks er den mindste. 783 00:25:34,880 --> 00:25:35,520 Godt. 784 00:25:35,520 --> 00:25:36,585 Syv er den mindste. 785 00:25:36,585 --> 00:25:37,085 Ingen ændring. 786 00:25:37,085 --> 00:25:38,630 Otte er den mindste. 787 00:25:38,630 --> 00:25:39,170 Færdig. 788 00:25:39,170 --> 00:25:43,900 >> Så hvad vi har netop gjort ved iterativt vælge et element efter den anden 789 00:25:43,900 --> 00:25:47,230 er gennemføre noget, som vi er kommer til at formalisere som udvælgelse slags. 790 00:25:47,230 --> 00:25:49,120 Og det er måske endda enklere at forklare, 791 00:25:49,120 --> 00:25:51,310 i det bogstaveligt talt alt, hvad du ønsker at gøre, er bare holde 792 00:25:51,310 --> 00:25:54,700 gå frem og tilbage gennem listen vælge den næstmindste element, 793 00:25:54,700 --> 00:25:55,720 indtil du er færdig. 794 00:25:55,720 --> 00:25:58,650 >> Så det er endnu enklere, måske intuitivt, end sidste. 795 00:25:58,650 --> 00:26:00,020 Lad os prøve en sidste. 796 00:26:00,020 --> 00:26:03,060 Hvis du fyre kunne nulstille jer i følgende positioner 797 00:26:03,060 --> 00:26:08,600 en sidste gang, lad os se om vi ikke kan nu formalisere en anden tilgang. 798 00:26:08,600 --> 00:26:12,857 Faktisk ville en person derude gerne foreslå 799 00:26:12,857 --> 00:26:14,440 hvordan vi ellers kan gå om at gøre dette? 800 00:26:14,440 --> 00:26:17,439 Uden at smide ud buzzwords eller sortering af svar, der allerede er kendt, 801 00:26:17,439 --> 00:26:19,689 bare intuitivt, hvad kunne vi gøre? 802 00:26:19,689 --> 00:26:21,635 >> PUBLIKUM: [uhørligt]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. MALAN: Ja. 804 00:26:22,510 --> 00:26:24,620 Så der er nogle store intuition der. 805 00:26:24,620 --> 00:26:28,020 Gode ​​ting synes at ske hidtil i datalogi, når vi deler 806 00:26:28,020 --> 00:26:30,832 og erobre problemet med at opdele det i halve og halvt. 807 00:26:30,832 --> 00:26:32,540 Og så ja, vi kunne begynde at gøre det. 808 00:26:32,540 --> 00:26:35,754 Og i virkeligheden, er det kommer til at være, vil vi se, en af ​​vores bedste løsninger endnu. 809 00:26:35,754 --> 00:26:37,420 Men lad os vende tilbage til det inden længe. 810 00:26:37,420 --> 00:26:40,500 Faktisk vil vi gøre at lidt senere på ugen. 811 00:26:40,500 --> 00:26:42,180 Hvad andet kan vi gøre for at løse dette? 812 00:26:42,180 --> 00:26:44,647 Så alle her er i tilsyneladende tilfældig rækkefølge. 813 00:26:44,647 --> 00:26:45,230 Du ved hvad? 814 00:26:45,230 --> 00:26:48,320 Snarere end at gå frem og tilbage, frem og tilbage, frem og tilbage 815 00:26:48,320 --> 00:26:50,624 hver gang, det føles Jeg gør en masse Walking. 816 00:26:50,624 --> 00:26:52,790 Hvorfor kan jeg ikke bare starte på begyndelsen af ​​listen, 817 00:26:52,790 --> 00:26:54,960 og bare sætte fire hvor det hører hjemme? 818 00:26:54,960 --> 00:26:59,680 Så lad mig antage for det øjeblik, min liste er kun denne første element. 819 00:26:59,680 --> 00:27:04,937 Er fire sorteres på nuværende tidspunkt, hvis alle jeg holder af, er alt her? 820 00:27:04,937 --> 00:27:06,520 Det er en slags trivielt sandt, ikke? 821 00:27:06,520 --> 00:27:10,000 Ligesom den liste, der indeholder ét nummer, og at nummer fire er naturligvis sorteres. 822 00:27:10,000 --> 00:27:13,070 >> Så lad mig bare fastsætte at denne liste er sorteret. 823 00:27:13,070 --> 00:27:15,090 Men nu har jeg resten af ​​denne liste. 824 00:27:15,090 --> 00:27:17,240 Så nu, støder jeg to. 825 00:27:17,240 --> 00:27:21,690 Hvor kommer to tydeligvis hører med hensyn til fire? 826 00:27:21,690 --> 00:27:22,580 Før fire. 827 00:27:22,580 --> 00:27:23,862 Så hvad kan jeg gøre her? 828 00:27:23,862 --> 00:27:24,820 Hvad er dit navn igen? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. MALAN: Joseph, hvis du kunne gå tilbage 831 00:27:26,030 --> 00:27:27,790 for bare et øjeblik med dit nummer. 832 00:27:27,790 --> 00:27:31,130 Og nu hvad skal Stefan gøre her? 833 00:27:31,130 --> 00:27:33,720 Lad os flytte Stefan herovre. 834 00:27:33,720 --> 00:27:35,520 Og nu, lad Josef komme herind. 835 00:27:35,520 --> 00:27:39,660 Og nu, lad mig påstå, at alt her er sorteret. 836 00:27:39,660 --> 00:27:42,474 Så lignende resultat, men en fundamentalt anderledes tilgang. 837 00:27:42,474 --> 00:27:44,140 Jeg har ikke engang set, hvad der er dernede. 838 00:27:44,140 --> 00:27:46,310 Jeg bare fortsætte med at tage de elementer da de er givet til mig, 839 00:27:46,310 --> 00:27:47,240 og håndtere dem. 840 00:27:47,240 --> 00:27:48,330 >> Så nu ser jeg nummer seks. 841 00:27:48,330 --> 00:27:51,110 Hvor kommer nummer seks tilhører? 842 00:27:51,110 --> 00:27:53,250 Vi har to, fire, seks. 843 00:27:53,250 --> 00:27:54,800 Præcis hvor hun er lige nu. 844 00:27:54,800 --> 00:27:57,750 Så lad os overlade det alene, og nu hævder, at denne del af listen 845 00:27:57,750 --> 00:27:58,772 er nu sorteret. 846 00:27:58,772 --> 00:28:01,230 Og så, det føles fundamentalt anderledes, idet jeg bare 847 00:28:01,230 --> 00:28:05,230 bevæger sig gennem listen her lineært, og jeg aldrig fordobling tilbage. 848 00:28:05,230 --> 00:28:05,730 Ja. 849 00:28:05,730 --> 00:28:06,230 Okay. 850 00:28:06,230 --> 00:28:08,190 Så otte, hvor vil du hører? 851 00:28:08,190 --> 00:28:08,730 Lige her. 852 00:28:08,730 --> 00:28:09,310 Perfekt. 853 00:28:09,310 --> 00:28:10,210 Så nu, en. 854 00:28:10,210 --> 00:28:10,900 Uh-oh. 855 00:28:10,900 --> 00:28:13,010 Dette føles som om det er ville være dyrt. 856 00:28:13,010 --> 00:28:15,690 Nu, i den foregående algoritme, Jeg har lige byttet mennesker. 857 00:28:15,690 --> 00:28:18,648 Så jeg kan sætte ham hele vejen på begyndelsen, men derefter flyttet Joseph. 858 00:28:18,648 --> 00:28:21,450 Men hvis jeg flytter Josef, nu hvad der kommer til at være galt? 859 00:28:21,450 --> 00:28:24,250 >> Nu har jeg slags undone-- jeg har taget et skridt fremad og derefter 860 00:28:24,250 --> 00:28:26,300 et skridt tilbage, for nu Joseph ville være ude af drift. 861 00:28:26,300 --> 00:28:26,830 Så lad os gøre det. 862 00:28:26,830 --> 00:28:29,150 Hvis du kunne tage nummer et og skridt tilbage for et øjeblik. 863 00:28:29,150 --> 00:28:30,490 Hvordan kan vi put-- hvad var dit navn igen? 864 00:28:30,490 --> 00:28:31,130 >> ANNAN: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. MALAN: Annan på plads? 866 00:28:32,610 --> 00:28:36,091 Hvad skal der ske med respekt til to, fire, seks, otte og? 867 00:28:36,091 --> 00:28:37,570 De har alle brug for at flytte. 868 00:28:37,570 --> 00:28:42,590 Så hvis otte ønsker at flytte først, derefter seks, derefter fire, derefter to. 869 00:28:42,590 --> 00:28:45,380 Og så Annan, hvis du ville gerne komme herind, god. 870 00:28:45,380 --> 00:28:47,760 Men her, vi har bare slags betalt en pris 871 00:28:47,760 --> 00:28:49,510 på et andet punkt i algoritmen. 872 00:28:49,510 --> 00:28:52,550 Hvorimod sidste gang med udvælgelsen sortere og endda boble sortere, 873 00:28:52,550 --> 00:28:54,700 Jeg går tilbage og frem, frem og tilbage, 874 00:28:54,700 --> 00:28:58,360 der er helt sikkert addere tidsmæssigt, og bogstaveligt trinvis. 875 00:28:58,360 --> 00:29:00,660 >> Indsættelse sortere, først øjekast ser det er 876 00:29:00,660 --> 00:29:05,150 super smartere, idet jeg bare skrider langsomt, trinvise fremskridt, 877 00:29:05,150 --> 00:29:07,120 men jeg har ikke tænkt mig det frem og tilbage. 878 00:29:07,120 --> 00:29:09,410 Men hvis nogen er faktisk ude af drift, varsel 879 00:29:09,410 --> 00:29:10,840 alt det arbejde, jeg havde bare at gøre. 880 00:29:10,840 --> 00:29:14,750 Jeg måtte flytte halvdelen af ​​listen bare for at gøre plads til nummer et. 881 00:29:14,750 --> 00:29:16,790 Så det er det samme beløb af hidtidige arbejde det 882 00:29:16,790 --> 00:29:18,690 føles, bare en anden type arbejde. 883 00:29:18,690 --> 00:29:19,370 >> Lad os fortsætte. 884 00:29:19,370 --> 00:29:22,657 Så nu ved vi, at alle mellem en og otte sorteres. 885 00:29:22,657 --> 00:29:23,740 Her har jeg nummer tre. 886 00:29:23,740 --> 00:29:25,864 Hvis du kan lide at samle op nummer tre, gå tilbage én. 887 00:29:25,864 --> 00:29:28,260 Og hvad gør du fyre nødt til at gøre? 888 00:29:28,260 --> 00:29:28,760 Yep. 889 00:29:28,760 --> 00:29:33,070 Så det er en anden en, to, tre trin. 890 00:29:33,070 --> 00:29:36,010 Tre tidsenheder, der bare koster mig, så at tre kan nu passe. 891 00:29:36,010 --> 00:29:37,460 Endelig syv. 892 00:29:37,460 --> 00:29:39,730 >> Lad os gå videre og have du tager et skridt tilbage. 893 00:29:39,730 --> 00:29:42,780 Dette er kun vil koste os en enhed af tid, men det er OK. 894 00:29:42,780 --> 00:29:44,170 Og nu, fem kommer til at være lidt dyrere. 895 00:29:44,170 --> 00:29:45,340 Hvis du gerne vil til at træde tilbage. 896 00:29:45,340 --> 00:29:48,380 Vi er nødt til at flytte otte, og syv og seks. 897 00:29:48,380 --> 00:29:50,749 Og så alle er nu sorteres. 898 00:29:50,749 --> 00:29:52,290 Så en stor hånd til vores frivillige her. 899 00:29:52,290 --> 00:29:53,554 Mange tak. 900 00:29:53,554 --> 00:29:56,220 >> [Applaus] 901 00:29:56,220 --> 00:29:56,860 >> Tak allesammen. 902 00:29:56,860 --> 00:29:57,520 Tak allesammen. 903 00:29:57,520 --> 00:30:02,940 Så lad os nu se, hvor kostbare alt dette var. 904 00:30:02,940 --> 00:30:06,210 Lad os betragte måske simpleste af disse, bubble slags. 905 00:30:06,210 --> 00:30:09,950 Og jeg siger enkleste, kun fordi du kan løse det grådigt ved blot 906 00:30:09,950 --> 00:30:11,660 løse den parvise problem her. 907 00:30:11,660 --> 00:30:13,720 Løs den parvise problem her, igen og igen 908 00:30:13,720 --> 00:30:17,680 og igen, at gentage så mange gange som du faktisk har brug for. 909 00:30:17,680 --> 00:30:21,050 >> Så det viser sig, at med en boble sortere, godt, 910 00:30:21,050 --> 00:30:25,820 hvor mange skridt skal jeg tage på den første passage af denne algoritme? 911 00:30:25,820 --> 00:30:30,850 Jeg kunne take-- lad os see-- én, to, tre, fire, fem, seks, syv. 912 00:30:30,850 --> 00:30:32,190 Og der er otte elementer her. 913 00:30:32,190 --> 00:30:35,280 Så det er ligesom n minus 1 trin til komme fra begyndelsen af ​​listen 914 00:30:35,280 --> 00:30:36,380 til slutningen af ​​listen. 915 00:30:36,380 --> 00:30:41,350 >> Men med valg Sorter, minde om, at jeg er vælge elementerne igen og igen 916 00:30:41,350 --> 00:30:44,590 og igen, at mindste, Jeg sætte det på plads, 917 00:30:44,590 --> 00:30:46,616 men så er jeg ikke ser bag mig igen. 918 00:30:46,616 --> 00:30:49,490 Så jeg synes det er lidt mere klar da, at det første gang, jeg kunne 919 00:30:49,490 --> 00:30:52,680 nødt til at tage alle n minus 1 trin at finde det mindste element. 920 00:30:52,680 --> 00:30:55,920 Så jeg sætte dem på plads, og jeg forjage hvem var her tidligere. 921 00:30:55,920 --> 00:30:57,500 >> Men så har jeg ikke til holde udkig på dette element, 922 00:30:57,500 --> 00:30:59,040 fordi jeg ved, det er allerede de mindste. 923 00:30:59,040 --> 00:31:01,581 Så nu kan jeg se på bare syv elementer, derefter seks elementer, 924 00:31:01,581 --> 00:31:03,290 derefter fem elementer, derefter fire elementer. 925 00:31:03,290 --> 00:31:06,900 Og så matematisk, hvis n er antallet af elementer eller numre 926 00:31:06,900 --> 00:31:11,990 at vi startede med, kan du forestille dig at dette er det samme som n minus 1, 927 00:31:11,990 --> 00:31:14,250 plus n minus 2 trin, plus n minus 3 trin, 928 00:31:14,250 --> 00:31:16,780 plus n minus 4 trin, hele vejen ned til kun et skridt. 929 00:31:16,780 --> 00:31:18,160 Og jeg er på min sidste person. 930 00:31:18,160 --> 00:31:20,650 >> Og hvis du husker, at en masse af statistik bøger eller matematiske bøger 931 00:31:20,650 --> 00:31:24,730 har disse formler på Indbundet ryggen eller foran dem, 932 00:31:24,730 --> 00:31:27,690 Det viser sig, at denne serie kan udtrykkes mere enkelt 933 00:31:27,690 --> 00:31:28,857 som n gange n minus 1 over 2. 934 00:31:28,857 --> 00:31:31,273 Og det er fint, hvis det ikke er på forkant med dit sind. 935 00:31:31,273 --> 00:31:32,420 Men dette er faktisk sandt. 936 00:31:32,420 --> 00:31:34,449 Det er bare en enklere måde at skrive det. 937 00:31:34,449 --> 00:31:36,240 Og så hvis du tror tilbage til folkeskolen, 938 00:31:36,240 --> 00:31:38,698 når du bare begynde at multiplicere ting ud, dette er naturligvis, 939 00:31:38,698 --> 00:31:41,820 er bare n kvadreret minus n divideres med 2. 940 00:31:41,820 --> 00:31:44,772 Alt, hvad jeg har gjort, er at udvide udtrykkene der. 941 00:31:44,772 --> 00:31:46,730 Og så lad os omskrive dette lidt anderledes. 942 00:31:46,730 --> 00:31:49,780 Der er n kvadreret divideret med 2 minus n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Så igen, jeg er bare lidt for at anvende nogle aritmetiske regler der. 944 00:31:53,270 --> 00:31:57,140 Men bemærke nu, at den største sigt i dette udtryk, så at sige, 945 00:31:57,140 --> 00:31:58,540 er, at n potens. 946 00:31:58,540 --> 00:32:02,910 Så ja, det er n kvadreret divideret med 2, minus n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Men generelt, hvis n er kommer til at være en stor værdi, 948 00:32:05,080 --> 00:32:08,740 Jeg har tænkt mig at påstå, at n kvadreret vil være den dominerende faktor. 949 00:32:08,740 --> 00:32:10,490 Det er bare kommer til at være en større bidragsyder 950 00:32:10,490 --> 00:32:12,877 til antallet af trin end n / 2. 951 00:32:12,877 --> 00:32:13,960 Så hvad mener jeg med det? 952 00:32:13,960 --> 00:32:16,795 Lad os prøve et simpelt eksempel, selv selvom matematik bliver lidt stor. 953 00:32:16,795 --> 00:32:20,210 >> Så formoder, at vi havde 1 million mennesker på scenen, eller 1 million ting 954 00:32:20,210 --> 00:32:21,320 at vi ønsker at sortere. 955 00:32:21,320 --> 00:32:23,730 Lad os sætte en million i netop denne formel 956 00:32:23,730 --> 00:32:27,230 for at se, hvor mange skridt, det tager alt at sortere en million elementer ved hjælp sige, 957 00:32:27,230 --> 00:32:28,560 udvælgelse slags. 958 00:32:28,560 --> 00:32:30,760 >> Så ville vi have den samme formel som før. 959 00:32:30,760 --> 00:32:34,120 Jeg ville sætte en million, så jeg får en million divideret med kvadratet 2, 960 00:32:34,120 --> 00:32:35,990 minus en million divideret med 2. 961 00:32:35,990 --> 00:32:40,180 Hvis jeg gør det math på forhånd her har vi 500 milliarder 962 00:32:40,180 --> 00:32:47,460 minus 500.000, som giver os 499.999.500.000, 963 00:32:47,460 --> 00:32:49,270 som er temmelig darn stor. 964 00:32:49,270 --> 00:32:54,370 >> Faktisk, hvis du sammenligner nu 499 milliarder, 999 millioner, 965 00:32:54,370 --> 00:33:01,210 500.000 mod vores oprindelige værdi, 500 milliarder, det er så forbandet tæt på. 966 00:33:01,210 --> 00:33:06,850 Højre? n kvadreret divideret med 2 giver os-- eller rettere, n kvadreret divideret med 2 967 00:33:06,850 --> 00:33:08,370 gav os 500 mia. 968 00:33:08,370 --> 00:33:13,510 Det er temmelig darn tæt til 499.999.500.000, 969 00:33:13,510 --> 00:33:17,970 hvilket vil sige at fratrække 500.000, eller mere generelt, at fratrække 970 00:33:17,970 --> 00:33:20,010 n kvadreret, egentlig ikke en big deal. 971 00:33:20,010 --> 00:33:22,490 N kvadreret gør disse tal vokser virkelig hurtigt. 972 00:33:22,490 --> 00:33:25,790 >> Nu, dette er kun vigtigt i det omfang som vi, som dataloger, 973 00:33:25,790 --> 00:33:29,350 er generelt ikke til at passe så meget om nuancerne i disse formler 974 00:33:29,350 --> 00:33:31,400 og præcis, hvad den præcise svar er. 975 00:33:31,400 --> 00:33:33,390 Vi pleje kun det, ved du hvad? 976 00:33:33,390 --> 00:33:37,810 Ved slutningen af ​​dagen, denne formel er af størrelsesordenen n potens. 977 00:33:37,810 --> 00:33:39,350 >> Ja, vi dividere med 2 derinde. 978 00:33:39,350 --> 00:33:41,360 Ja, vi fratrække off n minus 2. 979 00:33:41,360 --> 00:33:46,860 Men i slutningen af ​​dagen, udtrykket der virkelig gør ondt os og koster os 980 00:33:46,860 --> 00:33:48,995 en masse af trin er, at firkantede sigt. 981 00:33:48,995 --> 00:33:51,370 Og så hvad datalog vil generelt gøre 982 00:33:51,370 --> 00:33:54,160 er ignorere alle de mindre ordens led, 983 00:33:54,160 --> 00:33:56,900 og bare se på den, der bidrager mest til omkostningerne. 984 00:33:56,900 --> 00:34:00,530 >> Og det er rart, fordi vi kan nu taler i langt større generalitet 985 00:34:00,530 --> 00:34:02,470 om algoritmer, og kan sammenligne dem. 986 00:34:02,470 --> 00:34:04,550 Og det faktum, at jeg er ved hjælp af denne O er bevidst. 987 00:34:04,550 --> 00:34:06,680 Når jeg siger på ordren af, jeg er specielt 988 00:34:06,680 --> 00:34:09,560 henvise til noget kaldet big O. og store O 989 00:34:09,560 --> 00:34:14,090 er en notation, at en computer videnskabsmand bruger til at beskrive 990 00:34:14,090 --> 00:34:16,710 en øvre grænse på noget. 991 00:34:16,710 --> 00:34:21,150 >> Så hvis du siger, at en algoritme er i stort O n kvadreret, 992 00:34:21,150 --> 00:34:23,380 som jeg foreslog bare en øjeblik siden, det betyder 993 00:34:23,380 --> 00:34:27,710 at med hensyn til dets drift tid eller dens effektivitet, 994 00:34:27,710 --> 00:34:30,090 det tager i størrelsesordenen n kvadreret trin. 995 00:34:30,090 --> 00:34:31,420 Måske mere, måske mindre. 996 00:34:31,420 --> 00:34:33,435 Men det er på rækkefølgen af ​​n potens. 997 00:34:33,435 --> 00:34:34,560 Og det er den øvre grænse. 998 00:34:34,560 --> 00:34:36,530 Det kommer ikke til at være mere smertefuld end det. 999 00:34:36,530 --> 00:34:40,800 Det kommer ikke til at være n kubik, eller 2 til n eller noget meget større. 1000 00:34:40,800 --> 00:34:43,800 Dette er en øvre grænse på hvad det koster. 1001 00:34:43,800 --> 00:34:46,150 Så da, lad os overveje blot et par eksempler. 1002 00:34:46,150 --> 00:34:49,820 Og dette er blot en begrænset liste af meget almindelige kører tider 1003 00:34:49,820 --> 00:34:52,870 for algoritmer, der er beregnet til at være illustrativ for nogle ting, vi har 1004 00:34:52,870 --> 00:34:53,600 set allerede. 1005 00:34:53,600 --> 00:34:58,060 >> Så for eksempel i tilfælde af udvælgelse sortere, hvad jeg påstår her 1006 00:34:58,060 --> 00:35:02,250 er, at udvælgelsen sortere s kører tid er af størrelsesordenen n potens. 1007 00:35:02,250 --> 00:35:06,260 I værste fald, vil jeg have en hel masse tilfældige tal her. 1008 00:35:06,260 --> 00:35:08,600 Og som vi så matematisk, hvis jeg fortsætter med at gå 1009 00:35:08,600 --> 00:35:11,310 gennem listen, gennem listen, vælge den næstmindste 1010 00:35:11,310 --> 00:35:14,410 element igen og igen, hvis jeg faktisk nedskrive alle trinnene 1011 00:35:14,410 --> 00:35:18,750 Jeg tager som jeg foreslog formulaically før, er det på rækkefølgen af ​​n kvadreret 1012 00:35:18,750 --> 00:35:20,370 skridt, jeg tager. 1013 00:35:20,370 --> 00:35:24,520 >> Og det viser sig, at boble sortere og indsættelse sortere 1014 00:35:24,520 --> 00:35:27,370 er lige så langsomme i værste fald. 1015 00:35:27,370 --> 00:35:32,040 Overvej for eksempel, indsættelse sortere, det allersidste algoritme vi behandlet, 1016 00:35:32,040 --> 00:35:35,500 som havde os se på det element, og derefter indsætte det hvor det hører hjemme. 1017 00:35:35,500 --> 00:35:38,720 Og så har vi kigget på det næste element, og indsat det, hvor det hører hjemme. 1018 00:35:38,720 --> 00:35:40,990 >> Så overveje den bedst mulige scenario. 1019 00:35:40,990 --> 00:35:45,590 Antag jeg havde mine frivillige linje op bogstaveligt som dette, en gennem otte, 1020 00:35:45,590 --> 00:35:47,440 allerede sorteret. 1021 00:35:47,440 --> 00:35:51,300 Hvor mange trin er indsættelse sortere kommer til at tage for at sortere otte personer, 1022 00:35:51,300 --> 00:35:55,640 hvis de ankommer på scenen ser sådan ud? 1023 00:35:55,640 --> 00:35:57,410 >> Otte mennesker allerede ordnet. 1024 00:35:57,410 --> 00:35:58,760 Og jeg bruger indsættelse slags. 1025 00:35:58,760 --> 00:36:02,180 Det sidste af de algoritmer. 1026 00:36:02,180 --> 00:36:03,640 Nå, lad os reenact virkelig hurtigt. 1027 00:36:03,640 --> 00:36:05,504 Så hvis jeg starter her, ser jeg en. 1028 00:36:05,504 --> 00:36:06,420 Hvor kan man hører? 1029 00:36:06,420 --> 00:36:07,730 Det tilhører lige her. 1030 00:36:07,730 --> 00:36:08,330 Jeg ser to. 1031 00:36:08,330 --> 00:36:09,660 Hvor kommer to hører? 1032 00:36:09,660 --> 00:36:10,260 Lige her. 1033 00:36:10,260 --> 00:36:10,900 Jeg ser tre. 1034 00:36:10,900 --> 00:36:11,920 Hvor kommer tre tilhører? 1035 00:36:11,920 --> 00:36:12,480 Lige her. 1036 00:36:12,480 --> 00:36:13,100 >> Jeg ser fire. 1037 00:36:13,100 --> 00:36:13,600 Lige her. 1038 00:36:13,600 --> 00:36:15,660 Fem, seks, syv, otte. 1039 00:36:15,660 --> 00:36:17,320 Der er ingen grund til at gentage mig selv. 1040 00:36:17,320 --> 00:36:21,260 Og så, hvor mange skridt er, at i forhold til n? 1041 00:36:21,260 --> 00:36:23,870 Det er på rækkefølgen af ​​n trin, højre? n minus 1. 1042 00:36:23,870 --> 00:36:27,567 Men jeg tog en lineær nummer trin, og nu er jeg færdig. 1043 00:36:27,567 --> 00:36:28,900 Så det er det bedste tilfældet, selv om. 1044 00:36:28,900 --> 00:36:29,983 Hvad med det værst tænkelige? 1045 00:36:29,983 --> 00:36:32,730 Hvilke otte var derovre, og syv var dernede, 1046 00:36:32,730 --> 00:36:35,840 og en og to var herovre, så at listen virkelig var omvendt? 1047 00:36:35,840 --> 00:36:38,300 >> Nå, hvad sker der faktisk hvis dette er nummeret? 1048 00:36:38,300 --> 00:36:41,300 Og vi vil gøre blot et par eksempler. 1049 00:36:41,300 --> 00:36:49,300 Hvad hvis ja, nummer otte er her, og de number-- hovsa. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Så hvad nu hvis, ja, antallet otte er hele vejen over her, 1052 00:36:56,430 --> 00:36:57,790 og jeg bruger indsættelse slags? 1053 00:36:57,790 --> 00:36:58,290 >> OK. 1054 00:36:58,290 --> 00:37:00,280 Jeg hævder i det øjeblik, det er på plads. 1055 00:37:00,280 --> 00:37:03,152 Men nu, seven-- hvor kommer syv hen? 1056 00:37:03,152 --> 00:37:04,360 Selvfølgelig er det går over her. 1057 00:37:04,360 --> 00:37:06,760 Så jeg er nødt til at flytte otte over et sted. 1058 00:37:06,760 --> 00:37:08,554 Nu seks, hvor går det gå? 1059 00:37:08,554 --> 00:37:09,220 Nå, okay. 1060 00:37:09,220 --> 00:37:13,150 Nu har jeg til at flytte otte i løbet af et sted, og syv over et sted, 1061 00:37:13,150 --> 00:37:14,440 og så jeg plask ned seks. 1062 00:37:14,440 --> 00:37:16,870 >> Så den første gang, det koste mig et skridt til at løse tingene, 1063 00:37:16,870 --> 00:37:18,570 så det kostede mig to trin til at løse tingene. 1064 00:37:18,570 --> 00:37:20,370 Hvor mange trin er det kommer til at tage for at løse 1065 00:37:20,370 --> 00:37:22,720 ting at sætte fem i det rigtige sted? 1066 00:37:22,720 --> 00:37:23,340 Tre. 1067 00:37:23,340 --> 00:37:29,520 Fordi nu er jeg nødt til at flytte en, to, tre. 1068 00:37:29,520 --> 00:37:32,430 Hvor mange trin er det kommer til at tage at sætte fire i det rigtige sted? 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 >> Og så det er matematisk identisk med hvad vi beskrevet for valg Sorter. 1071 00:37:40,260 --> 00:37:42,130 Vi har denne serie der er bare stigende. 1072 00:37:42,130 --> 00:37:45,650 1 plus 2 + 3 + 4, eller omvendt, 7 plus 6 1073 00:37:45,650 --> 00:37:52,610 plus 5 plus 4 tilføjer op til nutidens formål til på rækkefølgen af ​​n potens. 1074 00:37:52,610 --> 00:37:57,640 >> Så lad mig fastsætte også, at boble sortere er også i n potens. 1075 00:37:57,640 --> 00:38:01,340 Fordi med boble sortere, hver gang jeg går gennem listen, 1076 00:38:01,340 --> 00:38:03,100 Jeg tager nogenlunde hvor mange skridt? 1077 00:38:03,100 --> 00:38:06,260 Hver gang jeg bogstaveligt talt gå derfra til der? 1078 00:38:06,260 --> 00:38:07,960 Omkring n trin. 1079 00:38:07,960 --> 00:38:12,650 Men hvor mange gange jeg måske nødt til at gå gennem listen? 1080 00:38:12,650 --> 00:38:13,920 >> Nå, groft n tid. 1081 00:38:13,920 --> 00:38:15,680 Måske n minus 1, men groft n gange. 1082 00:38:15,680 --> 00:38:16,430 Tja, hvorfor er det? 1083 00:38:16,430 --> 00:38:19,560 Nå, med boble sortere, hvis vi starter med boble sortere, 1084 00:38:19,560 --> 00:38:23,570 med listen i den værst mulige situation, som igen er helt 1085 00:38:23,570 --> 00:38:25,550 baglæns, hvad der kommer til at ske? 1086 00:38:25,550 --> 00:38:28,830 Jeg går gennem listen, og nummer man hører hele vejen derovre. 1087 00:38:28,830 --> 00:38:33,280 >> Men med boble sortere, hvor langt gør man bevæge sig på min første passage gennem listen? 1088 00:38:33,280 --> 00:38:36,620 Hvor mange pletter får han tættere på det rigtige sted? 1089 00:38:36,620 --> 00:38:37,240 Bare en. 1090 00:38:37,240 --> 00:38:40,281 Så hvis du slags årsag gennem denne, hver gang gennem denne algoritme, 1091 00:38:40,281 --> 00:38:41,880 Davids tager ca n trin. 1092 00:38:41,880 --> 00:38:44,940 Men hvor mange gennemløb gennem listen er det 1093 00:38:44,940 --> 00:38:49,060 vil tage for en at boble til venstre hvor den hører hjemme? 1094 00:38:49,060 --> 00:38:51,840 >> Han har fået til at bevæge sig ud, n rum på denne måde. 1095 00:38:51,840 --> 00:38:57,960 Så bare for at gøre sorteringen af ​​listen, Jeg er nødt til at gå frem og tilbage n gange. 1096 00:38:57,960 --> 00:39:01,540 Og hver gang, jeg er ser på n elementer. 1097 00:39:01,540 --> 00:39:05,410 Så gør n ting n gange på rækkefølgen af ​​n potens. 1098 00:39:05,410 --> 00:39:07,220 >> Nu vil vi se på nogle af shorts, der 1099 00:39:07,220 --> 00:39:10,440 er indlejret i CS50 næste problem sæt, en anden fremgangsmåde på disse, 1100 00:39:10,440 --> 00:39:13,490 men for nu, lad os bare overveje nogle andre kører tider, 1101 00:39:13,490 --> 00:39:16,840 især hvis sortering dem tage en lille smule tid til at synke i. 1102 00:39:16,840 --> 00:39:21,790 Hvad er en algoritme, vi har set allerede der tager i størrelsesordenen n trin? 1103 00:39:21,790 --> 00:39:27,560 >> Hvad skal tage en lineær nummer af trin, vi har set indtil videre? 1104 00:39:27,560 --> 00:39:29,350 Hvad er det? 1105 00:39:29,350 --> 00:39:30,480 Telefonbogen søgning. 1106 00:39:30,480 --> 00:39:31,390 Den første algoritme. 1107 00:39:31,390 --> 00:39:31,560 Højre? 1108 00:39:31,560 --> 00:39:33,650 Hvor vi er lineært søger efter Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Faktisk. 1110 00:39:34,150 --> 00:39:37,180 Fra uge nul, da jeg startede dreje én side ad gangen, 1111 00:39:37,180 --> 00:39:40,095 og jeg selv sagde, at det var venlig af en lineær følelse algoritme, 1112 00:39:40,095 --> 00:39:42,720 og vi havde at billedet på bord med den lige røde linje 1113 00:39:42,720 --> 00:39:44,678 og lige gul linje, der faktisk var 1114 00:39:44,678 --> 00:39:46,810 algoritmer, der er i store O i n. 1115 00:39:46,810 --> 00:39:50,680 >> Fordi at finde Mike Smith i en telefon bog af n sider, i værste fald, 1116 00:39:50,680 --> 00:39:52,422 kan tage mig n trin. 1117 00:39:52,422 --> 00:39:53,630 Hvad med at tage fremmøde? 1118 00:39:53,630 --> 00:39:55,790 En to tre fire fem seks. 1119 00:39:55,790 --> 00:39:59,420 Hvad er køretid for denne algoritme til at føre protokol? 1120 00:39:59,420 --> 00:40:03,070 Big O i n, for i teorien I nødt til at pege alle i lokalet. 1121 00:40:03,070 --> 00:40:05,861 >> Nu som en sidebemærkning, hvad med andet optimering fra uge nul? 1122 00:40:05,861 --> 00:40:08,117 To, fire, seks, otte, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 En computer videnskabsmand ville indse, vent et minut, 1124 00:40:10,200 --> 00:40:12,320 der er på rækkefølgen af n divideret med to trin. 1125 00:40:12,320 --> 00:40:12,820 Højre? 1126 00:40:12,820 --> 00:40:14,444 Fordi jeg gør to personer ad gangen. 1127 00:40:14,444 --> 00:40:17,015 Men vi kommer til at ignorere disse lavere ordens led, 1128 00:40:17,015 --> 00:40:19,140 og vi bare gå til smide dividere med 2, 1129 00:40:19,140 --> 00:40:21,830 og blot sige, store O i n for denne algoritme samt. 1130 00:40:21,830 --> 00:40:22,760 >> Hvad med denne her? 1131 00:40:22,760 --> 00:40:26,170 Vi vil springe over nogle af disse, men hvad var en algoritme, der var log n? 1132 00:40:26,170 --> 00:40:29,900 Det tog omtrent log n trin? 1133 00:40:29,900 --> 00:40:30,870 Den kløft og erobre. 1134 00:40:30,870 --> 00:40:31,369 Præcis. 1135 00:40:31,369 --> 00:40:33,900 Ligesom telefonbogen eksempel i uge nul og tidligere i dag, 1136 00:40:33,900 --> 00:40:36,191 hvor vi delt problemet igen og igen og igen. 1137 00:40:36,191 --> 00:40:39,070 Vi trak det i bestyrelsen i uge nul som en buet grøn linje, 1138 00:40:39,070 --> 00:40:41,460 og vi sagde, at dag var en logaritmisk algoritme. 1139 00:40:41,460 --> 00:40:44,970 >> Og ja, antallet af skridt it tager at udføre del og hersk, 1140 00:40:44,970 --> 00:40:48,610 eller binær søgning som vi starter at kalde det, som i telefonbogen, 1141 00:40:48,610 --> 00:40:50,680 er af størrelsesordenen log og trin. 1142 00:40:50,680 --> 00:40:52,470 Og det er lidt af en underlig en. 1143 00:40:52,470 --> 00:40:54,910 >> Hvad tager et skridt, eller mere specifikt 1144 00:40:54,910 --> 00:40:56,240 et konstant antal trin? 1145 00:40:56,240 --> 00:40:58,865 Måske er det to, måske er det tre, men datalog bare 1146 00:40:58,865 --> 00:41:01,423 forenkler det så stor O på 1, nogle konstant antal trin. 1147 00:41:01,423 --> 00:41:04,256 Hvad er noget, du kunne gøre det tager et konstant antal trin? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Hvad er køretid for at klappe? 1150 00:41:10,930 --> 00:41:11,920 Konstant tid. 1151 00:41:11,920 --> 00:41:12,420 Højre? 1152 00:41:12,420 --> 00:41:15,490 Ligesom, hvad er køretiden for gøre noget, der tager kun én 1153 00:41:15,490 --> 00:41:18,570 drift, ligesom udskrive F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Det kunne siges at være konstant tid, medmindre mindre hjørne tilfældet med print F, 1155 00:41:24,110 --> 00:41:28,260 Hvad kan køretiden af print F faktisk være? 1156 00:41:28,260 --> 00:41:28,790 Og hvorfor? 1157 00:41:28,790 --> 00:41:30,550 Hvad er n måling i dette tilfælde? 1158 00:41:30,550 --> 00:41:32,251 >> PUBLIKUM: [uhørligt]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. MALAN: Præcis. 1160 00:41:33,250 --> 00:41:34,900 Antallet af tegn Vi ønsker at udskrive. 1161 00:41:34,900 --> 00:41:36,191 Så det er meget kontekstafhængig. 1162 00:41:36,191 --> 00:41:39,910 I dag har vi haft fokus meget på bogstaver og tal her på brættet. 1163 00:41:39,910 --> 00:41:43,540 Men det kan også være tegn i en faktiske strengen. 1164 00:41:43,540 --> 00:41:46,420 Så det viser sig der er en anden foranstaltning, der vil begynde at bekymre sig om, 1165 00:41:46,420 --> 00:41:48,530 og det er det modsatte af store O, så at sige. 1166 00:41:48,530 --> 00:41:50,120 >> Det er omega notation. 1167 00:41:50,120 --> 00:41:53,380 Hvorimod store O betyder, hvad der er den øvre grænse på din køretid? 1168 00:41:53,380 --> 00:41:55,580 Maksimalt, hvor meget tid måske noget tage? 1169 00:41:55,580 --> 00:41:59,250 Omega-- ked dette holder kommer up-- er det modsatte af det, 1170 00:41:59,250 --> 00:42:02,960 hvorved det er en nedre grænse på mængde tid noget kan tage. 1171 00:42:02,960 --> 00:42:10,480 >> So. for eksempel, hvad er en algoritme der tager altid n firkantede trin? 1172 00:42:10,480 --> 00:42:15,600 Tja, en af ​​de algoritmer vi har set dag, i virkeligheden kan være, at så godt. 1173 00:42:15,600 --> 00:42:16,720 Udvælgelse slags. 1174 00:42:16,720 --> 00:42:18,270 Valg Sorter er temmelig dumt. 1175 00:42:18,270 --> 00:42:21,760 Selv om algorithm-- ked, selv Hvis array allerede er sorteret, 1176 00:42:21,760 --> 00:42:24,150 valg Sorter kommer til at fortsætter med at gå gennem listen 1177 00:42:24,150 --> 00:42:28,907 for at sikre det har den mindste element igen og igen og igen. 1178 00:42:28,907 --> 00:42:31,740 Og selvom du mennesker i publikum ved, at vente et øjeblik, 1179 00:42:31,740 --> 00:42:33,948 du allerede bestået mindste element, computeren 1180 00:42:33,948 --> 00:42:37,300 ikke, at indtil det ser hele vejen gennem listen. 1181 00:42:37,300 --> 00:42:40,240 Ligeledes en nedre grænse, at kan også tages i betragtning 1182 00:42:40,240 --> 00:42:42,000 kan være lineær tid. 1183 00:42:42,000 --> 00:42:48,260 >> Hvor meget tid tager det at Sorter n elementer i den bedste 1184 00:42:48,260 --> 00:42:52,420 tilfælde ved hjælp af noget som boble slags? 1185 00:42:52,420 --> 00:42:54,280 Antag, at din liste er allerede sorteret. 1186 00:42:54,280 --> 00:42:56,696 Vi sagde boble slags tager på rækkefølgen af ​​n kvadreret trin. 1187 00:42:56,696 --> 00:42:59,640 Men hvad nu, hvis det er allerede ordnet? 1188 00:42:59,640 --> 00:43:02,310 Hvad hvis du er klar efter en passage gennem array 1189 00:43:02,310 --> 00:43:03,540 at du har lavet nogen swaps? 1190 00:43:03,540 --> 00:43:05,970 Har du brug for at holde gøre flere afleveringer? 1191 00:43:05,970 --> 00:43:06,470 >> Nej. 1192 00:43:06,470 --> 00:43:10,340 Så en nedre grænse på boble sortere kan siges at være lineær. 1193 00:43:10,340 --> 00:43:11,830 Omega af n. 1194 00:43:11,830 --> 00:43:14,450 Og vi kan se på andre af disse. 1195 00:43:14,450 --> 00:43:17,990 Så lad os tage et hurtigt kig på kun en visualisering her 1196 00:43:17,990 --> 00:43:20,790 at se, hvordan disse adskiller sig. 1197 00:43:20,790 --> 00:43:24,592 Jeg har tænkt mig at gå ned her i dette side, der er tilgængelig på C50 hjemmeside, 1198 00:43:24,592 --> 00:43:27,550 men det vil være en smerte at få arbejde, da den bruger en teknologi kaldet 1199 00:43:27,550 --> 00:43:30,560 Java applets, hvilket er en stort set ikke understøttes i disse dage, 1200 00:43:30,560 --> 00:43:32,730 i det mindste ved Chrome og visse andre. 1201 00:43:32,730 --> 00:43:37,070 >> Og lad mig gå videre og fremskynde denne op og forklare, hvad der foregår. 1202 00:43:37,070 --> 00:43:40,840 Dette er en demonstration af boble sortere, den første algoritme vi kiggede på. 1203 00:43:40,840 --> 00:43:43,950 Og det er en visualisering, at hvert af disse søjler repræsenterer en række. 1204 00:43:43,950 --> 00:43:45,710 Jo større bar, jo større nummeret. 1205 00:43:45,710 --> 00:43:47,520 Jo mindre bar, Jo mindre tallet. 1206 00:43:47,520 --> 00:43:50,353 Og hvad du kan se visuelt, selv selvom dette foregår super hurtig, 1207 00:43:50,353 --> 00:43:53,699 er, at den røde bar er ligesom mig, walking og tilbage fastsættelse problemer. 1208 00:43:53,699 --> 00:43:56,740 Du kan se, at de større elementer er faktisk gennemstrømning op til højre, 1209 00:43:56,740 --> 00:43:59,650 og de mindre elementer er gennemstrømning op til venstre. 1210 00:43:59,650 --> 00:44:01,870 Og hernede, hvis vi faktisk ser nærmere, 1211 00:44:01,870 --> 00:44:04,330 Vi kan faktisk tælle Antallet af sammenligninger og swaps 1212 00:44:04,330 --> 00:44:05,350 der blev foretaget. 1213 00:44:05,350 --> 00:44:07,360 >> Men i stedet, lad os se ved den anden algoritme 1214 00:44:07,360 --> 00:44:11,240 vi kiggede på tidligere med vores frivillige, udvælgelse slags. 1215 00:44:11,240 --> 00:44:13,500 Visuelt, det har en meget anderledes effekt. 1216 00:44:13,500 --> 00:44:16,820 Men det er, igen, meget intuitiv, i at vi holder vælge den næstmindste 1217 00:44:16,820 --> 00:44:18,660 element, og vi fik lidt heldig. 1218 00:44:18,660 --> 00:44:20,110 Der følte fundamentalt hurtigere. 1219 00:44:20,110 --> 00:44:22,840 Men hvis vi kørte dette igen og igen og igen med masser af input, 1220 00:44:22,840 --> 00:44:26,680 ville vi se, at det er faktisk stadig i store O n potens. 1221 00:44:26,680 --> 00:44:29,920 >> Lad os gøre et sidste her, indsættelse sortere, 1222 00:44:29,920 --> 00:44:33,180 som var den tredje algoritme vi kiggede på, og tilbagekaldelse 1223 00:44:33,180 --> 00:44:36,700 at denne ene handler om elementer, som det møder dem, 1224 00:44:36,700 --> 00:44:39,290 men så er det måske skift over tingene for at gøre plads, 1225 00:44:39,290 --> 00:44:41,660 indsætte elementer, hvor de hører til. 1226 00:44:41,660 --> 00:44:45,330 >> Og dette også ender med at give endelige resultat. Nu er alle tre af dem 1227 00:44:45,330 --> 00:44:46,490 følte temmelig hurtigt. 1228 00:44:46,490 --> 00:44:48,740 Og ja, jeg kørte dem på en temmelig god klip. 1229 00:44:48,740 --> 00:44:52,510 Men fundamentalt, de er alle temmelig forfærdeligt, at være ærlig. 1230 00:44:52,510 --> 00:44:56,960 Alle disse algoritmer hidtil at løb store O i n kvadreret 1231 00:44:56,960 --> 00:44:59,270 tage en hel del af tid til at køre i sidste ende. 1232 00:44:59,270 --> 00:45:01,920 >> Og ja, kan vi se og føler det endelig 1233 00:45:01,920 --> 00:45:04,090 hvis jeg trækker op denne tredje og sidste demo. 1234 00:45:04,090 --> 00:45:05,840 Dette er en anden visualisering, der kommer 1235 00:45:05,840 --> 00:45:08,500 at vise boble sortere til venstre, valg Sorter i midten, 1236 00:45:08,500 --> 00:45:13,410 og noget, som en af ​​vores hånd hæver tidligere foreslået, 1237 00:45:13,410 --> 00:45:15,020 mergesort til højre. 1238 00:45:15,020 --> 00:45:16,937 En kløft og erobre strategi til højre. 1239 00:45:16,937 --> 00:45:19,520 Og det er i virkeligheden, hvad vi er kommer til at se på onsdag. 1240 00:45:19,520 --> 00:45:21,990 Men lad os tid disse til at løbe parallelt. 1241 00:45:21,990 --> 00:45:26,765 Det er nogenlunde det samme antal elementer, der alle kører på samme tid. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble sortere vs udvælgelse sortere vs mergesort. 1244 00:45:34,440 --> 00:45:36,760 >> Nu, de er alle kører i teorien samtidig. 1245 00:45:36,760 --> 00:45:39,830 CPU'en kører på samme hastighed, men du 1246 00:45:39,830 --> 00:45:44,014 kan føle hvor kedeligt det er meget hurtigt ved at blive, 1247 00:45:44,014 --> 00:45:45,930 og hvor hurtigt, når Vi indsprøjte en smule uge 1248 00:45:45,930 --> 00:45:49,330 nul algoritmer kan vi fremskynde tingene op. 1249 00:45:49,330 --> 00:45:51,760 >> Og lad os nu sammenligne disse i en sidste form. 1250 00:45:51,760 --> 00:45:55,710 Jeg har tænkt mig at gå videre til CS50 hjemmeside, hvor 1251 00:45:55,710 --> 00:45:59,020 vi har denne sidste led for i dag, hvor en person på internettet 1252 00:45:59,020 --> 00:46:03,960 venligt sammensætte en video, indfanger hvad forskellige sortering 1253 00:46:03,960 --> 00:46:07,510 algoritmer lyder. 1254 00:46:07,510 --> 00:46:09,577 Dette er insertion slags. 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 >> Hvorved du anvender en frekvens baseret på højden af ​​bar bar. 1258 00:46:16,850 --> 00:46:19,826 Dette er boble slags. 1259 00:46:19,826 --> 00:46:21,822 >> [Skæv bip] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Kommer op næste is-- kommer op næste is-- udvælgelse sortere, 1262 00:46:45,774 --> 00:46:48,820 hvor igen, vi vælge den næstmindste element, 1263 00:46:48,820 --> 00:46:51,820 og vi kan se det voksende fra venstre mod højre. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Mergesort, vores vinder hidtil dag. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Læg mærke til, hvordan det er at opdele tingene ind [uhørligt] halvdelen og kvartaler. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome slags, som vi ikke har talte om, og skaber visuelt 1270 00:47:21,660 --> 00:47:24,450 og audally lidt af en forskellig form og lyd. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Går frem og tilbage, rengøring tingene op. 1273 00:47:30,160 --> 00:47:32,230 Du kan også læse heapsort på denne fyr hjemmeside. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Og det er det. 1276 00:47:36,810 --> 00:47:38,210 Vi vil se dig næste gang. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Susen OG MUSIK] 1279 00:47:48,334 --> 00:50:24,839