Ayudantía 2

De Departamento de Informatica
Saltar a: navegación, buscar

Contenido

¡Que complejo es todo!: Complejidad algoritmica

"Beware of bugs in the code above, I have only proved to be correct, not tried" - Donald Ervin Knuth, fuente: [Wikipedia]

¿A que nos referimos cuando un algoritmo o función es de complejidad n2?. ¿Cómo decidímos si un algoritmo es mejor que otro?.

El cálculo de complejidades en los algoritmos que se desarrollan o que son utilizados para ciertos procedimientos no es un tema trivial. La confección de buenos algoritmos y con complejidades bajas hara que nuestro código se ejecute de manera más rápido y eficiente, lo que producirá mejores resulados. Sin embargo la tarea de desarrollar buenos algoritmos o calcular complejidades, no es una labor del todo fácil, se requiere una gran experticia matemática para ello y una experiencia acabada en la programación de estos.

En la presente sección se abordara el tema de cálculo de complejidades. Sin embargo el trato que se dará será de manera bastante superficial, en principal medida a que no es parte del curso conocer a cabalidad todos los mecanismos existentes para el cálculo de éstos. Se expondrán los principales mecanismos, sin embargo se desarrollará en profundidad sólo uno (claramente el más sencillo para todos).

Antes de comenzar: ¿Qué es un algoritmo?

Informalmente, un algoritmo es un procedimiento o serie de pasos, los cuales se encuentran claramente definidos, los cuales nos permiten resolver un problema en una cantidad de tiempo finita.

Podriamos observar nuestra rutina diaria, y darnos cuenta que cada acción que realizamos corresponde a un algoritmo. Por ejemplo, supongamos que es la hora de almuerzo, y como buenos estudiantes, nos dieron ganas de comer unos ricos fideos con salsa boloñeza.

Algoritmo del Fideo

Necesitamos:

- 1 paquete de fideos
- 1 paquete de salsa de tomates.
- 1/4 de carne molida

Procedimiento:

- Sacar agua de la llave y llenar un hervidor o tetera.
- Una vez que el agua este hervida, servir en una olla.
- Colocar la olla al fuego.
- Agregar sal y aceite a gusto.
- ¿Hirvio de nuevo?. Agregar los fideos.
- Sacar sarten de la alacena.
- Agregar aceite al sarten.
- Colocar sarten en el fuego.
- Freir la carne.
- ¿Está cocida la carne?. Agregar la salsa.
- ¿Hirvió la salsa?. Apagar sarten.
- ¿Están cocidos los fideos?. Apagar olla.
- Colar los fideos.
- Servir fideos en un plata. 
- Esparcir salsa sobre los fideos.
- Disfrutar.

Lo que observamos anteriormente es una receta de cocina para cocinar un rico plato de fideos con salsa (ahora la relación con el curso). Lo que observamos son una serie de pasos enmarcados en un procedimiento de preparación. Esto no es más que un algoritmo. Ahora, veamos como sería si lo hacemos en pseudocódigo.

Algoritmo del Fideo RELOADED '

variables
  fideos, salsa_tomate, carne;
inicio
 fideos := 1;
 salsa_tomate:= 1;
 carne := 0,25;
 tetera := 1;
 agua := 1000;
 llenar_tetera(agua);
 prender_tetera();
 while(estado_tetera() != 'hervido')
   ver_television();
 colocar_olla_fuego(agua);
 


Todo es recursivo: Recursión

Complejidades Reloaded: Complejidades y Recursiones

Seamos Estructurados: Tipos de Datos Estructurados

Arreglos

Estructuras

Uniones

Objetos, Objetos everywere: Programación Orientada a Objetos

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas