Tiempo de ejecución (Parte 1)

CHenry [chenry@lab.matcom.uh.cu]

Siempre un tema de gran inquietud es el tiempo de ejecución de nuestras aplicaciones aunque en los últimos tiempos se ha optado por no prestar atención a este aspecto ya que el hardware actual facilita este aspecto pero siempre es importante tener en cuenta este aspecto, para los que no lo están teniendo en cuenta aquí les va algo para que reflexionen. Al intentar abordar la solución de un problema computacionalmente tenemos siempre la disyuntiva de seleccionar entre varios algoritmos, el que resulte más conveniente, y dicha elección se realiza basándose en los siguientes aspectos, fundamentalmente:

Algoritmo fácil de: Entender (claridad) Codoficar Depurar

VS

Algoritmo que se ejecute con la mayor rapidez posible. Haciendo uso eficiente de los recursos de la máquina.

Lograr uno de estos objetivos, generalmente, implica entrar en contradicción con el cumplimiento del otro, por ello, debemos valorar los casos en que se debe priorizar, uno o el otro.

El primero, referido a la claridad, es importante cuando el programa será usado, pocas veces. En tal caso, el tiempo de programación será mayor que el costo de ejecución del programa y por tanto, debemos centrar nuestra atención en optimizar la escritura del programa. Por el contrario, ante un problema cuya solución se va a utilizar muchas veces, debemos centrar nuestra atención en optimizar el tiempo de ejecución del programa, y en este caso, el costo de ejecución del mismo será mayor que el tiempo de programación.

Medición del tiempo de ejecución de un programa.

El tiempo de ejecución de un programa depende de los siguientes factores:

• DATOS de entrada al algoritmo.
• Calidad del código objeto generado por el COMPILADOR.
• Naturaleza y rapidez de las instrucciones de máquina empleadas en la ejecución del programa (PROCESADOR).

El hecho de que el tiempo de ejecución dependa de la entrada, implica que el tiempo de ejecución debe definirse como una función de dicha entrada. Al referirnos a tal dependencia no solo nos referimos al tipo de dato, sino también, al “tamaño” de la entrada que es equivalente a hablar de la longitud de la misma, o sea, a la cantidad de datos de una entrada en específico.

T(n) es la forma de referirnos a una función, cuyo valor es aproximado, al tiempo de ejecución de un programa con una entrada de tamaño n.

Decimos aproximado, pues el cálculo del tiempo de ejecución no puede ser exacto, ya que para un mismo programa, este varía en función de diversos factores técnicos referidos al dispositivo de cómputo donde este se ejecute, así como a determinados elementos de SW.

T(n) se puede definir como el número de operaciones elementales ejecutadas en una computadora idealizada, pues el tiempo requerido para ejecutar una operación específica, varía entre las diferentes configuraciones de HW.
A partir de esta definición, no se utilizan unidades específicas para referirnos al tiempo de ejecución de un programa

En algunos casos, el tiempo de ejecución es una función que depende de las entradas específicas y no solo del tamaño de ellas.
Ejemplo: En un algoritmo de ordenación concreto, no es el mismo tiempo de ejecución para cuando los elementos a ordenar vienen completamente desordenados que cuando vienen casi ordenados

El tiempo de ejecución de un programa puede verse puntualmente, referido a cualquiera de estos tres casos y considerando un tamaño determinado de la entrada:

• Caso Peor: Situación en que el algoritmo ejecuta la mayor cantidad de operaciones para resolver el problema
• Caso Promedio: Promedio de operaciones a ejecutar para resolver el problema considerando todas las entradas posibles para un tamaño de la entrada específico.
• Caso Mejor: Situación ideal en la que el algoritmo realiza el menos número de instrucciones para resolver el problema.

Ejemplo:
Problema: Buscar la posición de un elemento en un arreglo de tamaño n, sabiendo que el mismo ya está en dicho arreglo

BUSCAR(int[ ] A, int x)
{
  for i=1 to A.Lenght          costo de esta instrucción c1
  If (A[i] = x) return i         costo de la evaluación c2. costo de retornar valor c3
}

T(n) = (C1 + C2)t + C3

Donde t, es la cantidad de veces que se ejecuta el ciclo, tÎ {1..n} y coincide con la posición del arreglo donde se encuentra el elemento. n es la longitud del arreglo.
En este ejemplo, T(n) depende del tamaño de la entrada, especialmente, de la posición donde está el elemento que se busca

Caso mejor, cuando t = 1
Caso peor, cuando t = n
Caso promedio, cuando t = (n+1)/2

El tiempo para el caso promedio es:
T(n) = P1((C1 + C2) + C3) + P2(2(C1 + C2) + C3) +...+ Pn(n(C1 + C2) + cC3)

Que se cumple cuando t es la parte entera de (n+1)/2

Aunque lo ideal sería calcular el tiempo de ejecución para el caso promedio, en la práctica se trabaja frecuentemente con el caso peor y con el mejor caso, debido a que el cálculo del caso promedio se hace difícil desde el punto de vista probabilístico, y en la inmensa mayoría de los casos es proporcional al tiempo del caso peor.

Notación asintótica: “O” grande, W Omega, q Theta

Llegamos a criterios objetivos sobre el comportamiento asintótico del tiempo de ejecución de un algoritmo analizando el comportamiento del mismo cuando el tamaño de la entrada crece y crece considerablemente

Definición 1:

T(n) es O(f(n)) si existen constantes positivas c y n0, tales que para los n >= n0 se cumple que T(n) <= cf(n)

f(n) es una cota superior para T(n)

Tomando el ejemplo del algoritmo BUSCAR anteriormente visto podemos ver que para el caso peor T(n) = O(n):
T(n) = (C1 + C2)n + C3 <= (C1 + C2 + 1)n = Cn para n >= [C3] = N0

Para el caso promedio T(n) es también O(n):

                (n + 1)        (C1 + C2)      (C1 + C2)          (C1 + C2)
T(n) = (C1+C2) --------- + C3 = --------- n + --------- + C3 <= (-------- + 1)n = Cn
                   2                2             2                2   

           (C1 + C2)   
para n >= (------- + C3) = N0
              2        

Definición 2:

T(n) es W(f(n)) si existen constantes positivas c y n0, tales que para los n >= n0 se cumple que T(n) >= cf(n)

f(n) es una cota inferior para T(n)

En el ejemplo de BUSCAR, el caso peor es W(n).

T(n) = (C1 + C2)n + C3 >= (C1 + C2)n = Cn n >= 1 = n0

Notas:
• Ver otra definición que propone el texto, donde solo exige que se cumpla la desigualdad para un número infinito de valores.
• W(f(n)) debe ser mencionada pero es mucho menos usada que la notación O.

Artículos relacionados:

Tiempo de ejecución (Parte 2)

Artículos relacionados