SIARADWR: pob hawl, mae hyn yn CS50. Mae hyn yn ddiwedd yr wythnos tri, ac os nad ydych wedi cymryd mantais eisoes, gwybod y bydd cinio dydd Gwener hwn yn ôl yr arfer, lle mae gallwch fwynhau sgwrs da a bwyd yng Tân ac Iâ gyda rhai o CS50 yn staff a chyd-ddisgyblion. Ewch i URL hwn yma. Nawr efallai y byddwch yn cofio, neu os ydych yn Efallai cyn bo hir yn cael ei adnabod, pethau hyn yma, a oedd yn yn cael eu rhoi allan ar y diwedd y semester ar gyfer llawer o ddosbarthiadau. Hyn a elwir yn arholiad llyfrau glas, lle chi ysgrifennu eich atebion i arholiadau. Nawr rwyf wedi yma 26 o'r fath llyfrau glas, ar bob un ohonynt ei ysgrifennu enw, A drwy Z. A yn wir yr enwau yn y syml, A drwy Z. Ac un o y nodau wrth law heddiw yn mynd i fod i barhau yr hyn rydym yn dechrau ar ddydd Llun, nad yw'n cymaint yn edrych ar god, ond mewn gwirionedd edrych ar syniadau a datrys problemau. Un o'r nodau ac addewidion y cwrs hwn yw eich dysgu i feddwl yn fwy ofalus, yn fwy yn drefnus, ac i ddatrys problemau yn fwy effeithlon. Ac yn wir, gallwn wneud hynny mewn gwirionedd heb hyd yn oed yn cyffwrdd y llinell o god. Felly mae gen i un neu ddau o eliffantod fyny yma heddiw, oren a glas, pe gallem gael un gwirfoddolwr, efallai o farther yn ôl na'r arfer. Beth am iawn yno, yn dod ar i lawr. Mae'r nod o sydd yn mynd i fod i help yn ogystal â gweinyddu'r arholiad hwn yma. Beth yw eich enw? CYNULLEIDFA: Mary Beth. SIARADWR: Mary Beth, yn dod ar i fyny. Gadewch i mi gael y meicroffon yma i chi. Neis i gwrdd â chi. CYNULLEIDFA: Neis i gwrdd â chi. SIARADWR: pob hawl, felly mae gen i yma llyfrau glas A drwy Z, ac yr wyf i'n mynd i esgus bod Mae gen i un o'r myfyrwyr, ac maen nhw'n dod i mewn braidd ar hap ar ddiwedd bloc arholiad tair awr, felly maent yn dod i ben i fyny mewn rhai trefn lled-hap fel hyn. Nawr eich swydd mewn dim ond hyn o bryd yn mynd i be-- hyn mewn gwirionedd sut y maent yn ei gael troi i mewn ar ddiwedd y dosbarth, yn fwyaf tebygol. Mae eich swydd yn awr yn mynd i fod, yn eithaf yn syml, i ddidoli y llyfrau glas i ni o A trwy Z. CYNULLEIDFA: O, mae hyn yn mynd i gymryd am byth. SIARADWR: A byddwn yn gwylio wrth i chi wneud hyn, dim pwysau. CYNULLEIDFA: Na, dim pwysau neu unrhyw beth. SIARADWR: Ac am hwyl, gadewch i ni roi i fyny amserydd. CYNULLEIDFA: Felly o hwyl, yn gymaint o hwyl. SIARADWR: Yr wyf yn gallu dal y meic i chi. Mae pob hawl, rydym wedi dyblu yn unig ein cyflymder. Felly, yn y cyfamser, gadewch i mi beri beth sydd mynd i fod y cwestiwn ar gyfer Mary Beth yn yr hyn y mae hi'n ei wneud, sut mae hi'n mynd ati i ddatrys hyn? Ac yn wir, ni allai fod gennych erioed wedi meddwl am rywbeth mor syml â phan fyddwch yn dewis i fyny 26 o lyfrau fel hyn, oes ganddynt naturiol yn gorchymyn iddynt. Beth yw'r broses yr ydych yn ei ddefnyddio? A yw'n deg ar hap yn unig casglu yr un cyntaf y byddwch yn gweld a'i roi yn ei le? A ydych yn symud eich dwylo yn gyntaf o gwmpas edrych am A wedyn chwilio am B? A ydych yn cymryd golwg ar y pâr ohonynt ochr yn ochr a dim ond dweud, arhoswch funud, mae hyn Nid yn iawn, ac yna'n cyfnewid y gorchymyn? Gwelsom eisoes ar ddydd Llun fod yna nifer o ffyrdd lle y gallwn wneud hyn, ac yn wir wrth i ni agosáu at ddiwedd yma, Byddwn yn cymryd sylw o bosibl o'r hyn a Mary Beth yn ei wneud. Mae gennym ychydig o pentyrrau mae'n ymddangos, a fwy un, tri rhai llai. CYNULLEIDFA: Rydw i'n eu archebu pan fyddaf yn dod o hyd dau lythyr fy mod yn gwybod yn gyda'i gilydd mewn dilyniant, Yr wyf yn rhoi at ei gilydd fel nad wyf yn ei wneud rhaid i chi boeni am gadw trac o res gyfan o lyfrau. 'I' jyst, oh, A yn gyntaf, Mae gen i stac hwn yma. SIARADWR: Felly, bron fel o ddarnau pos sy'n yn cael y siâp cywir i yn cyd-fynd i fyny gyda'i gilydd. CYNULLEIDFA: 'N bert lawer, yeah. SIARADWR: OK, rhagorol. Ac yn awr pob un o'r rhain pentyrrau cael ei ddidoli yn ôl pob tebyg? CYNULLEIDFA: Yeah. SIARADWR: pob hawl, A drwy Z. All iawn, llongyfarchiadau, y gwnaethoch chi hynny. Mae gennych eich dewis. Glas? Mae pob hawl, diolch i chi am hynny. Felly Mary Beth wnaeth gynnig beth oedd ei dull gweithredu, ond yr hyn sy'n ddull arall sut yr ydych yn Gallai fynd ati i ddidoli pethau hyn? Beth fyddech chi wedi ei wneud? Byddai'r cofnod i guro wedi bod un munud a 50 eiliad neu lai, yn ogystal â'r rhai yr wyf yn anghofio i gyfrif. Beth fyddech chi wedi ei wneud? Yeah? CYNULLEIDFA: Cymerwch y pentwr. Dechrau o'r dechrau. Gwiriwch eich papurau. Ac os yw'r un uchaf yn uwch nag, efallai, y maent, mae'r un gwaelod yn uwch, ac yna eu newid. SIARADWR: Iawn, felly cychwyn ar y brig a'r gwaelod, ac yna gweithio eich ffordd o'r tu allan fel 'na, yn eu cyfnewid? Iawn, felly ychydig yn debyg mewn ysbryd i'r math swigen, ond dewis y eithafion Nid yw'r parau cyfagos. Ond y tymor byr ohono yw bod yna sicr bagad o ffyrdd gwahanol gallem wneud hyn, ac a dweud y gwir, yr wyf yn meddwl i chi fath o mabwysiadu ymagweddau cwpl, dde? Gwnaethoch fath o bedwar pentwr ddidoli, a Yna uno nhw at ei gilydd yn effeithiol. A dyna, mentraf ddweud, un arall dechneg yn gyfan gwbl. Doeddech chi ddim yn ei drin fel un pentwr mawr, chi rhannu'r broblem yn bedwar quads, os mynnwch, ac yna rhywsut Unodd nhw yn y diwedd. Felly, gadewch i ni ystyried, yn y pen draw, sut arall y gallwn wneud hyn. Rydym yn ffurfioli y syniad o swigen didoli tro diwethaf, a didoli swigen cofio yn algorithm yr ydym yn dychmygu gydag wyth o'ch cyd-ddisgyblion i fyny yma, ymddangos yn didoli ar hap ar y dechrau. Ac rydym Yna penderfynodd pairwise, os dwy elfen yn allan o drefn, yn syml yn eu cyfnewid. Felly pedwar a dau yn yn amlwg allan o drefn, felly y ddau cyd-ddisgyblion troi swyddi. Ac yna rydym yn ailadrodd gyda pedwar a chwech, Yna, chwech ac wyth, ar bob iteriad, symud i'r dde. Felly o ystyried, faint o pairwise wyth o bobl cymariaethau wnes i wrth gerdded o chwith i'r dde mewn un fersiwn o'r fath? Faint o gymariaethau? Saith, dde? Oherwydd os oes wyth bobl ond mae gennych y pâr nhw ac eich bod yn cadw i symud un hop ar y dde, nad ydych yn mynd i gael wyth cymariaethau oherwydd na allwch gymharu elfen yn erbyn ei hun, neu y byddai unig fod ddibwynt, felly mae gennych saith. Neu'n fwy cyffredinol, os mae gennym n bobl, rydym yn wneud minws n 1 cymariaethau gyda'r math swigen. Felly, gadewch i ni ystyried nawr pa mor dda neu swigen drwg fath mewn gwirionedd oedd, ac yn ceisio i roi geirfa ein hunain gyda sydd i algorithmau beirniadaeth fel hyn, ac yn fuan ein hunain. Felly, y pas cyntaf trwy didoli swigen, y tro cyntaf Cerddais o'r chwith i'r dde ar draws y llwyfan, cymerodd fi n minws 1 cymariaethau. Ac mae hynny'n mynd i fod fy uned o fesur, dde? Roeddwn yn fath o siarad a mynd am dro, braidd yn gyflym, braidd yn araf, felly cyfri fy nifer o eiliadau Nid yw dweud yn arbennig, ond yn cyfrif faint o gweithrediadau a wneuthum ar ddydd Llun, cymharu dau o bobl, sy'n teimlo'n fel uned neis o fesur. Felly minws n 1 gamau y tro cyntaf, ond wedyn yr hyn a ddigwyddodd ar ôl hynny? Beth yw'r un upside o un tocyn drwy restr fel arall heb eu didoli? Beth allwch chi ei ddweud wrthyf am yr elfen a oedd yr holl ffordd dros yno? Yeah? Dyna oedd yr elfen fwyaf, dde? Rhif wyth, er ei bod ddechrau yma, bob tro rwy'n cymharu ei herbyn cymydog, mae hi'n cadw byrlymu i fyny ar y dde ochr y rhestr. Ac yn wir, dyna lle yr algorithm yn cael ei enw. Yn awr gan hynny rhesymeg, faint o gymariaethau mae angen imi eu gwneud ar yr ail dro Yr wyf yn gwneud y pas o'r chwith i'r dde? n minws 2, dde? Byddai 'I jyst yn gwastraffu fy amser os byddaf cadw cymharu wyth yn erbyn rhywun arall oherwydd ein bod eisoes yn gwybod ei bod yn y lle iawn. Felly dyna dipyn o optimeiddio, felly mae'r tocyn nesaf yn mynd i fod plws n minws ddau gam, lle mae n yw nifer y bobl. Nawr gallwch chi fath o allosod, hyd yn oed os nad ydych yn wyddonydd cyfrifiadurol, sut mae hyn yn dod i ben. Ar ddiwedd y algorithm hwn, yn ôl pob tebyg gennych dim ond un gymhariaeth chwith. Mae'n rhaid i chi fath o osod y gan ddechrau o'r rhestr rhag ofn dau ac un yn allan o drefn a dylai fod yn un a dau, felly mae hyn gwaelodion allan yn y ac 1 cymhariaeth terfynol. Nawr bod y dot, dot, dot math o donnau 'i' dwylo ar rai o'r manylion juicier, ond gadewch i ni jyst mynd yn ei flaen a symleiddio. Os cofiwch o uchel ysgol, a dweud y gwir, mae llawer ohonoch Roedd llyfrau mathemateg a oedd taflen twyllo ychydig ar y clawr blaen neu ar y clawr cefn a oedd yn dangos i chi pa gyfres crynodebau yn hoffi mae hyn yn y pen draw ychwanegu hyd at. Yn yr achos gyffredinol, os oes gennych amrywiol fel n, ac yn wir yr un yma, os ydych yn edrych ar eich Llyfr mathemateg hen ysgol, byddech yn gweld bod hyn yn mewn gwirionedd yn ychwanegu hyd at swm hwn yma, n amserau minws n 1 wedi'i rannu gyfan erbyn 2. Felly, am y tro, gadewch i mi jyst nodi mae hyn yn wir, y blaen naid o ffydd, dyna beth mae hyn yn crynhoi hyd at, a gallem brofi bod mewn achos mwy cyffredinol. Ond yn awr gadewch i ni ehangu hyn allan. Felly, gadewch i ni yn lluosi hyn allan, felly dyna n sgwâr, minws n, pob rannu â 2. Mae hynny'n wir yn sgwâr n, wedi'i rannu â 2, minws n dros 2, felly dyna i gyd 'n glws a diddorol. Ond beth sy'n digwydd os ydym yn Erbyn hyn plug-in werth? Tybiwch Nid oedd gan wyth wyf bobl, ond yn dweud miliwn. A miliwn dim ond oherwydd mae'n nifer eithaf mawr, gadewch i dopio bod i mewn a gweld beth sy'n digwydd. Felly, os wyf yn plwg miliwn i mewn i'r fformiwla Rydw i'n mynd i gael miliwn sgwâr, wedi'i rannu â 2, minws a miliwn, wedi'i rannu â 2. Yn awr beth sy'n mynd i fod yn gyfartal? Felly 500,000,000,000, minws 500,000. Ac os wyf yn ei wneud mewn gwirionedd y cwestiwn allan, mae hynny'n ei olygu bod didoli miliwn pobl sydd â'r math swigen Gallai mynd â fi 499,999,500,000 grisiau neu gymariaethau yn y diwedd, ni jyst yn allosod. Sy'n teimlo'n eithaf araf, ond dweud y gwir un mesur mewnbwn penodol fel hyn, nid yw pob dweud hynny. Ond yn wir, mae'n awgrymu bod yn n mynd yn fwy ac yn fwy, algorithm hwn math o teimlo'n waeth ac yn waeth, neu os ydych yn wir yn dechrau teimlo'r boen o hynny exponentiation, hynny n sgwario, sy'n ychwanegu i fyny 'n bert gyflym. Ac nid yw manylion hyn yn colli ar bobl, mewn gwirionedd rai blynyddoedd yn ôl seneddwr penodol a oedd ymgyrchu, eistedd i lawr am gyfweliad gyda Google Eric Schmidt, Prif Swyddog Gweithredol ar y pryd, ac yn ei herio gyda chwestiwn yn debyg ein bod yn archwilio heddiw. Gadewch i ni edrych. [VIDEO Playback] -Senator, Byddwch yma yn Google, ac yr wyf yn hoffi i feddwl am y llywyddiaeth fel cyfweliad am swydd. Yn awr, mae'n anodd i gael swydd fel llywydd, a ydych yn mynd trwy'r llymder yn awr. Mae hefyd yn anodd i gael swydd yn Google. Mae gennym gwestiynau, ac yr ydym gofyn i'n cwestiynau i ymgeiswyr, ac mae hyn yn un yn dod o Larry Schwimmer. What-- chi guys yn meddwl fy mod kidding, 'i' iawn yma. Beth yw'r ffordd fwyaf effeithlon i didoli miliwn o gyfanrifau 32-bit? -Well-- -I'm Ddrwg gennym, maybe-- -Dim, Na, na. Rwy'n meddwl bod y math swigen fyddai'r ffordd anghywir i fynd. -Come Ar, a ddywedodd wrtho hyn? Doeddwn i ddim yn gweld cyfrifiadur gwyddoniaeth yn eich cefndir. -We've Cael ein ysbiwyr i mewn 'na. -OK, Gadewch i ni ofyn i wahanol cwestiwn cyfweliad. [DIWEDD Playback VIDEO] SIARADWR: Felly, yn siarad am rhifau penodol, fodd bynnag, Nid yn mynd i fod bob un sy'n ddefnyddiol. Nid yw'n gwers bywyd y swigen didoli, o ystyried miliwn mewnbynnau, Gallai cymryd cymaint â 500,000,000,000 grisiau. Ni allwch wir yn gyffredinoli rhy effeithiol o hynny a gwneud penderfyniadau dylunio da wrth ysgrifennu rhaglenni. Felly gadewch i ni ganolbwyntio er ar sut efallai y byddwn yn symleiddio'r canlyniad hwn. Felly dwi wedi hamlygu mewn melyn yma ganlyniad n sgwâr rhannu â 2, felly i filiwn sgwario wedi'i rannu â 2, ac yna Rwyf wedi tynnu sylw at yr hyn yr ateb yn y pen draw yn ar ôl i ni dynnu i ffwrdd wedi'i rannu n erbyn 2. A'r hawliad Rydw i'n mynd i wneud yn awr yw, pwy mae'r Heck gofalu os ydych yn tynnu i ffwrdd ychydig yn hen n dros 2 pan fydd y cyntaf rhan o'r fformiwla hwn mor llawer mwy? Mae'n dominyddu y llall dymor, n sgwario wedi'i rannu â 2 mor llawer mwy, yn amlwg, fel y n yn cael fawr fel miliwn, sydd yno mewn gwirionedd gwahaniaeth mawr yn diwedd y dydd rhwng 500,000,000,000 a 499,999,500,000? Ddim mewn gwirionedd. Ac felly yr hyn rydym yn mynd i wneud fel gwyddonwyr cyfrifiadurol yn telerau anwybyddu gorchymyn is hynny a cymryd rhywbeth fel hyn ac yn wir jyst symleiddio i'r dymor sy'n mynd i mater. Y mwyaf fydd ein setiau data yn cael, y mwyaf fydd ein cronfeydd data yn cael, y tudalennau mwy gwe mae'n rhaid i ni chwilio, y mwyaf ffrindiau sydd gennych ar Facebook. Wrth n mynd yn fwy, rydym yn wirioneddol mynd i ofalu am y mwyaf dymor mewn unrhyw ddadansoddiad o'r fath o ein perfformiad algorithmau. Ac yr wyf i'n mynd i ddweud, eich bod yn gwybod beth, didoli swigen ar y drefn O fawr, ar y drefn n sgwâr. Dyw hi ddim yn union n sgwario fel yr ydym wedi gweld, ond sydd yn poeni amdanynt am delerau llai hynny, a dweud y gwir, sydd wir gofalu os ydym yn ei rannu â 2? Dyna dim ond yn ffactor cyson. Ac mae'n 500,000,000,000 erbyn 250 biliwn iawn bod fawr o gytundeb? Gallai Fi jyst aros un flwyddyn, gadael i fy ngliniadur llythrennol mynd ddwywaith mor gyflym mewn caledwedd, a'r math yna o wahaniaeth yn unig yn mynd i ffwrdd yn naturiol dros amser. Yr hyn yr ydym yn gofalu amdano yw yr ymadrodd, mae'r rhan o'r mynegiad sy'n mynd i amrywio fel ein mewnbwn yn mynd yn fwy ac yn fwy. Ac yn wir, yn y byd go iawn, dyna beth sy'n digwydd yn gynyddol yw'r mewnbynnau i'n problemau a algorithmau yn mynd yn fwy. Felly O mawr yn mynd i fod y nodiant, y nodiant asymptotic, yr ydym newydd ei defnyddio fel gwyddonwyr cyfrifiadurol i ddisgrifio y perfformiad, neu yr amser yn rhedeg, o'r algorithm. Er mwyn i ni allu cymharu algorithmau ar wahanol gyfrifiaduron ysgrifenedig gan wahanol bobl, trwy ddefnyddio rhywfaint o metrig yn sylfaenol debyg fel y nifer o gymariaethau ydych yn gwneud, neu efallai y nifer o gyfnewidiadau eich bod yn gwneud. Yr hyn nad ydym yn mynd i cyfrif yw faint o amser sy'n mynd ar y cloc ar y wal fel arfer. Yr hyn nad ydym yn mynd i boeni amdano yw faint o gof ydych chi'n defnyddio heddiw yn lleiaf, er bod hynny'n adnodd arall efallai y byddwn yn mesur. Rydym yn mynd i geisio seilio ein dadansoddiadau ar ddim ond y gweithrediadau sylfaenol, y rhai, a dweud y gwir, y gallwch ei weld fwyaf ar eu golwg. Felly, gyda rhywbeth fel O mawr o n sgwâr, yr wyf yn honni bod O o n squared yw yn rhwym uchaf ar y hyn a elwir yn rhedeg amser o'r math swigen. Mewn geiriau eraill, os ydych yn eisiau honni bod yna y terfyn uchaf ar faint o camau y gallai algorithm cymryd, mae'n mynd i fod yn y O fawr o n sgwâr yn yr achos hwn, yn uchaf rhwymo. Beth os byddaf yn lle hynny yn newid y stori i fod nid am fath swigen, ond am hyn rhwymo uchaf. Allwch chi feddwl am algorithm ein bod wedi edrych ar yn barod y mae ei uchaf rhwymo, uchafswm mesur o amser neu weithrediadau, Byddai fod yn dweud i gael ei ffinio gan n, swyddogaeth llinol, nid yn un cwadratig sy'n crwm? Beth yw algorithm sy'n bob amser yn cymryd dim mwy nag fel grisiau n, neu Camau 2n, neu gamau 3n? Yeah? CYNULLEIDFA: Dod o hyd i'r nifer mwyaf mewn rhestr? SIARADWR: Perffaith, dod o hyd i y nifer mwyaf mewn rhestr. Os ydw i'n cael rhestr o pobl er enghraifft, pob un sydd yn cynnal nifer, beth yw'r nifer fwyaf o'r camau y dylid ei gymryd i mi, person rhesymol smart, i ddod o hyd i'r person mwyaf yn y rhestr honno? n, dde? Oherwydd yn yr achos gwaethaf, lle efallai y bydd y gwerth mwyaf fod? Iawn, yr holl ffordd ar y diwedd. Felly, yn yr achos gwaethaf uchaf rhwymo, yr wyf efallai rhaid i chi fynd yr holl ffordd dros yma ac yn cael ei hoffi, oh, dyma rhif wyth, neu beth bynnag y gwerth. Nawr byddai'n jyst yn dwp os wyf yn cadw fynd, dde? Chwilio am fwy a mwy o elfennau os yr olaf ohonynt yw dros yno? Felly yn sicr, n yn uwch yn rhwymo. Nid oes angen i mi gymryd mwy o gamau na hynny. Felly beth os yn lle hynny yr wyf yn cynnig bod mae algorithmau yn y byd hwn sy'n cael amser rhedeg dyna ffinio gan O fawr o log n, mewngofnodwch n? Ble yr ydym wedi gweld hyn o'r blaen? Yeah? CYNULLEIDFA: Yn y broblem llyfr ffôn? SIARADWR: Fel y broblem llyfr ffôn. Beth oedd y mesur o ba mor llawer o amser neu faint o ddagrau y mae'n cymerodd fi i ddod o hyd i rywun fel Mike Smith yn y llyfr ffôn? Rydym yn honni ei fod yn log n, ac hyd yn oed os yw'n anghyfarwydd, neu ei fod yn ychydig yn niwlog beth yw logarithm neu ddehonglwr oedd, dim ond cofiwch y log n yn gyffredinol yn cyfeirio at y broses, yn yr achos hwn, o rannu rhywbeth yn ei hanner eto, ac unwaith eto, ac unwaith eto, ac unwaith eto, fel ei fod yn mynd yn fwyfwy bach wrth i chi wneud hynny. Felly log o n yn cyfeirio, yn sicr, at yr enghraifft llyfr ffôn, i chwilio deuaidd mewn theori, pan fyddwn yn Roedd y drysau rhithwir ar y bwrdd, neu pan oedd Sean chwilio am rywbeth. Pe bai wedi defnyddio chwiliad deuaidd, mewngofnodwch n fyddai uchaf rhwymo ar faint amser sy'n cymryd. Ond algorithmau rhai a oedd yn rhedeg yn log n cymryd yn ganiataol pa manylion allweddol? Bod y rhestr ei datrys, dde? Mae eich algorithm yn anghywir os nad yw eich cyfraniad yn cael ei ddidoli, ac eto yr ydych yn ei ddefnyddio rhywbeth fel chwiliad deuaidd oherwydd efallai y byddwch yn neidio i'r dde dros yr elfen heb sylweddoli ei fod yn wir yno. Yn awr beth allai hyn ei olygu, O fawr o un? Nid yw hyn yn golygu bod eich algorithm yn cymryd un a dim ond un cam, 'i jyst yn golygu ei bod yn cymryd nifer cyson o gamau. Efallai ei fod yn 1, efallai ei bod yn 10, efallai ei bod yn 1,000, ond mae'n annibynnol ar maint y broblem. Ni waeth pa mor fawr yw n, algorithm amser cyson bob amser yn cymryd yr un nifer o gamau. Felly, yr hyn a allai fod yn algorithm rydym wedi trafod neu dim ond reddfol sy'n dod i chi fod bob amser yn rhedeg yn hyn a elwir yn amser yn gyson? Yeah? CYNULLEIDFA: Ychwanegu dau rif. SIARADWR: Ychwanegwch ddau rif, 2 a 2 yn dychwelyd 4, wneud. Felly, a allai weithio, beth arall? Beth am y byd yn fwy real, ie? CYNULLEIDFA: Dod o hyd i'r peth cyntaf mewn rhestr. SIARADWR: Dod o hyd i'r cyntaf elfen mewn rhestr, yn sicr. Rydym wedi bod yn siarad mewn gwirionedd am araeau eisoes, sut yr ydych yn ei gael yn y elfen gyntaf mewn arae, ni waeth pa mor hir y mae'r amrywiaeth mewn cod C? Yr ydych newydd ei ddefnyddio fel y braced sero nodiant, bam, rydych chi yno. Ac yn wir araeau, wrth fynd heibio, cefnogi rhywbeth a elwir yn gyffredinol fel mynediad ar hap, mynediad ar hap cof, oherwydd gallwch llythrennol neidio i unrhyw un lle. Gallwn wneud hyn hyd yn oed yn fwy syml gallwn ni ailddirwyn i wythnos sero pan wnaethom Scratch. Faint o amser gymerodd hi i'r ddweud bloc yn Scratch i weithredu? Dim ond amser yn gyson, dde? Dweud rhywbeth, yn dweud rhywbeth, nid oes gwahaniaeth sut Crafiadau mawr y byd yw, mae bob amser mynd i gymryd yr un faint o amser i wneud dim ond dweud rhywbeth. Felly dyna amser cyson, ond beth yw'r ochr arall? Os oedd hynny'n uchaf ffiniau, beth os ydym am i ddisgrifio'r arffiniau isaf o'n algorithmau amser yn rhedeg? Mae bron i achos gorau o bosibl, os mynnwch, er y gallai telerau hyn yn berthnasol i gorau achosion, achosion gwaethaf, achosion gyfartaledd yn fwy yn gyffredinol, ond gadewch i ni dim ond yn canolbwyntio ar arffiniau isaf yn fwy cyffredinol. Beth yw algorithm sydd wedi mae is rhwymo o gamau n, neu gamau 2n, neu gamau 3n? Rhyw ffactor o risiau n, dyna ei is rhwymo. Yeah? CYNULLEIDFA: didoli Bubble? SIARADWR: didoli Bubble cymryd chi grisiau n leiaf, pam? Pam hynny? Pam y dylai y dechrau i ddod i chi reddfol, dim hyd yn oed os bydd yn gwneud dim ond eto? Yeah? CYNULLEIDFA: [Anghlywadwy]. SIARADWR: Yn union. Yn y senario gorau posibl o didoli swigen, ac mae llawer o algorithmau, os wyf yn llaw ydych wyth o bobl sydd eisoes yn cael eu datrys, byddai'n ffôl i chi, y algorithm, i fynd yn ôl ac ymlaen fwy nag unwaith, dde? Oherwydd cyn gynted ag y byddwch yn cerdded drwy'r rhestr unwaith, dylech sylweddoli, oh, yr wyf yn gwneud unrhyw cyfnewidiadau, y rhestr hon yn cael ei datrys, allanfa. Ond mae hynny'n mynd i fynd â chi n grisiau. Ac i'r gwrthwyneb, beth arall ffordd o feddwl am y peth? Fath swigen yn omega, fel petai, o n, oherwydd os edrychwch ar llai na n elfen, beth yw'r mater sylfaenol yno? Nid ydych yn gwybod os yw'n cael ei datrys, ar y dde. Rydym bodau dynol cipolwg nerth mewn wyth bobl ac yn cael ei hoffi, oh, mae'n cael ei datrys, nad oedd yn mynd â fi n grisiau, ond yr oedd. Eich llygaid, er eich math o mae ganddynt faes mawr o weledigaeth, chi edrych ar wyth elfen, chi edrych ar wyth o bobl, dyna wyth cam yn effeithiol. A dim ond os ydw i'n cerdded drwy'r cyfan rhestr ydw i'n sylweddoli, ie, didoli. Os byddaf yn rhoi'r gorau i hanner ffordd i feddwl, i gyd iawn, mae'n eithaf didoli hyd yn hyn, beth yw'r groes nid yw'n cael ei datrys? Nid yw algorithmau mynd i fod yn gywir. A allai fod yn gyflymach, ond yn anghywir. Felly nawr mae gennym ffordd o disgrifio is terfynau, a beth am amser yn gyson? Beth yw algorithm sydd â llai rhwymo ar ei amser yn rhedeg o un? Cam 1, 2 cam, 10 cam, ond gyson, yn annibynnol ar n, maint y mewnbwn? Yeah, yn y cefn. CYNULLEIDFA: printf? SIARADWR: Beth sy'n bod? CYNULLEIDFA: printf? SIARADWR: printf. OK, yn sicr. Felly, mae'n cymryd nifer penodol o gamau. A ddylwn i now-- nawr bod rydym yn sôn am cod C ac nid Scratch, rhywbeth fel dweud, gyda printf, dylem ddechrau i fynd yn ofalus. Oherwydd bod printf yn cymryd mewnbwn, mae'n llinyn, a llinynnau dechnegol oes ganddynt hyd. Felly os ydym yn awr yn awyddus i godi arnoch chi, os nad oes gwahaniaeth gennych, dechnegol gallem ddadlau bod printf yn cymryd mewnbwn hyd newidiol, ac yn sicr gallai gymryd mwy amser i argraffu llinyn hwn yn hir, na hyn hir. Felly beth os ydym yn ystyried dim ond y didoli a chwilio enghreifftiau? Beth am Mike Smith yn y ffôn lyfr, neu chwiliad deuaidd yn fwy cyffredinol? Yn yr achos gorau, beth allai ddigwydd? Yr wyf yn agor y llyfr ffôn ac, bam, mae rhif Mike Smith. Gallaf ei alw ef yn syth. Cymerodd un cam, efallai dau gam, ond mae nifer cyson o gamau os wyf got 'n ffodus. Ac yn dweud y gwir, gwelsom ar Dydd Llun eich classmate gael yn eithaf lwcus ddwywaith yn olynol. A dyna oedd yn wir gyson amser mewn is terfynau ar y algorithm dan sylw ar gyfer dod o hyd i y rhif 50 y tu ôl y rhai ar gau drysau. Yn awr, wrth fynd heibio, os byddwch yn darganfod bod y ddau O fawr, mae'r rhwymo uchaf, ac omega, yr isaf rhwymo, yn un yn yr un, bod yr un fformiwla yn cromfachau, gallwch hefyd yn dweud, dim ond i fod yn ffansi, bod rhywbeth yn theta o n neu theta o ryw werth arall. Mae hynny yn unig yn golygu pan fydd fawr O a omega yr un fath. Nawr beth am fath dethol? Gadewch i ni ddefnyddio hyn geirfa newydd. Yn y math dethol, beth oedd yr ydym wneud eto, ac unwaith eto, ac unwaith eto? Yr oeddwn yn mynd yn ôl ac ymlaen trwy y rhestr, yn chwilio am bwy? Y nifer lleiaf. Felly faint o gamau, sut llawer o gymariaethau wnes i rhaid iddynt eu gwneud er mwyn chyfrif i maes pwy yr elfen lleiaf yn y rhestr oedd? n minws 1, dde? Oherwydd os Fi jyst ddechrau gyda'r un rwy'n roddwyd a byddaf yn dechrau cymharu ef neu hi, Yna, ef neu hi, ef neu hi, ef neu hi, yr wyf yn dim ond paru elfennau ynghyd n minws 1 o weithiau. Felly detholiad didoli un modd yn cymryd n minws 1 gamau y tro cyntaf. Faint o gamau y mae'n cymryd i mi ddod o hyd i'r elfen ail leiaf? n minws 2, oherwydd fy mod i'n bod yn fud os Rwy'n cadw edrych ar yr un bobl eto os wyf eisoes wedi dewis iddo neu hi ac yn eu rhoi yn eu lle. A'r trydydd cam, n minws 3, yna minws n 4. Rydym wedi gweld y patrwm hwn o'r blaen, ac yn wir detholiad didoli yn yr un modd Mae gan uchaf rhwymo o n sgwâr os ydym yn ei wneud i fyny y Crynodeb. Beth yw ei, didoli dewis is rhwymo? Cyn lleied â phosibl, faint o amser dethol rhaid didoli cymryd, wrth i ni ddiffinio ar ddydd Llun? Cynnig ddau opsiwn. Efallai ei bod yn n, fel o'r blaen. Efallai ei fod yn n sgwâr, gan ei fod yn yn awr gan fod y rhwymo uchaf. CYNULLEIDFA: n sgwâr. SIARADWR: n sgwâr. Pam? CYNULLEIDFA: Oherwydd bod gennych i ddiffinio [Anghlywadwy]. SIARADWR: Yn union. O leiaf gan fy mod diffinnir fath dethol roedd yn eithaf naïf, ddal ati, ddod o hyd i'r elfen lleiaf. Ewch eto, dod o hyd i'r elfen lleiaf. Ewch eto, dod o hyd i'r elfen lleiaf. Does dim fath o optimization yno fod Efallai gadewch i mi erthylu ar ôl camau yn unig n neu hynny. Felly yn wir, dewis didoli, omega o n sgwâr. Beth am fath mewnosod, lle yr wyf yn cymryd pwy a roddwyd i mi, ac yna yr wyf plopped ef neu hi yn y lle iawn? Yna mi ymlaen at yr ail berson, plopped ef neu hi yn y lle iawn. Yna bydd y person nesaf, plopped ef neu hi yn y lle iawn. Sylwch fod hyn yn iawn llinol, fel petai. Rwy'n llinell syth, rwy'n ddim yn mynd yn ôl ac ymlaen, Dydw i erioed wedi edrych yn ôl mewn gwirionedd, ond beth sy'n digwydd pan fyddaf yn mewnosod ef neu hi i ddechrau y rhestr fel y gwnaethom ar ddydd Llun? Beth sy'n digwydd? Yeah? CYNULLEIDFA: [Anghlywadwy]. SIARADWR: Yeah, mae hynny'n Roedd y ddalfa, dde? Efallai y byddwch yn cofio o eich cyd-ddisgyblion, os ydynt yn yn gwneud unrhyw symudiad gyda eu traed, a oedd llawdriniaeth. Felly, pe byddai tri o bobl yma ac y person newydd yn perthyn ffordd dros yno, ar lwyfan hir fel hyn, yn sicr, fe neu gallai hi dim ond yn mynd i'r diwedd un. Ond os ydym yn meddwl am cyfrifiadur ac amrywiaeth o gof, bobl hyn yn mynd i gael i siffrwd dros i wneud lle ar gyfer y person hwnnw. Ac felly bod minws n 1 shufflings, n minws 2 shufflings, n shufflings minws 3 yn unig fath o digwydd tu ôl i mi, nid o fy mlaen fel o'r blaen, mewn rhyw ystyr. Yn awr wrth fynd heibio, ac fel y Efallai eich bod wedi gweld ar-lein os byddwch yn dechrau procio o gwmpas am math, mae cymaint o rai gwahanol allan yna, rhai ohonynt yn well nag eraill. Yn wir, bogosort yn un dyna fath o hwyl i edrych i fyny. Bogosort cymryd set o rhifau neu ddweud dec o gardiau, ar hap shuffles hwy, a gwirio os ydynt yn didoli. Ac os nad yw, mae'n ei eto. Ac os nad yw, mae'n ei eto. Os nad yw, mae'n ei eto. Yn anhygoel dwp. Ac yn wir, os ydych yn darllen fel erthygl Wicipedia, ei lysenw yn fath dwp. Yn y pen draw bydd yn gweithio, gobeithio, yn cael digon o amser, ond faint o amser Gallai gymryd cryn dipyn o amser. Felly, pe gallwn, gadewch i cyflymder pethau i fyny o enghraifft Mary Beth yn gynharach, drwy gael ychydig mwy o elfennau, ond dau proseswyr mwy. Mae dau o bobl, os ydych yn Ni fyddai ots ymuno â mi. Beth am 1 dros yma, ac gadewch i ni go-- oes neb dros yno? Nid oes unrhyw un dros yno? OK. Chi gyda'r du shirt, ie, dewch draw. Mae pob hawl, beth yw eich enw? CYNULLEIDFA: Peter. SIARADWR: Beth sy'n bod? CYNULLEIDFA: Peter. SIARADWR: Peter, David, neis i gwrdd â chi. Mae pob hawl, rydym wedi Pedr fan hyn, os ydych yn eisiau dod ar y bwrdd dros yma. A beth yw eich enw? CYNULLEIDFA: Elena. SIARADWR: Elena. OK, neis i gwrdd â chi. Elena yn cyfarfod Peter. Pedr, Elena. A bydd angen i ni Andrew hyd yma hefyd, os gwelwch yn dda. Ac mae eich her yn mynd i fod i ddatrys dec o gardiau. Ac os anghyfarwydd, dec Dylai o gardiau yn y pen draw eu didoli bach rhywbeth fel hyn lle y byddwn ni'n gwneud y clybiau, ac yna y rhawiau, yna bydd y calonnau a diamonds, o ace fel un, holl ffordd i fyny at frenin. Mae'r cardiau Rydw i'n mynd i roi i chi yn mynd i fod yn 52 mewn nifer. Rydym yn mynd i yn yr un modd amser i chi, mewn dim ond eiliad. Rydym yn mynd i daflu Andrew fyny ar y sgrin yma, er i wylio wrth i chi wneud hyn. Ac fel bod yr holl o hyn yn oed yn fwy gweladwy, mae'r rhain yn y cardiau Cawn ar Amazon. Fel eu bod yn barod ar hap didoli, ac rydym yn mynd i amser i chi. Ac rydym yn mynd i gadw'n go iawn y tro hwn, felly rydym yn mynd i geisio pwysau arnoch oherwydd fel arall y bydd hyn yn mynd yn ddiflas yn gyflym. Pe gallech fynd ymlaen i ddidoli 52 elfennau at ei gilydd trwy ryw fodd, yn awr. Ac eto, wrth i ni wylio'r rhain guys gwneud yr hyn, yn y pen draw yn mynd i gynhyrchu amlwg canlyniad, meddyliwch am 'n sylweddol sut y maent yn pob un yn ei wneud, sut y gallech ddisgrifio. Oherwydd unwaith eto, mae'r rhain yn holl brosesau, algorithmau ein bod yn eu cymryd yn ganiataol fel dynol. Ond eich bod wedi yn ôl pob tebyg o amser wedi cael greddf, ymhell cyn i chi hyd yn oed yn yn meddwl am gymryd gwyddoniaeth gyfrifiadurol dosbarth chi efallai wedi cael y reddf gyda i ddatrys problemau fel hyn. Ond unwaith y byddwch yn adnabod patrymau a dechrau i ffurfioli y camau â nhw eich bod yn datrys y problemau hyn, fe welwch y gallwch ddatrys llawer yn fwy diddorol ac yn llawer mwy cymhleth problemau yn gyflym. Felly rhywun o'r gynulleidfa, yr hyn sy'n o leiaf un elfen o'r algorithm eu bod yn defnyddio yma? CYNULLEIDFA: [Anghlywadwy] SIARADWR: Beth sy'n bod? CYNULLEIDFA: Drwy siwt. SIARADWR: Drwy siwt. Felly, cyntaf y byddant yn cael eu clystyru pob un o'r deiamwntiau ei gilydd mae'n ymddangos, pob un o'r calonnau at ei gilydd mae'n ymddangos, ac yn y blaen, heb barch ar gyfer y niferoedd ar y cardiau. Ac yn awr y maent yn ymddangos, er enghraifft, i gael eu didoli yn ôl rhif. Da iawn. Mae pob hawl, felly beth sy'n mynd i fydd y cam olaf, yna yma? Unwaith y mae gennym bedwar siwtiau ddidoli, beth y mae angen inni ei wneud at y pedwar pentyrrau er mwyn cyflawni un didoli dec, yn syml? Felly mae angen i uno â hwy eto. Felly mae 'na syniad diddorol sy'n unwaith eto, mentraf ddweud, yn reddfol iawn hyd yn oed os gallai ydych erioed wedi taro y math hwnnw o label arno. Mae hyn yn syniad sylfaenol o rannu y broblem nid yn ei hanner y cyfnod hwn, ond o leiaf yn bedwar darn. Datrys 'n bert lawer problemau sylfaenol union yr un fath ar wahân i'w gilydd, ac wedyn gyfuno'r canlyniadau. Ac, rhagorol, wneud. Mae pob hawl, rownd mawr o gymeradwyaeth, pe gallem. [Cymeradwyaeth] SIARADWR: Nid oes gennyf unrhyw syniad beth wnewch chi helpu wneud â'r rhain, ond dyma i chi fynd. Ddiolch 'ch ogystal. Felly, gadewch i ni weld, dwy funud ac wyth eiliad, os hoffech i herio eich ffrindiau. Beth felly yn mynd i fod yn cymryd i ffwrdd oddi wrth hyn y gallwn trosoledd yn fwy cyffredinol? Wel, yn meddwl yn ôl i amrywiaeth hwn o rifau, a meddwl yn ôl yn awr at rai o'r pseudocode rydym wedi ysgrifennu yn y gorffennol, a dyma oedd y pseudocode ar gyfer datrys y broblem llyfr ffôn. Lle mewn pseudocode wyf wedi'u rhifo ffordd fwy trefnus o ddisgrifio sut fe wnes i 'n athrylithgar iawn algorithm dynol o rannu'r ffôn llyfr yn ei hanner, ailadrodd, ailadrodd, ailadrodd, nes i mi ddod o hyd i rywun fel Mike Smith, os yw'n wir yn y llyfr ffôn. Ond yr wyf yn fath o defnyddio beth 'n annhymerus' galw dull ailadroddol iawn yma, yn rhybudd enwedig llinell 8 a llinell 11. Mae'r rhai yn dystiolaeth o ailadroddol dull, dull dolennu, oherwydd dyna'n union yr ymddygiad y maent yn achosi. Llinellau hynny yn dweud ewch i llinell tri, a gallwch math o feddwl am hynny yn eich llygad meddwl fel bod yn ddolen. Mae'n dweud wrthych i fynd yn ôl i fyny i gam tri ac ailadrodd, unwaith eto, ac unwaith eto, ac unwaith eto. Ond beth os ydym trosoledd syniad allweddol yma inni wneud nad oedd y tro diwethaf, a symleiddio llinell 8 a llinell 11 ac mae eu cymdogion fel dim ond hyn, mewn melyn. Dyw hi ddim yn byrhau sylfaenol y pseudocode yn fawr iawn, ond mae'n newid yn sylfaenol natur fy algorithm. Yr hyn rydw i'n awr yn dweud yng ngham 7, yng ngham 10, yw chwilio am Mike yn yr un ffordd union, ond dim ond yn y chwith hanner neu yn hanner cywir. Felly, mewn geiriau eraill, os Yr wyf yn dechrau o'r cam un, godi llyfr ffôn, yn agored i ganol o'r llyfr ffôn, yn edrych ar enwau, os Smith ymhlith enw i, ffoniwch Mike, arall os Smith yn gynharach yn y llyfr, cam saith chwilio am Mike mewn chwith hanner y llyfr. Ond yn y math hwnnw o yn teimlo fel mae'n gadael i mi hongian, dde? Mewn melyn, yn cyfarwyddyd, ond sut ydw i'n chwilio am Mike yn y chwith hanner y llyfr ffôn? Ble ydw i'n cael algorithm ag yr wyf Gall chwilio am rywun fel Mike Smith? Wel, mae'n ein syllu yn wyneb. Gallaf llythrennol ddefnyddio'r union un fath rhaglen yn effeithiol yn mynd i fyny i ben unwaith eto ac ail-redeg yr un llinellau o god. Felly hyd yn oed er y dylai hyn deimlo fel tipyn o ddiffiniad cylchol ble rydych yn ateb rhywun yn gwestiwn gan jyst fath o ofyn yr un cwestiwn eto, fel pam, pam, pam? Y gwir amdani yw oherwydd ein bod wedi codio galed un neu ddau o linellau arbennig, cam 4, sy'n os, ac yn cam 12, a oedd yn yn effeithiol gangen arall, oherwydd bod gennym fesurau rhywbeth dros dro y rhai, Bydd algorithm hwn yn dod i ben os ydym dod o hyd i Mike, neu os nad ydym yn ei wneud. Ond yng ngham 7 a 10 erbyn hyn, rydym wedi yr hyn y byddwn yn ei alw'n algorithm dychweliadol. Ac recursion yn wir yn syniad pwerus mae hynny'n ychydig o feddwl blygu ar y dechrau, y gallwn yn awr wneud cais fel a ganlyn. Uno fath fydd y math olaf y rydym yn edrych ar, o leiaf yn y dosbarth yn ffurfiol. Ac mae'n sylfaenol wahanol o dair olaf hynny, ac yn sicr pedwar olaf os ydym yn cynnwys bogosort. Dyma y pseudocode ar gyfer math uno. Pan ar fewnbwn o elfennau n, o ystyried mor amrywiaeth o faint n, os yw n yn llai na 2, dychwelyd. Felly pam ydw i'n cael y sanity wirio yn gyntaf? Beth yw'r goblygiadau os wyf yn llaw ydych amrywiaeth y mae ei hyd n yn llai na 2? Mae eisoes wedi eu didoli, yn amlwg, dde? Oherwydd bod y rhestr naill ai wedi un elfen, sef trivially didoli am ei fod yn yr unig beth yno. Neu, 'i' o faint sero sy'n golygu does dim byd i ddidoli, hynny gan natur mae'n cael ei datrys. Does dim ond dim o'i le yno. Felly dyna ein achos sylfaenol fel y'u gelwir. Mae hynny'n debyg o ran ysbryd i'r hyn a wnaethom gyda Mike. Os yw Mike yn y llyfr ffôn, ei alw ef. Os nad yw ei fod yno, rhoi'r gorau iddi. Mae'n achos sylfaenol fel y'i gelwir, i wneud yn siŵr algorithm hwn ar ddiwedd y dydd yn dod i ben mewn rhai amgylchiadau. Ond dyma y naid ffydd yn awr, arall, didoli'r hanner chwith y elfennau, Yna datrys y dde hanner o'r elfennau, ac yna cyfuno'r haneri didoli. A dyma lle mae'n teimlo fel rydym yn wrthod wynebu. Rwyf wedi gofyn i chi i roi trefn ar n elfennau, ac rwy'n gan ddywedyd, OK, peidiwch iddo drwy ddidoli y chwith a didoli y dde. Ond yr wyf yn dweud un beth arall, ac mae hyn yn yw'r thema allweddol mae'n ymddangos yn y greddf hyd yn hyn, mae y trydydd cam o uno. Sydd er ei fod yn ymddangos mor fud yn yr ysbryd, fel dim ond uno pethau at ei gilydd, mae'n ymddangos i fod yn gam allweddol tuag at y reassembly o ddwy broblem sy'n eu rhannu yn y pen draw yn ei hanner. Felly uno fath, gadewch i ni wneud hyn, os wnewch chi helpu digrifwch i mi, gydag un arddangos mwy, yn union fel y bydd gennym rai rhifau i weithio gyda. Alla i gyfnewid wyth straen peli ar gyfer wyth o bobl? Mae pob hawl, beth am i chi dri, rydych bedair yn yr adran hon, pump, chwech, a gadewch i ni yn 7, 8, yn dod ar i fyny. OK, OK yeah. Minus 8, dyna ni, ac 1. Ardderchog. Mae pob hawl yn dod ar i fyny, gadewch i ni rhoi rhifau yn gyflym. Rhif dau, rhif tri, rhif pedwar, rhif pump, chwech, saith, ac wyth. Fe wnes wyth yn gywir y tro hwn. Iawn, felly fynd yn ei flaen os gallech, ac gadewch i ddidoli yn y gorchymyn gwreiddiol a gawsom ddoe a oedd yn edrych fel hyn, os na fyddech yn meddwl. A gadewch i ni wneud hynny o flaen y tabl. Mae pob hawl, felly uno fath. Dyma lle mae'n mynd i gael math o ddiddorol, oherwydd fy mod yn ymddangos i fod yn rhoi fy hun gymaint yn llai o wybodaeth heddiw. Felly uno fath yn gyntaf oll ar fewnbwn o elfennau n, ac yn amlwg heb fod yn llai na dau, 'i' wyth, felly mae gen i ychydig mwy o waith i'w wneud. Felly nawr yn feddyliol i ni fel dosbarth yn awr yn y gangen arall, sy'n golygu tri cham. Yn gyntaf, rhaid i mi ddatrys y chwith hanner o'r elfennau. Felly sut mae mynd ati i wneud hyn? Wel, dw i'n mynd i fath o rhannu yn y pen y rhestr yma, Nid oes rhaid i chi symud yn gorfforol, ac rwy'n mynd i ganolbwyntio yn unig ar y chwith hanner o'r elfennau yma. Felly sut mae mynd ati i ddidoli restr nawr o faint pedwar? Beth yw fy algorithm? Yn gyntaf yr wyf yn gwirio yn n llai na dau, na, felly yr wyf yn symud ymlaen at y bloc arall eto. Trefnu chwith hanner yr elfennau. Felly nawr eto, yn feddyliol, a dyma lle rhaid i chi gronni llawer o hanes meddwl, os mynnwch. Nawr rwy'n didoli y chwith hanner y hanner chwith. Mae pob hawl, felly yn awr yr wyf yn galw fy un uno didoli algorithm, yn N llai na dau? Na, y mae dau, felly mae'n rhaid i mi roi trefn yr hanner chwith, a'r hanner cywir. Felly dyma ni, didoli yr hanner chwith. Pam na wnewch chi jyst gymryd un cam ymlaen. Beth yw eich enw? CYNULLEIDFA: Darren. SIARADWR: Dan. Mae Dan wedi camu ymlaen. CYNULLEIDFA: Darren. SIARADWR: Darren, a wnaed. Wnaethoch chi ei ddweud Darren neu Dan? CYNULLEIDFA: Darren. SIARADWR: Darren. OK, Darren wedi camu ymlaen ac mae bellach yn cael ei sortio. Ac mae hyn yn bron yn hawliad inane, dde? Dydw i ddim yn ymddangos mewn gwirionedd i fod yn cyflawni unrhyw beth, ond gadewch i ni symud ymlaen. Nawr, gadewch i mi ddatrys yr hawl hanner o'r elfennau. Beth yw eich enw? CYNULLEIDFA: Luke. SIARADWR: Luke. Dewch ymlaen, cam ymlaen. Done, yr wyf wedi datrys Luke. Mae'r hanner chwith bellach yn didoli a yr hanner ar hyn o bryd yn cael ei sortio, ond unwaith eto, mae yn gam allweddol yma. Beth sydd angen i mi ei wneud nesaf? Cyfuno haneri didoli. Nawr rydym yn mynd i jyst gael mae pawb yn ôl ac ymlaen yn y modd hwn, am fy mod yn fath o angen ychydig o le crafu. Mae bron fel y rhain guys yn ar fwrdd, ac mae angen rhywfaint o le i mi i symud o gwmpas ar. Felly dw i'n mynd i uno rydych guys drwy edrych ar yr hanner chwith a'r hanner cywir. A phwy amlwg yn dod yn gyntaf, Gadawodd hanner neu hanner cywir? Felly hanner i'r dde, felly gadewch i ni symud Luke dros yma i safle gwreiddiol Darren. Ac yn awr i uno eu hanner chwith i mewn, Darren yn mynd i symud yn iawn yno. Felly, yn teimlo fel bron effaith fath swigen, ond mae fy algorithm sylfaenol, wahanol iawn y tro hwn. Ond nawr yw ble mae pethau yn cael ychydig yn blino oherwydd eich rhaid i ailddirwyn feddyliol lle wnes i yn gadael i ffwrdd. Dwi newydd unodd y haneri ddidoli, sy'n golygu fy mod lle yn fy algorithm? Rhaid i mi ddatrys yr hanner dde, dde? Os ydych yn ail-ddirwyn, yn llythrennol ar y fideo, wnewch chi helpu gwelwch ein bod yn mynd â hyn pwynt Luke a Darren drwy ddidoli y chwith hanner y hanner chwith. Yna, rydym yn uno y rhai haneri ddidoli, a oedd yn yn golygu bod y cam nesaf yw fath y hanner dde o'r hanner chwith. Mae pob hawl, felly gadewch i ni gwneud hyn yn gyflymach. Mae pob hawl, chwech, dw i'n mynd i hawlio yn awr yr ydych yn cael eu didoli, dewch ymlaen. Beth yw eich enw? CYNULLEIDFA: Adriano. SIARADWR: Adriano. Adriano bellach yn cael ei sortio. A beth yw eich enw? CYNULLEIDFA: Alex. SIARADWR: Alex bellach yn cael ei sortio. Chwith hanner, hanner i'r dde, beth yw'r cam olaf? Uno. Pretty ddibwys, felly rwy'n mynd i uno mewn chwech, gymryd cam yn ôl, wyth, gymryd cam yn ôl. Ac yn awr sylwi ar hyn yn tecawê defnyddiol, yr hyn yn awr yn wir am yr hanner chwith y rhestr, heb ystyried sut yr ydym yn dechrau? Mae'n cael ei datrys. Nawr, nid yw'n cael ei datrys yn y cynllun mawr o bethau, ond mae'n cael ei datrys yn annibynnol yr hanner arall. Nawr pa gam ydw i ar os wyf yn cadw ailddirwyn sut y dechreuodd y stori? Nawr mae'n rhaid i mi roi trefn yr hanner cywir. Felly nawr rydym yn ffordd yn ôl yn cychwyn y stori, a gadewch i ni wneud hyn yn gynt. Felly dw i'n mynd i ddatrys y hanner chwith y rhestr gyfan. Beth yw'r cam nesaf? Didoli'r hanner chwith yr hanner cywir. Didoli'r hanner chwith y chwith hanner y hanner cywir. A beth yw eich enw? CYNULLEIDFA: Omar. SIARADWR: Omar, gamu ymlaen, wneud. Hanner Chwith cael ei datrys. A beth yw eich enw? CYNULLEIDFA: Chris. SIARADWR: Chris, yn cymryd cam ymlaen, yr ydych yn cael eu didoli yn awr. Beth yw'r cam allweddol yn awr? Uno. Felly, un yn mynd i uno i mewn i le yma, pe gallech gymryd cam yn ôl, a thri yn mynd i gymryd cam yn ôl, yn uno. Felly mae'r hanner chwith y hanner i'r dde, yn awr yn cael ei sortio. Dweud y gwir, algorithm hwn yn teimlo fel ein bod yn gwastraffu ffordd mwy o amser nag o'r blaen, ond pe baem yn gwneud hyn mewn amser real, rydym annhymerus weld beth mae'r siopau cludfwyd mynd i fod. Yn awr dyma fi, yn iawn hanner y hanner cywir, gadewch i mi fynd yn ei flaen ac yn didoli'r hanner chwith. Cam ymlaen, beth yw eich enw? CYNULLEIDFA: Ramsey. SIARADWR: Ramsey bellach yn cael ei sortio. Beth yw eich enw? CYNULLEIDFA: Marina. SIARADWR: Marina bellach yn cael ei sortio fel yn dda, os ydych yn cymryd un cam ymlaen. Gam allweddol yma yn awr yn uno, rwy'n mynd i plycio o fy dwy restr, chwith ac i'r dde. Pump yn mynd i ddod yn gyntaf, a saith yn mynd i ddod nesaf. Ac eto, mae hyn yn fwriadol. Mae'r ffaith eu bod yn cymryd camu ymlaen ac yn ôl i fod i gynrychioli na allwn gwneud algorithm hwn yn ei le mor hawdd fel didoli swigod, a didoli dethol, a didoli mewnosod lle rydym yn unig cadw cyfnewid pobl. Yr wyf yn llythrennol angen rhyw fath o bapur crafu lle i roi Folks hyn er fy mod yn gwneud yr uno, ac yna gallaf rhoi yn ôl yn eu lle. Ac mae hynny'n allweddol oherwydd fy mod yn defnyddio adnodd newydd, lle, nid dim ond amser. OK, mae hyn yn anhygoel. Hanner Chwith cael ei ddidoli, hanner cywir yn ddidoli, nawr bod allwedd uno cam. Sut ydw i'n mynd i uno hyn? Felly, os byddwch yn dilyn fy llaw chwith a llaw dde, Rydw i'n mynd i bwynt fy llaw chwith ar yr hanner chwith, fy llaw dde ar yr hanner cywir, ac yn awr rhaid i mi benderfynu cam wrth gam bwy i uno mewn. Sy'n amlwg yn dod gyntaf? Rhif un. Felly dewch draw yma, dyma ein pad crafu. Felly nawr rif un, a rhybudd beth 'n annhymerus' yn ei wneud gyda fy llaw dde, Rydw i'n mynd i symud fy un llaw dde gamu drosodd i bwynt rhif tri, ac yn awr mae'n rhaid i mi wneud yr un penderfyniad. Ac mewn gwirionedd yn sefyll yn iawn yn flaen Luke yma os ydych allai, oherwydd mae hyn yn ein pad crafu. Felly, pwy sy'n dod nesaf? Rydym wedi Luke gyda rhif dau neu Chris gyda rhif tri. Yn amlwg Luke, rhif dau, felly yr ydych yn dod yma. Ond mae fy llaw chwith yn awr yn mynd i cael ei gynyddrannedig i bwyntio at Darren, a dyma y allweddol yn cymryd i ffwrdd gyda uno, dw i'n mynd i ddal i wneud hyn, yn amlwg, os ydych yn garedig o ddilyn y rhesymeg. Ond mae fy nwylo byth yn mynd i fynd yn ôl, sy'n golygu fy mod yn unig byth yn symud i y chwith gyda fy broses uno, ac mae hynny'n mynd i fod yn allweddol i ein dadansoddiad mewn dim ond eiliad. Felly nawr gadewch i ni orffen hyn i fyny yn gyflym. Felly tri sy'n dod nesaf, Yna pedair dod nesaf, ac yn awr bump sy'n dod nesaf, yna chwech, a saith, ac yna yn olaf wyth. Teimlo fel y algorithm arafaf eto, ond nid os ydym mewn gwirionedd rhedeg ar yr un fath o gyflymder cloc, felly i siarad, gyda'r un roi tic cloc fel o'r blaen. Pam? Wel, Gadewch i ni gymryd edrych ar y canlyniad terfynol. Gadewch i ni fynd yn ôl dros yma, gadewch i mi dynnu i fyny arddangosiad ar eu golwg o'r hyn yr ydym newydd ei wneud. Chwyddo i mewn yma, ar hyn dudalen fan hyn, yn dweud Firefox ein bod am giwio i fyny yn y blwch hwn, gadewch i ni dweud fath swigen, gyda lle rydym yn awr yn gyfarwydd yn dda, didoli dethol, sef un arall deg un syml, ac yn awr didoli uno heddiw, a oedd fydd ein diweddglo hinsoddol. Y rheswm y cymerodd gymaint llawer hirach yma gyda phobl a fi ar lafar yw, yn amlwg, Im 'yn esbonio pob cam. Ond os ydych yn syml cyflawni hyn, llawer fel y gwnaethom fath swigen a dethol fath nid yn unig ar eu golwg, gwylio yn union faint yn fwy effeithlon Leveraging hwn o is-adran a concro Gellir pan gaiff ei ddefnyddio i set ddata sy'n Nid yw hyd yn oed maint wyth, ond hyd yn oed yn llawer, llawer mwy. Yr wyf yn rhoi i chi uno didoli, ochr yn ochr â'r rhain algorithmau eraill. Mae hyn yn mynd i gael boenus gyflym, ac mae'r diweddglo Nid yn arbennig o hinsoddol, maent ond yn y pen draw didoli. Ond yr allwedd cymryd i ffwrdd yw bod edrych faint yn gynt o lawer uno fath oedd, oni bai eich bod yn meddwl fy mod unig fath o cyboli gyda chi. Os byddwn yn gwneud hyn un tro olaf, gadewch i ail-lwytho hwn, gadewch i ni fynd yn ôl a dewis math swigen, a dim ond ar gyfer cychwyn, gadewch i ni ddewis gosod didoli, dim ond ar gyfer mesur da. A'r tro hwn eto, gadewch i ni dewis didoli uno a gadewch i ni mewn gwirionedd yn rhedeg ochr yn ochr hyn. Ac nid yw, mewn gwirionedd, mae llyngyr. Yr hyn yr wyf wedi ei wneud yn effeithiol yw fy mod i wedi Rhannwyd fy mewnbwn yn ei hanner, unwaith eto, ac unwaith eto, ac unwaith eto. Ac mae dim ond cymaint o weithiau y gallwch rannu eich mewnbwn i haneri, gadawodd ac i'r dde. Beth yw'r fformiwla yr ydym yn cadw gweld sy'n disgrifio'r is-adran yn ei hanner unwaith eto, ac unwaith eto, ac unwaith eto, ac unwaith eto? CYNULLEIDFA: Logio n. SIARADWR: Logio n. Ond yna mae un cam allweddol eraill, Nid yw algorithm hwn yn cael ei logio n grisiau. Pe bai'n cael dim ond logio n grisiau, fyddem yn yr un broblem fel o'r blaen lle nad oes modd i ni fod yn yn siwr bod popeth yn didoli. Mae'n rhaid i chi edrych cyn lleied â phosibl ar elfennau n i fod yn sicr n elfennau yn cael eu datrys, fel arall mae'n naid o ffydd. Felly mae'n log n camau cyn lleied â phosibl, ond beth am y cam uno allweddol lle dwi'n uno fy hanner chwith a'r dde hanner ac yn cerdded ar draws y llwyfan? Faint o gamau yw bod i uno? Mae'n n, ond doeddwn i ddim yn unig uno y tro olaf. Ar bob un o'r rhai galwadau yn nythu, ar bob o'r rhai yn uno nythu, yr wyf yn dal didoli. Rwy'n unodd y ddau guys, yna dwy rhain guys, yna y ddau guys ac yn y blaen. Felly i ddim yn cyfuno unwaith eto, ac unwaith eto. Faint o weithiau? Felly, bob tro yr wyf yn rhannu'r rhestr yn ei hanner, fe wnes i uno. Rhannwch y rhestr yn ei hanner, yn gwneud yn uno. Felly os rannu'r rhestr gellir ei wneud amserau log n, a chyfuno'r yn y pen draw yn cymryd n grisiau, yr hyn a allai fod nawr yw'r uchaf rhwymo ar y gwaith o redeg adeg ein algorithm? n log n. Ac yn wir, dyna beth rydym wedi ei gyflawni yma. Felly mae'r teimlad eich bod yn gweld yn weledol pan y rhai tri pheth rhedeg ochr yn ochr yn sgwâr n erbyn n sgwario erbyn n log n. Pa sylfaenol byddwn yn gweld, nid yn unig heddiw, ond yn y dyfodol, yn llawer, llawer cyflymach. Mae rownd o gymeradwyaeth ar gyfer guys hyn, Byddaf yn eu gwobrwyo gyda pheli straen. Gadewch i ni ohirio yma heddiw, ac byddwn yn eich gweld ar ddydd Llun.