1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [TÓNLIST spila] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. Malan: Þetta er CS50. 5 00:00:12,550 --> 00:00:14,612 Og þetta er upphaf viku þrjú. 6 00:00:14,612 --> 00:00:16,820 Þannig að við höfum fengið fullt af spennandi atriði sem þarf að ná í dag. 7 00:00:16,820 --> 00:00:20,160 A einhver fjöldi af tækifærum fyrir sjálfboðaliðar upp á sviðinu. 8 00:00:20,160 --> 00:00:22,780 Og að lokum, í dag er ekki um kóða yfirleitt. 9 00:00:22,780 --> 00:00:24,820 En það er um hugmyndir, og það er um reiknirit, 10 00:00:24,820 --> 00:00:28,420 og í raun koma aftur sum í kennslustundum lært af viku núll, 11 00:00:28,420 --> 00:00:31,910 þar muna, við kynna þessa monstrosity. 12 00:00:31,910 --> 00:00:33,880 Og lántökur innblástur frá því, til að byrja 13 00:00:33,880 --> 00:00:36,879 til að leysa sífellt flóknari vandamál algorithmically. 14 00:00:36,879 --> 00:00:38,420 En fyrst, a par af tilkynningum. 15 00:00:38,420 --> 00:00:42,020 Svo einn, ef þú vildi eins og til að taka þátt Starfsfólk CS50 og bekkjarfélagar í hádeginu 16 00:00:42,020 --> 00:00:44,670 á föstudaginn, bæði hér og í Cambridge, og í New Haven, 17 00:00:44,670 --> 00:00:48,060 skaltu fara á námskeið er website, þar sem URL er að finna. 18 00:00:48,060 --> 00:00:50,390 Fyrirlestur þessi miðvikudagur mun ekki vera hér í Sanders. 19 00:00:50,390 --> 00:00:53,610 Það verður að vera á netinu bara, svo lag í á vefsíðu CS50 er, 20 00:00:53,610 --> 00:00:55,850 hvort hér í Cambridge eða New Haven eins vel. 21 00:00:55,850 --> 00:00:58,110 >> Og þá vandamálið sett tvö er nú þegar í höndum þínum. 22 00:00:58,110 --> 00:01:03,067 Ef þú hefur ekki bætti enn leyfa mér að bjóða upp á mjög orðuð tillögu 23 00:01:03,067 --> 00:01:05,150 að, sérstaklega nú, eins og vandamálið setur fyrirfram, 24 00:01:05,150 --> 00:01:08,669 þú virkilega vilt að byrja núna, ef ekki notaði svolítið um helgina eða áður 25 00:01:08,669 --> 00:01:10,710 þegar þeir fara fyrst út á Fridays, vegna þess að þú munt 26 00:01:10,710 --> 00:01:14,380 finna að þeir eru ekki endilega fá lengri eða meira krefjandi fyrir 27 00:01:14,380 --> 00:01:14,950 SE. 28 00:01:14,950 --> 00:01:17,575 Ég held að þú munt komast að því að í Almennt, þeir hafa tilhneigingu til að taka u.þ.b. 29 00:01:17,575 --> 00:01:18,892 um sama tíma. 30 00:01:18,892 --> 00:01:20,850 En það fer örugglega á nemanda, og það 31 00:01:20,850 --> 00:01:22,880 veltur á hugarfari sem þú nálgast það. 32 00:01:22,880 --> 00:01:24,910 En ávallt, ætlar þú að fara að hlaupa upp á móti einhverju vegg, 33 00:01:24,910 --> 00:01:26,350 og þú ert að fara að lemja sumir galla, og þú ert bara 34 00:01:26,350 --> 00:01:27,950 ekki að fara að vera fær um að komast yfir það á einhverjum tímapunkti. 35 00:01:27,950 --> 00:01:31,380 Og það er gríðarlega mikils virði að vera fær um að stíga í burtu, koma aftur næsta dag, 36 00:01:31,380 --> 00:01:35,286 fara til skrifstofutíma birti á CS50 Ræddu eða þess háttar, til að raunverulega fá bannlista. 37 00:01:35,286 --> 00:01:36,160 Svo halda að í huga. 38 00:01:36,160 --> 00:01:40,830 Byrjar fyrsta og mögulegt er það besta sem þú getur gert. 39 00:01:40,830 --> 00:01:44,160 Svo er hér þar sem við byrjuðum bekknum, yfir í viku núll. 40 00:01:44,160 --> 00:01:47,441 Og getum við fengið sjálfboðaliða hér til að hjálpa mér að finna mics? 41 00:01:47,441 --> 00:01:47,940 OK. 42 00:01:47,940 --> 00:01:48,900 Standa upp nú þegar. 43 00:01:48,900 --> 00:01:50,080 Komdu upp. 44 00:01:50,080 --> 00:01:53,707 Giska á það er hvernig það er að fara að vinna. 45 00:01:53,707 --> 00:01:54,415 Hvað heitir þú? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 DAVID J. Malan: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Komdu upp. 49 00:01:57,910 --> 00:01:58,619 Gaman að hitta þig. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Gaman að hitta þig. 51 00:01:59,910 --> 00:02:02,772 DAVID J. Malan: Og þú værir hér með okkur í viku núll, að sjálfsögðu. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: Ég var. 53 00:02:03,028 --> 00:02:03,160 Ég var. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. Malan: Svo væri hægt að fara á undan og finna fyrir okkur Mike Smith, 55 00:02:05,868 --> 00:02:08,639 eins hratt og þú getur? 56 00:02:08,639 --> 00:02:10,639 Eins hratt og þú getur. 57 00:02:10,639 --> 00:02:13,756 Bókstaflega rífa vandamálið í tvennt eins og þú þarft að. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. Malan: Bókstaflega rífa vandamál í tvennt. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Oh. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Mjög gott. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. Malan: OK. 65 00:02:23,700 --> 00:02:24,200 Good. 66 00:02:24,200 --> 00:02:24,701 Þakka þér fyrir. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Mjög gott. 68 00:02:25,700 --> 00:02:26,210 OK. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. Malan: Og svo nú, þú hefur tálga það niður 70 00:02:27,610 --> 00:02:29,320 að helmingur the stærð af the vandamál. 71 00:02:29,320 --> 00:02:31,267 Nú erum við niður í fjórðung. 72 00:02:31,267 --> 00:02:33,475 Ert þú að borga eftirtekt til hvaða hlið við erum að halda? 73 00:02:33,475 --> 00:02:34,405 >> [Hlæjandi] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Já, think-- I 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. Malan: Hvað kafla erum við í? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: treflar, svo. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. Malan: OK. 78 00:02:39,941 --> 00:02:42,810 En Mike Smith er að fara að vera eftir Mufflers. 79 00:02:42,810 --> 00:02:44,130 So-- 80 00:02:44,130 --> 00:02:48,180 >> [Hlæjandi] 81 00:02:48,180 --> 00:02:48,742 >> Allt í lagi. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Hvar erum við að leita? 83 00:02:50,200 --> 00:02:52,049 DAVID J. Malan: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN ESTRADA: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 DAVID J. Malan: Nú erum við í skurðaðgerð. 86 00:02:54,760 --> 00:02:57,840 Nú, læknar. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- skulum fara með alvöru. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. Malan: Real. 91 00:03:00,970 --> 00:03:01,470 OK. 92 00:03:01,470 --> 00:03:03,700 Ef þú þarft alvöru. 93 00:03:03,700 --> 00:03:05,250 Nú, hvaða leið er Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Þessa leið. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. Malan: Hvaða leið? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Bíddu. 97 00:03:08,240 --> 00:03:08,790 M is-- satt? 98 00:03:08,790 --> 00:03:09,110 Við byrjuðum with-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. Malan: Já. 100 00:03:10,090 --> 00:03:10,650 Þeir eru eftir. 101 00:03:10,650 --> 00:03:11,430 Rétt þinn. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Já. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. Malan: Svo Mike er hér. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Hvað? 105 00:03:13,990 --> 00:03:14,665 >> [Hlæjandi] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Bad dæmi, krakkar. 108 00:03:18,330 --> 00:03:18,830 Sorry. 109 00:03:18,830 --> 00:03:21,610 DAVID J. Malan: Þetta mun kenna þú þarft að stökkva út úr stólnum. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Oh. 111 00:03:22,318 --> 00:03:22,890 Oh. 112 00:03:22,890 --> 00:03:23,390 Ég fékk þig. 113 00:03:23,390 --> 00:03:24,670 Ég fékk þig. 114 00:03:24,670 --> 00:03:25,170 Oh. 115 00:03:25,170 --> 00:03:25,669 Oh. 116 00:03:25,669 --> 00:03:26,812 Þetta is-- OK, fékk ég þig. 117 00:03:26,812 --> 00:03:27,520 Smith hérna? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. Malan: Smith, þakka þér. 119 00:03:28,894 --> 00:03:30,535 Svo ég ætla að halda áfram að leita upp Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Ó, já. 121 00:03:30,790 --> 00:03:31,340 Nei, nei, nei. 122 00:03:31,340 --> 00:03:31,600 Ó nei. 123 00:03:31,600 --> 00:03:31,940 Þetta er mitt. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. Malan: Oh, fékk Smith þú. 125 00:03:32,580 --> 00:03:33,415 OK. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Já, ég fékk Smith hérna. 127 00:03:34,040 --> 00:03:34,700 Því miður, krakkar. 128 00:03:34,700 --> 00:03:35,860 Ég hélt Michael-- við voru að leita að Michael. 129 00:03:35,860 --> 00:03:36,550 Sorry. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. Malan: Það er allt í lagi. 131 00:03:37,550 --> 00:03:39,950 Allt í lagi, nú erum við í Paccini og sona. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini og synir. 133 00:03:41,242 --> 00:03:43,158 DAVID J. Malan: Aðeins þú og ég erum í á þessu. 134 00:03:43,158 --> 00:03:44,050 OK. 135 00:03:44,050 --> 00:03:45,130 Finna okkur Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Smith. 137 00:03:45,830 --> 00:03:46,310 >> ALAN ESTRADA: Smith. 138 00:03:46,310 --> 00:03:46,750 >> DAVID J. Malan: Smith. 139 00:03:46,750 --> 00:03:47,728 Við erum í R fyrir rusl. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Slæm. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Þetta er að fara að taka smá stund. 143 00:03:52,480 --> 00:03:54,340 >> [Hlæjandi] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. Malan: Skór. 146 00:03:56,720 --> 00:03:58,080 Við erum í skóm. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Nú erum við gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. Malan: Nice. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [Hlæjandi] 151 00:04:03,620 --> 00:04:05,440 Oh, þetta er frábært. 152 00:04:05,440 --> 00:04:06,910 [Hlæjandi] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. Malan: Það er allt í lagi. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, þetta er gott. 156 00:04:11,365 --> 00:04:14,425 Ég held ekki að ég ætla að hafa PSAT verðandi eftir þetta. 157 00:04:14,425 --> 00:04:15,300 DAVID J. Malan: Good. 158 00:04:15,300 --> 00:04:16,078 Sporting. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporting. 160 00:04:17,036 --> 00:04:18,668 About, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 DAVID J. Malan: OK. 162 00:04:19,459 --> 00:04:21,600 Svo skulum rífa þetta í tvennt. 163 00:04:21,600 --> 00:04:22,270 Það er allt í lagi. 164 00:04:22,270 --> 00:04:25,606 Þetta endar illa samt, því Mike Smith mun ekki vera í gulu síðurnar. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. Malan: Nei, það er í lagi. 167 00:04:27,140 --> 00:04:28,930 En við skulum láta eins og hann er á þessari síðu. 168 00:04:28,930 --> 00:04:33,260 Svo nú hefur þú tálga vandamál niður að einni síðu, og við fundum Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Uppörvandi] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Allt í lagi þakka þér. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 OK. 174 00:04:41,200 --> 00:04:43,646 Það var ótrúlega. 175 00:04:43,646 --> 00:04:45,954 En það var samt hraðar en línuleg leit, 176 00:04:45,954 --> 00:04:47,870 þar sem við byrjum á upphafi bókar, 177 00:04:47,870 --> 00:04:51,210 og við færa leið okkar frá vinstri til hægri, loksins að leita að Mike Smith. 178 00:04:51,210 --> 00:04:53,540 Og svo, ef símaskrá hafði kannski 1.000 síður, 179 00:04:53,540 --> 00:04:56,300 kannski það hefði tekið US 10 eða svo page tár. 180 00:04:56,300 --> 00:04:59,380 >> En þú gætir hafa skuldsett snert forsendu 181 00:04:59,380 --> 00:05:03,602 á allt það, sem er að segja að síminn bóka fyrirfram var það? 182 00:05:03,602 --> 00:05:04,310 Áhorfendur: Raðað. 183 00:05:04,310 --> 00:05:05,000 DAVID J. Malan: Það er flokkaður. 184 00:05:05,000 --> 00:05:05,160 Ekki satt? 185 00:05:05,160 --> 00:05:07,909 Það er raðað í stafrófsröð, svo að allir þeir nöfn og númer 186 00:05:07,909 --> 00:05:11,230 eru flokkuð frá A er til Z er, og í stafrófsröð á milli. 187 00:05:11,230 --> 00:05:13,100 En í dag, við biðjum nú spurningin, vel, 188 00:05:13,100 --> 00:05:16,170 hvernig var Regin eða síminn fyrirtæki fá það inn í þessi ríki? 189 00:05:16,170 --> 00:05:19,560 >> Vegna þess að það er eitt að nýta sú forsenda, og því, 190 00:05:19,560 --> 00:05:22,570 leysa vandamál með að reiknirit skilvirkari. 191 00:05:22,570 --> 00:05:24,900 En við aldrei raunverulega spurði í viku núll, vel, 192 00:05:24,900 --> 00:05:27,790 hversu mikið var það kostnaður Regin eða einhver annar 193 00:05:27,790 --> 00:05:29,620 að fá að símaskrána í raðaða röð? 194 00:05:29,620 --> 00:05:29,780 >> Ekki satt? 195 00:05:29,780 --> 00:05:31,529 Það skiptir ekki máli ef horfa upp Mike Smith 196 00:05:31,529 --> 00:05:35,190 er frábær fljótur, ef það tekur þig að ári til að raða síðum í upphafi. 197 00:05:35,190 --> 00:05:35,690 Ekki satt? 198 00:05:35,690 --> 00:05:38,620 Þú might eins og heilbrigður bara sigta í slembiraðaðri símaskránni, 199 00:05:38,620 --> 00:05:40,690 ef það er að fara að vera frábær dýrt að flokka það. 200 00:05:40,690 --> 00:05:42,350 Svo ef við getum haft aðra sjálfboðaliða. 201 00:05:42,350 --> 00:05:46,350 Við skulum taka a líta upp hér á hvernig við might-- koma á up-- hvernig 202 00:05:46,350 --> 00:05:48,100 við gætum farið um flokkun þessara. 203 00:05:48,100 --> 00:05:51,990 >> Og ef Jordan gæti reyndar tengja okkur upp hér á sviðinu. 204 00:05:51,990 --> 00:05:55,100 Komdu upp fyrir réttlátur a augnablik. 205 00:05:55,100 --> 00:05:56,359 Hvað heitir þú? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. Malan: Caroline, koma á upp. 208 00:05:58,691 --> 00:06:02,070 Og þú munt vera tengdur af mér og Jórdaníu hér. 209 00:06:02,070 --> 00:06:03,800 Caroline, þakka þér. 210 00:06:03,800 --> 00:06:04,300 Allt í lagi. 211 00:06:04,300 --> 00:06:08,330 Svo það sem við höfum hér fyrir Caroline er 26 blár bækur 212 00:06:08,330 --> 00:06:10,747 sem FAS notar til að stjórna ákveðin endanleg próf. 213 00:06:10,747 --> 00:06:13,330 Þetta eru að fá erfitt að finna, en það sem við höfum gert í fyrirfram 214 00:06:13,330 --> 00:06:15,800 er að við höfum sett nafn einhvers framan á öllum þessum, 215 00:06:15,800 --> 00:06:18,133 en við höfum haldið það einfalt með þá setja út fullt nafn. 216 00:06:18,133 --> 00:06:22,720 Þannig að við myndum setja mann með nafni L, D, J, B, alla leið A í gegnum Z, 217 00:06:22,720 --> 00:06:24,090 en þeir eru í handahófskenndri röð. 218 00:06:24,090 --> 00:06:26,890 Og svo ef þú vilt tala þínum leið í gegnum vandamál sem þú 219 00:06:26,890 --> 00:06:31,620 gera það, getur þú farið á undan og raða þeim fyrir okkur, frá A til Z. 220 00:06:31,620 --> 00:06:34,070 >> Áhorfendur: OK, svo er L eins, miðju. 221 00:06:34,070 --> 00:06:35,050 C er farin. 222 00:06:35,050 --> 00:06:42,410 B. J áður L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. Malan: Haltu sem hélt í eina sekúndu. 224 00:06:45,140 --> 00:06:48,910 Vegna þess að annars, þetta er aðeins áhugavert að þér, mér, og Jórdaníu. 225 00:06:48,910 --> 00:06:49,724 Það sem við förum. 226 00:06:49,724 --> 00:06:50,640 Áhorfendur: [inaudible]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. Malan: OK. 229 00:06:58,090 --> 00:06:59,310 Hvað ertu að gera? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M kemur eftir O. 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. Malan: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. Malan: O, Good. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> DAVID J. Malan: E, F. Já. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V. 237 00:07:07,620 --> 00:07:10,689 >> DAVID J. Malan: V, T, U, V. Svo það lítur út eins og þú ert making-- halda áfram. 238 00:07:10,689 --> 00:07:12,730 Það lítur út eins og þú ert að gera stór stafli hérna, 239 00:07:12,730 --> 00:07:13,910 og góður af a stór stafli þarna. 240 00:07:13,910 --> 00:07:16,230 Svo fyrsta hluta stafrófinu, seinni hluta stafrófsins. 241 00:07:16,230 --> 00:07:16,460 OK. 242 00:07:16,460 --> 00:07:16,960 Good. 243 00:07:16,960 --> 00:07:19,680 Tegund skipta vandamál í tvennt. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Já. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. Malan: OK. 247 00:07:22,980 --> 00:07:25,070 K. Svo þú ert góður að velja þá einn eftir annan, 248 00:07:25,070 --> 00:07:27,620 setja það annaðhvort vinstri eða hægri, eða Z er að fara á gólfið. 249 00:07:27,620 --> 00:07:28,012 OK. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z er að gerast á gólfinu. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. Malan: OK. 252 00:07:29,360 --> 00:07:30,920 Y er að fara á gólfið. 253 00:07:30,920 --> 00:07:31,735 Nú getum við sett X. 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 DAVID J. Malan: G er að fara til vinstri. 256 00:07:33,700 --> 00:07:36,017 S er að fara rétt. 257 00:07:36,017 --> 00:07:37,642 Allt í lagi, A er að fara alla leið til vinstri. 258 00:07:37,642 --> 00:07:38,790 >> CAROLINE: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> DAVID J. Malan: Nú, gott. 260 00:07:39,873 --> 00:07:43,260 Við höfum fengið A, B, C. W er að fara þarna niður. 261 00:07:43,260 --> 00:07:45,566 Allt í lagi, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, J. 263 00:07:46,611 --> 00:07:47,860 DAVID J. Malan: H, I, J. Good. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: Í miðju, ég er gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. Malan: OK. 266 00:07:50,000 --> 00:07:52,375 Svo nú erum við að fara að eins konar af sameinast þessar mismunandi hrúgur. 267 00:07:52,375 --> 00:08:00,730 Svo A gegnum C, þá get ég séð D, og E, og F, og G, og H, og I. Nice. 268 00:08:00,730 --> 00:08:05,540 J, K. Og þá, þetta stafli er hvolfi, en það er allt í lagi. 269 00:08:05,540 --> 00:08:06,040 Viss. 270 00:08:06,040 --> 00:08:07,240 Við getum skera nokkrar horn. 271 00:08:07,240 --> 00:08:07,950 OK. 272 00:08:07,950 --> 00:08:10,530 Og þá þurfum við W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Já. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. Malan: Excellent. 275 00:08:11,880 --> 00:08:14,122 Svo stór þakka þér að Caroline fyrir flokkun þessara. 276 00:08:14,122 --> 00:08:15,030 >> [Uppörvandi] 277 00:08:15,030 --> 00:08:17,287 >> Þakka þér fyrir. 278 00:08:17,287 --> 00:08:18,120 Þakka þér kærlega. 279 00:08:18,120 --> 00:08:22,910 Svo nú skulum við íhuga um stund hvernig Caroline gekk um, gjörði það, 280 00:08:22,910 --> 00:08:26,040 og hvað nákvæmlega við gátu to-- hvernig við 281 00:08:26,040 --> 00:08:28,409 gátu til að leysa það vandamál þegar við vorum bara 282 00:08:28,409 --> 00:08:29,950 gefið a heild búnt af handahófi aðföngum. 283 00:08:29,950 --> 00:08:31,610 >> Jæja, það lítur út eins og það var a hluti af a kerfi þar? 284 00:08:31,610 --> 00:08:32,110 Hægri. 285 00:08:32,110 --> 00:08:34,495 Svo fyrri bréfum í stafrófinu, hún 286 00:08:34,495 --> 00:08:37,120 var að setja til vinstri, og síðar bréf í stafrófinu, 287 00:08:37,120 --> 00:08:38,270 hún var að setja í hægri. 288 00:08:38,270 --> 00:08:40,500 Og um leið og hún fann sumir aðlægan bréf, sjálfur 289 00:08:40,500 --> 00:08:43,124 að fara við hliðina á hvort öðru, hún myndi setja þá í röð. 290 00:08:43,124 --> 00:08:46,750 Og svo við höfðum eins konar þessir litlu hrúgur af flokkaður aðföngum viðburður. 291 00:08:46,750 --> 00:08:50,540 >> Og svo er það alveg eins og það Flest okkar menn myndu gera. 292 00:08:50,540 --> 00:08:53,530 Við viljum konar sigta í gegnum það, og við myndum konar hafa kerfi. 293 00:08:53,530 --> 00:08:56,930 En það gæti verið erfitt að skrifa það niður í formúlu per se. 294 00:08:56,930 --> 00:08:59,010 Það var aðeins meira lífræn en það. 295 00:08:59,010 --> 00:09:02,560 Svo við skulum sjá hvort við getum nú bundið vandamálið með færri aðföngum. 296 00:09:02,560 --> 00:09:05,170 >> Í stað þess að 26, við skulum gera eitthvað sem færri 297 00:09:05,170 --> 00:09:09,890 með bara segja, sjö, á bak þessar hurðir, svo að segja. 298 00:09:09,890 --> 00:09:11,300 Eru bara sjö tölur? 299 00:09:11,300 --> 00:09:15,240 Og ef markmiðið nú vegar er að finna gildi, 300 00:09:15,240 --> 00:09:17,850 við skulum sjá hversu duglegur við getum farið að gera þetta. 301 00:09:17,850 --> 00:09:22,460 Og við skulum sjá hvort við getum núna byrja að beita nokkrar tölur, 302 00:09:22,460 --> 00:09:26,310 eða sumir formúlur sem lýsa skilvirkni bókinni okkar sími 303 00:09:26,310 --> 00:09:31,060 reiknirit, exam bók reiknirit okkar, og almennt, að finna upplýsingar. 304 00:09:31,060 --> 00:09:34,770 >> Svo fyrir þetta, láta mig fara á undan, og á snertiskjánum hérna, 305 00:09:34,770 --> 00:09:41,100 setja upp a vefur flettitæki sem hefur nákvæmlega þessi sjö hurðir. 306 00:09:41,100 --> 00:09:46,670 Og ef við gætum fengið eitt annað sjálfboðaliða til að koma á hérna, 307 00:09:46,670 --> 00:09:48,480 Ég hef sett þessar sömu dyr hérna. 308 00:09:48,480 --> 00:09:49,170 Quick sjálfboðaliði. 309 00:09:49,170 --> 00:09:51,130 >> Þessi one-- demo eru að fara að hraðari og fljótari núna. 310 00:09:51,130 --> 00:09:51,600 Koma niður. 311 00:09:51,600 --> 00:09:52,308 Hvað heitir þú? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> DAVID J. Malan: Trevor? 314 00:09:53,998 --> 00:09:55,770 Allt í lagi, Trevor, koma niður. 315 00:09:55,770 --> 00:09:59,212 Svo Trevor hefur boðist hér til gera svipuð vandamál, en sá sem er 316 00:09:59,212 --> 00:10:02,170 þrengri að umfangi, og það er að fara til að leyfa okkur að reyna að móta nú 317 00:10:02,170 --> 00:10:03,970 aðferð til að flokka þessar tölur. 318 00:10:03,970 --> 00:10:05,500 >> Svo Trevor, gaman að hitta þig. 319 00:10:05,500 --> 00:10:08,720 Svo hér er fylki, svo að tala, lista yfir sjö hurðir. 320 00:10:08,720 --> 00:10:10,327 Fara á undan og finna okkur númer 50. 321 00:10:10,327 --> 00:10:12,410 Og þá eftir því, segðu okkur hvernig þú fannst það. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Ætti be-- allt í lagi. 324 00:10:20,040 --> 00:10:21,945 Já, þetta er einn hér? 325 00:10:21,945 --> 00:10:24,680 Uh-ó. 326 00:10:24,680 --> 00:10:25,560 OK. 327 00:10:25,560 --> 00:10:26,680 Þú smelltir þessari. 328 00:10:26,680 --> 00:10:28,690 Good. 329 00:10:28,690 --> 00:10:29,780 >> Og gott. 330 00:10:29,780 --> 00:10:30,970 Nú þú smelltir þessari. 331 00:10:30,970 --> 00:10:34,060 Og láta mig gefa þér hljóðnema, svo að þú hafir það í bara smá stund. 332 00:10:34,060 --> 00:10:37,000 Fara á undan og smelltu á í næsta húsi sem þú ætlar. 333 00:10:37,000 --> 00:10:39,812 Já, gott. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Get ég unclick dyr? 335 00:10:41,020 --> 00:10:42,620 DAVID J. Malan: Nei, þú getur ekki unclick. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Þetta einn. 338 00:10:43,974 --> 00:10:45,640 DAVID J. Malan: Hvar viltu fara? 339 00:10:45,640 --> 00:10:46,410 Hver þeirra? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Það eitt. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. Malan: No. 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Þetta einn. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. Malan: Já. 345 00:10:49,020 --> 00:10:49,700 Það var gott. 346 00:10:49,700 --> 00:10:50,380 Allt í lagi. 347 00:10:50,380 --> 00:10:53,900 Svo það var reiknirit eða aðferð til að gera þetta, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Ég fór bara í gegnum hurðir fyrr en ég fann 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. Malan: OK. 350 00:10:56,940 --> 00:10:58,150 Excellent reiknirit. 351 00:10:58,150 --> 00:10:59,540 Svo er það í lagi. 352 00:10:59,540 --> 00:11:03,120 Því að í raun, ef ég sýna hvað er á bak við þessar tvær aðrar hurðir, hvað 353 00:11:03,120 --> 00:11:06,954 við munum finna hér er að við höfum aðeins handahófi inntak. 354 00:11:06,954 --> 00:11:08,870 Svo sem var í raun eins og góð og þú gætir fengið. 355 00:11:08,870 --> 00:11:12,509 Og í raun, fengið þér betri en tæmandi leita á ýmiss, 356 00:11:12,509 --> 00:11:15,300 vegna þess að það hefði verið mjög óheppinn ef þú hefðir högg fjölda 357 00:11:15,300 --> 00:11:16,604 50 á allra síðustu dyrnar. 358 00:11:16,604 --> 00:11:18,520 En hvað ef við staðinn gaf þér forsendu. 359 00:11:18,520 --> 00:11:20,630 Ég geri ráð konar allt þessar hurðir kring, 360 00:11:20,630 --> 00:11:23,500 þannig að þú hefur tölur raðað í þetta sinn, 361 00:11:23,500 --> 00:11:29,730 en í þetta skiptið það er í raun a different-- þetta sinn, 362 00:11:29,730 --> 00:11:32,640 það er í raun raðað fyrir þig. 363 00:11:32,640 --> 00:11:35,380 Og nú markmiðið hendi er að slá númerið 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. Malan: Hvað er reiknirit þinn að fara að vera? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Jæja, ef það er raðað, það er annað hvort að fara 367 00:11:39,628 --> 00:11:42,710 að be-- ef stærsta til stærsta, niður, verður það að vera sá fyrsti, 368 00:11:42,710 --> 00:11:44,751 eða ef það er hið gagnstæða, það verður það síðasta. 369 00:11:44,751 --> 00:11:48,897 Þannig að ég ætla bara að tappa þessa hurð, og þá bara tappa síðustu dyrnar. 370 00:11:48,897 --> 00:11:49,980 DAVID J. Malan: Excellent. 371 00:11:49,980 --> 00:11:50,270 Allt í lagi. 372 00:11:50,270 --> 00:11:51,150 Svo fundum fjölda 50. 373 00:11:51,150 --> 00:11:52,970 Svo um leið og þú vissir þeir voru flokkuð, við 374 00:11:52,970 --> 00:11:55,040 voru fær um að nýta þessa forsendu. 375 00:11:55,040 --> 00:11:57,040 Svo þeir eru of mikið eins og símaskrá dæmi. 376 00:11:57,040 --> 00:11:59,540 Um leið og þú hefur, jafnvel með lítið vandamál eins og þetta, 377 00:11:59,540 --> 00:12:02,380 inntak pre-raðað, við getum í raun að finna gildi að öllum líkindum 378 00:12:02,380 --> 00:12:03,130 skilvirkari. 379 00:12:03,130 --> 00:12:05,800 >> Og ég var ekki að segja þér ef það var flokkaður lítil og stór, eða stór til lítil, 380 00:12:05,800 --> 00:12:08,080 og svo það var mjög sanngjarnt til að byrja á annan endann eða öðrum 381 00:12:08,080 --> 00:12:09,750 að í raun finna þessi markgildi. 382 00:12:09,750 --> 00:12:11,400 Svo þakka að Trevor eins og heilbrigður. 383 00:12:11,400 --> 00:12:13,260 Og ég ætla að propose-- fallega gert. 384 00:12:13,260 --> 00:12:16,960 Við höfum smá bút, reyndar, það er meðal uppáhalds augnablikum okkar í CS50, 385 00:12:16,960 --> 00:12:19,700 þar stundum þessar kynningar ekki alveg að fara samkvæmt áætlun. 386 00:12:19,700 --> 00:12:22,050 Og reyndar núna, ég dreginn upp rangt tengi 387 00:12:22,050 --> 00:12:23,508 sem á að nota snertiskjáinn. 388 00:12:23,508 --> 00:12:24,660 Svo það var mér að kenna þar. 389 00:12:24,660 --> 00:12:26,600 >> Þannig að þetta mun gera fyrir myndband á næsta ári eins og 390 00:12:26,600 --> 00:12:28,570 hvers vegna ég var að smella á skjánum mínum. 391 00:12:28,570 --> 00:12:31,390 En við skulum taka a fljótur líta á það sem gerðist á síðasta ári 392 00:12:31,390 --> 00:12:34,770 með Jay, kom sér, mikið eins Trevor hér, bauðst, 393 00:12:34,770 --> 00:12:39,380 og í þessari stuttu myndband, munt þú sjá hvernig þetta sama kynningu ekki alveg 394 00:12:39,380 --> 00:12:41,074 sýna sömu kennslustundum lært. 395 00:12:41,074 --> 00:12:41,740 [Vídeó spilun] 396 00:12:41,740 --> 00:12:45,360 -Öll Ég vil að þú að gera núna er að finna fyrir mig, og fyrir okkur, 397 00:12:45,360 --> 00:12:51,674 í raun, fjölda 50 eitt skref í einu. 398 00:12:51,674 --> 00:12:52,450 >> -The Númer 50? 399 00:12:52,450 --> 00:12:53,190 >> -The Númer 50. 400 00:12:53,190 --> 00:12:55,356 Og þú geta sýna hvað er á bak við hvert af þessum hlerum 401 00:12:55,356 --> 00:12:58,540 einfaldlega með því að snerta það með fingri. 402 00:12:58,540 --> 00:13:00,910 Fari það. 403 00:13:00,910 --> 00:13:02,870 >> [Hlæjandi] 404 00:13:02,870 --> 00:13:03,806 >> [END spilun] 405 00:13:03,806 --> 00:13:05,430 DAVID J. Malan: Svo að gekk mjög vel. 406 00:13:05,430 --> 00:13:06,796 Þeir voru óflokkaðar hurðir. 407 00:13:06,796 --> 00:13:08,670 Og Jay, að sjálfsögðu, fann það allt of fljótt. 408 00:13:08,670 --> 00:13:12,910 Trevor gerði miklu betur í skilmálum teachable stund, 409 00:13:12,910 --> 00:13:15,850 svo að segja, á þessu ári í taka lengri tíma að finna það. 410 00:13:15,850 --> 00:13:17,950 Auðvitað, þá gáfum Jay annað tækifæri, 411 00:13:17,950 --> 00:13:20,320 þar sem við raðað dyr, bara eins og við gerðum fyrir Trevor, 412 00:13:20,320 --> 00:13:22,300 og Trevor gerði frábær vel að þessu sinni. 413 00:13:22,300 --> 00:13:26,124 En Jay gerði það helmingi fljótt. 414 00:13:26,124 --> 00:13:26,790 [Vídeó spilun] 415 00:13:26,790 --> 00:13:29,650 -The Markmiðið er nú einnig finna okkur númer 50, 416 00:13:29,650 --> 00:13:33,030 en gera það algorithmically og segðu okkur hvernig þú ert að fara um það. 417 00:13:33,030 --> 00:13:33,660 >> -OK. 418 00:13:33,660 --> 00:13:35,604 >> -Og Ef þú finnur það, halda þér myndina. 419 00:13:35,604 --> 00:13:37,228 Ef þú finnur ekki það, þú gefur það aftur. 420 00:13:37,228 --> 00:13:38,044 >> -Man. 421 00:13:38,044 --> 00:13:38,860 >> -OH! 422 00:13:38,860 --> 00:13:40,800 >> - [Inaudible] OK. 423 00:13:40,800 --> 00:13:46,236 Þannig að ég ætla að athuga enda fyrst að ákveða hvort there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Applause] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [END spilun] 427 00:13:55,729 --> 00:13:56,520 DAVID J. Malan: OK. 428 00:13:56,520 --> 00:13:59,760 Svo flokkun dyr greinilega leiðir til meiri skilvirkni. 429 00:13:59,760 --> 00:14:01,680 Og svo, tvisvar eins hratt er það sem ég þýddi það. 430 00:14:01,680 --> 00:14:03,270 Og svo Jay fékk heppinn bæði skiptin. 431 00:14:03,270 --> 00:14:06,685 Og hann fékk einnig heppinn í því síðasta ári, pantaði ég nokkrar Blu-geisli diskur 432 00:14:06,685 --> 00:14:07,560 að í raun að gefa út. 433 00:14:07,560 --> 00:14:09,768 Fyrirgefðu þessu ári, við ekki hafa það sama, Trevor. 434 00:14:09,768 --> 00:14:11,540 En betra samt var fyrir nokkrum árum. 435 00:14:11,540 --> 00:14:14,820 Og sumir af þú might vita þetta náungi, Sean, sem hann var í CS50, 436 00:14:14,820 --> 00:14:17,780 var mótmælt með nákvæmlega Sama vandamál, að vísu í SD, 437 00:14:17,780 --> 00:14:19,360 eins og þú munt fljótlega sjá, aftur í dag. 438 00:14:19,360 --> 00:14:22,622 Og þú munt komast að því að ekki aðeins var hann taka aðeins lengri tíma en Jay, 439 00:14:22,622 --> 00:14:25,580 aðeins lengur en Trevor, það var reyndar þetta frábæra tækifæri 440 00:14:25,580 --> 00:14:29,820 til að taka þátt næstum alla í mannfjöldi a la verðið er rétt, hvetja 441 00:14:29,820 --> 00:14:31,889 honum að finna fjölda sem við vorum að leita að. 442 00:14:31,889 --> 00:14:32,930 Skulum. taka a fljótur líta. 443 00:14:32,930 --> 00:14:33,320 >> [Vídeó spilun] 444 00:14:33,320 --> 00:14:33,820 >> -OK. 445 00:14:33,820 --> 00:14:36,680 Svo þitt verkefni hér, Sean, er eftirfarandi. 446 00:14:36,680 --> 00:14:40,860 Ég hef falið á bak við þessar hurðir fjöldi sjö. 447 00:14:40,860 --> 00:14:45,120 En matur burt í sumum þessara hurðir sem eru önnur neikvæðar tölur. 448 00:14:45,120 --> 00:14:47,500 Og markmið þitt er að hugsa af þessum efstu röð af tölum 449 00:14:47,500 --> 00:14:50,390 sem bara fjölda, eða bara röð af stykki af pappír 450 00:14:50,390 --> 00:14:51,510 með tölur á bak við þá. 451 00:14:51,510 --> 00:14:55,540 Og markmið þitt er, aðeins að nota efst array hér, finna mér númer sjö. 452 00:14:55,540 --> 00:14:58,570 Og við erum svo að fara að gagnrýna hvernig þú ferð að gera það. 453 00:14:58,570 --> 00:14:59,070 -Allt í lagi. 454 00:14:59,070 --> 00:15:00,850 -Find Okkur Talan sjö, takk. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Nei 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Fimm, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Hlæjandi] 461 00:15:24,770 --> 00:15:25,910 >> Það er ekki bragð spurning. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Einn. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Hlæjandi] 466 00:15:34,695 --> 00:15:37,861 Á þessum tímapunkti, skora er ekki mjög gott, svo þú might eins og heilbrigður að halda áfram. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Þrjú. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Hlæjandi] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Haltu áfram. 473 00:15:47,774 --> 00:15:50,690 Frankly, ég get ekki annað en furða það sem þú ert jafnvel að hugsa um, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Hlæjandi] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Aðeins efsta röð, svo þú hefur fengið þrjú vinstri. 477 00:15:55,020 --> 00:15:56,200 Svo að finna mér sjö. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Hlæjandi] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Seven. 484 00:16:26,946 --> 00:16:28,780 >> [Applause] 485 00:16:28,780 --> 00:16:29,426 >> Allt í lagi. 486 00:16:29,426 --> 00:16:30,360 >> [END spilun] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. Malan: Svo við gátum horfa þetta allan daginn. 488 00:16:31,840 --> 00:16:34,090 Og auðvitað, sum demo þessu ári kannski 489 00:16:34,090 --> 00:16:36,330 mun nú endað í næsta video ári eins og heilbrigður. 490 00:16:36,330 --> 00:16:39,040 Svo nú skulum raunverulega leggja áherslu á reiknirit 491 00:16:39,040 --> 00:16:42,140 hér, og sjá hvort við getum ekki nú byrja að móta 492 00:16:42,140 --> 00:16:46,650 hvernig við getum farið um að fá gögn okkar í þessu ástandi að það er raðað, 493 00:16:46,650 --> 00:16:50,054 svo að lokum, getum við í raun leita það á skilvirkari hátt. 494 00:16:50,054 --> 00:16:52,470 Og jafnvel þó að við erum að fara að nota nokkuð lítið gagnagrunna, 495 00:16:52,470 --> 00:16:54,511 eins átta tölurnar við hafa hér á borð, 496 00:16:54,511 --> 00:16:58,230 lokum þessir sömu hugmyndir gæti átt 1.000 aðföngum, milljón inntak, 497 00:16:58,230 --> 00:17:02,100 4 milljarða inntak, því reiknirit eru að fara að vera í grundvallaratriðum sú sama. 498 00:17:02,100 --> 00:17:05,359 >> Og svo er þetta síðasta vor tækifæri fyrir sjálfboðaliða í dag, 499 00:17:05,359 --> 00:17:09,790 en kannski helst koma einn, sem við þurfum átta sjálfboðaliða 500 00:17:09,790 --> 00:17:12,960 að koma upp og ganga okkur í gegnum Ferlið flokkun hvað mun brátt 501 00:17:12,960 --> 00:17:15,212 vera á þessum tónlist stendur hér. 502 00:17:15,212 --> 00:17:16,170 Leyfðu mér að byrja aftur hér. 503 00:17:16,170 --> 00:17:19,692 >> Svo einn í turquoise-- græna er það? 504 00:17:19,692 --> 00:17:21,130 Ert þú að fremja? 505 00:17:21,130 --> 00:17:21,630 Two. 506 00:17:21,630 --> 00:17:23,069 Koma niður. 507 00:17:23,069 --> 00:17:23,569 OK. 508 00:17:23,569 --> 00:17:24,420 Þrjú. 509 00:17:24,420 --> 00:17:25,400 Four. 510 00:17:25,400 --> 00:17:27,247 Láta me-- OK, fimm. 511 00:17:27,247 --> 00:17:28,830 Þú ert að vera tilnefndur af vini þínum. 512 00:17:28,830 --> 00:17:31,340 Sex, sjö og átta. 513 00:17:31,340 --> 00:17:32,130 Komdu upp. 514 00:17:32,130 --> 00:17:32,630 Allt í lagi. 515 00:17:32,630 --> 00:17:33,190 Þakka þér kærlega fyrir. 516 00:17:33,190 --> 00:17:33,689 Komdu upp. 517 00:17:33,689 --> 00:17:34,790 Komdu upp. 518 00:17:34,790 --> 00:17:35,330 >> Allt í lagi. 519 00:17:35,330 --> 00:17:38,890 Svo það sem við höfum here-- og þetta er meðal fleiri óþægilega sjálfur, 520 00:17:38,890 --> 00:17:42,390 þar sem þetta krefst þess að þú húmor mér fyrir réttlátur a lítill hluti af tími. 521 00:17:42,390 --> 00:17:43,442 Þú skalt vera númer eitt. 522 00:17:43,442 --> 00:17:44,150 Hvað heitir þú? 523 00:17:44,150 --> 00:17:44,610 >> Annan: Annan. 524 00:17:44,610 --> 00:17:45,526 >> DAVID J. Malan: Annan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 Hvað heitir þú? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. Malan: Joseph, þú ert númer tvö. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, númer þrjú. 530 00:17:52,260 --> 00:17:53,722 Stefan, númer fjögur. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. Malan: Cynthia, númer fimm. 533 00:17:57,548 --> 00:17:58,452 [Inaudible] 534 00:17:58,452 --> 00:17:59,618 DAVID J. Malan: [inaudible]. 535 00:17:59,618 --> 00:18:00,391 David, númer sex. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. Malan: fjöldi Matt er sjö. 538 00:18:02,160 --> 00:18:02,850 Og? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. Malan: Waverly, númer átta. 541 00:18:04,470 --> 00:18:04,970 Allt í lagi. 542 00:18:04,970 --> 00:18:06,510 Ef þú could-- Úpps. 543 00:18:06,510 --> 00:18:08,820 Ef ykkur öllum, eins og þinn Fyrsta áskorunin, það 544 00:18:08,820 --> 00:18:10,820 eru átta tónlist stendur hér frammi fyrir áhorfendur. 545 00:18:10,820 --> 00:18:14,200 Ef þú gætir sett tölur þínar á þessum tónlist stendur á þann hátt 546 00:18:14,200 --> 00:18:16,560 að þeir stilla upp með sömu tölur á borðinu. 547 00:18:16,560 --> 00:18:19,560 Svo að þér líta út eins og að með því að setja tölur þínar á þessum tónlist 548 00:18:19,560 --> 00:18:21,960 stendur hér. 549 00:18:21,960 --> 00:18:25,980 Excellent svo langt. 550 00:18:25,980 --> 00:18:26,600 >> Excellent. 551 00:18:26,600 --> 00:18:26,890 OK. 552 00:18:26,890 --> 00:18:29,556 Svo nú erum við að fara að spyrja Spurningin í nokkrum mismunandi vegu. 553 00:18:29,556 --> 00:18:31,610 Hvernig getum við farið um flokkun þessi fólkinu hérna? 554 00:18:31,610 --> 00:18:34,500 Því við vorum nokkrar aðferðir fyrr, þar sem við vorum 555 00:18:34,500 --> 00:18:36,360 konar að gera tvær mismunandi hópa. 556 00:18:36,360 --> 00:18:38,842 Og þá vorum við yfirleitt piecing hlutina saman. 557 00:18:38,842 --> 00:18:41,050 Um leið og við sáum tvær tölur sem átti saman, 558 00:18:41,050 --> 00:18:41,975 við setjum þá saman. 559 00:18:41,975 --> 00:18:43,350 Tvö bréf sem tilheyra saman. 560 00:18:43,350 --> 00:18:45,058 >> En við skulum sjá hvort við getur ekki móta þetta, 561 00:18:45,058 --> 00:18:48,044 þannig að við höfum á endanum sumir gervi-númerið sem þú vilt, 562 00:18:48,044 --> 00:18:49,710 sem þú getur leyst þetta vandamál. 563 00:18:49,710 --> 00:18:51,870 Svo nú er ég að leita út á þessar tölur hér. 564 00:18:51,870 --> 00:18:55,030 Og ég sé allt fullt af mistökum. 565 00:18:55,030 --> 00:18:57,750 Á endanum, ég vil einn á vinstri og átta ofan. 566 00:18:57,750 --> 00:19:00,650 >> Og svo ég er að leita á þessir tveir, fjórir og tveir. 567 00:19:00,650 --> 00:19:02,930 Og hvað er vandamálið, augljóslega? 568 00:19:02,930 --> 00:19:04,261 Já. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Two kemur augljóslega áður fjórir, svo þú veist hvað? 571 00:19:07,160 --> 00:19:10,210 Leyfðu mér að taka fyrst gráðugur nálgun, ef þú vilt, eins vandamálið 572 00:19:10,210 --> 00:19:13,790 setja one-- ef þú manst frá Standard Edition af Problem Set One, 573 00:19:13,790 --> 00:19:16,820 þar sem ég bara á staðnum að leysa vandamál sem er hérna fyrir framan mig 574 00:19:16,820 --> 00:19:17,690 og sjá hvar það leiðir mig. 575 00:19:17,690 --> 00:19:17,870 >> OK. 576 00:19:17,870 --> 00:19:20,161 Svo tveggja og fjögurra, láta mig fara undan og bara skipta þér tvo. 577 00:19:20,161 --> 00:19:22,400 Ef þú getur líkamlega færa ykkur og pappír þinn, 578 00:19:22,400 --> 00:19:25,040 Ég virðist hafa fengið að skrá í betri stöðu. 579 00:19:25,040 --> 00:19:26,330 >> Nú, þeir gott. 580 00:19:26,330 --> 00:19:28,480 Ég ætla að fara, fjögur og sex, lítur vel út. 581 00:19:28,480 --> 00:19:29,110 Ekki vandamál. 582 00:19:29,110 --> 00:19:30,440 Sex og átta, OK. 583 00:19:30,440 --> 00:19:31,860 Átta og eitt, annað vandamál. 584 00:19:31,860 --> 00:19:34,750 Vegna þess að það er satt um átta og einn? 585 00:19:34,750 --> 00:19:36,990 Einn kemur fyrir átta, og svo hvað eigum við að gera? 586 00:19:36,990 --> 00:19:38,090 Við skulum skipta þessar tvær. 587 00:19:38,090 --> 00:19:39,316 Einn og átta. 588 00:19:39,316 --> 00:19:40,690 Og nú ætla ég að fara að halda áfram. 589 00:19:40,690 --> 00:19:42,030 Ég ætla að halda að leita á undan. 590 00:19:42,030 --> 00:19:42,840 Og við skulum sjá hvað gerist. 591 00:19:42,840 --> 00:19:44,680 Átta og þrír, af Auðvitað út af röð. 592 00:19:44,680 --> 00:19:45,815 Skulum skipti. 593 00:19:45,815 --> 00:19:46,940 Átta og sjö, auðvitað. 594 00:19:46,940 --> 00:19:47,481 Bilað. 595 00:19:47,481 --> 00:19:48,280 Skulum skipti. 596 00:19:48,280 --> 00:19:49,940 Átta og fimm, auðvitað, við skulum skipta. 597 00:19:49,940 --> 00:19:50,560 Allt í lagi. 598 00:19:50,560 --> 00:19:51,880 List er raðað. 599 00:19:51,880 --> 00:19:53,060 já? 600 00:19:53,060 --> 00:19:54,280 >> OK, augljóslega ekki. 601 00:19:54,280 --> 00:19:55,860 En það er lítið betra, ekki satt? 602 00:19:55,860 --> 00:19:57,270 Vegna tilkynning hvað gerðist. 603 00:19:57,270 --> 00:20:01,749 Hvert skipti sem við framkvæmdu skipti, minni Fjöldi konar percolated þannig, 604 00:20:01,749 --> 00:20:03,790 og stærri tala percolated þessa leið, eða við munum 605 00:20:03,790 --> 00:20:06,880 byrja að segja í loftbólum til vinstri eða í loftbólum til hægri. 606 00:20:06,880 --> 00:20:10,080 >> Nú, það er ekki nóg, því í besta falli númer gæti 607 00:20:10,080 --> 00:20:11,990 hafa flutt eitt blettur fram, eða í versta falli, 608 00:20:11,990 --> 00:20:13,880 a tala gæti hafa flutti eitt blettur frekar. 609 00:20:13,880 --> 00:20:16,369 Svo þú veist hvað af þessu tagi af unnið ágætlega hingað til. 610 00:20:16,369 --> 00:20:17,410 Leyfðu mér að reyna bara aftur. 611 00:20:17,410 --> 00:20:18,880 Tveggja og fjögurra, þeir OK. 612 00:20:18,880 --> 00:20:20,180 Fjögur og sex, þá eru þeir í lagi. 613 00:20:20,180 --> 00:20:21,790 Sex og einn, út af röð. 614 00:20:21,790 --> 00:20:23,007 Svo skulum skipta þér tvær. 615 00:20:23,007 --> 00:20:25,840 Og nú, eftir að vandamálið er farin að fá smá betri aftur. 616 00:20:25,840 --> 00:20:27,006 Sex og þrír, út af röð. 617 00:20:27,006 --> 00:20:28,100 Við skulum skipta þér tvær. 618 00:20:28,100 --> 00:20:29,730 Sex og sjö, þú ert góður. 619 00:20:29,730 --> 00:20:32,230 Sjö og fimm, að sjálfsögðu, út af röð. 620 00:20:32,230 --> 00:20:33,920 Sjö og átta, í því skyni. 621 00:20:33,920 --> 00:20:36,470 Og nú gæti ég þurft að gera þetta nokkrum sinnum. 622 00:20:36,470 --> 00:20:39,830 Og í raun held sjálfir kannski hversu oft hámarks 623 00:20:39,830 --> 00:20:41,330 gæti ég þurft að ganga fram og til baka? 624 00:20:41,330 --> 00:20:42,390 >> Við munum koma aftur að því. 625 00:20:42,390 --> 00:20:43,700 Svo tveir og fjórir eru enn í lagi. 626 00:20:43,700 --> 00:20:44,940 Fjögur og eitt, nei. 627 00:20:44,940 --> 00:20:45,747 Svo skulum skipti. 628 00:20:45,747 --> 00:20:47,830 Og aftur, eftir sjónrænt einn er góður af freyðandi 629 00:20:47,830 --> 00:20:49,163 til vinstri, þar sem það ætti að vera. 630 00:20:49,163 --> 00:20:50,010 Fjögur og þrjú skipti. 631 00:20:50,010 --> 00:20:51,330 Fjögur og sex. 632 00:20:51,330 --> 00:20:53,100 Sex og fimm skipti. 633 00:20:53,100 --> 00:20:53,959 Sex og sjö. 634 00:20:53,959 --> 00:20:55,000 Sjö og átta eru góð. 635 00:20:55,000 --> 00:20:55,500 >> Good. 636 00:20:55,500 --> 00:20:58,460 Við erum að fá jafnvel betri. 637 00:20:58,460 --> 00:20:59,130 Svo skulum sjá. 638 00:20:59,130 --> 00:21:00,940 Nú höfum við tvö og einn. 639 00:21:00,940 --> 00:21:02,520 Auðvitað, skipta. 640 00:21:02,520 --> 00:21:07,520 Tveir og þrír, þrír og fjórir, fjórir og fimm, sex og sjö, sjö og átta. 641 00:21:07,520 --> 00:21:08,020 Good. 642 00:21:08,020 --> 00:21:08,730 Og þú veist hvað? 643 00:21:08,730 --> 00:21:11,190 Vegna þess að ég gerði eina breytingu þar, Leyfðu mér að gera eitt geðheilsu stöðva. 644 00:21:11,190 --> 00:21:13,023 Leyfðu mér að fara alla leið aftur á byrjun. 645 00:21:13,023 --> 00:21:13,680 OK. 646 00:21:13,680 --> 00:21:14,750 Einn, two-- jamm, sjá? 647 00:21:14,750 --> 00:21:15,870 Eitthvað var rangt. 648 00:21:15,870 --> 00:21:18,420 Þrír, fjórir, fimm, sex, sjö, átta. 649 00:21:18,420 --> 00:21:21,920 Og í þessu síðasta framhjá, eru þú ánægð með minn núna 650 00:21:21,920 --> 00:21:23,830 segja að það er raðað? 651 00:21:23,830 --> 00:21:24,330 OK. 652 00:21:24,330 --> 00:21:25,880 Sjónrænt, það er alveg satt. 653 00:21:25,880 --> 00:21:28,410 En virkni, hvað gerði líka bara gerst 654 00:21:28,410 --> 00:21:31,870 í þeirri síðustu umferð sem gerir þér til að staðfesta að þessi listi er örugglega 655 00:21:31,870 --> 00:21:32,660 flokkaður? 656 00:21:32,660 --> 00:21:34,477 >> Hvað gerði ég gera eða ekki gera þetta síðasta framhjá? 657 00:21:34,477 --> 00:21:35,810 Áhorfendur: Það voru engar breytingar. 658 00:21:35,810 --> 00:21:36,120 DAVID J. Malan: Svo? 659 00:21:36,120 --> 00:21:37,070 Áhorfendur: Engar breytingar. 660 00:21:37,070 --> 00:21:38,653 DAVID J. Malan: Það voru engar breytingar. 661 00:21:38,653 --> 00:21:41,947 Svo það væri heimskulegt af mér að gera það sama reiknirit aftur 662 00:21:41,947 --> 00:21:43,780 ef ég vissi ekki að allir breytir í fyrsta skipti. 663 00:21:43,780 --> 00:21:45,160 Og ríkið hefur ekki breyst. 664 00:21:45,160 --> 00:21:47,576 Víst, ég er ekki að fara að gera Allar breytingar í annað sinn. 665 00:21:47,576 --> 00:21:49,820 Og svo, það er óhætt núna að segja, lista er raðað. 666 00:21:49,820 --> 00:21:52,069 >> Og reyndar, þetta er nú eitthvað sem við munum almennt 667 00:21:52,069 --> 00:21:56,900 kalla kúla tegund, þar gefnar, þú leiðrétta mistök aftur, 668 00:21:56,900 --> 00:22:00,210 og aftur, og aftur, og þú halda áfram fram og til baka, 669 00:22:00,210 --> 00:22:03,370 og fram og til baka, þar til þú gera engar slíkar skiptasamninga, á hver benda 670 00:22:03,370 --> 00:22:07,089 þú getur verið viss um, já, ég lauk ákveða allar mistökum. 671 00:22:07,089 --> 00:22:08,630 Við skulum endurstilla og reyna nýja nálgun. 672 00:22:08,630 --> 00:22:11,590 Ef þú krakkar gætu farið aftur í röð þú varst í smá stund síðan, 673 00:22:11,590 --> 00:22:13,780 sem leit út eins og þetta. 674 00:22:13,780 --> 00:22:17,640 Nú, við skulum taka nálgast aðeins meira eins og próf bók, 675 00:22:17,640 --> 00:22:21,122 þar sem við vorum stöðugt velja bókstaf 676 00:22:21,122 --> 00:22:22,830 sem við vildum konar að takast á við næsta. 677 00:22:22,830 --> 00:22:26,420 Kannski var það mikil bréf, eins A, eða lágt bréf Z. 678 00:22:26,420 --> 00:22:28,170 >> Svo er allir aftur í þessari röð. 679 00:22:28,170 --> 00:22:29,800 Og nú langar mig að gera þetta. 680 00:22:29,800 --> 00:22:34,880 Við skulum sjá Ég veit að ég hef átta tölur hér. 681 00:22:34,880 --> 00:22:37,410 Ég ætla að fara á undan og bara vísvitandi að velja 682 00:22:37,410 --> 00:22:38,520 minnstu atriði. 683 00:22:38,520 --> 00:22:38,760 Ekki satt? 684 00:22:38,760 --> 00:22:39,801 Þetta virðist innsæi líka. 685 00:22:39,801 --> 00:22:42,560 Hvers vegna get ég ekki fundið minnstu þáttur, setja það þar sem það tilheyrir, 686 00:22:42,560 --> 00:22:45,280 þá fá næsta minnstu þáttur, setja það þar sem það tilheyrir, og bara endurtaka. 687 00:22:45,280 --> 00:22:46,820 >> Vegna innsæi, sem ætti að virka líka. 688 00:22:46,820 --> 00:22:48,441 Svo, það er fjórir ansi lítill fjöldi. 689 00:22:48,441 --> 00:22:49,940 Ég ætla að muna hvar þetta er. 690 00:22:49,940 --> 00:22:50,523 Bíddu aðeins. 691 00:22:50,523 --> 00:22:51,577 Tveggja er minni. 692 00:22:51,577 --> 00:22:53,910 Leyfðu mér að muna nú að hvar sem tveir er, og gleyma um fjögur. 693 00:22:53,910 --> 00:22:55,050 Við munum takast á við það seinna. 694 00:22:55,050 --> 00:22:56,460 Sex, ég hef ekki áhuga. 695 00:22:56,460 --> 00:22:57,810 Átta, ég hef ekki áhuga á. 696 00:22:57,810 --> 00:22:59,780 Eitt er nýr lítill númerið mitt. 697 00:22:59,780 --> 00:23:01,470 Þannig að ég ætla að muna hvar maður er. 698 00:23:01,470 --> 00:23:02,534 Þrír, ekki áhuga. 699 00:23:02,534 --> 00:23:03,450 Seven, ekki áhuga. 700 00:23:03,450 --> 00:23:04,530 Fimm, ekki áhuga. 701 00:23:04,530 --> 00:23:07,390 >> Svo án þess að detta stigi á þessu ári, 702 00:23:07,390 --> 00:23:09,890 Ég ætla að grípa fjölda one-- og hvað hét aftur? 703 00:23:09,890 --> 00:23:10,150 >> Annan: Annan. 704 00:23:10,150 --> 00:23:11,220 >> DAVID J. Malan: Annan. 705 00:23:11,220 --> 00:23:13,540 Og ef þú gætir komið með mér á upphaf listanum, 706 00:23:13,540 --> 00:23:14,870 við skulum setja þig þar sem þú tilheyrir. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- hvað er nafnið þitt? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. Malan: Stefan er á leiðinni. 710 00:23:18,191 --> 00:23:23,490 Svo áður en Stefan leysa þetta Vandamálið, hvað eigum við að gera? 711 00:23:23,490 --> 00:23:25,412 Hvað gerum við við Stefan? 712 00:23:25,412 --> 00:23:27,269 >> Áhorfendur: [inaudible]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. Malan: OK. 714 00:23:28,060 --> 00:23:28,850 Þannig að við gætum gert það. 715 00:23:28,850 --> 00:23:31,730 Við gætum konar taka Stefan og hans fjögur, og bara setja það í breytu 716 00:23:31,730 --> 00:23:33,530 og halda í það fyrir talsverða tíma, 717 00:23:33,530 --> 00:23:35,220 þannig að gera pláss fyrir númer eitt. 718 00:23:35,220 --> 00:23:36,280 Og það er ekki slæmt. 719 00:23:36,280 --> 00:23:39,270 Ég gæti bent, hvers vegna ekki við setjum bara Stefan hér? 720 00:23:39,270 --> 00:23:41,610 Hvers vegna gæti þetta brjóta eitt af þeim hugmyndum sem við byrjuðum 721 00:23:41,610 --> 00:23:44,830 að tala um síðustu tíma, í síðustu viku? 722 00:23:44,830 --> 00:23:45,330 Já? 723 00:23:45,330 --> 00:23:45,740 >> Áhorfendur: [inaudible]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. Malan: Það er engin Vísitala fyrir það. 725 00:23:46,860 --> 00:23:49,735 Ef þú hugsa um þetta, örugglega, eins og óákveðinn greinir í ensku array, þetta er eins neikvætt einn, 726 00:23:49,735 --> 00:23:52,900 þannig að það er ekkert minni í raun hér ef þetta er örugglega fylki, 727 00:23:52,900 --> 00:23:55,090 eins og við lýst í síðustu viku í fyrirlestri. 728 00:23:55,090 --> 00:23:56,250 Svo við ættum ekki að gera þetta. 729 00:23:56,250 --> 00:23:57,340 Við gætum geyma það í breytu. 730 00:23:57,340 --> 00:23:57,820 >> Eða þú veist hvað? 731 00:23:57,820 --> 00:23:59,153 Ég heyrði einhver annar benda henni. 732 00:23:59,153 --> 00:24:01,020 Hvað annað gætum við gert með Stefan? 733 00:24:01,020 --> 00:24:03,770 Hvers vegna eigum við ekki að evict bara hann og setti hann yfir þar númer eitt var. 734 00:24:03,770 --> 00:24:05,170 Svo ef þú vilt fara þarna. 735 00:24:05,170 --> 00:24:07,300 Og reyndar, þetta er nokkuð góð lausn. 736 00:24:07,300 --> 00:24:10,480 Nú á annars vegar hef ég góður af gerði vandamálið verra. 737 00:24:10,480 --> 00:24:13,650 Fjögur er nú lengra í burtu frá þar sem það ætti að vera. 738 00:24:13,650 --> 00:24:14,900 Það ætti að vera til þessa hluta. 739 00:24:14,900 --> 00:24:16,100 >> En þú veist hvað? 740 00:24:16,100 --> 00:24:17,630 Það gæti hafa verið óheppni. 741 00:24:17,630 --> 00:24:18,822 Kannski númer átta var hér. 742 00:24:18,822 --> 00:24:20,530 Og svo, kannski við gerðum hafa fengið heppinn, 743 00:24:20,530 --> 00:24:22,460 og ýtt átta nær til loka. 744 00:24:22,460 --> 00:24:24,710 Svo í lok dagsins, það svona allt meðaltöl út. 745 00:24:24,710 --> 00:24:26,085 Við þurfum ekki að hugsa um fjögur. 746 00:24:26,085 --> 00:24:29,400 Allt sem ég hugsa um núna er velja minnstu þáttur. 747 00:24:29,400 --> 00:24:32,030 >> Og nú, hvað ég ætla að gera er að gleyma um númer eitt 748 00:24:32,030 --> 00:24:35,160 varanlega, því ég veit að Listinn aftan mig er nú flokkaður. 749 00:24:35,160 --> 00:24:36,720 Svo minn listi var áður stærð átta. 750 00:24:36,720 --> 00:24:37,720 Nú er það á stærð sjö. 751 00:24:37,720 --> 00:24:40,340 Svo vandamálið mitt er að verða minni, að vísu línulega. 752 00:24:40,340 --> 00:24:43,022 Svo nú er ég að fara að velja núverandi minnsti þáttur, tveir. 753 00:24:43,022 --> 00:24:46,520 Sex, átta, fjórir, þrír, sjö, fimm. 754 00:24:46,520 --> 00:24:47,770 Það var minnsta þáttur. 755 00:24:47,770 --> 00:24:49,416 Svo hvað er ég að fara að gera with-- Hvað hét aftur? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. Malan: Joseph? 758 00:24:50,085 --> 00:24:52,000 Við erum að fara að yfirgefa Jósef í stað. 759 00:24:52,000 --> 00:24:54,842 Nú ætla ég að þykjast að þessir krakkar are-- vel, 760 00:24:54,842 --> 00:24:56,550 Ég veit að þessir tveir eru þegar raðað. 761 00:24:56,550 --> 00:24:58,424 Beinum nú sjónum á Afgangurinn af listanum. 762 00:24:58,424 --> 00:25:00,080 Six er núverandi minnsta. 763 00:25:00,080 --> 00:25:01,190 Átta er stærri. 764 00:25:01,190 --> 00:25:02,970 Fjögur er nú núverandi minnstu. 765 00:25:02,970 --> 00:25:04,762 Þrjú er nú núverandi minnstu. 766 00:25:04,762 --> 00:25:07,720 Og svo nú, ég ætla að velja þrjá, sem is-- hvað er nafnið þitt aftur? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. Malan: Serena, ef þú gætir grípa þitt og skipti with-- 769 00:25:10,620 --> 00:25:11,550 KALSANG: Kalsang. 770 00:25:11,550 --> 00:25:12,940 DAVID J. Malan: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Koma á aftur, og við erum fara að skipta þessir tveir. 772 00:25:15,220 --> 00:25:17,360 Og nú, við skulum setja þetta á Autopilot. 773 00:25:17,360 --> 00:25:21,589 Ég ætla að fara og fara með hana til ykkur til að velja næsta minnstu atriði. 774 00:25:21,589 --> 00:25:22,380 Dun Dun Dun Dun. 775 00:25:22,380 --> 00:25:24,560 Númer fjögur, hvað ættir þú að gera? 776 00:25:24,560 --> 00:25:26,261 Excellent. 777 00:25:26,261 --> 00:25:27,760 Nú, ég ætla að gera annað framhjá. 778 00:25:27,760 --> 00:25:28,590 Dun Dun Dun Dun. 779 00:25:28,590 --> 00:25:31,465 Ég sé fimm er næsta lítill. 780 00:25:31,465 --> 00:25:32,840 Nú, ég ætla að taka aðra sendingu. 781 00:25:32,840 --> 00:25:33,631 Dun Dun Dun Dun. 782 00:25:33,631 --> 00:25:34,880 Six er minnsti. 783 00:25:34,880 --> 00:25:35,520 Good. 784 00:25:35,520 --> 00:25:36,585 Seven er minnsti. 785 00:25:36,585 --> 00:25:37,085 Engin breyting. 786 00:25:37,085 --> 00:25:38,630 Átta er minnsti. 787 00:25:38,630 --> 00:25:39,170 Lokið. 788 00:25:39,170 --> 00:25:43,900 >> Svo það sem við höfum bara gert með því að iteratively að velja einn þáttur á eftir öðrum 789 00:25:43,900 --> 00:25:47,230 er framkvæma eitthvað sem að við erum að fara að móta og val tagi. 790 00:25:47,230 --> 00:25:49,120 Og það er jafnvel einfaldara að útskýra, 791 00:25:49,120 --> 00:25:51,310 í að bókstaflega allt sem þú langar að gera er bara að halda 792 00:25:51,310 --> 00:25:54,700 fara fram og til baka í gegnum listann velja, næsta lítill þáttur, 793 00:25:54,700 --> 00:25:55,720 þar til þú ert búinn. 794 00:25:55,720 --> 00:25:58,650 >> Svo það er jafnvel einfaldara, kannski innsæi, en í fyrra. 795 00:25:58,650 --> 00:26:00,020 Við skulum reyna í síðasta einn. 796 00:26:00,020 --> 00:26:03,060 Ef þú krakkar gætu endurstilla ykkur í eftirfarandi stöður 797 00:26:03,060 --> 00:26:08,600 Eitt síðasta sinn, við skulum sjá hvort við getum ekki nú formlega eitt annað nálgun. 798 00:26:08,600 --> 00:26:12,857 Í raun, myndi einhver þarna eins og að leggja 799 00:26:12,857 --> 00:26:14,440 hvernig annars gætum við farið að gera þetta? 800 00:26:14,440 --> 00:26:17,439 Án kasta út buzzwords eða tegund af svörum sem eru nú þegar þekkt, 801 00:26:17,439 --> 00:26:19,689 bara innsæi, hvað getum við gert? 802 00:26:19,689 --> 00:26:21,635 >> Áhorfendur: [inaudible]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. Malan: Já. 804 00:26:22,510 --> 00:26:24,620 Svo er það einhver mikill innsæi þar. 805 00:26:24,620 --> 00:26:28,020 Góðir hlutir virðast gerast svona langt í tölvunarfræði þegar við skipta 806 00:26:28,020 --> 00:26:30,832 og sigra vandamál af því að deila það í tvennt og tvennt og tvennt. 807 00:26:30,832 --> 00:26:32,540 Og svo reyndar, við gæti byrjað að gera það. 808 00:26:32,540 --> 00:26:35,754 Og í raun, það er að fara að vera, við munum sjá, einn af bestu lausnir okkar enn. 809 00:26:35,754 --> 00:26:37,420 En við skulum koma aftur til að áður en langur. 810 00:26:37,420 --> 00:26:40,500 Í raun erum við að fara að gera sem stuttu seinna í þessari viku. 811 00:26:40,500 --> 00:26:42,180 Hvað annað gætum við gert til að leysa þetta? 812 00:26:42,180 --> 00:26:44,647 Svo er allir hér í virðist af handahófi röð. 813 00:26:44,647 --> 00:26:45,230 Veistu hvað? 814 00:26:45,230 --> 00:26:48,320 Frekar en að fara fram og til baka, fram og til baka, fram og til baka 815 00:26:48,320 --> 00:26:50,624 í hvert sinn, þetta er eins og Ég er að gera a einhver fjöldi af gangandi. 816 00:26:50,624 --> 00:26:52,790 Hvers vegna get ég ekki að byrja bara á upphaf listanum, 817 00:26:52,790 --> 00:26:54,960 og bara setja fjögur þar sem það tilheyrir? 818 00:26:54,960 --> 00:26:59,680 Svo láta mig gera ráð fyrir stundu að minn listi er bara þetta fyrsti þáttur. 819 00:26:59,680 --> 00:27:04,937 Er fjögurra flokkaður á þessari stundu í tíma, ef allt sem ég hugsa um er allt hér? 820 00:27:04,937 --> 00:27:06,520 Þetta er tegund af trivially satt, ekki satt? 821 00:27:06,520 --> 00:27:10,000 Eins listanum inniheldur eitt númer, og sem tala fjögur er augljóslega flokkaður. 822 00:27:10,000 --> 00:27:13,070 >> Svo láta mig kveða bara að þessi listi er flokkaður. 823 00:27:13,070 --> 00:27:15,090 En nú hef ég restina af þessum lista. 824 00:27:15,090 --> 00:27:17,240 Svo nú, lendir I tvö. 825 00:27:17,240 --> 00:27:21,690 Hvar er tvö augljóslega tilheyra með tilliti til fjórum? 826 00:27:21,690 --> 00:27:22,580 Áður fjórum. 827 00:27:22,580 --> 00:27:23,862 Svo hvað get ég gert hér? 828 00:27:23,862 --> 00:27:24,820 Hvað er nafnið þitt aftur? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. Malan: Joseph, ef þú gætir stíga til baka 831 00:27:26,030 --> 00:27:27,790 fyrir aðeins augnablik með númerið þitt. 832 00:27:27,790 --> 00:27:31,130 Og nú hvað ætti Stefan gera hér? 833 00:27:31,130 --> 00:27:33,720 Við skulum skipta Stefan hérna. 834 00:27:33,720 --> 00:27:35,520 Og nú skulum Joseph koma hér. 835 00:27:35,520 --> 00:27:39,660 Og nú, láta mig halda því fram að allt hér er flokkað. 836 00:27:39,660 --> 00:27:42,474 Svo, að svipuð niðurstaða, en grundvallaratriðum ólík nálgun. 837 00:27:42,474 --> 00:27:44,140 Ég hef ekki einu sinni litið hvað er þarna niðri. 838 00:27:44,140 --> 00:27:46,310 Ég halda bara að taka þá þætti eins og þeir eru afhent mér, 839 00:27:46,310 --> 00:27:47,240 og takast á við þá. 840 00:27:47,240 --> 00:27:48,330 >> Svo nú, ég sjá númer sex. 841 00:27:48,330 --> 00:27:51,110 Hvar er númer sex tilheyra? 842 00:27:51,110 --> 00:27:53,250 Við höfum tvær, fjórar, sex. 843 00:27:53,250 --> 00:27:54,800 Nákvæmlega þar sem hún er núna. 844 00:27:54,800 --> 00:27:57,750 Svo skulum fara það eitt og sér, og nú halda því fram að þessum hluta af the listi 845 00:27:57,750 --> 00:27:58,772 er nú flokkað. 846 00:27:58,772 --> 00:28:01,230 Og svo, þetta finnst grundvallaratriðum mismunandi í því að ég er bara 847 00:28:01,230 --> 00:28:05,230 fara í gegnum listann hér línulega, og ég er aldrei tvöföldun aftur. 848 00:28:05,230 --> 00:28:05,730 Já. 849 00:28:05,730 --> 00:28:06,230 Allt í lagi. 850 00:28:06,230 --> 00:28:08,190 Svo átta, þar tilheyra þér? 851 00:28:08,190 --> 00:28:08,730 Hérna. 852 00:28:08,730 --> 00:28:09,310 Perfect. 853 00:28:09,310 --> 00:28:10,210 Svo nú, einn. 854 00:28:10,210 --> 00:28:10,900 Uh-ó. 855 00:28:10,900 --> 00:28:13,010 Þetta er eins og það er að fara að vera dýrt. 856 00:28:13,010 --> 00:28:15,690 Nú, í fyrri reiknirit, Ég skipti bara fólk. 857 00:28:15,690 --> 00:28:18,648 Þannig að ég gæti sett hann alla leið á upphaf, en flutti Jósef. 858 00:28:18,648 --> 00:28:21,450 En ef ég flyt Jósef, nú hvað er að fara að vera rangt? 859 00:28:21,450 --> 00:28:24,250 >> Nú hef ég svona undone-- ég hef tekið eitt skref fram á við og þá 860 00:28:24,250 --> 00:28:26,300 eitt skref til baka, vegna þess að nú Joseph vildi vera út af röð. 861 00:28:26,300 --> 00:28:26,830 Svo skulum gera þetta. 862 00:28:26,830 --> 00:28:29,150 Ef þú gætir tekið númer eitt og stíga til baka fyrir aðeins augnablik. 863 00:28:29,150 --> 00:28:30,490 Hvernig getum við put-- það var heitirðu aftur? 864 00:28:30,490 --> 00:28:31,130 >> Annan: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. Malan: Annan í stað? 866 00:28:32,610 --> 00:28:36,091 Hvað þarf að gerast með tilliti að tveir, fjórir, sex og átta? 867 00:28:36,091 --> 00:28:37,570 Þeir þurfa að skipta. 868 00:28:37,570 --> 00:28:42,590 Svo ef átta langar til að skipta fyrst, þá sex, þá fjórir, þá tvö. 869 00:28:42,590 --> 00:28:45,380 Og þá Annan, ef þú vilt eins og til að koma hingað, góð. 870 00:28:45,380 --> 00:28:47,760 En hér, höfum við bara konar greitt verð 871 00:28:47,760 --> 00:28:49,510 á öðrum stað í reiknirit. 872 00:28:49,510 --> 00:28:52,550 En síðast þegar við val flokka, og jafnvel kúla tegund, 873 00:28:52,550 --> 00:28:54,700 Ég er að ganga til baka og fram, fram og til baka, 874 00:28:54,700 --> 00:28:58,360 sem er vissulega að bæta upp tími-vitur, og bókstaflega þrepum. 875 00:28:58,360 --> 00:29:00,660 >> Innsetning tegund, fyrst sýn, lítur út eins og það er 876 00:29:00,660 --> 00:29:05,150 frábær klárari, með því að ég er bara gera hægur, stigvaxandi framfarir, 877 00:29:05,150 --> 00:29:07,120 en ég ætla ekki að fara þetta fram og til baka. 878 00:29:07,120 --> 00:29:09,410 En ef einhver er örugglega út af röð, tilkynningu 879 00:29:09,410 --> 00:29:10,840 alla vinnu sem ég þurfti bara að gera. 880 00:29:10,840 --> 00:29:14,750 Ég þurfti að fara helminginn af listanum bara til að gera pláss fyrir númer eitt. 881 00:29:14,750 --> 00:29:16,790 Svo er það sama upphæð vinnu svona langt það 882 00:29:16,790 --> 00:29:18,690 finnst bara öðruvísi tegund af vinna. 883 00:29:18,690 --> 00:29:19,370 >> Við skulum halda áfram. 884 00:29:19,370 --> 00:29:22,657 Svo nú vitum við að allir milli einn og átta eru flokkuð. 885 00:29:22,657 --> 00:29:23,740 Hér hef ég númer þrjú. 886 00:29:23,740 --> 00:29:25,864 Ef þú vilt að taka upp númer þrjú, stíga til baka einn. 887 00:29:25,864 --> 00:29:28,260 Og hvað þú krakkar þarft að gera? 888 00:29:28,260 --> 00:29:28,760 Jebb. 889 00:29:28,760 --> 00:29:33,070 Svo er það annað, tveir, þrjú skref. 890 00:29:33,070 --> 00:29:36,010 Þrjár einingar af tíma sem bara kosta mér, svo að þrír geta nú passa. 891 00:29:36,010 --> 00:29:37,460 Að lokum, sjö. 892 00:29:37,460 --> 00:29:39,730 >> Við skulum fara á undan og hafa þú taka skref til baka. 893 00:29:39,730 --> 00:29:42,780 Þetta er bara að fara að kosta okkur ein eining af tíma, en það er allt í lagi. 894 00:29:42,780 --> 00:29:44,170 Og nú, fimm er að fara að vera svolítið dýrari. 895 00:29:44,170 --> 00:29:45,340 Ef þú vilt að stíga til baka. 896 00:29:45,340 --> 00:29:48,380 Við þurfum að fara átta, og sjö og sex. 897 00:29:48,380 --> 00:29:50,749 Og þá munu allir er nú flokkaður. 898 00:29:50,749 --> 00:29:52,290 Svo stór hönd sjálfboðaliða okkar hér. 899 00:29:52,290 --> 00:29:53,554 Þakka þér kærlega fyrir. 900 00:29:53,554 --> 00:29:56,220 >> [Applause] 901 00:29:56,220 --> 00:29:56,860 >> Þakka ykkur öllum. 902 00:29:56,860 --> 00:29:57,520 Þakka ykkur öllum. 903 00:29:57,520 --> 00:30:02,940 Svo skulum sjá nú bara hvernig dýr allt sem var. 904 00:30:02,940 --> 00:30:06,210 Við skulum íhuga kannski Einfaldasta þeirra, kúla tegund. 905 00:30:06,210 --> 00:30:09,950 Og ég segi einfaldasta, bara vegna þess að þú getur leyst það græðgislega bara með 906 00:30:09,950 --> 00:30:11,660 laga pöruðum vandamál hér. 907 00:30:11,660 --> 00:30:13,720 Festa pöruðum vandamál hér, aftur og aftur 908 00:30:13,720 --> 00:30:17,680 og aftur, endurtaka eins og margir oft og þú þarft í raun að. 909 00:30:17,680 --> 00:30:21,050 >> Svo kemur í ljós að með kúla tagi, vel, 910 00:30:21,050 --> 00:30:25,820 hversu mörg skref þarf ég að taka á fyrsta umferð þess reiknirit? 911 00:30:25,820 --> 00:30:30,850 Ég gæti take-- skulum see-- einn, tveir, þrír, fjórir, fimm, sex, sjö. 912 00:30:30,850 --> 00:30:32,190 Og það er átta þætti hér. 913 00:30:32,190 --> 00:30:35,280 Svo það er eins og n mínus 1 skref til fá frá upphafi listanum 914 00:30:35,280 --> 00:30:36,380 til loka listanum. 915 00:30:36,380 --> 00:30:41,350 >> En með val tagi, muna að ég er að velja þá þætti aftur og aftur 916 00:30:41,350 --> 00:30:44,590 og aftur er það minnsta, Ég er að setja það í stað, 917 00:30:44,590 --> 00:30:46,616 en þá er ég ekki leita á bak við mig aftur. 918 00:30:46,616 --> 00:30:49,490 Þannig að ég held að það sé svolítið skýrari þá í fyrsta skipti, gæti ég 919 00:30:49,490 --> 00:30:52,680 að taka alla n mínus 1 skref að finna minnstu frumefni. 920 00:30:52,680 --> 00:30:55,920 Og ég setti þá í stað, og ég evict hver var hér áður. 921 00:30:55,920 --> 00:30:57,500 >> En þá þarf ég ekki að halda að leita á þennan þátt, 922 00:30:57,500 --> 00:30:59,040 vegna þess að ég veit að það er þegar minnsti. 923 00:30:59,040 --> 00:31:01,581 Svo nú get ég líta á bara sjö þætti, þá sex þætti, 924 00:31:01,581 --> 00:31:03,290 þá fimm þætti, þá fjóra þætti. 925 00:31:03,290 --> 00:31:06,900 Og svo stærðfræðilega, ef n er fjöldi staka eða númer 926 00:31:06,900 --> 00:31:11,990 að við byrjuðum með, getur þú ímyndað þér að þetta er það sama og n mínus 1, 927 00:31:11,990 --> 00:31:14,250 plús n mínus 2 skref, plús n mínus 3 skref, 928 00:31:14,250 --> 00:31:16,780 plús n mínus 4 skref, öll leið niður í aðeins eitt skref. 929 00:31:16,780 --> 00:31:18,160 Og ég er á síðasta mann minn. 930 00:31:18,160 --> 00:31:20,650 >> Og ef þú manst að mikið af stats bækur eða stærðfræði bækur 931 00:31:20,650 --> 00:31:24,730 hafa þessir formúlur á Hardcover aftur eða framan af þeim, 932 00:31:24,730 --> 00:31:27,690 það kemur í ljós að þessari röð er að lýsa einfaldlega 933 00:31:27,690 --> 00:31:28,857 sem n sinnum n mínus 1 yfir 2. 934 00:31:28,857 --> 00:31:31,273 Og það er allt í lagi ef það er ekki í fremstu röð á huga þinn. 935 00:31:31,273 --> 00:31:32,420 En þetta er örugglega satt. 936 00:31:32,420 --> 00:31:34,449 Það er bara einfaldara leið til að skrifa hana. 937 00:31:34,449 --> 00:31:36,240 Og svo ef þú heldur að aftur í grunnskóla, 938 00:31:36,240 --> 00:31:38,698 þegar þú byrjar bara að margfalda það út, þetta er auðvitað, 939 00:31:38,698 --> 00:31:41,820 er bara n veldi mínus n deilt með 2. 940 00:31:41,820 --> 00:31:44,772 Allt sem ég hef gert er að auka orðalagið þar. 941 00:31:44,772 --> 00:31:46,730 Og svo skulum umrita þetta svolítið öðruvísi. 942 00:31:46,730 --> 00:31:49,780 Það er n kvaðrat deilt með 2 mínus N / 2. 943 00:31:49,780 --> 00:31:53,270 >> Svo aftur, ég er bara svona að beita sumir tölur reglur þar. 944 00:31:53,270 --> 00:31:57,140 En takið nú að stærsta tíma í þessari tjáningu, svo að segja, 945 00:31:57,140 --> 00:31:58,540 er að n veldi. 946 00:31:58,540 --> 00:32:02,910 Svo já, það er n veldi deilt með 2, mínus N / 2. 947 00:32:02,910 --> 00:32:05,080 >> En almennt, ef n er að fara til vera a stór gildi, 948 00:32:05,080 --> 00:32:08,740 Ég ætla að halda því fram að n veldi er að fara að vera ráðandi þáttur. 949 00:32:08,740 --> 00:32:10,490 Það er bara að fara að vera stærri framlög 950 00:32:10,490 --> 00:32:12,877 til fjölda skrefum en n / 2. 951 00:32:12,877 --> 00:32:13,960 Svo hvað ég meina með þessu? 952 00:32:13,960 --> 00:32:16,795 Við skulum reyna einfalt dæmi, jafnvel þótt stærðfræði fær smá stór. 953 00:32:16,795 --> 00:32:20,210 >> Svo býst við höfðum 1 milljón manns á sviðinu, eða 1 milljón hlutum 954 00:32:20,210 --> 00:32:21,320 sem við viljum að raða. 955 00:32:21,320 --> 00:32:23,730 Skulum stinga milljón í nákvæmlega þeirri formúlu 956 00:32:23,730 --> 00:32:27,230 að sjá hversu mörg skref sem það tekur samtals að raða milljón þætti með segja, 957 00:32:27,230 --> 00:32:28,560 val tegund. 958 00:32:28,560 --> 00:32:30,760 >> Þannig að við myndum hafa sömu formúlu og áður. 959 00:32:30,760 --> 00:32:34,120 Ég myndi stinga milljón, þannig að ég fæ milljón kvaðrat deilt með 2, 960 00:32:34,120 --> 00:32:35,990 mínus milljón deilt með 2. 961 00:32:35,990 --> 00:32:40,180 Ef ég geri það stærðfræði fyrirfram hér höfum við 500 milljarða 962 00:32:40,180 --> 00:32:47,460 mínus 500.000, sem gefur okkur 499999500000, 963 00:32:47,460 --> 00:32:49,270 sem er laglegur fjári stór. 964 00:32:49,270 --> 00:32:54,370 >> Í staðreynd, ef þú bera saman núna 499000000000, 999 milljónir, 965 00:32:54,370 --> 00:33:01,210 500.000 á móti upprunalegu gildi okkar, 500 milljarðar, það er svo fjandinn nálægt. 966 00:33:01,210 --> 00:33:06,850 Ekki satt? n kvaðrat deilt með 2 gefur us-- eða öllu heldur, n kvaðrat deilt með 2 967 00:33:06,850 --> 00:33:08,370 gaf okkur 500 milljarða. 968 00:33:08,370 --> 00:33:13,510 Það er nokkuð fjári nálægt að 499,999,500,000, 969 00:33:13,510 --> 00:33:17,970 sem er að segja að draga burt 500.000, eða oftast draga burt 970 00:33:17,970 --> 00:33:20,010 n veldi, í raun ekki stór samningur. 971 00:33:20,010 --> 00:33:22,490 The n veldi gerir þetta tölur vaxa mjög hratt. 972 00:33:22,490 --> 00:33:25,790 >> Nú, þetta er mikilvægt aðeins að því marki eins og við, eins og tölva vísindamenn, 973 00:33:25,790 --> 00:33:29,350 eru almennt ekki að fara að hugsa svo mikið um blæbrigði þessum formúlum 974 00:33:29,350 --> 00:33:31,400 og nákvæmlega hvað nákvæmar svör eru. 975 00:33:31,400 --> 00:33:33,390 Við sama bara það, þú veist hvað? 976 00:33:33,390 --> 00:33:37,810 Í lok dags, þetta uppskrift er á röð af n veldi. 977 00:33:37,810 --> 00:33:39,350 >> Já, við erum að deila með 2 í það. 978 00:33:39,350 --> 00:33:41,360 Já, við erum að draga burt n mínus 2. 979 00:33:41,360 --> 00:33:46,860 En í lok dagsins, hugtakið sem raunverulega særir okkur og kostar okkur 980 00:33:46,860 --> 00:33:48,995 a einhver fjöldi af stíga er að veldi tíma. 981 00:33:48,995 --> 00:33:51,370 Og svo það sem tölvunarfræðingur er að fara að gera almennt 982 00:33:51,370 --> 00:33:54,160 er hunsa alla þá minni pöntun hugtök, 983 00:33:54,160 --> 00:33:56,900 og bara líta á einn sem stuðlar mest að kostnaði. 984 00:33:56,900 --> 00:34:00,530 >> Og þetta er gott, vegna þess að við getum nú tala í mun meiri almenn 985 00:34:00,530 --> 00:34:02,470 um reiknirit, og er að bera þá. 986 00:34:02,470 --> 00:34:04,550 Og sú staðreynd að ég er nota þessa O er vísvitandi. 987 00:34:04,550 --> 00:34:06,680 Þegar ég segi á röð um, ég er sérstaklega 988 00:34:06,680 --> 00:34:09,560 vísa til eitthvað heitir stór O. Og stór O 989 00:34:09,560 --> 00:34:14,090 er merki sem tölvan vísindamaður notar til að lýsa 990 00:34:14,090 --> 00:34:16,710 efri bundið á eitthvað. 991 00:34:16,710 --> 00:34:21,150 >> Svo ef þú segir að reiknirit er í stórum O n veldi, 992 00:34:21,150 --> 00:34:23,380 eins og ég lagði bara áðan, það þýðir 993 00:34:23,380 --> 00:34:27,710 að í skilmálar af gangi hennar tíma eða skilvirkni þess, 994 00:34:27,710 --> 00:34:30,090 það tekur á röð af n veldi skrefum. 995 00:34:30,090 --> 00:34:31,420 Kannski meira, kannski minna. 996 00:34:31,420 --> 00:34:33,435 En það er á röð n veldi. 997 00:34:33,435 --> 00:34:34,560 Og það er efri. 998 00:34:34,560 --> 00:34:36,530 Það er ekki að fara að vera meira sársaukafullt en það. 999 00:34:36,530 --> 00:34:40,800 Það er ekki að fara að vera n cubed, eða 2 í n, eða eitthvað miklu stærra. 1000 00:34:40,800 --> 00:34:43,800 Þetta er að skilgreina efri mörk á hvað sem kostnaður er. 1001 00:34:43,800 --> 00:34:46,150 Svo í ljósi þess, við skulum íhuga bara nokkur dæmi. 1002 00:34:46,150 --> 00:34:49,820 Og þetta er bara tímabundið listi mjög algengar í gangi sinnum 1003 00:34:49,820 --> 00:34:52,870 fyrir reiknirit sem er ætlað að vera lýsandi sumum hlutum sem við höfum 1004 00:34:52,870 --> 00:34:53,600 séð nú þegar. 1005 00:34:53,600 --> 00:34:58,060 >> Svo til dæmis, í tilviki Val tegund, hvað ég er að segja hér 1006 00:34:58,060 --> 00:35:02,250 er í gangi því vali Raða er tíminn er á röð n veldi. 1007 00:35:02,250 --> 00:35:06,260 Í versta tilfelli, ég ætla að hafa a heild búnt af handahófi tölur hér. 1008 00:35:06,260 --> 00:35:08,600 Og eins og við sáum stærðfræðilega, ef ég halda gangandi 1009 00:35:08,600 --> 00:35:11,310 í gegnum listann, í gegnum lista, velja næsta minnstu 1010 00:35:11,310 --> 00:35:14,410 þáttur aftur og aftur, ef ég í raun skrifa niður öll skrefin 1011 00:35:14,410 --> 00:35:18,750 Ég ætla að taka eins og ég lagði formulaically áður, það er á stærðargráðunni n veldi 1012 00:35:18,750 --> 00:35:20,370 skref sem ég er að taka. 1013 00:35:20,370 --> 00:35:24,520 >> Og það kemur í ljós að kúla flokka og innsetning konar 1014 00:35:24,520 --> 00:35:27,370 eru bara eins og hægur í versta tilfelli. 1015 00:35:27,370 --> 00:35:32,040 Hugleiddu til dæmis, innsetning flokka, mjög síðustu reiknirit við brugðist við, 1016 00:35:32,040 --> 00:35:35,500 sem hafði okkur að líta á frumefni, og þá setja það þar sem það tilheyrir. 1017 00:35:35,500 --> 00:35:38,720 Og þá erum við leit á næsta frumefni, og sett það þar sem það tilheyrir. 1018 00:35:38,720 --> 00:35:40,990 >> Svo telja bestu mögulegu atburðarás. 1019 00:35:40,990 --> 00:35:45,590 Segjum að ég hefði sjálfboðaliðar mínar stilla upp bókstaflega eins og þetta, eitt til átta, 1020 00:35:45,590 --> 00:35:47,440 þegar raðað. 1021 00:35:47,440 --> 00:35:51,300 Hversu mörg skref er innsetning tegund að fara að taka að raða átta manns, 1022 00:35:51,300 --> 00:35:55,640 ef þeir koma á sviðið leita svona? 1023 00:35:55,640 --> 00:35:57,410 >> Átta manns þegar raðað. 1024 00:35:57,410 --> 00:35:58,760 Og ég nota Innsetningarröðun. 1025 00:35:58,760 --> 00:36:02,180 Að síðustu af reiknirit. 1026 00:36:02,180 --> 00:36:03,640 Jæja, við skulum lögleiða alvöru hratt. 1027 00:36:03,640 --> 00:36:05,504 Þannig að ef ég byrja hér, ég sé einn. 1028 00:36:05,504 --> 00:36:06,420 Þar er einn tilheyra? 1029 00:36:06,420 --> 00:36:07,730 Það tilheyrir hérna. 1030 00:36:07,730 --> 00:36:08,330 Ég sé tvo. 1031 00:36:08,330 --> 00:36:09,660 Hvar tveir tilheyra? 1032 00:36:09,660 --> 00:36:10,260 Hérna. 1033 00:36:10,260 --> 00:36:10,900 Ég sé þrjú. 1034 00:36:10,900 --> 00:36:11,920 Hvar þrír tilheyra? 1035 00:36:11,920 --> 00:36:12,480 Hérna. 1036 00:36:12,480 --> 00:36:13,100 >> Ég sé þó fjóra. 1037 00:36:13,100 --> 00:36:13,600 Hérna. 1038 00:36:13,600 --> 00:36:15,660 Fimm, sex, sjö, átta. 1039 00:36:15,660 --> 00:36:17,320 Það er engin ástæða til að endurtaka mig. 1040 00:36:17,320 --> 00:36:21,260 Og svo, hversu mörg skref er að með tilliti til n? 1041 00:36:21,260 --> 00:36:23,870 Það er á röð n skref, ekki satt? n mínus 1. 1042 00:36:23,870 --> 00:36:27,567 En ég tók línulegt fjölda skref, og nú ég er búin. 1043 00:36:27,567 --> 00:36:28,900 Svo er það besta mál, þó. 1044 00:36:28,900 --> 00:36:29,983 Hvað um versta tilfelli? 1045 00:36:29,983 --> 00:36:32,730 Hvað átta voru þarna, og sjö voru þarna niðri, 1046 00:36:32,730 --> 00:36:35,840 og einn og tveir voru hérna, svo að listinn væri sannarlega snúið? 1047 00:36:35,840 --> 00:36:38,300 >> Jæja, hvað gerist örugglega ef þetta er númer? 1048 00:36:38,300 --> 00:36:41,300 Og við munum gera bara nokkrar af dæmum. 1049 00:36:41,300 --> 00:36:49,300 Hvað ef, reyndar númer átta er hér, og number-- Úpps. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Svo hvað ef, reyndar númer átta er alla leið hérna, 1052 00:36:56,430 --> 00:36:57,790 og ég er að nota Innsetningarröðun? 1053 00:36:57,790 --> 00:36:58,290 >> OK. 1054 00:36:58,290 --> 00:37:00,280 Ég kröfu á því augnabliki sem það er í stað. 1055 00:37:00,280 --> 00:37:03,152 En nú, seven-- hvar sjö fara? 1056 00:37:03,152 --> 00:37:04,360 Auðvitað fer það hérna. 1057 00:37:04,360 --> 00:37:06,760 Svo ég verð að fara átta yfir einum stað. 1058 00:37:06,760 --> 00:37:08,554 Nú sex, þar er það að fara? 1059 00:37:08,554 --> 00:37:09,220 Jæja, allt í lagi. 1060 00:37:09,220 --> 00:37:13,150 Nú, ég verð að fara átta yfir staður, og sjö yfir stað, 1061 00:37:13,150 --> 00:37:14,440 og þá er ég plop niður sex. 1062 00:37:14,440 --> 00:37:16,870 >> Svo í fyrsta skipti, það kostar mér eitt skref til að festa það, 1063 00:37:16,870 --> 00:37:18,570 þá kosta mig tvö skref til að festa það. 1064 00:37:18,570 --> 00:37:20,370 Hversu mörg skref er það að fara að taka til að festa 1065 00:37:20,370 --> 00:37:22,720 atriði sem þarf að setja fimm á réttum stað? 1066 00:37:22,720 --> 00:37:23,340 Þrjú. 1067 00:37:23,340 --> 00:37:29,520 Því nú verð ég að færa einn, tveir, þrír. 1068 00:37:29,520 --> 00:37:32,430 Hversu mörg skref er það að fara að taka að setja fjögur á réttum stað? 1069 00:37:32,430 --> 00:37:36,040 4 plús 5, auk 6, plús 7. 1070 00:37:36,040 --> 00:37:40,260 >> Og svo er það stærðfræðilega samhljóða það sem við lýst fyrir vali tagi. 1071 00:37:40,260 --> 00:37:42,130 Við höfum þessa röð það er bara að aukast. 1072 00:37:42,130 --> 00:37:45,650 1 plús 2 plús 3 plús 4, eða öfugt, 7 plús 6 1073 00:37:45,650 --> 00:37:52,610 plús 5 plús 4 bætir upp fyrir dag er tilgangi til á röð n veldi. 1074 00:37:52,610 --> 00:37:57,640 >> Svo láta mig kveða líka að kúla tegund er einnig í n veldi. 1075 00:37:57,640 --> 00:38:01,340 Vegna þess að með kúla tagi, hvert skipti sem ég fer í gegnum listann, 1076 00:38:01,340 --> 00:38:03,100 Ég ætla að taka það bil hversu mörg skref? 1077 00:38:03,100 --> 00:38:06,260 Hvert skipti sem ég bókstaflega ganga þaðan til þar? 1078 00:38:06,260 --> 00:38:07,960 Rúmlega n skrefum. 1079 00:38:07,960 --> 00:38:12,650 En hversu oft gæti ég þurfa að fara í gegnum listann? 1080 00:38:12,650 --> 00:38:13,920 >> Jæja, u.þ.b. n tíma. 1081 00:38:13,920 --> 00:38:15,680 Kannski n mínus 1, en u.þ.b. n sinnum. 1082 00:38:15,680 --> 00:38:16,430 Ja, hvers vegna er það? 1083 00:38:16,430 --> 00:38:19,560 Jæja, með kúla tagi, ef við byrjum með kúla tagi, 1084 00:38:19,560 --> 00:38:23,570 með lista í versta ástand, sem aftur er alveg 1085 00:38:23,570 --> 00:38:25,550 aftur á bak, hvað er að fara að gerast? 1086 00:38:25,550 --> 00:38:28,830 Ég fer í gegnum listann, og fjölda einn tilheyrir alla leið þarna. 1087 00:38:28,830 --> 00:38:33,280 >> En með kúla tegund, hversu langt er einn fara á fyrsta framhjá mér í gegnum listann? 1088 00:38:33,280 --> 00:38:36,620 Hversu margir blettir er hann að fá nær á réttan stað? 1089 00:38:36,620 --> 00:38:37,240 Bara einn. 1090 00:38:37,240 --> 00:38:40,281 Svo ef þú konar ástæða í gegnum þetta, í hvert skipti í gegnum þetta reiknirit, 1091 00:38:40,281 --> 00:38:41,880 Taka u.þ.b. n skrefum Davíðs. 1092 00:38:41,880 --> 00:38:44,940 En hversu margir fer gegnum listinn er það 1093 00:38:44,940 --> 00:38:49,060 að fara að taka fyrir einn til að kúla til vinstri þar sem það tilheyrir? 1094 00:38:49,060 --> 00:38:51,840 >> Hann fékk að fara út, n rými á þennan hátt. 1095 00:38:51,840 --> 00:38:57,960 Svo bara að gera flokkun á listanum, Ég verð að ganga fram og til baka n sinnum. 1096 00:38:57,960 --> 00:39:01,540 Og í hvert sinn, er ég horfa á n þáttum. 1097 00:39:01,540 --> 00:39:05,410 Svo gera n hlutina n sinnum á röð af N veldi. 1098 00:39:05,410 --> 00:39:07,220 >> Nú munum við sjá í sumum af stuttbuxur sem 1099 00:39:07,220 --> 00:39:10,440 eru hluti í næsta vandamál CS50 er sett, nýja nálgun á þetta, 1100 00:39:10,440 --> 00:39:13,490 en nú, við skulum íhuga bara sumir aðrir gangi sinnum, 1101 00:39:13,490 --> 00:39:16,840 sérstaklega ef flokkun sjálfur taka smá tíma til að sökkva í. 1102 00:39:16,840 --> 00:39:21,790 Hvað er algrím sem við höfum séð nú þegar sem tekur á röð n skrefum? 1103 00:39:21,790 --> 00:39:27,560 >> Hvað ætti að taka línulega fjölda skref sem við höfum séð svona langt? 1104 00:39:27,560 --> 00:39:29,350 Hvað er þetta? 1105 00:39:29,350 --> 00:39:30,480 The sími skrá leit. 1106 00:39:30,480 --> 00:39:31,390 Fyrsti reiknirit. 1107 00:39:31,390 --> 00:39:31,560 Ekki satt? 1108 00:39:31,560 --> 00:39:33,650 Þar sem við erum línulega leita Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Einmitt. 1110 00:39:34,150 --> 00:39:37,180 Frá viku núll, þegar ég byrjaði beygja eina síðu í einu, 1111 00:39:37,180 --> 00:39:40,095 og ég sagði jafnvel að það var góður úr línulegri tilfinningu reiknirit, 1112 00:39:40,095 --> 00:39:42,720 og við höfðum þessi mynd á borð við beina rauða línu 1113 00:39:42,720 --> 00:39:44,678 og beina gula lína, þeir voru örugglega 1114 00:39:44,678 --> 00:39:46,810 reiknirit sem eru í stór O í n. 1115 00:39:46,810 --> 00:39:50,680 >> Því að finna Mike Smith í síma bók n síður, í versta tilfelli, 1116 00:39:50,680 --> 00:39:52,422 gæti tekið mig n skrefum. 1117 00:39:52,422 --> 00:39:53,630 Hvað um að taka mætingu? 1118 00:39:53,630 --> 00:39:55,790 Einn, tveir, þrír, fjórir, fimm, sex. 1119 00:39:55,790 --> 00:39:59,420 Hvað er í gangi þegar þetta er Reiknirit til að taka mætingu? 1120 00:39:59,420 --> 00:40:03,070 Stór O af N, vegna þess að í kenningu I að benda öllum í herberginu. 1121 00:40:03,070 --> 00:40:05,861 >> Nú sem innskot, hvað um annað hagræðingu frá viku núll? 1122 00:40:05,861 --> 00:40:08,117 Tvær, fjórar, sex, átta, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 A tölva vísindamaður myndi gera sér grein fyrir, bíddu í eina mínútu, 1124 00:40:10,200 --> 00:40:12,320 það er á röð n deilt með tveimur skrefum. 1125 00:40:12,320 --> 00:40:12,820 Ekki satt? 1126 00:40:12,820 --> 00:40:14,444 Þar sem ég er að gera tvær manneskjur í einu. 1127 00:40:14,444 --> 00:40:17,015 En við erum að fara að hunsa þessir lægri röð hugtök, 1128 00:40:17,015 --> 00:40:19,140 og við erum bara að fara að henda deilum með 2, 1129 00:40:19,140 --> 00:40:21,830 og bara segja, stór O n fyrir þessi reiknirit eins og heilbrigður. 1130 00:40:21,830 --> 00:40:22,760 >> Hvað um þetta? 1131 00:40:22,760 --> 00:40:26,170 Við munum sleppa yfir sumir af þessum, en það var reiknirit sem var log n? 1132 00:40:26,170 --> 00:40:29,900 Það tók um það bil log n skrefum? 1133 00:40:29,900 --> 00:40:30,870 Deilum og sigra. 1134 00:40:30,870 --> 00:40:31,369 Nákvæmlega. 1135 00:40:31,369 --> 00:40:33,900 Eins og símaskrá td í viku núll og fyrr í dag, 1136 00:40:33,900 --> 00:40:36,191 þar sem við skipt vandamál aftur og aftur og aftur. 1137 00:40:36,191 --> 00:40:39,070 Við dró það á borð í vikunni núll sem boginn græna línu, 1138 00:40:39,070 --> 00:40:41,460 og við sögðum um daginn að það væri Logarythmiskur reiknirit. 1139 00:40:41,460 --> 00:40:44,970 >> Og reyndar, fjölda skref IT tekur að framkvæma skipta og sigra, 1140 00:40:44,970 --> 00:40:48,610 eða Tvíundarleit eins og við munum byrja kalla það, sem í símaskránni, 1141 00:40:48,610 --> 00:40:50,680 er á röð þig inn og stíga. 1142 00:40:50,680 --> 00:40:52,470 Og þetta er hluti af a furðulegur einn. 1143 00:40:52,470 --> 00:40:54,910 >> Hvað tekur eitt skref, eða nánar tiltekið 1144 00:40:54,910 --> 00:40:56,240 stöðug tala af skrefum? 1145 00:40:56,240 --> 00:40:58,865 Kannski er það tveir, kannski er það þrír, en tölvunarfræðingur bara 1146 00:40:58,865 --> 00:41:01,423 einfaldar það sem stór O 1, sumir stöðug tala af skrefum. 1147 00:41:01,423 --> 00:41:04,256 Hvað er eitthvað sem þú gætir gert það tekur stöðugt fjölda skrefum? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Hvað er í gangi tími clapping? 1150 00:41:10,930 --> 00:41:11,920 Constant tíma. 1151 00:41:11,920 --> 00:41:12,420 Ekki satt? 1152 00:41:12,420 --> 00:41:15,490 Eins og, hvað er í gangi tími gera eitthvað sem tekur bara einn 1153 00:41:15,490 --> 00:41:18,570 rekstur, eins prenta F Halló heimur. 1154 00:41:18,570 --> 00:41:24,110 Það gæti verið sagt að vera stöðug tími, nema minna horn tilfelli Prenta F, 1155 00:41:24,110 --> 00:41:28,260 hvað gæti hlaupandi tími prenta F raunverulega vera? 1156 00:41:28,260 --> 00:41:28,790 Og hvers vegna? 1157 00:41:28,790 --> 00:41:30,550 Hvað er n mæla í því tilviki? 1158 00:41:30,550 --> 00:41:32,251 >> Áhorfendur: [inaudible]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. Malan: Einmitt. 1160 00:41:33,250 --> 00:41:34,900 Fjöldi stafa við viljum prenta. 1161 00:41:34,900 --> 00:41:36,191 Svo er það mjög samhengi næmur. 1162 00:41:36,191 --> 00:41:39,910 Í dag höfum við verið að einblína mikið á bókstafir og tölur hér á borð. 1163 00:41:39,910 --> 00:41:43,540 En það gæti líka verið stafir í raunverulegum streng. 1164 00:41:43,540 --> 00:41:46,420 Svo kemur í ljós að það er annað mælikvarði sem hefst umhyggju um, 1165 00:41:46,420 --> 00:41:48,530 og það er hið gagnstæða af stór O, svo að segja. 1166 00:41:48,530 --> 00:41:50,120 >> Það er ómega tákn. 1167 00:41:50,120 --> 00:41:53,380 En stór O þýðir hvað er, sem efri mörk keyra þinn tími? 1168 00:41:53,380 --> 00:41:55,580 Hámarks, hversu mikinn tíma gæti eitthvað taka? 1169 00:41:55,580 --> 00:41:59,250 Omega-- miður þetta heldur áfram að koma up-- er andstæða þess, 1170 00:41:59,250 --> 00:42:02,960 þar sem það er neðri mörk á Fjárhæð tíma eitthvað gæti tekið. 1171 00:42:02,960 --> 00:42:10,480 >> So. til dæmis, hvað er reiknirit sem tekur alltaf n veldi skref? 1172 00:42:10,480 --> 00:42:15,600 Jæja, einn af reiknirit sem við höfum séð í dag, í raun, gæti verið þessi eins og heilbrigður. 1173 00:42:15,600 --> 00:42:16,720 Val tegund. 1174 00:42:16,720 --> 00:42:18,270 Val tegund er frekar heimskur. 1175 00:42:18,270 --> 00:42:21,760 Jafnvel þótt algorithm-- miður, jafnvel ef array er þegar raðað, 1176 00:42:21,760 --> 00:42:24,150 Val tegund er að fara að halda gangandi í gegnum listann 1177 00:42:24,150 --> 00:42:28,907 að ganga úr skugga um að það hefur minnstu þáttur aftur og aftur og aftur. 1178 00:42:28,907 --> 00:42:31,740 Og jafnvel þó að þú menn í áhorfendur vita að, bíddu í eina mínútu, 1179 00:42:31,740 --> 00:42:33,948 þú staðist nú þegar Minnsta þáttur, the tölva 1180 00:42:33,948 --> 00:42:37,300 veit ekki að fyrr en það lítur alla leið í gegnum listann. 1181 00:42:37,300 --> 00:42:40,240 Á sama hátt, er lægri mörk sem gæti líka að taka tillit til 1182 00:42:40,240 --> 00:42:42,000 gæti verið línuleg tími. 1183 00:42:42,000 --> 00:42:48,260 >> Hversu mikinn tíma tekur það að raða n þættir í besta 1184 00:42:48,260 --> 00:42:52,420 Málið nota eitthvað eins og kúla tegund? 1185 00:42:52,420 --> 00:42:54,280 Segjum listinn er þegar raðað. 1186 00:42:54,280 --> 00:42:56,696 Við sögðum kúla tegund tekur á röð n veldi skrefum. 1187 00:42:56,696 --> 00:42:59,640 En hvað ef það er þegar raðað? 1188 00:42:59,640 --> 00:43:02,310 Hvað ef þér grein eftir einn að fara í gegnum array 1189 00:43:02,310 --> 00:43:03,540 sem þú hefur ekki gert neinar skiptasamninga? 1190 00:43:03,540 --> 00:43:05,970 Þarft þú að halda að meira fer? 1191 00:43:05,970 --> 00:43:06,470 >> Nei 1192 00:43:06,470 --> 00:43:10,340 Svo lægri mörk á kúla tegund mætti ​​segja að línuleg. 1193 00:43:10,340 --> 00:43:11,830 Omega á n. 1194 00:43:11,830 --> 00:43:14,450 Og við getum litið á aðrir af þessum eins og heilbrigður. 1195 00:43:14,450 --> 00:43:17,990 Svo skulum taka a fljótur líta á bara visualization hér 1196 00:43:17,990 --> 00:43:20,790 til að sjá hvernig þetta aðgreina sig. 1197 00:43:20,790 --> 00:43:24,592 Ég ætla að fara niður hér í þessu síðu sem er í boði á heimasíðu C50 er, 1198 00:43:24,592 --> 00:43:27,550 en það mun vera a sársauki til að fá að vinna, þar sem það notar tækni sem kallast 1199 00:43:27,550 --> 00:43:30,560 Java forrit, sem er mestu óstudd þessa dagana, 1200 00:43:30,560 --> 00:43:32,730 að minnsta kosti með Chrome og tilteknum öðrum. 1201 00:43:32,730 --> 00:43:37,070 >> Og láta mig fara á undan og flýta þessu upp og útskýra hvað er að gerast. 1202 00:43:37,070 --> 00:43:40,840 Þetta er sýning á kúla tegund, fyrsta reiknirit við skoðuðum. 1203 00:43:40,840 --> 00:43:43,950 Og það er visualization í að hver þessara börum táknar númer. 1204 00:43:43,950 --> 00:43:45,710 The allstór bar, því stærri númer. 1205 00:43:45,710 --> 00:43:47,520 Minni á barnum, minni númer. 1206 00:43:47,520 --> 00:43:50,353 Og það sem þú getur séð sjónrænt, jafnvel en þetta er að fara frábær fljótur, 1207 00:43:50,353 --> 00:43:53,699 er að rauða bar er eins og mig, ganga fram og til baka ákveða vandamál. 1208 00:43:53,699 --> 00:43:56,740 Þú getur séð að stærri þætti eru örugglega freyðandi upp til hægri, 1209 00:43:56,740 --> 00:43:59,650 og smærri þætti eru freyðandi upp til vinstri. 1210 00:43:59,650 --> 00:44:01,870 Og hérna, ef við í raun líta betur, 1211 00:44:01,870 --> 00:44:04,330 getum við í raun að telja Fjöldi samanburð og skiptasamninga 1212 00:44:04,330 --> 00:44:05,350 sem voru gerðar. 1213 00:44:05,350 --> 00:44:07,360 >> En í staðinn, við skulum líta á seinni reiknirit 1214 00:44:07,360 --> 00:44:11,240 við skoðuðum áðan með okkar sjálfboðaliðar, val tagi. 1215 00:44:11,240 --> 00:44:13,500 Sjónrænt, það hefur a mjög mismunandi áhrif. 1216 00:44:13,500 --> 00:44:16,820 En það er, aftur, mjög leiðandi, í að við höldum að velja næsta minnstu 1217 00:44:16,820 --> 00:44:18,660 þáttur, og við fengum smá heppinn. 1218 00:44:18,660 --> 00:44:20,110 Það fannst í grundvallaratriðum hraðar. 1219 00:44:20,110 --> 00:44:22,840 En ef við hljóp þetta aftur og aftur og aftur með fullt af inntak, 1220 00:44:22,840 --> 00:44:26,680 myndum við sjá að það er örugglega enn í stóru O í n veldi. 1221 00:44:26,680 --> 00:44:29,920 >> Skulum gera eitt síðasta eitt hér, innsetning flokka, 1222 00:44:29,920 --> 00:44:33,180 sem var þriðja reiknirit við skoðuðum, og muna 1223 00:44:33,180 --> 00:44:36,700 að þetta fjallar um þættir eins og það kynni þá, 1224 00:44:36,700 --> 00:44:39,290 En þá kannski vaktir það yfir til að gera pláss, 1225 00:44:39,290 --> 00:44:41,660 setja þætti þar sem þeir tilheyra. 1226 00:44:41,660 --> 00:44:45,330 >> Og þetta endar líka upp sem gefur Endanleg niðurstaða. Nú öll þrjú af þeim 1227 00:44:45,330 --> 00:44:46,490 fannst nokkuð hratt. 1228 00:44:46,490 --> 00:44:48,740 Og reyndar, ég hljóp þá á mjög góðu bút. 1229 00:44:48,740 --> 00:44:52,510 En í grundvallaratriðum, þeir eru allt nokkuð hræðilegt, að vera heiðarlegur. 1230 00:44:52,510 --> 00:44:56,960 Öll þessi reiknirit svona langt sem keyra í stóru O á n veldi 1231 00:44:56,960 --> 00:44:59,270 taka töluvert af tími til að hlaupa í lokin. 1232 00:44:59,270 --> 00:45:01,920 >> Og reyndar, getum við séð og finnst þetta loks 1233 00:45:01,920 --> 00:45:04,090 ef ég draga upp þessa þriðja og síðasta kynningu. 1234 00:45:04,090 --> 00:45:05,840 Þetta er annar visualization það er að fara 1235 00:45:05,840 --> 00:45:08,500 að sýna kúla tegund á vinstri val raða í miðju, 1236 00:45:08,500 --> 00:45:13,410 og eitthvað, eins og einn af okkar hönd vekur fyrr leiðbeinandi, 1237 00:45:13,410 --> 00:45:15,020 Mergesort á hægri. 1238 00:45:15,020 --> 00:45:16,937 A skipta og sigra stefnu til hægri. 1239 00:45:16,937 --> 00:45:19,520 Og það er í raun, hvað við erum fara að horfa á miðvikudaginn. 1240 00:45:19,520 --> 00:45:21,990 En við skulum tíma þessar til að keyra samhliða. 1241 00:45:21,990 --> 00:45:26,765 Það er u.þ.b. sama fjölda þætti, allt í gangi á sama tíma. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble konar vs val raða vs mergesort. 1244 00:45:34,440 --> 00:45:36,760 >> Nú, þeir eru allir hlaupandi í kenningu á sama tíma. 1245 00:45:36,760 --> 00:45:39,830 The CPU er í gangi á sama hraða, en þú 1246 00:45:39,830 --> 00:45:44,014 finn hvernig leiðinlegur þetta er mjög fljótt að fara að verða, 1247 00:45:44,014 --> 00:45:45,930 og hversu hratt þegar við sprauta smá vikunnar 1248 00:45:45,930 --> 00:45:49,330 reiknirit Zero getur við að hraða hlutum upp. 1249 00:45:49,330 --> 00:45:51,760 >> Og nú skulum bera saman þessir í eitt síðasta formi. 1250 00:45:51,760 --> 00:45:55,710 Ég ætla að fara á undan á vefsvæðið CS50, þar 1251 00:45:55,710 --> 00:45:59,020 við höfum þetta endanlega tengil fyrir í dag, þar sem einhver á internetinu 1252 00:45:59,020 --> 00:46:03,960 vinsamlega setja saman vídeó sem fangar hvað mismunandi flokkun 1253 00:46:03,960 --> 00:46:07,510 reiknirit hljóma. 1254 00:46:07,510 --> 00:46:09,577 Þetta er innsetning tegund. 1255 00:46:09,577 --> 00:46:12,072 >> [Bíphljóð] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Þar sem þú ert að sækja um tíðni miðað við hæð bar bar. 1258 00:46:16,850 --> 00:46:19,826 Þetta er kúla tegund. 1259 00:46:19,826 --> 00:46:21,822 >> [Vinda Bíphljóð] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Tilkoma upp næsta is-- koma upp næsta is-- val flokka, 1262 00:46:45,774 --> 00:46:48,820 þar aftur, við erum að velja næsta minnstu þáttur, 1263 00:46:48,820 --> 00:46:51,820 og við getum séð það vaxa frá vinstri til hægri. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Mergesort, sigurvegari okkar svona langt í dag. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Taktu eftir hvernig það er að deila hlutum í [inaudible] hálfleik og ársfjórðunga. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome tegund, sem við höfum ekki talaði um, og skapar sjónrænt 1270 00:47:21,660 --> 00:47:24,450 og audally smá a mismunandi lögun og hljóð. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Fara fram og til baka, þrífa það upp. 1273 00:47:30,160 --> 00:47:32,230 Einnig skrá sig út heapsort á vefsíðu Þessi strákur er. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Og það er það. 1276 00:47:36,810 --> 00:47:38,210 Við munum sjá þig næst. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [WHOOSHING AND MUSIC] 1279 00:47:48,334 --> 00:50:24,839