1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> Speak: Okej, det här är CS50. 3 00:00:14,910 --> 00:00:19,020 Detta är slutet av vecka tre, och om du inte har utnyttjat redan, 4 00:00:19,020 --> 00:00:21,790 vet att det kommer att finnas lunch denna fredag ​​som vanligt, där 5 00:00:21,790 --> 00:00:25,430 du kan njuta av bra samtal och mat på Fire and Ice 6 00:00:25,430 --> 00:00:27,980 med några av CS50: s personal och klasskamrater. 7 00:00:27,980 --> 00:00:30,170 Chef till denna URL här. 8 00:00:30,170 --> 00:00:33,420 >> Nu kanske du minns, eller du kan snart vara bekant med, 9 00:00:33,420 --> 00:00:35,970 dessa saker här, vilket ges ut i slutet 10 00:00:35,970 --> 00:00:37,850 av terminen för många klasser. 11 00:00:37,850 --> 00:00:40,870 Så kallade examen blå böcker, där du skriver dina svar på tentor. 12 00:00:40,870 --> 00:00:44,240 Nu har jag här 26 sådana blå böcker, på var och en av dem 13 00:00:44,240 --> 00:00:47,580 är skrivet ett namn, A till Z. Och ja namnen är så enkelt, A 14 00:00:47,580 --> 00:00:50,490 genom Z. Och en av målen till hands idag 15 00:00:50,490 --> 00:00:53,910 kommer att vara att fortsätta det Vi började på måndagen, vilket inte är 16 00:00:53,910 --> 00:00:57,830 så mycket att titta på koden, men egentligen tittar på idéer och problemlösning. 17 00:00:57,830 --> 00:01:00,170 Ett av de mål och löften om kursen 18 00:01:00,170 --> 00:01:02,985 är att lära dig att tänka mer noggrant, mer metodiskt, 19 00:01:02,985 --> 00:01:05,400 och att lösa problem på ett effektivare sätt. 20 00:01:05,400 --> 00:01:09,526 Och faktiskt, kan vi göra det riktigt utan att ens röra en rad kod. 21 00:01:09,526 --> 00:01:12,150 Så jag har ett par elefanter upp här i dag, orange och blått, 22 00:01:12,150 --> 00:01:15,780 om vi kunde få en volontär, kanske från längre tillbaka än vanligt. 23 00:01:15,780 --> 00:01:18,070 Vad sägs om just där, kom ner. 24 00:01:18,070 --> 00:01:24,180 Målet, som kommer att vara till hjälpa plus administrera denna examen här. 25 00:01:24,180 --> 00:01:24,935 Vad heter du? 26 00:01:24,935 --> 00:01:25,768 >> PUBLIK: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 Speak: Mary Beth, kom upp. 28 00:01:27,560 --> 00:01:29,560 Låt mig få mikrofonen här för dig. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Trevligt att träffas. 31 00:01:32,880 --> 00:01:34,005 >> PUBLIK: Trevligt att träffas. 32 00:01:34,005 --> 00:01:36,790 Speak: Okej, så jag har Här blå böcker A till Z, 33 00:01:36,790 --> 00:01:41,680 och jag ska låtsas att Jag har en av studenterna, 34 00:01:41,680 --> 00:01:45,770 och de kommer i något slumpmässigt vid slutet av en tre timmars tenta blocket, 35 00:01:45,770 --> 00:01:49,400 så de hamna i några semi-slumpmässig ordning så här. 36 00:01:49,400 --> 00:01:54,510 Nu ditt jobb på bara ett ögonblick går att vara-- detta är faktiskt hur de får 37 00:01:54,510 --> 00:01:56,820 slås in vid slutet av klassen, mest troligt. 38 00:01:56,820 --> 00:02:01,120 Ditt jobb nu kommer att bli helt enkelt att sortera dessa blå böcker för oss 39 00:02:01,120 --> 00:02:05,220 från A till Z. 40 00:02:05,220 --> 00:02:08,400 >> PUBLIK: Åh, det här är kommer att ta evigheter. 41 00:02:08,400 --> 00:02:13,747 >> Speak: Och vi kommer att titta på när du gör detta, inget tryck. 42 00:02:13,747 --> 00:02:15,330 PUBLIK: Nej, ingen press eller något. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> Speak: Och för skojs skull, låt oss sätta upp en timer. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> PUBLIK: Så mycket roligt, så roligt. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> Speak: Jag kan hålla mikrofonen för dig. 49 00:02:38,574 --> 00:02:40,240 Okej, vi har just fördubblat hastigheten. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Så under tiden, låt mig ställa vad som är kommer att bli frågan om Mary Beth 52 00:02:49,060 --> 00:02:51,540 är vad gör hon, hur är Hon går om att lösa det här? 53 00:02:51,540 --> 00:02:54,040 Och faktiskt, kanske du inte har någonsin tänkt på något 54 00:02:54,040 --> 00:02:57,440 så enkelt som när du plockar upp 26 böcker som denna, 55 00:02:57,440 --> 00:02:59,350 som har en naturlig beställa dem. 56 00:02:59,350 --> 00:03:01,335 Hur ser processen att du faktiskt använder? 57 00:03:01,335 --> 00:03:03,770 Är det ganska slumpmässigt bara plocka den första du ser 58 00:03:03,770 --> 00:03:05,250 och sätta det på sin plats? 59 00:03:05,250 --> 00:03:09,680 Brukar du först flytta dina händer runt Letar du efter en sedan letar efter B? 60 00:03:09,680 --> 00:03:11,722 Brukar du titta på en par av dem sida vid sida 61 00:03:11,722 --> 00:03:14,680 och bara säga, vänta lite, det här är inte rätt, och sedan byta ordern? 62 00:03:14,680 --> 00:03:16,960 Vi såg redan på måndag att det finns ett antal olika sätt 63 00:03:16,960 --> 00:03:22,140 där vi kan göra detta, och ja som vi i slutet här, 64 00:03:22,140 --> 00:03:26,360 Jag skulle notera kanske vad Mary Beth gör. 65 00:03:26,360 --> 00:03:30,040 Vi har några högar det verkar, en större en, tre mindre. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> PUBLIK: Jag beställer dem när jag hittar två bokstäver 68 00:03:36,415 --> 00:03:39,540 som jag vet är tillsammans i en sekvens, Jag satte ihop dem så att jag inte 69 00:03:39,540 --> 00:03:42,915 oroa dig hålla spår av en hel rad av böcker. 70 00:03:42,915 --> 00:03:45,706 Det är bara, åh, A är först, Jag har en bunt här. 71 00:03:45,706 --> 00:03:47,580 Speak: Så, nästan som en pusselbitar som 72 00:03:47,580 --> 00:03:49,860 har rätt form för att stämmer med varandra. 73 00:03:49,860 --> 00:03:51,026 PUBLIK: Ganska mycket, ja. 74 00:03:51,026 --> 00:03:55,320 Speak: OK, utmärkt. 75 00:03:55,320 --> 00:03:59,850 Och nu var och en av dessa pålar är förmodligen sorteras? 76 00:03:59,850 --> 00:04:00,990 >> PUBLIKEN: Ja. 77 00:04:00,990 --> 00:04:09,900 >> Speak: Okej, A till Z. Alla höger, grattis, du gjorde det. 78 00:04:09,900 --> 00:04:11,461 Du har ditt val. 79 00:04:11,461 --> 00:04:11,960 Blue? 80 00:04:11,960 --> 00:04:13,530 Okej, tack för det. 81 00:04:13,530 --> 00:04:16,679 Så Mary Beth gjorde föreslå vad hennes inställning var, 82 00:04:16,679 --> 00:04:19,720 men vad är en annan metod hur man skulle gå att sortera dessa saker? 83 00:04:19,720 --> 00:04:21,130 Vad skulle du ha gjort? 84 00:04:21,130 --> 00:04:24,060 Rekordet att slå skulle ha varit en minut och 50-tal sekunder 85 00:04:24,060 --> 00:04:26,039 plus de som jag glömde att räkna. 86 00:04:26,039 --> 00:04:27,080 Vad skulle du ha gjort? 87 00:04:27,080 --> 00:04:27,579 Yeah? 88 00:04:27,579 --> 00:04:28,735 PUBLIK: Ta stapeln. 89 00:04:28,735 --> 00:04:29,776 Börja från början. 90 00:04:29,776 --> 00:04:32,284 Kontrollera dina papper. 91 00:04:32,284 --> 00:04:36,586 Och om den översta en är högre än, kanske, de är, 92 00:04:36,586 --> 00:04:38,980 botten en är högre, sedan byta dem. 93 00:04:38,980 --> 00:04:41,300 >> Speak: OK, så börjar vid toppen och botten, 94 00:04:41,300 --> 00:04:43,716 och sedan arbeta dig inåt så där, byta dem? 95 00:04:43,716 --> 00:04:46,580 OK, så lite liknande i anden att bubbla sortera, 96 00:04:46,580 --> 00:04:49,160 men att välja ytterlighet inte de närliggande par. 97 00:04:49,160 --> 00:04:52,080 Men den korta av det är att det finns säkert en massa olika sätt 98 00:04:52,080 --> 00:04:54,210 vi kan göra detta, och ärligt talat, jag tror att du typ av 99 00:04:54,210 --> 00:04:55,700 antagit ett par metoder, eller hur? 100 00:04:55,700 --> 00:05:00,567 Du gjorde sorts fyra sorterade högar, och sedan effektivt slås ihop dem. 101 00:05:00,567 --> 00:05:02,650 Och det är, förmodar, en annan tekniken helt och hållet. 102 00:05:02,650 --> 00:05:06,950 Du har inte behandla det som en stor hög, du indelade problemet i fyra brigader, 103 00:05:06,950 --> 00:05:09,820 om du vill, och sedan på något sätt fusione dem i slutet. 104 00:05:09,820 --> 00:05:13,410 >> Så låt oss betrakta, i slutändan, hur annat vi kan göra det här. 105 00:05:13,410 --> 00:05:15,860 Vi formalise begreppet bubbla sortera förra gången, 106 00:05:15,860 --> 00:05:18,780 och bubbelsorterings minns var en algoritm som vi visualiserade 107 00:05:18,780 --> 00:05:22,640 med åtta av dina klasskamrater här uppe, till synes slumpmässigt sorteras först. 108 00:05:22,640 --> 00:05:26,110 Och vi beslutade sedan parvis, om två element är ur funktion, 109 00:05:26,110 --> 00:05:26,950 helt enkelt byta dem. 110 00:05:26,950 --> 00:05:28,930 Så fyra och två är uppenbarligen ur funktion, 111 00:05:28,930 --> 00:05:31,080 så dessa två klasskamrater bytte positioner. 112 00:05:31,080 --> 00:05:35,390 Och så upprepade vi med fyra och sex, sedan sex och åtta, på varje iteration, 113 00:05:35,390 --> 00:05:36,980 rör sig åt höger. 114 00:05:36,980 --> 00:05:42,590 >> Så med tanke på åtta personer, hur många parvisa jämförelser gjorde jag när hon gick från 115 00:05:42,590 --> 00:05:45,220 vänster till höger i en sådan iteration? 116 00:05:45,220 --> 00:05:48,410 Hur många jämförelser? 117 00:05:48,410 --> 00:05:49,197 Sju, eller hur? 118 00:05:49,197 --> 00:05:51,405 För om det finns åtta människor, men du har paret 119 00:05:51,405 --> 00:05:53,880 dem och du rör ett hopp till höger, 120 00:05:53,880 --> 00:05:56,060 du kommer inte att ha åtta jämförelser eftersom du kan inte jämföra 121 00:05:56,060 --> 00:05:59,226 ett element mot sig själv, eller det skulle bara vara meningslöst, så du har sju. 122 00:05:59,226 --> 00:06:01,290 , Eller mer generellt, om Vi har n personer, vi 123 00:06:01,290 --> 00:06:04,300 gör n minus ett jämförelser med bubbel slag. 124 00:06:04,300 --> 00:06:08,150 >> Så låt oss tänka nu hur bra eller dålig bubbla sortera faktiskt var, och försök 125 00:06:08,150 --> 00:06:13,570 att ge oss själva ordförråd med vilket till kritik algoritmer som denna, 126 00:06:13,570 --> 00:06:14,430 och snart våra egna. 127 00:06:14,430 --> 00:06:16,970 Så den första passera genom bubbla sortera, första gången 128 00:06:16,970 --> 00:06:20,909 Jag gick från vänster till höger över skede, tog mig n minus ett jämförelser. 129 00:06:20,909 --> 00:06:22,950 Och det kommer att bli min måttenhet, eller hur? 130 00:06:22,950 --> 00:06:26,170 Jag var typ av prat och promenader, något snabbt, något långsam, 131 00:06:26,170 --> 00:06:29,300 så räknar jag antalet sekunder är inte särskilt träffande, 132 00:06:29,300 --> 00:06:32,260 men räkna antalet verksamheter som jag gjorde i måndags, 133 00:06:32,260 --> 00:06:35,900 jämföra två personer, anser att som en trevlig måttenhet. 134 00:06:35,900 --> 00:06:40,980 >> Så n minus 1 steg första gången men vad hände efter det? 135 00:06:40,980 --> 00:06:46,610 Vad är det upp av ett pass genom en i övrigt osorterad lista? 136 00:06:46,610 --> 00:06:49,840 Vad kan du berätta om elementet som var hela vägen dit? 137 00:06:49,840 --> 00:06:51,300 Yeah? 138 00:06:51,300 --> 00:06:52,870 Det var den största elementet, eller hur? 139 00:06:52,870 --> 00:06:55,710 Nummer åtta, även om hon började här, varje gång jag 140 00:06:55,710 --> 00:06:57,860 jämfört henne mot en granne, höll hon 141 00:06:57,860 --> 00:07:00,480 bubblar upp till höger sidan av listan. 142 00:07:00,480 --> 00:07:02,710 Och faktiskt, det är där algoritmen har fått sitt namn. 143 00:07:02,710 --> 00:07:07,630 >> Nu med den logiken, hur många jämförelser behöver jag göra på andra gången 144 00:07:07,630 --> 00:07:09,800 Jag gör det passning från vänster till höger? 145 00:07:09,800 --> 00:07:10,730 n minus 2, eller hur? 146 00:07:10,730 --> 00:07:14,297 Det skulle bara vara slöseri med min tid om jag hålla jämföra åtta mot någon 147 00:07:14,297 --> 00:07:16,630 annat eftersom vi redan vet hon var på rätt plats. 148 00:07:16,630 --> 00:07:19,760 Så det är lite av en optimering, så nästa pass 149 00:07:19,760 --> 00:07:23,899 kommer att bli plus n minus två steg, där n är antalet personer. 150 00:07:23,899 --> 00:07:26,940 Nu kan du typ av extrapolera, och med om du inte är en datorforskare, 151 00:07:26,940 --> 00:07:27,680 hur detta slutar. 152 00:07:27,680 --> 00:07:31,259 Vid slutet av denna algoritm, förmodligen du har bara en jämförelse kvar. 153 00:07:31,259 --> 00:07:33,800 Du måste slags fixera början av listan i fall två 154 00:07:33,800 --> 00:07:36,540 och en är i ordning och bör vara ett och två, 155 00:07:36,540 --> 00:07:40,330 så denna bottnar på plus en slutlig jämförelse. 156 00:07:40,330 --> 00:07:44,500 >> Nu pricken, kort, kort sorts vågor är det händerna på några av de saftigare detaljer, 157 00:07:44,500 --> 00:07:46,452 men låt oss bara gå vidare och förenkla. 158 00:07:46,452 --> 00:07:48,660 Om ni minns från hög skola, ärligt talat, en hel del av er 159 00:07:48,660 --> 00:07:50,340 hade matteböcker som hade en liten fusklapp 160 00:07:50,340 --> 00:07:52,550 på framsidan eller bakstycket som visade dig 161 00:07:52,550 --> 00:07:56,400 vilken serie summationer som detta i slutändan läggas till. 162 00:07:56,400 --> 00:07:59,600 I det allmänna fallet, om du har en variabel som n, och faktiskt den här, 163 00:07:59,600 --> 00:08:01,634 om du tittat på ditt old school matte bok, 164 00:08:01,634 --> 00:08:04,050 skulle du se att det faktiskt lägger upp till denna summa här, 165 00:08:04,050 --> 00:08:07,970 n gånger n minus 1 alla delat med 2. 166 00:08:07,970 --> 00:08:11,172 Så nu vill jag bara föreskriva detta är sant, så på ett språng i tro, 167 00:08:11,172 --> 00:08:12,880 det är vad det här summerar upp till, och vi kunde 168 00:08:12,880 --> 00:08:14,341 bevisa att på ett mer allmänt fall. 169 00:08:14,341 --> 00:08:15,590 Men nu ska vi utöka denna. 170 00:08:15,590 --> 00:08:19,920 Så låt oss multiplicera denna, så det är n kvadrat, minus n, allt delat med 2. 171 00:08:19,920 --> 00:08:23,200 Det är verkligen n kvadrat, delat med 2, minus n över 2, 172 00:08:23,200 --> 00:08:25,010 så det är allt trevligt och intressant. 173 00:08:25,010 --> 00:08:27,060 Men vad händer om vi nu plug-in ett värde? 174 00:08:27,060 --> 00:08:29,724 Anta att jag inte hade åtta människor, men säger en miljon. 175 00:08:29,724 --> 00:08:31,890 Och en miljon bara för att det är ett ganska stort antal, 176 00:08:31,890 --> 00:08:34,039 Låt oss koppla den in och se vad som händer. 177 00:08:34,039 --> 00:08:39,039 Så om jag ansluter en miljon in i den formel Jag kommer att få en miljon kvadrat, 178 00:08:39,039 --> 00:08:42,868 delat med 2, minus en miljoner delat med 2. 179 00:08:42,868 --> 00:08:44,159 Nu vad som kommer att vara lika? 180 00:08:44,159 --> 00:08:47,354 Så 500 miljarder, minus 500.000. 181 00:08:47,354 --> 00:08:49,270 Och om jag faktiskt gör att matte ut, innebär att 182 00:08:49,270 --> 00:08:53,920 att sortera en miljon människor med bubbelsorterings 183 00:08:53,920 --> 00:09:01,800 kan ta mig 499.999.500.000 steg eller jämförelser i slutet, 184 00:09:01,800 --> 00:09:02,900 vi bara extrapolera. 185 00:09:02,900 --> 00:09:06,860 >> Det känns ganska långsam, men uppriktigt sagt mätning av en viss ingång 186 00:09:06,860 --> 00:09:09,160 så här, är inte så talande. 187 00:09:09,160 --> 00:09:14,050 Men ja det antyder att så n blir större och större, denna algoritm 188 00:09:14,050 --> 00:09:16,280 slags känns värre och värre, eller om du verkligen 189 00:09:16,280 --> 00:09:20,450 börjar känna smärtan av att exponentiering, att n kvadrat, 190 00:09:20,450 --> 00:09:21,770 vilket ger upp ganska snabbt. 191 00:09:21,770 --> 00:09:25,340 Och denna detalj är inte förlorat på människor, faktiskt 192 00:09:25,340 --> 00:09:29,640 för några år sedan en viss senator som var kampanjarbete, satte sig ner för en intervju 193 00:09:29,640 --> 00:09:32,180 med Googles Eric Schmidt, CEO på tiden, 194 00:09:32,180 --> 00:09:36,380 och utmanades med en fråga ungefär som vi utforskar i dag. 195 00:09:36,380 --> 00:09:38,468 Låt oss ta en titt. 196 00:09:38,468 --> 00:09:45,280 >> [VIDEOAVSPELNING] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Du är här på Google, och jag gillar 198 00:09:48,560 --> 00:09:53,382 att tänka på ordförandeskapet som en anställningsintervju. 199 00:09:53,382 --> 00:09:56,434 Nu är det svårt att få ett jobb som president, 200 00:09:56,434 --> 00:09:58,100 och du går igenom stelhet nu. 201 00:09:58,100 --> 00:10:01,860 Det är också svårt att få jobb på Google. 202 00:10:01,860 --> 00:10:05,490 Vi har frågor, och vi fråga våra kandidater frågor, 203 00:10:05,490 --> 00:10:09,770 och den här är från Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 Vad-- ni tror att jag är skojar, det är just här. 205 00:10:14,760 --> 00:10:17,930 Vad är det mest effektiva sättet att sortera en miljon 32-bitars heltal? 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 >> Jag är ledsen, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Nej, nej, nej. 210 00:10:27,400 --> 00:10:30,700 Jag tror att bubblan sorterings skulle vara fel väg att gå. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> Kom igen, som berättade det här? 213 00:10:38,180 --> 00:10:40,590 Jag såg inte datorn vetenskap i din bakgrund. 214 00:10:40,590 --> 00:10:42,130 >> -Vi Fick våra spioner där. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Låt oss be en annan intervju fråga. 217 00:10:48,444 --> 00:10:49,300 >> [END VIDEOAVSPELNING] 218 00:10:49,300 --> 00:10:52,290 >> Speak: Så talar om specifika siffror dock, 219 00:10:52,290 --> 00:10:53,890 kommer inte att vara så användbart. 220 00:10:53,890 --> 00:10:56,810 Det är inte ett liv lektion som bubblan sortera, givet en miljon ingångar, 221 00:10:56,810 --> 00:10:58,590 kan ta så många som 500 miljarder steg. 222 00:10:58,590 --> 00:11:01,120 Du kan inte riktigt generalisera alltför effektivt från att 223 00:11:01,120 --> 00:11:03,560 och göra bra designbeslut när man skriver program. 224 00:11:03,560 --> 00:11:07,070 Så låt oss fokusera även på hur vi kan förenkla detta resultat. 225 00:11:07,070 --> 00:11:11,780 >> Så jag har gulmarkerat här resultatet av n kvadrat dividerat med 2, 226 00:11:11,780 --> 00:11:14,330 så en miljon kvadrat dividerad med två, och sedan 227 00:11:14,330 --> 00:11:16,710 Jag har markerat vad det ultimata svaret var 228 00:11:16,710 --> 00:11:20,180 när vi dras bort n delat med 2. 229 00:11:20,180 --> 00:11:24,850 Och påståendet jag ska göra nu är, vem fan bryr sig om du subtraherar bort 230 00:11:24,850 --> 00:11:30,060 lite gamla n över 2 när den första del av denna formel är så mycket större? 231 00:11:30,060 --> 00:11:33,910 Den dominerar den andra sikt n kvadrat delat med 2 232 00:11:33,910 --> 00:11:37,510 är så mycket större, uppenbarligen, såsom n blir stor som en miljon, 233 00:11:37,510 --> 00:11:41,450 det är det verkligen en stor skillnad på slutet av dagen mellan 500.000.000.000 234 00:11:41,450 --> 00:11:45,730 och 499.999.500.000? 235 00:11:45,730 --> 00:11:46,349 Inte riktigt. 236 00:11:46,349 --> 00:11:48,640 Och så vad vi ska gör som datavetare är 237 00:11:48,640 --> 00:11:53,270 ignorera dessa lägre ordningens termer och ta något som detta och verkligen 238 00:11:53,270 --> 00:11:56,050 bara förenkla det till term som kommer spela någon roll. 239 00:11:56,050 --> 00:12:00,315 De större våra datamängder blir, desto större våra databaser får, desto fler webbsidor 240 00:12:00,315 --> 00:12:02,690 Vi måste söka, desto mer vänner du har på Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Som n blir större, vi är verkligen kommer att bry sig om den största 242 00:12:07,340 --> 00:12:11,560 termen i någon sådan analys av våra algoritmer prestanda. 243 00:12:11,560 --> 00:12:16,230 Och jag ska säga, vet du vad, bubbla slag är i storleksordningen big O, 244 00:12:16,230 --> 00:12:18,060 i storleksordningen n kvadrat. 245 00:12:18,060 --> 00:12:20,090 Det är inte precis n kvadrat som vi har sett, 246 00:12:20,090 --> 00:12:22,060 men vem bryr sig egentligen om de mindre termer, 247 00:12:22,060 --> 00:12:24,390 och ärligt talat, som verkligen bryr sig om vi delar med 2? 248 00:12:24,390 --> 00:12:25,870 Det är bara en konstant faktor. 249 00:12:25,870 --> 00:12:29,480 Och är 500 miljarder jämfört med 250 miljard verkligen så stor grej? 250 00:12:29,480 --> 00:12:32,190 Jag kunde bara vänta ett år, Låt min laptop bokstav 251 00:12:32,190 --> 00:12:34,810 få dubbelt så snabbt i hårdvara, och den typen av skillnad 252 00:12:34,810 --> 00:12:36,650 bara försvinner naturligt med tiden. 253 00:12:36,650 --> 00:12:39,300 >> Det vi bryr oss om är uttrycket, den del 254 00:12:39,300 --> 00:12:42,489 av uttrycket som kommer att variera som vår ingång blir större och större. 255 00:12:42,489 --> 00:12:45,280 Och mycket riktigt, i den verkliga världen, det är vad som händer mer och mer 256 00:12:45,280 --> 00:12:48,330 är ingångarna till våra problem och algoritmer blir större. 257 00:12:48,330 --> 00:12:53,470 Så stor o kommer att bli notationen, den asymptotiska notation, att vi bara 258 00:12:53,470 --> 00:12:57,160 använda som datavetare för att beskriva prestanda eller gångtid, 259 00:12:57,160 --> 00:12:58,130 av en algoritm. 260 00:12:58,130 --> 00:13:00,800 Så att vi kan jämföra algoritmer på olika datorer skriftliga 261 00:13:00,800 --> 00:13:04,170 av olika personer, med hjälp av några i grunden liknande metrisk 262 00:13:04,170 --> 00:13:07,557 liksom antalet jämförelser du gör, eller kanske det antal swappar 263 00:13:07,557 --> 00:13:08,140 du gör. 264 00:13:08,140 --> 00:13:11,910 >> Vad vi ska inte räkningen är den tid 265 00:13:11,910 --> 00:13:13,981 som passerar på klockan på väggen normalt. 266 00:13:13,981 --> 00:13:16,230 Vad vi ska inte oroa sig om är hur mycket minne 267 00:13:16,230 --> 00:13:17,820 du använder idag på Minst, men det är 268 00:13:17,820 --> 00:13:19,370 en annan resurs som vi kan mäta. 269 00:13:19,370 --> 00:13:23,610 Vi ska försöka att basera våra analyser om bara de grundläggande funktionerna, de som, 270 00:13:23,610 --> 00:13:25,930 ärligt talat, att du kan se mest visuellt. 271 00:13:25,930 --> 00:13:30,700 Så med något i stil med stort O n kvadrat, jag hävdar att O n kvadrat 272 00:13:30,700 --> 00:13:35,820 är en övre gräns för den så kallade gångtid bubbla slag. 273 00:13:35,820 --> 00:13:38,820 Med andra ord, om du ville påstå att det finns 274 00:13:38,820 --> 00:13:41,370 denna övre gräns för hur många steg en algoritm kan ta, 275 00:13:41,370 --> 00:13:46,240 det kommer att vara i den stora O n kvadrat i detta fall, en övre gräns. 276 00:13:46,240 --> 00:13:49,710 >> Vad händer om jag ändrar i stället för historia att vara inte om bubbla sortera, 277 00:13:49,710 --> 00:13:50,910 men om denna övre gräns. 278 00:13:50,910 --> 00:13:54,030 Kan du komma på en algoritm att vi har tittat på redan 279 00:13:54,030 --> 00:13:59,530 vars övre gräns, maximalt mäta tid eller verksamhet, 280 00:13:59,530 --> 00:14:04,300 skulle sägas vara begränsad av n, en linjär funktion, 281 00:14:04,300 --> 00:14:07,260 inte en kvadratisk en som är böjd? 282 00:14:07,260 --> 00:14:10,780 Vad är en algoritm som alltid tar inte mer 283 00:14:10,780 --> 00:14:12,860 än som n steg, eller 2n steg, eller 3n steg? 284 00:14:12,860 --> 00:14:13,360 Yeah? 285 00:14:13,360 --> 00:14:15,030 >> PUBLIK: Att hitta största antalet i en lista? 286 00:14:15,030 --> 00:14:16,930 >> Speak: Perfect, hitta det största värdet i en lista. 287 00:14:16,930 --> 00:14:18,940 Om jag får en lista över människor till exempel, 288 00:14:18,940 --> 00:14:21,440 var och av vem som innehar ett nummer, vad som är det maximala antalet 289 00:14:21,440 --> 00:14:23,770 steg det ska ta mig, en någorlunda smart person, 290 00:14:23,770 --> 00:14:27,530 att hitta den största personen i listan? 291 00:14:27,530 --> 00:14:28,100 n, eller hur? 292 00:14:28,100 --> 00:14:31,320 Därför att i det värsta fallet, där kanske den största värdet vara? 293 00:14:31,320 --> 00:14:32,700 Höger, hela vägen i slutet. 294 00:14:32,700 --> 00:14:34,575 Så i värsta fall övre gräns, kanske jag 295 00:14:34,575 --> 00:14:36,450 måste gå hela vägen hit och bli som, 296 00:14:36,450 --> 00:14:39,170 åh, här är nummer åtta, eller vad värdet är. 297 00:14:39,170 --> 00:14:41,330 Nu skulle det bara vara dumt om jag höll på, eller hur? 298 00:14:41,330 --> 00:14:43,840 Söker fler och fler element om den sista av dem är borta? 299 00:14:43,840 --> 00:14:45,340 Så säkert är n en övre gräns. 300 00:14:45,340 --> 00:14:47,420 Jag behöver inte ta fler steg än så. 301 00:14:47,420 --> 00:14:51,580 >> Så vad händer om i stället jag föreslog att Det finns algoritmer i världen som 302 00:14:51,580 --> 00:14:57,750 har en gångtid som är avgränsas av stora O i log n, log n? 303 00:14:57,750 --> 00:15:00,390 Där har vi sett det här förut? 304 00:15:00,390 --> 00:15:00,890 Yeah? 305 00:15:00,890 --> 00:15:03,309 >> PUBLIK: I telefonboken problemet? 306 00:15:03,309 --> 00:15:04,850 Speak: Som telefonboken problemet. 307 00:15:04,850 --> 00:15:07,754 Vad var mått på hur mycket tid eller hur många tårar det 308 00:15:07,754 --> 00:15:10,170 tog mig att hitta någon som Mike Smith i telefonboken? 309 00:15:10,170 --> 00:15:13,212 Vi hävdade att det var log n, och även om obekant eller så är det 310 00:15:13,212 --> 00:15:15,170 lite oklar vad en logaritm eller exponent var, 311 00:15:15,170 --> 00:15:17,650 kom bara ihåg att log n i allmänhet hänvisar till processen, 312 00:15:17,650 --> 00:15:20,790 i det här fallet, att dela något i halv igen, och igen, 313 00:15:20,790 --> 00:15:25,790 och igen, och igen, så att den blir allt mindre när du gör det. 314 00:15:25,790 --> 00:15:28,470 >> Så log n avser, säker, i telefonboken exempel 315 00:15:28,470 --> 00:15:32,662 till binär sökning i teorin, när vi hade de virtuella dörrarna på tavlan, 316 00:15:32,662 --> 00:15:34,370 eller när Sean var söker efter något. 317 00:15:34,370 --> 00:15:37,374 Om han hade använt binär sökning, log n skulle vara den övre gränsen för hur mycket 318 00:15:37,374 --> 00:15:38,040 tid det tar. 319 00:15:38,040 --> 00:15:44,027 Men de algoritmer som sprang in logga n antas vilka nyckel detalj? 320 00:15:44,027 --> 00:15:45,360 Att listan sorterades, eller hur? 321 00:15:45,360 --> 00:15:47,789 Din algoritm är fel om din ingång är inte sorterade, 322 00:15:47,789 --> 00:15:49,830 och ändå du använder något liknande binär sökning 323 00:15:49,830 --> 00:15:51,704 eftersom du kan hoppa rätt över elementet 324 00:15:51,704 --> 00:15:53,600 utan att inse att det är faktiskt där. 325 00:15:53,600 --> 00:15:55,600 >> Nu vad kan detta innebära, stort O i en? 326 00:15:55,600 --> 00:15:59,117 Detta betyder inte att din algoritm tar en och endast ett steg, 327 00:15:59,117 --> 00:16:01,200 det betyder bara att det tar en konstant antal steg. 328 00:16:01,200 --> 00:16:04,060 Kanske är det en, kanske är det 10, kanske 1.000, 329 00:16:04,060 --> 00:16:07,750 men det är oberoende av storleken på problemet. 330 00:16:07,750 --> 00:16:10,850 Oavsett hur stor n är, en konstant tid algoritm 331 00:16:10,850 --> 00:16:12,747 alltid tar samma antal steg. 332 00:16:12,747 --> 00:16:15,080 Så vad kan vara en algoritm Vi har pratat om eller bara 333 00:16:15,080 --> 00:16:20,418 intuitivt som kommer till dig att alltid körs i så kallad konstant tid? 334 00:16:20,418 --> 00:16:20,918 Yeah? 335 00:16:20,918 --> 00:16:22,001 >> PUBLIK: Lägg två nummer. 336 00:16:22,001 --> 00:16:25,320 Speak: Lägg två nummer, 2 plus 2 är lika med 4, gjort. 337 00:16:25,320 --> 00:16:27,227 Så det kan fungera, vad annars? 338 00:16:27,227 --> 00:16:28,560 Vad sägs om mer verkliga världen, ja? 339 00:16:28,560 --> 00:16:30,686 >> PUBLIK: Att hitta först på en lista. 340 00:16:30,686 --> 00:16:32,810 Speak: Att hitta den första element i en lista, visst. 341 00:16:32,810 --> 00:16:34,540 Vi har faktiskt pratat om arrayer redan, 342 00:16:34,540 --> 00:16:36,540 hur får man på första element i en array, 343 00:16:36,540 --> 00:16:40,465 oavsett hur länge den array är i C-kod? 344 00:16:40,465 --> 00:16:43,090 Du använder precis som konsolen noll notation, bam, du är där. 345 00:16:43,090 --> 00:16:46,120 Och faktiskt matriser, som en sidoreplik, stöd något allmänt känt 346 00:16:46,120 --> 00:16:49,240 som random access, random access minne, eftersom du kan bokstavligen 347 00:16:49,240 --> 00:16:50,284 hoppa till något ställe. 348 00:16:50,284 --> 00:16:52,700 Vi kan göra detta ännu enklare vi kan spola tillbaka till vecka noll 349 00:16:52,700 --> 00:16:53,900 när vi gjorde Scratch. 350 00:16:53,900 --> 00:16:59,707 Hur lång tid tog det för säger blocket i Scratch att köra? 351 00:16:59,707 --> 00:17:00,790 Bara konstant tid, eller hur? 352 00:17:00,790 --> 00:17:03,960 Säg något, säger någonting, det spelar ingen roll 353 00:17:03,960 --> 00:17:07,359 hur stora Repor världen är, är det alltid kommer att ta lika lång tid 354 00:17:07,359 --> 00:17:08,490 att helt enkelt säga något. 355 00:17:08,490 --> 00:17:11,089 >> Så det är konstant tid, men vad är baksidan? 356 00:17:11,089 --> 00:17:13,030 Om det var över bounds, tänk om vi vill 357 00:17:13,030 --> 00:17:17,089 att beskriva de undre gränser av våra algoritmer gångtid? 358 00:17:17,089 --> 00:17:19,852 Nästan en bästa fall potentiellt, om ni så vill, 359 00:17:19,852 --> 00:17:23,060 om dessa villkor kan gälla för bästa fall, värsta fall genomsnittliga fall mer 360 00:17:23,060 --> 00:17:26,359 allmänhet, men låt oss bara fokusera på undre gränser mer allmänt. 361 00:17:26,359 --> 00:17:31,920 Vad är en algoritm som har en lägre gräns för n steg, 362 00:17:31,920 --> 00:17:33,350 eller 2n steg, eller 3n steg? 363 00:17:33,350 --> 00:17:36,241 Några faktor av n steg, det är dess nedre gräns. 364 00:17:36,241 --> 00:17:36,740 Yeah? 365 00:17:36,740 --> 00:17:37,910 >> PUBLIK: Bubble sort? 366 00:17:37,910 --> 00:17:41,610 >> Speak: Bubble sort tar du minimalt n steg, varför? 367 00:17:41,610 --> 00:17:42,279 Varför det? 368 00:17:42,279 --> 00:17:45,320 Varför skulle det börjar att komma till dig intuitivt, inte ens om det gör bara 369 00:17:45,320 --> 00:17:46,530 än? 370 00:17:46,530 --> 00:17:47,030 Yeah? 371 00:17:47,030 --> 00:17:47,990 >> PUBLIK: [ohörbart]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 Speak: Exakt. 374 00:17:52,360 --> 00:17:55,810 I bästa möjliga scenariot bubbla sortera, och en hel del algoritmer, 375 00:17:55,810 --> 00:17:58,769 om jag lämnar er åtta personer som redan är sorterade, 376 00:17:58,769 --> 00:18:00,560 det vore dumt för dig, algoritmen, 377 00:18:00,560 --> 00:18:02,202 att gå fram och tillbaka mer än en gång, eller hur? 378 00:18:02,202 --> 00:18:04,285 Därför att så fort du gå igenom listan en gång, 379 00:18:04,285 --> 00:18:08,090 du bör inse, åh, jag gjorde inget swappar, är den här listan sorteras, utgång. 380 00:18:08,090 --> 00:18:09,700 Men det kommer att ta dig n steg. 381 00:18:09,700 --> 00:18:12,033 >> Och omvänt, vad är en annan sätt att tänka på det? 382 00:18:12,033 --> 00:18:15,240 Bubble sort är en omega, så att säga, av n, 383 00:18:15,240 --> 00:18:19,050 för om man tittar på färre än n element, vad 384 00:18:19,050 --> 00:18:23,009 är den grundläggande frågan där? 385 00:18:23,009 --> 00:18:24,550 Du vet inte om det sorteras, höger. 386 00:18:24,550 --> 00:18:26,800 Vi människor kanske blick på åtta människor och vara som, åh, det sorteras, 387 00:18:26,800 --> 00:18:28,430 det tog mig inte n steg, men det gjorde det. 388 00:18:28,430 --> 00:18:30,810 Dina ögon, även om du snäll i har ett stort synfält, 389 00:18:30,810 --> 00:18:33,184 du tittat på åtta element, du tittat på åtta personer, 390 00:18:33,184 --> 00:18:34,610 det är åtta steg effektivt. 391 00:18:34,610 --> 00:18:38,612 Och bara om jag gå igenom hela Listan gör jag inser, ja, sortering. 392 00:18:38,612 --> 00:18:41,320 Om jag stannar halvvägs tänka, allt rätt, det är ganska sorteras hittills, 393 00:18:41,320 --> 00:18:42,520 vad är oddsen att det inte är sorterade? 394 00:18:42,520 --> 00:18:44,186 Det algoritmer kommer inte att vara korrekt. 395 00:18:44,186 --> 00:18:46,250 Kan vara snabbare, men felaktig. 396 00:18:46,250 --> 00:18:48,500 >> Så nu har vi ett sätt att beskriver en undre gränser, 397 00:18:48,500 --> 00:18:49,710 och hur är det konstant tid? 398 00:18:49,710 --> 00:18:54,565 Vad är en algoritm som har en lägre bunden på sin speltid på en? 399 00:18:54,565 --> 00:18:58,350 1 steg 2 steg, 10 steg, men konstant, oberoende av n, 400 00:18:58,350 --> 00:18:59,310 storleken på den ingående? 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 >> PUBLIK: Printf? 404 00:19:05,309 --> 00:19:06,183 Speak: Vad är det? 405 00:19:06,183 --> 00:19:07,184 PUBLIK: Printf? 406 00:19:07,184 --> 00:19:07,850 Speak: Printf. 407 00:19:07,850 --> 00:19:08,400 OK, visst. 408 00:19:08,400 --> 00:19:10,720 Så det tar ett fast antal steg. 409 00:19:10,720 --> 00:19:13,170 Och jag bör nu-- nu vi pratar om C-kod 410 00:19:13,170 --> 00:19:16,040 och inte Scratch, något liknande säg, med printf, 411 00:19:16,040 --> 00:19:17,710 Vi borde börja få försiktig. 412 00:19:17,710 --> 00:19:21,090 Eftersom printf tar ingång, det är en sträng, 413 00:19:21,090 --> 00:19:23,220 och stråkar har tekniskt längd. 414 00:19:23,220 --> 00:19:25,530 Så om vi nu vill plocka på dig, om du inte har något emot, 415 00:19:25,530 --> 00:19:29,430 tekniskt vi skulle kunna hävda att printf tar en input variabel längd, 416 00:19:29,430 --> 00:19:32,270 och säkert det kan ta mer tid att skriva ut en sträng så här länge, 417 00:19:32,270 --> 00:19:33,560 än så länge. 418 00:19:33,560 --> 00:19:36,570 >> Så vad händer om vi anser bara sortering och sökning exempel? 419 00:19:36,570 --> 00:19:40,450 Hur är det med Mike Smith i telefonen bok, eller binär sökning mer allmänt? 420 00:19:40,450 --> 00:19:42,220 I bästa fall, vad som kan hända? 421 00:19:42,220 --> 00:19:45,577 Jag öppnar telefonboken och, bam, det är Mike Smiths nummer. 422 00:19:45,577 --> 00:19:46,660 Jag kan ringa honom direkt. 423 00:19:46,660 --> 00:19:49,390 >> Tog ett steg, kanske två steg, men ett konstant antal steg 424 00:19:49,390 --> 00:19:50,230 om jag hade tur. 425 00:19:50,230 --> 00:19:52,570 Och ärligt talat, vi såg på Måndag din klasskompis 426 00:19:52,570 --> 00:19:54,710 få ganska tur två gånger i rad. 427 00:19:54,710 --> 00:19:57,050 Och det var faktiskt konstant gången på undre gränser 428 00:19:57,050 --> 00:20:01,280 på algoritmen i fråga för att hitta Antalet 50 bakom de stängda 429 00:20:01,280 --> 00:20:01,830 dörrar. 430 00:20:01,830 --> 00:20:06,400 >> Nu, som en sidoreplik, om du upptäcker att både stora O, den övre gränsen, 431 00:20:06,400 --> 00:20:09,310 och omega, den nedre gränsen, är en i samma, att 432 00:20:09,310 --> 00:20:11,830 är samma formel i parenteser, kan du också 433 00:20:11,830 --> 00:20:15,170 säger, bara för att vara snygga, att något är i theta 434 00:20:15,170 --> 00:20:18,270 av n eller teta av ett annat värde. 435 00:20:18,270 --> 00:20:20,661 Det betyder bara när stora O och omega är samma. 436 00:20:20,661 --> 00:20:21,910 Nu vad om val slag? 437 00:20:21,910 --> 00:20:23,400 Låt oss använda detta nya vokabulär. 438 00:20:23,400 --> 00:20:27,407 I urvalet sortera, vad var vi göra igen, och igen, och igen? 439 00:20:27,407 --> 00:20:29,990 Jag tänkte fram och tillbaka genom listan, letar efter vem? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Det minsta antalet. 442 00:20:34,730 --> 00:20:37,560 >> Så hur många steg, hur många jämförelser jag gjorde 443 00:20:37,560 --> 00:20:43,250 måste göra för att lista ut vem det minsta elementet i listan är den? 444 00:20:43,250 --> 00:20:44,437 n minus 1, eller hur? 445 00:20:44,437 --> 00:20:47,770 För om jag bara börja med den jag är ges och jag börjar jämföra honom eller henne, 446 00:20:47,770 --> 00:20:49,519 då honom eller henne, honom eller henne, honom eller henne, jag 447 00:20:49,519 --> 00:20:52,010 kan bara koppla ihop element tillsammans n minus 1 gånger. 448 00:20:52,010 --> 00:20:55,630 Så val tar sorterings liknande n minus 1 steg första gången. 449 00:20:55,630 --> 00:20:59,540 >> Hur många steg tar det mig till hitta den näst minsta elementet? 450 00:20:59,540 --> 00:21:02,920 n minus 2, eftersom jag är att vara dum Om jag fortsätter att titta på samma personer 451 00:21:02,920 --> 00:21:06,280 igen om jag har redan valt honom eller henne och sätta dem i deras ställe. 452 00:21:06,280 --> 00:21:09,270 Och det tredje steget, n minus 3, då n minus 4. 453 00:21:09,270 --> 00:21:11,020 Vi har sett detta mönster innan, och faktiskt 454 00:21:11,020 --> 00:21:13,460 urval sortera på liknande har en övre gräns 455 00:21:13,460 --> 00:21:16,210 n kvadrat om vi gör upp det summering. 456 00:21:16,210 --> 00:21:19,790 Vad är dess nedre gräns, val slag? 457 00:21:19,790 --> 00:21:25,350 Minimalt, hur mycket tid måste val sorterings tar, som vi definierat det på måndag? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Föreslå två alternativ. 460 00:21:30,490 --> 00:21:32,360 Kanske är det n, som tidigare. 461 00:21:32,360 --> 00:21:35,040 Kanske är det n kvadrat, eftersom det är nu som den övre gränsen. 462 00:21:35,040 --> 00:21:35,874 >> PUBLIK: n kvadrat. 463 00:21:35,874 --> 00:21:36,664 Speak: n kvadrat. 464 00:21:36,664 --> 00:21:37,368 Varför? 465 00:21:37,368 --> 00:21:40,060 >> PUBLIK: Eftersom du har att definiera [ohörbart]. 466 00:21:40,060 --> 00:21:41,510 >> Speak: Exakt. 467 00:21:41,510 --> 00:21:45,077 Åtminstone som jag definierat val Sortera det var ganska naivt, fortsätt, 468 00:21:45,077 --> 00:21:46,160 hitta det minsta elementet. 469 00:21:46,160 --> 00:21:47,770 Gå igen, hitta den minsta elementet. 470 00:21:47,770 --> 00:21:49,490 Gå igen, hitta den minsta elementet. 471 00:21:49,490 --> 00:21:51,700 Det finns ingen typ av optimering där som 472 00:21:51,700 --> 00:21:54,350 skulle låta mig avbryta efter bara n eller så steg. 473 00:21:54,350 --> 00:21:57,080 Så ja, val sortera, omega n kvadrat. 474 00:21:57,080 --> 00:22:00,667 >> Hur är insättnings sortera, där jag tog vem jag fick, och sedan jag plopped honom 475 00:22:00,667 --> 00:22:01,750 eller henne på rätt plats? 476 00:22:01,750 --> 00:22:04,958 Sen fortsatte jag att den andra personen, plopped honom eller henne på rätt plats. 477 00:22:04,958 --> 00:22:07,910 Sedan nästa person, plopped honom eller henne på rätt plats. 478 00:22:07,910 --> 00:22:10,537 Lägg märke till att detta är mycket linjär, så att säga. 479 00:22:10,537 --> 00:22:12,620 Jag är en rak linje, jag är inte går fram och tillbaka, 480 00:22:12,620 --> 00:22:16,080 Jag har aldrig ser tillbaka riktigt, men vad som händer när jag sätter honom 481 00:22:16,080 --> 00:22:20,302 eller henne i början av listan som vi gjorde i måndags? 482 00:22:20,302 --> 00:22:21,010 Vad händer? 483 00:22:21,010 --> 00:22:21,510 Yeah? 484 00:22:21,510 --> 00:22:23,122 PUBLIK: [ohörbart]. 485 00:22:23,122 --> 00:22:24,830 Speak: Ja, det var fångsten, eller hur? 486 00:22:24,830 --> 00:22:26,746 Du kanske kommer ihåg från dina klasskamrater, om de 487 00:22:26,746 --> 00:22:29,670 gjorde någon rörelse med fötterna, det var en operation. 488 00:22:29,670 --> 00:22:33,610 Så om det var tre personer här och den nya personen tillhörde väg dit, 489 00:22:33,610 --> 00:22:37,360 på en lång etapp så här, visst, han eller hon kan bara gå in i det sista. 490 00:22:37,360 --> 00:22:40,074 Men om vi tänker på ett dator och en matris med minne, 491 00:22:40,074 --> 00:22:41,990 Dessa människor kommer att behöva blanda över 492 00:22:41,990 --> 00:22:43,260 för att göra plats för den personen. 493 00:22:43,260 --> 00:22:46,930 Och så att n minus en shufflings, n minus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 minus 3 shufflings är bara typ av händer bakom mig, inte framför mig 495 00:22:50,660 --> 00:22:52,710 som tidigare, i någon mening. 499 00:22:52,557 --> 00:22:54,640 Nu som en sidoreplik, och som du kanske har sett på nätet 500 00:22:54,640 --> 00:22:57,699 om du börjar peta runt om sorterar, det finns så många olika listor 501 00:22:57,699 --> 00:22:59,490 där ute, en del av dem bättre än andra. 502 00:22:59,490 --> 00:23:02,200 Faktum är bogosort en det är ganska kul att se upp. 503 00:23:02,200 --> 00:23:06,650 Bogosort tar en uppsättning av siffror eller säga en kortlek, 504 00:23:06,650 --> 00:23:09,870 slumpmässigt blandar dem, och kontrollerar om de är sorterade. 505 00:23:09,870 --> 00:23:12,130 Och om inte, gör det igen. 506 00:23:12,130 --> 00:23:14,140 Och om inte, gör det igen. 507 00:23:14,140 --> 00:23:15,440 Om inte, gör det igen. 508 00:23:15,440 --> 00:23:17,060 Otroligt dumt. 509 00:23:17,060 --> 00:23:19,520 >> Och faktiskt, om du läser gillar den Wikipedia artikeln, 510 00:23:19,520 --> 00:23:21,200 dess smeknamn är dum sort. 511 00:23:21,200 --> 00:23:25,180 Det kommer så småningom att fungera, förhoppningsvis får tillräckligt med tid, 512 00:23:25,180 --> 00:23:28,240 men den mängd av tid kan ta ganska lång tid. 513 00:23:28,240 --> 00:23:31,650 Så om jag kunde, låt oss hastighet saker upp från Mary Beths exempel tidigare, 514 00:23:31,650 --> 00:23:35,150 genom att ha några fler element, men två fler processorer. 515 00:23:35,150 --> 00:23:37,100 Två personer, om du skulle inte ha något emot att gå med mig. 516 00:23:37,100 --> 00:23:40,972 Vad sägs om en hit, och låt oss go-- ingen där borta? 517 00:23:40,972 --> 00:23:41,722 Ingen där borta? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 Du med den svarta skjorta, ja, kom ner. 520 00:23:44,190 --> 00:23:45,000 Okej, vad heter du? 521 00:23:45,000 --> 00:23:45,720 >> PUBLIKEN: Peter. 522 00:23:45,720 --> 00:23:46,100 >> Speak: Vad är det? 523 00:23:46,100 --> 00:23:46,766 >> PUBLIKEN: Peter. 524 00:23:46,766 --> 00:23:49,450 Speak: Peter, David, trevligt att träffas. 525 00:23:49,450 --> 00:23:53,670 Okej, vi har Peter här, om du vill komma på bordet här. 526 00:23:53,670 --> 00:23:54,550 Och vad heter du? 527 00:23:54,550 --> 00:23:55,216 >> PUBLIKEN: Elena. 528 00:23:55,216 --> 00:23:55,970 Speak: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, trevligt att träffas. 530 00:23:57,030 --> 00:23:58,060 Elena träffa Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 Och vi behöver Andrew upp här också, tack. 533 00:24:02,290 --> 00:24:06,107 Och din utmaning går vara att sortera en kortlek. 534 00:24:06,107 --> 00:24:08,190 Och om obekanta, däck av kort bör slutligen 535 00:24:08,190 --> 00:24:11,064 sorteras lite något liknande här vi ska göra klubbarna, då 536 00:24:11,064 --> 00:24:13,660 spadarna, då hjärtan och diamanter, från ess som en, 537 00:24:13,660 --> 00:24:15,570 hela vägen upp till kungen. 538 00:24:15,570 --> 00:24:20,890 >> Korten Jag ska ge dig kommer att vara 52 i kvantitet. 539 00:24:20,890 --> 00:24:23,160 Vi ska på samma sätt gång du, på bara ett ögonblick. 540 00:24:23,160 --> 00:24:26,410 Vi ska kasta Andrew upp på skärmen här, 541 00:24:26,410 --> 00:24:28,170 för att titta på när du gör detta. 542 00:24:28,170 --> 00:24:31,070 Och så att allt detta är desto mer synliga, 543 00:24:31,070 --> 00:24:33,490 dessa är de kort jag fick på Amazon. 544 00:24:33,490 --> 00:24:42,861 Så de är redan slumpmässigt sorteras, och vi kommer att tajma dig. 545 00:24:42,861 --> 00:24:44,610 Och vi ska hålla det riktigt den här gången, 546 00:24:44,610 --> 00:24:47,820 så vi kommer att försöka pressa dig för annars kommer detta att få tråkiga 547 00:24:47,820 --> 00:24:48,460 snabbt. 548 00:24:48,460 --> 00:24:53,860 Om du kunde gå vidare för att sortera 52 elementen via något sätt, nu. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> Och återigen, när vi tittar på dessa killar gör vad, till slut 551 00:25:07,180 --> 00:25:10,200 kommer att producera en uppenbar resultat, tänk på riktigt 552 00:25:10,200 --> 00:25:12,962 hur de var och att göra det, hur du kan beskriva det. 553 00:25:12,962 --> 00:25:15,045 Eftersom igen, dessa är alla processer, algoritmer 554 00:25:15,045 --> 00:25:17,090 som vi tar för givet som en människa. 555 00:25:17,090 --> 00:25:22,349 Men du har antagligen länge haft intuition, långt innan du ens 556 00:25:22,349 --> 00:25:24,390 tänkte på att ta en datavetenskap klass du 557 00:25:24,390 --> 00:25:27,223 kan ha haft på intuition med för att lösa problem som detta. 558 00:25:27,223 --> 00:25:29,560 Men när du känner igen mönstren och börja 559 00:25:29,560 --> 00:25:32,407 att formalisera stegen med vilka du lösa dessa problem, 560 00:25:32,407 --> 00:25:35,490 du kommer att upptäcka att du kan lösa mycket mer intressant och mycket mer komplex 561 00:25:35,490 --> 00:25:39,190 problemen snabbt. 562 00:25:39,190 --> 00:25:42,351 Så någon från publiken, det som är åtminstone en del av algoritmen 563 00:25:42,351 --> 00:25:43,350 att de använder här? 564 00:25:43,350 --> 00:25:44,275 >> PUBLIK: [ohörbart] 565 00:25:44,275 --> 00:25:45,150 Speak: Vad är det? 566 00:25:45,150 --> 00:25:47,062 PUBLIK: Genom kostym. 567 00:25:47,062 --> 00:25:47,770 Speak: Med kostym. 568 00:25:47,770 --> 00:25:50,630 Så först de klustring alla diamanter tillsammans 569 00:25:50,630 --> 00:25:52,560 det verkar, alla av hjärtan ihop det verkar, 570 00:25:52,560 --> 00:25:56,520 och så vidare, utan respekt för de nummer på korten. 571 00:25:56,520 --> 00:26:00,900 Och nu verkar det, till exempel, att sortera dem i antal. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Mycket bra. 574 00:26:08,910 --> 00:26:12,370 >> Okej, så vad som kommer att vara det sista steget då här? 575 00:26:12,370 --> 00:26:16,950 När vi har fyra sorterade kostymer, vad behöver vi göra för att de fyra högarna 576 00:26:16,950 --> 00:26:20,059 i syfte att uppnå en sorterade däck, helt enkelt? 577 00:26:20,059 --> 00:26:21,350 Så vi måste slå ihop dem igen. 578 00:26:21,350 --> 00:26:25,160 >> Så det är en intressant idé som igen, förmodar, är mycket intuitivt och med 579 00:26:25,160 --> 00:26:28,140 om du kanske aldrig har smällde den typen av etikett på den. 580 00:26:28,140 --> 00:26:31,900 Denna grundläggande begreppet dela problemet inte i halv denna tid, 581 00:26:31,900 --> 00:26:33,410 men åtminstone i fyra bitar. 582 00:26:33,410 --> 00:26:36,810 Lösa ganska mycket i grunden identiska problem 583 00:26:36,810 --> 00:26:40,480 i isolering av varandra, och sedan slå ihop resultaten. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 Och, utmärkt, gjort. 586 00:26:50,140 --> 00:26:52,140 Okej, en stor rund applåder, om vi kunde. 587 00:26:52,140 --> 00:26:56,480 >> [Applåder] 588 00:26:56,480 --> 00:26:59,740 >> Speak: Jag har ingen aning om vad du kommer göra med dessa, men här har du. 589 00:26:59,740 --> 00:27:01,690 Tack så mycket. 590 00:27:01,690 --> 00:27:04,660 Så låt oss se, två minuter och åtta sekunder, 591 00:27:04,660 --> 00:27:07,490 Om du vill utmana dina vänner. 592 00:27:07,490 --> 00:27:12,160 Vad är det då kommer att vara en ta bort från denna 593 00:27:12,160 --> 00:27:13,830 att vi kan utnyttja mer allmänt? 594 00:27:13,830 --> 00:27:16,080 Tja, tänker tillbaka på denna rad av siffror, 595 00:27:16,080 --> 00:27:19,060 och tänker tillbaka nu till några av de pseudokod vi har skrivit tidigare, 596 00:27:19,060 --> 00:27:22,080 och detta var pseudokod för lösa telefonboken problemet. 597 00:27:22,080 --> 00:27:25,150 Varvid i pseudokod I räknas ett mer metodiskt sätt 598 00:27:25,150 --> 00:27:28,400 att beskriva hur jag gjorde ett mycket intuitivt mänsklig algoritm för att dela upp telefonen 599 00:27:28,400 --> 00:27:31,650 bok i hälften, upprepa, upprepa, upprepa, tills jag hittar någon som Mike Smith, 600 00:27:31,650 --> 00:27:33,790 om han verkligen är i telefonboken. 601 00:27:33,790 --> 00:27:37,610 >> Men jag liksom använt vad jag ska kalla en mycket iterativ metod här, 602 00:27:37,610 --> 00:27:42,160 särskilt meddelande linje 8 och linjen 11. 603 00:27:42,160 --> 00:27:46,750 De vittnar om en iterativ strategi, en looping strategi, 604 00:27:46,750 --> 00:27:49,040 eftersom det är precis beteendet de inducerar. 605 00:27:49,040 --> 00:27:52,910 Dessa linjer både säga gå till linje tre, och du kan typ av 606 00:27:52,910 --> 00:27:55,140 tänker på det i din inre öga som en loop. 607 00:27:55,140 --> 00:27:59,080 Det säger åt dig att gå upp till steg tre och upprepa, igen, och igen, 608 00:27:59,080 --> 00:28:00,010 och igen. 609 00:28:00,010 --> 00:28:04,410 >> Men tänk om vi utnyttja en viktig idé här att vi gjorde inte sista gången, 610 00:28:04,410 --> 00:28:10,280 och förenkla linje 8 och linje 11 och deras grannar 611 00:28:10,280 --> 00:28:12,840 som just detta, i gult. 612 00:28:12,840 --> 00:28:16,480 Det är inte i grunden förkorta pseudokoden så mycket, 613 00:28:16,480 --> 00:28:20,530 men det är i grunden förändra arten av min algoritm. 614 00:28:20,530 --> 00:28:24,220 Vad jag säger nu i steg 7, i steg 10, 615 00:28:24,220 --> 00:28:29,140 är att söka efter Mike på exakt samma sätt, 616 00:28:29,140 --> 00:28:31,580 men bara i den vänstra hälften eller den högra halvan. 617 00:28:31,580 --> 00:28:33,420 >> Så med andra ord, om Jag börjar från steg ett, 618 00:28:33,420 --> 00:28:36,150 plocka upp telefonboken, öppen för mitten i telefonboken, titta på namn, 619 00:28:36,150 --> 00:28:39,010 Om Smith är bland heter, ring Mike, annars 620 00:28:39,010 --> 00:28:44,340 Om Smith är tidigare i boken, steg sju söka efter Mike i vänstra halvan av boken. 621 00:28:44,340 --> 00:28:47,130 Men denna typ av känns som det lämnar mig hängande, eller hur? 622 00:28:47,130 --> 00:28:49,240 I gult, är en undervisning, men hur gör jag 623 00:28:49,240 --> 00:28:51,870 söka efter Mike i det vänstra hälften av telefonboken? 624 00:28:51,870 --> 00:28:54,210 Var ska jag ha en algoritm som jag 625 00:28:54,210 --> 00:28:57,100 kan söka efter någon som Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Tja, det stirrar oss i ansiktet. 627 00:28:58,980 --> 00:29:03,090 Jag kan bokstavligen använda exakt samma program på ett effektivt sätt att gå upp till toppen 628 00:29:03,090 --> 00:29:06,490 åter och åter igång samma kodrader. 629 00:29:06,490 --> 00:29:10,610 >> Så även om det här ska känna som lite av en cyklisk definition 630 00:29:10,610 --> 00:29:13,480 var du svara någons fråga genom att bara sorts fråga 631 00:29:13,480 --> 00:29:15,990 samma fråga igen, som varför, varför, varför? 632 00:29:15,990 --> 00:29:21,580 Verkligheten är att vi har hårt kodat några speciella linjer, steg 4, 633 00:29:21,580 --> 00:29:25,320 vilket är en om, och steg 12, vilket är ett effektivt sätt en annan gren, 634 00:29:25,320 --> 00:29:30,120 eftersom vi har dessa stopgap åtgärder, denna algoritm kommer att upphöra om vi 635 00:29:30,120 --> 00:29:32,050 hitta Mike, eller om vi inte gör det. 636 00:29:32,050 --> 00:29:36,810 Men i steg 7 och 10 nu, vi har vad vi kallar en rekursiv algoritm. 637 00:29:36,810 --> 00:29:40,420 Och rekursion är verkligen en kraftfull idé som är lite sinne bockning i början, 638 00:29:40,420 --> 00:29:42,500 att vi nu kan tillämpas enligt följande. 639 00:29:42,500 --> 00:29:46,600 >> Merge sort blir den sista slag som vi tittar på, åtminstone i klass formellt. 640 00:29:46,600 --> 00:29:50,040 Och det är fundamentalt annorlunda från de tre sista, och definitivt 641 00:29:50,040 --> 00:29:52,140 senaste fyra om vi räknar bogosort. 642 00:29:52,140 --> 00:29:54,810 Här är pseudokod för sammanslagnings slag. 643 00:29:54,810 --> 00:30:00,170 När du är på ingång av n element, så med tanke på en matris av storlek n, om n är mindre än 2, 644 00:30:00,170 --> 00:30:01,040 tillbaka. 645 00:30:01,040 --> 00:30:03,610 Så varför har jag att sanity kontrollera först? 646 00:30:03,610 --> 00:30:09,477 Vad är konsekvenserna om jag lämna dig en array vars längd n är mindre än 2? 647 00:30:09,477 --> 00:30:11,060 Det är redan sorterade, uppenbarligen, eller hur? 648 00:30:11,060 --> 00:30:13,640 Eftersom listan har antingen ett element, som är trivialt 649 00:30:13,640 --> 00:30:15,180 sorteras för att det är det enda som finns. 650 00:30:15,180 --> 00:30:18,138 Eller är det för storlek noll, vilket innebär det finns inget att sortera, så av naturen 651 00:30:18,138 --> 00:30:18,720 den sorteras. 652 00:30:18,720 --> 00:30:20,410 Det finns bara inget fel där. 653 00:30:20,410 --> 00:30:22,310 Så det är vår så kallade referensscenariot. 654 00:30:22,310 --> 00:30:24,440 >> Det är i samma anda vad vi gjorde med Mike. 655 00:30:24,440 --> 00:30:26,023 Om Mike i telefonboken, kalla honom. 656 00:30:26,023 --> 00:30:27,740 Om han inte är där, ge upp. 657 00:30:27,740 --> 00:30:31,240 Det är en så kallad basfallet, för att se denna algoritm i slutet av dagen 658 00:30:31,240 --> 00:30:33,540 stannar under vissa omständigheter. 659 00:30:33,540 --> 00:30:37,890 >> Men här är steg i tro nu, annars, sortera den vänstra halvan av elementen, 660 00:30:37,890 --> 00:30:39,740 sedan sortera rätt hälften av elementen, 661 00:30:39,740 --> 00:30:41,189 och sedan slå samman de sorterade halvorna. 662 00:30:41,189 --> 00:30:43,230 Och här är där det känns som om vi copping ut. 663 00:30:43,230 --> 00:30:46,900 Jag har bett dig att sortera n element, och jag är 664 00:30:46,900 --> 00:30:50,712 ordstäv, OK, gör det genom att sortera vänster och sortera rätt. 665 00:30:50,712 --> 00:30:52,420 Men jag säger en annan sak, och detta 666 00:30:52,420 --> 00:30:55,530 är nyckeln temat verkar i intuition så här långt, 667 00:30:55,530 --> 00:30:57,380 Det är det här tredje steget att slå samman. 668 00:30:57,380 --> 00:31:00,430 Vilket även om det verkar så dum i anden, 669 00:31:00,430 --> 00:31:02,320 som bara samman saker tillsammans, verkar det 670 00:31:02,320 --> 00:31:05,380 att vara ett viktigt steg mot återmontering av två problem som 671 00:31:05,380 --> 00:31:07,330 delades slutligen i hälften. 672 00:31:07,330 --> 00:31:12,090 >> Så slå ihop sortera, låt oss göra detta, om du kommer blidka mig, med ytterligare en demonstration, 673 00:31:12,090 --> 00:31:14,730 bara så att vi har några siffror att arbeta med. 674 00:31:14,730 --> 00:31:19,470 Kan jag byta åtta stressen bollar för åtta personer? 675 00:31:19,470 --> 00:31:29,320 Okej, hur du tre, du fyra i detta avsnitt, fem, sex, och låt oss 676 00:31:29,320 --> 00:31:30,720 gör 7, 8, kom upp. 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, där går vi, plus 1. 680 00:31:38,640 --> 00:31:39,150 Utmärkt. 681 00:31:39,150 --> 00:31:42,000 Okej Kom fram, låt oss snabbt ge dig siffror. 682 00:31:42,000 --> 00:31:50,800 Nummer två, nummer tre, nummer fyra, nummer fem, sex, sju och åtta. 683 00:31:50,800 --> 00:31:52,140 Jag gjorde åtta rätt den här gången. 684 00:31:52,140 --> 00:31:56,390 >> OK, så sätt igång om du kunde, och Låt oss sortera i original ordning 685 00:31:56,390 --> 00:31:59,810 att vi hade igår som såg så här, om du inte skulle ha något emot. 686 00:31:59,810 --> 00:32:03,620 Och låt oss göra det framför bordet. 687 00:32:03,620 --> 00:32:06,510 Okej, så slå ihop sort. 688 00:32:06,510 --> 00:32:08,820 Det är här det händer att få typ av intressant, 689 00:32:08,820 --> 00:32:12,800 eftersom jag verkar vara att ge mig själv så mycket mindre information i dag. 690 00:32:12,800 --> 00:32:15,149 >> Så slå ihop slags först av allt på ingången av n element, 691 00:32:15,149 --> 00:32:18,440 och är naturligtvis inte mindre än två, det är åtta, så jag har lite mer arbete att göra. 692 00:32:18,440 --> 00:32:21,140 Så nu mentalt vi som en klass är nu i annan gren, 693 00:32:21,140 --> 00:32:22,540 vilket innebär tre steg. 694 00:32:22,540 --> 00:32:25,017 Först måste jag sortera vänstra halvan av elementen. 695 00:32:25,017 --> 00:32:26,350 Så hur gör jag för att göra detta? 696 00:32:26,350 --> 00:32:28,950 Tja, jag ska typ av mentalt dela upp listan här, 697 00:32:28,950 --> 00:32:30,700 du behöver inte fysiskt flytta, och jag är 698 00:32:30,700 --> 00:32:33,180 kommer att fokusera enbart på vänstra halvan av elementen här. 699 00:32:33,180 --> 00:32:36,770 Så hur gör jag för att sortera en lista nu över storlek fyra? 700 00:32:36,770 --> 00:32:38,730 Vad är min algoritm? 701 00:32:38,730 --> 00:32:42,580 Först jag kontrollera är n mindre än två, nej, så jag går vidare till annat blocket igen. 702 00:32:42,580 --> 00:32:43,900 Sortera vänstra halvan av element. 703 00:32:43,900 --> 00:32:45,608 >> Så nu igen, mentalt, och det är där 704 00:32:45,608 --> 00:32:49,550 du måste samla en massa mental historia, om man så vill. 705 00:32:49,550 --> 00:32:51,940 Nu ska jag sortera vänster hälften av den vänstra halvan. 706 00:32:51,940 --> 00:32:57,000 Okej, så nu kallar jag mitt samma merge sorteringsalgoritm är n mindre än två? 707 00:32:57,000 --> 00:33:00,590 Nej, det är två, så jag måste sortera den vänstra halvan, och den högra halvan. 708 00:33:00,590 --> 00:33:02,042 Så här går vi, sortera den vänstra halvan. 709 00:33:02,042 --> 00:33:03,750 Varför inte bara ta ett steg framåt. 710 00:33:03,750 --> 00:33:04,415 Vad heter du? 711 00:33:04,415 --> 00:33:04,860 >> PUBLIKEN: Darren. 712 00:33:04,860 --> 00:33:05,260 >> Speak: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan har klivit fram. 714 00:33:06,040 --> 00:33:06,748 >> PUBLIKEN: Darren. 715 00:33:06,748 --> 00:33:09,000 Speak: Darren, gjort. 716 00:33:09,000 --> 00:33:10,090 Sa du Darren eller Dan? 717 00:33:10,090 --> 00:33:10,550 >> PUBLIKEN: Darren. 718 00:33:10,550 --> 00:33:11,216 >> Speak: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren har klivit framåt och han nu sorteras. 720 00:33:14,422 --> 00:33:16,130 Och det är nästan en inane påstående, eller hur? 721 00:33:16,130 --> 00:33:18,862 Jag vet inte riktigt verkar vara att uppnå något, men låt oss gå vidare. 722 00:33:18,862 --> 00:33:20,820 Låt mig nu sortera rätt halv av elementen. 723 00:33:20,820 --> 00:33:21,200 Vad heter du? 724 00:33:21,200 --> 00:33:21,690 >> PUBLIKEN: Luke. 725 00:33:21,690 --> 00:33:22,273 >> Speak: Luke. 726 00:33:22,273 --> 00:33:23,400 Kom igen, steg framåt. 727 00:33:23,400 --> 00:33:25,640 Klar, har jag sorterat Luke. 728 00:33:25,640 --> 00:33:28,570 Den vänstra halvan är nu sorteras och den högra halvan är nu sorteras, 729 00:33:28,570 --> 00:33:30,770 men återigen, det är ett viktigt steg här. 730 00:33:30,770 --> 00:33:32,940 Vad behöver jag nästa behöver göra? 731 00:33:32,940 --> 00:33:33,941 Slå ihop de sorterade halvorna. 732 00:33:33,941 --> 00:33:36,648 Nu ska vi bara ha alla fram och tillbaka på det sättet, 733 00:33:36,648 --> 00:33:38,620 eftersom jag slags behov del ett utrymme. 734 00:33:38,620 --> 00:33:40,411 Det är nästan som dessa killar är på ett bord, 735 00:33:40,411 --> 00:33:42,460 och jag behöver lite utrymme att flytta runt dem på. 736 00:33:42,460 --> 00:33:44,170 Så jag ska gå samman ni genom att titta 737 00:33:44,170 --> 00:33:45,960 på den vänstra halvan och den högra halvan. 738 00:33:45,960 --> 00:33:48,740 Och som uppenbarligen kommer först, vänstra halvan eller högra halvan? 739 00:33:48,740 --> 00:33:52,710 Så högra halvan, så låt oss gå Luke över här för att Darren ursprungliga ståndpunkt. 740 00:33:52,710 --> 00:33:57,640 Och nu att slå samman sina vänstra halvan i, Darren kommer att röra sig där. 741 00:33:57,640 --> 00:33:59,750 >> Så känns nästan en bubbla sorteringseffekt, 742 00:33:59,750 --> 00:34:02,482 men min grundläggande algoritm, mycket annorlunda den här gången. 743 00:34:02,482 --> 00:34:04,815 Men nu börjar det bli en lite irriterande eftersom du 744 00:34:04,815 --> 00:34:06,810 måste spola tillbaka mentalt där lämnade jag av. 745 00:34:06,810 --> 00:34:09,893 Jag har precis slagits samman de sorterade halvorna, vilket betyder att jag var i min algoritm? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Jag måste sortera den högra halvan, eller hur? 748 00:34:13,770 --> 00:34:15,910 >> Om du spola tillbaka, bokstavligen på videon, du ska 749 00:34:15,910 --> 00:34:18,339 se till att vi kom till denna punkt i Lukas och Darren 750 00:34:18,339 --> 00:34:21,370 genom att sortera vänster hälften av den vänstra halvan. 751 00:34:21,370 --> 00:34:23,430 Sedan vi gick samman de sorterat halvor, vilka 752 00:34:23,430 --> 00:34:27,941 innebär nästa steg är typ det högra halvan av den vänstra halvan. 753 00:34:27,941 --> 00:34:29,649 Okej, så låt oss göra detta snabbare. 754 00:34:29,649 --> 00:34:33,282 Okej, sex, kommer jag att hävda ni nu sorteras, kom fram. 755 00:34:33,282 --> 00:34:33,990 Vad heter du? 756 00:34:33,990 --> 00:34:34,589 >> PUBLIKEN: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> Speak: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano nu sorteras. 759 00:34:36,010 --> 00:34:36,450 Och vad heter du? 760 00:34:36,450 --> 00:34:37,080 >> PUBLIKEN: Alex. 761 00:34:37,080 --> 00:34:38,379 >> TALARE: Alex är nu sorteras. 762 00:34:38,379 --> 00:34:40,750 Vänster halv, högra halvan, vad är det sista steget? 763 00:34:40,750 --> 00:34:41,250 Merge. 764 00:34:41,250 --> 00:34:44,310 Ganska trivialt, så jag är kommer att gå samman i sex, 765 00:34:44,310 --> 00:34:46,930 ta ett steg tillbaka, åtta, ta ett steg tillbaka. 766 00:34:46,930 --> 00:34:49,530 Och nu märker att detta är en användbar takeaway, vad 767 00:34:49,530 --> 00:34:53,930 är nu sant om den vänstra halvan av lista, oavsett hur vi började? 768 00:34:53,930 --> 00:34:55,090 Det sorteras. 769 00:34:55,090 --> 00:34:57,750 >> Nu det inte sorteras i den stora tingens ordning, 770 00:34:57,750 --> 00:35:00,250 men den sorteras självständigt av den andra hälften. 771 00:35:00,250 --> 00:35:04,100 Nu vad steget är jag på om jag håller spola tillbaka hur historien började? 772 00:35:04,100 --> 00:35:05,680 Nu måste jag sortera den högra halvan. 773 00:35:05,680 --> 00:35:07,630 Så nu är vi tillbaka på I början av berättelsen, 774 00:35:07,630 --> 00:35:08,921 och låt oss göra detta snabbare. 775 00:35:08,921 --> 00:35:11,320 Så jag kommer att sortera högra halvan av hela listan. 776 00:35:11,320 --> 00:35:13,060 Vad är nästa steg? 777 00:35:13,060 --> 00:35:15,840 Sortera vänstra halvan av den högra halvan. 778 00:35:15,840 --> 00:35:18,715 Sortera vänstra halvan av vänstra halvan av den högra halvan. 779 00:35:18,715 --> 00:35:19,590 Och vad heter du? 780 00:35:19,590 --> 00:35:20,230 >> PUBLIKEN: Omar. 781 00:35:20,230 --> 00:35:21,970 >> Speak: Omar, steg framåt, gjort. 782 00:35:21,970 --> 00:35:22,860 Vänster halva sorteras. 783 00:35:22,860 --> 00:35:23,330 Och vad heter du? 784 00:35:23,330 --> 00:35:23,820 >> PUBLIKEN: Chris. 785 00:35:23,820 --> 00:35:25,620 >> Speak: Chris, ta ett steg framåt, du är nu sorteras. 786 00:35:25,620 --> 00:35:27,010 Vad är den viktigaste steget nu? 787 00:35:27,010 --> 00:35:27,510 Merge. 788 00:35:27,510 --> 00:35:30,509 Så man kommer att gå samman på plats Här, om du kunde ta ett steg tillbaka, 789 00:35:30,509 --> 00:35:32,930 och tre kommer att ta ett steg tillbaka, slå samman. 790 00:35:32,930 --> 00:35:38,080 Så den vänstra halvan av högra halvan, nu sorteras. 791 00:35:38,080 --> 00:35:41,747 Ärligt talat, denna algoritm känns som vi slösar mycket mer tid än tidigare, 792 00:35:41,747 --> 00:35:44,830 men om vi gjorde detta i realtid, vi ska se vad takeaways kommer att bli. 793 00:35:44,830 --> 00:35:47,970 Nu är jag här, rätt hälften av den högra halvan, 794 00:35:47,970 --> 00:35:50,170 Låt mig gå vidare och sortera den vänstra halvan. 795 00:35:50,170 --> 00:35:51,482 Steg framåt, vad heter du? 796 00:35:51,482 --> 00:35:52,190 PUBLIKEN: Ramsey. 797 00:35:52,190 --> 00:35:53,210 TALARE: Ramsey nu sorteras. 798 00:35:53,210 --> 00:35:53,570 Vad heter du? 799 00:35:53,570 --> 00:35:54,200 >> PUBLIKEN: Marina. 800 00:35:54,200 --> 00:35:57,033 >> TALARE: Marina nu sorteras som Tja, om du tar ett steg framåt. 801 00:35:57,033 --> 00:36:00,690 Nyckel steg här nu samman, jag är kommer att plocka från mina två listor, 802 00:36:00,690 --> 00:36:01,720 vänster och höger. 803 00:36:01,720 --> 00:36:05,150 Fem kommer att komma först, och sju kommer att komma härnäst. 804 00:36:05,150 --> 00:36:06,410 Och återigen, detta är avsiktlig. 805 00:36:06,410 --> 00:36:08,535 Det faktum att de tar steg framåt och bakåt 806 00:36:08,535 --> 00:36:12,997 är tänkt att representera att vi inte kan gör denna algoritm på plats som lätt 807 00:36:12,997 --> 00:36:15,830 som bubbla sortera och välja sortera, och insättning sortera där vi bara 808 00:36:15,830 --> 00:36:16,960 hålls byta folk. 809 00:36:16,960 --> 00:36:19,940 Jag behöver bokstavligen en sorts av scratch papper där 810 00:36:19,940 --> 00:36:21,827 att sätta dessa människor medan jag gör en sammanslagning, 811 00:36:21,827 --> 00:36:23,410 och sedan kan jag sätta dem på plats igen. 812 00:36:23,410 --> 00:36:27,260 Och det är nyckeln eftersom jag använder en ny resurs, utrymme, inte bara tid. 813 00:36:27,260 --> 00:36:28,270 >> OK, det här är fantastiskt. 814 00:36:28,270 --> 00:36:32,050 Vänster halva sorteras, högra halvan är sorterade, nu när nyckeln sammanslagning steg. 815 00:36:32,050 --> 00:36:33,450 Hur ska jag slå ihop det här? 816 00:36:33,450 --> 00:36:35,470 Så om du ska följa min vänster hand och höger hand, 817 00:36:35,470 --> 00:36:38,930 Jag kommer att peka min vänstra hand på den vänstra halvan, min högra hand 818 00:36:38,930 --> 00:36:42,680 på den högra halvan, och nu måste jag besluta steg för steg som att gå samman i. 819 00:36:42,680 --> 00:36:44,650 Som uppenbarligen kommer först? 820 00:36:44,650 --> 00:36:45,150 Nummer ett. 821 00:36:45,150 --> 00:36:47,327 Så kom den hit, Här är vår scratch pad. 822 00:36:47,327 --> 00:36:49,910 Så nu nummer ett, och varsel vad jag ska göra med min högra hand, 823 00:36:49,910 --> 00:36:54,152 Jag ska flytta min högra hand en steg över till punkt nummer tre, 824 00:36:54,152 --> 00:36:55,860 och nu måste jag göra samma beslut. 825 00:36:55,860 --> 00:36:58,387 Och faktiskt står rätt i framför Luke här om du kunde, 826 00:36:58,387 --> 00:36:59,720 eftersom detta är vår scratch pad. 827 00:36:59,720 --> 00:37:00,610 Så vem kommer härnäst? 828 00:37:00,610 --> 00:37:05,000 Vi har Lukas med nummer två eller Chris med nummer tre. 829 00:37:05,000 --> 00:37:07,460 Uppenbarligen Luke, antal två, så du kommer hit. 830 00:37:07,460 --> 00:37:11,270 >> Men min vänstra hand nu kommer att ökas för att peka på Darren, 831 00:37:11,270 --> 00:37:15,160 och här är nyckeln ta bort med sammanslagning, kommer jag att fortsätta att göra detta, 832 00:37:15,160 --> 00:37:17,340 självklart, om du snäll av följa logiken. 833 00:37:17,340 --> 00:37:19,670 Men mina händer är aldrig kommer att gå bakåt, 834 00:37:19,670 --> 00:37:23,861 vilket betyder att jag alltid bara flyttar till vänster med min sammanslagning process, 835 00:37:23,861 --> 00:37:26,360 och det kommer att vara nyckeln till att vår analys på bara ett ögonblick. 836 00:37:26,360 --> 00:37:27,859 >> Så nu ska vi avsluta detta snabbt. 837 00:37:27,859 --> 00:37:31,650 Så tre kommer nästa, sedan fyra kommer därnäst, 838 00:37:31,650 --> 00:37:38,750 och nu fem kommer nästa, sedan sex, och sju, och sedan slutligen åtta. 839 00:37:38,750 --> 00:37:42,960 Känns som den långsammaste algoritmen ännu, men inte om vi faktiskt 840 00:37:42,960 --> 00:37:45,510 kör den på samma sorts av klockhastighet, så att 841 00:37:45,510 --> 00:37:48,106 tala, med samma tickande klocka som tidigare. 842 00:37:48,106 --> 00:37:48,605 Varför? 843 00:37:48,605 --> 00:37:51,100 Nåväl, låt oss ta en titta på slutresultatet. 844 00:37:51,100 --> 00:37:56,990 >> Låt oss gå tillbaka hit, låt mig dra upp en demonstration visuellt 845 00:37:56,990 --> 00:37:59,030 av vad vi just gjorde. 846 00:37:59,030 --> 00:38:06,110 Zooma in här, på denna sida här, berättar Firefox 847 00:38:06,110 --> 00:38:08,200 att vi vill köa upp i den här rutan, låt oss 848 00:38:08,200 --> 00:38:11,260 säger bubbla sortera, med vilken Vi är nu väl bekant, 849 00:38:11,260 --> 00:38:14,130 urvals sortera, som är en annan ganska okomplicerad man, 850 00:38:14,130 --> 00:38:18,250 och nu dagens merge sort, som kommer att vara vår climactic slut. 851 00:38:18,250 --> 00:38:21,530 Anledningen till att det tog så mycket längre här med människor och mig verbalt är, 852 00:38:21,530 --> 00:38:23,480 självklart, jag förklarar varje steg. 853 00:38:23,480 --> 00:38:26,920 Men om du bara köra det här, mycket som vi gjorde bubbla sortera och urval 854 00:38:26,920 --> 00:38:30,890 sorterar inte bara visuellt, klocka hur mycket mer effektivt 855 00:38:30,890 --> 00:38:33,330 denna hävstångseffekt division och erövra 856 00:38:33,330 --> 00:38:39,150 kan när den tillämpas på en datamängd som är inte ens storlek åtta, men även mycket, 857 00:38:39,150 --> 00:38:39,970 mycket större. 858 00:38:39,970 --> 00:38:44,585 Jag ger dig samman sortera, sida vid sida med dessa andra algoritmer. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Det här kommer att bli smärtsamt snabbt, och sluttid 861 00:38:58,530 --> 00:39:00,890 är inte särskilt kulminerande, de bara sluta sortering. 862 00:39:00,890 --> 00:39:05,280 Men nyckeln ta bort är att ser hur mycket snabbare samman sorterings 863 00:39:05,280 --> 00:39:08,110 var, om du inte tror att jag är bara typ av jävlas med dig. 864 00:39:08,110 --> 00:39:13,100 Om vi ​​gör det här en sista gång, låt oss ladda om, låt oss gå tillbaka 865 00:39:13,100 --> 00:39:14,960 och välj bubbla sortera, och bara för sparkar, 866 00:39:14,960 --> 00:39:17,330 Låt oss välja insättnings sortera, bara för bra åtgärd. 867 00:39:17,330 --> 00:39:20,020 Och den här gången igen, låt oss välj merge sortera och låt oss 868 00:39:20,020 --> 00:39:21,595 faktiskt köra dessa sida vid sida. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> Och det är inte i själva verket en lyckträff. 871 00:39:26,930 --> 00:39:31,140 Vad jag har effektivt gjort är jag har indelat min input på mitten, igen, 872 00:39:31,140 --> 00:39:32,240 och igen, och igen. 873 00:39:32,240 --> 00:39:35,590 Och det finns bara så många gånger du kan dela upp din input i halvor, vänster 874 00:39:35,590 --> 00:39:36,240 och höger. 875 00:39:36,240 --> 00:39:39,425 Vad är formeln som vi håller ser som beskriver uppdelningen i hälften 876 00:39:39,425 --> 00:39:41,050 igen, och igen, och igen, och igen? 877 00:39:41,050 --> 00:39:41,890 >> PUBLIK: Logga n. 878 00:39:41,890 --> 00:39:42,760 >> Speak: Log n. 879 00:39:42,760 --> 00:39:46,300 Men sedan finns det en annan viktig åtgärd, denna algoritm är inte log n steg. 880 00:39:46,300 --> 00:39:48,992 Om det bara var log n steg, Vi skulle vara i samma problem 881 00:39:48,992 --> 00:39:51,200 som tidigare där vi inte kan vara att allt är sorterade. 882 00:39:51,200 --> 00:39:54,480 Du måste minimalt titta på n element att vara säker n elementen sorteras, 883 00:39:54,480 --> 00:39:55,950 annars är det ett steg i tro. 884 00:39:55,950 --> 00:39:59,810 >> Så det är minimalt log n steg, men hur är denna nyckel sammanslagning steg 885 00:39:59,810 --> 00:40:04,370 där jag gick samman min vänstra halvan och höger hälften och gick över scenen? 886 00:40:04,370 --> 00:40:06,980 Hur många steg är att gå samman? 887 00:40:06,980 --> 00:40:10,150 Det är n, men jag gjorde inte bara slå ihop den sista tiden. 888 00:40:10,150 --> 00:40:15,089 På var och en av dessa kapslade samtal, på varje av dessa kapslade går samman, jag sorteras fortfarande. 889 00:40:15,089 --> 00:40:18,380 Jag slås samman dessa två killar, då dessa två killar, då dessa två tjejer och så vidare. 890 00:40:18,380 --> 00:40:19,955 >> Så jag gjorde en sammanslagning igen, och igen. 891 00:40:19,955 --> 00:40:20,580 Hur många gånger? 892 00:40:20,580 --> 00:40:23,510 Så varje gång jag delade Listan på mitten, gjorde jag en sammanslagning. 893 00:40:23,510 --> 00:40:25,460 Dela upp listan på mitten, gör en sammanslagning. 894 00:40:25,460 --> 00:40:28,570 Så om man dividerar lista kan göras log n gånger, 895 00:40:28,570 --> 00:40:33,880 och sammanslagningen till slut tar n steg, vad som kan vara nu den övre 896 00:40:33,880 --> 00:40:37,000 bundet på driften tiden för vår algoritm? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> Och faktiskt, det är vad det vi har uppnått här. 899 00:40:40,560 --> 00:40:44,650 Så den känslan som du ser visuellt när dessa tre saker körda sida vid sida 900 00:40:44,650 --> 00:40:47,930 är n squared mot n kvadrat mot n log n. 901 00:40:47,930 --> 00:40:51,010 Som i grunden får vi se, inte bara idag utan även i framtiden, 902 00:40:51,010 --> 00:40:52,760 är mycket, mycket snabbare. 903 00:40:52,760 --> 00:40:56,010 En applåd för dessa killar, Jag kommer att belöna dem med stress bollar. 904 00:40:56,010 --> 00:41:00,260 Låt oss ajournera här i dag, och vi ses på måndag. 905 00:41:00,260 --> 00:41:02,255