[Music kucheza] DOUG LLOYD: Linear search ni algorithm sisi unaweza kutumia ili kupata kipengele katika safu. Wanakumbuka algorithm ni hatua kwa hatua ya kuweka maelekezo kwa ajili ya kukamilisha kazi. 

Tafuta linear algorithm kazi kama ifuatavyo. Iterate hela safu kutoka kushoto kwenda haki, kuangalia kwa kipengele maalum. 

Katika pseudocode, ambayo ni zaidi distilled toleo la hukumu hii, kama kitu cha kwanza ni kile wewe kutafuta, unaweza kuacha. Vinginevyo, hoja ya kipengele ijayo na kuendelea tena na tena mpaka kupata kipengele, au huna. Ili tuweze kutumia linear search algorithm, kwa mfano, kupata thamani Lengo tisa katika safu hii. Naam sisi kuanza mwanzoni. Kama ni nini tuko kutafuta, tunaweza kuacha. Siyo, sisi siyo kuangalia kwa 11. Hivyo vinginevyo, hoja ya kipengele ijayo. 

Hivyo sisi kuangalia 23. Ni 23 nini sisi ni kuangalia kwa? Naam hakuna, hivyo sisi kuhamia kwenye ijayo kipengele, na kipengele ijayo, na sisi kuendelea kwenda kwa mchakato huu tena na tena na tena, mpaka sisi ardhi juu ya hali kama hii. 

Tisa ni nini sisi ni kuangalia kwa, na kipengele hiki cha safu yaani, thamani yake ni tisa. Na hivyo sisi kupatikana nini tuko kutafuta, na tunaweza kuacha. Tafuta linear ina kukamilika, kwa mafanikio. 

Lakini nini kuhusu kama sisi ni kuangalia kwa kipengele kwamba si katika safu yetu. Je, linear la bado kazi? Naam uhakika. Kwa hiyo sisi kurudia utaratibu huu kuanzia saa kipengele kwanza. Kama ni nini tuko kutafuta, tunaweza kuacha. Sio. Vinginevyo, sisi hoja ya kipengele ijayo. 

Lakini tunaweza kuendelea kurudia utaratibu huu, kuchunguza kila kipengele kwa upande wake, matumaini kwamba sisi kupata idadi 50. Lakini hatutaweza kujua kama tumekuwa kupatikana idadi 50 au kama hatukuwa, mpaka tumekuwa kupitiwa juu ya kila kipengele moja ya safu. 

Tu mara moja tumefanya kuwa na kuja mfupi, Tunaweza kuhitimisha kwamba 50 siyo katika safu. Na hivyo tafuta linear algorithm, vizuri alishindwa, per se. Lakini si kwa maana kwamba hakufaulu katika kufanya yaliyo sisi aliuliza kufanya. 

Ilikuwa ni aliyeshindwa katika kama vile ni hawakuona 50, lakini 50 hakuwa katika safu. Lakini sisi vyema msako kupitia kila kipengele moja na hivyo, wakati sisi hawakuona kitu chochote, tafuta linear bado inafanikiwa hata kama kipengele ni si katika safu. 

Basi nini hali mbaya mazingira na tafuta linear? Vizuri inabidi kuangalia njia kila kipengele moja, ama kwa sababu lengo kipengele ni kipengele mwisho wa safu, au kipengele sisi ni kuangalia kwa hana kweli zipo katika safu wakati wote. Nini bora kesi mazingira? Naam tunaweza kukuta kipengele mara moja. Na jinsi mambo mengi Je, sisi kisha kuwa na kuangalia katika katika kesi bora, kama sisi ni kuangalia kwa ajili yake na tunapata ni mwanzoni kabisa? Tunaweza kuacha mara moja. 

Je, hii inasema nini kuhusu utata wa tafuta linear? Vizuri katika hali mbaya zaidi, tuna kuangalia kila kipengele moja. Na hivyo ni anaendesha katika O wa n, katika hali mbaya zaidi. 

Katika kesi bora, sisi ni gonna kupata kipengele mara moja. Na hivyo anaendesha katika omega ya 1. 

Mimi nina Doug Lloyd. Hii ni CS50.