1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [CHWARAE CERDDORIAETH] 3 00:00:10,800 --> 00:00:13,500 DAVID Malan: Pob hawl. 4 00:00:13,500 --> 00:00:14,670 Mae pob hawl, croeso yn ôl. 5 00:00:14,670 --> 00:00:18,120 Felly, mae hyn yn Wythnos 4, y dechrau ohono, yn barod. 6 00:00:18,120 --> 00:00:21,320 A byddwch yn cofio bod yr wythnos diwethaf, rydym yn rhoi codio neilltuo ar gyfer ychydig bach 7 00:00:21,320 --> 00:00:24,240 ac yr ydym yn dechrau siarad ychydig yn fwy lefel uchel, am bethau fel 8 00:00:24,240 --> 00:00:28,130 chwilio a didoli, sydd, er syniadau braidd yn syml, yn cael eu 9 00:00:28,130 --> 00:00:31,840 cynrychiolydd o ddosbarth o broblemau byddwch yn dechrau i ddatrys arbennig 10 00:00:31,840 --> 00:00:34,820 wrth i chi ddechrau meddwl am terfynol prosiectau ac atebion diddorol yr ydych 11 00:00:34,820 --> 00:00:36,760 efallai y bydd rhaid i broblemau yn y byd go iawn. 12 00:00:36,760 --> 00:00:39,490 Nawr fath swigen yn un o'r symlaf algorithmau o'r fath, ac mae'n 13 00:00:39,490 --> 00:00:42,900 gweithio drwy gael niferoedd bach hyn mewn rhestr neu mewn math amrywiaeth o 14 00:00:42,900 --> 00:00:46,530 swigen eu ffordd i fyny i ben, ac mae'r rhifau mawr yn symud eu ffordd i lawr i 15 00:00:46,530 --> 00:00:47,930 ddiwedd y rhestr. 16 00:00:47,930 --> 00:00:50,650 >> A dwyn i gof y gallem ddychmygu fath swigen ychydig 17 00:00:50,650 --> 00:00:52,310 rhywbeth fel hyn. 18 00:00:52,310 --> 00:00:53,640 Felly, gadewch i mi fynd yn ei flaen a chliciwch Start. 19 00:00:53,640 --> 00:00:55,350 Rwyf wedi preselected fath swigen. 20 00:00:55,350 --> 00:00:58,920 Ac os ydych yn cofio bod y glas dalach llinellau cynrychioli rhifau mawr, bach 21 00:00:58,920 --> 00:01:03,300 llinellau glas yn cynrychioli rhifau bach, fel y inni fynd drwy hyn eto ac eto ac 22 00:01:03,300 --> 00:01:07,680 unwaith eto, gan gymharu dau far nesaf i bob eraill mewn coch, rydyn ni'n mynd i gyfnewid y 23 00:01:07,680 --> 00:01:11,010 mwyaf a'r lleiaf os eu bod allan o drefn. 24 00:01:11,010 --> 00:01:14,150 >> Felly, bydd hyn yn mynd ymlaen ac yn mynd ymlaen ac yn mynd ymlaen, a byddwch yn gweld bod y mwy o faint 25 00:01:14,150 --> 00:01:16,700 elfennau yn gwneud eu ffordd i'r iawn, ac elfennau llai yn 26 00:01:16,700 --> 00:01:17,900 gwneud eu ffordd i'r chwith. 27 00:01:17,900 --> 00:01:21,380 Ond rydym yn dechrau mesur effeithlonrwydd, y 28 00:01:21,380 --> 00:01:22,970 ansawdd y algorithm hwn. 29 00:01:22,970 --> 00:01:25,200 Ac rydym yn dweud bod yn y gwaethaf achos, cymerodd algorithm hwn 30 00:01:25,200 --> 00:01:27,940 yn fras faint o gamau? 31 00:01:27,940 --> 00:01:28,980 >> Felly n sgwâr. 32 00:01:28,980 --> 00:01:30,402 A beth oedd yn n? 33 00:01:30,402 --> 00:01:31,650 >> GYNULLEIDFA: Nifer o elfennau. 34 00:01:31,650 --> 00:01:32,790 >> DAVID Malan: Felly n oedd y nifer o elfennau. 35 00:01:32,790 --> 00:01:33,730 Ac felly byddwn yn gwneud hyn yn aml. 36 00:01:33,730 --> 00:01:36,650 Unrhyw bryd rydym eisiau siarad am faint o broblem neu faint o 37 00:01:36,650 --> 00:01:39,140 mewnbwn, neu faint o amser mae'n ei gymryd i gynhyrchu cynnyrch, byddwn ni yn unig 38 00:01:39,140 --> 00:01:41,610 gyffredinol beth bynnag mewnbwn fel n. 39 00:01:41,610 --> 00:01:45,970 Felly, yn ôl yn Wythnos 0, tudalennau y nifer yn y llyfr ffôn yn n. 40 00:01:45,970 --> 00:01:47,550 Mae nifer y myfyrwyr yn yr ystafell yn n. 41 00:01:47,550 --> 00:01:49,630 Felly yma, hefyd, rydym yn dilyn y patrwm hwnnw. 42 00:01:49,630 --> 00:01:52,800 >> Nawr n sgwâr nad ydynt yn arbennig o gyflym, felly rydym yn ceisio ei wneud yn well. 43 00:01:52,800 --> 00:01:55,970 Ac felly rydym yn edrych ar un neu ddau o algorithmau eraill, ymhlith y 44 00:01:55,970 --> 00:01:57,690 yn fath dethol. 45 00:01:57,690 --> 00:01:59,180 Felly fath dethol yn ychydig yn wahanol. 46 00:01:59,180 --> 00:02:03,130 Yr oedd bron yn symlach, mentraf ddweud, lle dechreuais ar ddechrau'r 47 00:02:03,130 --> 00:02:06,740 rhestr o'n gwirfoddolwyr a Fi jyst eto ac eto ac eto yn mynd drwy 48 00:02:06,740 --> 00:02:10,060 y rhestr, pluo y lleiaf elfen ar y tro a rhoi iddo ef neu 49 00:02:10,060 --> 00:02:13,040 hi ar ddechrau'r rhestr. 50 00:02:13,040 --> 00:02:16,410 >> Ond mae hyn, hefyd, ar ôl i ni ddechrau meddwl trwy y math ac yn fwy 51 00:02:16,410 --> 00:02:19,860 llun, meddwl am faint o weithiau Yr wyf yn mynd yn ôl ac ymlaen ac yn ôl 52 00:02:19,860 --> 00:02:24,090 ac ymlaen, yr ydym yn dweud yn yr achos gwaethaf, fath dethol, hefyd, oedd yr hyn? 53 00:02:24,090 --> 00:02:24,960 n sgwario. 54 00:02:24,960 --> 00:02:27,490 Nawr yn y byd go iawn, y gallai mewn gwirionedd ychydig yn gyflymach. 55 00:02:27,490 --> 00:02:30,620 Oherwydd unwaith eto, nid oedd rhaid i mi gadw camu'n ôl ar ôl i mi wedi datrys y 56 00:02:30,620 --> 00:02:31,880 elfennau lleiaf. 57 00:02:31,880 --> 00:02:35,090 Ond os ydym yn meddwl am n fawr iawn, ac os ydych yn fath o wneud y cwestiwn yn 58 00:02:35,090 --> 00:02:39,170 Wnes i ar y bwrdd, gyda'r n sgwâr rhywbeth minws, popeth arall 59 00:02:39,170 --> 00:02:41,850 ar wahân i'r n sgwâr, unwaith n yn mynd yn wirioneddol fawr, nid yw'n 60 00:02:41,850 --> 00:02:42,850 wirioneddol bwysig cymaint. 61 00:02:42,850 --> 00:02:45,470 Felly, fel gwyddonwyr cyfrifiadur, rydym yn datrys y troi llygad dall i'r llai 62 00:02:45,470 --> 00:02:49,220 ffactorau ac yn canolbwyntio yn unig ar y ffactor yn mynegiant mae hynny'n mynd i wneud 63 00:02:49,220 --> 00:02:50,330 y gwahaniaeth mwyaf. 64 00:02:50,330 --> 00:02:52,840 >> Wel, yn olaf, rydym yn edrych ar y math gosod. 65 00:02:52,840 --> 00:02:56,620 Ac mae hyn yn debyg o ran ysbryd, ond yn hytrach na mynd trwy iteraidd a 66 00:02:56,620 --> 00:03:01,250 dewis yr elfen lleiaf un ar y pryd, yr wyf yn hytrach yn cymryd y llaw fy mod 67 00:03:01,250 --> 00:03:04,070 Deliwyd, a phenderfynais, pob gywir, rydych yn perthyn yma. 68 00:03:04,070 --> 00:03:06,160 Yna mi symud ymlaen i'r elfen nesaf ac wedi penderfynu ei fod ef neu 69 00:03:06,160 --> 00:03:07,470 hi yn perthyn yma. 70 00:03:07,470 --> 00:03:08,810 Ac yna symudais ymlaen ac ymlaen. 71 00:03:08,810 --> 00:03:11,780 Ac yr wyf yn gallai i, ar hyd y ffordd, symud guys hyn er mwyn 72 00:03:11,780 --> 00:03:13,030 gwneud lle ar eu cyfer. 73 00:03:13,030 --> 00:03:16,880 Felly dyna oedd y math o gwrthdroad meddwl o'r fath dethol ein bod yn 74 00:03:16,880 --> 00:03:18,630 Gelwir fath gosod. 75 00:03:18,630 --> 00:03:20,810 >> Felly, y pynciau hyn i ddigwydd yn y byd go iawn. 76 00:03:20,810 --> 00:03:23,640 Dim ond ychydig flynyddoedd yn ôl, pan benodol Roedd seneddwr yn rhedeg am llywydd, 77 00:03:23,640 --> 00:03:27,160 Eric Schmidt, ar yr adeg y Prif Swyddog Gweithredol Google, wedi cael y cyfle mewn gwirionedd 78 00:03:27,160 --> 00:03:28,040 i gyfweld ag ef. 79 00:03:28,040 --> 00:03:32,010 Ac rydym yn meddwl y bydden ni'n rhannu hyn YouTube clip i chi yma, pe gallem droi i fyny 80 00:03:32,010 --> 00:03:32,950 y gyfrol. 81 00:03:32,950 --> 00:03:39,360 >> [VIDEO Playback] 82 00:03:39,360 --> 00:03:44,620 >> -Yn awr, Seneddwr, eich bod yma yn Google, ac yr wyf yn hoffi meddwl am y llywyddiaeth 83 00:03:44,620 --> 00:03:46,042 fel cyfweliad am swydd. 84 00:03:46,042 --> 00:03:47,770 >> [Chwerthin] 85 00:03:47,770 --> 00:03:50,800 >> -Nawr mae'n anodd cael swydd fel llywydd. 86 00:03:50,800 --> 00:03:52,480 A ydych yn mynd trwy y llymder awr. 87 00:03:52,480 --> 00:03:54,330 Mae hefyd yn anodd i gael swydd yn Google. 88 00:03:54,330 --> 00:03:59,610 Mae gennym gwestiynau ac rydym yn gofyn ein cwestiynau ymgeiswyr. 89 00:03:59,610 --> 00:04:02,250 Ac mae hyn yn un yn dod o Larry Schwimmer. 90 00:04:02,250 --> 00:04:05,325 >> [Chwerthin] 91 00:04:05,325 --> 00:04:06,400 -Rydych guys yn meddwl fy mod i'n kidding? 92 00:04:06,400 --> 00:04:08,750 Mae'n iawn yma. 93 00:04:08,750 --> 00:04:12,110 Beth yw'r ffordd fwyaf effeithlon o didoli miliwn o gyfanrifau dau-bit? 94 00:04:12,110 --> 00:04:15,810 >> [Chwerthin] 95 00:04:15,810 --> 00:04:18,260 >> -Wel, uh - 96 00:04:18,260 --> 00:04:19,029 >> -I'm ddrwg. 97 00:04:19,029 --> 00:04:19,745 Efallai dylem - 98 00:04:19,745 --> 00:04:21,000 >> -Na, na, na, na, na. 99 00:04:21,000 --> 00:04:21,470 >> -Nad yw 'na - 100 00:04:21,470 --> 00:04:22,185 OK. 101 00:04:22,185 --> 00:04:25,328 >> -Rwy'n credu y byddai'r math swigen yn y ffordd anghywir i fynd. 102 00:04:25,328 --> 00:04:26,792 >> [Chwerthin] 103 00:04:26,792 --> 00:04:28,510 >> [Bloeddio a chymeradwyaeth] 104 00:04:28,510 --> 00:04:31,211 >> -Dewch ar, a ddywedodd wrtho hyn? 105 00:04:31,211 --> 00:04:32,155 OK. 106 00:04:32,155 --> 00:04:33,350 >> [VIDEO END Playback] 107 00:04:33,350 --> 00:04:35,070 >> DAVID Malan: Felly dyna ni. 108 00:04:35,070 --> 00:04:39,600 Felly, rydym yn dechrau mesur y rhain yn rhedeg adegau, fel petai, gyda rhywbeth 109 00:04:39,600 --> 00:04:43,480 a elwir yn nodiant asymptotic, sydd yn dim ond cyfeirio at ein math o droi 110 00:04:43,480 --> 00:04:47,420 llygad dall i'r rhai ffactorau llai ac ond yn edrych ar yr amser yn rhedeg, 111 00:04:47,420 --> 00:04:51,250 perfformiad o algorithmau hyn, fel n mynd yn wirioneddol fawr dros gyfnod o amser. 112 00:04:51,250 --> 00:04:55,110 Ac felly rydym yn cyflwyno O. mawr a mawr O rhywbeth cynrychioli ein bod yn meddwl 113 00:04:55,110 --> 00:04:57,000 o fel rhwymo uchaf. 114 00:04:57,000 --> 00:04:59,570 Ac mewn gwirionedd, y Barri, gallwn ostwng na'r mic ychydig? 115 00:04:59,570 --> 00:05:01,040 >> Roeddem yn meddwl o hyn yn rhwymo uchaf. 116 00:05:01,040 --> 00:05:04,710 O mor fawr o n golygu sgwâr, mewn yr achos gwaethaf, rhywbeth fel 117 00:05:04,710 --> 00:05:07,780 Byddai fath dewis cymryd n camau sgwâr. 118 00:05:07,780 --> 00:05:10,310 Neu rywbeth fel math gosod Byddai n camau sgwâr. 119 00:05:10,310 --> 00:05:15,150 Nawr am rywbeth fel gosod fath, beth oedd yr achos gwaethaf? 120 00:05:15,150 --> 00:05:18,200 O ystyried amrywiaeth, beth yw'r gwaethaf senario posibl a allai fod yn 121 00:05:18,200 --> 00:05:20,650 eich hun yn wynebu? 122 00:05:20,650 --> 00:05:21,860 >> Mae'n hollol yn ôl, dde? 123 00:05:21,860 --> 00:05:24,530 Oherwydd os yw'n gwbl yn ôl, rhaid i chi wneud llawer iawn o waith. 124 00:05:24,530 --> 00:05:26,420 Oherwydd os ydych yn gyfan gwbl yn ôl, ydych yn mynd i ddod o hyd i'r 125 00:05:26,420 --> 00:05:28,840 elfen fwyaf yma, er bod mae'n perthyn i lawr yno. 126 00:05:28,840 --> 00:05:31,140 Felly, rydych chi'n mynd i ddweud, iawn, yn hyn o bryd, rydych yn perthyn yma, 127 00:05:31,140 --> 00:05:32,310 fel eich bod yn gadael ei ben ei hun. 128 00:05:32,310 --> 00:05:35,425 >> Yna byddwch yn sylweddoli, oh, damn, rhaid i mi symud yr elfen hon ychydig yn llai i 129 00:05:35,425 --> 00:05:36,470 y chwith i chi. 130 00:05:36,470 --> 00:05:38,770 Yna rhaid i mi wneud hynny eto ac eto ac eto. 131 00:05:38,770 --> 00:05:41,410 Ac os wyf yn cerdded yn ôl ac ymlaen, yr ydych yn Byddai datrys o deimlo perfformiad 132 00:05:41,410 --> 00:05:45,540 y algorithm, oherwydd gyson ydw i shuffling pawb arall i lawr yn y 133 00:05:45,540 --> 00:05:46,510 amrywiaeth i wneud lle ar ei gyfer. 134 00:05:46,510 --> 00:05:47,750 Felly dyna'r achos gwaethaf. 135 00:05:47,750 --> 00:05:48,570 >> Ar y llaw arall - 136 00:05:48,570 --> 00:05:50,320 ac roedd hyn yn Cliffhanger tro diwethaf - 137 00:05:50,320 --> 00:05:54,065 Dywedodd ein bod math mewnosod yn omega o beth? 138 00:05:54,065 --> 00:05:57,530 Beth yw'r redeg orau-achos amser o'r fath gosod? 139 00:05:57,530 --> 00:05:58,520 Felly mae'n n mewn gwirionedd. 140 00:05:58,520 --> 00:06:00,980 Dyna oedd y wag ein bod yn gadael ar y bwrdd tro diwethaf. 141 00:06:00,980 --> 00:06:03,160 >> Ac mae'n omega n oherwydd pham? 142 00:06:03,160 --> 00:06:06,630 Wel, yn yr achos gorau, beth fath gosod yn mynd i gael ei drosglwyddo? 143 00:06:06,630 --> 00:06:09,830 Wel, rhestr sy'n cael ei datrys yn llwyr eisoes, mae gwaith ychydig iawn i'w wneud. 144 00:06:09,830 --> 00:06:12,460 Ond yr hyn sy'n daclus am y math gosod yw ei fod oherwydd ei fod yn cychwyn yma a 145 00:06:12,460 --> 00:06:15,340 penderfynu, oh, yr ydych yn y nifer un, rydych yn perthyn yma. 146 00:06:15,340 --> 00:06:16,970 O, beth ffortiwn da. 147 00:06:16,970 --> 00:06:17,740 >> Rydych yn rhif dau. 148 00:06:17,740 --> 00:06:19,030 Rydych hefyd yn perthyn yma. 149 00:06:19,030 --> 00:06:21,010 Rhif tri, hyd yn oed yn well, ydych yn perthyn yma. 150 00:06:21,010 --> 00:06:25,210 Cyn gynted ag y mae'n mynd i ddiwedd y pseudocode rhestr, fesul mewnosod fath yn 151 00:06:25,210 --> 00:06:28,010 ein bod yn cerdded trwy lafar tro diwethaf, mae'n ei wneud. 152 00:06:28,010 --> 00:06:32,790 Ond didoli dewis, ar y llaw arall, cadw gwneud beth? 153 00:06:32,790 --> 00:06:35,260 >> Cadw mynd drwy'r rhestr eto ac eto ac eto. 154 00:06:35,260 --> 00:06:39,160 Oherwydd bod y mewnwelediad allweddol nad oedd ond unwaith y byddwch wedi edrych yr holl ffordd at y 155 00:06:39,160 --> 00:06:42,500 ddiwedd y rhestr, gallwch fod yn sicr bod yr elfen a ddewiswyd gennych oedd 156 00:06:42,500 --> 00:06:45,560 yn wir yr elfen lleiaf ar hyn o bryd. 157 00:06:45,560 --> 00:06:48,920 Felly mae'r rhain modelau meddyliol gwahanol diwedd i fyny cynhyrchu rhai byd go iawn iawn 158 00:06:48,920 --> 00:06:53,130 gwahaniaethau i ni, yn ogystal â'r gwahaniaethau asymptotic damcaniaethol. 159 00:06:53,130 --> 00:06:56,910 >> Felly, dim ond i ailadrodd, yna, mawr O n sgwâr, rydym wedi gweld rhai o'r fath 160 00:06:56,910 --> 00:06:58,350 algorithmau hyd yn hyn. 161 00:06:58,350 --> 00:06:59,580 O Big n? 162 00:06:59,580 --> 00:07:02,870 Beth 'an algorithm a allai gellir dweud i fod yn fawr O o n? 163 00:07:02,870 --> 00:07:06,930 Yn yr achos gwaethaf, mae'n cymryd nifer llinol o gamau. 164 00:07:06,930 --> 00:07:07,810 >> OK, chwiliad llinol. 165 00:07:07,810 --> 00:07:10,470 Ac yn yr achos gwaethaf, ble mae'r elfen rydych yn chwilio amdano wrth 166 00:07:10,470 --> 00:07:12,950 cymhwyso chwiliad llinol? 167 00:07:12,950 --> 00:07:14,680 >> OK, yn yr achos gwaethaf, nid yw hyd yn oed yno. 168 00:07:14,680 --> 00:07:17,000 Neu yn yr ail achos gwaethaf, mae'n yr holl ffordd yn y diwedd, sydd yn 169 00:07:17,000 --> 00:07:18,880 plus-neu-minws gwahaniaeth un-cam. 170 00:07:18,880 --> 00:07:21,180 Felly, ar ddiwedd y dydd, gallwn ddweud ei fod yn llinol. 171 00:07:21,180 --> 00:07:23,910 Byddai O Big n fod chwiliad llinol, oherwydd yn yr achos gwaethaf, y 172 00:07:23,910 --> 00:07:26,610 Nid yw hyd yn oed yn elfen yno neu ei fod yn yr holl ffordd ar y diwedd. 173 00:07:26,610 --> 00:07:29,370 >> Wel, mawr O o log o n. 174 00:07:29,370 --> 00:07:32,760 Doedden ni ddim yn siarad yn fanwl iawn am hyn, ond yr ydym wedi gweld hyn o'r blaen. 175 00:07:32,760 --> 00:07:36,840 Beth sydd yn rhedeg mewn hyn a elwir yn logarithmig amser, yn yr achos gwaethaf? 176 00:07:36,840 --> 00:07:38,500 >> Yeah, search mor deuaidd. 177 00:07:38,500 --> 00:07:42,930 Ac chwiliad deuaidd yn yr achos gwaethaf gallai fod yr elfen rhywle yn 178 00:07:42,930 --> 00:07:45,640 y canol, neu rywle y tu mewn i'r amrywiaeth. 179 00:07:45,640 --> 00:07:48,040 Ond dim ond yn ei chael yn ôl i chi rhannwch y rhestr yn ei hanner, yn 180 00:07:48,040 --> 00:07:48,940 hanner, yn ei hanner, yn ei hanner. 181 00:07:48,940 --> 00:07:50,200 Ac yna voila, ei fod yno. 182 00:07:50,200 --> 00:07:52,500 Neu eto, achos gwaethaf, nid yw hyd yn oed yno. 183 00:07:52,500 --> 00:07:56,770 Ond nid ydych yn gwybod nad ei fod yno nes i chi math o cyrraedd y diwethaf 184 00:07:56,770 --> 00:08:00,470 gwaelod-y rhan fwyaf o elfennau drwy haneru a haneru a haneru. 185 00:08:00,470 --> 00:08:01,400 >> Big O o 1. 186 00:08:01,400 --> 00:08:03,540 Felly, gallem mawr O o 2, mawr O o 3. 187 00:08:03,540 --> 00:08:06,260 Anytime ydych am dim ond rhif gyson, rydym yn unig didoli o ychydig symleiddio 188 00:08:06,260 --> 00:08:07,280 bod mor fawr O o 1. 189 00:08:07,280 --> 00:08:10,440 Hyd yn oed er os realistig, mae'n cymryd 2 neu hyd yn oed 100 o gamau, os yw'n 190 00:08:10,440 --> 00:08:13,680 nifer cyson o gamau, rydym yn unig dweud O fawr o 1. 191 00:08:13,680 --> 00:08:15,930 Beth 'an algorithm sy'n yn fawr O 1? 192 00:08:15,930 --> 00:08:18,350 >> GYNULLEIDFA: Dod o hyd i'r hyd o newidyn. 193 00:08:18,350 --> 00:08:21,090 >> DAVID Malan: Dod o hyd i'r hyd o newidyn? 194 00:08:21,090 --> 00:08:23,870 >> GYNULLEIDFA: Na, hyd os caiff ei datrys yn barod. 195 00:08:23,870 --> 00:08:24,160 >> DAVID Malan: Da. 196 00:08:24,160 --> 00:08:27,850 Iawn, felly dod o hyd i'r darn o rywbeth os yw hyd y rhywbeth, fel 197 00:08:27,850 --> 00:08:30,020 amrywiaeth, yn cael ei storio mewn rhai amrywiol. 198 00:08:30,020 --> 00:08:33,380 Oherwydd y gallwch jyst ddarllen y newidyn, neu argraffwch y newidyn, neu 199 00:08:33,380 --> 00:08:34,960 dim ond yn gyffredinol gael mynediad i'r amrywiol. 200 00:08:34,960 --> 00:08:37,299 Ac voila, sy'n cymryd amser cyson. 201 00:08:37,299 --> 00:08:38,909 >> Ar y llaw arall, yn meddwl yn ôl y safon. 202 00:08:38,909 --> 00:08:42,460 Meddyliwch yn ôl at yr wythnos gyntaf o C, galw yn unig printf ac argraffu 203 00:08:42,460 --> 00:08:46,240 rhywbeth ar y sgrîn yn dadlau cysonyn amser, gan ei fod yn cymryd dim ond 204 00:08:46,240 --> 00:08:50,880 ryw nifer o gylchoedd CPU i ddangos bod y testun ar y sgrin. 205 00:08:50,880 --> 00:08:52,720 Neu aros - a yw'n? 206 00:08:52,720 --> 00:08:56,430 Ym mha ffordd arall y gallem fodelu'r perfformiad printf? 207 00:08:56,430 --> 00:09:00,420 A fyddai rhywun yn hoffi i anghytuno, bod efallai nad yw'n amser iawn gyson? 208 00:09:00,420 --> 00:09:03,600 Ym mha ystyr y gallai printf yn rhedeg amser, mewn gwirionedd argraffu llinyn ar 209 00:09:03,600 --> 00:09:05,580 y sgrin, fod yn rhywbeth heblaw gyson. 210 00:09:05,580 --> 00:09:07,860 >> GYNULLEIDFA: [Anghlywadwy]. 211 00:09:07,860 --> 00:09:08,230 >> DAVID Malan: Yeah. 212 00:09:08,230 --> 00:09:09,300 Felly, mae'n dibynnu ar ein safbwynt. 213 00:09:09,300 --> 00:09:13,390 Os ydym mewn gwirionedd yn meddwl am y mewnbwn i printf fel y llinyn, ac 214 00:09:13,390 --> 00:09:16,380 Felly, rydym yn mesur faint y mewnbwn gan ei hyd - felly gadewch i ni alw 215 00:09:16,380 --> 00:09:17,780 y darn hwnnw n hefyd - 216 00:09:17,780 --> 00:09:21,990 gellid dadlau, printf ei hun O fawr o n oherwydd ei fod yn mynd i fynd â chi n camau 217 00:09:21,990 --> 00:09:24,750 i argraffu pob un o'r n cymeriadau, yn fwyaf tebygol. 218 00:09:24,750 --> 00:09:27,730 O leiaf i'r graddau ein bod yn cymryd yn ganiataol bod efallai ei fod yn defnyddio ar gyfer dolen 219 00:09:27,730 --> 00:09:28,560 o dan y cwfl. 220 00:09:28,560 --> 00:09:30,860 >> Ond byddai'n rhaid inni edrych ar hynny codio i ddeall yn well. 221 00:09:30,860 --> 00:09:33,650 Ac yn wir, ar ôl i chi guys yn dechrau dadansoddi eich algorithmau eich hun, byddwch yn 222 00:09:33,650 --> 00:09:34,900 llythrennol yn gwneud hynny. 223 00:09:34,900 --> 00:09:37,765 Math o belen y llygad eich cod a meddwl am - i gyd yn iawn, mae gen i ddolen hon 224 00:09:37,765 --> 00:09:41,870 yma neu gen i ddolenni nythu yma, mae hynny'n mynd i wneud pethau n n adegau, 225 00:09:41,870 --> 00:09:46,050 a allwch chi ddatrys y rheswm eich ffordd drwy'r cod, hyd yn oed os yw'n 226 00:09:46,050 --> 00:09:47,980 pseudocode ac nid cod gwirioneddol. 227 00:09:47,980 --> 00:09:49,730 >> Felly beth am omega n sgwâr? 228 00:09:49,730 --> 00:09:53,582 Beth oedd algorithm bod yn y gorau achos, yn dal i gymryd camau n sgwâr? 229 00:09:53,582 --> 00:09:54,014 Yeah? 230 00:09:54,014 --> 00:09:54,880 >> GYNULLEIDFA: [Anghlywadwy]. 231 00:09:54,880 --> 00:09:55,900 >> DAVID Malan: math dethol So. 232 00:09:55,900 --> 00:09:59,150 Oherwydd yn y broblem honno mewn gwirionedd ostwng at y ffaith hynny eto, nid wyf yn gwybod 233 00:09:59,150 --> 00:10:02,600 Rwyf wedi dod o hyd y lleiaf ar hyn o bryd hyd nes y Rwyf wedi gwirio pob un o'r elfennau darn. 234 00:10:02,600 --> 00:10:08,050 Felly omega o, dyweder, n, yr ydym yn yn unig yn dod o hyd i un. 235 00:10:08,050 --> 00:10:09,300 Mewnosod fath. 236 00:10:09,300 --> 00:10:12,370 Os yw'r rhestr yn digwydd i gael eu datrys eisoes, yn yr achos gorau rydym yn unig wedi 237 00:10:12,370 --> 00:10:15,090 i wneud un basio drwyddo, a phryd rydym yn sicr. 238 00:10:15,090 --> 00:10:17,890 Ac yna y gellid ei ddweud i fod yn llinol, yn sicr. 239 00:10:17,890 --> 00:10:20,570 >> Beth am omega o 1? 240 00:10:20,570 --> 00:10:23,790 Beth, yn yr achos gorau, efallai y bydd yn cymryd nifer cyson o gamau? 241 00:10:23,790 --> 00:10:27,220 Chwilio Felly llinol, os ydych yn unig yn cael lwcus a'r elfen rydych yn chwilio 242 00:10:27,220 --> 00:10:31,000 yn iawn ar ddechrau'r y rhestr, os dyna lle rydych yn dechrau eich 243 00:10:31,000 --> 00:10:33,070 llinol groesi o'r rhestr. 244 00:10:33,070 --> 00:10:35,180 >> Ac mae hyn yn wir am nifer o bethau. 245 00:10:35,180 --> 00:10:37,660 Er enghraifft, hyd yn oed deuaidd Chwilio yn omega o 1. 246 00:10:37,660 --> 00:10:40,310 Oherwydd yr hyn os ydych yn cael 'n sylweddol darn lwcus ac smack-lleden yng nghanol 247 00:10:40,310 --> 00:10:42,950 eich amrywiaeth yw nifer rydych yn chwilio amdano? 248 00:10:42,950 --> 00:10:45,730 Felly, gallwch gael lwcus yno, yn ogystal. 249 00:10:45,730 --> 00:10:49,190 >> Mae hyn yn un, yn olaf, omega o log n n. 250 00:10:49,190 --> 00:10:52,573 Felly n log n, ni wnaethom mewn gwirionedd siarad am hyd yn hyn, ond - 251 00:10:52,573 --> 00:10:53,300 >> GYNULLEIDFA: Cyfuno fath? 252 00:10:53,300 --> 00:10:53,960 >> DAVID Malan: Cyfuno fath. 253 00:10:53,960 --> 00:10:56,920 Dyna oedd y Cliffhanger y tro diwethaf, os yw'r cynnig byddwn ni, a dangos ein 254 00:10:56,920 --> 00:10:58,600 golwg, bod algorithmau. 255 00:10:58,600 --> 00:11:02,470 Ac uno math o dim ond un fath algorithm sydd yn y bôn yn gyflymach 256 00:11:02,470 --> 00:11:03,450 na rhai o'r rhain yn guys eraill. 257 00:11:03,450 --> 00:11:07,800 Yn wir, uno byr yn cael ei nid yn unig yn y achos gorau n n log, yn y gwaethaf 258 00:11:07,800 --> 00:11:09,460 achos n n log. 259 00:11:09,460 --> 00:11:14,540 A phan fyddwch yn cael cyd-ddigwyddiad hwn o omega ac O mawr yn yr un peth? 260 00:11:14,540 --> 00:11:17,310 Gallwn mewn gwirionedd yn disgrifio hynny fel hyn sy'n enw theta, er ei fod yn 261 00:11:17,310 --> 00:11:18,220 ychydig yn llai cyffredin. 262 00:11:18,220 --> 00:11:21,730 Ond mai dim ond yn golygu y ddwy ffiniau, yn yr achos hwn, yr un fath. 263 00:11:21,730 --> 00:11:25,770 >> Felly uno fath, beth mae hyn yn wir berwi i lawr i i ni? 264 00:11:25,770 --> 00:11:27,000 Wel, dwyn i gof y cymhelliant. 265 00:11:27,000 --> 00:11:30,340 Gadewch i mi dynnu i fyny animeiddio arall ni wnaethom edrych ar y tro diwethaf. 266 00:11:30,340 --> 00:11:33,390 Mae hyn yn un, yr un syniad, ond mae'n ychydig yn fwy. 267 00:11:33,390 --> 00:11:36,160 Ac yr wyf i'n mynd i fynd yn ei flaen ac yn tynnu sylw at cyntaf - mae gennym fath gosod ar 268 00:11:36,160 --> 00:11:39,410 y chwith uchaf, yna fath dethol, fath swigen, ychydig o mathau eraill - 269 00:11:39,410 --> 00:11:42,670 cregyn ac yn gyflym - nad ydym wedi siarad am, a tomen a chyfuno fath. 270 00:11:42,670 --> 00:11:47,090 >> Felly, o leiaf yn ceisio canolbwyntio eich llygaid ar y tri uchaf ar y chwith, ac yna 271 00:11:47,090 --> 00:11:49,120 uno fath pan fyddaf yn clicio saeth werdd yma. 272 00:11:49,120 --> 00:11:51,900 Ond byddaf yn gadael pob un ohonynt yn rhedeg, dim ond i rhoi ymdeimlad o amrywiaeth i chi 273 00:11:51,900 --> 00:11:53,980 algorithmau sy'n bodoli yn y byd. 274 00:11:53,980 --> 00:11:56,180 Rydw i'n mynd i adael i redeg hwn am ddim ond ychydig o eiliadau. 275 00:11:56,180 --> 00:11:59,640 Ac os byddwch yn canolbwyntio eich llygaid - yn ddewis algorithm, yn canolbwyntio arno am ddim ond 276 00:11:59,640 --> 00:12:02,970 eiliad - byddwch yn dechrau gweld y batrwm ei fod yn gweithredu. 277 00:12:02,970 --> 00:12:04,530 >> Cyfuno fath, hysbysiad, yn cael ei wneud. 278 00:12:04,530 --> 00:12:06,430 Fath Heap, didoli cyflym, cragen - 279 00:12:06,430 --> 00:12:09,480 felly mae'n ymddangos cyflwynwyd y tair algorithmau gwaethaf yr wythnos diwethaf. 280 00:12:09,480 --> 00:12:12,960 Ond mae hynny'n dda ein bod ni yma heddiw i edrych ar uno didoli, sy'n un o 281 00:12:12,960 --> 00:12:16,500 y rhai yn haws yw edrych ar, hyd yn oed er ei bod yn debyg y bydd yn plygu eich meddwl 282 00:12:16,500 --> 00:12:17,490 dim ond ychydig bach. 283 00:12:17,490 --> 00:12:21,130 Yma, gallwn weld yn union faint o fath dethol sucks. 284 00:12:21,130 --> 00:12:24,600 >> Ond ar y llaw arall, mae'n hawdd iawn i'w gweithredu. 285 00:12:24,600 --> 00:12:28,160 Ac efallai ar gyfer P Set 3, dyna un o'r algorithmau dewis i chi i weithredu 286 00:12:28,160 --> 00:12:28,960 ar gyfer y rhifyn safonol. 287 00:12:28,960 --> 00:12:30,970 Berffaith iawn, yn berffaith gywir. 288 00:12:30,970 --> 00:12:35,210 >> Ond unwaith eto, fel n mynd yn fawr, os ydych yn dewis i weithredu algorithm gyflymach 289 00:12:35,210 --> 00:12:39,020 hoffi uno didoli, groes yn yn fwy ac mewnbynnau mwy, eich cod yn unig 290 00:12:39,020 --> 00:12:39,800 mynd i redeg yn gyflymach. 291 00:12:39,800 --> 00:12:41,090 Eich gwefan yn mynd i weithio'n well. 292 00:12:41,090 --> 00:12:42,650 Eich defnyddwyr yn mynd i fod yn hapusach. 293 00:12:42,650 --> 00:12:45,280 Ac felly mae effeithiau hyn o roi mewn gwirionedd 294 00:12:45,280 --> 00:12:47,350 ni rai feddwl yn ddyfnach. 295 00:12:47,350 --> 00:12:49,990 >> Felly, gadewch i ni edrych ar yr hyn uno fath mewn gwirionedd yn ei olygu. 296 00:12:49,990 --> 00:12:52,992 Y peth oera yw bod uno fath yw hyn yn unig. 297 00:12:52,992 --> 00:12:56,300 Mae hyn, unwaith eto, yr hyn yr ydym wedi galw pseudocode, Bod pseudocode 298 00:12:56,300 --> 00:12:57,720 Cystrawen Saesneg-debyg. 299 00:12:57,720 --> 00:12:59,890 Ac mae'r symlrwydd yn math o ddiddorol. 300 00:12:59,890 --> 00:13:02,840 >> Felly, ar fewnbwn n elfennau - fel y yn unig yn golygu, dyma arae. 301 00:13:02,840 --> 00:13:04,000 'I' got n bethau ynddo. 302 00:13:04,000 --> 00:13:05,370 Dyna'r cyfan yr ydym yn ei ddweud yno. 303 00:13:05,370 --> 00:13:07,560 >> Os yw n yn llai na 2, yn dychwelyd. 304 00:13:07,560 --> 00:13:08,640 Felly, dyna yn union yr achos dibwys. 305 00:13:08,640 --> 00:13:12,580 Os yw n yn llai na 2, yna yn amlwg mae'n 1 neu 0, ac yn yr achos y peth 306 00:13:12,580 --> 00:13:14,780 eisoes yn didoli neu ddim yn bodoli, felly dim ond dychwelyd. 307 00:13:14,780 --> 00:13:15,900 Does dim byd i'w wneud. 308 00:13:15,900 --> 00:13:18,360 Felly, mae hynny'n achos syml i tyn i ffwrdd. 309 00:13:18,360 --> 00:13:20,110 >> Else, mae gennym tri cham. 310 00:13:20,110 --> 00:13:23,650 Ddatrys y hanner chwith y elfennau, didoli yr hanner dde o'r elfennau, 311 00:13:23,650 --> 00:13:26,650 ac yna uno haneri didoli. 312 00:13:26,650 --> 00:13:29,400 Beth sy'n ddiddorol yma yw bod Rwy'n fath o punting, dde? 313 00:13:29,400 --> 00:13:32,300 Mae fath o ddiffiniad cylchlythyr i algorithm hwn. 314 00:13:32,300 --> 00:13:35,986 Ym mha ystyr yn algorithm hwn cylchlythyr diffiniad? 315 00:13:35,986 --> 00:13:37,850 >> GYNULLEIDFA: [Anghlywadwy]. 316 00:13:37,850 --> 00:13:41,670 >> DAVID Malan: Yeah, fy algorithm didoli, dau o'i gamau yn cael eu "math 317 00:13:41,670 --> 00:13:44,640 rhywbeth. "Ac er mwyn codi'r cwestiwn, wel, beth ydw i'n mynd i ddefnyddio 318 00:13:44,640 --> 00:13:46,460 i ddatrys yr hanner chwith a'r hanner cywir? 319 00:13:46,460 --> 00:13:49,600 A harddwch yma yw bod hyd yn oed er Unwaith eto, mae hyn yn y meddwl-blygu 320 00:13:49,600 --> 00:13:54,030 rhan o bosibl, gallwch ddefnyddio un algorithm i ddatrys yr hanner chwith. 321 00:13:54,030 --> 00:13:54,700 >> Ond arhoswch funud. 322 00:13:54,700 --> 00:13:57,070 Pan fyddwch yn cael gwybod i ddatrys y chwith hanner, beth yw'r ddau 323 00:13:57,070 --> 00:13:58,240 grisiau yn mynd i fod yn nesaf? 324 00:13:58,240 --> 00:14:00,550 Byddwn yn datrys y hanner chwith y hanner chwith a'r dde 325 00:14:00,550 --> 00:14:01,420 hanner yr hanner chwith. 326 00:14:01,420 --> 00:14:04,430 Damn, sut ydw i'n trefnu dau y rhai hanner, neu chwarter, yn awr? 327 00:14:04,430 --> 00:14:05,260 >> Ond mae hynny'n iawn. 328 00:14:05,260 --> 00:14:07,830 Mae gennym algorithm didoli yma. 329 00:14:07,830 --> 00:14:10,660 A hyd yn oed er efallai y byddwch yn poeni am cyntaf yn fath o anfeidrol 330 00:14:10,660 --> 00:14:12,780 ddolen, mae'n gylch sy'n byth yn mynd i orffen - mae'n mynd i 331 00:14:12,780 --> 00:14:15,770 dod i ben ar ôl beth sy'n digwydd? 332 00:14:15,770 --> 00:14:16,970 Unwaith n yn llai na 2. 333 00:14:16,970 --> 00:14:19,180 Yn y pen draw yn mynd i ddigwydd, oherwydd os ydych yn cadw haneru a 334 00:14:19,180 --> 00:14:23,020 haneru yn haneru haneri hyn, yn sicr yn y pen draw ydych yn mynd i ben 335 00:14:23,020 --> 00:14:25,350 i fyny gyda dim ond 1 neu 0 elfen. 336 00:14:25,350 --> 00:14:28,500 Ar y pwynt, algorithm hwn dweud eich bod yn ei wneud. 337 00:14:28,500 --> 00:14:31,020 >> Felly, y hud go iawn yn y algorithm yn ymddangos i fod yn 338 00:14:31,020 --> 00:14:33,470 y cam olaf, uno. 339 00:14:33,470 --> 00:14:37,190 Mae hynny'n syniad syml dim ond uno dau bethau, dyna beth sy'n digwydd yn y pen draw 340 00:14:37,190 --> 00:14:40,920 i'n galluogi i drefnu amrywiaeth o, gadewch i ni ddweud, wyth elfen. 341 00:14:40,920 --> 00:14:44,410 Felly, yr wyf wedi wyth beli straen yn fwy i fyny yma, mae wyth darn o bapur, ac un 342 00:14:44,410 --> 00:14:45,500 Google Gwydr - 343 00:14:45,500 --> 00:14:46,140 yr wyf yn cael eu cadw. 344 00:14:46,140 --> 00:14:46,960 >> [Chwerthin] 345 00:14:46,960 --> 00:14:48,970 >> DAVID Malan: Pe gallem gymryd wyth gwirfoddolwyr, a gadewch i ni weld os gallwn 346 00:14:48,970 --> 00:14:51,430 chwarae y tu allan, felly. 347 00:14:51,430 --> 00:14:52,500 Wow, OK. 348 00:14:52,500 --> 00:14:53,565 Gwyddoniaeth gyfrifiadurol yn cael hwyl. 349 00:14:53,565 --> 00:14:54,320 Mae pob hawl. 350 00:14:54,320 --> 00:14:57,770 Felly beth am i chi dri, llaw mwyaf i fyny yno. 351 00:14:57,770 --> 00:14:58,580 Pedwar yn y cefn. 352 00:14:58,580 --> 00:15:02,220 A beth am y byddwn yn ei wneud i chi tri yn y rhes hon? 353 00:15:02,220 --> 00:15:03,390 A phedwar yn y blaen. 354 00:15:03,390 --> 00:15:04,920 Felly rydych yn wyth, yn dod ar i fyny. 355 00:15:04,920 --> 00:15:12,060 >> [Chwerthin] 356 00:15:12,060 --> 00:15:13,450 >> DAVID Malan: Rwy'n mewn gwirionedd ddim yn siŵr beth ydyw. 357 00:15:13,450 --> 00:15:14,810 A yw'n y peli straen? 358 00:15:14,810 --> 00:15:16,510 Mae'r lampau desg? 359 00:15:16,510 --> 00:15:18,650 Mae'r deunydd? 360 00:15:18,650 --> 00:15:19,680 Mae'r rhyngrwyd? 361 00:15:19,680 --> 00:15:20,160 >> OK. 362 00:15:20,160 --> 00:15:21,310 Felly dewch ar i fyny. 363 00:15:21,310 --> 00:15:22,310 Pwy fyddai'n hoffi - 364 00:15:22,310 --> 00:15:23,570 dal i ddod i fyny. 365 00:15:23,570 --> 00:15:24,240 Gadewch i ni weld. 366 00:15:24,240 --> 00:15:26,460 Ac mae hyn yn eich rhoi yn y lleoliad - 367 00:15:26,460 --> 00:15:27,940 eich bod yn y lleoliad un. 368 00:15:27,940 --> 00:15:28,670 Uh-oh, arhoswch funud. 369 00:15:28,670 --> 00:15:30,760 1, 2, 3, 4, 5, 6, 7 - oh, yn dda. 370 00:15:30,760 --> 00:15:31,310 Mae pob hawl, rydym yn dda. 371 00:15:31,310 --> 00:15:35,130 Mae pob hawl, fel bod pawb yn cael sedd, ond nid ar y Glass Google. 372 00:15:35,130 --> 00:15:36,475 Gadewch i mi i ciw hyn i fyny. 373 00:15:36,475 --> 00:15:37,115 Beth yw eich enw? 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 Mae pob hawl, byddwch yn cael i edrych fel y geek, os yw hynny'n iawn. 377 00:15:42,000 --> 00:15:44,625 Wel, yr wyf yn ei wneud hefyd, mae'n debyg, am ddim ond ennyd. 378 00:15:44,625 --> 00:15:45,875 Mae pob hawl, 'standby'. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Rydym wedi bod yn ceisio dod o hyd i achos dros ddefnyddio Google Glass, ac rydym yn 381 00:15:50,950 --> 00:15:53,750 yn meddwl y byddai'n hwyl i ychydig wneud hwn pan fydd pobl yn llwyfan. 382 00:15:53,750 --> 00:15:57,120 Byddwn yn cofnodi y byd o'u safbwynt hwy. 383 00:15:57,120 --> 00:15:58,410 Mae pob hawl. 384 00:15:58,410 --> 00:15:59,830 Nid yw yn ôl pob tebyg yr hyn Google fwriadwyd. 385 00:15:59,830 --> 00:16:02,260 Mae pob hawl, os nad oes gwahaniaeth gennych wisgo hwn am y cofnodion lletchwith nesaf, 386 00:16:02,260 --> 00:16:03,150 byddai hynny'n wych. 387 00:16:03,150 --> 00:16:08,620 >> Mae pob hawl, felly mae gennym yma amrywiaeth o elfennau, a bod amrywiaeth, yn unol â'r 388 00:16:08,620 --> 00:16:11,480 darnau o bapur yn y Folks hyn ' dwylo, yn cael ei heb eu didoli ar hyn o bryd. 389 00:16:11,480 --> 00:16:12,050 >> MICHELLE: O, mor rhyfedd. 390 00:16:12,050 --> 00:16:12,810 >> DAVID Malan: Mae 'n bert lawer ar hap. 391 00:16:12,810 --> 00:16:15,760 Ac mewn dim ond hyn o bryd, rydym yn mynd i roi cynnig i weithredu uno fath at ei gilydd 392 00:16:15,760 --> 00:16:17,950 a gweld ble y mewnwelediad allweddol yw. 393 00:16:17,950 --> 00:16:21,970 Ac mae'r tric yma gyda uno fath yn rhywbeth nad ydym wedi cymryd yn ganiataol eto. 394 00:16:21,970 --> 00:16:24,030 Rydym mewn gwirionedd angen rhywfaint o gofod ychwanegol. 395 00:16:24,030 --> 00:16:26,650 Felly beth sy'n mynd i fod yn arbennig o ddiddorol am hyn yw bod y rhain 396 00:16:26,650 --> 00:16:29,270 guys yn mynd i symud o gwmpas ychydig bit, oherwydd fy mod i'n mynd i gymryd yn ganiataol bod 397 00:16:29,270 --> 00:16:31,880 mae 'na amrywiaeth ychwanegol o le, ddweud, dde y tu ôl iddynt. 398 00:16:31,880 --> 00:16:34,570 >> Felly, os ydyn nhw y tu ôl i'w gadair, dyna yr amrywiaeth uwchradd. 399 00:16:34,570 --> 00:16:36,960 Os ydynt yn eistedd yma, dyna yr amrywiaeth cynradd. 400 00:16:36,960 --> 00:16:40,170 Ond mae hyn yn adnodd sydd gennym Nid leveraged hyd yma gyda swigen 401 00:16:40,170 --> 00:16:42,040 fath, gyda'r math dethol, gyda'r math fewnosod. 402 00:16:42,040 --> 00:16:44,600 Dwyn i gof yr wythnos diwethaf, mae pawb yn unig math o cymysgu yn eu lle. 403 00:16:44,600 --> 00:16:46,840 Doedden nhw ddim yn defnyddio unrhyw cof ychwanegol. 404 00:16:46,840 --> 00:16:49,310 Rydym yn gwneud lle i bobl drwy symud pobl o gwmpas. 405 00:16:49,310 --> 00:16:50,580 >> Felly mae hwn yn gipolwg allweddol, hefyd. 406 00:16:50,580 --> 00:16:53,410 Mae y fasnach-off, yn gyffredinol yn gwyddoniaeth gyfrifiadurol, o adnoddau. 407 00:16:53,410 --> 00:16:55,800 Os ydych am i gyflymu'r broses o rywbeth fel amser, rydych chi'n mynd i 408 00:16:55,800 --> 00:16:56,900 rhaid i chi dalu pris. 409 00:16:56,900 --> 00:17:00,750 Ac un o'r prisiau hynny yn aml iawn gofod, maint y cof neu'r caled 410 00:17:00,750 --> 00:17:01,700 lle ar y ddisg eich bod yn defnyddio. 411 00:17:01,700 --> 00:17:03,640 Neu, a dweud y gwir, y swm o amser rhaglennydd. 412 00:17:03,640 --> 00:17:06,700 Faint o amser mae'n ei gymryd i chi, y dynol, i mewn gwirionedd yn gweithredu rhai mwy 413 00:17:06,700 --> 00:17:07,829 algorithm cymhleth. 414 00:17:07,829 --> 00:17:09,760 Ond ar gyfer heddiw, y fasnach-off yn amser a gofod. 415 00:17:09,760 --> 00:17:11,930 >> Felly, pe gallech guys dim ond yn dal i fyny eich niferoedd er mwyn i ni weld eich bod chi'n 416 00:17:11,930 --> 00:17:15,839 yn wir cyfateb 4, 2, 6, 1, 3, 7, 8. 417 00:17:15,839 --> 00:17:16,599 Ardderchog. 418 00:17:16,599 --> 00:17:19,520 Felly, yr wyf i'n mynd i geisio drefnu'r pethau, gall os ydych yn guys yn unig 419 00:17:19,520 --> 00:17:21,800 ddilyn fy arweiniad yma. 420 00:17:21,800 --> 00:17:26,650 >> Felly, yr wyf yn mynd i weithredu, yn gyntaf, y Cam cyntaf y pseudocode, sydd yn 421 00:17:26,650 --> 00:17:29,440 ar fewnbwn n elfennau, os yw n yn llai na 2, ac yna dychwelyd. 422 00:17:29,440 --> 00:17:31,370 Yn amlwg, nid yw hynny'n yn gymwys, felly rydym yn symud ymlaen. 423 00:17:31,370 --> 00:17:33,340 Felly ddatrys y hanner chwith y elfennau. 424 00:17:33,340 --> 00:17:36,220 Felly mae hynny'n golygu fy mod i'n mynd i ganolbwyntio fy sylw am ychydig funudau'n ar y rhain 425 00:17:36,220 --> 00:17:37,310 pedwar guys yma. 426 00:17:37,310 --> 00:17:39,774 Mae pob hawl, beth ddylwn i ei wneud nesaf? 427 00:17:39,774 --> 00:17:40,570 >> GYNULLEIDFA: Trefnwch y hanner chwith. 428 00:17:40,570 --> 00:17:42,780 >> DAVID Malan: Felly, yn awr yn rhaid i mi ddatrys hanner chwith y guys hyn. 429 00:17:42,780 --> 00:17:45,580 Oherwydd unwaith eto, cymryd yn ganiataol i chi eich hun y nod yw i ddatrys yr hanner chwith. 430 00:17:45,580 --> 00:17:46,440 Sut ydych chi'n ei wneud hynny? 431 00:17:46,440 --> 00:17:49,140 Dilynwch y cyfarwyddiadau, hyd yn oed er ein bod yn ei wneud eto. 432 00:17:49,140 --> 00:17:50,160 Felly ddatrys yr hanner chwith. 433 00:17:50,160 --> 00:17:52,030 Nawr rwy'n trefnu y ddau guys. 434 00:17:52,030 --> 00:17:53,563 Beth sy'n dod nesaf? 435 00:17:53,563 --> 00:17:54,510 >> GYNULLEIDFA: Trefnwch y hanner chwith. 436 00:17:54,510 --> 00:17:55,460 >> DAVID Malan: Trefnwch y hanner chwith. 437 00:17:55,460 --> 00:18:00,680 Felly, yn awr y rhain, y sedd yma, mae rhestr o faint 1. 438 00:18:00,680 --> 00:18:01,365 A beth yw eich enw eto? 439 00:18:01,365 --> 00:18:02,390 >> PRINCESS DAISY: Princess Daisy. 440 00:18:02,390 --> 00:18:03,690 >> DAVID Malan: Princess Daisy yma. 441 00:18:03,690 --> 00:18:07,470 Ac felly mae hi'n ei ddidoli yn barod, oherwydd y rhestr o faint 1. 442 00:18:07,470 --> 00:18:09,490 Beth ddylwn i ei wneud nesaf? 443 00:18:09,490 --> 00:18:13,680 OK, yn dychwelyd, gan fod y rhestr honno o maint 1, sy'n llai na 2. 444 00:18:13,680 --> 00:18:14,320 Yna, beth yw'r cam nesaf? 445 00:18:14,320 --> 00:18:17,490 Ac yn awr mae'n rhaid i chi fath o mynd yn ôl yn eich meddwl. 446 00:18:17,490 --> 00:18:19,340 >> Trefnwch yr hanner cywir, sef - 447 00:18:19,340 --> 00:18:19,570 beth yw eich enw? 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 Ac felly beth ydym yn ei wneud yn awr bod mae gennym restr o faint 1? 451 00:18:23,210 --> 00:18:24,440 >> GYNULLEIDFA: Ffurflen Dreth. 452 00:18:24,440 --> 00:18:24,760 >> DAVID Malan: ofalus. 453 00:18:24,760 --> 00:18:29,540 Byddwn yn dychwelyd yn gyntaf, ac yn awr y trydydd cam - ac os wyf yn fath o ddarlunio iddo gan 454 00:18:29,540 --> 00:18:33,490 cofleidio'r ddwy sedd nawr, yn awr yr wyf rhaid iddynt gyfuno y ddwy elfen. 455 00:18:33,490 --> 00:18:35,530 Felly, erbyn hyn yn anffodus, mae'r elfennau allan o drefn. 456 00:18:35,530 --> 00:18:39,920 Ond dyna lle y broses uno yn dechrau cael anorchfygol. 457 00:18:39,920 --> 00:18:42,410 >> Felly, pe gallech guys sefyll i fyny am ddim ond hyn o bryd, dw i'n mynd i angen i chi, mewn 458 00:18:42,410 --> 00:18:44,170 hyn o bryd, i gamu y tu ôl i'ch cadair. 459 00:18:44,170 --> 00:18:46,480 Ac os Linda, gan fod 2 llai na 4, pam na wnewch 460 00:18:46,480 --> 00:18:48,130 byddwch yn dod o gwmpas yn gyntaf? 461 00:18:48,130 --> 00:18:48,690 Aros yno. 462 00:18:48,690 --> 00:18:50,520 Felly, Linda, byddwch yn dod o gwmpas yn gyntaf. 463 00:18:50,520 --> 00:18:53,820 >> Nawr, mewn gwirionedd os mai dim ond arae gallem dim ond symud ei mewn amser real 464 00:18:53,820 --> 00:18:55,360 o gadair hon i adnabod hwn. 465 00:18:55,360 --> 00:18:57,770 Felly dychmygwch a gymerodd rhai cyson nifer o gamau 1. 466 00:18:57,770 --> 00:18:58,480 Ac yn awr - 467 00:18:58,480 --> 00:19:01,490 ond mae angen eich rhoi mewn y lleoliad cyntaf yma. 468 00:19:01,490 --> 00:19:03,930 >> Ac yn awr pe baech yn dod o gwmpas, yn ogystal, rydym yn mynd i 469 00:19:03,930 --> 00:19:06,300 fod yn y lleoliad dau. 470 00:19:06,300 --> 00:19:09,120 A hyd yn oed er bod hyn yn teimlo fel ei fod yn cymryd ychydig o amser, beth braf yn awr yw 471 00:19:09,120 --> 00:19:14,710 bod hanner chwith y chwith hanner yn cael ei ddatrys yn awr. 472 00:19:14,710 --> 00:19:18,010 Felly beth oedd y cam nesaf, os ydym yn awr ailddirwyn ymhellach yn y stori? 473 00:19:18,010 --> 00:19:18,980 >> GYNULLEIDFA: hanner Iawn. 474 00:19:18,980 --> 00:19:19,900 >> DAVID Malan: Trefnwch y hanner cywir. 475 00:19:19,900 --> 00:19:21,320 Felly, mae'n rhaid i chi guys i wneud hyn, yn ogystal. 476 00:19:21,320 --> 00:19:23,510 Felly, pe baech yn sefyll i fyny am ddim ond hyn o bryd? 477 00:19:23,510 --> 00:19:25,192 A beth yw eich enw? 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 Iawn, felly Jess yn awr y chwith hanner yr hanner cywir. 481 00:19:29,720 --> 00:19:31,400 Ac felly mae hi'n rhestr o faint 1. 482 00:19:31,400 --> 00:19:32,380 Amlwg hi didoli. 483 00:19:32,380 --> 00:19:33,070 A'ch enw eto? 484 00:19:33,070 --> 00:19:33,630 >> MICHELLE: Michelle. 485 00:19:33,630 --> 00:19:35,340 >> DAVID Malan: Michelle yn amlwg restr o faint 1. 486 00:19:35,340 --> 00:19:36,050 Mae hi wedi datrys eisoes. 487 00:19:36,050 --> 00:19:38,690 Felly, yn awr y hud yn digwydd, y broses uno. 488 00:19:38,690 --> 00:19:39,790 Felly, pwy sy'n mynd i ddod yn gyntaf? 489 00:19:39,790 --> 00:19:41,560 Michelle yn amlwg. 490 00:19:41,560 --> 00:19:43,280 Felly, pe gallech ddod o gwmpas yn ôl. 491 00:19:43,280 --> 00:19:47,090 Mae'r gofod sydd gennym ar gael iddi nawr yn iawn y tu ôl i gadair hon yma. 492 00:19:47,090 --> 00:19:51,580 Ac yn awr pe gallech ddod yn ôl hefyd, gennym yn awr, i fod yn glir, dau 493 00:19:51,580 --> 00:19:53,810 haneri, pob un maint 2 - 494 00:19:53,810 --> 00:19:57,090 a dim ond er mwyn darlun yn, os ydych yn allai wneud ychydig o le - 495 00:19:57,090 --> 00:19:59,780 neb ar ôl hanner yma, un hanner i'r dde yma. 496 00:19:59,780 --> 00:20:01,160 >> Ailddirwyn ymhellach yn y stori. 497 00:20:01,160 --> 00:20:02,270 Beth yw cam nesaf? 498 00:20:02,270 --> 00:20:03,030 >> GYNULLEIDFA: Cyfuno. 499 00:20:03,030 --> 00:20:04,160 >> DAVID Malan: Felly, yn awr mae'n rhaid i ni uno. 500 00:20:04,160 --> 00:20:07,490 Felly Iawn, felly nawr, diolch byth, rydym yn dim ond rhyddhau pedair cadair. 501 00:20:07,490 --> 00:20:11,480 Felly, rydym wedi defnyddio ddwywaith cymaint o cof, ond gallwn roi fflip-flopping rhwng 502 00:20:11,480 --> 00:20:12,330 y ddau arae. 503 00:20:12,330 --> 00:20:14,190 Felly, pa rif yw i ddod yn gyntaf? 504 00:20:14,190 --> 00:20:14,850 Felly, Michelle, yn amlwg. 505 00:20:14,850 --> 00:20:16,680 Felly dod o gwmpas ac yn cymryd eich sedd yma. 506 00:20:16,680 --> 00:20:19,120 Ac yna rhif 2 yn amlwg nesaf, felly yr ydych yn dod yma. 507 00:20:19,120 --> 00:20:21,520 Rhif 4, rhif 6. 508 00:20:21,520 --> 00:20:23,390 Ac eto, er bod yna ychydig bach o gerdded dan sylw, 509 00:20:23,390 --> 00:20:26,010 mewn gwirionedd, gallai'r rhain ddigwydd yn syth, drwy symud un - 510 00:20:26,010 --> 00:20:26,880 OK, chwarae yn dda. 511 00:20:26,880 --> 00:20:28,350 >> [Chwerthin] 512 00:20:28,350 --> 00:20:29,680 >> DAVID Malan: Ac yn awr rydym yn mewn cyflwr eithaf da. 513 00:20:29,680 --> 00:20:34,910 Mae hanner chwith y cyfan mewnbwn bellach wedi ei ddatrys. 514 00:20:34,910 --> 00:20:37,370 Mae pob hawl, felly guys hyn wedi y fantais o fy - 515 00:20:37,370 --> 00:20:40,340 sut oedd yn y pen draw yr holl ferched ar y chwith a'r holl fechgyn ar y dde? 516 00:20:40,340 --> 00:20:42,450 >> Iawn, felly 'guys droi yn awr. 517 00:20:42,450 --> 00:20:44,680 Felly, ni fyddaf byddwch yn cerdded trwy camau hyn. 518 00:20:44,680 --> 00:20:46,550 Byddwn yn gweld a allwn ailymgeisio yr un pseudocode. 519 00:20:46,550 --> 00:20:50,050 Os ydych am fynd ymlaen a sefyll i fyny, ac rydych guys, gadewch i mi roi'r meic i chi. 520 00:20:50,050 --> 00:20:52,990 Gwelwch os nad ydych yn gallu ailadrodd yr hyn rydym yn unig oedd yma ar y 521 00:20:52,990 --> 00:20:53,880 ben arall y rhestr. 522 00:20:53,880 --> 00:20:59,530 Pwy sydd angen i siarad yn gyntaf, yn seiliedig ar y algorithm? 523 00:20:59,530 --> 00:21:03,210 Felly esbonio beth rydych chi'n ei wneud cyn byddwch yn gwneud unrhyw symudiadau droed. 524 00:21:03,210 --> 00:21:05,930 >> SIARADWR 1: pob hawl, felly ers Fi yw hanner chwith y 525 00:21:05,930 --> 00:21:07,790 chwith hanner, yn ol. 526 00:21:07,790 --> 00:21:08,730 Iawn? 527 00:21:08,730 --> 00:21:09,250 >> DAVID Malan: Da. 528 00:21:09,250 --> 00:21:10,350 >> SIARADWR 1: Ac yna - 529 00:21:10,350 --> 00:21:11,800 >> DAVID Malan: Pwy sy'n gwneud y meic yn mynd i'r nesaf? 530 00:21:11,800 --> 00:21:12,920 >> SIARADWR 1: Nifer Nesaf. 531 00:21:12,920 --> 00:21:14,720 >> SIARADWR 2: Felly, yr wyf fi yw'r hanner cywir yr hanner chwith y 532 00:21:14,720 --> 00:21:17,830 chwith hanner, ac yn ol. 533 00:21:17,830 --> 00:21:18,050 >> DAVID Malan: Da. 534 00:21:18,050 --> 00:21:18,550 Byddwch yn dychwelyd. 535 00:21:18,550 --> 00:21:21,855 Felly, yn awr beth sydd i fyny nesaf i chi ddau? 536 00:21:21,855 --> 00:21:23,740 >> SIARADWR 2: Yr ydym am weld pwy yn llai. 537 00:21:23,740 --> 00:21:24,200 >> DAVID Malan: Yn union. 538 00:21:24,200 --> 00:21:24,940 Rydym yn awyddus i uno. 539 00:21:24,940 --> 00:21:27,590 Mae'r gofod rydym yn mynd i ddefnyddio i uno chi i mewn, er eu bod yn 540 00:21:27,590 --> 00:21:30,250 amlwg yn datrys eisoes, rydym yn mynd i ddilyn yr un algorithm. 541 00:21:30,250 --> 00:21:31,560 Felly, sy'n mynd yn ôl yn gyntaf? 542 00:21:31,560 --> 00:21:35,720 Felly 3, ac yna 7. 543 00:21:35,720 --> 00:21:38,570 Ac yn awr y meic yn mynd i guys hyn, OK? 544 00:21:38,570 --> 00:21:43,590 >> SIARADWR 3: Felly, yr wyf i'n hanner hawl y chwith hanner, ac mae fy n yn llai na 545 00:21:43,590 --> 00:21:45,048 1, fel Im 'jyst yn mynd i basio - 546 00:21:45,048 --> 00:21:46,380 >> DAVID Malan: Da. 547 00:21:46,380 --> 00:21:49,450 >> SIARADWR 4: Rwy'n hanner hawl y hanner dde o'r hanner iawn, ac rwy'n 548 00:21:49,450 --> 00:21:51,740 hefyd yn un person, felly rwy'n mynd i ddychwelyd. 549 00:21:51,740 --> 00:21:52,990 Felly, yn awr rydym yn uno. 550 00:21:52,990 --> 00:21:55,140 551 00:21:55,140 --> 00:21:56,150 >> SIARADWR 3: Felly, rydym yn mynd yn ôl. 552 00:21:56,150 --> 00:21:57,160 >> DAVID Malan: Felly, byddwch yn mynd i mewn i'r cefn. 553 00:21:57,160 --> 00:21:59,200 Felly, 5 yn mynd yn gyntaf, ac yna 8. 554 00:21:59,200 --> 00:22:01,240 Ac yn awr gynulleidfa, sef y gam yn rhaid i ailddirwyn nawr 555 00:22:01,240 --> 00:22:02,200 yn ôl yn ein meddyliau? 556 00:22:02,200 --> 00:22:02,940 >> GYNULLEIDFA: Cyfuno. 557 00:22:02,940 --> 00:22:07,270 >> DAVID Malan: Cyfuno hanner ac i'r dde i'r chwith hanner yr hanner chwith gwreiddiol. 558 00:22:07,270 --> 00:22:08,840 Felly, yn awr - 559 00:22:08,840 --> 00:22:10,520 a dim ond er mwyn gwneud hyn yn glir, gwneud ychydig o ofod 560 00:22:10,520 --> 00:22:11,690 rhyngoch chi ddau guys. 561 00:22:11,690 --> 00:22:13,800 Felly nawr dyna'r ddwy restr, chwith ac i'r dde. 562 00:22:13,800 --> 00:22:18,320 Felly, sut yr ydym yn awr yn cyfuno i chi guys i mewn i y rhes flaen y seddi eto? 563 00:22:18,320 --> 00:22:19,600 >> 3 yn mynd yn gyntaf. 564 00:22:19,600 --> 00:22:20,850 Yna, 5, yn amlwg. 565 00:22:20,850 --> 00:22:23,110 566 00:22:23,110 --> 00:22:27,330 Yna, 7, ac yn awr 8. 567 00:22:27,330 --> 00:22:28,710 OK, ac yn awr rydym ni? 568 00:22:28,710 --> 00:22:29,650 >> GYNULLEIDFA: Heb ei wneud. 569 00:22:29,650 --> 00:22:32,440 >> DAVID Malan: Heb ei wneud, oherwydd yn amlwg, mae un cam ar ôl. 570 00:22:32,440 --> 00:22:35,720 Ond unwaith eto, y rheswm rwy'n ei ddefnyddio hwn jargon fel "ailddirwyn yn eich meddwl," 571 00:22:35,720 --> 00:22:37,160 mae'n oherwydd dyna wir beth sy'n digwydd. 572 00:22:37,160 --> 00:22:39,610 Rydym yn mynd drwy bob un o'r camau hyn, ond rydym yn fath o oedi ar gyfer 573 00:22:39,610 --> 00:22:42,480 hyn o bryd, plymio ddyfnach i mewn i'r algorithm, gan oedi am eiliad, 574 00:22:42,480 --> 00:22:45,840 plymio ddyfnach i mewn i'r algorithm, a erbyn hyn mae'n rhaid i ni drefnu o ailddirwyn yn ein 575 00:22:45,840 --> 00:22:49,430 meddyliau a dadwneud pob un o'r haenau hyn ein bod wedi fath o gohirio. 576 00:22:49,430 --> 00:22:51,790 >> Felly, erbyn hyn mae gennym dwy restr o faint 4. 577 00:22:51,790 --> 00:22:54,790 Pe gallech guys sefyll i fyny am y tro olaf ac yn gwneud ychydig o le yma i 578 00:22:54,790 --> 00:22:57,230 gwneud yn glir bod hyn yn y chwith hanner y gwreiddiol, y 579 00:22:57,230 --> 00:22:58,620 hanner cywir o'r gwreiddiol. 580 00:22:58,620 --> 00:23:01,060 Pwy yw'r rhif cyntaf ein bod yn angen i dynnu i mewn i gefn? 581 00:23:01,060 --> 00:23:01,870 Michelle, wrth gwrs. 582 00:23:01,870 --> 00:23:03,230 >> Felly, rydym yn rhoi Michelle yma. 583 00:23:03,230 --> 00:23:05,080 Ac sydd â rhif 2? 584 00:23:05,080 --> 00:23:06,440 Rhif 2 yn dod ar gefn hefyd. 585 00:23:06,440 --> 00:23:07,800 Rhif 3? 586 00:23:07,800 --> 00:23:08,510 Ardderchog. 587 00:23:08,510 --> 00:23:16,570 Rhif 4, rhif 5, rhif 6, rhif 7, a rhif 8. 588 00:23:16,570 --> 00:23:18,850 >> Iawn, felly roedd yn teimlo fel llawer o gamau, yn sicr. 589 00:23:18,850 --> 00:23:22,390 Ond yn awr gadewch i ni weld os na allwn gadarnhau math o reddfol bod hyn yn 590 00:23:22,390 --> 00:23:26,190 algorithm sylfaenol, yn enwedig gan n mynd yn wirioneddol fawr, fel yr ydym wedi gweld 591 00:23:26,190 --> 00:23:29,170 gyda'r animeiddiadau, yn sylfaenol yn gyflymach. 592 00:23:29,170 --> 00:23:33,400 Felly gallaf hawlio algorithm hwn, yn y gwaethaf achos a hyd yn oed yn yr achos gorau, 593 00:23:33,400 --> 00:23:36,160 yn fawr O n amseroedd log n. 594 00:23:36,160 --> 00:23:39,160 Hynny yw, mae rhywfaint o agwedd ar hyn algorithm sy'n cymryd camau n, ond 595 00:23:39,160 --> 00:23:43,110 mae agwedd arall rhywle yn y iteriad, hynny dolennu, hynny 596 00:23:43,110 --> 00:23:44,410 yn cymryd camau n log. 597 00:23:44,410 --> 00:23:49,154 A allwn ni roi ein bys ar yr hyn y rhai ddau rif yn cyfeirio ato? 598 00:23:49,154 --> 00:23:51,320 Wel, ble - 599 00:23:51,320 --> 00:23:54,160 where'd y meic yn mynd? 600 00:23:54,160 --> 00:23:58,660 >> SIARADWR 1: A fyddai'r log n yn torri ni i fyny yn ddau - 601 00:23:58,660 --> 00:23:59,630 rhannu â dau, yn y bôn. 602 00:23:59,630 --> 00:24:00,120 >> DAVID Malan: Yn union. 603 00:24:00,120 --> 00:24:03,000 Unrhyw tro y byddwn yn gweld mewn unrhyw algorithm felly yn hyn, mae wedi bod yn y patrwm hwn o 604 00:24:03,000 --> 00:24:04,200 rhannu, rhannu, rhannu. 605 00:24:04,200 --> 00:24:05,700 Ac mae'n nodweddiadol ostwng i rywbeth sy'n 606 00:24:05,700 --> 00:24:07,100 logarithmig, log sylfaen 2. 607 00:24:07,100 --> 00:24:10,180 Ond gallai fod mewn gwirionedd fod yn unrhyw beth, ond logio sylfaen 2. 608 00:24:10,180 --> 00:24:11,330 >> Nawr, beth am y n? 609 00:24:11,330 --> 00:24:14,550 Gallaf weld ein bod yn fath o rannu eich guys - rhannu i chi, wedi ei rannu i chi, 610 00:24:14,550 --> 00:24:15,910 rhannu i chi, wedi ei rannu i chi. 611 00:24:15,910 --> 00:24:18,760 Lle mae'r diwedd yn dod o? 612 00:24:18,760 --> 00:24:19,810 >> Felly mae'n cyfuno. 613 00:24:19,810 --> 00:24:20,610 Oherwydd meddwl am y peth. 614 00:24:20,610 --> 00:24:25,420 Pan fyddwch yn uno wyth o bobl at ei gilydd, lle mae hanner ohonynt yn set o bedwar 615 00:24:25,420 --> 00:24:27,770 a'r hanner arall yn un arall set o bedwar, sut ydych chi'n mynd 616 00:24:27,770 --> 00:24:28,820 ymwneud â gwneud y uno? 617 00:24:28,820 --> 00:24:30,830 Wel, yr ydych yn guys yn gwneud hynny weddol reddfol. 618 00:24:30,830 --> 00:24:34,140 >> Ond ychydig, os wyf yn hytrach yn gwneud yn fwy drefnus, efallai y byddwn wedi tynnu sylw at 619 00:24:34,140 --> 00:24:38,090 y person leftmost cyntaf gyda fy chwith llaw, sylw at y ffaith ar y person leftmost 620 00:24:38,090 --> 00:24:42,080 o bod hanner gyda fy llaw dde, a dim ond wedyn cerdded drwy'r 621 00:24:42,080 --> 00:24:46,990 rhestr, gan dynnu sylw at yr elfen lleiaf bob tro, gan symud fy mys drosodd a 622 00:24:46,990 --> 00:24:48,970 drosodd fel sydd ei angen drwy gydol y rhestr. 623 00:24:48,970 --> 00:24:51,890 Ond yr hyn sy'n allweddol am y cyfuno broses yn Rwy'n cymharu parau hyn 624 00:24:51,890 --> 00:24:53,460 o elfennau. 625 00:24:53,460 --> 00:24:57,270 O hanner dde ac o'r chwith hanner, rwy'n byth yn gwrthgilio oddi unwaith. 626 00:24:57,270 --> 00:25:00,570 >> Felly, mae'r uno ei hun yn cymryd dim mwy na n risiau. 627 00:25:00,570 --> 00:25:03,250 A sawl gwaith oedd gen i i wneud hynny uno? 628 00:25:03,250 --> 00:25:07,150 Wel, dim mwy na n, ac rydym yn unig yn gweld bod â'r uno terfynol. 629 00:25:07,150 --> 00:25:13,120 Ac felly os ydych yn gwneud rhywbeth sy'n cymryd log n grisiau n amser, neu i'r gwrthwyneb, 630 00:25:13,120 --> 00:25:15,210 mae'n mynd i roi i ni n amseroedd log n. 631 00:25:15,210 --> 00:25:16,310 >> A pham mae hyn yn well? 632 00:25:16,310 --> 00:25:19,600 Wel, os ydym eisoes yn gwybod bod log n yn well na n - iawn? 633 00:25:19,600 --> 00:25:22,590 Gwelsom mewn chwiliad deuaidd, y llyfr ffôn enghraifft, roedd log n bendant 634 00:25:22,590 --> 00:25:23,760 well na llinol. 635 00:25:23,760 --> 00:25:28,420 Felly, mae hynny'n golygu n amseroedd log n yn bendant yn well na n gwaith arall 636 00:25:28,420 --> 00:25:30,390 n, AKA n sgwâr. 637 00:25:30,390 --> 00:25:32,400 A dyna beth rydym yn y pen draw yn teimlo. 638 00:25:32,400 --> 00:25:34,928 >> Rownd mor fawr o gymeradwyaeth, os gallem, ar gyfer guys hyn. 639 00:25:34,928 --> 00:25:38,920 >> [Cymeradwyaeth] 640 00:25:38,920 --> 00:25:41,550 >> DAVID Malan: A'ch rhoddion rhaniad - efallai y byddwch yn cadw'r rhifau, 641 00:25:41,550 --> 00:25:44,010 os hoffech. 642 00:25:44,010 --> 00:25:45,620 Ac mae eich rhodd rhaniad, fel arfer. 643 00:25:45,620 --> 00:25:47,290 O, a byddwn yn anfon y ffilm, Michelle. 644 00:25:47,290 --> 00:25:48,343 Diolch yn fawr. 645 00:25:48,343 --> 00:25:49,250 Mae pob hawl. 646 00:25:49,250 --> 00:25:50,400 Helpu eich hun i bêl straen. 647 00:25:50,400 --> 00:25:54,110 >> A gadewch i mi dynnu i fyny, yn y cyfamser, ein ffrind Rob Bowden i gynnig 648 00:25:54,110 --> 00:25:59,520 bersbectif ychydig yn wahanol ar hyn, gan y gall eich barn chi am y rhain 649 00:25:59,520 --> 00:26:01,280 camau yn digwydd mewn braidd gwahanol ffordd. 650 00:26:01,280 --> 00:26:04,750 Mewn gwirionedd, mae'r set-up ar gyfer yr hyn Rob ymwneud â i ddangos i ni yn cymryd yn ganiataol bod rydym wedi 651 00:26:04,750 --> 00:26:09,030 gwneud i fyny rannu y eisoes rhestr mawr yn wyth rhestrau bach, 652 00:26:09,030 --> 00:26:10,570 pob un o faint 1. 653 00:26:10,570 --> 00:26:13,350 >> Felly, rydym yn newid y pseudocode a ychydig bach yn unig i ddatrys o gyrraedd y 654 00:26:13,350 --> 00:26:15,320 syniad craidd o sut y mae'r uno yn gweithio. 655 00:26:15,320 --> 00:26:17,600 Ond mae'r amser yn rhedeg o'r hyn ei fod ar fin ei wneud yn dal i fod 656 00:26:17,600 --> 00:26:19,110 mynd i fod yr un fath. 657 00:26:19,110 --> 00:26:23,540 Ac eto, y set-up yma yw ei fod yn dechrau gydag wyth rhestrau o faint 1. 658 00:26:23,540 --> 00:26:27,730 Felly, rydych wedi colli y rhan lle mae'n wneud mewn gwirionedd y log n, n log, log n 659 00:26:27,730 --> 00:26:31,205 rannu y mewnbwn. 660 00:26:31,205 --> 00:26:32,120 >> [VIDEO Playback] 661 00:26:32,120 --> 00:26:33,615 >> -Dyna ni am gam un. 662 00:26:33,615 --> 00:26:38,270 Ar gyfer cam dau, dro ar ôl tro uno parau o restrau. 663 00:26:38,270 --> 00:26:39,210 >> DAVID Malan: EM. 664 00:26:39,210 --> 00:26:41,270 Dim ond sain yn dod allan o fy nghyfrifiadur. 665 00:26:41,270 --> 00:26:42,520 Gadewch i ni geisio eto. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Dim ond fympwyol ddewis sydd - erbyn hyn mae gennym bedwar rhestrau. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 Dysgu o'r blaen. 670 00:26:52,120 --> 00:26:53,040 >> DAVID Malan: Dyna ni. 671 00:26:53,040 --> 00:27:00,510 >> Cyfuno-108 a 15, rydym yn y pen i fyny â'r rhestr 15, 108. 672 00:27:00,510 --> 00:27:07,170 Cyfuno 50 a 4, rydym yn y pen draw gyda 4, 50. 673 00:27:07,170 --> 00:27:12,990 Cyfuno 8 a 42, rydym yn darfod i fyny ag 8, 42. 674 00:27:12,990 --> 00:27:19,970 Ac uno 23 a 16 oed, rydym yn darfod i fyny ag 16, 23. 675 00:27:19,970 --> 00:27:23,270 >> Nawr ein holl restrau o faint 2. 676 00:27:23,270 --> 00:27:26,690 Sylwch fod pob un o'r pedair rhestr yn cael ei datrys. 677 00:27:26,690 --> 00:27:29,450 Felly, gallwn ddechrau cyfuno parau o restrau eto. 678 00:27:29,450 --> 00:27:38,420 Cyfuno 15 a 108 a 4 a 50, rydym yn gyntaf yn y 4, yna bydd y 15, yna 679 00:27:38,420 --> 00:27:41,500 y 50, yna bydd y 108. 680 00:27:41,500 --> 00:27:50,610 Cyfuno 8, 42 ac 16, 23, rydym yn cymryd yn gyntaf 8, yna bydd y 16, yna 23, 681 00:27:50,610 --> 00:27:52,700 yna bydd y 42. 682 00:27:52,700 --> 00:27:57,600 >> Felly, erbyn hyn rydym wedi dim ond dwy restr o faint 4, pob un ohonynt yn cael ei drefnu. 683 00:27:57,600 --> 00:28:01,170 Felly nawr rydym yn cyfuno'r ddwy restr. 684 00:28:01,170 --> 00:28:11,835 Yn gyntaf, rydym yn cymryd y 4, yna rydym yn cymryd y 8, yna rydym yn cymryd y 15, yna 16, yna 685 00:28:11,835 --> 00:28:19,456 23, yna 42, yna 50, yna 108. 686 00:28:19,456 --> 00:28:19,872 >> [VIDEO END Playback] 687 00:28:19,872 --> 00:28:23,430 >> DAVID Malan: Unwaith eto, rhybudd, ef byth yn cyffwrdd gwpan cael mwy nag un amser 688 00:28:23,430 --> 00:28:24,860 ar ôl symud ymlaen y tu hwnt iddo. 689 00:28:24,860 --> 00:28:26,200 Felly, nad oedd erioed wedi ailadrodd. 690 00:28:26,200 --> 00:28:29,850 Felly, mae'n bob amser yn symud i'r ochr, a dyna lle rydym yn cael ein n. 691 00:28:29,850 --> 00:28:33,290 >> Beth am adael i mi dynnu i fyny un animeiddio a welsom yn gynharach, ond y tro hwn 692 00:28:33,290 --> 00:28:35,110 canolbwyntio ar uno fath. 693 00:28:35,110 --> 00:28:38,030 Gadewch i mi fynd yn ei flaen a chwyddo i mewn ar hyn yma. 694 00:28:38,030 --> 00:28:42,530 Yn gyntaf gadewch i mi ddewis mewnbwn ar hap, chwyddo hyn, a gallwch ddatrys o weld 695 00:28:42,530 --> 00:28:46,600 yr hyn a wnaethom yn ganiataol, yn gynharach, uno fath yn ei wneud mewn gwirionedd. 696 00:28:46,600 --> 00:28:50,330 >> Felly, yn sylwi eich bod yn cael haneri hyn neu y chwarter neu wyth o'r rhain yn y 697 00:28:50,330 --> 00:28:53,140 broblem yn sydyn dechrau cymryd siâp da. 698 00:28:53,140 --> 00:28:57,070 Ac yna yn olaf, byddwch yn gweld yn y diwedd y bam, 699 00:28:57,070 --> 00:28:58,860 popeth yn cael ei gyfuno gyda'i gilydd. 700 00:28:58,860 --> 00:29:01,690 >> Felly mae'r rhain yn dim ond tri wahanol yn cymryd ar yr un syniad. 701 00:29:01,690 --> 00:29:05,980 Ond mae'r mewnwelediad allweddol, yn union fel rhaniad a gorchfygu yn y dosbarth cyntaf, 702 00:29:05,980 --> 00:29:10,640 oedd ein bod yn penderfynu i rhywsut rhannu y broblem yn rhywbeth mawr, i mewn 703 00:29:10,640 --> 00:29:14,760 rhywbeth math o union yr un fath yn yr ysbryd, ond yn llai ac yn llai ac yn llai 704 00:29:14,760 --> 00:29:15,660 ac yn llai. 705 00:29:15,660 --> 00:29:18,420 >> Nawr ffordd hwyliog arall i ddatrys o feddwl am y rhain, er nad yw'n 706 00:29:18,420 --> 00:29:20,520 mynd i roi yr un 'n athrylithgar i chi dealltwriaeth, yn 707 00:29:20,520 --> 00:29:21,640 yr animeiddiad canlynol. 708 00:29:21,640 --> 00:29:25,400 Felly, mae hwn yn rhywun fideo rhoi at ei gilydd a gysylltir gwahanol 709 00:29:25,400 --> 00:29:29,970 synau gyda'r gwahanol gweithrediadau ar gyfer fath mewnosod, ar gyfer uno didoli, a 710 00:29:29,970 --> 00:29:31,150 am ychydig o rai eraill. 711 00:29:31,150 --> 00:29:32,330 Felly, mewn munud, dw i'n mynd i daro Chwarae. 712 00:29:32,330 --> 00:29:33,600 Mae'n ymwneud munud o hyd. 713 00:29:33,600 --> 00:29:37,410 A hyd yn oed er y gallwch ddal i weld y batrymau digwydd, y tro hwn gallwch 714 00:29:37,410 --> 00:29:41,420 hefyd yn clywed sut y algorithmau hyn yn perfformio'n wahanol a chyda 715 00:29:41,420 --> 00:29:43,950 batrymau ychydig yn wahanol. 716 00:29:43,950 --> 00:29:45,830 >> Mae hyn yn fath gosod. 717 00:29:45,830 --> 00:29:50,400 >> [Tones CHWARAE] 718 00:29:50,400 --> 00:29:52,400 >> DAVID Malan: Mae'n eto yn ceisio i fewnosod pob elfen 719 00:29:52,400 --> 00:29:52,900 i ble mae'n perthyn. 720 00:29:52,900 --> 00:29:54,628 Mae hyn yn fath swigen. 721 00:29:54,628 --> 00:30:10,097 >> [Tones CHWARAE] 722 00:30:10,097 --> 00:30:13,630 >> DAVID Malan: A allwch chi ddatrys o deimlad sut mae cymharol ychydig o waith mae'n gwneud 723 00:30:13,630 --> 00:30:15,834 ar bob cam. 724 00:30:15,834 --> 00:30:20,470 Mae hyn yn beth tediousness swnio fel. 725 00:30:20,470 --> 00:30:21,472 >> [Tones CHWARAE] 726 00:30:21,472 --> 00:30:25,222 >> DAVID Malan: Mae hwn yn fath dethol, lle rydym yn dewis yr elfen ydym eisiau trwy 727 00:30:25,222 --> 00:30:28,845 mynd trwy eto ac eto ac eto a'i roi ar y dechrau. 728 00:30:28,845 --> 00:30:37,674 >> [Tones CHWARAE] 729 00:30:37,674 --> 00:30:43,970 >> DAVID Malan: Mae hyn yn cyfuno math, sy'n gallwch chi wir yn dechrau teimlo. 730 00:30:43,970 --> 00:30:51,810 >> [Tones CHWARAE] 731 00:30:51,810 --> 00:30:54,770 >> [Chwerthin] 732 00:30:54,770 --> 00:30:58,395 >> DAVID Malan: Rhywbeth o'r enw gnome fath, nad ydym wedi edrych ar. 733 00:30:58,395 --> 00:31:13,630 >> [Tones CHWARAE] 734 00:31:13,630 --> 00:31:17,910 >> DAVID Malan: Felly, gadewch i mi weld, yn awr, canolbwyntio ar y ffordd wrth i chi gobeithio bod gan y 735 00:31:17,910 --> 00:31:21,110 cerddoriaeth, os gallaf lithro ychydig ychydig o cwestiwn yma. 736 00:31:21,110 --> 00:31:24,850 Felly mae pedwerydd ffordd y gallwn meddwl am yr hyn y mae'n ei olygu hyn 737 00:31:24,850 --> 00:31:29,210 swyddogaethau i fod yn gyflymach na rhai yr ydym wedi ei weld o'r blaen. 738 00:31:29,210 --> 00:31:32,470 Ac os ydych yn dod ar y cwrs cefndir mathemateg, rydych yn 739 00:31:32,470 --> 00:31:36,030 mewn gwirionedd yn gwybod efallai eich bod eisoes yn Gall slap tymor ar y dechneg hon - 740 00:31:36,030 --> 00:31:40,400 sef recursion, rhaid i swyddogaeth hynny rywsut yn galw ei hun. 741 00:31:40,400 --> 00:31:44,780 >> Ac eto, dwyn i gof bod uno math pseudocode yn ailadroddus yn yr ystyr 742 00:31:44,780 --> 00:31:48,460 mai un o'r camau uno fath yn oedd i alw fath - 743 00:31:48,460 --> 00:31:49,740 hynny yw, ei hun. 744 00:31:49,740 --> 00:31:52,480 Ond diolch byth, oherwydd ein bod yn cadw galw didoli, neu gyfuno fath, 745 00:31:52,480 --> 00:31:55,880 yn benodol, ar lai a llai a rhestr llai, yn y pen draw 746 00:31:55,880 --> 00:32:00,005 gwaelod, diolch i'r hyn y byddwn yn galw achos sylfaenol, yr achos hard-coded bod 747 00:32:00,005 --> 00:32:04,270 Dywedodd os yw'r rhestr yn fach, llai na 2 yn yr achos hwnnw, dim ond dychwelyd ar unwaith. 748 00:32:04,270 --> 00:32:07,550 Os nad oedd gennym yr achos arbennig, y Ni fyddai algorithm gwaelod allan, 749 00:32:07,550 --> 00:32:11,010 a byddech yn wir yn mynd i mewn i dolen ddiddiwedd wir am byth. 750 00:32:11,010 --> 00:32:14,330 >> Ond mae'n debyg ein bod am roi yn awr rhai rhifau ar hyn, unwaith eto, gan ddefnyddio n 751 00:32:14,330 --> 00:32:15,660 gan fod maint y mewnbwn. 752 00:32:15,660 --> 00:32:18,680 Ac yr wyf yn awyddus i ofyn i chi, beth cyfanswm yr amser sy'n ymwneud â 753 00:32:18,680 --> 00:32:19,800 rhedeg fath uno? 754 00:32:19,800 --> 00:32:22,960 Neu yn fwy cyffredinol, beth y gost o mewn pryd? 755 00:32:22,960 --> 00:32:24,730 >> Wel, mae'n eithaf hawdd i fesur hynny. 756 00:32:24,730 --> 00:32:29,010 Os yw n yn llai na 2, yr amser dan sylw wrth ddidoli n elfennau, 757 00:32:29,010 --> 00:32:30,480 lle mae n yn 2, yw 0. 758 00:32:30,480 --> 00:32:31,410 Oherwydd ein bod yn unig yn dychwelyd. 759 00:32:31,410 --> 00:32:32,510 Does dim gwaith i'w wneud o hyd. 760 00:32:32,510 --> 00:32:35,660 Nawr gellir dadlau, efallai ei fod yn un cam neu ddau camau i chyfrif i maes faint o 761 00:32:35,660 --> 00:32:38,420 gweithio, ond mae'n ddigon agos i 0 y Im 'jyst yn mynd i ddweud dim gwaith yn 762 00:32:38,420 --> 00:32:40,940 angenrheidiol os y rhestr mor fach i anniddorol. 763 00:32:40,940 --> 00:32:42,580 >> Ond yr achos hwn yn ddiddorol. 764 00:32:42,580 --> 00:32:47,320 Mae'r achos recursive oedd y gangen o y pseudocode a ddywedodd arall, didoli 765 00:32:47,320 --> 00:32:52,000 yr hanner chwith, ddatrys yr hawl hanner, uno'r ddau hanner. 766 00:32:52,000 --> 00:32:55,530 Nawr, pam mae ymadrodd hwn cynrychioli'r gost? 767 00:32:55,530 --> 00:32:58,690 Wel, T y n unig yn golygu y amser i ddatrys elfennau n. 768 00:32:58,690 --> 00:33:03,070 Ac yna ar yr ochr dde-law y arwydd hafal yno, mae'r T n rhannu 769 00:33:03,070 --> 00:33:06,600 gan 2 yn cyfeirio at y gost o beth? 770 00:33:06,600 --> 00:33:07,570 Didoli yr hanner chwith. 771 00:33:07,570 --> 00:33:10,990 Mae T arall n rhannu gan 2 cyfeirio yn ôl pob tebyg at y gost i 772 00:33:10,990 --> 00:33:12,390 ddatrys yr hanner cywir. 773 00:33:12,390 --> 00:33:14,590 >> Ac yna y plws n? 774 00:33:14,590 --> 00:33:15,420 A yw'r uno. 775 00:33:15,420 --> 00:33:19,120 Oherwydd os oes gennych dwy restr, un o maint n dros 2 ac un arall o faint n 776 00:33:19,120 --> 00:33:22,580 dros 2, rhaid i chi gyffwrdd yn y bôn pob un o'r elfennau hynny, yn union fel Rob 777 00:33:22,580 --> 00:33:24,990 cyffwrdd pob un o'r cwpanau, a dim ond wrth i ni nodwyd ym mhob un o'r 778 00:33:24,990 --> 00:33:26,310 gwirfoddolwyr ar y llwyfan. 779 00:33:26,310 --> 00:33:28,790 Felly, mae n yn y gost o uno. 780 00:33:28,790 --> 00:33:31,780 >> Nawr yn anffodus, fformiwla hon hefyd yn ei hun yn recursive. 781 00:33:31,780 --> 00:33:36,390 Felly, os gofynnir y cwestiwn, os n yw, dweud, 16, os oes 16 o bobl ar y llwyfan 782 00:33:36,390 --> 00:33:40,670 neu 16 cwpan yn y fideo, faint o gyfanswm camau y mae'n ei gymryd i ddatrys eu 783 00:33:40,670 --> 00:33:41,550 gyda uno fath? 784 00:33:41,550 --> 00:33:45,790 Mae'n mewn gwirionedd nid yw'n ateb amlwg, oherwydd erbyn hyn mae'n rhaid i chi ddatrys y 785 00:33:45,790 --> 00:33:48,500 recursively ateb y fformiwla hon. 786 00:33:48,500 --> 00:33:51,190 >> Ond mae hynny'n iawn, oherwydd gadewch i mi gynnig ein bod yn gwneud y canlynol. 787 00:33:51,190 --> 00:33:56,670 Mae'r amser dan sylw i ddatrys 16 o bobl neu 16 cwpan yn mynd i gael ei gynrychioli 788 00:33:56,670 --> 00:33:58,020 gyffredinol fel T o 16. 789 00:33:58,020 --> 00:34:01,400 Ond mae hynny'n gyfartal, yn ôl ein fformiwla blaenorol, 2 gwaith y swm 790 00:34:01,400 --> 00:34:04,780 o amser mae'n ei gymryd i ddatrys 8 cwpan a 16. 791 00:34:04,780 --> 00:34:08,590 Ac eto, yn ogystal â 16 yw'r amser i uno, ac mae'r ddau amseroedd T o 8 yw'r 792 00:34:08,590 --> 00:34:10,790 amser i ddatrys chwith hanner a hanner i'r dde. 793 00:34:10,790 --> 00:34:11,989 >> Ond unwaith eto, nid yw hyn yn ddigon. 794 00:34:11,989 --> 00:34:13,210 Mae'n rhaid i ddeifio yn ddyfnach. 795 00:34:13,210 --> 00:34:16,409 Mae hyn yn golygu bod rhaid i ateb y cwestiwn, beth yw T o 8? 796 00:34:16,409 --> 00:34:19,610 Wel T o 8 yn unig 2 amseroedd T o 4 ac 8. 797 00:34:19,610 --> 00:34:20,520 Wel, beth T o 4? 798 00:34:20,520 --> 00:34:23,780 T o 4 yn unig 2 waith T o 2 a 4. 799 00:34:23,780 --> 00:34:25,489 Wel, beth T o 2? 800 00:34:25,489 --> 00:34:29,030 T o 2 yn unig 2 waith T o 1 a 2. 801 00:34:29,030 --> 00:34:31,940 >> Ac eto, rydym yn fath o gael yn sownd yn y cylch hwn. 802 00:34:31,940 --> 00:34:34,790 Ond mae'n ar fin cyrraedd y hyn a elwir yn achos sylfaenol. 803 00:34:34,790 --> 00:34:37,310 Oherwydd yr hyn sy'n T o 1, gwnaethom hawlio? 804 00:34:37,310 --> 00:34:37,810 0. 805 00:34:37,810 --> 00:34:39,730 Felly nawr yn olaf, gallwn weithio tuag yn ôl. 806 00:34:39,730 --> 00:34:44,290 >> Os yw T o 1 yn 0, gallaf yn awr yn mynd yn ôl i fyny un llinell i hyn guy yma, ac yr wyf yn gallu 807 00:34:44,290 --> 00:34:46,330 plwg yn 0 ar gyfer T o 1. 808 00:34:46,330 --> 00:34:51,770 Felly, mae hynny'n golygu ei fod yn hafal i 2 gwaith sero, a elwir fel arall fel 0, a 2. 809 00:34:51,770 --> 00:34:53,739 Ac felly y ceir yr ymadrodd cyfan yw 2. 810 00:34:53,739 --> 00:34:58,740 >> Nawr, os wyf yn cymryd y T 2, y mae ei ateb yw 2, plwg i mewn i'r llinell ganol, T 811 00:34:58,740 --> 00:35:02,740 o 4, sy'n rhoi 2 gwaith i mi 2 a 4, hynny 8. 812 00:35:02,740 --> 00:35:07,080 Os yna rwyf yn plwg yn 8 i Ddeddf blaenorol lein, sy'n rhoi 2 gwaith 8, 16 i mi. 813 00:35:07,080 --> 00:35:12,470 Ac os ydym wedyn yn parhau i hynny gyda'r 24, gan ychwanegu mewn 16, rydym o'r diwedd yn cael 814 00:35:12,470 --> 00:35:13,820 werth o 64. 815 00:35:13,820 --> 00:35:18,480 >> Nawr bod mewn ac o ei hun math o siarad ddim i nodiant n, y 816 00:35:18,480 --> 00:35:20,700 O fawr, y omega a rydym wedi bod yn siarad am. 817 00:35:20,700 --> 00:35:24,890 Ond mae'n troi allan bod 64 yn wir 16, mae'r maint y mewnbwn, 818 00:35:24,890 --> 00:35:27,110 log sylfaen 2 o 16. 819 00:35:27,110 --> 00:35:30,200 Ac os yw hyn yn ychydig yn anghyfarwydd, dim ond meddwl yn ôl, a bydd yn dod yn ôl 820 00:35:30,200 --> 00:35:30,700 i chi yn y pen draw. 821 00:35:30,700 --> 00:35:33,775 Os yw hyn yn sylfaen log 2, mae fel 2 godi i'r hyn sy'n rhoi 16 i chi? 822 00:35:33,775 --> 00:35:36,380 O, dyna 4, felly mae'n 16 gwaith 4. 823 00:35:36,380 --> 00:35:39,380 >> Ac eto, nid yw'n llawer mawr os yw hyn yn yn fath o gof niwlog awr. 824 00:35:39,380 --> 00:35:43,720 Ond am y tro, yn cymryd ar ffydd fod 16 log 16 yw 64. 825 00:35:43,720 --> 00:35:46,590 Ac felly yn wir, gyda'r bwyll syml gwirio, rydym wedi cadarnhau - 826 00:35:46,590 --> 00:35:48,250 ond nid yn profi yn ffurfiol - 827 00:35:48,250 --> 00:35:52,800 bod yr amser yn rhedeg o uno fath yn wir n mewngofnodi n. 828 00:35:52,800 --> 00:35:53,790 >> Felly, nid drwg. 829 00:35:53,790 --> 00:35:57,260 Mae'n bendant yn well na'r algorithmau rydym wedi gweld hyd yn hyn, a 830 00:35:57,260 --> 00:36:00,710 mae'n oherwydd ein bod wedi ysgogi, un, techneg o'r enw recursion. 831 00:36:00,710 --> 00:36:03,880 Ond yn fwy diddorol na hynny, bod syniad o rannu a concro. 832 00:36:03,880 --> 00:36:07,460 Unwaith eto, yr wythnos wirioneddol 0 pethau sy'n hyd yn oed yn awr yn ailddigwydd mewn 833 00:36:07,460 --> 00:36:08,740 ffordd fwy cymhellol. 834 00:36:08,740 --> 00:36:11,750 >> Erbyn hyn, mae ymarfer ychydig o hwyl, os ydych wedi byth yn gwneud hyn - ac mae'n debyg y 835 00:36:11,750 --> 00:36:14,660 Ni fyddai'n rhaid, oherwydd math o normal nad yw pobl yn meddwl i wneud hyn. 836 00:36:14,660 --> 00:36:20,650 Ond os byddaf yn mynd i google.com ac os Rwyf am i ddysgu rhywbeth am 837 00:36:20,650 --> 00:36:22,356 recursion, Enter. 838 00:36:22,356 --> 00:36:25,106 839 00:36:25,106 --> 00:36:29,058 >> [Chwerthin] 840 00:36:29,058 --> 00:36:32,030 [Chwerthin MWY] 841 00:36:32,030 --> 00:36:33,385 DAVID Malan: jôc drwg lledaenu yn araf. 842 00:36:33,385 --> 00:36:34,450 [Chwerthin] 843 00:36:34,450 --> 00:36:36,970 DAVID Malan: Rhag ofn, ei fod yno. 844 00:36:36,970 --> 00:36:38,710 Doeddwn i ddim yn sillafu yn anghywir, ac mae 'y jôc. 845 00:36:38,710 --> 00:36:40,810 Mae pob hawl. 846 00:36:40,810 --> 00:36:42,950 Esbonio i'r bobl nesaf i chi os Nid yn gwbl wedi clicio eto. 847 00:36:42,950 --> 00:36:47,650 Ond recursion, yn fwy cyffredinol, yn cyfeirio i'r broses o swyddogaeth galw 848 00:36:47,650 --> 00:36:51,430 ei hun, neu yn fwy cyffredinol, rhannu a problem yn rhywbeth y gellir ei 849 00:36:51,430 --> 00:36:56,220 datrys dameidiog drwy ddatrys union yr un fath problemau cynrychioliadol. 850 00:36:56,220 --> 00:36:58,400 >> Newid gerau Wel, gadewch i ni am ddim ond ennyd. 851 00:36:58,400 --> 00:37:00,840 Rydym yn hoffi i ben ar rai cliffhangers, felly gadewch i ni ddechrau i osod 852 00:37:00,840 --> 00:37:05,870 y llwyfan, am sawl munud, ar syniad syml iawn - 853 00:37:05,870 --> 00:37:07,620 hynny o gyfnewid dwy elfen, dde? 854 00:37:07,620 --> 00:37:10,040 Mae pob un o'r algorithmau hyn, rydym wedi bod yn siarad am y cwpl yn y gorffennol 855 00:37:10,040 --> 00:37:12,420 darlithoedd cynnwys rhai math o gyfnewid. 856 00:37:12,420 --> 00:37:14,630 Heddiw, cafodd ei dychmygu drwy eu cael i fyny allan o'u cadeiriau a 857 00:37:14,630 --> 00:37:18,570 cerdded o gwmpas, ond mewn cod, byddem yn dim ond yn cymryd elfen o un amrywiaeth 858 00:37:18,570 --> 00:37:20,370 a sw n plopian i mewn i un arall. 859 00:37:20,370 --> 00:37:21,880 >> Felly, sut rydym yn mynd ati i wneud hyn? 860 00:37:21,880 --> 00:37:24,850 Wel, gadewch i mi fynd yn ei flaen ac ysgrifennu rhaglen hwylus yma. 861 00:37:24,850 --> 00:37:31,600 Rydw i'n mynd i fynd yn ei flaen a gwneud hyn fel y canlynol. 862 00:37:31,600 --> 00:37:33,910 Gadewch i ni yn galw hyn - 863 00:37:33,910 --> 00:37:38,070 beth ydyn ni am i alw hyn yn un? 864 00:37:38,070 --> 00:37:38,650 >> A dweud y gwir, dim. 865 00:37:38,650 --> 00:37:39,420 Gadewch i mi ailddirwyn. 866 00:37:39,420 --> 00:37:41,220 Nid wyf am wneud hynny Cliffhanger eto. 867 00:37:41,220 --> 00:37:42,270 Bydd yn difetha'r hwyl. 868 00:37:42,270 --> 00:37:43,600 Gadewch i ni wneud hwn yn lle. 869 00:37:43,600 --> 00:37:47,430 >> Gadewch i ni dybio fy mod am i ysgrifennu ychydig rhaglen, ac sydd bellach yn cynnwys hyn 870 00:37:47,430 --> 00:37:48,700 syniad o recursion. 871 00:37:48,700 --> 00:37:50,370 Yr wyf yn fath o got blaen arnaf fy hun. 872 00:37:50,370 --> 00:37:51,420 Rydw i'n mynd i wneud y canlynol. 873 00:37:51,420 --> 00:38:00,220 >> Yn gyntaf, cyflym cynnwys o safon io.h, yn ogystal â cynnwys o cs50.h. 874 00:38:00,220 --> 00:38:03,200 Ac yna yr wyf i'n mynd i fynd yn ei flaen a datgan int brif ddi-rym 875 00:38:03,200 --> 00:38:04,360 yn y ffordd arferol. 876 00:38:04,360 --> 00:38:07,920 Sylweddolais fy mod i wedi misnamed y ffeil, felly gadewch i mi ychwanegu estyniad c. yma fel 877 00:38:07,920 --> 00:38:09,510 y gallwn lunio yn iawn. 878 00:38:09,510 --> 00:38:10,970 Dechrau swyddogaeth hon i ffwrdd. 879 00:38:10,970 --> 00:38:13,290 >> Ac mae'r swyddogaeth yr wyf am i ysgrifennu, yn eithaf yn syml, yn un sy'n gofyn y 880 00:38:13,290 --> 00:38:16,210 defnyddiwr ar gyfer nifer ac wedyn yn ychwanegu i fyny holl rifau rhwng y 881 00:38:16,210 --> 00:38:19,920 nifer a, dyweder, 0. 882 00:38:19,920 --> 00:38:22,510 Felly, yn gyntaf yr wyf i'n mynd i fynd yn ei flaen a datgan n int. 883 00:38:22,510 --> 00:38:24,760 Yna mi gopïo rhai cod sy'n rydym wedi defnyddio am gyfnod. 884 00:38:24,760 --> 00:38:26,660 Er bod rhywbeth yn wir. 885 00:38:26,660 --> 00:38:28,000 'N annhymerus' yn dod yn ôl at hynny mewn munud. 886 00:38:28,000 --> 00:38:29,010 >> Beth ydw i am ei wneud? 887 00:38:29,010 --> 00:38:33,460 Yr wyf am ddweud printf cadarnhaol cyfanrif gwelwch yn dda. 888 00:38:33,460 --> 00:38:36,130 Ac yna yr wyf i'n mynd i dweud n cael cael int. 889 00:38:36,130 --> 00:38:38,800 Felly, unwaith eto, mae rhai côd boilerplate ein bod wedi defnyddio o'r blaen. 890 00:38:38,800 --> 00:38:40,810 Ac yr wyf i'n mynd i wneud hyn tra n yn llai nag 1. 891 00:38:40,810 --> 00:38:44,120 Felly, bydd hyn yn sicrhau bod y defnyddiwr rhoi cyfanrif positif mi. 892 00:38:44,120 --> 00:38:45,490 >> Ac yn awr yr wyf i'n mynd i wneud y canlynol. 893 00:38:45,490 --> 00:38:51,020 Yr wyf am ychwanegu at yr holl o'r rhifau rhwng 1 a a n, neu 0 a n, 894 00:38:51,020 --> 00:38:52,570 equivalently, i gael cyfanswm. 895 00:38:52,570 --> 00:38:55,100 Felly, y symbol sigma mawr y gallai byddwch yn cofio. 896 00:38:55,100 --> 00:38:59,050 Felly, yr wyf i'n mynd i wneud hyn drwy ffonio gyntaf swyddogaeth o'r enw sigma, 897 00:38:59,050 --> 00:39:06,030 basio yn n, ac yna rwy'n mynd i dweud printf, yr ateb yn iawn yno. 898 00:39:06,030 --> 00:39:08,180 >> Felly, yn fyr, yr wyf yn ei gael ac int gan y defnyddiwr. 899 00:39:08,180 --> 00:39:09,280 Rwyf yn sicrhau ei fod yn gadarnhaol. 900 00:39:09,280 --> 00:39:12,700 Yr wyf yn datgan ateb a elwir yn amrywiol o int math a storio ynddo y ffurflen 901 00:39:12,700 --> 00:39:15,610 gwerth sigma, gan fynd yn n fel mewnbwn. 902 00:39:15,610 --> 00:39:17,060 Ac yna yr wyf argraffu yr ateb hwnnw. 903 00:39:17,060 --> 00:39:19,550 >> Yn anffodus, er bod sigma swnio'n fel rhywbeth a allai fod yn 904 00:39:19,550 --> 00:39:24,040 y ffeil math.h, ei datganiad, mae'n mewn gwirionedd yn peidio. 905 00:39:24,040 --> 00:39:24,690 Felly, mae hynny'n iawn. 906 00:39:24,690 --> 00:39:26,170 Gallaf roi hyn ar waith fy hun. 907 00:39:26,170 --> 00:39:29,160 Rydw i'n mynd i weithredu swyddogaeth o'r enw sigma, ac mae'n mynd i gymryd 908 00:39:29,160 --> 00:39:29,900 paramedr - 909 00:39:29,900 --> 00:39:32,100 gadewch i ni ei alw'n m, dim ond felly mae'n wahanol. 910 00:39:32,100 --> 00:39:35,910 Ac yna i fyny yma, dw i'n mynd i ddweud, yn dda, os m yn llai na 1 - mae hyn yn 911 00:39:35,910 --> 00:39:38,180 rhaglen anniddorol iawn. 912 00:39:38,180 --> 00:39:41,700 Felly, yr wyf i'n mynd i fynd yn ei flaen a dychwelyd ar unwaith 0. 913 00:39:41,700 --> 00:39:45,920 Mae'n nid yn unig yn gwneud synnwyr i ychwanegu at yr holl y rhifau rhwng 1 a m os m 914 00:39:45,920 --> 00:39:48,470 ei hun yn 0 neu negyddol. 915 00:39:48,470 --> 00:39:50,900 >> Ac yna yr wyf i'n mynd i fynd yn ei flaen a gwneud hyn yn iteraidd iawn. 916 00:39:50,900 --> 00:39:53,090 Rydw i'n mynd i wneud y math hwn o hen-ysgol, ac yr wyf i'n mynd i fynd yn ei flaen 917 00:39:53,090 --> 00:39:57,150 a dweud fy mod i'n mynd i datgan swm i fod yn 0. 918 00:39:57,150 --> 00:39:59,630 Yna mi i'n mynd i gael a ar gyfer dolen int - 919 00:39:59,630 --> 00:40:02,820 a gadewch i mi ei wneud i gyd-fynd ein cod dosbarthu, er mwyn i chi gael copi 920 00:40:02,820 --> 00:40:07,500 yn y cartref. int i yn cael 1 ar hyd at i yn llai na neu'n hafal i m. 921 00:40:07,500 --> 00:40:09,430 i yn ogystal a mwy. 922 00:40:09,430 --> 00:40:11,430 Ac yna y tu mewn o hyn ar gyfer dolen - 923 00:40:11,430 --> 00:40:12,440 rydym yn bron yno - 924 00:40:12,440 --> 00:40:15,810 swm yn cael swm ac 1. 925 00:40:15,810 --> 00:40:17,670 Ac yna dwi'n mynd i ddychwelyd y swm. 926 00:40:17,670 --> 00:40:19,420 >> Felly, yr wyf yn gwneud hyn yn gyflym, eithaf cyfaddef. 927 00:40:19,420 --> 00:40:22,775 Ond unwaith eto, y prif swyddogaeth 'n bert syml, yn seiliedig ar god rydym wedi 928 00:40:22,775 --> 00:40:23,190 ysgrifenedig hyd yn hyn. 929 00:40:23,190 --> 00:40:25,610 Yn defnyddio'r ddolen deuol i gael cadarnhaol int gan y defnyddiwr. 930 00:40:25,610 --> 00:40:29,870 Yna yn trosglwyddo'r int i swyddogaeth newydd enw sigma, yn galw yn, unwaith eto, n. 931 00:40:29,870 --> 00:40:33,100 Ac yr wyf yn storio gwerth gyfnewid, mae'r ateb o'r blwch du ar hyn o bryd 932 00:40:33,100 --> 00:40:35,460 a elwir yn sigma, mewn newidyn a elwir yn ateb. 933 00:40:35,460 --> 00:40:36,580 Yna mi ei hargraffu. 934 00:40:36,580 --> 00:40:39,090 >> Os byddwn yn awr yn parhau y stori, sut mae sigma gweithredu? 935 00:40:39,090 --> 00:40:40,840 Yr wyf yn bwriadu gweithredu fel a ganlyn. 936 00:40:40,840 --> 00:40:43,560 Yn gyntaf, ychydig bach o wall-gwirio i wneud yn siŵr nad yw'r defnyddiwr yn 937 00:40:43,560 --> 00:40:46,480 cyboli gyda mi ac yn pasio mewn rhywfaint o werth negyddol neu 0. 938 00:40:46,480 --> 00:40:49,710 Yna mi ddatgan amrywiol o'r enw swm a'i osod i 0. 939 00:40:49,710 --> 00:40:55,910 >> Ac yn awr yr wyf yn dechrau symud o hafal i 1 yr holl ffordd i fyny at ac yn cynnwys m, 940 00:40:55,910 --> 00:41:00,130 oherwydd yr wyf am i gynnwys yr holl rhifau o un drwy m, cynhwysol. 941 00:41:00,130 --> 00:41:04,350 Ac y tu mewn o hyn ar gyfer dolen, Fi jyst yn ei wneud swm yn cael beth bynnag y mae yn awr, yn ogystal â'r 942 00:41:04,350 --> 00:41:08,900 werth i. 943 00:41:08,900 --> 00:41:10,370 Byd Gwaith gwerth i. 944 00:41:10,370 --> 00:41:14,090 >> Fel o'r neilltu, os nad ydych wedi gweld y o'r blaen, mae rhywfaint o siwgr cystrawennol 945 00:41:14,090 --> 00:41:14,870 ar gyfer y llinell hon. 946 00:41:14,870 --> 00:41:21,120 Gallaf ailysgrifennu'r hyn fel a mwy hafal i, dim ond i arbed fy hun ychydig keystrokes 947 00:41:21,120 --> 00:41:22,570 ac i edrych ychydig yn oerach. 948 00:41:22,570 --> 00:41:23,140 Ond dyna i gyd. 949 00:41:23,140 --> 00:41:24,660 Mae'n swyddogaethol yr un peth. 950 00:41:24,660 --> 00:41:26,710 >> Yn anffodus, y cod hwn yn ddim yn mynd i lunio eto. 951 00:41:26,710 --> 00:41:31,600 Os byddaf yn rhedeg wneud sigma 0, sut wyf yn I'n mynd i gael yelled arno? 952 00:41:31,600 --> 00:41:33,473 Beth rwyt ti'n mynd i yn ei hoffi? 953 00:41:33,473 --> 00:41:35,740 >> GYNULLEIDFA: [Anghlywadwy]. 954 00:41:35,740 --> 00:41:37,800 >> DAVID Malan: Yeah, doeddwn i ddim yn datgan y swyddogaeth atodol, dde? 955 00:41:37,800 --> 00:41:40,590 C yn fath o dwp, gan ei fod dim ond yn gwneud yr hyn yr ydych yn dweud iddo ei wneud, ac rydych 956 00:41:40,590 --> 00:41:41,880 rhaid i ni wneud hynny yn y drefn honno. 957 00:41:41,880 --> 00:41:45,910 Ac felly os byddaf yn taro Rhowch yma, yr wyf i'n mynd i cael rhybudd am sigma ymhlyg 958 00:41:45,910 --> 00:41:46,860 datganiad. 959 00:41:46,860 --> 00:41:48,120 >> Oh, nid problem. 960 00:41:48,120 --> 00:41:50,370 Gallaf fynd i fyny at y brig, a gallaf dweud, popeth yn iawn, arhoswch funud. 961 00:41:50,370 --> 00:41:54,240 Sigma yn swyddogaeth sy'n dychwelyd yn int ac mae'n disgwyl i 962 00:41:54,240 --> 00:41:56,620 int fel mewnbwn, hanner colon. 963 00:41:56,620 --> 00:41:59,550 Neu gallwn roi'r holl swyddogaeth uchod yn bennaf, ond yn gyffredinol, yr wyf i wedi 964 00:41:59,550 --> 00:42:02,260 argymell yn erbyn hynny, oherwydd ei fod yn braf i bob amser yn cael prif ar y brig fel y 965 00:42:02,260 --> 00:42:06,310 gallwch deifio i'r dde i mewn ac yn gwybod beth yw rhaglen yn ei wneud trwy ddarllen prif gyntaf. 966 00:42:06,310 --> 00:42:07,930 >> Felly nawr gadewch i mi glirio'r sgrin. 967 00:42:07,930 --> 00:42:09,330 Ail-wneud Sigma 0. 968 00:42:09,330 --> 00:42:10,340 Gyd yn ymddangos i edrych ar. 969 00:42:10,340 --> 00:42:11,970 Gadewch i mi redeg sigma 0. 970 00:42:11,970 --> 00:42:12,770 Rhyng Cadarnhaol. 971 00:42:12,770 --> 00:42:15,580 Byddaf yn rhoi y nifer 3 i'w gadw'n syml. 972 00:42:15,580 --> 00:42:18,710 Felly dylai hynny roi i mi 3 ynghyd â 2 plws 1, felly 6. 973 00:42:18,710 --> 00:42:20,750 Fynd i mewn, ac yn wir i mi gael 6. 974 00:42:20,750 --> 00:42:21,820 >> Allaf wneud rhywbeth mwy - 975 00:42:21,820 --> 00:42:24,080 50, 12, 75. 976 00:42:24,080 --> 00:42:27,690 Yn union fel tangiad, yr wyf i'n mynd i wneud rhywbeth chwerthinllyd fel fawr iawn 977 00:42:27,690 --> 00:42:30,375 rhif, O, sydd mewn gwirionedd yn gweithio allan - 978 00:42:30,375 --> 00:42:31,600 eh, nid wyf yn credu bod hynny'n iawn. 979 00:42:31,600 --> 00:42:32,810 Gadewch i ni weld. 980 00:42:32,810 --> 00:42:34,060 Gadewch i ni llanast iawn ag ef. 981 00:42:34,060 --> 00:42:37,150 982 00:42:37,150 --> 00:42:38,400 >> Mae hynny'n broblem. 983 00:42:38,400 --> 00:42:43,180 984 00:42:43,180 --> 00:42:44,970 Beth sy'n digwydd? 985 00:42:44,970 --> 00:42:46,050 Nid yw'r Cod yn ddrwg. 986 00:42:46,050 --> 00:42:48,470 Mae'n dal i fod llinol. 987 00:42:48,470 --> 00:42:50,810 Chwibanu yn cael effaith dda, er. 988 00:42:50,810 --> 00:42:52,060 Beth sy'n digwydd? 989 00:42:52,060 --> 00:42:54,700 990 00:42:54,700 --> 00:42:55,620 >> Ddim yn siwr os ydw i'n ei glywed. 991 00:42:55,620 --> 00:42:57,620 Felly, mae'n troi allan - ac hwn fel o'r neilltu. 992 00:42:57,620 --> 00:42:59,400 Nid yw hyn yn greiddiol i syniad o recursion. 993 00:42:59,400 --> 00:43:02,480 Mae'n troi allan, oherwydd fy mod i'n ceisio cynrychioli nifer mor fawr, mae'r rhan fwyaf 994 00:43:02,480 --> 00:43:06,980 debygol o fod yn cael ei gamddehongli gan C fel rhif yn gadarnhaol, 995 00:43:06,980 --> 00:43:09,980 ond mae rhif negatif. 996 00:43:09,980 --> 00:43:12,690 >> Nid ydym wedi sôn am hyn, ond mae'n troi allan bod rhifau negyddol 997 00:43:12,690 --> 00:43:14,210 yn y byd yn ogystal i rifau positif. 998 00:43:14,210 --> 00:43:16,290 A'r modd y gallwch cynrychioli nifer negyddol 999 00:43:16,290 --> 00:43:19,530 hanfod yw, byddwch yn defnyddio un eithaf arbennig i ddangos 1000 00:43:19,530 --> 00:43:20,400 gadarnhaol dros negyddol. 1001 00:43:20,400 --> 00:43:22,950 Mae'n ychydig yn fwy cymhleth na hynny, ond dyna'r syniad sylfaenol. 1002 00:43:22,950 --> 00:43:26,740 >> Felly, yn anffodus, os C yn ddryslyd un o ddarnau hynny fel mewn gwirionedd yn golygu, 1003 00:43:26,740 --> 00:43:30,790 oh, mae hwn yn rhif negyddol, fy dolen yma, er enghraifft, mewn gwirionedd byth yn 1004 00:43:30,790 --> 00:43:31,740 mynd i derfynu. 1005 00:43:31,740 --> 00:43:33,850 Felly, os wyf mewn gwirionedd yn argraffu rhywbeth dro ar ôl tro, byddem yn 1006 00:43:33,850 --> 00:43:34,650 gweld llawer cyfan. 1007 00:43:34,650 --> 00:43:36,220 Ond unwaith eto, mae hyn yn ar wahân i'r pwynt. 1008 00:43:36,220 --> 00:43:38,590 Mae hyn yn wir dim ond rhyw fath o chwilfrydedd deallusol y byddwn yn dod 1009 00:43:38,590 --> 00:43:39,550 yn ôl yn y pen draw. 1010 00:43:39,550 --> 00:43:43,400 Ond ar hyn o bryd, mae hwn yn gywir gweithredu os ydym yn tybio bod y 1011 00:43:43,400 --> 00:43:45,970 Bydd defnyddwyr yn darparu ints sy'n addas mewn ints. 1012 00:43:45,970 --> 00:43:49,370 >> Ond yr wyf yn honni bod y cod hwn, a dweud y gwir, y gellid ei wneud cymaint yn fwy syml. 1013 00:43:49,370 --> 00:43:54,060 Os yw'r nod wrth law i gymryd nifer fel m ac yn ychwanegu at yr holl o'r 1014 00:43:54,060 --> 00:43:59,510 rhifau rhyngddi ac 1, neu i'r gwrthwyneb rhwng 1 a hynny, gallaf wneud cais 1015 00:43:59,510 --> 00:44:03,380 y gallaf fenthyg syniad hwn y uno fath gael, a oedd yn cymryd problem 1016 00:44:03,380 --> 00:44:05,660 o'r maint hwn a'i rannu i mewn i rywbeth llai. 1017 00:44:05,660 --> 00:44:09,875 Efallai na hanner, ond yn llai, ond gynrychioliadol yr un fath. 1018 00:44:09,875 --> 00:44:12,130 Un syniad, ond mae problem llai. 1019 00:44:12,130 --> 00:44:15,470 >> Felly rwy'n mewn gwirionedd - gadewch i mi arbed y ffeil gyda rhif fersiwn gwahanol. 1020 00:44:15,470 --> 00:44:17,670 Byddwn yn galw hyn yn fersiwn 1 yn hytrach na 0. 1021 00:44:17,670 --> 00:44:20,790 Ac yr wyf yn honni y gallaf mewn gwirionedd reimplement hyn yn y math hwn o 1022 00:44:20,790 --> 00:44:22,160 meddwl-blygu ffordd. 1023 00:44:22,160 --> 00:44:23,710 >> Rydw i'n mynd i adael rhan ohono yn unig. 1024 00:44:23,710 --> 00:44:27,710 Rydw i'n mynd i ddweud os m yn llai hyd yn oed na neu'n hafal i 0 - 1025 00:44:27,710 --> 00:44:29,280 Im 'jyst yn mynd i fod ychydig yn mwy rhefrol y tro hwn 1026 00:44:29,280 --> 00:44:30,520 gyda fy wirio gwall - 1027 00:44:30,520 --> 00:44:33,190 Rydw i'n mynd i fynd yn ei flaen ac yn dychwelyd 0. 1028 00:44:33,190 --> 00:44:34,490 Mae hyn yn fympwyol. 1029 00:44:34,490 --> 00:44:37,500 Yr wyf yn syml penderfynu os yw'r defnyddiwr rhoi rhif negatif i mi, rwy'n 1030 00:44:37,500 --> 00:44:41,490 dychwelyd 0, a dylent fod wedi darllen y dogfennau yn agosach. 1031 00:44:41,490 --> 00:44:42,170 >> Arall - 1032 00:44:42,170 --> 00:44:44,070 sylwi ar yr hyn yr wyf i'n mynd i wneud. 1033 00:44:44,070 --> 00:44:49,260 Arall wyf yn mynd i ddychwelyd m a mwy - 1034 00:44:49,260 --> 00:44:51,010 beth yw sigma o m? 1035 00:44:51,010 --> 00:44:56,710 Wel, sigma o m a m minws 1, ynghyd â m minws 2, ynghyd m minws 3. 1036 00:44:56,710 --> 00:44:58,030 Nid wyf am i ysgrifennu i gyd allan. 1037 00:44:58,030 --> 00:44:59,120 Pam nad ydw i'n jyst punt? 1038 00:44:59,120 --> 00:45:05,080 Recursively galw fy hun gydag ychydig problem llai, hanner colon, 1039 00:45:05,080 --> 00:45:06,840 a galw yn y dydd? 1040 00:45:06,840 --> 00:45:07,040 >> Iawn? 1041 00:45:07,040 --> 00:45:10,980 Nawr dyma, hefyd, efallai y byddwch yn teimlo neu bryder bod hwn yn dolen ddiddiwedd fy mod yn 1042 00:45:10,980 --> 00:45:15,450 ysgogi, lle yr wyf yn gweithredu sigma drwy ffonio sigma. 1043 00:45:15,450 --> 00:45:20,342 Ond mae hynny'n berffaith iawn, gan fy mod yn meddwl ymlaen yn ychwanegol y llinellau? 1044 00:45:20,342 --> 00:45:22,600 >> GYNULLEIDFA: [Anghlywadwy]. 1045 00:45:22,600 --> 00:45:25,430 >> DAVID Malan: 23-26, sy'n yw fy os yw cyflwr. 1046 00:45:25,430 --> 00:45:28,390 Oherwydd yr hyn sy'n braf am y tynnu yma, oherwydd yr wyf yn cadw 1047 00:45:28,390 --> 00:45:31,180 trosglwyddo problemau llai sigma, llai problemau, llai - nid yw'n 1048 00:45:31,180 --> 00:45:31,870 hanner y maint. 1049 00:45:31,870 --> 00:45:34,380 Mae'n dim ond cam fabi llai, ond mae hynny'n iawn. 1050 00:45:34,380 --> 00:45:38,050 Oherwydd yn y pen draw, byddwn yn gweithio ein ffordd i lawr i 1 neu 0. 1051 00:45:38,050 --> 00:45:41,630 Ac unwaith y byddwn yn cyrraedd 0, nid sigma yn mynd i alw ei hun anymore. 1052 00:45:41,630 --> 00:45:43,590 Mae'n mynd i ddychwelyd 0 unwaith. 1053 00:45:43,590 --> 00:45:47,960 >> Felly, yr effaith, os ydych yn fath o wynt hwn i fyny yn eich meddwl, yw ychwanegu m plws 1054 00:45:47,960 --> 00:45:52,740 m minws 1, yn ogystal â m minws 2, yn ogystal â m minws 3, yn ogystal â dot, dot, dot, m minws 1055 00:45:52,740 --> 00:45:57,820 m, yn y pen draw yn rhoi 0 chi, ac y effaith yn y pen draw i ychwanegu'r holl 1056 00:45:57,820 --> 00:45:59,070 pethau hyn gyda'i gilydd. 1057 00:45:59,070 --> 00:46:02,380 Felly, nid ydym wedi, gyda recursion, datrys y broblem yr ydym yn 1058 00:46:02,380 --> 00:46:03,470 Ni ellid datrys o'r blaen. 1059 00:46:03,470 --> 00:46:06,840 Yn wir, fersiwn 0 o hyn, a phob broblem hyd yn hyn, wedi bod yn solvable 1060 00:46:06,840 --> 00:46:09,980 gyda dim ond defnyddio ar gyfer dolenni neu wrth dolenni neu lluniadau tebyg. 1061 00:46:09,980 --> 00:46:13,150 >> Ond recursion, mae'n siŵr, yn rhoi i ni ffordd wahanol o feddwl am 1062 00:46:13,150 --> 00:46:17,010 problemau, lle os gallwn gymryd problem, ei rannu o rywbeth 1063 00:46:17,010 --> 00:46:22,340 braidd yn fawr i fod yn rhywbeth braidd yn llai, gallaf hawlio y gallwn ddatrys 1064 00:46:22,340 --> 00:46:26,040 efallai ychydig yn fwy cain o ran y cynllun, gyda llai o cod, 1065 00:46:26,040 --> 00:46:30,980 ac efallai hyd yn oed yn datrys problemau a fyddai'n fod yn fwy anodd, gan ein bod yn y pen draw chi helpu 1066 00:46:30,980 --> 00:46:33,280 gweld, datrys yn unig iteraidd. 1067 00:46:33,280 --> 00:46:35,980 >> Ond mae'r Cliffhanger a wneuthum eisiau gadael ni ar oedd hyn. 1068 00:46:35,980 --> 00:46:40,720 Gadewch i mi fynd yn ei flaen ac yn agor i fyny ffeil o - 1069 00:46:40,720 --> 00:46:44,300 mewn gwirionedd, gadewch i mi fynd a gwneud hyn yn gyflym go iawn. 1070 00:46:44,300 --> 00:46:46,875 Gadewch i mi fynd yn ei flaen ac yn cynnig y canlynol. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Ymhlith Cod heddiw yn y ffeil yma. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 Mae hyn yn un yma, noswap. 1075 00:47:03,050 --> 00:47:06,260 >> Felly, mae hyn ychydig yn rhaglen wirion bod Yr wyf chwipio i fyny bod y ceisiadau i wneud 1076 00:47:06,260 --> 00:47:06,940 y canlynol. 1077 00:47:06,940 --> 00:47:10,140 Yn bennaf, mae'n datgan cyntaf i int enw x ac yn pennu ei 1078 00:47:10,140 --> 00:47:11,100 gwerth o 1. 1079 00:47:11,100 --> 00:47:13,520 Yna mae'n datgan y int a neilltuo yn werth 2. 1080 00:47:13,520 --> 00:47:15,310 Yna, bydd yn argraffu beth x ac y mae. 1081 00:47:15,310 --> 00:47:17,781 Yna y mae'n ei ddweud, cyfnewid, dot dot dot. 1082 00:47:17,781 --> 00:47:21,670 >> Yna mae'n honni eu bod yn galw swyddogaeth a elwir yn cyfnewid, gan fynd heibio yn x ac 1083 00:47:21,670 --> 00:47:24,290 y, y syniad o'r rhain yw bod gobaith Bydd x ac y yn dod yn ôl 1084 00:47:24,290 --> 00:47:25,620 wahanol, y gwrthwyneb. 1085 00:47:25,620 --> 00:47:27,110 Yna mae'n hawlio cyfnewid! 1086 00:47:27,110 --> 00:47:28,420 gyda phwynt ebychnod. 1087 00:47:28,420 --> 00:47:30,190 Yna, bydd yn argraffu allan x ac y. 1088 00:47:30,190 --> 00:47:33,480 >> Ond mae'n troi allan bod hyn yn iawn arddangosiad syml i lawr 1089 00:47:33,480 --> 00:47:35,570 dyma mewn gwirionedd buggy. 1090 00:47:35,570 --> 00:47:38,870 Hyd yn oed er fy mod yn datgan dros dro amrywiol a rhoi dros dro mewn 1091 00:47:38,870 --> 00:47:42,010 , yna rwy'n ailgyfeirio a gwerth b - 1092 00:47:42,010 --> 00:47:45,080 sy'n teimlo'n rhesymol, gan fy mod i wedi arbed copi o yn dros dro. 1093 00:47:45,080 --> 00:47:48,410 Yna mi diweddaru b i cyfartal beth bynnag oedd yn y tymheredd. 1094 00:47:48,410 --> 00:47:51,610 Mae'r math hwn o gêm cragen symud i mewn i b a b mewn drwy ddefnyddio'r 1095 00:47:51,610 --> 00:47:54,360 canol-dyn o'r enw dros dro yn teimlo gwbl resymol. 1096 00:47:54,360 --> 00:47:57,270 >> Ond yr wyf yn honni bod pan fyddaf yn rhedeg y cod, fel y byddaf yn ei wneud nawr - 1097 00:47:57,270 --> 00:47:59,490 gadewch i mi fynd yn ei flaen a'i gludo i mewn yma. 1098 00:47:59,490 --> 00:48:01,995 'N annhymerus' galw noswap.c hwn. 1099 00:48:01,995 --> 00:48:05,630 Ac fel yr awgryma'r enw, nid yw hyn yn mynd i fod yn rhaglen gywir. 1100 00:48:05,630 --> 00:48:09,460 Gwnewch noswap. / Dim cyfnewid. 1101 00:48:09,460 --> 00:48:12,110 x yw 1, y yn 2, cyfnewid, cyfnewid. 1102 00:48:12,110 --> 00:48:14,220 x yw 1, y mae 2. 1103 00:48:14,220 --> 00:48:16,920 Mae hyn yn sylfaenol anghywir, hyd yn oed er bod hyn yn ymddangos yn gwbl 1104 00:48:16,920 --> 00:48:17,730 rhesymol i mi. 1105 00:48:17,730 --> 00:48:21,330 Ac mae rheswm, ond nid ydym yn mynd i ddatgelu y rheswm eto. 1106 00:48:21,330 --> 00:48:24,610 >> Am y tro yr ail Cliffhanger roeddwn i eisiau i adael i chi yw hyn, mae 1107 00:48:24,610 --> 00:48:27,120 cyhoeddiad o ryw fath ar godau cwpon. 1108 00:48:27,120 --> 00:48:31,590 Mae ein arloesi gyda diwrnodau yn ddiweddarach eleni wedi ennyn rhif di-ddibwys 1109 00:48:31,590 --> 00:48:33,830 o gwestiynau, a oedd yn nid yw ein bwriad. 1110 00:48:33,830 --> 00:48:36,590 Bwriad y codau cwpon hyn, lle os byddwch yn rhan o'r broblem 1111 00:48:36,590 --> 00:48:39,850 gosod yn gynnar, a thrwy hynny cael diwrnod ychwanegol, oedd mewn gwirionedd i'ch helpu chi guys helpu 1112 00:48:39,850 --> 00:48:42,420 eich hun yn dechrau'n gynnar, trefnu o drwy incentivizing chi. 1113 00:48:42,420 --> 00:48:44,880 Helpu i ni dosbarthu llwyth ar draws oriau swyddfa well fel bod 1114 00:48:44,880 --> 00:48:45,740 ei fod yn fath o ennill-ennill. 1115 00:48:45,740 --> 00:48:48,860 >> Yn anffodus, yr wyf yn meddwl fy nghyfarwyddiadau nad ydynt wedi bod, hyd yn hyn, yn glir iawn, felly 1116 00:48:48,860 --> 00:48:52,230 Es i yn ôl y penwythnos hwn a'i ddiweddaru y fanyleb mewn maes mwy, testun beiddgar i 1117 00:48:52,230 --> 00:48:53,600 esbonio bwledi fel y rhain. 1118 00:48:53,600 --> 00:48:56,900 A dim ond i ddweud ei fod yn fwy cyhoeddus, gan diofyn, setiau problem yn ddyledus Dydd Iau 1119 00:48:56,900 --> 00:48:58,400 am hanner dydd, y maes llafur. 1120 00:48:58,400 --> 00:49:02,030 Os byddwch yn dechrau yn gynnar, gorffen yn rhan o y broblem a osodwyd erbyn dydd Mercher am 12:00 1121 00:49:02,030 --> 00:49:05,170 PM, y rhan sy'n ymwneud â cwpon cod, y syniad yw y gallwch ymestyn 1122 00:49:05,170 --> 00:49:07,710 eich dyddiad cau ar gyfer P gosod tan ddydd Gwener. 1123 00:49:07,710 --> 00:49:10,890 Hynny yw, ychydig oddi ar rhan fach iawn o'r P gosod mewn perthynas â hyn sydd fel arfer yn y 1124 00:49:10,890 --> 00:49:13,200 problem mwy o faint, ac rydych yn prynu eich hun diwrnod ychwanegol. 1125 00:49:13,200 --> 00:49:15,190 Unwaith eto, mae'n mynd i chi feddwl am y broblem a osodwyd, yn cael i chi 1126 00:49:15,190 --> 00:49:16,380 oriau swyddfa yn gynt. 1127 00:49:16,380 --> 00:49:20,670 Ond y broblem cod cwpon yn dal i fod angen, hyd yn oed os nad ydych yn ei gyflwyno. 1128 00:49:20,670 --> 00:49:23,340 >> Ond yn fwy gymhellol yw hyn. 1129 00:49:23,340 --> 00:49:26,520 (Sibrwd CAM) Ac Folks hynny sy'n gadael gynnar yn gonna yn difaru. 1130 00:49:26,520 --> 00:49:28,620 Fel y mae'r Folks ar y balconi. 1131 00:49:28,620 --> 00:49:32,510 Rwy'n ymddiheuro ymlaen llaw i'r Folks ar y balconi am resymau a fydd yn 1132 00:49:32,510 --> 00:49:33,920 glir mewn dim ond hyn o bryd. 1133 00:49:33,920 --> 00:49:37,050 >> Felly, rydym yn ffodus i gael un o'r Cyn cymrodyr addysgu pen CS50 ar 1134 00:49:37,050 --> 00:49:39,302 chwmni o'r enw dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 Maent wedi rhoi yn hael iawn cod cwpon yma am lawer lle hwn, 1136 00:49:45,500 --> 00:49:48,180 sydd wedi codi o'r 2 gigabeit arferol. 1137 00:49:48,180 --> 00:49:51,740 Felly, yr hyn yr wyf yn meddwl y byddem yn ei wneud ar hyn nodyn olaf yn gwneud ychydig o giveaway, 1138 00:49:51,740 --> 00:49:55,380 lle mewn dim ond hyn o bryd, byddwn yn datgelu yr enillydd ac sydd â cwpon 1139 00:49:55,380 --> 00:49:57,980 Cod y gallwch wedyn yn mynd at eu gwefan, teipiwch ef i mewn, a voila, yn cael 1140 00:49:57,980 --> 00:50:01,370 llawer iawn mwy Dropbox o le ar gyfer eich offer ac ar gyfer eich ffeiliau personol. 1141 00:50:01,370 --> 00:50:05,690 >> Ac yn gyntaf, a fyddai'n hoffi cymryd rhan yn y darlun hwn? 1142 00:50:05,690 --> 00:50:09,630 OK, nawr bod yn ei gwneud yn hyd yn oed yn fwy o hwyl. 1143 00:50:09,630 --> 00:50:14,010 Y person sy'n derbyn y 25-gigabyte cod cwpon - sy'n llawer 1144 00:50:14,010 --> 00:50:16,150 yn fwy grymus na'r diweddar ddiwrnod yn awr, efallai - 1145 00:50:16,150 --> 00:50:20,620 yw'r un sy'n eistedd ar ben clustog sedd o dan y mae 1146 00:50:20,620 --> 00:50:21,620 y cod cwpon. 1147 00:50:21,620 --> 00:50:23,480 Efallai y byddwch yn awr yn edrych o dan eich clustog sedd. 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 >> -Un, dau, tri. 1151 00:50:31,620 --> 00:50:35,015 >> [Screaming] 1152 00:50:35,015 --> 00:50:35,985 >> -Byddwch yn cael car! 1153 00:50:35,985 --> 00:50:36,670 Byddwch yn cael car! 1154 00:50:36,670 --> 00:50:37,970 >> DAVID Malan: Byddwn yn gweld chi ar Mercher. 1155 00:50:37,970 --> 00:50:38,904 >> -Byddwch yn cael car! 1156 00:50:38,904 --> 00:50:39,371 Byddwch yn cael car! 1157 00:50:39,371 --> 00:50:40,305 Byddwch yn cael car! 1158 00:50:40,305 --> 00:50:41,706 Byddwch yn cael car! 1159 00:50:41,706 --> 00:50:43,107 Byddwch yn cael car! 1160 00:50:43,107 --> 00:50:45,530 >> DAVID Malan: Folks Balconi, yn dod lawr yma i'r tu blaen, 1161 00:50:45,530 --> 00:50:46,866 lle mae gennym pethau ychwanegol. 1162 00:50:46,866 --> 00:50:50,282 >> -Mae pawb yn cael car! 1163 00:50:50,282 --> 00:50:52,234 Mae pawb yn cael car! 1164 00:50:52,234 --> 00:50:52,722 >> [VIDEO END Playback] 1165 00:50:52,722 --> 00:50:54,590 >> Adroddwr: Yn y CS50 nesaf - 1166 00:50:54,590 --> 00:51:00,374 >> SIARADWR 5: O fy diar diar diar diar diar diar diar diar diar diar - 1167 00:51:00,374 --> 00:51:02,106 >> [DRAMÂU ukelele]