[Música tocando] Doug LLOYD: Lineal investigación é un algoritmo que pode usar para atopar un elemento nunha matriz. Un recordo algoritmo é un conxunto paso a paso de instrucións para completar unha tarefa. 

A investigación lineal algoritmo funciona do seguinte xeito. Iterado través da matriz de esquerda a dereita, á procura dun elemento especificado. 

En pseudocódigo, que é unha forma máis versión destilada desta frase, O primeiro elemento que é está a buscar, pode parar. Se non, pasar ao seguinte elemento e manter indo máis e máis ata que atope o elemento, ou non fai. Así, podemos usar o lineal algoritmo de procura, por exemplo, para atopar o valor obxectivo nove nesa matriz. Ben imos comezar polo comezo. Se é o que somos buscar, podemos parar. Non é, non estamos a buscar 11. Así, se non, pasar ao seguinte elemento. 

Entón miramos para 23. 23 é o que estamos a buscar? Ben, non, por iso, pasar á seguinte elemento eo elemento seguinte, e seguimos a atravesar este proceso máis e máis e máis, ata que pousar nunha situación como esta. 

Nove é o que estamos a buscar, e este elemento da matriz é, de valor é nove. E así atopamos o que somos buscar, e podemos parar. A investigación lineal ten Feito con éxito. 

Pero o que dicir se estamos a buscar un elemento que non está na nosa matriz. Será que busca lineal aínda funciona? Ben seguro. Entón, nós repetimos este proceso comezando o primeiro elemento. Se é o que somos buscar, podemos parar. Non é. Se non, nós nos movemos no seguinte elemento. 

Pero podemos seguir a repetir ese proceso, examina cada elemento, á súa vez, coa esperanza de que atopamos o número 50. Pero nós non saberemos se atopamos o número 50 ou se non o fixo, ata que xa pisou sobre cada elemento da matriz. 

Só unha vez que fixemos iso e vir enriba do short, podemos concluír que 50, non figura na matriz. E así a procura lineal algoritmo, así el fallou, per se. Pero non no sentido de que non tivo éxito en facer o que pedimos que faga. 

Tivo éxito en como tanto como el non atopou 50, pero 50 non estaba na matriz. Pero temos extensa investigados a través de cada elemento e así, mentres non atopamos algo, procura lineal aínda sucede aínda que a elemento non está na matriz. 

Entón, cal é o peor caso escenario con procura lineal? Ben, temos que mirar a través cada elemento, ben porque o elemento obxecto é o último elemento da matriz, ou o elemento que estamos a buscar non realmente existen na matriz en todo. Cal é o mellor escenario? Ben que poderíamos atopar o elemento inmediatamente. E cantos elementos nós entón temos que mirar na no mellor dos casos, se nós estamos mirando para el e nós atopalo ao comezo? Podemos deixar inmediatamente. 

O que isto di sobre a complexidade da busca lineal? Ben, no peor caso, temos ollar para cada elemento. E así é executado no de N, no peor dos casos. 

No mellor dos casos, nós imos atopar o elemento inmediatamente. E así é executado en omega de 1. 

Eu son Doug Lloyd. Este é CS50.