Platzi
Platzi

¡Invierte en ti y celebremos! Adquiere un plan Expert o Expert+ a precio especial.

Antes: $349
$259
Currency
Antes: $349
Ahorras: $90
COMIENZA AHORA
Termina en: 17D : 21H : 29M : 11S

Debes tener cuenta en Platzi

Para ver esta clase abierta debes iniciar sesión

Introducción a la complejidad algorítmica11/25

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
Sin título.png

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)

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

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

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

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)

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

con 10000:
0.02991342544555664
0.026929378509521484

Con 100000:
2.672286033630371
2.5404880046844482

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:
ecomplejidadPy.png

n = 200000
24.1235613822937
22.07455086708069

Captura de pantalla de 2020-05-28 11-10-11.png

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

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

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!

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

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

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

time.jpg

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.

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?
carbon.png

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

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

Captura de pantalla (21).png

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

el método iterativo tiene un paso menos que el recursivo, si se fijan la recursión para hasta que el valor de n es igual a 1, eso significa que n = 1 se esta teniendo en cuenta.En cambio, en la versión iterativa nunca se opera cuando n es igual a 1 ya que en ese caso no se ingresa a l loop while, no es necesario operar n = 1 en el método iterativo, sin embargo, desde la construcción de los mismos algortimos se verifica que se va a tener un paso menos en la iteración comparado a la recursividad.

200.000

10.496364831924438
10.486165761947632

Esta maquina vuela
n = 200,000
bucle 0.0010027885437011719
recusivo 0.004001617431640625

n = 200000
0.0010111331939697266
0.0009877681732177734

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

Complejidad Temporal.png

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

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.

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

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

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.

Python

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.

Por si a alguien le interesa y quiere complementar lo aprendido en esta clase…(Más allá de que ya haya quedado claro que hay un error en el código, lo cual es fácilmente subsanable)
https://ocw.unican.es/pluginfile.php/1246/course/section/1539/eda-tema2.pdf

Con 1000:
Sin recursividad 0.0
Con recursividad 0.000997304916381836

Con 10000:
Sin recursividad 0.022943496704101562
Con recursividad 0.022943496704101562

Con 50000:
Sin recursividad 0.6133561134338379
Con recursividad 0.6083202362060547

Con 100000:
Sin recursividad 2.5938313007354736
Con recursividad 2.5482211112976074

Que lindo ver que usa vscode, pero con el modo VI

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) 

Estos son los tiempos que se tomo mi computadora, creo que es bastante rápida la verdad.

Con 10,000
7.152557373046875e-07
3.0994415283203125e-06

Con 100,000
9.5367431640625e-07
7.152557373046875e-07

Con 200,000
1.1920928955078125e-06
9.5367431640625e-07

Para 100000 registros, en una maquina virtual, siempre siendo mayor el tiempo del recursivo

9.627435684204102
10.008164405822754

Mi compu tardo

14.307519435882568
15.52149224281311

Captura de pantalla 2021-03-23 201640.png

mi pc ejecuto sin problemas
mis dos tiempos con 200 000
14.045423746109009
14.178290843963623

n = 1000
Loop: 0.0005083084106445312
Recursividad: 0.00045752525329589844
n = 10000
Loop: 0.04527854919433594
Recursividad: 0.042467594146728516
n = 50000
Loop: 1.0868217945098877
Recursividad: 1.0809297561645508
n = 100000
Loop: 5.407958745956421
Recursividad: 4.908452033996582
n = 200000
Loop: 28.592811584472656
Recursividad: 28.926639080047607

no sé cuando se volverá la recursión más ineficiente pero en mi pc la recursión sigue siendo más eficiente
incluso para esta n = 1_000_000_000 (en python puedes separar los ceros con guion bajo, no pasa nada.)

sin recursión = 114.17801904678345
con recursión = 101.00001072883606

Ayuda para interpretar el problema please

import time

def Cronometro(funcion_factorial):
    def inside(n):
        start = time.time()
        funcion_factorial(n)
        end = time.time()
        print(end - start)
    return inside

@Cronometro
def factorial(n):
    result = 1
    while n > 1:
        result *= n
        n -= 1
    return result

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


if __name__ == '__main__':

    n = 99999

    try:
        factorial(n)
    except ValueError:
        print('falla en el factorial iterativo')

    try:
        factorial_r(n)
    except ValueError:
        print('falla en el factorial recursivo')

El error es:

λ python Complejidad_Algoritmica.py
3.2163960933685303
3.061840772628784
Traceback (most recent call last):
  File "Complejidad_Algoritmica.py", line 36, in <module>
    factorial_r(n)
  File "Complejidad_Algoritmica.py", line 6, in inside
    funcion_factorial(n)
  File "Complejidad_Algoritmica.py", line 23, in factorial_r
    return n * factorial(n - 1)
TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'

muchas gracias al que me ayude a entender esto.

En el libro “Applied Linear Algebra and Matrix Analysis” de Shores, se explica muy bien esto, aunque el libro en verdad es de algebra lineal se habla mucho de la parte computacional y siempre se habla de la complejidad algoritmica de los metodos usados.

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

Creo hay un error:
debería ser return n * factorial_r(n - 1) "con la _r "

Aplicando esto el segundo algoritmo es mas lento

pues si ha de estar potente su equipo, a mi computadora le llevo al rededor de 200 segundos el cálculo del factorial de 500000.

1000 { iterativa = 0.00099778173540039
recursiva = 0.0
10000 { iterativa = 0.008922080993652344
recursiva = 0.028921842575073242
200000{ iterativa = 13.758224248886108
recursiva = 13.614301443099976

Asus Core i7 10th GEN

al maestro 18.09
me 25.12 ja

Se demoro mucho tiempo con n=200000

normal 55.245145320892334
recursivo 66.56243133544922

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
Sin título.png

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)

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

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

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

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)

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

con 10000:
0.02991342544555664
0.026929378509521484

Con 100000:
2.672286033630371
2.5404880046844482

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:
ecomplejidadPy.png

n = 200000
24.1235613822937
22.07455086708069

Captura de pantalla de 2020-05-28 11-10-11.png

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

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

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!

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

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

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

time.jpg

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.

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?
carbon.png

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

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

Captura de pantalla (21).png

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

el método iterativo tiene un paso menos que el recursivo, si se fijan la recursión para hasta que el valor de n es igual a 1, eso significa que n = 1 se esta teniendo en cuenta.En cambio, en la versión iterativa nunca se opera cuando n es igual a 1 ya que en ese caso no se ingresa a l loop while, no es necesario operar n = 1 en el método iterativo, sin embargo, desde la construcción de los mismos algortimos se verifica que se va a tener un paso menos en la iteración comparado a la recursividad.

200.000

10.496364831924438
10.486165761947632

Esta maquina vuela
n = 200,000
bucle 0.0010027885437011719
recusivo 0.004001617431640625

n = 200000
0.0010111331939697266
0.0009877681732177734

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

Complejidad Temporal.png

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

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.

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

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

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.

Python

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.

Por si a alguien le interesa y quiere complementar lo aprendido en esta clase…(Más allá de que ya haya quedado claro que hay un error en el código, lo cual es fácilmente subsanable)
https://ocw.unican.es/pluginfile.php/1246/course/section/1539/eda-tema2.pdf

Con 1000:
Sin recursividad 0.0
Con recursividad 0.000997304916381836

Con 10000:
Sin recursividad 0.022943496704101562
Con recursividad 0.022943496704101562

Con 50000:
Sin recursividad 0.6133561134338379
Con recursividad 0.6083202362060547

Con 100000:
Sin recursividad 2.5938313007354736
Con recursividad 2.5482211112976074

Que lindo ver que usa vscode, pero con el modo VI

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) 

Estos son los tiempos que se tomo mi computadora, creo que es bastante rápida la verdad.

Con 10,000
7.152557373046875e-07
3.0994415283203125e-06

Con 100,000
9.5367431640625e-07
7.152557373046875e-07

Con 200,000
1.1920928955078125e-06
9.5367431640625e-07

Para 100000 registros, en una maquina virtual, siempre siendo mayor el tiempo del recursivo

9.627435684204102
10.008164405822754

Mi compu tardo

14.307519435882568
15.52149224281311

Captura de pantalla 2021-03-23 201640.png

mi pc ejecuto sin problemas
mis dos tiempos con 200 000
14.045423746109009
14.178290843963623

n = 1000
Loop: 0.0005083084106445312
Recursividad: 0.00045752525329589844
n = 10000
Loop: 0.04527854919433594
Recursividad: 0.042467594146728516
n = 50000
Loop: 1.0868217945098877
Recursividad: 1.0809297561645508
n = 100000
Loop: 5.407958745956421
Recursividad: 4.908452033996582
n = 200000
Loop: 28.592811584472656
Recursividad: 28.926639080047607

no sé cuando se volverá la recursión más ineficiente pero en mi pc la recursión sigue siendo más eficiente
incluso para esta n = 1_000_000_000 (en python puedes separar los ceros con guion bajo, no pasa nada.)

sin recursión = 114.17801904678345
con recursión = 101.00001072883606

Ayuda para interpretar el problema please

import time

def Cronometro(funcion_factorial):
    def inside(n):
        start = time.time()
        funcion_factorial(n)
        end = time.time()
        print(end - start)
    return inside

@Cronometro
def factorial(n):
    result = 1
    while n > 1:
        result *= n
        n -= 1
    return result

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


if __name__ == '__main__':

    n = 99999

    try:
        factorial(n)
    except ValueError:
        print('falla en el factorial iterativo')

    try:
        factorial_r(n)
    except ValueError:
        print('falla en el factorial recursivo')

El error es:

λ python Complejidad_Algoritmica.py
3.2163960933685303
3.061840772628784
Traceback (most recent call last):
  File "Complejidad_Algoritmica.py", line 36, in <module>
    factorial_r(n)
  File "Complejidad_Algoritmica.py", line 6, in inside
    funcion_factorial(n)
  File "Complejidad_Algoritmica.py", line 23, in factorial_r
    return n * factorial(n - 1)
TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'

muchas gracias al que me ayude a entender esto.

En el libro “Applied Linear Algebra and Matrix Analysis” de Shores, se explica muy bien esto, aunque el libro en verdad es de algebra lineal se habla mucho de la parte computacional y siempre se habla de la complejidad algoritmica de los metodos usados.

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

Creo hay un error:
debería ser return n * factorial_r(n - 1) "con la _r "

Aplicando esto el segundo algoritmo es mas lento

pues si ha de estar potente su equipo, a mi computadora le llevo al rededor de 200 segundos el cálculo del factorial de 500000.

1000 { iterativa = 0.00099778173540039
recursiva = 0.0
10000 { iterativa = 0.008922080993652344
recursiva = 0.028921842575073242
200000{ iterativa = 13.758224248886108
recursiva = 13.614301443099976

Asus Core i7 10th GEN

al maestro 18.09
me 25.12 ja

Se demoro mucho tiempo con n=200000

normal 55.245145320892334
recursivo 66.56243133544922