[CHWARAE CERDDORIAETH] DOUG LLOYD: didoli Dethol yn algorithm hynny, fel y byddech yn ei ddisgwyl, didoli'r set o elfennau. Ac algorithm adalw yn set cam-wrth-gam o gyfarwyddiadau am gwblhau tasg. 

Yn dethol didoli'r syniad sylfaenol yw hyn, ddod o hyd i'r elfen heb eu didoli lleiaf a ychwanegu at ddiwedd y rhestr ddidoli. I bob pwrpas beth mae hyn yn ei wneud yw adeiladu rhestr didoli, un elfen ar y tro. Torri i lawr i pseudocode gallem ddatgan algorithm hwn fel a ganlyn, ailadrodd hyn nes dim elfennau heb eu didoli yn parhau. Chwiliwch drwy'r heb eu didoli data i ddarganfod gwerth lleiaf, Yna gyfnewid y gwerth lleiaf gyda'r Elfen gyntaf y rhan heb eu didoli. 

Gallai fod o gymorth i ddychmygu hyn, felly gadewch i ni edrych ar hyn. Felly, mae hyn, yr wyf yn dadlau, yn amrywiaeth heb eu didoli ac rwyf wedi Nododd iddo gan nodi bod yr holl o'r elfennau yn cael eu lliwio'n goch, Nid ydynt yn cael eu datrys eto. Mae hyn yn y cyfan rhan heb eu didoli y rhesi. 

Felly gadewch i ni fynd drwy'r camau o didoli dewis i ddatrys amrywiaeth hwn. Felly unwaith eto, rydym yn ailadrodd gonna hyd nes nad oes elfennau heb eu didoli yn parhau. Rydym yn chwilio gonna drwy'r data i ddarganfod gwerth lleiaf, ac yna cyfnewid y gwerth hwnnw gyda'r Elfen gyntaf y rhan heb eu didoli. 

Ar hyn o bryd, unwaith eto, mae'r cyfan amrywiaeth yw'r rhan heb eu didoli. Mae pob un o'r elfennau coch yn heb eu didoli. Felly, rydym yn chwilio drwy a rydym yn dod o hyd i'r gwerth lleiaf. Rydym yn dechrau ar y dechrau, rydym yn mynd at y diwedd, rydym yn dod o hyd i'r gwerth lleiaf yw, un. Felly mae hynny'n rhan un. Ac yna rhan dau, gyfnewid y gwerth hwnnw gyda yr elfen gyntaf y rhan heb eu didoli, neu yr elfen goch cyntaf. 

Yn yr achos hwn a fyddai'n cael ei pump, felly rydym yn gyfnewid un a phump. Pan fyddwn yn gwneud hyn, y gallwn ar eu golwg yn gweld bod rydym wedi Symudodd yr elfen lleiaf gwerthfawr y rhesi, i'r cychwyn cyntaf. Didoli yr elfen honno yn effeithiol. 

Ac felly y gallwn ni wir gadarnhau ac yn datgan fod un, yn cael ei datrys. Ac felly byddwn yn dangos y rhan didoli o'n array, trwy liwio ei las. 

Nawr rydym yn unig ailadrodd y broses eto. Rydym yn chwilio drwy'r rhan heb eu didoli o yr amrywiaeth i ddod o hyd i'r elfen lleiaf. Yn yr achos hwn, mae'n ddau. 

Rydym yn cyfnewid bod gyda'r cyntaf elfen o'r rhan heb eu didoli. Yn yr achos dau hefyd yn digwydd bod yr elfen gyntaf y rhan heb eu didoli. Felly, rydym yn gyfnewid dau gyda ei hun, sydd mewn gwirionedd dim ond yn gadael dau lle y mae, ac mae'n datrys. Gan barhau ymlaen, rydym yn chwilio drwy'r i ddod o hyd i'r elfen lleiaf. Mae'n tri. Rydym yn cyfnewid gyda'r cyntaf elfen, sef pump. Ac yn awr dri cael ei drefnu. 

Rydym yn chwilio drwy unwaith eto, ac yr ydym yn ddod o hyd i'r elfen lleiaf yw pedwar. Rydym yn cyfnewid 'i ag yr elfen gyntaf y rhan heb eu didoli, ac yn awr bedwar yn cael ei sortio. 

Rydym yn canfod bod bump oed yn yr elfen lleiaf. Rydym yn cyfnewid gyda'r cyntaf elfen o'r rhan heb eu didoli. Ac yn awr bump yn didoli. 

Ac yna yn olaf, mae ein rhan heb eu didoli yn cynnwys o ddim ond un elfen, felly rydym yn chwilio drwy a gwelwn fod chwech yw'r lleiaf, ac mewn gwirionedd, dim ond elfen. Ac yna gallwn ddweud ei fod yn datrys. Ac yn awr rydym wedi newid ein array rhag cael eu heb eu didoli yn gyfan gwbl mewn coch, er mwyn didoli yn gyfan gwbl mewn glas, gan ddefnyddio didoli dewis. 

Felly beth yw'r sefyllfa waethaf yma? Yn dda yn y gwaethaf absoliwt achos, mae'n rhaid i ni edrych drosodd holl elfennau y rhesi i ddod o hyd i'r elfen heb eu didoli lleiaf, ac mae'n rhaid i ni ailadrodd y broses hon n amser. Unwaith ar gyfer pob elfen o'r casgliad oherwydd ein bod yn unig, yn y algorithm hwn, didoli un elfen ar pryd. 

Beth yw'r senario achos gorau? Wel mae'n union yr un fath, dde? Mae gennym mewn gwirionedd yn dal i gamu drwy pob elfen unigol y rhesi er mwyn cadarnhau ei fod, mewn gwirionedd, yr elfen lleiaf. 

Felly mae'r Rhedeg achos gwaethaf, yr ydym rhaid ailadrodd broses n amserau, unwaith ar gyfer pob un o'r elfennau n. Ac yn y senario achos gorau, mae'n rhaid i ni wneud yr un peth. 

Felly meddwl yn ôl at ein blwch offer cymhlethdod cyfrifiadurol, beth yn eich barn chi yn y gwaethaf Rhedeg achos dros fath dethol? Beth yn eich barn chi yw'r gorau Rhedeg achos dros fath dethol? 

A wnaethoch chi ddyfalu Big O n sgwâr, a Big Omega o n sgwâr? Byddech yn iawn. Mae'r rhai yn cael eu, mewn gwirionedd, y achos gwaethaf a rhedeg achos gorau adegau, ar gyfer y math dethol. 

Rwy'n Doug Lloyd. Mae hyn yn CS50.