PDF de programación - Capitulo 1 - Tema 2: Tiempo de ejecución. Notaciones para la Eficiencia de los Algoritmos

Capitulo 1

Tema 2: Tiempo de ejecucion. Notaciones

para la Eficiencia de los Algoritmos



La eficiencia de los algoritmos. Metodos para evaluar la eficiencia.

Es natural preguntarse a estas alturas que unidad habra que usar para expresar
la eficiencia teorica de un algoritmo. Independientemente de cual sea la medida que
nos evalue la bondad (la eficiencia) de un algoritmo, hay tres metodos de calcular
estas medidas:

a) El enfoque empirico (o a posteriori) consiste en programar los algoritmos
candidatos y correrlos en diferentes casos con la ayuda de un ordenador.

b) El enfoque teorico (o a priori), consiste en determinar matematicamente la
cantidad de recursos necesarios para cada algoritmo, como una funcion del tamaño
de los casos considerados. La ventaja del enfoque teorico es que no depende del
ordenador que se use, ni del lenguaje de programacion empleado.

c) El enfoque hibrido, en el que la forma de la funcion que describe la eficiencia
del algoritmo se determina teoricamente, y entonces cualquier parametro numerico
que se necesite se determina empiricamente sobre un programa y una maquina
particulares. Este enfoque permite hacer predicciones sobre el tiempo que una
implementacion determinada tomara en resolver un caso mucho mayor que el que se ha
considerado en el test. Si tal extrapolacion se hace aisladamente en base al test
empirico, ignorando todas las consideraciones teoricas, sera menos precisa, por no
decir poco ajustada.

En todo lo que sigue emplearemos el enfoque teorico o "a priori", y desde este
punto de vista la seleccion de la unidad para medir la eficiencia de los algoritmos la
vamos a encontrar a partir del denominado Principio de Invarianza. Segun este
Principio dos implementaciones diferentes de un mismo algoritmo no diferiran en
eficiencia mas que, a lo sumo, en una constante multiplicativa. Mas precisamente, si
dos implementaciones consumen t1(n) y t2 (n) unidades de tiempo,
respectivamente, en resolver un caso de tamaño n, entonces siempre existe una
constante positiva c tal que t1(n) £
ct2(n), siempre que n sea suficientemente grande.
Este Principio es valido, independientemente del ordenador usado, del lenguaje de
programacion empleado y de la habilidad del programador (supuesto que no
modifica el algoritmo). Asi, un cambio de maquina puede permitirnos resolver un
problema 10 o 100 veces mas rapidamente, pero solo un cambio de algoritmo nos
dara una mejora de cara al aumento del tamaño de los casos.


Parece por tanto oportuno referirnos a la eficiencia teorica de un algoritmo en
terminos de tiempo. En este contexto algo que conocemos de antemano es el
denominado Tiempo de Ejecucion de un programa. Como se sabe este tiempo de
ejecucion depende de factores tales como,

a) El input del programa

b) La calidad del codigo que genera el compilador que se use para la creacion del
programa,

c) La naturaleza y velocidad de las instrucciones en la maquina que se este
empleando para ejecutar el programa, y

d) La complejidad en tiempo del algoritmo que subyace en el programa.

Los apartados b) y c) son dificiles de tener en cuenta de cara a buscar una medida
objetiva, mediante la cual podamos comparar todos los algoritmos
correspondientes a un mismo programa. Volveremos sobre ello mas adelante. Sin
embargo, el hecho de que un tiempo de ejecucion dependa del input nos indica que ese
tiempo debe definirse en funcion de dicho input. Pero a menudo el tiempo de
ejecucion no depende directamente del input, sino del tamaño de este (un ejemplo de
esto puede ser cualquier algoritmo de ordenacion). Por tanto es usual notar T(n) el
tiempo de ejecucion de un programa para un input de tamaño n, y tambien para el del
algoritmo en el que se basa.

Volviendo ahora a la cuestion de la unidad a usar para expresar el tiempo de
ejecucion de un algoritmo, y por tanto a lo anotado en los anteriores puntos b) y c):
no habra tal unidad, pero haremos uso de una constante para acumular en ella todos
los factores relativos a esos aspectos de calidad, naturaleza y velocidad aludidos.

Diremos que un algoritmo consume un tiempo de orden t(n), para una funcion
dada t, si existe una constante positiva c y una implementacion del algoritmo capaz de
resolver cualquier caso del problema en un tiempo acotado superiormente por ct(n)
segundos, donde n es el tamaño (o eventualmente el valor, para problemas
numericos) del caso considerado. El uso de segundos en esta definicion es obviamente
mas que arbitrario, ya que solo necesitamos cambiar la constante para expresar el
tiempo en dias o años. Por el Principio de Invarianza cualquier otra implementacion del
algoritmo tendra la misma propiedad, aunque la constante multiplicativa puede cambiar
de una implementacion a otra.

Esa constante multiplicativa (a la que luego aludiremos como "oculta") usada en
estas definiciones puede provocar un cierto peligro de mala interpretacion.
Consideremos, por ejemplo, dos algoritmos cuyas implementaciones en una maquina
dada, consumen respectivamente n2 dias y n3 segundos para resolver un caso de
tamaño n. Es solo en casos que requieran mas de 20 millones de años para resolverlos,
donde el algoritmo cuadratico puede ser mas rapido que el algoritmo cubico. En
cualquier caso, el primero es asintoticamente mejor que el segundo, es decir, su
eficiencia teorica es mejor en todos los casos grandes, aunque desde un punto de vista
practico el alto valor que tiene la constante oculta recomiende el empleo del cubico.




Notaciones O y W

Para poder comparar los algoritmos empleando los tiempos de ejecucion que mas
arriba hemos justificado, y las constantes acumuladoras de efectos tecnologicos, se
emplea la conocida notacion asintotica, segun la cual un algoritmo con un tiempo de
ejecucion T(n) se dice que es de orden O(f(n)) si existe una constante positiva c y un
numero entero n0 tales que


" n ‡

n0

T(n) £

cf(n)


Asi, decimos que el tiempo de ejecucion de un programa es O(n2), si existen dos
constantes positivas c y n0 tales que


" n ‡

n0

T(n) £

c n2


Mas concretamente, supongamos por ejemplo que T(0) = 1, T(1) = 4 y que, en
general, T(n) = (n+1)2 . Entonces T(n) es O(n2), puesto que si tomamos n0 = 1 y c = 4,
se verifica que


" n ‡

1

(n+1)2 £

4 n2


En lo que sigue supondremos que todas las funciones de tiempos de ejecucion estan
definidas sobre los enteros no negativos, y que sus valores son no negativos,
aunque no necesariamente enteros. Asi mismo, si un algoritmo tiene un tiempo de
ejecucion O(f(n)), a f(n) le llamaremos Tasa de Crecimiento.

Asi queda claro que cuando T(n) es O(f(n)), lo que estamos dando es una cota
superior para el tiempo de ejecucion, que siempre referiremos al peor caso del
problema en cuestion. De manera anloga, podemos definir una cota inferior
introduciendo la notacion W
(g(n)) si existen dos
constantes positivas k y m0 tales que


(n). Decimos que un algoritmo es W

" n ‡

m0

T(n) ‡

kg(n)


Es de destacar la asimetria existente entre estas dos notaciones. La razon por la cual
tal asimetria es a menudo util, es que hay muchas ocasiones en las que un algoritmo es
rapido, pero no lo es para todos los inputs, por lo que interesa saber lo menos que
hemos de estar dispuestos a consumir en tiempo para resolver cualquier caso del
problema.

En definitva supondremos que los algoritmos podemos evaluarlos comparando sus
tiempos de ejecucion, despreciando sus constantes de proporcionalidad. Bajo esta
hipotesis, un algoritmo con tiempo de ejecucion O(n2) es mejor por ejemplo que uno
con tiempo de ejecucion O(n3). A pesar de los factores constantes debidos al
compilador y a la maquina (a las cuestiones tecnologicas en resumen), ademas hay un
factor constante debido a la naturaleza del algoritmo en si mismo. Es posible que, a la
hora de las implementaciones, que con una combinacion especial compilador-
maquina, el primer algoritmo consuma 100n2 milisg., y el segundo 5n3 milisg, entonces

¿no podria ser mejor el algoritmo cubico que el cuadratico?. La respuesta esta en
funcion del tamaño de los inputs que se esperan procesar. Para inputs de tamaños n <
20, el algoritmo cubico sera mas rapido que el cuadratico. Por tanto, si el algoritmo se
va a usar con inputs de gran tamaño, realmente podriamos preferir el programa
cubico. Pero cuando n se hace grande, la razon de los tiempos de ejecucion, 5n3 /100n2
= n/20, se hace arbitrariamente grande. Asi cuando el tamaño del input aumenta, el
algoritmo cubico tomara de forma significativa mas tiempo que el algoritmo
cuadratico. Incluso si hay unos cuantos inputs grandes en el conjunto de los
problemas que han de resolver estos dos algoritmos, podemos sentirnos mas comodos
con el algoritmo de menor tasa de crecimiento.

El argumento que acabamos de emplear, referente a la razon existente entre las tasas
de crecimiento, sugi