TIEMPO DE EJECUCIÓN DE UN ALGORITMO

El tiempo de ejecución de un programa en función de N(numero de datos) se denomina T(N) y se calcula sobre el código contando las instrucciones a ejecutar y multiplicando por el tiempo requerido para cada instrucción.

Ejemplo:

S1; (sentencia = s)

For (int i = 0; i < N; i++)

S2;

Requiere: T(N) = t1 + t2 * N

Los algoritmos bien estructurados combinan las sentencias de algunas de las formas siguientes:

A) Sentencias sencillas. Contempla las sentencias de asignación, entrada y salida de datos y tienen una complejidad constante que se establece Orden 1 = O(1).

B) Secuencia de sentencias. La complejidad de ella es la suma de las complejidades individuales de cada una de ellas. O(1).

C) Decisión (if). Una condición es de complejidad O(1) ya sea en la rama then o en la rama else.

D) Decisión multiple (switch case). Se tomara la complejidad de la peor de las ramas.

E) Bucles de contador explicito (for). Si se realiza un numero fijo de veces independientemente de N sera el siguiente.

Ejemplo:

For ( i = 0 ; i < k; i++)

{algo de O(1)}

K * O(1) = O(1)

Dependiendo de N: ejemplo:

For (i = 0; i < N; i++)

{algo de O(1)}

N * O(1) = O(n)

F) Ciclos anidados:

Ejemplo:

For (i = 0; i < N; i++)

{For (j = 0; j<N; j++)

{algo de O(1)}

N * N * O(1) = O(n2)

G) Llamada a procedimiento. Su complejidad depende del contenido de las instrucciones que formen el cuerpo del procedimiento.

Ejemplo:

Int factorial (int n) O(1) entrada

{ int Fact = 1 O(1) asignación

for (int i = N; i > 0; i–) O(n) bucle dependiente de N

Fact = Fact * i; O(1) sentencia sencilla

Return Fact; O(1) sentencia sencilla

}

resultado complejidad mayor = O(n)

Ordenes de Complejidad:

O(1)	Constante	Ideal
O(n)	Lineal	Eficiente
O(log n)	Logaritmico	Eficiente
O(n log n)	Logaritmico	Eficiente
O(nK)	Polinomial	Tratable
O(Kn)	Exponencial	Intratable
O(n!)	Factorial	Intratable