1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> SPEAKER: Greit, dette er CS50. 3 00:00:14,910 --> 00:00:19,020 Dette er slutten av uke tre, og hvis du ikke har utnyttet allerede, 4 00:00:19,020 --> 00:00:21,790 vet at det vil være lunsj denne fredagen som vanlig, der 5 00:00:21,790 --> 00:00:25,430 du kan nyte god samtale og mat på Fire and Ice 6 00:00:25,430 --> 00:00:27,980 med noen av CS50 sin ansatte og klassekamerater. 7 00:00:27,980 --> 00:00:30,170 Hodet til denne nettadressen her. 8 00:00:30,170 --> 00:00:33,420 >> Nå kan du husker, eller du kan snart bli kjent med, 9 00:00:33,420 --> 00:00:35,970 disse tingene her, som gis ut på slutten 10 00:00:35,970 --> 00:00:37,850 av semesteret i mange klasser. 11 00:00:37,850 --> 00:00:40,870 Såkalt eksamen blå bøker, der du skriver svarene dine til eksamen. 12 00:00:40,870 --> 00:00:44,240 Nå har jeg her 26 slike blå bøker, på hver av dem 13 00:00:44,240 --> 00:00:47,580 er skrevet et navn, A til Z. Og faktisk navnene er så enkelt, A 14 00:00:47,580 --> 00:00:50,490 gjennom Z. Og en av målene for hånden i dag 15 00:00:50,490 --> 00:00:53,910 kommer til å være å fortsette det vi startet på mandag, som ikke er 16 00:00:53,910 --> 00:00:57,830 så mye å se på koden, men egentlig ser på ideer og problemløsning. 17 00:00:57,830 --> 00:01:00,170 Ett av målene og løfter om dette kurset 18 00:01:00,170 --> 00:01:02,985 er å lære deg å tenke mer nøye, mer metodisk, 19 00:01:02,985 --> 00:01:05,400 og å løse problemer mer effektivt. 20 00:01:05,400 --> 00:01:09,526 Og ja, vi kan gjøre som virkelig uten engang å berøre en linje med kode. 21 00:01:09,526 --> 00:01:12,150 Så jeg har et par elefanter opp her i dag, oransje og blått, 22 00:01:12,150 --> 00:01:15,780 hvis vi kunne få en frivillig, kanskje fra lenger tilbake enn vanlig. 23 00:01:15,780 --> 00:01:18,070 Hva med akkurat der, komme ned. 24 00:01:18,070 --> 00:01:24,180 Målet med som kommer til å være til hjelpe pluss administrere denne eksamen her. 25 00:01:24,180 --> 00:01:24,935 Hva heter du? 26 00:01:24,935 --> 00:01:25,768 >> PUBLIKUM: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 SPEAKER: Mary Beth, kom opp. 28 00:01:27,560 --> 00:01:29,560 La meg få mikrofonen her for deg. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Hyggelig å møte deg. 31 00:01:32,880 --> 00:01:34,005 >> PUBLIKUM: Hyggelig å møte deg. 32 00:01:34,005 --> 00:01:36,790 SPEAKER: Ok, så jeg har her blå bøker A til Z, 33 00:01:36,790 --> 00:01:41,680 og jeg kommer til å late som Jeg har en av studentene, 34 00:01:41,680 --> 00:01:45,770 og de kommer i litt tilfeldig ved slutten av en tre timers undersøkelse blokk, 35 00:01:45,770 --> 00:01:49,400 slik at de ender opp i noen semi-tilfeldig rekkefølge som dette. 36 00:01:49,400 --> 00:01:54,510 Nå din jobb i bare et øyeblikk kommer å be-- dette er faktisk hvordan de får 37 00:01:54,510 --> 00:01:56,820 leverte i slutten av klassen, mest sannsynlig. 38 00:01:56,820 --> 00:02:01,120 Din jobb nå kommer til å være, ganske rett og slett, å sortere disse blå bøker for oss 39 00:02:01,120 --> 00:02:05,220 fra A til Z. 40 00:02:05,220 --> 00:02:08,400 >> PUBLIKUM: Å, dette er kommer til å ta en evighet. 41 00:02:08,400 --> 00:02:13,747 >> SPEAKER: Og vi vil se som du gjør dette, ikke noe press. 42 00:02:13,747 --> 00:02:15,330 PUBLIKUM: Nei, ikke noe press eller noe. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> SPEAKER: Og for moro skyld la oss sette opp en timer. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> PUBLIKUM: Så gøy, så gøy. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> SPEAKER: Jeg kan holde mikrofonen for deg. 49 00:02:38,574 --> 00:02:40,240 Greit, vi har bare doblet vår hastighet. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Så i mellomtiden, la meg stille hva som er kommer til å være spørsmålet for Mary Beth 52 00:02:49,060 --> 00:02:51,540 er hva hun gjør, hvordan er hun går om å løse dette? 53 00:02:51,540 --> 00:02:54,040 Og faktisk, har du kanskje ikke noen gang tenkt på noe 54 00:02:54,040 --> 00:02:57,440 så enkelt som når du plukker opp 26 bøker som dette, 55 00:02:57,440 --> 00:02:59,350 som har en naturlig bestilling til dem. 56 00:02:59,350 --> 00:03:01,335 Hva er prosessen at du faktisk bruker? 57 00:03:01,335 --> 00:03:03,770 Er det ganske tilfeldig bare plukke den første du ser 58 00:03:03,770 --> 00:03:05,250 og setter det på sin plass? 59 00:03:05,250 --> 00:03:09,680 Har du først flytte hendene rundt På utkikk etter en så leter etter B? 60 00:03:09,680 --> 00:03:11,722 Vil du ta en titt på en par av dem ved siden av hverandre 61 00:03:11,722 --> 00:03:14,680 og bare si, vent litt, dette er ikke riktig, og deretter bytte den rekkefølgen? 62 00:03:14,680 --> 00:03:16,960 Vi så allerede på mandag at det er en rekke måter 63 00:03:16,960 --> 00:03:22,140 der vi kan gjøre dette, og faktisk som vi nærmer oss slutten her, 64 00:03:22,140 --> 00:03:26,360 Jeg ville ta notat kanskje av hva Mary Beth gjør. 65 00:03:26,360 --> 00:03:30,040 Vi har noen få hauger det virker, en større en, tre små. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> PUBLIKUM: Jeg beordrer dem når jeg finner to bokstaver 68 00:03:36,415 --> 00:03:39,540 at jeg vet er sammen i en sekvens, Jeg satte dem sammen slik at jeg ikke 69 00:03:39,540 --> 00:03:42,915 trenger å bekymre deg for å holde styr på en hel rad med bøker. 70 00:03:42,915 --> 00:03:45,706 Det er bare, oh, A er først, Jeg har fått denne bunken her. 71 00:03:45,706 --> 00:03:47,580 SPEAKER: Så, nesten som Et puslespill brikker som 72 00:03:47,580 --> 00:03:49,860 har rett form til matche opp med hverandre. 73 00:03:49,860 --> 00:03:51,026 PUBLIKUM: Ganske mye, ja. 74 00:03:51,026 --> 00:03:55,320 SPEAKER: OK, utmerket. 75 00:03:55,320 --> 00:03:59,850 Og nå hver av disse hauger er antagelig sortert? 76 00:03:59,850 --> 00:04:00,990 >> PUBLIKUM: Yeah. 77 00:04:00,990 --> 00:04:09,900 >> SPEAKER: Greit, A til Z. Alle høyre, gratulerer, du gjorde det. 78 00:04:09,900 --> 00:04:11,461 Du har ditt valg. 79 00:04:11,461 --> 00:04:11,960 Blue? 80 00:04:11,960 --> 00:04:13,530 Ok, takk for det. 81 00:04:13,530 --> 00:04:16,679 Så Mary Beth gjorde foreslå hva hennes tilnærming var, 82 00:04:16,679 --> 00:04:19,720 men hva er en annen tilnærming hvordan du kan gå om sortering disse tingene? 83 00:04:19,720 --> 00:04:21,130 Hva ville du ha gjort? 84 00:04:21,130 --> 00:04:24,060 Rekorden å slå ville ha vært ett minutt og 50 eller så sekunder, 85 00:04:24,060 --> 00:04:26,039 pluss de jeg glemte å telle. 86 00:04:26,039 --> 00:04:27,080 Hva ville du ha gjort? 87 00:04:27,080 --> 00:04:27,579 Yeah? 88 00:04:27,579 --> 00:04:28,735 PUBLIKUM: Ta bunken. 89 00:04:28,735 --> 00:04:29,776 Starte fra begynnelsen. 90 00:04:29,776 --> 00:04:32,284 Sjekk dine papirer. 91 00:04:32,284 --> 00:04:36,586 Og hvis det over er høyere enn, kanskje, er de, 92 00:04:36,586 --> 00:04:38,980 den nederste er høyere, deretter bytte dem. 93 00:04:38,980 --> 00:04:41,300 >> SPEAKER: OK, så starter øverst og nederst, 94 00:04:41,300 --> 00:04:43,716 og deretter jobbe din vei innover sånn, bytte dem? 95 00:04:43,716 --> 00:04:46,580 OK, så litt lignende i ånden til boble sortere, 96 00:04:46,580 --> 00:04:49,160 men velger ytterpunktene ikke de tilstøtende par. 97 00:04:49,160 --> 00:04:52,080 Men den korte av det, er at det finnes sikkert en haug med forskjellige måter 98 00:04:52,080 --> 00:04:54,210 vi kunne gjøre dette, og ærlig, jeg tror du slags 99 00:04:54,210 --> 00:04:55,700 vedtatt et par tilnærminger, ikke sant? 100 00:04:55,700 --> 00:05:00,567 Du gjorde liksom fire sorterte hauger, og så effektivt fusjonerte dem sammen. 101 00:05:00,567 --> 00:05:02,650 Og det er, påstår at en annen Teknikken helt. 102 00:05:02,650 --> 00:05:06,950 Du har ikke behandle det som en stor haug, du delt problemet inn i fire firehjulinger, 103 00:05:06,950 --> 00:05:09,820 om du vil, og deretter en eller annen måte fusjonerte dem til slutt. 104 00:05:09,820 --> 00:05:13,410 >> Så la oss vurdere, til slutt, hvordan annet vi kan gjøre dette. 105 00:05:13,410 --> 00:05:15,860 Vi formalisert begrepet boble slags siste gang, 106 00:05:15,860 --> 00:05:18,780 og boble slags tilbakekalling var en algoritme som vi visualisert 107 00:05:18,780 --> 00:05:22,640 med åtte av dine klassekamerater her oppe, tilsynelatende tilfeldig sortert først. 108 00:05:22,640 --> 00:05:26,110 Og vi deretter besluttet parvise, hvis to elementer er ute av drift, 109 00:05:26,110 --> 00:05:26,950 rett og slett bytte dem. 110 00:05:26,950 --> 00:05:28,930 Så fire og to er åpenbart ute av drift, 111 00:05:28,930 --> 00:05:31,080 så de to klassekamerater bytte posisjon. 112 00:05:31,080 --> 00:05:35,390 Og da har vi gjentatt med fire og seks, deretter seks og åtte, på hver iterasjon, 113 00:05:35,390 --> 00:05:36,980 beveger seg mot høyre. 114 00:05:36,980 --> 00:05:42,590 >> Så gitt åtte personer, hvor mange parvise sammenligninger gjorde jeg mens jeg gikk fra 115 00:05:42,590 --> 00:05:45,220 venstre til høyre i en iterasjon, for eksempel? 116 00:05:45,220 --> 00:05:48,410 Hvor mange sammenligninger? 117 00:05:48,410 --> 00:05:49,197 Seven, ikke sant? 118 00:05:49,197 --> 00:05:51,405 For hvis det er åtte folk, men du har paret 119 00:05:51,405 --> 00:05:53,880 dem, og du beveger deg ett hopp til høyre, 120 00:05:53,880 --> 00:05:56,060 du kommer ikke til å ha åtte sammenligninger, fordi du kan ikke sammenligne 121 00:05:56,060 --> 00:05:59,226 et element mot seg selv, eller det ville bare være meningsløst, så du har sju. 122 00:05:59,226 --> 00:06:01,290 Eller mer generelt, hvis vi har n mennesker, vi 123 00:06:01,290 --> 00:06:04,300 gjøre n minus 1 sammenligninger med boble slag. 124 00:06:04,300 --> 00:06:08,150 >> Så la oss vurdere nå hvor godt eller dårlig boble slags egentlig var, og prøv 125 00:06:08,150 --> 00:06:13,570 å gi oss selv vokabular med som til kritikk algoritmer som dette, 126 00:06:13,570 --> 00:06:14,430 og snart vår egen. 127 00:06:14,430 --> 00:06:16,970 Så den første går gjennom bobletype, første gang 128 00:06:16,970 --> 00:06:20,909 Jeg gikk fra venstre til høyre over scenen, tok meg n minus 1 sammenligninger. 129 00:06:20,909 --> 00:06:22,950 Og det kommer til å bli min måleenhet, ikke sant? 130 00:06:22,950 --> 00:06:26,170 Jeg var litt snakk og rusler, noe fort, noe treg, 131 00:06:26,170 --> 00:06:29,300 så teller min antall sekunder er ikke spesielt å fortelle, 132 00:06:29,300 --> 00:06:32,260 men telle antallet operasjoner som jeg gjorde på mandag, 133 00:06:32,260 --> 00:06:35,900 sammenligne to personer, mener at som en fin måleenhet. 134 00:06:35,900 --> 00:06:40,980 >> Så n minus 1 trinn første gang men så hva som skjedde etter det? 135 00:06:40,980 --> 00:06:46,610 Hva er en oppside på ett pass gjennom en ellers usortert liste? 136 00:06:46,610 --> 00:06:49,840 Hva kan du fortelle meg om elementet som var helt der borte? 137 00:06:49,840 --> 00:06:51,300 Yeah? 138 00:06:51,300 --> 00:06:52,870 Det var den største element, ikke sant? 139 00:06:52,870 --> 00:06:55,710 Nummer åtte, selv om hun startet her, hver gang jeg 140 00:06:55,710 --> 00:06:57,860 sammenlignet henne mot en nabo, holdt hun 141 00:06:57,860 --> 00:07:00,480 bobler opp til høyre side av listen. 142 00:07:00,480 --> 00:07:02,710 Og ja, det er der algoritmen har fått navnet sitt. 143 00:07:02,710 --> 00:07:07,630 >> Nå følger den logikken, hvor mange sammenligninger trenger jeg gjør på andre gang 144 00:07:07,630 --> 00:07:09,800 Jeg gjør at pasning fra venstre til høyre? 145 00:07:09,800 --> 00:07:10,730 n minus 2, ikke sant? 146 00:07:10,730 --> 00:07:14,297 Det ville bare være å kaste bort tiden min hvis jeg holde sammenligne åtte mot noen 147 00:07:14,297 --> 00:07:16,630 annet fordi vi allerede vet hun var på rett sted. 148 00:07:16,630 --> 00:07:19,760 Så det er litt av en optimalisering, slik at den neste ballen 149 00:07:19,760 --> 00:07:23,899 kommer til å være pluss n minus to trinn, der n er antall personer. 150 00:07:23,899 --> 00:07:26,940 Nå kan du slags ekstrapolere, selv hvis du ikke er en datamaskin vitenskapsmann, 151 00:07:26,940 --> 00:07:27,680 hvordan dette ender. 152 00:07:27,680 --> 00:07:31,259 Ved slutten av denne algoritmen, formodentlig du har bare én sammenligning venstre. 153 00:07:31,259 --> 00:07:33,800 Du må slags fikse begynnelsen av listen i tilfelle to 154 00:07:33,800 --> 00:07:36,540 og en er ute av rekkefølge og bør være en og to, 155 00:07:36,540 --> 00:07:40,330 så dette bunner ut på pluss en endelig sammenligning. 156 00:07:40,330 --> 00:07:44,500 >> Nå prikk, prikk, prikk slags bølger det er hendene på noen av de saftigere detaljer, 157 00:07:44,500 --> 00:07:46,452 men la oss bare gå videre og forenkle. 158 00:07:46,452 --> 00:07:48,660 Hvis du husker fra videregående skole, ærlig, mange av dere 159 00:07:48,660 --> 00:07:50,340 hadde mattebøker som hadde en liten jukselapp 160 00:07:50,340 --> 00:07:52,550 på frontdekselet eller bakdekselet som viste deg 161 00:07:52,550 --> 00:07:56,400 hva serien summeringer som dette til slutt lagt opp til. 162 00:07:56,400 --> 00:07:59,600 I det generelle tilfellet, hvis du har en variabel som n, og faktisk denne, 163 00:07:59,600 --> 00:08:01,634 hvis du så på din old school matte bok, 164 00:08:01,634 --> 00:08:04,050 du vil se at dette faktisk legger opp til denne sum her, 165 00:08:04,050 --> 00:08:07,970 n ganger n minus 1 alt delt på 2. 166 00:08:07,970 --> 00:08:11,172 Så for nå la meg bare fastsette dette er sant, så på en porsjon tro, 167 00:08:11,172 --> 00:08:12,880 det er hva dette oppsummerer opp til, og vi kunne 168 00:08:12,880 --> 00:08:14,341 vise seg at det i et mer generelt tilfelle. 169 00:08:14,341 --> 00:08:15,590 Men la oss nå utvide dette ut. 170 00:08:15,590 --> 00:08:19,920 Så la oss formere ut dette, så det er n kvadrert, minus n, alt dividert med to. 171 00:08:19,920 --> 00:08:23,200 Det er virkelig n squared, delt på to, minus n over 2, 172 00:08:23,200 --> 00:08:25,010 så det er alt fint og interessant. 173 00:08:25,010 --> 00:08:27,060 Men hva skjer hvis vi nå plug-in en verdi? 174 00:08:27,060 --> 00:08:29,724 Anta at jeg ikke har åtte mennesker, men si en million. 175 00:08:29,724 --> 00:08:31,890 Og en million bare fordi det er en ganske stort tall, 176 00:08:31,890 --> 00:08:34,039 La oss plugge det i og se hva som skjer. 177 00:08:34,039 --> 00:08:39,039 Så hvis jeg kobler en million inn i den formelen Jeg kommer til å få en million kvadrat, 178 00:08:39,039 --> 00:08:42,868 dividert med 2, minus millioner, delt på to. 179 00:08:42,868 --> 00:08:44,159 Nå hva som kommer til å like? 180 00:08:44,159 --> 00:08:47,354 Så 500 milliarder dollar, minus 500.000. 181 00:08:47,354 --> 00:08:49,270 Og hvis jeg faktisk gjør at regnestykket ut, det betyr 182 00:08:49,270 --> 00:08:53,920 at sortering en million mennesker med boblen slags 183 00:08:53,920 --> 00:09:01,800 kan ta meg 499999500000 trinn eller sammenligninger i slutten, 184 00:09:01,800 --> 00:09:02,900 vi bare ekstrapolere. 185 00:09:02,900 --> 00:09:06,860 >> Det føles ganske treg, men ærlig måler en bestemt inngang 186 00:09:06,860 --> 00:09:09,160 som dette, er ikke alle som fortelle. 187 00:09:09,160 --> 00:09:14,050 Men faktisk er det ikke tyder på at så n blir større og større, denne algoritmen 188 00:09:14,050 --> 00:09:16,280 slags føles verre og verre, eller du virkelig 189 00:09:16,280 --> 00:09:20,450 begynner å føle smerten ved det eksponenter, som n squared, 190 00:09:20,450 --> 00:09:21,770 som legger opp ganske fort. 191 00:09:21,770 --> 00:09:25,340 Og denne detaljen er ikke tapt på folk, faktisk 192 00:09:25,340 --> 00:09:29,640 for noen år siden en viss senator som var valgkamp, ​​satte seg ned for et intervju 193 00:09:29,640 --> 00:09:32,180 med Googles Eric Schmidt, administrerende direktør på den tiden, 194 00:09:32,180 --> 00:09:36,380 og ble utfordret med et spørsmål mye som vi utforsker i dag. 195 00:09:36,380 --> 00:09:38,468 La oss ta en titt. 196 00:09:38,468 --> 00:09:45,280 >> [VIDEOAVSPILLING] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Du er her på Google, og jeg liker 198 00:09:48,560 --> 00:09:53,382 å tenke på formannskapet som et jobbintervju. 199 00:09:53,382 --> 00:09:56,434 Nå er det vanskelig å få en jobb som president, 200 00:09:56,434 --> 00:09:58,100 og du går gjennom påkjenningene nå. 201 00:09:58,100 --> 00:10:01,860 Det er også vanskelig å få en jobb på Google. 202 00:10:01,860 --> 00:10:05,490 Vi har spørsmål, og vi ber våre kandidater spørsmål, 203 00:10:05,490 --> 00:10:09,770 og dette er fra Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 Hva-- dere tror jeg er tuller, det er rett her. 205 00:10:14,760 --> 00:10:17,930 Hva er den mest effektive måten å sortere en million 32-bits heltall? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> Jeg beklager, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Nei, nei, nei. 210 00:10:27,400 --> 00:10:30,700 Jeg tror boblen slags ville være feil vei å gå. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> Kom igjen, som fortalte ham dette? 213 00:10:38,180 --> 00:10:40,590 Jeg fikk ikke se datamaskinen vitenskap i din bakgrunn. 214 00:10:40,590 --> 00:10:42,130 >> Vi hare fikk våre spioner i det. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, La oss be en annen intervju spørsmål. 217 00:10:48,444 --> 00:10:49,300 >> [END VIDEOAVSPILLING] 218 00:10:49,300 --> 00:10:52,290 >> SPEAKER: Så snakker om spesifikke tall skjønt, 219 00:10:52,290 --> 00:10:53,890 ikke kommer til å være alt som er nyttig. 220 00:10:53,890 --> 00:10:56,810 Det er ikke et liv leksjon som boble sortere, gitt en million innganger, 221 00:10:56,810 --> 00:10:58,590 kan ta så mange som 500 milliarder dollar trinn. 222 00:10:58,590 --> 00:11:01,120 Du kan virkelig ikke general for effektivt fra at 223 00:11:01,120 --> 00:11:03,560 og lage gode design beslutninger når du skriver programmer. 224 00:11:03,560 --> 00:11:07,070 Så la oss fokusere selv på hvordan vi kan forenkle dette resultatet. 225 00:11:07,070 --> 00:11:11,780 >> Så jeg har uthevet i gult her produktet av n squared dividert med 2, 226 00:11:11,780 --> 00:11:14,330 så en million squared dividert med 2, og deretter 227 00:11:14,330 --> 00:11:16,710 Jeg har fremhevet det det ultimate svaret var 228 00:11:16,710 --> 00:11:20,180 når vi trekkes av n delt på to. 229 00:11:20,180 --> 00:11:24,850 Og påstanden jeg kommer til å gjøre nå er, hvem pokker bryr seg om du trekker ut 230 00:11:24,850 --> 00:11:30,060 litt gamle N over 2 når den første en del av denne formelen er så mye større? 231 00:11:30,060 --> 00:11:33,910 Det dominerer den andre sikt, n rutet delt på to 232 00:11:33,910 --> 00:11:37,510 er så mye større, tydelig, som N blir stor som en million, 233 00:11:37,510 --> 00:11:41,450 som er det virkelig en stor forskjell på slutten av dagen mellom 500000000000 234 00:11:41,450 --> 00:11:45,730 og 499 999 500 000? 235 00:11:45,730 --> 00:11:46,349 Ikke egentlig. 236 00:11:46,349 --> 00:11:48,640 Og så hva vi skal gjøre som dataforskere er 237 00:11:48,640 --> 00:11:53,270 ignorere de lavere ordens ledd og ta noe sånt som dette, og virkelig 238 00:11:53,270 --> 00:11:56,050 bare forenkle den til begrep som kommer til å spille noen rolle. 239 00:11:56,050 --> 00:12:00,315 De større våre datasett blir, jo større våre databaser får, jo flere nettsider 240 00:12:00,315 --> 00:12:02,690 vi må søke, jo mer venner du har på Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Som n blir større, vi er virkelig kommer til å bry seg om den største 242 00:12:07,340 --> 00:12:11,560 begrep i en slik analyse av våre prestasjoner algoritmer. 243 00:12:11,560 --> 00:12:16,230 Og jeg kommer til å si, vet du hva, boble slags er i størrelsesorden big O, 244 00:12:16,230 --> 00:12:18,060 av størrelsesorden n kvadrat. 245 00:12:18,060 --> 00:12:20,090 Det er ikke akkurat n squared som vi har sett, 246 00:12:20,090 --> 00:12:22,060 men som virkelig bryr seg om de mindre vilkår, 247 00:12:22,060 --> 00:12:24,390 og ærlig, som virkelig bryr seg hvis vi deler med 2? 248 00:12:24,390 --> 00:12:25,870 Det er bare en konstant faktor. 249 00:12:25,870 --> 00:12:29,480 Og er 500 milliarder dollar versus 250 milliarder virkelig så stor av en avtale? 250 00:12:29,480 --> 00:12:32,190 Jeg kunne bare vente ett år, la min laptop bokstavelig 251 00:12:32,190 --> 00:12:34,810 få dobbelt så raskt i maskinvare, og den slags forskjell 252 00:12:34,810 --> 00:12:36,650 bare forsvinner naturlig over tid. 253 00:12:36,650 --> 00:12:39,300 >> Hva vi bryr oss om er uttrykket, delen 254 00:12:39,300 --> 00:12:42,489 av uttrykket som kommer til å variere som våre innspill blir større og større. 255 00:12:42,489 --> 00:12:45,280 Og ja, i den virkelige verden, det er hva som skjer i økende grad 256 00:12:45,280 --> 00:12:48,330 er inngangene på våre problemer og algoritmer blir større. 257 00:12:48,330 --> 00:12:53,470 Så stor O kommer til å være notasjonen, asymptotisk notasjon, at vi bare 258 00:12:53,470 --> 00:12:57,160 bruke som dataforskere å beskrive ytelsen, eller løpende tid, 259 00:12:57,160 --> 00:12:58,130 av en algoritme. 260 00:12:58,130 --> 00:13:00,800 Slik at vi kan sammenligne algoritmer på forskjellige datamaskiner skrevet 261 00:13:00,800 --> 00:13:04,170 av forskjellige mennesker, ved å bruke noen fundamentalt lik metriske 262 00:13:04,170 --> 00:13:07,557 som antall sammenligninger du er gjør, eller kanskje antall bytteavtaler 263 00:13:07,557 --> 00:13:08,140 du gjør. 264 00:13:08,140 --> 00:13:11,910 >> Hva vi kommer ikke til å teller er tiden 265 00:13:11,910 --> 00:13:13,981 som passerer på klokken på veggen vanligvis. 266 00:13:13,981 --> 00:13:16,230 Hva vi kommer ikke til å bekymre om er hvor mye minne 267 00:13:16,230 --> 00:13:17,820 du bruker i dag på minst, selv om det er 268 00:13:17,820 --> 00:13:19,370 annen ressurs vi kan måle. 269 00:13:19,370 --> 00:13:23,610 Vi kommer til å prøve å basere våre analyser på akkurat de grunnleggende operasjoner, de, 270 00:13:23,610 --> 00:13:25,930 ærlig, som du kan se mest visuelt. 271 00:13:25,930 --> 00:13:30,700 Så med noe sånt som stor O av n squared, jeg hevder at O ​​av n squared 272 00:13:30,700 --> 00:13:35,820 er en øvre grense for den såkalte kjøretiden boble slag. 273 00:13:35,820 --> 00:13:38,820 Med andre ord, hvis du ønsket å hevde at det er 274 00:13:38,820 --> 00:13:41,370 denne øvre grense for hvor mange trinn en algoritme kan ta, 275 00:13:41,370 --> 00:13:46,240 det kommer til å være i stor O av n kvadrert i dette tilfelle en øvre grense. 276 00:13:46,240 --> 00:13:49,710 >> Hva om jeg i stedet endre historie å være ikke om boble sortere, 277 00:13:49,710 --> 00:13:50,910 men om dette øvre grense. 278 00:13:50,910 --> 00:13:54,030 Kan du tenke deg en algoritme at vi har sett på allerede 279 00:13:54,030 --> 00:13:59,530 som øvre grense, maksimal måle tid eller operasjoner, 280 00:13:59,530 --> 00:14:04,300 skulle kunne sies å være avgrenset med n, en lineær funksjon, 281 00:14:04,300 --> 00:14:07,260 ikke en kvadratisk en som er buet? 282 00:14:07,260 --> 00:14:10,780 Hva er en algoritme som alltid tar ikke mer 283 00:14:10,780 --> 00:14:12,860 enn som n trinn, eller 2n skritt, eller 3n trinn? 284 00:14:12,860 --> 00:14:13,360 Yeah? 285 00:14:13,360 --> 00:14:15,030 >> PUBLIKUM: Finne største antallet i en liste? 286 00:14:15,030 --> 00:14:16,930 >> SPEAKER: Perfect, finne det største antallet i en liste. 287 00:14:16,930 --> 00:14:18,940 Hvis jeg får en liste over mennesker for eksempel, 288 00:14:18,940 --> 00:14:21,440 hver av hvem som holder et nummer, hva som er det maksimale antallet 289 00:14:21,440 --> 00:14:23,770 trinn det skal ta meg, en rimelig smart person, 290 00:14:23,770 --> 00:14:27,530 å finne den største personen i denne listen? 291 00:14:27,530 --> 00:14:28,100 n, ikke sant? 292 00:14:28,100 --> 00:14:31,320 Fordi i verste fall, hvor kanskje den største verdien være? 293 00:14:31,320 --> 00:14:32,700 Høyre, helt på slutten. 294 00:14:32,700 --> 00:14:34,575 Så i verste fall øvre grense, kan jeg 295 00:14:34,575 --> 00:14:36,450 nødt til å gå hele veien over her og være like, 296 00:14:36,450 --> 00:14:39,170 oh, her er nummer åtte, eller hva denne verdien er. 297 00:14:39,170 --> 00:14:41,330 Nå ville det bare være dum hvis jeg fortsatte å gå, ikke sant? 298 00:14:41,330 --> 00:14:43,840 Leter du etter flere og flere elementer hvis den siste av dem er der borte? 299 00:14:43,840 --> 00:14:45,340 Så sikkert, er n en øvre grense. 300 00:14:45,340 --> 00:14:47,420 Jeg trenger ikke å ta flere trinn enn det. 301 00:14:47,420 --> 00:14:51,580 >> Så hva om stedet jeg foreslått at det er algoritmer i denne verden som 302 00:14:51,580 --> 00:14:57,750 har en driftstid som er avgrenset av store O av log n, log n? 303 00:14:57,750 --> 00:15:00,390 Hvor har vi sett dette før? 304 00:15:00,390 --> 00:15:00,890 Yeah? 305 00:15:00,890 --> 00:15:03,309 >> PUBLIKUM: I telefonboken problemet? 306 00:15:03,309 --> 00:15:04,850 SPEAKER: Som telefonboken problem. 307 00:15:04,850 --> 00:15:07,754 Det var et mål på hvordan mye tid eller hvor mange tårer det 308 00:15:07,754 --> 00:15:10,170 Tok meg å finne noen som Mike Smith i telefonboken? 309 00:15:10,170 --> 00:15:13,212 Vi hevdet at det var log n og selv om ukjente eller det det er 310 00:15:13,212 --> 00:15:15,170 litt disig hva en logaritmen eller eksponent var, 311 00:15:15,170 --> 00:15:17,650 bare husk at log n generelt refererer til prosessen, 312 00:15:17,650 --> 00:15:20,790 i dette tilfellet, for å dele noe i to igjen, og igjen, 313 00:15:20,790 --> 00:15:25,790 og igjen og igjen, slik at den blir stadig mindre som du gjør det. 314 00:15:25,790 --> 00:15:28,470 >> Så logge av n refererer, sikker, til telefonboken eksempel 315 00:15:28,470 --> 00:15:32,662 til binær søk i teorien, når vi hadde de virtuelle dørene på brettet, 316 00:15:32,662 --> 00:15:34,370 eller når Sean var søker etter noe. 317 00:15:34,370 --> 00:15:37,374 Hvis han hadde brukt binære søk, log n vil være den øvre grense for hvor mye 318 00:15:37,374 --> 00:15:38,040 tiden som tar. 319 00:15:38,040 --> 00:15:44,027 Men disse algoritmene som kjørte i log n antatt hva viktige detalj? 320 00:15:44,027 --> 00:15:45,360 At listen ble sortert, ikke sant? 321 00:15:45,360 --> 00:15:47,789 Din algoritmen er galt hvis dine innspill er ikke sortert, 322 00:15:47,789 --> 00:15:49,830 og ennå du bruker noe sånt som binære søk 323 00:15:49,830 --> 00:15:51,704 fordi du kan hoppe rett over elementet 324 00:15:51,704 --> 00:15:53,600 uten å vite det er faktisk det. 325 00:15:53,600 --> 00:15:55,600 >> Nå hva kan dette bety, big O av en? 326 00:15:55,600 --> 00:15:59,117 Dette betyr ikke at algoritmen tar ett og bare ett trinn, 327 00:15:59,117 --> 00:16:01,200 det betyr bare det tar en konstant antall skritt. 328 00:16:01,200 --> 00:16:04,060 Kanskje det er en, kanskje det er 10, kanskje det er 1000, 329 00:16:04,060 --> 00:16:07,750 men det er uavhengig av størrelsen av problemet. 330 00:16:07,750 --> 00:16:10,850 Uansett hvor stor n er, en konstant tid algoritme 331 00:16:10,850 --> 00:16:12,747 alltid tar det samme antall trinn. 332 00:16:12,747 --> 00:16:15,080 Så hva kan være en algoritme vi har snakket om, eller bare 333 00:16:15,080 --> 00:16:20,418 intuitivt som kommer til deg som alltid løper i såkalte konstant tid? 334 00:16:20,418 --> 00:16:20,918 Yeah? 335 00:16:20,918 --> 00:16:22,001 >> PUBLIKUM: Legg to tall. 336 00:16:22,001 --> 00:16:25,320 SPEAKER: Legg to tall, 2 pluss 2 er lik 4, gjort. 337 00:16:25,320 --> 00:16:27,227 Så det kan fungere, hva annet? 338 00:16:27,227 --> 00:16:28,560 Hva med mer virkelige verden, ja? 339 00:16:28,560 --> 00:16:30,686 >> PUBLIKUM: Finne første i en liste. 340 00:16:30,686 --> 00:16:32,810 SPEAKER: Finne den første element i en liste, sikker. 341 00:16:32,810 --> 00:16:34,540 Vi har faktisk vært snakket om arrays allerede, 342 00:16:34,540 --> 00:16:36,540 hvordan får du på første element i en matrise, 343 00:16:36,540 --> 00:16:40,465 uansett hvor lenge matrise er i C-kode? 344 00:16:40,465 --> 00:16:43,090 Du bare bruke som braketten null notasjon, bam, du er der. 345 00:16:43,090 --> 00:16:46,120 Og faktisk arrays, som en side, støtte noe generelt kjent 346 00:16:46,120 --> 00:16:49,240 som random access, random access minne, fordi du kan bokstavelig talt 347 00:16:49,240 --> 00:16:50,284 hoppe til et hvilket som helst sted. 348 00:16:50,284 --> 00:16:52,700 Vi kan gjøre dette enda enklere vi kan spole tilbake til uke null 349 00:16:52,700 --> 00:16:53,900 når vi gjorde Scratch. 350 00:16:53,900 --> 00:16:59,707 Hvor mye tid tok det for si blokk i Scratch å utføre? 351 00:16:59,707 --> 00:17:00,790 Bare konstant tid, ikke sant? 352 00:17:00,790 --> 00:17:03,960 Si noe, sier noe, spiller det ingen rolle 353 00:17:03,960 --> 00:17:07,359 Hvor stor Riper verden er, er det alltid kommer til å ta like lang tid 354 00:17:07,359 --> 00:17:08,490 å bare si noe. 355 00:17:08,490 --> 00:17:11,089 >> Så det er konstant tid, men hva er baksiden? 356 00:17:11,089 --> 00:17:13,030 Hvis det var øvre grenser, hva om vi ønsker 357 00:17:13,030 --> 00:17:17,089 å beskrive de nedre grenser av våre algoritmer gangtid? 358 00:17:17,089 --> 00:17:19,852 Nesten et best case potensielt, om du vil, 359 00:17:19,852 --> 00:17:23,060 selv om disse vilkårene kan gjelde for beste tilfeller, verste tilfellene gjennomsnittlig tilfeller mer 360 00:17:23,060 --> 00:17:26,359 generelt, men la oss bare fokusere på nedre grenser mer generelt. 361 00:17:26,359 --> 00:17:31,920 Hva er en algoritme som har en nedre grense for n skritt, 362 00:17:31,920 --> 00:17:33,350 eller 2n skritt, eller 3n trinn? 363 00:17:33,350 --> 00:17:36,241 Noen faktor av n skritt, det er dens nedre grense. 364 00:17:36,241 --> 00:17:36,740 Yeah? 365 00:17:36,740 --> 00:17:37,910 >> PUBLIKUM: Bubble slag? 366 00:17:37,910 --> 00:17:41,610 >> SPEAKER: Bubble slags tar du minimalt n skritt, hvorfor? 367 00:17:41,610 --> 00:17:42,279 Hvorfor er det? 368 00:17:42,279 --> 00:17:45,320 Hvorfor skulle det begynne å komme til deg intuitivt, selv ikke om den gjør det bare 369 00:17:45,320 --> 00:17:46,530 ennå? 370 00:17:46,530 --> 00:17:47,030 Yeah? 371 00:17:47,030 --> 00:17:47,990 >> PUBLIKUM: [uhørlig]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 SPEAKER: Nettopp. 374 00:17:52,360 --> 00:17:55,810 På best mulig scenario av boble sortere, og mye av algoritmer, 375 00:17:55,810 --> 00:17:58,769 hvis jeg hånd du åtte personer som allerede er sortert, 376 00:17:58,769 --> 00:18:00,560 det ville være tåpelig for deg, algoritmen, 377 00:18:00,560 --> 00:18:02,202 å gå frem og tilbake mer enn en gang, ikke sant? 378 00:18:02,202 --> 00:18:04,285 Fordi så snart du gå gjennom listen en gang, 379 00:18:04,285 --> 00:18:08,090 , du bør innse oh, gjorde jeg ingen bytteavtaler, er denne listen sorteres, exit. 380 00:18:08,090 --> 00:18:09,700 Men det kommer til å ta deg n trinn. 381 00:18:09,700 --> 00:18:12,033 >> Og omvendt, hva er en annen måte å tenke på det? 382 00:18:12,033 --> 00:18:15,240 Bubble sort er en omega, så å si, av n, 383 00:18:15,240 --> 00:18:19,050 fordi hvis du ser på færre enn n elementer, hva 384 00:18:19,050 --> 00:18:23,009 er den grunnleggende problem der? 385 00:18:23,009 --> 00:18:24,550 Du vet ikke om det er sortert, ikke sant. 386 00:18:24,550 --> 00:18:26,800 Vi mennesker kan blikk på åtte mennesker og være som, oh, er det sortert, 387 00:18:26,800 --> 00:18:28,430 som ikke tar meg n skritt, men det gjorde. 388 00:18:28,430 --> 00:18:30,810 Dine øyne, selv om du på en måte av har en stor synsfelt, 389 00:18:30,810 --> 00:18:33,184 du så på åtte elementer, du så på åtte personer, 390 00:18:33,184 --> 00:18:34,610 det er åtte trinn effektivt. 391 00:18:34,610 --> 00:18:38,612 Og bare hvis jeg går gjennom hele liste må jeg skjønner, ja, sortert. 392 00:18:38,612 --> 00:18:41,320 Hvis jeg stoppe halvveis tenker, alt Greit, det er ganske sortert så langt, 393 00:18:41,320 --> 00:18:42,520 hva er oddsen det er ikke sortert? 394 00:18:42,520 --> 00:18:44,186 At algoritmer ikke kommer til å være korrekt. 395 00:18:44,186 --> 00:18:46,250 Kan være raskere, men feil. 396 00:18:46,250 --> 00:18:48,500 >> Så nå har vi en måte å beskriver en nedre grense, 397 00:18:48,500 --> 00:18:49,710 og hva med konstant tid? 398 00:18:49,710 --> 00:18:54,565 Det er en algoritme som har en lavere bundet på sin driftstid for en? 399 00:18:54,565 --> 00:18:58,350 1 trinn, 2 trinn, 10 trinn, men konstant, uavhengig av n, 400 00:18:58,350 --> 00:18:59,310 størrelsen på inngangs? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Ja, i ryggen. 403 00:19:04,600 --> 00:19:05,309 >> PUBLIKUM: Printf? 404 00:19:05,309 --> 00:19:06,183 SPEAKER: Hva er det? 405 00:19:06,183 --> 00:19:07,184 PUBLIKUM: Printf? 406 00:19:07,184 --> 00:19:07,850 SPEAKER: Printf. 407 00:19:07,850 --> 00:19:08,400 OK, sikkert. 408 00:19:08,400 --> 00:19:10,720 Så det tar et fast antall skritt. 409 00:19:10,720 --> 00:19:13,170 Og jeg burde now-- nå at vi snakker om C-kode 410 00:19:13,170 --> 00:19:16,040 og ikke Scratch, noe som sier, med printf, 411 00:19:16,040 --> 00:19:17,710 vi bør begynne å bli forsiktig. 412 00:19:17,710 --> 00:19:21,090 Fordi printf tar input, er det en streng, 413 00:19:21,090 --> 00:19:23,220 og strenger trenger teknisk har lengde. 414 00:19:23,220 --> 00:19:25,530 Så hvis vi nå ønsker å plukke på deg, hvis du ikke tankene, 415 00:19:25,530 --> 00:19:29,430 teknisk vi kan argumentere for at printf tar en variabel lengde inngang, 416 00:19:29,430 --> 00:19:32,270 og sikkert kan det ta mer tid til å skrive ut en streng dette lenge, 417 00:19:32,270 --> 00:19:33,560 enn så lenge. 418 00:19:33,560 --> 00:19:36,570 >> Så hva hvis vi ser bare sortering og søking eksempler? 419 00:19:36,570 --> 00:19:40,450 Hva med Mike Smith i telefonen bok, eller binære søk mer generelt? 420 00:19:40,450 --> 00:19:42,220 I beste fall kan det skje? 421 00:19:42,220 --> 00:19:45,577 Jeg åpner telefonboken, og bam, det er Mike Smith nummer. 422 00:19:45,577 --> 00:19:46,660 Jeg kan ringe ham med en gang. 423 00:19:46,660 --> 00:19:49,390 >> Tok et skritt, kanskje to trinn, men en konstant antall skritt 424 00:19:49,390 --> 00:19:50,230 hvis jeg hadde flaks. 425 00:19:50,230 --> 00:19:52,570 Og ærlig talt, vi så på Mandag din klassekamerat 426 00:19:52,570 --> 00:19:54,710 bli ganske heldig to ganger på rad. 427 00:19:54,710 --> 00:19:57,050 Og det var faktisk konstant tid i en nedre grenser 428 00:19:57,050 --> 00:20:01,280 på algoritmen aktuelle for å finne nummer 50 bak de stengt 429 00:20:01,280 --> 00:20:01,830 dører. 430 00:20:01,830 --> 00:20:06,400 >> Nå, som en side, hvis du oppdager at både stor O, den øvre grensen, 431 00:20:06,400 --> 00:20:09,310 og omega, den nedre grensen, er en i samme, at 432 00:20:09,310 --> 00:20:11,830 er den samme formel i parentes, kan du også 433 00:20:11,830 --> 00:20:15,170 si, bare for å være fancy, at noe er i theta 434 00:20:15,170 --> 00:20:18,270 n eller theta av en annen verdi. 435 00:20:18,270 --> 00:20:20,661 Det betyr bare at når store O og omega er de samme. 436 00:20:20,661 --> 00:20:21,910 Hva nå om valg slag? 437 00:20:21,910 --> 00:20:23,400 La oss bruke denne nye vokabular. 438 00:20:23,400 --> 00:20:27,407 I utvalget sortere, hva var vi gjøre igjen, og igjen, og igjen? 439 00:20:27,407 --> 00:20:29,990 Jeg skulle frem og tilbake gjennom listen, på jakt etter hvem? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Det minste tallet. 442 00:20:34,730 --> 00:20:37,560 >> Så hvor mange trinn, hvordan mange sammenligninger gjorde jeg 443 00:20:37,560 --> 00:20:43,250 må gjøre for å finne ut hvem det minste element i listen var? 444 00:20:43,250 --> 00:20:44,437 n minus en, ikke sant? 445 00:20:44,437 --> 00:20:47,770 Fordi hvis jeg bare begynne med en jeg er gitt, og jeg begynner å sammenligne ham eller henne, 446 00:20:47,770 --> 00:20:49,519 så ham eller henne, ham eller henne, ham eller henne, jeg 447 00:20:49,519 --> 00:20:52,010 kan bare koble elementer sammen n minus 1 ganger. 448 00:20:52,010 --> 00:20:55,630 Så utvalget tar liksom på samme måte n minus 1 trinn første gang. 449 00:20:55,630 --> 00:20:59,540 >> Hvor mange skritt tar det meg til finne den nest minste element? 450 00:20:59,540 --> 00:21:02,920 n minus 2, fordi jeg blir stum hvis jeg fortsetter å se på de samme menneskene 451 00:21:02,920 --> 00:21:06,280 igjen hvis jeg allerede har valgt ham eller henne og sette dem i deres sted. 452 00:21:06,280 --> 00:21:09,270 Og det tredje trinnet, n minus 3, deretter n minus fire. 453 00:21:09,270 --> 00:21:11,020 Vi har sett dette mønsteret før, og faktisk 454 00:21:11,020 --> 00:21:13,460 utvalg slags tilsvar har en øvre grense 455 00:21:13,460 --> 00:21:16,210 av n squared hvis vi gjør opp at summering. 456 00:21:16,210 --> 00:21:19,790 Hva er dens nedre grense, valg liksom? 457 00:21:19,790 --> 00:21:25,350 Minimal, hvor mye tid must utvalg Sorter ta, slik vi definerte det på mandag? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Foreslår to alternativer. 460 00:21:30,490 --> 00:21:32,360 Kanskje det er n, som før. 461 00:21:32,360 --> 00:21:35,040 Kanskje det er n squared, som det er nå som den øvre grensen. 462 00:21:35,040 --> 00:21:35,874 >> PUBLIKUM: n squared. 463 00:21:35,874 --> 00:21:36,664 SPEAKER: n squared. 464 00:21:36,664 --> 00:21:37,368 Hvorfor? 465 00:21:37,368 --> 00:21:40,060 >> PUBLIKUM: Fordi du har å definere [uhørbart]. 466 00:21:40,060 --> 00:21:41,510 >> SPEAKER: Nettopp. 467 00:21:41,510 --> 00:21:45,077 Minst som jeg definert utvalg sort det var ganske naiv, holde det gående, 468 00:21:45,077 --> 00:21:46,160 finne den minste element. 469 00:21:46,160 --> 00:21:47,770 Gå igjen, finne det minste elementet. 470 00:21:47,770 --> 00:21:49,490 Gå igjen, finne det minste elementet. 471 00:21:49,490 --> 00:21:51,700 Det er ingen form for optimalisering i det at 472 00:21:51,700 --> 00:21:54,350 kanskje la meg avbryte etter bare n eller så trinnene. 473 00:21:54,350 --> 00:21:57,080 Så ja, utvalg sortere, omega n squared. 474 00:21:57,080 --> 00:22:00,667 >> Hva om innsetting sortere, der jeg tok som jeg fikk, og da jeg plopped ham 475 00:22:00,667 --> 00:22:01,750 eller henne på rett sted? 476 00:22:01,750 --> 00:22:04,958 Så jeg gikk videre til andre personen, plopped ham eller henne på rett sted. 477 00:22:04,958 --> 00:22:07,910 Så neste person, plopped ham eller henne på rett sted. 478 00:22:07,910 --> 00:22:10,537 Bemerk at dette er svært lineær, så å si. 479 00:22:10,537 --> 00:22:12,620 Jeg er en rett linje, jeg er ikke går frem og tilbake, 480 00:22:12,620 --> 00:22:16,080 Jeg har aldri ser tilbake egentlig, men hva som skjer når jeg setter ham 481 00:22:16,080 --> 00:22:20,302 eller hennes inn i begynnelsen av listen som vi gjorde på mandag? 482 00:22:20,302 --> 00:22:21,010 Hva skjer? 483 00:22:21,010 --> 00:22:21,510 Yeah? 484 00:22:21,510 --> 00:22:23,122 PUBLIKUM: [uhørlig]. 485 00:22:23,122 --> 00:22:24,830 SPEAKER: Ja, det var fangsten, ikke sant? 486 00:22:24,830 --> 00:22:26,746 Du husker kanskje fra klassekameratene dine, hvis de 487 00:22:26,746 --> 00:22:29,670 var å gjøre enhver bevegelse med sine føtter, som var en operasjon. 488 00:22:29,670 --> 00:22:33,610 Så hvis det var tre personer her og den nye personen tilhørte veien der borte, 489 00:22:33,610 --> 00:22:37,360 på en lang etappe som dette, sikker, han eller hun bare kunne gå helt til enden. 490 00:22:37,360 --> 00:22:40,074 Men hvis vi tenker på en datamaskin og en matrise av minne, 491 00:22:40,074 --> 00:22:41,990 disse menneskene går å måtte stokke løpet 492 00:22:41,990 --> 00:22:43,260 å gjøre plass til den personen. 493 00:22:43,260 --> 00:22:46,930 Og slik at n minus en shufflings, n minus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 minus 3 shufflings er bare slags skjer bak meg, ikke foran meg 495 00:22:50,660 --> 00:22:52,710 som før, i noen forstand. 499 00:22:52,557 --> 00:22:54,640 Nå som en side, og som du kanskje har sett på nettet 500 00:22:54,640 --> 00:22:57,699 hvis du begynner poking rundt om sorterer, det er så mange forskjellige lister 501 00:22:57,699 --> 00:22:59,490 ute, noen av dem bedre enn andre. 502 00:22:59,490 --> 00:23:02,200 Faktisk er bogosort ett det er like gøy å se opp. 503 00:23:02,200 --> 00:23:06,650 Bogosort tar et sett tall eller si en kortstokk, 504 00:23:06,650 --> 00:23:09,870 stokker dem tilfeldig, og sjekker om de er sortert. 505 00:23:09,870 --> 00:23:12,130 Og hvis ikke, gjør det igjen. 506 00:23:12,130 --> 00:23:14,140 Og hvis ikke, gjør det igjen. 507 00:23:14,140 --> 00:23:15,440 Hvis ikke, gjør det igjen. 508 00:23:15,440 --> 00:23:17,060 Utrolig dumt. 509 00:23:17,060 --> 00:23:19,520 >> Og ja, hvis du leser som Wikipedia-artikkelen, 510 00:23:19,520 --> 00:23:21,200 sitt kallenavn er dum liksom. 511 00:23:21,200 --> 00:23:25,180 Det vil etterhvert fungere, forhåpentligvis, gitt nok tid, 512 00:23:25,180 --> 00:23:28,240 men at tiden kan ta ganske lang tid. 513 00:23:28,240 --> 00:23:31,650 Så hvis jeg kunne, la oss fart på sakene opp fra Mary Beth eksempel tidligere, 514 00:23:31,650 --> 00:23:35,150 ved å ha noen flere elementer, men to flere prosessorer. 515 00:23:35,150 --> 00:23:37,100 To personer, hvis du ville ikke tankene å bli med meg. 516 00:23:37,100 --> 00:23:40,972 Hva med en over her, og la oss Vær så god ingen der borte? 517 00:23:40,972 --> 00:23:41,722 Ingen der borte? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 Du med den svarte skjorte, ja, komme ned. 520 00:23:44,190 --> 00:23:45,000 Ok, hva heter du? 521 00:23:45,000 --> 00:23:45,720 >> PUBLIKUM: Peter. 522 00:23:45,720 --> 00:23:46,100 >> SPEAKER: Hva er det? 523 00:23:46,100 --> 00:23:46,766 >> PUBLIKUM: Peter. 524 00:23:46,766 --> 00:23:49,450 SPEAKER: Peter, David, hyggelig å møte deg. 525 00:23:49,450 --> 00:23:53,670 Greit, vi har Peter her, hvis du ønsker å komme på bordet over her. 526 00:23:53,670 --> 00:23:54,550 Og hva heter du? 527 00:23:54,550 --> 00:23:55,216 >> PUBLIKUM: Elena. 528 00:23:55,216 --> 00:23:55,970 SPEAKER: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, hyggelig å møte deg. 530 00:23:57,030 --> 00:23:58,060 Elena møte Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 Og vi trenger Andrew opp her også, takk. 533 00:24:02,290 --> 00:24:06,107 Og utfordringen går å være å sortere en kortstokk. 534 00:24:06,107 --> 00:24:08,190 Og hvis ukjente, dekk av kortene bør til slutt 535 00:24:08,190 --> 00:24:11,064 sorteres litt noe sånt dette hvor vi vil gjøre klubbene, deretter 536 00:24:11,064 --> 00:24:13,660 de spar, deretter hjertene og diamanter, fra ess som ett, 537 00:24:13,660 --> 00:24:15,570 hele veien opp til kongen. 538 00:24:15,570 --> 00:24:20,890 >> Kortene jeg kommer til å gi deg kommer til å være 52 i kvantitet. 539 00:24:20,890 --> 00:24:23,160 Vi skal på samme måte gang du, i løpet av et øyeblikk. 540 00:24:23,160 --> 00:24:26,410 Vi kommer til å kaste Andrew opp på skjermen her 541 00:24:26,410 --> 00:24:28,170 slik som å se på som du gjør dette. 542 00:24:28,170 --> 00:24:31,070 Og slik at hele denne er enda mer synlig, 543 00:24:31,070 --> 00:24:33,490 dette er de kortene jeg fikk på Amazon. 544 00:24:33,490 --> 00:24:42,861 Så de er allerede tilfeldig sorteres, og vi kommer til tiden du. 545 00:24:42,861 --> 00:24:44,610 Og vi kommer til å holde det ekte denne gangen, 546 00:24:44,610 --> 00:24:47,820 så vi kommer til å prøve å presse deg fordi ellers vil dette bli kjedelig 547 00:24:47,820 --> 00:24:48,460 raskt. 548 00:24:48,460 --> 00:24:53,860 Hvis du kunne fortsette å sortere 52 elementene sammen via noen midler, som nå. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> Og igjen, når vi ser disse gutta gjør hva, til slutt 551 00:25:07,180 --> 00:25:10,200 kommer til å produsere en åpenbar resultat, tenker egentlig 552 00:25:10,200 --> 00:25:12,962 hvordan de hver gjør det, hvordan du kan beskrive det. 553 00:25:12,962 --> 00:25:15,045 Fordi igjen, er disse Alle prosesser, algoritmer 554 00:25:15,045 --> 00:25:17,090 som vi tar for gitt som et menneske. 555 00:25:17,090 --> 00:25:22,349 Men du har sikkert lenge hatt intuisjon, lenge før du selv 556 00:25:22,349 --> 00:25:24,390 tenkte på å ta en informatikk klasse du 557 00:25:24,390 --> 00:25:27,223 kan ha hatt intuisjon med for å løse problemer som dette. 558 00:25:27,223 --> 00:25:29,560 Men når du kjenner igjen mønstrene og begynne 559 00:25:29,560 --> 00:25:32,407 å formalisere trinnene med som du løse disse problemene, 560 00:25:32,407 --> 00:25:35,490 du vil finne at du kan løse mye mer interessant og mye mer kompleks 561 00:25:35,490 --> 00:25:39,190 problemer raskt. 562 00:25:39,190 --> 00:25:42,351 Så noen fra publikum, hva er i det minste ett element av algoritmen 563 00:25:42,351 --> 00:25:43,350 at de bruker her? 564 00:25:43,350 --> 00:25:44,275 >> PUBLIKUM: [uhørbart] 565 00:25:44,275 --> 00:25:45,150 SPEAKER: Hva er det? 566 00:25:45,150 --> 00:25:47,062 PUBLIKUM: Ved dress. 567 00:25:47,062 --> 00:25:47,770 SPEAKER: Ved dress. 568 00:25:47,770 --> 00:25:50,630 Så først de clustering alle diamantene sammen 569 00:25:50,630 --> 00:25:52,560 det virker, hele hjerter sammen det virker, 570 00:25:52,560 --> 00:25:56,520 og så videre, uten å gjøre forskjell for tallene på kortene. 571 00:25:56,520 --> 00:26:00,900 Og nå de dukker opp, for eksempel, skal sortere dem etter nummer. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Veldig bra. 574 00:26:08,910 --> 00:26:12,370 >> Greit, så hva som kommer til være det siste trinnet så her? 575 00:26:12,370 --> 00:26:16,950 Når vi har fire sorterte dresser, hva trenger vi å gjøre til de fire hauger 576 00:26:16,950 --> 00:26:20,059 for å oppnå en sortert dekk, ganske enkelt? 577 00:26:20,059 --> 00:26:21,350 Så vi trenger å sette dem sammen igjen. 578 00:26:21,350 --> 00:26:25,160 >> Så det er en interessant idé som igjen, daresay, er svært intuitivt selv 579 00:26:25,160 --> 00:26:28,140 hvis du kanskje aldri har slapped den slags merkelapp på det. 580 00:26:28,140 --> 00:26:31,900 Denne grunnleggende tanken om å dele problemet ikke i halvparten av denne tiden 581 00:26:31,900 --> 00:26:33,410 men i det minste i fire deler. 582 00:26:33,410 --> 00:26:36,810 Løse ganske mye fundamentalt identiske problemer 583 00:26:36,810 --> 00:26:40,480 isolert fra hverandre, og deretter å slå sammen resultatene. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 Og, utmerket, gjort. 586 00:26:50,140 --> 00:26:52,140 Greit, en stor runde applaus, hvis vi kunne. 587 00:26:52,140 --> 00:26:56,480 >> [APPLAUSE] 588 00:26:56,480 --> 00:26:59,740 >> SPEAKER: Jeg aner ikke hva du vil gjøre med disse, men her du går. 589 00:26:59,740 --> 00:27:01,690 Takk så mye. 590 00:27:01,690 --> 00:27:04,660 Så la oss se, to minutter og åtte sekunder, 591 00:27:04,660 --> 00:27:07,490 Hvis du ønsker å utfordre vennene dine. 592 00:27:07,490 --> 00:27:12,160 Hva da kommer til å være en ta bort fra dette 593 00:27:12,160 --> 00:27:13,830 at vi kan utnytte mer generelt? 594 00:27:13,830 --> 00:27:16,080 Vel, tenker tilbake til denne matrisen av tall, 595 00:27:16,080 --> 00:27:19,060 og tenker tilbake nå til noen av de pseudo vi har skrevet i det siste, 596 00:27:19,060 --> 00:27:22,080 og dette var den pseudokode for løse telefonboken problem. 597 00:27:22,080 --> 00:27:25,150 Der det i pseudo jeg oppregnet en mer metodisk måte 598 00:27:25,150 --> 00:27:28,400 beskrive hvordan jeg gjorde en veldig intuitiv menneskelig algoritme for å dele telefonen 599 00:27:28,400 --> 00:27:31,650 bok i to, gjenta, gjenta, gjenta, til jeg finner noen som Mike Smith, 600 00:27:31,650 --> 00:27:33,790 hvis han er faktisk i telefonboken. 601 00:27:33,790 --> 00:27:37,610 >> Men jeg slags brukt det jeg vil kalle en svært iterativ tilnærming her, 602 00:27:37,610 --> 00:27:42,160 særlig forvarsel linje 8 og linje 11. 603 00:27:42,160 --> 00:27:46,750 De er bevis på en iterativ tilnærming, en looping tilnærming, 604 00:27:46,750 --> 00:27:49,040 fordi det er akkurat atferden de indusere. 605 00:27:49,040 --> 00:27:52,910 Disse linjene både si gå til linje tre, og du kan slags 606 00:27:52,910 --> 00:27:55,140 tenk på at i din indre øye som en loop. 607 00:27:55,140 --> 00:27:59,080 Det er å fortelle deg å gå tilbake til trinn tre og gjenta, igjen og igjen, 608 00:27:59,080 --> 00:28:00,010 og igjen. 609 00:28:00,010 --> 00:28:04,410 >> Men hva om vi utnytte et sentralt begrep her at vi gjorde ikke siste gang, 610 00:28:04,410 --> 00:28:10,280 og forenkle linje 8 og linje 11 og deres naboer 611 00:28:10,280 --> 00:28:12,840 som nettopp dette, i gult. 612 00:28:12,840 --> 00:28:16,480 Det er ikke fundamentalt forkorte den pseudo veldig mye, 613 00:28:16,480 --> 00:28:20,530 men det er fundamentalt endre arten av min-algoritmen. 614 00:28:20,530 --> 00:28:24,220 Det jeg nå sier i trinn 7, i trinn 10, 615 00:28:24,220 --> 00:28:29,140 er å søke etter Mike på nøyaktig samme måte, 616 00:28:29,140 --> 00:28:31,580 men bare i den venstre halvparten eller høyre halvdel. 617 00:28:31,580 --> 00:28:33,420 >> Så med andre ord, hvis Jeg starter fra trinn én, 618 00:28:33,420 --> 00:28:36,150 plukke opp telefonboken, åpen for midten av telefonboken, se på navn, 619 00:28:36,150 --> 00:28:39,010 hvis Smith er blant heter, ringe Mike, annet 620 00:28:39,010 --> 00:28:44,340 hvis Smith er tidligere i boken, steg syv søke etter Mike i venstre halvdel av boken. 621 00:28:44,340 --> 00:28:47,130 Men den slags føles som det drar meg hengende, ikke sant? 622 00:28:47,130 --> 00:28:49,240 I gult, er en instruksjon, men hvordan gjør jeg 623 00:28:49,240 --> 00:28:51,870 søk etter Mike i venstre halvparten av telefonboken? 624 00:28:51,870 --> 00:28:54,210 Hvor har jeg en algoritme som jeg 625 00:28:54,210 --> 00:28:57,100 kan søke etter noen som Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Vel, det stirrer oss i ansiktet. 627 00:28:58,980 --> 00:29:03,090 Jeg kan bokstavelig talt bruke nøyaktig samme programmet effektivt å gå opp til toppen 628 00:29:03,090 --> 00:29:06,490 igjen, og re-løpe de samme linjer med kode. 629 00:29:06,490 --> 00:29:10,610 >> Så selv om dette bør føle som en bit av en syklisk definisjon 630 00:29:10,610 --> 00:29:13,480 hvor du svare noens spørsmålet ved bare liksom spørre 631 00:29:13,480 --> 00:29:15,990 det samme spørsmålet igjen, som hvorfor, hvorfor, hvorfor? 632 00:29:15,990 --> 00:29:21,580 Realiteten er fordi vi har hardkodet et par spesielle linjer, trinn 4, 633 00:29:21,580 --> 00:29:25,320 som er en hvis, og trinn 12, som er effektivt en annen gren, 634 00:29:25,320 --> 00:29:30,120 fordi vi har disse nødhjelp tiltak, denne algoritmen vil opphøre dersom vi 635 00:29:30,120 --> 00:29:32,050 finne Mike, eller hvis vi ikke gjør det. 636 00:29:32,050 --> 00:29:36,810 Men i trinn 7 og 10 nå, har vi hva vi vil kalle en rekursiv algoritme. 637 00:29:36,810 --> 00:29:40,420 Og rekursjon er faktisk en kraftig idé som er litt tankene bøyd i starten, 638 00:29:40,420 --> 00:29:42,500 at vi nå kan bruke som følger. 639 00:29:42,500 --> 00:29:46,600 >> Flett typen vil være den siste typen som vi ser på, i det minste i klassen formelt. 640 00:29:46,600 --> 00:29:50,040 Og det er fundamentalt annerledes fra de siste tre, og i hvert fall 641 00:29:50,040 --> 00:29:52,140 siste fire hvis vi inkluderer bogosort. 642 00:29:52,140 --> 00:29:54,810 Her er pseudokode for flettingen slag. 643 00:29:54,810 --> 00:30:00,170 Når på innspill av n elementer, så gitt en matrise av størrelse n, hvis n er mindre enn 2, 644 00:30:00,170 --> 00:30:01,040 tilbake. 645 00:30:01,040 --> 00:30:03,610 Så hvorfor har jeg det tilregnelighet sjekk først? 646 00:30:03,610 --> 00:30:09,477 Hva er implikasjonen om jeg leverer deg en matrise som har lengde n er mindre enn 2? 647 00:30:09,477 --> 00:30:11,060 Det er allerede sortert, selvsagt, ikke sant? 648 00:30:11,060 --> 00:30:13,640 Fordi listen har enten ett element, som er trivielt 649 00:30:13,640 --> 00:30:15,180 sortert fordi det er det eneste der. 650 00:30:15,180 --> 00:30:18,138 Eller, det er av størrelse null som betyr det er ingenting å sortere, så av natur 651 00:30:18,138 --> 00:30:18,720 det er sortert. 652 00:30:18,720 --> 00:30:20,410 Det er bare ikke noe galt der. 653 00:30:20,410 --> 00:30:22,310 Så det er vårt såkalte base case. 654 00:30:22,310 --> 00:30:24,440 >> Det ligner i ånden til hva vi gjorde med Mike. 655 00:30:24,440 --> 00:30:26,023 Hvis Mike i telefonboken, kan du ringe ham. 656 00:30:26,023 --> 00:30:27,740 Hvis han ikke er der, gi opp. 657 00:30:27,740 --> 00:30:31,240 Det er en såkalt base case, for å være sikker denne algoritmen på slutten av dagen 658 00:30:31,240 --> 00:30:33,540 vil stoppe i visse tilfeller. 659 00:30:33,540 --> 00:30:37,890 >> Men her er spranget tro nå, annet, sortere venstre halvdel av elementene, 660 00:30:37,890 --> 00:30:39,740 deretter sortere riktig halvparten av elementene, 661 00:30:39,740 --> 00:30:41,189 og deretter fusjonere de sorterte halvdeler. 662 00:30:41,189 --> 00:30:43,230 Og her er der det føles som om vi copping ut. 663 00:30:43,230 --> 00:30:46,900 Jeg har bedt deg om å sortere n elementer, og jeg er 664 00:30:46,900 --> 00:30:50,712 sa OK, gjør det ved å sortere venstre og sortering høyre. 665 00:30:50,712 --> 00:30:52,420 Men jeg sier ett andre ting, og dette 666 00:30:52,420 --> 00:30:55,530 er nøkkelen tema det virker i intuisjon så langt, 667 00:30:55,530 --> 00:30:57,380 det er dette tredje trinnet av sammenslåing. 668 00:30:57,380 --> 00:31:00,430 Som selv om det virker så dum i ånden, 669 00:31:00,430 --> 00:31:02,320 som bare flette ting sammen, virker det 670 00:31:02,320 --> 00:31:05,380 å være et viktig skritt mot remontering av to problemer som 671 00:31:05,380 --> 00:31:07,330 ble delt slutt i to. 672 00:31:07,330 --> 00:31:12,090 >> Så flette sortere, la oss gjøre dette, hvis du vil humor meg, med ett mer demonstrasjon, 673 00:31:12,090 --> 00:31:14,730 akkurat slik at vi har noen tall å jobbe med. 674 00:31:14,730 --> 00:31:19,470 Kan jeg bytte åtte stresset baller for åtte personer? 675 00:31:19,470 --> 00:31:29,320 Ok, hva med deg tre, du fire i denne delen, fem, seks, og la oss 676 00:31:29,320 --> 00:31:30,720 trenger 7, 8, kom igjen opp. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, ja OK. 679 00:31:36,520 --> 00:31:38,640 Minus 8, der vi går, pluss en. 680 00:31:38,640 --> 00:31:39,150 Utmerket. 681 00:31:39,150 --> 00:31:42,000 Greit kom igjen opp, la oss raskt gi deg tall. 682 00:31:42,000 --> 00:31:50,800 Nummer to, nummer tre, fire tall, nummer fem, seks, sju, og åtte. 683 00:31:50,800 --> 00:31:52,140 Jeg gjorde åtte riktig denne gangen. 684 00:31:52,140 --> 00:31:56,390 >> OK, så gå videre hvis du kunne, og La oss sortere i den opprinnelige bestillingen 685 00:31:56,390 --> 00:31:59,810 at vi hadde i går som sett som dette, hvis du ikke hadde noe imot. 686 00:31:59,810 --> 00:32:03,620 Og la oss gjøre det foran på tabellen. 687 00:32:03,620 --> 00:32:06,510 Greit, så flette slag. 688 00:32:06,510 --> 00:32:08,820 Det er der det kommer å få like interessant, 689 00:32:08,820 --> 00:32:12,800 fordi jeg synes å være å gi meg selv så mye mindre informasjon i dag. 690 00:32:12,800 --> 00:32:15,149 >> Så fusjonere liksom først av alt på innspill av n elementer, 691 00:32:15,149 --> 00:32:18,440 og er åpenbart ikke er mindre enn to, er det åtte, så jeg har litt mer arbeid å gjøre. 692 00:32:18,440 --> 00:32:21,140 Så nå mentalt vi som en klasse er nå i andre grenen, 693 00:32:21,140 --> 00:32:22,540 noe som betyr at tre trinn. 694 00:32:22,540 --> 00:32:25,017 Først må jeg sortere venstre halvdel av elementene. 695 00:32:25,017 --> 00:32:26,350 Så hvordan går jeg om du gjør dette? 696 00:32:26,350 --> 00:32:28,950 Vel, jeg kommer til å slags mentalt dele listen her, 697 00:32:28,950 --> 00:32:30,700 du trenger ikke å fysisk flytte, og jeg er 698 00:32:30,700 --> 00:32:33,180 kommer til å fokusere bare på venstre halvdel av elementene her. 699 00:32:33,180 --> 00:32:36,770 Så hvordan går jeg om sortering en liste nå av størrelse fire? 700 00:32:36,770 --> 00:32:38,730 Hva er min algoritme? 701 00:32:38,730 --> 00:32:42,580 Først sjekker jeg er n mindre enn to, nei, så jeg går videre til andre blokken igjen. 702 00:32:42,580 --> 00:32:43,900 Sorter forlot halvparten av elementer. 703 00:32:43,900 --> 00:32:45,608 >> Så nå igjen, mentalt, og det er her 704 00:32:45,608 --> 00:32:49,550 du må løpe mye mental historie, hvis du vil. 705 00:32:49,550 --> 00:32:51,940 Nå er jeg sortering venstre halvparten av den venstre halvdel. 706 00:32:51,940 --> 00:32:57,000 Ok, så nå jeg kaller min samme merge sortering algoritme, er N mindre enn to? 707 00:32:57,000 --> 00:33:00,590 Nei, det er to, så jeg må sortere den venstre halvdelen, og høyre halvdel. 708 00:33:00,590 --> 00:33:02,042 Så her går vi, sortere den venstre halvdelen. 709 00:33:02,042 --> 00:33:03,750 Hvorfor ikke bare ta ett skritt fremover. 710 00:33:03,750 --> 00:33:04,415 Hva heter du? 711 00:33:04,415 --> 00:33:04,860 >> PUBLIKUM: Darren. 712 00:33:04,860 --> 00:33:05,260 >> SPEAKER: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan har trappet fremover. 714 00:33:06,040 --> 00:33:06,748 >> PUBLIKUM: Darren. 715 00:33:06,748 --> 00:33:09,000 SPEAKER: Darren, gjort. 716 00:33:09,000 --> 00:33:10,090 Visste du sier Darren eller Dan? 717 00:33:10,090 --> 00:33:10,550 >> PUBLIKUM: Darren. 718 00:33:10,550 --> 00:33:11,216 >> SPEAKER: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren har trappet fremover og er han nå sortert. 720 00:33:14,422 --> 00:33:16,130 Og dette er nesten en tåpelig påstand, ikke sant? 721 00:33:16,130 --> 00:33:18,862 Jeg vet egentlig ikke synes å være å oppnå noe, men la oss fortsette. 722 00:33:18,862 --> 00:33:20,820 Nå la meg sortere riktig halvparten av elementene. 723 00:33:20,820 --> 00:33:21,200 Hva heter du? 724 00:33:21,200 --> 00:33:21,690 >> PUBLIKUM: Luke. 725 00:33:21,690 --> 00:33:22,273 >> SPEAKER: Luke. 726 00:33:22,273 --> 00:33:23,400 Kom igjen, kom frem. 727 00:33:23,400 --> 00:33:25,640 Gjort, har jeg sortert Luke. 728 00:33:25,640 --> 00:33:28,570 Den venstre halvdelen er nå sortert og høyre halvdel blir nå sortert, 729 00:33:28,570 --> 00:33:30,770 men igjen, det er et viktig steg her. 730 00:33:30,770 --> 00:33:32,940 Hva gjør jeg neste trenger å gjøre? 731 00:33:32,940 --> 00:33:33,941 Fusjonere de sorterte halvdeler. 732 00:33:33,941 --> 00:33:36,648 Nå skal vi bare ha alle frem og tilbake på denne måten, 733 00:33:36,648 --> 00:33:38,620 fordi jeg slags trenger noen scratch plass. 734 00:33:38,620 --> 00:33:40,411 Det er nesten som disse gutta er på et bord, 735 00:33:40,411 --> 00:33:42,460 og jeg trenger litt plass for å flytte dem rundt på. 736 00:33:42,460 --> 00:33:44,170 Så jeg kommer til å fusjonere dere ved å se 737 00:33:44,170 --> 00:33:45,960 på den venstre halvdel og den høyre halvdel. 738 00:33:45,960 --> 00:33:48,740 Og som åpenbart kommer først, venstre halvdel eller høyre halvdel? 739 00:33:48,740 --> 00:33:52,710 Så høyre halvdel, så la oss gå Luke løpet her til Darren opprinnelige posisjon. 740 00:33:52,710 --> 00:33:57,640 Og nå for å fusjonere deres venstre halvdel i, Darren kommer til å flytte rett der. 741 00:33:57,640 --> 00:33:59,750 >> Så føles nesten en boble slags effekt, 742 00:33:59,750 --> 00:34:02,482 men min grunnleggende algoritme, veldig annerledes denne gangen. 743 00:34:02,482 --> 00:34:04,815 Men nå er der ting blir litt irriterende fordi du 744 00:34:04,815 --> 00:34:06,810 må spole tilbake mentalt hvor har jeg sluttet. 745 00:34:06,810 --> 00:34:09,893 Jeg har nettopp slått sammen de sorterte halvdeler, noe som betyr at jeg er der i min algoritme? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Jeg må sortere høyre halvdel, ikke sant? 748 00:34:13,770 --> 00:34:15,910 >> Hvis du spoler, bokstavelig talt på video, vil du 749 00:34:15,910 --> 00:34:18,339 se at vi fikk til dette poenget med Luke og Darren 750 00:34:18,339 --> 00:34:21,370 ved å sortere venstre halvparten av den venstre halvdel. 751 00:34:21,370 --> 00:34:23,430 Da vi fusjonerte de sorterte halvdeler, hvilke 752 00:34:23,430 --> 00:34:27,941 betyr det neste trinnet er liksom den høyre halvdel av venstre halvdel. 753 00:34:27,941 --> 00:34:29,649 Ok, så la oss Dette gjør raskere. 754 00:34:29,649 --> 00:34:33,282 Greit, seks, kommer jeg til å hevde du er nå sortert, kom frem. 755 00:34:33,282 --> 00:34:33,990 Hva heter du? 756 00:34:33,990 --> 00:34:34,589 >> PUBLIKUM: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> SPEAKER: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano er nå sortert. 759 00:34:36,010 --> 00:34:36,450 Og hva heter du? 760 00:34:36,450 --> 00:34:37,080 >> PUBLIKUM: Alex. 761 00:34:37,080 --> 00:34:38,379 >> SPEAKER: Alex er nå sortert. 762 00:34:38,379 --> 00:34:40,750 Venstre halvdel, høyre halvdel, hva er det siste trinnet? 763 00:34:40,750 --> 00:34:41,250 Fusjonere. 764 00:34:41,250 --> 00:34:44,310 Ganske trivielt, så jeg er kommer til å fusjonere i seks, 765 00:34:44,310 --> 00:34:46,930 ta et skritt tilbake, åtte, ta et skritt tilbake. 766 00:34:46,930 --> 00:34:49,530 Og nå merke til dette er en nyttig takeaway, hva 767 00:34:49,530 --> 00:34:53,930 er nå sant om den venstre halvdelen av liste, uavhengig av hvordan vi begynte? 768 00:34:53,930 --> 00:34:55,090 Det er sortert. 769 00:34:55,090 --> 00:34:57,750 >> Nå er det ikke sorteres i den store sammenhengen, 770 00:34:57,750 --> 00:35:00,250 men det er sortert uavhengig av den andre halvparten. 771 00:35:00,250 --> 00:35:04,100 Nå hva trinnet er jeg på hvis jeg holder tilbakespoling hvordan historien begynte? 772 00:35:04,100 --> 00:35:05,680 Nå må jeg sortere høyre halvdel. 773 00:35:05,680 --> 00:35:07,630 Så nå er vi helt tilbake på begynnelsen av historien, 774 00:35:07,630 --> 00:35:08,921 og la oss gjøre dette raskere. 775 00:35:08,921 --> 00:35:11,320 Så jeg kommer til å sortere høyre halvpart av hele listen. 776 00:35:11,320 --> 00:35:13,060 Hva er neste steg? 777 00:35:13,060 --> 00:35:15,840 Sortere den venstre halvdel av høyre halvdel. 778 00:35:15,840 --> 00:35:18,715 Sortere den venstre halvdelen av venstre halvdel av den høyre halvdel. 779 00:35:18,715 --> 00:35:19,590 Og hva heter du? 780 00:35:19,590 --> 00:35:20,230 >> PUBLIKUM: Omar. 781 00:35:20,230 --> 00:35:21,970 >> SPEAKER: Omar, gå fremover, gjort. 782 00:35:21,970 --> 00:35:22,860 Venstre halvdelen er sortert. 783 00:35:22,860 --> 00:35:23,330 Og hva heter du? 784 00:35:23,330 --> 00:35:23,820 >> PUBLIKUM: Chris. 785 00:35:23,820 --> 00:35:25,620 >> SPEAKER: Chris, ta et skritt fremover, er du nå sortert. 786 00:35:25,620 --> 00:35:27,010 Hva er viktig skritt nå? 787 00:35:27,010 --> 00:35:27,510 Fusjonere. 788 00:35:27,510 --> 00:35:30,509 Så man kommer til å flette på plass her, hvis du kunne ta et skritt tilbake, 789 00:35:30,509 --> 00:35:32,930 og tre kommer til å ta et skritt tilbake, flette. 790 00:35:32,930 --> 00:35:38,080 Så den venstre halvdelen av høyre halvdel, er nå sortert. 791 00:35:38,080 --> 00:35:41,747 Oppriktig, føles denne algoritmen som vi kaster bort mye mer tid enn før, 792 00:35:41,747 --> 00:35:44,830 men hvis vi gjorde dette i sanntid, vil vi se hva takeaways kommer til å være. 793 00:35:44,830 --> 00:35:47,970 Nå er jeg her, ikke sant halvparten av den høyre halvdel, 794 00:35:47,970 --> 00:35:50,170 la meg gå videre og sortere den venstre halvdelen. 795 00:35:50,170 --> 00:35:51,482 Skritt fremover, hva heter du? 796 00:35:51,482 --> 00:35:52,190 PUBLIKUM: Ramsey. 797 00:35:52,190 --> 00:35:53,210 SPEAKER: Ramsey er nå sortert. 798 00:35:53,210 --> 00:35:53,570 Hva heter du? 799 00:35:53,570 --> 00:35:54,200 >> PUBLIKUM: Marina. 800 00:35:54,200 --> 00:35:57,033 >> SPEAKER: Marina er nå sortert som vel, hvis du tar ett skritt frem. 801 00:35:57,033 --> 00:36:00,690 Viktig steg her er nå flette, jeg er kommer til å rykke fra mine to lister, 802 00:36:00,690 --> 00:36:01,720 venstre og høyre. 803 00:36:01,720 --> 00:36:05,150 Fem skal komme først, og syv skal komme neste. 804 00:36:05,150 --> 00:36:06,410 Og igjen, dette er bevisst. 805 00:36:06,410 --> 00:36:08,535 Det faktum at de tar skritt frem og tilbake 806 00:36:08,535 --> 00:36:12,997 er ment å representere at vi ikke kan Dette gjør algoritmen i stedet som lett 807 00:36:12,997 --> 00:36:15,830 som boble sortere, og utvalg sortere, og innsetting slags der vi bare 808 00:36:15,830 --> 00:36:16,960 holdt bytte folk. 809 00:36:16,960 --> 00:36:19,940 Jeg bokstavelig talt trenger en slags kladdepapir der 810 00:36:19,940 --> 00:36:21,827 å sette disse folkene mens jeg gjør sammenslåing, 811 00:36:21,827 --> 00:36:23,410 og da kan jeg sette dem tilbake på plass. 812 00:36:23,410 --> 00:36:27,260 Og det er nøkkelen fordi jeg bruker en ny ressurs, plass, ikke bare tid. 813 00:36:27,260 --> 00:36:28,270 >> OK, dette er fantastisk. 814 00:36:28,270 --> 00:36:32,050 Venstre halvdel er sortert, høyre halvdel er sorteres, nå som nøkkelen sammenslåing trinn. 815 00:36:32,050 --> 00:36:33,450 Hvordan kommer jeg til å flette dette? 816 00:36:33,450 --> 00:36:35,470 Så hvis du vil følge min venstre hånd og høyre hånd, 817 00:36:35,470 --> 00:36:38,930 Jeg kommer til å peke min venstre hånd på venstre halvdel, min høyre hånd 818 00:36:38,930 --> 00:36:42,680 på høyre halvdel, og nå må jeg bestemme trinnvis hvem du skal flette inn. 819 00:36:42,680 --> 00:36:44,650 Som åpenbart kommer først? 820 00:36:44,650 --> 00:36:45,150 Nummer én. 821 00:36:45,150 --> 00:36:47,327 Så kom igjen over her, her er vår kladdeblokk. 822 00:36:47,327 --> 00:36:49,910 Så nå nummer én, og varsel hva skal jeg gjøre med min høyre hånd, 823 00:36:49,910 --> 00:36:54,152 Jeg kommer til å flytte min høyre hånd en gå over til punkt nummer tre, 824 00:36:54,152 --> 00:36:55,860 og nå er jeg nødt til å gjøre den samme beslutningen. 825 00:36:55,860 --> 00:36:58,387 Og faktisk stå rett foran Luke her hvis du kunne, 826 00:36:58,387 --> 00:36:59,720 fordi dette er vår kladdeblokk. 827 00:36:59,720 --> 00:37:00,610 Så hvem kommer neste? 828 00:37:00,610 --> 00:37:05,000 Vi har Luke med nummer to eller Chris med nummer tre. 829 00:37:05,000 --> 00:37:07,460 Tydeligvis Luke, antall to, slik at du kommer hit. 830 00:37:07,460 --> 00:37:11,270 >> Men min venstre hånd nå kommer til å skal økes til å peke på Darren, 831 00:37:11,270 --> 00:37:15,160 og her er nøkkelen ta bort med sammenslåing, kommer jeg til å fortsette å gjøre dette, 832 00:37:15,160 --> 00:37:17,340 Selvfølgelig, hvis du snill av følge logikken. 833 00:37:17,340 --> 00:37:19,670 Men hendene mine er aldri kommer til å gå bakover, 834 00:37:19,670 --> 00:37:23,861 som betyr at jeg bare måtte flytte til venstre med min fusjonsprosessen, 835 00:37:23,861 --> 00:37:26,360 og som kommer til å være nøkkelen til vår analyse på bare et øyeblikk. 836 00:37:26,360 --> 00:37:27,859 >> Så nå la oss avslutte dette raskt opp. 837 00:37:27,859 --> 00:37:31,650 Så tre kommer neste, deretter fire kommer etterpå, 838 00:37:31,650 --> 00:37:38,750 og nå fem kommer etterpå, så seks, og syv, og deretter til slutt åtte. 839 00:37:38,750 --> 00:37:42,960 Føles som den tregeste algoritmen ennå, men ikke hvis vi faktisk 840 00:37:42,960 --> 00:37:45,510 kjøre den på samme sorter av klokkefrekvens, så å 841 00:37:45,510 --> 00:37:48,106 tale, med samme tikkende klokke som før. 842 00:37:48,106 --> 00:37:48,605 Hvorfor? 843 00:37:48,605 --> 00:37:51,100 Vel, la oss ta en se på sluttresultatet. 844 00:37:51,100 --> 00:37:56,990 >> La oss gå tilbake over her, la meg trekke opp en demonstrasjon visuelt 845 00:37:56,990 --> 00:37:59,030 av hva vi nettopp gjorde. 846 00:37:59,030 --> 00:38:06,110 Zoome inn her, på dette side her, forteller Firefox 847 00:38:06,110 --> 00:38:08,200 at vi ønsker å stå i kø opp i denne boksen, la oss 848 00:38:08,200 --> 00:38:11,260 si boble sortere, som vi er nå godt kjent, 849 00:38:11,260 --> 00:38:14,130 valg sorter, som er en annen ganske grei en, 850 00:38:14,130 --> 00:38:18,250 og nå dagens merge sort, som vil være vår spennende slutt. 851 00:38:18,250 --> 00:38:21,530 Grunnen til at det tok så mye lenger her med mennesker og meg verbalt er, 852 00:38:21,530 --> 00:38:23,480 selvsagt, jeg forklare hvert trinn. 853 00:38:23,480 --> 00:38:26,920 Men hvis du bare utføre dette, mye som vi gjorde boble sortere og utvalg 854 00:38:26,920 --> 00:38:30,890 liksom ikke bare visuelt, watch hvor mye mer effektivt 855 00:38:30,890 --> 00:38:33,330 denne utnytte av divisjon og erobre 856 00:38:33,330 --> 00:38:39,150 kan når den anvendes på et sett med data som finnes ikke engang størrelse åtte, men enda mye, 857 00:38:39,150 --> 00:38:39,970 mye større. 858 00:38:39,970 --> 00:38:44,585 Jeg gir deg flette sortere, side ved side med disse andre algoritmer. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Dette kommer til å bli smertefullt raskt, og avslutningen 861 00:38:58,530 --> 00:39:00,890 er ikke spesielt klimaks, de bare ender opp sortert. 862 00:39:00,890 --> 00:39:05,280 Men nøkkelen ta bort er at Se hvor mye raskere flette sortere 863 00:39:05,280 --> 00:39:08,110 var, med mindre du tror jeg er bare slags tuller med deg. 864 00:39:08,110 --> 00:39:13,100 Hvis vi gjør dette for siste gang, la oss laste dette, la oss gå tilbake 865 00:39:13,100 --> 00:39:14,960 og velg boble sortere, og bare for morro skyld, 866 00:39:14,960 --> 00:39:17,330 la oss velge innsetting sortere, bare for godt mål. 867 00:39:17,330 --> 00:39:20,020 Og denne gangen igjen, la oss velge merge sortere og la oss 868 00:39:20,020 --> 00:39:21,595 faktisk kjøre disse side ved side. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> Og det er ikke, faktisk, et lykketreff. 871 00:39:26,930 --> 00:39:31,140 Hva jeg har effektivt gjort er at jeg har delt mitt innspill i to, igjen, 872 00:39:31,140 --> 00:39:32,240 og igjen og igjen. 873 00:39:32,240 --> 00:39:35,590 Og det er bare så mange ganger du kan dele dine innspill i halvdeler, venstre 874 00:39:35,590 --> 00:39:36,240 og høyre. 875 00:39:36,240 --> 00:39:39,425 Hva er formelen som vi fortsette å se som beskriver divisjonen i halvparten 876 00:39:39,425 --> 00:39:41,050 igjen, og igjen, og igjen, og igjen? 877 00:39:41,050 --> 00:39:41,890 >> PUBLIKUM: Logg n. 878 00:39:41,890 --> 00:39:42,760 >> SPEAKER: Logg n. 879 00:39:42,760 --> 00:39:46,300 Men så er det en annen viktig skritt, denne algoritmen er ikke logge n trinn. 880 00:39:46,300 --> 00:39:48,992 Hvis det var bare log n trinn, vi ville være i det samme problemet 881 00:39:48,992 --> 00:39:51,200 som før hvor vi ikke kan være at alt er sortert. 882 00:39:51,200 --> 00:39:54,480 Du må minimal se på n elementer for å være sikker på n elementer sorteres, 883 00:39:54,480 --> 00:39:55,950 ellers er det en tillitserklæring. 884 00:39:55,950 --> 00:39:59,810 >> Så det er minimalt log n trinn, men hva med denne nøkkelen sammenslåing trinn 885 00:39:59,810 --> 00:40:04,370 hvor jeg fusjonert min venstre halvdel og høyre halvparten og gikk over scenen? 886 00:40:04,370 --> 00:40:06,980 Hvor mange skritt er at å fusjonere? 887 00:40:06,980 --> 00:40:10,150 Det er n, men jeg gjorde ikke bare flette den siste tiden. 888 00:40:10,150 --> 00:40:15,089 På hver av de nestede anrop, på hvert av disse nestet fusjonerer, jeg fortsatt sortert. 889 00:40:15,089 --> 00:40:18,380 Jeg slått sammen disse to gutta, så disse to folkens, da disse to gutta, og så videre. 890 00:40:18,380 --> 00:40:19,955 >> Så jeg gjorde sammenslåing igjen, og igjen. 891 00:40:19,955 --> 00:40:20,580 Hvor mange ganger? 892 00:40:20,580 --> 00:40:23,510 Så hver gang jeg delt liste i to, gjorde jeg en flette. 893 00:40:23,510 --> 00:40:25,460 Dele opp listen i to, gjør en flette. 894 00:40:25,460 --> 00:40:28,570 Så hvis dele listen kan gjøres for log n ganger, 895 00:40:28,570 --> 00:40:33,880 og sammenslåing tar slutt n trinn, hva som kan være nå den øvre 896 00:40:33,880 --> 00:40:37,000 bundet på løpe tid algoritmen vår? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> Og ja, det er det vi har oppnådd her. 899 00:40:40,560 --> 00:40:44,650 Så føler at du ser visuelt når disse tre tingene kjøres side ved side 900 00:40:44,650 --> 00:40:47,930 er n squared mot n squared mot n log n. 901 00:40:47,930 --> 00:40:51,010 Hvilke fundamentalt vi får se, ikke bare i dag, men i fremtiden, 902 00:40:51,010 --> 00:40:52,760 er mye, mye raskere. 903 00:40:52,760 --> 00:40:56,010 En applaus for disse gutta, Jeg vil belønne dem med stress baller. 904 00:40:56,010 --> 00:41:00,260 La oss utsette her i dag, og vi vil se deg på mandag. 905 00:41:00,260 --> 00:41:02,255