1 00:00:00,000 --> 00:00:11,100 >> [Duke luajtur muzikë] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. Malan: Të gjitha e drejtë. 3 00:00:11,490 --> 00:00:12,170 Pra, të mirëpritur mbrapa. 4 00:00:12,170 --> 00:00:15,180 Kjo është CS50, dhe eshte fundi i javës së tre. 5 00:00:15,180 --> 00:00:17,770 >> Pra, kujtojnë në disa javëve të fundit, ne kemi qenë të shpenzimeve mjaft e 6 00:00:17,770 --> 00:00:20,820 Ora në C, për programimin, në sintaksë. 7 00:00:20,820 --> 00:00:24,680 Dhe kjo është krejt normale, në qoftë se ju jeni ende luftuar me Set Problem 2, të jetë 8 00:00:24,680 --> 00:00:25,950 banging kokën tuaj kundër murit. 9 00:00:25,950 --> 00:00:28,310 Është e fshehtë-looking mesazhet e gabimit dhe të mete që ju të 10 00:00:28,310 --> 00:00:29,220 nuk mund të mjaft të ndjekur poshtë. 11 00:00:29,220 --> 00:00:32,310 Sepse, pjesa tjetër e siguroi, se në vetëm një Ora javësh 'ju do të shikojnë prapa në 12 00:00:32,310 --> 00:00:35,930 gjëra të tilla si Cezarit, dhe [? V-genair,?] ndoshta edhe Crack, dhe 13 00:00:35,930 --> 00:00:40,050 të kuptojë se sa larg ju keni ardhur në një periudhë të shkurtër kohe. 14 00:00:40,050 --> 00:00:43,670 Pra, nëse kjo është ndonjë ngushëllim, ul receptorin e telefonit në atje tani për tani. 15 00:00:43,670 --> 00:00:46,610 >> Sot, edhe pse, ne fillojmë të tranzicionit për gjëra të nivelit të lartë. 16 00:00:46,610 --> 00:00:49,820 Dhe ne të fillojë të marrë për të dhënë se ju djema e di se si të programit, ose në 17 00:00:49,820 --> 00:00:52,090 pak fillimet e se niveli i rehati. 18 00:00:52,090 --> 00:00:56,520 Dhe ne do të fillojnë të marrin në konsideratë se si ne mundemi shkoni në lidhje me dizajnimin e programeve të më shumë 19 00:00:56,520 --> 00:00:57,440 në mënyrë efektive. 20 00:00:57,440 --> 00:01:01,090 Si ne mund të shkoni në lidhje me optimizmin efikasiteti i algoritmeve tanë, dhe të 21 00:01:01,090 --> 00:01:03,110 përgjithësisht zgjidhjen më shumë probleme interesante e. 22 00:01:03,110 --> 00:01:06,850 Dhe duke filluar për të marrë për të dhënë që, nëse ne të kërkuar për të, ne mund të kodojnë up çdo 23 00:01:06,850 --> 00:01:08,350 nga shembujt që kemi në mendje. 24 00:01:08,350 --> 00:01:11,430 Kështu që sot, ne nuk prek tastierën për çdo formë të kodit. 25 00:01:11,430 --> 00:01:15,150 Ajo do të jetë niveli shumë më të larta, dhe në fund të fundit, rreth zgjidhja e problemit-. 26 00:01:15,150 --> 00:01:20,490 >> Pra, për të marrë në këtë pikë, më lejoni të propozojnë se shtatë vijim 27 00:01:20,490 --> 00:01:24,290 rectangles përfaqësojnë shtatë dyer, prapa të cilat janë një bandë e tërë e 28 00:01:24,290 --> 00:01:26,340 Numrat, ndër të cilat është numri 50. 29 00:01:26,340 --> 00:01:30,470 Më lejoni të projektojë këtë on kjo ekran si edhe këtu. 30 00:01:30,470 --> 00:01:36,770 Dhe propozoj që ne kemi nevojë për vullnetar për ndihmojë të gjeni më një numër në frontin e 31 00:01:36,770 --> 00:01:38,140 Internet këtu për të parë. 32 00:01:38,140 --> 00:01:40,755 Vijnë më lart, në rozë. 33 00:01:40,755 --> 00:01:43,050 Dakord. 34 00:01:43,050 --> 00:01:43,930 Cili është emri juaj? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [e padëgjueshme] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. Malan: Na vjen keq? 37 00:01:45,170 --> 00:01:45,860 >> JENNIFER: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> DAVID J. Malan: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Të gjithë të drejtë, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Gëzohem që u njohëm. 41 00:01:47,630 --> 00:01:48,370 Come on up. 42 00:01:48,370 --> 00:01:52,430 Pra, këto këtu janë shtatë dyer, dhe çfarë Unë do të doja që ju të bëni për ne këtu, 43 00:01:52,430 --> 00:01:56,560 në frontin e të gjithë shokëve të tu, po na gjeni numrin, 50. 44 00:01:56,560 --> 00:02:00,860 Për të gjetur një numër, mundeni vjedhurazi prapa ndonjë nga këto dyer nga thjesht përgjimi 45 00:02:00,860 --> 00:02:03,030 mbi njërën nga dyert, dhe IT do të zbulojë numrin e saj. 46 00:02:03,030 --> 00:02:06,080 Dhe le të shohim se si shpejt ju mund të na gjeni numrin, 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Nicely done. 54 00:02:17,350 --> 00:02:18,040 Dakord. 55 00:02:18,040 --> 00:02:19,906 Raund i duartrokitje për Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Duartrokitje] 57 00:02:21,530 --> 00:02:22,320 >> Dakord. 58 00:02:22,320 --> 00:02:25,254 Pra, çfarë ishte e strategjia juaj për të gjetur numrin, 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Um, mendova se ndoshta në qoftë se - 60 00:02:27,222 --> 00:02:27,714 [Padëgjueshme] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. Malan: Oh. 62 00:02:28,206 --> 00:02:29,630 Give it një sekondë. 63 00:02:29,630 --> 00:02:32,420 Pra, ishte strategjia juaj për të gjetur numrin, 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Kështu që unë vetëm të fillojë në duke filluar për të parë se çfarë numri i parë 65 00:02:34,760 --> 00:02:38,590 ishte, dhe pastaj mendova, ndoshta në qoftë se ata janë të renditura, unë vetëm do të mbajë 66 00:02:38,590 --> 00:02:39,970 përgjimi larta deri? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. Malan: OK. 68 00:02:40,140 --> 00:02:42,910 Dhe ne duket se kanë gjetur që të jetë rasti. 69 00:02:42,910 --> 00:02:45,670 Edhe pse, le të zhvishem përsëri shtresa vetëm pak, dhe ju doni të shkoni 70 00:02:45,670 --> 00:02:47,640 përpara dhe të zbulojë dyert e tjera ju mund të keni zgjedhur? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Oh, i dashur. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. Malan: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Kështu që unë vetëm mori me fat. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. Malan: Pra, ju mori me fat. 76 00:02:55,270 --> 00:02:55,710 Dakord. 77 00:02:55,710 --> 00:02:56,795 Pra, jo i keq. 78 00:02:56,795 --> 00:02:58,750 Por kjo është një interesante Insajt, e drejtë? 79 00:02:58,750 --> 00:03:01,870 Nëse keni supozuar, dhe ju e bëri të marrë, në të vërtetë, pak fat atje. 80 00:03:01,870 --> 00:03:05,350 Por nëse ju supozohet se numrat e ishin të renditura, ju mund të jenë më të saktë 81 00:03:05,350 --> 00:03:08,750 se si që ndikoi sjellja juaj? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Pra, në qoftë se ata ishin të renditura, unë menduar ndoshta më i vogli tek më i madhi. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. Malan: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: Ose në qoftë se kjo përfundoi duke qenë me të vërtetë e madhe, atëherë më e madhe për të vogël. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. Malan: OK. 86 00:03:15,540 --> 00:03:18,170 Pra, më i madh për të vogël, ose vogli tek më i madhi. 87 00:03:18,170 --> 00:03:21,990 Por më lejoni të të propozojë, supozoj keni pasur gotten pafat, dhe mendoj se ata 88 00:03:21,990 --> 00:03:26,840 nuk ishin, në fakt, të renditura, sa i ato dyert mund të keni pasur për peek 89 00:03:26,840 --> 00:03:28,590 prapa në këtë rast më të keq? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Të gjitha prej tyre. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. Malan: Të gjitha prej tyre. 92 00:03:30,420 --> 00:03:31,740 Pra, le të përgjithësoj se si n. 93 00:03:31,740 --> 00:03:34,790 Nuk ndodh të jetë 7, por le të më në përgjithësi thonë se ka dyert n në 94 00:03:34,790 --> 00:03:35,650 Ekran këtu. 95 00:03:35,650 --> 00:03:40,110 Pra, në rastin më të keq, ju do të keni të shikojmë prapa 7 dyert, ose dyert n. 96 00:03:40,110 --> 00:03:44,140 Dhe kështu kjo është me të vërtetë, kjo është pak e fat sot, por kjo është me të vërtetë një lineare 97 00:03:44,140 --> 00:03:46,440 algoritmi i terezi, edhe pse ju ishin lloj i skipping rreth. 98 00:03:46,440 --> 00:03:47,080 A është kjo e drejtë? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Po. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. Malan: E pra, më lejoni të shohim në qoftë se juaj Ndryshimet strategji në qoftë se unë të na për të 101 00:03:50,000 --> 00:03:52,190 Shembulli ynë i dytë këtu me 7 dyer të ndryshme. 102 00:03:52,190 --> 00:03:55,240 Numrat e njëjtë, por kjo herë që ata janë të renditura. 103 00:03:55,240 --> 00:03:58,350 Cila është strategjia juaj këtu do të jetë, duke u përpjekur për të vënë nga mendjen tuaj se çfarë 104 00:03:58,350 --> 00:03:59,310 numrat e tjerë ishin - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. Malan: - më herët? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Le të fillojë me një të parë. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. Malan: Të gjithë të drejtë. 109 00:04:03,540 --> 00:04:05,190 Fillojnë me një të parë. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Tani ku ju do të shkoni, dhe pse? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 është me të vërtetë i vogël. 113 00:04:10,040 --> 00:04:12,500 Pra, nëse ata janë lloj ndoshta më të vogël të madhe, ajo duhet 114 00:04:12,500 --> 00:04:13,290 jenë dy herë se, dhe -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. Malan: OK. 116 00:04:13,670 --> 00:04:15,990 Le të shohim, të cilat ju mendoni se? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Provoni i fundit. 118 00:04:19,050 --> 00:04:19,500 Gëzohem. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. Malan: Shumë bukur bërë. 120 00:04:20,880 --> 00:04:21,860 Dakord. 121 00:04:21,860 --> 00:04:23,010 >> [Duartrokitje] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. Malan: OK. 123 00:04:24,310 --> 00:04:26,790 Pra, ju jeni në të vërtetë duke bërë këtë tmerrshëm, sepse ju jeni 124 00:04:26,790 --> 00:04:27,700 bërë atë shumë mirë. 125 00:04:27,700 --> 00:04:31,150 Cili na lë në gjendje të të bëjë pika të caktuara. 126 00:04:31,150 --> 00:04:32,565 Pra, le të përpiqemi të rrokulliset prapa këtu. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. Malan: Shumë mirë bërë, megjithatë. 129 00:04:35,980 --> 00:04:39,060 Pra, ju keni filluar në fillim, ju e pa se kjo ishte 4, atëherë ju 130 00:04:39,060 --> 00:04:40,240 u zhvendos në fund. 131 00:04:40,240 --> 00:04:42,320 Por mendoj që ju nuk e merrni me fat atje, dhe mendoj 50 132 00:04:42,320 --> 00:04:42,890 ishte diku tjetër. 133 00:04:42,890 --> 00:04:46,190 Çfarë hapi juaj i tretë kanë qenë? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Kthehu në fillim. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. Malan: Kthehu mbrapa te fillimit. 136 00:04:48,320 --> 00:04:51,320 OK, kështu që ju do të kemi preku kjo derë, e cila ishte 8. 137 00:04:51,320 --> 00:04:51,660 Dakord. 138 00:04:51,660 --> 00:04:52,650 Kështu që nuk është 50. 139 00:04:52,650 --> 00:04:55,380 Ku do keni shikuar ardhshme? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Nëse unë nuk e bëri e di se ata renditura. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. Malan: korrekte. 142 00:04:57,005 --> 00:04:58,490 E pra, nëse ju nuk e dini ata ishin të renditura - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Oh, nuk e di, vërtet. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. Malan: - por ju nuk e keni e di ku 50 ishte ende? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Vetëm mbani shkuar. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. Malan: Të gjithë të drejtë. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Mbani shkuar. 149 00:05:03,800 --> 00:05:05,270 OK, se unë mund të punojnë me të. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. Malan: Tani, në qoftë se ju jeni vetëm duke shkuar për të do të mbajë, çfarë është tuaj 152 00:05:07,210 --> 00:05:09,680 algorithm delegimin mbështetur në. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: lineare -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. Malan: Kjo është lloj i linear. 155 00:05:11,820 --> 00:05:13,480 Por më lejoni të propozojnë, le të mua vënë në vend. 156 00:05:13,480 --> 00:05:14,900 Më lejoni të rifreskoni faqen. 157 00:05:14,900 --> 00:05:17,120 numër të njëjtë, rregullim të njëjtë, dyert e njëjta. 158 00:05:17,120 --> 00:05:21,350 Por mendoj se prapa në atë ditë të parë në klasë kur ne grisi një libër telefoni në 159 00:05:21,350 --> 00:05:25,480 , gjysma lloj, dhe çfarë ishte strategjia jonë atje? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Filloni në mes. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. Malan: OK. 162 00:05:26,690 --> 00:05:27,610 Pra, fillojë në mes. 163 00:05:27,610 --> 00:05:28,790 Pra, le të shkojnë përpara dhe simulojnë se. 164 00:05:28,790 --> 00:05:30,720 Të fillojë në mesin e fushës nga zbuluar atë derë. 165 00:05:30,720 --> 00:05:31,660 Pra, numri 16. 166 00:05:31,660 --> 00:05:35,290 Pra, çfarë do të djalë të fortë kanë bërë, i cili shqeu librin e telefonit në gjysmë, 167 00:05:35,290 --> 00:05:38,450 për të shkuar në mend të ardhshëm? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Shkoni në këtë gjysmë. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. Malan: Dhe pse në të djathtë? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Në qoftë se ata ishin lloj i vogël të madh, atëherë 50 duhet të jetë 171 00:05:43,900 --> 00:05:44,720 në atë fund. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. Malan: Mirë. 173 00:05:44,920 --> 00:05:45,390 Totally të arsyeshme. 174 00:05:45,390 --> 00:05:48,380 Pra, si një libër telefoni, ju shkoni në e drejta në krahasim me të majtë, por këtu 175 00:05:48,380 --> 00:05:49,500 eshte takeaway çelësi. 176 00:05:49,500 --> 00:05:53,930 Ju tani mund të hedhin larg, ose shkëput, gjysma e këtij problemi, duke mos ju 177 00:05:53,930 --> 00:05:55,970 me 7 dyer, por me të vërtetë me vetëm 3. 178 00:05:55,970 --> 00:05:57,870 Cili është afërsisht gjysma e madhësia e problemit. 179 00:05:57,870 --> 00:05:58,350 Dakord. 180 00:05:58,350 --> 00:06:01,890 Kështu që tani se çfarë ju do të keni bëhet pasi ju shkoni e drejtë? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Pra, 16 është ende mjaft i vogël, relative në 50, kështu që ndoshta unë do të përpiqemi, 182 00:06:05,870 --> 00:06:06,700 si, ky. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. Malan: Të gjithë të drejtë. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Të gjithë të drejtë, kështu që tani se çfarë është tuaj Instinkti ju thënë? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Unë mund të hedhin larg këtë dhe pastaj vetëm - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. Malan: OK. 188 00:06:12,360 --> 00:06:14,212 Mirë, ju mund të hedhin larg gjysma e majtë atje. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - marr këtë një të tillë. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. Malan: Dhe drejtë. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Po. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. Malan: Pra, edhe pse kjo është e vështirë për të parë ndoshta, kur ka vetëm 193 00:06:17,820 --> 00:06:21,320 7 dyert, mendoni rreth, tani, qëndrueshmëri e 194 00:06:21,320 --> 00:06:22,620 algoritëm ju vetëm aplikuar. 195 00:06:22,620 --> 00:06:24,510 Në rastin e mëparshëm, ju e bëri merrni me fat, e cila ishte e madhe. 196 00:06:24,510 --> 00:06:26,540 Por ju bëri përdorni një orientues, Unë do të thoja. 197 00:06:26,540 --> 00:06:29,150 Keni përdorur lloj instinktet tuaja, dhe ditur se renditura, në qoftë se kjo është goxha 198 00:06:29,150 --> 00:06:31,600 të vogla në fillim, natyrisht, ne kemi mori për të shkojnë më shumë në të djathtë. 199 00:06:31,600 --> 00:06:34,990 Por në një farë mënyre, keni fat, për shkak se ndoshta kjo ishte Numri 100, 200 00:06:34,990 --> 00:06:36,220 dhe ndoshta 50 ishte më në mes. 201 00:06:36,220 --> 00:06:37,910 Ndoshta 50 ishte madje edhe mbi këtu. 202 00:06:37,910 --> 00:06:40,960 >> Por çfarë keni bërë pak ndryshe kjo ishte koha, që ju bëri të njëjtën gjë 203 00:06:40,960 --> 00:06:42,150 përsëri dhe përsëri. 204 00:06:42,150 --> 00:06:45,310 Dhe unë do të argumentojnë se ajo që ju vetëm ka, megjithëse ndikuar nga telefoni 205 00:06:45,310 --> 00:06:48,100 libër shembull, është diçka shumë më e më shumë algorithmic, dhe shumë 206 00:06:48,100 --> 00:06:49,930 më pak të veçantë cased. 207 00:06:49,930 --> 00:06:51,620 Shumë më pak instiktiv. 208 00:06:51,620 --> 00:06:57,160 Pra, në fund të ditës, si do ju përshkruani efikasitetin e 209 00:06:57,160 --> 00:07:00,530 algorithm e parë, ku ju shkoi majta në të djathtë, kundrejt 210 00:07:00,530 --> 00:07:03,430 Algoritmi i dytë këtu? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: Kjo duhet, si, ndoshta përgjysmon kohën, ose edhe më shumë, vërtet. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. Malan: OK, ndoshta edhe më shumë. 213 00:07:07,320 --> 00:07:10,150 Le të shtyjë një pak më e vështirë në atë. 214 00:07:10,150 --> 00:07:13,030 Çfarë me të vërtetë, në qoftë se ne vazhdojmë këtë Logjika, ne patjetër përgjysmuar 215 00:07:13,030 --> 00:07:15,830 running kohë me këtë algoritëm të dytë duke hedhur larg gjysmën e 216 00:07:15,830 --> 00:07:18,470 Numrat, por çfarë ka të bëjmë më tej përsëritje, kur Jennifer zbuloi 217 00:07:18,470 --> 00:07:20,615 numri i dytë? 218 00:07:20,615 --> 00:07:22,830 >> Ne përgjysmuar numrin e dyerve përsëri. 219 00:07:22,830 --> 00:07:25,270 Dhe pastaj çfarë bëri bëjmë pas kësaj, në qoftë se ka pasur dyert më shumë për të luajtur me? 220 00:07:25,270 --> 00:07:27,520 Ne do të përgjysmojë ato, dhe përsëri, dhe përsëri, dhe përsëri. 221 00:07:27,520 --> 00:07:30,420 Dhe kjo ishte vetëm si ju djema të gjithë këmbë deri në javë pare te 222 00:07:30,420 --> 00:07:33,000 , klasa gjysma e keni ulur poshtë, gjysma i keni ulur poshtë, gjysma prej jush 223 00:07:33,000 --> 00:07:35,440 ulur, derisa një i vetmuar shpirti ishte në këmbë. 224 00:07:35,440 --> 00:07:39,050 Dhe ne i thamë se koha drejtimin e se, numri i hapave ajo mori ishte 225 00:07:39,050 --> 00:07:40,430 me urdhër të kujt? 226 00:07:40,430 --> 00:07:41,230 >> Kryetari 1: [padëgjueshme] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. Malan: Pra, baza log 2 n, ose thjesht më thjesht, hyni nga n. 228 00:07:43,970 --> 00:07:45,060 Pra, diçka logaritmike. 229 00:07:45,060 --> 00:07:48,380 Dhe grafiku nuk ishte një vijë e drejtë që mori vetëm keq e më keq, ajo ishte 230 00:07:48,380 --> 00:07:52,490 kjo kurba interesante që nuk e bëri merrni aq keq me kalimin e kohës. 231 00:07:52,490 --> 00:07:53,910 Pra, le të mbajë më në këtë ide. 232 00:07:53,910 --> 00:07:54,690 Le të thank Jennifer. 233 00:07:54,690 --> 00:07:56,150 Thanks so much për të ardhur në dorë. 234 00:07:56,150 --> 00:07:57,400 Dhe, një sec. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Asnjë llambat tavolinë sot, por ne keni CS50 topa stresit. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. Malan: Të gjithë të drejtë, këtu. 239 00:08:04,410 --> 00:08:06,545 Faleminderit për shkaktohen stresi deri këtu. 240 00:08:06,545 --> 00:08:07,350 Dakord. 241 00:08:07,350 --> 00:08:10,620 Pra, le të shohim nëse mundemi jo tani formalizojë këtë një pak më shumë. 242 00:08:10,620 --> 00:08:14,820 Pra, përsëri, ajo që ne vetëm e bëri ishte në thelb e njëjta gjë si ne e bëmë 243 00:08:14,820 --> 00:08:16,660 në atë jave pare. 244 00:08:16,660 --> 00:08:23,780 Por në vend se fundi me vetëm një lineare algorithm, të cilat ne përshkruar 245 00:08:23,780 --> 00:08:27,210 më parë si këtë vijë të drejtë, ku, në qoftë se ne kemi vënë një derë më shumë në 246 00:08:27,210 --> 00:08:29,610 ekran, atëherë Jennifer do kanë pasur të shikojmë, potencialisht, 247 00:08:29,610 --> 00:08:30,600 prapa një derë më shumë. 248 00:08:30,600 --> 00:08:33,490 Në qoftë se ne kemi vënë dy dyer më shumë, ajo mund të ketë të shikojmë prapa dy dyer më shumë. 249 00:08:33,490 --> 00:08:35,990 >> Dhe kështu, nuk ishte ky linear Marrëdhënia ndërmjet madhësisë së 250 00:08:35,990 --> 00:08:39,059 Problemi në, të themi, x-aks, dhe sasia e kohës që duhet për të 251 00:08:39,059 --> 00:08:40,440 zgjidhet në y. 252 00:08:40,440 --> 00:08:43,330 Por fotografia unë isha duke aluduar në më herët ishte kjo linjë e gjelbër. 253 00:08:43,330 --> 00:08:45,970 Jeshile qëllimisht, për shkak se ajo vetëm ndjehet më mirë. 254 00:08:45,970 --> 00:08:49,790 Në teori, algorithm, kur ne e bëmë atë me librin e telefonit, kur ne e bëmë atë 255 00:08:49,790 --> 00:08:52,420 me ju djema numëruar njëri-tjetrin, dhe në rastin e dytë, kur Jennifer vetëm 256 00:08:52,420 --> 00:08:55,250 e bëri atë deri këtu, ajo ishte lloj i rrënjësisht të mirë. 257 00:08:55,250 --> 00:08:57,180 Për shkak se ajo nuk ishte vetëm dy herë më shpejt. 258 00:08:57,180 --> 00:08:58,870 Kjo nuk ishte edhe katër herë më shpejtë. 259 00:08:58,870 --> 00:09:03,290 Ajo ishte krejtësisht e varur nga ajo që Madhësia e input ishte, si për sa 260 00:09:03,290 --> 00:09:05,220 hapat që përfundimisht e mori. 261 00:09:05,220 --> 00:09:08,040 >> Dhe kështu kjo ide e thjeshtë që ne të gjithë e mori për të dhënë me librin e telefonit, 262 00:09:08,040 --> 00:09:10,200 mund ngjashme të aplikohet për diçka si kjo. 263 00:09:10,200 --> 00:09:12,380 Dhe kjo mund të jetë më rastësisht i njohur si, si ju mund të 264 00:09:12,380 --> 00:09:13,940 imagjinoni, përça dhe sundo. 265 00:09:13,940 --> 00:09:16,390 Jo ndryshe nga ajo që kemi bërë, natyrisht, me librin e telefonit. 266 00:09:16,390 --> 00:09:18,300 >> Por pseudokod, risjell, ishte kjo. 267 00:09:18,300 --> 00:09:21,800 Pra, ne nuk do ta bëjë këtë përsëri, por kujtojnë që javën e parë, të gjithë prej nesh u ngrit 268 00:09:21,800 --> 00:09:25,140 dhe pastaj gjysma prej jush u ul, gjysma e ju u ul, gjysma prej jush u ul. 269 00:09:25,140 --> 00:09:29,280 Se algorithm u zbatua në një të bit prej nje menyre cheating, ne se, ajo 270 00:09:29,280 --> 00:09:32,870 nuk ishte vetëm një nga mua numërimit, rrënjësisht, në mënyrë më efikase. 271 00:09:32,870 --> 00:09:35,830 Në këtë rast, unë u leveraging një burim sekondar. 272 00:09:35,830 --> 00:09:39,470 Lloj, CPU të shumta, truri shumta, njerëzit të shumta i zgjuar në 273 00:09:39,470 --> 00:09:42,740 dhomë ishin të duke ndihmuar mua të merrni nga diçka lineare për diçka 274 00:09:42,740 --> 00:09:45,190 logaritmike, nga diçka kuqe të gjelbër diçka. 275 00:09:45,190 --> 00:09:48,650 >> Por në këtë rast, Jennifer vetmuar mundeni rrënjësisht të përmirësuar mbi 276 00:09:48,650 --> 00:09:52,370 Performanca e algorithm e saj të parë nga, përsëri, vetëm duke menduar pak më e vështirë. 277 00:09:52,370 --> 00:09:56,650 Dhe tani, kur vjen koha për të zbatuar këto gjëra, duke parafytyruar 278 00:09:56,650 --> 00:10:00,670 çfarë rreshta të kodit që ju mund të shkruani të tilla që ju mund të përsërisë ato përsëri, dhe 279 00:10:00,670 --> 00:10:03,350 përsëri, dhe përsëri, lloj në një mënyrë looping. 280 00:10:03,350 --> 00:10:06,370 Sepse ju nuk jeni do të ketë luks, si Jennifer bëri në fillim, për të 281 00:10:06,370 --> 00:10:10,460 të ketë vetëm një bandë e tërë e VJ dhe të thonë, hmm, në qoftë se ky numër parë është 4, 282 00:10:10,460 --> 00:10:11,800 më lejoni të kërcejnë gjatë gjithë rrugës deri në fund. 283 00:10:11,800 --> 00:10:14,180 Ooh, në qoftë se numri është shumë i madh, më lejoni të lëvizë në mënyrë arbitrare mbrapa 284 00:10:14,180 --> 00:10:15,220 në elementin e dytë. 285 00:10:15,220 --> 00:10:18,210 Ju do të të gjeni se ai po ndodh të jetë një shumë vështirë të formalizojnë atë që ne njerëzit 286 00:10:18,210 --> 00:10:21,270 marrë për të dhënë, si shumë të arsyeshme heuristics, por një kompjuter është vetëm 287 00:10:21,270 --> 00:10:23,260 do të bëni atë që ju them se për të bërë. 288 00:10:23,260 --> 00:10:25,280 >> Tani kjo e ka shumë të interesante Implikimet. 289 00:10:25,280 --> 00:10:29,950 Ky grafik është lloj i menduar të lloj trullos vizualisht, por njoftimi, ku 290 00:10:29,950 --> 00:10:32,230 është vijë e drejtë në këtë grafik? 291 00:10:32,230 --> 00:10:35,330 Ku është grafik linear që ne e quajmë n? 292 00:10:35,330 --> 00:10:37,580 E pra, kjo është lloj i drejt fund e kësaj tabloje, e drejtë? 293 00:10:37,580 --> 00:10:40,500 Pra, të gjithë ne kemi bërë është ne kemi lloj i zoomed jashtë boshtit x dhe 294 00:10:40,500 --> 00:10:44,780 y-aks për të përpiqen për të marrë një kuptim të asaj lloje të tjera të kthesa të duken si. 295 00:10:44,780 --> 00:10:47,760 >> Dhe specifikat e matematike Shprehjet sot nuk do të marrë parasysh në mënyrë 296 00:10:47,760 --> 00:10:52,440 shumë, por të vëreni se ka një shumë të Algoritmet që janë shumë më e keqe sesa 297 00:10:52,440 --> 00:10:53,470 diçka që është lineare. 298 00:10:53,470 --> 00:10:55,410 Në të vërtetë, n cubed duket goxha keq. 299 00:10:55,410 --> 00:10:58,400 2 deri n duket goxha keq. n katror duket goxha keq. 300 00:10:58,400 --> 00:11:01,630 Dhe ne do të shohim se çfarë disa nga ata mund të jetë në realitet sot. 301 00:11:01,630 --> 00:11:05,430 Dhe log n nuk ndihet si e keqe, por mirë se N është log bazë 2 n. 302 00:11:05,430 --> 00:11:08,080 Por ju e dini, kjo do të kishte qenë edhe më më të mahnitshme në qoftë se Jennifer, ose në qoftë se ne, 303 00:11:08,080 --> 00:11:12,910 që javën e parë, kishte dalë me diçka që është log log e n. 304 00:11:12,910 --> 00:11:15,880 >> Pra, me fjalë të tjera, ekziston kjo tërësi Gama e zgjidhjeve të mundshme për 305 00:11:15,880 --> 00:11:18,570 probleme, por edhe këtu, njoftimi çfarë do të ndodhë. 306 00:11:18,570 --> 00:11:22,910 Kur unë zoom out, cila nga këto kthesa do të provojë të jetë absolute 307 00:11:22,910 --> 00:11:26,630 më e keqja nga ato në ekran tani? 308 00:11:26,630 --> 00:11:28,680 Pra, n cubed duket goxha e e keqe në këtë moment. 309 00:11:28,680 --> 00:11:32,470 Por nëse ne zoom out dhe të shohim më shumë x dhe y-aks, i cili do të 310 00:11:32,470 --> 00:11:34,550 dominojnë në fund të fundit? 311 00:11:34,550 --> 00:11:37,120 Pra, ajo në fakt rezulton out se, 2 për të n, dhe ju mund të kuptoj këtë jashtë vetëm nga 312 00:11:37,120 --> 00:11:39,990 mbylljen në disa gjithnjë e më i madh numrat, dhe ju do të shihni se 2 për të 313 00:11:39,990 --> 00:11:42,070 n, me të vërtetë, merr të mëdha shumë më të shpejtë. 314 00:11:42,070 --> 00:11:45,530 Nëse ne me të vërtetë zoom out, një 2 për algorithm n absolutisht sucks. 315 00:11:45,530 --> 00:11:48,170 Unë do të thotë kjo është duke shkuar për të marrë fare pak kohe për 316 00:11:48,170 --> 00:11:49,460 kompjuter për të dybek përmes. 317 00:11:49,460 --> 00:11:52,500 >> Por ju do të shihni kalimin e kohës, veçanërisht me grupe të ardhmen problemore dhe madje 318 00:11:52,500 --> 00:11:55,600 Projektet përfundimtare, është të dhënat tuaja set merr të mëdha, të gjithë të drejtë? 319 00:11:55,600 --> 00:11:58,300 Edhe në versionin e parë të Facebook, si numri i miqve, dhe të 320 00:11:58,300 --> 00:12:01,840 Numri i përdoruesve të regjistruar mori të mëdha, ju mund të lloj i telefonit atë në dhe 321 00:12:01,840 --> 00:12:05,530 zbatojë diçka me kërkim linear, ose një klasifikim shumë e thjeshtë 322 00:12:05,530 --> 00:12:07,030 algorithm, siç ne do të shohim sot. 323 00:12:07,030 --> 00:12:09,280 Ju duhet të filloni të menduarit e vështirë dhe më e vështirë në lidhje me këto probleme. 324 00:12:09,280 --> 00:12:12,070 Dhe llojet e problemeve vende të si Facebook, dhe Google, dhe Microsoft, 325 00:12:12,070 --> 00:12:16,350 dhe të tjerët punojnë në është pikërisht këto lloj lloj madhe të të dhënave të pyetjeve 326 00:12:16,350 --> 00:12:18,530 gjithnjë këto ditë. 327 00:12:18,530 --> 00:12:18,900 >> Dakord. 328 00:12:18,900 --> 00:12:23,800 Pra, suksesin Jennifer në që të dytë algorithm, sinqerisht, ajo e bëri amazingly 329 00:12:23,800 --> 00:12:26,110 edhe hera e parë, por le shkruaj atë si fat kështu që ne 330 00:12:26,110 --> 00:12:27,000 mund të bëjë këtë pikë. 331 00:12:27,000 --> 00:12:30,970 Në rastin e dytë, ajo leveraged një algorithm se përsëritet përsëri dhe të 332 00:12:30,970 --> 00:12:34,670 përsëri, por ajo mori për të dhënë një Supozimi i sigurt se ne të lejuara 333 00:12:34,670 --> 00:12:39,370 saj, por ajo shfrytëzuar disa detaje hera e dytë që ajo nuk kishte 334 00:12:39,370 --> 00:12:39,840 hera e parë. 335 00:12:39,840 --> 00:12:41,800 Cila ishte ajo? 336 00:12:41,800 --> 00:12:43,050 >> Kjo listë u renditura. 337 00:12:43,050 --> 00:12:46,350 Pra, sa më shpejt që lista u renditura, ne pohojnë se Jennifer ishte në gjendje të bëjë 338 00:12:46,350 --> 00:12:47,480 rrënjësisht të mirë. 339 00:12:47,480 --> 00:12:51,450 7 dyer, po, nuk është se e interesante, por mendoj se ne jemi 7 milion dyert. 340 00:12:51,450 --> 00:12:54,080 Log n është definitivisht do për të kryer shumë, shumë 341 00:12:54,080 --> 00:12:55,610 më të shpejtë në afat të gjatë. 342 00:12:55,610 --> 00:12:58,880 Por ajo duhet të kishte Dyert e renditura për të. 343 00:12:58,880 --> 00:13:02,320 Tani, unë mora guximin për të bërë që paraprakisht në ekranin e kompjuterit 344 00:13:02,320 --> 00:13:05,160 këtu, por mendoj se Jennifer kishte të bënte se veten? 345 00:13:05,160 --> 00:13:10,120 Supozoni se dyert në fjalë Të dhënat përfaqësuar në një bazë të dhënash, ose 346 00:13:10,120 --> 00:13:14,260 miqtë e regjistruara për Facebook, ose ndonjë web faqe në internet që 347 00:13:14,260 --> 00:13:16,880 faqet e internetit të ndryshme mund të kenë nevojë tek indeksi ose kërkoni mbi. 348 00:13:16,880 --> 00:13:20,940 >> Supozoni se ju kishte vetëm një të dhënat e papërpunuara vendosur dhe ajo është lënë për ju, ose për të 349 00:13:20,940 --> 00:13:23,010 Jennifer për të bërë këtë klasifikim? 350 00:13:23,010 --> 00:13:26,950 Kjo, përkundrazi, kërkon që ne të përgjigjem pyetja, mirë, sa kohë 351 00:13:26,950 --> 00:13:31,080 do të marrë Jennifer, apo edhe mua, për të zgjidhur ato numra paraprakisht në mënyrë 352 00:13:31,080 --> 00:13:32,680 që ajo të mund të përfitojnë nga kjo? 353 00:13:32,680 --> 00:13:32,880 E drejta? 354 00:13:32,880 --> 00:13:36,620 Sepse implikimi, natyrisht, është në qoftë se ajo merr mua një kohë mjaft për të zgjidhur 355 00:13:36,620 --> 00:13:40,800 numrat, të cilët dreq kujdeset që t'ju mund të gjeni një numër si 50 në mënyrë të shpejtë, 356 00:13:40,800 --> 00:13:44,850 si në rastin e Jennifer, në qoftë se ne kemi më shumë se përshkuar sasinë e kohës totale 357 00:13:44,850 --> 00:13:46,920 ajo mori nga zgjidhja gjërat paraprakisht? 358 00:13:46,920 --> 00:13:49,320 >> Pra, le të shohim nëse ne nuk mund të pikturuar foton këtu. 359 00:13:49,320 --> 00:13:51,370 Unë kam stres një bandë e tërë më shumë topa, në qoftë se ndihmon 360 00:13:51,370 --> 00:13:52,270 thyejnë akullin këtu. 361 00:13:52,270 --> 00:13:55,690 Dhe në qoftë se ju nuk do mend, ne nevojë për shtatë vullnetari - 362 00:13:55,690 --> 00:13:57,060 on, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Pra, ne nuk kemi për të shpenzuar on llambat tavolinë, ajo duket. 365 00:13:59,250 --> 00:13:59,690 Dakord. 366 00:13:59,690 --> 00:14:01,530 Pra, si në lidhje me jush dy në frontin. 367 00:14:01,530 --> 00:14:04,160 How about ju dy guys në mbrapa. 368 00:14:04,160 --> 00:14:04,870 Pra, kjo është katër. 369 00:14:04,870 --> 00:14:09,890 Si për ju në frontin pesë, gjashtë dhe shtatë. 370 00:14:09,890 --> 00:14:10,320 E drejta atje. 371 00:14:10,320 --> 00:14:13,260 Pershendetje ckemi është vënë nga ju, kështu që ju të merrni çmimin. 372 00:14:13,260 --> 00:14:13,700 >> Dakord. 373 00:14:13,700 --> 00:14:14,410 Come on up. 374 00:14:14,410 --> 00:14:17,120 Dhe pse nuk kemi ju djema vijnë më gjatë këtu. 375 00:14:17,120 --> 00:14:18,960 Unë jam duke shkuar për të ju jap çdo numër një. 376 00:14:18,960 --> 00:14:22,150 Dhe të shkojnë përpara dhe të koordinojë veten identike me atë që është 377 00:14:22,150 --> 00:14:25,180 përshkruar në ekran. 378 00:14:25,180 --> 00:14:26,530 >> [Mbivendosje VOICES] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. Malan: oop, sorry. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Dakord. 382 00:14:32,180 --> 00:14:32,750 E pra, këtu ne do të shkojmë. 383 00:14:32,750 --> 00:14:34,180 Numri pesë. 384 00:14:34,180 --> 00:14:35,136 Numri gjashtë. 385 00:14:35,136 --> 00:14:37,770 Njëri, dy, tre, katër, pesë, gjashtë, shtatë. 386 00:14:37,770 --> 00:14:39,410 Oh, kjo është e vështirë. 387 00:14:39,410 --> 00:14:41,210 >> KRYETARI 2: Unë do të merrni vetëm një -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. Malan: marrëveshje të mirë. 389 00:14:41,900 --> 00:14:43,130 Dakord. 390 00:14:43,130 --> 00:14:44,611 Faleminderit për pjesëmarrjen. 391 00:14:44,611 --> 00:14:47,200 >> [Duartrokitje] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Dakord. 394 00:14:48,860 --> 00:14:51,970 Pra, ne kemi katër, dy, gjashtë, një, tre, shtatë, pesë. 395 00:14:51,970 --> 00:14:56,010 Perfect kështu që ne kemi shtatë vullnetarë këtu të cilët janë të barabartë në gjerësi të 396 00:14:56,010 --> 00:14:57,430 array se ne jemi duke luajtur me herët. 397 00:14:57,430 --> 00:14:59,470 Dhe unë zgjodha shtatë për arsye se do të jetë vetëm 398 00:14:59,470 --> 00:15:00,840 i përshtatshëm në një grimë pak. 399 00:15:00,840 --> 00:15:04,400 Dhe unë jam duke shkuar për të propozojë parë që kemi zgjidhur këto shtatë vullnetarë. 400 00:15:04,400 --> 00:15:06,786 Nëse ju do të doja, së pari, për të thënë hello pse. 401 00:15:06,786 --> 00:15:08,970 Që nga viti kjo është duke duke shkuar për të jetë një minuta çuditshme disa. 402 00:15:08,970 --> 00:15:10,370 Prezantoni veten tuaj. 403 00:15:10,370 --> 00:15:10,980 >> Grace: Hi, unë jam i Grace. 404 00:15:10,980 --> 00:15:14,190 Unë jam një i paedukuar mjaft në Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> Branson: Hi. 406 00:15:14,620 --> 00:15:15,620 Unë jam Branson. 407 00:15:15,620 --> 00:15:16,920 Unë jam një studente në bashkoj. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> Gabe: Hi. 410 00:15:20,230 --> 00:15:21,040 Unë jam Gabe. 411 00:15:21,040 --> 00:15:22,300 Unë jam një junior në Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> Neil: Unë jam Neil. 414 00:15:25,980 --> 00:15:29,090 Unë jam një studente në Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Unë jam Jason. 416 00:15:29,550 --> 00:15:32,816 Unë jam një studente në Greenough. 417 00:15:32,816 --> 00:15:33,700 >> Mike: Unë jam Mike. 418 00:15:33,700 --> 00:15:37,360 Unë jam një studente në Grays. 419 00:15:37,360 --> 00:15:37,990 >> Jess: Unë jam Jess. 420 00:15:37,990 --> 00:15:40,313 Unë jam një i paedukuar mjaft në Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. Malan: Excellent. 422 00:15:41,300 --> 00:15:41,850 Dakord. 423 00:15:41,850 --> 00:15:44,190 E pra, ju falenderoj për të gjithë e tona vullnetarët këtu deri tani. 424 00:15:44,190 --> 00:15:47,110 Dhe sfida në dorë tani është duke shkuar të jetë për të zgjidhur nga këta njerëz, por pastaj 425 00:15:47,110 --> 00:15:50,250 ne jemi duke shkuar për të duhet të mendojnë pak vështirë se sa efikase ne fakt 426 00:15:50,250 --> 00:15:51,110 renditura ato. 427 00:15:51,110 --> 00:15:52,580 Pra, le të parë të provoni këtë. 428 00:15:52,580 --> 00:15:55,970 Ju djema mund të shikoni numrat e njëri-tjetrit vetëm duke e vendosur rreth qoshet. 429 00:15:55,970 --> 00:15:59,380 Shkoni përpara dhe për të marrë disa sekonda, dhe lloj veten nga më i vogli në 430 00:15:59,380 --> 00:16:01,240 la të madh në të djathtë. 431 00:16:01,240 --> 00:16:02,490 Go. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Good. 435 00:16:08,030 --> 00:16:09,370 Kjo ishte e shpejtë me të vërtetë i mallkuar. 436 00:16:09,370 --> 00:16:14,040 Tani dikush këtu, çfarë ishte algorithm se këta djema aplikuar? 437 00:16:14,040 --> 00:16:14,900 >> Kryetari 1: Pak tek më i madhi. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. Malan: OK. 439 00:16:15,000 --> 00:16:18,070 Pak tek më i madh është me të vërtetë lloj i objektive, por unë nuk jam i sigurt se kjo është 440 00:16:18,070 --> 00:16:18,890 me të vërtetë një algoritmi. 441 00:16:18,890 --> 00:16:21,810 Paktën për të më i madh nuk sexsy do tregoni mua hap-pas-hapi se çfarë të bëni. 442 00:16:21,810 --> 00:16:22,833 Po? 443 00:16:22,833 --> 00:16:24,083 >> Kryetari 1: [padëgjueshme] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. Malan: OK. 446 00:16:26,280 --> 00:16:28,920 Pra, nëse ju shihni një person më i vogël se numrin tuaj, pastaj të shkojë në 447 00:16:28,920 --> 00:16:29,680 drejta e tyre. 448 00:16:29,680 --> 00:16:32,800 Kështu që tani po bëhet më ekspresive, më shumë si një algoritmi, sepse ju 449 00:16:32,800 --> 00:16:35,410 mund të them se, në qoftë se kjo, atëherë kjo. 450 00:16:35,410 --> 00:16:37,050 Pra, ne kemi disa lloj konstrukt i kushtëzuar. 451 00:16:37,050 --> 00:16:39,700 Dhe këta njerëz dukej për të bërë që disa herë, për shkak se disa prej jush lëvizur një grimë 452 00:16:39,700 --> 00:16:40,420 e nje distance. 453 00:16:40,420 --> 00:16:43,410 Pra, nuk ishte me sa duket një lloj looping ndodh në mendjet e tyre. 454 00:16:43,410 --> 00:16:44,610 >> Por le të përpiqemi për të formalizuar këtë. 455 00:16:44,610 --> 00:16:47,540 Nëse ju djema mund të ktheni mbrapa në këtë aranzhman. 456 00:16:47,540 --> 00:16:50,650 Le të shohim nëse ne nuk mund të zyrtarizojë këtë një bit, dhe pastaj pyesni pyetje, vetëm 457 00:16:50,650 --> 00:16:51,580 sa efikas është kjo? 458 00:16:51,580 --> 00:16:54,220 Sigurisht, kur ne e bëjmë këtë më ngadalë, ajo do të ndjehen si të mirë të 459 00:16:54,220 --> 00:16:57,210 një algoritëm, por le të shohim nëse ne mund të vënë gishtat tonë në hapat e sakta. 460 00:16:57,210 --> 00:16:58,670 >> Pra, ju dy djemtë janë katër dhe dy. 461 00:16:58,670 --> 00:17:01,020 Ose ju qëllim të sakta ose të pasakta? 462 00:17:01,020 --> 00:17:01,900 Natyrisht pasaktë. 463 00:17:01,900 --> 00:17:02,710 Pra, ne swapped. 464 00:17:02,710 --> 00:17:05,170 Tani unë jam duke shkuar për të lëvizur anash këtu dhe thonë, katër në gjashtë. 465 00:17:05,170 --> 00:17:06,240 Jeni të sakta ose të pasakta? 466 00:17:06,240 --> 00:17:06,599 >> Gabe: korrekte. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. Malan: korrekte. 468 00:17:07,180 --> 00:17:08,300 Gjashtë dhe një? 469 00:17:08,300 --> 00:17:08,609 Nope. 470 00:17:08,609 --> 00:17:09,630 Swap. 471 00:17:09,630 --> 00:17:10,490 Pra, kjo është dy këmbime. 472 00:17:10,490 --> 00:17:11,710 Gjashtë dhe tre? 473 00:17:11,710 --> 00:17:11,980 Nope. 474 00:17:11,980 --> 00:17:13,000 Swap. 475 00:17:13,000 --> 00:17:13,930 Gjashtë dhe shtatë? 476 00:17:13,930 --> 00:17:14,630 Duket e mirë. 477 00:17:14,630 --> 00:17:15,396 Shtatë dhe pesë? 478 00:17:15,396 --> 00:17:16,150 >> Jess: [padëgjueshme] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. Malan: OK, të bie në ujdi. 480 00:17:17,089 --> 00:17:19,770 Dhe të renditura. 481 00:17:19,770 --> 00:17:19,980 Dakord. 482 00:17:19,980 --> 00:17:21,440 Pra, nuk është e qartë, e drejtë? 483 00:17:21,440 --> 00:17:22,470 Pra, nuk ishte më shumë në vazhdim e sipër. 484 00:17:22,470 --> 00:17:24,920 Por, në të vërtetë, këta njerëz, madje edhe vetëm instinktivisht. 485 00:17:24,920 --> 00:17:25,450 mbajtur në lëvizje. 486 00:17:25,450 --> 00:17:27,710 Ata nuk ndalet vetëm, pasi ata korrigjuar një problem. 487 00:17:27,710 --> 00:17:27,839 Pra. 488 00:17:27,839 --> 00:17:29,390 Në të vërtetë, unë jam do të ketë për të bërë të njëjtën gjë. 489 00:17:29,390 --> 00:17:32,720 Unë jam do të keni për të zgjidhur e pasme Rewind në fillim të këtij problemi, 490 00:17:32,720 --> 00:17:35,630 ose fillimi i këtij grup të njerëzit, le të fillojë duke i quajtur ato. 491 00:17:35,630 --> 00:17:38,366 >> Dhe tani çfarë duhet algoritmi im on së pasimi të së dytë jenë? 492 00:17:38,366 --> 00:17:39,220 >> Kryetari 1: E njëjta gjë. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. Malan: E njëjta gjë. 494 00:17:39,940 --> 00:17:41,460 Dhe kjo, unë jam duke filluar të pëlqen, e drejtë? 495 00:17:41,460 --> 00:17:44,720 Sa më shpejt si ju mund të gjeni veten tuaj duke bërë të njëjtën gjë përsëri dhe përsëri, kjo është 496 00:17:44,720 --> 00:17:47,890 duke u bërë më shumë si një algoritmi, dhe me pak instinkti njerëzor. 497 00:17:47,890 --> 00:17:48,680 >> Deri tani, këtu ne do të shkojmë përsëri. 498 00:17:48,680 --> 00:17:49,870 Dy dhe katër? 499 00:17:49,870 --> 00:17:50,220 Jo. 500 00:17:50,220 --> 00:17:51,050 Katër dhe një? 501 00:17:51,050 --> 00:17:53,380 Ah, nuk ishte me të vërtetë disa të punojë ende për t'u bërë. 502 00:17:53,380 --> 00:17:53,620 Për dhe tre? 503 00:17:53,620 --> 00:17:54,572 Good. 504 00:17:54,572 --> 00:17:56,000 Katër dhe gjashtë? 505 00:17:56,000 --> 00:17:58,380 Gjashtë dhe pesë? 506 00:17:58,380 --> 00:17:59,470 Gjashtë dhe shtatë? 507 00:17:59,470 --> 00:18:00,970 OK, tani, bëhet. 508 00:18:00,970 --> 00:18:01,550 OK, nr. 509 00:18:01,550 --> 00:18:02,710 Unë kam për të shkuar mbrapa. 510 00:18:02,710 --> 00:18:05,130 >> Deri tani, përsëri, ne jemi duke e bërë këtë pak më shumë qëllimisht. 511 00:18:05,130 --> 00:18:08,700 Dhe tani, atje është vetëm një truri ekzekutimin e këtij algoritmi. 512 00:18:08,700 --> 00:18:10,290 Një CPU, nëse ju do. 513 00:18:10,290 --> 00:18:13,090 Dhe sinqerisht, kjo është vetmi burim ne jemi duke shkuar për të kenë qasje në. 514 00:18:13,090 --> 00:18:16,280 Dhe dikur ne do të shkojnë kthehemi në një tastierë dhe të ketë diçka si C në tonë 515 00:18:16,280 --> 00:18:19,600 Shkatërrimi, ne jemi duke vetëm shkruarit e një program të që mund të bëjë një gjë në një kohë. 516 00:18:19,600 --> 00:18:22,900 Ndërsa, këta njerëz një moment më parë, ne leveraged brainpower e tyre kolektive 517 00:18:22,900 --> 00:18:24,180 si ju djema bëri në zero javë. 518 00:18:24,180 --> 00:18:24,980 Pra, le të vazhdojmë të bëjmë këtë. 519 00:18:24,980 --> 00:18:26,260 >> Dy dhe një. 520 00:18:26,260 --> 00:18:26,945 Dy dhe tre. 521 00:18:26,945 --> 00:18:27,460 Tre dhe katër. 522 00:18:27,460 --> 00:18:28,310 Katër dhe pesë. 523 00:18:28,310 --> 00:18:28,620 Pesë dhe gjashtë. 524 00:18:28,620 --> 00:18:30,510 Gjashtë dhe shtatë. 525 00:18:30,510 --> 00:18:31,880 Done? 526 00:18:31,880 --> 00:18:34,560 Kështu që unë jam, por më lejoni të luajë avokati i djallit. 527 00:18:34,560 --> 00:18:37,950 A kam, lloj i kompjuterit i cili vetëm e bëri një pasim nëpërmjet këtij array së 528 00:18:37,950 --> 00:18:40,225 njerëzit, e dinë se unë jam bërë? 529 00:18:40,225 --> 00:18:40,670 >> Gjuha 1: Jo 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. Malan: Pra, pse? 531 00:18:41,050 --> 00:18:46,900 Çfarë do që unë duhet të bëni në mënyrë që të konkludojmë decidivisht se unë jam bërë? 532 00:18:46,900 --> 00:18:48,230 Ndoshta një të kalojë më shumë. 533 00:18:48,230 --> 00:18:48,430 E drejta? 534 00:18:48,430 --> 00:18:51,760 Sepse të gjithë unë e di nga se paraardhëse kalojë është se unë korrigjuar një gabim. 535 00:18:51,760 --> 00:18:53,920 Që do të thotë, ndoshta ka ende të një tjetër gabim 536 00:18:53,920 --> 00:18:54,840 se kam nevojë për të korrigjuar. 537 00:18:54,840 --> 00:18:58,680 Kështu që unë mund vetëm të jetë i sigurt nga rewinding, dhe pastaj duke kontrolluar, një në dy, dy dhe 538 00:18:58,680 --> 00:19:00,940 tre, tre dhe katër, katër dhe pesë, pesë dhe gjashtë, gjashtë dhe shtatë. 539 00:19:00,940 --> 00:19:02,510 OK, tani unë nuk bëri asnjë punë. 540 00:19:02,510 --> 00:19:05,990 >> Unë me siguri mund të mbani mend se unë nuk bëri asnjë punojnë me diçka si një variabël, 541 00:19:05,990 --> 00:19:06,975 si një int. 542 00:19:06,975 --> 00:19:12,490 Quajeni këmbime, dhe në qoftë se këmbime është 0 herë unë merrni këtu, dhe ajo filloi në 0, atëherë 543 00:19:12,490 --> 00:19:15,520 Unë vetëm do të jetë i trashë për të mbajtur vazhdim e sipër mbrapa dhe me radhë, duke kontrolluar përsëri, dhe 544 00:19:15,520 --> 00:19:16,450 përsëri, dhe përsëri, e drejtë? 545 00:19:16,450 --> 00:19:18,450 Sepse ju merrni mbërthyer në disa lloj lak pafund. 546 00:19:18,450 --> 00:19:21,250 Pra, sa më shpejt që ka 0 këmbime, ne mund të pretendojnë se kjo 547 00:19:21,250 --> 00:19:23,810 Algorithm është me të vërtetë e plotë. 548 00:19:23,810 --> 00:19:25,400 >> Tani, le të vënë një emër për këtë. 549 00:19:25,400 --> 00:19:28,930 Algoritmi që unë propozoj ne vetëm implementuar është diçka që quhet flluskë 550 00:19:28,930 --> 00:19:32,800 lloj, i njohur si i tillë në kuptimin që numrat që janë lloji më i madh i 551 00:19:32,800 --> 00:19:37,990 flluskë rrugën e tyre deri në majë, ose deri tek fundi i vektorit të numrave. 552 00:19:37,990 --> 00:19:40,270 Por sa efikase ishte kjo algoritmi? 553 00:19:40,270 --> 00:19:44,600 Sa hapa kam fizikisht duhet të të marrë, për shembull, për të zgjidhur këto 554 00:19:44,600 --> 00:19:45,850 shtatë njerëzit? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Katër deri në pesë? 557 00:19:49,550 --> 00:19:51,420 OK, shumë është në fund të fundit do të jetë përgjigja. 558 00:19:51,420 --> 00:19:54,960 Por edhe atëherë, numër specifik nuk është aq interesante. 559 00:19:54,960 --> 00:19:56,670 Le të përgjithësojnë atë si n. 560 00:19:56,670 --> 00:20:00,520 Pra, nëse unë e kishte n popullin e up këtu, dhe ata ishin, lloj, në mënyrë të rastit në 561 00:20:00,520 --> 00:20:02,180 filluar, në atë mënyrë origjinale. 562 00:20:02,180 --> 00:20:04,910 E pra, sa hapa nuk kam për të marrë mbi kalimin e parë? 563 00:20:04,910 --> 00:20:09,810 Ajo ishte një, dy, tre, katër, pesë, gjashtë, dhe ata janë shtatë njerëz, kështu që 564 00:20:09,810 --> 00:20:13,670 kjo është shtatë, gjashtë -, kështu që është n minus një hapa herën e parë. 565 00:20:13,670 --> 00:20:16,280 >> Tani, sa hapa nuk kam për të marrë kur unë rewound? 566 00:20:16,280 --> 00:20:19,310 E pra, ne në fakt mund të dyfishtë se në qoftë se ne me të vërtetë të kërkuar për të, por tani për tani, unë jam 567 00:20:19,310 --> 00:20:22,300 vetëm do të them, të gjithë të drejtë, një tjetër n minus 1. 568 00:20:22,300 --> 00:20:25,240 Pra, minus n 1 është duke duke shkuar për të të merrni i bezdisshëm për të mbajtur gjurmët e, kështu që le të 569 00:20:25,240 --> 00:20:26,400 vetëm raundin deri pak. 570 00:20:26,400 --> 00:20:27,770 Pra 2N hapa. 571 00:20:27,770 --> 00:20:29,310 Pra 14 hapa, të japë ose të marrë. 572 00:20:29,310 --> 00:20:31,930 >> Sa herë kam marrë një hap herën tjetër? 573 00:20:31,930 --> 00:20:33,740 E pra, kjo është 3n. 574 00:20:33,740 --> 00:20:34,510 me të vërtetë. 575 00:20:34,510 --> 00:20:37,920 Dhe tani, në rastin më të keq, për shembull, sa herë do të kam 576 00:20:37,920 --> 00:20:41,730 shkuar mbrapa dhe me radhë, mbrapa dhe me radhë, ekzekutimin e këtij algoritmi, shkëmbejnë 577 00:20:41,730 --> 00:20:44,620 njerëzit në çdo të kalojë, afërsisht? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Është n fakt katror, ​​e drejtë? 580 00:20:50,010 --> 00:20:53,000 >> Sepse në rastin më të keq, ju mund të lloj të mendojnë në lidhje me këtë intuitive, 581 00:20:53,000 --> 00:20:54,800 edhe pse ajo mund të marrë pak pak kohë të zhytet in 582 00:20:54,800 --> 00:20:57,590 Në rastin më të keq, çfarë do këto shtatë njerëz kanë shikuar si, në 583 00:20:57,590 --> 00:21:00,230 Kushtet e marrëveshjes të numrit të tyre? 584 00:21:00,230 --> 00:21:01,460 Plotësisht prapa, të drejtë? 585 00:21:01,460 --> 00:21:02,815 Dhe vetëm për të simuluar se, çfarë ishte emri juaj përsëri? 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> DAVID J. Malan: Mike? 588 00:21:03,640 --> 00:21:08,100 OK, Mike, ju mund të bashkohen vetëm mbi mua këtu për vetëm një të dytë? 589 00:21:08,100 --> 00:21:08,880 Në fakt, nuk ka. 590 00:21:08,880 --> 00:21:10,150 Na vjen keq Mike, Rewind le. 591 00:21:10,150 --> 00:21:10,910 Cili është emri juaj përsëri? 592 00:21:10,910 --> 00:21:11,180 >> Neil: Neil. 593 00:21:11,180 --> 00:21:11,640 >> DAVID J. Malan: Neil. 594 00:21:11,640 --> 00:21:13,750 OK, Neil, ju vijnë me mua, në qoftë se ju nuk do mend. 595 00:21:13,750 --> 00:21:17,150 Kështu që unë jam duke shkuar për të propozojnë, vetëm për Thjeshtësia, se Neil është tani në e tij 596 00:21:17,150 --> 00:21:18,510 Rasti më i keq të jetë e mundur. 597 00:21:18,510 --> 00:21:20,720 Por kujtojmë se si unë zbatuar algorithm im. 598 00:21:20,720 --> 00:21:24,530 Unë jam duke e krahasuar, duke e krahasuar, duke e krahasuar, krahasuar, duke e krahasuar, oh. 599 00:21:24,530 --> 00:21:26,640 Tani këta janë jashtë e rendit, kështu që unë të rregulluar. 600 00:21:26,640 --> 00:21:27,980 Pra, ju djema bie në ujdi. 601 00:21:27,980 --> 00:21:31,630 Por e konsiderojnë tani, sa më larg nuk Neil duhet të shkojnë? 602 00:21:31,630 --> 00:21:32,690 Është n afërsisht. 603 00:21:32,690 --> 00:21:33,570 Ju e dini, kjo nuk është n fakt. 604 00:21:33,570 --> 00:21:36,040 Është si, n minus 1, por unë jam marrë udhë mërzitur mbajtja e pak 605 00:21:36,040 --> 00:21:37,550 numër, kështu që le të vetëm e quajti atë n. 606 00:21:37,550 --> 00:21:42,860 >> Pra, nëse Neil lëviz një hap maksimalisht çdo kohë, dhe për të lëvizur Neil një hap, 607 00:21:42,860 --> 00:21:46,580 Unë kam për të bërë këtë abone të vërtetë të lodhshme mbrapa dhe me radhë, kjo është afërsisht 608 00:21:46,580 --> 00:21:52,080 bërë këtë, n hapa, një total prej herë n, sepse ajo do të marrë mua 609 00:21:52,080 --> 00:21:55,820 se hapa shumë për të marrë të Neil të gjithë mënyrë për të, ku ai i takon. 610 00:21:55,820 --> 00:21:58,620 Le të vetëm të gjithë të tjerët në qoftë se ju djema ishin të gjithë mis-urdhëroi si mirë. 611 00:21:58,620 --> 00:22:01,100 >> Pra, le ta quajmë lloj flluskë n squared. 612 00:22:01,100 --> 00:22:04,860 Ora drejtimin e këtij algoritmi, Performanca e këtij algoritmi, 613 00:22:04,860 --> 00:22:07,120 efikasiteti i këtij algoritmi, ne do të vetëm të përshkruaj më shumë 614 00:22:07,120 --> 00:22:08,800 përgjithësisht si n katror. 615 00:22:08,800 --> 00:22:11,650 Cila është e bukur, sepse unë mund të bëj Shembulli i njëjtë me tetë njerëzve, nëntë 616 00:22:11,650 --> 00:22:15,450 njerëz, një milion njerëz, dhe se Përgjigja nuk do të ndryshojë. 617 00:22:15,450 --> 00:22:18,870 >> Pra, nëse ju djema nuk do mend, le të rivendosni ju ku ju keni filluar. 618 00:22:18,870 --> 00:22:22,510 Dhe le të përpiqemi dy qasjet e tjera dhe të shohim nëse ne nuk mund të bëjmë rrënjësisht 619 00:22:22,510 --> 00:22:23,820 mirë se kjo. 620 00:22:23,820 --> 00:22:27,130 Pra, kjo kohë, unë jam duke shkuar për të propozojë një lloj algoritmi të ndryshme. 621 00:22:27,130 --> 00:22:29,950 Kjo ishte shumë i zgjuar prej nesh hera e fundit, dhe ju djema ishin të drejtë të ketë 622 00:22:29,950 --> 00:22:32,470 Instinktet e pasur të drejtën e vetëm lloji të shkëmbejnë pairwise. 623 00:22:32,470 --> 00:22:36,500 Por në qoftë se unë me të vërtetë donte të qasen thjesht, dhe qëllimi im është që të lëvizë 624 00:22:36,500 --> 00:22:39,800 të gjithë numrat e vegjël në këtë mënyrë, dhe shtyjë të gjithë numrat e mëdha që 625 00:22:39,800 --> 00:22:43,030 mënyrë, pse nuk Unë vetëm të bëjë që në më naive mënyra e mundur dhe të shohim nëse unë 626 00:22:43,030 --> 00:22:45,730 mund të bëjë më mirë se ajo ishte një mjaft algorithm komplekse? 627 00:22:45,730 --> 00:22:46,620 >> Pra, le të shohim. 628 00:22:46,620 --> 00:22:48,940 Katër është një numër shumë i vogël, kështu që unë jam duke shkuar për të largohet nga ju atje moment. 629 00:22:48,940 --> 00:22:50,610 Ooh, numri dy është edhe më mirë. 630 00:22:50,610 --> 00:22:52,230 Pra, mund të ju vetëm hap përpara për një çast? 631 00:22:52,230 --> 00:22:55,670 Kjo është e aktualisht numerimet im më i vogël Kandidati, dhe unë jam duke shkuar për të kujtuar 632 00:22:55,670 --> 00:22:57,000 se me, si, një ndryshore. 633 00:22:57,000 --> 00:22:57,930 Por unë jam duke shkuar për të mbajtur të checking. 634 00:22:57,930 --> 00:22:59,890 A ka dikush të cilit numër është i vogël? 635 00:22:59,890 --> 00:23:00,460 Gjashtë, nr. 636 00:23:00,460 --> 00:23:01,390 Oh, nuk Neil përsëri. 637 00:23:01,390 --> 00:23:04,050 >> Kështu që unë jam duke shkuar për të nxitur ju prapa lloj konceptualisht. 638 00:23:04,050 --> 00:23:05,120 Neil do të vijë përpara. 639 00:23:05,120 --> 00:23:08,440 Dhe tani, variabli që unë jam duke përdorur për të mbajnë gjurmët e të cilët ka më të vogël 640 00:23:08,440 --> 00:23:11,390 numër është përditësuar të përmbajë Vendndodhja Neil. 641 00:23:11,390 --> 00:23:12,110 E pra, le të shohim. 642 00:23:12,110 --> 00:23:13,960 Tre, shtatë, pesë. 643 00:23:13,960 --> 00:23:15,590 OK, unë e di Neil ishte më i vogël. 644 00:23:15,590 --> 00:23:18,110 Cila është gjëja më e thjeshtë për mua të bëjmë tani? 645 00:23:18,110 --> 00:23:21,410 Unë nuk jam duke shkuar për të humbim kohë e mia me vetëm bubbling Neil vend një të majtë. 646 00:23:21,410 --> 00:23:25,350 Pse nuk mundem të vetëm vënë Neil ku ai takon, i cili eshte i kursit ku? 647 00:23:25,350 --> 00:23:26,160 >> Të gjitha mënyra në fillim. 648 00:23:26,160 --> 00:23:27,720 Pra, Neil, eja me mua. 649 00:23:27,720 --> 00:23:28,910 Dhe çfarë ishte emri juaj përsëri? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Grace. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. Malan: Grace. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Pra Grace, për fat të keq, ju jeni lloj në rrugë. 654 00:23:32,490 --> 00:23:34,290 Deri sa nuk kemi zgjidhur këtë problem? 655 00:23:34,290 --> 00:23:34,490 E drejta? 656 00:23:34,490 --> 00:23:37,500 Në qoftë se kjo është një koleksion, ka vetëm shtatë vende. 657 00:23:37,500 --> 00:23:40,830 Kujtojnë se, me Rob, kemi biseduar rreth shpallja e moshave, dhe kemi pasur vetëm një 658 00:23:40,830 --> 00:23:41,740 numër i caktuar i moshave? 659 00:23:41,740 --> 00:23:42,535 Ideja e njëjtë këtu. 660 00:23:42,535 --> 00:23:44,300 Ne kemi vetëm një numër i caktuar i ints. 661 00:23:44,300 --> 00:23:47,590 Grace është lloj i në tonë mënyrë, kështu që si mund ne të rregullojmë? 662 00:23:47,590 --> 00:23:49,555 >> Mënyra më e thjeshtë është si, Grace, sorry. 663 00:23:49,555 --> 00:23:51,870 Ju jeni do të keni për të shkuar mbi atje kështu që ne mund të bëjë dhomë. 664 00:23:51,870 --> 00:23:55,290 Tani, në qoftë se ju mendoni për këtë, ndoshta ne vetëm e bëri problemin edhe më keq. 665 00:23:55,290 --> 00:23:58,510 Dhe ndoshta ne e bëmë, sepse çka nëse Grace ishin në vendin e duhur? 666 00:23:58,510 --> 00:24:01,730 Por ne e dimë se ajo nuk është, sepse përndryshe, ajo do të kishte qenë 667 00:24:01,730 --> 00:24:03,980 këmbë përpara në vend të Neil në këtë kohë, e drejtë? 668 00:24:03,980 --> 00:24:05,550 Ne tashmë e kontrolluar numrin e saj jashtë. 669 00:24:05,550 --> 00:24:05,770 >> Dakord. 670 00:24:05,770 --> 00:24:09,110 Deri tani, Neil është në vendin e duhur, dhe Unë mund të bëjë një optimization lehtë. 671 00:24:09,110 --> 00:24:11,740 Për minutë ardhshëm, unë jam duke shkuar për të injorojë Neil gjithë së bashku, në mënyrë që të mos 672 00:24:11,740 --> 00:24:15,280 humbim kohën e tij, apo aksidentalisht të bie në ujdi atë në vendin e gabuar. 673 00:24:15,280 --> 00:24:17,805 Kështu që tani, si mund unë të gjeni e ardhshëm element që është më i vogël? 674 00:24:17,805 --> 00:24:18,480 Dy. 675 00:24:18,480 --> 00:24:20,225 Kjo është një numër mjaft të mirë, në qoftë se ju doni të hap përpara dhe 676 00:24:20,225 --> 00:24:21,100 Unë do të kujtoj juve. 677 00:24:21,100 --> 00:24:21,980 Gjashtë, asnjë të mirë. 678 00:24:21,980 --> 00:24:24,820 Katër, tre, shtatë, pesë, asnjë të mirë. 679 00:24:24,820 --> 00:24:26,800 Pra më lejoni të lëvizë ju për të vendi juaj drejtë. 680 00:24:26,800 --> 00:24:28,470 Dhe ne vetëm mori me fat këtë kohë. 681 00:24:28,470 --> 00:24:31,350 >> Tani, unë jam duke shkuar për të injorojë këto dy djemtë, dhe tani të bëjë një më shumë 682 00:24:31,350 --> 00:24:32,260 kalojnë nëpër këtë. 683 00:24:32,260 --> 00:24:33,490 Gjashtë, se një numër shumë i vogël. 684 00:24:33,490 --> 00:24:34,300 Come on përpara. 685 00:24:34,300 --> 00:24:35,220 Oh, sorry. 686 00:24:35,220 --> 00:24:37,640 Numri i Grace është më e mirë, kështu hap më përpara. 687 00:24:37,640 --> 00:24:38,260 Katër. 688 00:24:38,260 --> 00:24:39,120 Na vjen keq, Grace. 689 00:24:39,120 --> 00:24:39,950 Kthehu mbrapa përsëri. 690 00:24:39,950 --> 00:24:41,550 Numri tre është më e mirë. 691 00:24:41,550 --> 00:24:42,290 Shtatë. 692 00:24:42,290 --> 00:24:42,720 Pesë. 693 00:24:42,720 --> 00:24:43,550 Dhe tani çfarë është emri juaj përsëri? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. Malan: Jason. 696 00:24:44,420 --> 00:24:47,050 Pra, Jason është tani më i vogël Elementi i kam zgjedhur. 697 00:24:47,050 --> 00:24:49,160 Ku është ai që do të shkojnë? 698 00:24:49,160 --> 00:24:50,380 Pra, ku gjashtë është. 699 00:24:50,380 --> 00:24:51,210 Dhe emri i yt është përsëri? 700 00:24:51,210 --> 00:24:51,710 >> Gabe: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> DAVID J. Malan: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe është në rrugë të drejtë. 703 00:24:53,220 --> 00:24:54,640 Cila është gjëja më e lehtë për të bërë? 704 00:24:54,640 --> 00:24:58,390 Swap këto dy djem dhe vazhdojnë. 705 00:24:58,390 --> 00:24:59,020 Pra, tani le të shohim. 706 00:24:59,020 --> 00:25:00,170 Kush është më i vogël? 707 00:25:00,170 --> 00:25:01,030 Katër. 708 00:25:01,030 --> 00:25:01,990 Më lejoni vetëm lloj të mashtrojnë. 709 00:25:01,990 --> 00:25:03,090 Pesë do të jetë më i vogël. 710 00:25:03,090 --> 00:25:05,220 Unë gjej ardhshëm, nëse ju doni të hap përpara, çfarë duhet të bëj me 711 00:25:05,220 --> 00:25:06,820 këta djema, me Gabe? 712 00:25:06,820 --> 00:25:08,450 Swap përsëri. 713 00:25:08,450 --> 00:25:10,740 Deri tani, ende pak nga e rendit. 714 00:25:10,740 --> 00:25:14,140 Kam gjetur Gabe të jetë më i vogël, kështu që Unë pop atë jashtë, lëvizin you guys gjatë. 715 00:25:14,140 --> 00:25:15,190 Dhe bëhet. 716 00:25:15,190 --> 00:25:17,200 >> Pra, përgjigja është e njëjtë. 717 00:25:17,200 --> 00:25:18,600 Rezultati përfundimtar është i njëjtë. 718 00:25:18,600 --> 00:25:22,730 Cila nga këto dy algoritme është më e mirë? 719 00:25:22,730 --> 00:25:23,500 E dyta, kam dëgjuar. 720 00:25:23,500 --> 00:25:24,252 Pse? 721 00:25:24,252 --> 00:25:25,900 >> Kryetari 3: Është n etapat [padëgjueshme]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. Malan: Është hapa n më së shumti. 723 00:25:27,600 --> 00:25:28,490 Interesting. 724 00:25:28,490 --> 00:25:30,610 Pra, është ajo edhe pse? 725 00:25:30,610 --> 00:25:33,630 Pra, si nuk kam gjetur Elementi më i vogël? 726 00:25:33,630 --> 00:25:37,060 Sa shumë Hapat e nuk kam keni për të marrë gjeni elementin më të vogël? 727 00:25:37,060 --> 00:25:39,220 Unë kisha një vështrim të gjithë rrugën në fund, e drejtë? 728 00:25:39,220 --> 00:25:41,530 Sepse në këtë rast më të keq, çfarë nëse Neil ishin mbi këtu? 729 00:25:41,530 --> 00:25:45,700 Pra, vetëm gjetur elementin më të vogël merr mua n hapa, ose N minus 1. 730 00:25:45,700 --> 00:25:46,100 Por, OK. 731 00:25:46,100 --> 00:25:46,980 Pra, fix Neil. 732 00:25:46,980 --> 00:25:48,740 Mos harroni se, një minutë apo të kështu me më parë. 733 00:25:48,740 --> 00:25:51,680 >> Por si nuk kam gjetur tjetër Elementi më i vogël? 734 00:25:51,680 --> 00:25:54,830 Është n minus 1, ose n minus 2 vërtetë, nga numri i hapave. 735 00:25:54,830 --> 00:25:55,440 Pra, OK. 736 00:25:55,440 --> 00:25:57,390 Kështu që unë kam n minus 2. 737 00:25:57,390 --> 00:25:57,600 Dakord. 738 00:25:57,600 --> 00:25:59,130 Kështu që ndihet pak më mirë. 739 00:25:59,130 --> 00:25:59,730 Dakord. 740 00:25:59,730 --> 00:26:03,270 Sa hapa herën tjetër për të gjetur numrin tre? 741 00:26:03,270 --> 00:26:04,420 Pra, n minus 4. 742 00:26:04,420 --> 00:26:07,670 Pra, kjo është në rënie, një më pak hap në çdo përsëritje. 743 00:26:07,670 --> 00:26:08,740 Pra, kjo do të ndjehen më mirë, e drejtë? 744 00:26:08,740 --> 00:26:13,450 Nëse herën e fundit ajo ishte afërsisht n herë n, këtë herë kjo është n minus 1, plus n minus 745 00:26:13,450 --> 00:26:16,500 2, plus n minus 3, plus n minus 4, dot, dot, dot. 746 00:26:16,500 --> 00:26:18,750 Por në qoftë se ju kujtohet nga shkolla tuaj të lartë Tekstet, mashtrojnë pak 747 00:26:18,750 --> 00:26:24,380 fletë në pjesën e pasme që ka formula, nëse ju të shtoni deri këtë seri të numrave, 748 00:26:24,380 --> 00:26:31,280 çfarë është numri total i hapave do të jetë që unë të marrë këtu? 749 00:26:31,280 --> 00:26:36,580 >> Kjo është një nga ata, si, n minus 1, herë n, ndarë nga 2. 750 00:26:36,580 --> 00:26:39,040 Pra më lejoni të shohim nëse unë mund të tërheqë kjo për vetëm një moment. 751 00:26:39,040 --> 00:26:42,230 Dhe përsëri, unë jam natyrë e grumbullimit disa Numrat e vetëm për të mbajtur jetën tonë të thjeshtë, 752 00:26:42,230 --> 00:26:47,830 por si unë kujtoj, kjo është diçka si në qoftë se Bëj n minus 1 gjëra, pastaj n minus 753 00:26:47,830 --> 00:26:53,570 2, pastaj n minus 3, kjo është afërsisht diçka si kjo mbi 2, dhe në qoftë se unë 754 00:26:53,570 --> 00:26:55,510 shumëfishohen këtë, se është në fakt katror n. 755 00:26:55,510 --> 00:26:58,940 Kjo nuk është ndjenjë shumë e mirë. n minus n mbi 2. 756 00:26:58,940 --> 00:27:00,350 >> Por këtu është gjë. 757 00:27:00,350 --> 00:27:03,720 Në kompjuterike shkencës, kur problemet të fillojë të marrë interesant është kur n 758 00:27:03,720 --> 00:27:04,700 merr me të vërtetë e madhe. 759 00:27:04,700 --> 00:27:08,110 Dhe kur n merr me të vërtetë e madhe, e cila i këto vlera do të dominojë të gjithë 760 00:27:08,110 --> 00:27:09,750 e të tjerëve? 761 00:27:09,750 --> 00:27:10,990 Kjo është lloj i n katror, ​​e drejtë? 762 00:27:10,990 --> 00:27:13,340 Po, pjestuar me 2 është shumë e mirë. 763 00:27:13,340 --> 00:27:16,740 Por nëse ju jeni duke folur për miliarda nga copa të të dhënave, apo triliona 764 00:27:16,740 --> 00:27:18,700 pjesë e të dhënave, OK, kështu që ju jeni dy herë më të shpejtë. 765 00:27:18,700 --> 00:27:22,440 Por që me të vërtetë kujdeset në qoftë se numri i madh, në qoftë se ky faktor është ajo që merr 766 00:27:22,440 --> 00:27:23,040 më të mëdha. 767 00:27:23,040 --> 00:27:25,990 Dhe sigurisht, kjo e bën më të një dallim se këtë djalë. 768 00:27:25,990 --> 00:27:29,120 Pra, edhe pse ju djema jeni të drejtë, algorithm e dytë, ne do të thërrasë atë 769 00:27:29,120 --> 00:27:32,970 lloj përzgjedhjes, eshte, ne te botës reale, nje pak më të shpejtë të mundshme, sepse unë jam 770 00:27:32,970 --> 00:27:35,360 duke marrë më pak dhe më pak hapat që secila kohë. 771 00:27:35,360 --> 00:27:37,340 >> Kjo nuk është e me të vërtetë rrënjësisht më të shpejtë. 772 00:27:37,340 --> 00:27:41,430 Sepse në qoftë se ne të vërtetë të luajë këtë për Vlerat e mëdha të N, në fund të 773 00:27:41,430 --> 00:27:44,750 ditë, për n mjaft e madhe, ajo është ende do të ndiheni goxha i ngadalshëm. 774 00:27:44,750 --> 00:27:46,770 E pra, më lejoni të marrë një Pasimi fundit në atë. 775 00:27:46,770 --> 00:27:48,920 Kjo është ajo që unë do të thërrasë lloj përzgjedhje. 776 00:27:48,920 --> 00:27:51,040 Ju Mund të djema ricilësuar veten tuaj për herë të fundit? 777 00:27:51,040 --> 00:27:53,550 Dhe në këtë rast të fundit, unë jam duke shkuar të propozojë diçka 778 00:27:53,550 --> 00:27:54,970 quajtur lloj futje. 779 00:27:54,970 --> 00:27:57,470 Lloj futje të qenit, konceptualisht, pak më ndryshe. 780 00:27:57,470 --> 00:28:00,980 >> Në vend se të shkuar mbrapa dhe me radhë dhe zgjedhjen elementin më të vogël, unë jam 781 00:28:00,980 --> 00:28:05,030 vetëm do të merret me secilin nga këto djema si unë hasin ata, dhe futur 782 00:28:05,030 --> 00:28:06,850 ato në vendin e tyre të saktë. 783 00:28:06,850 --> 00:28:10,160 Pra, unë jam vetëm duke shkuar për të filluar me Grace, dhe unë shoh se ajo është numër katër. 784 00:28:10,160 --> 00:28:11,720 Ku ka numër katër i përkasin? 785 00:28:11,720 --> 00:28:14,940 Unë nuk kanë filluar sorting asgjë, kështu Grace merr për të qëndruar të drejtë atje. 786 00:28:14,940 --> 00:28:18,355 Dhe tani unë jam duke shkuar për të kërkuar, në qoftë se ju mund të të marrë një hap për të drejtën tuaj, kjo 787 00:28:18,355 --> 00:28:21,650 lista ime e renditura, kjo është e mia Lista unsorted mbetur. 788 00:28:21,650 --> 00:28:23,260 Deri tani unë jam duke shkuar për të vazhduar më tej, dhe çfarë është emri juaj përsëri? 789 00:28:23,260 --> 00:28:23,700 >> Branson: Branson. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. Malan: Branson. 791 00:28:24,150 --> 00:28:25,375 Pra Branson është numri dy. 792 00:28:25,375 --> 00:28:27,490 Kështu që unë jam duke shkuar për të marrë ju për një moment. 793 00:28:27,490 --> 00:28:30,940 Dhe tani, ku nuk ju përkasin në këtë grup? 794 00:28:30,940 --> 00:28:32,360 Pra, për të të drejtën e të Hirit. 795 00:28:32,360 --> 00:28:35,670 Pra, përsëri, ne jemi lloj i bërë Grace bëjë shumë punë këtu. 796 00:28:35,670 --> 00:28:37,290 Ku nuk kemi vënë ju? 797 00:28:37,290 --> 00:28:40,120 Pra, ne jemi duke shkuar për rrëshqitje ju u largua, dhe futur Branson atje. 798 00:28:40,120 --> 00:28:41,680 Por tani unë pretendojnë se ju djema janë bërë. 799 00:28:41,680 --> 00:28:43,240 Por vini re, unë nuk jam duke përdorur hapësirë ​​ekstra. 800 00:28:43,240 --> 00:28:45,130 Është ende e 2 elemente këtu, 5 mbi këtu. 801 00:28:45,130 --> 00:28:47,910 Madhësia gjithsej array është 7, kështu që unë jam jo mashtrimit, të gjithë të drejtë? 802 00:28:47,910 --> 00:28:51,950 >> Pra, tani ne kemi, me Gabe këtu, numër gjashtë, ku nuk ju takon? 803 00:28:51,950 --> 00:28:52,650 Ju mori me fat përsëri. 804 00:28:52,650 --> 00:28:53,820 Pra, ju merrni për të qëndruar të drejtë atje. 805 00:28:53,820 --> 00:28:57,210 Vetëm të marrë një hap të lehtë për të drejtën vetëm për të bëjë të qartë se ju jeni duke renditura. 806 00:28:57,210 --> 00:29:00,520 Dhe tani ne kemi Neil përsëri, numrin e një, ku shkoni? 807 00:29:00,520 --> 00:29:03,540 Dhe tani është ajo ku ne do të fillojnë të shohin se ky algoritëm, edhe pse më parë 808 00:29:03,540 --> 00:29:05,950 shikim, ndihet goxha i zgjuar, watch çfarë është gati të ndodhë. 809 00:29:05,950 --> 00:29:07,370 Nëse ju mund të hap përpara. 810 00:29:07,370 --> 00:29:09,260 >> Ku duam të vënë Neil? 811 00:29:09,260 --> 00:29:11,830 Pra padyshim këtu, kështu që se si nuk kemi të merrni Neil atje? 812 00:29:11,830 --> 00:29:12,970 Le ta bëjmë këtë hap-pas-hapi. 813 00:29:12,970 --> 00:29:15,620 Gabe, ku ju duhet të shkoni? 814 00:29:15,620 --> 00:29:19,590 Yep, kështu që të marrë një hap të madh, apo dy gjysmë-hapa për të bërë 815 00:29:19,590 --> 00:29:20,820 një hap mbi atje. 816 00:29:20,820 --> 00:29:21,750 Grace, ku ju shkoni? 817 00:29:21,750 --> 00:29:22,510 Good. 818 00:29:22,510 --> 00:29:23,500 Pra, një hap tjetër. 819 00:29:23,500 --> 00:29:24,960 Dhe së fundi, Branson? 820 00:29:24,960 --> 00:29:25,460 Një hap tjetër. 821 00:29:25,460 --> 00:29:27,190 Dhe tani ne mund të vënë Neil në vend. 822 00:29:27,190 --> 00:29:28,440 >> Deri tani, të vazhdojë këtë logjikë. 823 00:29:28,440 --> 00:29:32,420 Edhe pse ne nuk jemi zhvendosur Neil mbi, dhe mbi, dhe mbi, për të vënë atë 824 00:29:32,420 --> 00:29:36,420 ku ai shkon, ne rastin keq, numri i ardhshëm ne mund të hasni mund të 825 00:29:36,420 --> 00:29:42,220 të jetë numri, të themi, ka pasur një numër zero, atëherë ne jemi duke shkuar për të zhvendosur të gjithë 826 00:29:42,220 --> 00:29:42,730 këta djema. 827 00:29:42,730 --> 00:29:44,950 Supozoni se ka një numër, negative një, atëherë ne duhet të zhvendoset 828 00:29:44,950 --> 00:29:46,080 të gjitha këto guys. 829 00:29:46,080 --> 00:29:48,500 Pra, ne jemi me të vërtetë vetëm lloji i Flipping Problemi rreth, të tilla që ne jemi 830 00:29:48,500 --> 00:29:52,620 transferimin e shpenzimeve nga Procesi i përzgjedhjes kështu shtënie 831 00:29:52,620 --> 00:29:56,930 proces, i tillë që ju djema kishte vetëm për të lëvizur diçka afërsisht n minus 832 00:29:56,930 --> 00:29:57,940 Numri i hapave. 833 00:29:57,940 --> 00:30:01,200 Dhe se numri i hapave është vetëm do për të rritur si unë zgjidhni më shumë numra, 834 00:30:01,200 --> 00:30:04,730 në qoftë se unë kam për të mbajtur shoving ju djema mbrapa, dhe prapa, dhe mbrapa. 835 00:30:04,730 --> 00:30:08,320 >> Pra, gjëja e trishtuar tani është të gjitha këto algoritme janë n katror. 836 00:30:08,320 --> 00:30:10,570 Le të shkojnë përpara dhe në sajë të këtyre djema, dhe kujtoj këto pak 837 00:30:10,570 --> 00:30:11,090 ndryshe. 838 00:30:11,090 --> 00:30:12,312 Very well done. 839 00:30:12,312 --> 00:30:14,120 >> [Duartrokitje] 840 00:30:14,120 --> 00:30:15,030 >> Dakord. 841 00:30:15,030 --> 00:30:16,280 Nuk ju shkoni. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Faleminderit për - 844 00:30:18,470 --> 00:30:19,190 >> Branson: [padëgjueshme] mbajnë numrat. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. Malan: Jo, ju mund të mbajnë numrat si. 846 00:30:21,990 --> 00:30:23,440 Dakord. 847 00:30:23,440 --> 00:30:24,100 Nicely done. 848 00:30:24,100 --> 00:30:25,300 Dakord. 849 00:30:25,300 --> 00:30:30,510 Pra, le të shohim nëse ne tani nuk mund të përmblidhni më shpejt dhe më me sy, 850 00:30:30,510 --> 00:30:33,410 saktësisht se çfarë ka ndodhur vetëm këtu si më poshtë. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Unë jam duke shkuar për të shkuar përpara dhe tërheq lart Firefox. 853 00:30:38,770 --> 00:30:41,310 Ne do të lidhin këtë demonstratë në faqen e internetit Kursin së. 854 00:30:41,310 --> 00:30:43,870 Java është një pak i bezdisshëm për të marrë të punës në disa shfletues këto ditë. 855 00:30:43,870 --> 00:30:46,760 Pra, nëse ju bëni luajë me këtë në shtëpi, kuptojnë që ju mund të kenë nevojë të përdorni Firefox 856 00:30:46,760 --> 00:30:47,990 për të marrë atë që punojnë. 857 00:30:47,990 --> 00:30:50,440 Dhe çfarë unë jam duke duke shkuar për të bëjë me këtë demonstrim është në vijim. 858 00:30:50,440 --> 00:30:54,875 >> Në fund, unë kam një bandë e tërë e options menu, duke përfshirë një fillim dhe një 859 00:30:54,875 --> 00:30:55,840 të ndalet button. 860 00:30:55,840 --> 00:30:59,450 Gjithashtu, si një mënjanë, nuk duket të jetë një bug në këto programe, ku ju 861 00:30:59,450 --> 00:31:03,720 nuk mund të vërtetë shohim fillimin ose të ndaluar button nëse ju mbani Komanda ose ALT 862 00:31:03,720 --> 00:31:06,560 plus dhe zoom në, e cila interesant ju tregon butonat më shumë. 863 00:31:06,560 --> 00:31:09,090 Pra, vetëm FYI, nëse ju luani me këtë në shtëpi. 864 00:31:09,090 --> 00:31:12,870 Tani unë jam duke shkuar për të klikoni Start në vetëm një moment, pasi specifikuar një vonesë prej, 865 00:31:12,870 --> 00:31:16,810 si, 200 milisekonda këtu, vetëm kështu që ne mund të shohim se çfarë ndodh. 866 00:31:16,810 --> 00:31:20,180 >> Kështu që unë pretendojnë se kjo është një vizualizimi i algoritmin e parë 867 00:31:20,180 --> 00:31:23,730 këta bënë, lloj flluskë, ku ne swapped njerëz palë-të mençura. 868 00:31:23,730 --> 00:31:27,490 Insajt çelësi për këtë vizualizimi është se lartësia e hekurave 869 00:31:27,490 --> 00:31:30,510 paraqet madhësinë e numrit. 870 00:31:30,510 --> 00:31:32,210 Pra shtatlartë bar, madhe numrin. 871 00:31:32,210 --> 00:31:33,680 Shorter bar, më i vogël numri. 872 00:31:33,680 --> 00:31:38,630 Dhe në qoftë se ju të vini re, ne jemi duke shkuar nëpër përsëritje e parë e këtij algoritmi, 873 00:31:38,630 --> 00:31:42,620 shkëmbejnë numrat e mëdha dhe të vogla, në mënyrë që numër i vogël vjen e para dhe 874 00:31:42,620 --> 00:31:44,280 Numri i madh shkon në të djathtë. 875 00:31:44,280 --> 00:31:48,770 >> Dhe sa më shpejt që ne të merrni në fund të array e numrave shumë më shumë se shtatë, ne jemi 876 00:31:48,770 --> 00:31:49,900 duke shkuar për të shkuar përsëri në fillim. 877 00:31:49,900 --> 00:31:51,140 Dhe parashikojnë këtë. 878 00:31:51,140 --> 00:31:54,860 Më shumë majtas, se djalë i vogël po ndodh për të bie në ujdi për të në anën, dhe kjo 879 00:31:54,860 --> 00:31:56,010 përsërit proces. 880 00:31:56,010 --> 00:31:59,450 Tani kjo vizualizimi shpejt merr mërzitshëm, kështu që më lejoni të shkoj përpara dhe të ndaluar 881 00:31:59,450 --> 00:32:04,170 ajo, të ndryshojë diçka shumë vonesë të shpejtë vetëm për të marrë tani, një të ndjehen për 882 00:32:04,170 --> 00:32:05,060 ky algoritëm. 883 00:32:05,060 --> 00:32:07,840 >> Pra, edhe pse unë kam ankorua atë, kjo është si përmirësimin procesor tim, blerja e 884 00:32:07,840 --> 00:32:08,580 një kompjuter të ri. 885 00:32:08,580 --> 00:32:12,980 Unë nuk kam ndryshuar rrënjësisht mia algorithm, por ju me të vërtetë mund të shihni më shumë 886 00:32:12,980 --> 00:32:16,800 në mënyrë të qartë sesa me njerëzit, se i madh numra janë bubbling deri në majë, 887 00:32:16,800 --> 00:32:20,900 dhe numrat e vegjël janë bubbling poshtë në fund. 888 00:32:20,900 --> 00:32:22,390 Dhe tani kjo gjë renditura këtu. 889 00:32:22,390 --> 00:32:25,260 Dhe siç një mënjanë, në sheshet, nuk ka vetëm disa llogarimbajtje atje për të 890 00:32:25,260 --> 00:32:28,010 të ju ndihmojë të llogarisin se sa krahasime, apo sa këmbime kanë 891 00:32:28,010 --> 00:32:28,950 në fakt është bërë. 892 00:32:28,950 --> 00:32:30,750 >> E pra, le të provoni njërin prej të tjerët e pamë. 893 00:32:30,750 --> 00:32:37,116 Më lejoni të klikoni mbi lloj flluskë këtu, dhe më lejoni të zgjedhin, dhe kjo faqe e tërë web 894 00:32:37,116 --> 00:32:38,936 është një buggy pak. 895 00:32:38,936 --> 00:32:41,155 Le të pranojnë rrezikun dhe drejtuar atë përsëri. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Ka të shkojmë. 898 00:32:45,030 --> 00:32:47,180 Pra, le të bëjmë lloj përzgjedhjes. 899 00:32:47,180 --> 00:32:49,140 Unë nuk e di pse menu duket mbi atje. 900 00:32:49,140 --> 00:32:54,070 Le të zoom në për të rregullojmë se bug, të ndryshojë kjo në 50. 901 00:32:54,070 --> 00:32:56,020 Ah, le të bëjë në fakt se shumë më të shpejtë. 902 00:32:56,020 --> 00:32:59,160 Pesë milliseconds apo më shumë, dhe të fillojnë. 903 00:32:59,160 --> 00:33:00,470 >> Pra, kjo është lloj përzgjedhje. 904 00:33:00,470 --> 00:33:03,070 Pra, përsëri, mendoj në lidhje me atë që ne bëri me njerëzit këtu. 905 00:33:03,070 --> 00:33:08,490 Ne shkuam nëpër rrjet dhe përzgjedhur element më i vogël përsëri, 906 00:33:08,490 --> 00:33:09,250 dhe përsëri, dhe përsëri. 907 00:33:09,250 --> 00:33:11,110 Tani unë pretendojnë se ishte ende mjaft e keqe. 908 00:33:11,110 --> 00:33:15,010 Ajo ishte n ende katror, ​​të japë ose të marrë, por ajo ishte, në botën e vërtetë, pak a 909 00:33:15,010 --> 00:33:18,280 më shpejt, sepse isha me të vërtetë duke marrë pak më pak hapat që secila kohë. 910 00:33:18,280 --> 00:33:19,800 Por ne jemi vetëm duke folur se çfarë? 911 00:33:19,800 --> 00:33:21,830 Ndoshta 40 ose kështu që bare këtu? 912 00:33:21,830 --> 00:33:23,200 Ne nuk jemi duke folur 40 milion. 913 00:33:23,200 --> 00:33:27,430 Pra, kjo nuk është krejtësisht e qartë për mua se ishte me të vërtetë një fitim të rëndësishëm. 914 00:33:27,430 --> 00:33:32,530 >> Më lejoni tani të shkojnë prapa dhe të ndryshojë në tonë algorithm e tretë, e cila ishte zgjedhur 915 00:33:32,530 --> 00:33:33,180 lloj futje. 916 00:33:33,180 --> 00:33:36,380 Dhe tani ajo është me të vërtetë buggy sepse menu me të vërtetë nuk duhet të jetë atje poshtë. 917 00:33:36,380 --> 00:33:40,840 Pra, tani ne do të lëviz mbrapa deri këtu dhe të fillojnë këtë algoritëm. 918 00:33:40,840 --> 00:33:43,270 Bërtas, të fillojë dhe të ndaluar. 919 00:33:43,270 --> 00:33:47,160 Pra, ky lloj ka një model të bukur për të atë, së cilës ne jeni të përsëri 920 00:33:47,160 --> 00:33:50,240 futur humanet, ose ne këtë rast, bare në 921 00:33:50,240 --> 00:33:52,620 vendndodhjen e tyre të përshtatshme. 922 00:33:52,620 --> 00:33:55,430 Dhe kjo është bërë tashmë para Unë u kthye. 923 00:33:55,430 --> 00:33:58,940 Por kjo, gjithashtu, në teori, është n ende katror. 924 00:33:58,940 --> 00:34:01,430 >> Pra, le të shohim nëse ne nuk mund të përmbledhim këto si vijon. 925 00:34:01,430 --> 00:34:04,750 Unë jam duke shkuar për të shkuar përpara dhe vetëm për të dhënë na lloj i një mënyrë e zakonshme e folur 926 00:34:04,750 --> 00:34:08,489 në lidhje me këto gjëra, më lejoni të prezantoj vetëm një grimë e simbol këtu. 927 00:34:08,489 --> 00:34:12,480 Ju jeni gati për të parë diçka që quhet e madhe O, sepse ajo është fjalë për fjalë një i madh 928 00:34:12,480 --> 00:34:16,320 O. Dhe kjo është një mënyrë që një kompjuter shkencëtar apo një matematikan madje përdor 929 00:34:16,320 --> 00:34:19,230 për të përshkruar kohën running e disa algorithm. 930 00:34:19,230 --> 00:34:21,400 Sa hapat e bën atë të vërtetë të marrë? 931 00:34:21,400 --> 00:34:25,080 >> Tani unë jam duke shkuar për të vë në siklet veten me dorëshkrimit të im këtu në vetëm një moment. 932 00:34:25,080 --> 00:34:29,020 Por më lejoni të shkoj përpara dhe të thonë se kjo do të jetë O madh mbi këtu. 933 00:34:29,020 --> 00:34:33,610 Dhe më lejoni të prezantoj një tjetër simbol, një omega kapitale. 934 00:34:33,610 --> 00:34:37,080 Omega do të jetë e kundërta, në thelb, i madh O. patur parasysh Big O 935 00:34:37,080 --> 00:34:40,790 do të thotë, në rastin më të keq, sa kohë mund të disa algorithm të marrë, në 936 00:34:40,790 --> 00:34:43,480 termat e n, omega është duke duke shkuar për të të jetë sa kohë mund të 937 00:34:43,480 --> 00:34:45,409 të marrë në rastin më të mirë. 938 00:34:45,409 --> 00:34:48,090 Dhe ne do të shohim se çfarë ne kuptojmë me Rasti më i mirë në një moment të vetëm. 939 00:34:48,090 --> 00:34:49,940 >> Pra, le të fillojë diçka e thjeshtë. 940 00:34:49,940 --> 00:34:54,719 Më lejoni të filloj me një kërkim linear. 941 00:34:54,719 --> 00:34:55,679 Pra, nuk sorting. 942 00:34:55,679 --> 00:34:58,000 Ne do të quajmë këtë kërkim linear. 943 00:34:58,000 --> 00:35:01,140 Dhe tani, të bëjë pak Tabela nga kjo. 944 00:35:01,140 --> 00:35:06,600 Dhe tani, në rastin e kërkimit lineare, në rastin më të keq, sa hapa është 945 00:35:06,600 --> 00:35:11,770 ajo do të marrë mua për të gjetur një Numri i zgjedhjes arbitrare? 946 00:35:11,770 --> 00:35:14,540 Dhe nuk ka dyert e n totali i ose n numra totale. 947 00:35:14,540 --> 00:35:15,940 Rasti më i keq. 948 00:35:15,940 --> 00:35:18,800 Sa hapa jam unë do të duhet të të marrë për të të gjetur numrin 50 në një array 949 00:35:18,800 --> 00:35:20,830 i dyerve n? 950 00:35:20,830 --> 00:35:21,410 Dhe pse? 951 00:35:21,410 --> 00:35:23,680 Për shkak se ajo mund të jetë mbi të gjitha mënyrë mbi onto në fund. 952 00:35:23,680 --> 00:35:27,120 Pra, shumë si Jennifer hasur, numër 50 ishte e gjitha rruga e gjatë, kështu që në 953 00:35:27,120 --> 00:35:30,760 kërko keq rasti linear është e madhe O n, ne do të themi. 954 00:35:30,760 --> 00:35:33,430 >> Po në lidhje me rastin më të mirë, në qoftë se ju merrni të vërtetë me fat? 955 00:35:33,430 --> 00:35:36,200 Ajo është vetëm duke shkuar për të të marrë një hap, ose një numër konstant i hapa. 956 00:35:36,200 --> 00:35:37,830 Pra, ne do të përshkruaj se si 1. 957 00:35:37,830 --> 00:35:39,010 Pra, kjo është shumë e mirë. 958 00:35:39,010 --> 00:35:41,210 Tani çfarë nëse ne e bëmë diçka të doja kërkimin binar? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Kërko Pra binar, në më të keq rast, mori sa kohë? 961 00:35:47,846 --> 00:35:49,250 >> [Mbivendosje VOICES] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. Malan: Pra, në fakt, unë dëgjuar atë në disa vende çift. 963 00:35:51,310 --> 00:35:56,390 Pra, kjo është në të vërtetë hyni n, të japë ose të marrë, sepse si ne e ndajnë listën në gjysmën e 964 00:35:56,390 --> 00:36:00,730 përsëri, dhe përsëri, dhe përsëri, ne jemi në gjendje për të gjetur, në fund të fundit, vlera, 965 00:36:00,730 --> 00:36:04,750 në qoftë se ajo është atje, por ka një kapur. 966 00:36:04,750 --> 00:36:08,590 Çfarë është supozimi se ne kemi për të marrë për të dhënë për kërkimin binar? 967 00:36:08,590 --> 00:36:09,700 Ajo ka të zgjidhet. 968 00:36:09,700 --> 00:36:12,770 Kjo nuk është e renditur, ju mund të ndarë gjë në gjysmën përsëri dhe përsëri, dhe ju 969 00:36:12,770 --> 00:36:15,490 mund të shkoni majtas, dhe ju mund të shkoni të drejtë, dhe ju mund të shkoni majtas dhe djathtas, por ju jeni 970 00:36:15,490 --> 00:36:18,070 nuk shkojnë për të gjetur elementin nëse lista nuk është e renditura, për shkak se 971 00:36:18,070 --> 00:36:18,790 ju mund të humbasë atë. 972 00:36:18,790 --> 00:36:22,120 Sepse orientues tënd, për të shkuar majtas ose djathtas do të jetë me të meta në qoftë se është 973 00:36:22,120 --> 00:36:23,420 me të vërtetë nuk e renditura. 974 00:36:23,420 --> 00:36:26,110 Pra, ka një lloj kosto fshehur për të duke përdorur diçka si kjo. 975 00:36:26,110 --> 00:36:29,250 >> Tani, le të shkojë në klasifikim tonë Algoritme jo kërkim - 976 00:36:29,250 --> 00:36:31,140 oh, në të vërtetë le të shkojë në këtë bosh. 977 00:36:31,140 --> 00:36:33,190 Kërko Binary në rastin më të mirë? 978 00:36:33,190 --> 00:36:36,290 Është gjithashtu e 1 nëse kjo ndodh vetëm që të jetë në shumë mes i vektorit, ose 979 00:36:36,290 --> 00:36:37,810 mesme e librit të telefonit. 980 00:36:37,810 --> 00:36:39,710 Tani le të bëjmë lloj flluskë. 981 00:36:39,710 --> 00:36:42,570 Pra, përsëri, tani ne jemi duke hyrë në llojet jo, kërkime. 982 00:36:42,570 --> 00:36:47,220 >> Në rastin më të keq, sa hapa bëri ne flluskë pretendimi lloj do të marrë? 983 00:36:47,220 --> 00:36:48,410 n katror. 984 00:36:48,410 --> 00:36:49,200 Kështu që unë jam duke shkuar për të nxjerrë se. 985 00:36:49,200 --> 00:36:51,710 Ooh, lloj shkrimi im duket edhe më keq kur është parashikuar se madhe. 986 00:36:51,710 --> 00:36:52,510 Dakord. 987 00:36:52,510 --> 00:36:53,570 Pra, kjo është n katror. 988 00:36:53,570 --> 00:36:59,460 Dhe në rastin më të mirë të lloj flluskë, sa hapa është ajo do të marrë? 989 00:36:59,460 --> 00:37:00,980 1, I dëgjohet. 990 00:37:00,980 --> 00:37:01,760 >> Kryetari 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. Malan: n, kam dëgjuar. 992 00:37:03,286 --> 00:37:04,200 >> Kryetari 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. Malan: 2, kam dëgjuar. 994 00:37:05,010 --> 00:37:06,670 A kam dëgjuar 3? 995 00:37:06,670 --> 00:37:07,080 Dakord. 996 00:37:07,080 --> 00:37:11,390 Kështu që unë kam dëgjuar 1, n, 2, por le të marr përveç pakten parë e atyre 997 00:37:11,390 --> 00:37:12,330 sugjerime, 1. 998 00:37:12,330 --> 00:37:15,370 Kjo nuk është një instinkt i keq, sepse ajo lloj i ndjek një model këtu. 999 00:37:15,370 --> 00:37:19,670 Por në qoftë se ajo merr vetëm 1 hap, si në Bota mund të pohoj se lista 1000 00:37:19,670 --> 00:37:22,900 është e renditura, sepse në qoftë se unë jam i lejuar vetëm për të marrë 1 hap, sa elemente 1001 00:37:22,900 --> 00:37:25,230 mund të unë në fakt të kontrolloni të jetë i sigurt? 1002 00:37:25,230 --> 00:37:28,270 E pra, vetëm 1, që do të thotë nuk ka n minus 1 elemente që mund të jetë jashtë 1003 00:37:28,270 --> 00:37:31,310 mënyrë, dhe unë jam vetëm duke shkuar në besim pas në kërkim at 1 element të se 1004 00:37:31,310 --> 00:37:31,850 gjë është e renditura. 1005 00:37:31,850 --> 00:37:33,930 Pra 1 po jo korrigjuar këtu. 1006 00:37:33,930 --> 00:37:35,710 Pra minimalisht, se sa shumë nuk kam për të shikoni në? 1007 00:37:35,710 --> 00:37:36,680 >> [Mbivendosje VOICES] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. Malan: n minus 1, ose vërtetë, n, për shkak se kam nevojë për të shikojmë në çdo 1009 00:37:40,160 --> 00:37:42,190 element të sigurohemi që kjo nuk është jashtë rendit. 1010 00:37:42,190 --> 00:37:44,750 Por përsëri, ne do lloj i valë tonë Duart në numër më të vogël dhe 1011 00:37:44,750 --> 00:37:47,100 supozojmë se, si n merr të mëdha, ata janë jointeresant anyway. 1012 00:37:47,100 --> 00:37:48,380 Pra, kjo është lloj flluskë. 1013 00:37:48,380 --> 00:37:49,830 Dhe tani, le të bëjë këto dy të fundit. 1014 00:37:49,830 --> 00:37:53,520 Lloj përzgjedhje, dhe pastaj ne do të të bëni lloj futje. 1015 00:37:53,520 --> 00:37:57,160 Dhe pastaj ne do të fryj Juaj Mendjet me diçka shumë 1016 00:37:57,160 --> 00:37:58,926 më mirë se të gjitha këto. 1017 00:37:58,926 --> 00:38:00,410 Dakord. 1018 00:38:00,410 --> 00:38:04,700 >> Cila është rasti më i keq running koha e lloj përzgjedhjes? 1019 00:38:04,700 --> 00:38:05,680 >> Kryetari 4: n katror. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. Malan: n katror, ​​unë jam duke dëgjuar. 1021 00:38:06,710 --> 00:38:09,790 Por pse n katror, ​​intuitivisht? 1022 00:38:09,790 --> 00:38:11,170 >> Kryetari 4: Sepse ne vetëm e bëri atë. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. Malan: Sepse ne vetëm e bëri atë. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Mirë përgjigje. 1026 00:38:13,380 --> 00:38:16,660 Por intuitivisht, pse është zgjedhja Lloj n katror? 1027 00:38:16,660 --> 00:38:18,980 Çfarë kemi të bëjmë përsëri dhe përsëri? 1028 00:38:18,980 --> 00:38:22,570 Ne kishim për të mbajtur skanim me anë të, janë ju vogli, janë të që ju 1029 00:38:22,570 --> 00:38:24,020 vogël, jeni më të vogël. 1030 00:38:24,020 --> 00:38:27,480 Dhe të dhënë, ne ishim në gjendje për të marrë n hapa, pastaj n minus 1, pastaj n minus 2. 1031 00:38:27,480 --> 00:38:30,700 Por në qoftë se ju lloj i shtoni ato të gjithë lart, ose të marrë atë në besimin që unë kam shtuar 1032 00:38:30,700 --> 00:38:34,810 ato paraprakisht, ne kemi marrë afërsisht n katror minus disa numra të vogla. 1033 00:38:34,810 --> 00:38:36,730 Kështu që unë jam duke shkuar për të thirrur këtë n katror. 1034 00:38:36,730 --> 00:38:39,530 Por me lloj përzgjedhjes në më të mirë rasti, sa hapa është ajo 1035 00:38:39,530 --> 00:38:40,632 duke shkuar për të marrë mua? 1036 00:38:40,632 --> 00:38:41,840 >> Kryetari 5: [padëgjueshme] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. Malan: Kjo është për fat të keq ende të n squared, e drejtë? 1038 00:38:44,350 --> 00:38:49,590 Sepse në qoftë se unë jam zgjedhur më të vogël element, dhe ne kishim shtatë njerëz këtu, 1039 00:38:49,590 --> 00:38:53,280 Unë vetëm e di, një herë unë të shkoj në shumë fundi, që unë e kam gjetur më i vogël 1040 00:38:53,280 --> 00:38:55,670 numrin, kudo që ai ose ajo mund të ketë qenë. 1041 00:38:55,670 --> 00:38:58,820 Por si mund ta gjej e ardhshëm numri më i vogël? 1042 00:38:58,820 --> 00:39:00,160 Unë duhet të bëni një tjetër abone. 1043 00:39:00,160 --> 00:39:04,810 Pra, në rastin më të mirë, çfarë është input për lloj përzgjedhjes? 1044 00:39:04,810 --> 00:39:07,830 Kjo është një tashmë listë lloj, numër një, Numri dy, numri tre, numër katër. 1045 00:39:07,830 --> 00:39:08,600 Por unë jam një kompjuter. 1046 00:39:08,600 --> 00:39:10,190 Unë vetëm mund të shohim në një gjë në një kohë. 1047 00:39:10,190 --> 00:39:12,465 Unë nuk mund të lloj të marrë një hap përsëri si një njeri dhe të thonë, 1048 00:39:12,465 --> 00:39:14,030 ooh, kjo duket e saktë. 1049 00:39:14,030 --> 00:39:17,580 >> Unë vetëm mund të gjykojnë korrektësi në lloj përzgjedhje duke përzgjedhur 1050 00:39:17,580 --> 00:39:18,370 numri më i vogël. 1051 00:39:18,370 --> 00:39:21,390 Por edhe në qoftë se unë të gjeni një numër të parë, në qoftë se unë nuk di asgjë tjetër në lidhje 1052 00:39:21,390 --> 00:39:24,460 numrat e tjera, të cilat unë nuk e bëjnë, të gjitha unë e di se unë kam qenë i dorëzoi një sërë 1053 00:39:24,460 --> 00:39:27,930 ose një grup i dyerve prapa të cilave janë Numrat, e vetmja mënyrë unë e di se një 1054 00:39:27,930 --> 00:39:28,680 ishte më i vogël? 1055 00:39:28,680 --> 00:39:32,440 Nëse unë të marrë të gjithë rrugën këtu dhe e kuptojnë, Damn, njëri ishte me të vërtetë i vogël. 1056 00:39:32,440 --> 00:39:34,870 >> Por si mund unë atëherë të përcaktojë se dy është më i vogël e ardhshme? 1057 00:39:34,870 --> 00:39:38,350 Duke bërë paefektshmërinë njëjtin përsëri dhe përsëri. 1058 00:39:38,350 --> 00:39:42,210 Pra, në fund, me lloj futje, se, ne rastin keq, 1059 00:39:42,210 --> 00:39:44,990 nuk themi kryen atë? 1060 00:39:44,990 --> 00:39:49,100 Kjo shumë është n katror. 1061 00:39:49,100 --> 00:39:53,020 Dhe si në lidhje me rastin më të mirë? 1062 00:39:53,020 --> 00:39:56,282 Ne do të lënë atë si një cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Ne do të plotësoni në atë kohë bosh ardhshëm, por së pari më lejoni të propozoj që ne 1064 00:40:00,090 --> 00:40:02,620 rrënjësisht të bëjë më mirë se të gjitha këto, të gjithë të drejtë? 1065 00:40:02,620 --> 00:40:05,220 >> Pra, mendoni për veten se çfarë shtënie Rendit do të jetë. 1066 00:40:05,220 --> 00:40:06,910 E pra, që nuk ishte shumë dramatike, sepse unë jam i vetmi 1067 00:40:06,910 --> 00:40:08,970 se pa ndryshim. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Pra, këtu kemi një disi demonstrim të ndryshme. 1071 00:40:12,615 --> 00:40:16,580 Nëse unë zoom në këtu, ju do të shihni se në majtas ne kemi lloj flluskë, në 1072 00:40:16,580 --> 00:40:20,740 mesme ne kemi lloj përzgjedhje, dhe mbi ekstremit të djathtë, ne kemi diçka që ne 1073 00:40:20,740 --> 00:40:23,380 nuk e kanë shikuar ende quajtur bashkojë lloj. 1074 00:40:23,380 --> 00:40:26,080 Por e konsiderojnë atë që ne kemi qenë të duke bërë këtu deri tani sot. 1075 00:40:26,080 --> 00:40:29,200 Kur Jennifer e parë doli në skenë, shkuam nëpër rrjet të numrave 1076 00:40:29,200 --> 00:40:33,750 përsëri, dhe përsëri, me kërkim linear, dhe kemi marrë kohën lineare të rrjedhshëm, i madh o 1077 00:40:33,750 --> 00:40:35,100 i n, në mënyrë që të flet. 1078 00:40:35,100 --> 00:40:41,000 >> Kur ne tani e konsiderojnë javën e parë të klasë, kur ne kishim përça dhe sundo, 1079 00:40:41,000 --> 00:40:43,740 dhe ne kishim librin e telefonit marramendës, dhe Jennifer, dhe ne kolektivisht 1080 00:40:43,740 --> 00:40:47,500 leveraged që pasqyrë e kyç, i cili ishte për të përsëris veten përsëri dhe përsëri nga 1081 00:40:47,500 --> 00:40:50,930 disi hedhur larg, duke hedhur larg, hedhur larg, gjysma e problemit, ose 1082 00:40:50,930 --> 00:40:55,320 në përgjithësi, duke e ndarë një problem në gjysmë, dhe pastaj trajtimin copë të vogël të 1083 00:40:55,320 --> 00:40:59,630 Problemi si konceptualisht ekuivalent për tjetrin, ne disi e bëri 1084 00:40:59,630 --> 00:41:00,910 rrënjësisht të mirë. 1085 00:41:00,910 --> 00:41:04,720 Por me lloj flluskë, me përzgjedhje lloj, me lloj futje, ne kemi mund 1086 00:41:04,720 --> 00:41:06,560 nuk ka njohuri të tilla që Jennifer bëri. 1087 00:41:06,560 --> 00:41:10,220 Ne pretty much vetëm ecte prapa dhe radhë një bandë e tërë e kohës, dhe ne 1088 00:41:10,220 --> 00:41:12,650 gjërat tweaked pak, shkëmbejnë në këtë mënyrë, ndoshta 1089 00:41:12,650 --> 00:41:13,730 futur ose zgjedhjen. 1090 00:41:13,730 --> 00:41:16,950 Por në fund të ditës, unë e bëri një shumë të ecin vështirë mbrapa dhe me radhë. 1091 00:41:16,950 --> 00:41:21,160 Ne nuk e bëri me të vërtetë diçka të levave i zgjuar si Jennifer bëri si ndarëse 1092 00:41:21,160 --> 00:41:22,040 dhe pushtues. 1093 00:41:22,040 --> 00:41:25,620 >> Pra bashkojë lloj, nga ana tjetër, të cilin ne nuk do të shohin deri javën e ardhshme, ajo do 1094 00:41:25,620 --> 00:41:29,540 të levave se ideja kryesore duke pjesëtuar input, dhe pastaj të përgjysmuar, dhe pastaj 1095 00:41:29,540 --> 00:41:30,580 përgjysmuar, dhe pastaj të përgjysmuar. 1096 00:41:30,580 --> 00:41:34,590 Dhe në çdo përsëritje e asaj lak, sorting gjysmën e majtë, dhe e drejtë 1097 00:41:34,590 --> 00:41:38,200 gjysma, atëherë gjysma e majtë e gjysmës së majtë, dhe gjysma e djathtë e të majtë, atëherë 1098 00:41:38,200 --> 00:41:40,990 gjysma e majtë e gjysmës së djathtë, dhe gjysma e drejta e gjysmës së djathtë. 1099 00:41:40,990 --> 00:41:42,840 Dhe duke përsëritur përsëri dhe përsëri. 1100 00:41:42,840 --> 00:41:46,170 >> Pra, ju do të shihni këtë vizualisht, por kjo është ajo që na pret javën e ardhshme. 1101 00:41:46,170 --> 00:41:49,760 Dhe në përgjithësi, kur ne mendojmë pak pak e vështirë për çdo problem të tillë. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Ne kemi n katror në të majtë, n në katror në qendër, dhe n 1104 00:41:57,970 --> 00:41:59,400 hyni N në të djathtë. 1105 00:41:59,400 --> 00:42:00,590 Pra, nuk ka cliffhanger juaj i vërtetë. 1106 00:42:00,590 --> 00:42:02,040 Ne do të shohim ju në hënën. 1107 00:42:02,040 --> 00:42:05,163 >> [Duartrokitje]