Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Kërko Linear]
[Patrick Schmid, Universiteti i Harvardit]
[Kjo është CS50.] [CS50.TV]
Kërkuar është diçka që ju ndoshta bëni më shpesh se ju mendoni.
Natyrisht, çdo herë që të hapë një shfletues web
dhe kërkoni për një faqe web -
ose kërkoni për miqtë tuaj në faqen tuaj të preferuar social networking -
ju jeni në kërkim.
Por kjo është vetëm një pjesë e vogël e kërkimit që ju bëni në baza ditore.
Kur ju dëshironi të gjeni se një këmishë blu në dollap,
ose bluzë të kuqe e përkryer për rastin,
ju jeni në kërkim.
Kur ju shkoni në një dyqan që ju kurrë nuk kam qenë me parë,
dhe ju jeni duke kërkuar për brokoli në rresht të prodhuar
ju jeni në kërkim.
Çfarë ju mund të keni filluar të njoftimit
është se në varësi të asaj që ju jeni duke kërkuar për
ose si objekte janë të organizuar, kur ju jeni duke kërkuar për ta
ajo ka një efekt mbi se si ju kërkoni.
Për shembull, nëse këmisha e tua janë të varur në dollap,
ju ndoshta mund të marr vetëm atë pa shumë kërkim.
Nëse ju jeni duke supozuar që ju keni për të ecin poshtë rresht
për të marrë brokoli, ju ndoshta duhet të shikoni në të gjitha perimet e tjera
para se ju të gjeni se brokoli.
Kërko linear është një shembull i një metode të tillë - ose në kërkim algorithm.
Si emri nënkupton,
kjo metodë kërkon për një artikull në një mënyrë lineare, njëri pas tjetrit.
Pra, kur ju jeni duke kërkuar në rezultatet nga favorite search engine tuaj
dhe ju lexoni poshtë listën e rezultateve,
ju jeni duke përdorur kërkimin lineare.
Rregull. Le të shikojmë një shembull.
Thonë se ne kemi një listë të numrave - 2, 4, 0, 5, 3, 7, 8, dhe 1 -
dhe ne jemi duke kërkuar për numrin 0.
Natyrisht, ju thjesht mund të shihni se 0 është në pozitën e tretë.
Por, një program kompjuteri nuk është se fat.
Ajo vetëm mund të "shohin" një numër në një kohë.
Kështu, duke filluar në fillim të listës,
ajo vetëm "sheh" 2.
Programi pastaj kontrollon - është e barabartë me 2 0?
Natyrisht jo. Pra, ajo shkon për në numrin e ardhshëm, 4.
A 4 0 barabarta? Jo.
Një tjetër, 0. Ah! Zero është e barabartë me 0.
Nuk kemi atë! Kjo është në pozitën e tretë.
Rregull. Le të shikojmë në disa pseudokod.
Kjo është vetëm një çift i linjave të gjata, por le të shohim në atë një linjë në një kohë.
Së pari, le të përcaktojmë funksionin - dhe ne jemi duke shkuar për të thirrur të kërkimit lineare -
dhe ajo merr dy argumente - kyç dhe koleksion.
Çelësi është se vlera që ne jemi duke kërkuar për të,
kështu në shembullin e mëparshëm, që ishte zero.
Një grup është një listë të numrave të
që i ka të gjitha vlerat që ne jemi duke shkuar për të kërkuar.
Pra, ajo që ne duam të bëjmë është që ne duam të shikojmë në -
nga të gjitha pozitat, kështu që duke filluar në fillim të array
til fund të array - kështu gjatësinë e vektorit -
shikojmë në çdo pozicion të vetme dhe të kontrolloni çdo një të tillë.
Pra, kjo është ajo që që "për" loop është duke bërë.
Dhe në çdo pozicion, ne jemi duke shkuar për të thënë
"A është se vlera në atë pozicionin aktual të barabartë me kyç që ne jemi duke kërkuar për të?"
Pra, - në shembullin e mëparshëm përsëri, kyç ishte 0 -
kështu që ne jemi duke thënë se "është array në pozicionin i barabartë me zero?"
Në qoftë se ajo është, ne jemi duke shkuar për të kthyer 'i', sepse kjo është pozicioni aktual ne jemi në.
Kështu, në shembull të mëparshëm,
që ishte pozita e tretë.
Në qoftë se ne kemi kaluar nëpër rrjet të tërë
dhe ne nuk kemi gjetur asgjë -
kështu që le të themi që ne ishim në kërkim për numrin 500
të cilat në mënyrë të qartë nuk ishte në atë shembull -
ne kemi për t'u kthyer diçka,
dhe ne jemi duke shkuar për t'u kthyer -1.
Dhe ne jemi vetëm kthyer -1, sepse kjo është një pozicion
që nuk ekzistojnë në rrjet.
Dhe kështu që do të thotë kur ju merrni atë nga një funksion
ai thotë se "Hmm, okay. unë mendoj unë nuk kam gjetur asgjë.
Kështu që asnjëherë nuk ishte atje 500. "
Gjë e bukur për kërkim linear është se
ajo do të punojë në çdo listë të sendeve,
pavarësisht se si sendet janë të urdhëruar.
Kjo nuk ka rëndësi se ku brokoli është në rresht të prodhuar.
Për aq kohë sa ju ecni nëpër pjesë nga fillimi deri në fund,
ju jeni i detyruar për të gjetur atë,
supozuar dyqan nuk e ka drejtuar nga e brokoli, natyrisht.
Por fuqia është e madhe është edhe dobësia është e madhe.
Thonë se ju keni një listë të numrave dyqind
që janë të renditura 1-200.
Nëse jeni duke kërkuar për numrin 198,
ju duhet të kërkoni pothuajse tërë listën e numrave
para se ju të gjeni një që ju po kërkoni.
Nuk duhet të jetë një mënyrë më të mirë!
Pjesa tjetër e siguroi se ka.
Por, kjo është një temë për një tjetër video.
Gjithashtu, nuk e prish qejfin!
Vetëm për shkak se kërko lineare nuk është zgjidhja më e mirë në të gjitha situatat,
kjo nuk do të thotë se ajo nuk do të jetë në dispozicion.
Përndryshe, si do ta gjeni se brokoli në rresht të prodhuar?
Emri im është Patrick Schmid, dhe kjo është CS50.
[CS50.TV]