Ingeniería del software

Para cualquier tiempo de ejecución que se desea determinar siempre se asumirá el peor de los casos.

Sea el siguiente ejemplo :

(1) suma = 0

(2) for (i=1; i<= n; i++)

(3) suma += i;

La instrucción (1) ocupa una unidad de tiempo.

La instrucción (3) ocupa dos unidades de tiempo, una para la suma y otra para la asignación, y es ejecutada N veces, por lo que ocupa 2N unidades de tiempo.

La instrucción (2) tiene involucrada una asignación que utiliza una unidad de tiempo, N+1 comparaciones y N incrementos, por lo que ocupa 2N+2 unidades de tiempo.

El tiempo total del algoritmo es T(N) = 1+2N+2+2N, esto es : T(N) = 4N + 3

De otra forma se podría ver como la existencia de tiempos para cada una de las posibles operaciones individuales, así : Ta – Tiempo de asignación, Tc – Tiempo de comparación, To – Tiempo de operación, Ti – Tiempo de incremento.

La instrucción (1) posee Ta

La instrucción (3) posee un Ta y un To.

La instrucción (2) posee un Ta para i=1, Tc para i<=n, Ti para i++

Con base en estas valoraciones los tiempos serían así para el ciclo for las instrucciones internas se hacen la cantidad de veces que indique el ciclo, la instrucción interna tarda (Ta + To) el ciclo se realiza n-veces, lo cual indica un tiempo de n(Ta+To), ahora el ciclo realiza n veces el incremento de i++ es decir n(Ti) y las comparaciones son n+1 ya que el ciclo debe llegar hasta n+1 para que el ciclo pueda terminar, es por ello que es (n+1)Tc, y falta la asignación de i=1 es decir Ta, el tiempo total del algoritmo es : T(n) = n(Ta + To) + n(Ti) + (n+1)Tc + Ta + Ta, el total eliminando las agrupaciones es : n(Ta) + n(To) + n(Ti) + n(Tc) + Tc + Ta + Ta, factorizando n(Ta + To + Ti + Tc) + Tc + Ta + Ta, se aplica que cada uno de los tipos de operación tarda una unidad de tiempo, esta difiere en cada computador, por ello se toma general para este caso lo asumimos con valor 1, por ello sería el total final n(4) + 3, es decir el tiempo

T(n) = 4n + 3.

La pretensión de la segunda forma de evaluación es que se determine cuanto tiempo se tarda en cada uno de los tipos de operación, en caso de ser necesario.

Para simplificar el estudio de la complejidad, se han adoptado ciertas convenciones en su notación, una de ellas es el concepto de orden, que indica, de forma simple, el grado de complejidad de un algoritmo sin considerar por completo la función de tiempo.

Sea el siguiente algoritmo :

for (i=1; i<n; i++)

for (j=i+1; j<=n; j++)

if (vec[i] <= vec[j])

{

temp = vec[i];

vec[i] = vec[j];

vec[j] = temp;

}

El anterior algoritmo lo pueden reconocer como el ordenamiento de burbuja, el cual posee una función de tiempo de n(n-1)/2, la demostración de este valor se deja como ejercicio para el lector, esto es igual a (n² – n)/2, y se dice que es de orden n² , o simplemente O(n²). Para determinar el orden un algoritmo, a partir de su función de tiempo, se eliminan todos los términos excepto el de mayor grado y se eliminan todos los coeficientes del término mayor.

Existen algunas reglas que son útiles para determinar el orden de un algoritmo:

Regla 1 (Ciclos FOR) : El tiempo de ejecución de un ciclo FOR es al menos el tiempo de ejecución de las instrucciones dentro de él multiplicado por el número de iteraciones.

Ejemplo : Para orden O(n).

for (i=1; i<=n; i++)

suma += i;

La función de tiempo para el algoritmo es T(N) = 4N+2, ya que ciclo ocupa 2n+2 y la sumas 2n, por lo que tiene un orden O(n).

Regla 2 (Ciclos FOR anidados) : Se analiza desde dentro hacia fuera. El tiempo de una instrucción dentro de un conjunto de ciclos anidados es igual al tiempo de ejecución de las instrucciones internas multiplicado por el producto del tamaño de los ciclos.

Ejemplo : Para orden O(n²)

for (i=1; i<=n; i++)

for (j=1; j<=n; j++)

suma += i*j;

Regla 3 (Condicional) : El tiempo de ejecución nunca es mayor que el tiempo de ejecución de la condicional más el mayor de los tiempos de ejecución de las alternativas.

Ejemplo : Algoritmo es O(n²)

If (i==j)

for (i=1; i<=n; i++)

suma += i;

else

for (i=1; i<=n; i++)

for (j=1; j<=n; j++)

suma += i*j;

Debido a que el tiempo de ejecución de la condición es de orden O(1) más el mayor tiempo de ejecución de las alternativas : cuando se cumple la condición es o(n) y cuando no se cumple es O(n²), por lo cual el orden es O(1) + O(n) + O(n²), pero, como ya se ha dicho, solo se toma el mayor, quedando el orden del programa en O(n²).

A los algoritmos de orden n se les llama de orden lineal, los de n² de orden cuadrado, etc.

Se puede decir que un algoritmo tiene complejidad polinomial, o se ejecuta en tiempo polinomial, si tiene un orden O(n^x). Estos algoritmos se dice que son algoritmos eficientes y los problemas que se resuelven con estos algoritmos se dice son problemas tratables.

Un algoritmo tiene complejidad exponencial si la función de tiempo T(n) tiene un orden O(xⁿ). Los problemas que se resuelven usando algoritmos de tiempo exponencial se conocen como problemas intratables y a los algoritmos como algoritmos ineficientes.

Ejemplo : El problema de las Torres de Hanoi tiene complejidad exponencial de orden 2ⁿ. El algoritmo es el siguiente :

Sea M(n) el valor medio del tiempo de ejecución de todas las entradas de tamaño n. Para este caso se define los siguientes elementos :

Dn – conjunto de entradas de tamaño n.

T(i) – número de operaciones básicas correspondientes a la entrada I <- Di

P(n) - Tiempo de ejecución en el peor de los casos

P(n) = Max(T(i), V I ? Dn)

En la practica casi siempre es más difícil determinar el tiempo de ejecución promedio que el del peor caso, pues si las p(i) no son iguales, cosa que normalmente ocurre, el análisis se hace intratable en matemáticas, y la noción de entrada "promedio" puede carecer de un significado claro.

Para el caso de la búsqueda secuencial.

i=1

mientras ((i=n) and (A[i] <> x)) haga

i = i + 1

fin mientras

En forma general P(n) es n si se toma como operación la comparación de elementos del arreglo.

Vector A.

Sea q la probabilidad de x estar en el vector, significando con la entrada I – iesima que el elemento x ocupa la posición iesima.

Los valores de p(I) son iguales :

q (probabilidad de que el elemento este en la lista) en (i) número de iteraciones realizadas para encontrar (x).

(1-q) (probabilidad de que el elemento no este en la lista) en (n) número de iteraciones posibles en el vector. Este valor de determina por el principio básico de la estadística de un valor máximo (100%) corresponde a uno (1).

Trabajo practico ( Ejercicio : Medición de los tiempos de asignación, operación, comparación e incremento)

Métricas Técnicas. Estas se presentan en el libro de Ingeniería del software de Pressman página 58. Estas métricas se derivan de una relación empírica según las medidas contables del dominio de información del software y de evaluaciones de complejidad. Ejemplo,

Número de salidas usuario – cada una de las salidas de datos.

Número de peticiones usuario – cada generación de un evento.

Número de archivos – cada tabla, archivo, …

Número de interfaces externas – son interfaces, discos, copias de seguridad, transmisiones de datos.

Estas métricas poseen un modelo de valoración entre cero (0) y cinco (5), y por decisión del equipo de trabajo, se puede asumir una valoración en porcentajes como se muestra en la tabla siguiente así :

Esta valoración es usada para calificar 15 puntos de evaluación :