1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> SPEAKER: Dobre, to je CS50. 3 00:00:14,910 --> 00:00:19,020 To je koniec troch týždňov, a ak ste využili už 4 00:00:19,020 --> 00:00:21,790 vedieť, že tam bude obed tento piatok ako obvykle, kde 5 00:00:21,790 --> 00:00:25,430 môžete teraz dobrý rozhovor a jedlo na ohňa a ľadu 6 00:00:25,430 --> 00:00:27,980 s niektorými CS50 je Zamestnanci a spolužiaci. 7 00:00:27,980 --> 00:00:30,170 Vydajte sa na tejto adrese tu. 8 00:00:30,170 --> 00:00:33,420 >> Teraz si môžete pripomenúť, alebo môže čoskoro byť oboznámený s, 9 00:00:33,420 --> 00:00:35,970 tieto veci, ktorá sem sú uvedené na konci 10 00:00:35,970 --> 00:00:37,850 semestra pre mnoho tried. 11 00:00:37,850 --> 00:00:40,870 Takzvaná skúška modrej knihy, v ktorej môžete písať svoje odpovede na skúšky. 12 00:00:40,870 --> 00:00:44,240 Teraz mám tú 26 ako modrej knihy, na každý z nich 13 00:00:44,240 --> 00:00:47,580 je napísané meno, až Z. A naozaj mená sú tak jednoduché, 14 00:00:47,580 --> 00:00:50,490 vďaka Z. A jeden z ciele na dosah ruky dnes 15 00:00:50,490 --> 00:00:53,910 bude pokračovať v čo sme začali v pondelok, čo nie je 16 00:00:53,910 --> 00:00:57,830 tak pri pohľade na kód, ale v skutočnosti pri pohľade na nápady a riešenia problémov. 17 00:00:57,830 --> 00:01:00,170 Jedným z cieľov a sľuby tohto kurzu 18 00:01:00,170 --> 00:01:02,985 je, aby vás naučí myslieť viac opatrne, viac metodicky, 19 00:01:02,985 --> 00:01:05,400 a efektívnejšie riešiť problémy. 20 00:01:05,400 --> 00:01:09,526 A skutočne, môžeme to urobiť naozaj bez toho aby ste sa dotkli jediného riadku kódu. 21 00:01:09,526 --> 00:01:12,150 Takže mám pár slonov tu dnes, oranžovej a modrej, 22 00:01:12,150 --> 00:01:15,780 ak by sme sa mohli dostať jedného dobrovoľníka, možno z väčšej späť, než je obvyklé. 23 00:01:15,780 --> 00:01:18,070 Ako sa asi tu, poď dole. 24 00:01:18,070 --> 00:01:24,180 Ktorého cieľom bude, aby pomôcť a navyše spravovať túto skúšku tu. 25 00:01:24,180 --> 00:01:24,935 Ako sa voláte? 26 00:01:24,935 --> 00:01:25,768 >> Divákov: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 SPEAKER: Mary Beth, poď hore. 28 00:01:27,560 --> 00:01:29,560 Dovoľte mi, aby som sa mikrofón tu pre vás. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Teší ma. 31 00:01:32,880 --> 00:01:34,005 >> Divákov: Teší ma. 32 00:01:34,005 --> 00:01:36,790 SPEAKER: Dobre, takže mám tu modrej knihy A až Z, 33 00:01:36,790 --> 00:01:41,680 a budem predstierať, že Mám jeden zo študentov, 34 00:01:41,680 --> 00:01:45,770 a oni prichádzajú trochu náhodne na konci tri hodiny skúška bloku, 35 00:01:45,770 --> 00:01:49,400 tak oni skončia v niektorej semi-náhodné poradie takhle. 36 00:01:49,400 --> 00:01:54,510 Teraz svoju prácu za chvíľu bude na bylo-- to je vlastne, ako sa dostať 37 00:01:54,510 --> 00:01:56,820 obrátil na konci roka triedy, s najväčšou pravdepodobnosťou. 38 00:01:56,820 --> 00:02:01,120 Vašou úlohou teraz bude úplne Jednoducho povedané, triediť tieto modrej knihy pre nás 39 00:02:01,120 --> 00:02:05,220 od A po Z. 40 00:02:05,220 --> 00:02:08,400 >> DIVÁKOV: Oh, to je bude trvať večne. 41 00:02:08,400 --> 00:02:13,747 >> SPEAKER: A budeme sledovať ako to urobíte, žiadny tlak. 42 00:02:13,747 --> 00:02:15,330 DIVÁKOV: Nie, žiadny tlak alebo tak niečo. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> SPEAKER: A pre zábavu, poďme dať časovač. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> Divákov: Toľko zábavy, toľko zábavy. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> SPEAKER: Môžem držať mikrofón pre vás. 49 00:02:38,574 --> 00:02:40,240 Dobre, práve sme zdvojnásobili našu rýchlosť. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Takže do tej doby, dovoľte mi, aby som predstavovať, čo je bude otázka pre Mary Beth 52 00:02:49,060 --> 00:02:51,540 je to, čo robí, ako je že ide o riešenie tohto? 53 00:02:51,540 --> 00:02:54,040 A v skutočnosti, možno nebudete mať niekedy premýšľali o niečom 54 00:02:54,040 --> 00:02:57,440 tak jednoduché, ako keď si vyberiete až 26 kníh, ako je tento, 55 00:02:57,440 --> 00:02:59,350 ktoré majú prírodný objednanie k nim. 56 00:02:59,350 --> 00:03:01,335 Aký je proces že ste skutočne používať? 57 00:03:01,335 --> 00:03:03,770 Je to celkom náhodne len vyberanie prvý uvidíte 58 00:03:03,770 --> 00:03:05,250 a uvedenie na svojom mieste? 59 00:03:05,250 --> 00:03:09,680 Myslíte si najprv presunúť svoje ruky okolo Hľadáme potom hľadal B? 60 00:03:09,680 --> 00:03:11,722 Myslíte si, pozrite sa na pár z nich vedľa seba 61 00:03:11,722 --> 00:03:14,680 a len povedal, počkaj, to nie je v poriadku, a potom vymeniť poradie? 62 00:03:14,680 --> 00:03:16,960 Už sme videli v pondelok že existuje viacero spôsobov, ako 63 00:03:16,960 --> 00:03:22,140 v ktorom môžeme urobiť, a naozaj, ako sme u konca tu, 64 00:03:22,140 --> 00:03:26,360 Chcel by som vziať na vedomie možná z čoho Mary Beth robí. 65 00:03:26,360 --> 00:03:30,040 Máme niekoľko kôpok zdá sa, Väčšia z nich, tri menšie. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> Divákov: Ja je objednanie keď som si dva listy 68 00:03:36,415 --> 00:03:39,540 že viem, že sú spolu v poradí, Dal som ich dohromady tak, že sa mi nepáči 69 00:03:39,540 --> 00:03:42,915 musieť starať o udržanie track z celej rady kníh. 70 00:03:42,915 --> 00:03:45,706 Je to len, ach, je prvý, Mám tento stoh tu. 71 00:03:45,706 --> 00:03:47,580 SPEAKER: Takže, skoro ako puzzle kúsky, ktoré 72 00:03:47,580 --> 00:03:49,860 mať správny tvar na zhodovať s navzájom. 73 00:03:49,860 --> 00:03:51,026 DIVÁKOV: Docela veľa, jo. 74 00:03:51,026 --> 00:03:55,320 SPEAKER: OK, výborná. 75 00:03:55,320 --> 00:03:59,850 A teraz každá z nich zhromaždenia je pravdepodobne radené? 76 00:03:59,850 --> 00:04:00,990 >> Hľadisko: Áno. 77 00:04:00,990 --> 00:04:09,900 >> SPEAKER: Dobre, vďaka Z. Všetko Dobre, gratulujem, ste to urobil. 78 00:04:09,900 --> 00:04:11,461 Máte možnosť voľby. 79 00:04:11,461 --> 00:04:11,960 Modrá? 80 00:04:11,960 --> 00:04:13,530 Dobre, ďakujem vám za to. 81 00:04:13,530 --> 00:04:16,679 Takže Mary Beth sa navrhnúť čo jej prístup bol, 82 00:04:16,679 --> 00:04:19,720 ale to, čo je iný prístup, ako na Vás môže ísť o triedení týchto vecí? 83 00:04:19,720 --> 00:04:21,130 Čo by ste urobili? 84 00:04:21,130 --> 00:04:24,060 Záznam poraziť by bolo jednu minútu a 50 sekúnd, alebo tak, 85 00:04:24,060 --> 00:04:26,039 plus tie, ktoré som zabudol počítať. 86 00:04:26,039 --> 00:04:27,080 Čo by ste urobili? 87 00:04:27,080 --> 00:04:27,579 Jo? 88 00:04:27,579 --> 00:04:28,735 Divákov: Vezmite stoh papierov. 89 00:04:28,735 --> 00:04:29,776 Od začiatku. 90 00:04:29,776 --> 00:04:32,284 Skontrolujte, či vaše dokumenty. 91 00:04:32,284 --> 00:04:36,586 A v prípade, že horný z nich je vyššia ako, možno, že sú 92 00:04:36,586 --> 00:04:38,980 spodný z nich je vyššia, potom nimi prepínať. 93 00:04:38,980 --> 00:04:41,300 >> SPEAKER: OK, tak začína V hornej a spodnej časti, 94 00:04:41,300 --> 00:04:43,716 a pracovnú cestu dovnútra ako to, že ich vymení? 95 00:04:43,716 --> 00:04:46,580 OK, tak málo podobný duchom bublinkové druhu, 96 00:04:46,580 --> 00:04:49,160 ale voľba extrémy nie sú priľahlé pary. 97 00:04:49,160 --> 00:04:52,080 Ale krátke na to, že je tu určite veľa rôznych spôsobov, 98 00:04:52,080 --> 00:04:54,210 by sme to mohli urobiť, a Úprimne povedané, myslím, že tak nejako 99 00:04:54,210 --> 00:04:55,700 prijal pár prístupy, nie? 100 00:04:55,700 --> 00:05:00,567 Urobil si niečo ako štyri triedených pilotov a potom efektívne spojil dohromady. 101 00:05:00,567 --> 00:05:02,650 A to je, trúfam povedať, ďalšie technika dohromady. 102 00:05:02,650 --> 00:05:06,950 Vy ste to brať to ako jedna veľká hromada, môžete rozdeliť problém do štyroch štvorkolky, 103 00:05:06,950 --> 00:05:09,820 ak chcete, a potom sa nejakým spôsobom spojil ich do konca. 104 00:05:09,820 --> 00:05:13,410 >> Takže poďme zvážiť, nakoniec, Ako inak by sme mohli urobiť. 105 00:05:13,410 --> 00:05:15,860 Formalizované sme pojem bublinkové triedenie minule, 106 00:05:15,860 --> 00:05:18,780 a bubble sort odvolanie bolo Algoritmus, ktorý sme vizualizované 107 00:05:18,780 --> 00:05:22,640 s ôsmimi svojimi spolužiakmi sa tu, zdanlivo náhodne radené na prvom mieste. 108 00:05:22,640 --> 00:05:26,110 A potom sme sa rozhodli po dvoch, ak dva prvky sú mimo prevádzky, 109 00:05:26,110 --> 00:05:26,950 jednoducho ich vymeniť. 110 00:05:26,950 --> 00:05:28,930 Takže štyri a dve zrejme mimo prevádzku, 111 00:05:28,930 --> 00:05:31,080 Takže tí dvaja spolužiaci prepnúť pozície. 112 00:05:31,080 --> 00:05:35,390 A potom sme sa opakuje so štyrmi a šiestimi, potom šesť a osem, na každej iterácii, 113 00:05:35,390 --> 00:05:36,980 pohybujúce sa doprava. 114 00:05:36,980 --> 00:05:42,590 >> Takže vzhľadom k tomu osem ľudí, koľko pairwise porovnanie som urobil pri chôdzi od 115 00:05:42,590 --> 00:05:45,220 zľava doprava v jednom takom iterácii? 116 00:05:45,220 --> 00:05:48,410 Koľko porovnanie? 117 00:05:48,410 --> 00:05:49,197 Sedem, že jo? 118 00:05:49,197 --> 00:05:51,405 Vzhľadom k tomu, či je osem ľudia, ale máte pár 119 00:05:51,405 --> 00:05:53,880 ne a ďalej jeden hop na pravej strane, 120 00:05:53,880 --> 00:05:56,060 nebudeš mať osem porovnanie, pretože nemôžete porovnať 121 00:05:56,060 --> 00:05:59,226 prvok proti sebe, alebo by len zbytočné, takže budete mať sedem. 122 00:05:59,226 --> 00:06:01,290 Alebo všeobecnejšie, ak máme n ľudí, sme 123 00:06:01,290 --> 00:06:04,300 do n mínus 1 porovnaniu bublinkové druhu. 124 00:06:04,300 --> 00:06:08,150 >> Takže uvažujme teraz, ako dobrý alebo zlý bubble sort vlastne bol, a skúste 125 00:06:08,150 --> 00:06:13,570 aby sami slovnú zásobu ktoré k posudku algoritmov, ako je tento, 126 00:06:13,570 --> 00:06:14,430 a čoskoro sa naše vlastné. 127 00:06:14,430 --> 00:06:16,970 Takže prvom prechode bublina druh, prvýkrát 128 00:06:16,970 --> 00:06:20,909 Išiel som zľava doprava cez etapa, vzal ma n mínus 1 porovnanie. 129 00:06:20,909 --> 00:06:22,950 A to bude môj merná jednotka, nie? 130 00:06:22,950 --> 00:06:26,170 Bol som trochu hovoriť a prechádzky, trochu rýchlo, trochu pomalý, 131 00:06:26,170 --> 00:06:29,300 takže počítanie moje číslo v sekundách nie je osobitne hovorí, 132 00:06:29,300 --> 00:06:32,260 ale spočítaním operácie, ktoré som robil v pondelok, 133 00:06:32,260 --> 00:06:35,900 porovnanie dvoch ľudí, že sa cíti ako pekný mernú jednotku. 134 00:06:35,900 --> 00:06:40,980 >> Tak n mínus 1 krok prvýkrát, ale potom, čo sa stalo potom? 135 00:06:40,980 --> 00:06:46,610 Čo je to jeden nahor na jeden priechod cez inak netriedeného zoznamu? 136 00:06:46,610 --> 00:06:49,840 Čo mi môžete povedať o prvok ktorý bol po celú cestu tam? 137 00:06:49,840 --> 00:06:51,300 Jo? 138 00:06:51,300 --> 00:06:52,870 To bol najväčší prvok, nie? 139 00:06:52,870 --> 00:06:55,710 Číslo osem, aj keď tu začala, zakaždým, keď som 140 00:06:55,710 --> 00:06:57,860 v porovnaní s ňou proti sused, stále 141 00:06:57,860 --> 00:07:00,480 vyviera na pravej strane strane zoznamu. 142 00:07:00,480 --> 00:07:02,710 A vskutku, to je miesto, kde algoritmus dostane jeho meno. 143 00:07:02,710 --> 00:07:07,630 >> Práve týmto logiky, koľko porovnanie Potrebujem, aby na druhýkrát 144 00:07:07,630 --> 00:07:09,800 Robím, že prihrávku zľava doprava? 145 00:07:09,800 --> 00:07:10,730 n mínus 2, nie? 146 00:07:10,730 --> 00:07:14,297 Bolo by to plytvanie mojím časom, keby som udržať nákupný osem proti niekomu, 147 00:07:14,297 --> 00:07:16,630 iného, ​​pretože už vieme, bola na správnom mieste. 148 00:07:16,630 --> 00:07:19,760 Takže je to trochu optimalizácia, takže ďalší priechod 149 00:07:19,760 --> 00:07:23,899 bude navyše n mínus dva kroky, kde n je počet osôb. 150 00:07:23,899 --> 00:07:26,940 Teraz môžete trochu extrapolovať, a to aj ak nie ste počítačový odborník, 151 00:07:26,940 --> 00:07:27,680 ako to skončí. 152 00:07:27,680 --> 00:07:31,259 Na konci tohto algoritmu, pravdepodobne máte len jeden porovnanie odišiel. 153 00:07:31,259 --> 00:07:33,800 Musíte sa trochu opraviť začiatku zoznamu v prípade, že dvaja 154 00:07:33,800 --> 00:07:36,540 a jedna sú mimo poradia a mala by byť jedna a dve, 155 00:07:36,540 --> 00:07:40,330 tak to doraz na plus 1 v konečnom znení porovnanie. 156 00:07:40,330 --> 00:07:44,500 >> Teraz je bodka, bodka, bodka druh vĺn je ruky na niektoré šťavnatejšie podrobnosti 157 00:07:44,500 --> 00:07:46,452 ale poďme jednoducho ísť dopredu a zjednodušiť. 158 00:07:46,452 --> 00:07:48,660 Ak si spomínate z vysoko Škola, úprimne povedané, veľa z vás 159 00:07:48,660 --> 00:07:50,340 mali matematické knihy, ktoré mali malý ťahák 160 00:07:50,340 --> 00:07:52,550 na prednej strane obálky alebo zadný kryt, ktorý vám ukázal, 161 00:07:52,550 --> 00:07:56,400 čo séria súčtov ako to nakoniec pridal až. 162 00:07:56,400 --> 00:07:59,600 Vo všeobecnom prípade, ak máte variabilné, ako n, a v skutočnosti to jeden, 163 00:07:59,600 --> 00:08:01,634 ak ste sa pozreli na vaše old school math knihy, 164 00:08:01,634 --> 00:08:04,050 by ste vidieť, že to v skutočnosti pridáva do tejto sumy tu 165 00:08:04,050 --> 00:08:07,970 n krát n mínus 1 všetko deleno 2. 166 00:08:07,970 --> 00:08:11,172 Takže teraz mi dovoľte stanovuje je to pravda, tak na skok viery, 167 00:08:11,172 --> 00:08:12,880 to je to, čo to vystihuje až, a my sme mohli 168 00:08:12,880 --> 00:08:14,341 dokázať, že vo všeobecnejšom prípade. 169 00:08:14,341 --> 00:08:15,590 Ale teraz poďme rozšíriť to. 170 00:08:15,590 --> 00:08:19,920 Takže poďme sa množia na to, aby ich n na druhú, mínus n, všetko deleno 2. 171 00:08:19,920 --> 00:08:23,200 To je naozaj n na druhú, deleno 2, mínus n na 2, 172 00:08:23,200 --> 00:08:25,010 tak to je všetko pekné a zaujímavé. 173 00:08:25,010 --> 00:08:27,060 Ale čo sa stane, keď Teraz plug-in v hodnote? 174 00:08:27,060 --> 00:08:29,724 Dajme tomu, že som nemal osem ľudia, ale hovoria milióna. 175 00:08:29,724 --> 00:08:31,890 A milióny len preto, že to je celkom veľké číslo, 176 00:08:31,890 --> 00:08:34,039 poďme zástrčka, že v roku, a uvidíme, čo sa stane. 177 00:08:34,039 --> 00:08:39,039 Takže keď som plug miliónov do tohto vzorca Idem si milión na druhú, 178 00:08:39,039 --> 00:08:42,868 deleno 2, mínus miliónov, deleno 2. 179 00:08:42,868 --> 00:08:44,159 A teraz, čo to ide, aby sa rovnala? 180 00:08:44,159 --> 00:08:47,354 Takže 500 miliárd, mínus 500.000. 181 00:08:47,354 --> 00:08:49,270 A keď som vlastne robiť že matematika, znamená to, 182 00:08:49,270 --> 00:08:53,920 že triedenie milión ľudia s bubliny druhu 183 00:08:53,920 --> 00:09:01,800 mi môže trvať 499999500000 kroky alebo porovnanie na konci, 184 00:09:01,800 --> 00:09:02,900 sme len extrapolácie. 185 00:09:02,900 --> 00:09:06,860 >> Že sa cíti celkom pomaly, ale úprimne povedané, meranie jednej konkrétnej vstup 186 00:09:06,860 --> 00:09:09,160 ako je toto, nie je všetko, že to povedal. 187 00:09:09,160 --> 00:09:14,050 Ale v skutočnosti to naznačuje, že pre n dostane väčšie a väčšie, tento algoritmus 188 00:09:14,050 --> 00:09:16,280 druh cíti horšie a horší, alebo naozaj 189 00:09:16,280 --> 00:09:20,450 začnete cítiť bolesť, ktorá umocňovanie, že n na druhú, 190 00:09:20,450 --> 00:09:21,770 ktorý sčíta docela rýchlo. 191 00:09:21,770 --> 00:09:25,340 A to detail nie je stratil na ľudí, v skutočnosti 192 00:09:25,340 --> 00:09:29,640 pred niekoľkými rokmi istý senátor, ktorý bol kampane, sadol si na pohovor 193 00:09:29,640 --> 00:09:32,180 s Google Eric Schmidt, CEO v tej dobe, 194 00:09:32,180 --> 00:09:36,380 a bol napádaný s otázkou rovnako ako sme skúmanie dnes. 195 00:09:36,380 --> 00:09:38,468 Poďme sa pozrieť. 196 00:09:38,468 --> 00:09:45,280 >> [PREHRÁVANIE] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Že si tu na Google, a páči sa mi 198 00:09:48,560 --> 00:09:53,382 myslieť na predsedníctvo ako pracovný pohovor. 199 00:09:53,382 --> 00:09:56,434 Teraz je ťažké sa dostať zamestnania ako prezident, 200 00:09:56,434 --> 00:09:58,100 a idete cez nástrahami teraz. 201 00:09:58,100 --> 00:10:01,860 Je to tiež ťažké získať prácu v spoločnosti Google. 202 00:10:01,860 --> 00:10:05,490 Máme otázky, a my opýtajte Naši kandidáti otázky, 203 00:10:05,490 --> 00:10:09,770 a toto je od Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 Co-- vy myslíte, že som Robíš si srandu, že je to tu. 205 00:10:14,760 --> 00:10:17,930 Aký je najúčinnejší spôsob, ako zoradiť milión 32bitová celé čísla? 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 >> -Prepáčte, Maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Nie, nie, nie. 210 00:10:27,400 --> 00:10:30,700 Myslím si, že bublina druh by bol zlý spôsob, ako ísť. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> No tak, kto mu to povedal? 213 00:10:38,180 --> 00:10:40,590 Nevidel som počítač veda v pozadí. 214 00:10:40,590 --> 00:10:42,130 >> -Musíme Naša zvedov tam. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Poďme sa opýtať iný rozhovor otázka. 217 00:10:48,444 --> 00:10:49,300 >> [END Videoprehrávanie] 218 00:10:49,300 --> 00:10:52,290 >> SPEAKER: Tak hovorí o Konkrétne čísla však 219 00:10:52,290 --> 00:10:53,890 sa nebude všetko užitočné. 220 00:10:53,890 --> 00:10:56,810 Nejedná sa o životnú lekciu, že bublina triedenie, vzhľadom k tomu milión vstupov, 221 00:10:56,810 --> 00:10:58,590 môže trvať toľko ako 500 miliárd kroky. 222 00:10:58,590 --> 00:11:01,120 Nemôžete naozaj zovšeobecniť príliš účinne od 223 00:11:01,120 --> 00:11:03,560 a robiť správne rozhodnutia návrhu pri písaní programov. 224 00:11:03,560 --> 00:11:07,070 Takže poďme sa zamerať na to, ako by môžeme zjednodušiť tento výsledok. 225 00:11:07,070 --> 00:11:11,780 >> Tak som sa zvýrazní žlto tu výsledkom n na druhú deleno 2, 226 00:11:11,780 --> 00:11:14,330 tak milión na druhú delené 2, a potom 227 00:11:14,330 --> 00:11:16,710 Som zvýrazní to, čo konečná odpoveď bola 228 00:11:16,710 --> 00:11:20,180 akonáhle sme sa odpočíta z n deleno 2. 229 00:11:20,180 --> 00:11:24,850 A tvrdenie, budem teraz robiť, je kto sakra zaujíma, či si odpočítať z 230 00:11:24,850 --> 00:11:30,060 trochu starý n na 2, keď prvý Súčasťou tohto vzorca je tak oveľa väčší? 231 00:11:30,060 --> 00:11:33,910 Je dominantou druhej Termín, n na druhú deleno 2 232 00:11:33,910 --> 00:11:37,510 je tak oveľa väčší, jasne, ako n dostane veľký ako milión, 233 00:11:37,510 --> 00:11:41,450 to je naozaj veľký rozdiel v koniec dňa medzi 500000000000 234 00:11:41,450 --> 00:11:45,730 a 499999500000? 235 00:11:45,730 --> 00:11:46,349 Nie tak celkom. 236 00:11:46,349 --> 00:11:48,640 A tak to, čo budeme robiť, čo počítačoví odborníci sa 237 00:11:48,640 --> 00:11:53,270 ignorovať tie nižšieho rádu podmienky a sa niečo také a naozaj 238 00:11:53,270 --> 00:11:56,050 len zjednodušiť na termín, ktorý to bude jedno. 239 00:11:56,050 --> 00:12:00,315 Väčšia naše súbory dát, tým väčšia Naša databáza získať, tým viac webových stránok 240 00:12:00,315 --> 00:12:02,690 musíme hľadať, viac priatelia máte na Facebooku. 241 00:12:02,690 --> 00:12:07,340 >> Ako n zväčšuje, sme naozaj bude sa starať o najväčší 242 00:12:07,340 --> 00:12:11,560 Výraz v každej takejto analýze naše algoritmy výkon. 243 00:12:11,560 --> 00:12:16,230 A ja som chcel povedať, že vieš, čo, bubble sort je na objednávku veľký O, 244 00:12:16,230 --> 00:12:18,060 na poradí n na druhú. 245 00:12:18,060 --> 00:12:20,090 Nie je to zrovna n na druhú, ako sme videli, 246 00:12:20,090 --> 00:12:22,060 ale kto naozaj zaujíma o tých menších podmienkach, 247 00:12:22,060 --> 00:12:24,390 a úprimne povedané, kto naozaj zaujíma, či budeme deliť dve? 248 00:12:24,390 --> 00:12:25,870 To je len konštantný faktor. 249 00:12:25,870 --> 00:12:29,480 A 500 miliárd, v porovnaní s 250 miliárd naozaj tak veľký problém? 250 00:12:29,480 --> 00:12:32,190 Som mohol len čakať jeden rok, nechať notebook doslova 251 00:12:32,190 --> 00:12:34,810 sa dvakrát tak rýchlo v hardvéri, a že tak nejako rozdiel 252 00:12:34,810 --> 00:12:36,650 proste zmizne prirodzene v priebehu času. 253 00:12:36,650 --> 00:12:39,300 >> To, čo zaujíma je výraz, časť 254 00:12:39,300 --> 00:12:42,489 výrazu, že sa to líši ako náš vstup dostane väčšie a väčšie. 255 00:12:42,489 --> 00:12:45,280 A skutočne, v reálnom svete, to je to, čo sa deje ďalej 256 00:12:45,280 --> 00:12:48,330 Je vstupy do našich problémov a algoritmy sú stále väčšie. 257 00:12:48,330 --> 00:12:53,470 Tak veľký O bude zápis, asymptotickej notácie, ktorý sme práve 258 00:12:53,470 --> 00:12:57,160 použiť ako počítačoví experti popísať výkon, alebo čas beží, 259 00:12:57,160 --> 00:12:58,130 algoritmu. 260 00:12:58,130 --> 00:13:00,800 Takže môžeme porovnávať algoritmy na rôznych počítačoch písomných 261 00:13:00,800 --> 00:13:04,170 rôznymi ľuďmi, s použitím niektoré zásadne podobné metriky 262 00:13:04,170 --> 00:13:07,557 ako je počet porovnaní ste robiť, alebo možno počet swapov 263 00:13:07,557 --> 00:13:08,140 robíte. 264 00:13:08,140 --> 00:13:11,910 >> Čo my nebudeme počet je množstvo času, 265 00:13:11,910 --> 00:13:13,981 , Ktorý prechádza na hodiny na stene typicky. 266 00:13:13,981 --> 00:13:16,230 Čo my nebudeme sa báť o tom, je, koľko pamäte 267 00:13:16,230 --> 00:13:17,820 používate dnes na najmenej, aj keď je to 268 00:13:17,820 --> 00:13:19,370 iný zdroj môžeme merať. 269 00:13:19,370 --> 00:13:23,610 Budeme sa snažiť založiť svoje analýzy na len základné operácie, tie, 270 00:13:23,610 --> 00:13:25,930 úprimne, že môžete vidieť najviac vizuálne. 271 00:13:25,930 --> 00:13:30,700 Takže niečo ako veľký O n štvorcový, tvrdím, že O n na druhú 272 00:13:30,700 --> 00:13:35,820 je horná hranica na takzvaný doba chodu bublín druhu. 273 00:13:35,820 --> 00:13:38,820 Inými slovami, ak máte chcel tvrdiť, že je tu 274 00:13:38,820 --> 00:13:41,370 Tento horný limit na tom, koľko kroky algoritmus môže trvať, 275 00:13:41,370 --> 00:13:46,240 že to bude vo veľkom O n v tomto prípade štvorcový, horná hranica. 276 00:13:46,240 --> 00:13:49,710 >> Čo keby som namiesto toho zmeniť príbeh sa nejedná o bubble sort, 277 00:13:49,710 --> 00:13:50,910 ale o to hornú hranicu. 278 00:13:50,910 --> 00:13:54,030 Spomeniete si na algoritme že sme sa pozrel na už 279 00:13:54,030 --> 00:13:59,530 ktorého horná hranica, maximálny meranie času alebo prevádzky, 280 00:13:59,530 --> 00:14:04,300 by sa povedať, že je ohraničená o n, lineárne funkcie, 281 00:14:04,300 --> 00:14:07,260 nie je kvadratická ten, ktorý je zakrivený? 282 00:14:07,260 --> 00:14:10,780 Čo je to algoritmus, ktorý vždy netrvá dlhšie 283 00:14:10,780 --> 00:14:12,860 než ako n krokov, alebo 2n krokov, alebo 3n kroky? 284 00:14:12,860 --> 00:14:13,360 Jo? 285 00:14:13,360 --> 00:14:15,030 >> Divákov: Hľadanie najväčšie číslo v zozname? 286 00:14:15,030 --> 00:14:16,930 >> SPEAKER: Perfektné, hľadanie najväčšie číslo v zozname. 287 00:14:16,930 --> 00:14:18,940 Ak som dal zoznam ľudia napríklad, 288 00:14:18,940 --> 00:14:21,440 Každý, kto ich drží číslo, aký je maximálny počet 289 00:14:21,440 --> 00:14:23,770 krokov, to by ma vziať, primerane inteligentný človek, 290 00:14:23,770 --> 00:14:27,530 nájsť najväčšie osoby v tomto zozname? 291 00:14:27,530 --> 00:14:28,100 n, že jo? 292 00:14:28,100 --> 00:14:31,320 Vzhľadom k tomu, v najhoršom prípade, kedy je možné, že najväčšia hodnota byť? 293 00:14:31,320 --> 00:14:32,700 Jasné, úplne na konci. 294 00:14:32,700 --> 00:14:34,575 Takže v najhoršom prípade horná hranica, možno som 295 00:14:34,575 --> 00:14:36,450 musieť ísť celú cestu tu a byť rád, 296 00:14:36,450 --> 00:14:39,170 oh, tu je číslo osem, alebo čo, že hodnota je. 297 00:14:39,170 --> 00:14:41,330 Teraz to bude len hlúpy keď som išiel ďalej, že jo? 298 00:14:41,330 --> 00:14:43,840 Hľadáte viac a viac prvkov v prípade, že posledný z nich je tam? 299 00:14:43,840 --> 00:14:45,340 Tak isto, n je horná hranica. 300 00:14:45,340 --> 00:14:47,420 Nepotrebujem, aby sa viac krokov, ako je. 301 00:14:47,420 --> 00:14:51,580 >> Čo keď namiesto toho navrhuje, aby sú algoritmy v tomto svete, 302 00:14:51,580 --> 00:14:57,750 majú prevádzkovú dobu, ktorá je ohraničené veľkým O log n log n? 303 00:14:57,750 --> 00:15:00,390 Tam, kde sme videli skôr? 304 00:15:00,390 --> 00:15:00,890 Jo? 305 00:15:00,890 --> 00:15:03,309 >> Divákov: V telefónnom zozname problém? 306 00:15:03,309 --> 00:15:04,850 SPEAKER: Ako telefónneho zoznamu problém. 307 00:15:04,850 --> 00:15:07,754 Čo bolo meradlom toho, ako veľa času a koľko ju strhne 308 00:15:07,754 --> 00:15:10,170 trvalo mi nájsť niekoho, ako je Mike Smith v telefónnom zozname? 309 00:15:10,170 --> 00:15:13,212 Vyhlasoval sme, že log n, a aj keď nepoznajú, alebo je to 310 00:15:13,212 --> 00:15:15,170 trochu zahmlený, čo logaritmus alebo exponent bol, 311 00:15:15,170 --> 00:15:17,650 Len nezabudnite, že log n všeobecne sa odkazuje na proces, 312 00:15:17,650 --> 00:15:20,790 v tomto prípade delenia niečo v polovici znova a znova, 313 00:15:20,790 --> 00:15:25,790 a znova, a znova, tak, že dostane stále malý, ako to urobiť. 314 00:15:25,790 --> 00:15:28,470 >> Takže log n označuje, iste, do telefónneho zoznamu napríklad 315 00:15:28,470 --> 00:15:32,662 binárne vyhľadávanie v teórii, keď sme mal virtuálne dvere na palube, 316 00:15:32,662 --> 00:15:34,370 alebo keď bol Sean niečo hľadal. 317 00:15:34,370 --> 00:15:37,374 Keby bol použitý binárne vyhľadávanie, binárny log n bude horná hranica na tom, koľko 318 00:15:37,374 --> 00:15:38,040 čas, ktorý trvá. 319 00:15:38,040 --> 00:15:44,027 Ale tie algoritmy, ktoré bežali v log n predpokladá, aké kľúčové detail? 320 00:15:44,027 --> 00:15:45,360 Že zoznam bol triedený, že jo? 321 00:15:45,360 --> 00:15:47,789 Algoritmus ak je zle Váš vstup netriedi, 322 00:15:47,789 --> 00:15:49,830 a napriek tomu, že používate niečo ako binárne vyhľadávanie 323 00:15:49,830 --> 00:15:51,704 pretože by ste mohli skočiť priamo cez prvku 324 00:15:51,704 --> 00:15:53,600 bez toho aby si uvedomil, že je to naozaj tam. 325 00:15:53,600 --> 00:15:55,600 >> A teraz, čo by to mohlo znamenať, veľký O jedného? 326 00:15:55,600 --> 00:15:59,117 To neznamená, že algoritmu trvá jeden a len jeden krok, 327 00:15:59,117 --> 00:16:01,200 to jednoducho znamená, že to trvá konštantný počet krokov. 328 00:16:01,200 --> 00:16:04,060 Možno je to jeden, možno je to 10, možno je to 1000, 329 00:16:04,060 --> 00:16:07,750 ale je to nezávislý Veľkosť problému. 330 00:16:07,750 --> 00:16:10,850 Bez ohľadu na to, aký veľký je n, časová konštanta algoritmus 331 00:16:10,850 --> 00:16:12,747 má vždy rovnaký počet krokov. 332 00:16:12,747 --> 00:16:15,080 Takže to, čo by mohlo byť algoritmus sme hovorili o, alebo len 333 00:16:15,080 --> 00:16:20,418 intuitívne, že k vám príde, že vždy beží v takzvanej konštantnom čase? 334 00:16:20,418 --> 00:16:20,918 Jo? 335 00:16:20,918 --> 00:16:22,001 >> Divákov: Pridajte dve čísla. 336 00:16:22,001 --> 00:16:25,320 SPEAKER: Pridajte dve čísla, 2 plus 2 sa rovná 4, hotovo. 337 00:16:25,320 --> 00:16:27,227 Tak to by mohlo fungovať, čo iné? 338 00:16:27,227 --> 00:16:28,560 Ako sa o viac skutočnom svete, nie? 339 00:16:28,560 --> 00:16:30,686 >> Divákov: Hľadanie Prvá vec, ktorú v zozname. 340 00:16:30,686 --> 00:16:32,810 SPEAKER: Nájdenie prvý prvok v zozname, iste. 341 00:16:32,810 --> 00:16:34,540 Sme vlastne hovorili o poliach už 342 00:16:34,540 --> 00:16:36,540 ako sa dostať na prvý prvok v matici, 343 00:16:36,540 --> 00:16:40,465 bez ohľadu na to, ako dlho pole je v C kóde? 344 00:16:40,465 --> 00:16:43,090 Stačí použiť ako držiak bum, ste tam nula notácie, ty. 345 00:16:43,090 --> 00:16:46,120 A samozrejme poľa, ako stranou, Podpora niečo všeobecne známe, 346 00:16:46,120 --> 00:16:49,240 ako náhodný prístup, s priamym prístupom pamäť, pretože môžete doslova 347 00:16:49,240 --> 00:16:50,284 preskočiť na jednom mieste. 348 00:16:50,284 --> 00:16:52,700 Môžeme to urobiť ešte jednoduchšie môžeme pretočiť na týždeň nulovej 349 00:16:52,700 --> 00:16:53,900 keď sme nuly. 350 00:16:53,900 --> 00:16:59,707 Koľko času to trvať povedať, blok Scratch vykonať? 351 00:16:59,707 --> 00:17:00,790 Len konštantný čas, že jo? 352 00:17:00,790 --> 00:17:03,960 Povedz niečo, povedz niečo, nezáleží na tom, 353 00:17:03,960 --> 00:17:07,359 ako veľké škrabance svet, je to vždy bude trvať rovnakú dobu 354 00:17:07,359 --> 00:17:08,490 proste niečo povedať. 355 00:17:08,490 --> 00:17:11,089 >> Tak to je časová konštanta, ale čo druhá strana? 356 00:17:11,089 --> 00:17:13,030 Keby tomu tak bolo vyššie hranice, čo chceme 357 00:17:13,030 --> 00:17:17,089 popísať dolnej medze z našich algoritmov beží čas? 358 00:17:17,089 --> 00:17:19,852 Takmer v najlepšom prípade potenciálne, ak chcete, 359 00:17:19,852 --> 00:17:23,060 keď tieto podmienky by sa mohli vzťahovať k najlepším puzdrá, najhoršie prípady, priemer púzdra viac 360 00:17:23,060 --> 00:17:26,359 všeobecne, ale poďme sa sústrediť len Na spodnej hranice všeobecne. 361 00:17:26,359 --> 00:17:31,920 Čo je to algoritmus, ktorý má dolná hranica n krokov, 362 00:17:31,920 --> 00:17:33,350 alebo 2n krokov, alebo 3n kroky? 363 00:17:33,350 --> 00:17:36,241 Niektoré faktor n krokov, to je jeho dolná hranica. 364 00:17:36,241 --> 00:17:36,740 Jo? 365 00:17:36,740 --> 00:17:37,910 >> Divákov: Bubble sort? 366 00:17:37,910 --> 00:17:41,610 >> SPEAKER: Bubble sort sa budete minimálne n krokov, prečo? 367 00:17:41,610 --> 00:17:42,279 Prečo tomu tak je? 368 00:17:42,279 --> 00:17:45,320 Prečo by to začiatok prísť k vám intuitívne, aj keď to nie je len 369 00:17:45,320 --> 00:17:46,530 ešte? 370 00:17:46,530 --> 00:17:47,030 Jo? 371 00:17:47,030 --> 00:17:47,990 >> Divákov: [nepočuteľné]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 SPEAKER: Presne tak. 374 00:17:52,360 --> 00:17:55,810 V najlepšom možnom scenári bublina triediť a mnoho algoritmov, 375 00:17:55,810 --> 00:17:58,769 ak odovzdám vám osem ľudí ktorý už je zoradený, 376 00:17:58,769 --> 00:18:00,560 že by bolo pochabé pre vás, algoritmus, 377 00:18:00,560 --> 00:18:02,202 ísť tam a späť viac ako raz, nie? 378 00:18:02,202 --> 00:18:04,285 Vzhľadom k tomu, akonáhle sa prejsť zoznam raz, 379 00:18:04,285 --> 00:18:08,090 mali by ste si uvedomiť, oh, som žiadny swapy, tento zoznam je triedený, exit. 380 00:18:08,090 --> 00:18:09,700 Ale, čo sa deje, aby vás n krokov. 381 00:18:09,700 --> 00:18:12,033 >> A naopak, čo je iný spôsob, ako o tom premýšľať? 382 00:18:12,033 --> 00:18:15,240 Bubble sort je omega, aby som tak povedal, n, 383 00:18:15,240 --> 00:18:19,050 pretože keď sa pozriete na menej ako n prvkov, čo sa 384 00:18:19,050 --> 00:18:23,009 je tu zásadný problém? 385 00:18:23,009 --> 00:18:24,550 Neviete, či je to triedenie, doprava. 386 00:18:24,550 --> 00:18:26,800 Sme ľudia, môže dôjsť pohľad na osem ľudí a byť rád, ach, je to triedenie, 387 00:18:26,800 --> 00:18:28,430 že si mi n krokov neberie, ale stalo sa. 388 00:18:28,430 --> 00:18:30,810 Tvoje oči, aj keď tak nejako zo majú veľký zorné pole, 389 00:18:30,810 --> 00:18:33,184 ste sa pozreli na ôsmich prvkov, ste sa pozreli na osem osôb, 390 00:18:33,184 --> 00:18:34,610 to je osem krokov efektívne. 391 00:18:34,610 --> 00:18:38,612 A len vtedy, ak som prejsť celý Zoznam mám uvedomiť, áno, triediť. 392 00:18:38,612 --> 00:18:41,320 Ak by som sa zastaví na mysli všetky Dobre, je to celkom radené tak ďaleko, 393 00:18:41,320 --> 00:18:42,520 aké sú šance, že to nie je triedené? 394 00:18:42,520 --> 00:18:44,186 To algoritmy nebude správne. 395 00:18:44,186 --> 00:18:46,250 Môže byť rýchlejší, ale nesprávne. 396 00:18:46,250 --> 00:18:48,500 >> Takže teraz máme spôsob, ako popisujúce dolná hranica, 397 00:18:48,500 --> 00:18:49,710 a čo konštantnom čase? 398 00:18:49,710 --> 00:18:54,565 Čo je to algoritmus, ktorý má nižší viazaná na jeho chode dobe jedného? 399 00:18:54,565 --> 00:18:58,350 1 krok, dva kroky, 10 krokov, ale konštantná, nezávisle na n, 400 00:18:58,350 --> 00:18:59,310 Veľkosť vstupu? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Jo, v chrbte. 403 00:19:04,600 --> 00:19:05,309 >> Divákov: printf? 404 00:19:05,309 --> 00:19:06,183 SPEAKER: Čo je to? 405 00:19:06,183 --> 00:19:07,184 Divákov: printf? 406 00:19:07,184 --> 00:19:07,850 SPEAKER: printf. 407 00:19:07,850 --> 00:19:08,400 OK, iste. 408 00:19:08,400 --> 00:19:10,720 Tak to trvá stanovenom počte krokov. 409 00:19:10,720 --> 00:19:13,170 A ja som mala teď-- teraz hovoríme o C kódu 410 00:19:13,170 --> 00:19:16,040 a nie Scratch, niečo ako povedzme, s printf, 411 00:19:16,040 --> 00:19:17,710 by sme mali začať, aby si opatrný. 412 00:19:17,710 --> 00:19:21,090 Vzhľadom k tomu, printf sa vziať vstup, je to reťazec, 413 00:19:21,090 --> 00:19:23,220 a reťazce to technicky mať dĺžku. 414 00:19:23,220 --> 00:19:25,530 Takže ak chceme teraz vybrať na vás, či vám to nebude vadiť, 415 00:19:25,530 --> 00:19:29,430 technicky by sme mohli tvrdiť, že printf to sa s premennou dĺžkou vstup, 416 00:19:29,430 --> 00:19:32,270 a iste by to mohlo trvať dlhšie Doba tlače reťazec tak dlho, 417 00:19:32,270 --> 00:19:33,560 ako tak dlho. 418 00:19:33,560 --> 00:19:36,570 >> A čo keď vezmeme do úvahy len triedenie a vyhľadávanie príkladov? 419 00:19:36,570 --> 00:19:40,450 Čo Mike Smith v telefóne kniha, alebo binárne vyhľadávanie všeobecne? 420 00:19:40,450 --> 00:19:42,220 V najlepšom prípade, čo sa môže stať? 421 00:19:42,220 --> 00:19:45,577 Otvoril som telefónny zoznam, a bum, tam je číslo Mike Smith. 422 00:19:45,577 --> 00:19:46,660 Nemôžem ho zavolať hneď. 423 00:19:46,660 --> 00:19:49,390 >> Urobil jeden krok, možno dva kroky, ale konštantný počet krokov 424 00:19:49,390 --> 00:19:50,230 keď som mal šťastie. 425 00:19:50,230 --> 00:19:52,570 A úprimne povedané, sme videli na Pondelok váš spolužiak 426 00:19:52,570 --> 00:19:54,710 dostať celkom šťastie dvakrát za sebou. 427 00:19:54,710 --> 00:19:57,050 A to je skutočne konštantná čas v dolná hranica 428 00:19:57,050 --> 00:20:01,280 na algoritme sa jedná o hľadanie číslo 50 za tie zatvorené 429 00:20:01,280 --> 00:20:01,830 dvere. 430 00:20:01,830 --> 00:20:06,400 >> Teraz, rovnako ako stranou, keď zistíte, že tak veľký O, horná hranica, 431 00:20:06,400 --> 00:20:09,310 a omega, dolná hranica, sú jeden v rovnakej, že 432 00:20:09,310 --> 00:20:11,830 je rovnaký vzorec v zátvorky, môžete tiež 433 00:20:11,830 --> 00:20:15,170 povedať, len pre chuť, , Že niečo, čo je v theta 434 00:20:15,170 --> 00:20:18,270 n alebo theta nejaké iné hodnoty. 435 00:20:18,270 --> 00:20:20,661 To jednoducho znamená, že keď veľká O a omega sú rovnaké. 436 00:20:20,661 --> 00:20:21,910 A čo výber druhu teraz? 437 00:20:21,910 --> 00:20:23,400 Využime túto novú slovnú zásobu. 438 00:20:23,400 --> 00:20:27,407 Vo výbere druhu, o čom sme robiť znova a znova a znova? 439 00:20:27,407 --> 00:20:29,990 Bol som tam a späť cez zoznam, hľadá pre koho? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Najmenšie číslo. 442 00:20:34,730 --> 00:20:37,560 >> Tak koľko krokov, ako veľa porovnaní urobil ja 443 00:20:37,560 --> 00:20:43,250 musieť urobiť, aby sa zistiť, kto najmenší prvok v zozname je? 444 00:20:43,250 --> 00:20:44,437 n mínus 1, nie? 445 00:20:44,437 --> 00:20:47,770 Pretože keď som začať s jedným Som vzhľadom k tomu, a začnem ho porovnávanie, 446 00:20:47,770 --> 00:20:49,519 potom on alebo ona, ho alebo ona, on alebo ona, som 447 00:20:49,519 --> 00:20:52,010 možno spárovať iba prvky spolu n mínus 1 krát. 448 00:20:52,010 --> 00:20:55,630 Takže výber trochu podobne sa n mínus 1 krok prvýkrát. 449 00:20:55,630 --> 00:20:59,540 >> Koľko krokov to ma vziať nájsť druhý najmenší prvok? 450 00:20:59,540 --> 00:21:02,920 n mínus 2, pretože som bol hlúpy ak Stále sa pozerá na rovnakých ľudí 451 00:21:02,920 --> 00:21:06,280 znova, či som ho už vybrali alebo ju a dať ich na ich miesto. 452 00:21:06,280 --> 00:21:09,270 A tretí krok, n mínus 3, potom n mínus štyri. 453 00:21:09,270 --> 00:21:11,020 Videli sme tento model pred, a skutočne 454 00:21:11,020 --> 00:21:13,460 Výber triedenie podobne je horná hranica 455 00:21:13,460 --> 00:21:16,210 n na druhú, ak budeme robiť až ten zhrnutie. 456 00:21:16,210 --> 00:21:19,790 Aká je jeho dolná hranica, výber trochu? 457 00:21:19,790 --> 00:21:25,350 Minimálne, koľko výber času musí triedenie sa, ako sa nám to definované v pondelok? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Navrhnúť dve možnosti. 460 00:21:30,490 --> 00:21:32,360 Možno je to n, ako predtým. 461 00:21:32,360 --> 00:21:35,040 Možno, že to je n na druhú, ako to Teraz je ako horná hranica. 462 00:21:35,040 --> 00:21:35,874 >> Divákov: n na druhú. 463 00:21:35,874 --> 00:21:36,664 SPEAKER: n na druhú. 464 00:21:36,664 --> 00:21:37,368 Prečo? 465 00:21:37,368 --> 00:21:40,060 >> Divákov: Pretože máte definovať [nepočuteľné]. 466 00:21:40,060 --> 00:21:41,510 >> SPEAKER: Presne tak. 467 00:21:41,510 --> 00:21:45,077 Aspoň ako som je definované výber druhu to bolo dosť naivné, pokračuj, 468 00:21:45,077 --> 00:21:46,160 nájsť najmenší prvok. 469 00:21:46,160 --> 00:21:47,770 Iďte zase, nájsť najmenší prvok. 470 00:21:47,770 --> 00:21:49,490 Iďte zase, nájsť najmenší prvok. 471 00:21:49,490 --> 00:21:51,700 Neexistuje žiadny druh optimalizácia v tam, že 472 00:21:51,700 --> 00:21:54,350 môže mi dovoľte ukončiť po len n alebo tak kroky. 473 00:21:54,350 --> 00:21:57,080 Takže naozaj, výber triedenie, omega n na druhú. 474 00:21:57,080 --> 00:22:00,667 >> Čo vloženie druhu, kde som vzal ktorý som dostal, a potom som ho zvalil 475 00:22:00,667 --> 00:22:01,750 alebo ju na správne miesto? 476 00:22:01,750 --> 00:22:04,958 Potom som pristúpil k druhej osobe, zvalil ho na správnom mieste. 477 00:22:04,958 --> 00:22:07,910 Potom ďalšia osoba, zvalil ho alebo ju na správnom mieste. 478 00:22:07,910 --> 00:22:10,537 Všimnite si, že je to veľmi lineárne, aby som tak povedal. 479 00:22:10,537 --> 00:22:12,620 Som priamka, ja som Nie je tam a späť, 480 00:22:12,620 --> 00:22:16,080 Nikdy som sa obzrel nie, ale čo sa deje, keď som sa ho vložiť 481 00:22:16,080 --> 00:22:20,302 alebo ju do začiatku zoznam ako sme to urobili v pondelok? 482 00:22:20,302 --> 00:22:21,010 Čo sa deje? 483 00:22:21,010 --> 00:22:21,510 Jo? 484 00:22:21,510 --> 00:22:23,122 Divákov: [nepočuteľné]. 485 00:22:23,122 --> 00:22:24,830 SPEAKER: Jo, to bol úlovok, nie? 486 00:22:24,830 --> 00:22:26,746 Možno pamätáte z svojimi spolužiakmi, ak sa 487 00:22:26,746 --> 00:22:29,670 robili akýkoľvek pohyb s ich nohy, to je operácia. 488 00:22:29,670 --> 00:22:33,610 Takže v prípade, že boli traja ľudia tu a nový človek patril tamto, 489 00:22:33,610 --> 00:22:37,360 na dlhú fázu, ako je táto, iste, že alebo mohla jednoducho ísť až do samého konca. 490 00:22:37,360 --> 00:22:40,074 Ale ak uvažujete o počítača a polia pamäti, 491 00:22:40,074 --> 00:22:41,990 títo ľudia idú musieť zamiešať cez 492 00:22:41,990 --> 00:22:43,260 aby sa priestor pre túto osobu. 493 00:22:43,260 --> 00:22:46,930 A tak, aby n mínus 1 shufflings, n mínus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 mínus 3 shufflings je len trochu sa deje za mnou, nie predo mnou 495 00:22:50,660 --> 00:22:52,710 ako predtým, v istom zmysle. 499 00:22:52,557 --> 00:22:54,640 Teraz ako stranou a ako ste mohli vidieť on-line 500 00:22:54,640 --> 00:22:57,699 ak začnete vŕtať o druhy, je tam toľko rôznych ty 501 00:22:57,699 --> 00:22:59,490 tam, niektoré z nich lepší než ostatní. 502 00:22:59,490 --> 00:23:02,200 V skutočnosti, je jedným bogosort to je celkom zábavné vzhliadnuť. 503 00:23:02,200 --> 00:23:06,650 Bogosort má sadu čísla alebo hovoria, balíček kariet, 504 00:23:06,650 --> 00:23:09,870 náhodne zamieša je a skontroluje, či oni sú radené. 505 00:23:09,870 --> 00:23:12,130 A ak nie, urobí to znova. 506 00:23:12,130 --> 00:23:14,140 A ak nie, urobí to znova. 507 00:23:14,140 --> 00:23:15,440 Ak nie, robí to znova. 508 00:23:15,440 --> 00:23:17,060 Neuveriteľne hlúpy. 509 00:23:17,060 --> 00:23:19,520 >> A skutočne, keď si prečítate ako Wikipedia článku, 510 00:23:19,520 --> 00:23:21,200 jeho prezývka je hlúpy druh. 511 00:23:21,200 --> 00:23:25,180 To bude nakoniec fungovať, dúfajme, že vzhľadom na to dostatok času, 512 00:23:25,180 --> 00:23:28,240 ale to množstvo času, môže trvať nejakú dobu. 513 00:23:28,240 --> 00:23:31,650 Takže ak by som mohol, poďme rýchlosti vecí up od Mary Beth je napríklad skôr 514 00:23:31,650 --> 00:23:35,150 tým, že má ešte niekoľko ďalších prvkov, ale ďalšie dva procesory. 515 00:23:35,150 --> 00:23:37,100 Dvaja ľudia, ak máte Nevadilo by mi to spojenie. 516 00:23:37,100 --> 00:23:40,972 Ako sa o jeden sem, a poďme jít-- nikoho tam? 517 00:23:40,972 --> 00:23:41,722 Nikto tam? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 Tie s čiernou košele, áno, poď dole. 520 00:23:44,190 --> 00:23:45,000 Tak jo, Ako sa voláte? 521 00:23:45,000 --> 00:23:45,720 >> DIVÁKOV: Peter. 522 00:23:45,720 --> 00:23:46,100 >> SPEAKER: Čo je to? 523 00:23:46,100 --> 00:23:46,766 >> DIVÁKOV: Peter. 524 00:23:46,766 --> 00:23:49,450 SPEAKER: Peter Dávid, rád ťa spoznávam. 525 00:23:49,450 --> 00:23:53,670 Dobre, máme Petra tu, ak máte chcú prísť na stôl sem. 526 00:23:53,670 --> 00:23:54,550 A Ako sa voláte? 527 00:23:54,550 --> 00:23:55,216 >> DIVÁKOV: Elena. 528 00:23:55,216 --> 00:23:55,970 SPEAKER: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, rád ťa spoznávam. 530 00:23:57,030 --> 00:23:58,060 Elena stretnúť Petera. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 A budeme potrebovať Andrew sa aj tu, prosím. 533 00:24:02,290 --> 00:24:06,107 A vaša výzva sa deje aby triediť balíček kariet. 534 00:24:06,107 --> 00:24:08,190 A ak nepoznáte, paluba kariet by malo v konečnom dôsledku 535 00:24:08,190 --> 00:24:11,064 zoradiť trochu niečo ako Tu urobíme kluby, potom 536 00:24:11,064 --> 00:24:13,660 lopatky, potom srdce a diamanty, od esa ako jeden, 537 00:24:13,660 --> 00:24:15,570 celú cestu až ku kráľovi. 538 00:24:15,570 --> 00:24:20,890 >> Karty budem vám sa bude 52 v množstve. 539 00:24:20,890 --> 00:24:23,160 Chystáme sa podobne čas vás za chvíľu. 540 00:24:23,160 --> 00:24:26,410 Budeme hádzať Andrew na obrazovke tu 541 00:24:26,410 --> 00:24:28,170 tak sa pozerať, ako to urobíte. 542 00:24:28,170 --> 00:24:31,070 A aby to všetko je to viac vidieť, 543 00:24:31,070 --> 00:24:33,490 to sú karty Dostal som na Amazonu. 544 00:24:33,490 --> 00:24:42,861 Takže už sú náhodne radené, a budeme vám čas. 545 00:24:42,861 --> 00:24:44,610 A ideme na udržať skutočný tentoraz 546 00:24:44,610 --> 00:24:47,820 takže budeme snažiť tlačiť pretože inak to bude únavné 547 00:24:47,820 --> 00:24:48,460 rýchlo. 548 00:24:48,460 --> 00:24:53,860 Ak by ste mohli pokračovať triediť 52 prvky spolu cez niektoré prostriedky, hneď. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> A opäť, ako sme sa pozerať na to chlapci robiť čo, na konci 551 00:25:07,180 --> 00:25:10,200 bude produkovať jasné Výsledkom je, premýšľať o tom, naozaj 552 00:25:10,200 --> 00:25:12,962 ako si každý robí, ako môžete to popísať. 553 00:25:12,962 --> 00:25:15,045 Vzhľadom k tomu, opäť sa jedná o Všetky procesy, algoritmy 554 00:25:15,045 --> 00:25:17,090 ktoré berieme ako samozrejmosť ako človek. 555 00:25:17,090 --> 00:25:22,349 Ale pravdepodobne ste už dlho intuícia, dlho predtým, než vás, aj 556 00:25:22,349 --> 00:25:24,390 myšlienka o tom, výpočtová technika vám trieda 557 00:25:24,390 --> 00:25:27,223 mohla byť dôvodom pre intuíciu s pre riešenie problémov, ako je tento. 558 00:25:27,223 --> 00:25:29,560 Ale akonáhle spoznáte vzory a začať 559 00:25:29,560 --> 00:25:32,407 formalizovať kroky, s ktorými máte riešenie týchto problémov, 560 00:25:32,407 --> 00:25:35,490 zistíte, že môžete vyriešiť veľa zaujímavejšie a oveľa zložitejšie 561 00:25:35,490 --> 00:25:39,190 problémy rýchlo. 562 00:25:39,190 --> 00:25:42,351 Takže niekto z publika, čo je aspoň jeden prvok z algoritmu 563 00:25:42,351 --> 00:25:43,350 že používate tu? 564 00:25:43,350 --> 00:25:44,275 >> Divákov: [nepočuteľné] 565 00:25:44,275 --> 00:25:45,150 SPEAKER: Čo je to? 566 00:25:45,150 --> 00:25:47,062 DIVÁKOV: Podľa obleku. 567 00:25:47,062 --> 00:25:47,770 SPEAKER: Podľa obleku. 568 00:25:47,770 --> 00:25:50,630 Takže najprv sa klastrovanie všetky diamanty spoločne 569 00:25:50,630 --> 00:25:52,560 Zdá sa, že všetky srdce spolu sa zdá, 570 00:25:52,560 --> 00:25:56,520 a tak ďalej, a to bez ohľadu pre čísla na kartách. 571 00:25:56,520 --> 00:26:00,900 A teraz sa zdá, napríklad, k triedenie je podľa čísla. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Veľmi dobre. 574 00:26:08,910 --> 00:26:12,370 >> Dobre, takže to, čo sa byť posledným krokom potom tu? 575 00:26:12,370 --> 00:26:16,950 Akonáhle budeme mať štyri triedených obleky, čo to musíme urobiť, aby sa štyri pilotmi 576 00:26:16,950 --> 00:26:20,059 , Aby sa dosiahlo jednej radené palubu, jednoducho? 577 00:26:20,059 --> 00:26:21,350 Preto musíme znova zlúčiť. 578 00:26:21,350 --> 00:26:25,160 >> Takže tam je to zaujímavý nápad, ktorý opäť Trúfam si tvrdiť, je veľmi intuitívne, aj 579 00:26:25,160 --> 00:26:28,140 ak ste možno nikdy facku tento druh štítku na to. 580 00:26:28,140 --> 00:26:31,900 Táto základná predstava o rozdelení problém nie je v polovici tejto doby, 581 00:26:31,900 --> 00:26:33,410 ale aspoň do štyroch častí. 582 00:26:33,410 --> 00:26:36,810 Riešenie do značnej miery v podstate identické problémy 583 00:26:36,810 --> 00:26:40,480 izolovane od seba, a zlúčenie výsledkov. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 A vynikajúce, hotovo. 586 00:26:50,140 --> 00:26:52,140 Tak jo, malý a veľký okruh potlesk, keby sme mohli. 587 00:26:52,140 --> 00:26:56,480 >> [APPLAUSE] 588 00:26:56,480 --> 00:26:59,740 >> SPEAKER: Nemám poňatia, čo budete robiť s nimi, ale tu to máte. 589 00:26:59,740 --> 00:27:01,690 Ďakujem moc. 590 00:27:01,690 --> 00:27:04,660 Tak sa pozrime, dve minúty a osem sekúnd, 591 00:27:04,660 --> 00:27:07,490 ak by ste chceli vyzvať svojich priateľov. 592 00:27:07,490 --> 00:27:12,160 Čo sa potom bude by sa od tohto 593 00:27:12,160 --> 00:27:13,830 že môžeme využiť všeobecne? 594 00:27:13,830 --> 00:27:16,080 No, myslím, že späť do Toto pole čísel, 595 00:27:16,080 --> 00:27:19,060 a myslím, že teraz vrátiť k niektorým pseudokód písali sme v minulosti, 596 00:27:19,060 --> 00:27:22,080 a to pseudokód pre riešenie telefónneho zoznamu problém. 597 00:27:22,080 --> 00:27:25,150 Pričom v pseudokódu I vymenoval viac metodický spôsob 598 00:27:25,150 --> 00:27:28,400 popisovať, ako som to urobil veľmi intuitívne ľudský algoritmus delenia telefón 599 00:27:28,400 --> 00:27:31,650 knihy na polovicu, opakovať, opakovať, opakovať, kým nenájdem niekoho, ako Mike Smith, 600 00:27:31,650 --> 00:27:33,790 v prípade, že je naozaj v telefónnom zozname. 601 00:27:33,790 --> 00:27:37,610 >> Ale nejako som použiť to, čo budem hovoriť veľmi iteratívny prístup tu 602 00:27:37,610 --> 00:27:42,160 najmä oznámenia linka 8 a linka 11. 603 00:27:42,160 --> 00:27:46,750 To sú dôkazy o iteratívny prístup, prístup smyčkování, 604 00:27:46,750 --> 00:27:49,040 pretože to je presne to, správanie, ktoré vyvolávajú. 605 00:27:49,040 --> 00:27:52,910 Tieto riadky obaja, že ísť do riadok tri, a môžete trochu 606 00:27:52,910 --> 00:27:55,140 myslieť, že vo vašom mysli oko ako slučka. 607 00:27:55,140 --> 00:27:59,080 Je to hovorím, ísť späť ku kroku tri a opakovať znovu a znovu, 608 00:27:59,080 --> 00:28:00,010 a znovu. 609 00:28:00,010 --> 00:28:04,410 >> Ale čo keď budeme využívať kľúčovú myšlienku tu, že sme nemali v poslednej dobe, 610 00:28:04,410 --> 00:28:10,280 a zjednodušiť linky 8 a riadok 11 a ich susedia 611 00:28:10,280 --> 00:28:12,840 ako je len to, žlto. 612 00:28:12,840 --> 00:28:16,480 Nie je to v podstate skrátenie pseudokód moc, 613 00:28:16,480 --> 00:28:20,530 ale je to v podstate mení povahu môjho algoritmu. 614 00:28:20,530 --> 00:28:24,220 To, čo som teraz povedal v kroku 7, v kroku 10, 615 00:28:24,220 --> 00:28:29,140 je hľadať Mike v presne rovnakým spôsobom, 616 00:28:29,140 --> 00:28:31,580 ale len v ľavej polpenzia alebo pravú polovicu. 617 00:28:31,580 --> 00:28:33,420 >> Takže inými slovami, v prípade, Začnem od kroku jedna, 618 00:28:33,420 --> 00:28:36,150 zdvihnúť telefónny zoznam, otvorený stred z telefónneho zoznamu, pozrite sa na mená, 619 00:28:36,150 --> 00:28:39,010 ak Smith patrí medzi Názov je, zavolajte Mike, inak 620 00:28:39,010 --> 00:28:44,340 ak Smith predtým v knihe krok za sedem hľadať Mike v ľavej polovici knihy. 621 00:28:44,340 --> 00:28:47,130 Ale trochu pocit, ako to nechal ma visí, že jo? 622 00:28:47,130 --> 00:28:49,240 V žltej, je inštrukcie, ale ako to mám 623 00:28:49,240 --> 00:28:51,870 hľadanie Mike v ľavej polovica z telefónneho zoznamu? 624 00:28:51,870 --> 00:28:54,210 Kde mám algoritmus, s ktorým som 625 00:28:54,210 --> 00:28:57,100 Môžete hľadať niekoho, ako je Mike Smith? 626 00:28:57,100 --> 00:28:58,980 No, je to zíza nás tvárou v tvár. 627 00:28:58,980 --> 00:29:03,090 Môžem doslova použiť presne rovnaký program skutočne ísť až na vrchol 628 00:29:03,090 --> 00:29:06,490 Znovu a znovu beží rovnaké riadky kódu. 629 00:29:06,490 --> 00:29:10,610 >> Takže aj keď by to malo cítiť ako trochu cyklické definície 630 00:29:10,610 --> 00:29:13,480 kam odpovede niekto Otázka, ktorú tak nejako sa pýtať 631 00:29:13,480 --> 00:29:15,990 opäť rovnaká otázka, ako prečo, prečo, prečo? 632 00:29:15,990 --> 00:29:21,580 Skutočnosťou je, pretože sme pevne dané niekoľko špeciálnych liniek, krok 4, 633 00:29:21,580 --> 00:29:25,320 , Ktorý je v prípade, a krok 12, ktorý je v podstate ďalšia vetva, 634 00:29:25,320 --> 00:29:30,120 pretože máme tie provizórium opatrenia, Tento algoritmus sa ukončí, ak budeme 635 00:29:30,120 --> 00:29:32,050 nájsť Mike, alebo ak to neurobíme. 636 00:29:32,050 --> 00:29:36,810 Ale v kroku 7 a 10 teraz máme čo budeme hovoriť rekurzívny algoritmus. 637 00:29:36,810 --> 00:29:40,420 A rekurzia je naozaj silný nápad to je trochu myseľ ohýbanie na prvý, 638 00:29:40,420 --> 00:29:42,500 že teraz môžeme aplikovať takto. 639 00:29:42,500 --> 00:29:46,600 >> Merge sort bude posledný druh, ktorý sa pozrieme na, aspoň v triede formálne. 640 00:29:46,600 --> 00:29:50,040 A to je zásadne odlišná z tých posledných troch, a iste 641 00:29:50,040 --> 00:29:52,140 Posledné štyri ak zahrnieme bogosort. 642 00:29:52,140 --> 00:29:54,810 Tu je pseudokód pre zlučovacie druhu. 643 00:29:54,810 --> 00:30:00,170 Keď sa na vstupe n prvkov tak, vzhľadom k poľa veľkosti n, ak n je menšie ako 2, 644 00:30:00,170 --> 00:30:01,040 vrátiť. 645 00:30:01,040 --> 00:30:03,610 Tak prečo mám, že zdravý rozum skontrolovať ako prvý? 646 00:30:03,610 --> 00:30:09,477 Aký je dôsledok, ak odovzdám vás pole, ktorého dĺžka n je menšia ako 2? 647 00:30:09,477 --> 00:30:11,060 Je to už zoradený, samozrejme, že jo? 648 00:30:11,060 --> 00:30:13,640 Pretože zoznam má buď jeden prvok, ktorý je triviálne 649 00:30:13,640 --> 00:30:15,180 radené, pretože je to Jediné, čo tam. 650 00:30:15,180 --> 00:30:18,138 Alebo je to o veľkosti nula, čo znamená, nič vyriešiť, tak od prírody 651 00:30:18,138 --> 00:30:18,720 to je triedený. 652 00:30:18,720 --> 00:30:20,410 Je tu len nič zlého tam. 653 00:30:20,410 --> 00:30:22,310 Tak to je náš takzvaný referenčný prípad. 654 00:30:22,310 --> 00:30:24,440 >> To je podobné v duchu na to, čo sme urobili s Mikom. 655 00:30:24,440 --> 00:30:26,023 Ak sa Mike v telefónnom zozname, zavolajte mu. 656 00:30:26,023 --> 00:30:27,740 Ak tam nie je, vzdať. 657 00:30:27,740 --> 00:30:31,240 Je to takzvaný referenčný prípad, aby sa ubezpečil, Tento algoritmus na konci dňa 658 00:30:31,240 --> 00:30:33,540 sa zastaví v určitých okolností. 659 00:30:33,540 --> 00:30:37,890 >> Ale tu je ten skok viery teraz, inak, zoradiť ľavú polovicu prvkov, 660 00:30:37,890 --> 00:30:39,740 zoradiť právo polovica z prvkov, 661 00:30:39,740 --> 00:30:41,189 a potom zlúčiť zoradené polovice. 662 00:30:41,189 --> 00:30:43,230 A tu je miesto, kde sa cíti to, že sme Copping von. 663 00:30:43,230 --> 00:30:46,900 Požiadal som vás, aby ste triedenie n prvkov, a ja som 664 00:30:46,900 --> 00:30:50,712 riekol: OK, to je triedenie doľava a triedenie právo. 665 00:30:50,712 --> 00:30:52,420 Ale ja hovorím jedno Ďalšia vec, a to 666 00:30:52,420 --> 00:30:55,530 je kľúčové téma sa zdá, v intuíciu tak ďaleko, 667 00:30:55,530 --> 00:30:57,380 tam je to tretí krok zlučovanie. 668 00:30:57,380 --> 00:31:00,430 Ktoré, aj keď sa zdá byť tak hlúpy v duchu, 669 00:31:00,430 --> 00:31:02,320 ako práve zlúčiť veci spolu, sa zdá 670 00:31:02,320 --> 00:31:05,380 byť kľúčovým krokom smerom k opätovnú montáž dvoch problémov, ktoré 671 00:31:05,380 --> 00:31:07,330 boli rozdelené nakoniec v polovici. 672 00:31:07,330 --> 00:31:12,090 >> Takže zlúčiť druh, ideme na to, ak budete humor, aby som sa ešte jednu demonštráciu, 673 00:31:12,090 --> 00:31:14,730 len preto, že máme nejaké Čísla pracovať. 674 00:31:14,730 --> 00:31:19,470 Môžem u Vás vymeniť osem stres lopty pre osem ľudí? 675 00:31:19,470 --> 00:31:29,320 Dobre, a čo vy tri, vy štyria v tejto časti, päť, šesť, a poďme 676 00:31:29,320 --> 00:31:30,720 do 7, 8, poď hore. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, jo OK. 679 00:31:36,520 --> 00:31:38,640 Mínus 8, ideme na to, plus 1. 680 00:31:38,640 --> 00:31:39,150 Výborne. 681 00:31:39,150 --> 00:31:42,000 Dobre poď hore, poďme Rýchlo vám čísel. 682 00:31:42,000 --> 00:31:50,800 Číslo dve, číslo tri, číslo štyri, číslo päť, šesť, sedem a osem. 683 00:31:50,800 --> 00:31:52,140 Urobil som osem správne tentoraz. 684 00:31:52,140 --> 00:31:56,390 >> OK, tak do toho, ak by ste mohol, a zoraďte v pôvodnom poradí 685 00:31:56,390 --> 00:31:59,810 že sme mali včera, ktorá sa zaoberala takto, ak vám to nebude vadiť. 686 00:31:59,810 --> 00:32:03,620 A ideme na to pred stolom. 687 00:32:03,620 --> 00:32:06,510 Dobre, takže zlúčiť druh. 688 00:32:06,510 --> 00:32:08,820 To je miesto, kde to bude dostať celkom zaujímavé, 689 00:32:08,820 --> 00:32:12,800 pretože to vyzerá, že dávať sám seba oveľa menej informácií dnes. 690 00:32:12,800 --> 00:32:15,149 >> Takže zlúčiť druh v prvom rade na vstupe n prvkov, 691 00:32:15,149 --> 00:32:18,440 a je samozrejme nie menej ako dva, je to osem, takže mám trochu viac práce. 692 00:32:18,440 --> 00:32:21,140 Takže teraz psychicky sme sa ako trieda sú teraz v inom sektore, 693 00:32:21,140 --> 00:32:22,540 čo znamená, že tri kroky. 694 00:32:22,540 --> 00:32:25,017 Po prvé, musím vyriešiť ľavá polovica prvkov. 695 00:32:25,017 --> 00:32:26,350 Tak ako mám ísť asi robí? 696 00:32:26,350 --> 00:32:28,950 No, ja idem na druh mentálne rozdeliť zoznam tu 697 00:32:28,950 --> 00:32:30,700 nemáte k fyzicky pohybovať, a ja som 698 00:32:30,700 --> 00:32:33,180 Zameriam sa iba na ľavá polovica prvkov tu. 699 00:32:33,180 --> 00:32:36,770 Tak ako mám ísť o triedení zoznam sa veľkosti štyri? 700 00:32:36,770 --> 00:32:38,730 Čo je môj algoritmus? 701 00:32:38,730 --> 00:32:42,580 Najprv som skontrolujte n menšia než dva, nie, tak som sa pristúpiť k bloku iného znovu. 702 00:32:42,580 --> 00:32:43,900 Zoradiť ľavej polovici prvkov. 703 00:32:43,900 --> 00:32:45,608 >> Takže znova, mentálne, a to je tam, kde 704 00:32:45,608 --> 00:32:49,550 Máte pribúdať veľa duševné histórie, ak chcete. 705 00:32:49,550 --> 00:32:51,940 Teraz triedenie ľavej polovica z ľavej polovice. 706 00:32:51,940 --> 00:32:57,000 Dobre, takže teraz volám rovnaký korešpondencie algoritmus triedenia, n je menšia než dva? 707 00:32:57,000 --> 00:33:00,590 Nie, je to dva, takže musím vyriešiť ľavá polovica, a pravú polovicu. 708 00:33:00,590 --> 00:33:02,042 Tak ideme na to, triedenie ľavej polovice. 709 00:33:02,042 --> 00:33:03,750 Prečo nie len jeden krok vpred. 710 00:33:03,750 --> 00:33:04,415 Ako sa voláte? 711 00:33:04,415 --> 00:33:04,860 >> DIVÁKOV: Darren. 712 00:33:04,860 --> 00:33:05,260 >> SPEAKER: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan urobil krok vpred. 714 00:33:06,040 --> 00:33:06,748 >> DIVÁKOV: Darren. 715 00:33:06,748 --> 00:33:09,000 SPEAKER: Darren, hotovo. 716 00:33:09,000 --> 00:33:10,090 Hovorila ste, že Darrena alebo Dan? 717 00:33:10,090 --> 00:33:10,550 >> DIVÁKOV: Darren. 718 00:33:10,550 --> 00:33:11,216 >> SPEAKER: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren pristúpil dopredu a on je teraz radené. 720 00:33:14,422 --> 00:33:16,130 A to je takmer stupídne tvrdenie, že jo? 721 00:33:16,130 --> 00:33:18,862 Nemám naozaj Zdá sa, že dosiahnutie niečo, ale poďme pokračovať. 722 00:33:18,862 --> 00:33:20,820 Teraz mi dovoľte zoradiť právo polovica z týchto prvkov. 723 00:33:20,820 --> 00:33:21,200 Ako sa voláte? 724 00:33:21,200 --> 00:33:21,690 >> DIVÁKOV: Luke. 725 00:33:21,690 --> 00:33:22,273 >> SPEAKER: Luke. 726 00:33:22,273 --> 00:33:23,400 Poď, krok vpred. 727 00:33:23,400 --> 00:33:25,640 Hotovo, som radené Luku. 728 00:33:25,640 --> 00:33:28,570 Ľavá polovica je teraz triedené a pravá polovica je teraz triedené, 729 00:33:28,570 --> 00:33:30,770 ale zase tam je kľúčovým krokom tu. 730 00:33:30,770 --> 00:33:32,940 Čo u potrebné urobiť? 731 00:33:32,940 --> 00:33:33,941 Zlúčiť zoradené polovice. 732 00:33:33,941 --> 00:33:36,648 Teraz budeme jednoducho musieť všetci sem a tam tak, 733 00:33:36,648 --> 00:33:38,620 pretože som tak trochu potrebovať nejaký odkladací priestor. 734 00:33:38,620 --> 00:33:40,411 Je to skoro, ako sú tieto chlapci sú na stole, 735 00:33:40,411 --> 00:33:42,460 a ja potrebujem nejaký priestor je pohybovať ďalej. 736 00:33:42,460 --> 00:33:44,170 Takže budem zlúčiť vy od pohľadu 737 00:33:44,170 --> 00:33:45,960 v ľavej polovici a pravej polovici. 738 00:33:45,960 --> 00:33:48,740 A kto zrejme je na prvom mieste, vľavo alebo vpravo polovica polovice? 739 00:33:48,740 --> 00:33:52,710 Takže pravá polovica, takže poďme Luka nad tu pôvodnej polohy Darren. 740 00:33:52,710 --> 00:33:57,640 A teraz zlúčiť ich ľavú polovicu v, Darren sa bude pohybovať práve tam. 741 00:33:57,640 --> 00:33:59,750 >> Tak sa cíti ako takmer bublina druh účinku, 742 00:33:59,750 --> 00:34:02,482 ale moja základná algoritmus, veľmi odlišné tentoraz. 743 00:34:02,482 --> 00:34:04,815 Ale teraz je miesto, kde sa veci trochu nepríjemné, pretože ste 744 00:34:04,815 --> 00:34:06,810 musieť pretočiť mentálne kde som odísť preč. 745 00:34:06,810 --> 00:34:09,893 Práve som sa spojil zotriedené polovice, čo znamená, že som tam, kde vo svojom algoritmu? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Musím vyriešiť pravú polovicu, nie? 748 00:34:13,770 --> 00:34:15,910 >> Ak máte vzad, a to doslova na videu, budete 749 00:34:15,910 --> 00:34:18,339 vidieť, že sme sa dostali do tejto bod Luke a Darren 750 00:34:18,339 --> 00:34:21,370 triedením doľava polovica z ľavej polovice. 751 00:34:21,370 --> 00:34:23,430 Potom sme sa spojil tie triedené polovice, ktoré 752 00:34:23,430 --> 00:34:27,941 znamená, že ďalším krokom je triedenie Pravá polovica ľavej polovici. 753 00:34:27,941 --> 00:34:29,649 Dobre, tak poďme to rýchlejšie. 754 00:34:29,649 --> 00:34:33,282 Tak jo, šesť, budem tvrdiť, ste teraz triedené, poď dopredu. 755 00:34:33,282 --> 00:34:33,990 Ako sa voláte? 756 00:34:33,990 --> 00:34:34,589 >> DIVÁKOV: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> SPEAKER: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano je teraz radené. 759 00:34:36,010 --> 00:34:36,450 A Ako sa voláte? 760 00:34:36,450 --> 00:34:37,080 >> DIVÁKOV: Alex. 761 00:34:37,080 --> 00:34:38,379 >> SPEAKER: Alex je teraz radené. 762 00:34:38,379 --> 00:34:40,750 Ľavá polovica, pravá polovica, čo je posledný krok? 763 00:34:40,750 --> 00:34:41,250 Zlúčiť. 764 00:34:41,250 --> 00:34:44,310 Celkom triviálne, takže som k fúzii v šiestich, 765 00:34:44,310 --> 00:34:46,930 krok späť, osem, urobiť krok späť. 766 00:34:46,930 --> 00:34:49,530 A teraz si toho všimnúť je užitočné stánok s jedlom, čo 767 00:34:49,530 --> 00:34:53,930 je teraz platí o ľavej polovici zoznam, a to bez ohľadu na to, ako sme začali? 768 00:34:53,930 --> 00:34:55,090 To je triedený. 769 00:34:55,090 --> 00:34:57,750 >> Teraz to nie je zoradený veľký schéme vecí, 770 00:34:57,750 --> 00:35:00,250 ale to je radený samostatne z druhej polovice. 771 00:35:00,250 --> 00:35:04,100 A teraz, čo krok to som na tom, či som sa udržať prevíjanie, ako príbeh začal? 772 00:35:04,100 --> 00:35:05,680 Teraz musím vyriešiť pravú polovicu. 773 00:35:05,680 --> 00:35:07,630 Takže teraz sme cestu späť na začiatok príbehu, 774 00:35:07,630 --> 00:35:08,921 a poďme na to rýchlejšie. 775 00:35:08,921 --> 00:35:11,320 Takže budem triediť pravá polovica celého zoznamu. 776 00:35:11,320 --> 00:35:13,060 Aký je ďalší krok? 777 00:35:13,060 --> 00:35:15,840 Zoradiť ľavú polovicu pravej polovici. 778 00:35:15,840 --> 00:35:18,715 Zoradiť ľavej polovici ľavá polovica v pravej polovici. 779 00:35:18,715 --> 00:35:19,590 A Ako sa voláte? 780 00:35:19,590 --> 00:35:20,230 >> DIVÁKOV: Omar. 781 00:35:20,230 --> 00:35:21,970 >> SPEAKER: Omar, krok vpred, hotovo. 782 00:35:21,970 --> 00:35:22,860 Ľavá polovica je triedený. 783 00:35:22,860 --> 00:35:23,330 A Ako sa voláte? 784 00:35:23,330 --> 00:35:23,820 >> DIVÁKOV: Chris. 785 00:35:23,820 --> 00:35:25,620 >> SPEAKER: Chris, krok vpred, ste teraz radené. 786 00:35:25,620 --> 00:35:27,010 Čo je kľúčovým krokom teraz? 787 00:35:27,010 --> 00:35:27,510 Zlúčiť. 788 00:35:27,510 --> 00:35:30,509 Takže človek sa chystá zlúčiť svoje miesto tu, ak by ste mohli urobiť krok späť, 789 00:35:30,509 --> 00:35:32,930 a tri sa chystá krok späť, zlúčiť. 790 00:35:32,930 --> 00:35:38,080 Takže ľavá polovica Pravá polovica je teraz radené. 791 00:35:38,080 --> 00:35:41,747 Úprimne povedané, tento algoritmus pocit, ako by sme Strácate spôsobom viac času ako predtým, 792 00:35:41,747 --> 00:35:44,830 ale keď sme to urobili v reálnom čase, budeme vidieť, čo takeaways bude. 793 00:35:44,830 --> 00:35:47,970 A teraz som tu, že jo polovica pravej polovici, 794 00:35:47,970 --> 00:35:50,170 nechaj ma ísť napred a zoradiť ľavú polovicu. 795 00:35:50,170 --> 00:35:51,482 Krok vpred, Ako sa voláte? 796 00:35:51,482 --> 00:35:52,190 DIVÁKOV: Ramsey. 797 00:35:52,190 --> 00:35:53,210 SPEAKER: Ramsey je teraz radené. 798 00:35:53,210 --> 00:35:53,570 Ako sa voláte? 799 00:35:53,570 --> 00:35:54,200 >> DIVÁKOV: Marina. 800 00:35:54,200 --> 00:35:57,033 >> SPEAKER: Marina je teraz radené ako dobre, ak budete mať o jeden krok vpred. 801 00:35:57,033 --> 00:36:00,690 Kľúčovým krokom je tu teraz zlúčiť, som bude trhať zo svojich dvoch zoznamov, 802 00:36:00,690 --> 00:36:01,720 vľavo a vpravo. 803 00:36:01,720 --> 00:36:05,150 Päť bude na prvom mieste, a sedem sa chystá prísť ďalšie. 804 00:36:05,150 --> 00:36:06,410 A opäť, je to zámerné. 805 00:36:06,410 --> 00:36:08,535 Skutočnosť, že užívate kroky vpred a vzad 806 00:36:08,535 --> 00:36:12,997 má predstavovať, že nemôžeme do tohto algoritmu na mieste, ako ľahko 807 00:36:12,997 --> 00:36:15,830 ako bublinkové triedenie a výberu druhu, a vloženie triedenie, kde sa práve 808 00:36:15,830 --> 00:36:16,960 stále vymieňať ľudí. 809 00:36:16,960 --> 00:36:19,940 Doslova som potrebovať akúsi poškriabaniu papiera, v ktorom 810 00:36:19,940 --> 00:36:21,827 aby týchto ľudí keď som to zlúčenie, 811 00:36:21,827 --> 00:36:23,410 a potom som ich dať späť na miesto. 812 00:36:23,410 --> 00:36:27,260 A to je kľúč, pretože ja som s použitím nové zdroje, priestor, a to nielen čas. 813 00:36:27,260 --> 00:36:28,270 >> OK, to je úžasné. 814 00:36:28,270 --> 00:36:32,050 Ľavá polovica je triedený, pravá polovica je triedené, teraz ten kľúč zlúčenie krok. 815 00:36:32,050 --> 00:36:33,450 Ako to mám zlúčiť to? 816 00:36:33,450 --> 00:36:35,470 Takže ak budete nasledovať moje ľavá ruka a pravá ruka, 817 00:36:35,470 --> 00:36:38,930 Chystám sa ukázať svoju ľavú ruku na ľavej polovici, moja pravá ruka 818 00:36:38,930 --> 00:36:42,680 v pravej polovici, a teraz musím rozhodnúť, krok za krokom, ktorého sa zlúčia. 819 00:36:42,680 --> 00:36:44,650 Kto samozrejme na prvom mieste? 820 00:36:44,650 --> 00:36:45,150 Číslo jedna. 821 00:36:45,150 --> 00:36:47,327 Tak poď sem, tu je náš poznámkový blok. 822 00:36:47,327 --> 00:36:49,910 Takže teraz číslo jedna a oznámenia čo budem robiť s mojou pravou rukou, 823 00:36:49,910 --> 00:36:54,152 Chystám sa hýbať pravou rukou jedného krokom sa k bodu číslo tri, 824 00:36:54,152 --> 00:36:55,860 a teraz mám urobiť Rovnaké rozhodnutie. 825 00:36:55,860 --> 00:36:58,387 A vlastne stojí priamo v predné Lukáša tu, ak by ste mohli, 826 00:36:58,387 --> 00:36:59,720 pretože to je náš poznámkový blok. 827 00:36:59,720 --> 00:37:00,610 Tak kto je ďalší? 828 00:37:00,610 --> 00:37:05,000 Máme Luke s číslom dve alebo Chris s číslom tri. 829 00:37:05,000 --> 00:37:07,460 Je zrejmé, Luke, číslo dva, takže sa sem. 830 00:37:07,460 --> 00:37:11,270 >> Ale moja ľavá ruka teraz sa chystá byť zvýšený poukázať na Darrena, 831 00:37:11,270 --> 00:37:15,160 a tu je kľúč odniesť s zlúčenie, budem v tom pokračovať, 832 00:37:15,160 --> 00:37:17,340 Je zrejmé, že ak máte trochu o sledovať logiku. 833 00:37:17,340 --> 00:37:19,670 Ale moje ruky nikdy ísť späť, 834 00:37:19,670 --> 00:37:23,861 čo znamená, že som len niekedy sťahujú do odišiel s mojím proces zlúčenia, 835 00:37:23,861 --> 00:37:26,360 a že to bude kľúčom k naša analýza za chvíľu. 836 00:37:26,360 --> 00:37:27,859 >> Takže teraz poďme dokončiť rýchlo hore. 837 00:37:27,859 --> 00:37:31,650 Takže tri príde nabudúce, potom štyri príde nabudúce, 838 00:37:31,650 --> 00:37:38,750 a teraz päť príde nabudúce, potom šesť, a sedem a nakoniec osem. 839 00:37:38,750 --> 00:37:42,960 Cítim sa ako najpomalší algoritmus ešte, ale nie v prípade, vlastne 840 00:37:42,960 --> 00:37:45,510 nechajte ho bežať na rovnakom druhu o taktovaciu frekvenciu, takže sa 841 00:37:45,510 --> 00:37:48,106 hovoriť, s rovnakým tikajúce hodiny ako predtým. 842 00:37:48,106 --> 00:37:48,605 Prečo? 843 00:37:48,605 --> 00:37:51,100 No, poďme sa sa pozrieť na konečný výsledok. 844 00:37:51,100 --> 00:37:56,990 >> Vráťme sa tu, dovoľte mi, aby som vytiahnuť demonštrácii vizuálne 845 00:37:56,990 --> 00:37:59,030 z toho, čo sme práve urobili. 846 00:37:59,030 --> 00:38:06,110 Zväčšenie tu, na tomto strana tu, hovorí Firefox 847 00:38:06,110 --> 00:38:08,200 že chceme do fronty v tomto poli, poďme 848 00:38:08,200 --> 00:38:11,260 hovoria bublina druh, s ktorým teraz sme dobre oboznámení, 849 00:38:11,260 --> 00:38:14,130 Výber triedenie, čo je ďalší pomerne priamočiara, 850 00:38:14,130 --> 00:38:18,250 a teraz dnešné merge sort, ktorý bude naša vrcholná koniec. 851 00:38:18,250 --> 00:38:21,530 Dôvod, prečo to trvalo tak dlho tu s ľuďmi a ja slovne ich, 852 00:38:21,530 --> 00:38:23,480 samozrejme, ja som vysvetľovať každý krok. 853 00:38:23,480 --> 00:38:26,920 Ale ak ste jednoducho spustite tento, moc ako sme to urobili bubble sort a výber 854 00:38:26,920 --> 00:38:30,890 triediť nielen vizuálne, hodinky ako oveľa efektívnejšie 855 00:38:30,890 --> 00:38:33,330 to presadzovaním delenie a dobývanie 856 00:38:33,330 --> 00:38:39,150 môže byť pri aplikácii do dátového súboru, ktorý je Ani veľkosť osem, ale ešte oveľa, 857 00:38:39,150 --> 00:38:39,970 oveľa väčšie. 858 00:38:39,970 --> 00:38:44,585 Dám vám zlúčiť druh, vedľa strana s týmito ďalšími algoritmami. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 To dostane bolestivé rýchlo, a koniec 861 00:38:58,530 --> 00:39:00,890 nie je nijak zvlášť vrcholná, jednoducho skončiť radené. 862 00:39:00,890 --> 00:39:05,280 Ale kľúč odniesť je, že Pozri sa, ako ďaleko rýchlejšie zlúčiť druh 863 00:39:05,280 --> 00:39:08,110 bol, ak si myslíte, že som len tak si s vami. 864 00:39:08,110 --> 00:39:13,100 Ak sa nám tento jeden posledný čas, poďme znovu to, vráťme 865 00:39:13,100 --> 00:39:14,960 a vyberte bubliny druhu, a len tak pre srandu, 866 00:39:14,960 --> 00:39:17,330 Zvoľme vloženie triedenie, len pre istotu. 867 00:39:17,330 --> 00:39:20,020 A tentoraz opäť, poďme vyberte zlučovacie druh a poďme 868 00:39:20,020 --> 00:39:21,595 vlastne spustiť tieto bok po boku. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> A to nie je, v skutočnosti, náhoda. 871 00:39:26,930 --> 00:39:31,140 Čo som skutočne urobil je, že som rozdeliť svoj vstup na polovicu, opäť 872 00:39:31,140 --> 00:39:32,240 a znovu a znovu. 873 00:39:32,240 --> 00:39:35,590 A je to len toľkokrát môžete rozdeliť váš vstup do polovice, ľavá 874 00:39:35,590 --> 00:39:36,240 a vpravo. 875 00:39:36,240 --> 00:39:39,425 Aký je vzorec, ktorý držíme vidieť , Ktorý opisuje rozdelenie na dve polovice 876 00:39:39,425 --> 00:39:41,050 znova a znova, a znova, a znova? 877 00:39:41,050 --> 00:39:41,890 >> Divákov: log n. 878 00:39:41,890 --> 00:39:42,760 >> SPEAKER: log n. 879 00:39:42,760 --> 00:39:46,300 Ale potom je tu ešte jedna ďalší kľúčový krok, Tento algoritmus nie je nahlásená n krokov. 880 00:39:46,300 --> 00:39:48,992 Ak by bolo len prihlásiť n krokov, by sme byť v rovnakom probléme 881 00:39:48,992 --> 00:39:51,200 ako predtým, kde nemôže byť že všetko je triediť. 882 00:39:51,200 --> 00:39:54,480 Musíte sa minimálne pozrieť na n prvkov byť istí, že n prvky sú triedené, 883 00:39:54,480 --> 00:39:55,950 inak je to skok viery. 884 00:39:55,950 --> 00:39:59,810 >> Takže je to minimálne log n kroky, ale čo tejto kľúčovej zlúčenie kroku 885 00:39:59,810 --> 00:40:04,370 kde som sa spojil moje ľavá polovica a doprava polovice a prešiel cez javisko? 886 00:40:04,370 --> 00:40:06,980 Koľko krokov je zlúčiť? 887 00:40:06,980 --> 00:40:10,150 Je to n, ale neurobil som to len zlúčiť konečný čas. 888 00:40:10,150 --> 00:40:15,089 Na každej z týchto vnorených volaní, na každom z týchto vnorených zlučovanie, napriek tomu som radené. 889 00:40:15,089 --> 00:40:18,380 Aj zlúčil tieto dva chlapíkov, potom sa tieto dve chlapci, potom títo dvaja, a tak ďalej. 890 00:40:18,380 --> 00:40:19,955 >> Tak som sa zlúčenie znova a znova. 891 00:40:19,955 --> 00:40:20,580 Koľkokrát? 892 00:40:20,580 --> 00:40:23,510 Takže zakaždým, keď som sa rozdelil zoznam na polovicu, som zlúčenie. 893 00:40:23,510 --> 00:40:25,460 Rozdeľte zoznam na dve polovice, do zlúčenia. 894 00:40:25,460 --> 00:40:28,570 Takže v prípade, delenie zoznam môže byť vykonané log n krát, 895 00:40:28,570 --> 00:40:33,880 a zlúčenie nakoniec sa n kroky, čo by mohlo byť teraz horný 896 00:40:33,880 --> 00:40:37,000 viazaná na chod Doba nášho algoritmu? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> A vskutku, to je to, čo sme tu dosiahli. 899 00:40:40,560 --> 00:40:44,650 Takže myslíte, že ste vidieť vizuálne, keď tieto tri veci bežia bok po boku 900 00:40:44,650 --> 00:40:47,930 je n na druhú proti n na druhú proti n log n. 901 00:40:47,930 --> 00:40:51,010 Ktoré zásadným uvidíme, nielen dnes, ale v budúcnosti, 902 00:40:51,010 --> 00:40:52,760 je oveľa, oveľa rýchlejšie. 903 00:40:52,760 --> 00:40:56,010 Potlesk pre týchto ľudí, Ja sa za to odmení Antistresové loptičky. 904 00:40:56,010 --> 00:41:00,260 Poďme odložiť dnes, a Vás budeme vidieť v pondelok. 905 00:41:00,260 --> 00:41:02,255