1 00:00:00,000 --> 00:00:11,904 >> [Music kucheza] 2 00:00:11,904 --> 00:00:12,910 >> PROFESA: zote haki. 3 00:00:12,910 --> 00:00:16,730 Hii ni CS50 na hii ni Mwishoni mwa wiki tatu. 4 00:00:16,730 --> 00:00:20,230 Hivyo sisi ni hapa leo, si katika Sanders Ukumbi, badala katika Weidner maktaba. 5 00:00:20,230 --> 00:00:23,170 Ndani ya ambayo ni studio inayojulikana kama Hauser Studio, 6 00:00:23,170 --> 00:00:28,310 au tuseme Studio H, au atakuwa sisi say-- kama wewe walifurahia kwamba utani, 7 00:00:28,310 --> 00:00:30,540 ni kweli kutoka classmate, Marko, online, 8 00:00:30,540 --> 00:00:32,420 ambaye alipendekeza kama kiasi kupitia Twitter. 9 00:00:32,420 --> 00:00:34,270 Sasa nini baridi kuhusu kuwa hapa katika studio 10 00:00:34,270 --> 00:00:38,410 ni kwamba mimi nina kuzungukwa na kijani hizi kuta, screen ya kijani au chromakey, 11 00:00:38,410 --> 00:00:43,290 hivyo kusema, ambayo ina maana kwamba CS50 Timu ya uzalishaji, unbeknownst kwangu 12 00:00:43,290 --> 00:00:47,380 sasa hivi, inaweza kuwa kuweka mimi zaidi mahali popote duniani, 13 00:00:47,380 --> 00:00:48,660 kwa bora au mbaya. 14 00:00:48,660 --> 00:00:51,800 >> Sasa kile uongo mbele, tatizo kuweka mbili ni katika mikono yako kwa wiki hii, 15 00:00:51,800 --> 00:00:53,830 lakini kwa tatizo kuweka tatu hii kuja wiki, 16 00:00:53,830 --> 00:00:56,600 utakuwa changamoto kwa kinachojulikana mchezo wa 15, 17 00:00:56,600 --> 00:00:58,960 umri wa chama neema kwamba unaweza kukumbuka kupokea 18 00:00:58,960 --> 00:01:02,030 kama mtoto ambayo ina rundo zima ya idadi ya kwamba unaweza slide juu, chini, 19 00:01:02,030 --> 00:01:05,790 kushoto na kulia, na kuna pengo moja ndani ya puzzle, ambamo wewe 20 00:01:05,790 --> 00:01:07,840 kweli anaweza slide vipande wale puzzle. 21 00:01:07,840 --> 00:01:11,150 Hatimaye kupokea hii puzzle katika baadhi ya nusu random ili, 22 00:01:11,150 --> 00:01:12,940 na lengo ni aina yake, juu hadi chini, 23 00:01:12,940 --> 00:01:16,310 kushoto na kulia, kutoka kwa mmoja njia yote hadi kupitia 15. 24 00:01:16,310 --> 00:01:19,360 >> Kwa bahati mbaya, utekelezaji itabidi upande 25 00:01:19,360 --> 00:01:21,590 ni kwenda kuwa programu msingi, si kimwili. 26 00:01:21,590 --> 00:01:25,280 Wewe ni kweli kwenda na kuandika kificho na ambayo mwanafunzi au mtumiaji anaweza 27 00:01:25,280 --> 00:01:26,760 kucheza mchezo wa 15. 28 00:01:26,760 --> 00:01:29,030 Na kwa kweli, katika hacker toleo la mchezo wa 15, 29 00:01:29,030 --> 00:01:32,155 wewe utakuwa na changamoto ya kutekeleza, si tu kucheza ya hii umri wa shule 30 00:01:32,155 --> 00:01:35,010 mchezo, lakini badala ya kutatua yake, utekelezaji wa mungu mode, 31 00:01:35,010 --> 00:01:38,280 hivyo kusema, kwamba kweli kutatua puzzle kwa binadamu, 32 00:01:38,280 --> 00:01:41,080 kwa kuwapatia ladha, baada ya ladha, baada ya ladha. 33 00:01:41,080 --> 00:01:42,280 Hivyo zaidi juu ya kwamba wiki ijayo. 34 00:01:42,280 --> 00:01:43,720 Lakini hiyo ni nini uongo mbele. 35 00:01:43,720 --> 00:01:47,610 >> Kwa sasa kukumbuka kuwa mapema wiki hii tulikuwa na cliffhanger hii, kama wewe, 36 00:01:47,610 --> 00:01:52,560 ambapo bora tunafanya kuchagua busara alikuwa amefungwa juu ya kubwa o ya n 37 00:01:52,560 --> 00:01:53,210 squared. 38 00:01:53,210 --> 00:01:56,520 Kwa maneno mengine, Bubble aina, uteuzi aina, kuingizwa aina, 39 00:01:56,520 --> 00:01:59,120 wote, wakati tofauti katika utekelezaji wake, 40 00:01:59,120 --> 00:02:03,480 ulisababisha n squared mbio wakati katika hali mbaya sana. 41 00:02:03,480 --> 00:02:06,010 Na sisi ujumla kudhani kuwa mbaya sana kesi kwa ajili ya kuchagua 42 00:02:06,010 --> 00:02:08,814 ni moja kwamba pembejeo yako ni kabisa nyuma. 43 00:02:08,814 --> 00:02:11,980 Na hakika, ilichukua hatua chache kabisa kutekeleza kila moja ya algorithms hizo. 44 00:02:11,980 --> 00:02:15,110 >> Sasa mwishoni sana ya darasa wanakumbuka, sisi ikilinganishwa Bubble aina 45 00:02:15,110 --> 00:02:19,390 dhidi ya uteuzi aina dhidi ya mtu mwingine kwamba sisi kuitwa kuunganisha aina kwa wakati mmoja, 46 00:02:19,390 --> 00:02:22,120 na mimi kupendekeza kwamba ni kuchukua faida ya somo kutoka wiki 47 00:02:22,120 --> 00:02:24,060 sifuri, kugawanya na kushinda. 48 00:02:24,060 --> 00:02:28,810 Na kwa namna fulani kufanikisha baadhi ya aina ya logarithmic mbio wakati hatimaye, 49 00:02:28,810 --> 00:02:31,024 badala ya kitu hiyo ni rena quadratic. 50 00:02:31,024 --> 00:02:33,440 Na si logarithmic kabisa, ni kidogo zaidi ya hapo. 51 00:02:33,440 --> 00:02:36,520 Lakini kama unakumbuka kutoka darasani, ilikuwa kubwa, kwa kasi zaidi. 52 00:02:36,520 --> 00:02:38,210 Hebu tuangalie ambapo sisi kushoto mbali. 53 00:02:38,210 --> 00:02:41,880 54 00:02:41,880 --> 00:02:45,370 >> Bubble aina dhidi ya uteuzi aina dhidi ya kuunganisha aina. 55 00:02:45,370 --> 00:02:47,700 Sasa wao ni wote kukimbia, katika nadharia, kwa wakati mmoja. 56 00:02:47,700 --> 00:02:50,510 CPU ni mbio kwa kasi hiyo hiyo. 57 00:02:50,510 --> 00:02:54,990 Lakini unaweza kuhisi jinsi boring huu ni haraka sana kwenda kuwa, 58 00:02:54,990 --> 00:02:58,790 na tu jinsi ya kufunga, wakati sisi kuingiza kidogo ya wiki sifuri ya algorithms, 59 00:02:58,790 --> 00:03:00,080 Tunaweza kasi ya mambo up. 60 00:03:00,080 --> 00:03:01,630 >> Hivyo aina alama inaonekana ajabu. 61 00:03:01,630 --> 00:03:05,220 Jinsi gani tunakuwa na usawa, ili kutatua idadi kwa haraka zaidi. 62 00:03:05,220 --> 00:03:07,140 Naam hebu fikiria nyuma kwa kingo kwamba sisi 63 00:03:07,140 --> 00:03:10,380 alikuwa nyuma katika wiki sifuri, ile ya kwa ajili ya kutafuta mtu katika kitabu cha simu, 64 00:03:10,380 --> 00:03:12,380 na kukumbuka kuwa pseudocode kwamba sisi mapendekezo, 65 00:03:12,380 --> 00:03:14,560 kupitia ambayo tunaweza kupata mtu kama Mike Smith, 66 00:03:14,560 --> 00:03:16,310 inaonekana kitu kidogo kama hii. 67 00:03:16,310 --> 00:03:20,820 >> Sasa tuangalie hasa katika mstari wa 7 na 8, na 10 na 11, 68 00:03:20,820 --> 00:03:25,240 ambayo kushawishi kwamba kitanzi, ambapo tuliendelea kurejea mstari 3 tena, na tena, 69 00:03:25,240 --> 00:03:26,520 na tena. 70 00:03:26,520 --> 00:03:31,790 Lakini zinageuka kuwa tunaweza kuona algorithm hii, hapa katika pseudocode, 71 00:03:31,790 --> 00:03:33,620 kidogo zaidi holistically. 72 00:03:33,620 --> 00:03:35,960 Kwa kweli, ni nini mimi nina kuangalia katika hapa kwenye screen, 73 00:03:35,960 --> 00:03:41,180 ni algorithm kwa ajili ya kutafuta Mike Smith miongoni mwa baadhi ya seti ya kurasa. 74 00:03:41,180 --> 00:03:45,520 Na hakika, tunaweza kurahisisha hii algorithm katika wale mistari ya 7 na 8, 75 00:03:45,520 --> 00:03:49,860 na 10 na 11 ya kusema tu hii, ambayo nimekuwa iliyotolewa hapa katika njano. 76 00:03:49,860 --> 00:03:52,210 Kwa maneno mengine, kama Mike Smith ni mapema katika kitabu, 77 00:03:52,210 --> 00:03:55,004 hatuna haja ya kutaja hatua kwa hatua sasa jinsi ya kwenda kumpata. 78 00:03:55,004 --> 00:03:56,920 Hatuna bayana kurudi mstari wa 3, 79 00:03:56,920 --> 00:03:58,960 kwa nini sio sisi tu badala yake, kusema, kwa ujumla zaidi, 80 00:03:58,960 --> 00:04:01,500 kutafuta Mike katika kushoto nusu ya kitabu. 81 00:04:01,500 --> 00:04:03,960 >> Kinyume chake, kama Mike ni kweli baadaye katika kitabu, 82 00:04:03,960 --> 00:04:07,540 kwa nini sio sisi tu kunukuu la unquote kwa Mike katika nusu haki ya kitabu. 83 00:04:07,540 --> 00:04:11,030 Kwa maneno mengine, kwa nini sio sisi tu aina ya punt kwa wenyewe na kusema, 84 00:04:11,030 --> 00:04:13,130 kutafuta Mike katika hii subset ya kitabu, 85 00:04:13,130 --> 00:04:16,279 na kuondoka kwa zilizopo wetu algorithm kutuambia 86 00:04:16,279 --> 00:04:18,750 jinsi ya kutafuta Mike katika kuwa nusu ya kushoto ya kitabu. 87 00:04:18,750 --> 00:04:20,750 Kwa maneno mengine, yetu algorithm kazi kama ni 88 00:04:20,750 --> 00:04:24,670 kitabu cha simu ya unene hii, bila hii unene, au unene yoyote ile. 89 00:04:24,670 --> 00:04:27,826 Hivyo tunaweza recursively kufafanua algorithm hii. 90 00:04:27,826 --> 00:04:29,950 Kwa maneno mengine, juu ya screen hapa, ni algorithm 91 00:04:29,950 --> 00:04:33,130 kwa ajili ya kutafuta Mike Smith miongoni mwa kurasa za kitabu cha simu. 92 00:04:33,130 --> 00:04:37,410 Hivyo katika mstari 7 na 10, hebu tu kusema hasa kwamba. 93 00:04:37,410 --> 00:04:40,250 Na mimi kutumia muda huu sasa iliyopita, na kwa kweli, kujirudia 94 00:04:40,250 --> 00:04:42,450 ni buzzword kwa sasa, na ni mchakato huu 95 00:04:42,450 --> 00:04:47,210 ya kufanya kitu mzunguko na kwa namna fulani kutumia kanuni kwamba tayari kuwa, 96 00:04:47,210 --> 00:04:49,722 na kuiita tena, na tena, na tena. 97 00:04:49,722 --> 00:04:51,930 Sasa ni kwenda kuwa muhimu kwamba sisi kwa namna fulani chini 98 00:04:51,930 --> 00:04:53,821 nje, na kufanya hivyo kubwa kwa muda mrefu. 99 00:04:53,821 --> 00:04:56,070 Vinginevyo tunakwenda na kwa hakika usio kitanzi. 100 00:04:56,070 --> 00:04:59,810 Lakini hebu angalia kama tunaweza kukopa wazo hili ya kujirudia, kufanya kitu tena 101 00:04:59,810 --> 00:05:03,600 na tena na tena, kutatua kuchagua tatizo kupitia kuunganisha 102 00:05:03,600 --> 00:05:05,900 aina, kwa ufanisi zaidi wote. 103 00:05:05,900 --> 00:05:06,970 >> Hivyo mimi kukupa kuunganisha aina. 104 00:05:06,970 --> 00:05:07,920 Hebu tuangalie. 105 00:05:07,920 --> 00:05:10,850 Hivyo hapa ni pseudocode, kwa ambayo tunaweza kutekeleza kuchagua, 106 00:05:10,850 --> 00:05:12,640 kutumia algorithm hii inaitwa kuunganisha aina. 107 00:05:12,640 --> 00:05:13,880 Na ni tu kabisa hii. 108 00:05:13,880 --> 00:05:15,940 On mchango wa mambo n, kwa maneno mengine, kama wewe ni 109 00:05:15,940 --> 00:05:18,830 kutokana na N mambo na idadi na barua au chochote pembejeo ni, 110 00:05:18,830 --> 00:05:22,430 kama wewe ni kupewa vipengele n, ikiwa n ni chini ya 2, kurudi tu. 111 00:05:22,430 --> 00:05:22,930 Sawa? 112 00:05:22,930 --> 00:05:26,430 Kwa sababu kama n ni chini ya 2, kwamba maana yake ni kwamba orodha yangu ya vipengele 113 00:05:26,430 --> 00:05:30,446 ni aidha ya kawaida 0 au 1, na katika wawili wa kesi hizo yasiyo na maana, 114 00:05:30,446 --> 00:05:31,570 orodha tayari Iliyopangwa. 115 00:05:31,570 --> 00:05:32,810 Kama hakuna orodha, ni vyema. 116 00:05:32,810 --> 00:05:35,185 Na kama kuna orodha ya urefu 1, ni wazi yamepangwa. 117 00:05:35,185 --> 00:05:38,280 Hivyo algorithm anahitaji tu kweli kufanya kitu kuvutia, 118 00:05:38,280 --> 00:05:40,870 kama tuna mbili au zaidi mambo tuliyopewa. 119 00:05:40,870 --> 00:05:42,440 Hivyo hebu tuangalie uchawi wakati huo. 120 00:05:42,440 --> 00:05:47,500 Mwingine aina nusu ya kushoto ya mambo, kisha kutatua nusu ya haki ya vipengele, 121 00:05:47,500 --> 00:05:49,640 kisha kuunganisha halves Iliyopangwa. 122 00:05:49,640 --> 00:05:52,440 Na nini aina ya akili bending hapa, ni kwamba mimi si kweli 123 00:05:52,440 --> 00:05:56,190 kuonekana kwa nimewaambia chochote bado tu, sawa? 124 00:05:56,190 --> 00:05:59,560 Wote nilivyosema ni, kutokana na orodha ya n vipengele, aina nusu kushoto, 125 00:05:59,560 --> 00:06:01,800 kisha nusu wa kulia, kisha kuunganisha nusu yamepangwa, 126 00:06:01,800 --> 00:06:03,840 lakini yuko wapi halisi mchuzi siri? 127 00:06:03,840 --> 00:06:05,260 Ni algorithm wapi? 128 00:06:05,260 --> 00:06:09,150 Vizuri zinageuka kuwa wale mistari miwili kwanza, aina kushoto nusu ya vipengele, 129 00:06:09,150 --> 00:06:13,970 na aina haki nusu ya vipengele, ni wito kujirudia, hivyo kusema. 130 00:06:13,970 --> 00:06:16,120 >> Baada ya yote, wakati huu wakati katika muda, kufanya nina 131 00:06:16,120 --> 00:06:18,950 algorithm ambayo kwa aina rundo zima la mambo? 132 00:06:18,950 --> 00:06:19,450 Ndiyo. 133 00:06:19,450 --> 00:06:20,620 Ni haki hapa. 134 00:06:20,620 --> 00:06:25,180 Ni haki hapa kwenye screen, na hivyo siwezi kutumia seti moja ya hatua 135 00:06:25,180 --> 00:06:28,500 kutatua nusu kushoto, kama naweza nusu ya haki. 136 00:06:28,500 --> 00:06:30,420 Na hakika, tena, na tena. 137 00:06:30,420 --> 00:06:34,210 Hivyo namna fulani au nyingine, na tutaweza karibuni Kuona hii, uchawi wa aina kuunganisha 138 00:06:34,210 --> 00:06:37,967 ni iliyoingia katika kwamba mwisho sana line, kuunganisha halves Iliyopangwa. 139 00:06:37,967 --> 00:06:39,300 Na kwamba inaonekana haki Intuitive. 140 00:06:39,300 --> 00:06:41,050 Wewe kuchukua nusu mbili, na wewe, kwa kiasi fulani, kuunganisha yao kwa pamoja, 141 00:06:41,050 --> 00:06:43,260 na tutaweza kuona hii uthabiti katika wakati huu. 142 00:06:43,260 --> 00:06:45,080 >> Lakini hii ni algorithm kamili. 143 00:06:45,080 --> 00:06:46,640 Na hebu angalia nini hasa. 144 00:06:46,640 --> 00:06:50,912 Vizuri tuseme kwamba sisi ni kupewa hizo hizo mambo nane hapa kwenye screen, moja 145 00:06:50,912 --> 00:06:53,120 kupitia nane, lakini wao ni ili inaonekana random. 146 00:06:53,120 --> 00:06:55,320 Na lengo katika mkono ni kutatua mambo haya. 147 00:06:55,320 --> 00:06:58,280 Vizuri jinsi gani naweza kwenda juu kufanya hivyo kwa kutumia, tena, 148 00:06:58,280 --> 00:07:00,407 kuunganisha aina, kwa mujibu wa pseudocode hii? 149 00:07:00,407 --> 00:07:02,740 Na tena, ingrain hii katika akili yako, kwa muda tu. 150 00:07:02,740 --> 00:07:05,270 Kesi ya kwanza ni pretty yasiyo na maana, ikiwa ni chini ya 2, 151 00:07:05,270 --> 00:07:07,060 kurudi tu, hakuna kazi kufanyika. 152 00:07:07,060 --> 00:07:09,290 Hivyo kweli kuna tatu tu hatua za kweli kukumbuka. 153 00:07:09,290 --> 00:07:11,081 Tena, na tena, mimi nina atataka kuwa 154 00:07:11,081 --> 00:07:13,980 kutatua nusu kushoto, aina nusu haki, 155 00:07:13,980 --> 00:07:15,890 na kisha mara moja wao nusu mbili ni vyema, 156 00:07:15,890 --> 00:07:18,710 Nataka kuunganisha yao pamoja ndani ya moja sorted orodha. 157 00:07:18,710 --> 00:07:19,940 Hivyo kuendelea kuwa katika akili. 158 00:07:19,940 --> 00:07:21,310 >> Hivyo hapa ni orodha ya awali. 159 00:07:21,310 --> 00:07:23,510 Hebu kutibu hii kama safu, kama sisi kuanza kwa 160 00:07:23,510 --> 00:07:25,800 katika wiki mbili, ambayo ni contiguous block ya kumbukumbu. 161 00:07:25,800 --> 00:07:28,480 Katika kesi hiyo, zenye nane idadi, nyuma kwa nyuma kwa nyuma. 162 00:07:28,480 --> 00:07:30,700 Na hebu sasa kuomba kuunganisha aina. 163 00:07:30,700 --> 00:07:33,300 Hivyo mimi kwanza unataka kutatua nusu ya kushoto ya orodha hii, 164 00:07:33,300 --> 00:07:37,370 na hebu hiyo, kuzingatia 4, 8, 6, na 2. 165 00:07:37,370 --> 00:07:41,000 >> Sasa ni jinsi gani mimi kwenda kuhusu kuchagua orodha ya ukubwa 4? 166 00:07:41,000 --> 00:07:45,990 Vizuri mimi na sasa kufikiria kuchagua kushoto ya nusu kushoto. 167 00:07:45,990 --> 00:07:47,720 Tena, hebu rewind kwa muda tu. 168 00:07:47,720 --> 00:07:51,010 Kama pseudocode ni hii, na mimi nina kutolewa mambo nane, 169 00:07:51,010 --> 00:07:53,230 8 ni dhahiri zaidi kuliko au sawa na 2. 170 00:07:53,230 --> 00:07:54,980 Hivyo, pamoja na kesi ya kwanza haina kuomba. 171 00:07:54,980 --> 00:07:58,120 Hivyo kutatua mambo nane, mimi kwanza aina nusu ya kushoto ya mambo, 172 00:07:58,120 --> 00:08:01,930 kisha mimi aina nusu haki, basi mimi kuunganisha mbili halves Iliyopangwa, kila mmoja ukubwa 4. 173 00:08:01,930 --> 00:08:02,470 SAWA. 174 00:08:02,470 --> 00:08:07,480 >> Lakini kama wameweza tu aliniambia, aina kushoto nusu, ambayo sasa ni ya ukubwa 4, 175 00:08:07,480 --> 00:08:09,350 jinsi gani mimi kutatua kushoto nusu? 176 00:08:09,350 --> 00:08:11,430 Vizuri kama nina pembejeo ya mambo manne, 177 00:08:11,430 --> 00:08:14,590 Mimi kwanza kutatua kushoto mbili, kisha haki miwili, 178 00:08:14,590 --> 00:08:16,210 na kisha mimi kuunganisha yao kwa pamoja. 179 00:08:16,210 --> 00:08:18,700 Hivyo tena, inakuwa kidogo ya akili bending mchezo hapa, 180 00:08:18,700 --> 00:08:21,450 kwa sababu wewe, aina ya, na kukumbuka ambapo wewe ni katika hadithi, 181 00:08:21,450 --> 00:08:23,620 lakini mwisho wa siku, kutokana na idadi yoyote ya mambo, 182 00:08:23,620 --> 00:08:25,620 wewe kwanza unataka kutatua nusu ya kushoto, kisha nusu wa kulia, 183 00:08:25,620 --> 00:08:26,661 kisha kuunganisha yao kwa pamoja. 184 00:08:26,661 --> 00:08:28,630 Hebu kuanza kwa kufanya hasa kwamba. 185 00:08:28,630 --> 00:08:30,170 Hapa ni mchango wa mambo nane. 186 00:08:30,170 --> 00:08:31,910 Sasa sisi ni kuangalia nusu ya kushoto hapa. 187 00:08:31,910 --> 00:08:33,720 Je, mimi aina mambo manne? 188 00:08:33,720 --> 00:08:35,610 Naam, mimi kwanza kutatua kushoto nusu. 189 00:08:35,610 --> 00:08:37,720 Sasa ni jinsi gani mimi kutatua kushoto nusu? 190 00:08:37,720 --> 00:08:39,419 Naam nimekuwa kupewa vitu viwili. 191 00:08:39,419 --> 00:08:41,240 Basi hebu kutatua mambo haya mawili. 192 00:08:41,240 --> 00:08:44,540 2 ni kubwa zaidi kuliko au sawa na 2, bila shaka. 193 00:08:44,540 --> 00:08:46,170 Hivyo kwamba kesi ya kwanza haina kuomba. 194 00:08:46,170 --> 00:08:49,010 >> Hivyo mimi sasa una aina kushoto nusu ya mambo haya mawili. 195 00:08:49,010 --> 00:08:50,870 Nusu ya kushoto, bila shaka, ni 4 tu. 196 00:08:50,870 --> 00:08:54,020 Hivyo ni jinsi gani mimi aina orodha ya kipengele moja? 197 00:08:54,020 --> 00:08:57,960 Naam sasa, kwamba kesi maalum msingi juu juu, hivyo kusema, inatumika. 198 00:08:57,960 --> 00:09:01,470 1 ni chini ya 2, na yangu orodha ni kweli ya kawaida ya 1. 199 00:09:01,470 --> 00:09:02,747 Hivyo mimi tu kurudi. 200 00:09:02,747 --> 00:09:03,580 Mimi si kufanya kitu chochote. 201 00:09:03,580 --> 00:09:06,770 Na hakika, kuangalia nini nimekuwa kufanyika, 4 tayari Iliyopangwa. 202 00:09:06,770 --> 00:09:09,220 Kama tayari nina sehemu ya mafanikio hapa. 203 00:09:09,220 --> 00:09:11,750 >> Sasa kwa kuwa inaonekana aina ya kijinga kudai, lakini ni kweli. 204 00:09:11,750 --> 00:09:13,700 4 ni orodha ya kawaida ya 1. 205 00:09:13,700 --> 00:09:15,090 Ni tayari Iliyopangwa. 206 00:09:15,090 --> 00:09:16,270 Hiyo ni nusu kushoto. 207 00:09:16,270 --> 00:09:18,010 Sasa mimi kutatua nusu ya haki. 208 00:09:18,010 --> 00:09:22,310 Pembejeo yangu ni moja ya kipengele, 8 vile vile, tayari Iliyopangwa. 209 00:09:22,310 --> 00:09:25,170 Kijinga, pia, lakini tena, kanuni hii ya msingi 210 00:09:25,170 --> 00:09:28,310 ni kwenda kuruhusu sisi sasa kujenga juu ya hii kwa mafanikio. 211 00:09:28,310 --> 00:09:32,260 4 yamepangwa, 8 ni vyema, sasa nini ilikuwa ni hatua kwamba mwisho? 212 00:09:32,260 --> 00:09:35,330 Hivyo tatu na ya mwisho ya hatua, yoyote wakati wewe ni kuchagua orodha, kukumbuka, 213 00:09:35,330 --> 00:09:38,310 ilikuwa kuunganisha sehemu mbili, kushoto na kulia. 214 00:09:38,310 --> 00:09:39,900 Basi hebu kufanya hasa kwamba. 215 00:09:39,900 --> 00:09:41,940 Nusu au kushoto kwangu, bila shaka, 4. 216 00:09:41,940 --> 00:09:43,310 Nusu wangu wa kulia ni 8. 217 00:09:43,310 --> 00:09:44,100 >> Basi hebu kufanya hivyo. 218 00:09:44,100 --> 00:09:46,410 Kwanza mimi nina kwenda kutenga baadhi ya kumbukumbu za ziada, 219 00:09:46,410 --> 00:09:48,680 kwamba nita kuwakilisha hapa, kama tu safu ya sekondari, 220 00:09:48,680 --> 00:09:49,660 hiyo ni kubwa ya kutosha fit hii. 221 00:09:49,660 --> 00:09:52,243 Lakini unaweza kufikiria kupanua kuwa Mstatili urefu wote, 222 00:09:52,243 --> 00:09:53,290 kama tunahitaji zaidi baadaye. 223 00:09:53,290 --> 00:09:58,440 Je, mimi kuchukua 4 na 8, na kuunganisha wale orodha mbili ya ukubwa 1 pamoja? 224 00:09:58,440 --> 00:10:00,270 Hapa pia, pretty rahisi. 225 00:10:00,270 --> 00:10:03,300 4 anakuja kwanza, kisha huja 8. 226 00:10:03,300 --> 00:10:07,130 Kwa sababu kama nataka kutatua nusu ya kushoto, kisha nusu wa kulia, 227 00:10:07,130 --> 00:10:09,900 na kisha kuunganisha wale nusu mbili pamoja, ili Iliyopangwa, 228 00:10:09,900 --> 00:10:11,940 4 anakuja kwanza, kisha huja 8. 229 00:10:11,940 --> 00:10:15,810 >> Hivyo sisi wanaonekana kuwa kufanya maendeleo, hata ingawa sijafanya kazi yoyote halisi. 230 00:10:15,810 --> 00:10:17,800 Lakini kumbuka ambapo sisi ni katika hadithi. 231 00:10:17,800 --> 00:10:19,360 Sisi awali alichukua mambo nane. 232 00:10:19,360 --> 00:10:21,480 Sisi yamepangwa kushoto nusu, ambayo ni 4. 233 00:10:21,480 --> 00:10:24,450 Kisha sisi yamepangwa nusu ya kushoto ya kushoto nusu ambayo ilikuwa ni 2. 234 00:10:24,450 --> 00:10:25,270 Na hapa sisi kwenda. 235 00:10:25,270 --> 00:10:26,920 Sisi ni kosa kwa hatua hiyo. 236 00:10:26,920 --> 00:10:29,930 >> Hivyo kama tumekuwa yamepangwa kushoto nusu ya 2, sasa sisi 237 00:10:29,930 --> 00:10:32,130 una aina nusu haki ya 2. 238 00:10:32,130 --> 00:10:35,710 Hivyo nusu haki ya 2 ni maadili haya mawili hapa, 6 na 2. 239 00:10:35,710 --> 00:10:40,620 Basi hebu sasa kuchukua mchango wa ukubwa 2, na aina nusu kushoto, na kisha 240 00:10:40,620 --> 00:10:42,610 haki nusu, na kisha kuunganisha yao kwa pamoja. 241 00:10:42,610 --> 00:10:45,722 Vizuri jinsi gani mimi aina orodha ya ukubwa 1, zenye tu namba 6? 242 00:10:45,722 --> 00:10:46,430 Mimi tayari amefanya. 243 00:10:46,430 --> 00:10:48,680 Hiyo orodha ya ukubwa 1 ni Iliyopangwa. 244 00:10:48,680 --> 00:10:52,140 >> Je, mimi aina nyingine orodha ya ukubwa 1, kinachojulikana nusu ya haki. 245 00:10:52,140 --> 00:10:54,690 Vizuri, pia, tayari Iliyopangwa. 246 00:10:54,690 --> 00:10:56,190 Namba 2 ni peke yake. 247 00:10:56,190 --> 00:11:00,160 Hivyo sasa nina nusu mbili, kushoto na kulia, nahitaji kuunganisha yao kwa pamoja. 248 00:11:00,160 --> 00:11:01,800 Napenda kutoa mwenyewe baadhi ya nafasi ya ziada. 249 00:11:01,800 --> 00:11:05,580 Na kuweka 2 katika huko, kisha 6 katika huko, na hivyo 250 00:11:05,580 --> 00:11:10,740 kuchagua orodha hiyo, kushoto na kulia, na kuunganisha pamoja, hatimaye. 251 00:11:10,740 --> 00:11:12,160 Kwa hiyo mimi nina katika sura kidogo bora. 252 00:11:12,160 --> 00:11:16,250 Mimi si kufanyika, kwa sababu wazi 4, 8, 2, 6 ni si kuagiza mwisho kwamba nataka. 253 00:11:16,250 --> 00:11:20,640 Lakini sasa nina orodha mbili ya ukubwa 2, kwamba wana wawili, kwa mtiririko huo, wamekuwa yamepangwa. 254 00:11:20,640 --> 00:11:24,580 Hivyo sasa kama wewe rewind katika akili yako jicho, wapi kwamba kuondoka sisi? 255 00:11:24,580 --> 00:11:28,520 Mimi kuanza na mambo nane, basi mimi whittled ni chini ya nusu ya kushoto ya 4, 256 00:11:28,520 --> 00:11:31,386 kisha nusu ya kushoto ya 2, na kisha nusu haki ya 2, 257 00:11:31,386 --> 00:11:34,510 Mimi kumaliza, kwa hiyo, kuchagua kushoto nusu ya 2, na nusu haki ya 2, 258 00:11:34,510 --> 00:11:37,800 hivyo nini tatu na ya mwisho ya hatua hapa? 259 00:11:37,800 --> 00:11:41,290 Nina kuunganisha pamoja orodha mbili ya ukubwa 2. 260 00:11:41,290 --> 00:11:42,040 Basi hebu kwenda mbele. 261 00:11:42,040 --> 00:11:43,940 Na juu ya screen hapa, kutoa mimi baadhi ya kumbukumbu za ziada, 262 00:11:43,940 --> 00:11:47,170 ingawa kitaalam, taarifa kwamba nimekuwa got rundo zima la tupu nafasi ya juu juu 263 00:11:47,170 --> 00:11:47,670 huko. 264 00:11:47,670 --> 00:11:50,044 Kama Nataka kuwa hasa nafasi ufanisi busara, 265 00:11:50,044 --> 00:11:52,960 Mimi nilikuwa tu kuanza kusonga vipengele na kurudi, juu na chini. 266 00:11:52,960 --> 00:11:55,460 Lakini tu kwa uwazi Visual, Mimi nina kwenda kuiweka chini chini, 267 00:11:55,460 --> 00:11:56,800 kuweka mambo nzuri na safi. 268 00:11:56,800 --> 00:11:58,150 >> Hivyo mimi nimepata orodha mbili ya ukubwa 2. 269 00:11:58,150 --> 00:11:59,770 Orodha ya kwanza ina 4 na 8. 270 00:11:59,770 --> 00:12:01,500 Orodha pili ina 2 na 6. 271 00:12:01,500 --> 00:12:03,950 Hebu kuunganisha wale pamoja ili Iliyopangwa. 272 00:12:03,950 --> 00:12:09,910 2, bila shaka, suala la kwanza, kisha 4, kisha 6, basi 8. 273 00:12:09,910 --> 00:12:12,560 Na sasa sisi wanaonekana kuwa kupata mahali fulani ya kuvutia. 274 00:12:12,560 --> 00:12:15,720 Sasa nimekuwa yamepangwa nusu ya orodha, na kwa bahati, ni 275 00:12:15,720 --> 00:12:18,650 hata namba zote, lakini hiyo ni kweli, bahati mbaya tu. 276 00:12:18,650 --> 00:12:22,220 Na mimi sasa kuwa yamepangwa kushoto nusu, ili ni 2, 4, 6, na 8. 277 00:12:22,220 --> 00:12:23,430 Hakuna kitu nje ya utaratibu. 278 00:12:23,430 --> 00:12:24,620 Kwamba anahisi kama maendeleo. 279 00:12:24,620 --> 00:12:26,650 >> Sasa anahisi kama nimepata wamekuwa wakizungumza milele sasa, 280 00:12:26,650 --> 00:12:29,850 hivyo kile inabakia kuonekana kama hii algorithm ni kweli, ufanisi zaidi. 281 00:12:29,850 --> 00:12:31,766 Lakini tunakwenda kupitia super methodically. 282 00:12:31,766 --> 00:12:34,060 Kompyuta, bila shaka, bila kufanya hivyo kama hicho. 283 00:12:34,060 --> 00:12:34,840 Hivyo ambapo ni sisi? 284 00:12:34,840 --> 00:12:36,180 Sisi ilianza na mambo nane. 285 00:12:36,180 --> 00:12:37,840 Mimi yamepangwa nusu ya kushoto ya 4. 286 00:12:37,840 --> 00:12:39,290 Mimi wanaonekana kuwa kosa na kwamba. 287 00:12:39,290 --> 00:12:42,535 Hivyo sasa hatua inayofuata ni aina nusu haki ya 4. 288 00:12:42,535 --> 00:12:44,410 Na sehemu hii tunaweza kwenda kupitia zaidi kidogo 289 00:12:44,410 --> 00:12:47,140 haraka, ingawa uko kuwakaribisha kwa rewind au pause, tu 290 00:12:47,140 --> 00:12:49,910 kufikiri kwa njia hiyo katika kasi yako mwenyewe, lakini kile 291 00:12:49,910 --> 00:12:53,290 tuna sasa ni fursa ya kufanya halisi algorithm huo juu ya nne 292 00:12:53,290 --> 00:12:54,380 idadi tofauti. 293 00:12:54,380 --> 00:12:57,740 >> Basi hebu kwenda mbele, na kuzingatia haki nusu, ambayo sisi ni hapa. 294 00:12:57,740 --> 00:13:01,260 Nusu ya kushoto ya kwamba haki nusu, na sasa 295 00:13:01,260 --> 00:13:04,560 kushoto nusu ya kushoto nusu ya nusu kwamba haki, 296 00:13:04,560 --> 00:13:08,030 na jinsi gani mimi aina orodha ya ukubwa 1 zenye tu namba 1? 297 00:13:08,030 --> 00:13:09,030 Ni tayari kufanyika. 298 00:13:09,030 --> 00:13:11,830 Je, mimi kufanya hivyo kwa orodha ya kawaida ya 1 zenye 7 tu? 299 00:13:11,830 --> 00:13:12,840 Ni tayari kufanyika. 300 00:13:12,840 --> 00:13:16,790 Hatua ya tatu kwa nusu hii basi ni kuunganisha mambo hayo mawili 301 00:13:16,790 --> 00:13:20,889 ndani ya orodha mpya ya ukubwa 2, 1 na 7. 302 00:13:20,889 --> 00:13:23,180 Hawaonekani umefanya yote Inashangaza kwamba kazi kubwa. 303 00:13:23,180 --> 00:13:24,346 Hebu kuona nini kinatokea ijayo. 304 00:13:24,346 --> 00:13:29,210 I just yamepangwa nusu ya kushoto ya nusu haki ya pembejeo yangu ya awali. 305 00:13:29,210 --> 00:13:32,360 Sasa hebu kutatua haki nusu, ambayo ina 5 na 3. 306 00:13:32,360 --> 00:13:35,740 Hebu tuangalie tena kushoto nusu, yamepangwa, nusu haki, yamepangwa, 307 00:13:35,740 --> 00:13:39,120 na kuunganisha hizo mbili pamoja, ndani ya baadhi ya nafasi ya ziada, 308 00:13:39,120 --> 00:13:41,670 3 anakuja kwanza, kisha huja 5. 309 00:13:41,670 --> 00:13:46,190 Na hivyo sasa, tuna yamepangwa kushoto nusu ya nusu haki 310 00:13:46,190 --> 00:13:49,420 tatizo ya awali, na nusu haki ya nusu haki 311 00:13:49,420 --> 00:13:50,800 tatizo awali. 312 00:13:50,800 --> 00:13:52,480 Nini tatu na ya mwisho Hatua? 313 00:13:52,480 --> 00:13:54,854 Vizuri kuunganisha wale nusu mbili pamoja. 314 00:13:54,854 --> 00:13:57,020 Hivyo basi mimi kupata mwenyewe baadhi nafasi ya ziada, lakini, tena, mimi 315 00:13:57,020 --> 00:13:58,699 inaweza kuwa kwa kutumia kwamba vipuri nafasi juu juu. 316 00:13:58,699 --> 00:14:00,490 Lakini tunakwenda kuweka ni rahisi kuibua. 317 00:14:00,490 --> 00:14:07,070 Napenda kuunganisha katika sasa 1, na kisha 3, na kisha 5, na kisha 7. 318 00:14:07,070 --> 00:14:10,740 Hivyo kuondoka kwangu sasa kwa nusu haki ya tatizo ya awali 319 00:14:10,740 --> 00:14:12,840 hiyo kikamilifu yamepangwa. 320 00:14:12,840 --> 00:14:13,662 >> Kwa hiyo kile bado? 321 00:14:13,662 --> 00:14:16,120 Najisikia kama mimi kuendelea kusema mambo sawa tena, na tena, 322 00:14:16,120 --> 00:14:18,700 lakini hiyo ni kutafakari ya ukweli kwamba sisi ni kutumia recursion. 323 00:14:18,700 --> 00:14:21,050 Mchakato wa kutumia algorithm tena, na tena, 324 00:14:21,050 --> 00:14:23,940 juu ya subsets ndogo ya awali tatizo. 325 00:14:23,940 --> 00:14:27,580 Hivyo mimi sasa kuwa kushoto yamepangwa nusu ya tatizo ya awali. 326 00:14:27,580 --> 00:14:30,847 Nina haki yamepangwa nusu tatizo awali. 327 00:14:30,847 --> 00:14:32,180 Nini tatu na ya mwisho ya hatua? 328 00:14:32,180 --> 00:14:33,590 Oh, ni kuunganisha. 329 00:14:33,590 --> 00:14:34,480 Basi hebu kufanya hivyo. 330 00:14:34,480 --> 00:14:36,420 Hebu kutenga baadhi ya ziada kumbukumbu, lakini mungu wangu, sisi 331 00:14:36,420 --> 00:14:37,503 inaweza kuiweka mahali popote sasa. 332 00:14:37,503 --> 00:14:40,356 Tuna nafasi sana inapatikana kwetu, lakini tutaweza kushika ni rahisi. 333 00:14:40,356 --> 00:14:42,730 Badala ya kurejea na Basi nenda na kumbukumbu yetu ya awali, 334 00:14:42,730 --> 00:14:44,480 hebu tu kufanya hivyo kuibua chini hapa chini, 335 00:14:44,480 --> 00:14:47,240 kumaliza up kuunganisha nusu kushoto na nusu wa kulia. 336 00:14:47,240 --> 00:14:49,279 >> Hivyo kwa kuunganisha, je, mimi haja ya kufanya? 337 00:14:49,279 --> 00:14:50,820 Nataka kuchukua mambo kwa utaratibu. 338 00:14:50,820 --> 00:14:53,230 Hivyo kuangalia nusu ya kushoto, Mimi naona idadi ya kwanza ni 2. 339 00:14:53,230 --> 00:14:55,230 Mimi kuangalia nusu ya haki, Mimi naona idadi ya kwanza 340 00:14:55,230 --> 00:14:58,290 ni 1, hivyo ni wazi ambayo idadi mimi nataka kuvunja nje, 341 00:14:58,290 --> 00:15:00,430 na kuweka kwanza katika orodha yangu ya mwisho? 342 00:15:00,430 --> 00:15:01,449 Bila shaka, 1. 343 00:15:01,449 --> 00:15:02,990 Sasa nataka kuuliza kwamba swali moja. 344 00:15:02,990 --> 00:15:05,040 On nusu ya kushoto, nimekuwa bado got namba 2. 345 00:15:05,040 --> 00:15:07,490 On nusu wa kulia, Mimi nimepata namba 3. 346 00:15:07,490 --> 00:15:08,930 Ambayo moja je Nataka kuchagua? 347 00:15:08,930 --> 00:15:11,760 Bila shaka, idadi 2 sasa taarifa wagombea 348 00:15:11,760 --> 00:15:13,620 4 upande wa kushoto, 3 juu ya haki. 349 00:15:13,620 --> 00:15:15,020 Hebu, bila shaka, kuchagua 3. 350 00:15:15,020 --> 00:15:18,020 Sasa wagombea ni juu ya 4 kushoto, 5 juu ya haki. 351 00:15:18,020 --> 00:15:19,460 Sisi, bila shaka, kuchagua 4. 352 00:15:19,460 --> 00:15:21,240 6 upande wa kushoto, 5 juu ya haki. 353 00:15:21,240 --> 00:15:22,730 Sisi, bila shaka, kuchagua 5. 354 00:15:22,730 --> 00:15:25,020 6 upande wa kushoto, 7 juu ya haki. 355 00:15:25,020 --> 00:15:29,320 Sisi kuchagua 6, na kisha sisi kuchagua 7, na kisha sisi kuchagua 8. 356 00:15:29,320 --> 00:15:30,100 Voila. 357 00:15:30,100 --> 00:15:34,370 >> Hivyo idadi kubwa ya maneno baadaye, sisi kuwa yamepangwa hii orodha ya mambo nane 358 00:15:34,370 --> 00:15:38,450 ndani ya orodha ya kwanza hadi la nane, hiyo ni kuongezeka pamoja na kila hatua, 359 00:15:38,450 --> 00:15:40,850 lakini wakati kiasi gani alifanya ni kutupeleka kufanya hivyo. 360 00:15:40,850 --> 00:15:43,190 Naam nimekuwa makusudi aliweka mambo ya nje pictorially 361 00:15:43,190 --> 00:15:46,330 hapa, ili tuweze aina ya kuona au kufahamu mgawanyiko 362 00:15:46,330 --> 00:15:49,060 katika mshindi hiyo imekuwa yanatokea. 363 00:15:49,060 --> 00:15:52,830 >> Hakika kama wewe kuangalia nyuma katika wake, Nimekuwa kushoto yote ya mistari haya dotted 364 00:15:52,830 --> 00:15:55,660 katika wamiliki mahali, unaweza, aina ya, kuona, ili reverse, 365 00:15:55,660 --> 00:15:58,800 kama wewe aina ya kuangalia nyuma katika historia sasa orodha yangu ya awali 366 00:15:58,800 --> 00:16:00,250 Ni, bila shaka, ya kawaida 8. 367 00:16:00,250 --> 00:16:03,480 Na kisha hapo awali, nilikuwa kushughulika na orodha mbili ya ukubwa 4, 368 00:16:03,480 --> 00:16:08,400 na kisha orodha vinne vya ukubwa 2, na kisha orodha nane ya kawaida ya 1. 369 00:16:08,400 --> 00:16:10,151 >> Kwa hiyo kile anafanya hivyo, aina ya, kuwakumbusha? 370 00:16:10,151 --> 00:16:11,858 Naam, kwa hakika, yoyote ya algorithms tumekuwa 371 00:16:11,858 --> 00:16:14,430 inaonekana katika hivi sasa ambapo sisi kugawanya, na kugawanya, na kugawanya, 372 00:16:14,430 --> 00:16:19,500 kuendelea kuwa na mambo tena, na tena, matokeo katika wazo hili kwa ujumla. 373 00:16:19,500 --> 00:16:23,100 Na hivyo kuna kitu logarithmic kinachoendelea hapa. 374 00:16:23,100 --> 00:16:26,790 Na si kabisa logi ya n, lakini kuna sehemu logarithmic 375 00:16:26,790 --> 00:16:28,280 kwa kile ambacho tumefanya tu. 376 00:16:28,280 --> 00:16:31,570 >> Sasa hebu fikiria jinsi kwamba kweli ni. 377 00:16:31,570 --> 00:16:34,481 Hivyo kuingia ya n, tena alikuwa kubwa mbio wakati, 378 00:16:34,481 --> 00:16:36,980 wakati sisi alifanya kitu kama tafuta binary, kama sisi sasa simu yake, 379 00:16:36,980 --> 00:16:40,090 kugawanya na kushinda mkakati kupitia ambayo sisi kupatikana Mike Smith. 380 00:16:40,090 --> 00:16:41,020 Sasa kitaalam. 381 00:16:41,020 --> 00:16:43,640 Hiyo ni gogo msingi 2 ya n, hata ingawa katika madarasa zaidi math, 382 00:16:43,640 --> 00:16:45,770 10 ni kawaida msingi kwamba wewe kudhani. 383 00:16:45,770 --> 00:16:48,940 Lakini wanasayansi wa kompyuta karibu kila mara kufikiri na kuzungumza katika suala la msingi 2, 384 00:16:48,940 --> 00:16:52,569 hivyo sisi ujumla tu kusema gogo la n, badala ya gogo msingi 2 ya n, 385 00:16:52,569 --> 00:16:55,110 lakini wao ni hasa moja na sawa katika dunia ya kompyuta 386 00:16:55,110 --> 00:16:57,234 sayansi, na kama kando, kuna sababu mara kwa mara 387 00:16:57,234 --> 00:17:01,070 tofauti kati ya wawili, hivyo ni moot anyway, kwa sababu rasmi zaidi. 388 00:17:01,070 --> 00:17:04,520 >> Lakini kwa sasa, nini sisi huduma kuhusu ni mfano huu. 389 00:17:04,520 --> 00:17:08,520 Basi hebu kuthibitisha kwa mfano, lakini wakati angalau kutumia mfano wa idadi 390 00:17:08,520 --> 00:17:10,730 upande kama sanity hundi, kama wewe. 391 00:17:10,730 --> 00:17:14,510 Hivyo awali fomula ilikuwa gogo msingi 2 ya n, lakini kile ni n katika kesi hii. 392 00:17:14,510 --> 00:17:18,526 Mimi nilikuwa idadi n awali, au 8 ya idadi ya awali hasa. 393 00:17:18,526 --> 00:17:20,359 Sasa imekuwa ni kidogo muda, lakini mimi nina pretty 394 00:17:20,359 --> 00:17:25,300 kuhakikisha kwamba gogo msingi 2 ya thamani ya 8 ni 3, 395 00:17:25,300 --> 00:17:29,630 na kwa kweli, nini ni nzuri juu ya hilo ni kuwa 3 ni hasa idadi ya nyakati 396 00:17:29,630 --> 00:17:33,320 uweze kugawanya orodha ya urefu 8 tena, na tena, 397 00:17:33,320 --> 00:17:36,160 na tena, mpaka wewe ni wa kushoto na orodha ya tu ukubwa 1. 398 00:17:36,160 --> 00:17:36,660 Sawa? 399 00:17:36,660 --> 00:17:40,790 8 inakwenda 4, huenda kwa 2, inakwenda 1, na kwamba 400 00:17:40,790 --> 00:17:43,470 kutafakari ya hasa kwamba picha tulikuwa muda tu iliyopita. 401 00:17:43,470 --> 00:17:47,160 Hivyo sanity kidogo kuangalia kama ambapo logarithm ni kweli kushiriki. 402 00:17:47,160 --> 00:17:50,180 >> Hivyo sasa, kile kingine ni kushiriki hapa? n. 403 00:17:50,180 --> 00:17:53,440 Hivyo taarifa kwamba kila wakati mimi kupasuliwa orodha, 404 00:17:53,440 --> 00:17:58,260 angalau katika kubadili utaratibu katika historia hapa, nilikuwa bado kufanya mambo n. 405 00:17:58,260 --> 00:18:02,320 Kwamba hatua kuunganisha required kwamba Mimi kugusa kila mmoja idadi, 406 00:18:02,320 --> 00:18:05,060 ili slide ndani eneo lake sahihi. 407 00:18:05,060 --> 00:18:10,760 Hivyo hata kama urefu wa hii mchoro ni wa kawaida logi n ya n au 3, 408 00:18:10,760 --> 00:18:13,860 hasa, kwa maneno mengine, Nilifanya tarafa tatu hapa. 409 00:18:13,860 --> 00:18:18,800 Kiasi gani kazi mimi kufanya hakuwa usawa pamoja mchoro huu kila wakati? 410 00:18:18,800 --> 00:18:21,110 >> Naam, mimi hatua n ya kazi, kwa sababu kama mimi wameweza 411 00:18:21,110 --> 00:18:24,080 got mambo manne na mambo manne, na mimi haja ya kuunganisha yao kwa pamoja. 412 00:18:24,080 --> 00:18:26,040 Mimi haja ya kwenda kwa hizi nne na hizi nne, 413 00:18:26,040 --> 00:18:28,123 hatimaye kwa kuunganisha yao nyuma katika mambo nane. 414 00:18:28,123 --> 00:18:32,182 Kama kinyume chake Mimi nimepata vidole nane zaidi ya hapa, ambayo mimi hawana, na nane 415 00:18:32,182 --> 00:18:34,390 fingers-- sorry-- Kama nimepata got vidole vinne zaidi ya hapa, 416 00:18:34,390 --> 00:18:37,380 ambayo mimi kufanya, vidole vinne zaidi ya hapa, ambayo mimi kufanya, 417 00:18:37,380 --> 00:18:40,590 basi hiyo ni sawa mfano kama kabla, kama mimi kufanya 418 00:18:40,590 --> 00:18:44,010 na vidole nane ingawa katika jumla, ambayo siwezi, aina ya, kufanya. 419 00:18:44,010 --> 00:18:47,950 Siwezi hasa kufanya hapa, kisha naweza hakika 420 00:18:47,950 --> 00:18:50,370 kuunganisha wote wa orodha hizi ya kawaida ya 1 pamoja. 421 00:18:50,370 --> 00:18:54,050 Lakini mimi hakika na kuangalia katika kila kipengele hasa mara moja. 422 00:18:54,050 --> 00:18:59,640 Hivyo urefu wa mchakato huu ni gogo n, upana wa mchakato huu, ili kuzungumza, 423 00:18:59,640 --> 00:19:02,490 ni n, hivyo nini tunaonekana kuwa na, hatimaye, ni 424 00:19:02,490 --> 00:19:06,470 wakati mbio za ukubwa n mara logi n. 425 00:19:06,470 --> 00:19:08,977 >> Kwa maneno mengine, sisi kugawanywa orodha, gogo n nyakati, 426 00:19:08,977 --> 00:19:11,810 lakini kila wakati sisi alifanya hivyo, tulikuwa na kugusa kila moja ya mambo 427 00:19:11,810 --> 00:19:13,560 ili kuunganisha yao wote kwa pamoja, ambayo 428 00:19:13,560 --> 00:19:18,120 ilikuwa n hatua, hivyo tuna n mara logi n, au kama kompyuta mwanasayansi kusema, 429 00:19:18,120 --> 00:19:20,380 asymptotically, ambayo itakuwa ni neno kubwa 430 00:19:20,380 --> 00:19:22,810 kuelezea juu amefungwa kwa wakati kukimbia, 431 00:19:22,810 --> 00:19:28,010 sisi ni mbio katika o kubwa ya gogo n mara, hivyo kusema. 432 00:19:28,010 --> 00:19:31,510 >> Sasa hii ni muhimu, kwa sababu kukumbuka nini nyakati mbio walikuwa 433 00:19:31,510 --> 00:19:34,120 na Bubble aina, na uteuzi aina, na kuingizwa aina, 434 00:19:34,120 --> 00:19:38,200 na wengine hata chache ambazo zipo, n squared ilikuwa ambapo tulikuwa kwa. 435 00:19:38,200 --> 00:19:39,990 Na unaweza, aina ya, kuona hii hapa. 436 00:19:39,990 --> 00:19:45,720 Kama n squared ni wazi n mara n, lakini hapa tuna n mara logi n, 437 00:19:45,720 --> 00:19:48,770 na sisi tayari kujua kutoka wiki sifuri, kwamba n gogo, logarithmic, 438 00:19:48,770 --> 00:19:50,550 ni bora kuliko kitu linear. 439 00:19:50,550 --> 00:19:52,930 Baada ya yote, kukumbuka picha na nyekundu na njano 440 00:19:52,930 --> 00:19:56,500 na mistari ya kijani ambayo tulianzisha, kijani logarithmic line ilikuwa chini sana. 441 00:19:56,500 --> 00:20:00,920 Na kwa hiyo, bora zaidi na kwa kasi kuliko moja kwa moja mistari ya njano na nyekundu, 442 00:20:00,920 --> 00:20:05,900 n mara logi n ni, kwa kweli, bora ya mara n n, au n squared. 443 00:20:05,900 --> 00:20:09,110 >> Kwa hiyo sisi tunaonekana kuwa na kutambuliwa algorithm kuunganisha 444 00:20:09,110 --> 00:20:11,870 aina hiyo inaendesha katika kiasi wakati kasi, na kwa kweli, 445 00:20:11,870 --> 00:20:16,560 hiyo ndiyo sababu, mapema wiki hii, wakati tumeona kwamba mashindano kati ya Bubble 446 00:20:16,560 --> 00:20:20,750 aina, uteuzi aina, na kuunganisha aina, kuunganisha aina kweli, kweli alishinda. 447 00:20:20,750 --> 00:20:23,660 Na hakika, sisi hawakuwa hata kusubiri kwa Bubble aina na uteuzi aina 448 00:20:23,660 --> 00:20:24,790 kumaliza. 449 00:20:24,790 --> 00:20:27,410 >> Sasa hebu kuchukua wengine kupitisha moja wakati huu, kutokana na kidogo zaidi 450 00:20:27,410 --> 00:20:31,030 mtazamo rasmi, tu katika kesi, hii resonates bora 451 00:20:31,030 --> 00:20:33,380 kuliko ile ngazi mjadala juu. 452 00:20:33,380 --> 00:20:34,880 Hivyo hapa ni algorithm tena. 453 00:20:34,880 --> 00:20:36,770 Hebu tujiulize, nini wakati mbio 454 00:20:36,770 --> 00:20:39,287 ni ya hii algorithms hatua mbalimbali? 455 00:20:39,287 --> 00:20:41,620 Hebu kuigawanya katika kwanza kesi na kesi ya pili. 456 00:20:41,620 --> 00:20:46,280 Kama na kingine Katika kesi IF, Kama n ni chini ya 2, kurudi tu. 457 00:20:46,280 --> 00:20:47,580 Anahisi kama wakati mara kwa mara. 458 00:20:47,580 --> 00:20:50,970 Ni, aina ya, kama hatua mbili, Kama n ni chini ya 2, kisha kurudi. 459 00:20:50,970 --> 00:20:54,580 Lakini kama sisi alisema Jumatatu, wakati mara kwa mara, au kubwa o ya 1, 460 00:20:54,580 --> 00:20:57,130 inaweza kuwa hatua mbili, tatu hatua, hata hatua 1,000. 461 00:20:57,130 --> 00:20:59,870 Kitu muhimu ni kwamba ni idadi ya mara kwa mara ya hatua. 462 00:20:59,870 --> 00:21:03,240 Hivyo njano yalionyesha pseudocode hapa anaendesha katika, tutaweza simu yake, 463 00:21:03,240 --> 00:21:04,490 wakati mara kwa mara. 464 00:21:04,490 --> 00:21:06,780 Hivyo zaidi rasmi, na tunakwenda to-- hii 465 00:21:06,780 --> 00:21:09,910 itakuwa ni kwa kiasi gani sisi kurasimisha haki hii now-- T ya n, 466 00:21:09,910 --> 00:21:15,030 wakati mbio za tatizo kwamba inachukua n somethings kama pembejeo, 467 00:21:15,030 --> 00:21:19,150 sawa kubwa o ya moja, Kama n ni chini ya 2. 468 00:21:19,150 --> 00:21:20,640 Hivyo ni masharti juu ya jambo hilo. 469 00:21:20,640 --> 00:21:24,150 Hivyo kuwa wazi, IF n ni chini ya 2, tuna orodha fupi sana, kisha 470 00:21:24,150 --> 00:21:29,151 mbio wakati, T ya n, ambapo n ni 1 au 0, katika kesi hii maalum sana, 471 00:21:29,151 --> 00:21:30,650 ni tu kwenda kuwa wakati mara kwa mara. 472 00:21:30,650 --> 00:21:32,691 Ni kwenda kuchukua moja hatua, hatua mbili, chochote. 473 00:21:32,691 --> 00:21:33,950 Ni fasta idadi ya hatua. 474 00:21:33,950 --> 00:21:38,840 >> Hivyo sehemu Juicy lazima hakika kuwa katika kesi nyingine katika pseudocode. 475 00:21:38,840 --> 00:21:40,220 Kingine kesi. 476 00:21:40,220 --> 00:21:44,870 Aina ya kushoto nusu ya vipengele, aina haki nusu ya vipengele, kuunganisha halves Iliyopangwa. 477 00:21:44,870 --> 00:21:46,800 Muda gani kila moja ya hatua hizo kuchukua? 478 00:21:46,800 --> 00:21:49,780 Naam, kama mbio muda wa kutatua mambo n 479 00:21:49,780 --> 00:21:53,010 ni, hebu simu yake sana yaliyotokea, T ya n, 480 00:21:53,010 --> 00:21:55,500 kisha kuchagua kushoto nusu ya mambo 481 00:21:55,500 --> 00:21:59,720 ni, aina ya, kama kusema, T ya n kugawanywa na 2, 482 00:21:59,720 --> 00:22:03,000 na vile vile kuchagua nusu haki wa mambo ni, aina ya, kama kusema, 483 00:22:03,000 --> 00:22:06,974 T ya n kugawanywa 2, na kisha kuunganisha nusu yamepangwa. 484 00:22:06,974 --> 00:22:08,890 Naam kama mimi nimepata baadhi idadi ya vipengele hapa, 485 00:22:08,890 --> 00:22:11,230 kama wanne, na baadhi ya idadi wa mambo hapa, kama wanne, 486 00:22:11,230 --> 00:22:14,650 na nina kuunganisha kila moja ya haya nne katika, na kila moja ya haya nne katika, moja 487 00:22:14,650 --> 00:22:17,160 baada ya nyingine, ili hatimaye nina mambo nane. 488 00:22:17,160 --> 00:22:20,230 Ni anahisi kama hiyo ni kubwa o ya hatua n? 489 00:22:20,230 --> 00:22:23,500 Kama mimi nimepata n vidole na kila mmoja wao ana kuwa zimeunganishwa katika nafasi, 490 00:22:23,500 --> 00:22:25,270 hiyo ni kama hatua nyingine n. 491 00:22:25,270 --> 00:22:27,360 >> Hivyo kweli formulaically, tunaweza kueleza hayo, 492 00:22:27,360 --> 00:22:29,960 angalau scarily kidogo kwa mara ya kwanza mtazamo, lakini ni kitu 493 00:22:29,960 --> 00:22:31,600 kwamba Ukamataji hasa mantiki hiyo. 494 00:22:31,600 --> 00:22:35,710 Wakati mbio, T ya n, IF n ni mkubwa kuliko au sawa na 2. 495 00:22:35,710 --> 00:22:42,500 Katika kesi hiyo, kesi kingine, ni T ya n kugawanywa na 2, pamoja na T ya N kugawanywa na 2, 496 00:22:42,500 --> 00:22:45,320 pamoja na kubwa o ya n, baadhi linear Idadi ya hatua, 497 00:22:45,320 --> 00:22:51,630 labda hasa n, labda mara 2 n, lakini ni takribani, utaratibu wa n. 498 00:22:51,630 --> 00:22:54,060 Hivyo kwamba, pia, ndivyo tunaweza kueleza hii formulaically. 499 00:22:54,060 --> 00:22:56,809 Sasa bila kujua hii isipokuwa umefanya kumbukumbu katika akili yako, 500 00:22:56,809 --> 00:22:58,710 au kuangalia ni juu katika nyuma ya vitabu vya kiada, kwamba 501 00:22:58,710 --> 00:23:00,501 anaweza kuwa kidogo kudanganya karatasi mwishoni, 502 00:23:00,501 --> 00:23:03,940 lakini hii ni, kwa kweli, kwenda kutupa kubwa o ya n logi n, 503 00:23:03,940 --> 00:23:06,620 kwa sababu kujirudia kwamba wewe ni kuona hapa kwenye screen, 504 00:23:06,620 --> 00:23:09,550 kama kweli alifanya hivyo nje, na idadi ya usio wa mifano, 505 00:23:09,550 --> 00:23:13,000 au alifanya hivyo formulaically, ungekuwa kuona kwamba hii, kwa sababu utaratibu huu 506 00:23:13,000 --> 00:23:17,100 yenyewe ni kujirudia, na t ya n juu ya jambo fulani juu ya haki, 507 00:23:17,100 --> 00:23:21,680 na t ya n juu ya upande wa kushoto, hii inaweza kweli kuwa walionyesha, hatimaye, 508 00:23:21,680 --> 00:23:24,339 kama kubwa kwenda ya n logi n. 509 00:23:24,339 --> 00:23:26,130 Kama si wanaamini, hiyo ni faini kwa sasa, tu 510 00:23:26,130 --> 00:23:28,960 kuchukua imani, kwamba hiyo ni, kwa kweli, nini kwamba kujirudia inaongoza kwa, 511 00:23:28,960 --> 00:23:31,780 lakini hii ni kidogo tu zaidi ya mbinu za hisabati kwa kuangalia 512 00:23:31,780 --> 00:23:36,520 wakati mbio za kuunganisha aina kulingana na pseudocode wake peke yake. 513 00:23:36,520 --> 00:23:39,030 >> Sasa hebu kuchukua kidogo ya pumzi kutokana na yote hayo, 514 00:23:39,030 --> 00:23:41,710 na tuangalie fulani aliyekuwa seneta, ambaye 515 00:23:41,710 --> 00:23:44,260 ili kuangalia ukoo kidogo, ambao alikaa chini na Eric Google 516 00:23:44,260 --> 00:23:48,410 Schmidt, baadhi ya wakati uliopita, kwa ajili ya mahojiano juu ya hatua, mbele ya kundi zima 517 00:23:48,410 --> 00:23:53,710 ya watu, kuzungumza hatimaye kuhusu mada, kwamba ni pretty sasa ukoo. 518 00:23:53,710 --> 00:23:54,575 Hebu tuangalie. 519 00:23:54,575 --> 00:24:01,020 520 00:24:01,020 --> 00:24:03,890 >> ERIC SCHMIDT: Sasa Seneta, uko hapa katika Google, 521 00:24:03,890 --> 00:24:09,490 na mimi kama kufikiria urais kama mahojiano ya kazi. 522 00:24:09,490 --> 00:24:11,712 Sasa ni vigumu kupata kazi kama rais. 523 00:24:11,712 --> 00:24:12,670 RAIS OBAMA: Haki. 524 00:24:12,670 --> 00:24:13,940 ERIC SCHMIDT: Na wewe ni kwenda kufanya [inaudible] sasa. 525 00:24:13,940 --> 00:24:15,523 Ni pia vigumu kupata kazi katika Google. 526 00:24:15,523 --> 00:24:17,700 RAIS OBAMA: Haki. 527 00:24:17,700 --> 00:24:21,330 >> ERIC SCHMIDT: Tuna maswali, na tunaomba wagombea wetu maswali, 528 00:24:21,330 --> 00:24:24,310 na hii ni moja ya kutoka Larry Schwimmer. 529 00:24:24,310 --> 00:24:25,890 >> RAIS OBAMA: Sawa. 530 00:24:25,890 --> 00:24:27,005 >> ERIC SCHMIDT: nini? 531 00:24:27,005 --> 00:24:28,130 Guys kufikiri mimi nina kidding? 532 00:24:28,130 --> 00:24:30,590 Ni haki hapa. 533 00:24:30,590 --> 00:24:33,490 Ni njia bora zaidi ya kile aina milioni 32 kidogo integers? 534 00:24:33,490 --> 00:24:37,560 535 00:24:37,560 --> 00:24:38,979 >> RAIS OBAMA: Well-- 536 00:24:38,979 --> 00:24:41,020 ERIC SCHMIDT: Wakati mwingine, labda mimi nina pole, maybe-- 537 00:24:41,020 --> 00:24:42,750 RAIS OBAMA: Hapana, hapana, hapana, hapana, hapana, mimi think-- 538 00:24:42,750 --> 00:24:43,240 ERIC SCHMIDT: Hiyo si it-- 539 00:24:43,240 --> 00:24:45,430 RAIS OBAMA: Mimi kufikiri, nadhani Bubble 540 00:24:45,430 --> 00:24:46,875 aina itakuwa njia sahihi ya kwenda. 541 00:24:46,875 --> 00:24:49,619 542 00:24:49,619 --> 00:24:50,535 ERIC SCHMIDT: Haya. 543 00:24:50,535 --> 00:24:52,200 Ambaye alimwambia hivi? 544 00:24:52,200 --> 00:24:54,020 SAWA. 545 00:24:54,020 --> 00:24:55,590 Mimi si sayansi ya kompyuta on-- 546 00:24:55,590 --> 00:24:58,986 >> RAIS OBAMA: Tumekuwa got wapelelezi wetu huko. 547 00:24:58,986 --> 00:24:59,860 PROFESA: zote haki. 548 00:24:59,860 --> 00:25:03,370 Hebu kuondoka nyuma yetu sasa dunia ya kinadharia ya algorithms 549 00:25:03,370 --> 00:25:06,520 katika uchambuzi asymptotic yake, na kurudi baadhi ya mada 550 00:25:06,520 --> 00:25:09,940 kutoka wiki sifuri na moja, na kuanza kuondoa baadhi ya magurudumu mafunzo, 551 00:25:09,940 --> 00:25:10,450 kama wewe. 552 00:25:10,450 --> 00:25:13,241 Hivyo kwamba kwa kweli kuelewa hatimaye kutoka ardhini hadi, nini 553 00:25:13,241 --> 00:25:16,805 kinachoendelea chini ya Hood, wakati kuandika, kukusanya, na kutekeleza mipango. 554 00:25:16,805 --> 00:25:19,680 Kumbuka hasa, kwamba hii ilikuwa ni kwanza C mpango sisi inaonekana katika, 555 00:25:19,680 --> 00:25:22,840 kisheria, rahisi mpango ya kila aina, kiasi kuzungumza, 556 00:25:22,840 --> 00:25:24,620 eti, ni Prints, Hello World. 557 00:25:24,620 --> 00:25:27,610 Na kukumbuka kuwa nilisema mchakato kwamba chanzo kanuni hupitia 558 00:25:27,610 --> 00:25:28,430 ni hasa hili. 559 00:25:28,430 --> 00:25:31,180 Wewe kuchukua chanzo kanuni yako, kupita hivyo kwa njia ya compiler, kama Clang, 560 00:25:31,180 --> 00:25:34,650 na nje anakuja kitu kificho kwamba ili kuangalia kama hii, zeros na ndio 561 00:25:34,650 --> 00:25:37,880 kwamba CPU kompyuta, kati usindikaji kitengo au ubongo, 562 00:25:37,880 --> 00:25:39,760 hatimaye anaelewa. 563 00:25:39,760 --> 00:25:42,460 >> Ni zinageuka kuwa hiyo ni kidogo ya kurahisisha, 564 00:25:42,460 --> 00:25:44,480 kuwa tuko sasa katika nafasi ya tease mbali 565 00:25:44,480 --> 00:25:46,720 kuelewa nini kweli imekuwa kinachoendelea chini ya Hood 566 00:25:46,720 --> 00:25:48,600 kila wakati wewe kukimbia Clang, au zaidi kwa ujumla, 567 00:25:48,600 --> 00:25:53,040 kila wakati wewe kufanya mpango, kutumia Tengeneza na CF 50 IDE. 568 00:25:53,040 --> 00:25:56,760 Hasa, mambo kama hii ni ya kwanza yanayotokana, 569 00:25:56,760 --> 00:25:58,684 wakati wa kwanza kukusanya mpango wako. 570 00:25:58,684 --> 00:26:00,600 Kwa maneno mengine, wakati kuchukua chanzo kanuni yako 571 00:26:00,600 --> 00:26:04,390 na kukusanya ni, nini kwanza kuwa outputted na Clang 572 00:26:04,390 --> 00:26:06,370 ni kitu inayojulikana kama mkutano kificho. 573 00:26:06,370 --> 00:26:08,990 Na kwa kweli, inaonekana hasa kama hii. 574 00:26:08,990 --> 00:26:11,170 >> Mimi mbio amri katika mstari amri mapema. 575 00:26:11,170 --> 00:26:16,260 Clang dash mji mkuu wa hello.c, na hii kuundwa faili 576 00:26:16,260 --> 00:26:19,490 kwa ajili yangu aitwaye hello.s, ndani ya ambayo yalikuwa hasa 577 00:26:19,490 --> 00:26:22,290 yaliyomo hizi, na zaidi kidogo juu na kidogo zaidi chini, 578 00:26:22,290 --> 00:26:25,080 lakini nimekuwa kuweka juiciest habari hapa kwenye screen. 579 00:26:25,080 --> 00:26:29,190 Na kama ukiangalia kwa karibu, utaona angalau chache ukoo maneno. 580 00:26:29,190 --> 00:26:31,330 Tuna kuu juu. 581 00:26:31,330 --> 00:26:35,140 Tuna printf chini katikati. 582 00:26:35,140 --> 00:26:38,670 Na sisi pia kuwa hujambo dunia backslash n katika quotes chini chini. 583 00:26:38,670 --> 00:26:42,450 >> Na kila kitu kingine katika hapa ni maelekezo ya chini sana kiwango cha 584 00:26:42,450 --> 00:26:45,500 kwamba CPU kompyuta anaelewa. 585 00:26:45,500 --> 00:26:50,090 Maelekezo CPU kwamba hoja kumbukumbu kote, kwamba masharti mzigo kutokana na kumbukumbu, 586 00:26:50,090 --> 00:26:52,750 na hatimaye, magazeti mambo kwenye screen. 587 00:26:52,750 --> 00:26:56,780 Sasa nini kinatokea ingawa baada ya huu kificho mkutano ni kuzalisha? 588 00:26:56,780 --> 00:26:59,964 Hatimaye, kufanya, kwa kweli, bado kuzalisha kitu kificho. 589 00:26:59,964 --> 00:27:02,630 Lakini hatua ambazo zina kweli wamekuwa kinachoendelea chini ya Hood 590 00:27:02,630 --> 00:27:04,180 kuangalia kidogo zaidi kama hii. 591 00:27:04,180 --> 00:27:08,390 Chanzo kanuni inakuwa mkutano kificho, ambayo kisha inakuwa kitu kificho, 592 00:27:08,390 --> 00:27:11,930 na maneno operative hapa ni kwamba, wakati kukusanya chanzo kanuni yako, 593 00:27:11,930 --> 00:27:16,300 nje anakuja mkutano kificho, na kisha wakati wewe kukusanyika mkutano kanuni yako, 594 00:27:16,300 --> 00:27:17,800 nje anakuja kitu kificho. 595 00:27:17,800 --> 00:27:20,360 >> Sasa Clang ni super kisasa, kama mengi ya compilers, 596 00:27:20,360 --> 00:27:23,151 na ni gani hatua zote hizi pamoja, na ni gani si lazima 597 00:27:23,151 --> 00:27:25,360 pato yoyote kati mafaili kwamba unaweza hata kuona. 598 00:27:25,360 --> 00:27:28,400 Ni tu inaandaa mambo, ambayo ni neno la jumla kwamba 599 00:27:28,400 --> 00:27:30,000 inaelezea mchakato mzima huu. 600 00:27:30,000 --> 00:27:32,000 Lakini kama kweli unataka kuwa fulani, kuna 601 00:27:32,000 --> 00:27:34,330 mengi zaidi kinachoendelea huko pia. 602 00:27:34,330 --> 00:27:38,860 >> Lakini hebu fikiri sasa kwamba hata kuwa super rahisi mpango, hello.c, 603 00:27:38,860 --> 00:27:40,540 aitwaye kazi. 604 00:27:40,540 --> 00:27:41,870 Ni wito printf. 605 00:27:41,870 --> 00:27:46,900 Lakini sikuweza kuandika printf, kwa hakika, kuja na c, hivyo kusema. 606 00:27:46,900 --> 00:27:51,139 Ni kazi wanakumbuka kwamba ni alitangaza katika kiwango io.h, ambayo 607 00:27:51,139 --> 00:27:53,180 ni header faili, ambayo ni mada tutaweza kweli 608 00:27:53,180 --> 00:27:55,780 mbizi katika kina zaidi kabla ya muda mrefu. 609 00:27:55,780 --> 00:27:58,000 Lakini mpira wa kichwa faili ni kawaida akifuatana 610 00:27:58,000 --> 00:28:02,920 na kanuni faili, chanzo kanuni faili, hivyo kiasi kama kuna kiwango io.h. 611 00:28:02,920 --> 00:28:05,930 >> Wakati fulani uliopita, mtu, au someones, pia aliandika 612 00:28:05,930 --> 00:28:11,040 faili inayoitwa kiwango io.c, katika ambayo ufafanuzi halisi, 613 00:28:11,040 --> 00:28:15,220 au utekelezaji wa printf, na mashada ya kazi nyingine, 614 00:28:15,220 --> 00:28:16,870 ni kweli imeandikwa. 615 00:28:16,870 --> 00:28:22,140 Hivyo kutokana na kwamba, kama tunaona kuwa hapa upande wa kushoto, hello.c, kwamba wakati 616 00:28:22,140 --> 00:28:26,250 ulioandaliwa, inatupa hello.s, hata kama Clang haina bother kuokoa katika sehemu 617 00:28:26,250 --> 00:28:31,360 tunaweza kuona hilo, na kwamba mkutano kificho anapata wamekusanyika katika hello.o, ambayo 618 00:28:31,360 --> 00:28:34,630 ni, kwa kweli, jina chaguo-msingi kutokana na wakati wowote kukusanya chanzo 619 00:28:34,630 --> 00:28:39,350 kanuni katika kitu kificho, lakini si kabisa tayari nitafanya hivyo bado, 620 00:28:39,350 --> 00:28:41,460 kwa sababu hatua nyingine ina kutokea, na ina 621 00:28:41,460 --> 00:28:44,440 imekuwa ikitokea kwa michache iliyopita wiki, labda unbeknownst wewe. 622 00:28:44,440 --> 00:28:47,290 >> Hasa mahali fulani katika CS50 IDE, na hii, 623 00:28:47,290 --> 00:28:49,870 pia, itakuwa kidogo ya kurahisisha kwa muda, 624 00:28:49,870 --> 00:28:54,670 kuna, au ilikuwa juu ya muda, faili inayoitwa kiwango io.c, 625 00:28:54,670 --> 00:28:58,440 kwamba mtu ulioandaliwa katika io.s kiwango au sawa, 626 00:28:58,440 --> 00:29:02,010 kwamba mtu kisha wamekusanyika ndani ya kiwango cha io.o, 627 00:29:02,010 --> 00:29:04,600 au ni zamu nje katika faili tofauti kidogo 628 00:29:04,600 --> 00:29:07,220 muundo ambayo yanaweza kuwa tofauti faili ugani kabisa, 629 00:29:07,220 --> 00:29:11,720 lakini katika nadharia na conceptually, hasa hatua hizo alikuwa kutokea kwa namna fulani. 630 00:29:11,720 --> 00:29:14,060 Ambayo ni kusema, kwamba sasa wakati mimi nina kuandika mpango, 631 00:29:14,060 --> 00:29:17,870 hello.c, kwamba tu anasema, hujambo dunia, na mimi nina kutumia kanuni ya mtu mwingine 632 00:29:17,870 --> 00:29:22,480 kama printf, ambayo mara kwa mara nyingine juu ya muda, katika faili inayoitwa kiwango io.c, 633 00:29:22,480 --> 00:29:26,390 kisha kwa namna fulani mimi kuwa na kuchukua yangu kitu kificho, zeros yangu na ndio, 634 00:29:26,390 --> 00:29:29,260 na mtu huyo kitu kanuni, au zeros na ndio, 635 00:29:29,260 --> 00:29:34,970 na kwa namna fulani kiungo wao pamoja katika faili moja la mwisho, aitwaye hello, kwamba 636 00:29:34,970 --> 00:29:38,070 ina wote wa zeros na wale wa kutoka kazi yangu kuu, 637 00:29:38,070 --> 00:29:40,830 na wote wa zeros na ndio kwa printf. 638 00:29:40,830 --> 00:29:44,900 >> Na hakika, kwamba mchakato wa mwisho ni kuitwa, kuunganisha kitu kificho yako. 639 00:29:44,900 --> 00:29:47,490 Pato la ambayo ni faili la kutekelezwa. 640 00:29:47,490 --> 00:29:49,780 Hivyo katika haki, katika Mwisho wa siku, chochote 641 00:29:49,780 --> 00:29:52,660 imebadilika tangu wiki moja, wakati sisi kwanza ilianza kuandaa mipango. 642 00:29:52,660 --> 00:29:55,200 Kwa hakika, yote haya yamekuwa kinachotokea chini ya Hood, 643 00:29:55,200 --> 00:29:57,241 lakini sasa tuko katika nafasi ambapo tunaweza kweli 644 00:29:57,241 --> 00:29:58,794 tease mbali hatua hizi mbalimbali. 645 00:29:58,794 --> 00:30:00,710 Na hakika, mwishoni mwa wa siku, bado tuko 646 00:30:00,710 --> 00:30:04,480 kushoto na zeros na ndio, ambayo ni kweli segue kubwa sasa 647 00:30:04,480 --> 00:30:08,620 kwa uwezo mwingine wa C, kwamba tumekuwa si alikuwa na kujiinua na uwezo mkubwa 648 00:30:08,620 --> 00:30:11,250 hadi sasa, unaojulikana kama bitwise waendeshaji. 649 00:30:11,250 --> 00:30:15,220 Kwa maneno mengine, hivi sasa, wakati wowote tumekuwa kushughulikiwa na data katika C au vigezo katika C, 650 00:30:15,220 --> 00:30:17,660 tulikuwa na mambo kama chars na ikifungwa na ins 651 00:30:17,660 --> 00:30:21,990 na anatamani na mara mbili na kama, lakini wote wa wale ni vipande angalau nane. 652 00:30:21,990 --> 00:30:25,550 Tumekuwa kamwe bado na uwezo wa kuendesha bits mtu binafsi, 653 00:30:25,550 --> 00:30:28,970 hata kama mtu binafsi kidogo, sisi kujua, wanaweza kuwakilisha 0 na 1. 654 00:30:28,970 --> 00:30:32,640 Sasa ni zamu kuwa katika C, wewe wanaweza kupata vipande ya mtu binafsi, 655 00:30:32,640 --> 00:30:35,530 kama unajua syntax, na ambayo kwa kupata kwao. 656 00:30:35,530 --> 00:30:38,010 >> Hivyo hebu tuangalie katika bitwise waendeshaji. 657 00:30:38,010 --> 00:30:41,700 Hivyo pichani hapa ni ishara chache kuwa tumekuwa, aina ya, aina ya, kuona mbele. 658 00:30:41,700 --> 00:30:45,580 Mimi naona ampersand, wima bar, na baadhi ya watu wengine pia, 659 00:30:45,580 --> 00:30:49,430 na kukumbuka kuwa ampersand ampersand ni kitu tumeona kabla. 660 00:30:49,430 --> 00:30:54,060 Mantiki NA operator, ambapo una wawili kati yao pamoja, au mantiki AU 661 00:30:54,060 --> 00:30:56,300 operator, ambapo na baa mbili wima. 662 00:30:56,300 --> 00:31:00,550 Bitwise waendeshaji, ambayo tutaweza ona kazi juu ya bits mmoja mmoja, 663 00:31:00,550 --> 00:31:03,810 tu kutumia ampersand moja, moja wima bar, ishara kareti 664 00:31:03,810 --> 00:31:06,620 huja ijayo, kidogo tilde, na kisha kushoto 665 00:31:06,620 --> 00:31:08,990 mabano kushoto mabano, au haki mabano mabano haki. 666 00:31:08,990 --> 00:31:10,770 Kila moja ya haya kuwa na maana tofauti. 667 00:31:10,770 --> 00:31:11,950 >> Kwa kweli, hebu tuangalie. 668 00:31:11,950 --> 00:31:16,560 Hebu kwenda wa zamani shule leo, na matumizi screen kugusa kutoka yesteryear, 669 00:31:16,560 --> 00:31:18,002 inayojulikana kama bodi nyeupe. 670 00:31:18,002 --> 00:31:19,710 Na bodi hii nyeupe ni kwenda kuruhusu sisi 671 00:31:19,710 --> 00:31:27,360 kueleza baadhi ya alama haki rahisi, au tuseme baadhi ya kanuni haki rahisi, 672 00:31:27,360 --> 00:31:29,560 kwamba tunaweza kisha hatimaye kujiinua, ili 673 00:31:29,560 --> 00:31:33,230 kupata mtu binafsi bits ndani ya C mpango. 674 00:31:33,230 --> 00:31:34,480 Kwa maneno mengine, hebu kufanya hivyo. 675 00:31:34,480 --> 00:31:37,080 Hebu majadiliano kwanza kwa muda juu ampersand, 676 00:31:37,080 --> 00:31:39,560 ambayo ni bitwise NA operator. 677 00:31:39,560 --> 00:31:42,130 Kwa maneno mengine, hii ni alama ambayo inaruhusu 678 00:31:42,130 --> 00:31:45,930 yangu kuwa mkono wa kushoto kutofautiana kawaida, na mkono wa kulia kutofautiana, 679 00:31:45,930 --> 00:31:50,640 au thamani ya mtu binafsi, kwamba kama sisi NA nao pamoja, anitiaye matokeo ya mwisho. 680 00:31:50,640 --> 00:31:51,560 Basi je, I mean? 681 00:31:51,560 --> 00:31:54,840 Kama katika mpango, una kutofautiana kwamba maduka moja ya maadili haya, 682 00:31:54,840 --> 00:31:58,000 au hebu kushika ni rahisi, na tu kuandika zeros na ndio mmoja mmoja, 683 00:31:58,000 --> 00:32:00,940 hapa ni jinsi ampersand operator kazi. 684 00:32:00,940 --> 00:32:06,400 0 ampersand 0 kinaenda sawa 0. 685 00:32:06,400 --> 00:32:07,210 Sasa kwa nini ni kwamba? 686 00:32:07,210 --> 00:32:09,291 >> Ni sawa na Maneno Boolean, 687 00:32:09,291 --> 00:32:10,540 kwamba tumekuwa kujadiliwa hivi sasa. 688 00:32:10,540 --> 00:32:15,800 Kama unafikiri baada ya yote, ni 0 uongo, 0 ni uongo, uongo na uongo 689 00:32:15,800 --> 00:32:18,720 ni, kama tumekuwa kujadiliwa kifikra, pia uongo. 690 00:32:18,720 --> 00:32:20,270 Ili tuweze kupata 0 hapa pia. 691 00:32:20,270 --> 00:32:24,390 Kama wewe kuchukua 0 ampersand 1, vizuri kwamba, pia, 692 00:32:24,390 --> 00:32:29,890 ni kwenda kuwa 0, kwa sababu kwa hili mkono wa kushoto kujieleza kuwa ni kweli au 1, 693 00:32:29,890 --> 00:32:32,360 ingekuwa haja ya kuwa ni kweli na kweli. 694 00:32:32,360 --> 00:32:36,320 Lakini hapa tuna uongo na kweli, au 0 na 1. 695 00:32:36,320 --> 00:32:42,000 Sasa tena, kama tuna 1 ampersand 0, kwamba, pia, ni kwenda kuwa 0, 696 00:32:42,000 --> 00:32:47,240 na kama tuna 1 ampersand 1, hatimaye tuna 1 kidogo. 697 00:32:47,240 --> 00:32:50,340 Hivyo kwa maneno mengine, sisi siyo kufanya kitu cha kuvutia na alama hii 698 00:32:50,340 --> 00:32:51,850 bado tu, operator hii ampersand. 699 00:32:51,850 --> 00:32:53,780 Ni bitwise NA operator. 700 00:32:53,780 --> 00:32:57,290 Lakini haya ni viungo kupitia ambayo tunaweza kufanya 701 00:32:57,290 --> 00:32:59,240 mambo ya kuvutia, kama tutaweza hivi karibuni kuona. 702 00:32:59,240 --> 00:33:02,790 >> Sasa hebu tuangalie moja tu wima bar juu hapa juu ya haki. 703 00:33:02,790 --> 00:33:06,710 Kama mimi na 0 kidogo na mimi AU ni pamoja na, bitwise 704 00:33:06,710 --> 00:33:11,030 AU operator, mwingine 0 kidogo, ambayo inaenda nipe 0. 705 00:33:11,030 --> 00:33:17,540 Kama mimi kuchukua 0 kidogo na AU ni pamoja na 1 kidogo, kisha mimi nina kwenda kupata 1. 706 00:33:17,540 --> 00:33:19,830 Na kwa kweli, tu kwa uwazi, napenda kwenda nyuma, 707 00:33:19,830 --> 00:33:23,380 ili baa yangu wima si makosa kwa 1 ya. 708 00:33:23,380 --> 00:33:26,560 Napenda kuandika upya yote ya 1 wangu ni kidogo zaidi 709 00:33:26,560 --> 00:33:32,700 wazi, ili tuweze ijayo kuona, kama mimi 1 AU 0, kwamba kinaendelea kuwa 1, 710 00:33:32,700 --> 00:33:39,060 na kama nina 1 AU 1 kwamba, pia, ni kwenda kuwa 1. 711 00:33:39,060 --> 00:33:42,900 Hivyo unaweza kuona mantiki kwamba AU alama kutenda tofauti sana. 712 00:33:42,900 --> 00:33:48,070 Hii inanipa 0 AU 0 anitiaye 0, lakini kila mchanganyiko mengine anitiaye 1. 713 00:33:48,070 --> 00:33:52,480 Hivyo muda mrefu kama nina moja katika 1 fomula, matokeo ni kwenda kuwa 1. 714 00:33:52,480 --> 00:33:55,580 >> Kwa upande mwingine pamoja na NA operator, ampersand, 715 00:33:55,580 --> 00:34:00,940 tu kama nina mawili 1 katika equation, Je, mimi kwa kweli kupata 1 nje. 716 00:34:00,940 --> 00:34:02,850 Sasa kuna wengine wachache waendeshaji pia. 717 00:34:02,850 --> 00:34:04,810 Mmoja wao ni mdogo zaidi kushiriki. 718 00:34:04,810 --> 00:34:07,980 Hivyo basi mimi kwenda mbele na kufuta hii bure juu ya baadhi ya nafasi. 719 00:34:07,980 --> 00:34:13,020 720 00:34:13,020 --> 00:34:16,460 Na hebu tuangalie ishara kareti, kwa muda tu. 721 00:34:16,460 --> 00:34:18,210 Hii ni kawaida tabia unaweza aina 722 00:34:18,210 --> 00:34:21,420 kwenye keyboard kufanya yako Shift na kisha moja ya idadi atop Marekani yako 723 00:34:21,420 --> 00:34:22,250 keyboard. 724 00:34:22,250 --> 00:34:26,190 >> Hivyo hii ni ya kipekee AU operator, kipekee AU. 725 00:34:26,190 --> 00:34:27,790 Hivyo sisi tu kuona operator AU. 726 00:34:27,790 --> 00:34:29,348 Hii ni ya kipekee AU operator. 727 00:34:29,348 --> 00:34:30,639 Nini kweli tofauti? 728 00:34:30,639 --> 00:34:34,570 Naam hebu tu kuangalia fomula, na kutumia hii kama viungo hatimaye. 729 00:34:34,570 --> 00:34:37,690 0 XOR 0. 730 00:34:37,690 --> 00:34:39,650 Mimi nina kwenda kusema ni daima 0. 731 00:34:39,650 --> 00:34:41,400 Hiyo ni ufafanuzi wa XOR. 732 00:34:41,400 --> 00:34:47,104 0 XOR 1 ni kwenda kuwa 1. 733 00:34:47,104 --> 00:34:58,810 1 XOR 0 ni kwenda kuwa 1, na 1 XOR 1 ni kwenda kuwa? 734 00:34:58,810 --> 00:34:59,890 Kosa? 735 00:34:59,890 --> 00:35:00,520 Au haki? 736 00:35:00,520 --> 00:35:01,860 Sijui. 737 00:35:01,860 --> 00:35:02,810 0. 738 00:35:02,810 --> 00:35:04,700 Sasa ni nini kinaendelea hapa? 739 00:35:04,700 --> 00:35:06,630 Vizuri kufikiria kuhusu jina la operator huu. 740 00:35:06,630 --> 00:35:09,980 Exclusive AU, hivyo kama jina, aina ya, unaonyesha, 741 00:35:09,980 --> 00:35:13,940 jibu ni kwenda tu kuwa 1 kama pembejeo ni ya kipekee, 742 00:35:13,940 --> 00:35:15,560 peke mbalimbali. 743 00:35:15,560 --> 00:35:18,170 Hivyo hapa ni pembejeo huo, hivyo pato ni 0. 744 00:35:18,170 --> 00:35:20,700 Hapa ni pembejeo huo, hivyo pato ni 0. 745 00:35:20,700 --> 00:35:25,640 Hapa ni matokeo ni tofauti, wao ni ya kipekee, na hivyo pato ni 1. 746 00:35:25,640 --> 00:35:28,190 Hivyo ni sawa na NA, ni sawa sana, 747 00:35:28,190 --> 00:35:32,760 au tuseme ni sawa na AU, lakini tu kwa njia ya kipekee. 748 00:35:32,760 --> 00:35:36,210 Hii moja ni tena 1, kwa sababu tuna mbili 1 ya, 749 00:35:36,210 --> 00:35:38,621 na si kwa ajili tu, tu mmoja wao. 750 00:35:38,621 --> 00:35:39,120 Sawa. 751 00:35:39,120 --> 00:35:40,080 Je kuhusu watu wengine? 752 00:35:40,080 --> 00:35:44,220 Naam tilde, wakati huo huo, ni kweli nzuri na rahisi, nashiriki. 753 00:35:44,220 --> 00:35:46,410 Na hii ni unary operator, ambayo ina maana 754 00:35:46,410 --> 00:35:50,400 ni kutumika kwa pembejeo moja tu, operand moja, hivyo kusema. 755 00:35:50,400 --> 00:35:51,800 Si kwa kushoto na kulia. 756 00:35:51,800 --> 00:35:56,050 Kwa maneno mengine, kama wewe kuchukua tilde ya 0, jibu itakuwa kinyume. 757 00:35:56,050 --> 00:35:59,710 Na kama wewe kuchukua tilde ya 1, jibu kutakuwa na kinyume. 758 00:35:59,710 --> 00:36:02,570 Hivyo operator tilde ni njia ya kukataa kidogo, 759 00:36:02,570 --> 00:36:06,000 au flipping kidogo kutoka 0-1, au 1-0. 760 00:36:06,000 --> 00:36:09,820 >> Na kwamba zinatuacha hatimaye na waendeshaji wa mwisho mbili tu, 761 00:36:09,820 --> 00:36:13,840 kinachojulikana kushoto kuhama, na kinachojulikana haki ya kuhama operator. 762 00:36:13,840 --> 00:36:16,620 Hebu tuangalie jinsi wale kazi. 763 00:36:16,620 --> 00:36:20,780 Kushoto kuhama operator, imeandikwa na mabano mbili pembe kama hicho, 764 00:36:20,780 --> 00:36:22,110 kazi kama ifuatavyo. 765 00:36:22,110 --> 00:36:27,390 Kama pembejeo yangu, au operand wangu, kwa upande wa kushoto mabadiliko operator ni rahisi kabisa 1. 766 00:36:27,390 --> 00:36:33,750 Na mimi kisha kuwaambia kompyuta kwa kushoto kuhama kwamba 1, wanasema maeneo saba, 767 00:36:33,750 --> 00:36:37,150 Matokeo yake ni kana kwamba mimi kuchukua kwamba 1, na hoja hiyo 768 00:36:37,150 --> 00:36:40,160 maeneo saba zaidi kwa kushoto, na kwa default, 769 00:36:40,160 --> 00:36:42,270 tunakwenda kudhani kwamba nafasi na haki 770 00:36:42,270 --> 00:36:44,080 ni kwenda kuwa padded na zeros. 771 00:36:44,080 --> 00:36:50,316 Kwa maneno mengine, 1 wa kushoto kuhama 7 ni kwenda kunipa kwamba 1, ikifuatiwa na 1, 2, 3, 772 00:36:50,316 --> 00:36:54,060 4, 5, 6, 7 zeros. 773 00:36:54,060 --> 00:36:57,380 Hivyo katika njia, utapata kuchukua idadi ndogo kama 1, 774 00:36:57,380 --> 00:37:00,740 na kwa uwazi kufanya hivyo mengi sana, kubwa sana kwa njia hii, 775 00:37:00,740 --> 00:37:06,460 lakini sisi ni kweli kwenda kuona mbinu zaidi wajanja kwa kuwa 776 00:37:06,460 --> 00:37:08,080 badala yake, pia, 777 00:37:08,080 --> 00:37:08,720 >> Sawa. 778 00:37:08,720 --> 00:37:10,060 Hiyo ni kwa wiki tatu. 779 00:37:10,060 --> 00:37:11,400 Tutaona wewe wakati ujao. 780 00:37:11,400 --> 00:37:12,770 Hii ilikuwa ni CS50. 781 00:37:12,770 --> 00:37:17,270 782 00:37:17,270 --> 00:37:22,243 >> [Music kucheza] 783 00:37:22,243 --> 00:37:25,766 >> SPIKA 1: Alikuwa katika vitafunio bar kula moto fudge sundae. 784 00:37:25,766 --> 00:37:28,090 Alikuwa ni yote juu ya uso wake. 785 00:37:28,090 --> 00:37:30,506 Yeye amevaa kwamba chocolate kama ndevu 786 00:37:30,506 --> 00:37:31,756 SPIKA 2: unafanya nini? 787 00:37:31,756 --> 00:37:32,422 SPIKA 3: Hmmm? 788 00:37:32,422 --> 00:37:33,500 Nini? 789 00:37:33,500 --> 00:37:36,800 >> SPIKA 2: Je, tu mara mbili kuzamisha? 790 00:37:36,800 --> 00:37:38,585 Wewe mara mbili dipped Chip. 791 00:37:38,585 --> 00:37:39,460 SPIKA 3: Samahani. 792 00:37:39,460 --> 00:37:44,440 SPIKA 2: Wewe limelowekwa Chip, wewe alichukua kuumwa, na wewe limelowekwa tena. 793 00:37:44,440 --> 00:37:44,940 SPIKA 3: 794 00:37:44,940 --> 00:37:48,440 SPIKA 2: Kwa hivyo hiyo ni kama kuweka kinywa nzima haki yako katika kuzamisha. 795 00:37:48,440 --> 00:37:52,400 Wakati mwingine kuchukua Chip, tu kuitia mara moja, na mwisho ni. 796 00:37:52,400 --> 00:37:53,890 >> SPIKA 3: Unajua nini, Dan? 797 00:37:53,890 --> 00:37:58,006 Wewe kuzamisha njia hiyo unataka kuzamisha. 798 00:37:58,006 --> 00:38:01,900 Mimi itabidi kuzamisha njia hiyo nataka kuzamisha. 799 00:38:01,900 --> 00:38:03,194