[Powered by Google Translate] [Wythnos 3, Parhad]
>> [David J. Malan - Harvard University]
>> [Mae hyn yn CS50. - CS50.TV]
>> Mae pob hawl. Croeso yn ôl. Mae hyn yn CS50, a dyma'r diwedd wythnos 3.
>> Felly, ar gyfer rhai sy'n anghyfarwydd, y llynedd lansiodd Harvard hyn a elwir y Labordy Arloesi,
neu i-lab, sydd yn adeilad gwych ar draws yr afon ar HBS gampws
sy'n agored i fyfyrwyr y coleg, myfyrwyr GSAS, myfyrwyr o bob campws ar draws,
gan gynnwys gyfadran, ac mae'n lle i ddod at ei gilydd i weithio ar bethau arloesol,
pethau arbennig entrepreneuraidd
os ydych chi a 0 neu fwy o ffrindiau yn meddwl am wneud rhywbeth entrepreneuraidd
naill ai yn ystod y dosbarth hwn, ar ôl y dosbarth, neu'r tu hwnt.
>> Felly un o'r pethau y maent yn ei wneud dros J tymor yn y tripiau hyn,
un ohonynt yw i New York, ac un ohonynt yw i Silicon Valley.
Gofod yn gyfyngedig iawn, ond ei fod yn gyfle i ochr yn ochr â MBA
a myfyrwyr graddedig ar draws y campws ac mewn gwirionedd yn treulio amser yn y meysydd perthnasol
sgwrsio i fyny startups, sgwrsio i fyny entrepreneuriaid ac yn y blaen.
Felly os oes gennych ddiddordeb, edrychwch ar y URL yma.
Mae hefyd ar gael ar y sleidiau ar-lein.
>> Oni allem tôn i lawr y sain tŷ dim ond ychydig bach?
Os hoffech chi ymuno â ni am ginio dydd Gwener yma, 1:15 pm Tân ac Iâ, os gwelwch yn dda ben yno.
Ymddiheuriadau os yw'r ffurflen wedi ei llenwi eisoes gan i chi gyrraedd yno.
Ond byddwn yn parhau â'r traddodiad ymlaen.
>> Heddiw, rydym yn parhau â'r drafodaeth ar lefel uwch o broblemau amrywiol y gallwn eu datrys,
canolbwyntio llawer llai, heddiw o leiaf, ar cod a llawer mwy ar syniadau.
Felly meddyliwch yn ôl i'r wythnos 0 pan fyddwn yn rhwygodd llyfr ffôn yn ei hanner,
amcan a oedd i wneud rhywbeth, rhaid cyfaddef, ychydig yn ddramatig
ond i anfon y pwynt nad yw chwilio oes raid iddo fod, o reidrwydd,
mor amlwg ar yr olwg gyntaf fel y byddech yn ei feddwl.
Ac efallai na fydd datrys problemau yn gyffredinol o reidrwydd bob amser y gorau -
Efallai na fydd yr ateb mwyaf amlwg o reidrwydd fod y gorau.
Felly, rydym yn cael y llyfr ffôn a dweud y gwir, mae pob un ohonom yn yr ystafell hon wedi cael y greddfau,
fwyaf tebygol, i ddechrau yn y canol wrth chwilio am Mike Smith ac yna ewch i'r chwith neu i'r dde
yn seiliedig ar beth bynnag llythyren o'r wyddor rydym yn digwydd yn y pen draw ar.
>> Ond y syniad syml bod ein pobl wedi cymryd yn ganiataol am gyfnod mor hir
Dylai wir yn dechrau dod i'r amlwg yn eich meddwl
oherwydd fel y problemau yn cael llawer mwy cymhleth nag y llyfr ffôn,
rhai un peth syml, mewnwelediad gwych yn yr hyn yn mynd i ganiatáu i ni
i ddatrys problemau yn llawer mwy cymhleth ac yn fwy diddorol,
yn eu plith rai o'r pethau yr ydym yn eu cymryd yn ganiataol y dyddiau hyn yn barod.
Mae biliynau o dudalennau gwe allan yna, ac eto Google a Bing ac yn y blaen
yn gallu dod o hyd i bethau i ni fel 'na.
Nid yw hynny'n digwydd drwy ddefnyddio chwiliad llinol, chwilio drwy'r holl dudalennau gwe posibl.
Facebook yn gallu dweud wrthych pwy eich holl ffrindiau yn neu ffrindiau o ffrindiau,
ac y gellir hefyd ei wneud yn ôl pob golwg mewn amrantiad dyddiau hyn
er bod ganddynt miliynau o ddefnyddwyr.
>> Ac felly sut y byddwn mewn gwirionedd yn datrys problemau ar y raddfa honno yn y pen draw lleihau
at syniadau rydym yn edrych arnynt yn wythnos 0 ac ychydig mwy o bobl heddiw.
Ni fyddwn yn ail-weithredu y algorithm, ond rydym yn cofio hefyd a wneuthum yn wythnos 0 ymarfer hwn
lle'r oeddem wedi bawb sefyll i fyny, yn cymryd ar y rhif 1,
ac yna cawsom bawb hunan-gyfrif drwy baru i ffwrdd, gan ychwanegu eich rhifau gyda'i gilydd,
yna hanner y criw yn eistedd i lawr ar bob iteriad.
Felly, rydym yn mynd o 500 o fyfyrwyr i 250-125 ac yn y blaen.
Ond fel y dywedasom ar ddydd Llun, y syniad grymus yn awr
oedd os ydym yn dyblu maint y broblem
a'r holl blant o'r Adran Cyfiawnder neu CE 10 daeth yn ôl i mewn i'r ystafell ac yn ymuno â ni,
yn dda, gallem yn ôl pob tebyg yn cyfrif y grŵp cyfan agregau
gyda dim ond 1 yn fwy fersiwn mawr o'r ddolen oherwydd y byddent yn unig efallai yn dyblu maint
neu mewn CE 10 oed achos ychydig yn fwy na dwbl y maint.
Ac felly byddai'n rhaid i ni dreulio ychydig mwy o amser,
ond ni fyddem yn gorfod treulio 400 neu 700 mwy o gamau.
>> Dim ond i baentio darlun hwn mewn ffordd sy'n ychydig yn llai haniaethol, gadewch i ni wedi i bawb sefyll i fyny.
Ond os na fyddai rhai ohonoch sy'n dewis i eistedd yn y gerddorfa heddiw yn meddwl sefyll i fyny,
gadewch i ni weld os allwn chyfrif i maes eich plith a oedd y person talaf yn
drwy wneud yr un math o algorithm cymharol.
Felly, os ydych yn eistedd yn y gerddorfa, fy ymddiheuriadau, ond cam 1, safant i fyny;
cam 2, pâr i ffwrdd ag unrhyw un gerllaw chi,
chyfrif i maes sydd yn dalach, ac eistedd i lawr os ydych yn fyrrach.
Yna ailadrodd.
[Fyfyrwyr grwgnach]
>> Iawn.
Iawn. Mae un yn cael ei adael yn sefyll. Beth yw eich enw? >> Andrew.
>> Andrew, chi yw'r person talaf yn yr adran gerddorfa heddiw.
>> Llongyfarchiadau. [Gymeradwyaeth a bloeddio] Iawn. Cael sedd. Felly, rydym yn dod o hyd Andrew.
Ond faint o amser wedi cymryd i mi, er enghraifft, i ddod o hyd i Andrew
yn yr adran hon gerddorfa o 50 + neu fwy o bobl?
Gallwn i fod wedi cymryd yn ddull syml a dechrau yma.
Ac yr wyf wedi 2 o bobl yn sefyll i fyny ac roeddwn i yn eu cymharu,
ac yna yr wyf yn dweud i bwy bynnag ychydig yn fyrrach, "Iawn, chi eistedd i lawr,"
ac yr wyf i'n mynd i gofio pwy oedd y person talach oedd.
Yna mi ailadrodd, ailadrodd, ailadrodd, ac yr wyf yn hongian ar y person talaf
nes i mi ffeindio rhywun ychydig yn dalach na nhw, ac ar y pwynt
y person sydd ychydig yn fyrrach rhaid i yna yn eistedd i lawr.
Ond yn y algorithm yn yr adran hon gerddorfa, os oes n ohonoch,
faint o gamau yn y algorithm yn mynd i gymryd? >> [Myfyrwyr] N.
>> Mae'n mynd i gymryd n, iawn, oherwydd yn yr achos gwaethaf, fel petai,
y person talaf yn y person olaf un fy mod yn cael dim ond drwy lwc ddrwg ar hap.
Felly, yn yr achos gwaethaf, yr amser yn rhedeg y algorithm yn llinol, mae'n n,
lle mae n yn y cyfanswm o bobl yn y gofod, maint y broblem.
Beth am y algorithm?
Mae'r ffaith eich bod i gyd yn sefyll i fyny ac yna unwaith eto hanner chi eistedd i lawr,
hanner ohonoch eistedd i lawr, hanner chi eistedd i lawr.
Sawl cam sydd wedi cymryd os oes n ohonoch chi yma?
[Myfyrwyr] N log n. >> Byddai hynny'n waeth. Mewngofnodi n.
>> Felly logio n, hyd yn oed os nad ydych yn cofio'r beth yw logarithm yw,
ar hyn o bryd, dim ond gwerthfawrogi ei fod yn ymwneud rywsut i hyn haneru a haneru a haneru.
Nid oes rhaid iddo fod yn ffactor o 2. Gallai fod yn ffactor o 3.
Ond mae'n ydyn nhw ailadrodd yr un math o ffactor fel bod maint y broblem yn cychwyn yma:
ond yna yn syth yn mynd yma, yna yma, yna yma, yna yma.
Nid ydych yn cymryd brathiadau bach allan o'r broblem, ydych wirioneddol yn torri i ffwrdd yn ei
gyda mawr dyrnod bob tro.
Felly, roedd gennym 50 o bobl, yna 25, yna 12 ½ neu 13 o bobl yn sefyll,
yna 6 ½ ac yn y blaen hyd nes sefyll yn olaf yn unig Andrew oedd ar ôl.
Felly, rydym yn mynd i alw y log o n, a gallwch ddychmygu hyn fel a ganlyn.
Dwyn i gof y llun yma lle mae algorithm llinol yn debyg i'r llinell goch yno,
y llinell felen yn y cyfrif gan 2s algorithm a ddefnyddiwyd gennym ar gyfer myfyrwyr cyfrif
yn y gorffennol, ond erbyn heddiw mae'r greal sanctaidd yn mynd i aros yn y llinell werdd
lle os ydym yn dyblu nifer y bobl yn yr adran cerddorfa neu newydd ei ddweud,
uffern, gadewch i ni gael pawb yn yr ystafell gyfan na sefyll i fyny, mor bwysig â hynny
oherwydd ein bod yn fras yn dyblu faint o bobl i lawr yma,
1 iteriad heb fod yn fwy, yn broblem.
>> Rydym wedi dod o hyd Andrew neu bwy bynnag fydd yn digwydd i fod yn dalach nag Andrew
yn y mesanîn neu yn y balconi.
Felly, mae hyn syniad syml ein bod yn cymryd cymaint yn ganiataol mewn llyfr ffôn,
sylweddoli bod llawer o leoedd cymaint o wahanol y gallwn wneud cais amdano.
Dim ond i slap rhywfaint o jargon - mewn gwirionedd, yn hytrach na jargon gyntaf,
gadewch i mi fynd at y darlun hwn yma.
Ar hyn o bryd rydym yn siarad am n a n / 2, ac yna logio n,
ond gallwn yn sicr yn dod o hyd i, fel y gwnawn yn ystod y semester,
fath arall o fformiwlâu mathemategol i ddisgrifio y syniad cyffredinol o redeg amser.
Mae'r rhain yn allan o'u cyd-destun ar hyn o bryd oherwydd y byddwn yn gweld cyn bo hir
algorithmau bod y rhain eu cynrychioli mewn gwirionedd.
>> Ond sylwi yma y llinell llinol n, y llinell syth, mewn gwirionedd yn isel iawn pwyntio ar hyn o bryd.
Dyna fath o rhith optegol yn yr ydym yn unig yn newid yr hyn yr echelin x yn cynrychioli
a'r echelin y, a gallwn wneud pwynt llinell syth mewn unrhyw gyfeiriad yr ydym ei eisiau.
Ond y rheswm pam y mae mor ymddangos yn fflat erbyn hyn
oherwydd ein bod angen i wneud lle ar y graff ar gyfer amseroedd rhedeg yn arafach o lawer.
Am y tro, yn gwybod bod yna rai algorithmau eithaf gwael mewn bywyd,
Nid yw rhai ohonynt yn cymryd camau n neu, yn well fyth, ewch camau n ond yn fwy.
Felly, uwchben y llinell n yma yn yr hysbysiad gwaelod mae n amser log o n,
a gawn ni weld beth mae hyn yn golygu cyn bo hir.
Yn fwy na hynny yn n sgwâr, ac nid ydym wedi gweld unrhyw algorithmau n sgwâr eto ond rydym am i.
A bod yn edrych yn ddrwg iawn.
Mae 2 i'r n, rhywbeth esbonyddol, sy'n teimlo hyd yn oed yn waeth.
Ac eto, yn rhyfedd ddigon, yna mae n dorri'n giwbiau, ac os ydych yn fath o feddwl ymlaen,
os ydych yn fath o wneud y math, 2 i'r n mewn gwirionedd yn dod yn llawer sythach,
llawer yn uwch i fyny na n torri'n giwbiau os ydych yn edrych ar yr echelinau yn ddigon pell allan.
Felly sylwi ar hyn o bryd yr echelau yn fympwyol 2-10 ar yr echelin x.
>> A beth mae hynny'n ei olygu?
Mae hynny'n golygu 2 o bobl at 10 o bobl yn yr ystafell.
Dyna pob dull x: maint y broblem, beth bynnag fo'r cyd-destun yn.
A echelin fertigol ar hyn o bryd yn nifer o eiliadau neu nifer o gamau -
rhywfaint o uned o amser.
Ond sylwi ei bod yn 0-60 a 0 i 10.
Ond os ydym yn fath o chwyddo allan, fel y gellid yn yr Excel neu ryw feddalwedd siartio,
ac rydym yn mynd i fyny i 200,000, sylwi bod rhywbeth fel 2 i n
yn mynd yn llwyr gorlethu amseroedd rhedeg n sgwâr,
wedi'i dorri'n giwbiau n, n log n - popeth yr ydym wedi siarad am hyd yn hyn.
Ac eto dal yw pan fyddwch yn dechrau siarad am bethau fel Facebook
lle'r ydych wedi llawer, llawer, llawer o bobl yn gysylltiedig â'i gilydd i gyd,
gennych n pobl, y gallai pob un ohonynt gymaint â ffrindiau n
os yw pawb yn fath o buddy-buddy yn y byd,
wel, dyna amseroedd n n barod, felly mae hynny'n n cyfeillgarwch posibl sgwâr,
o leiaf mewn 1 cyfeiriad, n cyfeillgarwch posibl sgwâr.
Felly, sydd eisoes yn awgrymu bod chwilio Facebook yn graff cymdeithasol, fel petai,
Gellir dechrau cael ei fynegi yn y mathau hyn o fformiwlâu.
>> Byddwn yn dod yn ôl a gwneud hyn yn llawer mwy cadarn,
ond ar hyn o bryd, y nod ar gyfer yr wythnosau nesaf mae llawer o
yn mynd i fod yn sicr i beidio â mynd am algorithmau gweithredu neu god
y pen draw gymryd amser gymaint â rhywbeth fel hyn.
Ond y peth diddorol am wyddoniaeth gyfrifiadurol os ydych yn parhau ymlaen yn y maes hwn
gymryd dosbarthiadau fel CS121, CS124, y ddau ohonynt yn gyrsiau theori,
yw bod yna mewn gwirionedd rhai problemau sy'n bodoli yn y byd hwn
yn sylfaenol, cyn belled ag y gwyddom, ni ellir eu datrys yn gyflymach
nag y gwaethaf o'r graffiau hyn mewn gwirionedd yn awgrymu.
Felly, mae llawer o broblemau agored yn y byd i wneud llawer yn well na bodau dynol yn cael hyd yn hyn.
>> Felly, gadewch i ni ddechrau, yna â'r enghraifft hon.
Gwelsom Sean cael trafferth gyda hyn camera, i gyd yn rhy lletchwith ar fideo.
Ond y gwir amdani oedd pan Sean y dasg o ddod o hyd ar fwrdd fel hyn y rhif 7,
yn cofio fy mod wedi dweud hynny, "Mae yna rhywle y tu ôl i'r darnau o bapur neu ddrysau gwyn
"Y rhif 7. Sean, dod o hyd i ni."
Ac yn rhyfeddol o anodd i wylio
oherwydd ei fod yn wir yn cael trafferth â'r broblem hon.
Ond y realiti oedd Sean gwnaeth yn ogystal ag y gallai unrhyw un yn yr ystafell yn cael ei wneud.
Cymerodd ychydig yn hirach na pherson nodweddiadol a allai fod wedi
ond cymryd yn ganiataol bod rhywfaint o tric i'r broblem hon,
roedd cymryd yn ganiataol ei fod yn colli rhywbeth.
Ac nid oedd yn helpu cannoedd o lygaid yn dwyn i lawr arno.
>> Ond y gwirionedd oedd petai'r mewnbwn i'r broblem yw criw o rifau ar hap
ac rydych yn cael eu gofyn i ddod o hyd i rhif 1 o'r fath,
y gorau y gallwch ei wneud yw chwiliad llinol.
Dechreuwch ar y chwith, yn symud i'r dde, neu ddechrau ar y dde, yn symud i'r chwith.
Retroactively, efallai y byddwn yn meddwl, "Sean, pam na wnaethoch chi yn unig cychwyn o'r pen arall?"
Wel, gallai 7 ohonynt wedi un mor hawdd bod yma ar hap,
ond yr wyf yn fwriadol roi yno oherwydd fy mod cyfrifedig nad oedd yn mynd i ddechrau ar y diwedd.
Felly, yr wyf yn fath o drin y sefyllfa, ond gallai drwy hap a damwain ar hap 7 wedi bod yn unrhyw le.
Efallai felly mae dechrau o'r pen cywir wedi bod yn well, yna,
ond beth os yw'r flwyddyn nesaf byddaf yn symud 7 rhywle arall?
Nid yw hynny'n ateb sylfaenol newydd i'r broblem -
gan ddechrau o 1 ben neu'r llall - pan fyddwch yn cael unrhyw ragdybiaethau eraill.
Felly, Sean dechrau edrych drwy'r rhifau a dywedodd, "5. Dyw hynny ddim yn fan hyn."
Yna aeth yma a gweld 19, yna mae'n seibio am tua 20 eiliad,
yna agorodd hyn ar gyfer 13, ac yna daeth yn amlwg
nad yw'n ymddangos i fod yn batrwm yma.
Nid oedd 1, 2, 3, 4 neu debyg. Roedd bylchau yn y niferoedd, nad oedd yn helpu.
Ac hefyd, y ffaith fy mod defnyddio darnau hyn o bapur rhad i dalu am hyd y niferoedd
mewn gwirionedd yn fwriadol, oherwydd os wyf yn dileu yr holl ddarnau o bapur,
rhan fwyaf ohonom, Sean cynnwys, mae'n debyg y byddai wedi bwrw golwg math o macroscopically
dweud ar y bwrdd du, ac, "O, 7 yn amlwg iawn yno." Rydym yn gwneud hynny ar unwaith.
>> A allai fod yn y ffordd y mae'r ymennydd dynol yn gweithio i ryw raddau,
ond mewn gwirionedd, ei llygaid neu feddwl, mae'n debyg, sgimio y niferoedd o'r dde i'r chwith,
o'r chwith i'r dde, canol y tu allan i - rhywbeth oedd yn digwydd ffisiolegol
fel ei fod yn teimlo fel ei fod yn digwydd ar unwaith,
ond groes hyd yn oed yn fewnol roedd rhyw fath o fethodoleg i ddod o hyd i 7.
Ac yn wir, yn awr ein bod yn sôn am araeau a strwythurau data
ac y tu mewn cof cyfrifiadur, gall yr unig beth rydym yn bodau dynol yn ei wneud
yw edrych ar leoliadau cof unigol 1 ar y tro.
>> Felly, gallai pob lleoliad arall yn ogystal yn cael eu cynnwys i fyny gyda rhywfaint o ddarn o bapur
oherwydd ni allwn weld beth bynnag. Gallwn ond wneud 1 peth ar y tro.
Felly, yn yr achos hwn, yn Sean achos, rydym yn mynd yma ac yna aethom yma
ac yna aethom yma, yma, yma, yma, got glyfar erbyn diwedd
a dim ond math o hepgor yr un yma yn fympwyol ac yn dod o hyd 7 yno.
Nid yw'r un yn arbennig iawn. Roedd hon hefyd yn allan o drefn.
Ond o'r diwedd dod o hyd 7.
Ond yn awr mae'r parod mewn gwirionedd yw bod y gorau y gallwch ei wneud pan roddir unrhyw wybodaeth
heblaw nifer didoli ar hap yn dechrau o'r chwith neu ddechrau o'r dde.
Neu Heck, gallwch hap agor drysau, ond hyd yn oed wedyn beth mae'n ei olygu i fod ar hap?
Wel, byddai'n rhaid i ni rywsut ffurfioli'r hyn mae'n ei olygu i ddechrau yma,
wedyn yn mynd yma, yna ewch yma. Sean wnaeth wych, ac roedd yn hwyl i wylio.
Beth os yn lle hynny rydym yn newid y broblem ychydig ac yn dod i fyny Sean eleni, os mynnwch?
A fyddai unrhyw un fod yn gyfforddus yn dod i fyny ar y llwyfan ac yn datrys problem ychydig yn wahanol
ac yn ymddangos o flaen y camera?
>> Gadewch i ni fynd y tu hwnt i'r gerddorfa oherwydd eich bod guys wedi cymryd rhan yn eithaf heddiw yn barod.
Beth am mewn pinc, yn yr het? Dewch i lawr. Beth yw eich enw? >> Alex. >> Alex. Iawn.
Felly, bydd Alex yn Sean eleni a bydd yn ymddangos yn y blynyddoedd nesaf
gwerth CS50 darlithoedd.
Alex, neis i gwrdd â chi. >> Neis i gwrdd â chi hefyd.
Yr her wrth law i chi yw eich bod yn ei chael ychydig yn haws
yn yr Rwy'n dweud wrthych yr un rhifau yma, ond maent yn cael eu datrys erbyn hyn.
Felly nawr eich nod yw dod o hyd i'r rhif 7.
Ac mewn gwirionedd, dylem wneud gwir hyn - nid math you're o dwyllo, fel cyfrifiadur fyddai,
drwy edrych ar yr hyn y niferoedd yn funud yn ôl.
Gyda sialc hyn mewn gwirionedd yn mynd i helpu'r holl cymaint â hynny,
ond gadewch i esgus nad ydych yn gwybod beth yr amrywiaeth gwreiddiol yn.
Mae pob eich bod yn gwybod yn awr yw bod gennych amrywiaeth o rifau didoli
allai fod wedi bylchau rhyngddynt, a bod eich nod yw dod o hyd i'r rhif 7.
Sut fyddech chi, bod dynol rhesymol fod yn, mynd ati i ddod o hyd i'r rhif 7?
>> Ewch o isel i uchel? >> Iawn. Ewch isel i uchel.
A pheidiwch rhwygo i ffwrdd. Gadewch i 'jyst eu codi i fyny fel y gallwn eu hailddefnyddio.
Iawn, felly 1. Arhoswch. Cyn i chi gadw i fynd, a oedd yn 1, yn amlwg yn anghywir.
Felly beth sy'n mynd trwy dy feddwl nesaf? Beth yw eich cam nesaf?
Yr un nesaf. >> Iawn. Yr un nesaf. Da. 3, felly yn anghywir. Beth yw eich cam nesaf?
Cadwch ar fynd. >> Mae pob hawl. Cadwch ar fynd. 5.
Felly, dal i fynd, a gadewch i mi llaw hwn i chi ar gyfer y dyfodol.
7. >> Ardderchog. Da iawn. Wedi dod o hyd i'r rhif 7. [Cymeradwyaeth]
Felly, a oedd yn dda, ond mae Sean hefyd dod o hyd i'r rhif 7.
Ac yr wyf yn dadlau nad ydych wedi eu hecsbloetio mewn gwirionedd y darn ychwanegol o wybodaeth,
sef bod y niferoedd yn cael eu datrys.
Gall Felly, rydym yn gwneud yn well? Unrhyw awgrymiadau yma? Yeah, yn ôl.
[Myfyrwyr] search deuaidd. >> Nid oes gennyf unrhyw syniad beth yw chwiliad deuaidd.
>> [Myfyrwyr] Dechreuwch yn y canol. >> Dechreuwch yn y canol. Iawn. Felly, gadewch i ni weld os allwn ni gyrraedd yno.
Felly os ydych yn hytrach na dweud wrth gychwyn o'r canol, yn mynd yn ei flaen ac yn agor y drws canol.
Mae 8 ohonynt, felly rydych chi'n mynd i gael ato ar hap dewis yr un
ychydig i'r chwith neu i'r dde. Iawn. 7! [Gymeradwyaeth] Iawn 'n glws.
Iawn, ond lle'r oedd ydym yn mynd â hyn?
Gadewch i ni Mae'n debyg dim ond er mwyn torri'r ddadl rydych wedi dechrau yma
oherwydd y gallai un mor wedi digwydd yn ogystal.
Rydym yn unig yn digwydd gwybod bod 7 oedd yno. Felly, mae hyn yn 13.
Felly, os ydynt yn trefnu ac rydym newydd ddechrau yn y canol,
beth fyddai'r cam nesaf gorau posibl wedi bod?
Ewch i'r chwith. Ac felly dyma daw y ffôn enghraifft llyfr eto.
Os yw 13 yma ac rydym yn gwybod y rhestr yn cael ei datrys,
yna pob un o'r darnau o bapur yn anniddorol i ni nawr
gan ein bod eisoes yn gwybod bod yn rhaid i 7 yn y chwith
os bydd y niferoedd yn cael eu didoli ac rydym yn dod o hyd 13.
>> Felly beth yw eich cam nesaf yma? >> Ewch i'r chwith. >> Iawn, yn dda.
Felly, ewch i'r chwith, a - aros, hey, hey, hey. Dyna dwyllo.
Felly rydych yn dod o hyd 7, ond beth oedd y algorithm rydym yn unig gwneud cais?
Dechreuwch yn y canol. >> Da. Felly beth yw'r estyniad rhesymegol i'r un syniad?
O, am ddim ond y rhain. >> Yn union. >> Felly, yr wyf yn dechrau yma. >> Da.
Felly, nawr rydym yn mynd ychydig i'r chwith eto. Mae'n 3.
Ond mae'r prydau parod diddorol yn awr yw pa un onid ydych yn rhaid i chi ofalu am?
Mae'r rhain yn 2. Mae'r rhain yn >> 2. Felly, erbyn hyn gall yr un yma fynd i ffwrdd, gall hyn un fynd i ffwrdd.
Nawr bod y broblem a oedd yn 8 wedyn oedd 4 maint yn awr yw maint 2.
Rydym yn mynd yn eithaf agos. Unwaith eto, ewch i ganol y 2 elfen.
>> Iawn. Felly, mae'n fath o anffodus bod yn awr rydym bob amser yn mynd adael oherwydd ein bod yn talgrynnu i lawr.
Ond mae hynny'n iawn oherwydd erbyn hyn rydyn ni'n ei daflu i ffwrdd hyn a phopeth arall, gan ein gadael gyda dim ond 7.
Gadewch i ni roi rownd o gymeradwyaeth. Gwelsom 7 eto. [Cymeradwyaeth] Iawn. Cadarn.
Arhoswch am dim ond 1 mwy o ail.
Er bod y math hwnnw o broses nesaf yn cymryd ychydig yn hwy nag yr oeddem yn teimlo y byddai,
dweud y gwir, eich greddf cyntaf oedd y gorau, dde? Gwelsom 7 yn syth.
Ond byddem wedi dod o hyd 7 yn gyflymach, ni waeth beth, yn yr enghraifft hon yn erbyn yr un yma
oherwydd os bydd y niferoedd yn cael eu datrys i gyd, yn debyg iawn i'r tudalennau mewn llyfr ffôn,
gallwch chi wir torri hanner y broblem allan eto ac eto ac eto.
Ac nid yw mor hawdd gweld hyn gyda dim ond 8 rhif
yn hytrach na llyfr ffôn 1,000 dudalen lle rydych yn gweld yn weledol,
ond yn yr achos yma pan Sean yn chwilio am 7,
faint o gamau yn yr achos gwaethaf wedi mynd ag ef? >> [Myfyrwyr] 7.
7 yn yr achos gwaethaf. Wel, yn yr achos gwaethaf na 7 os oes sef 8 drysau yma.
Byddai wedi mynd ag ef 8 Y camau.
>> Felly, os oes ddrysau n, gallai fod wedi cymryd Sean cwpl o flynyddoedd yn ôl camau n.
Yn awr, yn eich achos chi, Alex, o ystyried bod y niferoedd yn cael eu datrys -
a gallwn fath o chasglu hyn o ble rydym wedi bod hyd yn hyn yn y stori hon -
beth amser yn rhedeg o Alex algorithm mwy deallus
o ddechrau o'r canol ac yna ailadrodd?
[Myfyrwyr] 3. >> Felly, mae'n mynd i fod yn 3, yn fras, os byddwch yn mynd 8-4 i 2 i 1.
Felly 3 cham neu, yn fwy cyffredinol, dyna log n eto.
Unrhyw bryd y byddwch chi'n haneru a haneru a haneru a haneru,
sy'n fynegiant o syniad hwn o log n.
Ac felly y byddem wedi cymryd dim ond 3 cham, ac yn wir y gwnaeth
ar ôl i ni agor y drysau haneru a haneru,
tra byddai hyn wedi cymryd Sean tua 7 neu 8 cam.
Felly diolch ichwi am fod gyda ni eleni. >> Diolch yn fawr. Braf eich cyfarfod chi.
Diolch i Alex. Yn yr un modd >>. [Cymeradwyaeth]
>> Beth yna bydd y goblygiadau go iawn o hyn?
Nawr dychmygwch nad yw'n sef 8 drysau, sydd, a dweud y gwir, gallai pob un ohonom ddod o hyd i rywbeth
y tu ôl i ddrysau 8 yn weddol gyflym yn unig gan rwygo y darnau o bapur a mynd gyda ein greddf.
Ond beth os yw'n miliwn o ddrysau? Beth os yw'n 4000000000 drysau?
Yn achos 4000000000 drysau, ydych wirioneddol yn mynd i eisiau i fynd gyda Alex algorithm,
deuaidd chwilio gan y byddwn yn dechrau ei alw'n neu rannu a goncro, yn fwy cyffredinol,
lle rydych yn cadw haneru a haneru y broblem,
oherwydd os oes gennych 4000000000 drysau, gall sawl gwaith y byddwch yn Torrwch 4 biliwn mewn hanner?
[Myfyrwyr] 32. >> Mae'n mewn gwirionedd yn 32. Gallwch weithio hyn allan ar ddarn o bapur neu yn eich pen.
Rydych yn mynd 4000000000-2000000000 to 1 biliwn i hanner biliwn, i 250 miliwn, dot, dot, dot.
Ac os ydych yn gwneud allan y cwestiwn, rydych chi'n mynd i wir, yn cael 32,
ac sydd mewn gwirionedd yn ymwneud â gwyddoniaeth gyfrifiadurol oherwydd ein bod fel arfer yn cyfrif mewn pwerau o 2.
2 i 32 yn digwydd i fod yn 4 biliwn.
Felly, mae llawer o berthnasol i'r math yma o bwerau 2 mewn gwyddoniaeth gyfrifiadurol.
>> Ond beth tua 8 biliwn? Faint o gamau yw bod mynd i'w cymryd os oes 8000000000 drysau?
[Myfyrwyr] 33. Felly >> 33. Beth os oes 16000000000 drysau? Faint o gamau yw bod mynd i gymryd?
[Myfyrwyr] 34. >> 34. Gallem fath o barhau â'r syrffed ad. Ond mae hynny'n beth pwerus.
Gallwch gyflwyno biliynau o fewnbynnau yn fwy at eich problem, ond, nid oes llawer mawr,
'ch jyst yn cymryd 1 brathiad ychwanegol y tu allan ohono ac felly yn rhoi rhywbeth i ni fel chwiliad deuaidd
neu rannu a goncro, yn fwy cyffredinol.
Ond rwy'n fath o dwyllo yma, dde?
Yn achos Alex algorithm, roedd ganddi fantais dros Sean.
Roedd hi'n gwybod bod y niferoedd hyn yn cael eu datrys, ond nid Alex oedd yn rhaid i'w datrys ei hun.
I ymlaen llaw yn dod i fyny at y bwrdd du a math o gwneud yn siŵr
y tynnais nhw i gyd allan er mwyn datrys, yna rwyf yn gorchuddio gyda phapur.
Ond faint o waith oedd yn cymryd i mi?
Os ydym wedi dechrau i ffwrdd gyda rhifau hyn mewn rhyw fath o drefn sy'n ymddangos ar hap -
yn yr achos hwn y niferoedd hyn symlach, 1 drwy 8 yma -
sut ydym yn mynd ati i drefnu gwerthoedd hyn?
Os oeddech yn ddynol roddir y dasg hon, pa fath o ddull sythweledol eich bod yn cymryd
i roi trefn criw cyfan o rifau?
Mae'r pethau hyn yn cael eu gosod allan fel darnau pos. Yeah.
>> [Myfyrwyr] byddwn yn cymryd pob rhif ac yn ei gymharu i bob un
a dal i fynd i'r chwith. >> Iawn, yn dda.
Felly, yn cymryd pob rhif, ei gymharu i'r un nesaf ato,
ac yna dim ond yn dal i symud ar hyd y math rhestr o rejiggering pethau wrth i chi fynd.
Felly dyma ni yn cael cyfle i efallai ychydig mwy o Folks i gymryd rhan.
A oes gennym 8 o wirfoddolwyr byddai mwy sydd wrth eu bodd i ddod o hyd?
Nid yw pwysau ychydig yn llai ers i chi yw'r unig un. 1, 2, 3, 4, 5, 6, 7, 8.
Dewch i lawr. Rydych guys yn mynd i fod y rhifau 1 drwy 8.
Gawn ni weld os na allwn wneud hyn didoli gyfer Alex lawer yn yr un modd yr wyf yn gwneud hynny o flaen llaw.
1, 2, 3, 4.
Mynd yn ei flaen ac os hoffech, llinell i fyny ar y llwyfan rhwng y stand cerddoriaeth a mi yma
yn yr un drefn ag y sleid ar y sgrin.
Uh-oh.
Byddwn yn gweithio i chi yn yr enghraifft nesaf. O, aros, aros. Yma rydym yn mynd. Arhoswch.
Mae'r enghraifft nesaf yn awr. Dyma chi fynd. Rhif 8. Dewch ar i fyny.
Mae pob hawl. Trefnu eich hunain yn ôl i hyn.
Llithro ychydig bach ar ochr y gerddoriaeth yn sefyll yma.
Felly mae gennym 4, 2, 6 - mynd i mewn yno, dros yma, iawn yno - 3.
Yeah. Iawn. Rydych yn mynd dros yma. Na, byddwch yn aros yno.
Yeah, iawn yno. Rhif dwi'n anghywir. Iawn yno. Iawn, da iawn. Iawn.
Felly nawr gadewch i ni eu didoli mewn gorchymyn cynyddol.
>> Sut alla i fynd ati i wneud hyn?
Mae'r algorithm a gynigiwyd funud yn ôl yn pam nad ydym yn unig yn cymharu
y Folks sydd yn fath o nesaf at ei gilydd ac yna ddatrys unrhyw gamgymeriadau,
symud o'r chwith i'r dde.
Felly yma mae gennym 4 a 2, yn amlwg allan o drefn. Gadewch i ni gyfnewid chi. Iawn.
Felly nawr rwy'n mynd i symud i lawr y llinell. 4 a 6, Na. [Chwerthin]
6 ac 8, 'n bert da. 8 a 1, gadewch i mi gyfnewid i chi guys. Mae pob hawl.
Felly, 8 a 3, cyfnewid i chi guys.
8 a 7, gadewch i mi gyfnewid i chi guys. 5 ac 8, yn rhagorol.
Wyf yn rhoi rhestr i chi datrys.
Mae pob hawl. Felly, nid yn eithaf.
Ond mae'n well oherwydd y niferoedd mwy - achos ym mhwynt 8 -
wedi math o bubbled i fyny o'r chwith draw i'r dde.
Felly cefais 1 o yn iawn, ond mae'n teimlo fel hyn nid oedd yn datrys y broblem.
>> Felly byddai hyn yr ydych yn bwriadu rydym yn ei wneud nesaf? >> [Myfyrwyr] Cadwch wneud hynny. >> Rydym yn cadw wneud hynny.
Ac yn sylweddoli, unwaith eto, rydym yn gosod pethau i fyny at jyst yn cael yr holl bobl
math o ddeallus trefnu eu hunain yn seiliedig ar y llun,
ond erbyn hyn mae'n rhaid i ni fod yn llawer mwy trefnus.
Mae'n rhaid i ni fod yn algorithmig yn ei gylch fel pe rydym yn ysgrifennu cod -
yn yr achos hwn pseudocode lafar.
Felly, gadewch i mi jyst yn ceisio hynny eto. Oedd yn gweithio'n eithaf da. Nid oedd yn datrys.
Ond pan fydd yn amau, dim ond ceisiwch a cheisiwch eto. Felly, 2 a 4, nid oedd yn helpu anymore.
4 a 6. Ah! 6 a 1, ychydig yn well yn awr.
6 a 3, yn dda. 6 a 7, 7 a 5, 7 ac 8, yn dda.
A ydych yn gwybod, mae'n debyg y gallaf anwybyddu 8 yn awr oherwydd ei fod ar ddiwedd y rhestr.
Efallai nad ydym yn rhaid i chi boeni am rywun yn mynd heibio iddo.
Ond gadewch i ni weld os bydd hynny'n dybiaeth ddiogel.
Nawr rhestr yw - damn - nid didoli. Gadewch i ni geisio hyn eto.
Felly, 2 a 4, 4 ac 1, 4 a 3.
4 a 6, yn dda. 6 a 5, yn dda.
6, 7, ac 8, yn dda. Ond rhybudd y gall, Fi jyst aros yma yn awr ac yn stopio yma nawr?
[Myfyrwyr] Ydy. >> Yeah?
Beth os oes un ohonoch wedi bod yn rhif 9 yr holl ffordd dros yno?
Byddai wedi cael ei datrys. >> Da. Byddai wedi cael ei datrys y tro cyntaf o gwmpas.
Da. Felly, gadewch i ni fynd yn ôl eto. Rydym bron yno.
1 a 2, 2 a 3, 3 a 4, 4 a 5, 5 a 6, 6 a 7, 7 ac 8.
>> Yr wyf yn ei wneud yn awr ond, unwaith eto, rwy'n cyfrifiadur sydd ond yn gallu gwneud yr hyn rwy'n gwybod ei wneud,
ac a gofiaf yn unig nawr yw fy mod mewn gwirionedd yn unig wnes i dipyn o waith.
Rhywbeth newid yma.
Felly, nid wyf wedi cadarnhau technegol weledol neu algorithmically bod y rhestr hon yn cael ei ddatrys yn wir.
Felly, dim ond ar gyfer mesur da, dim ond i fod rhefrol am hyn, gadewch i ni wneud y tro hwn 1 yn fwy.
Felly, 1 a 2, 2 a 3, 3 a 4. A ydych yn gwybod beth?
Dim ond ar gyfer mesur da, dw i'n mynd i gadw trac ar fy llaw y tro hwn
faint o gyfnewid wyf yn gwneud yn union fel fy mod yn gwybod faint o waith wyf wedi ei wneud mewn gwirionedd.
3 a 4, 4 a 5, 5 a 6, 6 a 7, 7 ac 8. Dim cyfnewid.
Felly nawr byddwn yn gyfreithlon yn idiot i wneud hyn eto
oherwydd os wyf yn gwneud dim gwaith drwy y bwlch hwn y bodau dynol,
yna mae'n amlwg y mae hynny'n mynd i ddigwydd eto os nad oes un sy'n fath o hap
adversarially symud eu hunain o gwmpas. Felly nawr gallaf stopio.
Nawr gadewch i ni ofyn y cwestiwn, faint o waith oedd hyn mewn gwirionedd yn cymryd i mi?
Faint o gamau oedd hynny'n ei gymryd? >> N sgwâr.
Yeah, felly n sgwâr. Ble ydych chi'n cael n sgwâr o?
Mae'n rhaid i chi wirio pob NUM -
Mae rhifau n, ac mae'n rhaid i chi wirio bob rhif gyda rhifau n arall.
Da. >> Felly, mae n sgwâr. >> Da.
>> Felly, mae'n teimlo fel y gallai fod yn dda iawn yn n sgwâr, dde?
Mae wedi n o'r rhain guys, 8 yn benodol yn yr achos hwn,
ond bob tro rwy'n mynd drwy'r rhestr hon yr wyf yn cymharu y person cyntaf yn erbyn yr ail,
yr ail yn erbyn y trydydd eto ac eto ac eto,
a phan gefais hyd y diwedd, beth wnes i? Rwy'n redid hynny.
Felly, os ydym yn cyffredinoli esboniad hwn, rydym wedi n pobl
ac fy mod yn gwneud, yn amlwg, 8 cam, n grisiau, bob tro y byddaf yn mynd drwy hyn algorithm.
Ond faint o weithiau yn yr achos gwaethaf oes rhaid i mi fynd drwy'r rhestr yma o bobl?
[Myfyrwyr] N amser. >> Mae'n debyg n, iawn, oherwydd yn yr achos gwaethaf,
beth mae'n debyg y trefniant achos gwaethaf o'r rhain guys o gael-fynd?
Os ydynt yn gwrthdroi yn gyfan gwbl er mwyn
oherwydd dim ond mae'n debyg feddyliol, let's - Beth yw eich enw? >> Bowen.
Bowen. Iawn. Felly Bowen, dewch draw yma am ychydig funudau'n.
>> Gadewch i ni dybio bod Bowen oedd yma ar ddechrau'r algorithm,
ac nid ydym yn gwybod beth mae pawb arall yn gwneud, ond Bowen yma, yn ôl yr algorithm -
ac os ydych am i ychydig dro gyda mi - yn mynd i swigen i fyny, fel y gwnaeth y tro cyntaf o gwmpas,
yr holl ffordd hyd y diwedd.
Ond mae'n debyg bod y person nesaf i Bowen oedd y rhif 7.
Rhaid i mi fynd yn ôl a chael rhif 7, sy'n golygu rhaid i mi fynd yr holl ffordd yn ôl yma.
Nawr rhaid i mi gael bod cerdded yr un gyda'r person sydd yn rhif 7.
Ond beth os hynny rhif 6 yn nesaf iddo hefyd?
Yna rhaid i mi fynd yn ôl a chael 6.
Felly, unwaith eto, ar bob fersiwn o hwn yn ddolen rwy'n siarad â phob un o'r bobl n,
ac efallai y bydd rhaid i mi wneud n o'r teithiau cerdded hamddenol i wneud yn siwr fy mod yn tynnu
pob un o'r elfennau mwyaf ôl ac yn ôl ac yn ôl i'r ddiwedd y rhestr.
Pethau Felly n n amser yn unig yw gwaith n n n neu sgwâr.
>> Felly dyma eisoes gennym algorithm sy'n mwyach n, dyw hynny ddim yn bellach n log,
mewn gwirionedd mae'n waeth nag unrhyw beth rydym wedi ei wneud o'r blaen.
Felly, Alex math o got 'n ffodus fy mod yn gwneud yr holl waith pob golwg o flaen llaw ar gyfer ei,
yr holl waith drud, er mwyn iddi allu eu mwynhau yn y algorithm chwiliad deuaidd,
sy'n log o n.
Ond mae hyn yn gyson â dydd Llun thema.
Rydym yn rhoi ychydig mwy o le, rydym yn defnyddio darnau mwy, er mwyn cyflymu ein amser yn rhedeg.
Mae cymaint fel mae y fasnach-off rhwng amser a gofod,
gallai hefyd newydd fod yn cyfaddawdu rhwng amser a dreuliwyd i fyny math flaen o gael pethau'n barod i fynd
ac mewn gwirionedd yn gweithredu fel algorithm chwilio. Gadewch i ni geisio un arall.
Os na fyddech guys meddwl dim ond yn gyflym ad-drefnu eich hunain i gyd-fynd hynny eto,
gadewch i ni roi cynnig ar rywbeth ychydig yn wahanol os nad yw'n mor syml
fel dim ond atgyweiria holl gamgymeriadau pairwise, sydd yn super 'n athrylithgar.
Gadewch i ni yn lle hynny fod ychydig yn fwy bwriadol a gwneud hyn.
Mae hyn yn un rhy byddwn yn cynnig yn ôl pob tebyg 'n bert' n athrylithgar.
>> Gadewch i ni ddewis y person lleiaf o'r rhestr eto ac eto. Felly, yma rydym yn mynd.
4, chi yw'r person lleiaf rwyf wedi weld hyd hyd yn hyn,
felly dwi'n mynd i feddyliol gofio bod at jyst yn pwyntio ar chi ar hyn o bryd.
2. Ooh! Anghofiwch am rif 4. Fi jyst dod o hyd i'r elfen newydd lleiaf yn y rhestr hon.
Rydw i'n mynd i fath o gofio hynny. 6, 8.
Ooh! 1. Hwyl fawr. Felly nawr rwy'n mynd i gofio rhif 1.
Rydym yn gwybod bod 1 yw'r lleiaf, ond yr wyf fi yw'r cyfrifiadur. Beth os oes 0?
Beth os oes -1? Rhaid i mi ddal ati.
Felly 3, 7, 5, Na. Iawn. Felly, rhif 1 oedd y lleiaf.
Gadewch i mi eich dewis o'r rhestr - we'll dilyn y ffordd hon -
ac yn eich rhoi fympwyol ar ddechrau'r rhestr.
Yn awr, arhoswch funud. Yr wyf yn fath o twyllo.
Os yw'r rhain yn guys yn cynrychioli nid yw'n rhestr o 8 o bobl ond yn hytrach yn array,
8 darnau o gof cyffiniol - ydych chi'n meddwl camu yn ôl am ychydig funudau'n?
Does dim mewn gwirionedd lle i chi hawl yma.
Felly sut rydym yn gwneud lle ar gyfer - beth yw eich enw? >> Sammy. >> Sammy.
Sut rydym yn gwneud lle ar gyfer Sammy?
>> Rydym yn symud y n sydd ger fy mron. >> Iawn.
Felly, gallem symud y bobl n sydd o'i flaen ef,
felly os ydych guys am cymryd 1 bwriadol, cam dramatig ar y chwith.
Maent i gyd yn gwneud hynny ar y cyd, ond y tro diwethaf i mi ysgrifennodd rhai cod,
nad ydych yn gallu datrys o symud llawer o bethau i gyd ar unwaith.
Gallem wneud hynny mewn dolen, symud pawb unwaith ar y tro.
Felly, os na fyddech yn meddwl guys camu yn ôl i'r dde,
a Sammy, pe baech yn gallu camu yn ôl oherwydd mae dal oes lle i chi,
nawr gadewch i wneud hyn. Lle'r oedd Sammy funud yn ôl? Iawn yno.
Felly, mae yna fwlch yno. Felly, gallech symud i mewn i Sammy yn fan a'r lle.
Nawr person nesaf i fyny ac yn awr person nesaf, sydd bellach person nesaf. Nawr mae gennym le i Sammy.
Yn awr, mae rhywun o'r gynulleidfa - a oedd yn dda, a oedd yn gywir,
yn teimlo ychydig o amser - beth gyflymach? Yeah.
[Myfyrwyr] Mae amrywiaeth newydd? >> Beth sy'n bod? >> [Myfyrwyr] Mae amrywiaeth newydd? >> Iawn, yn dda.
>> Felly, yn gyson â'r thema hon o ddim ond masnach-offs, pam nad ydw i'n jyst yn gwneud casgliad newydd
ac yna bydd yn cael ei Sammy nofio yn y gofod o flaen y bobl, er enghraifft,
a gallwn dim ond dechrau llenwi casgliad newydd yn gyfan gwbl. Byddai hefyd yn gweithio.
Ond dydw i ddim ddiddordeb yn ei wario mwy o le heddiw. Beth yw ymagwedd arall?
[Myfyrwyr] Cyfnewid. >> Iawn. Gallai Rydym yn unig cyfnewid y 2 guys. Beth yw eich enw?
Mario. >> Mario. Felly Mario, oeddech ar hyn o bryd yma.
Sammy, a allwch chi yn ôl i fyny am ychydig o bryd? Mario yma.
Nid oes gennym le i chi anymore, felly os na fyddech yn meddwl mynd i'r lle Sammy yw,
byddwn yn rhoi Sammy yma, ac yn awr byddwn i'n dadlau bod Sammy gweithrediad cyfnewid yn llawer cyflymach.
Gwnaethom 1 llawdriniaeth i gyfnewid hyn guys, neu efallai 2 i gyfnewid hyn guys,
ond doedden ni ddim yn ei wneud 1, 2, 3, 4, fel bod yn teimlo'n well. Yn awr, arhoswch funud.
Yr wyf yn fath o wneud y broblem yn waeth oherwydd rhif 4 yn fath o agos at y dechrau.
Nawr rhif 4 yn ychydig yn agosach i'r perwyl hwn, ond doeddwn i ddim wir yn gwybod nac yn poeni am hynny.
Felly, mae hyn yn unig yw lwc ddrwg bod rhif 4 yn ychydig ymhellach i ffwrdd oddi wrth ei le tynghedu.
Felly, gadewch i ni bellach yn ailadrodd y algorithm.
>> I grynhoi, cyn belled ag y stori oedd, i gyd wnaethom oedd cerdded drwy'r rhestr
chwilio am y person lleiaf rhifo.
Felly nawr gadewch i ni wneud hynny eto. Nid ydym yn rhaid i chi boeni am Sammy anymore.
Gallwn jyst yn mynd yma. Ooh! Rhif 2. Dyna nifer eithaf bach.
6, 8, 4, 3, 7, 5. Iawn, yn dda.
A diolch byth, drwy gyd-ddigwyddiad, nid oes gennyf i symud - >> Willie.
Willie oherwydd ei fod yn yn ei le ar hyn o bryd.
Gadewch i ni wneud hyn eto ac yn anwybyddu y 2 guys.
6. Dyna nifer eithaf bach. Ooh! 8 yn bendant yn fwy.
4. Gadewch i ni ganolbwyntio ar 4. Ooh! 3 yn hyd yn oed yn well.
7 a 5. Felly, beth ydym yn ei wneud yn awr - >> Roger. >> Roger?
Gadewch i ni gyfnewid ag ef gyda rhif 6.
Felly os byddai 6 a 3 yn hoffi cyfnewid,
rydym wedi awr yn fath o gotten ffodus bod 6 yn agosach at lle y dylai hi fod,
ond mae'r un cyd-ddigwyddiad yma. Felly, gadewch i ni yn awr yn mynd yma.
8 yn nifer eithaf bach. Ooh! 4 yn llai.
6, 7, 5. Beth ydyn ni'n wneud yn awr? Swap >>. >> Yn union.
Felly nawr gadewch i ni wneud y math hwn o gyflymach.
8, 6, 7, 5. Ble mae 5 yn mynd? Da. Iawn.
6, 7, 8. 6 yn cael i aros ble mae hi. Beth yw eich enw? >> Rosalie.
Rosalie yn cael i aros ble mae hi. 7 yn dod i - Gadewch i ni weld. 7, 8. Iawn.
Hynny 7 yn dod i aros ble mae hi. Beth yw eich enw? >> Amna. >> Amna.
>> Felly, Amna yn cael i aros lle mae hi, a rhif 8 yn barod lle y dylai bellach fod.
Iawn, yn dda. Mae'n teimlo fel ein bod dim ond creu gwaith ar gyfer ein hunain yma, er.
Beth yn y pen draw yr amser yn rhedeg y algorithm?
Os ydym yn meddwl am y bobl hyn nid fel 8 ond fel n? >> Mae'n n.
Mae'n n camau, ond rydym yn gwirio bob tro.
Iawn. N ond eich bod yn gwirio bob tro?
Iawn, ond os yw'n n gamau na ddylai, yr wyf wedi gallu datrys chi gan jyst yn mynd 1, 2, 3, 4?
Oh! Iawn, mae hynny'n wahaniaeth mawr.
Felly n sgwariodd pam? Beth sy'n digwydd mewn gwirionedd?
Mae pobl n yn y rhestr hon, ond i ddod o hyd i'r person lleiaf yn y rhestr
yn yr achos gwaethaf, faint o gamau oes rhaid i mi gymryd? N. >>
>> N, iawn, oherwydd yn yr achos gwaethaf, rhif 1 yn yr holl ffordd dros yno,
felly rhaid i mi fynd i gael ef neu hi.
Ac yna pan oeddwn yn olaf sylweddoli 1 oedd y lleiaf, yna mae'n eithaf cyflym i gyfnewid eu cyfer.
Ond yn awr rhaid i mi ddechrau o'r dechrau ac yn edrych i bwy?
Mae'r person nesaf lleiaf, sef 2. Ble yn yr achos gwaethaf yw 2?
O, fy Nuw. Mae'n holl ffordd dros yma ar y diwedd.
Felly, yn awr yr wyf wedi gwneud un arall camau n, un arall camau n.
Ac os ydym wedi cael pobl n ac yn yr achos gwaethaf y person lleiaf yw n camau i ffwrdd,
dyna unwaith eto n n gwaith, ac felly rydym unwaith eto wedi n sgwâr.
Nid yw hyn yn teimlo mor dda.
Ac yn wir, hyd yn oed yn yr achos gorau - mae'n debyg eu bod yn dechrau didoli oddi ar -
faint o gamau mae'n ei gymryd i mi ddefnyddio'r algorithm rhoi trefn ar y bobl n?
N sgwâr. >> Clywais n sgwâr. Pam n sgwâr?
Oherwydd bod yn rhaid i chi wirio bob tro. >> Yeah.
Ac mae'n rhaid i chi eu cyfnewid. >> Er ein bod bodau dynol yn fath o omniscient
yn yr ystyr weledol y gallwn dim ond math o weld bod hyn yn didoli,
Nid yw cyfrifiadur yw bod smart.
Mae'n mynd i edrych yma ac yma ac yma,
ond os bydd yr hyn mae'n chwilio amdano yw'r elfen leiaf,
chi ond yn gwybod eich bod yn dod o hyd i'r elfen lleiaf gan yr hyn pwynt? Unwaith y byddwch chi yn y diwedd.
Ond ar y pwynt hwnnw rydych wedi dod o hyd dim ond yr elfen ar hyn o bryd lleiaf.
Dydych chi ddim o reidrwydd yn gwybod unrhyw beth arall am gyflwr y byd.
Felly, rhaid i chi fynd eto ac eto ac eto.
>> Felly, y tro hwn Fi 'n sylweddol yn edrych yn fud gan fy mod yn gwirio, iawn, 2, chi yw'r lleiaf,
ond nid wyf yn gwybod bod cyfanswm eto.
3, 4, 5, 6, 7, 8. Iawn, yn dda. 2 oedd yn wir y lleiaf.
Nawr, gadewch i ddod o hyd i'r lleiaf nesaf. Iawn.
3, rydych ar hyn o bryd y lleiaf. Gadewch i ni weld. 4, 5, 6, 7, 8. Iawn, got 'n ffodus eto.
3 yn wir yn y lle iawn. Ond dw i'n mynd i ddal i wneud hyn eto ac eto ac eto.
Sut allwn ni wneud erioed mor ychydig yn well?
Yn hytrach na chael pobl yn swigen i fyny pairwise o'r lleiaf i'r mwyaf
ac yn hytrach na mynd yn ôl ac ymlaen drwy'r rhestr dewis y person yna lleiaf,
pam nad ydym yn hytrach gwthiwch y bobl i mewn i gam restr newydd wrth gam?
Gadewch i ni geisio hyn. Nawr, gadewch i mi alw hyn yn peth fath gosod.
Felly dyma ni yma. Rhif 1. Nid wyf yn poeni am unrhyw un arall yn y rhestr hon.
Fy nod ar hyn o bryd yw rhoi rhif 1 ar ddechrau'r rhestr datrys.
Ac yr wyf i'n mynd i gynnig ers i mi yn unig yn cael 8 darnau o gof,
fympwyol ar hyn o bryd rwy'n y wal rhwng fy rhestr i fod heb eu didoli,
ac unrhyw un sydd tu ôl i mi yr wyf i'n mynd i hawlio yn cael ei datrys.
Felly, yn awr mae gennym rhif 1.
Wyf i am osod ef yn fy rhestr datrys, felly dwi jyst yn mynd i symud fy wal dros yma,
ac yn awr y gallaf hawlio y rhestr hon yn cael ei datrys, y rhestr hon yn cael ei heb eu didoli - o leiaf cyn belled ag y gwn i.
Ni allaf weld yr holl rifau ar unwaith.
>> Nawr Yr wyf yn digwydd i ddod ar draws rhif 2. Beth ddylwn i ei wneud ag ef?
I fewnosod chi nawr yn y rhestr datrys. Ond sylwch pa mor hawdd oedd hynny.
Fi jyst yn rhaid i edrych. Rhif 1 yno. O, yn amlwg 2 yn mynd ar ochr y rhif 1.
Nawr beth ddylwn i ei wneud gyda 3? I fewnosod i chi yn y rhestr datrys. Ond a oedd yn hynod hawdd.
Mae hyn yn super hawdd, mae hyn yn super hawdd, mae hyn yn super hawdd, super hawdd, hawdd super.
Ac yn awr mae popeth yn datrys y tu ôl i mi, a faint o gamau oedd hynny'n ei gymryd?
[Myfyrwyr] N. >> Felly, mae n yn unig. Rydym yn got 'n ffodus.
Dim ond n pham? >> [Myfyrwyr] Oherwydd bod y rhestr gael ei ddatrys.
Mae'r rhestr yn cael ei datrys eisoes. Felly, rydym yn got 'n ffodus.
Ond rydym yn cynllunio algorithm y tro hwn sy'n manteisio ar y math hwnnw o lwc,
y senario achos gorau, drwy beidio â gwastraffu amser diangen.
Felly, mae gennym yn awr yr hyn y byddwn yn galw math swigen
lle mae pobl yn fath o swigen i fyny pairwise.
Erbyn hyn mae gennym fath dethol lle rydym yn dynnaf y person lleiaf eto ac eto.
Ac yn awr mae gennym fath mewnosod lle rydym yn fath o rhagweithiol rhoi pobl lle maent yn perthyn
mewn rhestr didoli gynyddol.
Os gallem, rownd o gymeradwyaeth ar gyfer y guys yma. [Cymeradwyaeth]
Gadewch i ni gymryd ein 5-munud egwyl yma.
A phan fyddwn yn dod yn ôl, byddwn yn chwythu pob un o'r algorithmau allan o'r dŵr
gyda rhywbeth gwell. Mae pob hawl. Diolch yn fawr iawn. Gallwch gadw rhai fel cofroddion.
Mae pob hawl. Rydym yn ôl.
>> Ac i ailadrodd gyflym go iawn, cawsom ymagweddau hyn 3 gwahanol didoli,
holl bwynt oedd i gyrraedd y pwynt lle mae rhywun fel Alex
Gallai chwilio rhestr o rifau gyflymach na rhywun fel Sean gallai.
Ac er bod gennym enghreifftiau syml o'r fath gyda 8 rhif,
gallech allosod yn hawdd i 8 tudalen ar y we, 8000000000 tudalennau gwe,
neu 800,000,000 ffrindiau ar Facebook.
Felly, gall y algorithmau yn sicr raddfa i'r mathau hynny o werthoedd,
a'r syniadau yn y pen draw yr un fath.
Fath swigen Felly oedd y cyntaf lle rydym yn fath o swigod i fyny y person mwyaf
yr holl ffordd i'r dde drwy gyfnewid pobl pairwise.
Yna cawsom yr hyn y byddwn yn galw fath dewis lle yr wyf yn ychydig yn fwy bwriadol
yn cadw yn edrych drwy'r rhestr, dewis y nifer lleiaf eto ac eto ac eto,
y canlyniad rhesymegol o'r rhain yw bod y rhestr yn cael ei datrys yn y pen draw.
Yna yn y trydydd, yr wyf mewnosod pobl yn eu lle priodol,
ac rydym yn gwneud yn enghraifft contrived o ran bod y rhestr yn cael ei datrys yn barod,
ond a oedd i anfon y neges bod yn achos fath mewnosod, yn
gallwch gael lwcus.
Os yw'r rhifau yn cael eu datrys yn barod, mae'n dim ond yn mynd i fynd â chi n camau i gadarnhau cymaint,
tra fath dethol ydych weledigaeth twnnel ychydig yn fwy
ac nad ydych byth yn sylweddoli bod y rhestr yn cael ei datrys eisoes.
Felly, gadewch i ni weld math swigen ar waith yma.
Yn yr enghraifft ganlynol, rydym chi ar fin i weld bariau fertigol
y mae ei uchder yn cynrychioli rhifau fel y gallwn ddatrys o delweddu didoli digwydd.
Po leiaf y bar, y lleiaf yw'r rhif, y mwyaf y bar, y mwyaf fydd y rhif.
>> A byddwn yn ei chwarae yn y cyflymder ddiofyn.
Mae'n mynd i symud yn gyflym ychydig ar hyn o bryd, ond mae coch yn beth sy'n dangos 2 far
cael eu cymharu ochr yn ochr.
Ac os ydych yn gwylio yn agos, beth fydd yn digwydd os bydd y bariau yn allan o drefn,
yr un llai yn cael ei symud i'r chwith, yr un mwyaf i'r dde,
ac yna eich bod yn cadw hyrwyddo.
Felly, os ydym yn gwneud hyn dro ar ôl tro, yn sylwi bod y bariau lleiaf
yn mynd i gadw inching eu ffordd i'r chwith
a'r bariau mwyaf yn mynd i gadw inching eu ffordd i'r dde.
Ac yn wir, rydym yn dechrau gweld patrwm yr holl ffordd ar yr ochr dde-law
yn union fel rydym yn gweld 8 a yna 7 yn y pen draw yn byrlymu i fyny i ben pellaf ein rhestr dynol.
Felly, mae hyn yn mynd i yn gyflym iawn cael braidd yn ddiflas, felly gadewch i mi roi'r gorau i hyn am eiliad.
Gadewch i mi newid y cyflymder i fod yn llawer cyflymach.
Dydw i ddim yn newid y algorithm, Im 'jyst yn gwneud y animeiddio yn digwydd yn gyflymach.
Fath swigod Still, algorithm un,
ond erbyn hyn gallwch weld llawer cyflymach na'r arddangos ar lafar
bod yr elfennau mwyaf yn wir yn byrlymu i fyny i'r brig.
>> Fel o'r neilltu, mae'r sgwariau bach yn y gwaelod ar y chwith a gwaelod dde
yn unig atgoffa ychydig o ran faint o cymariaethau rydych chi'n ei wneud.
Ond am nawr, gallwn ganolbwyntio ar y pyramid sydd wedi cymryd siâp, ac yno y mae'n mynd.
Mae'r elfen lleiaf ar y chwith, y mwyaf ar y dde, a phopeth arall yn y canol.
Nawr gadewch i ni yn hytrach yn edrych ar fath dethol.
Rydw i'n mynd i fynd yn ei flaen a tharo Stop. Rydym yn mynd i gael set ar hap newydd o fariau.
, Didoli Dewis galw i gof, yn mynd drwy'r rhestr eto ac eto ac eto,
plicio allan yr elfen lleiaf. Felly dyma fath dethol.
Mae'n edrych fel mae 'na llai o waith yn digwydd yn awr oherwydd nad ydym yn cymharu pairwise
ond rydym yn unig didoli o geirios dewis yr elfennau lleiaf o'r dde i'r chwith.
Hynny'n cymryd ychydig iawn o amser, felly mae deuoliaeth yn barod.
Nid yw'r ffaith bod algorithm yn dweud i gymryd n amser sgwâr, fel math swigen
ac fel math dethol, y rhai yn wir yn amseroedd gwaethaf rhedeg.
Er enghraifft, yn achos, gadewch i ni ddweud, didoli dewis,
Fi 'n weithredol mod yn dewis y person lleiaf a rhoi iddo ef neu hi yma,
yna rwy'n ei wneud eto, yna rwy'n ei wneud eto,
ond roedd optimization bach y gallwn i wneud.
>> Cyn gynted ag y mi symud rhif 1 yma - Sammy yn yr achos hwnnw -
beth oedd angen i mi ei wneud gydag ef ar ôl hynny? >> [Myfyrwyr] Gadewch iddo.
Gadewch iddo, dde? Dim byd.
Nid oedd rhaid i mi erioed siarad â Sammy eto oherwydd os wyf wedi dewis yr elfen lleiaf
ac a'i rhoddodd ef yma, pam gwastraffu amser yn mynd i ddiwedd fy rhestr gyfan?
Ar y fersiwn nesaf gadewch i mi mewn gwirionedd yn symud yn unig i rhif 2, dim ond i rif 3.
Felly, mewn gwirionedd, nid oeddwn yn gwneud pethau n n amser.
Mod yn gwneud pethau n, yna n - 1 pethau, yna n - 2 beth, yna n - 3 pheth,
Yna, n - 4, dot, dot, dot.
Mae gennym dipyn o gyfres geometrig, a dim ond yn golygu
rydych yn adio rhifau yn gynyddol llai.
Heb n + n + n + n, ond n + 7 + 6 + 5 + 4 + 3 + 2 + 1.
A beth sy'n gyffredinol yn gweithio allan i fod -
Rydw i'n mynd i llanast i fyny fy mwrdd yma am ychydig funudau'n -
mae hynny'n mynd i weithio allan i fod yn rhywbeth fel n (n - 1) / 2
os ydym yn unig fath o edrych yng nghefn y llyfr mathemateg lle mae gennych yr holl daflenni twyllo
ar gyfer y fformiwlâu.
Os ydych ond yn ychwanegu rhywbeth n + n - 1 + n - 2, mae'n gweithio allan i fod yn rhywbeth fel hyn.
Ac os ydym yn unig fath o lluosi hyn, mae hynny'n n sgwâr minws n / 2.
Yr wyf yn cadw ei ddweud n sgwâr, fodd bynnag, a dyna oherwydd fy mod yn fath o gymryd llwybr byr meddwl
oherwydd mewn gwirionedd, n sgwâr minws n rhannu â 2 yn wir y gwir nifer o gamau
y byddai algorithm fel math dewis cymryd os ydym yn wir yn cyfrif i fyny
pob un o'r cymariaethau hynny a'r holl waith prysur bach oeddem yn ei wneud.
Ond dweud y gwir, unwaith n cael i fod fel miliwn neu biliwn, pwy yw'r heck gofalu
os ydych chi'n gwneud biliwn o minws sgwâr biliwn wedi'i rannu â 2?
Mae biliwn sgwâr yn nifer enfawr.
Gallwch gymryd arall biliwn oddi ar 'i ag - n. Nid yw'n mor bwysig â hynny.
Felly, y mwyaf fydd y niferoedd yn cael, y llai pwysig y telerau hyn yn is trefnus yn cael eu.
Pwy sy'n gofalu os ydych yn rhannu â 2 os ydych yn siarad am quadrillions nifer o gamau?
>> Felly, yn gyffredinol, gwyddonwyr cyfrifiadurol yn tueddu i daflu i ffwrdd popeth ond y term mwyaf,
ac rydym yn unig fath o symleiddio'r byd a dweud bod algorithm
wedi cymryd camau bras n sgwâr. Dyna'r tro yn rhedeg o algorithm.
Felly, byddwn yn dod yn ôl at hyn mewn dim ond hyn o bryd gyda rhai enghreifftiau pendant,
ond ar hyn o bryd, mae hynny'n rhyw fath o gymhelliant sythweledol y tu ôl dim ond symleiddio ein byd
a siarad am y termau mwyaf pwysig yn hytrach na mynd i mewn i hyn i gyd fformiwlâu ffansi.
Felly roedd hynny'n fath dethol, ac rydym yn cael ychydig yn ffodus yno.
Gadewch i ni edrych ar fath gosod. Gadewch i mi fynd yn ei flaen ac yn dechrau yr un yma yn ogystal.
Nawr yn sylwi ar y patrwm sy'n digwydd ychydig yn wahanol,
ac rydym yn dechrau gyda rhifau ar hap,
ond os ydym mewn gwirionedd yn cyfrif y nifer o gamau yn yr achos gwaethaf,
os bydd y rhestr ddechrau yn gyfan gwbl yn y drefn gywir,
ni fyddem ond yn cymryd camau n i sylweddoli cymaint.
>> Ond os bydd y rhestr oedd mewn gwirionedd yn ôl - er enghraifft, yn yr achos yma -
yna sylwi ydym mewn gwirionedd yn rhaid i ni wneud llawer mwy o waith yn yr achos hwn.
Ac fe ddylai fath o teimlo i chi fel yr un yma yn fath o weithio galetach
i gael y elfennau llai ar y chwith, a dyna oherwydd ein bod yn cael anlwcus.
Cafodd y rhestr ei datrys yn ddamweiniol o chwith.
Ar y llaw arall, gyda math fewnosod os ydym yn dynwared yr hyn a wnaethom gyda'n pobl yma
drwy ddechrau gyda phawb didoli ac yna'n dechrau, mae'n algorithm 'n bert da, dde?
Mae'n eisoes, mewn gwirionedd, didoli.
Felly, gadewch i ni geisio crynhoi yn union faint o amser y pethau hyn yn mynd â ni
drwy gyflwyno dim ond ychydig o jargon neu nodiant sydd mewn gwirionedd yn llawer symlach
na'r math o fanciness awgrymu.
Mae hyn yn beth yma, mae hyn yn O fawr ar y sgrin, yn yr hyn y bydd yn wyddonydd cyfrifiadur fel arfer yn defnyddio
i ddisgrifio yr amser yn rhedeg achos gwaethaf o algorithm.
>> Unwaith eto, fesul achos gwaethaf, mae'n hollol cyd-destun-ddibynnol.
Beth a olygwn wrth achos gwaethaf llwyr yn amrywio yn seiliedig ar y broblem, rydym yn sôn amdano.
Ond yn yr achos didoli, beth yw'r sefyllfa waethaf posibl?
Mae popeth yn ôl oherwydd mae'n teimlo fel bod yn golygu llawer o waith i ni.
Rydw i wedi jotted i lawr rhai o'r algorithmau yr ydym wedi gweld hyd yn hyn:
chwiliad llinol, chwiliad deuaidd fel y llyfr ffôn neu ddarnau o bapur,
Yna, math swigen didoli dewis, a gosod didoli fel y gwelsom yn achos ein pobl,
ac yna 1 arall sydd yn y pen draw yn mynd i gael eu galw uno fath.
Felly, mewn chwiliad llinol yn yr achos gwaethaf, faint o gamau mae'n ei gymryd i ddod o hyd i'r rhif 7
os oes drysau n fel Sean wynebu? >> [Myfyrwyr] N.
N. Felly, rydym yn mynd i ysgrifennu mawr O o n.
Im 'jyst yn mynd i chi lenwi rhai bylchau. Mae hyn yn unig yw grid o bylchau.
Ond yn yr achos gorau gyda chwiliad llinol, efallai 7 wedi bod ar gychwyn cyntaf y rhestr,
ac efallai y Sean wedi dechrau edrych ar ddechrau'r rhestr.
Felly, os ydych yn defnyddio chwiliad llinol a dim ond gwirio chwith i'r dde neu efallai dde i'r chwith -
eu bod yn gyfwerth - yn yr achos gorau faint o gamau y gallai chwiliad llinol,
fel Sean algorithm, cymryd? Dim ond 1 cam.
>> Felly, yr wyf i'n mynd i ddweud bod yn y nodiant omega.
Mae hyn yn unig omega cyfalaf.
Omega yn unig yw ffordd o ddweud sexy achos gorau yn rhedeg amser.
Felly, yn yr achos gorau yr amser yn rhedeg yn gam un neu nifer cyson o gamau -
1 mewn yr achos hwn - ond yn yr achos gwaethaf, mawr O, mae'n mewn gwirionedd camau n.
Ac mae hyn un yma, theta, nid ydym yn wir yn mynd i edrych ar hyn o bryd.
Nid yw'n berthnasol i'r enghraifft benodol.
Ond yn awr, gadewch i ni geisio chwiliad deuaidd.
Yn yr achos gwaethaf gyda chwiliad deuaidd, faint o gamau y mae'n mynd i'w cymryd i ddod o hyd i'r rhif 7
neu beth bynnag yr ydym yn chwilio amdano? >> [Myfyrwyr] Log n.
Dal yn mynd i gymryd n log oherwydd yn union fel Alex got anlwcus
pan mae arnom wir yn gweithio trwy'r broblem yn drefnus
ac nad oedd yn dod o hyd i'r rhif 7 tan y drws olaf mae hi'n edrych ar,
hyd yn oed er, yn deg, mae hi'n mynd i daflu i ffwrdd drysau penodol ar hyd y ffordd,
chwiliad deuaidd yn yr achos gwaethaf yn cael amser yn rhedeg o log n.
Ac eto, sydd yn siarad i hyn rannu a goncro.
Ond beth am yn yr achos gorau?
Ac Alex mewn gwirionedd yn profi bod achos gorau iawn pan ddaeth hi i fyny ar y llwyfan.
Faint o gamau a gymerodd hyn mewn chwiliad deuaidd? >> [Myfyrwyr] 1.
1, dim ond oherwydd ei got 'n ffodus.
Ond mae hynny'n iawn oherwydd omega yn cyfeirio at sefyllfaoedd achos gorau,
mewnbynnau achos gorau, hyd yn oed os mai dim ond ar hap lwc fud.
>> Yn awr, mae hyn hefyd rydym yn mynd i jyst fath o absenoldeb wag ar hyn o bryd.
Fath swigod Beth am nawr?
Yn yr achos gwaethaf gyda math swigen, mae pawb yn am yn ôl,
felly mae'n rhaid i ni wneud llawer o byrlymu.
Ond faint o gamau yw bod mynd i gymryd yn yr achos gwaethaf? >> [Myfyrwyr] N sgwâr.
Hwn oedd y n sgwâr, oherwydd os ydych yn meddwl am y peth,
os bydd y rhestr yn hollol yn ôl - 8 yn dros yma, mae 1 yn dros yma -
fel peth ddechrau swigen, y rhif 8 yn mynd i symud y ffordd hon, y modd hwn,
y ffordd hon, y modd hwn, ond ble mae'r rhif 7 yn yr achos gwaethaf?
Dyma hi dal i fod dros yno. Felly, mae'n rhaid i ni wneud hynny eto ac eto.
A dyna lle'r ydym yn cael gamau n, yna n - 1 gamau, yna n - 2 cam.
Ac os byddwch yn cymryd fy ngair i am hynny - os ydych yn fath o luosi allan,
mae'n n fras sgwâr yn y diwedd gyda rhai termau eraill y byddwn yn ei hanwybyddu ar hyn o bryd -
Yna, yn y math swigen achos gwaethaf yn n sgwâr, rhoi neu gymryd.
Ond beth am yr achos gorau gyda math swigen?
Beth yw'r senario achos gorau? Mae pob un o'r rhifau yn cael eu datrys eisoes.
A beth oedd y hewristig wyf yn ei ddefnyddio, y gamp wyf yn ei ddefnyddio,
i sylweddoli fy mod wedi gwneud dim gwaith a allai felly roi taw ar gynnar?
[Myfyrwyr] Edrychwch ar unwaith. Gwiriwch >> unwaith. Ond beth oedd yr wyf yn ei wneud ar hyd y ffordd?
Roeddwn yn cadw golwg ar faint o gyfnewid a wneuthum.
Ac yr wyf yn sylweddoli os nad wyf wedi cyfrif unrhyw cyfnewid ar fy mysedd, hynny, rwyf wedi gwneud dim gwaith.
Rwy'n sicr na ddylai geisio gwneud dim gwaith eto, felly gallaf stopio.
>> Felly, yn yr achos gorau o fath swigod pan oedd y rhestr yn cael ei datrys eisoes,
beth fyddech chi'n dweud bod y nodiant omega yw, yr achos gorau yn rhedeg amser?
Mae n unig. Mae'n rhaid i ni wneud rhywfaint o waith, ond dim ond rhaid i ni wneud werth 1 dro o waith.
Ac yma hefyd rwy'n mynd i adael hwn yn wag rhan.
Ac yn awr fath dethol.
Dewis fath wedi i mi plicio y person lleiaf eto ac eto.
A beth oedd yr ydym yn dweud yr amser yn rhedeg o hynny oedd?
Dyna oedd n sgwario yn yr achos gwaethaf.
Ac yn anffodus, yn yr achos gorau mae'n n hefyd yn sgwâr
oherwydd nid wyf yn cael y math o olygfa omniscient y byd i gyd;
Dim ond yn gwybod ar y fersiwn llawn fy mod wedi dod o hyd yn wir y person lleiaf.
Felly, dewis math fath o sugno yn yr ystyr honno,
ond yr ochr orau yw ei fod yn fath o 'n athrylithgar.
Mae'n eithaf hawdd i cod i fyny gan fod yr holl rhaid i chi ei wneud yw ysgrifennu ychydig o nythu ar gyfer dolenni,
fel arfer, sy'n mynd drwy edrych ar gyfer yr elfen lleiaf
ac yna rhoi'r elfen lleiaf lle mae'n perthyn ar ddiwedd y rhestr.
Felly, yma hefyd mae mynd i fod yn fasnach-off.
Mae faint o amser mae'n ei gymryd i chi i feddwl ac i ddatblygu rhywbeth mewn gwirionedd drwy ysgrifennu cod
Gallai yn dda iawn yn cymryd mwy o amser os ydych am gael perfformiad gwell algorithm ac yn gyflymach.
>> Ond os ydych yn wir yn unig fath o rywbeth cod i fyny yn gyflym ac yn fudr
a dim ond math o gymryd y syniad stupidest posibl y gallwch feddwl,
a allai fynd â chi ychydig o funudau i cod, ond gyda setiau data mawr
gallai eich algorithm yn cymryd awr a hanner.
A byddai hyd yn oed yr wyf yn yr ysgol i raddedigion weithiau yn gwneud y cyfaddawdau hyn.
Byddai'n 3am, yr oeddwn yn ceisio dadansoddi rhai set ddata fawr iawn
gysylltiedig â'r ymchwil diogelwch oeddwn yn ei wneud, ac yr oedd naill ai yn treulio 5 munud
tweaking fy rhaglen i ddadansoddi'r data a mynd i gysgu
neu dreulio 8 awr yn cael y peth yn iawn fel ei fod yn rhedeg yn syth a pheidio â mynd i gysgu.
Ac felly yno hefyd mae'n fath o benderfyniad ymwybodol.
Llai o amser datblygu, mwy o gwsg.
Wrth edrych yn ôl, yr wyf debyg na ddylai annog y
pan fydd y nod yma yw gwneud y gorau ansawdd y cod,
ond hefyd yn y byd go iawn yn rhesymol iawn fasnach-off.
Llai o amser, perfformiad llai neu i'r gwrthwyneb.
Felly dyma ni o'r diwedd yn cael y cyfle i siarad am theta.
Theta nodiant yn rhywbeth y gall gwyddonwyr cyfrifiadurol yn dod i fyny mewn sgwrs
pan fydd fawr O ac omega yn digwydd bod yr un fath.
Rydych yn dweud theta i wir anfon y neges bod hwn yn fath o rhwymo dynn.
Ni waeth a yw'r senario yn dda neu'n ddrwg, mae'n n sgwâr.
Felly, nid dim ond yn berthnasol yn y straeon yma.
Mewnosod fath yw'r un olaf buom yn edrych ar,
lle yr oeddwn yn gosod pawb i mewn i'r lle iawn.
Yn yr achos gorau beth oedd yr amser yn rhedeg o fath fewnosod fel y gwelsom yma?
[Myfyrwyr] Yr achos gorau? >> Yr achos gorau.
>> Fe'i n oherwydd yn yr achos gorau pawb didoli,
a Sammy a neb arall mewn gwirionedd wedi gorfod symud o gwbl.
Roeddent eisoes yn eu lle cywir.
Fath gosod Felly, yn yr achos gorau yw, yn yr achos hwn, n.
Ond yn yr achos gwaethaf mae'n fath o n sgwâr. Pam?
Os yw fy rhestr o bobl mewn cyflwr cefn,
Tro cyntaf i mi dechrau gyda'r rhif 8 ac rwy'n rhowch ef neu hi i mewn i'r safle cywir, sydd ar gael yma.
Yr wyf yn fath o symudiad ar yr ochr. Mae'r rhain guys yn cael eu heb eu didoli, ef neu hi ei drefnu.
Ond yn awr yr wyf yn digwydd i ddod o hyd pwy nesaf? >> [Myfyrwyr] 7.
7 yn yr achos gwaethaf oherwydd ei fod yn ôl.
>> Felly dyma yw 7. Ble mae 7 yn perthyn? Yn bendant tu ôl i mi.
Ond yn awr 7 Nid mewn gwirionedd yn perthyn union y tu ôl i mi, ond y tu ôl i rif 8,
felly rhaid i mi ddweud, "Esgusodwch fi, rhif 8, a fyddech cystal symud y ffordd hon
"I wneud lle ar gyfer 7?" Nawr rwy'n dod ar draws 6.
"O, esgus i mi, rhif 8 a rhif 7 yn gallu, byddwch yn symud i wneud lle i 6?"
Felly, mewn geiriau eraill, gyda math mewnosod, er nad wyf yn gwneud llawer o symud,
bobl y tu ôl i mi yn gwneud llawer mwy o waith, ac mae'n rhaid bod cost amser rhywun.
Mae'n mynd i gostio amser cyfrifiadur.
Felly, yn achos math mewnosod rydym yn dal i ddioddef.
Os ydych yn dechrau ychwanegu i fyny 'r cyfanswm nifer o gamau, rydym yn y pen draw taro fras n sgwâr
oherwydd bod y rhain guys angen i wneud lle am y dynol i'w fewnosod yn ôl i mewn i'r rhestr.
Ac felly yn yr achos hwn theta nid yn unig yn berthnasol i'r stori arbennig wrth law.
Thats 'pawb' n glws ac yn dda. Mae gennym ffyrdd hyn 3 gwahanol o siarad am yr amser yn rhedeg.
Ond beth mae hyn yn ei olygu mewn termau go iawn os ydym mewn gwirionedd yn ceisio cod sefydlu algorithm?
>> Gadewch i mi yn cynnig y mae 'na hyd yn oed yn well algorithm i maes' na
bod ei hun rhywfaint o fasnach-offs.
Rydym yn mynd i alw yn uno fath, ac mae'n fath o algorithm hwn yn hudol
mai dim ond yn gweithio yn gyflymach rhywsut, ac mae mor hawdd i fynegi, o leiaf yn pseudocode.
Mae gweithrediad y uno algorithm fath yn mynd i fod fel a ganlyn.
Pan fyddwch chi'n rhoi n elfennau - rhifau n, n pobl, beth bynnag - yn gyntaf mae 'na gwiriad bwyll.
Os n yn llai na 2, uno fath dim ond yn dod i ben. Mae'n dychwelyd, felly, i siarad.
Pam y byddech yn dod i ben os n yn llai na 2? >> [Anghlywadwy ymateb y myfyrwyr]
Hawl. Ac eto, nid yw n yw rhif yn y rhestr, n yw maint y rhestr.
Os n yn llai na 2, mae hynny'n golygu eich rhestr naill ai 1,
lle rydych chi'n trefnu yn amlwg os yw'n 1 rhif,
neu 0, ac os felly does dim byd i drefnu,
felly mae angen y math hwn o achos sylfaenol.
Os yw'r rhestr mor fyr nad oes dim ond dim byd i wneud, nid yn llythrennol yn gwneud unrhyw beth. Dychwelyd.
Fel arall ddatrys hanner chwith y elfennau, ac yna ddatrys yr hanner dde yr elfennau,
yna cyfuno'r 2 hanner didoli.
>> Mae'r math hwn o ymddangos fel twyllo ychydig o lle rwy'n gofyn i chi sut i roi trefn ar elfennau
ac rydych yn dweud wrthyf, "Trefnwch yr hanner chwith, didoli yr hanner cywir."
Rydw i'n hoffi, "Mae pob hawl. Sut ydych chi'n datrys yr hanner chwith?"
"Trefnwch y hanner chwith yr hanner chwith, didoli hanner dde yr hanner chwith, ac yna ei wneud."
Rydych yn fath o gylchol diffinio beth mae'n ei olygu i drefnu,
ond mae'n troi allan bod mewn gwirionedd wych yn yr achos hwn.
Nid yw'n wir y cylch dieflig nad yw byth yn dod i ben
oherwydd ei fod yn dod i ben pryd? >> [Myfyrwyr] Pan fyddwch yn cyrraedd 1 peth.
Pan fyddwch yn cyrraedd 1 peth.
Felly, hyd yn oed er efallai y byddwch yn dechrau gydag 8 o bobl ac yr wyf yn dweud, "Trefnwch y hanner chwith o'r bobl hyn,
y 4 o bobl, "yna yr wyf yn dweud," Sut ydych chi'n datrys yr hanner chwith? "
"Wel, didoli'r 2 o bobl yma." Ac yna ydych chi fel, "Mae pob hawl, dirwy."
"Sut ydych chi'n datrys hanner chwith bobl hynny?"
"Dim ond ddatrys hyn person 1 yma." Beth yw'r datguddiad wych nawr?
Rhaid i mi ddatrys 1 person. Done. Nid oes gennyf i wneud unrhyw waith.
Ond yn awr rhaid i mi ddatrys y person hwn, ond maent chi'n berson sengl, dim byd i'w wneud.
>> Felly, y mae'n debyg hud a lledrith sydd yn y trydydd cam: uno yr haneri didoli.
Fath Felly uno yn cymryd y mewnwelediad gwych, os byddwch yn torri yn broblem fawr i lawr
yn 2 llai, yn union-maint problemau
ac yna dim ond math o lud atebion llai at ei gilydd ar y diwedd,
Yr wyf yn cynnig y gallwn wneud llawer, [sain tapio] llawer gwell
nag unrhyw fath o ddethol neu'n didoli gosod.
Rwyf wedi gwirionedd bod yn anwybyddu hynny am hanner awr, ond i ddim wir yn gwybod beth sy'n mynd ymlaen
y tu allan heddiw. [Sain whirring] [chwerthin]
Felly, gadewch i ni weld os allwn ni weld hyn gydag ychydig o help gan ein ffrind Rob Bowden.
Mae 2 cam mawr yn y broses o uno fath.
Yn gyntaf, yn barhaus rhannu rhestr o gwpanau mewn i haneri
nes bydd gennym griw o restrau gyda dim ond 1 cwpan ynddynt.
Peidiwch â phoeni os bydd rhestr yn cynnwys odrif
ac ni allwch wneud toriad yn berffaith lân rhyngddynt.
Dim ond fympwyol ddewis pa rhestr i gynnwys y cwpan ychwanegol i mewn
Felly, gadewch i ni rannu'r rhestrau hyn.
Nawr rydym yn cael 2 rhestrau.
Nawr rydym wedi 4 rhestrau.
Nawr mae gennym 8 rhestri gyda phaned un ym mhob rhestr.
Felly dyna ni ar gyfer cam 1.
Am cam 2, rydym dro ar ôl tro uno parau o restrau defnyddio'r algorithm uno a ddysgwyd o'r blaen.
Cyfuno 108 a 15 yn y pen i fyny â'r rhestr 15, 108.
Cyfuno 50 a 4, yn y pen draw gyda 4, 50.
Cyfuno 8 a 42 rydym yn darfod i fyny ag 8, 42.
Ac uno 23 a 16 yn y pen draw 16, 23.
Nawr ein holl restrau o faint 2.
Sylwch fod pob un o'r 4 rhestrau yn cael ei datrys,
fel y gallwn ddechrau cyfuno parau o restrau eto.
Cyfuno 15 a 108 a 4 a 50 yn gyntaf yn cymryd y 4, yna bydd y 15,
yna y 50, yna bydd y 108.
Cyfuno 8, 42 a 16, 23 i ni yn gyntaf gymryd y 8, yna yr 16,
yna y 23, ac yna 42.
Felly, nawr rydym wedi dim ond 2 restr o faint 4, pob un ohonynt yn cael ei ddidoli.
Felly, nawr rydym cyfuno'r 2 restr.
Yn gyntaf rydym yn cymryd y 4, yna rydym yn cymryd y 8, yna rydym yn cymryd y 15
a 16 a 23 a 42 a 50 a 108.
Ac rydym ni'n ei wneud. Erbyn hyn mae gennym restr datrys.
>> Rob yn fath o gymryd mantais o rywbeth nad ydym wedi gwneud hynny eto.
Awgrymwyd, ond doedden ni ddim yn gwneud hynny mewn gwirionedd.
Roedd yn gwneud rhywbeth yn gorfforol gyda'r cwpanau sy'n awgrymu
ei fod yn treulio rhywfaint o adnoddau ar wahân amser. >> [Myfyrwyr] Space. >> Roedd gofod.
Mae'r ffaith ei fod yn cael y math hwn o bi-lefel tabl lle y cafodd le i fyny yma
a gofod i lawr yma oedd mewn gwirionedd yn awgrymu ei fod wedi defnyddio gofod ddwywaith cymaint
ag unrhyw un o'n algorithmau hyd yn hyn -, math mewnosod fath swigen, neu ddewis math -
ond yr oedd yn ddylanwad busnes y gofod ychwanegol i fath o bethau symud yn ôl ac ymlaen
tra'n cadw pethau mewn trefn.
A hyd yn oed er ei fod yn teimlo fel ni gyrraedd at restr datrys, a oedd yn teimlo fel ei fod yn cymryd amser.
Mewn gwirionedd, yr hyn Rob yn ei wneud yn union y algorithm.
Yn gyntaf yn cymryd y broblem o n maint, wedi'i rannu i mewn i hanner chwith a hanner i'r dde.
Dyna pryd y symudodd y cwpanau. Yna mae'n ailadrodd y broses honno.
Mae'n rhannu 4 i 2 set o 2 dros yma a dros yma.
Yna mae'n ailadrodd y broses honno ac yn rhannu 2 i 2 set o 1 ar gyfer pob un o'r cwpanau gwahanol.
A dyna lle y cyfle gwych yn codi.
Ar yr adeg honno yn y stori, roedd Rob 8 rhestrau o faint 1,
pob un ohonynt eu datrys eisoes.
>> Felly, yna beth oedd yn mynd ati i wneud?
Pairwise cymerodd y rhestr hon didoli ac mae'r rhestr hon didoli a'u cyfuno nhw.
Yna cymerodd yr un yma a'u cyfuno nhw, yna mae hyn yn un a cyfuno nhw,
yna mae hyn un a unodd nhw.
Ac yna beth wnaeth e ei wneud nesaf?
Yna ail-uno y rhestrau yn fwy ac yna ail-uno y rhestrau yn fwy.
Ac os ydych yn meddwl am hyn yn unig yn reddfol am y tro, beth oedd yn ei wneud mewn gwirionedd?
Roedd yn rhannu'r broblem yn ei hanner, yn ei hanner, yn ei hanner, yn hanner
er mwyn cael y rhestri hyn super bach.
Yna efe a oedd yn fath o gyfuno dwbl, dwbl, dwbl, dwbl.
Felly roedd yn gwneud dwywaith cymaint o waith ag yr ydym wedi gweld hyd yn hyn
gydag unrhyw beth sy'n ymwneud â rhannu a gorchfygu, ond dim llawer mawr.
Nad yw gwaith dwywaith cymaint yn mor bwysig â hynny. Dim ond yn ffactor cyson.
A llawer fel ein mynegiant rhifyddeg o'r blaen, Im 'jyst yn mynd i groesi allan ffactorau cyson
fel amser 2. Pwy sy'n poeni? Os yw'n 2 biliynau amser 2, mae hynny'n dal i fod llawer o gamau.
Felly y cam hwn uno yn ymddangos i fod yn mewnwelediad allweddol.
Gadewch i ni gerdded drwy hyn yn union niferoedd o'r blaen - O, nid yw hynny'n cael ei barhau eto.
Gadewch i ni gerdded drwy hyn rhifol yn unig i mewn gwirionedd yn gweld sut mae hyn yn chwarae allan.
Mae hyn yn bennaf yn unig animeiddio dyn tlawd bach.
Gadewch i ni gynnig hyn.
Mae'r amser yn rhedeg o uno fath - ni jyst angen ffordd o siarad am hyn.
Nid yw hyn yn mathemateg, mae hyn yn unig fath o ffordd gryno o fynegi ein hunain.
Felly T yn cynrychioli amser ac n yn cynrychioli beth? >> [Myfyrwyr] Mae maint y -
>> [Malan] Mae maint y broblem, mae nifer o bobl.
Felly rwy'n hawlio bod yr amser yn rhedeg i ddidoli pobl n yn mynd i fod yn 0 faint o amser
os yw n yn llai na 2, oherwydd os ydych wedi 1 cwpan neu ddim cwpanau, oes gennych ddim i'w ddatrys.
Ond yn fwy cyffredinol, yr wyf i'n mynd i gynnig bod yr amser yn rhedeg i ddatrys elfennau n
yn mynd i fod yr amser mae'n ei gymryd i ddatrys yr hanner chwith plws hanner cywir
plus - beth ydyn nhw ychwanegol + n? >> [Myfyrwyr] fath Cyfuno.
[Malan] Mae'n mewn gwirionedd yn uno, oherwydd os oes gennych n / 2 elfen yma
ac mae gennych n / 2 elfen yma, faint o amser mae'n ei gymryd i uno nhw?
Yn union fel Rob, rhaid i chi tyn hwn dros yma, efallai tyn dros yma,
tyn dros yma, tyn dros yma, tyn dros yma.
Mae'n rhaid i chi gyffwrdd pob un o'r cwpanau unwaith.
Ac os oes 4 cwpan a 4 cwpan, sef 8 cwpan
neu, yn fwy cyffredinol, 8 cwpan n.
Felly, y cam uno gallwn fynegi fel n,
a bod yn llythrennol yn golygu y nifer o weithiau Rob cyffwrdd yn gorfforol
un o'r rhai cwpanau Styrofoam.
Felly, gadewch i ni ei wneud yn awr yn enghraifft mympwyol.
Os oes 16 cwpanau, beth yw'r amser rhedeg didoli, gan ddefnyddio Rob algorithm, 16 cwpanau?
Mae'n 2 gwaith y swm o amser mae'n ei gymryd i ddatrys 8 cwpan
oherwydd mae gennym 8 cwpan yma, 8 cwpan yma.
Nid wyf yn gwybod pa mor hir sy'n cymryd, felly rydym yn generalizing fel T am y tro.
Pwy a ŵyr beth yw e?
Ond yn awr y gallaf ddidoli o recursively neu dro ar ôl tro yn gofyn yr un cwestiwn.
Faint o amser mae'n ei gymryd i ddatrys 8 cwpan?
8 cwpan yr wyf i'n mynd i ddweud yn cymryd yr amser mae'n ei gymryd i ddatrys 4 cwpan a 4 cwpan,
yna gyfuno nhw at ei gilydd.
Fine. Rydym yn mynd i mewn i gylch eisoes. Pa mor hir mae'n ei gymryd i ddatrys 4 cwpan?
Mae'r amser mae'n ei gymryd i ddatrys 4 cwpan cwpan yw 2 plws 2 cwpanau didoli yn ogystal â'r broses uno.
Fine. Pa mor hir mae'n ei gymryd i ddatrys 2 cwpan?
2 gwpanaid yw faint o amser mae'n ei gymryd i ddatrys 1 cwpan yn ogystal â'r amser mae'n ei gymryd i ddatrys arall cwpan
yn ogystal â faint o amser mae'n ei gymryd i uno, sef dim ond 2.
>> Fine. Cwestiwn olaf. Pa mor hir mae'n ei gymryd i ddatrys 1 cwpan?
Dyma yr achos sylfaenol yr ydym yn rhagweld byddem yn cyrraedd yn gynharach.
Mae'r ffaith ei bod yn cymryd dim gwaith o gwbl i ddatrys y lleiaf o'r problemau
yn golygu bod yn awr, math o arddull ysgol radd,
gallwn fynd dechrau llenwi rhifau hyn yn ôl i mewn
Rydym bellach yn gwybod pa T o 1 yw, fel y gallaf plwg yn 0 ar gyfer T o 1.
Bydd hynny'n rhoi 'm' r ateb i T o 2, yr wyf yn gall wedyn plwg yn uwch i fyny.
Bydd hynny'n rhoi i mi T o 4, y gallaf plwg yn uwch i fyny.
Bydd hynny'n rhoi i mi T o 8, a gallaf plwg yn uwch i fyny.
Ac os wyf mewn gwirionedd yn gwneud allan y math drwy plygio i mewn atebion hyn,
Byddaf wedyn yn cael T o 16 yn 64.
A beth mae 64 ei gynrychioli?
Os T yn 16, yeah, mae'n 16 gwaith 4.
Felly yr wyf yn honni yn awr bod yr amser yn rhedeg y peth hyn a elwir yn uno fath -
ac mae hyn yn mynd i fod yn fanciest y rhai yr ydym wedi ei weld hyd yn hyn -
yn mynd i gael ei alw n log n
oherwydd gall sawl gwaith Rob rhannu criw cyfan o gwpanau yn eu hanner? Mewngofnodi n.
Mae yr un fath ag y llyfr ffôn enghraifft, mae'n yr un fath ag yr enghraifft hunan-gyfrif.
>> Sawl gwaith yr ydych yn rhannu rhywbeth yn ei hanner?
Fodd bynnag, mae hyn yn gam uno.
Efallai y bydd rhaid i chi rannu'r cwpanau i mewn i hanner eto ac eto ac eto,
ond bob tro y byddwch chi'n mynd i gael i uno.
Ac rydym yn dweud yn gynharach mai uno cwpanau n cymryd camau n
oherwydd bod yn rhaid i chi dynnaf cwpan rwystra, tyn allan cwpan, ac mae'n rhaid i chi gyffwrdd pob cwpan unwaith,
yn union fel y gwnaeth Rob.
Felly, os ydym yn gwneud rhywbeth log n gwaith ac rydym yn gwneud pethau n ar bob un o'r iteriadau,
pob un o'r halvings, rydym wedi n amser log n.
Felly, os gallwn gau mewn 16 yn yr enghraifft hon, 16 gwaith log o 16 -
peidiwch â phoeni ynghylch pam mae hyn yn wir ar hyn o bryd gan nad wyf wedi tynnu y sylfaen -
ond cofnod o sylfaen 2 o 16 yw 4, 16 gwaith 4 yn 64.
Ond ar y llaw arall, pe baem wedi defnyddio math swigod neu ddewis didoli neu fewnosod fath gyda 16 rhifau,
beth fyddai yr amser yn rhedeg wedi bod pe n yn 16 oed?
Byddai'n fod yn 16 sgwâr, sef 256, a hyd yn oed os nad ydych wedi dilyn yn eithaf yr holl math,
256 yn fwy na 64. Hynny'n wir yn y lle prydau parod hudolus yma.
Ac yn sylweddoli bod gweithio drwy hyn mewn enghreifftiau llai wrth i chi y bydd ar pset
yn ei gwneud yn llawer mwy 'n athrylithgar.
Ond beth sydd wir yn ei olygu o ran y teimlad yr algorithm yw hyn:
Os ydym mewn gwirionedd yn edrych ar uno fath yma - gadewch i mi dynnu i fyny yn y ffenestr hon yma -
mae hyn yn enghraifft ychydig yn wahanol lle mae gennym pob un o'r 3 o'r algorithmau -
swigen, dethol, ac yn uno - dim ond ochr yn ochr.
>> Maent i gyd wedi cychwyn gyda bariau ar hap, ac mae hynny'n dda.
Nid oes unrhyw un fantais sylfaenol dros y llall.
Dw i'n mynd i mewn eiliad cliciwch ar bob un o'r animeiddiadau - Start, Dechrau, Dechrau -
mor gyflym ag y gallaf er mwyn i, yn fras, maent i gyd yn cychwyn ar yr un pryd,
a gadewch i ni ystyried yr achos fath swigen yn waeth rhedeg amser yn beth? >> [Myfyrwyr] N sgwâr.
N sgwâr. Achos fath Dewis gwaethaf rhedeg amser? N sgwâr.
Ac uno fath yn ôl pob golwg - hyd yn oed os nad oeddech yn eithaf ddilyn yr holl math yn awr,
bydd yn dod yn llawer mwy 'n athrylithgar dros gyfnod o amser - yw, yr ydym yn hawlio, n amser log n.
Ac oherwydd log n yn gwbl llai nag n ôl i ni gael rhifau mawr,
n gwaith log n yn llai nag amseroedd n n n neu sgwâr.
Felly, beth mae'n ei deimlo mewn gwirionedd fod yn algorithm yn well o ran amser yn rhedeg,
n amser log n yn hytrach na n sgwâr? Yma rydym yn mynd. Cliciwch, cliciwch, cliciwch.
>> Dyna beth mae'n ei olygu i ddefnyddio rhywbeth fel uno fath.
Mae gennym hyn o bryd. Gadewch i ni weld beth sy'n digwydd yma.
[Chuckles] pwy arian ar fath swigen?
Mae yn hytrach yn dibynnu ar y mewnbwn weithiau.
Gadewch i ni weld.
Dewch ar. Mae'n teimlo fel ei fod yn dal i fyny. >> [Myfyrwyr] Ewch, math swigen!
[Fyfyrwyr grwgnach]
[Malan] Yeah, yeah.
[Fyfyrwyr grwgnach] Ewch, ewch, ewch!
[Holl bloeddio] [gymeradwyaeth]
Felly, yn awr gyda 1 y llynedd, demo terfynol, os yw'n ychydig yn anodd i lapio eich meddwl o amgylch y math
neu rhyw fath o ddelweddu yno, alli 'n weithredol glywed y cyflymder
o algorithmau gwahanol yn wahanol.
Mae hwn yn rhywun animeiddio a wnaed sydd mewn gwirionedd yn swnio'n cyswllt
gyda'r broses o gyfnewid ac uchder y bariau.
Fel gawn ni weld yma, mae 'na algorithmau didoli ychydig mwy allan yna sy'n Folks wedi meddwl amdanynt.
Mae'r un cyntaf yn mynd i fod yn fath mewnosod, a bydd hyn yn hedfan drwy
ac yn rhoi ymdeimlad clywadwy o sut mae hyn yn gweithio algorithmau amrywiol.
Dyma fath gosod.
[Beeping microform]
[Malan] fath Bubble.
[Gyflymach beeping microform]
[Malan] fath Dethol.
[Gyflymach beeping microform]
[Malan] fath Cyfuno.
[Beeping microform]
[Beeping yn arafu i lawr] [chwerthin]
[Malan] fath Gnome.
[Beeping microform]
>> Mae hyn yn CS50. Gwelwn ni chi wythnos nesaf. [Gymeradwyaeth a bloeddio]
>> [CS50.TV]