1 00:00:00,000 --> 00:00:11,100 >> [Tónlist spila] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. Malan: Allt í lagi. 3 00:00:11,490 --> 00:00:12,170 Svo velkomin aftur. 4 00:00:12,170 --> 00:00:15,180 Þetta er CS50, og er í lok viku þrjú. 5 00:00:15,180 --> 00:00:17,770 >> Svo muna á undanförnum vikum, við höfum verið að eyða töluvert af 6 00:00:17,770 --> 00:00:20,820 tími á C, á forritun, á setningafræði. 7 00:00:20,820 --> 00:00:24,680 Og það er alveg eðlilegt, ef þú ert enn erfiðleikum með Set Vandamál 2, að vera 8 00:00:24,680 --> 00:00:25,950 lemja höfðinu við vegg. 9 00:00:25,950 --> 00:00:28,310 Það er dulinn-útlit villa skilaboð og galla sem þú 10 00:00:28,310 --> 00:00:29,220 getur ekki alveg elta niður. 11 00:00:29,220 --> 00:00:32,310 Vegna þess, treyst, að í bara tími nokkurra vikna þú munt líta til baka á 12 00:00:32,310 --> 00:00:35,930 hlutir eins keisaranum og [? V-genair,?] kannski jafnvel sprunga, og 13 00:00:35,930 --> 00:00:40,050 grein fyrir hversu langt þú hefur komið á stuttum tíma. 14 00:00:40,050 --> 00:00:43,670 Þannig að ef það er einhver huggun, hanga í there fyrir nú. 15 00:00:43,670 --> 00:00:46,610 >> Í dag, þó, byrjum við að umskipti að hlutum hærra stig. 16 00:00:46,610 --> 00:00:49,820 Og við byrjum að taka sem sjálfsögðum hlut að þú krakkar vita hvernig á að forrita, eða á 17 00:00:49,820 --> 00:00:52,090 amk upphaf að þægindi stigi. 18 00:00:52,090 --> 00:00:56,520 Og við munum byrja að huga að því hvernig við getum fara um hanna forrit meira 19 00:00:56,520 --> 00:00:57,440 á áhrifaríkan hátt. 20 00:00:57,440 --> 00:01:01,090 Hvernig getum við farið um hagræðingu í skilvirkni reiknirit okkar, og 21 00:01:01,090 --> 00:01:03,110 almennt leysa meira áhugaverðar vandamál. 22 00:01:03,110 --> 00:01:06,850 Og byrja að taka sem sjálfsögðum hlut að, ef við vildum, gætum við kóðann upp allir 23 00:01:06,850 --> 00:01:08,350 af dæmunum sem við höfum í huga. 24 00:01:08,350 --> 00:01:11,430 Svo í dag, höfum við snerta lyklaborðið fyrir hvers konar kóða. 25 00:01:11,430 --> 00:01:15,150 Það verður miklu meiri, og lokum, um að leysa vandamál. 26 00:01:15,150 --> 00:01:20,490 >> Svo til að fá að þessu, láttu mig leggja að eftirfarandi sjö 27 00:01:20,490 --> 00:01:24,290 ferhyrninga tákna sjö hurðir, bak sem ert a heild búnt af 28 00:01:24,290 --> 00:01:26,340 tölur, þar á meðal er fjöldi 50. 29 00:01:26,340 --> 00:01:30,470 Leyfðu mér að verkefni þetta á þetta skjár hér eins vel. 30 00:01:30,470 --> 00:01:36,770 Og leggja til að við þurfum sjálfboðaliða til að að finna mér númerið fyrir framan 31 00:01:36,770 --> 00:01:38,140 Netið hér til að sjá. 32 00:01:38,140 --> 00:01:40,755 Komdu upp í bleiku. 33 00:01:40,755 --> 00:01:43,050 Allt í lagi. 34 00:01:43,050 --> 00:01:43,930 Hvað er nafn þitt? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [inaudible] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. Malan: Fyrirgefðu? 37 00:01:45,170 --> 00:01:45,860 >> JENNIFER: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> DAVID J. Malan: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Allt í lagi, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Gaman að hitta þig. 41 00:01:47,630 --> 00:01:48,370 Komdu upp. 42 00:01:48,370 --> 00:01:52,430 Svo þetta eru hér sjö hurðir, og hvað Mig langar að gera fyrir okkur hér, 43 00:01:52,430 --> 00:01:56,560 framan alla bekkjarfélaga þína, er að finna okkur á númerið 50. 44 00:01:56,560 --> 00:02:00,860 Að finna fjölda, getur þú gægjast á bak eitthvað af þessum hurðum með því einfaldlega að slá 45 00:02:00,860 --> 00:02:03,030 á einn af the dyr, og það mun sýna númer þess. 46 00:02:03,030 --> 00:02:06,080 Og við skulum sjá hversu fljótt þú getur fundið okkur númerið, 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Fallega gert. 54 00:02:17,350 --> 00:02:18,040 Allt í lagi. 55 00:02:18,040 --> 00:02:19,906 Umferð lófaklapp fyrir Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Applause] 57 00:02:21,530 --> 00:02:22,320 >> Allt í lagi. 58 00:02:22,320 --> 00:02:25,254 Svo það var tækni til finna fjölda, 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Um, ég hélt kannski ef - 60 00:02:27,222 --> 00:02:27,714 [Inaudible] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. Malan: Oh. 62 00:02:28,206 --> 00:02:29,630 Gefa það eina sekúndu. 63 00:02:29,630 --> 00:02:32,420 Svo var tækni til finna fjölda, 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Svo ég byrja bara á því farin að sjá hvað fyrsta talan 65 00:02:34,760 --> 00:02:38,590 var, og þá hugsaði ég, kannski ef þeir raðað, ég bara halda 66 00:02:38,590 --> 00:02:39,970 slá ofar? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. Malan: OK. 68 00:02:40,140 --> 00:02:42,910 Og við virðumst hafa fundið að vera raunin. 69 00:02:42,910 --> 00:02:45,670 Þó, við skulum afhýða aftur lögin bara svolítið, og þú vilt fara 70 00:02:45,670 --> 00:02:47,640 undan og sýna öðrum hurðir þú gætir hafa valið? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Ó, elskan. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. Malan: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Svo ég fékk bara heppinn. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. Malan: Svo þú got heppinn. 76 00:02:55,270 --> 00:02:55,710 Allt í lagi. 77 00:02:55,710 --> 00:02:56,795 Svo ekki slæmt. 78 00:02:56,795 --> 00:02:58,750 En það er áhugavert innsýn, ekki satt? 79 00:02:58,750 --> 00:03:01,870 Ef þú ráð fyrir, og þú gerðir fá, reyndar svolítið heppinn þar. 80 00:03:01,870 --> 00:03:05,350 En ef þú ráð fyrir að tölurnar væru raðað, getur þú verið nákvæmari 81 00:03:05,350 --> 00:03:08,750 um hvernig þessi áhrif hegðun þína? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Svo ef þeir voru raðað, ég hélt kannski minnstu til stærstu. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. Malan: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: Eða ef þetta endaði að vera mjög stór, þá stærsta í minnsta. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. Malan: OK. 86 00:03:15,540 --> 00:03:18,170 Svo stærsta til minnsta, eða minnstu að stærsta. 87 00:03:18,170 --> 00:03:21,990 En láttu mig leggja, ráð þú hefðir fengið óheppinn, og gera ráð fyrir að þeir 88 00:03:21,990 --> 00:03:26,840 voru ekki í raun, raðað, hversu margir af þær hurðir gætir þú þurft að gægjast 89 00:03:26,840 --> 00:03:28,590 bak í því versta tilfelli? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Öll þau. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. Malan: Öll þau. 92 00:03:30,420 --> 00:03:31,740 Svo skulum alhæfa að sem n. 93 00:03:31,740 --> 00:03:34,790 Það gerist til að vera 7, en við skulum meira almennt segja að það er n hurðir á 94 00:03:34,790 --> 00:03:35,650 skjár hér. 95 00:03:35,650 --> 00:03:40,110 Svo í versta tilfelli, myndir þú hafa að líta á bak 7 dyr, eða N dyr. 96 00:03:40,110 --> 00:03:44,140 Og svo er þetta virkilega, það er hluti af heppni í dag, en það er mjög línulegt 97 00:03:44,140 --> 00:03:46,440 reiknirit konar, jafnvel þótt þú voru konar skipstjóri í kring. 98 00:03:46,440 --> 00:03:47,080 Er það sanngjarnt? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Já. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. Malan: Jæja, láttu mig sjá ef þinn stefnu breytingar ef ég færa okkur til 101 00:03:50,000 --> 00:03:52,190 Annað dæmi okkar hér með 7 mismunandi hurðir. 102 00:03:52,190 --> 00:03:55,240 Sömu tölur, en þetta tíma þeir eru flokkuð. 103 00:03:55,240 --> 00:03:58,350 Hvað er tækni hér að fara að vera, reyna að setja út af huga þínum hvað 104 00:03:58,350 --> 00:03:59,310 aðrar tölur voru - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. Malan: - fyrr? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Byrjum með the fyrstur einn. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. Malan: Allt í lagi. 109 00:04:03,540 --> 00:04:05,190 Byrja með fyrsta. 110 00:04:05,190 --> 00:04:05,960 4.. 111 00:04:05,960 --> 00:04:08,810 Nú þar sem þú að fara að fara, og hvers vegna? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 er í raun lítil. 113 00:04:10,040 --> 00:04:12,500 Svo ef þeir eru svona kannski minnstu til stærsta, ætti það 114 00:04:12,500 --> 00:04:13,290 vera tvisvar sinnum að, og -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. Malan: OK. 116 00:04:13,670 --> 00:04:15,990 Við skulum sjá, sem þér finnst? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Prófaðu það síðasta. 118 00:04:19,050 --> 00:04:19,500 Nice. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. Malan: Mjög fallega gert. 120 00:04:20,880 --> 00:04:21,860 Allt í lagi. 121 00:04:21,860 --> 00:04:23,010 >> [Applause] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. Malan: OK. 123 00:04:24,310 --> 00:04:26,790 Svo þú ert í raun að gera þetta hryllilegur, vegna þess að þú ert 124 00:04:26,790 --> 00:04:27,700 gera það mjög vel. 125 00:04:27,700 --> 00:04:31,150 Sem skilur okkur ekki gera ákveðnar stig. 126 00:04:31,150 --> 00:04:32,565 Þannig að við skulum reyna að rúlla aftur hingað. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. Malan: Mjög vel gert, engu að síður. 129 00:04:35,980 --> 00:04:39,060 Svo þú byrjað frá upphafi, þú sást að það var 4, þá 130 00:04:39,060 --> 00:04:40,240 flutti til enda. 131 00:04:40,240 --> 00:04:42,320 En geri ráð fyrir að þú did ekki fá heppinn þar, og geri ráð fyrir 50 132 00:04:42,320 --> 00:04:42,890 var eitthvað annað. 133 00:04:42,890 --> 00:04:46,190 Hvað þriðja skrefið hafa verið? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Fara til baka í upphafi. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. Malan: Til baka á byrjun. 136 00:04:48,320 --> 00:04:51,320 OK, svo þú hefði snert þetta dyr, sem var 8. 137 00:04:51,320 --> 00:04:51,660 Allt í lagi. 138 00:04:51,660 --> 00:04:52,650 Svo er það ekki 50. 139 00:04:52,650 --> 00:04:55,380 Hvar vilt þú hafa rannsakað næst? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Ef ég gerði ekki vita þeir raðað. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. Malan: Rétt. 142 00:04:57,005 --> 00:04:58,490 Jæja, ef þú did vita þeir voru flokkaður - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Oh, gerði vita, já. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. Malan: - en þú gerðir ekki vita hvar 50 var enn? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Bara halda áfram. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. Malan: Allt í lagi. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Halda áfram. 149 00:05:03,800 --> 00:05:05,270 OK, ég get unnið með. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. Malan: Nú, ef þú ert bara að fara að halda áfram, hvað er þitt 152 00:05:07,210 --> 00:05:09,680 reiknirit devolving backed inn. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: The línuleg -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. Malan: Það er góður af línuleg. 155 00:05:11,820 --> 00:05:13,480 En láttu mig leggja, láta mér að setja á staðnum. 156 00:05:13,480 --> 00:05:14,900 Leyfðu mér að uppfæra síðuna. 157 00:05:14,900 --> 00:05:17,120 sama númer, sama fyrirkomulag, sömu dyr. 158 00:05:17,120 --> 00:05:21,350 En að hugsa til baka til að fyrsta degi í flokki þegar við reif símaskrá í 159 00:05:21,350 --> 00:05:25,480 helmingur, eiginlega, og hvað var stefnu okkar þar? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Byrja á miðju. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. Malan: OK. 162 00:05:26,690 --> 00:05:27,610 Svo byrja á miðju. 163 00:05:27,610 --> 00:05:28,790 Svo skulum við fara á undan og gera sér það. 164 00:05:28,790 --> 00:05:30,720 Byrja á miðju eftir sýna að dyrunum. 165 00:05:30,720 --> 00:05:31,660 Svo talan 16. 166 00:05:31,660 --> 00:05:35,290 Svo hvað myndi sterka strákur hefur gert, sem reif símaskrána í tvennt, 167 00:05:35,290 --> 00:05:38,450 að fá til the næstur giska? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Go þennan hálfleik. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. Malan: Og hvers vegna til hægri? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Ef þeir voru svona minnstu til stærsta, þá 50 að vera 171 00:05:43,900 --> 00:05:44,720 í því skyni. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. Malan: Gott. 173 00:05:44,920 --> 00:05:45,390 Algerlega sanngjarnt. 174 00:05:45,390 --> 00:05:48,380 Svo eins og símaskrá, þú ferð til rétt eins og öfugt við vinstri, en hér 175 00:05:48,380 --> 00:05:49,500 er lykillinn takeaway. 176 00:05:49,500 --> 00:05:53,930 Þú nú geta henda, eða rífa burt, helmingur af this vandamál, þannig að þú ekki 177 00:05:53,930 --> 00:05:55,970 með 7 hurðum, en í raun með bara 3. 178 00:05:55,970 --> 00:05:57,870 Sem er u.þ.b. helmingur af stærð vandans. 179 00:05:57,870 --> 00:05:58,350 Allt í lagi. 180 00:05:58,350 --> 00:06:01,890 Svo nú hvað þú þyrftir gert eftir að þú ferð ekki satt? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Svo 16 er enn nokkuð lítill, miðað við 50, svo kannski ég ætla að reyna, 182 00:06:05,870 --> 00:06:06,700 eins, og þessi. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. Malan: Allt í lagi. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Allt í lagi, svo nú er það þín eðlishvöt segja þér? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Ég get henda þetta og þá bara - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. Malan: OK. 188 00:06:12,360 --> 00:06:14,212 Góður, getur þú henda vinstri helmingur þar. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - velja þetta einn. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. Malan: Og rétt. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Já. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. Malan: Svo jafnvel þó að það er erfitt að sjá kannski þegar það er aðeins 193 00:06:17,820 --> 00:06:21,320 7 hurðir, hugsa um, nú, The samræmi við 194 00:06:21,320 --> 00:06:22,620 Reiknirit þú sótt bara. 195 00:06:22,620 --> 00:06:24,510 Í fyrra tilvikinu, en þér heppinn, sem var frábært. 196 00:06:24,510 --> 00:06:26,540 En þú gerðir nota leitandi, Ég myndi segja. 197 00:06:26,540 --> 00:06:29,150 Þú notaðir konar eðlishvöt þína og vitandi það flokkað, ef það er nokkuð 198 00:06:29,150 --> 00:06:31,600 lítil í upphafi, augljóslega, við höfum fékk að fara meira til hægri. 199 00:06:31,600 --> 00:06:34,990 En í einhverjum skilningi, þú got heppinn, því kannski var þetta númer 100, 200 00:06:34,990 --> 00:06:36,220 og kannski 50 var meira í miðjunni. 201 00:06:36,220 --> 00:06:37,910 Kannski 50 var jafnvel hérna. 202 00:06:37,910 --> 00:06:40,960 >> En hvað þú gerðir svolítið öðruvísi í þetta sinn var, gerði þér það sama 203 00:06:40,960 --> 00:06:42,150 aftur og aftur. 204 00:06:42,150 --> 00:06:45,310 Og ég myndi halda því fram að það sem þú bara gerði, að vísu undir áhrifum frá símanum 205 00:06:45,310 --> 00:06:48,100 bók dæmi, er eitthvað mikið meira lausnarleiðar, og margt 206 00:06:48,100 --> 00:06:49,930 minna sérstakt cased. 207 00:06:49,930 --> 00:06:51,620 Miklu minna instinctive. 208 00:06:51,620 --> 00:06:57,160 Svo í lok dagsins, hvernig væri þú lýsa skilvirkni í 209 00:06:57,160 --> 00:07:00,530 Fyrsta reiknirit, þar sem þú fórst vinstri til hægri, á móti 210 00:07:00,530 --> 00:07:03,430 annað reiknirit hér? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: Þessi ætti eins, kannski helminga tímann, eða jafnvel meira, já. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. Malan: OK, kannski jafnvel meira. 213 00:07:07,320 --> 00:07:10,150 Skulum ýta svolítið erfiðara á það. 214 00:07:10,150 --> 00:07:13,030 Hvað raunverulega, ef við höldum áfram þessu rökfræði, helming við ákveðið 215 00:07:13,030 --> 00:07:15,830 hlaupandi tíma með þessum seinni reiknirit með því að henda burt helmingi 216 00:07:15,830 --> 00:07:18,470 tölur, en hvað gerði við gera á næsta endurtekning, þegar Jennifer ljós 217 00:07:18,470 --> 00:07:20,615 seinni númer? 218 00:07:20,615 --> 00:07:22,830 >> Við helming tölur dyr aftur. 219 00:07:22,830 --> 00:07:25,270 Og þá hvað gerði við gera eftir það, ef voru fleiri dyr til að spila með? 220 00:07:25,270 --> 00:07:27,520 Við myndum helminga þá, og aftur, og aftur og aftur. 221 00:07:27,520 --> 00:07:30,420 Og þetta var bara eins og ykkur öll standa upp í fyrstu viku 222 00:07:30,420 --> 00:07:33,000 flokki, helmingur þú situr niður, helmingur af þú setjast niður, helmingur af þér 223 00:07:33,000 --> 00:07:35,440 sitja niður, þar til einn einn sál stóð. 224 00:07:35,440 --> 00:07:39,050 Og við sögðum að keyra tími þessi, the tala af skrefum sem það tók var 225 00:07:39,050 --> 00:07:40,430 á röð hvað? 226 00:07:40,430 --> 00:07:41,230 >> Ræðumaður 1: [inaudible] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. Malan: Svo þig stöð 2 af n, eða bara fleiri einfaldlega, skráðu þig á n. 228 00:07:43,970 --> 00:07:45,060 Svo eitthvað lógaritmískum. 229 00:07:45,060 --> 00:07:48,380 Og línurit var ekki bein lína sem bara verri og verri, það var 230 00:07:48,380 --> 00:07:52,490 þetta áhugavert ferill sem ekki fá svo slæmt tímanum. 231 00:07:52,490 --> 00:07:53,910 Þannig að við skulum halda í þessa hugmynd. 232 00:07:53,910 --> 00:07:54,690 Skulum þakka Jennifer. 233 00:07:54,690 --> 00:07:56,150 Takk svo mikið fyrir að koma upp. 234 00:07:56,150 --> 00:07:57,400 Og, einn sek. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Engar skrifborðið lampar í dag, en við hafa CS50 streitu kúlur. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. Malan: Allt í lagi, hér. 239 00:08:04,410 --> 00:08:06,545 Þakka þér fyrir incurring streitu upp hér. 240 00:08:06,545 --> 00:08:07,350 Allt í lagi. 241 00:08:07,350 --> 00:08:10,620 Svo við skulum sjá hvort við getum ekki núna formlega þetta aðeins meira. 242 00:08:10,620 --> 00:08:14,820 Svo aftur, hvað við gerðum var bara í raun það sama og við gerðum 243 00:08:14,820 --> 00:08:16,660 í fyrstu viku. 244 00:08:16,660 --> 00:08:23,780 En frekar en að enda með bara línuleg reiknirit, sem við lýst 245 00:08:23,780 --> 00:08:27,210 áður þar sem þetta beina línu, þar, ef við setjum eitt dyr á 246 00:08:27,210 --> 00:08:29,610 á skjánum, þá Jennifer myndi hafa þurft að leita, hugsanlega, 247 00:08:29,610 --> 00:08:30,600 bak eitt dyr. 248 00:08:30,600 --> 00:08:33,490 Ef við setjum tvær hurðir, gæti hún hafa að líta á bak tveimur hurðum. 249 00:08:33,490 --> 00:08:35,990 >> Og svo var þetta línuleg tengsl milli stærð af því 250 00:08:35,990 --> 00:08:39,059 vandamál á, segja, á x-ás og þann tíma sem það tekur að 251 00:08:39,059 --> 00:08:40,440 leysa á y. 252 00:08:40,440 --> 00:08:43,330 En myndin sem ég var að alluding fyrr var þetta græna línan. 253 00:08:43,330 --> 00:08:45,970 Grænt vísvitandi, því það var bara betra. 254 00:08:45,970 --> 00:08:49,790 Í orði, reiknirit, þegar við gerðum það með símaskránni, þegar við gerðum það 255 00:08:49,790 --> 00:08:52,420 með þið telja hvert annað, og í öðru lagi, þegar Jennifer bara 256 00:08:52,420 --> 00:08:55,250 gerði það upp hér, það var svona af grundvallaratriðum betur. 257 00:08:55,250 --> 00:08:57,180 Vegna þess að það var ekki bara tvisvar eins hratt. 258 00:08:57,180 --> 00:08:58,870 Það var ekki einu sinni fjórum sinnum eins hratt. 259 00:08:58,870 --> 00:09:03,290 Það var algjörlega háð því hvað stærð inntak var um hversu mörg 260 00:09:03,290 --> 00:09:05,220 skref sem það tók að lokum. 261 00:09:05,220 --> 00:09:08,040 >> Og svo þetta einfalda hugmynd að við tókum öll fyrir veitt með símaskránni, 262 00:09:08,040 --> 00:09:10,200 getur sömuleiðis að beita að eitthvað eins og this. 263 00:09:10,200 --> 00:09:12,380 Og þetta gæti verið frjálslegur þekktur sem, eins og þú might 264 00:09:12,380 --> 00:09:13,940 ímynda sér, deila og sigra. 265 00:09:13,940 --> 00:09:16,390 Ekki ólíkt því sem við gerðum, að sjálfsögðu, með símaskránni. 266 00:09:16,390 --> 00:09:18,300 >> En sauðakóðanum, muna, var þetta. 267 00:09:18,300 --> 00:09:21,800 Þannig að við munum ekki gera þetta aftur, en muna að fyrstu vikuna, allir af okkur stóð upp 268 00:09:21,800 --> 00:09:25,140 og þá helmingur þú settist niður, helmingur þú settist niður, helmingur þú settist niður. 269 00:09:25,140 --> 00:09:29,280 Að reiknirit var framkvæmd í hluti af a svindla hátt, í því, það 270 00:09:29,280 --> 00:09:32,870 var bara ein af mér ekki að telja, grundvallaratriðum, skilvirkari. 271 00:09:32,870 --> 00:09:35,830 Í því tilviki var ég að fá meira annar auðlind. 272 00:09:35,830 --> 00:09:39,470 Konar, margfeldi örgjörva, margar gáfur, margfeldi sviði fólk í 273 00:09:39,470 --> 00:09:42,740 herbergi voru að hjálpa mér að fá frá einhverju línuleg eitthvað 274 00:09:42,740 --> 00:09:45,190 lógaritmískum, frá einhverju rauður að eitthvað grænt. 275 00:09:45,190 --> 00:09:48,650 >> En í þessu tilfelli, Jennifer einn getur grundvallaratriðum bæta við að 276 00:09:48,650 --> 00:09:52,370 Afkoma fyrsta reiknirit hennar með, aftur, bara að hugsa svolítið erfiðara. 277 00:09:52,370 --> 00:09:56,650 Og nú, þegar það kemur tími til að framkvæma þetta, vangaveltur út 278 00:09:56,650 --> 00:10:00,670 hvaða línur af kóða sem þú getur skrifað svo sem þú getur endurtaka þá aftur, og 279 00:10:00,670 --> 00:10:03,350 aftur, og aftur, svona í lykkja tísku. 280 00:10:03,350 --> 00:10:06,370 Þar sem þú ert ekki að fara að hafa lúxus, eins Jennifer gerði í fyrstu, að 281 00:10:06,370 --> 00:10:10,460 bara hafa a heild búnt af IFS og segja, Hmm, ef þetta fyrsta númerið er 4, 282 00:10:10,460 --> 00:10:11,800 láta mig hoppa alla leið til enda. 283 00:10:11,800 --> 00:10:14,180 Ooh, ef þessi tala er of stór, láta mig fara geðþótta aftur 284 00:10:14,180 --> 00:10:15,220 til seinni frumefni. 285 00:10:15,220 --> 00:10:18,210 Þú munt komast að því að það er að fara til vera a einhver fjöldi erfiðara að móta það sem við mennirnir 286 00:10:18,210 --> 00:10:21,270 taka sem sjálfsögðum hlut sem mjög sanngjarnt leitandi, en tölvan er aðeins 287 00:10:21,270 --> 00:10:23,260 að fara að gera það sem þú segir það að gera. 288 00:10:23,260 --> 00:10:25,280 >> Nú hefur þetta mjög áhugavert afleiðingar. 289 00:10:25,280 --> 00:10:29,950 Þetta línurit er tegund af ætlað að raða á gagntaka sjónrænt, en tilkynning þar 290 00:10:29,950 --> 00:10:32,230 er bein lína í þessu grafi? 291 00:10:32,230 --> 00:10:35,330 Hvar er línuleg línurit sem við köllum n? 292 00:10:35,330 --> 00:10:37,580 Jæja, það er tegund af í átt að botn þessa mynd, ekki satt? 293 00:10:37,580 --> 00:10:40,500 Svo allt sem við höfum gert er að við höfum konar aðdregna út til x-ásnum og 294 00:10:40,500 --> 00:10:44,780 Y-ásinn til að reyna að fá tilfinningu fyrir því hvað aðrar gerðir af bugða líta út. 295 00:10:44,780 --> 00:10:47,760 >> Og the sérstakur af the stærðfræði tjáning í dag mun ekki máli svo 296 00:10:47,760 --> 00:10:52,440 mikið, en eftir þessi there er a einhver fjöldi af reiknirit sem eru miklu verra en 297 00:10:52,440 --> 00:10:53,470 eitthvað sem er línuleg. 298 00:10:53,470 --> 00:10:55,410 Reyndar n cubed lítur ansi slæmt. 299 00:10:55,410 --> 00:10:58,400 2 til n lítur ansi slæmt. n ferningur lítur ansi slæmt. 300 00:10:58,400 --> 00:11:01,630 Og við munum sjá hvað sumir af þeim gæti verið í raun í dag. 301 00:11:01,630 --> 00:11:05,430 Og log n ekki finnst eins slæmt, en betri en n er Log stöð 2 á n. 302 00:11:05,430 --> 00:11:08,080 En þú veist, það hefði verið enn meira ótrúlegt ef Jennifer, eða ef við, 303 00:11:08,080 --> 00:11:12,910 að fyrstu vikuna, hafði komið upp með eitthvað sem er log log n. 304 00:11:12,910 --> 00:11:15,880 >> Svo í öðrum orðum, það er þetta allt svið mögulegar lausnir á 305 00:11:15,880 --> 00:11:18,570 vandamál, en jafnvel hér, tilkynning hvað er að fara að gerast. 306 00:11:18,570 --> 00:11:22,910 Þegar ég súmma út, hver af þessum línur er að fara að sanna til vera the alger 307 00:11:22,910 --> 00:11:26,630 verstu sjálfur á skjánum núna? 308 00:11:26,630 --> 00:11:28,680 Svo lítur n cubed laglegur slæmt í augnablikinu. 309 00:11:28,680 --> 00:11:32,470 En ef við zoom út og sjá meira af x og y-ás, sem er að fara að 310 00:11:32,470 --> 00:11:34,550 ráða að lokum? 311 00:11:34,550 --> 00:11:37,120 Svo kemur reyndar í ljós að 2 til n, og þú getur fundið þetta út með því að 312 00:11:37,120 --> 00:11:39,990 tengja í sumum sífellt stór tölur, og þú munt sjá að 2 við 313 00:11:39,990 --> 00:11:42,070 n, reyndar fær stærri miklu hraðar. 314 00:11:42,070 --> 00:11:45,530 Ef við zoom raunverulega út, a 2 til n reiknirit sjúga algerlega. 315 00:11:45,530 --> 00:11:48,170 Ég meina þetta er að fara að taka alveg smá tíma fyrir 316 00:11:48,170 --> 00:11:49,460 tölva til strokkur í gegnum. 317 00:11:49,460 --> 00:11:52,500 >> En þú munt sjá með tímanum, sérstaklega með framtíð setur vandamál og jafnvel 318 00:11:52,500 --> 00:11:55,600 lokaverkefni, er gögn þín setja fær stór, allt í lagi? 319 00:11:55,600 --> 00:11:58,300 Jafnvel í fyrsta útgáfa af Facebook, sem fjöldi vina, og 320 00:11:58,300 --> 00:12:01,840 fjöldi skráðra notenda fékk stór, þú getur flokkað af símanum í samband og 321 00:12:01,840 --> 00:12:05,530 framkvæma eitthvað með línulegum leit, eða mjög einfalt flokkun 322 00:12:05,530 --> 00:12:07,030 reiknirit, eins og við munum sjá í dag. 323 00:12:07,030 --> 00:12:09,280 Þú þarft að byrja að hugsa erfiðara og erfiðara um þessi vandamál. 324 00:12:09,280 --> 00:12:12,070 Og tegundir af vandamál stöðum eins Facebook og Google og Microsoft, 325 00:12:12,070 --> 00:12:16,350 og aðrir vinna á er einmitt þetta konar stór gögn konar spurningum 326 00:12:16,350 --> 00:12:18,530 æ þessa dagana. 327 00:12:18,530 --> 00:12:18,900 >> Allt í lagi. 328 00:12:18,900 --> 00:12:23,800 Svo velgengni jennifer í þeirri síðari reiknirit, hreinskilnislega, gerði hún ótrúlega 329 00:12:23,800 --> 00:12:26,110 vel í fyrsta skipti, en við skulum skrifa það sem heppni svo að við 330 00:12:26,110 --> 00:12:27,000 getur gert þetta atriði. 331 00:12:27,000 --> 00:12:30,970 Í seinna tilvikinu, skuldsett hún er reiknirit sem endurtekið aftur og 332 00:12:30,970 --> 00:12:34,670 aftur, en hún tók sem sjálfsögðum hlut að víst forsendu að við leyft 333 00:12:34,670 --> 00:12:39,370 henni, en hún hagnýtt nokkru nánar annað sinn sem hún hafði ekki 334 00:12:39,370 --> 00:12:39,840 fyrsta skipti. 335 00:12:39,840 --> 00:12:41,800 Sem var hvað? 336 00:12:41,800 --> 00:12:43,050 >> Að listinn var flokkað. 337 00:12:43,050 --> 00:12:46,350 Svo um leið og listinn var raðað, við halda því fram að Jennifer hafi tekist að gera 338 00:12:46,350 --> 00:12:47,480 grundvallaratriðum betur. 339 00:12:47,480 --> 00:12:51,450 7 hurðir, já, er þetta ekki áhugavert, en geri ráð fyrir það sem við erum 7 milljónir hurðir. 340 00:12:51,450 --> 00:12:54,080 Log n er ákveðið að fara að framkvæma margt, margt 341 00:12:54,080 --> 00:12:55,610 hraðar í the langur hlaupa. 342 00:12:55,610 --> 00:12:58,880 En hún þurfti að hafa hurðir raðað fyrir hana. 343 00:12:58,880 --> 00:13:02,320 Nú, ég tók frelsi til að gera það fyrirfram á tölvuskjá 344 00:13:02,320 --> 00:13:05,160 hér, en ætla að Jennifer þurfti að gera það sjálf? 345 00:13:05,160 --> 00:13:10,120 Segjum að hurðir að ræða fulltrúa gögn í gagnagrunni, eða 346 00:13:10,120 --> 00:13:14,260 vinir skráðir á Facebook eða allir vefsíður á internetinu sem 347 00:13:14,260 --> 00:13:16,880 ýmsar vefsíður gætu þurft til vísitölu eða leita á. 348 00:13:16,880 --> 00:13:20,940 >> Segjum sem svo að þú hefðir bara hrár gögn setja og það var eftir að þér, eða að 349 00:13:20,940 --> 00:13:23,010 Jennifer að gera þessi flokkun? 350 00:13:23,010 --> 00:13:26,950 Það, frekar krefst að við svara spurningin vel, hvernig mikill tími 351 00:13:26,950 --> 00:13:31,080 hefði tekið Jennifer, eða jafnvel mig, að raða þær tölur fyrirfram svo 352 00:13:31,080 --> 00:13:32,680 að hún gæti farið sér að? 353 00:13:32,680 --> 00:13:32,880 Ekki satt? 354 00:13:32,880 --> 00:13:36,620 Vegna þess að vísbendingu, að sjálfsögðu, er ef það tekur mig alveg smá stund að raða 355 00:13:36,620 --> 00:13:40,800 tölurnar, sem Heck annt um að þú getur fundið fjölda eins 50 svo hratt, 356 00:13:40,800 --> 00:13:44,850 eins og í tilfelli Jennifer er, ef við meira en óvart hversu mikið af heildar tíma 357 00:13:44,850 --> 00:13:46,920 það tók því að flokka hluti fyrirfram? 358 00:13:46,920 --> 00:13:49,320 >> Svo við skulum sjá hvort við getum ekki mála mynd hér. 359 00:13:49,320 --> 00:13:51,370 Ég hafa a heild búnt meiri streitu kúlur, ef það hjálpar 360 00:13:51,370 --> 00:13:52,270 brjóta ísinn hér. 361 00:13:52,270 --> 00:13:55,690 Og ef þú vilt ekki huga, við þarf sjö sjálfboðaliða - 362 00:13:55,690 --> 00:13:57,060 á, OK. 363 00:13:57,060 --> 00:13:57,240 Vá. 364 00:13:57,240 --> 00:13:59,250 Þannig að við þurfum ekki að eyða á lampa skrifborðið, það virðist. 365 00:13:59,250 --> 00:13:59,690 Allt í lagi. 366 00:13:59,690 --> 00:14:01,530 Svo hvernig um þig tvær framan. 367 00:14:01,530 --> 00:14:04,160 Hvað um þig tveir gaurar í bak. 368 00:14:04,160 --> 00:14:04,870 Svo er það fjórir. 369 00:14:04,870 --> 00:14:09,890 Hvað um þig í framan fimm, sex og sjö. 370 00:14:09,890 --> 00:14:10,320 Þarna. 371 00:14:10,320 --> 00:14:13,260 Vinur þinn er að benda þér út, þannig að þú færð verðlaun. 372 00:14:13,260 --> 00:14:13,700 >> Allt í lagi. 373 00:14:13,700 --> 00:14:14,410 Komdu upp. 374 00:14:14,410 --> 00:14:17,120 Og hvers vegna eigum við ekki að krakkar koma á hérna. 375 00:14:17,120 --> 00:14:18,960 Ég ætla að gefa þér hvert númer. 376 00:14:18,960 --> 00:14:22,150 Og fara á undan og raða ykkur samur hvað er 377 00:14:22,150 --> 00:14:25,180 lýst á skjánum. 378 00:14:25,180 --> 00:14:26,530 >> [INTERPOSING raddir] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. Malan: OOP, því miður. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Allt í lagi. 382 00:14:32,180 --> 00:14:32,750 Jæja, hér við fara. 383 00:14:32,750 --> 00:14:34,180 Númer fimm. 384 00:14:34,180 --> 00:14:35,136 Númer sex. 385 00:14:35,136 --> 00:14:37,770 Einn, tveir, þrír, fjórir, fimm, sex, sjö. 386 00:14:37,770 --> 00:14:39,410 Ó, þetta er óþægilega. 387 00:14:39,410 --> 00:14:41,210 >> Ræðumaður 2: Ég verð bara að fá -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. Malan: Good deal. 389 00:14:41,900 --> 00:14:43,130 Allt í lagi. 390 00:14:43,130 --> 00:14:44,611 Þakka þér fyrir að taka þátt. 391 00:14:44,611 --> 00:14:47,200 >> [Applause] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Allt í lagi. 394 00:14:48,860 --> 00:14:51,970 Þannig að við höfum fjórar, tveir, sex, einn, þrír, sjö, fimm. 395 00:14:51,970 --> 00:14:56,010 Perfect þannig að við höfum sjö sjálfboðaliðar hér sem eru jafnir á breidd til 396 00:14:56,010 --> 00:14:57,430 array sem við erum að spila með fyrr. 397 00:14:57,430 --> 00:14:59,470 Og ég valdi sjö ástæðum sem verður bara 398 00:14:59,470 --> 00:15:00,840 þægilegt í smá. 399 00:15:00,840 --> 00:15:04,400 Og ég ætla að leggja fyrst að við að raða þessum sjö sjálfboðaliða. 400 00:15:04,400 --> 00:15:06,786 Ef þú vilt, fyrst, að segja halló þó. 401 00:15:06,786 --> 00:15:08,970 Þar sem þetta er að fara að vera óþægilega nokkrar mínútur. 402 00:15:08,970 --> 00:15:10,370 Kynntu ykkur. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Hæ, ég er Grace. 404 00:15:10,980 --> 00:15:14,190 Ég er sophomore í Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Hæ. 406 00:15:14,620 --> 00:15:15,620 Ég er Branson. 407 00:15:15,620 --> 00:15:16,920 Ég er að byrja í bræðslu. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> Gabe: Hæ. 410 00:15:20,230 --> 00:15:21,040 Ég er Gabe. 411 00:15:21,040 --> 00:15:22,300 Ég er yngri í Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Ég er Neil. 414 00:15:25,980 --> 00:15:29,090 Ég er að byrja í Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Ég er Jason. 416 00:15:29,550 --> 00:15:32,816 Ég er að byrja í GREENOUGH. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Ég er Mike. 418 00:15:33,700 --> 00:15:37,360 Ég er að byrja í Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Ég er Jess. 420 00:15:37,990 --> 00:15:40,313 Ég er sophomore í Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. Malan: Excellent. 422 00:15:41,300 --> 00:15:41,850 Allt í lagi. 423 00:15:41,850 --> 00:15:44,190 Jæja, þakka þér að öllum okkar sjálfboðaliðar hér svona langt. 424 00:15:44,190 --> 00:15:47,110 Og áskorun á hönd nú er að fara að vera að raða þessum krakkar, en þá 425 00:15:47,110 --> 00:15:50,250 við erum að fara til verða að hugsa smá hart um hvernig á skilvirkan hátt við raun 426 00:15:50,250 --> 00:15:51,110 raðað þeim. 427 00:15:51,110 --> 00:15:52,580 Þannig að við skulum fyrst reyna þetta. 428 00:15:52,580 --> 00:15:55,970 Þú krakkar geta séð tölur hvers annars bara með því að setja í kringum hornum. 429 00:15:55,970 --> 00:15:59,380 Fara á undan og taka nokkrar sekúndur, og raða ykkur frá minnstu á 430 00:15:59,380 --> 00:16:01,240 vinstri til stærsta hægra megin. 431 00:16:01,240 --> 00:16:02,490 Fara. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Gott. 435 00:16:08,030 --> 00:16:09,370 Það var mjög fjári hratt. 436 00:16:09,370 --> 00:16:14,040 Nú einhver hér, hvað var reiknirit að þessir krakkar beitt? 437 00:16:14,040 --> 00:16:14,900 >> Ræðumaður 1: Minnst til mest. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. Malan: OK. 439 00:16:15,000 --> 00:16:18,070 Kosti að mest er í raun raða af Markmið, en ég er ekki viss um að það 440 00:16:18,070 --> 00:16:18,890 virkilega reiknirit. 441 00:16:18,890 --> 00:16:21,810 Kosti að mestu ekki segja mér skref fyrir skref hvað ég á að gera. 442 00:16:21,810 --> 00:16:22,833 Já? 443 00:16:22,833 --> 00:16:24,083 >> Ræðumaður 1: [inaudible] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. Malan: OK. 446 00:16:26,280 --> 00:16:28,920 Svo ef þú sérð mann minni en númer, þá fara til 447 00:16:28,920 --> 00:16:29,680 rétt þeirra. 448 00:16:29,680 --> 00:16:32,800 Svo það er nú að fá meiri tjáningu, meira eins og reiknirit, vegna þess að þú 449 00:16:32,800 --> 00:16:35,410 má segja, ef þetta, þá. 450 00:16:35,410 --> 00:16:37,050 Þannig að við höfum einhvers konar skilyrt reisa. 451 00:16:37,050 --> 00:16:39,700 Og þessir krakkar virtust gera það nokkrum sinnum, af því að sumir af þú flutt svolítið 452 00:16:39,700 --> 00:16:40,420 af fjarlægð. 453 00:16:40,420 --> 00:16:43,410 Þannig að það var væntanlega einhvers konar lykkja gerast í huga þeirra. 454 00:16:43,410 --> 00:16:44,610 >> En við skulum reyna að móta það. 455 00:16:44,610 --> 00:16:47,540 Ef þú krakkar gætu endurstilla aftur að þetta fyrirkomulag. 456 00:16:47,540 --> 00:16:50,650 Við skulum sjá hvort við getum ekki formlega þetta hluti, og þá spyrja, bara 457 00:16:50,650 --> 00:16:51,580 Hversu duglegur er þetta? 458 00:16:51,580 --> 00:16:54,220 Að sjálfsögðu, þegar við að gera þetta hægar, það er að fara að líða eins gott 459 00:16:54,220 --> 00:16:57,210 reiknirit, en við skulum sjá hvort við getum setja fingur okkar á nákvæman vegvísi. 460 00:16:57,210 --> 00:16:58,670 >> Svo þú tveir gaurar eru fjórir og tveir. 461 00:16:58,670 --> 00:17:01,020 Eða þú rétt eða rangt röð? 462 00:17:01,020 --> 00:17:01,900 Augljóslega rangar. 463 00:17:01,900 --> 00:17:02,710 Svo við skipti. 464 00:17:02,710 --> 00:17:05,170 Nú ætla ég að fara til hliðar hér og segja, 05:56. 465 00:17:05,170 --> 00:17:06,240 Ertu rétt eða rangt? 466 00:17:06,240 --> 00:17:06,599 >> Gabe: Rétt. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. Malan: Rétt. 468 00:17:07,180 --> 00:17:08,300 Sex og einn? 469 00:17:08,300 --> 00:17:08,609 Nope. 470 00:17:08,609 --> 00:17:09,630 Víxla. 471 00:17:09,630 --> 00:17:10,490 Svo er að tveir skiptasamninga. 472 00:17:10,490 --> 00:17:11,710 Sex og þremur? 473 00:17:11,710 --> 00:17:11,980 Nope. 474 00:17:11,980 --> 00:17:13,000 Víxla. 475 00:17:13,000 --> 00:17:13,930 Sex og sjö? 476 00:17:13,930 --> 00:17:14,630 Lítur vel út. 477 00:17:14,630 --> 00:17:15,396 Sjö og fimm? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [inaudible] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. Malan: OK, skipti. 480 00:17:17,089 --> 00:17:19,770 Og raðað. 481 00:17:19,770 --> 00:17:19,980 Allt í lagi. 482 00:17:19,980 --> 00:17:21,440 Svo augljóslega ekki satt? 483 00:17:21,440 --> 00:17:22,470 Þannig að það var meira að fara á. 484 00:17:22,470 --> 00:17:24,920 En, reyndar, þessir krakkar, jafnvel bara dragast. 485 00:17:24,920 --> 00:17:25,450 hélt að færa. 486 00:17:25,450 --> 00:17:27,710 Þeir gerðu ekki bara að hætta, þegar þeir leiðrétta eitt vandamál. 487 00:17:27,710 --> 00:17:27,839 Svo. 488 00:17:27,839 --> 00:17:29,390 Reyndar er ég að fara að hafa að gera það sama. 489 00:17:29,390 --> 00:17:32,720 Ég ætla að hafa til að raða í baka í bak í byrjun þessa vanda, 490 00:17:32,720 --> 00:17:35,630 eða í upphafi þessa fjölbreytta fólk, við skulum byrja að kalla þá. 491 00:17:35,630 --> 00:17:38,366 >> Og nú hvað ætti reiknirit mín á annarri umferð vera? 492 00:17:38,366 --> 00:17:39,220 >> Ræðumaður 1: Sami hlutur. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. Malan: Sami hlutur. 494 00:17:39,940 --> 00:17:41,460 Og þetta, ég er farin að eins, ekki satt? 495 00:17:41,460 --> 00:17:44,720 Um leið og þú getur fundið sjálfur að gera sama aftur og aftur, það er 496 00:17:44,720 --> 00:17:47,890 verða meira eins og reiknirit, og minna manna eðlishvöt. 497 00:17:47,890 --> 00:17:48,680 >> Svo nú, hér við fara aftur. 498 00:17:48,680 --> 00:17:49,870 Tvö og fjögur? 499 00:17:49,870 --> 00:17:50,220 Nei 500 00:17:50,220 --> 00:17:51,050 Four og einn? 501 00:17:51,050 --> 00:17:53,380 Ah, það var örugglega einhver vinna enn að gera. 502 00:17:53,380 --> 00:17:53,620 Fyrir og þremur? 503 00:17:53,620 --> 00:17:54,572 Gott. 504 00:17:54,572 --> 00:17:56,000 Fjögur og sex? 505 00:17:56,000 --> 00:17:58,380 Sex og fimm? 506 00:17:58,380 --> 00:17:59,470 Sex og sjö? 507 00:17:59,470 --> 00:18:00,970 OK, nú, lokið. 508 00:18:00,970 --> 00:18:01,550 OK, nei. 509 00:18:01,550 --> 00:18:02,710 Ég verð að fara til baka. 510 00:18:02,710 --> 00:18:05,130 >> Svo nú, aftur, við erum að gera þetta smá meira af ásettu ráði. 511 00:18:05,130 --> 00:18:08,700 Og nú, það er bara einn heili framkvæmd þessa reiknirit. 512 00:18:08,700 --> 00:18:10,290 Einn CPU, ef þú vilt. 513 00:18:10,290 --> 00:18:13,090 Og hreinskilnislega, það er eina úrræði við erum að fara að hafa aðgang að. 514 00:18:13,090 --> 00:18:16,280 Og þegar við förum aftur í lyklaborðið og hafa eitthvað eins og C á okkar 515 00:18:16,280 --> 00:18:19,600 förgun, erum við aðeins að skrifa forrit sem getur gert eitt í einu. 516 00:18:19,600 --> 00:18:22,900 En þessir krakkar í smá stund síðan, við skuldsett sameiginlega brainpower þeirra 517 00:18:22,900 --> 00:18:24,180 eins og þú krakkar gerði í núll viku. 518 00:18:24,180 --> 00:18:24,980 Svo skulum halda þessu. 519 00:18:24,980 --> 00:18:26,260 >> Tveggja og einn. 520 00:18:26,260 --> 00:18:26,945 Tveir og þrír. 521 00:18:26,945 --> 00:18:27,460 Þrír og fjórir. 522 00:18:27,460 --> 00:18:28,310 Fjórir og fimm. 523 00:18:28,310 --> 00:18:28,620 Fimm og sex. 524 00:18:28,620 --> 00:18:30,510 Sex og sjö. 525 00:18:30,510 --> 00:18:31,880 Gert? 526 00:18:31,880 --> 00:18:34,560 Svo er ég, en láta mig spila djöfulsins talsmaður. 527 00:18:34,560 --> 00:18:37,950 Þarf ég, eins konar tölva sem bara gerði fara í gegnum þessa fjölbreytta 528 00:18:37,950 --> 00:18:40,225 fólk, veit að ég er búin? 529 00:18:40,225 --> 00:18:40,670 >> Ræðumaður 1: Nei 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. Malan: Svo hvers vegna? 531 00:18:41,050 --> 00:18:46,900 Hvað myndi ég þurfa að gera til að álykta afgerandi að ég er að gera? 532 00:18:46,900 --> 00:18:48,230 Sennilega eitt framhjá. 533 00:18:48,230 --> 00:18:48,430 Ekki satt? 534 00:18:48,430 --> 00:18:51,760 Vegna allt sem ég veit af því að fyrri Skarðið er að ég leiðrétta mistök. 535 00:18:51,760 --> 00:18:53,920 Og það þýðir, kannski er það enn annar mistök 536 00:18:53,920 --> 00:18:54,840 sem ég þarf að leiðrétta. 537 00:18:54,840 --> 00:18:58,680 Svo ég get ekki verið viss um trekkja, og þá stöðva, 1-2, tvö og 538 00:18:58,680 --> 00:19:00,940 þrír, þrír og fjórir, fjórir og fimm, fimm og sex, sex og sjö. 539 00:19:00,940 --> 00:19:02,510 OK, nú ég gerði ekkert verk vinna. 540 00:19:02,510 --> 00:19:05,990 >> Ég get vissulega man að ég gerði ekkert vinna með eitthvað eins breytu, 541 00:19:05,990 --> 00:19:06,975 eins við int. 542 00:19:06,975 --> 00:19:12,490 Kalla það skiptasamninga, og ef skiptasamninga er 0 þegar ég fá hér, og það byrjaði að minnsta 0, þá 543 00:19:12,490 --> 00:19:15,520 Ég vildi bara vera heimskur til að halda áfram fram og til baka, eftirlits aftur, og 544 00:19:15,520 --> 00:19:16,450 aftur og aftur, ekki satt? 545 00:19:16,450 --> 00:19:18,450 Þar sem þú færð fastur í sumum konar óendanlega lykkju. 546 00:19:18,450 --> 00:19:21,250 Svo um leið og það er 0 skiptasamninga, getum við haldið því fram að þetta 547 00:19:21,250 --> 00:19:23,810 reiknirit er örugglega lokið. 548 00:19:23,810 --> 00:19:25,400 >> Nú, við skulum setja nafn á þetta. 549 00:19:25,400 --> 00:19:28,930 The reiknirit sem ég leggja til við bara framkvæmda er eitthvað sem kallast kúla 550 00:19:28,930 --> 00:19:32,800 tegund, þekktur sem slíkur í þeim skilningi að tölurnar sem eru stærri konar 551 00:19:32,800 --> 00:19:37,990 kúla leið sína upp á toppinn, eða upp til loka array af tölum. 552 00:19:37,990 --> 00:19:40,270 En hvernig duglegur var þetta reiknirit? 553 00:19:40,270 --> 00:19:44,600 Hversu mörg skref gerði ég hef líkamlega til Taka, til dæmis, til að raða þeim 554 00:19:44,600 --> 00:19:45,850 sjö menn? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Fjögur til fimm? 557 00:19:49,550 --> 00:19:51,420 OK, of margir á endanum að fara að vera svarið. 558 00:19:51,420 --> 00:19:54,960 En jafnvel þá, er tilteknum fjölda er ekki svo áhugavert. 559 00:19:54,960 --> 00:19:56,670 Skulum alhæfa það sem n. 560 00:19:56,670 --> 00:20:00,520 Svo ef ég hefði n fólk upp hér, og þeir voru, eins konar, af handahófi á að 561 00:20:00,520 --> 00:20:02,180 upphafi, í því upprunalega röð. 562 00:20:02,180 --> 00:20:04,910 Jæja, hversu mörg skref gerði ég að taka á fyrstu umferð? 563 00:20:04,910 --> 00:20:09,810 Það var einn, tveir, þrír, fjórir, fimm, sex, og þeir eru sjö manns, svo 564 00:20:09,810 --> 00:20:13,670 það er sjö, sex - svo það er n mínus einn stíga í fyrsta sinn. 565 00:20:13,670 --> 00:20:16,280 >> Nú, hversu mörg skref gerði ég til að taka þegar ég rewound? 566 00:20:16,280 --> 00:20:19,310 Jæja, við í raun tvöfalda það ef okkur langaði til, en nú, ég er 567 00:20:19,310 --> 00:20:22,300 bara að fara að segja, allt í lagi, annar n mínus 1. 568 00:20:22,300 --> 00:20:25,240 Svo n mínus 1 er að fara að fá pirrandi að halda utan um, þannig að við skulum 569 00:20:25,240 --> 00:20:26,400 bara umferð upp smávegis. 570 00:20:26,400 --> 00:20:27,770 Svo 2n skref. 571 00:20:27,770 --> 00:20:29,310 Svo 14 skref, gefa eða taka. 572 00:20:29,310 --> 00:20:31,930 >> Hversu oft gerði ég taka skref næst? 573 00:20:31,930 --> 00:20:33,740 Jæja, það er 3n. 574 00:20:33,740 --> 00:20:34,510 í raun. 575 00:20:34,510 --> 00:20:37,920 Og nú, í versta tilfelli, fyrir dæmi, hversu oft hefði ég 576 00:20:37,920 --> 00:20:41,730 farið fram og til baka, fram og til baka, framkvæmd þessa reiknirit, skipta 577 00:20:41,730 --> 00:20:44,620 fólk á hverjum skarðið, u.þ.b.? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Það er í raun n veldi, ekki satt? 580 00:20:50,010 --> 00:20:53,000 >> Vegna þess að í versta tilfelli, þú getur konar um að hugsa um þetta innsæi, 581 00:20:53,000 --> 00:20:54,800 jafnvel þó það gæti tekið smá smá tíma til að sökkva inn 582 00:20:54,800 --> 00:20:57,590 Í versta tilfelli, hvað myndi þetta sjö manns hafa litið út, í 583 00:20:57,590 --> 00:21:00,230 skilmálum fyrirkomulagi af fjölda þeirra? 584 00:21:00,230 --> 00:21:01,460 Alveg afturábak, ekki satt? 585 00:21:01,460 --> 00:21:02,815 Og bara til að líkja því, hvað var nafnið þitt aftur? 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> DAVID J. Malan: Mike? 588 00:21:03,640 --> 00:21:08,100 OK, Mike, getur þú tekið þátt bara mig yfir hér fyrir bara eina sekúndu? 589 00:21:08,100 --> 00:21:08,880 Reyndar ekki. 590 00:21:08,880 --> 00:21:10,150 Því miður Mike, baka skulum. 591 00:21:10,150 --> 00:21:10,910 Hvað heitirðu aftur? 592 00:21:10,910 --> 00:21:11,180 >> NEIL: Neil. 593 00:21:11,180 --> 00:21:11,640 >> DAVID J. Malan: Neil. 594 00:21:11,640 --> 00:21:13,750 OK, Neil, kemur þú með mig, ef þú dont 'hugur. 595 00:21:13,750 --> 00:21:17,150 Þannig að ég ætla að leggja til, bara til einfaldleiki, sem Neil er nú í hans 596 00:21:17,150 --> 00:21:18,510 versta mögulega tilfelli. 597 00:21:18,510 --> 00:21:20,720 En muna hvernig ég innleitt reiknirit mín. 598 00:21:20,720 --> 00:21:24,530 Ég er að bera saman, bera saman, bera saman, bera saman, bera saman, oh. 599 00:21:24,530 --> 00:21:26,640 Nú þessir krakkar eru út þess, svo ég laga. 600 00:21:26,640 --> 00:21:27,980 Svo þú krakkar skipti. 601 00:21:27,980 --> 00:21:31,630 En nú íhuga, hversu mikið lengra er Neil að fara? 602 00:21:31,630 --> 00:21:32,690 Það er u.þ.b. n. 603 00:21:32,690 --> 00:21:33,570 Þú veist, það er í raun ekki n. 604 00:21:33,570 --> 00:21:36,040 Það er eins og n mínus 1, en ég er að fá gramur halda utan um litla 605 00:21:36,040 --> 00:21:37,550 númer, þannig að við skulum bara kalla það n. 606 00:21:37,550 --> 00:21:42,860 >> Svo ef Neil færist eitt skref hámarks hver tími, og að færa Neil eitt skref, 607 00:21:42,860 --> 00:21:46,580 Ég verð að gera þetta virkilega leiðinlegur framhjá fram og til baka, þetta er um það bil 608 00:21:46,580 --> 00:21:52,080 að gera þetta, n skref, samtals n sinnum, því það er að fara að taka mig 609 00:21:52,080 --> 00:21:55,820 sem margir skref til að fá Neil allt leið þangað sem hann tilheyrir. 610 00:21:55,820 --> 00:21:58,620 Hvað þá allir aðrir ef þið voru allir not-röð eins og heilbrigður. 611 00:21:58,620 --> 00:22:01,100 >> Svo skulum kalla kúla konar n ferningur. 612 00:22:01,100 --> 00:22:04,860 Rekstur sinn á þessum reiknirit er Árangur af þessum reiknirit er 613 00:22:04,860 --> 00:22:07,120 skilvirkni þessarar reiknirit, við munum bara lýsa meira 614 00:22:07,120 --> 00:22:08,800 almennt n veldi. 615 00:22:08,800 --> 00:22:11,650 Sem er ágætur, vegna þess að ég gæti gert það Sama dæmi með átta manns, níu 616 00:22:11,650 --> 00:22:15,450 fólk, milljón manns, og að Svarið er ekki að fara að breytast. 617 00:22:15,450 --> 00:22:18,870 >> Þannig að ef þú krakkar vildi ekki huga, við skulum endurstilla þig þar sem þú byrjaðir. 618 00:22:18,870 --> 00:22:22,510 Og við skulum reyna tvær aðrar leiðir og sjá hvort við getum ekki gert grundvallaratriðum 619 00:22:22,510 --> 00:22:23,820 betri en þetta. 620 00:22:23,820 --> 00:22:27,130 Svo þessar mundir, ætla ég að leggja eins konar mismunandi reiknirit. 621 00:22:27,130 --> 00:22:29,950 Það var mjög snjall af okkur síðasta sinn, og þú krakkar voru rétt að hafa 622 00:22:29,950 --> 00:22:32,470 rétt eðlishvöt af bara góður að skipta pöruðum. 623 00:22:32,470 --> 00:22:36,500 En ef ég vildi virkilega að nálgast þetta einfaldlega, og markmið mitt er að færa 624 00:22:36,500 --> 00:22:39,800 öll litlu tölur með þessum hætti, og ýta öllum stóru tölur sem 625 00:22:39,800 --> 00:22:43,030 vegur, hví ekki ég bara að í mest barnaleg hátt og sjá hvort ég 626 00:22:43,030 --> 00:22:45,730 getur gert betur en það var nokkuð flókið reiknirit? 627 00:22:45,730 --> 00:22:46,620 >> Svo skulum sjá. 628 00:22:46,620 --> 00:22:48,940 Fjögur er mjög lítið númer, þannig að ég er fara að yfirgefa þig þar augnablik. 629 00:22:48,940 --> 00:22:50,610 Ooh, númer tvö er jafnvel betra. 630 00:22:50,610 --> 00:22:52,230 Svo getur þú stíga bara áfram í smástund? 631 00:22:52,230 --> 00:22:55,670 Þetta er nú minnsti fjöldi var minn frambjóðandi, og ég ætla að muna 632 00:22:55,670 --> 00:22:57,000 að með, eins og breytu. 633 00:22:57,000 --> 00:22:57,930 En ég ætla að halda að haka. 634 00:22:57,930 --> 00:22:59,890 Er einhver sem tala er minni? 635 00:22:59,890 --> 00:23:00,460 Six, nr. 636 00:23:00,460 --> 00:23:01,390 Ó, það er Neil aftur. 637 00:23:01,390 --> 00:23:04,050 >> Þannig að ég ætla að ýta þér aftur konar eðli. 638 00:23:04,050 --> 00:23:05,120 Neil mun koma fram. 639 00:23:05,120 --> 00:23:08,440 Og nú, breytu sem ég nota til að halda utan um sem hefur minnstu 640 00:23:08,440 --> 00:23:11,390 tala er uppfærð að innihalda Neil er staðsetning. 641 00:23:11,390 --> 00:23:12,110 Jæja, við skulum sjá. 642 00:23:12,110 --> 00:23:13,960 Þrír, sjö, fimm. 643 00:23:13,960 --> 00:23:15,590 OK, ég veit Neil var minnsti. 644 00:23:15,590 --> 00:23:18,110 Hvað er einfaldasta hlutur fyrir mig að gera núna? 645 00:23:18,110 --> 00:23:21,410 Ég ætla ekki að sóa tíma mínum með því bara freyðandi Neil einn blettur til vinstri. 646 00:23:21,410 --> 00:23:25,350 Hvers vegna get ég ekki sett bara Neil þar sem hann tilheyrir, sem er auðvitað hvar? 647 00:23:25,350 --> 00:23:26,160 >> Alla leið í upphafi. 648 00:23:26,160 --> 00:23:27,720 Svo Neil, komdu með mér. 649 00:23:27,720 --> 00:23:28,910 Og hvað var nafnið þitt aftur? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Grace. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. Malan: Grace. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Svo Grace, því miður, þú ert konar í leiðinni. 654 00:23:32,490 --> 00:23:34,290 Svo hvernig leysa við þetta vandamál? 655 00:23:34,290 --> 00:23:34,490 Ekki satt? 656 00:23:34,490 --> 00:23:37,500 Ef þetta er fylki, það er aðeins sjö stöðum. 657 00:23:37,500 --> 00:23:40,830 Muna að með Rob, talaði við um lýsa aldri, og við höfðum aðeins 658 00:23:40,830 --> 00:23:41,740 endanlegri fjölda aldri? 659 00:23:41,740 --> 00:23:42,535 Sama hugmynd hér. 660 00:23:42,535 --> 00:23:44,300 Við höfum aðeins endanlega fjölda ints. 661 00:23:44,300 --> 00:23:47,590 Grace er góður af í okkar vegur, svo hvernig gætum við? 662 00:23:47,590 --> 00:23:49,555 >> Einfaldasta leiðin er eins, Náð, því miður. 663 00:23:49,555 --> 00:23:51,870 Þú ert að fara að þurfa að fara yfir það svo að við getum gert herbergið. 664 00:23:51,870 --> 00:23:55,290 Nú, ef þú hugsa um þetta, kannski við gert bara vandamálið verra. 665 00:23:55,290 --> 00:23:58,510 Og kannski við gerðum, því hvað ef Náð var á réttum stað? 666 00:23:58,510 --> 00:24:01,730 En við vitum að hún er ekki, vegna þess að Annars væri hún hafi verið 667 00:24:01,730 --> 00:24:03,980 standa áfram í stað þess að Neil á þessum tíma, ekki satt? 668 00:24:03,980 --> 00:24:05,550 Við skoðuðum nú þegar númerið hennar út. 669 00:24:05,550 --> 00:24:05,770 >> Allt í lagi. 670 00:24:05,770 --> 00:24:09,110 Svo nú, Neil er á réttum stað, og Ég get gert smá fínstillingu. 671 00:24:09,110 --> 00:24:11,740 Fyrir næstu mínútu, ég ætla að hunsa Neil allt saman, svo sem ekki að 672 00:24:11,740 --> 00:24:15,280 sóa tíma sínum, eða tilviljun skipta honum á röngum stað. 673 00:24:15,280 --> 00:24:17,805 Svo nú, hvernig finn ég næsta þáttur sem er minnst? 674 00:24:17,805 --> 00:24:18,480 Tveir. 675 00:24:18,480 --> 00:24:20,225 Það er nokkuð gott númer, ef þú vilt að stíga fram og 676 00:24:20,225 --> 00:24:21,100 Ég man eftir þér. 677 00:24:21,100 --> 00:24:21,980 Sex, ekki gott. 678 00:24:21,980 --> 00:24:24,820 Fjórir, þrír, sjö, fimm, ekki gott. 679 00:24:24,820 --> 00:24:26,800 Svo láta mig fara að rétti staðurinn þinn. 680 00:24:26,800 --> 00:24:28,470 Og við fengum bara heppinn í þetta sinn. 681 00:24:28,470 --> 00:24:31,350 >> Nú ætla ég að hunsa þetta tveir krakkar, og nú gera eitt 682 00:24:31,350 --> 00:24:32,260 fara í gegnum þetta. 683 00:24:32,260 --> 00:24:33,490 Sex, sem frekar lítið númer. 684 00:24:33,490 --> 00:24:34,300 Komdu fram. 685 00:24:34,300 --> 00:24:35,220 Ó, fyrirgefðu. 686 00:24:35,220 --> 00:24:37,640 Tala Grace er betra, svo stíga á áfram. 687 00:24:37,640 --> 00:24:38,260 Fjórir. 688 00:24:38,260 --> 00:24:39,120 Því miður, Grace. 689 00:24:39,120 --> 00:24:39,950 Fara aftur til baka. 690 00:24:39,950 --> 00:24:41,550 Númer þrjú er betri. 691 00:24:41,550 --> 00:24:42,290 Sjö. 692 00:24:42,290 --> 00:24:42,720 Fimm. 693 00:24:42,720 --> 00:24:43,550 Og nú er það nafnið þitt aftur? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. Malan: Jason. 696 00:24:44,420 --> 00:24:47,050 Svo er Jason nú minnsti þáttur sem ég hef valið. 697 00:24:47,050 --> 00:24:49,160 Hvar er hann að fara að fara? 698 00:24:49,160 --> 00:24:50,380 Svo þar sex er. 699 00:24:50,380 --> 00:24:51,210 Og nafn þitt er aftur? 700 00:24:51,210 --> 00:24:51,710 >> Gabe: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> DAVID J. Malan: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe er í leiðinni. 703 00:24:53,220 --> 00:24:54,640 Hvað er auðveldast að gera? 704 00:24:54,640 --> 00:24:58,390 Skipta þessir tveir gaurar og halda áfram. 705 00:24:58,390 --> 00:24:59,020 Svo nú skulum sjá. 706 00:24:59,020 --> 00:25:00,170 Hver er minnsti? 707 00:25:00,170 --> 00:25:01,030 Fjórir. 708 00:25:01,030 --> 00:25:01,990 Leyfðu mér bara svona svindl. 709 00:25:01,990 --> 00:25:03,090 Fimm er að fara að vera minnsti. 710 00:25:03,090 --> 00:25:05,220 Mér finnst næsta, ef þú vilt að stíga fram, hvað ég þarf að gera við 711 00:25:05,220 --> 00:25:06,820 þessir krakkar, með Gabe? 712 00:25:06,820 --> 00:25:08,450 Skipta aftur. 713 00:25:08,450 --> 00:25:10,740 Svo nú, enn örlítið út af röð. 714 00:25:10,740 --> 00:25:14,140 Ég fann Gabe að vera minnsti, svo Ég skjóta honum út, færa ykkur yfir. 715 00:25:14,140 --> 00:25:15,190 Og gert. 716 00:25:15,190 --> 00:25:17,200 >> Svo er svarið það sama. 717 00:25:17,200 --> 00:25:18,600 The Niðurstaðan er sú sama. 718 00:25:18,600 --> 00:25:22,730 Hver af þessum tveimur reiknirit er betra? 719 00:25:22,730 --> 00:25:23,500 The second einn, heyrði ég. 720 00:25:23,500 --> 00:25:24,252 Hvers vegna? 721 00:25:24,252 --> 00:25:25,900 >> Ræðumaður 3: Það er n skref [inaudible]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. Malan: Það er n skrefum á flestum. 723 00:25:27,600 --> 00:25:28,490 Áhugavert. 724 00:25:28,490 --> 00:25:30,610 Svo er það þó? 725 00:25:30,610 --> 00:25:33,630 Svo hvernig did I finna Minnsta þáttur? 726 00:25:33,630 --> 00:25:37,060 Hversu mörg skref var ég að taka The finna minnsta stak? 727 00:25:37,060 --> 00:25:39,220 Ég hafði að líta alla leið í lok, ekki satt? 728 00:25:39,220 --> 00:25:41,530 Vegna þess að í því versta tilfelli, hvað ef Neil voru hérna? 729 00:25:41,530 --> 00:25:45,700 Svo bara að finna minnstu þáttur tekur mig n stíga, eða N mínus 1. 730 00:25:45,700 --> 00:25:46,100 En, OK. 731 00:25:46,100 --> 00:25:46,980 Svo gætum Neil. 732 00:25:46,980 --> 00:25:48,740 Mundu að eina mínútu eða svo síðan. 733 00:25:48,740 --> 00:25:51,680 >> En hvernig gerði ég finna næsta Minnsta þáttur? 734 00:25:51,680 --> 00:25:54,830 Það er n mínus 1, eða n mínus 2 í raun, frá fjölda af skrefum. 735 00:25:54,830 --> 00:25:55,440 Svo OK. 736 00:25:55,440 --> 00:25:57,390 Svo ég gerði n mínus 2. 737 00:25:57,390 --> 00:25:57,600 Allt í lagi. 738 00:25:57,600 --> 00:25:59,130 Svo finnst svolítið betur. 739 00:25:59,130 --> 00:25:59,730 Allt í lagi. 740 00:25:59,730 --> 00:26:03,270 Hversu margir stíga næst að finna númer þrjú? 741 00:26:03,270 --> 00:26:04,420 Svo n mínus 4. 742 00:26:04,420 --> 00:26:07,670 Svo það er minnkandi, eitt færri stíga á hverri ítrun. 743 00:26:07,670 --> 00:26:08,740 Þannig að þetta er líða betur, ekki satt? 744 00:26:08,740 --> 00:26:13,450 Ef síðasta tíma var u.þ.b. n sinnum n, í þetta sinn það er n mínus 1, auk n mínus 745 00:26:13,450 --> 00:26:16,500 2, auk n mínus 3, ásamt n mínus 4, punktur, punktur, punktur. 746 00:26:16,500 --> 00:26:18,750 En ef þú manst úr menntaskóla þínum kennslubækur, litli svindlari 747 00:26:18,750 --> 00:26:24,380 blaði á bak sem hefur formúlur, ef þú bæta upp þessa röð af tölum, 748 00:26:24,380 --> 00:26:31,280 hvað er heildarfjöldi skrefum að fara að vera að ég taka hér? 749 00:26:31,280 --> 00:26:36,580 >> Þetta er einn af þeim, eins og, n mínus 1, sinnum n, deilt með 2. 750 00:26:36,580 --> 00:26:39,040 Svo láta mig sjá hvort ég get draga þetta upp fyrir réttlátur a augnablik. 751 00:26:39,040 --> 00:26:42,230 Og aftur, ég konar námundun sumir tölur bara til að halda líf okkar einfalt, 752 00:26:42,230 --> 00:26:47,830 en eins og ég man, það er eitthvað eins og ef Ég gera N mínus 1 hluti, þá n mínus 753 00:26:47,830 --> 00:26:53,570 2, þá er n mínus 3, það er um það bil eitthvað eins og þetta yfir 2, og ef ég 754 00:26:53,570 --> 00:26:55,510 margfalda þetta út, það er reyndar n ferningur. 755 00:26:55,510 --> 00:26:58,940 Það er ekki tilfinning of gott. n mínus n yfir 2. 756 00:26:58,940 --> 00:27:00,350 >> En hér er málið. 757 00:27:00,350 --> 00:27:03,720 Í tölvunarfræði, þegar erfiðleikar byrja að fá áhugavert er þegar n 758 00:27:03,720 --> 00:27:04,700 fær mjög stór. 759 00:27:04,700 --> 00:27:08,110 Og þegar n fær mjög stór, sem af þessi gildi er að fara að ráða öllu 760 00:27:08,110 --> 00:27:09,750 af öðrum? 761 00:27:09,750 --> 00:27:10,990 Það er góður af n veldi, ekki satt? 762 00:27:10,990 --> 00:27:13,340 Já, deila með 2 er nokkuð góð. 763 00:27:13,340 --> 00:27:16,740 En ef þú ert að tala um milljarða stykki af gögnum eða Trillions 764 00:27:16,740 --> 00:27:18,700 stykki af gögnum, í lagi, svo þú ert tvisvar eins hratt. 765 00:27:18,700 --> 00:27:22,440 En hver blíðuhót í raun ef að stór tala, ef þessi þáttur er það sem fær 766 00:27:22,440 --> 00:27:23,040 stærri og stærri. 767 00:27:23,040 --> 00:27:25,990 Og vissulega gerir það meira af munur en þetta strákur. 768 00:27:25,990 --> 00:27:29,120 Svo jafnvel þótt þú krakkar eru rétt, Annað reiknirit, munum við kalla það 769 00:27:29,120 --> 00:27:32,970 Val tagi, er í hinum raunverulega heimi, sem hluti hraðar hugsanlega, því ég er 770 00:27:32,970 --> 00:27:35,360 taka færri og færri skref í hvert skipti. 771 00:27:35,360 --> 00:27:37,340 >> Það er í raun ekki í grundvallaratriðum hraðar. 772 00:27:37,340 --> 00:27:41,430 Vegna þess að ef við spilum reyndar þetta út fyrir stór gildi n, í lok 773 00:27:41,430 --> 00:27:44,750 daginn, að nógu stór n, er það enn að fara að finna nokkuð hægur. 774 00:27:44,750 --> 00:27:46,770 Jæja, láttu mig taka einn síðustu umferð á þeim. 775 00:27:46,770 --> 00:27:48,920 Það er það sem ég myndi kalla val konar. 776 00:27:48,920 --> 00:27:51,040 Getur þú krakkar endurstilla ykkur eitt síðasta skipti? 777 00:27:51,040 --> 00:27:53,550 Og í þessu síðasta tilfelli, ég er að fara að leggja eitthvað 778 00:27:53,550 --> 00:27:54,970 kallað innsetningu konar. 779 00:27:54,970 --> 00:27:57,470 Innsetning konar vera, eðli, svolítið öðruvísi. 780 00:27:57,470 --> 00:28:00,980 >> Frekar en að fara fram og til baka og velja minnstu frumefni, ég 781 00:28:00,980 --> 00:28:05,030 bara að fara að takast á við hvert þessara krakkar sem ég lenda þeim, og settu 782 00:28:05,030 --> 00:28:06,850 þá í rétta stað þeirra. 783 00:28:06,850 --> 00:28:10,160 Þannig að ég ætla bara að fara að byrja með Grace, og ég sé að hún er númer fjögur. 784 00:28:10,160 --> 00:28:11,720 Hvar er númer fjögur tilheyra? 785 00:28:11,720 --> 00:28:14,940 Ég hef ekki byrjað flokkun neitt, svo fær Grace að vera rétt þar. 786 00:28:14,940 --> 00:28:18,355 Og nú ætla ég að halda því fram, ef þú gætir taka skref til hægri, þetta 787 00:28:18,355 --> 00:28:21,650 raðað minn listi, þetta er minn unsorted eftir lista. 788 00:28:21,650 --> 00:28:23,260 Svo nú ætla ég að halda áfram á næsta, og hvað er nafnið þitt aftur? 789 00:28:23,260 --> 00:28:23,700 >> BRANSON: Branson. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. Malan: Branson. 791 00:28:24,150 --> 00:28:25,375 Svo er Branson númer tvö. 792 00:28:25,375 --> 00:28:27,490 Þannig að ég ætla að taka þig út í smástund. 793 00:28:27,490 --> 00:28:30,940 Og nú, hvar tilheyra þér í þessu fylki? 794 00:28:30,940 --> 00:28:32,360 Svo til hægri Grace. 795 00:28:32,360 --> 00:28:35,670 Svo aftur, við erum konar að gera Grace gera a einhver fjöldi af vinna hér. 796 00:28:35,670 --> 00:28:37,290 Hvar set við þig? 797 00:28:37,290 --> 00:28:40,120 Þannig að við erum að fara að renna þér á vinstri, og setja Branson þar. 798 00:28:40,120 --> 00:28:41,680 En nú er ég halda því fram að þú krakkar ert. 799 00:28:41,680 --> 00:28:43,240 En fyrirvara, ég er ekki að nota auka rúm. 800 00:28:43,240 --> 00:28:45,130 Það er samt 2 atriði hér, 5 hérna. 801 00:28:45,130 --> 00:28:47,910 Samtals array stærð er 7, þannig að ég er ekki að svindla, allt í lagi? 802 00:28:47,910 --> 00:28:51,950 >> Svo nú höfum við, með Gabe hér, númer sex, þar tilheyrir þú? 803 00:28:51,950 --> 00:28:52,650 Þú got heppinn aftur. 804 00:28:52,650 --> 00:28:53,820 Þannig að þú færð að vera rétt þar. 805 00:28:53,820 --> 00:28:57,210 Bara taka smá skref til hægri bara til að gera ljóst að þú ert flokkað. 806 00:28:57,210 --> 00:29:00,520 Og nú höfum við Neil aftur, númer einn, hvar sem þú ferð? 807 00:29:00,520 --> 00:29:03,540 Og nú er þar sem við munum byrja að sjá að Þetta reiknirit, þó á fyrsta 808 00:29:03,540 --> 00:29:05,950 tillit, finnst nokkuð klár, horfa hvað er að fara að gerast. 809 00:29:05,950 --> 00:29:07,370 Ef þú gætir stíga fram. 810 00:29:07,370 --> 00:29:09,260 >> Hvar viljum við setja Neil? 811 00:29:09,260 --> 00:29:11,830 Svo augljóslega hér, svo hvernig fáum við Neil þar? 812 00:29:11,830 --> 00:29:12,970 Við skulum gera þetta skref-fyrir-skref. 813 00:29:12,970 --> 00:29:15,620 Gabe, þar þarft þú að fara? 814 00:29:15,620 --> 00:29:19,590 Já, svo taka eitt stórt skref, eða tveimur hálf-skref til að gera 815 00:29:19,590 --> 00:29:20,820 eitt skref þarna. 816 00:29:20,820 --> 00:29:21,750 Grace, þar sem þú ferð? 817 00:29:21,750 --> 00:29:22,510 Gott. 818 00:29:22,510 --> 00:29:23,500 Svo annað skref. 819 00:29:23,500 --> 00:29:24,960 Og að lokum, Branson? 820 00:29:24,960 --> 00:29:25,460 Annað skref. 821 00:29:25,460 --> 00:29:27,190 Og nú getum við sett Neil sinn stað. 822 00:29:27,190 --> 00:29:28,440 >> Svo nú, halda áfram þessari rökfræði. 823 00:29:28,440 --> 00:29:32,420 Jafnvel þótt við séum ekki að breytast Neil yfir, og aftur, og aftur, að setja hann 824 00:29:32,420 --> 00:29:36,420 þar sem hann fer, í versta tilfelli, næsta tala við gætum fundur gæti 825 00:29:36,420 --> 00:29:42,220 vera númer, segja, það var númer núll, þá erum við að fara að skipta öllum 826 00:29:42,220 --> 00:29:42,730 þessir krakkar. 827 00:29:42,730 --> 00:29:44,950 Segjum sem svo að það er tala, neikvæð einn, þá verðum við að skipta 828 00:29:44,950 --> 00:29:46,080 allar þessar krakkar. 829 00:29:46,080 --> 00:29:48,500 Þannig að við erum í raun bara svona ósvífni vandamálið í kring, þannig að við erum 830 00:29:48,500 --> 00:29:52,620 flytja kostnað frá val aðferð svo innsetning 831 00:29:52,620 --> 00:29:56,930 ferli, þannig að þið bara haft að færa það bil n mínus eitthvað 832 00:29:56,930 --> 00:29:57,940 fjölda af skrefum. 833 00:29:57,940 --> 00:30:01,200 Og þessi tala af skrefum er bara að fara að auka eins og ég að velja fleiri tölur, 834 00:30:01,200 --> 00:30:04,730 ef ég þarf að hafa ýting ykkur aftur, og aftur, og aftur. 835 00:30:04,730 --> 00:30:08,320 >> Svo er sorglegt hlutur nú allar þessar reiknirit eru n ferningur. 836 00:30:08,320 --> 00:30:10,570 Við skulum fara á undan og þökk sé þeim krakkar, og sjón þessar svolítið 837 00:30:10,570 --> 00:30:11,090 öðruvísi. 838 00:30:11,090 --> 00:30:12,312 Mjög vel gert. 839 00:30:12,312 --> 00:30:14,120 >> [Applause] 840 00:30:14,120 --> 00:30:15,030 >> Allt í lagi. 841 00:30:15,030 --> 00:30:16,280 Þar sem þú ferð. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Takk fyrir - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [inaudible] halda tölurnar. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. Malan: Nei, þú getur halda tölur eins vel. 846 00:30:21,990 --> 00:30:23,440 Allt í lagi. 847 00:30:23,440 --> 00:30:24,100 Fallega gert. 848 00:30:24,100 --> 00:30:25,300 Allt í lagi. 849 00:30:25,300 --> 00:30:30,510 Svo skulum sjá hvort við getum ekki nú saman hraðar og meira sjónrænt, 850 00:30:30,510 --> 00:30:33,410 nákvæmlega það bara gerðist hér segir. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Ég ætla að fara á undan og draga upp Firefox. 853 00:30:38,770 --> 00:30:41,310 Við munum tengja þessa kynningu á heimasíðu námskeiðsins er. 854 00:30:41,310 --> 00:30:43,870 Java er dálítið pirrandi að fá að vinna í sumum vöfrum þessa dagana. 855 00:30:43,870 --> 00:30:46,760 Svo ef þú spilar með þetta heima, grein fyrir að þú gætir þurft að nota Firefox 856 00:30:46,760 --> 00:30:47,990 til að fá það að virka. 857 00:30:47,990 --> 00:30:50,440 Og það sem ég ætla að gera við þetta Sýnt hefur verið fram er eftirfarandi. 858 00:30:50,440 --> 00:30:54,875 >> Neðst, ég er með allt fullt af valkostir, þar á meðal að byrja og 859 00:30:54,875 --> 00:30:55,840 stöðva hnappinn. 860 00:30:55,840 --> 00:30:59,450 Einnig, eins og innskot, það virðist vera galla í þessum forritum, þar sem þú 861 00:30:59,450 --> 00:31:03,720 getur í raun ekki séð að hefja eða hætta hnappinn nema þú halda Command eða Alt 862 00:31:03,720 --> 00:31:06,560 plús og zoom í, sem forvitinn sýnir þér fleiri hnappa. 863 00:31:06,560 --> 00:31:09,090 Svo bara FYI ef þú spilar með þetta heima. 864 00:31:09,090 --> 00:31:12,870 Nú ætla ég að smella á Start í bara stund, eftir að skilgreina seinkun á, 865 00:31:12,870 --> 00:31:16,810 eins, 200 millisekúndur hér, bara svo við getum séð hvað gerist. 866 00:31:16,810 --> 00:31:20,180 >> Svo ég halda því fram að þetta er visualization af fyrsta reiknirit 867 00:31:20,180 --> 00:31:23,730 þessir krakkar gerðu, kúla tagi, þar við skipti fólk par-vitur. 868 00:31:23,730 --> 00:31:27,490 Lykillinn innsýn í þessa sjónsköpun er að hæð bars 869 00:31:27,490 --> 00:31:30,510 táknar stærð tölu. 870 00:31:30,510 --> 00:31:32,210 Svo hærri sem stikan er, því stærri númer. 871 00:31:32,210 --> 00:31:33,680 Styttra sem stikan er, minni númer. 872 00:31:33,680 --> 00:31:38,630 Og ef þú tekur eftir, við erum að fara í gegnum fyrsta endurtekning af þessum reiknirit, 873 00:31:38,630 --> 00:31:42,620 skipta stór og lítil númer, þannig að lítill fjöldi kemur fyrst og 874 00:31:42,620 --> 00:31:44,280 stór tala fer til hægri. 875 00:31:44,280 --> 00:31:48,770 >> Og um leið og við fáum enda fylking margra fleiri tölur en sjö, við erum 876 00:31:48,770 --> 00:31:49,900 að fara að fara aftur til the byrjun. 877 00:31:49,900 --> 00:31:51,140 Og sjá þetta. 878 00:31:51,140 --> 00:31:54,860 Á lengst til vinstri, þessi litli er að fara að skipta til hliðar, og þetta 879 00:31:54,860 --> 00:31:56,010 ferli endurtekur. 880 00:31:56,010 --> 00:31:59,450 Nú fær þetta visualization fljótt leiðinlegt, svo láta mig fara á undan og hætta 881 00:31:59,450 --> 00:32:04,170 það, breyta tefja eitthvað miklu hraðar bara til að fá nú, tilfinningu fyrir 882 00:32:04,170 --> 00:32:05,060 Þetta reiknirit. 883 00:32:05,060 --> 00:32:07,840 >> Svo jafnvel þó að ég hef ferð það upp, þetta er eins og uppfærsla örgjörva minn, kaupa 884 00:32:07,840 --> 00:32:08,580 ný tölva. 885 00:32:08,580 --> 00:32:12,980 Ég hef ekki breyst minn reiknirit, en þú getur örugglega séð fleiri 886 00:32:12,980 --> 00:32:16,800 hætti en með mönnum, að stór númer eru freyðandi upp að ofan, 887 00:32:16,800 --> 00:32:20,900 og litlu númer eru vellandi niður á botn. 888 00:32:20,900 --> 00:32:22,390 Og nú þetta raðað hér. 889 00:32:22,390 --> 00:32:25,260 Og sem innskot, í reitum, það er bara sumir bókhald þar til 890 00:32:25,260 --> 00:32:28,010 hjálpa þér að telja hversu margir samanburð, eða hversu margir skiptasamningar hafa 891 00:32:28,010 --> 00:32:28,950 reyndar verið gert. 892 00:32:28,950 --> 00:32:30,750 >> Jæja, við skulum reyna einn af hinir sem við sáum. 893 00:32:30,750 --> 00:32:37,116 Leyfðu mér að smella á tegund kúla hér, og láta mig velja, og þetta allt vefsíðu 894 00:32:37,116 --> 00:32:38,936 er svolítið þrjótur. 895 00:32:38,936 --> 00:32:41,155 Skulum taka áhættu og keyra það aftur. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Þar við förum. 898 00:32:45,030 --> 00:32:47,180 Svo skulum gera val konar. 899 00:32:47,180 --> 00:32:49,140 Ég veit ekki hvers vegna valmynd birtist þarna. 900 00:32:49,140 --> 00:32:54,070 Skulum zoom í til að laga það padda, breyta þessu í 50. 901 00:32:54,070 --> 00:32:56,020 Ah, við skulum raunverulega gera sem mun hraðar. 902 00:32:56,020 --> 00:32:59,160 Fimm millisekúndur eða svo, og byrja. 903 00:32:59,160 --> 00:33:00,470 >> Svo er þetta val tagi. 904 00:33:00,470 --> 00:33:03,070 Svo aftur, hugsa um hvað við gerði með mönnum upp hér. 905 00:33:03,070 --> 00:33:08,490 Við fórum í gegnum fylking og valið minnsti þátturinn aftur, 906 00:33:08,490 --> 00:33:09,250 og aftur og aftur. 907 00:33:09,250 --> 00:33:11,110 Nú er ég halda því fram að enn var ansi slæmt. 908 00:33:11,110 --> 00:33:15,010 Það var samt n veldi, gefa eða taka, en það var, í hinum raunverulega heimi, dálítið 909 00:33:15,010 --> 00:33:18,280 hraðar, vegna þess að ég var örugglega að taka örlítið færri skrefum í hvert skipti. 910 00:33:18,280 --> 00:33:19,800 En við erum aðeins að tala hvað? 911 00:33:19,800 --> 00:33:21,830 Kannski 40 eða svo bars hér? 912 00:33:21,830 --> 00:33:23,200 Við erum ekki að tala 40 milljónir. 913 00:33:23,200 --> 00:33:27,430 Svo það er ekki alveg ljóst að mér að var örugglega mikil ávinningur. 914 00:33:27,430 --> 00:33:32,530 >> Leyfðu mér að fara nú aftur og breyta til okkar Þriðja algrím, sem var valið 915 00:33:32,530 --> 00:33:33,180 innsetning tagi. 916 00:33:33,180 --> 00:33:36,380 Og nú er það mjög þrjótur því valmynd í raun ætti ekki að vera þarna niðri. 917 00:33:36,380 --> 00:33:40,840 Svo nú að við munum fletta aftur upp hér og byrja þetta reiknirit. 918 00:33:40,840 --> 00:33:43,270 Whoop, byrja og hætta. 919 00:33:43,270 --> 00:33:47,160 Svo hefur þetta ein tegund af nokkuð mynstur við það, þar sem við erum aftur 920 00:33:47,160 --> 00:33:50,240 setja mennina, eða í þetta mál, súlurnar inn 921 00:33:50,240 --> 00:33:52,620 viðeigandi staðsetning þeirra. 922 00:33:52,620 --> 00:33:55,430 Og það er þegar gert áður Ég snéri. 923 00:33:55,430 --> 00:33:58,940 En þessi, of, í orði, er enn n ferningur. 924 00:33:58,940 --> 00:34:01,430 >> Svo skulum sjá hvort við getum ekki saman þetta segir. 925 00:34:01,430 --> 00:34:04,750 Ég ætla að fara á undan og bara til að gefa okkur konar sameiginlega leið að tala 926 00:34:04,750 --> 00:34:08,489 um þessa hluti, láttu mig kynna bara hluti af merki hér. 927 00:34:08,489 --> 00:34:12,480 Þú ert að fara að sjá eitthvað sem kallast stór O, vegna þess að það er bókstaflega a stór 928 00:34:12,480 --> 00:34:16,320 O. Og þetta er leið að tölva vísindamaður eða stærðfræðingur jafnvel notar 929 00:34:16,320 --> 00:34:19,230 að lýsa hlaupandi tími einhvers reiknirit. 930 00:34:19,230 --> 00:34:21,400 Hversu mörg skref tekur það í raun? 931 00:34:21,400 --> 00:34:25,080 >> Nú ætla ég að niðurlægja mig með rithönd mín hér í bara smá stund. 932 00:34:25,080 --> 00:34:29,020 En láta mig fara á undan og segja að þetta mun vera stór O hérna. 933 00:34:29,020 --> 00:34:33,610 Og láttu mig kynna eitt annað tákn, höfuðborg Omega. 934 00:34:33,610 --> 00:34:37,080 Omega er að fara að vera á móti, meginatriðum, af stór O. teknu tilliti til eftirfarandi stór O 935 00:34:37,080 --> 00:34:40,790 þýðir, í versta tilfelli, hversu mikinn tíma gæti einhver reiknirit taka, í 936 00:34:40,790 --> 00:34:43,480 hugtök af N, ómega er að fara að vera hversu mikinn tíma gæti það 937 00:34:43,480 --> 00:34:45,409 taka í besta tilfelli. 938 00:34:45,409 --> 00:34:48,090 Og við munum sjá hvað er átt við með besta mál í aðeins augnablik. 939 00:34:48,090 --> 00:34:49,940 >> Svo skulum byrja eitthvað einfalt. 940 00:34:49,940 --> 00:34:54,719 Leyfðu mér að byrja með línulegri leit. 941 00:34:54,719 --> 00:34:55,679 Svo ekki flokka. 942 00:34:55,679 --> 00:34:58,000 Við munum kalla þetta línulega leit. 943 00:34:58,000 --> 00:35:01,140 Og nú, gera a lítill borð út af þessu. 944 00:35:01,140 --> 00:35:06,600 Og nú, að því er varðar línuleg leit, í versta tilfelli, hversu mörg skref er 945 00:35:06,600 --> 00:35:11,770 það að fara að taka mig til að finna fjöldi handahófi val? 946 00:35:11,770 --> 00:35:14,540 Og það er n samtals hurðir eða n heildarfjölda. 947 00:35:14,540 --> 00:35:15,940 Versta tilfelli. 948 00:35:15,940 --> 00:35:18,800 Hversu mörg skref er ég að fara að hafa til að taka til að finna númerið 50 í fylki 949 00:35:18,800 --> 00:35:20,830 af n dyr? 950 00:35:20,830 --> 00:35:21,410 Og hvers vegna? 951 00:35:21,410 --> 00:35:23,680 Vegna þess að það gæti verið allt leið yfir á endanum. 952 00:35:23,680 --> 00:35:27,120 Svo mikið eins Jennifer fundur, sem númer 50 var alla leið yfir, svo í 953 00:35:27,120 --> 00:35:30,760 versta tilfelli línuleg leit er stór O n, munum við segja. 954 00:35:30,760 --> 00:35:33,430 >> Hvað um besta tilfelli, ef þú færð virkilega heppinn? 955 00:35:33,430 --> 00:35:36,200 Það er bara að fara að taka eitt skref, eða stöðug tala af skrefum. 956 00:35:36,200 --> 00:35:37,830 Þannig að við munum lýsa það sem 1. 957 00:35:37,830 --> 00:35:39,010 Þannig að þetta er nokkuð gott. 958 00:35:39,010 --> 00:35:41,210 Nú hvað ef við gerðum eitthvað eins tvöfaldur leit? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Svo tvöfaldur leit, í versta málið, tók hversu mikinn tíma? 961 00:35:47,846 --> 00:35:49,250 >> [INTERPOSING raddir] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. Malan: Svo í raun, ég heyrði það í nokkra staði. 963 00:35:51,310 --> 00:35:56,390 Svo það er í raun log n, gefa eða taka, því eins og við skipta lista í tvennt 964 00:35:56,390 --> 00:36:00,730 aftur, og aftur, og aftur, við erum fær að finna, að lokum, gildi, 965 00:36:00,730 --> 00:36:04,750 ef það er þarna, en það er a grípa. 966 00:36:04,750 --> 00:36:08,590 Hvað er ráð fyrir að við verðum að taka sem sjálfsögðum hlut að tvöfaldur leit? 967 00:36:08,590 --> 00:36:09,700 Það þarf að vera flokkaður. 968 00:36:09,700 --> 00:36:12,770 Það er ekki raðað, þú geta kljúfa málið í helmingur aftur og aftur, og þú 969 00:36:12,770 --> 00:36:15,490 getur farið til vinstri, og þú getur farið til hægri og þú getur farið til vinstri og hægri, en þú ert 970 00:36:15,490 --> 00:36:18,070 ekki að fara að finna stak ef listinn er ekki raðað því 971 00:36:18,070 --> 00:36:18,790 þú gætir missa það. 972 00:36:18,790 --> 00:36:22,120 Vegna leitandi þinni, fyrir að fara til vinstri eða hægri er að fara til að vera gölluð ef hún er 973 00:36:22,120 --> 00:36:23,420 örugglega ekki raðað. 974 00:36:23,420 --> 00:36:26,110 Svo er það eins konar falinn kostnaður að nota eitthvað eins og this. 975 00:36:26,110 --> 00:36:29,250 >> Nú, við skulum fara inn í flokka okkar reiknirit leita ekki - 976 00:36:29,250 --> 00:36:31,140 ó, reyndar skulum fara í þetta eftir autt. 977 00:36:31,140 --> 00:36:33,190 Binary leita í besta tilfelli? 978 00:36:33,190 --> 00:36:36,290 Það er líka 1 ef það gerist bara til að vera í mjög miðju í fylkinu, eða 979 00:36:36,290 --> 00:36:37,810 um miðja símaskránni. 980 00:36:37,810 --> 00:36:39,710 Nú skulum gera kúla konar. 981 00:36:39,710 --> 00:36:42,570 Svo aftur, nú erum við að slá inn konar, en ekki leit. 982 00:36:42,570 --> 00:36:47,220 >> Í versta tilfelli, hversu mörg skref gerði við krafa kúla tegund er að fara að taka? 983 00:36:47,220 --> 00:36:48,410 n veldi. 984 00:36:48,410 --> 00:36:49,200 Þannig að ég ætla að teikna það. 985 00:36:49,200 --> 00:36:51,710 Ooh, rithönd mín lítur jafnvel verri þegar það er spáð að stór. 986 00:36:51,710 --> 00:36:52,510 Allt í lagi. 987 00:36:52,510 --> 00:36:53,570 Svo það er n ferningur. 988 00:36:53,570 --> 00:36:59,460 Og í besta tilfelli konar kúla, hversu mörg skref er það að fara að taka? 989 00:36:59,460 --> 00:37:00,980 1, heyrði ég. 990 00:37:00,980 --> 00:37:01,760 >> Ræðumaður 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. Malan: n, heyrði ég. 992 00:37:03,286 --> 00:37:04,200 >> Ræðumaður 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. Malan: 2, ég heyrði. 994 00:37:05,010 --> 00:37:06,670 Ég heyri 3? 995 00:37:06,670 --> 00:37:07,080 Allt í lagi. 996 00:37:07,080 --> 00:37:11,390 Svo ég hef heyrt 1, n, 2, en við skulum velja í sundur að minnsta kosti fyrsta af þeim sem 997 00:37:11,390 --> 00:37:12,330 tillögur, 1. 998 00:37:12,330 --> 00:37:15,370 Það er ekki slæm eðlishvöt, vegna þess að það konar fylgir munstur. 999 00:37:15,370 --> 00:37:19,670 En ef það tekur bara 1 skref, hvernig í Heimurinn gæti ég halda því fram að listinn 1000 00:37:19,670 --> 00:37:22,900 er raðað, því ef ég er aðeins leyft að taka 1 skref, hvernig margir þættir 1001 00:37:22,900 --> 00:37:25,230 gæti ég athuga reyndar að vera viss? 1002 00:37:25,230 --> 00:37:28,270 Jæja, bara 1, sem þýðir að það er n mínus 1 atriði sem gæti verið út af 1003 00:37:28,270 --> 00:37:31,310 röð, og ég ætla bara að fara á trú eftir horfa á 1. þáttur sem 1004 00:37:31,310 --> 00:37:31,850 hlutur er raðað. 1005 00:37:31,850 --> 00:37:33,930 Svo 1 er ekki rétt hér. 1006 00:37:33,930 --> 00:37:35,710 Svo lítið, hversu margir þarf ég að horfa á? 1007 00:37:35,710 --> 00:37:36,680 >> [INTERPOSING raddir] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. Malan: n mínus 1, eða í raun, n, því að ég þarf að horfa á hverju 1009 00:37:40,160 --> 00:37:42,190 þáttur til að tryggja að það er ekki út af röð. 1010 00:37:42,190 --> 00:37:44,750 En aftur, munum við raða á öldu okkar hendur á smærri tölur og 1011 00:37:44,750 --> 00:37:47,100 ráð fyrir að, eins og n fær stór, þeir eru uninteresting samt. 1012 00:37:47,100 --> 00:37:48,380 Svo er það kúla tegund. 1013 00:37:48,380 --> 00:37:49,830 Og nú, við skulum gera þessa síðustu tvo. 1014 00:37:49,830 --> 00:37:53,520 Val tagi, og þá munum við gera innsetningu konar. 1015 00:37:53,520 --> 00:37:57,160 Og þá munum við blása þinni huga með eitthvað mikið 1016 00:37:57,160 --> 00:37:58,926 betri en allar þessar. 1017 00:37:58,926 --> 00:38:00,410 Allt í lagi. 1018 00:38:00,410 --> 00:38:04,700 >> Hvað er versta gangi tími konar val? 1019 00:38:04,700 --> 00:38:05,680 >> Ræðumaður 4: n ferningur. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. Malan: n veldi, ég heyra. 1021 00:38:06,710 --> 00:38:09,790 En hvers vegna n veldi, innsæi? 1022 00:38:09,790 --> 00:38:11,170 >> Ræðumaður 4: Þar sem við gerðum bara það. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. Malan: Vegna þess að við gerðum bara það. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Gott svar. 1026 00:38:13,380 --> 00:38:16,660 En innsæi, hvers vegna er val raða n veldi? 1027 00:38:16,660 --> 00:38:18,980 Hvað gerði við þurfum að gera aftur og aftur? 1028 00:38:18,980 --> 00:38:22,570 Við þurftum að halda skönnun í gegnum, eru þú minnstu, þú ert 1029 00:38:22,570 --> 00:38:24,020 lítill, þú ert minnstu. 1030 00:38:24,020 --> 00:38:27,480 Og veitt, við varúlfur fær til að taka n skref, þá n mínus 1, þá n mínus 2. 1031 00:38:27,480 --> 00:38:30,700 En ef þú góður af bæta þeim öllum upp, eða taka það á trú sem ég hef bætt við 1032 00:38:30,700 --> 00:38:34,810 þá upp fyrirfram, fáum við u.þ.b. n ferningur mínus sumum minni tölur. 1033 00:38:34,810 --> 00:38:36,730 Þannig að ég ætla að kalla þetta n ferningur. 1034 00:38:36,730 --> 00:38:39,530 En með tegund val á bestu ræða, hversu mörg skref er 1035 00:38:39,530 --> 00:38:40,632 að fara að taka mig? 1036 00:38:40,632 --> 00:38:41,840 >> Ræðumaður 5: [inaudible] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. Malan: Það er því miður enn n veldi, ekki satt? 1038 00:38:44,350 --> 00:38:49,590 Vegna þess að ef ég er að velja minnstu þáttur, og við höfðum sjö manns hér, 1039 00:38:49,590 --> 00:38:53,280 Ég veit bara, þegar ég fá til the mjög endir, að ég hef fundið minnstu 1040 00:38:53,280 --> 00:38:55,670 númer, hvar sem hann eða hún kann að hafa verið. 1041 00:38:55,670 --> 00:38:58,820 En hvernig finn ég næst minnsti fjöldi? 1042 00:38:58,820 --> 00:39:00,160 Ég verð að gera aðra sendingu. 1043 00:39:00,160 --> 00:39:04,810 Svo í besta tilfelli, hvað er inntak í val tagi? 1044 00:39:04,810 --> 00:39:07,830 Það er nú þegar konar lista, númer eitt, númer tvö, númer þrjú, númer fjögur. 1045 00:39:07,830 --> 00:39:08,600 En ég er í tölvu. 1046 00:39:08,600 --> 00:39:10,190 Ég get bara líta á einn hlutur í einu. 1047 00:39:10,190 --> 00:39:12,465 Ég get ekki raðað af taka skref aftur eins og manneskju og segja: 1048 00:39:12,465 --> 00:39:14,030 ooh, þetta lítur rétt. 1049 00:39:14,030 --> 00:39:17,580 >> Ég get bara dæma réttmæti í val konar með því að velja 1050 00:39:17,580 --> 00:39:18,370 minnsti fjöldi. 1051 00:39:18,370 --> 00:39:21,390 En jafnvel ef ég finn númer eitt fyrst, ef ég veit ekki neitt annað um 1052 00:39:21,390 --> 00:39:24,460 aðrar tölur, sem ég er ekki, allt sem ég veit að ég hef verið afhent fylki 1053 00:39:24,460 --> 00:39:27,930 eða setja af dyr bak við sem eru tölur, eina leiðin sem ég veit að einn 1054 00:39:27,930 --> 00:39:28,680 var minnsti? 1055 00:39:28,680 --> 00:39:32,440 Ef ég fæ alla leið hingað og átta, fjandinn, var einn örugglega minnstu. 1056 00:39:32,440 --> 00:39:34,870 >> En hvernig ég ákveða þá tveir er næsta lítill? 1057 00:39:34,870 --> 00:39:38,350 Með því að gera slíkt hið sama óhagkvæmni aftur og aftur. 1058 00:39:38,350 --> 00:39:42,210 Svo að lokum, með Innsetningarröðun, hvernig, í versta tilfelli, 1059 00:39:42,210 --> 00:39:44,990 gerði við segjum það virkar? 1060 00:39:44,990 --> 00:39:49,100 Það of er n ferningur. 1061 00:39:49,100 --> 00:39:53,020 Og hvernig óður með besta tilfelli? 1062 00:39:53,020 --> 00:39:56,282 Við munum fara að sem cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Við munum fylla í þessi auða næst, en fyrst láta mig leggja til að við 1064 00:40:00,090 --> 00:40:02,620 grundvallaratriðum gera betur en allt þetta, allt í lagi? 1065 00:40:02,620 --> 00:40:05,220 >> Svo hugsa fyrir sjálfan þig hvað innsetning tegund er að fara til vera. 1066 00:40:05,220 --> 00:40:06,910 Jæja, það var ekki mjög dramatísk, því að ég er sú eina 1067 00:40:06,910 --> 00:40:08,970 sem sá breytinguna. 1068 00:40:08,970 --> 00:40:09,620 Vá. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Svo hér höfum við nokkuð mismunandi sýning. 1071 00:40:12,615 --> 00:40:16,580 Ef ég zoom í hér, munt þú sjá að á vinstri við höfum kúla tegund, í 1072 00:40:16,580 --> 00:40:20,740 miðja höfum val konar, og á lengst til hægri, höfum við eitthvað við 1073 00:40:20,740 --> 00:40:23,380 hafa ekki horft á enn kallað sameinast einhverskonar. 1074 00:40:23,380 --> 00:40:26,080 En íhuga hvað við höfum verið gera hér svona langt í dag. 1075 00:40:26,080 --> 00:40:29,200 Þegar Jennifer kom fyrst upp á sviðinu, við fórum í gegnum array af tölum 1076 00:40:29,200 --> 00:40:33,750 aftur og aftur, með línulegri leit, og við fengum línuleg hlaupandi tími, stór O 1077 00:40:33,750 --> 00:40:35,100 af n, svo að segja. 1078 00:40:35,100 --> 00:40:41,000 >> Þegar við lítum nú í fyrstu viku flokki, þegar við höfðum skipta og sigra, 1079 00:40:41,000 --> 00:40:43,740 og við höfðum símaskrá ofsafenginn, og Jennifer, og við sameiginlega 1080 00:40:43,740 --> 00:40:47,500 skuldsett að lykill innsýn, sem var að endurtaka þig aftur og aftur með því 1081 00:40:47,500 --> 00:40:50,930 einhvern veginn að henda burt, hent, hent, helmingur af the vandamál, eða 1082 00:40:50,930 --> 00:40:55,320 almennt, deila vandamál í tvennt, og þá meðhöndla minni stykki af 1083 00:40:55,320 --> 00:40:59,630 vandamálið sem eðli jafngildi til annarra, við fengum einhvern veginn 1084 00:40:59,630 --> 00:41:00,910 grundvallaratriðum betur. 1085 00:41:00,910 --> 00:41:04,720 En með tegund kúla, með val tegund, með Innsetningarröðun, höfum við getur 1086 00:41:04,720 --> 00:41:06,560 engar slíkar innsýn sem Jennifer gerði. 1087 00:41:06,560 --> 00:41:10,220 Við nánast bara gekk aftur og fram a heild búnt af sinnum, og við 1088 00:41:10,220 --> 00:41:12,650 klip það svolítið, skipta í þessari röð, ef til vill 1089 00:41:12,650 --> 00:41:13,730 setja eða velja. 1090 00:41:13,730 --> 00:41:16,950 En í lok dagsins, ég gerði mikið af óþægilega göngu fram og til baka. 1091 00:41:16,950 --> 00:41:21,160 Við gerðum í raun ekki skiptimynt eitthvað Smart eins Jennifer gerði eins deila 1092 00:41:21,160 --> 00:41:22,040 og sigra. 1093 00:41:22,040 --> 00:41:25,620 >> Svo sameinast raða, hins, sem við mun ekki sjá fyrr en í næstu viku, það er að fara 1094 00:41:25,620 --> 00:41:29,540 að nýta sem lykill hugmynd með því að deila inntak, og þá halving, og þá 1095 00:41:29,540 --> 00:41:30,580 halving, og þá halving. 1096 00:41:30,580 --> 00:41:34,590 Og á hverjum endurtekning þeirrar lykkju, flokkun vinstri helming, og rétt 1097 00:41:34,590 --> 00:41:38,200 helming, þá vinstri helmingur af vinstri helming, og rétt helmingur af the vinstri, þá 1098 00:41:38,200 --> 00:41:40,990 vinstri helmingur af hægri hluta, og rétt helmingur af hægri helming. 1099 00:41:40,990 --> 00:41:42,840 Og endurtaka aftur og aftur. 1100 00:41:42,840 --> 00:41:46,170 >> Svo þú munt sjá þetta sjónrænt, en þetta er það sem bíður okkar í næstu viku. 1101 00:41:46,170 --> 00:41:49,760 Og almennt, þegar við hugsum lítið svolítið erfiðara á slíkum vanda. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Við höfum n ferningur til vinstri, n veldi í miðju, og n 1104 00:41:57,970 --> 00:41:59,400 log n til hægri. 1105 00:41:59,400 --> 00:42:00,590 Svo er það alvöru cliffhanger þinn. 1106 00:42:00,590 --> 00:42:02,040 Við munum sjá þig á mánudaginn. 1107 00:42:02,040 --> 00:42:05,163 >> [Applause]