1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> SPEAKER: Olgu, see on CS50. 3 00:00:14,910 --> 00:00:19,020 See on nädala lõpuks kolm, ja kui Te ei ole kasutanud juba, 4 00:00:19,020 --> 00:00:21,790 tean, et seal on lõunasöögi Selle reede nagu tavaliselt, kus 5 00:00:21,790 --> 00:00:25,430 saate nautida head vestlust ja toidu Fire ja Ice 6 00:00:25,430 --> 00:00:27,980 mõned CS50 on töötajate ja klassikaaslastega. 7 00:00:27,980 --> 00:00:30,170 Head selle URL siia. 8 00:00:30,170 --> 00:00:33,420 >> Nüüd te võib-olla mäletate, või sa võib peagi tundma, 9 00:00:33,420 --> 00:00:35,970 neid asju siin, mis antakse välja lõpuks 10 00:00:35,970 --> 00:00:37,850 Euroopa poolaasta paljudes klassides. 11 00:00:37,850 --> 00:00:40,870 Niinimetatud eksami sinine raamatud, kus Sa kirjutad oma vastused eksamid. 12 00:00:40,870 --> 00:00:44,240 Nüüd on mul siin 26 sellist sinine raamatud, igal neist 13 00:00:44,240 --> 00:00:47,580 on kirjutatud nimi, kuni Z. Ja tõepoolest nimed on nii lihtne, 14 00:00:47,580 --> 00:00:50,490 läbi Z. Ja üks eesmärke käepärast täna 15 00:00:50,490 --> 00:00:53,910 saab olema jätkata, mis meil algas esmaspäeval, mis ei ole 16 00:00:53,910 --> 00:00:57,830 nii palju, vaadates koodi, kuid tegelikult vaadates ideid ja probleemide lahendamine. 17 00:00:57,830 --> 00:01:00,170 Üks eesmärke ja lubadusi selle kursuse 18 00:01:00,170 --> 00:01:02,985 on õpetada teid mõtlema hoolikalt, rohkem metoodiliselt, 19 00:01:02,985 --> 00:01:05,400 ja lahendada probleeme tõhusamalt. 20 00:01:05,400 --> 00:01:09,526 Ja tõepoolest, me saame teha, et tegelikult ilma et isegi liigutav rida koodi. 21 00:01:09,526 --> 00:01:12,150 Nii et mul on paar elevanti täna siin, oranž ja sinine, 22 00:01:12,150 --> 00:01:15,780 Kui me saaksime ühe vabatahtliku, äkki kaugemalt tagasi kui tavaliselt. 23 00:01:15,780 --> 00:01:18,070 Kuidas seal, tule alla. 24 00:01:18,070 --> 00:01:24,180 Eesmärk, mis saab olema aitab lisaks manustada selle eksami siin. 25 00:01:24,180 --> 00:01:24,935 Mis su nimi on? 26 00:01:24,935 --> 00:01:25,768 >> Sihtrühm: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 SPEAKER: Mary Beth, tule üles. 28 00:01:27,560 --> 00:01:29,560 Las ma mikrofoni siin teile. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Meeldiv kohtuda. 31 00:01:32,880 --> 00:01:34,005 >> Sihtrühm: Meeldiv kohtuda. 32 00:01:34,005 --> 00:01:36,790 SPEAKER: Olgu, ma pean siin sinine raamatud läbi Z, 33 00:01:36,790 --> 00:01:41,680 ja ma teesklen, et Mul on üks üliõpilased, 34 00:01:41,680 --> 00:01:45,770 ja nad tulevad üsna juhuslikult aasta lõpus kolme tunni eksam blokaad, 35 00:01:45,770 --> 00:01:49,400 nii nad jõuavad teatud semi-juhuslikus järjekorras niimoodi. 36 00:01:49,400 --> 00:01:54,510 Nüüd teie töö on ainult hetk läheb olema-- see on tegelikult, kuidas nad saavad 37 00:01:54,510 --> 00:01:56,820 lahkus lõpus klass, kõige tõenäolisem. 38 00:01:56,820 --> 00:02:01,120 Sinu töö nüüd saab olema üsna lihtsalt, et sorteerida need sinine raamatuid meile 39 00:02:01,120 --> 00:02:05,220 alates kuni Z. 40 00:02:05,220 --> 00:02:08,400 >> Sihtrühm: Oh, see on kavatseme igavesti. 41 00:02:08,400 --> 00:02:13,747 >> SPEAKER: Ja me vaadata kui sa seda teed, ei rõhu. 42 00:02:13,747 --> 00:02:15,330 Sihtrühm: Ei, mingit survet või midagi. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> SPEAKER: Ja lõbu, paneme üles ehitatud taimer. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> Sihtrühm: nii lõbus, nii lõbus. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> SPEAKER: ma ei hoia mic teile. 49 00:02:38,574 --> 00:02:40,240 Olgu, me oleme lihtsalt kahekordistunud meie kiirus. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Nii et vahepeal, andke mulle kujutada, mida on saab olema küsimus Mary Beth 52 00:02:49,060 --> 00:02:51,540 on see, mida ta teeb, kuidas on Ta läheb umbes lahendada see? 53 00:02:51,540 --> 00:02:54,040 Ja tegelikult, ei pruugi teil olla kunagi mõelnud midagi 54 00:02:54,040 --> 00:02:57,440 nii lihtne, kui valite kuni 26 raamatut niimoodi, 55 00:02:57,440 --> 00:02:59,350 mis ei ole loomulik tellimisel neile. 56 00:02:59,350 --> 00:03:01,335 Mis on protsess mida te kasutate? 57 00:03:01,335 --> 00:03:03,770 Kas see on üsna juhuslik lihtsalt korjamine esimene näete 58 00:03:03,770 --> 00:03:05,250 ja panna see oma koht? 59 00:03:05,250 --> 00:03:09,680 Kas te esmalt liigutada oma käsi ümber otsin siis otsin B? 60 00:03:09,680 --> 00:03:11,722 Kas te võtate pilk paari neid kõrvuti 61 00:03:11,722 --> 00:03:14,680 ja lihtsalt öelda, oota, see ei ole õige, ja siis swap järjekorras? 62 00:03:14,680 --> 00:03:16,960 Nägime juba esmaspäeval et seal on mitmeid viise 63 00:03:16,960 --> 00:03:22,140 kus me saame seda teha, ja tõepoolest, kui me lähedal lõpuks siin, 64 00:03:22,140 --> 00:03:26,360 Võtaksin teadmiseks ehk mida Mary Beth teeb. 65 00:03:26,360 --> 00:03:30,040 Meil on mõned vaiad tundub, suurem üks, kolm väiksemad. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> Sihtrühm: käsin ma neid kui ma leian kaks tähte 68 00:03:36,415 --> 00:03:39,540 et ma tean, et on koos jada, Ma panin need kokku, nii et ma ei 69 00:03:39,540 --> 00:03:42,915 pea muretsema hoida jälgida kogu rida raamatuid. 70 00:03:42,915 --> 00:03:45,706 See on lihtsalt, oh, on esimene, Mul on see korstna siin. 71 00:03:45,706 --> 00:03:47,580 SPEAKER: Niisiis, peaaegu nagu puzzle tükki, et 72 00:03:47,580 --> 00:03:49,860 on õige kujuga kohakuti üksteist. 73 00:03:49,860 --> 00:03:51,026 Sihtrühm: Päris palju, jah. 74 00:03:51,026 --> 00:03:55,320 SPEAKER: OK, väga hea. 75 00:03:55,320 --> 00:03:59,850 Ja nüüd iga nimetatud vaiad on arvatavasti järjestatud? 76 00:03:59,850 --> 00:04:00,990 >> Sihtrühm: Jah. 77 00:04:00,990 --> 00:04:09,900 >> SPEAKER: Olgu, läbi Z. Kõik Olgu, palju õnne, sa tegid seda. 78 00:04:09,900 --> 00:04:11,461 Sul on valik. 79 00:04:11,461 --> 00:04:11,960 Blue? 80 00:04:11,960 --> 00:04:13,530 Olgu, tänan teid selle eest. 81 00:04:13,530 --> 00:04:16,679 Seega ei saa Mary Beth ei ettepanekud mida tema lähenemine oli 82 00:04:16,679 --> 00:04:19,720 aga mis on teine ​​lähenemine, kuidas te võiks minna sorteerimine neid asju? 83 00:04:19,720 --> 00:04:21,130 Mida te olete teinud? 84 00:04:21,130 --> 00:04:24,060 Rekord võita oleks olnud üks minut ja 50 või nii sekundi 85 00:04:24,060 --> 00:04:26,039 pluss need, ma unustasin loota. 86 00:04:26,039 --> 00:04:27,080 Mida te olete teinud? 87 00:04:27,080 --> 00:04:27,579 Jah? 88 00:04:27,579 --> 00:04:28,735 Sihtrühm: Võtke pinu. 89 00:04:28,735 --> 00:04:29,776 Alusta algusest. 90 00:04:29,776 --> 00:04:32,284 Kontrolli oma paberid. 91 00:04:32,284 --> 00:04:36,586 Ja kui ülemine on suurem kui, äkki on need, 92 00:04:36,586 --> 00:04:38,980 alt üks on kõrgem, siis lüliti neid. 93 00:04:38,980 --> 00:04:41,300 >> SPEAKER: OK, nii algab ülaosas ja allosas, 94 00:04:41,300 --> 00:04:43,716 ja seejärel töö teed sissepoole nagu, et vahetada neid? 95 00:04:43,716 --> 00:04:46,580 OK, nii et natuke sarnane vaimus, et mull sorteerida, 96 00:04:46,580 --> 00:04:49,160 kuid valides äärmuse ei külgneva paari. 97 00:04:49,160 --> 00:04:52,080 Aga lühike on see, et seal on kindlasti hunnik erinevaid viise 98 00:04:52,080 --> 00:04:54,210 me võiks seda teha, ja ausalt öeldes, ma arvan, et sa selline 99 00:04:54,210 --> 00:04:55,700 vastu paar lähenemisviise, eks? 100 00:04:55,700 --> 00:05:00,567 Tegid mingi neli sorteeritud vaiad, ja siis tõhusalt ühendada neid koos. 101 00:05:00,567 --> 00:05:02,650 Ja see, daresay teine tehnikat kokku. 102 00:05:02,650 --> 00:05:06,950 Sa ei käsitle seda nagu üks suur hunnik, sa jagada probleem neljaks ATVde, 103 00:05:06,950 --> 00:05:09,820 kui soovite, ja siis kuidagi liitis need lõpuks. 104 00:05:09,820 --> 00:05:13,410 >> Nii Vaatleme lõpuks kuidas muidu me võiksime seda teha. 105 00:05:13,410 --> 00:05:15,860 Me formaliseeritud mõiste mull omamoodi viimane kord, 106 00:05:15,860 --> 00:05:18,780 ja mull omamoodi tagasikutsumine algoritm, mis me visualiseerida 107 00:05:18,780 --> 00:05:22,640 kaheksa oma klassikaaslastega siin, pealtnäha juhuslikult järjestatud alguses. 108 00:05:22,640 --> 00:05:26,110 Ja siis otsustasime paarikaupa, kui kaks tegurit on rikkis, 109 00:05:26,110 --> 00:05:26,950 lihtsalt vahetada neid. 110 00:05:26,950 --> 00:05:28,930 Nii et neli ja kaks on ilmselt rikkis, 111 00:05:28,930 --> 00:05:31,080 Nii et need kaks klassikaaslased vahetas kohad. 112 00:05:31,080 --> 00:05:35,390 Ja siis me korrata neli ja kuus, siis kuus kuni kaheksa, iga iteratsiooni 113 00:05:35,390 --> 00:05:36,980 liigub paremale. 114 00:05:36,980 --> 00:05:42,590 >> Nii et antud kaheksa inimest, kui palju paarikaupa võrdlusi ma tegin käies alates 115 00:05:42,590 --> 00:05:45,220 vasakult paremale üks selline iteratsiooni? 116 00:05:45,220 --> 00:05:48,410 Mitu võrrelda? 117 00:05:48,410 --> 00:05:49,197 Seven, eks? 118 00:05:49,197 --> 00:05:51,405 Sest kui seal on kaheksa inimesi, kuid teil on paar 119 00:05:51,405 --> 00:05:53,880 neid ja te edasi liikuda üks hop paremale, 120 00:05:53,880 --> 00:05:56,060 sa ei kavatse on kaheksa võrdlusi, sest sa ei saa võrrelda 121 00:05:56,060 --> 00:05:59,226 element iseenda vastu, või oleks see lihtsalt mõttetu, nii et teil on seitse. 122 00:05:59,226 --> 00:06:01,290 Või üldisemalt kui meil n inimesed, me 123 00:06:01,290 --> 00:06:04,300 teha n miinus 1 võrdlused Bubble sort. 124 00:06:04,300 --> 00:06:08,150 >> Nii Vaatleme nüüd, kuidas hea või halb mull omamoodi tegelikult oli, ja proovige 125 00:06:08,150 --> 00:06:13,570 andma endale sõnavara mis on kriitika algoritme nagu see, 126 00:06:13,570 --> 00:06:14,430 ja varsti meie oma. 127 00:06:14,430 --> 00:06:16,970 Nii esimese läbida mull sorteerida, esimest korda 128 00:06:16,970 --> 00:06:20,909 Läksin vasakult paremale üle etapis võttis mind n miinus 1 võrdlusi. 129 00:06:20,909 --> 00:06:22,950 Ja see saab olema minu mõõtühik, eks? 130 00:06:22,950 --> 00:06:26,170 Ma nagu räägin ja uitav, veidi kiire, veidi aeglane, 131 00:06:26,170 --> 00:06:29,300 nii lugedes minu number sekundiga ei ole eriti tähenduslik, 132 00:06:29,300 --> 00:06:32,260 kuid loendades toiminguid, mis ma tegin esmaspäeval, 133 00:06:32,260 --> 00:06:35,900 võrrelda kahte inimest, kes tunneb tore mõõtühik. 134 00:06:35,900 --> 00:06:40,980 >> Nii n miinus 1 punkte esmakordselt aga mis siis juhtus pärast seda? 135 00:06:40,980 --> 00:06:46,610 Mis on üks tagurpidi ühe söödu läbi muidu sorteerimata nimekirja? 136 00:06:46,610 --> 00:06:49,840 Mida saab räägi mulle element kes oli kogu tee seal? 137 00:06:49,840 --> 00:06:51,300 Jah? 138 00:06:51,300 --> 00:06:52,870 See oli suurim osa, eks? 139 00:06:52,870 --> 00:06:55,710 Number kaheksa, kuigi ta algas siin, iga kord, kui ma 140 00:06:55,710 --> 00:06:57,860 võrreldes tema vastu naaber, ta hoida 141 00:06:57,860 --> 00:07:00,480 vahustamine kuni õige servas nimekirja. 142 00:07:00,480 --> 00:07:02,710 Ja tõepoolest, see on kui Algoritmi saab oma nime. 143 00:07:02,710 --> 00:07:07,630 >> Nüüd selle loogika, kui palju võrdlusi pea ma omale teist korda 144 00:07:07,630 --> 00:07:09,800 Ma teen selle käigu vasakult paremale? 145 00:07:09,800 --> 00:07:10,730 n miinus 2, eks? 146 00:07:10,730 --> 00:07:14,297 See oleks lihtsalt raiskad oma aega, kui ma hoida võrreldes kaheksa kellegi vastu 147 00:07:14,297 --> 00:07:16,630 muud, sest me juba teame ta oli õiges kohas. 148 00:07:16,630 --> 00:07:19,760 Nii et see on natuke optimeerimist, nii järgmisel liigu 149 00:07:19,760 --> 00:07:23,899 saab olema pluss n miinus kaks sammu, kus n on hulk inimesi. 150 00:07:23,899 --> 00:07:26,940 Nüüd saad liiki üldistusi, isegi kui sa ei ole arvuti teadlane, 151 00:07:26,940 --> 00:07:27,680 kuidas see lõpeb. 152 00:07:27,680 --> 00:07:31,259 Lõpus see algoritm, arvatavasti sul on lihtsalt üks võrdlus vasakule. 153 00:07:31,259 --> 00:07:33,800 Sa pead liiki määrata loendi alguses, kui kaks 154 00:07:33,800 --> 00:07:36,540 ja üks on rikkis ning peaks olema üks ja kaks, 155 00:07:36,540 --> 00:07:40,330 nii see põhjani läbi pluss 1 lõplik võrdlus. 156 00:07:40,330 --> 00:07:44,500 >> Nüüd dot, dot, dot tüüpi lained on käed mõned mahlasem üksikasjad, 157 00:07:44,500 --> 00:07:46,452 kuid olgem lihtsalt minna ja lihtsustada. 158 00:07:46,452 --> 00:07:48,660 Kui te mäletate kõrge kooli, ausalt, palju sa 159 00:07:48,660 --> 00:07:50,340 oli matemaatika raamatuid, mis olid vähe petma lehte 160 00:07:50,340 --> 00:07:52,550 Esikaanel on või tagakaas, mis näitas sulle 161 00:07:52,550 --> 00:07:56,400 Mis seeria kohtuvaidlust nagu Selle lõpuks liita. 162 00:07:56,400 --> 00:07:59,600 Üldises juhul, kui teil on varieeruv nagu n ja tõepoolest see üks, 163 00:07:59,600 --> 00:08:01,634 kui sa vaatasid oma vana kooli matemaatika raamat, 164 00:08:01,634 --> 00:08:04,050 sa näeksid, et see tegelikult lisab kuni selle summa siin 165 00:08:04,050 --> 00:08:07,970 n korda n miinus 1 kõik jagatud 2. 166 00:08:07,970 --> 00:08:11,172 Nii et nüüd las ma ette näha, see on tõsi, et on liigaasta usu, 167 00:08:11,172 --> 00:08:12,880 see on, mida see võtab kuni, ja me võiksime 168 00:08:12,880 --> 00:08:14,341 tõestada, et üldisemal juhul. 169 00:08:14,341 --> 00:08:15,590 Aga nüüd lähme laiendada seda. 170 00:08:15,590 --> 00:08:19,920 Korrutame selle välja, nii et see n ruudus miinus n, kõik jagatud 2. 171 00:08:19,920 --> 00:08:23,200 See on tõesti n ruudus jagatud 2 miinus n üle 2 172 00:08:23,200 --> 00:08:25,010 nii et kõik on tore ja huvitav. 173 00:08:25,010 --> 00:08:27,060 Aga mis juhtub siis, kui me nüüd plug-in väärtust? 174 00:08:27,060 --> 00:08:29,724 Oletame, et ma ei ole kaheksa inimesi, kuid öelda miljonit. 175 00:08:29,724 --> 00:08:31,890 Ja miljonit lihtsalt sellepärast, see on päris suur arv, 176 00:08:31,890 --> 00:08:34,039 olgem pistik, et ja vaata, mis juhtub. 177 00:08:34,039 --> 00:08:39,039 Nii et kui ma ühendan miljonit sellesse valem Ma lähen miljonit ruudus, 178 00:08:39,039 --> 00:08:42,868 jagatud 2 miinus miljonit eurot, mis on jagatud 2. 179 00:08:42,868 --> 00:08:44,159 Mis nüüd, et läheb võrdsed? 180 00:08:44,159 --> 00:08:47,354 Nii et 500 miljardit miinus 500,000. 181 00:08:47,354 --> 00:08:49,270 Ja kui ma tegelikult teha et matemaatika läbi, et vahend 182 00:08:49,270 --> 00:08:53,920 sorteerimise miljonit inimeste mull omamoodi 183 00:08:53,920 --> 00:09:01,800 võib võtta mind 499999500000 meetmeid või võrdlusi eesmärgil 184 00:09:01,800 --> 00:09:02,900 me lihtsalt ekstrapoleerimisel. 185 00:09:02,900 --> 00:09:06,860 >> See tundub üsna aeglane, kuid ausalt öeldes mõõtes ühe teatava sisendi 186 00:09:06,860 --> 00:09:09,160 nagu see, ei ole nii kõnekas. 187 00:09:09,160 --> 00:09:14,050 Aga tõesti see oletada, et kui n muutub suuremaks ja suuremaks, seda algoritmi 188 00:09:14,050 --> 00:09:16,280 selline enesetunne halveneb ja hullem, või sa tõesti 189 00:09:16,280 --> 00:09:20,450 enesetunne valu, et astendamine, et n ruudus 190 00:09:20,450 --> 00:09:21,770 mis lisab kuni päris kiire. 191 00:09:21,770 --> 00:09:25,340 Ja see detail ei ole kadunud inimesed tegelikult 192 00:09:25,340 --> 00:09:29,640 mõned aastad tagasi teatud senaator, kes oli agitatsiooni, istus intervjuu 193 00:09:29,640 --> 00:09:32,180 Google'i Eric Schmidt, tegevjuht ajal, 194 00:09:32,180 --> 00:09:36,380 ja oli vaidlustada küsimus meelega uurime täna. 195 00:09:36,380 --> 00:09:38,468 Võtame pilk. 196 00:09:38,468 --> 00:09:45,280 >> [VIDEO PLAYBACK] 197 00:09:45,280 --> 00:09:48,560 >> -Senaator, Et sa siin oled Google, ja mulle meeldib 198 00:09:48,560 --> 00:09:53,382 mõelda eesistujariigi nagu tööintervjuu. 199 00:09:53,382 --> 00:09:56,434 Nüüd on raske saada töö presidendina 200 00:09:56,434 --> 00:09:58,100 ja sa lähed läbi külmavärinad nüüd. 201 00:09:58,100 --> 00:10:01,860 Samuti on raske saada tööd Google. 202 00:10:01,860 --> 00:10:05,490 Meil on küsimusi, ja me Küsi meie kandidaatide küsimusi, 203 00:10:05,490 --> 00:10:09,770 ja see üks on Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 Mida-- te arvate, et ma olen nalja, see on siin. 205 00:10:14,760 --> 00:10:17,930 Mis on kõige tõhusam viis sorteeri miljonit 32-bitise täisarvu? 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 >> Mul on kahju, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Ei, ei, ei. 210 00:10:27,400 --> 00:10:30,700 Ma arvan, et mull omamoodi oleks vale tee. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> Tule, kes rääkis talle seda? 213 00:10:38,180 --> 00:10:40,590 Ma ei näe arvuti Teadus oma taustast. 214 00:10:40,590 --> 00:10:42,130 >> -Meil Meie spioonid on. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Olgem küsida erinevat intervjuu küsimus. 217 00:10:48,444 --> 00:10:49,300 >> [END VIDEO PLAYBACK] 218 00:10:49,300 --> 00:10:52,290 >> SPEAKER: Nii räägivad konkreetsed numbrid küll, 219 00:10:52,290 --> 00:10:53,890 ei kavatse olla kõik, mis kasulik. 220 00:10:53,890 --> 00:10:56,810 See ei ole elu õppetund, et mull sort, arvestades miljonit sisendite 221 00:10:56,810 --> 00:10:58,590 võib võtta nii palju kui 500 miljardit samme. 222 00:10:58,590 --> 00:11:01,120 Sa ei saa tõesti üldistada liiga tõhusalt, et 223 00:11:01,120 --> 00:11:03,560 ja teha head disaini otsuseid kirjutamise programme. 224 00:11:03,560 --> 00:11:07,070 Nii et olgem keskenduda sellele, kuidas me võiks seda lihtsustada tulemus. 225 00:11:07,070 --> 00:11:11,780 >> Nii et ma olen Kollased siin tulemusena n ruudus jagatud 2 226 00:11:11,780 --> 00:11:14,330 nii miljoni ruuduline jagatuna 2, ja seejärel 227 00:11:14,330 --> 00:11:16,710 Olen rõhutanud, mida lõplik vastus oli 228 00:11:16,710 --> 00:11:20,180 kui me lahutatakse maha n jagatud 2. 229 00:11:20,180 --> 00:11:24,850 Ja väide Ma teen praegu, kes kurat huvitab, kui sa lahutad maha 230 00:11:24,850 --> 00:11:30,060 natuke vana n üle 2 mil esimene Osa selle valem on nii palju suurem? 231 00:11:30,060 --> 00:11:33,910 Domineerib muu perspektiivis n ruudus jagatud 2 232 00:11:33,910 --> 00:11:37,510 on nii palju suurem, selgelt, kui n saab suur nagu miljon, 233 00:11:37,510 --> 00:11:41,450 see on tõesti suur vahe juures lõpu päeval vahemikus 500 miljardit 234 00:11:41,450 --> 00:11:45,730 ja 499999500000? 235 00:11:45,730 --> 00:11:46,349 Mitte eriti. 236 00:11:46,349 --> 00:11:48,640 Ja nii me läheme teha kui arvuti teadlased on 237 00:11:48,640 --> 00:11:53,270 ignoreerida neid madalamat järku tingimused ja võtta midagi sellist ja tegelikult 238 00:11:53,270 --> 00:11:56,050 lihtsalt lihtsustab see termin, mis läheb midagi. 239 00:11:56,050 --> 00:12:00,315 Suurem meie andmekogud saada, seda suurem Meie andmebaasis saada, rohkem veebilehti 240 00:12:00,315 --> 00:12:02,690 meil otsida, seda enam sõpru sul on Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Nagu n muutub suuremaks, et me oleme tõesti läheb hooli suurim 242 00:12:07,340 --> 00:12:11,560 perspektiivis sellise analüüsi meie algoritmide jõudlust. 243 00:12:11,560 --> 00:12:16,230 Ja ma ütlen, et tead, mida, mull sorteerida on suurusjärgus suur O, 244 00:12:16,230 --> 00:12:18,060 suurusjärgus n ruudus. 245 00:12:18,060 --> 00:12:20,090 See pole just n ruuduline nagu me oleme näinud, 246 00:12:20,090 --> 00:12:22,060 kuid kes tõesti hoolib umbes väiksematele mõttes 247 00:12:22,060 --> 00:12:24,390 ja ausalt, kes tegelikult huvitab, kui me jagame 2? 248 00:12:24,390 --> 00:12:25,870 See on lihtsalt konstandiks. 249 00:12:25,870 --> 00:12:29,480 Ja on 500 miljardit versus 250 miljardit tõesti nii suur probleem? 250 00:12:29,480 --> 00:12:32,190 Ma ei suutnud lihtsalt ootama ühe aasta, lase mu arvuti sõna otseses mõttes 251 00:12:32,190 --> 00:12:34,810 saada kaks korda kiiremini riistvara, ja et mingisugune vahe 252 00:12:34,810 --> 00:12:36,650 lihtsalt kaob aja jooksul loomulikul teel. 253 00:12:36,650 --> 00:12:39,300 >> Mida me hoolime on väljendus, osa 254 00:12:39,300 --> 00:12:42,489 väljend, mis läheb muutuda kui meie panus muutub suuremaks ja suuremaks. 255 00:12:42,489 --> 00:12:45,280 Ja tõepoolest, reaalses maailmas, see on, mida juhtub üha 256 00:12:45,280 --> 00:12:48,330 on sisendid meie probleemidele ja algoritmid on üha suurem. 257 00:12:48,330 --> 00:12:53,470 Nii suur O saab olema märge, asümptootiliseks märke, et me lihtsalt 258 00:12:53,470 --> 00:12:57,160 kasutada arvuti teadlased, et kirjeldada täitmisel või sõiduaega, 259 00:12:57,160 --> 00:12:58,130 ning algoritm. 260 00:12:58,130 --> 00:13:00,800 Nii et saame võrrelda algoritmide erinevates arvutites kirjutatud 261 00:13:00,800 --> 00:13:04,170 erinevad inimesed, kasutades mõned täiesti sarnane mõõdik 262 00:13:04,170 --> 00:13:07,557 nagu võrdluste arv oled tegemist, või äkki arvu vahetustehingud 263 00:13:07,557 --> 00:13:08,140 sa teed. 264 00:13:08,140 --> 00:13:11,910 >> Mida me ei kavatse arv on aja 265 00:13:11,910 --> 00:13:13,981 mis läbib kella seinal tavaliselt. 266 00:13:13,981 --> 00:13:16,230 Mida me ei hakka muretsema umbes kui palju mälu 267 00:13:16,230 --> 00:13:17,820 te kasutate täna vähemalt, kuigi see on 268 00:13:17,820 --> 00:13:19,370 teine ​​ressurss võiksime mõõta. 269 00:13:19,370 --> 00:13:23,610 Me läheme püüdma rajada oma analüüse just põhilisi toiminguid, need, 270 00:13:23,610 --> 00:13:25,930 ausalt, et sa näed kõige visuaalselt. 271 00:13:25,930 --> 00:13:30,700 Nii et midagi nagu suur O n ruuduline, Väidan, et O n ruudus 272 00:13:30,700 --> 00:13:35,820 on ülemise piiri niinimetatud sõiduaega mull omamoodi. 273 00:13:35,820 --> 00:13:38,820 Teisisõnu, kui te tahtsin väita, et seal on 274 00:13:38,820 --> 00:13:41,370 see ülemine piir, kui palju samme algoritm võib võtta, 275 00:13:41,370 --> 00:13:46,240 see saab olema suur O n ruudus sel juhul ülemise. 276 00:13:46,240 --> 00:13:49,710 >> Mis siis, kui ma selle asemel muuta lugu olla ei räägi mull sorteerida, 277 00:13:49,710 --> 00:13:50,910 aga selle ülemise. 278 00:13:50,910 --> 00:13:54,030 Kas te arvate algoritm et me vaatasime juba 279 00:13:54,030 --> 00:13:59,530 mille ülemine piir, maksimaalne mõõta aega või toiminguid, 280 00:13:59,530 --> 00:14:04,300 oleks öelnud, et olla piiratud n, lineaarne funktsioon, 281 00:14:04,300 --> 00:14:07,260 ei quadratic üks, mis on kaardus? 282 00:14:07,260 --> 00:14:10,780 Mis on algoritm, mis alati ei kesta 283 00:14:10,780 --> 00:14:12,860 kui nagu n samme, või 2n samme või 3n sammud? 284 00:14:12,860 --> 00:14:13,360 Jah? 285 00:14:13,360 --> 00:14:15,030 >> Sihtrühm: Leida Kõige rohkem on nimekirjas? 286 00:14:15,030 --> 00:14:16,930 >> SPEAKER: Perfect leidmine Kõige rohkem nimekirjas. 287 00:14:16,930 --> 00:14:18,940 Kui mulle on antud nimekiri inimesed näiteks 288 00:14:18,940 --> 00:14:21,440 igaüks, kes hoiab number, Mis on maksimaalne arv 289 00:14:21,440 --> 00:14:23,770 samme peaks ta mulle, mõistlikult arukas inimene, 290 00:14:23,770 --> 00:14:27,530 leida suurim isik selles nimekirjas? 291 00:14:27,530 --> 00:14:28,100 n, eks? 292 00:14:28,100 --> 00:14:31,320 Sest halvimal juhul, kui võivad suurim väärtus olla? 293 00:14:31,320 --> 00:14:32,700 Right, kõik viis lõpuks. 294 00:14:32,700 --> 00:14:34,575 Nii et halvimal juhul ülemist piiri, ma võiks 295 00:14:34,575 --> 00:14:36,450 pean minema kogu tee siin ja olla nagu, 296 00:14:36,450 --> 00:14:39,170 oh, siin on number kaheksa, või mis iganes, et väärtus on. 297 00:14:39,170 --> 00:14:41,330 Nüüd see oleks lihtsalt rumal kui ma elus hoida, eks? 298 00:14:41,330 --> 00:14:43,840 Otsite rohkem ja rohkem elemente kui viimane neist on seal? 299 00:14:43,840 --> 00:14:45,340 Nii kindlasti, n on ülemine piir. 300 00:14:45,340 --> 00:14:47,420 Ma ei pea võtma rohkem samme kui see. 301 00:14:47,420 --> 00:14:51,580 >> Mis siis, kui selle asemel ma ettepaneku, et on algoritmide selles maailmas, mis 302 00:14:51,580 --> 00:14:57,750 on sõiduaega, mis on piirneb suur O log n log n? 303 00:14:57,750 --> 00:15:00,390 Kus me oleme seda varem näinud? 304 00:15:00,390 --> 00:15:00,890 Jah? 305 00:15:00,890 --> 00:15:03,309 >> Sihtrühm: In telefoniraamat probleem? 306 00:15:03,309 --> 00:15:04,850 SPEAKER: Like telefoniraamatust probleem. 307 00:15:04,850 --> 00:15:07,754 Mis oli mõõta, kui palju aega või kui palju pisaraid ta 308 00:15:07,754 --> 00:15:10,170 võttis mul leida keegi nagu Mike Smith telefoniraamatust? 309 00:15:10,170 --> 00:15:13,212 Oleme väitnud, et see oli samamoodi n ja isegi siis, kui võõras või see, et see on 310 00:15:13,212 --> 00:15:15,170 natuke udune, mida logaritmi või eksponent oli, 311 00:15:15,170 --> 00:15:17,650 Pea meeles, et log n Üldiselt viitab protsessile, 312 00:15:17,650 --> 00:15:20,790 sel juhul, jagades midagi veel pooleks ja jälle 313 00:15:20,790 --> 00:15:25,790 ja uuesti ja uuesti, nii et see muutub üha väike nagu te teete seda. 314 00:15:25,790 --> 00:15:28,470 >> Nii log n viitab, muidugi, telefoniraamat näiteks 315 00:15:28,470 --> 00:15:32,662 kahekomponentsete otsing teoreetiliselt kui me oli virtuaalne uksed laual, 316 00:15:32,662 --> 00:15:34,370 või kui Sean oli otsivad midagi. 317 00:15:34,370 --> 00:15:37,374 Kui ta oli kasutanud binaarne otsing, log n Oleks ülemise kui palju 318 00:15:37,374 --> 00:15:38,040 aega, mis võtab. 319 00:15:38,040 --> 00:15:44,027 Aga need algoritmid, mis jooksis sisse log n oletada milline võti detail? 320 00:15:44,027 --> 00:15:45,360 See loetelu on järjestatud, eks? 321 00:15:45,360 --> 00:15:47,789 Teie algoritm on valesti, kui Teie panus on sorteerimata, 322 00:15:47,789 --> 00:15:49,830 ja veel sa kasutad midagi binaarne otsing 323 00:15:49,830 --> 00:15:51,704 sest te võite hüpata õigus üle element 324 00:15:51,704 --> 00:15:53,600 märkamata, et see on tõepoolest olemas. 325 00:15:53,600 --> 00:15:55,600 >> Nüüd, milline võiks see tähendab, suur O ühe? 326 00:15:55,600 --> 00:15:59,117 See ei tähenda, et teie algoritm võtab üks ja ainult üks samm, 327 00:15:59,117 --> 00:16:01,200 see tähendab, et see võtab pidev mitmeid samme. 328 00:16:01,200 --> 00:16:04,060 Võib-olla see on 1, võib-olla see on 10, võib-olla on see 1000, 329 00:16:04,060 --> 00:16:07,750 aga see on sõltumatu suurus probleem. 330 00:16:07,750 --> 00:16:10,850 Ükskõik kui suur n on konstantse ajaga algoritmi 331 00:16:10,850 --> 00:16:12,747 võtab alati sama arvu. 332 00:16:12,747 --> 00:16:15,080 Niisiis, milline võiks olla algoritm me rääkisime või lihtsalt 333 00:16:15,080 --> 00:16:20,418 intuitiivselt, et tegemist on teile, et alati töötab nn konstantse ajaga? 334 00:16:20,418 --> 00:16:20,918 Jah? 335 00:16:20,918 --> 00:16:22,001 >> Sihtrühm: Lisa kaks numbrit. 336 00:16:22,001 --> 00:16:25,320 SPEAKER: Lisa kaks numbrit, 2 pluss 2 võrdub 4, tehtud. 337 00:16:25,320 --> 00:16:27,227 Nii et võiks töötada, mida veel? 338 00:16:27,227 --> 00:16:28,560 Kuidas rohkem reaalses maailmas, jah? 339 00:16:28,560 --> 00:16:30,686 >> Sihtrühm: Leida esimese asjana nimekirja. 340 00:16:30,686 --> 00:16:32,810 SPEAKER: Leida esimene element nimekirja, kindlasti. 341 00:16:32,810 --> 00:16:34,540 Me oleme tegelikult rääkinud umbes massiivid juba, 342 00:16:34,540 --> 00:16:36,540 kuidas sa saad at esimene element massiivi 343 00:16:36,540 --> 00:16:40,465 ükskõik kui kaua massiiv on C-koodi? 344 00:16:40,465 --> 00:16:43,090 Sa lihtsalt kasutada nagu sulg null märke, BAM, sa oled seal. 345 00:16:43,090 --> 00:16:46,120 Ja tõepoolest paneelid kõrvale, toetust midagi üldtuntud 346 00:16:46,120 --> 00:16:49,240 kui muutmälu, muutmälu mälu, sest sa võid sõna otseses mõttes 347 00:16:49,240 --> 00:16:50,284 hüpata suvalisele kohale. 348 00:16:50,284 --> 00:16:52,700 Me saame seda teha isegi rohkem lihtsalt saame tagasi kerida nädal null 349 00:16:52,700 --> 00:16:53,900 kui me tegime Scratch. 350 00:16:53,900 --> 00:16:59,707 Kui palju aega kulus eest öelda ploki Scratch täita? 351 00:16:59,707 --> 00:17:00,790 Just pidev aeg, eks? 352 00:17:00,790 --> 00:17:03,960 Ütle midagi öelda midagi, see ei ole oluline 353 00:17:03,960 --> 00:17:07,359 kui suur Kriimustused maailm, see on alati aega võtab sama palju aega 354 00:17:07,359 --> 00:17:08,490 lihtsalt midagi öelda. 355 00:17:08,490 --> 00:17:11,089 >> Nii et see on pidev aja Aga mis on klapp poolel? 356 00:17:11,089 --> 00:17:13,030 Kui see oli ülemine piire, mis siis, kui me tahame 357 00:17:13,030 --> 00:17:17,089 kirjeldamiseks alumised piirid meie algoritme ajal? 358 00:17:17,089 --> 00:17:19,852 Peaaegu parimal juhul potentsiaalselt, kui soovite, 359 00:17:19,852 --> 00:17:23,060 kuigi need mõisted, mida kohaldatakse kõige paremini juhul, halvemal juhul keskmine juhtudel rohkem 360 00:17:23,060 --> 00:17:26,359 üldiselt, kuid olgem keskenduda ainult madalama piire üldisemalt. 361 00:17:26,359 --> 00:17:31,920 Mis on algoritm, mis on alampiir n samme, 362 00:17:31,920 --> 00:17:33,350 või 2n samme või 3n sammud? 363 00:17:33,350 --> 00:17:36,241 Mõned teguriga n samme, see on selle alumine piir. 364 00:17:36,241 --> 00:17:36,740 Jah? 365 00:17:36,740 --> 00:17:37,910 >> Sihtrühm: Bubble sort? 366 00:17:37,910 --> 00:17:41,610 >> SPEAKER: Bubble sort võtab sa minimaalselt n samme, miks? 367 00:17:41,610 --> 00:17:42,279 Miks see nii on? 368 00:17:42,279 --> 00:17:45,320 Miks peaks, et start tulevad sind intuitiivselt, isegi kui see ei ole lihtsalt 369 00:17:45,320 --> 00:17:46,530 veel? 370 00:17:46,530 --> 00:17:47,030 Jah? 371 00:17:47,030 --> 00:17:47,990 >> Sihtrühm: [kuuldamatu]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 SPEAKER: Täpselt. 374 00:17:52,360 --> 00:17:55,810 Parimal võimalikul stsenaariumil mull sorteerida, ja palju algoritme, 375 00:17:55,810 --> 00:17:58,769 kui ma käe kaheksa inimest kes on juba valmis, 376 00:17:58,769 --> 00:18:00,560 oleks rumal teile, algoritm, 377 00:18:00,560 --> 00:18:02,202 minna edasi ja tagasi rohkem kui üks kord, eks? 378 00:18:02,202 --> 00:18:04,285 Sest niipea kui kõndida läbi nimekirja kord, 379 00:18:04,285 --> 00:18:08,090 sa peaksid mõistma, et oh, ma ei teinud vahetustehingud, see nimekiri on sorteeritud, exit. 380 00:18:08,090 --> 00:18:09,700 Aga see aega võtab teid n samme. 381 00:18:09,700 --> 00:18:12,033 >> Ja vastupidi, mis on teise mõtlemine on? 382 00:18:12,033 --> 00:18:15,240 Bubble sort on omega, nii rääkida, n, 383 00:18:15,240 --> 00:18:19,050 sest kui te vaatate vähem kui n elementi, mida 384 00:18:19,050 --> 00:18:23,009 on oluline küsimus on? 385 00:18:23,009 --> 00:18:24,550 Sa ei tea, kas see on järjestatud, eks. 386 00:18:24,550 --> 00:18:26,800 Meie, inimesed, võiks pilgu kaheksa inimesi ja olla nagu, oh, see on sorteeritud, 387 00:18:26,800 --> 00:18:28,430 et ei võtnud mind n samme, kuid ta tegi. 388 00:18:28,430 --> 00:18:30,810 Su silmad, kuigi sa lahke kohta on suur vaateväli, 389 00:18:30,810 --> 00:18:33,184 sa vaatasid kaheksa elemente, sa vaatasid kaheksa inimest, 390 00:18:33,184 --> 00:18:34,610 see on kaheksa samme tõhusalt. 391 00:18:34,610 --> 00:18:38,612 Ja ainult siis, kui ma kõnnin läbi kogu list Kas ma mõistan, jah, järjestatud. 392 00:18:38,612 --> 00:18:41,320 Kui ma poole peal mõtlesin, kõik Olgu, see on päris järjestatud nii kaugele, 393 00:18:41,320 --> 00:18:42,520 Mis on tõenäosus, et see ei ole järjestatud? 394 00:18:42,520 --> 00:18:44,186 See algoritme ei kavatse olla õige. 395 00:18:44,186 --> 00:18:46,250 Võiks olla kiirem, kuid vale. 396 00:18:46,250 --> 00:18:48,500 >> Nii et nüüd on meil võimalus kirjeldades alammäär 397 00:18:48,500 --> 00:18:49,710 ja kuidas on pidev aja? 398 00:18:49,710 --> 00:18:54,565 Mis on algoritm, mis on madalam kohustatud oma sõiduaega üks? 399 00:18:54,565 --> 00:18:58,350 1. samm, 2 sammu, 10 sammu, kuid konstantne, sõltumatu n 400 00:18:58,350 --> 00:18:59,310 suurus sisend? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Jah, on tagasi. 403 00:19:04,600 --> 00:19:05,309 >> Sihtrühm: printf? 404 00:19:05,309 --> 00:19:06,183 SPEAKER: Mis see on? 405 00:19:06,183 --> 00:19:07,184 Sihtrühm: printf? 406 00:19:07,184 --> 00:19:07,850 SPEAKER: printf. 407 00:19:07,850 --> 00:19:08,400 OK, muidugi. 408 00:19:08,400 --> 00:19:10,720 Nii et see võtab kindla arvu. 409 00:19:10,720 --> 00:19:13,170 Ja ma peaks nüüd-- nüüd, et me räägime C kood 410 00:19:13,170 --> 00:19:16,040 ja ei kriimusta midagi nagu näiteks koos printf, 411 00:19:16,040 --> 00:19:17,710 peaksime hakkama saada ettevaatlik. 412 00:19:17,710 --> 00:19:21,090 Kuna printf ei võta sisend, see on string, 413 00:19:21,090 --> 00:19:23,220 ja stringid ei tehniliselt on pikkus. 414 00:19:23,220 --> 00:19:25,530 Nii et kui me nüüd tahame valida teile, kui te ei pahanda, 415 00:19:25,530 --> 00:19:29,430 tehniliselt võiksime väita, et printf ei võta muutuva pikkusega sisend, 416 00:19:29,430 --> 00:19:32,270 ja kindlasti see võib võtta rohkem aeg printida string nii kaua, 417 00:19:32,270 --> 00:19:33,560 kui seda kaua. 418 00:19:33,560 --> 00:19:36,570 >> Mis siis, kui me arvestame ainult sorteerimine ja otsimine näiteid? 419 00:19:36,570 --> 00:19:40,450 Aga Mike Smith telefoni raamat või binaarne otsing üldisemalt? 420 00:19:40,450 --> 00:19:42,220 Parimal juhul, mis võib juhtuda? 421 00:19:42,220 --> 00:19:45,577 Ma avan telefoniraamatu ja põmm, seal on Mike Smith number. 422 00:19:45,577 --> 00:19:46,660 Ma ei nimetaks teda kohe. 423 00:19:46,660 --> 00:19:49,390 >> Astus sammu, võib-olla kaks sammu, kuid pidev sammude arv 424 00:19:49,390 --> 00:19:50,230 kui mul vedas. 425 00:19:50,230 --> 00:19:52,570 Ja ausalt öeldes, me nägime Esmaspäev pinginaabri 426 00:19:52,570 --> 00:19:54,710 saada üsna õnnelik kaks korda järjest. 427 00:19:54,710 --> 00:19:57,050 Ja see oli tõesti pidev korda alumised piirid 428 00:19:57,050 --> 00:20:01,280 aasta algoritmi küsimuse kategooria number 50 taga need suletud 429 00:20:01,280 --> 00:20:01,830 uksed. 430 00:20:01,830 --> 00:20:06,400 >> Nüüd, kui kõrvale jätta, kui sa avastad, et nii suur O, ülemise, 431 00:20:06,400 --> 00:20:09,310 ja omega, alampiir, on üks sama, mis 432 00:20:09,310 --> 00:20:11,830 on sama valemit sulgudes, saate ka 433 00:20:11,830 --> 00:20:15,170 öelda, lihtsalt olla väljamõeldud, et midagi on teeta 434 00:20:15,170 --> 00:20:18,270 n või teeta mõne muu väärtusega. 435 00:20:18,270 --> 00:20:20,661 See tähendab lihtsalt seda, kui suur O ja omega on sama. 436 00:20:20,661 --> 00:20:21,910 Nüüd kuidas valikut sort? 437 00:20:21,910 --> 00:20:23,400 Kasutame seda uut sõnavara. 438 00:20:23,400 --> 00:20:27,407 In valiku sort, mis oli meil teed uuesti ja uuesti ja uuesti? 439 00:20:27,407 --> 00:20:29,990 Ma läksin edasi ja tagasi nimekirja, otsin kellele? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Kõige vähem. 442 00:20:34,730 --> 00:20:37,560 >> Nii mitu sammu, kuidas palju võrdlusi tegin ma 443 00:20:37,560 --> 00:20:43,250 pead tegema selleks, et aru saada, kes väikseim element nimekiri oli? 444 00:20:43,250 --> 00:20:44,437 n miinus 1, eks? 445 00:20:44,437 --> 00:20:47,770 Sest kui ma alustan ühe olen antud ja ma hakkan võrrelda teda, 446 00:20:47,770 --> 00:20:49,519 siis tema, ta või tema, tema, ma 447 00:20:49,519 --> 00:20:52,010 saab siduda elemendid koos n miinus 1 korda. 448 00:20:52,010 --> 00:20:55,630 Nii et valik omamoodi sarnaselt võtab n miinus 1 sammude esmakordselt. 449 00:20:55,630 --> 00:20:59,540 >> Mitu sammu see viib mind leida teine ​​väiksem element? 450 00:20:59,540 --> 00:21:02,920 n miinus 2, sest ma oleks loll kui ma saan vaadata samad inimesed 451 00:21:02,920 --> 00:21:06,280 uuesti, kui ma olen juba valitud teda või tema ja panna neid oma kohale. 452 00:21:06,280 --> 00:21:09,270 Ja kolmas samm, n miinus 3, siis n miinus 4. 453 00:21:09,270 --> 00:21:11,020 Me oleme näinud seda mustrit Enne ja tõepoolest 454 00:21:11,020 --> 00:21:13,460 valik omamoodi sarnaselt on ülemise 455 00:21:13,460 --> 00:21:16,210 n ruudus, kui me üles, et liitmise. 456 00:21:16,210 --> 00:21:19,790 Mis on selle alampiiri, valiku sort? 457 00:21:19,790 --> 00:21:25,350 Minimaalselt, kui palju aega peab valiku Sorteeri võtta, kui me määratleda seda esmaspäeval? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Pakub välja kaks võimalust. 460 00:21:30,490 --> 00:21:32,360 Võibolla on see n, nagu enne. 461 00:21:32,360 --> 00:21:35,040 Võibolla on see n ruudus, sest see nüüd kui ülemise. 462 00:21:35,040 --> 00:21:35,874 >> Sihtrühm: n ruudus. 463 00:21:35,874 --> 00:21:36,664 SPEAKER: n ruudus. 464 00:21:36,664 --> 00:21:37,368 Miks? 465 00:21:37,368 --> 00:21:40,060 >> Sihtrühm: Kuna teil on määratleda [kuuldamatu]. 466 00:21:40,060 --> 00:21:41,510 >> SPEAKER: Täpselt. 467 00:21:41,510 --> 00:21:45,077 Vähemalt nii ma määratletud valik omamoodi see oli päris naiivne, lase edasi, 468 00:21:45,077 --> 00:21:46,160 Leida väikseim element. 469 00:21:46,160 --> 00:21:47,770 Mine uuesti Leida väikseim element. 470 00:21:47,770 --> 00:21:49,490 Mine uuesti Leida väikseim element. 471 00:21:49,490 --> 00:21:51,700 Pole mingit sorti optimeerimine on, et 472 00:21:51,700 --> 00:21:54,350 laseks mind katkestada pärast lihtsalt n või nii samme. 473 00:21:54,350 --> 00:21:57,080 Nii et tõesti, valik sort, omega n ruudus. 474 00:21:57,080 --> 00:22:00,667 >> Aga sisestamise sorteerida, kus ma võtsin kes mulle anti, ja siis ma plopped teda 475 00:22:00,667 --> 00:22:01,750 või tema õiges kohas? 476 00:22:01,750 --> 00:22:04,958 Siis asus teine ​​isik, plopped teda õiges kohas. 477 00:22:04,958 --> 00:22:07,910 Siis järgmine isik, plopped teda õiges kohas. 478 00:22:07,910 --> 00:22:10,537 Pange tähele, et see on väga lineaarne, nii rääkida. 479 00:22:10,537 --> 00:22:12,620 Ma olen sirge, ma olen ei lähe edasi ja tagasi, 480 00:22:12,620 --> 00:22:16,080 Ma pole kunagi tagasi vaadates tõesti, kuid Mis juhtub, kui ma sisestan teda 481 00:22:16,080 --> 00:22:20,302 või tema ümber algul loetelus tegime esmaspäeval? 482 00:22:20,302 --> 00:22:21,010 Mis toimub? 483 00:22:21,010 --> 00:22:21,510 Jah? 484 00:22:21,510 --> 00:22:23,122 Sihtrühm: [kuuldamatu]. 485 00:22:23,122 --> 00:22:24,830 Ettekandja: Jah, et oli saak, eks? 486 00:22:24,830 --> 00:22:26,746 Sa võid mäletate oma klassikaaslastega, kui nad 487 00:22:26,746 --> 00:22:29,670 tegid iga liikumise oma jalgu, et oli operatsioon. 488 00:22:29,670 --> 00:22:33,610 Nii et kui seal oli kolm inimest siin ja uus isik kuulus viis sinna, 489 00:22:33,610 --> 00:22:37,360 pikk etapp niimoodi, muidugi, ta või ta võib lihtsalt minema lõpuni. 490 00:22:37,360 --> 00:22:40,074 Aga kui me mõtleme arvuti ja hulga mälu, 491 00:22:40,074 --> 00:22:41,990 need inimesed hakkavad on shuffle üle 492 00:22:41,990 --> 00:22:43,260 et teha ruumi, et isik. 493 00:22:43,260 --> 00:22:46,930 Ja nii, et n miinus 1 shufflings, n miinus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 miinus 3 shufflings on lihtsalt selline minu taga toimub, ei ole minu ees 495 00:22:50,660 --> 00:22:52,710 nagu enne, mõnes mõttes. 499 00:22:52,557 --> 00:22:54,640 Nüüd kui kõrvale, ja kui te olete näinud Internetis 500 00:22:54,640 --> 00:22:57,699 kui te hakkate poking ümber umbes kehvasti, seal on nii palju erinevaid ones 501 00:22:57,699 --> 00:22:59,490 seal, mõned neist paremini kui teised. 502 00:22:59,490 --> 00:23:02,200 Tõepoolest, bogosort on üks see on omamoodi lõbus otsida. 503 00:23:02,200 --> 00:23:06,650 Bogosort võtab komplekt numbrid või öelda kaardipakk, 504 00:23:06,650 --> 00:23:09,870 juhuslikult segab neid ja kontrollib, kas nad järjestatud. 505 00:23:09,870 --> 00:23:12,130 Ja kui ei, siis kas see uuesti. 506 00:23:12,130 --> 00:23:14,140 Ja kui ei, siis kas see uuesti. 507 00:23:14,140 --> 00:23:15,440 Kui ei, siis kas see uuesti. 508 00:23:15,440 --> 00:23:17,060 Uskumatult loll. 509 00:23:17,060 --> 00:23:19,520 >> Ja tõepoolest, kui sa loed nagu Wikipedia artikkel, 510 00:23:19,520 --> 00:23:21,200 tema hüüdnimi on rumalus. 511 00:23:21,200 --> 00:23:25,180 See lõpuks tööle, loodetavasti piisavalt aega, 512 00:23:25,180 --> 00:23:28,240 kuid sel aega võib võtta omajagu aega. 513 00:23:28,240 --> 00:23:31,650 Nii et kui ma saaks, olgem kiirus asjad üles Mary Beth näiteks varem 514 00:23:31,650 --> 00:23:35,150 lastes veel mõned elemendid, kuid veel kaks protsessorid. 515 00:23:35,150 --> 00:23:37,100 Kaks inimest, kui sa ei pahanda ühendab mind. 516 00:23:37,100 --> 00:23:40,972 Kuidas 1 üle siin, ja olgem go-- keegi seal? 517 00:23:40,972 --> 00:23:41,722 Keegi seal? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 Sa musta särk, jah, tule alla. 520 00:23:44,190 --> 00:23:45,000 Olgu, mis su nimi on? 521 00:23:45,000 --> 00:23:45,720 >> Sihtrühm: Peter. 522 00:23:45,720 --> 00:23:46,100 >> SPEAKER: Mis see on? 523 00:23:46,100 --> 00:23:46,766 >> Sihtrühm: Peter. 524 00:23:46,766 --> 00:23:49,450 SPEAKER: Peter, David, meeldiv kohtuda. 525 00:23:49,450 --> 00:23:53,670 Olgu, meil on Peter siin, kui te tahan tulla lauale siin. 526 00:23:53,670 --> 00:23:54,550 Ja mis sinu nimi on? 527 00:23:54,550 --> 00:23:55,216 >> Sihtrühm: Elena. 528 00:23:55,216 --> 00:23:55,970 SPEAKER: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, meeldiv kohtuda. 530 00:23:57,030 --> 00:23:58,060 Elena kohtuda Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 Ja me vajame Andrew siin ka, palun. 533 00:24:02,290 --> 00:24:06,107 Ja teie probleem läheb et sorteerida kaardipakk. 534 00:24:06,107 --> 00:24:08,190 Ja kui võõras, tekk kaarte peaks lõpuks 535 00:24:08,190 --> 00:24:11,064 sorteerida vähe midagi see, kus me teeme klubid, siis 536 00:24:11,064 --> 00:24:13,660 labidad, siis südameid ja teemandid, ässast kui üks, 537 00:24:13,660 --> 00:24:15,570 kõik viis kuni kuningas. 538 00:24:15,570 --> 00:24:20,890 >> Kaarte ma annan teile saab olema 52 koguses. 539 00:24:20,890 --> 00:24:23,160 Me läheme samamoodi kord, vaid hetk. 540 00:24:23,160 --> 00:24:26,410 Me läheme visata Andrew kuni ekraanil siin 541 00:24:26,410 --> 00:24:28,170 et vaadata, kui sa seda teed. 542 00:24:28,170 --> 00:24:31,070 Ja nii, et see kõik on eriti nähtav, 543 00:24:31,070 --> 00:24:33,490 need kaardid sain Amazon. 544 00:24:33,490 --> 00:24:42,861 Nii et nad on juba juhuslikult sorteeritud, ja me läheme kord, kui sa. 545 00:24:42,861 --> 00:24:44,610 Ja me ei kavatse hoiab see reaalne seekord 546 00:24:44,610 --> 00:24:47,820 nii me ei kavatse üritada sulle survet avaldada sest muidu saad tüütu 547 00:24:47,820 --> 00:24:48,460 kiiresti. 548 00:24:48,460 --> 00:24:53,860 Kui sa saaksid minna sorteerida 52 elemendid koos läbi mõned vahendid, nüüd. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> Ja veel, kui me vaatame neid mehed tegema seda, mida lõpuks 551 00:25:07,180 --> 00:25:10,200 läheb toota ilmne tulemus, mõtle tegelikult 552 00:25:10,200 --> 00:25:12,962 kuidas nad iga tee seda, kuidas sa võiksid kirjeldada. 553 00:25:12,962 --> 00:25:15,045 Kuna jällegi on need kõik protsessid, algoritmid 554 00:25:15,045 --> 00:25:17,090 et me enesestmõistetavaks nagu inimene. 555 00:25:17,090 --> 00:25:22,349 Aga sa oled ilmselt pikka aega olnud intuitsiooni, ammu enne seda, kui isegi 556 00:25:22,349 --> 00:25:24,390 mõelnud, võttes arvutiteadus klass sa 557 00:25:24,390 --> 00:25:27,223 võisid intuitsiooni koos mida lahendada selliseid probleeme. 558 00:25:27,223 --> 00:25:29,560 Aga kui te tunnete mustrid ja alustada 559 00:25:29,560 --> 00:25:32,407 vormistama samme, mis sa lahendada neid probleeme, 560 00:25:32,407 --> 00:25:35,490 leiad, et sul on võimalik lahendada palju huvitav ja palju keerulisem 561 00:25:35,490 --> 00:25:39,190 probleemid kiiresti. 562 00:25:39,190 --> 00:25:42,351 Nii et keegi publiku, mis on vähemalt üks element algoritmi 563 00:25:42,351 --> 00:25:43,350 et nad kasutavad siin? 564 00:25:43,350 --> 00:25:44,275 >> Sihtrühm: [kuuldamatu] 565 00:25:44,275 --> 00:25:45,150 SPEAKER: Mis see on? 566 00:25:45,150 --> 00:25:47,062 Sihtrühm: ülikond. 567 00:25:47,062 --> 00:25:47,770 SPEAKER: ülikond. 568 00:25:47,770 --> 00:25:50,630 Nii et kõigepealt nad koonduvad kõik teemandid koos 569 00:25:50,630 --> 00:25:52,560 tundub kõik südamed koos tundub, 570 00:25:52,560 --> 00:25:56,520 ja nii edasi, ilma suhtes numbrite jaoks kaarte. 571 00:25:56,520 --> 00:26:00,900 Ja nüüd nad ilmuvad, näiteks tuleb nende sorteerimine arvust. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Väga hea. 574 00:26:08,910 --> 00:26:12,370 >> Olgu, mis hakkab oleks viimane etapp, siis siin on? 575 00:26:12,370 --> 00:26:16,950 Kui meil on neli sorteeritud ülikonnad, mis me peame tegema, et neli vaiad 576 00:26:16,950 --> 00:26:20,059 saavutamiseks ühe järjestatud teki, lihtsalt? 577 00:26:20,059 --> 00:26:21,350 Seega on meil vaja liita need uuesti. 578 00:26:21,350 --> 00:26:25,160 >> Nii et seal on huvitav idee, jälle daresay, on väga intuitiivne isegi 579 00:26:25,160 --> 00:26:28,140 kui sa ei oleks kunagi laksu selline silt peal. 580 00:26:28,140 --> 00:26:31,900 See põhiline mõiste jagades probleemiks mitte pooleks seekord 581 00:26:31,900 --> 00:26:33,410 kuid vähemalt neljaks osaks. 582 00:26:33,410 --> 00:26:36,810 Probleemide päris palju põhimõtteliselt identsed probleemid 583 00:26:36,810 --> 00:26:40,480 isoleerituna üksteisest ja seejärel ühineb tulemusi. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 Ja väga hea, tehtud. 586 00:26:50,140 --> 00:26:52,140 Olgu, suur ümmargune aplaus, kui saime. 587 00:26:52,140 --> 00:26:56,480 >> [APPLAUSE] 588 00:26:56,480 --> 00:26:59,740 >> SPEAKER: ma ei tea, mida sa pistmist, küll aga lahke. 589 00:26:59,740 --> 00:27:01,690 Tänan sind nii palju. 590 00:27:01,690 --> 00:27:04,660 Vaatame, kaks minutit kaheksa sekundi 591 00:27:04,660 --> 00:27:07,490 Kui soovite, et väljakutse oma sõpradele. 592 00:27:07,490 --> 00:27:12,160 Mis siis saab olema ära võtta selle 593 00:27:12,160 --> 00:27:13,830 et saame kasutada enam üldiselt? 594 00:27:13,830 --> 00:27:16,080 Noh, arvan, et tagasi Selle massiivi numbrid, 595 00:27:16,080 --> 00:27:19,060 ja arvan, et nüüd tagasi mõned pseudokoodi oleme kirjutanud ka varem, 596 00:27:19,060 --> 00:27:22,080 ja see oli pseudokoodi võtta lahendamise telefoniraamatust probleem. 597 00:27:22,080 --> 00:27:25,150 Mille sisse pseudokoodi I loetletud rohkem metoodiliselt 598 00:27:25,150 --> 00:27:28,400 kirjeldada, kuidas ma tegin väga intuitiivne inimese algoritm jagades telefoni 599 00:27:28,400 --> 00:27:31,650 Broneeri pooleks, kordan, kordan, kordan, kuni ma leian kellegi, nagu Mike Smith, 600 00:27:31,650 --> 00:27:33,790 kui ta on tõepoolest telefoniraamatust. 601 00:27:33,790 --> 00:27:37,610 >> Aga ma sellist, mida kasutatakse, mida ma helistan väga kordusmeetod siin 602 00:27:37,610 --> 00:27:42,160 eriti teate rida 8 ja liin 11. 603 00:27:42,160 --> 00:27:46,750 Need on tõendeid korduv lähenemine, silmukoiminen lähenemine, 604 00:27:46,750 --> 00:27:49,040 sest see on täpselt käitumist nad esile kutsuda. 605 00:27:49,040 --> 00:27:52,910 Need read nii öelda minna line kolm, ja te saate objekti 606 00:27:52,910 --> 00:27:55,140 arvad, et sinu vaimusilmas nagu oleks loop. 607 00:27:55,140 --> 00:27:59,080 Ta räägib sulle, et minna tagasi üles astuma kolm ja kordan uuesti ja uuesti, 608 00:27:59,080 --> 00:28:00,010 ja jälle. 609 00:28:00,010 --> 00:28:04,410 >> Aga mis siis, kui me võimendada Põhiidee siin, et me ei ole viimane kord, 610 00:28:04,410 --> 00:28:10,280 ja lihtsustada rida 8 ja line 11 ja nende naabrid 611 00:28:10,280 --> 00:28:12,840 kui ainult see, et kollane. 612 00:28:12,840 --> 00:28:16,480 See ei ole põhimõtteliselt lühendamine pseudokoodi väga palju, 613 00:28:16,480 --> 00:28:20,530 aga see on põhimõtteliselt muutumas milline mu algoritm. 614 00:28:20,530 --> 00:28:24,220 Mis ma nüüd öelda, etapis 7, etapis 10, 615 00:28:24,220 --> 00:28:29,140 on otsida Mike aastal Täpselt samamoodi 616 00:28:29,140 --> 00:28:31,580 kuid igaks vasakul pool või paremal pool. 617 00:28:31,580 --> 00:28:33,420 >> Nii teisisõnu, kui Lähtun samm üks, 618 00:28:33,420 --> 00:28:36,150 korja telefoniraamat, avatud keskel telefoniraamatu, vaadata nimesid, 619 00:28:36,150 --> 00:28:39,010 kui Smith on üks nime, helistada Mike, teine 620 00:28:39,010 --> 00:28:44,340 kui Smith on varem raamat, astu seitse otsi Mike vasaku poole raamatust. 621 00:28:44,340 --> 00:28:47,130 Aga selline tunne ta lahkub mind rippus, eks? 622 00:28:47,130 --> 00:28:49,240 Kollane, on juhendamise, kuid kuidas ma 623 00:28:49,240 --> 00:28:51,870 otsi Mike vasakul pool telefoniraamatust? 624 00:28:51,870 --> 00:28:54,210 Kuhu ma pean algoritmi, mis ma 625 00:28:54,210 --> 00:28:57,100 otsida keegi nagu Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Noh, see on jõllis meid ees. 627 00:28:58,980 --> 00:29:03,090 Võin sõna otseses mõttes kasutada täpselt sama programmi tõhusalt tõuseb tippu 628 00:29:03,090 --> 00:29:06,490 uuesti ja uuesti jooksvate sama rida koodi. 629 00:29:06,490 --> 00:29:10,610 >> Nii et kuigi see ei tohiks tunda nagu natuke tsükliline määratlus 630 00:29:10,610 --> 00:29:13,480 kuhu vastates keegi on Küsimus, mida justkui küsides 631 00:29:13,480 --> 00:29:15,990 sama küsimust uuesti, nagu miks, miks, miks? 632 00:29:15,990 --> 00:29:21,580 Reaalsus on, sest me oleme kõva kodeeritud paar erilist read, etapp 4, 633 00:29:21,580 --> 00:29:25,320 mis on siis ja samm 12, mis on tegelikult teise filiaali, 634 00:29:25,320 --> 00:29:30,120 sest meil on need asetäitja meetmed, Selle algoritmi lõpeb, kui me 635 00:29:30,120 --> 00:29:32,050 leida Mike, või kui me seda ei tee. 636 00:29:32,050 --> 00:29:36,810 Aga etapis 7 ja 10 Siiani oleme mida me nimetame rekursiivne algoritm. 637 00:29:36,810 --> 00:29:40,420 Ja rekursioon on tõepoolest võimas idee et see on natuke meeles painutamine alguses, 638 00:29:40,420 --> 00:29:42,500 et saame nüüd taotleda järgmiselt. 639 00:29:42,500 --> 00:29:46,600 >> Merge sort on viimane sort, mis vaatame, vähemalt klassi ametlikult. 640 00:29:46,600 --> 00:29:50,040 Ja see on täiesti erinev neist viimase kolme ja kindlasti 641 00:29:50,040 --> 00:29:52,140 Viimase nelja, kui me kaasame bogosort. 642 00:29:52,140 --> 00:29:54,810 Siin pseudokoodi ühendamisväljundil sort. 643 00:29:54,810 --> 00:30:00,170 Kui sisendi n elementi, et anda massiivi suuruse n, kui n on väiksem kui 2, 644 00:30:00,170 --> 00:30:01,040 tagasi. 645 00:30:01,040 --> 00:30:03,610 Miks ma pean selle meelerahu kõigepealt kontrollida? 646 00:30:03,610 --> 00:30:09,477 Mis tähendas, kui ma käe massiivi, mille pikkus n on väiksem kui 2? 647 00:30:09,477 --> 00:30:11,060 See on juba sorteeritud, loomulikult, eks? 648 00:30:11,060 --> 00:30:13,640 Kuna nimekiri kas on üks element, mis on triviaalselt 649 00:30:13,640 --> 00:30:15,180 järjestatud, sest see on Ainuke asi seal. 650 00:30:15,180 --> 00:30:18,138 Või on see suurus null, mis tähendab, seal on midagi sorteerida, nii et oma olemuselt 651 00:30:18,138 --> 00:30:18,720 see on järjestatud. 652 00:30:18,720 --> 00:30:20,410 Seal on lihtsalt midagi valesti seal. 653 00:30:20,410 --> 00:30:22,310 Nii et see on meie nn aluspõhimõtted. 654 00:30:22,310 --> 00:30:24,440 >> See on sarnase sisuga et mida me tegime koos Mike. 655 00:30:24,440 --> 00:30:26,023 Kui Mike telefoniraamatus, helista talle. 656 00:30:26,023 --> 00:30:27,740 Kui ta ei ole seal, loobuma. 657 00:30:27,740 --> 00:30:31,240 See on niinimetatud baas juhul veenduda, Selle algoritmi lõpus päeval 658 00:30:31,240 --> 00:30:33,540 peatub teatud tingimustel. 659 00:30:33,540 --> 00:30:37,890 >> Aga siin on liigaasta usu praegu, teine, sorteerida vasakul poolel elemendid 660 00:30:37,890 --> 00:30:39,740 siis saad õige pool elemente, 661 00:30:39,740 --> 00:30:41,189 ja siis liita järjestatud pooleks. 662 00:30:41,189 --> 00:30:43,230 Ja siin on koht, kus ta tunneb, nagu me copping välja. 663 00:30:43,230 --> 00:30:46,900 Ma palusin teil sorteerida n elementi, ja ma olen 664 00:30:46,900 --> 00:30:50,712 öelda, OK, ei see sorteerimine vasakule ja sorteerimine õigus. 665 00:30:50,712 --> 00:30:52,420 Aga ma ütlen üht Teine asi, ja see 666 00:30:52,420 --> 00:30:55,530 on peamine teema tundub aastal intuitsiooni seni 667 00:30:55,530 --> 00:30:57,380 seal on see kolmas järk ühinevad. 668 00:30:57,380 --> 00:31:00,430 Milline kuigi see tundub nii tobe vaimus 669 00:31:00,430 --> 00:31:02,320 nagu lihtsalt ühendada asjad koos, tundub 670 00:31:02,320 --> 00:31:05,380 olla oluline samm uuesti kokku kaks probleemi, mis 671 00:31:05,380 --> 00:31:07,330 jagati lõppkokkuvõttes pooleks. 672 00:31:07,330 --> 00:31:12,090 >> Nii ühendada sorteerida, teeme seda, kui sa huumor mulle veel üks meeleavaldus, 673 00:31:12,090 --> 00:31:14,730 just nii, et meil on mõned numbrid töötada. 674 00:31:14,730 --> 00:31:19,470 Kas ma saan vahetada kaheksa stress pallid kaheksa inimest? 675 00:31:19,470 --> 00:31:29,320 Olgu, kuidas on teil kolm, siis neli Käesolevas paragrahvis, viis, kuus, ja olgem 676 00:31:29,320 --> 00:31:30,720 ei 7, 8, tule üles. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, jah OK. 679 00:31:36,520 --> 00:31:38,640 Miinus 8, seal läheme, pluss 1. 680 00:31:38,640 --> 00:31:39,150 Suurepärane. 681 00:31:39,150 --> 00:31:42,000 Olgu tule üles, olgem kiiresti teile numbreid. 682 00:31:42,000 --> 00:31:50,800 Number kaks, number kolm, number neli, number viis, kuus, seitse, kaheksa. 683 00:31:50,800 --> 00:31:52,140 Ma tegin kaheksa õigesti seekord. 684 00:31:52,140 --> 00:31:56,390 >> OK, nii et edasi minna, kui sa saaksid, ja Lahendame esialgses järjekorras 685 00:31:56,390 --> 00:31:59,810 et meil oli eile, mis nägi nagu see, kui sa ei pahanda. 686 00:31:59,810 --> 00:32:03,620 Ja teeme seda ees laual. 687 00:32:03,620 --> 00:32:06,510 Olgu, liita omamoodi. 688 00:32:06,510 --> 00:32:08,820 See on koht, kus see läheb saada omamoodi huvitav, 689 00:32:08,820 --> 00:32:12,800 sest ma tundub, et olen andnud oma nii palju vähem teavet täna. 690 00:32:12,800 --> 00:32:15,149 >> Nii liita omamoodi kõigepealt sisendi n elementi, 691 00:32:15,149 --> 00:32:18,440 ja loomulikult ei ole väiksem kui kaks, siis on kaheksa, nii et mul on veel tööd teha. 692 00:32:18,440 --> 00:32:21,140 Nüüd vaimselt oleme nagu klassi on nüüd teine ​​haru 693 00:32:21,140 --> 00:32:22,540 mis tähendab kolme etappi. 694 00:32:22,540 --> 00:32:25,017 Esiteks, ma pean sorteerima Vasakul pool elemente. 695 00:32:25,017 --> 00:32:26,350 Niisiis, kuidas ma minna seda teed? 696 00:32:26,350 --> 00:32:28,950 Noh, ma lähen liiki vaimselt jagada nimekirja siin, 697 00:32:28,950 --> 00:32:30,700 Te ei pea füüsiliselt liigutada, ja ma olen 698 00:32:30,700 --> 00:32:33,180 kavatse keskenduda ainult Vasakul pool elemendid siin. 699 00:32:33,180 --> 00:32:36,770 Niisiis, kuidas ma minna sorteerimine Avalda oma suuruse neli? 700 00:32:36,770 --> 00:32:38,730 Mis on minu algoritm? 701 00:32:38,730 --> 00:32:42,580 Esiteks ma kontrollin on n vähem kui kaks, ei, nii et ma edasi veel plokk uuesti. 702 00:32:42,580 --> 00:32:43,900 Sorteeri vasakule poole elemente. 703 00:32:43,900 --> 00:32:45,608 >> Nüüd jälle, vaimselt ja see on koht, kus 704 00:32:45,608 --> 00:32:49,550 teil on koguda palju vaimne ajalugu, kui soovite. 705 00:32:49,550 --> 00:32:51,940 Nüüd ma sorteerimine vasakul poolel vasakul poolel. 706 00:32:51,940 --> 00:32:57,000 Olgu, nüüd ma kutsun minu sama ühendamine sorteerimine algoritm on N vähem kui kaks? 707 00:32:57,000 --> 00:33:00,590 Ei, see on kaks, nii et ma pean sorteeri vasakul pool ja paremal pool. 708 00:33:00,590 --> 00:33:02,042 Nii et siin me läheme, sorteerida vasakule poole. 709 00:33:02,042 --> 00:33:03,750 Miks sa lihtsalt ei võta üks samm edasi. 710 00:33:03,750 --> 00:33:04,415 Mis su nimi on? 711 00:33:04,415 --> 00:33:04,860 >> Sihtrühm: Darren. 712 00:33:04,860 --> 00:33:05,260 >> SPEAKER: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan on astunud sammu edasi. 714 00:33:06,040 --> 00:33:06,748 >> Sihtrühm: Darren. 715 00:33:06,748 --> 00:33:09,000 SPEAKER: Darren, tehtud. 716 00:33:09,000 --> 00:33:10,090 Kas sa ütlesid Darren või Dan? 717 00:33:10,090 --> 00:33:10,550 >> Sihtrühm: Darren. 718 00:33:10,550 --> 00:33:11,216 >> SPEAKER: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren astunud edasi ja ta on nüüd järjestatud. 720 00:33:14,422 --> 00:33:16,130 Ja see on peaaegu Loll, õigus? 721 00:33:16,130 --> 00:33:18,862 Ma tõesti ei tundu olevat saavutada midagi, kuid olgem jätkata. 722 00:33:18,862 --> 00:33:20,820 Nüüd lubage mul sorteerida õige poolel elemente. 723 00:33:20,820 --> 00:33:21,200 Mis su nimi on? 724 00:33:21,200 --> 00:33:21,690 >> Sihtrühm: Luke. 725 00:33:21,690 --> 00:33:22,273 >> SPEAKER: Luke. 726 00:33:22,273 --> 00:33:23,400 Astuge edasi. 727 00:33:23,400 --> 00:33:25,640 Valmis olen järjestatud Luke. 728 00:33:25,640 --> 00:33:28,570 Vasakul pool on nüüd järjestatud ja paremal pool on nüüd sorteeritud, 729 00:33:28,570 --> 00:33:30,770 kuid jällegi, seal on oluline samm siin. 730 00:33:30,770 --> 00:33:32,940 Mida ma järgmiseks pean tegema? 731 00:33:32,940 --> 00:33:33,941 Merge järjestatud pooleks. 732 00:33:33,941 --> 00:33:36,648 Nüüd me lihtsalt igaüks edasi ja tagasi sel viisil 733 00:33:36,648 --> 00:33:38,620 sest ma nagu vaja mõned tühjalt ruumi. 734 00:33:38,620 --> 00:33:40,411 See on peaaegu nagu need kutid on lauale, 735 00:33:40,411 --> 00:33:42,460 ja mul on vaja ruumi neid liigutada edasi. 736 00:33:42,460 --> 00:33:44,170 Nii et ma lähen ühendada kutid vaadates 737 00:33:44,170 --> 00:33:45,960 vasakul pool ja paremal pool. 738 00:33:45,960 --> 00:33:48,740 Ja kes ilmselt on esimesel kohal, vasak pool või paremal pool? 739 00:33:48,740 --> 00:33:52,710 Nii et parem pool, nii et liigume Luke üle siin Darren oma algasendisse. 740 00:33:52,710 --> 00:33:57,640 Ja nüüd ühendada oma vasakule poole, Darren läheb liikuda seal. 741 00:33:57,640 --> 00:33:59,750 >> Nii et tundub, nagu peaaegu mull omamoodi mõju, 742 00:33:59,750 --> 00:34:02,482 kuid minu peamine algoritm, väga erinevaid seekord. 743 00:34:02,482 --> 00:34:04,815 Aga nüüd on koht, kus asjad natuke tüütu, sest sa 744 00:34:04,815 --> 00:34:06,810 pea kerida vaimselt Kust ma jätan maha. 745 00:34:06,810 --> 00:34:09,893 Ma olen lihtsalt liideti sorteeritud pooleks, mis tähendab, et ma olen, kus minu algoritm? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Mul on sorteerida õige poole, eks? 748 00:34:13,770 --> 00:34:15,910 >> Kui teil kerida, sõna otseses mõttes aasta video, saate 749 00:34:15,910 --> 00:34:18,339 näha, et me peame seda koht Luke ja Darren 750 00:34:18,339 --> 00:34:21,370 sorteerimine vasakul poolel vasakul poolel. 751 00:34:21,370 --> 00:34:23,430 Siis ühendati need sorteeritud pooleks, mis 752 00:34:23,430 --> 00:34:27,941 tähendab, järgmine samm on omamoodi paremal pool vasakul poolel. 753 00:34:27,941 --> 00:34:29,649 Olgu, oletame, seda kiiremini. 754 00:34:29,649 --> 00:34:33,282 Olgu, kuus, ma väita, te nüüd järjestatud, tule edasi. 755 00:34:33,282 --> 00:34:33,990 Mis su nimi on? 756 00:34:33,990 --> 00:34:34,589 >> Sihtrühm: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> SPEAKER: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano on nüüd järjestatud. 759 00:34:36,010 --> 00:34:36,450 Ja mis sinu nimi on? 760 00:34:36,450 --> 00:34:37,080 >> Sihtrühm: Alex. 761 00:34:37,080 --> 00:34:38,379 >> SPEAKER: Alex on nüüd järjestatud. 762 00:34:38,379 --> 00:34:40,750 Vasak pool, paremal pool, mis on viimane samm? 763 00:34:40,750 --> 00:34:41,250 Merge. 764 00:34:41,250 --> 00:34:44,310 Päris triviaalne, nii et ma olen kavatse ühineda kuus, 765 00:34:44,310 --> 00:34:46,930 astuda samm tagasi, kaheksa, astuda samm tagasi. 766 00:34:46,930 --> 00:34:49,530 Ja nüüd teate see on kasulik Buffee, mida 767 00:34:49,530 --> 00:34:53,930 Nüüd on tõsi, umbes vasakul poolel nimekiri, sõltumata sellest, kuidas me alustasime? 768 00:34:53,930 --> 00:34:55,090 See on sorteeritud. 769 00:34:55,090 --> 00:34:57,750 >> Nüüd see ei ole sorteeritud suur kava asju, 770 00:34:57,750 --> 00:35:00,250 kuid on järjestatud sõltumatult ning teise poole. 771 00:35:00,250 --> 00:35:04,100 Nüüd sellest, mis samm peal ma olen, kui ma hoida kerivad, kuidas lugu algas? 772 00:35:04,100 --> 00:35:05,680 Nüüd on mul sorteerida paremal pool. 773 00:35:05,680 --> 00:35:07,630 Nüüd oleme viis tagasi loo alguses, 774 00:35:07,630 --> 00:35:08,921 ja teeme seda kiiremini. 775 00:35:08,921 --> 00:35:11,320 Ma lähen, et järjestada paremal pool kogu nimekirjast. 776 00:35:11,320 --> 00:35:13,060 Mis on järgmine samm? 777 00:35:13,060 --> 00:35:15,840 Sorteeri vasakule poole parem pool. 778 00:35:15,840 --> 00:35:18,715 Sorteeri vasakule poole vasakul pool paremal poolel. 779 00:35:18,715 --> 00:35:19,590 Ja mis sinu nimi on? 780 00:35:19,590 --> 00:35:20,230 >> Sihtrühm: Omar. 781 00:35:20,230 --> 00:35:21,970 >> SPEAKER: Omar, samm edasi, teha. 782 00:35:21,970 --> 00:35:22,860 Vasak pool on järjestatud. 783 00:35:22,860 --> 00:35:23,330 Ja mis sinu nimi on? 784 00:35:23,330 --> 00:35:23,820 >> Sihtrühm: Chris. 785 00:35:23,820 --> 00:35:25,620 >> SPEAKER: Chris, astuda samm edasi, siis on nüüd järjestatud. 786 00:35:25,620 --> 00:35:27,010 Mis on oluline samm nüüd? 787 00:35:27,010 --> 00:35:27,510 Merge. 788 00:35:27,510 --> 00:35:30,509 Nii et keegi ei kavatse ühineda paika siin, kui sa võiksid astuda samm tagasi, 789 00:35:30,509 --> 00:35:32,930 ja kolm läheb astuda samm tagasi, liita. 790 00:35:32,930 --> 00:35:38,080 Nii vasakul poolel paremale poole, on nüüd järjestatud. 791 00:35:38,080 --> 00:35:41,747 Ausalt, see algoritm tunne me raiskame nii rohkem aega kui varem, 792 00:35:41,747 --> 00:35:44,830 aga kui me seda reaalajas, paneme vaata, mis takeaways saab olema. 793 00:35:44,830 --> 00:35:47,970 Nüüd siin ma olen, eks poolel paremal poolel, 794 00:35:47,970 --> 00:35:50,170 Lubage mul minna ja sorteeri vasakul pool. 795 00:35:50,170 --> 00:35:51,482 Samm edasi, mis su nimi on? 796 00:35:51,482 --> 00:35:52,190 Sihtrühm: Ramsey. 797 00:35:52,190 --> 00:35:53,210 SPEAKER: Ramsey on nüüd järjestatud. 798 00:35:53,210 --> 00:35:53,570 Mis su nimi on? 799 00:35:53,570 --> 00:35:54,200 >> Sihtrühm: Marina. 800 00:35:54,200 --> 00:35:57,033 >> SPEAKER: Marina on nüüd sorditud Noh, kui te võtate ühe sammu edasi. 801 00:35:57,033 --> 00:36:00,690 Oluline samm siin on nüüd liita, olen läheb näppima minu kaks nimekirja, 802 00:36:00,690 --> 00:36:01,720 vasakule ja paremale. 803 00:36:01,720 --> 00:36:05,150 Viis on tulemas esimene, ja seitse on tulemas järgmine. 804 00:36:05,150 --> 00:36:06,410 Ja veel, see on tahtlik. 805 00:36:06,410 --> 00:36:08,535 Asjaolu, et nad viivad sammu edasi ja tagasi 806 00:36:08,535 --> 00:36:12,997 on mõeldud esindama, et me ei saa seda algoritmi koht nii lihtsalt 807 00:36:12,997 --> 00:36:15,830 nagu mull sorteerida, ja valiku sorteerida, ja sisestamise sort, kus me lihtsalt 808 00:36:15,830 --> 00:36:16,960 hoida Vahetatakse inimestega. 809 00:36:16,960 --> 00:36:19,940 Ma sõna otseses mõttes vaja omamoodi Suttupaperi kus 810 00:36:19,940 --> 00:36:21,827 panna need inimesed samas ma ühinevad, 811 00:36:21,827 --> 00:36:23,410 ja siis ma ei pane neid tagasi. 812 00:36:23,410 --> 00:36:27,260 Ja see on võti, sest ma kasutan uus ressurss, ruumi ei ole lihtsalt aega. 813 00:36:27,260 --> 00:36:28,270 >> OK, see on hämmastav. 814 00:36:28,270 --> 00:36:32,050 Vasak pool on järjestatud, parem pool on sorteeritud, nüüd peamine ühinevad samm. 815 00:36:32,050 --> 00:36:33,450 Kuidas ma ühendada seda? 816 00:36:33,450 --> 00:36:35,470 Nii et kui sa järgima oma vasak käsi ja parem käsi, 817 00:36:35,470 --> 00:36:38,930 Ma juhtida minu vasak käsi vasakul pool, minu parem käsi 818 00:36:38,930 --> 00:36:42,680 õigel pool, ja nüüd pean otsustada, samm-sammult, kellega ühinevad. 819 00:36:42,680 --> 00:36:44,650 Kes ilmselt on esimene? 820 00:36:44,650 --> 00:36:45,150 Number üks. 821 00:36:45,150 --> 00:36:47,327 Nii et tulge siia, siin on meie muistiinpanokenttään. 822 00:36:47,327 --> 00:36:49,910 Nüüd number üks, ja teate mida ma teen mu paremale käele, 823 00:36:49,910 --> 00:36:54,152 Ma lähen, et liikuda oma parema käe üks samm üle juhtida number kolm, 824 00:36:54,152 --> 00:36:55,860 ja nüüd ma pean tegema Sama otsusega. 825 00:36:55,860 --> 00:36:58,387 Ja tegelikult paistavad õigus ees Luke siin kui sa saaksid, 826 00:36:58,387 --> 00:36:59,720 sest see on meie muistiinpanokenttään. 827 00:36:59,720 --> 00:37:00,610 Nii et kes on järgmine? 828 00:37:00,610 --> 00:37:05,000 Meil on Luke koos number kaks või Chris number kolm. 829 00:37:05,000 --> 00:37:07,460 Ilmselt Luke, number kaks, siis tule siia. 830 00:37:07,460 --> 00:37:11,270 >> Aga mu vasak käsi nüüd läheb suurendatakse punkti juures Darren, 831 00:37:11,270 --> 00:37:15,160 ja siin on võti ära võtta ühinevad, ma lähen hoida seda teed, 832 00:37:15,160 --> 00:37:17,340 Loomulikult, kui sa lahke ja loogikat. 833 00:37:17,340 --> 00:37:19,670 Aga mu käed on kunagi lähen tagasi, 834 00:37:19,670 --> 00:37:23,861 mis tähendab, et ma olen ainult kunagi kolimist vasakult minu ühendamise protsessi, 835 00:37:23,861 --> 00:37:26,360 ja mis saab olema võtmeks Meie analüüs hetk. 836 00:37:26,360 --> 00:37:27,859 >> Vaatame nüüd lõpetada see kiiresti. 837 00:37:27,859 --> 00:37:31,650 Nii et kolm tuleb järgmisena, siis neli tuleb järgmisena, 838 00:37:31,650 --> 00:37:38,750 ja nüüd viis on järgmine, siis kuus, ja seitse, ja siis lõpuks kaheksa. 839 00:37:38,750 --> 00:37:42,960 Tunne aeglaseim algoritm veel, aga mitte siis, kui me tegelikult 840 00:37:42,960 --> 00:37:45,510 käivitada samal sort kella kiirus, nii et 841 00:37:45,510 --> 00:37:48,106 rääkida, sama tiksub kella nagu enne. 842 00:37:48,106 --> 00:37:48,605 Miks? 843 00:37:48,605 --> 00:37:51,100 Noh, Võtame vaadata lõpptulemus. 844 00:37:51,100 --> 00:37:56,990 >> Lähme tagasi siia, las ma tõmba meeleavaldus visuaalselt 845 00:37:56,990 --> 00:37:59,030 mida me tegime. 846 00:37:59,030 --> 00:38:06,110 Suurendamine siin, sellel leht siin, ütlen Firefox 847 00:38:06,110 --> 00:38:08,200 et me tahame järjekorda kuni selles lahtris, olgem 848 00:38:08,200 --> 00:38:11,260 öelda mull sorteerida, kellega me oleme nüüd hästi kursis, 849 00:38:11,260 --> 00:38:14,130 valiku sorteerida, mis on teine üsna lihtne ühe, 850 00:38:14,130 --> 00:38:18,250 ja nüüd tänapäeva merge sort, mis on meie climactic lõpp. 851 00:38:18,250 --> 00:38:21,530 Põhjuseks see võttis nii palju kauem siin inimestega ja mind verbaalselt on 852 00:38:21,530 --> 00:38:23,480 Ilmselt ma selgitatakse igal sammul. 853 00:38:23,480 --> 00:38:26,920 Aga kui sa lihtsalt täita seda, palju nagu me tegime mull sorteerida ning valik 854 00:38:26,920 --> 00:38:30,890 Sorteeri mitte ainult visuaalselt, vaata kui palju efektiivsemalt 855 00:38:30,890 --> 00:38:33,330 Selle võimendades jagunemine ja vallutavad 856 00:38:33,330 --> 00:38:39,150 saab, kui seda kohaldada andmekogum, mis on isegi suurus kaheksa, kuid isegi palju 857 00:38:39,150 --> 00:38:39,970 palju suurem. 858 00:38:39,970 --> 00:38:44,585 Ma annan sulle liita omamoodi, külg küljel nende teiste algoritme. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 See ei hakka valus kiiresti ja lõpetamine 861 00:38:58,530 --> 00:39:00,890 ei ole eriti climactic, nad lihtsalt lõpuks sorteerida. 862 00:39:00,890 --> 00:39:05,280 Aga võti ära võtta on see, et Vaata, kui palju kiiremini liita omamoodi 863 00:39:05,280 --> 00:39:08,110 oli, kui sa arvad, et ma olen lihtsalt selline jama sulle. 864 00:39:08,110 --> 00:39:13,100 Kui me seda veel viimane aeg, Vaatame uuesti seda, lähme tagasi 865 00:39:13,100 --> 00:39:14,960 ja valida mull sorteerida, ja lihtsalt peksab, 866 00:39:14,960 --> 00:39:17,330 Valime sisestamise sort, lihtsalt hea meede. 867 00:39:17,330 --> 00:39:20,020 Ja seekord jälle, olgem vali ühendamise sorteerida ning olgem 868 00:39:20,020 --> 00:39:21,595 tegelikult juhivad neid kõrvuti. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> Ja see ei ole tegelikult juhus. 871 00:39:26,930 --> 00:39:31,140 Mida ma olen tegelikult teinud on, et ma olen jagada oma sisendi poole, jälle, 872 00:39:31,140 --> 00:39:32,240 ja uuesti ja uuesti. 873 00:39:32,240 --> 00:39:35,590 Ja seal on ainult nii palju kordi kui võimalik jagada oma panuse pooleks, vasak 874 00:39:35,590 --> 00:39:36,240 ja paremale. 875 00:39:36,240 --> 00:39:39,425 Mis on valem, mis me hoiame nähes mis kirjeldab divisjoni poole 876 00:39:39,425 --> 00:39:41,050 uuesti ja uuesti ja uuesti ja uuesti? 877 00:39:41,050 --> 00:39:41,890 >> Sihtrühm: Logi n. 878 00:39:41,890 --> 00:39:42,760 >> SPEAKER: Logi n. 879 00:39:42,760 --> 00:39:46,300 Aga seal on üks teine ​​oluline samm, Selle algoritmi ei log n samme. 880 00:39:46,300 --> 00:39:48,992 Kui oleks ainult log n samme, meil oleks sama probleem 881 00:39:48,992 --> 00:39:51,200 nagu enne, kui me ei saa olla et kõik on järjestatud. 882 00:39:51,200 --> 00:39:54,480 Sa pead minimaalselt vaadata n elementi olla kindel, n elemendid on järjestatud, 883 00:39:54,480 --> 00:39:55,950 muidu see on liigaasta usu. 884 00:39:55,950 --> 00:39:59,810 >> Nii et see on minimaalselt log n samme, kuid Aga see võti ühendamise samm 885 00:39:59,810 --> 00:40:04,370 kus ma ühinesid minu vasakul pool ja paremal poole ja kõndis üle lava? 886 00:40:04,370 --> 00:40:06,980 Mitu sammu on, et ühendada? 887 00:40:06,980 --> 00:40:10,150 See on n, aga ma ei ole lihtsalt ühendada viimast korda. 888 00:40:10,150 --> 00:40:15,089 Igal neist pesastatud nõuab iga nende pesastatud ühendab, ma ikka järjestatud. 889 00:40:15,089 --> 00:40:18,380 Ma liideti need kaks venda, siis need kaks poisid, siis need kaks ja nii edasi. 890 00:40:18,380 --> 00:40:19,955 >> Nii et ma ei ühinevad uuesti ja uuesti. 891 00:40:19,955 --> 00:40:20,580 Mitu korda? 892 00:40:20,580 --> 00:40:23,510 Nii et iga kord, kui ma jagatud nimekirja pooleks, tegin ühendamine. 893 00:40:23,510 --> 00:40:25,460 Jagage nimekirja pooleks, seda ühendamist. 894 00:40:25,460 --> 00:40:28,570 Nii et kui jagades nimekiri saab teha log n korda, 895 00:40:28,570 --> 00:40:33,880 ühendamine ja lõpuks võtab n samme, mis võivad olla nüüd üleval 896 00:40:33,880 --> 00:40:37,000 seondunud pooleli aega meie algoritmi? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> Ja tõepoolest, see on, mida oleme saavutanud siin. 899 00:40:40,560 --> 00:40:44,650 Nii tunned, et sa vaata visuaalselt kui need kolm asja joosta kõrvuti 900 00:40:44,650 --> 00:40:47,930 on n ruudus vastu n ruuduline vastu n log n. 901 00:40:47,930 --> 00:40:51,010 Mis põhimõtteliselt me ​​näeme, mitte ainult täna, vaid ka tulevikus, 902 00:40:51,010 --> 00:40:52,760 on palju, palju kiiremini. 903 00:40:52,760 --> 00:40:56,010 Aplausi need kutid, Ma premeerida neid stressi pallid. 904 00:40:56,010 --> 00:41:00,260 Lähme edasi lükata täna siin, ja me näeme esmaspäeval. 905 00:41:00,260 --> 00:41:02,255