DOUG LLOYD: Felly, yn CS50 rydym yn dysgu am amrywiaeth o didoli a chwilio algorithmau. Ac weithiau gall fod yn ychydig yn anodd i gadw golwg ar yr hyn algorithm sy'n gwneud beth. Rydym wedi gwirionedd dim ond sgim yr wyneb hefyd, mae yna lawer o chwilio eraill a didoli algorithmau. Felly, yn y fideo hwn gadewch i ni dim ond yn cymryd ychydig funudau i geisio distill pob algorithm i lawr at ei elfennau craidd er mwyn i chi gofio y mwyaf gwybodaeth bwysig am iddynt a gallu mynegi'r gwahaniaethau, os oes angen. 

Y cyntaf yw math dethol. Y syniad sylfaenol y tu ôl i fath dethol yn dod o hyd i'r elfen heb eu didoli lleiaf mewn amrywiaeth ac yn cyfnewid gyda'r Elfen heb ei ddidoli cyntaf y rhesi. Rydym yn dweud bod y gwaethaf-achos amser rhedeg o hynny oedd sgwâr n. Ac os ydych chi am i gofio pam, cymryd a edrych ar y fideo didoli dewis. Mae'r amser yn rhedeg orau-achos hefyd yn cael ei sgwâr n. 

Didoli Bubble, y syniad y tu ôl i hynny un yw cyfnewid parau cyfagos. Felly dyna allwedd sy'n eich helpu cofiwch y gwahaniaeth yma. Dewis math yw, hyd yn hyn, ddod o hyd i'r swigen smallest-- didoli yw cyfnewid parau cyfagos. Rydym yn gyfnewid parau cyfagos o elfennau os ydynt yn allan o drefn, a oedd yn effeithiol swigod elfennau mwy i'r dde, ac ar yr un pryd mae hefyd yn dechrau i symud elfennau llai ar y chwith. Y gwaethaf-achos amser yn rhedeg achos o'r math swigen yn sgwâr n. Mae'r amser yn rhedeg orau-achos o swigen fath yn n. Oherwydd yn y sefyllfa honno nid ydym yn actually-- Efallai na fydd angen i i ni wneud unrhyw gyfnewidiadau o gwbl. Dim ond rhaid i ni wneud un pasio ar draws pob elfen n. 

Yn y math mewnosod, mae'r syniad sylfaenol yma yn newid. Dyna y gair allweddol ar gyfer y math gosod. Rydym yn mynd i gamu unwaith drwy yr amrywiaeth o'r chwith i'r dde. Ac wrth i ni ei wneud, rydym yn mynd i newid elfennau rydym wedi gweld yn barod i wneud lle i rhai llai y mae angen i gyd-fynd rhywle yn ôl yn y gyfran didoli. Felly, rydym yn adeiladu yr amrywiaeth ddidoli un elfen ar y tro, o'r chwith i'r dde, ac yr ydym yn symud pethau i wneud lle. Mae'r amser yn rhedeg gwaethaf-achos didoli gosod yn sgwâr n. Yr amser gorau-achos yn rhedeg yn n. 

Cyfuno sort-- y gair allweddol yma ei rannu ac uno. Rydym yn rhannu yr amrywiaeth lawn, p'un 'i' chwe elfen, wyth elfen, 10,000 elements-- rydym yn rhannu ei i lawr i'w hanner, hanner, hanner, nes gennym o dan amrywiaeth o n un elfen araeau. Mae set o n un elfen araeau. Felly, rydym yn dechrau gyda un 1,000-elfen array, ac yr ydym yn cyrraedd y pwynt lle rydym yn rhaid i 1,000 un-elfen araeau. Yna, rydym yn dechrau i uno is araeau rhai ôl at ei gilydd yn y drefn gywir. Felly, rydym yn cymryd ddau arae un-elfen a chreu dwy elfen array. Rydym yn cymryd ddau arae dwy elfen a chreu pedwar-elfen array ac yn y blaen ac yn y blaen hyd nes y byddwn i wedi eto ailadeiladwyd un elfen n array. 

Mae'r amser yn rhedeg gwaethaf-achos uno fath yw n amserau log n. Mae gennym elfennau n, ond broses hailgyfuno hon cymryd log n camau i fynd yn ôl i amrywiaeth lawn. Yr achos gorau rhedeg amser hefyd yn n log n gan nad yw y broses hon yn wir gofal a oedd y casgliad oedd didoli neu beidio i ddechrau. Mae'r broses yr un fath, mae ' unrhyw ffordd i bethau cylched byr. Felly n log n yn yr achos gwaethaf, n log n yn yr achos gorau. 

Buom yn siarad am ddwy chwilio algorithmau. Felly chwiliad llinol yn ymwneud ailadrodd. Awn ymlaen ar draws yr amrywiaeth unwaith, o'r chwith i'r dde, ceisio dod o hyd i'r rhif ein bod yn chwilio am. Yr amser gwaethaf-achos yn rhedeg yn O fawr o n. Gallai fod yn mynd â ni ailadrodd ar draws pob elfen unigol i ddod o hyd i'r elfen rydym yn chwilio ar gyfer, naill ai yn y swydd ddiwethaf, neu ddim o gwbl. Ond ni allwn gadarnhau bod hyd nes rydym wedi edrych ar bopeth. my-achos gorau, rydym yn dod o hyd ar unwaith. Mae'r amser yn rhedeg orau-achos Chwilio llinol yw omega o 1. 

Yn olaf, yr oedd chwilio deuaidd, sy'n gofyn am amrywiaeth amrywiol. Cofiwch fod 'na iawn ystyriaeth bwysig wrth weithio gyda chwiliad deuaidd. Mae'n rhagofyniad i ddefnyddio iddo-- yr amrywiaeth eich bod yn chwilio trwy Mae'n rhaid eu datrys. Fel arall, yr allweddair yn rhaniad a gorchfygu. Rhannwch yr amrywiaeth mewn i hanner a gwared ar hanner yr elfennau bob tro wrth i chi symud ymlaen trwy'r. Oherwydd rhaniad hwn a gorchfygu a hollti pethau yn hanner ffordd, yr amser yn rhedeg waethaf chwilio deuaidd yw log n, sy'n sylweddol yn well na n chwilio llinellol yn. Yr amser gorau-achos yn rhedeg yn dal yn un. 

Efallai y byddwn yn ei chael yn syth i'r tro cyntaf i ni wneud is-adran, ond, unwaith eto, cofiwch fod er bod y chwiliad deuaidd yn sylweddol well na'r chwilio llinellol yn rhinwedd bod log n erbyn n, Efallai y bydd rhaid i chi fynd drwy'r gwaith o ddatrys eich array cyntaf, a gallai ei wneud yn llai effeithiol yn dibynnu ar faint y ailadrodd didoli. 

Rwy'n Doug Lloyd, mae hyn yn CS50.