[Powered by Google Translate] TOMMY: Gadewch i ni edrych ar fath dethol, algorithm
ar gyfer cymryd rhestr o rifau a didoli nhw.
Mae algorithm, cofiwch, yn syml, gam-wrth-gam
weithdrefn ar gyfer cyflawni'r dasg.
Y syniad sylfaenol y tu ôl math ddethol hon 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 o'r
cyfran heb eu didoli i'r gyfran didoli tan y pen draw
rhestr gyfan yn cael ei datrys.
Felly, dyma restr o chwe rhif -
23, 42, 4, 16, 8, a 15.
Ar hyn o bryd mae'r rhestr gyfan yn cael ei ystyried heb eu gwahanu.
Hyd yn oed er y gall nifer tebyg i 16 eisoes fod yn ei gywir
lleoliad, mae ein algorithm nid oes ffordd o wybod hynny tan y
rhestr gyfan yn cael ei datrys.
Felly, byddwn yn ystyried pob rhif i gael eu heb eu didoli nes i ni ddatrys
ein hunain.
Rydym yn gwybod ein bod am i'r rhestr fod yn nhrefn esgynnol.
Felly, byddwn yn awyddus i adeiladu i fyny y rhan datrys ein rhestr
o'r chwith i'r dde, o'r lleiaf i'r mwyaf.
I wneud hynny, bydd angen i ni ddod o hyd i'r elfen heb ei threfnu o leiaf
ac yn ei roi ar ddiwedd y rhan didoli.
Gan nad yw'r rhestr hon yn cael ei ddatrys, yr unig ffordd i wneud hynny yw
edrych ar bob elfen yn y gyfran heb eu didoli, cofio
pa elfen yw'r isaf a chymharu
pob elfen i hynny.
Felly, byddwn yn edrych yn gyntaf ar y 23.
Dyma'r elfen gyntaf rydym wedi gweld, felly byddwn yn cofio
fel y lleiafswm.
Nesaf byddwn yn edrych ar 42.
42 yn fwy na 23, felly 23 yn dal i fod y lleiaf.
Yn dilyn hynny y 4 sydd yn llai na 23, felly byddwn yn cofio 4
fel yr isafswm newydd.
Nesaf yn 16 sy'n fwy na 4, hynny 4
yn dal i fod y lleiaf.
8 yn fwy na 4, a 15 yn fwy na 4, felly mae'n rhaid 4 yn
yr elfen lleiaf heb eu didoli.
Felly hyd yn oed er, fel bodau dynol, gallwn ar unwaith weld bod 4 yn
yr elfen lleiaf, ein algorithm angen i edrych ar
bob elfen heb eu didoli, hyd yn oed ar ôl i ni wedi dod o hyd i'r 4 - y
elfen lleiaf.
Felly nawr ein bod wedi dod o hyd i'r elfen lleiaf, 4, byddwn eisiau
i symud i mewn i'r gyfran datrys y rhestr.
Gan fod hyn yw'r cam cyntaf, mae hyn yn golygu ein bod eisiau rhoi 4 yn
ddechrau'r rhestr.
Ar hyn o bryd 23 yw ar ddechrau'r rhestr, felly
gadewch i ni gyfnewid y 4 a'r 23.
Felly nawr ein rhestr yn edrych fel hyn.
Rydym yn gwybod bod yn rhaid i 4 fod ar ei lleoliad terfynol, oherwydd ei fod yn
yr elfen lleiaf a'r elfen ar y dechrau
y rhestr.
Felly, mae hyn yn golygu nad ydym byth angen i symud eto.
Felly, gadewch i ni ailadrodd y broses hon i ychwanegu elfen arall at y
cyfran datrys y rhestr.
Rydym yn gwybod nad oes angen i ni edrych ar y 4, oherwydd ei fod yn
datrys eisoes.
Felly, gallwn ddechrau ar y 42, y byddwn yn ei gofio fel y
elfen lleiaf.
Felly nesaf, byddwn yn edrych ar y 23 sydd yn llai na 42, felly rydym yn
cofio 23 yw isafswm newydd.
Nesaf rydym yn gweld y 16 sydd i fod yn llai na 23, felly
16 oed yw'r isafswm newydd.
Nawr rydym yn edrych ar y 8 sy'n llai na 16, felly
8 yn yr isafswm newydd.
Ac yn olaf 8 yn llai na 15, felly rydym yn gwybod bod 8 yn o leiaf
elfen heb eu didoli.
Felly mae hynny'n golygu y dylem atodi 8 i ddatrys
gyfran o'r rhestr.
Ar hyn o bryd 4 yw'r elfen didoli yn unig, felly mae arnom eisiau rhoi
nesaf 8 i'r 4.
Ers 42 yn yr elfen gyntaf yn y rhan heb eu didoli y
rhestr, byddwn yn awyddus i gyfnewid y 42 a'r 8.
Felly nawr ein rhestr yn edrych fel hyn.
4 ac 8 yn cynrychioli'r gyfran datrys y rhestr, ac mae'r
niferoedd sy'n weddill yn cynrychioli'r heb eu didoli
gyfran o'r rhestr.
Felly, gadewch i ni barhau â'r fersiwn arall.
Rydym yn dechrau gyda 23 y tro hwn, gan nad oes angen i ni edrych ar
y 4 ac 8 anymore oherwydd maent wedi
eisoes wedi cael ei datrys.
16 yn llai na 23, felly byddwn yn cofio
16 fel yr isafswm newydd.
16 yn llai na 42, ond 15 yn llai na 16, felly mae'n rhaid 15 fod yn
yr elfen heb ei threfnu o leiaf.
Felly, nawr rydym am i gyfnewid y 15 a'r 23 i
yn rhoi i ni y rhestr hon.
Mae'r rhan datrys y rhestr yn cynnwys 4, 8 a 15 oed, a
elfennau hyn yn cael eu heb eu didoli o hyd.
Ond dim ond fel y digwydd bod yr elfen heb ei threfnu nesaf, 16,
cael ei drefnu yn barod.
Fodd bynnag, does dim ffordd ar gyfer ein algorithm i wybod fod 16
eisoes yn ei lleoliad cywir, felly rydym yn dal angen i ni
ailadrodd yn union yr un broses.
Felly rydym yn gweld bod 16 yn llai na 42, a 16 yn llai na 23, felly
16 Rhaid fod yr elfen lleiaf.
Mae'n amhosibl i gyfnewid yr elfen hon gyda ei hun, fel y gallwn
dim ond ei adael yn y lleoliad hwn.
Felly, mae angen pasio un yn fwy o'n algorithm.
42 yn fwy na 23, felly mae'n rhaid i 23 fydd y
elfen lleiaf heb eu didoli.
Unwaith y byddwn yn cyfnewid y 23 a'r 42, rydym yn y pen draw ein terfynol
rhestr datrys -
4, 8, 15, 16, 23, 42.
Rydym yn gwybod bod yn rhaid 42 fod yn y lle cywir gan ei fod yn y
gadael elfen yn unig, ac mae hynny'n fath dethol.
Gadewch i ni bellach yn ffurfioli ein algorithm gyda rhai
pseudocode.
Ar-lein un, gallwn weld bod angen i integreiddio dros
pob elfen o'r rhestr.
Heblaw y elfen olaf, gan fod y elfen 1
rhestr yn cael ei datrys eisoes.
Ar-lein dau, rydym yn ystyried yr elfen gyntaf y heb eu didoli
gyfran o'r rhestr i fod y safon gofynnol, fel y gwnaethom gyda'n
enghraifft, felly mae gennym rywbeth i gymharu.
Llinell tri yn dechrau dolen ail yr ydym yn ailadrodd dros
bob elfen heb eu didoli.
Rydym yn gwybod bod ar ôl i iteriadau, y gyfran didoli
Mae'n rhaid ein rhestr gael i elfennau ynddo gan fod pob cam
fath un elfen.
Felly, mae'n rhaid i'r elfen heb eu didoli cyntaf yn sefyllfa i + 1.
Ar-lein pedwar, rydym yn cymharu yr elfen presennol i'r lleiafswm
elfen yr ydym wedi ei weld hyd yn hyn.
Os yw'r elfen ar hyn o bryd yn llai na'r isafswm
elfen, yna rydym yn cofio yr elfen gyfredol fel newydd
lleiafswm ar-lein pump.
Yn olaf, ar linellau chwech a saith, rydym yn cyfnewid y lleiafswm
elfen sydd â'r elfen heb ei threfnu yn gyntaf, a thrwy hynny
ychwanegu at y gyfran datrys y rhestr.
Unwaith y byddwn wedi algorithm, cwestiwn pwysig i'w ofyn
ein hunain fel rhaglenwyr yn cael ei pa mor hir oedd hynny'n ei gymryd?
Byddwn ofyn yn gyntaf y cwestiwn pa mor hir mae'n ei gymryd ar gyfer y
algorithm i redeg yn yr achos gwaethaf?
Cofio ydym yn eu cynrychioli hon rhedeg
amser gyda mawr O nodiant.
Er mwyn penderfynu ar yr elfen heb ei threfnu isafswm, rydym yn
yn y bôn roedd yn rhaid i gymharu pob elfen yn y rhestr i
pob elfen arall yn y rhestr.
Yn reddfol, mae hyn yn swnio fel O n gweithredu sgwâr.
Edrych ar ein pseudocode, mae gennym hefyd dolen nythu y tu mewn
arall dolen, sydd yn wir yn swnio fel O
o n gweithredu sgwâr.
Fodd bynnag, cofiwch nad oedd angen i ni edrych dros y
rhestr gyfan wrth benderfynu ar yr elfen heb ei threfnu o leiaf?
Unwaith y byddwn yn gwybod bod y 4 gael ei ddatrys, er enghraifft, nid ydym yn gwneud
angen i ni edrych arno eto.
Felly, mae hyn yn is yr amser yn rhedeg?
Ar gyfer ein rhestr o hyd 6, roedd angen i ni gwneud pum
cymariaethau ar gyfer yr elfen gyntaf, pedwar cymariaethau ar gyfer
yr ail elfen, ac yn y blaen.
Mae hynny'n golygu bod y cyfanswm nifer o gamau yn y swm o
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 amserau n
n minws 1 dros 2.
Neu equivalently, n sgwâr dros 2 minws n dros 2.
Wrth sôn am runtime asymptotic, y tymor hwn sgwâr n
yn mynd i dra-arglwyddiaethu y tymor n.
Felly fath dewis yn O o n sgwâr.
Dwyn i gof bod yn ein enghraifft, didoli dewis dal angen i
gwirio os oes nifer cafodd hynny ei ddatrys yn barod
angen eu symud.
Felly mae hynny'n golygu, os ydym yn rhedeg fath ddewis dros eisoes yn
ddidoli rhestr, byddai angen yr un nifer o camau hynny y mae'n
byddai'n rhedeg dros restr gyfan gwbl heb eu didoli.
Felly fath dethol Mae perfformiad achosion gorau o n sgwâr,
yr ydym yn cynrychioli gyda n sgwâr omega.
A dyna ni am y math dethol.
Dim ond un o'r algorithmau llawer y gallwn
defnyddio i ddatrys rhestr.
Fy enw i yw Tommy, ac mae hyn yn cs50.