[Powered by Google Translate] Rydych chi wedi clywed yn ôl pob tebyg mae pobl yn siarad am algorithm gyflym nac yn effeithlon am weithredu eich tasg benodol, ond beth yn union mae'n ei olygu i algorithm i fod yn gyflym nac yn effeithlon? Wel, nid yw'n sôn am fesur mewn amser real, fel eiliadau neu funudau. Mae hyn oherwydd bod caledwedd cyfrifiadurol a meddalwedd yn amrywio yn sylweddol. Efallai fy rhaglen yn rhedeg yn arafach na chi, gan fy mod yn rhedeg ar gyfrifiadur hŷn, neu oherwydd fy mod yn digwydd bod yn chwarae gêm fideo ar-lein ar yr un pryd, sy'n meddiannu'r holl fy nghof, neu efallai y byddaf yn cynnal fy rhaglen trwy feddalwedd gwahanol sy'n cyfathrebu gyda'r peiriant yn wahanol ar lefel isel. Mae fel chymharu afalau ac orennau. Dim ond oherwydd fy nghyfrifiadur arafach cymryd mwy o amser nag un chi i roi yn ôl ateb nid yw'n golygu bod gennych yr algorithm yn fwy effeithlon. 

Felly, gan na allwn uniongyrchol gymharu runtimes o raglenni mewn eiliadau neu funudau, sut rydym yn cymharu 2 algorithmau gwahanol waeth beth yw eu caledwedd neu feddalwedd amgylchedd? Er mwyn creu ffordd fwy unffurf o fesur effeithlonrwydd algorithmig, gwyddonwyr cyfrifiadurol a mathemategwyr wedi dyfeisio cysyniadau ar gyfer mesur cymhlethdod asymptotic o raglen a nodiant o'r enw 'Ohnotation Mawr' ar gyfer disgrifio hyn. Mae'r diffiniad ffurfiol yw bod y ffwythiant f (x) yn rhedeg ar y drefn g (x) os oes yn bodoli rhywfaint o werth (x), x ₀ a rhai cyson, C, y f (x) yn llai na neu'n hafal i bod yn gyson weithiau g (x) ar gyfer pob x yn fwy na x ₀. 

Ond peidiwch â bod ofn i ffwrdd gan y diffiniad ffurfiol. Beth mae hyn mewn gwirionedd yn ei olygu yn llai termau damcaniaethol? Wel, yn y bôn yn ffordd o ddadansoddi pa mor gyflym runtime rhaglen yn tyfu asymptotically. Hynny yw, gan fod y maint eich mewnbwn yn cynyddu tuag at anfeidredd, ddweud, eich bod yn didoli amrywiaeth o faint 1,000 o'i gymharu â amrywiaeth o faint 10. Sut mae'r Rhedeg eich rhaglen yn tyfu? Er enghraifft, dychmygwch cyfrif y nifer o gymeriadau mewn llinyn y ffordd symlaf  trwy gerdded trwy'r llinyn cyfan llythyr-by-lythyr ac ychwanegu 1 at cownter ar gyfer pob cymeriad. Mae'r algorithm yn cael ei ddweud i redeg mewn amser llinol mewn perthynas â nifer o gymeriadau, 'N' yn y llinyn. Yn fyr, mae'n rhedeg yn O (n). Pam fod hyn? Wel, gan ddefnyddio'r dull hwn, yr amser sydd ei angen i groesi'r llinyn cyfan yn gymesur â nifer o gymeriadau. Cyfrif y nifer o gymeriadau mewn llinyn 20-cymeriad yn mynd i cymryd dwywaith cyhyd ag y mae'n ei gymryd i gyfrif y cymeriadau mewn llinyn 10-gymeriad, oherwydd bod yn rhaid i chi edrych ar yr holl gymeriadau ac mae pob cymeriad yn cymryd yr un faint o amser i edrych ar. Wrth i chi gynyddu nifer y cymeriadau, Bydd y runtime cynyddu llinol gyda hyd mewnbwn. 

Nawr, dychmygwch os byddwch yn penderfynu bod amser llinol, O (n), nid yn unig oedd yn ddigon cyflym i chi? Efallai eich bod yn storio llinynnau enfawr, ac ni allwch fforddio'r amser ychwanegol y byddai'n ei gymryd i deithio ar draws eu holl gymeriadau cyfrif un-wrth-un. Felly, byddwch yn penderfynu i roi cynnig ar rywbeth gwahanol. Beth os ydych yn digwydd i eisoes yn storio nifer y nodau yn y llinyn, dyweder, mewn newidyn a elwir yn 'Len,' yn gynnar yn y rhaglen, cyn i chi storio hyd yn oed y cymeriad cyntaf yn eich llinyn? Yna, mae pob byddai'n rhaid i chi ei wneud yn awr i ddarganfod hyd llinyn, yw gwirio beth yw gwerth y newidyn yn. Ni fyddai rhaid i chi edrych ar y llinyn ei hun o gwbl, a chael gafael ar y gwerth newidyn fel Len yn cael ei ystyried llawdriniaeth amser asymptotically gyson, neu O (1). Pam fod hyn? Wel, cofio beth cymhlethdod asymptotic olygu. Sut mae'r newid runtime gan fod maint eich mewnbwn yn tyfu? 

Dywedwch eich bod chi yn ceisio cael y nifer o gymeriadau mewn llinyn mwy. Wel, ni fyddai ots pa mor fawr ydych yn gwneud y llinyn, hyd yn oed filiwn nod o hyd, bob byddai'n rhaid i chi ei wneud i ddod o hyd i hyd y llinyn gyda dull hwn, yw darllen y gwerth y len amrywiol, a wnaethoch eisoes. Mae'r, hyd mewnbwn hynny yw, hyd y llinyn ydych yn ceisio dod o hyd, nid yw'n effeithio o gwbl pa mor gyflym eich rhaglen yn rhedeg. Byddai hyn yn rhan o'ch rhaglen yn rhedeg yr un mor gyflym ar linyn un cymeriad a llinyn mil-gymeriad, a dyna pam y byddai hyn rhaglen yn cael ei gyfeirio ato fel rhedeg mewn amser cyson mewn perthynas â maint y mewnbwn. 

Wrth gwrs, mae yna anfantais. Byddwch yn treulio o le cof ychwanegol ar eich cyfrifiadur storio y newidyn a'r amser ychwanegol y mae'n ei gymryd i chi i wneud y storio gwirioneddol y newidyn, ond mae'r pwynt yn dal i sefyll, darganfod pa mor hir eich llinyn yn nid yw'n dibynnu ar hyd y llinyn o gwbl. Felly, mae'n rhedeg yn O (1) neu amser cyson. Mae hyn yn sicr nid o reidrwydd yn golygu bod eich cod yn rhedeg mewn 1 cam, ond ni waeth faint o gamau y mae, os nad yw'n newid gyda maint y mewnbynnau, mae'n dal i fod asymptotically gyson yr ydym yn eu cynrychioli fel O (1). 

Fel mae'n debyg y gallwch ddyfalu, mae yna nifer o wahanol runtimes O mawr i fesur algorithmau â hwy. O (n) ² algorithmau yn asymptotically arafach na O (n) algorithmau. Hynny yw, gan fod nifer o elfennau (n) yn tyfu, yn y pen draw bydd O (n) ² algorithmau yn cymryd mwy o amser na O (n) algorithmau i redeg. Nid yw hyn yn golygu O (n) algorithmau bob amser yn rhedeg yn gyflymach na O (n) ² algorithms, hyd yn oed yn yr un amgylchedd, ar yr un caledwedd. Efallai ar gyfer meintiau mewnbwn bach,  gallai'r O (n) ² algorithm yn gweithio mewn gwirionedd yn gyflymach, ond, yn y pen draw, gan fod maint yn cynyddu mewnbwn tuag at anfeidredd, y (n) O runtime ² algorithm yn yn y pen draw Eclipse y runtime y algorithm O (n). Yn union fel unrhyw swyddogaeth mathemategol gwadratig  yn y pen draw goddiweddyd unrhyw swyddogaeth llinellol, ni waeth faint o pen gychwyn y swyddogaeth llinellol yn dechrau i ffwrdd gyda. Os ydych chi'n gweithio gyda symiau mawr o ddata, algorithmau sy'n rhedeg yn O (n) y gall ² amser mewn gwirionedd yn y pen draw arafu eich rhaglen, ond ar gyfer meintiau mewnbwn bach, mae'n debyg na fydd hyd yn oed yn sylwi. 

Arall cymhlethdod asymptotic yw, amser logarithmig, O (n log). Un enghraifft o algorithm sy'n rhedeg hyn yn gyflym yw'r algorithm chwilio deuaidd clasurol, gyfer dod o hyd elfen mewn rhestr eisoes wedi ei ddidoli o elfennau. 

Os nad ydych yn gwybod pa chwiliad deuaidd yn ei wneud, 'N annhymerus' esbonio i chi yn gyflym iawn. Dewch i ddweud eich bod yn chwilio am y rhif 3 yn y amrywiaeth o gyfanrifau. Mae'n edrych ar yr elfen ganol y rhesi ac yn gofyn, "A yw'r elfen rwyf am fwy na, hafal i, neu'n llai na hyn?" Os yw'n gyfartal, yna fawr. Byddwch yn dod o hyd i'r elfen, ac rydych yn ei wneud. Os yw'n fwy, yna rydych yn gwybod yr elfen rhaid iddo fod yn yr ochr dde y rhesi, a gallwch edrych yn unig ar hynny yn y dyfodol, ac os yw'n llai, yna rydych yn gwybod mae'n rhaid iddo fod yn yr ochr chwith. Ailadroddir y broses hon wedyn gyda'r amrywiaeth llai faint hyd nes yr elfen gywir yn cael ei ganfod. 

Mae'r algorithm pwerus yn torri'r maint amrywiaeth yn hanner gyda pob gweithrediad. Felly, i ddod o hyd i elfen mewn arae datrys o faint 8, ar y mwyaf (logio ₂ 8), neu 3 o'r gweithrediadau hyn, Bydd yr elfen gwirio canol, yna torri'r amrywiaeth yn ei hanner yn cael ei angen, tra bod amrywiaeth o maint 16 yn cymryd (logio ₂ 16), neu 4 gweithrediadau. Dyna dim ond 1 gweithrediad mwy o amrywiaeth dyblu-maint. Ddyblu maint y rhesi cynyddu'r runtime gan dim ond 1 darn o cod hwn. Unwaith eto, gwirio elfen ganol y rhestr, yna hollti. Felly, dywedir i weithredu mewn amser logarithmig, O (n log). Ond arhoswch, y dywedwch, Nid yw hyn yn dibynnu ar ble yn y rhestr yr elfen rydych yn chwilio amdano yw? Beth os bydd yr elfen gyntaf ydych yn edrych ar digwydd i fod yn yr un cywir? Yna, dim ond yn cymryd 1 gweithrediad, ni waeth pa mor fawr yw'r rhestr yn. 

Wel, dyna pam mae gwyddonwyr cyfrifiadurol delerau mwy ar gyfer cymhlethdod asymptotic sy'n adlewyrchu orau-achos a gwaethaf perfformiadau o algorithm. Yn fwy priodol, y terfynau uchaf ac isaf ar y runtime. Yn yr achos gorau ar gyfer chwiliad deuaidd, ein elfen yn iawn yno yn y canol, a byddwch yn ei gael mewn pryd yn gyson, ni waeth pa mor fawr yw'r gweddill y rhesi yn. Y symbol a ddefnyddir ar gyfer hyn yw Ω. Felly, mae'r algorithm yn cael ei ddweud i redeg yn Ω (1). Yn yr achos gorau, mae'n dod o hyd i'r elfen yn gyflym, ni waeth pa mor fawr yr amrywiaeth yw, ond yn yr achos gwaethaf, mae'n rhaid iddo berfformio (log n) gwiriadau rhannu y rhesi i ddod o hyd i'r elfen cywir. Ffiniau gwaethaf uchaf yn cael eu cyfeirio at y mawr "O" eich bod eisoes yn gwybod. Felly, mae'n O (log n), ond Ω (1). 

Mae chwiliad llinol, ar y llaw arall, yr ydych yn cerdded drwy bob elfen o'r rhesi i ddod o hyd i'r un yr ydych ei eisiau, ar Ω gorau (1). Unwaith eto, yr elfen gyntaf i chi ei eisiau. Felly, nid oes ots pa mor fawr yw'r casgliad yn. Yn yr achos gwaethaf, mae'n elfen olaf yn y casgliad. Felly, rhaid i chi gerdded drwy'r holl elfennau n yn yr amrywiaeth o hyd iddi, yn hoffi pe baech yn edrych am 3. Felly, mae'n rhedeg mewn amser O (n) oherwydd ei fod yn gymesur â nifer o elfennau yn y rhesi. 

Un symbol mwy a ddefnyddir yn Θ. Gall hyn gael ei ddefnyddio i ddisgrifio algorithmau lle yr achosion gorau a gwaethaf yr un fath. Mae hyn yn wir yn y algorithmau llinyn-hyd buom yn siarad am gynharach. Hynny yw, os ydym yn ei storio mewn newidyn cyn byddwn yn storio y llinyn a chael mynediad iddo yn ddiweddarach mewn amser cyson. Ni waeth pa rif rydym yn storio yn y newidyn, bydd rhaid i ni edrych arno. Mae'r achos gorau yw, yr ydym yn edrych arno a darganfyddwch hyd y llinyn. Felly Ω (1) neu orau-achos cysonyn amser. Mae'r achos gwaethaf yw, rydym yn edrych arno ac yn dod o hyd i hyd y llinyn. Felly, O (1) neu amser cyson yn achos gwaethaf. Felly, gan fod yr achos gorau ac achosion gwaethaf yr un fath, gall hyn fod yn dweud i redeg mewn amser Θ (1). 

I grynhoi, mae gennym ffyrdd da o reswm am godau effeithlonrwydd heb wybod dim am y tro byd go iawn yn eu cymryd i redeg, sy'n cael ei heffeithio gan nifer o ffactorau y tu allan, gan gynnwys caledwedd gwahanol, meddalwedd, neu fanylion eich cod. Hefyd, mae'n ein galluogi i resymu yn dda am beth fydd yn digwydd pan fydd maint y cynnydd mewnbynnau. 

Os ydych yn rhedeg yn O (n) ² algorithm, neu waeth, a O (2 ⁿ) algorithm, un o'r mathau sy'n tyfu gyflymaf, byddwch chi wir yn dechrau sylwi ar yr arafu pan fyddwch yn dechrau gweithio gyda symiau mwy o ddata. 

Dyna cymhlethdod asymptotic. Diolch.