>> [CHWARAE CERDDORIAETH]
DAVID Malan: Pob hawl.
Mae pob hawl, croeso yn ôl.
Felly, mae hyn yn Wythnos 4, y dechrau ohono, yn barod.
A byddwch yn cofio bod yr wythnos diwethaf, rydym yn rhoi codio neilltuo ar gyfer ychydig bach
ac yr ydym yn dechrau siarad ychydig yn fwy lefel uchel, am bethau fel
chwilio a didoli, sydd, er syniadau braidd yn syml, yn cael eu
cynrychiolydd o ddosbarth o broblemau byddwch yn dechrau i ddatrys arbennig
wrth i chi ddechrau meddwl am terfynol prosiectau ac atebion diddorol yr ydych
efallai y bydd rhaid i broblemau yn y byd go iawn.
Nawr fath swigen yn un o'r symlaf algorithmau o'r fath, ac mae'n
gweithio drwy gael niferoedd bach hyn mewn rhestr neu mewn math amrywiaeth o
swigen eu ffordd i fyny i ben, ac mae'r rhifau mawr yn symud eu ffordd i lawr i
ddiwedd y rhestr.
>> A dwyn i gof y gallem ddychmygu fath swigen ychydig
rhywbeth fel hyn.
Felly, gadewch i mi fynd yn ei flaen a chliciwch Start.
Rwyf wedi preselected fath swigen.
Ac os ydych yn cofio bod y glas dalach llinellau cynrychioli rhifau mawr, bach
llinellau glas yn cynrychioli rhifau bach, fel y inni fynd drwy hyn eto ac eto ac
unwaith eto, gan gymharu dau far nesaf i bob eraill mewn coch, rydyn ni'n mynd i gyfnewid y
mwyaf a'r lleiaf os eu bod allan o drefn.
>> Felly, bydd hyn yn mynd ymlaen ac yn mynd ymlaen ac yn mynd ymlaen, a byddwch yn gweld bod y mwy o faint
elfennau yn gwneud eu ffordd i'r iawn, ac elfennau llai yn
gwneud eu ffordd i'r chwith.
Ond rydym yn dechrau mesur effeithlonrwydd, y
ansawdd y algorithm hwn.
Ac rydym yn dweud bod yn y gwaethaf achos, cymerodd algorithm hwn
yn fras faint o gamau?
>> Felly n sgwâr.
A beth oedd yn n?
>> GYNULLEIDFA: Nifer o elfennau.
>> DAVID Malan: Felly n oedd y nifer o elfennau.
Ac felly byddwn yn gwneud hyn yn aml.
Unrhyw bryd rydym eisiau siarad am faint o broblem neu faint o
mewnbwn, neu faint o amser mae'n ei gymryd i gynhyrchu cynnyrch, byddwn ni yn unig
gyffredinol beth bynnag mewnbwn fel n.
Felly, yn ôl yn Wythnos 0, tudalennau y nifer yn y llyfr ffôn yn n.
Mae nifer y myfyrwyr yn yr ystafell yn n.
Felly yma, hefyd, rydym yn dilyn y patrwm hwnnw.
>> Nawr n sgwâr nad ydynt yn arbennig o gyflym, felly rydym yn ceisio ei wneud yn well.
Ac felly rydym yn edrych ar un neu ddau o algorithmau eraill, ymhlith y
yn fath dethol.
Felly fath dethol yn ychydig yn wahanol.
Yr oedd bron yn symlach, mentraf ddweud, lle dechreuais ar ddechrau'r
rhestr o'n gwirfoddolwyr a Fi jyst eto ac eto ac eto yn mynd drwy
y rhestr, pluo y lleiaf elfen ar y tro a rhoi iddo ef neu
hi ar ddechrau'r rhestr.
>> Ond mae hyn, hefyd, ar ôl i ni ddechrau meddwl trwy y math ac yn fwy
llun, meddwl am faint o weithiau Yr wyf yn mynd yn ôl ac ymlaen ac yn ôl
ac ymlaen, yr ydym yn dweud yn yr achos gwaethaf, fath dethol, hefyd, oedd yr hyn?
n sgwario.
Nawr yn y byd go iawn, y gallai mewn gwirionedd ychydig yn gyflymach.
Oherwydd unwaith eto, nid oedd rhaid i mi gadw camu'n ôl ar ôl i mi wedi datrys y
elfennau lleiaf.
Ond os ydym yn meddwl am n fawr iawn, ac os ydych yn fath o wneud y cwestiwn yn
Wnes i ar y bwrdd, gyda'r n sgwâr rhywbeth minws, popeth arall
ar wahân i'r n sgwâr, unwaith n yn mynd yn wirioneddol fawr, nid yw'n
wirioneddol bwysig cymaint.
Felly, fel gwyddonwyr cyfrifiadur, rydym yn datrys y troi llygad dall i'r llai
ffactorau ac yn canolbwyntio yn unig ar y ffactor yn mynegiant mae hynny'n mynd i wneud
y gwahaniaeth mwyaf.
>> Wel, yn olaf, rydym yn edrych ar y math gosod.
Ac mae hyn yn debyg o ran ysbryd, ond yn hytrach na mynd trwy iteraidd a
dewis yr elfen lleiaf un ar y pryd, yr wyf yn hytrach yn cymryd y llaw fy mod
Deliwyd, a phenderfynais, pob gywir, rydych yn perthyn yma.
Yna mi symud ymlaen i'r elfen nesaf ac wedi penderfynu ei fod ef neu
hi yn perthyn yma.
Ac yna symudais ymlaen ac ymlaen.
Ac yr wyf yn gallai i, ar hyd y ffordd, symud guys hyn er mwyn
gwneud lle ar eu cyfer.
Felly dyna oedd y math o gwrthdroad meddwl o'r fath dethol ein bod yn
Gelwir fath gosod.
>> Felly, y pynciau hyn i ddigwydd yn y byd go iawn.
Dim ond ychydig flynyddoedd yn ôl, pan benodol Roedd seneddwr yn rhedeg am llywydd,
Eric Schmidt, ar yr adeg y Prif Swyddog Gweithredol Google, wedi cael y cyfle mewn gwirionedd
i gyfweld ag ef.
Ac rydym yn meddwl y bydden ni'n rhannu hyn YouTube clip i chi yma, pe gallem droi i fyny
y gyfrol.
>> [VIDEO Playback]
>> -Yn awr, Seneddwr, eich bod yma yn Google, ac yr wyf yn hoffi meddwl am y llywyddiaeth
fel cyfweliad am swydd.
>> [Chwerthin]
>> -Nawr mae'n anodd cael swydd fel llywydd.
A ydych yn mynd trwy y llymder awr.
Mae hefyd yn anodd i gael swydd yn Google.
Mae gennym gwestiynau ac rydym yn gofyn ein cwestiynau ymgeiswyr.
Ac mae hyn yn un yn dod o Larry Schwimmer.
>> [Chwerthin]
-Rydych guys yn meddwl fy mod i'n kidding?
Mae'n iawn yma.
Beth yw'r ffordd fwyaf effeithlon o didoli miliwn o gyfanrifau dau-bit?
>> [Chwerthin]
>> -Wel, uh -
>> -I'm ddrwg.
Efallai dylem -
>> -Na, na, na, na, na.
>> -Nad yw 'na -
OK.
>> -Rwy'n credu y byddai'r math swigen yn y ffordd anghywir i fynd.
>> [Chwerthin]
>> [Bloeddio a chymeradwyaeth]
>> -Dewch ar, a ddywedodd wrtho hyn?
OK.
>> [VIDEO END Playback]
>> DAVID Malan: Felly dyna ni.
Felly, rydym yn dechrau mesur y rhain yn rhedeg adegau, fel petai, gyda rhywbeth
a elwir yn nodiant asymptotic, sydd yn dim ond cyfeirio at ein math o droi
llygad dall i'r rhai ffactorau llai ac ond yn edrych ar yr amser yn rhedeg,
perfformiad o algorithmau hyn, fel n mynd yn wirioneddol fawr dros gyfnod o amser.
Ac felly rydym yn cyflwyno O. mawr a mawr O rhywbeth cynrychioli ein bod yn meddwl
o fel rhwymo uchaf.
Ac mewn gwirionedd, y Barri, gallwn ostwng na'r mic ychydig?
>> Roeddem yn meddwl o hyn yn rhwymo uchaf.
O mor fawr o n golygu sgwâr, mewn yr achos gwaethaf, rhywbeth fel
Byddai fath dewis cymryd n camau sgwâr.
Neu rywbeth fel math gosod Byddai n camau sgwâr.
Nawr am rywbeth fel gosod fath, beth oedd yr achos gwaethaf?
O ystyried amrywiaeth, beth yw'r gwaethaf senario posibl a allai fod yn
eich hun yn wynebu?
>> Mae'n hollol yn ôl, dde?
Oherwydd os yw'n gwbl yn ôl, rhaid i chi wneud llawer iawn o waith.
Oherwydd os ydych yn gyfan gwbl yn ôl, ydych yn mynd i ddod o hyd i'r
elfen fwyaf yma, er bod mae'n perthyn i lawr yno.
Felly, rydych chi'n mynd i ddweud, iawn, yn hyn o bryd, rydych yn perthyn yma,
fel eich bod yn gadael ei ben ei hun.
>> Yna byddwch yn sylweddoli, oh, damn, rhaid i mi symud yr elfen hon ychydig yn llai i
y chwith i chi.
Yna rhaid i mi wneud hynny eto ac eto ac eto.
Ac os wyf yn cerdded yn ôl ac ymlaen, yr ydych yn Byddai datrys o deimlo perfformiad
y algorithm, oherwydd gyson ydw i shuffling pawb arall i lawr yn y
amrywiaeth i wneud lle ar ei gyfer.
Felly dyna'r achos gwaethaf.
>> Ar y llaw arall -
ac roedd hyn yn Cliffhanger tro diwethaf -
Dywedodd ein bod math mewnosod yn omega o beth?
Beth yw'r redeg orau-achos amser o'r fath gosod?
Felly mae'n n mewn gwirionedd.
Dyna oedd y wag ein bod yn gadael ar y bwrdd tro diwethaf.
>> Ac mae'n omega n oherwydd pham?
Wel, yn yr achos gorau, beth fath gosod yn mynd i gael ei drosglwyddo?
Wel, rhestr sy'n cael ei datrys yn llwyr eisoes, mae gwaith ychydig iawn i'w wneud.
Ond yr hyn sy'n daclus am y math gosod yw ei fod oherwydd ei fod yn cychwyn yma a
penderfynu, oh, yr ydych yn y nifer un, rydych yn perthyn yma.
O, beth ffortiwn da.
>> Rydych yn rhif dau.
Rydych hefyd yn perthyn yma.
Rhif tri, hyd yn oed yn well, ydych yn perthyn yma.
Cyn gynted ag y mae'n mynd i ddiwedd y pseudocode rhestr, fesul mewnosod fath yn
ein bod yn cerdded trwy lafar tro diwethaf, mae'n ei wneud.
Ond didoli dewis, ar y llaw arall, cadw gwneud beth?
>> Cadw mynd drwy'r rhestr eto ac eto ac eto.
Oherwydd bod y mewnwelediad allweddol nad oedd ond unwaith y byddwch wedi edrych yr holl ffordd at y
ddiwedd y rhestr, gallwch fod yn sicr bod yr elfen a ddewiswyd gennych oedd
yn wir yr elfen lleiaf ar hyn o bryd.
Felly mae'r rhain modelau meddyliol gwahanol diwedd i fyny cynhyrchu rhai byd go iawn iawn
gwahaniaethau i ni, yn ogystal â'r gwahaniaethau asymptotic damcaniaethol.
>> Felly, dim ond i ailadrodd, yna, mawr O n sgwâr, rydym wedi gweld rhai o'r fath
algorithmau hyd yn hyn.
O Big n?
Beth 'an algorithm a allai gellir dweud i fod yn fawr O o n?
Yn yr achos gwaethaf, mae'n cymryd nifer llinol o gamau.
>> OK, chwiliad llinol.
Ac yn yr achos gwaethaf, ble mae'r elfen rydych yn chwilio amdano wrth
cymhwyso chwiliad llinol?
>> OK, yn yr achos gwaethaf, nid yw hyd yn oed yno.
Neu yn yr ail achos gwaethaf, mae'n yr holl ffordd yn y diwedd, sydd yn
plus-neu-minws gwahaniaeth un-cam.
Felly, ar ddiwedd y dydd, gallwn ddweud ei fod yn llinol.
Byddai O Big n fod chwiliad llinol, oherwydd yn yr achos gwaethaf, y
Nid yw hyd yn oed yn elfen yno neu ei fod yn yr holl ffordd ar y diwedd.
>> Wel, mawr O o log o n.
Doedden ni ddim yn siarad yn fanwl iawn am hyn, ond yr ydym wedi gweld hyn o'r blaen.
Beth sydd yn rhedeg mewn hyn a elwir yn logarithmig amser, yn yr achos gwaethaf?
>> Yeah, search mor deuaidd.
Ac chwiliad deuaidd yn yr achos gwaethaf gallai fod yr elfen rhywle yn
y canol, neu rywle y tu mewn i'r amrywiaeth.
Ond dim ond yn ei chael yn ôl i chi rhannwch y rhestr yn ei hanner, yn
hanner, yn ei hanner, yn ei hanner.
Ac yna voila, ei fod yno.
Neu eto, achos gwaethaf, nid yw hyd yn oed yno.
Ond nid ydych yn gwybod nad ei fod yno nes i chi math o cyrraedd y diwethaf
gwaelod-y rhan fwyaf o elfennau drwy haneru a haneru a haneru.
>> Big O o 1.
Felly, gallem mawr O o 2, mawr O o 3.
Anytime ydych am dim ond rhif gyson, rydym yn unig didoli o ychydig symleiddio
bod mor fawr O o 1.
Hyd yn oed er os realistig, mae'n cymryd 2 neu hyd yn oed 100 o gamau, os yw'n
nifer cyson o gamau, rydym yn unig dweud O fawr o 1.
Beth 'an algorithm sy'n yn fawr O 1?
>> GYNULLEIDFA: Dod o hyd i'r hyd o newidyn.
>> DAVID Malan: Dod o hyd i'r hyd o newidyn?
>> GYNULLEIDFA: Na, hyd os caiff ei datrys yn barod.
>> DAVID Malan: Da.
Iawn, felly dod o hyd i'r darn o rywbeth os yw hyd y rhywbeth, fel
amrywiaeth, yn cael ei storio mewn rhai amrywiol.
Oherwydd y gallwch jyst ddarllen y newidyn, neu argraffwch y newidyn, neu
dim ond yn gyffredinol gael mynediad i'r amrywiol.
Ac voila, sy'n cymryd amser cyson.
>> Ar y llaw arall, yn meddwl yn ôl y safon.
Meddyliwch yn ôl at yr wythnos gyntaf o C, galw yn unig printf ac argraffu
rhywbeth ar y sgrîn yn dadlau cysonyn amser, gan ei fod yn cymryd dim ond
ryw nifer o gylchoedd CPU i ddangos bod y testun ar y sgrin.
Neu aros - a yw'n?
Ym mha ffordd arall y gallem fodelu'r perfformiad printf?
A fyddai rhywun yn hoffi i anghytuno, bod efallai nad yw'n amser iawn gyson?
Ym mha ystyr y gallai printf yn rhedeg amser, mewn gwirionedd argraffu llinyn ar
y sgrin, fod yn rhywbeth heblaw gyson.
>> GYNULLEIDFA: [Anghlywadwy].
>> DAVID Malan: Yeah.
Felly, mae'n dibynnu ar ein safbwynt.
Os ydym mewn gwirionedd yn meddwl am y mewnbwn i printf fel y llinyn, ac
Felly, rydym yn mesur faint y mewnbwn gan ei hyd - felly gadewch i ni alw
y darn hwnnw n hefyd -
gellid dadlau, printf ei hun O fawr o n oherwydd ei fod yn mynd i fynd â chi n camau
i argraffu pob un o'r n cymeriadau, yn fwyaf tebygol.
O leiaf i'r graddau ein bod yn cymryd yn ganiataol bod efallai ei fod yn defnyddio ar gyfer dolen
o dan y cwfl.
>> Ond byddai'n rhaid inni edrych ar hynny codio i ddeall yn well.
Ac yn wir, ar ôl i chi guys yn dechrau dadansoddi eich algorithmau eich hun, byddwch yn
llythrennol yn gwneud hynny.
Math o belen y llygad eich cod a meddwl am - i gyd yn iawn, mae gen i ddolen hon
yma neu gen i ddolenni nythu yma, mae hynny'n mynd i wneud pethau n n adegau,
a allwch chi ddatrys y rheswm eich ffordd drwy'r cod, hyd yn oed os yw'n
pseudocode ac nid cod gwirioneddol.
>> Felly beth am omega n sgwâr?
Beth oedd algorithm bod yn y gorau achos, yn dal i gymryd camau n sgwâr?
Yeah?
>> GYNULLEIDFA: [Anghlywadwy].
>> DAVID Malan: math dethol So.
Oherwydd yn y broblem honno mewn gwirionedd ostwng at y ffaith hynny eto, nid wyf yn gwybod
Rwyf wedi dod o hyd y lleiaf ar hyn o bryd hyd nes y Rwyf wedi gwirio pob un o'r elfennau darn.
Felly omega o, dyweder, n, yr ydym yn yn unig yn dod o hyd i un.
Mewnosod fath.
Os yw'r rhestr yn digwydd i gael eu datrys eisoes, yn yr achos gorau rydym yn unig wedi
i wneud un basio drwyddo, a phryd rydym yn sicr.
Ac yna y gellid ei ddweud i fod yn llinol, yn sicr.
>> Beth am omega o 1?
Beth, yn yr achos gorau, efallai y bydd yn cymryd nifer cyson o gamau?
Chwilio Felly llinol, os ydych yn unig yn cael lwcus a'r elfen rydych yn chwilio
yn iawn ar ddechrau'r y rhestr, os dyna lle rydych yn dechrau eich
llinol groesi o'r rhestr.
>> Ac mae hyn yn wir am nifer o bethau.
Er enghraifft, hyd yn oed deuaidd Chwilio yn omega o 1.
Oherwydd yr hyn os ydych yn cael 'n sylweddol darn lwcus ac smack-lleden yng nghanol
eich amrywiaeth yw nifer rydych yn chwilio amdano?
Felly, gallwch gael lwcus yno, yn ogystal.
>> Mae hyn yn un, yn olaf, omega o log n n.
Felly n log n, ni wnaethom mewn gwirionedd siarad am hyd yn hyn, ond -
>> GYNULLEIDFA: Cyfuno fath?
>> DAVID Malan: Cyfuno fath.
Dyna oedd y Cliffhanger y tro diwethaf, os yw'r cynnig byddwn ni, a dangos ein
golwg, bod algorithmau.
Ac uno math o dim ond un fath algorithm sydd yn y bôn yn gyflymach
na rhai o'r rhain yn guys eraill.
Yn wir, uno byr yn cael ei nid yn unig yn y achos gorau n n log, yn y gwaethaf
achos n n log.
A phan fyddwch yn cael cyd-ddigwyddiad hwn o omega ac O mawr yn yr un peth?
Gallwn mewn gwirionedd yn disgrifio hynny fel hyn sy'n enw theta, er ei fod yn
ychydig yn llai cyffredin.
Ond mai dim ond yn golygu y ddwy ffiniau, yn yr achos hwn, yr un fath.
>> Felly uno fath, beth mae hyn yn wir berwi i lawr i i ni?
Wel, dwyn i gof y cymhelliant.
Gadewch i mi dynnu i fyny animeiddio arall ni wnaethom edrych ar y tro diwethaf.
Mae hyn yn un, yr un syniad, ond mae'n ychydig yn fwy.
Ac yr wyf i'n mynd i fynd yn ei flaen ac yn tynnu sylw at cyntaf - mae gennym fath gosod ar
y chwith uchaf, yna fath dethol, fath swigen, ychydig o mathau eraill -
cregyn ac yn gyflym - nad ydym wedi siarad am, a tomen a chyfuno fath.
>> Felly, o leiaf yn ceisio canolbwyntio eich llygaid ar y tri uchaf ar y chwith, ac yna
uno fath pan fyddaf yn clicio saeth werdd yma.
Ond byddaf yn gadael pob un ohonynt yn rhedeg, dim ond i rhoi ymdeimlad o amrywiaeth i chi
algorithmau sy'n bodoli yn y byd.
Rydw i'n mynd i adael i redeg hwn am ddim ond ychydig o eiliadau.
Ac os byddwch yn canolbwyntio eich llygaid - yn ddewis algorithm, yn canolbwyntio arno am ddim ond
eiliad - byddwch yn dechrau gweld y batrwm ei fod yn gweithredu.
>> Cyfuno fath, hysbysiad, yn cael ei wneud.
Fath Heap, didoli cyflym, cragen -
felly mae'n ymddangos cyflwynwyd y tair algorithmau gwaethaf yr wythnos diwethaf.
Ond mae hynny'n dda ein bod ni yma heddiw i edrych ar uno didoli, sy'n un o
y rhai yn haws yw edrych ar, hyd yn oed er ei bod yn debyg y bydd yn plygu eich meddwl
dim ond ychydig bach.
Yma, gallwn weld yn union faint o fath dethol sucks.
>> Ond ar y llaw arall, mae'n hawdd iawn i'w gweithredu.
Ac efallai ar gyfer P Set 3, dyna un o'r algorithmau dewis i chi i weithredu
ar gyfer y rhifyn safonol.
Berffaith iawn, yn berffaith gywir.
>> Ond unwaith eto, fel n mynd yn fawr, os ydych yn dewis i weithredu algorithm gyflymach
hoffi uno didoli, groes yn yn fwy ac mewnbynnau mwy, eich cod yn unig
mynd i redeg yn gyflymach.
Eich gwefan yn mynd i weithio'n well.
Eich defnyddwyr yn mynd i fod yn hapusach.
Ac felly mae effeithiau hyn o roi mewn gwirionedd
ni rai feddwl yn ddyfnach.
>> Felly, gadewch i ni edrych ar yr hyn uno fath mewn gwirionedd yn ei olygu.
Y peth oera yw bod uno fath yw hyn yn unig.
Mae hyn, unwaith eto, yr hyn yr ydym wedi galw pseudocode, Bod pseudocode
Cystrawen Saesneg-debyg.
Ac mae'r symlrwydd yn math o ddiddorol.
>> Felly, ar fewnbwn n elfennau - fel y yn unig yn golygu, dyma arae.
'I' got n bethau ynddo.
Dyna'r cyfan yr ydym yn ei ddweud yno.
>> Os yw n yn llai na 2, yn dychwelyd.
Felly, dyna yn union yr achos dibwys.
Os yw n yn llai na 2, yna yn amlwg mae'n 1 neu 0, ac yn yr achos y peth
eisoes yn didoli neu ddim yn bodoli, felly dim ond dychwelyd.
Does dim byd i'w wneud.
Felly, mae hynny'n achos syml i tyn i ffwrdd.
>> Else, mae gennym tri cham.
Ddatrys y hanner chwith y elfennau, didoli yr hanner dde o'r elfennau,
ac yna uno haneri didoli.
Beth sy'n ddiddorol yma yw bod Rwy'n fath o punting, dde?
Mae fath o ddiffiniad cylchlythyr i algorithm hwn.
Ym mha ystyr yn algorithm hwn cylchlythyr diffiniad?
>> GYNULLEIDFA: [Anghlywadwy].
>> DAVID Malan: Yeah, fy algorithm didoli, dau o'i gamau yn cael eu "math
rhywbeth. "Ac er mwyn codi'r cwestiwn, wel, beth ydw i'n mynd i ddefnyddio
i ddatrys yr hanner chwith a'r hanner cywir?
A harddwch yma yw bod hyd yn oed er Unwaith eto, mae hyn yn y meddwl-blygu
rhan o bosibl, gallwch ddefnyddio un algorithm i ddatrys yr hanner chwith.
>> Ond arhoswch funud.
Pan fyddwch yn cael gwybod i ddatrys y chwith hanner, beth yw'r ddau
grisiau yn mynd i fod yn nesaf?
Byddwn yn datrys y hanner chwith y hanner chwith a'r dde
hanner yr hanner chwith.
Damn, sut ydw i'n trefnu dau y rhai hanner, neu chwarter, yn awr?
>> Ond mae hynny'n iawn.
Mae gennym algorithm didoli yma.
A hyd yn oed er efallai y byddwch yn poeni am cyntaf yn fath o anfeidrol
ddolen, mae'n gylch sy'n byth yn mynd i orffen - mae'n mynd i
dod i ben ar ôl beth sy'n digwydd?
Unwaith n yn llai na 2.
Yn y pen draw yn mynd i ddigwydd, oherwydd os ydych yn cadw haneru a
haneru yn haneru haneri hyn, yn sicr yn y pen draw ydych yn mynd i ben
i fyny gyda dim ond 1 neu 0 elfen.
Ar y pwynt, algorithm hwn dweud eich bod yn ei wneud.
>> Felly, y hud go iawn yn y algorithm yn ymddangos i fod yn
y cam olaf, uno.
Mae hynny'n syniad syml dim ond uno dau bethau, dyna beth sy'n digwydd yn y pen draw
i'n galluogi i drefnu amrywiaeth o, gadewch i ni ddweud, wyth elfen.
Felly, yr wyf wedi wyth beli straen yn fwy i fyny yma, mae wyth darn o bapur, ac un
Google Gwydr -
yr wyf yn cael eu cadw.
>> [Chwerthin]
>> DAVID Malan: Pe gallem gymryd wyth gwirfoddolwyr, a gadewch i ni weld os gallwn
chwarae y tu allan, felly.
Wow, OK.
Gwyddoniaeth gyfrifiadurol yn cael hwyl.
Mae pob hawl.
Felly beth am i chi dri, llaw mwyaf i fyny yno.
Pedwar yn y cefn.
A beth am y byddwn yn ei wneud i chi tri yn y rhes hon?
A phedwar yn y blaen.
Felly rydych yn wyth, yn dod ar i fyny.
>> [Chwerthin]
>> DAVID Malan: Rwy'n mewn gwirionedd ddim yn siŵr beth ydyw.
A yw'n y peli straen?
Mae'r lampau desg?
Mae'r deunydd?
Mae'r rhyngrwyd?
>> OK.
Felly dewch ar i fyny.
Pwy fyddai'n hoffi -
dal i ddod i fyny.
Gadewch i ni weld.
Ac mae hyn yn eich rhoi yn y lleoliad -
eich bod yn y lleoliad un.
Uh-oh, arhoswch funud.
1, 2, 3, 4, 5, 6, 7 - oh, yn dda.
Mae pob hawl, rydym yn dda.
Mae pob hawl, fel bod pawb yn cael sedd, ond nid ar y Glass Google.
Gadewch i mi i ciw hyn i fyny.
Beth yw eich enw?
>> MICHELLE: Michelle.
>> DAVID Malan: Michelle?
Mae pob hawl, byddwch yn cael i edrych fel y geek, os yw hynny'n iawn.
Wel, yr wyf yn ei wneud hefyd, mae'n debyg, am ddim ond ennyd.
Mae pob hawl, 'standby'.
Rydym wedi bod yn ceisio dod o hyd i achos dros ddefnyddio Google Glass, ac rydym yn
yn meddwl y byddai'n hwyl i ychydig wneud hwn pan fydd pobl yn llwyfan.
Byddwn yn cofnodi y byd o'u safbwynt hwy.
Mae pob hawl.
Nid yw yn ôl pob tebyg yr hyn Google fwriadwyd.
Mae pob hawl, os nad oes gwahaniaeth gennych wisgo hwn am y cofnodion lletchwith nesaf,
byddai hynny'n wych.
>> Mae pob hawl, felly mae gennym yma amrywiaeth o elfennau, a bod amrywiaeth, yn unol â'r
darnau o bapur yn y Folks hyn ' dwylo, yn cael ei heb eu didoli ar hyn o bryd.
>> MICHELLE: O, mor rhyfedd.
>> DAVID Malan: Mae 'n bert lawer ar hap.
Ac mewn dim ond hyn o bryd, rydym yn mynd i roi cynnig i weithredu uno fath at ei gilydd
a gweld ble y mewnwelediad allweddol yw.
Ac mae'r tric yma gyda uno fath yn rhywbeth nad ydym wedi cymryd yn ganiataol eto.
Rydym mewn gwirionedd angen rhywfaint o gofod ychwanegol.
Felly beth sy'n mynd i fod yn arbennig o ddiddorol am hyn yw bod y rhain
guys yn mynd i symud o gwmpas ychydig bit, oherwydd fy mod i'n mynd i gymryd yn ganiataol bod
mae 'na amrywiaeth ychwanegol o le, ddweud, dde y tu ôl iddynt.
>> Felly, os ydyn nhw y tu ôl i'w gadair, dyna yr amrywiaeth uwchradd.
Os ydynt yn eistedd yma, dyna yr amrywiaeth cynradd.
Ond mae hyn yn adnodd sydd gennym Nid leveraged hyd yma gyda swigen
fath, gyda'r math dethol, gyda'r math fewnosod.
Dwyn i gof yr wythnos diwethaf, mae pawb yn unig math o cymysgu yn eu lle.
Doedden nhw ddim yn defnyddio unrhyw cof ychwanegol.
Rydym yn gwneud lle i bobl drwy symud pobl o gwmpas.
>> Felly mae hwn yn gipolwg allweddol, hefyd.
Mae y fasnach-off, yn gyffredinol yn gwyddoniaeth gyfrifiadurol, o adnoddau.
Os ydych am i gyflymu'r broses o rywbeth fel amser, rydych chi'n mynd i
rhaid i chi dalu pris.
Ac un o'r prisiau hynny yn aml iawn gofod, maint y cof neu'r caled
lle ar y ddisg eich bod yn defnyddio.
Neu, a dweud y gwir, y swm o amser rhaglennydd.
Faint o amser mae'n ei gymryd i chi, y dynol, i mewn gwirionedd yn gweithredu rhai mwy
algorithm cymhleth.
Ond ar gyfer heddiw, y fasnach-off yn amser a gofod.
>> Felly, pe gallech guys dim ond yn dal i fyny eich niferoedd er mwyn i ni weld eich bod chi'n
yn wir cyfateb 4, 2, 6, 1, 3, 7, 8.
Ardderchog.
Felly, yr wyf i'n mynd i geisio drefnu'r pethau, gall os ydych yn guys yn unig
ddilyn fy arweiniad yma.
>> Felly, yr wyf yn mynd i weithredu, yn gyntaf, y Cam cyntaf y pseudocode, sydd yn
ar fewnbwn n elfennau, os yw n yn llai na 2, ac yna dychwelyd.
Yn amlwg, nid yw hynny'n yn gymwys, felly rydym yn symud ymlaen.
Felly ddatrys y hanner chwith y elfennau.
Felly mae hynny'n golygu fy mod i'n mynd i ganolbwyntio fy sylw am ychydig funudau'n ar y rhain
pedwar guys yma.
Mae pob hawl, beth ddylwn i ei wneud nesaf?
>> GYNULLEIDFA: Trefnwch y hanner chwith.
>> DAVID Malan: Felly, yn awr yn rhaid i mi ddatrys hanner chwith y guys hyn.
Oherwydd unwaith eto, cymryd yn ganiataol i chi eich hun y nod yw i ddatrys yr hanner chwith.
Sut ydych chi'n ei wneud hynny?
Dilynwch y cyfarwyddiadau, hyd yn oed er ein bod yn ei wneud eto.
Felly ddatrys yr hanner chwith.
Nawr rwy'n trefnu y ddau guys.
Beth sy'n dod nesaf?
>> GYNULLEIDFA: Trefnwch y hanner chwith.
>> DAVID Malan: Trefnwch y hanner chwith.
Felly, yn awr y rhain, y sedd yma, mae rhestr o faint 1.
A beth yw eich enw eto?
>> PRINCESS DAISY: Princess Daisy.
>> DAVID Malan: Princess Daisy yma.
Ac felly mae hi'n ei ddidoli yn barod, oherwydd y rhestr o faint 1.
Beth ddylwn i ei wneud nesaf?
OK, yn dychwelyd, gan fod y rhestr honno o maint 1, sy'n llai na 2.
Yna, beth yw'r cam nesaf?
Ac yn awr mae'n rhaid i chi fath o mynd yn ôl yn eich meddwl.
>> Trefnwch yr hanner cywir, sef -
beth yw eich enw?
>> LINDA: Linda.
>> DAVID Malan: Linda.
Ac felly beth ydym yn ei wneud yn awr bod mae gennym restr o faint 1?
>> GYNULLEIDFA: Ffurflen Dreth.
>> DAVID Malan: ofalus.
Byddwn yn dychwelyd yn gyntaf, ac yn awr y trydydd cam - ac os wyf yn fath o ddarlunio iddo gan
cofleidio'r ddwy sedd nawr, yn awr yr wyf rhaid iddynt gyfuno y ddwy elfen.
Felly, erbyn hyn yn anffodus, mae'r elfennau allan o drefn.
Ond dyna lle y broses uno yn dechrau cael anorchfygol.
>> Felly, pe gallech guys sefyll i fyny am ddim ond hyn o bryd, dw i'n mynd i angen i chi, mewn
hyn o bryd, i gamu y tu ôl i'ch cadair.
Ac os Linda, gan fod 2 llai na 4, pam na wnewch
byddwch yn dod o gwmpas yn gyntaf?
Aros yno.
Felly, Linda, byddwch yn dod o gwmpas yn gyntaf.
>> Nawr, mewn gwirionedd os mai dim ond arae gallem dim ond symud ei mewn amser real
o gadair hon i adnabod hwn.
Felly dychmygwch a gymerodd rhai cyson nifer o gamau 1.
Ac yn awr -
ond mae angen eich rhoi mewn y lleoliad cyntaf yma.
>> Ac yn awr pe baech yn dod o gwmpas, yn ogystal, rydym yn mynd i
fod yn y lleoliad dau.
A hyd yn oed er bod hyn yn teimlo fel ei fod yn cymryd ychydig o amser, beth braf yn awr yw
bod hanner chwith y chwith hanner yn cael ei ddatrys yn awr.
Felly beth oedd y cam nesaf, os ydym yn awr ailddirwyn ymhellach yn y stori?
>> GYNULLEIDFA: hanner Iawn.
>> DAVID Malan: Trefnwch y hanner cywir.
Felly, mae'n rhaid i chi guys i wneud hyn, yn ogystal.
Felly, pe baech yn sefyll i fyny am ddim ond hyn o bryd?
A beth yw eich enw?
>> JESS: Jess.
>> DAVID Malan: Jess.
Iawn, felly Jess yn awr y chwith hanner yr hanner cywir.
Ac felly mae hi'n rhestr o faint 1.
Amlwg hi didoli.
A'ch enw eto?
>> MICHELLE: Michelle.
>> DAVID Malan: Michelle yn amlwg restr o faint 1.
Mae hi wedi datrys eisoes.
Felly, yn awr y hud yn digwydd, y broses uno.
Felly, pwy sy'n mynd i ddod yn gyntaf?
Michelle yn amlwg.
Felly, pe gallech ddod o gwmpas yn ôl.
Mae'r gofod sydd gennym ar gael iddi nawr yn iawn y tu ôl i gadair hon yma.
Ac yn awr pe gallech ddod yn ôl hefyd, gennym yn awr, i fod yn glir, dau
haneri, pob un maint 2 -
a dim ond er mwyn darlun yn, os ydych yn allai wneud ychydig o le -
neb ar ôl hanner yma, un hanner i'r dde yma.
>> Ailddirwyn ymhellach yn y stori.
Beth yw cam nesaf?
>> GYNULLEIDFA: Cyfuno.
>> DAVID Malan: Felly, yn awr mae'n rhaid i ni uno.
Felly Iawn, felly nawr, diolch byth, rydym yn dim ond rhyddhau pedair cadair.
Felly, rydym wedi defnyddio ddwywaith cymaint o cof, ond gallwn roi fflip-flopping rhwng
y ddau arae.
Felly, pa rif yw i ddod yn gyntaf?
Felly, Michelle, yn amlwg.
Felly dod o gwmpas ac yn cymryd eich sedd yma.
Ac yna rhif 2 yn amlwg nesaf, felly yr ydych yn dod yma.
Rhif 4, rhif 6.
Ac eto, er bod yna ychydig bach o gerdded dan sylw,
mewn gwirionedd, gallai'r rhain ddigwydd yn syth, drwy symud un -
OK, chwarae yn dda.
>> [Chwerthin]
>> DAVID Malan: Ac yn awr rydym yn mewn cyflwr eithaf da.
Mae hanner chwith y cyfan mewnbwn bellach wedi ei ddatrys.
Mae pob hawl, felly guys hyn wedi y fantais o fy -
sut oedd yn y pen draw yr holl ferched ar y chwith a'r holl fechgyn ar y dde?
>> Iawn, felly 'guys droi yn awr.
Felly, ni fyddaf byddwch yn cerdded trwy camau hyn.
Byddwn yn gweld a allwn ailymgeisio yr un pseudocode.
Os ydych am fynd ymlaen a sefyll i fyny, ac rydych guys, gadewch i mi roi'r meic i chi.
Gwelwch os nad ydych yn gallu ailadrodd yr hyn rydym yn unig oedd yma ar y
ben arall y rhestr.
Pwy sydd angen i siarad yn gyntaf, yn seiliedig ar y algorithm?
Felly esbonio beth rydych chi'n ei wneud cyn byddwch yn gwneud unrhyw symudiadau droed.
>> SIARADWR 1: pob hawl, felly ers Fi yw hanner chwith y
chwith hanner, yn ol.
Iawn?
>> DAVID Malan: Da.
>> SIARADWR 1: Ac yna -
>> DAVID Malan: Pwy sy'n gwneud y meic yn mynd i'r nesaf?
>> SIARADWR 1: Nifer Nesaf.
>> SIARADWR 2: Felly, yr wyf fi yw'r hanner cywir yr hanner chwith y
chwith hanner, ac yn ol.
>> DAVID Malan: Da.
Byddwch yn dychwelyd.
Felly, yn awr beth sydd i fyny nesaf i chi ddau?
>> SIARADWR 2: Yr ydym am weld pwy yn llai.
>> DAVID Malan: Yn union.
Rydym yn awyddus i uno.
Mae'r gofod rydym yn mynd i ddefnyddio i uno chi i mewn, er eu bod yn
amlwg yn datrys eisoes, rydym yn mynd i ddilyn yr un algorithm.
Felly, sy'n mynd yn ôl yn gyntaf?
Felly 3, ac yna 7.
Ac yn awr y meic yn mynd i guys hyn, OK?
>> SIARADWR 3: Felly, yr wyf i'n hanner hawl y chwith hanner, ac mae fy n yn llai na
1, fel Im 'jyst yn mynd i basio -
>> DAVID Malan: Da.
>> SIARADWR 4: Rwy'n hanner hawl y hanner dde o'r hanner iawn, ac rwy'n
hefyd yn un person, felly rwy'n mynd i ddychwelyd.
Felly, yn awr rydym yn uno.
>> SIARADWR 3: Felly, rydym yn mynd yn ôl.
>> DAVID Malan: Felly, byddwch yn mynd i mewn i'r cefn.
Felly, 5 yn mynd yn gyntaf, ac yna 8.
Ac yn awr gynulleidfa, sef y gam yn rhaid i ailddirwyn nawr
yn ôl yn ein meddyliau?
>> GYNULLEIDFA: Cyfuno.
>> DAVID Malan: Cyfuno hanner ac i'r dde i'r chwith hanner yr hanner chwith gwreiddiol.
Felly, yn awr -
a dim ond er mwyn gwneud hyn yn glir, gwneud ychydig o ofod
rhyngoch chi ddau guys.
Felly nawr dyna'r ddwy restr, chwith ac i'r dde.
Felly, sut yr ydym yn awr yn cyfuno i chi guys i mewn i y rhes flaen y seddi eto?
>> 3 yn mynd yn gyntaf.
Yna, 5, yn amlwg.
Yna, 7, ac yn awr 8.
OK, ac yn awr rydym ni?
>> GYNULLEIDFA: Heb ei wneud.
>> DAVID Malan: Heb ei wneud, oherwydd yn amlwg, mae un cam ar ôl.
Ond unwaith eto, y rheswm rwy'n ei ddefnyddio hwn jargon fel "ailddirwyn yn eich meddwl,"
mae'n oherwydd dyna wir beth sy'n digwydd.
Rydym yn mynd drwy bob un o'r camau hyn, ond rydym yn fath o oedi ar gyfer
hyn o bryd, plymio ddyfnach i mewn i'r algorithm, gan oedi am eiliad,
plymio ddyfnach i mewn i'r algorithm, a erbyn hyn mae'n rhaid i ni drefnu o ailddirwyn yn ein
meddyliau a dadwneud pob un o'r haenau hyn ein bod wedi fath o gohirio.
>> Felly, erbyn hyn mae gennym dwy restr o faint 4.
Pe gallech guys sefyll i fyny am y tro olaf ac yn gwneud ychydig o le yma i
gwneud yn glir bod hyn yn y chwith hanner y gwreiddiol, y
hanner cywir o'r gwreiddiol.
Pwy yw'r rhif cyntaf ein bod yn angen i dynnu i mewn i gefn?
Michelle, wrth gwrs.
>> Felly, rydym yn rhoi Michelle yma.
Ac sydd â rhif 2?
Rhif 2 yn dod ar gefn hefyd.
Rhif 3?
Ardderchog.
Rhif 4, rhif 5, rhif 6, rhif 7, a rhif 8.
>> Iawn, felly roedd yn teimlo fel llawer o gamau, yn sicr.
Ond yn awr gadewch i ni weld os na allwn gadarnhau math o reddfol bod hyn yn
algorithm sylfaenol, yn enwedig gan n mynd yn wirioneddol fawr, fel yr ydym wedi gweld
gyda'r animeiddiadau, yn sylfaenol yn gyflymach.
Felly gallaf hawlio algorithm hwn, yn y gwaethaf achos a hyd yn oed yn yr achos gorau,
yn fawr O n amseroedd log n.
Hynny yw, mae rhywfaint o agwedd ar hyn algorithm sy'n cymryd camau n, ond
mae agwedd arall rhywle yn y iteriad, hynny dolennu, hynny
yn cymryd camau n log.
A allwn ni roi ein bys ar yr hyn y rhai ddau rif yn cyfeirio ato?
Wel, ble -
where'd y meic yn mynd?
>> SIARADWR 1: A fyddai'r log n yn torri ni i fyny yn ddau -
rhannu â dau, yn y bôn.
>> DAVID Malan: Yn union.
Unrhyw tro y byddwn yn gweld mewn unrhyw algorithm felly yn hyn, mae wedi bod yn y patrwm hwn o
rhannu, rhannu, rhannu.
Ac mae'n nodweddiadol ostwng i rywbeth sy'n
logarithmig, log sylfaen 2.
Ond gallai fod mewn gwirionedd fod yn unrhyw beth, ond logio sylfaen 2.
>> Nawr, beth am y n?
Gallaf weld ein bod yn fath o rannu eich guys - rhannu i chi, wedi ei rannu i chi,
rhannu i chi, wedi ei rannu i chi.
Lle mae'r diwedd yn dod o?
>> Felly mae'n cyfuno.
Oherwydd meddwl am y peth.
Pan fyddwch yn uno wyth o bobl at ei gilydd, lle mae hanner ohonynt yn set o bedwar
a'r hanner arall yn un arall set o bedwar, sut ydych chi'n mynd
ymwneud â gwneud y uno?
Wel, yr ydych yn guys yn gwneud hynny weddol reddfol.
>> Ond ychydig, os wyf yn hytrach yn gwneud yn fwy drefnus, efallai y byddwn wedi tynnu sylw at
y person leftmost cyntaf gyda fy chwith llaw, sylw at y ffaith ar y person leftmost
o bod hanner gyda fy llaw dde, a dim ond wedyn cerdded drwy'r
rhestr, gan dynnu sylw at yr elfen lleiaf bob tro, gan symud fy mys drosodd a
drosodd fel sydd ei angen drwy gydol y rhestr.
Ond yr hyn sy'n allweddol am y cyfuno broses yn Rwy'n cymharu parau hyn
o elfennau.
O hanner dde ac o'r chwith hanner, rwy'n byth yn gwrthgilio oddi unwaith.
>> Felly, mae'r uno ei hun yn cymryd dim mwy na n risiau.
A sawl gwaith oedd gen i i wneud hynny uno?
Wel, dim mwy na n, ac rydym yn unig yn gweld bod â'r uno terfynol.
Ac felly os ydych yn gwneud rhywbeth sy'n cymryd log n grisiau n amser, neu i'r gwrthwyneb,
mae'n mynd i roi i ni n amseroedd log n.
>> A pham mae hyn yn well?
Wel, os ydym eisoes yn gwybod bod log n yn well na n - iawn?
Gwelsom mewn chwiliad deuaidd, y llyfr ffôn enghraifft, roedd log n bendant
well na llinol.
Felly, mae hynny'n golygu n amseroedd log n yn bendant yn well na n gwaith arall
n, AKA n sgwâr.
A dyna beth rydym yn y pen draw yn teimlo.
>> Rownd mor fawr o gymeradwyaeth, os gallem, ar gyfer guys hyn.
>> [Cymeradwyaeth]
>> DAVID Malan: A'ch rhoddion rhaniad - efallai y byddwch yn cadw'r rhifau,
os hoffech.
Ac mae eich rhodd rhaniad, fel arfer.
O, a byddwn yn anfon y ffilm, Michelle.
Diolch yn fawr.
Mae pob hawl.
Helpu eich hun i bêl straen.
>> A gadewch i mi dynnu i fyny, yn y cyfamser, ein ffrind Rob Bowden i gynnig
bersbectif ychydig yn wahanol ar hyn, gan y gall eich barn chi am y rhain
camau yn digwydd mewn braidd gwahanol ffordd.
Mewn gwirionedd, mae'r set-up ar gyfer yr hyn Rob ymwneud â i ddangos i ni yn cymryd yn ganiataol bod rydym wedi
gwneud i fyny rannu y eisoes rhestr mawr yn wyth rhestrau bach,
pob un o faint 1.
>> Felly, rydym yn newid y pseudocode a ychydig bach yn unig i ddatrys o gyrraedd y
syniad craidd o sut y mae'r uno yn gweithio.
Ond mae'r amser yn rhedeg o'r hyn ei fod ar fin ei wneud yn dal i fod
mynd i fod yr un fath.
Ac eto, y set-up yma yw ei fod yn dechrau gydag wyth rhestrau o faint 1.
Felly, rydych wedi colli y rhan lle mae'n wneud mewn gwirionedd y log n, n log, log n
rannu y mewnbwn.
>> [VIDEO Playback]
>> -Dyna ni am gam un.
Ar gyfer cam dau, dro ar ôl tro uno parau o restrau.
>> DAVID Malan: EM.
Dim ond sain yn dod allan o fy nghyfrifiadur.
Gadewch i ni geisio eto.
>> -Dim ond fympwyol ddewis sydd - erbyn hyn mae gennym bedwar rhestrau.
Dysgu o'r blaen.
>> DAVID Malan: Dyna ni.
>> Cyfuno-108 a 15, rydym yn y pen i fyny â'r rhestr 15, 108.
Cyfuno 50 a 4, rydym yn y pen draw gyda 4, 50.
Cyfuno 8 a 42, rydym yn darfod i fyny ag 8, 42.
Ac uno 23 a 16 oed, rydym yn darfod i fyny ag 16, 23.
>> Nawr ein holl restrau o faint 2.
Sylwch fod pob un o'r pedair rhestr yn cael ei datrys.
Felly, gallwn ddechrau cyfuno parau o restrau eto.
Cyfuno 15 a 108 a 4 a 50, rydym yn gyntaf yn y 4, yna bydd y 15, yna
y 50, yna bydd y 108.
Cyfuno 8, 42 ac 16, 23, rydym yn cymryd yn gyntaf 8, yna bydd y 16, yna 23,
yna bydd y 42.
>> Felly, erbyn hyn rydym wedi dim ond dwy restr o faint 4, pob un ohonynt yn cael ei drefnu.
Felly nawr rydym yn cyfuno'r ddwy restr.
Yn gyntaf, rydym yn cymryd y 4, yna rydym yn cymryd y 8, yna rydym yn cymryd y 15, yna 16, yna
23, yna 42, yna 50, yna 108.
>> [VIDEO END Playback]
>> DAVID Malan: Unwaith eto, rhybudd, ef byth yn cyffwrdd gwpan cael mwy nag un amser
ar ôl symud ymlaen y tu hwnt iddo.
Felly, nad oedd erioed wedi ailadrodd.
Felly, mae'n bob amser yn symud i'r ochr, a dyna lle rydym yn cael ein n.
>> Beth am adael i mi dynnu i fyny un animeiddio a welsom yn gynharach, ond y tro hwn
canolbwyntio ar uno fath.
Gadewch i mi fynd yn ei flaen a chwyddo i mewn ar hyn yma.
Yn gyntaf gadewch i mi ddewis mewnbwn ar hap, chwyddo hyn, a gallwch ddatrys o weld
yr hyn a wnaethom yn ganiataol, yn gynharach, uno fath yn ei wneud mewn gwirionedd.
>> Felly, yn sylwi eich bod yn cael haneri hyn neu y chwarter neu wyth o'r rhain yn y
broblem yn sydyn dechrau cymryd siâp da.
Ac yna yn olaf, byddwch yn gweld yn y diwedd y bam,
popeth yn cael ei gyfuno gyda'i gilydd.
>> Felly mae'r rhain yn dim ond tri wahanol yn cymryd ar yr un syniad.
Ond mae'r mewnwelediad allweddol, yn union fel rhaniad a gorchfygu yn y dosbarth cyntaf,
oedd ein bod yn penderfynu i rhywsut rhannu y broblem yn rhywbeth mawr, i mewn
rhywbeth math o union yr un fath yn yr ysbryd, ond yn llai ac yn llai ac yn llai
ac yn llai.
>> Nawr ffordd hwyliog arall i ddatrys o feddwl am y rhain, er nad yw'n
mynd i roi yr un 'n athrylithgar i chi dealltwriaeth, yn
yr animeiddiad canlynol.
Felly, mae hwn yn rhywun fideo rhoi at ei gilydd a gysylltir gwahanol
synau gyda'r gwahanol gweithrediadau ar gyfer fath mewnosod, ar gyfer uno didoli, a
am ychydig o rai eraill.
Felly, mewn munud, dw i'n mynd i daro Chwarae.
Mae'n ymwneud munud o hyd.
A hyd yn oed er y gallwch ddal i weld y batrymau digwydd, y tro hwn gallwch
hefyd yn clywed sut y algorithmau hyn yn perfformio'n wahanol a chyda
batrymau ychydig yn wahanol.
>> Mae hyn yn fath gosod.
>> [Tones CHWARAE]
>> DAVID Malan: Mae'n eto yn ceisio i fewnosod pob elfen
i ble mae'n perthyn.
Mae hyn yn fath swigen.
>> [Tones CHWARAE]
>> DAVID Malan: A allwch chi ddatrys o deimlad sut mae cymharol ychydig o waith mae'n gwneud
ar bob cam.
Mae hyn yn beth tediousness swnio fel.
>> [Tones CHWARAE]
>> DAVID Malan: Mae hwn yn fath dethol, lle rydym yn dewis yr elfen ydym eisiau trwy
mynd trwy eto ac eto ac eto a'i roi ar y dechrau.
>> [Tones CHWARAE]
>> DAVID Malan: Mae hyn yn cyfuno math, sy'n gallwch chi wir yn dechrau teimlo.
>> [Tones CHWARAE]
>> [Chwerthin]
>> DAVID Malan: Rhywbeth o'r enw gnome fath, nad ydym wedi edrych ar.
>> [Tones CHWARAE]
>> DAVID Malan: Felly, gadewch i mi weld, yn awr, canolbwyntio ar y ffordd wrth i chi gobeithio bod gan y
cerddoriaeth, os gallaf lithro ychydig ychydig o cwestiwn yma.
Felly mae pedwerydd ffordd y gallwn meddwl am yr hyn y mae'n ei olygu hyn
swyddogaethau i fod yn gyflymach na rhai yr ydym wedi ei weld o'r blaen.
Ac os ydych yn dod ar y cwrs cefndir mathemateg, rydych yn
mewn gwirionedd yn gwybod efallai eich bod eisoes yn Gall slap tymor ar y dechneg hon -
sef recursion, rhaid i swyddogaeth hynny rywsut yn galw ei hun.
>> Ac eto, dwyn i gof bod uno math pseudocode yn ailadroddus yn yr ystyr
mai un o'r camau uno fath yn oedd i alw fath -
hynny yw, ei hun.
Ond diolch byth, oherwydd ein bod yn cadw galw didoli, neu gyfuno fath,
yn benodol, ar lai a llai a rhestr llai, yn y pen draw
gwaelod, diolch i'r hyn y byddwn yn galw achos sylfaenol, yr achos hard-coded bod
Dywedodd os yw'r rhestr yn fach, llai na 2 yn yr achos hwnnw, dim ond dychwelyd ar unwaith.
Os nad oedd gennym yr achos arbennig, y Ni fyddai algorithm gwaelod allan,
a byddech yn wir yn mynd i mewn i dolen ddiddiwedd wir am byth.
>> Ond mae'n debyg ein bod am roi yn awr rhai rhifau ar hyn, unwaith eto, gan ddefnyddio n
gan fod maint y mewnbwn.
Ac yr wyf yn awyddus i ofyn i chi, beth cyfanswm yr amser sy'n ymwneud â
rhedeg fath uno?
Neu yn fwy cyffredinol, beth y gost o mewn pryd?
>> Wel, mae'n eithaf hawdd i fesur hynny.
Os yw n yn llai na 2, yr amser dan sylw wrth ddidoli n elfennau,
lle mae n yn 2, yw 0.
Oherwydd ein bod yn unig yn dychwelyd.
Does dim gwaith i'w wneud o hyd.
Nawr gellir dadlau, efallai ei fod yn un cam neu ddau camau i chyfrif i maes faint o
gweithio, ond mae'n ddigon agos i 0 y Im 'jyst yn mynd i ddweud dim gwaith yn
angenrheidiol os y rhestr mor fach i anniddorol.
>> Ond yr achos hwn yn ddiddorol.
Mae'r achos recursive oedd y gangen o y pseudocode a ddywedodd arall, didoli
yr hanner chwith, ddatrys yr hawl hanner, uno'r ddau hanner.
Nawr, pam mae ymadrodd hwn cynrychioli'r gost?
Wel, T y n unig yn golygu y amser i ddatrys elfennau n.
Ac yna ar yr ochr dde-law y arwydd hafal yno, mae'r T n rhannu
gan 2 yn cyfeirio at y gost o beth?
Didoli yr hanner chwith.
Mae T arall n rhannu gan 2 cyfeirio yn ôl pob tebyg at y gost i
ddatrys yr hanner cywir.
>> Ac yna y plws n?
A yw'r uno.
Oherwydd os oes gennych dwy restr, un o maint n dros 2 ac un arall o faint n
dros 2, rhaid i chi gyffwrdd yn y bôn pob un o'r elfennau hynny, yn union fel Rob
cyffwrdd pob un o'r cwpanau, a dim ond wrth i ni nodwyd ym mhob un o'r
gwirfoddolwyr ar y llwyfan.
Felly, mae n yn y gost o uno.
>> Nawr yn anffodus, fformiwla hon hefyd yn ei hun yn recursive.
Felly, os gofynnir y cwestiwn, os n yw, dweud, 16, os oes 16 o bobl ar y llwyfan
neu 16 cwpan yn y fideo, faint o gyfanswm camau y mae'n ei gymryd i ddatrys eu
gyda uno fath?
Mae'n mewn gwirionedd nid yw'n ateb amlwg, oherwydd erbyn hyn mae'n rhaid i chi ddatrys y
recursively ateb y fformiwla hon.
>> Ond mae hynny'n iawn, oherwydd gadewch i mi gynnig ein bod yn gwneud y canlynol.
Mae'r amser dan sylw i ddatrys 16 o bobl neu 16 cwpan yn mynd i gael ei gynrychioli
gyffredinol fel T o 16.
Ond mae hynny'n gyfartal, yn ôl ein fformiwla blaenorol, 2 gwaith y swm
o amser mae'n ei gymryd i ddatrys 8 cwpan a 16.
Ac eto, yn ogystal â 16 yw'r amser i uno, ac mae'r ddau amseroedd T o 8 yw'r
amser i ddatrys chwith hanner a hanner i'r dde.
>> Ond unwaith eto, nid yw hyn yn ddigon.
Mae'n rhaid i ddeifio yn ddyfnach.
Mae hyn yn golygu bod rhaid i ateb y cwestiwn, beth yw T o 8?
Wel T o 8 yn unig 2 amseroedd T o 4 ac 8.
Wel, beth T o 4?
T o 4 yn unig 2 waith T o 2 a 4.
Wel, beth T o 2?
T o 2 yn unig 2 waith T o 1 a 2.
>> Ac eto, rydym yn fath o gael yn sownd yn y cylch hwn.
Ond mae'n ar fin cyrraedd y hyn a elwir yn achos sylfaenol.
Oherwydd yr hyn sy'n T o 1, gwnaethom hawlio?
0.
Felly nawr yn olaf, gallwn weithio tuag yn ôl.
>> 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
plwg yn 0 ar gyfer T o 1.
Felly, mae hynny'n golygu ei fod yn hafal i 2 gwaith sero, a elwir fel arall fel 0, a 2.
Ac felly y ceir yr ymadrodd cyfan yw 2.
>> Nawr, os wyf yn cymryd y T 2, y mae ei ateb yw 2, plwg i mewn i'r llinell ganol, T
o 4, sy'n rhoi 2 gwaith i mi 2 a 4, hynny 8.
Os yna rwyf yn plwg yn 8 i Ddeddf blaenorol lein, sy'n rhoi 2 gwaith 8, 16 i mi.
Ac os ydym wedyn yn parhau i hynny gyda'r 24, gan ychwanegu mewn 16, rydym o'r diwedd yn cael
werth o 64.
>> Nawr bod mewn ac o ei hun math o siarad ddim i nodiant n, y
O fawr, y omega a rydym wedi bod yn siarad am.
Ond mae'n troi allan bod 64 yn wir 16, mae'r maint y mewnbwn,
log sylfaen 2 o 16.
Ac os yw hyn yn ychydig yn anghyfarwydd, dim ond meddwl yn ôl, a bydd yn dod yn ôl
i chi yn y pen draw.
Os yw hyn yn sylfaen log 2, mae fel 2 godi i'r hyn sy'n rhoi 16 i chi?
O, dyna 4, felly mae'n 16 gwaith 4.
>> Ac eto, nid yw'n llawer mawr os yw hyn yn yn fath o gof niwlog awr.
Ond am y tro, yn cymryd ar ffydd fod 16 log 16 yw 64.
Ac felly yn wir, gyda'r bwyll syml gwirio, rydym wedi cadarnhau -
ond nid yn profi yn ffurfiol -
bod yr amser yn rhedeg o uno fath yn wir n mewngofnodi n.
>> Felly, nid drwg.
Mae'n bendant yn well na'r algorithmau rydym wedi gweld hyd yn hyn, a
mae'n oherwydd ein bod wedi ysgogi, un, techneg o'r enw recursion.
Ond yn fwy diddorol na hynny, bod syniad o rannu a concro.
Unwaith eto, yr wythnos wirioneddol 0 pethau sy'n hyd yn oed yn awr yn ailddigwydd mewn
ffordd fwy cymhellol.
>> Erbyn hyn, mae ymarfer ychydig o hwyl, os ydych wedi byth yn gwneud hyn - ac mae'n debyg y
Ni fyddai'n rhaid, oherwydd math o normal nad yw pobl yn meddwl i wneud hyn.
Ond os byddaf yn mynd i google.com ac os Rwyf am i ddysgu rhywbeth am
recursion, Enter.
>> [Chwerthin]
[Chwerthin MWY]
DAVID Malan: jôc drwg lledaenu yn araf.
[Chwerthin]
DAVID Malan: Rhag ofn, ei fod yno.
Doeddwn i ddim yn sillafu yn anghywir, ac mae 'y jôc.
Mae pob hawl.
Esbonio i'r bobl nesaf i chi os Nid yn gwbl wedi clicio eto.
Ond recursion, yn fwy cyffredinol, yn cyfeirio i'r broses o swyddogaeth galw
ei hun, neu yn fwy cyffredinol, rhannu a problem yn rhywbeth y gellir ei
datrys dameidiog drwy ddatrys union yr un fath problemau cynrychioliadol.
>> Newid gerau Wel, gadewch i ni am ddim ond ennyd.
Rydym yn hoffi i ben ar rai cliffhangers, felly gadewch i ni ddechrau i osod
y llwyfan, am sawl munud, ar syniad syml iawn -
hynny o gyfnewid dwy elfen, dde?
Mae pob un o'r algorithmau hyn, rydym wedi bod yn siarad am y cwpl yn y gorffennol
darlithoedd cynnwys rhai math o gyfnewid.
Heddiw, cafodd ei dychmygu drwy eu cael i fyny allan o'u cadeiriau a
cerdded o gwmpas, ond mewn cod, byddem yn dim ond yn cymryd elfen o un amrywiaeth
a sw n plopian i mewn i un arall.
>> Felly, sut rydym yn mynd ati i wneud hyn?
Wel, gadewch i mi fynd yn ei flaen ac ysgrifennu rhaglen hwylus yma.
Rydw i'n mynd i fynd yn ei flaen a gwneud hyn fel y canlynol.
Gadewch i ni yn galw hyn -
beth ydyn ni am i alw hyn yn un?
>> A dweud y gwir, dim.
Gadewch i mi ailddirwyn.
Nid wyf am wneud hynny Cliffhanger eto.
Bydd yn difetha'r hwyl.
Gadewch i ni wneud hwn yn lle.
>> Gadewch i ni dybio fy mod am i ysgrifennu ychydig rhaglen, ac sydd bellach yn cynnwys hyn
syniad o recursion.
Yr wyf yn fath o got blaen arnaf fy hun.
Rydw i'n mynd i wneud y canlynol.
>> Yn gyntaf, cyflym cynnwys o safon io.h, yn ogystal â cynnwys o cs50.h.
Ac yna yr wyf i'n mynd i fynd yn ei flaen a datgan int brif ddi-rym
yn y ffordd arferol.
Sylweddolais fy mod i wedi misnamed y ffeil, felly gadewch i mi ychwanegu estyniad c. yma fel
y gallwn lunio yn iawn.
Dechrau swyddogaeth hon i ffwrdd.
>> Ac mae'r swyddogaeth yr wyf am i ysgrifennu, yn eithaf yn syml, yn un sy'n gofyn y
defnyddiwr ar gyfer nifer ac wedyn yn ychwanegu i fyny holl rifau rhwng y
nifer a, dyweder, 0.
Felly, yn gyntaf yr wyf i'n mynd i fynd yn ei flaen a datgan n int.
Yna mi gopïo rhai cod sy'n rydym wedi defnyddio am gyfnod.
Er bod rhywbeth yn wir.
'N annhymerus' yn dod yn ôl at hynny mewn munud.
>> Beth ydw i am ei wneud?
Yr wyf am ddweud printf cadarnhaol cyfanrif gwelwch yn dda.
Ac yna yr wyf i'n mynd i dweud n cael cael int.
Felly, unwaith eto, mae rhai côd boilerplate ein bod wedi defnyddio o'r blaen.
Ac yr wyf i'n mynd i wneud hyn tra n yn llai nag 1.
Felly, bydd hyn yn sicrhau bod y defnyddiwr rhoi cyfanrif positif mi.
>> Ac yn awr yr wyf i'n mynd i wneud y canlynol.
Yr wyf am ychwanegu at yr holl o'r rhifau rhwng 1 a a n, neu 0 a n,
equivalently, i gael cyfanswm.
Felly, y symbol sigma mawr y gallai byddwch yn cofio.
Felly, yr wyf i'n mynd i wneud hyn drwy ffonio gyntaf swyddogaeth o'r enw sigma,
basio yn n, ac yna rwy'n mynd i dweud printf, yr ateb yn iawn yno.
>> Felly, yn fyr, yr wyf yn ei gael ac int gan y defnyddiwr.
Rwyf yn sicrhau ei fod yn gadarnhaol.
Yr wyf yn datgan ateb a elwir yn amrywiol o int math a storio ynddo y ffurflen
gwerth sigma, gan fynd yn n fel mewnbwn.
Ac yna yr wyf argraffu yr ateb hwnnw.
>> Yn anffodus, er bod sigma swnio'n fel rhywbeth a allai fod yn
y ffeil math.h, ei datganiad, mae'n mewn gwirionedd yn peidio.
Felly, mae hynny'n iawn.
Gallaf roi hyn ar waith fy hun.
Rydw i'n mynd i weithredu swyddogaeth o'r enw sigma, ac mae'n mynd i gymryd
paramedr -
gadewch i ni ei alw'n m, dim ond felly mae'n wahanol.
Ac yna i fyny yma, dw i'n mynd i ddweud, yn dda, os m yn llai na 1 - mae hyn yn
rhaglen anniddorol iawn.
Felly, yr wyf i'n mynd i fynd yn ei flaen a dychwelyd ar unwaith 0.
Mae'n nid yn unig yn gwneud synnwyr i ychwanegu at yr holl y rhifau rhwng 1 a m os m
ei hun yn 0 neu negyddol.
>> Ac yna yr wyf i'n mynd i fynd yn ei flaen a gwneud hyn yn iteraidd iawn.
Rydw i'n mynd i wneud y math hwn o hen-ysgol, ac yr wyf i'n mynd i fynd yn ei flaen
a dweud fy mod i'n mynd i datgan swm i fod yn 0.
Yna mi i'n mynd i gael a ar gyfer dolen int -
a gadewch i mi ei wneud i gyd-fynd ein cod dosbarthu, er mwyn i chi gael copi
yn y cartref. int i yn cael 1 ar hyd at i yn llai na neu'n hafal i m.
i yn ogystal a mwy.
Ac yna y tu mewn o hyn ar gyfer dolen -
rydym yn bron yno -
swm yn cael swm ac 1.
Ac yna dwi'n mynd i ddychwelyd y swm.
>> Felly, yr wyf yn gwneud hyn yn gyflym, eithaf cyfaddef.
Ond unwaith eto, y prif swyddogaeth 'n bert syml, yn seiliedig ar god rydym wedi
ysgrifenedig hyd yn hyn.
Yn defnyddio'r ddolen deuol i gael cadarnhaol int gan y defnyddiwr.
Yna yn trosglwyddo'r int i swyddogaeth newydd enw sigma, yn galw yn, unwaith eto, n.
Ac yr wyf yn storio gwerth gyfnewid, mae'r ateb o'r blwch du ar hyn o bryd
a elwir yn sigma, mewn newidyn a elwir yn ateb.
Yna mi ei hargraffu.
>> Os byddwn yn awr yn parhau y stori, sut mae sigma gweithredu?
Yr wyf yn bwriadu gweithredu fel a ganlyn.
Yn gyntaf, ychydig bach o wall-gwirio i wneud yn siŵr nad yw'r defnyddiwr yn
cyboli gyda mi ac yn pasio mewn rhywfaint o werth negyddol neu 0.
Yna mi ddatgan amrywiol o'r enw swm a'i osod i 0.
>> Ac yn awr yr wyf yn dechrau symud o hafal i 1 yr holl ffordd i fyny at ac yn cynnwys m,
oherwydd yr wyf am i gynnwys yr holl rhifau o un drwy m, cynhwysol.
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
werth i.
Byd Gwaith gwerth i.
>> Fel o'r neilltu, os nad ydych wedi gweld y o'r blaen, mae rhywfaint o siwgr cystrawennol
ar gyfer y llinell hon.
Gallaf ailysgrifennu'r hyn fel a mwy hafal i, dim ond i arbed fy hun ychydig keystrokes
ac i edrych ychydig yn oerach.
Ond dyna i gyd.
Mae'n swyddogaethol yr un peth.
>> Yn anffodus, y cod hwn yn ddim yn mynd i lunio eto.
Os byddaf yn rhedeg wneud sigma 0, sut wyf yn I'n mynd i gael yelled arno?
Beth rwyt ti'n mynd i yn ei hoffi?
>> GYNULLEIDFA: [Anghlywadwy].
>> DAVID Malan: Yeah, doeddwn i ddim yn datgan y swyddogaeth atodol, dde?
C yn fath o dwp, gan ei fod dim ond yn gwneud yr hyn yr ydych yn dweud iddo ei wneud, ac rydych
rhaid i ni wneud hynny yn y drefn honno.
Ac felly os byddaf yn taro Rhowch yma, yr wyf i'n mynd i cael rhybudd am sigma ymhlyg
datganiad.
>> Oh, nid problem.
Gallaf fynd i fyny at y brig, a gallaf dweud, popeth yn iawn, arhoswch funud.
Sigma yn swyddogaeth sy'n dychwelyd yn int ac mae'n disgwyl i
int fel mewnbwn, hanner colon.
Neu gallwn roi'r holl swyddogaeth uchod yn bennaf, ond yn gyffredinol, yr wyf i wedi
argymell yn erbyn hynny, oherwydd ei fod yn braf i bob amser yn cael prif ar y brig fel y
gallwch deifio i'r dde i mewn ac yn gwybod beth yw rhaglen yn ei wneud trwy ddarllen prif gyntaf.
>> Felly nawr gadewch i mi glirio'r sgrin.
Ail-wneud Sigma 0.
Gyd yn ymddangos i edrych ar.
Gadewch i mi redeg sigma 0.
Rhyng Cadarnhaol.
Byddaf yn rhoi y nifer 3 i'w gadw'n syml.
Felly dylai hynny roi i mi 3 ynghyd â 2 plws 1, felly 6.
Fynd i mewn, ac yn wir i mi gael 6.
>> Allaf wneud rhywbeth mwy -
50, 12, 75.
Yn union fel tangiad, yr wyf i'n mynd i wneud rhywbeth chwerthinllyd fel fawr iawn
rhif, O, sydd mewn gwirionedd yn gweithio allan -
eh, nid wyf yn credu bod hynny'n iawn.
Gadewch i ni weld.
Gadewch i ni llanast iawn ag ef.
>> Mae hynny'n broblem.
Beth sy'n digwydd?
Nid yw'r Cod yn ddrwg.
Mae'n dal i fod llinol.
Chwibanu yn cael effaith dda, er.
Beth sy'n digwydd?
>> Ddim yn siwr os ydw i'n ei glywed.
Felly, mae'n troi allan - ac hwn fel o'r neilltu.
Nid yw hyn yn greiddiol i syniad o recursion.
Mae'n troi allan, oherwydd fy mod i'n ceisio cynrychioli nifer mor fawr, mae'r rhan fwyaf
debygol o fod yn cael ei gamddehongli gan C fel rhif yn gadarnhaol,
ond mae rhif negatif.
>> Nid ydym wedi sôn am hyn, ond mae'n troi allan bod rhifau negyddol
yn y byd yn ogystal i rifau positif.
A'r modd y gallwch cynrychioli nifer negyddol
hanfod yw, byddwch yn defnyddio un eithaf arbennig i ddangos
gadarnhaol dros negyddol.
Mae'n ychydig yn fwy cymhleth na hynny, ond dyna'r syniad sylfaenol.
>> Felly, yn anffodus, os C yn ddryslyd un o ddarnau hynny fel mewn gwirionedd yn golygu,
oh, mae hwn yn rhif negyddol, fy dolen yma, er enghraifft, mewn gwirionedd byth yn
mynd i derfynu.
Felly, os wyf mewn gwirionedd yn argraffu rhywbeth dro ar ôl tro, byddem yn
gweld llawer cyfan.
Ond unwaith eto, mae hyn yn ar wahân i'r pwynt.
Mae hyn yn wir dim ond rhyw fath o chwilfrydedd deallusol y byddwn yn dod
yn ôl yn y pen draw.
Ond ar hyn o bryd, mae hwn yn gywir gweithredu os ydym yn tybio bod y
Bydd defnyddwyr yn darparu ints sy'n addas mewn ints.
>> Ond yr wyf yn honni bod y cod hwn, a dweud y gwir, y gellid ei wneud cymaint yn fwy syml.
Os yw'r nod wrth law i gymryd nifer fel m ac yn ychwanegu at yr holl o'r
rhifau rhyngddi ac 1, neu i'r gwrthwyneb rhwng 1 a hynny, gallaf wneud cais
y gallaf fenthyg syniad hwn y uno fath gael, a oedd yn cymryd problem
o'r maint hwn a'i rannu i mewn i rywbeth llai.
Efallai na hanner, ond yn llai, ond gynrychioliadol yr un fath.
Un syniad, ond mae problem llai.
>> Felly rwy'n mewn gwirionedd - gadewch i mi arbed y ffeil gyda rhif fersiwn gwahanol.
Byddwn yn galw hyn yn fersiwn 1 yn hytrach na 0.
Ac yr wyf yn honni y gallaf mewn gwirionedd reimplement hyn yn y math hwn o
meddwl-blygu ffordd.
>> Rydw i'n mynd i adael rhan ohono yn unig.
Rydw i'n mynd i ddweud os m yn llai hyd yn oed na neu'n hafal i 0 -
Im 'jyst yn mynd i fod ychydig yn mwy rhefrol y tro hwn
gyda fy wirio gwall -
Rydw i'n mynd i fynd yn ei flaen ac yn dychwelyd 0.
Mae hyn yn fympwyol.
Yr wyf yn syml penderfynu os yw'r defnyddiwr rhoi rhif negatif i mi, rwy'n
dychwelyd 0, a dylent fod wedi darllen y dogfennau yn agosach.
>> Arall -
sylwi ar yr hyn yr wyf i'n mynd i wneud.
Arall wyf yn mynd i ddychwelyd m a mwy -
beth yw sigma o m?
Wel, sigma o m a m minws 1, ynghyd â m minws 2, ynghyd m minws 3.
Nid wyf am i ysgrifennu i gyd allan.
Pam nad ydw i'n jyst punt?
Recursively galw fy hun gydag ychydig problem llai, hanner colon,
a galw yn y dydd?
>> Iawn?
Nawr dyma, hefyd, efallai y byddwch yn teimlo neu bryder bod hwn yn dolen ddiddiwedd fy mod yn
ysgogi, lle yr wyf yn gweithredu sigma drwy ffonio sigma.
Ond mae hynny'n berffaith iawn, gan fy mod yn meddwl ymlaen yn ychwanegol y llinellau?
>> GYNULLEIDFA: [Anghlywadwy].
>> DAVID Malan: 23-26, sy'n yw fy os yw cyflwr.
Oherwydd yr hyn sy'n braf am y tynnu yma, oherwydd yr wyf yn cadw
trosglwyddo problemau llai sigma, llai problemau, llai - nid yw'n
hanner y maint.
Mae'n dim ond cam fabi llai, ond mae hynny'n iawn.
Oherwydd yn y pen draw, byddwn yn gweithio ein ffordd i lawr i 1 neu 0.
Ac unwaith y byddwn yn cyrraedd 0, nid sigma yn mynd i alw ei hun anymore.
Mae'n mynd i ddychwelyd 0 unwaith.
>> Felly, yr effaith, os ydych yn fath o wynt hwn i fyny yn eich meddwl, yw ychwanegu m plws
m minws 1, yn ogystal â m minws 2, yn ogystal â m minws 3, yn ogystal â dot, dot, dot, m minws
m, yn y pen draw yn rhoi 0 chi, ac y effaith yn y pen draw i ychwanegu'r holl
pethau hyn gyda'i gilydd.
Felly, nid ydym wedi, gyda recursion, datrys y broblem yr ydym yn
Ni ellid datrys o'r blaen.
Yn wir, fersiwn 0 o hyn, a phob broblem hyd yn hyn, wedi bod yn solvable
gyda dim ond defnyddio ar gyfer dolenni neu wrth dolenni neu lluniadau tebyg.
>> Ond recursion, mae'n siŵr, yn rhoi i ni ffordd wahanol o feddwl am
problemau, lle os gallwn gymryd problem, ei rannu o rywbeth
braidd yn fawr i fod yn rhywbeth braidd yn llai, gallaf hawlio y gallwn ddatrys
efallai ychydig yn fwy cain o ran y cynllun, gyda llai o cod,
ac efallai hyd yn oed yn datrys problemau a fyddai'n fod yn fwy anodd, gan ein bod yn y pen draw chi helpu
gweld, datrys yn unig iteraidd.
>> Ond mae'r Cliffhanger a wneuthum eisiau gadael ni ar oedd hyn.
Gadewch i mi fynd yn ei flaen ac yn agor i fyny ffeil o -
mewn gwirionedd, gadewch i mi fynd a gwneud hyn yn gyflym go iawn.
Gadewch i mi fynd yn ei flaen ac yn cynnig y canlynol.
Ymhlith Cod heddiw yn y ffeil yma.
Mae hyn yn un yma, noswap.
>> Felly, mae hyn ychydig yn rhaglen wirion bod Yr wyf chwipio i fyny bod y ceisiadau i wneud
y canlynol.
Yn bennaf, mae'n datgan cyntaf i int enw x ac yn pennu ei
gwerth o 1.
Yna mae'n datgan y int a neilltuo yn werth 2.
Yna, bydd yn argraffu beth x ac y mae.
Yna y mae'n ei ddweud, cyfnewid, dot dot dot.
>> Yna mae'n honni eu bod yn galw swyddogaeth a elwir yn cyfnewid, gan fynd heibio yn x ac
y, y syniad o'r rhain yw bod gobaith Bydd x ac y yn dod yn ôl
wahanol, y gwrthwyneb.
Yna mae'n hawlio cyfnewid!
gyda phwynt ebychnod.
Yna, bydd yn argraffu allan x ac y.
>> Ond mae'n troi allan bod hyn yn iawn arddangosiad syml i lawr
dyma mewn gwirionedd buggy.
Hyd yn oed er fy mod yn datgan dros dro amrywiol a rhoi dros dro mewn
, yna rwy'n ailgyfeirio a gwerth b -
sy'n teimlo'n rhesymol, gan fy mod i wedi arbed copi o yn dros dro.
Yna mi diweddaru b i cyfartal beth bynnag oedd yn y tymheredd.
Mae'r math hwn o gêm cragen symud i mewn i b a b mewn drwy ddefnyddio'r
canol-dyn o'r enw dros dro yn teimlo gwbl resymol.
>> Ond yr wyf yn honni bod pan fyddaf yn rhedeg y cod, fel y byddaf yn ei wneud nawr -
gadewch i mi fynd yn ei flaen a'i gludo i mewn yma.
'N annhymerus' galw noswap.c hwn.
Ac fel yr awgryma'r enw, nid yw hyn yn mynd i fod yn rhaglen gywir.
Gwnewch noswap. / Dim cyfnewid.
x yw 1, y yn 2, cyfnewid, cyfnewid.
x yw 1, y mae 2.
Mae hyn yn sylfaenol anghywir, hyd yn oed er bod hyn yn ymddangos yn gwbl
rhesymol i mi.
Ac mae rheswm, ond nid ydym yn mynd i ddatgelu y rheswm eto.
>> Am y tro yr ail Cliffhanger roeddwn i eisiau i adael i chi yw hyn, mae
cyhoeddiad o ryw fath ar godau cwpon.
Mae ein arloesi gyda diwrnodau yn ddiweddarach eleni wedi ennyn rhif di-ddibwys
o gwestiynau, a oedd yn nid yw ein bwriad.
Bwriad y codau cwpon hyn, lle os byddwch yn rhan o'r broblem
gosod yn gynnar, a thrwy hynny cael diwrnod ychwanegol, oedd mewn gwirionedd i'ch helpu chi guys helpu
eich hun yn dechrau'n gynnar, trefnu o drwy incentivizing chi.
Helpu i ni dosbarthu llwyth ar draws oriau swyddfa well fel bod
ei fod yn fath o ennill-ennill.
>> Yn anffodus, yr wyf yn meddwl fy nghyfarwyddiadau nad ydynt wedi bod, hyd yn hyn, yn glir iawn, felly
Es i yn ôl y penwythnos hwn a'i ddiweddaru y fanyleb mewn maes mwy, testun beiddgar i
esbonio bwledi fel y rhain.
A dim ond i ddweud ei fod yn fwy cyhoeddus, gan diofyn, setiau problem yn ddyledus Dydd Iau
am hanner dydd, y maes llafur.
Os byddwch yn dechrau yn gynnar, gorffen yn rhan o y broblem a osodwyd erbyn dydd Mercher am 12:00
PM, y rhan sy'n ymwneud â cwpon cod, y syniad yw y gallwch ymestyn
eich dyddiad cau ar gyfer P gosod tan ddydd Gwener.
Hynny yw, ychydig oddi ar rhan fach iawn o'r P gosod mewn perthynas â hyn sydd fel arfer yn y
problem mwy o faint, ac rydych yn prynu eich hun diwrnod ychwanegol.
Unwaith eto, mae'n mynd i chi feddwl am y broblem a osodwyd, yn cael i chi
oriau swyddfa yn gynt.
Ond y broblem cod cwpon yn dal i fod angen, hyd yn oed os nad ydych yn ei gyflwyno.
>> Ond yn fwy gymhellol yw hyn.
(Sibrwd CAM) Ac Folks hynny sy'n gadael gynnar yn gonna yn difaru.
Fel y mae'r Folks ar y balconi.
Rwy'n ymddiheuro ymlaen llaw i'r Folks ar y balconi am resymau a fydd yn
glir mewn dim ond hyn o bryd.
>> Felly, rydym yn ffodus i gael un o'r Cyn cymrodyr addysgu pen CS50 ar
chwmni o'r enw dropbox.com.
Maent wedi rhoi yn hael iawn cod cwpon yma am lawer lle hwn,
sydd wedi codi o'r 2 gigabeit arferol.
Felly, yr hyn yr wyf yn meddwl y byddem yn ei wneud ar hyn nodyn olaf yn gwneud ychydig o giveaway,
lle mewn dim ond hyn o bryd, byddwn yn datgelu yr enillydd ac sydd â cwpon
Cod y gallwch wedyn yn mynd at eu gwefan, teipiwch ef i mewn, a voila, yn cael
llawer iawn mwy Dropbox o le ar gyfer eich offer ac ar gyfer eich ffeiliau personol.
>> Ac yn gyntaf, a fyddai'n hoffi cymryd rhan yn y darlun hwn?
OK, nawr bod yn ei gwneud yn hyd yn oed yn fwy o hwyl.
Y person sy'n derbyn y 25-gigabyte cod cwpon - sy'n llawer
yn fwy grymus na'r diweddar ddiwrnod yn awr, efallai -
yw'r un sy'n eistedd ar ben clustog sedd o dan y mae
y cod cwpon.
Efallai y byddwch yn awr yn edrych o dan eich clustog sedd.
>> [VIDEO Playback]
>> -Un, dau, tri.
>> [Screaming]
>> -Byddwch yn cael car!
Byddwch yn cael car!
>> DAVID Malan: Byddwn yn gweld chi ar Mercher.
>> -Byddwch yn cael car!
Byddwch yn cael car!
>> DAVID Malan: Folks Balconi, yn dod lawr yma i'r tu blaen,
lle mae gennym pethau ychwanegol.
>> -Mae pawb yn cael car!
Mae pawb yn cael car!
>> [VIDEO END Playback]
>> Adroddwr: Yn y CS50 nesaf -
>> SIARADWR 5: O fy diar diar diar diar diar diar diar diar diar diar -
>> [DRAMÂU ukelele]