introducción a la computación - dc.uba.ar · pdf file¿cómo medir...

Introducción a la computación

Charlie

Complejidad algorítmica

¿Qué es la complejidad algorítmica?

Es el análisis del consumo de recursos de un algoritmo en función del tamaño de la entrada. En general, los dos aspectos más relevantes a analizar son el tiempo y el espacio.

Complejidad algorítmica

¿Por qué estudiar complejidad algorítmica?

Porque saber cuánto cuesta resolver un problema con un algoritmo nos da un mecanismo para comparar y elegir concientemente la forma más eficiente de hacerlo.

Complejidad algorítmica

¿Cómo medir la complejidad de un algoritmo?

Para saber cuanto cuesta resolver un problema lo que haremos será contar las operaciones (independientemente de el tiempo que tomen puesto que queremos una métrica que aplique a cualquier computadora) que realiza el algoritmo en cuestión.

Complejidad algorítmica

¿Cómo medir la complejidad de un algoritmo?

De esta forma, el costo de un algoritmo estará determinado por una “función” en los números naturales. Es decir, una “función” que evaluada sobre el tamaño de una entrada particular, nos da “la cantidad” de operaciones que el algoritmo realizará.

Complejidad algorítmica

¿Cómo medir la complejidad de un algoritmo?

Ahora bien, no vamos a mirar los detalles de esa suma sino que vamos a usar una técnica que nos da un modelo formal del costo en función del tamaño de los datos de entrada.

Complejidad algorítmica

¿Y qué haremos con las funciones recursivas?

int factorial (int i){if (i == 0) { return 1;}else{ return i*factorial(i-1);}

}

Complejidad algorítmica

¿Y qué haremos con las funciones recursivas?

int factorial (int i){if (i == 0) { return 1;}else{ return i*factorial(i-1);}

}

Ecuaciones de recurrencia

Las ecuaciones de recurrencia no son más que una caracterización del costo necesario para resolver un problema a partir del costo que toma resolver los subproblemas.

Para el caso de la función factorial,

T (n) = T (n! 1) + f(n)

Complejidad algorítmica

Veamos otro ejemplo...

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

}

No se van a ganar la medalla Fields por esto...

T (n) = T (n! 1) + T (n! 2) + f(n)

Resolución

• Por sustitución

• Usando el teorema maestro

Hay dos formas de resolver ecuaciones de recurrencia...

Método de sustitución

Dado T(n), se trata de imaginar una función que sirva para caracterizar la clase O a la que nuestro programa pertenece...

Método de sustitución.T (n) = 2 ! T

!n

2

"+ nSea quiero probar que T (n) ! O(n " log(n))

Luego, deberé probar por inducción que:

0 ! T (i) ! c " (i " log(i))n < iExisten c, n tal que, para todo i,

implica

Método maestro

El teorema maestro nos da una herramienta que nos permite resolver recurrencias de la forma:

T (n) = a ! T!n

b

"+ f(n)

Teorema maestro

T (n) !

!""#

""$

!(nlogb a) , si f(n) ! O(nlogb a!!) y ! > 0.!(nlogb a " log n) , si f(n) ! !(nlogb a).!(f(n)) , si f(n) ! "(nlogb a+!), ! > 0 y

a " f%

nb

&# c " f(n) para algun c > 1.

Sean a ≥ 1 y b > 1 constantes, sea f (n) una función, y sea T (n) definido sobre los enteros no negativos por la recurrencia

Entonces T (n) puede ser acotado asintóticamente como sigue.

T (n) = a ! T!n

b

"+ f(n)

Resumen- Complejidad algorítmica

- Ecuaciones de recurrencia

- Teorema maestro

Cormen, 2001 “Introduction to algorithms”, MIT Press.