1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Daqq tal-mużika] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. Malan: Dan huwa CS50. 5 00:00:12,550 --> 00:00:14,612 U dan huwa l-bidu ta 'tliet ġimgħat. 6 00:00:14,612 --> 00:00:16,820 Allura konna ltqajna ħafna ta 'eċċitanti affarijiet li tkopri llum. 7 00:00:16,820 --> 00:00:20,160 A lott ta 'opportunitajiet għall- voluntiera up fuq il-palk. 8 00:00:20,160 --> 00:00:22,780 U finalment, illum huwa mhux dwar kodiċi livelli kollha. 9 00:00:22,780 --> 00:00:24,820 Iżda huwa dwar l-ideat, u huwa dwar algoritmi, 10 00:00:24,820 --> 00:00:28,420 u fil-fatt tressaq lura uħud mill l-lezzjonijiet mitgħallma minn żero ġimgħa, 11 00:00:28,420 --> 00:00:31,910 fejn recall, aħna introduċew din monstrosity. 12 00:00:31,910 --> 00:00:33,880 U l-ispirazzjoni self minn dan, biex tibda 13 00:00:33,880 --> 00:00:36,879 biex isolvu dejjem aktar sofistikata problemi algorithmically. 14 00:00:36,879 --> 00:00:38,420 Iżda l-ewwel, ftit avviżi. 15 00:00:38,420 --> 00:00:42,020 Allura wieħed, jekk inti tixtieq li jissieħbu Persunal CS50 u klassi waqt l-ikla 16 00:00:42,020 --> 00:00:44,670 dan il-ġimgħa, kemm hawn u fl Cambridge, u fi New Haven, 17 00:00:44,670 --> 00:00:48,060 jekk jogħġbok żur il-kors tal website, fejn URL tista 'tinstab. 18 00:00:48,060 --> 00:00:50,390 Lecture dan l-erbgħa se Ma jkun hawn fil Sanders. 19 00:00:50,390 --> 00:00:53,610 Dan se jkun online biss, hekk tixgħel fil-website CS50, l 20 00:00:53,610 --> 00:00:55,850 jekk hawn fil Cambridge jew New Haven ukoll. 21 00:00:55,850 --> 00:00:58,110 >> U mbagħad problema stabbiliti żewġ hija diġà fil-idejk. 22 00:00:58,110 --> 00:01:03,067 Jekk int ma dived fil għadhom, ippermettuli li joffru l-suġġeriment miktuba bil-qawwa 23 00:01:03,067 --> 00:01:05,150 li, speċjalment issa, kif il-problema settijiet bil-quddiem, 24 00:01:05,150 --> 00:01:08,669 int verament tixtieq li tibda issa, jekk mhux dabble ftit fuq il-weekend jew qabel 25 00:01:08,669 --> 00:01:10,710 meta l-ewwel jmorru fuq Ġimgħa, għaliex inti ser 26 00:01:10,710 --> 00:01:14,380 issib li dawn mhux qed neċessarjament jitwal jew aktar ta 'sfida għal kull 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Naħseb li inti ser issib li, fi ġenerali, dawn għandhom tendenza li jieħdu bejn wieħed u ieħor 29 00:01:17,575 --> 00:01:18,892 madwar istess ammont ta 'ħin. 30 00:01:18,892 --> 00:01:20,850 Iżda ċertament jiddependi fuq l-istudent, u 31 00:01:20,850 --> 00:01:22,880 jiddependi fuq il-mentalità li magħhom inti approċċ dan. 32 00:01:22,880 --> 00:01:24,910 Iżda dejjem, int ser biex tiltaqa 'ma' xi ħajt, 33 00:01:24,910 --> 00:01:26,350 u int ser jintlaqtu xi bug, u int biss 34 00:01:26,350 --> 00:01:27,950 mhux se tkun kapaċi li nikseb fuqha f'xi punt. 35 00:01:27,950 --> 00:01:31,380 U huwa immensament importanti li tkun tista li pass bogħod, jiġu lura l-għada, 36 00:01:31,380 --> 00:01:35,286 mur ħinijiet tal-uffiċċju, post fuq CS50 Iddiskuti jew bħalhom, li fil-fatt tikseb mblukkata. 37 00:01:35,286 --> 00:01:36,160 Sabiex iżommu dan f'moħħhom. 38 00:01:36,160 --> 00:01:40,830 Bidu kmieni kemm jista 'jkun huwa l-aqwa ħaġa li tista 'tagħmel. 39 00:01:40,830 --> 00:01:44,160 Allura hawnhekk fejn bdejna il-klassi, fuq żero ġimgħa. 40 00:01:44,160 --> 00:01:47,441 U nistgħu jiksbu voluntier hawn biex għinni issib MICs? 41 00:01:47,441 --> 00:01:47,940 KOLLOX SEW. 42 00:01:47,940 --> 00:01:48,900 Wieqfa diġà. 43 00:01:48,900 --> 00:01:50,080 Come fuq up. 44 00:01:50,080 --> 00:01:53,707 Raden li l-mod kif huwa sejjer jaħdem. 45 00:01:53,707 --> 00:01:54,415 X'hemm isem tiegħek? 46 00:01:54,415 --> 00:01:55,570 ALAN Estrada: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 DAVID J. Malan: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Come fuq up. 49 00:01:57,910 --> 00:01:58,619 Għandi pjaċir. 50 00:01:58,619 --> 00:01:59,910 ALAN Estrada: Nizza biex jissodisfaw inti. 51 00:01:59,910 --> 00:02:02,772 DAVID J. Malan: U inti kienu hawn magħna żero ġimgħa, tal-kors. 52 00:02:02,772 --> 00:02:03,028 ALAN Estrada: I kien. 53 00:02:03,028 --> 00:02:03,160 I kien. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. Malan: Allura tista tmur quddiem u jsibu għalina Mike Smith, 55 00:02:05,868 --> 00:02:08,639 kif malajr kemm tista '? 56 00:02:08,639 --> 00:02:10,639 Malajr kemm tista '. 57 00:02:10,639 --> 00:02:13,756 Litteralment dmugħ l-problema fil nofs kif għandek bżonn biex. 58 00:02:13,756 --> 00:02:15,130 >> ALAN Estrada: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. Malan: Litteralment dmugħ l-problema min-nofs. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN Estrada: Oh. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Tajjeb ħafna. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. Malan: OK. 65 00:02:23,700 --> 00:02:24,200 Tajba. 66 00:02:24,200 --> 00:02:24,701 Grazzi. 67 00:02:24,701 --> 00:02:25,700 ALAN Estrada: Tajjeb ħafna. 68 00:02:25,700 --> 00:02:26,210 KOLLOX SEW. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. Malan: U għalhekk issa, inti stajt fadal l-isfel 70 00:02:27,610 --> 00:02:29,320 għal nofs id-daqs tal-problema. 71 00:02:29,320 --> 00:02:31,267 Issa, aħna qed isfel sa kwart. 72 00:02:31,267 --> 00:02:33,475 Inti tingħata attenzjoni lill liema naħa aħna qed iżżomm? 73 00:02:33,475 --> 00:02:34,405 >> [Laughing] 74 00:02:34,405 --> 00:02:35,970 >> ALAN Estrada: Iva, I think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. Malan: Liema taqsima aħna fil-? 76 00:02:37,594 --> 00:02:39,150 ALAN Estrada: mleffi, so. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. Malan: OK. 78 00:02:39,941 --> 00:02:42,810 Iżda Mike Smith huwa għaddej li jkun wara mleffi. 79 00:02:42,810 --> 00:02:44,130 So-- 80 00:02:44,130 --> 00:02:48,180 >> [Laughing] 81 00:02:48,180 --> 00:02:48,742 >> Kull dritt. 82 00:02:48,742 --> 00:02:50,200 ALAN Estrada: Fejn ninsabu tfittex? 83 00:02:50,200 --> 00:02:52,049 DAVID J. Malan: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN Estrada: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 DAVID J. Malan: Issa, aħna qed fil kirurġika. 86 00:02:54,760 --> 00:02:57,840 Issa, it-tobba. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN Estrada: Let's- ejja jmorru ma reali. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. Malan: Real. 91 00:03:00,970 --> 00:03:01,470 KOLLOX SEW. 92 00:03:01,470 --> 00:03:03,700 Jekk għandek bżonn Real. 93 00:03:03,700 --> 00:03:05,250 Issa, li mod huwa Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN Estrada: Dan il-mod. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. Malan: Liema mod? 96 00:03:07,333 --> 00:03:08,240 ALAN Estrada: Stenna. 97 00:03:08,240 --> 00:03:08,790 Dritt M is--? 98 00:03:08,790 --> 00:03:09,110 Bdejna with-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. Malan: Yeah. 100 00:03:10,090 --> 00:03:10,650 Huma qed xellug. 101 00:03:10,650 --> 00:03:11,430 Id-dritt tiegħek. 102 00:03:11,430 --> 00:03:11,710 >> ALAN Estrada: Yeah. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. Malan: hekk Mike fil hawn. 104 00:03:13,126 --> 00:03:13,990 ALAN Estrada: What? 105 00:03:13,990 --> 00:03:14,665 >> [Laughing] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Bad eżempju, guys. 108 00:03:18,330 --> 00:03:18,830 Jiddispjacini. 109 00:03:18,830 --> 00:03:21,610 DAVID J. Malan: Dan se jgħallmu inti qabża ta 'siġġu tiegħek. 110 00:03:21,610 --> 00:03:22,318 >> ALAN Estrada: Oh. 111 00:03:22,318 --> 00:03:22,890 Oh. 112 00:03:22,890 --> 00:03:23,390 Qbadtek. 113 00:03:23,390 --> 00:03:24,670 Qbadtek. 114 00:03:24,670 --> 00:03:25,170 Oh. 115 00:03:25,170 --> 00:03:25,669 Oh. 116 00:03:25,669 --> 00:03:26,812 Dan is-- OK, I ltqajna inti. 117 00:03:26,812 --> 00:03:27,520 Smith dritt hawn? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. Malan: Smith, grazie. 119 00:03:28,894 --> 00:03:30,535 So I ser iżommu tfittex up Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN Estrada: Oh, yeah. 121 00:03:30,790 --> 00:03:31,340 No, no, no. 122 00:03:31,340 --> 00:03:31,600 Oh, no. 123 00:03:31,600 --> 00:03:31,940 Dan huwa minjiera. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. Malan: Oh, inti ltqajna Smith. 125 00:03:32,580 --> 00:03:33,415 KOLLOX SEW. 126 00:03:33,415 --> 00:03:34,040 >> ALAN Estrada: Yeah, I ltqajna Smith dritt hawn. 127 00:03:34,040 --> 00:03:34,700 Jiddispjacini, guys. 128 00:03:34,700 --> 00:03:35,860 Ħsibt Michael-- we kienu qed ifittxu Michael. 129 00:03:35,860 --> 00:03:36,550 Jiddispjacini. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. Malan: Huwa OK. 131 00:03:37,550 --> 00:03:39,950 Kull dritt, issa aħna qed fis Paccini and Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN Estrada: Paccini u wliedu. 133 00:03:41,242 --> 00:03:43,158 DAVID J. Malan: inti biss u I huma dwar dan. 134 00:03:43,158 --> 00:03:44,050 KOLLOX SEW. 135 00:03:44,050 --> 00:03:45,130 Sib magħna Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Smith. 137 00:03:45,830 --> 00:03:46,310 >> ALAN Estrada: Smith. 138 00:03:46,310 --> 00:03:46,750 >> DAVID J. Malan: Smith. 139 00:03:46,750 --> 00:03:47,728 Aħna fl-R għal żibel. 140 00:03:47,728 --> 00:03:48,644 ALAN Estrada: Żibel. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Dan se jieħu waqt. 143 00:03:52,480 --> 00:03:54,340 >> [Laughing] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. Malan: Shoes. 146 00:03:56,720 --> 00:03:58,080 Aħna fil-żraben. 147 00:03:58,080 --> 00:04:00,210 >> ALAN Estrada: Issa aħna qed gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. Malan: Nizza. 149 00:04:01,105 --> 00:04:01,980 ALAN Estrada: Which-- 150 00:04:01,980 --> 00:04:03,620 [Laughing] 151 00:04:03,620 --> 00:04:05,440 Oh, dan huwa kbir. 152 00:04:05,440 --> 00:04:06,910 [Laughing] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. Malan: Huwa OK. 155 00:04:09,390 --> 00:04:11,365 >> ALAN Estrada: Oh, dan huwa tajjeb. 156 00:04:11,365 --> 00:04:14,425 Ma naħsibx li jien ser jkollhom buddies PSAT wara dan. 157 00:04:14,425 --> 00:04:15,300 DAVID J. Malan: Tajba. 158 00:04:15,300 --> 00:04:16,078 Sporting. 159 00:04:16,078 --> 00:04:17,036 ALAN Estrada: Sporting. 160 00:04:17,036 --> 00:04:18,668 Um, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 DAVID J. Malan: OK. 162 00:04:19,459 --> 00:04:21,600 Mela ejja tiċrita dan min-nofs. 163 00:04:21,600 --> 00:04:22,270 Orrajt. 164 00:04:22,270 --> 00:04:25,606 Dan jispiċċa ħażin xorta waħda, minħabba Mike Smith mhux se jkun fil-yellow pages. 165 00:04:25,606 --> 00:04:26,430 >> ALAN Estrada: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. Malan: Le, huwa OK. 167 00:04:27,140 --> 00:04:28,930 Imma ejja nippretendu simili hu f'din il-paġna. 168 00:04:28,930 --> 00:04:33,260 Allura issa, inti ħadthom fadal il-problema isfel għall-paġna waħda, u sibna Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Cheering] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 OK, nirringrazzjak. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 KOLLOX SEW. 174 00:04:41,200 --> 00:04:43,646 Dan kien straordinarja. 175 00:04:43,646 --> 00:04:45,954 Imma kien għadu aktar mgħaġġel minn tfittxija lineari, 176 00:04:45,954 --> 00:04:47,870 fejn nibdew fl- bidu tal-ktieb, 177 00:04:47,870 --> 00:04:51,210 u nimxu mod tagħna mix-xellug għal-lemin, eventwalment tfittex Mike Smith. 178 00:04:51,210 --> 00:04:53,540 U hekk, jekk il-ktieb tat-telefon kellhom forsi 1,000 paġni, 179 00:04:53,540 --> 00:04:56,300 forsi kien jieħu us 10 jew hekk tiċrit paġna. 180 00:04:56,300 --> 00:04:59,380 >> Iżda int tista għenu mimsus assunzjoni 181 00:04:59,380 --> 00:05:03,602 matul kollha ta 'dak, li jiġifieri li l-ktieb tat-telefon bil-quddiem kien dak? 182 00:05:03,602 --> 00:05:04,310 UDJENZA: Magħżula. 183 00:05:04,310 --> 00:05:05,000 DAVID J. Malan: Huwa magħżula. 184 00:05:05,000 --> 00:05:05,160 Dritt? 185 00:05:05,160 --> 00:05:07,909 Huwa magħżula alfabetikament, hekk li kollha ta 'dawk l-ismijiet u numri 186 00:05:07,909 --> 00:05:11,230 huma magħżula mill-l A għall- Z, u alfabetikament bejniethom. 187 00:05:11,230 --> 00:05:13,100 Imma llum, aħna issa staqsi il-kwistjoni, ukoll, 188 00:05:13,100 --> 00:05:16,170 kif Verizon sar jew it-telefon kumpanija ġġibu fis-istat? 189 00:05:16,170 --> 00:05:19,560 >> Għaliex dan huwa ħaġa waħda li jwieżen din il-preżunzjoni, u għalhekk, 190 00:05:19,560 --> 00:05:22,570 issolvi problema ma ' algoritmu b'mod aktar effiċjenti. 191 00:05:22,570 --> 00:05:24,900 Imma aħna qatt verament talab żero ġimgħa, ukoll, 192 00:05:24,900 --> 00:05:27,790 kemm ma jiswa Verizon jew xi ħadd ieħor 193 00:05:27,790 --> 00:05:29,620 li tikseb dak il-ktieb tat-telefon sabiex Issortjat? 194 00:05:29,620 --> 00:05:29,780 >> Dritt? 195 00:05:29,780 --> 00:05:31,529 Ma jimpurtax jekk tfittex up Mike Smith 196 00:05:31,529 --> 00:05:35,190 huwa super fast, jekk din tieħdok a sena biex issolvi l-paġni fil-bidu. 197 00:05:35,190 --> 00:05:35,690 Dritt? 198 00:05:35,690 --> 00:05:38,620 Inti tista 'ukoll biss ffiltrati permezz ta 'ktieb tat-telefon randomised, 199 00:05:38,620 --> 00:05:40,690 jekk li għaddej biex tkun super għaljin biex sort. 200 00:05:40,690 --> 00:05:42,350 Mela jekk jista 'jkollna voluntier ieħor. 201 00:05:42,350 --> 00:05:46,350 Ejja tagħti ħarsa up hawn fuq kif aħna might-- jaqgħu fuq up-- kif 202 00:05:46,350 --> 00:05:48,100 nistgħu tmur dwar għażla dawn. 203 00:05:48,100 --> 00:05:51,990 >> U jekk Ġordan jistgħu attwalment jingħaqdu magħna up here fuq il-palk. 204 00:05:51,990 --> 00:05:55,100 Come fuq up għal ftit mument. 205 00:05:55,100 --> 00:05:56,359 X'hemm isem tiegħek? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. Malan: Caroline, jaqgħu fuq up. 208 00:05:58,691 --> 00:06:02,070 U tkun taf tkun magħquda minni u l-Ġordan hawn. 209 00:06:02,070 --> 00:06:03,800 Caroline, nirringrazzjak. 210 00:06:03,800 --> 00:06:04,300 Kull dritt. 211 00:06:04,300 --> 00:06:08,330 Allura dak li għandna hawnhekk għal Caroline huwa 26 kotba blu 212 00:06:08,330 --> 00:06:10,747 li FAS juża biex jamministraw ċerti eżamijiet finali. 213 00:06:10,747 --> 00:06:13,330 Dawn huma jkollna diffiċli li ssib, imma dak li aħna ghamilt bil-quddiem 214 00:06:13,330 --> 00:06:15,800 hija li konna tpoġġi l-isem ta 'xi ħadd fuq quddiem ta 'kull wieħed minn dawn, 215 00:06:15,800 --> 00:06:18,133 imma konna żammha sempliċi mill imbagħad tqegħid barra ismijiet sħaħ. 216 00:06:18,133 --> 00:06:22,720 Allura aħna se tpoġġi l-persuna bl-isem L, D, J, B, it-triq A sa Z, 217 00:06:22,720 --> 00:06:24,090 iżda dawn qed sabiex każwali. 218 00:06:24,090 --> 00:06:26,890 U hekk jekk inti, jitkellem tiegħek mod permezz tal-problema kif inti 219 00:06:26,890 --> 00:06:31,620 tagħmel dan, inti tista 'tmur quddiem u sort dawn għalina, minn A sa Z. 220 00:06:31,620 --> 00:06:34,070 >> UDJENZA: OK, so L huwa simili,-nofs. 221 00:06:34,070 --> 00:06:35,050 C qed jibda. 222 00:06:35,050 --> 00:06:42,410 B. J qabel L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. Malan: Żomm li maħsub għat-tieni waħda. 224 00:06:45,140 --> 00:06:48,910 Minħabba xort'oħra, dan huwa biss interessanti għalik, lili, u l-Ġordan. 225 00:06:48,910 --> 00:06:49,724 Hemm immorru. 226 00:06:49,724 --> 00:06:50,640 UDJENZA: [inaudible]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. Malan: OK. 229 00:06:58,090 --> 00:06:59,310 X'Ser tagħmel? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M jiġi wara O. 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. Malan: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. Malan: O, Good. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> DAVID J. Malan: E, F. Yeah. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V. 237 00:07:07,620 --> 00:07:10,689 >> DAVID J. Malan: V, T, U, V. Għalhekk qisu int making-- jibqgħu għaddejjin. 238 00:07:10,689 --> 00:07:12,730 Jidher qisu int tagħmel munzell kbir hawn, 239 00:07:12,730 --> 00:07:13,910 u tip ta 'munzell kbir hemmhekk. 240 00:07:13,910 --> 00:07:16,230 Allura l-ewwel nofs tas-alfabett, tieni nofs tas-alfabett. 241 00:07:16,230 --> 00:07:16,460 KOLLOX SEW. 242 00:07:16,460 --> 00:07:16,960 Tajba. 243 00:07:16,960 --> 00:07:19,680 Tip ta 'qsim il-problema fi tnejn. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Yeah. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. Malan: OK. 247 00:07:22,980 --> 00:07:25,070 K. Allura int it-tip ta 'għażla minnhom wara xulxin, 248 00:07:25,070 --> 00:07:27,620 tqegħid jew tax-xellug jew il-lemin, jew tal Z għaddej fuq l-art. 249 00:07:27,620 --> 00:07:28,012 KOLLOX SEW. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z għaddej fuq l-art. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. Malan: OK. 252 00:07:29,360 --> 00:07:30,920 Y huwa għaddej fuq l-art. 253 00:07:30,920 --> 00:07:31,735 Issa nistgħu npoġġu X. 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 DAVID J. Malan: l G għaddejjin xellug. 256 00:07:33,700 --> 00:07:36,017 S huwa għaddej dritt. 257 00:07:36,017 --> 00:07:37,642 Kull dritt, A huwa għaddej it-triq kollha xellug. 258 00:07:37,642 --> 00:07:38,790 >> CAROLINE: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> DAVID J. Malan: Issa, tajba. 260 00:07:39,873 --> 00:07:43,260 Imxejna ltqajna A, B, Ċ W għaddej stabbiliti hemmhekk. 261 00:07:43,260 --> 00:07:45,566 Dritt kollox, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, J. 263 00:07:46,611 --> 00:07:47,860 DAVID J. Malan: H, I, J. Tajba. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: Fiċ-ċentru, jien gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. Malan: OK. 266 00:07:50,000 --> 00:07:52,375 Allura issa, aħna qed tmur biex tip ta 'jingħaqdu dawn piles varji. 267 00:07:52,375 --> 00:08:00,730 Allura A sa C, imbagħad nara D, u E, u F, u G, u H, u I. Nizza. 268 00:08:00,730 --> 00:08:05,540 J, K. U mbagħad, dan pile huwa rasu 'l isfel, iżda li OK. 269 00:08:05,540 --> 00:08:06,040 Sure. 270 00:08:06,040 --> 00:08:07,240 Aħna tista 'tnaqqas xi kantunieri. 271 00:08:07,240 --> 00:08:07,950 KOLLOX SEW. 272 00:08:07,950 --> 00:08:10,530 U allura għandna bżonn W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Yeah. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. Malan: Eċċellenti. 275 00:08:11,880 --> 00:08:14,122 Allura big gracias għal Caroline għall-għażla dawn. 276 00:08:14,122 --> 00:08:15,030 >> [Cheering] 277 00:08:15,030 --> 00:08:17,287 >> Grazzi. 278 00:08:17,287 --> 00:08:18,120 Grazzi ħafna. 279 00:08:18,120 --> 00:08:22,910 Allura issa ejja jikkunsidraw għal mument kif Caroline marru dwar kif isir dan, 280 00:08:22,910 --> 00:08:26,040 u dak eżattament aħna kienu kapaċi to-- kif aħna 281 00:08:26,040 --> 00:08:28,409 kienu kapaċi ssolvi din meta problema konna biss 282 00:08:28,409 --> 00:08:29,950 mogħti mazz sħiħ ta 'inputs każwali. 283 00:08:29,950 --> 00:08:31,610 >> Ukoll, jidher qisu hemm kien daqsxejn ta 'sistema hemmhekk? 284 00:08:31,610 --> 00:08:32,110 Dritt. 285 00:08:32,110 --> 00:08:34,495 Allura l-ittri preċedenti fl-alfabett, hi 286 00:08:34,495 --> 00:08:37,120 kien tqegħid lejn ix-xellug, u l- ittri aktar tard fil-alfabett, 287 00:08:37,120 --> 00:08:38,270 hi kien tqegħid fis-lemin. 288 00:08:38,270 --> 00:08:40,500 U hekk kif hija sabet xi ittri prossimali, dawk 289 00:08:40,500 --> 00:08:43,124 li jmorru dritt ħdejn xulxin, hi tqiegħed dawn fl-ordni. 290 00:08:43,124 --> 00:08:46,750 U hekk aħna tip ta 'kellhom dawn żgħir munzelli ta 'inputs magħżula jseħħu. 291 00:08:46,750 --> 00:08:50,540 >> U hekk dan huwa pjuttost bħal dak Ħafna minna bnedmin ser jagħmlu. 292 00:08:50,540 --> 00:08:53,530 Nixtiequ tip ta ffiltrati permezz tagħha, u aħna'd tip ta jkollhom mekkaniżmu. 293 00:08:53,530 --> 00:08:56,930 Iżda jista 'jkun diffiċli li tikteb l-isfel fil-formula per se. 294 00:08:56,930 --> 00:08:59,010 Huwa ħass ftit aktar organiku minn dak. 295 00:08:59,010 --> 00:09:02,560 Mela ejja ara jekk nistgħu issa marbut il-problema b'inqas inputs. 296 00:09:02,560 --> 00:09:05,170 >> Minflok ta '26, ejja jagħmel xi ħaġa ferm inqas 297 00:09:05,170 --> 00:09:09,890 ma biss jgħidu, seba ', wara dawn il-bibien, biex ngħidu hekk. 298 00:09:09,890 --> 00:09:11,300 Hemm biss seba 'numri? 299 00:09:11,300 --> 00:09:15,240 U jekk l-għan issa fil idejn huwa li tinstab valur, 300 00:09:15,240 --> 00:09:17,850 ejja ara kif effiċjenti nistgħu tmur dwar kif isir dan. 301 00:09:17,850 --> 00:09:22,460 U ejja ara jekk nistgħu issa jibdew japplikaw xi numri, 302 00:09:22,460 --> 00:09:26,310 jew xi formuli li biex jiddeskrivu l-effiċjenza tal-ktieb tat-telefon tagħna 303 00:09:26,310 --> 00:09:31,060 algoritmu, tagħna algoritmu ktieb eżami, u b'mod aktar ġenerali, il-konstatazzjoni informazzjoni. 304 00:09:31,060 --> 00:09:34,770 >> Allura għal dan, let me imorru quddiem u fuq il-touch screen hawn fuq, 305 00:09:34,770 --> 00:09:41,100 imqiegħed web browser li għandha eżattament dawn is-seba bibien. 306 00:09:41,100 --> 00:09:46,670 U jekk nistgħu jiksbu ieħor voluntier biex jitla fuq minn hawn, 307 00:09:46,670 --> 00:09:48,480 Stajt jitqiegħdu dawn l-istess bibien hawn. 308 00:09:48,480 --> 00:09:49,170 Quick voluntier. 309 00:09:49,170 --> 00:09:51,130 >> Dan demos one-- tmur għal aktar malajr u aktar malajr issa. 310 00:09:51,130 --> 00:09:51,600 Come fuq l isfel. 311 00:09:51,600 --> 00:09:52,308 X'hemm isem tiegħek? 312 00:09:52,308 --> 00:09:53,040 Trevor: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> DAVID J. Malan: Trevor? 314 00:09:53,998 --> 00:09:55,770 Kull dritt, Trevor, jaqgħu fuq l isfel. 315 00:09:55,770 --> 00:09:59,212 Allura Trevor offriet hawn biex do problema simili, iżda wieħed li 316 00:09:59,212 --> 00:10:02,170 ambitu iktar ristrett, u li għaddej li inessu jipprova jifformalizzaw issa 317 00:10:02,170 --> 00:10:03,970 il-proċess għall-għażla dawn in-numri. 318 00:10:03,970 --> 00:10:05,500 >> Allura Trevor, sbieħ li jissodisfaw inti. 319 00:10:05,500 --> 00:10:08,720 Allura hawnhekk huwa firxa, biex jitkellmu, lista ta 'seba' bibien. 320 00:10:08,720 --> 00:10:10,327 Jimxi 'l quddiem u issibna-numru 50. 321 00:10:10,327 --> 00:10:12,410 U mbagħad wara l-fatt, jgħidulna kif inti sabuha. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Jekk be-- id-dritt. 324 00:10:20,040 --> 00:10:21,945 Yeah, dan huwa l-waħda hawn? 325 00:10:21,945 --> 00:10:24,680 Uh-oh. 326 00:10:24,680 --> 00:10:25,560 KOLLOX SEW. 327 00:10:25,560 --> 00:10:26,680 Inti għafast li wieħed. 328 00:10:26,680 --> 00:10:28,690 Tajba. 329 00:10:28,690 --> 00:10:29,780 >> U tajjeb. 330 00:10:29,780 --> 00:10:30,970 Issa inti għafast li wieħed. 331 00:10:30,970 --> 00:10:34,060 U let me jagħtuk l-mikrofonu, sabiex ikollok fi ftit mument. 332 00:10:34,060 --> 00:10:37,000 Jimxi 'l quddiem u kklikkja l- bieb li jmiss li għandek il-ħsieb. 333 00:10:37,000 --> 00:10:39,812 Iva, tajjeb. 334 00:10:39,812 --> 00:10:41,020 Trevor: Nista unclick bieb? 335 00:10:41,020 --> 00:10:42,620 DAVID J. Malan: Le, inti ma tistax unclick. 336 00:10:42,620 --> 00:10:43,119 Trevor: OK. 337 00:10:43,119 --> 00:10:43,974 Dan wieħed. 338 00:10:43,974 --> 00:10:45,640 DAVID J. Malan: Meta inti tixtieq li tmur? 339 00:10:45,640 --> 00:10:46,410 Liema? 340 00:10:46,410 --> 00:10:47,230 >> Trevor: Li wieħed. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. Malan: Le 342 00:10:48,042 --> 00:10:48,450 >> Trevor: OK. 343 00:10:48,450 --> 00:10:48,735 Dan wieħed. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. Malan: Iva. 345 00:10:49,020 --> 00:10:49,700 Dan kien tajjeb. 346 00:10:49,700 --> 00:10:50,380 Kull dritt. 347 00:10:50,380 --> 00:10:53,900 Allura dak li kien algoritmu tiegħek jew proċedura biex isir dan, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> Trevor: I biss marru permezz bibien sakemm sibt 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. Malan: OK. 350 00:10:56,940 --> 00:10:58,150 Algoritmu eċċellenti. 351 00:10:58,150 --> 00:10:59,540 Allura li l-multa. 352 00:10:59,540 --> 00:11:03,120 Minħabba fil-fatt, jekk I jiżvelaw x'hemm wara dawn iż-żewġ bibien oħra, dak 353 00:11:03,120 --> 00:11:06,954 aħna ser issib hawnhekk huwa li aħna biss input każwali. 354 00:11:06,954 --> 00:11:08,870 Allura li kien effettivament bħala tajba kif int jista 'jkollok. 355 00:11:08,870 --> 00:11:12,509 U fil-fatt, inti ltqajna aħjar minn b'mod eżawrjenti tfittex l-firxa sħiħa, 356 00:11:12,509 --> 00:11:15,300 għaliex kien ikun verament unlucky jekk inti laqat in-numru 357 00:11:15,300 --> 00:11:16,604 50 fl-aħħar bieb. 358 00:11:16,604 --> 00:11:18,520 Imma dak jekk aħna minflok ħadt suppożizzjoni. 359 00:11:18,520 --> 00:11:20,630 Ejja ngħidu I sort kollha dawn il-bibien madwar, 360 00:11:20,630 --> 00:11:23,500 sabiex ikollok l- numri magħżula din id-darba, 361 00:11:23,500 --> 00:11:29,730 iżda din id-darba huwa attwalment a different-- dan iż-żmien, 362 00:11:29,730 --> 00:11:32,640 huwa attwalment magħżula għalik. 363 00:11:32,640 --> 00:11:35,380 U issa l-għan fil-idejn huwa li tolqot l-għadd 50. 364 00:11:35,380 --> 00:11:36,090 >> Trevor: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. Malan: X'hemm algoritmu tiegħek se tkun? 366 00:11:37,670 --> 00:11:39,628 >> Trevor: Well, jekk huwa magħżula, huwa jew ser 367 00:11:39,628 --> 00:11:42,710 li be-- jekk akbar għall-akbar, dixxendenti, dan ser ikun l-ewwel wieħed, 368 00:11:42,710 --> 00:11:44,751 jew jekk huwa l-oppost, se jkun l-aħħar wieħed. 369 00:11:44,751 --> 00:11:48,897 So I ser biss vit dan il-bieb, u allura biss tisfrutta l-aħħar bieb. 370 00:11:48,897 --> 00:11:49,980 DAVID J. Malan: Eċċellenti. 371 00:11:49,980 --> 00:11:50,270 Kull dritt. 372 00:11:50,270 --> 00:11:51,150 Allura sibna l-għadd 50. 373 00:11:51,150 --> 00:11:52,970 Allura hekk kif inti taf kienu magħżula, aħna 374 00:11:52,970 --> 00:11:55,040 kienu kapaċi li jwieżen din il-preżunzjoni. 375 00:11:55,040 --> 00:11:57,040 Allura jkunu wisq simili l-eżempju ktieb tat-telefon. 376 00:11:57,040 --> 00:11:59,540 Hekk kif ikollok, anke ma problema żgħira bħal dan, 377 00:11:59,540 --> 00:12:02,380 inputs tiegħek magħżula minn qabel, nistgħu attwalment sib il-valur forsi 378 00:12:02,380 --> 00:12:03,130 b'mod aktar effiċjenti. 379 00:12:03,130 --> 00:12:05,800 >> U jien ma jgħidlek jekk kien magħżula żgħar għall-kbar, jew kbar lill-intrapriżi żgħar, 380 00:12:05,800 --> 00:12:08,080 u allura kien raġonevoli ħafna li tibda f'tarf wieħed jew l-oħra 381 00:12:08,080 --> 00:12:09,750 li attwalment issib dak il-valur fil-mira. 382 00:12:09,750 --> 00:12:11,400 Allura nirringrazzja lil Trevor kif ukoll. 383 00:12:11,400 --> 00:12:13,260 U jien ser propose-- nicely jsir. 384 00:12:13,260 --> 00:12:16,960 Għandna clip ftit, fil-fatt, li hija fost mumenti favoriti tagħna fil CS50, 385 00:12:16,960 --> 00:12:19,700 li biha xi kultant dawn demos ma pjuttost tmur skond il-pjan. 386 00:12:19,700 --> 00:12:22,050 U fil-fatt dritt issa, I jinġibed l-interface ħażin 387 00:12:22,050 --> 00:12:23,508 li biex jużaw l-touch screen. 388 00:12:23,508 --> 00:12:24,660 Allura li kien tort tiegħi hemm. 389 00:12:24,660 --> 00:12:26,600 >> Allura dan se tagħmel għal clip sena d-dieħla kif 390 00:12:26,600 --> 00:12:28,570 għaliex I kien tikklikkja fuq l-iskrin tiegħi stess. 391 00:12:28,570 --> 00:12:31,390 Imma ejja tagħti ħarsa lejn dak li ġara aħħar sena 392 00:12:31,390 --> 00:12:34,770 ma Jay, li ħareġ, ħafna bħal Trevor hawn, volontarju, 393 00:12:34,770 --> 00:12:39,380 u f'dan il-clip qasir, tkun taf tara kif din l-istess demo ma pjuttost 394 00:12:39,380 --> 00:12:41,074 jiżvelaw l-istess lezzjonijiet meħuda. 395 00:12:41,074 --> 00:12:41,740 [Daqq video] 396 00:12:41,740 --> 00:12:45,360 -il Nixtieq li tagħmel issa huwa biex isibu għalija, u għalina, 397 00:12:45,360 --> 00:12:51,674 tassew, in-numru 50 pass wieħed fi żmien. 398 00:12:51,674 --> 00:12:52,450 >> -Il Numru 50? 399 00:12:52,450 --> 00:12:53,190 >> -Il Numru 50. 400 00:12:53,190 --> 00:12:55,356 U inti tista 'tikxef x'hemm wara kull waħda minn dawn il-bibien 401 00:12:55,356 --> 00:12:58,540 sempliċiment billi tmiss ma 'saba'. 402 00:12:58,540 --> 00:13:00,910 Kkritikat dan. 403 00:13:00,910 --> 00:13:02,870 >> [Laughing] 404 00:13:02,870 --> 00:13:03,806 >> [END Daqq] 405 00:13:03,806 --> 00:13:05,430 DAVID J. Malan: Allura li marru tajjeb ħafna. 406 00:13:05,430 --> 00:13:06,796 Dawn kienu l-bibien mhux magħżul. 407 00:13:06,796 --> 00:13:08,670 U Jay, naturalment, sabuha wisq malajr. 408 00:13:08,670 --> 00:13:12,910 Trevor għamlet xogħol aħjar f'termini ta 'mument teachable, 409 00:13:12,910 --> 00:13:15,850 biex ngħidu hekk, din is-sena jieħu iktar li jsibuha. 410 00:13:15,850 --> 00:13:17,950 Of course, allura aħna taw Jay opportunità oħra, 411 00:13:17,950 --> 00:13:20,320 li biha aħna magħżula l-bibien, hekk kif għamilna għal Trevor, 412 00:13:20,320 --> 00:13:22,300 u Trevor ma super tajjeb dan iż-żmien. 413 00:13:22,300 --> 00:13:26,124 Iżda Jay ma kien nofs malajr. 414 00:13:26,124 --> 00:13:26,790 [Daqq video] 415 00:13:26,790 --> 00:13:29,650 -Il-Għan issa huwa li wkoll issibna-numru 50, 416 00:13:29,650 --> 00:13:33,030 iżda tagħmel dan algorithmically, u jgħidulna kif int ser dwar dan. 417 00:13:33,030 --> 00:13:33,660 >> -KOLLOX SEW. 418 00:13:33,660 --> 00:13:35,604 >> -u Jekk issibha, inti żżomm il-movie. 419 00:13:35,604 --> 00:13:37,228 Jekk inti ma jsibuha, inti tagħti lura. 420 00:13:37,228 --> 00:13:38,044 >> -Man. 421 00:13:38,044 --> 00:13:38,860 >> -OH! 422 00:13:38,860 --> 00:13:40,800 >> - [Inaudible] OK. 423 00:13:40,800 --> 00:13:46,236 Hekk jien ser jiċċekkja l-truf ewwel biex jiddeterminaw jekk there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Applause] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [END Daqq] 427 00:13:55,729 --> 00:13:56,520 DAVID J. Malan: OK. 428 00:13:56,520 --> 00:13:59,760 Allura issortjar bibien biċ-ċar iwassal għal aktar effiċjenza. 429 00:13:59,760 --> 00:14:01,680 U hekk, darbtejn aktar malajr huwa dak I fisser hemmhekk. 430 00:14:01,680 --> 00:14:03,270 U hekk Jay ltqajna xxurtjati kemm żminijiet. 431 00:14:03,270 --> 00:14:06,685 U hu wkoll ltqajna xxurtjati f'dak aħħar sena, I ordnat xi diski Blu-ray 432 00:14:06,685 --> 00:14:07,560 li attwalment jagħtu. 433 00:14:07,560 --> 00:14:09,768 Jien sorry din is-sena, aħna ma kellhomx l-istess, Trevor. 434 00:14:09,768 --> 00:14:11,540 Iżda aħjar minn hekk kien ftit snin lura. 435 00:14:11,540 --> 00:14:14,820 U xi wħud minnkom tista 'taf dan sħabi, Sean, li meta kien fil CS50, 436 00:14:14,820 --> 00:14:17,780 ġiet ikkontestata bl-eżatt istess problema, għalkemm SD, 437 00:14:17,780 --> 00:14:19,360 kif tkun taf hekk ara, lura fil-ġurnata. 438 00:14:19,360 --> 00:14:22,622 U inti ser issib li mhux biss ma huwa jieħu ftit itwal minn Jay, 439 00:14:22,622 --> 00:14:25,580 ftit itwal milli Trevor, kien fil-fatt din l-opportunità mill-isbaħ 440 00:14:25,580 --> 00:14:29,820 li jidħlu kważi kulħadd fil- folla a la Prezz huwa Dritt, l-inkoraġġiment 441 00:14:29,820 --> 00:14:31,889 lilu biex issib in-numru konna qed ifittxu. 442 00:14:31,889 --> 00:14:32,930 Ejja. tagħti ħarsa. 443 00:14:32,930 --> 00:14:33,320 >> [Daqq video] 444 00:14:33,320 --> 00:14:33,820 >> -KOLLOX SEW. 445 00:14:33,820 --> 00:14:36,680 Allura kompitu tiegħek hawn, Sean, hija din li ġejja. 446 00:14:36,680 --> 00:14:40,860 Għandi moħbija wara dawn bibien in-numru sebgħa. 447 00:14:40,860 --> 00:14:45,120 Iżda tucked bogħod f'xi wħud minn dawn il-bibien kif ukoll huma numri negattivi oħra. 448 00:14:45,120 --> 00:14:47,500 U l-għan tiegħek huwa li wieħed jaħseb ta 'din il-filliera ta' fuq ta 'numri 449 00:14:47,500 --> 00:14:50,390 bħala biss firxa, jew biss sekwenza ta 'biċċiet tal-karti 450 00:14:50,390 --> 00:14:51,510 bin-numri warajhom. 451 00:14:51,510 --> 00:14:55,540 U l-għan tiegħek huwa, biss tuża l-quċċata firxa hawn, issib lili in-numru sebgħa. 452 00:14:55,540 --> 00:14:58,570 U aħna mbagħad se critique kif inti tmur dwar kif isir dan. 453 00:14:58,570 --> 00:14:59,070 -kull Dritt. 454 00:14:59,070 --> 00:15:00,850 -Sib Us-numru sebgħa, jekk jogħġbok. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 No 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Ħames, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Laughing] 461 00:15:24,770 --> 00:15:25,910 >> Mhuwiex kwistjoni trick. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 One. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Laughing] 466 00:15:34,695 --> 00:15:37,861 Wara dan, score tiegħek ma tantx hu tajba, sabiex inti tista 'ukoll jibqgħu għaddejjin. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Tlieta. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Laughing] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Mur fuq. 473 00:15:47,774 --> 00:15:50,690 Franchement, I iżda ma jistax jgħin wonder dak li qed ma jaħsbu dwar, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Laughing] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Biss il-filliera ta 'fuq, so inti stajt ltqajna tliet xellug. 477 00:15:55,020 --> 00:15:56,200 Allura ssib lili sebgħa. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Laughing] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Sebgħa. 484 00:16:26,946 --> 00:16:28,780 >> [Applause] 485 00:16:28,780 --> 00:16:29,426 >> Kull dritt. 486 00:16:29,426 --> 00:16:30,360 >> [END Daqq] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. Malan: Allura nistgħu watch dawn ġurnata kollha. 488 00:16:31,840 --> 00:16:34,090 U ovvjament, xi wħud demos din is-sena forsi 489 00:16:34,090 --> 00:16:36,330 issa se jispiċċaw fil jmiss video is-sena ukoll. 490 00:16:36,330 --> 00:16:39,040 Allura issa ejja fil-fatt tiffoka fuq l-algoritmi 491 00:16:39,040 --> 00:16:42,140 hawn, u ara jekk ma nistgħux issa tibda biex tifformalizza 492 00:16:42,140 --> 00:16:46,650 kif nistgħu tmur dwar jkollna data tagħna fis dan l-istat li huwa magħżula, 493 00:16:46,650 --> 00:16:50,054 sabiex finalment, nistgħu attwalment tfittxija b'mod aktar effiċjenti. 494 00:16:50,054 --> 00:16:52,470 U anki jekk aħna qed tmur tuża settijiet ta 'data pjuttost żgħar, 495 00:16:52,470 --> 00:16:54,511 bħall-tmien numri aħna hawn fuq il-bord, 496 00:16:54,511 --> 00:16:58,230 jista 'finalment japplikaw dawn l-istess ideat 1,000 inputs, miljun inputs, 497 00:16:58,230 --> 00:17:02,100 4 biljun inputs, minħabba li l-algoritmi ser ikunu fundamentalment l-istess. 498 00:17:02,100 --> 00:17:05,359 >> U għalhekk dan huwa aħħar tagħna opportunità għall-voluntiera llum, 499 00:17:05,359 --> 00:17:09,790 imma forsi l-aktar waħda involut, li għalihom hemm bżonn tmien voluntiera 500 00:17:09,790 --> 00:17:12,960 biex toħroġ u jimxu lilna permezz tal- proċess ta 'għażla x'se dalwaqt 501 00:17:12,960 --> 00:17:15,212 jkun fuq dawn il-mużika stands hawn. 502 00:17:15,212 --> 00:17:16,170 Nibda lura hawn. 503 00:17:16,170 --> 00:17:19,692 >> Allura wieħed fil-green turquoise-- huwa? 504 00:17:19,692 --> 00:17:21,130 Inti jikkommettu? 505 00:17:21,130 --> 00:17:21,630 Tnejn. 506 00:17:21,630 --> 00:17:23,069 Come fuq l isfel. 507 00:17:23,069 --> 00:17:23,569 KOLLOX SEW. 508 00:17:23,569 --> 00:17:24,420 Tlieta. 509 00:17:24,420 --> 00:17:25,400 Erbgħa. 510 00:17:25,400 --> 00:17:27,247 Ħalli me-- OK, ħamsa. 511 00:17:27,247 --> 00:17:28,830 Int jiġi nominat minn ħabib tiegħek. 512 00:17:28,830 --> 00:17:31,340 Sitta, seba ', u tmienja. 513 00:17:31,340 --> 00:17:32,130 Come fuq up. 514 00:17:32,130 --> 00:17:32,630 Kull dritt. 515 00:17:32,630 --> 00:17:33,190 Grazzi ħafna. 516 00:17:33,190 --> 00:17:33,689 Come fuq up. 517 00:17:33,689 --> 00:17:34,790 Come fuq up. 518 00:17:34,790 --> 00:17:35,330 >> Kull dritt. 519 00:17:35,330 --> 00:17:38,890 Allura dak li għandna here-- u dan hija fost dawk l-aktar skomdi, 520 00:17:38,890 --> 00:17:42,390 peress li dan se jeħtieġ li inti Humer me għal ftit ftit ftit ta 'żmien. 521 00:17:42,390 --> 00:17:43,442 Inti għandu jkun in-numru wieħed. 522 00:17:43,442 --> 00:17:44,150 X'hemm isem tiegħek? 523 00:17:44,150 --> 00:17:44,610 >> Annan: Annan. 524 00:17:44,610 --> 00:17:45,526 >> DAVID J. Malan: Annan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 X'hemm isem tiegħek? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. Malan: Joseph, inti numru tnejn. 529 00:17:49,190 --> 00:17:52,260 >> Serena: Serena, numru tlieta. 530 00:17:52,260 --> 00:17:53,722 Stefan, numru erbgħa. 531 00:17:53,722 --> 00:17:54,430 Cynthia: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. Malan: Cynthia, numru b'ħames. 533 00:17:57,548 --> 00:17:58,452 [Inaudible] 534 00:17:58,452 --> 00:17:59,618 DAVID J. Malan: [inaudible]. 535 00:17:59,618 --> 00:18:00,391 David, numru sitta. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. Malan: numru Matt sebgħa. 538 00:18:02,160 --> 00:18:02,850 U? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. Malan: Waverly, numru tmienja. 541 00:18:04,470 --> 00:18:04,970 Kull dritt. 542 00:18:04,970 --> 00:18:06,510 Jekk inti could-- Whoops. 543 00:18:06,510 --> 00:18:08,820 Jekk inti kollha, kif tiegħek ewwel sfida, hemm 544 00:18:08,820 --> 00:18:10,820 tmien stands mużika hawn qed tiffaċċja l-udjenza. 545 00:18:10,820 --> 00:18:14,200 Jekk inti tista 'tpoġġi numri tiegħek fuq dawn mużika stands b'tali mod 546 00:18:14,200 --> 00:18:16,560 li huma bi dritt il istess numri fuq il-bord. 547 00:18:16,560 --> 00:18:19,560 Sabiex tagħmel infuskom look like li billi tqegħid numri tiegħek fuq dawn il-mużika 548 00:18:19,560 --> 00:18:21,960 stands hawn. 549 00:18:21,960 --> 00:18:25,980 Eċċellenti s'issa. 550 00:18:25,980 --> 00:18:26,600 >> Eċċellenti. 551 00:18:26,600 --> 00:18:26,890 KOLLOX SEW. 552 00:18:26,890 --> 00:18:29,556 Allura issa, aħna qed tmur biex titlob lill- kwistjoni fi ftit modi differenti. 553 00:18:29,556 --> 00:18:31,610 Kif nistgħu tmur dwar għażla dawn folks up hawn? 554 00:18:31,610 --> 00:18:34,500 Minħabba kellna approċċi ftit qabel, fejn konna 555 00:18:34,500 --> 00:18:36,360 tip ta 'teħid żewġ bramel differenti. 556 00:18:36,360 --> 00:18:38,842 U allura konna ġeneralment piecing affarijiet flimkien. 557 00:18:38,842 --> 00:18:41,050 Hekk kif rajna żewġ numri li jappartjeni flimkien, 558 00:18:41,050 --> 00:18:41,975 npoġġux flimkien. 559 00:18:41,975 --> 00:18:43,350 Żewġ ittri li jappartjenu flimkien. 560 00:18:43,350 --> 00:18:45,058 >> Imma ejja ara jekk irridu ma jistgħux jifformalizza dan, 561 00:18:45,058 --> 00:18:48,044 sabiex inkunu finalment ikollhom xi-kodiċi psewdo inti se, 562 00:18:48,044 --> 00:18:49,710 li magħhom inti tista 'ssolvi dawn il-problemi. 563 00:18:49,710 --> 00:18:51,870 Allura issa, jien tfittex lejn dawn in-numri hawn. 564 00:18:51,870 --> 00:18:55,030 U nara mazz sħiħ ta 'żbalji. 565 00:18:55,030 --> 00:18:57,750 Fl-aħħarnett, nixtieq wieħed fuq il- xellug u tmienja fuq il-lemin. 566 00:18:57,750 --> 00:19:00,650 >> U hekk jien tħares lejn dawn iż-żewġ, erba 'u tnejn. 567 00:19:00,650 --> 00:19:02,930 U x'inhu l-problema, ovvjament? 568 00:19:02,930 --> 00:19:04,261 Yeah. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Żewġ ovvjament jasal quddiem erba, sabiex inti tkun taf liema? 571 00:19:07,160 --> 00:19:10,210 Let me ewwel jieħdu approċċ greedy, jekk inti se, ħafna problema simili 572 00:19:10,210 --> 00:19:13,790 sett one-- jekk inti recall mill- Standard Edition tal Problema Set One, 573 00:19:13,790 --> 00:19:16,820 fejn I biss lokalment ssolvi l-problema li d-dritt hawn quddiem lili 574 00:19:16,820 --> 00:19:17,690 u ara fejn din twassal me. 575 00:19:17,690 --> 00:19:17,870 >> KOLLOX SEW. 576 00:19:17,870 --> 00:19:20,161 Allura tnejn u erbgħa, let me go quddiem u biss tpartit inti tnejn. 577 00:19:20,161 --> 00:19:22,400 Jekk inti tista fiżikament jiċċaqalqu infuskom u karta tiegħek, 578 00:19:22,400 --> 00:19:25,040 I jidhru li gotten l- lista fi stat aħjar. 579 00:19:25,040 --> 00:19:26,330 >> Issa, dawn qed tajba. 580 00:19:26,330 --> 00:19:28,480 Jien ser jimxu fuq, erba 'u sitt, jidher tajjeb. 581 00:19:28,480 --> 00:19:29,110 Mhux problema. 582 00:19:29,110 --> 00:19:30,440 Sitt u tmienja, OK. 583 00:19:30,440 --> 00:19:31,860 Tmien u wieħed, problema oħra. 584 00:19:31,860 --> 00:19:34,750 Għaliex dak veru madwar tmien u waħda? 585 00:19:34,750 --> 00:19:36,990 Wieħed jasal quddiem tmienja, u iva, liema għandu nagħmlu? 586 00:19:36,990 --> 00:19:38,090 Ejja tpartit dawn iż-żewġ. 587 00:19:38,090 --> 00:19:39,316 Wieħed u tmienja. 588 00:19:39,316 --> 00:19:40,690 U issa, jien ser jibqgħu għaddejjin. 589 00:19:40,690 --> 00:19:42,030 Jien ser ikompli jfittex l quddiem. 590 00:19:42,030 --> 00:19:42,840 U ejja ara dak li jiġri. 591 00:19:42,840 --> 00:19:44,680 Tmien u tlieta, ta ' Naturalment, out of order. 592 00:19:44,680 --> 00:19:45,815 Ejja tpartit. 593 00:19:45,815 --> 00:19:46,940 Tmien u sebgħa, tal-kors. 594 00:19:46,940 --> 00:19:47,481 Out of order. 595 00:19:47,481 --> 00:19:48,280 Ejja tpartit. 596 00:19:48,280 --> 00:19:49,940 Tmien u ħamsa, naturalment, ejja swap. 597 00:19:49,940 --> 00:19:50,560 Kull dritt. 598 00:19:50,560 --> 00:19:51,880 Lista hija magħżula. 599 00:19:51,880 --> 00:19:53,060 iva? 600 00:19:53,060 --> 00:19:54,280 >> OK, ovvjament le. 601 00:19:54,280 --> 00:19:55,860 Iżda huwa xi ftit aħjar, right? 602 00:19:55,860 --> 00:19:57,270 Minħabba avviż dak li ġara. 603 00:19:57,270 --> 00:20:01,749 Kull darba għamilna swap, iżgħar Numru tip ta perkolati il-mod, 604 00:20:01,749 --> 00:20:03,790 u numru akbar perkolati B'dan il-mod, jew aħna ser 605 00:20:03,790 --> 00:20:06,880 tibda tgħid effervexxentement għall- xellug jew effervexxentement lejn il-lemin. 606 00:20:06,880 --> 00:20:10,080 >> Issa, mhuwiex biżżejjed, għax fl-aħjar numru jista 607 00:20:10,080 --> 00:20:11,990 mxew fuq il-post wieħed quddiem, jew fl-agħar, 608 00:20:11,990 --> 00:20:13,880 numru jista 'jkollhom mċaqalqa post wieħed ieħor. 609 00:20:13,880 --> 00:20:16,369 Allura inti taf liema, dan it-tip ta ħadmu pretty ukoll s'issa. 610 00:20:16,369 --> 00:20:17,410 Let me biss tipprova mill-ġdid. 611 00:20:17,410 --> 00:20:18,880 Tnejn u erbgħa, dawn qed OK. 612 00:20:18,880 --> 00:20:20,180 Erba 'u sitt, dawn qed OK. 613 00:20:20,180 --> 00:20:21,790 Sitt xhur u, out of order. 614 00:20:21,790 --> 00:20:23,007 Mela ejja tpartit inti tnejn. 615 00:20:23,007 --> 00:20:25,840 U issa, avviż-problema tibda tikseb ftit aħjar mill-ġdid. 616 00:20:25,840 --> 00:20:27,006 Sitt u tlieta, out of order. 617 00:20:27,006 --> 00:20:28,100 Ejja tpartit inti tnejn. 618 00:20:28,100 --> 00:20:29,730 Sitt u sebgħa, int tajba. 619 00:20:29,730 --> 00:20:32,230 Seba u ħamsa, naturalment, out of order. 620 00:20:32,230 --> 00:20:33,920 Seba u tmienja, fl-ordni. 621 00:20:33,920 --> 00:20:36,470 U issa, I jista 'jeħtieġ li tagħmel dan ftit aktar drabi. 622 00:20:36,470 --> 00:20:39,830 U fil-fatt, naħseb għall yourselves forsi kif ħafna drabi maximally 623 00:20:39,830 --> 00:20:41,330 jista I jkollhom jimxu quddiem u lura? 624 00:20:41,330 --> 00:20:42,390 >> Aħna ser terga 'lura għal dan. 625 00:20:42,390 --> 00:20:43,700 Allura tnejn u erbgħa għadhom OK. 626 00:20:43,700 --> 00:20:44,940 Erba 'u waħda, Nope. 627 00:20:44,940 --> 00:20:45,747 Allura, ejja swap. 628 00:20:45,747 --> 00:20:47,830 U għal darb'oħra, l-avviż viżwalment wieħed huwa tip ta 'tbaqbieq 629 00:20:47,830 --> 00:20:49,163 lejn ix-xellug, meta dan għandu jkun. 630 00:20:49,163 --> 00:20:50,010 Erba 'u tliet tpartit. 631 00:20:50,010 --> 00:20:51,330 Erba 'u sitt. 632 00:20:51,330 --> 00:20:53,100 Sitt u ħames swap. 633 00:20:53,100 --> 00:20:53,959 Sitt u sebgħa. 634 00:20:53,959 --> 00:20:55,000 Seba u tmienja huma tajbin. 635 00:20:55,000 --> 00:20:55,500 >> Tajba. 636 00:20:55,500 --> 00:20:58,460 Aħna jkollna anki aħjar. 637 00:20:58,460 --> 00:20:59,130 Mela ejja ara. 638 00:20:59,130 --> 00:21:00,940 Issa, għandna żewġ u wieħed. 639 00:21:00,940 --> 00:21:02,520 Of course, tpartit. 640 00:21:02,520 --> 00:21:07,520 Tnejn u tlieta, tlieta u erba ', erba' u ħames, sitt u seba ', seba' u tmien. 641 00:21:07,520 --> 00:21:08,020 Tajba. 642 00:21:08,020 --> 00:21:08,730 U inti taf liema? 643 00:21:08,730 --> 00:21:11,190 Minħabba I magħmula tibdil wieħed hemm, let me do check sanità wieħed. 644 00:21:11,190 --> 00:21:13,023 Let me tmur it-triq lura għall-bidu. 645 00:21:13,023 --> 00:21:13,680 KOLLOX SEW. 646 00:21:13,680 --> 00:21:14,750 Waħda, two-- Yup, ara? 647 00:21:14,750 --> 00:21:15,870 Xi ħaġa kienet żbaljata. 648 00:21:15,870 --> 00:21:18,420 Tlieta, erba ', ħames, sitt, seba', tmien. 649 00:21:18,420 --> 00:21:21,920 U f'dan l-aħħar pass, huma inti komdu ma issa tiegħi 650 00:21:21,920 --> 00:21:23,830 li qal li huwa magħżul? 651 00:21:23,830 --> 00:21:24,330 KOLLOX SEW. 652 00:21:24,330 --> 00:21:25,880 Viżwalment, dan huwa assolutament veru. 653 00:21:25,880 --> 00:21:28,410 Imma funzjonalment, dak ma wkoll jiġri biss 654 00:21:28,410 --> 00:21:31,870 F'dan l-aħħar pass li jippermettilek biex jikkonfermaw li din il-lista huwa tabilħaqq 655 00:21:31,870 --> 00:21:32,660 magħżula? 656 00:21:32,660 --> 00:21:34,477 >> What did I do jew ma tagħmel dan jgħaddi l-aħħar? 657 00:21:34,477 --> 00:21:35,810 UDJENZA: Ma kienx hemm tibdil. 658 00:21:35,810 --> 00:21:36,120 DAVID J. Malan: Jiddispjacini? 659 00:21:36,120 --> 00:21:37,070 UDJENZA: L-ebda bidla. 660 00:21:37,070 --> 00:21:38,653 DAVID J. Malan: Ma kienx hemm tibdil. 661 00:21:38,653 --> 00:21:41,947 Hekk ikun stupid ta 'lili li tagħmel dan algoritmu istess mill-ġdid 662 00:21:41,947 --> 00:21:43,780 jekk I ma tagħmel l-ebda bidliet l-ewwel darba. 663 00:21:43,780 --> 00:21:45,160 U l-istat ma nbidlitx. 664 00:21:45,160 --> 00:21:47,576 Żgur, jien mhux ser jagħmlu kwalunkwe bidliet it-tieni darba. 665 00:21:47,576 --> 00:21:49,820 U għalhekk, huwa sikur issa ngħid, lista hija magħżula. 666 00:21:49,820 --> 00:21:52,069 >> U fil-fatt, dan issa huwa xi ħaġa li aħna ser ġeneralment 667 00:21:52,069 --> 00:21:56,900 sejħa sort bużżieqa, fejn pairwise, inti jikkoreġu żbalji mill-ġdid, 668 00:21:56,900 --> 00:22:00,210 u għal darb'oħra, u għal darb'oħra, u inti jibqgħu għaddejjin quddiem u lura, 669 00:22:00,210 --> 00:22:03,370 u quddiem u lura, sakemm inti jagħmlu l-ebda swaps bħal dawn, f'liema punt 670 00:22:03,370 --> 00:22:07,089 inti tista 'tkun kunfidenti, yeah, I lest li jiffissa l-iżbalji. 671 00:22:07,089 --> 00:22:08,630 Ejja reset u jippruvaw approċċ ieħor. 672 00:22:08,630 --> 00:22:11,590 Jekk inti guys tista 'tmur lura fil l-ordni li inti kienu eżempju ilu, 673 00:22:11,590 --> 00:22:13,780 li dehru qishom dan. 674 00:22:13,780 --> 00:22:17,640 Issa, ejja tagħti approċċ ta 'l- ftit aktar bħall-ktieb eżami, 675 00:22:17,640 --> 00:22:21,122 li biha konna dejjem għażla tal-ittra tal-alfabett 676 00:22:21,122 --> 00:22:22,830 li aħna tip ta 'riedu biex jittrattaw jmiss. 677 00:22:22,830 --> 00:22:26,420 Forsi kien ittra għolja, bħal A, jew ittra Z. baxx 678 00:22:26,420 --> 00:22:28,170 >> Allura kulħadd lura f'din l-ordni. 679 00:22:28,170 --> 00:22:29,800 U issa let me tagħmel dan. 680 00:22:29,800 --> 00:22:34,880 Ejja naraw I know I jkollhom tmien numri hawn. 681 00:22:34,880 --> 00:22:37,410 Jien ser jimxi 'l quddiem u biss deliberatament tagħżel 682 00:22:37,410 --> 00:22:38,520 l-iżgħar elementi. 683 00:22:38,520 --> 00:22:38,760 Dritt? 684 00:22:38,760 --> 00:22:39,801 Dan jidher intuwittivi wisq. 685 00:22:39,801 --> 00:22:42,560 Għaliex ma nista 'nsib l-iżgħar element, poġġih fejn jappartjeni, 686 00:22:42,560 --> 00:22:45,280 mbagħad jiksbu l-element li jmiss iżgħar, tpoġġi fejn hi jappartjeni, u biss jirrepetu. 687 00:22:45,280 --> 00:22:46,820 >> Minħabba intuwittivament, li għandha taħdem wisq. 688 00:22:46,820 --> 00:22:48,441 Allura erba, li l-għadd pretty żgħir. 689 00:22:48,441 --> 00:22:49,940 Jien ser tiftakar fejn dan ikun. 690 00:22:49,940 --> 00:22:50,523 Stenna minuta. 691 00:22:50,523 --> 00:22:51,577 Tnejn hija iżgħar. 692 00:22:51,577 --> 00:22:53,910 Let me issa tiftakar fejn żewġ huwa, u tinsa dwar erbgħa. 693 00:22:53,910 --> 00:22:55,050 Aħna ser jittrattaw dan aktar tard. 694 00:22:55,050 --> 00:22:56,460 Sitta, jien ma interessati. 695 00:22:56,460 --> 00:22:57,810 Tmienja, jien ma interessati fil. 696 00:22:57,810 --> 00:22:59,780 Wieħed huwa numru żgħir ġdida tiegħi. 697 00:22:59,780 --> 00:23:01,470 Hekk jien ser tiftakar fejn wieħed hu. 698 00:23:01,470 --> 00:23:02,534 Tliet, mhumiex interessati. 699 00:23:02,534 --> 00:23:03,450 Seba ', mhumiex interessati. 700 00:23:03,450 --> 00:23:04,530 Ħames, mhumiex interessati. 701 00:23:04,530 --> 00:23:07,390 >> Allura mingħajr ma joħorġu barra l-istadju din is-sena, 702 00:23:07,390 --> 00:23:09,890 Jien ser grab numru one-- u dak li kien l-isem tiegħek mill-ġdid? 703 00:23:09,890 --> 00:23:10,150 >> Annan: Annan. 704 00:23:10,150 --> 00:23:11,220 >> DAVID J. Malan: Annan. 705 00:23:11,220 --> 00:23:13,540 U jekk inti tista 'tingħaqad miegħi fl il-bidu tal-lista, 706 00:23:13,540 --> 00:23:14,870 ejja tpoġġi lilek fejn inti jappartjenu. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- x'hemm isem tiegħek? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. Malan: Stefan hija fil-mod. 710 00:23:18,191 --> 00:23:23,490 Għalhekk qabel ma Stefan issolvi din problema, x'għandi nagħmlu? 711 00:23:23,490 --> 00:23:25,412 X'nagħmlu ma 'Stefan? 712 00:23:25,412 --> 00:23:27,269 >> UDJENZA: [inaudible]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. Malan: OK. 714 00:23:28,060 --> 00:23:28,850 Allura nistgħu nagħmlu dan. 715 00:23:28,850 --> 00:23:31,730 Nistgħu tip ta 'jieħu Stefan u tiegħu erba, u biss jitqiegħed fil-varjabbli 716 00:23:31,730 --> 00:23:33,530 u jżommu lill lilha għall xi ammont ta 'żmien, 717 00:23:33,530 --> 00:23:35,220 b'hekk tagħmel spazju għal numru wieħed. 718 00:23:35,220 --> 00:23:36,280 U li mhux ħażin. 719 00:23:36,280 --> 00:23:39,270 I tista 'tissuġġerixxi, għaliex ma aħna biss jitqiegħed Stefan hawn? 720 00:23:39,270 --> 00:23:41,610 Għaliex jista din tikser wieħed mill-ideat bdejna 721 00:23:41,610 --> 00:23:44,830 jitkellem dwar aħħar darba, l-aħħar ġimgħa? 722 00:23:44,830 --> 00:23:45,330 Yeah? 723 00:23:45,330 --> 00:23:45,740 >> UDJENZA: [inaudible]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. Malan: M'hemm l-ebda indiċi għal dan. 725 00:23:46,860 --> 00:23:49,735 Jekk taħseb ta 'dan, fil-fatt, bħala diodi, din hija bħal wieħed negattiv, 726 00:23:49,735 --> 00:23:52,900 b'hekk m'hemm l-ebda memorja attwalment hawn jekk dan huwa verament firxa, 727 00:23:52,900 --> 00:23:55,090 bħal aħna ddikjarat ġimgħa li għaddiet fil lecture. 728 00:23:55,090 --> 00:23:56,250 Allura aħna ma għandhom jagħmlu dan. 729 00:23:56,250 --> 00:23:57,340 Aħna jista 'jaħżen fil varjabbli. 730 00:23:57,340 --> 00:23:57,820 >> Jew inti taf liema? 731 00:23:57,820 --> 00:23:59,153 Smajt xi ħadd ieħor jissuġġerixxu dan. 732 00:23:59,153 --> 00:24:01,020 X'aktar jista nagħmlu ma 'Stefan? 733 00:24:01,020 --> 00:24:03,770 Għaliex ma aħna biss tkeċċi lilu u jniżżlu fuq fejn numru wieħed kien. 734 00:24:03,770 --> 00:24:05,170 Mela jekk inti tixtieq li tmur hemmhekk. 735 00:24:05,170 --> 00:24:07,300 U fil-fatt, dan huwa Soluzzjoni pjuttost tajba. 736 00:24:07,300 --> 00:24:10,480 Issa minn naħa, stajt tip tal għamel il-problema agħar. 737 00:24:10,480 --> 00:24:13,650 Erba issa huwa farther bogħod minn meta dan għandu jkun. 738 00:24:13,650 --> 00:24:14,900 Għandu jkun lejn Din it-taqsima. 739 00:24:14,900 --> 00:24:16,100 >> Imma inti taf liema? 740 00:24:16,100 --> 00:24:17,630 Li seta 'kien xortih ħażina. 741 00:24:17,630 --> 00:24:18,822 Forsi numru tmienja kien hawn. 742 00:24:18,822 --> 00:24:20,530 U hekk, forsi aħna se gotten xxurtjati, 743 00:24:20,530 --> 00:24:22,460 u mbuttati tmienja eqreb lejn l-aħħar. 744 00:24:22,460 --> 00:24:24,710 Għalhekk fl-aħħar tal-ġurnata, Huwa tip ta 'medji kollha barra. 745 00:24:24,710 --> 00:24:26,085 M'għandniex bżonn għall-kura dwar erbgħa. 746 00:24:26,085 --> 00:24:29,400 All I care about dritt issa huwa għażla tal-element iżgħar. 747 00:24:29,400 --> 00:24:32,030 >> U issa, dak li jien ser tagħmel huwa tinsieh numru wieħed 748 00:24:32,030 --> 00:24:35,160 b'mod permanenti, għaliex naf l- Lista lura lili issa huwa magħżul. 749 00:24:35,160 --> 00:24:36,720 Allura lista tiegħi kien preċedentement daqs tmienja. 750 00:24:36,720 --> 00:24:37,720 Issa, huwa ta 'daqs seba'. 751 00:24:37,720 --> 00:24:40,340 Allura problema tiegħi huwa jkollna iżgħar, għalkemm lineari. 752 00:24:40,340 --> 00:24:43,022 Allura issa, jien ser jagħżlu l- element iżgħar kurrenti, tnejn. 753 00:24:43,022 --> 00:24:46,520 Sitt, tmien, erba ', tlieta, seba, ħamsa. 754 00:24:46,520 --> 00:24:47,770 Dan kien l-iżgħar element. 755 00:24:47,770 --> 00:24:49,416 Allura dak am I se jagħmlu with-- dak li kien l-isem tiegħek mill-ġdid? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. Malan: Joseph? 758 00:24:50,085 --> 00:24:52,000 Aħna ser tħalli Joseph fis-seħħ. 759 00:24:52,000 --> 00:24:54,842 Issa, jien ser nippretendu li dawn guys are-- ukoll, 760 00:24:54,842 --> 00:24:56,550 Naf li dawn iż-żewġ huma diġà magħżula. 761 00:24:56,550 --> 00:24:58,424 Ejja issa jiffokaw fuq l- bqija tal-lista. 762 00:24:58,424 --> 00:25:00,080 Sitt huwa l-iżgħar kurrenti. 763 00:25:00,080 --> 00:25:01,190 Tmien huwa akbar. 764 00:25:01,190 --> 00:25:02,970 Erba issa huwa l-iżgħar kurrenti. 765 00:25:02,970 --> 00:25:04,762 Tliet issa huwa l-iżgħar kurrenti. 766 00:25:04,762 --> 00:25:07,720 U hekk issa, jien ser tagħżel tlieta, li is-- x'hemm isem tiegħek mill-ġdid? 767 00:25:07,720 --> 00:25:08,190 Serena: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. Malan: Serena, jekk inti tista grab numru tiegħek u tpartit with-- 769 00:25:10,620 --> 00:25:11,550 KALSANG: Kalsang. 770 00:25:11,550 --> 00:25:12,940 DAVID J. Malan: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Come fuq dahar, u aħna qed ser tpartit dawn iż-żewġ. 772 00:25:15,220 --> 00:25:17,360 U issa, ejja tpoġġi dan fuq awtopilota. 773 00:25:17,360 --> 00:25:21,589 Jien se jmorru u tħalli f'idejn l inti guys li jagħżlu l-elementi li ġejjin iżgħar. 774 00:25:21,589 --> 00:25:22,380 Dun, Dun, Dun, Dun. 775 00:25:22,380 --> 00:25:24,560 Numru erbgħa, x'għandek tagħmel? 776 00:25:24,560 --> 00:25:26,261 Eċċellenti. 777 00:25:26,261 --> 00:25:27,760 Issa, jien ser jagħmlu pass ieħor. 778 00:25:27,760 --> 00:25:28,590 Dun, Dun, Dun, Dun. 779 00:25:28,590 --> 00:25:31,465 Nara ħamsa huwa l-iżgħar jmiss. 780 00:25:31,465 --> 00:25:32,840 Issa, jien ser tieħu pass ieħor. 781 00:25:32,840 --> 00:25:33,631 Dun, Dun, Dun, Dun. 782 00:25:33,631 --> 00:25:34,880 Sitt huwa l-iżgħar. 783 00:25:34,880 --> 00:25:35,520 Tajba. 784 00:25:35,520 --> 00:25:36,585 Seba huwa l-iżgħar. 785 00:25:36,585 --> 00:25:37,085 L-ebda bidla. 786 00:25:37,085 --> 00:25:38,630 Tmien huwa l-iżgħar. 787 00:25:38,630 --> 00:25:39,170 Jsir. 788 00:25:39,170 --> 00:25:43,900 >> Allura dak li aħna ħadthom biss isir mill iteratively tagħżel element wieħed wara l-oħra 789 00:25:43,900 --> 00:25:47,230 huwa jimplimenta xi ħaġa li aħna qed ser jifformalizzaw mill sort għażla. 790 00:25:47,230 --> 00:25:49,120 U huwa forsi anke aktar sempliċi li tispjega, 791 00:25:49,120 --> 00:25:51,310 f'dak litteralment kull ma għandek trid tagħmel huwa biss iżommu 792 00:25:51,310 --> 00:25:54,700 tmur quddiem u lura permezz tal-lista għażla, l-element li jmiss iżgħar, 793 00:25:54,700 --> 00:25:55,720 sakemm inti qed isir. 794 00:25:55,720 --> 00:25:58,650 >> Allura huwa saħansitra aktar sempliċi, forsi intuwittivament, minn aħħar. 795 00:25:58,650 --> 00:26:00,020 Ejja nippruvaw aħħar wieħed wieħed. 796 00:26:00,020 --> 00:26:03,060 Jekk inti guys tista reset yourselves fil-pożizzjonijiet li ġejjin 797 00:26:03,060 --> 00:26:08,600 finali ħin, ejja ara jekk ma nistgħux issa tifformalizza approċċ ieħor. 798 00:26:08,600 --> 00:26:12,857 Fil-fatt, kieku xi ħadd hemmhekk tixtieq tipproponi 799 00:26:12,857 --> 00:26:14,440 kif inkella nistgħu tmur dwar kif isir dan? 800 00:26:14,440 --> 00:26:17,439 Mingħajr tossing out buzzwords jew tip ta 'tweġibiet li huma diġà magħrufa, 801 00:26:17,439 --> 00:26:19,689 biss intuwittivament, dak li nistgħu nagħmlu? 802 00:26:19,689 --> 00:26:21,635 >> UDJENZA: [inaudible]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. Malan: Yeah. 804 00:26:22,510 --> 00:26:24,620 Allura hemm xi intuwizzjoni kbira hemmhekk. 805 00:26:24,620 --> 00:26:28,020 Affarijiet tajba jidhru li jiġri s'issa fix-xjenza tal-kompjuter meta aħna jaqsam 806 00:26:28,020 --> 00:26:30,832 u jirbħu l-problema ta 'diviżjoni min-nofs u nofs u nofs. 807 00:26:30,832 --> 00:26:32,540 U hekk fil-fatt, aħna tista 'tibda tagħmel dan. 808 00:26:32,540 --> 00:26:35,754 U fil-fatt, li għaddej biex tkun, aħna ser tara, wieħed mill-aħjar soluzzjonijiet tagħna s'issa. 809 00:26:35,754 --> 00:26:37,420 Imma ejja terġa 'lura għal li qabel twil. 810 00:26:37,420 --> 00:26:40,500 Fil-fatt, aħna qed tmur biex tagħmel li ftit aktar tard din il-ġimgħa. 811 00:26:40,500 --> 00:26:42,180 X'iktar jista nagħmlu biex issolvi din? 812 00:26:42,180 --> 00:26:44,647 Allura kulħadd hawnhekk huwa ordni apparentement każwali. 813 00:26:44,647 --> 00:26:45,230 Taf xiex? 814 00:26:45,230 --> 00:26:48,320 Pjuttost milli jmorru quddiem u lura, quddiem u lura, u lura 815 00:26:48,320 --> 00:26:50,624 kull darba, dan iħoss bħal Jien jagħmlu ħafna mixi. 816 00:26:50,624 --> 00:26:52,790 Għaliex ma I biss tibda fil il-bidu tal-lista, 817 00:26:52,790 --> 00:26:54,960 u biss jitqiegħed erba fejn jappartjeni? 818 00:26:54,960 --> 00:26:59,680 So let me tħallas għall-mument li lista tiegħi huwa biss dan l-ewwel element. 819 00:26:59,680 --> 00:27:04,937 Huwa erba magħżula f'dan il-mument fil-ħin, jekk kollox I care about huwa kollox hawn? 820 00:27:04,937 --> 00:27:06,520 Dan huwa tip ta 'trivially vera, right? 821 00:27:06,520 --> 00:27:10,000 Bħall-lista li fiha numru wieħed, u dak in-numru erbgħa hija ovvjament magħżula. 822 00:27:10,000 --> 00:27:13,070 >> So let me biss jistipulaw li din il-lista huwa magħżul. 823 00:27:13,070 --> 00:27:15,090 Imma issa għandi l-bqija ta 'din il-lista. 824 00:27:15,090 --> 00:27:17,240 Allura issa, I jiltaqgħu tnejn. 825 00:27:17,240 --> 00:27:21,690 Fejn ma żewġ ovvjament jappartjenu rigward erba? 826 00:27:21,690 --> 00:27:22,580 Qabel erbgħa. 827 00:27:22,580 --> 00:27:23,862 Allura x'nista 'nagħmel hawn? 828 00:27:23,862 --> 00:27:24,820 X'hemm isem tiegħek mill-ġdid? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. Malan: Joseph, jekk inti tista 'pass lura 831 00:27:26,030 --> 00:27:27,790 għal ftit mument bin-numru tiegħek. 832 00:27:27,790 --> 00:27:31,130 U issa dak li għandu Stefan tagħmel hawn? 833 00:27:31,130 --> 00:27:33,720 Ejja bidla Stefan hawn. 834 00:27:33,720 --> 00:27:35,520 U issa, let Joseph jaqgħu fil hawn. 835 00:27:35,520 --> 00:27:39,660 U issa, let me jsostnu li kollox hawnhekk huwa magħżul. 836 00:27:39,660 --> 00:27:42,474 Allura, riżultat simili, iżda approċċ fundamentalment differenti. 837 00:27:42,474 --> 00:27:44,140 I lanqas biss ħares x'hemm stabbiliti hemmhekk. 838 00:27:44,140 --> 00:27:46,310 I biss iżommu tieħu l-elementi kif dawn qed tingħata lill lili, 839 00:27:46,310 --> 00:27:47,240 u kif jittrattaw magħhom. 840 00:27:47,240 --> 00:27:48,330 >> Allura issa, nara numru sitta. 841 00:27:48,330 --> 00:27:51,110 Fejn ma numru sitta jappartjenu? 842 00:27:51,110 --> 00:27:53,250 Għandna żewġ, erba, sitta. 843 00:27:53,250 --> 00:27:54,800 Eżattament fejn hi dritt issa. 844 00:27:54,800 --> 00:27:57,750 Mela ejja jħallu dak biss, u issa isostnu li din il-parti tal-lista 845 00:27:57,750 --> 00:27:58,772 issa huwa magħżul. 846 00:27:58,772 --> 00:28:01,230 U għalhekk, dan iħoss fundamentalment differenti li jien biss 847 00:28:01,230 --> 00:28:05,230 jiċċaqalqu permezz tal-lista hawn linearment, u jien qatt ma irduppjar lura. 848 00:28:05,230 --> 00:28:05,730 Iva. 849 00:28:05,730 --> 00:28:06,230 Kull dritt. 850 00:28:06,230 --> 00:28:08,190 Allura tmienja, fejn do inti jappartjenu? 851 00:28:08,190 --> 00:28:08,730 Dritt hawn. 852 00:28:08,730 --> 00:28:09,310 Perfect. 853 00:28:09,310 --> 00:28:10,210 Allura issa, wieħed. 854 00:28:10,210 --> 00:28:10,900 Uh-oh. 855 00:28:10,900 --> 00:28:13,010 Dan iħoss simili huwa se jiġu jiswew ħafna flus. 856 00:28:13,010 --> 00:28:15,690 Issa, fil-algoritmu ta 'qabel, I biss biddlu nies. 857 00:28:15,690 --> 00:28:18,648 So I tista 'tpoġġi lilu-triq kollha lejn il-bidu, iżda mbagħad għaddiet Joseph. 858 00:28:18,648 --> 00:28:21,450 Imma jekk nimxi Joseph, issa dak li għaddej biex tkun ħażina? 859 00:28:21,450 --> 00:28:24,250 >> Issa, stajt tip ta undone-- stajt meħuda pass 'il quddiem u mbagħad 860 00:28:24,250 --> 00:28:26,300 pass wieħed lura, minħabba li issa Joseph ikun out of order. 861 00:28:26,300 --> 00:28:26,830 Mela ejja tagħmel dan. 862 00:28:26,830 --> 00:28:29,150 Jekk inti tista 'tieħu numru wieħed u pass lura għal ftit mument. 863 00:28:29,150 --> 00:28:30,490 Kif nistgħu put-- dak kien l-isem tiegħek mill-ġdid? 864 00:28:30,490 --> 00:28:31,130 >> Annan: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. Malan: Annan fis-seħħ? 866 00:28:32,610 --> 00:28:36,091 Dak li jeħtieġ li jiġri fir-rigward għal żewġ, erba ', sitt, u tmienja? 867 00:28:36,091 --> 00:28:37,570 Dawn kollha għandhom bżonn għal bidla. 868 00:28:37,570 --> 00:28:42,590 Mela jekk tmienja tixtieq li ċċaqlaq ewwel, imbagħad sitt, imbagħad erba ', imbagħad tnejn. 869 00:28:42,590 --> 00:28:45,380 U mbagħad Annan, jekk youd simili li jaqgħu fil hawn, tajba. 870 00:28:45,380 --> 00:28:47,760 Iżda hawnhekk, konna biss tip ta ħallas prezz 871 00:28:47,760 --> 00:28:49,510 f'punt differenti fil-algoritmu. 872 00:28:49,510 --> 00:28:52,550 Billi aħħar darba bl-għażla sort, u anki bubble sort, 873 00:28:52,550 --> 00:28:54,700 Jien mixi lura u raba, u lura, 874 00:28:54,700 --> 00:28:58,360 li hija ċertament jingħaddu flimkien -time għaqli, u litteralment gradwali. 875 00:28:58,360 --> 00:29:00,660 >> Sort Inserzjoni, fl-ewwel t'għajn, tidher simili huwa 876 00:29:00,660 --> 00:29:05,150 super intelliġenti, f'dak jien biss jagħmlu bil-mod, progress inkrimentali, 877 00:29:05,150 --> 00:29:07,120 imma jien mhux ser f'dan il quddiem u lura. 878 00:29:07,120 --> 00:29:09,410 Imma jekk xi ħadd ikun tabilħaqq out of order, avviż 879 00:29:09,410 --> 00:29:10,840 kollha tax-xogħol I biss kellha tagħmel. 880 00:29:10,840 --> 00:29:14,750 I kellha timxi nofs tal-lista biss biex tagħmel spazju għal numru wieħed. 881 00:29:14,750 --> 00:29:16,790 Allura huwa l-istess ammont xogħol s'issa dan 882 00:29:16,790 --> 00:29:18,690 iħoss, biss tip differenti ta 'xogħol. 883 00:29:18,690 --> 00:29:19,370 >> Ejja tkompli. 884 00:29:19,370 --> 00:29:22,657 Allura issa nafu li kulħadd bejn wieħed u tmien huma magħżula. 885 00:29:22,657 --> 00:29:23,740 Hawnhekk, I jkollhom numru tlieta. 886 00:29:23,740 --> 00:29:25,864 Jekk inti tixtieq li pick up numru tlieta, pass lura wieħed. 887 00:29:25,864 --> 00:29:28,260 U dak li inti guys bżonn tagħmel? 888 00:29:28,260 --> 00:29:28,760 Yep. 889 00:29:28,760 --> 00:29:33,070 Allura dak xulxin, tnejn, tlieta passi. 890 00:29:33,070 --> 00:29:36,010 Tliet unitajiet ta 'ħin li biss l-ispiża me, sabiex tliet jistgħu issa joqogħdu. 891 00:29:36,010 --> 00:29:37,460 Fl-aħħarnett, seba '. 892 00:29:37,460 --> 00:29:39,730 >> Ejja imorru quddiem u jkollhom tieħu pass lura. 893 00:29:39,730 --> 00:29:42,780 Dan huwa biss se ispiża us unità waħda ta 'żmien, iżda li OK. 894 00:29:42,780 --> 00:29:44,170 U issa, ħames għaddej biex jkun ftit aktar għaljin. 895 00:29:44,170 --> 00:29:45,340 Jekk inti tixtieq li pass lura. 896 00:29:45,340 --> 00:29:48,380 Jeħtieġ li nimxu tmienja, u seba ', u sitta. 897 00:29:48,380 --> 00:29:50,749 U allura kulħadd issa huwa magħżul. 898 00:29:50,749 --> 00:29:52,290 Allura idejn big lil voluntiera tagħna hawn. 899 00:29:52,290 --> 00:29:53,554 Grazzi ħafna. 900 00:29:53,554 --> 00:29:56,220 >> [Applause] 901 00:29:56,220 --> 00:29:56,860 >> Nirringrazzjakom ilkoll. 902 00:29:56,860 --> 00:29:57,520 Nirringrazzjakom ilkoll. 903 00:29:57,520 --> 00:30:02,940 Mela ejja ara issa kemm għalja kollha ta 'dak kien. 904 00:30:02,940 --> 00:30:06,210 Ejja jikkunsidraw forsi l- aktar sempliċi ta 'dawn, sort bużżieqa. 905 00:30:06,210 --> 00:30:09,950 U jien ngħidlek sempliċi, biss minħabba inti tista issolvi dan greedily bi ftit 906 00:30:09,950 --> 00:30:11,660 tiffissa l-problema pairwise hawn. 907 00:30:11,660 --> 00:30:13,720 Tiffissa l-problema pairwise hawn, għal darb'oħra u għal darb'oħra 908 00:30:13,720 --> 00:30:17,680 u għal darb'oħra, tirrepeti daqs darbiet inti fil-fatt bżonn. 909 00:30:17,680 --> 00:30:21,050 >> Għalhekk jirriżulta li bi speċi bużżieqa, ukoll, 910 00:30:21,050 --> 00:30:25,820 kemm passi għandi jieħdu fuq l-ewwel pass ta 'din l-algorithm? 911 00:30:25,820 --> 00:30:30,850 I jista take-- ejja see-- waħda, tnejn, tlieta, erba ', ħames, sitt, seba'. 912 00:30:30,850 --> 00:30:32,190 U hemm tmien elementi hawn. 913 00:30:32,190 --> 00:30:35,280 Allura huwa simili n minus 1 passi biex jiksbu mill-bidu tal-lista 914 00:30:35,280 --> 00:30:36,380 sa l-aħħar tal-lista. 915 00:30:36,380 --> 00:30:41,350 >> Iżda ma sort għażla, ifakkar li jien għażla tal-elementi mill-ġdid u għal darb'oħra 916 00:30:41,350 --> 00:30:44,590 u għal darb'oħra li l-iżgħar, Jien tqegħid fil-post, 917 00:30:44,590 --> 00:30:46,616 iżda mbagħad jien ma tfittex lura lili darb'oħra. 918 00:30:46,616 --> 00:30:49,490 So I think huwa ftit aktar ċara allura dak l-ewwel darba, I jista 919 00:30:49,490 --> 00:30:52,680 għandek tieħu l n minus 1 passi biex isibu l-element iżgħar. 920 00:30:52,680 --> 00:30:55,920 Imbagħad I jpoġġuhom fil-post, u I tkeċċi min kien hawn qabel. 921 00:30:55,920 --> 00:30:57,500 >> Imma mbagħad I ma jkollhom iżommu tħares lejn dan l-element, 922 00:30:57,500 --> 00:30:59,040 għaliex naf huwa diġà l-iżgħar. 923 00:30:59,040 --> 00:31:01,581 Allura issa, I tista 'tħares lejn biss seba elementi, imbagħad sitt elementi, 924 00:31:01,581 --> 00:31:03,290 imbagħad ħames elementi, allura erba 'elementi. 925 00:31:03,290 --> 00:31:06,900 U għalhekk matematikament, jekk n hija in-numru ta 'elementi jew numri 926 00:31:06,900 --> 00:31:11,990 li bdejna ma ', inti tista' timmaġina li dan huwa l-istess bħal n minus 1, 927 00:31:11,990 --> 00:31:14,250 plus n minus 2 passi, plus n minus 3 passi, 928 00:31:14,250 --> 00:31:16,780 plus n minus 4 passi, l- triq biss pass wieħed. 929 00:31:16,780 --> 00:31:18,160 U jien fuq persuna tiegħi aħħar. 930 00:31:18,160 --> 00:31:20,650 >> U jekk inti recall li ħafna tal stats kotba jew kotba matematika 931 00:31:20,650 --> 00:31:24,730 jkollhom dawk formuli fuq il- Hardcover dahar jew ta 'quddiemhom, 932 00:31:24,730 --> 00:31:27,690 jirriżulta li din is-serje jista 'jiġi espress b'mod aktar sempliċi 933 00:31:27,690 --> 00:31:28,857 kif n darbiet n minus 1 minn 2. 934 00:31:28,857 --> 00:31:31,273 U huwa multa jekk dan mhux fuq quddiemnett tal-moħħ tiegħek. 935 00:31:31,273 --> 00:31:32,420 Iżda dan huwa minnu. 936 00:31:32,420 --> 00:31:34,449 Li jinsab biss mod sempliċi ta 'kitba dan. 937 00:31:34,449 --> 00:31:36,240 U allura jekk taħseb lura l-iskola grad, 938 00:31:36,240 --> 00:31:38,698 meta tkun għadek tibda multiplikazzjoni affarijiet out, dan il-kors, 939 00:31:38,698 --> 00:31:41,820 huwa biss n kwadrat minus n diviż bi 2. 940 00:31:41,820 --> 00:31:44,772 All I ghamilt hija tespandi l-espressjonijiet hemm. 941 00:31:44,772 --> 00:31:46,730 U hekk ejja jikteb dan ftit differenti. 942 00:31:46,730 --> 00:31:49,780 Li n kwadrat diviż bi 2 minus n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Għalhekk għal darb'oħra, jien biss tip ta 'applikazzjoni xi aritmetika regoli hemmhekk. 944 00:31:53,270 --> 00:31:57,140 Imma avviż issa li t-terminu akbar f'dan espressjoni, biex ngħidu hekk, 945 00:31:57,140 --> 00:31:58,540 hija li n kwadrat. 946 00:31:58,540 --> 00:32:02,910 Allura iva, huwa n kwadrat maqsum bi 2, nieqes n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Iżda ġeneralment, jekk n hija se tkun valur kbir, 948 00:32:05,080 --> 00:32:08,740 Jien ser issostni li n kwadrat se tkun il-fattur dominanti. 949 00:32:08,740 --> 00:32:10,490 Huwa biss se tkun kontributur akbar 950 00:32:10,490 --> 00:32:12,877 għan-numru ta 'passi minn n / 2. 951 00:32:12,877 --> 00:32:13,960 Mela xi do I jfisser minn dan? 952 00:32:13,960 --> 00:32:16,795 Ejja nippruvaw eżempju sempliċi, anke għalkemm l-matematika gets big ftit. 953 00:32:16,795 --> 00:32:20,210 >> Allura jissoponi kellna 1 miljun ruħ fuq il-palk, jew 1 miljun affarijiet 954 00:32:20,210 --> 00:32:21,320 li aħna rridu li sort. 955 00:32:21,320 --> 00:32:23,730 Ejja plug miljun fis eżattament dak formula 956 00:32:23,730 --> 00:32:27,230 biex tara kemm passi li tieħu totali biex issolvi miljun elementi jużaw jiġifieri, 957 00:32:27,230 --> 00:32:28,560 sort għażla. 958 00:32:28,560 --> 00:32:30,760 >> Allura aħna d jkollhom l-istess formula bħal qabel. 959 00:32:30,760 --> 00:32:34,120 I d plug miljun, b'tali mod li niġi miljun kwadrat diviż bi 2, 960 00:32:34,120 --> 00:32:35,990 nieqes miljun maqsum bi 2. 961 00:32:35,990 --> 00:32:40,180 Jekk nagħmel dan matematika bil-quddiem hawnhekk, għandna 500 biljun 962 00:32:40,180 --> 00:32:47,460 nieqes 500,000, li tagħtina 499999500000, 963 00:32:47,460 --> 00:32:49,270 li huwa pjuttost darn big. 964 00:32:49,270 --> 00:32:54,370 >> Fil-fatt, jekk inti tqabbel issa 499,000,000,000, 999,000,000, 965 00:32:54,370 --> 00:33:01,210 500000 kontra valur oriġinali tagħna, 500 biljun, huwa hekk kkritikat qrib. 966 00:33:01,210 --> 00:33:06,850 Dritt? n kwadrat diviż bi 2 jagħti us-- jew minflok, n kwadrat diviż bi 2 967 00:33:06,850 --> 00:33:08,370 tana 500 biljun. 968 00:33:08,370 --> 00:33:13,510 Li pretty darn qrib li 499999500000, 969 00:33:13,510 --> 00:33:17,970 li jfisser li tnaqqas off 500,000, jew b'mod iktar ġenerali, jitnaqqas off 970 00:33:17,970 --> 00:33:20,010 n kwadrat, mhuwiex verament big deal. 971 00:33:20,010 --> 00:33:22,490 Il n kwadrat jagħmel dawn numri jikbru verament mgħaġġel. 972 00:33:22,490 --> 00:33:25,790 >> Issa, dan huwa importanti biss safejn kif aħna, bħala xjenzjati tal-kompjuter, 973 00:33:25,790 --> 00:33:29,350 huma ġeneralment mhux ser kura daqstant dwar l-sfumaturi ta 'dawn il-formuli 974 00:33:29,350 --> 00:33:31,400 u eżattament dak li l- tweġibiet preċiżi huma. 975 00:33:31,400 --> 00:33:33,390 Aħna kura biss, inti taf liema? 976 00:33:33,390 --> 00:33:37,810 Fl-aħħar tal-ġurnata, din il-formula hija fuq l-ordni ta 'n kwadrat. 977 00:33:37,810 --> 00:33:39,350 >> Iva, aħna qed diviż bi 2 fil hemmhekk. 978 00:33:39,350 --> 00:33:41,360 Iva, aħna qed jitnaqqas off n tnaqqis ta '2. 979 00:33:41,360 --> 00:33:46,860 Iżda fl-aħħar tal-ġurnata, it-terminu li verament jolqot lilna u l-ispejjeż us 980 00:33:46,860 --> 00:33:48,995 ħafna passi huwa dak it-terminu kwadru. 981 00:33:48,995 --> 00:33:51,370 U iva, liema xjenzat kompjuter se ġeneralment jagħmlu 982 00:33:51,370 --> 00:33:54,160 huwa jinjora dawk kollha termini ordni iżgħar, 983 00:33:54,160 --> 00:33:56,900 u biss ħarsa lejn dak li jikkontribwixxi l-aktar għall-ispiża. 984 00:33:56,900 --> 00:34:00,530 >> U dan huwa sbieħ, għaliex nistgħu issa jitkellmu ġeneralità ferm akbar 985 00:34:00,530 --> 00:34:02,470 dwar algoritmi, u jista jqabbluhom. 986 00:34:02,470 --> 00:34:04,550 U l-fatt li jien jużaw dan O huwa intenzjonat. 987 00:34:04,550 --> 00:34:06,680 Meta I say fuq l-ordni ta, jien speċifikament 988 00:34:06,680 --> 00:34:09,560 jirreferu għal xi ħaġa imsejħa O. ​​big U big O 989 00:34:09,560 --> 00:34:14,090 huwa notazzjoni li l-kompjuter xjentist juża biex jiddeskrivu 990 00:34:14,090 --> 00:34:16,710 'fuq marbuta fuq xi ħaġa. 991 00:34:16,710 --> 00:34:21,150 >> Mela jekk inti tgħidli li algoriżmu huwa O kbira ta 'n kwadrat, 992 00:34:21,150 --> 00:34:23,380 kif I propost biss mument ilu, li l-mezzi 993 00:34:23,380 --> 00:34:27,710 li f'termini ta 'tmexxija tagħha time jew l-effiċjenza tiegħu, 994 00:34:27,710 --> 00:34:30,090 dan jieħu l-ordni ta n kwadrat passi. 995 00:34:30,090 --> 00:34:31,420 Forsi aktar, forsi inqas. 996 00:34:31,420 --> 00:34:33,435 Imma hija dwar l-ordni ta 'n kwadrat. 997 00:34:33,435 --> 00:34:34,560 U dak l-rbit għoli. 998 00:34:34,560 --> 00:34:36,530 Huwa mhux se tkun iktar diffiċli minn dak. 999 00:34:36,530 --> 00:34:40,800 Huwa mhux se tkun n kubiku, jew 2 għall-n, jew xi ħaġa ferm ikbar. 1000 00:34:40,800 --> 00:34:43,800 Dan huwa rbit superjuri fuq kwalunkwe tali kost huwa. 1001 00:34:43,800 --> 00:34:46,150 Allura peress li, ejja jikkunsidraw biss ftit eżempji. 1002 00:34:46,150 --> 00:34:49,820 U dan huwa biss lista limitata ħinijiet tmexxija tal komuni ħafna 1003 00:34:49,820 --> 00:34:52,870 għal algoritmi li kien ifisser li jkun illustrattiva ta 'xi affarijiet Imxejna 1004 00:34:52,870 --> 00:34:53,600 tidher diġà. 1005 00:34:53,600 --> 00:34:58,060 >> Allura per eżempju, fil-każ ta ' sort għażla, dak li jien titlob hawn 1006 00:34:58,060 --> 00:35:02,250 li għaddej b'mod dik it-tip Għażla ħin huwa fuq l-ordni ta 'n kwadrat. 1007 00:35:02,250 --> 00:35:06,260 Fl-agħar każ, jien ser ikollhom mazz sħiħ ta 'numri bl-addoċċ hawn. 1008 00:35:06,260 --> 00:35:08,600 U kif rajna matematikament, jekk I iżommu mixi 1009 00:35:08,600 --> 00:35:11,310 permezz tal-lista, permezz tal- lista, l-għażla li jmiss iżgħar 1010 00:35:11,310 --> 00:35:14,410 element ġdid u għal darb'oħra, jekk I attwalment ikteb kollha tal-passi 1011 00:35:14,410 --> 00:35:18,750 Jien tieħu bħala I propost formulaically qabel, huwa dwar l-ordni ta 'n kwadrat 1012 00:35:18,750 --> 00:35:20,370 passi li jien jieħdu. 1013 00:35:20,370 --> 00:35:24,520 >> U jirriżulta li bużżieqa sort u l-inserzjoni sort 1014 00:35:24,520 --> 00:35:27,370 huma daqstant bil-mod fl-agħar każ. 1015 00:35:27,370 --> 00:35:32,040 Ikkunsidra, per eżempju, sort inserzjoni, l-ħafna aħħar algoritmu aħna ttrattati, 1016 00:35:32,040 --> 00:35:35,500 li kellhom nħarsu lejn l-element, u mbagħad daħlu fejn jappartjeni. 1017 00:35:35,500 --> 00:35:38,720 U allura aħna ħares lejn l-element li jmiss, u mdaħħla fejn hi jappartjeni. 1018 00:35:38,720 --> 00:35:40,990 >> Għalhekk tikkunsidra l-aħjar xenarju possibbli. 1019 00:35:40,990 --> 00:35:45,590 Ejja ngħidu I kien voluntiera tiegħi line up litteralment bħal dan, wieħed permezz tmienja, 1020 00:35:45,590 --> 00:35:47,440 diġà magħżula. 1021 00:35:47,440 --> 00:35:51,300 Kemm passi huwa tip inserzjoni ser jieħu biex issolvi tmien persuni, 1022 00:35:51,300 --> 00:35:55,640 jekk jaslu fuq il-palk tfittex bħal dan? 1023 00:35:55,640 --> 00:35:57,410 >> Tmien persuni li diġà magħżula. 1024 00:35:57,410 --> 00:35:58,760 U jien jużaw sort inserzjoni. 1025 00:35:58,760 --> 00:36:02,180 Din l-aħħar ta 'l-algoritmi. 1026 00:36:02,180 --> 00:36:03,640 Well, ejja jerġgħu jiġu stabbiliti fast reali. 1027 00:36:03,640 --> 00:36:05,504 Mela jekk jien tibda hawn, I tara wieħed. 1028 00:36:05,504 --> 00:36:06,420 Fejn korp bħal dan jappartjeni? 1029 00:36:06,420 --> 00:36:07,730 Jappartjeni dritt hawn. 1030 00:36:07,730 --> 00:36:08,330 Nara tnejn. 1031 00:36:08,330 --> 00:36:09,660 Fejn ma tnejn jappartjenu? 1032 00:36:09,660 --> 00:36:10,260 Dritt hawn. 1033 00:36:10,260 --> 00:36:10,900 Nara tlieta. 1034 00:36:10,900 --> 00:36:11,920 Fejn ma tlieta jappartjenu? 1035 00:36:11,920 --> 00:36:12,480 Dritt hawn. 1036 00:36:12,480 --> 00:36:13,100 >> Nara erbgħa. 1037 00:36:13,100 --> 00:36:13,600 Dritt hawn. 1038 00:36:13,600 --> 00:36:15,660 Ta 'ħames, sitt, seba', tmien. 1039 00:36:15,660 --> 00:36:17,320 M'hemm l-ebda raġuni biex jirrepetu myself. 1040 00:36:17,320 --> 00:36:21,260 U l-passi hekk, kemm huwa li f'termini ta 'n? 1041 00:36:21,260 --> 00:36:23,870 Huwa dwar l-ordni ta 'n passi, id-dritt? n minus 1. 1042 00:36:23,870 --> 00:36:27,567 Imma I ħa numru lineari ta 'passi, u issa jien jsir. 1043 00:36:27,567 --> 00:36:28,900 Allura li l-aħjar każ, għalkemm. 1044 00:36:28,900 --> 00:36:29,983 Xi ngħidu dwar l-agħar każ? 1045 00:36:29,983 --> 00:36:32,730 Liema tmien kien hemmhekk, u sebgħa kienu stabbiliti hemm, 1046 00:36:32,730 --> 00:36:35,840 u wieħed u tnejn kienu hawn fuq, sabiex li l-lista kienu verament maqluba? 1047 00:36:35,840 --> 00:36:38,300 >> Ukoll, dak li jiġri fil-fatt jekk dan huwa n-numru? 1048 00:36:38,300 --> 00:36:41,300 U aħna ser tagħmel biss ftit eżempji. 1049 00:36:41,300 --> 00:36:49,300 X'jiġri jekk, fil-fatt, in-numru tmienja hija hawnhekk, u l-Whoops number--. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Allura dak li jekk, fil-fatt, in-numru tmienja hija it-triq kollha madwar hawn, 1052 00:36:56,430 --> 00:36:57,790 u jien jużaw sort inserzjoni? 1053 00:36:57,790 --> 00:36:58,290 >> KOLLOX SEW. 1054 00:36:58,290 --> 00:37:00,280 I titlob fil-mument huwa fil-post. 1055 00:37:00,280 --> 00:37:03,152 Imma issa, seven-- fejn ma seven imorru? 1056 00:37:03,152 --> 00:37:04,360 Of course, din tmur minn hawn. 1057 00:37:04,360 --> 00:37:06,760 So I ikollha tiġi spustjata tmien fuq il-post wieħed. 1058 00:37:06,760 --> 00:37:08,554 Issa sitt, fejn ma tmur? 1059 00:37:08,554 --> 00:37:09,220 Well, id-dritt. 1060 00:37:09,220 --> 00:37:13,150 Issa, I għandhom jimxu tmien fuq post, u seba fuq il-post, 1061 00:37:13,150 --> 00:37:14,440 u mbagħad I plop isfel sitt. 1062 00:37:14,440 --> 00:37:16,870 >> Allura l-ewwel darba, l-ispiża me wieħed pass biex jiffissaw affarijiet, 1063 00:37:16,870 --> 00:37:18,570 allura jiswa me żewġ passi biex tiffissa l-affarijiet. 1064 00:37:18,570 --> 00:37:20,370 Kemm passi huwa ser jieħdu biex jiffissaw 1065 00:37:20,370 --> 00:37:22,720 affarijiet li tpoġġi ħamsa fil-post it-tajjeb? 1066 00:37:22,720 --> 00:37:23,340 Tlieta. 1067 00:37:23,340 --> 00:37:29,520 Għaliex issa I għandhom jimxu wieħed, tnejn, tlieta. 1068 00:37:29,520 --> 00:37:32,430 Kemm passi huwa se jieħu li jpoġġi erba 'fil-post dritt? 1069 00:37:32,430 --> 00:37:36,040 4 plus 5, flimkien ma '6, plus 7. 1070 00:37:36,040 --> 00:37:40,260 >> U dan huwa matematikament identiċi għal dak li aħna deskritt għall tip selezzjoni. 1071 00:37:40,260 --> 00:37:42,130 Għandna din is-serje li jinsab biss tiżdied. 1072 00:37:42,130 --> 00:37:45,650 1 flimkien ma '2 u 3 u 4, jew bil-maqlub, 7 plus 6 1073 00:37:45,650 --> 00:37:52,610 plus 5 plus 4 tammonta għal-lum iskopijiet għad dwar l-ordni ta 'n kwadrat. 1074 00:37:52,610 --> 00:37:57,640 >> So let me jistipulaw wisq li sort bużżieqa huwa wkoll fl n kwadrat. 1075 00:37:57,640 --> 00:38:01,340 Minħabba li bl sort bużżieqa, kull darba li mmur permezz tal-lista, 1076 00:38:01,340 --> 00:38:03,100 Jien tieħu bejn wieħed u ieħor kemm passi? 1077 00:38:03,100 --> 00:38:06,260 Kull darba I litteralment jimxu minn hemm sa hemmhekk? 1078 00:38:06,260 --> 00:38:07,960 Madwar passi n. 1079 00:38:07,960 --> 00:38:12,650 Imma kif ħafna drabi tista I bżonn li jgħaddu mill-lista? 1080 00:38:12,650 --> 00:38:13,920 >> Ukoll, bejn wieħed u ieħor n żmien. 1081 00:38:13,920 --> 00:38:15,680 Forsi n minus 1, iżda madwar żminijiet n. 1082 00:38:15,680 --> 00:38:16,430 Well, għaliex huwa li? 1083 00:38:16,430 --> 00:38:19,560 Ukoll, ma sort bużżieqa, jekk nibdew il sort bużżieqa, 1084 00:38:19,560 --> 00:38:23,570 il-lista fl-agħar possibbli sitwazzjoni, li għal darb'oħra huwa kompletament 1085 00:38:23,570 --> 00:38:25,550 lura, dak li jiġri? 1086 00:38:25,550 --> 00:38:28,830 I jgħaddu l-lista, u n-numru wieħed jappartjeni it-triq kollha hemmhekk. 1087 00:38:28,830 --> 00:38:33,280 >> Iżda ma sort bużżieqa, kemm ma wieħed jimxu fuq ewwel pass tiegħi permezz tal-lista? 1088 00:38:33,280 --> 00:38:36,620 Kemm spots ma hu jiksbu eqreb lejn il-post korretta? 1089 00:38:36,620 --> 00:38:37,240 Just wieħed. 1090 00:38:37,240 --> 00:38:40,281 Mela jekk inti tip ta raġuni permezz ta 'dan, kull darba li permezz ta 'dan algoritmu, 1091 00:38:40,281 --> 00:38:41,880 Jieħdu madwar passi n David. 1092 00:38:41,880 --> 00:38:44,940 Imma kemm jgħaddi permezz tal-lista huwa 1093 00:38:44,940 --> 00:38:49,060 se jieħdu għal wieħed bużżieqa lejn ix-xellug fejn jappartjeni? 1094 00:38:49,060 --> 00:38:51,840 >> Hu ltqajna biex jimxu simili, spazji n b'dan il-mod. 1095 00:38:51,840 --> 00:38:57,960 Hekk biss li jagħmlu l-għażla tal-lista, I jkollhom jimxu quddiem u lura n darbiet. 1096 00:38:57,960 --> 00:39:01,540 U kull darba, jien tħares lejn n elementi. 1097 00:39:01,540 --> 00:39:05,410 So do n affarijiet n darbiet fuq l-ordni ta 'n kwadrat. 1098 00:39:05,410 --> 00:39:07,220 >> Issa, aħna ser tara f'xi ta 'l-xorts li 1099 00:39:07,220 --> 00:39:10,440 huma integrati fil-problema li jmiss CS50 s stabbiliti, approċċ ieħor lejn dawn, 1100 00:39:10,440 --> 00:39:13,490 iżda għal issa, ejja biss tikkunsidra xi drabi running oħra, 1101 00:39:13,490 --> 00:39:16,840 speċjalment jekk dawk issortjar jieħdu xi ftit ta 'żmien biex jinżel fil. 1102 00:39:16,840 --> 00:39:21,790 X'hemm algoritmu Rajna diġà li jieħu fuq l-ordni ta 'passi n? 1103 00:39:21,790 --> 00:39:27,560 >> X'għandu tieħu numru lineari ta 'passi li aħna stajt tidher s'issa? 1104 00:39:27,560 --> 00:39:29,350 Dak X'inhu? 1105 00:39:29,350 --> 00:39:30,480 It-tfittxija direttorju tat-telefon. 1106 00:39:30,480 --> 00:39:31,390 L-ewwel algoritmu. 1107 00:39:31,390 --> 00:39:31,560 Dritt? 1108 00:39:31,560 --> 00:39:33,650 Fejn aħna qed lineari tiftix għal Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Tabilħaqq. 1110 00:39:34,150 --> 00:39:37,180 Minn żero ġimgħa, meta bdejt tidwir paġna waħda fi żmien, 1111 00:39:37,180 --> 00:39:40,095 u I anke qal li kien tip ta 'l-algoritmu sensazzjoni lineari, 1112 00:39:40,095 --> 00:39:42,720 u kellna li istampa fuq il- board mal-linja ħamra dritta 1113 00:39:42,720 --> 00:39:44,678 u l-isfar dritta line, dawn kienu tabilħaqq 1114 00:39:44,678 --> 00:39:46,810 algoritmi li huma O kbira ta 'n. 1115 00:39:46,810 --> 00:39:50,680 >> Minħabba li ssib Mike Smith fil-telefon ktieb ta 'paġni N, fil-agħar każ, 1116 00:39:50,680 --> 00:39:52,422 jista 'jieħu me n passi. 1117 00:39:52,422 --> 00:39:53,630 What dwar it-teħid attendenza? 1118 00:39:53,630 --> 00:39:55,790 Wieħed, tnejn, tlieta, erba ', ħames, sitt. 1119 00:39:55,790 --> 00:39:59,420 X'hemm-running time ta 'dan algoritmu għat-teħid attendenza? 1120 00:39:59,420 --> 00:40:03,070 O Big ta n, għaliex fit-teorija I ikollhom punt kulħadd fil-kamra. 1121 00:40:03,070 --> 00:40:05,861 >> Issa bħala twarrib, dak dwar il- ottimizzazzjoni oħra minn żero ġimgħa? 1122 00:40:05,861 --> 00:40:08,117 Ġimagħtejn, erba, sitta, tmienja, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 A xjentist kompjuter se realizzata, stenna minuta, 1124 00:40:10,200 --> 00:40:12,320 li fuq l-ordni ta ' n maqsuma minn żewġ passi. 1125 00:40:12,320 --> 00:40:12,820 Dritt? 1126 00:40:12,820 --> 00:40:14,444 Minħabba li qed nagħmel żewġ persuni kull darba. 1127 00:40:14,444 --> 00:40:17,015 Iżda aħna qed tmur biex jinjoraw dawn it-termini ordni aktar baxxa, 1128 00:40:17,015 --> 00:40:19,140 u aħna qed biss jmorru tarmi l-iddividi 2, 1129 00:40:19,140 --> 00:40:21,830 u biss jgħidu, O kbir ta 'n għal din l-algorithm ukoll. 1130 00:40:21,830 --> 00:40:22,760 >> Xi ngħidu dwar dan wieħed? 1131 00:40:22,760 --> 00:40:26,170 Aħna ser skip fuq xi wħud minn dawn, imma dak kien algoritmu li kienet log ta 'n? 1132 00:40:26,170 --> 00:40:29,900 Li ħa bejn wieħed u ieħor log passi n? 1133 00:40:29,900 --> 00:40:30,870 Il-firda u conquer. 1134 00:40:30,870 --> 00:40:31,369 Eżattament. 1135 00:40:31,369 --> 00:40:33,900 Bħall-eżempju ktieb tat-telefon fil ġimgħa żero u aktar kmieni llum, 1136 00:40:33,900 --> 00:40:36,191 fejn aħna maqsuma l-problema ġdid u għal darb'oħra u għal darb'oħra. 1137 00:40:36,191 --> 00:40:39,070 Aħna ġibdet fuq il-bord fil-ġimgħa żero bħala linja ħadra mgħawweġ, 1138 00:40:39,070 --> 00:40:41,460 u għidna dak il-jum kien algoritmu logaritmika. 1139 00:40:41,460 --> 00:40:44,970 >> U fil-fatt, in-numru ta 'passi li jieħu biex iwettqu firda u conquer, 1140 00:40:44,970 --> 00:40:48,610 jew tfittxija binarja kif aħna ser tibda ssejjaħ dan, bħal fil-ktieb tat-telefon, 1141 00:40:48,610 --> 00:40:50,680 hija fuq l-ordni ta 'log u passi. 1142 00:40:50,680 --> 00:40:52,470 U dan huwa daqsxejn ta 'wieħed stramb. 1143 00:40:52,470 --> 00:40:54,910 >> Liema jieħu pass wieħed, jew b'mod aktar speċifiku 1144 00:40:54,910 --> 00:40:56,240 numru kostanti ta 'passi? 1145 00:40:56,240 --> 00:40:58,865 Forsi huwa tnejn, forsi huwa tlieta, iżda xjenzat kompjuter biss 1146 00:40:58,865 --> 00:41:01,423 tissemplifika bħala O kbir ta '1, xi numru kostanti ta 'passi. 1147 00:41:01,423 --> 00:41:04,256 X'hemm xi ħaġa inti tista 'tagħmel dan jieħu numru kostanti ta 'passi? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> X'hemm-running time ta clapping? 1150 00:41:10,930 --> 00:41:11,920 Ħin kostanti. 1151 00:41:11,920 --> 00:41:12,420 Dritt? 1152 00:41:12,420 --> 00:41:15,490 Bħal, x'inhu l-running time ta tagħmel xi ħaġa li tieħu biss wieħed 1153 00:41:15,490 --> 00:41:18,570 operazzjoni, bħal print F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Li jista 'jingħad li jkun żmien kostanti, sakemm anqas każ kantuniera ma print F, 1155 00:41:24,110 --> 00:41:28,260 Liema jista 'l-running time stampati F 'attwalment jiġi? 1156 00:41:28,260 --> 00:41:28,790 U għaliex? 1157 00:41:28,790 --> 00:41:30,550 X'inhu kejl n f'dak il-każ? 1158 00:41:30,550 --> 00:41:32,251 >> UDJENZA: [inaudible]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. Malan: Eżattament. 1160 00:41:33,250 --> 00:41:34,900 In-numru ta 'karattri irridu li jistampaw. 1161 00:41:34,900 --> 00:41:36,191 Allura huwa ħafna għall-kuntest sensittivi. 1162 00:41:36,191 --> 00:41:39,910 Illum, aħna kont qed jiffukaw ħafna fuq ittri u n-numri hawn fuq il-bord. 1163 00:41:39,910 --> 00:41:43,540 Iżda jista 'jkun ukoll karattri fi string attwali. 1164 00:41:43,540 --> 00:41:46,420 Għalhekk jirriżulta li hemm ieħor miżura li ser jibdew jieħdu ħsieb dwar, 1165 00:41:46,420 --> 00:41:48,530 u dak l-oppost ta O kbar, biex ngħidu hekk. 1166 00:41:48,530 --> 00:41:50,120 >> C'est notazzjoni omega. 1167 00:41:50,120 --> 00:41:53,380 Billi O big ifisser x'inhu, il- ta 'fuq marbutin fil-ħin running tiegħek? 1168 00:41:53,380 --> 00:41:55,580 Maximally, kemm ħin jista xi ħaġa tieħu? 1169 00:41:55,580 --> 00:41:59,250 Omega-- sorry dan jżomm ġejjin up-- huwa l-oppost ta 'dak, 1170 00:41:59,250 --> 00:42:02,960 li biha huwa rbit baxx fuq il- ammont ta 'xi ħaġa żmien tista' tieħu. 1171 00:42:02,960 --> 00:42:10,480 >> So. per eżempju, x'hemm algoriżmu li tieħu passi dejjem n kwadri? 1172 00:42:10,480 --> 00:42:15,600 Ukoll, wieħed mill-algoritmi Rajna illum, fil-fatt, jista 'jkun dak ukoll. 1173 00:42:15,600 --> 00:42:16,720 Sort għażla. 1174 00:42:16,720 --> 00:42:18,270 Għażla tip pjuttost stupid. 1175 00:42:18,270 --> 00:42:21,760 Anki jekk il-sorry algorithm--, anke jekk il-firxa hija diġà magħżula, 1176 00:42:21,760 --> 00:42:24,150 sort għażla se iżommu mixi permezz tal-lista 1177 00:42:24,150 --> 00:42:28,907 biex tiżgura li għandha l-iżgħar element ġdid u għal darb'oħra u għal darb'oħra. 1178 00:42:28,907 --> 00:42:31,740 U anki jekk inti bnedmin fil- udjenza taf li, stenna minuta, 1179 00:42:31,740 --> 00:42:33,948 inti diġà għadda mit- element iżgħar, il-kompjuter 1180 00:42:33,948 --> 00:42:37,300 ma jkunx jaf li sakemm jidher it-triq kollha permezz tal-lista. 1181 00:42:37,300 --> 00:42:40,240 Bl-istess mod, l-inqas limitu li jistgħu jittieħdu wkoll in kunsiderazzjoni 1182 00:42:40,240 --> 00:42:42,000 jista 'jkun żmien lineari. 1183 00:42:42,000 --> 00:42:48,260 >> Kif ħafna ħin ma jieħdu biex Elementi sort n fl-aħjar 1184 00:42:48,260 --> 00:42:52,420 każ li jużaw xi ħaġa bħal tip bużżieqa? 1185 00:42:52,420 --> 00:42:54,280 Ejja ngħidu lista tiegħek diġà magħżula. 1186 00:42:54,280 --> 00:42:56,696 Aħna qal sort bużżieqa jieħu fuq l-ordni ta 'n kwadrat passi. 1187 00:42:56,696 --> 00:42:59,640 Imma x'jiġri jekk huwa diġà magħżula? 1188 00:42:59,640 --> 00:43:02,310 X'jiġri jekk inti tirrealizza wara pass wieħed permezz tal-firxa 1189 00:43:02,310 --> 00:43:03,540 li inti ħadna l-ebda swaps? 1190 00:43:03,540 --> 00:43:05,970 Do ikollok bżonn li jżommu tagħmel aktar passes? 1191 00:43:05,970 --> 00:43:06,470 >> No 1192 00:43:06,470 --> 00:43:10,340 Allura Lower bound fuq sort bużżieqa jista 'jingħad li hija lineari. 1193 00:43:10,340 --> 00:43:11,830 Omega ta n. 1194 00:43:11,830 --> 00:43:14,450 U nistgħu nħarsu lejn oħrajn tagħhom kif ukoll. 1195 00:43:14,450 --> 00:43:17,990 Mela ejja tagħti ħarsa fi ftit viżwalizzazzjoni hawn 1196 00:43:17,990 --> 00:43:20,790 biex tara kif dawn jiddistingwu ruħhom. 1197 00:43:20,790 --> 00:43:24,592 Jien ser jinżlu hawn fis dan paġna li ikunu disponibbli fuq il-websajt C50, il 1198 00:43:24,592 --> 00:43:27,550 iżda se tkun uġigħ biex jiksbu xogħol, peress li juża teknoloġija msejħa 1199 00:43:27,550 --> 00:43:30,560 Applets Java, li hija aktar irfid dawn il-ġranet, 1200 00:43:30,560 --> 00:43:32,730 mill-inqas minn Chrome u biċċiet minnhom. 1201 00:43:32,730 --> 00:43:37,070 >> U let me jimxi 'l quddiem u jħaffu dan up u jispjegaw dak li għaddej. 1202 00:43:37,070 --> 00:43:40,840 Din hija turija ta 'bużżieqa sort, l-ewwel algoritmu ħarisna lejn. 1203 00:43:40,840 --> 00:43:43,950 U huwa viżwalizzazzjoni f'dak f'kull ta 'dawn il-vireg jirrappreżenta numru. 1204 00:43:43,950 --> 00:43:45,710 L-ikbar-bar, l-akbar il numru. 1205 00:43:45,710 --> 00:43:47,520 L-iżgħar bar, l-iżgħar in-numru. 1206 00:43:47,520 --> 00:43:50,353 U x'tista 'tara viżwalment, anke għalkemm dan se super fast, 1207 00:43:50,353 --> 00:43:53,699 hija li l-bar aħmar huwa simili me, mixi u lura iffissar problemi. 1208 00:43:53,699 --> 00:43:56,740 Tista 'tara li l-elementi akbar tabilħaqq tbaqbieq up lejn il-lemin, 1209 00:43:56,740 --> 00:43:59,650 u l-elementi iżgħar huma tbaqbieq sal-xellug. 1210 00:43:59,650 --> 00:44:01,870 U 'l isfel hawn, jekk aħna attwalment tħares aktar mill-qrib, 1211 00:44:01,870 --> 00:44:04,330 nistgħu ngħidu jgħoddu l- numru ta 'tqabbil u tpartit 1212 00:44:04,330 --> 00:44:05,350 li kienu qed isiru. 1213 00:44:05,350 --> 00:44:07,360 >> Iżda minflok, ejja nħarsu fit-tieni algoritmu 1214 00:44:07,360 --> 00:44:11,240 ħarisna lejn aktar kmieni ma 'tagħna voluntiera, sort għażla. 1215 00:44:11,240 --> 00:44:13,500 Viżwalment, hija għandha effett differenti ħafna. 1216 00:44:13,500 --> 00:44:16,820 Imma hija, għal darb'oħra, ħafna intuwittivi, fil li inżommu għażla li jmiss iżgħar 1217 00:44:16,820 --> 00:44:18,660 element, u aħna ltqajna ftit xxurtjati. 1218 00:44:18,660 --> 00:44:20,110 Li ħass fundamentalment aktar malajr. 1219 00:44:20,110 --> 00:44:22,840 Imma jekk irridu dam dan għal darb'oħra u darb'oħra u għal darb'oħra ma 'lottijiet ta' inputs, 1220 00:44:22,840 --> 00:44:26,680 aħna se tara li huwa tabilħaqq għadu fil O kbira ta 'n kwadrat. 1221 00:44:26,680 --> 00:44:29,920 >> Ejja nagħmlu aħħar wieħed wieħed hawn, sort inserzjoni, 1222 00:44:29,920 --> 00:44:33,180 li kienet it-tielet algoritmu ħarisna lejn, u recall 1223 00:44:33,180 --> 00:44:36,700 li dan wieħed jittratta l- Elementi għax jiltaqa lilhom, 1224 00:44:36,700 --> 00:44:39,290 iżda mbagħad forsi xiftijiet affarijiet fuq biex tagħmel spazju, 1225 00:44:39,290 --> 00:44:41,660 li jdaħħal elementi fejn huma jappartjenu. 1226 00:44:41,660 --> 00:44:45,330 >> U dan ukoll jispiċċa tagħti l- riżultat finali. Issa t-tliet dawk 1227 00:44:45,330 --> 00:44:46,490 ħass pretty fast. 1228 00:44:46,490 --> 00:44:48,740 U fil-fatt, I dam minnhom fuq clip pretty tajba. 1229 00:44:48,740 --> 00:44:52,510 Iżda fundamentalment, dawn qed kollha pretty horrible, li tkun onest. 1230 00:44:52,510 --> 00:44:56,960 Kollha ta 'dawn algoritmi s'issa li run fil O kbira ta 'n kwadrat 1231 00:44:56,960 --> 00:44:59,270 jieħu pjuttost ftit ta ' żmien jiddekorri fl-aħħar. 1232 00:44:59,270 --> 00:45:01,920 >> U fil-fatt, nistgħu naraw u jħossu dan fl-aħħar 1233 00:45:01,920 --> 00:45:04,090 jekk I pull up din it-tielet u l-aħħar demo. 1234 00:45:04,090 --> 00:45:05,840 Dan huwa pass ieħor viżwalizzazzjoni li għaddej 1235 00:45:05,840 --> 00:45:08,500 li juru sort bużżieqa fuq ix-xellug, sort għażla fin-nofs, 1236 00:45:08,500 --> 00:45:13,410 u xi ħaġa, bħala waħda mill tagħna naħa tqajjem qabel suġġerit, 1237 00:45:13,410 --> 00:45:15,020 jingħaqdu sort fuq il-lemin. 1238 00:45:15,020 --> 00:45:16,937 A firda u conquer istrateġija fuq il-lemin. 1239 00:45:16,937 --> 00:45:19,520 U li, fil-fatt, dak li aħna qed ser tħares lejn l-Erbgħa. 1240 00:45:19,520 --> 00:45:21,990 Imma ejja ħin dawn sabiex jimxu flimkien. 1241 00:45:21,990 --> 00:45:26,765 Huwa madwar l-istess numru ta ' elementi, kollha timxi fl-istess ħin. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble sort vs għażla sort vs sort jingħaqdu. 1244 00:45:34,440 --> 00:45:36,760 >> Issa, dawn qed kollha running fit-teorija fl-istess ħin. 1245 00:45:36,760 --> 00:45:39,830 Il-CPU tkun għaddejja bil l-istess veloċità, imma int 1246 00:45:39,830 --> 00:45:44,014 jistgħu jħossu kif boring dan huwa malajr ħafna se ssir, 1247 00:45:44,014 --> 00:45:45,930 u kemm malajr meta aħna tinjetta daqsxejn tal-ġimgħa 1248 00:45:45,930 --> 00:45:49,330 algoritmi żero jista aħna veloċità affarijiet up. 1249 00:45:49,330 --> 00:45:51,760 >> U issa ejja jqabblu dawn l-aħħar f forma waħda. 1250 00:45:51,760 --> 00:45:55,710 Jien ser jimxi 'l quddiem għall-websajt CS50, jekk ikun 1251 00:45:55,710 --> 00:45:59,020 għandna din ir-rabta finali għal-lum, fejn xi ħadd fuq l-internet 1252 00:45:59,020 --> 00:46:03,960 ġentilment jitqiegħdu flimkien video li jaqbad dak issortjar differenti 1253 00:46:03,960 --> 00:46:07,510 algoritmi ħoss bħal. 1254 00:46:07,510 --> 00:46:09,577 Dan huwa tip inserzjoni. 1255 00:46:09,577 --> 00:46:12,072 >> [Beeping] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Fejn inti qed tapplika frekwenza ibbażata fuq l-għoli tal-bar bar. 1258 00:46:16,850 --> 00:46:19,826 Dan huwa tip bubble. 1259 00:46:19,826 --> 00:46:21,822 >> [Beeping Warped] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Coming up jmiss is-- ġejjin up sort għażla is-- jmiss, 1262 00:46:45,774 --> 00:46:48,820 fejn għal darb'oħra, aħna qed jintgħażlu l-iżgħar element li jmiss, 1263 00:46:48,820 --> 00:46:51,820 u nistgħu naraw dan jikber mix-xellug għal-lemin. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Jingħaqdu sort, rebbieħ tagħna s'issa llum. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Avviż kif huwa diviż affarijiet fis [inaudible] nofs u kwartijiet. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Sort Gnome, li aħna ma tkellem dwar, u toħloq viżwalment 1270 00:47:21,660 --> 00:47:24,450 u audally daqsxejn ta ' forma u ħoss differenti. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Jmorru lura u 'l quddiem, tindif affarijiet up. 1273 00:47:30,160 --> 00:47:32,230 Wkoll check out heapsort fuq il-websajt dan Guy. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> U li hu. 1276 00:47:36,810 --> 00:47:38,210 Aħna se tara inti ħin li jmiss. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing U MUSIC] 1279 00:47:48,334 --> 00:50:24,839