Complejidad De Los Algoritmos

COMPLEJIDAD DE LOS ALGORITMOS

ALGORITMO

Es una secuencia finita de instrucciones, cada una de las cuales tiene un significado preciso y puede ejecutarse con una cantidad finita de esfuerzo en un tiempo finito. Las instrucciones de un algoritmo pueden ejecutarse cualquier número de veces, siempre que ellas mismas indiquen la repetición.

Un algoritmo es cualquier procedimiento computacional bien definido, junto con un conjunto de datos de entrada permitidos, que produce un valor o conjunto de valores de salida.

EFICIENCIA O COMPLEJIDAD DE LOS ALGORITMOS

La resolución de un problema se puede lograr por medio de diferentes algoritmos lo cual implica la necesidad de elegir el mejor entre ellos y, por tanto, se han de evaluar los recursos que requiere cada algoritmo para su ejecución. A este proceso de evaluación de los recursos se le denomina cálculo de la eficiencia o complejidad de un algoritmo. Se dice que un algoritmo es más eficiente o de menor complejidad que otro cuando utiliza menos recursos.

Memoria que necesita

RECURSOS (EFICIENCIA) Tiempo de Ejecución

Memoria Estática

Memoria

Sumar la memoria ocupada por todas las variables utilizadas por el algoritmo.

Memoria Dinámica No es fácil depende de cada ejecución concreta del algoritmo.

Tiempo de Ejecución

Tiempo que requiere para su ejecución

El incesante aumento de la capacidad que poseen los nuevos ordenadores, tanto en velocidad de cálculo, como en almacenamiento de memoria, no implica que se tenga que desechar el estudio de la eficiencia de los algoritmos, ya que un mal algoritmo ejecutado en un ordenador muy potente puede tardar mucho más que otro algoritmo mejor que se ejecute en otra máquina menos potente.

Tamaño de los datos de Entrada FACTORES DE LA COMPLEJIDAD

Contenido de los datos de Entrada Ordenador y código generado

Tamaño de los Datos de Entrada

El tamaño de un ejemplar X se corresponde formalmente con el número de dígitos binarios necesarios para representarlo en el computador .

Por ejemplo, un problema consistente en ordenar N enteros será considerado de tamaño N, aunque se necesite en la práctica más de un dígito binario para representar cada entero.

Cuando se trate de problemas numéricos, como el cálculo del factorial de un número, la eficiencia se expresará en función del valor del dato considerado y no en función de su tamaño (que sería la longitud de la representación binaria de dicho valor)

Tamaño de los datos de Entrada FACTORES DE LA COMPLEJIDAD

Contenido de los datos de Entrada Ordenador y código generado

Caso peor

Contenido de los Datos de Entrada

Caso medio

Caso Peor Fijado un tamaño del problema, analizar la eficiencia

del

algoritmo

en

aquellas

situaciones en las que emplea más tiempo y teniendo como objetivo la obtención de una cota superior del tiempo de ejecución del algoritmo.

Caso Medio Plantea la necesidad de conocer el tiempo de ejecución

del

algoritmo

en

todas

las

situaciones y la frecuencia con que éstas se presentan.

Tamaño de los datos de Entrada FACTORES DE LA COMPLEJIDAD

Contenido de los datos de Entrada Ordenador y código generado

Ordenador y Código Procesado No suele tenerse en cuenta a la hora de calcular la eficiencia en tiempo de un algoritmo debido a que, por un lado, se pretende analizar la eficiencia de un algoritmo de un modo totalmente independiente de las máquinas y lenguajes existentes, por otro lado, se acepta el PRINCIPIO DE INVARIANCIA: diferentes implementaciones de un mismo algoritmo diferirán en sus tiempos de ejecución.

CALCULO DEL TIEMPO DE EJECUCION El

tiempo

de

ejecución

debe

representarse independiente de cualquier unidad de medida como segundos, sino que se representa en base al número de iteraciones que el algoritmo ejecuta

Algoritmo: Sumar elementos de un arreglo

Entrada: un arreglo A, de n enteros Salida: Suma de los elementos almacenados en el arreglo A A[0] + A[1] + A[3] + Proceso 1)

suma = 0

2)

i=0

3)

mientras (i
4)

suma = suma + A[i]

5)

i=i+1

6)

fin_mientras

7)

devolver suma

Para este algoritmo, las instrucciones 1,2 y 7 se ejecutan una sola vez por lo que representamos su tiempo de ejecución como unitario. Sin embargo, las instrucciones 3, 4, 5 y 6 se ejecutan n veces, así al tiempo

de

ejecución

expresado como : T(n) = n + 1 Para n ∈ Z, n > 0

del

algoritmo

puede

ser

Algoritmo: Obtener el valor mayor

Entrada: un arreglo A, de n enteros Salida: Mayor del arreglo A Proceso 1)

mayor = A[0]

2)

Para i=0 hasta n-1 hacer

3)

si A[i] > mayor entonces

4) 5)

mayor = A[i] fin_si

6)

fin_para

7)

devolver mayor

Para este algoritmo, las instrucciones 1 y 7 se ejecutan una sola vez por lo que representamos su tiempo de ejecución

como

unitario.

Sin

embargo,

las

instrucciones 2, 3, 4, 5 y 6 se ejecutan n-1 veces, así al tiempo

de

ejecución

del

expresado como : T(n) = n + 1 T(n) = n – 1 + 1 T(n) = n Para n ∈ Z, n > 0

algoritmo

puede

ser

Algoritmo: Sumar elementos de una matriz Entrada: una matriz M de f filas y c columnas Salida: suma de los elementos de M Proceso 1)

suma = 0

2)

i=0

3)

mientras (i
4)

i=0

5)

mientras (j
6)

suma = suma + M[i,j]

7)

j=j+1

8)

fin_mientras

9)

i=i+1

10)

fin_mientras

11)

devolver suma

Para este algoritmo, las instrucciones 1, 2 y 11 se ejecutan una sola vez, entonces tenemos un tiempo unitario, las instrucciones 3,4 y 9 se ejecutan f veces, entonces tenemos un tiempo f y finalmente las instrucciones 5, 6 y 7 se ejecutan fc veces: T(n) = fc + f + 1 Donde n = numero de elementos de la matriz, es decir al número de filas (f) por el numero de columnas (c).