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