Introducción a la complejidad algorítmica

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!

Estos fueron mis resultados

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

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}");

El código de la función recursiva esta llamando al factorial del while, deberían arreglar el vídeo

El factorial recursivo deberia ser con _r al final

def factorial_r(n):
	if n == 1:
		return 1
	
	return n * factorial_r( n - 1 )```

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)

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)

Les comparto un articulo super util hecho por pablo trinidad profe de Django en platzi
Complejidad Algorítmica

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)”.

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

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!

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))```

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 :’/

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

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)```

Algo curioso, python tiene una configuración para el límite de veces que una función se puede llamar a sí misma. Lo descubrí por el siguiente error cuando ejecute el algoritmo por primera vez:

Traceback (most recent call last):
  File "src/complejidad_algoritmica.py", line 24, in <module>
    factorial_r(n)
  File "src/complejidad_algoritmica.py", line 13, in factorial_r
    return n * factorial_r(n - 1)
  File "src/complejidad_algoritmica.py", line 13, in factorial_r
    return n * factorial_r(n - 1)
  File "src/complejidad_algoritmica.py", line 13, in factorial_r
    return n * factorial_r(n - 1)
  [Previous line repeated 995 more times]
  File "src/complejidad_algoritmica.py", line 10, in factorial_r
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

Si ven, tiene un mensaje que dice [Previous line repeated 995 more times].

La solución, agregar el siguiente código antes de llamar a la función recursiva.

import sys
sys.setrecursionlimit(2000)

Hecha la modificación en relación al error en la fórmula obtuve estos resultados. Consideraciones:

• Los valores suelen variar considerablemente

• Lo estoy corriendo en virtualbox con linux. Entorno de uso de 3 cores con 2 gb de ram. Esto puede incidir en el rendimiento creo.

• Los valores son factoriales en un range(500,11000,500)

• Los rojos son el factorial con ciclo, los azules el factorial recursivo

Conclusión de esta clase: hay que comprar nueva laptop xD (29 segundos con 200.000)

No se si estoy equivocado, pero en la parte de recursión usa la función factorial() en vez de la función factorial_r()

def factorial_r(n):
    if n == 1:
        return 1

    return n * factorial(n - 1)

Debería ser así

def factorial_r(n):
    if n == 1:
        return 1

    return n * factorial_r(n - 1)

Toma tiempo pero si se puede fer un programa como una función matemática, los mas complicados son los programas que usan recursion por que no es tan evidente.

Primero podemos pensar en el peor caso, esa es la evaluacion de la complejidad.
Imaginen que cada for es n
Un ciclo anidado como while o for es m
al estar anidado es n * m, pero para simplificarlo lo dejamos en n * n o n cuadrado.

Hay casos donde el ciclo interno reduce m en cada iteracion, por ejemplo en menos uno, asi cuando n aumente m ya bale m-1
Ese crecimiento si lo vieramos en una grafica seria una curva pero menos dramática que un cuadrado, a esas funciones se les suele llamar n* log(n).

Considero que el verdadero impacto no se encuentra en el tiempo de ejecución sino en el consumo de memoria, ya que el método iterativo, sin importar el tamaño de N el consumo de memoria es constante, en la forma recursiva, el tamaño de la pila de recursión crece a medida que crece N.

Sí, está mal la implementación de la función factorial_r(n), ya que no es recursiva porque está llamando a la función factorial(n).

Con la implementación correcta, en mi computadora no pude pasar de los 10000 iteraciones recursivas, porque tronaba por Stack overflow.

Pero para factorial(n) y n=200,000. Mi compu se tardó 11.32545483 segundos

con 10000:
0.02991342544555664
0.026929378509521484

Con 100000:
2.672286033630371
2.5404880046844482

n = 200000
24.1235613822937
22.07455086708069

Hay un error en el codigo por lo cual no se nota mucho la diferencia.
En la funcion recursiva el falto volver a llamar a factorial_r el manda a llamar solo factorial

Así los resultados 😮

Factorial solo perdió para n = 50000

APLICANDO DECORADORES AL TIEMPO TOTAL DE EJECUCIÓN

Algunos habrán notado que comienzo y final se encuentran antes y después de las funciones que estamos evaluando. Esto se presta a la perfección para aplicar decoradores. A continuación, les muestro el código con la función decorador, que reemplazaría escribir comienzo y final antes y después de cada función que evaluemos.

import time
import sys
sys.setrecursionlimit(1000000)

# Funcion Decorador
def total_time(funcion_parametro):
    def funcion_interior(n):
        comienzo = time.time()
        funcion_parametro(n)
        final = time.time()
        print(final - comienzo)
    return funcion_interior

@total_time
def factorial(n):
    respuesta = 1
    while n > 1:
        respuesta = respuesta * n
        n = n - 1
    return respuesta

# Para aplicar decoradores a una función recursiva, debemos hacerlo directamente al final del código
def factorial_r(n):
    if n == 1:
        return 1
    return n * factorial_r(n-1)

if __name__ == '__main__':
    n = 1000

    # Como ya aplicamos el decorador @total_time, bastará ejecutar esto para mostrar el delta de tiempo:
    factorial(n)

    # Para funciones recursivas, el decorador deberá aplicarse así:
    total_time(factorial_r)(n)

Puse 200 mil…
Mi PC explotó.

Una solución más funcional ^^

from functools import reduce # para reducir un iterable a un solo valor, aplicando una función
from operator import mul # mul es el operador *

def factorial(n: int) -> int:
   return reduce(mul, range(1, n + 1)) # o reduce(lambda x, y: x * y, range(1, n + 1))

Han pasado 84 años…

import time
import sys

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__":
   
    sys.setrecursionlimit(1000000000)
    n = 10000000

    comienzo = time.time()
    factorial(n)
    final = time.time()
    print('Tiempo iterativa: ' + str(final - comienzo))

    comienzo = time.time()
    factorial_r(n)
    final = time.time()
    print('Tiempo recursiva: ' + str(final - comienzo))

En la función de factorial_r se hace uso de la función factorial, creería que la mejor manera sería poner factorial_r para mostrar bien la recursividad. Haciendolo así se nota una gran diferencia desde valores pequeños.

import time

def factorial_1(n):
    respuesta = 1
    while n > 1:
        respuesta *= n
        n -= 1

    return respuesta

def factorial_2(n):
    if n == 1:
        return 1
    else:
        return n * factorial_2(n-1)

if __name__=='__main__':
    n=200000

    comienzo = time.time()
    factorial_1(n)
    final = time.time()
    print(final-comienzo)

    comienzo = time.time()
    factorial_2(n)
    final = time.time()
    print(final-comienzo)```

Esto da un Corei3 con 3GRam
n = 200.000
113.97351884841919
100.9137716293335

Si he pensado en hacer la inversión claro jaja

En el factorial recursivo le falto al profe poner la r, por eso los tiempos son similares, en una corecta implementación se nota bastante la diferencia.

return  n * factorial_r(n - 1)```

Plop!

[Previous line repeated 997 more times]
MemoryError: Stack overflow

La función recursiva debe ser así:

def factorial_r(n):
    if n == 1:
        return 1
    
    return n * factorial_r(n - 1)```

Y se debe importar la sys para cambiar el límite

import sys
sys.setrecursionlimit(900000000)

con 200.000
45.572144746780396
46.49448800086975

tendre que cambiar de ordenador ajajaa

100
0.0
0.0

1000
0.0
0.0034165382385253906

10000
0.046872854232788086
0.051892995834350586

100000
15.093713998794556
12.642263889312744

1000000
1751.385460138321
1958.580992937088

Creo que necesito algo mejor xD

Me parece que hay un error en la definición de la función factorial_r(n). Debería ser:

def factorial_r(n):
if n == 1:
return 1

return n * factorial_r (n-1)

Es decir que en el return esta llamando a la función factorial_r(), y en el del ejemplo esta llamando a la función factorial(). Por lo tanto los resultados de tiempo son erróneos. Al ejecutar en mi Pc me muestra un error de recursion en la función factorial_r() : RecursionError: maximum recursion depth exceeded in comparison .

Hay un error en el código del profe para que una función sea considerada recursiva esta debe ser definida y a su vez ejecutada dentro de su definición, esto quiere decir que en la función recursiva era factorial_r(n-1) no factorial(n-1)

hay un error en la función recursiva ya que llama a la funcion “factorial(n-1)” y deberia llamarse a si misma asi:

def factorial_r(n):
    if n == 1 :
        return 1
    return n * factorial_r(n - 1)```

mi laptop dejo de funcionar con 50 mil :’(

Con 100000 y 200000

¿La clase tiene un error? Al definir la función recursiva factorial_r está usando la función anteriormente definida (factorial) y no a sí misma. Quizás los resultados habrían sido significativamente diferentes en la clase si la función recursiva (factorial_r) hubiera sido verdaderamente recursiva.

Chicos aquí les dejo mis apuntes de la clase, el código del profesor corregido y al final les dejo la explicación de todo el código, que creo que es muy importante que lo leas si no entendiste del toda la clase, lo explico todo:
.

Apuntes de la clase

1.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.

1.1. Aproximaciones

a) 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 medir con precisión ya que el tiempo que demore dependerá tambien de otros factores como el equipo que estemos usando o los programas que tengamos abiertos al ejecutar el código.

b)Contar los pasos con una medida abstracta de operación (cada vez que se haga alguna suma, resta, multiplicacion…): Nos puede acercar a una medición ideal, sin embargo varia mucho de algoritmo en algoritmo ya que cada algoritmo tiene un número distinto de operaciones, y a medida que crece nuestro dataset existen muchos términos que llegan a ser irrelevantes.

c) Contar los pasos conforme nos aproximamos al infinito pero con una medida asintótica.

1.2. Medición temporal con implementación recursiva vs implementación iterativa en un ejercicio de factoriales:

Este es el ejercicio que hizo el profesor pero corregido:

import time
import sys

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_r(n - 1)

if __name__ == '__main__':

    n = 50000

    sys.setrecursionlimit(60000)

    comienzo = time.time()
    factorial(n)
    final=time.time()
    print(final-comienzo)

    comienzo = time.time()
    factorial_r(n)
    final = time.time()
    print(final - comienzo)

Esta es la explicación del código

(NOTA: Colocar este código en el editor de texto para que se vea y se entienda bien)

import time
#para medir el tiempo en python
import sys

"""por seguridad Python tiene un limite de recursion, así que no va a iterar más de lo que está pre establecido (1000 por defecto)
puedes averiguar cual es el límite de recusion con "print(sys.getrecursionlimit())", y lo puedes modificar con
"sys.setrecursionlimit(numero_limite)",pero antes no se te olvide importar el módulo sys que está incorporado en python y proporciona
acceso a algunas variables y funciones específicas del sistema."""

"""¿Qué es el factorial?

El factorial de un número es el producto de todos los números enteros positivos desde 1 hasta ese número. 
Por ejemplo, el factorial de 5 es 5 * 4 * 3 * 2 * 1 = 120. 
Eso es lo que se hará en las siguientes funciones, sin embargo eso no es lo que nos interesa,
por lo tanto no es el número que nos da de vuelta al llamar a la función, 
el número que nos retorna la función en el tiempo que tarda en darse la operacióñ"""

#implementación de factorial iterativo:

def factorial(n):
    respuesta = 1

    while n > 1:
        respuesta *= n
        #esta notación simplemente significa respuesta mmultiplicala *n
        n -= 1

    return respuesta

"""En esta función, se define una variable llamada "respuesta" que se inicializa en 1. Luego, se utiliza un bucle "while" para iterar 
desde el número dado "n" hasta 1. En cada iteración, se multiplica el valor actual de "respuesta" por el valor actual de "n", 
y se decrementa "n" en 1. Al final del bucle, se devuelve el valor de "respuesta", que es el factorial del número "n".

Por ejemplo, si llamamos a la función "factorial(5)", el bucle se ejecutará 5 veces, multiplicando el valor de "respuesta" por 5,
 luego 4, luego 3, luego 2 y finalmente 1. El resultado final será 120, que es el factorial de 5."""
    
#este es la implementación factorial recursivo:

"""La recursividad es un enfoque en el que una función se llama a sí misma de manera repetida para resolver un problema."""

def factorial_r(n):
    if n == 1:
        return 1
    
    return n * factorial_r(n - 1)

"""En el caso de la función "factorial_r", se comprueba si el número dado "n" es igual a 1. Si es así, se devuelve 1, 
ya que el factorial de 1 es 1. Si el número "n" no es igual a 1, se llama a la función "factorial_r" con el parámetro "n - 1" 
y se multiplica el resultado por "n". Esto se repite hasta que se llega al caso base de n=1, 
en cuyo momento se inician las llamadas recursivas a la función que se habían quedado en espera. 
De esta forma, se va resolviendo el factorial de manera recursiva, reduciendo el tamaño del problema en cada llamada"""

if __name__ == '__main__':

    n = 50000
    #mientras mayor sea este número mayor será el tiempo que tarde nuestra implementación

    sys.setrecursionlimit(60000)
    #sirve para modificar el límete de recusión

    comienzo = time.time()
    #Esto quiere decir que estamos ejecutando el módulo time y dentro del módulo time hay una función que se llama time
    factorial(n)
    final=time.time()
    print(final-comienzo)
    #O sea, comenzamos a medir el tiempo antes de ejecutar la función y luego medimos cuanto nos tardamos

    comienzo = time.time()
    factorial_r(n)
    final = time.time()
    print(final - comienzo)

El super poder de platzi la comunidad. tocaba era aumentarle el limit de la recursion. Mi compu es más eficiente.

cómo crítica constructiva, es que no debería abordar conceptos matemáticos que descolocan al estudiante, porque por ejemplo la clase venía bien hasta que introdujo el factorial de un número, en la velocidad del curso, toca pausarlo para primero saber qué es el factorial de un numero y así con ejemplos con conceptos matemáticos como Fibonacci y etc, deberían implementar ejemplos prácticos que nos nos saquen del contexto de la programación e ingeniería de software, porque nos tratan de interpolar con matemáticas cuya lógica va más allá de un algoritmo porque implementan principios matemáticos que tienen una formulación de sus algoritmos mucho mas profunda y en casos como el Fibonacci mucho mas compleja.

Un ejemplo sencillo para entender la diferencia entre complejidad temporal y complejidad espacial es el siguiente: Imagina que tienes una lista de números y quieres encontrar el número más grande. Una forma de hacerlo es recorriendo toda la lista y comparando cada número con el número más grande encontrado hasta el momento. Este algoritmo tiene una complejidad temporal lineal, ya que el tiempo que tarda en ejecutarse aumenta linealmente con el tamaño de la lista. Sin embargo, su complejidad espacial es constante, ya que solo necesita almacenar un número (el número más grande encontrado hasta el momento) independientemente del tamaño de la lista.

Ok, voy a dejar de lado el video (Porque me parece absurdamente difícil de entender y con errores graves) y explicarlo con mis propias palabras para obtener su feedback.

En python las funciones recursivas se utilizan para la resolución de problemas en los que se necesita repetir una operación una cierta cantidad de veces hasta que se cumpla una condición. Por ejemplo, para calcular el factorial de un número n.

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

Nótese la recursión en return n * factorial(n-1)

Éstas, de acuerdo a la complejidad del problema a resolver, pueden ser más eficientes que las iterativas.
Las funciones iterativas son aquellas que se basan en un bucle, es decir, en una secuencia de instrucciones que se repiten hasta que se cumple una condición. En el caso anterior, el cálculo del factorial de un número n se puede realizar de la siguiente manera:

def factorial(n):
    resultado = 1
    for i in range(1, n+1):
        resultado = resultado * i
    return resultado

La diferencia de eficiencia entre los dos enfoques se debe a que en el caso de la** función recursiva** cada vez que se llama a sí misma genera una nueva variable en la pila de ejecución, lo cual puede ser costoso en términos de uso de memoria RAM. Por otro lado, la función iterativa utiliza una variable única en cada iteración, lo cual es más eficiente en memoria pero puede llegar a ser ineficiente en términos de consumo de CPU.

My times:

-La mayoría de los linters no recomiendan usar varios returns, siempre uno:

def factorial_r(n):
    response = 1
    if n != 1:
        response = n * factorial_r(n - 1)
    return response

A mí me sale este error con una recursión de 1000:

RecursionError: maximum recursion depth exceeded in comparison

no se porque pero en la funcion recursiva ya no me mostro la diferencia de tiempo, y segun yo aumente la cantidad de recursividad con sys.

sys.setrecursionlimit(100000)

En la línea 17 (implementación recursiva) está llamando a la otra implementación. Debería ser return n * factorial_r(n - 1).

Sobre el error de limite al corregir la funcion recursiva en el comentario de abajo y lo que encontre para solucionarlo…
https://platzi.com/comentario/1219399/

import time
def factorial(n):
    rta = 1
    while n>1:
        rta = n*rta
        n = n-1
    return rta

if __name__ == "__main__":

    print("Calculo algunos tiempos de ejecucion de factorial de N")
    print("N    || tiempo")
    n = 1

    for n in [1000 , 10000 , 50000 , 100000 , 200000 , 500000]:
        inicio = time.time()
        factorial(n)
        final = time.time()
        print( n , "    || ", final - inicio , "seg" )
        n = 10*n

Calculo algunos tiempos de ejecucion de factorial de N
N || Tiempo
1000 || 0.002030611038208008 seg
10000 || 0.05385732650756836 seg
50000 || 0.9488232135772705 seg
100000 || 3.6180427074432373 seg
200000 || 17.13899540901184 seg
500000 || 160.77143931388855 seg

Para comprender por qué es importante el análisis de algoritmos, tomaremos la ayuda de un ejemplo simple.

Supongamos que un gerente asigna una tarea a dos de sus empleados para diseñar un algoritmo en Python que calcule el factorial de un número ingresado por el usuario.

El algoritmo desarrollado por el primer empleado se ve así:

def fact(n):
    product = 1
    for i in range(n):
        product = product * (i+1)
    return product

print (fact(5))

Observe que el algoritmo simplemente toma un número entero como argumento. Dentro de fact funcionar una variable llamada product se inicializa a 1. Un bucle se ejecuta de 1 a N y durante cada iteración, el valor en el product se multiplica por el número que itera el ciclo y el resultado se almacena en el product variable de nuevo. Después de que se ejecuta el ciclo, product La variable contendrá el factorial.

Del mismo modo, el segundo empleado también desarrolló un algoritmo que calcula el factorial de un número. El segundo empleado utilizó una función recursiva para calcular el factorial de un programa como se muestra a continuación:

def fact2(n):
    if n == 0:
        return 1
    else:
        return n * fact2(n-1)

print (fact2(5))

El administrador tiene que decidir qué algoritmo utilizar. Para hacerlo, debe encontrar la complejidad del algoritmo. Una forma de hacerlo es encontrar el tiempo necesario para ejecutar los algoritmos.

En el cuaderno de Jupyter, puede utilizar el %timeit literal seguido de la llamada a la función para encontrar el tiempo que tarda la función en ejecutarse. Mira el siguiente guión:

%timeit fact(50)

Salida:

9 µs ± 405 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

La salida dice que el algoritmo toma 9 microsegundos (más / menos 45 nanosegundos) por ciclo.

Del mismo modo, ejecute el siguiente script:

%timeit fact2(50)

Salida:

15.7 µs ± 427 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

El segundo algoritmo que involucra la recursividad toma 15 microsegundos (más / menos 427 nanosegundos).

El tiempo de ejecución muestra que el primer algoritmo es más rápido en comparación con el segundo algoritmo que involucra recursividad. Este ejemplo muestra la importancia del análisis de algoritmos. En el caso de grandes insumos, la diferencia de rendimiento puede volverse más significativa.

Hay un error pequeño en la línea 17.
en vez de:

return n * factorial(n - 1)

copien:

return n * factorial_r(n - 1) 

Por más que aumentara el Recursion Limit (1M), mi computadora sólo me dejó hasta el número 6,463.
.
Cuando intento 6,464 me aparece el error “Stack Overflow”, que ya entiendo que significa que el programa intenta usar más espacio de memoria del que se tiene disponible.
.
Estos son mis resultados:

Creo que claramente tengo que cambiar mi Asus en algun momento:
n=200.000
70.72283363342285
61.304778814315796

Alguien sabe como hacer que el time me imprima el numero completo?
Ya que en las primeras pruebas, las dos iteraciones las imprime como

0.0

Gracias

Para aplicar lo que hemos aprendido un ejercicio interesante es medir el tiempo que tarda en ejecutarse un algoritmo por medio de un decorador.
En este caso la propuesta que les presento tiene un algoritmo que define si un número es primo o no, el algoritmo es muy básico y puede mejorar (por ejemplo recibe hasta números negativos :v); así que una invitación también es a que compartan sus mejoras del mismo. Ahora bien, el reto consiste en analizar el código y responder las siguientes preguntas 🤔: ¿Cuál es la diferencia que existe entre los algoritmos y cómo influye en su rendimiento? ¿Importa que el número a examinar sea primo? ¿Cual algoritmo es más eficiente y en qué contexto?

El tema lo entendí, pero todavía le batallo la recursividad, ¿Saben de casos de implementación de recursividad?

la mia se murio antes de llegar a los 10000 ya que la implementacion recursiva ocupo la memoria que habia 😦

Realizando corrección para la recursividad y utilizando caché en la función recursos, para mejorar el rendimiento.

import time
import sys
import resource


cache = {}

def factorial(n):
    respeusta = 1

    while n > 1:
        # print(n)
        respeusta *= n

        n -= 1

    return respeusta




def factorial_r(n):
    if n in cache:
        # print(cache)
        return cache[n]
    elif n == 1:
        return 1
    else:
        # print (n)
        value = n * factorial_r(n-1)
        cache[n] = value
    
    return value


def run ():
    while True:
        n =  int(input('Ingrese el numero que desea calcular el factorial:  '))
        # print resource.getrlimit(resource.RLIMIT_STACK)
        resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
        sys.setrecursionlimit(0x100000)

        comienzo = time.time()
        # print(factorial(n))
        factorial(n)
        final = time.time()
        print(final-comienzo)


        comienzo = time.time()
        # print(factorial_r(n))
        factorial_r(n)
        final = time.time()
        print(final-comienzo)




if __name__ == "__main__":
    run()

en Coolab con 200000
16.28399419784546
16.347416877746582

Con el de 10000 me salió el famoso Stack overflow, necesito una nueva PC :'v

n = 1000
1.9073486328125e-06
9.5367431640625e-07

n = 10000
1.9073486328125e-06
7.152557373046875e-07

n = 50000
2.1457672119140625e-06
9.5367431640625e-07

n = 200000
2.1457672119140625e-06
1.1920928955078125e-06

En el código del profesor, la linea 17 debe ser:

return n * factorial_r(n - 1)

y no:

return n * factorial(n - 1)

Le coloque 1000000 y explotó, se reinicio .
Creo que ya es hora de cambiar

Para 200000
17.345213890075684
13.822072982788086

Para 200000
41.210291147232056
41.46213340759277

buenardo

200000
11.13056206703186
11.104460954666138

Con n = 200000, los tiempos fueron:
17.964038848876953
18.26766586303711

pequeña modificacion

i = [1000,10000, 100000, 200000]
for n in i:
    print (n)
    comienzo = time.time()
    factorial(n)
    final = time.time()
    print (" nos tardamos iterativo =",final - comienzo)
    
    comienzo = time.time()
    factorial_r(n)
    final = time.time()
    print (" nos tardamos recursivo =",final - comienzo)

-------------- resultados ------------

1000
nos tardamos iterativo = 0.0003688335418701172
nos tardamos recursivo = 0.00032901763916015625
10000
nos tardamos iterativo = 0.028788089752197266
nos tardamos recursivo = 0.028656005859375
100000
nos tardamos iterativo = 2.5341811180114746
nos tardamos recursivo = 2.170130729675293
200000
nos tardamos iterativo = 11.454551935195923
nos tardamos recursivo = 9.166208505630493

Mis resultados para 200.000, en un principio tenia casi 30 segundos pero me di cuenta que tenia la versión de 32-bits de python. Luego cambie a la de 64-bits y mis resultados fueron:
9.09445834159851
9.068416357040405

Tengo una duda en la linea 17, ¿no debiese llamar a la función factorial_r(n - 1)?

con 200.000

16.904107570648193
16.968566179275513

ryzen 1800x @3.8Ghz

El profesor se equivocó llamando la función factorial en la función de factorial_r, dará error por el limite de recursidad, Pero hey aquí se aprende algo nuevo.

Creo hay problemas en el código, aquí dejo como sería y hasta donde llega

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_r(n-1)

if __name__=='__main__':
    n=998
    comienzo = time.time()
    factorial(n)
    final = time.time()
    print(f'tiempo: {final-comienzo} algoritmo 1')

    comienzo= time.time()
    factorial_r(n)
    final=time.time()
    print(f'tiempo: {final-comienzo} algoritmo 2')

Buenas Noches

Para N = 200.000

16.6449999809
17.8009998798

Pregunta!

¿No se supone que en la implementación recursiva debería utilizar la función factorial_r(n) en lugar de la función factorial(n)?

200.000

10.496364831924438
10.486165761947632

n = 200000
0.0010111331939697266
0.0009877681732177734

En mi computadora así se comportó la complejidad temporal para el factorial iterativo.

Para 200.000:
49.474706172943115
48.46279740333557
jajaja ahora siento que estoy trabajando desde una waflera

Hola! Vengo del futuro, para los que no tienen mucha noción de matemática o cuentan con solo lo esencial, les recomiendo este curso de Platzi para entender mucho mejor esta parte del curso llamado Matemáticas Discretas

A mí con 6000 iteraciones:
recursivo = 0.0293180
imperativo = 0.0312156

😦

Justo hoy a la mañana estuve comparando la función factorial recursiva con
otra implementación iterativa donde trate de usar logaritmos para mejorar la performance. Una herramienta propia de Python para este propósito que encontré muy útil es ejecutar esto desde consola:

python -m cProfile nombre_script.py

con esto el interprete genera un reporte sobre el desempeño temporal del script que podría ser útil para una primera aproximación para saber su eficiencia temporal

El profesor incurrió en un error en el código tal como lo muestra mi compañero caegomezda en el comentario anterior.

Un aporte como complemento a la clase, espero sea de utilidad:
###########
Comparar la eficiencia de los algoritmos. Se puede pensar que la forma mas sencilla de calcular la complejidad de un algoritmo es calcular la cantidad de pasos que debe realizar. Sin embargo, esto no es eficiente y el resultado final no nos dice mucho sobre la naturaleza del algoritmo.
En esto entra la complejidad de tiempo. En lugar de ver el número exacto de operaciones que realizara el algoritmo, vemos la complejidad de tiempo, que busca medir que tanto tarda un algoritmo en completarse a medida que si entrada crece.
Por eso es importante buscar los componentes más grandes en lugar de revisar cada línea de código. En otras palabras, hallar que parte del código es más costosa en términos computacionales. Un ejemplo de estas partes son los ciclos for o while, que son a menudo responsables por incrementar la complejidad de tiempo del algoritmo.
Fuente: https://www.learneroo.com/modules/106/nodes/559
Acá es donde entra el concepto de análisis asintótico y los términos Big O, Big Omega (Ω) y Big Theta (Θ), siendo Big O el más usado ya que representa el peor caso posible.

Creo que el profesor debió colocar en la función recursiva un llamado a factorial_r y no a factorial, porque de lo contrario estaría casi que comparando lo mismo, abajo mi código modificado:

import time
import sys

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_r(n-1)

if __name__ == '__main__':
    n = 10000
    sys.setrecursionlimit(n+2)
    comienzo = time.time()
    factorial(n)
    final = time.time()
    print(final - comienzo)

    comienzo = time.time()
    factorial_r(n)
    final = time.time()
    print(final - comienzo)```

97.88689732551575
98.39724397659302

Tengo mejor equipo que el maestro Aroesti

Al parecer tengo que cambiar mi computadora 😦
Mis tiempos con 200.000
Factorial (n) = 35.733352184295654
Fatorial_r (n) = 35.521392822265625

Me dio curiosidad y lo intente con estos números: 1000, 10000, 50000, 100000, 200000, 400000, 800000, 1600000. Desde 800.000 se empezó a demorar una eternidad.

Mi código:

import time
import sys


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 = 1000 # 1000, 10000, 50000, 100000, 200000, 400000, 800000, 1600000

    # aumentar el limete de recursividad de python
    sys.setrecursionlimit(n)
    
    print(f'Prueba de tiempo con {n}')
    inicio = time.time()
    factorial(n)
    final = time.time()
    print(f'La función del factorial con while se demoró:  {final - inicio} segundo(s)')

    inicio = time.time()
    factorial_r(n)
    final = time.time()
    print(f'La función del factorial con recursividad se demoró:  {final - inicio} segundo(s)')

El video está mal, al hacer el return de la forma del factorial recursivo pone factorial (n-1) en vez de factorial_r(n-1). De hecho cuando se hace el análisis se demora más con recursión.