>> [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.