1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> SIARADWR: pob hawl, mae hyn yn CS50. 3 00:00:14,910 --> 00:00:19,020 Mae hyn yn ddiwedd yr wythnos tri, ac os nad ydych wedi cymryd mantais eisoes, 4 00:00:19,020 --> 00:00:21,790 gwybod y bydd cinio dydd Gwener hwn yn ôl yr arfer, lle mae 5 00:00:21,790 --> 00:00:25,430 gallwch fwynhau sgwrs da a bwyd yng Tân ac Iâ 6 00:00:25,430 --> 00:00:27,980 gyda rhai o CS50 yn staff a chyd-ddisgyblion. 7 00:00:27,980 --> 00:00:30,170 Ewch i URL hwn yma. 8 00:00:30,170 --> 00:00:33,420 >> Nawr efallai y byddwch yn cofio, neu os ydych yn Efallai cyn bo hir yn cael ei adnabod, 9 00:00:33,420 --> 00:00:35,970 pethau hyn yma, a oedd yn yn cael eu rhoi allan ar y diwedd 10 00:00:35,970 --> 00:00:37,850 y semester ar gyfer llawer o ddosbarthiadau. 11 00:00:37,850 --> 00:00:40,870 Hyn a elwir yn arholiad llyfrau glas, lle chi ysgrifennu eich atebion i arholiadau. 12 00:00:40,870 --> 00:00:44,240 Nawr rwyf wedi yma 26 o'r fath llyfrau glas, ar bob un ohonynt 13 00:00:44,240 --> 00:00:47,580 ei ysgrifennu enw, A drwy Z. A yn wir yr enwau yn y syml, A 14 00:00:47,580 --> 00:00:50,490 drwy Z. Ac un o y nodau wrth law heddiw 15 00:00:50,490 --> 00:00:53,910 yn mynd i fod i barhau yr hyn rydym yn dechrau ar ddydd Llun, nad yw'n 16 00:00:53,910 --> 00:00:57,830 cymaint yn edrych ar god, ond mewn gwirionedd edrych ar syniadau a datrys problemau. 17 00:00:57,830 --> 00:01:00,170 Un o'r nodau ac addewidion y cwrs hwn 18 00:01:00,170 --> 00:01:02,985 yw eich dysgu i feddwl yn fwy ofalus, yn fwy yn drefnus, 19 00:01:02,985 --> 00:01:05,400 ac i ddatrys problemau yn fwy effeithlon. 20 00:01:05,400 --> 00:01:09,526 Ac yn wir, gallwn wneud hynny mewn gwirionedd heb hyd yn oed yn cyffwrdd y llinell o god. 21 00:01:09,526 --> 00:01:12,150 Felly mae gen i un neu ddau o eliffantod fyny yma heddiw, oren a glas, 22 00:01:12,150 --> 00:01:15,780 pe gallem gael un gwirfoddolwr, efallai o farther yn ôl na'r arfer. 23 00:01:15,780 --> 00:01:18,070 Beth am iawn yno, yn dod ar i lawr. 24 00:01:18,070 --> 00:01:24,180 Mae'r nod o sydd yn mynd i fod i help yn ogystal â gweinyddu'r arholiad hwn yma. 25 00:01:24,180 --> 00:01:24,935 Beth yw eich enw? 26 00:01:24,935 --> 00:01:25,768 >> CYNULLEIDFA: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 SIARADWR: Mary Beth, yn dod ar i fyny. 28 00:01:27,560 --> 00:01:29,560 Gadewch i mi gael y meicroffon yma i chi. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Neis i gwrdd â chi. 31 00:01:32,880 --> 00:01:34,005 >> CYNULLEIDFA: Neis i gwrdd â chi. 32 00:01:34,005 --> 00:01:36,790 SIARADWR: pob hawl, felly mae gen i yma llyfrau glas A drwy Z, 33 00:01:36,790 --> 00:01:41,680 ac yr wyf i'n mynd i esgus bod Mae gen i un o'r myfyrwyr, 34 00:01:41,680 --> 00:01:45,770 ac maen nhw'n dod i mewn braidd ar hap ar ddiwedd bloc arholiad tair awr, 35 00:01:45,770 --> 00:01:49,400 felly maent yn dod i ben i fyny mewn rhai trefn lled-hap fel hyn. 36 00:01:49,400 --> 00:01:54,510 Nawr eich swydd mewn dim ond hyn o bryd yn mynd i be-- hyn mewn gwirionedd sut y maent yn ei gael 37 00:01:54,510 --> 00:01:56,820 troi i mewn ar ddiwedd y dosbarth, yn fwyaf tebygol. 38 00:01:56,820 --> 00:02:01,120 Mae eich swydd yn awr yn mynd i fod, yn eithaf yn syml, i ddidoli y llyfrau glas i ni 39 00:02:01,120 --> 00:02:05,220 o A trwy Z. 40 00:02:05,220 --> 00:02:08,400 >> CYNULLEIDFA: O, mae hyn yn mynd i gymryd am byth. 41 00:02:08,400 --> 00:02:13,747 >> SIARADWR: A byddwn yn gwylio wrth i chi wneud hyn, dim pwysau. 42 00:02:13,747 --> 00:02:15,330 CYNULLEIDFA: Na, dim pwysau neu unrhyw beth. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> SIARADWR: Ac am hwyl, gadewch i ni roi i fyny amserydd. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> CYNULLEIDFA: Felly o hwyl, yn gymaint o hwyl. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> SIARADWR: Yr wyf yn gallu dal y meic i chi. 49 00:02:38,574 --> 00:02:40,240 Mae pob hawl, rydym wedi dyblu yn unig ein cyflymder. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Felly, yn y cyfamser, gadewch i mi beri beth sydd mynd i fod y cwestiwn ar gyfer Mary Beth 52 00:02:49,060 --> 00:02:51,540 yn yr hyn y mae hi'n ei wneud, sut mae hi'n mynd ati i ddatrys hyn? 53 00:02:51,540 --> 00:02:54,040 Ac yn wir, ni allai fod gennych erioed wedi meddwl am rywbeth 54 00:02:54,040 --> 00:02:57,440 mor syml â phan fyddwch yn dewis i fyny 26 o lyfrau fel hyn, 55 00:02:57,440 --> 00:02:59,350 oes ganddynt naturiol yn gorchymyn iddynt. 56 00:02:59,350 --> 00:03:01,335 Beth yw'r broses yr ydych yn ei ddefnyddio? 57 00:03:01,335 --> 00:03:03,770 A yw'n deg ar hap yn unig casglu yr un cyntaf y byddwch yn gweld 58 00:03:03,770 --> 00:03:05,250 a'i roi yn ei le? 59 00:03:05,250 --> 00:03:09,680 A ydych yn symud eich dwylo yn gyntaf o gwmpas edrych am A wedyn chwilio am B? 60 00:03:09,680 --> 00:03:11,722 A ydych yn cymryd golwg ar y pâr ohonynt ochr yn ochr 61 00:03:11,722 --> 00:03:14,680 a dim ond dweud, arhoswch funud, mae hyn Nid yn iawn, ac yna'n cyfnewid y gorchymyn? 62 00:03:14,680 --> 00:03:16,960 Gwelsom eisoes ar ddydd Llun fod yna nifer o ffyrdd 63 00:03:16,960 --> 00:03:22,140 lle y gallwn wneud hyn, ac yn wir wrth i ni agosáu at ddiwedd yma, 64 00:03:22,140 --> 00:03:26,360 Byddwn yn cymryd sylw o bosibl o'r hyn a Mary Beth yn ei wneud. 65 00:03:26,360 --> 00:03:30,040 Mae gennym ychydig o pentyrrau mae'n ymddangos, a fwy un, tri rhai llai. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> CYNULLEIDFA: Rydw i'n eu archebu pan fyddaf yn dod o hyd dau lythyr 68 00:03:36,415 --> 00:03:39,540 fy mod yn gwybod yn gyda'i gilydd mewn dilyniant, Yr wyf yn rhoi at ei gilydd fel nad wyf yn ei wneud 69 00:03:39,540 --> 00:03:42,915 rhaid i chi boeni am gadw trac o res gyfan o lyfrau. 70 00:03:42,915 --> 00:03:45,706 'I' jyst, oh, A yn gyntaf, Mae gen i stac hwn yma. 71 00:03:45,706 --> 00:03:47,580 SIARADWR: Felly, bron fel o ddarnau pos sy'n 72 00:03:47,580 --> 00:03:49,860 yn cael y siâp cywir i yn cyd-fynd i fyny gyda'i gilydd. 73 00:03:49,860 --> 00:03:51,026 CYNULLEIDFA: 'N bert lawer, yeah. 74 00:03:51,026 --> 00:03:55,320 SIARADWR: OK, rhagorol. 75 00:03:55,320 --> 00:03:59,850 Ac yn awr pob un o'r rhain pentyrrau cael ei ddidoli yn ôl pob tebyg? 76 00:03:59,850 --> 00:04:00,990 >> CYNULLEIDFA: Yeah. 77 00:04:00,990 --> 00:04:09,900 >> SIARADWR: pob hawl, A drwy Z. All iawn, llongyfarchiadau, y gwnaethoch chi hynny. 78 00:04:09,900 --> 00:04:11,461 Mae gennych eich dewis. 79 00:04:11,461 --> 00:04:11,960 Glas? 80 00:04:11,960 --> 00:04:13,530 Mae pob hawl, diolch i chi am hynny. 81 00:04:13,530 --> 00:04:16,679 Felly Mary Beth wnaeth gynnig beth oedd ei dull gweithredu, 82 00:04:16,679 --> 00:04:19,720 ond yr hyn sy'n ddull arall sut yr ydych yn Gallai fynd ati i ddidoli pethau hyn? 83 00:04:19,720 --> 00:04:21,130 Beth fyddech chi wedi ei wneud? 84 00:04:21,130 --> 00:04:24,060 Byddai'r cofnod i guro wedi bod un munud a 50 eiliad neu lai, 85 00:04:24,060 --> 00:04:26,039 yn ogystal â'r rhai yr wyf yn anghofio i gyfrif. 86 00:04:26,039 --> 00:04:27,080 Beth fyddech chi wedi ei wneud? 87 00:04:27,080 --> 00:04:27,579 Yeah? 88 00:04:27,579 --> 00:04:28,735 CYNULLEIDFA: Cymerwch y pentwr. 89 00:04:28,735 --> 00:04:29,776 Dechrau o'r dechrau. 90 00:04:29,776 --> 00:04:32,284 Gwiriwch eich papurau. 91 00:04:32,284 --> 00:04:36,586 Ac os yw'r un uchaf yn uwch nag, efallai, y maent, 92 00:04:36,586 --> 00:04:38,980 mae'r un gwaelod yn uwch, ac yna eu newid. 93 00:04:38,980 --> 00:04:41,300 >> SIARADWR: Iawn, felly cychwyn ar y brig a'r gwaelod, 94 00:04:41,300 --> 00:04:43,716 ac yna gweithio eich ffordd o'r tu allan fel 'na, yn eu cyfnewid? 95 00:04:43,716 --> 00:04:46,580 Iawn, felly ychydig yn debyg mewn ysbryd i'r math swigen, 96 00:04:46,580 --> 00:04:49,160 ond dewis y eithafion Nid yw'r parau cyfagos. 97 00:04:49,160 --> 00:04:52,080 Ond y tymor byr ohono yw bod yna sicr bagad o ffyrdd gwahanol 98 00:04:52,080 --> 00:04:54,210 gallem wneud hyn, ac a dweud y gwir, yr wyf yn meddwl i chi fath o 99 00:04:54,210 --> 00:04:55,700 mabwysiadu ymagweddau cwpl, dde? 100 00:04:55,700 --> 00:05:00,567 Gwnaethoch fath o bedwar pentwr ddidoli, a Yna uno nhw at ei gilydd yn effeithiol. 101 00:05:00,567 --> 00:05:02,650 A dyna, mentraf ddweud, un arall dechneg yn gyfan gwbl. 102 00:05:02,650 --> 00:05:06,950 Doeddech chi ddim yn ei drin fel un pentwr mawr, chi rhannu'r broblem yn bedwar quads, 103 00:05:06,950 --> 00:05:09,820 os mynnwch, ac yna rhywsut Unodd nhw yn y diwedd. 104 00:05:09,820 --> 00:05:13,410 >> Felly, gadewch i ni ystyried, yn y pen draw, sut arall y gallwn wneud hyn. 105 00:05:13,410 --> 00:05:15,860 Rydym yn ffurfioli y syniad o swigen didoli tro diwethaf, 106 00:05:15,860 --> 00:05:18,780 a didoli swigen cofio yn algorithm yr ydym yn dychmygu 107 00:05:18,780 --> 00:05:22,640 gydag wyth o'ch cyd-ddisgyblion i fyny yma, ymddangos yn didoli ar hap ar y dechrau. 108 00:05:22,640 --> 00:05:26,110 Ac rydym Yna penderfynodd pairwise, os dwy elfen yn allan o drefn, 109 00:05:26,110 --> 00:05:26,950 yn syml yn eu cyfnewid. 110 00:05:26,950 --> 00:05:28,930 Felly pedwar a dau yn yn amlwg allan o drefn, 111 00:05:28,930 --> 00:05:31,080 felly y ddau cyd-ddisgyblion troi swyddi. 112 00:05:31,080 --> 00:05:35,390 Ac yna rydym yn ailadrodd gyda pedwar a chwech, Yna, chwech ac wyth, ar bob iteriad, 113 00:05:35,390 --> 00:05:36,980 symud i'r dde. 114 00:05:36,980 --> 00:05:42,590 >> Felly o ystyried, faint o pairwise wyth o bobl cymariaethau wnes i wrth gerdded o 115 00:05:42,590 --> 00:05:45,220 chwith i'r dde mewn un fersiwn o'r fath? 116 00:05:45,220 --> 00:05:48,410 Faint o gymariaethau? 117 00:05:48,410 --> 00:05:49,197 Saith, dde? 118 00:05:49,197 --> 00:05:51,405 Oherwydd os oes wyth bobl ond mae gennych y pâr 119 00:05:51,405 --> 00:05:53,880 nhw ac eich bod yn cadw i symud un hop ar y dde, 120 00:05:53,880 --> 00:05:56,060 nad ydych yn mynd i gael wyth cymariaethau oherwydd na allwch gymharu 121 00:05:56,060 --> 00:05:59,226 elfen yn erbyn ei hun, neu y byddai unig fod ddibwynt, felly mae gennych saith. 122 00:05:59,226 --> 00:06:01,290 Neu'n fwy cyffredinol, os mae gennym n bobl, rydym yn 123 00:06:01,290 --> 00:06:04,300 wneud minws n 1 cymariaethau gyda'r math swigen. 124 00:06:04,300 --> 00:06:08,150 >> Felly, gadewch i ni ystyried nawr pa mor dda neu swigen drwg fath mewn gwirionedd oedd, ac yn ceisio 125 00:06:08,150 --> 00:06:13,570 i roi geirfa ein hunain gyda sydd i algorithmau beirniadaeth fel hyn, 126 00:06:13,570 --> 00:06:14,430 ac yn fuan ein hunain. 127 00:06:14,430 --> 00:06:16,970 Felly, y pas cyntaf trwy didoli swigen, y tro cyntaf 128 00:06:16,970 --> 00:06:20,909 Cerddais o'r chwith i'r dde ar draws y llwyfan, cymerodd fi n minws 1 cymariaethau. 129 00:06:20,909 --> 00:06:22,950 Ac mae hynny'n mynd i fod fy uned o fesur, dde? 130 00:06:22,950 --> 00:06:26,170 Roeddwn yn fath o siarad a mynd am dro, braidd yn gyflym, braidd yn araf, 131 00:06:26,170 --> 00:06:29,300 felly cyfri fy nifer o eiliadau Nid yw dweud yn arbennig, 132 00:06:29,300 --> 00:06:32,260 ond yn cyfrif faint o gweithrediadau a wneuthum ar ddydd Llun, 133 00:06:32,260 --> 00:06:35,900 cymharu dau o bobl, sy'n teimlo'n fel uned neis o fesur. 134 00:06:35,900 --> 00:06:40,980 >> Felly minws n 1 gamau y tro cyntaf, ond wedyn yr hyn a ddigwyddodd ar ôl hynny? 135 00:06:40,980 --> 00:06:46,610 Beth yw'r un upside o un tocyn drwy restr fel arall heb eu didoli? 136 00:06:46,610 --> 00:06:49,840 Beth allwch chi ei ddweud wrthyf am yr elfen a oedd yr holl ffordd dros yno? 137 00:06:49,840 --> 00:06:51,300 Yeah? 138 00:06:51,300 --> 00:06:52,870 Dyna oedd yr elfen fwyaf, dde? 139 00:06:52,870 --> 00:06:55,710 Rhif wyth, er ei bod ddechrau yma, bob tro rwy'n 140 00:06:55,710 --> 00:06:57,860 cymharu ei herbyn cymydog, mae hi'n cadw 141 00:06:57,860 --> 00:07:00,480 byrlymu i fyny ar y dde ochr y rhestr. 142 00:07:00,480 --> 00:07:02,710 Ac yn wir, dyna lle yr algorithm yn cael ei enw. 143 00:07:02,710 --> 00:07:07,630 >> Yn awr gan hynny rhesymeg, faint o gymariaethau mae angen imi eu gwneud ar yr ail dro 144 00:07:07,630 --> 00:07:09,800 Yr wyf yn gwneud y pas o'r chwith i'r dde? 145 00:07:09,800 --> 00:07:10,730 n minws 2, dde? 146 00:07:10,730 --> 00:07:14,297 Byddai 'I jyst yn gwastraffu fy amser os byddaf cadw cymharu wyth yn erbyn rhywun 147 00:07:14,297 --> 00:07:16,630 arall oherwydd ein bod eisoes yn gwybod ei bod yn y lle iawn. 148 00:07:16,630 --> 00:07:19,760 Felly dyna dipyn o optimeiddio, felly mae'r tocyn nesaf 149 00:07:19,760 --> 00:07:23,899 yn mynd i fod plws n minws ddau gam, lle mae n yw nifer y bobl. 150 00:07:23,899 --> 00:07:26,940 Nawr gallwch chi fath o allosod, hyd yn oed os nad ydych yn wyddonydd cyfrifiadurol, 151 00:07:26,940 --> 00:07:27,680 sut mae hyn yn dod i ben. 152 00:07:27,680 --> 00:07:31,259 Ar ddiwedd y algorithm hwn, yn ôl pob tebyg gennych dim ond un gymhariaeth chwith. 153 00:07:31,259 --> 00:07:33,800 Mae'n rhaid i chi fath o osod y gan ddechrau o'r rhestr rhag ofn dau 154 00:07:33,800 --> 00:07:36,540 ac un yn allan o drefn a dylai fod yn un a dau, 155 00:07:36,540 --> 00:07:40,330 felly mae hyn gwaelodion allan yn y ac 1 cymhariaeth terfynol. 156 00:07:40,330 --> 00:07:44,500 >> Nawr bod y dot, dot, dot math o donnau 'i' dwylo ar rai o'r manylion juicier, 157 00:07:44,500 --> 00:07:46,452 ond gadewch i ni jyst mynd yn ei flaen a symleiddio. 158 00:07:46,452 --> 00:07:48,660 Os cofiwch o uchel ysgol, a dweud y gwir, mae llawer ohonoch 159 00:07:48,660 --> 00:07:50,340 Roedd llyfrau mathemateg a oedd taflen twyllo ychydig 160 00:07:50,340 --> 00:07:52,550 ar y clawr blaen neu ar y clawr cefn a oedd yn dangos i chi 161 00:07:52,550 --> 00:07:56,400 pa gyfres crynodebau yn hoffi mae hyn yn y pen draw ychwanegu hyd at. 162 00:07:56,400 --> 00:07:59,600 Yn yr achos gyffredinol, os oes gennych amrywiol fel n, ac yn wir yr un yma, 163 00:07:59,600 --> 00:08:01,634 os ydych yn edrych ar eich Llyfr mathemateg hen ysgol, 164 00:08:01,634 --> 00:08:04,050 byddech yn gweld bod hyn yn mewn gwirionedd yn ychwanegu hyd at swm hwn yma, 165 00:08:04,050 --> 00:08:07,970 n amserau minws n 1 wedi'i rannu gyfan erbyn 2. 166 00:08:07,970 --> 00:08:11,172 Felly, am y tro, gadewch i mi jyst nodi mae hyn yn wir, y blaen naid o ffydd, 167 00:08:11,172 --> 00:08:12,880 dyna beth mae hyn yn crynhoi hyd at, a gallem 168 00:08:12,880 --> 00:08:14,341 brofi bod mewn achos mwy cyffredinol. 169 00:08:14,341 --> 00:08:15,590 Ond yn awr gadewch i ni ehangu hyn allan. 170 00:08:15,590 --> 00:08:19,920 Felly, gadewch i ni yn lluosi hyn allan, felly dyna n sgwâr, minws n, pob rannu â 2. 171 00:08:19,920 --> 00:08:23,200 Mae hynny'n wir yn sgwâr n, wedi'i rannu â 2, minws n dros 2, 172 00:08:23,200 --> 00:08:25,010 felly dyna i gyd 'n glws a diddorol. 173 00:08:25,010 --> 00:08:27,060 Ond beth sy'n digwydd os ydym yn Erbyn hyn plug-in werth? 174 00:08:27,060 --> 00:08:29,724 Tybiwch Nid oedd gan wyth wyf bobl, ond yn dweud miliwn. 175 00:08:29,724 --> 00:08:31,890 A miliwn dim ond oherwydd mae'n nifer eithaf mawr, 176 00:08:31,890 --> 00:08:34,039 gadewch i dopio bod i mewn a gweld beth sy'n digwydd. 177 00:08:34,039 --> 00:08:39,039 Felly, os wyf yn plwg miliwn i mewn i'r fformiwla Rydw i'n mynd i gael miliwn sgwâr, 178 00:08:39,039 --> 00:08:42,868 wedi'i rannu â 2, minws a miliwn, wedi'i rannu â 2. 179 00:08:42,868 --> 00:08:44,159 Yn awr beth sy'n mynd i fod yn gyfartal? 180 00:08:44,159 --> 00:08:47,354 Felly 500,000,000,000, minws 500,000. 181 00:08:47,354 --> 00:08:49,270 Ac os wyf yn ei wneud mewn gwirionedd y cwestiwn allan, mae hynny'n ei olygu 182 00:08:49,270 --> 00:08:53,920 bod didoli miliwn pobl sydd â'r math swigen 183 00:08:53,920 --> 00:09:01,800 Gallai mynd â fi 499,999,500,000 grisiau neu gymariaethau yn y diwedd, 184 00:09:01,800 --> 00:09:02,900 ni jyst yn allosod. 185 00:09:02,900 --> 00:09:06,860 >> Sy'n teimlo'n eithaf araf, ond dweud y gwir un mesur mewnbwn penodol 186 00:09:06,860 --> 00:09:09,160 fel hyn, nid yw pob dweud hynny. 187 00:09:09,160 --> 00:09:14,050 Ond yn wir, mae'n awgrymu bod yn n mynd yn fwy ac yn fwy, algorithm hwn 188 00:09:14,050 --> 00:09:16,280 math o teimlo'n waeth ac yn waeth, neu os ydych yn wir yn 189 00:09:16,280 --> 00:09:20,450 dechrau teimlo'r boen o hynny exponentiation, hynny n sgwario, 190 00:09:20,450 --> 00:09:21,770 sy'n ychwanegu i fyny 'n bert gyflym. 191 00:09:21,770 --> 00:09:25,340 Ac nid yw manylion hyn yn colli ar bobl, mewn gwirionedd 192 00:09:25,340 --> 00:09:29,640 rai blynyddoedd yn ôl seneddwr penodol a oedd ymgyrchu, eistedd i lawr am gyfweliad 193 00:09:29,640 --> 00:09:32,180 gyda Google Eric Schmidt, Prif Swyddog Gweithredol ar y pryd, 194 00:09:32,180 --> 00:09:36,380 ac yn ei herio gyda chwestiwn yn debyg ein bod yn archwilio heddiw. 195 00:09:36,380 --> 00:09:38,468 Gadewch i ni edrych. 196 00:09:38,468 --> 00:09:45,280 >> [VIDEO Playback] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Byddwch yma yn Google, ac yr wyf yn hoffi 198 00:09:48,560 --> 00:09:53,382 i feddwl am y llywyddiaeth fel cyfweliad am swydd. 199 00:09:53,382 --> 00:09:56,434 Yn awr, mae'n anodd i gael swydd fel llywydd, 200 00:09:56,434 --> 00:09:58,100 a ydych yn mynd trwy'r llymder yn awr. 201 00:09:58,100 --> 00:10:01,860 Mae hefyd yn anodd i gael swydd yn Google. 202 00:10:01,860 --> 00:10:05,490 Mae gennym gwestiynau, ac yr ydym gofyn i'n cwestiynau i ymgeiswyr, 203 00:10:05,490 --> 00:10:09,770 ac mae hyn yn un yn dod o Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 What-- chi guys yn meddwl fy mod kidding, 'i' iawn yma. 205 00:10:14,760 --> 00:10:17,930 Beth yw'r ffordd fwyaf effeithlon i didoli miliwn o gyfanrifau 32-bit? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> -I'm Ddrwg gennym, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> -Dim, Na, na. 210 00:10:27,400 --> 00:10:30,700 Rwy'n meddwl bod y math swigen fyddai'r ffordd anghywir i fynd. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> -Come Ar, a ddywedodd wrtho hyn? 213 00:10:38,180 --> 00:10:40,590 Doeddwn i ddim yn gweld cyfrifiadur gwyddoniaeth yn eich cefndir. 214 00:10:40,590 --> 00:10:42,130 >> -We've Cael ein ysbiwyr i mewn 'na. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Gadewch i ni ofyn i wahanol cwestiwn cyfweliad. 217 00:10:48,444 --> 00:10:49,300 >> [DIWEDD Playback VIDEO] 218 00:10:49,300 --> 00:10:52,290 >> SIARADWR: Felly, yn siarad am rhifau penodol, fodd bynnag, 219 00:10:52,290 --> 00:10:53,890 Nid yn mynd i fod bob un sy'n ddefnyddiol. 220 00:10:53,890 --> 00:10:56,810 Nid yw'n gwers bywyd y swigen didoli, o ystyried miliwn mewnbynnau, 221 00:10:56,810 --> 00:10:58,590 Gallai cymryd cymaint â 500,000,000,000 grisiau. 222 00:10:58,590 --> 00:11:01,120 Ni allwch wir yn gyffredinoli rhy effeithiol o hynny 223 00:11:01,120 --> 00:11:03,560 a gwneud penderfyniadau dylunio da wrth ysgrifennu rhaglenni. 224 00:11:03,560 --> 00:11:07,070 Felly gadewch i ni ganolbwyntio er ar sut efallai y byddwn yn symleiddio'r canlyniad hwn. 225 00:11:07,070 --> 00:11:11,780 >> Felly dwi wedi hamlygu mewn melyn yma ganlyniad n sgwâr rhannu â 2, 226 00:11:11,780 --> 00:11:14,330 felly i filiwn sgwario wedi'i rannu â 2, ac yna 227 00:11:14,330 --> 00:11:16,710 Rwyf wedi tynnu sylw at yr hyn yr ateb yn y pen draw yn 228 00:11:16,710 --> 00:11:20,180 ar ôl i ni dynnu i ffwrdd wedi'i rannu n erbyn 2. 229 00:11:20,180 --> 00:11:24,850 A'r hawliad Rydw i'n mynd i wneud yn awr yw, pwy mae'r Heck gofalu os ydych yn tynnu i ffwrdd 230 00:11:24,850 --> 00:11:30,060 ychydig yn hen n dros 2 pan fydd y cyntaf rhan o'r fformiwla hwn mor llawer mwy? 231 00:11:30,060 --> 00:11:33,910 Mae'n dominyddu y llall dymor, n sgwario wedi'i rannu â 2 232 00:11:33,910 --> 00:11:37,510 mor llawer mwy, yn amlwg, fel y n yn cael fawr fel miliwn, 233 00:11:37,510 --> 00:11:41,450 sydd yno mewn gwirionedd gwahaniaeth mawr yn diwedd y dydd rhwng 500,000,000,000 234 00:11:41,450 --> 00:11:45,730 a 499,999,500,000? 235 00:11:45,730 --> 00:11:46,349 Ddim mewn gwirionedd. 236 00:11:46,349 --> 00:11:48,640 Ac felly yr hyn rydym yn mynd i wneud fel gwyddonwyr cyfrifiadurol yn 237 00:11:48,640 --> 00:11:53,270 telerau anwybyddu gorchymyn is hynny a cymryd rhywbeth fel hyn ac yn wir 238 00:11:53,270 --> 00:11:56,050 jyst symleiddio i'r dymor sy'n mynd i mater. 239 00:11:56,050 --> 00:12:00,315 Y mwyaf fydd ein setiau data yn cael, y mwyaf fydd ein cronfeydd data yn cael, y tudalennau mwy gwe 240 00:12:00,315 --> 00:12:02,690 mae'n rhaid i ni chwilio, y mwyaf ffrindiau sydd gennych ar Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Wrth n mynd yn fwy, rydym yn wirioneddol mynd i ofalu am y mwyaf 242 00:12:07,340 --> 00:12:11,560 dymor mewn unrhyw ddadansoddiad o'r fath o ein perfformiad algorithmau. 243 00:12:11,560 --> 00:12:16,230 Ac yr wyf i'n mynd i ddweud, eich bod yn gwybod beth, didoli swigen ar y drefn O fawr, 244 00:12:16,230 --> 00:12:18,060 ar y drefn n sgwâr. 245 00:12:18,060 --> 00:12:20,090 Dyw hi ddim yn union n sgwario fel yr ydym wedi gweld, 246 00:12:20,090 --> 00:12:22,060 ond sydd yn poeni amdanynt am delerau llai hynny, 247 00:12:22,060 --> 00:12:24,390 a dweud y gwir, sydd wir gofalu os ydym yn ei rannu â 2? 248 00:12:24,390 --> 00:12:25,870 Dyna dim ond yn ffactor cyson. 249 00:12:25,870 --> 00:12:29,480 Ac mae'n 500,000,000,000 erbyn 250 biliwn iawn bod fawr o gytundeb? 250 00:12:29,480 --> 00:12:32,190 Gallai Fi jyst aros un flwyddyn, gadael i fy ngliniadur llythrennol 251 00:12:32,190 --> 00:12:34,810 mynd ddwywaith mor gyflym mewn caledwedd, a'r math yna o wahaniaeth 252 00:12:34,810 --> 00:12:36,650 yn unig yn mynd i ffwrdd yn naturiol dros amser. 253 00:12:36,650 --> 00:12:39,300 >> Yr hyn yr ydym yn gofalu amdano yw yr ymadrodd, mae'r rhan 254 00:12:39,300 --> 00:12:42,489 o'r mynegiad sy'n mynd i amrywio fel ein mewnbwn yn mynd yn fwy ac yn fwy. 255 00:12:42,489 --> 00:12:45,280 Ac yn wir, yn y byd go iawn, dyna beth sy'n digwydd yn gynyddol 256 00:12:45,280 --> 00:12:48,330 yw'r mewnbynnau i'n problemau a algorithmau yn mynd yn fwy. 257 00:12:48,330 --> 00:12:53,470 Felly O mawr yn mynd i fod y nodiant, y nodiant asymptotic, yr ydym newydd ei 258 00:12:53,470 --> 00:12:57,160 defnyddio fel gwyddonwyr cyfrifiadurol i ddisgrifio y perfformiad, neu yr amser yn rhedeg, 259 00:12:57,160 --> 00:12:58,130 o'r algorithm. 260 00:12:58,130 --> 00:13:00,800 Er mwyn i ni allu cymharu algorithmau ar wahanol gyfrifiaduron ysgrifenedig 261 00:13:00,800 --> 00:13:04,170 gan wahanol bobl, trwy ddefnyddio rhywfaint o metrig yn sylfaenol debyg 262 00:13:04,170 --> 00:13:07,557 fel y nifer o gymariaethau ydych yn gwneud, neu efallai y nifer o gyfnewidiadau 263 00:13:07,557 --> 00:13:08,140 eich bod yn gwneud. 264 00:13:08,140 --> 00:13:11,910 >> Yr hyn nad ydym yn mynd i cyfrif yw faint o amser 265 00:13:11,910 --> 00:13:13,981 sy'n mynd ar y cloc ar y wal fel arfer. 266 00:13:13,981 --> 00:13:16,230 Yr hyn nad ydym yn mynd i boeni amdano yw faint o gof 267 00:13:16,230 --> 00:13:17,820 ydych chi'n defnyddio heddiw yn lleiaf, er bod hynny'n 268 00:13:17,820 --> 00:13:19,370 adnodd arall efallai y byddwn yn mesur. 269 00:13:19,370 --> 00:13:23,610 Rydym yn mynd i geisio seilio ein dadansoddiadau ar ddim ond y gweithrediadau sylfaenol, y rhai, 270 00:13:23,610 --> 00:13:25,930 a dweud y gwir, y gallwch ei weld fwyaf ar eu golwg. 271 00:13:25,930 --> 00:13:30,700 Felly, gyda rhywbeth fel O mawr o n sgwâr, yr wyf yn honni bod O o n squared 272 00:13:30,700 --> 00:13:35,820 yw yn rhwym uchaf ar y hyn a elwir yn rhedeg amser o'r math swigen. 273 00:13:35,820 --> 00:13:38,820 Mewn geiriau eraill, os ydych yn eisiau honni bod yna 274 00:13:38,820 --> 00:13:41,370 y terfyn uchaf ar faint o camau y gallai algorithm cymryd, 275 00:13:41,370 --> 00:13:46,240 mae'n mynd i fod yn y O fawr o n sgwâr yn yr achos hwn, yn uchaf rhwymo. 276 00:13:46,240 --> 00:13:49,710 >> Beth os byddaf yn lle hynny yn newid y stori i fod nid am fath swigen, 277 00:13:49,710 --> 00:13:50,910 ond am hyn rhwymo uchaf. 278 00:13:50,910 --> 00:13:54,030 Allwch chi feddwl am algorithm ein bod wedi edrych ar yn barod 279 00:13:54,030 --> 00:13:59,530 y mae ei uchaf rhwymo, uchafswm mesur o amser neu weithrediadau, 280 00:13:59,530 --> 00:14:04,300 Byddai fod yn dweud i gael ei ffinio gan n, swyddogaeth llinol, 281 00:14:04,300 --> 00:14:07,260 nid yn un cwadratig sy'n crwm? 282 00:14:07,260 --> 00:14:10,780 Beth yw algorithm sy'n bob amser yn cymryd dim mwy 283 00:14:10,780 --> 00:14:12,860 nag fel grisiau n, neu Camau 2n, neu gamau 3n? 284 00:14:12,860 --> 00:14:13,360 Yeah? 285 00:14:13,360 --> 00:14:15,030 >> CYNULLEIDFA: Dod o hyd i'r nifer mwyaf mewn rhestr? 286 00:14:15,030 --> 00:14:16,930 >> SIARADWR: Perffaith, dod o hyd i y nifer mwyaf mewn rhestr. 287 00:14:16,930 --> 00:14:18,940 Os ydw i'n cael rhestr o pobl er enghraifft, 288 00:14:18,940 --> 00:14:21,440 pob un sydd yn cynnal nifer, beth yw'r nifer fwyaf 289 00:14:21,440 --> 00:14:23,770 o'r camau y dylid ei gymryd i mi, person rhesymol smart, 290 00:14:23,770 --> 00:14:27,530 i ddod o hyd i'r person mwyaf yn y rhestr honno? 291 00:14:27,530 --> 00:14:28,100 n, dde? 292 00:14:28,100 --> 00:14:31,320 Oherwydd yn yr achos gwaethaf, lle efallai y bydd y gwerth mwyaf fod? 293 00:14:31,320 --> 00:14:32,700 Iawn, yr holl ffordd ar y diwedd. 294 00:14:32,700 --> 00:14:34,575 Felly, yn yr achos gwaethaf uchaf rhwymo, yr wyf efallai 295 00:14:34,575 --> 00:14:36,450 rhaid i chi fynd yr holl ffordd dros yma ac yn cael ei hoffi, 296 00:14:36,450 --> 00:14:39,170 oh, dyma rhif wyth, neu beth bynnag y gwerth. 297 00:14:39,170 --> 00:14:41,330 Nawr byddai'n jyst yn dwp os wyf yn cadw fynd, dde? 298 00:14:41,330 --> 00:14:43,840 Chwilio am fwy a mwy o elfennau os yr olaf ohonynt yw dros yno? 299 00:14:43,840 --> 00:14:45,340 Felly yn sicr, n yn uwch yn rhwymo. 300 00:14:45,340 --> 00:14:47,420 Nid oes angen i mi gymryd mwy o gamau na hynny. 301 00:14:47,420 --> 00:14:51,580 >> Felly beth os yn lle hynny yr wyf yn cynnig bod mae algorithmau yn y byd hwn sy'n 302 00:14:51,580 --> 00:14:57,750 cael amser rhedeg dyna ffinio gan O fawr o log n, mewngofnodwch n? 303 00:14:57,750 --> 00:15:00,390 Ble yr ydym wedi gweld hyn o'r blaen? 304 00:15:00,390 --> 00:15:00,890 Yeah? 305 00:15:00,890 --> 00:15:03,309 >> CYNULLEIDFA: Yn y broblem llyfr ffôn? 306 00:15:03,309 --> 00:15:04,850 SIARADWR: Fel y broblem llyfr ffôn. 307 00:15:04,850 --> 00:15:07,754 Beth oedd y mesur o ba mor llawer o amser neu faint o ddagrau y mae'n 308 00:15:07,754 --> 00:15:10,170 cymerodd fi i ddod o hyd i rywun fel Mike Smith yn y llyfr ffôn? 309 00:15:10,170 --> 00:15:13,212 Rydym yn honni ei fod yn log n, ac hyd yn oed os yw'n anghyfarwydd, neu ei fod yn 310 00:15:13,212 --> 00:15:15,170 ychydig yn niwlog beth yw logarithm neu ddehonglwr oedd, 311 00:15:15,170 --> 00:15:17,650 dim ond cofiwch y log n yn gyffredinol yn cyfeirio at y broses, 312 00:15:17,650 --> 00:15:20,790 yn yr achos hwn, o rannu rhywbeth yn ei hanner eto, ac unwaith eto, 313 00:15:20,790 --> 00:15:25,790 ac unwaith eto, ac unwaith eto, fel ei fod yn mynd yn fwyfwy bach wrth i chi wneud hynny. 314 00:15:25,790 --> 00:15:28,470 >> Felly log o n yn cyfeirio, yn sicr, at yr enghraifft llyfr ffôn, 315 00:15:28,470 --> 00:15:32,662 i chwilio deuaidd mewn theori, pan fyddwn yn Roedd y drysau rhithwir ar y bwrdd, 316 00:15:32,662 --> 00:15:34,370 neu pan oedd Sean chwilio am rywbeth. 317 00:15:34,370 --> 00:15:37,374 Pe bai wedi defnyddio chwiliad deuaidd, mewngofnodwch n fyddai uchaf rhwymo ar faint 318 00:15:37,374 --> 00:15:38,040 amser sy'n cymryd. 319 00:15:38,040 --> 00:15:44,027 Ond algorithmau rhai a oedd yn rhedeg yn log n cymryd yn ganiataol pa manylion allweddol? 320 00:15:44,027 --> 00:15:45,360 Bod y rhestr ei datrys, dde? 321 00:15:45,360 --> 00:15:47,789 Mae eich algorithm yn anghywir os nad yw eich cyfraniad yn cael ei ddidoli, 322 00:15:47,789 --> 00:15:49,830 ac eto yr ydych yn ei ddefnyddio rhywbeth fel chwiliad deuaidd 323 00:15:49,830 --> 00:15:51,704 oherwydd efallai y byddwch yn neidio i'r dde dros yr elfen 324 00:15:51,704 --> 00:15:53,600 heb sylweddoli ei fod yn wir yno. 325 00:15:53,600 --> 00:15:55,600 >> Yn awr beth allai hyn ei olygu, O fawr o un? 326 00:15:55,600 --> 00:15:59,117 Nid yw hyn yn golygu bod eich algorithm yn cymryd un a dim ond un cam, 327 00:15:59,117 --> 00:16:01,200 'i jyst yn golygu ei bod yn cymryd nifer cyson o gamau. 328 00:16:01,200 --> 00:16:04,060 Efallai ei fod yn 1, efallai ei bod yn 10, efallai ei bod yn 1,000, 329 00:16:04,060 --> 00:16:07,750 ond mae'n annibynnol ar maint y broblem. 330 00:16:07,750 --> 00:16:10,850 Ni waeth pa mor fawr yw n, algorithm amser cyson 331 00:16:10,850 --> 00:16:12,747 bob amser yn cymryd yr un nifer o gamau. 332 00:16:12,747 --> 00:16:15,080 Felly, yr hyn a allai fod yn algorithm rydym wedi trafod neu dim ond 333 00:16:15,080 --> 00:16:20,418 reddfol sy'n dod i chi fod bob amser yn rhedeg yn hyn a elwir yn amser yn gyson? 334 00:16:20,418 --> 00:16:20,918 Yeah? 335 00:16:20,918 --> 00:16:22,001 >> CYNULLEIDFA: Ychwanegu dau rif. 336 00:16:22,001 --> 00:16:25,320 SIARADWR: Ychwanegwch ddau rif, 2 a 2 yn dychwelyd 4, wneud. 337 00:16:25,320 --> 00:16:27,227 Felly, a allai weithio, beth arall? 338 00:16:27,227 --> 00:16:28,560 Beth am y byd yn fwy real, ie? 339 00:16:28,560 --> 00:16:30,686 >> CYNULLEIDFA: Dod o hyd i'r peth cyntaf mewn rhestr. 340 00:16:30,686 --> 00:16:32,810 SIARADWR: Dod o hyd i'r cyntaf elfen mewn rhestr, yn sicr. 341 00:16:32,810 --> 00:16:34,540 Rydym wedi bod yn siarad mewn gwirionedd am araeau eisoes, 342 00:16:34,540 --> 00:16:36,540 sut yr ydych yn ei gael yn y elfen gyntaf mewn arae, 343 00:16:36,540 --> 00:16:40,465 ni waeth pa mor hir y mae'r amrywiaeth mewn cod C? 344 00:16:40,465 --> 00:16:43,090 Yr ydych newydd ei ddefnyddio fel y braced sero nodiant, bam, rydych chi yno. 345 00:16:43,090 --> 00:16:46,120 Ac yn wir araeau, wrth fynd heibio, cefnogi rhywbeth a elwir yn gyffredinol 346 00:16:46,120 --> 00:16:49,240 fel mynediad ar hap, mynediad ar hap cof, oherwydd gallwch llythrennol 347 00:16:49,240 --> 00:16:50,284 neidio i unrhyw un lle. 348 00:16:50,284 --> 00:16:52,700 Gallwn wneud hyn hyd yn oed yn fwy syml gallwn ni ailddirwyn i wythnos sero 349 00:16:52,700 --> 00:16:53,900 pan wnaethom Scratch. 350 00:16:53,900 --> 00:16:59,707 Faint o amser gymerodd hi i'r ddweud bloc yn Scratch i weithredu? 351 00:16:59,707 --> 00:17:00,790 Dim ond amser yn gyson, dde? 352 00:17:00,790 --> 00:17:03,960 Dweud rhywbeth, yn dweud rhywbeth, nid oes gwahaniaeth 353 00:17:03,960 --> 00:17:07,359 sut Crafiadau mawr y byd yw, mae bob amser mynd i gymryd yr un faint o amser 354 00:17:07,359 --> 00:17:08,490 i wneud dim ond dweud rhywbeth. 355 00:17:08,490 --> 00:17:11,089 >> Felly dyna amser cyson, ond beth yw'r ochr arall? 356 00:17:11,089 --> 00:17:13,030 Os oedd hynny'n uchaf ffiniau, beth os ydym am 357 00:17:13,030 --> 00:17:17,089 i ddisgrifio'r arffiniau isaf o'n algorithmau amser yn rhedeg? 358 00:17:17,089 --> 00:17:19,852 Mae bron i achos gorau o bosibl, os mynnwch, 359 00:17:19,852 --> 00:17:23,060 er y gallai telerau hyn yn berthnasol i gorau achosion, achosion gwaethaf, achosion gyfartaledd yn fwy 360 00:17:23,060 --> 00:17:26,359 yn gyffredinol, ond gadewch i ni dim ond yn canolbwyntio ar arffiniau isaf yn fwy cyffredinol. 361 00:17:26,359 --> 00:17:31,920 Beth yw algorithm sydd wedi mae is rhwymo o gamau n, 362 00:17:31,920 --> 00:17:33,350 neu gamau 2n, neu gamau 3n? 363 00:17:33,350 --> 00:17:36,241 Rhyw ffactor o risiau n, dyna ei is rhwymo. 364 00:17:36,241 --> 00:17:36,740 Yeah? 365 00:17:36,740 --> 00:17:37,910 >> CYNULLEIDFA: didoli Bubble? 366 00:17:37,910 --> 00:17:41,610 >> SIARADWR: didoli Bubble cymryd chi grisiau n leiaf, pam? 367 00:17:41,610 --> 00:17:42,279 Pam hynny? 368 00:17:42,279 --> 00:17:45,320 Pam y dylai y dechrau i ddod i chi reddfol, dim hyd yn oed os bydd yn gwneud dim ond 369 00:17:45,320 --> 00:17:46,530 eto? 370 00:17:46,530 --> 00:17:47,030 Yeah? 371 00:17:47,030 --> 00:17:47,990 >> CYNULLEIDFA: [Anghlywadwy]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 SIARADWR: Yn union. 374 00:17:52,360 --> 00:17:55,810 Yn y senario gorau posibl o didoli swigen, ac mae llawer o algorithmau, 375 00:17:55,810 --> 00:17:58,769 os wyf yn llaw ydych wyth o bobl sydd eisoes yn cael eu datrys, 376 00:17:58,769 --> 00:18:00,560 byddai'n ffôl i chi, y algorithm, 377 00:18:00,560 --> 00:18:02,202 i fynd yn ôl ac ymlaen fwy nag unwaith, dde? 378 00:18:02,202 --> 00:18:04,285 Oherwydd cyn gynted ag y byddwch yn cerdded drwy'r rhestr unwaith, 379 00:18:04,285 --> 00:18:08,090 dylech sylweddoli, oh, yr wyf yn gwneud unrhyw cyfnewidiadau, y rhestr hon yn cael ei datrys, allanfa. 380 00:18:08,090 --> 00:18:09,700 Ond mae hynny'n mynd i fynd â chi n grisiau. 381 00:18:09,700 --> 00:18:12,033 >> Ac i'r gwrthwyneb, beth arall ffordd o feddwl am y peth? 382 00:18:12,033 --> 00:18:15,240 Fath swigen yn omega, fel petai, o n, 383 00:18:15,240 --> 00:18:19,050 oherwydd os edrychwch ar llai na n elfen, beth 384 00:18:19,050 --> 00:18:23,009 yw'r mater sylfaenol yno? 385 00:18:23,009 --> 00:18:24,550 Nid ydych yn gwybod os yw'n cael ei datrys, ar y dde. 386 00:18:24,550 --> 00:18:26,800 Rydym bodau dynol cipolwg nerth mewn wyth bobl ac yn cael ei hoffi, oh, mae'n cael ei datrys, 387 00:18:26,800 --> 00:18:28,430 nad oedd yn mynd â fi n grisiau, ond yr oedd. 388 00:18:28,430 --> 00:18:30,810 Eich llygaid, er eich math o mae ganddynt faes mawr o weledigaeth, 389 00:18:30,810 --> 00:18:33,184 chi edrych ar wyth elfen, chi edrych ar wyth o bobl, 390 00:18:33,184 --> 00:18:34,610 dyna wyth cam yn effeithiol. 391 00:18:34,610 --> 00:18:38,612 A dim ond os ydw i'n cerdded drwy'r cyfan rhestr ydw i'n sylweddoli, ie, didoli. 392 00:18:38,612 --> 00:18:41,320 Os byddaf yn rhoi'r gorau i hanner ffordd i feddwl, i gyd iawn, mae'n eithaf didoli hyd yn hyn, 393 00:18:41,320 --> 00:18:42,520 beth yw'r groes nid yw'n cael ei datrys? 394 00:18:42,520 --> 00:18:44,186 Nid yw algorithmau mynd i fod yn gywir. 395 00:18:44,186 --> 00:18:46,250 A allai fod yn gyflymach, ond yn anghywir. 396 00:18:46,250 --> 00:18:48,500 >> Felly nawr mae gennym ffordd o disgrifio is terfynau, 397 00:18:48,500 --> 00:18:49,710 a beth am amser yn gyson? 398 00:18:49,710 --> 00:18:54,565 Beth yw algorithm sydd â llai rhwymo ar ei amser yn rhedeg o un? 399 00:18:54,565 --> 00:18:58,350 Cam 1, 2 cam, 10 cam, ond gyson, yn annibynnol ar n, 400 00:18:58,350 --> 00:18:59,310 maint y mewnbwn? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Yeah, yn y cefn. 403 00:19:04,600 --> 00:19:05,309 >> CYNULLEIDFA: printf? 404 00:19:05,309 --> 00:19:06,183 SIARADWR: Beth sy'n bod? 405 00:19:06,183 --> 00:19:07,184 CYNULLEIDFA: printf? 406 00:19:07,184 --> 00:19:07,850 SIARADWR: printf. 407 00:19:07,850 --> 00:19:08,400 OK, yn sicr. 408 00:19:08,400 --> 00:19:10,720 Felly, mae'n cymryd nifer penodol o gamau. 409 00:19:10,720 --> 00:19:13,170 A ddylwn i now-- nawr bod rydym yn sôn am cod C 410 00:19:13,170 --> 00:19:16,040 ac nid Scratch, rhywbeth fel dweud, gyda printf, 411 00:19:16,040 --> 00:19:17,710 dylem ddechrau i fynd yn ofalus. 412 00:19:17,710 --> 00:19:21,090 Oherwydd bod printf yn cymryd mewnbwn, mae'n llinyn, 413 00:19:21,090 --> 00:19:23,220 a llinynnau dechnegol oes ganddynt hyd. 414 00:19:23,220 --> 00:19:25,530 Felly os ydym yn awr yn awyddus i godi arnoch chi, os nad oes gwahaniaeth gennych, 415 00:19:25,530 --> 00:19:29,430 dechnegol gallem ddadlau bod printf yn cymryd mewnbwn hyd newidiol, 416 00:19:29,430 --> 00:19:32,270 ac yn sicr gallai gymryd mwy amser i argraffu llinyn hwn yn hir, 417 00:19:32,270 --> 00:19:33,560 na hyn hir. 418 00:19:33,560 --> 00:19:36,570 >> Felly beth os ydym yn ystyried dim ond y didoli a chwilio enghreifftiau? 419 00:19:36,570 --> 00:19:40,450 Beth am Mike Smith yn y ffôn lyfr, neu chwiliad deuaidd yn fwy cyffredinol? 420 00:19:40,450 --> 00:19:42,220 Yn yr achos gorau, beth allai ddigwydd? 421 00:19:42,220 --> 00:19:45,577 Yr wyf yn agor y llyfr ffôn ac, bam, mae rhif Mike Smith. 422 00:19:45,577 --> 00:19:46,660 Gallaf ei alw ef yn syth. 423 00:19:46,660 --> 00:19:49,390 >> Cymerodd un cam, efallai dau gam, ond mae nifer cyson o gamau 424 00:19:49,390 --> 00:19:50,230 os wyf got 'n ffodus. 425 00:19:50,230 --> 00:19:52,570 Ac yn dweud y gwir, gwelsom ar Dydd Llun eich classmate 426 00:19:52,570 --> 00:19:54,710 gael yn eithaf lwcus ddwywaith yn olynol. 427 00:19:54,710 --> 00:19:57,050 A dyna oedd yn wir gyson amser mewn is terfynau 428 00:19:57,050 --> 00:20:01,280 ar y algorithm dan sylw ar gyfer dod o hyd i y rhif 50 y tu ôl y rhai ar gau 429 00:20:01,280 --> 00:20:01,830 drysau. 430 00:20:01,830 --> 00:20:06,400 >> Yn awr, wrth fynd heibio, os byddwch yn darganfod bod y ddau O fawr, mae'r rhwymo uchaf, 431 00:20:06,400 --> 00:20:09,310 ac omega, yr isaf rhwymo, yn un yn yr un, bod 432 00:20:09,310 --> 00:20:11,830 yr un fformiwla yn cromfachau, gallwch hefyd 433 00:20:11,830 --> 00:20:15,170 yn dweud, dim ond i fod yn ffansi, bod rhywbeth yn theta 434 00:20:15,170 --> 00:20:18,270 o n neu theta o ryw werth arall. 435 00:20:18,270 --> 00:20:20,661 Mae hynny yn unig yn golygu pan fydd fawr O a omega yr un fath. 436 00:20:20,661 --> 00:20:21,910 Nawr beth am fath dethol? 437 00:20:21,910 --> 00:20:23,400 Gadewch i ni ddefnyddio hyn geirfa newydd. 438 00:20:23,400 --> 00:20:27,407 Yn y math dethol, beth oedd yr ydym wneud eto, ac unwaith eto, ac unwaith eto? 439 00:20:27,407 --> 00:20:29,990 Yr oeddwn yn mynd yn ôl ac ymlaen trwy y rhestr, yn chwilio am bwy? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Y nifer lleiaf. 442 00:20:34,730 --> 00:20:37,560 >> Felly faint o gamau, sut llawer o gymariaethau wnes i 443 00:20:37,560 --> 00:20:43,250 rhaid iddynt eu gwneud er mwyn chyfrif i maes pwy yr elfen lleiaf yn y rhestr oedd? 444 00:20:43,250 --> 00:20:44,437 n minws 1, dde? 445 00:20:44,437 --> 00:20:47,770 Oherwydd os Fi jyst ddechrau gyda'r un rwy'n roddwyd a byddaf yn dechrau cymharu ef neu hi, 446 00:20:47,770 --> 00:20:49,519 Yna, ef neu hi, ef neu hi, ef neu hi, yr wyf yn 447 00:20:49,519 --> 00:20:52,010 dim ond paru elfennau ynghyd n minws 1 o weithiau. 448 00:20:52,010 --> 00:20:55,630 Felly detholiad didoli un modd yn cymryd n minws 1 gamau y tro cyntaf. 449 00:20:55,630 --> 00:20:59,540 >> Faint o gamau y mae'n cymryd i mi ddod o hyd i'r elfen ail leiaf? 450 00:20:59,540 --> 00:21:02,920 n minws 2, oherwydd fy mod i'n bod yn fud os Rwy'n cadw edrych ar yr un bobl 451 00:21:02,920 --> 00:21:06,280 eto os wyf eisoes wedi dewis iddo neu hi ac yn eu rhoi yn eu lle. 452 00:21:06,280 --> 00:21:09,270 A'r trydydd cam, n minws 3, yna minws n 4. 453 00:21:09,270 --> 00:21:11,020 Rydym wedi gweld y patrwm hwn o'r blaen, ac yn wir 454 00:21:11,020 --> 00:21:13,460 detholiad didoli yn yr un modd Mae gan uchaf rhwymo 455 00:21:13,460 --> 00:21:16,210 o n sgwâr os ydym yn ei wneud i fyny y Crynodeb. 456 00:21:16,210 --> 00:21:19,790 Beth yw ei, didoli dewis is rhwymo? 457 00:21:19,790 --> 00:21:25,350 Cyn lleied â phosibl, faint o amser dethol rhaid didoli cymryd, wrth i ni ddiffinio ar ddydd Llun? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Cynnig ddau opsiwn. 460 00:21:30,490 --> 00:21:32,360 Efallai ei bod yn n, fel o'r blaen. 461 00:21:32,360 --> 00:21:35,040 Efallai ei fod yn n sgwâr, gan ei fod yn yn awr gan fod y rhwymo uchaf. 462 00:21:35,040 --> 00:21:35,874 >> CYNULLEIDFA: n sgwâr. 463 00:21:35,874 --> 00:21:36,664 SIARADWR: n sgwâr. 464 00:21:36,664 --> 00:21:37,368 Pam? 465 00:21:37,368 --> 00:21:40,060 >> CYNULLEIDFA: Oherwydd bod gennych i ddiffinio [Anghlywadwy]. 466 00:21:40,060 --> 00:21:41,510 >> SIARADWR: Yn union. 467 00:21:41,510 --> 00:21:45,077 O leiaf gan fy mod diffinnir fath dethol roedd yn eithaf naïf, ddal ati, 468 00:21:45,077 --> 00:21:46,160 ddod o hyd i'r elfen lleiaf. 469 00:21:46,160 --> 00:21:47,770 Ewch eto, dod o hyd i'r elfen lleiaf. 470 00:21:47,770 --> 00:21:49,490 Ewch eto, dod o hyd i'r elfen lleiaf. 471 00:21:49,490 --> 00:21:51,700 Does dim fath o optimization yno fod 472 00:21:51,700 --> 00:21:54,350 Efallai gadewch i mi erthylu ar ôl camau yn unig n neu hynny. 473 00:21:54,350 --> 00:21:57,080 Felly yn wir, dewis didoli, omega o n sgwâr. 474 00:21:57,080 --> 00:22:00,667 >> Beth am fath mewnosod, lle yr wyf yn cymryd pwy a roddwyd i mi, ac yna yr wyf plopped ef 475 00:22:00,667 --> 00:22:01,750 neu hi yn y lle iawn? 476 00:22:01,750 --> 00:22:04,958 Yna mi ymlaen at yr ail berson, plopped ef neu hi yn y lle iawn. 477 00:22:04,958 --> 00:22:07,910 Yna bydd y person nesaf, plopped ef neu hi yn y lle iawn. 478 00:22:07,910 --> 00:22:10,537 Sylwch fod hyn yn iawn llinol, fel petai. 479 00:22:10,537 --> 00:22:12,620 Rwy'n llinell syth, rwy'n ddim yn mynd yn ôl ac ymlaen, 480 00:22:12,620 --> 00:22:16,080 Dydw i erioed wedi edrych yn ôl mewn gwirionedd, ond beth sy'n digwydd pan fyddaf yn mewnosod ef 481 00:22:16,080 --> 00:22:20,302 neu hi i ddechrau y rhestr fel y gwnaethom ar ddydd Llun? 482 00:22:20,302 --> 00:22:21,010 Beth sy'n digwydd? 483 00:22:21,010 --> 00:22:21,510 Yeah? 484 00:22:21,510 --> 00:22:23,122 CYNULLEIDFA: [Anghlywadwy]. 485 00:22:23,122 --> 00:22:24,830 SIARADWR: Yeah, mae hynny'n Roedd y ddalfa, dde? 486 00:22:24,830 --> 00:22:26,746 Efallai y byddwch yn cofio o eich cyd-ddisgyblion, os ydynt yn 487 00:22:26,746 --> 00:22:29,670 yn gwneud unrhyw symudiad gyda eu traed, a oedd llawdriniaeth. 488 00:22:29,670 --> 00:22:33,610 Felly, pe byddai tri o bobl yma ac y person newydd yn perthyn ffordd dros yno, 489 00:22:33,610 --> 00:22:37,360 ar lwyfan hir fel hyn, yn sicr, fe neu gallai hi dim ond yn mynd i'r diwedd un. 490 00:22:37,360 --> 00:22:40,074 Ond os ydym yn meddwl am cyfrifiadur ac amrywiaeth o gof, 491 00:22:40,074 --> 00:22:41,990 bobl hyn yn mynd i gael i siffrwd dros 492 00:22:41,990 --> 00:22:43,260 i wneud lle ar gyfer y person hwnnw. 493 00:22:43,260 --> 00:22:46,930 Ac felly bod minws n 1 shufflings, n minws 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 shufflings minws 3 yn unig fath o digwydd tu ôl i mi, nid o fy mlaen 495 00:22:50,660 --> 00:22:52,710 fel o'r blaen, mewn rhyw ystyr. 499 00:22:52,557 --> 00:22:54,640 Yn awr wrth fynd heibio, ac fel y Efallai eich bod wedi gweld ar-lein 500 00:22:54,640 --> 00:22:57,699 os byddwch yn dechrau procio o gwmpas am math, mae cymaint o rai gwahanol 501 00:22:57,699 --> 00:22:59,490 allan yna, rhai ohonynt yn well nag eraill. 502 00:22:59,490 --> 00:23:02,200 Yn wir, bogosort yn un dyna fath o hwyl i edrych i fyny. 503 00:23:02,200 --> 00:23:06,650 Bogosort cymryd set o rhifau neu ddweud dec o gardiau, 504 00:23:06,650 --> 00:23:09,870 ar hap shuffles hwy, a gwirio os ydynt yn didoli. 505 00:23:09,870 --> 00:23:12,130 Ac os nad yw, mae'n ei eto. 506 00:23:12,130 --> 00:23:14,140 Ac os nad yw, mae'n ei eto. 507 00:23:14,140 --> 00:23:15,440 Os nad yw, mae'n ei eto. 508 00:23:15,440 --> 00:23:17,060 Yn anhygoel dwp. 509 00:23:17,060 --> 00:23:19,520 >> Ac yn wir, os ydych yn darllen fel erthygl Wicipedia, 510 00:23:19,520 --> 00:23:21,200 ei lysenw yn fath dwp. 511 00:23:21,200 --> 00:23:25,180 Yn y pen draw bydd yn gweithio, gobeithio, yn cael digon o amser, 512 00:23:25,180 --> 00:23:28,240 ond faint o amser Gallai gymryd cryn dipyn o amser. 513 00:23:28,240 --> 00:23:31,650 Felly, pe gallwn, gadewch i cyflymder pethau i fyny o enghraifft Mary Beth yn gynharach, 514 00:23:31,650 --> 00:23:35,150 drwy gael ychydig mwy o elfennau, ond dau proseswyr mwy. 515 00:23:35,150 --> 00:23:37,100 Mae dau o bobl, os ydych yn Ni fyddai ots ymuno â mi. 516 00:23:37,100 --> 00:23:40,972 Beth am 1 dros yma, ac gadewch i ni go-- oes neb dros yno? 517 00:23:40,972 --> 00:23:41,722 Nid oes unrhyw un dros yno? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 Chi gyda'r du shirt, ie, dewch draw. 520 00:23:44,190 --> 00:23:45,000 Mae pob hawl, beth yw eich enw? 521 00:23:45,000 --> 00:23:45,720 >> CYNULLEIDFA: Peter. 522 00:23:45,720 --> 00:23:46,100 >> SIARADWR: Beth sy'n bod? 523 00:23:46,100 --> 00:23:46,766 >> CYNULLEIDFA: Peter. 524 00:23:46,766 --> 00:23:49,450 SIARADWR: Peter, David, neis i gwrdd â chi. 525 00:23:49,450 --> 00:23:53,670 Mae pob hawl, rydym wedi Pedr fan hyn, os ydych yn eisiau dod ar y bwrdd dros yma. 526 00:23:53,670 --> 00:23:54,550 A beth yw eich enw? 527 00:23:54,550 --> 00:23:55,216 >> CYNULLEIDFA: Elena. 528 00:23:55,216 --> 00:23:55,970 SIARADWR: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, neis i gwrdd â chi. 530 00:23:57,030 --> 00:23:58,060 Elena yn cyfarfod Peter. 531 00:23:58,060 --> 00:23:59,170 Pedr, Elena. 532 00:23:59,170 --> 00:24:02,290 A bydd angen i ni Andrew hyd yma hefyd, os gwelwch yn dda. 533 00:24:02,290 --> 00:24:06,107 Ac mae eich her yn mynd i fod i ddatrys dec o gardiau. 534 00:24:06,107 --> 00:24:08,190 Ac os anghyfarwydd, dec Dylai o gardiau yn y pen draw 535 00:24:08,190 --> 00:24:11,064 eu didoli bach rhywbeth fel hyn lle y byddwn ni'n gwneud y clybiau, ac yna 536 00:24:11,064 --> 00:24:13,660 y rhawiau, yna bydd y calonnau a diamonds, o ace fel un, 537 00:24:13,660 --> 00:24:15,570 holl ffordd i fyny at frenin. 538 00:24:15,570 --> 00:24:20,890 >> Mae'r cardiau Rydw i'n mynd i roi i chi yn mynd i fod yn 52 mewn nifer. 539 00:24:20,890 --> 00:24:23,160 Rydym yn mynd i yn yr un modd amser i chi, mewn dim ond eiliad. 540 00:24:23,160 --> 00:24:26,410 Rydym yn mynd i daflu Andrew fyny ar y sgrin yma, 541 00:24:26,410 --> 00:24:28,170 er i wylio wrth i chi wneud hyn. 542 00:24:28,170 --> 00:24:31,070 Ac fel bod yr holl o hyn yn oed yn fwy gweladwy, 543 00:24:31,070 --> 00:24:33,490 mae'r rhain yn y cardiau Cawn ar Amazon. 544 00:24:33,490 --> 00:24:42,861 Fel eu bod yn barod ar hap didoli, ac rydym yn mynd i amser i chi. 545 00:24:42,861 --> 00:24:44,610 Ac rydym yn mynd i gadw'n go iawn y tro hwn, 546 00:24:44,610 --> 00:24:47,820 felly rydym yn mynd i geisio pwysau arnoch oherwydd fel arall y bydd hyn yn mynd yn ddiflas 547 00:24:47,820 --> 00:24:48,460 yn gyflym. 548 00:24:48,460 --> 00:24:53,860 Pe gallech fynd ymlaen i ddidoli 52 elfennau at ei gilydd trwy ryw fodd, yn awr. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> Ac eto, wrth i ni wylio'r rhain guys gwneud yr hyn, yn y pen draw 551 00:25:07,180 --> 00:25:10,200 yn mynd i gynhyrchu amlwg canlyniad, meddyliwch am 'n sylweddol 552 00:25:10,200 --> 00:25:12,962 sut y maent yn pob un yn ei wneud, sut y gallech ddisgrifio. 553 00:25:12,962 --> 00:25:15,045 Oherwydd unwaith eto, mae'r rhain yn holl brosesau, algorithmau 554 00:25:15,045 --> 00:25:17,090 ein bod yn eu cymryd yn ganiataol fel dynol. 555 00:25:17,090 --> 00:25:22,349 Ond eich bod wedi yn ôl pob tebyg o amser wedi cael greddf, ymhell cyn i chi hyd yn oed yn 556 00:25:22,349 --> 00:25:24,390 yn meddwl am gymryd gwyddoniaeth gyfrifiadurol dosbarth chi 557 00:25:24,390 --> 00:25:27,223 efallai wedi cael y reddf gyda i ddatrys problemau fel hyn. 558 00:25:27,223 --> 00:25:29,560 Ond unwaith y byddwch yn adnabod patrymau a dechrau 559 00:25:29,560 --> 00:25:32,407 i ffurfioli y camau â nhw eich bod yn datrys y problemau hyn, 560 00:25:32,407 --> 00:25:35,490 fe welwch y gallwch ddatrys llawer yn fwy diddorol ac yn llawer mwy cymhleth 561 00:25:35,490 --> 00:25:39,190 problemau yn gyflym. 562 00:25:39,190 --> 00:25:42,351 Felly rhywun o'r gynulleidfa, yr hyn sy'n o leiaf un elfen o'r algorithm 563 00:25:42,351 --> 00:25:43,350 eu bod yn defnyddio yma? 564 00:25:43,350 --> 00:25:44,275 >> CYNULLEIDFA: [Anghlywadwy] 565 00:25:44,275 --> 00:25:45,150 SIARADWR: Beth sy'n bod? 566 00:25:45,150 --> 00:25:47,062 CYNULLEIDFA: Drwy siwt. 567 00:25:47,062 --> 00:25:47,770 SIARADWR: Drwy siwt. 568 00:25:47,770 --> 00:25:50,630 Felly, cyntaf y byddant yn cael eu clystyru pob un o'r deiamwntiau ei gilydd 569 00:25:50,630 --> 00:25:52,560 mae'n ymddangos, pob un o'r calonnau at ei gilydd mae'n ymddangos, 570 00:25:52,560 --> 00:25:56,520 ac yn y blaen, heb barch ar gyfer y niferoedd ar y cardiau. 571 00:25:56,520 --> 00:26:00,900 Ac yn awr y maent yn ymddangos, er enghraifft, i gael eu didoli yn ôl rhif. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Da iawn. 574 00:26:08,910 --> 00:26:12,370 >> Mae pob hawl, felly beth sy'n mynd i fydd y cam olaf, yna yma? 575 00:26:12,370 --> 00:26:16,950 Unwaith y mae gennym bedwar siwtiau ddidoli, beth y mae angen inni ei wneud at y pedwar pentyrrau 576 00:26:16,950 --> 00:26:20,059 er mwyn cyflawni un didoli dec, yn syml? 577 00:26:20,059 --> 00:26:21,350 Felly mae angen i uno â hwy eto. 578 00:26:21,350 --> 00:26:25,160 >> Felly mae 'na syniad diddorol sy'n unwaith eto, mentraf ddweud, yn reddfol iawn hyd yn oed 579 00:26:25,160 --> 00:26:28,140 os gallai ydych erioed wedi taro y math hwnnw o label arno. 580 00:26:28,140 --> 00:26:31,900 Mae hyn yn syniad sylfaenol o rannu y broblem nid yn ei hanner y cyfnod hwn, 581 00:26:31,900 --> 00:26:33,410 ond o leiaf yn bedwar darn. 582 00:26:33,410 --> 00:26:36,810 Datrys 'n bert lawer problemau sylfaenol union yr un fath 583 00:26:36,810 --> 00:26:40,480 ar wahân i'w gilydd, ac wedyn gyfuno'r canlyniadau. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 Ac, rhagorol, wneud. 586 00:26:50,140 --> 00:26:52,140 Mae pob hawl, rownd mawr o gymeradwyaeth, pe gallem. 587 00:26:52,140 --> 00:26:56,480 >> [Cymeradwyaeth] 588 00:26:56,480 --> 00:26:59,740 >> SIARADWR: Nid oes gennyf unrhyw syniad beth wnewch chi helpu wneud â'r rhain, ond dyma i chi fynd. 589 00:26:59,740 --> 00:27:01,690 Ddiolch 'ch ogystal. 590 00:27:01,690 --> 00:27:04,660 Felly, gadewch i ni weld, dwy funud ac wyth eiliad, 591 00:27:04,660 --> 00:27:07,490 os hoffech i herio eich ffrindiau. 592 00:27:07,490 --> 00:27:12,160 Beth felly yn mynd i fod yn cymryd i ffwrdd oddi wrth hyn 593 00:27:12,160 --> 00:27:13,830 y gallwn trosoledd yn fwy cyffredinol? 594 00:27:13,830 --> 00:27:16,080 Wel, yn meddwl yn ôl i amrywiaeth hwn o rifau, 595 00:27:16,080 --> 00:27:19,060 a meddwl yn ôl yn awr at rai o'r pseudocode rydym wedi ysgrifennu yn y gorffennol, 596 00:27:19,060 --> 00:27:22,080 a dyma oedd y pseudocode ar gyfer datrys y broblem llyfr ffôn. 597 00:27:22,080 --> 00:27:25,150 Lle mewn pseudocode wyf wedi'u rhifo ffordd fwy trefnus 598 00:27:25,150 --> 00:27:28,400 o ddisgrifio sut fe wnes i 'n athrylithgar iawn algorithm dynol o rannu'r ffôn 599 00:27:28,400 --> 00:27:31,650 llyfr yn ei hanner, ailadrodd, ailadrodd, ailadrodd, nes i mi ddod o hyd i rywun fel Mike Smith, 600 00:27:31,650 --> 00:27:33,790 os yw'n wir yn y llyfr ffôn. 601 00:27:33,790 --> 00:27:37,610 >> Ond yr wyf yn fath o defnyddio beth 'n annhymerus' galw dull ailadroddol iawn yma, 602 00:27:37,610 --> 00:27:42,160 yn rhybudd enwedig llinell 8 a llinell 11. 603 00:27:42,160 --> 00:27:46,750 Mae'r rhai yn dystiolaeth o ailadroddol dull, dull dolennu, 604 00:27:46,750 --> 00:27:49,040 oherwydd dyna'n union yr ymddygiad y maent yn achosi. 605 00:27:49,040 --> 00:27:52,910 Llinellau hynny yn dweud ewch i llinell tri, a gallwch math o 606 00:27:52,910 --> 00:27:55,140 feddwl am hynny yn eich llygad meddwl fel bod yn ddolen. 607 00:27:55,140 --> 00:27:59,080 Mae'n dweud wrthych i fynd yn ôl i fyny i gam tri ac ailadrodd, unwaith eto, ac unwaith eto, 608 00:27:59,080 --> 00:28:00,010 ac unwaith eto. 609 00:28:00,010 --> 00:28:04,410 >> Ond beth os ydym trosoledd syniad allweddol yma inni wneud nad oedd y tro diwethaf, 610 00:28:04,410 --> 00:28:10,280 a symleiddio llinell 8 a llinell 11 ac mae eu cymdogion 611 00:28:10,280 --> 00:28:12,840 fel dim ond hyn, mewn melyn. 612 00:28:12,840 --> 00:28:16,480 Dyw hi ddim yn byrhau sylfaenol y pseudocode yn fawr iawn, 613 00:28:16,480 --> 00:28:20,530 ond mae'n newid yn sylfaenol natur fy algorithm. 614 00:28:20,530 --> 00:28:24,220 Yr hyn rydw i'n awr yn dweud yng ngham 7, yng ngham 10, 615 00:28:24,220 --> 00:28:29,140 yw chwilio am Mike yn yr un ffordd union, 616 00:28:29,140 --> 00:28:31,580 ond dim ond yn y chwith hanner neu yn hanner cywir. 617 00:28:31,580 --> 00:28:33,420 >> Felly, mewn geiriau eraill, os Yr wyf yn dechrau o'r cam un, 618 00:28:33,420 --> 00:28:36,150 godi llyfr ffôn, yn agored i ganol o'r llyfr ffôn, yn edrych ar enwau, 619 00:28:36,150 --> 00:28:39,010 os Smith ymhlith enw i, ffoniwch Mike, arall 620 00:28:39,010 --> 00:28:44,340 os Smith yn gynharach yn y llyfr, cam saith chwilio am Mike mewn chwith hanner y llyfr. 621 00:28:44,340 --> 00:28:47,130 Ond yn y math hwnnw o yn teimlo fel mae'n gadael i mi hongian, dde? 622 00:28:47,130 --> 00:28:49,240 Mewn melyn, yn cyfarwyddyd, ond sut ydw i'n 623 00:28:49,240 --> 00:28:51,870 chwilio am Mike yn y chwith hanner y llyfr ffôn? 624 00:28:51,870 --> 00:28:54,210 Ble ydw i'n cael algorithm ag yr wyf 625 00:28:54,210 --> 00:28:57,100 Gall chwilio am rywun fel Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Wel, mae'n ein syllu yn wyneb. 627 00:28:58,980 --> 00:29:03,090 Gallaf llythrennol ddefnyddio'r union un fath rhaglen yn effeithiol yn mynd i fyny i ben 628 00:29:03,090 --> 00:29:06,490 unwaith eto ac ail-redeg yr un llinellau o god. 629 00:29:06,490 --> 00:29:10,610 >> Felly hyd yn oed er y dylai hyn deimlo fel tipyn o ddiffiniad cylchol 630 00:29:10,610 --> 00:29:13,480 ble rydych yn ateb rhywun yn gwestiwn gan jyst fath o ofyn 631 00:29:13,480 --> 00:29:15,990 yr un cwestiwn eto, fel pam, pam, pam? 632 00:29:15,990 --> 00:29:21,580 Y gwir amdani yw oherwydd ein bod wedi codio galed un neu ddau o linellau arbennig, cam 4, 633 00:29:21,580 --> 00:29:25,320 sy'n os, ac yn cam 12, a oedd yn yn effeithiol gangen arall, 634 00:29:25,320 --> 00:29:30,120 oherwydd bod gennym fesurau rhywbeth dros dro y rhai, Bydd algorithm hwn yn dod i ben os ydym 635 00:29:30,120 --> 00:29:32,050 dod o hyd i Mike, neu os nad ydym yn ei wneud. 636 00:29:32,050 --> 00:29:36,810 Ond yng ngham 7 a 10 erbyn hyn, rydym wedi yr hyn y byddwn yn ei alw'n algorithm dychweliadol. 637 00:29:36,810 --> 00:29:40,420 Ac recursion yn wir yn syniad pwerus mae hynny'n ychydig o feddwl blygu ar y dechrau, 638 00:29:40,420 --> 00:29:42,500 y gallwn yn awr wneud cais fel a ganlyn. 639 00:29:42,500 --> 00:29:46,600 >> Uno fath fydd y math olaf y rydym yn edrych ar, o leiaf yn y dosbarth yn ffurfiol. 640 00:29:46,600 --> 00:29:50,040 Ac mae'n sylfaenol wahanol o dair olaf hynny, ac yn sicr 641 00:29:50,040 --> 00:29:52,140 pedwar olaf os ydym yn cynnwys bogosort. 642 00:29:52,140 --> 00:29:54,810 Dyma y pseudocode ar gyfer math uno. 643 00:29:54,810 --> 00:30:00,170 Pan ar fewnbwn o elfennau n, o ystyried mor amrywiaeth o faint n, os yw n yn llai na 2, 644 00:30:00,170 --> 00:30:01,040 dychwelyd. 645 00:30:01,040 --> 00:30:03,610 Felly pam ydw i'n cael y sanity wirio yn gyntaf? 646 00:30:03,610 --> 00:30:09,477 Beth yw'r goblygiadau os wyf yn llaw ydych amrywiaeth y mae ei hyd n yn llai na 2? 647 00:30:09,477 --> 00:30:11,060 Mae eisoes wedi eu didoli, yn amlwg, dde? 648 00:30:11,060 --> 00:30:13,640 Oherwydd bod y rhestr naill ai wedi un elfen, sef trivially 649 00:30:13,640 --> 00:30:15,180 didoli am ei fod yn yr unig beth yno. 650 00:30:15,180 --> 00:30:18,138 Neu, 'i' o faint sero sy'n golygu does dim byd i ddidoli, hynny gan natur 651 00:30:18,138 --> 00:30:18,720 mae'n cael ei datrys. 652 00:30:18,720 --> 00:30:20,410 Does dim ond dim o'i le yno. 653 00:30:20,410 --> 00:30:22,310 Felly dyna ein achos sylfaenol fel y'u gelwir. 654 00:30:22,310 --> 00:30:24,440 >> Mae hynny'n debyg o ran ysbryd i'r hyn a wnaethom gyda Mike. 655 00:30:24,440 --> 00:30:26,023 Os yw Mike yn y llyfr ffôn, ei alw ef. 656 00:30:26,023 --> 00:30:27,740 Os nad yw ei fod yno, rhoi'r gorau iddi. 657 00:30:27,740 --> 00:30:31,240 Mae'n achos sylfaenol fel y'i gelwir, i wneud yn siŵr algorithm hwn ar ddiwedd y dydd 658 00:30:31,240 --> 00:30:33,540 yn dod i ben mewn rhai amgylchiadau. 659 00:30:33,540 --> 00:30:37,890 >> Ond dyma y naid ffydd yn awr, arall, didoli'r hanner chwith y elfennau, 660 00:30:37,890 --> 00:30:39,740 Yna datrys y dde hanner o'r elfennau, 661 00:30:39,740 --> 00:30:41,189 ac yna cyfuno'r haneri didoli. 662 00:30:41,189 --> 00:30:43,230 A dyma lle mae'n teimlo fel rydym yn wrthod wynebu. 663 00:30:43,230 --> 00:30:46,900 Rwyf wedi gofyn i chi i roi trefn ar n elfennau, ac rwy'n 664 00:30:46,900 --> 00:30:50,712 gan ddywedyd, OK, peidiwch iddo drwy ddidoli y chwith a didoli y dde. 665 00:30:50,712 --> 00:30:52,420 Ond yr wyf yn dweud un beth arall, ac mae hyn yn 666 00:30:52,420 --> 00:30:55,530 yw'r thema allweddol mae'n ymddangos yn y greddf hyd yn hyn, 667 00:30:55,530 --> 00:30:57,380 mae y trydydd cam o uno. 668 00:30:57,380 --> 00:31:00,430 Sydd er ei fod yn ymddangos mor fud yn yr ysbryd, 669 00:31:00,430 --> 00:31:02,320 fel dim ond uno pethau at ei gilydd, mae'n ymddangos 670 00:31:02,320 --> 00:31:05,380 i fod yn gam allweddol tuag at y reassembly o ddwy broblem sy'n 671 00:31:05,380 --> 00:31:07,330 eu rhannu yn y pen draw yn ei hanner. 672 00:31:07,330 --> 00:31:12,090 >> Felly uno fath, gadewch i ni wneud hyn, os wnewch chi helpu digrifwch i mi, gydag un arddangos mwy, 673 00:31:12,090 --> 00:31:14,730 yn union fel y bydd gennym rai rhifau i weithio gyda. 674 00:31:14,730 --> 00:31:19,470 Alla i gyfnewid wyth straen peli ar gyfer wyth o bobl? 675 00:31:19,470 --> 00:31:29,320 Mae pob hawl, beth am i chi dri, rydych bedair yn yr adran hon, pump, chwech, a gadewch i ni 676 00:31:29,320 --> 00:31:30,720 yn 7, 8, yn dod ar i fyny. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, OK yeah. 679 00:31:36,520 --> 00:31:38,640 Minus 8, dyna ni, ac 1. 680 00:31:38,640 --> 00:31:39,150 Ardderchog. 681 00:31:39,150 --> 00:31:42,000 Mae pob hawl yn dod ar i fyny, gadewch i ni rhoi rhifau yn gyflym. 682 00:31:42,000 --> 00:31:50,800 Rhif dau, rhif tri, rhif pedwar, rhif pump, chwech, saith, ac wyth. 683 00:31:50,800 --> 00:31:52,140 Fe wnes wyth yn gywir y tro hwn. 684 00:31:52,140 --> 00:31:56,390 >> Iawn, felly fynd yn ei flaen os gallech, ac gadewch i ddidoli yn y gorchymyn gwreiddiol 685 00:31:56,390 --> 00:31:59,810 a gawsom ddoe a oedd yn edrych fel hyn, os na fyddech yn meddwl. 686 00:31:59,810 --> 00:32:03,620 A gadewch i ni wneud hynny o flaen y tabl. 687 00:32:03,620 --> 00:32:06,510 Mae pob hawl, felly uno fath. 688 00:32:06,510 --> 00:32:08,820 Dyma lle mae'n mynd i gael math o ddiddorol, 689 00:32:08,820 --> 00:32:12,800 oherwydd fy mod yn ymddangos i fod yn rhoi fy hun gymaint yn llai o wybodaeth heddiw. 690 00:32:12,800 --> 00:32:15,149 >> Felly uno fath yn gyntaf oll ar fewnbwn o elfennau n, 691 00:32:15,149 --> 00:32:18,440 ac yn amlwg heb fod yn llai na dau, 'i' wyth, felly mae gen i ychydig mwy o waith i'w wneud. 692 00:32:18,440 --> 00:32:21,140 Felly nawr yn feddyliol i ni fel dosbarth yn awr yn y gangen arall, 693 00:32:21,140 --> 00:32:22,540 sy'n golygu tri cham. 694 00:32:22,540 --> 00:32:25,017 Yn gyntaf, rhaid i mi ddatrys y chwith hanner o'r elfennau. 695 00:32:25,017 --> 00:32:26,350 Felly sut mae mynd ati i wneud hyn? 696 00:32:26,350 --> 00:32:28,950 Wel, dw i'n mynd i fath o rhannu yn y pen y rhestr yma, 697 00:32:28,950 --> 00:32:30,700 Nid oes rhaid i chi symud yn gorfforol, ac rwy'n 698 00:32:30,700 --> 00:32:33,180 mynd i ganolbwyntio yn unig ar y chwith hanner o'r elfennau yma. 699 00:32:33,180 --> 00:32:36,770 Felly sut mae mynd ati i ddidoli restr nawr o faint pedwar? 700 00:32:36,770 --> 00:32:38,730 Beth yw fy algorithm? 701 00:32:38,730 --> 00:32:42,580 Yn gyntaf yr wyf yn gwirio yn n llai na dau, na, felly yr wyf yn symud ymlaen at y bloc arall eto. 702 00:32:42,580 --> 00:32:43,900 Trefnu chwith hanner yr elfennau. 703 00:32:43,900 --> 00:32:45,608 >> Felly nawr eto, yn feddyliol, a dyma lle 704 00:32:45,608 --> 00:32:49,550 rhaid i chi gronni llawer o hanes meddwl, os mynnwch. 705 00:32:49,550 --> 00:32:51,940 Nawr rwy'n didoli y chwith hanner y hanner chwith. 706 00:32:51,940 --> 00:32:57,000 Mae pob hawl, felly yn awr yr wyf yn galw fy un uno didoli algorithm, yn N llai na dau? 707 00:32:57,000 --> 00:33:00,590 Na, y mae dau, felly mae'n rhaid i mi roi trefn yr hanner chwith, a'r hanner cywir. 708 00:33:00,590 --> 00:33:02,042 Felly dyma ni, didoli yr hanner chwith. 709 00:33:02,042 --> 00:33:03,750 Pam na wnewch chi jyst gymryd un cam ymlaen. 710 00:33:03,750 --> 00:33:04,415 Beth yw eich enw? 711 00:33:04,415 --> 00:33:04,860 >> CYNULLEIDFA: Darren. 712 00:33:04,860 --> 00:33:05,260 >> SIARADWR: Dan. 713 00:33:05,260 --> 00:33:06,040 Mae Dan wedi camu ymlaen. 714 00:33:06,040 --> 00:33:06,748 >> CYNULLEIDFA: Darren. 715 00:33:06,748 --> 00:33:09,000 SIARADWR: Darren, a wnaed. 716 00:33:09,000 --> 00:33:10,090 Wnaethoch chi ei ddweud Darren neu Dan? 717 00:33:10,090 --> 00:33:10,550 >> CYNULLEIDFA: Darren. 718 00:33:10,550 --> 00:33:11,216 >> SIARADWR: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren wedi camu ymlaen ac mae bellach yn cael ei sortio. 720 00:33:14,422 --> 00:33:16,130 Ac mae hyn yn bron yn hawliad inane, dde? 721 00:33:16,130 --> 00:33:18,862 Dydw i ddim yn ymddangos mewn gwirionedd i fod yn cyflawni unrhyw beth, ond gadewch i ni symud ymlaen. 722 00:33:18,862 --> 00:33:20,820 Nawr, gadewch i mi ddatrys yr hawl hanner o'r elfennau. 723 00:33:20,820 --> 00:33:21,200 Beth yw eich enw? 724 00:33:21,200 --> 00:33:21,690 >> CYNULLEIDFA: Luke. 725 00:33:21,690 --> 00:33:22,273 >> SIARADWR: Luke. 726 00:33:22,273 --> 00:33:23,400 Dewch ymlaen, cam ymlaen. 727 00:33:23,400 --> 00:33:25,640 Done, yr wyf wedi datrys Luke. 728 00:33:25,640 --> 00:33:28,570 Mae'r hanner chwith bellach yn didoli a yr hanner ar hyn o bryd yn cael ei sortio, 729 00:33:28,570 --> 00:33:30,770 ond unwaith eto, mae yn gam allweddol yma. 730 00:33:30,770 --> 00:33:32,940 Beth sydd angen i mi ei wneud nesaf? 731 00:33:32,940 --> 00:33:33,941 Cyfuno haneri didoli. 732 00:33:33,941 --> 00:33:36,648 Nawr rydym yn mynd i jyst gael mae pawb yn ôl ac ymlaen yn y modd hwn, 733 00:33:36,648 --> 00:33:38,620 am fy mod yn fath o angen ychydig o le crafu. 734 00:33:38,620 --> 00:33:40,411 Mae bron fel y rhain guys yn ar fwrdd, 735 00:33:40,411 --> 00:33:42,460 ac mae angen rhywfaint o le i mi i symud o gwmpas ar. 736 00:33:42,460 --> 00:33:44,170 Felly dw i'n mynd i uno rydych guys drwy edrych 737 00:33:44,170 --> 00:33:45,960 ar yr hanner chwith a'r hanner cywir. 738 00:33:45,960 --> 00:33:48,740 A phwy amlwg yn dod yn gyntaf, Gadawodd hanner neu hanner cywir? 739 00:33:48,740 --> 00:33:52,710 Felly hanner i'r dde, felly gadewch i ni symud Luke dros yma i safle gwreiddiol Darren. 740 00:33:52,710 --> 00:33:57,640 Ac yn awr i uno eu hanner chwith i mewn, Darren yn mynd i symud yn iawn yno. 741 00:33:57,640 --> 00:33:59,750 >> Felly, yn teimlo fel bron effaith fath swigen, 742 00:33:59,750 --> 00:34:02,482 ond mae fy algorithm sylfaenol, wahanol iawn y tro hwn. 743 00:34:02,482 --> 00:34:04,815 Ond nawr yw ble mae pethau yn cael ychydig yn blino oherwydd eich 744 00:34:04,815 --> 00:34:06,810 rhaid i ailddirwyn feddyliol lle wnes i yn gadael i ffwrdd. 745 00:34:06,810 --> 00:34:09,893 Dwi newydd unodd y haneri ddidoli, sy'n golygu fy mod lle yn fy algorithm? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Rhaid i mi ddatrys yr hanner dde, dde? 748 00:34:13,770 --> 00:34:15,910 >> Os ydych yn ail-ddirwyn, yn llythrennol ar y fideo, wnewch chi helpu 749 00:34:15,910 --> 00:34:18,339 gwelwch ein bod yn mynd â hyn pwynt Luke a Darren 750 00:34:18,339 --> 00:34:21,370 drwy ddidoli y chwith hanner y hanner chwith. 751 00:34:21,370 --> 00:34:23,430 Yna, rydym yn uno y rhai haneri ddidoli, a oedd yn 752 00:34:23,430 --> 00:34:27,941 yn golygu bod y cam nesaf yw fath y hanner dde o'r hanner chwith. 753 00:34:27,941 --> 00:34:29,649 Mae pob hawl, felly gadewch i ni gwneud hyn yn gyflymach. 754 00:34:29,649 --> 00:34:33,282 Mae pob hawl, chwech, dw i'n mynd i hawlio yn awr yr ydych yn cael eu didoli, dewch ymlaen. 755 00:34:33,282 --> 00:34:33,990 Beth yw eich enw? 756 00:34:33,990 --> 00:34:34,589 >> CYNULLEIDFA: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> SIARADWR: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano bellach yn cael ei sortio. 759 00:34:36,010 --> 00:34:36,450 A beth yw eich enw? 760 00:34:36,450 --> 00:34:37,080 >> CYNULLEIDFA: Alex. 761 00:34:37,080 --> 00:34:38,379 >> SIARADWR: Alex bellach yn cael ei sortio. 762 00:34:38,379 --> 00:34:40,750 Chwith hanner, hanner i'r dde, beth yw'r cam olaf? 763 00:34:40,750 --> 00:34:41,250 Uno. 764 00:34:41,250 --> 00:34:44,310 Pretty ddibwys, felly rwy'n mynd i uno mewn chwech, 765 00:34:44,310 --> 00:34:46,930 gymryd cam yn ôl, wyth, gymryd cam yn ôl. 766 00:34:46,930 --> 00:34:49,530 Ac yn awr sylwi ar hyn yn tecawê defnyddiol, yr hyn 767 00:34:49,530 --> 00:34:53,930 yn awr yn wir am yr hanner chwith y rhestr, heb ystyried sut yr ydym yn dechrau? 768 00:34:53,930 --> 00:34:55,090 Mae'n cael ei datrys. 769 00:34:55,090 --> 00:34:57,750 >> Nawr, nid yw'n cael ei datrys yn y cynllun mawr o bethau, 770 00:34:57,750 --> 00:35:00,250 ond mae'n cael ei datrys yn annibynnol yr hanner arall. 771 00:35:00,250 --> 00:35:04,100 Nawr pa gam ydw i ar os wyf yn cadw ailddirwyn sut y dechreuodd y stori? 772 00:35:04,100 --> 00:35:05,680 Nawr mae'n rhaid i mi roi trefn yr hanner cywir. 773 00:35:05,680 --> 00:35:07,630 Felly nawr rydym yn ffordd yn ôl yn cychwyn y stori, 774 00:35:07,630 --> 00:35:08,921 a gadewch i ni wneud hyn yn gynt. 775 00:35:08,921 --> 00:35:11,320 Felly dw i'n mynd i ddatrys y hanner chwith y rhestr gyfan. 776 00:35:11,320 --> 00:35:13,060 Beth yw'r cam nesaf? 777 00:35:13,060 --> 00:35:15,840 Didoli'r hanner chwith yr hanner cywir. 778 00:35:15,840 --> 00:35:18,715 Didoli'r hanner chwith y chwith hanner y hanner cywir. 779 00:35:18,715 --> 00:35:19,590 A beth yw eich enw? 780 00:35:19,590 --> 00:35:20,230 >> CYNULLEIDFA: Omar. 781 00:35:20,230 --> 00:35:21,970 >> SIARADWR: Omar, gamu ymlaen, wneud. 782 00:35:21,970 --> 00:35:22,860 Hanner Chwith cael ei datrys. 783 00:35:22,860 --> 00:35:23,330 A beth yw eich enw? 784 00:35:23,330 --> 00:35:23,820 >> CYNULLEIDFA: Chris. 785 00:35:23,820 --> 00:35:25,620 >> SIARADWR: Chris, yn cymryd cam ymlaen, yr ydych yn cael eu didoli yn awr. 786 00:35:25,620 --> 00:35:27,010 Beth yw'r cam allweddol yn awr? 787 00:35:27,010 --> 00:35:27,510 Uno. 788 00:35:27,510 --> 00:35:30,509 Felly, un yn mynd i uno i mewn i le yma, pe gallech gymryd cam yn ôl, 789 00:35:30,509 --> 00:35:32,930 a thri yn mynd i gymryd cam yn ôl, yn uno. 790 00:35:32,930 --> 00:35:38,080 Felly mae'r hanner chwith y hanner i'r dde, yn awr yn cael ei sortio. 791 00:35:38,080 --> 00:35:41,747 Dweud y gwir, algorithm hwn yn teimlo fel ein bod yn gwastraffu ffordd mwy o amser nag o'r blaen, 792 00:35:41,747 --> 00:35:44,830 ond pe baem yn gwneud hyn mewn amser real, rydym annhymerus weld beth mae'r siopau cludfwyd mynd i fod. 793 00:35:44,830 --> 00:35:47,970 Yn awr dyma fi, yn iawn hanner y hanner cywir, 794 00:35:47,970 --> 00:35:50,170 gadewch i mi fynd yn ei flaen ac yn didoli'r hanner chwith. 795 00:35:50,170 --> 00:35:51,482 Cam ymlaen, beth yw eich enw? 796 00:35:51,482 --> 00:35:52,190 CYNULLEIDFA: Ramsey. 797 00:35:52,190 --> 00:35:53,210 SIARADWR: Ramsey bellach yn cael ei sortio. 798 00:35:53,210 --> 00:35:53,570 Beth yw eich enw? 799 00:35:53,570 --> 00:35:54,200 >> CYNULLEIDFA: Marina. 800 00:35:54,200 --> 00:35:57,033 >> SIARADWR: Marina bellach yn cael ei sortio fel yn dda, os ydych yn cymryd un cam ymlaen. 801 00:35:57,033 --> 00:36:00,690 Gam allweddol yma yn awr yn uno, rwy'n mynd i plycio o fy dwy restr, 802 00:36:00,690 --> 00:36:01,720 chwith ac i'r dde. 803 00:36:01,720 --> 00:36:05,150 Pump yn mynd i ddod yn gyntaf, a saith yn mynd i ddod nesaf. 804 00:36:05,150 --> 00:36:06,410 Ac eto, mae hyn yn fwriadol. 805 00:36:06,410 --> 00:36:08,535 Mae'r ffaith eu bod yn cymryd camu ymlaen ac yn ôl 806 00:36:08,535 --> 00:36:12,997 i fod i gynrychioli na allwn gwneud algorithm hwn yn ei le mor hawdd 807 00:36:12,997 --> 00:36:15,830 fel didoli swigod, a didoli dethol, a didoli mewnosod lle rydym yn unig 808 00:36:15,830 --> 00:36:16,960 cadw cyfnewid pobl. 809 00:36:16,960 --> 00:36:19,940 Yr wyf yn llythrennol angen rhyw fath o bapur crafu lle 810 00:36:19,940 --> 00:36:21,827 i roi Folks hyn er fy mod yn gwneud yr uno, 811 00:36:21,827 --> 00:36:23,410 ac yna gallaf rhoi yn ôl yn eu lle. 812 00:36:23,410 --> 00:36:27,260 Ac mae hynny'n allweddol oherwydd fy mod yn defnyddio adnodd newydd, lle, nid dim ond amser. 813 00:36:27,260 --> 00:36:28,270 >> OK, mae hyn yn anhygoel. 814 00:36:28,270 --> 00:36:32,050 Hanner Chwith cael ei ddidoli, hanner cywir yn ddidoli, nawr bod allwedd uno cam. 815 00:36:32,050 --> 00:36:33,450 Sut ydw i'n mynd i uno hyn? 816 00:36:33,450 --> 00:36:35,470 Felly, os byddwch yn dilyn fy llaw chwith a llaw dde, 817 00:36:35,470 --> 00:36:38,930 Rydw i'n mynd i bwynt fy llaw chwith ar yr hanner chwith, fy llaw dde 818 00:36:38,930 --> 00:36:42,680 ar yr hanner cywir, ac yn awr rhaid i mi benderfynu cam wrth gam bwy i uno mewn. 819 00:36:42,680 --> 00:36:44,650 Sy'n amlwg yn dod gyntaf? 820 00:36:44,650 --> 00:36:45,150 Rhif un. 821 00:36:45,150 --> 00:36:47,327 Felly dewch draw yma, dyma ein pad crafu. 822 00:36:47,327 --> 00:36:49,910 Felly nawr rif un, a rhybudd beth 'n annhymerus' yn ei wneud gyda fy llaw dde, 823 00:36:49,910 --> 00:36:54,152 Rydw i'n mynd i symud fy un llaw dde gamu drosodd i bwynt rhif tri, 824 00:36:54,152 --> 00:36:55,860 ac yn awr mae'n rhaid i mi wneud yr un penderfyniad. 825 00:36:55,860 --> 00:36:58,387 Ac mewn gwirionedd yn sefyll yn iawn yn flaen Luke yma os ydych allai, 826 00:36:58,387 --> 00:36:59,720 oherwydd mae hyn yn ein pad crafu. 827 00:36:59,720 --> 00:37:00,610 Felly, pwy sy'n dod nesaf? 828 00:37:00,610 --> 00:37:05,000 Rydym wedi Luke gyda rhif dau neu Chris gyda rhif tri. 829 00:37:05,000 --> 00:37:07,460 Yn amlwg Luke, rhif dau, felly yr ydych yn dod yma. 830 00:37:07,460 --> 00:37:11,270 >> Ond mae fy llaw chwith yn awr yn mynd i cael ei gynyddrannedig i bwyntio at Darren, 831 00:37:11,270 --> 00:37:15,160 a dyma y allweddol yn cymryd i ffwrdd gyda uno, dw i'n mynd i ddal i wneud hyn, 832 00:37:15,160 --> 00:37:17,340 yn amlwg, os ydych yn garedig o ddilyn y rhesymeg. 833 00:37:17,340 --> 00:37:19,670 Ond mae fy nwylo byth yn mynd i fynd yn ôl, 834 00:37:19,670 --> 00:37:23,861 sy'n golygu fy mod yn unig byth yn symud i y chwith gyda fy broses uno, 835 00:37:23,861 --> 00:37:26,360 ac mae hynny'n mynd i fod yn allweddol i ein dadansoddiad mewn dim ond eiliad. 836 00:37:26,360 --> 00:37:27,859 >> Felly nawr gadewch i ni orffen hyn i fyny yn gyflym. 837 00:37:27,859 --> 00:37:31,650 Felly tri sy'n dod nesaf, Yna pedair dod nesaf, 838 00:37:31,650 --> 00:37:38,750 ac yn awr bump sy'n dod nesaf, yna chwech, a saith, ac yna yn olaf wyth. 839 00:37:38,750 --> 00:37:42,960 Teimlo fel y algorithm arafaf eto, ond nid os ydym mewn gwirionedd 840 00:37:42,960 --> 00:37:45,510 rhedeg ar yr un fath o gyflymder cloc, felly i 841 00:37:45,510 --> 00:37:48,106 siarad, gyda'r un roi tic cloc fel o'r blaen. 842 00:37:48,106 --> 00:37:48,605 Pam? 843 00:37:48,605 --> 00:37:51,100 Wel, Gadewch i ni gymryd edrych ar y canlyniad terfynol. 844 00:37:51,100 --> 00:37:56,990 >> Gadewch i ni fynd yn ôl dros yma, gadewch i mi dynnu i fyny arddangosiad ar eu golwg 845 00:37:56,990 --> 00:37:59,030 o'r hyn yr ydym newydd ei wneud. 846 00:37:59,030 --> 00:38:06,110 Chwyddo i mewn yma, ar hyn dudalen fan hyn, yn dweud Firefox 847 00:38:06,110 --> 00:38:08,200 ein bod am giwio i fyny yn y blwch hwn, gadewch i ni 848 00:38:08,200 --> 00:38:11,260 dweud fath swigen, gyda lle rydym yn awr yn gyfarwydd yn dda, 849 00:38:11,260 --> 00:38:14,130 didoli dethol, sef un arall deg un syml, 850 00:38:14,130 --> 00:38:18,250 ac yn awr didoli uno heddiw, a oedd fydd ein diweddglo hinsoddol. 851 00:38:18,250 --> 00:38:21,530 Y rheswm y cymerodd gymaint llawer hirach yma gyda phobl a fi ar lafar yw, 852 00:38:21,530 --> 00:38:23,480 yn amlwg, Im 'yn esbonio pob cam. 853 00:38:23,480 --> 00:38:26,920 Ond os ydych yn syml cyflawni hyn, llawer fel y gwnaethom fath swigen a dethol 854 00:38:26,920 --> 00:38:30,890 fath nid yn unig ar eu golwg, gwylio yn union faint yn fwy effeithlon 855 00:38:30,890 --> 00:38:33,330 Leveraging hwn o is-adran a concro 856 00:38:33,330 --> 00:38:39,150 Gellir pan gaiff ei ddefnyddio i set ddata sy'n Nid yw hyd yn oed maint wyth, ond hyd yn oed yn llawer, 857 00:38:39,150 --> 00:38:39,970 llawer mwy. 858 00:38:39,970 --> 00:38:44,585 Yr wyf yn rhoi i chi uno didoli, ochr yn ochr â'r rhain algorithmau eraill. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Mae hyn yn mynd i gael boenus gyflym, ac mae'r diweddglo 861 00:38:58,530 --> 00:39:00,890 Nid yn arbennig o hinsoddol, maent ond yn y pen draw didoli. 862 00:39:00,890 --> 00:39:05,280 Ond yr allwedd cymryd i ffwrdd yw bod edrych faint yn gynt o lawer uno fath 863 00:39:05,280 --> 00:39:08,110 oedd, oni bai eich bod yn meddwl fy mod unig fath o cyboli gyda chi. 864 00:39:08,110 --> 00:39:13,100 Os byddwn yn gwneud hyn un tro olaf, gadewch i ail-lwytho hwn, gadewch i ni fynd yn ôl 865 00:39:13,100 --> 00:39:14,960 a dewis math swigen, a dim ond ar gyfer cychwyn, 866 00:39:14,960 --> 00:39:17,330 gadewch i ni ddewis gosod didoli, dim ond ar gyfer mesur da. 867 00:39:17,330 --> 00:39:20,020 A'r tro hwn eto, gadewch i ni dewis didoli uno a gadewch i ni 868 00:39:20,020 --> 00:39:21,595 mewn gwirionedd yn rhedeg ochr yn ochr hyn. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> Ac nid yw, mewn gwirionedd, mae llyngyr. 871 00:39:26,930 --> 00:39:31,140 Yr hyn yr wyf wedi ei wneud yn effeithiol yw fy mod i wedi Rhannwyd fy mewnbwn yn ei hanner, unwaith eto, 872 00:39:31,140 --> 00:39:32,240 ac unwaith eto, ac unwaith eto. 873 00:39:32,240 --> 00:39:35,590 Ac mae dim ond cymaint o weithiau y gallwch rannu eich mewnbwn i haneri, gadawodd 874 00:39:35,590 --> 00:39:36,240 ac i'r dde. 875 00:39:36,240 --> 00:39:39,425 Beth yw'r fformiwla yr ydym yn cadw gweld sy'n disgrifio'r is-adran yn ei hanner 876 00:39:39,425 --> 00:39:41,050 unwaith eto, ac unwaith eto, ac unwaith eto, ac unwaith eto? 877 00:39:41,050 --> 00:39:41,890 >> CYNULLEIDFA: Logio n. 878 00:39:41,890 --> 00:39:42,760 >> SIARADWR: Logio n. 879 00:39:42,760 --> 00:39:46,300 Ond yna mae un cam allweddol eraill, Nid yw algorithm hwn yn cael ei logio n grisiau. 880 00:39:46,300 --> 00:39:48,992 Pe bai'n cael dim ond logio n grisiau, fyddem yn yr un broblem 881 00:39:48,992 --> 00:39:51,200 fel o'r blaen lle nad oes modd i ni fod yn yn siwr bod popeth yn didoli. 882 00:39:51,200 --> 00:39:54,480 Mae'n rhaid i chi edrych cyn lleied â phosibl ar elfennau n i fod yn sicr n elfennau yn cael eu datrys, 883 00:39:54,480 --> 00:39:55,950 fel arall mae'n naid o ffydd. 884 00:39:55,950 --> 00:39:59,810 >> Felly mae'n log n camau cyn lleied â phosibl, ond beth am y cam uno allweddol 885 00:39:59,810 --> 00:40:04,370 lle dwi'n uno fy hanner chwith a'r dde hanner ac yn cerdded ar draws y llwyfan? 886 00:40:04,370 --> 00:40:06,980 Faint o gamau yw bod i uno? 887 00:40:06,980 --> 00:40:10,150 Mae'n n, ond doeddwn i ddim yn unig uno y tro olaf. 888 00:40:10,150 --> 00:40:15,089 Ar bob un o'r rhai galwadau yn nythu, ar bob o'r rhai yn uno nythu, yr wyf yn dal didoli. 889 00:40:15,089 --> 00:40:18,380 Rwy'n unodd y ddau guys, yna dwy rhain guys, yna y ddau guys ac yn y blaen. 890 00:40:18,380 --> 00:40:19,955 >> Felly i ddim yn cyfuno unwaith eto, ac unwaith eto. 891 00:40:19,955 --> 00:40:20,580 Faint o weithiau? 892 00:40:20,580 --> 00:40:23,510 Felly, bob tro yr wyf yn rhannu'r rhestr yn ei hanner, fe wnes i uno. 893 00:40:23,510 --> 00:40:25,460 Rhannwch y rhestr yn ei hanner, yn gwneud yn uno. 894 00:40:25,460 --> 00:40:28,570 Felly os rannu'r rhestr gellir ei wneud amserau log n, 895 00:40:28,570 --> 00:40:33,880 a chyfuno'r yn y pen draw yn cymryd n grisiau, yr hyn a allai fod nawr yw'r uchaf 896 00:40:33,880 --> 00:40:37,000 rhwymo ar y gwaith o redeg adeg ein algorithm? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> Ac yn wir, dyna beth rydym wedi ei gyflawni yma. 899 00:40:40,560 --> 00:40:44,650 Felly mae'r teimlad eich bod yn gweld yn weledol pan y rhai tri pheth rhedeg ochr yn ochr 900 00:40:44,650 --> 00:40:47,930 yn sgwâr n erbyn n sgwario erbyn n log n. 901 00:40:47,930 --> 00:40:51,010 Pa sylfaenol byddwn yn gweld, nid yn unig heddiw, ond yn y dyfodol, 902 00:40:51,010 --> 00:40:52,760 yn llawer, llawer cyflymach. 903 00:40:52,760 --> 00:40:56,010 Mae rownd o gymeradwyaeth ar gyfer guys hyn, Byddaf yn eu gwobrwyo gyda pheli straen. 904 00:40:56,010 --> 00:41:00,260 Gadewch i ni ohirio yma heddiw, ac byddwn yn eich gweld ar ddydd Llun. 905 00:41:00,260 --> 00:41:02,255