1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> SPIKA: All haki, hii ni CS50. 3 00:00:14,910 --> 00:00:19,020 Hii ni mwisho wa wiki tatu, na kama una si kuchukuliwa kwa faida tayari, 4 00:00:19,020 --> 00:00:21,790 kujua kuwa kutakuwa na chakula cha mchana Ijumaa hii kama kawaida, ambapo 5 00:00:21,790 --> 00:00:25,430 unaweza kufurahia mazungumzo mazuri na chakula katika Moto na Ice 6 00:00:25,430 --> 00:00:27,980 na baadhi ya CS50 ya wafanyakazi na wanafunzi. 7 00:00:27,980 --> 00:00:30,170 Kichwa na URL hii hapa. 8 00:00:30,170 --> 00:00:33,420 >> Sasa unaweza kukumbuka, au wewe hivi karibuni inaweza kuwa khabari na, 9 00:00:33,420 --> 00:00:35,970 mambo haya hapa, ambayo wanapewa mwishoni 10 00:00:35,970 --> 00:00:37,850 wa muhula kwa ajili ya madarasa mengi. 11 00:00:37,850 --> 00:00:40,870 Mtihani kinachojulikana bluu vitabu, katika ambayo wewe kuandika majibu yako kwa mitihani. 12 00:00:40,870 --> 00:00:44,240 Sasa nina hapa 26 kama vitabu bluu, juu ya kila mmoja wao 13 00:00:44,240 --> 00:00:47,580 imeandikwa jina, A njia ya Z. Na kweli majina ni kuwa rahisi, A 14 00:00:47,580 --> 00:00:50,490 kupitia Z. Na moja ya malengo upande leo 15 00:00:50,490 --> 00:00:53,910 ni kwenda kuwa kuendelea nini sisi ilianza siku ya Jumatatu, ambayo ni si 16 00:00:53,910 --> 00:00:57,830 sana kuangalia code, lakini kwa kweli kuangalia mawazo na utatuzi wa matatizo. 17 00:00:57,830 --> 00:01:00,170 Moja ya malengo na ahadi ya kozi hii 18 00:01:00,170 --> 00:01:02,985 ni kufundisha wewe kufikiri zaidi makini, zaidi methodically, 19 00:01:02,985 --> 00:01:05,400 na kutatua matatizo kwa ufanisi zaidi. 20 00:01:05,400 --> 00:01:09,526 Na hakika, tunaweza kufanya kwamba kweli bila hata kugusa mstari wa kanuni. 21 00:01:09,526 --> 00:01:12,150 Hivyo mimi kuwa wanandoa wa tembo up hapa leo machungwa, na bluu, 22 00:01:12,150 --> 00:01:15,780 kama tunaweza kupata kujitolea moja, labda kutoka mbali nyuma kuliko kawaida. 23 00:01:15,780 --> 00:01:18,070 Vipi kuhusu haki pale, kuja juu chini. 24 00:01:18,070 --> 00:01:24,180 lengo la ambayo ni kwenda kuwa kwa msaada pamoja na kusimamia mtihani huu hapa. 25 00:01:24,180 --> 00:01:24,935 Nini jina lako? 26 00:01:24,935 --> 00:01:25,768 >> Watazamaji: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 SPIKA: Mary Beth, kuja juu up. 28 00:01:27,560 --> 00:01:29,560 Hebu kupata kipaza sauti hapa kwa ajili yenu. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Nice kukutana na wewe. 31 00:01:32,880 --> 00:01:34,005 >> Watazamaji: Nice kukutana na wewe. 32 00:01:34,005 --> 00:01:36,790 SPIKA: zote haki, hivyo nina hapa bluu vitabu A kupitia Z, 33 00:01:36,790 --> 00:01:41,680 na mimi nina kwenda kwa kujifanya kuwa Nina mmoja wa wanafunzi, 34 00:01:41,680 --> 00:01:45,770 na wao ni kuja katika kiasi fulani nasibu mwishoni mwa saa tatu mtihani kuzuia, 35 00:01:45,770 --> 00:01:49,400 hivyo ni kuishia katika baadhi Ili nusu random kama hii. 36 00:01:49,400 --> 00:01:54,510 Sasa kazi yako katika muda tu ni kwenda kwa be-- hii ni kweli jinsi ya kupata 37 00:01:54,510 --> 00:01:56,820 akageuka katika mwishoni mwa darasa, uwezekano mkubwa. 38 00:01:56,820 --> 00:02:01,120 Kazi yako sasa ni kwenda kuwa, kabisa tu, kwa aina vitabu hizi za bluu kwa ajili yetu 39 00:02:01,120 --> 00:02:05,220 kutoka kwa Z. A 40 00:02:05,220 --> 00:02:08,400 >> Watazamaji: Oh, hii ni kwenda kuchukua milele. 41 00:02:08,400 --> 00:02:13,747 >> SPIKA: Na sisi kuangalia kama wewe kufanya hili, hakuna shinikizo. 42 00:02:13,747 --> 00:02:15,330 Watazamaji: Hapana, hakuna shinikizo au kitu chochote. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> SPIKA: Na kwa ajili ya kujifurahisha, hebu kuweka up timer. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> Watazamaji: furaha sana, furaha sana. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> SPIKA: naweza kushikilia mic kwa ajili yenu. 49 00:02:38,574 --> 00:02:40,240 Haki wote, tumekuwa tu mara mbili kasi yetu. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Hivyo katika huo huo, napenda pose nini kwenda kuwa swali kwa Mary Beth 52 00:02:49,060 --> 00:02:51,540 ni nini yeye kufanya, ni jinsi gani yeye kwenda juu ya kutatua hili? 53 00:02:51,540 --> 00:02:54,040 Na kwa kweli, unaweza kuwa na milele mawazo kuhusu kitu 54 00:02:54,040 --> 00:02:57,440 rahisi sana kama wakati pick up 26 vitabu kama hii, 55 00:02:57,440 --> 00:02:59,350 ambao hawana kuwa na asili kuagiza kwao. 56 00:02:59,350 --> 00:03:01,335 Ni mchakato gani kweli kwamba unatumia? 57 00:03:01,335 --> 00:03:03,770 Je, ni haki random tu kuokota ya kwanza unaweza kuona 58 00:03:03,770 --> 00:03:05,250 na kuweka katika nafasi yake? 59 00:03:05,250 --> 00:03:09,680 Je, kwanza hoja mikono yako karibu kuangalia kwa basi kuangalia kwa B? 60 00:03:09,680 --> 00:03:11,722 Je, wewe kuangalia jozi yao upande kwa upande 61 00:03:11,722 --> 00:03:14,680 na tu kusema, kusubiri dakika, hii si sahihi, na kisha wabadilishane ili? 62 00:03:14,680 --> 00:03:16,960 Tuliona tayari juu ya Jumatatu kwamba kuna idadi ya njia 63 00:03:16,960 --> 00:03:22,140 ambayo tunaweza kufanya hivyo, na kweli kama sisi karibu na mwisho hapa, 64 00:03:22,140 --> 00:03:26,360 Napenda kuchukua note labda Mary Beth ya nini ni kufanya. 65 00:03:26,360 --> 00:03:30,040 Tuna piles chache inaonekana, a moja kubwa, tatu madogo. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> Watazamaji: Mimi kuagiza yao wakati mimi kupata barua mbili 68 00:03:36,415 --> 00:03:39,540 kuwa mimi najua ni pamoja katika mlolongo, Mimi kuweka yao kwa pamoja ili kwamba mimi si 69 00:03:39,540 --> 00:03:42,915 kuwa na wasiwasi juu ya kuweka wimbo wa zima mstari wa vitabu. 70 00:03:42,915 --> 00:03:45,706 Ni tu, oh, A ni ya kwanza, Mimi nimepata stack hii hapa. 71 00:03:45,706 --> 00:03:47,580 SPIKA: Kwa hiyo, karibu kama vipande puzzle kwamba 72 00:03:47,580 --> 00:03:49,860 kuwa na sura haki ya match up na kila mmoja. 73 00:03:49,860 --> 00:03:51,026 Watazamaji: Pretty much, yeah. 74 00:03:51,026 --> 00:03:55,320 SPIKA: Sawa, bora. 75 00:03:55,320 --> 00:03:59,850 Na sasa kila moja ya haya piles ni labda yamepangwa? 76 00:03:59,850 --> 00:04:00,990 >> Watazamaji: Yeah. 77 00:04:00,990 --> 00:04:09,900 >> SPIKA: zote haki, A njia ya Z. wote haki, pongezi, wewe alifanya hivyo. 78 00:04:09,900 --> 00:04:11,461 Una uchaguzi wako. 79 00:04:11,461 --> 00:04:11,960 Blue? 80 00:04:11,960 --> 00:04:13,530 Haki yote, asante kwa ajili hiyo. 81 00:04:13,530 --> 00:04:16,679 Hivyo Mary Beth hakuwa kupendekeza mbinu gani yake ilikuwa, 82 00:04:16,679 --> 00:04:19,720 lakini ni mbinu gani mwingine jinsi wewe wanaweza kwenda juu ya kuchagua mambo haya? 83 00:04:19,720 --> 00:04:21,130 Je, ungefanya nini kosa gani? 84 00:04:21,130 --> 00:04:24,060 rekodi ya kuwapiga ingekuwa dakika moja na sekunde 50 au hivyo, 85 00:04:24,060 --> 00:04:26,039 pamoja na wale I forgot kuhesabu. 86 00:04:26,039 --> 00:04:27,080 Je, ungefanya nini kosa gani? 87 00:04:27,080 --> 00:04:27,579 Yeah? 88 00:04:27,579 --> 00:04:28,735 Watazamaji: Chukua stack. 89 00:04:28,735 --> 00:04:29,776 Kuanza tangu mwanzo. 90 00:04:29,776 --> 00:04:32,284 Angalia karatasi yako. 91 00:04:32,284 --> 00:04:36,586 Na kama moja ya juu ni juu kuliko, labda, wao ni, 92 00:04:36,586 --> 00:04:38,980 moja chini ni juu, kisha kubadili yao. 93 00:04:38,980 --> 00:04:41,300 >> SPIKA: Sawa, hivyo kuanzia saa ya juu na chini, 94 00:04:41,300 --> 00:04:43,716 na kisha kufanya kazi kwa njia yako ndani kama kwamba, swapping yao? 95 00:04:43,716 --> 00:04:46,580 OK, hivyo kidogo sawa katika roho Bubble aina, 96 00:04:46,580 --> 00:04:49,160 lakini kuchagua extremes si jozi karibu. 97 00:04:49,160 --> 00:04:52,080 Lakini short yake ni kwamba kuna Hakika kundi la njia mbalimbali 98 00:04:52,080 --> 00:04:54,210 tunaweza kufanya hii, na kusema ukweli, nadhani wewe aina ya 99 00:04:54,210 --> 00:04:55,700 iliyopitishwa mbinu wanandoa, haki? 100 00:04:55,700 --> 00:05:00,567 Unaweza kufanywa aina ya nne piles sorted, na kisha kwa ufanisi zimeunganishwa pamoja. 101 00:05:00,567 --> 00:05:02,650 Na kwamba ni, daresay, mwingine mbinu kabisa. 102 00:05:02,650 --> 00:05:06,950 Wewe hakuwa na kutibu kama moja kubwa rundo, wewe kugawanywa tatizo katika quads nne, 103 00:05:06,950 --> 00:05:09,820 kama wewe, na kisha kwa namna fulani ilijiunga yao katika mwisho. 104 00:05:09,820 --> 00:05:13,410 >> Basi hebu fikiria, hatimaye, jinsi mwingine tupate kufanya hivyo. 105 00:05:13,410 --> 00:05:15,860 Sisi rasmi dhana ya Bubble aina mara ya mwisho, 106 00:05:15,860 --> 00:05:18,780 na Bubble aina kukumbuka mara algorithm kwamba sisi visualized 107 00:05:18,780 --> 00:05:22,640 na nane wa wanafunzi wako juu hapa, inaonekana nasibu sorted mara ya kwanza. 108 00:05:22,640 --> 00:05:26,110 Na sisi basi aliamua pairwise, kama mambo mawili ni nje ya utaratibu, 109 00:05:26,110 --> 00:05:26,950 tu wabadilishane yao. 110 00:05:26,950 --> 00:05:28,930 Hivyo nne na mbili ni wazi nje ya utaratibu, 111 00:05:28,930 --> 00:05:31,080 hivyo wale classmates mbili switched nafasi. 112 00:05:31,080 --> 00:05:35,390 Na kisha sisi mara kwa mara na nne na sita, kisha sita na nane, juu ya kila iteration, 113 00:05:35,390 --> 00:05:36,980 kuhamia na haki. 114 00:05:36,980 --> 00:05:42,590 >> Hivyo kutokana na watu nane, jinsi wengi pairwise kulinganisha mimi kufanya wakati kutembea kutoka 115 00:05:42,590 --> 00:05:45,220 kushoto na kulia katika moja iteration hayo? 116 00:05:45,220 --> 00:05:48,410 Jinsi kulinganisha wengi? 117 00:05:48,410 --> 00:05:49,197 Saba, haki? 118 00:05:49,197 --> 00:05:51,405 Kwa sababu kama kuna nane watu lakini una jozi 119 00:05:51,405 --> 00:05:53,880 yao na wewe kuendelea kusonga mbele moja hop na haki, 120 00:05:53,880 --> 00:05:56,060 wewe si kwenda kuwa na nane kulinganisha kwa sababu huwezi kulinganisha 121 00:05:56,060 --> 00:05:59,226 kipengele dhidi ya yenyewe, au ingekuwa tu kuwa pointless, hivyo una saba. 122 00:05:59,226 --> 00:06:01,290 Au zaidi kwa ujumla, kama tuna watu n, sisi 123 00:06:01,290 --> 00:06:04,300 kufanya n 1 minus kulinganisha na Bubble aina. 124 00:06:04,300 --> 00:06:08,150 >> Hivyo hebu fikiria sasa jinsi nzuri au mbaya Bubble aina kweli alikuwa, na kujaribu 125 00:06:08,150 --> 00:06:13,570 kutoa wenyewe msamiati kwa ambayo kwa kukosoa algorithms kama hii, 126 00:06:13,570 --> 00:06:14,430 na hivi karibuni yetu wenyewe. 127 00:06:14,430 --> 00:06:16,970 Hivyo kupita kwanza kwa njia ya Bubble aina, mara ya kwanza 128 00:06:16,970 --> 00:06:20,909 Mimi kutembea kutoka upande wa kushoto na haki katika hatua, alichukua yangu n 1 minus kulinganisha. 129 00:06:20,909 --> 00:06:22,950 Na kwamba ni kwenda kuwa wangu kitengo cha kipimo, haki? 130 00:06:22,950 --> 00:06:26,170 Mimi nilikuwa aina ya kuzungumza na matembezi, kiasi fulani kwa haraka, kwa kiasi fulani polepole, 131 00:06:26,170 --> 00:06:29,300 hivyo kuhesabu namba yangu ya sekunde si hasa kuwaambia, 132 00:06:29,300 --> 00:06:32,260 lakini kuhesabu idadi ya shughuli kwamba sikuwa juu ya Jumatatu, 133 00:06:32,260 --> 00:06:35,900 kulinganisha watu wawili, kwamba anahisi kama nzuri kitengo cha kipimo. 134 00:06:35,900 --> 00:06:40,980 >> Hivyo n 1 minus hatua mara ya kwanza, lakini kisha kile kilichotokea baada ya kwamba? 135 00:06:40,980 --> 00:06:46,610 Nini kichwa moja ya kupita moja kupitia orodha vinginevyo zisizochambuliwa? 136 00:06:46,610 --> 00:06:49,840 Nini unaweza kuniambia kuhusu kipengele ambaye alikuwa njia yote juu ya huko? 137 00:06:49,840 --> 00:06:51,300 Yeah? 138 00:06:51,300 --> 00:06:52,870 Hiyo ilikuwa kipengele kubwa, sawa? 139 00:06:52,870 --> 00:06:55,710 Idadi nane, ingawa yeye ilianza hapa, kila wakati mimi 140 00:06:55,710 --> 00:06:57,860 ikilinganishwa yake dhidi ya jirani, aliendelea 141 00:06:57,860 --> 00:07:00,480 bubbling up na haki mkono upande wa orodha. 142 00:07:00,480 --> 00:07:02,710 Na hakika, hiyo ambapo algorithm anapata jina lake. 143 00:07:02,710 --> 00:07:07,630 >> Sasa kwa mantiki kwamba, jinsi kulinganisha wengi haja mimi kufanya juu ya mara ya pili 144 00:07:07,630 --> 00:07:09,800 Mimi kufanya kupita kutoka kushoto kwenda kulia? 145 00:07:09,800 --> 00:07:10,730 n minus 2, haki? 146 00:07:10,730 --> 00:07:14,297 Ingekuwa tu kuwa na kupoteza muda wangu kama mimi kuweka kulinganisha nane dhidi ya mtu 147 00:07:14,297 --> 00:07:16,630 mwingine kwa sababu sisi tayari kujua yeye alikuwa katika mahali pa haki. 148 00:07:16,630 --> 00:07:19,760 Hivyo hiyo ni kidogo ya optimization, hivyo kupita ijayo 149 00:07:19,760 --> 00:07:23,899 ni kwenda kuwa pamoja na n minus hatua mbili, ambapo n ni idadi ya watu. 150 00:07:23,899 --> 00:07:26,940 Sasa unaweza aina ya extrapolate, hata kama wewe si mwanasayansi wa kompyuta, 151 00:07:26,940 --> 00:07:27,680 jinsi hii mwisho. 152 00:07:27,680 --> 00:07:31,259 Wakati wa mwisho wa algorithm hii, labda nimepata tu kulinganisha moja kushoto. 153 00:07:31,259 --> 00:07:33,800 Una aina ya kurekebisha mwanzo wa orodha katika kesi mbili 154 00:07:33,800 --> 00:07:36,540 na moja ni nje ya utaratibu na lazima moja na mbili, 155 00:07:36,540 --> 00:07:40,330 hivyo hii bottoms nje katika plus 1 mwisho kulinganisha. 156 00:07:40,330 --> 00:07:44,500 >> Sasa dot, dot, dot aina ya mawimbi ni mikono katika baadhi ya maelezo juicier, 157 00:07:44,500 --> 00:07:46,452 lakini hebu tu kwenda mbele na kurahisisha. 158 00:07:46,452 --> 00:07:48,660 Kama unakumbuka kutoka juu shule, kusema ukweli, mengi ya wewe 159 00:07:48,660 --> 00:07:50,340 alikuwa na vitabu math kwamba alikuwa kidogo kudanganya karatasi 160 00:07:50,340 --> 00:07:52,550 juu ya bima ya mbele au nyuma cover ambayo ilionyesha wewe 161 00:07:52,550 --> 00:07:56,400 summations mfululizo nini kama hii hatimaye aliongeza hadi. 162 00:07:56,400 --> 00:07:59,600 Katika kesi ujumla, kama una variable kama n, na kwa kweli hii moja, 163 00:07:59,600 --> 00:08:01,634 kama wewe inaonekana saa yako umri wa shule ya math kitabu, 164 00:08:01,634 --> 00:08:04,050 ungependa kuona kwamba hii kweli zinafikia kiasi hiki hapa, 165 00:08:04,050 --> 00:08:07,970 n mara n 1 minus kila kugawanywa na 2. 166 00:08:07,970 --> 00:08:11,172 Hivyo kwa sasa napenda tu inasema hii ni kweli, kadhalika leap ya imani, 167 00:08:11,172 --> 00:08:12,880 kwamba ni nini hii sums juu, na tunaweza 168 00:08:12,880 --> 00:08:14,341 kuthibitisha kwamba katika kesi zaidi kwa ujumla. 169 00:08:14,341 --> 00:08:15,590 Lakini sasa hebu kupanua hii nje. 170 00:08:15,590 --> 00:08:19,920 Basi hebu kuzidisha hii nje, hivyo hiyo ni n squared, minus n, kila kugawanywa na 2. 171 00:08:19,920 --> 00:08:23,200 Hiyo ni kweli n squared, kugawanywa na 2, minus n zaidi ya 2, 172 00:08:23,200 --> 00:08:25,010 hivyo kwamba wote nzuri na ya kuvutia. 173 00:08:25,010 --> 00:08:27,060 Lakini kile kinachotokea kama sisi sasa kuziba-katika thamani? 174 00:08:27,060 --> 00:08:29,724 Tuseme sikuwa na nane watu, lakini kusema milioni. 175 00:08:29,724 --> 00:08:31,890 Na kwa sababu tu milioni ni idadi kubwa pretty, 176 00:08:31,890 --> 00:08:34,039 hebu kuziba kwamba katika na kuona nini kinatokea. 177 00:08:34,039 --> 00:08:39,039 Hivyo kama mimi kuziba milioni katika formula kwamba Mimi nina kwenda kupata milioni mraba, 178 00:08:39,039 --> 00:08:42,868 kugawanywa na 2, minus a milioni, kugawanywa na 2. 179 00:08:42,868 --> 00:08:44,159 Sasa nini kwamba kwenda sawa? 180 00:08:44,159 --> 00:08:47,354 Hivyo bilioni 500, minus 500,000. 181 00:08:47,354 --> 00:08:49,270 Na kama mimi kwa kweli kufanya kwamba math nje, kwamba njia 182 00:08:49,270 --> 00:08:53,920 kwamba kuchagua milioni watu na aina Bubble 183 00:08:53,920 --> 00:09:01,800 inaweza kuchukua mimi 499,999,500,000 hatua au kulinganisha katika mwisho, 184 00:09:01,800 --> 00:09:02,900 sisi ni extrapolating tu. 185 00:09:02,900 --> 00:09:06,860 >> Kwamba anahisi pretty polepole, lakini kusema ukweli kupima hasa pembejeo moja 186 00:09:06,860 --> 00:09:09,160 kama hii, ni si kuwaambia kwamba wote. 187 00:09:09,160 --> 00:09:14,050 Lakini kwa kweli haina zinaonyesha kwamba kama n anapata kubwa na kubwa, hii algorithm 188 00:09:14,050 --> 00:09:16,280 aina ya anahisi mbaya na mbaya, au kweli 189 00:09:16,280 --> 00:09:20,450 kuanza kuhisi maumivu ya kwamba exponentiation, kwamba n squared, 190 00:09:20,450 --> 00:09:21,770 ambayo inaongeza up pretty kufunga. 191 00:09:21,770 --> 00:09:25,340 Na hii undani ni si waliopotea juu ya watu, kwa kweli 192 00:09:25,340 --> 00:09:29,640 baadhi ya miaka iliyopita senator fulani ambaye alikuwa kampeni, waliketi kwa ajili ya mahojiano 193 00:09:29,640 --> 00:09:32,180 na Eric Google Schmidt, Mkurugenzi Mtendaji wa wakati huo, 194 00:09:32,180 --> 00:09:36,380 na ilikuwa changamoto kwa swali kiasi kama sisi ni kuchunguza leo. 195 00:09:36,380 --> 00:09:38,468 Hebu tuangalie. 196 00:09:38,468 --> 00:09:45,280 >> [VIDEO avspelning] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Wewe ni hapa katika Google, na mimi kama 198 00:09:48,560 --> 00:09:53,382 kufikiri ya urais kama mahojiano ya kazi. 199 00:09:53,382 --> 00:09:56,434 Sasa, ni vigumu kupata kazi kama rais, 200 00:09:56,434 --> 00:09:58,100 na wewe ni kwenda kwa njia ya rigors sasa. 201 00:09:58,100 --> 00:10:01,860 Ni pia vigumu kupata kazi katika Google. 202 00:10:01,860 --> 00:10:05,490 Tuna maswali, na sisi kuuliza maswali wagombea wetu, 203 00:10:05,490 --> 00:10:09,770 na hii ni moja kutoka Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 What-- guys kufikiri mimi nina kidding, ni haki hapa. 205 00:10:14,760 --> 00:10:17,930 Ni njia ya ufanisi zaidi kwa nini aina milioni integers 32-bit? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> -I'm Sorry, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> -Hakuna, Hapana, hapana. 210 00:10:27,400 --> 00:10:30,700 Nadhani aina Bubble itakuwa njia sahihi ya kwenda. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> -Come Juu, ambaye alimwambia hii? 213 00:10:38,180 --> 00:10:40,590 Sikuweza kuona kompyuta sayansi katika background yako. 214 00:10:40,590 --> 00:10:42,130 >> -We've Got wapelelezi wetu huko. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Wacha tujiulize mbalimbali swali mahojiano. 217 00:10:48,444 --> 00:10:49,300 >> [END video avspelning] 218 00:10:49,300 --> 00:10:52,290 >> SPIKA: Kwa hiyo kuzungumza juu ya idadi maalum ingawa, 219 00:10:52,290 --> 00:10:53,890 si kwenda kuwa wote muhimu kwamba. 220 00:10:53,890 --> 00:10:56,810 Ni si maisha ya somo kwamba Bubble aina, kutokana na milioni pembejeo, 221 00:10:56,810 --> 00:10:58,590 inaweza kuchukua hatua kama wengi kama bilioni 500. 222 00:10:58,590 --> 00:11:01,120 Unaweza si kweli kujumlisha ufanisi pia kutoka kwamba 223 00:11:01,120 --> 00:11:03,560 na kufanya maamuzi design nzuri wakati wa kuandika mipango. 224 00:11:03,560 --> 00:11:07,070 Basi hebu kuzingatia ingawa juu ya jinsi tupate kurahisisha matokeo haya. 225 00:11:07,070 --> 00:11:11,780 >> Hivyo nimekuwa yalionyesha katika njano hapa matokeo ya n squared kugawanywa na 2, 226 00:11:11,780 --> 00:11:14,330 hivyo milioni mraba kugawanywa na 2, na kisha 227 00:11:14,330 --> 00:11:16,710 Nimekuwa yalionyesha nini jibu la mwisho ilikuwa 228 00:11:16,710 --> 00:11:20,180 mara moja sisi subtracted off n kugawanywa na 2. 229 00:11:20,180 --> 00:11:24,850 Na kudai mimi nina kwenda kufanya sasa ni, ambao heck anayejali kama wewe Ondoa off 230 00:11:24,850 --> 00:11:30,060 umri mdogo zaidi ya 2 n wakati wa kwanza sehemu ya formula hii ni hivyo kubwa sana? 231 00:11:30,060 --> 00:11:33,910 Ni dominates nyingine mrefu, n squared kugawanywa na 2 232 00:11:33,910 --> 00:11:37,510 ni hivyo kubwa sana, kwa uwazi, kama n anapata kubwa kama milioni, 233 00:11:37,510 --> 00:11:41,450 kwamba ni kweli kuna tofauti kubwa katika mwisho wa siku kati ya bilioni 500 234 00:11:41,450 --> 00:11:45,730 499,999,500,000 na? 235 00:11:45,730 --> 00:11:46,349 Si kweli. 236 00:11:46,349 --> 00:11:48,640 Na hivyo kile sisi ni kwenda kufanya kama wanasayansi wa kompyuta ni 237 00:11:48,640 --> 00:11:53,270 kupuuza wale suala chini ya amri, na kuchukua kitu kama hii na kwa kweli 238 00:11:53,270 --> 00:11:56,050 tu kurahisisha kwa mrefu ambayo inaenda jambo. 239 00:11:56,050 --> 00:12:00,315 kubwa data seti wetu kupata, kubwa database yetu kupata, kurasa zaidi ya mtandao 240 00:12:00,315 --> 00:12:02,690 sisi kuwa na kutafuta, zaidi marafiki una juu ya Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Kama n anapata kubwa, sisi ni kweli kwenda kwa huduma ya juu kubwa 242 00:12:07,340 --> 00:12:11,560 mrefu katika uchambuzi wowote kama hiyo ya algorithms yetu ya utendaji. 243 00:12:11,560 --> 00:12:16,230 Na mimi nina kwenda kusema, unajua nini, Bubble aina ni juu ya utaratibu wa kubwa O, 244 00:12:16,230 --> 00:12:18,060 juu ya utaratibu wa n squared. 245 00:12:18,060 --> 00:12:20,090 Ni si hasa n mraba kama tumeona, 246 00:12:20,090 --> 00:12:22,060 lakini ambao kwa kweli wasiwasi kuhusu sheria hizo ndogo, 247 00:12:22,060 --> 00:12:24,390 na kusema ukweli, ambao kwa kweli anayejali kama sisi kugawanya na 2? 248 00:12:24,390 --> 00:12:25,870 Hiyo tu sababu mara kwa mara. 249 00:12:25,870 --> 00:12:29,480 Na ni bilioni 500 dhidi ya 250 bilioni kweli kwamba kubwa ya mpango huo? 250 00:12:29,480 --> 00:12:32,190 Mimi nilikuwa tu kusubiri mwaka mmoja, basi laptop yangu literally 251 00:12:32,190 --> 00:12:34,810 kupata mara mbili kwa haraka katika vifaa, na kwamba aina ya tofauti 252 00:12:34,810 --> 00:12:36,650 tu inakwenda mbali kawaida baada ya muda. 253 00:12:36,650 --> 00:12:39,300 >> Nini sisi huduma ya juu ni kujieleza, sehemu 254 00:12:39,300 --> 00:12:42,489 wa kujieleza kwamba kwenda kutofautiana kama pembejeo yetu anapata makubwa na kubwa. 255 00:12:42,489 --> 00:12:45,280 Na hakika, katika ulimwengu wa kweli, kwamba ni nini kinatokea inazidi 256 00:12:45,280 --> 00:12:48,330 ni pembejeo kwa matatizo yetu na algorithms ni kupata kubwa. 257 00:12:48,330 --> 00:12:53,470 Hivyo kubwa O ni kwenda kuwa nukuu, nukuu asymptotic, kwamba sisi tu 258 00:12:53,470 --> 00:12:57,160 kutumia kama kompyuta wanasayansi kuelezea utendaji, au wakati kukimbia, 259 00:12:57,160 --> 00:12:58,130 ya algorithm. 260 00:12:58,130 --> 00:13:00,800 Ili tuweze kulinganisha algorithms juu ya kompyuta mbalimbali zilizoandikwa 261 00:13:00,800 --> 00:13:04,170 na watu tofauti, kwa kutumia baadhi tani kimsingi sawa 262 00:13:04,170 --> 00:13:07,557 kama idadi ya kulinganisha wewe ni maamuzi, au labda ya simu ya swaps 263 00:13:07,557 --> 00:13:08,140 wewe ni kufanya. 264 00:13:08,140 --> 00:13:11,910 >> Nini sisi siyo kwenda kuhesabu ni kiasi cha muda 265 00:13:11,910 --> 00:13:13,981 kwamba hupita juu ya saa juu ya ukuta kawaida. 266 00:13:13,981 --> 00:13:16,230 Nini sisi siyo kwenda kuwa na wasiwasi kuhusu ni kiasi gani kumbukumbu 267 00:13:16,230 --> 00:13:17,820 unatumia leo katika uchache, ingawa hiyo ni 268 00:13:17,820 --> 00:13:19,370 rasilimali nyingine tupate kupima. 269 00:13:19,370 --> 00:13:23,610 Sisi ni kwenda kujaribu msingi uchambuzi wetu juu tu michakato ya msingi, juu ya wale 270 00:13:23,610 --> 00:13:25,930 kusema ukweli, kwamba unaweza kuona wengi kuibua. 271 00:13:25,930 --> 00:13:30,700 Hivyo, pamoja na kitu kama O kubwa ya n mraba, mimi kudai kwamba O ya n squared 272 00:13:30,700 --> 00:13:35,820 ni juu amefungwa juu ya kile kinachoitwa mbio wakati wa Bubble aina. 273 00:13:35,820 --> 00:13:38,820 Kwa maneno mengine, kama wewe alitaka kudai kwamba kuna 274 00:13:38,820 --> 00:13:41,370 hii ukomo wa juu juu ya jinsi wengi hatua algorithm inaweza kuchukua, 275 00:13:41,370 --> 00:13:46,240 ni kwenda kuwa katika O kubwa ya n mraba katika kesi hii, juu amefungwa. 276 00:13:46,240 --> 00:13:49,710 >> Nini kama mimi badala mabadiliko hadithi kuwa si juu ya Bubble aina, 277 00:13:49,710 --> 00:13:50,910 lakini kuhusu hili amefungwa juu. 278 00:13:50,910 --> 00:13:54,030 Je, unaweza kufikiria algorithm kwamba tumekuwa inaonekana katika tayari 279 00:13:54,030 --> 00:13:59,530 ambao juu amefungwa, na kiwango cha kupima wa muda au shughuli, 280 00:13:59,530 --> 00:14:04,300 itakuwa alisema kuwa imepakana na n, kazi linear, 281 00:14:04,300 --> 00:14:07,260 si quadratic moja kwamba ni curved? 282 00:14:07,260 --> 00:14:10,780 Nini algorithm kwamba daima inachukua hakuna zaidi 283 00:14:10,780 --> 00:14:12,860 kuliko kama hatua n, au Hatua 2n, au hatua 3N? 284 00:14:12,860 --> 00:14:13,360 Yeah? 285 00:14:13,360 --> 00:14:15,030 >> Watazamaji: Kupata idadi kubwa katika orodha? 286 00:14:15,030 --> 00:14:16,930 >> SPIKA: Perfect, kutafuta idadi kubwa katika orodha. 287 00:14:16,930 --> 00:14:18,940 Kama mimi nina kupewa orodha ya watu kwa mfano, 288 00:14:18,940 --> 00:14:21,440 kila la nani kufanya idadi, nini ni upeo wa idadi 289 00:14:21,440 --> 00:14:23,770 ya hatua ni lazima kuchukua yangu, mtu sababu smart, 290 00:14:23,770 --> 00:14:27,530 kupata mtu mkubwa katika orodha hiyo? 291 00:14:27,530 --> 00:14:28,100 n, haki? 292 00:14:28,100 --> 00:14:31,320 Kwa sababu katika hali mbaya zaidi, ambapo ili thamani kubwa kuwa? 293 00:14:31,320 --> 00:14:32,700 Right, njia yote mwishoni. 294 00:14:32,700 --> 00:14:34,575 Hivyo katika kesi mbaya juu amefungwa, mimi ili 295 00:14:34,575 --> 00:14:36,450 na kwenda njia yote zaidi ya hapa na kuwa kama, 296 00:14:36,450 --> 00:14:39,170 oh, hapa namba nane, au chochote thamani kwamba ni. 297 00:14:39,170 --> 00:14:41,330 Sasa ingekuwa tu kuwa kijinga kama mimi naendelea kwenda, haki? 298 00:14:41,330 --> 00:14:43,840 Kuangalia kwa ajili ya mambo zaidi na zaidi kama mwisho wao ni zaidi ya hapo? 299 00:14:43,840 --> 00:14:45,340 Hakika, n ni amefungwa juu. 300 00:14:45,340 --> 00:14:47,420 Mimi hawana haja ya kuchukua hatua zaidi kuliko hiyo. 301 00:14:47,420 --> 00:14:51,580 >> Basi nini kama mimi badala mapendekezo kwamba kuna algorithms katika dunia hii ambayo 302 00:14:51,580 --> 00:14:57,750 na mbio wakati hiyo ni imepakana na O kubwa ya logi n, kuingia n? 303 00:14:57,750 --> 00:15:00,390 Ambapo tumeona huu kabla? 304 00:15:00,390 --> 00:15:00,890 Yeah? 305 00:15:00,890 --> 00:15:03,309 >> Watazamaji: Katika tatizo kitabu cha simu? 306 00:15:03,309 --> 00:15:04,850 SPIKA: Kama tatizo kitabu cha simu. 307 00:15:04,850 --> 00:15:07,754 Ilikuwa ni hatua ya jinsi ya nini wakati gani au jinsi machozi ni wengi 308 00:15:07,754 --> 00:15:10,170 alichukua mimi kupata mtu kama Mike Smith katika kitabu cha simu? 309 00:15:10,170 --> 00:15:13,212 Sisi alidai ni logi n, na hata kama usio wa kawaida au ni ni 310 00:15:13,212 --> 00:15:15,170 hazy kidogo nini a logarithm au exponent mara, 311 00:15:15,170 --> 00:15:17,650 kumbuka tu kwamba n logi kwa ujumla inahusu mchakato, 312 00:15:17,650 --> 00:15:20,790 katika kesi hii, ya kugawa kitu katika nusu tena, na tena, 313 00:15:20,790 --> 00:15:25,790 na tena, na tena, kama kwamba anapata inazidi ndogo kama wewe kufanya hivyo. 314 00:15:25,790 --> 00:15:28,470 >> Hivyo kuingia ya n inahusu, hakika, kwa kitabu cha simu mfano, 315 00:15:28,470 --> 00:15:32,662 kwa search binary katika nadharia, wakati sisi alikuwa milango virtual juu ya bodi, 316 00:15:32,662 --> 00:15:34,370 au wakati Sean mara kwa ajili ya kutafuta kitu fulani. 317 00:15:34,370 --> 00:15:37,374 Kama yeye alikuwa kutumika search binary, logi n itakuwa amefungwa juu juu ya ni kiasi gani 318 00:15:37,374 --> 00:15:38,040 wakati kwamba inachukua. 319 00:15:38,040 --> 00:15:44,027 Lakini wale algorithms kwamba mbio katika logi n kudhani undani nini muhimu? 320 00:15:44,027 --> 00:15:45,360 Hiyo orodha ilikuwa yamepangwa, haki? 321 00:15:45,360 --> 00:15:47,789 Algorithm yako ni vibaya kama mchango wako ni si Iliyopangwa, 322 00:15:47,789 --> 00:15:49,830 na bado unatumia kitu kama search binary 323 00:15:49,830 --> 00:15:51,704 kwa sababu unaweza kuruka haki juu ya kipengele 324 00:15:51,704 --> 00:15:53,600 bila kutambua ni kweli kuna. 325 00:15:53,600 --> 00:15:55,600 >> Sasa nini kinaweza hii ina maana, big O ya moja? 326 00:15:55,600 --> 00:15:59,117 Hii haina maana kwamba algorithm yako inachukua moja na hatua moja tu, 327 00:15:59,117 --> 00:16:01,200 ni tu ina maana inachukua mara kwa mara idadi ya hatua. 328 00:16:01,200 --> 00:16:04,060 Labda ni 1, labda ni 10, labda ni 1,000, 329 00:16:04,060 --> 00:16:07,750 lakini ni huru ya ukubwa wa tatizo. 330 00:16:07,750 --> 00:16:10,850 Hakuna jambo jinsi kubwa ni n, mara kwa mara wakati algorithm 331 00:16:10,850 --> 00:16:12,747 daima inachukua idadi sawa ya hatua. 332 00:16:12,747 --> 00:16:15,080 Hivyo kile anaweza kuwa algorithm tumekuwa aliyesema kuhusu au tu 333 00:16:15,080 --> 00:16:20,418 intuitively kwamba inakuja kwamba daima anaendesha katika kinachojulikana wakati mara kwa mara? 334 00:16:20,418 --> 00:16:20,918 Yeah? 335 00:16:20,918 --> 00:16:22,001 >> Watazamaji: Kuongeza namba mbili. 336 00:16:22,001 --> 00:16:25,320 SPIKA: Kuongeza namba mbili, 2 plus 2 ni sawa na 4, kufanyika. 337 00:16:25,320 --> 00:16:27,227 Hivyo kwamba inaweza kufanya kazi, nini kingine? 338 00:16:27,227 --> 00:16:28,560 Vipi kuhusu dunia zaidi ya kweli, yeah? 339 00:16:28,560 --> 00:16:30,686 >> Watazamaji: Kupata Jambo la kwanza katika orodha. 340 00:16:30,686 --> 00:16:32,810 SPIKA: Kupata kwanza kipengele katika orodha, uhakika. 341 00:16:32,810 --> 00:16:34,540 Tumekuwa kweli wamekuwa wakizungumza kuhusu arrays tayari, 342 00:16:34,540 --> 00:16:36,540 jinsi gani unaweza kupata katika kipengele kwanza katika safu, 343 00:16:36,540 --> 00:16:40,465 bila kujali ni muda gani safu ni katika C kanuni? 344 00:16:40,465 --> 00:16:43,090 Wewe tu kutumia kama bracket zero nukuu, bam, wewe ni huko. 345 00:16:43,090 --> 00:16:46,120 Na hakika arrays, kama kando, msaada kitu kwa ujumla inayojulikana 346 00:16:46,120 --> 00:16:49,240 kama upatikanaji random, random kupata kumbukumbu, kwa sababu unaweza literally 347 00:16:49,240 --> 00:16:50,284 kuruka kwa mtu yeyote sehemu moja. 348 00:16:50,284 --> 00:16:52,700 Tunaweza kufanya hivyo hata zaidi tu tunaweza rewind kwa wiki zero 349 00:16:52,700 --> 00:16:53,900 wakati sisi alifanya Scratch. 350 00:16:53,900 --> 00:16:59,707 Muda kiasi gani alifanya hivyo kuchukua kwa kusema block katika Scratch kutekeleza? 351 00:16:59,707 --> 00:17:00,790 Tu wakati mara kwa mara, haki? 352 00:17:00,790 --> 00:17:03,960 Kusema kitu, kusema kitu, haijalishi 353 00:17:03,960 --> 00:17:07,359 jinsi Scratches kubwa dunia ni, mara nyingi ni kwenda kuchukua kiasi kama hicho cha wakati 354 00:17:07,359 --> 00:17:08,490 tu kusema kitu. 355 00:17:08,490 --> 00:17:11,089 >> Hivyo kwamba ni wakati mara kwa mara, lakini nini upande flip? 356 00:17:11,089 --> 00:17:13,030 Kama hiyo ilikuwa ya juu mipaka, nini kama tunataka 357 00:17:13,030 --> 00:17:17,089 kuelezea mipaka ya chini ya algorithms wetu mbio wakati? 358 00:17:17,089 --> 00:17:19,852 Karibu kesi bora uwezekano, kama wewe, 359 00:17:19,852 --> 00:17:23,060 ingawa maneno haya inaweza kuomba bora kesi, kesi mbaya, wastani wa kesi zaidi 360 00:17:23,060 --> 00:17:26,359 kwa ujumla, lakini hebu tu kuzingatia juu ya mipaka ya chini zaidi kwa ujumla. 361 00:17:26,359 --> 00:17:31,920 Nini algorithm ambayo ina amefungwa chini ya hatua n, 362 00:17:31,920 --> 00:17:33,350 au hatua 2n, au hatua 3N? 363 00:17:33,350 --> 00:17:36,241 Baadhi ya sababu ya hatua n, hiyo ni ya chini yake amefungwa. 364 00:17:36,241 --> 00:17:36,740 Yeah? 365 00:17:36,740 --> 00:17:37,910 >> Watazamaji: Bubble aina? 366 00:17:37,910 --> 00:17:41,610 >> SPIKA: Bubble aina inachukua wewe hatua ya chini n, kwa nini? 367 00:17:41,610 --> 00:17:42,279 Kwa nini ni kwamba? 368 00:17:42,279 --> 00:17:45,320 Kwa nini kwamba mwanzo kuja kwenu intuitively, hata kama hana tu 369 00:17:45,320 --> 00:17:46,530 bado? 370 00:17:46,530 --> 00:17:47,030 Yeah? 371 00:17:47,030 --> 00:17:47,990 >> Watazamaji: [inaudible]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 SPIKA: Ndiyo hivyo. 374 00:17:52,360 --> 00:17:55,810 Katika bora mazingira ya Bubble aina, na mengi ya algorithms, 375 00:17:55,810 --> 00:17:58,769 kama mimi mkono wewe watu nane ambao tayari Iliyopangwa, 376 00:17:58,769 --> 00:18:00,560 ingekuwa ujinga kwa ajili yenu, algorithm, 377 00:18:00,560 --> 00:18:02,202 kwenda na kurudi zaidi ya mara moja, sawa? 378 00:18:02,202 --> 00:18:04,285 Kwa sababu kwa haraka kama wewe kutembea kwa njia ya orodha ya mara moja, 379 00:18:04,285 --> 00:18:08,090 unapaswa kutambua, oh, mimi alifanya hakuna swaps, orodha hii ni Iliyopangwa, exit. 380 00:18:08,090 --> 00:18:09,700 Lakini hiyo ni kwenda kuchukua wewe n hatua. 381 00:18:09,700 --> 00:18:12,033 >> Na kinyume chake, nini mwingine njia ya kufikiri kuhusu hilo? 382 00:18:12,033 --> 00:18:15,240 Bubble aina ni omega, hivyo kusema, ya n, 383 00:18:15,240 --> 00:18:19,050 kwa sababu kama ukiangalia katika chini ya n vipengele, nini 384 00:18:19,050 --> 00:18:23,009 ni suala la msingi huko? 385 00:18:23,009 --> 00:18:24,550 Huwezi kujua kama ni vyema, haki. 386 00:18:24,550 --> 00:18:26,800 Sisi binadamu nguvu mtazamo saa nane watu na kuwa kama, oh, ni sorted, 387 00:18:26,800 --> 00:18:28,430 kwamba hakuwa na kuchukua yangu n hatua, lakini ni gani. 388 00:18:28,430 --> 00:18:30,810 Macho yako, hata kama wewe aina ya kuwa na uwanja kubwa ya maono, 389 00:18:30,810 --> 00:18:33,184 wewe inaonekana saa vipengele nane, wewe inaonekana saa watu nane, 390 00:18:33,184 --> 00:18:34,610 hiyo ni hatua nane kwa ufanisi. 391 00:18:34,610 --> 00:18:38,612 Na tu kama mimi kutembea kwa njia ya zima orodha kufanya mimi kutambua, ndiyo, Iliyopangwa. 392 00:18:38,612 --> 00:18:41,320 Kama mimi kuacha nusu ya kufikiri, kila haki, ni pretty yamepangwa hadi sasa, 393 00:18:41,320 --> 00:18:42,520 nini tabia mbaya ni si yamepangwa ni? 394 00:18:42,520 --> 00:18:44,186 Hiyo algorithms si kwenda kuwa sahihi. 395 00:18:44,186 --> 00:18:46,250 Inaweza kuwa kwa kasi, lakini sahihi. 396 00:18:46,250 --> 00:18:48,500 >> Hivyo basi, tuna njia ya kuelezea mipaka ya chini, 397 00:18:48,500 --> 00:18:49,710 na nini kuhusu wakati mara kwa mara? 398 00:18:49,710 --> 00:18:54,565 Nini algorithm ambayo ina chini amefungwa juu ya mbio yake wakati wa moja? 399 00:18:54,565 --> 00:18:58,350 Hatua 1, 2 hatua, hatua 10, lakini mara kwa mara, huru ya n, 400 00:18:58,350 --> 00:18:59,310 ukubwa wa pembejeo? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Yeah, katika nyuma. 403 00:19:04,600 --> 00:19:05,309 >> Watazamaji: printf? 404 00:19:05,309 --> 00:19:06,183 SPIKA: Nini hiyo? 405 00:19:06,183 --> 00:19:07,184 Watazamaji: printf? 406 00:19:07,184 --> 00:19:07,850 SPIKA: printf. 407 00:19:07,850 --> 00:19:08,400 OK, uhakika. 408 00:19:08,400 --> 00:19:10,720 Hivyo inachukua fasta idadi ya hatua. 409 00:19:10,720 --> 00:19:13,170 Na mimi lazima now-- sasa kwamba sisi ni kuzungumza juu ya C code 410 00:19:13,170 --> 00:19:16,040 na si Scratch, kitu kama kusema, kwa printf, 411 00:19:16,040 --> 00:19:17,710 tuanze kupata makini. 412 00:19:17,710 --> 00:19:21,090 Kwa sababu printf haina kuchukua pembejeo, ni kamba, 413 00:19:21,090 --> 00:19:23,220 na masharti wala kitaalam na urefu. 414 00:19:23,220 --> 00:19:25,530 Hivyo kama sisi sasa wanataka kuchukua juu yenu, kama wewe huna akili, 415 00:19:25,530 --> 00:19:29,430 kitaalam sisi anaweza kusema kwamba printf haina kuchukua variable urefu pembejeo, 416 00:19:29,430 --> 00:19:32,270 Na hakika inaweza kuchukua zaidi wakati magazeti string hii kwa muda mrefu, 417 00:19:32,270 --> 00:19:33,560 kuliko huu muda mrefu. 418 00:19:33,560 --> 00:19:36,570 >> Basi nini kama sisi kufikiria tu kuchagua na kutafuta mifano? 419 00:19:36,570 --> 00:19:40,450 Nini juu ya Mike Smith katika simu kitabu, or search binary zaidi kwa ujumla? 420 00:19:40,450 --> 00:19:42,220 Katika kesi bora, nini kinaweza kutokea? 421 00:19:42,220 --> 00:19:45,577 Mimi kufungua kitabu cha simu na, bam, kuna idadi Mike Smith ya. 422 00:19:45,577 --> 00:19:46,660 Siwezi kumwita haki mbali. 423 00:19:46,660 --> 00:19:49,390 >> Alichukua hatua moja, labda hatua mbili, lakini idadi ya mara kwa mara ya hatua 424 00:19:49,390 --> 00:19:50,230 kama mimi got bahati. 425 00:19:50,230 --> 00:19:52,570 Na kusema ukweli, tuliona juu ya Jumatatu classmate yako 426 00:19:52,570 --> 00:19:54,710 kupata bahati kabisa mara mbili mfululizo. 427 00:19:54,710 --> 00:19:57,050 Na kwamba kweli alikuwa mara kwa mara wakati katika mipaka ya chini 428 00:19:57,050 --> 00:20:01,280 juu ya algorithm katika swali kwa ajili ya kutafuta idadi 50 nyuma ya wale imefungwa 429 00:20:01,280 --> 00:20:01,830 milango. 430 00:20:01,830 --> 00:20:06,400 >> Sasa, kama kando, kama wewe kugundua kwamba wote O kubwa, huku amefungwa juu, 431 00:20:06,400 --> 00:20:09,310 na omega, chini amefungwa, ni moja katika huo huo, kwamba 432 00:20:09,310 --> 00:20:11,830 ni formula sawa katika mabano, unaweza pia 433 00:20:11,830 --> 00:20:15,170 kusema, tu kuwa dhana tu, kwamba kitu fulani ni katika theta 434 00:20:15,170 --> 00:20:18,270 ya n au theta ya baadhi thamani mengine. 435 00:20:18,270 --> 00:20:20,661 Hiyo ina maana tu wakati kubwa O na omega ni sawa. 436 00:20:20,661 --> 00:20:21,910 Sasa nini kuhusu uteuzi aina? 437 00:20:21,910 --> 00:20:23,400 Hebu kutumia msamiati hii mpya. 438 00:20:23,400 --> 00:20:27,407 Katika uteuzi aina, nini tulikuwa kufanya tena, na tena, na tena? 439 00:20:27,407 --> 00:20:29,990 Mimi nilikuwa kwenda na kurudi kwa njia orodha, kuangalia kwa nani? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 idadi ndogo. 442 00:20:34,730 --> 00:20:37,560 >> Hivyo ni jinsi hatua nyingi, jinsi kulinganisha ngapi mimi 443 00:20:37,560 --> 00:20:43,250 kufanya ili takwimu nje ambao kipengele ndogo katika orodha alikuwa? 444 00:20:43,250 --> 00:20:44,437 n minus 1, haki? 445 00:20:44,437 --> 00:20:47,770 Kwa sababu kama mimi tu kuanza na moja mimi nina aliyopewa na mimi kuanza kulinganisha kwake, 446 00:20:47,770 --> 00:20:49,519 kisha kwake, naye au wake, yeye au yake, mimi 447 00:20:49,519 --> 00:20:52,010 unaweza tu jozi mambo pamoja n 1 minus mara kwa mara. 448 00:20:52,010 --> 00:20:55,630 Hivyo uteuzi aina vile vile inachukua n minus 1 hatua mara ya kwanza. 449 00:20:55,630 --> 00:20:59,540 >> Jinsi hatua nyingi gani kuchukua mimi kupata kipengele pili madogo? 450 00:20:59,540 --> 00:21:02,920 n minus 2, kwa sababu mimi nina kuwa bubu kama mimi kuendelea kuangalia watu sawa 451 00:21:02,920 --> 00:21:06,280 tena kama nimekuwa tayari kuchaguliwa kwake au yake na kuziweka katika nafasi zao. 452 00:21:06,280 --> 00:21:09,270 Na hatua ya tatu, n minus 3, basi n minus 4. 453 00:21:09,270 --> 00:21:11,020 Tumeona muundo huu kabla ya, na kwa kweli 454 00:21:11,020 --> 00:21:13,460 uteuzi aina vile vile ina ya juu amefungwa 455 00:21:13,460 --> 00:21:16,210 ya n squared kama sisi kufanya up kwamba summation. 456 00:21:16,210 --> 00:21:19,790 Ni ya chini amefungwa, uteuzi aina yake nini? 457 00:21:19,790 --> 00:21:25,350 Minimally, ni kiasi gani wakati lazima uteuzi aina kuchukua, kama sisi ni inavyoelezwa Jumatatu? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Kupendekeza njia mbili. 460 00:21:30,490 --> 00:21:32,360 Labda ni n, kama kabla. 461 00:21:32,360 --> 00:21:35,040 Labda ni n squared, kama ni sasa kama amefungwa juu. 462 00:21:35,040 --> 00:21:35,874 >> Watazamaji: n squared. 463 00:21:35,874 --> 00:21:36,664 SPIKA: n squared. 464 00:21:36,664 --> 00:21:37,368 Kwa nini? 465 00:21:37,368 --> 00:21:40,060 >> Watazamaji: Kwa sababu una kufafanua [inaudible]. 466 00:21:40,060 --> 00:21:41,510 >> SPIKA: Ndiyo hivyo. 467 00:21:41,510 --> 00:21:45,077 Angalau kama mimi inavyoelezwa uteuzi aina ilikuwa pretty naive, kuendelea, 468 00:21:45,077 --> 00:21:46,160 kupata kipengele ndogo. 469 00:21:46,160 --> 00:21:47,770 Kwenda tena, kupata kipengele ndogo. 470 00:21:47,770 --> 00:21:49,490 Kwenda tena, kupata kipengele ndogo. 471 00:21:49,490 --> 00:21:51,700 Hakuna aina ya optimization katika pale kwamba 472 00:21:51,700 --> 00:21:54,350 wanaweza basi mimi mimba baada ya tu n au hivyo hatua. 473 00:21:54,350 --> 00:21:57,080 Hivyo kweli, uteuzi aina, omega ya n squared. 474 00:21:57,080 --> 00:22:00,667 >> Nini juu ya insertion aina, ambapo mimi alichukua ambao nilipewa, na kisha mimi plopped naye 475 00:22:00,667 --> 00:22:01,750 au wake katika mahali sahihi? 476 00:22:01,750 --> 00:22:04,958 Kisha mimi aliendelea na mtu wa pili, plopped kwake katika mahali pa haki. 477 00:22:04,958 --> 00:22:07,910 Kisha mtu mwingine, plopped kwake katika mahali pa haki. 478 00:22:07,910 --> 00:22:10,537 Taarifa kwamba hii ni sana linear, hivyo kusema. 479 00:22:10,537 --> 00:22:12,620 Mimi nina line moja kwa moja, mimi nina si kwenda na kurudi, 480 00:22:12,620 --> 00:22:16,080 Sijawahi kuangalia nyuma kwa kweli, lakini nini kinatokea wakati mimi mtatizeni 481 00:22:16,080 --> 00:22:20,302 au wake katika mwanzo wa orodha kama tulivyofanya Jumatatu? 482 00:22:20,302 --> 00:22:21,010 Nini kinatokea? 483 00:22:21,010 --> 00:22:21,510 Yeah? 484 00:22:21,510 --> 00:22:23,122 Watazamaji: [inaudible]. 485 00:22:23,122 --> 00:22:24,830 SPIKA: Yeah, kwamba mara catch, haki? 486 00:22:24,830 --> 00:22:26,746 Unaweza kukumbuka kutoka classmates wako, kama 487 00:22:26,746 --> 00:22:29,670 walikuwa wakifanya harakati yoyote na miguu yao ili kwamba ilikuwa operesheni. 488 00:22:29,670 --> 00:22:33,610 Hivyo kama kulikuwa na watu watatu hapa na mtu mpya mali, kuna njia juu, 489 00:22:33,610 --> 00:22:37,360 juu ya hatua ya muda mrefu kama hii, hakika, yeye au yeye anaweza tu kwenda hadi mwisho. 490 00:22:37,360 --> 00:22:40,074 Lakini kama sisi ni kufikiri kuhusu kompyuta na safu ya kumbukumbu, 491 00:22:40,074 --> 00:22:41,990 watu hawa wanaenda kuwa na changa juu ya 492 00:22:41,990 --> 00:22:43,260 kufanya chumba kwa mtu huyo. 493 00:22:43,260 --> 00:22:46,930 Na ili n minus 1 shufflings, n minus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 minus 3 shufflings ni aina tu ya kinachotokea nyuma yangu, si mbele yangu 495 00:22:50,660 --> 00:22:52,710 kama kabla, katika baadhi ya hisia. 499 00:22:52,557 --> 00:22:54,640 Sasa kama kando, na kama unaweza kuwa na kuonekana online 500 00:22:54,640 --> 00:22:57,699 kama wewe kuanza poking kuzunguka juu ya kila aina, kuna wale wengi mbalimbali 501 00:22:57,699 --> 00:22:59,490 huko nje, baadhi yao bora kuliko wengine. 502 00:22:59,490 --> 00:23:02,200 Hakika, bogosort ni moja hiyo ni aina ya furaha na kuangalia up. 503 00:23:02,200 --> 00:23:06,650 Bogosort inachukua seti ya namba au kusema staha ya kadi, 504 00:23:06,650 --> 00:23:09,870 nasibu shuffles yao, na hundi kama wao ni sorted. 505 00:23:09,870 --> 00:23:12,130 Na kama si, gani tena. 506 00:23:12,130 --> 00:23:14,140 Na kama si, gani tena. 507 00:23:14,140 --> 00:23:15,440 Kama siyo, anafanya hivyo tena. 508 00:23:15,440 --> 00:23:17,060 Incredibly kijinga. 509 00:23:17,060 --> 00:23:19,520 >> Na hakika, kama kusoma kama makala Wikipedia, 510 00:23:19,520 --> 00:23:21,200 jina la utani wake ni aina ya kijinga. 511 00:23:21,200 --> 00:23:25,180 Ni hatimaye kazi, hopefully, kutokana na muda wa kutosha, 512 00:23:25,180 --> 00:23:28,240 lakini kwamba kiasi cha muda inaweza kuchukua muda kabisa. 513 00:23:28,240 --> 00:23:31,650 Hivyo kama mimi naweza, hebu mambo kasi up kutokana na mfano Mary Beth ya awali, 514 00:23:31,650 --> 00:23:35,150 kwa kuwa chache mambo zaidi, lakini wasindikaji mbili zaidi. 515 00:23:35,150 --> 00:23:37,100 Watu wawili, kama wewe bila akili kujiunga na yangu. 516 00:23:37,100 --> 00:23:40,972 Vipi kuhusu 1 zaidi ya hapa, na hebu go-- hakuna mtu zaidi ya hapo? 517 00:23:40,972 --> 00:23:41,722 Hakuna mtu zaidi ya hapo? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 Wewe na nyeusi shati, ndiyo, kuja juu chini. 520 00:23:44,190 --> 00:23:45,000 Haki wote, nini jina lako? 521 00:23:45,000 --> 00:23:45,720 >> Watazamaji: Peter. 522 00:23:45,720 --> 00:23:46,100 >> SPIKA: Nini hiyo? 523 00:23:46,100 --> 00:23:46,766 >> Watazamaji: Peter. 524 00:23:46,766 --> 00:23:49,450 SPIKA: Peter, David, nzuri ya kukutana na wewe. 525 00:23:49,450 --> 00:23:53,670 Zote haki, tuna Peter hapa, kama wewe wanataka kuja kwenye meza ya zaidi ya hapa. 526 00:23:53,670 --> 00:23:54,550 Na nini jina lako? 527 00:23:54,550 --> 00:23:55,216 >> Watazamaji: Elena. 528 00:23:55,216 --> 00:23:55,970 SPIKA: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, nzuri ya kukutana na wewe. 530 00:23:57,030 --> 00:23:58,060 Elena kukutana na Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 Na tutaweza haja Andrew up hapa kama vizuri, tafadhali. 533 00:24:02,290 --> 00:24:06,107 Na changamoto yako ni kwenda kuwa na aina staha ya kadi. 534 00:24:06,107 --> 00:24:08,190 Na kama usio wa kawaida, staha ya kadi lazima hatimaye 535 00:24:08,190 --> 00:24:11,064 kutatuliwa kitu kidogo kama hii ambapo tutaweza kufanya klabu, basi 536 00:24:11,064 --> 00:24:13,660 spades, basi mioyo na almasi, kutoka Ace kama moja, 537 00:24:13,660 --> 00:24:15,570 njia yote hadi mfalme. 538 00:24:15,570 --> 00:24:20,890 >> kadi mimi nina kwenda kukupa ni kwenda kuwa 52 katika wingi. 539 00:24:20,890 --> 00:24:23,160 Sisi ni kwenda vile vile muda, katika muda tu. 540 00:24:23,160 --> 00:24:26,410 Sisi ni kwenda kutupa Andrew juu ya screen hapa, 541 00:24:26,410 --> 00:24:28,170 ili kuangalia kama wewe kufanya hivyo. 542 00:24:28,170 --> 00:24:31,070 Na hivyo kwamba haya yote ni wazi zaidi, 543 00:24:31,070 --> 00:24:33,490 hizi ni kadi I got juu ya Amazon. 544 00:24:33,490 --> 00:24:42,861 Hivyo wao ni tayari nasibu Iliyopangwa, na sisi ni kwenda kwa mara wewe. 545 00:24:42,861 --> 00:24:44,610 Na tunakwenda kuitunza halisi wakati huu, 546 00:24:44,610 --> 00:24:47,820 hivyo sisi ni kwenda kujaribu kushinikiza wewe kwa sababu vinginevyo hii kupata tedious 547 00:24:47,820 --> 00:24:48,460 haraka. 548 00:24:48,460 --> 00:24:53,860 Kama unaweza kuendelea na aina 52 mambo pamoja kupitia baadhi ya njia, sasa. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> Na tena, kama sisi kuangalia hizi guys kufanya nini, katika mwisho 551 00:25:07,180 --> 00:25:10,200 ni kwenda kuzalisha dhahiri Matokeo yake, kufikiri juu ya kweli 552 00:25:10,200 --> 00:25:12,962 jinsi re kila kufanya hivyo, jinsi gani unaweza kuelezea. 553 00:25:12,962 --> 00:25:15,045 Kwa sababu tena, hizi ni taratibu zote, algorithms 554 00:25:15,045 --> 00:25:17,090 kwamba sisi kuchukua kwa nafasi kama binadamu. 555 00:25:17,090 --> 00:25:22,349 Lakini ve pengine kwa muda mrefu alikuwa Intuition, kwa muda mrefu kabla hata 556 00:25:22,349 --> 00:25:24,390 mawazo kuhusu kuchukua sayansi ya kompyuta darasa wewe 557 00:25:24,390 --> 00:25:27,223 anaweza kuwa na Intuition na ambayo kutatua matatizo kama hii. 558 00:25:27,223 --> 00:25:29,560 Lakini mara moja wewe kutambua mwelekeo na kuanza 559 00:25:29,560 --> 00:25:32,407 kurasimisha hatua ambayo wewe kutatua matatizo haya, 560 00:25:32,407 --> 00:25:35,490 utapata kwamba unaweza kutatua mengi zaidi ya kuvutia na tata zaidi 561 00:25:35,490 --> 00:25:39,190 matatizo ya haraka. 562 00:25:39,190 --> 00:25:42,351 Hivyo mtu kutoka watazamaji, ni nini kipengele angalau moja ya algorithm 563 00:25:42,351 --> 00:25:43,350 kwamba wao ni kutumia hapa? 564 00:25:43,350 --> 00:25:44,275 >> Watazamaji: [inaudible] 565 00:25:44,275 --> 00:25:45,150 SPIKA: Nini hiyo? 566 00:25:45,150 --> 00:25:47,062 Watazamaji: Kwa nyayo. 567 00:25:47,062 --> 00:25:47,770 SPIKA: Kwa nyayo. 568 00:25:47,770 --> 00:25:50,630 Hivyo kwanza wao ni kuunganisha yote ya almasi pamoja 569 00:25:50,630 --> 00:25:52,560 inaonekana, yote ya mioyo pamoja inaonekana, 570 00:25:52,560 --> 00:25:56,520 na kadhalika, bila heshima kwa idadi ya kadi. 571 00:25:56,520 --> 00:26:00,900 Na sasa wao kuonekana, kwa mfano, kuwa kuchagua yao na idadi. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Nzuri sana. 574 00:26:08,910 --> 00:26:12,370 >> Haki zote, hivyo nini kinaendelea kuwa hatua ya mwisho basi hapa? 575 00:26:12,370 --> 00:26:16,950 Mara baada ya tuna nne suti sorted, nini kufanya sisi haja ya kufanya ili piles nne 576 00:26:16,950 --> 00:26:20,059 ili kufikia moja namna ya staha, kwa urahisi kabisa? 577 00:26:20,059 --> 00:26:21,350 Kwa hiyo, tunahitaji kuunganisha yao tena. 578 00:26:21,350 --> 00:26:25,160 >> Hivyo kuna wazo kuvutia ambayo tena, daresay, ni Intuitive sana hata 579 00:26:25,160 --> 00:26:28,140 kama unaweza kamwe kuwa slapped aina hiyo ya studio juu yake. 580 00:26:28,140 --> 00:26:31,900 Hii dhana ya msingi ya kugawa tatizo si katika wakati huu nusu, 581 00:26:31,900 --> 00:26:33,410 lakini angalau katika vipande nne. 582 00:26:33,410 --> 00:26:36,810 Kutatua pretty much matatizo ya kimsingi kufanana 583 00:26:36,810 --> 00:26:40,480 katika kutengwa wa kila mmoja, na kisha kuunganisha matokeo. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 Na, bora, kufanyika. 586 00:26:50,140 --> 00:26:52,140 Haki zote, pande zote kubwa ya applause, kama tunaweza. 587 00:26:52,140 --> 00:26:56,480 >> [Makofi] 588 00:26:56,480 --> 00:26:59,740 >> SPIKA: Mimi sijui nini utasikia kufanya na hayo, lakini hapa kwenda. 589 00:26:59,740 --> 00:27:01,690 Asante sana. 590 00:27:01,690 --> 00:27:04,660 Basi hebu angalia, dakika mbili na sekunde nane, 591 00:27:04,660 --> 00:27:07,490 kama Ningependa kutoa changamoto kwa rafiki yako. 592 00:27:07,490 --> 00:27:12,160 Ni nini basi ni kwenda kuwa kuchukua mbali na hii 593 00:27:12,160 --> 00:27:13,830 kwamba tunaweza kujiinua zaidi kwa ujumla? 594 00:27:13,830 --> 00:27:16,080 Naam, kufikiri nyuma safu hii ya idadi, 595 00:27:16,080 --> 00:27:19,060 na kufikiri nyuma sasa kwa baadhi ya pseudocode tumekuwa imeandikwa katika siku za nyuma, 596 00:27:19,060 --> 00:27:22,080 na hii ilikuwa pseudocode kwa kutatua tatizo kitabu cha simu. 597 00:27:22,080 --> 00:27:25,150 Ambapo katika pseudocode mimi enumerated njia zaidi methodical 598 00:27:25,150 --> 00:27:28,400 ya kuelezea jinsi mimi alifanya Intuitive sana algorithm binadamu wa kugawa simu 599 00:27:28,400 --> 00:27:31,650 kitabu katika nusu, kurudia, kurudia, kurudia, mpaka mimi kupata mtu kama Mike Smith, 600 00:27:31,650 --> 00:27:33,790 kama yeye ni kweli katika kitabu cha simu. 601 00:27:33,790 --> 00:27:37,610 >> Lakini mimi aina ya kutumika kile Mimi nitakuita mbinu iterative sana hapa, 602 00:27:37,610 --> 00:27:42,160 katika ilani hasa mstari wa 8 na line 11. 603 00:27:42,160 --> 00:27:46,750 Wale ni ushahidi wa iterative mbinu, mbinu looping, 604 00:27:46,750 --> 00:27:49,040 kwa sababu hiyo hasa tabia wao kushawishi. 605 00:27:49,040 --> 00:27:52,910 Wale wote mistari kusema kwenda kwa line tatu, na unaweza aina ya 606 00:27:52,910 --> 00:27:55,140 kufikiri ya kwamba katika yako macho ya akili ya kuwa kitanzi. 607 00:27:55,140 --> 00:27:59,080 Ni ninawaambieni kwa kwenda nyuma juu ya hatua tatu na kurudia, tena, na tena, 608 00:27:59,080 --> 00:28:00,010 na tena. 609 00:28:00,010 --> 00:28:04,410 >> Lakini nini kama sisi kujiinua wazo muhimu hapa kwamba hatukuwa mara ya mwisho, 610 00:28:04,410 --> 00:28:10,280 na kurahisisha line 8 na line 11 na majirani zao 611 00:28:10,280 --> 00:28:12,840 kama tu hii, katika njano. 612 00:28:12,840 --> 00:28:16,480 Ni si kimsingi shortening pseudocode sana, 613 00:28:16,480 --> 00:28:20,530 lakini ni kubadilisha kimsingi asili ya algorithm yangu. 614 00:28:20,530 --> 00:28:24,220 Nini mimi sasa kusema katika hatua 7, katika hatua 10, 615 00:28:24,220 --> 00:28:29,140 ni kutafuta kwa Mike katika halisi njia hiyo hiyo, 616 00:28:29,140 --> 00:28:31,580 lakini tu katika wa kushoto nusu au nusu ya haki. 617 00:28:31,580 --> 00:28:33,420 >> Hivyo kwa maneno mengine, kama Mimi kuanza kutoka hatua moja, 618 00:28:33,420 --> 00:28:36,150 kuchukua kitabu cha simu, wazi katikati za kitabu cha simu, kuangalia majina, 619 00:28:36,150 --> 00:28:39,010 kama Smith ni kati ya jina ya, piga Mike, mwingine 620 00:28:39,010 --> 00:28:44,340 kama Smith ni mapema katika kitabu, hatua saba kutafuta Mike katika nusu kushoto ya kitabu. 621 00:28:44,340 --> 00:28:47,130 Lakini hiyo aina ya anahisi kama ni kuondoka kwangu kunyongwa, haki? 622 00:28:47,130 --> 00:28:49,240 Katika njano, ni mafundisho, lakini jinsi gani mimi 623 00:28:49,240 --> 00:28:51,870 kutafuta Mike katika wa kushoto nusu ya kitabu cha simu? 624 00:28:51,870 --> 00:28:54,210 Wapi mimi na algorithm ambayo mimi 625 00:28:54,210 --> 00:28:57,100 Unaweza kutafuta kwa mtu kama Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Naam, ni staring us uso kwa uso. 627 00:28:58,980 --> 00:29:03,090 Siwezi literally kutumia exact mpango kwa ufanisi kwenda hadi juu 628 00:29:03,090 --> 00:29:06,490 tena na re-mbio mistari hiyo ya kificho. 629 00:29:06,490 --> 00:29:10,610 >> Hivyo hata ingawa hii anatakiwa kujisikia kama kidogo ya ufafanuzi mzunguko 630 00:29:10,610 --> 00:29:13,480 ambapo wewe ni kujibu mtu ni swali na tu aina ya kuuliza 631 00:29:13,480 --> 00:29:15,990 swali moja tena, kama nini, kwa nini, kwa nini? 632 00:29:15,990 --> 00:29:21,580 Ukweli ni kwa sababu tumekuwa ngumu coded wanandoa wa mistari maalum, hatua ya 4, 633 00:29:21,580 --> 00:29:25,320 ambayo ni kama, na hatua 12, ambayo ni ufanisi mwingine tawi, 634 00:29:25,320 --> 00:29:30,120 kwa sababu tuna hatua hizo stopgap, algorithm hii kusitisha kama sisi 635 00:29:30,120 --> 00:29:32,050 kupata Mike, au kama sisi hawana. 636 00:29:32,050 --> 00:29:36,810 Lakini katika hatua 7 na 10 sasa, tuna nini tutaweza kuwaita algorithm kujirudia. 637 00:29:36,810 --> 00:29:40,420 Na kujirudia ni kweli wazo nguvu hiyo ni akili kidogo bending mara ya kwanza, 638 00:29:40,420 --> 00:29:42,500 kwamba sisi sasa wanaweza kuomba kama ifuatavyo. 639 00:29:42,500 --> 00:29:46,600 >> Kuunganisha aina itakuwa aina mwisho kwamba sisi kuangalia, angalau katika darasa rasmi. 640 00:29:46,600 --> 00:29:50,040 Na ni tofauti kimsingi kutoka kwa wale mitatu iliyopita, na kwa hakika 641 00:29:50,040 --> 00:29:52,140 mwisho nne ikiwa ni pamoja na sisi bogosort. 642 00:29:52,140 --> 00:29:54,810 Hapa ni pseudocode kwa kuunganisha aina. 643 00:29:54,810 --> 00:30:00,170 Wakati juu ya mchango wa mambo n, hivyo kutokana na safu ya ukubwa n, ikiwa ni n chini ya 2, 644 00:30:00,170 --> 00:30:01,040 kurudi. 645 00:30:01,040 --> 00:30:03,610 Hivyo kwa nini mimi kuwa na kwamba sanity kuangalia kwanza? 646 00:30:03,610 --> 00:30:09,477 Nini maana kama mimi mkono wewe safu ambaye urefu n ni chini ya 2? 647 00:30:09,477 --> 00:30:11,060 Ni tayari Iliyopangwa, ni wazi, haki? 648 00:30:11,060 --> 00:30:13,640 Kwa sababu orodha ama ina kipengele moja, ambayo ni trivially 649 00:30:13,640 --> 00:30:15,180 yamepangwa kwa sababu ni Kitu pekee huko. 650 00:30:15,180 --> 00:30:18,138 Au, ni ya kawaida sifuri ambayo ina maana kuna kitu kutatua, hivyo kwa asili 651 00:30:18,138 --> 00:30:18,720 ni Iliyopangwa. 652 00:30:18,720 --> 00:30:20,410 Kuna kitu tu makosa huko. 653 00:30:20,410 --> 00:30:22,310 Hivyo hiyo ni kesi yetu kinachojulikana msingi. 654 00:30:22,310 --> 00:30:24,440 >> Hiyo ni sawa katika roho kwa nini sisi alivyofanya kwa Mike. 655 00:30:24,440 --> 00:30:26,023 Kama Mike katika kitabu cha simu, kumwita. 656 00:30:26,023 --> 00:30:27,740 Kama yeye si huko, kutoa up. 657 00:30:27,740 --> 00:30:31,240 Ni kinachojulikana kesi ya msingi, ili kuhakikisha algorithm hii ifikapo mwisho wa siku 658 00:30:31,240 --> 00:30:33,540 kuacha katika mazingira fulani. 659 00:30:33,540 --> 00:30:37,890 >> Lakini hapa ni leap ya imani sasa, mwingine, aina nusu ya kushoto ya mambo, 660 00:30:37,890 --> 00:30:39,740 kisha kutatua haki nusu ya vipengele, 661 00:30:39,740 --> 00:30:41,189 na kisha kuunganisha halves Iliyopangwa. 662 00:30:41,189 --> 00:30:43,230 Na hapa ni ambapo anahisi kama sisi ni copping nje. 663 00:30:43,230 --> 00:30:46,900 Nimekuwa aliuliza wewe kutatua n vipengele, na mimi nina 664 00:30:46,900 --> 00:30:50,712 akisema, OK, kufanya hivyo kwa kuchagua kushoto na kuchagua haki. 665 00:30:50,712 --> 00:30:52,420 Lakini ninachosema moja Jambo jingine, na hii 666 00:30:52,420 --> 00:30:55,530 ni mandhari muhimu inaonekana katika Intuition hivi sasa, 667 00:30:55,530 --> 00:30:57,380 kuna hatua hii ya tatu ya kuunganisha. 668 00:30:57,380 --> 00:31:00,430 Ambayo hata kama ni inaonekana hivyo bubu katika roho, 669 00:31:00,430 --> 00:31:02,320 kama tu kuunganisha mambo pamoja, inaonekana 670 00:31:02,320 --> 00:31:05,380 kuwa hatua muhimu kuelekea reassembly ya matatizo mawili ambayo 671 00:31:05,380 --> 00:31:07,330 waligawanyika hatimaye katika nusu. 672 00:31:07,330 --> 00:31:12,090 >> Hivyo kuunganisha aina, hebu kufanya hili, kama wewe utakuwa ucheshi mimi, pamoja na moja zaidi maandamano, 673 00:31:12,090 --> 00:31:14,730 hivyo tu kwamba tuna baadhi ya namba kufanya kazi pamoja. 674 00:31:14,730 --> 00:31:19,470 Je, mimi kubadilishana stress nane mipira kwa watu nane? 675 00:31:19,470 --> 00:31:29,320 Zote haki, vipi kuhusu wewe tatu, nne katika sehemu hii, tano, sita, na hebu 676 00:31:29,320 --> 00:31:30,720 je 7, 8, kuja juu up. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, yeah OK. 679 00:31:36,520 --> 00:31:38,640 Minus 8, kuna sisi kwenda, plus 1. 680 00:31:38,640 --> 00:31:39,150 Excellent. 681 00:31:39,150 --> 00:31:42,000 Haki zote kuja juu juu, hebu haraka kukupa idadi. 682 00:31:42,000 --> 00:31:50,800 Namba mbili, namba tatu, namba nne, namba tano, sita, saba, na wanane. 683 00:31:50,800 --> 00:31:52,140 Mimi nane kwa usahihi wakati huu. 684 00:31:52,140 --> 00:31:56,390 >> OK, hivyo kwenda mbele kama unaweza, na hebu kutatua ili awali 685 00:31:56,390 --> 00:31:59,810 kwamba tulikuwa jana ambayo inaonekana kama hii, kama isingekuwa akili. 686 00:31:59,810 --> 00:32:03,620 Na hebu kufanya hivyo mbele ya meza. 687 00:32:03,620 --> 00:32:06,510 Haki zote, hivyo kuunganisha aina. 688 00:32:06,510 --> 00:32:08,820 Hii ni pale ambapo ni kwenda kupata aina ya kuvutia, 689 00:32:08,820 --> 00:32:12,800 kwa sababu mimi wanaonekana kuwa kutoa mwenyewe sana habari chini leo. 690 00:32:12,800 --> 00:32:15,149 >> Hivyo kuunganisha aina ya kwanza ya yote juu ya mchango wa mambo n, 691 00:32:15,149 --> 00:32:18,440 na ni wazi si chini ya mbili, ni nane, hivyo mimi na baadhi ya kazi zaidi ya kufanya. 692 00:32:18,440 --> 00:32:21,140 Hivyo sasa kiakili sisi kama darasa ni sasa katika mwingine tawi, 693 00:32:21,140 --> 00:32:22,540 ambayo ina maana hatua tatu. 694 00:32:22,540 --> 00:32:25,017 Kwanza, mimi kuwa na aina kushoto nusu ya vipengele. 695 00:32:25,017 --> 00:32:26,350 Hivyo ni jinsi gani mimi kwenda juu ya kufanya hii? 696 00:32:26,350 --> 00:32:28,950 Naam, mimi nina kwenda aina ya kiakili kugawanya orodha hapa, 697 00:32:28,950 --> 00:32:30,700 huna kwa kimwili hoja, na mimi nina 698 00:32:30,700 --> 00:32:33,180 kwenda kuzingatia tu juu ya kushoto nusu ya mambo hapa. 699 00:32:33,180 --> 00:32:36,770 Hivyo ni jinsi gani mimi kwenda juu ya kuchagua orodha ya sasa ukubwa nne? 700 00:32:36,770 --> 00:32:38,730 Nini algorithm wangu? 701 00:32:38,730 --> 00:32:42,580 Kwanza mimi kuangalia ni n chini ya miaka miwili, hapana, hivyo mimi kuendelea na mwingine block tena. 702 00:32:42,580 --> 00:32:43,900 Aina kushoto nusu ya vipengele. 703 00:32:43,900 --> 00:32:45,608 >> Hivyo sasa tena, kiakili, na hii ni mahali ambapo 704 00:32:45,608 --> 00:32:49,550 una inaingia mengi ya historia ya akili, kama wewe. 705 00:32:49,550 --> 00:32:51,940 Sasa mimi nina kuchagua kushoto nusu ya nusu kushoto. 706 00:32:51,940 --> 00:32:57,000 Haki zote, hivyo sasa mimi wito kuunganisha yangu huo kuchagua algorithm, ni n chini ya miaka miwili? 707 00:32:57,000 --> 00:33:00,590 Hapana, ni mbili, hivyo nina kutatua kushoto nusu, na nusu ya haki. 708 00:33:00,590 --> 00:33:02,042 Hivyo hapa sisi kwenda, kutatua kushoto nusu. 709 00:33:02,042 --> 00:33:03,750 Kwa nini si wewe tu kuchukua hatua moja mbele. 710 00:33:03,750 --> 00:33:04,415 Nini jina lako? 711 00:33:04,415 --> 00:33:04,860 >> Watazamaji: Darren. 712 00:33:04,860 --> 00:33:05,260 >> SPIKA: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan ina kupitiwa mbele. 714 00:33:06,040 --> 00:33:06,748 >> Watazamaji: Darren. 715 00:33:06,748 --> 00:33:09,000 SPIKA: Darren, kufanyika. 716 00:33:09,000 --> 00:33:10,090 Je, kusema Darren au Dan? 717 00:33:10,090 --> 00:33:10,550 >> Watazamaji: Darren. 718 00:33:10,550 --> 00:33:11,216 >> SPIKA: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren ameongeza mbele na yeye ni sasa Iliyopangwa. 720 00:33:14,422 --> 00:33:16,130 Na hii ni karibu inane madai, haki? 721 00:33:16,130 --> 00:33:18,862 Mimi si kweli wanaonekana kuwa kufikia kitu chochote, lakini hebu kuendelea. 722 00:33:18,862 --> 00:33:20,820 Sasa basi mimi aina haki nusu ya vipengele. 723 00:33:20,820 --> 00:33:21,200 Nini jina lako? 724 00:33:21,200 --> 00:33:21,690 >> Watazamaji: Luke. 725 00:33:21,690 --> 00:33:22,273 >> SPIKA: Luke. 726 00:33:22,273 --> 00:33:23,400 Kuja juu, hatua mbele. 727 00:33:23,400 --> 00:33:25,640 Kufanyika, mimi kuwa yamepangwa Luke. 728 00:33:25,640 --> 00:33:28,570 nusu kushoto ni sasa sorted na nusu haki ni sasa Iliyopangwa, 729 00:33:28,570 --> 00:33:30,770 lakini tena, kuna hatua muhimu hapa. 730 00:33:30,770 --> 00:33:32,940 Je, mimi ijayo haja ya kufanya? 731 00:33:32,940 --> 00:33:33,941 Kuunganisha halves Iliyopangwa. 732 00:33:33,941 --> 00:33:36,648 Sasa tunakwenda tu kila mtu na kurudi katika njia hii, 733 00:33:36,648 --> 00:33:38,620 kwa sababu mimi aina ya haja baadhi ya nafasi mwanzo. 734 00:33:38,620 --> 00:33:40,411 Ni karibu kama haya guys ni juu ya meza, 735 00:33:40,411 --> 00:33:42,460 na mimi haja ya baadhi ya chumba kwa hoja yao kote juu ya. 736 00:33:42,460 --> 00:33:44,170 Hivyo nina kwenda kwa kuunganisha you guys kwa kuangalia 737 00:33:44,170 --> 00:33:45,960 katika nusu kushoto na nusu wa kulia. 738 00:33:45,960 --> 00:33:48,740 Na ambaye ni wazi anakuja kwanza, kushoto nusu au nusu haki? 739 00:33:48,740 --> 00:33:52,710 Hivyo nusu haki, hivyo hebu hoja juu ya Luke hapa kwa Darren ya nafasi ya awali. 740 00:33:52,710 --> 00:33:57,640 Na sasa kwa kuunganisha nusu yao ya kushoto katika, Darren kinaendelea kwa hoja haki pale. 741 00:33:57,640 --> 00:33:59,750 >> Hivyo anahisi kama karibu Bubble aina athari, 742 00:33:59,750 --> 00:34:02,482 lakini algorithm yangu ya msingi, tofauti sana wakati huu. 743 00:34:02,482 --> 00:34:04,815 Lakini sasa ni ambapo mambo kupata kidogo annoying kwa sababu wewe 744 00:34:04,815 --> 00:34:06,810 kuwa na rewind kiakili wapi mimi kuondoka mbali. 745 00:34:06,810 --> 00:34:09,893 Nimekuwa tu ilijiunga halves sorted, ambayo ina maana mimi nina ambapo katika algorithm wangu? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Nina kutatua nusu haki, haki? 748 00:34:13,770 --> 00:34:15,910 >> Kama wewe rewind, literally juu ya video, itabidi 749 00:34:15,910 --> 00:34:18,339 kuona kwamba sisi got hii hatua ya Luka na Darren 750 00:34:18,339 --> 00:34:21,370 na kuchagua kushoto nusu ya nusu kushoto. 751 00:34:21,370 --> 00:34:23,430 Kisha sisi ilijiunga wale halves sorted, ambayo 752 00:34:23,430 --> 00:34:27,941 ina maana hatua ya pili ni aina nusu haki ya nusu kushoto. 753 00:34:27,941 --> 00:34:29,649 Haki zote, hivyo hebu kufanya hivyo haraka zaidi. 754 00:34:29,649 --> 00:34:33,282 Haki wote, sita, mimi nina kwenda kudai wewe ni sasa yamepangwa, kuja juu mbele. 755 00:34:33,282 --> 00:34:33,990 Nini jina lako? 756 00:34:33,990 --> 00:34:34,589 >> Watazamaji: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> SPIKA: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano sasa ni Iliyopangwa. 759 00:34:36,010 --> 00:34:36,450 Na nini jina lako? 760 00:34:36,450 --> 00:34:37,080 >> Watazamaji: Alex. 761 00:34:37,080 --> 00:34:38,379 >> SPIKA: Alex sasa ni Iliyopangwa. 762 00:34:38,379 --> 00:34:40,750 Kushoto nusu, nusu haki, nini hatua ya mwisho? 763 00:34:40,750 --> 00:34:41,250 Kuunganisha. 764 00:34:41,250 --> 00:34:44,310 Pretty yasiyo na maana, hivyo mimi nina kwenda kuunganisha katika sita, 765 00:34:44,310 --> 00:34:46,930 kuchukua hatua nyuma, nane, kuchukua hatua nyuma. 766 00:34:46,930 --> 00:34:49,530 Na sasa taarifa hii ni takeaway muhimu, nini 767 00:34:49,530 --> 00:34:53,930 ni sasa kweli kuhusu nusu ya kushoto ya orodha, bila kujali jinsi sisi ilianza? 768 00:34:53,930 --> 00:34:55,090 Ni vyema. 769 00:34:55,090 --> 00:34:57,750 >> Sasa ni si vyema katika mpango kubwa ya mambo, 770 00:34:57,750 --> 00:35:00,250 lakini ni vyema kujitegemea ya nusu nyingine. 771 00:35:00,250 --> 00:35:04,100 Sasa nini hatua niko juu ya kama mimi kuweka rewinding jinsi hadithi alianza? 772 00:35:04,100 --> 00:35:05,680 Sasa nina kutatua nusu ya haki. 773 00:35:05,680 --> 00:35:07,630 Hivyo sasa sisi ni njia nyuma katika mwanzo wa hadithi, 774 00:35:07,630 --> 00:35:08,921 na hebu kufanya hivyo kwa kasi zaidi. 775 00:35:08,921 --> 00:35:11,320 Hivyo nina kwenda kwa aina nusu haki ya orodha nzima. 776 00:35:11,320 --> 00:35:13,060 Nini hatua ya pili? 777 00:35:13,060 --> 00:35:15,840 Aina kushoto nusu ya nusu ya haki. 778 00:35:15,840 --> 00:35:18,715 Aina kushoto nusu ya kushoto nusu ya nusu ya haki. 779 00:35:18,715 --> 00:35:19,590 Na nini jina lako? 780 00:35:19,590 --> 00:35:20,230 >> Watazamaji: Omar. 781 00:35:20,230 --> 00:35:21,970 >> SPIKA: Omar, hatua mbele, kufanyika. 782 00:35:21,970 --> 00:35:22,860 Nusu kushoto ni Iliyopangwa. 783 00:35:22,860 --> 00:35:23,330 Na nini jina lako? 784 00:35:23,330 --> 00:35:23,820 >> Watazamaji: Chris. 785 00:35:23,820 --> 00:35:25,620 >> SPIKA: Chris, kuchukua hatua mbele, wewe ni sasa Iliyopangwa. 786 00:35:25,620 --> 00:35:27,010 Nini hatua muhimu sasa? 787 00:35:27,010 --> 00:35:27,510 Kuunganisha. 788 00:35:27,510 --> 00:35:30,509 Hivyo mtu ni kwenda kuunganisha katika nafasi hapa, kama unaweza kuchukua hatua nyuma, 789 00:35:30,509 --> 00:35:32,930 na tatu ni kwenda kuchukua hatua nyuma, kuunganisha. 790 00:35:32,930 --> 00:35:38,080 Hivyo nusu ya kushoto ya nusu haki, sasa ni Iliyopangwa. 791 00:35:38,080 --> 00:35:41,747 Kwa kweli, algorithm hii anahisi kama sisi ni kupoteza muda njia zaidi kuliko kabla, 792 00:35:41,747 --> 00:35:44,830 lakini kama sisi alifanya hivyo katika muda halisi, tutaweza kuona nini takeaways kwenda kuwa. 793 00:35:44,830 --> 00:35:47,970 Sasa hapa mimi, haki nusu ya nusu haki, 794 00:35:47,970 --> 00:35:50,170 basi mimi kwenda mbele na aina nusu kushoto. 795 00:35:50,170 --> 00:35:51,482 Hatua ya mbele, nini jina lako? 796 00:35:51,482 --> 00:35:52,190 Watazamaji: Ramsey. 797 00:35:52,190 --> 00:35:53,210 SPIKA: Ramsey ni sasa Iliyopangwa. 798 00:35:53,210 --> 00:35:53,570 Nini jina lako? 799 00:35:53,570 --> 00:35:54,200 >> Watazamaji: Marina. 800 00:35:54,200 --> 00:35:57,033 >> SPIKA: Marina ni sasa yamepangwa kama vizuri, kama wewe kuchukua hatua moja mbele. 801 00:35:57,033 --> 00:36:00,690 Hatua muhimu ya hapa ni sasa kuunganisha, mimi nina kwenda kung'oa kutoka kwenye orodha ya wangu wawili, 802 00:36:00,690 --> 00:36:01,720 kushoto na kulia. 803 00:36:01,720 --> 00:36:05,150 Tano ni kwenda kuja kwanza, na saba ni kwenda kuja ijayo. 804 00:36:05,150 --> 00:36:06,410 Na tena, hii ni makusudi. 805 00:36:06,410 --> 00:36:08,535 ukweli kwamba wao ni kuchukua hatua mbele na nyuma 806 00:36:08,535 --> 00:36:12,997 ni maana ya kuwakilisha kwamba tunaweza si kufanya algorithm hii katika nafasi ya kama kwa urahisi 807 00:36:12,997 --> 00:36:15,830 kama Bubble aina, na uteuzi aina, na insertion aina ambapo sisi tu 808 00:36:15,830 --> 00:36:16,960 naendelea swapping watu. 809 00:36:16,960 --> 00:36:19,940 I literally haja aina karatasi ya mwanzo katika ambayo 810 00:36:19,940 --> 00:36:21,827 kuweka folks hizi wakati mimi kufanya kuunganisha, 811 00:36:21,827 --> 00:36:23,410 na kisha siwezi kuweka yao nyuma katika mahali. 812 00:36:23,410 --> 00:36:27,260 Na kwamba ni muhimu kwa sababu mimi nina kutumia rasilimali mpya, nafasi, si tu wakati. 813 00:36:27,260 --> 00:36:28,270 >> OK, hii ni ajabu. 814 00:36:28,270 --> 00:36:32,050 Kushoto nusu ni Iliyopangwa, nusu haki ni sorted, sasa kuwa muhimu kuunganisha hatua. 815 00:36:32,050 --> 00:36:33,450 Jinsi mimi kwenda kuunganisha hii? 816 00:36:33,450 --> 00:36:35,470 Hivyo kama wewe utakuwa kufuata yangu mkono wa kushoto na mkono wa kulia, 817 00:36:35,470 --> 00:36:38,930 Mimi nina kwenda kwa uhakika mkono wangu wa kushoto katika nusu ya kushoto, upande wangu wa kulia 818 00:36:38,930 --> 00:36:42,680 katika nusu haki, na sasa mimi kuwa na kuamua hatua kwa hatua nani wa kuunganisha katika. 819 00:36:42,680 --> 00:36:44,650 Ambaye ni wazi anakuja kwanza? 820 00:36:44,650 --> 00:36:45,150 Namba moja. 821 00:36:45,150 --> 00:36:47,327 Hivyo kuja juu zaidi ya hapa, hapa ni mwanzo wetu pedi. 822 00:36:47,327 --> 00:36:49,910 Hivyo sasa namba moja, na tangazo la nini la kufanya kwa mkono wangu wa kulia, 823 00:36:49,910 --> 00:36:54,152 Mimi nina kwenda kwa hoja upande wangu wa kulia moja hatua ya juu kwa uhakika namba tatu, 824 00:36:54,152 --> 00:36:55,860 na sasa nina kufanya uamuzi huo. 825 00:36:55,860 --> 00:36:58,387 Na kwa kweli kusimama haki katika mbele ya Luke hapa kama unaweza, 826 00:36:58,387 --> 00:36:59,720 kwa sababu hii ni mwanzo wetu pedi. 827 00:36:59,720 --> 00:37:00,610 Hivyo ajaye ijayo? 828 00:37:00,610 --> 00:37:05,000 Tuna Luke na namba mbili au Chris na idadi tatu. 829 00:37:05,000 --> 00:37:07,460 Ni wazi Luke, idadi mbili, hivyo kuja hapa. 830 00:37:07,460 --> 00:37:11,270 >> Lakini mkono wangu wa kushoto sasa ni kwenda kuwa incremented kwa kumweka katika Darren, 831 00:37:11,270 --> 00:37:15,160 na hapa ni muhimu kuchukua mbali na kuunganisha, mimi nina kwenda kuendelea kufanya hivyo, 832 00:37:15,160 --> 00:37:17,340 ni wazi, kama wewe aina ya kufuata mantiki. 833 00:37:17,340 --> 00:37:19,670 Lakini mikono yangu ni kamwe kwenda nyuma, 834 00:37:19,670 --> 00:37:23,861 ambayo ina maana mimi nina milele tu kuhamia kushoto na mchakato wangu kuunganisha, 835 00:37:23,861 --> 00:37:26,360 na kwamba itakuja kuwa muhimu kwa uchambuzi wetu katika muda tu. 836 00:37:26,360 --> 00:37:27,859 >> Hivyo sasa hebu kumaliza hii kwa kasi. 837 00:37:27,859 --> 00:37:31,650 Hivyo tatu huja ijayo, kisha nne huja ijayo, 838 00:37:31,650 --> 00:37:38,750 na sasa tano huja ijayo, basi sita, na saba, na kisha hatimaye nane. 839 00:37:38,750 --> 00:37:42,960 Anahisi kama algorithm slowest bado, lakini si kama sisi kweli 840 00:37:42,960 --> 00:37:45,510 kuendesha katika aina hiyo ya saa kasi, hivyo 841 00:37:45,510 --> 00:37:48,106 kusema, na huo Baada ya kuangalia saa kama kabla. 842 00:37:48,106 --> 00:37:48,605 Kwa nini? 843 00:37:48,605 --> 00:37:51,100 Naam, Hebu kuchukua kuangalia matokeo ya mwisho. 844 00:37:51,100 --> 00:37:56,990 >> Hebu kwenda nyuma zaidi ya hapa, basi mimi kuvuta up maandamano kuibua 845 00:37:56,990 --> 00:37:59,030 ya nini sisi tu hawakuwa. 846 00:37:59,030 --> 00:38:06,110 Zooming katika hapa, juu ya hili ukurasa hapa, kuwaambia Firefox 847 00:38:06,110 --> 00:38:08,200 kwamba tunataka foleni up katika sanduku hii, hebu 848 00:38:08,200 --> 00:38:11,260 kusema Bubble aina, na ambayo sisi ni sasa vizuri familiar, 849 00:38:11,260 --> 00:38:14,130 uteuzi aina, ambayo ni mwingine haki moja kwa moja moja, 850 00:38:14,130 --> 00:38:18,250 na sasa leo kuunganisha aina, ambayo itakuwa mwisho wetu climactic. 851 00:38:18,250 --> 00:38:21,530 sababu ilichukua muda mrefu sana hapa na binadamu na mimi kwa maneno ni, 852 00:38:21,530 --> 00:38:23,480 wazi, mimi nina akielezea kila hatua. 853 00:38:23,480 --> 00:38:26,920 Lakini kama wewe tu nitafanya hii, kiasi kama tulivyofanya Bubble aina na uteuzi 854 00:38:26,920 --> 00:38:30,890 aina si tu kuibua, kuangalia tu kiasi gani kwa ufanisi zaidi 855 00:38:30,890 --> 00:38:33,330 leveraging hii ya mgawanyiko na mshindi 856 00:38:33,330 --> 00:38:39,150 inaweza kuwa wakati kutumika kwa kuweka data hiyo ni hata ukubwa nane, lakini hata sana, 857 00:38:39,150 --> 00:38:39,970 kubwa sana. 858 00:38:39,970 --> 00:38:44,585 Mimi kukupa kuunganisha aina, kwa upande upande na algorithms hizi nyingine. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Hii ni kwenda kupata chungu haraka, na mwisho 861 00:38:58,530 --> 00:39:00,890 si hasa climactic, wao tu kuishia Iliyopangwa. 862 00:39:00,890 --> 00:39:05,280 Lakini muhimu kuchukua ni kwamba kuangalia ni kiasi gani kwa kasi kuunganisha aina 863 00:39:05,280 --> 00:39:08,110 mara, isipokuwa wewe kufikiri mimi nina aina tu ya messing na wewe. 864 00:39:08,110 --> 00:39:13,100 Kama sisi kufanya wakati huu moja ya mwisho, Hebu upya hii, hebu kwenda nyuma 865 00:39:13,100 --> 00:39:14,960 na kuchagua Bubble aina, na tu kwa ajili ya mateke, 866 00:39:14,960 --> 00:39:17,330 hebu kuchagua insertion aina, tu kwa ajili ya hatua nzuri. 867 00:39:17,330 --> 00:39:20,020 Na wakati huu tena, hebu kuchagua kuunganisha aina na hebu 868 00:39:20,020 --> 00:39:21,595 kweli kuendesha upande haya kwa upande. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> Na si, kwa kweli, fluke. 871 00:39:26,930 --> 00:39:31,140 Kile nimepata kufanyika ni kwa ufanisi nimekuwa kugawanywa pembejeo yangu katika nusu, tena, 872 00:39:31,140 --> 00:39:32,240 na tena, na tena. 873 00:39:32,240 --> 00:39:35,590 Na kuna tu hivyo mara nyingi unaweza kugawanya mchango wako katika nusu, kushoto 874 00:39:35,590 --> 00:39:36,240 na kulia. 875 00:39:36,240 --> 00:39:39,425 Nini formula kwamba sisi kuendelea kuona kwamba inaeleza mgawanyiko katika nusu 876 00:39:39,425 --> 00:39:41,050 tena, na tena, na tena, na tena? 877 00:39:41,050 --> 00:39:41,890 >> Watazamaji: Ingia n. 878 00:39:41,890 --> 00:39:42,760 >> SPIKA: Ingia n. 879 00:39:42,760 --> 00:39:46,300 Lakini basi kuna hatua moja nyingine muhimu ni, algorithm hii si logi n hatua. 880 00:39:46,300 --> 00:39:48,992 Kama walikuwa tu logi n hatua, sisi itakuwa katika tatizo moja 881 00:39:48,992 --> 00:39:51,200 kama kabla ya ambapo hatuwezi kuwa kuhakikisha kila kitu ya Iliyopangwa. 882 00:39:51,200 --> 00:39:54,480 Una minimally kuangalia mambo n kuwa na uhakika n mambo ni vyema, 883 00:39:54,480 --> 00:39:55,950 vinginevyo ni leap ya imani. 884 00:39:55,950 --> 00:39:59,810 >> Hivyo ni ya chini logi n hatua, lakini nini kuhusu hili kuunganisha hatua muhimu 885 00:39:59,810 --> 00:40:04,370 ambapo mimi ilijiunga nusu wangu wa kushoto na kulia nusu na kutembea katika hatua? 886 00:40:04,370 --> 00:40:06,980 Jinsi hatua nyingi ni kwamba kwa kuunganisha? 887 00:40:06,980 --> 00:40:10,150 Ni n, lakini mimi si tu kuunganisha wakati wa mwisho. 888 00:40:10,150 --> 00:40:15,089 Juu ya kila ya simu hizo nested, juu ya kila ya huingiza wale nested, mimi bado Iliyopangwa. 889 00:40:15,089 --> 00:40:18,380 Mimi ilijiunga guys hizi mbili, kisha hizi mbili guys, basi guys hizi mbili na kadhalika. 890 00:40:18,380 --> 00:40:19,955 >> Hivyo mimi kuunganisha tena, na tena. 891 00:40:19,955 --> 00:40:20,580 Ni mara ngapi? 892 00:40:20,580 --> 00:40:23,510 Hivyo kila wakati mimi kugawanywa orodha katika nusu, mimi kuunganisha. 893 00:40:23,510 --> 00:40:25,460 Kugawanya orodha katika nusu, kufanya kuunganisha. 894 00:40:25,460 --> 00:40:28,570 Hivyo kama kugawa orodha kifanyike mara logi n, 895 00:40:28,570 --> 00:40:33,880 na kuunganisha hatimaye inachukua n hatua, nini inaweza kuwa sasa juu 896 00:40:33,880 --> 00:40:37,000 amefungwa juu ya mbio wakati wa algorithm yetu? 897 00:40:37,000 --> 00:40:37,980 n logi n. 898 00:40:37,980 --> 00:40:40,560 >> Na hakika, kwamba ni nini tumekuwa mafanikio hapa. 899 00:40:40,560 --> 00:40:44,650 Hivyo kujisikia kwamba unaweza kuona kuibua wakati mambo matatu kukimbia upande kwa upande 900 00:40:44,650 --> 00:40:47,930 ni n squared dhidi ya n mraba dhidi ya n logi n. 901 00:40:47,930 --> 00:40:51,010 Ambayo kimsingi tutaweza kuona, si tu leo ​​lakini katika siku zijazo, 902 00:40:51,010 --> 00:40:52,760 ni mengi, mengi zaidi. 903 00:40:52,760 --> 00:40:56,010 raundi ya applause kwa guys haya, Mimi malipo yao na mipira stress. 904 00:40:56,010 --> 00:41:00,260 Hebu kuahirisha hapa leo, na sisi kuona juu ya Jumatatu. 905 00:41:00,260 --> 00:41:02,255