1 00:00:00,000 --> 00:00:11,100 >> [Daqq tal-mużika] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. Malan: Kull dritt. 3 00:00:11,490 --> 00:00:12,170 Allura merħba lura. 4 00:00:12,170 --> 00:00:15,180 Dan huwa CS50, u l huwa l-aħħar ta 'tliet ġimgħat. 5 00:00:15,180 --> 00:00:17,770 >> Allura mfakkra fl-aħħar ġimgħat, aħna kont qed infiq pjuttost ftit ta ' 6 00:00:17,770 --> 00:00:20,820 ħin fuq C, dwar l-ipprogrammar, fuq sintassi. 7 00:00:20,820 --> 00:00:24,680 U huwa pjuttost normali, jekk int xorta tissara mal-problema Set 2, li jkun 8 00:00:24,680 --> 00:00:25,950 banging ras tiegħek kontra l-ħajt. 9 00:00:25,950 --> 00:00:28,310 Huwa messaġġi ta 'żball cryptic li tħares u bugs li inti 10 00:00:28,310 --> 00:00:29,220 ma tistax pjuttost chase isfel. 11 00:00:29,220 --> 00:00:32,310 Minħabba, mistrieħ assigurat, li fi ftit żmien ftit ġimgħat int ser tħares lura fuq 12 00:00:32,310 --> 00:00:35,930 affarijiet simili Caesar, u [? V-genair,?] forsi anki jixxaqqaq, u 13 00:00:35,930 --> 00:00:40,050 jirrealizzaw kemm inti ħadthom ġejjin fil-perjodu qasir ta 'żmien. 14 00:00:40,050 --> 00:00:43,670 Allura jekk dan huwa xi konsolazzjoni, hang fil hemm għal issa. 15 00:00:43,670 --> 00:00:46,610 >> Illum, għalkemm, aħna jibdew transizzjoni għal affarijiet livell ogħla. 16 00:00:46,610 --> 00:00:49,820 U aħna jibdew jieħdu għal mogħtija li inti guys taf kif program, jew 17 00:00:49,820 --> 00:00:52,090 inqas il-bidu ta ' dak il-livell kumdità. 18 00:00:52,090 --> 00:00:56,520 U aħna ser tibda biex jikkunsidraw kif nistgħu tmur dwar tfassil ta 'programmi aktar 19 00:00:56,520 --> 00:00:57,440 b'mod effettiv. 20 00:00:57,440 --> 00:01:01,090 Kif nistgħu tmur dwar ottimizzat l- effiċjenza ta 'algoritmi tagħna, u 21 00:01:01,090 --> 00:01:03,110 ġeneralment soluzzjoni aktar problemi interessanti. 22 00:01:03,110 --> 00:01:06,850 U jibdew jieħdu għal mogħtija li, jekk ridna li, nistgħu kodiċi up xi 23 00:01:06,850 --> 00:01:08,350 mill-eżempji li għandna fil-moħħ. 24 00:01:08,350 --> 00:01:11,430 Allura llum, aħna ma tmissx il-keyboard għal kwalunkwe forma ta 'kodiċi. 25 00:01:11,430 --> 00:01:15,150 Huwa ser jiġi livell ħafna ogħla, u finalment, dwar soluzzjoni tal-problemi. 26 00:01:15,150 --> 00:01:20,490 >> Allura biex tikseb dak il-punt, let me tipproponi li l-seba ġej 27 00:01:20,490 --> 00:01:24,290 rettangoli jirrappreżentaw seba bibien, wara li huma mazz sħiħ ta ' 28 00:01:24,290 --> 00:01:26,340 numri, li fosthom huwa n-numru 50. 29 00:01:26,340 --> 00:01:30,470 Let me proġett dan fuq dan screen hawnhekk ukoll. 30 00:01:30,470 --> 00:01:36,770 U jipproponu li għandna bżonn voluntier biex tgħin sabiex tinstab me numru quddiem 31 00:01:36,770 --> 00:01:38,140 l-internet hawn biex tara. 32 00:01:38,140 --> 00:01:40,755 Come on up, fil-roża. 33 00:01:40,755 --> 00:01:43,050 Kull dritt. 34 00:01:43,050 --> 00:01:43,930 X'hemm isem tiegħek? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [inaudible] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. Malan: Jiddispjacini? 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 Kull dritt, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Nizza li jissodisfaw inti. 41 00:01:47,630 --> 00:01:48,370 Come fuq up. 42 00:01:48,370 --> 00:01:52,430 Allura dawn hawn huma seba 'bibien, u liema Nixtieq li tagħmel għalina hawnhekk, 43 00:01:52,430 --> 00:01:56,560 quddiem ta 'kollha ta' klassi tiegħek, huwa issibna-numru, 50. 44 00:01:56,560 --> 00:02:00,860 Biex issib numru, inti tista Peek wara xi wieħed minn dawn il-bibien billi sempliċiment ttektek 45 00:02:00,860 --> 00:02:03,030 fuq waħda mill-bibien, u se jiżvelaw in-numru tiegħu. 46 00:02:03,030 --> 00:02:06,080 U ejja ara kif malajr inti tista 'issibna in-numru, 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 jsir. 54 00:02:17,350 --> 00:02:18,040 Kull dritt. 55 00:02:18,040 --> 00:02:19,906 Round ta 'applause għall Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Applause] 57 00:02:21,530 --> 00:02:22,320 >> Kull dritt. 58 00:02:22,320 --> 00:02:25,254 Allura dak li kien l-istrateġija tiegħek għall konstatazzjoni tal-numru, 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Um, ħsibt forsi jekk - 60 00:02:27,222 --> 00:02:27,714 [Inaudible] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. Malan: Oh. 62 00:02:28,206 --> 00:02:29,630 Agħti tieni waħda. 63 00:02:29,630 --> 00:02:32,420 Hekk kien istrateġija tiegħek għall konstatazzjoni tal-numru, 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: So I biss tibda fl- bidu biex tara dak li l-ewwel numru 65 00:02:34,760 --> 00:02:38,590 kien, u mbagħad ħsibt, forsi jekk dawn qed magħżula, jien ser biss iżommu 66 00:02:38,590 --> 00:02:39,970 tapping ogħla up? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. Malan: OK. 68 00:02:40,140 --> 00:02:42,910 U aħna jidhru li sabu dan ikun il-każ. 69 00:02:42,910 --> 00:02:45,670 Għalkemm, ejja qaxxar il-saffi biss ftit, u inti tixtieq li tmur 70 00:02:45,670 --> 00:02:47,640 quddiem u jiżvelaw l-bibien oħra inti tista għażilt? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Oh, għeżież. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. Malan: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: So I biss ltqajna xxurtjati. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. Malan: Allura inti ltqajna xxurtjati. 76 00:02:55,270 --> 00:02:55,710 Kull dritt. 77 00:02:55,710 --> 00:02:56,795 Allura mhux ħażin. 78 00:02:56,795 --> 00:02:58,750 Imma thats interessanti għarfien, id-dritt? 79 00:02:58,750 --> 00:03:01,870 Jekk inti preżunt, u għamilt tikseb, tabilħaqq, daqsxejn xxurtjati hemmhekk. 80 00:03:01,870 --> 00:03:05,350 Imma jekk inti jassumi li n-numri kienu magħżula, inti tista 'tkun aktar preċiża 81 00:03:05,350 --> 00:03:08,750 dwar kif dik influwenzati imġieba tiegħek? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Mela jekk kienu magħżula, I ħsibt forsi iżgħar sa l-akbar. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. Malan: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: Jew jekk dan spiċċa biex tkun verament kbir, allura akbar għall-iżgħar. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. Malan: OK. 86 00:03:15,540 --> 00:03:18,170 Allura akbar biex iżgħar, jew iżgħar sa l-akbar. 87 00:03:18,170 --> 00:03:21,990 Iżda let me tipproponi, ejja ngħidu li inti kellhom gotten unlucky, u jissoponi li 88 00:03:21,990 --> 00:03:26,840 ma kinux, fil-fatt, magħżula, kemm ta ' dawk bibien jistgħu kellek Peek 89 00:03:26,840 --> 00:03:28,590 lura f'dak agħar każ? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Kollha kemm huma. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. Malan: Kollha kemm huma. 92 00:03:30,420 --> 00:03:31,740 Mela ejja tiġġeneralizza li bħala n. 93 00:03:31,740 --> 00:03:34,790 Jiġri li jkun hemm 7, imma ejja aktar ġeneralment jgħidu hemm bibien n fuq il- 94 00:03:34,790 --> 00:03:35,650 iskrin hawn. 95 00:03:35,650 --> 00:03:40,110 Allura fl-agħar każ, inti jkollok tfittex wara 7 bibien, jew bibien n. 96 00:03:40,110 --> 00:03:44,140 U hekk dan huwa verament, huwa daqsxejn ta ' Xorti llum, iżda huwa verament lineari 97 00:03:44,140 --> 00:03:46,440 algoritmu ta 'tipi, anki jekk inti kienu tip ta taqbeż is-site madwar. 98 00:03:46,440 --> 00:03:47,080 Huwa li ġust? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Yeah. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. Malan: Well, let me ara jekk tiegħek bidliet istrateġija jekk I twassalna lejn 101 00:03:50,000 --> 00:03:52,190 tieni eżempju tagħna hawn 7 bibien differenti. 102 00:03:52,190 --> 00:03:55,240 Numri istess, iżda dan darba li huma magħżula. 103 00:03:55,240 --> 00:03:58,350 X'hemm istrateġija tiegħek hawn se tkun, jippruvaw joħolqu minn moħħok dak 104 00:03:58,350 --> 00:03:59,310 in-numri l-oħra kienu - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. Malan: - qabel? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Nibdew l-ewwel waħda. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. Malan: Kull dritt. 109 00:04:03,540 --> 00:04:05,190 Jibda bl-ewwel wieħed. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Issa fejn inti se jmorru, u għaliex? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 huwa verament żgħir. 113 00:04:10,040 --> 00:04:12,500 Mela jekk dawn qed sort forsi iżgħar biex akbar, għandu 114 00:04:12,500 --> 00:04:13,290 jkun id-doppju dak, u -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. Malan: OK. 116 00:04:13,670 --> 00:04:15,990 Ejja naraw, li taħseb? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Ipprova l-aħħar wieħed. 118 00:04:19,050 --> 00:04:19,500 Nizza. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. Malan: Ħafna nicely jsir. 120 00:04:20,880 --> 00:04:21,860 Kull dritt. 121 00:04:21,860 --> 00:04:23,010 >> [Applause] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. Malan: OK. 123 00:04:24,310 --> 00:04:26,790 Allura int fil-fatt tagħmel dan horribly, għax int 124 00:04:26,790 --> 00:04:27,700 tagħmel dan tajjeb ħafna. 125 00:04:27,700 --> 00:04:31,150 Li tħalli us kapaċi jagħmlu ċerti punti. 126 00:04:31,150 --> 00:04:32,565 Mela ejja jippruvaw li roll lura hawn. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. Malan: Tajjeb ħafna jsir, madankollu. 129 00:04:35,980 --> 00:04:39,060 Allura bdejt fil-bidu, inti raw li kien 4, allura inti 130 00:04:39,060 --> 00:04:40,240 tmexxa għall-aħħar. 131 00:04:40,240 --> 00:04:42,320 Imma ejja ngħidu li inti ma tikseb xxurtjati hemm, u jissoponi 50 132 00:04:42,320 --> 00:04:42,890 kien x'imkien ieħor. 133 00:04:42,890 --> 00:04:46,190 What tielet pass tiegħek kienu? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Mur lura għall-bidu. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. Malan: Mur lura għall-bidu. 136 00:04:48,320 --> 00:04:51,320 OK, sabiex inti stajt mimsus dan il-bieb, li kienet ta '8. 137 00:04:51,320 --> 00:04:51,660 Kull dritt. 138 00:04:51,660 --> 00:04:52,650 Allura li mhux 50. 139 00:04:52,650 --> 00:04:55,380 Fejn kieku inti ħarsu jmiss? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Jekk jien ma jafu li magħżula. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. Malan: Korretta. 142 00:04:57,005 --> 00:04:58,490 Ukoll, jekk inti ma taf kienu magħżula - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Oh, ma taf, yeah. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. Malan: - imma inti ma taf fejn 50 kien għadhom? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Just iżommu għaddejjin. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. Malan: Kull dritt. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Jibqgħu għaddejjin. 149 00:05:03,800 --> 00:05:05,270 OK, li I jistgħu jaħdmu ma '. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. Malan: Issa, jekk int biss ser jibqgħu għaddejjin, x'hemm tiegħek 152 00:05:07,210 --> 00:05:09,680 algoritmu jiddevolvu appoġġjati fil. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: Il lineari -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. Malan: Huwa tip ta 'lineari. 155 00:05:11,820 --> 00:05:13,480 Iżda let me tipproponi, let me jitqiegħdu fuq il-post. 156 00:05:13,480 --> 00:05:14,900 Let me jġedded il-paġna. 157 00:05:14,900 --> 00:05:17,120 istess numru, l-istess arranġament, istess bibien. 158 00:05:17,120 --> 00:05:21,350 Iżda naħseb lura għal dak l-ewwel jum klassi meta aħna Tore ktieb tat-telefon fil- 159 00:05:21,350 --> 00:05:25,480 nofs, tip ta ', u dak li kien istrateġija tagħna hemm? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Ibda fl-nofs. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. Malan: OK. 162 00:05:26,690 --> 00:05:27,610 Allura tibda fil-nofs. 163 00:05:27,610 --> 00:05:28,790 Mela ejja imorru quddiem u jissimulaw dak. 164 00:05:28,790 --> 00:05:30,720 Ibda fl-nofs minn tiżvela dak il-bieb. 165 00:05:30,720 --> 00:05:31,660 Allura n-numru 16. 166 00:05:31,660 --> 00:05:35,290 Allura dak li l-Guy qawwija għamlu, li Tore-ktieb tat-telefon fil nofs, 167 00:05:35,290 --> 00:05:38,450 biex jiksbu l-raden jmiss? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Mur Din it-taqsima. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. Malan: U għaliex għad-dritt? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Jekk dawn kienu tip ta 'iżgħar għall-akbar, allura 50 għandu jkun 171 00:05:43,900 --> 00:05:44,720 fi dak il-għan. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. Malan: Tajba. 173 00:05:44,920 --> 00:05:45,390 Totalment raġonevoli. 174 00:05:45,390 --> 00:05:48,380 Allura bħal ktieb tat-telefon, inti tmur għall- dritt kif oppost għad-xellug, iżda hawnhekk 175 00:05:48,380 --> 00:05:49,500 hija l-muftieħ takeaway. 176 00:05:49,500 --> 00:05:53,930 Inti tista 'issa armih, jew tiċrita off, nofs ta 'din il-problema, jħalli inti ma 177 00:05:53,930 --> 00:05:55,970 ma '7 bibien, imma verament biss ma 3. 178 00:05:55,970 --> 00:05:57,870 Liema hija bejn wieħed u ieħor nofs il- daqs tal-problema. 179 00:05:57,870 --> 00:05:58,350 Kull dritt. 180 00:05:58,350 --> 00:06:01,890 Allura issa dak li inti jkollok jsir wara li inti tmur id-dritt? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Allura 16 għadu pjuttost żgħir, relattiv għal 50, hekk forsi I ser nippruvaw, 182 00:06:05,870 --> 00:06:06,700 simili, dan wieħed. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. Malan: Kull dritt. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Kull dritt, hekk issa x'hemm tiegħek istint tghidlek? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: I tista tarmi l bogħod dan u mbagħad biss - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. Malan: OK. 188 00:06:12,360 --> 00:06:14,212 Tajba, inti tista tarmi l bogħod in-nofs xellugi hemmhekk. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - pick dan wieħed. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. Malan: U d-dritt. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Yeah. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. Malan: Allura anke jekk huwa diffiċli biex tara forsi, meta jkun hemm biss 193 00:06:17,820 --> 00:06:21,320 7 bibien, jaħsbu dwar, issa, il-konsistenza tal- 194 00:06:21,320 --> 00:06:22,620 Algoritmu inti biss applikati. 195 00:06:22,620 --> 00:06:24,510 Fil-każ preċedenti, għamilt tikseb xxurtjati, li kien kbir. 196 00:06:24,510 --> 00:06:26,540 Imma inti ma tuża heuristic, Jien ngħid. 197 00:06:26,540 --> 00:06:29,150 Inti użati tip ta 'instincts tiegħek, u jkunu jafu magħżula, jekk huwa pretty 198 00:06:29,150 --> 00:06:31,600 żgħir fil-bidu, ovvjament, konna ltqajna biex tmur aktar lejn il-lemin. 199 00:06:31,600 --> 00:06:34,990 Iżda f'xi sens, inti ltqajna xxurtjati, għaliex forsi dan kien in-numru 100, 200 00:06:34,990 --> 00:06:36,220 u forsi 50 kien aktar fin-nofs. 201 00:06:36,220 --> 00:06:37,910 Forsi 50 kien saħansitra hawn fuq. 202 00:06:37,910 --> 00:06:40,960 >> Imma dak li għamilt ftit differenti din id-darba kien, għamilt l-istess ħaġa 203 00:06:40,960 --> 00:06:42,150 ġdid u għal darb'oħra. 204 00:06:42,150 --> 00:06:45,310 U nixtieq jargumentaw li dak li inti biss ma, għalkemm influwenzati mill-telefon 205 00:06:45,310 --> 00:06:48,100 eżempju ktieb, hija xi ħaġa ferm aktar algorithmic, u ħafna 206 00:06:48,100 --> 00:06:49,930 inqas speċjali b'għata. 207 00:06:49,930 --> 00:06:51,620 Ħafna inqas istintiv. 208 00:06:51,620 --> 00:06:57,160 Għalhekk fl-aħħar tal-ġurnata, kif kieku tiddeskrivi l-effiċjenza ta 'l- 209 00:06:57,160 --> 00:07:00,530 ewwel algoritmu, fejn inti marru xellug għal-lemin, kontra l- 210 00:07:00,530 --> 00:07:03,430 tieni algoritmu hawn? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: Dan wieħed għandu, bħal, forsi tnaqqas iż, jew saħansitra aktar, yeah. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. Malan: OK, forsi anke aktar. 213 00:07:07,320 --> 00:07:10,150 Ejja timbotta ftit diffiċli fuq dan. 214 00:07:10,150 --> 00:07:13,030 Dak li verament, jekk inkomplu din loġika, aħna definittivament bin-nofs l- 215 00:07:13,030 --> 00:07:15,830 running time ma 'din it-tieni algoritmu billi jitfa bogħod nofs il- 216 00:07:15,830 --> 00:07:18,470 numri, imma dak li ma nagħmlu fuq il-li jmiss iterazzjoni, meta Jennifer żvelat 217 00:07:18,470 --> 00:07:20,615 it-tieni numru? 218 00:07:20,615 --> 00:07:22,830 >> Aħna bin-nofs in-numri ta 'bibien mill-ġdid. 219 00:07:22,830 --> 00:07:25,270 U allura dak li ma nagħmlu wara li, jekk kien hemm bibien aktar biex jilagħbu ma? 220 00:07:25,270 --> 00:07:27,520 Nixtiequ jonqos bin-nofs minnhom, u għal darb'oħra, u għal darb'oħra, u għal darb'oħra. 221 00:07:27,520 --> 00:07:30,420 U dan kien biss bħal inti guys kollha wieqfa fl-ewwel ġimgħa ta ' 222 00:07:30,420 --> 00:07:33,000 klassi, nofs inti bilqiegħda, nofs tal inti bilqiegħda, nofs inti 223 00:07:33,000 --> 00:07:35,440 bilqiegħda, sakemm wieħed isolati ruħ kien bil-wieqfa. 224 00:07:35,440 --> 00:07:39,050 U aħna qal li l-ħin tmexxija ta ' li, l-għadd ta 'passi li ħa kienet 225 00:07:39,050 --> 00:07:40,430 fuq l-ordni ta 'xiex? 226 00:07:40,430 --> 00:07:41,230 >> SPEAKER 1: [inaudible] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. Malan: Allura log bażi 2 ta 'n, jew biss aktar sempliċi, log ta 'n. 228 00:07:43,970 --> 00:07:45,060 Allura xi ħaġa logaritmika. 229 00:07:45,060 --> 00:07:48,380 U l-grafika ma kienx linja dritta li biss marret għall-agħar u agħar, kien 230 00:07:48,380 --> 00:07:52,490 din il-kurva interessanti li ma tikseb daqshekk ħżiena matul iż-żmien. 231 00:07:52,490 --> 00:07:53,910 Mela ejja iżommu lill din l-idea. 232 00:07:53,910 --> 00:07:54,690 Ejja nirringrazzja Jennifer. 233 00:07:54,690 --> 00:07:56,150 Grazzi tant għall ġejjin fuq up. 234 00:07:56,150 --> 00:07:57,400 U, wieħed taqs. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Ebda bozoz mejda llum, imma aħna do jkollhom CS50 blalen istress. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. Malan: Kull dritt, hawn. 239 00:08:04,410 --> 00:08:06,545 Grazzi għall jeħel l-istress up here. 240 00:08:06,545 --> 00:08:07,350 Kull dritt. 241 00:08:07,350 --> 00:08:10,620 Mela ejja ara jekk nistgħu mhux issa jifformalizza din daqsxejn aktar. 242 00:08:10,620 --> 00:08:14,820 Għalhekk għal darb'oħra, dak li aħna biss ma kien essenzjalment l-istess ħaġa bħat għamilna 243 00:08:14,820 --> 00:08:16,660 f'dan l-ewwel ġimgħa. 244 00:08:16,660 --> 00:08:23,780 Iżda pjuttost milli tmiem biss bi lineari algoritmu, li aħna jidhru 245 00:08:23,780 --> 00:08:27,210 qabel bħala din il-linja dritta, fejn, jekk npoġġux wieħed bieb aktar fuq 246 00:08:27,210 --> 00:08:29,610 l-iskrin, allura Jennifer kieku kellhom ħarsa, potenzjalment, 247 00:08:29,610 --> 00:08:30,600 wara bieb wieħed aktar. 248 00:08:30,600 --> 00:08:33,490 Jekk nistaqsu żewġ bibien aktar, hi jista 'jkollhom tfittex wara żewġ bibien aktar. 249 00:08:33,490 --> 00:08:35,990 >> U hekk, kien hemm dan lineari relazzjoni bejn id-daqs tal- 250 00:08:35,990 --> 00:08:39,059 problema, ngħidu aħna, l-assi x, u l-ammont ta 'ħin li tieħu biex 251 00:08:39,059 --> 00:08:40,440 isolvu fuq il-y. 252 00:08:40,440 --> 00:08:43,330 Iżda l-istampa I kien jalludi għal qabel kienet din il-linja ħadra. 253 00:08:43,330 --> 00:08:45,970 Green deliberatament, minħabba huwa biss ħassew aħjar. 254 00:08:45,970 --> 00:08:49,790 Fit-teorija, l-algoritmu, meta aħna ma kien mal-ktieb tat-telefon, meta aħna ma kien 255 00:08:49,790 --> 00:08:52,420 miegħek guys għadd xulxin, u fit-tieni każ, meta Jennifer biss 256 00:08:52,420 --> 00:08:55,250 ma kien up hawn, kien sort tal fundamentalment aħjar. 257 00:08:55,250 --> 00:08:57,180 Minħabba li ma kienx biss darbtejn aktar malajr. 258 00:08:57,180 --> 00:08:58,870 Lanqas ma kien erba 'darbiet malajr. 259 00:08:58,870 --> 00:09:03,290 Kien kompletament dipendenti fuq dak il- daqs tal-input kien, dwar kemm 260 00:09:03,290 --> 00:09:05,220 passi li finalment ħa. 261 00:09:05,220 --> 00:09:08,040 >> U hekk din l-idea sempliċi li aħna kollha ħa għall mogħtija mal-ktieb tat-telefon, 262 00:09:08,040 --> 00:09:10,200 jistgħu bl-istess mod jiġu applikati għal xi ħaġa bħal din. 263 00:09:10,200 --> 00:09:12,380 U dan jista 'jkun aktar każwali magħrufa bħala, kif inti tista ' 264 00:09:12,380 --> 00:09:13,940 jimmaġina, jaqsam u jirbħu. 265 00:09:13,940 --> 00:09:16,390 B'differenza ma dak li għamilna, naturalment, mal-ktieb tat-telefon. 266 00:09:16,390 --> 00:09:18,300 >> Iżda l-pseudocode, recall, kien dan. 267 00:09:18,300 --> 00:09:21,800 Allura aħna mhux se tagħmel dan mill-ġdid, iżda tfakkar li l-ewwel ġimgħa, lkoll saqajh 268 00:09:21,800 --> 00:09:25,140 u mbagħad nofs tal inti sib stabbiliti, nofs inti sib stabbiliti, nofs inti sib stabbiliti. 269 00:09:25,140 --> 00:09:29,280 Din l-algorithm ġiet implimentata daqsxejn ta 'mod qerq, peress li, hija 270 00:09:29,280 --> 00:09:32,870 kienx biss waħda mill me għadd, fundamentalment, b'mod aktar effiċjenti. 271 00:09:32,870 --> 00:09:35,830 F'dak il-każ, I kien jitqawwa riżorsa sekondarja. 272 00:09:35,830 --> 00:09:39,470 Sort ta ', CPUs multipli, imħuħ multipli, nies intelliġenti multipli fil- 273 00:09:39,470 --> 00:09:42,740 kamra ġew tgħin me tikseb minn xi ħaġa lineari għal xi ħaġa 274 00:09:42,740 --> 00:09:45,190 logaritmika, minn xi ħaġa aħmar għal aħdar xi ħaġa. 275 00:09:45,190 --> 00:09:48,650 >> Iżda f'dan il-każ, Jennifer weħidha ma fundamentalment jtejbu fuq l- 276 00:09:48,650 --> 00:09:52,370 prestazzjoni ta 'l-ewwel algoritmu tagħha minn, għal darb'oħra, biss ħsieb ftit diffiċli. 277 00:09:52,370 --> 00:09:56,650 U issa, meta niġu żmien biex jimplimentaw dawn l-affarijiet, jidhru 278 00:09:56,650 --> 00:10:00,670 liema linji tal-kodiċi tista 'tikteb bħal li inti tista 'tirrepeti lilhom mill-ġdid, u 279 00:10:00,670 --> 00:10:03,350 għal darb'oħra, u għal darb'oħra, tip ta ' b'mod looping. 280 00:10:03,350 --> 00:10:06,370 Minħabba int mhux se jkollhom l- lussu, bħal Jennifer ma fl-ewwel, biex 281 00:10:06,370 --> 00:10:10,460 biss ikollhom mazz sħiħ ta 'IFs u jgħidu, hmm, jekk din l-ewwel numru huwa 4, 282 00:10:10,460 --> 00:10:11,800 let me jaqbżu it-triq kollha sa l-aħħar. 283 00:10:11,800 --> 00:10:14,180 Ooh, jekk dak in-numru huwa kbir wisq, let me jimxu arbitrarju lura 284 00:10:14,180 --> 00:10:15,220 għat-tieni element. 285 00:10:15,220 --> 00:10:18,210 Inti ser issib li huwa għaddej li jkun hemm ħafna aktar diffiċli biex tifformalizza dak aħna bnedmin 286 00:10:18,210 --> 00:10:21,270 jieħdu għal mogħtija bħala raġonevoli ħafna heuristics, iżda l-kompjuter huwa biss 287 00:10:21,270 --> 00:10:23,260 se tagħmel dak li inti tgħid li tagħmel. 288 00:10:23,260 --> 00:10:25,280 >> Issa dan għandu interessanti ħafna implikazzjonijiet. 289 00:10:25,280 --> 00:10:29,950 Din il-graff hija tip ta maħsub biex isolvi ta jisbqu viżwalment, imma avviż, fejn 290 00:10:29,950 --> 00:10:32,230 hija l-linja dritta f'dan graff? 291 00:10:32,230 --> 00:10:35,330 Fejn hi l-graff lineari li nitolbu n? 292 00:10:35,330 --> 00:10:37,580 Ukoll, huwa tip ta 'lejn il-qiegħ ta 'din l-istampa, id-dritt? 293 00:10:37,580 --> 00:10:40,500 Allura kollha għandna ghamilt hija konna tip ta ' żżomjati out għall-assi-x u il- 294 00:10:40,500 --> 00:10:44,780 assi-y biex nipprova nikseb sens ta 'dak tipi oħra ta 'kurvi look like. 295 00:10:44,780 --> 00:10:47,760 >> U l-ispeċifiċitajiet ta 'l-matematiċi espressjonijiet illum mhux se kwistjoni hekk 296 00:10:47,760 --> 00:10:52,440 ħafna, iżda avviż li hemm ħafna ta ' algoritmi li huma ħafna agħar minn 297 00:10:52,440 --> 00:10:53,470 xi ħaġa li lineari. 298 00:10:53,470 --> 00:10:55,410 Tabilħaqq, n kubiku jistenna pretty bad. 299 00:10:55,410 --> 00:10:58,400 2 għall-n jistenna pretty bad. n kwadrat jistenna pretty bad. 300 00:10:58,400 --> 00:11:01,630 U aħna ser tara dak li xi wħud minn dawk jista 'jkun fir-realtà llum. 301 00:11:01,630 --> 00:11:05,430 U log n ma jħossx bħala ħżiena, iżda aħjar minn n huwa log bażi 2 ta 'n. 302 00:11:05,430 --> 00:11:08,080 Imma inti taf, kien ikun saħansitra aktar aqwa jekk Jennifer, jew jekk aħna, 303 00:11:08,080 --> 00:11:12,910 li l-ewwel ġimgħa, kienet toħroġ bi xi ħaġa li log log ta 'n. 304 00:11:12,910 --> 00:11:15,880 >> Allura fi kliem ieħor, hemm dan kollu firxa ta 'soluzzjonijiet possibbli għall- 305 00:11:15,880 --> 00:11:18,570 problemi, iżda anke hawn, l-avviż x'inhu jiġri. 306 00:11:18,570 --> 00:11:22,910 Meta I zoom out, liema minn dawn kurvi se jirriżultaw li huma l assoluta 307 00:11:22,910 --> 00:11:26,630 agħar ta 'dawk fuq l-iskrin issa? 308 00:11:26,630 --> 00:11:28,680 Allura n kubiku jistenna pretty gravi fil-mument. 309 00:11:28,680 --> 00:11:32,470 Imma jekk irridu zoom out u ara aktar tal- x u il-y-axis, li għaddej biex 310 00:11:32,470 --> 00:11:34,550 jiddominaw finalment? 311 00:11:34,550 --> 00:11:37,120 Għalhekk fil-fatt jirriżulta li 2 għall- n, u inti tista 'figura dan biss billi 312 00:11:37,120 --> 00:11:39,990 fejn jitwaħħal f'xi kbir dejjem jiżdied numri, u tkun taf tara li 2 għall- 313 00:11:39,990 --> 00:11:42,070 n, tabilħaqq, tkompli tikber ħafna aktar mgħaġġla. 314 00:11:42,070 --> 00:11:45,530 Jekk aħna verament zoom out, a 2 għall- n algoritmu assolutament sucks. 315 00:11:45,530 --> 00:11:48,170 I tfisser dan se jieħu pjuttost ftit ta 'żmien għall- 316 00:11:48,170 --> 00:11:49,460 kompjuter biex lenbija permezz. 317 00:11:49,460 --> 00:11:52,500 >> Imma int ser tara matul iż-żmien, speċjalment ma 'settijiet problema futuri u anke 318 00:11:52,500 --> 00:11:55,600 proġetti finali, hija data tiegħek sett gets kbira, id-dritt? 319 00:11:55,600 --> 00:11:58,300 Anke fl-ewwel verżjoni ta 'Facebook, bħala n-numru ta 'ħbieb, u l- 320 00:11:58,300 --> 00:12:01,840 numru ta 'utenti reġistrati ltqajna kbar, inti tista sort ta 'telefon fil u 321 00:12:01,840 --> 00:12:05,530 timplimenta xi ħaġa ma 'search lineari, jew għażla sempliċi ħafna 322 00:12:05,530 --> 00:12:07,030 algoritmu, kif Ser naraw illum. 323 00:12:07,030 --> 00:12:09,280 Int għandek tibda taħseb aktar diffiċli u aktar diffiċli dwar dawn il-problemi. 324 00:12:09,280 --> 00:12:12,070 U t-tipi ta 'problemi postijiet bħal Facebook, u Google, u Microsoft, 325 00:12:12,070 --> 00:12:16,350 u oħrajn jaħdmu fuq huwa eżattament dawn tip ta 'big tip data ta' mistoqsijiet 326 00:12:16,350 --> 00:12:18,530 dejjem dawn il-jiem. 327 00:12:18,530 --> 00:12:18,900 >> Kull dritt. 328 00:12:18,900 --> 00:12:23,800 Allura suċċess Jennifer f'dan it-tieni algoritmu, franchement, hija għamlet amazingly 329 00:12:23,800 --> 00:12:26,110 ukoll l-ewwel darba, iżda ejja tiktibha kif Xorti sabiex inkunu 330 00:12:26,110 --> 00:12:27,000 tista 'tagħmel dan il-punt. 331 00:12:27,000 --> 00:12:30,970 Fit-tieni każ, hija leveraged l algoritmu li ripetuta mill-ġdid u 332 00:12:30,970 --> 00:12:34,670 għal darb'oħra, iżda hi ħa jingħataw ċerti suppożizzjoni li aħna permess 333 00:12:34,670 --> 00:12:39,370 tagħha, iżda hi sfruttata xi dettall l- tieni darba li hi ma kellhiex l- 334 00:12:39,370 --> 00:12:39,840 ewwel darba. 335 00:12:39,840 --> 00:12:41,800 Liema kien dak? 336 00:12:41,800 --> 00:12:43,050 >> Li l-lista ġiet magħżula. 337 00:12:43,050 --> 00:12:46,350 Allura hekk kif il-lista ġiet magħżula, aħna jsostnu li Jennifer kienet f'pożizzjoni li tagħmel 338 00:12:46,350 --> 00:12:47,480 fundamentalment aħjar. 339 00:12:47,480 --> 00:12:51,450 7 bibien, iva, mhijiex dik interessanti, iżda jissoponi li aħna qed 7000000 bibien. 340 00:12:51,450 --> 00:12:54,080 Log ta 'n huwa definittivament se biex iwettqu ħafna, ħafna 341 00:12:54,080 --> 00:12:55,610 aktar mgħaġġel fit-tul. 342 00:12:55,610 --> 00:12:58,880 Iżda hija kellha li jkollhom l- bibien magħżula għall tagħha. 343 00:12:58,880 --> 00:13:02,320 Issa, I ħa l-libertà li jagħmlu dan bil-quddiem fuq l-iskrin tal-kompjuter 344 00:13:02,320 --> 00:13:05,160 hawn, iżda jissoponi li Jennifer kellha tagħmel dan lilha nfisha? 345 00:13:05,160 --> 00:13:10,120 Ejja ngħidu li l-bibien in kwistjoni data rappreżentati f 'database, jew 346 00:13:10,120 --> 00:13:14,260 ħbieb rreġistrati għal Facebook, jew xi paġni web fuq l-internet li 347 00:13:14,260 --> 00:13:16,880 diversi websites jistgħu jeħtieġu biex indiċi jew tfittxija fuq. 348 00:13:16,880 --> 00:13:20,940 >> Ejja ngħidu li inti biss kellhom data mhux ipproċessata stabbiliti u kien f'idejn lilek, jew li 349 00:13:20,940 --> 00:13:23,010 Jennifer biex tagħmel dan issortjar? 350 00:13:23,010 --> 00:13:26,950 Li, aktar, teħtieġ li aħna risposta il-kwistjoni, ukoll, kemm ħin 351 00:13:26,950 --> 00:13:31,080 kienx jieħu Jennifer, jew saħansitra me, biex issolvi dawn in-numri bil-quddiem sabiex 352 00:13:31,080 --> 00:13:32,680 li hi tista 'tieħu vantaġġ ta' dak? 353 00:13:32,680 --> 00:13:32,880 Dritt? 354 00:13:32,880 --> 00:13:36,620 Minħabba li l-implikazzjoni, naturalment, huwa jekk tieħu me pjuttost filwaqt li sort 355 00:13:36,620 --> 00:13:40,800 in-numri, li l-Heck cares li inti tista 'ssib numru simili 50 daqstant b'mod mgħaġġel, 356 00:13:40,800 --> 00:13:44,850 bħal fil-każ Jennifer, jekk aħna aktar minn megħlub l-ammont ta 'ħin totali 357 00:13:44,850 --> 00:13:46,920 hija ħadet bl-għażil affarijiet bil-quddiem? 358 00:13:46,920 --> 00:13:49,320 >> Mela ejja ara jekk aħna ma tista 'l- żebgħa l-istampa hawn. 359 00:13:49,320 --> 00:13:51,370 I jkollhom mazz sħiħ aktar stress blalen, jekk li tgħin 360 00:13:51,370 --> 00:13:52,270 jkisser is-silġ hawn. 361 00:13:52,270 --> 00:13:55,690 U jekk inti ma mind, aħna bżonn seba voluntier - 362 00:13:55,690 --> 00:13:57,060 fuq, OK. 363 00:13:57,060 --> 00:13:57,240 Ara naqra. 364 00:13:57,240 --> 00:13:59,250 Allura aħna ma jkollu jonfoq fuq lampi desk, jidher. 365 00:13:59,250 --> 00:13:59,690 Kull dritt. 366 00:13:59,690 --> 00:14:01,530 Allura kif dwarek tnejn quddiem. 367 00:14:01,530 --> 00:14:04,160 Kif dwarek żewġ guys fid-dahar. 368 00:14:04,160 --> 00:14:04,870 Allura dak erbgħa. 369 00:14:04,870 --> 00:14:09,890 Kif dwarek quddiem ħames, sitt u seba '. 370 00:14:09,890 --> 00:14:10,320 Hemm dritt. 371 00:14:10,320 --> 00:14:13,260 Ħabib tiegħek tipponta out, sabiex tikseb l-premju. 372 00:14:13,260 --> 00:14:13,700 >> Kull dritt. 373 00:14:13,700 --> 00:14:14,410 Come fuq up. 374 00:14:14,410 --> 00:14:17,120 U għaliex ma we jkollhom inti guys jaqgħu fuq matul hawn. 375 00:14:17,120 --> 00:14:18,960 Jien ser jagħtuk kull numru. 376 00:14:18,960 --> 00:14:22,150 U jimxi 'l quddiem u jirranġa yourselves identiku għal dak 377 00:14:22,150 --> 00:14:25,180 jidhru fuq l-iskrin. 378 00:14:25,180 --> 00:14:26,530 >> [INTERPOSING VUĊI] 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 Kull dritt. 382 00:14:32,180 --> 00:14:32,750 Well, here we go. 383 00:14:32,750 --> 00:14:34,180 Numru b'ħames. 384 00:14:34,180 --> 00:14:35,136 Numru sitta. 385 00:14:35,136 --> 00:14:37,770 Wieħed, tnejn, tlieta, erba, ħames, sitt, seba '. 386 00:14:37,770 --> 00:14:39,410 Oh, dan huwa skomda. 387 00:14:39,410 --> 00:14:41,210 >> SPEAKER 2: I taf biss jiksbu -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. Malan: jittrattaw Tajba. 389 00:14:41,900 --> 00:14:43,130 Kull dritt. 390 00:14:43,130 --> 00:14:44,611 Grazzi għall-parteċipazzjoni. 391 00:14:44,611 --> 00:14:47,200 >> [Applause] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Kull dritt. 394 00:14:48,860 --> 00:14:51,970 Allura aħna għandna erba ', tnejn, sitta, waħda, tlieta, seba ', ħames. 395 00:14:51,970 --> 00:14:56,010 Perfetta hekk aħna f'seba 'voluntiera hawn li huma ugwali fil-wisa 'l- 396 00:14:56,010 --> 00:14:57,430 array li aħna qed jilagħbu mal-ewwel. 397 00:14:57,430 --> 00:14:59,470 U jien għażlet seba għal raġunijiet li se jkun biss 398 00:14:59,470 --> 00:15:00,840 konvenjenti fi ftit. 399 00:15:00,840 --> 00:15:04,400 U jien ser tipproponi ewwel li aħna issolvi dawn f'seba 'voluntiera. 400 00:15:04,400 --> 00:15:06,786 Jekk inti tixtieq, minn naħa, li jgħidu bonjour għalkemm. 401 00:15:06,786 --> 00:15:08,970 Peress li din se tkun skomdi diversi minuti. 402 00:15:08,970 --> 00:15:10,370 Introduċi yourselves. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Hi, jien Grace. 404 00:15:10,980 --> 00:15:14,190 Jien sophomore fil Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Hi. 406 00:15:14,620 --> 00:15:15,620 Jien Branson. 407 00:15:15,620 --> 00:15:16,920 Jien freshman fil Weld. 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 Jien Gabe. 411 00:15:21,040 --> 00:15:22,300 Jien junior fil Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Jien Neil. 414 00:15:25,980 --> 00:15:29,090 Jien freshman fil Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Jien Jason. 416 00:15:29,550 --> 00:15:32,816 Jien freshman fil Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Jien Mike. 418 00:15:33,700 --> 00:15:37,360 Jien freshman fil Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Jien Jess. 420 00:15:37,990 --> 00:15:40,313 Jien sophomore fl Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. Malan: Eċċellenti. 422 00:15:41,300 --> 00:15:41,850 Kull dritt. 423 00:15:41,850 --> 00:15:44,190 Ukoll, grazzi għall kollha ta 'tagħna voluntiera hawn s'issa. 424 00:15:44,190 --> 00:15:47,110 U l-isfida fil-idejn issa huwa għaddej li jkun biex issolvi ta 'dawn guys, iżda mbagħad 425 00:15:47,110 --> 00:15:50,250 aħna qed tmur biex ikollhom biex jaħsbu ftit hard dwar kif effiċjenti nistgħu attwalment 426 00:15:50,250 --> 00:15:51,110 magħżula minnhom. 427 00:15:51,110 --> 00:15:52,580 Mela ejja ewwel tipprova dan. 428 00:15:52,580 --> 00:15:55,970 You guys tista 'tara n-numri ta' xulxin biss mill-tqegħid madwar il-kantunieri. 429 00:15:55,970 --> 00:15:59,380 Jimxi 'l quddiem u tieħu ftit sekondi, u sort yourselves mill-iżgħar fuq l- 430 00:15:59,380 --> 00:16:01,240 xellug għal akbar fuq il-lemin. 431 00:16:01,240 --> 00:16:02,490 Mur. 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 Tajba. 435 00:16:08,030 --> 00:16:09,370 Dan kien verament darn fast. 436 00:16:09,370 --> 00:16:14,040 Issa xi ħadd hawnhekk, dak li kien l-algoritmu li dawn guys applikati? 437 00:16:14,040 --> 00:16:14,900 >> SPEAKER 1: Inqas għall-akbar. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. Malan: OK. 439 00:16:15,000 --> 00:16:18,070 Inqas sal akbar huwa verament sort ta 'l- għan, iżda M'inix ċert li l- 440 00:16:18,070 --> 00:16:18,890 verament algoritmu. 441 00:16:18,890 --> 00:16:21,810 Inqas sal akbar ma tgħid me pass pass x'għandek tagħmel. 442 00:16:21,810 --> 00:16:22,833 Yeah? 443 00:16:22,833 --> 00:16:24,083 >> SPEAKER 1: [inaudible] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. Malan: OK. 446 00:16:26,280 --> 00:16:28,920 Mela jekk inti tara persuna iżgħar minn numru tiegħek, mbagħad jimxu għal 447 00:16:28,920 --> 00:16:29,680 id-dritt minnhom. 448 00:16:29,680 --> 00:16:32,800 Allura thats issa jkollna aktar espressiva, aktar bħal algoritmu, għaliex inti 449 00:16:32,800 --> 00:16:35,410 jista 'jgħid, jekk dan, allura dik. 450 00:16:35,410 --> 00:16:37,050 Allura aħna għandna xi tip ta ' tibni kondizzjonali. 451 00:16:37,050 --> 00:16:39,700 U dawn guys deher li tagħmel dan ftit drabi, minħabba li xi wħud minnkom mċaqalqa daqsxejn 452 00:16:39,700 --> 00:16:40,420 ta 'distanza. 453 00:16:40,420 --> 00:16:43,410 Allura kien hemm preżumibbilment xi tip ta ' looping għaddej fl-imħuħ tagħhom. 454 00:16:43,410 --> 00:16:44,610 >> Imma ejja jippruvaw li jifformalizzaw dan. 455 00:16:44,610 --> 00:16:47,540 Jekk inti guys tista reset lura għal dan l-arranġament. 456 00:16:47,540 --> 00:16:50,650 Ejja naraw jekk aħna ma tistax jifformalizza din l- bit, u mbagħad titlob il-kwistjoni, biss 457 00:16:50,650 --> 00:16:51,580 kif effiċjenti huwa dan? 458 00:16:51,580 --> 00:16:54,220 Of course, meta nagħmlu dan aktar bil-mod, li għaddej biex jħossu bħala tajba ta ' 459 00:16:54,220 --> 00:16:57,210 algoritmu, imma ejja ara jekk nistgħu jitqiegħdu idejna fuq il-passi preċiżi. 460 00:16:57,210 --> 00:16:58,670 >> Allura inti żewġ guys huma erba 'u tnejn. 461 00:16:58,670 --> 00:17:01,020 Jew inti ordni eżatta jew żbaljata? 462 00:17:01,020 --> 00:17:01,900 Ovvjament żbaljata. 463 00:17:01,900 --> 00:17:02,710 Allura aħna biddlu. 464 00:17:02,710 --> 00:17:05,170 Issa jien ser jiċċaqalqu aside hawn u jgħidu, 4-6. 465 00:17:05,170 --> 00:17:06,240 Inti eżatta jew żbaljata? 466 00:17:06,240 --> 00:17:06,599 >> Gabe: Korretta. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. Malan: Korretta. 468 00:17:07,180 --> 00:17:08,300 Sitta u wieħed? 469 00:17:08,300 --> 00:17:08,609 Nope. 470 00:17:08,609 --> 00:17:09,630 Tpartit. 471 00:17:09,630 --> 00:17:10,490 Allura dak żewġ tpartit. 472 00:17:10,490 --> 00:17:11,710 Sitta u tlieta? 473 00:17:11,710 --> 00:17:11,980 Nope. 474 00:17:11,980 --> 00:17:13,000 Tpartit. 475 00:17:13,000 --> 00:17:13,930 Sitta u seba? 476 00:17:13,930 --> 00:17:14,630 Jidher tajjeb. 477 00:17:14,630 --> 00:17:15,396 Seba u ħames? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [inaudible] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. Malan: OK, tpartit. 480 00:17:17,089 --> 00:17:19,770 U magħżula. 481 00:17:19,770 --> 00:17:19,980 Kull dritt. 482 00:17:19,980 --> 00:17:21,440 Allura ovvjament le, id-dritt? 483 00:17:21,440 --> 00:17:22,470 Allura kien hemm aktar għaddej. 484 00:17:22,470 --> 00:17:24,920 Iżda, fil-fatt, dawn guys, anke biss istintivament. 485 00:17:24,920 --> 00:17:25,450 miżmuma miexja. 486 00:17:25,450 --> 00:17:27,710 Huma ma tieqaf biss, ladarba korretta problema waħda. 487 00:17:27,710 --> 00:17:27,839 So. 488 00:17:27,839 --> 00:17:29,390 Tabilħaqq, jien ser ikollhom jagħmlu l-istess ħaġa. 489 00:17:29,390 --> 00:17:32,720 Jien ser ikollhom biex isolvi ta kontrina lura għall-bidu ta 'din il-problema, 490 00:17:32,720 --> 00:17:35,630 jew il-bidu ta 'din firxa ta' nies, ejja tibda sejħa minnhom. 491 00:17:35,630 --> 00:17:38,366 >> U issa dak li għandu algoritmu tiegħi fit-tieni pass ikun? 492 00:17:38,366 --> 00:17:39,220 >> SPEAKER 1: L-istess ħaġa. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. Malan: L-istess ħaġa. 494 00:17:39,940 --> 00:17:41,460 U dan, jien jibdew biex simili, right? 495 00:17:41,460 --> 00:17:44,720 Hekk kif inti tista 'ssib ruħek jagħmlu l-istess ħaġa mill-ġdid u għal darb'oħra, li l- 496 00:17:44,720 --> 00:17:47,890 isiru aktar simili algoritmu, u istint inqas bniedem. 497 00:17:47,890 --> 00:17:48,680 >> Allura issa, here we go darb'oħra. 498 00:17:48,680 --> 00:17:49,870 Żewġ u erba? 499 00:17:49,870 --> 00:17:50,220 No 500 00:17:50,220 --> 00:17:51,050 Erba 'u waħda? 501 00:17:51,050 --> 00:17:53,380 Ah, kien hemm tabilħaqq xi xogħol xi jsir. 502 00:17:53,380 --> 00:17:53,620 Għal u tliet? 503 00:17:53,620 --> 00:17:54,572 Tajba. 504 00:17:54,572 --> 00:17:56,000 Erba 'u sitt? 505 00:17:56,000 --> 00:17:58,380 Sitta u ħames? 506 00:17:58,380 --> 00:17:59,470 Sitta u seba? 507 00:17:59,470 --> 00:18:00,970 OK, issa, isir. 508 00:18:00,970 --> 00:18:01,550 OK, l-ebda. 509 00:18:01,550 --> 00:18:02,710 I ikollhom imorru lura. 510 00:18:02,710 --> 00:18:05,130 >> Allura issa, għal darb'oħra, aħna qed tagħmel dan ftit aktar deliberatament. 511 00:18:05,130 --> 00:18:08,700 U issa, hemm waħda biss tal-moħħ eżekuzzjoni din algoritmu. 512 00:18:08,700 --> 00:18:10,290 CPU waħda, jekk inti se. 513 00:18:10,290 --> 00:18:13,090 U franchement, dak l-uniku riżors aħna qed tmur biex ikollhom aċċess għall. 514 00:18:13,090 --> 00:18:16,280 U ladarba aħna ma jmorru lura għal tastiera u jkollhom xi ħaġa simili C lejn tagħna 515 00:18:16,280 --> 00:18:19,600 rimi, aħna qed biss kitba ta 'programm li tista 'tagħmel ħaġa waħda f'ħin wieħed. 516 00:18:19,600 --> 00:18:22,900 Billi, dawn guys mument ilu, aħna leveraged intelliġenza kollettiva tagħhom 517 00:18:22,900 --> 00:18:24,180 bħal inti guys għamlet fil-ġimgħa żero. 518 00:18:24,180 --> 00:18:24,980 Mela ejja iżommu tagħmel dan. 519 00:18:24,980 --> 00:18:26,260 >> Tnejn u wieħed. 520 00:18:26,260 --> 00:18:26,945 Tnejn u tlieta. 521 00:18:26,945 --> 00:18:27,460 Tlieta u erbgħa. 522 00:18:27,460 --> 00:18:28,310 Erba 'u ħames. 523 00:18:28,310 --> 00:18:28,620 Ħames u sitt. 524 00:18:28,620 --> 00:18:30,510 Sitt snin u seba '. 525 00:18:30,510 --> 00:18:31,880 Magħmula? 526 00:18:31,880 --> 00:18:34,560 So I am, iżda let me play avukat devil. 527 00:18:34,560 --> 00:18:37,950 Do I, il-tip tal-kompjuter li sempliċiment għamlet pass permezz ta 'dan firxa ta' 528 00:18:37,950 --> 00:18:40,225 nies, jafu li jien jsir? 529 00:18:40,225 --> 00:18:40,670 >> SPEAKER 1: Le 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. Malan: Allura għaliex? 531 00:18:41,050 --> 00:18:46,900 X'għandu nagħmel biex jikkonkludi deċiżiv li jiena jsir? 532 00:18:46,900 --> 00:18:48,230 Probabbilment wieħed pass aktar. 533 00:18:48,230 --> 00:18:48,430 Dritt? 534 00:18:48,430 --> 00:18:51,760 Minħabba li kull naf minn dak preċedenti pass huwa li jien korrett żball. 535 00:18:51,760 --> 00:18:53,920 U dan ifisser, forsi hemm xorta żball ieħor 536 00:18:53,920 --> 00:18:54,840 li għandi bżonn biex jikkoreġu. 537 00:18:54,840 --> 00:18:58,680 So I jista 'jkun żgur biss mill rewinding, u allura iċċekkjar, 1-2, tnejn u 538 00:18:58,680 --> 00:19:00,940 tlieta, tlieta u erba ', erba' u ħames, ħames u sitt, sitt u seba '. 539 00:19:00,940 --> 00:19:02,510 OK, issa I ma ebda xogħol. 540 00:19:02,510 --> 00:19:05,990 >> I jista 'ċertament ftakar li għamilt ebda jaħdmu ma 'xi ħaġa bħal varjabbli, 541 00:19:05,990 --> 00:19:06,975 bħal int. 542 00:19:06,975 --> 00:19:12,490 Sejħa hija swaps, u jekk tpartit huwa 0 darba I nikseb hawn, u dan beda fil-0, imbagħad 543 00:19:12,490 --> 00:19:15,520 I se jkun biss stupid li jibqgħu għaddejjin quddiem u lura, il-verifika mill-ġdid, u 544 00:19:15,520 --> 00:19:16,450 għal darb'oħra, u għal darb'oħra, id-dritt? 545 00:19:16,450 --> 00:19:18,450 Għaliex inti jeħlu f'xi tip ta 'loop infinita. 546 00:19:18,450 --> 00:19:21,250 Allura hekk kif hemm 0 tpartit, nistgħu jsostnu li dan 547 00:19:21,250 --> 00:19:23,810 algoritmu huwa tabilħaqq kompluta. 548 00:19:23,810 --> 00:19:25,400 >> Issa, ejja tpoġġi isem fuq dan. 549 00:19:25,400 --> 00:19:28,930 L-algoritmu li nipproponi aħna biss implimentat huwa xi ħaġa imsejħa bużżieqa 550 00:19:28,930 --> 00:19:32,800 sort, magħrufa bħala tali fis-sens li -numri li huma xorta akbar ta ' 551 00:19:32,800 --> 00:19:37,990 bużżieqa mod tagħhom sal-quċċata, jew sa l-aħħar tal-firxa ta 'numri. 552 00:19:37,990 --> 00:19:40,270 Imma kif effiċjenti kien dan algoritmu? 553 00:19:40,270 --> 00:19:44,600 Kemm passi ħafna ma I fiżikament jkollhom jieħdu, per eżempju, biex issolvi dawn 554 00:19:44,600 --> 00:19:45,850 seba bnedmin? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Erba 'sa ħames? 557 00:19:49,550 --> 00:19:51,420 OK, wisq hija finalment se tkun ir-risposta. 558 00:19:51,420 --> 00:19:54,960 Iżda anke dakinhar, in-numru speċifiku ma jkunx hekk interessanti. 559 00:19:54,960 --> 00:19:56,670 Ejja tiġġeneralizza bħala n. 560 00:19:56,670 --> 00:20:00,520 Mela jekk jien kienu n-nies up hawn, u dawn kienu, tip ta ', sabiex każwali fil- 561 00:20:00,520 --> 00:20:02,180 bidu, f'dik l-ordni oriġinali. 562 00:20:02,180 --> 00:20:04,910 Well, kemm passi ma I jkollhom li jieħu fuq l-ewwel pass? 563 00:20:04,910 --> 00:20:09,810 Kien wieħed, tnejn, tlieta, erba ', ħames, sitta, u dawn qed seba 'persuni, hekk 564 00:20:09,810 --> 00:20:13,670 li l-seba ', sitt -, b'tali mod li n nieqes waħda passi l-ewwel darba. 565 00:20:13,670 --> 00:20:16,280 >> Issa, kemm passi ma I jkollhom li jieħdu meta I rewound? 566 00:20:16,280 --> 00:20:19,310 Well, nistgħu attwalment doppju li jekk aħna verament riedu, iżda għal issa, jien 567 00:20:19,310 --> 00:20:22,300 biss se ngħid, id-dritt, n ieħor minus 1. 568 00:20:22,300 --> 00:20:25,240 Allura l-n minus 1 hija se tikseb annoying biex iżommu kont ta ', hekk ejja 569 00:20:25,240 --> 00:20:26,400 biss madwar up ftit. 570 00:20:26,400 --> 00:20:27,770 Allura 2n passi. 571 00:20:27,770 --> 00:20:29,310 Allura 14 passi, jagħtu jew jieħu. 572 00:20:29,310 --> 00:20:31,930 >> Kemm-il darba ma nieħu pass l-ħin li jmiss? 573 00:20:31,930 --> 00:20:33,740 Ukoll, huwa 3n. 574 00:20:33,740 --> 00:20:34,510 verament. 575 00:20:34,510 --> 00:20:37,920 U issa, fl-agħar każ, eżempju, kif ħafna drabi irrid 576 00:20:37,920 --> 00:20:41,730 marret quddiem u lura, u lura, eżekuzzjoni din algoritmu, jagħmlu skambju ta ' 577 00:20:41,730 --> 00:20:44,620 nies fuq kull pass, bejn wieħed u ieħor? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Huwa fil-fatt n kwadrat, right? 580 00:20:50,010 --> 00:20:53,000 >> Minħabba fl-agħar każ, inti tista 'tip ta 'jaħsbu dwar dan intuwittivament, 581 00:20:53,000 --> 00:20:54,800 anki jekk jista 'jieħu ftit ftit ta 'żmien biex jinżel pulzieri 582 00:20:54,800 --> 00:20:57,590 Fl-agħar każ, liema kieku dawn seba 'persuni ħarsu simili, fil 583 00:20:57,590 --> 00:21:00,230 termini tal-arranġament ta 'numri tagħhom? 584 00:21:00,230 --> 00:21:01,460 Kompletament lura, id-dritt? 585 00:21:01,460 --> 00:21:02,815 U biss biex jissimulaw li, dak kien l-isem tiegħek mill-ġdid? 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, inti biss tista jissieħbu miegħi fuq hawn għal waħda biss tieni? 589 00:21:08,100 --> 00:21:08,880 Attwalment, l-ebda. 590 00:21:08,880 --> 00:21:10,150 Jiddispjacini Mike, ejja kontrina. 591 00:21:10,150 --> 00:21:10,910 X'hemm isem tiegħek mill-ġdid? 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, inti taqa 'bi me, jekk inti ma mind. 595 00:21:13,750 --> 00:21:17,150 Hekk jien ser tipproponi, biss għal sempliċità, li Neil issa hija fil tiegħu 596 00:21:17,150 --> 00:21:18,510 agħar każ possibbli. 597 00:21:18,510 --> 00:21:20,720 Imma jitfakkar kif I implimentati algoritmu tiegħi. 598 00:21:20,720 --> 00:21:24,530 Jien jqabbel, li jqabbel, li jqabbel, jitqabblu, li jqabbel, oh. 599 00:21:24,530 --> 00:21:26,640 Issa dawn guys huma barra ta 'ordni, so I jiffissaw. 600 00:21:26,640 --> 00:21:27,980 Allura inti guys tpartit. 601 00:21:27,980 --> 00:21:31,630 Iżda jikkunsidraw issa, kemm farther ma Neil jkollhom imorru? 602 00:21:31,630 --> 00:21:32,690 Huwa madwar n. 603 00:21:32,690 --> 00:21:33,570 You know, mhuwiex attwalment n. 604 00:21:33,570 --> 00:21:36,040 Huwa simili, n minus 1, imma jien jkollna imdejqa iżżomm rekord ta 'l-ftit 605 00:21:36,040 --> 00:21:37,550 numru, hekk ejja biss sejħa hija n. 606 00:21:37,550 --> 00:21:42,860 >> Mela jekk Neil jiċċaqlaq pass wieħed maximally kull żmien, u biex jimxu Neil pass wieħed, 607 00:21:42,860 --> 00:21:46,580 I jkollhom jagħmlu dan il-pass verament tedious quddiem u lura, dan huwa bejn wieħed u ieħor 608 00:21:46,580 --> 00:21:52,080 tagħmel dan, n passi, total ta 'n darbiet, minħabba li għaddej biex jieħdu me 609 00:21:52,080 --> 00:21:55,820 li ħafna passi biex tikseb Neil kollha l-mod biex fejn hu jappartjeni. 610 00:21:55,820 --> 00:21:58,620 Aħseb u ara kulħadd jekk inti guys kienu kollha mis-ordnati kif ukoll. 611 00:21:58,620 --> 00:22:01,100 >> Mela ejja sejħa bubble n sort kwadru. 612 00:22:01,100 --> 00:22:04,860 Il-running time ta 'dan algoritmu, il- prestazzjoni ta 'dan algoritmu, il- 613 00:22:04,860 --> 00:22:07,120 effiċjenza ta 'dan algoritmu, aħna għandu biss jiddeskrivu aktar 614 00:22:07,120 --> 00:22:08,800 ġeneralment bħala n kwadrat. 615 00:22:08,800 --> 00:22:11,650 Li huwa sbieħ, minħabba I tista 'tagħmel l- istess eżempju bi tmien persuni, disa 616 00:22:11,650 --> 00:22:15,450 nies, miljun ruħ, u li tweġiba mhux se jibdlu. 617 00:22:15,450 --> 00:22:18,870 >> Hekk jekk inti guys ma mind, ejja reset inti fejn bdejt. 618 00:22:18,870 --> 00:22:22,510 U ejja tipprova żewġ approċċi l-oħra u ara jekk aħna ma tistax tagħmel fundamentalment 619 00:22:22,510 --> 00:22:23,820 aħjar minn hekk. 620 00:22:23,820 --> 00:22:27,130 Allura dan iż-żmien, jien ser tipproponi tip ta 'algoritmu differenti. 621 00:22:27,130 --> 00:22:29,950 Dan kien ħafna għaqlija minna aħħar darba, u inti guys kienu dritt li jkollhom l- 622 00:22:29,950 --> 00:22:32,470 instincts dritt ta 'biss tip ta 'iskambji pairwise. 623 00:22:32,470 --> 00:22:36,500 Imma jekk jien verament riedu approċċ dan sempliċi, u l-għan tiegħi huwa li jiċċaqalqu 624 00:22:36,500 --> 00:22:39,800 kollha tal-numri ftit il-mod, u imbotta kollha tan-numri kbar li 625 00:22:39,800 --> 00:22:43,030 mod, għaliex ma I biss tagħmel dan fil- aktar naive mod possibbli u ara jekk I 626 00:22:43,030 --> 00:22:45,730 tista 'tagħmel aħjar minn dak li kien a pjuttost algoritmu kumpless? 627 00:22:45,730 --> 00:22:46,620 >> Mela ejja ara. 628 00:22:46,620 --> 00:22:48,940 Erba huwa numru pjuttost żgħir, hekk jien ser tħallik hemm mument. 629 00:22:48,940 --> 00:22:50,610 Ooh, numru tnejn huwa anki aħjar. 630 00:22:50,610 --> 00:22:52,230 Allura tista 'biss pass' il quddiem għal mument? 631 00:22:52,230 --> 00:22:55,670 Dan huwa attwalment numru iżgħar tiegħi kandidat, u jien ser tiftakar 632 00:22:55,670 --> 00:22:57,000 li ma, bħal, varjabbli. 633 00:22:57,000 --> 00:22:57,930 Imma jien ser żżomm kontroll. 634 00:22:57,930 --> 00:22:59,890 Hemm xi ħadd li in-numru huwa iżgħar? 635 00:22:59,890 --> 00:23:00,460 Sitta, l-ebda. 636 00:23:00,460 --> 00:23:01,390 Oh, hemm Neil ġdid. 637 00:23:01,390 --> 00:23:04,050 >> Hekk jien ser push inti lura tip ta 'kunċettwalment. 638 00:23:04,050 --> 00:23:05,120 Neil se tressaq. 639 00:23:05,120 --> 00:23:08,440 U issa, il-varjabbli li jien jużaw biex jżommu rekord ta 'min għandu l-iżgħar 640 00:23:08,440 --> 00:23:11,390 numru hija aġġornata biex tinkludi Post Neil. 641 00:23:11,390 --> 00:23:12,110 Well, ejja ara. 642 00:23:12,110 --> 00:23:13,960 Tliet, seba ', ħames. 643 00:23:13,960 --> 00:23:15,590 OK, I know Neil kien l-iżgħar. 644 00:23:15,590 --> 00:23:18,110 X'hemm-ħaġa sempliċi għalija li tagħmel issa? 645 00:23:18,110 --> 00:23:21,410 Jien ma jmur l-iskart ħin tiegħi bi ftit tbaqbieq Neil wieħed spot lejn ix-xellug. 646 00:23:21,410 --> 00:23:25,350 Għaliex ma I biss jitqiegħed Neil fejn hu jappartjeni, li naturalment huwa fejn? 647 00:23:25,350 --> 00:23:26,160 >> It-triq kollha fil-bidu. 648 00:23:26,160 --> 00:23:27,720 Allura Neil, come miegħi. 649 00:23:27,720 --> 00:23:28,910 U dak kien l-isem tiegħek mill-ġdid? 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 Allura Grace, sfortunatament, int tip ta 'fil-mod. 654 00:23:32,490 --> 00:23:34,290 Allura kif nistgħu issolvi din il-problema? 655 00:23:34,290 --> 00:23:34,490 Dritt? 656 00:23:34,490 --> 00:23:37,500 Jekk dan huwa firxa, hemm biss seba 'postijiet. 657 00:23:37,500 --> 00:23:40,830 Ifakkar li, bil Rob, tkellimna dwar tiddikjara etajiet, u aħna biss kellhom 658 00:23:40,830 --> 00:23:41,740 numru finit ta 'etajiet? 659 00:23:41,740 --> 00:23:42,535 Istess idea hawn. 660 00:23:42,535 --> 00:23:44,300 Aħna biss numru finit ta 'ints. 661 00:23:44,300 --> 00:23:47,590 Grace huwa tip ta fil tagħna mod, hekk kif nistgħu jiffissaw? 662 00:23:47,590 --> 00:23:49,555 >> L-eħfef mod huwa simili, Grace, sorry. 663 00:23:49,555 --> 00:23:51,870 Int ser ikollok tmur fuq hemm hekk nistgħu nagħmlu kamra. 664 00:23:51,870 --> 00:23:55,290 Issa, jekk taħseb dwar dan, forsi aħna biss għamel il-problema agħar. 665 00:23:55,290 --> 00:23:58,510 U forsi għamilna, għaliex dak li jekk Grace kienu fil-post it-tajjeb? 666 00:23:58,510 --> 00:24:01,730 Imma nafu hi li ma, għaliex mod ieħor, kienet tkun 667 00:24:01,730 --> 00:24:03,980 wieqfa quddiem minflok Neil f'dan iż-żmien, id-dritt? 668 00:24:03,980 --> 00:24:05,550 Aħna diġà ċċekkjati numru tagħha out. 669 00:24:05,550 --> 00:24:05,770 >> Kull dritt. 670 00:24:05,770 --> 00:24:09,110 Allura issa, Neil fil-post it-tajjeb, u I tista 'tagħmel ottimizzazzjoni żgħira. 671 00:24:09,110 --> 00:24:11,740 Għall-minuta li jmiss, jien ser jinjora Neil kollha flimkien, sabiex ma 672 00:24:11,740 --> 00:24:15,280 jaħlux ħin tiegħu, jew aċċidentalment tpartit lilu għall-post żbaljat. 673 00:24:15,280 --> 00:24:17,805 Allura issa, kif nista 'nsib li jmiss element li l-iżgħar? 674 00:24:17,805 --> 00:24:18,480 Tnejn. 675 00:24:18,480 --> 00:24:20,225 Li numru pjuttost tajba, jekk inti tixtieq li pass 'il quddiem u 676 00:24:20,225 --> 00:24:21,100 I ser ftakar li inti. 677 00:24:21,100 --> 00:24:21,980 Sitta, l-ebda tajba. 678 00:24:21,980 --> 00:24:24,820 Erba, tlieta, seba ', ħames, mhux tajba. 679 00:24:24,820 --> 00:24:26,800 So let me jimxu inti post dritt tiegħek. 680 00:24:26,800 --> 00:24:28,470 U aħna biss ltqajna xxurtjati dan iż-żmien. 681 00:24:28,470 --> 00:24:31,350 >> Issa, jien ser jinjora dawn żewġ guys, u issa jagħmlu waħda aktar 682 00:24:31,350 --> 00:24:32,260 jgħaddu dan. 683 00:24:32,260 --> 00:24:33,490 Sitta, li numru żgħir pretty. 684 00:24:33,490 --> 00:24:34,300 Come fuq quddiem. 685 00:24:34,300 --> 00:24:35,220 Oh, sorry. 686 00:24:35,220 --> 00:24:37,640 Numru Grace huwa aħjar, hekk pass fuq quddiem. 687 00:24:37,640 --> 00:24:38,260 Erbgħa. 688 00:24:38,260 --> 00:24:39,120 Jiddispjacini, Grace. 689 00:24:39,120 --> 00:24:39,950 Mur lura. 690 00:24:39,950 --> 00:24:41,550 Numru tlieta huwa aħjar. 691 00:24:41,550 --> 00:24:42,290 Seven. 692 00:24:42,290 --> 00:24:42,720 Ħamsa. 693 00:24:42,720 --> 00:24:43,550 U issa dak l-isem tiegħek mill-ġdid? 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 Allura Jason issa huwa l-iżgħar element stajt magħżula. 697 00:24:47,050 --> 00:24:49,160 Fejn huwa hu se jmorru? 698 00:24:49,160 --> 00:24:50,380 Għalhekk, fejn huwa sitta. 699 00:24:50,380 --> 00:24:51,210 U l-isem tiegħek hija għal darb'oħra? 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 huwa fil-mod. 703 00:24:53,220 --> 00:24:54,640 X'hemm-eħfef ħaġa li tagħmel? 704 00:24:54,640 --> 00:24:58,390 Tpartit dawn iż-żewġ guys u tkompli. 705 00:24:58,390 --> 00:24:59,020 Allura issa ejja ara. 706 00:24:59,020 --> 00:25:00,170 Min hu l-iżgħar? 707 00:25:00,170 --> 00:25:01,030 Erbgħa. 708 00:25:01,030 --> 00:25:01,990 Let me biss tip ta 'iqarrqu. 709 00:25:01,990 --> 00:25:03,090 Ta 'ħames se tkun l-iżgħar. 710 00:25:03,090 --> 00:25:05,220 I isibu li jmiss, jekk, inti tixtieq li pass quddiem, x'għandi nagħmel għandhom x'jaqsmu ma ' 711 00:25:05,220 --> 00:25:06,820 dawn guys, bl Gabe? 712 00:25:06,820 --> 00:25:08,450 Tpartit mill-ġdid. 713 00:25:08,450 --> 00:25:10,740 Allura issa, għadu ftit out of order. 714 00:25:10,740 --> 00:25:14,140 I sabet Gabe l-iżgħar, so I pop lilu out, inti timxi guys fuq. 715 00:25:14,140 --> 00:25:15,190 U jsir. 716 00:25:15,190 --> 00:25:17,200 >> Allura tweġiba hija l-istess. 717 00:25:17,200 --> 00:25:18,600 Ir-riżultat aħħari huwa l-istess. 718 00:25:18,600 --> 00:25:22,730 Liema minn dawn iż-żewġ algoritmi hija aħjar? 719 00:25:22,730 --> 00:25:23,500 It-tieni waħda, I jinstemgħu. 720 00:25:23,500 --> 00:25:24,252 Għaliex? 721 00:25:24,252 --> 00:25:25,900 >> SPEAKER 3: Huwa n-passi [inaudible]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. Malan: Huwa passi n-iktar tard. 723 00:25:27,600 --> 00:25:28,490 Interessanti. 724 00:25:28,490 --> 00:25:30,610 Allura huwa għalkemm? 725 00:25:30,610 --> 00:25:33,630 Allura kif ma nsib l- element iżgħar? 726 00:25:33,630 --> 00:25:37,060 Kemm passi ħafna ma I għandhom jieħdu isibu l-iżgħar element? 727 00:25:37,060 --> 00:25:39,220 I kellhom ħarsa-triq kollha fl-aħħar, id-dritt? 728 00:25:39,220 --> 00:25:41,530 Għaliex f'dak agħar każ, liema jekk Neil kienu aktar hawn? 729 00:25:41,530 --> 00:25:45,700 Hekk biss konstatazzjoni tal-iżgħar element jieħu me n passi, jew minus 1 n. 730 00:25:45,700 --> 00:25:46,100 Iżda, OK. 731 00:25:46,100 --> 00:25:46,980 Allura jiffissaw Neil. 732 00:25:46,980 --> 00:25:48,740 Ftakar li, minuta jew hekk ilu. 733 00:25:48,740 --> 00:25:51,680 >> Imma kif ma nsib li jmiss element iżgħar? 734 00:25:51,680 --> 00:25:54,830 Huwa n minus 1, jew n minus 2 tassew, min-numru ta 'passi. 735 00:25:54,830 --> 00:25:55,440 Allura OK. 736 00:25:55,440 --> 00:25:57,390 So I ma n minus 2. 737 00:25:57,390 --> 00:25:57,600 Kull dritt. 738 00:25:57,600 --> 00:25:59,130 Allura li jħoss ftit aħjar. 739 00:25:59,130 --> 00:25:59,730 Kull dritt. 740 00:25:59,730 --> 00:26:03,270 Kemm passi l-ħin li jmiss issib numru tlieta? 741 00:26:03,270 --> 00:26:04,420 Allura n minus 4. 742 00:26:04,420 --> 00:26:07,670 Allura huwa jonqos, wieħed inqas pass fuq kull iterazzjoni. 743 00:26:07,670 --> 00:26:08,740 Allura dan ma tħossok aħjar, id-dritt? 744 00:26:08,740 --> 00:26:13,450 Jekk l-aħħar darba kien madwar n ħinijiet n, din id-darba n minus 1, plus minus n 745 00:26:13,450 --> 00:26:16,500 2, plus minus n 3, plus n minus 4, dot, dot, dot. 746 00:26:16,500 --> 00:26:18,750 Imma jekk inti recall mill-iskola għolja tiegħek kotba, l-iqarrqu ftit 747 00:26:18,750 --> 00:26:24,380 sheet fid-dahar li għandu formuli, jekk inti żid up din is-serje ta 'numri, 748 00:26:24,380 --> 00:26:31,280 liema huwa l-għadd totali ta 'passi se tkun li nieħu hawn? 749 00:26:31,280 --> 00:26:36,580 >> Din hija waħda minn dawk, simili, n minus 1, il-ħinijiet n, diviż 2. 750 00:26:36,580 --> 00:26:39,040 So let me ara jekk I jistgħu jiġbdu dan up għal ftit mument. 751 00:26:39,040 --> 00:26:42,230 U għal darb'oħra, jien tip ta 'arrotondament f'xi numri biss biex iżommu sempliċi ħajja tagħna, 752 00:26:42,230 --> 00:26:47,830 iżda bħala I recall, huwa xi ħaġa simili jekk I do n minus 1-affarijiet, allura n minus 753 00:26:47,830 --> 00:26:53,570 2, allura n minus 3, huwa bejn wieħed u ieħor xi ħaġa bħal din aktar minn 2, u jekk I 754 00:26:53,570 --> 00:26:55,510 immoltiplika dan out, li attwalment n kwadru. 755 00:26:55,510 --> 00:26:58,940 Li ma tħossok wisq tajbin. n minus n aktar minn 2. 756 00:26:58,940 --> 00:27:00,350 >> Iżda hawn l-ħaġa. 757 00:27:00,350 --> 00:27:03,720 Fix-xjenza tal-kompjuter, meta l-problemi tibda tikseb interessanti huwa meta n 758 00:27:03,720 --> 00:27:04,700 gets verament kbir. 759 00:27:04,700 --> 00:27:08,110 U meta n gets verament kbira, li ta ' dawn il-valuri se jiddominaw kollha 760 00:27:08,110 --> 00:27:09,750 mill-oħrajn? 761 00:27:09,750 --> 00:27:10,990 Huwa tip ta 'n kwadrat, right? 762 00:27:10,990 --> 00:27:13,340 Iva, jiġi diviż bi 2 hija pjuttost tajba. 763 00:27:13,340 --> 00:27:16,740 Imma jekk inti qed jitkellem dwar biljuni ta 'biċċiet ta' data, jew triljuni ta ' 764 00:27:16,740 --> 00:27:18,700 biċċiet ta 'data, Ok, sabiex int darbtejn aktar malajr. 765 00:27:18,700 --> 00:27:22,440 Imma li verament jimpurtah jekk dak in-numru kbir, jekk dan il-fattur huwa dak gets 766 00:27:22,440 --> 00:27:23,040 akbar u akbar. 767 00:27:23,040 --> 00:27:25,990 U żgur, jagħmel aktar ta ' differenza minn dan Guy. 768 00:27:25,990 --> 00:27:29,120 Allura anke jekk inti guys huma dritt, il- tieni algoritmu, aħna ser sejħa hija 769 00:27:29,120 --> 00:27:32,970 sort għażla, hija, fid-dinja reali, a bit malajr potenzjalment, minħabba I am 770 00:27:32,970 --> 00:27:35,360 tieħu anqas u anqas passi kull darba. 771 00:27:35,360 --> 00:27:37,340 >> Mhuwiex verament fundamentalment aktar malajr. 772 00:27:37,340 --> 00:27:41,430 Għaliex jekk aħna fil-fatt play dan out għal valuri kbar ta 'n, fl-aħħar ta' 773 00:27:41,430 --> 00:27:44,750 il-jum, għal n kbir biżżejjed, huwa għadu se jħossu pretty bil-mod. 774 00:27:44,750 --> 00:27:46,770 Well, let me tieħu waħda jgħaddi l-aħħar f'dak. 775 00:27:46,770 --> 00:27:48,920 Dan huwa dak I call sort għażla. 776 00:27:48,920 --> 00:27:51,040 Tista guys reset yourselves aħħar darba? 777 00:27:51,040 --> 00:27:53,550 U f'dan il-aħħar każ, jien ser li tipproponi xi ħaġa 778 00:27:53,550 --> 00:27:54,970 imsejħa sort inserzjoni. 779 00:27:54,970 --> 00:27:57,470 Sort Inserzjoni tkun, kunċettwalment, daqsxejn differenti. 780 00:27:57,470 --> 00:28:00,980 >> Pjuttost milli jmorru quddiem u lura u għażla tal-iżgħar element, jien 781 00:28:00,980 --> 00:28:05,030 biss jmorru biex jittrattaw ma 'kull wieħed minn dawn guys kif I jiltaqgħu magħhom, u daħħal 782 00:28:05,030 --> 00:28:06,850 minnhom fil-post korretta tagħhom. 783 00:28:06,850 --> 00:28:10,160 Hekk jien biss ser tibda bil Grace, u nara li hi numru erbgħa. 784 00:28:10,160 --> 00:28:11,720 Fejn ma numru erbgħa jappartjenu? 785 00:28:11,720 --> 00:28:14,940 I ma bdew issortjar xejn, hekk Grace gets li tissospendi hemm dritt. 786 00:28:14,940 --> 00:28:18,355 U issa jien ser jitolbu, jekk inti tista ' tieħu pass għal-lemin tiegħek, dan 787 00:28:18,355 --> 00:28:21,650 lista magħżula tiegħi, dan huwa tiegħi lista li jifdal mhux magħżul. 788 00:28:21,650 --> 00:28:23,260 Allura issa jien ser tipproċedi jmiss, u dak l-isem tiegħek mill-ġdid? 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 Allura Branson huwa numru żewġ. 792 00:28:25,375 --> 00:28:27,490 Hekk jien ser tieħu inti out għal mument. 793 00:28:27,490 --> 00:28:30,940 U issa, fejn do inti jappartjenu f'dan firxa? 794 00:28:30,940 --> 00:28:32,360 Allura għad-dritt ta Grace. 795 00:28:32,360 --> 00:28:35,670 Għalhekk għal darb'oħra, aħna qed tip ta 'teħid Grace jagħmlu ħafna xogħol hawnhekk. 796 00:28:35,670 --> 00:28:37,290 Fejn nistgħu tpoġġi lilek? 797 00:28:37,290 --> 00:28:40,120 Allura aħna qed tmur biex slide inti l- xellug, u daħħal Branson hemmhekk. 798 00:28:40,120 --> 00:28:41,680 Imma issa I jsostnu li inti guys qed isir. 799 00:28:41,680 --> 00:28:43,240 Imma avviż, jien ma jużaw spazju żejjed. 800 00:28:43,240 --> 00:28:45,130 Huwa għadu 2 elementi hawn, 5 hawn fuq. 801 00:28:45,130 --> 00:28:47,910 Daqs l-array totali huwa 7, hekk jien mhux qerq, id-dritt? 802 00:28:47,910 --> 00:28:51,950 >> Allura issa għandna, ma Gabe hawn, il- numru sitta, fejn do inti jappartjenu? 803 00:28:51,950 --> 00:28:52,650 You ltqajna xxurtjati darb'oħra. 804 00:28:52,650 --> 00:28:53,820 Allura ikollok li tissospendi hemm dritt. 805 00:28:53,820 --> 00:28:57,210 Just tieħu pass żgħir lejn il-lemin biss biex jagħmilha ċara li int magħżula. 806 00:28:57,210 --> 00:29:00,520 U issa għandna Neil darb'oħra, numru wieħed, fejn ma tmur? 807 00:29:00,520 --> 00:29:03,540 U issa huwa fejn aħna ser tibda tara li dan algoritmu, għalkemm fuq l-ewwel 808 00:29:03,540 --> 00:29:05,950 daqqa t'għajn, iħoss pretty intelliġenti, watch x'hemm sejjer iseħħ. 809 00:29:05,950 --> 00:29:07,370 Jekk inti tista 'pass' il quddiem. 810 00:29:07,370 --> 00:29:09,260 >> Fejn irridu li tqiegħed Neil? 811 00:29:09,260 --> 00:29:11,830 Allura ovvjament hawnhekk, hekk kif nilħqu Neil hemmhekk? 812 00:29:11,830 --> 00:29:12,970 Ejja nagħmlu dan il-pass-pass. 813 00:29:12,970 --> 00:29:15,620 Gabe, fejn għandek bżonn biex tmur? 814 00:29:15,620 --> 00:29:19,590 Yep, sabiex jieħdu pass wieħed kbir, jew żewġ nofs passi biex jagħmlu 815 00:29:19,590 --> 00:29:20,820 pass wieħed hemmhekk. 816 00:29:20,820 --> 00:29:21,750 Grace, fejn inti tmur? 817 00:29:21,750 --> 00:29:22,510 Tajba. 818 00:29:22,510 --> 00:29:23,500 Allura pass ieħor. 819 00:29:23,500 --> 00:29:24,960 U fl-aħħarnett, Branson? 820 00:29:24,960 --> 00:29:25,460 Pass ieħor. 821 00:29:25,460 --> 00:29:27,190 U issa nistgħu npoġġu Neil fis-seħħ. 822 00:29:27,190 --> 00:29:28,440 >> Allura issa, ikomplu din il-loġika. 823 00:29:28,440 --> 00:29:32,420 Anki jekk aħna mhux ċaqliq Neil fuq, u aktar, u aktar, li jniżżlu 824 00:29:32,420 --> 00:29:36,420 fejn imur, fl-agħar każ, il- numru li jmiss nistgħu jiltaqgħu jistgħu 825 00:29:36,420 --> 00:29:42,220 jkun in-numru, ngħidu aħna, kien hemm numru żero, allura aħna qed tmur li ċċaqlaq kollha 826 00:29:42,220 --> 00:29:42,730 dawn guys. 827 00:29:42,730 --> 00:29:44,950 Ejja ngħidu li hemm numru, negattiv waħda, allura għandna għall-bidla 828 00:29:44,950 --> 00:29:46,080 kollha ta 'dawn guys. 829 00:29:46,080 --> 00:29:48,500 Allura aħna qed verament biss tip ta 'flipping il-problema madwar, bħal li aħna qed 830 00:29:48,500 --> 00:29:52,620 jittrasferixxi l-ispiża mill- proċess ta 'għażla sabiex l-inserzjoni 831 00:29:52,620 --> 00:29:56,930 proċess, b'tali mod li inti guys biss kellhom jimxu madwar n minus xi ħaġa 832 00:29:56,930 --> 00:29:57,940 numru ta 'passi. 833 00:29:57,940 --> 00:30:01,200 U dak in-numru ta 'passi huwa biss se jiżdied hekk kif I jagħżlu numri aktar, 834 00:30:01,200 --> 00:30:04,730 jekk I għandhom iżommu shoving inti guys lura, u lura, u lura. 835 00:30:04,730 --> 00:30:08,320 >> Allura l-ħaġa diqa hija issa kollha ta 'dawn algoritmi huma n kwadru. 836 00:30:08,320 --> 00:30:10,570 Ejja imorru quddiem u grazzi għal dawn guys, u Ħares dawn daqsxejn 837 00:30:10,570 --> 00:30:11,090 differenti. 838 00:30:11,090 --> 00:30:12,312 Ħafna isir ukoll. 839 00:30:12,312 --> 00:30:14,120 >> [Applause] 840 00:30:14,120 --> 00:30:15,030 >> Kull dritt. 841 00:30:15,030 --> 00:30:16,280 Hemm inti tmur. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Grazzi għall - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [inaudible] jżomm in-numri. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. Malan: Le, inti tista ' iżommu n-numri kif ukoll. 846 00:30:21,990 --> 00:30:23,440 Kull dritt. 847 00:30:23,440 --> 00:30:24,100 Nicely jsir. 848 00:30:24,100 --> 00:30:25,300 Kull dritt. 849 00:30:25,300 --> 00:30:30,510 Mela ejja ara jekk ma nkunux nistgħu issa tqassar aktar malajr, u aktar viżwalment, 850 00:30:30,510 --> 00:30:33,410 eżattament dak li ġara biss hawn kif ġej. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Jien ser jimxi 'l quddiem u iġbed up Firefox. 853 00:30:38,770 --> 00:30:41,310 Aħna ser jorbot dan dimostrazzjoni fuq il-websajt il-kors tal. 854 00:30:41,310 --> 00:30:43,870 Java huwa daqsxejn tedjanti biex tikseb xogħol f'xi browsers dawn il-jiem. 855 00:30:43,870 --> 00:30:46,760 Mela jekk inti play ma 'dan fid-dar, tirrealizza jista 'jkollok bżonn biex jużaw Firefox 856 00:30:46,760 --> 00:30:47,990 biex tiksbu tax-xogħol. 857 00:30:47,990 --> 00:30:50,440 U dak li jien ser tagħmel ma 'dan dimostrazzjoni huma dawn li ġejjin. 858 00:30:50,440 --> 00:30:54,875 >> Fil-qiegħ, I jkollhom mazz sħiħ ta ' għażliet menu, inkluż bidu u 859 00:30:54,875 --> 00:30:55,840 stop buttuna. 860 00:30:55,840 --> 00:30:59,450 Wkoll, bħala twarrib, jidher li jkun bug f'dawn il-programmi, fejn inti 861 00:30:59,450 --> 00:31:03,720 ma tistax attwalment ara l-bidu jew tieqaf buttuna sakemm inti żżomm Kmand jew Alt 862 00:31:03,720 --> 00:31:06,560 plus u zoom fi, li curiously jurik buttuni aktar. 863 00:31:06,560 --> 00:31:09,090 Hekk biss FYI jekk inti play ma 'dan fid-dar. 864 00:31:09,090 --> 00:31:12,870 Issa jien ser ikklikkja Start fi ftit mument, wara li jispeċifikaw dewmien ta ', 865 00:31:12,870 --> 00:31:16,810 simili, 200 millisekondi hawn, just hekk nistgħu naraw x'jiġri. 866 00:31:16,810 --> 00:31:20,180 >> So I jsostnu li dan huwa viżwalizzazzjoni ta 'l-ewwel algoritmu 867 00:31:20,180 --> 00:31:23,730 dawn guys ma, sort bubble, fejn aħna biddlu nies par għaqli. 868 00:31:23,730 --> 00:31:27,490 L-għarfien ċavetta għal din viżwalizzazzjoni huwa li l-għoli tal-bars 869 00:31:27,490 --> 00:31:30,510 tirrappreżenta d-daqs tan-numru. 870 00:31:30,510 --> 00:31:32,210 Allura l-taller l-bar, il- akbar in-numru. 871 00:31:32,210 --> 00:31:33,680 Iqsar l-bar, iżgħar in-numru. 872 00:31:33,680 --> 00:31:38,630 U jekk tinnota, aħna qed tmur permezz l-ewwel iterazzjoni ta 'dan algoritmu, 873 00:31:38,630 --> 00:31:42,620 iskambji numri kbar u żgħar, sabiex in-numru żgħir jiġi l-ewwel u 874 00:31:42,620 --> 00:31:44,280 in-numru kbir imur lejn il-lemin. 875 00:31:44,280 --> 00:31:48,770 >> U hekk kif aħna jiksbu l-aħħar ta 'firxa ta 'ħafna aktar minn seba' numri, aħna qed 876 00:31:48,770 --> 00:31:49,900 se jmorru lura għall-bidu. 877 00:31:49,900 --> 00:31:51,140 U jantiċipaw dan. 878 00:31:51,140 --> 00:31:54,860 Fuq ix-xellug, li Guy ftit għaddej tpartit għall-ġenb, u dan 879 00:31:54,860 --> 00:31:56,010 jirrepeti proċess. 880 00:31:56,010 --> 00:31:59,450 Issa dan viżwalizzazzjoni malajr gets boring, so let me imorru quddiem u stop 881 00:31:59,450 --> 00:32:04,170 dan, jibdlu l-ħaġa wisq dewmien aktar mgħaġġel biss li tikseb issa, jħossu għal 882 00:32:04,170 --> 00:32:05,060 dan algoritmu. 883 00:32:05,060 --> 00:32:07,840 >> Allura anke jekk stajt titħaffef it up, dan huwa bħal titjib proċessur tiegħi, ix-xiri 884 00:32:07,840 --> 00:32:08,580 kompjuter ġdid. 885 00:32:08,580 --> 00:32:12,980 I ma nbidlux fundamentalment tiegħi algoritmu, imma int tista 'tabilħaqq tara aktar 886 00:32:12,980 --> 00:32:16,800 ċar milli mal-bnedmin, li l-big in-numri huma tbaqbieq sal-quċċata, 887 00:32:16,800 --> 00:32:20,900 u n-numri żgħar huma tbaqbieq sal-qiegħ. 888 00:32:20,900 --> 00:32:22,390 U issa dan il-ħaġa hawn magħżula. 889 00:32:22,390 --> 00:32:25,260 U bħala twarrib, fil-pjazez, hemm biss ftit bookkeeping hemm biex 890 00:32:25,260 --> 00:32:28,010 jgħinu inti għadd kemm paraguni, jew kif ħafna swaps għandhom 891 00:32:28,010 --> 00:32:28,950 attwalment sar. 892 00:32:28,950 --> 00:32:30,750 >> Well, ejja ipprova wieħed ta ' l-oħrajn rajna. 893 00:32:30,750 --> 00:32:37,116 Let me ikklikkja fuq tip bużżieqa hawn, u let me jagħżlu, u din il-paġna web kollu 894 00:32:37,116 --> 00:32:38,936 huwa Buggy ftit. 895 00:32:38,936 --> 00:32:41,155 Ejja taċċetta r-riskju u run mill-ġdid. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Hemm immorru. 898 00:32:45,030 --> 00:32:47,180 Mela ejja jagħmlu sort għażla. 899 00:32:47,180 --> 00:32:49,140 I do not know għaliex il-menu jidher hemmhekk. 900 00:32:49,140 --> 00:32:54,070 Ejja zoom fl biex jiffissaw dak bug, tbiddel dan sa 50. 901 00:32:54,070 --> 00:32:56,020 Ah, ejja fil-fatt jagħmlu li ħafna aktar mgħaġġla. 902 00:32:56,020 --> 00:32:59,160 Ħames millisekondi jew hekk, u tibda. 903 00:32:59,160 --> 00:33:00,470 >> Allura dan huwa tip għażla. 904 00:33:00,470 --> 00:33:03,070 Għalhekk għal darb'oħra, jaħsbu dwar dak li aħna għamlet mal-bnedmin up hawn. 905 00:33:03,070 --> 00:33:08,490 Aħna marru permezz tal-firxa u magħżula l-iżgħar element ġdid, 906 00:33:08,490 --> 00:33:09,250 u għal darb'oħra, u għal darb'oħra. 907 00:33:09,250 --> 00:33:11,110 Now I jsostnu li kien għadu pretty bad. 908 00:33:11,110 --> 00:33:15,010 Kien għadu n kwadrat, jagħtu jew jieħu, imma kien, fid-dinja reali, daqsxejn 909 00:33:15,010 --> 00:33:18,280 aktar malajr, minħabba I kien tabilħaqq tieħu kemmxejn inqas passi kull darba. 910 00:33:18,280 --> 00:33:19,800 Iżda aħna qed jitkellem biss dak? 911 00:33:19,800 --> 00:33:21,830 Forsi 40 jew hekk bars hawn? 912 00:33:21,830 --> 00:33:23,200 Aħna ma jitkellem 40 miljun. 913 00:33:23,200 --> 00:33:27,430 Allura mhuwiex totalment ċar għalija li kienet tabilħaqq żieda sinjifikanti. 914 00:33:27,430 --> 00:33:32,530 >> Let me issa jmorru lura u l-bidla għal tagħna tielet algoritmu, li kien tagħżel 915 00:33:32,530 --> 00:33:33,180 sort inserzjoni. 916 00:33:33,180 --> 00:33:36,380 U issa huwa verament Buggy minħabba li l- menu verament ma għandu jkun hemm isfel. 917 00:33:36,380 --> 00:33:40,840 Allura issa aħna ser iscroll back up here u tibda dan algoritmu. 918 00:33:40,840 --> 00:33:43,270 Konvulżjonijiet, startjar u waqfien. 919 00:33:43,270 --> 00:33:47,160 Allura dan it-tip wieħed ta ikollu mudell pretty lilha, fejn aħna napprovaw qed 920 00:33:47,160 --> 00:33:50,240 jiddaħħlu l-bnedmin, jew F'dan il-każ, il-bars fis 921 00:33:50,240 --> 00:33:52,620 post xieraq tagħhom. 922 00:33:52,620 --> 00:33:55,430 U huwa diġà sar qabel I daru madwar. 923 00:33:55,430 --> 00:33:58,940 Iżda dan wieħed, wisq, fit-teorija, għadu n kwadru. 924 00:33:58,940 --> 00:34:01,430 >> Mela ejja ara jekk ma nkunux nistgħu tqassar dawn kif ġej. 925 00:34:01,430 --> 00:34:04,750 Jien ser imorru quddiem u biss biex tagħti us tip ta 'mod komuni ta' titkellem 926 00:34:04,750 --> 00:34:08,489 dwar dawn l-affarijiet, let me jintroduċu biss daqsxejn ta 'notazzjoni hawn. 927 00:34:08,489 --> 00:34:12,480 Int ser tara xi ħaġa imsejħa big O, minħabba li huwa litteralment a big 928 00:34:12,480 --> 00:34:16,320 O. U dan huwa mod li l-kompjuter xjentist jew matematiku anke juża 929 00:34:16,320 --> 00:34:19,230 biex jiddeskrivu l-running time ta 'xi algoritmu. 930 00:34:19,230 --> 00:34:21,400 Kif passi ħafna ma attwalment jieħdu? 931 00:34:21,400 --> 00:34:25,080 >> Issa jien ser jimbarazza myself ma ' kalligrafija tiegħi hawn fi ftit mument. 932 00:34:25,080 --> 00:34:29,020 Iżda let me imorru quddiem u jgħidu li dan se jkun kbir O hawn fuq. 933 00:34:29,020 --> 00:34:33,610 U let me jintroduċu waħda oħra simbolu, a omega kapital. 934 00:34:33,610 --> 00:34:37,080 Omega se tkun l-oppost, essenzjalment, ta 'big O. Billi big O 935 00:34:37,080 --> 00:34:40,790 mezzi, fl-agħar każ, kemm ħin jista xi algoritmu jieħu, fir- 936 00:34:40,790 --> 00:34:43,480 f'termini ta 'n, omega se jkun kemm ħin jista 'dan 937 00:34:43,480 --> 00:34:45,409 tieħu fil-każ aħjar. 938 00:34:45,409 --> 00:34:48,090 U aħna ser tara dak li jfisser minn aħjar każ fi ftit mument. 939 00:34:48,090 --> 00:34:49,940 >> Mela ejja nibdew xi ħaġa sempliċi. 940 00:34:49,940 --> 00:34:54,719 Nibda ma 'tfittxija lineari. 941 00:34:54,719 --> 00:34:55,679 Allura mhux issortjar. 942 00:34:55,679 --> 00:34:58,000 Aħna ser sejħa dan tfittxija lineari. 943 00:34:58,000 --> 00:35:01,140 U issa, jagħmlu ftit tabella barra ta 'dan. 944 00:35:01,140 --> 00:35:06,600 U issa, fil-każ tat-tfittxija lineari, fl-agħar każ, kemm passi huwa 945 00:35:06,600 --> 00:35:11,770 Huwa ser jieħu me biex isibu numru ta 'għażla arbitrarja? 946 00:35:11,770 --> 00:35:14,540 U hemm bibien totali n jew n-numri totali. 947 00:35:14,540 --> 00:35:15,940 L-agħar każ. 948 00:35:15,940 --> 00:35:18,800 Kemm passi ħafna jien ser ikollhom jieħdu biex issib in-numru 50 fil-firxa 949 00:35:18,800 --> 00:35:20,830 ta 'bibien n? 950 00:35:20,830 --> 00:35:21,410 U għaliex? 951 00:35:21,410 --> 00:35:23,680 Minħabba li jista 'jkun l- mod fuq fuq l-aħħar. 952 00:35:23,680 --> 00:35:27,120 Tant simili Jennifer ltaqgħu magħhom, l- numru 50 kienet it-triq kollha madwar, hekk 953 00:35:27,120 --> 00:35:30,760 l-agħar każ tfittxija lineari huwa big O ta 'n, aħna ser ngħidu. 954 00:35:30,760 --> 00:35:33,430 >> Xi ngħidu dwar l-aħjar każ, jekk ikollok verament xxurtjati? 955 00:35:33,430 --> 00:35:36,200 Huwa biss ser jieħdu pass wieħed, jew numru ta 'passi kostanti. 956 00:35:36,200 --> 00:35:37,830 Allura aħna ser jiddeskrivu li bħala 1. 957 00:35:37,830 --> 00:35:39,010 Allura dan huwa pjuttost tajba. 958 00:35:39,010 --> 00:35:41,210 Issa dak li jekk aħna ma xi ħaġa bħal tfittxija binarja? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Tfittxija Allura binarju, fl-agħar każ, ħa kemm ħin? 961 00:35:47,846 --> 00:35:49,250 >> [INTERPOSING VUĊI] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. Malan: So attwalment, I smajtu fi postijiet koppja. 963 00:35:51,310 --> 00:35:56,390 Allura huwa attwalment log n, jagħtu jew jieħu, għaliex kif aħna jaqsam il-lista fil nofs 964 00:35:56,390 --> 00:36:00,730 għal darb'oħra, u għal darb'oħra, u għal darb'oħra, aħna qed kapaċi biex isibu, finalment, il-valur, 965 00:36:00,730 --> 00:36:04,750 jekk huwa hemmhekk, iżda hemm qabda. 966 00:36:04,750 --> 00:36:08,590 X'hemm-suppożizzjoni li rridu jieħdu għal mogħtija għat-tiftix binarju? 967 00:36:08,590 --> 00:36:09,700 Għandu jiġi magħżul. 968 00:36:09,700 --> 00:36:12,770 Mhuwiex magħżula, inti tista 'taqsam il-ħaġa fil nofs mill-ġdid u għal darb'oħra, u għandek 969 00:36:12,770 --> 00:36:15,490 tista 'tmur xellug, u inti tista' tmur dritt, u inti tista 'tmur xellug u lemin, imma int 970 00:36:15,490 --> 00:36:18,070 mhux ser isibu l-element jekk il-lista mhix magħżula, minħabba 971 00:36:18,070 --> 00:36:18,790 inti tista 'titlef dan. 972 00:36:18,790 --> 00:36:22,120 Minħabba heuristic tiegħek, biex imur xellug jew dritt se tkun difettuż jekk huwa 973 00:36:22,120 --> 00:36:23,420 tabilħaqq jkunux magħżula. 974 00:36:23,420 --> 00:36:26,110 Allura hemm tip ta 'spiża moħbija għall-użu xi ħaġa bħal din. 975 00:36:26,110 --> 00:36:29,250 >> Issa, ejja jmorru fil issortjar tagħna algoritmi ma jistgħux tiftix - 976 00:36:29,250 --> 00:36:31,140 oh, fil-fatt ejja imorru f'dan vojt. 977 00:36:31,140 --> 00:36:33,190 Tfittxija Binarju fl-aħjar każ? 978 00:36:33,190 --> 00:36:36,290 Huwa wkoll 1 jekk hija biss jiġri li jkun fin-nofs ħafna mill-firxa, jew 979 00:36:36,290 --> 00:36:37,810 -nofs tal-ktieb tat-telefon. 980 00:36:37,810 --> 00:36:39,710 Issa ejja jagħmlu sort bubble. 981 00:36:39,710 --> 00:36:42,570 Għalhekk għal darb'oħra, issa aħna qed jidħlu fil- xorta, mhux il-tfittxijiet. 982 00:36:42,570 --> 00:36:47,220 >> Fl-agħar każ, kemm-passi ma we talba bubble sort għaddej biex tieħu? 983 00:36:47,220 --> 00:36:48,410 n kwadrat. 984 00:36:48,410 --> 00:36:49,200 Hekk jien ser tiġbed dan. 985 00:36:49,200 --> 00:36:51,710 Ooh, kalligrafija tiegħi jistenna saħansitra agħar meta huwa proġettat li big. 986 00:36:51,710 --> 00:36:52,510 Kull dritt. 987 00:36:52,510 --> 00:36:53,570 Allura thats n kwadru. 988 00:36:53,570 --> 00:36:59,460 U fl-aħjar każ ta 'tip bużżieqa, kemm passi huwa se tieħu? 989 00:36:59,460 --> 00:37:00,980 1, I jinstemgħu. 990 00:37:00,980 --> 00:37:01,760 >> SPEAKER 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. Malan: n, I jinstemgħu. 992 00:37:03,286 --> 00:37:04,200 >> SPEAKER 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. Malan: 2, smajt. 994 00:37:05,010 --> 00:37:06,670 Do Nisma 3? 995 00:37:06,670 --> 00:37:07,080 Kull dritt. 996 00:37:07,080 --> 00:37:11,390 So I widnejna 1, n, 2, imma ejja pick apparti mill-inqas l-ewwel ta 'dawk 997 00:37:11,390 --> 00:37:12,330 suġġerimenti, 1. 998 00:37:12,330 --> 00:37:15,370 Mhuwiex istint ħażin, għaliex tip ta 'ssegwi mudell hawn. 999 00:37:15,370 --> 00:37:19,670 Iżda jekk hija tieħu biss 1 pass, kif fid- dinja jista I jsostnu li l-lista 1000 00:37:19,670 --> 00:37:22,900 huwa magħżul, għaliex jekk jien permess biss li tieħu pass 1, kemm elementi 1001 00:37:22,900 --> 00:37:25,230 jista I attwalment jivverifika sabiex ikun żgur? 1002 00:37:25,230 --> 00:37:28,270 Well, just 1, li jfisser li hemm n minus 1 elementi li jistgħu jkunu wkoll ta ' 1003 00:37:28,270 --> 00:37:31,310 ordni, u jien biss jmorru fuq il-fidi wara tħares lejn 1 element li l- 1004 00:37:31,310 --> 00:37:31,850 Ħaġa huwa magħżul. 1005 00:37:31,850 --> 00:37:33,930 Allura 1 mhuwiex korrett hawnhekk. 1006 00:37:33,930 --> 00:37:35,710 Allura minimament, kemm għandi tħares lejn? 1007 00:37:35,710 --> 00:37:36,680 >> [INTERPOSING VUĊI] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. Malan: n minus 1, jew verament, n, minħabba I bżonn tħares lejn kull 1009 00:37:40,160 --> 00:37:42,190 element biex tiżgura li mhuwiex out of order. 1010 00:37:42,190 --> 00:37:44,750 Iżda għal darb'oħra, aħna ser issolvi ta 'mewġa tagħna idejn fil-numri iżgħar u 1011 00:37:44,750 --> 00:37:47,100 jassumi li, bħala n gets kbar, dawn qed uninteresting xorta waħda. 1012 00:37:47,100 --> 00:37:48,380 Allura dak it-tip bubble. 1013 00:37:48,380 --> 00:37:49,830 U issa, ejja tagħmel dawn l-aħħar tnejn. 1014 00:37:49,830 --> 00:37:53,520 Sort għażla, u mbagħad aħna ser jagħmlu sort inserzjoni. 1015 00:37:53,520 --> 00:37:57,160 U allura aħna se blow tiegħek imħuħ ma 'xi ħaġa ferm 1016 00:37:57,160 --> 00:37:58,926 aħjar minn kollha ta 'dawn. 1017 00:37:58,926 --> 00:38:00,410 Kull dritt. 1018 00:38:00,410 --> 00:38:04,700 >> X'inhu l-agħar każ running ħin ta 'tip-għażla? 1019 00:38:04,700 --> 00:38:05,680 >> SPEAKER 4: n kwadru. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. Malan: n kwadru, jien seduta. 1021 00:38:06,710 --> 00:38:09,790 Iżda għaliex n kwadrat, intuwittivament? 1022 00:38:09,790 --> 00:38:11,170 >> SPEAKER 4: Għaliex aħna biss ma kien. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. Malan: Għaliex aħna biss ma kien. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Tweġiba tajba. 1026 00:38:13,380 --> 00:38:16,660 Iżda intuwittivament, għaliex hija għażla sort n kwadrat? 1027 00:38:16,660 --> 00:38:18,980 What did għandna nagħmlu ġdid u għal darb'oħra? 1028 00:38:18,980 --> 00:38:22,570 Kellna biex iżommu scanning permezz, huma inti l-iżgħar, inti l- 1029 00:38:22,570 --> 00:38:24,020 iżgħar, inti l-iżgħar. 1030 00:38:24,020 --> 00:38:27,480 U mogħtija, konna kapaċi jieħdu n passi, allura n nieqes 1, allura n minus 2. 1031 00:38:27,480 --> 00:38:30,700 Imma jekk inti-tip ta 'żżid dawk kollha up, jew teħodha fuq il-fidi li stajt miżjud 1032 00:38:30,700 --> 00:38:34,810 lilhom minn qabel, irridu jiksbu madwar n kwadrat minus xi numri iżgħar. 1033 00:38:34,810 --> 00:38:36,730 Hekk jien ser sejħa dan n kwadru. 1034 00:38:36,730 --> 00:38:39,530 Iżda ma sort għażla fl-aħjar każ, kemm passi huwa 1035 00:38:39,530 --> 00:38:40,632 ser tieħu me? 1036 00:38:40,632 --> 00:38:41,840 >> SPEAKER 5: [inaudible] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. Malan: Huwa sfortunatament xorta n kwadrat, right? 1038 00:38:44,350 --> 00:38:49,590 Għaliex jekk jien jintgħażlu l-iżgħar element, u kellna seba 'persuni hawn, 1039 00:38:49,590 --> 00:38:53,280 I biss jafu, ladarba I jiksbu l-ħafna għan, li stajt sabu l-iżgħar 1040 00:38:53,280 --> 00:38:55,670 numru, kull fejn hu jew hi setgħu kienu. 1041 00:38:55,670 --> 00:38:58,820 Imma kif nista 'nsib li jmiss iżgħar numru? 1042 00:38:58,820 --> 00:39:00,160 I għandek tagħmel pass ieħor. 1043 00:39:00,160 --> 00:39:04,810 Allura fl-aħjar każ, liema huwa l- input li sort għażla? 1044 00:39:04,810 --> 00:39:07,830 Huwa ta 'lista tip diġà, numru wieħed, numru tnejn, numru tlieta, numru erbgħa. 1045 00:39:07,830 --> 00:39:08,600 Imma jien kompjuter. 1046 00:39:08,600 --> 00:39:10,190 I tista 'tħares biss lejn wieħed ħaġa fi żmien. 1047 00:39:10,190 --> 00:39:12,465 I ma tistax issolvi ta jittieħed pass lura bħal bniedem u jgħidu, 1048 00:39:12,465 --> 00:39:14,030 ooh, dan jistenna korretta. 1049 00:39:14,030 --> 00:39:17,580 >> I tista 'biss tiddeċiedi korrettezza fl sort għażla billi tagħżel il- 1050 00:39:17,580 --> 00:39:18,370 iżgħar numru. 1051 00:39:18,370 --> 00:39:21,390 Iżda anke jekk nsib numru wieħed ewwel, jekk jien ma nafx xi ħaġa oħra dwar 1052 00:39:21,390 --> 00:39:24,460 n-numri l-oħra, li jien ma, I kollha jafu li stajt ġiet mogħtija array 1053 00:39:24,460 --> 00:39:27,930 jew sett ta 'bibien wara li huma numri, l-uniku mod Naf li wieħed 1054 00:39:27,930 --> 00:39:28,680 kien l-iżgħar? 1055 00:39:28,680 --> 00:39:32,440 Jekk niġi-triq kollha hawn u jirrealizzaw, kkritikat, wieħed kien tabilħaqq l-iżgħar. 1056 00:39:32,440 --> 00:39:34,870 >> Imma kif nista mbagħad tiddetermina li tnejn huwa l-iżgħar li jmiss? 1057 00:39:34,870 --> 00:39:38,350 Billi tagħmel l-istess ineffiċjenza ġdid u għal darb'oħra. 1058 00:39:38,350 --> 00:39:42,210 Allura finalment, ma sort inserzjoni, kif, fl-agħar każ, 1059 00:39:42,210 --> 00:39:44,990 ma ngħidu li jwettaq? 1060 00:39:44,990 --> 00:39:49,100 Huwa wisq huwa n kwadru. 1061 00:39:49,100 --> 00:39:53,020 U kif madwar bl-aħjar każ? 1062 00:39:53,020 --> 00:39:56,282 Aħna ser tħalli li bħala cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Aħna ser timla dak iż-żmien li jmiss vojta, imma l-ewwel let me tipproponi li aħna 1064 00:40:00,090 --> 00:40:02,620 fundamentalment do aħjar minn kollha ta 'dawn, id-dritt? 1065 00:40:02,620 --> 00:40:05,220 >> Allura taħseb għalik innifsek dak inserzjoni sort għaddej biex tkun. 1066 00:40:05,220 --> 00:40:06,910 Ukoll, li ma kienx drammatiku ħafna, għaliex jien l-unika waħda 1067 00:40:06,910 --> 00:40:08,970 li raw il-bidla. 1068 00:40:08,970 --> 00:40:09,620 Ara naqra. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Allura hawnhekk għandna kemmxejn dimostrazzjoni differenti. 1071 00:40:12,615 --> 00:40:16,580 Jekk I zoom fil hawn, tkun taf tara li fuq ix-xellug għandna sort bużżieqa, fil- 1072 00:40:16,580 --> 00:40:20,740 nofs għandna sort għażla, u fuq -lemin, għandna xi ħaġa li aħna 1073 00:40:20,740 --> 00:40:23,380 ma jkunux ħarsu lejn għadhom imsejħa jingħaqdu tip. 1074 00:40:23,380 --> 00:40:26,080 Iżda jikkunsidraw dak li aħna kont qed tagħmel hawn s'issa illum. 1075 00:40:26,080 --> 00:40:29,200 Meta Jennifer ewwel daħal up fuq il-palk, aħna marru permezz tal-firxa ta 'numri 1076 00:40:29,200 --> 00:40:33,750 għal darb'oħra, u għal darb'oħra, bil-tfittxija lineari, u aħna ltqajna running time lineari, big O 1077 00:40:33,750 --> 00:40:35,100 ta 'n, biex ngħidu hekk. 1078 00:40:35,100 --> 00:40:41,000 >> Meta aħna issa tikkunsidra l-ewwel ġimgħa ta ' klassi, meta kellna jaqsam u jirbħu, 1079 00:40:41,000 --> 00:40:43,740 u kellna l-ktieb tat-telefon dmugħ, u Jennifer, u aħna kollettivament 1080 00:40:43,740 --> 00:40:47,500 leveraged li ħarsa ewlenin, li kellha jirrepetu yourself darb'oħra u għal darb'oħra mill 1081 00:40:47,500 --> 00:40:50,930 b'xi tarmi, jitfg bogħod, tarmi, nofs il-problema, jew 1082 00:40:50,930 --> 00:40:55,320 ġeneralment, jiġi diviż problema fil nofs, u mbagħad wieħed jittratta l-biċċa iżgħar ta ' 1083 00:40:55,320 --> 00:40:59,630 il-problema bħala kunċettwalment ekwivalenti għall-ieħor, aħna b'xi mod ma 1084 00:40:59,630 --> 00:41:00,910 fundamentalment aħjar. 1085 00:41:00,910 --> 00:41:04,720 Iżda ma sort bużżieqa, bl-għażla sort, ma sort inserzjoni, konna jista 1086 00:41:04,720 --> 00:41:06,560 ebda għarfien bħal dak Jennifer għamlet. 1087 00:41:06,560 --> 00:41:10,220 Aħna pretty ħafna biss mixi lura u raba mazz sħiħ ta 'drabi, u aħna 1088 00:41:10,220 --> 00:41:12,650 affarijiet tweaked ftit, jagħmlu skambju ta ' f'din l-ordni, forsi 1089 00:41:12,650 --> 00:41:13,730 jinserixxi jew għażla. 1090 00:41:13,730 --> 00:41:16,950 Iżda fl-aħħar tal-ġurnata, Jien għamilt ħafna ta 'mixi skomdi u lura. 1091 00:41:16,950 --> 00:41:21,160 Aħna ma verament lieva xi ħaġa smart bħal Jennifer ma tixtieq tiddividi 1092 00:41:21,160 --> 00:41:22,040 u conquering. 1093 00:41:22,040 --> 00:41:25,620 >> Allura jingħaqdu sort, b'kuntrast, li aħna mhux se tara sal-ġimgħa d-dieħla, li għaddej 1094 00:41:25,620 --> 00:41:29,540 biex ingranaġġ li idea ewlenija billi tiddividi l-input, u mbagħad tnaqqis bin-nofs, u mbagħad 1095 00:41:29,540 --> 00:41:30,580 tnaqqis bin-nofs, u mbagħad tnaqqis bin-nofs. 1096 00:41:30,580 --> 00:41:34,590 U fuq kull iterazzjoni ta 'dak loop, issortjar in-nofs xellugi, u d-dritt 1097 00:41:34,590 --> 00:41:38,200 nofs, allura l-nofs tax-xellug ta 'nofs tax-xellug, u l-nofs tal-lemin ta 'fuq ix-xellug, imbagħad 1098 00:41:38,200 --> 00:41:40,990 in-nofs xellugi tal-nofs tal-lemin, u il-nofs tal-lemin ta 'l-nofs tal-lemin. 1099 00:41:40,990 --> 00:41:42,840 U jirrepeti ġdid u għal darb'oħra. 1100 00:41:42,840 --> 00:41:46,170 >> Sabiex tkun taf tara dan viżwalment, iżda dan huwa dak li jistenna minna ġimgħa d-dieħla. 1101 00:41:46,170 --> 00:41:49,760 U b'mod ġenerali, meta naħsbu ftit daqsxejn aktar diffiċli fuq kull problema simili. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Aħna n-kwadrat fuq ix-xellug n kwadrat fin-nofs, u n 1104 00:41:57,970 --> 00:41:59,400 log n fuq il-lemin. 1105 00:41:59,400 --> 00:42:00,590 Allura hemm cliffhanger reali tiegħek. 1106 00:42:00,590 --> 00:42:02,040 Aħna ser tara inti nhar it-Tnejn. 1107 00:42:02,040 --> 00:42:05,163 >> [Applause]