1 00:00:00,000 --> 00:00:02,640 [Powered by Google Translate] [Semina: Ufundi Mahojiano] 2 00:00:02,640 --> 00:00:04,630 [Kenny Yu, Chuo Kikuu cha Harvard] 3 00:00:04,630 --> 00:00:08,910 [Hii ni CS50.] [CS50.TV] 4 00:00:08,910 --> 00:00:12,420 Hi kila mtu, mimi nina Kenny. I am sasa junior kusoma sayansi ya kompyuta. 5 00:00:12,420 --> 00:00:17,310 Mimi nina zamani CS TF, na mimi napenda alikuwa nilipokuwa underclassman, 6 00:00:17,310 --> 00:00:19,380 na kwamba sababu mimi nina kutoa semina hii. 7 00:00:19,380 --> 00:00:21,370 Hivyo Natumaini kufurahia. 8 00:00:21,370 --> 00:00:23,470 Semina hii ni kuhusu mahojiano ya kiufundi, 9 00:00:23,470 --> 00:00:26,650 na rasilimali yangu yote yanaweza kupatikana katika link hii, 10 00:00:26,650 --> 00:00:32,350 link hii hapa hapa, wanandoa wa rasilimali. 11 00:00:32,350 --> 00:00:36,550 Hivyo mimi alifanya orodha ya matatizo, kwa kweli, kabisa matatizo machache. 12 00:00:36,550 --> 00:00:40,800 Pia jumla ya rasilimali ukurasa ambapo tunaweza kupata tips 13 00:00:40,800 --> 00:00:42,870 juu ya jinsi ya kujiandaa kwa ajili ya mahojiano, 14 00:00:42,870 --> 00:00:46,470 vidokezo juu ya nini unatakiwa kufanya wakati wa mahojiano halisi, 15 00:00:46,470 --> 00:00:51,910 kama vile jinsi ya kukabili matatizo na rasilimali kwa ajili ya baadae. 16 00:00:51,910 --> 00:00:53,980 Ni wote online. 17 00:00:53,980 --> 00:00:58,290 Na tu kwa utangulizi semina hii, disclaimer, 18 00:00:58,290 --> 00:01:00,690 kama hii haipaswi - mahojiano yako maandalizi 19 00:01:00,690 --> 00:01:02,800 kusiishie tu kwa orodha hii. 20 00:01:02,800 --> 00:01:04,750 Hii ni tu maana ya kuwa kiongozi, 21 00:01:04,750 --> 00:01:08,890 na unapaswa dhahiri kuchukua kila kitu nasema pamoja na punje ya chumvi, 22 00:01:08,890 --> 00:01:14,620 lakini pia kutumia kila kitu mimi kutumika kukusaidia katika mahojiano maandalizi yako. 23 00:01:14,620 --> 00:01:16,400 >> Mimi nina kwenda kwa haraka kupitia slides michache ijayo 24 00:01:16,400 --> 00:01:18,650 ili tuweze kupata masomo halisi kesi. 25 00:01:18,650 --> 00:01:23,630 muundo wa mahojiano kwa postion uhandisi programu, 26 00:01:23,630 --> 00:01:26,320 kawaida ni dakika 30 hadi 45, 27 00:01:26,320 --> 00:01:29,810 nyingi raundi, kutegemea kampuni. 28 00:01:29,810 --> 00:01:33,090 Mara nyingi utasikia kuwa coding juu ya bodi nyeupe. 29 00:01:33,090 --> 00:01:35,960 Hivyo bodi nyeupe kama hii, lakini mara nyingi kwa kiwango kidogo. 30 00:01:35,960 --> 00:01:38,540 Kama wewe ni kuwa na mahojiano ya simu, pengine utasikia kutumia 31 00:01:38,540 --> 00:01:44,030 aidha collabedit au Doc Google ili waweze kuona mkiishi coding 32 00:01:44,030 --> 00:01:46,500 wakati wewe kuwa waliohojiwa juu ya simu. 33 00:01:46,500 --> 00:01:48,490 mahojiano yenyewe ni kawaida 2 au 3 matatizo 34 00:01:48,490 --> 00:01:50,620 kupima kompyuta yako sayansi maarifa. 35 00:01:50,620 --> 00:01:54,490 Na itakuwa karibu dhahiri kuhusisha coding. 36 00:01:54,490 --> 00:01:59,540 maswali ya aina hiyo utaona ni kawaida data miundo na algorithms. 37 00:01:59,540 --> 00:02:02,210 Na katika kufanya aina hii ya matatizo, 38 00:02:02,210 --> 00:02:07,830 watamwuliza wewe, kama, nini ni wakati na utata nafasi, kubwa O? 39 00:02:07,830 --> 00:02:09,800 Mara nyingi wao pia kuuliza maswali juu ya ngazi, 40 00:02:09,800 --> 00:02:12,530 hivyo, kubuni mfumo, 41 00:02:12,530 --> 00:02:14,770 jinsi gani unaweza kuweka nje code yako? 42 00:02:14,770 --> 00:02:18,370 Nini interfaces, kile madarasa, modules je, una katika mfumo wako, 43 00:02:18,370 --> 00:02:20,900 na jinsi gani haya kuingiliana pamoja? 44 00:02:20,900 --> 00:02:26,130 Hivyo data miundo na algorithms kama vile mifumo ya kubuni. 45 00:02:26,130 --> 00:02:29,180 >> Baadhi ya vidokezo ujumla kabla ya sisi kupiga mbizi katika kesi yetu masomo. 46 00:02:29,180 --> 00:02:32,300 Nadhani utawala muhimu zaidi ni daima kufikiri kwa sauti. 47 00:02:32,300 --> 00:02:36,980 mahojiano zinatakiwa kuwa nafasi yako ya kuonyesha mbali mawazo yako mchakato. 48 00:02:36,980 --> 00:02:39,820 hatua ya mahojiano ni kwa ajili ya mhojaji ili kupima 49 00:02:39,820 --> 00:02:42,660 jinsi wanafikiri na jinsi ya kwenda kwenye tatizo. 50 00:02:42,660 --> 00:02:45,210 Kitu mbaya unaweza kufanya ni kuwa kimya katika mahojiano nzima. 51 00:02:45,210 --> 00:02:50,090 Hiyo tu hakuna nzuri. 52 00:02:50,090 --> 00:02:53,230 Wakati wewe ni kupewa swali, wewe pia wanataka kuhakikisha unaelewa swali. 53 00:02:53,230 --> 00:02:55,350 Hivyo kurudia swali nyuma kwa maneno yako mwenyewe 54 00:02:55,350 --> 00:02:58,920 na jaribio la kazi ya uhakika chache kesi mtihani rahisi 55 00:02:58,920 --> 00:03:01,530 kuhakikisha unaelewa swali. 56 00:03:01,530 --> 00:03:05,510 Kufanya kazi kwa njia ya kesi chache mtihani pia kukupa Intuition juu ya jinsi ya kutatua tatizo hili. 57 00:03:05,510 --> 00:03:11,210 Unaweza hata kugundua ruwaza chache kukusaidia kutatua tatizo. 58 00:03:11,210 --> 00:03:14,500 Ncha yao kubwa ni si kupata frustrated. 59 00:03:14,500 --> 00:03:17,060 Je, si kupata frustrated. 60 00:03:17,060 --> 00:03:19,060 Mahojiano ni changamoto, lakini kitu mbaya unaweza kufanya, 61 00:03:19,060 --> 00:03:23,330 kwa kuongeza kuwa kimya, ni kuwa wazi imechanganyikiwa. 62 00:03:23,330 --> 00:03:27,410 Wewe hawataki kutoa hisia kwamba kwa mhojaji. 63 00:03:27,410 --> 00:03:33,960 Jambo moja kwamba - kwa hivyo, watu wengi, wakati wao kwenda katika mahojiano, 64 00:03:33,960 --> 00:03:37,150 wao kujaribu kujaribu kupata ufumbuzi bora ya kwanza, 65 00:03:37,150 --> 00:03:39,950 wakati kwa kweli, kuna kawaida ufumbuzi glaringly dhahiri. 66 00:03:39,950 --> 00:03:43,500 Inaweza kuwa polepole, inaweza kuwa ufanisi, lakini wewe lazima tu kueleza kuwa, 67 00:03:43,500 --> 00:03:46,210 hivyo tu una uhakika kuanzia ambayo kazi vizuri zaidi. 68 00:03:46,210 --> 00:03:48,270 Pia, akizungumzia nje ufumbuzi ni polepole, katika suala la 69 00:03:48,270 --> 00:03:52,160 kubwa O wakati utata au utata nafasi, 70 00:03:52,160 --> 00:03:54,450 itadhihirisha kwa mhojaji kwamba kuelewa 71 00:03:54,450 --> 00:03:57,510 masuala haya wakati wa kuandika code. 72 00:03:57,510 --> 00:04:01,440 Kwa hiyo msiwe na hofu ya kuja na algorithm rahisi kwanza 73 00:04:01,440 --> 00:04:04,950 na kisha kazi bora kutoka huko. 74 00:04:04,950 --> 00:04:09,810 Maswali yoyote hadi sasa? Sawa. 75 00:04:09,810 --> 00:04:11,650 >> Hivyo hebu kupiga mbizi katika tatizo letu kwanza. 76 00:04:11,650 --> 00:04:14,790 "Kutokana na safu ya integers n, kuandika kazi kwamba shuffles safu 77 00:04:14,790 --> 00:04:20,209 katika mahali vile kwamba permutations wote wa integers n wana uwezekano sawa. " 78 00:04:20,209 --> 00:04:23,470 Na kudhani kuwa inapatikana random integer jenereta 79 00:04:23,470 --> 00:04:30,980 kwamba inazalisha integer katika mbalimbali kutoka 0 kwa i, nusu mbalimbali. 80 00:04:30,980 --> 00:04:32,970 Je, kila mtu kuelewa swali hili? 81 00:04:32,970 --> 00:04:39,660 Mimi kukupa safu ya integers n, na Mimi nataka wewe shuffle yake. 82 00:04:39,660 --> 00:04:46,050 Katika orodha yangu, mimi aliandika programu chache kuonyesha namaanisha nini. 83 00:04:46,050 --> 00:04:48,910 Mimi naenda shuffle safu ya vipengele 20, 84 00:04:48,910 --> 00:04:52,490 kutoka -10 hadi 9, 85 00:04:52,490 --> 00:04:57,050 na mimi nataka wewe pato orodha kama hii. 86 00:04:57,050 --> 00:05:02,890 Hivyo hii ni pembejeo yangu sorted safu, na Mimi nataka wewe shuffle yake. 87 00:05:02,890 --> 00:05:07,070 Tutaweza kufanya hivyo tena. 88 00:05:07,070 --> 00:05:13,780 Je, kila mtu kuelewa swali? Sawa. 89 00:05:13,780 --> 00:05:16,730 Hivyo ni juu yako. 90 00:05:16,730 --> 00:05:21,220 Nini ni baadhi ya mawazo? Je, unaweza kufanya hivyo kama n ^ 2, n logi n, n? 91 00:05:21,220 --> 00:05:34,400 Fungua kwa mapendekezo. 92 00:05:34,400 --> 00:05:37,730 Sawa. Hivyo wazo moja, alipendekeza kwa Emmy, 93 00:05:37,730 --> 00:05:45,300 ni ya kwanza compute random idadi, random integer, katika mbalimbali 0-20. 94 00:05:45,300 --> 00:05:49,840 Hivyo kudhani safu yetu ina urefu wa 20. 95 00:05:49,840 --> 00:05:54,800 Katika mchoro wetu wa mambo ya 20, 96 00:05:54,800 --> 00:05:58,560 hii ni pembejeo yetu safu. 97 00:05:58,560 --> 00:06:04,590 Na sasa, pendekezo lake ni kujenga safu mpya, 98 00:06:04,590 --> 00:06:08,440 hivyo hii itakuwa safu pato. 99 00:06:08,440 --> 00:06:12,880 Na msingi i akarudi na rand - 100 00:06:12,880 --> 00:06:17,580 hivyo kama i alikuwa, hebu sema, 17, 101 00:06:17,580 --> 00:06:25,640 nakala ya kipengele 17 katika nafasi ya kwanza. 102 00:06:25,640 --> 00:06:30,300 Sasa sisi haja ya kufuta - tunahitaji kuhama vipengele vyote hapa 103 00:06:30,300 --> 00:06:36,920 juu ya hivyo kwamba tuna pengo mwishoni na mashimo hakuna katikati. 104 00:06:36,920 --> 00:06:39,860 Na sasa sisi kurudia utaratibu. 105 00:06:39,860 --> 00:06:46,360 Sasa sisi kuchukua mpya random integer kati ya 0 na 19. 106 00:06:46,360 --> 00:06:52,510 Tuna i mpya hapa, na sisi nakala hii ya kipengele katika nafasi hii. 107 00:06:52,510 --> 00:07:00,960 Kisha sisi kuhama vitu zaidi na sisi kurudia mchakato mpaka tuna mpya wetu kamili safu. 108 00:07:00,960 --> 00:07:05,890 Je, ni wakati wa kukimbia algorithm hii? 109 00:07:05,890 --> 00:07:08,110 Naam, hebu kuangalia matokeo ya. 110 00:07:08,110 --> 00:07:10,380 Sisi ni shifting kila kipengele. 111 00:07:10,380 --> 00:07:16,800 Wakati sisi kuondoa hii i, sisi ni shifting vipengele vyote baada ya upande wa kushoto. 112 00:07:16,800 --> 00:07:21,600 Na kwamba ni O (n) gharama 113 00:07:21,600 --> 00:07:26,100 kwa sababu nini kama sisi kuondoa kipengele kwanza? 114 00:07:26,100 --> 00:07:29,670 Hivyo kwa ajili ya kuondolewa kila, sisi kuondoa - 115 00:07:29,670 --> 00:07:32,170 kuondolewa kila incurs O (n) operesheni, 116 00:07:32,170 --> 00:07:41,520 na tangu tuna n removals, hii hupelekea shuffle O (n ^ 2). 117 00:07:41,520 --> 00:07:49,550 Sawa. Hivyo nzuri kuanza. Nzuri ya kuanza. 118 00:07:49,550 --> 00:07:55,290 >> Pendekezo lingine ni kutumia kitu inayojulikana kama shuffle Knuth, 119 00:07:55,290 --> 00:07:57,540 au shuffle Fisher-Yates. 120 00:07:57,540 --> 00:07:59,630 Na ni kweli linear wakati shuffle. 121 00:07:59,630 --> 00:08:02,200 Na wazo ni sawa sana. 122 00:08:02,200 --> 00:08:05,160 Tena, tuna mchango wetu safu, 123 00:08:05,160 --> 00:08:08,580 lakini badala ya kutumia arrays mbili kwa ajili ya pembejeo wetu / pato, 124 00:08:08,580 --> 00:08:13,590 sisi kutumia sehemu ya kwanza ya safu ya kuweka wimbo wa sehemu yetu huchanganywa, 125 00:08:13,590 --> 00:08:18,400 na sisi kuweka wimbo, na kisha sisi kuacha wengine wa safu yetu kwa ajili ya sehemu unshuffled. 126 00:08:18,400 --> 00:08:24,330 Hivyo hapa ni nini namaanisha. Sisi kuanza mbali na - sisi kuchagua i, 127 00:08:24,330 --> 00:08:30,910 safu 0-20. 128 00:08:30,910 --> 00:08:36,150 Pointer wetu wa sasa ni akizungumzia index kwanza. 129 00:08:36,150 --> 00:08:39,590 Sisi kuchagua baadhi hapa i 130 00:08:39,590 --> 00:08:42,740 na sasa sisi wabadilishane. 131 00:08:42,740 --> 00:08:47,690 Hivyo kama hii ilikuwa 5 na hii ilikuwa 4, 132 00:08:47,690 --> 00:08:57,150 safu kusababisha itakuwa na 5 hapa na 4 hapa. 133 00:08:57,150 --> 00:09:00,390 Na sasa tunaona marker hapa. 134 00:09:00,390 --> 00:09:05,770 Kila kitu kwa upande wa kushoto ni huchanganywa, 135 00:09:05,770 --> 00:09:15,160 na kila kitu kwa kulia unshuffled. 136 00:09:15,160 --> 00:09:17,260 Na sasa tunaweza kurudia utaratibu. 137 00:09:17,260 --> 00:09:25,210 Sisi kuchagua index random kati ya 1 na 20 sasa. 138 00:09:25,210 --> 00:09:30,650 Hivyo kudhani wetu mpya i ni hapa. 139 00:09:30,650 --> 00:09:39,370 Sasa sisi byta hii i na msimamo wetu wa sasa mpya hapa. 140 00:09:39,370 --> 00:09:44,790 Hivyo hatujui swapping na kurudi kama hii. 141 00:09:44,790 --> 00:09:51,630 Hebu kuleta code kufanya hivyo zaidi zege. 142 00:09:51,630 --> 00:09:55,290 Tunaweza kuanza na uchaguzi wetu wa i - 143 00:09:55,290 --> 00:09:58,370 sisi kuanza na i sawa na 0, tunachukua random mahali j 144 00:09:58,370 --> 00:10:02,420 katika sehemu unshuffled wa safu, i kwa n-1. 145 00:10:02,420 --> 00:10:07,280 Basi, ikiwa mimi niko hapa, kuchagua kati ya index random hapa na wengine wa safu, 146 00:10:07,280 --> 00:10:12,410 na sisi wabadilishane. 147 00:10:12,410 --> 00:10:17,550 Hii ni kanuni zote muhimu shuffle safu yako. 148 00:10:17,550 --> 00:10:21,670 Maswali yoyote? 149 00:10:21,670 --> 00:10:25,530 >> Naam, mmoja zinahitajika swali ni, kwa nini hili ni sahihi? 150 00:10:25,530 --> 00:10:28,360 Kwa nini ni kila permutation uwezekano sawa? 151 00:10:28,360 --> 00:10:30,410 Na mimi si kwenda kwa njia ya ushahidi wa hili, 152 00:10:30,410 --> 00:10:35,970 lakini matatizo mengi katika sayansi ya kompyuta inaweza kuthibitika kwa njia ya introduktionsutbildning. 153 00:10:35,970 --> 00:10:38,520 Jinsi wengi wewe ni ukoo na introduktionsutbildning? 154 00:10:38,520 --> 00:10:40,590 Sawa. Cool. 155 00:10:40,590 --> 00:10:43,610 Hivyo unaweza kuthibitisha usahihi wa algorithm hili kwa introduktionsutbildning rahisi, 156 00:10:43,610 --> 00:10:49,540 ambapo introduktionsutbildning yako hypothesis itakuwa, kudhani kuwa 157 00:10:49,540 --> 00:10:53,290 Shuffle yangu anarudi kila permutation uwezekano sawa 158 00:10:53,290 --> 00:10:56,120 hadi kwanza i vipengele. 159 00:10:56,120 --> 00:10:58,300 Sasa, fikiria i + 1. 160 00:10:58,300 --> 00:11:02,550 Na kwa njia ya sisi kuchagua index yetu j wabadilishane, 161 00:11:02,550 --> 00:11:05,230 hii husababisha - na kisha kazi nje maelezo, 162 00:11:05,230 --> 00:11:07,390 angalau ushahidi kamili ya nini algorithm hili hurejea 163 00:11:07,390 --> 00:11:12,800 kila permutation na uwezekano uwezekano sawa. 164 00:11:12,800 --> 00:11:15,940 >> Haki ya wote, karibu tatizo. 165 00:11:15,940 --> 00:11:19,170 Hivyo "kupewa safu ya integers, postive, sifuri, hasi, 166 00:11:19,170 --> 00:11:21,290 kuandika kazi ambayo inakokotoa Jumla upeo 167 00:11:21,290 --> 00:11:24,720 yoyote subarray continueous wa safu pembejeo. " 168 00:11:24,720 --> 00:11:28,370 mfano hapa ni, katika kesi ambapo wote idadi ni chanya, 169 00:11:28,370 --> 00:11:31,320 basi sasa chaguo bora ni kuchukua safu nzima. 170 00:11:31,320 --> 00:11:34,690 1, 2, 3, 4, sawa na 10. 171 00:11:34,690 --> 00:11:36,780 Wakati una baadhi negatives huko, 172 00:11:36,780 --> 00:11:38,690 katika kesi hii sisi tu wanataka mbili kwanza 173 00:11:38,690 --> 00:11:44,590 kwa sababu kuchagua -1 na / au -3 ataleta Jumla yetu chini. 174 00:11:44,590 --> 00:11:48,120 Wakati mwingine sisi tupate kuwa na kuanza katikati ya safu. 175 00:11:48,120 --> 00:11:53,500 Wakati mwingine tunataka kuchagua kitu; ni bora si kuchukua kitu chochote. 176 00:11:53,500 --> 00:11:56,490 Na wakati mwingine ni bora kuchukua kuanguka, 177 00:11:56,490 --> 00:12:07,510 sababu jambo baada ya ni super kubwa. Hivyo mawazo yoyote? 178 00:12:07,510 --> 00:12:10,970 (Mwanafunzi, unintelligible) >> Yeah. 179 00:12:10,970 --> 00:12:13,560 Tuseme mimi wala kuchukua -1. 180 00:12:13,560 --> 00:12:16,170 Basi ama mimi kuchagua 1000 na 20,000, 181 00:12:16,170 --> 00:12:18,630 au mimi tu kuchagua bilioni 3. 182 00:12:18,630 --> 00:12:20,760 Naam, chaguo bora ni kuchukua namba zote. 183 00:12:20,760 --> 00:12:24,350 Hii -1, licha ya kuwa hasi, 184 00:12:24,350 --> 00:12:31,340 Jumla zima ni bora kuliko walikuwa mimi si kuchukua -1. 185 00:12:31,340 --> 00:12:36,460 Basi mmoja wa tips nilivyoeleza awali ilikuwa kueleza wazi wazi 186 00:12:36,460 --> 00:12:40,540 na nguvu brute ufumbuzi kwanza. 187 00:12:40,540 --> 00:12:44,340 Je, ni nguvu brute ufumbuzi katika tatizo hili? Yeah? 188 00:12:44,340 --> 00:12:46,890 [Jane] Vizuri, nadhani brute nguvu ufumbuzi 189 00:12:46,890 --> 00:12:52,600 itakuwa na kuongeza hadi mchanganyiko wote inawezekana (unintelligible). 190 00:12:52,600 --> 00:12:58,250 [Yu] Sawa. Hivyo wazo Jane ni kuchukua kila iwezekanavyo - 191 00:12:58,250 --> 00:13:01,470 Mimi nina kufafanua - ni kuchukua kila iwezekanavyo kuendelea subarray, 192 00:13:01,470 --> 00:13:07,840 compute Jumla yake, na kisha kuchukua upeo wa subarrays wote inawezekana kuendelea. 193 00:13:07,840 --> 00:13:13,310 Nini kipekee kubainisha subarray katika pembejeo safu yangu? 194 00:13:13,310 --> 00:13:17,380 Kama, nini mambo mawili Ninahitaji? Yeah? 195 00:13:17,380 --> 00:13:19,970 (Mwanafunzi, unintelligible) >> Haki. 196 00:13:19,970 --> 00:13:22,130 chini amefungwa juu ya index na juu amefungwa index 197 00:13:22,130 --> 00:13:28,300 kipekee huamua subarray kuendelea. 198 00:13:28,300 --> 00:13:31,400 [Kike mwanafunzi] Je, sisi kukadiria ni safu ya idadi ya kipekee? 199 00:13:31,400 --> 00:13:34,280 [Yu] No Hivyo swali lake, ni sisi kuchukua safu yetu - 200 00:13:34,280 --> 00:13:39,000 ni safu zetu zote idadi ya kipekee, na jibu ni hapana. 201 00:13:39,000 --> 00:13:43,390 >> Kama sisi kutumia nguvu zetu brute ufumbuzi, basi fahirisi kuanza / mwisho 202 00:13:43,390 --> 00:13:47,200 kipekee huamua subarray wetu kuendelea. 203 00:13:47,200 --> 00:13:51,680 Hivyo kama sisi iterate kwa entries wote inawezekana kuanza, 204 00:13:51,680 --> 00:13:58,320 na kwa entries mwisho wote> au = kuanza, na 00:14:05,570 wewe compute jumla, na kisha sisi kuchukua Jumla upeo tumeona mpaka sasa. 206 00:14:05,570 --> 00:14:07,880 Je, hii ni wazi? 207 00:14:07,880 --> 00:14:12,230 Nini ni O kubwa ya ufumbuzi huu? 208 00:14:12,230 --> 00:14:16,660 Timewise. 209 00:14:16,660 --> 00:14:18,860 Si kabisa n ^ 2. 210 00:14:18,860 --> 00:14:25,250 Kumbuka kwamba sisi iterate kutoka 0 kwa n, 211 00:14:25,250 --> 00:14:27,520 hivyo kwamba moja kwa kitanzi. 212 00:14:27,520 --> 00:14:35,120 Sisi iterate tena kutoka karibu mwanzo hadi mwisho, mwingine kwa kitanzi. 213 00:14:35,120 --> 00:14:37,640 Na sasa, ndani ya kwamba, tuna jumla juu ya kila kuingia, 214 00:14:37,640 --> 00:14:43,810 ili mwingine kwa kitanzi. Hivyo tuna tatu nested kwa tanzi, n ^ 3. 215 00:14:43,810 --> 00:14:46,560 Sawa. Hii inakwenda kama kianzio. 216 00:14:46,560 --> 00:14:53,180 Ufumbuzi yetu ni mbaya zaidi kuliko hakuna n ^ 3. 217 00:14:53,180 --> 00:14:55,480 Je, kila mtu kuelewa brute nguvu ufumbuzi? 218 00:14:55,480 --> 00:14:59,950 >> Sawa. ufumbuzi bora ni kutumia wazo kuitwa nguvu programu. 219 00:14:59,950 --> 00:15:03,040 Kama wewe kuchukua CS124, ambayo ni Algorithms na Miundo Data, 220 00:15:03,040 --> 00:15:05,680 utakuwa familiar sana na mbinu hii. 221 00:15:05,680 --> 00:15:12,190 Na wazo, kujaribu kujenga ufumbuzi wa matatizo madogo ya kwanza. 222 00:15:12,190 --> 00:15:17,990 Nini maana na hii ni, sisi sasa kuwa na wasiwasi juu ya mambo mawili: mwanzo na mwisho. 223 00:15:17,990 --> 00:15:29,340 Na kwamba ni annoying. Nini kama tunaweza kujikwamua moja ya vigezo wale? 224 00:15:29,340 --> 00:15:32,650 Moja wazo ni - we're aliyopewa tatizo yetu ya awali, 225 00:15:32,650 --> 00:15:37,470 Jumla kupata upeo wa yoyote katika subarray mbalimbali [O, n-1]. 226 00:15:37,470 --> 00:15:47,400 Na sasa tuna subproblem mpya, ambapo tunajua, katika ripoti yetu ya sasa i, 227 00:15:47,400 --> 00:15:52,520 tunajua lazima kuhitimisha huko. Subarray yetu lazima mwisho katika index sasa. 228 00:15:52,520 --> 00:15:57,640 Hivyo tatizo iliyobaki ni, ambapo tunapaswa kuanza subarray yetu? 229 00:15:57,640 --> 00:16:05,160 Je, hii mantiki? Sawa. 230 00:16:05,160 --> 00:16:12,030 Hivyo nimekuwa coded hii juu, na hebu tuangalie nini maana ya hii. 231 00:16:12,030 --> 00:16:16,230 Katika codirectory, kuna programu inayoitwa subarray, 232 00:16:16,230 --> 00:16:19,470 na inachukua idadi ya vitu, 233 00:16:19,470 --> 00:16:25,550 na kuirudisha maximal subarray Jumla katika orodha yangu huchanganywa. 234 00:16:25,550 --> 00:16:29,920 Hivyo katika kesi hii, subarray wetu maximal ni 3. 235 00:16:29,920 --> 00:16:34,850 Na hiyo kuchukuliwa na kutumia tu 2 na 1. 236 00:16:34,850 --> 00:16:38,050 Hebu kukimbia tena. Ni pia 3. 237 00:16:38,050 --> 00:16:40,950 Lakini wakati huu, tambua jinsi sisi got 3. 238 00:16:40,950 --> 00:16:46,690 Sisi alichukua - sisi tu kuchukua 3 yenyewe 239 00:16:46,690 --> 00:16:49,980 sababu ni kuzungukwa na negatives pande zote mbili, 240 00:16:49,980 --> 00:16:55,080 ambayo kuleta Jumla <3. 241 00:16:55,080 --> 00:16:57,820 Hebu kukimbia juu ya vitu 10. 242 00:16:57,820 --> 00:17:03,200 Wakati huu ni 7, sisi kuchukua 3 kuongoza na 4. 243 00:17:03,200 --> 00:17:09,450 Wakati huu ni 8, na sisi kupata kwamba kwa kuchukua 1, 4 na 3. 244 00:17:09,450 --> 00:17:16,310 Hivyo kukupa Intuition juu ya jinsi gani tunaweza kutatua tatizo hili kubadilishwa, 245 00:17:16,310 --> 00:17:18,890 hebu tuangalie subarray hii. 246 00:17:18,890 --> 00:17:23,460 Sisi ni kupewa hii safu ya pembejeo, na tunajua jibu ni 8. 247 00:17:23,460 --> 00:17:26,359 Sisi kuchukua 1, 4, na 3. 248 00:17:26,359 --> 00:17:29,090 Lakini hebu tuangalie jinsi sisi kweli got kuwa jibu. 249 00:17:29,090 --> 00:17:34,160 Hebu tuangalie subarray maximal kumalizika katika kila moja ya fahirisi hizi. 250 00:17:34,160 --> 00:17:40,780 Nini subarray maximal ambayo ina kumaliza katika nafasi ya kwanza? 251 00:17:40,780 --> 00:17:46,310 [Mwanafunzi] Sifuri. >> Zero. Tu wala kuchukua -5. 252 00:17:46,310 --> 00:17:50,210 Hapa ni kwenda kuwa 0 vilevile. Yeah? 253 00:17:50,210 --> 00:17:56,470 (Mwanafunzi, unintelligible) 254 00:17:56,470 --> 00:17:58,960 [Yu] Oh, sorry, ni -3. 255 00:17:58,960 --> 00:18:03,220 Hivyo hii ni 2, hii ni -3. 256 00:18:03,220 --> 00:18:08,690 Sawa. Hivyo -4, nini subarray maximal kukomesha kwamba nafasi 257 00:18:08,690 --> 00:18:12,910 ambapo -4 ni saa? Zero. 258 00:18:12,910 --> 00:18:22,570 Moja? 1, 5, 8. 259 00:18:22,570 --> 00:18:28,060 Sasa, mimi lazima mwisho katika eneo ambapo -2 ni saa. 260 00:18:28,060 --> 00:18:39,330 Hivyo 6, 5, 7, na moja ya mwisho ni 4. 261 00:18:39,330 --> 00:18:43,480 Kujua kwamba haya ni entries yangu 262 00:18:43,480 --> 00:18:48,130 kwa tatizo kubadilishwa ambapo mimi lazima mwisho katika kila moja ya fahirisi hizi, 263 00:18:48,130 --> 00:18:51,410 basi jibu langu la mwisho ni wa haki, kuchukua zoa hela, 264 00:18:51,410 --> 00:18:53,580 na kuchukua idadi ya juu. 265 00:18:53,580 --> 00:18:55,620 Hivyo katika kesi hii ni 8. 266 00:18:55,620 --> 00:19:00,010 Hii ina maana kwamba subarray maximal inaishia katika index hii, 267 00:19:00,010 --> 00:19:04,970 na kuanza mahali fulani mbele yake. 268 00:19:04,970 --> 00:19:09,630 Je, kila mtu kuelewa hili subarray kubadilishwa? 269 00:19:09,630 --> 00:19:22,160 >> Sawa. Naam, hebu takwimu nje upprepning kwa hili. 270 00:19:22,160 --> 00:19:27,990 Hebu fikiria tu kwanza entries chache. 271 00:19:27,990 --> 00:19:35,930 Hivyo hapa ilikuwa 0, 0, 0, 1, 5, 8. 272 00:19:35,930 --> 00:19:39,790 Na kisha kulikuwa -2 hapa, na kwamba kuletwa ni chini ya 6. 273 00:19:39,790 --> 00:19:50,800 Hivyo kama mimi wito kuingia katika nafasi i subproblem (i), 274 00:19:50,800 --> 00:19:54,910 jinsi gani naweza kutumia jibu subproblem uliopita 275 00:19:54,910 --> 00:19:59,360 kujibu hii subproblem? 276 00:19:59,360 --> 00:20:04,550 Kama mimi kuangalia, hebu sema, kuingia hii. 277 00:20:04,550 --> 00:20:09,190 Ninawezaje compute jibu 6 kwa kuangalia 278 00:20:09,190 --> 00:20:18,780 mchanganyiko wa safu hii na majibu ya subproblems uliopita katika safu hii? Ndiyo? 279 00:20:18,780 --> 00:20:22,800 [Kike mwanafunzi] Wewe kuchukua safu ya maswali 280 00:20:22,800 --> 00:20:25,430 katika nafasi ya haki mbele yake, hivyo 8, 281 00:20:25,430 --> 00:20:32,170 na kisha kuongeza subproblem sasa. 282 00:20:32,170 --> 00:20:36,460 [Yu] Basi pendekezo lake ni kuangalia namba hizi mbili, 283 00:20:36,460 --> 00:20:40,090 idadi hii na idadi hii. 284 00:20:40,090 --> 00:20:50,130 Hivyo hii 8 inahusu jibu kwa subproblem (i - 1). 285 00:20:50,130 --> 00:20:57,300 Na hebu piga pembejeo yangu safu A. 286 00:20:57,300 --> 00:21:01,470 Ili kupata subarray maximal kwamba mwisho katika msimamo i, 287 00:21:01,470 --> 00:21:03,980 Nina maamuzi mawili: Mimi wanaweza ama kuendelea subarray 288 00:21:03,980 --> 00:21:09,790 kwamba kumalizika saa index uliopita, au kuanza safu mpya. 289 00:21:09,790 --> 00:21:14,190 Kama ningekuwa na kuendelea subarray ambayo ilianza katika index uliopita, 290 00:21:14,190 --> 00:21:19,260 kisha Jumla upeo naweza kufikia ni jibu kwa subproblem uliopita 291 00:21:19,260 --> 00:21:24,120 plus sasa safu ya kuingia. 292 00:21:24,120 --> 00:21:27,550 Lakini, mimi pia kuwa na uchaguzi wa kuanzia subarray mpya, 293 00:21:27,550 --> 00:21:30,830 katika kesi ambayo Jumla ni 0. 294 00:21:30,830 --> 00:21:42,860 Hivyo jibu ni max ya 0, subproblem i - 1, plus sasa kuingia safu. 295 00:21:42,860 --> 00:21:46,150 Je upprepning hii mantiki? 296 00:21:46,150 --> 00:21:50,840 Upprepning yetu, kama sisi tu kugundua, ni subproblem i 297 00:21:50,840 --> 00:21:54,740 ni sawa na upeo wa subproblem uliopita plus kuingia yangu ya sasa safu, 298 00:21:54,740 --> 00:22:01,490 ambayo ina maana ya kuendelea subarray uliopita, 299 00:22:01,490 --> 00:22:07,250 au 0, kuanza subarray mpya katika index yangu ya sasa. 300 00:22:07,250 --> 00:22:10,060 Na mara moja tumejenga hii meza ya ufumbuzi, basi jibu wetu wa mwisho, 301 00:22:10,060 --> 00:22:13,950 tu kufanya zoa linear hela safu subproblem 302 00:22:13,950 --> 00:22:19,890 na kuchukua idadi ya juu. 303 00:22:19,890 --> 00:22:23,330 Hii ni utekelezaji kamili ya kile tu alisema. 304 00:22:23,330 --> 00:22:27,320 Hivyo sisi kujenga mpya subproblem safu, subproblems. 305 00:22:27,320 --> 00:22:32,330 kwanza kuingia ni aidha 0 au ya kwanza kuingia, upeo wa wale wawili. 306 00:22:32,330 --> 00:22:35,670 Na kwa ajili ya mapumziko ya subproblems 307 00:22:35,670 --> 00:22:39,810 sisi kutumia upprepning halisi sisi kirahisi tu. 308 00:22:39,810 --> 00:22:49,960 Sasa sisi compute upeo wa safu yetu subproblems, na kwamba jibu yetu ya mwisho. 309 00:22:49,960 --> 00:22:54,130 >> Hivyo muda kiasi gani ni sisi kutumia katika algorithm hii? 310 00:22:54,130 --> 00:23:01,470 Kama ve tu kuchukuliwa CS50, basi unaweza kuwa kujadiliwa nafasi sana. 311 00:23:01,470 --> 00:23:07,750 Naam, jambo moja kukumbuka ni kwamba mimi kuitwa malloc hapa na n kawaida. 312 00:23:07,750 --> 00:23:13,590 Gani zinaonyesha kwamba na wewe? 313 00:23:13,590 --> 00:23:17,450 Algorithm hii inatumia nafasi linear. 314 00:23:17,450 --> 00:23:21,030 Je, tunaweza kufanya vizuri zaidi? 315 00:23:21,030 --> 00:23:30,780 Je, kuna kitu utaona kwamba ni unnecessary kwa compute jibu la mwisho? 316 00:23:30,780 --> 00:23:33,290 Nadhani swali bora ni, nini habari 317 00:23:33,290 --> 00:23:40,680 je, sisi si haja ya kubeba njia yote hadi mwisho? 318 00:23:40,680 --> 00:23:44,280 Sasa, kama sisi kuangalia mistari hii miwili, 319 00:23:44,280 --> 00:23:47,720 sisi tu huduma ya juu subproblem uliopita, 320 00:23:47,720 --> 00:23:50,910 na sisi tu huduma kuhusu upeo tumekuwa milele kuona hadi sasa. 321 00:23:50,910 --> 00:23:53,610 Compute jibu letu la mwisho, sisi hatuhitaji safu nzima. 322 00:23:53,610 --> 00:23:57,450 Tunahitaji tu namba ya mwisho, mwisho namba mbili. 323 00:23:57,450 --> 00:24:02,630 Mwisho idadi kwa safu subproblem, na namba ya mwisho kwa upeo. 324 00:24:02,630 --> 00:24:07,380 Hivyo, kwa kweli, tunaweza Fuse matanzi hizi pamoja 325 00:24:07,380 --> 00:24:10,460 na kwenda kutoka nafasi linear nafasi ya mara kwa mara. 326 00:24:10,460 --> 00:24:15,830 Hali Jumla hadi sasa, hapa, nafasi nafasi ya subproblem, subproblem yetu safu. 327 00:24:15,830 --> 00:24:20,020 Hivyo sasa jumla, hadi sasa, ni jibu kwa subproblem uliopita. 328 00:24:20,020 --> 00:24:23,450 Jumla na kwamba, hadi sasa, unafanyika ya max yetu. 329 00:24:23,450 --> 00:24:28,100 Sisi compute upeo kama sisi kwenda pamoja. 330 00:24:28,100 --> 00:24:30,890 Na hivyo sisi kwenda kutoka nafasi linear nafasi ya mara kwa mara, 331 00:24:30,890 --> 00:24:36,650 na sisi pia kuwa na ufumbuzi linear subarray tatizo letu. 332 00:24:36,650 --> 00:24:40,740 >> Hizi aina ya maswali utapata wakati wa mahojiano. 333 00:24:40,740 --> 00:24:44,450 Je, ni utata wakati; ni nini utata nafasi? 334 00:24:44,450 --> 00:24:50,600 Je, unaweza kufanya vizuri? Je, kuna mambo ambayo ni lazima kuweka kote? 335 00:24:50,600 --> 00:24:55,270 Mimi alifanya hivyo kuonyesha kwamba uchambuzi unapaswa kuchukua juu yako mwenyewe 336 00:24:55,270 --> 00:24:57,400 kama wewe ni kufanya kazi kwa njia ya matatizo haya. 337 00:24:57,400 --> 00:25:01,710 Daima kuwa na kuuliza wewe mwenyewe, "Naweza kufanya vizuri?" 338 00:25:01,710 --> 00:25:07,800 Kwa kweli, tunaweza kufanya vizuri zaidi kuliko haya? 339 00:25:07,800 --> 00:25:10,730 Aina ya swali hila. Huwezi, kwa sababu unahitaji 340 00:25:10,730 --> 00:25:13,590 angalau kusoma pembejeo kwa tatizo. 341 00:25:13,590 --> 00:25:15,570 Hivyo ukweli kwamba unahitaji angalau kusoma pembejeo kwa tatizo 342 00:25:15,570 --> 00:25:19,580 ina maana kwamba huwezi kufanya vizuri zaidi kuliko wakati linear, 343 00:25:19,580 --> 00:25:22,870 na huwezi kufanya vizuri zaidi kuliko nafasi ya mara kwa mara. 344 00:25:22,870 --> 00:25:27,060 Hivyo hii ni, kwa kweli, ufumbuzi bora wa tatizo hili. 345 00:25:27,060 --> 00:25:33,040 Maswali? Sawa. 346 00:25:33,040 --> 00:25:35,190 >> Hisa soko tatizo: 347 00:25:35,190 --> 00:25:38,350 "Kutokana na safu ya integers n, chanya, sifuri, au hasi, 348 00:25:38,350 --> 00:25:41,680 kwamba kuwakilisha bei ya hisa zaidi ya siku n, 349 00:25:41,680 --> 00:25:44,080 kuandika kazi kwa compute faida upeo unaweza kufanya 350 00:25:44,080 --> 00:25:49,350 kutokana na kwamba unaweza kununua na kuuza hasa 1 hisa ndani ya siku hizi n. " 351 00:25:49,350 --> 00:25:51,690 Kimsingi, tunataka kununua chini, kuuza high. 352 00:25:51,690 --> 00:25:58,580 Na tunataka takwimu nje faida bora tunaweza kufanya. 353 00:25:58,580 --> 00:26:11,500 Tukirudi kwenye ncha wangu, ni nini mara moja wazi, rahisi jibu, lakini ni polepole? 354 00:26:11,500 --> 00:26:17,690 Ndiyo? (Mwanafunzi, unintelligible) >> Ndiyo. 355 00:26:17,690 --> 00:26:21,470 >> Hivyo ingekuwa tu kwenda ingawa na kuangalia bei ya hisa 356 00:26:21,470 --> 00:26:30,550 katika kila hatua katika wakati, (unintelligible). 357 00:26:30,550 --> 00:26:33,990 [Yu] Sawa, hivyo ufumbuzi wake - pendekezo yake ya kompyuta 358 00:26:33,990 --> 00:26:37,380 chini na kompyuta ya juu si lazima kazi 359 00:26:37,380 --> 00:26:42,470 kwa sababu ya juu ili kutokea kabla ya chini. 360 00:26:42,470 --> 00:26:47,340 Hiyo ni nini brute force ufumbuzi wa tatizo hili? 361 00:26:47,340 --> 00:26:53,150 Je, ni mambo mawili ambayo nahitaji kipekee kuamua faida mimi kufanya? Haki. 362 00:26:53,150 --> 00:26:59,410 brute force ufumbuzi ni - oh, hivyo, pendekezo George ni sisi tu haja ya siku mbili 363 00:26:59,410 --> 00:27:02,880 kwa kipekee kuamua faida ya siku hizo mbili. 364 00:27:02,880 --> 00:27:06,660 Hivyo sisi compute kila jozi, kama kununua / kuuza, 365 00:27:06,660 --> 00:27:12,850 compute faida, ambayo inaweza kuwa hasi au chanya au sifuri. 366 00:27:12,850 --> 00:27:18,000 Compute faida kubwa kwamba sisi kufanya baada ya iterating juu ya jozi wote wa siku. 367 00:27:18,000 --> 00:27:20,330 Hiyo itakuwa jibu yetu ya mwisho. 368 00:27:20,330 --> 00:27:25,730 Na ufumbuzi kwamba itakuwa O (n ^ 2), kwa sababu kuna n kuchagua jozi mbili - 369 00:27:25,730 --> 00:27:30,270 ya siku kwamba unaweza kuchagua kati ya siku za mwisho. 370 00:27:30,270 --> 00:27:32,580 Okay, hivyo nina si kwenda na kwenda juu ya ufumbuzi brute force hapa. 371 00:27:32,580 --> 00:27:37,420 Mimi naenda kukuambia kwamba kuna n logi n ufumbuzi. 372 00:27:37,420 --> 00:27:45,550 Nini algorithm gani sasa kujua kwamba ni n logi n? 373 00:27:45,550 --> 00:27:50,730 Siyo suala hila. 374 00:27:50,730 --> 00:27:54,790 >> Changanya aina. Changanya aina ni n logi n, 375 00:27:54,790 --> 00:27:57,760 na kwa kweli, njia moja ya kutatua tatizo hili ni kutumia 376 00:27:57,760 --> 00:28:04,400 aina kuunganisha aina ya wazo kuitwa, kwa ujumla, kugawanya na kushinda. 377 00:28:04,400 --> 00:28:07,570 Na wazo ni kama ifuatavyo. 378 00:28:07,570 --> 00:28:12,400 Unataka compute bora kununua / kuuza jozi katika nusu kushoto. 379 00:28:12,400 --> 00:28:16,480 Kupata faida bora unaweza kufanya, na tu n kwanza juu ya siku mbili. 380 00:28:16,480 --> 00:28:19,780 Kisha unataka oompute bora kununua / kuuza jozi kwenye nusu haki, 381 00:28:19,780 --> 00:28:23,930 hivyo n mwisho juu ya siku mbili. 382 00:28:23,930 --> 00:28:32,400 Na sasa swali ni jinsi gani sisi kuunganisha hawa ufumbuzi nyuma pamoja? 383 00:28:32,400 --> 00:28:36,320 Ndiyo? (Mwanafunzi, unintelligible) 384 00:28:36,320 --> 00:28:49,890 >> Sawa. Hivyo basi mimi kuchora picha. 385 00:28:49,890 --> 00:29:03,870 Ndiyo? (George, unintelligible) 386 00:29:03,870 --> 00:29:06,450 >> Hasa. George ufumbuzi ni sahihi kabisa. 387 00:29:06,450 --> 00:29:10,040 Hivyo maoni yake ni, kwanza compute bora kununua / kuuza jozi, 388 00:29:10,040 --> 00:29:16,050 na kwamba hutokea katika nusu kushoto, hivyo hebu wito kwamba kushoto, kushoto. 389 00:29:16,050 --> 00:29:20,790 Best kununua / kuuza jozi kwamba hutokea katika nusu ya haki. 390 00:29:20,790 --> 00:29:25,180 Lakini kama sisi tu ikilinganishwa namba hizi mbili, sisi ni kukosa kesi 391 00:29:25,180 --> 00:29:30,460 ambapo sisi kununua hapa na kuuza mahali fulani katika nusu ya haki. 392 00:29:30,460 --> 00:29:33,810 Sisi kununua katika nusu kushoto, kuuza katika nusu ya haki. 393 00:29:33,810 --> 00:29:38,490 Na njia bora ya compute bora kununua / kuuza jozi kwamba spans halves wote 394 00:29:38,490 --> 00:29:43,480 ni kwa compute kima cha chini hapa na compute upeo hapa 395 00:29:43,480 --> 00:29:45,580 na kuchukua tofauti zao. 396 00:29:45,580 --> 00:29:50,850 Hivyo kesi mbili ambapo jozi kununua / kuuza hutokea tu hapa, 397 00:29:50,850 --> 00:30:01,910 tu hapa, au juu ya wote halves hufafanuliwa kwa namba hizi tatu. 398 00:30:01,910 --> 00:30:06,450 Hivyo algorithm yetu kwa kuunganisha ufumbuzi yetu nyuma pamoja, 399 00:30:06,450 --> 00:30:08,350 tunataka compute bora kununua / kuuza jozi 400 00:30:08,350 --> 00:30:13,120 ambapo sisi kununua kwa nusu kushoto na kuuza nusu ya haki. 401 00:30:13,120 --> 00:30:16,740 Na njia bora ya kufanya hivyo ni kwa compute bei ya chini katika nusu ya kwanza, 402 00:30:16,740 --> 00:30:20,360 bei ya juu katika nusu haki, na kuchukua tofauti zao. 403 00:30:20,360 --> 00:30:25,390 kusababisha tatu faida, hizi idadi tatu, unaweza kuchukua upeo wa tatu, 404 00:30:25,390 --> 00:30:32,720 na kwamba ni faida bora unaweza kufanya zaidi ya siku hizi kwanza na wa mwisho. 405 00:30:32,720 --> 00:30:36,940 Hapa mistari muhimu ni katika nyekundu. 406 00:30:36,940 --> 00:30:41,160 Huu ni wito wa kujirudia kwa compute jibu katika nusu kushoto. 407 00:30:41,160 --> 00:30:44,760 Huu ni wito wa kujirudia kwa compute jibu katika nusu ya haki. 408 00:30:44,760 --> 00:30:50,720 Hizi mbili kwa matanzi compute min na max juu ya nusu ya kushoto na kulia, kwa mtiririko huo. 409 00:30:50,720 --> 00:30:54,970 Sasa mimi compute faida spans halves wote, 410 00:30:54,970 --> 00:31:00,530 na jibu la mwisho ni upeo wa tatu hizi. 411 00:31:00,530 --> 00:31:04,120 Sawa. 412 00:31:04,120 --> 00:31:06,420 >> Hivyo, uhakika, tuna algorithm, lakini swali kubwa ni, 413 00:31:06,420 --> 00:31:08,290 kile ni utata wakati wa hili? 414 00:31:08,290 --> 00:31:16,190 Na sababu mimi zilizotajwa kuunganisha aina ni kwamba aina hii ya kugawanya jibu 415 00:31:16,190 --> 00:31:19,200 katika mbili na kisha kuunganisha ufumbuzi yetu nyuma pamoja 416 00:31:19,200 --> 00:31:23,580 ni hasa aina ya aina kuunganisha. 417 00:31:23,580 --> 00:31:33,360 Hivyo basi mimi kwenda kwa njia ya muda. 418 00:31:33,360 --> 00:31:41,340 Kama sisi defined t kazi (n) kuwa idadi ya hatua 419 00:31:41,340 --> 00:31:50,010 kwa n siku, 420 00:31:50,010 --> 00:31:54,350 zetu mbili kujirudia wito 421 00:31:54,350 --> 00:32:00,460 ni kila kwenda gharama t (n / 2), 422 00:32:00,460 --> 00:32:03,540 na kuna mawili ya simu hizi. 423 00:32:03,540 --> 00:32:10,020 Sasa nahitaji compute chini ya nusu ya kushoto, 424 00:32:10,020 --> 00:32:17,050 ambayo naweza kufanya katika n / 2 wakati, pamoja na upeo wa nusu ya haki. 425 00:32:17,050 --> 00:32:20,820 Hivyo hii ni haki ya n. 426 00:32:20,820 --> 00:32:25,050 Na kisha pamoja na baadhi ya kazi mara kwa mara. 427 00:32:25,050 --> 00:32:27,770 Na hii equation upprepning 428 00:32:27,770 --> 00:32:35,560 ni hasa equation upprepning kwa aina kuunganisha. 429 00:32:35,560 --> 00:32:39,170 Na sisi wote tunajua kwamba kuunganisha aina ni n logi n wakati. 430 00:32:39,170 --> 00:32:46,880 Kwa hiyo, algorithm yetu pia n logi n wakati. 431 00:32:46,880 --> 00:32:52,220 Je iteration hii mantiki? 432 00:32:52,220 --> 00:32:55,780 Tu recap mafupi ya hili: 433 00:32:55,780 --> 00:32:59,170 T (n) ni Idadi ya hatua ya compute faida upeo 434 00:32:59,170 --> 00:33:02,750 juu ya mwendo wa siku n. 435 00:33:02,750 --> 00:33:06,010 njia ya sisi wameigawanya wetu wito kujirudia 436 00:33:06,010 --> 00:33:11,980 ni kwa wito ufumbuzi yetu juu ya siku ya kwanza n / 2, 437 00:33:11,980 --> 00:33:14,490 hivyo kwamba moja ya simu, 438 00:33:14,490 --> 00:33:16,940 na kisha sisi kuwaita tena juu ya nusu ya pili. 439 00:33:16,940 --> 00:33:20,440 Basi hiyo ni mbili wito. 440 00:33:20,440 --> 00:33:25,310 Na kisha sisi kupata chini ya nusu ya kushoto, ambayo tunaweza kufanya katika muda linear, 441 00:33:25,310 --> 00:33:29,010 kupata upeo wa nusu haki, ambayo tunaweza kufanya katika muda linear. 442 00:33:29,010 --> 00:33:31,570 Hivyo n / 2 + n / 2 ni tu n. 443 00:33:31,570 --> 00:33:36,020 Basi tuna baadhi ya kazi mara kwa mara, ambayo ni kama kufanya hesabu. 444 00:33:36,020 --> 00:33:39,860 Hii equation upprepning ni hasa equation upprepning kwa aina kuunganisha. 445 00:33:39,860 --> 00:33:55,490 Hivyo, shuffle wetu algorithm ni pia n logi n. 446 00:33:55,490 --> 00:33:58,520 Hivyo muda kiasi gani ni sisi kutumia? 447 00:33:58,520 --> 00:34:04,910 Turudi kwa kificho. 448 00:34:04,910 --> 00:34:09,420 >> swali ni bora, jinsi wengi stack muafaka gani sisi milele kuwa wakati wowote? 449 00:34:09,420 --> 00:34:11,449 Tangu sisi ni kutumia recursion, 450 00:34:11,449 --> 00:34:23,530 idadi ya muafaka stack huamua nafasi yetu ya matumizi. 451 00:34:23,530 --> 00:34:29,440 Hebu fikiria n = 8. 452 00:34:29,440 --> 00:34:36,889 Tunatoa wito shuffle juu ya 8, 453 00:34:36,889 --> 00:34:41,580 ambayo nitakuita shuffle juu entries kwanza nne, 454 00:34:41,580 --> 00:34:46,250 ambayo nitakuita shuffle juu entries mbili za kwanza. 455 00:34:46,250 --> 00:34:51,550 Hivyo stack yetu ni - hii ni stack yetu. 456 00:34:51,550 --> 00:34:54,980 Na kisha sisi kuwaita shuffle tena juu ya 1, 457 00:34:54,980 --> 00:34:58,070 na kwamba ni nini msingi wetu ni kesi, hivyo sisi kurudi mara moja. 458 00:34:58,070 --> 00:35:04,700 Je, sisi milele kuwa na zaidi ya muafaka hii wengi stack? 459 00:35:04,700 --> 00:35:08,880 No sababu kila wakati sisi kufanya sala, 460 00:35:08,880 --> 00:35:10,770 sala ya kujirudia kwa Shuffle, 461 00:35:10,770 --> 00:35:13,950 sisi kugawanya kawaida yetu katika nusu. 462 00:35:13,950 --> 00:35:17,020 Hivyo idadi ya juu ya muafaka stack sisi milele kuwa wakati wowote 463 00:35:17,020 --> 00:35:28,460 ni juu ya utaratibu wa muafaka logi n stack. 464 00:35:28,460 --> 00:35:42,460 Kila sura stack ina nafasi ya mara kwa mara, 465 00:35:42,460 --> 00:35:44,410 na kwa hiyo jumla ya kiasi cha nafasi, 466 00:35:44,410 --> 00:35:49,240 kiasi cha upeo wa nafasi sisi milele kutumia ni O (logi n) nafasi 467 00:35:49,240 --> 00:36:03,040 ambapo n ni idadi ya siku. 468 00:36:03,040 --> 00:36:07,230 >> Sasa, ujihoji, "Je, sisi kufanya vizuri?" 469 00:36:07,230 --> 00:36:12,390 Na hasa, tunaweza kupunguza tatizo tumekuwa tayari kutatuliwa? 470 00:36:12,390 --> 00:36:20,040 hint: sisi tu kujadiliwa mbili matatizo mengine kabla ya haya, na si kwenda kuwa shuffle. 471 00:36:20,040 --> 00:36:26,200 Tunaweza kubadilisha soko hili la hisa tatizo katika tatizo maximal subarray. 472 00:36:26,200 --> 00:36:40,100 Tunawezaje kufanya hivyo? 473 00:36:40,100 --> 00:36:42,570 Moja ya wewe? Emmy? 474 00:36:42,570 --> 00:36:47,680 (Emmy, unintelligible) 475 00:36:47,680 --> 00:36:53,860 [Yu] Hasa. 476 00:36:53,860 --> 00:36:59,940 Hivyo tatizo maximal subarray, 477 00:36:59,940 --> 00:37:10,610 sisi ni kuangalia kwa jumla juu ya subarray kuendelea. 478 00:37:10,610 --> 00:37:16,230 Na pendekezo Emmy kwa tatizo hifadhi, 479 00:37:16,230 --> 00:37:30,720 kuzingatia mabadiliko, au delta. 480 00:37:30,720 --> 00:37:37,440 Na picha ya hii ni - hii ni bei ya hisa, 481 00:37:37,440 --> 00:37:42,610 lakini kama sisi alichukua tofauti kati ya kila siku mfululizo - 482 00:37:42,610 --> 00:37:45,200 hivyo tunaona kwamba bei ya upeo, upeo faida tunaweza kufanya 483 00:37:45,200 --> 00:37:50,070 ni kama sisi kununua na kuuza hapa hapa. 484 00:37:50,070 --> 00:37:54,240 Lakini hebu angalia kuendelea - hebu tuangalie tatizo subarray. 485 00:37:54,240 --> 00:38:02,510 Hivyo hapa, tunaweza kufanya - yanaenda hapa na hapa, 486 00:38:02,510 --> 00:38:08,410 tuna mabadiliko chanya, na kisha kwenda kutoka hapa na hapa tuna mabadiliko hasi. 487 00:38:08,410 --> 00:38:14,220 Lakini basi, inaenda hapa na hapa tuna kubwa mabadiliko chanya. 488 00:38:14,220 --> 00:38:20,930 Na haya ni mabadiliko ambayo tunataka jumla juu ya kupata faida yetu ya mwisho. 489 00:38:20,930 --> 00:38:25,160 Basi tuna zaidi hasi mabadiliko hapa. 490 00:38:25,160 --> 00:38:29,990 muhimu kwa kupunguza hisa zetu tatizo ndani ya tatizo letu maximal subarray 491 00:38:29,990 --> 00:38:36,630 ni kuzingatia delta kati ya siku. 492 00:38:36,630 --> 00:38:40,630 Hivyo sisi kujenga safu mpya inayoitwa delta, 493 00:38:40,630 --> 00:38:43,000 initialize ya kwanza kuingia kwa kuwa 0, 494 00:38:43,000 --> 00:38:46,380 na kisha kwa kila delta (i), basi kwamba kuwa tofauti 495 00:38:46,380 --> 00:38:52,830 wa pembejeo yangu array (i), na safu (i - 1). 496 00:38:52,830 --> 00:38:55,530 Kisha sisi kuwaita utaratibu wetu wa kawaida kwa subarray maximal 497 00:38:55,530 --> 00:39:01,500 kupita katika safu ya delta. 498 00:39:01,500 --> 00:39:06,440 Na kwa sababu subarray maximal ni linear muda, 499 00:39:06,440 --> 00:39:09,370 na hii kupunguza, mchakato huu wa kujenga hii safu delta, 500 00:39:09,370 --> 00:39:11,780 pia ni linear muda, 501 00:39:11,780 --> 00:39:19,060 basi suluhisho la mwisho kwa ajili ya hifadhi ni O (n) kazi pamoja na O (n) kazi, bado ni O (n) kazi. 502 00:39:19,060 --> 00:39:23,900 Hivyo tuna linear wakati ufumbuzi wa tatizo letu. 503 00:39:23,900 --> 00:39:29,610 Je, kila mtu kuelewa mabadiliko haya? 504 00:39:29,610 --> 00:39:32,140 >> Kwa ujumla, wazo nzuri kwamba unapaswa daima kuwa 505 00:39:32,140 --> 00:39:34,290 ni kujaribu kupunguza tatizo mpya kwamba wewe ni kuona. 506 00:39:34,290 --> 00:39:37,700 Kama inaonekana familiar na tatizo zamani, 507 00:39:37,700 --> 00:39:39,590 kujaribu kupunguza kwa tatizo zamani. 508 00:39:39,590 --> 00:39:41,950 Na kama unaweza kutumia zana zote kwamba ve kutumika kwenye tatizo zamani 509 00:39:41,950 --> 00:39:46,450 kutatua tatizo mpya. 510 00:39:46,450 --> 00:39:49,010 Hivyo wa kufuta, mahojiano ya kiufundi ni changamoto. 511 00:39:49,010 --> 00:39:52,280 Matatizo haya pengine baadhi ya matatizo magumu zaidi 512 00:39:52,280 --> 00:39:54,700 kwamba unaweza kuona katika mahojiano, 513 00:39:54,700 --> 00:39:57,690 hivyo kama huelewi matatizo yote kwamba mimi tu kufunikwa, ni sawa. 514 00:39:57,690 --> 00:40:01,080 Hizi ni baadhi ya matatizo ya changamoto zaidi. 515 00:40:01,080 --> 00:40:03,050 Mazoezi, mazoezi, mazoezi. 516 00:40:03,050 --> 00:40:08,170 Mimi alitoa na matatizo mengi katika karatasi ya mazoezi, hivyo dhahiri kuangalia wale nje. 517 00:40:08,170 --> 00:40:11,690 Na bahati nzuri juu ya mahojiano yako. Rasilimali yangu yote ni posted katika link hii, 518 00:40:11,690 --> 00:40:15,220 na mmoja wa marafiki zangu mwandamizi imetoa kufanya mahojiano maskhara kiufundi, 519 00:40:15,220 --> 00:40:22,050 hivyo kama wewe ni nia, barua pepe Will Yao katika anuani kwamba barua pepe. 520 00:40:22,050 --> 00:40:26,070 Kama una baadhi ya maswali, unaweza kuuliza mimi. 521 00:40:26,070 --> 00:40:28,780 Je, wewe guys kuwa maswali maalum kuhusiana na mahojiano ya kiufundi 522 00:40:28,780 --> 00:40:38,440 au matatizo yoyote tumeona hadi sasa? 523 00:40:38,440 --> 00:40:49,910 Sawa. Naam, bahati nzuri na mahojiano yako. 524 00:40:49,910 --> 00:40:52,910 [CS50.TV]