1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> SPEAKER: Dobře, to je CS50. 3 00:00:14,910 --> 00:00:19,020 To je konec tří týdnů, a pokud jste využili již 4 00:00:19,020 --> 00:00:21,790 vědět, že tam bude oběd tento pátek jako obvykle, kde 5 00:00:21,790 --> 00:00:25,430 můžete nyní dobrý rozhovor a jídlo na ohně a ledu 6 00:00:25,430 --> 00:00:27,980 s některými CS50 je Zaměstnanci a spolužáci. 7 00:00:27,980 --> 00:00:30,170 Vydejte se na této adrese zde. 8 00:00:30,170 --> 00:00:33,420 >> Nyní si můžete připomenout, nebo může brzy být seznámen s, 9 00:00:33,420 --> 00:00:35,970 tyto věci, která sem jsou uvedeny na konci 10 00:00:35,970 --> 00:00:37,850 semestru pro mnoho tříd. 11 00:00:37,850 --> 00:00:40,870 Takzvaná zkouška modré knihy, ve které můžete psát své odpovědi na zkoušky. 12 00:00:40,870 --> 00:00:44,240 Teď mám tu 26 jako modré knihy, na každý z nich 13 00:00:44,240 --> 00:00:47,580 je napsáno jméno, až Z. A opravdu jména jsou tak jednoduché, 14 00:00:47,580 --> 00:00:50,490 díky Z. A jeden z cíle na dosah ruky dnes 15 00:00:50,490 --> 00:00:53,910 bude pokračovat v co jsme začali v pondělí, což není 16 00:00:53,910 --> 00:00:57,830 tak při pohledu na kód, ale ve skutečnosti při pohledu na nápady a řešení problémů. 17 00:00:57,830 --> 00:01:00,170 Jedním z cílů a sliby tohoto kurzu 18 00:01:00,170 --> 00:01:02,985 je, aby vás naučí myslet více opatrně, více metodicky, 19 00:01:02,985 --> 00:01:05,400 a efektivněji řešit problémy. 20 00:01:05,400 --> 00:01:09,526 A skutečně, můžeme to udělat opravdu aniž byste se dotkli jediného řádku kódu. 21 00:01:09,526 --> 00:01:12,150 Takže mám pár slonů tady dnes, oranžové a modré, 22 00:01:12,150 --> 00:01:15,780 pokud bychom se mohli dostat jednoho dobrovolníka, možná z větší zpátky, než je obvyklé. 23 00:01:15,780 --> 00:01:18,070 Jak se asi tady, pojď dolů. 24 00:01:18,070 --> 00:01:24,180 Jehož cílem bude, aby pomoci a navíc spravovat tuto zkoušku tady. 25 00:01:24,180 --> 00:01:24,935 Jak se jmenujete? 26 00:01:24,935 --> 00:01:25,768 >> Diváků: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 SPEAKER: Mary Beth, pojď nahoru. 28 00:01:27,560 --> 00:01:29,560 Dovolte mi, abych se mikrofon tu pro vás. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Těší mě. 31 00:01:32,880 --> 00:01:34,005 >> Diváků: Těší mě. 32 00:01:34,005 --> 00:01:36,790 SPEAKER: Dobře, takže mám zde modré knihy A až Z, 33 00:01:36,790 --> 00:01:41,680 a budu předstírat, že Mám jeden ze studentů, 34 00:01:41,680 --> 00:01:45,770 a oni přicházejí poněkud náhodně na konci tři hodiny zkouška bloku, 35 00:01:45,770 --> 00:01:49,400 tak oni skončí v některé semi-náhodné pořadí takhle. 36 00:01:49,400 --> 00:01:54,510 Nyní svou práci za chvíli bude na bylo-- to je vlastně, jak se dostat 37 00:01:54,510 --> 00:01:56,820 obrátil na konci roku třídy, s největší pravděpodobností. 38 00:01:56,820 --> 00:02:01,120 Vaším úkolem nyní bude zcela Jednoduše řečeno, třídit tyto modré knihy pro 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ÁKŮ: Oh, to je bude trvat věčně. 41 00:02:08,400 --> 00:02:13,747 >> SPEAKER: A budeme sledovat jak to uděláte, žádný tlak. 42 00:02:13,747 --> 00:02:15,330 DIVÁKŮ: Ne, žádný tlak nebo tak něco. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> SPEAKER: A pro zábavu, pojďme dát časovač. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> Diváků: Tolik legrace, tolik legrace. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> SPEAKER: Můžu držet mikrofon pro vás. 49 00:02:38,574 --> 00:02:40,240 Dobře, právě jsme zdvojnásobili naši rychlost. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Takže do té doby, dovolte mi, abych představovat, co je bude otázka pro Mary Beth 52 00:02:49,060 --> 00:02:51,540 je to, co dělá, jak je že jde o řešení tohoto? 53 00:02:51,540 --> 00:02:54,040 A ve skutečnosti, možná nebudete mít někdy přemýšleli o něčem 54 00:02:54,040 --> 00:02:57,440 tak jednoduché, jako když si vyberete až 26 knih, jako je tento, 55 00:02:57,440 --> 00:02:59,350 které mají přírodní objednání k nim. 56 00:02:59,350 --> 00:03:01,335 Jaký je proces že jste skutečně používat? 57 00:03:01,335 --> 00:03:03,770 Je to docela náhodně jen vybírání první uvidíte 58 00:03:03,770 --> 00:03:05,250 a uvedení na svém místě? 59 00:03:05,250 --> 00:03:09,680 Myslíte si nejprve přesunout své ruce kolem Hledáme pak hledal B? 60 00:03:09,680 --> 00:03:11,722 Myslíte si, podívejte se na pár z nich vedle sebe 61 00:03:11,722 --> 00:03:14,680 a jen řekl, počkej, to není v pořádku, a pak vyměnit pořadí? 62 00:03:14,680 --> 00:03:16,960 Již jsme viděli v pondělí že existuje řada způsobů, jak 63 00:03:16,960 --> 00:03:22,140 ve kterém můžeme udělat, a opravdu, jak jsme u konce tady, 64 00:03:22,140 --> 00:03:26,360 Chtěl bych vzít na vědomí možná z čeho Mary Beth dělá. 65 00:03:26,360 --> 00:03:30,040 Máme několik hromádek zdá se, Větší z nich, tři menší. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> Diváků: Já je objednání když jsem si dva dopisy 68 00:03:36,415 --> 00:03:39,540 že vím, že jsou spolu v pořadí, Dal jsem je dohromady tak, že se mi nelíbí 69 00:03:39,540 --> 00:03:42,915 muset starat o udržení track z celé řady knih. 70 00:03:42,915 --> 00:03:45,706 Je to jen, ach, je první, Mám tento stoh zde. 71 00:03:45,706 --> 00:03:47,580 SPEAKER: Takže, skoro jako puzzle kousky, které 72 00:03:47,580 --> 00:03:49,860 mít správný tvar na shodovat s navzájem. 73 00:03:49,860 --> 00:03:51,026 DIVÁKŮ: Docela hodně, jo. 74 00:03:51,026 --> 00:03:55,320 SPEAKER: OK, výborná. 75 00:03:55,320 --> 00:03:59,850 A teď každá z nich hromady je pravděpodobně řazeny? 76 00:03:59,850 --> 00:04:00,990 >> Hlediště: Ano. 77 00:04:00,990 --> 00:04:09,900 >> SPEAKER: Dobře, díky Z. Vše Dobře, gratuluji, jste to udělal. 78 00:04:09,900 --> 00:04:11,461 Máte možnost volby. 79 00:04:11,461 --> 00:04:11,960 Modrá? 80 00:04:11,960 --> 00:04:13,530 Dobře, děkuji vám za to. 81 00:04:13,530 --> 00:04:16,679 Takže Mary Beth se navrhnout co její přístup byl, 82 00:04:16,679 --> 00:04:19,720 ale to, co je jiný přístup, jak na Vás může jít o třídění těchto věcí? 83 00:04:19,720 --> 00:04:21,130 Co by jste udělali? 84 00:04:21,130 --> 00:04:24,060 Záznam porazit by bylo jednu minutu a 50 sekund, nebo tak, 85 00:04:24,060 --> 00:04:26,039 plus ty, které jsem zapomněl počítat. 86 00:04:26,039 --> 00:04:27,080 Co by jste udělali? 87 00:04:27,080 --> 00:04:27,579 Jo? 88 00:04:27,579 --> 00:04:28,735 Diváků: Vezměte stoh papírů. 89 00:04:28,735 --> 00:04:29,776 Od začátku. 90 00:04:29,776 --> 00:04:32,284 Zkontrolujte, zda vaše dokumenty. 91 00:04:32,284 --> 00:04:36,586 A v případě, že horní z nich je vyšší než, možná, že jsou 92 00:04:36,586 --> 00:04:38,980 spodní z nich je vyšší, pak nimi přepínat. 93 00:04:38,980 --> 00:04:41,300 >> SPEAKER: OK, tak začíná V horní a spodní části, 94 00:04:41,300 --> 00:04:43,716 a pracovní cestu dovnitř jako to, že je vymění? 95 00:04:43,716 --> 00:04:46,580 OK, tak málo podobný duchem bublinkové druhu, 96 00:04:46,580 --> 00:04:49,160 ale volba extrémy nejsou přilehlé páry. 97 00:04:49,160 --> 00:04:52,080 Ale krátké na to, že je tu jistě spoustu různých způsobů, 98 00:04:52,080 --> 00:04:54,210 bychom to mohli udělat, a Upřímně řečeno, myslím, že tak nějak 99 00:04:54,210 --> 00:04:55,700 přijal pár přístupy, ne? 100 00:04:55,700 --> 00:05:00,567 Udělal jsi něco jako čtyři tříděných piloty a pak efektivně spojil dohromady. 101 00:05:00,567 --> 00:05:02,650 A to je, troufám říct, další technika dohromady. 102 00:05:02,650 --> 00:05:06,950 Vy jste to brát to jako jedna velká hromada, můžete rozdělit problém do čtyř čtyřkolky, 103 00:05:06,950 --> 00:05:09,820 chcete-li, a pak se nějakým způsobem spojil je do konce. 104 00:05:09,820 --> 00:05:13,410 >> Takže pojďme zvážit, nakonec, Jak jinak bychom mohli udělat. 105 00:05:13,410 --> 00:05:15,860 Formalizované jsme pojem bublinkové třídění minule, 106 00:05:15,860 --> 00:05:18,780 a bubble sort odvolání bylo Algoritmus, který jsme vizualizovány 107 00:05:18,780 --> 00:05:22,640 s osmi svými spolužáky se zde, zdánlivě náhodně řazeny na prvním místě. 108 00:05:22,640 --> 00:05:26,110 A pak jsme se rozhodli po dvou, pokud dva prvky jsou mimo provoz, 109 00:05:26,110 --> 00:05:26,950 prostě je vyměnit. 110 00:05:26,950 --> 00:05:28,930 Takže čtyři a dvě zřejmě mimo provoz, 111 00:05:28,930 --> 00:05:31,080 Takže ti dva spolužáci přepnout pozice. 112 00:05:31,080 --> 00:05:35,390 A pak jsme se opakuje se čtyřmi a šesti, pak šest a osm, na každé iteraci, 113 00:05:35,390 --> 00:05:36,980 pohybující se doprava. 114 00:05:36,980 --> 00:05:42,590 >> Takže vzhledem k tomu osm lidí, kolik pairwise srovnání jsem udělal při chůzi od 115 00:05:42,590 --> 00:05:45,220 zleva doprava v jednom takovém iteraci? 116 00:05:45,220 --> 00:05:48,410 Kolik srovnání? 117 00:05:48,410 --> 00:05:49,197 Sedm, že jo? 118 00:05:49,197 --> 00:05:51,405 Vzhledem k tomu, jestli je osm lidé, ale máte pár 119 00:05:51,405 --> 00:05:53,880 ně a dál jeden hop na pravé straně, 120 00:05:53,880 --> 00:05:56,060 nebudeš mít osm srovnání, protože nemůžete porovnat 121 00:05:56,060 --> 00:05:59,226 prvek proti sobě, nebo by jen zbytečné, takže budete mít sedm. 122 00:05:59,226 --> 00:06:01,290 Nebo obecněji, pokud máme n lidi, jsme 123 00:06:01,290 --> 00:06:04,300 do n minus 1 srovnání bublinkové druhu. 124 00:06:04,300 --> 00:06:08,150 >> Takže uvažujme nyní, jak dobrý nebo špatný bubble sort vlastně byl, a zkuste 125 00:06:08,150 --> 00:06:13,570 aby sami slovní zásobu které k posudku algoritmů, jako je tento, 126 00:06:13,570 --> 00:06:14,430 a brzy se naše vlastní. 127 00:06:14,430 --> 00:06:16,970 Takže prvním průchodu bublina druh, poprvé 128 00:06:16,970 --> 00:06:20,909 Šel jsem zleva doprava přes etapa, vzal mě n mínus 1 srovnání. 129 00:06:20,909 --> 00:06:22,950 A to bude můj měrná jednotka, ne? 130 00:06:22,950 --> 00:06:26,170 Byl jsem trochu mluvit a procházky, poněkud rychle, poněkud pomalý, 131 00:06:26,170 --> 00:06:29,300 takže počítání moje číslo v sekundách není zvláště říká, 132 00:06:29,300 --> 00:06:32,260 ale spočítáním operace, které jsem dělal v pondělí, 133 00:06:32,260 --> 00:06:35,900 porovnání dvou lidí, že se cítí jako pěkný měrnou jednotku. 134 00:06:35,900 --> 00:06:40,980 >> Tak n minus 1 krok poprvé, ale potom, co se stalo potom? 135 00:06:40,980 --> 00:06:46,610 Co je to jeden vzhůru na jeden průchod přes jinak netříděného seznamu? 136 00:06:46,610 --> 00:06:49,840 Co mi můžete říct o prvek který byl po celou cestu tam? 137 00:06:49,840 --> 00:06:51,300 Jo? 138 00:06:51,300 --> 00:06:52,870 To byl největší prvek, ne? 139 00:06:52,870 --> 00:06:55,710 Číslo osm, i když zde začala, pokaždé, když jsem 140 00:06:55,710 --> 00:06:57,860 ve srovnání s ní proti soused, pořád 141 00:06:57,860 --> 00:07:00,480 vyvěrá na pravé straně straně seznamu. 142 00:07:00,480 --> 00:07:02,710 A vskutku, to je místo, kde algoritmus dostane jeho jméno. 143 00:07:02,710 --> 00:07:07,630 >> Právě tímto logiky, kolik srovnání Potřebuji, aby na podruhé 144 00:07:07,630 --> 00:07:09,800 Dělám, že přihrávku zleva doprava? 145 00:07:09,800 --> 00:07:10,730 n minus 2, ne? 146 00:07:10,730 --> 00:07:14,297 Bylo by to plýtvání mým časem, kdybych udržet porovnání osm proti někomu, 147 00:07:14,297 --> 00:07:16,630 jiného, ​​protože už víme, byla na správném místě. 148 00:07:16,630 --> 00:07:19,760 Takže je to trochu optimalizace, takže další průchod 149 00:07:19,760 --> 00:07:23,899 bude navíc n minus dva kroky, kde n je počet osob. 150 00:07:23,899 --> 00:07:26,940 Nyní můžete trochu extrapolovat, a to i pokud nejste počítačový odborník, 151 00:07:26,940 --> 00:07:27,680 jak to skončí. 152 00:07:27,680 --> 00:07:31,259 Na konci tohoto algoritmu, pravděpodobně máte jen jeden srovnání odešel. 153 00:07:31,259 --> 00:07:33,800 Musíte se trochu opravit začátku seznamu v případě, že dva 154 00:07:33,800 --> 00:07:36,540 a jedna jsou mimo pořadí a měla by být jedna a dvě, 155 00:07:36,540 --> 00:07:40,330 tak to doraz na plus 1 v konečném znění porovnání. 156 00:07:40,330 --> 00:07:44,500 >> Nyní je tečka, tečka, tečka druh vln je ruce na některé šťavnatější podrobnosti 157 00:07:44,500 --> 00:07:46,452 ale pojďme prostě jít dopředu a zjednodušit. 158 00:07:46,452 --> 00:07:48,660 Pokud si vzpomínáte z vysoce Škola, upřímně řečeno, mnoho z vás 159 00:07:48,660 --> 00:07:50,340 měli matematické knihy, které měly malý tahák 160 00:07:50,340 --> 00:07:52,550 na přední straně obálky nebo zadní kryt, který vám ukázal, 161 00:07:52,550 --> 00:07:56,400 co série součtů jako to nakonec přidal až. 162 00:07:56,400 --> 00:07:59,600 V obecném případě, máte-li variabilní, jako n, a ve skutečnosti to jeden, 163 00:07:59,600 --> 00:08:01,634 pokud jste se podívali na vaše old school math knihy, 164 00:08:01,634 --> 00:08:04,050 byste vidět, že to ve skutečnosti přidává do této částky zde 165 00:08:04,050 --> 00:08:07,970 n krát n minus 1 vše děleno 2. 166 00:08:07,970 --> 00:08:11,172 Takže teď mi dovolte stanoví je to pravda, tak na skok víry, 167 00:08:11,172 --> 00:08:12,880 to je to, co to vystihuje až, a my jsme mohli 168 00:08:12,880 --> 00:08:14,341 dokázat, že v obecnějším případě. 169 00:08:14,341 --> 00:08:15,590 Ale teď pojďme rozšířit to. 170 00:08:15,590 --> 00:08:19,920 Takže pojďme se množí na to, aby je n na druhou, mínus n, vše děleno 2. 171 00:08:19,920 --> 00:08:23,200 To je opravdu n na druhou, děleno 2, minus n na 2, 172 00:08:23,200 --> 00:08:25,010 tak to je všechno pěkné a zajímavé. 173 00:08:25,010 --> 00:08:27,060 Ale co se stane, když Nyní plug-in v hodnotě? 174 00:08:27,060 --> 00:08:29,724 Dejme tomu, že jsem neměl osm lidé, ale říkají milionu. 175 00:08:29,724 --> 00:08:31,890 A miliony jen proto, že to je docela velké číslo, 176 00:08:31,890 --> 00:08:34,039 pojďme zástrčka, že v roce, a uvidíme, co se stane. 177 00:08:34,039 --> 00:08:39,039 Takže když jsem plug milionů do tohoto vzorce Jdu si milion na druhou, 178 00:08:39,039 --> 00:08:42,868 děleno 2, minus milionů, děleno 2. 179 00:08:42,868 --> 00:08:44,159 A teď, co to jde, aby se rovnala? 180 00:08:44,159 --> 00:08:47,354 Takže 500 miliard, minus 500.000. 181 00:08:47,354 --> 00:08:49,270 A když jsem vlastně dělat že matematika, znamená to, 182 00:08:49,270 --> 00:08:53,920 že třídění milion lidé s bubliny druhu 183 00:08:53,920 --> 00:09:01,800 mi může trvat 499999500000 kroky nebo srovnání na konci, 184 00:09:01,800 --> 00:09:02,900 jsme jen extrapolace. 185 00:09:02,900 --> 00:09:06,860 >> Že se cítí docela pomalu, ale upřímně řečeno, měření jedné konkrétní vstup 186 00:09:06,860 --> 00:09:09,160 jako je toto, není všechno, že to řekl. 187 00:09:09,160 --> 00:09:14,050 Ale ve skutečnosti to naznačuje, že pro n dostane větší a větší, tento algoritmus 188 00:09:14,050 --> 00:09:16,280 druh cítí hůř a horší, nebo opravdu 189 00:09:16,280 --> 00:09:20,450 začnete cítit bolest, která umocňování, že n na druhou, 190 00:09:20,450 --> 00:09:21,770 který sčítá docela rychle. 191 00:09:21,770 --> 00:09:25,340 A to detail není ztratil na lidi, ve skutečnosti 192 00:09:25,340 --> 00:09:29,640 před několika lety jistý senátor, který byl kampaně, sedl si na pohovor 193 00:09:29,640 --> 00:09:32,180 s Google Eric Schmidt, CEO v té době, 194 00:09:32,180 --> 00:09:36,380 a byl napadán s otázkou stejně jako jsme zkoumání dnes. 195 00:09:36,380 --> 00:09:38,468 Pojďme se podívat. 196 00:09:38,468 --> 00:09:45,280 >> [PŘEHRÁVÁNÍ] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Že jsi tady na Google, a líbí se mi 198 00:09:48,560 --> 00:09:53,382 myslet na předsednictví jako pracovní pohovor. 199 00:09:53,382 --> 00:09:56,434 Nyní je těžké se dostat zaměstnání jako prezident, 200 00:09:56,434 --> 00:09:58,100 a jdete přes nástrahami teď. 201 00:09:58,100 --> 00:10:01,860 Je to také těžké získat práci ve společnosti Google. 202 00:10:01,860 --> 00:10:05,490 Máme otázky, a my zeptejte Naši kandidáti otázky, 203 00:10:05,490 --> 00:10:09,770 a tohle je od Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 Co-- vy myslíte, že jsem Děláš si srandu, že je to tady. 205 00:10:14,760 --> 00:10:17,930 Jaký je nejúčinnější způsob, jak seřadit milion 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 >> -Promiňte, Maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Ne, ne, ne. 210 00:10:27,400 --> 00:10:30,700 Myslím si, že bublina druh by byl špatný způsob, jak jít. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> No tak, kdo mu to řekl? 213 00:10:38,180 --> 00:10:40,590 Neviděl jsem počítač věda v pozadí. 214 00:10:40,590 --> 00:10:42,130 >> -Musíme Naše zvědy tam. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Pojďme se zeptat jiný rozhovor otázka. 217 00:10:48,444 --> 00:10:49,300 >> [END VIDEOPŘEHRÁVÁNÍ] 218 00:10:49,300 --> 00:10:52,290 >> SPEAKER: Tak mluví o Konkrétní čísla však 219 00:10:52,290 --> 00:10:53,890 se nebude všechno užitečné. 220 00:10:53,890 --> 00:10:56,810 Nejedná se o životní lekci, že bublina třídění, vzhledem k tomu milion vstupů, 221 00:10:56,810 --> 00:10:58,590 může trvat tolik jako 500 miliard kroky. 222 00:10:58,590 --> 00:11:01,120 Nemůžete opravdu zobecnit příliš účinně od 223 00:11:01,120 --> 00:11:03,560 a činit správná rozhodnutí návrhu při psaní programů. 224 00:11:03,560 --> 00:11:07,070 Takže pojďme se zaměřit na to, jak by můžeme zjednodušit tento výsledek. 225 00:11:07,070 --> 00:11:11,780 >> Tak jsem se zvýrazní žlutě zde výsledkem n na druhou děleno 2, 226 00:11:11,780 --> 00:11:14,330 tak milion na druhou děleno 2, a poté 227 00:11:14,330 --> 00:11:16,710 Jsem zvýrazní to, co konečná odpověď byla 228 00:11:16,710 --> 00:11:20,180 jakmile jsme se odečte z n děleno 2. 229 00:11:20,180 --> 00:11:24,850 A tvrzení, budu nyní dělat, je kdo sakra zajímá, jestli si odečíst z 230 00:11:24,850 --> 00:11:30,060 trochu starý n na 2, kdy první Součástí tohoto vzorce je tak mnohem větší? 231 00:11:30,060 --> 00:11:33,910 Je dominantou druhé Termín, n na druhou děleno 2 232 00:11:33,910 --> 00:11:37,510 je tak mnohem větší, jasně, jak n dostane velký jako milión, 233 00:11:37,510 --> 00:11:41,450 to je opravdu velký rozdíl v konec dne mezi 500000000000 234 00:11:41,450 --> 00:11:45,730 a 499999500000? 235 00:11:45,730 --> 00:11:46,349 Ne tak docela. 236 00:11:46,349 --> 00:11:48,640 A tak to, co budeme dělat, co počítačoví odborníci se 237 00:11:48,640 --> 00:11:53,270 ignorovat ty nižšího řádu podmínky a se něco takového a opravdu 238 00:11:53,270 --> 00:11:56,050 jen zjednodušit na termín, který to bude jedno. 239 00:11:56,050 --> 00:12:00,315 Větší naše soubory dat, tím větší Naše databáze získat, tím více webových stránek 240 00:12:00,315 --> 00:12:02,690 musíme hledat, více přátelé máte na Facebooku. 241 00:12:02,690 --> 00:12:07,340 >> Jako n zvětšuje, jsme opravdu bude se starat o největší 242 00:12:07,340 --> 00:12:11,560 Výraz v každé takové analýze naše algoritmy výkon. 243 00:12:11,560 --> 00:12:16,230 A já jsem chtěl říct, že víš, co, bubble sort je na objednávku velký O, 244 00:12:16,230 --> 00:12:18,060 na pořadí n na druhou. 245 00:12:18,060 --> 00:12:20,090 Není to zrovna n na druhou, jak jsme viděli, 246 00:12:20,090 --> 00:12:22,060 ale kdo opravdu zajímá o těch menších podmínkách, 247 00:12:22,060 --> 00:12:24,390 a upřímně řečeno, kdo opravdu zajímá, jestli budeme dělit dvě? 248 00:12:24,390 --> 00:12:25,870 To je jen konstantní faktor. 249 00:12:25,870 --> 00:12:29,480 A 500 miliard ve srovnání s 250 miliard opravdu tak velký problém? 250 00:12:29,480 --> 00:12:32,190 Jsem mohl jen čekat jeden rok, nechat notebook doslova 251 00:12:32,190 --> 00:12:34,810 se dvakrát tak rychle v hardwaru, a že tak nějak rozdíl 252 00:12:34,810 --> 00:12:36,650 prostě zmizí přirozeně v průběhu času. 253 00:12:36,650 --> 00:12:39,300 >> To, co zajímá je výraz, část 254 00:12:39,300 --> 00:12:42,489 výrazu, že se to liší jako náš vstup dostane větší a větší. 255 00:12:42,489 --> 00:12:45,280 A skutečně, v reálném světě, to je to, co se děje dál 256 00:12:45,280 --> 00:12:48,330 Je vstupy do našich problémů a algoritmy jsou stále větší. 257 00:12:48,330 --> 00:12:53,470 Tak velký O bude zápis, asymptotické notace, který jsme právě 258 00:12:53,470 --> 00:12:57,160 použít jako počítačoví odborníci popsat výkon, nebo čas běží, 259 00:12:57,160 --> 00:12:58,130 algoritmu. 260 00:12:58,130 --> 00:13:00,800 Takže můžeme porovnávat algoritmy na různých počítačích písemných 261 00:13:00,800 --> 00:13:04,170 různými lidmi, s použitím některé zásadně podobné metriky 262 00:13:04,170 --> 00:13:07,557 jako je počet porovnání jste dělat, nebo možná počet swapů 263 00:13:07,557 --> 00:13:08,140 děláte. 264 00:13:08,140 --> 00:13:11,910 >> Co my nebudeme počet je množství času, 265 00:13:11,910 --> 00:13:13,981 , který prochází na hodiny na stěně typicky. 266 00:13:13,981 --> 00:13:16,230 Co my nebudeme se bát o tom, je, kolik paměti 267 00:13:16,230 --> 00:13:17,820 používáte dnes na nejméně, i když je to 268 00:13:17,820 --> 00:13:19,370 jiný zdroj můžeme měřit. 269 00:13:19,370 --> 00:13:23,610 Budeme se snažit založit své analýzy na jen základní operace, ty, 270 00:13:23,610 --> 00:13:25,930 upřímně, že můžete vidět nejvíce vizuálně. 271 00:13:25,930 --> 00:13:30,700 Takže něco jako velký O n čtvercový, tvrdím, že O n na druhou 272 00:13:30,700 --> 00:13:35,820 je horní mez na takzvaný doba chodu bublin druhu. 273 00:13:35,820 --> 00:13:38,820 Jinými slovy, pokud máte chtěl tvrdit, že je tu 274 00:13:38,820 --> 00:13:41,370 Tento horní limit na tom, kolik kroky algoritmus může trvat, 275 00:13:41,370 --> 00:13:46,240 že to bude ve velkém O n v tomto případě čtvercový, horní mez. 276 00:13:46,240 --> 00:13:49,710 >> Co kdybych místo toho změnit příběh se nejedná o bubble sort, 277 00:13:49,710 --> 00:13:50,910 ale o to horní mez. 278 00:13:50,910 --> 00:13:54,030 Vzpomenete si na algoritmu že jsme se podíval na již 279 00:13:54,030 --> 00:13:59,530 jehož horní hranice, maximální měření času nebo provozu, 280 00:13:59,530 --> 00:14:04,300 by se říci, že je ohraničena o n, lineární funkce, 281 00:14:04,300 --> 00:14:07,260 není kvadratická ten, který je zakřivený? 282 00:14:07,260 --> 00:14:10,780 Co je to algoritmus, který vždy netrvá déle 283 00:14:10,780 --> 00:14:12,860 než jako n kroků, nebo 2n kroků, nebo 3n kroky? 284 00:14:12,860 --> 00:14:13,360 Jo? 285 00:14:13,360 --> 00:14:15,030 >> Diváků: Hledání největší číslo v seznamu? 286 00:14:15,030 --> 00:14:16,930 >> SPEAKER: Perfektní, hledání největší číslo v seznamu. 287 00:14:16,930 --> 00:14:18,940 Pokud jsem dal seznam lidé například, 288 00:14:18,940 --> 00:14:21,440 Každý, kdo je drží číslo, jaký je maximální počet 289 00:14:21,440 --> 00:14:23,770 kroků, to by mě vzít, přiměřeně inteligentní člověk, 290 00:14:23,770 --> 00:14:27,530 najít největší osoby v tomto seznamu? 291 00:14:27,530 --> 00:14:28,100 n, že jo? 292 00:14:28,100 --> 00:14:31,320 Vzhledem k tomu, v nejhorším případě, kdy je možné, že největší hodnota být? 293 00:14:31,320 --> 00:14:32,700 Jasně, úplně na konci. 294 00:14:32,700 --> 00:14:34,575 Takže v nejhorším případě horní mez, možná jsem 295 00:14:34,575 --> 00:14:36,450 muset jít celou cestu tady a být rád, 296 00:14:36,450 --> 00:14:39,170 oh, tady je číslo osm, nebo co, že hodnota je. 297 00:14:39,170 --> 00:14:41,330 Teď to bude jen hloupý když jsem šel dál, že jo? 298 00:14:41,330 --> 00:14:43,840 Hledáte více a více prvků v případě, že poslední z nich je tam? 299 00:14:43,840 --> 00:14:45,340 Tak jistě, n je horní mez. 300 00:14:45,340 --> 00:14:47,420 Nepotřebuju, aby se více kroků, než je. 301 00:14:47,420 --> 00:14:51,580 >> Co když místo toho navrhuje, aby jsou algoritmy v tomto světě, 302 00:14:51,580 --> 00:14:57,750 mají provozní dobu, která je ohraničené velkým O log n log n? 303 00:14:57,750 --> 00:15:00,390 Tam, kde jsme viděli dřív? 304 00:15:00,390 --> 00:15:00,890 Jo? 305 00:15:00,890 --> 00:15:03,309 >> Diváků: V telefonním seznamu problém? 306 00:15:03,309 --> 00:15:04,850 SPEAKER: Jako telefonního seznamu problém. 307 00:15:04,850 --> 00:15:07,754 Co bylo měřítkem toho, jak hodně času a kolik ji strhne 308 00:15:07,754 --> 00:15:10,170 trvalo mi najít někoho, jako je Mike Smith v telefonním seznamu? 309 00:15:10,170 --> 00:15:13,212 Prohlašoval jsme, že log n, a i když neznají, nebo je to 310 00:15:13,212 --> 00:15:15,170 trochu zamlžený, co logaritmus nebo exponent byl, 311 00:15:15,170 --> 00:15:17,650 Jen nezapomeňte, že log n obecně se odkazuje na proces, 312 00:15:17,650 --> 00:15:20,790 v tomto případě dělení něco v polovině znovu a znovu, 313 00:15:20,790 --> 00:15:25,790 a znovu, a znovu, tak, že dostane stále malý, jak to udělat. 314 00:15:25,790 --> 00:15:28,470 >> Takže log n odkazuje, jistě, do telefonního seznamu například 315 00:15:28,470 --> 00:15:32,662 binární vyhledávání v teorii, když jsme měl virtuální dveře na palubě, 316 00:15:32,662 --> 00:15:34,370 nebo když byl Sean něco hledal. 317 00:15:34,370 --> 00:15:37,374 Kdyby byl použit binární vyhledávání, binární log n bude horní mez na tom, kolik 318 00:15:37,374 --> 00:15:38,040 čas, který trvá. 319 00:15:38,040 --> 00:15:44,027 Ale ty algoritmy, které běžely v log n předpokládá, jaká klíčová detail? 320 00:15:44,027 --> 00:15:45,360 Že seznam byl tříděn, že jo? 321 00:15:45,360 --> 00:15:47,789 Algoritmus je-li špatně Váš vstup netřídí, 322 00:15:47,789 --> 00:15:49,830 a přesto, že používáte něco jako binární vyhledávání 323 00:15:49,830 --> 00:15:51,704 protože byste mohli skočit přímo přes prvku 324 00:15:51,704 --> 00:15:53,600 aniž by si uvědomil, že je to opravdu tam. 325 00:15:53,600 --> 00:15:55,600 >> A teď, co by to mohlo znamenat, velký O jednoho? 326 00:15:55,600 --> 00:15:59,117 To neznamená, že algoritmu trvá jeden a pouze jeden krok, 327 00:15:59,117 --> 00:16:01,200 to prostě znamená, že to trvá konstantní počet kroků. 328 00:16:01,200 --> 00:16:04,060 Možná je to jeden, možná je to 10, možná je to 1000, 329 00:16:04,060 --> 00:16:07,750 ale je to nezávislý Velikost problému. 330 00:16:07,750 --> 00:16:10,850 Bez ohledu na to, jak velký je n, časová konstanta algoritmus 331 00:16:10,850 --> 00:16:12,747 má vždy stejný počet kroků. 332 00:16:12,747 --> 00:16:15,080 Takže to, co by mohlo být algoritmus jsme mluvili o, nebo jen 333 00:16:15,080 --> 00:16:20,418 intuitivně, že k vám přijde, že vždy běží v takzvané konstantním čase? 334 00:16:20,418 --> 00:16:20,918 Jo? 335 00:16:20,918 --> 00:16:22,001 >> Diváků: Přidejte dvě čísla. 336 00:16:22,001 --> 00:16:25,320 SPEAKER: Přidejte dvě čísla, 2 plus 2 se rovná 4, hotovo. 337 00:16:25,320 --> 00:16:27,227 Tak to by mohlo fungovat, co jiného? 338 00:16:27,227 --> 00:16:28,560 Jak se o více skutečném světě, ne? 339 00:16:28,560 --> 00:16:30,686 >> Diváků: Hledání První věc, kterou v seznamu. 340 00:16:30,686 --> 00:16:32,810 SPEAKER: Nalezení první prvek v seznamu, jistě. 341 00:16:32,810 --> 00:16:34,540 Jsme vlastně mluvili o polích již 342 00:16:34,540 --> 00:16:36,540 jak se dostat na první prvek v matici, 343 00:16:36,540 --> 00:16:40,465 bez ohledu na to, jak dlouho pole je v C kódu? 344 00:16:40,465 --> 00:16:43,090 Stačí použít jako držák bum, jste tam nula notace, ty. 345 00:16:43,090 --> 00:16:46,120 A samozřejmě pole, jako stranou, Podpora něco všeobecně známo, 346 00:16:46,120 --> 00:16:49,240 jako náhodný přístup, s přímým přístupem paměť, protože můžete doslova 347 00:16:49,240 --> 00:16:50,284 přeskočit na jednom místě. 348 00:16:50,284 --> 00:16:52,700 Můžeme to udělat ještě jednodušeji můžeme přetočit na týden nulové 349 00:16:52,700 --> 00:16:53,900 když jsme nuly. 350 00:16:53,900 --> 00:16:59,707 Kolik času to trvat říci, blok Scratch vykonat? 351 00:16:59,707 --> 00:17:00,790 Jen konstantní čas, že jo? 352 00:17:00,790 --> 00:17:03,960 Řekni něco, řekni něco, nezáleží na tom, 353 00:17:03,960 --> 00:17:07,359 jak velké škrábance svět, je to vždy bude trvat stejnou dobu 354 00:17:07,359 --> 00:17:08,490 prostě něco říct. 355 00:17:08,490 --> 00:17:11,089 >> Tak to je časová konstanta, ale co druhá strana? 356 00:17:11,089 --> 00:17:13,030 Kdyby tomu tak bylo vyšší hranice, co chceme-li 357 00:17:13,030 --> 00:17:17,089 popsat dolní meze z našich algoritmů běží čas? 358 00:17:17,089 --> 00:17:19,852 Téměř v nejlepším případě potenciálně, chcete-li, 359 00:17:19,852 --> 00:17:23,060 když tyto podmínky by se mohly vztahovat k nejlepším pouzdra, nejhorší případy, průměr pouzdra více 360 00:17:23,060 --> 00:17:26,359 obecně, ale pojďme se soustředit jen Na spodní hranice obecně. 361 00:17:26,359 --> 00:17:31,920 Co je to algoritmus, který má dolní mez n kroků, 362 00:17:31,920 --> 00:17:33,350 nebo 2n kroků, nebo 3n kroky? 363 00:17:33,350 --> 00:17:36,241 Některé faktor n kroků, to je jeho dolní mez. 364 00:17:36,241 --> 00:17:36,740 Jo? 365 00:17:36,740 --> 00:17:37,910 >> Diváků: Bubble sort? 366 00:17:37,910 --> 00:17:41,610 >> SPEAKER: Bubble sort se budete minimálně n kroků, proč? 367 00:17:41,610 --> 00:17:42,279 Proč tomu tak je? 368 00:17:42,279 --> 00:17:45,320 Proč by to začátek přijít k vám intuitivně, i když to není jen 369 00:17:45,320 --> 00:17:46,530 ještě? 370 00:17:46,530 --> 00:17:47,030 Jo? 371 00:17:47,030 --> 00:17:47,990 >> Diváků: [neslyšitelné]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 SPEAKER: Přesně tak. 374 00:17:52,360 --> 00:17:55,810 V nejlepším možném scénáři bublina třídit a mnoho algoritmů, 375 00:17:55,810 --> 00:17:58,769 pokud předám vám osm lidí který je již řazeno, 376 00:17:58,769 --> 00:18:00,560 že by bylo pošetilé pro vás, algoritmus, 377 00:18:00,560 --> 00:18:02,202 jít tam a zpět více než jednou, ne? 378 00:18:02,202 --> 00:18:04,285 Vzhledem k tomu, jakmile se projít seznam jednou, 379 00:18:04,285 --> 00:18:08,090 měli byste si uvědomit, oh, jsem žádný swapy, tento seznam je tříděn, exit. 380 00:18:08,090 --> 00:18:09,700 Ale, co se děje, aby vás n kroků. 381 00:18:09,700 --> 00:18:12,033 >> A naopak, co je jiný způsob, jak o tom přemýšlet? 382 00:18:12,033 --> 00:18:15,240 Bubble sort je omega, abych tak řekl, n, 383 00:18:15,240 --> 00:18:19,050 protože když se podíváte na méně než n prvků, co se 384 00:18:19,050 --> 00:18:23,009 je zde zásadní problém? 385 00:18:23,009 --> 00:18:24,550 Nevíte, jestli je to třídění, doprava. 386 00:18:24,550 --> 00:18:26,800 Jsme lidé, může dojít pohled na osm lidí a být rád, ach, je to třídění, 387 00:18:26,800 --> 00:18:28,430 že jsi mi n kroků nebere, ale stalo se. 388 00:18:28,430 --> 00:18:30,810 Tvé oči, i když tak nějak ze mají velký zorné pole, 389 00:18:30,810 --> 00:18:33,184 jste se podívali na osmi prvků, jste se podívali na osm osob, 390 00:18:33,184 --> 00:18:34,610 to je osm kroků efektivně. 391 00:18:34,610 --> 00:18:38,612 A jen tehdy, pokud jsem projít celý Seznam mám uvědomit, ano, třídit. 392 00:18:38,612 --> 00:18:41,320 Pokud bych se zastaví na mysli všechny Dobře, je to docela řazeny tak daleko, 393 00:18:41,320 --> 00:18:42,520 jaké jsou šance, že to není tříděné? 394 00:18:42,520 --> 00:18:44,186 To algoritmy nebude správné. 395 00:18:44,186 --> 00:18:46,250 Může být rychlejší, ale nesprávné. 396 00:18:46,250 --> 00:18:48,500 >> Takže teď máme způsob, jak popisující dolní hranice, 397 00:18:48,500 --> 00:18:49,710 a co konstantním čase? 398 00:18:49,710 --> 00:18:54,565 Co je to algoritmus, který má nižší vázána na jeho chodu době jednoho? 399 00:18:54,565 --> 00:18:58,350 1 krok, dva kroky, 10 kroků, ale konstantní, nezávisle na n, 400 00:18:58,350 --> 00:18:59,310 Velikost vstupu? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Jo, v zádech. 403 00:19:04,600 --> 00:19:05,309 >> Diváků: printf? 404 00:19:05,309 --> 00:19:06,183 SPEAKER: Co je to? 405 00:19:06,183 --> 00:19:07,184 Diváků: printf? 406 00:19:07,184 --> 00:19:07,850 SPEAKER: printf. 407 00:19:07,850 --> 00:19:08,400 OK, jistě. 408 00:19:08,400 --> 00:19:10,720 Tak to trvá stanoveném počtu kroků. 409 00:19:10,720 --> 00:19:13,170 A já jsem měla teď-- teď mluvíme o C kódu 410 00:19:13,170 --> 00:19:16,040 a ne Scratch, něco jako řekněme, s printf, 411 00:19:16,040 --> 00:19:17,710 bychom měli začít, aby si opatrný. 412 00:19:17,710 --> 00:19:21,090 Vzhledem k tomu, printf se vzít vstup, je to řetězec, 413 00:19:21,090 --> 00:19:23,220 a řetězce to technicky mít délku. 414 00:19:23,220 --> 00:19:25,530 Takže pokud chceme nyní vybrat na vás, jestli vám to nebude vadit, 415 00:19:25,530 --> 00:19:29,430 technicky bychom mohli tvrdit, že printf to se s proměnnou délkou vstup, 416 00:19:29,430 --> 00:19:32,270 a jistě by to mohlo trvat déle Doba tisku řetězec tak dlouho, 417 00:19:32,270 --> 00:19:33,560 než tak dlouho. 418 00:19:33,560 --> 00:19:36,570 >> A co když vezmeme v úvahu jen třídění a vyhledávání příkladů? 419 00:19:36,570 --> 00:19:40,450 Co Mike Smith v telefonu kniha, nebo binární vyhledávání obecně? 420 00:19:40,450 --> 00:19:42,220 V nejlepším případě, co se může stát? 421 00:19:42,220 --> 00:19:45,577 Otevřel jsem telefonní seznam, a bum, tam je číslo Mike Smith. 422 00:19:45,577 --> 00:19:46,660 Nemůžu ho zavolat hned. 423 00:19:46,660 --> 00:19:49,390 >> Udělal jeden krok, možná dva kroky, ale konstantní počet kroků 424 00:19:49,390 --> 00:19:50,230 když jsem měl štěstí. 425 00:19:50,230 --> 00:19:52,570 A upřímně řečeno, jsme viděli na Pondělí váš spolužák 426 00:19:52,570 --> 00:19:54,710 dostat docela štěstí dvakrát za sebou. 427 00:19:54,710 --> 00:19:57,050 A to je skutečně konstantní čas v dolní mez 428 00:19:57,050 --> 00:20:01,280 na algoritmu se jedná o hledání číslo 50 za ty zavřené 429 00:20:01,280 --> 00:20:01,830 dveře. 430 00:20:01,830 --> 00:20:06,400 >> Nyní, stejně jako stranou, když zjistíte, že jak velký O, horní mez, 431 00:20:06,400 --> 00:20:09,310 a omega, dolní mez, jsou jeden ve stejné, že 432 00:20:09,310 --> 00:20:11,830 je stejný vzorec v závorky, můžete také 433 00:20:11,830 --> 00:20:15,170 říci, jen pro chuť, , že něco, co je v theta 434 00:20:15,170 --> 00:20:18,270 n nebo theta nějaké jiné hodnoty. 435 00:20:18,270 --> 00:20:20,661 To prostě znamená, že když velká O a omega jsou stejné. 436 00:20:20,661 --> 00:20:21,910 A co výběr druhu teď? 437 00:20:21,910 --> 00:20:23,400 Využijme tuto novou slovní zásobu. 438 00:20:23,400 --> 00:20:27,407 Ve výběru druhu, o čem jsme dělat znovu a znovu a znovu? 439 00:20:27,407 --> 00:20:29,990 Byl jsem tam a zpět přes seznam, hledá pro koho? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Nejmenší číslo. 442 00:20:34,730 --> 00:20:37,560 >> Tak kolik kroků, jak mnoho srovnání udělal já 443 00:20:37,560 --> 00:20:43,250 muset udělat, aby se zjistit, kdo nejmenší prvek v seznamu je? 444 00:20:43,250 --> 00:20:44,437 n minus 1, ne? 445 00:20:44,437 --> 00:20:47,770 Protože když jsem začít s jedním Jsem vzhledem k tomu, a začnu ho porovnávání, 446 00:20:47,770 --> 00:20:49,519 pak on nebo ona, ho nebo ona, on nebo ona, jsem 447 00:20:49,519 --> 00:20:52,010 lze spárovat pouze prvky spolu n minus 1 krát. 448 00:20:52,010 --> 00:20:55,630 Takže výběr trochu podobně se n minus 1 krok poprvé. 449 00:20:55,630 --> 00:20:59,540 >> Kolik kroků to mě vzít najít druhý nejmenší prvek? 450 00:20:59,540 --> 00:21:02,920 n minus 2, protože jsem byl hloupý pokud Pořád se dívá na stejných lidí 451 00:21:02,920 --> 00:21:06,280 znovu, jestli jsem ho už vybrali nebo ji a dát je na jejich místo. 452 00:21:06,280 --> 00:21:09,270 A třetí krok, n minus 3, pak n minus čtyři. 453 00:21:09,270 --> 00:21:11,020 Viděli jsme tento model před, a skutečně 454 00:21:11,020 --> 00:21:13,460 Výběr třídění podobně je horní hranice 455 00:21:13,460 --> 00:21:16,210 n na druhou, pokud budeme dělat až ten shrnutí. 456 00:21:16,210 --> 00:21:19,790 Jaká je jeho dolní mez, výběr trochu? 457 00:21:19,790 --> 00:21:25,350 Minimálně, kolik výběr času musí třídění se, jak se nám to definováno v pondělí? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Navrhnout dvě možnosti. 460 00:21:30,490 --> 00:21:32,360 Možná je to n, jako předtím. 461 00:21:32,360 --> 00:21:35,040 Možná, že to je n na druhou, jak to Nyní je jako horní mez. 462 00:21:35,040 --> 00:21:35,874 >> Diváků: n na druhou. 463 00:21:35,874 --> 00:21:36,664 SPEAKER: n na druhou. 464 00:21:36,664 --> 00:21:37,368 Proč? 465 00:21:37,368 --> 00:21:40,060 >> Diváků: Protože máte definovat [neslyšitelné]. 466 00:21:40,060 --> 00:21:41,510 >> SPEAKER: Přesně tak. 467 00:21:41,510 --> 00:21:45,077 Alespoň jak jsem je definováno výběr druhu to bylo dost naivní, pokračuj, 468 00:21:45,077 --> 00:21:46,160 najít nejmenší prvek. 469 00:21:46,160 --> 00:21:47,770 Jděte zase, a najít nejmenší prvek. 470 00:21:47,770 --> 00:21:49,490 Jděte zase, a najít nejmenší prvek. 471 00:21:49,490 --> 00:21:51,700 Neexistuje žádný druh optimalizace v tam, že 472 00:21:51,700 --> 00:21:54,350 může mi dovolte ukončit po jen n nebo tak kroky. 473 00:21:54,350 --> 00:21:57,080 Takže opravdu, výběr třídění, omega n na druhou. 474 00:21:57,080 --> 00:22:00,667 >> Co vložení druhu, kde jsem vzal který jsem dostal, a pak jsem ho svalil 475 00:22:00,667 --> 00:22:01,750 nebo ji na správné místo? 476 00:22:01,750 --> 00:22:04,958 Pak jsem přistoupil k druhé osobě, svalil ho na správném místě. 477 00:22:04,958 --> 00:22:07,910 Pak další osoba, svalil ho nebo ji na správném místě. 478 00:22:07,910 --> 00:22:10,537 Všimněte si, že je to velmi lineární, abych tak řekl. 479 00:22:10,537 --> 00:22:12,620 Jsem přímka, já jsem Není tam a zpět, 480 00:22:12,620 --> 00:22:16,080 Nikdy jsem se ohlédl ne, ale co se děje, když jsem se ho vložit 481 00:22:16,080 --> 00:22:20,302 nebo ji do začátku seznam jako jsme to udělali v pondělí? 482 00:22:20,302 --> 00:22:21,010 Co se děje? 483 00:22:21,010 --> 00:22:21,510 Jo? 484 00:22:21,510 --> 00:22:23,122 Diváků: [neslyšitelné]. 485 00:22:23,122 --> 00:22:24,830 SPEAKER: Jo, to byl úlovek, ne? 486 00:22:24,830 --> 00:22:26,746 Možná pamatujete z svými spolužáky, pokud se 487 00:22:26,746 --> 00:22:29,670 dělali jakýkoli pohyb s jejich nohy, to je operace. 488 00:22:29,670 --> 00:22:33,610 Takže v případě, že byli tři lidé tady a nový člověk patřil támhle, 489 00:22:33,610 --> 00:22:37,360 na dlouhou fázi, jako je tato, jistě, že nebo mohla prostě jít až do samého konce. 490 00:22:37,360 --> 00:22:40,074 Ale pokud uvažujete o počítače a pole paměti, 491 00:22:40,074 --> 00:22:41,990 tito lidé jdou muset zamíchat přes 492 00:22:41,990 --> 00:22:43,260 aby se prostor pro tuto osobu. 493 00:22:43,260 --> 00:22:46,930 A tak, aby n minus 1 shufflings, n minus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 minus 3 shufflings je jen trochu se děje za mnou, ne přede mnou 495 00:22:50,660 --> 00:22:52,710 jako dříve, v jistém smyslu. 499 00:22:52,557 --> 00:22:54,640 Nyní jako stranou a jako jste mohli vidět on-line 500 00:22:54,640 --> 00:22:57,699 pokud začnete vrtat o druhy, je tam tolik různých ty 501 00:22:57,699 --> 00:22:59,490 tam, některé z nich lepší než ostatní. 502 00:22:59,490 --> 00:23:02,200 Ve skutečnosti, je jedním bogosort to je docela zábavné vzhlédnout. 503 00:23:02,200 --> 00:23:06,650 Bogosort má sadu čísla nebo říkají, balíček karet, 504 00:23:06,650 --> 00:23:09,870 náhodně zamíchá je a zkontroluje, zda oni jsou řazeny. 505 00:23:09,870 --> 00:23:12,130 A pokud ne, udělá to znovu. 506 00:23:12,130 --> 00:23:14,140 A pokud ne, udělá to znovu. 507 00:23:14,140 --> 00:23:15,440 Pokud ne, dělá to znovu. 508 00:23:15,440 --> 00:23:17,060 Neuvěřitelně hloupý. 509 00:23:17,060 --> 00:23:19,520 >> A skutečně, když si přečtete jako Wikipedia článku, 510 00:23:19,520 --> 00:23:21,200 jeho přezdívka je hloupý druh. 511 00:23:21,200 --> 00:23:25,180 To bude nakonec fungovat, doufejme, že vzhledem k tomu dostatek času, 512 00:23:25,180 --> 00:23:28,240 ale to množství času, může trvat nějakou dobu. 513 00:23:28,240 --> 00:23:31,650 Takže pokud bych mohl, pojďme rychlosti věcí up od Mary Beth je například dříve, 514 00:23:31,650 --> 00:23:35,150 tím, že má ještě několik dalších prvků, ale další dva procesory. 515 00:23:35,150 --> 00:23:37,100 Dva lidé, pokud máte Nevadilo by mi to spojení. 516 00:23:37,100 --> 00:23:40,972 Jak se o jeden sem, a pojďme jít-- nikoho tam? 517 00:23:40,972 --> 00:23:41,722 Nikdo tam? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 Ty s černou košile, ano, pojď dolů. 520 00:23:44,190 --> 00:23:45,000 Tak jo, Jak se jmenujete? 521 00:23:45,000 --> 00:23:45,720 >> DIVÁKŮ: Peter. 522 00:23:45,720 --> 00:23:46,100 >> SPEAKER: Co je to? 523 00:23:46,100 --> 00:23:46,766 >> DIVÁKŮ: Peter. 524 00:23:46,766 --> 00:23:49,450 SPEAKER: Peter David, rád tě poznávám. 525 00:23:49,450 --> 00:23:53,670 Dobře, máme Petra tady, pokud máte chtějí přijít na stůl sem. 526 00:23:53,670 --> 00:23:54,550 A Jak se jmenujete? 527 00:23:54,550 --> 00:23:55,216 >> DIVÁKŮ: Elena. 528 00:23:55,216 --> 00:23:55,970 SPEAKER: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, rád tě poznávám. 530 00:23:57,030 --> 00:23:58,060 Elena setkat Petera. 531 00:23:58,060 --> 00:23:59,170 Petr, Elena. 532 00:23:59,170 --> 00:24:02,290 A budeme potřebovat Andrew se i zde, prosím. 533 00:24:02,290 --> 00:24:06,107 A vaše výzva se děje aby třídit balíček karet. 534 00:24:06,107 --> 00:24:08,190 A pokud neznáte, paluba karet by mělo v konečném důsledku 535 00:24:08,190 --> 00:24:11,064 seřadit trochu něco jako Tady uděláme kluby, pak 536 00:24:11,064 --> 00:24:13,660 lopatky, pak srdce a diamanty, od esa jako jeden, 537 00:24:13,660 --> 00:24:15,570 celou cestu až ke králi. 538 00:24:15,570 --> 00:24:20,890 >> Karty budu vám se bude 52 v množství. 539 00:24:20,890 --> 00:24:23,160 Chystáme se podobně čas vás za chvíli. 540 00:24:23,160 --> 00:24:26,410 Budeme házet Andrew na obrazovce zde 541 00:24:26,410 --> 00:24:28,170 tak se dívat, jak to uděláte. 542 00:24:28,170 --> 00:24:31,070 A aby to všechno je to více vidět, 543 00:24:31,070 --> 00:24:33,490 to jsou karty Dostal jsem na Amazonu. 544 00:24:33,490 --> 00:24:42,861 Takže už jsou náhodně řazeny, a budeme vám čas. 545 00:24:42,861 --> 00:24:44,610 A jdeme na udržet skutečný tentokrát 546 00:24:44,610 --> 00:24:47,820 takže budeme snažit tlačit protože jinak to bude únavné 547 00:24:47,820 --> 00:24:48,460 rychle. 548 00:24:48,460 --> 00:24:53,860 Pokud byste mohli pokračovat třídit 52 prvky spolu přes některé prostředky, hned. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> A opět, jak jsme se dívat na to kluci dělat co, na konci 551 00:25:07,180 --> 00:25:10,200 bude produkovat jasné Výsledkem je, přemýšlet o tom, opravdu 552 00:25:10,200 --> 00:25:12,962 jak si každý dělá, jak můžete to popsat. 553 00:25:12,962 --> 00:25:15,045 Vzhledem k tomu, opět se jedná o Všechny procesy, algoritmy 554 00:25:15,045 --> 00:25:17,090 které bereme jako samozřejmost jako člověk. 555 00:25:17,090 --> 00:25:22,349 Ale pravděpodobně jste už dlouho intuice, dlouho předtím, než vás, i 556 00:25:22,349 --> 00:25:24,390 myšlenka o tom, výpočetní technika vám třída 557 00:25:24,390 --> 00:25:27,223 mohla být důvodem pro intuici s pro řešení problémů, jako je tento. 558 00:25:27,223 --> 00:25:29,560 Ale jakmile poznáte vzory a začít 559 00:25:29,560 --> 00:25:32,407 formalizovat kroky, s nimiž máte řešení těchto problémů, 560 00:25:32,407 --> 00:25:35,490 zjistíte, že můžete vyřešit mnoho zajímavější a mnohem složitější 561 00:25:35,490 --> 00:25:39,190 problémy rychle. 562 00:25:39,190 --> 00:25:42,351 Takže někdo z publika, co je alespoň jeden prvek z algoritmu 563 00:25:42,351 --> 00:25:43,350 že používáte tady? 564 00:25:43,350 --> 00:25:44,275 >> Diváků: [neslyšitelné] 565 00:25:44,275 --> 00:25:45,150 SPEAKER: Co je to? 566 00:25:45,150 --> 00:25:47,062 DIVÁKŮ: Podle obleku. 567 00:25:47,062 --> 00:25:47,770 SPEAKER: Podle obleku. 568 00:25:47,770 --> 00:25:50,630 Takže nejprve se klastrování všechny diamanty společně 569 00:25:50,630 --> 00:25:52,560 Zdá se, že všechny srdce spolu se zdá, 570 00:25:52,560 --> 00:25:56,520 a tak dále, a to bez ohledu pro čísla na kartách. 571 00:25:56,520 --> 00:26:00,900 A teď se zdá, například, k třídění je podle čísla. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Velmi dobře. 574 00:26:08,910 --> 00:26:12,370 >> Dobře, takže to, co se být posledním krokem pak tady? 575 00:26:12,370 --> 00:26:16,950 Jakmile budeme mít čtyři tříděných obleky, co to musíme udělat, aby se čtyři piloty 576 00:26:16,950 --> 00:26:20,059 , aby se dosáhlo jedné řazeny palubu, jednoduše? 577 00:26:20,059 --> 00:26:21,350 Proto musíme znovu sloučit. 578 00:26:21,350 --> 00:26:25,160 >> Takže tam je to zajímavý nápad, který opět Troufám si tvrdit, je velmi intuitivní, i 579 00:26:25,160 --> 00:26:28,140 pokud jste možná nikdy facku tento druh štítku na to. 580 00:26:28,140 --> 00:26:31,900 Tato základní představa o rozdělení problém není v polovině této doby, 581 00:26:31,900 --> 00:26:33,410 ale alespoň do čtyř částí. 582 00:26:33,410 --> 00:26:36,810 Řešení do značné míry v podstatě identické problémy 583 00:26:36,810 --> 00:26:40,480 izolovaně od sebe, a sloučení výsledků. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 A vynikající, hotovo. 586 00:26:50,140 --> 00:26:52,140 Tak jo, malý a velký okruh potlesk, kdybychom mohli. 587 00:26:52,140 --> 00:26:56,480 >> [APPLAUSE] 588 00:26:56,480 --> 00:26:59,740 >> SPEAKER: Nemám ponětí, co budete dělat s nimi, ale tady to máte. 589 00:26:59,740 --> 00:27:01,690 Děkuji moc. 590 00:27:01,690 --> 00:27:04,660 Tak se podívejme, dvě minuty a osm sekund, 591 00:27:04,660 --> 00:27:07,490 pokud byste chtěli vyzvat své přátele. 592 00:27:07,490 --> 00:27:12,160 Co se pak bude by se od tohoto 593 00:27:12,160 --> 00:27:13,830 že můžeme využít obecně? 594 00:27:13,830 --> 00:27:16,080 No, myslím, že zpět do Toto pole čísel, 595 00:27:16,080 --> 00:27:19,060 a myslím, že teď vrátit k některým pseudokód psali jsme v minulosti, 596 00:27:19,060 --> 00:27:22,080 a to pseudokód pro řešení telefonního seznamu problém. 597 00:27:22,080 --> 00:27:25,150 Přičemž v pseudokódu I vyjmenoval více metodický způsob 598 00:27:25,150 --> 00:27:28,400 popisovat, jak jsem to udělal velmi intuitivní lidský algoritmus dělení telefon 599 00:27:28,400 --> 00:27:31,650 knihy na polovinu, opakovat, opakovat, opakovat, dokud nenajdu někoho, jako Mike Smith, 600 00:27:31,650 --> 00:27:33,790 v případě, že je opravdu v telefonním seznamu. 601 00:27:33,790 --> 00:27:37,610 >> Ale nějak jsem použít to, co budu říkat velmi iterativní přístup zde 602 00:27:37,610 --> 00:27:42,160 zejména oznámení linka 8 a linka 11. 603 00:27:42,160 --> 00:27:46,750 To jsou důkazy o iterativní přístup, přístup smyčkování, 604 00:27:46,750 --> 00:27:49,040 protože to je přesně to, chování, které vyvolávají. 605 00:27:49,040 --> 00:27:52,910 Tyto řádky oba, že jít do řádek tři, a můžete trochu 606 00:27:52,910 --> 00:27:55,140 myslet, že ve vašem mysli oko jako smyčka. 607 00:27:55,140 --> 00:27:59,080 Je to říkám, jít zpět ke kroku tři a opakovat znovu a znovu, 608 00:27:59,080 --> 00:28:00,010 a znovu. 609 00:28:00,010 --> 00:28:04,410 >> Ale co když budeme využívat klíčovou myšlenku tady, že jsme neměli v poslední době, 610 00:28:04,410 --> 00:28:10,280 a zjednodušit linky 8 a řádek 11 a jejich sousedé 611 00:28:10,280 --> 00:28:12,840 jak je jen to, žlutě. 612 00:28:12,840 --> 00:28:16,480 Není to v podstatě zkrácení pseudokód moc, 613 00:28:16,480 --> 00:28:20,530 ale je to v podstatě mění povahu mého algoritmu. 614 00:28:20,530 --> 00:28:24,220 To, co jsem teď řekl v kroku 7, v kroku 10, 615 00:28:24,220 --> 00:28:29,140 je hledat Mike v přesně stejným způsobem, 616 00:28:29,140 --> 00:28:31,580 ale jen v levé polopenze nebo pravou polovinu. 617 00:28:31,580 --> 00:28:33,420 >> Takže jinými slovy, v případě, Začnu od kroku jedna, 618 00:28:33,420 --> 00:28:36,150 zvednout telefonní seznam, otevřený střed z telefonního seznamu, podívejte se na jména, 619 00:28:36,150 --> 00:28:39,010 pokud Smith patří mezi Název je, zavolejte Mike, jinak 620 00:28:39,010 --> 00:28:44,340 pokud Smith dříve v knize krok za sedm hledat Mike v levé polovině knihy. 621 00:28:44,340 --> 00:28:47,130 Ale trochu pocit, jako to nechal mě visí, že jo? 622 00:28:47,130 --> 00:28:49,240 Ve žluté, je instrukce, ale jak to mám 623 00:28:49,240 --> 00:28:51,870 hledání Mike v levé polovina z telefonního seznamu? 624 00:28:51,870 --> 00:28:54,210 Kde mám algoritmus, se kterým jsem 625 00:28:54,210 --> 00:28:57,100 Můžete hledat někoho, jako je Mike Smith? 626 00:28:57,100 --> 00:28:58,980 No, je to zírá nás tváří v tvář. 627 00:28:58,980 --> 00:29:03,090 Mohu doslova použít přesně stejný program skutečně jít až na vrchol 628 00:29:03,090 --> 00:29:06,490 Znovu a znovu běží stejné řádky kódu. 629 00:29:06,490 --> 00:29:10,610 >> Takže i když by to mělo cítit jako trochu cyklické definice 630 00:29:10,610 --> 00:29:13,480 kam odpovědi někdo Otázka, kterou tak nějak se ptát 631 00:29:13,480 --> 00:29:15,990 opět stejná otázka, jako proč, proč, proč? 632 00:29:15,990 --> 00:29:21,580 Skutečností je, protože jsme pevně dáno několik speciálních linek, krok 4, 633 00:29:21,580 --> 00:29:25,320 , který je v případě, a krok 12, který je v podstatě další větev, 634 00:29:25,320 --> 00:29:30,120 protože máme ty provizorium opatření, Tento algoritmus se ukončí, pokud budeme 635 00:29:30,120 --> 00:29:32,050 najít Mike, nebo pokud to neuděláme. 636 00:29:32,050 --> 00:29:36,810 Ale v kroku 7 a 10 nyní máme co budeme říkat rekurzivní algoritmus. 637 00:29:36,810 --> 00:29:40,420 A rekurze je opravdu silný nápad to je trochu mysl ohýbání na první, 638 00:29:40,420 --> 00:29:42,500 že nyní můžeme aplikovat takto. 639 00:29:42,500 --> 00:29:46,600 >> Merge sort bude poslední druh, který se podíváme na, alespoň ve třídě formálně. 640 00:29:46,600 --> 00:29:50,040 A to je zásadně odlišná z těch posledních tří, a jistě 641 00:29:50,040 --> 00:29:52,140 Poslední čtyři zahrneme-li bogosort. 642 00:29:52,140 --> 00:29:54,810 Zde je pseudokód pro slučovací druhu. 643 00:29:54,810 --> 00:30:00,170 Když se na vstupu n prvků tak, vzhledem k pole o velikosti n, pokud n je menší než 2, 644 00:30:00,170 --> 00:30:01,040 vrátit. 645 00:30:01,040 --> 00:30:03,610 Tak proč mám, že zdravý rozum zkontrolovat jako první? 646 00:30:03,610 --> 00:30:09,477 Jaký je důsledek, pokud předám vás pole, jehož délka n je menší než 2? 647 00:30:09,477 --> 00:30:11,060 Je to již řazeno, samozřejmě, že jo? 648 00:30:11,060 --> 00:30:13,640 Protože seznam má buď jeden prvek, který je triviálně 649 00:30:13,640 --> 00:30:15,180 řazeny, protože je to Jediné, co tam. 650 00:30:15,180 --> 00:30:18,138 Nebo je to o velikosti nula, což znamená, nic vyřešit, tak od přírody 651 00:30:18,138 --> 00:30:18,720 to je tříděn. 652 00:30:18,720 --> 00:30:20,410 Je tu jen nic špatného tam. 653 00:30:20,410 --> 00:30:22,310 Tak to je náš takzvaný referenční případ. 654 00:30:22,310 --> 00:30:24,440 >> To je podobné v duchu na to, co jsme udělali s Mikem. 655 00:30:24,440 --> 00:30:26,023 Pokud se Mike v telefonním seznamu, zavolejte mu. 656 00:30:26,023 --> 00:30:27,740 Pokud tam není, vzdát. 657 00:30:27,740 --> 00:30:31,240 Je to takzvaný referenční případ, aby se ujistil, Tento algoritmus na konci dne 658 00:30:31,240 --> 00:30:33,540 se zastaví v určitých okolností. 659 00:30:33,540 --> 00:30:37,890 >> Ale tady je ten skok víry nyní, jinak, seřadit levou polovinu prvků, 660 00:30:37,890 --> 00:30:39,740 seřadit právo polovina z prvků, 661 00:30:39,740 --> 00:30:41,189 a pak sloučit seřazené poloviny. 662 00:30:41,189 --> 00:30:43,230 A tady je místo, kde se cítí to, že jsme copping ven. 663 00:30:43,230 --> 00:30:46,900 Požádal jsem vás, abyste třídění n prvků, a já jsem 664 00:30:46,900 --> 00:30:50,712 řka: OK, to je třídění doleva a třídění právo. 665 00:30:50,712 --> 00:30:52,420 Ale já říkám jedno Další věc, a to 666 00:30:52,420 --> 00:30:55,530 je klíčové téma se zdá, v intuici tak daleko, 667 00:30:55,530 --> 00:30:57,380 tam je to třetí krok slučování. 668 00:30:57,380 --> 00:31:00,430 Které, i když se zdá být tak hloupý v duchu, 669 00:31:00,430 --> 00:31:02,320 jako právě sloučit věci spolu, se zdá 670 00:31:02,320 --> 00:31:05,380 být klíčovým krokem směrem k opětovnou montáž dvou problémů, které 671 00:31:05,380 --> 00:31:07,330 byly rozděleny nakonec v polovině. 672 00:31:07,330 --> 00:31:12,090 >> Takže sloučit druh, jdeme na to, pokud budete humor, abych se ještě jednu demonstraci, 673 00:31:12,090 --> 00:31:14,730 jen proto, že máme nějaké Čísla pracovat. 674 00:31:14,730 --> 00:31:19,470 Mohu u Vás vyměnit osm stres míče pro osm lidí? 675 00:31:19,470 --> 00:31:29,320 Dobře, a co vy tři, vy čtyři v této části, pět, šest, a pojďme 676 00:31:29,320 --> 00:31:30,720 do 7, 8, pojď nahoru. 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 Minus 8, jdeme na to, plus 1. 680 00:31:38,640 --> 00:31:39,150 Výborně. 681 00:31:39,150 --> 00:31:42,000 Dobře pojď nahoru, pojďme Rychle vám čísel. 682 00:31:42,000 --> 00:31:50,800 Číslo dvě, číslo tři, číslo čtyři, číslo pět, šest, sedm a osm. 683 00:31:50,800 --> 00:31:52,140 Udělal jsem osm správně tentokrát. 684 00:31:52,140 --> 00:31:56,390 >> OK, tak do toho, pokud byste mohl, a seřaďte v původním pořadí 685 00:31:56,390 --> 00:31:59,810 že jsme měli včera, která se zabývala takhle, pokud vám to nebude vadit. 686 00:31:59,810 --> 00:32:03,620 A jdeme na to před stolem. 687 00:32:03,620 --> 00:32:06,510 Dobře, takže sloučit druh. 688 00:32:06,510 --> 00:32:08,820 To je místo, kde to bude dostat docela zajímavé, 689 00:32:08,820 --> 00:32:12,800 protože to vypadá, že dávat sám sebe mnohem méně informací dnes. 690 00:32:12,800 --> 00:32:15,149 >> Takže sloučit druh v první řadě na vstupu n prvků, 691 00:32:15,149 --> 00:32:18,440 a je samozřejmě ne méně než dva, je to osm, takže mám trochu víc práce. 692 00:32:18,440 --> 00:32:21,140 Takže teď psychicky jsme se jako třída jsou nyní v odvětví jiném, 693 00:32:21,140 --> 00:32:22,540 což znamená, že tři kroky. 694 00:32:22,540 --> 00:32:25,017 Za prvé, musím vyřešit levá polovina prvků. 695 00:32:25,017 --> 00:32:26,350 Tak jak mám jít asi dělá? 696 00:32:26,350 --> 00:32:28,950 No, já jdu na druh mentálně rozdělit seznam zde 697 00:32:28,950 --> 00:32:30,700 nemáte k fyzicky pohybovat, a já jsem 698 00:32:30,700 --> 00:32:33,180 Zaměřím se pouze na levá polovina prvků zde. 699 00:32:33,180 --> 00:32:36,770 Tak jak mám jít o třídění seznam se velikosti čtyři? 700 00:32:36,770 --> 00:32:38,730 Co je můj algoritmus? 701 00:32:38,730 --> 00:32:42,580 Nejprve jsem zkontrolujte n menší než dva, ne, tak jsem se přistoupit k bloku jiného znovu. 702 00:32:42,580 --> 00:32:43,900 Seřadit levé polovině prvků. 703 00:32:43,900 --> 00:32:45,608 >> Takže znovu, mentálně, a to je tam, kde 704 00:32:45,608 --> 00:32:49,550 Máte přibývat spoustu duševní historie, chcete-li. 705 00:32:49,550 --> 00:32:51,940 Teď třídění levé polovina z levé poloviny. 706 00:32:51,940 --> 00:32:57,000 Dobře, takže teď volám stejný korespondence algoritmus třídění, n je menší než dva? 707 00:32:57,000 --> 00:33:00,590 Ne, je to dva, takže musím vyřešit levá polovina, a pravou polovinu. 708 00:33:00,590 --> 00:33:02,042 Tak jdeme na to, třídění levé poloviny. 709 00:33:02,042 --> 00:33:03,750 Proč ne jen jeden krok vpřed. 710 00:33:03,750 --> 00:33:04,415 Jak se jmenujete? 711 00:33:04,415 --> 00:33:04,860 >> DIVÁKŮ: Darren. 712 00:33:04,860 --> 00:33:05,260 >> SPEAKER: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan udělal krok vpřed. 714 00:33:06,040 --> 00:33:06,748 >> DIVÁKŮ: Darren. 715 00:33:06,748 --> 00:33:09,000 SPEAKER: Darren, hotovo. 716 00:33:09,000 --> 00:33:10,090 Říkala jste, že Darrena nebo Dan? 717 00:33:10,090 --> 00:33:10,550 >> DIVÁKŮ: Darren. 718 00:33:10,550 --> 00:33:11,216 >> SPEAKER: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren přistoupil dopředu a on je nyní řazeny. 720 00:33:14,422 --> 00:33:16,130 A to je téměř stupidní tvrzení, že jo? 721 00:33:16,130 --> 00:33:18,862 Nemám opravdu Zdá se, že dosažení něco, ale pojďme pokračovat. 722 00:33:18,862 --> 00:33:20,820 Nyní mi dovolte seřadit právo polovina z těchto prvků. 723 00:33:20,820 --> 00:33:21,200 Jak se jmenujete? 724 00:33:21,200 --> 00:33:21,690 >> DIVÁKŮ: Luke. 725 00:33:21,690 --> 00:33:22,273 >> SPEAKER: Luke. 726 00:33:22,273 --> 00:33:23,400 Pojď, krok vpřed. 727 00:33:23,400 --> 00:33:25,640 Hotovo, jsem řazeny Luku. 728 00:33:25,640 --> 00:33:28,570 Levá polovina je nyní tříděny a pravá polovina je nyní tříděny, 729 00:33:28,570 --> 00:33:30,770 ale zase tam je klíčovým krokem zde. 730 00:33:30,770 --> 00:33:32,940 Co u potřeba udělat? 731 00:33:32,940 --> 00:33:33,941 Sloučit seřazené poloviny. 732 00:33:33,941 --> 00:33:36,648 Nyní budeme prostě muset všichni sem a tam tak, 733 00:33:36,648 --> 00:33:38,620 protože jsem tak trochu potřebovat nějaký odkládací prostor. 734 00:33:38,620 --> 00:33:40,411 Je to skoro, jako jsou tyto kluci jsou na stole, 735 00:33:40,411 --> 00:33:42,460 a já potřebuju nějaký prostor je pohybovat dál. 736 00:33:42,460 --> 00:33:44,170 Takže budu sloučit vy od pohledu 737 00:33:44,170 --> 00:33:45,960 v levé polovině a pravé polovině. 738 00:33:45,960 --> 00:33:48,740 A kdo zřejmě je na prvním místě, vlevo nebo vpravo polovina poloviny? 739 00:33:48,740 --> 00:33:52,710 Takže pravá polovina, takže pojďme Luka nad zde původní polohy Darren. 740 00:33:52,710 --> 00:33:57,640 A teď sloučit jejich levou polovinu v, Darren se bude pohybovat právě tam. 741 00:33:57,640 --> 00:33:59,750 >> Tak se cítí jako téměř bublina druh účinku, 742 00:33:59,750 --> 00:34:02,482 ale moje základní algoritmus, velmi odlišné tentokrát. 743 00:34:02,482 --> 00:34:04,815 Ale teď je místo, kde se věci trochu nepříjemné, protože jste 744 00:34:04,815 --> 00:34:06,810 muset přetočit mentálně kde jsem odejít pryč. 745 00:34:06,810 --> 00:34:09,893 Právě jsem se spojil setříděné poloviny, což znamená, že jsem tam, kde ve svém algoritmu? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Musím vyřešit pravou polovinu, ne? 748 00:34:13,770 --> 00:34:15,910 >> Máte-li vzad, a to doslova na videu, budete 749 00:34:15,910 --> 00:34:18,339 vidět, že jsme se dostali do této bod Luke a Darren 750 00:34:18,339 --> 00:34:21,370 tříděním doleva polovina z levé poloviny. 751 00:34:21,370 --> 00:34:23,430 Pak jsme se spojil ty tříděné poloviny, které 752 00:34:23,430 --> 00:34:27,941 znamená, že dalším krokem je třídění Pravá polovina levé polovině. 753 00:34:27,941 --> 00:34:29,649 Dobře, tak pojďme to rychleji. 754 00:34:29,649 --> 00:34:33,282 Tak jo, šest, budu tvrdit, jste nyní tříděny, pojď dopředu. 755 00:34:33,282 --> 00:34:33,990 Jak se jmenujete? 756 00:34:33,990 --> 00:34:34,589 >> DIVÁKŮ: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> SPEAKER: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano je nyní řazeny. 759 00:34:36,010 --> 00:34:36,450 A Jak se jmenujete? 760 00:34:36,450 --> 00:34:37,080 >> DIVÁKŮ: Alex. 761 00:34:37,080 --> 00:34:38,379 >> SPEAKER: Alex je nyní řazeny. 762 00:34:38,379 --> 00:34:40,750 Levá polovina, pravá polovina, co je poslední krok? 763 00:34:40,750 --> 00:34:41,250 Sloučit. 764 00:34:41,250 --> 00:34:44,310 Docela triviální, takže jsem k fúzi v šesti, 765 00:34:44,310 --> 00:34:46,930 krok zpět, osm, udělat krok zpět. 766 00:34:46,930 --> 00:34:49,530 A teď si toho všimnout je užitečné stánek s jídlem, co 767 00:34:49,530 --> 00:34:53,930 je nyní platí o levé polovině seznam, a to bez ohledu na to, jak jsme začali? 768 00:34:53,930 --> 00:34:55,090 To je tříděn. 769 00:34:55,090 --> 00:34:57,750 >> Teď to není seřazen velký schématu věcí, 770 00:34:57,750 --> 00:35:00,250 ale to je řazen samostatně z druhé poloviny. 771 00:35:00,250 --> 00:35:04,100 A teď, co krok to jsem na tom, zda jsem se udržet převíjení, jak příběh začal? 772 00:35:04,100 --> 00:35:05,680 Teď musím vyřešit pravou polovinu. 773 00:35:05,680 --> 00:35:07,630 Takže teď jsme cestu zpět na začátek příběhu, 774 00:35:07,630 --> 00:35:08,921 a pojďme na to rychleji. 775 00:35:08,921 --> 00:35:11,320 Takže budu třídit pravá polovina celého seznamu. 776 00:35:11,320 --> 00:35:13,060 Jaký je další krok? 777 00:35:13,060 --> 00:35:15,840 Seřadit levou polovinu pravé polovině. 778 00:35:15,840 --> 00:35:18,715 Seřadit levé polovině levá polovina v pravé polovině. 779 00:35:18,715 --> 00:35:19,590 A Jak se jmenujete? 780 00:35:19,590 --> 00:35:20,230 >> DIVÁKŮ: Omar. 781 00:35:20,230 --> 00:35:21,970 >> SPEAKER: Omar, krok vpřed, hotovo. 782 00:35:21,970 --> 00:35:22,860 Levá polovina je tříděn. 783 00:35:22,860 --> 00:35:23,330 A Jak se jmenujete? 784 00:35:23,330 --> 00:35:23,820 >> DIVÁKŮ: Chris. 785 00:35:23,820 --> 00:35:25,620 >> SPEAKER: Chris, krok vpřed, jste nyní řazeny. 786 00:35:25,620 --> 00:35:27,010 Co je klíčovým krokem teď? 787 00:35:27,010 --> 00:35:27,510 Sloučit. 788 00:35:27,510 --> 00:35:30,509 Takže člověk se chystá sloučit své místo zde, pokud byste mohli udělat krok zpět, 789 00:35:30,509 --> 00:35:32,930 a tři se chystá krok zpět, sloučit. 790 00:35:32,930 --> 00:35:38,080 Takže levá polovina Pravá polovina je nyní řazeny. 791 00:35:38,080 --> 00:35:41,747 Upřímně řečeno, tento algoritmus pocit, jako bychom Ztrácíte způsobem více času než dříve, 792 00:35:41,747 --> 00:35:44,830 ale když jsme to udělali v reálném čase, budeme vidět, co takeaways bude. 793 00:35:44,830 --> 00:35:47,970 A teď jsem tady, že jo polovina pravé polovině, 794 00:35:47,970 --> 00:35:50,170 nech mě jít napřed a seřadit levou polovinu. 795 00:35:50,170 --> 00:35:51,482 Krok vpřed, Jak se jmenujete? 796 00:35:51,482 --> 00:35:52,190 DIVÁKŮ: Ramsey. 797 00:35:52,190 --> 00:35:53,210 SPEAKER: Ramsey je nyní řazeny. 798 00:35:53,210 --> 00:35:53,570 Jak se jmenujete? 799 00:35:53,570 --> 00:35:54,200 >> DIVÁKŮ: Marina. 800 00:35:54,200 --> 00:35:57,033 >> SPEAKER: Marina je nyní řazeny jako dobře, pokud budete mít o jeden krok vpřed. 801 00:35:57,033 --> 00:36:00,690 Klíčovým krokem je zde nyní sloučit, jsem bude trhat ze svých dvou seznamů, 802 00:36:00,690 --> 00:36:01,720 vlevo a vpravo. 803 00:36:01,720 --> 00:36:05,150 Pět bude na prvním místě, a sedm se chystá přijít další. 804 00:36:05,150 --> 00:36:06,410 A opět, je to záměrné. 805 00:36:06,410 --> 00:36:08,535 Skutečnost, že užíváte kroky vpřed a vzad 806 00:36:08,535 --> 00:36:12,997 má představovat, že nemůžeme do tohoto algoritmu na místě, jak snadno 807 00:36:12,997 --> 00:36:15,830 jako bublinkové třídění a výběru druhu, a vložení třídění, kde se právě 808 00:36:15,830 --> 00:36:16,960 stále vyměňovat lidí. 809 00:36:16,960 --> 00:36:19,940 Doslova jsem potřebovat jakousi poškrábání papíru, ve kterém 810 00:36:19,940 --> 00:36:21,827 aby tyto lidi když jsem to sloučení, 811 00:36:21,827 --> 00:36:23,410 a pak jsem je dát zpět na místo. 812 00:36:23,410 --> 00:36:27,260 A to je klíč, protože já jsem s použitím nové zdroje, prostor, a to nejen čas. 813 00:36:27,260 --> 00:36:28,270 >> OK, to je úžasné. 814 00:36:28,270 --> 00:36:32,050 Levá polovina je tříděn, pravá polovina je tříděny, teď ten klíč sloučení krok. 815 00:36:32,050 --> 00:36:33,450 Jak to mám sloučit to? 816 00:36:33,450 --> 00:36:35,470 Takže pokud budete následovat mé levá ruka a pravá ruka, 817 00:36:35,470 --> 00:36:38,930 Chystám se ukázat svou levou ruku na levé polovině, moje pravá ruka 818 00:36:38,930 --> 00:36:42,680 v pravé polovině, a teď musím rozhodnout, krok za krokem, kterého se sloučí. 819 00:36:42,680 --> 00:36:44,650 Kdo samozřejmě na prvním místě? 820 00:36:44,650 --> 00:36:45,150 Číslo jedna. 821 00:36:45,150 --> 00:36:47,327 Tak pojď sem, tady je náš poznámkový blok. 822 00:36:47,327 --> 00:36:49,910 Takže teď číslo jedna a oznámení co budu dělat s mou pravou rukou, 823 00:36:49,910 --> 00:36:54,152 Chystám se hýbat pravou rukou jednoho krokem se k bodu číslo tři, 824 00:36:54,152 --> 00:36:55,860 a teď mám udělat Stejné rozhodnutí. 825 00:36:55,860 --> 00:36:58,387 A vlastně stojí přímo v přední Lukáše zde, pokud byste mohli, 826 00:36:58,387 --> 00:36:59,720 protože to je náš poznámkový blok. 827 00:36:59,720 --> 00:37:00,610 Tak kdo je další? 828 00:37:00,610 --> 00:37:05,000 Máme Luke s číslem dvě nebo Chris s číslem tři. 829 00:37:05,000 --> 00:37:07,460 Je zřejmé, Luke, číslo dva, takže se sem. 830 00:37:07,460 --> 00:37:11,270 >> Ale moje levá ruka teď se chystá být zvýšen poukázat na Darrena, 831 00:37:11,270 --> 00:37:15,160 a tady je klíč odnést s sloučení, budu v tom pokračovat, 832 00:37:15,160 --> 00:37:17,340 Je zřejmé, že pokud máte trochu o sledovat logiku. 833 00:37:17,340 --> 00:37:19,670 Ale moje ruce nikdy jít zpět, 834 00:37:19,670 --> 00:37:23,861 což znamená, že jsem jen někdy stěhují do odešel s mým proces sloučení, 835 00:37:23,861 --> 00:37:26,360 a že to bude klíčem k naše analýza za chvíli. 836 00:37:26,360 --> 00:37:27,859 >> Takže teď pojďme dokončit rychle nahoru. 837 00:37:27,859 --> 00:37:31,650 Takže tři přijde příště, pak čtyři přijde příště, 838 00:37:31,650 --> 00:37:38,750 a teď pět přijde příště, pak šest, a sedm a nakonec osm. 839 00:37:38,750 --> 00:37:42,960 Cítím se jako nejpomalejší algoritmus ještě, ale ne v případě, vlastně 840 00:37:42,960 --> 00:37:45,510 nechte jej běžet na stejném druhu o taktovací frekvenci, takže se 841 00:37:45,510 --> 00:37:48,106 mluvit, se stejným tikající hodiny jako předtím. 842 00:37:48,106 --> 00:37:48,605 Proč? 843 00:37:48,605 --> 00:37:51,100 No, pojďme se se podívat na konečný výsledek. 844 00:37:51,100 --> 00:37:56,990 >> Vraťme se tady, dovolte mi, abych vytáhnout demonstraci vizuálně 845 00:37:56,990 --> 00:37:59,030 z toho, co jsme právě udělali. 846 00:37:59,030 --> 00:38:06,110 Zvětšení zde, na tomto strana tady, říká Firefox 847 00:38:06,110 --> 00:38:08,200 že chceme do fronty v tomto poli, pojďme 848 00:38:08,200 --> 00:38:11,260 říkají bublina druh, s nímž teď jsme dobře obeznámeni, 849 00:38:11,260 --> 00:38:14,130 Výběr třídění, což je další poměrně přímočará, 850 00:38:14,130 --> 00:38:18,250 a nyní dnešní merge sort, který bude naše vrcholná konec. 851 00:38:18,250 --> 00:38:21,530 Důvod, proč to trvalo tak dlouho zde s lidmi a já slovně je, 852 00:38:21,530 --> 00:38:23,480 samozřejmě, já jsem vysvětlovat každý krok. 853 00:38:23,480 --> 00:38:26,920 Ale pokud jste jednoduše spusťte tento, moc jako jsme to udělali bubble sort a výběr 854 00:38:26,920 --> 00:38:30,890 třídit nejen vizuálně, hodinky jak mnohem efektivněji 855 00:38:30,890 --> 00:38:33,330 to prosazováním dělení a dobývání 856 00:38:33,330 --> 00:38:39,150 může být při aplikaci do datového souboru, který je Ani velikost osm, ale ještě mnohem, 857 00:38:39,150 --> 00:38:39,970 mnohem větší. 858 00:38:39,970 --> 00:38:44,585 Dám vám sloučit druh, vedle strana s těmito dalšími algoritmy. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 To dostane bolestivé rychle, a konec 861 00:38:58,530 --> 00:39:00,890 není nijak zvlášť vrcholná, prostě skončit řazeny. 862 00:39:00,890 --> 00:39:05,280 Ale klíč odnést je, že Podívej se, jak daleko rychleji sloučit druh 863 00:39:05,280 --> 00:39:08,110 byl, pokud si myslíte, že jsem jen tak si s vámi. 864 00:39:08,110 --> 00:39:13,100 Pokud se nám tento jeden poslední čas, pojďme znovu to, vraťme 865 00:39:13,100 --> 00:39:14,960 a zvolte bubliny druhu, a jen tak pro legraci, 866 00:39:14,960 --> 00:39:17,330 Zvolme vložení třídění, jen pro jistotu. 867 00:39:17,330 --> 00:39:20,020 A tentokrát opět, pojďme vyberte slučovací druh a pojďme 868 00:39:20,020 --> 00:39:21,595 vlastně spustit tyto bok po boku. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> A to není, ve skutečnosti, náhoda. 871 00:39:26,930 --> 00:39:31,140 Co jsem skutečně udělal je, že jsem rozdělit svůj vstup na polovinu, opět 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 jen tolikrát můžete rozdělit váš vstup do poloviny, levá 874 00:39:35,590 --> 00:39:36,240 a vpravo. 875 00:39:36,240 --> 00:39:39,425 Jaký je vzorec, který držíme vidět , který popisuje rozdělení na dvě poloviny 876 00:39:39,425 --> 00:39:41,050 znovu a znovu, a znovu, a znovu? 877 00:39:41,050 --> 00:39:41,890 >> Diváků: log n. 878 00:39:41,890 --> 00:39:42,760 >> SPEAKER: log n. 879 00:39:42,760 --> 00:39:46,300 Ale pak je tu ještě jedna další klíčový krok, Tento algoritmus není přihlášena n kroků. 880 00:39:46,300 --> 00:39:48,992 Pokud by bylo jen přihlásit n kroků, bychom být ve stejném problému 881 00:39:48,992 --> 00:39:51,200 jako dříve, kde nemůže být že všechno je třídit. 882 00:39:51,200 --> 00:39:54,480 Musíte se minimálně podívat na n prvků být jisti, že n prvky jsou tříděny, 883 00:39:54,480 --> 00:39:55,950 jinak je to skok víry. 884 00:39:55,950 --> 00:39:59,810 >> Takže je to minimálně log n kroky, ale co této klíčové sloučení kroku 885 00:39:59,810 --> 00:40:04,370 kde jsem se spojil moje levá polovina a doprava poloviny a přešel přes jeviště? 886 00:40:04,370 --> 00:40:06,980 Kolik kroků je sloučit? 887 00:40:06,980 --> 00:40:10,150 Je to n, ale neudělal jsem to jen sloučit konečný čas. 888 00:40:10,150 --> 00:40:15,089 Na každé z těchto vnořených volání, na každém z těchto vnořených slučování, přesto jsem řazeny. 889 00:40:15,089 --> 00:40:18,380 I sloučil tyto dva chlápky, pak se tyto dvě kluci, pak tihle dva, a tak dále. 890 00:40:18,380 --> 00:40:19,955 >> Tak jsem se sloučení znovu a znovu. 891 00:40:19,955 --> 00:40:20,580 Kolikrát? 892 00:40:20,580 --> 00:40:23,510 Takže pokaždé, když jsem se rozdělil seznam na polovinu, jsem sloučení. 893 00:40:23,510 --> 00:40:25,460 Rozdělte seznam na dvě poloviny, do sloučení. 894 00:40:25,460 --> 00:40:28,570 Takže v případě, dělení seznam může být provedeno log n krát, 895 00:40:28,570 --> 00:40:33,880 a sloučení nakonec se n kroky, co by mohlo být nyní horní 896 00:40:33,880 --> 00:40:37,000 vázána na chod Doba našeho 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, co jsme tu dosáhli. 899 00:40:40,560 --> 00:40:44,650 Takže myslíte, že jste vidět vizuálně, když tyto tři věci běží bok po boku 900 00:40:44,650 --> 00:40:47,930 je n na druhou proti n na druhou proti n log n. 901 00:40:47,930 --> 00:40:51,010 Které zásadním uvidíme, nejen dnes, ale v budoucnu, 902 00:40:51,010 --> 00:40:52,760 je mnohem, mnohem rychleji. 903 00:40:52,760 --> 00:40:56,010 Potlesk pro tyto lidi, Já se za to odmění Antistresové míčky. 904 00:40:56,010 --> 00:41:00,260 Pojďme odložit dnes, a Vás budeme vidět v pondělí. 905 00:41:00,260 --> 00:41:02,255