Anónimo
Análisis de complejidad de un algoritmo
Suponga está encargado de evaluar la complejidad de un algoritmo que desean aplicar en su empresa de motores de búsqueda en internet. Para efectos de estudio se define el siguiente prototipo de problema:
Sea V = [2,3,1,6,0,8,5,4] el arreglo de documentos identificados por un número, en donde tenemos que encontrar un documento que denotamos por la variable x. El algoritmo a utilizar es el siguiente:
Este algoritmo es tal que comienza identificando a la variable inicio y fin con el primer y último elemento del arreglo V, y luego comienza a buscar el valor de x recorriendo (avanzando) de uno en uno desde la posición inicio hasta la posición fin.
Como se puede apreciar el algoritmo tiene una ecuación de recurrencia para el caso peor cuando n>1 de la forma: T(n) = T(n-1) + b, con b constante, y T(n) = 0, para n = 0.
Dado la información anterior, se pide que realice un análisis del algoritmo para determinar la siguiente
Información:
1.- ¿Cuál es el tamaño de la entrada al comienzo de la implementación del algoritmo sobre el arreglo V?
2.- ¿Cuál es el caso en que el algoritmo resuelve la búsqueda de x en los elementos del arreglo V en el menor tiempo posible?
3.- ¿Cuál es el caso en que más tiempo demora el algoritmo realizar la búsqueda de x en los elementos del arreglo V?
4.- Calcule el orden de complejidad del algoritmo a partir de la ecuación de recurrencia.
1 Respuesta
1. La cantidad de elementos del arreglo, o sea 'fin'
2. Es 1 y se da cuando el elemento a buscar 'x', coincide con el primer elemento del arreglo
3. Es 'fin' y ocurre cuando el elemento 'x' coincide con el último elemento del arreglo (o no existe)
4. O(n), ya que el orden se mide siempre en el peor caso, y en este caso el peor caso se da cuando debe recorrer todo el arreglo
Salu2