1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> Ræðumaður: Allt í lagi, þetta er CS50. 3 00:00:14,910 --> 00:00:19,020 Þetta er endir viku þrjú, og ef þú hefur ekki nýtt sér nú þegar, 4 00:00:19,020 --> 00:00:21,790 veit að það mun vera hádegismatur á föstudaginn eins og venjulega, þar 5 00:00:21,790 --> 00:00:25,430 þú getur notið góða hegðun og mat á Fire og Ice 6 00:00:25,430 --> 00:00:27,980 með nokkrum af CS50 er starfsfólk og bekkjarfélaga. 7 00:00:27,980 --> 00:00:30,170 Höfuð á þessa slóð hér. 8 00:00:30,170 --> 00:00:33,420 >> Nú getur þú muna, eða þú gæti brátt að kynnast, 9 00:00:33,420 --> 00:00:35,970 þetta hér, sem eru gefin út í lok 10 00:00:35,970 --> 00:00:37,850 á önn fyrir mörgum bekkjum. 11 00:00:37,850 --> 00:00:40,870 Svokallaða exam bláa bækur, sem þú skrifar svörin við prófum. 12 00:00:40,870 --> 00:00:44,240 Nú hef ég hér 26 slík blár bækur, á hver þeirra 13 00:00:44,240 --> 00:00:47,580 er skrifað nafn, A í gegnum Z. Og örugglega nöfn eru svo einfalt, A 14 00:00:47,580 --> 00:00:50,490 gegnum Z. Og einn af markmið á hendi í dag 15 00:00:50,490 --> 00:00:53,910 er að fara að vera að halda áfram hvað við byrjuðum á mánudaginn, sem er ekki 16 00:00:53,910 --> 00:00:57,830 svo mikið að horfa á kóða, en í raun horfa á hugmyndum og leysa vandamál. 17 00:00:57,830 --> 00:01:00,170 Eitt af markmiðum og loforð þetta námskeið 18 00:01:00,170 --> 00:01:02,985 er að kenna þér að hugsa meira vandlega, meira skipulega, 19 00:01:02,985 --> 00:01:05,400 og til að leysa vandamál á skilvirkari hátt. 20 00:01:05,400 --> 00:01:09,526 Og reyndar, við getum gert það í raun án þess þó að snerta línu af kóða. 21 00:01:09,526 --> 00:01:12,150 Svo ég hafa a par af fílum upp hér í dag, appelsínugult og blátt, 22 00:01:12,150 --> 00:01:15,780 ef við gætum fengið einn sjálfboðaliða, kannski frá lengra aftur en venjulega. 23 00:01:15,780 --> 00:01:18,070 Hvernig væri rétt þar, koma niður. 24 00:01:18,070 --> 00:01:24,180 Markmið sem er að fara að vera að hjálpa plús gefa þessu prófi hér. 25 00:01:24,180 --> 00:01:24,935 Hvað er nafn þitt? 26 00:01:24,935 --> 00:01:25,768 >> Áhorfendur: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 Ræðumaður: María Beth, koma upp. 28 00:01:27,560 --> 00:01:29,560 Leyfðu mér að fá hljóðnemann hér fyrir þig. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Gaman að hitta þig. 31 00:01:32,880 --> 00:01:34,005 >> Áhorfendur: Gaman að hitta þig. 32 00:01:34,005 --> 00:01:36,790 Ræðumaður: Allt í lagi, þannig að ég hef hér blár bækur A í gegnum Z, 33 00:01:36,790 --> 00:01:41,680 og ég ætla að láta sem Ég hef einn af nemendum, 34 00:01:41,680 --> 00:01:45,770 og þeir eru að koma í nokkuð af handahófi í lok þriggja klukkustunda próf blokk, 35 00:01:45,770 --> 00:01:49,400 svo þeir eru að lenda í sumum hálf-handahófi röð eins og þetta. 36 00:01:49,400 --> 00:01:54,510 Nú er starf þitt í réttlátur a augnablik er að fara að be-- þetta er í raun hvernig þeir fá 37 00:01:54,510 --> 00:01:56,820 sneri í lok bekknum, líklega. 38 00:01:56,820 --> 00:02:01,120 Starf þitt núna er að fara að vera, alveg einfaldlega, að raða þessum bláa bækur fyrir okkur 39 00:02:01,120 --> 00:02:05,220 frá A gegnum Z. 40 00:02:05,220 --> 00:02:08,400 >> Áhorfendur: Ó, þetta er að fara að taka að eilífu. 41 00:02:08,400 --> 00:02:13,747 >> Ræðumaður: Og við munum horfa eins og þú gerir þetta, enginn þrýstingur. 42 00:02:13,747 --> 00:02:15,330 Áhorfendur: Nei, enginn þrýstingur eða neitt. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> Ræðumaður: Og til gamans, skulum setja upp teljara. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> Áhorfendur: Svo mikið gaman, svo mikið gaman. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> Ræðumaður: Ég get haldið á mic fyrir þig. 49 00:02:38,574 --> 00:02:40,240 Allt í lagi, við höfum bara tvöfaldast hraða okkar. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Svo í millitíðinni, láta mig sitja hvað er fara að vera spurning fyrir Mary Beth 52 00:02:49,060 --> 00:02:51,540 er hvað er hún að gera, hvernig er hún að fara um að leysa þetta? 53 00:02:51,540 --> 00:02:54,040 Og í raun, þú might ekki hafa alltaf hugsun um eitthvað 54 00:02:54,040 --> 00:02:57,440 svo einfalt eins og þegar þú velur upp 26 bækur eins og þetta, 55 00:02:57,440 --> 00:02:59,350 sem hafa náttúrulega panta þá. 56 00:02:59,350 --> 00:03:01,335 Hvað er ferlið sem þú notar í raun og veru? 57 00:03:01,335 --> 00:03:03,770 Er það nokkuð af handahófi bara tína fyrsta sem þú sérð 58 00:03:03,770 --> 00:03:05,250 og setja hana á sinn stað? 59 00:03:05,250 --> 00:03:09,680 Ert þú að fara fyrst hendurnar í kring Útlit fyrir þá að leita að B? 60 00:03:09,680 --> 00:03:11,722 Ert þú að taka a líta á a par af þeim hlið við hlið 61 00:03:11,722 --> 00:03:14,680 og bara segja, bíddu í eina mínútu, þetta er ekki í lagi, og þá skipta um röð? 62 00:03:14,680 --> 00:03:16,960 Við sáum þegar á mánudaginn að það er a tala af lifnaðarhættir 63 00:03:16,960 --> 00:03:22,140 þar sem við getum gert þetta, og örugglega eins og við undir lok hér, 64 00:03:22,140 --> 00:03:26,360 Ég myndi taka mið kannski hvat Mary Beth er að gera. 65 00:03:26,360 --> 00:03:30,040 Við höfum nokkrar hrúgur það virðist, er stærri, þrjú smærri. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> Áhorfendur: Ég panta þá þegar ég finn tvo stafi 68 00:03:36,415 --> 00:03:39,540 sem ég veit eru saman í röð, Ég setti þá saman þannig að ég er ekki 69 00:03:39,540 --> 00:03:42,915 að hafa áhyggjur óður í gæsla lag af heild röð af bókum. 70 00:03:42,915 --> 00:03:45,706 Það er bara, ó, A er fyrst, Ég hef fengið þessa stafla hér. 71 00:03:45,706 --> 00:03:47,580 Ræðumaður: Svo, næstum eins og a stykki púsluspil sem 72 00:03:47,580 --> 00:03:49,860 hafa rétt form á passa upp með hvert annað. 73 00:03:49,860 --> 00:03:51,026 Áhorfendur: Nokkuð mikið, já. 74 00:03:51,026 --> 00:03:55,320 Ræðumaður: Allt í lagi, frábært. 75 00:03:55,320 --> 00:03:59,850 Og nú hvert af þessum hrúgur er væntanlega raðað? 76 00:03:59,850 --> 00:04:00,990 >> Áhorfendur: Já. 77 00:04:00,990 --> 00:04:09,900 >> Ræðumaður: Allt í lagi, A til Z. All rétt, til hamingju, þú gerðir það. 78 00:04:09,900 --> 00:04:11,461 Þú hefur val þitt. 79 00:04:11,461 --> 00:04:11,960 Blár? 80 00:04:11,960 --> 00:04:13,530 Allt í lagi, þakka þér fyrir það. 81 00:04:13,530 --> 00:04:16,679 Svo María Beth gerði leggja hvað nálgun hennar var, 82 00:04:16,679 --> 00:04:19,720 en hvað er annar aðferð hvernig þú gæti farið um flokkun þetta? 83 00:04:19,720 --> 00:04:21,130 Hvað myndir þú hafa gert? 84 00:04:21,130 --> 00:04:24,060 Met að slá hefði verið eina mínútu og 50 eða svo sekúndur, 85 00:04:24,060 --> 00:04:26,039 auk þær sem ég gleymdi að telja. 86 00:04:26,039 --> 00:04:27,080 Hvað myndir þú hafa gert? 87 00:04:27,080 --> 00:04:27,579 Já? 88 00:04:27,579 --> 00:04:28,735 Áhorfendur: Taktu stakkur. 89 00:04:28,735 --> 00:04:29,776 Byrja frá byrjun. 90 00:04:29,776 --> 00:04:32,284 Athugaðu blöð. 91 00:04:32,284 --> 00:04:36,586 Og ef efst einn er hærri en kannski eru þeir, 92 00:04:36,586 --> 00:04:38,980 botn einn er hærri, þá skipta þær. 93 00:04:38,980 --> 00:04:41,300 >> Ræðumaður: Allt í lagi, svo byrja efst og neðst, 94 00:04:41,300 --> 00:04:43,716 og þá vinna leið inn svona, skipta þá? 95 00:04:43,716 --> 00:04:46,580 Allt í lagi, þannig að smá svipað í anda þess sem kúla tagi, 96 00:04:46,580 --> 00:04:49,160 en velja öfgar ekki eru aðliggjandi pör. 97 00:04:49,160 --> 00:04:52,080 En stutt það er að það er vafalaust fullt af mismunandi vegu 98 00:04:52,080 --> 00:04:54,210 við gætum gert þetta, og hreinskilnislega, ég held þér svona 99 00:04:54,210 --> 00:04:55,700 samþykkt nokkrar aðferðir, ekki satt? 100 00:04:55,700 --> 00:05:00,567 Þú lést konar fjórum raðað hrúgur, og þá í raun sameinað þá saman. 101 00:05:00,567 --> 00:05:02,650 Og það er, eflaust, annar tækni að öllu leyti. 102 00:05:02,650 --> 00:05:06,950 Þú varst ekki að meðhöndla það eins og einn stór stafli, þú skipt vandamál í fjóra quads, 103 00:05:06,950 --> 00:05:09,820 ef þú vilt, og þá einhvern veginn sameinaði í lokin. 104 00:05:09,820 --> 00:05:13,410 >> Svo skulum við íhuga, að lokum, hvernig annars gætum gert þetta. 105 00:05:13,410 --> 00:05:15,860 Við formlegt hugmynd af kúla röðun síðasta sinn, 106 00:05:15,860 --> 00:05:18,780 og kúla raða muna var reiknirit sem við sjáanlegir 107 00:05:18,780 --> 00:05:22,640 við átta bekkjarfélaga þína upp hér, virðist af handahófi raðað í fyrstu. 108 00:05:22,640 --> 00:05:26,110 Og við ákváðum þá pöruðum, ef tveir þættir eru í ólagi, 109 00:05:26,110 --> 00:05:26,950 einfaldlega skipta á þeim. 110 00:05:26,950 --> 00:05:28,930 Svo fjögurra og tveir eru augljóslega út af röð, 111 00:05:28,930 --> 00:05:31,080 svo þessir tveir bekkjarfélagar skiptu um stöður. 112 00:05:31,080 --> 00:05:35,390 Og þá erum við endurtekin með fjórum og sex, átta þá sex og á hverjum endurtekning, 113 00:05:35,390 --> 00:05:36,980 flytja til hægri. 114 00:05:36,980 --> 00:05:42,590 >> Svo gefið átta manns, hversu margir pöruðum samanburð gerði ég á meðan gangandi frá 115 00:05:42,590 --> 00:05:45,220 vinstri til hægri í einni endurtekning? 116 00:05:45,220 --> 00:05:48,410 Hversu margir samanburð? 117 00:05:48,410 --> 00:05:49,197 Sjö, ekki satt? 118 00:05:49,197 --> 00:05:51,405 Vegna þess að ef það er átta fólk en þú hefur par 119 00:05:51,405 --> 00:05:53,880 þá og þú halda áfram einn step til hægri, 120 00:05:53,880 --> 00:05:56,060 þú ert ekki að fara að hafa átta samanburður vegna þess að þú getur ekki bera saman 121 00:05:56,060 --> 00:05:59,226 þáttur sjálfu sér, eða að það væri bara vera tilgangslaust, þannig að þú hefur sjö. 122 00:05:59,226 --> 00:06:01,290 Eða oftast, ef Við höfum n manns, við 123 00:06:01,290 --> 00:06:04,300 gera n mínus 1 samanburð með kúla tagi. 124 00:06:04,300 --> 00:06:08,150 >> Svo skulum nú íhuga hversu gott eða slæmur kúla tegund í raun var, og reyna 125 00:06:08,150 --> 00:06:13,570 að gefa okkur orðaforða með sem að gagnrýna reiknirit eins og þetta, 126 00:06:13,570 --> 00:06:14,430 og brátt okkar eigin. 127 00:06:14,430 --> 00:06:16,970 Svo í fyrstu umferð um kúla tagi, í fyrsta sinn 128 00:06:16,970 --> 00:06:20,909 Ég gekk frá vinstri til hægri yfir á stigi, tók mig n mínus 1 samanburð. 129 00:06:20,909 --> 00:06:22,950 Og það er að fara að vera minn eining mál, ekki satt? 130 00:06:22,950 --> 00:06:26,170 Ég var eins konar tala og göngutúrar, nokkuð hratt, nokkuð hægur, 131 00:06:26,170 --> 00:06:29,300 svo að telja fjölda mína sekúndum er ekki sérstaklega að segja, 132 00:06:29,300 --> 00:06:32,260 en að telja fjölda aðgerðir sem ég gerði á mánudaginn, 133 00:06:32,260 --> 00:06:35,900 bera saman tvær manneskjur, sem finnst eins og a ágætur mælieiningu. 134 00:06:35,900 --> 00:06:40,980 >> Svo n mínus 1 skref í fyrsta skipti, en hvað þá gerðist eftir það? 135 00:06:40,980 --> 00:06:46,610 Hvað er einn Upside of einu framhjá gegnum annað óflokkuðu lista? 136 00:06:46,610 --> 00:06:49,840 Hvað getur þú sagt mér um frumefni sem var alla leið þarna? 137 00:06:49,840 --> 00:06:51,300 Já? 138 00:06:51,300 --> 00:06:52,870 Það var stærsta þáttur, ekki satt? 139 00:06:52,870 --> 00:06:55,710 Númer átta, jafnvel þótt hún byrjaði hér, í hvert skipti sem ég 140 00:06:55,710 --> 00:06:57,860 samanborið hana við nágranni, hélt hún 141 00:06:57,860 --> 00:07:00,480 freyðandi upp til hægri hönd hlið af listanum. 142 00:07:00,480 --> 00:07:02,710 Og reyndar, það er þar sem reiknirit fær nafn sitt. 143 00:07:02,710 --> 00:07:07,630 >> Nú eftir að rökfræði, hversu margir samanburð þarf ég að gera á í annað sinn 144 00:07:07,630 --> 00:07:09,800 Ég gera það framhjá frá vinstri til hægri? 145 00:07:09,800 --> 00:07:10,730 n mínus 2, ekki satt? 146 00:07:10,730 --> 00:07:14,297 Það myndi bara vera að sóa tíma mínum ef ég halda samanburður átta gegn einhverjum 147 00:07:14,297 --> 00:07:16,630 annars vegna þess að við vitum nú þegar hún var á réttum stað. 148 00:07:16,630 --> 00:07:19,760 Svo er það hluti af óákveðinn greinir í ensku hagræðingu, þannig að næsta umferð 149 00:07:19,760 --> 00:07:23,899 er að fara að vera plús n mínus tvö skref, þar sem n er fjöldi fólks. 150 00:07:23,899 --> 00:07:26,940 Nú þú getur konar framreikna, jafnvel ef þú ert ekki tölvuna vísindamaður, 151 00:07:26,940 --> 00:07:27,680 hvernig þetta endar. 152 00:07:27,680 --> 00:07:31,259 Í lok þessa reiknirit, væntanlega þú hafir fengið bara eitt samanburður vinstri. 153 00:07:31,259 --> 00:07:33,800 Þú þarft að konar festa farin af listanum ef tveimur 154 00:07:33,800 --> 00:07:36,540 og einn eru í ólagi og ætti að vera einn og tveir, 155 00:07:36,540 --> 00:07:40,330 þannig að þetta nær lágmarki í auk 1 endanleg samanburður. 156 00:07:40,330 --> 00:07:44,500 >> Nú punktur, punktur, punktur konar bylgjum það er hendur á sumir af the juicier upplýsingar, 157 00:07:44,500 --> 00:07:46,452 en við skulum bara fara á undan og einfalda. 158 00:07:46,452 --> 00:07:48,660 Ef þú manst úr hár skóla, hreinskilnislega, a einhver fjöldi af þér 159 00:07:48,660 --> 00:07:50,340 hafði stærðfræði bækur sem höfðu smá svindl blaði 160 00:07:50,340 --> 00:07:52,550 á framhliðinni eða að bakhliðina sem sýndi þér 161 00:07:52,550 --> 00:07:56,400 hvað röð summations eins þetta á endanum bætt upp. 162 00:07:56,400 --> 00:07:59,600 Í almennu máli, ef þú hafa a breytu eins n, og raunar þetta, 163 00:07:59,600 --> 00:08:01,634 ef þú lítur á þinn gamla skólanum stærðfræði bók, 164 00:08:01,634 --> 00:08:04,050 þú myndir sjá að þetta í raun bætir upp til þessa upphæð hér, 165 00:08:04,050 --> 00:08:07,970 n sinnum n mínus 1 öllum deilt með 2. 166 00:08:07,970 --> 00:08:11,172 Svo nú láta mig kveða bara þetta er satt, það á áræðni, 167 00:08:11,172 --> 00:08:12,880 það er það sem þetta dregur til, og við gátum 168 00:08:12,880 --> 00:08:14,341 sanna að í almennari tilfelli. 169 00:08:14,341 --> 00:08:15,590 En nú skulum auka þessa út. 170 00:08:15,590 --> 00:08:19,920 Svo skulum margfalda þetta út, svo það er n veldi mínus n, allt deilt með 2. 171 00:08:19,920 --> 00:08:23,200 Það er í raun n veldi, deilt með 2, mínus n yfir 2, 172 00:08:23,200 --> 00:08:25,010 svo það er allt gott og áhugavert. 173 00:08:25,010 --> 00:08:27,060 En hvað gerist ef við nú stinga í gildi? 174 00:08:27,060 --> 00:08:29,724 Segjum að ég hafði ekki átta fólk, en segja milljón. 175 00:08:29,724 --> 00:08:31,890 Og milljón bara vegna þess að það er ansi stór tala, 176 00:08:31,890 --> 00:08:34,039 skulum stinga því inn og sjá hvað gerist. 177 00:08:34,039 --> 00:08:39,039 Svo ef ég stinga milljón inn í þessi formúlu Ég ætla að fá milljón ferningur, 178 00:08:39,039 --> 00:08:42,868 deilt með 2, mínus milljónir, deilt með 2. 179 00:08:42,868 --> 00:08:44,159 Nú hvað er að fara til að jafna? 180 00:08:44,159 --> 00:08:47,354 Svo 500 milljarðar, mínus 500.000. 181 00:08:47,354 --> 00:08:49,270 Og ef ég geri að stærðfræði út, það þýðir 182 00:08:49,270 --> 00:08:53,920 að flokka milljón fólk með kúla tagi 183 00:08:53,920 --> 00:09:01,800 gæti tekið mig 499.999.500.000 skref eða samanburður í lokin, 184 00:09:01,800 --> 00:09:02,900 við erum bara að framreikna. 185 00:09:02,900 --> 00:09:06,860 >> Það er ansi hægur, en hreinskilnislega mæla einu tilteknu inntak 186 00:09:06,860 --> 00:09:09,160 eins og þetta, er ekki allt sem að segja. 187 00:09:09,160 --> 00:09:14,050 En reyndar er það benda til þess að eins og n fær stærri og stærri, þetta reiknirit 188 00:09:14,050 --> 00:09:16,280 konar finnst verra og verri, eða þú virkilega 189 00:09:16,280 --> 00:09:20,450 byrja að finna fyrir sársauka af því exponentiation, að n veldi, 190 00:09:20,450 --> 00:09:21,770 sem bætir upp ansi hratt. 191 00:09:21,770 --> 00:09:25,340 Og þetta smáatriði er ekki glataður á fólk, í raun 192 00:09:25,340 --> 00:09:29,640 nokkur ár síðan ákveðinn þingmaður sem var berjast, settist í viðtal 193 00:09:29,640 --> 00:09:32,180 Eiríks Google Schmidt, forstjóri á þeim tíma, 194 00:09:32,180 --> 00:09:36,380 og var mótmælt með spurningu mikið eins og við erum að kanna í dag. 195 00:09:36,380 --> 00:09:38,468 Við skulum taka a líta. 196 00:09:38,468 --> 00:09:45,280 >> [Vídeó spilun] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Þú ert hér á Google, og ég eins og 198 00:09:48,560 --> 00:09:53,382 að hugsa um formennsku sem atvinnuviðtal. 199 00:09:53,382 --> 00:09:56,434 Nú, það er erfitt að fá starf sem forseti, 200 00:09:56,434 --> 00:09:58,100 og þú ert að fara í gegnum kuldahrollur núna. 201 00:09:58,100 --> 00:10:01,860 Það er líka erfitt að fá vinnu á Google. 202 00:10:01,860 --> 00:10:05,490 Við hafa spurningar, og við spyrja frambjóðendur spurninga okkar, 203 00:10:05,490 --> 00:10:09,770 og þetta er frá Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 What-- þú krakkar hugsa ég grínast, það er hér. 205 00:10:14,760 --> 00:10:17,930 Hvað er skilvirkasta leiðin til að raða milljón 32-bita heiltölur? 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 >> Ég er hryggur, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Nei, nei, nei. 210 00:10:27,400 --> 00:10:30,700 Ég held að kúla konar væri röng leið til að fara. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> Svona, sem sagði honum þetta? 213 00:10:38,180 --> 00:10:40,590 Ég vissi ekki að sjá tölvuna vísindi í bakgrunn þinn. 214 00:10:40,590 --> 00:10:42,130 >> -We've Fékk njósnara okkar í það. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK Skulum spyrja aðra viðtal spurning. 217 00:10:48,444 --> 00:10:49,300 >> [END vídeó spilun] 218 00:10:49,300 --> 00:10:52,290 >> Ræðumaður: Svo að tala um sérstakar tölur þó, 219 00:10:52,290 --> 00:10:53,890 er ekki að fara að vera allt að gagni. 220 00:10:53,890 --> 00:10:56,810 Það er ekki líf kennslustund sem kúla raða, gefið milljón inntak, 221 00:10:56,810 --> 00:10:58,590 gæti tekið eins og margir eins og 500 milljarða skrefum. 222 00:10:58,590 --> 00:11:01,120 Þú getur í raun ekki alhæfa of hátt frá því 223 00:11:01,120 --> 00:11:03,560 og gera góða ákvarðanir hönnun þegar þú skrifar forrit. 224 00:11:03,560 --> 00:11:07,070 Svo skulum einbeita þó á hvernig við gætum einfalda þessa niðurstöðu. 225 00:11:07,070 --> 00:11:11,780 >> Þannig að ég hef bent á gulu hér afleiðing n kvaðrat deilt með 2, 226 00:11:11,780 --> 00:11:14,330 svo milljón ferningur deilt með 2, og þá 227 00:11:14,330 --> 00:11:16,710 Ég hef hápunktur hvað fullkominn svarið var 228 00:11:16,710 --> 00:11:20,180 þegar við dregin burt n deilt með 2. 229 00:11:20,180 --> 00:11:24,850 Og krafan sem ég ætla að gera núna er sem Heck sama ef þú draga burt 230 00:11:24,850 --> 00:11:30,060 smá gamall n yfir 2 þegar fyrsta hluti af þessari jöfnu er svo miklu stærri? 231 00:11:30,060 --> 00:11:33,910 Það drottnar hinn Hugtakið, n kvaðrat deilt með 2 232 00:11:33,910 --> 00:11:37,510 er svo miklu stærri, greinilega, eins og n fær stór eins og milljón, 233 00:11:37,510 --> 00:11:41,450 það er það í raun mikill munur á lok dags milli 500 milljarða 234 00:11:41,450 --> 00:11:45,730 og 499.999.500.000? 235 00:11:45,730 --> 00:11:46,349 Ekki í raun. 236 00:11:46,349 --> 00:11:48,640 Og svo það sem við erum að fara að gera eins og tölva vísindamenn er 237 00:11:48,640 --> 00:11:53,270 hunsa þá lægri röð skilmála og taka eitthvað eins og þetta og í raun 238 00:11:53,270 --> 00:11:56,050 bara einfalda það til Hugtakið sem er að fara að máli. 239 00:11:56,050 --> 00:12:00,315 Stærri gagnagrunna okkar fá, því stærri gagnagrunna okkar fá, því fleiri vefsíður 240 00:12:00,315 --> 00:12:02,690 við verðum að leita að meira vinir sem þú ert með á Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Sem n fær stærra, erum við í raun fara að hugsa um stærsta 242 00:12:07,340 --> 00:12:11,560 tíma í slíkum greiningu reiknirit árangur okkar. 243 00:12:11,560 --> 00:12:16,230 Og ég ætla að segja, þú veist hvað, kúla tegund er á röð af stór O, 244 00:12:16,230 --> 00:12:18,060 á röð af n öðru veldi. 245 00:12:18,060 --> 00:12:20,090 Það er ekki nákvæmlega n kvaðrat eins og við höfum séð, 246 00:12:20,090 --> 00:12:22,060 en hver raunverulega annt um þá smærri hugtök, 247 00:12:22,060 --> 00:12:24,390 og hreinskilnislega, sem raunverulega sama ef við deilum með 2? 248 00:12:24,390 --> 00:12:25,870 Það er bara stöðug þáttur. 249 00:12:25,870 --> 00:12:29,480 Og er 500 milljarðar á móti 250 milljarða í raun það stór af a samningur? 250 00:12:29,480 --> 00:12:32,190 Ég gæti bara bíða eitt ár, láta fartölvuna mína bókstaflega 251 00:12:32,190 --> 00:12:34,810 fá tvisvar sinnum eins hratt í vélbúnaði, og þessi tegund af mismunur 252 00:12:34,810 --> 00:12:36,650 bara fer í burtu náttúrulega með tímanum. 253 00:12:36,650 --> 00:12:39,300 >> Það sem við þykir vænt um er tjáningu, sá hluti 254 00:12:39,300 --> 00:12:42,489 á tjáningu sem er að fara til að vera breytilegur sem inntak okkar fær stærri og stærri. 255 00:12:42,489 --> 00:12:45,280 Og reyndar, í hinum raunverulega heimi, það er það sem er að gerast í auknum mæli 256 00:12:45,280 --> 00:12:48,330 er inntak á vandamálum okkar og reiknirit eru að fá stærri. 257 00:12:48,330 --> 00:12:53,470 Svo stór O er að fara til vera the tákn, sem asymptotic rithátturinn, að vér bara 258 00:12:53,470 --> 00:12:57,160 nota sem tölvunarfræðingar að lýsa árangur, eða keyra tíma, 259 00:12:57,160 --> 00:12:58,130 af reiknirit. 260 00:12:58,130 --> 00:13:00,800 Svo að við getum saman reiknirit á mismunandi tölvum skrifaðar 261 00:13:00,800 --> 00:13:04,170 með mismunandi fólki, með því að nota sumir grundvallaratriðum svipuð mæligildi 262 00:13:04,170 --> 00:13:07,557 eins og fjölda samanburð sem þú ert gerð, eða kannski fjölda skiptasamninga 263 00:13:07,557 --> 00:13:08,140 þú ert að gera. 264 00:13:08,140 --> 00:13:11,910 >> Það sem við erum ekki að fara að Bréfafjöldi er the magn af tími 265 00:13:11,910 --> 00:13:13,981 sem fer á klukkuna á vegg venjulega. 266 00:13:13,981 --> 00:13:16,230 Það sem við erum ekki að fara að hafa áhyggjur um er hversu mikið minni 267 00:13:16,230 --> 00:13:17,820 þú ert að nota í dag á kosti, þó það er 268 00:13:17,820 --> 00:13:19,370 annar auðlind sem við gætum mæla. 269 00:13:19,370 --> 00:13:23,610 Við ætlum að reyna að byggja greiningu okkar á aðeins helstu aðgerðir, þær, 270 00:13:23,610 --> 00:13:25,930 hreinskilnislega, að þú getur séð mest sjónrænt. 271 00:13:25,930 --> 00:13:30,700 Svo með eitthvað eins og stór O á n kvaðrat, ég halda því fram að O n veldi 272 00:13:30,700 --> 00:13:35,820 er skilgreina efri mörk svokallaða gangi þegar kúla tagi. 273 00:13:35,820 --> 00:13:38,820 Með öðrum orðum, ef þú vildi halda því fram að það er 274 00:13:38,820 --> 00:13:41,370 þetta efri mörk á hversu margir stíga reiknirit gæti tekið, 275 00:13:41,370 --> 00:13:46,240 það er að fara að vera í stóru O á n í öðru veldi í þessu tilfelli, skilgreina efri mörk. 276 00:13:46,240 --> 00:13:49,710 >> Hvað ef ég breyti í stað þess Sagan að vera ekki um kúla tagi, 277 00:13:49,710 --> 00:13:50,910 en um þetta efri. 278 00:13:50,910 --> 00:13:54,030 Getur þú hugsa um reiknirit að við höfum horft á þegar 279 00:13:54,030 --> 00:13:59,530 Hvers efri, hámark mæla tíma eða starfsemi, 280 00:13:59,530 --> 00:14:04,300 væri að segja að afmarkast af n, línulegt fall, 281 00:14:04,300 --> 00:14:07,260 ekki annars stigs einn sem er boginn? 282 00:14:07,260 --> 00:14:10,780 Hvað er reiknirit sem alltaf tekur ekki meira 283 00:14:10,780 --> 00:14:12,860 en eins og n skrefum eða 2n skref eða 3N skref? 284 00:14:12,860 --> 00:14:13,360 Já? 285 00:14:13,360 --> 00:14:15,030 >> Áhorfendur: Að finna Stærsta talan í listanum? 286 00:14:15,030 --> 00:14:16,930 >> Ræðumaður: Perfect, finna stærsta tala í lista. 287 00:14:16,930 --> 00:14:18,940 Ef ég er gefið lista yfir fólk til dæmis, 288 00:14:18,940 --> 00:14:21,440 hver sem heldur að tala, hvað er hámarksfjöldi 289 00:14:21,440 --> 00:14:23,770 skref ætti að taka mig, nokkuð klár maður, 290 00:14:23,770 --> 00:14:27,530 að finna stærsta mann á listanum? 291 00:14:27,530 --> 00:14:28,100 n, ekki satt? 292 00:14:28,100 --> 00:14:31,320 Vegna þess að í versta tilfelli, þar gæti stærsta gildi vera? 293 00:14:31,320 --> 00:14:32,700 Hægri, alla leið á enda. 294 00:14:32,700 --> 00:14:34,575 Svo í versta falli efri bundið, gæti ég 295 00:14:34,575 --> 00:14:36,450 verða að fara alla leið hérna og vera eins, 296 00:14:36,450 --> 00:14:39,170 ó, hér er númer átta, eða hvað sem gildi. 297 00:14:39,170 --> 00:14:41,330 Nú það væri bara heimskulegt ef ég hélt að fara, ekki satt? 298 00:14:41,330 --> 00:14:43,840 Að leita að fleiri og fleiri þætti ef síðasta af þeim er þarna? 299 00:14:43,840 --> 00:14:45,340 Svo örugglega, n er heil efri. 300 00:14:45,340 --> 00:14:47,420 Ég þarf ekki að taka fleiri skref en það. 301 00:14:47,420 --> 00:14:51,580 >> Svo hvað ef í staðinn ég lagði til að það eru reiknirit í þessum heimi sem 302 00:14:51,580 --> 00:14:57,750 hafa hlaupandi tími sem er afmarkast af stór O frá log n, skráðu þig n? 303 00:14:57,750 --> 00:15:00,390 Hvar höfum við séð þetta áður? 304 00:15:00,390 --> 00:15:00,890 Já? 305 00:15:00,890 --> 00:15:03,309 >> Áhorfendur: Í símaskrá vandamál? 306 00:15:03,309 --> 00:15:04,850 Ræðumaður: Eins og símaskrá vandamál. 307 00:15:04,850 --> 00:15:07,754 Hver var mælikvarði á hversu mikill tími eða hversu margir, eyðir það 308 00:15:07,754 --> 00:15:10,170 tók mig að finna einhvern eins og Mike Smith í símaskránni? 309 00:15:10,170 --> 00:15:13,212 Við krafa það var log n, og jafnvel þótt ókunnur eða það að það er 310 00:15:13,212 --> 00:15:15,170 svolítið óljós hvað lógariþma eða veldisvísirinn var, 311 00:15:15,170 --> 00:15:17,650 bara muna að log n yfirleitt átt við ferli, 312 00:15:17,650 --> 00:15:20,790 í þessu tilfelli, af því að deila eitthvað í tvennt aftur, og aftur, 313 00:15:20,790 --> 00:15:25,790 og aftur, og aftur, þannig að það fær sífellt lítill eins og þú gerir það. 314 00:15:25,790 --> 00:15:28,470 >> Svo skráðu þig á n vísar, viss, að símaskránni td 315 00:15:28,470 --> 00:15:32,662 til tvöfaldur leit í orði, þegar við hafði raunverulegur dyr á borð, 316 00:15:32,662 --> 00:15:34,370 eða þegar Sean var að leita að einhverju. 317 00:15:34,370 --> 00:15:37,374 Ef hann hefði notað tvöfaldur leit, skráðu þig n væri efri mörk hversu mikið 318 00:15:37,374 --> 00:15:38,040 tími sem tekur. 319 00:15:38,040 --> 00:15:44,027 En þessir reiknirit sem hljóp í Annállinn n ráð hvað lykill smáatriði? 320 00:15:44,027 --> 00:15:45,360 Að listinn var flokkaður, ekki satt? 321 00:15:45,360 --> 00:15:47,789 Reiknirit er rangt ef inntak þitt er ekki raðað, 322 00:15:47,789 --> 00:15:49,830 og enn þú ert að nota eitthvað eins og tvöfaldur leit 323 00:15:49,830 --> 00:15:51,704 vegna þess að þú gætir hoppað rétt yfir frumefni 324 00:15:51,704 --> 00:15:53,600 án þess að átta það er örugglega það. 325 00:15:53,600 --> 00:15:55,600 >> Nú hvað gæti þetta þýtt, stór O í einu? 326 00:15:55,600 --> 00:15:59,117 Þetta þýðir ekki að reiknirit þinn tekur einn og aðeins eitt skref, 327 00:15:59,117 --> 00:16:01,200 það þýðir bara að það tekur stöðug ýmis skref. 328 00:16:01,200 --> 00:16:04,060 Kannski er það 1, kannski er það 10, kannski er það 1000, 329 00:16:04,060 --> 00:16:07,750 en það er óháð stærð vandans. 330 00:16:07,750 --> 00:16:10,850 Sama hversu stór n er, stöðug tími reiknirit 331 00:16:10,850 --> 00:16:12,747 tekur alltaf sama fjölda af skrefum. 332 00:16:12,747 --> 00:16:15,080 Svo hvað gæti verið reiknirit Við höfum talað um eða bara 333 00:16:15,080 --> 00:16:20,418 innsæi kemur að þér að alltaf rennur í svokölluðu föstu tíma? 334 00:16:20,418 --> 00:16:20,918 Já? 335 00:16:20,918 --> 00:16:22,001 >> Áhorfendur: Bæta tvær tölur. 336 00:16:22,001 --> 00:16:25,320 Ræðumaður: Bæta tvær tölur, 2 plús 2 er 4, gert. 337 00:16:25,320 --> 00:16:27,227 Svo það gæti vinna, hvað annað? 338 00:16:27,227 --> 00:16:28,560 Hvernig væri meira alvöru heiminum, já? 339 00:16:28,560 --> 00:16:30,686 >> Áhorfendur: Að finna fyrstur hlutur í listanum. 340 00:16:30,686 --> 00:16:32,810 Ræðumaður: Að finna fyrsta þáttur í lista, viss. 341 00:16:32,810 --> 00:16:34,540 Við höfum í raun verið að tala um fylki nú þegar, 342 00:16:34,540 --> 00:16:36,540 hvernig gera þú fá að minnsta Fyrsta þáttur í fylki, 343 00:16:36,540 --> 00:16:40,465 sama hversu lengi array er í C ​​kóða? 344 00:16:40,465 --> 00:16:43,090 Þú notar bara eins krappi núll ritháttur, Bam, þú ert þar. 345 00:16:43,090 --> 00:16:46,120 Og örugglega fylki, sem til hliðar, Stuðningur eitthvað almennt þekkt 346 00:16:46,120 --> 00:16:49,240 eins handahófi aðgang, handahófi aðgang minni, vegna þess að þú getur bókstaflega 347 00:16:49,240 --> 00:16:50,284 hoppa til hvaða einum stað. 348 00:16:50,284 --> 00:16:52,700 Við getum gert þetta jafnvel meira einfaldlega við getum baka í viku núll 349 00:16:52,700 --> 00:16:53,900 þegar við gerðum grunni. 350 00:16:53,900 --> 00:16:59,707 Hversu mikill tími fór það að taka fyrir segja blokk í grunni til að framkvæma? 351 00:16:59,707 --> 00:17:00,790 Bara stöðug skipti, ekki satt? 352 00:17:00,790 --> 00:17:03,960 Segja eitthvað, segja eitthvað, það skiptir ekki máli 353 00:17:03,960 --> 00:17:07,359 hversu stór klóra heimurinn er, það er alltaf að fara að taka sama magn af tíma 354 00:17:07,359 --> 00:17:08,490 að einfaldlega segja eitthvað. 355 00:17:08,490 --> 00:17:11,089 >> Svo er það stöðug tími, en hvað er bakhlið? 356 00:17:11,089 --> 00:17:13,030 Ef það var efri mörk, hvað ef við viljum 357 00:17:13,030 --> 00:17:17,089 að lýsa neðri mörk reiknirita okkar hlaupandi tími? 358 00:17:17,089 --> 00:17:19,852 Næstum besta mál hugsanlega, ef þú vilt, 359 00:17:19,852 --> 00:17:23,060 þó að þessi hugtök gætu sótt að bestu tilvikum verstu tilvikum, meðaltal tilvikum meira 360 00:17:23,060 --> 00:17:26,359 almennt, en við skulum bara einblína á lægri mörk almennt. 361 00:17:26,359 --> 00:17:31,920 Hvað er reiknirit sem hefur lægri bundinn af n skrefum, 362 00:17:31,920 --> 00:17:33,350 eða 2n skref eða 3N skref? 363 00:17:33,350 --> 00:17:36,241 Sumir þáttur n skrefum, það er þess neðri. 364 00:17:36,241 --> 00:17:36,740 Já? 365 00:17:36,740 --> 00:17:37,910 >> Áhorfendur: Bubble tegund? 366 00:17:37,910 --> 00:17:41,610 >> Ræðumaður: Bubble tegund tekur þú óverulega n skref, hvers vegna? 367 00:17:41,610 --> 00:17:42,279 Hvers vegna er það? 368 00:17:42,279 --> 00:17:45,320 Hvers vegna ætti að byrja að koma til þín innsæi, jafnvel ef það virkar ekki bara 369 00:17:45,320 --> 00:17:46,530 enn? 370 00:17:46,530 --> 00:17:47,030 Já? 371 00:17:47,030 --> 00:17:47,990 >> Áhorfendur: [inaudible]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 Ræðumaður: Einmitt. 374 00:17:52,360 --> 00:17:55,810 Í bestu mögulegu aðstæður á kúla tagi, og mikið af reiknirita, 375 00:17:55,810 --> 00:17:58,769 ef ég hendi þér átta manns sem eru nú þegar raðað, 376 00:17:58,769 --> 00:18:00,560 það væri heimska fyrir þig, reiknirit, 377 00:18:00,560 --> 00:18:02,202 að fara fram og til baka oftar en einu sinni, ekki satt? 378 00:18:02,202 --> 00:18:04,285 Því eins fljótt og þú ganga í gegnum listann einu sinni, 379 00:18:04,285 --> 00:18:08,090 þú ættir að átta sig á, ó, ég gerði ekkert skiptasamninga, þessi listi er raðað, hætta. 380 00:18:08,090 --> 00:18:09,700 En það er að fara að taka þig n skrefum. 381 00:18:09,700 --> 00:18:12,033 >> Og öfugt, hvað er annað hugsun um það? 382 00:18:12,033 --> 00:18:15,240 Bubble tegund er ómega, svo að segja, af N, 383 00:18:15,240 --> 00:18:19,050 því ef þú lítur á færri en n þætti, hvað 384 00:18:19,050 --> 00:18:23,009 er grundvallaratriði þar? 385 00:18:23,009 --> 00:18:24,550 Þú veist ekki hvort það er raðað, satt. 386 00:18:24,550 --> 00:18:26,800 Við menn gætu litið á átta fólk og vera eins, ó, það er raðað, 387 00:18:26,800 --> 00:18:28,430 sem ekki taka mig n skref, en það gerði. 388 00:18:28,430 --> 00:18:30,810 Augun, jafnvel þótt þér góður af hafa stóran sjónsvið, 389 00:18:30,810 --> 00:18:33,184 þú horft á átta þáttum, þú horft á átta manns, 390 00:18:33,184 --> 00:18:34,610 það er átta þrep á áhrifaríkan hátt. 391 00:18:34,610 --> 00:18:38,612 Og aðeins ef ég geng í gegnum allt listi ég átta sig á, já, raðað. 392 00:18:38,612 --> 00:18:41,320 Ef ég stoppa á miðri leið að hugsa, allir rétt, það er frekar raðað svo langt, 393 00:18:41,320 --> 00:18:42,520 hvað eru líkurnar að það er ekki raðað? 394 00:18:42,520 --> 00:18:44,186 Að reiknirit ekki að fara að vera rétt. 395 00:18:44,186 --> 00:18:46,250 Gæti verið hraðar, en röng. 396 00:18:46,250 --> 00:18:48,500 >> Svo nú höfum við leið lýsa upp lægri mörk, 397 00:18:48,500 --> 00:18:49,710 og hvað um föstu tíma? 398 00:18:49,710 --> 00:18:54,565 Hvað er reiknirit sem hefur lægri bundið á gengi hennar síðan einn? 399 00:18:54,565 --> 00:18:58,350 1 skref, 2 skref, 10 skref, en fasti, óháð n, 400 00:18:58,350 --> 00:18:59,310 stærð inntak? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Já, í bakinu. 403 00:19:04,600 --> 00:19:05,309 >> Áhorfendur: printf? 404 00:19:05,309 --> 00:19:06,183 Ræðumaður: Hvað er það? 405 00:19:06,183 --> 00:19:07,184 Áhorfendur: printf? 406 00:19:07,184 --> 00:19:07,850 Ræðumaður: printf. 407 00:19:07,850 --> 00:19:08,400 Allt í lagi, viss. 408 00:19:08,400 --> 00:19:10,720 Þannig að það tekur ákveðinn fjölda af skrefum. 409 00:19:10,720 --> 00:19:13,170 Og ég ætti að now-- nú að við erum að tala um C kóða 410 00:19:13,170 --> 00:19:16,040 og ekki Scratch, eitthvað eins segja, með printf, 411 00:19:16,040 --> 00:19:17,710 við ættum að byrja að fá varkár. 412 00:19:17,710 --> 00:19:21,090 Vegna printf er tekið inntak, það er band, 413 00:19:21,090 --> 00:19:23,220 og strengir hafa tæknilega lengd. 414 00:19:23,220 --> 00:19:25,530 Svo ef við viljum nú að velja á þig, ef þú dont 'hugur, 415 00:19:25,530 --> 00:19:29,430 tæknilega gætum við halda því fram að printf þýðir að taka breytilega lengd inntak, 416 00:19:29,430 --> 00:19:32,270 og hlýtur það gæti tekið meira tími til að prenta streng þessu lengi, 417 00:19:32,270 --> 00:19:33,560 en þetta lengi. 418 00:19:33,560 --> 00:19:36,570 >> Svo hvað ef við teljum bara flokkun og leita dæmum? 419 00:19:36,570 --> 00:19:40,450 Hvað um Mike Smith í símanum bók, eða tvöfaldur leit almennt? 420 00:19:40,450 --> 00:19:42,220 Í besta tilfelli, hvað gæti gerst? 421 00:19:42,220 --> 00:19:45,577 Ég opna símaskrána og Bam, það er númer Mike Smith. 422 00:19:45,577 --> 00:19:46,660 Ég get hringt hann strax. 423 00:19:46,660 --> 00:19:49,390 >> Tók eitt skref, kannski tveimur skrefum, en stöðug tala af skrefum 424 00:19:49,390 --> 00:19:50,230 ef ég var heppinn. 425 00:19:50,230 --> 00:19:52,570 Og hreinskilnislega, sáum við á Mánudagur bekkjarfélaga þinn 426 00:19:52,570 --> 00:19:54,710 fá alveg heppinn tvisvar í röð. 427 00:19:54,710 --> 00:19:57,050 Og það var reyndar stöðug tími í neðri mörk 428 00:19:57,050 --> 00:20:01,280 á reiknirit sem um ræðir til að finna númer 50 á bak þeim lokað 429 00:20:01,280 --> 00:20:01,830 hurðir. 430 00:20:01,830 --> 00:20:06,400 >> Nú, eins og innskot, ef þú uppgötvar að bæði stór O, efri, 431 00:20:06,400 --> 00:20:09,310 og ómega, lægri mörk, eru einn á sama, að 432 00:20:09,310 --> 00:20:11,830 er það sama uppskrift í svigum, getur þú einnig 433 00:20:11,830 --> 00:20:15,170 segja, bara að vera fínt, að eitthvað er í þeta 434 00:20:15,170 --> 00:20:18,270 n eða þeta af einhverjum öðrum gildi. 435 00:20:18,270 --> 00:20:20,661 Það þýðir bara þegar stór O og omega eru þeir sömu. 436 00:20:20,661 --> 00:20:21,910 Hvað um val tagi núna? 437 00:20:21,910 --> 00:20:23,400 Við skulum nota þetta nýja orðaforða. 438 00:20:23,400 --> 00:20:27,407 Í val tagi, hvað vorum við gera aftur, og aftur, og aftur? 439 00:20:27,407 --> 00:20:29,990 Ég var að fara fram og til baka í gegnum lista, leita fyrir hvern? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Minnsti fjöldi. 442 00:20:34,730 --> 00:20:37,560 >> Svo hversu margir stíga, hvernig margir samanburð gerði ég 443 00:20:37,560 --> 00:20:43,250 að gera í því skyni að reikna út hver minnsti þáttur í listanum var? 444 00:20:43,250 --> 00:20:44,437 n mínus 1, ekki satt? 445 00:20:44,437 --> 00:20:47,770 Vegna þess að ef ég byrja bara með einn sem ég er gefið og ég byrja að bera saman við honum, 446 00:20:47,770 --> 00:20:49,519 þá hann eða hana, hann eða hana, hann eða hana, ég 447 00:20:49,519 --> 00:20:52,010 getur aðeins parað þætti saman n mínus 1 sinnum. 448 00:20:52,010 --> 00:20:55,630 Svo val tekur tegund álíka n mínus 1 skref í fyrsta skipti. 449 00:20:55,630 --> 00:20:59,540 >> Hversu mörg skref tekur það mig til finna næstminnsta frumefni? 450 00:20:59,540 --> 00:21:02,920 n mínus 2, vegna þess að ég er að vera heimsk ef ég halda að horfa á sama fólkið 451 00:21:02,920 --> 00:21:06,280 aftur ef ég hef nú þegar valið hann eða hana og setja þá á sinn stað. 452 00:21:06,280 --> 00:21:09,270 Og þriðja skrefið, n mínus 3, 4 þá var n mínus. 453 00:21:09,270 --> 00:21:11,020 Við höfum séð þetta mynstur áður, og raunar 454 00:21:11,020 --> 00:21:13,460 Val tegund álíka hefur skilgreina efri mörk 455 00:21:13,460 --> 00:21:16,210 af n kvaðrat ef við gerum upp að samantekt. 456 00:21:16,210 --> 00:21:19,790 Hvað er lægri bundinn, val tegund þess? 457 00:21:19,790 --> 00:21:25,350 Óverulega, hversu mikill tími verður val raða taka, eins og við skilgreint það á mánudaginn? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Leggja til tvo valkosti. 460 00:21:30,490 --> 00:21:32,360 Kannski er það n, eins og áður. 461 00:21:32,360 --> 00:21:35,040 Kannski er það n veldi, sem það er nú sem efri. 462 00:21:35,040 --> 00:21:35,874 >> Áhorfendur: n veldi. 463 00:21:35,874 --> 00:21:36,664 Ræðumaður: n veldi. 464 00:21:36,664 --> 00:21:37,368 Hvers vegna? 465 00:21:37,368 --> 00:21:40,060 >> Áhorfendur: Þar sem þú ert að skilgreina [inaudible]. 466 00:21:40,060 --> 00:21:41,510 >> Ræðumaður: Einmitt. 467 00:21:41,510 --> 00:21:45,077 Að minnsta kosti eins og ég skilgreint val konar það var nokkuð barnaleg, að halda áfram, 468 00:21:45,077 --> 00:21:46,160 finna minnstu frumefni. 469 00:21:46,160 --> 00:21:47,770 Fara aftur, finna minnstu frumefni. 470 00:21:47,770 --> 00:21:49,490 Fara aftur, finna minnstu frumefni. 471 00:21:49,490 --> 00:21:51,700 Það er engin tegund af hagræðingu þar sem 472 00:21:51,700 --> 00:21:54,350 gæti látið mig hætta eftir bara n eða svo skref. 473 00:21:54,350 --> 00:21:57,080 Svo reyndar, val raða, ómega n veldi. 474 00:21:57,080 --> 00:22:00,667 >> Hvað um Innsetningarröðun, þar sem ég tók sem ég fékk, og þá er ég plopped honum 475 00:22:00,667 --> 00:22:01,750 eða hana á réttum stað? 476 00:22:01,750 --> 00:22:04,958 Þá er ég gekk til seinni mann, plopped honum á réttum stað. 477 00:22:04,958 --> 00:22:07,910 Þá er næsta manneskja, plopped hann eða hana á réttum stað. 478 00:22:07,910 --> 00:22:10,537 Takið eftir að þetta er mjög línuleg, svo að segja. 479 00:22:10,537 --> 00:22:12,620 Ég er bein lína, ég er ekki að fara fram og til baka, 480 00:22:12,620 --> 00:22:16,080 Ég hef aldrei að horfa til baka í raun, en hvað er að gerast þegar ég setja hann 481 00:22:16,080 --> 00:22:20,302 eða hana í upphafi listinn sem við gerðum á mánudaginn? 482 00:22:20,302 --> 00:22:21,010 Hvað er að gerast? 483 00:22:21,010 --> 00:22:21,510 Já? 484 00:22:21,510 --> 00:22:23,122 Áhorfendur: [inaudible]. 485 00:22:23,122 --> 00:22:24,830 Ræðumaður: Já, að var aflinn, ekki satt? 486 00:22:24,830 --> 00:22:26,746 Þú gætir muna úr bekkjarfélagar þínir, ef þeir 487 00:22:26,746 --> 00:22:29,670 voru að gera allar hreyfingar með fætur þeirra, sem var aðgerð. 488 00:22:29,670 --> 00:22:33,610 Þannig að ef það voru þrjár manneskjur hérna og sem ný manneskja átti leið þarna, 489 00:22:33,610 --> 00:22:37,360 á löngu stigi svona viss, hann eða hún gæti bara farið til enda. 490 00:22:37,360 --> 00:22:40,074 En ef við erum að hugsa um að tölva og fjölda minni, 491 00:22:40,074 --> 00:22:41,990 þetta fólk er að fara að þurfa að stokka yfir 492 00:22:41,990 --> 00:22:43,260 að gera pláss fyrir viðkomandi. 493 00:22:43,260 --> 00:22:46,930 Og svo að n mínus 1 shufflings, n mínus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 mínus 3 shufflings er bara svona að gerast fyrir aftan mig, ekki fyrir framan mig 495 00:22:50,660 --> 00:22:52,710 eins og áður, í einhverjum skilningi. 499 00:22:52,557 --> 00:22:54,640 Nú sem innskot, og eins þú gætir hafa séð á netinu 500 00:22:54,640 --> 00:22:57,699 ef þú byrjar poking í kring um konar, það er svo margar mismunandi sjálfur 501 00:22:57,699 --> 00:22:59,490 þarna úti, sumir þeirra betri en aðrir. 502 00:22:59,490 --> 00:23:02,200 Reyndar, bogosort er einn það er góður af gaman að horfa upp. 503 00:23:02,200 --> 00:23:06,650 Bogosort tekur mengi númer eða segja spilastokk, 504 00:23:06,650 --> 00:23:09,870 stokkar þau og eftirlit ef þeir eru raðað. 505 00:23:09,870 --> 00:23:12,130 Og ef ekki, er það aftur. 506 00:23:12,130 --> 00:23:14,140 Og ef ekki, er það aftur. 507 00:23:14,140 --> 00:23:15,440 Ef ekki, er það aftur. 508 00:23:15,440 --> 00:23:17,060 Ótrúlega heimskulegt. 509 00:23:17,060 --> 00:23:19,520 >> Og reyndar, ef þú lest eins og Wikipedia grein, 510 00:23:19,520 --> 00:23:21,200 Gælunafnið hennar er heimskur tegund. 511 00:23:21,200 --> 00:23:25,180 Það mun að lokum vinna, vonandi, gefinn nægur tími, 512 00:23:25,180 --> 00:23:28,240 en það magn af tími gæti tekið þó nokkurn tíma. 513 00:23:28,240 --> 00:23:31,650 Svo ef ég gæti, við skulum hraða hlutum upp úr td Mary Beth fyrr, 514 00:23:31,650 --> 00:23:35,150 með því að hafa nokkur fleiri atriði, en tvo örgjörva. 515 00:23:35,150 --> 00:23:37,100 Tveir menn, ef þér myndi ekki hug að taka þátt mér. 516 00:23:37,100 --> 00:23:40,972 Hvernig um 1 hérna, og skulum go-- enginn þarna? 517 00:23:40,972 --> 00:23:41,722 Enginn þarna? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 Þú með svarta skyrta, já, komdu niður. 520 00:23:44,190 --> 00:23:45,000 Allt í lagi, hvað er nafnið þitt? 521 00:23:45,000 --> 00:23:45,720 >> Áhorfendur: Pétur. 522 00:23:45,720 --> 00:23:46,100 >> Ræðumaður: Hvað er það? 523 00:23:46,100 --> 00:23:46,766 >> Áhorfendur: Pétur. 524 00:23:46,766 --> 00:23:49,450 Ræðumaður: Pétur, Davíð, gaman að hitta þig. 525 00:23:49,450 --> 00:23:53,670 Allt í lagi, við höfum Pétur hér, ef þú vil koma inn á borð hérna. 526 00:23:53,670 --> 00:23:54,550 Og hvað er nafnið þitt? 527 00:23:54,550 --> 00:23:55,216 >> Áhorfendur: Elena. 528 00:23:55,216 --> 00:23:55,970 Ræðumaður: Elena. 529 00:23:55,970 --> 00:23:57,030 Allt í lagi, gaman að hitta þig. 530 00:23:57,030 --> 00:23:58,060 Elena hitta Pétur. 531 00:23:58,060 --> 00:23:59,170 Pétur, Elena. 532 00:23:59,170 --> 00:24:02,290 Og við þurfum Andrési upp hér eins og heilbrigður, vinsamlegast. 533 00:24:02,290 --> 00:24:06,107 Og áskorun er að fara að vera að raða spilastokk. 534 00:24:06,107 --> 00:24:08,190 Og ef ókunnur, þilfari af kortum ætti að lokum 535 00:24:08,190 --> 00:24:11,064 vera flokkaður smá eitthvað eins þetta þar sem við munum gera klúbba, þá 536 00:24:11,064 --> 00:24:13,660 sem spaða, þá hjörtu og demöntum, frá Ás sem einn, 537 00:24:13,660 --> 00:24:15,570 alla leið upp að konungi. 538 00:24:15,570 --> 00:24:20,890 >> Spilin sem ég ætla að gefa þér eru að fara að vera 52 í magni. 539 00:24:20,890 --> 00:24:23,160 Við erum að fara að álíka tími þig, á aðeins augnablik. 540 00:24:23,160 --> 00:24:26,410 Við erum að fara að henda Andrew upp á skjánum hér, 541 00:24:26,410 --> 00:24:28,170 svo sem að horfa á eins og þú gerir þetta. 542 00:24:28,170 --> 00:24:31,070 Og svo að öll þessi er allt meira áberandi, 543 00:24:31,070 --> 00:24:33,490 þetta eru spil sem ég fékk á Amazon. 544 00:24:33,490 --> 00:24:42,861 Svo þeir eru nú þegar af handahófi raðað, og við erum að fara að tíma þig. 545 00:24:42,861 --> 00:24:44,610 Og við erum að fara að halda það raunverulegt í þetta sinn, 546 00:24:44,610 --> 00:24:47,820 þannig að við erum að fara að reyna að þrýstingur þig því annars mun þetta fá leiðinlegur 547 00:24:47,820 --> 00:24:48,460 fljótt. 548 00:24:48,460 --> 00:24:53,860 Ef þú gætir haldið áfram að raða 52 þættir saman í gegnum sumir hætti, núna. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> Og aftur, eins og við horfa þær krakkar gera hvað, í lok 551 00:25:07,180 --> 00:25:10,200 er að fara að framleiða augljós Niðurstaðan, hugsa um raunverulega 552 00:25:10,200 --> 00:25:12,962 hvernig þeir eru á hverjum að gera það, hvernig þú gætir lýst því. 553 00:25:12,962 --> 00:25:15,045 Því aftur, þetta eru allt ferli, reiknirit 554 00:25:15,045 --> 00:25:17,090 að við tökum sem sjálfsögðum hlut eins og mönnum. 555 00:25:17,090 --> 00:25:22,349 En þú hefur sennilega lengi haft innsæi, löngu áður en þú jafnvel 556 00:25:22,349 --> 00:25:24,390 hugsað um að taka upp tölvunarfræði bekknum þér 557 00:25:24,390 --> 00:25:27,223 gæti hafa haft innsæi með sem til að leysa vandamál eins og þetta. 558 00:25:27,223 --> 00:25:29,560 En þegar þú kannast mynstrin og byrja 559 00:25:29,560 --> 00:25:32,407 að formlega skrefin sem þú ert að leysa þessi vandamál, 560 00:25:32,407 --> 00:25:35,490 þú munt finna að þú getur leyst mikið áhugaverðari og miklu flóknari 561 00:25:35,490 --> 00:25:39,190 vandamál fljótt. 562 00:25:39,190 --> 00:25:42,351 Svo, hvað er einhver frá áhorfendum að minnsta kosti einn þáttur í reiknirit 563 00:25:42,351 --> 00:25:43,350 að þeir eru að nota hérna? 564 00:25:43,350 --> 00:25:44,275 >> Áhorfendur: [inaudible] 565 00:25:44,275 --> 00:25:45,150 Ræðumaður: Hvað er það? 566 00:25:45,150 --> 00:25:47,062 Áhorfendur: Með föt. 567 00:25:47,062 --> 00:25:47,770 Ræðumaður: Eftir föt. 568 00:25:47,770 --> 00:25:50,630 Svo fyrst þeir eru Þyrping allar demöntum saman 569 00:25:50,630 --> 00:25:52,560 það virðist, allt að hjörtu saman það virðist, 570 00:25:52,560 --> 00:25:56,520 og svo framvegis, án þess að því er varðar fyrir tölur um spilin. 571 00:25:56,520 --> 00:26:00,900 Og nú eru þeir birtast, til dæmis, að flokka þær eftir fjölda. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Mjög gott. 574 00:26:08,910 --> 00:26:12,370 >> Allt í lagi, svo hvað er að fara að vera síðasta skrefið þá hér? 575 00:26:12,370 --> 00:26:16,950 Þegar við höfum fjóra flokkuð föt, hvað þurfum við að gera til fjögurra hrúgur 576 00:26:16,950 --> 00:26:20,059 í því skyni að ná fram einn raðað þilfari, einfaldlega? 577 00:26:20,059 --> 00:26:21,350 Þannig að við þurfum að sameinast þeim aftur. 578 00:26:21,350 --> 00:26:25,160 >> Svo er það áhugavert hugmynd að aftur, eflaust, er mjög leiðandi, jafnvel 579 00:26:25,160 --> 00:26:28,140 ef þú gætir aldrei hafa löðrungur þannig merki á það. 580 00:26:28,140 --> 00:26:31,900 Þessi grundvallaratriði hugmynd að deila vandamálið ekki í hálfan þessum tíma, 581 00:26:31,900 --> 00:26:33,410 en að minnsta kosti í fjóra hluta. 582 00:26:33,410 --> 00:26:36,810 Solving ansi mikið grundvallaratriðum samhljóða vandamál 583 00:26:36,810 --> 00:26:40,480 í einangrun á hvern annan, og þá sameina niðurstöður. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 Og frábært, gert. 586 00:26:50,140 --> 00:26:52,140 Allt í lagi, stór kringlótt af lófaklapp, ef við gátum. 587 00:26:52,140 --> 00:26:56,480 >> [Applause] 588 00:26:56,480 --> 00:26:59,740 >> Ræðumaður: Ég hef ekki hugmynd um hvað þú munt gera með þetta, en hér þú fara. 589 00:26:59,740 --> 00:27:01,690 Þakka þér svo mikið. 590 00:27:01,690 --> 00:27:04,660 Svo skulum sjá, tvær mínútur og átta sekúndur, 591 00:27:04,660 --> 00:27:07,490 ef þú vilt áskorun vinum þínum. 592 00:27:07,490 --> 00:27:12,160 Hvað þá er að fara að vera tekið í burtu frá þessu 593 00:27:12,160 --> 00:27:13,830 að við getum skiptimynt almennt? 594 00:27:13,830 --> 00:27:16,080 Jæja, hugsa aftur til þetta fylki af tölum, 595 00:27:16,080 --> 00:27:19,060 og hugsa til baka núna til sumir af the sauðakóðanum við höfum skrifað í fortíðinni, 596 00:27:19,060 --> 00:27:22,080 og þetta var sauðakóðanum fyrir leysa símaskrá vandamál. 597 00:27:22,080 --> 00:27:25,150 Þar í sauðakóðanum I talin meiri methodical hátt 598 00:27:25,150 --> 00:27:28,400 að lýsa hvernig ég gerði mjög leiðandi manna reiknirit deila símann 599 00:27:28,400 --> 00:27:31,650 bók í tvennt, endurtaka, endurtaka, endurtaka, þar til ég finna einhvern eins og Mike Smith, 600 00:27:31,650 --> 00:27:33,790 ef hann er örugglega í símaskránni. 601 00:27:33,790 --> 00:27:37,610 >> En ég nota svona sem ég ætla að hringja mjög endurtekningu nálgun hér, 602 00:27:37,610 --> 00:27:42,160 einkum fyrirvara línu 8 og lína 11. 603 00:27:42,160 --> 00:27:46,750 Þeir eru vísbendingar um endurtekningu nálgun, a lykkja nálgun, 604 00:27:46,750 --> 00:27:49,040 því það er einmitt hegðun sem þeir framkalla. 605 00:27:49,040 --> 00:27:52,910 Þeir línur bæði segja að fara til lína þrír, og þú getur konar 606 00:27:52,910 --> 00:27:55,140 hugsa um það í þínum auga hugans eins og að vera lykkja. 607 00:27:55,140 --> 00:27:59,080 Það er að segja þér að fara aftur upp að stíga þrír og endurtaka aftur og aftur, 608 00:27:59,080 --> 00:28:00,010 og aftur. 609 00:28:00,010 --> 00:28:04,410 >> En hvað ef við nýta á takka hugmynd hér að við gerðum ekki í síðasta sinn, 610 00:28:04,410 --> 00:28:10,280 og einfalda línu 8 og lína 11 og nágrannar þeirra 611 00:28:10,280 --> 00:28:12,840 eins og bara þetta, í gulum. 612 00:28:12,840 --> 00:28:16,480 Það er ekki í grundvallaratriðum að stytta að sauðakóðanum mjög mikið, 613 00:28:16,480 --> 00:28:20,530 en það er í grundvallaratriðum að breyta eðli reiknirit mitt. 614 00:28:20,530 --> 00:28:24,220 Það sem ég er nú að segja í skrefi 7, í skrefi 10, 615 00:28:24,220 --> 00:28:29,140 er að leita að Mike í nákvæmlega sama hátt, 616 00:28:29,140 --> 00:28:31,580 en bara í vinstri helmingur eða hægri helminginn. 617 00:28:31,580 --> 00:28:33,420 >> Svo í öðrum orðum, ef Ég byrja frá skrefi eitt, 618 00:28:33,420 --> 00:28:36,150 taka upp símaskrána opin miðju af símaskránni líta á nöfn, 619 00:28:36,150 --> 00:28:39,010 ef Smith er meðal nafn er, kalla Mike, annars 620 00:28:39,010 --> 00:28:44,340 ef Smith er fyrr í bókinni, stíga sjö leita Mike í vinstri hluta bókarinnar. 621 00:28:44,340 --> 00:28:47,130 En þannig er eins það er afgangur mig hangandi, ekki satt? 622 00:28:47,130 --> 00:28:49,240 Í gulum, er kennsla, en hvernig geri ég 623 00:28:49,240 --> 00:28:51,870 leita Mike í vinstri helmingur símaskránni? 624 00:28:51,870 --> 00:28:54,210 Hvar fæ ég að reiknirit sem ég 625 00:28:54,210 --> 00:28:57,100 Hægt er að leita að einhverjum eins Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Jæja, það er starandi okkur í andlitið. 627 00:28:58,980 --> 00:29:03,090 Ég get bókstaflega notað nákvæmlega sama program í raun að fara upp á toppinn 628 00:29:03,090 --> 00:29:06,490 aftur og aftur hlaupandi sömu línur af kóða. 629 00:29:06,490 --> 00:29:10,610 >> Svo jafnvel þótt þetta ætti að líða eins og a hluti af a cyclical skilgreiningu 630 00:29:10,610 --> 00:29:13,480 þar sem þú ert að svara einhverjum er spurning bara með svona spyrja 631 00:29:13,480 --> 00:29:15,990 sama spurning aftur, eins hvers vegna, hvers vegna, hvers vegna? 632 00:29:15,990 --> 00:29:21,580 Staðreyndin er sú að við höfum harður á dulmáli a par af sérstökum línum, skref 4, 633 00:29:21,580 --> 00:29:25,320 sem er ef, og skref 12, þar sem er í raun önnur útibú, 634 00:29:25,320 --> 00:29:30,120 vegna þess að við höfum þá stopgap ráðstafanir, þetta reiknirit mun segja ef við 635 00:29:30,120 --> 00:29:32,050 finna Mike, eða ef við gerum það ekki. 636 00:29:32,050 --> 00:29:36,810 En í skrefi 7 og 10 núna, höfum við það sem við munum kalla endurkvæma reiknirit. 637 00:29:36,810 --> 00:29:40,420 Og endurkvæmni er örugglega öflugur hugmynd það er smá hugur beygja í fyrstu, 638 00:29:40,420 --> 00:29:42,500 að við getum nú sótt þannig. 639 00:29:42,500 --> 00:29:46,600 >> Sameina raða verður síðasta tegund sem við líta á, að minnsta kosti í flokki formlega. 640 00:29:46,600 --> 00:29:50,040 Og það er í grundvallaratriðum öðruvísi frá þeim síðustu þremur, og vissulega 641 00:29:50,040 --> 00:29:52,140 síðustu fjórum, ef við eru bogosort. 642 00:29:52,140 --> 00:29:54,810 Hér er sauðakóðanum fyrir sameiningu tagi. 643 00:29:54,810 --> 00:30:00,170 Þegar um inntak n þáttum, svo gefið fylki af stærð n, ef n er minna en 2, 644 00:30:00,170 --> 00:30:01,040 aftur. 645 00:30:01,040 --> 00:30:03,610 Svo hvers vegna þarf ég að geðheilbrigði athuga fyrst? 646 00:30:03,610 --> 00:30:09,477 Hvað er óbeint ef ég hendi þér fylki sem lengd n er minna en 2? 647 00:30:09,477 --> 00:30:11,060 Það er nú þegar raðað, augljóslega, ekki satt? 648 00:30:11,060 --> 00:30:13,640 Vegna þess að listi hefur annaðhvort einn þáttur, sem er trivially 649 00:30:13,640 --> 00:30:15,180 raðað því það er það eina þar. 650 00:30:15,180 --> 00:30:18,138 Eða, er það af stærð núll, sem þýðir það er ekkert til að flokka, svo eðli sínu 651 00:30:18,138 --> 00:30:18,720 það er flokkað. 652 00:30:18,720 --> 00:30:20,410 Það er bara ekkert rangt þarna. 653 00:30:20,410 --> 00:30:22,310 Svo er það svo-kallað stöð mál okkar. 654 00:30:22,310 --> 00:30:24,440 >> Það er svipað í anda að það sem við gerðum með Mike. 655 00:30:24,440 --> 00:30:26,023 Ef Mike er í símaskránni, hringja í hann. 656 00:30:26,023 --> 00:30:27,740 Ef hann er ekki þarna, gefa upp. 657 00:30:27,740 --> 00:30:31,240 Það er svo-kölluð stöð að ræða, að ganga úr skugga um þetta reiknirit í lok dags 658 00:30:31,240 --> 00:30:33,540 mun hætta í vissum tilvikum. 659 00:30:33,540 --> 00:30:37,890 >> En hér er áræðni nú, annars, raða vinstri helming þætti, 660 00:30:37,890 --> 00:30:39,740 þá raða rétt helmingur af þeim þáttum, 661 00:30:39,740 --> 00:30:41,189 og þá sameina raðað helminga. 662 00:30:41,189 --> 00:30:43,230 Og hér er þar sem það finnst eins og við erum að copping út. 663 00:30:43,230 --> 00:30:46,900 Ég hef beðið þig að raða n þættir, og ég er 664 00:30:46,900 --> 00:30:50,712 segja, OK, það með því að flokka vinstri og flokkun rétt. 665 00:30:50,712 --> 00:30:52,420 En ég er að segja eitt annar hlutur, og þetta 666 00:30:52,420 --> 00:30:55,530 er lykillinn þema virðist í innsæi svona langt, 667 00:30:55,530 --> 00:30:57,380 það er þetta þriðja skref að sameina. 668 00:30:57,380 --> 00:31:00,430 Sem jafnvel þótt það virðist svo heimsk í anda, 669 00:31:00,430 --> 00:31:02,320 eins bara sameinast hluti saman, það virðist 670 00:31:02,320 --> 00:31:05,380 að vera mikilvægt skref í átt að reassembly af tveimur vandamálum sem 671 00:31:05,380 --> 00:31:07,330 var skipt lokum í tvennt. 672 00:31:07,330 --> 00:31:12,090 >> Svo sameinast konar, við skulum gera þetta, ef þú munt húmor mig, og enn eitt sýnikennslu, 673 00:31:12,090 --> 00:31:14,730 bara svo að við höfum sumir tölur til að vinna með. 674 00:31:14,730 --> 00:31:19,470 Get ég skipt átta streitu bolta fyrir átta manns? 675 00:31:19,470 --> 00:31:29,320 Allt í lagi, hvernig um þig þrír, þú fjórir í þessum kafla, fimm, sex, og við skulum 676 00:31:29,320 --> 00:31:30,720 gera 7, 8, koma upp. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 Allt í lagi, já allt í lagi. 679 00:31:36,520 --> 00:31:38,640 Mínus 8, þar sem við komum, plús 1. 680 00:31:38,640 --> 00:31:39,150 Excellent. 681 00:31:39,150 --> 00:31:42,000 Allt í lagi að koma á þig, við skulum fljótt að gefa þér númer. 682 00:31:42,000 --> 00:31:50,800 Númer tvö, númer þrjú, númer fjögur, númer fimm, sex, sjö og átta. 683 00:31:50,800 --> 00:31:52,140 Ég gerði átta rétt í þetta sinn. 684 00:31:52,140 --> 00:31:56,390 >> Allt í lagi, þannig að fara á undan, ef þú gætir, og skulum raða í upprunalegu röð 685 00:31:56,390 --> 00:31:59,810 að við höfðum í gær, sem leit eins og þetta, ef þú vilt ekki huga. 686 00:31:59,810 --> 00:32:03,620 Og við skulum gera það fyrir framan borðið. 687 00:32:03,620 --> 00:32:06,510 Allt í lagi, svo sameinast konar. 688 00:32:06,510 --> 00:32:08,820 Þetta er þar sem það er að fara að fá eins konar áhugavert, 689 00:32:08,820 --> 00:32:12,800 vegna þess að ég virðist vera að gefa mér svo mikið minni upplýsingar í dag. 690 00:32:12,800 --> 00:32:15,149 >> Svo sameinast raða fyrst af öllu á inntak n þáttum, 691 00:32:15,149 --> 00:32:18,440 og er augljóslega ekki minna en tveir, það er átta, svo ég hef fengið meiri vinnu til að gera. 692 00:32:18,440 --> 00:32:21,140 Svo nú andlega við sem bekknum eru nú í annað útibú, 693 00:32:21,140 --> 00:32:22,540 sem þýðir þrjú skref. 694 00:32:22,540 --> 00:32:25,017 Fyrst verð ég að raða vinstri helmingur af þeim þáttum. 695 00:32:25,017 --> 00:32:26,350 Svo hvernig á ég að fara að gera þetta? 696 00:32:26,350 --> 00:32:28,950 Jæja, ég ætla að eins konar andlega skipta lista hér, 697 00:32:28,950 --> 00:32:30,700 þú þarft ekki að líkamlega færa, og ég er 698 00:32:30,700 --> 00:32:33,180 að fara að einblína á vinstri helmingur af þeim þáttum hér. 699 00:32:33,180 --> 00:32:36,770 Svo hvernig get ég farið um flokkun listi nú stærð fjórum? 700 00:32:36,770 --> 00:32:38,730 Hvað er algrím mitt? 701 00:32:38,730 --> 00:32:42,580 Fyrst ég athuga er n minna en tveir, nei, svo ég sný mér að öðrum blokk aftur. 702 00:32:42,580 --> 00:32:43,900 Raða eftir helming þætti. 703 00:32:43,900 --> 00:32:45,608 >> Svo nú aftur, andlega, og þetta er þar 704 00:32:45,608 --> 00:32:49,550 þú þarft að safna mikið af andlega sögu, ef þú vilt. 705 00:32:49,550 --> 00:32:51,940 Nú er ég að flokka vinstri helmingur af vinstri helming. 706 00:32:51,940 --> 00:32:57,000 Allt í lagi, svo nú ég kalla sama sameinast minn flokkun reiknirit, er n minna en tvö? 707 00:32:57,000 --> 00:33:00,590 Nei, er það tveir, þannig að ég verð að raða vinstri helming, og hægri helminginn. 708 00:33:00,590 --> 00:33:02,042 Svo hér við fara, raða vinstri helming. 709 00:33:02,042 --> 00:33:03,750 Hvers vegna ekki þú bara taka eitt skref fram á við. 710 00:33:03,750 --> 00:33:04,415 Hvað er nafn þitt? 711 00:33:04,415 --> 00:33:04,860 >> Áhorfendur: Darren. 712 00:33:04,860 --> 00:33:05,260 >> Ræðumaður: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan hefur stigið fram. 714 00:33:06,040 --> 00:33:06,748 >> Áhorfendur: Darren. 715 00:33:06,748 --> 00:33:09,000 Ræðumaður: Darren, gert. 716 00:33:09,000 --> 00:33:10,090 Sagðirðu Darren eða Dan? 717 00:33:10,090 --> 00:33:10,550 >> Áhorfendur: Darren. 718 00:33:10,550 --> 00:33:11,216 >> Ræðumaður: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren hefur stigið áfram og hann er nú flokkað. 720 00:33:14,422 --> 00:33:16,130 Og þetta er næstum inane krafa, ekki satt? 721 00:33:16,130 --> 00:33:18,862 Ég í raun ekki virðast til að vera að ná nokkuð, en við skulum halda áfram. 722 00:33:18,862 --> 00:33:20,820 Nú láta mig raða rétt helmingur af þeim þáttum. 723 00:33:20,820 --> 00:33:21,200 Hvað er nafn þitt? 724 00:33:21,200 --> 00:33:21,690 >> Áhorfendur: Luke. 725 00:33:21,690 --> 00:33:22,273 >> Ræðumaður: Luke. 726 00:33:22,273 --> 00:33:23,400 Komdu, stíga fram. 727 00:33:23,400 --> 00:33:25,640 Gert, ég hef raðað Luke. 728 00:33:25,640 --> 00:33:28,570 Vinstri helmingur er nú raðað og hægri helminginn er nú raðað, 729 00:33:28,570 --> 00:33:30,770 en aftur, það er mikilvægt skref hér. 730 00:33:30,770 --> 00:33:32,940 Hvað þarf ég næst að gera? 731 00:33:32,940 --> 00:33:33,941 Sameina raðað helminga. 732 00:33:33,941 --> 00:33:36,648 Nú erum við að fara að bara að hafa allir fram og til baka á þennan hátt, 733 00:33:36,648 --> 00:33:38,620 vegna þess að ég þarf svona sumir klóra pláss. 734 00:33:38,620 --> 00:33:40,411 Það er nánast eins og þetta krakkar eru á borð, 735 00:33:40,411 --> 00:33:42,460 og ég þarf smá pláss að færa þá í kring á. 736 00:33:42,460 --> 00:33:44,170 Þannig að ég ætla að fara að sameinast ykkur eftir að leita 737 00:33:44,170 --> 00:33:45,960 á vinstri helming og hægri hluta. 738 00:33:45,960 --> 00:33:48,740 Og hver augljóslega kemur fyrst, vinstri helmingur eða hægri helming? 739 00:33:48,740 --> 00:33:52,710 Svo hægri helminginn, þannig að við skulum fara Lúkas yfir hér að upprunalega stöðu Darren er. 740 00:33:52,710 --> 00:33:57,640 Og nú að sameinast vinstri helming þeirra í, Darren er að fara að flytja þarna. 741 00:33:57,640 --> 00:33:59,750 >> Svo er eins og næstum kúla konar áhrif, 742 00:33:59,750 --> 00:34:02,482 en grundvallaratriði reiknirit mitt, mjög mismunandi að þessu sinni. 743 00:34:02,482 --> 00:34:04,815 En nú er þar sem hlutirnir fá lítið pirrandi vegna þess að þú 744 00:34:04,815 --> 00:34:06,810 þurfa að spóla til baka andlega þar gerði ég fara burt. 745 00:34:06,810 --> 00:34:09,893 Ég hef bara sameinuð á flokkuð helminga, sem þýðir að ég er þar í reiknirit mitt? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Ég verð að raða rétt helmingur, ekki satt? 748 00:34:13,770 --> 00:34:15,910 >> Ef þú til baka, bókstaflega á vídeó, þú munt 749 00:34:15,910 --> 00:34:18,339 sjá að við fengum að þessu benda á Luke og Darren 750 00:34:18,339 --> 00:34:21,370 með því að flokka á vinstri helmingur af vinstri helming. 751 00:34:21,370 --> 00:34:23,430 Þá erum við sameinuð þeim Raðað helminga, sem 752 00:34:23,430 --> 00:34:27,941 þýðir að næsta skref er að raða hægri helminginn af vinstri helming. 753 00:34:27,941 --> 00:34:29,649 Allt í lagi, þannig að við skulum gera þetta hraðar. 754 00:34:29,649 --> 00:34:33,282 Allt í lagi, sex, ég ætla að halda því þú ert nú raðað, komdu fram. 755 00:34:33,282 --> 00:34:33,990 Hvað er nafn þitt? 756 00:34:33,990 --> 00:34:34,589 >> Áhorfendur: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> Ræðumaður: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano er nú flokkað. 759 00:34:36,010 --> 00:34:36,450 Og hvað er nafnið þitt? 760 00:34:36,450 --> 00:34:37,080 >> Áhorfendur: Alex. 761 00:34:37,080 --> 00:34:38,379 >> Ræðumaður: Alex er nú flokkað. 762 00:34:38,379 --> 00:34:40,750 Vinstri helmingur, hægri helming, hvað er lokaskrefið? 763 00:34:40,750 --> 00:34:41,250 Sameinast. 764 00:34:41,250 --> 00:34:44,310 Pretty léttvæg, þannig að ég er að fara að sameinast í sex, 765 00:34:44,310 --> 00:34:46,930 taka skref til baka, átta, taka skref til baka. 766 00:34:46,930 --> 00:34:49,530 Og nú taka þetta er gagnlegt takeaway, hvað 767 00:34:49,530 --> 00:34:53,930 er nú satt um vinstri hluta sem lista, án tillits til þess hvernig við byrjuðum? 768 00:34:53,930 --> 00:34:55,090 Það er flokkað. 769 00:34:55,090 --> 00:34:57,750 >> Nú það er ekki raðað í stóra fyrirætlun af hlutur, 770 00:34:57,750 --> 00:35:00,250 en það er raðað óháð á hinn helminginn. 771 00:35:00,250 --> 00:35:04,100 Nú hvað skref er ég á ef ég halda trekkja hvernig sagan hófst? 772 00:35:04,100 --> 00:35:05,680 Nú þarf ég að raða rétt helminginn. 773 00:35:05,680 --> 00:35:07,630 Svo nú erum við langt aftur í upphaf sögunnar, 774 00:35:07,630 --> 00:35:08,921 og við skulum gera þetta hraðar. 775 00:35:08,921 --> 00:35:11,320 Þannig að ég ætla að fara að raða rétt helmingur af öllum listanum. 776 00:35:11,320 --> 00:35:13,060 Hvað er næsta skref? 777 00:35:13,060 --> 00:35:15,840 Raða vinstri helming hægri helming. 778 00:35:15,840 --> 00:35:18,715 Raða vinstri helminginn af vinstri helmingur af the réttur helmingur. 779 00:35:18,715 --> 00:35:19,590 Og hvað er nafnið þitt? 780 00:35:19,590 --> 00:35:20,230 >> Áhorfendur: Omar. 781 00:35:20,230 --> 00:35:21,970 >> Ræðumaður: Omar, stíga fram, gert. 782 00:35:21,970 --> 00:35:22,860 Vinstri helmingurinn er flokkaður. 783 00:35:22,860 --> 00:35:23,330 Og hvað er nafnið þitt? 784 00:35:23,330 --> 00:35:23,820 >> Áhorfendur: Chris. 785 00:35:23,820 --> 00:35:25,620 >> Ræðumaður: Chris, taka skref áfram, þú ert nú flokkað. 786 00:35:25,620 --> 00:35:27,010 Hvað er lykillinn skref núna? 787 00:35:27,010 --> 00:35:27,510 Sameinast. 788 00:35:27,510 --> 00:35:30,509 Svo er að fara að sameinast í stað hér, ef þú gætir tekið skref til baka, 789 00:35:30,509 --> 00:35:32,930 og þrír er að fara að taka skref til baka, sameinast. 790 00:35:32,930 --> 00:35:38,080 Þannig að vinstri helmingi af hægri helminginn, er nú flokkað. 791 00:35:38,080 --> 00:35:41,747 Frankly, þetta reiknirit finnst eins og við eru að sóa hátt meiri tíma en áður, 792 00:35:41,747 --> 00:35:44,830 en ef við gerðum þetta í rauntíma, munum við sjá hvað takeaways að fara að vera. 793 00:35:44,830 --> 00:35:47,970 Nú hér er ég, rétt helmingur af the réttur helmingur, 794 00:35:47,970 --> 00:35:50,170 láta mig fara á undan og raða vinstri helming. 795 00:35:50,170 --> 00:35:51,482 Stíga fram, hvað er nafnið þitt? 796 00:35:51,482 --> 00:35:52,190 Áhorfendur: Ramsey. 797 00:35:52,190 --> 00:35:53,210 Ræðumaður: Ramsey er nú flokkað. 798 00:35:53,210 --> 00:35:53,570 Hvað er nafn þitt? 799 00:35:53,570 --> 00:35:54,200 >> Áhorfendur: Marina. 800 00:35:54,200 --> 00:35:57,033 >> Ræðumaður: Marina er nú raðað sem vel, ef þú tekur eitt skref fram á við. 801 00:35:57,033 --> 00:36:00,690 Mikilvægt skref hér er nú sameinast, ég er að fara að reyta af tveimur listum mínum, 802 00:36:00,690 --> 00:36:01,720 vinstri og hægri. 803 00:36:01,720 --> 00:36:05,150 Fimm er að fara að koma fyrst, og sjö er að fara að koma næst. 804 00:36:05,150 --> 00:36:06,410 Og aftur, þetta er vísvitandi. 805 00:36:06,410 --> 00:36:08,535 Sú staðreynd að þeir eru að taka stígur fram og til baka 806 00:36:08,535 --> 00:36:12,997 er ætlað að tákna að við getum ekki gera þetta reiknirit í stað eins auðveldlega 807 00:36:12,997 --> 00:36:15,830 eins kúla tagi og val tagi, og insertion sort þar sem við bara 808 00:36:15,830 --> 00:36:16,960 haldið swap fólk. 809 00:36:16,960 --> 00:36:19,940 Ég þarf bókstaflega eins konar af grunni pappír sem 810 00:36:19,940 --> 00:36:21,827 að setja þessar fólkinu á meðan ég gera samruna, 811 00:36:21,827 --> 00:36:23,410 og þá get ég sett þá aftur á sinn stað. 812 00:36:23,410 --> 00:36:27,260 Og það er lykillinn af því að ég er að nota Ný úrræði, rúm, ekki bara tími. 813 00:36:27,260 --> 00:36:28,270 >> OK, þetta er ótrúlegt. 814 00:36:28,270 --> 00:36:32,050 Vinstri helmingurinn er raðað, hægri helminginn er raðað, nú er lykillinn sameina skref. 815 00:36:32,050 --> 00:36:33,450 Hvernig er ég að fara að sameina þetta? 816 00:36:33,450 --> 00:36:35,470 Þannig að ef þú munt fylgja mínum vinstri hönd og hægri hönd, 817 00:36:35,470 --> 00:36:38,930 Ég ætla að benda vinstri hendina á mér á vinstri helming, hægri hönd mín 818 00:36:38,930 --> 00:36:42,680 á réttum helming, og nú verð ég að ákveða skref fyrir skref sem á að sameinast í. 819 00:36:42,680 --> 00:36:44,650 Sem augljóslega kemur fyrst? 820 00:36:44,650 --> 00:36:45,150 Númer eitt. 821 00:36:45,150 --> 00:36:47,327 Svo koma á hérna, hér er klóra púði okkar. 822 00:36:47,327 --> 00:36:49,910 Svo nú númer eitt, og tilkynningu hvað ég ætla að gera með hægri hendi minni, 823 00:36:49,910 --> 00:36:54,152 Ég ætla að flytja mitt hægri hönd einn stíga yfir til að benda númer þrjú, 824 00:36:54,152 --> 00:36:55,860 og nú þarf ég að gera sama ákvörðun. 825 00:36:55,860 --> 00:36:58,387 Og í raun standa rétt í framan Luke hér ef þú gætir, 826 00:36:58,387 --> 00:36:59,720 vegna þess að þetta er klóra púði okkar. 827 00:36:59,720 --> 00:37:00,610 Svo sem kemur næst? 828 00:37:00,610 --> 00:37:05,000 Við höfum Lúkas með númer tvö eða Chris með númer þrjú. 829 00:37:05,000 --> 00:37:07,460 Vitanlega Lúkas, fjöldi tveir, svo þú kemur hingað. 830 00:37:07,460 --> 00:37:11,270 >> En vinstri hönd mín nú er að fara að vera hækkuð að benda á Darren, 831 00:37:11,270 --> 00:37:15,160 og hér er lykillinn að taka í burtu með samruna, ég ætla að halda þessu, 832 00:37:15,160 --> 00:37:17,340 Vitanlega, ef þú góður af fylgja rökfræði. 833 00:37:17,340 --> 00:37:19,670 En hendur mínar eru aldrei að fara aftur á bak, 834 00:37:19,670 --> 00:37:23,861 sem þýðir að ég er bara alltaf að flytja til vinstri samrunafélaganna ferli mínum, 835 00:37:23,861 --> 00:37:26,360 og það er að fara að vera lykill að Greining okkar á aðeins augnablik. 836 00:37:26,360 --> 00:37:27,859 >> Svo nú skulum klára þetta upp hratt. 837 00:37:27,859 --> 00:37:31,650 Svo þremur kemur næst, þá fjögur kemur næst, 838 00:37:31,650 --> 00:37:38,750 og nú fimm kemur næst, þá sex, og sjö, og þá loks átta. 839 00:37:38,750 --> 00:37:42,960 Líður eins og hægur reiknirit enn, en ekki ef við raunverulega 840 00:37:42,960 --> 00:37:45,510 keyra það á sama tagi af klukku hraða, svo að 841 00:37:45,510 --> 00:37:48,106 tala, með sömu tifar klukka sem áður. 842 00:37:48,106 --> 00:37:48,605 Hvers vegna? 843 00:37:48,605 --> 00:37:51,100 Jæja, við skulum taka a líta á the endir afleiðing. 844 00:37:51,100 --> 00:37:56,990 >> Við skulum fara aftur hérna, láttu mig draga upp sýning sjónrænt 845 00:37:56,990 --> 00:37:59,030 af því sem við gerðum bara. 846 00:37:59,030 --> 00:38:06,110 Zooming í hér, á þessu síðu hér, segja Firefox 847 00:38:06,110 --> 00:38:08,200 að við viljum að biðröð upp í þessum kassa, skulum 848 00:38:08,200 --> 00:38:11,260 segja kúla konar, sem við erum nú vel kunnugur, 849 00:38:11,260 --> 00:38:14,130 Val tegund, sem er annar nokkuð augljóst einn, 850 00:38:14,130 --> 00:38:18,250 og nú Mergesort dag, sem verður climactic endir okkar. 851 00:38:18,250 --> 00:38:21,530 Ástæðan það tók svo mikið lengur hér með mönnum og mér er munnlega, 852 00:38:21,530 --> 00:38:23,480 augljóslega, ég er að útskýra hvert skref. 853 00:38:23,480 --> 00:38:26,920 En ef þú framkvæma einfaldlega þetta, mikið eins og við gerðum kúla raða og val 854 00:38:26,920 --> 00:38:30,890 raða ekki aðeins sjónrænt, horfa hversu miklu skilvirkari 855 00:38:30,890 --> 00:38:33,330 þetta skuldsetning deild og sigra 856 00:38:33,330 --> 00:38:39,150 má þegar beitt til a gögnum sem er ekki einu sinni stærð átta, en jafnvel miklu, 857 00:38:39,150 --> 00:38:39,970 miklu stærri. 858 00:38:39,970 --> 00:38:44,585 Ég gef þér sameinast raða, hlið við hlið með þessum reiknirit. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Þetta er að fara að fá sársaukafull fljótt, og endirinn 861 00:38:58,530 --> 00:39:00,890 er ekki sérstaklega climactic, þeir enda bara upp raðað. 862 00:39:00,890 --> 00:39:05,280 En lykillinn að taka burt er að líta hversu mikið hraðar sameinast raða 863 00:39:05,280 --> 00:39:08,110 var, nema þú heldur að ég bara svona að fíflast með þér. 864 00:39:08,110 --> 00:39:13,100 Ef við gerum þetta einn endanlega tíma, skulum endurhlaða þetta, við skulum fara aftur 865 00:39:13,100 --> 00:39:14,960 og velja kúla konar, og bara ánægja, 866 00:39:14,960 --> 00:39:17,330 skulum velja innsetningu raða, bara gott mál. 867 00:39:17,330 --> 00:39:20,020 Og í þetta sinn aftur, við skulum velja Mergesort og skulum 868 00:39:20,020 --> 00:39:21,595 í raun að keyra þessar hlið við hlið. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> Og það er ekki í raun einstakur. 871 00:39:26,930 --> 00:39:31,140 Það sem ég hef í raun gert er að ég hef skipt inntak mína í tvennt aftur, 872 00:39:31,140 --> 00:39:32,240 og aftur, og aftur. 873 00:39:32,240 --> 00:39:35,590 Og það er aðeins svo oft sem þú getur skipta inntak inn í helminga, vinstri 874 00:39:35,590 --> 00:39:36,240 og rétt. 875 00:39:36,240 --> 00:39:39,425 Hvað er uppskrift að við höldum að sjá sem lýsir skiptingu í tvennt 876 00:39:39,425 --> 00:39:41,050 aftur, og aftur, og aftur, og aftur? 877 00:39:41,050 --> 00:39:41,890 >> Áhorfendur: Log n. 878 00:39:41,890 --> 00:39:42,760 >> Ræðumaður: Log n. 879 00:39:42,760 --> 00:39:46,300 En svo er það eitt annað mikilvægt skref, þetta reiknirit er ekki skráð þig inn n skrefum. 880 00:39:46,300 --> 00:39:48,992 Ef það voru aðeins skrá n skref, Við vildi vera í sama vandamáli 881 00:39:48,992 --> 00:39:51,200 eins og áður þar sem við getum ekki verið viss raðað allt er. 882 00:39:51,200 --> 00:39:54,480 Þú þarft að óverulega líta á n þætti til að vera viss n þættir eru flokkuð, 883 00:39:54,480 --> 00:39:55,950 annars er það áræðni. 884 00:39:55,950 --> 00:39:59,810 >> Svo það er óverulega þig n skref, en hvað um þennan takka samrunafélaganna skref 885 00:39:59,810 --> 00:40:04,370 þar sem ég sameinuðust vinstri helmingur minn og hægri helmingur og gekk yfir sviðið? 886 00:40:04,370 --> 00:40:06,980 Hversu mörg skref er að að sameina? 887 00:40:06,980 --> 00:40:10,150 Það er n, en ég gerði ekki bara sameinast endanlega tíma. 888 00:40:10,150 --> 00:40:15,089 Á hverjum þessara hreiður símtöl á hverjum af þeim hreiður sameinast, raðað ég enn. 889 00:40:15,089 --> 00:40:18,380 Ég sameinuðust þessir tveir gaurar, þá eru þessir tveir krakkar, þá eru þessir tveir gaurar og svo framvegis. 890 00:40:18,380 --> 00:40:19,955 >> Svo ég gerði sameina aftur, og aftur. 891 00:40:19,955 --> 00:40:20,580 Hversu oft? 892 00:40:20,580 --> 00:40:23,510 Svo í hvert skipti sem ég skipt á lista í tvennt, ég gerði sameinast. 893 00:40:23,510 --> 00:40:25,460 Skiptið lista í tvennt, gera sameinast. 894 00:40:25,460 --> 00:40:28,570 Þannig að ef skipta á lista er hægt að gera Log N sinnum, 895 00:40:28,570 --> 00:40:33,880 og sameiningu tekur að lokum n skref, hvað gæti verið nú efri 896 00:40:33,880 --> 00:40:37,000 bundinn á gangi tími reiknirit okkar? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> Og reyndar, það er það við höfum náð hér. 899 00:40:40,560 --> 00:40:44,650 Svo finnst sem þú sérð sjónrænt þegar þessir þrír hlutir hlaupa hlið við hlið 900 00:40:44,650 --> 00:40:47,930 er n veldi gegn n kvaðrat gegn n log n. 901 00:40:47,930 --> 00:40:51,010 Sem í grundvallaratriðum við munum sjá, ekki aðeins í dag heldur í framtíðinni, 902 00:40:51,010 --> 00:40:52,760 er miklu, miklu hraðar. 903 00:40:52,760 --> 00:40:56,010 A umferð af lófaklapp fyrir þessar krakkar, Ég mun verðlauna þau með streitu bolta. 904 00:40:56,010 --> 00:41:00,260 Við skulum fresta hér í dag, og Við munum sjá þig á mánudaginn. 905 00:41:00,260 --> 00:41:02,255