Busca llineal

	Busca Llineal
	Classe	Algoritmes de busca
	Estructura de senyes	{{{senyes}}}
	Pijor dels casos	O(n)
	Millor dels casos	O(1)
	Case promig	O(n)
	Complexitat del pijor dels casos	O(1) iterativo

En informàtica, la busca llineal o la busca seqüencial és un método per a trobar un valor objectiu dins d'una llista. Esta comprova secuencialmente cada element de la llista per al valor objectiu fins que és trobat o fins que tots els elements hagen segut comparats.

Busca llineal és en temps el pijor, i marca com a màxim n comparacions, a on n és la llongitut de la llista. Si la provabilitat de cada element per a ser buscat és el mateix, llavors la busca llineal té una mija de n/2 comparacions, pero esta mija pot ser afectat si les provabilitats de busca per a cada element varien. La busca llineal és poc pràctica perque atres algoritmes de busca i esquemes, com l'algoritme de busca binaria i Taula hash, és significativament més ràpit buscant tot menys llestes curtes.

Algoritme

Busca llineal comprova secuencialmente cada element de la llista fins que troba un element que coincidix en el valor d'objectiu. Si l'algoritme aplega al fi de la llista sense trobar l'objectiu, la busca termina insatisfactoriamente.

Algoritme bàsic

Donat una llista L de n elements en valors o registres L0 ... Ln−1 i valor d'objectiu T, la subrutina següent utilisa busca llineal per a trobar l'índex de l'objectiu T en L.

1. Set i a 0.
2. Si L_i = T, la busca culmina exitosamente; retorna i.
3. Aumente i en 1.
4. Si i < n, retornar al pas 2. D'un atre modo, la busca termina insatisfactoriamente.

En un valor centinela

L'algoritme anterior, realisa dos comparacions per iteración: un per a comprovar si Li és igual a t, i l'atre per a comprovar si i apunta a un índex vàlit de la llista. Afegint un valor extra Ln a la llista (un valor centinela) que és igual a l'objectiu, la segona comparació pot ser eliminada fins al fi de la busca, fent l'algoritme més ràpit. La busca trobarà el centinela si l'objectiu no està contingut dins de la llista.[4]

1. Set i a 0.
2. Si  L_i = T,anar al pas 4.
3. Aumente i en 1 i anar al pas 2.
4. Si i < n , la busca termina exitosamente; retorna i. Sino la busca culmina insatisfactoriamente.

En una llista ordenada

Si la llista està ordenada tal que L₀ &li; L₁ ... &li; L_n−1 , la busca pot establir l'absència de l'objectiu més corrents en concloure la busca una volta que Li supera l'objectiu. Esta variació requerix un centinela el valor del qual és més gran que l'objectiu.

1. Set i a 0.
2. Si  L_i ≥ T , anar al pas 4.
3. Aumente i en 1 i anar al pas 2.
4. Si L_i = T, la busca termina exitosamente; retorna i. Sino la busca termina sense èxit.

Anàlisis

Per a una llista en n elements, el millor cas és quàn el valor és igual al primer element de la llista, en este cas solament es necessita una comparació. El pijor cas és quan el valor no és en la llista (o ocorre solament una volta, al final de la llista), en este cas es necessiten n comparacions.

Si el valor que s'està buscant es presenta k voltes en la llista, i tots els elements de la llista és igualment provables, el número esperat de comparacions és

$\{\begin{array}{cc}n& \text{if }k=0\\ \frac{n+1}{k+1}& \text{if }1\le k\le n.\end{array}$

Per eixemple, si el valor que s'està buscat ocorre una volta en la llista, i tot element de la llista és igualment provable, el número esperat de comparacions és $\frac{n+1}{2}$ Aún aixina, si és sabut que ocorre una volta, llavors com a màxim n - 1 comparacions són necessitades, i el número esperat de comparacions és

$\frac{(n+2)(n-1)}{2n}$

(Per eixemple, per a n = 2 açò és 1, corresponent a un sol si-llavors-més construir).

Qualsevol manera, el cost del pijor cas i el cost esperat de busca llineal són abdós O(n).

Provabilitats no uniformes

El rendiment de busca llineal millora si el valor desijat és té major provabilitat de ser trobat el principi de la llista que al seu fi. Per tant, si alguns valors són molt més provables per a ser buscats que uns atres, és millor colocar-los al principi de la llista.

En particular, quàn els elements de llista estan arreglats per orde de provabilitat decreixent, i estes provabilitats estan geomètricament distribuïdes, el cost de busca llineal és únic O(1). Si el tamany n de llista és bastanet gran, la busca llineal serà més ràpida que busca binaria, el cost de la qual és O(log n).

Vore també

• Busca ternaria
• Taula hash

Bibliografia

• Knuth, Donald (1998). (2.º ed.). Llectura, MA: Addison-Wesley Professional.  ISBN 0-201-89685-0