Nos vemos hoy Martes 21 de Febrero en el salón de clase para hacerles entrega de sus notas.
Acabo de enviar un correo con el archivo de notas actualizado.
martes, febrero 21, 2006
lunes, febrero 20, 2006
Por fin las Notas
Bueno, finalmente terminé de calificar los dos talleres que faltaban y acabo de enviar un e-mail con las tan anheladas notas.
Estaré pendiente de sus comentarios. Estén pendientes de la hora en que nos encontraremos mañana martes para dejar listo el asunto de las notas.
Suerte...
Estaré pendiente de sus comentarios. Estén pendientes de la hora en que nos encontraremos mañana martes para dejar listo el asunto de las notas.
Suerte...
miércoles, febrero 15, 2006
Mejor Caso, Peor Caso y Caso Promedio
El análisis de un algoritmo no necesariamente implica encontrar el tiempo exacto o el orden del tiempo del algoritmo para cualquier entrada. Usualmente basta con analizar casos extremos: el mejor y el peor. El mejor caso, es aquel en el que el algoritmo utiliza la menor cantidad de recursos (tiempo, por ejemplo) para solucionar el problema; mientras que el peor caso es aquel en el que el algoritmo utiliza la mayor cantidad de recursos para encontrar la solución.
Nótese que aunque se diga "el mejor caso", no significa que haya una, y sólo una, entrada para la cual el algoritmo se ejecuta en el menor tiempo posible. Un argumento similar se tiene para "el peor caso".
Por ejemplo para Insertion-Sort el mejor caso ocurre cuando el arreglo de entrada está ordenado ya que no debe desplazar ningún elemento, en este caso el tiempo del algoritmo es de orden lineal; el peor caso ocurre cuando el arreglo de entrada está en orden inverso porque en cada iteración debe desplazar todos los elementos que están antes del elemento a insertar, en este caso, el tiempo del algoritmo es de orden cuadrático.
Para el análisis del caso promedio, se impone (si no se conoce) una distribución de probabilidad sobre las entradas del algoritmo, usualmente tal distribución corresponde a una uiforme, es decir, se asume que todas las entradas tienen la misma probabilidad de ocurrir, cuando se aplica dicho enfoque al análisis de Insertion-Sort se encuentra que el tiempo promedio tiene el mismo orden que el peor caso.
A partir de esta pequeña explicación, se deja como tarea responder las siguientes dos preguntas:
Nótese que aunque se diga "el mejor caso", no significa que haya una, y sólo una, entrada para la cual el algoritmo se ejecuta en el menor tiempo posible. Un argumento similar se tiene para "el peor caso".
Por ejemplo para Insertion-Sort el mejor caso ocurre cuando el arreglo de entrada está ordenado ya que no debe desplazar ningún elemento, en este caso el tiempo del algoritmo es de orden lineal; el peor caso ocurre cuando el arreglo de entrada está en orden inverso porque en cada iteración debe desplazar todos los elementos que están antes del elemento a insertar, en este caso, el tiempo del algoritmo es de orden cuadrático.
Para el análisis del caso promedio, se impone (si no se conoce) una distribución de probabilidad sobre las entradas del algoritmo, usualmente tal distribución corresponde a una uiforme, es decir, se asume que todas las entradas tienen la misma probabilidad de ocurrir, cuando se aplica dicho enfoque al análisis de Insertion-Sort se encuentra que el tiempo promedio tiene el mismo orden que el peor caso.
A partir de esta pequeña explicación, se deja como tarea responder las siguientes dos preguntas:
- ¿Por qué se prefiere, en general, el tiempo de peor caso de un algoritmo en vez del caso promedio?
- ¿Qué entradas representan el mejor y el peor caso de Merge-Sort?
Suscribirse a:
Entradas (Atom)
