Complejidad de un algoritmo

Nombre: Jonathan cofre Vivanco

Fecha: 08-mayo-2013

¿Qué es una complejidad de algoritmo?

• -La complejidad de los algoritmos representa o dice el tiempo de ejecución de cualquier programa en base a los 'n' datos de entrada.

La complejidad de un algoritmo según:

• En el desarrollo de un programa computacional resulta necesario definir criterios para medir su rendimiento o comportamiento. Estos criterios se centran principalmente en su simplicidad y en el uso eficiente de los recursos.

Si los recursos fueran espacio

• Respecto al uso eficiente de los recursos, éste suele medirse en función de dos

espacio, es decir, memoria que utiliza

Y si fuera tiempo

• el tiempo, lo que tarda en ejecutarse.

Cada algoritmo se va a comportar de manera distinta dependiendo de la cantidad de datos que se ingresen ( variables.) y del equipo en que se ejecute.

Por eso es conveniente estudiar

• El comportamiento de un algoritmo puede cambiar notablemente para diferentes

• entradas para muchos programas el tiempo de ejecución es en realidad una función

• de la entrada específica, y no sólo del tamaño de ésta. Así suelen estudiarse tres casos

• para un mismo algoritmo: caso peor, caso mejor y caso medio.

Complejidad del mejor caso

• El caso mejor corresponde a la traza (secuencia de sentencias) del algoritmo que realiza menos instrucciones.

Complejidad del caso promedio

• el caso peor corresponde a la traza del algoritmo que realiza más instrucciones, lo cual nos asegura que al menos el algoritmo se desempeñará de esa forma .

Complejidad peor caso

• el caso peor corresponde a la traza del algoritmo que realiza más instrucciones, lo cual nos asegura que al menos el algoritmo se desempeñará de esa forma .

Tiempo de ejecución

• Tiempo de Ejecución

• cuando el tamaño de la entrada crece , la función para medir esa

• complejidad se denota como T(n).

• Esta función se puede medir físicamente ejecutando el programa, calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción

Notación asintótica( o cota superior asintótica)

• En análisis de algoritmo una cota superior asintótica es una función que sirve de cota superior de otra función cuando el argumento tiende a infinito.

La cota superior asintótica tiene gran importancia en teoría de la complejidad computacional a la hora de definir las clases de complejidad de cada algoritmo.

Se denomina “asintótica” porque analiza el comportamiento de las funciones en base a su tasa de crecimiento

• En informática, la notación O grande se utiliza para clasificar los algoritmos de cómo responden (por ejemplo, en su tiempo de procesamiento o de los requisitos de espacio de trabajo) a los cambios de tamaño de entrada. Esta siempre es positiva

Órdenes usuales para funcionesLos órdenes más utilizados en análisis de algoritmos, en orden creciente, son los siguientes (donde c representa una constante y n el tamaño de la entrada):

notación nombre

O(1) orden constante

O(log log n) orden sublogarítmico

O(log n) orden logarítmico

O() orden sublineal

O(n) orden lineal

O(n · log n) orden lineal logarítmico

O(nc) orden potencial

O(cn), n > 1 orden exponencial

O(n!) orden factorial

O(nn) orden potencial exponencial

final