Complejidad Algorítmica: Comparación y Medición de Eficiencia
Contenido del curso
Gastón Gentile
Jose Colmenares
Alfonso Morán
Walter Correa
Santiago Ahumada Lozano
Julian Omar Meza
Julio Hurtado
Julio Hurtado
Joel Eduardo Gaspar
Emilian Harastasan
Angel de Jesus Rodríguez Venegas
Eber Laurente Lliuyacc
Juan Pablo Gómez García
Byron Oyarzún 🇨🇱
Carlos Rodríguez
Karl Behrens Gil
José Szychowski
Omar Rodríguez Aldama
Martin Mendez
Daniel Andrés Giraldo Benites
Beder Danilo Casa Condori
Francisco Leví Méndez Delgado
Jesús Lautaro Careglio Albornoz
Royer Guerrero Pinilla
Carolina Acosta Muñoz
Omar Rodríguez Aldama
Gonzalo Ferrando
Gonzalo Ferrando
Jose Cardenas
JAVIER SANTIAGO SALGADO
Andres Julian Mendez Pizarro
Roger Carlos Ariel Alba
Moisés Manuel Morín Hevia
Alejandro Castaño Vargas
José Manuel Barajas Ramírez
Vanessa Tejerina
David Rosas
Juan Nuñez
Neo TRAN
Juan Pablo Celiz
Cesar Eduardo Montoya Santiago
Pedro Alejandro Rodríguez García
Moisés Manuel Morín Hevia
Jherom Chacon
Chris Rico
Kevin Inca
Hola, aquellos que tengan problemas al ejecutar el script realizado por el profesor:
Probablemente tu interprete de Python te este alertando:
maximum recursion depth exceeded in comparison
Esto se debe a que por seguridad Python tiene un limite de recursion (por defecto 1000, puedes leer más sobre ello en la documentación oficial de python) que puedes averiguar realizando en tu main() un:
print(sys.getrecursionlimit())
Antes de utilizarlo deberás hacer un import del modulo sys, al comienzo de tu script:
import sys
Para ampliar este limite debes hacer un:
sys.setrecursionlimit(numero_limite)
De esta manera, la recursion funcionara hasta el limite especificado.
Pero, tal como especifica la documentación de Python, debes ser cuidadoso con aumentar este limite.
Espero haberlos ayudado,
Saludos!
Grande! Que interesante
Gracias, pero aunque ponga yo mismo el límite el programa falla con la función recursiva.
MemoryError: Stack overflow
Estos fueron mis resultados
¡Excelente!
Son los mismos valores para otra referencia en los tiempos.
Deberían arreglar este vídeo. El código del factorial recursivo está mal, no está haciendo llamadas recursivas a la función. El factorial recursivo llama al factorial que usa while
Haciendo el método recursivo yo obtengo un error que dice:
return n * factorial_r(n - 1) [Previous line repeated 995 more times] File ".\factorial.py", line 14, in factorial_r if n == 1: RecursionError: maximum recursion depth exceeded in comparison
Con esto se soluciona ese problema
import sys sys.setrecursionlimit(1000000)
El programa es incorrecto: porque dentro de la funcion factorial_r se esta llamando la funcion factorial en vez de a la funcion factorial_r para que sea recursivo. Porque sino el codigo habría dado error con 20000 iteraciones porque Python tiene un maximo de 999 en “Recursion depth”.
He hecho unas pruebas y aqui os dejo el codigo que utilizo yo:
import time import sys def factorial(n): response = 1 while n > 1: response = response * n n = n - 1 return response def factorial_recursive(n): if n == 1: return 1 return n * factorial_recursive(n - 1) if __name__ == '__main__': n = 2500 sys.setrecursionlimit(n + 10) startingTime = time.time() factorial(n) endTime = time.time() print(f"Execturion time with bucle\t{endTime - startingTime}"); startingTime = time.time() factorial_recursive(n) endTime = time.time() print(f"Execution time with recusive\t{endTime - startingTime}");
Buen aporte!
Sí tienes razón, pero es un error fácil de darse cuenta. :)
El código de la función recursiva esta llamando al factorial del while, deberían arreglar el vídeo
Buen detalle!
Buen detalle.
Les dejo un link con mis apuntes https://github.com/karlbehrensg/poo-y-algoritmos-python
Introducción a la complejidad algorítmica
La complejidad algorítmica nos permite comparar la eficiencia de 2 algoritmos, esto a su vez va a predecir el tiempo que va a tomar resolver un problema. No solamente podemos analizar la complejidad desde la perspectiva temporal, también la podemos hacer desde la espacial, como por ejemplo cuanto espacio en memoria necesitamos.
La complejidad algorítmica temporal la podemos definir como T(n) el cual determinara el tiempo que demora en resolver nuestro algoritmo.
Aproximaciones
¿Como podríamos aplicar nuestra función T(n)?
Cronometrar el tiempo en el que corre un algoritmo. Sin embargo no es una buena forma de medir los algoritmos, ya que no se puede predecir cuanto demorara a medida que crece nuestros pasos.
Contar los pasos con una medida abstracta de operación. Nos puede acercar a una medición ideal, sin embargo varia mucho de algoritmo en algoritmo y a medida que crece nuestro dataset existen muchos términos que llegan a ser irrelevantes.
Contar los pasos conforme nos aproximamos al infinito pero con una medida asintótica.
Medición temporal
Para una realizar una medida temporal simplemente calculamos la diferencia del tiempo previo y posterior de la ejecución del algoritmo.
import time def factorial(n): respuesta = 1 while n > 1: respuesta *= n n -= 1 return respuesta def factorial_r(n): if n == 1: return 1 return n * factorial(n - 1) if __name__ == '__main__': n = 200000 comienzo = time.time() factorial(n) final = time.time() print(final - comienzo) comienzo = time.time() factorial_r(n) final = time.time() print(final - comienzo)
sos un genio amigo
me encanto muchas felicidades, apuntes increibles ❤️
El factorial recursivo deberia ser con _r al final
def factorial_r(n): if n == 1: return 1 return n * factorial_r( n - 1 )```
asi es compañero fue un pequeño error
exacto
Me parece que la función recursiva está mal implementada ya que está mandando a llamar a la función iterativa en vez de a si misma.
El número más grande que pude utilizar fue el 998, y por cada ejecución el timepo cambiaba, pero siempre era menor en la función iterativa.
Adjunto el código de mi función iterativa:
def factorial_r(n): """Factorial recursivo.""" if n == 1: return 1 return n * factorial_r(n - 1)
No parece que está mal implementada, ESTÁ mal implementad.... este profe esta arrastrando muchas fallas...
Les comparto un articulo super util hecho por pablo trinidad profe de Django en platzi Complejidad Algorítmica
Lo leeré más tarde, gracias!!!
wow esta muy completo, gracias por compartirlo
Hay un error en el código! Dentro de la recursividad se está llamando a "factorial(n - 1)" cuando realmente se tendría que llamar a a "factorial_r(n - 1)".
Eso explica que los resultados den tan próximos: Si probamos con n = 100 se nota:
3.1948089599609375e-05 0.00035190582275390625
y con n = 1000
RecursionError: maximum recursion depth exceeded in comparison
No es un error, Eel factorial de un numero se puede escribir como n! = n*(n-1)! Intentalo en tu calculadora y verás que si
David, llamo en la función factorial_r a la función factorial, toca cambiarlos en ese momento para comparar bien. Para que no tengan problemas usen:
import sys sys.setrecursionlimit(200000)
Por que Python solo deja 999 iteraciones en las recursivas . Esta info también esta en preguntas, pero creo bueno tenerlo aca
Por que se demoran en corregir el video, ya que la demora parecida es por que a la primera llamada de la recursividad se va al factorial del while lo que hace que se demoren practicamente lo mismo siempre.
Hola Andres,
Gracias por tu feedbak. Lo apreciamos. ¿Cuál es exactamente el problema? Estamos revisando ya el video. También nos puedes escribir a team@platzi.com y con gusto damos seguimiento a tu caso.
Saludos
Yo lo veo todo bien
Mi computadora cuenta con 12GB de RAM, sin embargo, cuando uso un n mayor o igual a 2900 el código no lanza errores ni nada, simplemente se detiene y no ejecuta el resto del código ¿alguien sabe qué sucede? RAM utilizable: 11,9 GB
Algunas obviedades como el 2 en las variables de tiempo o los 'aaaa' eran para ver dónde se detenía el programa
import time import sys def factorial(n): respuesta = 1 while n > 1: respuesta *= respuesta n -= 1 def factorial_r(n): if n == 1: return 1 return n * factorial_r(n - 1) if __name__ == '__main__': n = 2900 sys.setrecursionlimit(n + 100) inicio2 = time.time() print('aaaa') factorial_r(n) print('aa') final2 = time.time() tiempo2 = final2-inicio2 print(tiempo2) inicio = time.time() factorial(n) final = time.time() tiempo = final-inicio print (tiempo)
Me pasa lo mismo.
Un error que vi en el codigo es que el factorial recursivo esta mal escrito deberia estar asi:
def factorial_recursivo(n): if n == 1: return 1 return n*factorial_recursivo(n-1)
Ya que lo que se muestra en el video es un factorial recursivo que utiliza al factorial iterativo para devolver una solucion. En realidad, la operacion de factorial iterativo, deberia ser mucho mucho mas rapida que la del factorial recursivo Ademas, si implementas el factorial recursivo tal cual aca:
import time def factorial(n): respuesta = 1 while n>1: respuesta *= n n -= 1 return respuesta def factorial_recursivo(n): if n == 1: return 1 return n*factorial_recursivo(n-1) if __name__ == '__main__': n = 1000 comienzo = time.time() factorial(n) final = time.time() print(final - comienzo) comienzo = time.time() factorial_recursivo(n) final = time.time() print(final - comienzo)
Te sale el error ++RecursionError: maximum recursion depth exceeded in comparison++ Que basicamente indica que la recursion ha llegado a un "limite" de profundidad Esto se puede resolver con cosas muy raras en python, pero... Traten de corregir esa parte del video!
Gracias! Sabes de esas cosas raras? Quisiera resolverlo jaja Encontre que podemos ver el limite importando sys y ...
import sys print(sys.getrecursionlimit()) #(1000)
E incluso cambiarlo con sys.setrecursionlimit(1500) pero advierten que puede ser peligroso y deberiamos optar por cambiar el algoritmo iterativamente.
https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it
En el código del profesor creo que hay un detalle que pasó por alto y es que el código de factorial recursivo no se llama a si mismo si no a la función de factorial sin recursión. El código que hice fue éste pero no me deja hacer muchas recursiones porque hay un límite:
def factorial(n): r=n while n>1: r=r*(n-1) n-=1 return r def factorial_r(n): if n==1: return 1 else: return n*factorial_r(n-1) if __name__=="__main__": print(factorial(100)) print(factorial_r(100))```
Quizás es una duda muy simple, pero en la función recursiva que tiene el profesor llama a factorial() en lugar de a factorial_r()
def factorial_r(n): if n == 1: return 1 return n * factorial(n - 1)
Para que una función sea recursiva se tiene que llamar a ella misma, ¿no? Entonces tendríamos
def factorial_r(n): if n == 1: return 1 return n * factorial_r(n - 1)
Quizás ya muchos han dado una respuesta a eso, pero me ha quedado esa duda
Así es, tienes razón. Recursión).
Existe error en codigo, una funcion recursiva , se llama a si misma el codigo correcto queda:
def factorial_rec(n): if n == 1: return 1 return n * factorial_rec(n-1)
pero se debe importar la libreria porque marca error de numero maximo de recursividad import sys sys.setrecursionlimit(900000000)
Cuando me contrate google compraré una laptop mejorcita :'/
Hola, soy google.
He tenido algunos problemas con la recursividad en Python, debido a que aparentemente este no es un lenguaje de programación que esté demasiado optimizado para trabajar con esta técnica. Entonces, he tenido que investigar un poco, anteriormente había tenido un error de:
RecursionError: maximum recursion depth exceeded in comparison
Sin embargo, encontré en este hilo de stackoverflow una solución para este problema:
import sys sys.setrecursionlimit(1500)
Gracias [David Young]!(https://stackoverflow.com/users/399663/david-young) Aquí les dejo una imagen de mis resultados: e
Qu funcion tiene el import sys o generalmente para que mas se usa? gracias por tu aporte
Programa corregido y con las limitantes de Python en 1M.
import time import sys sys.setrecursionlimit(1000000) def factorial(n): respuesta = 1 while n > 1: respuesta *= n n -= 1 return respuesta def factorial_r(n): if n==1: return 1 else: return n * factorial_r(n-1) if __name__ == "__main__": n = 9995 comienzo = time.time() print(factorial(n)) final = time.time() print(final -comienzo) comienzo2 = time.time() factorial_r(n) final2 = time.time() print(final2 - comienzo2)```
