[CHWARAE CERDDORIAETH] DOUG LLOYD: Llinol Chwilio yn rydym algorithm Gall eu defnyddio i ddod o hyd elfen mewn arae. Adalw algorithm yn set cam-wrth-gam o gyfarwyddiadau am gwblhau tasg. 

Mae'r chwiliad llinol algorithm yn gweithio fel a ganlyn. Ailadrodd ar draws yr amrywiaeth o'r chwith i'r gywir, yn chwilio am elfen benodol. 

Yn pseudocode, sydd yn fwy Fersiwn ddistyllu y frawddeg hon, os yw'r elfen gyntaf yw'r hyn rydych chi'n chwilio amdano, gallwch roi'r gorau. Fel arall, yn symud i'r elfen nesaf ac dal i fynd drosodd a throsodd nes i chi ddod o hyd yr elfen, neu os nad ydych yn ei wneud. Felly, gallwn ddefnyddio'r llinellol Chwilio algorithm, er enghraifft, i ddarganfod gwerth targed naw o amrywiaeth hwn. Wel, rydym yn dechrau ar y dechrau. Os yw'n hyn yr ydym ni'n chwilio am, gallwn roi'r gorau iddi. Dyw hi ddim yn, rydym yn nad ydynt yn chwilio am 11. Felly fel arall, symud ymlaen i'r elfen nesaf. 

Felly, rydym yn edrych ar 23. A yw 23 yr hyn rydym yn chwilio amdano? Wel na, felly rydym yn symud ymlaen at y nesaf elfen, a'r elfen nesaf, ac rydym yn cadw mynd drwy'r y broses hon drosodd a throsodd a throsodd, hyd nes y byddwn tir ar sefyllfa fel hyn. 

Naw yw'r hyn yr ydym yn chwilio amdano, ac yr elfen hon o'r amrywiaeth yw, 'i' gwerth yn naw. Ac felly rydym yn dod o hyd i hyn yr ydym ni'n chwilio am, a gallwn stopio. Mae'r chwiliad llinol wedi gwblhau, yn llwyddiannus. 

Ond beth am os ydym yn chwilio am elfen sydd ddim sydd yn ein casgliad. A yw chwilio llinol yn dal i weithio? Wel yn sicr. Felly, rydym yn ailadrodd y broses hon gan ddechrau yn yr elfen gyntaf. Os yw'n hyn yr ydym ni'n chwilio am, gallwn roi'r gorau iddi. Nid yw'n. Fel arall, byddwn yn symud at yr elfen nesaf. 

Ond gallwn gadw ailadrodd y broses hon, archwilio pob elfen yn ei dro, gan obeithio y byddwn yn dod o hyd i'r rhif 50. Ond ni fyddwn yn gwybod os rydym wedi dod o hyd i'r rhif 50 neu os nad ydym yn gwneud, nes ein bod wedi camu dros bob elfen unigol y rhesi. 

Dim ond ar ôl i ni wedi ei wneud hynny ac yn dod i fyny byr, gallwn ddod i'r casgliad bod 50 Nid yw yn y rhesi. Ac felly y chwiliad llinol algorithm, dda y mae'n methu, fel y cyfryw. Ond nid yn yr ystyr ei fod yn aflwyddiannus wrth wneud yr hyn y roeddem wedi gofyn iddo ei wneud. 

Roedd yn aflwyddiannus mewn fel gymaint ag nad oedd yn dod o hyd i 50, ond nid oedd yn 50 y rhesi. Ond rydym wedi chwilio yn drwyadl trwy bob elfen unigol ac felly, er ein bod nid oedd yn dod o hyd unrhyw beth, chwilio llinol yn dal i yn llwyddo hyd yn oed os y Nid yw elfen yn y rhesi. 

Felly beth yw'r achos gwaethaf senario gyda chwiliad llinol? Wel mae'n rhaid i ni edrych drwy pob un elfen, naill ai oherwydd yr elfen targed yw elfen olaf y rhesi, neu os nad yw'r elfen rydym yn chwilio am ei wneud yn bodoli mewn gwirionedd yn y rhesi o gwbl. Beth yw'r senario achos gorau? Wel efallai y byddwn yn dod o hyd i'r Elfen ar unwaith. Sut a elfennau o ydym wedyn yn rhaid inni edrych yn yn yr achos gorau, os ydym yn chwilio amdano ac yr ydym yn dod o hyd iddo ar y cychwyn cyntaf? Gallwn roi'r gorau ar unwaith. 

Beth mae hyn yn ei ddweud am y cymhlethdod chwilio llinellol? Wel yn yr achos gwaethaf, mae gennym i edrych ar bob elfen unigol. Ac felly mae'n rhedeg yn y O o n, yn yr achos gwaethaf. 

Yn yr achos gorau, rydym yn gonna ddod o hyd i'r elfen ar unwaith. Ac felly yn rhedeg mewn omega o 1. 

Rwy'n Doug Lloyd. Mae hyn yn CS50.