[CHWARAE CERDDORIAETH] 

DOUG LLOYD: OK, felly mae uno didoli yn algorithm arall eto y gallwn eu defnyddio i roi trefn ar elfennau amrywiaeth. Ond fel y byddwn yn gweld, 'i' got a gwahaniaeth sylfaenol iawn o fath dethol, swigen didoli, a didoli mewnosod sy'n ei gwneud yn wir yn eithaf clyfar. 

Y syniad sylfaenol y tu ôl i uno didoli yw didoli arrays llai ac yna cyfuno arrays rhai gyda'i gilydd, neu uno them-- dyna pam y name-- er mwyn didoli. Mae'r ffordd y uno fath yn ei wneud mae hyn yn dan ddylanwad busnes yn offeryn Gelwir recursion, sef yr hyn rydym yn mynd i fod yn siarad am cyn bo hir, ond nid ydym wedi siarad mewn gwirionedd am hyd yn hyn. 

Dyma y syniad sylfaenol y tu ôl math uno. Trefnu yn hanner chwith y array, gan dybio n yn fwy na 1. A hyn yr wyf yn ei olygu wrth ddweud gan dybio n yn fwy na 1 yw, Yr wyf yn meddwl y gallwn ni gytuno, os amrywiaeth Dim ond yn cynnwys elfen unigol, mae'n datrys. Nid oes mewn gwirionedd yn rhaid i ni i wneud unrhyw beth iddo. Gall Rydym yn unig yn datgan iddo gael ei datrys. Dim ond un elfen. 

Felly mae'r pseudocode, unwaith eto, yn ddatrys y hanner chwith y rhesi, Yna ddatrys yr hanner hawl y array, Yna uno'r ddau hanner at ei gilydd. Yn awr, yn barod efallai y byddwch yn meddwl, mae'n fath o ychydig swnio fel eich bod yn oedi cyn gwneud the-- nad ydych yn mewn gwirionedd yn gwneud unrhyw beth. Rydych yn ei ddweud ddatrys y chwith hanner, didoli'r hanner cywir, ond nad ydych yn dweud i mi sut yr ydych yn gwneud hynny. 

Ond cofiwch fod cyn belled â amrywiaeth yn elfen sengl, gallwn ddatgan ei datrys. Yna gallwn jyst cyfuno gyda'i gilydd. A dyna mewn gwirionedd y syniad sylfaenol y tu ôl math uno, yw i dorri i lawr fel bod eich araeau o faint un. Ac yna byddwch yn ail-adeiladu oddi yno. 

Cyfuno fath yn bendant algorithm cymhleth. Ac mae hefyd ychydig yn cymhleth i ddelweddu. Felly, gobeithio, y delweddu fy mod wedi yma yn eich helpu i ddilyn ar hyd. A byddaf yn gwneud fy ngorau i adrodd pethau a symud ymlaen drwy'r ychydig hyn yn fwy yn araf na'r rhai eraill dim ond er mwyn, gobeithio cael eich pen o amgylch y syniadau y tu ôl math uno. 

Felly mae gennym yr un amrywiaeth â'r didoli fideos algorithm eraill os ydych chi wedi gweld them-- o chwe elfen arae. Ac mae ein cod pseudocode yma yw didoli yr hanner chwith, didoli'r hanner cywir, cyfuno'r ddau hanner at ei gilydd. Felly gadewch i ni gymryd y coch brics tywyll iawn amrywiaeth a didoli'r hanner chwith ohono. 

Felly, am y tro, rydym yn mynd i anwybyddu'r pethau ar y dde. Mae'n yno, ond rydym yn nid ar y cam eto. Nid ydym ni mewn math y hanner dde o'r rhesi. Ry'n ni mewn math y chwith hanner y rhesi. A dim ond er mwyn o fod ychydig yn fwy yn glir, fel y gallaf gyfeirio i ba gam rydym yn ar, Rydw i'n mynd i newid y lliw y set hon i oren. Yn awr, rydym yn dal i siarad am y un hanner chwith y rhesi gwreiddiol. Ond dw i'n gobeithio bod drwy allu cyfeirio at y lliwiau o eitemau amrywiol, bydd yn ei gwneud yn ychydig yn fwy glir beth sy'n digwydd fan hyn. 

Iawn, felly erbyn hyn mae gennym tri elfen arae. Sut rydym ddatrys hanner chwith o hyn array, sydd yn dal i fod y cam hwn? Rydym yn ceisio datrys y chwith hanner y brics coch array-- hanner chwith o'r rhain Rwyf bellach wedi lliw oren. 

Wel, gallem geisio ailadrodd y broses hon eto. Felly, rydym yn dal i fod yn y canol ceisio datrys hanner chwith y rhesi llawn. Mae hanner chwith y array, Im 'jyst yn mynd i benderfynu fympwyol bod yr hanner chwith yn llai na'r hanner cywir, gan fod hyn yn digwydd i yn cynnwys tair elfen. 

Ac felly yr wyf i'n mynd i ddweud bod y chwith hanner yr hanner chwith y rhesi yn unig yw yr elfen pump. Pump, yn elfen sengl array, rydym yn gwybod sut i ddatrys y. Ac felly pump yn cael ei datrys. Rydym yn jyst yn mynd i ddatgan hynny. Mae'n elfen amrywiaeth sengl. 

Felly, rydym yn awr wedi datrys y chwith hanner y half-- chwith neu yn hytrach, rydym wedi datrys y chwith hanner y oren. Felly nawr, er mwyn dal i fod yn gyflawn hanner chwith yr amrywiaeth gyffredinol, yn mae angen i ni ddatrys yr hanner cywir yr oren, neu pethau hyn. Sut rydym yn gwneud hynny? Wel, mae gennym ddwy elfen arae. Felly, gallwn ddatrys yr hanner chwith y rhesi, sef dau. Dau yn elfen sengl. Felly mae'n trefnu yn ôl ddiofyn. Yna, gallwn ddatrys yr hanner cywir o y rhan honno o'r array, yr un. Dyna fath o yn ddiofyn. 

Mae hyn yn awr yn y tro cyntaf rydym wedi cyrraedd cam uno. Rydym wedi cwblhau, er bod rydym yn awr yn fath o nythu down-- a dyna fath o anodd peth gyda recursion yw, mae angen i chi gadw eich pennaeth am ble yr ydym. Felly rydym wedi fath o chwith hanner y gyfran oren. 

Ac yn awr, rydym yn yng nghanol didoli hanner dde o'r gyfran oren. Ac yn y broses honno, yr ydym yn bellach am i fod ar y cam, cyfuno'r ddau hanner at ei gilydd. Pan edrychwn ar y ddau hanner y rhesi, rydym yn gweld dau ac un. Pa elfen yn llai? Un. 

Yna, pa elfen yn llai? Wel, mae'n ddau neu ddim byd. Felly mae'n dau. Felly nawr, dim ond i ffrâm eto lle'r ydym ni mewn cyd-destun, rydym wedi datrys y chwith hanner y oren a'r hanner dde o'r tarddiad. Gwn fy mod wedi newid y lliwiau unwaith eto, ond dyna lle yr oeddem. A'r rheswm Fe wnes i hyn oherwydd bod y broses hon yn mynd i ddal ati, ailadrodd i lawr. Rydym wedi sortio y chwith hanner y cyn-oren a'r hanner dde o'r cyn-oren. 

Yn awr, mae angen i uno rhai ddau hanner at ei gilydd hefyd. Dyna'r cam rydym ar. Felly, rydym yn ystyried pob un o'r elfennau sydd bellach yn wyrdd, hanner chwith y rhesi gwreiddiol. Ac rydym yn cyfuno y rhai gan ddefnyddio'r un broses gwnaethom dros uno dau ac un ychydig funudau'n ôl. 

Mae'r hanner chwith, y lleiaf Elfen ar hanner chwith yw pump. Yr elfen lleiaf ar yr hanner cywir yn un. Pa un o'r rheini yn llai? Un. 

Yr elfen lleiaf ar yr hanner chwith yw pump. Yr elfen lleiaf ar yr hanner cywir yw dau. Beth yw'r lleiaf? Dau. Ac yna yn olaf pump a dim byd, gallwn ddweud pump. 

Iawn, llun mor fawr, gadewch i ni gymryd seibiant am eiliad a chyfrif i maes lle yr ydym. Os byddwn yn dechrau o y cychwyn cyntaf, rydym yn bellach wedi cwblhau ar gyfer yr amrywiaeth gyffredinol yn unig un cam y cod pseudocode yma. Rydym wedi datrys y chwith hanner y rhesi. 

Dwyn i gof bod y ddogfen wreiddiol gorchymyn oedd pump, dau, un. Drwy fynd drwy'r broses hon a nythu i lawr ac ailadrodd, parhau i dorri'r broblem i lawr yn rhannau llai ac yn llai, rydym bellach wedi cwblhau cam un o'r pseudocode am yr amrywiaeth cychwyn cyfan. Rydym wedi datrys ei hanner chwith. 

Felly nawr gadewch i rewi yno. Ac yn awr gadewch i ni ddatrys yr hawl hanner y rhesi gwreiddiol. Ac rydym yn mynd i wneud hynny drwy mynd trwy'r un ailadroddol broses o dorri pethau i lawr ac yna eu cyfuno gyda'i gilydd. 

Felly mae'r hanner chwith y coch, neu'r hanner chwith o hanner dde o'r gwreiddiol array, dwi'n mynd i ddweud yw tri. Unwaith eto, rwy'n bod yn gyson yma. Os oes gennych rhyfedd nifer o elfennau, mae'n Nid yw o bwys mewn gwirionedd a yw byddwch yn gwneud yr un a adawodd llai neu yr un cywir llai. 

Yr hyn sy'n bwysig yw bod pryd bynnag y byddwch yn dod ar draws y broblem hon wrth gynnal yn uno, mae angen i chi fod yn gyson. Rydych naill ai angen i bob amser gwneud ochr chwith llai neu bob amser angen i ni wneud yr ochr dde llai. Yma, yr wyf wedi dewis bob amser yn gwneud yr ochr chwith llai pan fydd fy array, neu fy is-array, o faint od. 

Tri yn elfen sengl, ac felly mae'n cael ei datrys. Rydym wedi ysgogi y rhagdybiaeth drwy gydol ein proses gyfan hyd yn hyn. Felly nawr gadewch i ni ddatrys yr hawl hanner yr hanner cywir, neu hanner dde o'r coch. 

Unwaith eto, mae angen i ni rannu hyn i lawr. Nid yw hyn yn elfen amrywiaeth sengl. Ni allwn ddatgan ei datrys. Ac felly yn gyntaf, rydym yn mynd i roi trefn ar yr hanner chwith. 

Mae'r hanner chwith yn elfen sengl, felly mae'n fath o yn ddiofyn. Yna, rydyn ni'n mynd i ddatrys yr hawl hanner, sy'n elfen sengl. Mae'n trefnu yn ddiofyn. Ac yn awr, gallwn uno dwy hynny at ei gilydd. Pedwar yn llai, ac Yna, chwech yn llai. 

Unwaith eto, beth ydyn ni wedi'i wneud yn y fan hon? Rydym wedi sortio y chwith hanner yr hanner cywir. Neu fynd yn ôl at y gwreiddiol lliwiau a oedd yno, rydym wedi datrys y chwith hanner y coch meddal. Yn wreiddiol roedd yn brics tywyll coch ac yn awr mae'n feddalach yn goch, neu roedd yn goch meddal. 

Ac yna rydym wedi datrys y hanner dde o'r coch meddal. Yn awr, yn dda, eu bod yn wyrdd unwaith eto, dim ond oherwydd ein bod yn mynd trwy broses. Ac mae'n rhaid i ni ailadrodd dros y a throsodd. 

Felly, erbyn hyn gallwn uno rhai ddau hanner at ei gilydd. A dyna beth rydym yn ei wneud yma. Felly y llinell ddu yn unig Rhannwyd yr hanner chwith a'r hanner cywir o'r math hwn yn rhan. 

Rydym yn cymharu gwerth lleiaf ar ochr chwith y array-- neu esgus i mi, y lleiaf gwerth y hanner chwith i werth lleiaf o'r hawl hanner ac yn canfod bod tri yn llai. Ac yn awr yn dipyn o optimeiddio, dde? Does dim byd mewn gwirionedd gadael ar yr ochr chwith. 

Does dim byd sy'n weddill ar yr ochr chwith, felly y gallwn effeithlon dim ond move-- y gallwn ddatgan gweddill ei fod mewn gwirionedd didoli a dim ond tac ei ymlaen, oherwydd does dim byd arall i gymharu yn erbyn. Ac rydym yn gwybod bod yr ochr dde o'r ochr dde yn cael ei datrys. 

Iawn, felly nawr gadewch i rewi eto ac chyfrif i maes ble yr ydym yn y stori. Yn yr amrywiaeth gyffredinol, yr hyn rydym wedi ei gyflawni? Rydym wedi cyflawni mewn gwirionedd bellach camau un a dau gam. Rydym yn datrys yr hanner chwith, ac rydym yn datrys yr hanner cywir. 

Felly nawr, cyfan sydd ar ôl yw i ni i uno dau hanner y rheini at ei gilydd. Felly, rydym yn cymharu yr isaf gwerthfawr elfen o bob hanner y rhesi yn eu tro ac yn symud ymlaen. Mae un yn llai na thri, felly neb yn mynd. 

Dau yn llai na thri, felly dau yn mynd. Three yn llai na 5, felly thri yn mynd. Mae pedwar yn llai na 5, felly phedwar yn mynd. Yna bum yn llai na chwech, a chwech cyfan sy'n weddill. 

Yn awr, yr wyf yn gwybod, a oedd yn llawer o gamau. Ac rydym wedi gadael llawer o gof yn ein deffro. A dyna beth sgwariau llwyd hynny. Ac mae'n fwy na thebyg yn teimlo fel hynny yn cymryd llawer hwy na didoli fewnosod, swigen didoli, neu ddidoli dethol. 

Ond mewn gwirionedd, gan fod llawer o'r prosesau hyn yn digwydd ar yr un adeg-- sydd yn rhywbeth yr ydym n annhymerus ', unwaith eto, siarad am pan fyddwn yn sôn am recursion mewn dyfodol video-- algorithm hwn mewn gwirionedd yn amlwg yn sylfaenol yn wahanol nag unrhyw beth yr ydym wedi ei weld o'r blaen ond mae hefyd yn sylweddol yn fwy effeithlon. 

Pam hynny? Wel, yn y gwaethaf senario achos, rydym wedi i rannu'r n elfen fyny ac yna eu ailgyfuno. Ond pan fyddwn yn ailgyfuno iddynt, yr hyn rydym yn ei wneud yn dyblu yn y bôn y maint y arrays llai. Mae gennym griw o un elfen araeau yr ydym yn effeithiol cyfuno i mewn i ddau arae elfen. Ac yna rydym yn cymryd rhai ddau arae elfen a'u cyfuno gyda'i gilydd i mewn i pedwar araeau elfennau, ac yn y blaen, ac yn y blaen, ac yn y blaen, nes i ni ag elfen n amrywiaeth sengl. 

Ond faint o doublings mae'n ei gymryd i gyrraedd n? Meddyliwch yn ôl at yr enghraifft llyfr ffôn. Sawl gwaith sydd gennym i rwygo y llyfr ffôn yn ei hanner, faint yn fwy Amseroedd sydd gennym i rwygo y llyfr ffôn yn ei hanner, os yw maint y llyfr ffôn dyblu? Dim ond un, dde? 

Felly mae yna rhyw fath o Elfen logarithmig yma. Ond rydym hefyd yn dal i orfod leiaf edrych ar yr holl elfennau n. Felly, yn y senario achos gwaethaf, uno fath yn rhedeg yn n log n. Mae'n rhaid i ni edrych ar holl elfennau n, ac yr ydym wedi eu cyfuno gyda'i gilydd mewn log n set o risiau. Yn y senario achos gorau, yr amrywiaeth yn cael ei datrys yn berffaith. Mae hynny'n wych. Ond yn seiliedig ar y algorithm sydd gennym yma, rydym yn dal i orfod rhannu ac ailgyfuno. Er bod yn yr achos hwn, mae'r hailgyfuno yn fath o aneffeithiol. Nad oes ei angen. Ond rydym yn dal i fynd drwy y broses gyfan beth bynnag. 

Felly, yn yr achos gorau ac yn yr achos gwaethaf, algorithm hwn yn rhedeg mewn n log n amser. Cyfuno fath yn bendant yn ychydig yn fwy anodd na'r prif algorithmau didoli eraill rydym wedi siarad am CS50, ond mae llawer mwy pwerus. 

Ac felly os ydych chi erioed yn dod o hyd achlysur i ei angen neu ei ddefnyddio i roi trefn ar set fawr o ddata, cael eich pen o gwmpas y syniad o recursion yn mynd i fod yn wirioneddol pwerus. Ac mae'n mynd i wneud eich rhaglenni 'n sylweddol llawer mwy effeithlon gan ddefnyddio uno fath yn erbyn unrhyw beth arall. Rwy'n Doug Lloyd. Mae hyn yn CS50.