[CHWARAE CERDDORIAETH] 

DAVID J. Malan: Pob hawl. Felly, croeso yn ôl. Mae hyn yn CS50, a'r cyntaf ohonynt yw'r diwedd yr wythnos tri. 

Felly, dwyn i gof yn y nifer o wythnosau diwethaf, rydym wedi bod yn treulio cryn dipyn o amser ar C, ar raglenni, ar gystrawen. Ac mae'n eithaf normal, os ydych yn dal trafferth gyda Problem Set 2, i fod yn taro eich pen yn erbyn y wal. Mae'n negeseuon gwall cryptig-edrych a chwilod sy'n eich Ni all fynd ar ôl i lawr yn eithaf. Oherwydd, yn dawel eich meddwl, bod mewn dim ond ymhen ychydig wythnosau byddwch yn edrych yn ôl ar pethau fel Cesar, a [? V-genair,?] efallai hyd yn oed Crac, a sylweddoli pa mor bell rydych chi wedi dod mewn cyfnod byr o amser. Felly, os yw hynny'n unrhyw gysur, hongian yno am y tro. 

Heddiw, fodd bynnag, rydym yn dechrau i bontio at lefel uwch bethau. Ac rydym yn dechrau cymryd yn ganiataol y rydych guys yn gwybod sut i raglennu, neu mewn lleiaf y dechreuadau y lefel cysur. A byddwn yn dechrau ystyried sut y gallwn mynd ati i gynllunio rhaglenni mwy effeithiol. Sut gallwn ni fynd ati i wneud y gorau o'r effeithlonrwydd ein algorithmau, a gyffredinol yn datrys mwy problemau diddorol. Ac yn dechrau cymryd yn ganiataol bod, os ydym am wneud hynny, gallem godio i fyny unrhyw o'r enghreifftiau sydd gennym mewn golwg. Felly heddiw, nid ydym yn cyffwrdd y bysellfwrdd am unrhyw fath o god. Bydd yn lefel llawer uwch, a yn y pen draw, am ddatrys problemau. 

Felly, i gyrraedd y pwynt hwnnw, gadewch i mi gynnig bod y saith canlynol petryalau cynrychioli saith drysau, y tu ôl sydd yn criw cyfan o rhifau, ymhlith sef y rhif 50. Gadewch i mi prosiect hwn ar y sgrîn yma hefyd. Ac yn cynnig ein bod yn rhaid i wirfoddolwr helpu i ddod o hyd i mi nifer o flaen y rhyngrwyd yma i weld. Dewch ar i fyny, yn y pinc. Mae pob hawl. Beth yw eich enw? 

JENNIFER: [Anghlywadwy] 

DAVID J. Malan: Mae'n ddrwg gennyf? 

JENNIFER: Jennifer. 

DAVID J. Malan: Jennifer. Mae pob hawl, Jennifer. Neis i gwrdd â chi. Dewch ar i fyny. Felly mae'r dyma saith drysau, a beth Hoffwn i chi ei wneud i ni yma, o flaen eich holl ffrindiau yn y dosbarth, yn dod o hyd i ni nifer, 50. I ddod o hyd i rif, gallwch peek y tu ôl i unrhyw un o'r drysau hyn gan syml tapio ar un o'r drysau, ac mae'n yn datgelu ei rhif. A gadewch i ni weld pa mor gyflym rydych gallu dod o hyd i ni nifer, 50. 

15. 16. 50. Gwneud 'N glws. Mae pob hawl. Rownd o gymeradwyaeth ar gyfer Jennifer. 

[Cymeradwyaeth] 

Mae pob hawl. Felly, beth oedd eich strategaeth ar gyfer dod o hyd i nifer, 50? 

JENNIFER: Um, yr wyf yn meddwl efallai os - [Anghlywadwy] 

DAVID J. Malan: Oh. Rhowch un eiliad. Felly oedd eich strategaeth ar gyfer dod o hyd i nifer, 50? 

JENNIFER: Felly, Fi jyst yn dechrau ar y dechrau gweld yr hyn y mae'r rhif cyntaf oedd, ac yna yr wyf yn meddwl, efallai os maent yn didoli, 'n annhymerus' jyst cadw tapio yn uwch i fyny? 

DAVID J. Malan: OK. Ac rydym yn ymddangos i wedi dod o hyd bod hynny'n wir. Er bod, gadewch i ni croen yn ôl yr haenau dim ond ychydig bach, ac rydych eisiau mynd ymlaen ac yn dangos y drysau eraill gallech fod wedi dewis? 

JENNIFER: O, diar. 

DAVID J. Malan: Ah. 

JENNIFER: Felly, Fi jyst got 'n ffodus. 

DAVID J. Malan: Felly, byddwch yn cael lwcus. Mae pob hawl. Felly, nid drwg. Ond dyna ddiddorol mewnwelediad, dde? Os ydych yn cymryd yn ganiataol, ac a wnaeth i chi ei gael, yn wir, ychydig lwcus yno. Ond os ydych yn cymryd yn ganiataol bod y niferoedd yn didoli, gallwch fod yn fwy manwl gywir o ran sut y mae hynny'n dylanwadu eich ymddygiad? 

JENNIFER: Felly, os ydynt yn cael eu didoli, yr wyf yn meddwl efallai lleiaf i'r mwyaf. 

DAVID J. Malan: OK. 

JENNIFER: Neu os yw hyn yn y pen draw yn fawr iawn, yna mwyaf i'r lleiaf. 

DAVID J. Malan: OK. Felly, o'r mwyaf i'r lleiaf, neu lleiaf i'r mwyaf. Ond gadewch i mi gynnig, mae'n debyg eich bod gotten anlwcus, ac mae'n debyg eu bod yn nad oedd, mewn gwirionedd, didoli, faint o'r drysau hynny efallai y byddwch wedi gorfod peek y tu ôl yn yr achos gwaethaf? 

JENNIFER: Mae pob un ohonynt. 

DAVID J. Malan: Mae pob un ohonynt. Felly, gadewch i ni cyffredinoli hynny fel n. Mae yn digwydd i fod yn 7, ond gadewch i ni yn fwy gyffredinol yn dweud mae 'n drysau ar y sgrin yma. Felly, yn yr achos gwaethaf, byddai gennych i edrych y tu ôl 7 drysau, neu n ddrysau. Ac felly mae hyn mewn gwirionedd yw, mae'n dipyn o lwc heddiw, ond mae'n wir yn llinellol algorithm o ryw fath, er eich bod yn fath o sgipio o gwmpas. A yw hynny'n deg? 

JENNIFER: Yeah. 

DAVID J. Malan: Wel, gadewch i mi weld os yw eich newidiadau strategaeth os byddaf yn symud i ni ein ail enghraifft yma gyda 7 drysau gwahanol. Rhifau un fath, ond mae hyn yn amser y maent yn cael eu datrys. Beth yw eich strategaeth yma yn mynd i fod, ceisio rhoi allan o'ch meddwl beth y rhifau eraill oedd - 

JENNIFER: OK. 

DAVID J. Malan: - yn gynharach? 

JENNIFER: Gadewch i ni ddechrau gyda'r un cyntaf. 

DAVID J. Malan: Pob hawl. Dechreuwch â'r un cyntaf. 4. Nawr ble rydych yn mynd i fynd, a pham? 

JENNIFER: 4 sydd mewn gwirionedd yn fach. Felly, os ydynt yn fath efallai lleiaf i'r mwyaf, dylai yn ddwywaith hynny, a -. 

DAVID J. Malan: OK. Gadewch i ni weld, yr ydych yn meddwl? 

JENNIFER: Rhowch gynnig ar y un ddiwethaf. Nice. 

DAVID J. Malan: gwneud 'n glws iawn. Mae pob hawl. 

[Cymeradwyaeth] 

DAVID J. Malan: OK. Felly, rydych chi'n mewn gwirionedd yn gwneud hyn ofnadwy, oherwydd eich bod yn wneud yn dda iawn. Sy'n gadael i ni yn gallu gwneud rhai pwyntiau. Felly, gadewch i ni geisio rolio yn ôl yma. 

JENNIFER: OK. 

DAVID J. Malan: Da iawn wneud, serch hynny. Felly, byddwch yn dechrau yn y dechrau, gwelsoch mai 4, yna rydych symud i'r diwedd. Ond mae'n debyg nad oeddech yn cael lwcus yno, ac mae'n debyg 50 yn rhywle arall. Beth yw eich drydydd cam wedi bod? 

JENNIFER: Ewch yn ôl i'r dechrau. 

DAVID J. Malan: Ewch yn ôl i'r dechrau. Iawn, felly eich bod wedi cyffwrdd drws hwn, a oedd 8. Mae pob hawl. Felly, nid yw hynny'n 50. Ble fyddech chi'n wedi edrych nesaf? 

JENNIFER: Os nad wyf yn gwneud gwybod eu datrys. 

DAVID J. Malan: Cywir. Wel, os ydych yn gwybod cawsant eu datrys - 

JENNIFER: O, ddim yn gwybod, ie. 

DAVID J. Malan: - Nid yw ond gwnaethoch gwybod lle mae 50 oedd eto? 

JENNIFER: Dim ond yn cadw i fynd. 

DAVID J. Malan: Pob hawl. OK. Daliwch ati. OK, y gallaf weithio gyda. 

JENNIFER: OK. 

DAVID J. Malan: Nawr, os ydych yn unig mynd i gadw i fynd, beth yw eich algorithm Datganoli cefnogi i mewn. 

JENNIFER: Y llinol -. 

DAVID J. Malan: Mae'n fath o llinol. Ond gadewch i mi gynnig, gadewch fy rhoi ar y fan a'r lle. Gadewch i mi adnewyddu'r dudalen. un nifer, un trefniant, yr un drysau. Ond meddyliwch yn ôl i'r diwrnod cyntaf yn dosbarth pan fyddwn yn rhwygodd llyfr ffôn hanner, rhyw fath o, a beth oedd ein strategaeth yno? 

JENNIFER: Dechreuwch yn y canol. 

DAVID J. Malan: OK. Felly, yn dechrau yn y canol. Felly, gadewch i ni fynd yn ei flaen ac yn efelychu hynny. Dechreuwch yn y canol gan datgelu bod drws. Felly, y rhif 16. Felly, beth fyddai y dyn cryf wedi ei wneud, a rhwygodd y llyfr ffôn yn ei hanner, i gyrraedd y dyfalu nesaf? 

JENNIFER: Ewch yn y hanner. 

DAVID J. Malan: A pham ar y dde? 

JENNIFER: Os ydynt yn fath o leiaf i'r mwyaf, yna dylai 50 fod yn yn y pen hwnnw. 

DAVID J. Malan: Da. Hollol rhesymol. Felly, fel llyfr ffôn, byddwch yn mynd i'r hawl yn hytrach na'r chwith, ond dyma yw'r lle prydau parod allweddol. Yr ydych yn awr yn gallu daflu i ffwrdd, neu rhwygo i ffwrdd, Nid yw hanner y broblem hon, gan adael i chi gyda 7 drysau, ond mewn gwirionedd gyda dim ond 3. Pa un yw tua hanner y maint y broblem. Mae pob hawl. Felly, yn awr yr hyn y byddech yn cael ei wneud ar ôl i chi mynd yn iawn? 

JENNIFER: Felly 16 yn dal i fod yn eithaf bach, gymharu â 50, felly efallai 'n annhymerus' roi cynnig, fel, mae hyn yn un. 

DAVID J. Malan: Pob hawl. 42. Mae pob hawl, felly nawr beth yw eich greddf yn dweud wrthych? 

JENNIFER: Gallaf daflu i ffwrdd ac mae hyn wedyn yn unig - 

DAVID J. Malan: OK. Da, gallwch chi daflu i ffwrdd yr hanner chwith yno. 

JENNIFER: - dewis hwn. 

DAVID J. Malan: Ac y dde. 

JENNIFER: Yeah. 

DAVID J. Malan: Felly hyd yn oed er ei bod yn anodd i weld efallai, pan fo dim ond 7 drysau, yn meddwl am, yn awr, cysondeb y Algorithm ydych newydd gymhwyso. Yn yr achos blaenorol, wnaethoch chi cael lwcus, a oedd yn wych. Ond wnaethoch chi ddefnyddio hewristig, Byddwn yn dweud. Rydych yn defnyddio math o eich greddf, a gan wybod ei datrys, os mae'n eithaf fach ar y dechrau, yn amlwg, rydym wedi rhaid i mi fynd yn fwy ar y dde. Ond mewn rhai ystyr, yr ydych got 'n ffodus, oherwydd efallai hwn oedd y rhif 100, ac efallai 50 yn fwy yn y canol. Efallai 50 hyd yn oed dros yma. 

Ond beth wnaethoch chi ychydig yn wahanol y tro hwn oedd, a wnaethoch chi yr un peth dro ar ôl tro. A byddwn yn dadlau bod yr hyn yr ydych newydd ei oedd, er ddylanwadu gan y ffôn enghraifft llyfr, yn rhywbeth llawer mwy algorithmig, a llawer Mewn Casys llai arbennig. Llawer llai greddfol. Felly, yn y diwedd y dydd, sut y byddai chi'n disgrifio effeithlonrwydd y algorithm gyntaf, ble aethoch chi o'r chwith i'r dde, yn erbyn y ail algorithm yma? 

JENNIFER: Dylai Mae hyn yn un, fel, efallai haneru'r amser, neu hyd yn oed yn fwy, ie. 

DAVID J. Malan: OK, efallai hyd yn oed yn fwy. Gadewch i ni wthio ychydig yn galetach ar hynny. Beth mewn gwirionedd, os byddwn yn parhau â'r rhesymeg, yn sicr haneru amser rhedeg gyda hyn ail algorithm drwy daflu i ffwrdd hanner y rhifau, ond yr hyn a wnaethom ni ei wneud ar y dudalen nesaf iteriad, pan ddatgelwyd Jennifer yr ail rif? 

Rydym yn haneru nifer y drysau eto. Ac yna beth wnaeth rydym yn ei wneud ar ôl hynny, os roedd mwy o ddrysau i chwarae gyda? Byddem yn haneru iddynt, ac eto, ac unwaith eto, ac unwaith eto. Ac mae hyn yn union fel chi guys i gyd sefyll i fyny yn yr wythnos gyntaf o dosbarth, hanner ohonoch yn eistedd i lawr, hanner i chi eistedd i lawr, hanner ohonoch eistedd i lawr, hyd nes un unigol enaid yn sefyll. Ac rydym yn dweud bod yr amser yn rhedeg o hynny, mae nifer o gamau gymerodd yn ar y drefn o beth? 

SIARADWR 1: [Anghlywadwy] 

DAVID J. Malan: sylfaen log Felly 2 o n, neu ddim ond yn fwy syml, mewngofnodwch o n. Felly, rhywbeth logarithmig. Ac nid y graff yn llinell syth mai dim ond mynd yn waeth ac yn waeth, roedd yn gromlin hon yn ddiddorol nad oedd yn mynd mor wael dros gyfnod o amser. Felly, gadewch i ni ddal gafael ar y syniad hwn. Gadewch i ni ddiolch Jennifer. Diolch yn fawr am ddod ar i fyny. Ac, un sec. Dim lampau desg heddiw, ond yr ydym yn oes CS50 peli straen. 

JENNIFER: Yay. 

DAVID J. Malan: pob hawl, yma. Diolch i chi am dynnu y straen i fyny yma. Mae pob hawl. Felly, gadewch i ni weld os gallwn ni nawr ffurfioli hyn ychydig yn fwy. Felly, unwaith eto, yr hyn yr ydym yn unig oedd yn yn ei hanfod yr un peth fel y gwnaethom yn ystod yr wythnos gyntaf. Ond yn hytrach na diwedd gyda dim ond llinellol algorithm, yr ydym yn darlunio yn flaenorol fel llinell syth hwn, sy'n golygu, os ydym yn rhoi un drws mwy ar y sgrin, yna byddai Jennifer wedi gorfod edrych, o bosibl, tu ôl i un drws mwy. Os byddwn yn rhoi dau ddrws mwy, gallai fod wedi i edrych y tu ôl dau ddrws mwy. 

Ac felly, yr oedd hyn yn llinol berthynas rhwng maint y problem ar, dyweder, yr echelin-x, a faint o amser mae'n ei gymryd i datrys ar y. Ond mae'r darlun oeddwn yn cyfeirio ato yn gynharach yn y llinell hon gwyrdd. Green yn fwriadol, gan fod 'i jyst yn teimlo'n well. Mewn theori, mae'r algorithm, pan fyddwn yn gwneud hynny gyda'r llyfr ffôn, pan fyddwn yn gwneud hynny gyda chi guys cyfrif gilydd, ac yn yr ail achos, pan Jennifer yn unig gwneud i fyny yma, roedd yn fath o well o'u hanfod. Oherwydd nid dim ond ddwywaith mor gyflym. Nid oedd hyd yn oed bedair gwaith mor gyflym. Yr oedd yn gwbl ddibynnol ar yr hyn y mae'r maint y cyfraniad yr oedd, o ran faint o camau yn y pen draw yn cymryd. 

Ac felly y syniad syml ein bod i gyd yn cymryd yn ganiataol gyda'r llyfr ffôn, Gall yr un modd yn cael eu cymhwyso i rywbeth fel hyn. A gallai hyn fod yn fwy casually a elwir yn, fel y gallai ddychmygu, rhannu a gorchfygu. Ddim yn wahanol i'r hyn a wnaethom, wrth gwrs, gyda'r llyfr ffôn. 

Ond mae'r pseudocode, galw i gof, oedd hyn. Felly, ni fyddwn yn gwneud hyn eto, ond yn cofio yr wythnos gyntaf, mae pob un ohonom yn sefyll i fyny ac yna hanner ohonoch eistedd i lawr, hanner i chi eistedd i lawr, hanner ohonoch eistedd i lawr. Ei weithredu Bod algorithm mewn dipyn o ffordd twyllo, yn hynny, mae'n nid oedd dim ond un ohonof cyfrif, yn y bôn, yn fwy effeithlon. Yn yr achos hwnnw, yr oeddwn yn ddylanwad busnes adnodd uwchradd. Math o, CPUs lluosog, ymennydd lluosog, pobl smart lluosog yn y ystafell yn helpu i mi gael o rywbeth llinellol i rywbeth logarithmig, o rywbeth coch i rywbeth gwyrdd. 

Ond yn yr achos hwn, gall Jennifer ei ben ei hun gwella yn sylfaenol ar y perfformiad ei algorithm cyntaf, eto, dim ond meddwl ychydig yn galetach. Ac yn awr, pan ddaw amser i weithredu pethau hyn, figuring pa linellau o god gallwch ysgrifennu o'r fath y gallwch eu hailadrodd eto, ac unwaith eto, ac unwaith eto, math o mewn modd dolennu. Oherwydd nad ydych yn mynd i gael y moethus, fel Jennifer gwnaeth yn y lle cyntaf, i dim ond yn cael criw cyfan o IFS a dweud, hmm, os yw hyn rhif cyntaf yw 4, gadewch i mi neidio yr holl ffordd at y diwedd. Ooh, os bydd y nifer yn rhy fawr, gadewch i mi symud yn fympwyol yn ôl i'r ail elfen. Fe welwch ei fod yn mynd i fod yn llawer yn fwy anodd i ffurfioli hyn yr ydym bodau dynol eu cymryd yn ganiataol yn rhesymol iawn heuristics, ond yn cyfrifiadur yn unig mynd i wneud yr hyn yr ydych yn dweud iddo ei wneud. 

Nawr mae hyn yn ddiddorol iawn goblygiadau. Mae'r graff hwn yn fath o fod i ddatrys y gorlethu golwg, ond rybudd, lle y yw'r llinell syth yn y graff hwn? Ble mae'r graff llinol ein bod yn galw n? Wel, mae'n fath o tuag at y gwaelod y llun, dde? Felly yr holl rydym wedi ei wneud yw ein i wedi fath o chwyddo allan i'r echelin-x a'r y-echelin i geisio cael ymdeimlad o'r hyn mathau eraill o gromliniau yn edrych fel. 

Ac manylion y fathemategol ymadroddion Ni fydd heddiw ots am hynny; llawer, ond yn sylwi bod yna lawer o algorithmau sy'n llawer gwaeth na rhywbeth sy'n llinol. Yn wir, wedi'i dorri'n giwbiau n edrych yn eithaf gwael. 2 i'r n edrych yn eithaf gwael. n squared yn edrych yn eithaf gwael. A gawn ni weld beth mae rhai o'r rheiny allai fod mewn gwirionedd heddiw. Ac nid log n yn teimlo mor ddrwg, ond well na n yn sylfaen log 2 o n. Ond eich bod yn gwybod, byddai wedi bod hyd yn oed yn fwy anhygoel os Jennifer, neu os ydym ni, yr wythnos gyntaf, wedi dod o hyd i rhywbeth sy'n log o log o n. 

Felly, mewn geiriau eraill, mae hyn yn gyfan ystod o atebion posibl i problemau, ond hyd yn oed yma, rhybudd beth sy'n mynd i ddigwydd. Pan fyddaf yn chwyddo allan, pa rai o'r cromliniau hyn yn mynd i brofi i fod yn absoliwt gwaethaf y rhai ar y sgrin yn awr? Felly torri'n giwbiau n edrych yn eithaf wael ar hyn o bryd. Ond os ydym yn chwyddo allan a gweld mwy o'r x a'r echelin-y, pwy sy'n mynd i dominyddu yn y pen draw? Felly, mae'n mewn gwirionedd yn troi allan bod 2 i'r Gall n, ac yn eich ffigur hwn allan yn unig gan plygio mewn rhai gynyddol fawr rhifau, a byddwch yn gweld bod 2 i'r n, yn wir, mynd yn fwy yn gynt o lawer. Os ydym o ddifrif chwyddo allan, a 2 i'r n algorithm gwbl sucks. Yr wyf yn golygu hyn yn mynd i gymryd cryn dipyn o amser ar gyfer y cyfrifiadur i gorddi trwy. 

Ond byddwch yn gweld dros gyfnod o amser, yn enwedig gyda setiau phroblem yn y dyfodol a hyd yn oed prosiectau terfynol, a yw eich data set yn cael fawr, iawn? Hyd yn oed yn y fersiwn gyntaf o Facebook, fel y nifer o ffrindiau, ac mae'r nifer y defnyddwyr cofrestredig got fawr, gallwch ddatrys y ffôn i mewn ac gweithredu rhywbeth gyda chwiliad llinol, neu ddidoli syml iawn algorithm, gan y byddwn yn gweld heddiw. Rhaid i chi ddechrau meddwl yn galetach ac yn fwy anodd am y problemau hyn. A'r mathau o broblemau lefydd fel Facebook, a Google, a Microsoft, ac eraill yn gweithio ar yn union y math o ddata mawr math o gwestiynau fwyfwy y dyddiau hyn. 

Mae pob hawl. Felly llwyddiant Jennifer yn yr ail algorithm, dweud y gwir, mae hi'n gwneud yn rhyfeddol yn dda y tro cyntaf, ond gadewch i ni ysgrifennu fel lwc er mwyn i ni gallu gwneud y pwynt hwn. Yn yr ail achos, mae'n ysgogi i algorithm sy'n ailadrodd eto ac eto, ond mae hi'n eu cymryd yn ganiataol yn rhagdybiaeth yn sicr ein bod yn caniatáu hi, ond mae hi'n manteisio rhai manylion y ail dro nad oedd yn cael y tro cyntaf. Pa oedd yr hyn? 

Bod y rhestr didoli. Felly, cyn gynted ag y rhestr didoli, yr ydym yn honni bod Jennifer yn gallu gwneud well o'u hanfod. 7 drysau, ie, nid yw hynny'n ddiddorol, ond mae'n debyg ei fod rydym yn 7 miliwn drysau. Log n yn bendant yn mynd i berfformio llawer, llawer gyflymach yn y tymor hir. Ond bu'n rhaid iddi gael y drysau trefnu ar ei chyfer. Yn awr, yr wyf yn cymryd y rhyddid o wneud hynny ymlaen llaw ar y sgrin cyfrifiadur yma, ond mae'n debyg fod Jennifer rhaid iddo wneud hynny ei hun? Tybiwch fod y drysau dan sylw data gynrychioli mewn cronfa ddata, neu ffrindiau cofrestru ar gyfer Facebook, neu unrhyw dudalennau gwe ar y rhyngrwyd sy'n Efallai y bydd angen gwahanol wefannau i mynegai neu chwiliwch drosodd. 

Gadewch i ni dybio eich bod newydd gael data crai gosod ac fe'i gadawyd i chi, neu i Jennifer i wneud hynny didoli? Mae hynny, yn hytrach, yn gofyn ein bod yn ateb y cwestiwn, yn dda, faint o amser byddai wedi cymryd Jennifer, neu hyd yn oed i mi, i ddatrys y niferoedd hynny ymlaen llaw fel y y gallai gymryd mantais o hynny? Iawn? Oherwydd bod y goblygiadau, wrth gwrs, yw os bydd yn cymryd cryn amser i mi i ddatrys y niferoedd, pwy y mae'r Heck gofalu eich bod Gellir dod o hyd i nifer debyg 50 mor gyflym, fel yn achos Jennifer yn, os ydym yn fwy na llethu faint o gyfanswm yr amser cymerodd drwy ddidoli pethau ymlaen llaw? 

Felly, gadewch i ni weld os na all y paent y darlun yma. Mae gen i criw cyfan mwy o straen peli, os yw hynny'n helpu torri'r iâ yma. Ac os na fyddech yn meddwl, rydym yn angen saith gwirfoddolwr - ar, OK. Wow. Felly nid oes rhaid i ni dreulio ar lampau desg, mae'n ymddangos. Mae pob hawl. Felly, beth am chi ddau o flaen. Beth am i chi ddau guys yn y cefn. Felly dyna pedwar. Beth am i chi o flaen pump, chwech a saith. Iawn yno. Mae eich ffrind sy'n eich pwyntio allan, er mwyn i chi gael y wobr. 

Mae pob hawl. Dewch ar i fyny. A pam nad ydym yn rhaid i chi guys yn dod ymlaen dros yma. Rydw i'n mynd i roi i bob nifer i chi. Ac yn mynd yn ei flaen ac yn trefnu eich hunain union i'r hyn sydd ddangosir ar y sgrin. 

[Ymyrryd yn LLEISIAU] 

DAVID J. Malan: OOP, mae'n ddrwg gennyf. Bug. Mae pob hawl. Wel, dyma ni yn mynd. Rhif pump. Rhif chwech. Un, dau, tri, pedwar, pump, chwech, saith. O, mae hyn yn lletchwith. 

SIARADWR 2: 'n annhymerus' jyst yn cael -. 

DAVID J. Malan: ddelio Da. Mae pob hawl. Diolch i chi am gymryd rhan. 

[Cymeradwyaeth] 

OK. Mae pob hawl. Felly, mae gennym bedwar, dau, chwech, un, tri, saith, pump. Perffaith felly mae gennym saith o wirfoddolwyr yma sydd yn gyfartal o led i'r amrywiaeth ein bod yn chwarae gyda'r cynharach. Ac yr wyf yn dewis saith am resymau a fydd yn unig cyfleus mewn ychydig. Ac yr wyf i'n mynd i gynnig cyntaf rydym yn datrys y saith wirfoddolwyr. Os hoffech, yn gyntaf, i ddweud helo er. Gan fod hyn yn mynd i fod yn lletchwith sawl munud. Cyflwyno eich hunain. 

GRACE: Hi, Im 'Grace. Rwy'n sophomore yn Leverett House. 

BRANSON: Hi. Rwy'n Branson. Rwy'n freshman yn Weld. 

Gabe: Hi. Rwy'n Gabe. Rwy'n iau yng Cabot. 

NEIL: Rwy'n Neil. Rwy'n freshman ym Matthews. 

JASON: Rwy'n Jason. Rwy'n freshman yn Greenough. 

MIKE: Rwy'n Mike. Rwy'n freshman yn Grays. 

JESS: Rwy'n Jess. Rwy'n sophomore yn Leverett. 

DAVID J. Malan: Ardderchog. Mae pob hawl. Wel, diolch yn fawr i bob un o'n gwirfoddolwyr yma hyd yn hyn. A'r her wrth law yn awr yn mynd i fod i ddatrys y rhain guys, ond wedyn rydym yn mynd i gael i feddwl ychydig yn galed am ba mor effeithlon ydym mewn gwirionedd eu datrys. Felly, gadewch i ni yn gyntaf rhowch gynnig ar hyn. Gallwch chi guys gweld y niferoedd gilydd dim ond drwy osod o gwmpas y corneli. Mynd yn ei flaen ac yn cymryd ychydig eiliadau, a fath eich hunain o'r lleiaf ar y chwith i'r mwyaf ar y dde. Go. 

OK. Da. A oedd yn gyflym iawn darn. Nawr rhywun yma, beth oedd y algorithm y guys y rhain yn berthnasol? 

SIARADWR 1: Lleiaf i fwyaf. 

DAVID J. Malan: OK. Lleiaf mwyaf yn wirioneddol datrys y amcan, ond nid wyf yn siŵr sy'n mewn gwirionedd algorithm. Yn anad dim er fwyaf yn dweud mi cam-wrth-gam beth i'w wneud. Yeah? 

SIARADWR 1: [Anghlywadwy] 

DAVID J. Malan: OK. Felly, os ydych yn gweld rhywun yn llai na'r eich rhif, yna symud i yr hawl ohonynt. Felly, mae hynny'n awr yn mynd yn fwy mynegiannol, fwy fel algorithm, oherwydd eich bod gallu dweud, os yw hyn, yna. Felly, rydym yn cael rhyw fath o lluniad amodol. Ac guys hyn yn ymddangos i wneud hynny ychydig amser, oherwydd bod rhai ohonoch wedi symud ychydig o bellter. Felly yr oedd yn ôl pob tebyg rhyw fath o dolennu yn digwydd yn eu meddyliau. 

Ond gadewch i ni geisio ffurfioli hynny. Pe gallech guys ailosod yn ôl i'r trefniant hwn. Gadewch i ni weld os na allwn ffurfioli hyn a ychydig, ac yna gofyn y cwestiwn, dim ond pa mor effeithlon yw hwn? Wrth gwrs, pan fyddwn yn gwneud hyn yn fwy araf, mae'n mynd i deimlo mor dda o algorithm, ond gadewch i ni weld os gallwn roi ein bysedd ar y camau manwl gywir. 

Felly rydych yn ddau guys yn bedair a dau. Neu gallwch drefn gywir neu'n anghywir? Amlwg yn anghywir. Felly, rydym yn cyfnewid. Nawr rydw i'n mynd i symud o'r neilltu yma a dweud, 05:56. A ydych yn gywir neu'n anghywir? 

Gabe: Cywir. 

DAVID J. Malan: Cywir. Chwech ac un? Na. Cyfnewid. Felly dyna dau cyfnewid. Chwech a thair? Na. Cyfnewid. Chwech a saith? Yn edrych yn dda. Saith a phum? 

JESS: [Anghlywadwy] 

DAVID J. Malan: OK, cyfnewid. A'u didoli. Mae pob hawl. Felly, yn amlwg nid, dde? Felly roedd yna mwy yn mynd ymlaen. Ond, yn wir, guys hyn, hyd yn oed dim ond yn reddfol. cadw i symud. Nid oeddent yn unig stopio, unwaith y byddant gywiro un broblem. So. Yn wir, yr wyf i'n mynd i gael i wneud yr un peth. Rydw i'n mynd i gael i ddatrys y ailddirwyn yn ôl i ddechrau'r broblem hon, neu ddechrau'r amrywiaeth hwn o pobl, gadewch i ni ddechrau eu galw. 

Ac yn awr yr hyn a ddylai fy algorithm ar yr ail tocyn yn? 

SIARADWR 1: Un peth. 

DAVID J. Malan: Un peth. Ac mae hyn, rwy'n dechrau i fel, dde? Cyn gynted ag y gallwch ddod o hyd i eich hun yn gwneud yr un peth dro ar ôl tro, dyna dod yn fwy fel algorithm, a greddf yn llai dynol. 

Felly nawr, yma rydym yn mynd eto. Dwy a phedair? Rhif Pedwar ac un? Ah, roedd yn wir mae rhai waith i'w wneud o hyd. Am a thri? Da. Pedwar a chwech? Chwech a phump? Chwech a saith? OK, yn awr, wedi gwneud. OK, dim. Rhaid i mi fynd yn ôl. 

Felly nawr, unwaith eto, rydym yn gwneud hyn ychydig yn fwy yn fwriadol. Ac yn awr, mae dim ond un ymennydd gweithredu algorithm hwn. Un CPU, os mynnwch. A dweud y gwir, dyna'r unig adnodd rydym yn mynd i gael mynediad atynt. Ac unwaith y byddwn yn mynd yn ôl i bysellfwrdd a chael rhywbeth fel C yn ein gwaredu, rydym yn unig yn ysgrifennu rhaglen a all wneud un peth ar y tro. Tra, guys hyn funud yn ôl, rydym yn ysgogi eu gadair ddu enwog Mastermind ar y cyd fel chi guys wnaeth yn wythnos sero. Felly, gadewch i ni barhau i wneud hyn. 

Dau ac un. Dau a thri. Tri a phedwar. Pedwar a phump. Pump a chwech. Chwech a saith. Wneud? Felly, yr wyf fi, ond gadewch i mi chwarae eiriolwr diafol. Ydw i'n, y math o gyfrifiadur sydd ond gwneud pasio drwy amrywiaeth hwn o bobl, yn gwybod fy mod yn ei wneud? 

SIARADWR 1: Na 

DAVID J. Malan: Felly pam? Beth fyddai'n rhaid i mi ei wneud er mwyn casgliad bendant fy mod yn ei wneud? Mae'n debyg mai un tocyn mwy. Iawn? Oherwydd bod yr holl wyf yn gwybod o'r blaenorol tocyn yw fy mod yn cywiro camgymeriad. Ac mae hynny'n golygu, efallai mae yn dal i gamgymeriad arall fod angen imi gywiro. Felly, ni allaf ond fod yn sicr gan ailddirwyn, a Yna, gwirio, 1-2, dau a tri, tri a phedwar, pedwar a phump, pump a chwech, chwech a saith. Iawn, yn awr yr wyf yn gwneud dim gwaith. 

Gallaf yn sicr yn cofio fy mod yn gwneud unrhyw gweithio gyda rhywbeth fel newidyn, hoffi int. Ffoniwch y cyfnewidiadau, ac os gyfnewidiadau yn 0 ar ôl i mi cyrraedd yma, ac mae'n dechrau ar 0, ac yna Byddai Fi jyst yn wirion i gadw i fynd yn ôl ac ymlaen, gan wirio eto, ac unwaith eto, ac unwaith eto, dde? Oherwydd eich bod yn mynd yn sownd mewn rhai math o dolen ddiddiwedd. Felly, cyn gynted ag y mae 0 cyfnewidiadau, gallwn honni bod hyn yn algorithm yn wir yn gyflawn. 

Yn awr, gadewch i ni roi enw ar hyn. Mae'r algorithm a gynigiaf ydym yn unig gweithredu yn rhywbeth o'r enw swigen fath, a elwir fel y cyfryw yn yr ystyr y y niferoedd sy'n yn garedig fwy o swigen eu ffordd i fyny i ben, neu hyd at ddiwedd y rhesi o rifau. Ond pa mor effeithlon oedd algorithm hwn? Faint o gamau oedd gen i yn gorfforol i cymryd, er enghraifft, i ddatrys y rhain saith o bobl? 

Bedwar i bump? OK, mae gormod o yn y pen draw mynd i fod yr ateb. Ond hyd yn oed wedyn, mae'r nifer penodol nid yw mor diddorol. Gadewch i ni cyffredinoli fel n. Felly, os wyf wedi n pobl i fyny yma, ac maent yn oedd, rhyw fath o, er ar hap yn y ddechrau, yn y drefn wreiddiol. Wel, faint o gamau oedd gen i i gymryd y tocyn cyntaf? Yr oedd yn un, dau, tri, pedwar, pump, chwech, ac maen nhw'n saith o bobl, felly dyna saith, chwech -, felly dyna n llai un camau y tro cyntaf. 

Yn awr, faint o gamau oedd gen i i fynd pan fyddaf yn rewound? Wel, gallem mewn gwirionedd yn dyblu, os rydym yn awyddus iawn i, ond am y tro, rwy'n jyst yn mynd i ddweud, yn iawn, n arall minws 1. Felly, y n minws 1 yn mynd i gael blino i gadw golwg ar, felly gadewch i ni dim ond rownd i fyny ychydig. Felly 2n cam. Felly 14 cam, yn rhoi neu gymryd. 

Sawl gwaith yr wyf yn cymryd cam y tro nesaf? Wel, mae'n 3n. mewn gwirionedd. Ac yn awr, yn yr achos gwaethaf, er enghraifft, faint o weithiau y byddai gennyf mynd yn ôl ac ymlaen, yn ôl ac ymlaen, weithredu algorithm hwn, cyfnewid pobl ar bob tocyn, yn fras? Mae'n mewn gwirionedd n sgwâr, dde? 

Gan fod yn yr achos gwaethaf, gallwch fath o feddwl am hyn yn reddfol, hyd yn oed er y gall gymryd ychydig yn dipyn o amser i suddo i mewn Yn yr achos gwaethaf, yr hyn y byddai'r rhain saith o bobl wedi edrych fel, yn ran y trefniant o'u rhifau? Hollol yn ôl, dde? A dim ond i efelychu hynny, beth oedd eich enw eto? 

MIKE: Mike. 

DAVID J. Malan: Mike? OK, Mike, gallwch ymuno â mi dros yma am ddim ond un eiliad? A dweud y gwir, dim. Mae'n ddrwg gennyf Mike, rewind gadewch i. Beth yw eich enw eto? 

NEIL: Neil. 

DAVID J. Malan: Neil. OK, Neil, byddwch yn dod â mi, os nad ydych yn meddwl. Felly, yr wyf i'n mynd i gynnig, dim ond ar gyfer symlrwydd, hynny Neil yn awr yn ei achos gwaethaf posibl. Ond yn cofio sut yr wyf yn rhoi ar waith fy algorithm. Rwy'n cymharu, cymharu, cymharu, cymharu, cymharu, oh. Nawr guys hyn allan o drefn, felly yr wyf yn atgyweiria. Felly rydych guys cyfnewid. Ond yn ystyried nawr, faint ymhellach mae Neil rhaid i chi fynd? Mae'n n fras. Rydych yn gwybod, nid yw'n n mewn gwirionedd. Mae'n debyg, n minws 1, ond rwy'n cael trac cadw flin o'r ychydig nifer, felly gadewch i ni dim ond alw yn n. 

Felly, os Neil yn symud un cam maximally bob amser, ac i symud Neil un cam, Rhaid i mi wneud y tocyn iawn 'n faith yn ôl ac ymlaen, mae hyn yn fras wneud hyn, n grisiau, cyfanswm o n gwaith, oherwydd ei fod yn mynd i fynd â mi bod llawer o gamau i gael Neil pob y ffordd i ble mae'n perthyn. Heb sôn am bawb arall os ydych yn guys i gyd yn cam-archebu hefyd. 

Felly, gadewch i ni alw fath swigen n sgwâr. Mae'r amser rhedeg algorithm hwn, mae'r berfformiad algorithm hwn, mae'r effeithlonrwydd y algorithm hwn, byddwn dim ond disgrifio mwy gyffredinol fel n sgwario. Pa yn neis, gan y byddwn yn gwneud y un enghraifft gydag wyth o bobl, naw bobl, a miliwn o bobl, a bod Nid yw ateb yn mynd i newid. 

Felly, os na fyddech yn meddwl guys, gadewch i ni chi ailosod i'r man lle y dechreuoch. A gadewch i ni geisio dau ddulliau eraill ac gweld os na allwn wneud sylfaenol yn well na hyn. Felly, y tro hwn, yr wyf i'n mynd i gynnig rhyw fath o algorithm gwahanol. A oedd yn glyfar iawn ohonom yn y tro diwethaf, ac yr ydych guys yn iawn i gael y greddfau hawl o'r fath yn unig o gyfnewid pairwise. Ond os wyf wir eisiau i fynd at y yn syml, a fy nod yw symud pob un o'r rhifau bach y modd hwn, ac gwthio yr holl rifau mawr sy'n ffordd, pam na Fi jyst gwneud hynny yn y mwyaf naïf ffordd posibl i weld os wyf yn Gall gwneud yn well na'r hyn a oedd yn deg algorithm cymhleth? 

Felly, gadewch i ni weld. Pedwar yn rhif eithaf bach, felly rwy'n yn mynd i adael i chi yno o bryd. Ooh, rhif dau yn oed yn well. Felly, gallwch gamu ymlaen ar gyfer hyn o bryd? Ar hyn o bryd fy rhif lleiaf ymgeisydd, ac yr wyf i'n mynd i gofio hynny gyda, fel, yn amrywiol. Ond dw i'n mynd i gadw gwirio. A oes rhywun y mae ei rhif yn llai? Chwech, dim. O, mae Neil eto. 

Felly, yr wyf i'n mynd i wthio yn ôl math o gysyniadol. Bydd Neil yn dod ymlaen. Ac yn awr, y newidyn fy mod i'n defnyddio i gadw cofnod o pwy sydd â'r lleiaf rhif yn cael ei ddiweddaru i gynnwys Lleoliad Neil. Wel, gadewch i ni weld. Three, saith, pump. OK, yr wyf yn gwybod Neil oedd y lleiaf. Beth yw'r peth symlaf i mi ei wneud nawr? Dydw i ddim yn mynd i wastraffu fy amser o ddim ond byrlymu Neil un man ar y chwith. Pam nad ydw i'n jyst rhoi Neil lle yn perthyn iddi, sydd wrth gwrs ble? 

Yr holl ffordd ar y dechrau. Felly Neil, dewch gyda mi. A beth oedd eich enw eto? 

GRACE: Grace. 

DAVID J. Malan: Grace. OK. Felly, Grace, yn anffodus, rydych yn fath yn y ffordd. Felly sut rydym yn datrys y broblem? Iawn? Os yw hyn yn amrywiaeth, mae dim ond saith o leoliadau. Dwyn i gof bod, gyda Rob, buom yn siarad am datgan oedran, a dim ond wedi cael nifer cyfyngedig o oedrannau? Un syniad yma. Dim ond nifer cyfyngedig o ints. Grace yn fath o yn ein ffordd, felly sut rydym yn atgyweiria? 

Y ffordd symlaf yw fel, Grace, mae'n ddrwg gennyf. Rydych yn mynd i gael i fynd dros yno er mwyn i ni wneud lle. Yn awr, os ydych yn meddwl am hyn, efallai rydym yn unig yn gwneud y broblem yn waeth. Ac efallai wnaethom, oherwydd yr hyn os Roedd Grace yn y lle iawn? Ond rydym yn gwybod nad yw, oherwydd fel arall, byddai wedi bod yn sefyll ymlaen yn hytrach na Neil ar hyn o bryd, dde? Rydym eisoes yn gwirio ei rhif allan. 

Mae pob hawl. Felly nawr, Neil sydd yn y lle iawn, ac Gallaf ei wneud ychydig o optimization. Am y funud nesaf, dw i'n mynd i anwybyddu Neil i gyd gyda'i gilydd, er mwyn peidio â gwastraffu ei amser, neu'n ddamweiniol cyfnewid ef i'r lle anghywir. Felly nawr, sut ydw i'n dod o hyd i'r nesaf elfen sy'n lleiaf? Dau. Dyna nifer 'n bert da, os ydych am i gamu ymlaen a 'N annhymerus' yn cofio i chi. Chwech, ddim yn dda. Pedwar, tri, saith, pump, ddim yn dda. Felly, gadewch i mi symud i chi eich lle iawn. Ac rydym yn jyst got ffodus y tro hwn. 

Yn awr, yr wyf i'n mynd i anwybyddu'r rhain dau guys, ac yn awr yn gwneud un yn fwy pasio drwy hyn. Chwech, bod nifer eithaf bach. Dewch ymlaen. O, mae'n ddrwg gennyf. Rhif Grace yn well, felly camu ar ei flaen. Pedwar. Mae'n ddrwg gennym, Grace. Ewch yn ôl eto. Rhif tri yn well. Saith. Five. Ac yn awr beth yw eich enw eto? 

JASON: Jason. 

DAVID J. Malan: Jason. Felly Jason bellach yw'r lleiaf elfen Rwyf wedi dewis. Ble mae e'n mynd i fynd? Felly, lle chwech yn. A'ch enw i yw eto? 

Gabe: Gabe. 

DAVID J. Malan: Gabe. Gabe sydd yn y ffordd. Beth yw'r peth hawsaf i'w wneud? Swap y ddau guys ac yn parhau. Felly nawr gadewch i ni weld. Pwy yw'r lleiaf? Pedwar. Gadewch yn unig fath o twyllo i mi. Pump yn mynd i fod y lleiaf. Rwy'n dod o hyd nesaf, os, yr ydych am i gamu ymlaen, beth sy'n rhaid i mi ei wneud gyda guys hyn, gyda Gabe? Cyfnewid eto. Felly nawr, yn dal ychydig allan o drefn. Cefais Gabe i fod y lleiaf, felly I pop ef allan, yn symud i chi guys drosodd. Ac yn ei wneud. 

Felly ateb yr un fath. Y canlyniad yw yr un fath. Pa un o'r ddau algorithmau yn well? Yr ail un, yr wyf yn clywed. Pam? 

SIARADWR 3: Mae'n n camau [Anghlywadwy]. 

DAVID J. Malan: Mae'n gamau n ar y mwyaf. Diddorol. Felly a yw'n er bod? Felly, sut wnes i ddod o hyd i'r elfen lleiaf? Faint o gamau oedd yn rhaid i mi gymryd y dod o hyd i'r elfen lleiaf? Roeddwn wedi i edrych yr holl ffordd ar y diwedd, dde? Oherwydd yn yr achos gwaethaf, yr hyn os oedd Neil dros yma? Felly, dim ond dod o hyd i'r elfen lleiaf mynd â fi n grisiau, neu n finws 1. Ond, OK. Felly atgyweiria Neil. Cofiwch eich bod yn a funud neu ddwy yn ôl. 

Ond sut wnes i ddod o hyd i'r nesaf elfen lleiaf? Mae'n n minws 1, neu n minws 2 mewn gwirionedd, o'r nifer o gamau. Felly OK. Felly, yr wyf ddim yn n minws 2. Mae pob hawl. Felly mae hynny'n teimlo ychydig yn well. Mae pob hawl. Faint o gamau y tro nesaf i ddod o hyd i rhif tri? Felly n minws 4. Felly, mae'n lleihau, un yn llai gam ar bob fersiwn. Felly, mae hyn yn teimlo'n well, dde? Os bydd amser diwethaf roedd tua n amseroedd n, y tro hwn mae'n n minws 1, yn ogystal n minws 2, ynghyd n minws 3, yn ogystal â n minws 4, dot, dot, dot. Ond os ydych yn cofio gan eich ysgol yn uchel gwerslyfrau, y twyllo ychydig taflen yn y cefn sydd â fformiwlâu, os ydych yn ychwanegu at y gyfres o rifau, beth yw cyfanswm y nifer o gamau mynd i fod fy mod yn cymryd yma? 

Mae hwn yn un o'r rhai, fel, n minws 1, amseroedd n, wedi'i rannu â 2. Felly, gadewch i mi weld os gallaf dynnu hyd yma am ychydig funud. Ac eto, yr wyf i'n fath o dalgrynnu rhai rhifau yn unig i gadw ein bywyd syml, ond fel yr wyf yn cofio, mae'n rhywbeth fel pe Wyf yn ei wneud n minws 1 bethau, yna mae n minws 2, yna mae n minws 3, mae'n fras rhywbeth fel hyn dros 2, ac os wyf yn lluosi hyn, dyna sgwâr n mewn gwirionedd. Nid yw hynny'n teimlo'n rhy dda. n minws n dros 2. 

Ond dyma y peth. Mewn gwyddoniaeth gyfrifiadurol, pan fydd y problemau dechrau cael diddorol yw pan n yn mynd yn wirioneddol fawr. A phan n mynd yn wirioneddol fawr, pa un o'r gwerthoedd hyn yn mynd i dra-arglwyddiaethu pob o'r lleill? Mae'n fath o y n sgwâr, dde? Ie, rannu â 2 yn eithaf da. Ond os ydych yn siarad am biliynau o ddarnau o ddata, neu triliynau o darnau o ddata, OK, felly eich bod yn ddwywaith mor gyflym. Ond sydd wir yn poeni os bydd y nifer mawr, os yw ffactor hyn yn beth yn cael fwy ac yn fwy. Ac yn sicr, mae'n gwneud mwy o gwahaniaeth na hyn guy. Felly hyd yn oed er eich guys yn iawn, mae'r ail algorithm, byddwn yn ei alw'n fath ddethol, yw, yn y byd go iawn, a ychydig yn gyflymach o bosibl, oherwydd yr wyf yn cymryd llai a llai o camau bob tro. 

Dyw hi ddim yn wir yn y bôn yn gyflymach. Oherwydd os ydym mewn gwirionedd yn chwarae y tu allan ar gyfer werthoedd mawr o n, ar ddiwedd y y dydd, am ddigon n mawr, mae'n dal i fod mynd i deimlo'n eithaf araf. Wel, gadewch i mi gymryd un pasio ddiwethaf am hynny. Dyna beth byddwn yn ei alw'n fath dethol. Allwch chi guys ailosod eich hunain am y tro olaf? Ac yn yr achos diwethaf, yr wyf i'n mynd i gynnig rhywbeth Gelwir fath gosod. Fath Mewnosod lles, yn gysyniadol, ychydig yn wahanol. 

Yn hytrach na mynd yn ôl ac ymlaen a ddewis yr elfen lleiaf, rwy'n dim ond yn mynd i ymdrin â phob un o'r rhain guys fel yr wyf yn dod ar eu traws nhw, a rhowch iddynt yn eu lle cywir. Felly, Im 'jyst yn mynd i ddechrau gyda Grace, ac yr wyf yn gweld ei bod yn rhif pedwar. Ble mae rhif pedwar yn perthyn? Nid wyf wedi dechrau didoli unrhyw beth, felly Grace yn mynd i aros iawn yno. Ac yn awr yr wyf i'n mynd i wneud cais, os gallech cymryd cam i'r dde, mae hyn yn fy rhestr datrys, mae hyn yn fy rhestr heb ei threfnu ar ôl. Felly, yn awr yr wyf i'n mynd i symud ymlaen nesaf, a beth yw eich enw eto? 

BRANSON: Branson. 

DAVID J. Malan: Branson. Felly Branson yn rhif dau. Felly, yr wyf i'n mynd i fynd â chi allan am funud. Ac yn awr, os ydych chi'n perthyn yn y casgliad hwn? Felly, i'r dde o'r Grace. Felly, unwaith eto, rydym yn fath o wneud Grace yn gwneud llawer o waith yma. Ble rydym yn rhoi i chi? Felly, rydym yn mynd i lithro chi i'r chwith, a gosod Branson yno. Ond yn awr yr wyf yn honni bod rydych guys yn cael eu gwneud. Ond rhybudd, dydw i ddim yn defnyddio gofod ychwanegol. Mae'n dal i fod 2 elfen yma, 5 dros yma. Cyfanswm maint array yw 7, felly rwy'n Nid yw twyllo, iawn? 

Felly, erbyn hyn mae gennym, gyda Gabe yma, y rhif chwech, ble ydych chi'n perthyn? Rydych got 'n ffodus eto. Felly, byddwch yn cael i aros yn iawn yno. Dim ond yn cymryd ychydig yn gam i'r dde dim ond er mwyn gwneud yn glir eich bod yn didoli. Ac yn awr mae gennym Neil eto, rhif un, ble rydych chi'n mynd? Ac yn awr lle y byddwn yn dechrau gweld bod algorithm hwn, er ar y tro cyntaf golwg, yn teimlo 'n bert smart, gwylio beth sydd ar fin digwydd. Pe gallech gamu ymlaen. 

Ble ydym ni eisiau i roi Neil? Felly yn amlwg yma, felly sut y ydyn ni'n cael Neil yno? Gadewch i ni wneud y cam-wrth-gam. Gabe, lle y mae angen i chi fynd? Yep, felly cymryd un cam mawr, neu ddau hanner-camau i wneud un cam dros yno. Grace, ble rydych yn mynd? Da. Felly, cam arall. Ac yn olaf, Branson? Cam arall. Ac yn awr y gallwn roi Neil ar waith. 

Felly nawr, yn parhau rhesymeg hwn. Hyd yn oed er nad ydym yn symud Neil throsodd, a throsodd, a throsodd, ei roi lle y mae'n mynd, yn yr achos gwaethaf, y rhif nesaf efallai y byddwn yn dod ar draws y gallai fydd y nifer, yn dweud, roedd nifer sero, yna rydym yn mynd i symud yr holl guys hyn. Tybiwch fod yna nifer, negyddol un, yna mae'n rhaid i ni symud pob un o'r rhain guys. Felly, rydym yn wir yn unig fath o flipping y broblem o gwmpas, fel ein bod ni'n trosglwyddo'r gost o broses ddethol er mwyn gosod broses, fel bod chi guys newydd gael i symud yn fras n minws rhywbeth nifer o gamau. Ac mae'r nifer o gamau yn mynd yn unig i gynyddu wrth i mi dewis mwy rhifau, os oes rhaid i mi gadw gwthio i chi guys yn ôl, ac yn ôl, ac yn ôl. 

Felly, y peth drist yn awr yw pob un o'r rhain algorithmau yn cael eu n sgwâr. Gadewch i ni fynd yn ei flaen a diolch i'r guys, a delweddu hyn, mae ychydig wahanol. Gwneud yn dda iawn. 

[Cymeradwyaeth] 

Mae pob hawl. Dyna chi. Diolch am - 

BRANSON: [Anghlywadwy] cadw'r rhifau. 

DAVID J. Malan: Na, efallai y gallwch cadw'r rhifau hefyd. Mae pob hawl. Gwneud 'N glws. Mae pob hawl. Felly, gadewch i ni weld os na allwn grynhoi nawr yn gyflymach, ac yn fwy gweledol, yn union yr hyn a ddigwyddodd yn unig yma fel a ganlyn. Rydw i'n mynd i fynd yn ei flaen a thynnu i fyny Firefox. Byddwn yn cysylltu arddangosiad hwn ar wefan y cwrs. Java yn ychydig yn blino i gael gweithio mewn rhai porwyr y dyddiau hyn. Felly, os ydych yn chwarae gyda hyn yn y cartref, yn sylweddoli efallai y bydd angen i chi ddefnyddio Firefox i'w gael i weithio. A hyn yr wyf i'n mynd i wneud â hyn arddangos yn y canlynol. 

Ar y gwaelod, mae gen i criw cyfan o ddewislen opsiynau, gan gynnwys dechrau a rhoi'r gorau i botwm. Hefyd, wrth fynd heibio, mae'n ymddangos i fod yn bug yn y rhaglenni hyn, lle rydych Ni all mewn gwirionedd yn gweld dechrau neu'n rhoi'r gorau i botwm oni bai eich bod yn dal Reoli neu Alt a mwy a chwyddo i mewn, sy'n rhyfedd yn dangos i chi mwy o botymau. Felly dim ond FYI os ydych yn chwarae gyda hyn yn y cartref. Nawr rydw i'n mynd i glicio Start mewn dim ond hyn o bryd, ar ôl nodi oedi o, fel, 200 milieiliadau yma, dim ond fel y gallwn weld beth sy'n digwydd. 

Felly, yr wyf yn honni bod hyn yn delweddu o'r algorithm cyntaf wnaeth guys hyn, didoli swigen, lle rydym yn cyfnewid pobl pâr-ddoeth. Mewnwelediad allweddol i delweddu hwn yw bod y uchder y bariau cynrychioli maint o nifer. Felly, y talach y bar, y mwyaf yw'r rhif. Byrraf y bar, lleiaf yw'r rhif. Ac os byddwch yn sylwi, rydym yn mynd drwy y fersiwn cyntaf o algorithm hwn, cyfnewid rhifau mawr a bach, fel y y nifer fach yn dod yn gyntaf ac yn y nifer fawr yn mynd i'r dde. 

A chyn gynted ag yr ydym yn cael y diwedd amrywiaeth llawer mwy o rifau na saith, rydym yn mynd i fynd yn ôl i'r dechrau. A rhagweld hyn. Ar y chwith yn hyn, ychydig y boi yn mynd i gyfnewid i'r ochr, ac mae hyn yn ailddarllediadau broses. Nawr delweddu hyn yn mynd yn gyflym ddiflas, felly gadewch i mi fynd yn ei flaen ac yn rhoi'r gorau i iddo, yn newid yr oedi rhywbeth llawer gyflymach dim ond i gael nawr, ymdeimlad algorithm hwn. 

Felly hyd yn oed er fy mod i wedi sped i fyny, mae hyn yn fel uwchraddio fy prosesydd, prynu cyfrifiadur newydd. Nid wyf wedi newid yn sylfaenol fy algorithm, ond gallwch yn wir weld mwy o glir na gyda phobl, bod y mawr niferoedd yn byrlymu i fyny i ben, ac mae'r niferoedd bach yn byrlymu i lawr i'r gwaelod. Ac yn awr y peth hyn sortio yma. Ac wrth fynd heibio, yn y sgwariau, mae dim ond rhai cadw llyfrau yno i eich helpu i gyfrif faint o gymariaethau, na faint o gyfnewidiadau wedi mewn gwirionedd yn cael ei wneud. 

Wel, gadewch i ni roi cynnig ar un o'r y lleill a welsom. Gadewch i mi cliciwch ar swigen fath yma, ac gadewch i mi ddewis, ac mae hyn yn dudalen we gyfan ychydig yn buggy. Gadewch i ni dderbyn y risg a'i redeg eto. Dyna ni. Felly, gadewch i ni wneud y math dethol. Nid wyf yn gwybod pam y fwydlen ymddangos dros yno. Gadewch i chwyddo i mewn i atgyweiria bod bug, newid hyn i 50. Ah, gadewch i ni wneud mewn gwirionedd bod llawer cyflymach. Pum milfed eiliad neu ddwy, ac Start. 

Felly, mae hyn yn fath dethol. Felly, unwaith eto, meddyliwch am yr hyn yr ydym yn gwnaeth gyda'r bobl i fyny yma. Aethom drwy'r amrywiaeth a ddewiswyd yr elfen lleiaf eto, ac unwaith eto, ac unwaith eto. Yn awr yr wyf yn honni bod yn dal yn eithaf gwael. Yr oedd yn dal n sgwario, rhoi neu gymryd, ond oedd hi, yn y byd go iawn, ychydig yn gyflymach, gan fy mod yn wir yn cymryd ychydig yn llai o gamau bob tro. Ond rydym yn dim ond siarad beth? Efallai 40 neu lai bariau yma? Nid ydym yn sôn 40 miliwn. Felly nid yw'n hollol glir i mi fod oedd yn wir yn ennill arwyddocaol. 

Gadewch i mi yn awr fynd yn ôl a newid at ein drydydd algorithm, a gafodd ei ddewis fath gosod. Ac yn awr mae'n hynod bygi oherwydd bod y menu Ni ddylai mewn gwirionedd fod yn i lawr yno. Felly nawr byddwn yn sgrolio yn ôl i fyny yma a dechrau algorithm hwn. Whoop, dechrau a stopio. Felly mae hyn yn un math o batrwm eithaf iddo, lle rydym yn eto osod y bobl, neu mewn yr achos hwn, y bariau i mewn i eu lleoliad priodol. Ac mae'n ei wneud yn barod cyn Rwy'n troi o gwmpas. Ond mae hyn yn un, hefyd, mewn theori, yn dal n sgwâr. 

Felly gadewch i ni weld os na allwn grynhoi rhain fel a ganlyn. Rydw i'n mynd i fynd yn ei flaen a dim ond i roi ni fath o ffordd gyffredin o siarad am y pethau hyn, gadewch i mi gyflwyno dim ond ychydig o nodiant yma. Rydych chi ar fin i weld rhywbeth a elwir yn fawr O, am ei fod yn llythrennol yn fawr O. Ac mae hyn yn ffordd y cyfrifiadur gwyddonydd neu hyd yn oed yn defnyddio mathemategydd i ddisgrifio amser yn rhedeg o rai algorithm. Faint o gamau y mae'n mewn gwirionedd yn cymryd? 

Nawr rwy'n mynd i godi cywilydd fy hun gyda fy llawysgrifen yma mewn dim ond hyn o bryd. Ond gadewch i mi fynd yn ei flaen ac yn dweud bod bydd hyn yn O mawr dros yma. A gadewch i mi gyflwyno un arall symbol, a omega cyfalaf. Omega yn mynd i fod i'r gwrthwyneb, yn y bôn, o O. mawr Er O mawr yn golygu, yn yr achos gwaethaf, faint o amser gallai rhai algorithm cymryd, mewn nhermau n, omega yn mynd i fod faint o amser y gallai ei cymryd yn yr achos gorau. A gawn ni weld beth ydym yn ei olygu wrth achos gorau mewn dim ond hyn o bryd. 

Felly, gadewch i ni ddechrau rhywbeth syml. Gadewch i mi ddechrau gyda chwiliad llinol. Felly nid didoli. Byddwn yn galw chwiliad llinol hwn. Ac yn awr, yn gwneud ychydig tabl allan o hyn. Ac yn awr, yn achos chwiliad llinol, yn yr achos gwaethaf, faint o gamau yn mae'n mynd i gymryd i mi ddod o hyd i nifer o ddewis mympwyol? Ac mae n ddrysau cyfanswm neu n chyfanswm niferoedd. Achos gwaethaf. Faint o gamau ydw i'n mynd i gael i cymryd i ddod o hyd i'r rhif 50 mewn amrywiaeth n drysau? A pham? Oherwydd gallai fod yn yr holl ffordd dros ar y diwedd. Felly, yn debyg iawn Jennifer traws, y rhif 50 yn yr holl ffordd dros, felly yn y chwiliad llinol achos gwaethaf yn fawr O n, byddwn yn dweud. 

Beth am yr achos gorau, os ydych yn cael wirioneddol lwcus? Mae'n jyst yn mynd i gymryd un cam, neu nifer cyson o risiau. Felly, byddwn yn disgrifio hynny fel 1. Felly, mae hyn yn eithaf da. Nawr, beth os ydym yn gwneud rhywbeth hoffi chwiliad deuaidd? Chwilio Felly deuaidd, yn y gwaethaf achos, cymerodd faint o amser? 

[Ymyrryd yn LLEISIAU] 

DAVID J. Malan: Felly mewn gwirionedd, yr wyf yn glywed mewn llefydd cwpl. Felly, mae'n mewn gwirionedd yn logio n, rhoi neu gymryd, oherwydd wrth i ni rhannu'r rhestr yn ei hanner unwaith eto, ac unwaith eto, ac unwaith eto, rydym yn gallu i ddod o hyd, yn y pen draw, mae'r gwerth, os yw'n yno, ond mae yna dal. Beth yw'r dybiaeth bod yn rhaid i eu cymryd yn ganiataol ar gyfer chwiliad deuaidd? Mae'n rhaid iddo gael ei datrys. Dyw hi ddim yn didoli, gallwch rannu'r peth yn ei hanner eto ac eto, ac yr ydych yn gallu mynd i'r chwith, a gallwch fynd yn gywir, a gallwch fynd i'r chwith a dde, ond rydych yn ddim yn mynd i ddod o hyd i'r elfen os nid yw'r rhestr yn cael ei datrys, oherwydd efallai y byddwch yn gweld ei eisiau. Oherwydd bod eich hewristig, am fynd chwith neu hawl yn mynd i fod yn ddiffygiol os yw'n yn wir nid didoli. Felly, mae yna fath o gost gudd i ddefnyddio rhywbeth fel hyn. 

Yn awr, gadewch i ni fynd i mewn i'n didoli algorithmau na chwilio - oh, mewn gwirionedd gadewch i ni fynd yn hwn yn wag. Chwiliad deuaidd yn yr achos gorau? Mae hefyd yn 1 os 'i jyst yn digwydd bod yn yng nghanol iawn y rhesi, neu ganol y llyfr ffôn. Nawr, gadewch i ni wneud y math swigen. Felly, unwaith eto, yn awr rydym yn mynd i mewn i'r fath, nid yw'r chwiliadau. 

Yn yr achos gwaethaf, faint o gamau wnaethon ni hawliad fath swigen yn mynd i gymryd? n sgwario. Felly, yr wyf i'n mynd i dynnu hynny. Ooh, fy llawysgrifen yn edrych hyd yn oed yn waeth pan gaiff ei amcanestynnir y bydd mawr. Mae pob hawl. Felly, mae hynny'n n sgwâr. Ac yn yr achos gorau o'r math swigen, faint o gamau y mae'n mynd i gymryd? 1, yr wyf yn clywed. 

SIARADWR 1: n. 

DAVID J. Malan: n, yr wyf yn clywed. 

SIARADWR 1: 2. 

DAVID J. Malan: 2, yr wyf yn clywed. Ydw i'n clywed 3? Mae pob hawl. Felly, yr wyf wedi clywed 1, n, 2, ond gadewch i ni ddewis ar wahân o leiaf y cyntaf o'r rheini awgrymiadau, 1. Dyw hi ddim yn reddf drwg, oherwydd ei fod yn fath o dilyn patrwm yma. Ond os mai dim ond yn cymryd 1 cam, sut yn y Gallai byd yr wyf yn honni bod y rhestr yn cael ei datrys, oherwydd os wyf yn unig a ganiateir i gymryd 1 cam, faint o elfennau Gallai Fi 'n weithredol gwirio i fod yn sicr? Wel, dim ond 1, sy'n golygu mae n minws 1 Elfennau a allai fod allan o gorchymyn, a Im 'jyst yn mynd ar ffydd ar ôl edrych ar 1 elfen y mae'r beth yn cael ei datrys. Felly, 1 e ddim yn gywir yma. Felly cyn lleied â phosibl, faint o mae'n rhaid i mi edrych ar? 

[Ymyrryd yn LLEISIAU] 

DAVID J. Malan: n minws 1, neu, mewn gwirionedd, n, oherwydd mae angen imi edrych ar bob elfen i wneud yn siwr bod nid yw'n allan o drefn. Ond unwaith eto, byddwn yn trefnu o don ein dwylo ar y niferoedd llai a cymryd yn ganiataol bod, fel y n cael fawr, maen nhw'n anniddorol beth bynnag. Felly dyna fath swigen. Ac yn awr, gadewch i ni wneud y ddau ddiwethaf. Fath Dethol, ac yna gallwn eich wneud y math gosod. Ac yna byddwn yn chwythu eich meddyliau gyda rhywbeth llawer yn well na rhain i gyd. Mae pob hawl. 

Beth yw yr achos gwaethaf rhedeg amser o'r fath dethol? 

SIARADWR 4: n sgwâr. 

DAVID J. Malan: n sgwâr, rwy'n clywed. Ond pam n sgwario, yn reddfol? 

SIARADWR 4: Gan ein bod yn unig yn gwneud hynny. 

DAVID J. Malan: Gan ein bod yn unig yn gwneud hynny. OK. Ateb da. Ond yn reddfol, pam dewis didoli n sgwâr? Beth oedd yn rhaid i ni ei wneud dro ar ôl tro? Roedd rhaid i ni gadw sganio drwy, yn i chi y lleiaf, a ydych yn y lleiaf, yw'r lleiaf chi. Ac ganiataol, roeddem yn gallu cymryd n gamau, yna n minws 1, yna mae n minws 2. Ond os ydych yn fath o ychwanegu hynny i gyd i fyny, neu fynd ag ef ar y ffydd yr wyf wedi ychwanegu nhw ymlaen llaw, rydym yn cael tua n sgwâr minws rhai rhifau llai. Felly, yr wyf i'n mynd i alw n hon sgwâr. Ond gyda'r math dethol y gorau achos, faint o gamau y mae'n mynd i fynd â mi? 

SIARADWR 5: [Anghlywadwy] 

DAVID J. Malan: Mae'n anffodus dal n sgwario, dde? Oherwydd os wyf yn dewis y lleiaf elfen, ac roedd gennym saith o bobl yma, Dim ond yn gwybod, ar ôl i mi gyrraedd yr union diwedd, fy mod wedi dod o hyd y lleiaf rhif, lle bynnag y bo ef neu gallai fod wedi bod. Ond sut ydw i'n dod o hyd i'r nesaf nifer lleiaf? Rhaid i mi wneud pasio arall. Felly, yn yr achos gorau, beth yw'r mewnbwn i ddidoli dethol? Mae'n rhestr fath eisoes, rhif un, rhif dau, rhif tri, rhif pedwar. Ond rwy'n cyfrifiadur. Ni allaf ond edrych ar un peth ar y tro. Nid wyf yn gallu datrys o gymryd cam yn ôl fel bod dynol ac yn dweud, www, mae hyn yn edrych yn gywir. 

Ni allaf ond farnu cywirdeb yn didoli dewis drwy ddewis y nifer lleiaf. Ond hyd yn oed os wyf yn dod o hyd i rif un cyntaf, os nad wyf yn gwybod unrhyw beth arall am y rhifau eraill, ac nid wyf yn ei wneud, y cyfan yr wyf yn gwybod fy mod i wedi bod yn rhoi arae neu set o ddrysau y tu ôl sy'n cael eu rhifau, yr unig ffordd rwy'n gwybod bod un oedd y lleiaf? Os byddaf yn cael yr holl ffordd yma ac yn sylweddoli, damn, roedd un yn wir y lleiaf. 

Ond sut ydw i'n wedyn yn penderfynu bod dau yw'r lleiaf nesaf? Drwy wneud yr un aneffeithlonrwydd dro ar ôl tro. Felly, yn olaf, gyda'r math mewnosod, sut, yn yr achos gwaethaf, oeddem yn dweud ei fod yn perfformio? Mae hefyd yn n sgwâr. A beth am â'r achos gorau? Byddwn yn gadael hynny fel Cliffhanger. Byddwn yn llenwi yn yr gwag y tro nesaf, ond yn gyntaf gadewch i mi cynnig ein bod yn sylfaenol yn gwneud yn well na pob un o'r rhain, iawn? 

Felly meddyliwch drosoch eich hun beth osod fath yn mynd i fod. Wel, nad oedd hynny'n ddramatig iawn, oherwydd fy mod i'n yr unig un a welodd y newid. Wow. OK. Felly dyma gennym braidd arddangos gwahanol. Os byddaf yn chwyddo i mewn yma, byddwch yn gweld bod ar y chwith mae gennym fath swigod, yn y canol mae gennym fath dethol, ac ar y dde, mae gennym rywbeth yr ydym nid wyf wedi edrych eto ar Gelwir uno fath. Ond yn ystyried yr hyn yr ydym wedi bod yn wneud yma hyd yn hyn heddiw. Pan ddaeth Jennifer cyntaf i fyny ar y llwyfan, aethom trwy amrywiaeth o rifau unwaith eto, ac unwaith eto, gyda chwiliad llinol, ac rydym yn cael amser yn rhedeg llinol, O mawr n, fel petai. 

Pan fyddwn yn awr yn ystyried yr wythnos gyntaf dosbarth, pan fyddwn wedi rannu a goncro, ac yr oeddem wedi y llyfr ffôn rhwygo, a Jennifer, ac rydym ar y cyd ysgogi bod mewnwelediad allweddol, a oedd i ailadrodd eich hun dro ar ôl tro gan rhywsut taflu i ffwrdd, taflu i ffwrdd, taflu i ffwrdd, hanner y broblem, neu yn gyffredinol, gan rannu problem yn ei hanner, ac yna trin y darn llai o y broblem yn gyfwerth gysyniadol i'r llall, yr ydym rywsut oedd well o'u hanfod. Ond gyda'r math swigen, gyda dewis fath, gyda'r math mewnosod, rydym wedi gall unrhyw syniadau fel bod Jennifer wnaeth. Rydym yn 'n bert lawer yn cerdded yn ôl a allan criw cyfan o weithiau, ac rydym yn pethau tweaked ychydig bach, cyfnewid yn y drefn hon, efallai gosod neu ddewis. Ond ar ddiwedd y dydd, yr wyf yn gwneud llawer o gerdded lletchwith yn ôl ac ymlaen. Nid ydym yn gwneud rhywbeth yn iawn leverage smart fel Jennifer ddim yn hoffi rhannu a concro. 

Felly uno fath, ar y llaw arall, yr ydym yn Ni fydd gweld tan yr wythnos nesaf, mae'n mynd i trosoledd y syniad hwnnw allweddol drwy rannu mewnbwn, ac yna haneru, ac yna haneru, ac yna haneru. Ac ar bob fersiwn y ddolen, didoli yr hanner chwith, a'r hawl hanner, yna hanner chwith y chwith hanner, a hanner dde y chwith, yna hanner chwith y hanner cywir, a yr hanner dde o'r hanner cywir. Ac ailadrodd dro ar ôl tro. 

Felly, byddwch yn gweld hyn yn eu golwg, ond mae hyn yn yn disgwyl i ni beth yr wythnos nesaf. Ac yn gyffredinol, pan fyddwn yn meddwl ychydig yn ychydig yn galetach am unrhyw broblem o'r fath. Rydym wedi n sgwâr ar y chwith, n sgwâr yn y canol, ac n mewngofnodi n ar y dde. Felly, mae eich Cliffhanger go iawn. Byddwn yn eich gweld ar ddydd Llun. 

[Cymeradwyaeth]