PDF de programación - Análisis de algoritmos

Análisis de algoritmos



• Eficiencia de un algoritmo
• Técnicas de diseño de algoritmos



Bibliografía


Robert Sedgewick:
“Algorithms in C”
Addison-Wesley, 1990
ISBN 0201514257



Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman:
“Data Structures and Algorithms”
Addison-Wesley, 1983
ISBN: 0201000237

Mark Allen Weiss
“Data Structures and Algorithm Analysis in C”
Addison-Wesley, Second Edition, 1996
ISBN 0201498405

Thomas H. Cormen, Charles E. Leiserson & Ronald L. Rivest
“Introduction to Algorithms”
MIT Press, 1990
ISBN 0262031418

Giles Brassard & Paul Bratley
“Fundamentals of Algorithmics”
Prentice Hall, 1996
ISBN 0133350681

“Fundamentos de Algoritmia”
Prentice Hall, 1997
ISBN 848966000X

Eficiencia de un algoritmo

El análisis de algoritmos estudia, desde el punto de vista teórico, los
recursos computacionales que necesita la ejecución de un programa de
ordenador: su eficiencia.

p.ej. Tiempo de CPU
Uso de memoria
Ancho de banda
…


NOTA:



En el desarrollo real de software, existen otros factores que, a
menudo, son más importantes que la eficiencia: funcionalidad,
corrección, robustez, usabilidad, modularidad, mantenibilidad,
fiabilidad, simplicidad… y el tiempo del programador.



¿Por qué estudiar la eficiencia de los algoritmos?

Porque nos sirve para establecer la frontera entre lo factible y lo imposible.


Ejemplo: Algoritmos de ordenación


Observación
El tiempo de ejecución depende del tamaño del conjunto de datos.

Objetivo
Parametrizar el tiempo de ejecución en función del tamaño del conjunto
de datos, intentando buscar una cota superior que nos sirva de garantía

Tipos de análisis


Peor caso (usualmente)
T(n) = Tiempo máximo necesario para un problema de tamaño n

Caso medio (a veces)
T(n) = Tiempo esperado para un problema cualquiera de tamaño n

• Requiere establecer una distribución estadística

Mejor caso (engañoso)

Análisis de Algoritmos

1

© Fernando Berzal

Análisis del peor caso

¿Cuál es el tiempo que necesitaría un algoritmo concreto?
ß Varía en función del ordenador que utilicemos.
ß Varía en función del compilador que seleccionemos.
ß Puede variar en función de nuestra habilidad como programadores.

IDEA: Ignorar las constantes dependientes del contexto

SOLUCIÓN: Fijarse en el crecimiento de T(n) cuando n fi ¥


Notación O
O(g(n)) = { f(n) | $ c,n0 constantes positivas tales que f (n) = c g(n) "


En la práctica, se ignoran las constantes y los términos de menor peso:


3n3 + 90n2 – 5n + 6046 = O(n3)



n = n0 }

Eficiencia asintótica
Cuando n es lo suficientemente grande…

un algoritmo O(1)

es más eficiente que

es más eficiente que

es más eficiente que

es más eficiente que

es más eficiente que

es más eficiente que

un algoritmo O(log n)

un algoritmo O(n)

un algoritmo O(n log n)

un algoritmo O(n2)

un algoritmo O(n3)

un algoritmo O(2n)



NOTA:



En ocasiones, un algoritmo más ineficiente puede resultar más
adecuado para resolver un problema real ya que, en la práctica, hay
que tener en cuenta otros aspectos además de la eficiencia.

Análisis de Algoritmos

2

© Fernando Berzal

Análisis de la complejidad de un algoritmo


Propiedades de la notación O


c O(f(n)) = O(f(n))

O(f(n)+g(n)) = max{ O(f(n)), O(g(n)) }

O(f(n)+g(n)) = O(f(n)+g(n))

O(f(n))O(g(n)) = O(f(n)g(n))

O(O(f(n))) = O(f(n))


Asignaciones y expresiones simples



x = x+1;

T(n) = O(1)

Secuencias de instrucciones



I1;
I2;



T(n) = T1(n) + T2(n) = max { O(T1(n)), O(T2(n)) }

Estructuras de control condicionales (if-then-else)



T(n) = O (Tcondición(n)) + max { O(Tthen(n)), O(Telse(n)) }

Estructuras de control iterativas
Producto del número de iteraciones por la complejidad de cada iteración.
Si la complejidad varía en función de la iteración, obtenemos una sumatoria.


Si no conocemos con exactitud el número de iteraciones (bucles
while y do-while), se estima este número para el peor caso.



Algoritmos recursivos
Se obtienen recurrencias que hay que resolver…

Análisis de Algoritmos

3

© Fernando Berzal

Ejemplo: Algoritmo de ordenación por inserción

void OrdenarInsercion (double v[], int N)
{
int i, j;
double tmp;

for (i=1; i<N; i++) {

tmp = v[i];

for (j=i; (j>0) && (tmp<v[j-1]); j--)
v[j] = v[j-1];

v[j] = tmp;
}
}


Peor caso: Vector inicialmente ordenado al revés


nT
)(

=

n

1

=
1

i

nOiO
(

)(

=

2

)



Caso promedio (con todas las permutaciones igualmente probables):


nT
)(

=

n

1

=
1

i

)2/(
i

Q=

2

(

n

)



¿Es eficiente el algoritmo de ordenación por inserción?

Moderadamente sí cuando n es relativamente pequeño.

ß Absolutamente no cuando n es grande.



Análisis de Algoritmos

4

© Fernando Berzal

-
Q
-
Ejemplo: Algoritmo de ordenación por mezcla (merge-sort)

IDEA
- Dividir el vector en dos y ordenar cada mitad por separado.
- Una vez que tengamos las mitades ordenadas, las podemos ir mezclando

para obtener fácilmente el vector ordenado

// Vector auxiliar
// O(n)



IMPLEMENTACIÓN EN C

// Mezcla dos subvectores ordenados

double aux[maxN];

void merge (double v[], int l, int m, int r)
{
int i, j, k;

for (i=m+1; i>l; i--)
aux[i-1] = v[i-1];
for (j=m; j<r; j++)
aux[r+m-j] = v[j+1];

for (k=l; k<=r; k++)
if (aux[i]<aux[j])
a[k] = aux[i++];
else
a[k] = aux[j--];
}


// Algoritmo de ordenación

void mergesort (double v[], int l, int r) // T(n)
{
int m = (r+l)/2;

if (r > l) {

mergesort (v, l, m);
mergesort (v, m+1, r);
merge (a, l, m, r);

}
}

// Mezcla

// O(1)

// O(n)



// O(1)
// T(n/2)
// T(n/2)
// O(n)

Análisis de Algoritmos

5

© Fernando Berzal

ANÁLISIS


1. Mezcla de dos subvectores ordenados (merge):

2. Algoritmo de ordenación


nT
)(

=

)1(
O
+
)2/

)(
nO

nsi
nsi

(2
nT

=
>



Solución de la ecuación


nT
)(

=

nT
(2

)2/

+

n



Tmerge

)(
n

=

2nO

(

)



1
1



O(n log n) crece más despacio que O(n2)

Por tanto,



la ordenación por mezcla es más eficiente que la ordenación por inserción.



Ejercicio
Comprobar experimentalmente a partir de qué valor de n el algoritmo de
ordenación por mezcla es más rápido que el de ordenación por inserción.



Análisis de Algoritmos

6

© Fernando Berzal




Resolución de recurrencias
Se pueden aplicar distintas técnicas y trucos:

Método de sustitución

1. Adivinar la forma de la solución.
2. Demostrar por inducción.
3. Resolver las constantes.

)(
nT

=

O
nT
(4

)1(
)2/

+

n

nsi
nsi

=
>

1
1



¿T(n) es O(n3)?
Suposición
Demostramos por inducción T(n) = cn3



T(k) = ck3 para k<n



T(n) = 4T(n/2) + n



= 4c(n/2)3 + n = (c/2)n3 + n = cn3 – ((c/2)n3 – n)
= cn3 siempre que ((c/2)n3 – n)>0 (p.ej. c=2 y n=1)

PROBLEMA:



¿Podríamos encontrar una cota superior más ajustada?
Sugerencia: Probar con T(n) = cn2 y T(n) = c1n2-c2n



Árbol de recursión
Se basa en construir una representación gráfica intuitiva…


(
nT

)4/

(
nT

)2/

+

)(
nT

=

+

2

n



Análisis de Algoritmos

7

© Fernando Berzal






Expansión de recurrencias
Equivalente algebraica al árbol de recurrencias


Ejemplo: Cálculo del factorial

int factorial (int n)
{
return (n==0)? 1: n*factorial(n-1);
}

nT
)(

=

O
nT
(

)1(
+
1)1

nsi
nsi

=
>

0
1



T(n) = T(0) + n = 1 + n = O(n)

Algoritmo de orden lineal



T(n) = T(n-1) + 1



= (T(n-2)+1) + 1 = T(n-2) + 2
= (T(n-3)+1) + 2 = T(n-3) + 3
…
= T(n-k) + k



Cuando k=n:



Ejemplo: Sucesión de Fibonacci

int fibonacci (int n)
{
if ((n == 0) || (n == 1))
return 1;
else
return fibonacci(n-1) + fibonacci(n-2);
}

)(
nT

=

O
+

)1(
nT
(

nsi
nsi

1
1



>

+
1)2

(
nT

)1



T(n) = T(n-1) + T(n-2) + 1


= (T(n-2)+T(n-3)+1) + (T(n-3)+T(n-4)+1) + 1
= T(n-2) + 2T(n-3) + T(n-4) + (2+1)
= T(n-3) + 3T(n-4) + 3T(n-5) + T(n-6) + (4+2+1)
…



nT
)(

=

n

5

1
5

+
1
2

n

5

+
1
2



Análisis de Algoritmos

8

© Fernando Berzal




-



-
-
£
œ
œ
ß
ø
Œ
Œ
º
Ø


ł



Ł
-


ł



Ł
Método de la ecuación característica

Recurrencias homogéneas lineales con coeficientes constantes


T(n) = c1T(n-1) + c2T(n-2) + … + ckT(n-k)

a0tn + a1tn-1 + … + aktn-k = 0



Sustituimos tn=xn:

a0xn + a1xn-1 + … + akxn-k = 0


Ecuación característica (eliminando la solución trivial x=0):


a0xk + a1xk-1 + … + ak = 0



Obtenemos la solución a partir de las raíces del polinomio característico:


Caso 1: Raíces distintas ri



Caso 2: Raíces múltiples ri de multiplicidad mi

t

n

= k

=
1

i

n

rc
i
i



t

n

m
i

1

= l

=
1

i

=
1

j

j
rnc
ij
i

n



Finalmente, las constantes se determinan a partir de las k condiciones iniciales.



DEMOSTRACIÓN:

Aplicando el Teorema Fundamental del Álgebra,
factorizamos el polinomio de grado k como un producto de k monomios.

Si p(ri)=0,


ri es una raíz del polinomio característico
x=ri es una solución de la ecuación característica
n es una solución de la recurrencia.
ri


Cuando tenemos una raíz múltiple r de multiplicidad m, podemos llegar a la conclusión de
que rn, nrn, n2rn … nm-1rn son otras soluciones de la recurren