[Musiikkia] DOUG Lloyd: Lineaarinen haku on algoritmi me voi käyttää löytää elementti array. Algoritmi Recall on askel-askeleelta sarja ohjeisto valmiiksi tehtävän. 

Lineaarinen haku Algoritmi toimii seuraavasti. Kerrata rivin poikki vasemmalta oikea, etsivät tietyn elementin. 

Pseudokoodilla, joka on enemmän tislattua versio tämän lauseen, jos ensimmäinen elementti on mitä etsit, voit lopettaa. Muuten, siirtyä seuraavaan elementtiin ja jatkaa yhä kunnes löydät elementti, tai et. Joten voimme käyttää lineaarinen hakualgoritmi, esimerkiksi, löytää tavoitearvo yhdeksän tässä array. No me aloittaa alusta. Jos se mitä olemme etsivät, voimme lopettaa. Se ei ole, emme ole etsimässä 11. Niin muuten, siirry seuraavaan elementtiin. 

Joten katsomme 23. On 23, mitä etsimme? No ei, joten siirrymme seuraavaan elementti, ja seuraava osa, ja pidämme läpi tämä prosessi uudestaan ​​ja uudestaan ja yli, kunnes laskeudumme on tällainen tilanne. 

Yhdeksän on mitä etsimme, ja tämä alkio on, se arvo on yhdeksän. Ja niin löysimme mitä olemme etsivät, ja voimme lopettaa. Lineaarinen haku on suoritettu onnistuneesti. 

Mutta entä jos me etsimme elementti, joka ei ole meidän array. Onko lineaarinen haku silti toimia? Hyvin varma. Joten me toista tämä prosessi alkaen ensimmäinen elementti. Jos se mitä olemme etsivät, voimme lopettaa. Ei ole. Muuten, siirrymme seuraavaan elementtiin. 

Mutta voimme pitää toistaa tätä prosessia, tutkii jokaisen elementin puolestaan toivoen, että löydämme numero 50. Mutta emme tiedä, olemme löytäneet numero 50 tai jos emme, ennen kuin olemme astui yli jokainen alkio. 

Vasta kun olemme tehneet että ja keksiä lyhyt, voimme päätellä, että 50 ei ole jono. Ja niin lineaarinen haku algoritmi, hyvin se epäonnistui, sinänsä. Mutta ei siinä mielessä, että se ei onnistunut tekemään mitä pyysimme sitä tekemään. 

Se ei onnistunut, koska paljon kuin se ei löytänyt 50, mutta 50 ei ollut jono. Mutta olemme tyhjentävästi etsinyt läpi jokaisen elementin ja niin, vaikka emme löytäneet mitään, lineaarinen haku yhä onnistuu vaikka elementti ei ole jono. 

Niin mitä pahimmassa tapauksessa skenaario, jossa lineaarinen haku? No meidän täytyy käydä läpi jokainen elementti, joko siksi kohdistuselementti on viimeinen osa array, tai elementti etsimme ei todella olemassa joukko lainkaan. Mikä on parhaassa tapauksessa? No voisimme löytää elementti välittömästi. Ja kuinka monta elementtiä meillä sitten on tarkasteltava klo parhaassa tapauksessa, jos etsimme sitä ja pidämme aivan alussa? Voimme lopettaa välittömästi. 

Mitä tämä sanottavaa monimutkaisuus lineaarinen haku? Hyvin pahimmassa tapauksessa olemme katsomaan jokaisen elementin. Ja niin se toimii O n, pahimmassa tapauksessa. 

Parhaassa tapauksessa aiomme löytää elementti välittömästi. Ja niin toimii omega 1. 

Olen Doug Lloyd. Tämä on CS50.