Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Guías prácticas/Complejidad computacional/Solución al ejercicio 1 de complejidad computacional

De Wikilibros, la colección de libros de texto de contenido libre.
Ir a la navegación Ir a la búsqueda

El primer algoritmo de búsqueda recorrerá todos los elementos del arreglo en el peor de los casos, de manera que su complejidad será de . El segundo –la búsqueda binaria- divide en dos el campo de búsqueda en cada llamada o iteración, de manera que, en el peor de los casos, la cantidad de pasos será tal que:

-el entero igual o inmediatamente superior a .

Si el arreglo está ordenado, evidentemente convendría utilizar el algoritmo de búsqueda binaria.

Si no está ordenado, ordenarlo costaría por lo menos un tiempo de , que es superior al orden de tiempo de búsqueda lineal.


Algoritmo Encontrar el primer elemento Encontrar el elemento en la mitad
Búsqueda lineal O(1) O(n)
Búsqueda binaria O(1)


Algoritmo Mejor caso Peor caso Caso medio
Búsqueda lineal Primer elemento Elemento ausente Elemento del medio
Búsqueda binaria Elemento del medio Elemento ausente Posiciones intermedias[1]



^ El caso medio para el buscador binario es cualquier posición que se alcance en pasos.