Búsqueda lineal
De Wikipedia, la enciclopedia encyclopedia
En informática, la búsqueda lineal o la búsqueda secuencial es un método para encontrar un valor objetivo dentro de una lista. Ésta comprueba secuencialmente cada elemento de la lista para el valor objetivo hasta que es encontrado o hasta que todos los elementos hayan sido comparados.
Búsqueda Lineal | ||
---|---|---|
Clase | Algoritmos de búsqueda | |
Estructura de datos | {{{datos}}} | |
Peor de los casos | O(n) | |
Mejor de los casos | O(1) | |
Caso promedio | O(n) | |
Complejidad del peor de los casos | O(1) iterativo |
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 el mismo, entonces la búsqueda lineal tiene una media de n/2 comparaciones, pero esta media puede ser afectado si las probabilidades de búsqueda para cada elemento varían. La búsqueda lineal es poco práctica porque otros algoritmos de búsqueda y esquemas, como el algoritmo de búsqueda binaria y Tabla hash, es significativamente más rápido buscando todo menos listas cortas.