Complejidad del tiempo de búsqueda lineal

La búsqueda lineal es una búsqueda secuencial. Este método de búsqueda verifica los elementos de la lista uno por uno, comenzando desde el primer elemento. Cuando ve la primera aparición del elemento que está buscando, la búsqueda se detiene. El elemento que está buscando se llama objetivo. Si no se encuentra el elemento, se verifican todos los elementos de la lista. La búsqueda lineal es un algoritmo de búsqueda muy simple que cada programador debe aprender, ya sea oficial o intuitivamente.

Considere la siguiente lista:

I J A C B G D H E F

Para buscar A, el programa tiene que iterar la lista 3 veces. Para buscar G, el programa tiene que iterar la lista 6 veces. Para buscar F, el programa tiene que iterar la lista 10 veces. Para buscar k o cualquier carta que no esté en la lista, el programa tiene que iterar la lista 10 veces y no encontrará una coincidencia.

El objetivo de este artículo es producir la complejidad del tiempo para la búsqueda lineal. La programación se realiza en la siguiente discusión C.

Algoritmo de búsqueda lineal

El algoritmo para la búsqueda lineal es sencillo. Suponga que la lista es una matriz basada en índice cero. Deje que la variable que represente cada índice sea i. Deje que la matriz tenga el nombre un. Los pasos son los siguientes:

• • Que yo sea 0.
  • Si A [i] es el objetivo, el valor para i se devuelve y la búsqueda termina con éxito.
  • Si a [i] no es el objetivo, aumente i por 1 y repita el paso anterior.
  • Mientras que yo es menor que n, donde n es la longitud de la matriz, sigue repitiendo los dos pasos anteriores en orden.
  • Continúe de esta manera hasta que se encuentre o no se encuentre el objetivo.

La búsqueda termina con éxito cuando se encuentra el objetivo. La búsqueda termina sin éxito cuando no se encuentra el objetivo. Para un final fallido, todos los n elementos se verifican.

Complejidad del tiempo

La complejidad del tiempo es el número de operaciones principales para que algún código complete su tarea. Verificar si el objetivo coincide con un elemento es una operación. Existe la peor complejidad del tiempo, la complejidad del tiempo promedio y la complejidad del tiempo en el mejor de los casos.

Peor complejidad del tiempo

El número máximo de operaciones ocurre cuando el objetivo está al final de la lista o no está en la lista en absoluto. Este es el peor caso. La peor complejidad del tiempo se da como:

En)

Esto usa la notación Big-O. La notación Big-O comienza con el mayúscula O, seguido de paréntesis. Dentro de los paréntesis es la expresión del número de operaciones para resolver la tarea.

La mejor complejidad del tiempo

Si el primer elemento de la lista es el objetivo, solo es necesaria una operación de verificación para la búsqueda. Es decir, solo una operación es necesaria para la búsqueda. Esta es la mejor complejidad del tiempo. Está escrito como:

O (1)

Donde 1 en los paréntesis significa una operación.

Complejidad del tiempo promedio

La complejidad del tiempo promedio de los casos depende de la distribución de probabilidad. Si cada elemento puede estar en cualquier posición, es probable que cada elemento se busque igualmente. En esta situación, la complejidad del tiempo promedio se da como:

En 2)

Programación en C

La búsqueda lineal es probablemente la búsqueda más fácil para escribir un programa para. Simplemente siga el algoritmo, que se repite aquí, para una fácil referencia:

• • Que yo sea 0.
  • Si A [i] es el objetivo, el valor para i se devuelve y la búsqueda termina con éxito.
  • Si a [i] no es el objetivo, aumente i por 1 y repita el paso anterior.
  • Mientras que yo es menor que n, donde n es la longitud de la matriz, sigue repitiendo los dos pasos anteriores en orden.
  • Continúe de esta manera hasta que se encuentre o no se encuentre el objetivo.

Esencialmente, el programa es el siguiente:

#incluir
int LinearSearch (char a [], int n, char t)
para (int i = 0; iif (t == a [i])
regresar i;

Comienza al incluir el stdio.H Biblioteca que es responsable de la entrada y salida. Después de eso, existe la definición de función LinearSearch (). El código principal en la definición de función es el for-loop. El for-bucle escanea la matriz desde el principio hasta el final, buscando una coincidencia del objetivo. Si se encuentra un objetivo, se devuelve el índice para el elemento coincidente en la matriz. Para obtener el número ordinal del índice del elemento coincidente, agregue 1 al índice basado en cero.

Una función principal C adecuada para el programa anterior es la siguiente:

int main (int argc, char ** argv)

int n = 10;
char a [] = 'i', 'j', 'a', 'c', 'b', 'g', 'd', 'h', 'e', ​​'f';
int ret = linealsearch (a, n, 'g');
printf ("%i \ n", ret);
regresar 0;

La primera declaración de la función principal C declara el número de elementos en la matriz dada. Después de eso, está la matriz con el nombre A. Hay diez personajes en la matriz. La declaración de la matriz comienza con "char" y no "int". A partir de ahí, se llama a la función definida de LinealSearch (). El primer argumento de la llamada de función es la matriz. El segundo argumento es el número de elementos en la matriz. El tercer argumento es el objetivo que es la letra cuya presencia en la matriz se verifica. Si está presente, se devuelve el índice basado en cero. Si no está presente, no se devuelve nada.

La siguiente declaración imprime cualquier índice devuelto. Para esta función principal C, se imprime 5. Si se agrega 1 a 5, sería 6, que es el índice ordinal.

Conclusión

La peor complejidad del tiempo se da como:

En)

Esto usa la notación Big-O. La notación Big-O comienza con el mayúscula O, seguido de paréntesis. Dentro de los paréntesis es la expresión del número de operaciones para resolver la tarea.

Si el primer elemento de la lista es el objetivo, solo es necesaria una operación de verificación para la búsqueda. Es decir, solo una operación es necesaria para la búsqueda. Esta es la mejor complejidad del tiempo. Está escrito como:

O (1)

Donde 1 en los paréntesis significa una operación.

La complejidad del tiempo de caso promedio depende de la distribución de probabilidad. Si cada elemento puede estar en cualquier posición, es probable que cada elemento sea igualmente buscado por este algoritmo. En esta situación, la complejidad del tiempo promedio es:

En 2)