1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> Govornik: U redu, ovo je CS50. 3 00:00:14,910 --> 00:00:19,020 To je kraj tjedna tri, a ako niste iskoristili već, 4 00:00:19,020 --> 00:00:21,790 Znam da će biti ručak ovaj petak, kao i obično, u kojoj 5 00:00:21,790 --> 00:00:25,430 možete uživati ​​dobar razgovor i hrane na Vatra i led 6 00:00:25,430 --> 00:00:27,980 s nekim od CS50-a osoblje i kolege. 7 00:00:27,980 --> 00:00:30,170 Krenite na ovaj URL ovdje. 8 00:00:30,170 --> 00:00:33,420 >> Sada možete sjetiti, ili ste svibanj uskoro biti upoznati s, 9 00:00:33,420 --> 00:00:35,970 te stvari ovdje, što daju se na kraju 10 00:00:35,970 --> 00:00:37,850 semestra za mnoge klase. 11 00:00:37,850 --> 00:00:40,870 Takozvani ispit plava knjiga, u kojoj pišete svoje odgovore na ispitima. 12 00:00:40,870 --> 00:00:44,240 Sada imam ovdje 26, kao plava knjiga, na svakom od njih 13 00:00:44,240 --> 00:00:47,580 je napisano ime, preko Z. A Doista imena su tako jednostavno, 14 00:00:47,580 --> 00:00:50,490 do Z. A jedan od ciljevi pri ruci danas 15 00:00:50,490 --> 00:00:53,910 koja će se nastaviti, što smo započeli u ponedjeljak, što nije 16 00:00:53,910 --> 00:00:57,830 toliko gleda na kodu, ali stvarno gleda na ideje i rješenja problema. 17 00:00:57,830 --> 00:01:00,170 Jedan od ciljeva i obećanja o ovom tečaju 18 00:01:00,170 --> 00:01:02,985 je da vas naučiti da razmišljaju više Pažljivo, više sustavno, 19 00:01:02,985 --> 00:01:05,400 i učinkovitije rješavanje problema. 20 00:01:05,400 --> 00:01:09,526 I doista, što možemo učiniti da se uistinu čak i bez dodirivanja liniju koda. 21 00:01:09,526 --> 00:01:12,150 Dakle, imam par slonova do danas ovdje, narančaste i plave, 22 00:01:12,150 --> 00:01:15,780 ako smo mogli dobiti jedan volonter, Možda iz dalje natrag nego inače. 23 00:01:15,780 --> 00:01:18,070 Kako bi bilo tamo, dođi ovamo. 24 00:01:18,070 --> 00:01:24,180 Cilj je što će biti s pomoći uz administraciju ovaj ispit ovdje. 25 00:01:24,180 --> 00:01:24,935 Koje je tvoje ime? 26 00:01:24,935 --> 00:01:25,768 >> PUBLIKA: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 Govornik: Mary Beth, dođi gore. 28 00:01:27,560 --> 00:01:29,560 Dopustite mi da se mikrofon ovdje za vas. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Drago mi je. 31 00:01:32,880 --> 00:01:34,005 >> PUBLIKA: Drago mi. 32 00:01:34,005 --> 00:01:36,790 Govornik: U redu, tako da imam Ovdje plava knjiga od A do Z, 33 00:01:36,790 --> 00:01:41,680 i ja ću se pretvarati da Imam jedan od studenata, 34 00:01:41,680 --> 00:01:45,770 i oni dolaze u pomalo slučajno Na kraju tri sata ispita blok 35 00:01:45,770 --> 00:01:49,400 pa oni završiti u nekim polu-nasumično ovako. 36 00:01:49,400 --> 00:01:54,510 Sada je vaš posao u samo nekoliko trenutaka ide da be-- to je zapravo kako su to 37 00:01:54,510 --> 00:01:56,820 predao krajem klase, najvjerojatnije. 38 00:01:56,820 --> 00:02:01,120 Vaš posao sada će biti, sasvim jednostavno, riješiti ove plave knjige za nas 39 00:02:01,120 --> 00:02:05,220 od A do Z. 40 00:02:05,220 --> 00:02:08,400 >> PUBLIKA: Oh, to je će potrajati zauvijek. 41 00:02:08,400 --> 00:02:13,747 >> Zvučnik: I mi ćemo gledati kao što ste to učinili, nema pritiska. 42 00:02:13,747 --> 00:02:15,330 PUBLIKA: Ne, nema pritiska ili bilo što. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> Zvučnik: I za zabavu, ajmo dići timer. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> PUBLIKA: Toliko zabavno, jako zabavno. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> Govornik: Ja mogu držati mikrofon za vas. 49 00:02:38,574 --> 00:02:40,240 U redu, upravo smo udvostručili svoju brzinu. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Dakle, u međuvremenu, neka mi predstavljati ono što je će biti pitanje za Mary Beth 52 00:02:49,060 --> 00:02:51,540 je ono što ona radi, kako je ona ide o rješavanju ovoga? 53 00:02:51,540 --> 00:02:54,040 A u stvari, možda nećete imati ikada razmišljali o nečemu 54 00:02:54,040 --> 00:02:57,440 tako jednostavno kao kada pokupiti do 26 knjiga kao što je ovaj, 55 00:02:57,440 --> 00:02:59,350 koji nemaju prirodni naredio da se njima. 56 00:02:59,350 --> 00:03:01,335 Što je proces da ste zapravo koriste? 57 00:03:01,335 --> 00:03:03,770 Je li to pravedno slučajni samo branje prvi vidite 58 00:03:03,770 --> 00:03:05,250 i stavljajući ga na njegovo mjesto? 59 00:03:05,250 --> 00:03:09,680 Da li prvo premjestiti svoje ruke oko traže onda traže B? 60 00:03:09,680 --> 00:03:11,722 Da li se pogledati na Par ih uz bok 61 00:03:11,722 --> 00:03:14,680 i samo reći, čekaj malo, ovo nije u redu, a onda mijenjati redoslijed? 62 00:03:14,680 --> 00:03:16,960 Vidjeli smo već u ponedjeljak da postoji više načina 63 00:03:16,960 --> 00:03:22,140 u kojem možemo to učiniti, a Doista kako smo blizu kraja ovdje, 64 00:03:22,140 --> 00:03:26,360 Ja bih se na znanje, možda od onoga što je Mary Beth se radi. 65 00:03:26,360 --> 00:03:30,040 Imamo nekoliko pilota Čini se, veći, tri manja. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> PUBLIKA: Ja sam ih naručivanje kad nađem dva slova 68 00:03:36,415 --> 00:03:39,540 Znam da su zajedno u nizu, Ja ih staviti zajedno, tako da ne znam 69 00:03:39,540 --> 00:03:42,915 morati brinuti o održavanju Staza za čitav red knjiga. 70 00:03:42,915 --> 00:03:45,706 To je samo, o, prvo, Imam tu hrpu ovdje. 71 00:03:45,706 --> 00:03:47,580 Govornik: Dakle, gotovo kao puzzle komada koji 72 00:03:47,580 --> 00:03:49,860 imaju pravo na oblik podudaraju se jedni s drugima. 73 00:03:49,860 --> 00:03:51,026 PUBLIKA: Prilično mnogo, da. 74 00:03:51,026 --> 00:03:55,320 Govornik: U redu, izvrsno. 75 00:03:55,320 --> 00:03:59,850 I sada je svaki od tih piloti navodno je izdvojiti? 76 00:03:59,850 --> 00:04:00,990 >> PUBLIKA: Da. 77 00:04:00,990 --> 00:04:09,900 >> Govornik: U redu, kroz Z. Sve Dobro, čestitam, ti si to učinio. 78 00:04:09,900 --> 00:04:11,461 Imate svoj izbor. 79 00:04:11,461 --> 00:04:11,960 Plavi? 80 00:04:11,960 --> 00:04:13,530 U redu, hvala ti za to. 81 00:04:13,530 --> 00:04:16,679 Tako je Mary Beth nije predlaže ono što joj je pristup bio, 82 00:04:16,679 --> 00:04:19,720 ali ono što je još jedan pristup koji će vas moglo ići oko sortiranja te stvari? 83 00:04:19,720 --> 00:04:21,130 Što biste vi učinili? 84 00:04:21,130 --> 00:04:24,060 Rekord pobijediti bi bilo jednu minutu i 50-ak sekundi, 85 00:04:24,060 --> 00:04:26,039 plus one Zaboravio sam brojati. 86 00:04:26,039 --> 00:04:27,080 Što biste vi učinili? 87 00:04:27,080 --> 00:04:27,579 Da? 88 00:04:27,579 --> 00:04:28,735 PUBLIKA: Uzmi snop. 89 00:04:28,735 --> 00:04:29,776 Počnite od početka. 90 00:04:29,776 --> 00:04:32,284 Provjerite svoje radove. 91 00:04:32,284 --> 00:04:36,586 A ako vrhu jednog je veća nego, možda, oni su, 92 00:04:36,586 --> 00:04:38,980 Dno je jedan veća, a zatim ih prebaciti. 93 00:04:38,980 --> 00:04:41,300 >> Govornik: U redu, tako da počevši na vrhu i na dnu, 94 00:04:41,300 --> 00:04:43,716 a zatim raditi svoj put unutra kao što je to, zamjene ih? 95 00:04:43,716 --> 00:04:46,580 U redu, tako da malo slična u duhu na bubble vrste, 96 00:04:46,580 --> 00:04:49,160 ali odabiru krajnosti Ne susjedna parova. 97 00:04:49,160 --> 00:04:52,080 No, kratko je u tome da postoji sigurno hrpa različitih načina 98 00:04:52,080 --> 00:04:54,210 mogli smo to učinili, i iskreno, mislim da ti vrsta 99 00:04:54,210 --> 00:04:55,700 usvojio par pristupe, zar ne? 100 00:04:55,700 --> 00:05:00,567 Vi napravili svojevrsno četiri sortiranost pilota, a a zatim ih učinkovito spojene zajedno. 101 00:05:00,567 --> 00:05:02,650 I to je, pretpostavljam, još jedan Tehnika uopce. 102 00:05:02,650 --> 00:05:06,950 Nisi ga tretiraju kao jednu veliku hrpu, li podijeliti problem u četiri četvorci, 103 00:05:06,950 --> 00:05:09,820 ako hoćete, i onda nekako ih spojio na kraju. 104 00:05:09,820 --> 00:05:13,410 >> Tako ćemo razmotriti, u konačnici, Kako inače bismo mogli to učiniti. 105 00:05:13,410 --> 00:05:15,860 Formalizirali smo ideju bubble sort posljednji put, 106 00:05:15,860 --> 00:05:18,780 i mjehurića svojevrsni Podsjetimo je algoritam koji smo vizualizirati 107 00:05:18,780 --> 00:05:22,640 s osam od svojih kolega ovdje, naizgled nasumično razvrstani po prvi put. 108 00:05:22,640 --> 00:05:26,110 I mi smo tada odlučili parovima, ako dva elementa su izvan reda, 109 00:05:26,110 --> 00:05:26,950 jednostavno ih zamijeniti. 110 00:05:26,950 --> 00:05:28,930 Dakle, četiri, a dva su očito preko reda, 111 00:05:28,930 --> 00:05:31,080 pa ta dva kolege uključen pozicije. 112 00:05:31,080 --> 00:05:35,390 A onda ćemo ponoviti s četiri i šest, zatim šest i osam, na svakoj iteraciji, 113 00:05:35,390 --> 00:05:36,980 pomicanjem u desno. 114 00:05:36,980 --> 00:05:42,590 >> Dakle, dao osam osoba, koliko parovima usporedbe sam napravio dok hodaju od 115 00:05:42,590 --> 00:05:45,220 lijeva na desno u jednom takvom iteraciji? 116 00:05:45,220 --> 00:05:48,410 Koliko usporedbe? 117 00:05:48,410 --> 00:05:49,197 Sedam, zar ne? 118 00:05:49,197 --> 00:05:51,405 Jer ako postoji osam ljudi, ali imate par 119 00:05:51,405 --> 00:05:53,880 ih i držati se kreće jedan hop na desno, 120 00:05:53,880 --> 00:05:56,060 nećeš imati osam usporedbe, jer se ne može usporediti 121 00:05:56,060 --> 00:05:59,226 Element protiv sebe, ili bi samo biti besmisleno, tako da imate sedam. 122 00:05:59,226 --> 00:06:01,290 Ili općenitije, ako se imamo n ljudi, mi 123 00:06:01,290 --> 00:06:04,300 to n minus 1 usporedbe s bubble vrste. 124 00:06:04,300 --> 00:06:08,150 >> Tako ćemo razmotriti sada koliko dobro ili loše mjehur svojevrsni je zapravo bio, i pokušati 125 00:06:08,150 --> 00:06:13,570 kako bi sebi dati vokabular s koji se kritiku algoritmima kao što je ovaj, 126 00:06:13,570 --> 00:06:14,430 i ubrzo naše. 127 00:06:14,430 --> 00:06:16,970 Dakle, na prvom prolazu kroz mjehurić sortirati, prvi put 128 00:06:16,970 --> 00:06:20,909 Hodao sam s lijeva na desno preko stage, uzeo me n minus 1 usporedbe. 129 00:06:20,909 --> 00:06:22,950 I to će biti moj jedinica mjere, zar ne? 130 00:06:22,950 --> 00:06:26,170 Ja je vrsta govori i šetnje, Nešto brzo, nešto sporo, 131 00:06:26,170 --> 00:06:29,300 pa računajući moj broj sekundi nije posebno reći, 132 00:06:29,300 --> 00:06:32,260 ali brojanjem Operacije koje sam učinio u ponedjeljak, 133 00:06:32,260 --> 00:06:35,900 Uspoređujući dvije osobe, da se osjeća kao lijep jedinicu mjere. 134 00:06:35,900 --> 00:06:40,980 >> Dakle, n minus 1 korake prvi put, ali ono što se tada dogodilo nakon toga? 135 00:06:40,980 --> 00:06:46,610 Što je jedan naopako jednom prolazu kroz inače nerazvrstani popisu? 136 00:06:46,610 --> 00:06:49,840 Što mi možete reći o elementu koji je bio skroz tamo? 137 00:06:49,840 --> 00:06:51,300 Da? 138 00:06:51,300 --> 00:06:52,870 To je bio najveći elementa, zar ne? 139 00:06:52,870 --> 00:06:55,710 Broj osam, iako ona počelo ovdje, svaki put sam 140 00:06:55,710 --> 00:06:57,860 je u odnosu prema susjed, ona je zadržao 141 00:06:57,860 --> 00:07:00,480 mjehurića do desne na desnoj strani popisa. 142 00:07:00,480 --> 00:07:02,710 I doista, to je mjesto gdje algoritam dobiva svoje ime. 143 00:07:02,710 --> 00:07:07,630 >> Sada po toj logici, koliko usporedbe Trebam napraviti na drugi put 144 00:07:07,630 --> 00:07:09,800 Ja bi tu loptu s lijeva na desno? 145 00:07:09,800 --> 00:07:10,730 n minus 2, zar ne? 146 00:07:10,730 --> 00:07:14,297 To bi samo biti gubit svoje vrijeme, ako sam zadržati uspoređujući osam protiv nekoga 147 00:07:14,297 --> 00:07:16,630 drugo, jer smo već znali je bio na pravom mjestu. 148 00:07:16,630 --> 00:07:19,760 Dakle, to je malo optimizacije, tako da sljedeći propusnica 149 00:07:19,760 --> 00:07:23,899 će biti plus n minus dva koraka, gdje je n je broj osoba. 150 00:07:23,899 --> 00:07:26,940 Sada možete vrsta zaključivati, Ako niste računalni znanstvenik, 151 00:07:26,940 --> 00:07:27,680 kako to završava. 152 00:07:27,680 --> 00:07:31,259 Na kraju ovog algoritma, vjerojatno imaš samo jednu usporedbu napustio. 153 00:07:31,259 --> 00:07:33,800 Morate vrsta popraviti početku popisa u slučaju dva 154 00:07:33,800 --> 00:07:36,540 i jedan su od reda i trebao bi biti jedan i dva, 155 00:07:36,540 --> 00:07:40,330 tako da je ovo s dna se na plus 1 konačni usporedbu. 156 00:07:40,330 --> 00:07:44,500 >> Sada točka, točka, točkica vrsta valova je Ruke na neke od juicier detaljima, 157 00:07:44,500 --> 00:07:46,452 ali neka je samo ići naprijed i pojednostaviti. 158 00:07:46,452 --> 00:07:48,660 Ako se sjećate iz visokih Škola, iskreno, puno vas 159 00:07:48,660 --> 00:07:50,340 imali matematičkih knjiga koje su imale Malo Cheat Sheet 160 00:07:50,340 --> 00:07:52,550 na naslovnici ili stražnji poklopac koji vam je pokazao 161 00:07:52,550 --> 00:07:56,400 ono serije summations poput To u konačnici zbrajaju se. 162 00:07:56,400 --> 00:07:59,600 U općem slučaju, ako imate promjenjiva kao n, i zaista ovo, 163 00:07:59,600 --> 00:08:01,634 ako ste gledali na svoje stara škola matematike knjiga, 164 00:08:01,634 --> 00:08:04,050 vidjeli biste da je to zapravo dodaje do tog iznosa ovdje, 165 00:08:04,050 --> 00:08:07,970 n puta n minus 1 sve podijeljeno s 2. 166 00:08:07,970 --> 00:08:11,172 Dakle, za sada neka mi samo propisuje to je istina, pa na skok vjere, 167 00:08:11,172 --> 00:08:12,880 to je ono što ovaj sažima do, a što smo mogli 168 00:08:12,880 --> 00:08:14,341 dokazati da je u općenitijem slučaju. 169 00:08:14,341 --> 00:08:15,590 No, sada ćemo proširiti ovo. 170 00:08:15,590 --> 00:08:19,920 Tako ćemo umnožiti ovo, tako da je n na kvadrat, minus nje, sve podijeljeno s 2. 171 00:08:19,920 --> 00:08:23,200 To je stvarno n kvadrat, podijeli s 2, minus n nad 2, 172 00:08:23,200 --> 00:08:25,010 tako da je sve lijepo i zanimljivo. 173 00:08:25,010 --> 00:08:27,060 Ali što se događa ako smo Sada plug-in vrijednosti? 174 00:08:27,060 --> 00:08:29,724 Pretpostavimo da nisam imao osam ljudi, ali kažu milijun. 175 00:08:29,724 --> 00:08:31,890 I samo zato milijuna to je prilično velik broj, 176 00:08:31,890 --> 00:08:34,039 ajmo plug da je u i vidjeti što će se dogoditi. 177 00:08:34,039 --> 00:08:39,039 Dakle, ako sam čep milijuna u toj formuli Ja ću dobiti milijun na kvadrat, 178 00:08:39,039 --> 00:08:42,868 podijeljeno sa 2, minus milijuna, podijeljeno s 2. 179 00:08:42,868 --> 00:08:44,159 Sad što se to događa na jednak? 180 00:08:44,159 --> 00:08:47,354 Dakle, 500 milijardi, minus 500.000. 181 00:08:47,354 --> 00:08:49,270 A ako sam zapravo učiniti da je matematika, to znači 182 00:08:49,270 --> 00:08:53,920 da razvrstavanje milijun ljudi s bubble vrste 183 00:08:53,920 --> 00:09:01,800 možda mi se 499999500000 koraka ili usporedbe na kraju, 184 00:09:01,800 --> 00:09:02,900 mi smo samo extrapolating. 185 00:09:02,900 --> 00:09:06,860 >> To se osjeća prilično sporo, ali iskreno mjerenje jedan određeni input 186 00:09:06,860 --> 00:09:09,160 ovako, nije sve što govori. 187 00:09:09,160 --> 00:09:14,050 Ali doista ne upućuju na to da kao n dobiva sve veći i veći, ovaj algoritam 188 00:09:14,050 --> 00:09:16,280 vrsta osjeća još gore i još gore, ili ste stvarno 189 00:09:16,280 --> 00:09:20,450 početi osjećati bol koja potenciranje, da n na kvadrat, 190 00:09:20,450 --> 00:09:21,770 koji dodaje se prilično brzo. 191 00:09:21,770 --> 00:09:25,340 I ovaj detalj nije izgubio na ljude, u stvari 192 00:09:25,340 --> 00:09:29,640 Prije nekoliko godina sigurno senator koji je bio kampanja, sjeo za intervju 193 00:09:29,640 --> 00:09:32,180 s Googleovog Erica Schmidt, izvršni direktor u to vrijeme, 194 00:09:32,180 --> 00:09:36,380 i bio je izazvan s pitanjem baš kao i mi danas istražuju. 195 00:09:36,380 --> 00:09:38,468 Idemo pogledati. 196 00:09:38,468 --> 00:09:45,280 >> [Video reprodukciju] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Ti si ovdje u Googleu, a ja volim 198 00:09:48,560 --> 00:09:53,382 razmišljati predsjedništva kao intervju za posao. 199 00:09:53,382 --> 00:09:56,434 Sada, to je teško dobiti posao kao predsjednik, 200 00:09:56,434 --> 00:09:58,100 i ti si idući kroz surovost sada. 201 00:09:58,100 --> 00:10:01,860 Također je teško dobiti posao u Googleu. 202 00:10:01,860 --> 00:10:05,490 Imamo pitanja, a mi pitajte naši kandidati pitanja, 203 00:10:05,490 --> 00:10:09,770 a to je jedna od Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 Što-- ste vi mislite da sam šalite, to je upravo ovdje. 205 00:10:14,760 --> 00:10:17,930 Što je najučinkovitiji način da se sortirati milijun 32-bitnih cijelih brojeva? 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 >> Žao mi je, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Ne, ne, ne. 210 00:10:27,400 --> 00:10:30,700 Mislim da je mjehurić vrsta bio bi pogrešan način da ide. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> Hajde, tko ga je to rekao? 213 00:10:38,180 --> 00:10:40,590 Nisam vidio računalo Znanost u pozadinu. 214 00:10:40,590 --> 00:10:42,130 >> -Imamo Naše špijune tamo. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Pitajmo drugačije Intervju pitanje. 217 00:10:48,444 --> 00:10:49,300 >> [END video reprodukciju] 218 00:10:49,300 --> 00:10:52,290 >> Zvučnik: Dakle govorimo o specifični brojevi ipak, 219 00:10:52,290 --> 00:10:53,890 ne će biti sve što je korisno. 220 00:10:53,890 --> 00:10:56,810 To nije život lekcija koju mjehur sortirati, dao milijun ulaza, 221 00:10:56,810 --> 00:10:58,590 možda se čak 500 milijardi korake. 222 00:10:58,590 --> 00:11:01,120 Vi stvarno ne mogu generalizirati previše učinkovito toga 223 00:11:01,120 --> 00:11:03,560 i donositi dobre odluke o dizajnu prilikom pisanja programa. 224 00:11:03,560 --> 00:11:07,070 Tako ćemo se usredotočiti iako o tome bismo mogli pojednostaviti ovaj rezultat. 225 00:11:07,070 --> 00:11:11,780 >> Tako sam istaknuo u žuto ovdje Rezultat n kvadrat, podijeljeno s 2, 226 00:11:11,780 --> 00:11:14,330 tako milijuna na kvadrat podijeljen 2, i 227 00:11:14,330 --> 00:11:16,710 Ja sam istaknuo ono što konačni odgovor bio 228 00:11:16,710 --> 00:11:20,180 Jednom smo oduzima off n podijeljena 2. 229 00:11:20,180 --> 00:11:24,850 A tvrdnja da ću napraviti sada je, koji kritički briga ako oduzmete off 230 00:11:24,850 --> 00:11:30,060 Malo stara nje više od 2, kada je prvi dio ove formule je tako puno veći? 231 00:11:30,060 --> 00:11:33,910 Dominira drugi Izraz, n kvadrat, podijeljeno s 2 232 00:11:33,910 --> 00:11:37,510 toliko je mnogo veći, jasno, kao što je nje dobiva velika kao milijun, 233 00:11:37,510 --> 00:11:41,450 da je tamo stvarno velika razlika u kraj dana između 500 milijardi 234 00:11:41,450 --> 00:11:45,730 i 499.999.500.000? 235 00:11:45,730 --> 00:11:46,349 Ne baš. 236 00:11:46,349 --> 00:11:48,640 I tako što ćemo učiniti što je računalni znanstvenici 237 00:11:48,640 --> 00:11:53,270 ignoriraju one niže pojmove reda i uzeti nešto poput ovog i stvarno 238 00:11:53,270 --> 00:11:56,050 samo ga pojednostaviti kako bi Pojam koji će važno. 239 00:11:56,050 --> 00:12:00,315 Veće naše skupine podataka dobiti, veći naše baze podataka dobili, više web stranica 240 00:12:00,315 --> 00:12:02,690 moramo tražiti, više prijateljima imate na Facebooku. 241 00:12:02,690 --> 00:12:07,340 >> Kao nje dobiva veći, mi smo stvarno će se brinuti o veličini 242 00:12:07,340 --> 00:12:11,560 termina u svakoj takvoj analizi naša izvedba algoritama. 243 00:12:11,560 --> 00:12:16,230 A ja ću reći, znate što, Bubble sorta je po nalogu velikog O, 244 00:12:16,230 --> 00:12:18,060 po nalogu n na kvadrat. 245 00:12:18,060 --> 00:12:20,090 To nije točno n kvadrat, kao što smo vidjeli, 246 00:12:20,090 --> 00:12:22,060 ali tko stvarno brine o tim manjim uvjetima, 247 00:12:22,060 --> 00:12:24,390 i iskreno, tko je zapravo brine ako podijelimo s 2? 248 00:12:24,390 --> 00:12:25,870 To je samo konstantan faktor. 249 00:12:25,870 --> 00:12:29,480 I 500 milijardi u odnosu na 250 milijardi stvarno da je veliki posao? 250 00:12:29,480 --> 00:12:32,190 Mogao sam samo čekati jedne godine, neka moj laptop doslovno 251 00:12:32,190 --> 00:12:34,810 dobili dva puta brže u hardver, i da je na neki način razlika 252 00:12:34,810 --> 00:12:36,650 samo ide dalje, naravno, tijekom vremena. 253 00:12:36,650 --> 00:12:39,300 >> Ono što mi je stalo je izraz, dio 254 00:12:39,300 --> 00:12:42,489 izraza koji će se razlikovati kao što je naš ulaz dobiva veći i veći. 255 00:12:42,489 --> 00:12:45,280 I doista, u stvarnom svijetu, to je ono što se događa sve više 256 00:12:45,280 --> 00:12:48,330 je ulaze na naše probleme i algoritmi su sve veći. 257 00:12:48,330 --> 00:12:53,470 Tako veliki O će biti zapis, asimptotsko zapis, koji smo upravo 258 00:12:53,470 --> 00:12:57,160 koristiti kao računalni znanstvenici opisati performanse, ili trčanje vremena, 259 00:12:57,160 --> 00:12:58,130 algoritma. 260 00:12:58,130 --> 00:13:00,800 Tako da možemo usporediti algoritme na različitim računalima pisanim 261 00:13:00,800 --> 00:13:04,170 od strane različitih ljudi, pomoću Neki osnovi slična metrički 262 00:13:04,170 --> 00:13:07,557 poput broja usporedbe ste izrade, ili možda broj swaps 263 00:13:07,557 --> 00:13:08,140 radite. 264 00:13:08,140 --> 00:13:11,910 >> Ono što mi se ne ide na Broj je količina vremena 265 00:13:11,910 --> 00:13:13,981 koji prolazi na sat na zidu obično. 266 00:13:13,981 --> 00:13:16,230 Ono što nećemo brinuti o je koliko memorije 267 00:13:16,230 --> 00:13:17,820 koristite danas na Barem, iako je to 268 00:13:17,820 --> 00:13:19,370 još jedan resurs možemo izmjeriti. 269 00:13:19,370 --> 00:13:23,610 Mi ćemo pokušati temeljiti naše analize o samo osnovnim operacijama, one, 270 00:13:23,610 --> 00:13:25,930 iskreno, da možete vidjeti najviše vizualno. 271 00:13:25,930 --> 00:13:30,700 Dakle, nešto poput velikog O n kvadrat, ja tvrdim da je O n na kvadrat 272 00:13:30,700 --> 00:13:35,820 gornja granica na tzv trajanju od mjehurića vrste. 273 00:13:35,820 --> 00:13:38,820 Drugim riječima, ako vas Htio tvrde da postoji 274 00:13:38,820 --> 00:13:41,370 ova gornja granica koliko koraci algoritma moglo potrajati, 275 00:13:41,370 --> 00:13:46,240 to će biti u velikoj O n kvadrat u ovom slučaju, gornja granica. 276 00:13:46,240 --> 00:13:49,710 >> Što ako umjesto promijeniti Priča se da nije riječ o balonu vrste, 277 00:13:49,710 --> 00:13:50,910 ali o tome gornju granicu. 278 00:13:50,910 --> 00:13:54,030 Možete li se sjetiti algoritma koje smo gledali na već 279 00:13:54,030 --> 00:13:59,530 čija je gornja granica, maksimalna mjerenje vremena ili operacija, 280 00:13:59,530 --> 00:14:04,300 bi se reći da je omeđeno N, linearna funkcija, 281 00:14:04,300 --> 00:14:07,260 Ne kvadratne onaj koji je zaobljen? 282 00:14:07,260 --> 00:14:10,780 Što je algoritam koji uvijek ne traje više 283 00:14:10,780 --> 00:14:12,860 nego kao n koraka, ili 2n koraka, ili 3n koraka? 284 00:14:12,860 --> 00:14:13,360 Da? 285 00:14:13,360 --> 00:14:15,030 >> PUBLIKA: Pronalaženje Najveći broj u popisu? 286 00:14:15,030 --> 00:14:16,930 >> Govornik: Savršen, pronalaženje Najveći broj u popisu. 287 00:14:16,930 --> 00:14:18,940 Ako sam dao popis ljudi za primjer, 288 00:14:18,940 --> 00:14:21,440 svaki od koga se drži broj, što je najveći broj 289 00:14:21,440 --> 00:14:23,770 koraka da me treba poduzeti, razumno pametna osoba, 290 00:14:23,770 --> 00:14:27,530 pronaći najveći osobu u tom popisu? 291 00:14:27,530 --> 00:14:28,100 nje, zar ne? 292 00:14:28,100 --> 00:14:31,320 Budući da je u najgorem slučaju, gdje je možda najveća vrijednost biti? 293 00:14:31,320 --> 00:14:32,700 Točno, skroz na kraju. 294 00:14:32,700 --> 00:14:34,575 Dakle, u najgorem slučaju gornju granicu, mogao bih 295 00:14:34,575 --> 00:14:36,450 moram ići do kraja ovamo i biti poput, 296 00:14:36,450 --> 00:14:39,170 Oh, ovdje je broj osam, ili što god da je vrijednost. 297 00:14:39,170 --> 00:14:41,330 Sada bi samo biti glup ako sam zadržao ide, zar ne? 298 00:14:41,330 --> 00:14:43,840 U potrazi za sve više i više elemenata Ako je posljednji od njih je tamo? 299 00:14:43,840 --> 00:14:45,340 Pa sigurno, n gornju granicu. 300 00:14:45,340 --> 00:14:47,420 Ne treba uzeti više koraka od toga. 301 00:14:47,420 --> 00:14:51,580 >> Pa što ako se umjesto toga sam predložio da postoje algoritmi u ovom svijetu koji 302 00:14:51,580 --> 00:14:57,750 imati vrijeme rada koji je omeđen velikim O iz log n, prijavite n? 303 00:14:57,750 --> 00:15:00,390 Gdje smo prije vidjeli ovo? 304 00:15:00,390 --> 00:15:00,890 Da? 305 00:15:00,890 --> 00:15:03,309 >> PUBLIKA: U problemu telefonski imenik? 306 00:15:03,309 --> 00:15:04,850 Zvučnik: Kao problem imenika. 307 00:15:04,850 --> 00:15:07,754 Što je mjerilo koliko koliko vremena i koliko suze IT 308 00:15:07,754 --> 00:15:10,170 Trebalo mi je naći nekoga poput Mike Smith je u telefonskom imeniku? 309 00:15:10,170 --> 00:15:13,212 Tvrdili smo da je log n, a čak i ako nisu upoznati ili je to 310 00:15:13,212 --> 00:15:15,170 malo mutno što logaritam ili eksponent bio, 311 00:15:15,170 --> 00:15:17,650 Samo zapamtite da log n općenito se odnosi na proces 312 00:15:17,650 --> 00:15:20,790 U tom slučaju, dijeljenja nešto na pola opet, i opet, 313 00:15:20,790 --> 00:15:25,790 i opet, i opet, kao da je to dobiva sve više mali kao što učiniti. 314 00:15:25,790 --> 00:15:28,470 >> Dakle, prijavite n odnosi, sigurno, do telefonskog imenika, primjerice, 315 00:15:28,470 --> 00:15:32,662 na binarnom potrazi u teoriji, kada smo imali virtualne vrata na brodu, 316 00:15:32,662 --> 00:15:34,370 ili kad je Sean je u potrazi za nečim. 317 00:15:34,370 --> 00:15:37,374 Ako je koristio binarni pretraživanje, prijavite n će biti gornja granica na koliko 318 00:15:37,374 --> 00:15:38,040 Vrijeme koje traje. 319 00:15:38,040 --> 00:15:44,027 Ali ti algoritmi koja su bila u log n pretpostaviti što ključni detalj? 320 00:15:44,027 --> 00:15:45,360 Taj popis je sortirano, zar ne? 321 00:15:45,360 --> 00:15:47,789 Vaš algoritam nije u redu, ako Vaš komentar se ne sortira se, 322 00:15:47,789 --> 00:15:49,830 a ipak budete koristili nešto poput binarnog pretraživanja 323 00:15:49,830 --> 00:15:51,704 jer možda skočiti Pravo nad elementa 324 00:15:51,704 --> 00:15:53,600 ne shvaćajući da je doista postoji. 325 00:15:53,600 --> 00:15:55,600 >> Sad što bi to značilo, veliki O jedne od njih? 326 00:15:55,600 --> 00:15:59,117 To ne znači da je vaš algoritma ima jedan i samo jedan korak, 327 00:15:59,117 --> 00:16:01,200 To samo znači da je potrebno konstanta broj koraka. 328 00:16:01,200 --> 00:16:04,060 Možda je to 1, možda je 10, možda je 1.000, 329 00:16:04,060 --> 00:16:07,750 ali to je neovisan o veličina problema. 330 00:16:07,750 --> 00:16:10,850 Bez obzira koliko je velika n, konstanta vrijeme algoritam 331 00:16:10,850 --> 00:16:12,747 Uvijek ima isti broj koraka. 332 00:16:12,747 --> 00:16:15,080 Dakle, ono što bi moglo biti algoritam smo razgovarali o tome ili samo 333 00:16:15,080 --> 00:16:20,418 intuitivno da dolazi k vama da uvijek radi u tzv stalnom vrijeme? 334 00:16:20,418 --> 00:16:20,918 Da? 335 00:16:20,918 --> 00:16:22,001 >> PUBLIKA: Dodaj dva broja. 336 00:16:22,001 --> 00:16:25,320 Zvučnik: Dodaj dva broja, 2 plus 2 jednako 4, učinjeno. 337 00:16:25,320 --> 00:16:27,227 Tako da bi mogli raditi, što drugo? 338 00:16:27,227 --> 00:16:28,560 Kako bi bilo više stvarnom svijetu, zar ne? 339 00:16:28,560 --> 00:16:30,686 >> PUBLIKA: Pronalaženje Prva stvar na popisu. 340 00:16:30,686 --> 00:16:32,810 Zvučnik: Pronalaženje prvi element u listi, sigurno. 341 00:16:32,810 --> 00:16:34,540 Mi smo zapravo razgovarali O polja već, 342 00:16:34,540 --> 00:16:36,540 Kako ste dobili na Prvi element u nizu, 343 00:16:36,540 --> 00:16:40,465 bez obzira koliko dugo Niz je u C-kod? 344 00:16:40,465 --> 00:16:43,090 Vi samo koristiti kao nosač nula zapis, bam, ti si tamo. 345 00:16:43,090 --> 00:16:46,120 I zaista, polja, što je po strani, Podrška nešto općenito poznato 346 00:16:46,120 --> 00:16:49,240 kao slučajni pristup, s izravnim pristupom memorije, jer možete doslovno 347 00:16:49,240 --> 00:16:50,284 skok na bilo kojem mjestu. 348 00:16:50,284 --> 00:16:52,700 Možemo to učiniti još više jednostavno možemo natrag u tjedan nula 349 00:16:52,700 --> 00:16:53,900 kad smo nule. 350 00:16:53,900 --> 00:16:59,707 Koliko vremena je trebalo za kažu blok u Scratch izvršiti? 351 00:16:59,707 --> 00:17:00,790 Samo konstanta vrijeme, zar ne? 352 00:17:00,790 --> 00:17:03,960 Reci nešto, kažu nešto, to nije važno 353 00:17:03,960 --> 00:17:07,359 Koliko je velika Ogrebotine svijet, to je uvijek trajat će istu količinu vremena 354 00:17:07,359 --> 00:17:08,490 jednostavno nešto reći. 355 00:17:08,490 --> 00:17:11,089 >> Dakle, to je konstanta vrijeme, ali ono što je naličje? 356 00:17:11,089 --> 00:17:13,030 Ako je to gornja granice, što ako želimo 357 00:17:13,030 --> 00:17:17,089 opisati donje granice od naših algoritama vrijeme rada? 358 00:17:17,089 --> 00:17:19,852 Gotovo najboljem slucaju potencijalno, ako hoćete, 359 00:17:19,852 --> 00:17:23,060 iako ti pojmovi mogu primijeniti na najbolji Kućišta, najgorem slučaju, prosjek slučajevi više 360 00:17:23,060 --> 00:17:26,359 općenito, ali neka je samo usredotočiti na donje granice općenito. 361 00:17:26,359 --> 00:17:31,920 Što je algoritam koji ima donju granicu od n koraka, 362 00:17:31,920 --> 00:17:33,350 ili 2n koraka, ili 3n koraka? 363 00:17:33,350 --> 00:17:36,241 Neki faktor od n koraka, To joj je donju granicu. 364 00:17:36,241 --> 00:17:36,740 Da? 365 00:17:36,740 --> 00:17:37,910 >> PUBLIKA: Bubble svojevrsni? 366 00:17:37,910 --> 00:17:41,610 >> Zvučnik: Bubble svojevrsni traje što minimalno n koraka, zašto? 367 00:17:41,610 --> 00:17:42,279 Zašto je to tako? 368 00:17:42,279 --> 00:17:45,320 Zašto bi to početak doći do vas intuitivno, čak ni ako to ne samo 369 00:17:45,320 --> 00:17:46,530 još? 370 00:17:46,530 --> 00:17:47,030 Da? 371 00:17:47,030 --> 00:17:47,990 >> PUBLIKA: [nečujan]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 Govornik: Točno. 374 00:17:52,360 --> 00:17:55,810 U najboljem mogućem scenariju mjehurić sortirati, a puno algoritama, 375 00:17:55,810 --> 00:17:58,769 Ako sam ruku vam osam osoba koji već su razvrstani, 376 00:17:58,769 --> 00:18:00,560 bilo bi glupo za vas, algoritam, 377 00:18:00,560 --> 00:18:02,202 ići naprijed i natrag više od jednom, zar ne? 378 00:18:02,202 --> 00:18:04,285 Jer čim prošetati kroz popis jednom, 379 00:18:04,285 --> 00:18:08,090 trebate shvatiti, oh, ja se nisam swapovi, ovaj popis se sortira, izlaz. 380 00:18:08,090 --> 00:18:09,700 No, to će vas n korake poduzeti. 381 00:18:09,700 --> 00:18:12,033 >> A s druge strane, ono što je još jedan način razmišljanja o tome? 382 00:18:12,033 --> 00:18:15,240 Bubble sorta je Omega, da se tako izrazim, n, 383 00:18:15,240 --> 00:18:19,050 jer ako pogledate manje od n elemenata, što 384 00:18:19,050 --> 00:18:23,009 je temeljno pitanje postoji? 385 00:18:23,009 --> 00:18:24,550 Ne znam je li to razvrstani, zar ne. 386 00:18:24,550 --> 00:18:26,800 Mi ljudi možda pogledao osam ljudi i biti poput, oh, to je riješeno, 387 00:18:26,800 --> 00:18:28,430 da me n koraka nije uzeo, ali je to učinio. 388 00:18:28,430 --> 00:18:30,810 Tvoje oči, iako ste ljubazni od imati veliki vidno polje, 389 00:18:30,810 --> 00:18:33,184 ste gledali na osam elemenata, ste gledali na osam ljudi, 390 00:18:33,184 --> 00:18:34,610 to je osam koraka učinkovito. 391 00:18:34,610 --> 00:18:38,612 I samo ako sam prošetati kroz cijeli Popis ne shvaćam, da, razvrstani. 392 00:18:38,612 --> 00:18:41,320 Ako sam stati na pola puta razmišljam, sve U redu, to je do sada prilično razvrstani, 393 00:18:41,320 --> 00:18:42,520 kakvi su izgledi da nije poredani? 394 00:18:42,520 --> 00:18:44,186 To algoritmi neće biti točna. 395 00:18:44,186 --> 00:18:46,250 Mogao bi biti brži, ali netočna. 396 00:18:46,250 --> 00:18:48,500 >> Tako sada imamo način Opisujući nižu granicu, 397 00:18:48,500 --> 00:18:49,710 a što je sa stalnim vremena? 398 00:18:49,710 --> 00:18:54,565 Što je algoritam koji ima manji dužni na svom trajanju od jedne? 399 00:18:54,565 --> 00:18:58,350 1 korak, 2 koraka, 10 koraka, ali konstanta, neovisno od N, 400 00:18:58,350 --> 00:18:59,310 veličina ulaz? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Da, u leđima. 403 00:19:04,600 --> 00:19:05,309 >> PUBLIKA: printf? 404 00:19:05,309 --> 00:19:06,183 Zvučnika: Što je to? 405 00:19:06,183 --> 00:19:07,184 PUBLIKA: printf? 406 00:19:07,184 --> 00:19:07,850 Govornik: printf. 407 00:19:07,850 --> 00:19:08,400 U redu, sigurno. 408 00:19:08,400 --> 00:19:10,720 Dakle, to traje određeni broj koraka. 409 00:19:10,720 --> 00:19:13,170 I ja bi trebao now-- sada da pričamo o C kod 410 00:19:13,170 --> 00:19:16,040 a ne grebanje, nešto kao što je recimo, s printf, 411 00:19:16,040 --> 00:19:17,710 trebamo početi dobiti oprezni. 412 00:19:17,710 --> 00:19:21,090 Zbog printf uzima ulaz, to je niz, 413 00:19:21,090 --> 00:19:23,220 i gudače tehnički nemaju duljinu. 414 00:19:23,220 --> 00:19:25,530 Dakle, ako mi sada žele pokupiti na vas, ako vam ne smeta, 415 00:19:25,530 --> 00:19:29,430 tehnički možemo tvrditi da printf uzima varijabilne duljine ulaz, 416 00:19:29,430 --> 00:19:32,270 a sigurno bi to moglo potrajati više Vrijeme ispisati niz tako dugo, 417 00:19:32,270 --> 00:19:33,560 nego ovako dugo. 418 00:19:33,560 --> 00:19:36,570 >> Pa što ako uzmemo u obzir samo sortiranje i pretraživanje primjere? 419 00:19:36,570 --> 00:19:40,450 Što je Mike Smith u telefonu Knjiga ili binarno pretraživanje općenito? 420 00:19:40,450 --> 00:19:42,220 U najboljem slučaju, što bi se moglo dogoditi? 421 00:19:42,220 --> 00:19:45,577 Ja otvoriti telefonski imenik i, bam, Tu je Mike Smith broj. 422 00:19:45,577 --> 00:19:46,660 Ja ga mogu nazvati odmah. 423 00:19:46,660 --> 00:19:49,390 >> Uzeo jedan korak, možda dva koraka, ali konstantan broj koraka 424 00:19:49,390 --> 00:19:50,230 ako mi se posrećilo. 425 00:19:50,230 --> 00:19:52,570 I iskreno, vidjeli smo na Ponedjeljak vaša kolegica 426 00:19:52,570 --> 00:19:54,710 dobiti prilično sretan dva puta za redom. 427 00:19:54,710 --> 00:19:57,050 I to je doista konstantna put u donje granice 428 00:19:57,050 --> 00:20:01,280 na algoritam u pitanju za pronalaženje broj 50 iza onih zatvoren 429 00:20:01,280 --> 00:20:01,830 Vrata. 430 00:20:01,830 --> 00:20:06,400 >> Sada, kao što je na stranu, ako otkrijete da su i veliki O, gornja granica, 431 00:20:06,400 --> 00:20:09,310 i omega, donju granicu, su jedan te isti, da 432 00:20:09,310 --> 00:20:11,830 je ista formula zagrade, također možete 433 00:20:11,830 --> 00:20:15,170 kažu, samo da bude fancy, da nešto nije u theta 434 00:20:15,170 --> 00:20:18,270 n i nagiba neke druge vrijednosti. 435 00:20:18,270 --> 00:20:20,661 To samo znači kada se velika O i omega su isti. 436 00:20:20,661 --> 00:20:21,910 Što o odabiru vrste sad? 437 00:20:21,910 --> 00:20:23,400 Iskoristimo ovaj novi vokabular. 438 00:20:23,400 --> 00:20:27,407 U odabiru vrste, što smo radi opet, i opet, i opet? 439 00:20:27,407 --> 00:20:29,990 Htjela sam natrag i naprijed kroz Popis, u potrazi za koga? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Najmanji broj. 442 00:20:34,730 --> 00:20:37,560 >> Pa koliko koraka, kako mnogi usporedbe zar ne 443 00:20:37,560 --> 00:20:43,250 morati učiniti kako bi se shvatiti tko najmanji element na popisu je bio? 444 00:20:43,250 --> 00:20:44,437 n minus 1, zar ne? 445 00:20:44,437 --> 00:20:47,770 Jer ako mi samo početi s koje sam dao i ja početi njega ili nju usporedbe, 446 00:20:47,770 --> 00:20:49,519 onda njemu ili njoj, on ili nju, njega ili nju, ja 447 00:20:49,519 --> 00:20:52,010 mogu samo upariti elemente zajedno n minus 1 puta. 448 00:20:52,010 --> 00:20:55,630 Dakle, izbor svojevrsni sličan traje n minus 1 korake prvi put. 449 00:20:55,630 --> 00:20:59,540 >> Koliko koraka to me odvesti naći drugi najmanji element? 450 00:20:59,540 --> 00:21:02,920 n minus 2, jer sam bio glup ako sam stalno gleda na istim ljudima 451 00:21:02,920 --> 00:21:06,280 opet, ako već sam ga odabrali ili nju, te ih staviti na svoje mjesto. 452 00:21:06,280 --> 00:21:09,270 I treći korak, n minus 3, a zatim n minus 4. 453 00:21:09,270 --> 00:21:11,020 Vidjeli smo ovaj uzorak prije, i doista 454 00:21:11,020 --> 00:21:13,460 Izbor svojevrsni sličan ima gornju granicu 455 00:21:13,460 --> 00:21:16,210 n na kvadrat, ako mi se da zbrajanja. 456 00:21:16,210 --> 00:21:19,790 Koja je njegova donja granica, izbor svojevrsni? 457 00:21:19,790 --> 00:21:25,350 Minimalno, koliko je vremena potrebno za odabir Sortiranje se, kao što smo to definirano u ponedjeljak? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Predložiti dvije mogućnosti. 460 00:21:30,490 --> 00:21:32,360 Možda je to nje, kao i prije. 461 00:21:32,360 --> 00:21:35,040 Možda je n je kvadrat, što je njemu sada je kao gornja granica. 462 00:21:35,040 --> 00:21:35,874 >> PUBLIKA: n na kvadrat. 463 00:21:35,874 --> 00:21:36,664 Zvučnika: n na kvadrat. 464 00:21:36,664 --> 00:21:37,368 Zašto? 465 00:21:37,368 --> 00:21:40,060 >> PUBLIKA: Zato što imate definirati [nečujan]. 466 00:21:40,060 --> 00:21:41,510 >> Govornik: Točno. 467 00:21:41,510 --> 00:21:45,077 Barem dok sam definira odabir vrsta to je prilično naivno, zadržati ide, 468 00:21:45,077 --> 00:21:46,160 naći najmanji element. 469 00:21:46,160 --> 00:21:47,770 Idi opet, naći najmanji element. 470 00:21:47,770 --> 00:21:49,490 Idi opet, naći najmanji element. 471 00:21:49,490 --> 00:21:51,700 Nema vrsta optimizacija tamo da 472 00:21:51,700 --> 00:21:54,350 možda neka mi se prekinuti nakon samo n-ak koraka. 473 00:21:54,350 --> 00:21:57,080 Dakle, doista, izbor sortirati, omega n na kvadrat. 474 00:21:57,080 --> 00:22:00,667 >> Što je umetanje vrsta, gdje sam uzeo koji sam dobio, a onda sam ga ubacio 475 00:22:00,667 --> 00:22:01,750 ili joj na pravom mjestu? 476 00:22:01,750 --> 00:22:04,958 Onda sam nastavio s drugom osobom, njega ili nju ubacio na pravom mjestu. 477 00:22:04,958 --> 00:22:07,910 Zatim sljedeća osoba, ubacio njemu ili njoj na pravom mjestu. 478 00:22:07,910 --> 00:22:10,537 Uočite da je ovo vrlo linearno, da se tako izrazim. 479 00:22:10,537 --> 00:22:12,620 Ja sam ravna crta, ja sam ne ide natrag i naprijed, 480 00:22:12,620 --> 00:22:16,080 Nikad nisam gleda unatrag stvarno, ali što se događa kad sam ga umetnite 481 00:22:16,080 --> 00:22:20,302 ili joj se u početku Popis kao što smo učinili u ponedjeljak? 482 00:22:20,302 --> 00:22:21,010 Što se događa? 483 00:22:21,010 --> 00:22:21,510 Da? 484 00:22:21,510 --> 00:22:23,122 PUBLIKA: [nečujan]. 485 00:22:23,122 --> 00:22:24,830 Zvučnik: Da, da bio ulov, zar ne? 486 00:22:24,830 --> 00:22:26,746 Možda ćete se sjetiti iz Vaši kolege, ako su 487 00:22:26,746 --> 00:22:29,670 su stvaranje bilo koji pokret s nogama, da je operacija. 488 00:22:29,670 --> 00:22:33,610 Dakle, ako je bilo troje ljudi ovdje i nova osoba pripadala put tamo, 489 00:22:33,610 --> 00:22:37,360 na dugom pozornici kao što je ovaj, je li, on ili je ona samo može ići do samog kraja. 490 00:22:37,360 --> 00:22:40,074 Ali, ako razmišljamo o Računalo i niz sjećanja, 491 00:22:40,074 --> 00:22:41,990 ti ljudi idu imati na shuffle preko 492 00:22:41,990 --> 00:22:43,260 kako bi napravili mjesta za tu osobu. 493 00:22:43,260 --> 00:22:46,930 I tako da n minus 1 shufflings, n minus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 minus 3 shufflings je samo neka vrsta događa iza mene, a ne ispred mene 495 00:22:50,660 --> 00:22:52,710 kao i prije, u nekom smislu. 499 00:22:52,557 --> 00:22:54,640 Sada kao na stranu, a kao ste mogli vidjeti na internetu 500 00:22:54,640 --> 00:22:57,699 ako počnete čeprka po o vrste, postoji toliko različitih one 501 00:22:57,699 --> 00:22:59,490 vani, neki od njih bolji od drugih. 502 00:22:59,490 --> 00:23:02,200 Doista, bogosort jedan to je vrsta zabave potražiti. 503 00:23:02,200 --> 00:23:06,650 Bogosort ima niz brojevi ili kažu špil karata, 504 00:23:06,650 --> 00:23:09,870 slučajno ih u slučajnom, a provjerava da li oni razvrstani. 505 00:23:09,870 --> 00:23:12,130 A ako ne, opet nema ga. 506 00:23:12,130 --> 00:23:14,140 A ako ne, opet nema ga. 507 00:23:14,140 --> 00:23:15,440 Ako ne, opet nema ga. 508 00:23:15,440 --> 00:23:17,060 Nevjerojatno glupo. 509 00:23:17,060 --> 00:23:19,520 >> I doista, ako ste pročitali kao što je Wikipedia članak, 510 00:23:19,520 --> 00:23:21,200 njegov nadimak je glup neka vrsta. 511 00:23:21,200 --> 00:23:25,180 To će na kraju raditi, nadamo se, dati dovoljno vremena, 512 00:23:25,180 --> 00:23:28,240 , ali da je količina vremena mogao potrajati duže vrijeme. 513 00:23:28,240 --> 00:23:31,650 Dakle, ako sam mogao, ajmo ubrzati stvari gore od Mary Beth je primjer ranije, 514 00:23:31,650 --> 00:23:35,150 tako da još nekoliko elemenata, ali još dva procesora. 515 00:23:35,150 --> 00:23:37,100 Dvoje ljudi, ako vas Ne bi mi smetalo mi se pridružio. 516 00:23:37,100 --> 00:23:40,972 Kako oko 1 ovamo, i ajmo go-- nikoga tamo? 517 00:23:40,972 --> 00:23:41,722 Nitko tamo? 518 00:23:41,722 --> 00:23:42,221 U redu. 519 00:23:42,221 --> 00:23:44,190 Vi s crnom košulju, da, dođi ovamo. 520 00:23:44,190 --> 00:23:45,000 U redu, kako se zoveš? 521 00:23:45,000 --> 00:23:45,720 >> PUBLIKA: Petar. 522 00:23:45,720 --> 00:23:46,100 >> Zvučnika: Što je to? 523 00:23:46,100 --> 00:23:46,766 >> PUBLIKA: Petar. 524 00:23:46,766 --> 00:23:49,450 Govornik: Peter David, lijepo da zadovolji vas. 525 00:23:49,450 --> 00:23:53,670 U redu, imamo Petra ovdje, ako vas žele doći na stol ovamo. 526 00:23:53,670 --> 00:23:54,550 A kako se ti zoveš? 527 00:23:54,550 --> 00:23:55,216 >> PUBLIKA: Elena. 528 00:23:55,216 --> 00:23:55,970 Govornik: Elena. 529 00:23:55,970 --> 00:23:57,030 U redu, lijepo da zadovolji vas. 530 00:23:57,030 --> 00:23:58,060 Elena susret Petra. 531 00:23:58,060 --> 00:23:59,170 Petar, Elena. 532 00:23:59,170 --> 00:24:02,290 A mi ćemo morati Andriju Ovdje, kao i, molim te. 533 00:24:02,290 --> 00:24:06,107 I vaš izazov ide se razvrstati špil karata. 534 00:24:06,107 --> 00:24:08,190 A ako nisu upoznati, paluba kartica bi trebala u konačnici 535 00:24:08,190 --> 00:24:11,064 biti razvrstani malo nešto slično to gdje ćemo napraviti klubova, a zatim 536 00:24:11,064 --> 00:24:13,660 Pik, a zatim su srca i dijamanti, od asa kao jedan, 537 00:24:13,660 --> 00:24:15,570 pa sve do kralja. 538 00:24:15,570 --> 00:24:20,890 >> Kartice ću vam dati će biti 52 u količini. 539 00:24:20,890 --> 00:24:23,160 Idemo na sličan način Vrijeme vam, u samo trenutak. 540 00:24:23,160 --> 00:24:26,410 Idemo baciti Andriju Na zaslonu se ovdje, 541 00:24:26,410 --> 00:24:28,170 kako bi se gledati kao što ste to učinili. 542 00:24:28,170 --> 00:24:31,070 Tako da je sve to je sve više vidljiv, 543 00:24:31,070 --> 00:24:33,490 To su kartice dobio sam na Amazonu. 544 00:24:33,490 --> 00:24:42,861 Dakle, oni su već nasumično razvrstani, a mi ćemo vam vrijeme. 545 00:24:42,861 --> 00:24:44,610 A mi idemo u držati ga u realnom ovaj put, 546 00:24:44,610 --> 00:24:47,820 pa ćemo pokušati prisiliti jer bi u suprotnom to će dobiti zamorno 547 00:24:47,820 --> 00:24:48,460 brzo. 548 00:24:48,460 --> 00:24:53,860 Ako bi mogao nastaviti sortirati 52 elementi zajedno preko nekih sredstava, odmah. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> I opet, kao što smo to gledati radite što u konačnici 551 00:25:07,180 --> 00:25:10,200 će proizvoditi očito Rezultat, razmišljati o uistinu 552 00:25:10,200 --> 00:25:12,962 kako oni to rade jedni, Kako biste mogli opisati. 553 00:25:12,962 --> 00:25:15,045 Zbog toga ponovno su Svi procesi, algoritmi 554 00:25:15,045 --> 00:25:17,090 koje uzimamo zdravo za gotovo, kao čovjeka. 555 00:25:17,090 --> 00:25:22,349 No, vjerojatno ste dugo imali intuicija, dugo prije nego što čak i 556 00:25:22,349 --> 00:25:24,390 mislili o preuzimanju informatika klasa vam 557 00:25:24,390 --> 00:25:27,223 možda su imali intuiciju s koji je za rješavanje problema kao što je ovaj. 558 00:25:27,223 --> 00:25:29,560 No, nakon što prepoznaju obrasci i početi 559 00:25:29,560 --> 00:25:32,407 formalizirati korake s kojima ti si rješavanju tih problema, 560 00:25:32,407 --> 00:25:35,490 vidjet ćete da možete riješiti mnogo zanimljivije i još mnogo složeniji 561 00:25:35,490 --> 00:25:39,190 problemi brzo. 562 00:25:39,190 --> 00:25:42,351 Dakle netko iz publike, što je barem jedan element algoritma 563 00:25:42,351 --> 00:25:43,350 da oni koriste ovdje? 564 00:25:43,350 --> 00:25:44,275 >> PUBLIKA: [nečujan] 565 00:25:44,275 --> 00:25:45,150 Zvučnika: Što je to? 566 00:25:45,150 --> 00:25:47,062 PUBLIKA: Do odijelu. 567 00:25:47,062 --> 00:25:47,770 Zvučnik: Do odijelu. 568 00:25:47,770 --> 00:25:50,630 Dakle, prvo su grupiranje sve od dijamanata zajedno 569 00:25:50,630 --> 00:25:52,560 čini se, sve srca zajedno čini se, 570 00:25:52,560 --> 00:25:56,520 i tako dalje, bez poštovanja za brojeve na karticama. 571 00:25:56,520 --> 00:26:00,900 I sada se pojavljuju, primjerice, treba ih sortiranje po broju. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Vrlo dobro. 574 00:26:08,910 --> 00:26:12,370 >> U redu, tako što će se biti završni korak onda ovdje? 575 00:26:12,370 --> 00:26:16,950 Kada imamo četiri razvrstane odijela, što trebamo učiniti na četiri pilota 576 00:26:16,950 --> 00:26:20,059 da bi se postigao jedan razvrstani palubu, vrlo jednostavno? 577 00:26:20,059 --> 00:26:21,350 Dakle, moramo ih ponovno spojiti. 578 00:26:21,350 --> 00:26:25,160 >> Dakle, tu je zanimljiva ideja da opet, pretpostavljam, je vrlo intuitivno i 579 00:26:25,160 --> 00:26:28,140 Ako ste možda nikada ne bi ošamario koja vrsta naljepnicom na njega. 580 00:26:28,140 --> 00:26:31,900 Ova temeljna ideja o podjeli Problem nije u pola tog vremena, 581 00:26:31,900 --> 00:26:33,410 ali barem na četiri dijela. 582 00:26:33,410 --> 00:26:36,810 Rješavanje prilično osnovi identične probleme 583 00:26:36,810 --> 00:26:40,480 izolacijom međusobno a zatim spajanjem rezultate. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 I, izvrsna, učinjeno. 586 00:26:50,140 --> 00:26:52,140 U redu, veliki okrugli pljesak, ako smo mogli. 587 00:26:52,140 --> 00:26:56,480 >> [Pljesak] 588 00:26:56,480 --> 00:26:59,740 >> Zvučnik: Nemam pojma što ćete učiniti s njima, ali ovdje ide. 589 00:26:59,740 --> 00:27:01,690 Hvala ti puno. 590 00:27:01,690 --> 00:27:04,660 Pa da vidimo, dvije minute i osam sekundi, 591 00:27:04,660 --> 00:27:07,490 Ako želite izazov svoje prijatelje. 592 00:27:07,490 --> 00:27:12,160 Što se onda događa da biti oduzeti to 593 00:27:12,160 --> 00:27:13,830 da možemo utjecati općenito? 594 00:27:13,830 --> 00:27:16,080 Pa, mislim natrag na ovaj niz brojeva, 595 00:27:16,080 --> 00:27:19,060 i prisjetim se neke od pseudocode smo zapisano u prošlosti, 596 00:27:19,060 --> 00:27:22,080 i to je bio pseudocode za rješavanju problema telefonskog imenika. 597 00:27:22,080 --> 00:27:25,150 Čime se u pseudocode I. nabrojani više metodički način 598 00:27:25,150 --> 00:27:28,400 opisati kako sam učinio vrlo intuitivno Ljudsko algoritam dijeljenja telefon 599 00:27:28,400 --> 00:27:31,650 Knjiga na pola, ponavljanje, ponavljanje, ponavljanje, dok ne nađem nekoga poput Mike Smith, 600 00:27:31,650 --> 00:27:33,790 ako je doista u telefonskom imeniku. 601 00:27:33,790 --> 00:27:37,610 >> Ali nekako se koristi ono što ću nazvati Vrlo iterativni pristup ovdje, 602 00:27:37,610 --> 00:27:42,160 u određenom roku linija 8 i 11 linija. 603 00:27:42,160 --> 00:27:46,750 Oni su dokaz iterativni pristup, petlje pristup, 604 00:27:46,750 --> 00:27:49,040 jer to je upravo Ponašanje koje izazivaju. 605 00:27:49,040 --> 00:27:52,910 Ta linija oba kažu ići Linija tri, a možete vrsta 606 00:27:52,910 --> 00:27:55,140 sjetiti da je u svoj mislima kao petlje. 607 00:27:55,140 --> 00:27:59,080 To vam govorim da se vrati do koraka tri i ponavljam opet, i opet, 608 00:27:59,080 --> 00:28:00,010 i opet. 609 00:28:00,010 --> 00:28:04,410 >> No, što ako smo iskoristiti ključnu ideju Ovdje nam nije posljednji put, 610 00:28:04,410 --> 00:28:10,280 i pojednostaviti linije 8 i Linija 11 i njihovi susjedi 611 00:28:10,280 --> 00:28:12,840 kako je upravo to, u žuto. 612 00:28:12,840 --> 00:28:16,480 Nije bitno skraćivanje pseudocode jako puno, 613 00:28:16,480 --> 00:28:20,530 ali je iz temelja se mijenja Priroda mog algoritma. 614 00:28:20,530 --> 00:28:24,220 Ono što sam sada rekao U koraku 7, u koraku 10, 615 00:28:24,220 --> 00:28:29,140 je u potrazi za Mike na isti način, 616 00:28:29,140 --> 00:28:31,580 ali samo u lijevo pola ili desna polovica. 617 00:28:31,580 --> 00:28:33,420 >> Dakle, drugim riječima, ako je Polazim od jednog koraka, 618 00:28:33,420 --> 00:28:36,150 pokupiti telefonski imenik, otvorena sredinom u telefonskom imeniku, pogledati imena, 619 00:28:36,150 --> 00:28:39,010 ako Smith je među Zove se, zovu Mike, inače 620 00:28:39,010 --> 00:28:44,340 ako Smith je ranije u knjizi, korak sedam tražiti Mikea u lijevoj polovici knjige. 621 00:28:44,340 --> 00:28:47,130 Ali ta vrsta osjeća kao to je ostavljajući me na cjedilu, zar ne? 622 00:28:47,130 --> 00:28:49,240 U žuto, je upute, ali kako mi je činiti 623 00:28:49,240 --> 00:28:51,870 tražiti Mikea u lijevo pola telefonskog imenika? 624 00:28:51,870 --> 00:28:54,210 Gdje moram algoritam s kojim sam 625 00:28:54,210 --> 00:28:57,100 možete tražiti nekoga poput Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Pa, to je nas gleda u lice. 627 00:28:58,980 --> 00:29:03,090 Ja doslovno može koristiti isti Program učinkovito ide do vrha 628 00:29:03,090 --> 00:29:06,490 ponovno i ponovno trčanje ista linija koda. 629 00:29:06,490 --> 00:29:10,610 >> Dakle, iako je to trebao osjećati kao malo cikličkom definiciji 630 00:29:10,610 --> 00:29:13,480 gdje ste odgovoriti netko Pitanje je samo kakve pita 631 00:29:13,480 --> 00:29:15,990 isto pitanje opet, Na primjer, zašto, zašto, zašto? 632 00:29:15,990 --> 00:29:21,580 Stvarnost je, jer smo naporno smo kodirani nekoliko posebnih linija, stupanj 4, 633 00:29:21,580 --> 00:29:25,320 koja je, ako i korak 12, koji je učinkovito druga grana, 634 00:29:25,320 --> 00:29:30,120 jer imamo one hitna privremena mjera, Ovaj algoritam će raskinuti ako 635 00:29:30,120 --> 00:29:32,050 pronaći Mikea, ili ako to ne učinimo. 636 00:29:32,050 --> 00:29:36,810 No, u koraku 7 i 10. Sada imamo ono što ćemo nazvati rekurzivni algoritam. 637 00:29:36,810 --> 00:29:40,420 I rekurzija je doista moćan ideja to je malo um savijanje u početku, 638 00:29:40,420 --> 00:29:42,500 da sada možemo primijeniti na sljedeći način. 639 00:29:42,500 --> 00:29:46,600 >> Spoji neka vrsta će biti posljednja vrsta koja gledamo, barem u klasi formalno. 640 00:29:46,600 --> 00:29:50,040 A to je bitno različita od onih prošle tri, a sigurno 641 00:29:50,040 --> 00:29:52,140 posljednja četiri, ako uključimo bogosort. 642 00:29:52,140 --> 00:29:54,810 Evo pseudocode udruži- vrste. 643 00:29:54,810 --> 00:30:00,170 Kada je na ulazu od n elemenata, tako da s obzirom niz veličine N, ako je n manji od 2, 644 00:30:00,170 --> 00:30:01,040 povratak. 645 00:30:01,040 --> 00:30:03,610 Pa zašto moram da razum provjeriti prvi? 646 00:30:03,610 --> 00:30:09,477 Što je implikacija da sam na ruke niz čija duljina je n manji od 2? 647 00:30:09,477 --> 00:30:11,060 To je već riješeno, očito, zar ne? 648 00:30:11,060 --> 00:30:13,640 Zbog popis bilo je jedan element koji je trivijalno 649 00:30:13,640 --> 00:30:15,180 razvrstani jer je Jedino što postoji. 650 00:30:15,180 --> 00:30:18,138 Ili, to je od veličine nula, što znači nema ništa riješiti, pa po prirodi 651 00:30:18,138 --> 00:30:18,720 to je riješeno. 652 00:30:18,720 --> 00:30:20,410 Postoji samo postoji ništa krivo. 653 00:30:20,410 --> 00:30:22,310 Dakle, to je naš tzv osnovni scenarij. 654 00:30:22,310 --> 00:30:24,440 >> To je slično u duhu na ono što smo učinili s Mikeom. 655 00:30:24,440 --> 00:30:26,023 Ako Mike je u telefonskom imeniku, nazovite ga. 656 00:30:26,023 --> 00:30:27,740 Ako on ne postoji, odustati. 657 00:30:27,740 --> 00:30:31,240 To je takozvani osnovni scenarij, kako bi bili sigurni Ovaj algoritam na kraju dan 658 00:30:31,240 --> 00:30:33,540 zaustavit će se u određenim okolnostima. 659 00:30:33,540 --> 00:30:37,890 >> No, ovdje je skok vjere sada, drugo, sortirati lijevu polovicu elemenata, 660 00:30:37,890 --> 00:30:39,740 zatim sortirati pravo polovice elemenata 661 00:30:39,740 --> 00:30:41,189 a zatim spojiti sortirani polovice. 662 00:30:41,189 --> 00:30:43,230 I ovdje gdje se osjeća kao da smo copping van. 663 00:30:43,230 --> 00:30:46,900 Ja sam te pitao za sortiranje n elemenata, a ja sam 664 00:30:46,900 --> 00:30:50,712 govoreći, u redu, nemojte ga sortiranje napustio i sortiranje pravo. 665 00:30:50,712 --> 00:30:52,420 Ali ja govorim jedno druga stvar, a to 666 00:30:52,420 --> 00:30:55,530 je ključna tema čini u intuiciji do sada, 667 00:30:55,530 --> 00:30:57,380 tu je ovo treći korak spajanja. 668 00:30:57,380 --> 00:31:00,430 Koji iako Izgleda tako glupo u duhu, 669 00:31:00,430 --> 00:31:02,320 kao što je samo spojiti stvari zajedno čini 670 00:31:02,320 --> 00:31:05,380 biti ključan korak prema ponovno sastaviti dva problema koji 671 00:31:05,380 --> 00:31:07,330 podijeljeni su u konačnici na pola. 672 00:31:07,330 --> 00:31:12,090 >> Dakle, spajanje vrsta, učinimo to, ako ćete humor ja, s još jednom demonstracije, 673 00:31:12,090 --> 00:31:14,730 samo tako da imamo neke Brojevi raditi. 674 00:31:14,730 --> 00:31:19,470 Mogu li zamijeniti osam stres loptice za osam osoba? 675 00:31:19,470 --> 00:31:29,320 Dobro, o tome kako vam tri, četiri vi U ovom poglavlju, pet, šest, i neka je 676 00:31:29,320 --> 00:31:30,720 ne 7, 8, dođi gore. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 U redu, da je u redu. 679 00:31:36,520 --> 00:31:38,640 Minus 8, tamo idemo, plus 1. 680 00:31:38,640 --> 00:31:39,150 Izvrsno. 681 00:31:39,150 --> 00:31:42,000 Dobro došli gore, ajmo brzo vam dati brojeve. 682 00:31:42,000 --> 00:31:50,800 Broj dva, broj tri, broj četiri, broj pet, šest, sedam i osam. 683 00:31:50,800 --> 00:31:52,140 Ja sam osam ispravno ovaj put. 684 00:31:52,140 --> 00:31:56,390 >> U redu, pa ići naprijed ako bi mogao, i neka je vrsta u izvornom redoslijedu 685 00:31:56,390 --> 00:31:59,810 da smo imali jučer koja je izgledala ovako, ako ne bi smetalo. 686 00:31:59,810 --> 00:32:03,620 I neka je to učiniti ispred stola. 687 00:32:03,620 --> 00:32:06,510 U redu, tako spojiti vrsta. 688 00:32:06,510 --> 00:32:08,820 Ovo je mjesto gdje to ide da bi dobili kakav zanimljiv, 689 00:32:08,820 --> 00:32:12,800 jer čini mi se da se davanje sebe tako puno manje informacija i danas. 690 00:32:12,800 --> 00:32:15,149 >> Dakle, spajanje svojevrsni prije svega na ulazu od n elemenata, 691 00:32:15,149 --> 00:32:18,440 i očito nije manji od dva, to je osam, tako da imam više posla. 692 00:32:18,440 --> 00:32:21,140 Tako sada psihički smo kao klasa sada su u grani drugo, 693 00:32:21,140 --> 00:32:22,540 što znači tri koraka. 694 00:32:22,540 --> 00:32:25,017 Prvo, moram sortirati lijeva polovica elemenata. 695 00:32:25,017 --> 00:32:26,350 Pa kako mogu ići o događaj ovaj? 696 00:32:26,350 --> 00:32:28,950 Pa, ja ću vrsta mentalno podijelite popis ovdje, 697 00:32:28,950 --> 00:32:30,700 vi ne morate fizički kretati, a ja sam 698 00:32:30,700 --> 00:32:33,180 će se fokusirati samo na lijeva polovica elemenata ovdje. 699 00:32:33,180 --> 00:32:36,770 Pa kako ću ići oko sortiranja Popis je sada veličine četiri? 700 00:32:36,770 --> 00:32:38,730 Što je moj algoritam? 701 00:32:38,730 --> 00:32:42,580 Prvo sam provjeriti je n manji od dvije, ne, pa prešli na drugi blok ponovno. 702 00:32:42,580 --> 00:32:43,900 Sortiranje napustio polovicu elemenata. 703 00:32:43,900 --> 00:32:45,608 >> Tako sada opet, mentalno, i to je mjesto gdje 704 00:32:45,608 --> 00:32:49,550 morate prikupiti puno mentalno povijest, ako hoćete. 705 00:32:49,550 --> 00:32:51,940 Sada sam sortiranja lijevu polovica lijeve polovine. 706 00:32:51,940 --> 00:32:57,000 U redu, tako da sada zovem moj isti spajanje sortiranja algoritam, je n manje od dva? 707 00:32:57,000 --> 00:33:00,590 Ne, to je dva, pa moram sortirati lijeva polovica, a desna polovica. 708 00:33:00,590 --> 00:33:02,042 Dakle, ovdje mi ići, sortiranje lijevu polovicu. 709 00:33:02,042 --> 00:33:03,750 Zašto ne samo uzeti jedan korak naprijed. 710 00:33:03,750 --> 00:33:04,415 Koje je tvoje ime? 711 00:33:04,415 --> 00:33:04,860 >> PUBLIKA: Darren. 712 00:33:04,860 --> 00:33:05,260 >> Govornik: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan je istupio. 714 00:33:06,040 --> 00:33:06,748 >> PUBLIKA: Darren. 715 00:33:06,748 --> 00:33:09,000 Govornik: Darren, učinjeno. 716 00:33:09,000 --> 00:33:10,090 Jeste li rekli Darren ili Dan? 717 00:33:10,090 --> 00:33:10,550 >> PUBLIKA: Darren. 718 00:33:10,550 --> 00:33:11,216 >> Govornik: Darren. 719 00:33:11,216 --> 00:33:14,422 U redu, Darren je stao prema naprijed, a on je sada riješeno. 720 00:33:14,422 --> 00:33:16,130 A to je gotovo besmisleno tvrdnja, zar ne? 721 00:33:16,130 --> 00:33:18,862 Ja stvarno ne izgleda da će postizanje ništa, ali idemo dalje. 722 00:33:18,862 --> 00:33:20,820 Sada neka mi sortirati pravo polovica elemenata. 723 00:33:20,820 --> 00:33:21,200 Koje je tvoje ime? 724 00:33:21,200 --> 00:33:21,690 >> PUBLIKA: Luka. 725 00:33:21,690 --> 00:33:22,273 >> Govornik: Luka. 726 00:33:22,273 --> 00:33:23,400 Hajde, korak naprijed. 727 00:33:23,400 --> 00:33:25,640 Gotovo sam razvrstani Luke. 728 00:33:25,640 --> 00:33:28,570 Lijeva polovica sada sortirati i desna polovica je sada riješeno, 729 00:33:28,570 --> 00:33:30,770 ali opet, tu je ključni korak ovdje. 730 00:33:30,770 --> 00:33:32,940 Što mi je pored trebate učiniti? 731 00:33:32,940 --> 00:33:33,941 Spoji sortirane polovice. 732 00:33:33,941 --> 00:33:36,648 Sada ćemo samo Svi natrag i naprijed na ovaj način, 733 00:33:36,648 --> 00:33:38,620 jer nekako je potrebno Neki brisani prostor. 734 00:33:38,620 --> 00:33:40,411 To je gotovo kao one Dečki su na stolu, 735 00:33:40,411 --> 00:33:42,460 i ja trebam malo mjesta kako bi ih se kretati dalje. 736 00:33:42,460 --> 00:33:44,170 Tako ću spojiti vi gledanjem 737 00:33:44,170 --> 00:33:45,960 na lijevoj polovici i desnu polovicu. 738 00:33:45,960 --> 00:33:48,740 A tko je očito na prvom mjestu, lijevo ili desno pola pola? 739 00:33:48,740 --> 00:33:52,710 Dakle, pravo na pola, pa krenimo Luka tijekom Ovdje se Darren je prvobitni položaj. 740 00:33:52,710 --> 00:33:57,640 A sada spojiti svoju lijevu polovicu, Darren će se premjestiti tamo. 741 00:33:57,640 --> 00:33:59,750 >> Tako se osjeća kao gotovo Učinak mjehurić sortirati, 742 00:33:59,750 --> 00:34:02,482 ali moj temeljni algoritam, vrlo različite ovaj put. 743 00:34:02,482 --> 00:34:04,815 No, sada je mjesto gdje se stvari malo neugodno zbog tebe 744 00:34:04,815 --> 00:34:06,810 moram premotati psihički gdje sam ugasiti. 745 00:34:06,810 --> 00:34:09,893 Upravo sam spojio razvrstanih polovice, što znači da sam gdje u mom algoritmu? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Moram izdvojiti desnu polovicu, zar ne? 748 00:34:13,770 --> 00:34:15,910 >> Ako unatrag, doslovno Na videu, vi ćete 749 00:34:15,910 --> 00:34:18,339 vidim da smo došli do toga točka Luke i Darren 750 00:34:18,339 --> 00:34:21,370 sortiranje lijevi polovica lijeve polovine. 751 00:34:21,370 --> 00:34:23,430 Onda smo spojili one razvrstane polovice, koja 752 00:34:23,430 --> 00:34:27,941 znači sljedeći korak je vrsta Pravo polovica lijeve polovine. 753 00:34:27,941 --> 00:34:29,649 U redu, pa neka je to učiniti brže. 754 00:34:29,649 --> 00:34:33,282 U redu, šest, ja ću tvrditi Sada su razvrstani, dođi naprijed. 755 00:34:33,282 --> 00:34:33,990 Koje je tvoje ime? 756 00:34:33,990 --> 00:34:34,589 >> PUBLIKA: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> Govornik: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano je sada riješeno. 759 00:34:36,010 --> 00:34:36,450 A kako se ti zoveš? 760 00:34:36,450 --> 00:34:37,080 >> PUBLIKA: Alex. 761 00:34:37,080 --> 00:34:38,379 >> Zvučnik: Alex je sada riješeno. 762 00:34:38,379 --> 00:34:40,750 Lijeva polovica, desna polovica, što je završni korak? 763 00:34:40,750 --> 00:34:41,250 Spoji. 764 00:34:41,250 --> 00:34:44,310 Prilično trivijalna, pa sam će se stopiti u šest, 765 00:34:44,310 --> 00:34:46,930 uzeti jedan korak natrag, osam, uzeti jedan korak natrag. 766 00:34:46,930 --> 00:34:49,530 I sada primjetiti to je korisne takeaway, što 767 00:34:49,530 --> 00:34:53,930 sada je istina o lijevoj polovici Popis, neovisno o tome kako smo počeli? 768 00:34:53,930 --> 00:34:55,090 To je riješeno. 769 00:34:55,090 --> 00:34:57,750 >> Sada to nije razvrstani u Veliki shemi stvari, 770 00:34:57,750 --> 00:35:00,250 ali to je razvrstani neovisno druge polovice. 771 00:35:00,250 --> 00:35:04,100 Sad, što je korak sam ja o tome ako držim premotavanja kako je priča započela? 772 00:35:04,100 --> 00:35:05,680 Sada moram sortirati desnu polovicu. 773 00:35:05,680 --> 00:35:07,630 Dakle, sada smo put natrag u početak priče, 774 00:35:07,630 --> 00:35:08,921 i učinimo to brže. 775 00:35:08,921 --> 00:35:11,320 Tako ću sortiranje Pravo da polovica cijelog popisa. 776 00:35:11,320 --> 00:35:13,060 Što je sljedeći korak? 777 00:35:13,060 --> 00:35:15,840 Sortirati lijevu polovicu desnoj polovici. 778 00:35:15,840 --> 00:35:18,715 Sortirati lijevu polovicu lijeva polovica desnoj polovici. 779 00:35:18,715 --> 00:35:19,590 A kako se ti zoveš? 780 00:35:19,590 --> 00:35:20,230 >> PUBLIKA: Omar. 781 00:35:20,230 --> 00:35:21,970 >> Govornik: Omar, korak naprijed, učinjeno. 782 00:35:21,970 --> 00:35:22,860 Lijeva polovica sortira. 783 00:35:22,860 --> 00:35:23,330 A kako se ti zoveš? 784 00:35:23,330 --> 00:35:23,820 >> PUBLIKA: Chris. 785 00:35:23,820 --> 00:35:25,620 >> Govornik: Chris, uzeti jedan korak prema naprijed, sada su razvrstani. 786 00:35:25,620 --> 00:35:27,010 Ono što je ključni korak sad? 787 00:35:27,010 --> 00:35:27,510 Spoji. 788 00:35:27,510 --> 00:35:30,509 Dakle, jedan će se spojiti na svoje mjesto Ovdje, ako bi mogao uzeti jedan korak natrag, 789 00:35:30,509 --> 00:35:32,930 , a tri će uzeti jedan korak nazad, spojiti. 790 00:35:32,930 --> 00:35:38,080 Dakle, lijeva polovica desna polovica, sada je riješeno. 791 00:35:38,080 --> 00:35:41,747 Iskreno, ovaj algoritam se osjeća kao mi se troši daleko više vremena nego prije, 792 00:35:41,747 --> 00:35:44,830 ali ako je to učinio u stvarnom vremenu, mi ćemo vidjeti što su Zaključci će biti. 793 00:35:44,830 --> 00:35:47,970 Sada sam ovdje, zar ne polovica desnoj polovici, 794 00:35:47,970 --> 00:35:50,170 neka mi ići naprijed i sortiranje lijevu polovicu. 795 00:35:50,170 --> 00:35:51,482 Korak naprijed, kako se ti zoveš? 796 00:35:51,482 --> 00:35:52,190 PUBLIKA: Ramsey. 797 00:35:52,190 --> 00:35:53,210 Zvučnik: Ramsey sada riješeno. 798 00:35:53,210 --> 00:35:53,570 Koje je tvoje ime? 799 00:35:53,570 --> 00:35:54,200 >> PUBLIKA: Marina. 800 00:35:54,200 --> 00:35:57,033 >> Zvučnik: Marina sada razvrstani kao Pa, ako se uzme jedan korak naprijed. 801 00:35:57,033 --> 00:36:00,690 Ključni korak ovdje je sada spojiti, ja sam će se iščupati iz moje dvije liste, 802 00:36:00,690 --> 00:36:01,720 lijevo i desno. 803 00:36:01,720 --> 00:36:05,150 Pet će biti na prvom mjestu, i sedam će doći sljedeći. 804 00:36:05,150 --> 00:36:06,410 I opet, to je namjerno. 805 00:36:06,410 --> 00:36:08,535 Činjenica da se oni uzimati korake prema naprijed i natrag 806 00:36:08,535 --> 00:36:12,997 je značilo da predstavljaju da ne možemo učinite ovaj algoritam na mjestu tako lako 807 00:36:12,997 --> 00:36:15,830 kao mjehur vrste, i odabir vrste, i umetanje svojevrsni gdje smo upravo 808 00:36:15,830 --> 00:36:16,960 čuvaju zamjene ljude. 809 00:36:16,960 --> 00:36:19,940 Doslovno sam potrebna neka vrsta od ogrebotina rada u kojem 810 00:36:19,940 --> 00:36:21,827 staviti te ljude dok sam obaviti spajanje, 811 00:36:21,827 --> 00:36:23,410 i onda ja mogu ih vratiti na mjesto. 812 00:36:23,410 --> 00:36:27,260 I to je ključno, jer sam koristeći novi resurs, prostor, ne samo vrijeme. 813 00:36:27,260 --> 00:36:28,270 >> U redu, ovo je nevjerojatno. 814 00:36:28,270 --> 00:36:32,050 Lijeva polovica razvrstani, desna polovica je sortirani, sada se taj ključ spajanjem korak. 815 00:36:32,050 --> 00:36:33,450 Kako ću spojiti ovo? 816 00:36:33,450 --> 00:36:35,470 Dakle, ako ćete slijediti moj lijeva ruka i desna ruka, 817 00:36:35,470 --> 00:36:38,930 Ja ću istaknuti svoju lijevu ruku na lijevoj polovici, moja desna ruka 818 00:36:38,930 --> 00:36:42,680 Na desnoj polovici, a sada moram odlučiti korak po korak kojeg se stapaju u. 819 00:36:42,680 --> 00:36:44,650 Tko očito dolazi prvo? 820 00:36:44,650 --> 00:36:45,150 Broj jedan. 821 00:36:45,150 --> 00:36:47,327 Pa hajde ovamo, ovdje je naš notes. 822 00:36:47,327 --> 00:36:49,910 Tako je sada broj jedan, i obavijest Što ću učiniti s moje desne strane, 823 00:36:49,910 --> 00:36:54,152 Idem da se presele desnoj ruci jedan korak više do točke broj tri, 824 00:36:54,152 --> 00:36:55,860 i sad moram napraviti Istom odlukom. 825 00:36:55,860 --> 00:36:58,387 I zapravo stoje pravo u Prednji dio Luke ovdje ako bi mogao, 826 00:36:58,387 --> 00:36:59,720 jer ovo je naša notes. 827 00:36:59,720 --> 00:37:00,610 Dakle, tko dolazi sljedeći? 828 00:37:00,610 --> 00:37:05,000 Imamo Luka s brojem dva ili Chris s brojem tri. 829 00:37:05,000 --> 00:37:07,460 Očito Luka, broj dva, tako da ovdje dolaze. 830 00:37:07,460 --> 00:37:11,270 >> Ali mi je lijeva ruka sada će povećavati do točke na Darren, 831 00:37:11,270 --> 00:37:15,160 i ovdje je ključno oduzima s spajanjem, idem da bi to, 832 00:37:15,160 --> 00:37:17,340 Očito, ako ste ljubazni od slijede logiku. 833 00:37:17,340 --> 00:37:19,670 No ruke su mi nikada ići unatrag, 834 00:37:19,670 --> 00:37:23,861 što znači da sam samo ikada kreće se napustio s mojim pretapajuĘem procesa, 835 00:37:23,861 --> 00:37:26,360 a to će biti ključ Naša analiza u samo trenutak. 836 00:37:26,360 --> 00:37:27,859 >> Dakle, sada ćemo završiti ovo vrlo brzo. 837 00:37:27,859 --> 00:37:31,650 Dakle, tri dolazi sljedeći, zatim četiri dolazi sljedeći, 838 00:37:31,650 --> 00:37:38,750 a sada pet dolazi sljedeći, a zatim šest, i sedam godina, a onda je konačno osam. 839 00:37:38,750 --> 00:37:42,960 Osjeća kao najsporijim algoritma još uvijek, ali ne i ako smo zapravo 840 00:37:42,960 --> 00:37:45,510 pokrenuti ga na istoj vrsti brzine sata, tako da se 841 00:37:45,510 --> 00:37:48,106 govoriti, s istom otkucava sat kao i prije. 842 00:37:48,106 --> 00:37:48,605 Zašto? 843 00:37:48,605 --> 00:37:51,100 Pa, neka je uzme pogled na krajnji rezultat. 844 00:37:51,100 --> 00:37:56,990 >> Vratimo se ovamo, neka me podići demonstraciju vizualno 845 00:37:56,990 --> 00:37:59,030 onoga što smo upravo učinili. 846 00:37:59,030 --> 00:38:06,110 Povećavanje ovdje, na ovom Stranica ovdje, govori Firefox 847 00:38:06,110 --> 00:38:08,200 da želimo stati u red u tom okviru, ajmo 848 00:38:08,200 --> 00:38:11,260 kažu mjehurić vrsta, s kojom mi smo sada dobro poznato, 849 00:38:11,260 --> 00:38:14,130 Izbor sortirati, što je još jedan prilično jednostavan jedan, 850 00:38:14,130 --> 00:38:18,250 a sada današnja spajanje sorta, koja će biti naš vrhunac kraj. 851 00:38:18,250 --> 00:38:21,530 Razlog je to što je toliko mnogo dulje ovdje s ljudima i ja verbalno je, 852 00:38:21,530 --> 00:38:23,480 Očito, ja sam objašnjavajući svaki korak. 853 00:38:23,480 --> 00:38:26,920 Ali ako jednostavno izvršiti to, mnogo kao što smo učinili mjehur sortiranje i odabir 854 00:38:26,920 --> 00:38:30,890 Sortiranje ne samo vizualno, sat koliko učinkovitije 855 00:38:30,890 --> 00:38:33,330 to Utjecati od podjela i osvajanje 856 00:38:33,330 --> 00:38:39,150 može kad se odnosi na skupu koji je Nije čak veličine osam, ali čak i mnogo, 857 00:38:39,150 --> 00:38:39,970 puno veći. 858 00:38:39,970 --> 00:38:44,585 Dajem vam spojiti sortirati, rame uz strana s tim drugim sredinama. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 To se događa da se bolno brzo, a završetak 861 00:38:58,530 --> 00:39:00,890 nije osobito vrhunac, oni samo završiti razvrstani. 862 00:39:00,890 --> 00:39:05,280 No, ključno je da se oduzima Vidi kako je mnogo brže spajanje svojevrsni 863 00:39:05,280 --> 00:39:08,110 bio je, osim ako ne mislite da sam samo vrsta petljaju s vama. 864 00:39:08,110 --> 00:39:13,100 Ako smo to učinili posljednji put, Idemo Reload this, idemo natrag 865 00:39:13,100 --> 00:39:14,960 i odaberite balon vrsta, i samo za slatkiš, 866 00:39:14,960 --> 00:39:17,330 ajmo birati umetanje sortirati, samo za dobru mjeru. 867 00:39:17,330 --> 00:39:20,020 I ovaj put opet, ajmo odaberite spajanja vrsta i neka 868 00:39:20,020 --> 00:39:21,595 zapravo pokrenuti ove rame uz rame. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> I to nije, zapravo, slučajnost. 871 00:39:26,930 --> 00:39:31,140 Ono što sam uspješno učinio je da sam podijeljeni moj ulaz na pola, opet, 872 00:39:31,140 --> 00:39:32,240 i opet, i opet. 873 00:39:32,240 --> 00:39:35,590 I tu je samo toliko puta možete podijeliti svoj ulaz na polovice, lijevo 874 00:39:35,590 --> 00:39:36,240 i desno. 875 00:39:36,240 --> 00:39:39,425 Koja je formula koja držimo gledajući koji opisuje podjelu na pola 876 00:39:39,425 --> 00:39:41,050 opet, i opet, i opet, i opet? 877 00:39:41,050 --> 00:39:41,890 >> PUBLIKA: Prijavite n. 878 00:39:41,890 --> 00:39:42,760 >> Zvučnik: Prijavite n. 879 00:39:42,760 --> 00:39:46,300 Ali tu je još jedna ključni korak, Ovaj algoritam nije prijavite n koraka. 880 00:39:46,300 --> 00:39:48,992 Ako to su samo prijavite n koraka, mi bi se u istom problemu 881 00:39:48,992 --> 00:39:51,200 kao i prije, gdje ne možemo biti uvjerim da je sve riješeno. 882 00:39:51,200 --> 00:39:54,480 Morate minimalno pogledati n elemenata kako bi bili sigurni n elementi su razvrstani, 883 00:39:54,480 --> 00:39:55,950 inače je skok vjere. 884 00:39:55,950 --> 00:39:59,810 >> Dakle, to je minimalno dnevnik n koraka, ali Što je s tom ključnom pretapajuĘem korak 885 00:39:59,810 --> 00:40:04,370 gdje sam spojio moje lijeve i desne polovice polovice i hodao po pozornici? 886 00:40:04,370 --> 00:40:06,980 Koliko koraka je da se spojiti? 887 00:40:06,980 --> 00:40:10,150 To je n, ali nisam baš spojiti posljednji put. 888 00:40:10,150 --> 00:40:15,089 Na svakom od tih ugniježđena poziva, na svakoj od onih ugniježđena spaja, ja još uvijek razvrstani. 889 00:40:15,089 --> 00:40:18,380 Spojio sam ove dvije dečki, onda ova dva Dečki, a zatim su dvojica i tako dalje. 890 00:40:18,380 --> 00:40:19,955 >> Pa nisam spajanjem opet, i opet. 891 00:40:19,955 --> 00:40:20,580 Koliko puta? 892 00:40:20,580 --> 00:40:23,510 Dakle, svaki put kad bih podijeliti Popis na pola, ja sam pisma. 893 00:40:23,510 --> 00:40:25,460 Podijeljeno je popis na pola, napraviti spajanje. 894 00:40:25,460 --> 00:40:28,570 Dakle, ako dijeljenjem popis može biti učinjeno dnevnik n puta, 895 00:40:28,570 --> 00:40:33,880 i spajanje u konačnici vodi n koraka, što bi moglo biti sad gornja 896 00:40:33,880 --> 00:40:37,000 vezan na trčanje Vrijeme našeg algoritma? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> I doista, to je ono što ostvarili smo ovdje. 899 00:40:40,560 --> 00:40:44,650 Dakle, mislite da ste vidjeli vizualno kada te tri stvari pokrenuti rame uz rame 900 00:40:44,650 --> 00:40:47,930 je n kvadrat protiv n kvadrat od n log n. 901 00:40:47,930 --> 00:40:51,010 Koji je bitno vidjet ćemo, ne samo danas, ali u budućnosti, 902 00:40:51,010 --> 00:40:52,760 je puno, puno brže. 903 00:40:52,760 --> 00:40:56,010 Pljesak za ove dečke, Ja ću ih nagraditi sa stresom loptice. 904 00:40:56,010 --> 00:41:00,260 Idemo odgodi danas ovdje, a mi ćemo vas vidjeti u ponedjeljak. 905 00:41:00,260 --> 00:41:02,255