ejercicios de calentamiento semana 2

ejercicios de calentamiento semana 2

de Bruno Stefano Lombardo Palleiro -
Número de respuestas: 4

Buenas,

Tengo algunas dudas:

Sobre el 1 hice esta demostración  basándome en el ejercicio resuelto el año pasado, pero aquí no se si es correcto afirmar el paso dos tal cual como lo hice en la cota superior, y si la demostración para la cota inferior esta bien.

Sobre el 2 parte b, no entiendo porque sería falso, aplicando el mismo argumento de la parte a lo podría demostrar(esto me dice que mi demostración del a debe estar mal).

Gracias

Ej 1


Cota superior: 

   1)cada ejecución del paso 4 requiere O(1).

   

   2) cada ejecución del paso 3, realiza n-1 sumas, es decir menos de n sumas.

   

   3)Los ciclos de los pasos 1 y 2 no se repiten  mas de n veces cada uno, 

      entonces los pasos 3 y 4 no se repiten  más de n^2 veces en total.


   Sea T3(n) y T4(n) los tiempos totales en todas las ejecuciones de los pasos 

   3 y 4 respectivamente.

   De 1) y 3): T4(n)=O(n^2) (no voy a ejecutar mas de n^2 veces algo que es O(1))

   De 2) y 3): T3(n)=O(n^3) (pq cada vez que ejecuto el paso 3 no tengo que hacer mas de n sumas y esto no lo hago  mas de n^2 veces)


   Entonces T3(n)+T4(n)=O(n^3)


cota inferior:

   cada ejecución realiza n-1 sumas, que se repiten para j entre 1 y n , que a su vez se repiten  con i variando entre 1 y n.

   Sea s(i) la cantidad de sumas para cada valor de i.

   s(i) es la sumatoria de j=1 hasta n de n-1 sumas , por lo que s(i)=n(n-1).

   Si llamamos N(n) a la cantidad de sumas totales tenemos que N(n)=n^2(n-1)

   Por lo tanto N(n) es omega(n^3)

   

Como el tiempo del algoritmo esta acotado tanto inferiormente como superiormente por n^3 entonces la función buscada es f(n)= n^3.

 Ej 2

a)  Cada elemento se imprimirá una sola vez ya que no se vuelve a visitar por el algoritmo una vez que se imprimió. Pero sólo hay m elementos, por lo que hay m iteraciones y cada iteración lleva una cantidad de tiempo constante de trabajo, por lo que el tiempo total de ejecución es O(m).


En respuesta a Bruno Stefano Lombardo Palleiro

Re: ejercicios de calentamiento semana 2

de Sofia Tito Virgilio Rodriguez -
Hola Bruno.

Respecto al paso 2 para la demostración de la cota superior para el Ejercicio 1, notar que en este caso el producto escalar no solamente implica n-1 sumas, sino que además implica n productos (a1.b1 + a2.b2 + … + an.bn) y si refinamos todavía un poco más implica además un loop, comparaciones, asignaciones, etc. Por lo que no podemos afirmar que solamente realiza n-1 sumas, lo que si podemos es afirmar que se puede implementar en tiempo O(n) porque implica recorrer un par de vectores de largo n, realizando una cantidad finita de operaciones elementales por cada posición de estos vectores, por lo que el resto de la justificación no se ve alterada, ya que para T3(n) tenemos que se ejecuta no más de n^2 veces algo que es O(n).

Además, conviene tener presente que también se debe tener en cuenta el tiempo empleado al evaluar las condiciones y actualizar las variables del for o del loop que se esté utilizando, aunque en este caso no tiene ningún impacto porque no requiere más de O(1) por iteración, por lo que el tiempo total que requiere ejecutar el for (sin tener en cuenta el cuerpo) es O(n) que es de un orden menor al resto de tiempos que estamos manejando.

Respecto a la demostración de la cota inferior para el Ejercicio 1, el procedimiento es correcto, notar que en este caso si podemos tener en cuenta solamente las sumas porque estamos buscando una cota inferior y con el tiempo empleado para realizar las sumas ya nos alcanza para hallar la cota buscada.

Respecto al Ejercicio 2, es correcto que el tiempo total empleado en imprimir los elementos es O(m), el problema es que no se está teniendo en cuenta que el loop itera n veces invirtiendo un tiempo Omega(1) en cada iteración, independientemente del valor de m, lo cual requiere invertir un tiempo Omega(n) solamente por ejecutar el for.

En la parte a, como trabajo sobre la hipótesis de que las listas son no vacías, esto me garantiza que m >= n, y por lo tanto, me quedo con el tiempo más lento, que es O(m). Pero sin embargo, en la parte b no tengo la garantía de que m sea mayor o igual a n, por lo que no tengo la certeza de que mi algoritmo sea O(m). Por ejemplo, supongamos m = 0, en este caso el algoritmo igualmente realiza n iteraciones invirtiendo un tiempo constante en cada iteración, aunque no imprima ningún elemento, por lo que no sería correcto decir que el tiempo de ejecución es O(m). Entonces en ese caso el orden total del algoritmo va a depender de la relación entre m y n que puede ser diferente en cada ejecución del algoritmo dependiendo de la instancia del problema, por lo que se suele expresar como O(m+n).

Espero que haya quedado un poco más claro, cualquier cosa quedo a las órdenes.
Saludos!
En respuesta a Sofia Tito Virgilio Rodriguez

Re: ejercicios de calentamiento semana 2

de Bruno Stefano Lombardo Palleiro -
Hola Sofia, muchas gracias por la respuesta, me ayudaron muchísimo tu comentarios.

Entonces para que el ejercicio 1 esté bien, tendría que corregir el paso 2 y agregar por ejemplo el siguiente comentario:
"Además el tiempo empleado en una ejecución en los pasos 1 y 2 no requiere mas de O(1).
Como estos se realizan en total n^2 veces, el tiempo total en todas las ejecuciones de los pasos 1 y 2 sería
O(n^2),que es un orden menor que O(n^3) y por tanto el tiempo total del algoritmo sigue siendo O(n^3)."

En el ejercicio 2, teniendo en cuenta todo lo que dijiste lo pensé así:
a)
Sea T1(n) el tiempo total sumado de todas las ejecuciones del paso 2.
Como tenemos m elementos a imprimir y no se imprime dos veces el mismo elemento, habrá m iteraciones y cada una lleva un tiempo constante por lo que T1(n)=O(m).

Sea T2(n) el tiempo total en todas las ejecuciones del paso 1. En cada iteración de este paso se invierte un tiempo O(1) y como se hace n veces T2(n)=O(n).

Como por hipótesis tenemos m>=n el tiempo total del algoritmo sería T1(n)+T2(n)=O(m)

En la parte b entendí perfectamente la explicación, mi única duda es al final cuando decís que el tiempo se suele expresar como O(m+n), esto es por convención no? Porque al no saber la relación entre m y n no sabemos que tiempo es.

Saludos
En respuesta a Bruno Stefano Lombardo Palleiro

Re: ejercicios de calentamiento semana 2

de Sofia Tito Virgilio Rodriguez -
Hola.

Las correcciones del Ejercicio 1 son correctas.

En el Ejercicio 2, notar que en realidad el tiempo total de todas las ejecuciones del paso 2 ya requiere un tiempo O(m + n) porque ese paso lo ejecutamos sí o sí n veces aunque sea para verificar si la lista está vacía, y a veces además imprimimos alguna cantidad de elementos. ¿Se ve?

Sobre el O(m+n), lo que indica es que tenemos dos parámetros que aportan su parte al tiempo de ejecución del algoritmo, y a priori no tenemos ningún motivo para priorizar uno o el otro, o afirmar que uno le "gana" al otro, entonces el tiempo de ejecución de nuestro algoritmo está dado por la suma de esas dos componentes que aportan al tiempo total, y que en la práctica quizás una predomine sobre la otra dependiendo de la instancia del problema, pero en el caso general ambas deben ser tenidas en cuenta y por eso el orden del tiempo de ejecución del algoritmo es O(n + m). Este orden de tiempo de ejecución va a aparecer mucho cuando trabajemos sobre grafos, ya que tanto el procesamiento de los vértices (n) como el de las aristas (m) de los grafos aportan al tiempo de ejecución total del algoritmo y en ocasiones no tenemos por qué conocer la relación entre la cantidad de nodos y aristas del grafo.

Intuitivamente es lo que haríamos si tuviéramos por ejemplo un for vacío de 1 a n y luego otro de 1 a m y no supiéramos la relación entre m y n, en ese caso el orden del tiempo total del algoritmo sería el orden de la suma de las funciones que definen el orden de los bloques que se ejecutan secuencialmente.

Avisame si quedó un poco más claro.

Saludos!