[REPRODUCCIÓ DE MÚSICA] DOUG LLOYD: Lineal recerca és un algoritme que pot utilitzar per trobar un element en una matriu. Un record algoritme és un conjunt pas a pas d'instruccions per completar una tasca. 

Hi lineal algoritme funciona de la següent manera. Iterar a través de la matriu d'esquerra a dreta, a la recerca d'un element especificat. 

En pseudocodi, que és un més versió destil·lada d'aquesta frase, si el primer element és el que vostè està buscant, pot aturar. Altrament, passar al següent element i seguir endavant i una altra fins que trobi l'element, o no ho fas. Així que podem fer servir el lineal algoritme de recerca, per exemple, per trobar el valor objectiu 09:00 en aquesta matriu. Bé comencem pel principi. Si és el que estem buscant, podem aturar. No és, no estem buscant 11. Així que en cas contrari, passar al següent element. 

Així que ens fixem en el 23. És de 23 que estem buscant? Doncs no, així que vam passar a la següent element, i el següent element, i seguim passant per aquest procés una i altra i una altra, fins que aterrem en una situació com aquesta. 

Nou és el que estem buscant, i aquest element de la matriu és a dir, el seu valor és de nou. I així ens trobem el que estem buscant, i podem aturar. Hi lineal té completat, amb èxit. 

Però què passa si estem buscant un element que no està en la nostra matriu. Té encara treballen cerca lineal? Bé segur. Així que repetim aquest procés començant en el primer element. Si és el que estem buscant, podem aturar. No és. Altrament, ens movem al següent element. 

Però podem seguir repetint aquest procés, examinar cada element, al seu torn, l'esperança que ens trobem amb el número 50. Però no sabrem si hem trobat el número 50 o si no ho féssim, fins que hàgim entrem sobre cada element de la matriu. 

Només una vegada que hem fet això i es queden curts, podem concloure que 50 no està a la matriu. I pel que la recerca lineal algoritme, així que no, per se. Però no en el sentit que no va tenir èxit en fer el que demanem que faci. 

Es va tenir èxit en el molt més, ja que no es va trobar 50, però 50 no estava en l'array. Però hem buscat exhaustivament a través de cada element i així, mentre que no trobem res, cerca lineal encara té èxit encara que la element no està en la matriu. 

Quin és el pitjor dels casos escenari amb recerca lineal? Bé, hem de mirar a través de cada element, ja sigui perquè l'element de destinació és l'últim element de la matriu, o l'element que estem buscant no en realitat existeix en la matriu en absolut. Quin és el millor dels casos? Bé podríem trobar la element immediatament. I quants elements Com podem llavors hem de mirar en en el millor cas, si estem a la recerca d'ella i ens trobem en el començament? Podem parar immediatament. 

Què diu això sobre la complexitat de cerca lineal? Bé, en el pitjor dels casos, tenim per mirar a cada element. I el que s'executa en O de n, en el pitjor dels casos. 

En el millor dels casos, anem a trobar l'element immediatament. I així funciona en omega d'1. 

Sóc Doug Lloyd. Això és CS50.