>> [CHWARAE CERDDORIAETH]
>> DAVID J. Malan: Mae hwn yn CS50.
Ac mae hyn yn ddechrau wythnos tri.
Felly, rydym wedi cael llawer o gyffrous pethau i dalu am heddiw.
Mae llawer o gyfleoedd ar gyfer Gwirfoddolwyr i fyny ar y llwyfan.
Ac yn y pen draw, heddiw yw Nid yw am cod o gwbl.
Ond mae'n ymwneud syniadau, ac mae'n ymwneud algorithmau,
ac mewn gwirionedd yn dod yn ôl rhai o'r y gwersi a ddysgwyd o wythnos sero,
wherein dwyn i gof, rydym yn Cyflwynodd monstrosity hwn.
A benthyca ysbrydoliaeth o hynny, i ddechrau
i ddatrys fwyfwy soffistigedig problemau algorithmically.
Ond yn gyntaf, un neu ddau o gyhoeddiadau.
Felly un, os hoffech ymuno Staff a chyd-ddisgyblion CS50 yn ginio
dydd Gwener hwn, yma ac yn Caergrawnt, ac yn New Haven,
ewch i'r cwrs gwefan, lle gellir URL i'w gael.
Darlith Dydd Mercher hwn, bydd beidio â bod yma yn Sanders.
Bydd yn ar-lein yn unig, felly alaw mewn o wefan CS50, a
boed yma yng Nghaergrawnt neu New Haven hefyd.
>> Ac yna broblem a osodwyd dau eisoes yn eich dwylo.
Os nad ydych wedi deifio i mewn eto, yn caniatáu i mi i gynnig yr awgrym wedi'i eirio'n gryf
hynny, yn enwedig yn awr, fel y y broblem yn pennu ymlaen llaw,
Ydych wir eisiau i ddechrau yn awr, os nad dabble ychydig ar y penwythnos neu cyn
pan fyddant yn mynd allan gyntaf ar Dydd Gwener, oherwydd eich bod chi helpu
canfod nad ydynt yn o angenrheidrwydd mynd yn hirach neu'n fwy heriol bob
se.
Yr wyf yn credu y byddwch yn canfod bod, yn gyffredinol, maent yn tueddu i gymryd yn fras
tua un faint o amser.
Ond mae'n sicr yn dibynnu ar y myfyriwr, ac mae'n
yn dibynnu ar y meddylfryd fyddwch yn nesáu ato â nhw.
Ond yn ddieithriad, rydych yn mynd rhedeg i fyny yn erbyn rhai wal,
ac ydych yn mynd i daro rhywfaint o chwilod, ac eich bod yn unig
ddim yn mynd i fod yn gallu ddod dros y rywbryd.
Ac mae'n hynod werthfawr i allu i gamu i ffwrdd, yn dod yn ôl y diwrnod nesaf,
ewch i oriau swyddfa, post ar CS50 Trafod neu debyg, er mwyn cael dadflocio mewn gwirionedd.
Felly cadwch hynny mewn cof.
Dechrau cynharaf ag y bo modd yw'r peth gorau y gallwch ei wneud.
Felly dyma lle rydym yn dechrau y dosbarth, dros mewn wythnos sero.
A gallwn gael yn wirfoddolwr yma i fy helpu i ddod o hyd i mics?
IAWN.
Sefyll i fyny yn barod.
Dewch ar i fyny.
Dyfalu dyna sut mae'n mynd i'r gwaith.
Beth yw dy enw?
ALAN Estrada: Alan Estrada.
DAVID J. Malan: Alan Estrada.
Dewch ar i fyny.
Neis i gwrdd â chi.
ALAN Estrada: Neis i gwrdd â chi.
DAVID J. Malan: A oeddech yma gyda ni yn wythnos sero, wrth gwrs.
ALAN Estrada: Yr oeddwn yn.
Yr oeddwn i.
>> DAVID J. Malan: Felly gallech fynd ymlaen llaw a dod o hyd i ni Mike Smith,
mor gyflym ag y gallwch?
Mor gyflym ag y gallwch.
Llythrennol rhwygo y broblem yn ei hanner gan fod angen i chi.
>> ALAN Estrada: Um.
DAVID J. Malan: Yn llythrennol rhwygo y broblem yn ei hanner.
>> ALAN Estrada: Oh.
Mm.
Da iawn.
>> DAVID J. Malan: Iawn.
Da.
Diolch.
ALAN Estrada: Da iawn.
IAWN.
>> DAVID J. Malan: Ac felly yn awr, rydych wedi ei dreulio o dipyn i lawr
i hanner maint y broblem.
Nawr, rydym yn i lawr at chwarter.
A ydych yn talu sylw i pa ochr rydym yn cadw?
>> [Chwerthin]
>> ALAN Estrada: Ydw, yr wyf yn think--
>> DAVID J. Malan: Pa adran ydym ni ynddi?
ALAN Estrada: distewyddion, felly.
>> DAVID J. Malan: Iawn.
Ond Mike Smith yn mynd i fod ar ôl distewyddion.
So--
>> [Chwerthin]
>> Iawn.
ALAN Estrada: Ble ydyn ni'n chwilio?
DAVID J. Malan: Mike Smith.
ALAN Estrada: Mike Smith.
DAVID J. Malan: Yn awr, rydym mewn llawfeddygol.
Yn awr, meddygon.
Now--
>> ALAN Estrada: Let's- gadewch i ni fynd gyda go iawn.
Real.
>> DAVID J. Malan: Real.
IAWN.
Os oes angen Real.
Yn awr, pa ffordd yw Mike Smith?
>> ALAN Estrada: Fel hyn.
>> DAVID J. Malan: Pa ffordd?
ALAN Estrada: Aros.
Hawl M yw--?
Rydym yn dechrau with--
>> DAVID J. Malan: Yeah.
Maen nhw'n gadael.
Eich hawl.
>> ALAN Estrada: Yeah.
>> DAVID J. Malan: Felly Mike yn fan hyn.
ALAN Estrada: Beth?
>> [Chwerthin]
>> Esiampl ddrwg, guys.
Mae'n ddrwg gennym.
DAVID J. Malan: Bydd hyn yn addysgu chi i neidio allan o'ch cadair.
>> ALAN Estrada: Oh.
Oh.
Ges i chi.
Oh.
Mae hyn yn yw-- OK, Cawn chi.
Smith iawn yma?
>> DAVID J. Malan: Smith, diolch.
Felly byddaf yn cadw yn edrych i fyny Smith?
>> ALAN Estrada: O, ie.
Na, na, na.
O, na.
Mae hyn yn pwll.
>> DAVID J. Malan: O, cawsoch Smith.
IAWN.
>> ALAN Estrada: Yeah, yr wyf yn got Smith dde yma.
Mae'n ddrwg gennym, guys.
Roeddwn i'n meddwl Michael-- rydym yn yn chwilio am Michael.
Mae'n ddrwg gennym.
>> DAVID J. Malan: Mae'n iawn.
Mae pob hawl, yn awr rydym yn i mewn i Paccini a'i Feibion.
>> ALAN Estrada: Paccini a meibion.
DAVID J. Malan: Dim ond i chi ac yr wyf yn i mewn ar hyn.
IAWN.
Dod o hyd i ni Mike Smith.
Smith.
>> ALAN Estrada: Smith.
>> DAVID J. Malan: Smith.
Rydym yn mewn ymchwil ar gyfer sbwriel.
ALAN Estrada: Sbwriel.
Oh.
Mae hyn yn mynd i gymryd amser.
>> [Chwerthin]
DAVID J. Malan: Esgidiau.
Rydym yn mewn esgidiau.
>> ALAN Estrada: Nawr rydym yn gonna--
>> DAVID J. Malan: Nice.
ALAN Estrada: ac--
[Chwerthin]
O, mae hyn yn wych.
[Chwerthin]
>> DAVID J. Malan: Mae'n iawn.
>> ALAN Estrada: O, mae hyn yn dda.
Dwi ddim yn meddwl fy mod i'n mynd i cael ffrindiau PSAT ar ôl hyn.
DAVID J. Malan: Da.
Chwaraeon.
ALAN Estrada: Chwaraeon.
Um, L, M, N, O, P.
DAVID J. Malan: Iawn.
Felly gadewch i rwygo'r hyn yn ei hanner.
Mae'n iawn.
Mae hyn yn dod i ben yn wael beth bynnag, gan fod Mike Ni fydd Smith yn y tudalennau melyn.
>> ALAN Estrada: Aw.
>> DAVID J. Malan: Na, mae'n iawn.
Ond gadewch i esgus fel ei fod ar y dudalen hon.
Felly nawr, rydych chi wedi ei dreulio o dipyn i lawr y broblem i un dudalen, a gwelsom Mike Smith.
>> [Bloeddio]
OK, diolch i chi.
IAWN.
Dyna oedd rhyfeddol.
Ond roedd yn dal yn gynt na chwilio llinol,
yr hwn yr ydym yn dechrau ar y gan ddechrau o'r llyfr,
ac yr ydym yn symud ein ffordd o'r chwith i'r dde, yn y pen draw yn edrych am Mike Smith.
Ac felly, os yw'r llyfr ffôn Roedd gan efallai 1,000 o dudalennau,
efallai byddai wedi cymryd ni 10 neu felly dagrau dudalen.
>> Ond efallai eich bod wedi ysgogi cyffwrdd rhagdybiaeth
yn ystod hynny i gyd, sef dweud bod y llyfr ffôn o flaen llaw oedd yr hyn?
GYNULLEIDFA: Trefnwyd yn.
DAVID J. Malan: Mae'n didoli.
Iawn?
Mae'n nhrefn yr wyddor, felly bod yr holl enwau a niferoedd hynny
yn cael eu datrys o A i'r Z, ac yn nhrefn yr wyddor yn y canol.
Ond heddiw, rydym yn gofyn yn awr y cwestiwn, yn dda,
sut y gwnaeth Verizon neu y ffôn cwmni ei gael i mewn i'r wladwriaeth?
>> Oherwydd ei fod yn un peth i trosoledd hynny dybiaeth, ac felly,
datrys problem gyda algorithm fwy effeithlon.
Ond ni fyddwn byth yn wir ofynnwyd yn wythnos sero, yn dda,
faint yn gwneud hynny cost Verizon neu rywun arall
i gael y llyfr ffôn er mwyn ddidoli?
>> Iawn?
Nid oes ots os edrych i fyny Mike Smith
yn gyflym super, os yw'n mynd â chi yn flwyddyn i roi trefn y tudalennau yn y lle cyntaf.
Iawn?
Efallai y byddwch yn ogystal dim ond nithio drwy llyfr ffôn ar hap,
os yw'n mynd i fod yn super ddrud i ddatrys y.
Felly os gallwn gael gwirfoddolwr arall.
Gadewch i ni gymryd edrych i fyny yma yn sut might-- ni ddod ar up-- sut
efallai y byddwn yn mynd ati i ddatrys y rhain.
>> Ac os Jordan gallai mewn gwirionedd ymuno â ni i fyny yma ar y llwyfan.
Dewch ar i fyny am ychydig funudau'n.
Beth yw dy enw?
CAROLINE: Caroline.
DAVID J. Malan: Caroline, yn dod ar i fyny.
A byddwch yn ymuno gan i mi a Jordan yma.
Caroline, diolch i chi.
Iawn.
Felly, yr hyn sydd gennym yma am Caroline yw 26 o lyfrau glas
bod FAS defnyddio i weinyddu rhai arholiadau terfynol.
Mae'r rhain yn cael anodd dod o hyd, ond yr hyn yr ydym wedi ei wneud o flaen llaw
yw ein bod wedi rhoi enw rhywun ar flaen pob un o'r rhain,
ond rydym wedi cadw pethau'n syml gan Yna diffodd enwau llawn.
Felly byddem yn gosod y person gyda'r enw L, D, J, B, yr holl ffordd A drwy Z,
ond eu bod nhw mewn trefn ar hap.
Ac felly os ydych fyddai, yn siarad â'ch ffordd trwy'r broblem wrth i chi
yn hynny, gallwch fynd yn ei flaen a didoli rhain i ni, o A i Z.
>> GYNULLEIDFA: Iawn, felly L yn debyg, y canol.
C yn dechrau.
B. J cyn L. B, C.
>> DAVID J. Malan: Daliwch y yn meddwl am eiliad.
Oherwydd fel arall, mae hyn yn unig ddiddorol i chi, mi, a Jordan.
Dyna ni.
GYNULLEIDFA: [Anghlywadwy].
R.
DAVID J. Malan: Iawn.
Beth wyt ti'n gwneud?
>> CAROLINE: M dod ar ôl O.
>> DAVID J. Malan: Iawn.
>> CAROLINE: O.
DAVID J. Malan: O, Da.
>> CAROLINE: E.
>> DAVID J. Malan: E, F. Yeah.
>> CAROLINE: T, U, V.
>> DAVID J. Malan: V, T, U, V. Felly mae'n yn edrych fel eich bod making-- cadw i fynd.
Mae'n edrych yn debyg eich bod yn gwneud pentwr mawr dros yma,
a math o pentwr mawr dros yno.
Felly, y hanner cyntaf y wyddor, ail hanner y wyddor.
IAWN.
Da.
Math o rannu'r broblem yn ddau.
M, N, X. Yeah.
CAROLINE: K.
DAVID J. Malan: Iawn.
K. Felly, rydych yn fath o ddewis nhw un ar ôl y llall,
ei roi naill ai i'r chwith neu i'r dde, neu Z yn mynd ar y llawr.
IAWN.
>> CAROLINE: Z sy'n mynd ar y llawr.
>> DAVID J. Malan: Iawn.
Y yn mynd ar y llawr.
Nawr gallwn roi X.
>> CAROLINE: G.
DAVID J. Malan: G fynd i'r chwith.
S yn mynd yn iawn.
Mae pob hawl, A yn mynd yr holl ffordd i'r chwith.
>> CAROLINE: A, B, C, D.
>> DAVID J. Malan: Yn awr, yn dda.
Mae gennym A, B, C. W yn mynd i lawr yno.
Mae pob hawl, T.
>> CAROLINE: H, I, J.
DAVID J. Malan: H, I, J. Da.
CAROLINE: Yn y canol, dw i'n gonna--
DAVID J. Malan: Iawn.
Felly nawr, rydym yn mynd i fath o'r uno amrywiol hyn pentyrrau.
Felly A drwy C, yna yr wyf yn gweld D, a E ac F, a G, a H, ac I. Nice.
J, K. Ac yna, pentwr hwn ben i lawr, ond mae hynny'n iawn.
Cadarn.
Gallwn dorri rhai corneli.
IAWN.
Ac yna mae angen W, X, Y, Z.
>> CAROLINE: Yeah.
>> DAVID J. Malan: Ardderchog.
Diolch Felly yn fawr iawn i Caroline ar gyfer didoli hyn.
>> [Bloeddio]
>> Diolch.
Diolch yn fawr iawn.
Felly nawr gadewch i ni ystyried am eiliad sut yr aeth Caroline ynglŷn â gwneud hynny,
a beth yn union yr ydym yn yn gallu canlynol-- sut yr ydym
yn gallu datrys y broblem pan oeddem yn unig
Rhoddir criw cyfan o fewnbynnau hap.
>> Wel, mae'n edrych fel yna Roedd yn dipyn o system yno?
Hawl.
Felly y llythrennau cynharach yn yr wyddor, mae hi
oedd rhoi ar y chwith, a'r llythyrau yn ddiweddarach yn y wyddor,
ei bod yn rhoi ar y dde.
A chyn gynted ag y daeth o hyd rhai llythrennau procsimol, rhai
sy'n mynd i'r dde nesaf at ei gilydd, byddai'n rhoi'r rheiny yn eu trefn.
Ac felly rydym yn fath o roedd hyn bach pentyrrau o fewnbynnau didoli digwydd.
>> Ac felly dyna yn union fel yr hyn y byddai'r rhan fwyaf ohonom yn ei wneud bodau dynol.
Byddem yn fath o sifftio drwyddo, a byddem yn fath o fecanwaith.
Ond gallai fod yn anodd i ysgrifennu i lawr mewn fformiwla fel y cyfryw.
Mae'n teimlo ychydig yn fwy organig na hynny.
Felly, gadewch i ni weld os gallwn yn awr rhwymo y broblem gyda llai o fewnbynnau.
>> Yn hytrach na 26, gadewch i ni gwneud rhywbeth llawer llai
gyda dim ond dweud, saith, y tu ôl y drysau hyn, fel petai.
A oes dim ond saith rhifau?
Ac os y nod yn awr ar law yn dod o hyd i werth,
gadewch i ni weld pa mor effeithlon gallwn fynd ati i wneud hyn.
A gadewch i ni weld os gallwn yn awr dechrau i wneud cais rhai rhifau,
neu ryw fformiwlâu i ddisgrifio â hwy effeithlonrwydd ein llyfr ffôn
algorithm, mae ein algorithm llyfrau arholiad, ac yn fwy cyffredinol, dod o hyd i wybodaeth.
>> Felly, ar gyfer hyn, gadewch i mi fynd yn ei flaen, ac ar y sgrin gyffwrdd dros yma,
gosod porwr gwe sydd wedi yn union saith drysau.
Ac os gallem gael un arall gwirfoddoli i ddod ymlaen dros yma,
Dwi wedi rhoi un y drysau hyn dros yma.
Gwirfoddolwr Cyflym.
>> Mae hyn yn demos one-- yn mynd i gyflymach ac yn gyflymach yn awr.
Dewch ar i lawr.
Beth yw dy enw?
TREVOR: Trevor.
>> DAVID J. Malan: Trevor?
Mae pob hawl, Trevor, yn dod ar i lawr.
Felly Trevor wedi gwirfoddoli yma i gwneud problem debyg, ond un sy'n
gulach eu cwmpas, ac sy'n mynd i'n galluogi i geisio ffurfioli yn awr
y broses ar gyfer didoli rhifau hyn.
>> Felly Trevor, neis i gwrdd â chi.
Felly dyma yw arae, felly i siarad, rhestr o saith drysau.
Mynd yn ei flaen ac yn dod o hyd i ni y rhif 50.
Ac yna ar ôl y ffaith, dywedwch wrthym sut yr ydych yn ei chael yn.
A ddylai be-- pob hawl.
Yeah, mae hyn yw'r un yma?
Uh-oh.
IAWN.
Cliciwyd bod un.
Da.
>> Ac yn dda.
Nawr eich clicio bod un.
A gadewch i mi roi y meicroffon i chi, fel bod gennych mewn dim ond hyn o bryd.
Mynd yn ei flaen a chliciwch ar y y drws nesaf yr ydych yn bwriadu.
Ie, da.
TREVOR: Alla i unclick drws?
DAVID J. Malan: Na, ni allwch unclick.
TREVOR: OK.
Mae hyn yn un.
DAVID J. Malan: Ble ydych chi eisiau mynd?
Pa un?
>> TREVOR: Bod un.
>> DAVID J. Malan: Na
>> TREVOR: OK.
Mae hyn yn un.
>> DAVID J. Malan: Ydw.
A oedd yn dda.
Iawn.
Felly beth oedd eich algorithm neu weithdrefn ar gyfer gwneud hyn, Trevor?
>> TREVOR: Fi jyst yn mynd trwy drysau hyd nes i mi dod o hyd i 50.
DAVID J. Malan: Iawn.
Algorithm Ardderchog.
Felly mae hynny'n iawn.
Oherwydd yn wir, os wyf yn datgelu beth sydd tu ôl i'r rhain dau ddrws arall, beth
byddwn yn dod o hyd yma yw bod mai dim ond mewnbwn hap.
Felly dyna oedd mewn gwirionedd fel cystal ag y gallech ei gael.
Ac yn wir, a gawsoch yn well na drwyadl chwilio'r amrywiaeth cyfan,
oherwydd byddai wedi bod yn hynod anlwcus pe byddech wedi cyrraedd y nifer
50 wrth y drws olaf un.
Ond beth os ydym yn lle hynny Rhoddodd rhagdybiaeth chi.
Tybiwch wyf yn fath bob un drysau hyn o gwmpas,
fel bod gennych yr niferoedd datrys y tro hwn,
ond y tro hwn, mae'n mewn gwirionedd a different-- y tro hwn,
'i' didoli mewn gwirionedd i chi.
Ac yn awr y nod wrth law yw taro'r rhif 50.
>> TREVOR: OK.
>> DAVID J. Malan: Beth yw eich algorithm mynd i fod?
>> TREVOR: Wel, os yw'n didoli, mae'n naill ai fynd
i be-- os mwyaf i'r mwyaf, ddisgynnol, bydd yn cael yr un cyntaf,
neu os mai i'r gwrthwyneb, bydd yn yr un olaf.
Felly byddaf dim ond tap drws hwn, a yna dim ond tap y drws diwethaf.
DAVID J. Malan: Ardderchog.
Iawn.
Felly, rydym yn dod o hyd i'r rhif 50.
Felly, cyn gynted ag y byddwch yn gwybod cawsant eu didoli, yr ydym yn
yn gallu trosoledd dybiaeth hon.
Felly, maent yn rhy debyg yr enghraifft llyfr ffôn.
Cyn gynted ag y byddwch wedi, hyd yn oed gyda problem fach fel hyn,
eich mewnbynnau didoli cyn-, y gallwn mewn gwirionedd yn dod o hyd i'r gwerth gellid dadlau
yn fwy effeithlon.
>> A doeddwn i ddim yn dweud wrthych os oedd didoli bach i mawr, neu fawr i fach,
ac felly roedd yn rhesymol iawn i gychwyn ar un pen neu'r llall
i mewn gwirionedd yn gweld bod gwerth targed.
Felly diolch i Trevor hefyd.
A byddaf propose-- ei wneud 'n glws.
Mae gennym ychydig clip, mewn gwirionedd, bod ymhlith ein hoff eiliadau yn CS50,
lle weithiau demos hyn peidiwch â mynd yn eithaf yn unol â'r cynllun.
Ac yn wir ar hyn o bryd, yr wyf yn dynnu i fyny y rhyngwyneb anghywir
â hwy i ddefnyddio'r sgrîn gyffwrdd.
Felly dyna oedd fy mai yno.
>> Felly, bydd hyn yn gwneud i clip flwyddyn nesaf fel
pam yr oeddwn yn clicio ar fy sgrin hun.
Ond gadewch i ni edrych yn sydyn ar yr hyn a ddigwyddodd y llynedd
gyda Jay, a ddaeth i fyny, llawer fel Trevor yma, gwirfoddoli,
ac yn y clip byr hwn, byddwch yn gweld sut na wnaeth yr un demo yn eithaf
datgelu yr un gwersi a ddysgwyd.
[VIDEO Playback]
-Mae Pob Rwyf am i chi ei wneud yn awr yw i ddod o hyd i mi, ac i ni,
mewn gwirionedd, mae nifer 50 un cam ar y tro.
>> -Y Rhif 50?
>> -Y Rhif 50.
A gallwch ddatgelu beth sydd y tu ôl i bob un o'r drysau hyn
syml drwy ei gyffwrdd gyda bys.
Damn hi.
>> [Chwerthin]
>> [DIWEDD Playback]
DAVID J. Malan: Felly a aeth yn dda iawn.
Dyna oedd y drysau heb eu didoli.
A Jay, wrth gwrs, ei chael yn llawer rhy gyflym.
Gwnaeth Trevor gwaith llawer gwell yn nhermau eiliad teachable,
fel petai, eleni yn cymryd mwy o amser i ddod o hyd iddo.
Wrth gwrs, yna rydym rhoddodd Jay ail gyfle,
lle rydym yn datrys y drysau, yn union fel y gwnaethom dros Trevor,
a gwnaeth Trevor super yn dda y tro hwn.
Ond wnaeth Jay ei hanner mor gyflym.
[VIDEO Playback]
-Y Nod nawr yw hefyd ddod o hyd i ni y rhif 50,
ond yn ei wneud algorithmically, a dywedwch wrthym sut rydych chi'n mynd am y peth.
>> -IAWN.
>> -ac Os byddwch yn dod o hyd iddo, eich bod yn cadw y ffilm.
Os nad ydych yn ei chael yn, byddwch yn rhoi yn ôl.
>> -Man.
>> -OH!
>> - [Anghlywadwy] OK.
Felly, yr wyf i'n mynd i edrych ar y ben gyntaf i benderfynu os there's-- Oh.
>> [Cymeradwyaeth]
>> [DIWEDD Playback]
DAVID J. Malan: Iawn.
Felly didoli drysau yn glir yn arwain at fwy o effeithlonrwydd.
Ac felly, ddwywaith mor gyflym yw'r hyn oeddwn yn ei olygu yno.
Ac felly Jay got 'n ffodus ddau achlysur.
Ac efe a hefyd got 'n ffodus yn hynny ddiwethaf blwyddyn, yr wyf yn archebu rhai Blu-ray disgiau
i roi allan mewn gwirionedd.
Mae'n ddrwg gen i eleni, rydym yn Nid oedd gan yr un peth, Trevor.
Ond well fyth oedd ychydig flynyddoedd yn ôl.
Ac efallai y bydd rhai ohonoch yn gwybod hyn gyd, Sean, a pan oedd yn CS50,
Heriwyd gyda'r union un broblem, er mewn SD,
fel y byddwch yn fuan yn gweld, yn ôl yn y dydd.
Ac fe welwch fod nid yn unig oedd yn yn cymryd ychydig yn hwy nag Jay,
ychydig yn hwy nag Trevor, yr oedd mewn gwirionedd y cyfle gwych
i gymryd rhan bron pawb yn y dorf a la Price is Right, gan annog
iddo ddod o hyd i'r rhif yr oeddem yn ei geisio.
Gadewch i ni. yn edrych yn gyflym.
>> [VIDEO Playback]
>> -IAWN.
Felly eich tasg yma, Sean, yw'r canlynol.
Rwyf wedi cuddio y tu ôl y rhain drysau y rhif saith.
Ond cuddio mewn rhai o'r drysau hyn yn ogystal niferoedd negyddol eraill.
Ac mae eich nod yw i feddwl o hyn rhes uchaf o rifau
fel dim ond amrywiaeth, neu dim ond dilyniant o ddarnau o bapur
gyda rhifau y tu ôl iddynt.
Ac mae eich nod yw, dim ond yn defnyddio'r top amrywiaeth yma, dod o hyd i mi y rhif saith.
Ac rydym yn wedyn yn mynd i feirniadu sut yr ydych yn mynd ati i'w gyflawni.
-Iawn.
-Find I ni y rhif saith, os gwelwch yn dda.
Na
Pump, 19, 13.
>> [Chwerthin]
>> Nid yw'n gwestiwn tric.
Un.
>> [Chwerthin]
Ar y pwynt hwn, nid yw eich sgôr yn iawn da, felly efallai y byddwch yn ogystal yn dal i fynd.
Tri.
>> [Chwerthin]
>> Ewch ymlaen.
A dweud y gwir, ni allaf helpu ond meddwl hyn yr ydych yn hyd yn oed yn meddwl am, so--
>> [Chwerthin]
Dim ond y rhes uchaf, felly oes gennych chi dri chwith.
Felly dod o hyd i mi saith.
>> [Chwerthin]
17.
Saith.
>> [Cymeradwyaeth]
>> Iawn.
>> [DIWEDD Playback]
>> DAVID J. Malan: Felly gallem gwyliwch y rhain drwy'r dydd hir.
Ac wrth gwrs, mae rhai o'r demos eleni efallai
Bydd yn awr yn y pen draw yn nesaf fideo flwyddyn yn ogystal.
Felly nawr gadewch i ni mewn gwirionedd canolbwyntio ar y algorithmau
yma, a gweld os na allwn yn awr yn dechrau i ffurfioli
sut y gallwn ni fynd ati i gael ein data i mewn i hyn datgan ei fod yn didoli,
fel y pen draw, y gallwn mewn gwirionedd chwilio yn fwy effeithlon.
A hyd yn oed er ein bod yn mynd i ddefnyddio setiau data yn weddol fach,
fel yr wyth rhif ydym wedi yma ar y bwrdd,
yn y pen draw gallai un syniadau hyn yn berthnasol at 1,000 o mewnbynnau, miliwn mewnbynnau,
4 biliwn a mewnbynnau, oherwydd bod y algorithmau yn mynd i fod yn sylfaenol yr un fath.
>> Ac felly mae hyn yn ein olaf cyfle i wirfoddolwyr heddiw,
ond efallai y mwyaf ymwneud un, y mae ei angen arnom wyth o wirfoddolwyr
i ddod i fyny a cherdded ni drwy'r broses o ddidoli beth fydd cyn bo hir
fod ar gerddoriaeth hyn yn sefyll yma.
Gadewch i mi ddechrau yn ôl yma.
>> Felly un yn y gwyrdd turquoise-- yw e?
A ydych yn ymrwymo?
Dau.
Dewch ar i lawr.
IAWN.
Tri.
Pedwar.
Gadewch me-- OK, pump.
Rydych yn cael eich enwebu gan eich ffrind.
Chwech, saith, ac wyth.
Dewch ar i fyny.
Iawn.
Diolch yn fawr.
Dewch ar i fyny.
>> Iawn.
Felly, yr hyn sydd gennym ac mae hyn Yma-- ymhlith y rhai mwy lletchwith,
gan fod hyn bydd angen hiwmor bod chi fi am ddim ond ychydig o amser.
Rhaid i chi fod yn rhif un.
Beth yw dy enw?
>> Annan: Annan.
>> DAVID J. Malan: Annan.
David.
Beth yw dy enw?
>> JOSEPH: Joseff.
>> DAVID J. Malan: Joseff, rydych yn rhif dau.
>> SERENA: Serena, rhif tri.
Stefan, rhif pedwar.
CYNTHIA: Cynthia.
DAVID J. Malan: Cynthia, rhif pump.
[Anghlywadwy]
DAVID J. Malan: [Anghlywadwy].
Dafydd, rhif chwech.
MATT: Matt.
DAVID J. Malan: Rhif Matt saith.
A?
>> WAVERLY: Waverly.
>> DAVID J. Malan: Waverly, rhif wyth.
Iawn.
Os ydych yn could-- whoops.
Os ydych i gyd, fel eich her gyntaf, mae yna
Mae wyth standiau cerddoriaeth yma yn wynebu'r gynulleidfa.
Pe gallech roi eich niferoedd ar Saif cerddoriaeth hyn yn y fath fodd
eu bod yn llinell i fyny gyda'r yr un rhifau ar y bwrdd.
Felly, gwneud eich hunain yn edrych fel 'na gan roi eich niferoedd ar gerddoriaeth yma
yn sefyll yma.
Ardderchog hyd yn hyn.
>> Ardderchog.
IAWN.
Felly nawr, rydym yn mynd i ofyn i'r cwestiwn mewn ychydig o ffyrdd gwahanol.
Sut y gallwn fynd ati i ddidoli Folks hyn i fyny yma?
Oherwydd bod gennym ychydig o ddulliau yn gynharach, lle roeddem yn
math o gwneud dau bwcedi gwahanol.
Ac yna rydym yn gyffredinol piecing pethau at ei gilydd.
Cyn gynted ag y gwelsom dau rif oedd yn perthyn gyda'i gilydd,
rydym yn rhoi nhw at ei gilydd.
Dau lythyr sy'n perthyn i'w gilydd.
>> Ond gadewch i ni weld os byddwn yn Ni all ffurfioli hyn,
fel ein bod yn y pen draw yn cael rhywfaint o ffug-god byddwch,
gallwch ddatrys y problemau hyn â hwy.
Felly nawr, rwy'n edrych allan yn y niferoedd hyn yma.
Ac yr wyf yn gweld criw cyfan o gamgymeriadau.
Yn y pen draw, yr wyf am un ar y chwith ac wyth ar y dde.
>> Ac felly rwy'n edrych ar y ddau hyn, pedwar a dau.
A beth yw'r broblem, yn amlwg?
Yeah.
So.
Mae dau yn amlwg yn dod cyn pedwar, felly eich bod yn gwybod beth?
Gadewch i mi yn gyntaf yn defnyddio dull farus, os mynnwch, llawer problem debyg
gosod one-- os cofiwch oddi wrth y Standard Edition o Broblem Set One,
lle rwy'n dim ond yn lleol yn datrys y broblem sy'n iawn yma o flaen fy
a gweld ble mae'n arwain fi.
>> IAWN.
Felly dau a phedwar, gadewch i mi fynd ei flaen a dim ond cyfnewid gennych ddwy.
Os gallwch symud yn gorfforol eich hunain a'ch papur,
Rwyf yn ymddangos i wedi gotten y rhestru mewn gwell cyflwr.
>> Yn awr, maen nhw'n dda.
Rydw i'n mynd i symud ymlaen, pedwar a chwech, yn edrych yn dda.
Ddim yn broblem.
Chwech ac wyth, OK.
Wyth ac un, problem arall.
Oherwydd bod yr hyn sy'n wir am wyth ac un?
Mae un yn dod cyn wyth, ac felly beth ddylem ei wneud?
Gadewch i ni gyfnewid dau hyn.
Mae un ac wyth.
Ac yn awr, yr wyf i'n mynd i ddal ati.
Rydw i'n mynd i gadw edrych i'r dyfodol.
A gadewch i ni weld beth sy'n digwydd.
Wyth a thri, o gwrs, allan o drefn.
Gadewch i ni gyfnewid.
Wyth a saith, wrth gwrs.
Allan o drefn.
Gadewch i ni gyfnewid.
Wyth a phump, wrth gwrs, gadewch i ni gyfnewid.
Iawn.
Rhestr yn cael ei datrys.
ie?
>> OK, yn amlwg nid.
Ond mae'n ychydig yn well, dde?
Oherwydd bod rhybudd beth ddigwyddodd.
Bob tro y byddwn yn perfformio cyfnewid, mae llai o faint Rhif fath o percolated y ffordd honno,
a nifer mwy percolated y modd hwn, neu yr ydym chi helpu
dechrau gan ddweud bubbled i'r chwith neu bubbled i'r dde.
>> Yn awr, nid yw'n ddigon, oherwydd ar y gorau gallai nifer
wedi symud un man ymlaen, neu ar y gwaethaf,
gallai nifer gael Symudodd un man arall.
Felly rydych yn gwybod beth, y math hwn o wedi gweithio yn eithaf da hyd yn hyn.
Gadewch i mi roi cynnig arni eto.
Dau a phedwar, maen nhw'n iawn.
Pedwar a chwech, maen nhw'n iawn.
Chwech ac un, allan o drefn.
Felly gadewch i ni cyfnewid i chi ddau.
Ac yn awr, yn sylwi ar y broblem yn dechrau cael ychydig yn well eto.
Chwech a thri, allan o drefn.
Gadewch i ni cyfnewid chi ddau.
Chwech a saith, rydych yn dda.
Saith a phump, wrth gwrs, allan o drefn.
Saith ac wyth, mewn trefn.
Ac yn awr, efallai y bydd angen i I gwneud hyn ychydig yn fwy o weithiau.
Ac yn wir, yn meddwl am eich hunain faint o bosibl weithiau maximally
efallai y bydd rhaid i mi gerdded yn ôl ac ymlaen?
>> Byddwn yn dod yn ôl at hynny.
Felly dau a phedwar yn dal yn OK.
Pedair ac un, Na.
Felly, gadewch i ni gyfnewid.
Ac eto, yn sylwi ar eu golwg mae un yn fath o byrlymu
ar y chwith, lle y dylai fod.
Pedwar a thri cyfnewid.
Pedwar a chwech.
Chwech a phump cyfnewid.
Chwech a saith.
Mae saith ac wyth yn dda.
>> Da.
Rydym yn cael hyd yn oed yn well.
Felly, gadewch i ni weld.
Yn awr, mae gennym ddau ac un.
Wrth gwrs, cyfnewid.
Dau a thri, tri a phedwar, pedwar a pump, chwech a saith, saith ac wyth.
Da.
A ydych yn gwybod beth?
Gan fy mod yn gwneud un newid yno, gadewch i mi wneud un archwiliad bwyll.
Gadewch i mi fynd yr holl ffordd yn ôl i'r dechrau.
IAWN.
Un, two-- yup, gweld?
Rhywbeth o'i le.
Tri, pedwar, pump, chwech, saith, wyth.
Ac yn y tocyn olaf, yn cael eu ydych yn gyfforddus gyda fy nawr
gan honni ei cael ei datrys?
IAWN.
Yn weledol, mae hynny'n hollol wir.
Ond swyddogaethol, beth oedd hefyd jyst yn digwydd
yn y tocyn olaf sy'n caniatáu i chi i gadarnhau bod y rhestr hon yn wir
didoli?
>> Beth wnes i ei wneud neu beidio â gwneud hyn tocyn diwethaf?
GYNULLEIDFA: Nid oedd unrhyw newidiadau.
DAVID J. Malan: Mae'n ddrwg gennyf?
GYNULLEIDFA: Dim newidiadau.
DAVID J. Malan: Nid oedd unrhyw newidiadau.
Felly byddai'n wirion i mi i gwneud yr un algorithm eto
os nad oeddwn yn gwneud unrhyw yn newid y tro cyntaf.
Ac nid y wladwriaeth wedi newid.
Yn sicr, nid wyf ddim yn mynd i wneud unrhyw newid yr ail dro.
Ac felly, mae'n ddiogel bellach i ddweud, rhestr ei ddidoli.
>> Ac yn wir, mae hyn yn awr rhywbeth yr ydym annhymerus 'yn gyffredinol
didoli swigen alwad, lle pairwise, rydych cywiro camgymeriadau eto,
ac unwaith eto, ac unwaith eto, ac yr ydych dal i fynd yn ôl ac ymlaen,
ac yn ôl ac ymlaen, hyd nes y byddwch yn gwneud unrhyw gyfnewidiadau o'r fath, a phryd
gallwch fod yn hyderus, ie, yr wyf yn gorffen gosod pob un o'r camgymeriadau.
Gadewch i ailosod a rhoi cynnig ar ddull arall.
Pe gallech guys mynd yn ôl i mewn i y drefn oeddech eiliad yn ôl,
a oedd yn edrych fel hyn.
Yn awr, gadewch i ni gymryd agwedd yn un ychydig yn fwy fel y llyfr arholiad,
lle'r oeddem yn gyson ddewis y llythyren o'r wyddor
ein bod yn fath o eisiau i ddelio â nesaf.
Efallai ei fod yn llythyr uchel, fel A, neu Z. lythyr isel
>> Felly mae pawb yn ôl yn y drefn hon.
Ac yn awr gadewch i mi wneud hyn.
Gadewch i ni weld wyf yn gwybod fy mod wedi wyth rhifau yma.
Rydw i'n mynd i fynd yn ei flaen a dim ond yn fwriadol yn dewis
yr elfennau lleiaf.
Iawn?
Mae hyn yn ymddangos 'n athrylithgar hefyd.
Pam nad ydw i'n dod o hyd i'r lleiaf elfen, ei roi lle mae'n perthyn iddo,
wedyn yn cael yr elfen lleiaf nesaf, rhowch mae'n lle mae'n perthyn iddo, a dim ond ailadrodd.
>> Oherwydd reddfol, ddylai weithio hefyd.
Felly pedwar, mae hynny'n nifer eithaf bychan.
Rydw i'n mynd i gofio lle bo hyn yn.
Arhoswch funud.
Dau yn llai.
Gadewch i mi yn awr gofio lle mae dau yw, ac yn anghofio am phedwar.
Byddwn yn ymdrin â hynny yn nes ymlaen.
Chwech, dydw i ddim diddordeb.
Wyth, nid gen i ddiddordeb mewn.
Un yw fy rhif fach newydd.
Felly, yr wyf i'n mynd i cofio lle mae un yn.
Tri, dim diddordeb.
Saith, dim diddordeb.
Five, dim diddordeb.
>> Felly, heb syrthio i ffwrdd y llwyfan eleni,
Rydw i'n mynd i chrafangia rhif one-- a beth oedd eich enw eto?
>> Annan: Annan.
>> DAVID J. Malan: Annan.
Ac os gallech ymuno â mi yn cychwyn y rhestr,
gadewch i ni eich rhoi chi ble rydych yn perthyn.
Unfortunately-- beth yw eich enw?
>> Stefan: Stefan.
>> DAVID J. Malan: Stefan yn y ffordd.
Felly, cyn i Stefan datrys hyn problem, beth ddylem ei wneud?
Beth rydym yn ei wneud gyda Stefan?
>> GYNULLEIDFA: [Anghlywadwy].
DAVID J. Malan: Iawn.
Felly, gallem wneud hynny.
Gallem fath o gymryd Stefan a'i pedwar, a dim ond ei roi mewn newidyn
a dal gafael arni am rhyw faint o amser,
a thrwy hynny wneud lle i rif un.
Ac nid dyna'r drwg.
Gallwn awgrymu, beth am wneud rydym yn unig yn rhoi Stefan yma?
Pam y gallai hyn dorri un o'r syniadau i ni ddechrau
siarad am y tro diwethaf, yr wythnos diwethaf?
Yeah?
>> GYNULLEIDFA: [Anghlywadwy].
>> DAVID J. Malan: Does dim mynegai ar ei gyfer.
Os ydych yn meddwl am hyn, yn wir, fel array, mae hyn yn debyg i un negyddol,
felly does dim cof mewn gwirionedd yma os yw hyn yn wir amrywiaeth,
fel rydym datgan yr wythnos diwethaf yn y ddarlith.
Felly, ni ddylem wneud hyn.
Efallai y byddwn yn ei storio mewn newidyn.
>> Neu eich bod yn gwybod beth?
Clywais rywun arall yn awgrymu hynny.
Beth arall y gallem ei wneud gyda Stefan?
Pam mae nid ydym yn unig droi allan o'i gartref ac ei roi ynghylch ble rhif un oedd.
Felly os ydych am fynd draw yno.
Ac yn wir, mae hwn yn ateb yn eithaf da.
Nawr ar y naill law, yr wyf i wedi fath o gwneud y broblem yn waeth.
Pedwar bellach ymhellach i ffwrdd o ble y dylai fod.
Dylai fod tuag at hanner hwn.
>> Ond eich bod yn gwybod beth?
A allai fod wedi bod yn lwc ddrwg.
Efallai wythwr oedd yma.
Ac felly, efallai byddem wedi gotten lwcus,
a gwthio wyth yn agosach at y diwedd.
Felly, yn y diwedd y dydd, mae'n fath o holl gyfartaleddau allan.
Nid oes angen i ni ofalu am bedwar.
Y cyfan yr wyf yn poeni am ar hyn o bryd yw gan ddewis yr elfen lleiaf.
>> Ac yn awr, yr hyn yr wyf i'n mynd i wneud yw anghofio am un rhif
yn barhaol, oherwydd gwn y Rhestr tu ôl i mi erbyn hyn didoli.
Felly fy rhestr oedd gynt maint wyth.
Yn awr, mae'n o faint saith.
Felly, fy broblem yn mynd yn llai o faint, er yn llinol.
Felly nawr, dw i'n mynd i ddewis y elfen lleiaf ar hyn o bryd, dau.
Chwech, wyth, pedwar, tri, saith, pump.
Dyna oedd yr elfen lleiaf.
Felly, beth ydw i'n mynd i'w wneud with-- beth oedd eich enw eto?
>> JOSEPH: Joseff.
>> DAVID J. Malan: Joseff?
Rydym yn mynd i adael Joseff yn ei le.
Nawr, dw i'n mynd i esgus bod y rhain guys yw-- yn dda,
Gwn fod dau rhain eisoes yn cael eu datrys.
Gadewch i ni yn awr yn canolbwyntio ar y gweddill y rhestr.
Chwech yw'r lleiaf ar hyn o bryd.
Wyth yn fwy.
Pedwar yw'r lleiaf ar hyn o bryd yn awr.
Tri yw'r lleiaf ar hyn o bryd yn awr.
Ac felly yn awr, yr wyf i'n mynd i ddewis tri, pwy yw-- beth yw eich enw eto?
SERENA: Serena.
DAVID J. Malan: Serena, os gallech chrafangia eich rhif a chyfnewid with--
KALSANG: Kalsang.
DAVID J. Malan: Kalsang.
Dewch ar ôl, ac rydym yn mynd i gyfnewid dau rheini.
Ac yn awr, gadewch i ni roi hyn ar awtobeilot.
Rydw i'n mynd i fynd a'i adael i chi guys i ddewis yr elfennau lleiaf nesaf.
Dun, dun, dun, dun.
Rhif pedwar, beth ddylech chi ei wneud?
Ardderchog.
Yn awr, yr wyf i'n mynd i wneud tocyn arall.
Dun, dun, dun, dun.
Rwy'n gweld pump yw'r lleiaf nesaf.
Nawr, dw i'n mynd yn pasio arall.
Dun, dun, dun, dun.
Chwech yw'r lleiaf.
Da.
Saith yw'r lleiaf.
Dim newid.
Wyth yw'r lleiaf.
Done.
>> Felly, yr hyn yr ydym wedi ei wneud yn unig gan ailadroddol gan ddewis un elfen ar ôl y llall
yn gweithredu rhywbeth yr ydym ni'n mynd i ffurfioli fel math dethol.
Ac mae'n efallai hyd yn oed symlach i egluro,
yn hynny llythrennol pawb 'ch am ei wneud yw jyst cadw
yn mynd yn ôl ac ymlaen drwy'r rhestr dewis, yr elfen lleiaf nesaf,
hyd nes y byddwch yn ei wneud.
>> Felly mae hyd yn oed yn symlach, efallai reddfol, na'r olaf.
Gadewch i ni geisio un yr un olaf.
Pe gallech guys ailosod eich hunain i mewn i'r swyddi canlynol
un tro olaf, gadewch i ni weld os na allwn yn awr yn ffurfioli un dull arall.
Yn wir, byddai rhywun allan yna hoffi cynnig
sut arall y gallem fynd ati i wneud hyn?
Heb tossing allan geiriau allweddol neu fath o atebion sydd eisoes yn hysbys,
dim ond reddfol, yr hyn y gallem ei wneud?
>> GYNULLEIDFA: [Anghlywadwy].
DAVID J. Malan: Yeah.
Felly mae rhywfaint o greddf gwych yno.
Pethau da yn ymddangos i ddigwydd hyd yn hyn mewn gwyddoniaeth gyfrifiadurol pan fyddwn yn rhannu'r
a gorchfygu y broblem o rannu yn ei hanner a hanner a hanner.
Ac felly yn wir, rydym yn Gallai dechrau i wneud hynny.
Ac yn wir, mae hynny'n mynd i fod, fe wnawn ni weld, un o'n datrysiadau gorau eto.
Ond gadewch i ni ddod yn ôl at hynny cyn bo hir.
Yn wir, rydym yn mynd i'w wneud bod ychydig yn ddiweddarach yr wythnos hon.
Beth arall y gallem ei wneud i ddatrys hyn?
Felly pawb yma yn gorchymyn sy'n ymddangos ar hap.
Ti'n gwybod beth?
Yn hytrach na mynd yn ôl ac ymlaen, yn ôl ac ymlaen, yn ôl ac ymlaen
bob amser, mae hyn yn teimlo fel Dwi'n gwneud lot o gerdded.
Pam nad ydw i'n jyst dechrau am cychwyn y rhestr,
a dim ond rhowch bedwar lle mae'n perthyn iddo?
Felly gadewch i mi gymryd yn ganiataol gyfer hyn o bryd y fy rhestr Dim ond yr elfen hon yn gyntaf.
A yw pedwar didoli ar hyn o bryd, os bydd yr holl wyf yn poeni am yw popeth fan hyn?
Mae hyn yn fath o trivially yn wir, dde?
Fel y rhestr yn cynnwys un rhif, a y rhif hwnnw pedwar yn amlwg yn eu didoli.
>> Felly gadewch i mi jyst nodi bod y rhestr hon yn cael ei datrys.
Ond yn awr yr wyf yn cael y gweddill y rhestr hon.
Felly nawr, yr wyf yn dod ar draws dau.
Ble mae dau yn amlwg perthyn mewn perthynas â phedwar?
Cyn bedwar.
Felly, beth allaf ei wneud fan hyn?
Beth yw eich enw eto?
>> JOSEPH: Joseff.
>> DAVID J. Malan: Joseff, pe gallech cam yn ôl
am ddim ond ennyd gyda'ch rhif.
Ac yn awr yr hyn y dylai Stefan wneud yma?
Gadewch i ni symud Stefan dros yma.
Ac yn awr, gadewch i Joseff ddod i mewn yma.
Ac yn awr, gadewch i mi yn honni bod popeth yma yn cael ei datrys.
Felly, canlyniad tebyg, ond mae dull sylfaenol wahanol.
Nid wyf wedi edrych hyd yn oed yn yr hyn sydd i lawr yno.
Fi jyst cadw cymryd yr elfennau gan eu bod yn rhoi i mi,
a delio â nhw.
>> Felly nawr, rwy'n gweld rhif chwech.
Ble mae rhif chwech yn perthyn?
Mae gennym ddau, pedwar, chwech.
Yn union lle mae'n ar hyn o bryd.
Felly gadewch i ni adael hynny yn unig, ac yn awr honni bod y rhan hon o'r rhestr
yn awr yn didoli.
Ac felly, mae hyn yn teimlo yn sylfaenol yn wahanol yn hynny Im 'jyst
symud drwy'r rhestr yma llinol, ac rwy'n byth yn dyblu yn ôl.
Ydw.
Iawn.
Felly wyth, ble ydych chi'n perthyn?
Iawn yma.
Perffaith.
Felly nawr, un.
Uh-oh.
Mae hyn yn teimlo fel ei fod yn mynd i fod yn ddrud.
Yn awr, yn y algorithm blaenorol, Fi jyst cyfnewid bobl.
Felly, efallai y byddwn yn ei roi yr holl ffordd yn y dechrau, ond yna symudodd Joseff.
Ond os byddaf yn symud Joseph, yn awr beth sy'n mynd i fod yn anghywir?
>> Yn awr, yr wyf i wedi fath o undone-- rydw i wedi cymryd un cam ymlaen, ac yna
un cam yn ôl, oherwydd erbyn hyn Byddai Joseph fod allan o drefn.
Felly, gadewch i ni wneud hyn.
Pe gallech gymryd rhif un ac yn gam yn ôl am ychydig ennyd.
Sut allwn ni put-- beth oedd eich enw eto?
>> Annan: Annan.
>> DAVID J. Malan: Annan yn ei le?
Beth sydd angen digwydd gyda pharch i ddau, pedwar, chwech, ac wyth?
Mae angen iddynt i gyd i symud.
Felly os wyth hoffai symud yn gyntaf, ac yna chwech, ac yna bedwar, ac yna dau.
Ac yna Annan, os byddech yn hoffi dod i mewn yma, yn dda.
Ond yma, rydym wedi dim ond fath o talu pris
ar bwynt gwahanol yn yr algorithm.
Tra bod y tro diwethaf gyda dewis didoli, a hyd yn oed fath swigod,
Im 'yn cerdded yn ôl ac allan, yn ôl ac ymlaen,
sydd yn sicr yn adio i fyny , ac yn llythrennol grisiog-ddoeth amser.
>> Didoli Mewnosod, ar y dechrau yr olwg, yn edrych fel ei fod yn
super fwy craff, gan fod Im 'jyst gan wneud yn araf cynnydd, cynyddol,
ond dydw i ddim yn mynd hwn yn ôl ac ymlaen.
Ond os bydd rhywun yn wir allan o drefn, rhybudd
holl waith yr wyf newydd gael ei wneud.
Roedd rhaid i mi symud hanner y rhestr dim ond er mwyn gwneud lle i rif un.
Felly mae'n un faint o waith hyd yn hyn mae'n
yn teimlo, dim ond math gwahanol o waith.
>> Gadewch i ni barhau.
Felly nawr rydym yn gwybod bod pawb rhwng un ac wyth yn cael eu didoli.
Yma, mae gennyf rhif tri.
Os ydych yn hoffi i godi rhif tri, cam yn ôl un.
A beth sydd angen i chi guys i ei wneud?
Yep.
Felly dyna un arall, dau, tri cham.
Tair uned o amser mai dim ond yn costio mi, fel y tair awr yn gallu ffitio.
Yn olaf, saith.
>> Gadewch i ni fynd yn ei flaen ac yn cael byddwch yn cymryd cam yn ôl.
Mae hyn yn unig yn mynd i gostio i ni un uned o amser, ond mae hynny'n iawn.
Ac yn awr, pump yn mynd i fod ychydig yn fwy drud.
Os hoffech chi gamu'n ôl.
Mae angen i ni symud wyth, a saith, a chwech.
Ac yna mae pawb yn awr yn cael ei sortio.
Felly llaw mawr i'n gwirfoddolwyr yma.
Diolch yn fawr.
>> [Cymeradwyaeth]
>> Diolch i chi i gyd.
Diolch i chi i gyd.
Felly, gadewch i ni weld nawr pa mor costus hynny i gyd yr oedd.
Gadewch i ni ystyried efallai y symlaf o'r rhain, math swigen.
Ac yr wyf yn dweud symlaf, dim ond am fod gallwch ei datrys farus o ddim ond
datrys y broblem pairwise yma.
Datrys y broblem pairwise yma, dro ar ôl tro
ac unwaith eto, gan ailadrodd cymaint o weithiau ag y bydd angen i chi mewn gwirionedd.
>> Felly, mae'n ymddangos bod gyda rhyw fath swigod, yn dda,
faint o gamau y mae rhaid i mi gymryd ar y tocyn cyntaf y algorithm?
Efallai fy mod take-- gadewch i ni see-- un, dau, tri, pedwar, pump, chwech, saith.
Ac mae wyth elfen yma.
Felly mae fel n minws 1 cam i gael gan ddechrau'r rhestr
hyd at ddiwedd y rhestr.
>> Ond gyda'r math dethol, yn cofio fy mod i'n gan ddewis yr elfennau dro ar ôl tro
ac eto dyna lleiaf, Im 'yn ei roi yn ei le,
ond yna Dydw i ddim edrych tu ôl i mi eto.
Felly yr wyf yn credu ei fod ychydig yn fwy clir felly fod y tro cyntaf, yr wyf efallai
rhaid iddynt gymryd yr holl n minws 1 gamau i ddod o hyd i'r elfen lleiaf.
Yna, yr wyf yn eu rhoi ar waith, ac yr wyf yn troi allan pwy bynnag oedd yma o'r blaen.
>> Ond yna nid oes gennyf i cadw edrych ar yr elfen hon,
gan fy mod yn gwybod ei fod yn eisoes y lleiaf.
Felly nawr, gallaf edrych ar ddim ond saith elfennau, yna chwe elfen,
Yna pum elfen, yna pedair elfen.
Ac felly yn fathemategol, os yw n y nifer o elfennau neu rifau
ein bod yn dechrau gyda, gallwch ddychmygu bod hyn yr un fath â n minws 1,
plws n minws 2 cam, plws n minws 3 cham,
plws n minws 4 cam, yr holl ffordd i lawr i ddim ond un cam.
Ac dwi ar ben fy person olaf.
>> Ac os ydych yn cofio bod llawer o stats lyfrau neu lyfrau mathemateg
rhaid i fformiwlâu rhai ar y Hardcover yn ôl neu o'u blaen,
mae'n ymddangos fod y gyfres hon Gellir yn symlach
fel amseroedd n n minws 1 dros 2.
Ac mae'n iawn os nad yw hynny'n ar flaen eich meddwl.
Ond mae hyn yn wir yn wir.
Dyna dim ond yn ffordd symlach o ysgrifennu arno.
Ac yna os ydych yn meddwl yn ôl i'r ysgol radd,
pan fyddwch yn dim ond dechrau lluosi pethau allan, mae hyn wrth gwrs,
yn unig yw n sgwâr minws n rhannu â 2.
Y cyfan yr wyf wedi gwneud yn ehangu mae i'r ymadroddion yno.
Ac felly gadewch i ailysgrifennu hwn ychydig yn wahanol.
Mae hynny n ei sgwâr wedi'i rannu â 2 minws n / 2.
>> Felly unwaith eto, Im 'jyst fath o wneud cais rhywfaint o rifyddeg rheolau yno.
Ond yn sylwi nawr bod y term mwyaf yn ymadrodd hwn, fel petai,
yw bod n sgwâr.
Felly ie, 'i' n sgwâr wedi'i rannu â 2, minws n / 2.
>> Ond yn gyffredinol, os yw n mynd i fod yn werth mawr,
Rydw i'n mynd i honni bod n sgwâr yn mynd i fod y ffactor amlycaf.
Dim ond ei fod yn mynd i fod yn mwy o cyfrannwr
at y nifer o gamau na n / 2.
Felly, beth ddylwn i ei olygu wrth hyn?
Gadewch i ni geisio enghraifft syml, hyd yn oed er bod y math yn cael ychydig o fawr.
>> Felly mae'n debyg roedd gennym 1 filiwn o bobl ar y llwyfan, neu 1 filiwn o bethau
ein bod am roi trefn.
Gadewch i plwg miliwn i mewn yn union fformiwla sy'n
i weld faint o gamau y mae'n ei gymryd cyfanswm i ddidoli miliwn o elfennau gan ddefnyddio dyweder,
didoli dewis.
>> Felly byddem yn cael yr un fformiwla ag o'r blaen.
Id 'plwg miliwn, er mwyn i mi gael miliwn sgwâr wedi'i rannu â 2,
minws miliwn wedi'i rannu â 2.
Os byddaf yn gwneud hynny mathemateg o flaen llaw yma, mae gennym 500,000,000,000
minws 500,000, a oedd yn rhoi i ni 499,999,500,000,
sydd yn eithaf darn mawr.
>> Yn wir, os ydych yn cymharu yn awr 499,000,000,000, 999,000,000,
500,000 yn erbyn ein gwerth gwreiddiol, 500,000,000,000, mae mor damn agos.
Iawn? n sgwâr wedi'i rannu gan 2 yn rhoi us-- neu yn hytrach, n sgwâr wedi'i rannu gan 2
yn rhoi i ni 500,000,000,000.
Dyna darn eithaf agos i 499,999,500,000,
sy'n cael ei ddweud tynnu oddi ar 500,000, neu yn fwy cyffredinol, tynnu oddi ar
n sgwâr, mo 'n sylweddol llawer mawr.
Mae'r n sgwâr yn gwneud hyn niferoedd yn tyfu yn gyflym iawn.
>> Yn awr, mae hyn yn bwysig dim ond i'r graddau wrth i ni, fel gwyddonwyr cyfrifiadurol,
Yn gyffredinol, nid yn mynd i ofalu cymaint am y naws o fformiwlâu hyn
ac yn union yr hyn y mae'r atebion manwl gywir yn cael eu.
Rydym ofal yn unig hynny, byddwch yn gwybod beth?
Ar ddiwedd y dydd, fformiwla hon ar y drefn n sgwâr.
>> Ie, rydym yn rhannu â 2 mewn 'na.
Ie, rydym yn tynnu i ffwrdd n minws 2.
Ond ar ddiwedd y dydd, mae'r term a 'n sylweddol yn ein brifo ac yn ein costau
mae llawer o gamau yn y tymor sgwâr.
Ac felly yr hyn y gwyddonydd cyfrifiadurol yn mynd i wneud yn gyffredinol
yn anwybyddu'r pob un o'r rhai telerau gorchymyn llai,
a dim ond yn edrych ar yr un sy'n cyfrannu fwyaf at y gost.
>> Ac mae hyn yn braf, oherwydd ein bod yn gallu yn awr yn siarad yn llawer mwy cyffredinolrwydd
am algorithmau, a gallant eu cymharu.
Ac mae'r ffaith fy mod yn gan ddefnyddio'r O mae hyn yn fwriadol.
Pan fyddaf yn dweud ar y gorchymyn o, rwy'n benodol
gan gyfeirio at rywbeth Gelwir O. mawr A mawr O
yn nodiant y cyfrifiadur gwyddonydd defnyddio i ddisgrifio
yn rhwymo uchaf ar rywbeth.
>> Felly, os ydych yn dweud bod algorithm yn O fawr o n sgwâr,
gan fy mod yn cynnig dim ond funud yn ôl, bod modd
bod o ran ei rhedeg amser neu ei effeithlonrwydd,
y mae'n ei gymryd ar y gorchymyn o n sgwâr grisiau.
Efallai mwy, efallai llai.
Ond mae'n ar y drefn n sgwâr.
A dyna yr rhwymo uchaf.
Nid yw'n mynd i fod yn yn fwy poenus na hynny.
Nid yw'n mynd i fod n dorri'n giwbiau, neu 2 i'r n, neu rywbeth llawer mwy.
Mae hwn yn rhan uchaf rhwymo ar beth bynnag y gost yn.
Felly o gofio bod, gadewch i ni ystyried dim ond ychydig o enghreifftiau.
Ac mae hyn yn unig yw rhestr cyfyngedig amseroedd rhedeg o gyffredin iawn
am algorithmau sy'n golygu i fod darluniadol o rai pethau rydym wedi
gweld eisoes.
>> Felly, er enghraifft, yn achos didoli dethol, yr hyn rwy'n hawlio yma
yn rhedeg y fath dethol yn amser ar y drefn n sgwâr.
Yn yr achos gwaethaf, dw i'n mynd i gael criw cyfan o rifau ar hap yma.
Ac fel y gwelsom yn fathemategol, os wyf yn cadw cerdded
drwy'r rhestr, trwy'r rhestr, gan ddewis y lleiaf nesaf
Elfen dro ar ôl tro, os wyf mewn gwirionedd yn ysgrifennu i lawr yr holl gamau
Rwy'n cymryd gan fy mod yn cynnig formulaically o'r blaen, 'i' ar y drefn n sgwâr
camau yr Rwy'n cymryd.
>> Ac mae'n troi allan y swigen didoli a gosod math
yr un mor araf yn yr achos gwaethaf.
Ystyriwch, er enghraifft, trefnu mewnosod, yr algorithm olaf un yr ydym yn delio â,
a oedd i ni edrych ar yr elfen, ac yna rhowch ei lle mae'n perthyn.
Ac yna rydym yn edrych ar yr elfen nesaf, a mewnosod mae'n lle mae'n perthyn.
>> Felly yn ystyried y senario gorau posibl.
Gadewch i ni dybio fy mod wedi fy gwirfoddolwyr yn llinell i fyny yn llythrennol fel hyn, y naill drwy wyth,
didoli yn barod.
Faint o gamau yn fath mewnosod mynd i gymryd i ddatrys wyth o bobl,
os byddant yn cyrraedd ar y llwyfan edrych fel hyn?
>> Mae wyth o bobl eu didoli yn barod.
Ac yr wyf yn defnyddio math fewnosod.
Dyna olaf o'r algorithmau.
Wel, gadewch i reenact gyflym go iawn.
Felly os byddaf yn dechrau fan hyn, yr wyf yn gweld un.
Ble mae un yn perthyn?
Mae'n perthyn i'r dde fan hyn.
Rwy'n gweld dau.
Ble mae dau yn perthyn?
Iawn yma.
Rwy'n gweld tri.
Ble mae tri yn perthyn?
Iawn yma.
>> Rwy'n gweld pedwar.
Iawn yma.
Pump, chwech, saith, wyth.
Does dim rheswm i ailadrodd fy hun.
Ac felly, faint o gamau yw bod yn nhermau n?
Mae'n ar y drefn o n grisiau, dde? n minws 1.
Ond yr wyf yn cymryd nifer llinol o risiau, ac erbyn hyn rwy'n ei wneud.
Felly dyna yr achos gorau, er.
Beth am yr achos gwaethaf?
Pa wyth oedd dros yno, a saith i lawr yno,
ac un a dau yn dros yma, felly bod y rhestr yn cael eu gwrthdroi gwirioneddol?
>> Wel, beth sy'n digwydd yn wir os yw hyn yn y rhif?
Ac fe wnawn ond ychydig o enghreifftiau.
Beth os, yn wir, mae'r wythwr yma, ac mae'r whoops number--.
Felly beth os, yn wir, mae nifer wyth yn yr holl ffordd dros yma,
ac rwy'n ei ddefnyddio fath fewnosod?
>> IAWN.
I hawlio ar hyn o bryd mae yn ei le.
Ond yn awr, seven-- ble mae saith yn mynd?
Wrth gwrs, mae'n mynd dros yma.
Felly, rhaid i mi symud wyth dros un lle.
Nawr chwech, ble mae'n mynd?
Wel, pob hawl.
Yn awr, rhaid i mi symud wyth dros lle, a saith dros le,
ac yna yr wyf yn sw n plopian i lawr chwech.
>> Felly, y tro cyntaf, yn ei gostio mi un cam at atgyweiria pethau,
yna mae'n gostio i mi dau gam i osod pethau.
Faint o gamau y mae'n mynd i gymryd at atgyweiria
pethau i roi pump yn y lle iawn?
Tri.
Oherwydd erbyn hyn rhaid i mi symud un, dau, tri.
Faint o gamau y mae'n mynd i gymryd i roi pedwar yn y lle iawn?
4 a 5, a 6, yn ogystal â 7.
>> Ac felly mae'n fathemategol union yr hyn yr ydym ddisgrifir ar gyfer math dethol.
Mae gennym gyfres hon hynny dim ond cynyddu.
1 a 2 a 3 ynghyd â 4, neu i'r gwrthwyneb, 7 a 6
a 5 ynghyd â 4 yn ychwanegu ar gyfer heddiw dibenion ar y drefn n sgwâr.
>> Felly gadewch i mi nodi hefyd bod didoli swigen yn n sgwâr hefyd.
Gan fod gyda'r math swigen, pob un tro yr af drwy'r rhestr,
Rwy'n cymryd yn fras faint o gamau?
Bob tro rwy'n yn llythrennol cerdded oddi yno i yno?
Yn fras grisiau n.
Sut Ond mae amseroedd lawer efallai i mi Mae angen i fynd drwy'r rhestr?
>> Wel, yn fras n amser.
Efallai n minws 1, ond yn fras amseroedd n.
Wel, pam hynny?
Wel, gyda'r math swigod, os rydym yn dechrau gyda'r math swigen,
gyda'r rhestr yn y gwaethaf posibl sefyllfa, sydd unwaith eto yn gwbl
yn ôl, beth sy'n mynd i ddigwydd?
Rwy'n mynd drwy'r rhestr, a rhif un perthyn yr holl ffordd dros yno.
>> Ond gyda'r math swigen, pa mor bell mae un symud ymlaen fy nhocyn cyntaf drwy'r rhestr?
Faint o fannau y mae'n ei gael nes at y man cywir?
Dim ond un.
Felly, os ydych fath o reswm thrwy hyn, bob tro drwy algorithm hwn,
Cymryd camau n fras Dewi.
Ond faint o tocynnau drwy'r rhestr yw hi
mynd i gymryd yn un i swigen i'r chwith lle mae'n perthyn iddo?
>> Mae ganddo i symud fel, mannau n fel hyn.
Felly, dim ond i wneud y didoli y rhestr, Mae'n rhaid i mi gerdded yn ôl ac ymlaen amseroedd n.
A bob tro, rwy'n gan edrych ar n elfen.
Felly, yn gwneud pethau n n amserau ar y drefn n sgwâr.
>> Yn awr, byddwn yn gweld mewn rhai o'r shorts a
yn cael eu hymgorffori yn broblem nesaf CS50 yn gosod, dull arall ar y rhain,
ond am y tro, gadewch i 'jyst yn ystyried rai adegau rhedeg eraill,
yn enwedig os y rhai didoli cymryd ychydig o amser i suddo i mewn.
Beth yw algorithm rydym wedi gweld yn barod sy'n cymryd ar y drefn o gamau n?
>> Beth ddylai gymryd nifer llinol o'r camau yr ydym wedi gweld hyd yn hyn?
Beth yw hwnna?
Mae'r chwiliad llyfr ffôn.
Mae'r algorithm yn gyntaf.
Iawn?
Lle rydym yn llinol chwilio am Mike Smith?
Yn wir.
O'r wythnos sero, pan ddechreuais droi un dudalen ar y tro,
a dywedais hyd yn oed ei bod yn garedig o algorithm deimlad llinol,
a chawsom y llun ar y bwrdd gyda'r llinell goch syth
a'r melyn yn syth llinell, y rhai oedd yn wir
algorithmau sydd mewn O fawr o n.
>> Gan fod i ddod o hyd Mike Smith mewn ffôn Llyfr o dudalennau n, yn yr achos gwaethaf,
Gallai mynd â fi n grisiau.
Beth am gymryd presenoldeb?
Un, dau, tri, pedwar, pump, chwech.
Beth yw'r amser yn rhedeg o hyn algorithm ar gyfer cymryd presenoldeb?
O Big n, oherwydd mewn theori wyf rhaid i bwynt pawb yn yr ystafell.
>> Nawr fel o'r neilltu, beth am y Optimization arall o wythnos sero?
Dau, pedwar, chwech, wyth, 10, 12.
Byddai gwyddonydd cyfrifiadurol sylweddoli, arhoswch funud,
sydd ar y drefn Rhennir n gan ddau gam.
Iawn?
Gan fy mod i'n gwneud dau o bobl ar y tro.
Ond rydym ni'n mynd i anwybyddu telerau gorchymyn is hynny,
ac rydym yn jyst yn mynd i daflu i ffwrdd y rhaniad 2,
a dim ond dweud, O fawr o n ar gyfer y algorithm yn ogystal.
>> Beth am hwn?
Byddwn yn sgip dros rai o'r rhain, ond beth Roedd algorithm a oedd yn log n?
Cymerodd hynny'n fras log camau n?
Mae'r rhaniad a gorchfygu.
Yn union.
Fel yr enghraifft llyfr ffôn mewn wythnos sero ac yn gynharach heddiw,
lle rydym yn rhannu'r broblem dro ar ôl tro ar ôl tro.
Rydym yn tynnu ar y bwrdd mewn wythnos sero fel llinell werdd crwm,
a dywedasom y diwrnod hwnnw ei fod yn algorithm logarithmig.
>> Ac yn wir, mae nifer o gamau y mae'n cymryd i berfformio rannu a gorchfygu,
neu chwilio deuaidd fel y byddwn yn dechrau yn galw arno, fel yn y llyfr ffôn,
ar y drefn log a grisiau.
Ac mae hyn yn dipyn o un 'n annaearol.
>> Beth yn cymryd un cam, neu yn fwy penodol
nifer cyson o gamau?
Efallai ei fod yn ddau, efallai ei bod yn dri, ond gwyddonydd cyfrifiadurol yn unig
symleiddio fel O fawr o 1, rhyw nifer cyson o gamau.
Beth sy'n rhywbeth y gallech ei wneud hynny yn cymryd nifer cyson o gamau?
>> Beth yw'r amser yn rhedeg o glapio?
Amser yn gyson.
Iawn?
Fel, beth yw'r amser yn rhedeg o gwneud unrhyw beth sy'n cymryd dim ond un
llawdriniaeth, fel argraffu F Helo Byd.
Gallai hynny fod yn dweud i fod yn amser yn gyson, oni bai bod llai o achosion gornel gyda phrint F,
yr hyn y gallai'r amser yn rhedeg o brint F gwirionedd fod?
A pham?
Beth yw n mesur yn yr achos hwnnw?
>> GYNULLEIDFA: [Anghlywadwy].
DAVID J. Malan: Yn union.
Mae nifer o gymeriadau rydym eisiau argraffu.
Felly mae'n iawn y cyd-destun.
Heddiw, rydym wedi bod yn canolbwyntio llawer ar llythrennau a rhifau yma ar y bwrdd.
Ond gallai hefyd fod cymeriadau mewn llinyn go iawn.
Felly, mae'n troi allan yna un arall mesur a fydd yn dechrau gofalu am,
a dyna y gwrthwyneb o O fawr, fel petai.
>> Dyna nodiant omega.
Tra O mawr yn golygu beth sydd, mae'r uchaf rhwymo ar eich amser yn rhedeg?
Maximally, faint o amser gallai rhywbeth yn ei gymryd?
Omega-- ddrwg gennym hyn yn cadw i ddod up-- yn y gwrthwyneb i hynny,
lle mae'n is rhwymo ar y Gallai faint o amser rywbeth cymryd.
>> So. er enghraifft, beth algorithm sy'n cymryd camau bob amser sgwâr n?
Wel, un o'r algorithmau rydym wedi gweld heddiw, mewn gwirionedd, fod yn hynny hefyd.
Didoli Dewis.
Dewis math eithaf dwp.
Hyd yn oed os bydd y algorithm-- ddrwg gennym, hyd yn oed os yw'r amrywiaeth eisoes yn didoli,
didoli detholiad yn mynd i cadw cerdded drwy'r rhestr
i wneud yn siŵr ei fod wedi y lleiaf Elfen dro ar ôl tro ar ôl tro.
A hyd yn oed er eich bodau dynol yn y gynulleidfa yn gwybod bod, arhoswch funud,
ydych chi eisoes yn llwyddo yn y elfen lleiaf, y cyfrifiadur
nid yw'n gwybod hynny hyd nes ei fod yn edrych yr holl ffordd trwy'r rhestr.
Yn yr un modd, mae is rhwymo bod Efallai hefyd yn cael eu hystyried
a allai fod yn amser llinol.
>> Faint o amser mae'n ei gymryd i elfennau didoli n yn y gorau
achos gan ddefnyddio rhywbeth fel math swigod?
Gadewch i ni dybio eich rhestr eisoes yn cael ei datrys.
Dywedasom fath swigen yn cymryd ar y drefn n sgwâr grisiau.
Ond beth os yw eisoes wedi datrys?
Beth os byddwch yn sylweddoli ar ôl un tocyn trwy'r amrywiaeth
eich bod wedi gwneud unrhyw gyfnewidiadau?
A oes angen i chi gadw gwneud mwy o docynnau?
>> Na
Felly mae rhwymo is ar fath swigen allai fod yn dweud i fod yn llinol.
Omega o n.
A gallwn edrych ar eraill o'r hyn hefyd.
Felly, gadewch i ni edrych cyflym am ddim ond mae delweddu yma
i weld sut mae'r rhain yn gwahaniaethu eu hunain.
Rydw i'n mynd i fynd i lawr fan hyn i mewn i hyn tudalen sydd ar gael ar wefan C50 yn,
ond bydd yn boen i gael gwaith, gan ei fod yn defnyddio technoleg o'r enw
Applets Java, sy'n un o heb gefnogaeth i raddau helaeth y dyddiau hyn,
o leiaf erbyn Chrome a rhai pobl eraill.
>> A gadewch i mi fynd yn ei flaen a chyflymu hyn i fyny ac i esbonio beth sy'n digwydd.
Mae hyn yn arwydd o swigen didoli, mae'r algorithm cyntaf i ni edrych ar.
Ac mae'n delweddu mewn bod gan bob o fariau hyn cynrychioli nifer.
Po fwyaf y bar, po fwyaf y rhif.
Po leiaf y bar, y lleiaf yw'r rhif.
A beth y gallwch weld eu golwg, hyd yn oed er bod hyn yn mynd gyflym super,
yw bod y bar coch yn fel fi, cerdded yn ôl ac ymlaen gosod problemau.
Gallwch weld bod yr elfennau mwy yn wir yn byrlymu i fyny i'r dde,
a'r elfennau llai yn byrlymu i fyny at y chwith.
Ac i lawr fan hyn, os byddwn yn mewn gwirionedd yn edrych yn agosach,
gallwn mewn gwirionedd yn cyfrif y nifer o gymariaethau a chyfnewidiadau
oedd yn cael eu gwneud.
>> Ond yn hytrach, gadewch i ni edrych yn yr ail algorithm
buom yn edrych ar gynharach gyda'n gwirfoddolwyr, didoli dewis.
Yn weledol, mae ganddo effaith wahanol iawn.
Ond mae'n, unwaith eto, iawn 'n athrylithgar, yn ein bod yn cadw dewis y lleiaf nesaf
elfen, ac rydym yn cael ychydig yn lwcus.
Oedd yn teimlo y bôn yn gynt.
Ond os ydym yn rhedeg hyn eto ac eto ac unwaith eto gyda llawer o fewnbynnau,
byddem yn gweld ei bod yn wir dal i fod yn O fawr o n sgwâr.
>> Gadewch i ni wneud un un olaf yma, didoli mewnosod,
sef y trydydd algorithm buom yn edrych ar, a dwyn i gof
bod hyn yn un yn delio â'r elfennau gan ei fod yn dod ar eu traws yn eu,
ond yna mae'n efallai shifftiau pethau i wneud lle,
mewnosod elfennau lle maent yn perthyn.
>> Ac mae hyn hefyd yn dod i ben i fyny gan roi canlyniad terfynol. Nawr pob un o'r tri o'r rhai a
yn teimlo eithaf cyflym.
Ac yn wir, yr wyf yn rhedeg nhw ar glip 'n bert da.
Ond yn y bôn, maen nhw i gyd 'n bert ofnadwy, a dweud y gwir.
Mae pob un o'r algorithmau hyn hyd yn hyn bod yn rhedeg mewn O fawr o n squared
cymryd cryn dipyn o amser i redeg yn y diwedd.
>> Ac yn wir, gallwn weld ac yn teimlo bod hyn yn olaf
os byddaf yn tynnu i fyny y trydydd a'r olaf demo.
Mae hyn yn un arall delweddu sy'n mynd
i ddangos didoli swigen ar y chwith, didoli detholiad yn y canol,
ac yn rhywbeth, fel un o'n llaw yn codi awgrymwyd yn gynharach,
uno fath ar y dde.
Mae rhaniad a gorchfygu strategaeth ar y dde.
A dyna, mewn gwirionedd, yr hyn rydym yn mynd i edrych ar ddydd Mercher.
Ond gadewch i amser hyn i redeg yn gyfochrog.
Mae'n tua'r un nifer o elfennau, pob rhedeg ar yr un pryd.
Didoli swigen vs dethol math vs fath uno.
>> Yn awr, maen nhw i gyd yn rhedeg mewn theori ar yr un pryd.
Mae'r CPU yn rhedeg ar yr un cyflymder, ond rydych yn
Gall deimlo pa mor ddiflas mae hyn yn yn gyflym iawn yn mynd i ddod yn,
ac yn union pa mor gyflym pan rydym yn chwistrellu ychydig o wythnos
algorithmau sero yn gallu rydym gyflymu pethau.
>> Ac yn awr gadewch i ni gymharu hyn mewn un ffurf diwethaf.
Rydw i'n mynd i fynd yn ei flaen at wefan CS50, ble
mae gennym y ddolen terfynol ar gyfer heddiw, lle mae rhywun ar y rhyngrwyd
garedig rhoi at ei gilydd fideo sy'n cipio pa didoli gwahanol
algorithmau swnio.
Mae hwn yn fath gosod.
>> [Gwneud sain]
>> Lle rydych yn gwneud cais mor aml yn seiliedig ar uchder y bar bar.
Mae hwn yn fath swigen.
>> [Gwneud sain warped]
>> Yn dod i fyny nesaf yw-- ddod i fyny fath dethol yw-- nesaf,
lle unwaith eto, rydym yn dewis yr elfen lleiaf nesaf,
a gallwn weld ei fod yn tyfu o'r chwith i'r dde.
>> Cyfuno didoli, mae ein enillydd hyd yma heddiw.
Hysbysiad sut mae'n rhannu pethau i mewn i [Anghlywadwy] hanner a chwarteri.
Didoli Gnome, nad ydym wedi siarad am, ac yn creu eu golwg
ac audally yn dipyn o siâp a sain gwahanol.
Mynd yn ôl ac ymlaen, glanhau pethau i fyny.
Hefyd edrych ar heapsort ar y wefan boi.
>> A dyna ni.
Byddwn yn gweld y tro nesaf i chi.
>> [Whooshing A CHERDDORIAETH]