Clase 2 Midiendo El Tiempo De Un Algoritmo

DED4501 - Diseño de Estructuras de Datos

Midiendo el tiempo de un Algoritmo.-

Unidad de Aprendizaje N°1
Optimiza el código fuente de manera de hacer un buen
uso de los recursos del sistemaExperiencia:

¿Qué es un algoritmo?
¿Por qué debería importarme?

"Un conjunto de pasos
ordenados para realizar una
tarea"

Algoritmos en lo cotidiano
Lavarse los dientes
* Abrir la pasta
* Tomar elcepillo
* Poner pasta en el
cepillo
* Cerrar la pasta
* Cepillarse el lado
izquierdo 15
segundos
....

Algoritmos en lo cotidiano
Llegar a clases
* Salir de la casa
* Caminar al metro
* Entrar a laestación
* Apretujarse
* Golpear al de
adelante
* Subirse al carro
* Bajarse en
VespucioNorte
* Caminar al Duoc

Algoritmos computacionales
El GPS del celular.
Algoritmo de "camino
más corto"
¿Tiempo máscorto?
* Es el mismo algoritmo,
solo que los datos son
diferentes!

Algoritmos computacionales
Compra segura.
Los servidores web y
los browsers corren
algoritmos de
encriptación para
comunicarse sinque
nadie pueda leer la
información que se
envía.

¿Cómo llevar un paquete a destino?

Algoritmos con nombre.

Dijkstra

Lempel

Ziv

Algoritmo Cotidiano vs Computacional
* Acepta imprecisión:
"Si elmetro esta muy
lleno, tratar de irse en
micro"

* Debe ser muy
preciso:
¿Qué es "muy lleno"?

* El cerebro no necesita
compilar

*Debe "compilar"

* Se escriben en humano

* Se escriben en Java,
C# oPerl

¿Qué queremos de un algoritmo?
Correctitud:
Dado un problema,
debe producir
siempre una solución
correcta al problema.

Eficiencia :
Debería usar los
recursos
computacionales
disponibles enforma
eficiente (memoria,
procesador,
almacenamiento,
etc)

Correctitud.
* ¿El GPS te da el camino más corto?
* ¿O el más rápido?
* Hay algunos problemas en los que es difícil
decidir si se encuentrauna solución correcta...
ese tipo de problemas no los veremos en este
curso. (¿Algún ejemplo?)

Eficiencia
- Tiempo!
- Un algoritmo que da un
resultado correcto pero
demora demasiado, no
sirve...