ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Búsqueda lineal : que es, definición y significado, descargar videos y fotos.

videos internet

salud  ıllı Búsqueda lineal : que es, definición y significado, descargar videos y fotos.  


En informática, la busca lineal o bien la busca secuencial es un procedimiento para hallar un valor objetivo en una lista.Ésta verifica secuencialmente cada elemento de la lista para el valor objetivo hasta el momento en que es encontrado o bien hasta el momento en que todos y cada uno de los elementos hayan sido equiparados.


Búsqueda lineal es en tiempo el peor, y marca como máximo n comparaciones, donde n es la longitud de la lista. Si la probabilidad de cada elemento para ser buscado es exactamente el mismo, entonces la busca lineal tiene una media de n/2 comparaciones, mas esta media puede ser perjudicado si las probabilidades de busca para cada elemento cambian. La busca lineal es poco práctica por el hecho de que otros algoritmos de busca y esquemas, como el algoritmo de busca binaria y Tabla hash , es significativamente más veloz buscando todo menos listas cortas.


Búsqueda lineal verifica secuencialmente cada elemento de la lista hasta el momento en que halla un factor que coincide con el valor de objetivo. Si el algoritmo llega por fin de la lista sin hallar el propósito, la busca acaba insatisfactoriamente.


Algoritmo básico


Dado una lista L de n elementos con valores o bien registros L0 ... Ln-1 y valor de objetivo T, la subrutina siguiente emplea busca lineal para localizar el índice del objetivo T en L.



  1. Set i a 0.
  2. Si Li = T, la busca acaba exitosamente; regresa i.
  3. Aumento i en 1.
  4. Si i < n, retornar al paso dos. De otra manera, la busca acaba insatisfactoriamente.

Con un valor centinela


El algoritmo precedente, efectúa 2 comparaciones por iteración: uno para revisar si Li es igual a t, y el otro para revisar si i apunta a un índice válido de la lista. Agregando un valor extra Ln a la lista (un valor centinela) que es igual al objetivo, la segunda comparación puede ser eliminada hasta el fin de la busca, haciendo el algoritmo más veloz. La busca hallará el centinela si la meta no esta contenido en la lista.



  1. Set i a 0.
  2. Si Li = T,ir al paso cuatro.
  3. Aumento i en 1 y también ir al paso dos.
  4. Si i < n , la busca acaba exitosamente; regresa i. Sino más bien la busca acaba insatisfactoriamente.

En una lista ordenada


Si la lista está ordenada tal que L0 = L1 ... = Ln-1 , la busca puede establecer la ausencia del objetivo más deprisa al finalizar la busca cuando Li supera el propósito. Esta alteración requiere un centinela cuyo valor es más grande que la meta.



  1. Set i a 0.
  2. Si Li = T , ir al paso cuatro.
  3. Aumento i en 1 y también ir al paso dos.
  4. Si Li = T, la busca acaba exitosamente; regresa i. Sino más bien la busca acaba sin éxito.

Para una lista con n elementos, el mejor caso es en qué momento el valor es igual al primer elemento de la lista, en un caso así solo se precisa una comparación. El peor caso es cuando el valor no es en la lista (o bien ocurre solo una vez, al final de la lista), en un caso así se precisan n comparaciones.


Si el valor que se esta buscando se presenta k veces en la lista, y todos y cada uno de los elementos de la lista es del mismo modo probables, el número aguardado de comparaciones es

{nif k=0n+1k+1if 1=k=n.undefined

Por ejemplo, si el valor que se esta buscado ocurre una vez en la lista, y todo elemento de la lista es del mismo modo probable, el número aguardado de comparaciones es n+12undefined Todavía de esta forma, si es sabido que ocurre una vez, entonces como máximo n - 1 comparaciones son necesitadas, y el número aguardado de comparaciones es

(n+2)(n-1)2nundefined

(Por servirnos de un ejemplo, para n = dos esto es 1, correspondiendo a un solo si-entonces-más edificar).


Cualquier forma, el costo del peor caso y el costo aguardado de busca lineal son los dos O(n).


Probabilidades no uniformes


El desempeño de busca lineal mejora si el valor deseado es tiene mayor probabilidad de ser encontrado el principio de la lista que a su fin. Por ende, si ciertos valores son considerablemente más probables para ser buscados que otros, es mejor ponerlos al comienzo de la lista.


En particular, en qué momento los elementos de lista están arreglados por orden de probabilidad decreciente, y estas probabilidades están geométricamente distribuidas, el costo de busca lineal es único O(1). Si el tamaño n de lista es bastante grande, la busca lineal va a ser más veloz que busca binaria, cuyo costo es O(log n).


La busca lineal es por norma general sencillísima de incorporar, y es práctico en qué momento la lista tiene solo varios elementos, o bien cuando efectúa una sola busca en un lista desorganizada.


Cuando muchos valores deben ser buscados en exactamente la misma lista, de manera frecuente se pre-procesa la lista para usar un procedimiento más veloz. Por poner un ejemplo, uno puede ordenar la lista y usar busca binaria, o bien edificar una estructura de datos de busca eficiente de él. El contenido de la lista debería mudar habitualmente, reiterar la re-organización puede ser más el conflictivo de lo que vale.


Como resultado, aun incluso de esta forma teóricamente otros algoritmos de busca pueden ser más veloces que busca lineal (por poner un ejemplo busca binaria), en la práctica los arreglos de tamaño medio (alrededor cien elementos o bien menos) pueda ser no viables usar cualquier otro procedimiento. En arreglos más grandes, solo hace sentido para emplear otros métodos de busca más veloz si los datos son bastante grande, pues el tiempo inicial para preparar (ordenar) los datos es equiparable a muchos buscas lineales


  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı Búsqueda lineal : que es, definición y significado, descargar videos y fotos.

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas