>> 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.