1.3.4 Comparacion de órdenes de complejidad
Los órdenes de complejidad están relacionados con la notación Big O y con las condiciones de espacio y tiempo. La complejidad de un algoritmo se refiere a la función que mide los recursos que necesita en relación al tamaño de la entrada, considerando tanto el espacio (la cantidad de memoria requerida) como el tiempo (que incluye las operaciones básicas como acceso, aritmética y comparación).
Según la implementación de cada uno de los algoritmos, las órdenes de complejidad son las siguientes:
| Algoritmo | Complejidad temporal del peor caso o cota superior Big O | Complejidad |
|---|---|---|
| Búsqueda secuencial | O(n) | Lineal |
| Búsqueda binaria | O(log n) | Logarítmico |
| Búsqueda indexada | O(1) | Constante |
En el siguiente recurso, podrás observar una explicación más detallada de la tabla anterior.
Algoritmo de búsqueda secuencial
El algoritmo de búsqueda secuencial tiene una complejidad lineal debido al ciclo for que se utiliza. En el peor de los casos, si se busca un registro que no se encuentra, se recorrerá el arreglo en su totalidad. Esto se puede visualizar gráficamente.
Algoritmo de búsqueda binaria
La búsqueda binaria tiene una complejidad logarítmica, ya que el arreglo debe estar ordenado y permite descartar mitades del arreglo en cada iteración, lo que la hace eficiente.
Algoritmo de búsqueda indexada
Finalmente, la búsqueda indexada tiene una complejidad constante debido a la función hash utilizada para calcular el índice del registro. Las operaciones aritméticas en la función hash se realizan en un tiempo constante, lo que optimiza la búsqueda.
En conclusión, es crucial elegir el algoritmo adecuado según la tarea y la cantidad de información a manejar. Con datos pequeños, cualquier algoritmo puede ser eficiente; sin embargo, con grandes volúmenes de datos, es preferible utilizar algoritmos con complejidades más bajas.