Download - Analisis de algoritmo
¿Qué es un 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.
Respecto al uso eficiente de los
recursos, éste suele medirse
en función de dos espacio, es
decir, memoria que utiliza
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.
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
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
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