1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [Glazba svira] 3 00:00:10,800 --> 00:00:13,500 DAVID Malan: U redu. 4 00:00:13,500 --> 00:00:14,670 U redu, dobrodošao natrag. 5 00:00:14,670 --> 00:00:18,120 Dakle, ovo je 4. tjedan, početak tome, već. 6 00:00:18,120 --> 00:00:21,320 A vi ćete se prisjetiti da je prošlog tjedna, stavili smo kodirati stranu za samo malo 7 00:00:21,320 --> 00:00:24,240 i počeli smo razgovarati malo više na visokoj razini, o stvarima kao što su 8 00:00:24,240 --> 00:00:28,130 pretraživanje i sortiranje, koji iako Nešto jednostavne ideje, su 9 00:00:28,130 --> 00:00:31,840 Predstavnik jedne klase problema ćete početi rješavati posebno 10 00:00:31,840 --> 00:00:34,820 kao što počnete razmišljati o finalu projekti i zanimljivi rješenja što 11 00:00:34,820 --> 00:00:36,760 Možda ćete morati stvarnim problemima. 12 00:00:36,760 --> 00:00:39,490 Sada bubble sortiranje bio je jedan od najjednostavnijih takve algoritme, i to 13 00:00:39,490 --> 00:00:42,900 radio tako da te male brojeve s popisa ili u niz vrste 14 00:00:42,900 --> 00:00:46,530 mjehurić svoj put do vrha, a Veliki broj presele svoj put do 15 00:00:46,530 --> 00:00:47,930 kraj tog popisa. 16 00:00:47,930 --> 00:00:50,650 >> I podsjetiti da smo mogli vizualizirati bubble sortiranje malo 17 00:00:50,650 --> 00:00:52,310 nešto poput ovoga. 18 00:00:52,310 --> 00:00:53,640 Zato mi dopustite da ići naprijed i kliknite Start. 19 00:00:53,640 --> 00:00:55,350 Ja sam odabrao mjehurić vrsta. 20 00:00:55,350 --> 00:00:58,920 A ako se prisjetiti da je jači plava linije predstavljaju velike brojeve, male 21 00:00:58,920 --> 00:01:03,300 plave linije predstavljaju male brojeve, kao ćemo proći kroz to opet i opet i 22 00:01:03,300 --> 00:01:07,680 opet, uspoređujući dvije prečke jedni pored drugi u crvenom, idemo na swap 23 00:01:07,680 --> 00:01:11,010 Najveći i najmanji, ako oni su izvan funkcije. 24 00:01:11,010 --> 00:01:14,150 >> Dakle, to će ići na i ići na i otići na, i vidjet ćete da je veći 25 00:01:14,150 --> 00:01:16,700 elementi su čineći njihovu putu u pravo, a manji elementi 26 00:01:16,700 --> 00:01:17,900 čineći svoj put s lijeve strane. 27 00:01:17,900 --> 00:01:21,380 No, počeli smo kvantificirati učinkovitost, 28 00:01:21,380 --> 00:01:22,970 Kvaliteta ovog algoritma. 29 00:01:22,970 --> 00:01:25,200 A mi je rekao da je u najgorem slučaj, ovaj algoritam je 30 00:01:25,200 --> 00:01:27,940 otprilike koliko koraka? 31 00:01:27,940 --> 00:01:28,980 >> Dakle, n kvadrat. 32 00:01:28,980 --> 00:01:30,402 A što je n? 33 00:01:30,402 --> 00:01:31,650 >> PUBLIKA: Broj elemenata. 34 00:01:31,650 --> 00:01:32,790 >> DAVID Malan: Tako je n broj elemenata. 35 00:01:32,790 --> 00:01:33,730 I tako ćemo to često. 36 00:01:33,730 --> 00:01:36,650 Svaki put kada želimo govoriti o veličini nekog problema ili veličini 37 00:01:36,650 --> 00:01:39,140 ulazna, odnosno iznos od vrijeme koje je potrebno za izradu izlaza, mi ćemo jednostavno 38 00:01:39,140 --> 00:01:41,610 generalizirati god Ulaz je, kao n. 39 00:01:41,610 --> 00:01:45,970 Dakle, natrag u tjednu 0, broj stranice u imeniku je n. 40 00:01:45,970 --> 00:01:47,550 Broj studenata u sobi je n. 41 00:01:47,550 --> 00:01:49,630 Dakle, ovdje je, također, da smo nakon da je uzorak. 42 00:01:49,630 --> 00:01:52,800 >> Sada n kvadrat nije osobito brzo, tako da smo pokušali učiniti bolje. 43 00:01:52,800 --> 00:01:55,970 I tako smo gledali na nekoliko drugi algoritama, među kojima 44 00:01:55,970 --> 00:01:57,690 Izbor su neka vrsta. 45 00:01:57,690 --> 00:01:59,180 Dakle, izbor je svojevrsni malo drugačiji. 46 00:01:59,180 --> 00:02:03,130 Bilo je gotovo jednostavnije, usudio bih se reći, gdje sam započeo na početku 47 00:02:03,130 --> 00:02:06,740 Popis naših volontera, a ja samo jednom i opet i opet otišao do 48 00:02:06,740 --> 00:02:10,060 Popis, čupanje najmanji Element na vrijeme i da ga stavite ili 49 00:02:10,060 --> 00:02:13,040 ju na početku popisa. 50 00:02:13,040 --> 00:02:16,410 >> Ali to je, kada smo počeli razmišljati kroz matematiku i veći 51 00:02:16,410 --> 00:02:19,860 Slika, razmišljao koliko puta Htjela sam natrag i naprijed i natrag 52 00:02:19,860 --> 00:02:24,090 i naprijed, rekli smo u najgorem slučaju, Izbor sortiranje, također, bio je ono? 53 00:02:24,090 --> 00:02:24,960 n kvadrat. 54 00:02:24,960 --> 00:02:27,490 Sada u stvarnom svijetu, to bi moglo zapravo biti marginalno brži. 55 00:02:27,490 --> 00:02:30,620 Jer opet, nisam morati držati zaostaje kada sam razvrstani 56 00:02:30,620 --> 00:02:31,880 najmanji elementi. 57 00:02:31,880 --> 00:02:35,090 No, ako mislimo o vrlo velikom n, i ako vrsta napraviti iz matematike kao 58 00:02:35,090 --> 00:02:39,170 Ja sam na brodu, s n kvadrat minus nešto, sve ostalo 59 00:02:39,170 --> 00:02:41,850 osim n kvadrat, jednom n dobiva stvarno velik, ne 60 00:02:41,850 --> 00:02:42,850 stvarno obzira koliko. 61 00:02:42,850 --> 00:02:45,470 Dakle, kao računalnih znanstvenika, mi vrsta zažmiriti na manji 62 00:02:45,470 --> 00:02:49,220 čimbenici i usredotočiti se samo na faktor u izraz koji će napraviti 63 00:02:49,220 --> 00:02:50,330 Najveća razlika. 64 00:02:50,330 --> 00:02:52,840 >> Pa, na kraju, tražili smo kod unosa vrste. 65 00:02:52,840 --> 00:02:56,620 I to je bila slična u duhu, ali nego proći kroz iterativno i 66 00:02:56,620 --> 00:03:01,250 odaberite najmanji element na jednu Vrijeme, umjesto da sam uzeo ruku da sam 67 00:03:01,250 --> 00:03:04,070 riješeno, a ja sam odlučio, sve Dobro, vi pripadate ovdje. 68 00:03:04,070 --> 00:03:06,160 Onda sam se preselio na sljedeći elementa i odlučio da on ili 69 00:03:06,160 --> 00:03:07,470 ona je pripadala ovdje. 70 00:03:07,470 --> 00:03:08,810 A onda sam se preselio na i na. 71 00:03:08,810 --> 00:03:11,780 I ja bi se, usput, pomak te tipove kako bi se 72 00:03:11,780 --> 00:03:13,030 napravite mjesta za njih. 73 00:03:13,030 --> 00:03:16,880 Znači, to je neka vrsta mentalnih preokret od odabira vrste, koje smo 74 00:03:16,880 --> 00:03:18,630 naziva unosa vrsta. 75 00:03:18,630 --> 00:03:20,810 >> Dakle, ove teme koje se javljaju u stvarnom svijetu. 76 00:03:20,810 --> 00:03:23,640 Samo prije nekoliko godina, kada je izvjesno Senator je bio u utrci za predsjednika, 77 00:03:23,640 --> 00:03:27,160 Eric Schmidt, u to vrijeme predsjednik Uprave Google, zapravo imali priliku 78 00:03:27,160 --> 00:03:28,040 da ga intervjuirati. 79 00:03:28,040 --> 00:03:32,010 I mislili smo da ćemo podijeliti ovaj YouTube clip za vas ovdje, ako smo mogli okrenuti prema gore 80 00:03:32,010 --> 00:03:32,950 volumen. 81 00:03:32,950 --> 00:03:39,360 >> [Video reprodukciju] 82 00:03:39,360 --> 00:03:44,620 >> -Sada, senatore, da ste ovdje na Googleu, a ja volim misliti predsjedništva 83 00:03:44,620 --> 00:03:46,042 kao intervju za posao. 84 00:03:46,042 --> 00:03:47,770 >> [Smijeh] 85 00:03:47,770 --> 00:03:50,800 >> -Sada je teško dobiti posao kao predsjednika. 86 00:03:50,800 --> 00:03:52,480 A što prolaziš rigors sada. 87 00:03:52,480 --> 00:03:54,330 Također je teško dobiti posao u Googleu. 88 00:03:54,330 --> 00:03:59,610 Imamo pitanja i tražimo naši kandidati pitanja. 89 00:03:59,610 --> 00:04:02,250 I to je jedna od Larry Schwimmer. 90 00:04:02,250 --> 00:04:05,325 >> [Smijeh] 91 00:04:05,325 --> 00:04:06,400 -Vi mislite da se šalim? 92 00:04:06,400 --> 00:04:08,750 To je upravo ovdje. 93 00:04:08,750 --> 00:04:12,110 Što je najučinkovitiji način da se sortirati milijun dvije bitne cijele brojeve? 94 00:04:12,110 --> 00:04:15,810 >> [Smijeh] 95 00:04:15,810 --> 00:04:18,260 >> -Pa, uh - 96 00:04:18,260 --> 00:04:19,029 >> -Žao mi je. 97 00:04:19,029 --> 00:04:19,745 Možda smo trebali - 98 00:04:19,745 --> 00:04:21,000 >> -Ne, ne, ne, ne, ne. 99 00:04:21,000 --> 00:04:21,470 >> -To nije - 100 00:04:21,470 --> 00:04:22,185 OK. 101 00:04:22,185 --> 00:04:25,328 >> -Mislim da bi neka vrsta balon biti krivi način da ide. 102 00:04:25,328 --> 00:04:26,792 >> [Smijeh] 103 00:04:26,792 --> 00:04:28,510 >> [Navijanje i PLJESAK] 104 00:04:28,510 --> 00:04:31,211 >> -Ma daj, koji je rekao mu ovo? 105 00:04:31,211 --> 00:04:32,155 OK. 106 00:04:32,155 --> 00:04:33,350 >> [END video reprodukciju] 107 00:04:33,350 --> 00:04:35,070 >> DAVID Malan: Tako da ste ga imati. 108 00:04:35,070 --> 00:04:39,600 Tako smo počeli kvantificirati te trčanje puta, da tako kažem, s nešto 109 00:04:39,600 --> 00:04:43,480 zove asimptotska zapis, što je Samo se odnosi na naše vrste okreće 110 00:04:43,480 --> 00:04:47,420 slijep na one manje čimbenika i Samo gleda u vrijeme rada, 111 00:04:47,420 --> 00:04:51,250 obavljanje tih algoritama, kao n dobiva stvarno veliki tijekom vremena. 112 00:04:51,250 --> 00:04:55,110 I tako smo uveli veliki O. i veliki O- predstavljao nešto što smo mislili 113 00:04:55,110 --> 00:04:57,000 kao gornja granica. 114 00:04:57,000 --> 00:04:59,570 I zapravo, Barry, možemo sniziti od mic malo? 115 00:04:59,570 --> 00:05:01,040 >> Mislili smo da je to gornja granica. 116 00:05:01,040 --> 00:05:04,710 Tako veliko O od n na kvadrat znači da je u najgorem slučaju, nešto poput 117 00:05:04,710 --> 00:05:07,780 Izbor svojevrsni bi potrajati n kvadratna korake. 118 00:05:07,780 --> 00:05:10,310 Ili nešto poput umetanja vrstom bi n kvadratna koraka. 119 00:05:10,310 --> 00:05:15,150 Sada za nešto poput umetanja sortiranje, što je najgori slučaj? 120 00:05:15,150 --> 00:05:18,200 S obzirom na niz, što je najgore mogući scenarij koji bi mogli naći 121 00:05:18,200 --> 00:05:20,650 se suočavaju s? 122 00:05:20,650 --> 00:05:21,860 >> To je potpuno unatrag, zar ne? 123 00:05:21,860 --> 00:05:24,530 Jer ako je to potpuno unatrag, što morate učiniti puno posla. 124 00:05:24,530 --> 00:05:26,420 Jer, ako ste potpuno unatrag, ti si idući u nađi 125 00:05:26,420 --> 00:05:28,840 Najveći elementa ovdje, iako ona pripada tamo dolje. 126 00:05:28,840 --> 00:05:31,140 Tako ćeš reći, ok, na ovaj trenutak u vremenu, da pripadam ovdje, 127 00:05:31,140 --> 00:05:32,310 tako da ga ostavi na miru. 128 00:05:32,310 --> 00:05:35,425 >> Tada ćete shvatiti, oh, damn, ja moram premjestiti ovaj nešto manji element 129 00:05:35,425 --> 00:05:36,470 lijevo od vas. 130 00:05:36,470 --> 00:05:38,770 Onda moram to ponoviti i opet i opet. 131 00:05:38,770 --> 00:05:41,410 A ako sam išao naprijed i natrag, što bi vrsta osjetiti izvedbu 132 00:05:41,410 --> 00:05:45,540 da je algoritam, jer stalno sam ja miješanje svima ostalima dolje 133 00:05:45,540 --> 00:05:46,510 Niz kako bi napravili mjesta za njega. 134 00:05:46,510 --> 00:05:47,750 Dakle, to je najgori slučaj. 135 00:05:47,750 --> 00:05:48,570 >> Za razliku od toga - 136 00:05:48,570 --> 00:05:50,320 a to je roman u zadnji put - 137 00:05:50,320 --> 00:05:54,065 mi je rekao da je uneseni sortiranje bio omega što? 138 00:05:54,065 --> 00:05:57,530 Što je najbolje slučaj trčanje vrijeme umetanja vrste? 139 00:05:57,530 --> 00:05:58,520 Dakle, to je zapravo n. 140 00:05:58,520 --> 00:06:00,980 To je bio prazan da smo napustili Na brodu zadnji put. 141 00:06:00,980 --> 00:06:03,160 >> I to je omega n, jer zašto? 142 00:06:03,160 --> 00:06:06,630 Pa, u najboljem slučaju, ono što je sortiranje umetanjem će se predati? 143 00:06:06,630 --> 00:06:09,830 Pa, popis koji je potpuno razvrstani Već, minimalni rad učiniti. 144 00:06:09,830 --> 00:06:12,460 No, ono što je uredno o tome kakve umetanja je da zato što počinje ovdje i 145 00:06:12,460 --> 00:06:15,340 odluči, oh, ti si broj jedan, da pripadam ovdje. 146 00:06:15,340 --> 00:06:16,970 Oh, što je sreća. 147 00:06:16,970 --> 00:06:17,740 >> Ti si broj dva. 148 00:06:17,740 --> 00:06:19,030 Također pripadam ovdje. 149 00:06:19,030 --> 00:06:21,010 Broj tri, čak i bolje, da pripadam ovdje. 150 00:06:21,010 --> 00:06:25,210 Čim stigne do kraja Popis, po utiskivanja za sortiranje je pseudocode 151 00:06:25,210 --> 00:06:28,010 kako smo hodali kroz verbalno Posljednji put, to je učinjeno. 152 00:06:28,010 --> 00:06:32,790 No, izbor sortiranje, za razliku od, držati što radiš? 153 00:06:32,790 --> 00:06:35,260 >> Zadržao ide kroz popis opet i opet i opet. 154 00:06:35,260 --> 00:06:39,160 Zbog Ključni uvid bilo je samo nakon što ste gledali sve do 155 00:06:39,160 --> 00:06:42,500 kraj popisa možete biti sigurni Element koji ste odabrali je 156 00:06:42,500 --> 00:06:45,560 Doista trenutno najmanji element. 157 00:06:45,560 --> 00:06:48,920 Tako su ti različitih mentalnih modela kraj se donosi neke vrlo stvarnom svijetu 158 00:06:48,920 --> 00:06:53,130 razlike za nas, kao i ovi teorijski asimptotske razlike. 159 00:06:53,130 --> 00:06:56,910 >> Dakle, samo da ponovim, dakle, velika O n kvadrat, vidjeli smo nekoliko takvih 160 00:06:56,910 --> 00:06:58,350 Algoritmi do sada. 161 00:06:58,350 --> 00:06:59,580 Big O n? 162 00:06:59,580 --> 00:07:02,870 Što je algoritam koji bi može reći da je velika O n? 163 00:07:02,870 --> 00:07:06,930 U najgorem slučaju, to traje linearni niz koraka. 164 00:07:06,930 --> 00:07:07,810 >> OK, linearno pretraživanje. 165 00:07:07,810 --> 00:07:10,470 A u najgorem slučaju, gdje je Element ste u potrazi za kada 166 00:07:10,470 --> 00:07:12,950 primjenom linearne pretragu? 167 00:07:12,950 --> 00:07:14,680 >> OK, u najgorem slučaju, to nije ni tamo. 168 00:07:14,680 --> 00:07:17,000 Ili u drugom najgorem slučaju, to je sve na kraju, što je 169 00:07:17,000 --> 00:07:18,880 plus-minus ili jedan korak razlika. 170 00:07:18,880 --> 00:07:21,180 Tako da je na kraju dana, možemo reći da je linearno. 171 00:07:21,180 --> 00:07:23,910 Big O n će biti linearna pretragu, jer u najgorem slučaju, 172 00:07:23,910 --> 00:07:26,610 Element je ni tamo ili je sve na kraju. 173 00:07:26,610 --> 00:07:29,370 >> Pa, big O log n. 174 00:07:29,370 --> 00:07:32,760 Nismo razgovarali u detalje o tome ovo, ali mi smo to vidjeli. 175 00:07:32,760 --> 00:07:36,840 Ono što radi u tzv logaritamska Vrijeme, u najgorem slučaju? 176 00:07:36,840 --> 00:07:38,500 >> Da, tako binarno pretraživanje. 177 00:07:38,500 --> 00:07:42,930 I binarna pretraga u najgorem slučaju Možda ima element negdje u 178 00:07:42,930 --> 00:07:45,640 Srednji, ili negdje unutar polja. 179 00:07:45,640 --> 00:07:48,040 No, samo ga pronašli kada vas podijelite popis na pola, u 180 00:07:48,040 --> 00:07:48,940 polovice, na pola, na pola. 181 00:07:48,940 --> 00:07:50,200 I onda voila, to je tamo. 182 00:07:50,200 --> 00:07:52,500 Ili opet, najgorem slučaju, to nije ni tamo. 183 00:07:52,500 --> 00:07:56,770 Ali vi ne znate da to ne postoji dok ne dođete do vrsta koje traju 184 00:07:56,770 --> 00:08:00,470 bottom-ina elemenata tako da se prepolovi i prepolovi i prepoloviti. 185 00:08:00,470 --> 00:08:01,400 >> Big O od 1. 186 00:08:01,400 --> 00:08:03,540 Tako smo mogli big O od 2, velikim O iz tri. 187 00:08:03,540 --> 00:08:06,260 Bilo da želite samo stalan broj, mi samo vrsta samo pojednostaviti 188 00:08:06,260 --> 00:08:07,280 da kao veliki O iz jednog. 189 00:08:07,280 --> 00:08:10,440 Iako ako je realno, to traje 2 ili čak 100 koraka, ako je 190 00:08:10,440 --> 00:08:13,680 konstantna broj koraka, mi samo reći veliko O od 1. 191 00:08:13,680 --> 00:08:15,930 Što je algoritam koji je u velikoj O iz jedne? 192 00:08:15,930 --> 00:08:18,350 >> PUBLIKA: Pronalaženje duljinu varijable. 193 00:08:18,350 --> 00:08:21,090 >> DAVID Malan: Pronalaženje duljina varijable? 194 00:08:21,090 --> 00:08:23,870 >> PUBLIKA: Ne, duljina ako je već riješeno. 195 00:08:23,870 --> 00:08:24,160 >> DAVID Malan: Dobro. 196 00:08:24,160 --> 00:08:27,850 U redu, tako pronalaženju dužine nešto ako je duljina tog nečega, kao što su 197 00:08:27,850 --> 00:08:30,020 polje, pohranjena u nekom varijablu. 198 00:08:30,020 --> 00:08:33,380 Zato što jednostavno možete pročitati varijablu, ili ispisati varijablu, ili 199 00:08:33,380 --> 00:08:34,960 samo općenito pristup toj varijabli. 200 00:08:34,960 --> 00:08:37,299 I voila, koji se stalno vrijeme. 201 00:08:37,299 --> 00:08:38,909 >> Nasuprot tome, mislim natrag na očekivanoj razini. 202 00:08:38,909 --> 00:08:42,460 Prisjetite se u prvom tjednu C, zove samo printf i ispis 203 00:08:42,460 --> 00:08:46,240 nešto na ekranu je nedvojbeno stalno vrijeme, jer to traje samo 204 00:08:46,240 --> 00:08:50,880 Neki broj CPU ciklusa pokazati da je tekst na zaslonu. 205 00:08:50,880 --> 00:08:52,720 Ili čekati - zar ne? 206 00:08:52,720 --> 00:08:56,430 Kako bi inače mogli smo modelirati izvedba printf? 207 00:08:56,430 --> 00:09:00,420 Bi li netko sviđa kako se ne slažu, da je možda je to zapravo i nije konstantna vrijeme? 208 00:09:00,420 --> 00:09:03,600 U kojem smislu printf možda je trčanje Vrijeme, zapravo ispisuje string na 209 00:09:03,600 --> 00:09:05,580 screen, biti nešto osim konstantna. 210 00:09:05,580 --> 00:09:07,860 >> PUBLIKA: [nečujno]. 211 00:09:07,860 --> 00:09:08,230 >> DAVID Malan: Da. 212 00:09:08,230 --> 00:09:09,300 Pa to ovisi o našoj perspektive. 213 00:09:09,300 --> 00:09:13,390 Ako mi zapravo mislimo na ulazu u printf kao string, i 214 00:09:13,390 --> 00:09:16,380 Stoga smo izmjeriti veličinu koja ulazna po dužini - pa nazovimo 215 00:09:16,380 --> 00:09:17,780 da je duljina n, kao i - 216 00:09:17,780 --> 00:09:21,990 nedvojbeno, printf je sama po sebi velika O n jer će vas odvesti n koraka 217 00:09:21,990 --> 00:09:24,750 ispisati iz svake od tih n likovi, najvjerojatnije. 218 00:09:24,750 --> 00:09:27,730 Barem u tolikoj mjeri da pretpostavljamo da možda je korištenjem for petlje 219 00:09:27,730 --> 00:09:28,560 ispod poklopca motora. 220 00:09:28,560 --> 00:09:30,860 >> No, trebali bismo gledati u to kodirati razumjeti bolje. 221 00:09:30,860 --> 00:09:33,650 I doista, kad vi počnete Analizirajući svoje algoritme, vi ćete 222 00:09:33,650 --> 00:09:34,900 doslovno učiniti upravo to. 223 00:09:34,900 --> 00:09:37,765 Vrsta od očne jabučice svoj broj i mislim o - u redu, ja imam ovu petlju 224 00:09:37,765 --> 00:09:41,870 Ovdje ili ja imamo ugniježđeni petlje ovdje, da će učiniti stvari n n puta, 225 00:09:41,870 --> 00:09:46,050 , a možete sortirati razuma svoj put kroz kod, čak i ako je 226 00:09:46,050 --> 00:09:47,980 pseudocode a ne stvarni broj. 227 00:09:47,980 --> 00:09:49,730 >> Zato što o omega na kvadrat od n? 228 00:09:49,730 --> 00:09:53,582 Što je algoritam koji je u najboljem slučaj, još uvijek je n kvadratna koraka? 229 00:09:53,582 --> 00:09:54,014 Da? 230 00:09:54,014 --> 00:09:54,880 >> PUBLIKA: [nečujno]. 231 00:09:54,880 --> 00:09:55,900 >> DAVID Malan: Pa neka vrsta odabira. 232 00:09:55,900 --> 00:09:59,150 Budući da u tom problemu zapravo smanjuje na činjenicu da je opet, ne znam 233 00:09:59,150 --> 00:10:02,600 Ja sam pronašao struje dok najmanji Provjerio sam sve prokleto elemente. 234 00:10:02,600 --> 00:10:08,050 Dakle, omega, kažu, n, mi Samo je došao gore sa jednim. 235 00:10:08,050 --> 00:10:09,300 Ubacivanje sortiranje. 236 00:10:09,300 --> 00:10:12,370 Ako se dogodi da se popis razvrstani već, u najboljem slučaju imamo samo 237 00:10:12,370 --> 00:10:15,090 napraviti jednu loptu kroz njega, U tom trenutku smo sigurni. 238 00:10:15,090 --> 00:10:17,890 A onda je to moglo biti, rekao je biti linearno, sigurno. 239 00:10:17,890 --> 00:10:20,570 >> Što je omega od 1? 240 00:10:20,570 --> 00:10:23,790 Ono, u najboljem slučaju, mogao potrajati konstantna broj koraka? 241 00:10:23,790 --> 00:10:27,220 Dakle, linearno pretraživanje, ako baš posreći a element koji tražite 242 00:10:27,220 --> 00:10:31,000 Nalazi se u početku popisa, ako je to gdje ste počinju svoj 243 00:10:31,000 --> 00:10:33,070 Linearni obuhvaćanje tog popisa. 244 00:10:33,070 --> 00:10:35,180 >> A to vrijedi i za Broj stvari. 245 00:10:35,180 --> 00:10:37,660 Na primjer, čak i binarna Nova je omega jedan. 246 00:10:37,660 --> 00:10:40,310 Jer što ako se stvarno prokleto sretni i ukus-stručnjak u sredini 247 00:10:40,310 --> 00:10:42,950 svoje polje je broj što tražite? 248 00:10:42,950 --> 00:10:45,730 Tako možete dobiti sretan tamo, kao dobro. 249 00:10:45,730 --> 00:10:49,190 >> To je jedan, na kraju, omega n log n. 250 00:10:49,190 --> 00:10:52,573 Dakle, n log n, mi zapravo nije govoriti o još, ali - 251 00:10:52,573 --> 00:10:53,300 >> PUBLIKA: Spoji vrsta? 252 00:10:53,300 --> 00:10:53,960 >> DAVID Malan: Spajanje sortiranje. 253 00:10:53,960 --> 00:10:56,920 To je roman u zadnje vrijeme, gdje smo predložili, a mi pokazali 254 00:10:56,920 --> 00:10:58,600 vizualno, da postoje algoritmi. 255 00:10:58,600 --> 00:11:02,470 A spajanje kakve samo jedan takav algoritam koji je iz temelja brži 256 00:11:02,470 --> 00:11:03,450 nego neki od ovih momaka. 257 00:11:03,450 --> 00:11:07,800 U stvari, spajanje kratko je ne samo u Najbolji slučaj n log n, u najgorem 258 00:11:07,800 --> 00:11:09,460 Slučaj n log n. 259 00:11:09,460 --> 00:11:14,540 A kad imate ovu podudarnost Omega i velikih O biti ista stvar? 260 00:11:14,540 --> 00:11:17,310 Mi zapravo mogu opisati kao da je ono što je zove theta, iako je 261 00:11:17,310 --> 00:11:18,220 malo rjeđi. 262 00:11:18,220 --> 00:11:21,730 No, to samo znači dvije granice, u ovom slučaju, su isti. 263 00:11:21,730 --> 00:11:25,770 >> Dakle spojiti neku, što to Stvarno svode se na za nas? 264 00:11:25,770 --> 00:11:27,000 Pa, sjećam motivaciju. 265 00:11:27,000 --> 00:11:30,340 Dopustite mi podići još jednu animaciju taj nismo pogledajte zadnje vrijeme. 266 00:11:30,340 --> 00:11:33,390 Ovo je jedna, ista ideja, ali to je malo veći. 267 00:11:33,390 --> 00:11:36,160 I ja ću ići naprijed i istaknuti Prvi - imamo unosa vrsta na 268 00:11:36,160 --> 00:11:39,410 gore lijevo, a zatim odabir sortiranje, bubble sortiranje, nekoliko drugih vrsta - 269 00:11:39,410 --> 00:11:42,670 ljuske i brzo - da nismo razgovarali o, i gomila i spajanje vrsta. 270 00:11:42,670 --> 00:11:47,090 >> Tako barem pokušati usredotočiti svoje oči na prva tri mjesta na lijevoj strani, a zatim 271 00:11:47,090 --> 00:11:49,120 spojiti neku kad kliknem ova zelena strelica. 272 00:11:49,120 --> 00:11:51,900 Ali ja ću sve od njih pokrenuti, samo da daje vam osjećaj raznolikosti 273 00:11:51,900 --> 00:11:53,980 algoritmi koji postoje u svijetu. 274 00:11:53,980 --> 00:11:56,180 Ja ću pustiti ovu utrku za samo nekoliko sekundi. 275 00:11:56,180 --> 00:11:59,640 A ako se usredotočite vaše oči - pick Algoritam, usredotočiti na to za samo 276 00:11:59,640 --> 00:12:02,970 sekundi - vi ćete početi vidjeti uzorak koji se to provodi. 277 00:12:02,970 --> 00:12:04,530 >> Spoji sortiranje, obavijest, učinjeno je. 278 00:12:04,530 --> 00:12:06,430 Skupi sortiranje, brzo sortirati, školjke - 279 00:12:06,430 --> 00:12:09,480 pa se čini uveli smo tri Najgore algoritama prošli tjedan. 280 00:12:09,480 --> 00:12:12,960 Ali to je dobro da smo danas ovdje da se , pogledajte spajanja vrste, što je jedan od 281 00:12:12,960 --> 00:12:16,500 one su lakše je gledati, čak i iako to vjerojatno će saviti svoje mišljenje 282 00:12:16,500 --> 00:12:17,490 Samo malo. 283 00:12:17,490 --> 00:12:21,130 Ovdje možemo vidjeti koliko je Izbor svojevrsni sranje. 284 00:12:21,130 --> 00:12:24,600 >> No, na drugoj strani, to je stvarno lako provesti. 285 00:12:24,600 --> 00:12:28,160 A možda je za P Set 3, to je jedna od Algoritmi ste izabrali za provedbu 286 00:12:28,160 --> 00:12:28,960 za standardnom izdanju. 287 00:12:28,960 --> 00:12:30,970 Savršeno u redu, posve točna. 288 00:12:30,970 --> 00:12:35,210 >> Ali opet, kao n dobiva veliki, ako odlučite provesti brži algoritam 289 00:12:35,210 --> 00:12:39,020 kao svojevrsno pismo, izgledi su u veće i veće ulaza, tvoj broj je samo 290 00:12:39,020 --> 00:12:39,800 ide na trčanje brže. 291 00:12:39,800 --> 00:12:41,090 Vaša web stranica će raditi bolje. 292 00:12:41,090 --> 00:12:42,650 Vaši korisnici će biti sretniji. 293 00:12:42,650 --> 00:12:45,280 I tako su ti učinci da zapravo daje 294 00:12:45,280 --> 00:12:47,350 nas neki dublji mislili. 295 00:12:47,350 --> 00:12:49,990 >> Tako ćemo pogledati što spajanje svojevrsni je zapravo riječ. 296 00:12:49,990 --> 00:12:52,992 Super stvar je da spajanje svojevrsni je upravo to. 297 00:12:52,992 --> 00:12:56,300 To je, opet, ono što smo pozvani pseudocode, biće pseudocode 298 00:12:56,300 --> 00:12:57,720 Engleski poput sintakse. 299 00:12:57,720 --> 00:12:59,890 A jednostavnost je vrsta fascinantno. 300 00:12:59,890 --> 00:13:02,840 >> Tako se na ulaz od n elemenata - tako da samo znači, ovdje je niz. 301 00:13:02,840 --> 00:13:04,000 To je dobio n stvari u njemu. 302 00:13:04,000 --> 00:13:05,370 To je sve što govoriš postoji. 303 00:13:05,370 --> 00:13:07,560 >> Ako n je manje od 2, vratiti. 304 00:13:07,560 --> 00:13:08,640 Dakle, to je samo trivijalno slučaj. 305 00:13:08,640 --> 00:13:12,580 Ako je n manji od 2, a zatim je očito da je 1 ili 0, u kojem slučaju je stvar 306 00:13:12,580 --> 00:13:14,780 je već riješeno ili nepostojeće, pa samo se vratiti. 307 00:13:14,780 --> 00:13:15,900 Nema se što učiniti. 308 00:13:15,900 --> 00:13:18,360 Dakle, to je jednostavan slučaj trgati off. 309 00:13:18,360 --> 00:13:20,110 >> Inače, imamo tri koraka. 310 00:13:20,110 --> 00:13:23,650 Sortiranje lijevu polovicu elemenata, sortiranja Desna polovina od elemenata, 311 00:13:23,650 --> 00:13:26,650 a zatim spojiti sortirane polovice. 312 00:13:26,650 --> 00:13:29,400 Ono što je zanimljivo je da je Nekako sam punting, zar ne? 313 00:13:29,400 --> 00:13:32,300 Postoji vrsta kružnog definiciji na ovaj algoritam. 314 00:13:32,300 --> 00:13:35,986 U kojem je smislu ovaj algoritam je definicija kružne? 315 00:13:35,986 --> 00:13:37,850 >> PUBLIKA: [nečujno]. 316 00:13:37,850 --> 00:13:41,670 >> DAVID Malan: Da, moj algoritam za sortiranje, dvojica njegovih koraka "svojevrsni 317 00:13:41,670 --> 00:13:44,640 nešto. "A, tako da moli Pitanje, dakle, ono što ću koristiti 318 00:13:44,640 --> 00:13:46,460 sortirati lijevu polovicu , a desna polovica? 319 00:13:46,460 --> 00:13:49,600 A ljepota je u tome što, iako opet, to je um-savijanje 320 00:13:49,600 --> 00:13:54,030 dio potencijalno, možete koristiti isti algoritam za sortiranje lijevu polovicu. 321 00:13:54,030 --> 00:13:54,700 >> Ali čekaj malo. 322 00:13:54,700 --> 00:13:57,070 Kad ste rekli da razriješi lijeva polovica, što su dvije 323 00:13:57,070 --> 00:13:58,240 koraka će biti sljedeći? 324 00:13:58,240 --> 00:14:00,550 Mi ćemo sortirati lijevu polovicu lijeva polovica i pravo 325 00:14:00,550 --> 00:14:01,420 polovica lijeve polovice. 326 00:14:01,420 --> 00:14:04,430 Dovraga, kako mogu sortirati i one dvije polovice ili četvrtine, sada? 327 00:14:04,430 --> 00:14:05,260 >> Ali to je u redu. 328 00:14:05,260 --> 00:14:07,830 Imamo sortiranja algoritam ovdje. 329 00:14:07,830 --> 00:14:10,660 I iako možda brinite, na Prvi je to vrsta beskonačnog 330 00:14:10,660 --> 00:14:12,780 petlje, to je ciklus koji nikada nije ide do kraja - to je idući u 331 00:14:12,780 --> 00:14:15,770 završiti nakon što se događa? 332 00:14:15,770 --> 00:14:16,970 Kada n je manje od 2. 333 00:14:16,970 --> 00:14:19,180 Što na kraju će se dogoditi, jer ako bi se prepoloviti, a 334 00:14:19,180 --> 00:14:23,020 prepoloviti u prepoloviti te polovice, sigurno na kraju ti si idući u kraj 335 00:14:23,020 --> 00:14:25,350 sa samo 1 ili 0 elemenata. 336 00:14:25,350 --> 00:14:28,500 U tom trenutku, ovaj algoritam kaže da ste učinili. 337 00:14:28,500 --> 00:14:31,020 >> Dakle, prava čarolija u ovom Algoritam se čini da se u 338 00:14:31,020 --> 00:14:33,470 da je konačni korak, spajanjem. 339 00:14:33,470 --> 00:14:37,190 Ta jednostavna ideja jednostavno spajanje dvaju stvari, to je ono što se događa u konačnici 340 00:14:37,190 --> 00:14:40,920 kako bi se omogućilo nam da sortirati niz, recimo, osam elemenata. 341 00:14:40,920 --> 00:14:44,410 Dakle, imam još osam stres loptice do Ovdje, osam komada papira, i jedan 342 00:14:44,410 --> 00:14:45,500 Google Glass - 343 00:14:45,500 --> 00:14:46,140 što sam mogao zadržati. 344 00:14:46,140 --> 00:14:46,960 >> [Smijeh] 345 00:14:46,960 --> 00:14:48,970 >> DAVID Malan: Ako smo mogli potrajati osam volonteri, pa da vidimo možemo li 346 00:14:48,970 --> 00:14:51,430 igrati ovu out, tako da. 347 00:14:51,430 --> 00:14:52,500 Wow, OK. 348 00:14:52,500 --> 00:14:53,565 Računarstvo je sve zabavno. 349 00:14:53,565 --> 00:14:54,320 U redu. 350 00:14:54,320 --> 00:14:57,770 Dakle, o tome što tri, Najveći ruku gore. 351 00:14:57,770 --> 00:14:58,580 Četiri u leđa. 352 00:14:58,580 --> 00:15:02,220 A što ćemo vam napraviti tri u ovom nizu? 353 00:15:02,220 --> 00:15:03,390 I četiri u prednjem. 354 00:15:03,390 --> 00:15:04,920 Dakle, osam, daj se. 355 00:15:04,920 --> 00:15:12,060 >> [Smijeh] 356 00:15:12,060 --> 00:15:13,450 >> DAVID Malan: Ja sam zapravo ne znam što je to. 357 00:15:13,450 --> 00:15:14,810 Je li to stres loptice? 358 00:15:14,810 --> 00:15:16,510 U stolna lampa? 359 00:15:16,510 --> 00:15:18,650 Materijal? 360 00:15:18,650 --> 00:15:19,680 Internet? 361 00:15:19,680 --> 00:15:20,160 >> OK. 362 00:15:20,160 --> 00:15:21,310 Pa hajde gore. 363 00:15:21,310 --> 00:15:22,310 Tko bi htio - 364 00:15:22,310 --> 00:15:23,570 zadržati dolaze. 365 00:15:23,570 --> 00:15:24,240 Idemo vidjeti. 366 00:15:24,240 --> 00:15:26,460 A to vas stavlja u položaj - 367 00:15:26,460 --> 00:15:27,940 ti si u jednom mjestu. 368 00:15:27,940 --> 00:15:28,670 Uh-oh, čekaj malo. 369 00:15:28,670 --> 00:15:30,760 1, 2, 3, 4, 5, 6, 7 - O, dobro. 370 00:15:30,760 --> 00:15:31,310 Dobro, dobro smo. 371 00:15:31,310 --> 00:15:35,130 U redu, tako da svatko ima sjedište, ali ne na Google Glass. 372 00:15:35,130 --> 00:15:36,475 Dopustite mi da na red ovih gore. 373 00:15:36,475 --> 00:15:37,115 Koje je tvoje ime? 374 00:15:37,115 --> 00:15:37,440 >> MICHELLE: Michelle. 375 00:15:37,440 --> 00:15:38,090 >> DAVID Malan: Michelle? 376 00:15:38,090 --> 00:15:42,000 U redu, ti izgledati geek, ako je to u redu. 377 00:15:42,000 --> 00:15:44,625 Pa, ja također, pretpostavljam, samo na trenutak. 378 00:15:44,625 --> 00:15:45,875 U redu, čekanja. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Pokušali smo doći do koristite slučaj za Google Glass, a mi 381 00:15:50,950 --> 00:15:53,750 mislio da će to biti zabavno samo raditi ovo kad su ljudi na pozornici. 382 00:15:53,750 --> 00:15:57,120 Mi ćemo snimiti svijet iz njihove perspektive. 383 00:15:57,120 --> 00:15:58,410 U redu. 384 00:15:58,410 --> 00:15:59,830 Nije vjerojatno ono što Google namjerava. 385 00:15:59,830 --> 00:16:02,260 U redu, ako vam ne smeta nosio ovo idućih nespretan minuta, 386 00:16:02,260 --> 00:16:03,150 to bi bilo divno. 387 00:16:03,150 --> 00:16:08,620 >> U redu, tako da ovdje imamo niz elementi, te da niz, kao i po 388 00:16:08,620 --> 00:16:11,480 papirići u tih ljudi ' Ruke, trenutno nesortirani. 389 00:16:11,480 --> 00:16:12,050 >> MICHELLE: Oh, to je tako čudno. 390 00:16:12,050 --> 00:16:12,810 >> DAVID Malan: To je prilično slučajna. 391 00:16:12,810 --> 00:16:15,760 I u samo nekoliko trenutaka, idemo pokušati provesti spojiti neku zajedno 392 00:16:15,760 --> 00:16:17,950 i vidjeti gdje je taj ključni uvid. 393 00:16:17,950 --> 00:16:21,970 A trik ovdje s udruživanjem vrste je nešto što nismo još uvijek pretpostavlja. 394 00:16:21,970 --> 00:16:24,030 Mi zapravo treba neki Dodatni prostor. 395 00:16:24,030 --> 00:16:26,650 Dakle, što će biti posebno Zanimljivo je o tome da su ti 396 00:16:26,650 --> 00:16:29,270 Dečki će se kretati malo bitni, jer ću pretpostaviti da 397 00:16:29,270 --> 00:16:31,880 postoji dodatni niz prostora, recimo, odmah iza njih. 398 00:16:31,880 --> 00:16:34,570 >> Dakle, ako ste iza svog stolca, to je sekundarna polja. 399 00:16:34,570 --> 00:16:36,960 Ako oni sjede ovdje, to je Primarni polja. 400 00:16:36,960 --> 00:16:40,170 No, to je resurs koji imamo Nije iskoristio dosad s mjehur 401 00:16:40,170 --> 00:16:42,040 sortiranje, uz izbor sorte, s umetanja vrste. 402 00:16:42,040 --> 00:16:44,600 Sjetite se prošlog tjedna, svi samo vrsta miješaju u mjestu. 403 00:16:44,600 --> 00:16:46,840 Oni nisu koristili nikakvu dodatnu memoriju. 404 00:16:46,840 --> 00:16:49,310 Mi smo napravili mjesta za osobe koje kretanje ljudi oko sebe. 405 00:16:49,310 --> 00:16:50,580 >> Dakle, ovo je ključni uvid, previše. 406 00:16:50,580 --> 00:16:53,410 Tu je ova trgovina-off, u cjelini u računalne znanosti, resursa. 407 00:16:53,410 --> 00:16:55,800 Ako želite ubrzati nešto kao što su vrijeme, ti ćeš 408 00:16:55,800 --> 00:16:56,900 morati platiti cijenu. 409 00:16:56,900 --> 00:17:00,750 A jedna od tih cijena je vrlo često prostor, količina memorije ili tvrdog 410 00:17:00,750 --> 00:17:01,700 prostor na disku koji koristite. 411 00:17:01,700 --> 00:17:03,640 Ili, iskreno, iznos programer vremena. 412 00:17:03,640 --> 00:17:06,700 Koliko je vremena potrebno vam, ljudi, se zapravo provesti neke više 413 00:17:06,700 --> 00:17:07,829 komplicirano algoritam. 414 00:17:07,829 --> 00:17:09,760 Ali za danas, trade-off je vrijeme i prostor. 415 00:17:09,760 --> 00:17:11,930 >> Dakle, ako ti dečki samo mogao držati do svoje brojeva, tako možemo vidjeti da ste 416 00:17:11,930 --> 00:17:15,839 doista podudaranje 4, 2, 6, 1, 3, 7, 8. 417 00:17:15,839 --> 00:17:16,599 Izvrsno. 418 00:17:16,599 --> 00:17:19,520 Pa ću pokušati orkestrirati stvari, ako dečki mogu jednostavno 419 00:17:19,520 --> 00:17:21,800 slijedite moj vodstvo ovdje. 420 00:17:21,800 --> 00:17:26,650 >> Tako ću provesti, prvo, Prvi korak u pseudocode, što je 421 00:17:26,650 --> 00:17:29,440 na ulaz od n elemenata, ako je N manji od 2, a zatim se vratiti. 422 00:17:29,440 --> 00:17:31,370 Očito, to ne primjenjuju, tako da možemo krenuti dalje. 423 00:17:31,370 --> 00:17:33,340 Dakle, sortirati lijevu polovicu elemenata. 424 00:17:33,340 --> 00:17:36,220 Dakle, to znači da ću se usredotočiti moju pozornost samo na trenutak na njih 425 00:17:36,220 --> 00:17:37,310 Četiri dečki ovdje. 426 00:17:37,310 --> 00:17:39,774 U redu, što trebam učiniti iduće? 427 00:17:39,774 --> 00:17:40,570 >> PUBLIKA: Sortiranje lijevu polovicu. 428 00:17:40,570 --> 00:17:42,780 >> DAVID Malan: Pa sad moram sortirati lijeva polovica od tih momaka. 429 00:17:42,780 --> 00:17:45,580 Jer opet, preuzeti na sebe u Cilj je riješiti lijevu polovicu. 430 00:17:45,580 --> 00:17:46,440 Kako ćete to učiniti? 431 00:17:46,440 --> 00:17:49,140 Samo slijedite upute, čak i iako mi to opet. 432 00:17:49,140 --> 00:17:50,160 Dakle, sortirati lijevu polovicu. 433 00:17:50,160 --> 00:17:52,030 Sada sam sortiranja ove dvije dečki. 434 00:17:52,030 --> 00:17:53,563 Što je sljedeće? 435 00:17:53,563 --> 00:17:54,510 >> PUBLIKA: Sortiranje lijevu polovicu. 436 00:17:54,510 --> 00:17:55,460 >> DAVID Malan: Sortiranje lijevu polovicu. 437 00:17:55,460 --> 00:18:00,680 Pa sad ti, ovo sjedalo ovdje, je popis veličine 1. 438 00:18:00,680 --> 00:18:01,365 I ono zoveš? 439 00:18:01,365 --> 00:18:02,390 >> PRINCEZA DAISY: Princeza Daisy. 440 00:18:02,390 --> 00:18:03,690 >> DAVID Malan: Princeza Daisy je ovdje. 441 00:18:03,690 --> 00:18:07,470 I tako je već riješeno, jer je Popis je veličine 1. 442 00:18:07,470 --> 00:18:09,490 Što trebam učiniti iduće? 443 00:18:09,490 --> 00:18:13,680 OK, vratite, jer to je popis od veličina 1, što je manje od 2. 444 00:18:13,680 --> 00:18:14,320 Nakon što je sljedeći korak? 445 00:18:14,320 --> 00:18:17,490 A sada morate vrsta backtrack u vašem umu. 446 00:18:17,490 --> 00:18:19,340 >> Sortiranje desnu polovicu, što je - 447 00:18:19,340 --> 00:18:19,570 kako se ti zoveš? 448 00:18:19,570 --> 00:18:20,220 >> LINDA: Linda. 449 00:18:20,220 --> 00:18:20,980 >> DAVID Malan: Linda. 450 00:18:20,980 --> 00:18:23,210 I tako što ćemo sada da imamo popis veličine 1? 451 00:18:23,210 --> 00:18:24,440 >> PUBLIKA: Povratak. 452 00:18:24,440 --> 00:18:24,760 >> DAVID Malan: Oprezno. 453 00:18:24,760 --> 00:18:29,540 Vraćamo prva, a sada treći korak - a ako Nekako sam se prikazuju prema 454 00:18:29,540 --> 00:18:33,490 ušle dva mjesta sada, sada sam morati spojiti ta dva elementa. 455 00:18:33,490 --> 00:18:35,530 Tako sada, nažalost, elementi su izvan funkcije. 456 00:18:35,530 --> 00:18:39,920 No, to je mjesto gdje proces pripajanja počinje da se uvjerljiv. 457 00:18:39,920 --> 00:18:42,410 >> Dakle, ako ti dečki mogli ustati za jednostavno Trenutak, idem da vam je potrebno, u 458 00:18:42,410 --> 00:18:44,170 Trenutak, na korak iza stolica. 459 00:18:44,170 --> 00:18:46,480 A ako Linda, jer je 2 manji od četiri, zašto ne 460 00:18:46,480 --> 00:18:48,130 li navratiti prvi? 461 00:18:48,130 --> 00:18:48,690 Ostani tamo. 462 00:18:48,690 --> 00:18:50,520 Dakle, Linda, što navratiti na prvom mjestu. 463 00:18:50,520 --> 00:18:53,820 >> Sada je u stvarnosti i ako je samo niz samo smo je mogli kretati u stvarnom vremenu 464 00:18:53,820 --> 00:18:55,360 od ove stolice na tom mjestu. 465 00:18:55,360 --> 00:18:57,770 Pa zamislite da je neki stalni Broj koraka 1. 466 00:18:57,770 --> 00:18:58,480 A sada - 467 00:18:58,480 --> 00:19:01,490 ali moramo vas staviti u prvo mjesto ovdje. 468 00:19:01,490 --> 00:19:03,930 >> I sad ako bi mogao navratiti, kao dobro, idemo na 469 00:19:03,930 --> 00:19:06,300 biti u mjestu dva. 470 00:19:06,300 --> 00:19:09,120 I iako se osjeća kao da je uzimajući neko vrijeme, ono što je lijepo sad je 471 00:19:09,120 --> 00:19:14,710 da je lijeva polovica lijeva polovica je sada riješeno. 472 00:19:14,710 --> 00:19:18,010 Dakle, što je sljedeći korak, ako mi sada premotati dalje u priči? 473 00:19:18,010 --> 00:19:18,980 >> PUBLIKA: desna polovica. 474 00:19:18,980 --> 00:19:19,900 >> DAVID Malan: Sortiranje desnu polovicu. 475 00:19:19,900 --> 00:19:21,320 Dakle, što vi imate za to, kao dobro. 476 00:19:21,320 --> 00:19:23,510 Dakle, ako mogu ustati samo na trenutak? 477 00:19:23,510 --> 00:19:25,192 A kako se ti zoveš? 478 00:19:25,192 --> 00:19:25,540 >> JESS: Jess. 479 00:19:25,540 --> 00:19:25,870 >> DAVID Malan: Jess. 480 00:19:25,870 --> 00:19:29,720 U redu, tako da Jess je sada lijevo polovica desnoj polovici. 481 00:19:29,720 --> 00:19:31,400 I tako je ona lista veličine 1. 482 00:19:31,400 --> 00:19:32,380 Očito je riješeno. 483 00:19:32,380 --> 00:19:33,070 I zoveš? 484 00:19:33,070 --> 00:19:33,630 >> MICHELLE: Michelle. 485 00:19:33,630 --> 00:19:35,340 >> DAVID Malan: Michelle je očito Popis veličine 1. 486 00:19:35,340 --> 00:19:36,050 Već je riješeno. 487 00:19:36,050 --> 00:19:38,690 Tako sada magija se događa, Proces spajanja. 488 00:19:38,690 --> 00:19:39,790 Dakle, tko će biti na prvom mjestu? 489 00:19:39,790 --> 00:19:41,560 Očito Michelle. 490 00:19:41,560 --> 00:19:43,280 Dakle, ako bi mogao navratiti vratiti. 491 00:19:43,280 --> 00:19:47,090 Prostor imamo na raspolaganju za nju sada je odmah iza tog stolca ovdje. 492 00:19:47,090 --> 00:19:51,580 A sad, ako bi se mogla vratiti kao dobro, mi sada imamo, da bude jasno, dva 493 00:19:51,580 --> 00:19:53,810 polovice, od kojih je svaki veličine 2 - 494 00:19:53,810 --> 00:19:57,090 i samo za prikaz miloga, ako mogao bi malo prostora - 495 00:19:57,090 --> 00:19:59,780 jedan lijevo polovice ovdje, jedan Desna polovina ovdje. 496 00:19:59,780 --> 00:20:01,160 >> Rewind dalje u priči. 497 00:20:01,160 --> 00:20:02,270 Koji je sljedeći korak? 498 00:20:02,270 --> 00:20:03,030 >> PUBLIKA: pisma. 499 00:20:03,030 --> 00:20:04,160 >> DAVID Malan: Sada moramo spojiti. 500 00:20:04,160 --> 00:20:07,490 Pa OK, tako da sada, srećom, možemo Samo oslobodio četiri stolice. 501 00:20:07,490 --> 00:20:11,480 Tako smo se i dvostruko više memorije, ali možemo dati flip-flopping između 502 00:20:11,480 --> 00:20:12,330 dva polja. 503 00:20:12,330 --> 00:20:14,190 Dakle koji broj je na prvom mjestu? 504 00:20:14,190 --> 00:20:14,850 Dakle Michelle, očito. 505 00:20:14,850 --> 00:20:16,680 Dakle navratiti i uzeti svoje mjesto ovdje. 506 00:20:16,680 --> 00:20:19,120 I tada se broj 2 je očito Sljedeći, tako da ovdje dolaze. 507 00:20:19,120 --> 00:20:21,520 Broj 4, broj 6. 508 00:20:21,520 --> 00:20:23,390 I opet, iako postoji Malo šetnje su uključeni, 509 00:20:23,390 --> 00:20:26,010 Stvarno, to bi se moglo dogoditi odmah, pomicanjem jedan - 510 00:20:26,010 --> 00:20:26,880 OK, dobro igrao. 511 00:20:26,880 --> 00:20:28,350 >> [Smijeh] 512 00:20:28,350 --> 00:20:29,680 >> DAVID Malan: I sad smo u prilično dobrom stanju. 513 00:20:29,680 --> 00:20:34,910 Lijeva polovica cijeli Ulaz je sada riješeno. 514 00:20:34,910 --> 00:20:37,370 U redu, tako da su ti dečki imali Prednost moje - 515 00:20:37,370 --> 00:20:40,340 kako se to završiti sve djevojke na lijevo i svi dječaci na desnoj strani? 516 00:20:40,340 --> 00:20:42,450 >> U redu, tako da dečki 'Okrenimo se sada. 517 00:20:42,450 --> 00:20:44,680 Dakle, neću vas kroz ti koraci. 518 00:20:44,680 --> 00:20:46,550 Mi ćemo vidjeti ako mi može ponovo isto pseudocode. 519 00:20:46,550 --> 00:20:50,050 Ako želite ići naprijed i stand up, a vi, dopustite mi da vam mikrofon. 520 00:20:50,050 --> 00:20:52,990 Vidi ako ne može ponoviti ono samo mi je ovdje na 521 00:20:52,990 --> 00:20:53,880 drugi kraj popisa. 522 00:20:53,880 --> 00:20:59,530 Tko treba govoriti prvi, temelji na algoritmu? 523 00:20:59,530 --> 00:21:03,210 Dakle objasniti što ste radili prije nego što bi bilo stopala pokrete. 524 00:21:03,210 --> 00:21:05,930 >> ZVUČNI 1: U redu, tako da od Ja sam lijeva polovica 525 00:21:05,930 --> 00:21:07,790 lijeva polovica, vraćam. 526 00:21:07,790 --> 00:21:08,730 Točno? 527 00:21:08,730 --> 00:21:09,250 >> DAVID Malan: Dobro. 528 00:21:09,250 --> 00:21:10,350 >> ZVUČNI 1: A onda - 529 00:21:10,350 --> 00:21:11,800 >> DAVID Malan: Tko mic ići dalje? 530 00:21:11,800 --> 00:21:12,920 >> ZVUČNI 1: Sljedeći broj. 531 00:21:12,920 --> 00:21:14,720 >> ZVUČNI 2: Dakle, ja sam desna polovica na lijevoj polovici 532 00:21:14,720 --> 00:21:17,830 lijeva polovica, a ja sam se vratiti. 533 00:21:17,830 --> 00:21:18,050 >> DAVID Malan: Dobro. 534 00:21:18,050 --> 00:21:18,550 Vraćate. 535 00:21:18,550 --> 00:21:21,855 Pa sad što je sljedeći za vas dvoje? 536 00:21:21,855 --> 00:21:23,740 >> ZVUČNI 2: Želimo vidjeti tko je manja. 537 00:21:23,740 --> 00:21:24,200 >> DAVID Malan: Točno. 538 00:21:24,200 --> 00:21:24,940 Želimo spojiti. 539 00:21:24,940 --> 00:21:27,590 Prostor ćemo koristiti za spajanje ste u, iako su 540 00:21:27,590 --> 00:21:30,250 Očito je već riješeno, idemo slijediti isti algoritam. 541 00:21:30,250 --> 00:21:31,560 Pa tko ide natrag prva? 542 00:21:31,560 --> 00:21:35,720 Pa je 3, a zatim 7. 543 00:21:35,720 --> 00:21:38,570 I sad ide mic s tim dečkima, OK? 544 00:21:38,570 --> 00:21:43,590 >> ZVUČNI 3: Tako sam desnu polovinu lijeva polovica, i moje n je manje od 545 00:21:43,590 --> 00:21:45,048 1, tako da sam samo ću proći - 546 00:21:45,048 --> 00:21:46,380 >> DAVID Malan: Dobro. 547 00:21:46,380 --> 00:21:49,450 >> ZVUČNI 4: Ja sam desnu polovinu desnu polovinu desnoj polovici, a ja sam 548 00:21:49,450 --> 00:21:51,740 Također jedna osoba, tako da sam će se vratiti. 549 00:21:51,740 --> 00:21:52,990 Dakle, sada smo spojiti. 550 00:21:52,990 --> 00:21:55,140 551 00:21:55,140 --> 00:21:56,150 >> ZVUČNI 3: Tako smo se vratiti. 552 00:21:56,150 --> 00:21:57,160 >> DAVID Malan: Znači li ići u leđa. 553 00:21:57,160 --> 00:21:59,200 Dakle, 5 ide prvi, a zatim 8. 554 00:21:59,200 --> 00:22:01,240 A sada publike, što je korak moramo sada premotati 555 00:22:01,240 --> 00:22:02,200 natrag u našim glavama? 556 00:22:02,200 --> 00:22:02,940 >> PUBLIKA: pisma. 557 00:22:02,940 --> 00:22:07,270 >> DAVID Malan: Spajanje lijeve i desne polovice polovice izvornog lijeve polovice. 558 00:22:07,270 --> 00:22:08,840 Pa sada - 559 00:22:08,840 --> 00:22:10,520 i samo da se to jasno, napraviti malo prostora 560 00:22:10,520 --> 00:22:11,690 između vas dvojica. 561 00:22:11,690 --> 00:22:13,800 Dakle, sada kada je na dva popisa, lijevo i desno. 562 00:22:13,800 --> 00:22:18,320 Pa kako ćemo sada spojiti li dečki u prednji red sjedala opet? 563 00:22:18,320 --> 00:22:19,600 >> 3. ide prvi. 564 00:22:19,600 --> 00:22:20,850 Zatim 5, očito. 565 00:22:20,850 --> 00:22:23,110 566 00:22:23,110 --> 00:22:27,330 Zatim 7, 8 i sad. 567 00:22:27,330 --> 00:22:28,710 U redu, a sada smo? 568 00:22:28,710 --> 00:22:29,650 >> PUBLIKA: Nije učinjeno. 569 00:22:29,650 --> 00:22:32,440 >> DAVID Malan: Nije učinjeno, jer je Očito, postoji jedan korak preostalo. 570 00:22:32,440 --> 00:22:35,720 Ali opet, razlog sam koristeći ovaj žargonu kao "unatrag u vašem umu," 571 00:22:35,720 --> 00:22:37,160 to je zato što je stvarno što se događa. 572 00:22:37,160 --> 00:22:39,610 Idemo kroz svih ovih koraka, ali mi smo vrsta zaustavio 573 00:22:39,610 --> 00:22:42,480 Trenutak, ronjenje dublje u Algoritam, zastavši na trenutak, 574 00:22:42,480 --> 00:22:45,840 ronjenje dublje u algoritmu, a Sada moramo vrsta unatrag u našoj 575 00:22:45,840 --> 00:22:49,430 umovi i poništavanje svih tih slojeva da smo vrsta stavili na čekanje. 576 00:22:49,430 --> 00:22:51,790 >> Tako sada imamo dvije liste veličine 4. 577 00:22:51,790 --> 00:22:54,790 Ako ti dečki mogu ustati posljednji put i napraviti malo prostora ovdje 578 00:22:54,790 --> 00:22:57,230 jasno da je to lijeva polovica izvornika, 579 00:22:57,230 --> 00:22:58,620 Desna polovina od izvornika. 580 00:22:58,620 --> 00:23:01,060 Tko je prvi broj koji smo trebaju povući u leđa? 581 00:23:01,060 --> 00:23:01,870 Michelle, naravno. 582 00:23:01,870 --> 00:23:03,230 >> Tako smo stavili Michelle ovdje. 583 00:23:03,230 --> 00:23:05,080 A tko ima broj 2? 584 00:23:05,080 --> 00:23:06,440 Broj 2 dolazi na leđa kao dobro. 585 00:23:06,440 --> 00:23:07,800 Broj 3? 586 00:23:07,800 --> 00:23:08,510 Izvrsno. 587 00:23:08,510 --> 00:23:16,570 Broj 4, broj 5, broj 6, broj 7, i broj 8. 588 00:23:16,570 --> 00:23:18,850 >> U redu, tako da se osjeća kao puno koraka, sigurno. 589 00:23:18,850 --> 00:23:22,390 No, sada ćemo vidjeti, ako ne možemo potvrditi vrsta intuitivno da je to 590 00:23:22,390 --> 00:23:26,190 Algoritam temelja, posebice n dobiva stvarno velik, kao što smo vidjeli 591 00:23:26,190 --> 00:23:29,170 s animacije, je bitno brži. 592 00:23:29,170 --> 00:23:33,400 Dakle, ja tvrdim ovaj algoritam, u najgorem slučaj, a čak iu najboljem slučaju, 593 00:23:33,400 --> 00:23:36,160 je velika O n puta log n. 594 00:23:36,160 --> 00:23:39,160 To je, tu je neki aspekt ove algoritam koji se n korake, ali 595 00:23:39,160 --> 00:23:43,110 postoji još jedan aspekt negdje u da iteracija, da petlje, da 596 00:23:43,110 --> 00:23:44,410 traje log n korake. 597 00:23:44,410 --> 00:23:49,154 Možemo li staviti prst na ono što naš onima dva broja se odnosi? 598 00:23:49,154 --> 00:23:51,320 Pa, gdje je - 599 00:23:51,320 --> 00:23:54,160 otkud mic ide? 600 00:23:54,160 --> 00:23:58,660 >> ZVUČNI 1: Biste prijavite se n nas nego što se u dvije - 601 00:23:58,660 --> 00:23:59,630 podijeli s dva, u biti. 602 00:23:59,630 --> 00:24:00,120 >> DAVID Malan: Točno. 603 00:24:00,120 --> 00:24:03,000 Svaki put smo vidjeli u bilo kojoj algoritma time sada, tu je bio takav obrazac 604 00:24:03,000 --> 00:24:04,200 podjele, podjele, podjele. 605 00:24:04,200 --> 00:24:05,700 I to je obično smanjuje za nešto što je 606 00:24:05,700 --> 00:24:07,100 logaritamska, prijavite baza 2. 607 00:24:07,100 --> 00:24:10,180 Ali, to stvarno može biti bilo što, ali prijaviti bazu 2. 608 00:24:10,180 --> 00:24:11,330 >> Sada što je n? 609 00:24:11,330 --> 00:24:14,550 Vidim da smo vrsta te podijeliti Dečki - ti podijeljene, te podijeliti, 610 00:24:14,550 --> 00:24:15,910 ti podijeljene, te podijeljeni. 611 00:24:15,910 --> 00:24:18,760 Gdje je kraj dolaze iz? 612 00:24:18,760 --> 00:24:19,810 >> Tako da je spajanjem. 613 00:24:19,810 --> 00:24:20,610 Jer misle o tome. 614 00:24:20,610 --> 00:24:25,420 Kada spojite osam ljudi zajedno, pri čemu polovica njih su set od četiri 615 00:24:25,420 --> 00:24:27,770 , a druga polovica su drugi set od četiri, kako idete 616 00:24:27,770 --> 00:24:28,820 radi o spajanju? 617 00:24:28,820 --> 00:24:30,830 Pa, vi to učinio prilično intuitivno. 618 00:24:30,830 --> 00:24:34,140 >> Ali, ako sam to učinio umjesto da malo više metodički, možda sam ukazao na 619 00:24:34,140 --> 00:24:38,090 Lijevi osoba prvi put s moje lijeve strane S druge strane, istaknuo je na lijevom osobi 620 00:24:38,090 --> 00:24:42,080 Od toga polovicu s moje desne strane, i Samo naknadno prošetao 621 00:24:42,080 --> 00:24:46,990 Popis, pokazujući na najmanji element svaki put, kreće moj prst preko i 622 00:24:46,990 --> 00:24:48,970 više po potrebi tijekom popisa. 623 00:24:48,970 --> 00:24:51,890 No, ono što je ključno za ovo spajanje Proces je sam usporedbom tih para 624 00:24:51,890 --> 00:24:53,460 elemenata. 625 00:24:53,460 --> 00:24:57,270 S desne polovice i od lijeva polovice, nikada neću još zaostaje. 626 00:24:57,270 --> 00:25:00,570 >> Znači spajanje sama izvodi ne više od n koraka. 627 00:25:00,570 --> 00:25:03,250 I koliko puta sam imala za to spajanje? 628 00:25:03,250 --> 00:25:07,150 Pa, ne više od n, a mi samo vidio da je s konačnim spajanja. 629 00:25:07,150 --> 00:25:13,120 I tako, ako to učinite nešto što traje log n koraka n puta, ili obratno, 630 00:25:13,120 --> 00:25:15,210 to će nam dati n puta log n. 631 00:25:15,210 --> 00:25:16,310 >> I zašto je ovo bolje? 632 00:25:16,310 --> 00:25:19,600 Pa, ako već znate da je zapisnik n je bolji od n - zar ne? 633 00:25:19,600 --> 00:25:22,590 Vidjeli smo u binarnom pretraživanje, telefonski imenik Primjer, log n je svakako 634 00:25:22,590 --> 00:25:23,760 bolje nego linearno. 635 00:25:23,760 --> 00:25:28,420 Dakle, to znači da je n puta log n Definitivno bolje od n puta drugi 636 00:25:28,420 --> 00:25:30,390 n, n AKA kvadrat. 637 00:25:30,390 --> 00:25:32,400 I to je ono što mi u konačnici osjećam. 638 00:25:32,400 --> 00:25:34,928 >> Tako veliki aplauz, ako se smo mogli, za ove dečke. 639 00:25:34,928 --> 00:25:38,920 >> [PLJESAK] 640 00:25:38,920 --> 00:25:41,550 >> DAVID Malan: A svoje oproštajne darove - možete zadržati brojeve, 641 00:25:41,550 --> 00:25:44,010 Ako biste željeli. 642 00:25:44,010 --> 00:25:45,620 I vaš oproštajni dar, kao i obično. 643 00:25:45,620 --> 00:25:47,290 Oh, a mi ćemo vam poslati snimke, Michelle. 644 00:25:47,290 --> 00:25:48,343 Hvala Vam. 645 00:25:48,343 --> 00:25:49,250 U redu. 646 00:25:49,250 --> 00:25:50,400 Posluži se stres loptu. 647 00:25:50,400 --> 00:25:54,110 >> I neka mi povucite prema gore, u međuvremenu, naš prijatelj Rob Bowden ponuditi 648 00:25:54,110 --> 00:25:59,520 nešto drugačiji pogled na ovo, jer možete misliti o tim 649 00:25:59,520 --> 00:26:01,280 Koraci se dešavaju u nešto drugačiji način. 650 00:26:01,280 --> 00:26:04,750 U stvari, set-up za ono što Rob je o da nam pokaže pretpostavlja da imamo 651 00:26:04,750 --> 00:26:09,030 već učinjeno parcelacija veliki popis u osam malih popisima, 652 00:26:09,030 --> 00:26:10,570 svaki od veličine 1. 653 00:26:10,570 --> 00:26:13,350 >> Dakle, mi smo promjenom pseudocode Malo samo da vrsta dobiti na 654 00:26:13,350 --> 00:26:15,320 Temeljna je ideja o tome kako spajanjem djela. 655 00:26:15,320 --> 00:26:17,600 No, vrijeme rada što on je o to učiniti još 656 00:26:17,600 --> 00:26:19,110 će biti isti. 657 00:26:19,110 --> 00:26:23,540 I opet, set-up je da je on počeo s osam lista veličine 1. 658 00:26:23,540 --> 00:26:27,730 Dakle, što ste propustili dio gdje je on zapravo učinio log N, N, log log n 659 00:26:27,730 --> 00:26:31,205 dijeljenjem ulazu. 660 00:26:31,205 --> 00:26:32,120 >> [Video reprodukciju] 661 00:26:32,120 --> 00:26:33,615 >> -To je to za korak jedan. 662 00:26:33,615 --> 00:26:38,270 Za drugi korak, više puta spajanje parova liste. 663 00:26:38,270 --> 00:26:39,210 >> DAVID Malan: Hm. 664 00:26:39,210 --> 00:26:41,270 Samo zvuk dolazi iz moje računalo. 665 00:26:41,270 --> 00:26:42,520 Pokušajmo to opet. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Samo svojevoljno izabrati koje - Sada imamo četiri liste. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 Saznajte prije. 670 00:26:52,120 --> 00:26:53,040 >> DAVID Malan: Tu smo. 671 00:26:53,040 --> 00:27:00,510 >> Stapanje-108 i 15, možemo završiti s popisa 15, 108. 672 00:27:00,510 --> 00:27:07,170 Spajanje 50 i 4, mi završiti s 4, 50. 673 00:27:07,170 --> 00:27:12,990 Spajanje 8 i 42, što završiti s 8, 42. 674 00:27:12,990 --> 00:27:19,970 I spajanjem 23 i 16, što završiti s 16, 23. 675 00:27:19,970 --> 00:27:23,270 >> Sada svi naši su popisi veličine 2. 676 00:27:23,270 --> 00:27:26,690 Primijetiti da je svaki od četiri lista je riješeno. 677 00:27:26,690 --> 00:27:29,450 Dakle, možemo početi spajanjem para popisima ponovno. 678 00:27:29,450 --> 00:27:38,420 Spajanje 15 i 108 i 4 i 50, što Prvi uzeti 4, a zatim 15, a zatim 679 00:27:38,420 --> 00:27:41,500 50, a zatim 108. 680 00:27:41,500 --> 00:27:50,610 Spajanje 8, 42 i 16, 23, prvo se 8, a zatim 16, zatim 23, 681 00:27:50,610 --> 00:27:52,700 zatim 42. 682 00:27:52,700 --> 00:27:57,600 >> Tako sada imamo samo dvije liste veličine 4, od kojih je riješeno. 683 00:27:57,600 --> 00:28:01,170 Dakle, sada smo spojiti te dvije liste. 684 00:28:01,170 --> 00:28:11,835 Prvo, uzmemo 4, a zatim smo se 8, onda ćemo uzeti 15, zatim 16, a zatim 685 00:28:11,835 --> 00:28:19,456 23, a zatim 42, zatim 50, a zatim 108. 686 00:28:19,456 --> 00:28:19,872 >> [END video reprodukciju] 687 00:28:19,872 --> 00:28:23,430 >> DAVID Malan: Opet, obavijest, on nikada dotakla dao šalicu više od jedan put 688 00:28:23,430 --> 00:28:24,860 nakon što napreduje dalje od njega. 689 00:28:24,860 --> 00:28:26,200 Dakle, on nikada ponoviti. 690 00:28:26,200 --> 00:28:29,850 Dakle, on je uvijek kreće na stranu, i to je mjesto gdje smo dobili naše n. 691 00:28:29,850 --> 00:28:33,290 >> Zašto ne pustiti mene podići jednu animaciju da smo ranije vidjeli, ali ovaj put 692 00:28:33,290 --> 00:28:35,110 fokusiranje samo na pisma vrste. 693 00:28:35,110 --> 00:28:38,030 Dopustite mi da ide naprijed i zumiranje u ovo ovdje. 694 00:28:38,030 --> 00:28:42,530 Prvo neka mi odabrati slučajan ulaz, uveličati ovu, a možete sortirati mjesta vide 695 00:28:42,530 --> 00:28:46,600 ono što mi je uzeo zdravo za gotovo, ranije, sortiranje pisama zapravo radi. 696 00:28:46,600 --> 00:28:50,330 >> Dakle, primijetite da ste dobili ove polovice ili ove četvrtine ili to osmina 697 00:28:50,330 --> 00:28:53,140 problem koji sve odjednom počnete uzimati dobru formu. 698 00:28:53,140 --> 00:28:57,070 I onda napokon, vidite, na samom kraju da bam, 699 00:28:57,070 --> 00:28:58,860 sve spojene zajedno. 700 00:28:58,860 --> 00:29:01,690 >> Dakle, ovo su samo tri različita se na istu ideju. 701 00:29:01,690 --> 00:29:05,980 No, ključni uvid, baš kao razdjelnice i osvojiti već u prvom razredu, 702 00:29:05,980 --> 00:29:10,640 bilo da smo odlučili da na neki način podijeliti Problem u nešto veliko, u 703 00:29:10,640 --> 00:29:14,760 nešto vrsta identične u duhu, , ali manji i manji i manji 704 00:29:14,760 --> 00:29:15,660 i manji. 705 00:29:15,660 --> 00:29:18,420 >> Sada još jedan zabavan način da se sortirati think o njima, iako to nije 706 00:29:18,420 --> 00:29:20,520 će vam dati isti intuitivno razumijevanje, je 707 00:29:20,520 --> 00:29:21,640 sljedeće animacije. 708 00:29:21,640 --> 00:29:25,400 Dakle, ovo je video netko staviti zajedno koji povezuje različite 709 00:29:25,400 --> 00:29:29,970 zvukovi s različitih poslovnih aktivnosti umetanja sortiranje, za udruživanjem vrste, i 710 00:29:29,970 --> 00:29:31,150 za par drugih. 711 00:29:31,150 --> 00:29:32,330 Dakle, u ovom trenutku, ja ću pogoditi Play. 712 00:29:32,330 --> 00:29:33,600 To je oko minutu. 713 00:29:33,600 --> 00:29:37,410 I iako još uvijek možete vidjeti obrasci događa, ovaj put možete 714 00:29:37,410 --> 00:29:41,420 Također čuti kako ti algoritmi su obavljanje drugačije i 715 00:29:41,420 --> 00:29:43,950 Nešto različitih uzoraka. 716 00:29:43,950 --> 00:29:45,830 >> To je neka vrsta umetanja. 717 00:29:45,830 --> 00:29:50,400 >> [Tonova igraju] 718 00:29:50,400 --> 00:29:52,400 >> DAVID Malan: Ponovno se pokušava za umetanje svaki element 719 00:29:52,400 --> 00:29:52,900 u kojoj je zaposlen. 720 00:29:52,900 --> 00:29:54,628 To je neka vrsta balon. 721 00:29:54,628 --> 00:30:10,097 >> [Tonova igraju] 722 00:30:10,097 --> 00:30:13,630 >> DAVID Malan: I vi možete sortirati dodira Kako relativno malo rade to radi 723 00:30:13,630 --> 00:30:15,834 na svakom koraku. 724 00:30:15,834 --> 00:30:20,470 To je ono što zvuči kao dosadu. 725 00:30:20,470 --> 00:30:21,472 >> [Tonova igraju] 726 00:30:21,472 --> 00:30:25,222 >> DAVID Malan: Ovo je neka vrsta odabira, gdje smo odabrali element želimo by 727 00:30:25,222 --> 00:30:28,845 prolazi kroz opet i opet i opet i nalazi se na početku. 728 00:30:28,845 --> 00:30:37,674 >> [Tonova igraju] 729 00:30:37,674 --> 00:30:43,970 >> DAVID Malan: Ovo je neka vrsta pisma, koje zaista možete početi osjećati. 730 00:30:43,970 --> 00:30:51,810 >> [Tonova igraju] 731 00:30:51,810 --> 00:30:54,770 >> [Smijeh] 732 00:30:54,770 --> 00:30:58,395 >> DAVID Malan: Nešto što se zove gnome sortiranje, koji nismo gledali. 733 00:30:58,395 --> 00:31:13,630 >> [Tonova igraju] 734 00:31:13,630 --> 00:31:17,910 >> DAVID Malan: Pa da vidim, sada, rastresena kao što su nadamo strane 735 00:31:17,910 --> 00:31:21,110 glazba, ako ja mogu skliznuti malo Malo matematike ovdje. 736 00:31:21,110 --> 00:31:24,850 Dakle, postoji četvrti put da možemo razmišljati o tome što to znači to 737 00:31:24,850 --> 00:31:29,210 funkcije koje će se brže od onih koje smo vidjeli prije. 738 00:31:29,210 --> 00:31:32,470 A ako ste došli na tečaj iz matematike pozadini, što 739 00:31:32,470 --> 00:31:36,030 zapravo zna možda već da može slap mandat na tom tehnikom - 740 00:31:36,030 --> 00:31:40,400 Naime rekurzija, funkcija nekako se zove. 741 00:31:40,400 --> 00:31:44,780 >> A opet, sjećam da spajanje vrsta pseudocode je rekurzivna u smislu 742 00:31:44,780 --> 00:31:48,460 da je jedan od Spoji sortirati o koracima je nazvati neku - 743 00:31:48,460 --> 00:31:49,740 to je, sama po sebi. 744 00:31:49,740 --> 00:31:52,480 No, srećom, jer mi je zadržao zove vrsta, ili spojiti vrsta, 745 00:31:52,480 --> 00:31:55,880 Naime, na sve manji i manji i manji popis, na kraju smo 746 00:31:55,880 --> 00:32:00,005 dno zahvaljujući tome što ćemo nazvati osnovni scenarij, tvrdi kodirani slučaj da 747 00:32:00,005 --> 00:32:04,270 rekao, ako popis je mali, manji od 2 u tom slučaju, jednostavno odmah vratiti. 748 00:32:04,270 --> 00:32:07,550 Ako nismo imali taj poseban slučaj, Algoritam nikad i dno, 749 00:32:07,550 --> 00:32:11,010 a vi bi doista dobili u klapa doista zauvijek. 750 00:32:11,010 --> 00:32:14,330 >> No, pretpostavimo da smo htjeli sada staviti neke brojeve na to, opet, pomoću n 751 00:32:14,330 --> 00:32:15,660 kao veličina ulaza. 752 00:32:15,660 --> 00:32:18,680 I htjela sam vas pitati, što je ukupno vrijeme koji su uključeni u 753 00:32:18,680 --> 00:32:19,800 radi spajanja vrsta? 754 00:32:19,800 --> 00:32:22,960 Ili općenitije, ono što je Trošak njega na vrijeme? 755 00:32:22,960 --> 00:32:24,730 >> Pa to je prilično lako izmjeriti da. 756 00:32:24,730 --> 00:32:29,010 Ako n je manje od 2, vrijeme potrebno u razvrstavanje n elemenata, 757 00:32:29,010 --> 00:32:30,480 gdje n je 2, 0 je. 758 00:32:30,480 --> 00:32:31,410 Budući da smo upravo vratili. 759 00:32:31,410 --> 00:32:32,510 Nema posla koji treba obaviti. 760 00:32:32,510 --> 00:32:35,660 Sada vjerojatno, možda je to jedan korak ili dva koraka shvatiti količinu 761 00:32:35,660 --> 00:32:38,420 rade, ali to je dovoljno blizu da je 0 Samo ću reći nema posla 762 00:32:38,420 --> 00:32:40,940 potreban ako popis je tako mali biti nezanimljiv. 763 00:32:40,940 --> 00:32:42,580 >> No, ovaj slučaj je zanimljiv. 764 00:32:42,580 --> 00:32:47,320 Rekurzivna slučaj bio grana pseudocode da je rekao drugdje, svojevrsni 765 00:32:47,320 --> 00:32:52,000 lijeva polovica, sortiranje pravo polovice, spojiti dvije polovice. 766 00:32:52,000 --> 00:32:55,530 Sad zašto se ovaj izraz predstavlja taj trošak? 767 00:32:55,530 --> 00:32:58,690 Pa, T n samo znači Vrijeme za sortiranje n elemenata. 768 00:32:58,690 --> 00:33:03,070 A onda na desnoj strani znak jednakosti tamo, T n podijeljeni 769 00:33:03,070 --> 00:33:06,600 by 2 se odnosi na troškove čega? 770 00:33:06,600 --> 00:33:07,570 Sortiranje lijevu polovicu. 771 00:33:07,570 --> 00:33:10,990 Druga T n dijelimo s 2 je vjerojatno se odnosi na trošak za 772 00:33:10,990 --> 00:33:12,390 sortirati desnu polovicu. 773 00:33:12,390 --> 00:33:14,590 >> A onda plus n? 774 00:33:14,590 --> 00:33:15,420 Je spajanjem. 775 00:33:15,420 --> 00:33:19,120 Jer, ako imate dvije liste, jednu od Veličina n više od 2, a drugi veličine n 776 00:33:19,120 --> 00:33:22,580 više od 2, morate biti dotaknuti svaki od tih elemenata, baš kao Rob 777 00:33:22,580 --> 00:33:24,990 dotakla svaki od šalice, i samo kao što je ukazao na svakom od 778 00:33:24,990 --> 00:33:26,310 Volonteri na pozornici. 779 00:33:26,310 --> 00:33:28,790 Tako je n trošak spajanja. 780 00:33:28,790 --> 00:33:31,780 >> Sada, nažalost, ova formula Također je sama rekurzivna. 781 00:33:31,780 --> 00:33:36,390 Dakle, ako se postavi pitanje, ako je n, recimo, 16, ako ima 16 ljudi na pozornici 782 00:33:36,390 --> 00:33:40,670 ili 16 šalica u videu, koliko je ukupno koraka je potrebno da ih sortirati 783 00:33:40,670 --> 00:33:41,550 udruži s vrstom? 784 00:33:41,550 --> 00:33:45,790 To je zapravo nije očigledan odgovor, jer sada morate izdvojiti od 785 00:33:45,790 --> 00:33:48,500 rekurzivno odgovoriti na ovu formulu. 786 00:33:48,500 --> 00:33:51,190 >> Ali to je u redu, jer neka mi predloži da ćemo učiniti sljedeće. 787 00:33:51,190 --> 00:33:56,670 Vrijeme koji su uključeni za sortiranje ili 16 ljudi 16 šalice će biti predstavljeni 788 00:33:56,670 --> 00:33:58,020 općenito, kao T od 16 godina. 789 00:33:58,020 --> 00:34:01,400 Ali to jednako, prema našim prethodnu formulu, 2 puta iznos 790 00:34:01,400 --> 00:34:04,780 Vrijeme koje je potrebno za sortiranje 8 šalice plus 16. 791 00:34:04,780 --> 00:34:08,590 I opet, plus 16 je vrijeme za spajanja, i dva puta T je od 8. 792 00:34:08,590 --> 00:34:10,790 Vrijeme za sortiranje lijevu polovicu i desnu polovicu. 793 00:34:10,790 --> 00:34:11,989 >> Ali opet, to nije dovoljno. 794 00:34:11,989 --> 00:34:13,210 Mi moramo zaroniti u dublje. 795 00:34:13,210 --> 00:34:16,409 To znači da ćemo morati odgovarati Pitanje, što je T od 8? 796 00:34:16,409 --> 00:34:19,610 Pa T od 8 je samo 2 T puta od 4 plus osam. 797 00:34:19,610 --> 00:34:20,520 Pa, ono što je T od 4? 798 00:34:20,520 --> 00:34:23,780 T od 4. je samo 2 puta T od 2 plus četiri. 799 00:34:23,780 --> 00:34:25,489 Pa, ono što je T od 2? 800 00:34:25,489 --> 00:34:29,030 T od 2 je samo 2 puta T od 1 plus dva. 801 00:34:29,030 --> 00:34:31,940 >> I opet, mi smo vrsta dobivanja zaglavi u ovom ciklusu. 802 00:34:31,940 --> 00:34:34,790 No, to je oko pogoditi da je tzv. osnovni scenarij. 803 00:34:34,790 --> 00:34:37,310 Jer ono što je od 1. T, nije tvrdimo? 804 00:34:37,310 --> 00:34:37,810 0. 805 00:34:37,810 --> 00:34:39,730 Dakle, sada je konačno, možemo raditi unatrag. 806 00:34:39,730 --> 00:34:44,290 >> Ako T od 1 je 0, ja sada mogu ići natrag gore jedan poredati prema ovom čovjeku ovdje, a ja mogu 807 00:34:44,290 --> 00:34:46,330 priključite 0 za T iz jedne. 808 00:34:46,330 --> 00:34:51,770 Dakle, to znači da je jednaka dva puta nula, inače poznat kao 0, plus dva. 809 00:34:51,770 --> 00:34:53,739 I tako da je cijeli izraz je 2. 810 00:34:53,739 --> 00:34:58,740 >> Sada, ako sam uzeti T od 2, čiji odgovor je 2, uključite ga u srednjoj liniji, T 811 00:34:58,740 --> 00:35:02,740 od 4, to mi daje dva puta 2 plus 4, pa 8. 812 00:35:02,740 --> 00:35:07,080 Ako sam tada priključiti 8 do prethodna linije, to mi daje 2 puta 8, 16. 813 00:35:07,080 --> 00:35:12,470 A ako smo tada i dalje da s 24, dodavanjem u 16., napokon smo dobili 814 00:35:12,470 --> 00:35:13,820 vrijednost 64. 815 00:35:13,820 --> 00:35:18,480 >> Sada kada je i sama vrsta govori ništa za n zapis, 816 00:35:18,480 --> 00:35:20,700 O veliki, omega kojeg smo pričali. 817 00:35:20,700 --> 00:35:24,890 No, ispada da je doista 64 16, veličina ulaz, 818 00:35:24,890 --> 00:35:27,110 prijavite bazu dvije od 16 godina. 819 00:35:27,110 --> 00:35:30,200 A ako je to nešto nepoznato, samo mislim vratiti, i to ću se vratiti 820 00:35:30,200 --> 00:35:30,700 da vas na kraju. 821 00:35:30,700 --> 00:35:33,775 Ako je ovo dnevnik baza 2, to je kao 2 podigli na ono što vam daje 16? 822 00:35:33,775 --> 00:35:36,380 Oh, to je 4, tako da je 16 puta 4. 823 00:35:36,380 --> 00:35:39,380 >> I opet, to nije velika stvar, ako to svojevrsni je maglovita sjećanja sada. 824 00:35:39,380 --> 00:35:43,720 Ali za sada, uzeti na vjeri da 16 log 16 je 64. 825 00:35:43,720 --> 00:35:46,590 I tako je doista, s ovom jednostavnom zdravom razumu provjerili smo potvrdili - 826 00:35:46,590 --> 00:35:48,250 ali ne dokazuje službeno - 827 00:35:48,250 --> 00:35:52,800 da je vrijeme rada spajanja svojevrsni je doista n log n. 828 00:35:52,800 --> 00:35:53,790 >> Dakle, nije loše. 829 00:35:53,790 --> 00:35:57,260 To je svakako bolje nego Algoritmi koje smo vidjeli do sada, i 830 00:35:57,260 --> 00:36:00,710 to je zato što smo iskoristio, jedan, Tehnika se zove rekurzija. 831 00:36:00,710 --> 00:36:03,880 No, zanimljivije od toga, da je pojam podjele i osvajati. 832 00:36:03,880 --> 00:36:07,460 Opet, doista tjedna 0 stvari koje i sada se ponavlja u 833 00:36:07,460 --> 00:36:08,740 više uvjerljiv način. 834 00:36:08,740 --> 00:36:11,750 >> Sada zabavno malo vježbe, ako ste Nikad to učinio - i vjerojatno 835 00:36:11,750 --> 00:36:14,660 Ne bi, jer je svojevrsni normalno ljudi ne misle da to učinite. 836 00:36:14,660 --> 00:36:20,650 Ali ako idem na google.com, a ako Želim naučiti nešto o 837 00:36:20,650 --> 00:36:22,356 rekurzija, Enter. 838 00:36:22,356 --> 00:36:25,106 839 00:36:25,106 --> 00:36:29,058 >> [Smijeh] 840 00:36:29,058 --> 00:36:32,030 [VIŠE Smijeh] 841 00:36:32,030 --> 00:36:33,385 DAVID Malan: loša šala polako širi. 842 00:36:33,385 --> 00:36:34,450 [Smijeh] 843 00:36:34,450 --> 00:36:36,970 DAVID Malan: Samo u slučaju, da je ona tu. 844 00:36:36,970 --> 00:36:38,710 Nisam to piše u krivu, a tu je šala. 845 00:36:38,710 --> 00:36:40,810 U redu. 846 00:36:40,810 --> 00:36:42,950 Objasnite to ljudi pored vas, ako to nije dosta kliknuo samo još. 847 00:36:42,950 --> 00:36:47,650 No, rekurzija, općenito, odnosi se na proces funkcije poziva 848 00:36:47,650 --> 00:36:51,430 sama, ili općenitije, dijeljenjem Problem u nešto što može biti 849 00:36:51,430 --> 00:36:56,220 riješiti parče rješavanjem identični predstavnička problemi. 850 00:36:56,220 --> 00:36:58,400 >> Pa, neka je promjena stupnjeva prijenosa samo na trenutak. 851 00:36:58,400 --> 00:37:00,840 Mi smo željeli završiti na određenim cliffhangers, pa krenimo za postavljanje 852 00:37:00,840 --> 00:37:05,870 faza, za nekoliko minuta, na vrlo jednostavnom idejom - 853 00:37:05,870 --> 00:37:07,620 da je od zamjene dva elementa, zar ne? 854 00:37:07,620 --> 00:37:10,040 Sve ove algoritama smo bili govori o posljednjih nekoliko 855 00:37:10,040 --> 00:37:12,420 Predavanja uključuju neke vrsta zamjene. 856 00:37:12,420 --> 00:37:14,630 Danas je vizualizirano od strane uzimajući ih up iz svojih stolica i 857 00:37:14,630 --> 00:37:18,570 šetnju, ali u kodu, mi bismo samo uzeti jedan element iz jednog polja 858 00:37:18,570 --> 00:37:20,370 i buć ga u drugu. 859 00:37:20,370 --> 00:37:21,880 >> Pa kako ćemo ići oko radiš ovo? 860 00:37:21,880 --> 00:37:24,850 Pa, neka mi ići naprijed i pisati Program brzo ovdje. 861 00:37:24,850 --> 00:37:31,600 Ja ću ići naprijed i učiniti ovo što je sljedeće. 862 00:37:31,600 --> 00:37:33,910 Nazovimo to - 863 00:37:33,910 --> 00:37:38,070 Što želimo nazvati ovo? 864 00:37:38,070 --> 00:37:38,650 >> Zapravo, nije. 865 00:37:38,650 --> 00:37:39,420 Dopustite mi premotati. 866 00:37:39,420 --> 00:37:41,220 Ne želim to učiniti Još alpinista. 867 00:37:41,220 --> 00:37:42,270 To će pokvariti zabavu. 868 00:37:42,270 --> 00:37:43,600 Učinimo to, umjesto. 869 00:37:43,600 --> 00:37:47,430 >> Pretpostavimo da želim napisati nešto Program obuhvaća i da je sada to 870 00:37:47,430 --> 00:37:48,700 Ideja rekurzije. 871 00:37:48,700 --> 00:37:50,370 Nekako sam dobio ispred sebe ima. 872 00:37:50,370 --> 00:37:51,420 Ja ću učiniti sljedeće. 873 00:37:51,420 --> 00:38:00,220 >> Prvo, brzi su od standardnog io.h, kao i uključuju mjesta cs50.h. 874 00:38:00,220 --> 00:38:03,200 A onda ću ići naprijed i proglasiti int main prazninu 875 00:38:03,200 --> 00:38:04,360 na uobičajeni način. 876 00:38:04,360 --> 00:38:07,920 I shvatio sam elek-tro konvulzivna datoteku, tako da neka mi samo dodati. C produljenje ovdje tako 877 00:38:07,920 --> 00:38:09,510 da možemo prevesti ga ispravno. 878 00:38:09,510 --> 00:38:10,970 Započnite ovu funkciju off. 879 00:38:10,970 --> 00:38:13,290 >> A funkcija želim pisati, sasvim Jednostavno, to je jedna pita 880 00:38:13,290 --> 00:38:16,210 Korisnik za broj, a zatim zbraja svi brojevi između da 881 00:38:16,210 --> 00:38:19,920 broj i, recimo, 0. 882 00:38:19,920 --> 00:38:22,510 Dakle, prvo ću ići naprijed i proglasiti int n. 883 00:38:22,510 --> 00:38:24,760 Tada sam kopirati neki kod koji upotrijebili smo za neko vrijeme. 884 00:38:24,760 --> 00:38:26,660 Dok je nešto istinito. 885 00:38:26,660 --> 00:38:28,000 Ja ću se vratiti na to u trenutku. 886 00:38:28,000 --> 00:38:29,010 >> Što želim učiniti? 887 00:38:29,010 --> 00:38:33,460 Želim reći printf pozitivno cijeli molimo. 888 00:38:33,460 --> 00:38:36,130 A onda ću se kažu n dobiva se int. 889 00:38:36,130 --> 00:38:38,800 Pa opet, neki predloženi broj koje smo koristili prije. 890 00:38:38,800 --> 00:38:40,810 I ja ću to učiniti a n je manje od 1. 891 00:38:40,810 --> 00:38:44,120 Dakle, to će osigurati da korisnik mi daje pozitivan cijeli broj. 892 00:38:44,120 --> 00:38:45,490 >> A sada ću učiniti sljedeće. 893 00:38:45,490 --> 00:38:51,020 Želim zbrojiti sve brojeve između 1 i i n ili 0, i n, 894 00:38:51,020 --> 00:38:52,570 ravnopravno, kako bi dobili ukupnu sumu. 895 00:38:52,570 --> 00:38:55,100 Tako veliko sigma simbol da je možda podsjetiti. 896 00:38:55,100 --> 00:38:59,050 Dakle, ja ću to učiniti prvi poziv Funkcija se zove Sigma, 897 00:38:59,050 --> 00:39:06,030 to prolazi u n, a onda ću se printf kažu, odgovor je ovdje. 898 00:39:06,030 --> 00:39:08,180 >> Dakle, ukratko, sam doći i int od korisnika. 899 00:39:08,180 --> 00:39:09,280 Ja bi to pozitivno. 900 00:39:09,280 --> 00:39:12,700 Izjavljujem varijablu odgovor Tip int i trgovina u njoj povratak 901 00:39:12,700 --> 00:39:15,610 Vrijednost sigma, prolazeći u n kao ulaz. 902 00:39:15,610 --> 00:39:17,060 A onda sam isprintati taj odgovor. 903 00:39:17,060 --> 00:39:19,550 >> Nažalost, iako zvuči sigma kao nešto što bi moglo biti u 904 00:39:19,550 --> 00:39:24,040 math.h file, njegova izjava, to zapravo nije. 905 00:39:24,040 --> 00:39:24,690 Dakle, to je u redu. 906 00:39:24,690 --> 00:39:26,170 Ja mogu provesti ovaj ja osobno. 907 00:39:26,170 --> 00:39:29,160 Idem implementirati funkciju pod nazivom sigma, i to će potrajati 908 00:39:29,160 --> 00:39:29,900 parametar - 909 00:39:29,900 --> 00:39:32,100 Nazovimo to m, samo tako da je drugačije. 910 00:39:32,100 --> 00:39:35,910 I onda se ovdje, ja ću reći, i, ako je m je manji od 1 - to je 911 00:39:35,910 --> 00:39:38,180 vrlo nezanimljivih programa. 912 00:39:38,180 --> 00:39:41,700 Dakle, ja ću ići naprijed i odmah vratiti 0.. 913 00:39:41,700 --> 00:39:45,920 To jednostavno nema smisla da zbrojimo sve su brojevi između 1 i m ako m 914 00:39:45,920 --> 00:39:48,470 Sam je 0 ili negativan. 915 00:39:48,470 --> 00:39:50,900 >> A onda ću ići naprijed i to vrlo iterativno. 916 00:39:50,900 --> 00:39:53,090 Ja ću učiniti ovu vrstu stare škole, i ja ću ići naprijed 917 00:39:53,090 --> 00:39:57,150 i reći da ću se proglasiti iznos biti 0. 918 00:39:57,150 --> 00:39:59,630 Tada ću imati za petlju int - 919 00:39:59,630 --> 00:40:02,820 i neka mi to učiniti da bude jednak Raspodjela broj, tako da imate kopiju 920 00:40:02,820 --> 00:40:07,500 kod kuće. int i dobiva jedan na do i manji od ili jednak m. 921 00:40:07,500 --> 00:40:09,430 i plus plus. 922 00:40:09,430 --> 00:40:11,430 A onda unutar ove for petlje - 923 00:40:11,430 --> 00:40:12,440 skoro smo stigli - 924 00:40:12,440 --> 00:40:15,810 Zbroj dobiva iznos plus jedan. 925 00:40:15,810 --> 00:40:17,670 A onda ću se vratiti svotu. 926 00:40:17,670 --> 00:40:19,420 >> Pa sam to učinio brzo, doduše dosta. 927 00:40:19,420 --> 00:40:22,775 Ali opet, glavna funkcija je lijepa jednostavno, na temelju koda smo 928 00:40:22,775 --> 00:40:23,190 napisano do sada. 929 00:40:23,190 --> 00:40:25,610 Koristi dual loop dobiti pozitivno int od korisnika. 930 00:40:25,610 --> 00:40:29,870 I onda prođe taj int na novu funkciju zove Sigma, nazivajući ga, opet, n. 931 00:40:29,870 --> 00:40:33,100 I sam pohraniti povratnu vrijednost, odgovor iz crne kutije trenutačno 932 00:40:33,100 --> 00:40:35,460 poznat kao sigma, u varijabla zove odgovor. 933 00:40:35,460 --> 00:40:36,580 Onda sam ga ispisati. 934 00:40:36,580 --> 00:40:39,090 >> Ako mi sada nastaviti priču, Kako se provodi sigma? 935 00:40:39,090 --> 00:40:40,840 Predlažem provesti na sljedeći način. 936 00:40:40,840 --> 00:40:43,560 Prvo, malo provjeru pogrešaka kako bi bili sigurni da korisnik nije 937 00:40:43,560 --> 00:40:46,480 petljaju sa mnom i prolazi u Neki negativna ili 0 vrijednosti. 938 00:40:46,480 --> 00:40:49,710 Tada sam proglasiti varijablu pod nazivom Ukratko i postavite na 0. 939 00:40:49,710 --> 00:40:55,910 >> I sad sam se početi kretati od ja jednaka 1 pa sve do i uključujući m, 940 00:40:55,910 --> 00:41:00,130 jer želim uključiti sve brojeva od jedan do m, uključivo. 941 00:41:00,130 --> 00:41:04,350 A unutar toga za petlju, ja samo to Zbroj dobiva ono što je sada, plus 942 00:41:04,350 --> 00:41:08,900 vrijednost i. 943 00:41:08,900 --> 00:41:10,370 Plus vrijednost i. 944 00:41:10,370 --> 00:41:14,090 >> Kao na stranu, ako niste vidjeli ovo prije, ima nekih sintaktička šećera 945 00:41:14,090 --> 00:41:14,870 za ovu liniju. 946 00:41:14,870 --> 00:41:21,120 Ja mogu napisati to kao plus ja jednako, samo da ste sebi nekoliko pritisaka tipke 947 00:41:21,120 --> 00:41:22,570 i gledati malo hladnije. 948 00:41:22,570 --> 00:41:23,140 Ali to je sve. 949 00:41:23,140 --> 00:41:24,660 To je funkcionalno ista stvar. 950 00:41:24,660 --> 00:41:26,710 >> Nažalost, ovaj broj je Ne ide sastaviti još. 951 00:41:26,710 --> 00:41:31,600 Ako sam pokrenuti bi sigma 0, kako sam Ja ću dobiti vikao na? 952 00:41:31,600 --> 00:41:33,473 Što će se ne sviđa? 953 00:41:33,473 --> 00:41:35,740 >> PUBLIKA: [nečujno]. 954 00:41:35,740 --> 00:41:37,800 >> DAVID Malan: Da, nisam proglasi Funkcija do vrha, zar ne? 955 00:41:37,800 --> 00:41:40,590 C je glupo, u smislu da je samo čini ono što vam reći što učiniti, a vi 956 00:41:40,590 --> 00:41:41,880 moraju to učiniti u tom redoslijedu. 957 00:41:41,880 --> 00:41:45,910 I tako, ako sam pogodio Unesite ovdje, ja ću dobili upozorenje o sigma implicitno 958 00:41:45,910 --> 00:41:46,860 Deklaracija. 959 00:41:46,860 --> 00:41:48,120 >> Oh, nije problem. 960 00:41:48,120 --> 00:41:50,370 I može ići do vrha, a mogu kažu, sve u redu, čekaj malo. 961 00:41:50,370 --> 00:41:54,240 Sigma je funkcija koja vraća int a očekuje 962 00:41:54,240 --> 00:41:56,620 int kao ulazni, zarez. 963 00:41:56,620 --> 00:41:59,550 Ili sam mogao staviti cijeli funkciju Glavni iznad, ali općenito, ja bih 964 00:41:59,550 --> 00:42:02,260 Preporučujem protiv toga, jer je lijepo je uvijek imati glavni na vrhu tako 965 00:42:02,260 --> 00:42:06,310 možete roniti u pravu i znaju što Program radi čitajući glavna prvi. 966 00:42:06,310 --> 00:42:07,930 >> Pa sad neka mi jasan zaslon. 967 00:42:07,930 --> 00:42:09,330 Remake sigma 0. 968 00:42:09,330 --> 00:42:10,340 Sve se čini da provjerite. 969 00:42:10,340 --> 00:42:11,970 Dopustite mi da vodim sigma 0. 970 00:42:11,970 --> 00:42:12,770 Pozitivno me. 971 00:42:12,770 --> 00:42:15,580 Ja ću mu dati broj 3 da bi to jednostavno. 972 00:42:15,580 --> 00:42:18,710 Tako da bi mi dati 3 plus 2 plus 1, tako 6. 973 00:42:18,710 --> 00:42:20,750 Enter, i doista sam se šest. 974 00:42:20,750 --> 00:42:21,820 >> Ja mogu učiniti nešto veći - 975 00:42:21,820 --> 00:42:24,080 50, 12, 75. 976 00:42:24,080 --> 00:42:27,690 Baš kao tangentu, ja ću to učiniti nešto smiješno kao što je stvarno velik 977 00:42:27,690 --> 00:42:30,375 broj, Oh, kako je zapravo razrađen - 978 00:42:30,375 --> 00:42:31,600 eh, ja ne mislim da je u pravu. 979 00:42:31,600 --> 00:42:32,810 Idemo vidjeti. 980 00:42:32,810 --> 00:42:34,060 Idemo jako igrati s njim. 981 00:42:34,060 --> 00:42:37,150 982 00:42:37,150 --> 00:42:38,400 >> To je problem. 983 00:42:38,400 --> 00:42:43,180 984 00:42:43,180 --> 00:42:44,970 Što se zbiva? 985 00:42:44,970 --> 00:42:46,050 Broj nije tako loše. 986 00:42:46,050 --> 00:42:48,470 To je još uvijek linearno. 987 00:42:48,470 --> 00:42:50,810 Zviždanje je dobar učinak, iako. 988 00:42:50,810 --> 00:42:52,060 Što se zbiva? 989 00:42:52,060 --> 00:42:54,700 990 00:42:54,700 --> 00:42:55,620 >> Ne siguran ako sam to čuo. 991 00:42:55,620 --> 00:42:57,620 Tako ispada - a ovo kao na stranu. 992 00:42:57,620 --> 00:42:59,400 To nije jezgra Ideja rekurzije. 993 00:42:59,400 --> 00:43:02,480 Ispada, jer sam pokušavao predstavlja takav veliki broj, većina 994 00:43:02,480 --> 00:43:06,980 Vjerojatno je se pogrešno tumači C Ne kao pozitivan broj, 995 00:43:06,980 --> 00:43:09,980 , ali negativni broj. 996 00:43:09,980 --> 00:43:12,690 >> Nismo razgovarali o tome, ali to Ispada postoje negativni brojevi 997 00:43:12,690 --> 00:43:14,210 u svijetu osim do pozitivnih brojeva. 998 00:43:14,210 --> 00:43:16,290 A način na koji možete predstavljaju negativan broj 999 00:43:16,290 --> 00:43:19,530 bitno je, koristite jedan Posebna malo naznačiti 1000 00:43:19,530 --> 00:43:20,400 pozitivni tijekom negativna. 1001 00:43:20,400 --> 00:43:22,950 To je malo složeniji od toga, ali to je osnovna ideja. 1002 00:43:22,950 --> 00:43:26,740 >> Dakle, nažalost, ako je C je zbunjujuće jedan od tih bitova što zapravo znači, 1003 00:43:26,740 --> 00:43:30,790 Oh, to je negativni broj, moj petlje Ovdje, na primjer, je zapravo nikad nije 1004 00:43:30,790 --> 00:43:31,740 će se prekinuti. 1005 00:43:31,740 --> 00:43:33,850 Dakle, ako sam zapravo ispisuje nešto opet i opet, mi bismo 1006 00:43:33,850 --> 00:43:34,650 vidim puno. 1007 00:43:34,650 --> 00:43:36,220 Ali opet, to je osim točke. 1008 00:43:36,220 --> 00:43:38,590 To je zapravo samo vrsta intelektualnu znatiželju da ćemo doći 1009 00:43:38,590 --> 00:43:39,550 natrag na kraju. 1010 00:43:39,550 --> 00:43:43,400 Ali za sada, ovo je točno Provedba ako pretpostavimo da 1011 00:43:43,400 --> 00:43:45,970 Korisnik će osigurati Ints da stane u roku Ints. 1012 00:43:45,970 --> 00:43:49,370 >> No ja tvrdim da je to broj, iskreno, može učiniti puno više jednostavno. 1013 00:43:49,370 --> 00:43:54,060 Ako je cilj na ruku je da se broj m kao i dodati mu sve 1014 00:43:54,060 --> 00:43:59,510 brojevi između njega i 1, ili obrnuto između 1 i to, ja tvrdim 1015 00:43:59,510 --> 00:44:03,380 da ja mogu posuditi ovu ideju da spajanje sortiranje imala, koji je vodeći problem 1016 00:44:03,380 --> 00:44:05,660 ove veličine i dijeljenjem u nešto manjoj. 1017 00:44:05,660 --> 00:44:09,875 Možda nije ni upola, ali manji, ali reprezentativno isti. 1018 00:44:09,875 --> 00:44:12,130 Sve ideje, ali manji problem. 1019 00:44:12,130 --> 00:44:15,470 >> Dakle, ja sam zapravo - neka mi spremiti ovu datoteku s različitim brojem verzije. 1020 00:44:15,470 --> 00:44:17,670 Zvat ćemo ovu verziju 1 umjesto 0. 1021 00:44:17,670 --> 00:44:20,790 A ja tvrdim da sam zapravo mogu reimplement to u ovom vrstom 1022 00:44:20,790 --> 00:44:22,160 um-savijanje način. 1023 00:44:22,160 --> 00:44:23,710 >> Ja ću ostaviti dio nje same. 1024 00:44:23,710 --> 00:44:27,710 Ja ću reći, ako m je manje od ili čak jednak 0 - 1025 00:44:27,710 --> 00:44:29,280 Samo ću se malo više analni ovaj put 1026 00:44:29,280 --> 00:44:30,520 s mojim provjere pogreške - 1027 00:44:30,520 --> 00:44:33,190 Ja ću ići naprijed i povratak 0. 1028 00:44:33,190 --> 00:44:34,490 To je proizvoljna. 1029 00:44:34,490 --> 00:44:37,500 Ja sam samo jednostavno odlučivanje, ako korisnik mi daje negativan broj, ja sam 1030 00:44:37,500 --> 00:44:41,490 vraća 0, i oni bi trebali imati čitanje Dokumentacija pobliže. 1031 00:44:41,490 --> 00:44:42,170 >> Drugo - 1032 00:44:42,170 --> 00:44:44,070 primjetiti ono što ću učiniti. 1033 00:44:44,070 --> 00:44:49,260 Inače ću se vratiti M PLUS - 1034 00:44:49,260 --> 00:44:51,010 Što je sigma od m? 1035 00:44:51,010 --> 00:44:56,710 Pa, sigma m od plus minus 1 m, plus minus 2 m, plus minus 3 m. 1036 00:44:56,710 --> 00:44:58,030 Ne želim pisati sve to van. 1037 00:44:58,030 --> 00:44:59,120 Zašto ne ja samo punt? 1038 00:44:59,120 --> 00:45:05,080 Rekurzivno sebe nazivaju s nešto manji problem, zarez, 1039 00:45:05,080 --> 00:45:06,840 i pozvati ga na dan? 1040 00:45:06,840 --> 00:45:07,040 >> Točno? 1041 00:45:07,040 --> 00:45:10,980 Sada i ovdje, možda ćete osjetiti ili brinuti da je beskonačna petlja koja sam 1042 00:45:10,980 --> 00:45:15,450 izaziva, pri čemu sam provedbi Sigma pozivom sigma. 1043 00:45:15,450 --> 00:45:20,342 Ali to je savršeno u redu, jer sam Mislio uoči dodao koji linije? 1044 00:45:20,342 --> 00:45:22,600 >> PUBLIKA: [nečujno]. 1045 00:45:22,600 --> 00:45:25,430 >> David Malan: 23 do 26 godina, koji Ako je moj uvjet. 1046 00:45:25,430 --> 00:45:28,390 Jer ono što je lijepo o Oduzimanje ovdje, jer sam držati 1047 00:45:28,390 --> 00:45:31,180 Predaja Sigma manji problemi, manja Problemi, manja - to nije 1048 00:45:31,180 --> 00:45:31,870 upola manji. 1049 00:45:31,870 --> 00:45:34,380 To je samo korak beba manja, ali to je u redu. 1050 00:45:34,380 --> 00:45:38,050 Jer na kraju, mi ćemo raditi naš put prema dolje do 1 ili 0.. 1051 00:45:38,050 --> 00:45:41,630 A kad smo pogodak 0, sigma nije će se zvati više. 1052 00:45:41,630 --> 00:45:43,590 To će se odmah vratiti 0.. 1053 00:45:43,590 --> 00:45:47,960 >> Tako je učinak, ako je ovo vrsta vjetra u vašem umu, je dodati M PLUS 1054 00:45:47,960 --> 00:45:52,740 m minus 1, plus minus 2 m, plus minus m 3, plus točka, točka, točka, m minus 1055 00:45:52,740 --> 00:45:57,820 m, na kraju dajući vam 0, a Učinak je u konačnici dodati sve 1056 00:45:57,820 --> 00:45:59,070 ove stvari zajedno. 1057 00:45:59,070 --> 00:46:02,380 Pa nismo, s rekurzije, riješiti problem koji smo 1058 00:46:02,380 --> 00:46:03,470 nije mogao riješiti prije. 1059 00:46:03,470 --> 00:46:06,840 Doista, verzija 0 toga, i svaka Problem do danas, je rješiva 1060 00:46:06,840 --> 00:46:09,980 sa samo pomoću za petlje ili dok se petlje ili slični konstrukti. 1061 00:46:09,980 --> 00:46:13,150 >> No, rekurzija, usuđujem se reći, daje nam drugačiji način razmišljanja o 1062 00:46:13,150 --> 00:46:17,010 problemima, pri čemu ako se može uzeti Problem, podijelite ga s nečim 1063 00:46:17,010 --> 00:46:22,340 Veliki nešto u nešto nešto manja, ja tvrdim da možemo to riješiti 1064 00:46:22,340 --> 00:46:26,040 možda malo više elegantno u smislu od dizajna, s manje koda, 1065 00:46:26,040 --> 00:46:30,980 a možda čak i riješiti probleme koji bi biti teže, jer ćemo na kraju 1066 00:46:30,980 --> 00:46:33,280 vidi, rješavanje čisto iterativno. 1067 00:46:33,280 --> 00:46:35,980 >> No, roman u koji sam učinio žele nas ostaviti na bilo to. 1068 00:46:35,980 --> 00:46:40,720 Dopustite mi da ide naprijed i otvorite up file od - 1069 00:46:40,720 --> 00:46:44,300 Zapravo, pusti me i to učiniti vrlo brzo. 1070 00:46:44,300 --> 00:46:46,875 Dopustite mi da ide naprijed i predlaže sljedeće. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Među današnjem kod je ovu sliku ovdje. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 Ova ovdje, noswap. 1075 00:47:03,050 --> 00:47:06,260 >> Dakle, ovo je glupo malo program koji I šlag gore koji tvrdi da to učinite 1076 00:47:06,260 --> 00:47:06,940 sljedeće. 1077 00:47:06,940 --> 00:47:10,140 U glavnom, najprije izjavljuje int x pozvao i dodjeljuje 1078 00:47:10,140 --> 00:47:11,100 vrijednost od 1. 1079 00:47:11,100 --> 00:47:13,520 Tada je riječ int y i dodjeljuje joj vrijednost 2. 1080 00:47:13,520 --> 00:47:15,310 Zatim ga ispisuje ono xiy je. 1081 00:47:15,310 --> 00:47:17,781 Tada je, kaže, zamjene, dot dot dot. 1082 00:47:17,781 --> 00:47:21,670 >> Onda ona tvrdi da se zove funkciju pozvao zamjenu, prolazeći u X i 1083 00:47:21,670 --> 00:47:24,290 godina, ideja je da se nadamo xiy će se vratiti 1084 00:47:24,290 --> 00:47:25,620 drugačija, suprotno. 1085 00:47:25,620 --> 00:47:27,110 Tada je tvrditi zamijenili! 1086 00:47:27,110 --> 00:47:28,420 s uskličnikom. 1087 00:47:28,420 --> 00:47:30,190 Zatim ga ispisuje xiy. 1088 00:47:30,190 --> 00:47:33,480 >> No, ispostavilo se da je to vrlo jednostavna demonstracija prema dolje 1089 00:47:33,480 --> 00:47:35,570 Ovdje je zapravo lud. 1090 00:47:35,570 --> 00:47:38,870 Iako sam privremenu promjenjiva i privremeno stavljanje u 1091 00:47:38,870 --> 00:47:42,010 to, onda ću reassigning vrijednost b - 1092 00:47:42,010 --> 00:47:45,080 koji osjeća razumno, jer sam spremiti kopiju na temp. 1093 00:47:45,080 --> 00:47:48,410 Tada sam ažurirati b za jednake sve što je u temp. 1094 00:47:48,410 --> 00:47:51,610 Ova vrsta oklopa igara kreće u B i b u koristeći ovaj 1095 00:47:51,610 --> 00:47:54,360 srednje-čovjek zove temp osjeća savršeno razumno. 1096 00:47:54,360 --> 00:47:57,270 >> Ali ja tvrdim da kad sam pokrenuti ovu broj, kao što ću učiniti sada - 1097 00:47:57,270 --> 00:47:59,490 neka mi ići naprijed i zalijepite ga ovdje. 1098 00:47:59,490 --> 00:48:01,995 Nazvat ću ovo noswap.c. 1099 00:48:01,995 --> 00:48:05,630 I kao što ime sugerira, to nije će se odgovarajući program. 1100 00:48:05,630 --> 00:48:09,460 Provjerite noswap. / Nema swapa. 1101 00:48:09,460 --> 00:48:12,110 x je 1, y je 2, zamjene, zamijeniti. 1102 00:48:12,110 --> 00:48:14,220 x je 1, y je 2. 1103 00:48:14,220 --> 00:48:16,920 To je temeljno pogrešno, čak i iako ovo izgleda savršeno 1104 00:48:16,920 --> 00:48:17,730 razumno mene. 1105 00:48:17,730 --> 00:48:21,330 I tu je razlog, ali nismo će otkriti razlog samo još. 1106 00:48:21,330 --> 00:48:24,610 >> Za sada u drugom Cliffhanger sam htjela vas ostaviti s je ovo, 1107 00:48:24,610 --> 00:48:27,120 Najava vrsta na kupon kodovi. 1108 00:48:27,120 --> 00:48:31,590 Naša inovacija s kasnim dana ove godine izazvalo je ne-beznačajan broj 1109 00:48:31,590 --> 00:48:33,830 pitanja, što je Nije nam namjera. 1110 00:48:33,830 --> 00:48:36,590 Namjera ovih kupon kodovi, pri čemu ako ne dio problema 1111 00:48:36,590 --> 00:48:39,850 postavljen početkom, čime se dobiva dodatni dan, je stvarno pomoći ti dečki pomoći 1112 00:48:39,850 --> 00:48:42,420 sami početi rano, vrsta od strane vas poticanje. 1113 00:48:42,420 --> 00:48:44,880 Pomaže nam distribuirati opterećenje diljem Radno vrijeme bolje, tako da je 1114 00:48:44,880 --> 00:48:45,740 to je vrsta win-win. 1115 00:48:45,740 --> 00:48:48,860 >> Nažalost, mislim da moje upute nisu bili, do danas, vrlo jasno, tako da 1116 00:48:48,860 --> 00:48:52,230 Vratio sam se ovaj vikend i ažurira spec. u većim, hrabriji teksta na 1117 00:48:52,230 --> 00:48:53,600 objasni metke poput ovih. 1118 00:48:53,600 --> 00:48:56,900 I samo da ga još što reći javno, prema Zadane, problem setovi su zbog četvrtak 1119 00:48:56,900 --> 00:48:58,400 u podne, po nastavnom planu. 1120 00:48:58,400 --> 00:49:02,030 Ako ste početi rano, završni dio Problem postavljena do srijede u 12:00 1121 00:49:02,030 --> 00:49:05,170 PM, dio koji se odnosi na kupon broj, ideja je da se može produljiti 1122 00:49:05,170 --> 00:49:07,710 Rok za vaš P postavljena sve do petka. 1123 00:49:07,710 --> 00:49:10,890 To je, odgrizao maleni dio P postavljena u odnosu na ono što je obično 1124 00:49:10,890 --> 00:49:13,200 Veći je problem, a ti kupi se dodatni dan. 1125 00:49:13,200 --> 00:49:15,190 Opet, to dobiva razmišljanja o Problem set, dobiva na vas 1126 00:49:15,190 --> 00:49:16,380 Radno vrijeme prije. 1127 00:49:16,380 --> 00:49:20,670 No, problem je još uvijek kupon potrebno, čak i ako ne pošaljete. 1128 00:49:20,670 --> 00:49:23,340 >> No, više je to uvjerljivo. 1129 00:49:23,340 --> 00:49:26,520 (STAGE WHISPER) I ti ljudi odlazi već ćeš se požaliti. 1130 00:49:26,520 --> 00:49:28,620 Kao što su ljudi na balkonu. 1131 00:49:28,620 --> 00:49:32,510 Unaprijed se ispričavam na narod na balkon iz razloga koji će biti 1132 00:49:32,510 --> 00:49:33,920 jasno je u samo trenutak. 1133 00:49:33,920 --> 00:49:37,050 >> Dakle, mi smo sretni da imaju jednu od CS50 je bivši šef nastavne novaci u 1134 00:49:37,050 --> 00:49:39,302 Tvrtka se zove dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 Oni su vrlo velikodušno donirao kupon ovdje za ovu puno prostora, 1136 00:49:45,500 --> 00:49:48,180 što je gore od Uobičajeni 2 gigabajta. 1137 00:49:48,180 --> 00:49:51,740 Dakle, ono što sam mislio da će to učiniti na ovom Konačna napomena je to malo podijela, 1138 00:49:51,740 --> 00:49:55,380 kojom se u samo trenutak, otkrit ćemo dobitnik, a tko ima kupon 1139 00:49:55,380 --> 00:49:57,980 kod koji onda možete ići na njihove Web stranica, upišite ga u, i voila, dobili 1140 00:49:57,980 --> 00:50:01,370 puno više prostora za svoje Dropbox aparata i za vaše osobne datoteke. 1141 00:50:01,370 --> 00:50:05,690 >> I prvi, koji su željeli sudjelovati na ovom crtežu? 1142 00:50:05,690 --> 00:50:09,630 OK, sad, što ga čini još više zabave. 1143 00:50:09,630 --> 00:50:14,010 Osoba koja prima te 25-gigabajt kupon kod - što je daleko 1144 00:50:14,010 --> 00:50:16,150 uvjerljiviji od kasne Sada dana, možda - 1145 00:50:16,150 --> 00:50:20,620 je onaj koji sjedi na vrhu sjedala, ispod kojeg se nalazi 1146 00:50:20,620 --> 00:50:21,620 da je kupon. 1147 00:50:21,620 --> 00:50:23,480 Sada možete pogledati ispod Vaš sjedala. 1148 00:50:23,480 --> 00:50:28,710 1149 00:50:28,710 --> 00:50:29,680 >> [Video reprodukciju] 1150 00:50:29,680 --> 00:50:31,620 >> -Jedan, dva, tri. 1151 00:50:31,620 --> 00:50:35,015 >> [SCREAMING] 1152 00:50:35,015 --> 00:50:35,985 >> -Dobivate auto! 1153 00:50:35,985 --> 00:50:36,670 Možete dobiti auto! 1154 00:50:36,670 --> 00:50:37,970 >> DAVID Malan: Vidjet ćemo što je u srijedu. 1155 00:50:37,970 --> 00:50:38,904 >> -Dobivate auto! 1156 00:50:38,904 --> 00:50:39,371 Možete dobiti auto! 1157 00:50:39,371 --> 00:50:40,305 Možete dobiti auto! 1158 00:50:40,305 --> 00:50:41,706 Možete dobiti auto! 1159 00:50:41,706 --> 00:50:43,107 Možete dobiti auto! 1160 00:50:43,107 --> 00:50:45,530 >> DAVID Malan: Balkon ljudi, dolaze ovdje dolje na prednji, 1161 00:50:45,530 --> 00:50:46,866 gdje smo dodataka. 1162 00:50:46,866 --> 00:50:50,282 >> -Svatko dobiva auto! 1163 00:50:50,282 --> 00:50:52,234 Svatko dobiva auto! 1164 00:50:52,234 --> 00:50:52,722 >> [END video reprodukciju] 1165 00:50:52,722 --> 00:50:54,590 >> Narator: Na sljedećem CS50 - 1166 00:50:54,590 --> 00:51:00,374 >> ZVUČNI 5: O, moj bože bože bože bože bože bože bože bože bože bože - 1167 00:51:00,374 --> 00:51:02,106 >> [UKELELE PLAYS]