[Muzika] DOUG LLOYD: Linear Kërkimi është një algoritmi ne mund të përdorni për të gjetur një element në një rrjet. Një risjell algoritëm është një grup hap-pas-hapi Udhëzimet për plotësimin e një detyre. 

Kërkimi lineare algorithm punon si vijon. Iterate nëpër rrjet nga e majta në të e drejtë, duke kërkuar për një element të caktuar. 

Në pseudokod, e cila është më e version i distiluar i këtij dënimi, elementi i parë në qoftë se është ajo ju jeni duke kërkuar për të, ju mund të ndalojë. Përndryshe, të shkojë në elementin e ardhshëm dhe do të mbajë mbi dhe mbi derisa ju të gjeni element, ose ju nuk e bëni. Kështu që ne mund të përdorni lineare Kërkimi algorithm, për shembull, për të gjetur vlerën e synuar nëntë në këtë grup. E pra ne të fillojë në fillim. Në qoftë se kjo është ajo që ne jemi në kërkim të, ne mund të ndalet. Kjo nuk është, ne nuk jemi duke kërkuar për 11. Pra ndryshe, të shkojë në elementin e ardhshëm. 

Pra, ne shikojmë në 23. Është 23 atë që ne jemi duke kërkuar për? E pra jo, kështu që ne të lëvizin në të ardhshëm element, dhe element tjetër, dhe do të vazhdojmë duke shkuar nëpër ky proces pa pushim dhe mbi, deri ne toke në një situatë si kjo. 

Nëntë është ajo që ne jemi duke kërkuar për, dhe ky element i vektorit është, kjo është vlerë është nëntë. Dhe kështu kemi gjetur atë që ne jemi kërkoni, dhe ne mund të ndalet. Kërkimi lineare ka përfundoi, me sukses. 

Por ajo që për në qoftë se ne jemi duke kërkuar për një element që nuk është në rrjet tonë. A kërkimit linear ende punë? Edhe i sigurt. Pra, ne përsëris këtë proces duke filluar në elementin e parë. Në qoftë se kjo është ajo që ne jemi në kërkim të, ne mund të ndalet. Nuk eshte. Përndryshe, ne shkojmë në elementin e ardhshëm. 

Por ne mund të mbani përsëritur këtë proces, shqyrtuar çdo element nga ana tjetër, duke shpresuar se ne gjejmë numrin 50. Por ne nuk do të dimë nëse ne kemi gjetur numrin 50 ose në qoftë se ne nuk e bëri, deri sa ne kemi rritur mbi çdo element të vetëm të vektorit. 

Vetëm një herë ne kemi bërë se dhe ardhur deri të shkurtër, mund të arrijmë në përfundimin se 50 nuk eshte ne vektorit. Dhe kështu Kërkimi lineare algorithm, edhe ajo nuk arriti, në vetvete. Por jo në kuptimin se ajo ishte i pasuksesshëm në duke bërë atë kemi kërkuar atë për të bërë. 

Ajo ishte i pasuksesshëm në si më shumë që ajo nuk ka gjetur 50, por 50 nuk ishte në rrjet. Por ne kemi kërkuar në mënyrë shteruese përmes çdo element të vetme dhe kështu, ndërsa ne nuk ka gjetur çdo gjë, kërko lineare ende pason edhe nëse element nuk është në vektorit. 

Pra, çfarë është rasti më i keq Skenari me kërkim linear? E pra ne duhet të shohim përmes çdo element i vetëm, ose për shkak se elementi objektiv është elementi i fundit i vektorit, ose elementi ne jemi duke kërkuar për nuk ka në fakt ekzistojnë në rrjet në të gjitha. Çfarë është skenari më i mirë? Edhe ne mund të gjeni element menjëherë. Dhe sa elemente nuk kemi atëherë duhet të shohim në në rastin më të mirë, në qoftë se ne jemi duke kërkuar për të dhe ne gjejmë atë në fillim? Ne mund të ndalet menjëherë. 

Çfarë do të thotë kjo në lidhje me Kompleksiteti i kërkimit lineare? Edhe në rastin më të keq, ne kemi për të parë në çdo element të vetëm. Dhe kështu ajo shkon në O e n, në rastin më të keq. 

Në rastin më të mirë, ne jemi gonna të gjeni elementin menjëherë. Dhe kështu shkon në omega e 1. 

Unë jam Doug Lloyd. Kjo është CS50.