Algoritmos

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 unproblema 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?
Parasaber 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 losnú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ómomedir 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 datosde 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);
}
}

Complejidadalgorí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 derecurrencia 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 −...