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?
13 comentarios:
respecto a las notas, cuando empieza su publicación y hasta cuando se puede enviar este taller
......................................................................................................
Las notas empezarán a aparecer mañana Sábado.
Las tareas que deje aquí, tienen como fecha última, en principio, el Martes 21 de Febrero a las 4:00 a.m.
Recuerden, que espero respuestas sencillas, así que no es necesario que hagn trabjaos, con portadas y demás cosas propias de ese tipo de documentos. Es suficiente con un correo o con un post en el blog.
profe donde va a publicar. aqui o en donde o envia al correo?
1.
Bueno respecto al primer punto,se prefiere tener el tiempo del peor caso para saber cuál sería la mayor cantidad de recursos en tiempo que requiere el algoritmo para el ordenamiento, es decir, para conocer cuánto es lo máximo que podemos esperar; en general se utiliza este método con los diferentes algoritmos de ordenamiento para saber cuál sería el de mejor rendimiento en el peor caso, según el tipo de entrada o de arreglo o de elementos que querramos ordenar.
2.
Para Merge Sort, la mejor entrada es cualquiera siempre y cuando cuando el arreglo sea menor o igual a 1 pues el tiempo de ejecución es de (theta)1; el peor caso depende realmente del tamaño del arreglo por las operaciones de división y unión de las sub-partes del arreglo.
Diego Franco
256350
1.Cuando uno analiza un algoritmo, es bueno saber cual es su peor y su mejor caso, pero primordialmente el peor caso, ya que con este podemos determinar los recursos necesarios para la ejecución del mismo y sabiendo que es el peor entonces los demas casos podran ser suplidos con los mismos recursos.
2.no importa las entradas el peor y el mejor caso gastan el mismo tiempo que es del orden de O(n*Ln(n)) por lo que al dividir hasta tener arreglos de tamaño 1 respresenta siempre hacer el mismo número de comparaciones y combinaciones para cualquier entrada.
cod: 256920
oscar sanchez
PARA EL PUNTO PRIMERO...
Se puede decir que el análisis de tiempo en el peor caso de ejecución es más tenido en cuenta que el caso promedio debido al uso de recursos que hace el algoritmo de la máquina; pues es mejor contar con una holgura (con respecto al peor tiempo de ejecución) para manejo de posibles problemas por recursos físicos o virtuales; además el análisis de caso promedio se basa en un cálculo de probabilidades que en la mayoría de casos se cumple (distribución uniforme), pero también se puede dar el caso en que el algoritmo requiera de un análisis estocástico y que se esté dando como obvio que la distribución que siempre va a seguir es la uniforme; mientras que en el peor caso su análisis es matemático que es "más exacto" que el análisis del caso promedio.
PARA EL SEGUNDO PUNTO...
Tenemos que el orden de ejecución del algoritmo obedece a O(n*log(n)) con respecto a n, número de elementos a ordenar. Merge-sort parte el arreglo o vector principal en dos (vector de posiciones pares y otro de impares) que serán ordenados y después unidos de nuevo. Para el análisis del mejor o del peor caso; se puede decir que esto es independiente pues necesariamente se va a partir el vector en dos para poder ser ordenado por este método, aunque genera más eficiencia si el arreglo entra ordenado, por lo menos en teoría, pues en la práctica son similares los tiempos de ejecución.
William Damián Guevara M.
Código: 256785
1. El peor caso nos da una perspectiva de los recursos, específicamente el tiempo, que tomará el algoritmo para completar una tarea en términos de la entrada. Este tiempo se toma como referente al momento de comparar diversos algoritmos dado que nos da un limite superior para el tiempo de ejecución, el tiempo promedio no nos da una cota sino el tiempo para la mayoría de casos lo que no nos da certeza del tiempo maximo para todos los casos.
2.
En general para todas las entradas el tiempo es de orden O(nlgn), en este caso el mejor, peor y caso promedio tienen el mismo orden.
Att:
Christian Ariza
256848
1.
Es mas importante obtener el tiempo para el peor caso que para el caso promedio ya que con este se consigue saber el consumo máximo de recursos y permite tener una holgura. Además al obtener el caso promedio, se está trabajando sobre una probabilidad que además de no tener el mismo nivel de exactitud, esta representando a la mayoria de los casos, pero siempe existe la posibilidad de se presente un caso peor(mayor consumo de máquina, tiempo,etc)
2.
Para MergeSort el mejor caso está representado por la entrada del arreglo ordenado, pero en realidad los tiempos de ejecucion para el mejor y el peor caso son similares, del orden O(nlgn).
Claudia Jimena Rodríguez
Cod: 256912
Para el primer punto.
Al tener en cuenta el peor caso se esta considerando el maximo de recursos que un algoritmo usara con respecto a otro. Estos nos dara una punto de vista objetivo en el momento de decidir entre dos algoritmos en al caso tal en que tenga soluciones del mejor caso del mismo orden. De igual forma se debe tener en cuenta el orden del caso probable, ya que no siempre se presentara el peor caso ni tampoco siempre el mejor.
Para el punto 2, se tiene que el mergesort tiene un orden de Kn(LGn) y su funcion T(n)=kn +knLGn. por tanto el tiempo necesario para resolver un arreglo obedece siempre esta formula sin importar que este ordenado ascendente o descendente.
Didier A. Vega O.
Cod:257002
el peor caso se esta considerando el maximo de recursos que un algoritmo usara con respecto a otro. Un punto de vista objetivo en el momento de decidir entre dos algoritmos en al caso tal en que tenga soluciones del mejor caso del mismo orden.
punto 2: mergesort tiene un orden de Kn(LGn) y su funcion T(n)=kn +knLGn. El tiempo necesario para resolver un arreglo obedece siempre esta formula sin importar el orden.
Juan Felipe Garcia
Cod:256964
punto 1:
en el peor caso se emplean todos los recursos necesarios y se toma el mayor tiempo para completar la tarea. Estos nos dara una punto de vista objetivo en el momento de decidir entre dos algoritmos en tal caso tal en que tenga soluciones del mejor caso del mismo orden
Punto 2.
Merge Sort: si el arreglo es menor o igual a 1 cualquier entrada es valida ya que el tiempo de ejecucion es teta = 1
El peor caso depende realmente del tamaño del arreglo por las operaciones de división y unión de las sub-partes del arreglo
NESTOR JAVIER VEGA
257003
Publicar un comentario