1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Muzika] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. Malan: Kjo është CS50. 5 00:00:12,550 --> 00:00:14,612 Dhe kjo është fillimi i javës së tretë. 6 00:00:14,612 --> 00:00:16,820 Pra, ne kemi marrë një shumë të emocionuese gjëra për të mbuluar sot. 7 00:00:16,820 --> 00:00:20,160 Një shumë e mundësive për vullnetarë deri në skenë. 8 00:00:20,160 --> 00:00:22,780 Dhe në fund të fundit, sot është jo në lidhje me kodin fare. 9 00:00:22,780 --> 00:00:24,820 Por kjo është në lidhje me idetë, dhe kjo është në lidhje me algoritme, 10 00:00:24,820 --> 00:00:28,420 dhe në fakt duke sjellë përsëri disa prej mësimet e nxjerra nga javë zero, 11 00:00:28,420 --> 00:00:31,910 ku kujtojnë, ne futur këtë gjë të shëmtuar. 12 00:00:31,910 --> 00:00:33,880 Dhe huamarrja frymëzim nga ajo, për të filluar 13 00:00:33,880 --> 00:00:36,879 për të zgjidhur gjithnjë e më të sofistikuara Problemet algoritmikisht. 14 00:00:36,879 --> 00:00:38,420 Por së pari, një çift i njoftimeve. 15 00:00:38,420 --> 00:00:42,020 Pra, një, në qoftë se ju do të donte për t'u bashkuar Stafi dhe Shokët e klasës CS50-së në drekë 16 00:00:42,020 --> 00:00:44,670 kjo e premte, si këtu dhe në Cambridge, dhe në New Haven, 17 00:00:44,670 --> 00:00:48,060 ju lutem vizitoni Sigurisht së Faqja e internetit, ku një URL mund të gjenden. 18 00:00:48,060 --> 00:00:50,390 Leksion këtë të mërkurë do të të mos jetë këtu në Sanders. 19 00:00:50,390 --> 00:00:53,610 Ajo do të jetë vetëm online, kështu që akorduar në në faqen e internetit CS50 e, 20 00:00:53,610 --> 00:00:55,850 nëse këtu në Kembrixh ose New Haven si. 21 00:00:55,850 --> 00:00:58,110 >> Dhe pastaj problemi vendosur dy tashmë është në duart tuaja. 22 00:00:58,110 --> 00:01:03,067 Nëse ju nuk e keni hodh në krahun ende, më lejoni për të ofruar sugjerimin fjalë të ashpra 23 00:01:03,067 --> 00:01:05,150 se, sidomos tani, si problemi përcakton paraprakisht, 24 00:01:05,150 --> 00:01:08,669 ju me të vërtetë duan të fillojnë tani, në qoftë se nuk njom pak në fundjavë ose para 25 00:01:08,669 --> 00:01:10,710 kur ata së pari të shkojnë jashtë në Premteve, sepse ju do të 26 00:01:10,710 --> 00:01:14,380 të gjeni se ata nuk janë domosdoshmërisht duke marrë më të gjatë ose më të vështirë për 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Unë mendoj se ju do të gjeni se, në përgjithësi, ata kanë tendencë për të marrë afërsisht 29 00:01:17,575 --> 00:01:18,892 rreth të njëjtën sasi kohe. 30 00:01:18,892 --> 00:01:20,850 Por kjo sigurisht varet për nxënësit, dhe atë 31 00:01:20,850 --> 00:01:22,880 varet nga mendim me të cilat ju qasje atë. 32 00:01:22,880 --> 00:01:24,910 Por pa ndryshim, ju do të jeni për të drejtuar kundër një mur, 33 00:01:24,910 --> 00:01:26,350 dhe ju jeni duke shkuar për të goditur disa bug, dhe ju jeni vetëm 34 00:01:26,350 --> 00:01:27,950 nuk do të jetë në gjendje të të marrë përsipër atë në një pikë. 35 00:01:27,950 --> 00:01:31,380 Dhe kjo është jashtëzakonisht e vlefshme për të të jetë në gjendje për të hap larg, kthehen të nesërmen, 36 00:01:31,380 --> 00:01:35,286 shkoni në orarit të punës, postoni në CS50 Diskutoni apo si, që në fakt të marrë zhbllokuar. 37 00:01:35,286 --> 00:01:36,160 Pra, mbani në mend. 38 00:01:36,160 --> 00:01:40,830 Duke filluar hershme të jetë e mundur është gjëja më e mirë që ju mund të bëni. 39 00:01:40,830 --> 00:01:44,160 Kështu që këtu është ku kemi filluar klasa, mbi në javë zero. 40 00:01:44,160 --> 00:01:47,441 Dhe mund të marrim një vullnetar këtu për të ndihmuar mua të gjej mics? 41 00:01:47,441 --> 00:01:47,940 NE RREGULL. 42 00:01:47,940 --> 00:01:48,900 Këmbë tashmë. 43 00:01:48,900 --> 00:01:50,080 Eja up. 44 00:01:50,080 --> 00:01:53,707 Mendoj se është se si ajo do të punojë. 45 00:01:53,707 --> 00:01:54,415 Si e ke emrin? 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 Eja up. 49 00:01:57,910 --> 00:01:58,619 Gëzohem që u njohëm. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Gëzohem që u njohëm. 51 00:01:59,910 --> 00:02:02,772 DAVID J. Malan: Dhe ju ishit këtu me ne në javën zero, natyrisht. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: Unë kam qenë. 53 00:02:03,028 --> 00:02:03,160 Isha. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. Malan: Pra, mund të shkoni përpara dhe për të gjetur për ne Mike Smith, 55 00:02:05,868 --> 00:02:08,639 aq shpejt si ju mund? 56 00:02:08,639 --> 00:02:10,639 Sa më shpejtë që mundeni. 57 00:02:10,639 --> 00:02:13,756 Fjalë për fjalë marramendës problemin në gjysmën e si ju duhet të. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. Malan: Fjalë për fjalë marramendës problemin në gjysmë. 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 Shume mire. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. Malan: OK. 65 00:02:23,700 --> 00:02:24,200 Të mirë. 66 00:02:24,200 --> 00:02:24,701 Faleminderit. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Shumë mirë. 68 00:02:25,700 --> 00:02:26,210 NE RREGULL. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. Malan: Dhe kështu tani, ju keni whittled atë poshtë 70 00:02:27,610 --> 00:02:29,320 në gjysmën e madhësisë së problemit. 71 00:02:29,320 --> 00:02:31,267 Tani, ne jemi deri në një të katërtën. 72 00:02:31,267 --> 00:02:33,475 A jeni duke i kushtuar vëmendje të cilën anë ne jemi duke e mbajtur? 73 00:02:33,475 --> 00:02:34,405 >> [Duke qeshur] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Po, unë think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. Malan: Cilat seksion jemi në? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: Mufflers, kështu. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. Malan: OK. 78 00:02:39,941 --> 00:02:42,810 Por, Mike Smith po shkon të jetë pas Mufflers. 79 00:02:42,810 --> 00:02:44,130 Kështu që-- 80 00:02:44,130 --> 00:02:48,180 >> [Duke qeshur] 81 00:02:48,180 --> 00:02:48,742 >> Në rregull. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Ku jemi duke kërkuar? 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: Tani, ne jemi në kirurgjikale. 86 00:02:54,760 --> 00:02:57,840 Tani, mjekët. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- le të shkojë me të vërtetë. 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 NE RREGULL. 92 00:03:01,470 --> 00:03:03,700 Nëse keni nevojë të vërtetë. 93 00:03:03,700 --> 00:03:05,250 Tani, cila rrugë është Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Në këtë mënyrë. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. Malan: Cila mënyrë? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Prit. 97 00:03:08,240 --> 00:03:08,790 E drejtë M is--? 98 00:03:08,790 --> 00:03:09,110 Ne kemi filluar with-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. Malan: Po. 100 00:03:10,090 --> 00:03:10,650 Ata janë lënë. 101 00:03:10,650 --> 00:03:11,430 E drejta juaj. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Po. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. Malan: Pra, Mike s në këtu. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Çfarë? 105 00:03:13,990 --> 00:03:14,665 >> [Duke qeshur] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Shembulli i keq, djema. 108 00:03:18,330 --> 00:03:18,830 Më vjen keq. 109 00:03:18,830 --> 00:03:21,610 DAVID J. Malan: Kjo do të mësojmë ju të brishtë nga karrige tuaj. 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 I kam ju. 113 00:03:23,390 --> 00:03:24,670 I kam ju. 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 Kjo is-- OK, unë kam ty. 117 00:03:26,812 --> 00:03:27,520 Smith drejtë këtu? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. Malan: Smith, faleminderit. 119 00:03:28,894 --> 00:03:30,535 Kështu që unë do të mbaj shikuar deri Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, po. 121 00:03:30,790 --> 00:03:31,340 Jo jo jo. 122 00:03:31,340 --> 00:03:31,600 Oh, jo. 123 00:03:31,600 --> 00:03:31,940 Kjo është e imja. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. Malan: Oh, ju mori Smith. 125 00:03:32,580 --> 00:03:33,415 NE RREGULL. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Po, unë mori Smith drejtë këtu. 127 00:03:34,040 --> 00:03:34,700 Më vjen keq, djema. 128 00:03:34,700 --> 00:03:35,860 Mendova Michael-- ne ishin në kërkim për Michael. 129 00:03:35,860 --> 00:03:36,550 Më vjen keq. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. Malan: Është në rregull. 131 00:03:37,550 --> 00:03:39,950 Në rregull, tani ne jemi në Paccini dhe fëmijësh. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini dhe bijtë. 133 00:03:41,242 --> 00:03:43,158 DAVID J. Malan: Vetëm ju dhe unë jemi në në këtë. 134 00:03:43,158 --> 00:03:44,050 NE RREGULL. 135 00:03:44,050 --> 00:03:45,130 Na gjeni 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 Ne jemi në R për mbeturina. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Shumë keq. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Kjo do të marrë një kohë. 143 00:03:52,480 --> 00:03:54,340 >> [Duke qeshur] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. Malan: Këpucë. 146 00:03:56,720 --> 00:03:58,080 Ne jemi në këpucë. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Tani ne jemi gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. Malan: Bukur. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [Duke qeshur] 151 00:04:03,620 --> 00:04:05,440 Oh, kjo është e madhe. 152 00:04:05,440 --> 00:04:06,910 [Duke qeshur] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. Malan: Është në rregull. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, kjo është e mirë. 156 00:04:11,365 --> 00:04:14,425 Unë nuk mendoj se unë jam duke shkuar për të kanë miqtë PSAT pas kësaj. 157 00:04:14,425 --> 00:04:15,300 DAVID J. Malan: Mirë. 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 Um, 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 Pra, le të gris këtë në gjysmë. 163 00:04:21,600 --> 00:04:22,270 Eshte mire. 164 00:04:22,270 --> 00:04:25,606 Kjo përfundon keq gjithsesi, sepse Mike Smith nuk do të jetë në faqet e verdhë. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. Malan: Jo, kjo është në rregull. 167 00:04:27,140 --> 00:04:28,930 Por le të pretendojë si ai është në këtë faqe. 168 00:04:28,930 --> 00:04:33,260 Deri tani, ju keni whittled problemin poshtë në një faqe, dhe gjetëm Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Brohorisnin] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Ne rregull faleminderit. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 NE RREGULL. 174 00:04:41,200 --> 00:04:43,646 Kjo ishte e jashtëzakonshme. 175 00:04:43,646 --> 00:04:45,954 Por ai ishte ende më i shpejtë se kërko lineare, 176 00:04:45,954 --> 00:04:47,870 ku ne të fillojë në nivel fillim të librit, 177 00:04:47,870 --> 00:04:51,210 dhe ne shkojmë rrugën tonë nga e majta në të djathtë, përfundimisht duke kërkuar për Mike Smith. 178 00:04:51,210 --> 00:04:53,540 Dhe kështu, në qoftë se libri telefonit kishte ndoshta 1.000 faqe, 179 00:04:53,540 --> 00:04:56,300 ndoshta kjo do të kishte marrë ne 10 apo më shumë lot faqe. 180 00:04:56,300 --> 00:04:59,380 >> Por ju mund të keni leveraged prekur një supozim 181 00:04:59,380 --> 00:05:03,602 gjatë gjithë se, që do të thotë se libri telefoni paraprakisht ishte ajo? 182 00:05:03,602 --> 00:05:04,310 Audienca: Renditur. 183 00:05:04,310 --> 00:05:05,000 DAVID J. Malan: Është e renditura. 184 00:05:05,000 --> 00:05:05,160 E drejtë? 185 00:05:05,160 --> 00:05:07,909 Është renditura alfabetikisht, kështu se të gjithë ata emra dhe numra 186 00:05:07,909 --> 00:05:11,230 janë të renditura nga A-së të Z-së, dhe sipas rendit alfabetik në mes. 187 00:05:11,230 --> 00:05:13,100 Por sot, ne tani pyesim pyetja, mirë, 188 00:05:13,100 --> 00:05:16,170 sa e bëri Verizon ose telefon kompani të marrë atë në atë shtet? 189 00:05:16,170 --> 00:05:19,560 >> Sepse kjo është një gjë për të levave që supozim, dhe për këtë arsye, 190 00:05:19,560 --> 00:05:22,570 të zgjidhur një problem me një algorithm më efikase. 191 00:05:22,570 --> 00:05:24,900 Por ne kurrë nuk të vërtetë pyetur në javë zero, mirë, 192 00:05:24,900 --> 00:05:27,790 sa e bëri atë kosto Verizon apo dikush tjetër 193 00:05:27,790 --> 00:05:29,620 për të marrë atë libër telefonit në mënyrë renditura? 194 00:05:29,620 --> 00:05:29,780 >> E drejtë? 195 00:05:29,780 --> 00:05:31,529 Nuk ka rëndësi nëse shikuar deri Mike Smith 196 00:05:31,529 --> 00:05:35,190 është e super të shpejtë, në qoftë se ajo ju merr një vit për të zgjidhur faqet fillimisht. 197 00:05:35,190 --> 00:05:35,690 E drejtë? 198 00:05:35,690 --> 00:05:38,620 Si edhe ju mund vetëm të analizoj përmes një libër telefoni randomized, 199 00:05:38,620 --> 00:05:40,690 në qoftë se ajo do të jetë super shtrenjtë për të zgjidhur atë. 200 00:05:40,690 --> 00:05:42,350 Pra, nëse ne mund të kemi një tjetër vullnetar. 201 00:05:42,350 --> 00:05:46,350 Le të marrin një vështrim lart këtu në se si ne might-- ardhur në up-- si 202 00:05:46,350 --> 00:05:48,100 ne mund të shkoni në lidhje me klasifikim këto. 203 00:05:48,100 --> 00:05:51,990 >> Dhe në qoftë se Jordani mund të vërtetë të bashkohen me ne këtu në skenë. 204 00:05:51,990 --> 00:05:55,100 Eja për vetëm një moment. 205 00:05:55,100 --> 00:05:56,359 Si e ke emrin? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. Malan: Caroline, eja lart. 208 00:05:58,691 --> 00:06:02,070 Dhe ju do të bashkohen nga unë dhe Jordani këtu. 209 00:06:02,070 --> 00:06:03,800 Caroline, faleminderit. 210 00:06:03,800 --> 00:06:04,300 Në rregull. 211 00:06:04,300 --> 00:06:08,330 Pra, ajo që ne kemi këtu për Caroline është 26 libra blu 212 00:06:08,330 --> 00:06:10,747 që FAS përdor për të administruar Provimet caktuara përfundimtar. 213 00:06:10,747 --> 00:06:13,330 Këto janë duke u vështirë për të gjetur, por ajo që ne kemi bërë më parë 214 00:06:13,330 --> 00:06:15,800 është se ne kemi vënë emrin e dikujt në pjesën e përparme të secilit prej këtyre, 215 00:06:15,800 --> 00:06:18,133 por ne kemi mbajtur atë të thjeshtë nga pastaj vënë nga emrat e plotë. 216 00:06:18,133 --> 00:06:22,720 Pra, ne do të vënë personin me emrin L, D, J, B, të gjithë mënyrë A nëpër Z, 217 00:06:22,720 --> 00:06:24,090 por ata janë në mënyrë të rastit. 218 00:06:24,090 --> 00:06:26,890 Dhe kështu që në qoftë se ju do, duke folur tuaj rrugën përmes problem si ju 219 00:06:26,890 --> 00:06:31,620 bëni atë, ju mund të shkoni përpara dhe lloj këto për ne, nga A në Z. 220 00:06:31,620 --> 00:06:34,070 >> Audienca: OK, kështu që L është si, e mesme. 221 00:06:34,070 --> 00:06:35,050 C ka filluar. 222 00:06:35,050 --> 00:06:42,410 B. J para L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. Malan: Hold se mendoi për një sekondë. 224 00:06:45,140 --> 00:06:48,910 Sepse përndryshe, kjo është vetëm interesante për ju, mua, dhe Jordani. 225 00:06:48,910 --> 00:06:49,724 Atje shkojmë. 226 00:06:49,724 --> 00:06:50,640 Audienca: [padëgjueshme]. 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 Çfarë po bën? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M vjen pas 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, mirë. 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. Po. 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. kështu që ajo duket sikur ju jeni making-- mbajë. 238 00:07:10,689 --> 00:07:12,730 Ajo duket sikur ju jeni duke e bërë një grumbull i madh gjatë këtu, 239 00:07:12,730 --> 00:07:13,910 dhe lloj i një grumbull i madh mbi atje. 240 00:07:13,910 --> 00:07:16,230 Pra, gjysma e parë e alfabetit, gjysma e dytë e alfabetit. 241 00:07:16,230 --> 00:07:16,460 NE RREGULL. 242 00:07:16,460 --> 00:07:16,960 Të mirë. 243 00:07:16,960 --> 00:07:19,680 Lloji i ndarjes problemin në dy. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Po. 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. Pra, ju jeni lloj i zgjedhur ata njëri pas tjetrit, 248 00:07:25,070 --> 00:07:27,620 duke e vënë atë ose majtas ose djathtas, ose Z po ndodh në dysheme. 249 00:07:27,620 --> 00:07:28,012 NE RREGULL. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z po ndodh në dysheme. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. Malan: OK. 252 00:07:29,360 --> 00:07:30,920 Y po ndodh në dysheme. 253 00:07:30,920 --> 00:07:31,735 Tani ne mund të vënë 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 do largua. 256 00:07:33,700 --> 00:07:36,017 S po shkon drejtë. 257 00:07:36,017 --> 00:07:37,642 Të gjithë të drejtë, A po shkon gjatë gjithë rrugës majtë. 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: Tani, mirë. 260 00:07:39,873 --> 00:07:43,260 Ne kemi marrë A, B, C. W-së shkuar atje poshtë. 261 00:07:43,260 --> 00:07:45,566 Të gjithë të drejtë, 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. mirë. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: Në qendër, unë jam gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. Malan: OK. 266 00:07:50,000 --> 00:07:52,375 Deri tani, ne jemi duke shkuar për të llojit të bashkojë të këtyre shtyllave të ndryshme. 267 00:07:52,375 --> 00:08:00,730 Pra, një anë C, atëherë unë shoh D, dhe E, dhe F, dhe G, dhe H dhe I. Nisë. 268 00:08:00,730 --> 00:08:05,540 J, K. Dhe pastaj, kjo është grumbull me kokë poshtë, por kjo është në rregull. 269 00:08:05,540 --> 00:08:06,040 I sigurt. 270 00:08:06,040 --> 00:08:07,240 Ne mund të prerë disa qoshet. 271 00:08:07,240 --> 00:08:07,950 NE RREGULL. 272 00:08:07,950 --> 00:08:10,530 Dhe pastaj ne kemi nevojë W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Po. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. Malan: Excellent. 275 00:08:11,880 --> 00:08:14,122 Pra, një i madh ju falënderoj për Caroline për klasifikim këto. 276 00:08:14,122 --> 00:08:15,030 >> [Brohorisnin] 277 00:08:15,030 --> 00:08:17,287 >> Faleminderit. 278 00:08:17,287 --> 00:08:18,120 Faleminderit shumë. 279 00:08:18,120 --> 00:08:22,910 Pra, tani le të shqyrtojmë për një moment si Caroline përshkoi vendin duke bërë atë, 280 00:08:22,910 --> 00:08:26,040 dhe çfarë saktësisht ne ishin në gjendje to-- si ne 281 00:08:26,040 --> 00:08:28,409 ishin në gjendje për të zgjidhur atë Problemi kur ishim vetëm 282 00:08:28,409 --> 00:08:29,950 dhënë një bandë e tërë e inputeve të rastit. 283 00:08:29,950 --> 00:08:31,610 >> E pra, ajo duket sikur ka ishte pak e një sistemi atje? 284 00:08:31,610 --> 00:08:32,110 E drejtë. 285 00:08:32,110 --> 00:08:34,495 Pra, letrat e mëparshme në alfabetin, ajo 286 00:08:34,495 --> 00:08:37,120 ishte vënë në të majtë, dhe letra Më vonë në alfabetin, 287 00:08:37,120 --> 00:08:38,270 ajo ishte vënë në të djathtë. 288 00:08:38,270 --> 00:08:40,500 Dhe sa më shpejt që ajo gjeti disa letra proksimalen, ato të 289 00:08:40,500 --> 00:08:43,124 që shkojnë drejtë pranë njëri-tjetrit, ajo do të vënë ato në mënyrë. 290 00:08:43,124 --> 00:08:46,750 Dhe kështu që ne lloj i pasur këto të vogla grumbujt e inputeve të renditura ndodhin. 291 00:08:46,750 --> 00:08:50,540 >> Dhe kështu kjo është mjaft si ajo Shumica prej nesh do të bëjë njerëzit. 292 00:08:50,540 --> 00:08:53,530 Ne do lloj analizoj përmes saj, dhe ne do lloj të ketë një mekanizëm. 293 00:08:53,530 --> 00:08:56,930 Por ajo mund të jetë e vështirë për të shkruar ajo poshtë në një formulë në vetvete. 294 00:08:56,930 --> 00:08:59,010 Ajo ndjeu një pak më shumë se kaq organik. 295 00:08:59,010 --> 00:09:02,560 Pra, le të shohim nëse ne mund tani lidhur problemi me më pak inpute. 296 00:09:02,560 --> 00:09:05,170 >> Në vend të 26, le të të bëjë diçka shumë më pak 297 00:09:05,170 --> 00:09:09,890 me të them vetëm, shtatë, prapa këto dyer, kështu që të flasin. 298 00:09:09,890 --> 00:09:11,300 A ka vetëm shtatë numra? 299 00:09:11,300 --> 00:09:15,240 Dhe në qoftë se qëllimi tani në dorë është për të gjetur një vlerë, 300 00:09:15,240 --> 00:09:17,850 le të shohim se si në mënyrë efikase ne mund të shkojë për të bërë këtë. 301 00:09:17,850 --> 00:09:22,460 Dhe le të shohim nëse ne mund tani fillojnë të aplikojnë disa numra, 302 00:09:22,460 --> 00:09:26,310 ose disa formula me të cilin për të përshkruar efikasiteti i librit tonë të telefonit 303 00:09:26,310 --> 00:09:31,060 algorithm, tona algorithm libër provim, dhe më në përgjithësi, gjetjen e informacionit. 304 00:09:31,060 --> 00:09:34,770 >> Pra për këtë, më lejoni të shkoj përpara, dhe në ekran touch gjatë këtu, 305 00:09:34,770 --> 00:09:41,100 vënë një shfletues web që ka pikërisht këto shtatë dyer. 306 00:09:41,100 --> 00:09:46,670 Dhe në qoftë se ne mund të marrë një tjetër vullnetarë për të ardhur në këtu, 307 00:09:46,670 --> 00:09:48,480 Unë e kam vënë këto dyer të njëjta mbi këtu. 308 00:09:48,480 --> 00:09:49,170 Vullnetar të shpejtë. 309 00:09:49,170 --> 00:09:51,130 >> Ky popull one-- janë duke shkuar për një të shpejtë dhe më të shpejtë tani. 310 00:09:51,130 --> 00:09:51,600 Eja poshtë. 311 00:09:51,600 --> 00:09:52,308 Si e ke emrin? 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 Të gjithë të drejtë, Trevor, vijnë më poshtë. 315 00:09:55,770 --> 00:09:59,212 Pra, Trevor ka vullnetarë këtu për të bëjë një problem të ngjashëm, por ai që është 316 00:09:59,212 --> 00:10:02,170 ngushtë në fushëveprimin, dhe kjo po ndodh të na lejojë që të përpiqen për të zyrtarizuar tani 317 00:10:02,170 --> 00:10:03,970 procesi për klasifikim këto numra. 318 00:10:03,970 --> 00:10:05,500 >> Pra Trevor, nice to meet you. 319 00:10:05,500 --> 00:10:08,720 Kështu që këtu është një grup, në mënyrë që të flasin, një listë të shtatë dyerve. 320 00:10:08,720 --> 00:10:10,327 Shkoni përpara dhe të na gjeni numrin 50. 321 00:10:10,327 --> 00:10:12,410 Dhe pastaj pas faktit, na tregoni se si keni gjetur atë. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Duhet be-- të gjithë të drejtë. 324 00:10:20,040 --> 00:10:21,945 Po, kjo është ajo këtu? 325 00:10:21,945 --> 00:10:24,680 Uh-oh. 326 00:10:24,680 --> 00:10:25,560 NE RREGULL. 327 00:10:25,560 --> 00:10:26,680 Ju klikuar se një. 328 00:10:26,680 --> 00:10:28,690 Të mirë. 329 00:10:28,690 --> 00:10:29,780 >> Dhe të mirë. 330 00:10:29,780 --> 00:10:30,970 Tani ju klikuar se një. 331 00:10:30,970 --> 00:10:34,060 Dhe më lejoni t'ju jap mikrofonin, në mënyrë që ju të keni atë në një moment të vetëm. 332 00:10:34,060 --> 00:10:37,000 Shkoni përpara dhe klikoni në vendin fqinj që keni ndërmend. 333 00:10:37,000 --> 00:10:39,812 Po, mirë. 334 00:10:39,812 --> 00:10:41,020 Trevor: A mund të unclick një derë? 335 00:10:41,020 --> 00:10:42,620 DAVID J. Malan: Jo, ju nuk mund të unclick. 336 00:10:42,620 --> 00:10:43,119 Trevor: OK. 337 00:10:43,119 --> 00:10:43,974 Këtë. 338 00:10:43,974 --> 00:10:45,640 DAVID J. Malan: Ku doni të shkoni? 339 00:10:45,640 --> 00:10:46,410 Cila? 340 00:10:46,410 --> 00:10:47,230 >> Trevor: Se një. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. Malan: Jo. 342 00:10:48,042 --> 00:10:48,450 >> Trevor: OK. 343 00:10:48,450 --> 00:10:48,735 Këtë. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. Malan: Po. 345 00:10:49,020 --> 00:10:49,700 Kjo ishte e mirë. 346 00:10:49,700 --> 00:10:50,380 Në rregull. 347 00:10:50,380 --> 00:10:53,900 Pra, çfarë ishte algoritmi tuaj ose Procedura për të bërë këtë, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> Trevor: Unë vetëm shkoi nëpër Dyert deri sa kam gjetur një 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. Malan: OK. 350 00:10:56,940 --> 00:10:58,150 Algorithm shkëlqyer. 351 00:10:58,150 --> 00:10:59,540 Pra, kjo është në rregull. 352 00:10:59,540 --> 00:11:03,120 Sepse në fakt, në qoftë se unë të zbulojë se çfarë është pas këtyre dy dyer të tjera, çfarë 353 00:11:03,120 --> 00:11:06,954 ne do të gjeni këtu është se ne kemi vetëm të dhëna të rastit. 354 00:11:06,954 --> 00:11:08,870 Kështu që ishte në të vërtetë si i mirë sa ju mund të merrni. 355 00:11:08,870 --> 00:11:12,509 Dhe në fakt, ju mori më të mirë se shteruese në kërkim të gjithë array, 356 00:11:12,509 --> 00:11:15,300 sepse kjo do të kishte qenë me të vërtetë pafat në qoftë se ju kishte goditur numrin 357 00:11:15,300 --> 00:11:16,604 50 tek dera e fundit. 358 00:11:16,604 --> 00:11:18,520 Por, çfarë nëse ne vend ju dha një supozim. 359 00:11:18,520 --> 00:11:20,630 Mendoj unë lloj të gjithë Këto dyer rreth, 360 00:11:20,630 --> 00:11:23,500 kështu që ju keni Numrat e renditura në këtë kohë, 361 00:11:23,500 --> 00:11:29,730 por këtë herë është e vërtetë një different-- këtë herë, 362 00:11:29,730 --> 00:11:32,640 është e renditura në fakt për ju. 363 00:11:32,640 --> 00:11:35,380 Dhe tani qëllimi në dorë është për të goditur numrin 50. 364 00:11:35,380 --> 00:11:36,090 >> Trevor: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. Malan: Çfarë është do të jetë algorithm juaj? 366 00:11:37,670 --> 00:11:39,628 >> Trevor: E pra, në qoftë se është të renditura, është ose do 367 00:11:39,628 --> 00:11:42,710 për be-- nëse e madhe për të më e madhe, zbritëse, ajo do të jetë i pari, 368 00:11:42,710 --> 00:11:44,751 ose në qoftë se është e kundërta, ajo do të jetë e fundit. 369 00:11:44,751 --> 00:11:48,897 Kështu që unë do të caktojë vetëm këtë derë, dhe pastaj vetëm trokitje e lehtë derën e fundit. 370 00:11:48,897 --> 00:11:49,980 DAVID J. Malan: Excellent. 371 00:11:49,980 --> 00:11:50,270 Në rregull. 372 00:11:50,270 --> 00:11:51,150 Pra, ne kemi gjetur numrin 50. 373 00:11:51,150 --> 00:11:52,970 Pra, sa më shpejt që ju e dinte ata ishin të renditura, ne 374 00:11:52,970 --> 00:11:55,040 ishin në gjendje të levave këtë supozim. 375 00:11:55,040 --> 00:11:57,040 Pra, ata janë shumë si shembulli librin e telefonit. 376 00:11:57,040 --> 00:11:59,540 Sa më shpejt që ju keni, madje edhe me një problem të vogël si kjo, 377 00:11:59,540 --> 00:12:02,380 inputet e tu para-renditura, ne mund të në fakt të gjetur vlerën ndoshta 378 00:12:02,380 --> 00:12:03,130 në mënyrë më efikase. 379 00:12:03,130 --> 00:12:05,800 >> Dhe unë nuk ju them në qoftë se ajo ishte renditura vogla në të mëdha, ose të mëdha në të vogla, 380 00:12:05,800 --> 00:12:08,080 dhe kështu që ishte shumë e arsyeshme për të filluar në një nga skajet ose tjetër 381 00:12:08,080 --> 00:12:09,750 që në fakt gjetur këtë vlerë të synuar. 382 00:12:09,750 --> 00:12:11,400 Pra, falënderoj për Trevor si. 383 00:12:11,400 --> 00:12:13,260 Dhe unë do të propose-- bërë mirë. 384 00:12:13,260 --> 00:12:16,960 Ne kemi një klip të vogël, në të vërtetë, se është ndër momentet favorite tona në CS50, 385 00:12:16,960 --> 00:12:19,700 ku ndonjëherë këto popull mos fare shkojnë sipas planit. 386 00:12:19,700 --> 00:12:22,050 Dhe me të vërtetë tani, unë u tërhoq deri interface gabuar 387 00:12:22,050 --> 00:12:23,508 me të cilin do të përdorni ekranin me prekje. 388 00:12:23,508 --> 00:12:24,660 Kështu që ishte faji im aty. 389 00:12:24,660 --> 00:12:26,600 >> Pra, kjo do të bëjë për clip vitin e ardhshëm si 390 00:12:26,600 --> 00:12:28,570 pse unë kam qenë duke klikuar në ekranin tim. 391 00:12:28,570 --> 00:12:31,390 Por le të marrin një vështrim të shpejtë se çfarë ka ndodhur vitin e kaluar 392 00:12:31,390 --> 00:12:34,770 me Jay, i cili erdhi, shumë si Trevor këtu, vullnetarë, 393 00:12:34,770 --> 00:12:39,380 dhe në këtë klip të shkurtër, ju do të shihni si kjo e njëjta demo nuk bëri mjaft 394 00:12:39,380 --> 00:12:41,074 zbulojnë të njëjtat mësimet e nxjerra. 395 00:12:41,074 --> 00:12:41,740 [VIDEO rishikim] 396 00:12:41,740 --> 00:12:45,360 -Të Gjitha unë dua që ju të bëni tani është për të gjetur për mua, dhe për ne, 397 00:12:45,360 --> 00:12:51,674 me të vërtetë, numri 50 një hap në një kohë. 398 00:12:51,674 --> 00:12:52,450 >> -Numri 50? 399 00:12:52,450 --> 00:12:53,190 >> -Numri 50. 400 00:12:53,190 --> 00:12:55,356 Dhe ju mund të zbulojë se çfarë është pas secili prej këtyre dyerve 401 00:12:55,356 --> 00:12:58,540 thjesht duke prekur atë me një gisht. 402 00:12:58,540 --> 00:13:00,910 Mallkuar atë. 403 00:13:00,910 --> 00:13:02,870 >> [Duke qeshur] 404 00:13:02,870 --> 00:13:03,806 >> [END rishikim] 405 00:13:03,806 --> 00:13:05,430 DAVID J. Malan: Pra, që shkoi shumë mirë. 406 00:13:05,430 --> 00:13:06,796 Ata ishin dyert Unsorted. 407 00:13:06,796 --> 00:13:08,670 Dhe Jay, sigurisht, gjeti atë të gjithë shumë shpejt. 408 00:13:08,670 --> 00:13:12,910 Trevor bëri një punë shumë të mirë në kushtet e një moment i aftë për shkollë, 409 00:13:12,910 --> 00:13:15,850 mënyrë që të flasin, këtë vit në duke marrë më të gjatë për të gjetur atë. 410 00:13:15,850 --> 00:13:17,950 Sigurisht, atëherë ne i dhamë Jay një shans të dytë, 411 00:13:17,950 --> 00:13:20,320 ku ne renditura dyert, ashtu siç bëmë për Trevor, 412 00:13:20,320 --> 00:13:22,300 dhe Trevor e bëri super të mirë këtë herë. 413 00:13:22,300 --> 00:13:26,124 Por Jay bëri atë gjysmë sa më shpejt. 414 00:13:26,124 --> 00:13:26,790 [VIDEO rishikim] 415 00:13:26,790 --> 00:13:29,650 -The Tani qëllimi është edhe na gjeni numrin 50, 416 00:13:29,650 --> 00:13:33,030 por të bëjë atë algoritmikisht, dhe na tregoni se si ju do të jeni në lidhje me të. 417 00:13:33,030 --> 00:13:33,660 >> -NE RREGULL. 418 00:13:33,660 --> 00:13:35,604 >> -Dhe Në qoftë se ju të gjeni atë, ju mbani filmin. 419 00:13:35,604 --> 00:13:37,228 Nëse ju nuk e gjeni atë, ju jepni atë përsëri. 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 >> - [E padëgjueshme] OK. 423 00:13:40,800 --> 00:13:46,236 Kështu që unë jam duke shkuar për të kontrolluar përfundon së pari për të përcaktuar nëse there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Duartrokitje] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [END rishikim] 427 00:13:55,729 --> 00:13:56,520 DAVID J. Malan: OK. 428 00:13:56,520 --> 00:13:59,760 Pra, sorting dyert në mënyrë të qartë çon në efikasitet më të madh. 429 00:13:59,760 --> 00:14:01,680 Dhe kështu, dy herë më shpejt është ajo që unë do të thotë atje. 430 00:14:01,680 --> 00:14:03,270 Dhe kështu Jay mori me fat dy herë. 431 00:14:03,270 --> 00:14:06,685 Dhe ai gjithashtu mori me fat në atë të fundit vit, unë urdhëroi disa disqe Blu-ray 432 00:14:06,685 --> 00:14:07,560 që në fakt japin. 433 00:14:07,560 --> 00:14:09,768 Më vjen keq të këtij viti, ne nuk kanë të njëjtë, Trevor. 434 00:14:09,768 --> 00:14:11,540 Por më mirë akoma ishte disa vjet mbrapa. 435 00:14:11,540 --> 00:14:14,820 Dhe disa prej jush mund të dini këtë shokët, Sean, i cili kur ai ishte në CS50, 436 00:14:14,820 --> 00:14:17,780 u sfidua me saktë njëjtin problem, megjithëse në SD, 437 00:14:17,780 --> 00:14:19,360 si ju së shpejti do të shihni, mbrapa në ditë. 438 00:14:19,360 --> 00:14:22,622 Dhe ju do të gjeni se jo vetëm që ai të marrë pak më shumë se Jay, 439 00:14:22,622 --> 00:14:25,580 pak më shumë se Trevor, ajo ishte në fakt kjo mundësi e mrekullueshme 440 00:14:25,580 --> 00:14:29,820 për t'u angazhuar pothuajse të gjithë në Turma a la Çmimi është e drejta, duke inkurajuar 441 00:14:29,820 --> 00:14:31,889 atë për të gjetur numrin e ne po e kërkojmë. 442 00:14:31,889 --> 00:14:32,930 Le. të marrë një sy të shpejtë. 443 00:14:32,930 --> 00:14:33,320 >> [VIDEO rishikim] 444 00:14:33,320 --> 00:14:33,820 >> -NE RREGULL. 445 00:14:33,820 --> 00:14:36,680 Kështu që detyra juaj këtu, Sean, është në vijim. 446 00:14:36,680 --> 00:14:40,860 Unë kam fshehur prapa këto Dyert numri shtatë. 447 00:14:40,860 --> 00:14:45,120 Por tucked larg në disa prej këtyre dyerve si dhe një numër të tjera negative. 448 00:14:45,120 --> 00:14:47,500 Dhe qëllimi juaj është për të menduar i këtij rreshtin e lartë të numrave 449 00:14:47,500 --> 00:14:50,390 si vetëm një grup, apo vetëm Sekuenca e copa letre 450 00:14:50,390 --> 00:14:51,510 me numra pas tyre. 451 00:14:51,510 --> 00:14:55,540 Dhe qëllimi juaj është vetëm duke përdorur të lartë array këtu, të gjetur me numrin shtatë. 452 00:14:55,540 --> 00:14:58,570 Dhe ne jemi duke shkuar për të kritikuar më pas si ju shkoni për të bërë atë. 453 00:14:58,570 --> 00:14:59,070 -Në rregull. 454 00:14:59,070 --> 00:15:00,850 Na -Find numrin shtatë, ju lutem. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Jo. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Pesë, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Duke qeshur] 461 00:15:24,770 --> 00:15:25,910 >> Kjo nuk është një pyetje mashtrim. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Një. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Duke qeshur] 466 00:15:34,695 --> 00:15:37,861 Në këtë pikë, rezultati juaj nuk është shumë e e mirë, kështu që ju mund edhe të do të mbajë. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Tre. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Duke qeshur] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Vazhdo. 473 00:15:47,774 --> 00:15:50,690 Sinqerisht, unë nuk mund të ndihmojnë por pyes veten çfarë jeni duke menduar për, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Duke qeshur] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Vetëm në radhën e lartë, kështu që ju keni marrë tre majtë. 477 00:15:55,020 --> 00:15:56,200 Pra, gjeni mua shtatë. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Duke qeshur] 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 Shtatë. 484 00:16:26,946 --> 00:16:28,780 >> [Duartrokitje] 485 00:16:28,780 --> 00:16:29,426 >> Në rregull. 486 00:16:29,426 --> 00:16:30,360 >> [END rishikim] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. Malan: Pra, ne mund të shikojnë këto gjatë gjithë ditës. 488 00:16:31,840 --> 00:16:34,090 Dhe sigurisht, disa prej popull këtij viti ndoshta 489 00:16:34,090 --> 00:16:36,330 tani do të përfundojë deri në të ardhshëm Video viti si. 490 00:16:36,330 --> 00:16:39,040 Pra, tani le të vërtetë të përqëndrohet në algoritme 491 00:16:39,040 --> 00:16:42,140 këtu, dhe të shohim nëse ne nuk mund të tani të fillojë të formalizuar 492 00:16:42,140 --> 00:16:46,650 se si ne mund të shkoni në lidhje me marrjen e të dhënave tonë në këtë gjendje që është e renditura, 493 00:16:46,650 --> 00:16:50,054 në mënyrë që në fund të fundit, ne mund të vërtetë kërko atë në mënyrë më efikase. 494 00:16:50,054 --> 00:16:52,470 Dhe, edhe pse ne jemi duke shkuar të përdorin të dhënat grupe mjaft të vogla, 495 00:16:52,470 --> 00:16:54,511 si tetë numrat ne kemi këtu në bord, 496 00:16:54,511 --> 00:16:58,230 në fund të fundit këto ide të njëjta mund të aplikohet në 1.000 inputeve, një milion inputeve, 497 00:16:58,230 --> 00:17:02,100 4 miliardë inputeve, sepse algoritme do të jetë në thelb e njëjtë. 498 00:17:02,100 --> 00:17:05,359 >> Dhe kështu kjo është e fundit ynë mundësi për vullnetarët sot, 499 00:17:05,359 --> 00:17:09,790 por ndoshta më e përfshirë, për të cilat ne kemi nevojë për tetë vullnetarë 500 00:17:09,790 --> 00:17:12,960 për të dalë dhe të na ecin nëpër Procesi i ndarjes se çfarë do të së shpejti 501 00:17:12,960 --> 00:17:15,212 të jetë në këto muzikën qëndron këtu. 502 00:17:15,212 --> 00:17:16,170 Më lejoni të filloj përsëri këtu. 503 00:17:16,170 --> 00:17:19,692 >> Pra, një në të gjelbër turquoise-- është ajo? 504 00:17:19,692 --> 00:17:21,130 A jeni kryerjen? 505 00:17:21,130 --> 00:17:21,630 Dy. 506 00:17:21,630 --> 00:17:23,069 Eja poshtë. 507 00:17:23,069 --> 00:17:23,569 NE RREGULL. 508 00:17:23,569 --> 00:17:24,420 Tre. 509 00:17:24,420 --> 00:17:25,400 Katër. 510 00:17:25,400 --> 00:17:27,247 Le me-- OK, pesë. 511 00:17:27,247 --> 00:17:28,830 Ju jeni duke u nominuar nga miku juaj. 512 00:17:28,830 --> 00:17:31,340 Gjashtë, shtatë, tetë. 513 00:17:31,340 --> 00:17:32,130 Eja up. 514 00:17:32,130 --> 00:17:32,630 Në rregull. 515 00:17:32,630 --> 00:17:33,190 Shume faleminderit. 516 00:17:33,190 --> 00:17:33,689 Eja up. 517 00:17:33,689 --> 00:17:34,790 Eja up. 518 00:17:34,790 --> 00:17:35,330 >> Në rregull. 519 00:17:35,330 --> 00:17:38,890 Pra, ajo që ne kemi here-- dhe kjo është ndër ato më të vështirë, 520 00:17:38,890 --> 00:17:42,390 pasi kjo do të kërkojë që të humorit mua për vetëm një grimë të vogël të kohës. 521 00:17:42,390 --> 00:17:43,442 Ju do të jetë numër një. 522 00:17:43,442 --> 00:17:44,150 Si e ke emrin? 523 00:17:44,150 --> 00:17:44,610 >> Anan: Anan. 524 00:17:44,610 --> 00:17:45,526 >> DAVID J. Malan: Anan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 Si e ke emrin? 527 00:17:46,800 --> 00:17:47,140 >> Joseph: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. Malan: Joseph, ju jeni numri dy. 529 00:17:49,190 --> 00:17:52,260 >> Serena: Serena, numri tre. 530 00:17:52,260 --> 00:17:53,722 Stefan, numri katër. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. Malan: Cynthia, numri pesë. 533 00:17:57,548 --> 00:17:58,452 [Padëgjueshme] 534 00:17:58,452 --> 00:17:59,618 DAVID J. Malan: [padëgjueshme]. 535 00:17:59,618 --> 00:18:00,391 David, numri gjashtë. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. Malan: Numri i Matt shtatë. 538 00:18:02,160 --> 00:18:02,850 Dhe? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. Malan: Waverly, numri tetë. 541 00:18:04,470 --> 00:18:04,970 Në rregull. 542 00:18:04,970 --> 00:18:06,510 Nëse ju could-- uh. 543 00:18:06,510 --> 00:18:08,820 Në qoftë se ju të gjithë, siç tuaj Sfida e parë, atje 544 00:18:08,820 --> 00:18:10,820 janë tetë qëndron muzikë këtu përballet me audiencën. 545 00:18:10,820 --> 00:18:14,200 Në qoftë se ju mund të vënë numrat tuaj mbi këto muzikë qëndron në një mënyrë të tillë 546 00:18:14,200 --> 00:18:16,560 që ata të vijë deri me Numrat e njëjta në bord. 547 00:18:16,560 --> 00:18:19,560 Pra, bëni të duken si se nga vënë numrat tuaj në këto muzikën 548 00:18:19,560 --> 00:18:21,960 qëndron këtu. 549 00:18:21,960 --> 00:18:25,980 Të shkëlqyer deri tani. 550 00:18:25,980 --> 00:18:26,600 >> Shkëlqyer. 551 00:18:26,600 --> 00:18:26,890 NE RREGULL. 552 00:18:26,890 --> 00:18:29,556 Deri tani, ne jemi duke shkuar për të pyesni pyetje në disa mënyra të ndryshme. 553 00:18:29,556 --> 00:18:31,610 Si mund të shkoni në lidhje me sorting këto folks këtu? 554 00:18:31,610 --> 00:18:34,500 Sepse kemi pasur një qasje pak më parë, ku ne ishim 555 00:18:34,500 --> 00:18:36,360 lloj i bërë dy kova të ndryshme. 556 00:18:36,360 --> 00:18:38,842 Dhe pastaj ne kemi qenë në përgjithësi piecing gjëra së bashku. 557 00:18:38,842 --> 00:18:41,050 Sapo pamë dy numrat që i përkiste së bashku, 558 00:18:41,050 --> 00:18:41,975 ne kemi vënë ata së bashku. 559 00:18:41,975 --> 00:18:43,350 Dy letra që i përkasin së bashku. 560 00:18:43,350 --> 00:18:45,058 >> Por le të shohim nëse ne nuk mund të formalizojë këtë, 561 00:18:45,058 --> 00:18:48,044 në mënyrë që në fund të fundit ne kemi disa pseudo-kod ju do, 562 00:18:48,044 --> 00:18:49,710 me të cilat ju mund të zgjidhin këto probleme. 563 00:18:49,710 --> 00:18:51,870 Deri tani, unë jam duke kërkuar jashtë në këto numra këtu. 564 00:18:51,870 --> 00:18:55,030 Dhe unë shoh një bandë e tërë e gabimeve. 565 00:18:55,030 --> 00:18:57,750 Në fund të fundit, unë dua një të tillë në majtë dhe të tetë në të djathtë. 566 00:18:57,750 --> 00:19:00,650 >> Dhe kështu që unë jam duke kërkuar në këta të dy, katër dhe dy. 567 00:19:00,650 --> 00:19:02,930 Dhe çfarë është problemi, natyrisht? 568 00:19:02,930 --> 00:19:04,261 Po. 569 00:19:04,261 --> 00:19:04,760 Kështu që. 570 00:19:04,760 --> 00:19:07,160 Dy padyshim vjen para katër, kështu që ju e dini se çfarë? 571 00:19:07,160 --> 00:19:10,210 Më lejoni së pari të marrë një qasje babëzitur, në qoftë se ju do të, problemi shumë si 572 00:19:10,210 --> 00:19:13,790 vendosur one-- nëse ju kujtohet nga Standard Edition i problemit Set One, 573 00:19:13,790 --> 00:19:16,820 ku unë vetëm në vend të zgjidhur problemin kjo është e drejtë këtu para meje 574 00:19:16,820 --> 00:19:17,690 dhe të shohim se ku ajo të çon mua. 575 00:19:17,690 --> 00:19:17,870 >> NE RREGULL. 576 00:19:17,870 --> 00:19:20,161 Pra, dy dhe katër, më lejoni të shkoj përpara dhe vetëm shkëmbim të dy. 577 00:19:20,161 --> 00:19:22,400 Në qoftë se ju mund të lëvizin fizikisht veten dhe letër tuaj, 578 00:19:22,400 --> 00:19:25,040 Unë duket se kanë marrë lista në një gjendje më të mirë. 579 00:19:25,040 --> 00:19:26,330 >> Tani, ata janë të mirë. 580 00:19:26,330 --> 00:19:28,480 Unë jam duke shkuar për të shkuar përpara, katër dhe gjashtë, duket e mirë. 581 00:19:28,480 --> 00:19:29,110 Nuk është problem. 582 00:19:29,110 --> 00:19:30,440 Gjashtë dhe tetë, OK. 583 00:19:30,440 --> 00:19:31,860 Tetë dhe një, një tjetër problem. 584 00:19:31,860 --> 00:19:34,750 Sepse ajo që është e vërtetë në lidhje me tetë dhe një? 585 00:19:34,750 --> 00:19:36,990 Vjen para se të tetë, dhe kështu çfarë duhet të bëjmë? 586 00:19:36,990 --> 00:19:38,090 Le të bie në ujdi këto dy. 587 00:19:38,090 --> 00:19:39,316 Një dhe tetë. 588 00:19:39,316 --> 00:19:40,690 Dhe tani, unë jam duke shkuar për të do të mbajë. 589 00:19:40,690 --> 00:19:42,030 Unë jam duke shkuar për të mbajtur në kërkim përpara. 590 00:19:42,030 --> 00:19:42,840 Dhe le të shohim se çfarë ndodh. 591 00:19:42,840 --> 00:19:44,680 Tetë dhe tre, të Sigurisht, nga e rendit. 592 00:19:44,680 --> 00:19:45,815 Le të swap. 593 00:19:45,815 --> 00:19:46,940 Tetë dhe shtatë, natyrisht. 594 00:19:46,940 --> 00:19:47,481 Jashte perdorimit. 595 00:19:47,481 --> 00:19:48,280 Le të swap. 596 00:19:48,280 --> 00:19:49,940 Tetë dhe pesë, natyrisht, le shkëmbim. 597 00:19:49,940 --> 00:19:50,560 Në rregull. 598 00:19:50,560 --> 00:19:51,880 Lista është e renditura. 599 00:19:51,880 --> 00:19:53,060 po? 600 00:19:53,060 --> 00:19:54,280 >> OK, natyrisht jo. 601 00:19:54,280 --> 00:19:55,860 Por kjo është një pak më të mirë, e drejtë? 602 00:19:55,860 --> 00:19:57,270 Sepse njoftim çfarë ka ndodhur. 603 00:19:57,270 --> 00:20:01,749 Çdo herë kemi kryer një shkëmbim, një më të vogël Numri lloj i percolated në këtë mënyrë, 604 00:20:01,749 --> 00:20:03,790 dhe një numër i madh percolated këtë mënyrë, ose ne do të 605 00:20:03,790 --> 00:20:06,880 fillojnë duke thënë bubbled të majtas ose bubbled në të djathtë. 606 00:20:06,880 --> 00:20:10,080 >> Tani, kjo nuk është e mjaftueshme, sepse në të mirë të një numër i fuqisë 607 00:20:10,080 --> 00:20:11,990 kanë lëvizur një vend përpara, ose në më të keq, 608 00:20:11,990 --> 00:20:13,880 një numër mund të ketë lëvizur një vend edhe më tej. 609 00:20:13,880 --> 00:20:16,369 Pra, ju e dini se çfarë, ky lloj i ka punuar mjaft mirë deri tani. 610 00:20:16,369 --> 00:20:17,410 Më lejoni vetëm të provoni përsëri. 611 00:20:17,410 --> 00:20:18,880 Dy dhe katër, ata janë në rregull. 612 00:20:18,880 --> 00:20:20,180 Katër dhe gjashtë, ata janë në rregull. 613 00:20:20,180 --> 00:20:21,790 Gjashtë dhe një, nga e rendit. 614 00:20:21,790 --> 00:20:23,007 Pra, le të bie në ujdi të dy. 615 00:20:23,007 --> 00:20:25,840 Dhe tani, vini re problemi-së duke filluar për të marrë një pak më të mirë përsëri. 616 00:20:25,840 --> 00:20:27,006 Gjashtë dhe tre, nga e rendit. 617 00:20:27,006 --> 00:20:28,100 Le të bie në ujdi të dy. 618 00:20:28,100 --> 00:20:29,730 Gjashtë dhe shtatë, ju jeni të mirë. 619 00:20:29,730 --> 00:20:32,230 Shtatë dhe pesë, natyrisht, jashtë funksionit. 620 00:20:32,230 --> 00:20:33,920 Shtatë dhe tetë, në rregull. 621 00:20:33,920 --> 00:20:36,470 Dhe tani, unë mund të kenë nevojë për të bëni këtë disa herë më shumë. 622 00:20:36,470 --> 00:20:39,830 Dhe në fakt, mendoj për veten tuaj ndoshta sa herë maksimalisht 623 00:20:39,830 --> 00:20:41,330 mund të më duhet të ecin mbrapa dhe me radhë? 624 00:20:41,330 --> 00:20:42,390 >> Ne do të kthehen në atë. 625 00:20:42,390 --> 00:20:43,700 Pra, dy dhe katër janë ende në rregull. 626 00:20:43,700 --> 00:20:44,940 Katër dhe një, Jo. 627 00:20:44,940 --> 00:20:45,747 Pra, le të swap. 628 00:20:45,747 --> 00:20:47,830 Dhe përsëri, vini re vizualisht një është lloj i bubbling 629 00:20:47,830 --> 00:20:49,163 në të majtë, ku ajo duhet të jetë. 630 00:20:49,163 --> 00:20:50,010 Katër dhe tre shkëmbim. 631 00:20:50,010 --> 00:20:51,330 Katër dhe gjashtë. 632 00:20:51,330 --> 00:20:53,100 Gjashtë dhe pesë shkëmbim. 633 00:20:53,100 --> 00:20:53,959 Gjashtë dhe shtatë. 634 00:20:53,959 --> 00:20:55,000 Shtatë dhe tetë janë të mira. 635 00:20:55,000 --> 00:20:55,500 >> Të mirë. 636 00:20:55,500 --> 00:20:58,460 Ne jemi duke marrë edhe më të mirë. 637 00:20:58,460 --> 00:20:59,130 Pra, le të shohim. 638 00:20:59,130 --> 00:21:00,940 Tani, ne kemi dy dhe një. 639 00:21:00,940 --> 00:21:02,520 Sigurisht, të bie në ujdi. 640 00:21:02,520 --> 00:21:07,520 Dy dhe tre, tre dhe katër, katër dhe pesë, gjashtë dhe shtatë, shtatë dhe tetë. 641 00:21:07,520 --> 00:21:08,020 Të mirë. 642 00:21:08,020 --> 00:21:08,730 Dhe ju e dini se çfarë? 643 00:21:08,730 --> 00:21:11,190 Sepse unë bëra një ndryshim atje, më lejoni të bëj një kontroll mendje e shëndoshë. 644 00:21:11,190 --> 00:21:13,023 Më lejoni të shkoni të gjithë rrugën përsëri në fillim. 645 00:21:13,023 --> 00:21:13,680 NE RREGULL. 646 00:21:13,680 --> 00:21:14,750 Një, two-- Yup, e shihni? 647 00:21:14,750 --> 00:21:15,870 Diçka ishte e gabuar. 648 00:21:15,870 --> 00:21:18,420 Tre, katër, pesë, gjashtë, shtatë, tetë. 649 00:21:18,420 --> 00:21:21,920 Dhe në këtë kalim të fundit, janë ju rehat me tani tim 650 00:21:21,920 --> 00:21:23,830 duke pretenduar se ai është renditur? 651 00:21:23,830 --> 00:21:24,330 NE RREGULL. 652 00:21:24,330 --> 00:21:25,880 Vizualisht, kjo është absolutisht e vërtetë. 653 00:21:25,880 --> 00:21:28,410 Por funksionalisht, çfarë ka gjithashtu ndodhë vetëm 654 00:21:28,410 --> 00:21:31,870 në atë të kalojë e fundit që ju lejon për të konfirmuar se kjo listë është me të vërtetë 655 00:21:31,870 --> 00:21:32,660 të renditura? 656 00:21:32,660 --> 00:21:34,477 >> Çfarë ka të bëj apo jo të bëjë këtë abone të fundit? 657 00:21:34,477 --> 00:21:35,810 Audienca: Nuk ka pasur ndryshime. 658 00:21:35,810 --> 00:21:36,120 DAVID J. Malan: Na vjen keq? 659 00:21:36,120 --> 00:21:37,070 Audienca: Nuk ka pasur ndryshime. 660 00:21:37,070 --> 00:21:38,653 DAVID J. Malan: Nuk ka pasur ndryshime. 661 00:21:38,653 --> 00:21:41,947 Pra, kjo do të jetë budalla për mua për të të bëjë të njëjtin algoritmi përsëri 662 00:21:41,947 --> 00:21:43,780 në qoftë se unë nuk e ka bërë asnjë ndryshon për herë të parë. 663 00:21:43,780 --> 00:21:45,160 Dhe shteti nuk ka ndryshuar. 664 00:21:45,160 --> 00:21:47,576 Sigurisht, unë nuk jam duke shkuar për të bërë Çdo ndryshim për herë të dytë. 665 00:21:47,576 --> 00:21:49,820 Dhe kështu, është e sigurt tani për të thënë, lista është renditur. 666 00:21:49,820 --> 00:21:52,069 >> Dhe në të vërtetë, kjo është tani diçka që ne do të në përgjithësi 667 00:21:52,069 --> 00:21:56,900 thirrje lloj flluskë, ku pairwise, ju korrigjuar gabimet përsëri, 668 00:21:56,900 --> 00:22:00,210 dhe përsëri, dhe përsëri, dhe ju do të mbajë mbrapa dhe me radhë, 669 00:22:00,210 --> 00:22:03,370 dhe mbrapa dhe me radhë, derisa ju të bëjë asnjë këmbime të tilla, në të cilën pikë 670 00:22:03,370 --> 00:22:07,089 ju mund të jeni i sigurt, po, përfundoi fiksimin e të gjitha gabimet. 671 00:22:07,089 --> 00:22:08,630 Le të rivendosur dhe të provoj diçka tjetër. 672 00:22:08,630 --> 00:22:11,590 Në qoftë se ju djema mund të kthehem në rendi keni qenë një moment më parë, 673 00:22:11,590 --> 00:22:13,780 që dukej si kjo. 674 00:22:13,780 --> 00:22:17,640 Tani, le të marrin një qasje të një pak më shumë si librin e provimit, 675 00:22:17,640 --> 00:22:21,122 ku ne kemi qenë vazhdimisht zgjedhjen letrën e alfabetit 676 00:22:21,122 --> 00:22:22,830 që ne lloj i dashur për t'u marrë me të ardhshëm. 677 00:22:22,830 --> 00:22:26,420 Ndoshta kjo ishte një letër e lartë, si A, ose një letër Z. ulët 678 00:22:26,420 --> 00:22:28,170 >> Kështu që të gjithë është kthyer në këtë mënyrë. 679 00:22:28,170 --> 00:22:29,800 Dhe tani më lejoni të bëj këtë. 680 00:22:29,800 --> 00:22:34,880 Le të shohim se Unë e di unë kam tetë numra këtu. 681 00:22:34,880 --> 00:22:37,410 Unë jam duke shkuar për të shkuar përpara dhe vetëm qëllimisht zgjidhni 682 00:22:37,410 --> 00:22:38,520 elementet më të vogla. 683 00:22:38,520 --> 00:22:38,760 E drejtë? 684 00:22:38,760 --> 00:22:39,801 Kjo duket intuitive shumë. 685 00:22:39,801 --> 00:22:42,560 Pse nuk mund të gjej më të vogël element, e vënë atë ku i takon, 686 00:22:42,560 --> 00:22:45,280 pastaj të marrë elementin tjetër më të vogël, vendos ajo aty ku i takon, dhe vetëm përsërisin. 687 00:22:45,280 --> 00:22:46,820 >> Sepse intuitive, që duhet të punojnë shumë. 688 00:22:46,820 --> 00:22:48,441 Pra katër, që është një numër shumë i vogël. 689 00:22:48,441 --> 00:22:49,940 Unë jam duke shkuar për të kujtuar se ku është kjo. 690 00:22:49,940 --> 00:22:50,523 Prit një minutë. 691 00:22:50,523 --> 00:22:51,577 Dy është më i vogël. 692 00:22:51,577 --> 00:22:53,910 Më lejoni tani të mbani mend se ku dy është, dhe të harrojmë për katër. 693 00:22:53,910 --> 00:22:55,050 Ne do të merremi me këtë më vonë. 694 00:22:55,050 --> 00:22:56,460 Gjashtë, unë nuk jam i interesuar. 695 00:22:56,460 --> 00:22:57,810 Tetë, unë nuk jam i interesuar në. 696 00:22:57,810 --> 00:22:59,780 Njëra është numri im i ri i vogël. 697 00:22:59,780 --> 00:23:01,470 Kështu që unë jam duke shkuar për të kujtuar ku është. 698 00:23:01,470 --> 00:23:02,534 Tre, nuk janë të interesuar. 699 00:23:02,534 --> 00:23:03,450 Shtatë, nuk janë të interesuar. 700 00:23:03,450 --> 00:23:04,530 Pesë, nuk janë të interesuar. 701 00:23:04,530 --> 00:23:07,390 >> Pra, pa u pakësuar faza të këtij viti, 702 00:23:07,390 --> 00:23:09,890 Unë jam duke shkuar për të rrëmbyer numrin one-- dhe ajo që ishte emri juaj përsëri? 703 00:23:09,890 --> 00:23:10,150 >> Anan: Anan. 704 00:23:10,150 --> 00:23:11,220 >> DAVID J. Malan: Anan. 705 00:23:11,220 --> 00:23:13,540 Dhe në qoftë se ju mund të bashkohet me mua në fillimi i listës, 706 00:23:13,540 --> 00:23:14,870 le të ju vë ku ju i përkisni. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- çfarë është emri juaj? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. Malan: Stefan është në rrugë të drejtë. 710 00:23:18,191 --> 00:23:23,490 Pra, para se të Stefan zgjidh këtë problem, çfarë duhet të bëjmë? 711 00:23:23,490 --> 00:23:25,412 Çfarë bëjmë ne me Stefan? 712 00:23:25,412 --> 00:23:27,269 >> Audienca: [padëgjueshme]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. Malan: OK. 714 00:23:28,060 --> 00:23:28,850 Pra, ne mund të bëjmë atë. 715 00:23:28,850 --> 00:23:31,730 Ne mund të lloj të Stefan dhe tij katër, dhe vetëm vënë atë në një variabël 716 00:23:31,730 --> 00:23:33,530 dhe të mbajë në të atë për disa sasinë e kohës, 717 00:23:33,530 --> 00:23:35,220 duke e bërë vend për numrin një. 718 00:23:35,220 --> 00:23:36,280 Dhe kjo nuk është e keqe. 719 00:23:36,280 --> 00:23:39,270 Unë mund të sugjeroj, pse nuk e bëjmë ne vetëm vënë Stefan këtu? 720 00:23:39,270 --> 00:23:41,610 Pse mund të shkelë një kjo e ideve kemi filluar 721 00:23:41,610 --> 00:23:44,830 duke folur për herë të fundit, javën e kaluar? 722 00:23:44,830 --> 00:23:45,330 Po? 723 00:23:45,330 --> 00:23:45,740 >> Audienca: [padëgjueshme]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. Malan: Nuk ka indeks për të. 725 00:23:46,860 --> 00:23:49,735 Nëse ju mendoni për këtë, me të vërtetë, si një grup, kjo është si një negativ, 726 00:23:49,735 --> 00:23:52,900 kështu që nuk ka asnjë kujtim fakt këtu nëse kjo është me të vërtetë një grup, 727 00:23:52,900 --> 00:23:55,090 si kemi deklaruar javën e kaluar në leksion. 728 00:23:55,090 --> 00:23:56,250 Pra, ne nuk duhet ta bëjë këtë. 729 00:23:56,250 --> 00:23:57,340 Ne mund të ruani atë në një variabël. 730 00:23:57,340 --> 00:23:57,820 >> Apo ju e dini se çfarë? 731 00:23:57,820 --> 00:23:59,153 Kam dëgjuar dikush tjetër sugjerojnë atë. 732 00:23:59,153 --> 00:24:01,020 Çfarë tjetër mund të bëjmë me Stefan? 733 00:24:01,020 --> 00:24:03,770 Pse nuk kemi vetëm të dëbojë atë dhe vënë atë mbi ku numër një ishte. 734 00:24:03,770 --> 00:24:05,170 Pra, nëse ju doni të shkoni atje. 735 00:24:05,170 --> 00:24:07,300 Dhe në të vërtetë, kjo është një zgjidhje shumë e mirë. 736 00:24:07,300 --> 00:24:10,480 Tani në njërën anë, unë kam lloj e bëri problemin edhe më keq. 737 00:24:10,480 --> 00:24:13,650 Katër tani është më larg larg nga ku ajo duhet të jetë. 738 00:24:13,650 --> 00:24:14,900 Ajo duhet të jetë në drejtim të këtij gjysmë. 739 00:24:14,900 --> 00:24:16,100 >> Por ju e dini se çfarë? 740 00:24:16,100 --> 00:24:17,630 Kjo mund të ketë qenë fat i keq. 741 00:24:17,630 --> 00:24:18,822 Ndoshta numri tetë ishte këtu. 742 00:24:18,822 --> 00:24:20,530 Dhe kështu, ndoshta ne do kanë marrë me fat, 743 00:24:20,530 --> 00:24:22,460 dhe shtyrë tetë më afër deri në fund. 744 00:24:22,460 --> 00:24:24,710 Pra, në fund të ditës, Kjo lloj e të gjitha mesataret jashtë. 745 00:24:24,710 --> 00:24:26,085 Ne nuk duhet të kujdesen për katër. 746 00:24:26,085 --> 00:24:29,400 Të gjitha unë intereson tani është zgjedhjen elementin më të vogël. 747 00:24:29,400 --> 00:24:32,030 >> Dhe tani, ajo që unë jam duke shkuar për bëni është të harrojmë për numrin një 748 00:24:32,030 --> 00:24:35,160 përgjithmonë, sepse unë e di Lista prapa meje është renditur tani. 749 00:24:35,160 --> 00:24:36,720 Pra lista ime ishte më parë madhësia e tetë. 750 00:24:36,720 --> 00:24:37,720 Tani, është e madhësisë shtatë. 751 00:24:37,720 --> 00:24:40,340 Pra, problemi im po më i vogël, megjithëse në mënyrë lineare. 752 00:24:40,340 --> 00:24:43,022 Deri tani, unë jam duke shkuar për të zgjedhur element i tanishëm më i vogël, dy. 753 00:24:43,022 --> 00:24:46,520 Gjashtë, tetë, katër, tre, shtatë, pesë. 754 00:24:46,520 --> 00:24:47,770 Kjo ishte elementi më i vogël. 755 00:24:47,770 --> 00:24:49,416 Pra, çfarë jam unë do të bëj with-- çfarë ishte emri juaj përsëri? 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 Ne jemi duke shkuar për të lënë Jozefin në vend. 759 00:24:52,000 --> 00:24:54,842 Tani, unë jam duke shkuar për të pretendojë se këta njerëz are-- mirë, 760 00:24:54,842 --> 00:24:56,550 Unë e di se këto dy janë të renditura tashmë. 761 00:24:56,550 --> 00:24:58,424 Le tani të përqëndrohet në Pjesa tjetër e listës. 762 00:24:58,424 --> 00:25:00,080 Gjashtë është aktual më i vogël. 763 00:25:00,080 --> 00:25:01,190 Tetë është më e madhe. 764 00:25:01,190 --> 00:25:02,970 Katër tani është aktuale vogël. 765 00:25:02,970 --> 00:25:04,762 Tre tani është aktuale vogël. 766 00:25:04,762 --> 00:25:07,720 Dhe kështu që tani, unë jam duke shkuar për të zgjedhur tre, kush is-- çfarë është emri juaj përsëri? 767 00:25:07,720 --> 00:25:08,190 Serena: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. Malan: Serena, në qoftë se ju mund të kap numrin tuaj dhe swap 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 Come on mbrapa, dhe ne jemi do të bie në ujdi ata dy. 772 00:25:15,220 --> 00:25:17,360 Dhe tani, le të vënë këtë në autopilot. 773 00:25:17,360 --> 00:25:21,589 Unë jam duke shkuar për të shkuar dhe të lënë atë për ju djema për të zgjedhur elementët e ardhshme më të vogla. 774 00:25:21,589 --> 00:25:22,380 Dun, Dun, murmë, dun. 775 00:25:22,380 --> 00:25:24,560 Numri katër, çfarë duhet të bëni? 776 00:25:24,560 --> 00:25:26,261 Shkëlqyer. 777 00:25:26,261 --> 00:25:27,760 Tani, unë jam duke shkuar për të bërë një abone. 778 00:25:27,760 --> 00:25:28,590 Dun, Dun, murmë, dun. 779 00:25:28,590 --> 00:25:31,465 Unë shoh pesë është tjetër vogël. 780 00:25:31,465 --> 00:25:32,840 Tani, unë jam duke shkuar për të marrë një tjetër abone. 781 00:25:32,840 --> 00:25:33,631 Dun, Dun, murmë, dun. 782 00:25:33,631 --> 00:25:34,880 Gjashtë është më i vogël. 783 00:25:34,880 --> 00:25:35,520 Të mirë. 784 00:25:35,520 --> 00:25:36,585 Shtatë është më i vogël. 785 00:25:36,585 --> 00:25:37,085 Nuk ka ndryshim. 786 00:25:37,085 --> 00:25:38,630 Tetë është më i vogël. 787 00:25:38,630 --> 00:25:39,170 Done. 788 00:25:39,170 --> 00:25:43,900 >> Pra, ajo që ne kemi bërë vetëm nga iteratively një element të zgjedhur pas tjetrit 789 00:25:43,900 --> 00:25:47,230 është të zbatojë diçka që ne jemi duke shkuar për të formalizuar si përzgjedhës lloj. 790 00:25:47,230 --> 00:25:49,120 Dhe kjo është ndoshta edhe thjeshtë për të shpjeguar, 791 00:25:49,120 --> 00:25:51,310 në që fjalë për fjalë të gjithë ju doni të bëni është vetëm i mbajnë 792 00:25:51,310 --> 00:25:54,700 duke shkuar mbrapa dhe me radhë nëpër lista zgjedhjen, elementi tjetër i vogël, 793 00:25:54,700 --> 00:25:55,720 derisa ju jeni bërë. 794 00:25:55,720 --> 00:25:58,650 >> Pra, kjo është edhe më të thjeshta, ndoshta intuitive, se fundit. 795 00:25:58,650 --> 00:26:00,020 Le të provoni një e fundit. 796 00:26:00,020 --> 00:26:03,060 Në qoftë se ju djema mund të rivendosur veten në pozitat vijuese 797 00:26:03,060 --> 00:26:08,600 një kohë e fundit, le të shohim nëse ne nuk mund të tani formalizojë një qasje tjetër. 798 00:26:08,600 --> 00:26:12,857 Në fakt, do dikush atje doja të propozojë 799 00:26:12,857 --> 00:26:14,440 si tjetër ne mund të shkojë për të bërë këtë? 800 00:26:14,440 --> 00:26:17,439 Pa hedhur nga buzzwords apo lloj e përgjigjeve që janë të njohur tashmë, 801 00:26:17,439 --> 00:26:19,689 vetëm intuitive, çfarë mund të bëjmë? 802 00:26:19,689 --> 00:26:21,635 >> Audienca: [padëgjueshme]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. Malan: Po. 804 00:26:22,510 --> 00:26:24,620 Pra, ka disa intuitë të madh atje. 805 00:26:24,620 --> 00:26:28,020 Gjërat e mira duket të ndodhë deri tani në shkenca kompjuterike, kur ne të ndarë 806 00:26:28,020 --> 00:26:30,832 dhe të pushtuar problemin e ndarjes atë në gjysmë dhe gjysmë dhe gjysmë. 807 00:26:30,832 --> 00:26:32,540 Dhe kështu me të vërtetë, ne mund të fillojë për të bërë këtë. 808 00:26:32,540 --> 00:26:35,754 Dhe në fakt, kjo do të jetë, ne do të shih, një nga zgjidhjet tona më të mira ende. 809 00:26:35,754 --> 00:26:37,420 Por le të kthehemi në atë para se të gjatë. 810 00:26:37,420 --> 00:26:40,500 Në fakt, ne jemi duke shkuar për të bërë se pak më vonë gjatë kësaj jave. 811 00:26:40,500 --> 00:26:42,180 Çfarë tjetër mund të bëjmë për të zgjidhur këtë? 812 00:26:42,180 --> 00:26:44,647 Kështu që të gjithë këtu është në mënyrë në dukje të rastit. 813 00:26:44,647 --> 00:26:45,230 E di çfarë? 814 00:26:45,230 --> 00:26:48,320 Në vend se të shkuar mbrapa dhe me radhë, mbrapa dhe me radhë, mbrapa dhe me radhë 815 00:26:48,320 --> 00:26:50,624 çdo herë, kjo ndjehet si Unë jam duke bërë një shumë të ecin. 816 00:26:50,624 --> 00:26:52,790 Pse nuk mund vetëm të fillojë në fillimi i listës, 817 00:26:52,790 --> 00:26:54,960 dhe vetëm vënë katër ku i takon? 818 00:26:54,960 --> 00:26:59,680 Pra më lejoni të supozojmë për momentin se lista ime është vetëm ky element i parë. 819 00:26:59,680 --> 00:27:04,937 Është katër të renditura në këtë moment në kohë, në qoftë se të gjitha që më intereson është gjithçka këtu? 820 00:27:04,937 --> 00:27:06,520 Kjo është lloj i trivially e vërtetë, e drejtë? 821 00:27:06,520 --> 00:27:10,000 Ashtu si listë që përmban një numër, dhe se numri katër është e renditura qartë. 822 00:27:10,000 --> 00:27:13,070 >> Pra, më lejoni vetëm të parashikojë se kjo listë është renditur. 823 00:27:13,070 --> 00:27:15,090 Por tani unë kam pjesën tjetër të kësaj liste. 824 00:27:15,090 --> 00:27:17,240 Deri tani, unë hasni dy. 825 00:27:17,240 --> 00:27:21,690 Ku ka dy padyshim përkasin në lidhje me katër? 826 00:27:21,690 --> 00:27:22,580 Para katër. 827 00:27:22,580 --> 00:27:23,862 Pra, çfarë mund të bëj këtu? 828 00:27:23,862 --> 00:27:24,820 Cili është emri juaj përsëri? 829 00:27:24,820 --> 00:27:25,090 >> Joseph: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. Malan: Joseph, nëse ju mund të hap prapa 831 00:27:26,030 --> 00:27:27,790 për vetëm një moment me numrin tuaj. 832 00:27:27,790 --> 00:27:31,130 Dhe tani çfarë duhet të bëjë Stefan këtu? 833 00:27:31,130 --> 00:27:33,720 Le të zhvendoset Stefan mbi këtu. 834 00:27:33,720 --> 00:27:35,520 Dhe tani, le të Jozefi vijë këtu. 835 00:27:35,520 --> 00:27:39,660 Dhe tani, më lejoni të pohojnë se çdo gjë këtu është e renditura. 836 00:27:39,660 --> 00:27:42,474 Pra, rezultat i ngjashëm, por një qasje krejtësisht të ndryshme. 837 00:27:42,474 --> 00:27:44,140 Unë nuk kam shikuar edhe ajo që është atje poshtë. 838 00:27:44,140 --> 00:27:46,310 Unë vetëm i mbajnë duke marrë elementet si ata janë dorëzuar për mua, 839 00:27:46,310 --> 00:27:47,240 dhe të merren me ta. 840 00:27:47,240 --> 00:27:48,330 >> Deri tani, unë shoh numrin gjashtë. 841 00:27:48,330 --> 00:27:51,110 Ku ka numër gjashtë përket? 842 00:27:51,110 --> 00:27:53,250 Ne kemi dy, katër, gjashtë. 843 00:27:53,250 --> 00:27:54,800 Pikërisht aty ku ajo është e drejtë tani. 844 00:27:54,800 --> 00:27:57,750 Pra, le të lënë që vetëm, dhe tani pretendimit se kjo pjesë e lista 845 00:27:57,750 --> 00:27:58,772 është renditur tani. 846 00:27:58,772 --> 00:28:01,230 Dhe kështu, kjo ndihet krejtësisht i ndryshëm në atë që unë jam vetëm 847 00:28:01,230 --> 00:28:05,230 lëviz nëpër lista këtu lineare, dhe unë kurrë nuk jam duke e dyfishuar prapa. 848 00:28:05,230 --> 00:28:05,730 Po. 849 00:28:05,730 --> 00:28:06,230 Në rregull. 850 00:28:06,230 --> 00:28:08,190 Pra tetë, ku ju takon? 851 00:28:08,190 --> 00:28:08,730 Mu ketu. 852 00:28:08,730 --> 00:28:09,310 Përsosur. 853 00:28:09,310 --> 00:28:10,210 Deri tani, një. 854 00:28:10,210 --> 00:28:10,900 Uh-oh. 855 00:28:10,900 --> 00:28:13,010 Kjo ndjehet si ajo është do të jetë i shtrenjtë. 856 00:28:13,010 --> 00:28:15,690 Tani, në algorithm e mëparshëm, Unë vetëm swapped njerëzit. 857 00:28:15,690 --> 00:28:18,648 Kështu që unë mund të vënë atë të gjithë rrugën në fillimi, por pastaj u zhvendos Jozefin. 858 00:28:18,648 --> 00:28:21,450 Por në qoftë se unë të lëvizur Jozefi, tani çfarë do të jetë i gabuar? 859 00:28:21,450 --> 00:28:24,250 >> Tani, unë kam lloj undone-- kam ndërmarrë një hap përpara dhe pastaj 860 00:28:24,250 --> 00:28:26,300 një hap prapa, sepse tani Jozefi do të jetë jashtë funksionit. 861 00:28:26,300 --> 00:28:26,830 Pra, le ta bëjmë këtë. 862 00:28:26,830 --> 00:28:29,150 Nëse ju mund të marrë një numër dhe hap prapa për vetëm një moment. 863 00:28:29,150 --> 00:28:30,490 Si mund të put-- çfarë ishte emri juaj përsëri? 864 00:28:30,490 --> 00:28:31,130 >> Anan: Anan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. Malan: Annan në vend? 866 00:28:32,610 --> 00:28:36,091 Çfarë duhet të ndodhë me respekt për të dy, katër, gjashtë dhe tetë? 867 00:28:36,091 --> 00:28:37,570 Ata të gjithë duhet të zhvendoset. 868 00:28:37,570 --> 00:28:42,590 Pra, nëse tetë do të donte për të zhvendosur së pari, pastaj gjashtë, pastaj katër, pastaj dy. 869 00:28:42,590 --> 00:28:45,380 Dhe pastaj Anan, në qoftë se ju do të si për të ardhur këtu, mirë. 870 00:28:45,380 --> 00:28:47,760 Por këtu, ne kemi vetëm lloj i pagoi një çmim 871 00:28:47,760 --> 00:28:49,510 në një pikë të ndryshme në algoritmin. 872 00:28:49,510 --> 00:28:52,550 Ndërsa herën e fundit me zgjedhjen lloj, dhe madje flluskë lloj, 873 00:28:52,550 --> 00:28:54,700 Unë jam duke ecur mbrapa dhe radhë, mbrapa dhe me radhë, 874 00:28:54,700 --> 00:28:58,360 e cila është sigurisht duke shtuar deri kohë-i mençur, dhe fjalë për fjalë hap pas hapi. 875 00:28:58,360 --> 00:29:00,660 >> Futje lloj, në fillim shikim, duket sikur është 876 00:29:00,660 --> 00:29:05,150 super të zgjuar, në atë që unë jam vetëm duke bërë përparim të ngadalshëm, rritje, 877 00:29:05,150 --> 00:29:07,120 por unë nuk jam duke shkuar ky mbrapa dhe me radhë. 878 00:29:07,120 --> 00:29:09,410 Por në qoftë se dikush është me të vërtetë nga e rendit, njoftimi 879 00:29:09,410 --> 00:29:10,840 të gjithë punën Unë vetëm kishte për të bërë. 880 00:29:10,840 --> 00:29:14,750 Unë kisha për të lëvizur gjysmën e listës vetëm për të bërë vend për numrin një. 881 00:29:14,750 --> 00:29:16,790 Pra, kjo është shuma e njëjtë e punës deri më tani atë 882 00:29:16,790 --> 00:29:18,690 ndihet, vetëm një lloj tjetër të punës. 883 00:29:18,690 --> 00:29:19,370 >> Le të vazhdojnë. 884 00:29:19,370 --> 00:29:22,657 Pra, tani ne e dimë se të gjithë ndërmjet një dhe tetë janë të renditura. 885 00:29:22,657 --> 00:29:23,740 Këtu, unë kam numrin tre. 886 00:29:23,740 --> 00:29:25,864 Nëse ju pëlqen të marr numri tre, hap prapa një të tillë. 887 00:29:25,864 --> 00:29:28,260 Dhe çfarë mendoni ju djema duhet të bëni? 888 00:29:28,260 --> 00:29:28,760 Yep. 889 00:29:28,760 --> 00:29:33,070 Pra, kjo është një tjetër një, dy, tre hapa. 890 00:29:33,070 --> 00:29:36,010 Tre njësi të kohës që vetëm kushtojnë mua, kështu që tre tani mund të përshtatet. 891 00:29:36,010 --> 00:29:37,460 Së fundi, shtatë. 892 00:29:37,460 --> 00:29:39,730 >> Le të shkojnë përpara dhe të ketë ju të marrë një hap prapa. 893 00:29:39,730 --> 00:29:42,780 Kjo është vetëm do të na kushtojë një njësi e kohës, por kjo është në rregull. 894 00:29:42,780 --> 00:29:44,170 Dhe tani, pesë-së do të të jetë pak më të shtrenjtë. 895 00:29:44,170 --> 00:29:45,340 Nëse ju dëshironi të hap prapa. 896 00:29:45,340 --> 00:29:48,380 Ne kemi nevojë për të lëvizur tetë, dhe shtatë, dhe gjashtë. 897 00:29:48,380 --> 00:29:50,749 Dhe pastaj të gjithë po zgjidhet tani. 898 00:29:50,749 --> 00:29:52,290 Pra, një dorë e madhe për vullnetarët tanë këtu. 899 00:29:52,290 --> 00:29:53,554 Shume faleminderit. 900 00:29:53,554 --> 00:29:56,220 >> [Duartrokitje] 901 00:29:56,220 --> 00:29:56,860 >> Ju faleminderit të gjithëve. 902 00:29:56,860 --> 00:29:57,520 Ju faleminderit të gjithëve. 903 00:29:57,520 --> 00:30:02,940 Pra, le të shohim tani se sa kushtueshme të gjithë se ishte. 904 00:30:02,940 --> 00:30:06,210 Le të konsiderojmë ndoshta thjeshtë nga këto, lloj flluskë. 905 00:30:06,210 --> 00:30:09,950 Dhe unë them thjeshtë, vetëm për shkak ju mund të zgjidhin atë me lakmi nga vetëm 906 00:30:09,950 --> 00:30:11,660 zgjidhur problemin pairwise këtu. 907 00:30:11,660 --> 00:30:13,720 Zgjidhur problemin pairwise këtu, përsëri dhe përsëri 908 00:30:13,720 --> 00:30:17,680 dhe përsëri, duke përsëritur si shumë herë të ju në të vërtetë nevojë për të. 909 00:30:17,680 --> 00:30:21,050 >> Pra, rezulton se me një lloj flluskë, mirë, 910 00:30:21,050 --> 00:30:25,820 sa hapa nuk kam për të të marrë në kalojë e parë e këtij algoritmi? 911 00:30:25,820 --> 00:30:30,850 Unë mund të take-- le see-- një, dy, tre, katër, pesë, gjashtë, shtatë. 912 00:30:30,850 --> 00:30:32,190 Dhe nuk ka tetë elemente këtu. 913 00:30:32,190 --> 00:30:35,280 Pra, kjo është si n minus 1 hapa për merrni nga fillimi i listës 914 00:30:35,280 --> 00:30:36,380 në fund të lista. 915 00:30:36,380 --> 00:30:41,350 >> Por me përzgjedhjes lloj, kujtojnë se unë jam zgjedhjen elementet përsëri dhe përsëri 916 00:30:41,350 --> 00:30:44,590 dhe një herë se është i vogël, Unë jam vënë atë në vend, 917 00:30:44,590 --> 00:30:46,616 por pastaj unë nuk jam në kërkim pas meje përsëri. 918 00:30:46,616 --> 00:30:49,490 Kështu që unë mendoj se është pak më i qartë pastaj se herë të parë, unë mund 919 00:30:49,490 --> 00:30:52,680 duhet të marrin të gjitha n minus 1 hapa për të gjetur elementin më të vogël. 920 00:30:52,680 --> 00:30:55,920 Pastaj kam vënë ato në vend, dhe unë dëbojë kush ishte këtu më parë. 921 00:30:55,920 --> 00:30:57,500 >> Por atëherë unë nuk duhet të mbajtur në kërkim në këtë element, 922 00:30:57,500 --> 00:30:59,040 sepse unë e di se është tashmë më të vogël. 923 00:30:59,040 --> 00:31:01,581 Deri tani, unë mund të shikoni në vetëm shtatë elemente, atëherë gjashtë elemente, 924 00:31:01,581 --> 00:31:03,290 pastaj pesë elemente, pastaj katër elemente. 925 00:31:03,290 --> 00:31:06,900 Dhe kështu matematikisht, nëse n është numri i elementeve ose numra 926 00:31:06,900 --> 00:31:11,990 se kemi filluar me, ju mund të imagjinoni se kjo është e njëjtë si n minus 1, 927 00:31:11,990 --> 00:31:14,250 plus n minus 2 hapa, plus n minus 3 hapa, 928 00:31:14,250 --> 00:31:16,780 plus n minus 4 hapa, të gjithë Mënyra poshtë për të vetëm një hap. 929 00:31:16,780 --> 00:31:18,160 Dhe unë jam në personin tim të fundit. 930 00:31:18,160 --> 00:31:20,650 >> Dhe në qoftë se ju kujtohet se një shumë i stats librave apo libra të matematikës 931 00:31:20,650 --> 00:31:24,730 kanë këto formula në Hardcover prapa ose para tyre, 932 00:31:24,730 --> 00:31:27,690 rezulton se këtë seri mund të shprehet më thjesht 933 00:31:27,690 --> 00:31:28,857 si kohët n n minus 1 mbi 2. 934 00:31:28,857 --> 00:31:31,273 Dhe kjo është në rregull në qoftë se kjo nuk është e në ballë e mendjen tuaj. 935 00:31:31,273 --> 00:31:32,420 Por kjo është me të vërtetë e vërtetë. 936 00:31:32,420 --> 00:31:34,449 Kjo është vetëm një mënyrë e thjeshtë e shkruar atë. 937 00:31:34,449 --> 00:31:36,240 Dhe pastaj në qoftë se ju mendoni se përsëri në klasën e shkollës, 938 00:31:36,240 --> 00:31:38,698 kur ju sapo filloni shumëzuar gjërat, kjo natyrisht, 939 00:31:38,698 --> 00:31:41,820 është vetëm katror n minus n ndarë nga 2. 940 00:31:41,820 --> 00:31:44,772 Të gjitha unë kam bërë është të zgjerohet shprehjet atje. 941 00:31:44,772 --> 00:31:46,730 Dhe kështu që le të rishkruaj këtë pak ndryshe. 942 00:31:46,730 --> 00:31:49,780 Kjo është n katrore e ndarë nga 2 minus n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Pra, përsëri, unë jam vetëm lloji i aplikimit disa aritmetikë rregullat atje. 944 00:31:53,270 --> 00:31:57,140 Por vini re tani se termi më i madh në këtë shprehje, kështu që të flasin, 945 00:31:57,140 --> 00:31:58,540 n është se katror. 946 00:31:58,540 --> 00:32:02,910 Pra, po, kjo është n katror e ndarë nga 2, minus n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Por në përgjithësi, në qoftë se është n do të jetë një vlerë e madhe, 948 00:32:05,080 --> 00:32:08,740 Unë do të thonë se n katror do të jetë faktori dominant. 949 00:32:08,740 --> 00:32:10,490 Është vetëm do të jetë një kontribues i madh 950 00:32:10,490 --> 00:32:12,877 me numrin e hapave sesa n / 2. 951 00:32:12,877 --> 00:32:13,960 Pra, çfarë dua të them me këtë? 952 00:32:13,960 --> 00:32:16,795 Le të provoni një shembull të thjeshtë, madje edhe pse matematikë merr një i madh pak. 953 00:32:16,795 --> 00:32:20,210 >> Pra, mendoj që ne kishim 1 milion njerëz në skenë, apo 1 milion gjëra 954 00:32:20,210 --> 00:32:21,320 se ne duam për të zgjidhur. 955 00:32:21,320 --> 00:32:23,730 Le të plug një milion në pikërisht këtë formulë 956 00:32:23,730 --> 00:32:27,230 për të parë se sa hapa ajo merr gjithsej për të zgjidhur një milion elemente të përdorur të themi, 957 00:32:27,230 --> 00:32:28,560 lloj përzgjedhje. 958 00:32:28,560 --> 00:32:30,760 >> Pra, ne do të kemi të njëjtën formulë si më parë. 959 00:32:30,760 --> 00:32:34,120 Unë do të plug një milion, kështu që unë të marrë një milion katrore ndarë nga 2, 960 00:32:34,120 --> 00:32:35,990 minus një milion e ndarë nga 2. 961 00:32:35,990 --> 00:32:40,180 Nëse unë bëj atë matematikë më parë këtu, ne kemi 500 miliardë 962 00:32:40,180 --> 00:32:47,460 minus 500,000, e cila na jep 499999500000, 963 00:32:47,460 --> 00:32:49,270 i cili është goxha i mallkuar i madh. 964 00:32:49,270 --> 00:32:54,370 >> Në fakt, në qoftë se ju krahasoni tani 499000000000, 999000000, 965 00:32:54,370 --> 00:33:01,210 500,000 kundër vlerës tonë origjinal, 500 miliardë, kjo është aq damn afër. 966 00:33:01,210 --> 00:33:06,850 E drejtë? n katrore e ndarë nga 2 jep us-- ose më mirë, n katrore ndarë nga 2 967 00:33:06,850 --> 00:33:08,370 na dhanë 500 miliardë. 968 00:33:08,370 --> 00:33:13,510 Kjo është goxha i mallkuar afër në 499,999,500,000, 969 00:33:13,510 --> 00:33:17,970 që do të thotë zbritur off 500,000, ose më në përgjithësi, zbritur off 970 00:33:17,970 --> 00:33:20,010 n katror, ​​jo të vërtetë një punë e madhe. 971 00:33:20,010 --> 00:33:22,490 N katror bën këto Numrat rriten me të vërtetë i shpejtë. 972 00:33:22,490 --> 00:33:25,790 >> Tani, kjo është e rëndësishme vetëm për aq si ne, si shkencëtarët kompjuterike, 973 00:33:25,790 --> 00:33:29,350 në përgjithësi nuk do të kujdesen aq shumë për nuancat e këtyre formulave 974 00:33:29,350 --> 00:33:31,400 dhe pikërisht ajo që përgjigje të sakta janë. 975 00:33:31,400 --> 00:33:33,390 Kemi kujdes vetëm se, ju e dini se çfarë? 976 00:33:33,390 --> 00:33:37,810 Në fund të ditës, kjo formulë është në mënyrë të n katror. 977 00:33:37,810 --> 00:33:39,350 >> Po, ne jemi duke e ndarë nga 2 në atje. 978 00:33:39,350 --> 00:33:41,360 Po, ne jemi duke zbritur off n minus 2. 979 00:33:41,360 --> 00:33:46,860 Por në fund të ditës, termi që me të vërtetë na lëndon dhe na kushton 980 00:33:46,860 --> 00:33:48,995 shumë hapa është se termi katrore. 981 00:33:48,995 --> 00:33:51,370 Dhe kështu që ajo që një shkencëtar kompjuteri do të në përgjithësi të bëjë 982 00:33:51,370 --> 00:33:54,160 po injorojnë të gjithë ata Termat vogla rendit, 983 00:33:54,160 --> 00:33:56,900 dhe vetëm shikoni në atë që kontribuon më me koston. 984 00:33:56,900 --> 00:34:00,530 >> Dhe kjo është e bukur, sepse ne mund të tani flasim në parim i përgjithshëm shumë më të madh 985 00:34:00,530 --> 00:34:02,470 në lidhje me algoritme, dhe mund të krahasohen ato. 986 00:34:02,470 --> 00:34:04,550 Dhe fakti që unë jam duke përdorur këtë O është e qëllimshme. 987 00:34:04,550 --> 00:34:06,680 Kur them në mënyrë e, unë jam në mënyrë specifike 988 00:34:06,680 --> 00:34:09,560 duke iu referuar diçka quajtur O. e madhe dhe e madhe o 989 00:34:09,560 --> 00:34:14,090 është një simbol që një kompjuter shkencëtar përdor për të përshkruar 990 00:34:14,090 --> 00:34:16,710 një kufi i sipërm për diçka. 991 00:34:16,710 --> 00:34:21,150 >> Pra, nëse ju them se një algoritëm është në O madhe të n katror, 992 00:34:21,150 --> 00:34:23,380 si unë propozuar vetëm një moment më parë, që do të thotë 993 00:34:23,380 --> 00:34:27,710 se në aspektin e drejtimin e saj herë ose efikasiteti i tij, 994 00:34:27,710 --> 00:34:30,090 ajo merr në mënyrë e n katror hapa. 995 00:34:30,090 --> 00:34:31,420 Ndoshta më shumë, ndoshta më pak. 996 00:34:31,420 --> 00:34:33,435 Por kjo është në mënyrë të n katror. 997 00:34:33,435 --> 00:34:34,560 Dhe kjo është kufi i sipërm. 998 00:34:34,560 --> 00:34:36,530 Kjo nuk do të jetë më e dhimbshme se kaq. 999 00:34:36,530 --> 00:34:40,800 Kjo nuk do të jetë n cubed, ose 2 me n, apo diçka shumë më të madhe. 1000 00:34:40,800 --> 00:34:43,800 Ky është një kufi i sipërm për çfarëdo që kostoja është. 1001 00:34:43,800 --> 00:34:46,150 Pra duke pasur parasysh se, le të konsiderojnë vetëm disa shembuj. 1002 00:34:46,150 --> 00:34:49,820 Dhe kjo është vetëm një listë të fundme herë e shumë të zakonshme running 1003 00:34:49,820 --> 00:34:52,870 për algoritme që është menduar të jetë ilustrues i disa gjëra që ne kemi 1004 00:34:52,870 --> 00:34:53,600 parë tashmë. 1005 00:34:53,600 --> 00:34:58,060 >> Kështu për shembull, në rastin e Zgjedhja lloj, çfarë unë jam duke pretenduar këtu 1006 00:34:58,060 --> 00:35:02,250 po kalon ky lloj përzgjedhës Ora është në mënyrë të n katror. 1007 00:35:02,250 --> 00:35:06,260 Në rastin më të keq, unë jam do të ketë një bandë e tërë e numrave të rastit këtu. 1008 00:35:06,260 --> 00:35:08,600 Dhe siç e pamë matematikisht, në qoftë se unë mbaj duke ecur 1009 00:35:08,600 --> 00:35:11,310 nëpër lista, përmes Lista, zgjedhjen e ardhshme të vogël 1010 00:35:11,310 --> 00:35:14,410 element përsëri dhe përsëri, në qoftë se unë në fakt shkruani të gjitha hapat 1011 00:35:14,410 --> 00:35:18,750 Unë jam duke marrë si kam propozuar formulaically para, kjo është me urdhër të n katror 1012 00:35:18,750 --> 00:35:20,370 Hapat që unë jam duke marrë. 1013 00:35:20,370 --> 00:35:24,520 >> Dhe kjo rezulton se flluskë lloj dhe futje lloj 1014 00:35:24,520 --> 00:35:27,370 janë po aq të ngadalshëm në rastin më të keq. 1015 00:35:27,370 --> 00:35:32,040 Mendoni, për shembull, futje lloj, shumë të fundit algorithm kemi trajtuar me të, 1016 00:35:32,040 --> 00:35:35,500 e cila kishte të shikojmë në elementin, dhe pastaj futur atë ku i takon. 1017 00:35:35,500 --> 00:35:38,720 Dhe pastaj kemi shikuar në elementin e ardhshëm, dhe futur atë ku i takon. 1018 00:35:38,720 --> 00:35:40,990 >> Kështu që e konsiderojnë skenarin më të mirë të mundshme. 1019 00:35:40,990 --> 00:35:45,590 Mendoj unë kisha vullnetarët e mia të vijë deri fjalë për fjalë si kjo, një anë të tetë, 1020 00:35:45,590 --> 00:35:47,440 tashmë të renditura. 1021 00:35:47,440 --> 00:35:51,300 Sa hapa është futje lloj do të marrë për të zgjidhur tetë persona, 1022 00:35:51,300 --> 00:35:55,640 në qoftë se ata të arrijnë në skenë në kërkim si kjo? 1023 00:35:55,640 --> 00:35:57,410 >> Tetë persona tashmë të renditura. 1024 00:35:57,410 --> 00:35:58,760 Dhe unë e përdorin futje lloj. 1025 00:35:58,760 --> 00:36:02,180 Kjo e fundit e algoritme. 1026 00:36:02,180 --> 00:36:03,640 E pra, le të reenact agjërimin e vërtetë. 1027 00:36:03,640 --> 00:36:05,504 Pra, nëse unë të fillojë këtu, unë shoh një të tillë. 1028 00:36:05,504 --> 00:36:06,420 Ku ka një përket? 1029 00:36:06,420 --> 00:36:07,730 Ajo i takon të drejtë këtu. 1030 00:36:07,730 --> 00:36:08,330 Unë shoh dy. 1031 00:36:08,330 --> 00:36:09,660 Ku ka dy takon? 1032 00:36:09,660 --> 00:36:10,260 Mu ketu. 1033 00:36:10,260 --> 00:36:10,900 Unë shoh tre. 1034 00:36:10,900 --> 00:36:11,920 Ku ka tre takon? 1035 00:36:11,920 --> 00:36:12,480 Mu ketu. 1036 00:36:12,480 --> 00:36:13,100 >> Unë po shoh katër. 1037 00:36:13,100 --> 00:36:13,600 Mu ketu. 1038 00:36:13,600 --> 00:36:15,660 Pesë, gjashtë, shtatë, tetë. 1039 00:36:15,660 --> 00:36:17,320 Nuk ka asnjë arsye për të përsëritur veten. 1040 00:36:17,320 --> 00:36:21,260 Dhe kështu, sa shumë hapa është se në drejtim të n? 1041 00:36:21,260 --> 00:36:23,870 Kjo është në mënyrë të n hapa, e drejtë? n minus 1. 1042 00:36:23,870 --> 00:36:27,567 Por mora një numër lineare e hapa, dhe tani unë jam bërë. 1043 00:36:27,567 --> 00:36:28,900 Pra, kjo është rasti më i mirë, edhe pse. 1044 00:36:28,900 --> 00:36:29,983 Po në lidhje me rastin më të keq? 1045 00:36:29,983 --> 00:36:32,730 Çfarë tetë ishin atje, dhe shtatë ishin poshtë atje, 1046 00:36:32,730 --> 00:36:35,840 dhe një dhe dy ishin mbi këtu, kështu që se lista u ndryshuan me të vërtetë? 1047 00:36:35,840 --> 00:36:38,300 >> E pra, çfarë ndodh në të vërtetë në qoftë se ky është numri? 1048 00:36:38,300 --> 00:36:41,300 Dhe ne do të bëjmë vetëm disa shembuj. 1049 00:36:41,300 --> 00:36:49,300 Çfarë nëse, vërtet, numri tetë është këtu, dhe uh number--. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Pra, çfarë nëse, në të vërtetë, numri i tetë është gjatë gjithë rrugës gjatë këtu, 1052 00:36:56,430 --> 00:36:57,790 dhe unë jam duke përdorur futje lloj? 1053 00:36:57,790 --> 00:36:58,290 >> NE RREGULL. 1054 00:36:58,290 --> 00:37:00,280 Unë pretendojnë në këtë moment kjo është në vend. 1055 00:37:00,280 --> 00:37:03,152 Por tani, seven-- ku ka shtatë shkoni? 1056 00:37:03,152 --> 00:37:04,360 Sigurisht, ajo shkon mbi këtu. 1057 00:37:04,360 --> 00:37:06,760 Pra, unë kam për të lëvizur tetë mbi një vend. 1058 00:37:06,760 --> 00:37:08,554 Tani gjashtë, ku do të shkojë? 1059 00:37:08,554 --> 00:37:09,220 E pra, të gjithë të drejtë. 1060 00:37:09,220 --> 00:37:13,150 Tani, unë kam për të lëvizur mbi tetë një vend, dhe shtatë më shumë se një vend, 1061 00:37:13,150 --> 00:37:14,440 dhe pastaj unë pllum poshtë gjashtë. 1062 00:37:14,440 --> 00:37:16,870 >> Pra, për herë të parë, ajo kosto mua një hap për të rregulluar gjërat, 1063 00:37:16,870 --> 00:37:18,570 atëherë ajo të kushtojë më dy hapa për të rregulluar gjërat. 1064 00:37:18,570 --> 00:37:20,370 Sa hapa është ajo do të marrë për të rregulluar 1065 00:37:20,370 --> 00:37:22,720 gjëra për të vënë pesë në vendin e duhur? 1066 00:37:22,720 --> 00:37:23,340 Tre. 1067 00:37:23,340 --> 00:37:29,520 Sepse tani më duhet të lëvizur një, dy, tre. 1068 00:37:29,520 --> 00:37:32,430 Sa hapa është ajo do të marrë për të vënë katër në vendin e duhur? 1069 00:37:32,430 --> 00:37:36,040 4 plus 5, plus 6, plus 7. 1070 00:37:36,040 --> 00:37:40,260 >> Dhe kështu që është matematikisht identike me ajo që ne e përshkroi për përzgjedhjes lloj. 1071 00:37:40,260 --> 00:37:42,130 Ne kemi këtë seri kjo është vetëm në rritje. 1072 00:37:42,130 --> 00:37:45,650 1 plus 2 plus 3 plus 4, ose anasjelltas, 7 plus 6 1073 00:37:45,650 --> 00:37:52,610 plus 5 plus 4 shton për sotëm si qëllim të në mënyrë të n katror. 1074 00:37:52,610 --> 00:37:57,640 >> Pra më lejoni të përcaktojnë gjithashtu se flluskë lloj është edhe në n katror. 1075 00:37:57,640 --> 00:38:01,340 Sepse me lloj flluskë, çdo herë që unë shkoj nëpër lista, 1076 00:38:01,340 --> 00:38:03,100 Unë jam duke marrë afërsisht sa hapa? 1077 00:38:03,100 --> 00:38:06,260 Çdo herë që unë fjalë për fjalë këmbë nga aty deri atje? 1078 00:38:06,260 --> 00:38:07,960 Afërsisht hapa n. 1079 00:38:07,960 --> 00:38:12,650 Por sa herë fuqinë unë nevojë për të shkuar nëpër lista? 1080 00:38:12,650 --> 00:38:13,920 >> E pra, afërsisht n herë. 1081 00:38:13,920 --> 00:38:15,680 Ndoshta n minus 1, por afërsisht herë n. 1082 00:38:15,680 --> 00:38:16,430 E pra, pse është kjo? 1083 00:38:16,430 --> 00:38:19,560 E pra, me flluskë lloji, nëse ne fillojmë me flluskë lloji, 1084 00:38:19,560 --> 00:38:23,570 me listën në më të keqen e mundshme situatë, e cila përsëri është plotësisht 1085 00:38:23,570 --> 00:38:25,550 prapa, çfarë do të ndodhë? 1086 00:38:25,550 --> 00:38:28,830 Unë shkoj nëpër lista, dhe numri një i takon të gjithë rrugën atje. 1087 00:38:28,830 --> 00:38:33,280 >> Por me flluskë lloji, sa larg nuk e lëvizin mbi kalojë tim të parë përmes listës? 1088 00:38:33,280 --> 00:38:36,620 Sa spote e bën ai të marrë më afër në vendin e duhur? 1089 00:38:36,620 --> 00:38:37,240 Vetem nje. 1090 00:38:37,240 --> 00:38:40,281 Pra, nëse ju lloj arsye përmes kësaj, çdo herë përmes këtij algoritmi, 1091 00:38:40,281 --> 00:38:41,880 Duke marrë afërsisht Hapat e Davidit n. 1092 00:38:41,880 --> 00:38:44,940 Por sa kalon nëpër lista është ajo 1093 00:38:44,940 --> 00:38:49,060 do të marrë për një të flluskë në të majtë, ku i takon? 1094 00:38:49,060 --> 00:38:51,840 >> Ai e mori për të lëvizur si, Hapësirat n në këtë mënyrë. 1095 00:38:51,840 --> 00:38:57,960 Pra, vetëm për të bërë klasifikim i listës, Unë duhet të ecin mbrapa dhe me radhë herë n. 1096 00:38:57,960 --> 00:39:01,540 Dhe çdo herë, unë jam duke kërkuar në n elemente. 1097 00:39:01,540 --> 00:39:05,410 Pra, bëni gjëra n n herë në rendi i n katror. 1098 00:39:05,410 --> 00:39:07,220 >> Tani, ne do të shohim në disa e pantallona të shkurtra që 1099 00:39:07,220 --> 00:39:10,440 janë të ngulitura në problemin e ardhshëm CS50 e vendosur, një tjetër qasje në këto, 1100 00:39:10,440 --> 00:39:13,490 por tani për tani, le të vetëm të marrin në konsideratë disa herë të tjera running, 1101 00:39:13,490 --> 00:39:16,840 veçanërisht nëse ato klasifikim marrin pak kohë për të zhytet në. 1102 00:39:16,840 --> 00:39:21,790 Çfarë është një algoritmi që ne kemi parë tashmë që merr në mënyrë të hapave n? 1103 00:39:21,790 --> 00:39:27,560 >> Çfarë duhet të marrë një numër lineare i hapave që kemi parë deri më tani? 1104 00:39:27,560 --> 00:39:29,350 Cfare eshte kjo? 1105 00:39:29,350 --> 00:39:30,480 Kërkimi Lista telefonit. 1106 00:39:30,480 --> 00:39:31,390 Algorithm e parë. 1107 00:39:31,390 --> 00:39:31,560 E drejtë? 1108 00:39:31,560 --> 00:39:33,650 Ku ne jemi linear kërkim për Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Ne te vertete. 1110 00:39:34,150 --> 00:39:37,180 Nga java zero, kur kam filluar duke e kthyer një faqe në një kohë, 1111 00:39:37,180 --> 00:39:40,095 dhe unë madje tha se ajo ishte lloj nga një ndjenjë lineare algorithm, 1112 00:39:40,095 --> 00:39:42,720 dhe ne kishim këtë foto në Bordi me vijë të drejtë e kuqe 1113 00:39:42,720 --> 00:39:44,678 dhe të verdhë drejt line, ato ishin me të vërtetë 1114 00:39:44,678 --> 00:39:46,810 algoritme që janë në O madh të n. 1115 00:39:46,810 --> 00:39:50,680 >> Sepse për të gjetur Mike Smith në një telefon Libri i faqeve n, në rastin më të keq, 1116 00:39:50,680 --> 00:39:52,422 mund të marrë mua n hapa. 1117 00:39:52,422 --> 00:39:53,630 Po në lidhje me marrjen frekuentimin? 1118 00:39:53,630 --> 00:39:55,790 Një dy tre Katër Pesë Gjashtë. 1119 00:39:55,790 --> 00:39:59,420 Çfarë është koha drejtimin e kësaj algorithm për të marrë frekuentimin? 1120 00:39:59,420 --> 00:40:03,070 Big O i n, sepse në teori unë duhet të theksoj gjithë në dhomë. 1121 00:40:03,070 --> 00:40:05,861 >> Tani si një mënjanë, çka në lidhje me optimization të tjera nga java zero? 1122 00:40:05,861 --> 00:40:08,117 Dy, katër, gjashtë, tetë, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Një shkencëtar kompjuteri do realizuar, prit një minutë, 1124 00:40:10,200 --> 00:40:12,320 që është në rendin e n ndarë nga dy hapa. 1125 00:40:12,320 --> 00:40:12,820 E drejtë? 1126 00:40:12,820 --> 00:40:14,444 Sepse unë jam duke bërë dy njerëz në një kohë. 1127 00:40:14,444 --> 00:40:17,015 Por ne jemi duke shkuar për të injorojë këto terma më të ulëta rendit, 1128 00:40:17,015 --> 00:40:19,140 dhe ne jemi vetëm duke shkuar për të hedhin larg ndarjen me 2, 1129 00:40:19,140 --> 00:40:21,830 dhe vetëm thonë, O i madh i n për këtë algorithm, si dhe. 1130 00:40:21,830 --> 00:40:22,760 >> Po në lidhje me këtë? 1131 00:40:22,760 --> 00:40:26,170 Ne do të kaloni mbi disa nga këto, por ajo që ishte një algoritmi që ishte log n? 1132 00:40:26,170 --> 00:40:29,900 Që mori afërsisht hyni hapa n? 1133 00:40:29,900 --> 00:40:30,870 Ndarja dhe sundo. 1134 00:40:30,870 --> 00:40:31,369 Pikërisht. 1135 00:40:31,369 --> 00:40:33,900 Ashtu si shembull librin e telefonit në Javën zero dhe më herët sot, 1136 00:40:33,900 --> 00:40:36,191 ku kemi ndarë problemin përsëri dhe përsëri dhe përsëri. 1137 00:40:36,191 --> 00:40:39,070 Ne tërhoqi atë në bord në javë zero si një linjë të lakuar të gjelbër, 1138 00:40:39,070 --> 00:40:41,460 dhe kemi thënë atë ditë ishte një algoritmi logaritmike. 1139 00:40:41,460 --> 00:40:44,970 >> Dhe me të vërtetë, numri i hapat që merr për të kryer ndarjen dhe të pushtuar, 1140 00:40:44,970 --> 00:40:48,610 ose kërko binar si ne do të fillojmë duke e quajtur atë, si në librin e telefonit, 1141 00:40:48,610 --> 00:40:50,680 është në rendin e log dhe hapat. 1142 00:40:50,680 --> 00:40:52,470 Dhe kjo është pak e një të pazakontë. 1143 00:40:52,470 --> 00:40:54,910 >> Çfarë merr një hap, ose më saktë 1144 00:40:54,910 --> 00:40:56,240 një numër i vazhdueshëm i hapave? 1145 00:40:56,240 --> 00:40:58,865 Ndoshta kjo është dy, ndoshta kjo është tre, por një shkencëtar kompjuteri vetëm 1146 00:40:58,865 --> 00:41:01,423 thjeshton atë si O e madhe e 1, disa numër konstant prej hapave. 1147 00:41:01,423 --> 00:41:04,256 Çfarë është diçka që ju mund të bëni atë merr një numër të vazhdueshëm të hapave? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Çfarë është koha drejtimin e duartrokitje? 1150 00:41:10,930 --> 00:41:11,920 Kohë konstante. 1151 00:41:11,920 --> 00:41:12,420 E drejtë? 1152 00:41:12,420 --> 00:41:15,490 Si, çfarë është koha drejtimin e bërë ndonjë gjë që merr vetëm një 1153 00:41:15,490 --> 00:41:18,570 operacion, si të shtypura F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Kjo mund të thuhet të jetë kohë konstante, nëse rast më pak nga këndi me të shtypura F, 1155 00:41:24,110 --> 00:41:28,260 çfarë mund të kohën running e shtypura F jetë në fakt? 1156 00:41:28,260 --> 00:41:28,790 Dhe pse? 1157 00:41:28,790 --> 00:41:30,550 Çfarë është n matëse në këtë rast? 1158 00:41:30,550 --> 00:41:32,251 >> Audienca: [padëgjueshme]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. Malan: Pikërisht. 1160 00:41:33,250 --> 00:41:34,900 Numri i karaktereve ne duam të shtypura. 1161 00:41:34,900 --> 00:41:36,191 Pra, kjo është shumë e context-sensitive. 1162 00:41:36,191 --> 00:41:39,910 Sot, ne kemi qenë duke u përqëndruar shumë në shkronja dhe numra këtu në bord. 1163 00:41:39,910 --> 00:41:43,540 Por ajo mund të jetë edhe karaktere në një varg aktuale. 1164 00:41:43,540 --> 00:41:46,420 Pra, ajo rezulton atje është një tjetër masë që do të fillojë të kujdeseni për, 1165 00:41:46,420 --> 00:41:48,530 dhe kjo është e kundërta O i madh, kështu që të flasin. 1166 00:41:48,530 --> 00:41:50,120 >> Kjo është simbol omega. 1167 00:41:50,120 --> 00:41:53,380 Ndërsa O i madh do të thotë se çfarë së, sipërme të detyruar në kohën tuaj running? 1168 00:41:53,380 --> 00:41:55,580 Maksimalisht, sa kohë mund të marrë diçka? 1169 00:41:55,580 --> 00:41:59,250 Omega-- keq kjo mban të vijnë up-- është e kundërta e kësaj, 1170 00:41:59,250 --> 00:42:02,960 ku kjo është një më të ulët i lidhur nga Sasinë e kohës që diçka mund të marrë. 1171 00:42:02,960 --> 00:42:10,480 >> Kështu që. për shembull, çfarë është një algoritmi që merr hapa gjithmonë ne katror n? 1172 00:42:10,480 --> 00:42:15,600 E pra, një nga algoritme kemi parë sot, në fakt, mund të jetë se si. 1173 00:42:15,600 --> 00:42:16,720 Përzgjedhja lloj. 1174 00:42:16,720 --> 00:42:18,270 Përzgjedhja lloj është goxha budalla. 1175 00:42:18,270 --> 00:42:21,760 Edhe nëse algorithm-- keq, madje edhe nëse array është renditur tashmë, 1176 00:42:21,760 --> 00:42:24,150 Zgjedhja lloj do të mbajtur ecur nëpër lista 1177 00:42:24,150 --> 00:42:28,907 për t'u siguruar se e ka më të vogël element përsëri dhe përsëri dhe përsëri. 1178 00:42:28,907 --> 00:42:31,740 Dhe, edhe pse ju njerëzit i në Audienca e di se, prit një minutë, 1179 00:42:31,740 --> 00:42:33,948 ju tashmë e kaluar Elementi më i vogël, kompjuteri 1180 00:42:33,948 --> 00:42:37,300 nuk e di se deri sa ajo duket të gjithë rrugën nëpër lista. 1181 00:42:37,300 --> 00:42:40,240 Në mënyrë të ngjashme, një ulët i detyruar që gjithashtu mund të merren parasysh 1182 00:42:40,240 --> 00:42:42,000 mund të jetë koha lineare. 1183 00:42:42,000 --> 00:42:48,260 >> Sa kohë nuk është marrë për Elementet lloj n në të mirë 1184 00:42:48,260 --> 00:42:52,420 rast duke përdorur diçka si flluskë lloj? 1185 00:42:52,420 --> 00:42:54,280 Supozoni se lista juaj është renditur tashmë. 1186 00:42:54,280 --> 00:42:56,696 Ne i thamë flluskë lloj merr rendi i n katror hapa. 1187 00:42:56,696 --> 00:42:59,640 Por, çfarë nëse ajo është renditur tashmë? 1188 00:42:59,640 --> 00:43:02,310 Çfarë nëse ti e kupton pas një të kalojë nëpër rrjet 1189 00:43:02,310 --> 00:43:03,540 që ju keni bërë asnjë këmbime? 1190 00:43:03,540 --> 00:43:05,970 A ju duhet të mbani të bërë më shumë kalon? 1191 00:43:05,970 --> 00:43:06,470 >> Jo. 1192 00:43:06,470 --> 00:43:10,340 Pra, një i lidhur në flluskë lloji më i ulët mund të thuhet të jetë linear. 1193 00:43:10,340 --> 00:43:11,830 Omega e n. 1194 00:43:11,830 --> 00:43:14,450 Dhe ne mund të shohim në të tjerët e tyre si edhe. 1195 00:43:14,450 --> 00:43:17,990 Pra, le të marrin një vështrim të shpejtë në vetëm një vizualizimi këtu 1196 00:43:17,990 --> 00:43:20,790 për të parë se si këto dallojnë veten e tyre. 1197 00:43:20,790 --> 00:43:24,592 Unë jam duke shkuar për të shkuar poshtë këtu në këtë faqe që është në dispozicion në faqen e internetit C50-së, 1198 00:43:24,592 --> 00:43:27,550 por ajo do të jetë një dhimbje për të marrë të punës, pasi që ai përdor një teknologji të quajtur 1199 00:43:27,550 --> 00:43:30,560 Java applets, e cila është një kryesisht pambështetur këto ditë, 1200 00:43:30,560 --> 00:43:32,730 të paktën nga Chrome dhe disa të tjerë. 1201 00:43:32,730 --> 00:43:37,070 >> Dhe më lejoni të shkoj përpara dhe të shpejtuar këtë dhe të shpjegojë se çfarë po ndodh. 1202 00:43:37,070 --> 00:43:40,840 Ky është demonstrim i flluskë lloj, algorithm parë kemi shikuar. 1203 00:43:40,840 --> 00:43:43,950 Dhe kjo është një vizualizimi në që çdo nga këto bare përfaqëson një numër. 1204 00:43:43,950 --> 00:43:45,710 Sa më i madh bar, aq më i madh numri. 1205 00:43:45,710 --> 00:43:47,520 Sa më e vogël bar, aq më i vogël numri. 1206 00:43:47,520 --> 00:43:50,353 Dhe çfarë ju mund të shihni me sy, madje edhe edhe pse kjo po ndodh super të shpejtë, 1207 00:43:50,353 --> 00:43:53,699 është se bar i kuq është si unë, duke ecur mbrapa dhe me radhë fiksimin e problemeve. 1208 00:43:53,699 --> 00:43:56,740 Ju mund të shihni se elementet më të mëdha janë me të vërtetë bubbling deri në të djathtë, 1209 00:43:56,740 --> 00:43:59,650 dhe elementet më të vogla janë bubbling deri në të majtë. 1210 00:43:59,650 --> 00:44:01,870 Dhe këtu poshtë, në qoftë se ne në fakt shohim më nga afër, 1211 00:44:01,870 --> 00:44:04,330 ne fakt mund të llogarisë Numri i krahasimeve dhe këmbime 1212 00:44:04,330 --> 00:44:05,350 se janë duke u bërë. 1213 00:44:05,350 --> 00:44:07,360 >> Por në vend, le të shohim ne algoritmin e dytë 1214 00:44:07,360 --> 00:44:11,240 kemi shikuar më herët me tonë vullnetarë, përzgjedhja lloji. 1215 00:44:11,240 --> 00:44:13,500 Vizualisht, ajo ka një efekt shumë të ndryshme. 1216 00:44:13,500 --> 00:44:16,820 Por kjo është, përsëri, shumë intuitiv, në që ne të zbatojmë zgjedhjen e ardhshme të vogël 1217 00:44:16,820 --> 00:44:18,660 element, dhe kemi marrë një pak fat. 1218 00:44:18,660 --> 00:44:20,110 Se ndjerë rrënjësisht të shpejtë. 1219 00:44:20,110 --> 00:44:22,840 Por nëse ne u këtë përsëri dhe përsëri dhe përsëri me shumë inputeve, 1220 00:44:22,840 --> 00:44:26,680 ne do të shohim se kjo është me të vërtetë ende në O madh të n katror. 1221 00:44:26,680 --> 00:44:29,920 >> Le të bëjmë një një të fundit këtu, futje lloj, 1222 00:44:29,920 --> 00:44:33,180 e cila ishte algoritmi i tretë ne shikuar në, dhe risjell 1223 00:44:33,180 --> 00:44:36,700 se kjo ka të bëjë me elemente si ajo ballafaqohet me to, 1224 00:44:36,700 --> 00:44:39,290 por pastaj ajo ndoshta ndërrime gjëra mbi të bëjë vend, 1225 00:44:39,290 --> 00:44:41,660 futur elemente ku ata i përkasin. 1226 00:44:41,660 --> 00:44:45,330 >> Dhe kjo edhe përfundon duke i dhënë Rezultati përfundimtar. Tani të tre të atyre 1227 00:44:45,330 --> 00:44:46,490 ndjerë shumë shpejt. 1228 00:44:46,490 --> 00:44:48,740 Dhe me të vërtetë, unë u zhvillua ato në një clip mjaft të mirë. 1229 00:44:48,740 --> 00:44:52,510 Por në thelb, ata janë të gjithë goxha e tmerrshme, të jetë i sinqertë. 1230 00:44:52,510 --> 00:44:56,960 Të gjitha këto algoritme deri tani që të kandidojë në O madh të n katror 1231 00:44:56,960 --> 00:44:59,270 të marrë mjaft e kohë për të kandiduar në fund. 1232 00:44:59,270 --> 00:45:01,920 >> Dhe me të vërtetë, ne mund të shohim dhe të ndjehen kjo së fundi 1233 00:45:01,920 --> 00:45:04,090 në qoftë se unë tërheq lart këtë demo tretë dhe të fundit. 1234 00:45:04,090 --> 00:45:05,840 Ky është një tjetër vizualizimi që po ndodh 1235 00:45:05,840 --> 00:45:08,500 për të treguar flluskë lloj në të majtë, lloj përzgjedhje në mes, 1236 00:45:08,500 --> 00:45:13,410 dhe diçka, si një nga tonë dore ngre sugjeruar më herët, 1237 00:45:13,410 --> 00:45:15,020 bashkojë lloj në të djathtë. 1238 00:45:15,020 --> 00:45:16,937 Një ndarje dhe sundo strategji në të djathtë. 1239 00:45:16,937 --> 00:45:19,520 Dhe kjo është, në fakt, ajo që ne jemi do të shikojmë në të mërkurën. 1240 00:45:19,520 --> 00:45:21,990 Por le të kohës këto për të kandiduar në mënyrë paralele. 1241 00:45:21,990 --> 00:45:26,765 Kjo është afërsisht i njëjtë numri i të elementë, të gjithë drejtimin në të njëjtën kohë. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble lloj vs përzgjedhjes lloj vs merge lloji. 1244 00:45:34,440 --> 00:45:36,760 >> Tani, ata janë të gjithë duke teorikisht në të njëjtën kohë. 1245 00:45:36,760 --> 00:45:39,830 CPU është në drejtimin të njëjtën shpejtësi, por ju 1246 00:45:39,830 --> 00:45:44,014 mund të ndjehen si i mërzitshëm ky është shumë shpejt do të bëhet, 1247 00:45:44,014 --> 00:45:45,930 dhe se sa shpejt kur ne injektuar një grimë e javës 1248 00:45:45,930 --> 00:45:49,330 Algoritme ZERO-së mund ne të shpejtojë gjërat. 1249 00:45:49,330 --> 00:45:51,760 >> Dhe tani le të krahasojmë këto në një formë fundit. 1250 00:45:51,760 --> 00:45:55,710 Unë jam duke shkuar për të shkuar përpara në faqen e internetit CS50, ku 1251 00:45:55,710 --> 00:45:59,020 ne kemi këtë link përfundimtare për sot, ku dikush në internet 1252 00:45:59,020 --> 00:46:03,960 mirësi të vënë së bashku një video që kap Çfarë klasifikim të ndryshëm 1253 00:46:03,960 --> 00:46:07,510 algoritme të tingëllojë si. 1254 00:46:07,510 --> 00:46:09,577 Kjo është lloj futje. 1255 00:46:09,577 --> 00:46:12,072 >> [Beeping] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Ku ju jeni duke aplikuar një frekuencë bazuar në lartësinë e bar bar. 1258 00:46:16,850 --> 00:46:19,826 Kjo është flluskë lloj. 1259 00:46:19,826 --> 00:46:21,822 >> [Deformuar beeping] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Vjen deri ardhshme is-- vjen up tjetër lloj is-- përzgjedhjes, 1262 00:46:45,774 --> 00:46:48,820 ku përsëri, ne jemi duke zgjedhur element tjetër i vogël, 1263 00:46:48,820 --> 00:46:51,820 dhe ne mund të shohim atë në rritje nga e majta në të djathtë. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Merge lloj, fitues ynë deri më tani sot. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Vini re se si është e ndarë gjërat në [padëgjueshme] gjysmë dhe lagjet. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Lloj gnome, të cilat ne nuk kemi biseduar rreth, dhe krijon vizualisht 1270 00:47:21,660 --> 00:47:24,450 dhe audally një grimë e një formë të ndryshme dhe të shëndoshë. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Kthim prapa dhe me radhë, pastrimin gjërat. 1273 00:47:30,160 --> 00:47:32,230 Gjithashtu shikoni heapsort në faqen e internetit këtë djalë. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Dhe kjo është ajo. 1276 00:47:36,810 --> 00:47:38,210 Ne do të ju shohim herën tjetër. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing DHE MUZIKA] 1279 00:47:48,334 --> 00:50:24,839