[MUSIC SPILLE] DOUG LLOYD: Linear søk er en algoritme vi kan bruke for å finne et element i en matrise. En algoritme tilbakekalling er en steg-for-steg sett instruks for å fullføre en oppgave. 

Den lineære søk algoritmen virker som følger. Iterere over rekken fra venstre til høyre, på jakt etter en bestemt element. 

I pseudokode, som er en mer destillert versjon av denne setningen, hvis det første element er hva du leter etter, kan du stoppe. Ellers gå til neste element og holde går om og om igjen til du finner elementet, eller du ikke. Så vi kan bruke den lineære søkealgoritme, for eksempel, for å finne målverdien ni i denne matrisen. Vel skal vi begynne på begynnelsen. Hvis det er det vi er på jakt etter, kan vi stoppe. Det er ikke, vi er ikke ute etter 11. Så ellers, gå til neste element. 

Så vi ser på 23. Er 23 det vi leter etter? Vel nei, så vi går videre til neste element, og det neste element, og vi holder det gående gjennom denne prosessen igjen og igjen og over, før vi lander på en situasjon som dette. 

Ni er det vi leter etter, og dette element i matrisen er, er det verdi ni. Og så fant vi hva vi er på jakt etter, og vi kan stoppe. Den lineære søk har fullført, med hell. 

Men hva hvis vi leter etter et element som ikke er i vårt utvalg. Betyr lineær søke fortsatt fungere? Vel sikker. Så vi gjentar denne prosessen starter ved det første elementet. Hvis det er det vi er på jakt etter, kan vi stoppe. Det er ikke. Ellers flytter vi til neste element. 

Men vi kan terpe denne prosessen, undersøke hvert element i sin tur håper at vi finner nummer 50. Men vi vil ikke vite om vi har funnet nummeret 50 eller hvis vi ikke gjorde det, før vi har trappet i løpet av hvert enkelt element i gruppen. 

Bare når vi har gjort det og komme opp kort, kan vi konkludere med at 50 er ikke i matrisen. Og så den lineære søk algoritme, vel det mislyktes, per se. Men ikke i den forstand at den var mislykket i å gjøre det vi spurte den å gjøre. 

Det var mislykket i så mye som det ikke fant 50, men 50 var ikke i tabellen. Men vi har grundig søkt gjennom hvert enkelt element og så, mens vi ikke fant noe, lineær søke fortsatt lykkes selv om element ikke er i matrisen. 

Så hva er det verste tilfellet scenario med lineær søk? Vel har vi å se gjennom hvert enkelt element, enten ved at målelementet er det siste elementet i matrisen, eller elementet vi leter etter ikke befinne seg i matrisen i det hele tatt. Hva er den best case scenario? Vel, vi kan finne den element umiddelbart. Og hvor mange elementer vi må da se på i beste fall hvis vi leter etter det og vi finner det helt i begynnelsen? Vi kan stoppe umiddelbart. 

Hva sier dette om kompleksiteten i lineær søk? Vel i verste fall har vi å se på hvert enkelt element. Og så det kjører i O av n, i verste tilfelle. 

I beste fall er vi skal finne elementet umiddelbart. Og så kjører i omega for en. 

Jeg er Doug Lloyd. Dette er CS50.