Crea una cuenta o inicia sesión

¡Continúa aprendiendo sin ningún costo! Únete y comienza a potenciar tu carrera

Introducción a la complejidad algorítmica

11/25
Recursos

A continuación te dejo el código con una corrección en el returnde la función recursiva:

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 = 200000

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

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

Aportes 474

Preguntas 61

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesión.

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!

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

Estos fueron mis resultados

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

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

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!

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)

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

Cuando me contrate google compraré una laptop mejorcita :’/

con 10000:
0.02991342544555664
0.026929378509521484

Con 100000:
2.672286033630371
2.5404880046844482

n = 200000
24.1235613822937
22.07455086708069

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)

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

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

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.

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

línea de código 17, para que sea recursivo debería invocar a la función misma, osea a factorial_r y no a factorial que es una no recursiva

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

Con 100000 y 200000

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)

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

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

Puse 200 mil…
Mi PC explotó.

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)

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

<h3>¡RETO 🤓!</h3>

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

Así los resultados 😮

Factorial solo perdió para n = 50000

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.

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

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.

Con 200000, con la primer implementación tardó 38.8 segundos aproximadamente, y con la recursiva tardó 44.07 segundos

Sería interesante graficarlo y ver que tal crece.

Para las personas que tal vez tienen problema en entender estos conceptos les dejo este video que me ayudo muchísimo, el problema es que esta en inglés.
https://www.youtube.com/watch?v=Q_1M2JaijjQ

12.772971868515015
11.860903024673462

😉

En mi caso, se tardó 14.1748 seg en el factorial con ciclo cuando le mandé n=200_000.

En cuanto al factorial recursivo, ya ni salió el tiempo.

Parece que truena en ese punto a pesar de haberle subido el recursionlimit. 😥

Hola. Para los curiosos de cómo es posible de qué el bucle le gane a recursividad, aquí unas anotaciones:
Sucede que al usar recursividad nosotros consumimos más recursos al tener que guardar cada resultado de cada iteración en memoria. Esto, en casos extremos, causando el famoso= 'Stack overflow’
En cambio en la otra solución, nosotros solo hacemos uso de 1 variable que cambia su valor cada iteración, no tenemos que guardar cada resultado en memoria.

Si te gustaría explorar más la técnica en la cual se optimizó la solución: Busca Dynamic Programming.

  • 1000 →
    • 0.00040602684020996094
    • 0.001669168472290039
  • 10000 →
    • 0.026676177978515625
    • 0.03961181640625
  • 20000 →
    • 0.11501097679138184
    • 0.13064289093017578

Mi pc solo aguanta hasta 20000, despues de esta cifra me sale lo siguiente:
0.13336896896362305 (resultado de la funcion normal)
zsh: segmentation fault python3 complejidad_algoritmica.py (resultado de la funcion factorial)

My times:

Aquí mis resultados. Mi ranfla no puede pasar de n=5000 :’) así que no pude hacer más jajaja. Se aceptan donativos ;D