1.3 Complejidad.- Tiempo de ejecucion de un algoritmo

1.3.1 - Tiempo de ejecución de un algoritmo

Como se mide el tiempo de ejecución de un programa en funcion de N (numero de datos)?

Esta función se puede medir físicamente calculando con un reloj o se puede calcular sobre el código contando las instrucciones ejecutadas a ejecutar y multiplicándolo por el tiempo requerido
por cada instrucción.

Ejemplo:
S1;
for(int i=0;i
S2;
entonces: T(n) = t1 + t2 * N

En este ejemplo siendo T1 el tiempo que lleve ejecutar la sentencia de S1 y t2 el tiempo que lleve ejectuar la S2 un numero N de veces dentro del ciclo for.

Reglas practicas para calcular la complejidad de un algoritmo

1.- Sentencia Sencilla
Se refiere a la sentencia de asignacion ,entrada o salida de datos siempre y cuando no trabajen sobre estructuras cuyo tamaño esta relacionado con N que es el numero de datos.
Como requiere un tiempo constante de ejecucion su complejidad es el orden O(1).

2.- Secuencia de sentencias:
Su complejidad esta dada por la suma de las complejidades individuales de acuerdo al tipo de sentencias que se trate tomandose en cuenta el orden mas alto

3.- Decision (if):
La condicion puede ser de orden constante o uno, sumando en la peor rama posible ya sea la del then o del else.

4.- Bucles(ciclos):
En los ciclos con contador explicito existen 2 casos: el tamaño N forma parte de los limites del ciclo o no.

Ejemplos:

caso 1: for(int i=0;i
{S1;}
entonces k*0(1)= 0(1) Constante
caso 2: for(int i=0;i
{S1;}
entonces N*O(1) = 0(n) Linear

b) Evolucion de variable de control No lineal (while)
En los ciclos multiplicativos como el while y do while el incremento o decremento de la variable
de control no es lineal lo que hace incrementar el orden de complejidad como en los ejemplos
siguientes.

Ej.
c=1
while (c
{
S1;
c=2*c;
entonces complejidad 0(log n)
logaritmica

Ej.
c=n;
while (c
{
S1;
c=c/2;
}
Complejidad Logaritmica 0(log n)

5.- Llamadas a Procedimientos:
La complejidad de llamar a un procedimiento esta dada por la complejidad del procedimiento en si
es decir, su complejidad depende del tipo de instrucciones o sentencias que existan en el
cuerpo de los procedimientos. En conclusion la complejidad de un procedimiento tiende a
complicarse si se trata de procedimientos recursivos.

Ej. Funcion factorial (no recursividad)
int factorial(int n) //sentencia Entrada (1)
{
int fact = 1; //sentencia asignacion O(1)
for(int i = n; i>0; i--) //ciclo contador explicito O(1)
fact = fact * i; //sentencia de asignacion O(1)
return fact; //sentencia salida O(1)
}

entonces: Complejidad Lineal O(n)
por el ciclo for con numero de interacciones igualan a n.

Programa 9.
Crear clase factorial, recibira n, en el programa principal se pide n.
Factorial (no recursivo)

Ordenes de complejidad
O(1) Constante Ideal
O(n) Lineal Eficiente
O(log n) Logarítmico //
O(nlogn) Casi Lineal //
O(n^k) Polinimica Tratable
O(k^n) Exponencial Intratable
O(n!) Factorial Intratable