1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [Nagpe-play ng musika] 3 00:00:10,800 --> 00:00:13,500 David MALAN: Lahat ng karapatan. 4 00:00:13,500 --> 00:00:14,670 Ang lahat ng mga karapatan, maligayang pagdating pabalik. 5 00:00:14,670 --> 00:00:18,120 Kaya ito ay Linggo 4, sa simula niyaon, na. 6 00:00:18,120 --> 00:00:21,320 At makikita mo na isipin ang nakaraang linggo, inilalagay namin ang Code para sa isang tabi lamang ng kaunting 7 00:00:21,320 --> 00:00:24,240 at nagsimula kaming nagsasalita ng kaunti pa mataas na antas, tungkol sa mga bagay tulad ng 8 00:00:24,240 --> 00:00:28,130 paghahanap at pag-uuri, na bagaman medyo simpleng ideya, ay 9 00:00:28,130 --> 00:00:31,840 kinatawan ng isang klase ng mga problema magsisimula kang upang malutas lalo 10 00:00:31,840 --> 00:00:34,820 bilang ka magsimula-iisip tungkol sa huling proyekto at kagiliw-giliw na mga solusyon sa iyo 11 00:00:34,820 --> 00:00:36,760 baka magkaroon sa real-world problema. 12 00:00:36,760 --> 00:00:39,490 Ngayon bubble-uri ay isa sa mga pinakamadaling tulad ng mga algorithm, at ito 13 00:00:39,490 --> 00:00:42,900 nagtrabaho sa pamamagitan ng pagkakaroon ng mga maliliit na mga numero sa isang listahan o sa isang array uri ng 14 00:00:42,900 --> 00:00:46,530 bubble kanilang mga paraan up sa tuktok, at ang malaki mga numero ng ilipat ang kanilang mga paraan pababa sa 15 00:00:46,530 --> 00:00:47,930 sa dulo ng listahan na iyon. 16 00:00:47,930 --> 00:00:50,650 >> At isipin ang na kami maaaring maisalarawan bubble sort ng kaunti 17 00:00:50,650 --> 00:00:52,310 isang bagay na katulad nito. 18 00:00:52,310 --> 00:00:53,640 Kaya ipaalam sa akin sige at i-click ang Simulan. 19 00:00:53,640 --> 00:00:55,350 Ko na preselected bubble sort. 20 00:00:55,350 --> 00:00:58,920 At kung isipin ang mo na ang taller asul mga linya ay kumakatawan sa malaking numero, maliit 21 00:00:58,920 --> 00:01:03,300 asul na linya ay kumakatawan maliit na mga numero, bilang pumunta namin sa pamamagitan ng ito muli at muli at 22 00:01:03,300 --> 00:01:07,680 muli, paghahambing ng dalawang bar sa tabi ng bawat iba sa pula, kami ay pagpunta sa swap ang 23 00:01:07,680 --> 00:01:11,010 pinakamalaki at ang pinakamaliit na kung ang mga ito ay out ng order. 24 00:01:11,010 --> 00:01:14,150 >> Kaya ito ay pumunta sa at pumunta sa at pumunta on, at makikita mo na ang mas malaking 25 00:01:14,150 --> 00:01:16,700 mga elemento ay paggawa ng kanilang mga paraan upang ang kanan, at ang mga mas maliit na mga elemento ay 26 00:01:16,700 --> 00:01:17,900 paggawa ng kanilang mga paraan sa kaliwa. 27 00:01:17,900 --> 00:01:21,380 Ngunit sinimulan namin upang tumyak ng dami ang kahusayan, ang 28 00:01:21,380 --> 00:01:22,970 kalidad ng mga ito algorithm. 29 00:01:22,970 --> 00:01:25,200 At sinabi namin na sa pinakamalala kaso, algorithm na ito kinuha 30 00:01:25,200 --> 00:01:27,940 halos kung gaano karaming mga hakbang na ito? 31 00:01:27,940 --> 00:01:28,980 >> Kaya n squared. 32 00:01:28,980 --> 00:01:30,402 At kung ano ang n? 33 00:01:30,402 --> 00:01:31,650 >> Madla: Bilang ng mga elemento. 34 00:01:31,650 --> 00:01:32,790 >> David MALAN: Kaya n ay ang numero ng mga elemento. 35 00:01:32,790 --> 00:01:33,730 At kaya namin gawin ito madalas. 36 00:01:33,730 --> 00:01:36,650 Anumang oras na gusto naming makipag-usap tungkol sa laki sa isang problema o ang laki ng isang 37 00:01:36,650 --> 00:01:39,140 input, o ang dami ng oras na aabutin upang makabuo ng output, bibigyan namin lamang 38 00:01:39,140 --> 00:01:41,610 heneralisado anumang input ay ang bilang n. 39 00:01:41,610 --> 00:01:45,970 Kaya bumalik sa Linggo 0, bilang ng mga pahina sa aklat ng telepono ay n. 40 00:01:45,970 --> 00:01:47,550 Ang bilang ng mga mag-aaral sa kuwarto ay n. 41 00:01:47,550 --> 00:01:49,630 Kaya dito, masyadong, namin sinusubaybayan na pattern. 42 00:01:49,630 --> 00:01:52,800 >> Ngayon n squared ay hindi partikular na mabilis, kaya sinubukan naming gawin mas mahusay. 43 00:01:52,800 --> 00:01:55,970 At kaya kami ay tumingin sa isang pares ng mga iba pang mga algorithm, bukod sa kung saan 44 00:01:55,970 --> 00:01:57,690 mga seleksyon-uri. 45 00:01:57,690 --> 00:01:59,180 Kaya seleksyon-uri noon ay medyo naiiba. 46 00:01:59,180 --> 00:02:03,130 Ito ay halos mas simple, maglakas-loob ko sabihin, kung saan ako nagsimula sa simula ng 47 00:02:03,130 --> 00:02:06,740 listahan ng aming mga boluntaryo at ko lang muli at muli at muli nagpunta sa pamamagitan ng 48 00:02:06,740 --> 00:02:10,060 ang listahan, plucking out sa pinakamaliliit elemento sa isang pagkakataon at paglalagay sa kanya o 49 00:02:10,060 --> 00:02:13,040 kanya sa simula ng listahan. 50 00:02:13,040 --> 00:02:16,410 >> Ngunit ito, masyadong, sa sandaling nagsimula kaming mag-isip sa pamamagitan ng matematika at mas malalaking 51 00:02:16,410 --> 00:02:19,860 larawan, naisip tungkol sa kung gaano karaming beses Ako ay pagpunta sa likod at sa una at likod 52 00:02:19,860 --> 00:02:24,090 at balik, sinabi namin sa pinakamasama kaso, pagpili ng uri, masyadong, ay kung ano? 53 00:02:24,090 --> 00:02:24,960 n nakalapat. 54 00:02:24,960 --> 00:02:27,490 Ngayon, sa tunay na mundo, maaari itong talagang maging marginally mas mabilis. 55 00:02:27,490 --> 00:02:30,620 Dahil muli, hindi ko na kailangang panatilihing backtracking isang beses ko ay pinagsunod-sunod ang 56 00:02:30,620 --> 00:02:31,880 pinakamaliliit na elemento. 57 00:02:31,880 --> 00:02:35,090 Ngunit kung sa tingin namin tungkol sa napakalaking n, at kung iyong pag-uuri ng gawin ang matematika bilang 58 00:02:35,090 --> 00:02:39,170 Ginawa ko sa board, na may n squared minus isang bagay, lahat ng iba pa 59 00:02:39,170 --> 00:02:41,850 maliban sa n squared, sa sandaling n ay makakakuha ng talagang malaki, ay hindi 60 00:02:41,850 --> 00:02:42,850 talagang mahalaga bilang magkano. 61 00:02:42,850 --> 00:02:45,470 Kaya bilang mga siyentipiko computer, namin-uri-uriin ng pumikit ang mga mata sa mas maliit 62 00:02:45,470 --> 00:02:49,220 salik at focus lamang sa mga salik sa isang expression na pagpunta sa gumawa 63 00:02:49,220 --> 00:02:50,330 ang pinakamalaking pagkakaiba. 64 00:02:50,330 --> 00:02:52,840 >> Well, bilang wakas, kami ay tumingin pagpapasok sa pag-uuri. 65 00:02:52,840 --> 00:02:56,620 At ito ay katulad sa espiritu, ngunit sa halip na pumunta sa pamamagitan ng iteratively at 66 00:02:56,620 --> 00:03:01,250 piliin ang pinakamaliit na ang isang elemento sa isang oras, ako sa halip kinuha ang kamay na ako 67 00:03:01,250 --> 00:03:04,070 ay Aaksyunan, at ako nagpasya, lahat karapatan, pag-aari mo dito. 68 00:03:04,070 --> 00:03:06,160 Pagkatapos ko inilipat sa susunod na elemento at nagpasya na siya o 69 00:03:06,160 --> 00:03:07,470 aari niya dito. 70 00:03:07,470 --> 00:03:08,810 At pagkatapos ay ako inilipat sa at sa. 71 00:03:08,810 --> 00:03:11,780 At maaari kong, kasama ang paraan, shift ang mga guys upang 72 00:03:11,780 --> 00:03:13,030 gumawa ng room para sa mga ito. 73 00:03:13,030 --> 00:03:16,880 Kaya na noon ay isang uri ng mga sakit sa baligtad ng pagpili ng pag-uuri na namin 74 00:03:16,880 --> 00:03:18,630 tinatawag na pagpapasok sort. 75 00:03:18,630 --> 00:03:20,810 >> Kaya ang mga paksa na mangyari sa tunay na mundo. 76 00:03:20,810 --> 00:03:23,640 Ilang taon na ang nakalipas, kapag ang isang tiyak na senador ay tumatakbo para sa presidente, 77 00:03:23,640 --> 00:03:27,160 Eric Schmidt, sa panahon na ang CEO ng Google, talagang nagkaroon ng pagkakataon 78 00:03:27,160 --> 00:03:28,040 sa pakikipanayam sa kanya. 79 00:03:28,040 --> 00:03:32,010 At naisip naming ibahagi ito sa YouTube sipit para sa iyo dito, kung maaari naming i-up 80 00:03:32,010 --> 00:03:32,950 ang lakas ng tunog. 81 00:03:32,950 --> 00:03:39,360 >> [Video playback] 82 00:03:39,360 --> 00:03:44,620 >> -Ngayon, Senator, nandito ka sa Google, at gusto kong isipin na ang pagkapangulo 83 00:03:44,620 --> 00:03:46,042 bilang isang trabaho interbiyu. 84 00:03:46,042 --> 00:03:47,770 >> [Tawa] 85 00:03:47,770 --> 00:03:50,800 >> -Ngayon ay mahirap na makuha isang trabaho bilang presidente. 86 00:03:50,800 --> 00:03:52,480 At ka ng pagpunta sa pamamagitan ng ang mga kahirapan ngayon. 87 00:03:52,480 --> 00:03:54,330 Ito ay din mahirap upang makakuha ng trabaho sa Google. 88 00:03:54,330 --> 00:03:59,610 Mayroon kaming mga tanong at hinihiling namin ang aming mga kandidato tanong. 89 00:03:59,610 --> 00:04:02,250 At ang isang ito ay mula sa Larry Schwimmer. 90 00:04:02,250 --> 00:04:05,325 >> [Tawa] 91 00:04:05,325 --> 00:04:06,400 -Mo guys sa tingin ko kidding? 92 00:04:06,400 --> 00:04:08,750 Ito ay karapatan dito. 93 00:04:08,750 --> 00:04:12,110 Ano ang pinaka-mahusay na paraan upang -uri-uriin ng isang milyon dalawang-bit integer? 94 00:04:12,110 --> 00:04:15,810 >> [Tawa] 95 00:04:15,810 --> 00:04:18,260 >> -Well, uh - 96 00:04:18,260 --> 00:04:19,029 >> -I'm paumanhin. 97 00:04:19,029 --> 00:04:19,745 Siguro dapat namin - 98 00:04:19,745 --> 00:04:21,000 >> -Hindi, hindi, hindi, hindi, hindi. 99 00:04:21,000 --> 00:04:21,470 >> -Iyan ay hindi isang - 100 00:04:21,470 --> 00:04:22,185 OK. 101 00:04:22,185 --> 00:04:25,328 >> -Sa tingin ko ang bubble sort ng ginagawa maging sa maling paraan upang pumunta. 102 00:04:25,328 --> 00:04:26,792 >> [Tawa] 103 00:04:26,792 --> 00:04:28,510 >> [Pagpalakpak AT palakpakan] 104 00:04:28,510 --> 00:04:31,211 >> -Halika sa, na sinabi sa kanya ito? 105 00:04:31,211 --> 00:04:32,155 OK. 106 00:04:32,155 --> 00:04:33,350 >> [END-playback ng video] 107 00:04:33,350 --> 00:04:35,070 >> David MALAN: So doon mayroon kang ito. 108 00:04:35,070 --> 00:04:39,600 Kaya sinimulan namin upang tumyak ng dami ang mga tumatakbo beses, sa gayon na magsalita, may isang bagay 109 00:04:39,600 --> 00:04:43,480 tinatawag asymptotic notation, na kung saan ay nagre-refer lamang sa aming mga uri ng pag-on 110 00:04:43,480 --> 00:04:47,420 isang bulag mata sa mga mas maliit na mga kadahilanan at lamang ng pagtingin sa mga tumatakbo ang oras, 111 00:04:47,420 --> 00:04:51,250 ang pagganap ng mga algorithm, bilang n nakakakuha talagang malaki sa paglipas ng panahon. 112 00:04:51,250 --> 00:04:55,110 At kaya ipinakilala namin malaki O. At malaki O kinakatawan ng isang bagay na naisip namin na 113 00:04:55,110 --> 00:04:57,000 ng bilang isang pang-itaas bound. 114 00:04:57,000 --> 00:04:59,570 At talagang, Barry, maaari naming babaan kaysa sa mic Medyo? 115 00:04:59,570 --> 00:05:01,040 >> Naisip namin na ito ay isang upper bound. 116 00:05:01,040 --> 00:05:04,710 Kaya malaki O ng n squared ay nangangahulugan na sa ang pinakamasamang sitwasyon, isang bagay tulad ng 117 00:05:04,710 --> 00:05:07,780 pagpili sort gusto tumagal n squared hakbang. 118 00:05:07,780 --> 00:05:10,310 O isang bagay tulad ng pagpasok ng pag-uuri gagawin n squared hakbang. 119 00:05:10,310 --> 00:05:15,150 Ngayon para sa isang bagay tulad ng pagpapasok uri, ano ay ang pinakamasama kaso? 120 00:05:15,150 --> 00:05:18,200 Given isang array, ano ang pinakamasama posibleng sitwasyon na maaari mong makita 121 00:05:18,200 --> 00:05:20,650 iyong sarili nahaharap na may? 122 00:05:20,650 --> 00:05:21,860 >> Ito ay ganap na paurong, tama? 123 00:05:21,860 --> 00:05:24,530 Dahil kung ito ay ganap na paurong, mayroon ka na gawin ang isang buong maraming trabaho. 124 00:05:24,530 --> 00:05:26,420 Dahil kung ikaw ay ganap na paurong, ka pagpunta upang mahanap ang 125 00:05:26,420 --> 00:05:28,840 pinakamalaking elemento dito, kahit na ito ay kabilang pababa doon. 126 00:05:28,840 --> 00:05:31,140 Kaya ka pagpunta sa sabihin, ang lahat ng karapatan, sa sandaling ito sa oras, nabibilang ka dito, 127 00:05:31,140 --> 00:05:32,310 kaya mong iwanan ito nang nag-iisa. 128 00:05:32,310 --> 00:05:35,425 >> Pagkatapos ay natanto, oh, sumpain, mayroon akong upang ilipat ito bahagyang mas maliit na elemento upang 129 00:05:35,425 --> 00:05:36,470 sa kaliwa ng iyo. 130 00:05:36,470 --> 00:05:38,770 Pagkatapos ay kailangan kong gawin na muli at muli at muli. 131 00:05:38,770 --> 00:05:41,410 At kung ako lumakad na pabalik-balik, mo Gusto-uri-uriin ng pakiramdam ang pagganap ng 132 00:05:41,410 --> 00:05:45,540 algorithm na, dahil patuloy Ako shuffling ang iba pababa sa 133 00:05:45,540 --> 00:05:46,510 array upang gumawa ng room para sa mga ito. 134 00:05:46,510 --> 00:05:47,750 Kaya iyon ang pinakamasama kaso. 135 00:05:47,750 --> 00:05:48,570 >> Sa pamamagitan ng kaibahan - 136 00:05:48,570 --> 00:05:50,320 at ito ay isang cliffhanger huling beses na - 137 00:05:50,320 --> 00:05:54,065 sinabi namin na ang pagpapasok ng pag-uuri ng wakas ng ano? 138 00:05:54,065 --> 00:05:57,530 Ano ang pinakamahusay na-case na tumatakbo oras ng pagpasok ng pag-uuri? 139 00:05:57,530 --> 00:05:58,520 Kaya talaga ito n. 140 00:05:58,520 --> 00:06:00,980 Iyon ay ang blangko na iniwanan namin sa board huling oras. 141 00:06:00,980 --> 00:06:03,160 >> At ito ay katapusan ng n dahil bakit? 142 00:06:03,160 --> 00:06:06,630 Well, sa pinakamahusay na kaso, kung ano ang pagpapasok ng pag-uuri ng pagpunta sa ma-ipinasa? 143 00:06:06,630 --> 00:06:09,830 Well, isang listahan na ganap na pinagsunod-sunod pa, minimal na trabaho upang gawin. 144 00:06:09,830 --> 00:06:12,460 Ngunit kung ano ang tungkol sa malinis at maayos ang pagpapasok ng pag-uuri ay na dahil ito magsimula dito at 145 00:06:12,460 --> 00:06:15,340 Nagpasya, oh, ikaw ang numero isa, nabibilang ka dito. 146 00:06:15,340 --> 00:06:16,970 Oh, kung ano ang isang magandang kapalaran. 147 00:06:16,970 --> 00:06:17,740 >> Kayo ang dalawang numero. 148 00:06:17,740 --> 00:06:19,030 Bahagi ka rin dito. 149 00:06:19,030 --> 00:06:21,010 Numero ng tatlong, kahit na mas mahusay, nabibilang ka dito. 150 00:06:21,010 --> 00:06:25,210 Sa sandali na ito ay nakakakuha sa dulo ng pseudocode listahan, sa bawat insertion sort ni 151 00:06:25,210 --> 00:06:28,010 na namin lumakad sa pamamagitan ng pasalita huling oras, tapos na ito. 152 00:06:28,010 --> 00:06:32,790 Ngunit seleksyon uri, sa pamamagitan ng kaibahan, iningatan ginagawa kung ano? 153 00:06:32,790 --> 00:06:35,260 >> Iningatan ng pagdaan sa listahan muli at muli at muli. 154 00:06:35,260 --> 00:06:39,160 Dahil ang mga key pananaw nagkaroon lamang sa oras na iyong ay tumingin sa lahat ng mga paraan upang ang 155 00:06:39,160 --> 00:06:42,500 dulo ng listahan maaari kang maging tiyak na ang mga elemento na iyong pinili ay 156 00:06:42,500 --> 00:06:45,560 sa katunayan ang kasalukuyang pinakamaliit na elemento. 157 00:06:45,560 --> 00:06:48,920 Kaya ang mga iba't ibang mga sakit sa mga modelo ng pagtatapos up mapagpakumbaba ilang mga napaka-real-world 158 00:06:48,920 --> 00:06:53,130 mga pagkakaiba para sa amin, pati na rin ang mga manilay-nilay asymptotic pagkakaiba. 159 00:06:53,130 --> 00:06:56,910 >> Kaya lang sa paglalagom, pagkatapos, malaki O ng n squared, nakakita kami ng ilang tulad 160 00:06:56,910 --> 00:06:58,350 algorithm kaya sa ngayon. 161 00:06:58,350 --> 00:06:59,580 Big O ng n? 162 00:06:59,580 --> 00:07:02,870 Ano ang isang algorithm na maaari ay sinabi na maging malaki O ng n? 163 00:07:02,870 --> 00:07:06,930 Sa pinakamasama kaso, ito ay tumatagal ng isang linear na bilang ng mga hakbang na ito. 164 00:07:06,930 --> 00:07:07,810 >> OK, linear paghahanap. 165 00:07:07,810 --> 00:07:10,470 At sa pinakamasama kaso, kung saan ay ang element na hinahanap mo kapag 166 00:07:10,470 --> 00:07:12,950 paglalapat ng linear paghahanap? 167 00:07:12,950 --> 00:07:14,680 >> OK, sa pinakamasama kaso, ito ay hindi kahit doon. 168 00:07:14,680 --> 00:07:17,000 O kaya sa pangalawang pinakamasama kaso, ito ay ang lahat ng mga paraan sa dulo, na kung saan ay 169 00:07:17,000 --> 00:07:18,880 plus-o-minus isang hakbang pagkakaiba. 170 00:07:18,880 --> 00:07:21,180 Kaya sa katapusan ng araw, maaari naming sabihin ito ay linear. 171 00:07:21,180 --> 00:07:23,910 Big O ng n magiging linear paghahanap, dahil sa ang pinakamasama kaso, ang 172 00:07:23,910 --> 00:07:26,610 elemento ay hindi kahit doon o ito ang lahat ng mga paraan sa dulo. 173 00:07:26,610 --> 00:07:29,370 >> Well, malaki O ng log ng n. 174 00:07:29,370 --> 00:07:32,760 Hindi namin makipag-usap sa mahusay na detalye tungkol sa ito, ngunit nasaksihan namin ito bago. 175 00:07:32,760 --> 00:07:36,840 Ano ang tumatakbo sa tinaguriang logarithmic oras, sa pinakamasama kaso? 176 00:07:36,840 --> 00:07:38,500 >> Oo, kaya binary paghahanap. 177 00:07:38,500 --> 00:07:42,930 At binary paghahanap sa pinakamasama kaso Maaaring magkaroon ang elemento sa isang lugar sa 178 00:07:42,930 --> 00:07:45,640 sa gitna, o sa isang lugar sa loob ng array. 179 00:07:45,640 --> 00:07:48,040 Ngunit mo lamang makita ito sa sandaling hatiin ang listahan sa kalahati, sa 180 00:07:48,040 --> 00:07:48,940 kalahati, sa kalahati, sa kalahati. 181 00:07:48,940 --> 00:07:50,200 At pagkatapos ay voila, ito ay doon. 182 00:07:50,200 --> 00:07:52,500 O muli, pinakamasama kaso, ito ay hindi kahit doon. 183 00:07:52,500 --> 00:07:56,770 Ngunit hindi mo alam na ito ay hindi doon hanggang sa ikaw ay isang uri ng maabot na ang huling 184 00:07:56,770 --> 00:08:00,470 ibabang pinaka elemento sa pamamagitan ng paghati at paghati at paghati. 185 00:08:00,470 --> 00:08:01,400 >> Big O ng 1. 186 00:08:01,400 --> 00:08:03,540 Kaya maaari naming malaki ng O 2, malaki O ng 3. 187 00:08:03,540 --> 00:08:06,260 Anumang oras na gusto mo lamang ng isang hindi nagbabagong numero, namin lamang-uri-uriin ng lang gawing simple 188 00:08:06,260 --> 00:08:07,280 na malaki ang bilang ng mga O 1. 189 00:08:07,280 --> 00:08:10,440 Kahit na kung realistically, ito ay tumatagal ng 2 o kahit na 100 mga hakbang, kung ito ay isang 190 00:08:10,440 --> 00:08:13,680 pare-pareho ang bilang ng mga hakbang, kami lang sabihin malaki O ng 1. 191 00:08:13,680 --> 00:08:15,930 Ano ang isang algorithm na sa malaki O ng 1? 192 00:08:15,930 --> 00:08:18,350 >> Madla: Paghahanap ng ang haba ng isang variable. 193 00:08:18,350 --> 00:08:21,090 >> David MALAN: Hinahanap ang haba ng isang variable? 194 00:08:21,090 --> 00:08:23,870 >> Madla: Hindi, ang haba kung ito ay pinagsunod-sunod. 195 00:08:23,870 --> 00:08:24,160 >> David MALAN: Mahusay. 196 00:08:24,160 --> 00:08:27,850 OK, kaya sa paghahanap ng haba ng isang bagay kung ang haba ng na may isang bagay, tulad ng 197 00:08:27,850 --> 00:08:30,020 isang array, ay naka-imbak sa ilang mga variable. 198 00:08:30,020 --> 00:08:33,380 Dahil maaari mo lamang basahin ang mga variable, o i-print ang variable, o 199 00:08:33,380 --> 00:08:34,960 lamang sa pangkalahatan access na variable. 200 00:08:34,960 --> 00:08:37,299 At voila, na tumatagal ng pare-pareho ang panahon. 201 00:08:37,299 --> 00:08:38,909 >> Sa pamamagitan ng kaibahan, sa tingin bumalik sa simula. 202 00:08:38,909 --> 00:08:42,460 Isipin pabalik sa unang linggo ng C, pagtawag lamang printf at pag-print 203 00:08:42,460 --> 00:08:46,240 isang bagay sa screen ay arguably pare-pareho ang panahon, dahil ito lamang tumatagal 204 00:08:46,240 --> 00:08:50,880 ilang bilang ng mga siklo ng CPU upang ipakita ang na teksto sa screen. 205 00:08:50,880 --> 00:08:52,720 O kaya maghintay - ang ibig ito? 206 00:08:52,720 --> 00:08:56,430 Paano pa ang maaari naming gawing modelo ang pagganap ng printf? 207 00:08:56,430 --> 00:09:00,420 Gusto isang tao na gusto upang hindi sumang-ayon, na marahil ito ay hindi talaga pare-pareho ang oras? 208 00:09:00,420 --> 00:09:03,600 Sa anong kahulugan ay maaaring printf Tumatakbo oras, talagang pag-print ng isang string sa 209 00:09:03,600 --> 00:09:05,580 ang screen, maging isang bagay bukod sa pare-pareho. 210 00:09:05,580 --> 00:09:07,860 >> Madla: [hindi marinig]. 211 00:09:07,860 --> 00:09:08,230 >> David MALAN: Oo. 212 00:09:08,230 --> 00:09:09,300 Kaya ito ay depende sa aming pananaw. 213 00:09:09,300 --> 00:09:13,390 Kung namin ang aktwal na sa tingin ng mga input upang printf bilang pagiging string, at 214 00:09:13,390 --> 00:09:16,380 samakatuwid namin sinusukat ang laki ng mga na input sa pamamagitan ng haba nito - kaya natin tawagan 215 00:09:16,380 --> 00:09:17,780 na haba n pati na rin - 216 00:09:17,780 --> 00:09:21,990 arguably, printf mismo ay malaki O ng n dahil ito ay pagpunta sa magdadala sa iyo n hakbang 217 00:09:21,990 --> 00:09:24,750 upang i-print out sa bawat isa sa mga n character, pinaka-malamang. 218 00:09:24,750 --> 00:09:27,730 Hindi bababa sa lawak na ipinapalagay namin na siguro gumagamit ito ng para sa loop 219 00:09:27,730 --> 00:09:28,560 sa ilalim ng hood. 220 00:09:28,560 --> 00:09:30,860 >> Pero gusto naming magkaroon upang tumingin sa na code upang maunawaan itong mas mahusay. 221 00:09:30,860 --> 00:09:33,650 At sa katunayan, sa sandaling simulan guys pag-aaral ng iyong sariling mga algorithm, makikita mo 222 00:09:33,650 --> 00:09:34,900 Literal na gawin lamang na. 223 00:09:34,900 --> 00:09:37,765 Pagsunud-sunurin ng eyeball ang iyong code at sa tingin tungkol - lahat ng mga karapatan, mayroon akong ito loop 224 00:09:37,765 --> 00:09:41,870 dito o ba akong magkaroon ng isang nested loop dito, na pagpunta sa gawin ang mga bagay n n beses, 225 00:09:41,870 --> 00:09:46,050 at maaari mong uri-uriin ang dahilan ng iyong paraan sa pamamagitan ng code, kahit na ito ay 226 00:09:46,050 --> 00:09:47,980 pseudocode at hindi aktwal na code. 227 00:09:47,980 --> 00:09:49,730 >> Kaya kung ano ang tungkol sa katapusan ng n squared? 228 00:09:49,730 --> 00:09:53,582 Ano ang isang algorithm na sa ang pinakamahusay na kaso, kinuha pa rin n squared hakbang? 229 00:09:53,582 --> 00:09:54,014 Oo? 230 00:09:54,014 --> 00:09:54,880 >> Madla: [hindi marinig]. 231 00:09:54,880 --> 00:09:55,900 >> David MALAN: Kaya seleksyon-uri. 232 00:09:55,900 --> 00:09:59,150 Dahil sa problema na talagang binawasan upang ang katotohanan na muli, hindi ko alam 233 00:09:59,150 --> 00:10:02,600 Nahanap ko ang kasalukuyang pinakamaliit hanggang Ko na naka-check ang lahat ng mga elemento darn. 234 00:10:02,600 --> 00:10:08,050 Kaya wakas ng, sabihin nating, n, namin lamang ay dumating up sa isa. 235 00:10:08,050 --> 00:10:09,300 Insertion sort. 236 00:10:09,300 --> 00:10:12,370 Kung listahan ang mangyayari na pinagsunod-sunod pa, sa ang pinakamahusay na kaso namin na lang ay 237 00:10:12,370 --> 00:10:15,090 upang gumawa ng isang pass sa pamamagitan nito, at sa puntong sigurado kami. 238 00:10:15,090 --> 00:10:17,890 At pagkatapos na ma-sinabi upang maging linear, para sigurado. 239 00:10:17,890 --> 00:10:20,570 >> Paano ang tungkol sa wakas ng 1? 240 00:10:20,570 --> 00:10:23,790 Ano, sa ang pinakamahusay na kaso, maaaring tumagal isang pare-pareho ang bilang ng mga hakbang na ito? 241 00:10:23,790 --> 00:10:27,220 Kaya linear paghahanap, kung mo lamang makakuha ng masuwerteng at ang sangkap na hinahanap mo 242 00:10:27,220 --> 00:10:31,000 ang tama sa simula ng listahan, kung na kung saan ka pagsisimula ng iyong 243 00:10:31,000 --> 00:10:33,070 linear traversal ng listahang iyon. 244 00:10:33,070 --> 00:10:35,180 >> At ito ay totoo ng isang bilang ng mga bagay. 245 00:10:35,180 --> 00:10:37,660 Halimbawa, kahit na binary paghahanap ay wakas na 1. 246 00:10:37,660 --> 00:10:40,310 Dahil kung ano ang kung makakuha ka talaga darn mapalad at may bakas-magdutdot sa gitna ng 247 00:10:40,310 --> 00:10:42,950 ang iyong array ay ang bilang ang iyong hinahanap para sa? 248 00:10:42,950 --> 00:10:45,730 Kaya maaari kang makakuha ng masuwerteng doon, pati na rin. 249 00:10:45,730 --> 00:10:49,190 >> Ito ang isa, bilang wakas, wakas ng n log n. 250 00:10:49,190 --> 00:10:52,573 Kaya n log n, ginawa namin hindi talaga makipag-usap tungkol sa pa, ngunit - 251 00:10:52,573 --> 00:10:53,300 >> Madla: Pagsamahin-uri? 252 00:10:53,300 --> 00:10:53,960 >> David MALAN: Pagsamahin ang pag-uuri. 253 00:10:53,960 --> 00:10:56,920 Iyon ay ang cliffhanger ng huling oras, kung saan kami ipinanukala, at kami ay nagpakita ng 254 00:10:56,920 --> 00:10:58,600 biswal, na may mga algorithm. 255 00:10:58,600 --> 00:11:02,470 At pagsamahin ang uri ng isa lang gaya algorithm na ay mas mabilis sa panimula 256 00:11:02,470 --> 00:11:03,450 kaysa sa ilang ng iba pang mga guys. 257 00:11:03,450 --> 00:11:07,800 Sa katunayan, pagsamahin maikling ay hindi lamang sa pinakamahusay na kaso n log n, sa pinakamalala 258 00:11:07,800 --> 00:11:09,460 kaso n log n. 259 00:11:09,460 --> 00:11:14,540 At kapag mayroon kang ito ng pagkakaisa wakas at malaki O pagiging ang parehong bagay? 260 00:11:14,540 --> 00:11:17,310 Maaari naming ilarawan ang aktwal na bilang kung ano ang tinatawag theta, bagaman ito ay isang 261 00:11:17,310 --> 00:11:18,220 maliit na mas mababa karaniwang. 262 00:11:18,220 --> 00:11:21,730 Ngunit iyon lamang ay nangangahulugan na ang dalawang hanggahan, sa kasong ito, ay pareho. 263 00:11:21,730 --> 00:11:25,770 >> Kaya pagsamahin ang uri, kung ano ang ibig ito talaga pasingawan sa para sa amin? 264 00:11:25,770 --> 00:11:27,000 Well, isipin ang mga pagganyak. 265 00:11:27,000 --> 00:11:30,340 Hayaan akong makuha ang isa pang animation na hindi kami tumingin sa huling beses. 266 00:11:30,340 --> 00:11:33,390 Ang isa, parehong ideya, ngunit ito ay isang maliit na mas malaki. 267 00:11:33,390 --> 00:11:36,160 At ako pagpunta sa sige at ituro una - kami ay may pagpapasok-uri sa 268 00:11:36,160 --> 00:11:39,410 sa tuktok na kaliwang, pagkatapos ay pagpili ng uri, bubble sort, isang pares ng mga iba pang mga uri - 269 00:11:39,410 --> 00:11:42,670 shell at mabilis - na hindi namin na-uusapang tungkol sa, at kimpal at pagsamahin ang pag-uuri. 270 00:11:42,670 --> 00:11:47,090 >> Kaya hindi bababa sa subukan upang ituon ang iyong mga mata sa ang tatlong nangungunang sa kaliwa at pagkatapos ay 271 00:11:47,090 --> 00:11:49,120 merge sort kapag i-click ko ang berdeng arrow. 272 00:11:49,120 --> 00:11:51,900 Ngunit Ipapaalam ko sa lahat ng mga ito tatakbo, para lamang bigyan ka ng isang pakiramdam ng pagkakaroon ng mga pagkakaiba-iba ng 273 00:11:51,900 --> 00:11:53,980 algorithm na umiiral sa mundo. 274 00:11:53,980 --> 00:11:56,180 Pupunta ako upang ipaalam ito run para lamang ng ilang segundo. 275 00:11:56,180 --> 00:11:59,640 At kung mong ituon ang iyong mga mata - pumili ng isang algorithm, tumuon sa mga ito para lamang sa isang 276 00:11:59,640 --> 00:12:02,970 segundo - magkakaroon ka magsimula upang makita ang pattern na ito pagpapatupad. 277 00:12:02,970 --> 00:12:04,530 >> Pagsamahin ang mga pag-uuri, notice, tapos na. 278 00:12:04,530 --> 00:12:06,430 Kimpal sort, quick sort, shell - 279 00:12:06,430 --> 00:12:09,480 kaya mukhang ipinakilala namin ang tatlong pinakamasama algorithm noong nakaraang linggo. 280 00:12:09,480 --> 00:12:12,960 Ngunit iyon lamang ang mahusay na kami dito ngayon sa tumingin sa pagsasama-uri, na kung saan ay isa sa mga 281 00:12:12,960 --> 00:12:16,500 mas madali ang mga bago ay ang pagtingin sa, kahit na bagaman marahil ito ay yumuko iyong isip 282 00:12:16,500 --> 00:12:17,490 lamang ng isang maliit na bit. 283 00:12:17,490 --> 00:12:21,130 Dito maaari naming makita lamang kung magkano pagpili sort sucks. 284 00:12:21,130 --> 00:12:24,600 >> Ngunit sa gilid tingnan ito, talaga madaling ipatupad. 285 00:12:24,600 --> 00:12:28,160 At marahil para sa P Set 3, na isa sa mga algorithm na pinili mo upang ipatupad 286 00:12:28,160 --> 00:12:28,960 para sa standard edition. 287 00:12:28,960 --> 00:12:30,970 Ganap na ganap fine, perpektong tama. 288 00:12:30,970 --> 00:12:35,210 >> Ngunit muli, bilang n nakukuha ng malaki, kung ikaw pumili upang ipatupad ng mas mabilis na algorithm 289 00:12:35,210 --> 00:12:39,020 i-merge sort, bentahe sa mga mas malaki at mas malaki input, ang iyong code lamang ang 290 00:12:39,020 --> 00:12:39,800 pagpunta upang tumakbo nang mas mabilis. 291 00:12:39,800 --> 00:12:41,090 Ang iyong website ay pagpunta upang gumana nang mas mahusay. 292 00:12:41,090 --> 00:12:42,650 Ang iyong mga gumagamit ay pumunta sa upang maging mas masaya. 293 00:12:42,650 --> 00:12:45,280 At kaya mayroong mga effect ng aktwal na nagbibigay sa 294 00:12:45,280 --> 00:12:47,350 sa amin ng ilang mas malalim na inisip. 295 00:12:47,350 --> 00:12:49,990 >> Kaya sabihin tumingin sa kung ano sumanib -uri ay talagang lahat tungkol sa. 296 00:12:49,990 --> 00:12:52,992 Ang mga cool na bagay ay na-merge sort lamang ito. 297 00:12:52,992 --> 00:12:56,300 Ito ay, muli, kung ano ang namin ang tinatawag na pseudocode, pseudocode pagkatao 298 00:12:56,300 --> 00:12:57,720 Ingles-tulad ng syntax. 299 00:12:57,720 --> 00:12:59,890 At ang pagiging simple ay uri ng mga kamangha-manghang. 300 00:12:59,890 --> 00:13:02,840 >> Kaya sa pag-input ng mga elemento n - sa gayon ay Nangangahulugan lamang, narito ang isang array. 301 00:13:02,840 --> 00:13:04,000 Ito ay nakuha ko n bagay sa loob nito. 302 00:13:04,000 --> 00:13:05,370 Iyon lang namin sinasabi na doon. 303 00:13:05,370 --> 00:13:07,560 >> Kung n Mababa sa 2, bumalik. 304 00:13:07,560 --> 00:13:08,640 Kaya ito lamang ang walang kuwenta kaso. 305 00:13:08,640 --> 00:13:12,580 Kung n Mababa sa 2, pagkatapos ay malinaw naman ito 1 o 0, kung saan ang mga bagay 306 00:13:12,580 --> 00:13:14,780 ay pinagsunod-sunod o nonexistent, kaya lang bumalik. 307 00:13:14,780 --> 00:13:15,900 Wala na gawin. 308 00:13:15,900 --> 00:13:18,360 Kaya na ang isang simpleng kaso sa pumitas off. 309 00:13:18,360 --> 00:13:20,110 >> Iba Pa, mayroon kaming tatlong hakbang. 310 00:13:20,110 --> 00:13:23,650 Pagbukud-bukurin sa kaliwang kalahati ng mga elemento, pag-uuri ang karapatan kalahati ng mga elemento, 311 00:13:23,650 --> 00:13:26,650 at pagkatapos ay pagsamahin ang pinagsunod-sunod halves. 312 00:13:26,650 --> 00:13:29,400 Ano ang mga kagiliw-giliw dito ay na Ako uri ng punting, tama? 313 00:13:29,400 --> 00:13:32,300 Mayroong uri ng isang pabilog na kahulugan upang ito algorithm. 314 00:13:32,300 --> 00:13:35,986 Sa anong kahulugan ay ang algorithm ni Kahulugan ng pabilog? 315 00:13:35,986 --> 00:13:37,850 >> Madla: [hindi marinig]. 316 00:13:37,850 --> 00:13:41,670 >> David MALAN: Oo, ang aking mga pag-uuri algorithm, dalawa sa kanyang mga hakbang ay ang "pag-uuri 317 00:13:41,670 --> 00:13:44,640 isang bagay. "At kaya na begs ang pinag-uusapan, well, kung ano ako pagpunta sa gamitin 318 00:13:44,640 --> 00:13:46,460 upang pagbukud-bukurin ang kaliwang kalahati at ang kanang kalahati? 319 00:13:46,460 --> 00:13:49,600 At ang kagandahan dito ay na kahit na muli, ito ang isip-baluktot 320 00:13:49,600 --> 00:13:54,030 bahagi potensyal na, maaari mong gamitin ang parehong algorithm upang pagbukud-bukurin ang kaliwang kalahati. 321 00:13:54,030 --> 00:13:54,700 >> Ngunit maghintay ng isang minuto. 322 00:13:54,700 --> 00:13:57,070 Kapag naka-Sinabi upang ayusin ang kaliwa kalahati, kung ano ay ang dalawang 323 00:13:57,070 --> 00:13:58,240 hakbang ng pagpunta sa maging susunod? 324 00:13:58,240 --> 00:14:00,550 Kami uri-uriin ang kaliwang kalahati ng kaliwa kalahati at ang karapatan 325 00:14:00,550 --> 00:14:01,420 kalahati ng kaliwang kalahati. 326 00:14:01,420 --> 00:14:04,430 Sumpain, paano ko uri-uriin ang mga dalawang halves, o quarters, ngayon? 327 00:14:04,430 --> 00:14:05,260 >> Ngunit iyon lamang ang OK. 328 00:14:05,260 --> 00:14:07,830 Mayroon kaming isang pag-uuri algorithm dito. 329 00:14:07,830 --> 00:14:10,660 At kahit na maaari kang mag-alala sa unang ito ay uri ng isang walang-katapusang 330 00:14:10,660 --> 00:14:12,780 loop, ito ay isang cycle na hindi kailanman pagpunta sa tapusin - ito ay pagpunta sa 331 00:14:12,780 --> 00:14:15,770 tapusin beses kung ano ang mangyayari? 332 00:14:15,770 --> 00:14:16,970 Sa sandaling n ay mas mababa kaysa 2. 333 00:14:16,970 --> 00:14:19,180 Aling kalaunan ay pagpunta sa mangyari, dahil kung patuloy mong paghati at 334 00:14:19,180 --> 00:14:23,020 paghati sa paghati mga halves, tiyak malaon ka ng pagpunta sa magtapos 335 00:14:23,020 --> 00:14:25,350 up na may lamang 1 o 0 na mga elemento. 336 00:14:25,350 --> 00:14:28,500 Sa aling mga punto, ito algorithm sabi tapos ka na. 337 00:14:28,500 --> 00:14:31,020 >> Kaya ang tunay na magic sa ito algorithm ay anyong sa 338 00:14:31,020 --> 00:14:33,470 na huling hakbang, pinagsasama. 339 00:14:33,470 --> 00:14:37,190 Iyon simpleng ideya lamang pinagsasama ang dalawang mga bagay, na kung ano ang pagpunta sa huli 340 00:14:37,190 --> 00:14:40,920 upang payagan sa amin upang ayusin ang isang array ng, sabihin nating, walong elemento. 341 00:14:40,920 --> 00:14:44,410 Kaya Mayroon akong walong higit pang mga bola ng stress up dito, walong piraso ng papel, at isa 342 00:14:44,410 --> 00:14:45,500 Google Salamin - 343 00:14:45,500 --> 00:14:46,140 na nakukuha ko upang panatilihing. 344 00:14:46,140 --> 00:14:46,960 >> [Tawa] 345 00:14:46,960 --> 00:14:48,970 >> David MALAN: Kung kami maaaring tumagal ng walong boluntaryo, at sabihin makita kung ang aming makakaya 346 00:14:48,970 --> 00:14:51,430 maglaro ito out, nang sa gayon. 347 00:14:51,430 --> 00:14:52,500 Wow, OK. 348 00:14:52,500 --> 00:14:53,565 Computer science ay nakakakuha ng masaya. 349 00:14:53,565 --> 00:14:54,320 Ayos lang. 350 00:14:54,320 --> 00:14:57,770 Kaya kung paano tungkol sa iyo tatlo, pinakamalaking kamay up doon. 351 00:14:57,770 --> 00:14:58,580 Apat sa likod. 352 00:14:58,580 --> 00:15:02,220 At kung paano tungkol sa gagawin namin sa iyo tatlong sa hilerang ito? 353 00:15:02,220 --> 00:15:03,390 At apat na nasa harap. 354 00:15:03,390 --> 00:15:04,920 Kaya mo walo, dumating sa up. 355 00:15:04,920 --> 00:15:12,060 >> [Tawa] 356 00:15:12,060 --> 00:15:13,450 >> David MALAN: Ako talaga Hindi sigurado kung ano ito ay. 357 00:15:13,450 --> 00:15:14,810 Ito ba ay ang bola ng stress? 358 00:15:14,810 --> 00:15:16,510 Ang desk lamp? 359 00:15:16,510 --> 00:15:18,650 Ang materyal? 360 00:15:18,650 --> 00:15:19,680 Ang internet? 361 00:15:19,680 --> 00:15:20,160 >> OK. 362 00:15:20,160 --> 00:15:21,310 Kaya dumating sa up. 363 00:15:21,310 --> 00:15:22,310 Sino ang nais - 364 00:15:22,310 --> 00:15:23,570 panatilihing darating up. 365 00:15:23,570 --> 00:15:24,240 Tayo'y makita. 366 00:15:24,240 --> 00:15:26,460 At ito Binibigyan ka ng lokasyon - 367 00:15:26,460 --> 00:15:27,940 ikaw ay nasa isang lokasyon. 368 00:15:27,940 --> 00:15:28,670 Uh-oh, maghintay ng isang minuto. 369 00:15:28,670 --> 00:15:30,760 1, 2, 3, 4, 5, 6, 7 - oh, mabuti. 370 00:15:30,760 --> 00:15:31,310 Ang lahat ng mga karapatan, kami ay mabuti. 371 00:15:31,310 --> 00:15:35,130 Ang lahat ng mga karapatan, kaya lahat ng tao ay may isang upuan, ngunit hindi sa Google Glass. 372 00:15:35,130 --> 00:15:36,475 Hayaan akong i-queue ang mga up. 373 00:15:36,475 --> 00:15:37,115 Ano ang inyong pangalan? 374 00:15:37,115 --> 00:15:37,440 >> Michelle: Michelle. 375 00:15:37,440 --> 00:15:38,090 >> David MALAN: Michelle? 376 00:15:38,090 --> 00:15:42,000 Ang lahat ng mga karapatan, nakarating ka na sa hitsura ang geek, kung iyon ang OK. 377 00:15:42,000 --> 00:15:44,625 Well, gawin ko masyadong, ipagpalagay ko, para lamang ng ilang sandali. 378 00:15:44,625 --> 00:15:45,875 Ang lahat ng mga karapatan, standby. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Kami ay sinusubukan upang makabuo ng isang gamitin ang kaso para sa Google Glass, at kami 381 00:15:50,950 --> 00:15:53,750 naisip magiging masaya na lang gawin ito kapag ang mga tao onstage. 382 00:15:53,750 --> 00:15:57,120 Itatala namin ang mundo mula sa kanilang mga pananaw. 383 00:15:57,120 --> 00:15:58,410 Ayos lang. 384 00:15:58,410 --> 00:15:59,830 Hindi marahil kung ano ang inilaan ng Google. 385 00:15:59,830 --> 00:16:02,260 Ang lahat ng mga karapatan, kung hindi tututol kayo suot ito para sa susunod na nakahihiya minuto, 386 00:16:02,260 --> 00:16:03,150 na magiging kahanga-hanga. 387 00:16:03,150 --> 00:16:08,620 >> Ang lahat ng mga karapatan, kaya't mayroon kaming dito ng isang hanay ng mga mga sangkap, at na array, bilang bawat ang 388 00:16:08,620 --> 00:16:11,480 piraso ng papel sa mga tao ' mga kamay, ay kasalukuyang unsorted. 389 00:16:11,480 --> 00:16:12,050 >> Michelle: Oh, syanga kakaiba. 390 00:16:12,050 --> 00:16:12,810 >> David MALAN: Ito ay medyo magkano ang random. 391 00:16:12,810 --> 00:16:15,760 At sa loob lamang ng isang sandali, kami ay pagpunta sa subukan ipatupad ang pagsamahin-uri-sama 392 00:16:15,760 --> 00:16:17,950 at makita kung saan na key pananaw ay. 393 00:16:17,950 --> 00:16:21,970 At ang kahanga-hangang gawa dito na may sumanib-uri ay isang bagay na hindi pa namin ipinapalagay pa. 394 00:16:21,970 --> 00:16:24,030 Kami talagang kailangan ang ilang mga dagdag na espasyo. 395 00:16:24,030 --> 00:16:26,650 Kaya kung ano ang nangyayari upang maging partikular na kagiliw-giliw na tungkol sa ito ay na ang mga 396 00:16:26,650 --> 00:16:29,270 guys ay pagpunta sa ilipat sa paligid ng kaunti bit, dahil ako pagpunta sa ipagpalagay na ang 397 00:16:29,270 --> 00:16:31,880 mayroong isang dagdag na hanay ng mga espasyo, sabihin, karapatan sa likod ng mga ito. 398 00:16:31,880 --> 00:16:34,570 >> Kaya kung ang mga ito ay sa likod ng kanilang mga upuan, iyon ang pangalawang array. 399 00:16:34,570 --> 00:16:36,960 Kung sila ay nakaupo dito, na ang pangunahing array. 400 00:16:36,960 --> 00:16:40,170 Ngunit ito ay isang mapagkukunan na mayroon kami Hindi magagamit sa ngayon kaya may bubble 401 00:16:40,170 --> 00:16:42,040 uri, na may pagpili-uri, may pagpapasok ng pag-uuri. 402 00:16:42,040 --> 00:16:44,600 Isipin ang nakaraang linggo, lahat ng tao lamang uri ng shuffled sa lugar. 403 00:16:44,600 --> 00:16:46,840 Hindi nila gamitin ang anumang karagdagang memorya. 404 00:16:46,840 --> 00:16:49,310 Ginawa namin room para sa mga tao sa pamamagitan ng paglipat ng mga tao sa paligid. 405 00:16:49,310 --> 00:16:50,580 >> Kaya ito ay isang mahalagang pananaw, masyadong. 406 00:16:50,580 --> 00:16:53,410 Mayroong ito kalakalan-off, sa pangkalahatan sa computer science, ng mga mapagkukunan. 407 00:16:53,410 --> 00:16:55,800 Kung nais mong pabilisin ang isang bagay tulad ng oras, ikaw ay pagpunta sa 408 00:16:55,800 --> 00:16:56,900 kailangang magbayad ng isang presyo. 409 00:16:56,900 --> 00:17:00,750 At ang isa sa mga presyo ay napakadalas espasyo, ang halaga ng memorya o hard 410 00:17:00,750 --> 00:17:01,700 puwang sa disk na ginagamit mo. 411 00:17:01,700 --> 00:17:03,640 O kaya naman, lantaran, ang halaga programmer ng oras. 412 00:17:03,640 --> 00:17:06,700 Gaano karaming oras na aabutin mo, ang tao, upang aktwal na ipatupad ang ilang higit pang mga 413 00:17:06,700 --> 00:17:07,829 kumplikadong mga algorithm. 414 00:17:07,829 --> 00:17:09,760 Ngunit para sa ngayon, ang kalakalan-off ay oras at espasyo. 415 00:17:09,760 --> 00:17:11,930 >> Kaya't kung ikaw guys ay maaaring hawakan lamang up ang iyong mga numero upang maaari naming makita na ikaw ay 416 00:17:11,930 --> 00:17:15,839 sa katunayan na tumutugma sa 4, 2, 6, 1, 3, 7, 8. 417 00:17:15,839 --> 00:17:16,599 Magaling. 418 00:17:16,599 --> 00:17:19,520 Kaya ako ng pagpunta sa subukan upang mamigay bagay, kung maaari guys lamang 419 00:17:19,520 --> 00:17:21,800 sundin ang aking mga nangunguna dito. 420 00:17:21,800 --> 00:17:26,650 >> Kaya ako ng pagpunta sa ipatupad, una, ang unang hakbang ng pseudocode, na siyang 421 00:17:26,650 --> 00:17:29,440 sa input ng n elemento, kung n ay Mababa sa 2, pagkatapos ay bumalik. 422 00:17:29,440 --> 00:17:31,370 Malinaw, na ang hindi Ilapat, kaya kami umusad. 423 00:17:31,370 --> 00:17:33,340 Kaya-uri-uriin ang kaliwang kalahati ng mga elemento. 424 00:17:33,340 --> 00:17:36,220 Kaya ito ay nangangahulugan na pupuntahan ko ang aking pokus pansin para sa sandali lamang sa mga 425 00:17:36,220 --> 00:17:37,310 apat na guys dito. 426 00:17:37,310 --> 00:17:39,774 Ang lahat ng mga karapatan, ano ang gagawin ko susunod na gagawin? 427 00:17:39,774 --> 00:17:40,570 >> Madla: Pagbukud-bukurin sa kaliwa kalahati. 428 00:17:40,570 --> 00:17:42,780 >> David MALAN: Kaya ngayon mayroon akong upang pagsunud-sunurin sa kaliwang kalahati ng mga guys. 429 00:17:42,780 --> 00:17:45,580 Dahil muli, ipagpalagay na ang iyong sarili layunin ay upang ayusin ang kaliwang kalahati. 430 00:17:45,580 --> 00:17:46,440 Paano mo gawin iyon? 431 00:17:46,440 --> 00:17:49,140 Sundin lamang ang mga tagubilin, kahit kahit na ginagawa namin itong muli. 432 00:17:49,140 --> 00:17:50,160 Kaya-uri-uriin ang kaliwang kalahati. 433 00:17:50,160 --> 00:17:52,030 Ngayon ako ng pagbubukod-bukod ng mga dalawang guys. 434 00:17:52,030 --> 00:17:53,563 Ano ay susunod? 435 00:17:53,563 --> 00:17:54,510 >> Madla: Pagbukud-bukurin sa kaliwa kalahati. 436 00:17:54,510 --> 00:17:55,460 >> David MALAN: Pagbukud-bukurin sa kaliwa kalahati. 437 00:17:55,460 --> 00:18:00,680 Kaya ngayon ang mga ito, ito upuan dito, ay isang listahan ng sukat 1. 438 00:18:00,680 --> 00:18:01,365 At kung ano ang iyong pangalan muli? 439 00:18:01,365 --> 00:18:02,390 >> Uri ng bulaklak Princess: Princess Daisy. 440 00:18:02,390 --> 00:18:03,690 >> David MALAN: Princess Daisy ay dito. 441 00:18:03,690 --> 00:18:07,470 At kaya na siya ay pinagsunod-sunod, dahil listahan ay ang laki ng 1. 442 00:18:07,470 --> 00:18:09,490 Ano ang gagawin ko susunod na gagawin? 443 00:18:09,490 --> 00:18:13,680 OK, bumalik, dahil listahan na ng 1 laki, na kung saan ay mas mababa kaysa 2. 444 00:18:13,680 --> 00:18:14,320 Pagkatapos ay kung ano ang susunod na hakbang? 445 00:18:14,320 --> 00:18:17,490 At ngayon ikaw ay may sa uri ng pag-urong sa iyong isip. 446 00:18:17,490 --> 00:18:19,340 >> Pagbukud-bukurin ang karapatan kalahati, na kung saan ay - 447 00:18:19,340 --> 00:18:19,570 ano ang pangalan mo? 448 00:18:19,570 --> 00:18:20,220 >> Linda: Linda. 449 00:18:20,220 --> 00:18:20,980 >> David MALAN: Linda. 450 00:18:20,980 --> 00:18:23,210 At kaya kung ano ang gagawin namin ngayon na kami ay may isang listahan ng mga laki 1? 451 00:18:23,210 --> 00:18:24,440 >> Madla: Return. 452 00:18:24,440 --> 00:18:24,760 >> David MALAN: ingat. 453 00:18:24,760 --> 00:18:29,540 Ibalik namin ang una, at ngayon ang ikatlong hakbang - at kung ako uri ng ilarawan ito sa pamamagitan ng 454 00:18:29,540 --> 00:18:33,490 embracing ang dalawang upuan ngayon, ngayon ako mayroon upang pagsamahin ang dalawang mga elemento. 455 00:18:33,490 --> 00:18:35,530 Kaya ngayon sa kasamaang-palad, ang mga elemento ay sira. 456 00:18:35,530 --> 00:18:39,920 Ngunit iyon kung saan ang proseso ng pagbubuklod nagsisimula upang makakuha ng nakahihimok. 457 00:18:39,920 --> 00:18:42,410 >> Kaya't kung ikaw guys maaaring tumayo para lang isang saglit, pupuntahan ko kailangan mo, sa isang 458 00:18:42,410 --> 00:18:44,170 sandali, sa hakbang sa likod ng iyong upuan. 459 00:18:44,170 --> 00:18:46,480 At kung Linda, dahil 2 ay mas maliit sa 4, bakit hindi gawin 460 00:18:46,480 --> 00:18:48,130 dumating ka sa paligid muna? 461 00:18:48,130 --> 00:18:48,690 Manatili doon. 462 00:18:48,690 --> 00:18:50,520 Kaya Linda, dumating ka sa paligid muna. 463 00:18:50,520 --> 00:18:53,820 >> Ngayon sa katotohanan kung ito lamang ay isang array kami maaaring lamang ilipat ang kanyang sa real time 464 00:18:53,820 --> 00:18:55,360 mula sa upuan sa lugar na ito. 465 00:18:55,360 --> 00:18:57,770 Kaya isipin na tumagal ng ilang mga pare-pareho bilang ng mga hakbang 1. 466 00:18:57,770 --> 00:18:58,480 At ngayon - 467 00:18:58,480 --> 00:19:01,490 ngunit kailangan naming ilagay mo sa ang unang lokasyon dito. 468 00:19:01,490 --> 00:19:03,930 >> At ngayon kung maaari mong dumating sa paligid, pati na rin, kami ay pagpunta sa 469 00:19:03,930 --> 00:19:06,300 maging sa dalawang lokasyon. 470 00:19:06,300 --> 00:19:09,120 At kahit na ito nararamdaman tulad ng ito ay tumatagal ang, ano ang maganda ngayon ay 471 00:19:09,120 --> 00:19:14,710 na sa kaliwang kalahati ng kaliwa kalahati na ngayon ang pinagsunod-sunod. 472 00:19:14,710 --> 00:19:18,010 Kaya kung ano ang susunod na hakbang, kung namin ngayon rewind pa sa kuwentong ito? 473 00:19:18,010 --> 00:19:18,980 >> Madla: Mag-right kalahati. 474 00:19:18,980 --> 00:19:19,900 >> David MALAN: Pagsunud-sunurin ang karapatan kalahati. 475 00:19:19,900 --> 00:19:21,320 Kaya mo guys na kailangang gawin ito, pati na rin. 476 00:19:21,320 --> 00:19:23,510 Kaya kung maaari mong tumayo para sandali lamang? 477 00:19:23,510 --> 00:19:25,192 At kung ano ang iyong pangalan? 478 00:19:25,192 --> 00:19:25,540 >> Jess: Jess. 479 00:19:25,540 --> 00:19:25,870 >> David MALAN: Jess. 480 00:19:25,870 --> 00:19:29,720 OK, kaya Jess na ngayon ang sa kaliwa kalahati ng kanang kalahati. 481 00:19:29,720 --> 00:19:31,400 At kaya niya ang isang listahan ng sukat 1. 482 00:19:31,400 --> 00:19:32,380 Malinaw naman ang kanyang pinagsunod-sunod. 483 00:19:32,380 --> 00:19:33,070 At ang iyong pangalan muli? 484 00:19:33,070 --> 00:19:33,630 >> Michelle: Michelle. 485 00:19:33,630 --> 00:19:35,340 >> David MALAN: Michelle ay malinaw naman isang listahan ng mga sukat 1. 486 00:19:35,340 --> 00:19:36,050 Na siya pinagsunod-sunod. 487 00:19:36,050 --> 00:19:38,690 Kaya ngayon magic ang mangyayari, ang proseso ng pagbubuklod. 488 00:19:38,690 --> 00:19:39,790 Kaya kung sino ang pagpunta sa dumating una? 489 00:19:39,790 --> 00:19:41,560 Malinaw Michelle. 490 00:19:41,560 --> 00:19:43,280 Kaya kung maaari mong dumating sa paligid ng likod. 491 00:19:43,280 --> 00:19:47,090 Ang espasyo mayroon kaming magagamit para sa kanya ngayon ang tama ito sa likod ng upuan dito. 492 00:19:47,090 --> 00:19:51,580 At ngayon, kung maaari kang bumalik pati na rin, kami ay mayroon na ngayong, upang maging malinaw, dalawang 493 00:19:51,580 --> 00:19:53,810 halves, bawat isa sa laki ng 2 - 494 00:19:53,810 --> 00:19:57,090 at para lamang sa kapakanan ng paglalarawan, kung maaaring gumawa ng isang maliit na bit ng isang puwang - 495 00:19:57,090 --> 00:19:59,780 isa pakaliwa kalahati dito, isa kanang kalahati dito. 496 00:19:59,780 --> 00:20:01,160 >> Rewind pa sa kuwento. 497 00:20:01,160 --> 00:20:02,270 Ano hakbang ay ang susunod? 498 00:20:02,270 --> 00:20:03,030 >> Madla: Pagsamahin. 499 00:20:03,030 --> 00:20:04,160 >> David MALAN: Kaya ngayon kami ay may upang sumanib. 500 00:20:04,160 --> 00:20:07,490 Kaya OK, kaya ngayon, thankfully, namin lamang nabakante apat na upuan. 501 00:20:07,490 --> 00:20:11,480 Kaya namin ang ginamit nang dalawang beses bilang magkano ang memorya, ngunit maaari naming bigyan tingnan-flopping sa pagitan ng 502 00:20:11,480 --> 00:20:12,330 ang dalawang array. 503 00:20:12,330 --> 00:20:14,190 Kaya kung aling mga numero ay na dumating una? 504 00:20:14,190 --> 00:20:14,850 Kaya Michelle, nang walang alinlangan. 505 00:20:14,850 --> 00:20:16,680 Kaya dumating sa paligid at tumagal ang iyong upuan dito. 506 00:20:16,680 --> 00:20:19,120 At pagkatapos ay number 2 ay malinaw naman susunod, kaya napunta ka dito. 507 00:20:19,120 --> 00:20:21,520 Number 4, 6 na numero. 508 00:20:21,520 --> 00:20:23,390 At muli, kahit na mayroong isang kaunting paglalakad kasangkot, 509 00:20:23,390 --> 00:20:26,010 talaga, ang mga ito ay maaaring mangyari kaagad, sa pamamagitan ng paggalaw ng isa - 510 00:20:26,010 --> 00:20:26,880 OK, nag-play na rin. 511 00:20:26,880 --> 00:20:28,350 >> [Tawa] 512 00:20:28,350 --> 00:20:29,680 >> David MALAN: At ngayon kami ay sa medyo magandang hugis. 513 00:20:29,680 --> 00:20:34,910 Ang kaliwa kalahati ng buong input na ngayon ang pinagsunod-sunod. 514 00:20:34,910 --> 00:20:37,370 Ang lahat ng mga karapatan, sa gayon ang mga guys ay nagkaroon ng kalamangan sa aking - 515 00:20:37,370 --> 00:20:40,340 paano ginawa ito tapusin ang lahat ng mga batang babae sa pakaliwa at ang lahat ng mga lalaki sa kanan? 516 00:20:40,340 --> 00:20:42,450 >> OK, kaya guys 'i-on ngayon. 517 00:20:42,450 --> 00:20:44,680 Kaya hindi ko ituturo sa iyo mga hakbang na ito. 518 00:20:44,680 --> 00:20:46,550 Susubukan naming makita kung maaari naming muling mag-apply ang parehong pseudocode. 519 00:20:46,550 --> 00:20:50,050 Kung nais mong sige at tumayo, at ka guys, hayaan mo akong bigyan ka ng mic. 520 00:20:50,050 --> 00:20:52,990 Tingnan kung hindi ka maaaring magtiklop kung ano lang namin ginawa dito sa 521 00:20:52,990 --> 00:20:53,880 kabilang dulo ng listahan. 522 00:20:53,880 --> 00:20:59,530 Sino ang kailangang makipag-usap muna, batay sa mga algorithm? 523 00:20:59,530 --> 00:21:03,210 Kaya ipaliwanag kung ano ang iyong ginagawa bago gumawa ka ng anumang mga paa paggalaw. 524 00:21:03,210 --> 00:21:05,930 >> Tagapagsalita 1: Ang lahat ng mga karapatan, kaya mula noong Ako ang kaliwang kalahati ng 525 00:21:05,930 --> 00:21:07,790 kaliwa kalahati, bumalik ako. 526 00:21:07,790 --> 00:21:08,730 I-right? 527 00:21:08,730 --> 00:21:09,250 >> David MALAN: Mahusay. 528 00:21:09,250 --> 00:21:10,350 >> Tagapagsalita 1: At pagkatapos - 529 00:21:10,350 --> 00:21:11,800 >> David MALAN: Sino ang ipinapakita mic ang pumunta sa susunod? 530 00:21:11,800 --> 00:21:12,920 >> Tagapagsalita 1: Susunod na numero. 531 00:21:12,920 --> 00:21:14,720 >> Tagapagsalita 2: Kaya ako ang kanang kalahati ng kaliwang kalahati ng 532 00:21:14,720 --> 00:21:17,830 kaliwa kalahati, at ibalik ko. 533 00:21:17,830 --> 00:21:18,050 >> David MALAN: Mahusay. 534 00:21:18,050 --> 00:21:18,550 Bumalik ka. 535 00:21:18,550 --> 00:21:21,855 Kaya ngayon kung ano ang susunod na up para sa iyo dalawang? 536 00:21:21,855 --> 00:21:23,740 >> Tagapagsalita 2: Gusto naming makita kung sino ang mas maliit. 537 00:21:23,740 --> 00:21:24,200 >> David MALAN: Mismong. 538 00:21:24,200 --> 00:21:24,940 Gusto naming pagsamahin. 539 00:21:24,940 --> 00:21:27,590 Ang espasyo kami ng pagpunta sa gamitin upang sumanib sa iyo, kahit na ang mga ito 540 00:21:27,590 --> 00:21:30,250 malinaw naman na pinagsunod-sunod, kami ay pagpunta na sundin ang parehong algorithm. 541 00:21:30,250 --> 00:21:31,560 Kaya kung sino ang pupunta sa likod muna? 542 00:21:31,560 --> 00:21:35,720 Kaya 3, at pagkatapos ay i-7. 543 00:21:35,720 --> 00:21:38,570 At ngayon ang mic napupunta sa mga guys, OK? 544 00:21:38,570 --> 00:21:43,590 >> Tagapagsalita 3: Kaya ako ang kanang kalahati ng kaliwa kalahati, at ang aking n Mababa sa 545 00:21:43,590 --> 00:21:45,048 1, kaya lang ako pagpunta sa pumasa - 546 00:21:45,048 --> 00:21:46,380 >> David MALAN: Mahusay. 547 00:21:46,380 --> 00:21:49,450 >> Tagapagsalita 4: Ako ang kanang kalahati ng kanang kalahati ng kanang kalahati, at ako 548 00:21:49,450 --> 00:21:51,740 din ang isang tao, kaya ako pagpunta sa bumalik. 549 00:21:51,740 --> 00:21:52,990 Kaya ngayon namin pagsamahin. 550 00:21:52,990 --> 00:21:55,140 551 00:21:55,140 --> 00:21:56,150 >> Tagapagsalita 3: Kaya naming bumalik. 552 00:21:56,150 --> 00:21:57,160 >> David MALAN: Kaya kang pumunta sa likod. 553 00:21:57,160 --> 00:21:59,200 Kaya 5 napupunta muna, pagkatapos ay i-8. 554 00:21:59,200 --> 00:22:01,240 At ngayon madla, kung saan ay ang hakbang na mayroon kami sa ngayon rewind 555 00:22:01,240 --> 00:22:02,200 upang i-back sa ating mga isip? 556 00:22:02,200 --> 00:22:02,940 >> Madla: Pagsamahin. 557 00:22:02,940 --> 00:22:07,270 >> David MALAN: Ang pagsasama sa kaliwa kalahati at kanang kalahati ng orihinal na kaliwa kalahati. 558 00:22:07,270 --> 00:22:08,840 Kaya ngayon - 559 00:22:08,840 --> 00:22:10,520 at lamang upang gumawa ng malinaw na ito, gumawa ng kaunting espasyo 560 00:22:10,520 --> 00:22:11,690 sa pagitan mo dalawang guys. 561 00:22:11,690 --> 00:22:13,800 Kaya ngayon na ang dalawang mga listahan, kaliwa at kanan. 562 00:22:13,800 --> 00:22:18,320 Kaya paano namin ngayon pagsamahin mo guys sa sa harap hilera ng upuan muli? 563 00:22:18,320 --> 00:22:19,600 >> 3 napupunta unang. 564 00:22:19,600 --> 00:22:20,850 Pagkatapos 5, nang walang alinlangan. 565 00:22:20,850 --> 00:22:23,110 566 00:22:23,110 --> 00:22:27,330 Pagkatapos ay 7, at ngayon ay 8. 567 00:22:27,330 --> 00:22:28,710 OK, at ngayon kami ay? 568 00:22:28,710 --> 00:22:29,650 >> Madla: Di tapos na. 569 00:22:29,650 --> 00:22:32,440 >> David MALAN: Hindi tapos na, dahil malinaw naman, mayroong isang hakbang natitira. 570 00:22:32,440 --> 00:22:35,720 Ngunit muli, ang dahilan gumagamit ako ng ito magulong pag-uusap tulad ng "rewind sa iyong isip," 571 00:22:35,720 --> 00:22:37,160 ito ay dahil na talaga kung ano ang nangyayari. 572 00:22:37,160 --> 00:22:39,610 Kami ay pagpunta sa pamamagitan ng lahat ng mga hakbang na ito, ngunit kami ay isang uri ng pag-pause para sa isang 573 00:22:39,610 --> 00:22:42,480 sandali, diving mas malalim sa algorithm, pag-pause para sa isang sandali, 574 00:22:42,480 --> 00:22:45,840 diving mas malalim sa mga algorithm, at ngayon kami ay may upang ayusin ng rewind sa aming 575 00:22:45,840 --> 00:22:49,430 isip at i-undo lahat ng mga layer na namin ang uri ng ilagay sa hold. 576 00:22:49,430 --> 00:22:51,790 >> Kaya ngayon kami ay may dalawang mga listahan ng mga sukat 4. 577 00:22:51,790 --> 00:22:54,790 Kung ka guys ay maaaring tumayo ang huling oras at gumawa ng kaunting espasyo dito upang 578 00:22:54,790 --> 00:22:57,230 gumawa ng malinaw na ito ay ang kaliwa kalahati ng orihinal na, ang 579 00:22:57,230 --> 00:22:58,620 kanang kalahati ng orihinal. 580 00:22:58,620 --> 00:23:01,060 Sino ang unang numero na aming kailangan upang hilahin sa likod? 581 00:23:01,060 --> 00:23:01,870 Michelle, siyempre. 582 00:23:01,870 --> 00:23:03,230 >> Kaya naming ilagay Michelle dito. 583 00:23:03,230 --> 00:23:05,080 At sino ang may number 2? 584 00:23:05,080 --> 00:23:06,440 Numero ng 2 pagdating sa likod pati na rin. 585 00:23:06,440 --> 00:23:07,800 Number 3? 586 00:23:07,800 --> 00:23:08,510 Magaling. 587 00:23:08,510 --> 00:23:16,570 Number 4, numero 5, 6 na numero, number 7, at 8 numero. 588 00:23:16,570 --> 00:23:18,850 >> OK, sa gayon ito nadama tulad ng maraming ng mga hakbang, para sigurado. 589 00:23:18,850 --> 00:23:22,390 Ngunit ngayon sabihin makita kung hindi namin makumpirma uri ng intuitively na ito 590 00:23:22,390 --> 00:23:26,190 algorithm sa panimula, lalo na bilang n ay nakakakuha talagang malaki, pati na nasaksihan namin 591 00:23:26,190 --> 00:23:29,170 may animation, ay sa panimula mas mabilis. 592 00:23:29,170 --> 00:23:33,400 Kaya inaangkin ko ito algorithm, sa pinakamalala kaso at kahit na sa ang pinakamahusay na kaso, 593 00:23:33,400 --> 00:23:36,160 ay malaki O ng beses n log n. 594 00:23:36,160 --> 00:23:39,160 Iyon ay, mayroong ilang mga aspeto ng ito algorithm na tumatagal ng mga hakbang n, ngunit 595 00:23:39,160 --> 00:23:43,110 mayroong isa pang aspeto sa isang lugar sa na-ulit, na looping, na 596 00:23:43,110 --> 00:23:44,410 tumatagal log hakbang n. 597 00:23:44,410 --> 00:23:49,154 Maaari naming ilagay ang aming mga daliri sa kung ano ang mga dalawang numero ay nagre-refer sa? 598 00:23:49,154 --> 00:23:51,320 Well, kung saan - 599 00:23:51,320 --> 00:23:54,160 where'd mic ang pumunta? 600 00:23:54,160 --> 00:23:58,660 >> Tagapagsalita 1: Gusto ang mag-log n maging pagsira sa amin up sa dalawa - 601 00:23:58,660 --> 00:23:59,630 paghahati sa pamamagitan ng dalawang, mahalagang. 602 00:23:59,630 --> 00:24:00,120 >> David MALAN: Mismong. 603 00:24:00,120 --> 00:24:03,000 Anumang oras na nakikita namin sa anumang mga algorithm kaya sa ngayon, mayroong nangyaring ang pattern na ito ng 604 00:24:03,000 --> 00:24:04,200 divide, divide, divide. 605 00:24:04,200 --> 00:24:05,700 At karaniwang ito ay nabawasan sa isang bagay na 606 00:24:05,700 --> 00:24:07,100 logarithmic, log base 2. 607 00:24:07,100 --> 00:24:10,180 Ngunit maaari itong talagang maging anumang bagay, ngunit mag-log base 2. 608 00:24:10,180 --> 00:24:11,330 >> Ngayon kung ano ang tungkol sa n? 609 00:24:11,330 --> 00:24:14,550 Maaari ko bang makita na namin ang uri ng hinati mo guys - hinati sa iyo, na hinati sa iyo, 610 00:24:14,550 --> 00:24:15,910 hinati mo, hinati sa iyo. 611 00:24:15,910 --> 00:24:18,760 Saan kinukuha ng pagtatapos ang nanggaling? 612 00:24:18,760 --> 00:24:19,810 >> Kaya ito ang pinagsasama. 613 00:24:19,810 --> 00:24:20,610 Dahil sa tingin tungkol dito. 614 00:24:20,610 --> 00:24:25,420 Kapag pagsamahin mo ang walong taong magkasama, kung saan ang kalahati sa kanila ay isang hanay ng mga apat 615 00:24:25,420 --> 00:24:27,770 at ang iba pang kalahati ay isa pang set ng apat, paano mo pumunta 616 00:24:27,770 --> 00:24:28,820 tungkol sa paggawa ng pagbubuklod? 617 00:24:28,820 --> 00:24:30,830 Well, ka guys ginawa ito medyo intuitively. 618 00:24:30,830 --> 00:24:34,140 >> Ngunit kung ako sa halip ginawa ito ng kaunti pa methodically, maaari ko pa sa may tulis 619 00:24:34,140 --> 00:24:38,090 pinakakaliwa ang unang tao sa aking kaliwa banda, itinuturo sa pinakakaliwa tao 620 00:24:38,090 --> 00:24:42,080 ng na kalahati sa aking kanang kamay, at lamang pagkaraan lumakad sa pamamagitan ng 621 00:24:42,080 --> 00:24:46,990 listahan, na nagtuturo sa mga pinakamaliliit na elemento bawat oras, gumagalaw ang aking daliri sa ibabaw at 622 00:24:46,990 --> 00:24:48,970 sa ibabaw tulad ng kinakailangan sa buong listahan. 623 00:24:48,970 --> 00:24:51,890 Ngunit kung ano ang tungkol sa key na ito pinagsasama proseso ay ako paghahambing ng mga pares 624 00:24:51,890 --> 00:24:53,460 ng mga elemento. 625 00:24:53,460 --> 00:24:57,270 Mula sa kanang kalahati at mula sa kaliwa kalahati, hindi ako isang beses backtracking. 626 00:24:57,270 --> 00:25:00,570 >> Kaya ang sumanib mismo ay pagkuha hindi hihigit sa n hakbang. 627 00:25:00,570 --> 00:25:03,250 At kung gaano karaming beses ginawang Mayroon akong gawin na pinagsasama? 628 00:25:03,250 --> 00:25:07,150 Well, hindi hihigit sa n, at hindi na namin lamang Nakita na may mga panghuling sumanib. 629 00:25:07,150 --> 00:25:13,120 At kaya kung gagawin mo ang isang bagay na tumatagal mag-log n hakbang n beses, o kabaligtaran, 630 00:25:13,120 --> 00:25:15,210 ito ay pagpunta sa bigyan kami ng n beses log n. 631 00:25:15,210 --> 00:25:16,310 >> At kung bakit ito ay mas mahusay? 632 00:25:16,310 --> 00:25:19,600 Well, kung kami na malaman na ang log n ay mas mahusay kaysa sa n - tama? 633 00:25:19,600 --> 00:25:22,590 Nakakita kami sa binary paghahanap, ang phone book Halimbawa, log n noon ay siguradong 634 00:25:22,590 --> 00:25:23,760 mas mahusay kaysa sa linear. 635 00:25:23,760 --> 00:25:28,420 Kaya na nangangahulugan n beses log n ay Talagang mas mahusay kaysa sa n isa pang beses 636 00:25:28,420 --> 00:25:30,390 n, aka n squared. 637 00:25:30,390 --> 00:25:32,400 At ang ginagawa namin sa huli pakiramdam. 638 00:25:32,400 --> 00:25:34,928 >> Kaya malaki ang pag-ikot ng papuri, kung maaari naming, para sa mga guys. 639 00:25:34,928 --> 00:25:38,920 >> [Palakpakan] 640 00:25:38,920 --> 00:25:41,550 >> David MALAN: At ang iyong Paghahati ng mga regalo - maaari mong panatilihin ang mga numero, 641 00:25:41,550 --> 00:25:44,010 kung gusto mo. 642 00:25:44,010 --> 00:25:45,620 At iyong Paghahati ng regalo, gaya ng dati. 643 00:25:45,620 --> 00:25:47,290 Oh, at magpapadala kami sa iyo ang footage, Michelle. 644 00:25:47,290 --> 00:25:48,343 Salamat sa inyo. 645 00:25:48,343 --> 00:25:49,250 Ayos lang. 646 00:25:49,250 --> 00:25:50,400 Tulungan ang iyong sarili sa isang bola stress. 647 00:25:50,400 --> 00:25:54,110 >> At hayaan mo akong hilahin pataas, sa pansamantala, ang aming mga kaibigan Rob Bowden upang mag-alok 648 00:25:54,110 --> 00:25:59,520 medyo iba sa pananaw na ito, dahil maaari mong isipin ang tungkol sa mga 649 00:25:59,520 --> 00:26:01,280 hakbang na nangyayari sa isang medyo iba't ibang paraan. 650 00:26:01,280 --> 00:26:04,750 Sa katunayan, ang set-up para sa kung ano ang Rob ay tungkol sa upang ipakita sa amin Ipinagpapalagay na na namin 651 00:26:04,750 --> 00:26:09,030 nagagawa sa naghahating up ng malaking listahan sa walong maliit na mga listahan, 652 00:26:09,030 --> 00:26:10,570 bawat isa sa laki 1. 653 00:26:10,570 --> 00:26:13,350 >> Kaya naming binabago ang isang pseudocode Medyo lamang upang pagbukud-bukurin makakuha ng sa 654 00:26:13,350 --> 00:26:15,320 pangunahing ideya kung paano ang pinagsasama ang mga gawa. 655 00:26:15,320 --> 00:26:17,600 Ngunit ang oras ng paggana ng kung ano siya ay tungkol sa upang gawin ay pa rin 656 00:26:17,600 --> 00:26:19,110 pagpunta sa maging ang parehong. 657 00:26:19,110 --> 00:26:23,540 At muli, ang set-up dito ay na siya ay nagsimula na may walong mga listahan ng mga sukat 1. 658 00:26:23,540 --> 00:26:27,730 Kaya mo nasagot ang bahagi kung saan siya talagang tapos na ang log n, log n, log n 659 00:26:27,730 --> 00:26:31,205 paghahati ng input. 660 00:26:31,205 --> 00:26:32,120 >> [Video playback] 661 00:26:32,120 --> 00:26:33,615 >> -Iyon lang para sa hakbang ng isa. 662 00:26:33,615 --> 00:26:38,270 Para sa dalawang hakbang, paulit-ulit pagsamahin ang mga pares ng mga listahan. 663 00:26:38,270 --> 00:26:39,210 >> David MALAN: Hm. 664 00:26:39,210 --> 00:26:41,270 Tanging ang audio ay darating out sa aking computer. 665 00:26:41,270 --> 00:26:42,520 Tayo'y subukan ito muli. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Nagkataon lang piliin kung aling mga - ngayon kami ay may apat na mga listahan. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 Matuto nang bago. 670 00:26:52,120 --> 00:26:53,040 >> David MALAN: Mayroon kaming pumunta. 671 00:26:53,040 --> 00:27:00,510 >> Ang pagsasama-108 at 15, tapusin namin up sa listahan ng 15, 108. 672 00:27:00,510 --> 00:27:07,170 Ang pagsasama sa 50 at 4, namin end up sa 4, 50. 673 00:27:07,170 --> 00:27:12,990 Ang pagsasama sa 8 at 42, kami end up sa 8, 42. 674 00:27:12,990 --> 00:27:19,970 At pagbubuklod 23 at 16, kami end up na may 16, 23. 675 00:27:19,970 --> 00:27:23,270 >> Ngayon ang lahat ng aming mga listahan ay ang laki ng 2. 676 00:27:23,270 --> 00:27:26,690 Pansinin na ang bawat isa sa apat na listahan ay pinagsunod-sunod. 677 00:27:26,690 --> 00:27:29,450 Kaya maaari naming simulan pinagsasama mga pares ng mga listahan muli. 678 00:27:29,450 --> 00:27:38,420 Ang pagsasama sa 15 at 108 at 4 at 50, kami unang kumuha ng 4, pagkatapos ang 15, pagkatapos ay 679 00:27:38,420 --> 00:27:41,500 ang 50, pagkatapos ay ang 108. 680 00:27:41,500 --> 00:27:50,610 Ang pagsasama sa 8, 42 at 16, 23, una naming tumagal ang 8, pagkatapos ang 16, pagkatapos ay ang 23, 681 00:27:50,610 --> 00:27:52,700 pagkatapos ng 42. 682 00:27:52,700 --> 00:27:57,600 >> Kaya ngayon kami ay may lamang ng dalawang mga listahan ng mga laki 4, ang bawat isa ay pinagsunod-sunod. 683 00:27:57,600 --> 00:28:01,170 Kaya ngayon pagsamahin namin ang dalawang mga listahan. 684 00:28:01,170 --> 00:28:11,835 Una, tumagal kami ng 4, pagkatapos ay i-alang namin ang mga 8, pagkatapos ay i-alang namin ang 15, pagkatapos ay 16, pagkatapos 685 00:28:11,835 --> 00:28:19,456 23, pagkatapos ay 42, pagkatapos ay 50, pagkatapos ay 108. 686 00:28:19,456 --> 00:28:19,872 >> [END-playback ng video] 687 00:28:19,872 --> 00:28:23,430 >> David MALAN: Muli, paunawa, siya ay hindi kailanman hinawakan isang ibinigay na tasa ng higit sa isang oras 688 00:28:23,430 --> 00:28:24,860 pagkatapos ng pagsulong lampas ito. 689 00:28:24,860 --> 00:28:26,200 Kaya hindi na niya paulit-ulit. 690 00:28:26,200 --> 00:28:29,850 Kaya palagi niya gumagalaw sa gilid, at na kung saan namin nakuha ang aming n. 691 00:28:29,850 --> 00:28:33,290 >> Bakit hindi hayaan mo akong makuha ang isa animation na nakita natin mas maaga, ngunit oras na ito 692 00:28:33,290 --> 00:28:35,110 tumututok lamang sa pagsasama-uri. 693 00:28:35,110 --> 00:28:38,030 Hayaan akong sige at mag-zoom in sa mga ito dito. 694 00:28:38,030 --> 00:28:42,530 Unang hayaan mo akong pumili ng isang random na input, palakihin ito, at maaari mong i-sort ng makita 695 00:28:42,530 --> 00:28:46,600 ano kinuha namin para sa ipinagkaloob, mas maaga, pagsamahin ang pag-uuri ay aktwal na paggawa. 696 00:28:46,600 --> 00:28:50,330 >> Kaya mapapansin na kumuha ka ng mga halves o mga quarters o mga eighths ng 697 00:28:50,330 --> 00:28:53,140 problema na ang lahat ng isang biglaang simulan na kumuha ng mahusay na hugis. 698 00:28:53,140 --> 00:28:57,070 At pagkatapos ay sa wakas, makikita mo sa pinakadulo na panunuba, 699 00:28:57,070 --> 00:28:58,860 ang lahat ng bagay ay pinagsama-sama. 700 00:28:58,860 --> 00:29:01,690 >> Kaya ang mga ito ay lamang ng tatlong iba't ibang tumatagal sa parehong mga ideya. 701 00:29:01,690 --> 00:29:05,980 Ngunit ang key na pananaw, tulad ng hatiin at lupigin sa pinakadulo first class, 702 00:29:05,980 --> 00:29:10,640 na noon ay napagpasyahan naming sa paanuman hatiin ang mga problema sa isang bagay na malaki, sa 703 00:29:10,640 --> 00:29:14,760 isang bagay na uri ng katulad sa espiritu, ngunit mas maliit at mas maliit at mas maliit 704 00:29:14,760 --> 00:29:15,660 at mas maliit. 705 00:29:15,660 --> 00:29:18,420 >> Ngayon ay isa pang masaya na paraan upang ayusin ng tingin tungkol sa mga ito, kahit na ito ay hindi 706 00:29:18,420 --> 00:29:20,520 pagpunta sa magbibigay sa iyo ng parehong madaling maunawaan pang-unawa, ay 707 00:29:20,520 --> 00:29:21,640 ang mga sumusunod na animation. 708 00:29:21,640 --> 00:29:25,400 Kaya ito ay isang video ng isang tao ilagay magkasama na nauugnay ibang 709 00:29:25,400 --> 00:29:29,970 tunog na may iba't-ibang mga pagpapatakbo para sa pagpapasok ng uri, para sa pagsasama-uri-uriin, at 710 00:29:29,970 --> 00:29:31,150 para sa isang pares ng mga iba. 711 00:29:31,150 --> 00:29:32,330 Kaya sa isang sandali, pupuntahan ko pindutin ang Play. 712 00:29:32,330 --> 00:29:33,600 Ito ay tungkol sa isang minuto ang haba. 713 00:29:33,600 --> 00:29:37,410 At kahit na maaari mo pa ring makita ang pattern ng nangyayari, oras na ito maaari mong 714 00:29:37,410 --> 00:29:41,420 din marinig kung paano ang mga algorithm ay gumaganap naiiba at may 715 00:29:41,420 --> 00:29:43,950 medyo iba pattern. 716 00:29:43,950 --> 00:29:45,830 >> Ito ay pagpapasok-uri. 717 00:29:45,830 --> 00:29:50,400 >> [Tone pag-play] 718 00:29:50,400 --> 00:29:52,400 >> David MALAN: Ito muli ay sinusubukan upang magpasok ng bawat elemento 719 00:29:52,400 --> 00:29:52,900 sa kung saan ito ay kabilang. 720 00:29:52,900 --> 00:29:54,628 Ito ang bubble sort. 721 00:29:54,628 --> 00:30:10,097 >> [Tone pag-play] 722 00:30:10,097 --> 00:30:13,630 >> David MALAN: At maaari mong uri-uriin ng pakiramdam paano relatibong maliit na gumana ito ginagawa 723 00:30:13,630 --> 00:30:15,834 sa bawat hakbang. 724 00:30:15,834 --> 00:30:20,470 Ito ay kung ano tediousness Mukhang. 725 00:30:20,470 --> 00:30:21,472 >> [Tone pag-play] 726 00:30:21,472 --> 00:30:25,222 >> David MALAN: Ito ang seleksyon-uri, kung saan namin piliin ang sangkap na nais naming sa pamamagitan ng 727 00:30:25,222 --> 00:30:28,845 sa pamamagitan ng pagpunta muli at muli at muli at paglalagay ito sa simula. 728 00:30:28,845 --> 00:30:37,674 >> [Tone pag-play] 729 00:30:37,674 --> 00:30:43,970 >> David MALAN: Ito ay sumanib-uri, na Maaari mo ba talagang simulan sa pakiramdam. 730 00:30:43,970 --> 00:30:51,810 >> [Tone pag-play] 731 00:30:51,810 --> 00:30:54,770 >> [Tawa] 732 00:30:54,770 --> 00:30:58,395 >> David MALAN: Isang bagay na tinatawag na lamang-lupa -uri-uriin, na hindi pa namin ay tumingin sa. 733 00:30:58,395 --> 00:31:13,630 >> [Tone pag-play] 734 00:31:13,630 --> 00:31:17,910 >> David MALAN: Kaya hayaan mo akong makita, ngayon, ginulo bilang ka sana ay sa pamamagitan ng mga 735 00:31:17,910 --> 00:31:21,110 musika, kung maaari kong slip ng kaunti bit ng math in dito. 736 00:31:21,110 --> 00:31:24,850 Kaya mayroong 1/4 na paraan na aming makakaya isipin ang tungkol sa kung ano ang ibig sabihin nito ang mga 737 00:31:24,850 --> 00:31:29,210 mga function na maging mas mabilis kaysa sa mga bago na nasaksihan namin dati. 738 00:31:29,210 --> 00:31:32,470 At kung ikaw ay darating sa kurso mula sa isang matematika background, mo 739 00:31:32,470 --> 00:31:36,030 talaga alam na marahil na ikaw Maaari sampal isang termino sa diskarteng ito - 740 00:31:36,030 --> 00:31:40,400 lalo recursion, isang function sa paanuman na tawag mismo. 741 00:31:40,400 --> 00:31:44,780 >> At muli, isipin ang sumanib na pag-uuri pseudocode ay recursive sa kamalayan 742 00:31:44,780 --> 00:31:48,460 na ang isa sa mga hakbang sa pagsasama-uri ng ay tumawag sa uri-uriin - 743 00:31:48,460 --> 00:31:49,740 iyon ay, mismo. 744 00:31:49,740 --> 00:31:52,480 Pero thankfully, sapagkat hindi namin itinatago pagtawag-uri, o pagsamahin ang pag-uuri, 745 00:31:52,480 --> 00:31:55,880 partikular, sa isang mas maliit at mas maliit at mas maliit na listahan, namin kalaunan 746 00:31:55,880 --> 00:32:00,005 bottomed out salamat sa kung ano ang makikita namin tumawag isang base ng kaso, ang hard-code na kaso 747 00:32:00,005 --> 00:32:04,270 Sinabi kung ang listahan ay maliit, mas mababa sa 2 sa kasong iyon, bumalik lang agad. 748 00:32:04,270 --> 00:32:07,550 Kung hindi namin ginawa na may mga espesyal na kaso, ang algorithm ng ginagawa hindi kailanman ilalim out, 749 00:32:07,550 --> 00:32:11,010 at gusto mo talagang makapunta sa isang walang katapusang loop tunay magpakailanman. 750 00:32:11,010 --> 00:32:14,330 >> Ngunit ipagpalagay na gusto naming ilagay ngayon ilang mga numero sa mga ito, muli, gamit n 751 00:32:14,330 --> 00:32:15,660 bilang ang laki ng input. 752 00:32:15,660 --> 00:32:18,680 At Nais kong hilingin sa iyo, kung ano ang ang kabuuang oras na kasangkot sa 753 00:32:18,680 --> 00:32:19,800 tumatakbo pagsasama-uri? 754 00:32:19,800 --> 00:32:22,960 O kaya naman mas pangkalahatang paraan, kung ano ang ang gastos ng mga ito sa oras? 755 00:32:22,960 --> 00:32:24,730 >> Well ito ay medyo madali upang masukat na. 756 00:32:24,730 --> 00:32:29,010 Kung n Mababa sa 2, ang oras na kasangkot sa pagbubukod-bukod ng mga elemento n, 757 00:32:29,010 --> 00:32:30,480 n kung saan ay 2, ay 0. 758 00:32:30,480 --> 00:32:31,410 Dahil kami lang bumalik. 759 00:32:31,410 --> 00:32:32,510 Walang trabaho upang gawin. 760 00:32:32,510 --> 00:32:35,660 Ngayon arguably, marahil ito ay isang hakbang o dalawang hakbang na ito upang malaman ang halaga ng 761 00:32:35,660 --> 00:32:38,420 gumana, ngunit ito ay malapit na sapat upang 0 na Lamang ako ng pagpunta sa sabihin walang trabaho ay 762 00:32:38,420 --> 00:32:40,940 kinakailangan kapag ang listahan ay kaya maliit na na hindi kawili-wili. 763 00:32:40,940 --> 00:32:42,580 >> Ngunit kasong ito ay kawili-wili. 764 00:32:42,580 --> 00:32:47,320 Ang recursive kaso ay ang sangay ng ang pseudocode na sinabi ng ibang tao, pag-uuri 765 00:32:47,320 --> 00:32:52,000 sa kaliwang kalahati, uri-uriin ang karapatan kalahati, pagsamahin ang dalawang halves. 766 00:32:52,000 --> 00:32:55,530 Ngayon kung bakit gumagana ang expression na ito kumakatawan na gastos? 767 00:32:55,530 --> 00:32:58,690 Well, T ng n lamang ay nangangahulugan na ang oras upang ayusin n elemento. 768 00:32:58,690 --> 00:33:03,070 At pagkatapos ay sa kanang bahagi ng equals sign doon, ang T ng n hinati 769 00:33:03,070 --> 00:33:06,600 sa pamamagitan ng 2 ay nagre-refer na upang ang gastos ng kung ano? 770 00:33:06,600 --> 00:33:07,570 Pag-aayos sa kaliwa kalahati. 771 00:33:07,570 --> 00:33:10,990 Ang iba pang mga T ng n hinati sa 2 ay siguro nagre-refer sa mga gastos sa 772 00:33:10,990 --> 00:33:12,390 -uri-uriin ang karapatan kalahati. 773 00:33:12,390 --> 00:33:14,590 >> At pagkatapos ay ang plus n? 774 00:33:14,590 --> 00:33:15,420 Ay ang pinagsasama. 775 00:33:15,420 --> 00:33:19,120 Dahil kung mayroon kang dalawang mga listahan, isa sa laki n sa 2 at isa pa sa laki n 776 00:33:19,120 --> 00:33:22,580 sa 2, mayroon ka upang lubos na hawakan bawat isa sa mga elemento, tulad ng Rob 777 00:33:22,580 --> 00:33:24,990 hinawakan bawat isa sa mga tasa, at lamang bilang namin itinuturo sa bawat isa sa mga 778 00:33:24,990 --> 00:33:26,310 boluntaryo sa entablado. 779 00:33:26,310 --> 00:33:28,790 Kaya n ay ang gastos ng pagbubuklod. 780 00:33:28,790 --> 00:33:31,780 >> Ngayon, sa kasamaang-palad, ito formula din ang kanyang sarili recursive. 781 00:33:31,780 --> 00:33:36,390 Kaya kung tinanong ang tanong, kung n ay, sabihin nating, 16, kung mayroong 16 mga tao sa entablado 782 00:33:36,390 --> 00:33:40,670 o 16 tasa sa video, kung gaano karaming mga kabuuang hakbang na aabutin upang pagbukud-bukurin ang mga ito 783 00:33:40,670 --> 00:33:41,550 may sumanib-uri? 784 00:33:41,550 --> 00:33:45,790 Ito ay talagang hindi isang halata na sagot, dahil ngayon ikaw ay may upang ayusin ng 785 00:33:45,790 --> 00:33:48,500 recursively sagutin ang formula. 786 00:33:48,500 --> 00:33:51,190 >> Ngunit iyon lamang ang OK, dahil ipaalam sa akin imungkahi na gawin namin ang mga sumusunod. 787 00:33:51,190 --> 00:33:56,670 Ang oras na kasangkot upang pagbukud-bukurin 16 mga tao o 16 tasa ay pagpunta sa ay kakatawanin 788 00:33:56,670 --> 00:33:58,020 sa pangkalahatan bilang ng T 16. 789 00:33:58,020 --> 00:34:01,400 Ngunit na katumbas, ayon sa aming nakaraang formula, 2 beses ang halaga 790 00:34:01,400 --> 00:34:04,780 ng oras na aabutin upang pagsunud-sunurin 8 tasa plus 16. 791 00:34:04,780 --> 00:34:08,590 At muli, plus 16 ang oras upang pagsamahin, at ang dalawang beses T ng 8 ay ang 792 00:34:08,590 --> 00:34:10,790 oras upang ayusin kaliwa kalahati at kanang kalahati. 793 00:34:10,790 --> 00:34:11,989 >> Ngunit muli, ito ay hindi sapat. 794 00:34:11,989 --> 00:34:13,210 Mayroon kaming upang sumisid sa mas malalim. 795 00:34:13,210 --> 00:34:16,409 Nangangahulugan ito na mayroon kami upang sagutin ang tanong, ano ang T ng 8? 796 00:34:16,409 --> 00:34:19,610 Well T ng 8 ay 2 T beses na 4 na plus 8. 797 00:34:19,610 --> 00:34:20,520 Well, kung ano ang T ng 4? 798 00:34:20,520 --> 00:34:23,780 T ng 4 ay 2 beses T ng 2 plus 4. 799 00:34:23,780 --> 00:34:25,489 Well, kung ano ang T ng 2? 800 00:34:25,489 --> 00:34:29,030 T ng 2 ay 2 beses T ng 1 plus 2. 801 00:34:29,030 --> 00:34:31,940 >> At muli, hindi namin uri ng pagkuha ng natigil sa pag-ikot na ito. 802 00:34:31,940 --> 00:34:34,790 Ngunit ito ay tungkol sa hit na tinatawag nang gayon base kaso. 803 00:34:34,790 --> 00:34:37,310 Dahil kung ano ang T na 1, kami nag-claim? 804 00:34:37,310 --> 00:34:37,810 0. 805 00:34:37,810 --> 00:34:39,730 Kaya ngayon sa wakas, maaari naming magtrabaho paurong. 806 00:34:39,730 --> 00:34:44,290 >> Kung T ng 1 ay 0, maaari ko na ngayong bumalik up isa linya upang ito tao dito, at maaari ko 807 00:34:44,290 --> 00:34:46,330 plug sa 0 para sa T na 1. 808 00:34:46,330 --> 00:34:51,770 Kaya ito ay nangangahulugan na ito ay katumbas ng 2 beses zero, kung hindi man kilala bilang 0, plus 2. 809 00:34:51,770 --> 00:34:53,739 At upang ang buong expression ay 2. 810 00:34:53,739 --> 00:34:58,740 >> Ngayon kung kumuha ako ng T ng 2, na ang sagot ay 2, plug ito sa gitnang linya, T 811 00:34:58,740 --> 00:35:02,740 ng 4, na nagbibigay sa akin ng 2 beses 2 plus 4, kaya 8. 812 00:35:02,740 --> 00:35:07,080 Kung ako pagkatapos ay i-plug in 8 sa nakaraang linya, na nagbibigay sa akin ng 2 beses 8, 16. 813 00:35:07,080 --> 00:35:12,470 At kung namin pagkatapos ay patuloy na may mga 24, pagdaragdag sa 16, namin sa wakas makakuha ng isang 814 00:35:12,470 --> 00:35:13,820 halaga ng 64. 815 00:35:13,820 --> 00:35:18,480 >> Ngayon na in at ng mismong uri ng nagsasalita walang kinalaman ang notation n, ang 816 00:35:18,480 --> 00:35:20,700 malaki Oh, ang wakas na na namin na-pakikipag-usap tungkol sa. 817 00:35:20,700 --> 00:35:24,890 Ngunit ito lumiliko out na 64 ay talagang 16, ang laki ng input, 818 00:35:24,890 --> 00:35:27,110 mag-log base 2 ng 16. 819 00:35:27,110 --> 00:35:30,200 At kung ito ay isang maliit na pamilyar, lamang Sa tingin pabalik, at makikita ito ay bumalik 820 00:35:30,200 --> 00:35:30,700 sa iyo sa kalaunan. 821 00:35:30,700 --> 00:35:33,775 Kung ito ay base log 2, ito ay tulad ng 2 itataas sa kung ano ang nagbibigay sa iyo ng 16? 822 00:35:33,775 --> 00:35:36,380 Oh, na 4, kaya 16 beses 4. 823 00:35:36,380 --> 00:35:39,380 >> At muli, ito ay hindi isang malaking pakikitungo kung ito ay isang uri ng isang malabo memory ngayon. 824 00:35:39,380 --> 00:35:43,720 Ngunit para sa ngayon, kumuha sa pananampalataya 16 na log 16 ay 64. 825 00:35:43,720 --> 00:35:46,590 At gayon nga, na may ganitong simpleng kaliwanagan ng isip check, kami Nakumpirma - 826 00:35:46,590 --> 00:35:48,250 ngunit hindi pormal na di-napatutunayang - 827 00:35:48,250 --> 00:35:52,800 na ang oras ng pagsasama -uri ay sa katunayan n log n. 828 00:35:52,800 --> 00:35:53,790 >> Kaya hindi masama. 829 00:35:53,790 --> 00:35:57,260 Ito ay tiyak na mas mahusay kaysa sa algorithm nasaksihan namin kaya sa ngayon, at 830 00:35:57,260 --> 00:36:00,710 ito ay dahil kami na magagamit, isa, isang diskarte na tinatawag na recursion. 831 00:36:00,710 --> 00:36:03,880 Ngunit mas kawili-wiling kaysa sa na, na kuru-kuro ng paghahati at mapanakop. 832 00:36:03,880 --> 00:36:07,460 Muli, ang tunay na linggo 0 bagay-bagay na kahit na ngayon ay umuulit sa isang 833 00:36:07,460 --> 00:36:08,740 mas nakakahimok paraan. 834 00:36:08,740 --> 00:36:11,750 >> Ngayon ay isang masaya maliit na ehersisyo, kung ikaw ay hindi kailanman tapos na ito - at malamang na 835 00:36:11,750 --> 00:36:14,660 hindi mayroon, dahil uri ng normal mga tao ay hindi isip upang gawin ito. 836 00:36:14,660 --> 00:36:20,650 Ngunit kung pumunta ako sa google.com at kung Gusto kong matuto ng isang bagay tungkol sa 837 00:36:20,650 --> 00:36:22,356 recursion, ang Enter. 838 00:36:22,356 --> 00:36:25,106 839 00:36:25,106 --> 00:36:29,058 >> [Tawa] 840 00:36:29,058 --> 00:36:32,030 [MORE tawa] 841 00:36:32,030 --> 00:36:33,385 David MALAN: Hindi magandang biro mabagal ang pagkalat. 842 00:36:33,385 --> 00:36:34,450 [Tawa] 843 00:36:34,450 --> 00:36:36,970 David MALAN: lamang sa kaso, ito ay doon. 844 00:36:36,970 --> 00:36:38,710 Hindi ko oras ng paggawa ito mali, at mayroong biro ang. 845 00:36:38,710 --> 00:36:40,810 Ayos lang. 846 00:36:40,810 --> 00:36:42,950 Ipaliwanag ito sa mga tao na susunod sa iyo kung ang hindi ito ay lubos na nag-click pa lang. 847 00:36:42,950 --> 00:36:47,650 Ngunit recursion, higit pa sa pangkalahatan, ay tumutukoy upang ang proseso ng isang function sa pagtawag 848 00:36:47,650 --> 00:36:51,430 mismo, o sa mas pangkalahatang paraan, paghahati ng problema sa isang bagay na maaaring maging 849 00:36:51,430 --> 00:36:56,220 Nalutas unti-unti sa pamamagitan ng paglutas ng magkaparehong kinatawan problema. 850 00:36:56,220 --> 00:36:58,400 >> Well, sabihin pagbabagong gears para lamang ng ilang sandali. 851 00:36:58,400 --> 00:37:00,840 Nais namin na magtatapos sa ilang cliffhangers, kaya natin simulan upang i-set 852 00:37:00,840 --> 00:37:05,870 ang entablado, para sa ilang mga minuto, sa isang napaka-simpleng ideya - 853 00:37:05,870 --> 00:37:07,620 na pagpapalit ng dalawang mga elemento, tama? 854 00:37:07,620 --> 00:37:10,040 Ang lahat ng mga algorithm kami nakapunta pakikipag-usap tungkol sa mga nakalipas na ilang 855 00:37:10,040 --> 00:37:12,420 aralin kasangkot sa ilang uri ng pagpapalit. 856 00:37:12,420 --> 00:37:14,630 Ngayon ay makita ang mga ito sa pamamagitan ng pagkuha ng up out ng kanilang mga upuan at 857 00:37:14,630 --> 00:37:18,570 paglalakad sa paligid, ngunit sa code, gagawin namin lamang tumagal ng isang elemento mula sa isang array 858 00:37:18,570 --> 00:37:20,370 at masamang balak ito sa isa pa. 859 00:37:20,370 --> 00:37:21,880 >> Kaya paano namin pumunta tungkol sa paggawa na ito? 860 00:37:21,880 --> 00:37:24,850 Well, ipaalam sa akin sige at isulat isang mabilis na programa dito. 861 00:37:24,850 --> 00:37:31,600 Pupunta ako sa sige at gawin ito bilang sumusunod. 862 00:37:31,600 --> 00:37:33,910 Sabihin tumawag ito - 863 00:37:33,910 --> 00:37:38,070 ano ang gusto namin na tawagan ang isang ito? 864 00:37:38,070 --> 00:37:38,650 >> Talaga, hindi. 865 00:37:38,650 --> 00:37:39,420 Hayaan akong rewind. 866 00:37:39,420 --> 00:37:41,220 Hindi ko nais upang gawin iyon cliffhanger pa. 867 00:37:41,220 --> 00:37:42,270 Ito ay palayawin ang saya. 868 00:37:42,270 --> 00:37:43,600 Natin gawin ito sa halip. 869 00:37:43,600 --> 00:37:47,430 >> Ipagpalagay na gusto kong magsulat ng kaunti at programa na ngayon embraces ito 870 00:37:47,430 --> 00:37:48,700 ideya ng recursion. 871 00:37:48,700 --> 00:37:50,370 Ako uri ng nakuha nang mas maaga sa aking sarili doon. 872 00:37:50,370 --> 00:37:51,420 Pupunta ako sa gawin ang mga sumusunod. 873 00:37:51,420 --> 00:38:00,220 >> Una, ang isang mabilis na isama ng standard io.h, pati na rin ang kinabibilangan ng cs50.h. 874 00:38:00,220 --> 00:38:03,200 At pagkatapos ay ako pagpunta sa sige at ipinapahayag int pangunahing walang bisa 875 00:38:03,200 --> 00:38:04,360 sa karaniwang paraan. 876 00:38:04,360 --> 00:38:07,920 Ako natanto ko na misnamed ang file, sa gayon hayaan mo akong magdagdag lang ng isang. extension c dito kaya 877 00:38:07,920 --> 00:38:09,510 na maaari naming ipunin ito nang maayos. 878 00:38:09,510 --> 00:38:10,970 Simulan ang pag-andar na ito off. 879 00:38:10,970 --> 00:38:13,290 >> At ang function na gusto kong isulat, medyo lamang, ay isa na itinatanong ang 880 00:38:13,290 --> 00:38:16,210 gumagamit para sa isang numero at pagkatapos ay nagdadagdag up ang lahat ng mga numero sa pagitan na 881 00:38:16,210 --> 00:38:19,920 numero at, sabihin nating, 0. 882 00:38:19,920 --> 00:38:22,510 Kaya unang pupuntahan ko sige at ipinapahayag int n. 883 00:38:22,510 --> 00:38:24,760 Pagkatapos ay kokopyahin ang ilang mga code na kami na ginagamit para sa isang habang. 884 00:38:24,760 --> 00:38:26,660 Habang ang isang bagay ay totoo. 885 00:38:26,660 --> 00:38:28,000 Kukunin ko ay bumalik sa na sa ilang sandali. 886 00:38:28,000 --> 00:38:29,010 >> Ano ang gusto kong gawin? 887 00:38:29,010 --> 00:38:33,460 Gusto kong sabihin printf positibong mangyaring integer. 888 00:38:33,460 --> 00:38:36,130 At pagkatapos ay pupuntahan ko sabihin n nakakakuha makakuha ng int. 889 00:38:36,130 --> 00:38:38,800 Kaya muli, ang ilang mga boilerplate code na aming ginamit bago. 890 00:38:38,800 --> 00:38:40,810 At ako pagpunta sa gawin ito habang n Mababa sa 1. 891 00:38:40,810 --> 00:38:44,120 Kaya ito ay tinitiyak na ang mga gumagamit ay nagbibigay sa akin ng isang positibong integer. 892 00:38:44,120 --> 00:38:45,490 >> At ngayon ako pagpunta sa gawin ang mga sumusunod. 893 00:38:45,490 --> 00:38:51,020 Gusto kong magdagdag ng hanggang ang lahat ng mga numero sa pagitan ng 1 at at n, o 0 at n, 894 00:38:51,020 --> 00:38:52,570 equivalently, upang makuha ang kabuuang sum. 895 00:38:52,570 --> 00:38:55,100 Kaya ang malaking simbolo palatandaan na maaari mong isipin ang. 896 00:38:55,100 --> 00:38:59,050 Kaya ako ng pagpunta sa gawin ito sa pamamagitan ng pagtawag sa unang isang function na tinatawag na palatandaan, 897 00:38:59,050 --> 00:39:06,030 pagpasa ito sa n, at pagkatapos ay pupuntahan ko sabihin printf, ang sagot ay kanan doon. 898 00:39:06,030 --> 00:39:08,180 >> Kaya sa maikling, kumuha ako at int mula sa user. 899 00:39:08,180 --> 00:39:09,280 Ko matitiyak na ito ay positibo. 900 00:39:09,280 --> 00:39:12,700 Ipinahahayag ko sa isang variable na tinatawag na sagot ng Uri ng int at iimbak sa ito ang balik 901 00:39:12,700 --> 00:39:15,610 halaga ng mga palatandaan, pagpasa sa n bilang input. 902 00:39:15,610 --> 00:39:17,060 At pagkatapos kong i-print out na sagot. 903 00:39:17,060 --> 00:39:19,550 >> Sa kasamaang palad, kahit na palatandaan tunog tulad ng isang bagay na maaaring maging sa 904 00:39:19,550 --> 00:39:24,040 ang math.h file, deklarasyon nito, ito ay talagang hindi. 905 00:39:24,040 --> 00:39:24,690 Kaya iyon ang OK. 906 00:39:24,690 --> 00:39:26,170 Maaari ko bang ipatupad ang sarili ko. 907 00:39:26,170 --> 00:39:29,160 Pupunta ako sa ipatupad ang isang function na tinatawag na palatandaan, at ito ay pagpunta sa kumuha ng isang 908 00:39:29,160 --> 00:39:29,900 parameter - 909 00:39:29,900 --> 00:39:32,100 sabihin lang tumawag ito m, lamang kaya iba ito. 910 00:39:32,100 --> 00:39:35,910 At pagkatapos ay i-up dito, pupuntahan ko sabihin, well, kung m ay mas mababa sa 1 - ito ay isang 911 00:39:35,910 --> 00:39:38,180 napaka hindi kawili-wili programa. 912 00:39:38,180 --> 00:39:41,700 Kaya pupuntahan ko sige at agad na bumalik 0. 913 00:39:41,700 --> 00:39:45,920 Ito lamang ay hindi magkaroon ng kahulugan upang magdagdag ng hanggang ang lahat ng ang mga numero sa pagitan ng 1 at m kung m 914 00:39:45,920 --> 00:39:48,470 mismo ay 0 o negatibo. 915 00:39:48,470 --> 00:39:50,900 >> At pagkatapos ay ako pagpunta sa sige at gawin ito napaka iteratively. 916 00:39:50,900 --> 00:39:53,090 Pupuntahan ko na gawin ang ganitong uri ng lumang-paaralan, at pupuntahan ko sige 917 00:39:53,090 --> 00:39:57,150 at sabihin na pupuntahan ko magpahayag ng isang kabuuan sa 0. 918 00:39:57,150 --> 00:39:59,630 Pagkatapos ay pupuntahan ko mayroon isang para sa loop ng int - 919 00:39:59,630 --> 00:40:02,820 at ipaalam sa akin gawin ito upang tumugma sa aming pamamahagi code, kaya mayroon kang isang kopya 920 00:40:02,820 --> 00:40:07,500 sa bahay. int i makakakuha ng 1 sa hanggang sa i mas mababa sa o katumbas ng m. 921 00:40:07,500 --> 00:40:09,430 i plus plus. 922 00:40:09,430 --> 00:40:11,430 At pagkatapos ay sa loob ng mga ito para sa loop - 923 00:40:11,430 --> 00:40:12,440 Ikinalulungkot namin halos doon - 924 00:40:12,440 --> 00:40:15,810 sum ay nakakakuha ng sum plus 1. 925 00:40:15,810 --> 00:40:17,670 At pagkatapos ay ako pagpunta sa bumalik ang kabuuan. 926 00:40:17,670 --> 00:40:19,420 >> Kaya ko ginawa ito nang mabilis, medyo tinatanggap na. 927 00:40:19,420 --> 00:40:22,775 Ngunit muli, ang pangunahing function na ay medyo tuwiran, batay sa code na namin 928 00:40:22,775 --> 00:40:23,190 nakasulat kaya malayo. 929 00:40:23,190 --> 00:40:25,610 Gumagamit ang dual loop upang makakuha ng positibong int mula sa user. 930 00:40:25,610 --> 00:40:29,870 Pagkatapos kong pumasa na int sa isang bagong pag-andar tinatawag na palatandaan, pagtawag ito, muli, n. 931 00:40:29,870 --> 00:40:33,100 At mag-store ko ang return value, ang kasagutan mula sa itim na kahon sa kasalukuyan 932 00:40:33,100 --> 00:40:35,460 Kilala bilang palatandaan, sa isang variable tinatawag na sagot. 933 00:40:35,460 --> 00:40:36,580 Pagkatapos ko i-print ito. 934 00:40:36,580 --> 00:40:39,090 >> Kung namin ngayon magpatuloy sa kuwento, paano palatandaan ay ipinatupad? 935 00:40:39,090 --> 00:40:40,840 Ipanukala ko upang ipatupad tulad ng sumusunod. 936 00:40:40,840 --> 00:40:43,560 Una, ng kaunting error-checking upang tiyakin na ang gumagamit ay hindi 937 00:40:43,560 --> 00:40:46,480 panggugulo sa akin at sa pagpasa sa ilang mga negatibong o 0 halaga. 938 00:40:46,480 --> 00:40:49,710 Pagkatapos kong idedeklara sa isang variable na tinatawag na sabihin sa ilang at itakda ito sa 0. 939 00:40:49,710 --> 00:40:55,910 >> At ngayon ako magsisimulang upang ilipat mula sa i katumbas 1 ang lahat ng mga paraan ng hanggang sa at kabilang ang m, 940 00:40:55,910 --> 00:41:00,130 dahil gusto ko upang isama ang lahat ng mga numero mula sa isa sa pamamagitan ng m, inclusive. 941 00:41:00,130 --> 00:41:04,350 At sa loob ng mga ito para sa loop, ko lang gawin sum ay nakakakuha ng anumang ito ay ngayon, pati ang 942 00:41:04,350 --> 00:41:08,900 halaga ng i. 943 00:41:08,900 --> 00:41:10,370 Plus ang halaga ng i. 944 00:41:10,370 --> 00:41:14,090 >> Bilang isang tabi, kung hindi mo nakita ito bago, mayroong ilang mga sintaktik asukal 945 00:41:14,090 --> 00:41:14,870 para sa linyang ito. 946 00:41:14,870 --> 00:41:21,120 Maaari ko bang isulat na muli ito bilang katumbas ng plus i, lamang i-save ang sarili ko ng ilang mga keystroke 947 00:41:21,120 --> 00:41:22,570 at upang tumingin ng kaunti mas cool. 948 00:41:22,570 --> 00:41:23,140 Ngunit iyon lamang ang lahat. 949 00:41:23,140 --> 00:41:24,660 Ito ay halos pareho sa pagtakbo bagay. 950 00:41:24,660 --> 00:41:26,710 >> Sa kasamaang palad, ang code na ito sa hindi pagpunta sa sumulat ng libro pa. 951 00:41:26,710 --> 00:41:31,600 Kung nagpapatakbo ako gumawa palatandaan 0, paano am Ako pagpunta upang yelled sa? 952 00:41:31,600 --> 00:41:33,473 Ano kaya ito ng pagpunta sa hindi gusto? 953 00:41:33,473 --> 00:41:35,740 >> Madla: [hindi marinig]. 954 00:41:35,740 --> 00:41:37,800 >> David MALAN: Oo, hindi ko idedeklara ang pagpapaandar up tuktok, tama? 955 00:41:37,800 --> 00:41:40,590 C ay uri ng bobo, sa na ito lamang kung ano ang ibig sabihin mo ito gawin, at ikaw 956 00:41:40,590 --> 00:41:41,880 kailangang gawin ito sa na order. 957 00:41:41,880 --> 00:41:45,910 At kaya kung ako pindutin ang Enter dito, pupuntahan ko makakuha ng isang babala tungkol sa palatandaan implicit 958 00:41:45,910 --> 00:41:46,860 deklarasyon. 959 00:41:46,860 --> 00:41:48,120 >> Oh, hindi problema. 960 00:41:48,120 --> 00:41:50,370 Maaari ba akong mag-up sa tuktok, at maaari ko sabihin, ang lahat ng karapatan, maghintay ng isang minuto. 961 00:41:50,370 --> 00:41:54,240 Sigma ay isang function na nagbabalik isang int at ito Inaasahan ng isang 962 00:41:54,240 --> 00:41:56,620 int bilang input, tuldok-kuwit. 963 00:41:56,620 --> 00:41:59,550 O maaari ko bang ilagay ang buong pag-andar sa itaas pangunahing, ngunit sa pangkalahatan, Gusto ko 964 00:41:59,550 --> 00:42:02,260 Inirerekumenda laban na, dahil ito ay Nice upang laging may pangunahing sa tuktok kaya 965 00:42:02,260 --> 00:42:06,310 maaari kang sumisid karapatan sa at alam kung ano ang isang programa ay ginagawa sa pamamagitan ng pagbabasa pangunahing muna. 966 00:42:06,310 --> 00:42:07,930 >> Kaya ngayon hayaan mo akong i-clear ang screen. 967 00:42:07,930 --> 00:42:09,330 Muling paggawa palatandaan 0. 968 00:42:09,330 --> 00:42:10,340 Ang lahat ay tila mag-check out. 969 00:42:10,340 --> 00:42:11,970 Hayaan akong magpatakbo palatandaan 0. 970 00:42:11,970 --> 00:42:12,770 Positibong ilibing. 971 00:42:12,770 --> 00:42:15,580 Kukunin ko bigyan ito ang bilang 3 upang panatilihin itong simple. 972 00:42:15,580 --> 00:42:18,710 Kaya na dapat magbigay sa akin 3 plus 2 plus 1, kaya 6. 973 00:42:18,710 --> 00:42:20,750 Ipasok, at sa katunayan nakukuha ko 6. 974 00:42:20,750 --> 00:42:21,820 >> Ang maaari kong gawin ng isang bagay na mas malaki - 975 00:42:21,820 --> 00:42:24,080 50, 12, 75. 976 00:42:24,080 --> 00:42:27,690 Tulad ng isang tanghente, pupuntahan ko gawin isang bagay na katawa-tawa tulad ng isang talagang malaking 977 00:42:27,690 --> 00:42:30,375 numero, Oh, na aktwal na nagtrabaho out - 978 00:42:30,375 --> 00:42:31,600 eh, Hindi sa tingin ko na tama. 979 00:42:31,600 --> 00:42:32,810 Tayo'y makita. 980 00:42:32,810 --> 00:42:34,060 Natin talaga Nagkamali gamit ito. 981 00:42:34,060 --> 00:42:37,150 982 00:42:37,150 --> 00:42:38,400 >> Iyan ay isang problema. 983 00:42:38,400 --> 00:42:43,180 984 00:42:43,180 --> 00:42:44,970 Ano kaya ang nangyari? 985 00:42:44,970 --> 00:42:46,050 Ang code ay hindi na masama. 986 00:42:46,050 --> 00:42:48,470 Ito ay pa rin linear. 987 00:42:48,470 --> 00:42:50,810 Sumisipol ay isang mahusay na epekto, bagaman. 988 00:42:50,810 --> 00:42:52,060 Ano kaya ang nangyari? 989 00:42:52,060 --> 00:42:54,700 990 00:42:54,700 --> 00:42:55,620 >> Hindi sigurado kung Narinig ko ito. 991 00:42:55,620 --> 00:42:57,620 Kaya ito lumiliko out - at ito ay bilang isang bukod. 992 00:42:57,620 --> 00:42:59,400 Ito ay hindi core sa ideya ng recursion. 993 00:42:59,400 --> 00:43:02,480 Ito ay lumiliko out, dahil sinusubukan ko upang Kinakatawan tulad ng isang malaking bilang, karamihan 994 00:43:02,480 --> 00:43:06,980 malamang ito ay misinterpreted sa pamamagitan ng C bilang isang hindi positibong numero, 995 00:43:06,980 --> 00:43:09,980 ngunit negatibong numero. 996 00:43:09,980 --> 00:43:12,690 >> Hindi pa kami uusapang tungkol sa ito, ngunit ito lumiliko out may mga negatibong numero 997 00:43:12,690 --> 00:43:14,210 sa mundo bilang karagdagan sa positibong numero. 998 00:43:14,210 --> 00:43:16,290 At ang paraan kung saan maaari kang kumakatawan sa isang negatibong numero 999 00:43:16,290 --> 00:43:19,530 talaga ay, gamitin mo ang isa espesyal na sandali upang ipahiwatig 1000 00:43:19,530 --> 00:43:20,400 positibo sa paglipas ng mga negatibong. 1001 00:43:20,400 --> 00:43:22,950 Ito ay isang maliit na mas kumplikado kaysa sa na, ngunit iyon ang pangunahing ideya. 1002 00:43:22,950 --> 00:43:26,740 >> Kaya sa kasamaang-palad, kung C ay nakakalito isa ng mga piraso ng kung aktwal ibig sabihin, 1003 00:43:26,740 --> 00:43:30,790 oh, ito ay isang negatibong numero, ang aking loop dito, halimbawa, ay talagang hindi kailanman 1004 00:43:30,790 --> 00:43:31,740 pagpunta sa wakasan. 1005 00:43:31,740 --> 00:43:33,850 Kaya kung talagang ako ay pag-print ng isang bagay muli at muli, kami ay 1006 00:43:33,850 --> 00:43:34,650 makita ang isang buong lot. 1007 00:43:34,650 --> 00:43:36,220 Ngunit muli, ito ay bukod sa punto. 1008 00:43:36,220 --> 00:43:38,590 Ito ay talagang lamang ng isang uri ng intelektwal na pag-usisa na kami ay dumating 1009 00:43:38,590 --> 00:43:39,550 i-back sa kalaunan. 1010 00:43:39,550 --> 00:43:43,400 Ngunit para sa ngayon, ito ay isang tamang pagpapatupad kung ipinapalagay namin na ang 1011 00:43:43,400 --> 00:43:45,970 user ay magbibigay ng ints na akma sa loob ng ints. 1012 00:43:45,970 --> 00:43:49,370 >> Pero inaangkin ko na ang code na ito, lantaran, ma-nagagawa mas simple. 1013 00:43:49,370 --> 00:43:54,060 Kung ang layunin sa kamay ay upang kumuha ng isang numero tulad m at magdagdag ng hanggang ang lahat ng mga 1014 00:43:54,060 --> 00:43:59,510 mga numero sa pagitan ng ito at ang 1, o pasalungat sa pagitan ng 1 at ito, inaangkin ko 1015 00:43:59,510 --> 00:44:03,380 na maaari ko bang hiramin ang ideya na pagsamahin sort nagkaroon, kung saan ito ay tumatagal ng problema 1016 00:44:03,380 --> 00:44:05,660 na ganito ang laki at paghahati nito sa isang bagay na mas maliit. 1017 00:44:05,660 --> 00:44:09,875 Siguro hindi kalahati, ngunit mas maliit, ngunit representatively ang parehong. 1018 00:44:09,875 --> 00:44:12,130 Parehong mga ideya, ngunit isang mas maliit na problema. 1019 00:44:12,130 --> 00:44:15,470 >> Kaya talaga ako - hayaan mo akong i-save ang file na ito gamit ang ibang numero ng bersyon. 1020 00:44:15,470 --> 00:44:17,670 Susubukan naming tawagan ang bersyon na ito 1 sa halip na 0. 1021 00:44:17,670 --> 00:44:20,790 At inaangkin ko na makakaya ko talaga reimplement ito sa ganitong uri ng 1022 00:44:20,790 --> 00:44:22,160 isip-baluktot na paraan. 1023 00:44:22,160 --> 00:44:23,710 >> Pupunta ako sa umalis bahagi nito nag-iisa. 1024 00:44:23,710 --> 00:44:27,710 Pupunta ako sa sinasabi kung m ay mas mababa mababa sa o kahit na katumbas ng 0 - 1025 00:44:27,710 --> 00:44:29,280 Lamang ako ng pagpunta sa maging isang maliit na mas anal oras na ito 1026 00:44:29,280 --> 00:44:30,520 kasama ang aking mga error checking - 1027 00:44:30,520 --> 00:44:33,190 Pupunta ako sa sige at bumalik 0. 1028 00:44:33,190 --> 00:44:34,490 Ito ay di-makatwirang. 1029 00:44:34,490 --> 00:44:37,500 Lamang ako ay simpleng pagpapasya kung ang user Binibigyan ako ng isang negatibong numero, ako 1030 00:44:37,500 --> 00:44:41,490 bumabalik na 0, at dapat nilang Nabasa ang dokumentasyon ng malapitan. 1031 00:44:41,490 --> 00:44:42,170 >> Iba Pa - 1032 00:44:42,170 --> 00:44:44,070 mapansin kung ano ako ng pagpunta sa gawin. 1033 00:44:44,070 --> 00:44:49,260 Iba Pa ako pagpunta sa bumalik m plus - 1034 00:44:49,260 --> 00:44:51,010 ano ang palatandaan ng m? 1035 00:44:51,010 --> 00:44:56,710 Well, palatandaan ng m plus m minus 1, plus m minus 2, plus m minus 3. 1036 00:44:56,710 --> 00:44:58,030 Hindi ko nais upang isulat ang lahat ng na out. 1037 00:44:58,030 --> 00:44:59,120 Bakit hindi ko lang magtikin? 1038 00:44:59,120 --> 00:45:05,080 Recursively tumawag sa aking sarili na may isang bahagyang mas maliit problema, tuldok-kuwit, 1039 00:45:05,080 --> 00:45:06,840 at tumawag ito ng isang araw? 1040 00:45:06,840 --> 00:45:07,040 >> I-right? 1041 00:45:07,040 --> 00:45:10,980 Ngayon dito, masyadong, maaari mong huwag mag-o-alala na ito ay isang walang-katapusang loop na ako 1042 00:45:10,980 --> 00:45:15,450 pampalaglag, kung saan ako ay pagpapatupad palatandaan sa pamamagitan ng pagtawag ng palatandaan. 1043 00:45:15,450 --> 00:45:20,342 Ngunit iyon lamang ang perpektong OK, dahil ako Naisip maaga isang idinagdag na mga linya? 1044 00:45:20,342 --> 00:45:22,600 >> Madla: [hindi marinig]. 1045 00:45:22,600 --> 00:45:25,430 >> David MALAN: 23-26, na ay ang aking kung kondisyon. 1046 00:45:25,430 --> 00:45:28,390 Dahil kung ano ang maganda tungkol sa palabawasan dito, dahil panatilihing ako 1047 00:45:28,390 --> 00:45:31,180 handing palatandaan mas maliit na problema, mas maliit problema, mas maliit - hindi ito 1048 00:45:31,180 --> 00:45:31,870 kalahati ng laki. 1049 00:45:31,870 --> 00:45:34,380 Ito ay lamang ng isang sanggol hakbang na mas maliit, ngunit iyon ang OK. 1050 00:45:34,380 --> 00:45:38,050 Dahil sa huli, makikipagtulungan kami ang aming paraan down sa 1 o 0. 1051 00:45:38,050 --> 00:45:41,630 At sa sandaling pindutin namin 0, palatandaan ay hindi pagpunta sa tawagan mismo nakikita. 1052 00:45:41,630 --> 00:45:43,590 Ito ay pagpunta sa agad na bumalik 0. 1053 00:45:43,590 --> 00:45:47,960 >> Kaya ang epekto, kung uri ng hangin na ito up sa iyong isip, ay ang magdagdag ng m plus 1054 00:45:47,960 --> 00:45:52,740 m minus 1, plus m minus 2, plus minus m 3, plus tuldok, tuldok, tuldok, m minus 1055 00:45:52,740 --> 00:45:57,820 m, sa huli pagbibigay sa iyo ng 0, at ang epekto sa huli ay upang idagdag ang lahat ng 1056 00:45:57,820 --> 00:45:59,070 mga bagay na ito nang magkakasama. 1057 00:45:59,070 --> 00:46:02,380 Kaya kami ay may hindi, may recursion, malutas ang problema na namin 1058 00:46:02,380 --> 00:46:03,470 Hindi ma-solve bago. 1059 00:46:03,470 --> 00:46:06,840 Sa katunayan, 0 bersyon ng ito, at ang bawat problema sa petsa, ay naging nalulusaw 1060 00:46:06,840 --> 00:46:09,980 sa pamamagitan lamang ng paggamit para sa mga loop o habang mga loop o katulad na mga constructs. 1061 00:46:09,980 --> 00:46:13,150 >> Ngunit recursion, sa palagay ko, ay nagbibigay sa amin ang ibang paraan ng pag-iisip tungkol sa 1062 00:46:13,150 --> 00:46:17,010 problema, kung saan kung maaari naming maglaan ng problema, hatiin ito mula sa isang bagay 1063 00:46:17,010 --> 00:46:22,340 medyo malaki sa isang bagay na medyo mas maliit, inaangkin ko na maaari naming malutas ito 1064 00:46:22,340 --> 00:46:26,040 marahil ng kaunti pa elegante sa tuntunin ng mga disenyo, na may mas kaunting code, 1065 00:46:26,040 --> 00:46:30,980 at marahil kahit na malutas ang mga problema na gagawin maging mahirap, pati na bibigyan namin ng kalaunan 1066 00:46:30,980 --> 00:46:33,280 makita, solve pulos iteratively. 1067 00:46:33,280 --> 00:46:35,980 >> Ngunit ang cliffhanger na aking ginawa nais na mag-iwan sa amin noon ay sa ito. 1068 00:46:35,980 --> 00:46:40,720 Hayaan akong sige at buksan up ng isang file mula sa - 1069 00:46:40,720 --> 00:46:44,300 talaga, hayaan mo akong pumunta at gawin ito real mabilis. 1070 00:46:44,300 --> 00:46:46,875 Hayaan akong sige at ipanukala ang mga sumusunod na. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Kabilang sa mga code na ngayong araw ay ang file na ito dito. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 Ito ang isa dito, noswap. 1075 00:47:03,050 --> 00:47:06,260 >> Kaya ito ay isang maliit na nakababagod programa na Ako whipped up na claim na gawin 1076 00:47:06,260 --> 00:47:06,940 ang mga sumusunod na. 1077 00:47:06,940 --> 00:47:10,140 Sa pangunahing, ito muna declares isang int tinatawag na x at nagtatalaga ito 1078 00:47:10,140 --> 00:47:11,100 ang halaga ng 1. 1079 00:47:11,100 --> 00:47:13,520 Pagkatapos ito declares isang int y at Nagtatalaga ito ang halaga 2. 1080 00:47:13,520 --> 00:47:15,310 Pagkatapos ito prints out kung ano ang x at y ay. 1081 00:47:15,310 --> 00:47:17,781 Pagkatapos ay sinasabi nito, pagpapalit, tuldok tuldok tuldok. 1082 00:47:17,781 --> 00:47:21,670 >> Pagkatapos ito ang sinasabing ay pagtawag ng isang function tinatawag makipagpalitan ng, pagpasa sa x at 1083 00:47:21,670 --> 00:47:24,290 y, ang ideya ng kung saan ay na sana x at y ay bumalik 1084 00:47:24,290 --> 00:47:25,620 naiiba, ang kabaligtaran. 1085 00:47:25,620 --> 00:47:27,110 Pagkatapos ay i-claim ito swapped! 1086 00:47:27,110 --> 00:47:28,420 may isang tandang padamdam. 1087 00:47:28,420 --> 00:47:30,190 Pagkatapos ito prints out x at y. 1088 00:47:30,190 --> 00:47:33,480 >> Ngunit ito lumiliko out na ito napaka simpleng demonstration pababa 1089 00:47:33,480 --> 00:47:35,570 dito ay ang tunay maraming surot. 1090 00:47:35,570 --> 00:47:38,870 Kahit na ako deklarasyon ng pansamantalang variable at pansamantalang paglalagay ng sa 1091 00:47:38,870 --> 00:47:42,010 ito, pagkatapos ay ako reassigning ng ang halaga ng b - 1092 00:47:42,010 --> 00:47:45,080 na palagay ng makatwirang, dahil nag ko nai-save ang isang kopya ng isang sa Temp. 1093 00:47:45,080 --> 00:47:48,410 Pagkatapos ay i-update ko b-pantay na ano ay nasa Temp. 1094 00:47:48,410 --> 00:47:51,610 Ang ganitong uri ng shell laro ng paglipat ng isang sa b at b papunta sa isang sa pamamagitan ng paggamit na ito 1095 00:47:51,610 --> 00:47:54,360 gitna-tao na tinatawag na palagay ng Temp ganap na ganap makatwirang. 1096 00:47:54,360 --> 00:47:57,270 >> Pero inaangkin ko na kapag nagpatakbo ako ito code, dahil kakailanganin kong gawin ngayon - 1097 00:47:57,270 --> 00:47:59,490 ipaalam sa akin sige lang at i-paste ito sa dito. 1098 00:47:59,490 --> 00:48:01,995 Tatawag ako ito noswap.c. 1099 00:48:01,995 --> 00:48:05,630 At bilang ang pangalan nagmumungkahi, ito ay hindi pagpunta sa maging isang tamang programa. 1100 00:48:05,630 --> 00:48:09,460 Gawing noswap. / Hindi makipagpalitan. 1101 00:48:09,460 --> 00:48:12,110 x ay 1, y ay 2, pagpapalit, swapped. 1102 00:48:12,110 --> 00:48:14,220 x ay 1, y ay 2. 1103 00:48:14,220 --> 00:48:16,920 Ito ay sa panimula mali, kahit na bagaman ito ay tila ganap na ganap 1104 00:48:16,920 --> 00:48:17,730 makatwirang sa akin. 1105 00:48:17,730 --> 00:48:21,330 At doon ay isang dahilan, ngunit kami ay hindi pagpunta sa ibunyag ang dahilan lamang pa. 1106 00:48:21,330 --> 00:48:24,610 >> Para sa ngayon ang pangalawang cliffhanger Nais kong umalis ka ay may ito, isang 1107 00:48:24,610 --> 00:48:27,120 anunsyo ng ibang mga klase sa mga code ng kupon. 1108 00:48:27,120 --> 00:48:31,590 Ang aming mga makabagong ideya na may late na araw sa taong ito ay provoked isang non-walang halaga bilang 1109 00:48:31,590 --> 00:48:33,830 ng mga katanungan, na noon ay hindi aming intensyon. 1110 00:48:33,830 --> 00:48:36,590 Ang intensyon ng mga code ng kupon, kung saan gawin kung bahagi ka ng problema 1111 00:48:36,590 --> 00:48:39,850 itakda maaga, at dahil doon nakakakuha ng isang extrang araw, ay talagang upang matulungan kang makatulong na guys 1112 00:48:39,850 --> 00:48:42,420 simulan ang iyong sarili nang maaga, pag-uuri sa pamamagitan ng incentivizing mo. 1113 00:48:42,420 --> 00:48:44,880 Tumutulong sa amin ipamahagi sa buong load opisina ng mas mahusay na oras upang ang 1114 00:48:44,880 --> 00:48:45,740 ito ay isang uri ng manalo-manalo. 1115 00:48:45,740 --> 00:48:48,860 >> Sa kasamaang palad, sa tingin ko ang aking tagubilin hindi naging, sa petsa, napakalinaw, kaya 1116 00:48:48,860 --> 00:48:52,230 Nagpunta ako pabalik na ito katapusan ng linggo at na-update ang spec sa mas malaki, mas agresibong mga teksto sa 1117 00:48:52,230 --> 00:48:53,600 ipaliwanag bullet tulad ng mga ito. 1118 00:48:53,600 --> 00:48:56,900 At para lamang ito sinasabi pa sa publiko, sa pamamagitan ng default, ang problema sets ay dahil Huwebes 1119 00:48:56,900 --> 00:48:58,400 sa tanghali, sa bawat ang syllabus. 1120 00:48:58,400 --> 00:49:02,030 Kung nagsimula ka nang maaga, pagtatapos bahagi ng ang problema itinakda ng Miyerkules sa 12:00 1121 00:49:02,030 --> 00:49:05,170 PM, ang mga bahagi na nauugnay sa isang kupon code, ang ideya ay na maaari mong pahabain 1122 00:49:05,170 --> 00:49:07,710 iyong deadline para sa P itakda hanggang Biyernes. 1123 00:49:07,710 --> 00:49:10,890 Iyon ay, ang bit-off ang isang napakaliit na bahagi ng P set na may kaugnayan sa kung ano ang karaniwang ay ang 1124 00:49:10,890 --> 00:49:13,200 mas malaking problema, at bumili ka iyong sarili ng dagdag na araw. 1125 00:49:13,200 --> 00:49:15,190 Muli, ito ay nakakakuha ka ng pag-iisip tungkol sa ang problema set, nakakakuha ka sa 1126 00:49:15,190 --> 00:49:16,380 opisina oras mas maaga. 1127 00:49:16,380 --> 00:49:20,670 Ngunit ang kupon code problema pa rin ang kailangan, kahit na hindi mo isumite ito. 1128 00:49:20,670 --> 00:49:23,340 >> Ngunit higit pa compellingly ay ito. 1129 00:49:23,340 --> 00:49:26,520 (Stage bulong) At ang mga tao umaalis maagang gonna ay ikinalulungkot ito. 1130 00:49:26,520 --> 00:49:28,620 Habang ang mga tao sa balkonahe. 1131 00:49:28,620 --> 00:49:32,510 Humihingi ako ng paumanhin sa maaga upang ang mga tao sa ang balkonahe para sa mga kadahilanang iyon ay magiging 1132 00:49:32,510 --> 00:49:33,920 i-clear sa loob lamang ng ilang sandali. 1133 00:49:33,920 --> 00:49:37,050 >> Kaya tayo ay masuwerte upang magkaroon ng isa sa Dating ulo CS50 ng pagtuturo sa Fellows 1134 00:49:37,050 --> 00:49:39,302 isang kumpanya na tinatawag na dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 Sila ay napaka maraming donasyon ng coupon code dito para sa mas espasyo, 1136 00:49:45,500 --> 00:49:48,180 na kung saan ay up mula sa karaniwan 2 gigabytes. 1137 00:49:48,180 --> 00:49:51,740 Kaya kung ano naisip ko na gusto naming gawin sa mga ito panghuling tala ay gawin ang isang bit ng isang giveaway, 1138 00:49:51,740 --> 00:49:55,380 kung saan sa loob lamang ng ilang sandali, ay namin ibinubunyag sa panalo at kung sino ang may isang kupon 1139 00:49:55,380 --> 00:49:57,980 code na maaari mong pagkatapos ay pumunta sa kanilang website, i-type ito sa, at voila, kumuha ng isang 1140 00:49:57,980 --> 00:50:01,370 buong maraming higit pa Dropbox espasyo para sa iyong appliance at para sa iyong personal na mga file. 1141 00:50:01,370 --> 00:50:05,690 >> At una sa lahat, na nais na lumahok sa ang guhit na ito? 1142 00:50:05,690 --> 00:50:09,630 OK, ngayon na ginagawang mas masaya. 1143 00:50:09,630 --> 00:50:14,010 Ang taong ito na natatanggap ng 25-gigabyte coupon code - na kung saan ay malayo 1144 00:50:14,010 --> 00:50:16,150 mas mabisa kaysa sa huli araw ngayon, siguro - 1145 00:50:16,150 --> 00:50:20,620 ay ang isa kung sino ang nakaupo sa tuktok ng isang upuan unan sa ilalim kung saan mayroong 1146 00:50:20,620 --> 00:50:21,620 na coupon code. 1147 00:50:21,620 --> 00:50:23,480 Maaari mo na ngayong tumingin sa ilalim ang iyong upuan unan. 1148 00:50:23,480 --> 00:50:28,710 1149 00:50:28,710 --> 00:50:29,680 >> [Video playback] 1150 00:50:29,680 --> 00:50:31,620 >> -Ang isa, dalawa, tatlo. 1151 00:50:31,620 --> 00:50:35,015 >> [Magaralgal] 1152 00:50:35,015 --> 00:50:35,985 >> -Mong makakuha ng isang kotse! 1153 00:50:35,985 --> 00:50:36,670 Makakakuha ka ng isang kotse! 1154 00:50:36,670 --> 00:50:37,970 >> David MALAN: Makikita natin mo sa Miyerkules. 1155 00:50:37,970 --> 00:50:38,904 >> -Mong makakuha ng isang kotse! 1156 00:50:38,904 --> 00:50:39,371 Makakakuha ka ng isang kotse! 1157 00:50:39,371 --> 00:50:40,305 Makakakuha ka ng isang kotse! 1158 00:50:40,305 --> 00:50:41,706 Makakakuha ka ng isang kotse! 1159 00:50:41,706 --> 00:50:43,107 Makakakuha ka ng isang kotse! 1160 00:50:43,107 --> 00:50:45,530 >> David MALAN: Balkonahe kakailanganin ng mga tao, dumating down na dito sa harap, 1161 00:50:45,530 --> 00:50:46,866 kung saan mayroon kaming mga extra. 1162 00:50:46,866 --> 00:50:50,282 >> -Lahat ng tao ay nakakakuha ng kotse! 1163 00:50:50,282 --> 00:50:52,234 Lahat ng tao ay nakakakuha ng kotse! 1164 00:50:52,234 --> 00:50:52,722 >> [END-playback ng video] 1165 00:50:52,722 --> 00:50:54,590 >> Tagapagsalaysay: Sa susunod na CS50 - 1166 00:50:54,590 --> 00:51:00,374 >> Tagapagsalita 5: Oh aking sus sus sus sus sus sus sus sus sus sus - 1167 00:51:00,374 --> 00:51:02,106 >> [UKELELE pag-play]