[Powered by Google Translate] [Trefnu Mewnosod]
[Tommy MacWilliam] [Harvard University]
[Mae hyn yn CS50.TV]
Gadewch i ni edrych ar fath gosod, algorithm ar gyfer cymryd restr o rifau a didoli nhw.
Mae algorithm, cofiwch, yn syml, trefn cam-wrth-gam ar gyfer cyflawni'r dasg.
Y syniad sylfaenol y tu ôl math gosod, yw rhannu ein rhestr yn ddau ddogn,
cyfran didoli a chyfran heb eu didoli.
>> Ym mhob cam o'r algorithm, mae nifer yn cael ei symud
gan y rhan heb eu didoli i'r gyfran datrys
nes yn y pen draw y rhestr gyfan yn cael ei datrys.
Dyma restr o chwe rhif heb eu didoli - 23, 42, 4, 16, 8, a 15.
Gan nad yw'r rhifau i gyd mewn trefn esgynnol, maen nhw'n heb eu gwahanu.
Gan nad ydym wedi dechrau didoli eto, byddwn yn ystyried pob un o'r chwe elfen ein cyfran heb eu didoli.
>> Unwaith y byddwn yn dechrau didoli, byddwn yn gosod y rhain rhifau didoli ar ochr chwith y rhain.
Felly, gadewch i ni ddechrau gyda 23, yr elfen gyntaf yn ein rhestr.
Nid oes gennym unrhyw elfennau yn ein cyfran datrys eto,
felly gadewch i ni dim ond yn ystyried 23 i fod yn ddechrau a diwedd ein cyfran datrys.
Yn awr, mae ein cyfran didoli un rhif, 23,
ac mae ein cyfran heb eu didoli yn y pum rhifau.
Gadewch i ni yn awr rhowch y rhif nesaf yn ein cyfran heb eu didoli, 42, i mewn i'r gyfran datrys.
>> I wneud hynny, bydd angen i ni gymharu y 42 i 23 - yr elfen yn unig yn ein cyfran datrys hyd yn hyn.
Mae pedwar deg dau yn fwy na 23, fel y gallwn yn syml atodi 42 i ddiwedd y
o gyfran datrys y rhestr. Great!
Nawr ein cyfran datrys ddwy elfen, ac mae ein cyfran heb eu didoli Mae pedair elfen.
Felly, gadewch i ni nawr symud i 4, yr elfen nesaf yn y gyfran heb eu didoli.
Felly, dylai ble y caiff ei osod yn y gyfran datrys?
>> Cofiwch, mae arnom eisiau rhoi rhif hwn er mwyn datrys
felly mae ein cyfran datrys yn parhau i fod didoli'n gywir bob amser.
Os ydym yn rhoi 4 i'r dde o'r 42, yna bydd ein rhestr fod allan o drefn.
Felly, gadewch i ni barhau i symud dde-i-chwith yn ein cyfran fath.
Wrth i ni symud, gadewch i ni symud pob rhif i lawr lle i wneud lle ar gyfer y rhif newydd.
Iawn, 4 hefyd yn llai na 23, felly ni allwn osod yma chwaith.
Gadewch i ni symud y 23 cywir un lle.
>> Mae hynny'n golygu hoffem i osod y 4 i mewn i'r slot cyntaf yn y gyfran datrys.
Hysbysiad sut y gofod hwn yn y rhestr eisoes yn wag,
oherwydd ein bod wedi bod yn symud elfennau trefnu i lawr fel yr ydym wedi dod ar eu traws nhw.
Mae pob hawl. Felly, rydym hanner ffordd yno.
Gadewch i ni barhau ein algorithm trwy fewnosod y 16 i mewn i'r gyfran datrys.
Un ar bymtheg yn llai na 42, felly gadewch i ni symud y 42 i ar y dde.
Un ar bymtheg hefyd yn llai na 23, felly gadewch i ni hefyd yn symud yr elfen honno.
>> Yn awr, 16 yn fwy na 4. Felly, mae'n edrych fel hoffem i fewnosod y 16 rhwng y 4 a'r 23.
Er symud drwy'r rhan datrys y rhestr o'r dde i'r chwith,
4 yw'r rhif cyntaf rydym wedi gweld bod yn llai na'r nifer a
rydym yn ceisio i fewnosod.
Felly, yn awr gallwn mewnosoder y 16 i hyn slot gwag,
sydd, cofiwch, rydym wedi creu gan elfennau sy'n symud yn y rhan fath dros y
fel yr ydym wedi dod ar eu traws nhw.
>> Mae pob hawl. Yn awr, mae gennym bedair elfen didoli a dwy elfen heb eu didoli.
Felly, gadewch i ni symud yr 8 i mewn i'r gyfran datrys.
Wyth yn llai na 42.
Wyth yn llai na 23.
Ac 8 yn llai na 16.
Ond mae 8 yn fwy na 4.
Felly, byddem yn hoffi i fewnosod yr 8 rhwng y 4 a'r 16.
Ac yn awr rydym yn unig un elfen yn weddill i ddatrys - y 15.
Bymtheg yn llai na 42,
Bymtheg yn llai na 23.
A 15 yn llai na 16.
Ond 15 yn fwy na 8.
>> Felly, dyma lle rydym eisiau gwneud ein gosod terfynol.
Ac rydym ni'n ei wneud.
Nid oes gennym unrhyw elfennau mwy yn y gyfran heb eu didoli,
ac mae ein cyfran didoli yn y drefn gywir.
Mae'r niferoedd yn cael eu harchebu o'r lleiaf i'r mwyaf.
Felly, gadewch i ni edrych ar rai pseudocode sy'n disgrifio'r camau rydym yn unig berfformio.
>> Ar llinell 1, gallwn weld bod bydd angen i ni ailadrodd dros bob elfen yn y rhestr
ac eithrio'r cyntaf, bydd gan fod yr elfen gyntaf yn y gyfran heb eu didoli yn troi'n ddim ond
yr elfen gyntaf yn y rhan didoli.
Ar linellau 2 a 3, rydym yn cadw golwg ar ein lle ar hyn o bryd yn y gyfran heb eu didoli.
Elfen yn cynrychioli nifer o bryd rydym yn symud i mewn i'r gyfran didoli,
a j yn cynrychioli ein mynegai yn y gyfran heb eu didoli.
>> Ar llinell 4, rydym yn ailadrodd drwy'r gyfran datrys o dde i'r chwith.
Rydym yn awyddus i roi'r gorau i ailadrodd unwaith y bydd yr elfen i'r chwith ar ein sefyllfa bresennol
yn llai na'r elfen ydym yn ceisio ei fewnosod.
Ar llinell 5, rydym yn symud pob elfen rydym yn dod ar draws un lle i'r dde.
Drwy hynny, bydd gennym ofod clir i fewnosod yn pan fyddwn yn dod o hyd i'r elfen gyntaf
llai na'r elfen rydym yn symud.
Ar llinell 6, rydym yn diweddaru ein cownter i barhau i symud i'r chwith trwy'r rhan didoli.
Yn olaf, ar-lein 7, rydym yn gosod yr elfen yn y rhan datrys y rhestr.
>> Rydym yn gwybod ei bod yn iawn i fewnosod yn j sefyllfa,
oherwydd ein bod wedi symud yn barod yr elfen a arferai fod yno un lle i'r dde.
Cofiwch, rydym yn symud drwy'r rhan didoli o'r dde i'r chwith,
ond rydym yn symud drwy'r rhan heb eu didoli o'r chwith i'r dde.
Mae pob hawl. Gadewch i ni yn awr yn cymryd golwg ar ba mor hir yn rhedeg y algorithm yn cymryd.
Byddwn ofyn yn gyntaf y cwestiwn pa mor hir mae'n ei gymryd ar gyfer y algorithm i redeg yn yr achos gwaethaf.
Dwyn i gof ein bod yn cynrychioli y tro hwn yn rhedeg gyda Big O nodiant.
Er mwyn datrys ein rhestr, bu'n rhaid i ni ailadrodd dros yr elfennau yn y rhan heb eu didoli,
ac ar gyfer pob un o'r elfennau hynny, o bosibl dros yr holl elfennau yn y rhan didoli.
Yn reddfol, mae hyn yn swnio fel llawdriniaeth O (n ^ 2).
>> Edrych ar ein pseudocode, mae gennym dolen nythu y tu mewn arall dolen,
sydd, yn wir, swnio fel llawdriniaeth O (n ^ 2).
Fodd bynnag, nid yw'r gyfran datrys y rhestr yn cynnwys y rhestr gyfan tan y diwedd un.
Still, gallem o bosibl ychwanegu elfen newydd ar y cychwyn cyntaf y gyfran datrys
ar bob fersiwn o'r algorithm,
sy'n golygu y byddai'n rhaid i ni edrych ar bob elfen ar hyn o bryd yn y rhan didoli.
Felly, mae hynny'n golygu yn bosibl i ni wneud un gymhariaeth ar gyfer yr ail elfen,
2 cymariaethau ar gyfer y drydedd elfen, ac yn y blaen.
Felly, cyfanswm nifer o gamau yn y swm y cyfanrifau o 1 i hyd y rhestr minws 1.
Gallwn gynrychioli hyn gyda symiant.
>> Ni fyddwn yn mynd i mewn i summations yma, ond mae'n troi allan fod y symiant yn hafal i
n (n - 1) dros 2, sef n gyfwerth ^ 2/2 - n / 2.
Wrth sôn am runtime asymptotic,
hyn ^ n 2 Tymor yn mynd i dra-arglwyddiaethu y tymor n.
Felly, didoli rhoi i mewn yw Big O (n ^ 2).
Beth os ydym yn rhedeg fath gosod ar restr datrys eisoes.
Yn yr achos hwnnw, byddem yn syml yn adeiladu i fyny y rhan didoli o'r chwith i'r dde.
Felly, byddwn dim ond angen ar y drefn o gamau n.
>> Mae hynny'n golygu y math mewnosod Mae perfformiad gorau-achos n,
yr ydym yn cynrychioli gyda Ω (n).
A dyna ni am y math gosod,
dim ond un o'r algorithmau llawer y gallwn ei defnyddio i ddatrys rhestr.
Fy enw i yw Tommy, ac mae hyn yn CS50.
[CS50.TV]
O, ni allwch atal hynny unwaith y bydd yn dechrau.
O, rydym yn gwneud hynny - Boom >>!