1.3-complejidad

1.3.1-tiempo de ejecucion de un algoritmo

como se mide el tiempo de ejecucion de un programa en funcion de N (numero de datos)?. esta funcion se puede medir fisicsamente calulandola con un reloj o se puede calcular con el codigo contando las intrucciones a ejecutar y multiplicandoli por el tiempo requerido por cada intruccion.

reglas practicas para calcular la omplejidad de un algoritmo

1.-sentencia sencilla:se refiere alas sentencia de asigacion mostrada en la asalida de datos simpre yc cunado no trnaaje sobre estructuras cullo tamano esta relacionado con N. como requiere un tiempo constante de ejecucion su complejidad es del orden 1

2.-secuencia de sentencia: su complejidad esta dada por la suma de las complejidades individuales de acuerdo al tipo de sentencias tomandose en cuneta el orden mas alto.

3.-decision (if): la cindicion suele ser de orden constante O(1), sumando en la peor rama posible ya sea d la del then o l a del else

4.-bucles(ciclos): en los cilcos con contaddor explisito existen dos casos el tamana N forme parte de los limites del ciclo o no

en los cickos multiplicatios com el whiley el do while el inremento de la variable control no es nineal no que ase incrementar el orden de complejidad como en los ejemplos siguientes.

COMPLEJIDAD LOG(log n)

5.-llamdas de procedimientos: la complejidad e llamar a un prosedoimiento esta dada por la cmplejidad del contididdo del proisedimeinto en si , es desir su complejidad depende del tipo de intrucciones o sentencias que existan en el cuerpo del prodedimiento. en clonclucion la comliejidad dein prosedimineto tiende a complidarse si se trata de prosediminetos recursivos

ordenes de complejidad

O(1)constante idela

O(n)lineal eficente

O(log n)logaritmico eficente

O(n log n)casi lineal eficente

O(n*)polinomial tratable

o(K^n)exponencial intratables

o(n!)factorial intratables