1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Muusika mängib] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. Humala: See on CS50. 5 00:00:12,550 --> 00:00:14,612 Ja see on algusest nädalal kolm. 6 00:00:14,612 --> 00:00:16,820 Nii on meil palju põnevaid asju katteks täna. 7 00:00:16,820 --> 00:00:20,160 Palju võimalusi vabatahtlike laval. 8 00:00:20,160 --> 00:00:22,780 Ja lõpuks, täna on ei tähenda koodi üldse. 9 00:00:22,780 --> 00:00:24,820 Aga see on umbes ideid ja see on umbes algoritme, 10 00:00:24,820 --> 00:00:28,420 ja tegelikult toob tagasi mõned õppetunnid nädalal null, 11 00:00:28,420 --> 00:00:31,910 kus mäletate, me tutvustas seda Kaameus. 12 00:00:31,910 --> 00:00:33,880 Ka laenamine inspiratsiooni sellest, et alustada 13 00:00:33,880 --> 00:00:36,879 lahendada üha keerukamaid probleeme algoritmiliselt. 14 00:00:36,879 --> 00:00:38,420 Aga kõigepealt paar teadaandeid. 15 00:00:38,420 --> 00:00:42,020 Nii et üks, kui soovid liituda CS50 töötajad ja klassikaaslastega lõunasöögi 16 00:00:42,020 --> 00:00:44,670 sel reedel, nii siin kui Cambridge ja New Haven, 17 00:00:44,670 --> 00:00:48,060 külasta kursuse veebileht, kus URL võib leida. 18 00:00:48,060 --> 00:00:50,390 Loeng seda kolmapäeval ei ole siin Sanders. 19 00:00:50,390 --> 00:00:53,610 See on ainult võrgus, nii et häälestama CS50 veebisaidil 20 00:00:53,610 --> 00:00:55,850 kas siin Cambridge või New Haven samuti. 21 00:00:55,850 --> 00:00:58,110 >> Ja siis probleem seatud kaks on juba pihus. 22 00:00:58,110 --> 00:01:03,067 Kui te ei ole sukeldus veel, lubage mul pakkuda tugevalt sõnastatud ettepanek 23 00:01:03,067 --> 00:01:05,150 et eriti nüüd, kui probleem seab ette, 24 00:01:05,150 --> 00:01:08,669 sa tõesti tahad hakata nüüd, kui ei ole võõpama natuke nädalavahetusel või enne 25 00:01:08,669 --> 00:01:10,710 kui nad esimest korda minema Reedeti, sest sa oled 26 00:01:10,710 --> 00:01:14,380 leiavad, et nad ei ole tingimata saada enam või rohkem väljakutseid kohta 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Ma arvan, et sa leiad, et Üldiselt nad kipuvad võtma umbes 29 00:01:17,575 --> 00:01:18,892 umbes sama palju aega. 30 00:01:18,892 --> 00:01:20,850 Aga see sõltub kindlasti õpilase ja see 31 00:01:20,850 --> 00:01:22,880 sõltub mõtteviisi kellega läheneda. 32 00:01:22,880 --> 00:01:24,910 Aga alati, sa lähed eel vastu mõne seina, 33 00:01:24,910 --> 00:01:26,350 ja sa lähed lüüa mõned bug, ja sa oled lihtsalt 34 00:01:26,350 --> 00:01:27,950 ei hakka saama sellest üle saada mingil ajahetkel. 35 00:01:27,950 --> 00:01:31,380 Ja see on väga väärtuslik, et oleks võimalik sammu kaugusel, tulevad tagasi järgmisel päeval, 36 00:01:31,380 --> 00:01:35,286 minna tööaega postitust CS50 Arutle vms, tegelikult saada vabastada. 37 00:01:35,286 --> 00:01:36,160 Nii et hoidke seda silmas pidades. 38 00:01:36,160 --> 00:01:40,830 Alates esimesel võimalusel on parim asi, mida saate teha. 39 00:01:40,830 --> 00:01:44,160 Nii et siin on, kust me alustasime klassi, üle nädala null. 40 00:01:44,160 --> 00:01:47,441 Ja me saame vabatahtlikuna siin, et aidata mul leida mikrofoni? 41 00:01:47,441 --> 00:01:47,940 OKEI. 42 00:01:47,940 --> 00:01:48,900 Püsti juba. 43 00:01:48,900 --> 00:01:50,080 Tule üles. 44 00:01:50,080 --> 00:01:53,707 Arvan, et see, kuidas see läheb tööle. 45 00:01:53,707 --> 00:01:54,415 Mis su nimi on? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 DAVID J. Humala: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Tule üles. 49 00:01:57,910 --> 00:01:58,619 Meeldiv tutvuda. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Meeldiv kohtuda. 51 00:01:59,910 --> 00:02:02,772 DAVID J. Humala: Ja siin olid meiega nädalal null, muidugi. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: olin. 53 00:02:03,028 --> 00:02:03,160 Ma olin. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. Humala: Nii võiks minna käia ja leida meile Mike Smith, 55 00:02:05,868 --> 00:02:08,639 nii kiiresti kui võimalik? 56 00:02:08,639 --> 00:02:10,639 Nii kiiresti kui võimalik. 57 00:02:10,639 --> 00:02:13,756 Sõna otseses mõttes pisaravool probleem poole kui vaja. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. Humala: Sõna-sõnalt pisaravool probleemi poole. 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 Väga hasti. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. Humala: OK. 65 00:02:23,700 --> 00:02:24,200 Väga hea. 66 00:02:24,200 --> 00:02:24,701 Aitäh. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Väga hea. 68 00:02:25,700 --> 00:02:26,210 OKEI. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. Humala: Ja nii nüüd, olete whittled see alla 70 00:02:27,610 --> 00:02:29,320 poolega Probleemi suurus. 71 00:02:29,320 --> 00:02:31,267 Nüüd me oleme alla veerandi. 72 00:02:31,267 --> 00:02:33,475 Kas olete pöörates tähelepanu millisel poolel me hoida? 73 00:02:33,475 --> 00:02:34,405 >> [Naerab] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Jah, ma think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. Humala: Mis osa on meil? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: sallid, nii. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. Humala: OK. 78 00:02:39,941 --> 00:02:42,810 Aga Mike Smith läheb olla pärast sallid. 79 00:02:42,810 --> 00:02:44,130 So-- 80 00:02:44,130 --> 00:02:48,180 >> [Naerab] 81 00:02:48,180 --> 00:02:48,742 >> Hästi. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Kus me otsime? 83 00:02:50,200 --> 00:02:52,049 DAVID J. Humala: 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. Humala: Nüüd me oleme kirurgia. 86 00:02:54,760 --> 00:02:57,840 Nüüd, arstid. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- lähme päris. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. Humala: Real. 91 00:03:00,970 --> 00:03:01,470 OKEI. 92 00:03:01,470 --> 00:03:03,700 Kui teil on vaja Real. 93 00:03:03,700 --> 00:03:05,250 Nüüd, mil moel on Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Nii. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. Humala: Millist teed? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Oota. 97 00:03:08,240 --> 00:03:08,790 M on-- õige? 98 00:03:08,790 --> 00:03:09,110 Alustasime with-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. Humala: Jah. 100 00:03:10,090 --> 00:03:10,650 Nad lahkusid. 101 00:03:10,650 --> 00:03:11,430 Teie õigus. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Jah. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. Humala: Nii Mike'i siin. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Mis? 105 00:03:13,990 --> 00:03:14,665 >> [Naerab] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Bad näiteks poisid. 108 00:03:18,330 --> 00:03:18,830 Vabandust. 109 00:03:18,830 --> 00:03:21,610 DAVID J. Humala: See õpetab sa hüpe läbi oma toolil. 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 Sain su kätte. 113 00:03:23,390 --> 00:03:24,670 Sain su kätte. 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 See on-- OK, ma sain sulle. 117 00:03:26,812 --> 00:03:27,520 Smith siin? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. Humala: Smith, aitäh. 119 00:03:28,894 --> 00:03:30,535 Nii et ma hoian soojaks Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, jah. 121 00:03:30,790 --> 00:03:31,340 Ei ei ei. 122 00:03:31,340 --> 00:03:31,600 Oh ei. 123 00:03:31,600 --> 00:03:31,940 See on minu. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. Humala: Oh, sul Smith. 125 00:03:32,580 --> 00:03:33,415 OKEI. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Jah, ma sain Smith siin. 127 00:03:34,040 --> 00:03:34,700 Vabandame, poisid. 128 00:03:34,700 --> 00:03:35,860 Ma arvasin, et Michael-- me otsisid Michael. 129 00:03:35,860 --> 00:03:36,550 Vabandust. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. Humala: See on OK. 131 00:03:37,550 --> 00:03:39,950 Olgu, nüüd oleme arvesse Paccini ja Pojad. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini ja pojad. 133 00:03:41,242 --> 00:03:43,158 DAVID J. Humala: Ainult sina ja ma on sellel. 134 00:03:43,158 --> 00:03:44,050 OKEI. 135 00:03:44,050 --> 00:03:45,130 Leia meid 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. Humala: Smith. 139 00:03:46,750 --> 00:03:47,728 Me oleme R prügi. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Prahi. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 See läheb veidi aega võtta. 143 00:03:52,480 --> 00:03:54,340 >> [Naerab] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. Humala: Shoes. 146 00:03:56,720 --> 00:03:58,080 Oleme kingad. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Nüüd oleme gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. Humala: Nice. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: misjärjekorras 150 00:04:01,980 --> 00:04:03,620 [Naerab] 151 00:04:03,620 --> 00:04:05,440 Oh, see on hea. 152 00:04:05,440 --> 00:04:06,910 [Naerab] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. Humala: See on OK. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, see on hea. 156 00:04:11,365 --> 00:04:14,425 Ma ei usu, et ma lähen on PSAT semud pärast seda. 157 00:04:14,425 --> 00:04:15,300 DAVID J. Humala: Hea. 158 00:04:15,300 --> 00:04:16,078 Spordi. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporting. 160 00:04:17,036 --> 00:04:18,668 Um, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 DAVID J. Humala: OK. 162 00:04:19,459 --> 00:04:21,600 Nii saab pisar see pooleks. 163 00:04:21,600 --> 00:04:22,270 See on OK. 164 00:04:22,270 --> 00:04:25,606 See lõpeb halvasti niikuinii, sest Mike Smith ei ole kollased leheküljed. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. Humala: Ei, see on OK. 167 00:04:27,140 --> 00:04:28,930 Aga olgem teeselda, nagu ta on sellel lehel. 168 00:04:28,930 --> 00:04:33,260 Nüüd, kui olete whittled probleemi alla ühe lehekülje, ja leidsime Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Hõiskab] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 OK aitäh sulle. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 OKEI. 174 00:04:41,200 --> 00:04:43,646 See oli erakordne. 175 00:04:43,646 --> 00:04:45,954 Aga see oli veel kiirem kui lineaarne otsing, 176 00:04:45,954 --> 00:04:47,870 kus hakkame juures alguses raamat, 177 00:04:47,870 --> 00:04:51,210 ja me liigume meie teed vasakult paremale, lõpuks otsin Mike Smith. 178 00:04:51,210 --> 00:04:53,540 Ja nii, kui telefoniraamatus oli äkki 1000 lehekülge, 179 00:04:53,540 --> 00:04:56,300 võibolla see oleks võtnud meil 10 või nii lehele pisaraid. 180 00:04:56,300 --> 00:04:59,380 >> Aga sa võisid võimendatud puudutanud oletus 181 00:04:59,380 --> 00:05:03,602 käigus kõik see, mis on öelda et telefoniraamatust eelnevalt oli siis? 182 00:05:03,602 --> 00:05:04,310 Sihtrühm: sorteerida. 183 00:05:04,310 --> 00:05:05,000 DAVID J. Humala: See on järjestatud. 184 00:05:05,000 --> 00:05:05,160 Õigus? 185 00:05:05,160 --> 00:05:07,909 See on tähestikulises järjekorras, nii et et kõik need nimed ja numbrid 186 00:05:07,909 --> 00:05:11,230 on järjestatud alates A kuni Z ja tähestikuliselt vahel. 187 00:05:11,230 --> 00:05:13,100 Aga täna on meil nüüd küsida küsimus, noh, 188 00:05:13,100 --> 00:05:16,170 Kuidas Verizon või telefon Ettevõte saada see, et riik? 189 00:05:16,170 --> 00:05:19,560 >> Sest see on üks asi, mida võimendada selle eelduse, mistõttu 190 00:05:19,560 --> 00:05:22,570 lahendada probleemi, mille algoritmi efektiivsemalt. 191 00:05:22,570 --> 00:05:24,900 Aga me kunagi küsis nädala null, noh, 192 00:05:24,900 --> 00:05:27,790 kui palju see maksis Verizon või keegi teine 193 00:05:27,790 --> 00:05:29,620 saada see telefoniraamat sorteeritud järjekorras? 194 00:05:29,620 --> 00:05:29,780 >> Õigus? 195 00:05:29,780 --> 00:05:31,529 Ei ole oluline, kui soojaks Mike Smith 196 00:05:31,529 --> 00:05:35,190 on super kiire, kui see viib teid aasta sorteerida lehekülge esialgu. 197 00:05:35,190 --> 00:05:35,690 Õigus? 198 00:05:35,690 --> 00:05:38,620 Sa võid ka lihtsalt sõeluma läbi randomiseeritud telefoniraamat, 199 00:05:38,620 --> 00:05:40,690 kui see saab olema super kallis sortida. 200 00:05:40,690 --> 00:05:42,350 Nii et kui meil on veel üks vabatahtlik. 201 00:05:42,350 --> 00:05:46,350 Võtame otsida siin kuidas me might-- tule up-- kuidas 202 00:05:46,350 --> 00:05:48,100 me võiks minna sorteerimine neid. 203 00:05:48,100 --> 00:05:51,990 >> Ja kui Jordan võiks tegelikult liitu meiega siin laval. 204 00:05:51,990 --> 00:05:55,100 Tule üles hetkeks. 205 00:05:55,100 --> 00:05:56,359 Mis su nimi on? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. Humala: Caroline, tule üles. 208 00:05:58,691 --> 00:06:02,070 Ja siis saad liitus minu ja Jordaania siin. 209 00:06:02,070 --> 00:06:03,800 Caroline, aitäh. 210 00:06:03,800 --> 00:06:04,300 Hästi. 211 00:06:04,300 --> 00:06:08,330 Mis meil siin Caroline on 26 sinine raamatud 212 00:06:08,330 --> 00:06:10,747 et FAS kasutab hallata Teatud lõpueksamid. 213 00:06:10,747 --> 00:06:13,330 Need saavad raske leida, aga mida me oleme teinud eelnevalt 214 00:06:13,330 --> 00:06:15,800 on see, et me panime kellegi nime esiküljel kummagi, 215 00:06:15,800 --> 00:06:18,133 kuid me oleme hoidnud it simple Seejärel paneb välja täisnimed. 216 00:06:18,133 --> 00:06:22,720 Nii et me paneks isiku nime L, D, J, B, kõik viis A kuni Z, 217 00:06:22,720 --> 00:06:24,090 kuid nad juhuslikus järjekorras. 218 00:06:24,090 --> 00:06:26,890 Ja kui sa oleks, räägi oma tee läbi probleem kui 219 00:06:26,890 --> 00:06:31,620 seda teha, võite minna ja sorteeri need meile A kuni Z. 220 00:06:31,620 --> 00:06:34,070 >> Sihtrühm: OK, nii et L on nagu, keset. 221 00:06:34,070 --> 00:06:35,050 C hakkab. 222 00:06:35,050 --> 00:06:42,410 B. J enne L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. Humala: Hoia, et arvas üks sekund. 224 00:06:45,140 --> 00:06:48,910 Sest muidu on see vaid huvitav teile, mina ja Jordan. 225 00:06:48,910 --> 00:06:49,724 Seal me läheme. 226 00:06:49,724 --> 00:06:50,640 Sihtrühm: [kuuldamatu]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. Humala: OK. 229 00:06:58,090 --> 00:06:59,310 Mida sa teed? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M tuleb pärast O. 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. Humala: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. Humala: O, hea. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> DAVID J. Humala: E, F. Jah. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V 237 00:07:07,620 --> 00:07:10,689 >> DAVID J. Humala: V, T, U, V Seega Tundub, et sa oled making-- edasi. 238 00:07:10,689 --> 00:07:12,730 Tundub, et sa üritad suur kuhi siin, 239 00:07:12,730 --> 00:07:13,910 ja selline suur kuhi seal. 240 00:07:13,910 --> 00:07:16,230 Nii et esimene pool tähestikku, teisel poolel tähestikku. 241 00:07:16,230 --> 00:07:16,460 OKEI. 242 00:07:16,460 --> 00:07:16,960 Väga hea. 243 00:07:16,960 --> 00:07:19,680 Kind of jagada probleem kaks. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Jah. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. Humala: OK. 247 00:07:22,980 --> 00:07:25,070 K. Nii et sa oled selline valides neid üksteise järel, 248 00:07:25,070 --> 00:07:27,620 paneb see kas vasakule või paremale, või Z läheb põrandale. 249 00:07:27,620 --> 00:07:28,012 OKEI. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z läheb põrandale. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. Humala: OK. 252 00:07:29,360 --> 00:07:30,920 Y läheb põrandale. 253 00:07:30,920 --> 00:07:31,735 Nüüd saame panna X. 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 DAVID J. Humala: G läheb vasakule. 256 00:07:33,700 --> 00:07:36,017 S läheb paremale. 257 00:07:36,017 --> 00:07:37,642 Olgu A läheb kogu tee vasakule. 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. Humala: Nüüd hea. 260 00:07:39,873 --> 00:07:43,260 Meil A, B, C W läheb sinna. 261 00:07:43,260 --> 00:07:45,566 Olgu, 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. Humala: H, I, J. hea. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: Keskel, ma gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. Humala: OK. 266 00:07:50,000 --> 00:07:52,375 Nüüd, me ei kavatse sellist ning ühendada need erinevad vaiad. 267 00:07:52,375 --> 00:08:00,730 Nii A-C, siis ma näen D, ja E, F, ja G ja H ning I. Nice. 268 00:08:00,730 --> 00:08:05,540 J, K. Ja siis see pakk on tagurpidi, kuid see on OK. 269 00:08:05,540 --> 00:08:06,040 Muidugi. 270 00:08:06,040 --> 00:08:07,240 Me ei lõigata mõned nurgad. 271 00:08:07,240 --> 00:08:07,950 OKEI. 272 00:08:07,950 --> 00:08:10,530 Ja siis me peame W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Jah. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. Humala: Suurepärane. 275 00:08:11,880 --> 00:08:14,122 Nii suur aitäh Caroline sorteerimiseks neid. 276 00:08:14,122 --> 00:08:15,030 >> [Hõiskab] 277 00:08:15,030 --> 00:08:17,287 >> Aitäh. 278 00:08:17,287 --> 00:08:18,120 Tänan teid väga. 279 00:08:18,120 --> 00:08:22,910 Nüüd Vaatleme korraks kuidas Caroline läks seda teed, et 280 00:08:22,910 --> 00:08:26,040 ja mida täpselt me suutsid mina-- kuidas me 281 00:08:26,040 --> 00:08:28,409 suutsid lahendada seda probleem siis, kui me olime lihtsalt 282 00:08:28,409 --> 00:08:29,950 antud terve hunnik juhuslikult sisendeid. 283 00:08:29,950 --> 00:08:31,610 >> Noh, tundub, et seal oli natuke süsteem seal? 284 00:08:31,610 --> 00:08:32,110 Õigus. 285 00:08:32,110 --> 00:08:34,495 Nii et varasemad kirjad tähestiku, ta 286 00:08:34,495 --> 00:08:37,120 pani vasakule, ja hiljem tähed tähestikus, 287 00:08:37,120 --> 00:08:38,270 ta paneb õigesse. 288 00:08:38,270 --> 00:08:40,500 Ja niipea, kui ta leidis, mõned proksimaalne tähed, need 289 00:08:40,500 --> 00:08:43,124 et minna paremale üksteise kõrval, ta paneks neid selleks. 290 00:08:43,124 --> 00:08:46,750 Ja nii me pidime need väikesed hunnikud sorteeritud mille sagedus. 291 00:08:46,750 --> 00:08:50,540 >> Ja nii see on päris see, mida enamik meist inimesed teeksid. 292 00:08:50,540 --> 00:08:53,530 Meil oleks justkui sõeluma läbi, ja me tahaks sellist olema mehhanism. 293 00:08:53,530 --> 00:08:56,930 Aga see võib olla raske kirjutada Kirjutage see valem per se. 294 00:08:56,930 --> 00:08:59,010 Tundus veidi rohkem orgaanilisi kui see. 295 00:08:59,010 --> 00:09:02,560 Vaatame, kas me saame nüüd seotud Probleemi vähemate sisendeid. 296 00:09:02,560 --> 00:09:05,170 >> Selle asemel, et 26, olgem midagi märksa vähem 297 00:09:05,170 --> 00:09:09,890 lihtsalt öelda, seitse, taga Nende uste niiöelda. 298 00:09:09,890 --> 00:09:11,300 Kas on ainult seitse numbrid? 299 00:09:11,300 --> 00:09:15,240 Ja kui eesmärk nüüd Samas on leida väärtus, 300 00:09:15,240 --> 00:09:17,850 Vaatame, kuidas tõhusalt saame minna seda teed. 301 00:09:17,850 --> 00:09:22,460 Ja vaatame, kas me saame nüüd hakkavad kehtima mõned numbrid, 302 00:09:22,460 --> 00:09:26,310 või mõne valemid kellega kirjeldamiseks tõhusust meie telefoniraamat 303 00:09:26,310 --> 00:09:31,060 algoritm, meie eksam raamat algoritm, ja üldisemalt informatsiooni leidmine. 304 00:09:31,060 --> 00:09:34,770 >> Nii see, lubage mul minna, ja puuteekraanil siin, 305 00:09:34,770 --> 00:09:41,100 panna veebibrauser, mis on just need seitse uksed. 306 00:09:41,100 --> 00:09:46,670 Ja kui me saaksime veel ühe vabatahtlikuna tulge siia, 307 00:09:46,670 --> 00:09:48,480 Ma panin need samad uksed siin. 308 00:09:48,480 --> 00:09:49,170 Quick vabatahtlikuna. 309 00:09:49,170 --> 00:09:51,130 >> See one-- demos ei kavatse kiiremale ja kiirem nüüd. 310 00:09:51,130 --> 00:09:51,600 Tule alla. 311 00:09:51,600 --> 00:09:52,308 Mis su nimi on? 312 00:09:52,308 --> 00:09:53,040 Trevor: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> DAVID J. Humala: Trevor? 314 00:09:53,998 --> 00:09:55,770 Olgu, Trevor, tule alla. 315 00:09:55,770 --> 00:09:59,212 Nii Trevor on vabatahtlikult siia teha sarnane probleem, kuid see on 316 00:09:59,212 --> 00:10:02,170 kitsam ja mis läheb et saaksime proovida vormistama nüüd 317 00:10:02,170 --> 00:10:03,970 Protsessi sorteerimiseks need numbrid. 318 00:10:03,970 --> 00:10:05,500 >> Nii Trevor, nice to meet you. 319 00:10:05,500 --> 00:10:08,720 Nii et siin on massiiv, nii et rääkida, nimekirja seitsmest uksed. 320 00:10:08,720 --> 00:10:10,327 Lase käia ja leida meile number 50. 321 00:10:10,327 --> 00:10:12,410 Ja siis pärast fakti, ütle meile, kuidas sa leidsid. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Kui olla-- kõik korras. 324 00:10:20,040 --> 00:10:21,945 Jah, see on üks siin? 325 00:10:21,945 --> 00:10:24,680 Uh-oh. 326 00:10:24,680 --> 00:10:25,560 OKEI. 327 00:10:25,560 --> 00:10:26,680 Sa klõpsad, et üks. 328 00:10:26,680 --> 00:10:28,690 Väga hea. 329 00:10:28,690 --> 00:10:29,780 >> Ja hea. 330 00:10:29,780 --> 00:10:30,970 Nüüd sa klõpsasid seda. 331 00:10:30,970 --> 00:10:34,060 Ja las ma annan teile mikrofoni, nii, et teil on see hetk. 332 00:10:34,060 --> 00:10:37,000 Lase käia ja klõpsake kõrvalmajas, et te kavatsete. 333 00:10:37,000 --> 00:10:39,812 Jah, hea. 334 00:10:39,812 --> 00:10:41,020 Trevor: Kas ma unclick uks? 335 00:10:41,020 --> 00:10:42,620 DAVID J. Humala: Ei, sa ei saa unclick. 336 00:10:42,620 --> 00:10:43,119 Trevor: OK. 337 00:10:43,119 --> 00:10:43,974 See. 338 00:10:43,974 --> 00:10:45,640 DAVID J. Humala: Kuhu sa tahad minna? 339 00:10:45,640 --> 00:10:46,410 Milline? 340 00:10:46,410 --> 00:10:47,230 >> Trevor: See üks. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. Humala: Ei 342 00:10:48,042 --> 00:10:48,450 >> Trevor: OK. 343 00:10:48,450 --> 00:10:48,735 See. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. Humala: Jah. 345 00:10:49,020 --> 00:10:49,700 See oli hea. 346 00:10:49,700 --> 00:10:50,380 Hästi. 347 00:10:50,380 --> 00:10:53,900 Mis oli teie algoritm või kord seda teed, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> Trevor: Ma lihtsalt läks läbi uksed, kuni leidsin 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. Humala: OK. 350 00:10:56,940 --> 00:10:58,150 Suurepärane algoritm. 351 00:10:58,150 --> 00:10:59,540 Nii et trahvi. 352 00:10:59,540 --> 00:11:03,120 Sest tegelikult, kui ma paljastada, mis on taga kaks ust, mida 353 00:11:03,120 --> 00:11:06,954 me leiame siin on see, et meil on ainult juhuslik sisend. 354 00:11:06,954 --> 00:11:08,870 Nii et tegelikult oli nii hea, kui sa võiksid saada. 355 00:11:08,870 --> 00:11:12,509 Ja tegelikult, et sul parem kui ammendavalt otsivad kogu massiiv, 356 00:11:12,509 --> 00:11:15,300 sest see oleks olnud tõesti õnnetu, kui sa tabanud number 357 00:11:15,300 --> 00:11:16,604 50 päris viimase ukse. 358 00:11:16,604 --> 00:11:18,520 Aga mis siis, kui me selle asemel saatis sulle oletus. 359 00:11:18,520 --> 00:11:20,630 Oletame, ma justkui kõik Nende uste ümber, 360 00:11:20,630 --> 00:11:23,500 nii, et teil on numbrid järjestatud seekord 361 00:11:23,500 --> 00:11:29,730 kuid seekord on see tegelikult erinevalt-- seekord 362 00:11:29,730 --> 00:11:32,640 see on tegelikult järjestatud teile. 363 00:11:32,640 --> 00:11:35,380 Ja nüüd eesmärgiks käepärast on tabanud number 50. 364 00:11:35,380 --> 00:11:36,090 >> Trevor: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. Humala: Mis on Sinu algoritmi saab olema? 366 00:11:37,670 --> 00:11:39,628 >> Trevor: Noh, kui see on sorteeritud, see kas lähed 367 00:11:39,628 --> 00:11:42,710 to olla-- kui suurim on suurim, alanevas, siis saad olla esimene, 368 00:11:42,710 --> 00:11:44,751 või kui see on vastupidine, see saab olema viimane. 369 00:11:44,751 --> 00:11:48,897 Nii et ma lihtsalt puuduta seda ust, ja siis puuduta lihtsalt valikut viimase ukse. 370 00:11:48,897 --> 00:11:49,980 DAVID J. Humala: Suurepärane. 371 00:11:49,980 --> 00:11:50,270 Hästi. 372 00:11:50,270 --> 00:11:51,150 Nii leidsime number 50. 373 00:11:51,150 --> 00:11:52,970 Nii kiiresti sa teadsid nad on sorteeritud, me 374 00:11:52,970 --> 00:11:55,040 suutsid võimendada see eeldus. 375 00:11:55,040 --> 00:11:57,040 Nii nad on liiga palju nagu telefoniraamatust näiteks. 376 00:11:57,040 --> 00:11:59,540 Niipea, kui teil on, isegi väike probleem selline, 377 00:11:59,540 --> 00:12:02,380 Sinu sisendite eelnevalt sorteeritud, saame tegelikult leida väärtus vaieldamatult 378 00:12:02,380 --> 00:12:03,130 efektiivsemalt. 379 00:12:03,130 --> 00:12:05,800 >> Ja ma ei saa öelda, kas see oli järjestatud väike suur või suur, et väike, 380 00:12:05,800 --> 00:12:08,080 ja nii see oli väga mõistlik alustada ühes otsas või teine 381 00:12:08,080 --> 00:12:09,750 tegelikult leiavad, et sihtväärtust. 382 00:12:09,750 --> 00:12:11,400 Nii tänada, et Trevor samuti. 383 00:12:11,400 --> 00:12:13,260 Ja ma propose-- ilusti tehtud. 384 00:12:13,260 --> 00:12:16,960 Meil on väike klipp, tegelikult, et on üks meie lemmik hetki CS50, 385 00:12:16,960 --> 00:12:19,700 kusjuures mõnikord need demod ei ole päris kavakohaselt minema. 386 00:12:19,700 --> 00:12:22,050 Ja tõepoolest just nüüd, ma tõmmata vale liidesega 387 00:12:22,050 --> 00:12:23,508 kellega kasutada puuteekraani. 388 00:12:23,508 --> 00:12:24,660 Nii et oli minu viga seal. 389 00:12:24,660 --> 00:12:26,600 >> Nii see teha Järgmise aasta klambrit 390 00:12:26,600 --> 00:12:28,570 miks ma klikkides oma ekraanil. 391 00:12:28,570 --> 00:12:31,390 Aga olgem võtta Kiire pilk mis juhtus eelmisel aastal 392 00:12:31,390 --> 00:12:34,770 Jay, kes tulid, palju nagu Trevor siin vabatahtlikult, 393 00:12:34,770 --> 00:12:39,380 ja selle lühikese klipi, näete kuidas see sama demo ei ole päris 394 00:12:39,380 --> 00:12:41,074 näitavad sama õppetunnid. 395 00:12:41,074 --> 00:12:41,740 [Video taasesitus] 396 00:12:41,740 --> 00:12:45,360 -Kõik Ma tahan, et sa nüüd on leida mind, ja meie jaoks, 397 00:12:45,360 --> 00:12:51,674 tõesti, number 50 üks samm korraga. 398 00:12:51,674 --> 00:12:52,450 >> -The Number 50? 399 00:12:52,450 --> 00:12:53,190 >> -The Number 50. 400 00:12:53,190 --> 00:12:55,356 Ja saate paljastada, mis on taga kõik need uksed 401 00:12:55,356 --> 00:12:58,540 lihtsalt puudutades sõrmega. 402 00:12:58,540 --> 00:13:00,910 Pagan võtaks. 403 00:13:00,910 --> 00:13:02,870 >> [Naerab] 404 00:13:02,870 --> 00:13:03,806 >> [Taasesituse lõpetamiseks] 405 00:13:03,806 --> 00:13:05,430 DAVID J. Humala: Nii et läks väga hästi. 406 00:13:05,430 --> 00:13:06,796 Need olid sorteerimata uksed. 407 00:13:06,796 --> 00:13:08,670 Ja Jay, muidugi, leidis, et see kõik liiga kiiresti. 408 00:13:08,670 --> 00:13:12,910 Trevor tegi palju paremat tööd nii õpetusliku hetk, 409 00:13:12,910 --> 00:13:15,850 niiöelda, sel aastal võttes enam leida. 410 00:13:15,850 --> 00:13:17,950 Muidugi, siis andsime Jay teist võimalust, 411 00:13:17,950 --> 00:13:20,320 kusjuures me järjestatud uksed, niisama tegime Trevor, 412 00:13:20,320 --> 00:13:22,300 ja Trevor tegi super hästi seekord. 413 00:13:22,300 --> 00:13:26,124 Aga Jay tegi seda poole nii kiiresti. 414 00:13:26,124 --> 00:13:26,790 [Video taasesitus] 415 00:13:26,790 --> 00:13:29,650 -The Eesmärk nüüd on ka meid leida number 50, 416 00:13:29,650 --> 00:13:33,030 kuid seda algoritmiliselt ja ütle meile, kuidas sa tahad seda. 417 00:13:33,030 --> 00:13:33,660 >> -OKEI. 418 00:13:33,660 --> 00:13:35,604 >> -Ja Kui leiate, et teil hoida filmi. 419 00:13:35,604 --> 00:13:37,228 Kui sa ei leia seda, siis anna seda tagasi. 420 00:13:37,228 --> 00:13:38,044 >> -Mees. 421 00:13:38,044 --> 00:13:38,860 >> Oh! 422 00:13:38,860 --> 00:13:40,800 >> - [Kuuldamatu] OK. 423 00:13:40,800 --> 00:13:46,236 Nii et ma lähen kontrollida otsad kõigepealt kindlaks teha, kas 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 >> [Taasesituse lõpetamiseks] 427 00:13:55,729 --> 00:13:56,520 DAVID J. Humala: OK. 428 00:13:56,520 --> 00:13:59,760 Nii sorteerimine uksed selgelt toob kaasa suurema tõhususe. 429 00:13:59,760 --> 00:14:01,680 Ja nii kaks korda kiiremini on see, mida ma mõtlesin seal. 430 00:14:01,680 --> 00:14:03,270 Ja nii Jay vedas mõlemal korral. 431 00:14:03,270 --> 00:14:06,685 Ja ta sai ka õnnelik, et viimase aastal, ma tellisin mõned Blu-ray kettad 432 00:14:06,685 --> 00:14:07,560 tegelikult välja anda. 433 00:14:07,560 --> 00:14:09,768 Vabandust sel aastal oleme ei ole sama, Trevor. 434 00:14:09,768 --> 00:14:11,540 Aga veel parem oli paar aastat tagasi. 435 00:14:11,540 --> 00:14:14,820 Ja mõned teist ehk teavad seda mehe, Sean, kes siis, kui ta oli CS50, 436 00:14:14,820 --> 00:14:17,780 vaidlustati täpne Sama probleem, kuigi SD, 437 00:14:17,780 --> 00:14:19,360 kui saate kohe näha, juba järgmisel päeval. 438 00:14:19,360 --> 00:14:22,622 Ja sa leiad, et mitte ainult ei Ta võtab pisut rohkem kui Jay, 439 00:14:22,622 --> 00:14:25,580 veidi enam kui Trevor, see oli tegelikult see suurepärane võimalus 440 00:14:25,580 --> 00:14:29,820 tegeleda peaaegu kõigile Rahvas a la Hind on õigus, julgustades 441 00:14:29,820 --> 00:14:31,889 teda leida number olime otsib. 442 00:14:31,889 --> 00:14:32,930 Olgem. võtta Kiire pilk. 443 00:14:32,930 --> 00:14:33,320 >> [Video taasesitus] 444 00:14:33,320 --> 00:14:33,820 >> -OKEI. 445 00:14:33,820 --> 00:14:36,680 Nii et teie ülesanne siin, Sean, on järgmine. 446 00:14:36,680 --> 00:14:40,860 Olen taga peidus need uksed arv seitse. 447 00:14:40,860 --> 00:14:45,120 Aga peitunud mõned neist uksed samuti on ka teisi negatiivseid numbreid. 448 00:14:45,120 --> 00:14:47,500 Ja teie eesmärk on mõelda Selle esirea numbrid 449 00:14:47,500 --> 00:14:50,390 lihtsalt massiivi, või lihtsalt jada paberitükke 450 00:14:50,390 --> 00:14:51,510 numbrite taga. 451 00:14:51,510 --> 00:14:55,540 Ja teie eesmärk on ainult kasutades tippu massiivi siin, leida mulle number seitse. 452 00:14:55,540 --> 00:14:58,570 Ja me siis läheb kritiseerida kuidas sa minema umbes teeb seda. 453 00:14:58,570 --> 00:14:59,070 -Hästi. 454 00:14:59,070 --> 00:15:00,850 -Leia meile number seitse, palun. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Ei. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Viis, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Naerab] 461 00:15:24,770 --> 00:15:25,910 >> See ei ole konksuga küsimus. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Üks. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Naerab] 466 00:15:34,695 --> 00:15:37,861 Sel hetkel, oma skoori ei ole väga hea, et sa võiksid samuti edasi. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Kolm. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Naerab] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Mine edasi. 473 00:15:47,774 --> 00:15:50,690 Ausalt, ma ei saa aidata, kuid ei tea, mida sa isegi mõelda, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Naerab] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Ainult ülemises reas, nii sul kolm vasakule. 477 00:15:55,020 --> 00:15:56,200 Nii leia mind seitse. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Naerab] 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 Seitse. 484 00:16:26,946 --> 00:16:28,780 >> [APPLAUSE] 485 00:16:28,780 --> 00:16:29,426 >> Hästi. 486 00:16:29,426 --> 00:16:30,360 >> [Taasesituse lõpetamiseks] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. Humala: et me saaksime vaadata neid kogu päeva pikkune. 488 00:16:31,840 --> 00:16:34,090 Ja muidugi, mõned Tänavuse demos ehk 489 00:16:34,090 --> 00:16:36,330 Nüüd lõpuks järgmise aasta video ka. 490 00:16:36,330 --> 00:16:39,040 Vaatame nüüd tegelikult keskenduda algoritme 491 00:16:39,040 --> 00:16:42,140 siin, ja vaata, kui me ei saa Nüüd hakkavad vormistama 492 00:16:42,140 --> 00:16:46,650 kuidas me saame minna saan oma andmed sellesse riik, mis see on järjestatud, 493 00:16:46,650 --> 00:16:50,054 nii et lõpuks saame tegelikult search efektiivsemalt. 494 00:16:50,054 --> 00:16:52,470 Ja kuigi me ei kavatse kasutada üsna väike andmekogumid 495 00:16:52,470 --> 00:16:54,511 nagu kaheksa numbrit me on siin laual, 496 00:16:54,511 --> 00:16:58,230 lõpuks need samad ideed, mida kohaldatakse 1000 sisendid, miljon sisendid, 497 00:16:58,230 --> 00:17:02,100 4 miljardit sisendid, sest algoritmid saab olema põhiolemuselt sama. 498 00:17:02,100 --> 00:17:05,359 >> Ja nii see on meie viimane võimaluse vabatahtlikele täna 499 00:17:05,359 --> 00:17:09,790 aga võib-olla kõige kaasatud üks, mille eest me peame kaheksa vabatahtlikud 500 00:17:09,790 --> 00:17:12,960 tulla ja kõndida meid läbi Protsessi sorteerimine mida varsti 501 00:17:12,960 --> 00:17:15,212 olla nende muusika seisab siin. 502 00:17:15,212 --> 00:17:16,170 Lubage mul alustada siia tagasi. 503 00:17:16,170 --> 00:17:19,692 >> Nii et üks on turquoise-- roheline on? 504 00:17:19,692 --> 00:17:21,130 Kas olete toime? 505 00:17:21,130 --> 00:17:21,630 Kaks. 506 00:17:21,630 --> 00:17:23,069 Tule alla. 507 00:17:23,069 --> 00:17:23,569 OKEI. 508 00:17:23,569 --> 00:17:24,420 Kolm. 509 00:17:24,420 --> 00:17:25,400 Neli. 510 00:17:25,400 --> 00:17:27,247 Lubage mind-- OK, viis. 511 00:17:27,247 --> 00:17:28,830 Sa oled nimetab oma sõbraks. 512 00:17:28,830 --> 00:17:31,340 Kuus, seitse, kaheksa. 513 00:17:31,340 --> 00:17:32,130 Tule üles. 514 00:17:32,130 --> 00:17:32,630 Hästi. 515 00:17:32,630 --> 00:17:33,190 Suur tänu. 516 00:17:33,190 --> 00:17:33,689 Tule üles. 517 00:17:33,689 --> 00:17:34,790 Tule üles. 518 00:17:34,790 --> 00:17:35,330 >> Hästi. 519 00:17:35,330 --> 00:17:38,890 Mis meil siin-- ja selle on üks ebamugav need, 520 00:17:38,890 --> 00:17:42,390 kuna see nõuab, et sa huumor mind natuke aega. 521 00:17:42,390 --> 00:17:43,442 Sa peab olema number üks. 522 00:17:43,442 --> 00:17:44,150 Mis su nimi on? 523 00:17:44,150 --> 00:17:44,610 >> ANNAN: Annan. 524 00:17:44,610 --> 00:17:45,526 >> DAVID J. Humala: Annan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 Mis su nimi on? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. Humala: Joseph, sa oled number kaks. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, number kolm. 530 00:17:52,260 --> 00:17:53,722 Stefan, number neli. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. Humala: Cynthia, number viis. 533 00:17:57,548 --> 00:17:58,452 [Kuuldamatu] 534 00:17:58,452 --> 00:17:59,618 DAVID J. Humala: [kuuldamatu]. 535 00:17:59,618 --> 00:18:00,391 David, number kuus. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. Humala: Matt number seitse. 538 00:18:02,160 --> 00:18:02,850 Ja? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. Humala: Waverly, number kaheksa. 541 00:18:04,470 --> 00:18:04,970 Hästi. 542 00:18:04,970 --> 00:18:06,510 Kui te could-- whoops. 543 00:18:06,510 --> 00:18:08,820 Kui te kõik, sest teie Esimene väljakutse, seal 544 00:18:08,820 --> 00:18:10,820 Kaheksa muusika seisu siin ees publik. 545 00:18:10,820 --> 00:18:14,200 Kui sa võiksid panna oma numbrid Nende muusika seisu nii 546 00:18:14,200 --> 00:18:16,560 et nad rivistama koos samad numbrid laual. 547 00:18:16,560 --> 00:18:19,560 Nii et ise nägema, et pannes oma numbrid nende muusika 548 00:18:19,560 --> 00:18:21,960 seisab siin. 549 00:18:21,960 --> 00:18:25,980 Suurepärane siiani. 550 00:18:25,980 --> 00:18:26,600 >> Suurepärane. 551 00:18:26,600 --> 00:18:26,890 OKEI. 552 00:18:26,890 --> 00:18:29,556 Nüüd, me ei kavatse küsida Küsimus on mitu erinevat võimalust. 553 00:18:29,556 --> 00:18:31,610 Kuidas me saame minna sorteerimine need inimesed siin? 554 00:18:31,610 --> 00:18:34,500 Kuna meil oli paar lähenemisviise varem, kusjuures me olime 555 00:18:34,500 --> 00:18:36,360 Selline tegemist kahe erineva ämbrid. 556 00:18:36,360 --> 00:18:38,842 Ja siis me üldiselt lõikuva asju koos. 557 00:18:38,842 --> 00:18:41,050 Niipea kui nägime kaks numbrit mis kuulus kokku 558 00:18:41,050 --> 00:18:41,975 paneme need kokku. 559 00:18:41,975 --> 00:18:43,350 Kaks tähte, mis kuuluvad kokku. 560 00:18:43,350 --> 00:18:45,058 >> Aga vaatame, kui me ei saa ametlikult selle, 561 00:18:45,058 --> 00:18:48,044 nii et me lõpuks on mõned pseudo-koodi sisestamist, 562 00:18:48,044 --> 00:18:49,710 millega saab neid probleeme lahendada. 563 00:18:49,710 --> 00:18:51,870 Nüüd, ma otsin välja neid numbreid siin. 564 00:18:51,870 --> 00:18:55,030 Ja ma näen terve hulk vigu. 565 00:18:55,030 --> 00:18:57,750 Lõpuks, ma tahan ühte kohta vasakule ja kaheksa paremal. 566 00:18:57,750 --> 00:19:00,650 >> Ja nii ma vaatan Nende kahe, nelja ja kaks. 567 00:19:00,650 --> 00:19:02,930 Ja milles probleem, ilmselt? 568 00:19:02,930 --> 00:19:04,261 Jah. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Kaks ilmselt tuleb enne neli, nii et sa tead, mida? 571 00:19:07,160 --> 00:19:10,210 Lubage mul kõigepealt ahne lähenemist, kui sa meelega probleem 572 00:19:10,210 --> 00:19:13,790 määrata one-- kui te mäletate alates Standard Edition Ülesanded Üks, 573 00:19:13,790 --> 00:19:16,820 kus ma lihtsalt kohapeal lahendada probleemi mis on siin minu ees 574 00:19:16,820 --> 00:19:17,690 ja vaata kuhu see viib mind. 575 00:19:17,690 --> 00:19:17,870 >> OKEI. 576 00:19:17,870 --> 00:19:20,161 Nii kaks ja neli, lase mul minna käia ja lihtsalt vahetada teie kaks. 577 00:19:20,161 --> 00:19:22,400 Kui te ei füüsiliselt liigutada ise ja oma paberi, 578 00:19:22,400 --> 00:19:25,040 Mulle tundub, et oleme saanud nimekirja paremas olukorras. 579 00:19:25,040 --> 00:19:26,330 >> Nüüd nad on head. 580 00:19:26,330 --> 00:19:28,480 Ma lähen edasi liikuda, neli ja kuus, näeb hea välja. 581 00:19:28,480 --> 00:19:29,110 Pole probleemi. 582 00:19:29,110 --> 00:19:30,440 Kuus ja kaheksa OK. 583 00:19:30,440 --> 00:19:31,860 Kaheksa ja üks, teine ​​probleem. 584 00:19:31,860 --> 00:19:34,750 Sest see, mis on tõsi umbes kaheksa ja üks? 585 00:19:34,750 --> 00:19:36,990 Üks on enne kaheksa, ja mis siis peaksime tegema? 586 00:19:36,990 --> 00:19:38,090 Olgem vahetada need kaks. 587 00:19:38,090 --> 00:19:39,316 Üks ja kaheksa. 588 00:19:39,316 --> 00:19:40,690 Ja nüüd, ma lähen edasi. 589 00:19:40,690 --> 00:19:42,030 Ma lähen hoida eel. 590 00:19:42,030 --> 00:19:42,840 Ja vaatame, mis juhtub. 591 00:19:42,840 --> 00:19:44,680 Kaheksa ja kolm, on Muidugi, rikkis. 592 00:19:44,680 --> 00:19:45,815 Olgem swap. 593 00:19:45,815 --> 00:19:46,940 Kaheksa ja seitse muidugi. 594 00:19:46,940 --> 00:19:47,481 Korrast ära. 595 00:19:47,481 --> 00:19:48,280 Olgem swap. 596 00:19:48,280 --> 00:19:49,940 Kaheksa ja viis, muidugi, olgem swap. 597 00:19:49,940 --> 00:19:50,560 Hästi. 598 00:19:50,560 --> 00:19:51,880 Nimekiri on sorteeritud. 599 00:19:51,880 --> 00:19:53,060 jah? 600 00:19:53,060 --> 00:19:54,280 >> OK, ilmselt mitte. 601 00:19:54,280 --> 00:19:55,860 Aga see on natuke parem, eks? 602 00:19:55,860 --> 00:19:57,270 Sest teate, mis juhtus. 603 00:19:57,270 --> 00:20:01,749 Iga kord, kui me läbi swap, väiksem number selline kurnatud, et viis, 604 00:20:01,749 --> 00:20:03,790 ja suurem number percolated sel viisil, või me tulen 605 00:20:03,790 --> 00:20:06,880 alustada öeldes mullidena kuni vasakule või mullidena paremale. 606 00:20:06,880 --> 00:20:10,080 >> Nüüd, see ei ole piisav, sest parimal number võiks 607 00:20:10,080 --> 00:20:11,990 liikunud ühest kohast edasi, või halvimal juhul 608 00:20:11,990 --> 00:20:13,880 number võib olla kolis ühe koha peal edasi. 609 00:20:13,880 --> 00:20:16,369 Nii et sa tead, mida seda laadi ning töötas päris hästi siiani. 610 00:20:16,369 --> 00:20:17,410 Lubage mul lihtsalt proovida seda uuesti. 611 00:20:17,410 --> 00:20:18,880 Kaks ja neli, on nad OK. 612 00:20:18,880 --> 00:20:20,180 Neli ja pool on nad OK. 613 00:20:20,180 --> 00:20:21,790 Kuus ja üks, rikkis. 614 00:20:21,790 --> 00:20:23,007 Nii saab vahetada teie kaks. 615 00:20:23,007 --> 00:20:25,840 Ja nüüd, märka probleemi on hakanud natuke parem uuesti. 616 00:20:25,840 --> 00:20:27,006 Kuus ja kolm, rikkis. 617 00:20:27,006 --> 00:20:28,100 Olgem vahetada teie kaks. 618 00:20:28,100 --> 00:20:29,730 Kuus ja seitse, sa oled hea. 619 00:20:29,730 --> 00:20:32,230 Seitse ja viis muidugi rikkis. 620 00:20:32,230 --> 00:20:33,920 Seitse ja kaheksa korda. 621 00:20:33,920 --> 00:20:36,470 Ja nüüd, ma võib olla vaja Selleks paar korda. 622 00:20:36,470 --> 00:20:39,830 Ja tegelikult arvan endile ehk mitu korda maksimaalselt 623 00:20:39,830 --> 00:20:41,330 võiks mul käia edasi-tagasi? 624 00:20:41,330 --> 00:20:42,390 >> Me tuleme tagasi selle. 625 00:20:42,390 --> 00:20:43,700 Nii kaks ja neli on ikka OK. 626 00:20:43,700 --> 00:20:44,940 Neli ja üks, nope. 627 00:20:44,940 --> 00:20:45,747 Niisiis, oletame, swap. 628 00:20:45,747 --> 00:20:47,830 Ja jälle märgata visuaalselt üks on selline kihisevat 629 00:20:47,830 --> 00:20:49,163 vasakule, kus see peaks olema. 630 00:20:49,163 --> 00:20:50,010 Neli ja kolm swap. 631 00:20:50,010 --> 00:20:51,330 Neli kuni kuus. 632 00:20:51,330 --> 00:20:53,100 Kuus ja viis swap. 633 00:20:53,100 --> 00:20:53,959 Kuus ja seitse. 634 00:20:53,959 --> 00:20:55,000 Seitse ja kaheksa on hea. 635 00:20:55,000 --> 00:20:55,500 >> Väga hea. 636 00:20:55,500 --> 00:20:58,460 Saame isegi parem. 637 00:20:58,460 --> 00:20:59,130 Vaatame. 638 00:20:59,130 --> 00:21:00,940 Nüüd on meil kaks ja üks. 639 00:21:00,940 --> 00:21:02,520 Muidugi vahetada. 640 00:21:02,520 --> 00:21:07,520 Teist ja kolmandat kolme ja nelja, nelja ja viis, kuus ja seitse, seitse ja kaheksa. 641 00:21:07,520 --> 00:21:08,020 Väga hea. 642 00:21:08,020 --> 00:21:08,730 Ja tead mis? 643 00:21:08,730 --> 00:21:11,190 Sest ma tegin ühe muutus seal, lubage mul teha üks meelerahu kontrolli. 644 00:21:11,190 --> 00:21:13,023 Lubage mul minna kogu tee tagasi algusesse. 645 00:21:13,023 --> 00:21:13,680 OKEI. 646 00:21:13,680 --> 00:21:14,750 Üks, two-- yup, näed? 647 00:21:14,750 --> 00:21:15,870 Midagi oli valesti. 648 00:21:15,870 --> 00:21:18,420 Kolm, neli, viis, kuus, seitse, kaheksa. 649 00:21:18,420 --> 00:21:21,920 Ja see viimane pass, on sa rahul minu nüüd 650 00:21:21,920 --> 00:21:23,830 väites, et see on järjestatud? 651 00:21:23,830 --> 00:21:24,330 OKEI. 652 00:21:24,330 --> 00:21:25,880 Visuaalselt, see on tõsi. 653 00:21:25,880 --> 00:21:28,410 Aga funktsionaalselt, mida ei ka lihtsalt juhtub 654 00:21:28,410 --> 00:21:31,870 et viimase pass, mis võimaldab teil kinnitada, et see nimekiri on tõepoolest 655 00:21:31,870 --> 00:21:32,660 järjestatud? 656 00:21:32,660 --> 00:21:34,477 >> Mida ma tegin või ei tee seda viimase pass? 657 00:21:34,477 --> 00:21:35,810 Sihtrühm: muutusi ei toimunud. 658 00:21:35,810 --> 00:21:36,120 DAVID J. Humala: Vabandust? 659 00:21:36,120 --> 00:21:37,070 Sihtrühm: No muudatusi. 660 00:21:37,070 --> 00:21:38,653 DAVID J. Humala: muutusi ei toimunud. 661 00:21:38,653 --> 00:21:41,947 Seega oleks rumal minust teha sama algoritmi uuesti 662 00:21:41,947 --> 00:21:43,780 kui ma ei tee muudab esmakordselt. 663 00:21:43,780 --> 00:21:45,160 Ja riik ei ole muutunud. 664 00:21:45,160 --> 00:21:47,576 Kindlasti ma ei kavatse teha Kõik muudatused teist korda. 665 00:21:47,576 --> 00:21:49,820 Ja nii, et see on ohutu nüüd öelda, nimekirja sorteeritakse. 666 00:21:49,820 --> 00:21:52,069 >> Ja tõepoolest, see on nüüd midagi, mida me tulen üldiselt 667 00:21:52,069 --> 00:21:56,900 kõne mull sorteerida, millega paarikaupa, sa parandada vigu korrata, 668 00:21:56,900 --> 00:22:00,210 ja uuesti ja uuesti, ja sa hoida läheb edasi ja tagasi, 669 00:22:00,210 --> 00:22:03,370 ja edasi-tagasi, kuni olete ei tee selliseid vahetustehingud, misjärel 670 00:22:03,370 --> 00:22:07,089 võite olla kindlad, jah, ma lõpetanud, millega kõik vigu. 671 00:22:07,089 --> 00:22:08,630 Olgem nullida ja proovida teistsugust lähenemist. 672 00:22:08,630 --> 00:22:11,590 Kui te poisid võiks minna tagasi järjekorras sa olid hetk tagasi, 673 00:22:11,590 --> 00:22:13,780 mis nägi välja selline. 674 00:22:13,780 --> 00:22:17,640 Nüüd saab võtta lähenemise alusel veidi nagu eksam raamat, 675 00:22:17,640 --> 00:22:21,122 kusjuures me olime pidevalt Valides täht 676 00:22:21,122 --> 00:22:22,830 et me mingi tahtsime tegelema järgmisel. 677 00:22:22,830 --> 00:22:26,420 Võib-olla oli see suur kiri, nagu A, või väike täht Z. 678 00:22:26,420 --> 00:22:28,170 >> Nii et igaüks on tagasi selles järjekorras. 679 00:22:28,170 --> 00:22:29,800 Ja nüüd lubage mul seda teha. 680 00:22:29,800 --> 00:22:34,880 Vaatame, ma tean, et ma ei Kaheksa numbrid siin. 681 00:22:34,880 --> 00:22:37,410 Ma lähen edasi minna ja lihtsalt teadlikult valida 682 00:22:37,410 --> 00:22:38,520 väikseim elemente. 683 00:22:38,520 --> 00:22:38,760 Õigus? 684 00:22:38,760 --> 00:22:39,801 See tundub intuitiivselt liiga. 685 00:22:39,801 --> 00:22:42,560 Miks ma ei leia väikseim element, pane see, kui ta kuulub, 686 00:22:42,560 --> 00:22:45,280 siis saan järgmisel väikseim element, panna see, kuhu see kuulub, ja lihtsalt korrata. 687 00:22:45,280 --> 00:22:46,820 >> Kuna intuitiivselt, mis peaks toimima ka. 688 00:22:46,820 --> 00:22:48,441 Nii neli, mis on üsna väike number. 689 00:22:48,441 --> 00:22:49,940 Ma mäletan, kui see on. 690 00:22:49,940 --> 00:22:50,523 Oota hetk. 691 00:22:50,523 --> 00:22:51,577 Kaks on väiksemad. 692 00:22:51,577 --> 00:22:53,910 Lubage mul nüüd meeles pidada, kus kaks on, ja unustada neli. 693 00:22:53,910 --> 00:22:55,050 Me tegeleme sellega hiljem. 694 00:22:55,050 --> 00:22:56,460 Kuus, ma ei ole huvitatud. 695 00:22:56,460 --> 00:22:57,810 Kaheksa, ma ei ole huvitatud. 696 00:22:57,810 --> 00:22:59,780 Üks on minu uus väike number. 697 00:22:59,780 --> 00:23:01,470 Nii et ma lähen mäleta, kus üks on. 698 00:23:01,470 --> 00:23:02,534 Kolm, ei huvita. 699 00:23:02,534 --> 00:23:03,450 Seitse, ei huvita. 700 00:23:03,450 --> 00:23:04,530 Viis, ei huvita. 701 00:23:04,530 --> 00:23:07,390 >> Nii ilma allakukkumist laval sel aastal 702 00:23:07,390 --> 00:23:09,890 Ma lähen haarata number one-- ja mis oli su nimi oligi? 703 00:23:09,890 --> 00:23:10,150 >> ANNAN: Annan. 704 00:23:10,150 --> 00:23:11,220 >> DAVID J. Humala: Annan. 705 00:23:11,220 --> 00:23:13,540 Ja kui sa võiksid ühineda minuga Alguses nimekirja, 706 00:23:13,540 --> 00:23:14,870 paneme sind, kuhu sa kuulud. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- mis su nimi on? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. Humala: Stefan on viis. 710 00:23:18,191 --> 00:23:23,490 Nii et enne Stefan lahendab selle Probleem, mida me peaksime tegema? 711 00:23:23,490 --> 00:23:25,412 Mida me teeme Stefan? 712 00:23:25,412 --> 00:23:27,269 >> Sihtrühm: [kuuldamatu]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. Humala: OK. 714 00:23:28,060 --> 00:23:28,850 Nii et me võiks seda teha. 715 00:23:28,850 --> 00:23:31,730 Võiksime omamoodi võtta Stefan ja tema neli, ja lihtsalt panna see muutujale 716 00:23:31,730 --> 00:23:33,530 ja hoidke seda Mõnes aega, 717 00:23:33,530 --> 00:23:35,220 muutes ruumi number üks. 718 00:23:35,220 --> 00:23:36,280 Ja see pole halb. 719 00:23:36,280 --> 00:23:39,270 Ma võiks oletada, miks mitte me lihtsalt panna Stefan siin? 720 00:23:39,270 --> 00:23:41,610 Miks võib see rikkuda üks ideid alustasime 721 00:23:41,610 --> 00:23:44,830 räägime viimasel ajal eelmisel nädalal? 722 00:23:44,830 --> 00:23:45,330 Jah? 723 00:23:45,330 --> 00:23:45,740 >> Sihtrühm: [kuuldamatu]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. Humala: Ei ole indeks ta. 725 00:23:46,860 --> 00:23:49,735 Kui te arvate sellest, tõepoolest, kui massiiv, see on nagu negatiivne, 726 00:23:49,735 --> 00:23:52,900 seega ei ole mälu tegelikult siin, kui see on tõepoolest massiivi, 727 00:23:52,900 --> 00:23:55,090 nagu me kuulutas eelmisel nädalal loengu. 728 00:23:55,090 --> 00:23:56,250 Nii et me ei peaks seda tegema. 729 00:23:56,250 --> 00:23:57,340 Me võime salvestada see muutujale. 730 00:23:57,340 --> 00:23:57,820 >> Või sa tead, mida? 731 00:23:57,820 --> 00:23:59,153 Kuulsin kellegi soovitan seda. 732 00:23:59,153 --> 00:24:01,020 Mida võiks veel teha Stefan? 733 00:24:01,020 --> 00:24:03,770 Miks me lihtsalt ei tõstma teda ja pani ta selle üle, kus number üks oli. 734 00:24:03,770 --> 00:24:05,170 Nii et kui sa tahad minna sinna. 735 00:24:05,170 --> 00:24:07,300 Ja tõepoolest, see on päris hea lahendus. 736 00:24:07,300 --> 00:24:10,480 Nüüd ühelt poolt, ma olen lahke on teinud probleemi hullemaks. 737 00:24:10,480 --> 00:24:13,650 Neli on nüüd kaugemal kust see peaks olema. 738 00:24:13,650 --> 00:24:14,900 Peaks olema poole käesoleva poole. 739 00:24:14,900 --> 00:24:16,100 >> Aga tead mis? 740 00:24:16,100 --> 00:24:17,630 See oleks võinud olla halb õnn. 741 00:24:17,630 --> 00:24:18,822 Võib-olla number kaheksa oli siin. 742 00:24:18,822 --> 00:24:20,530 Ja nii, võibolla oleksime saanud õnnelik, 743 00:24:20,530 --> 00:24:22,460 ning lükatakse kaheksa lõpule lähemale. 744 00:24:22,460 --> 00:24:24,710 Nii et lõpuks päev, see omamoodi kõik tasakaalustub. 745 00:24:24,710 --> 00:24:26,085 Me ei pea hooli neli. 746 00:24:26,085 --> 00:24:29,400 Kõik hoolin just nüüd on valides väikseim element. 747 00:24:29,400 --> 00:24:32,030 >> Ja nüüd, mida ma lähen teha, on unustada number üks 748 00:24:32,030 --> 00:24:35,160 püsivalt, sest ma tean nimekirja minu taga on nüüd järjestatud. 749 00:24:35,160 --> 00:24:36,720 Nii et minu nimekirjas oli varem suurus kaheksa. 750 00:24:36,720 --> 00:24:37,720 Nüüd on nende suurusest seitse. 751 00:24:37,720 --> 00:24:40,340 Nii et minu probleem muutub väiksem, ehkki lineaarselt. 752 00:24:40,340 --> 00:24:43,022 Nüüd ma lähen valima Praeguse väikseim element, kaks. 753 00:24:43,022 --> 00:24:46,520 Kuus, kaheksa, nelja, kolme, seitsme, viie. 754 00:24:46,520 --> 00:24:47,770 See oli väikseim element. 755 00:24:47,770 --> 00:24:49,416 Mida ma nüüd tegema with-- Mis oli su nimi oligi? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. Humala: Joseph? 758 00:24:50,085 --> 00:24:52,000 Me läheme lahkuda Joseph paigas. 759 00:24:52,000 --> 00:24:54,842 Nüüd ma lähen teeselda et need kutid are-- hästi, 760 00:24:54,842 --> 00:24:56,550 Ma tean, et need kaks on juba järjestatud. 761 00:24:56,550 --> 00:24:58,424 Olgem nüüd keskenduda Ülejäänud nimekirjas. 762 00:24:58,424 --> 00:25:00,080 Kuus on praegune väikseim. 763 00:25:00,080 --> 00:25:01,190 Kaheksa on suurem. 764 00:25:01,190 --> 00:25:02,970 Neli on nüüd praeguse väikseim. 765 00:25:02,970 --> 00:25:04,762 Kolm on nüüd praeguse väikseim. 766 00:25:04,762 --> 00:25:07,720 Ja nii nüüd ma lähen valima kolm, kes on-- mis su nimi oligi? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. Humala: Serena, kui sa saaksid Haara number ja swap with-- 769 00:25:10,620 --> 00:25:11,550 KALSANG: Kalsang. 770 00:25:11,550 --> 00:25:12,940 DAVID J. Humala: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Tule tagasi, ja me oleme läheb vahetada need kaks. 772 00:25:15,220 --> 00:25:17,360 Ja nüüd, paneme selle autopiloot. 773 00:25:17,360 --> 00:25:21,589 Ma lähen ja jätan teiega et valida järgmine väikseim elemente. 774 00:25:21,589 --> 00:25:22,380 Dun Dun Dun Dun. 775 00:25:22,380 --> 00:25:24,560 Number neli, mida teha? 776 00:25:24,560 --> 00:25:26,261 Suurepärane. 777 00:25:26,261 --> 00:25:27,760 Nüüd ma lähen tegema teise pass. 778 00:25:27,760 --> 00:25:28,590 Dun Dun Dun Dun. 779 00:25:28,590 --> 00:25:31,465 Näen viis on järgmine kahanevas järjekorras. 780 00:25:31,465 --> 00:25:32,840 Nüüd ma lähen võtma teise pass. 781 00:25:32,840 --> 00:25:33,631 Dun Dun Dun Dun. 782 00:25:33,631 --> 00:25:34,880 Kuus on väikseim. 783 00:25:34,880 --> 00:25:35,520 Väga hea. 784 00:25:35,520 --> 00:25:36,585 Seitse on väikseim. 785 00:25:36,585 --> 00:25:37,085 Ei muutu. 786 00:25:37,085 --> 00:25:38,630 Kaheksa on väikseim. 787 00:25:38,630 --> 00:25:39,170 Valmis. 788 00:25:39,170 --> 00:25:43,900 >> Nii et me oleme lihtsalt teha korduvalt valides ühe elemendi teise järel 789 00:25:43,900 --> 00:25:47,230 on ellu midagi, mis me oleme läheb vormistama kui valikut omamoodi. 790 00:25:47,230 --> 00:25:49,120 Ja see on võib-olla isegi lihtsam selgitada, 791 00:25:49,120 --> 00:25:51,310 et sõna otseses mõttes kõik, mida tahan teha, on lihtsalt hoida 792 00:25:51,310 --> 00:25:54,700 läheb edasi ja tagasi läbi nimekirja valides, suuruselt järgmine kahanevas element, 793 00:25:54,700 --> 00:25:55,720 kuni sa oled teinud. 794 00:25:55,720 --> 00:25:58,650 >> Nii et see on isegi lihtsam, võib-olla intuitiivselt, kui eelmisel. 795 00:25:58,650 --> 00:26:00,020 Proovime üks viimane. 796 00:26:00,020 --> 00:26:03,060 Kui te poisid võiksid nullida ise arvesse järgmisi positsioone 797 00:26:03,060 --> 00:26:08,600 lõplikult maha, vaatame, kui me ei saa nüüd vormistama üks teine ​​lähenemine. 798 00:26:08,600 --> 00:26:12,857 Tegelikult peaks keegi seal suggest 799 00:26:12,857 --> 00:26:14,440 kuidas muidu me võiksime minna seda teed? 800 00:26:14,440 --> 00:26:17,439 Ilma visklemine välja buzzwords või järjesta vastuseid, mis on juba teada, 801 00:26:17,439 --> 00:26:19,689 lihtsalt intuitiivselt, mida saaksime teha? 802 00:26:19,689 --> 00:26:21,635 >> Sihtrühm: [kuuldamatu]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. Humala: Jah. 804 00:26:22,510 --> 00:26:24,620 Nii et mõned suured intuitsiooni seal. 805 00:26:24,620 --> 00:26:28,020 Head asjad tunduvad juhtuda seni infotehnoloogia, kui me jagame 806 00:26:28,020 --> 00:26:30,832 ja vallutada probleemi jagades see pooleks ja pool ja pool. 807 00:26:30,832 --> 00:26:32,540 Ja nii tõesti, me võiks alustada seda teha. 808 00:26:32,540 --> 00:26:35,754 Ja tegelikult, et see saab olema, siis me vaata, üks meie parimaid lahendusi veel. 809 00:26:35,754 --> 00:26:37,420 Aga tulgem tagasi, et enne pikk. 810 00:26:37,420 --> 00:26:40,500 Tegelikult me ​​teeme et veidi hiljem sel nädalal. 811 00:26:40,500 --> 00:26:42,180 Mida võiks me lahendada seda? 812 00:26:42,180 --> 00:26:44,647 Nii et igaüks siin on näiliselt juhuslikus järjekorras. 813 00:26:44,647 --> 00:26:45,230 Tead mida? 814 00:26:45,230 --> 00:26:48,320 Selle asemel, et minna edasi ja tagasi, edasi ja tagasi, edasi ja tagasi 815 00:26:48,320 --> 00:26:50,624 Iga kord, see tunne Ma teen palju jalgsi. 816 00:26:50,624 --> 00:26:52,790 Miks ma just ei alusta Alguses nimekirja, 817 00:26:52,790 --> 00:26:54,960 ja lihtsalt panna neli kuhu ta kuulub? 818 00:26:54,960 --> 00:26:59,680 Nii et lubage mul oletame hetkeks, et minu nimekiri on ainult see esimene element. 819 00:26:59,680 --> 00:27:04,937 Kas neli järjestatud sel ajahetkel, kui ma hoolin on siin kõik? 820 00:27:04,937 --> 00:27:06,520 See on omamoodi triviaalne, eks? 821 00:27:06,520 --> 00:27:10,000 Nagu nimekirjast, mis sisaldab ühe numbri ja et number neli on ilmselt järjestatud. 822 00:27:10,000 --> 00:27:13,070 >> Lubage mul ette näha selle nimekirja sorteerida. 823 00:27:13,070 --> 00:27:15,090 Aga nüüd on mul ülejäänud seda nimekirja. 824 00:27:15,090 --> 00:27:17,240 Nüüd, ma kogevad kaks. 825 00:27:17,240 --> 00:27:21,690 Kust kaks ilmselt kuuluvad seoses nelja? 826 00:27:21,690 --> 00:27:22,580 Enne neli. 827 00:27:22,580 --> 00:27:23,862 Mida ma saan teha siin? 828 00:27:23,862 --> 00:27:24,820 Mis su nimi oligi? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. Humala: Joseph, kui sa saaksid sammu tagasi 831 00:27:26,030 --> 00:27:27,790 hetkeks oma number. 832 00:27:27,790 --> 00:27:31,130 Ja nüüd, milline peaks Stefan teha siin? 833 00:27:31,130 --> 00:27:33,720 Lähme minema Stefan siin. 834 00:27:33,720 --> 00:27:35,520 Ja nüüd, lase Joseph siia tulla. 835 00:27:35,520 --> 00:27:39,660 Ja nüüd, las ma väita, et kõik siin on järjestatud. 836 00:27:39,660 --> 00:27:42,474 Niisiis, sarnase tulemuse, kuid fundamentaalselt erinevat lähenemist. 837 00:27:42,474 --> 00:27:44,140 Ma pole isegi vaadanud, mis on seal. 838 00:27:44,140 --> 00:27:46,310 Ma muudkui võttes elemendid kui nad kätte mulle, 839 00:27:46,310 --> 00:27:47,240 ja nendega toime tulla. 840 00:27:47,240 --> 00:27:48,330 >> Nüüd näen number kuus. 841 00:27:48,330 --> 00:27:51,110 Kuhu see number kuus kuuluvad? 842 00:27:51,110 --> 00:27:53,250 Meil on kaks, neli, kuus. 843 00:27:53,250 --> 00:27:54,800 Täpselt, kus ta on praegu. 844 00:27:54,800 --> 00:27:57,750 Nii saab jätta, et üksi, ja nüüd väidavad, et see osa loetelu 845 00:27:57,750 --> 00:27:58,772 Nüüd on järjestatud. 846 00:27:58,772 --> 00:28:01,230 Ja nii see tundub täiesti erinevad, et ma olen lihtsalt 847 00:28:01,230 --> 00:28:05,230 liigub läbi nimekirja siin lineaarselt, ja ma ei ole kunagi kahekordistada tagasi. 848 00:28:05,230 --> 00:28:05,730 Jah. 849 00:28:05,730 --> 00:28:06,230 Hästi. 850 00:28:06,230 --> 00:28:08,190 Nii kaheksa, kus Te kuulute? 851 00:28:08,190 --> 00:28:08,730 Siin samas. 852 00:28:08,730 --> 00:28:09,310 Perfect. 853 00:28:09,310 --> 00:28:10,210 Nüüd, üks. 854 00:28:10,210 --> 00:28:10,900 Uh-oh. 855 00:28:10,900 --> 00:28:13,010 See kõik tundub nii saab olema kallis. 856 00:28:13,010 --> 00:28:15,690 Nüüd eelmisel algoritmi, Ma vahetasin inimesi. 857 00:28:15,690 --> 00:28:18,648 Nii et ma võiks panna teda kogu tee juures alguses, kuid siis kolis Joseph. 858 00:28:18,648 --> 00:28:21,450 Aga kui ma liigun Joseph, nüüd Mis saab olema vale? 859 00:28:21,450 --> 00:28:24,250 >> Nüüd ma olen omamoodi undone-- Olen võtta üks samm edasi ja siis 860 00:28:24,250 --> 00:28:26,300 üks samm tagasi, sest nüüd Joseph oleks rikkis. 861 00:28:26,300 --> 00:28:26,830 Nii teeme seda. 862 00:28:26,830 --> 00:28:29,150 Kui sa saaksid võtta number üks ja tagasi astuda hetkeks. 863 00:28:29,150 --> 00:28:30,490 Kuidas me saame put-- mida oli su nimi oligi? 864 00:28:30,490 --> 00:28:31,130 >> ANNAN: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. Humala: Annan olemas? 866 00:28:32,610 --> 00:28:36,091 Mida peab toimuma suhtes kahele, neli, kuus, kaheksa? 867 00:28:36,091 --> 00:28:37,570 Nad kõik peavad minema. 868 00:28:37,570 --> 00:28:42,590 Nii et kui kaheksa tahaks minna Esimene, siis kuus, siis neli, siis kaks. 869 00:28:42,590 --> 00:28:45,380 Ja siis Annan, kui soovite tahaks siia tulla, hea. 870 00:28:45,380 --> 00:28:47,760 Aga siin, me oleme lihtsalt Selline makstud hind 871 00:28:47,760 --> 00:28:49,510 erinevas punktis algoritmi. 872 00:28:49,510 --> 00:28:52,550 Kui eelmisel aja valikut sorteerida ja isegi mull sorteerida, 873 00:28:52,550 --> 00:28:54,700 Ma kõnnin ja tagasi edasi, edasi ja tagasi, 874 00:28:54,700 --> 00:28:58,360 mis on kindlasti liitmist ajalist ja sõna otseses mõttes sammhaaval. 875 00:28:58,360 --> 00:29:00,660 >> Insertion sorti, esimesel lühidalt, näeb välja nagu see on 876 00:29:00,660 --> 00:29:05,150 super targemaks, et ma olen lihtsalt muutes aeglaselt ja järk-järgult edusamme, 877 00:29:05,150 --> 00:29:07,120 aga ma ei hakka seda edasi ja tagasi. 878 00:29:07,120 --> 00:29:09,410 Aga kui keegi on tõepoolest rikkis, teate 879 00:29:09,410 --> 00:29:10,840 kõik tööd ma lihtsalt pidin tegema. 880 00:29:10,840 --> 00:29:14,750 Mul oli liikuda pool nimekirja lihtsalt, et teha ruumi number üks. 881 00:29:14,750 --> 00:29:16,790 Nii et see on sama palju töö siiani seda 882 00:29:16,790 --> 00:29:18,690 tunneb, vaid teistsugust tööd tegema. 883 00:29:18,690 --> 00:29:19,370 >> Jätkame. 884 00:29:19,370 --> 00:29:22,657 Nüüd me teame, et kõik üks kuni kaheksa on järjestatud. 885 00:29:22,657 --> 00:29:23,740 Siin on mul number kolm. 886 00:29:23,740 --> 00:29:25,864 Kui soovite kiirenemist number kolm, samm tagasi üks. 887 00:29:25,864 --> 00:29:28,260 Ja mis te poisid peavad tegema? 888 00:29:28,260 --> 00:29:28,760 Yep. 889 00:29:28,760 --> 00:29:33,070 Nii et on veel üks, kaks, kolm sammu. 890 00:29:33,070 --> 00:29:36,010 Kolm ajaühikutes, et lihtsalt maksma mulle, et kolme saab nüüd sobi. 891 00:29:36,010 --> 00:29:37,460 Lõpuks seitse. 892 00:29:37,460 --> 00:29:39,730 >> Lähme edasi ja on sa astuda samm tagasi. 893 00:29:39,730 --> 00:29:42,780 See on ainult kavatse meile maksma ühe ajaühiku, kuid see on OK. 894 00:29:42,780 --> 00:29:44,170 Ja nüüd, viis läheb olla natuke kallim. 895 00:29:44,170 --> 00:29:45,340 Kui soovite sammu tagasi. 896 00:29:45,340 --> 00:29:48,380 Me peame liikuma kaheksa, seitse ja kuus. 897 00:29:48,380 --> 00:29:50,749 Ja siis kõik on nüüd järjestatud. 898 00:29:50,749 --> 00:29:52,290 Nii suur käsi meie vabatahtlike siin. 899 00:29:52,290 --> 00:29:53,554 Suur tänu. 900 00:29:53,554 --> 00:29:56,220 >> [APPLAUSE] 901 00:29:56,220 --> 00:29:56,860 >> Tänan teid kõiki. 902 00:29:56,860 --> 00:29:57,520 Tänan teid kõiki. 903 00:29:57,520 --> 00:30:02,940 Vaatame nüüd, kuidas kulukad kõik see oli. 904 00:30:02,940 --> 00:30:06,210 Vaatleme ehk Lihtsaim neist, mull omamoodi. 905 00:30:06,210 --> 00:30:09,950 Ja ma ütlen lihtsam, ainult sellepärast, saab seda lahendada aplalt lihtsalt 906 00:30:09,950 --> 00:30:11,660 määrata paarikaupa probleem. 907 00:30:11,660 --> 00:30:13,720 Kinnitage paarikaupa probleem siin, ikka ja jälle 908 00:30:13,720 --> 00:30:17,680 ja jälle, korrates nii palju korda, kui tegelikult vaja. 909 00:30:17,680 --> 00:30:21,050 >> Nii selgub, et koos mull sorteerida, noh, 910 00:30:21,050 --> 00:30:25,820 kui palju samme pean võtma esimene pass selle algoritmi? 911 00:30:25,820 --> 00:30:30,850 Ma võiks Vőta olgem see-- üks, kaks, kolm, neli, viis, kuus, seitse. 912 00:30:30,850 --> 00:30:32,190 Ja seal on kaheksa elemente siin. 913 00:30:32,190 --> 00:30:35,280 Nii et see on nagu n miinus 1 samme saada algusest nimekiri 914 00:30:35,280 --> 00:30:36,380 lõpuni nimekirja. 915 00:30:36,380 --> 00:30:41,350 >> Kuid valikut omamoodi, meelde tuletada, et ma olen valides elemendid ja jälle 916 00:30:41,350 --> 00:30:44,590 ja jälle, et on väikseim, Ma panen oma kohale, 917 00:30:44,590 --> 00:30:46,616 aga siis ma ei ole otsin minu taga uuesti. 918 00:30:46,616 --> 00:30:49,490 Nii et ma arvan, et see on natuke selgem siis esimest korda, ma võin 919 00:30:49,490 --> 00:30:52,680 võtma kõik n miinus 1 etappe leida kõige väikseim element. 920 00:30:52,680 --> 00:30:55,920 Siis panin need paika, ja ma tõstma kes oli siin varem. 921 00:30:55,920 --> 00:30:57,500 >> Aga siis ma ei pea hoida vaadates seda element, 922 00:30:57,500 --> 00:30:59,040 sest ma tean, et see juba väikseim. 923 00:30:59,040 --> 00:31:01,581 Nüüd, ma ei saa vaadata ainult seitse elemente, siis kuus elementi, 924 00:31:01,581 --> 00:31:03,290 Seejärel viis tegurit, siis nelja elementi. 925 00:31:03,290 --> 00:31:06,900 Ja nii matemaatiliselt, kui n on elementide arv või numbrid 926 00:31:06,900 --> 00:31:11,990 et alustasime, võite ette kujutada et see on sama nagu n miinus 1, 927 00:31:11,990 --> 00:31:14,250 pluss n miinus 2 sammu, pluss n miinus 3 astet, 928 00:31:14,250 --> 00:31:16,780 plus n miinus 4 samme, kõik tee alla vaid üks samm. 929 00:31:16,780 --> 00:31:18,160 Ja ma olen minu viimane inimene. 930 00:31:18,160 --> 00:31:20,650 >> Ja kui te mäletate, et palju stats raamatuid või matemaatika raamatud 931 00:31:20,650 --> 00:31:24,730 on need valemid kõvakaaneline tagasi või nende ees, 932 00:31:24,730 --> 00:31:27,690 Selgub, et selles seerias saab väljendada lihtsamalt 933 00:31:27,690 --> 00:31:28,857 kui n korda n miinus 1 jagatud 2. 934 00:31:28,857 --> 00:31:31,273 Ja see on hea, kui see ei ole esirinnas meelt. 935 00:31:31,273 --> 00:31:32,420 Aga see on tõsi. 936 00:31:32,420 --> 00:31:34,449 See on lihtsalt lihtsam viis kirjutamist. 937 00:31:34,449 --> 00:31:36,240 Ja siis, kui te arvate, tagasi algkool, 938 00:31:36,240 --> 00:31:38,698 kui sa lihtsalt alustada korrutades asju teha, seda muidugi 939 00:31:38,698 --> 00:31:41,820 on lihtsalt n ruudus miinus n jagatud 2. 940 00:31:41,820 --> 00:31:44,772 Kõik, mida ma olen teinud on laiendada väljendid seal. 941 00:31:44,772 --> 00:31:46,730 Ja nii kirjutame selle uuesti natuke teistmoodi. 942 00:31:46,730 --> 00:31:49,780 See on n ruudus jagatud 2 miinus n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Nii jälle, ma olen lihtsalt selline kohaldamisel mõned aritmeetika reeglitega. 944 00:31:53,270 --> 00:31:57,140 Aga teate nüüd, et suurim perspektiivis Selles väljendus, kui nii võib öelda, 945 00:31:57,140 --> 00:31:58,540 on see, et n ruudus. 946 00:31:58,540 --> 00:32:02,910 Nii et jah, see on n ruudus jagatuna 2 miinus n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Aga üldiselt, kui n on saab olema suur väärtus, 948 00:32:05,080 --> 00:32:08,740 Ma lähen väidavad, et n ruudus saab olema domineeriv tegur. 949 00:32:08,740 --> 00:32:10,490 See on lihtsalt saab olema suurem toetaja 950 00:32:10,490 --> 00:32:12,877 to sammude arvu kui n / 2. 951 00:32:12,877 --> 00:32:13,960 Mida ma öelda? 952 00:32:13,960 --> 00:32:16,795 Proovime lihtne näide, isegi kuigi matemaatikat saab natuke suur. 953 00:32:16,795 --> 00:32:20,210 >> Nii Oletame, et meil oli 1 miljon inimest laval, või 1 miljon asja 954 00:32:20,210 --> 00:32:21,320 et me soovime sortida. 955 00:32:21,320 --> 00:32:23,730 Olgem plug miljonit arvesse just seda valemit 956 00:32:23,730 --> 00:32:27,230 näha, kuidas paljud sammud kulub kokku sorteeri miljoni elemente kasutades näiteks 957 00:32:27,230 --> 00:32:28,560 valikut omamoodi. 958 00:32:28,560 --> 00:32:30,760 >> Nii et me tahaks olla sama valemit nagu enne. 959 00:32:30,760 --> 00:32:34,120 Ma ühendan miljonit, nii et ma saan miljon ruudus jagatud 2, 960 00:32:34,120 --> 00:32:35,990 miinus miljon jagatuna 2. 961 00:32:35,990 --> 00:32:40,180 Kui ma seda teen matemaatikat ette siin on meil 500 miljardit 962 00:32:40,180 --> 00:32:47,460 miinus 500.000, mis annab meile 499999500000, 963 00:32:47,460 --> 00:32:49,270 mis on päris darn suur. 964 00:32:49,270 --> 00:32:54,370 >> Tegelikult, kui sa võrdled nüüd 499000000000 999 miljonit 965 00:32:54,370 --> 00:33:01,210 500,000 vastu meie esialgsest väärtusest, 500 miljardit, see on nii kuradi tihe. 966 00:33:01,210 --> 00:33:06,850 Õigus? n ruudus jagatud 2 annab us-- või pigem n ruudus jagatud 2 967 00:33:06,850 --> 00:33:08,370 andis meile 500 miljardit. 968 00:33:08,370 --> 00:33:13,510 See on päris darn lähedal to 499999500000, 969 00:33:13,510 --> 00:33:17,970 mis tähendab, lahutades maha 500.000, või üldisemalt lahutades off 970 00:33:17,970 --> 00:33:20,010 n ruudus, ei ole tõesti suur asi. 971 00:33:20,010 --> 00:33:22,490 N ruudus muudab need numbrid kasvavad väga kiiresti. 972 00:33:22,490 --> 00:33:25,790 >> Nüüd, see on oluline vaid niivõrd, nagu meie, arvuti teadlased, 973 00:33:25,790 --> 00:33:29,350 üldiselt ei kavatse hooli nii palju umbes nüansse need valemid 974 00:33:29,350 --> 00:33:31,400 ja täpselt täpne vastused on. 975 00:33:31,400 --> 00:33:33,390 Me hoolime ainult, et sa tead, mida? 976 00:33:33,390 --> 00:33:37,810 Lõpus päeval, see valem on järjekorras n ruudus. 977 00:33:37,810 --> 00:33:39,350 >> Jah, me jagame 2 seal. 978 00:33:39,350 --> 00:33:41,360 Jah, me lahutades maha n miinus 2. 979 00:33:41,360 --> 00:33:46,860 Aga lõpus päeval, termin et on tõesti valus juures ja maksab meil 980 00:33:46,860 --> 00:33:48,995 palju samme, et ruudu mõiste. 981 00:33:48,995 --> 00:33:51,370 Ja mis siis arvuti teadlane läheb tavaliselt teha 982 00:33:51,370 --> 00:33:54,160 on ignoreerida kõiki neid väiksem järku, 983 00:33:54,160 --> 00:33:56,900 ja lihtsalt vaadata mis aitab kõige kuludega. 984 00:33:56,900 --> 00:34:00,530 >> Ja see on tore, sest me suudame nüüd rääkida palju suurem üldisus 985 00:34:00,530 --> 00:34:02,470 umbes algoritmide ja võib neid võrrelda. 986 00:34:02,470 --> 00:34:04,550 Ja see, et ma olen kasutades seda O on tahtlik. 987 00:34:04,550 --> 00:34:06,680 Kui ma ütlen tellimusel ja ma olen just 988 00:34:06,680 --> 00:34:09,560 viidates midagi Big O. Ja suur O 989 00:34:09,560 --> 00:34:14,090 on märge, et arvuti teadlane kasutab kirjeldada 990 00:34:14,090 --> 00:34:16,710 ülemine piir midagi. 991 00:34:16,710 --> 00:34:21,150 >> Nii et kui sa ütled, et algoritm on suur O n ruudus 992 00:34:21,150 --> 00:34:23,380 nagu ma pakutud vaid Hetk tagasi, et vahendid 993 00:34:23,380 --> 00:34:27,710 mis mõttes oma jooksvaid aega või oma tõhusust, 994 00:34:27,710 --> 00:34:30,090 kulub tellimusel n ruudus samme. 995 00:34:30,090 --> 00:34:31,420 Võib-olla rohkem, võibolla vähem. 996 00:34:31,420 --> 00:34:33,435 Aga see, mis järjekorras n ruudus. 997 00:34:33,435 --> 00:34:34,560 Ja see on ülemise. 998 00:34:34,560 --> 00:34:36,530 Ta ei kavatse olla valusam kui see. 999 00:34:36,530 --> 00:34:40,800 Ta ei kavatse olla n kuubis, või 2 astmes n, või midagi palju suurem. 1000 00:34:40,800 --> 00:34:43,800 See on ülemine piir mida iganes, et kulu on. 1001 00:34:43,800 --> 00:34:46,150 Nii sest olgem kaaluda vaid mõned näited. 1002 00:34:46,150 --> 00:34:49,820 Ja see on vaid piiratud nimekirja väga sage töötab korda 1003 00:34:49,820 --> 00:34:52,870 algoritmi, mis on mõeldud illustreerivad mõningaid asju me oleme 1004 00:34:52,870 --> 00:34:53,600 näinud juba. 1005 00:34:53,600 --> 00:34:58,060 >> Nii näiteks juhul, valikut sorteerida, mida ma väidan siin 1006 00:34:58,060 --> 00:35:02,250 on see, et valikut omamoodi jooksvate aeg on järjekorras n ruudus. 1007 00:35:02,250 --> 00:35:06,260 Halvimal juhul, ma lähen terve hulk juhuslikke numbreid siin. 1008 00:35:06,260 --> 00:35:08,600 Ja nagu me nägime matemaatiliselt, kui ma saan jalgsi 1009 00:35:08,600 --> 00:35:11,310 loendis kaudu nimekirja, valides järgmiseks väikseim 1010 00:35:11,310 --> 00:35:14,410 element uuesti ja uuesti, kui ma tegelikult kirjutada kõik sammud 1011 00:35:14,410 --> 00:35:18,750 Ma viin nagu ma ettepaneku formulaically enne, see on suurusjärgus n ruudus 1012 00:35:18,750 --> 00:35:20,370 samme, et ma olen võttes. 1013 00:35:20,370 --> 00:35:24,520 >> Ja selgub, et mull sorteerida ning sisestamise omamoodi 1014 00:35:24,520 --> 00:35:27,370 on lihtsalt nii aeglane halvimal juhul. 1015 00:35:27,370 --> 00:35:32,040 Võtame näiteks sisestamise sorteerida, väga viimane algoritm käsil, 1016 00:35:32,040 --> 00:35:35,500 mis oli meil vaadata element, ja paigaldage siis, kui ta kuulub. 1017 00:35:35,500 --> 00:35:38,720 Ja siis me vaatasime järgmise elemendi, ja lisada see, kuhu see kuulub. 1018 00:35:38,720 --> 00:35:40,990 >> Nii leiavad parima stsenaariumi. 1019 00:35:40,990 --> 00:35:45,590 Oletame, mul oli mu vabatahtlike rivistama sõna otseses mõttes nagu see üks läbi kaheksa, 1020 00:35:45,590 --> 00:35:47,440 juba järjestatud. 1021 00:35:47,440 --> 00:35:51,300 Mitu sammu on sisestamise omamoodi kavatseme sorteerida kaheksa inimest, 1022 00:35:51,300 --> 00:35:55,640 kui nad jõuavad lavale niimoodi välja? 1023 00:35:55,640 --> 00:35:57,410 >> Kaheksa inimest on juba järjestatud. 1024 00:35:57,410 --> 00:35:58,760 Ja ma kasutan sisestamise omamoodi. 1025 00:35:58,760 --> 00:36:02,180 See viimane algoritme. 1026 00:36:02,180 --> 00:36:03,640 Noh, olgem taaskehtestada päris kiiresti. 1027 00:36:03,640 --> 00:36:05,504 Nii et kui ma hakkan siin, ma näen ühte. 1028 00:36:05,504 --> 00:36:06,420 Kuhu see üks kuulub? 1029 00:36:06,420 --> 00:36:07,730 See kuulub siin. 1030 00:36:07,730 --> 00:36:08,330 Näen kahte. 1031 00:36:08,330 --> 00:36:09,660 Kust kaks kuulute? 1032 00:36:09,660 --> 00:36:10,260 Siin samas. 1033 00:36:10,260 --> 00:36:10,900 Ma näen kolme. 1034 00:36:10,900 --> 00:36:11,920 Kust kolm kuuluvad? 1035 00:36:11,920 --> 00:36:12,480 Siin samas. 1036 00:36:12,480 --> 00:36:13,100 >> Ma näen nelja. 1037 00:36:13,100 --> 00:36:13,600 Siin samas. 1038 00:36:13,600 --> 00:36:15,660 Viis, kuus, seitse, kaheksa. 1039 00:36:15,660 --> 00:36:17,320 Ei ole mingit põhjust ennast kordama. 1040 00:36:17,320 --> 00:36:21,260 Ja nii mitu sammu on see, et nii n? 1041 00:36:21,260 --> 00:36:23,870 See tellimusel n samme, eks? n miinus 1. 1042 00:36:23,870 --> 00:36:27,567 Aga ma võtsin lineaarne number samme, ja nüüd ma olen teinud. 1043 00:36:27,567 --> 00:36:28,900 Nii et parimal juhul küll. 1044 00:36:28,900 --> 00:36:29,983 Aga halval juhul? 1045 00:36:29,983 --> 00:36:32,730 Mis kaheksa olid seal, ja seitse olid seal, 1046 00:36:32,730 --> 00:36:35,840 ja üks ja kaks olid siin, nii et nimekiri oli tõesti vastupidine? 1047 00:36:35,840 --> 00:36:38,300 >> Noh, mis juhtub tõepoolest kas see on number? 1048 00:36:38,300 --> 00:36:41,300 Ja me teeme vaid paar näidet. 1049 00:36:41,300 --> 00:36:49,300 Mis siis, kui tõepoolest arv kaheksa on siin, ja number-- whoops. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Mis siis, kui tõepoolest arv Kaheksa on kõik teed siin, 1052 00:36:56,430 --> 00:36:57,790 ja ma kasutan sisestamise omamoodi? 1053 00:36:57,790 --> 00:36:58,290 >> OKEI. 1054 00:36:58,290 --> 00:37:00,280 Väidan hetkel on olemas. 1055 00:37:00,280 --> 00:37:03,152 Aga nüüd, seven-- kus ei seitse minna? 1056 00:37:03,152 --> 00:37:04,360 Muidugi, see läheb siia. 1057 00:37:04,360 --> 00:37:06,760 Nii et ma pean liikuma kaheksa üle ühest kohast. 1058 00:37:06,760 --> 00:37:08,554 Nüüd kuus, kus see läheb? 1059 00:37:08,554 --> 00:37:09,220 Noh, eks. 1060 00:37:09,220 --> 00:37:13,150 Nüüd ma pean liikuma kaheksa üle koht, ja seitse üle koht, 1061 00:37:13,150 --> 00:37:14,440 ja siis ma sulpsti maha kuus. 1062 00:37:14,440 --> 00:37:16,870 >> Nii esmakordselt seda kulu mul üks samm fikseerida asju, 1063 00:37:16,870 --> 00:37:18,570 siis see maksab mulle kaks sammu asju parandada. 1064 00:37:18,570 --> 00:37:20,370 Mitu sammu on ta aega võtab, et määrata 1065 00:37:20,370 --> 00:37:22,720 asju panna viis õiges kohas? 1066 00:37:22,720 --> 00:37:23,340 Kolm. 1067 00:37:23,340 --> 00:37:29,520 Sest nüüd ma pean liikuda üks, kaks, kolm. 1068 00:37:29,520 --> 00:37:32,430 Mitu sammu on see aega võtab panna neli õiges kohas? 1069 00:37:32,430 --> 00:37:36,040 4 pluss 5, pluss 6, pluss 7. 1070 00:37:36,040 --> 00:37:40,260 >> Ja nii see on matemaatiliselt identne mida me kirjeldatud valikut omamoodi. 1071 00:37:40,260 --> 00:37:42,130 Meil on selles sarjas See on lihtsalt suureneb. 1072 00:37:42,130 --> 00:37:45,650 1 pluss 2 pluss 3 pluss 4, või vastupidi, 7 plus 6 1073 00:37:45,650 --> 00:37:52,610 pluss 5 pluss 4 lisab kuni tänase eesmärgil tellimusel n ruudus. 1074 00:37:52,610 --> 00:37:57,640 >> Nii et lubage mul ette näha ka seda, et mull sorteerida on ka n ruudus. 1075 00:37:57,640 --> 00:38:01,340 Kuna mull sorteerida, iga kord, kui ma nimekiri läbi, 1076 00:38:01,340 --> 00:38:03,100 Ma võtan umbes kui palju samme? 1077 00:38:03,100 --> 00:38:06,260 Iga kord, kui ma sõna otseses mõttes sealt jalutada seal? 1078 00:38:06,260 --> 00:38:07,960 Umbes n samme. 1079 00:38:07,960 --> 00:38:12,650 Aga mitu korda võiks ma pead minema läbi nimekirja? 1080 00:38:12,650 --> 00:38:13,920 >> Noh, umbes n korda. 1081 00:38:13,920 --> 00:38:15,680 Võib-olla n miinus 1, kuid umbes n korda. 1082 00:38:15,680 --> 00:38:16,430 Noh, miks see nii on? 1083 00:38:16,430 --> 00:38:19,560 Noh, mull sorteerida, kui hakkame koos mull sorteerida, 1084 00:38:19,560 --> 00:38:23,570 loetelule halvim võimalik olukord, mis omakorda on täiesti 1085 00:38:23,570 --> 00:38:25,550 tagasi, mida juhtub? 1086 00:38:25,550 --> 00:38:28,830 Lähen läbi nimekirja ja number üks kuulub kogu tee sinna. 1087 00:38:28,830 --> 00:38:33,280 >> Kuid mull sorteerida, kui kaugele ei üks liikuda minu esimese läbida nimekirja? 1088 00:38:33,280 --> 00:38:36,620 Mitu laigud ei ta saada lähemale õige koht? 1089 00:38:36,620 --> 00:38:37,240 Ainult üks. 1090 00:38:37,240 --> 00:38:40,281 Nii et kui sa mingi põhjus selle kaudu, iga kord läbi selle algoritmi, 1091 00:38:40,281 --> 00:38:41,880 Davidi võttes umbes n samme. 1092 00:38:41,880 --> 00:38:44,940 Aga kui palju läbib loendis on see 1093 00:38:44,940 --> 00:38:49,060 aega võtab ühe mull vasakul kui ta kuulub? 1094 00:38:49,060 --> 00:38:51,840 >> Tal on liikuda nagu, n ruumid sel viisil. 1095 00:38:51,840 --> 00:38:57,960 Nii lihtsalt teha sorteerimise nimekirja, Mul on kõndida edasi-tagasi n korda. 1096 00:38:57,960 --> 00:39:01,540 Ja iga kord, ma olen vaadates n elementi. 1097 00:39:01,540 --> 00:39:05,410 Nii et ärge n asju n korda järjekorras n ruudus. 1098 00:39:05,410 --> 00:39:07,220 >> Nüüd me näeme mõnedes on lühikesed püksid, mis 1099 00:39:07,220 --> 00:39:10,440 on põimitud CS50 järgmise probleemi määrata, teine ​​lähenemine on need, 1100 00:39:10,440 --> 00:39:13,490 aga nüüd, lähme lihtsalt kaaluda mõned muud jooksvad korda 1101 00:39:13,490 --> 00:39:16,840 eriti kui sortimine ones võtta natuke aega imbuma. 1102 00:39:16,840 --> 00:39:21,790 Mis algoritmi oleme näinud juba mis võtab tellimusel n sammud? 1103 00:39:21,790 --> 00:39:27,560 >> Mida peaks lineaarne number samme, et me oleme näinud siiani? 1104 00:39:27,560 --> 00:39:29,350 Mis see on? 1105 00:39:29,350 --> 00:39:30,480 Telefoni kataloogi otsingu. 1106 00:39:30,480 --> 00:39:31,390 Esimene algoritm. 1107 00:39:31,390 --> 00:39:31,560 Õigus? 1108 00:39:31,560 --> 00:39:33,650 Kus me oleme lineaarselt otsivad Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Tõepoolest. 1110 00:39:34,150 --> 00:39:37,180 Nädalast null, kui hakkasin keerates ühe lehekülje korraga 1111 00:39:37,180 --> 00:39:40,095 ja ma isegi öelda, et see oli selline lineaarse tunnet algoritmi, 1112 00:39:40,095 --> 00:39:42,720 ja meil oli, et pilti papi otse punase joone 1113 00:39:42,720 --> 00:39:44,678 ja sirge kollane line, need olid tõepoolest 1114 00:39:44,678 --> 00:39:46,810 algoritme, mis on suurte O n. 1115 00:39:46,810 --> 00:39:50,680 >> Sest leida Mike Smith telefon raamat n lehti, halvimal juhul, 1116 00:39:50,680 --> 00:39:52,422 võiks mind n samme. 1117 00:39:52,422 --> 00:39:53,630 Aga võttes käimist? 1118 00:39:53,630 --> 00:39:55,790 Üks, kaks, kolm, neli, viis, kuus. 1119 00:39:55,790 --> 00:39:59,420 Mis on töötamise aeg selle algoritm võttes käimist? 1120 00:39:59,420 --> 00:40:03,070 Big O n, sest teoreetiliselt I on juhtida kõik ruumis. 1121 00:40:03,070 --> 00:40:05,861 >> Nüüd kui kõrvale, kuidas on lood teiste optimeerimine nädalast null? 1122 00:40:05,861 --> 00:40:08,117 Kaks, neli, kuus, kaheksa, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Arvuti teadlane oleks mõistma, oodake minut, 1124 00:40:10,200 --> 00:40:12,320 see tellimusel n jagatud kahte etappi. 1125 00:40:12,320 --> 00:40:12,820 Õigus? 1126 00:40:12,820 --> 00:40:14,444 Sest ma teen kaks inimest korraga. 1127 00:40:14,444 --> 00:40:17,015 Aga me ei kavatse ignoreerida need väiksemad mõttes, 1128 00:40:17,015 --> 00:40:19,140 ja me lihtsalt läheb visata jagage 2, 1129 00:40:19,140 --> 00:40:21,830 ja lihtsalt öelda, suur O n sel algoritmi samuti. 1130 00:40:21,830 --> 00:40:22,760 >> Aga see? 1131 00:40:22,760 --> 00:40:26,170 Me vahele üle mõned neist, kuid mida oli algoritmi, mis oli samamoodi n? 1132 00:40:26,170 --> 00:40:29,900 Mis võttis umbes samamoodi n sammud? 1133 00:40:29,900 --> 00:40:30,870 Lõhe ja vallutada. 1134 00:40:30,870 --> 00:40:31,369 Täpselt. 1135 00:40:31,369 --> 00:40:33,900 Nagu telefoniraamatust näiteks nädal null ja täna, 1136 00:40:33,900 --> 00:40:36,191 kus me jagada probleem uuesti ja uuesti ja uuesti. 1137 00:40:36,191 --> 00:40:39,070 Me juhtis ta laual nädal null kõvera roheline joon, 1138 00:40:39,070 --> 00:40:41,460 ja me ütlesime, et päev oli logaritmiline algoritm. 1139 00:40:41,460 --> 00:40:44,970 >> Ja tõepoolest, astmete arv on võtab täita jaga ja valitse, 1140 00:40:44,970 --> 00:40:48,610 või Kahendotsingupuu kui hakkame nimetades seda, kui telefoniraamatus, 1141 00:40:48,610 --> 00:40:50,680 on järjekorras log ja samme. 1142 00:40:50,680 --> 00:40:52,470 Ja see on natuke imelik ühe. 1143 00:40:52,470 --> 00:40:54,910 >> Mis teeb ühe sammu või täpsemalt 1144 00:40:54,910 --> 00:40:56,240 pidev mitmeid samme? 1145 00:40:56,240 --> 00:40:58,865 Võib-olla on kaks, äkki see on kolm, kuid arvuti teadlane lihtsalt 1146 00:40:58,865 --> 00:41:01,423 lihtsustab see nii suur O 1, mõned pidev mitmeid samme. 1147 00:41:01,423 --> 00:41:04,256 Mis on midagi, mida võiks teha, et võtab pidev mitmeid samme? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Mis on töötamise aeg plaksutamine? 1150 00:41:10,930 --> 00:41:11,920 Pidev aega. 1151 00:41:11,920 --> 00:41:12,420 Õigus? 1152 00:41:12,420 --> 00:41:15,490 Like, milline on töötamise aeg tee midagi, mis võtab vaid üks 1153 00:41:15,490 --> 00:41:18,570 laadsete printida F Hello World. 1154 00:41:18,570 --> 00:41:24,110 See võiks öelda, et pidev aega, kui ei ole vähem nurgas puhul print F, 1155 00:41:24,110 --> 00:41:28,260 Millised võivad sõiduaega prindi F tegelikult olla? 1156 00:41:28,260 --> 00:41:28,790 Ja miks? 1157 00:41:28,790 --> 00:41:30,550 Mis on n mõõtmist sellisel juhul? 1158 00:41:30,550 --> 00:41:32,251 >> Sihtrühm: [kuuldamatu]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. Humala: Täpselt. 1160 00:41:33,250 --> 00:41:34,900 Märkide arv tahame trükkida. 1161 00:41:34,900 --> 00:41:36,191 Nii et see on väga kontekstitundlik. 1162 00:41:36,191 --> 00:41:39,910 Täna oleme olnud suunatud partii tähed ja numbrid siin laual. 1163 00:41:39,910 --> 00:41:43,540 Aga see võib olla ka tegelaste tegelik string. 1164 00:41:43,540 --> 00:41:46,420 Nii selgub ka teine meede, mis hakkab hooliv, 1165 00:41:46,420 --> 00:41:48,530 ja see on vastupidine suur O, nii rääkida. 1166 00:41:48,530 --> 00:41:50,120 >> See on omega märke. 1167 00:41:50,120 --> 00:41:53,380 Arvestades suur O tähendab, mis on, on ülemist piiri peal oma sõiduaega? 1168 00:41:53,380 --> 00:41:55,580 Maksimaalselt, kui palju aega võiks midagi teha? 1169 00:41:55,580 --> 00:41:59,250 Omega-- sorry see hoiab tulemas up-- on vastupidine, 1170 00:41:59,250 --> 00:42:02,960 kusjuures see on alumise piiri ajaga midagi võiks võtta. 1171 00:42:02,960 --> 00:42:10,480 >> So. Näiteks milline on algoritmi mis võtab alati n ruudus sammud? 1172 00:42:10,480 --> 00:42:15,600 Noh, üks algoritme oleme näinud Täna, tegelikult võib olla, et hästi. 1173 00:42:15,600 --> 00:42:16,720 Valik omamoodi. 1174 00:42:16,720 --> 00:42:18,270 Valik omamoodi päris loll. 1175 00:42:18,270 --> 00:42:21,760 Isegi kui algorithm-- kahju isegi Kui massiiv on juba sorteeritud, 1176 00:42:21,760 --> 00:42:24,150 valikut omamoodi läheb hoida jalgsi läbi nimekirja 1177 00:42:24,150 --> 00:42:28,907 veendumaks, et see on kõige väiksem element uuesti ja uuesti ja uuesti. 1178 00:42:28,907 --> 00:42:31,740 Ja kuigi sa inimesed on publik teab, et oodake minut, 1179 00:42:31,740 --> 00:42:33,948 sa juba möödas väikseim element, arvuti 1180 00:42:33,948 --> 00:42:37,300 ei tea, et enne, kui see näeb välja kõik teed läbi nimekirja. 1181 00:42:37,300 --> 00:42:40,240 Samuti alampiiri, mis Samuti võib arvesse võtta 1182 00:42:40,240 --> 00:42:42,000 võib olla lineaarne aeg. 1183 00:42:42,000 --> 00:42:48,260 >> Kui palju aega läheb aega, et Sorteeri n elementi parim 1184 00:42:48,260 --> 00:42:52,420 Juhul kasutades midagi mull omamoodi? 1185 00:42:52,420 --> 00:42:54,280 Oletame, et teie loend on juba järjestatud. 1186 00:42:54,280 --> 00:42:56,696 Me ütlesime mull omamoodi võtab järjekorras n ruudus samme. 1187 00:42:56,696 --> 00:42:59,640 Aga mis siis, kui see on juba järjestatud? 1188 00:42:59,640 --> 00:43:02,310 Mis siis, kui sa mõistad pärast üks läbida massiivi 1189 00:43:02,310 --> 00:43:03,540 mis sa oled teinud ühtegi vahetustehingud? 1190 00:43:03,540 --> 00:43:05,970 Kas teil on vaja hoida muutes möödub? 1191 00:43:05,970 --> 00:43:06,470 >> Ei. 1192 00:43:06,470 --> 00:43:10,340 Nii alampiiri mull omamoodi Võib öelda, et lineaarne. 1193 00:43:10,340 --> 00:43:11,830 Omega n. 1194 00:43:11,830 --> 00:43:14,450 Ja me võime vaadata teised neist samuti. 1195 00:43:14,450 --> 00:43:17,990 Võtame pilgu just visualiseerimine siin 1196 00:43:17,990 --> 00:43:20,790 näha, kuidas need eristuda. 1197 00:43:20,790 --> 00:43:24,592 Ma lähen siin sellesse leht, mis on saadaval C50 kodulehel 1198 00:43:24,592 --> 00:43:27,550 kuid see on valu, et saada tööd, kuna ta kasutab tehnoloogiat nimega 1199 00:43:27,550 --> 00:43:30,560 Javat, mis on suuresti toeta nendel päevadel, 1200 00:43:30,560 --> 00:43:32,730 vähemalt Chrome ja teatud teised. 1201 00:43:32,730 --> 00:43:37,070 >> Ja lubage mul minna ja kiirendada selle up ja seletada, mis toimub. 1202 00:43:37,070 --> 00:43:40,840 See on demonstratsioon mull Sorteeri esimene algoritm me vaatasime. 1203 00:43:40,840 --> 00:43:43,950 Ja see on visualiseerimine, et iga Nende baarid tähistab number. 1204 00:43:43,950 --> 00:43:45,710 Mida suurem on baar, mida suurem number. 1205 00:43:45,710 --> 00:43:47,520 Mida väiksem on baar, väiksem number. 1206 00:43:47,520 --> 00:43:50,353 Ja mida näed visuaalselt, isegi kuigi see läheb super kiire, 1207 00:43:50,353 --> 00:43:53,699 on see, et punane riba on nagu mina, jalgsi edasi-tagasi millega probleeme. 1208 00:43:53,699 --> 00:43:56,740 Näete, et suurem elemendid tõepoolest mullitava kuni paremalt 1209 00:43:56,740 --> 00:43:59,650 ja väiksematele elemendid on vahustamine kuni vasakule. 1210 00:43:59,650 --> 00:44:01,870 Ja siin, kui me tegelikult lähemalt, 1211 00:44:01,870 --> 00:44:04,330 me saame tegelikult loota võrdluste arv ja vahetustehingud 1212 00:44:04,330 --> 00:44:05,350 mis olid tehtud. 1213 00:44:05,350 --> 00:44:07,360 >> Kuid selle asemel, vaatame teisel algoritm 1214 00:44:07,360 --> 00:44:11,240 me vaatasime varem meie vabatahtlikud, valiku omamoodi. 1215 00:44:11,240 --> 00:44:13,500 Visuaalselt on tal väga erinev mõju. 1216 00:44:13,500 --> 00:44:16,820 Aga see on jällegi väga intuitiivne, in et me peame valides järgmise väikseim 1217 00:44:16,820 --> 00:44:18,660 element, ja me saime natuke õnne. 1218 00:44:18,660 --> 00:44:20,110 See tundus täiesti kiiremini. 1219 00:44:20,110 --> 00:44:22,840 Aga kui me jooksime seda uuesti ja uuesti ja jälle palju sisendeid, 1220 00:44:22,840 --> 00:44:26,680 me näeme, et see on tõepoolest ikka suur O n ruudus. 1221 00:44:26,680 --> 00:44:29,920 >> Teeme ühe Viimane Siin sisestamise sorteerida, 1222 00:44:29,920 --> 00:44:33,180 mis oli kolmas algoritmi me vaatasime, ja tagasikutsumine 1223 00:44:33,180 --> 00:44:36,700 et see üks tegeleb elemente kui tal tekib neile 1224 00:44:36,700 --> 00:44:39,290 kuid siis äkki vahetuses asjad üle, et teha ruumi, 1225 00:44:39,290 --> 00:44:41,660 sisestades elemente, kuhu nad kuuluvad. 1226 00:44:41,660 --> 00:44:45,330 >> Ja ka see jõuab andes lõpptulemust. Nüüd kõik kolm neist 1227 00:44:45,330 --> 00:44:46,490 tunda päris kiire. 1228 00:44:46,490 --> 00:44:48,740 Ja tõepoolest, ma jooksin neid kell päris hea klipp. 1229 00:44:48,740 --> 00:44:52,510 Aga põhimõtteliselt on nad kõik päris jube, kui aus olla. 1230 00:44:52,510 --> 00:44:56,960 Kõik need algoritmid seni mis töötavad suure O n ruudus 1231 00:44:56,960 --> 00:44:59,270 võtab üsna natuke aega joosta lõpus. 1232 00:44:59,270 --> 00:45:01,920 >> Ja tõepoolest, me näeme ja tundub, et see lõpuks 1233 00:45:01,920 --> 00:45:04,090 kui ma tõmba see kolmas ja viimane demo. 1234 00:45:04,090 --> 00:45:05,840 See on veel üks visualiseerimine, et läheb 1235 00:45:05,840 --> 00:45:08,500 näidata mull omamoodi vasakul, valikut omamoodi keskel, 1236 00:45:08,500 --> 00:45:13,410 ja midagi, kui üht meie Samas tekitab varem soovitanud, 1237 00:45:13,410 --> 00:45:15,020 ühendada sorteerida õige. 1238 00:45:15,020 --> 00:45:16,937 Jaga ja valitse strateegia paremal. 1239 00:45:16,937 --> 00:45:19,520 Ja see on tegelikult see, mida me oleme läheb vaadata kolmapäeval. 1240 00:45:19,520 --> 00:45:21,990 Aga olgem aega neid paralleelselt. 1241 00:45:21,990 --> 00:45:26,765 On ligikaudu sama arvu elemente, kõik töötavad samal ajal. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble omamoodi vs valikut Sorteeri vs ühendamine omamoodi. 1244 00:45:34,440 --> 00:45:36,760 >> Nüüd on nad kõik töötavad teoreetiliselt samaaegselt. 1245 00:45:36,760 --> 00:45:39,830 Protsessor töötab sama kiirusega, kuid te 1246 00:45:39,830 --> 00:45:44,014 tunda, kuidas igav on väga kiiresti hakkab muutuma, 1247 00:45:44,014 --> 00:45:45,930 ja kuidas kiiresti kui me süstida natuke nädalas 1248 00:45:45,930 --> 00:45:49,330 null algoritmid saab me asju kiirendada. 1249 00:45:49,330 --> 00:45:51,760 >> Ja nüüd lähme võrrelda Nende ühe viimase kujul. 1250 00:45:51,760 --> 00:45:55,710 Ma lähen edasi minna et CS50 veebisaidil kus 1251 00:45:55,710 --> 00:45:59,020 meil on see viimane lüli täna, kus keegi internetis 1252 00:45:59,020 --> 00:46:03,960 sõbralikult kokku pandud video, mis lööb mida erinevad sorteerimine 1253 00:46:03,960 --> 00:46:07,510 algoritme tunduda. 1254 00:46:07,510 --> 00:46:09,577 See on sisestamise omamoodi. 1255 00:46:09,577 --> 00:46:12,072 >> [Piiksumine] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Millest sa rakendades sagedus põhineb tulba kõrgus baar. 1258 00:46:16,850 --> 00:46:19,826 See on mull omamoodi. 1259 00:46:19,826 --> 00:46:21,822 >> [WARPED piiksumine] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Järgmisena on-- tulevad kuni järgmise on-- valikut omamoodi, 1262 00:46:45,774 --> 00:46:48,820 kus jälle, me valides Järgmise väikseim element, 1263 00:46:48,820 --> 00:46:51,820 ja me näeme seda kasvavate vasakult paremale. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Merge omamoodi, meie võitja seni täna. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Pane tähele, kuidas see jagatakse asju arvesse [kuuldamatu] poole ja kvartalites. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome omamoodi, mis meil ei ole rääkisime, ja loob visuaalselt 1270 00:47:21,660 --> 00:47:24,450 ja audally natuke erineva kuju ja heli. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Läheb edasi ja tagasi, puhastamise asju. 1273 00:47:30,160 --> 00:47:32,230 Tutvuge ka heapsort Selle mehe kodulehel. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Ja see ongi kõik. 1276 00:47:36,810 --> 00:47:38,210 Me näeme järgmine kord. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing JA MUUSIKA] 1279 00:47:48,334 --> 00:50:24,839