1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> Tagapagsalita: Lahat ng karapatan, ito ay CS50. 3 00:00:14,910 --> 00:00:19,020 Ito ang katapusan ng linggo tatlong, at kung hindi mo kinuha bentahe na, 4 00:00:19,020 --> 00:00:21,790 malaman na magkakaroon ng tanghalian Biyernes ito gaya ng dati, kung saan 5 00:00:21,790 --> 00:00:25,430 Maaari mong tangkilikin ang mahusay na pag-uusap at pagkain sa Sunog at Yelo 6 00:00:25,430 --> 00:00:27,980 kasama ang ilan sa CS50 ni kawani at mga kamag-aral. 7 00:00:27,980 --> 00:00:30,170 Magtungo sa URL na ito dito. 8 00:00:30,170 --> 00:00:33,420 >> Ngayon maaari mong isipin ang, o sa iyo Maaaring madaling ma-kilala sa, 9 00:00:33,420 --> 00:00:35,970 mga bagay na ito dito, na ay binibigyan out sa dulo 10 00:00:35,970 --> 00:00:37,850 ng semestre para sa maraming mga klase. 11 00:00:37,850 --> 00:00:40,870 Kaya-tinatawag na pagsusulit asul na mga libro, kung saan mong isulat ang iyong mga sagot sa mga pagsusulit. 12 00:00:40,870 --> 00:00:44,240 Ngayon Mayroon akong dito 26 tulad asul na mga aklat, sa bawat isa sa kanila 13 00:00:44,240 --> 00:00:47,580 nakasulat ang isang pangalan, A sa pamamagitan Z. At sa katunayan ang pangalan ay na simple, A 14 00:00:47,580 --> 00:00:50,490 sa pamamagitan ng Z. At isa sa ang mga layunin sa kamay ngayon 15 00:00:50,490 --> 00:00:53,910 ay magiging upang magpatuloy kung ano namin na nagsimula sa Monday, kung saan ay hindi 16 00:00:53,910 --> 00:00:57,830 kaya magkano ng pagtingin sa code, ngunit talagang pagtingin sa mga ideya at mga problema paglutas. 17 00:00:57,830 --> 00:01:00,170 Isa sa mga layunin at mga pangako ng kursong ito 18 00:01:00,170 --> 00:01:02,985 ay upang magturo sa iyo mag-isip nang higit pa Maingat, mas methodically, 19 00:01:02,985 --> 00:01:05,400 at upang malutas ang mga problema nang mas mabisa. 20 00:01:05,400 --> 00:01:09,526 At sa katunayan, maaari naming gawin na talaga nang walang kahit pagpindot sa isang linya ng code. 21 00:01:09,526 --> 00:01:12,150 Kaya ba akong magkaroon ng isang pares ng mga elepante up dito ngayon, orange at asul, 22 00:01:12,150 --> 00:01:15,780 kung maaari naming makakuha ng isang volunteer, siguro mas malayo mula sa likod kaysa sa karaniwan. 23 00:01:15,780 --> 00:01:18,070 Paano ang tungkol doon, dumating pababa. 24 00:01:18,070 --> 00:01:24,180 Ang layunin ng kung saan ay magiging sa tulungan plus pangasiwaan ang eksaminasyong ito dito. 25 00:01:24,180 --> 00:01:24,935 Ano ang inyong pangalan? 26 00:01:24,935 --> 00:01:25,768 >> Madla: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 Tagapagsalita: Mary Beth, dumating sa up. 28 00:01:27,560 --> 00:01:29,560 Hayaan akong makuha ang mikropono dito para sa iyo. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Nice upang matugunan mo. 31 00:01:32,880 --> 00:01:34,005 >> Madla: Nice upang matugunan mo. 32 00:01:34,005 --> 00:01:36,790 Tagapagsalita: Lahat ng karapatan, kaya Mayroon akong dito asul Ang isang libro sa pamamagitan ng Z, 33 00:01:36,790 --> 00:01:41,680 at pupuntahan ko upang magpanggap na Mayroon akong isa sa mga mag-aaral, 34 00:01:41,680 --> 00:01:45,770 at sila nagmumula sa medyo random sa dulo ng isang tatlong oras na bloke pagsusulit, 35 00:01:45,770 --> 00:01:49,400 kaya sila ay nagtatapos up sa ilang mga semi-random na pagkakasunod-sunod na katulad nito. 36 00:01:49,400 --> 00:01:54,510 Ngayon ang iyong trabaho sa isang sandali lamang ay pagpunta upang be-- ito ay talagang kung paano sila makakuha ng 37 00:01:54,510 --> 00:01:56,820 Naka-in sa dulo ng ang klase, pinaka-malamang. 38 00:01:56,820 --> 00:02:01,120 Ang iyong trabaho ngayon ay magiging, medyo lamang, upang ayusin ang mga asul na mga libro para sa amin 39 00:02:01,120 --> 00:02:05,220 mula sa A sa pamamagitan Z. 40 00:02:05,220 --> 00:02:08,400 >> Madla: Oh, ito ay pagpunta sa tumagal magpakailanman. 41 00:02:08,400 --> 00:02:13,747 >> Tagapagsalita: At magkakaroon kami panoorin ginawa mo na ito, walang presyon. 42 00:02:13,747 --> 00:02:15,330 Madla: Hindi, walang presyon o kahit ano. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> Tagapagsalita: At para masaya, ni maglagay ng isang timer ipaalam. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> Madla: Kaya magkano masaya, kaya magkano masaya. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> Tagapagsalita: Maaari ko bang hawakan ang mic para sa iyo. 49 00:02:38,574 --> 00:02:40,240 Ang lahat ng mga karapatan, na lamang Dinoble namin ang aming bilis. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Kaya sa Pansamantala, hayaan mo akong magpose kayo kung ano ang pagpunta sa maging ang tanong para sa Mary Beth 52 00:02:49,060 --> 00:02:51,540 ay kung ano ang ginagawa niya, paano ay siya ng pagpunta tungkol sa paglutas ng mga ito? 53 00:02:51,540 --> 00:02:54,040 At sa katunayan, hindi mo maaaring mayroon kailanman naisip tungkol sa isang bagay 54 00:02:54,040 --> 00:02:57,440 kaya simpleng bilang kapag kinuha mo hanggang 26 mga aklat na tulad nito, 55 00:02:57,440 --> 00:02:59,350 na kung saan ay walang natural ng pag-order sa kanila. 56 00:02:59,350 --> 00:03:01,335 Ano ang proseso na iyong aktwal na gamitin? 57 00:03:01,335 --> 00:03:03,770 Ito ba ay medyo random na lamang pagpili ang unang isa na nakikita mo 58 00:03:03,770 --> 00:03:05,250 at paglalagay nito sa lugar nito? 59 00:03:05,250 --> 00:03:09,680 Huwag mong ilipat muna ang iyong mga kamay sa paligid naghahanap ng isang pagkatapos ay naghahanap para sa B? 60 00:03:09,680 --> 00:03:11,722 Umiinom ba ng isang pagtingin sa isang pares ng mga ito tabi-tabi 61 00:03:11,722 --> 00:03:14,680 at sabihin lamang, maghintay ng isang minuto, ito hindi tama, at pagkatapos magpalit ng order? 62 00:03:14,680 --> 00:03:16,960 Nakita namin na sa Lunes na mayroong isang bilang ng mga paraan 63 00:03:16,960 --> 00:03:22,140 kung saan maaari naming gawin ito, at sa katunayan bilang namin na malapit sa dulo dito, 64 00:03:22,140 --> 00:03:26,360 Gusto ko itala marahil ng kung ano ang Mary Beth ang ginagawa. 65 00:03:26,360 --> 00:03:30,040 Mayroon kaming ilang mga piles ito ay tila, isang mas malaking isa, tatlong mas maliit na mga bago. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> Madla: ako pag-order ng mga ito kapag nakahanap ako ng dalawang titik 68 00:03:36,415 --> 00:03:39,540 na kong malaman ay magkasama sa isang pagkakasunud-sunod, Ilagay ko ang mga ito nang sama-sama upang ang gagawin ko hindi 69 00:03:39,540 --> 00:03:42,915 kailangang mag-alala tungkol sa pagpapanatiling track ng isang buong hilera ng libro. 70 00:03:42,915 --> 00:03:45,706 Ito ay lamang, oh, A ay una, Mayroon akong na ito stack dito. 71 00:03:45,706 --> 00:03:47,580 Tagapagsalita: Kaya, halos tulad ng isang palaisipan piraso na 72 00:03:47,580 --> 00:03:49,860 ay may karapatan sa hugis tutugma sa isa't isa. 73 00:03:49,860 --> 00:03:51,026 Madla: Pretty magkano, Oo. 74 00:03:51,026 --> 00:03:55,320 Tagapagsalita: OK, mahusay. 75 00:03:55,320 --> 00:03:59,850 At ngayon bawat isa sa mga piles ay baka pinagsunod-sunod? 76 00:03:59,850 --> 00:04:00,990 >> Madla: Oo. 77 00:04:00,990 --> 00:04:09,900 >> Tagapagsalita: Lahat ng karapatan, A sa pamamagitan Z. Lahat karapatan, binabati kita, ginawa mo ito. 78 00:04:09,900 --> 00:04:11,461 Mayroon kang ang iyong pinili. 79 00:04:11,461 --> 00:04:11,960 Blue? 80 00:04:11,960 --> 00:04:13,530 Ang lahat ng mga karapatan, salamat sa iyo para sa na. 81 00:04:13,530 --> 00:04:16,679 Kaya Mary Beth ay ipanukala kung ano ang kanyang diskarte ay, 82 00:04:16,679 --> 00:04:19,720 ngunit kung ano ay isa pang diskarte kung paano mo Baka pumunta tungkol sa pagbubukod-bukod ng mga bagay na ito? 83 00:04:19,720 --> 00:04:21,130 Ano ang gusto mo pa? 84 00:04:21,130 --> 00:04:24,060 Ang tala upang talunin ang maaaring naging isang minuto at 50 o kaya mga segundo, 85 00:04:24,060 --> 00:04:26,039 kasama ang mga bago Nakalimutan ko ang upang mabilang. 86 00:04:26,039 --> 00:04:27,080 Ano ang gusto mo pa? 87 00:04:27,080 --> 00:04:27,579 Oo? 88 00:04:27,579 --> 00:04:28,735 Madla: Dumaan sa stack. 89 00:04:28,735 --> 00:04:29,776 Simulan mula sa simula. 90 00:04:29,776 --> 00:04:32,284 Suriin ang iyong mga papeles. 91 00:04:32,284 --> 00:04:36,586 At kung ang isa tuktok ay mas mataas kaysa, marahil, ang mga ito, 92 00:04:36,586 --> 00:04:38,980 ang isa ay ibaba mas mataas, pagkatapos ay lumipat sa kanila. 93 00:04:38,980 --> 00:04:41,300 >> Tagapagsalita: OK, kaya simula sa itaas at sa ibaba, 94 00:04:41,300 --> 00:04:43,716 at pagkatapos ay gumagana ang iyong paraan paloob tulad na, pagpapalit ang mga ito? 95 00:04:43,716 --> 00:04:46,580 OK, kaya ng kaunti katulad sa espiritu sa bubble-uuri, 96 00:04:46,580 --> 00:04:49,160 ngunit pagpili ng extremes hindi ang katabing mga pares. 97 00:04:49,160 --> 00:04:52,080 Subalit ang maikling ng ito ay mayroong tiyak ng grupo ng mga iba't-ibang paraan 98 00:04:52,080 --> 00:04:54,210 maaari naming gawin ito, at tapat, sa tingin ko sa iyo uri ng 99 00:04:54,210 --> 00:04:55,700 pinagtibay ng ilang approach na ito, tama? 100 00:04:55,700 --> 00:05:00,567 Nagsagawa ka ng isang uri ng apat na pinagsunod-sunod piles, at pagkatapos ay epektibo Pinagsama-sama ang mga ito. 101 00:05:00,567 --> 00:05:02,650 At iyon ang, daresay, isa pang diskarteng ito nang sama-sama. 102 00:05:02,650 --> 00:05:06,950 Hindi mo ituturing ito bilang isa malaki pile, hinati mo ang problema sa apat na quads, 103 00:05:06,950 --> 00:05:09,820 kung gagawin mo, at pagkatapos ay kahit papaano Pinag-isa ang mga ito sa dulo. 104 00:05:09,820 --> 00:05:13,410 >> Kaya Isaalang-alang natin, sa huli ipaalam, paano pa namin maaaring gawin ito. 105 00:05:13,410 --> 00:05:15,860 Formalized namin ang paniwala ng bubble-uuri huling oras, 106 00:05:15,860 --> 00:05:18,780 at bubble uri pagpapabalik ng algorithm na namin makita 107 00:05:18,780 --> 00:05:22,640 may walong ng iyong mga kaklase up dito, tila random na pinagsunod-sunod sa unang. 108 00:05:22,640 --> 00:05:26,110 At pagkatapos ay nagpasya kaming pairwise, kung ang dalawang mga elemento ay sira, 109 00:05:26,110 --> 00:05:26,950 magpalit lang ang mga ito. 110 00:05:26,950 --> 00:05:28,930 Kaya apat at dalawa malinaw naman out sa pagkakasunud-sunod, 111 00:05:28,930 --> 00:05:31,080 kaya dalawang kaklase mga nakalipat posisyon. 112 00:05:31,080 --> 00:05:35,390 At pagkatapos ay paulit-ulit namin na may apat at anim, pagkatapos ng anim at walong, sa bawat iteration, 113 00:05:35,390 --> 00:05:36,980 paglipat sa kanan. 114 00:05:36,980 --> 00:05:42,590 >> Kaya ibinigay na walong tao, kung gaano karaming mga pairwise paghahambing ginawa ko habang naglalakad mula sa 115 00:05:42,590 --> 00:05:45,220 ang natitira upang karapatan sa isa tulad iteration? 116 00:05:45,220 --> 00:05:48,410 Gaano karaming mga paghahambing? 117 00:05:48,410 --> 00:05:49,197 Pitong, tama? 118 00:05:49,197 --> 00:05:51,405 Dahil kung mayroong walong mga tao ngunit mayroon ka ng mga pares 119 00:05:51,405 --> 00:05:53,880 ang mga ito at mong mapanatili ang paglipat isa Hop sa kanan, 120 00:05:53,880 --> 00:05:56,060 Hindi ka pagpunta sa may walong paghahambing dahil hindi mo maaaring ihambing 121 00:05:56,060 --> 00:05:59,226 isang elemento laban sa sarili nito, o gagawin ito maging pointless lamang, kaya mayroon kang pitong. 122 00:05:59,226 --> 00:06:01,290 O mas pangkalahatang paraan, kung mayroon kaming n tao, namin 123 00:06:01,290 --> 00:06:04,300 gawin n minus 1 paghahambing may bubble-uuri. 124 00:06:04,300 --> 00:06:08,150 >> Kaya Isaalang-alang natin ngayon kung paano mahusay na ipaalam o masamang bubble uri talaga noon, at subukan 125 00:06:08,150 --> 00:06:13,570 upang bigyan ang ating mga sarili na may bokabularyo kung saan pumupuna algorithm na tulad nito, 126 00:06:13,570 --> 00:06:14,430 at sa lalong madaling panahon ang aming mga sarili. 127 00:06:14,430 --> 00:06:16,970 Kaya ang unang pass sa pamamagitan ng uri ng bubble, sa unang pagkakataon 128 00:06:16,970 --> 00:06:20,909 Lumakad ako mula kaliwa hanggang kanang sa buong yugto, kinuha sa akin n minus 1 paghahambing. 129 00:06:20,909 --> 00:06:22,950 At na pupuntahan maging ang aking yunit ng pagsukat, tama? 130 00:06:22,950 --> 00:06:26,170 Uri ng ako ay pakikipag-usap at strolling, medyo mabilis, medyo mabagal, 131 00:06:26,170 --> 00:06:29,300 kaya pagbibilang aking bilang ng mga segundo ay hindi partikular na nagsasabi, 132 00:06:29,300 --> 00:06:32,260 ngunit pagbibilang ang bilang ng mga mga operasyon na ginawa ko sa Monday, 133 00:06:32,260 --> 00:06:35,900 paghahambing ng dalawang tao, na sa palagay tulad ng isang masarap na unit ng pagsukat. 134 00:06:35,900 --> 00:06:40,980 >> Kaya n minus 1 hakbang sa unang pagkakataon, ngunit pagkatapos ay kung ano ang nangyari pagkatapos na? 135 00:06:40,980 --> 00:06:46,610 Ano ang isang bentahe ng isa pass sa pamamagitan ng isang kung hindi man ay unsorted listahan? 136 00:06:46,610 --> 00:06:49,840 Ano ang maaari mong sabihin sa akin ang tungkol sa mga elemento na naging ang lahat ng mga paraan na iyon? 137 00:06:49,840 --> 00:06:51,300 Oo? 138 00:06:51,300 --> 00:06:52,870 Iyon ay ang pinakamalaking elemento, tama? 139 00:06:52,870 --> 00:06:55,710 Numero ng walong, kahit na siya Nagsimula dito, sa tuwing ako 140 00:06:55,710 --> 00:06:57,860 kumpara laban sa kanya isang kapit-bahay, siya ay pinananatiling 141 00:06:57,860 --> 00:07:00,480 bubbling up sa kanan bahagi ng listahan. 142 00:07:00,480 --> 00:07:02,710 At sa katunayan, iyon ang kung saan ang algorithm ay makakakuha ng pangalan nito. 143 00:07:02,710 --> 00:07:07,630 >> Ngayon na sa pamamagitan ng logic, kung gaano karaming mga paghahambing kailangan gumawa ako sa ikalawang oras 144 00:07:07,630 --> 00:07:09,800 Gumawa ko na pass mula kaliwa hanggang kanang? 145 00:07:09,800 --> 00:07:10,730 n minus 2, i-right? 146 00:07:10,730 --> 00:07:14,297 Ito ay lamang ma-aksaya ang aking oras kung ako panatilihin ng paghahambing ng walong laban sa isang tao 147 00:07:14,297 --> 00:07:16,630 iba dahil alam namin siya ay nasa tamang lugar. 148 00:07:16,630 --> 00:07:19,760 Kaya na ang isang bit ng isang pag-optimize, kaya ang susunod na pass 149 00:07:19,760 --> 00:07:23,899 ay magiging plus n minus dalawang hakbang, kung saan n ay ang bilang ng mga tao. 150 00:07:23,899 --> 00:07:26,940 Ngayon ay maaari mong uri ng extrapolate, kahit kung ikaw ay hindi isang computer siyentipiko, 151 00:07:26,940 --> 00:07:27,680 paano nagtatapos ito. 152 00:07:27,680 --> 00:07:31,259 Sa dulo ng algorithm na ito, baka mayroon ka lamang isang paghahambing na natitira. 153 00:07:31,259 --> 00:07:33,800 Mayroon kang sa uri ng maayos ang simula ng listahan sa kasong dalawang 154 00:07:33,800 --> 00:07:36,540 at isa ay sira at dapat ay isa at dalawa, 155 00:07:36,540 --> 00:07:40,330 kaya ito bottoms out sa plus 1 panghuling paghahambing. 156 00:07:40,330 --> 00:07:44,500 >> Ngayon ang tuldok, tuldok, tuldok uri ng mga wave ito mga kamay sa ilan sa mga juicier mga detalye, 157 00:07:44,500 --> 00:07:46,452 ngunit hayaan pumunta ni lamang magpatuloy at pasimplehin. 158 00:07:46,452 --> 00:07:48,660 Kung isipin ang mo mula sa mataas paaralan, tapat, ng maraming mo 159 00:07:48,660 --> 00:07:50,340 Nagkaroon matematika mga aklat na nagkaroon ng medyo cheat sheet 160 00:07:50,340 --> 00:07:52,550 sa harap na pabalat o ang likurang pabalat na ipinakita sa iyo 161 00:07:52,550 --> 00:07:56,400 ano serye summations tulad ng ito sa huli idinagdag hanggang sa. 162 00:07:56,400 --> 00:07:59,600 Sa pangkalahatan kaso, kung mayroon kang isang variable tulad n, at sa katunayan ang isang ito, 163 00:07:59,600 --> 00:08:01,634 kung tiningnan mo ang iyong matematika aklat lumang paaralan, 164 00:08:01,634 --> 00:08:04,050 Gusto mong makita na ito talaga nagdadagdag ng hanggang sa halagang ito dito, 165 00:08:04,050 --> 00:08:07,970 n beses n minus 1 lahat ng hinati sa 2. 166 00:08:07,970 --> 00:08:11,172 Kaya para sa ngayon hayaan stipulate sa akin lamang ito ay totoo, kaya sa isang hakbang ng pananampalataya, 167 00:08:11,172 --> 00:08:12,880 na kung ano ito sums hanggang sa, at maaari naming 168 00:08:12,880 --> 00:08:14,341 patunayan na sa isang mas pangkalahatang mga kaso. 169 00:08:14,341 --> 00:08:15,590 Ngunit ng palawakin ito out na ngayon hayaan. 170 00:08:15,590 --> 00:08:19,920 Kaya ni-multiply ito out ipaalam, kaya na n nakalapat, minus n, ang lahat ng hinati sa 2. 171 00:08:19,920 --> 00:08:23,200 Iyon ay talagang n nakalapat, hinati sa 2, minus n paglipas ng 2, 172 00:08:23,200 --> 00:08:25,010 nang sa gayon ang lahat ay maganda at kawili-wiling. 173 00:08:25,010 --> 00:08:27,060 Ngunit ano ang mangyayari kung namin ngayon plug-in ng isang halaga? 174 00:08:27,060 --> 00:08:29,724 Ipagpalagay Hindi ko kinailangang walong mga tao, ngunit sinasabi ng isang milyon. 175 00:08:29,724 --> 00:08:31,890 At isang milyon dahil lang ito ay isang medyo malaking bilang, 176 00:08:31,890 --> 00:08:34,039 plug sa na at tingnan kung ano ang mangyayari ipaalam. 177 00:08:34,039 --> 00:08:39,039 Kaya kung plug ako ng isang milyon sa na formula Pupunta ako upang makakuha ng isang milyong nakalapat, 178 00:08:39,039 --> 00:08:42,868 hinati sa 2, na binawasan ng isang milyon, na hinati sa 2. 179 00:08:42,868 --> 00:08:44,159 Ngayon kung ano ang na pagpunta sa kasing-halaga? 180 00:08:44,159 --> 00:08:47,354 Kaya 500000000000, na binawasan ng 500,000. 181 00:08:47,354 --> 00:08:49,270 At kung ako aktwal na gawin na matematika out, paraan na 182 00:08:49,270 --> 00:08:53,920 na pag-uuri ng isang milyong mga taong may bubble-uuri 183 00:08:53,920 --> 00:09:01,800 Maaaring umabot sa akin 499999500000 hakbang o mga paghahambing sa dulo, 184 00:09:01,800 --> 00:09:02,900 lamang kami extrapolating. 185 00:09:02,900 --> 00:09:06,860 >> Na sa palagay medyo mabagal, ngunit tapat pagsukat ng isang partikular na pag-input 186 00:09:06,860 --> 00:09:09,160 tulad nito, ay hindi lahat na nagsasabi na iyon. 187 00:09:09,160 --> 00:09:14,050 Ngunit sa katunayan ito magmungkahi na ang bilang n ay makakakuha ng mas malaki at mas malaki, ito algorithm 188 00:09:14,050 --> 00:09:16,280 uri ng pakiramdam ng mas masahol pa at mas masahol pa, o mo ba talagang 189 00:09:16,280 --> 00:09:20,450 simulan sa pakiramdam ang sakit ng na exponentiation, na n nakalapat, 190 00:09:20,450 --> 00:09:21,770 na medyo mabilis nagdadagdag up. 191 00:09:21,770 --> 00:09:25,340 At detalye na ito ay hindi Nawala sa mga tao, sa katunayan 192 00:09:25,340 --> 00:09:29,640 ilang taon na ang nakakaraan ng isang tiyak na Senador na naging campaigning, SA down para sa isang pakikipanayam 193 00:09:29,640 --> 00:09:32,180 may Eric Google Schmidt, CEO sa oras, 194 00:09:32,180 --> 00:09:36,380 at ay hinamon sa isang tanong halos tulad kami ng paggalugad ngayon. 195 00:09:36,380 --> 00:09:38,468 Tingnan natin ang isang hitsura. 196 00:09:38,468 --> 00:09:45,280 >> [VIDEO pag-playback] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Handa ka dito sa Google, at gusto ko 198 00:09:48,560 --> 00:09:53,382 mag-isip ng pagkapangulo bilang isang interbyu sa trabaho. 199 00:09:53,382 --> 00:09:56,434 Ngayon, mahirap upang makakuha ng ng trabaho bilang president, 200 00:09:56,434 --> 00:09:58,100 at tapos ka ng pagpunta sa pamamagitan ng mga kahirapan ngayon. 201 00:09:58,100 --> 00:10:01,860 Mahirap din upang makakuha ng trabaho sa Google. 202 00:10:01,860 --> 00:10:05,490 Mayroon kaming mga tanong, at kami hilingin sa aming mga tanong kandidato, 203 00:10:05,490 --> 00:10:09,770 at ang isang ito ay mula sa Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 What-- mo guys tingin ko Nagagalak kidding, ito ay dito mismo. 205 00:10:14,760 --> 00:10:17,930 Ano ang pinaka-mahusay na paraan upang pagbukud-bukurin isang milyong 32-bit integer? 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 Ng paumanhin, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> -No, Walang, hindi. 210 00:10:27,400 --> 00:10:30,700 Sa tingin ko ang bubble-uuri ay magiging sa maling paraan upang pumunta. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> -Come Sa, na sinabi sa kanya na ito? 213 00:10:38,180 --> 00:10:40,590 Hindi ko nakita ng computer agham sa iyong background. 214 00:10:40,590 --> 00:10:42,130 >> Nakakuha -We've aming spies sa doon. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Na magtanong sa isang iba't ibang hayaan tanong interbiyu. 217 00:10:48,444 --> 00:10:49,300 >> [END VIDEO pag-playback] 218 00:10:49,300 --> 00:10:52,290 >> Tagapagsalita: Kaya pinag-uusapan tungkol sa tukoy na mga numero bagaman, 219 00:10:52,290 --> 00:10:53,890 Hindi pupunta na maging lahat na kapaki-pakinabang. 220 00:10:53,890 --> 00:10:56,810 Hindi ito isang aralin buhay na bubble uri, bibigyan ng milyon input, 221 00:10:56,810 --> 00:10:58,590 maaaring tumagal ng maraming bilang 500,000,000,000 hakbang. 222 00:10:58,590 --> 00:11:01,120 Hindi mo maaaring talagang tuntuning panlahat Masyadong epektibo mula sa na 223 00:11:01,120 --> 00:11:03,560 at gumawa ng mabuting pasya sa disenyo kapag sumusulat ng mga programa. 224 00:11:03,560 --> 00:11:07,070 Kaya sabihin tumuon bagaman sa kung paano maaari naming gawing simple ang resultang ito. 225 00:11:07,070 --> 00:11:11,780 >> Kaya nai-highlight ko sa dilaw dito ang resulta ng n nakalapat na hinati sa 2, 226 00:11:11,780 --> 00:11:14,330 kaya isang milyong nakalapat hinati sa 2, at pagkatapos ay 227 00:11:14,330 --> 00:11:16,710 Nai-highlight ko kung ano ang ang tunay na sagot ay 228 00:11:16,710 --> 00:11:20,180 sa sandaling subtracted namin off n na hinati sa 2. 229 00:11:20,180 --> 00:11:24,850 At ang claim Pupunta ako sa gumawa ngayon ay, sino ang heck na pinahahalagahan mo kung ibawas off 230 00:11:24,850 --> 00:11:30,060 isang maliit na gulang n sa 2 kapag ang unang bahagi ng formula na ito ay kaya magkano ang mas malaki? 231 00:11:30,060 --> 00:11:33,910 Dominates nito ang iba pang mga na termino, n nakalapat na hinati sa 2 232 00:11:33,910 --> 00:11:37,510 ay kaya magkano ang mas malaki, malinaw, bilang n ay makakakuha ng malaking tulad ng isang milyon, 233 00:11:37,510 --> 00:11:41,450 na mayroong talagang isang malaking pagkakaiba sa ang pagtatapos ng araw sa pagitan ng 500000000000 234 00:11:41,450 --> 00:11:45,730 at 499999500000? 235 00:11:45,730 --> 00:11:46,349 Hindi talaga. 236 00:11:46,349 --> 00:11:48,640 At kaya kung ano ang namin ang pagpunta sa gawin bilang mga siyentipiko computer ay 237 00:11:48,640 --> 00:11:53,270 huwag pansinin ang mga mas mababang mga tuntunin ng order at kumuha ng isang bagay na tulad nito at talaga 238 00:11:53,270 --> 00:11:56,050 gawing simple lamang ito sa taning na pupuntahan mahalaga. 239 00:11:56,050 --> 00:12:00,315 Ang mas malaki ang aming hanay ng data makakuha ng, ang mas malaking aming database makakuha ng, ang higit pang mga pahina ng web 240 00:12:00,315 --> 00:12:02,690 mayroon kaming upang maghanap, ang higit pa mga kaibigan na mayroon ka sa Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Bilang n nakakakuha ng mas malaki, hindi namin talaga pagpunta sa nagmamalasakit sa pinakamalaking 242 00:12:07,340 --> 00:12:11,560 termino sa anumang naturang pag-aaral ng ang aming mga algorithm pagganap. 243 00:12:11,560 --> 00:12:16,230 At pupuntahan ko sabihin, alam mo kung ano ang, bubble uri ay sa pagkakasunud-sunod ng malaking O, 244 00:12:16,230 --> 00:12:18,060 sa pagkakasunud-sunod ng n nakalapat. 245 00:12:18,060 --> 00:12:20,090 Ito ay hindi eksakto n nakalapat bilang nasaksihan namin, 246 00:12:20,090 --> 00:12:22,060 ngunit sino ba talagang pinahahalagahan tungkol sa mga mas maliit na mga termino, 247 00:12:22,060 --> 00:12:24,390 at tapat, na talagang pinahahalagahan ng kung hinati namin sa pamamagitan ng 2? 248 00:12:24,390 --> 00:12:25,870 Ito lamang ay isang pare-pareho factor. 249 00:12:25,870 --> 00:12:29,480 At 500000000000 kumpara sa 250 bilyon talaga na malaki ng isang deal? 250 00:12:29,480 --> 00:12:32,190 Maaari ko lang maghintay ng isang taon, hayaan ang aking laptop na literal 251 00:12:32,190 --> 00:12:34,810 makakuha ng dalawang beses nang mas mabilis sa hardware, at na uri ng mga pagkakaiba 252 00:12:34,810 --> 00:12:36,650 natural lang napupunta ang layo sa paglipas ng panahon. 253 00:12:36,650 --> 00:12:39,300 >> Ano pinapahalagahan namin tungkol ay ang expression, ang bahagi 254 00:12:39,300 --> 00:12:42,489 ng mga expression na pupuntahan mag-iba bilang aming input ay nakakakuha ng mas malaki at mas malalaking. 255 00:12:42,489 --> 00:12:45,280 At sa katunayan, sa tunay na mundo, na kung ano ang nangyayari lalong 256 00:12:45,280 --> 00:12:48,330 ay ang input sa aming mga problema at algorithm ay nakakakuha ng mas malaki. 257 00:12:48,330 --> 00:12:53,470 Kaya malaki O ay magiging ang pagtatanda, ang asymptotic pagtatanda, na namin lamang 258 00:12:53,470 --> 00:12:57,160 gamitin bilang mga siyentipiko computer upang ilarawan ang pagganap, o mga oras sa pagtakbo, 259 00:12:57,160 --> 00:12:58,130 ng isang algorithm. 260 00:12:58,130 --> 00:13:00,800 Upang maaari naming ihambing ang mga algorithm sa iba't ibang mga computer nakasulat 261 00:13:00,800 --> 00:13:04,170 sa pamamagitan ng iba't ibang mga tao, sa pamamagitan ng paggamit ilang fundamentally katulad na sukatan 262 00:13:04,170 --> 00:13:07,557 tulad ng bilang ng mga paghahambing ikaw ay paggawa, o marahil ang bilang ng mga swaps 263 00:13:07,557 --> 00:13:08,140 nagsasagawa ka ng. 264 00:13:08,140 --> 00:13:11,910 >> Ano ang hindi namin pagpunta sa count ay ang halaga ng oras 265 00:13:11,910 --> 00:13:13,981 na pumasa sa orasan sa pader karaniwang. 266 00:13:13,981 --> 00:13:16,230 Ano ang hindi namin pagpunta sa mag-alala tungkol ay kung magkano ang memorya 267 00:13:16,230 --> 00:13:17,820 gumagamit ka ngayon sa hindi bababa sa, bagaman na 268 00:13:17,820 --> 00:13:19,370 isa pang mapagkukunan na maaari naming sukatin. 269 00:13:19,370 --> 00:13:23,610 Kami ay pagpunta sa subukan upang ibabase ang aming pagsusuri sa lamang ang pangunahing mga pagpapatakbo, ang mga taong, 270 00:13:23,610 --> 00:13:25,930 tapat, na maaari mong makita ang pinaka-biswal. 271 00:13:25,930 --> 00:13:30,700 Kaya may isang bagay tulad ng malaking O ng n nakalapat, inaangkin ko na O ng n nakalapat 272 00:13:30,700 --> 00:13:35,820 ay isang pang-itaas bound sa tinatawag na oras ng paggana ng bubble-uuri. 273 00:13:35,820 --> 00:13:38,820 Sa ibang salita, kung ikaw Nais upang i-claim na mayroong 274 00:13:38,820 --> 00:13:41,370 ito mataas na limitasyon sa kung gaano karaming hakbang ay maaaring tumagal ng isang algorithm, 275 00:13:41,370 --> 00:13:46,240 itong ibang mapupuntahan na nasa malaking O ng n nakalapat sa kasong ito, isang pang-itaas nakatali. 276 00:13:46,240 --> 00:13:49,710 >> Paano kung ako sa halip baguhin ang kuwento na hindi tungkol sa bubble-uuri, 277 00:13:49,710 --> 00:13:50,910 ngunit tungkol sa itaas na hangganan. 278 00:13:50,910 --> 00:13:54,030 Maaari mong isipin ang isang algorithm na Tiningnan namin sa na 279 00:13:54,030 --> 00:13:59,530 na kung saan ang itaas na hangganan, maximum sukatin ng oras o mga pagpapatakbo, 280 00:13:59,530 --> 00:14:04,300 ay nagsabi na bounded sa pamamagitan ng n, isang linear function, 281 00:14:04,300 --> 00:14:07,260 hindi isang isa quadratic na Kurbadong? 282 00:14:07,260 --> 00:14:10,780 Ano ang isang algorithm na laging tumatagal ng hindi hihigit 283 00:14:10,780 --> 00:14:12,860 kaysa tulad ng n hakbang, o 2n mga hakbang, o mga hakbang 3n? 284 00:14:12,860 --> 00:14:13,360 Oo? 285 00:14:13,360 --> 00:14:15,030 >> Madla: Paghahanap ng mga pinakamalaking bilang sa isang listahan? 286 00:14:15,030 --> 00:14:16,930 >> Tagapagsalita: Ganap, paghahanap ang pinakamalaking bilang sa isang listahan. 287 00:14:16,930 --> 00:14:18,940 Kapag ako ay bibigyan ng isang listahan ng mga mga tao halimbawa, 288 00:14:18,940 --> 00:14:21,440 bawat isa sa kung sino ang humahawak ng isang numero, kung ano ang maximum na bilang 289 00:14:21,440 --> 00:14:23,770 ng hakbang na dapat itong tumagal sa akin, isang makatwirang matalinong tao, 290 00:14:23,770 --> 00:14:27,530 upang mahanap ang pinakamalaking tao sa listahang iyon? 291 00:14:27,530 --> 00:14:28,100 n, tama? 292 00:14:28,100 --> 00:14:31,320 Dahil sa ang pinakamasama kaso, kung saan ang ay maaaring ang pinakamalaking halaga? 293 00:14:31,320 --> 00:14:32,700 Mag-right, ang lahat ng mga paraan sa dulo. 294 00:14:32,700 --> 00:14:34,575 Kaya sa mga pinakamasama kaso upper bound, maaari ko 295 00:14:34,575 --> 00:14:36,450 kailangang pumunta lahat ng mga paraan sa paglipas dito at dapat tulad ng, 296 00:14:36,450 --> 00:14:39,170 oh, narito ang numero ng walong, o kahit anong halaga na hindi. 297 00:14:39,170 --> 00:14:41,330 Ngayon magiging hangal lamang kung iningatan ko pagpunta, i-right? 298 00:14:41,330 --> 00:14:43,840 Naghahanap ng higit pa at higit pang mga elemento kung ang huli sa kanila ay banda roon? 299 00:14:43,840 --> 00:14:45,340 Kaya tiyak, n ay isang pang-itaas nakatali. 300 00:14:45,340 --> 00:14:47,420 Hindi ko na kailangang gumawa ng higit pang hakbang kaysa iyon. 301 00:14:47,420 --> 00:14:51,580 >> Kaya kung ano kung sa halip ipinanukalang ko na may mga algorithm sa mundo na 302 00:14:51,580 --> 00:14:57,750 magkaroon ng oras tumatakbo na bounded sa pamamagitan ng malaking O ng log n, mag-log n? 303 00:14:57,750 --> 00:15:00,390 Saan nakita namin na ito bago? 304 00:15:00,390 --> 00:15:00,890 Oo? 305 00:15:00,890 --> 00:15:03,309 >> Madla: Sa problema phone book? 306 00:15:03,309 --> 00:15:04,850 Tagapagsalita: Tulad ng problema phone book. 307 00:15:04,850 --> 00:15:07,754 Ano ang sukatan ng kung gaano karaming oras o kung gaano karaming mga luha ito 308 00:15:07,754 --> 00:15:10,170 kinuha sa akin upang mahanap ang isang tao tulad ng Mike Smith sa aklat ng telepono? 309 00:15:10,170 --> 00:15:13,212 Inaangkin namin na ito ay log n, at kahit na hindi pamilyar o ito ito ay 310 00:15:13,212 --> 00:15:15,170 medyo hazy kung ano ang isang logarithm o exponent ay, 311 00:15:15,170 --> 00:15:17,650 tandaan lamang na ang log n sa pangkalahatan ay tumutukoy sa proseso, 312 00:15:17,650 --> 00:15:20,790 sa kasong ito, ng paghahati damit na yari sa kalahati muli, at muli, 313 00:15:20,790 --> 00:15:25,790 at muli, at muli, tulad na ito ay makakakuha ng mas maliit na tulad ng iyong ginagawa iyon. 314 00:15:25,790 --> 00:15:28,470 >> Kaya mag-log ng n tumutukoy, sigurado, sa halimbawa sa aklat ng telepono, 315 00:15:28,470 --> 00:15:32,662 sa binary paghahanap sa teorya, kung kailan namin Nagkaroon ng virtual na mga pinto sa board, 316 00:15:32,662 --> 00:15:34,370 o kapag Sean noon ay na naghahanap ng isang bagay. 317 00:15:34,370 --> 00:15:37,374 Kung gumamit siya ng binary paghahanap, mag-log n ay magiging sa itaas na hangganan sa kung magkano 318 00:15:37,374 --> 00:15:38,040 oras na tumatagal. 319 00:15:38,040 --> 00:15:44,027 Ngunit ang mga algorithm na ang bumangga sa Mag-log n ipinapalagay kung ano ang detalye ng key? 320 00:15:44,027 --> 00:15:45,360 Na ang listahan ay pinagsunod-sunod, i-right? 321 00:15:45,360 --> 00:15:47,789 Ang iyong algorithm ay mali kung iyong input ay hindi pinagsunod-sunod, 322 00:15:47,789 --> 00:15:49,830 at pa gumagamit ka ng isang bagay tulad ng binary paghahanap 323 00:15:49,830 --> 00:15:51,704 dahil maaari kang tumalon karapatan sa ibabaw ng elemento 324 00:15:51,704 --> 00:15:53,600 nang hindi napagtatanto ito ay sa katunayan doon. 325 00:15:53,600 --> 00:15:55,600 >> Ngayon kung ano ang maaaring sabihin nito, malaki O ng isa? 326 00:15:55,600 --> 00:15:59,117 Hindi ito nangangahulugan na ang iyong algorithm tumatagal ng isa at isa lamang hakbang, 327 00:15:59,117 --> 00:16:01,200 Nangangahulugan ito lamang tumatagal ng isang pare-pareho ang bilang ng mga hakbang. 328 00:16:01,200 --> 00:16:04,060 Siguro ito ay 1, marahil ito ay 10, marahil ito ay 1,000, 329 00:16:04,060 --> 00:16:07,750 ngunit ito ay hiwalay sa ang laki ng problema. 330 00:16:07,750 --> 00:16:10,850 Hindi mahalaga kung gaano kalaki n ay, isang pare-pareho ang oras algorithm 331 00:16:10,850 --> 00:16:12,747 laging tumatagal ang parehong bilang ng mga hakbang. 332 00:16:12,747 --> 00:16:15,080 Kaya kung ano ang maaaring maging isang algorithm nai-usapan natin ang tungkol sa o lamang 333 00:16:15,080 --> 00:16:20,418 intuitively na pagdating sa iyo na palaging tumatakbo sa tinatawag na pare-pareho ang oras? 334 00:16:20,418 --> 00:16:20,918 Oo? 335 00:16:20,918 --> 00:16:22,001 >> Madla: Magdagdag ng dalawang numero. 336 00:16:22,001 --> 00:16:25,320 Tagapagsalita: Magdagdag ng dalawang mga numero, 2 plus 2 ay katumbas ng 4, tapos na. 337 00:16:25,320 --> 00:16:27,227 Kaya na maaaring gumana, ano pa? 338 00:16:27,227 --> 00:16:28,560 Paano ang tungkol sa higit pang mga tunay na mundo, Oo? 339 00:16:28,560 --> 00:16:30,686 >> Madla: Paghahanap ng mga unang bagay sa isang listahan. 340 00:16:30,686 --> 00:16:32,810 Tagapagsalita: Paghahanap ng mga unang sangkap sa isang listahan, siguraduhin. 341 00:16:32,810 --> 00:16:34,540 Namin ang aktwal na pakikipag-usap tungkol sa array na, 342 00:16:34,540 --> 00:16:36,540 paano mo makukuha sa unang elemento sa isang array, 343 00:16:36,540 --> 00:16:40,465 hindi mahalaga kung gaano katagal ang array ay nasa C code? 344 00:16:40,465 --> 00:16:43,090 Gamitin mo lang tulad ng bracket zero pagtatanda, Bam, nandoon ka. 345 00:16:43,090 --> 00:16:46,120 At sa katunayan array, bilang isang bukod, suporta ng isang bagay na sa pangkalahatan ay kilala 346 00:16:46,120 --> 00:16:49,240 bilang random access, random access memorya, dahil maaari ka nang literal 347 00:16:49,240 --> 00:16:50,284 tumalon sa anumang isang lugar. 348 00:16:50,284 --> 00:16:52,700 Maaari naming gawin ito kahit na higit pa lamang maaari naming rewind sa linggo zero 349 00:16:52,700 --> 00:16:53,900 kapag ginawa namin sa simula. 350 00:16:53,900 --> 00:16:59,707 Magkano oras ay tumagal para sa sabihin block sa simula upang maisagawa? 351 00:16:59,707 --> 00:17:00,790 Pare-pareho lang ng oras, tama? 352 00:17:00,790 --> 00:17:03,960 Sabihing isang bagay, sabihin natin isang bagay, hindi mahalaga 353 00:17:03,960 --> 00:17:07,359 kung gaano kalaki ang mga gasgas mundo ay, ito ay palaging pagpunta sa gawin ang parehong dami ng oras 354 00:17:07,359 --> 00:17:08,490 upang sabihin lamang ng isang bagay. 355 00:17:08,490 --> 00:17:11,089 >> Kaya na pare-pareho ang oras, ngunit ano ang flip side? 356 00:17:11,089 --> 00:17:13,030 Kung na-itaas hangganan, paano kung gusto naming 357 00:17:13,030 --> 00:17:17,089 upang ilarawan ang mas mababang mga hangganan ng aming mga algorithm sa pagtakbo ang oras? 358 00:17:17,089 --> 00:17:19,852 Halos isang pinakamahusay na kaso potensyal na, kung gagawin mo, 359 00:17:19,852 --> 00:17:23,060 bagaman ang mga terminong ito maaaring ilapat sa mga pinakamahusay na kaso, pinakamasama kaso, average na mga kaso nang higit pa 360 00:17:23,060 --> 00:17:26,359 Sa pangkalahatan, ngunit hayaan ang pagtuon ni lamang sa mas mababang hangganan sa mas pangkalahatang paraan. 361 00:17:26,359 --> 00:17:31,920 Ano ang isang algorithm na iyon ay mayroon isang mas mababang bound ng n hakbang, 362 00:17:31,920 --> 00:17:33,350 o 2n mga hakbang, o mga hakbang 3n? 363 00:17:33,350 --> 00:17:36,241 Ang ilang mga salik ng n hakbang, na mas mababa ang hangganan. 364 00:17:36,241 --> 00:17:36,740 Oo? 365 00:17:36,740 --> 00:17:37,910 >> Madla: Bubble-uri-uriin? 366 00:17:37,910 --> 00:17:41,610 >> Tagapagsalita: Bubble-uri-uriin tumatagal Nagnais mo n hakbang na ito, bakit? 367 00:17:41,610 --> 00:17:42,279 Bakit na? 368 00:17:42,279 --> 00:17:45,320 Bakit dapat na pagsisimula darating sa iyo intuitively, kahit na ito ay hindi lamang 369 00:17:45,320 --> 00:17:46,530 pa? 370 00:17:46,530 --> 00:17:47,030 Oo? 371 00:17:47,030 --> 00:17:47,990 >> Madla: [INAUDIBLE]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 Tagapagsalita: Mismong. 374 00:17:52,360 --> 00:17:55,810 Sa pinakamahusay na posibleng mga sitwasyon ng uri ng bubble, at maraming mga algorithm, 375 00:17:55,810 --> 00:17:58,769 kung ipasa ko sa inyo walong tao na na pinagsunod-sunod, 376 00:17:58,769 --> 00:18:00,560 magiging hangal para sa iyo, ang algorithm, 377 00:18:00,560 --> 00:18:02,202 upang bumalik-balik higit sa isang beses, tama? 378 00:18:02,202 --> 00:18:04,285 Dahil sa lalong madaling mo maglakad sa pamamagitan ng mga listahan nang isang beses, 379 00:18:04,285 --> 00:18:08,090 dapat mong mapagtanto, oh, ginawa ko walang swaps, list na ito ay pinagsunod-sunod, lumabas. 380 00:18:08,090 --> 00:18:09,700 Ngunit na pupuntahan magdadala sa iyo n hakbang. 381 00:18:09,700 --> 00:18:12,033 >> At kabaligtaran, kung ano ang isa pang paraan ng pag-iisip tungkol dito? 382 00:18:12,033 --> 00:18:15,240 Bubble-uri-uriin ay isang wakas, kaya upang makipag-usap, ng n, 383 00:18:15,240 --> 00:18:19,050 dahil kung tiningnan mo ang mas kaunti sa n elemento, kung ano 384 00:18:19,050 --> 00:18:23,009 ay ang pangunahing mga isyu doon? 385 00:18:23,009 --> 00:18:24,550 Hindi mo alam kung ito ay pinagsunod-sunod, i-right. 386 00:18:24,550 --> 00:18:26,800 Mga tao namin na maaaring sulyap sa walong mga tao at maging tulad ng, oh, ito ay pinagsunod-sunod, 387 00:18:26,800 --> 00:18:28,430 na hindi dalhin ako n hakbang na ito, ngunit ito ginawa. 388 00:18:28,430 --> 00:18:30,810 Ang iyong mga mata, kahit na na-uri ng may malaking field ng paningin, 389 00:18:30,810 --> 00:18:33,184 ikaw ay tumingin sa walong mga elemento, ikaw ay tumingin sa walong mga tao, 390 00:18:33,184 --> 00:18:34,610 na walong hakbang na ito nang epektibo. 391 00:18:34,610 --> 00:18:38,612 At lamang kung lumakad ako sa pamamagitan ng buong listahan gawin Napag-alaman kong, oo, pinagsunod-sunod. 392 00:18:38,612 --> 00:18:41,320 Kung ihihinto ko kalahatian pag-iisip, ang lahat karapatan, kaakit-akit na ito ay pinagsunod-sunod sa ngayon, 393 00:18:41,320 --> 00:18:42,520 kung ano ang mga logro hindi ito pinagsunod-sunod? 394 00:18:42,520 --> 00:18:44,186 Na algorithm hindi magiging tama. 395 00:18:44,186 --> 00:18:46,250 Maaaring maging mas mabilis, ngunit hindi tama. 396 00:18:46,250 --> 00:18:48,500 >> Kaya ngayon ay mayroon kaming isang paraan ng na naglalarawan ng isang mas mababang hangganan, 397 00:18:48,500 --> 00:18:49,710 at kung ano ang tungkol sa pare-pareho ang oras? 398 00:18:49,710 --> 00:18:54,565 Ano ang isang algorithm na may mas mababang nakatali sa running time nito sa isa? 399 00:18:54,565 --> 00:18:58,350 1 na hakbang, 2 hakbang, 10 mga hakbang, pero pare-pareho, independiyenteng ng n, 400 00:18:58,350 --> 00:18:59,310 ang laki ng input? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Oo, sa likod. 403 00:19:04,600 --> 00:19:05,309 >> Madla: Printf? 404 00:19:05,309 --> 00:19:06,183 Tagapagsalita: Ano iyon? 405 00:19:06,183 --> 00:19:07,184 Madla: Printf? 406 00:19:07,184 --> 00:19:07,850 Tagapagsalita: Printf. 407 00:19:07,850 --> 00:19:08,400 OK, sigurado. 408 00:19:08,400 --> 00:19:10,720 Kaya gumugugol ito ng nakapirming bilang ng mga hakbang. 409 00:19:10,720 --> 00:19:13,170 At ang dapat kong now-- ngayon na kami ay pakikipag-usap tungkol sa C code 410 00:19:13,170 --> 00:19:16,040 at hindi sa simula, isang bagay tulad ng sabihin nating, na may printf, 411 00:19:16,040 --> 00:19:17,710 dapat namin simulan upang makakuha ng maingat. 412 00:19:17,710 --> 00:19:21,090 Dahil printf aabutin input, ito ay isang string, 413 00:19:21,090 --> 00:19:23,220 at mga string ay technically mayroon haba. 414 00:19:23,220 --> 00:19:25,530 Kaya kung nais namin ngayon upang pumili sa iyo, kung ikaw ay hindi bale na gawin, 415 00:19:25,530 --> 00:19:29,430 technically na maaari kaming argue na printf aabutin ng isang variable na haba ng pag-input, 416 00:19:29,430 --> 00:19:32,270 at tiyak na maaaring tumagal ito nang higit pa oras upang i-print ang isang string na ito ang haba, 417 00:19:32,270 --> 00:19:33,560 kaysa ito mahaba. 418 00:19:33,560 --> 00:19:36,570 >> Kaya kung ano kung isinasaalang-alang namin lamang ang pag-uuri at paghahanap ng mga halimbawa? 419 00:19:36,570 --> 00:19:40,450 Paano ang tungkol sa Mike Smith sa telepono aklat, o binary paghahanap sa mas pangkalahatang? 420 00:19:40,450 --> 00:19:42,220 Sa pinakamahusay na kaso, kung ano ang maaaring mangyari? 421 00:19:42,220 --> 00:19:45,577 Buksan ko ang phone book at, Bam, mayroong Mike Smith numero. 422 00:19:45,577 --> 00:19:46,660 Maaari ko sa kanya tumawag agad-agad. 423 00:19:46,660 --> 00:19:49,390 >> Kinuha isang hakbang, siguro dalawang hakbang, ngunit isang pare-pareho ang bilang ng mga hakbang 424 00:19:49,390 --> 00:19:50,230 kung Nakatanggap ako masuwerteng. 425 00:19:50,230 --> 00:19:52,570 At tapat, nakita namin sa Lunes iyong kaklase 426 00:19:52,570 --> 00:19:54,710 makakuha ng masyadong masuwerteng dalawang beses sa isang hilera. 427 00:19:54,710 --> 00:19:57,050 At iyon ay sa katunayan pare-pareho oras sa isang mas mababang hangganan 428 00:19:57,050 --> 00:20:01,280 sa algorithm na pinag-uusapan para sa paghahanap ng ang bilang 50 sa likod ng mga sarado 429 00:20:01,280 --> 00:20:01,830 pintuan. 430 00:20:01,830 --> 00:20:06,400 >> Ngayon, bilang isang bukod, kung matuklasan mo na parehong malaki O, sa itaas na hangganan, 431 00:20:06,400 --> 00:20:09,310 at wakas, ang mas mababang nakatali, ay isa sa parehong, na 432 00:20:09,310 --> 00:20:11,830 ay ang parehong formula sa panaklong, maaari ring mo 433 00:20:11,830 --> 00:20:15,170 sabihin, upang maging fancy lamang, na may isang bagay ay nasa theta 434 00:20:15,170 --> 00:20:18,270 ng n o theta ng ilang iba pang mga halaga. 435 00:20:18,270 --> 00:20:20,661 Iyon ay nangangahulugan lamang kapag malaki Oh at wakas ay pareho. 436 00:20:20,661 --> 00:20:21,910 Kung ano ang tungkol sa uri seleksyon ngayon? 437 00:20:21,910 --> 00:20:23,400 Gumamit ng bagong bokabularyo Hayaan. 438 00:20:23,400 --> 00:20:27,407 Sa uri seleksyon, ano ang mga namin paggawa muli, at muli, at muli? 439 00:20:27,407 --> 00:20:29,990 Ako ay pagpunta pabalik-balik sa pamamagitan ng sa listahan, naghahanap ng kanino? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Ang pinakamaliit na numero. 442 00:20:34,730 --> 00:20:37,560 >> Kaya kung gaano karaming mga hakbang na ito, kung paano maraming mga paghahambing ng ginawa ko 443 00:20:37,560 --> 00:20:43,250 mayroon upang gawing upang malaman kung sino ang pinakamaliit na elemento sa listahan ay? 444 00:20:43,250 --> 00:20:44,437 n minus 1, tama? 445 00:20:44,437 --> 00:20:47,770 Dahil kung magsimulang lang ako sa isa ako given at ako magsisimulang paghahambing sa kanya, 446 00:20:47,770 --> 00:20:49,519 pagkatapos ay sa kanya, siya o ang kanyang, kanya, ako 447 00:20:49,519 --> 00:20:52,010 Maaari lamang ipares ang mga elemento magkasama n minus 1 beses. 448 00:20:52,010 --> 00:20:55,630 Kaya uri kaparehong tumatagal seleksyon n minus 1 hakbang sa unang pagkakataon. 449 00:20:55,630 --> 00:20:59,540 >> Ilang hakbang na ito ay tumagal sa akin upang hanapin ang pangalawang pinakamaliliit na elemento? 450 00:20:59,540 --> 00:21:02,920 n minus 2, dahil ako sa pagiging pipi kung ako patuloy na pagtingin sa parehong mga tao 451 00:21:02,920 --> 00:21:06,280 muli kung ang napili na ako sa kanya o ang kanyang at ilagay ang mga ito sa kanilang lugar. 452 00:21:06,280 --> 00:21:09,270 At ang ikatlong hakbang, n minus 3, pagkatapos n minus 4. 453 00:21:09,270 --> 00:21:11,020 Nakakita kami ang pattern na ito bago, at sa katunayan 454 00:21:11,020 --> 00:21:13,460 pagpili ng uri kaparehong May isang pang-itaas nakatali 455 00:21:13,460 --> 00:21:16,210 ng n nakalapat kung gagawin up namin na kabuuan. 456 00:21:16,210 --> 00:21:19,790 Ano ang kanyang mas mababang nakatali, uri seleksyon? 457 00:21:19,790 --> 00:21:25,350 Nagnais, kung magkano ang seleksyon kailangang oras uri tumagal, gaya ng nilinaw namin ito sa Lunes? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Ipanukala dalawang pagpipilian. 460 00:21:30,490 --> 00:21:32,360 Siguro ito ay n, tulad ng dati. 461 00:21:32,360 --> 00:21:35,040 Siguro ito n nakalapat, pati na ito na ngayon ang bilang sa itaas na hangganan. 462 00:21:35,040 --> 00:21:35,874 >> Madla: n nakalapat. 463 00:21:35,874 --> 00:21:36,664 Tagapagsalita: n nakalapat. 464 00:21:36,664 --> 00:21:37,368 Bakit? 465 00:21:37,368 --> 00:21:40,060 >> Madla: Dahil mayroon kang upang tukuyin ang [INAUDIBLE]. 466 00:21:40,060 --> 00:21:41,510 >> Tagapagsalita: Mismong. 467 00:21:41,510 --> 00:21:45,077 Hindi bababa sa gaya ng nilinaw ko maisasa-ayos seleksyon ito ay medyo walang muwang, panatilihin ang pagpunta, 468 00:21:45,077 --> 00:21:46,160 hanapin ang pinakamaliit na elemento. 469 00:21:46,160 --> 00:21:47,770 Pumunta muli, hanapin ang pinakamaliit na elemento. 470 00:21:47,770 --> 00:21:49,490 Pumunta muli, hanapin ang pinakamaliit na elemento. 471 00:21:49,490 --> 00:21:51,700 Walang uri ng sa pag-optimize sa doon na 472 00:21:51,700 --> 00:21:54,350 maaaring ipaalam sa akin i-abort matapos hakbang lamang n o kaya. 473 00:21:54,350 --> 00:21:57,080 Kaya nga, seleksyon -uri-uriin, wakas ng n nakalapat. 474 00:21:57,080 --> 00:22:00,667 >> Paano ang tungkol sa uri ng pagpapasok ng, kung saan kinuha ko na ako ay ibinigay, at pagkatapos ay plopped ko sa kanya 475 00:22:00,667 --> 00:22:01,750 o ang kanyang sa tamang lugar? 476 00:22:01,750 --> 00:22:04,958 Pagkatapos ay nagpatuloy ako sa ikalawang tao, plopped kanya sa tamang lugar. 477 00:22:04,958 --> 00:22:07,910 Pagkatapos ng susunod na tao, plopped sa kanya sa tamang lugar. 478 00:22:07,910 --> 00:22:10,537 Pansinin na ito ay napaka linear, kaya upang makipag-usap. 479 00:22:10,537 --> 00:22:12,620 Ako ay isang tuwid na linya, ako hindi pagpunta pabalik-balik, 480 00:22:12,620 --> 00:22:16,080 Hindi pa ko naghahanap bumalik talaga ito, ngunit kung ano ang nangyayari kapag ipasok ko sa kanya 481 00:22:16,080 --> 00:22:20,302 o ang kanyang sa simula ng ang listahan tulad ng ginawa namin sa Lunes? 482 00:22:20,302 --> 00:22:21,010 Anong nangyayari? 483 00:22:21,010 --> 00:22:21,510 Oo? 484 00:22:21,510 --> 00:22:23,122 Madla: [INAUDIBLE]. 485 00:22:23,122 --> 00:22:24,830 Tagapagsalita: Oo, na ay ang catch, tama? 486 00:22:24,830 --> 00:22:26,746 Maaari mong isipin ang mula sa ang iyong mga kamag-aral, kung ang mga ito 487 00:22:26,746 --> 00:22:29,670 ay ang pagsasagawa ng anumang pagkilos sa ang kanilang mga paa, na noon ay isang operasyon. 488 00:22:29,670 --> 00:22:33,610 Kaya kung mayroong tatlong mga tao dito at ang bagong tao aari paraan banda roon, 489 00:22:33,610 --> 00:22:37,360 sa isang mahabang yugto tulad nito, sigurado, siya o maaaring siya pumunta lamang sa dulo napaka. 490 00:22:37,360 --> 00:22:40,074 Ngunit kung pinag-iisipan mo kami tungkol sa isang computer at isang array ng memorya, 491 00:22:40,074 --> 00:22:41,990 ang mga taong ito ay pumunta sa upang i-shuffle sa ibabaw 492 00:22:41,990 --> 00:22:43,260 para gumawa nang lugar para sa taong iyon. 493 00:22:43,260 --> 00:22:46,930 At nang sa gayon ay n minus 1 shufflings, n minus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 minus 3 shufflings lamang ang uri ng nangyayari sa likod ng akin, hindi sa harap ng akin 495 00:22:50,660 --> 00:22:52,710 tulad ng dati, sa ilang mga kahulugan. 499 00:22:52,557 --> 00:22:54,640 Ngayon bilang isang bukod, at bilang maaaring nakakita ka online 500 00:22:54,640 --> 00:22:57,699 kung nagsimula ka ng poking sa paligid tungkol sa mga uri, mayroong kaya maraming iba't ibang mga bago 501 00:22:57,699 --> 00:22:59,490 Nariyan lang, ang ilan sa kanila mas mahusay kaysa sa iba. 502 00:22:59,490 --> 00:23:02,200 Sa katunayan, bogosort ay isa na uri ng masaya upang tumingin hanggang. 503 00:23:02,200 --> 00:23:06,650 Bogosort tumatagal ng isang hanay ng mga numero o sinasabi ng isang deck ng mga baraha, 504 00:23:06,650 --> 00:23:09,870 random shuffles sa kanila, at mga tseke kung ang mga ito ay pinagsunod-sunod. 505 00:23:09,870 --> 00:23:12,130 At kung hindi, ginagawa itong muli. 506 00:23:12,130 --> 00:23:14,140 At kung hindi, ginagawa itong muli. 507 00:23:14,140 --> 00:23:15,440 Kung hindi, ginagawa itong muli. 508 00:23:15,440 --> 00:23:17,060 Hindi kapani-paniwalang hangal. 509 00:23:17,060 --> 00:23:19,520 >> At sa katunayan, kung basahin mo tulad ng mga artikulo sa Wikipedia, 510 00:23:19,520 --> 00:23:21,200 palayaw nito ay hangal uri. 511 00:23:21,200 --> 00:23:25,180 Ito ay malaon gumana, sana ay, na ibinigay ng sapat na panahon, 512 00:23:25,180 --> 00:23:28,240 ngunit na dami ng oras Maaaring magtagal pa masyadong ilang panahon. 513 00:23:28,240 --> 00:23:31,650 Kaya kung kaya kong, sabihin bilis bagay up mula sa halimbawa ni Maria Beth ng mas maaga, 514 00:23:31,650 --> 00:23:35,150 sa pamamagitan ng pagkakaroon ng ilang higit pang mga elemento, ngunit dalawang higit pang mga processors. 515 00:23:35,150 --> 00:23:37,100 Dalawang mga tao, kung ikaw hindi bale na sumali sa akin. 516 00:23:37,100 --> 00:23:40,972 Paano ang tungkol sa 1 sa ibabaw dito, at go-- ni walang sinuman banda roon ipaalam? 517 00:23:40,972 --> 00:23:41,722 Walang isa na iyon? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 Ikaw na may itim shirt, oo, dumating pababa. 520 00:23:44,190 --> 00:23:45,000 Ang lahat ng mga karapatan, kung ano ang iyong pangalan? 521 00:23:45,000 --> 00:23:45,720 >> Madla: Peter. 522 00:23:45,720 --> 00:23:46,100 >> Tagapagsalita: Ano iyon? 523 00:23:46,100 --> 00:23:46,766 >> Madla: Peter. 524 00:23:46,766 --> 00:23:49,450 Tagapagsalita: Pedro, David, mabait sa matugunan mo. 525 00:23:49,450 --> 00:23:53,670 Ang lahat ng mga karapatan, mayroon kaming Peter dito, kung ikaw nais na dumating sa talahanayan sa paglipas dito. 526 00:23:53,670 --> 00:23:54,550 At kung ano ang iyong pangalan? 527 00:23:54,550 --> 00:23:55,216 >> Madla: Elena. 528 00:23:55,216 --> 00:23:55,970 Tagapagsalita: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, mabait sa matugunan mo. 530 00:23:57,030 --> 00:23:58,060 Elena matugunan Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 At kailangan nating Andrew up dito pati na rin, pakiusap. 533 00:24:02,290 --> 00:24:06,107 At ang iyong mga hamon ay pagpunta upang maging upang pagbukud-bukurin ang isang deck ng mga baraha. 534 00:24:06,107 --> 00:24:08,190 At kung hindi pamilyar, deck ng mga baraha dapat sa huli 535 00:24:08,190 --> 00:24:11,064 ay pinagsunod-sunod ng kaunti ng isang bagay tulad ng na ito kung saan kami na ang mga club, pagkatapos ay 536 00:24:11,064 --> 00:24:13,660 ang spades, pagkatapos ay ang puso at diamante, mula sa ACE bilang isa, 537 00:24:13,660 --> 00:24:15,570 ang lahat ng mga paraan ng hanggang sa hari. 538 00:24:15,570 --> 00:24:20,890 >> Ang mga kard Pupunta ako sa magbibigay sa iyo ng ay magiging 52 sa dami. 539 00:24:20,890 --> 00:24:23,160 Kami ay pagpunta sa kaparehong oras ka, sa sandali lamang. 540 00:24:23,160 --> 00:24:26,410 Kami ay pagpunta sa magtapon ng Andrew hanggang sa screen dito, 541 00:24:26,410 --> 00:24:28,170 kaya bilang upang panoorin bilang gawin mo ito. 542 00:24:28,170 --> 00:24:31,070 At upang ang lahat ng ito ay ang lahat ng mga mas nakikita, 543 00:24:31,070 --> 00:24:33,490 ang mga ito ay ang mga card Nakatanggap ako sa Amazon. 544 00:24:33,490 --> 00:24:42,861 Kaya ang mga ito ay mayroon nang sapalaran pinagsunod-sunod, at kami ay pagpunta sa minsan sa iyo. 545 00:24:42,861 --> 00:24:44,610 At kami ay pagpunta sa panatilihin itong real time na ito, 546 00:24:44,610 --> 00:24:47,820 kaya kami ay pagpunta upang subukang i-presyon ka dahil kung hindi man ito ay makakakuha nakakainip 547 00:24:47,820 --> 00:24:48,460 mabilis. 548 00:24:48,460 --> 00:24:53,860 Kung maaari kang magpatuloy upang pagbukud-bukurin 52 mga elemento nang magkasama sa pamamagitan ng ilang mga paraan, na ngayon. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> At muli, habang pinapanood namin ang mga guys kung ano, gawin sa dulo 551 00:25:07,180 --> 00:25:10,200 Mawawala na upang makabuo ng isang halata resulta, isipin ang tungkol talaga 552 00:25:10,200 --> 00:25:12,962 kung paano sila bawat paggawa nito, kung paano maaari mong ilarawan ito. 553 00:25:12,962 --> 00:25:15,045 Dahil muli, ang mga ito ay lahat ng mga proseso, mga algorithm 554 00:25:15,045 --> 00:25:17,090 na lubos naming para sa ipinagkaloob bilang isang tao. 555 00:25:17,090 --> 00:25:22,349 Ngunit mo na marahil ay nagkaroon mahaba Swersey, katagal bago mo kahit na 556 00:25:22,349 --> 00:25:24,390 naisip tungkol sa pagkuha ng isang computer science klase mo 557 00:25:24,390 --> 00:25:27,223 Maaaring nagkaroon ang Swersey na may na lutasin ang mga problema tulad nito. 558 00:25:27,223 --> 00:25:29,560 Ngunit sa sandaling makilala ka ang mga pattern at simulan 559 00:25:29,560 --> 00:25:32,407 upang gawing pormal ang mga hakbang kung saan naka-solve ang mga problemang ito, 560 00:25:32,407 --> 00:25:35,490 makikita mo na maaari mong malutas magkano higit pa kawili-wili at marami pang iba complex 561 00:25:35,490 --> 00:25:39,190 mga problema nang mabilis. 562 00:25:39,190 --> 00:25:42,351 Kaya ang isang tao mula sa madla, kung ano ang hindi bababa sa isang elemento ng algorithm 563 00:25:42,351 --> 00:25:43,350 na ginagamit nila dito? 564 00:25:43,350 --> 00:25:44,275 >> Madla: [INAUDIBLE] 565 00:25:44,275 --> 00:25:45,150 Tagapagsalita: Ano iyon? 566 00:25:45,150 --> 00:25:47,062 Madla: Sa pamamagitan ng suit. 567 00:25:47,062 --> 00:25:47,770 Tagapagsalita: Sa pamamagitan ng suit. 568 00:25:47,770 --> 00:25:50,630 Kaya unang ay clustering sila ang lahat ng mga diamante magkasama 569 00:25:50,630 --> 00:25:52,560 ito ay tila, ang lahat ng mga puso-sama ito ay tila, 570 00:25:52,560 --> 00:25:56,520 at iba pa, nang walang paggalang para sa mga numero sa mga baraha. 571 00:25:56,520 --> 00:26:00,900 At ngayon lumilitaw ang mga ito, halimbawa, na pag-uuri ang mga ito sa pamamagitan ng numero. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Napakabuti. 574 00:26:08,910 --> 00:26:12,370 >> Ang lahat ng mga karapatan, kaya kung ano ang nangyayari sa maging ang huling hakbang pagkatapos dito? 575 00:26:12,370 --> 00:26:16,950 Sa sandaling mayroon kami ng apat na pinagsunod-sunod paghahabla, kung ano ang kailangan naming gawin sa apat na piles 576 00:26:16,950 --> 00:26:20,059 upang makamit isa pinagsunod-sunod deck, medyo simple? 577 00:26:20,059 --> 00:26:21,350 Kaya kailangan namin upang sumanib muli ang mga ito. 578 00:26:21,350 --> 00:26:25,160 >> Kaya mayroong isang kawili-wiling ideya na ang muli, daresay, ay napaka madaling maunawaan kahit na 579 00:26:25,160 --> 00:26:28,140 kung maaari mong hindi kailanman na-slapped na uri ng label na ito. 580 00:26:28,140 --> 00:26:31,900 Ang mga pangunahing paniwala ng paghahati ang problema wala sa kalahati oras na ito, 581 00:26:31,900 --> 00:26:33,410 ngunit hindi bababa sa apat na piraso. 582 00:26:33,410 --> 00:26:36,810 Paglutas halos fundamentally magkatulad na mga problema 583 00:26:36,810 --> 00:26:40,480 sa paghihiwalay ng bawat isa, at pagkatapos ay pinagsasama ang mga resulta. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 At, mahusay na, tapos na. 586 00:26:50,140 --> 00:26:52,140 Ang lahat ng mga karapatan, isang malaking bilog ng applause, kung magagawa namin. 587 00:26:52,140 --> 00:26:56,480 >> [APPLAUSE] 588 00:26:56,480 --> 00:26:59,740 >> Tagapagsalita: wala akong mga ideya kung ano ikaw gawin sa mga ito, ngunit dito mo pumunta. 589 00:26:59,740 --> 00:27:01,690 Salamat sa iyo kaya magkano. 590 00:27:01,690 --> 00:27:04,660 Kaya hayaan makita, ang dalawang minuto at walong segundo, 591 00:27:04,660 --> 00:27:07,490 kung nais mong hamunin ang iyong mga kaibigan. 592 00:27:07,490 --> 00:27:12,160 Ano pagkatapos ay pagpunta sa maging isang tumagal ang layo mula sa na ito 593 00:27:12,160 --> 00:27:13,830 na maaari naming magamit sa mas pangkalahatang? 594 00:27:13,830 --> 00:27:16,080 Well, sa tingin pabalik sa ito array ng mga numero, 595 00:27:16,080 --> 00:27:19,060 at sa tingin bumalik ngayon sa ilan sa mga pseudocode na naisulat namin sa nakaraan, 596 00:27:19,060 --> 00:27:22,080 at ito ay ang pseudocode para sa paglutas sa problema phone book. 597 00:27:22,080 --> 00:27:25,150 Kung saan sa pseudocode ko enumerated isang mas sistema paraan 598 00:27:25,150 --> 00:27:28,400 ng na naglalarawan kung paano ko ginawang isang napaka-intuitive algorithm ng pag-divide ng telepono ng tao 599 00:27:28,400 --> 00:27:31,650 aklat sa kalahati, ulitin, ulitin, ulitin, hanggang sa mahanap ako ng isang tao tulad ng Mike Smith, 600 00:27:31,650 --> 00:27:33,790 kung siya ay sa katunayan sa aklat telepono. 601 00:27:33,790 --> 00:27:37,610 >> Ngunit uri ng ko ginamit kung ano Tatawag ako isang napaka-iterative diskarte dito, 602 00:27:37,610 --> 00:27:42,160 sa partikular na notice sa linya 8 at 11 linya. 603 00:27:42,160 --> 00:27:46,750 Iyon ang mga ebidensiya ng isang iterative diskarteng ito, ang diskarteng looping, 604 00:27:46,750 --> 00:27:49,040 dahil iyon mismo ang pag-uugali nila humimok. 605 00:27:49,040 --> 00:27:52,910 Yaong parehong linya sabihin pumunta sa tatlong linya, at maaari mong uri ng 606 00:27:52,910 --> 00:27:55,140 isipin na iyon sa iyong mata isip bilang sa pagiging isang loop. 607 00:27:55,140 --> 00:27:59,080 Ay nagsasabi sa iyo ito upang bumalik up sa hakbang tatlong at ulitin, muli, at muli, 608 00:27:59,080 --> 00:28:00,010 at muli. 609 00:28:00,010 --> 00:28:04,410 >> Ngunit paano kung makakuha kami ng isang key ideya dito na ginawa namin hindi sa huling pagkakataon, 610 00:28:04,410 --> 00:28:10,280 at padaliin ang 8 linya at line 11 at ang kanilang mga kapitbahay 611 00:28:10,280 --> 00:28:12,840 bilang lamang ito, sa kulay dilaw. 612 00:28:12,840 --> 00:28:16,480 Ito ay hindi fundamentally ang pagpapaikli ang pseudocode Sobra, 613 00:28:16,480 --> 00:28:20,530 ngunit fundamentally ito pagbabago ang likas na katangian ng aking mga algorithm. 614 00:28:20,530 --> 00:28:24,220 Ano ngayon ang gagawin ko sinasabi sa hakbang 7, sa hakbang 10, 615 00:28:24,220 --> 00:28:29,140 ay upang maghanap para sa Mike sa eksaktong magkatulad na paraan, 616 00:28:29,140 --> 00:28:31,580 ngunit lamang sa kaliwang kalahati o ang karapatan sa kalahati. 617 00:28:31,580 --> 00:28:33,420 >> Kaya sa ibang salita, kung Sisimulan ko mula sa unang hakbang, 618 00:28:33,420 --> 00:28:36,150 kunin phone book, bukas sa gitna ng phone book, tumingin sa mga pangalan, 619 00:28:36,150 --> 00:28:39,010 kung Smith ay kabilang sa pangalan, tawagan Mike, iba pa 620 00:28:39,010 --> 00:28:44,340 kung Smith ay mas maaga sa libro, magbasa-pitong maghanap para sa Mike sa kaliwang kalahati ng libro. 621 00:28:44,340 --> 00:28:47,130 Ngunit na uri ng pakiramdam ng tulad ng ito ay nag-iiwan sa akin nakikipag-hang, tama? 622 00:28:47,130 --> 00:28:49,240 Sa dilaw, ay isang pagtuturo, ngunit kung paano gagawin ko 623 00:28:49,240 --> 00:28:51,870 maghanap para sa Mike sa kaliwang kalahati ng phone book? 624 00:28:51,870 --> 00:28:54,210 Saan Mayroon akong isang algorithm na kung saan ako 625 00:28:54,210 --> 00:28:57,100 maaaring maghanap para sa isang tao tulad ng Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Well, ito ay staring sa amin sa mukha. 627 00:28:58,980 --> 00:29:03,090 Maaari ko literal gamitin ang eksaktong parehong programa epektibo ng pagpunta hanggang sa tuktok 628 00:29:03,090 --> 00:29:06,490 tumakbo muling muli at ang parehong linya ng code. 629 00:29:06,490 --> 00:29:10,610 >> Kaya kahit na ito ay dapat na sa tingin tulad ng isang bit ng isang paikot-ikot kahulugan 630 00:29:10,610 --> 00:29:13,480 kung saan ka ng pagsagot ng isang tao ang tanong sa pamamagitan lamang uri ng pagtatanong 631 00:29:13,480 --> 00:29:15,990 muli ng parehong tanong, tulad ng kung bakit, bakit, bakit? 632 00:29:15,990 --> 00:29:21,580 Ang katotohanan ay dahil mahirap na namin ang naka-code isang pares ng mga espesyal na mga linya, na hakbang 4, 633 00:29:21,580 --> 00:29:25,320 kung saan ay isang kung, at hakbang 12, na ay epektibo ng isa pang sangay, 634 00:29:25,320 --> 00:29:30,120 dahil mayroon kaming mga stopgap mga panukala, algorithm na ito ay magwawakas kung namin 635 00:29:30,120 --> 00:29:32,050 hanapin Mike, o kung hindi namin. 636 00:29:32,050 --> 00:29:36,810 Ngunit sa hakbang 7 at 10 ngayon, mayroon kaming kung ano ang makikita namin tumawag sa isang recursive algorithm. 637 00:29:36,810 --> 00:29:40,420 At recursion ay sa katunayan isang malakas na ideya na ang isang ilan isip bending sa una, 638 00:29:40,420 --> 00:29:42,500 maaari naming ngayong mag-apply tulad ng sumusunod. 639 00:29:42,500 --> 00:29:46,600 >> Pagsamahin ang uri-uriin ang magiging huling uri na tinitingnan namin ang, hindi bababa sa klase pormal. 640 00:29:46,600 --> 00:29:50,040 At ito ay fundamentally iba't ibang mula sa mga huling tatlong, at tiyak 641 00:29:50,040 --> 00:29:52,140 huling apat na kung isama namin bogosort. 642 00:29:52,140 --> 00:29:54,810 Narito ang pseudocode para sa uri merge. 643 00:29:54,810 --> 00:30:00,170 Kapag sa input ng n elemento, kaya ibinigay isang hanay ng mga sukat n, kung n ay mas mababa sa 2, 644 00:30:00,170 --> 00:30:01,040 bumalik. 645 00:30:01,040 --> 00:30:03,610 Kaya bakit mayroon akong na katinuan suriin muna? 646 00:30:03,610 --> 00:30:09,477 Ano ang implikasyon kung ipasa ko sa iyo isang array na kung saan ang haba n Mababa sa 2? 647 00:30:09,477 --> 00:30:11,060 Na-pinagsunod-sunod, malinaw naman, tama? 648 00:30:11,060 --> 00:30:13,640 Dahil ang listahan ng alinman sa may ang isang elemento, na kung saan ay trivially 649 00:30:13,640 --> 00:30:15,180 pinagsunod-sunod dahil ito ay ang tanging bagay doon. 650 00:30:15,180 --> 00:30:18,138 O kaya naman, ito ay ang laki ng zero na nangangahulugang walang upang pagbukud-bukurin ang, kaya sa pamamagitan ng kalikasan 651 00:30:18,138 --> 00:30:18,720 ito ay pinagsunod-sunod. 652 00:30:18,720 --> 00:30:20,410 Mayroong walang lamang mali doon. 653 00:30:20,410 --> 00:30:22,310 Kaya na aming tinatawag na base kaso. 654 00:30:22,310 --> 00:30:24,440 >> Iyon ay katulad sa espiritu sa kung ano ang ginawa namin gamit ang Mike. 655 00:30:24,440 --> 00:30:26,023 Kung ni Mike sa aklat ng telepono, tumawag sa kanya. 656 00:30:26,023 --> 00:30:27,740 Kung siya ay hindi doon, ibigay up. 657 00:30:27,740 --> 00:30:31,240 Ito ay isang tinatawag na base kaso, upang matiyak ito algorithm sa pagtatapos ng araw 658 00:30:31,240 --> 00:30:33,540 Hihinto sa ilang mga pangyayari. 659 00:30:33,540 --> 00:30:37,890 >> Ngunit narito ang hakbang ng pananampalataya ngayon, iba pa, -uri-uriin ang kaliwang kalahati ng mga elemento, 660 00:30:37,890 --> 00:30:39,740 pagkatapos ay i-uri-uriin ang karapatan kalahati ng mga elemento, 661 00:30:39,740 --> 00:30:41,189 at pagkatapos ay pagsamahin ang pinagsunod-sunod halves. 662 00:30:41,189 --> 00:30:43,230 At narito ang kung saan ito nararamdaman tulad kami copping out. 663 00:30:43,230 --> 00:30:46,900 Tinanong ko ang upang pagbukud-bukurin sa iyo n elemento, at ako 664 00:30:46,900 --> 00:30:50,712 na nagsasabi, OK, huwag ito sa pamamagitan ng pag-uuri sa kaliwa at sa pag-aayos sa kanan. 665 00:30:50,712 --> 00:30:52,420 Ngunit ako ay sinasabi ng isang iba pang mga bagay, at ito 666 00:30:52,420 --> 00:30:55,530 ay ang susi tema ito ay tila sa Swersey kaya sa ngayon, 667 00:30:55,530 --> 00:30:57,380 mayroong ito ikatlong hakbang ng pagbubuklod. 668 00:30:57,380 --> 00:31:00,430 Aling kahit na ito Mukhang kaya pipi sa espiritu, 669 00:31:00,430 --> 00:31:02,320 tulad ng sumanib lamang bagay magkasama, tila 670 00:31:02,320 --> 00:31:05,380 upang maging isang mahalagang hakbang patungo sa reassembly ng dalawang mga problema na 671 00:31:05,380 --> 00:31:07,330 ay hinati sa huli sa kalahati. 672 00:31:07,330 --> 00:31:12,090 >> Kaya sumanib-uri-uriin, ni gawin ito ipaalam, kung ikaw ay katatawanan sa akin, may isa pang demonstration, 673 00:31:12,090 --> 00:31:14,730 kaya lang na mayroon kaming ilang mga mga numero upang gumana sa. 674 00:31:14,730 --> 00:31:19,470 Maaari ba akong makipagpalitan ng walong ang stress bola para sa walong tao? 675 00:31:19,470 --> 00:31:29,320 Ang lahat ng mga karapatan, kung paano tungkol sa iyo tatlong, mo apat sa seksiyong ito, limang, anim, at sabihin 676 00:31:29,320 --> 00:31:30,720 huwag 7, 8, dumating sa up. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, Oo OK. 679 00:31:36,520 --> 00:31:38,640 Minus 8, doon pumunta kami, plus 1. 680 00:31:38,640 --> 00:31:39,150 Mahusay. 681 00:31:39,150 --> 00:31:42,000 Lahat ng karapatan ay sa up, sabihin mabilis na magbibigay sa iyo ng mga numero. 682 00:31:42,000 --> 00:31:50,800 Numero ng dalawang, numero ng tatlong, numero ng apat, numero ng limang, anim, pitong, at walong. 683 00:31:50,800 --> 00:31:52,140 Ginawa ko nang tama ang walong oras na ito. 684 00:31:52,140 --> 00:31:56,390 >> OK, kaya sige kung magagawa mo, at ni-uri-uriin sa orihinal na pagkakasunud-sunod hayaan 685 00:31:56,390 --> 00:31:59,810 na nagkaroon kami kahapon kung saan ay tumingin tulad nito, kung hindi mo nais na bale. 686 00:31:59,810 --> 00:32:03,620 At gawin ni ito sa harap ng table ipaalam. 687 00:32:03,620 --> 00:32:06,510 Ang lahat ng mga karapatan, kaya pagsamahin-uri-uriin. 688 00:32:06,510 --> 00:32:08,820 Ito ay kung saan ito ang nangyayari upang makakuha ng mga uri ng kawili-wili, 689 00:32:08,820 --> 00:32:12,800 dahil mukhang ako na nagbibigay sa aking sarili kaya higit na mas mababa impormasyon ngayon. 690 00:32:12,800 --> 00:32:15,149 >> Kaya sumanib-uri-uriin una sa lahat sa input ng n elemento, 691 00:32:15,149 --> 00:32:18,440 at ito ay malinaw naman hindi kukulangin sa dalawang, ito ay walo, kaya bang makakuha ng ilang pang trabaho na gawin. 692 00:32:18,440 --> 00:32:21,140 Kaya ngayon itak namin bilang isang klase na ngayon sa ibang sangay, 693 00:32:21,140 --> 00:32:22,540 na nangangahulugan tatlong hakbang. 694 00:32:22,540 --> 00:32:25,017 Una, mayroon akong upang ayusin ang kaliwang kalahati ng mga elemento. 695 00:32:25,017 --> 00:32:26,350 Kaya paano ko pumunta tungkol sa paggawa na ito? 696 00:32:26,350 --> 00:32:28,950 Well, ako ako pagpunta sa uri ng itak hatiin ang listahan dito, 697 00:32:28,950 --> 00:32:30,700 hindi mo kailangang i- pisikal na ilipat, at ako 698 00:32:30,700 --> 00:32:33,180 pagpunta upang tumutok lamang sa mga kaliwang kalahati ng mga elemento dito. 699 00:32:33,180 --> 00:32:36,770 Kaya paano ko pumunta ako tungkol sa pag-uuri isang listahan ngayon ng apat na laki? 700 00:32:36,770 --> 00:32:38,730 Ano ang aking algorithm? 701 00:32:38,730 --> 00:32:42,580 Una kong suriin ay n mas mababa kaysa sa dalawang, hindi, kaya magpatuloy ko muli sa ibang block. 702 00:32:42,580 --> 00:32:43,900 Pagsunud-sunurin ayon kaliwa kalahati ng mga elemento. 703 00:32:43,900 --> 00:32:45,608 >> Kaya ngayon muli, itak, at ito ay kung saan 704 00:32:45,608 --> 00:32:49,550 Mayroon kang nakakaipon ng maraming sakit sa kasaysayan, kung gagawin mo. 705 00:32:49,550 --> 00:32:51,940 Ngayon ako sa pag-aayos sa kaliwa kalahati ng kaliwang kalahati. 706 00:32:51,940 --> 00:32:57,000 Ang lahat ng mga karapatan, kaya ngayon Tinatawag kong aking parehong pagsanib pag-uuri algorithm, ay n mas mababa sa dalawang? 707 00:32:57,000 --> 00:33:00,590 Hindi, ito ay dalawang, kaya Mayroon akong upang ayusin kaliwang kalahati, at ang kanang kalahati. 708 00:33:00,590 --> 00:33:02,042 Kaya dito pumunta kami, uri-uriin ang natitira kalahati. 709 00:33:02,042 --> 00:33:03,750 Bakit hindi mo pa lamang tumagal ng isang hakbang pasulong. 710 00:33:03,750 --> 00:33:04,415 Ano ang inyong pangalan? 711 00:33:04,415 --> 00:33:04,860 >> Madla: Darren. 712 00:33:04,860 --> 00:33:05,260 >> Tagapagsalita: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan ay stepped pasulong. 714 00:33:06,040 --> 00:33:06,748 >> Madla: Darren. 715 00:33:06,748 --> 00:33:09,000 Tagapagsalita: Darren, tapos na. 716 00:33:09,000 --> 00:33:10,090 Sabihin mo ba Darren o Dan? 717 00:33:10,090 --> 00:33:10,550 >> Madla: Darren. 718 00:33:10,550 --> 00:33:11,216 >> Tagapagsalita: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren ay stepped pasulong at siya ay pinagsunod-sunod ngayon. 720 00:33:14,422 --> 00:33:16,130 At ito ay halos isang inane claim, tama? 721 00:33:16,130 --> 00:33:18,862 Huwag tila ko talagang i-pagkamit ng magpatuloy anumang bagay, ngunit hayaan. 722 00:33:18,862 --> 00:33:20,820 Ngayon ipaalam sa akin-uri-uriin ang karapatan kalahati ng mga elemento. 723 00:33:20,820 --> 00:33:21,200 Ano ang inyong pangalan? 724 00:33:21,200 --> 00:33:21,690 >> Madla: Luke. 725 00:33:21,690 --> 00:33:22,273 >> Tagapagsalita: Luke. 726 00:33:22,273 --> 00:33:23,400 Halika sa, magbasa-forward. 727 00:33:23,400 --> 00:33:25,640 Tapos, na-pinagsunod-sunod ko Lucas. 728 00:33:25,640 --> 00:33:28,570 Ang kaliwang kalahati ay pinagsunod-sunod ngayon at ang karapatan kalahati ay pinagsunod-sunod ngayon, 729 00:33:28,570 --> 00:33:30,770 ngunit muli, mayroong isang mahalagang hakbang dito. 730 00:33:30,770 --> 00:33:32,940 Ano ang susunod na kailangan kong gawin? 731 00:33:32,940 --> 00:33:33,941 Pagsamahin ang pinagsunod-sunod halves. 732 00:33:33,941 --> 00:33:36,648 Ngayon kami ay pagpunta sa may lamang lahat nang pabalik-balik sa ganitong paraan, 733 00:33:36,648 --> 00:33:38,620 dahil ko uri ng kailangan ilang espasyo sa simula. 734 00:33:38,620 --> 00:33:40,411 Ito ay halos tulad ng mga ito guys ay nasa isang mesa, 735 00:33:40,411 --> 00:33:42,460 at kailangan ko ang ilang mga kuwarto upang ilipat ang mga ito sa paligid sa. 736 00:33:42,460 --> 00:33:44,170 Kaya ako pupunta upang sumanib mo guys sa pamamagitan ng pagtingin 737 00:33:44,170 --> 00:33:45,960 sa kaliwang kalahati at ang kanang kalahati. 738 00:33:45,960 --> 00:33:48,740 At malinaw naman kung sino ang mauuna, iniwan kalahati o pakanan kalahati? 739 00:33:48,740 --> 00:33:52,710 Kaya kanang kalahati, kaya ni Lucas ilipat sa paglipas ng ipaalam dito sa orihinal na posisyon Darren iyon. 740 00:33:52,710 --> 00:33:57,640 At ngayon upang pagsamahin ang kanilang kaliwang kalahati in, Darren pupuntahan ilipat mula doon. 741 00:33:57,640 --> 00:33:59,750 >> Kaya pakiramdam ng tulad ng halos ang isang bubble ng uri ng epekto, 742 00:33:59,750 --> 00:34:02,482 ngunit ang aking pangunahing mga algorithm, napaka iba't ibang mga oras na ito. 743 00:34:02,482 --> 00:34:04,815 Ngunit ngayon kung saan ang mga bagay makakuha ng isang maliit na nakakainis na dahil ikaw 744 00:34:04,815 --> 00:34:06,810 mag-rewind itak kung saan nag-iwan ako off. 745 00:34:06,810 --> 00:34:09,893 Lamang ako ng Pinagsama ang Pinagbukud-bukod halves, na nangangahulugan na ako kung saan sa aking mga algorithm? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Mayroon akong upang pagbukud-bukurin ang karapatan kalahati, tama? 748 00:34:13,770 --> 00:34:15,910 >> Kung rewind, literal sa video, ipapakita sa iyo 749 00:34:15,910 --> 00:34:18,339 makita na Nakakuha kami upang ito punto ni Lucas at Darren 750 00:34:18,339 --> 00:34:21,370 sa pamamagitan ng pag-uuri sa kaliwa kalahati ng kaliwang kalahati. 751 00:34:21,370 --> 00:34:23,430 Pagkatapos Pinagsama namin ang mga Pinagbukud-bukod halves, na 752 00:34:23,430 --> 00:34:27,941 ay nangangahulugan na ang susunod na hakbang ay isang uri ng kanang kalahati ng kaliwang kalahati. 753 00:34:27,941 --> 00:34:29,649 Ang lahat ng mga karapatan, kaya sabihin gawin ito nang mas mabilis. 754 00:34:29,649 --> 00:34:33,282 Ang lahat ng mga karapatan, anim, pupuntahan ko upang i-claim ikaw ay pinagsunod-sunod ngayon, dumating sa pasulong. 755 00:34:33,282 --> 00:34:33,990 Ano ang inyong pangalan? 756 00:34:33,990 --> 00:34:34,589 >> Madla: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> Tagapagsalita: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano ay pinagsunod-sunod ngayon. 759 00:34:36,010 --> 00:34:36,450 At kung ano ang iyong pangalan? 760 00:34:36,450 --> 00:34:37,080 >> Madla: Alex. 761 00:34:37,080 --> 00:34:38,379 >> Tagapagsalita: Alex ay pinagsunod-sunod ngayon. 762 00:34:38,379 --> 00:34:40,750 Kaliwa kalahati, i-right kalahati, ano ang huling hakbang? 763 00:34:40,750 --> 00:34:41,250 Pagsamahin. 764 00:34:41,250 --> 00:34:44,310 Pretty trivia, kaya ako pagpunta upang sumanib sa anim, 765 00:34:44,310 --> 00:34:46,930 tumagal ng isang hakbang pabalik, walo, kumuha nang isang hakbang pabalik. 766 00:34:46,930 --> 00:34:49,530 At ngayon mapansin na ito ay isang kapaki-pakinabang takeaway, kung ano 767 00:34:49,530 --> 00:34:53,930 ngayon ay totoo tungkol sa kaliwang kalahati ng listahan, kanikanilang mga kung paano namin nagsimula? 768 00:34:53,930 --> 00:34:55,090 Ito ay pinagsunod-sunod. 769 00:34:55,090 --> 00:34:57,750 >> Ngayon hindi ito pinagsunod-sunod sa ang malaking scheme ng mga bagay, 770 00:34:57,750 --> 00:35:00,250 ngunit ito ay pinagsunod-sunod nang nakapag-iisa ng iba pang kalahati. 771 00:35:00,250 --> 00:35:04,100 Ngayon kung ano ang hakbang na ako sa kung panatilihing ako rewinding kung paano nagsimula ang kuwento? 772 00:35:04,100 --> 00:35:05,680 Ngayon Mayroon akong upang pagbukud-bukurin ang karapatan kalahati. 773 00:35:05,680 --> 00:35:07,630 Kaya ngayon kami ay paraan pabalik sa simula ng kuwento, 774 00:35:07,630 --> 00:35:08,921 at sabihin gawin ito nang higit pa mabilis. 775 00:35:08,921 --> 00:35:11,320 Kaya ako pagpunta sa uri-uriin ang kanang kalahati ng buong listahan. 776 00:35:11,320 --> 00:35:13,060 Ano ang susunod na hakbang? 777 00:35:13,060 --> 00:35:15,840 -Uri-uriin ang natitira sa kalahati ng mga karapatan kalahati. 778 00:35:15,840 --> 00:35:18,715 -Uri-uriin ang natitira kalahati ng kaliwang kalahati ng kanang kalahati. 779 00:35:18,715 --> 00:35:19,590 At kung ano ang iyong pangalan? 780 00:35:19,590 --> 00:35:20,230 >> Madla: Omar. 781 00:35:20,230 --> 00:35:21,970 >> Tagapagsalita: Omar, magbasa-forward, tapos na. 782 00:35:21,970 --> 00:35:22,860 Kaliwa kalahati ay pinagsunod-sunod. 783 00:35:22,860 --> 00:35:23,330 At kung ano ang iyong pangalan? 784 00:35:23,330 --> 00:35:23,820 >> Madla: Chris. 785 00:35:23,820 --> 00:35:25,620 >> Tagapagsalita: Chris, kumuha nang isang hakbang pasulong, ikaw ay pinagsunod-sunod ngayon. 786 00:35:25,620 --> 00:35:27,010 Ano ang mga pangunahing hakbang ngayon? 787 00:35:27,010 --> 00:35:27,510 Pagsamahin. 788 00:35:27,510 --> 00:35:30,509 Kaya isa ay pagpunta upang sumanib sa lugar dito, kung maaari kang kumuha ng isang hakbang pabalik, 789 00:35:30,509 --> 00:35:32,930 at tatlong ay pagpunta sa tumagal ng isang hakbang pabalik, pagsamahin. 790 00:35:32,930 --> 00:35:38,080 Kaya sa kaliwang kalahati ng kanang kalahati, ay pinagsunod-sunod ngayon. 791 00:35:38,080 --> 00:35:41,747 Tapat, pakiramdam ng algorithm na ito tulad ng namin ay aksaya paraan ng higit pang oras kaysa sa dati, 792 00:35:41,747 --> 00:35:44,830 ngunit kung ginawa namin ito sa real time, ipapakita namin tingnan kung ano ang takeaways pagpunta sa maging. 793 00:35:44,830 --> 00:35:47,970 Ngayon dito Ako, i-right kalahati ng kanang kalahati, 794 00:35:47,970 --> 00:35:50,170 hayaan mo akong sige at ayusin ang kaliwang kalahati. 795 00:35:50,170 --> 00:35:51,482 Hakbang pasulong, kung ano ang iyong pangalan? 796 00:35:51,482 --> 00:35:52,190 Madla: Ramsey. 797 00:35:52,190 --> 00:35:53,210 Tagapagsalita: Ramsey ay pinagsunod-sunod ngayon. 798 00:35:53,210 --> 00:35:53,570 Ano ang inyong pangalan? 799 00:35:53,570 --> 00:35:54,200 >> Madla: Marina. 800 00:35:54,200 --> 00:35:57,033 >> Tagapagsalita: Marina ay pinagsunod-sunod na ngayon bilang well, kung gagawin mo ng isang hakbang pasulong. 801 00:35:57,033 --> 00:36:00,690 Key hakbang dito ay sumanib ngayon, ako pagpunta sa pluck mula sa aking dalawang mga listahan, 802 00:36:00,690 --> 00:36:01,720 pakaliwa at pakanan. 803 00:36:01,720 --> 00:36:05,150 Limang ay pagpunta sa first come, at pitong ay pagpunta sa darating sa susunod. 804 00:36:05,150 --> 00:36:06,410 At muli, ito ay sinadya. 805 00:36:06,410 --> 00:36:08,535 Ang katotohanan na ito ay naka-pagkuha hakbang pasulong at pabalik 806 00:36:08,535 --> 00:36:12,997 Nakalaan lamang ito upang kumatawan na hindi namin maaari gawin algorithm na ito sa lugar na kasing-dali 807 00:36:12,997 --> 00:36:15,830 bilang uri ng bubble, at uri seleksyon, at uri ng pagpapasok ng kung saan kami lamang 808 00:36:15,830 --> 00:36:16,960 pinananatiling pagpapalit ng mga tao. 809 00:36:16,960 --> 00:36:19,940 Literal na kailangan ko ng isang sort ng scratch papel kung saan 810 00:36:19,940 --> 00:36:21,827 upang ilagay ang mga tao habang gagawin ko ang pagsasama, 811 00:36:21,827 --> 00:36:23,410 at pagkatapos ay maaari kong ilagay ang mga ito pabalik sa lugar. 812 00:36:23,410 --> 00:36:27,260 At iyon ang key dahil ako ako gamit ang isang bagong mapagkukunan, espasyo, hindi lamang oras. 813 00:36:27,260 --> 00:36:28,270 >> OK, ito ay kamangha-manghang. 814 00:36:28,270 --> 00:36:32,050 Kaliwa kalahati ay pinagsunod-sunod, i-right kalahati ay Pinagbukud-bukod, ngayon na key pinagsasama ang mga hakbang na ito. 815 00:36:32,050 --> 00:36:33,450 Paano ako pagpunta upang sumanib ito? 816 00:36:33,450 --> 00:36:35,470 Kaya kung makikita mo sundin ang aking pakaliwa kamay at kanang kamay, 817 00:36:35,470 --> 00:36:38,930 Pupunta ako upang ituro ang aking kaliwang kamay sa kaliwang kalahati, ang aking kanang kamay 818 00:36:38,930 --> 00:36:42,680 sa kanang kalahati, at ngayon Kailangan ko bang magpasya sunud-sunod kung kanino upang sumanib sa. 819 00:36:42,680 --> 00:36:44,650 Sino malinaw naman ang mauna? 820 00:36:44,650 --> 00:36:45,150 Numero ng isa. 821 00:36:45,150 --> 00:36:47,327 Kaya dumating sa paglipas dito, narito ang aming mga scratch pad. 822 00:36:47,327 --> 00:36:49,910 Kaya ngayon numero ng isa, at abiso kung ano ang makikita ko sa pamamagitan ng aking kanang kamay, 823 00:36:49,910 --> 00:36:54,152 Pupunta ako sa ilipat ang aking kanang kamay isa basa sa ibabaw upang ituro ang numero ng tatlong, 824 00:36:54,152 --> 00:36:55,860 at ngayon may kong gumawa ang parehong desisyon. 825 00:36:55,860 --> 00:36:58,387 At talagang tumayo karapatan sa harap ng Lucas dito kung magagawa mo, 826 00:36:58,387 --> 00:36:59,720 dahil ito ay ang aming mga scratch pad. 827 00:36:59,720 --> 00:37:00,610 Kaya sino ay susunod? 828 00:37:00,610 --> 00:37:05,000 Mayroon kaming Lucas na may numero ng dalawang o Chris na may numero ng tatlong. 829 00:37:05,000 --> 00:37:07,460 Malinaw Lucas, numero dalawa, kaya napunta ka dito. 830 00:37:07,460 --> 00:37:11,270 >> Ngunit ang aking kaliwang ngayon ay pagpunta sa ay incremented upang tumuro sa Darren, 831 00:37:11,270 --> 00:37:15,160 at narito ang key tumagal ang layo sa pagbubuklod, ako ako pagpunta sa panatilihin ang paggawa nito, 832 00:37:15,160 --> 00:37:17,340 malinaw naman, kung ikaw uri ng sundin ang logic. 833 00:37:17,340 --> 00:37:19,670 Ngunit ang aking mga kamay ay hindi kailanman pagpunta sa pumunta paurong, 834 00:37:19,670 --> 00:37:23,861 na ang ibig sabihin ay nakakaapekto lamang ako sa paglipat sa ang natitira sa aking proseso ng pagsasama, 835 00:37:23,861 --> 00:37:26,360 at na ang nangyayari upang maging susi sa aming pag-aaral sa isang sandali lamang. 836 00:37:26,360 --> 00:37:27,859 >> Kaya ng tapusin ito up mabilis na ngayon hayaan. 837 00:37:27,859 --> 00:37:31,650 Kaya tatlong ay susunod, pagkatapos ng apat na nanggagaling sa tabi, 838 00:37:31,650 --> 00:37:38,750 at ngayon ay limang susunod, pagkatapos ay i-anim, at pitong, at pagkatapos ay sa wakas ay alas-otso. 839 00:37:38,750 --> 00:37:42,960 Pakiramdam ng tulad ng pinakamabagal na algorithm pa, ngunit hindi namin kung talagang 840 00:37:42,960 --> 00:37:45,510 patakbuhin ito sa parehong uri bilis ng orasan, kaya upang 841 00:37:45,510 --> 00:37:48,106 makipag-usap, na may parehong ticking orasan tulad ng dati. 842 00:37:48,106 --> 00:37:48,605 Bakit? 843 00:37:48,605 --> 00:37:51,100 Well, Sabihin maglaan ng tumingin sa dulo ng resulta. 844 00:37:51,100 --> 00:37:56,990 >> Sabihin bumalik sa paglipas dito, ipaalam sa akin hilahin up sa isang demonstration biswal 845 00:37:56,990 --> 00:37:59,030 ng kung ano ang ginawa namin lamang. 846 00:37:59,030 --> 00:38:06,110 Ang pag-zoom in dito, sa na ito pahina dito, na nagsasabi sa Firefox 847 00:38:06,110 --> 00:38:08,200 na nais naming mag-lilinya hanggang sa kahong ito, sabihin 848 00:38:08,200 --> 00:38:11,260 sabihin bubble-uri-uriin, kung saan Ikinalulungkot namin ngayon na rin pamilyar, 849 00:38:11,260 --> 00:38:14,130 uri pinili, na kung saan ay isa pang medyo prangka isa, 850 00:38:14,130 --> 00:38:18,250 at ngayon uri pagsanib ngayon, na Magiging aming climactic nagtatapos. 851 00:38:18,250 --> 00:38:21,530 Ang dahilan kung bakit ito kinuha kaya mas matagal dito sa mga kawani na tao at ako ay pasalita, 852 00:38:21,530 --> 00:38:23,480 malinaw naman, ako ko na nagpapaliwanag sa bawat hakbang. 853 00:38:23,480 --> 00:38:26,920 Ngunit kung execute mo lang ito, magkano tulad ng ginawa namin bubble-uri-uriin at seleksyon 854 00:38:26,920 --> 00:38:30,890 uri hindi lamang biswal, sa panonood paano lamang magkano ang mas mahusay 855 00:38:30,890 --> 00:38:33,330 ito sinusulit ng dibisyon at conquering 856 00:38:33,330 --> 00:38:39,150 Pwedeng kapag inilapat sa isang hanay ng data na Hindi kahit na laki ng walong, ngunit kahit magkano, 857 00:38:39,150 --> 00:38:39,970 magkano ang mas malaking. 858 00:38:39,970 --> 00:38:44,585 Bigyan ko bang pagsamahin mo uri, tabi- gilid sa iba pang mga algorithm. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Ito ay pagpunta upang makakuha ng masakit mabilis, at ang nagtatapos 861 00:38:58,530 --> 00:39:00,890 ay hindi partikular na climactic, tapusin lang nila up pinagsunod-sunod. 862 00:39:00,890 --> 00:39:05,280 Ngunit ang susi tumagal ang layo ay na hitsura kung magkano ang mas mabilis na bumaybay-uri 863 00:39:05,280 --> 00:39:08,110 ay, maliban kung sa tingin mo ako lamang uri ng panggugulo sa iyo. 864 00:39:08,110 --> 00:39:13,100 Kung gagawin namin ito ng isang huling oras, Hinahayaan ni-reload ito, sabihin bumalik 865 00:39:13,100 --> 00:39:14,960 at pumili ng bubble uri, at para lamang sa mga kicks, 866 00:39:14,960 --> 00:39:17,330 hayaan pumili ng pagpapasok -uri-uriin, para lamang sa mabuting panukala. 867 00:39:17,330 --> 00:39:20,020 At oras na ito muli, sabihin pumili ng uri merge at sabihin 868 00:39:20,020 --> 00:39:21,595 talaga tumakbo ang mga magkatabi. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> At ito ay hindi, sa katunayan, isang fluke. 871 00:39:26,930 --> 00:39:31,140 Ano mabisang ko nagawa mo na ay na hindi ko na hinati ang aking input sa kalahati, muli, 872 00:39:31,140 --> 00:39:32,240 at muli, at muli. 873 00:39:32,240 --> 00:39:35,590 At mayroon lamang kaya maraming beses na maaari kang hatiin ang iyong input sa halves, pakaliwa 874 00:39:35,590 --> 00:39:36,240 at kanan. 875 00:39:36,240 --> 00:39:39,425 Ano ang formula na panatilihin namin ang nakakakita na naglalarawan ng dibisyon sa kalahati 876 00:39:39,425 --> 00:39:41,050 muli, at muli, at muli, at muli? 877 00:39:41,050 --> 00:39:41,890 >> Madla: Mag-log n. 878 00:39:41,890 --> 00:39:42,760 >> Tagapagsalita: Mag-log n. 879 00:39:42,760 --> 00:39:46,300 Ngunit pagkatapos ay mayroong isang iba pang mga pangunahing hakbang, algorithm na ito ay hindi mag-log n hakbang. 880 00:39:46,300 --> 00:39:48,992 Kung ito ay mag-log lamang n hakbang na ito, Gusto naming maging sa parehong problema 881 00:39:48,992 --> 00:39:51,200 tulad ng dati kung saan hindi namin maaaring maging Tiyaking ang lahat ng pinagsunod-sunod. 882 00:39:51,200 --> 00:39:54,480 Kailangan mong Nagnais tumingin sa n elemento upang makatiyak n mga elemento ay pinagsunod-sunod, 883 00:39:54,480 --> 00:39:55,950 kung hindi man ito ay isang hakbang ng pananampalataya. 884 00:39:55,950 --> 00:39:59,810 >> Kaya Nagnais log n hakbang na ito, ngunit kung ano ang tungkol sa mga pangunahing hakbang pagsasama 885 00:39:59,810 --> 00:40:04,370 kung saan ako naka-merge ang aking kaliwang kalahati at kanang mga kalahati at lumakad sa buong yugto? 886 00:40:04,370 --> 00:40:06,980 Ilang hakbang na ito ay na upang sumanib? 887 00:40:06,980 --> 00:40:10,150 Ito'y n, ngunit ko ginawa hindi lamang pagsamahin ang panghuling oras. 888 00:40:10,150 --> 00:40:15,089 Sa bawat isa sa mga nested mga tawag, sa bawat ng mga nested merges, pinagsunod-sunod pa rin ako. 889 00:40:15,089 --> 00:40:18,380 Pinagsama ko ang dalawang guys, pagkatapos ay ang dalawang guys, pagkatapos ay ang dalawang guys at iba pa. 890 00:40:18,380 --> 00:40:19,955 >> Kaya ako nag pinagsasama muli, at muli. 891 00:40:19,955 --> 00:40:20,580 Gaano karaming beses? 892 00:40:20,580 --> 00:40:23,510 Kaya sa tuwing ko na hinati-hati ang listahan sa kalahati, ginawa ko ang isang pag-merge. 893 00:40:23,510 --> 00:40:25,460 Hatiin ang listahan sa kalahati, gawin ang isang pag-merge. 894 00:40:25,460 --> 00:40:28,570 Kaya kung paghati sa listahan Maaaring magawa ng log n beses, 895 00:40:28,570 --> 00:40:33,880 at ang pagsasama sa huli ay tumatagal ng n hakbang na ito, kung ano ang maaaring maging itaas na ngayon 896 00:40:33,880 --> 00:40:37,000 nakatali sa pagtakbo oras ng aming algorithm? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> At sa katunayan, iyon ang na nakamit namin dito. 899 00:40:40,560 --> 00:40:44,650 Kaya ang pakiramdam na nakikita mo kapag biswal mga tatlong bagay bahagi tumakbo sa pamamagitan ng gilid 900 00:40:44,650 --> 00:40:47,930 ay nakalapat n laban n nakalapat laban sa n log n. 901 00:40:47,930 --> 00:40:51,010 Aling fundamentally ipapakita namin makita, hindi lamang ngayon ngunit sa hinaharap, 902 00:40:51,010 --> 00:40:52,760 ay mas, mas mabilis. 903 00:40:52,760 --> 00:40:56,010 Ang isang round ng applause para sa mga guys, Ako ay gantimpalaan ang mga ito ang stress bola. 904 00:40:56,010 --> 00:41:00,260 Ni adjourn dito ngayon Hayaan, at aalisin namin ang nakikita mo sa Lunes. 905 00:41:00,260 --> 00:41:02,255