PDF de programación - Capítulo 1 - Análisis de la eficiencia de los algoritmos

Capítulo 1
Análisis de la eficiencia de los
algoritmos 1

No puede haber orden cuando hay mucha prisa
Seneca

Resumen: En este tema se muestra la importancia de contar con algoritmos eficien-
tes, se define qué se entiende por coste de un algoritmo y se enseña a comparar las
funciones de coste de distintos algoritmos con el fin de decidir cuál de ellos es preferi-
ble. Se define una jerarquía de órdenes de complejidad que ilustra la separación entre
algoritmos eficientes y los que no lo son.

1.

?

?

?

?

Introducción

Aproximadamente cada año y medio se duplica el número de instrucciones por se-
gundo que son capaces de ejecutar los computadores. Ello puede inducir a pensar
que basta con esperar algunos años para que problemas que hoy necesitan muchas
horas de cálculo puedan resolverse en pocos segundos.

Sin embargo hay algoritmos tan ineficientes que ningún avance en la velocidad de las
máquinas podrá conseguir para ellos tiempos aceptables. El factor predominante que
delimita lo que es soluble en un tiempo razonable de lo que no lo es, es precisamente
el algoritmo elegido para resolver el problema.

En este capítulo enseñaremos a medir la eficiencia de los algoritmos y a comparar
la eficiencia de distintos algoritmos para un mismo problema. Después de la correc-
ción, conseguir eficiencia debe ser el principal objetivo del programador. Mediremos
principalmente la eficiencia en tiempo de ejecución, pero los mismos conceptos
son aplicables a la medición de la eficiencia en espacio, es decir a medir la memoria
que necesita el algoritmo.
El siguiente programa ordena un vector a[0..n 1] por el método de selección:

1Ricardo Peña es el autor principal de este tema.

1

2

?

Capítulo 1. Análisis de la eficiencia

1 int a[n];
2 int i, j, pmin, temp;
3 for (i = 0; i < n-1; i++)
4
5 {pmin = i;
6

// pmin c a l c u l a l a p o s i c i ó n d e l mínimo de a [ i . . n1]
for

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

if (a[j] < a[pmin]) pmin = j;

// ponemos e l mínimo en a [ i ]
temp = a[i]; a[i] = a[pmin]; a[pmin] = temp;

7

8

9
10 }

Una manera de medir la eficiencia en tiempo de este programa es contar cuántas
instrucciones de cada tipo se ejecutan, multiplicar este número por el tiempo que
emplea la instrucción en ejecutarse, y realizar la suma para los diferentes tipos. Sean

ta = tiempo de una asignación entre enteros
tc = tiempo de una comparación entre enteros
ti = tiempo de incrementar un entero
tv = tiempo de acceso a un elemento de un vector

(1.1)

La línea (3) da lugar a una asignación, a n1 incrementos y a n comparaciones,
es decir, a un tiempo ta + (n 1)ti + ntc.
La línea (5) da lugar a un tiempo (n 1)ta.
El bucle interior for se ejecuta n 1 veces, cada una con un valor diferente de
i. Para cada valor de i y siguiendo el cálculo hecho para la (3), la línea (6) da
lugar a un tiempo ta + (n i 1)ti + (n i)tc.
La línea (7) da, para cada valor de i, un tiempo mínimo de (n i 1)(2tv + tc),
suponiendo que la instrucción pmin = j nunca se ejecuta. A ello hay que sumar
(n i 1)ta en el caso más desfavorable en que dicha rama se ejecute todas las
veces. El caso promedio tendrá un tiempo de ejecución entre estos dos.
Finalmente, la línea (9) dará lugar a un tiempo (n 1)(4tv + 3ta).
Por tanto, el tiempo del bucle interior for, en el caso más desfavorable, se
calcula mediante el siguiente sumatorio:

(ta + tc + (n i 1)(ti + 2tv + ta + 2tc)) = P (n 1) +

1
2 Qn(n 1)

n2Xi=0

siendo P = ta + tc y Q = ti + 2tv + ta + 2tc.

Para no cansar al lector con tediosos cálculos, concluiremos que la suma de todos
estos tiempos da lugar a dos polinomios de la forma:
Tmin = An2 Bn + C
Tmax = A0n2 B0n + C0

donde A, A0, B, B0, C y C0 son expresiones racionales positivas que dependen lineal-
mente de los tiempos elementales descritos en 1.1.

?

En este sencillo ejemplo se observan claramente los tres factores de los que en general
depende el tiempo de ejecución de un algoritmo:

Estructura de Datos y Algoritmos

2. Medidas asintóticas de la eficiencia

3

1. El tamaño de los datos de entrada, simbolizado aquí por la longitud n del

vector.

2. El contenido de los datos de entrada, que en el ejemplo hace que el tiempo
para diferentes vectores del mismo tamaño esté comprendido entre los valores
Tmin y Tmax .

3. El código generado por el compilador y el computador concreto utilizados,

que afectan a los tiempos elementales 1.1.

?

Como el objetivo es poder comparar algoritmos independientemente del valor de los
datos de entrada, el segundo factor podemos eliminarlo de dos maneras:

O bien midiendo solo el caso peor, es decir la ejecución que tarde más tiempo
de todos los ejemplares de tamaño n.
O bien midiendo todos los casos de tamaño n y calculando el tiempo del caso
promedio.

En esta asignatura nos concentraremos en el caso peor por dos razones:

1. El caso peor establece una cota superior fiable para todos los casos del mismo

tamaño.

2. El caso peor es más fácil de calcular.

El caso promedio es más difícil de calcular pero a veces es más informativo. Además
exige conocer la probabilidad con la que se va a presentar cada caso. Muy raramente
puede ser útil conocer el caso mejor de un algoritmo para un tamaño n dado. Ese
coste es una cota inferior al coste de cualquier otro ejemplar de ese tamaño.

?

?

El tercer factor impediría comparar algoritmos escritos en diferentes lenguajes, tra-
ducidos por diferentes compiladores, o ejecutados en diferentes máquinas. El criterio
que seguiremos es ignorar estos factores.

Por tanto solo mediremos la eficiencia de un algoritmo en función del tamaño de
los datos de entrada. Este criterio está en la base de lo que llamaremos medida
asintótica de la eficiencia.

2. Medidas asintóticas de la eficiencia

?

El criterio asintótico para medir la eficiencia de los algoritmos tiene como objetivo
comparar algoritmos independientemente de los lenguajes en que están escritos,
de las máquinas en que se ejecutan y del valor concreto de los datos que reciben
como entrada. Tan solo considera importante el tamaño de dichos datos. Para cada
problema habrá que definir qué se entiende por tamaño del mismo.

?

Se basa en tres principios:

1. El coste o eficiencia es una función que solo depende del tamaño de la entrada,

e.g. f(n) = n2.

2. Las constantes multiplicativas o aditivas no se tienen en cuenta, e.g. f(n) = n2

y g(n) = 3n2 + 27 se consideran costes equivalentes.

Facultad de Informática - UCM

4

?

?

?

?

?

?

?

Capítulo 1. Análisis de la eficiencia

3. La comparación entre funciones de coste se hará para valores de n suficien-
temente grandes, es decir los costes para tamaños pequeños se consideran
irrelevantes.

Sea N el conjunto de los números naturales y R+ el conjunto de los reales estricta-
mente positivos.

Definición 1.1 Sea f : N ! R+ [{ 0}. El conjunto de las funciones del orden de
f(n), denotado O(f(n)), se define como:

O(f(n)) = {g : N ! R+ [{ 0} |9 c 2 R+, n0 2 N . 8n n0 . g(n)  cf(n)}

Asímismo, diremos que una función g es del orden de f(n) cuando g 2O (f(n)).
También diremos que g está en O(f(n)).

cf(n)
g(n)

Generalizando, admitiremos también que una función negativa o indefinida para un
número finito de valores de n pertenece al conjunto O(f(n)) si eligiendo n0 suficien-
temente grande, satisface la definición.

Esta garantiza que, si el tiempo de ejecución g(n) de una implementación concreta
de un algoritmo es del orden de f(n), entonces el tiempo g0(n) de cualquier otra
implementación del mismo que difiera de la anterior en el lenguaje, el compilador,
o/y la máquina empleada, también será del orden de f(n). Por tanto, el coste O(f(n))
expresa la eficiencia del algoritmo per se, no el de una implementación concreta del
mismo.
Las clases O(f(n)) para diferentes funciones f(n) se denominan clases de comple-
jidad, u órdenes de complejidad. Algunos órdenes tienen nombre propio. Así, al
orden de complejidad O(n) se le llama lineal, al orden O(n2), cuadrático, el orden
O(1) describe la clase de las funciones constantes, etc. Eligiremos como represen-
tante del orden O(f(n)) la función f(n) más sencilla posible dentro del mismo.
Nótese que la definición 1.1 se puede aplicar tanto a un análisis en el caso peor, como
a un análisis en el caso promedio. Por ejemplo, hay algoritmos cuyo coste en tiempo
está en O(n2) en el caso peor y en O(n log n) en el caso promedio.
Nótese también que las unidades en que se mide el coste en tiempo (horas, segundos,
milisegundos, etc.), o en memoria (octetos, palabras, celdas de longitud fija, etc.) no
son relevantes en la complejidad asintótica: dos unidades distintas se diferencian
en una constante multiplicativa (e.g. 120 n2 segundos son 2 n2 minutos, ambos en
O(n2)).
Aplicando directamente la definición de O(f(n)), demostremos que (n+1)2 2 O(n2).
Un modo de hacerlo es por inducción sobre n. Elegimos n0 = 1 y c = 4, es decir
demostraremos 8n 1 . (n + 1)2  4n2:

Estructura de Datos y Algoritmos

2. Medidas asintóticas de la eficiencia

5

Caso base: n = 1, (1 + 1)2  4 · 12
Paso inductivo: h.i. (n + 1)2  4n2. Demostrémoslo para n + 1:

(n + 1 + 1)2  4(n + 1)2
(n + 1)2 + 1 + 2(n + 1)  4n2 + 4 + 8n
(n + 1)2  4n2 + 6n + 1
| {z }0
También podemos probar que 3n 62 O(2n). Si perteneciera, existiría c 2 R+, n0 2 N
tales que 3n  c · 2n para todo n n0. Esto implicaría que ( 3
2)n  c para todo
n n0. Pero esto es falso porque dado un c cualquiera, bastaría tomar n > log1,5 c
para que ( 3
2)n no se puede acotar superiormente.
La notación O(f(n)) nos da una cota superior al tiempo de ejecución t(n) de un
algoritmo. Normalmente estaremos interesados en la menor función f(n) tal que
t(n) 2O (f(n)). Una forma de realizar un análisis más completo es encontrar además
la mayor función g(n) que sea una cota inferior de t(n). Para ello introducimos la
siguiente medida.

2)n > c, es decir ( 3

Definición 1.2 Sea f : N ! R+ [{ 0}. El conjunto ⌦(f(n)), leído omega de f(n),
se define como:

⌦(f(n)) = {g : N ! R+ [{ 0} |9 c 2 R+, n0 2 N . 8n n0 . g(n) cf(n)}