Complejidad Algorítmica: Comparación y Medición de Eficiencia

Clase 2 de 16 • Curso de Complejidad Algorítmica con Python

Resumen

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)

Gastón Gentile

student•

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!

Jose Colmenares

student•

Grande! Que interesante

Alfonso Morán

student•

Gracias, pero aunque ponga yo mismo el límite el programa falla con la función recursiva.

MemoryError: Stack overflow

Walter Correa

student•

Estos fueron mis resultados

Santiago Ahumada Lozano

student•

¡Excelente!

Julian Omar Meza

student•

Son los mismos valores para otra referencia en los tiempos.

Julio Hurtado

student•

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

Julio Hurtado

student•

Haciendo el método recursivo yo obtengo un error que dice:

return n * factorial_r(n - 1) [Previous line repeated 995 more times] File ".\factorial.py", line 14, in factorial_r if n == 1: RecursionError: maximum recursion depth exceeded in comparison

Joel Eduardo Gaspar

student•

Con esto se soluciona ese problema

import sys
sys.setrecursionlimit(1000000)

Emilian Harastasan

student•

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

Angel de Jesus Rodríguez Venegas

student•

Buen aporte!

Eber Laurente Lliuyacc

student•

Sí tienes razón, pero es un error fácil de darse cuenta. :)

Juan Pablo Gómez García

student•

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

Byron Oyarzún Venegas

student•

Buen detalle!

Carlos Rodríguez

student•

Buen detalle.

Martin Mendez

student•

El factorial recursivo deberia ser con _r al final

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

Daniel Andrés Giraldo Benites

student•

asi es compañero fue un pequeño error

Beder Danilo Casa Condori

student•

exacto

Karl Behrens Gil

student•

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)

José Szychowski

student•

sos un genio amigo

Omar Rodríguez Aldama

student•

me encanto muchas felicidades, apuntes increibles ❤️

Francisco Leví Méndez Delgado

student•

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):
    &quot;&quot;&quot;Factorial recursivo.&quot;&quot;&quot;
    if n == 1:
        return 1
    return n * factorial_r(n - 1)

Jesús Lautaro Careglio Albornoz

student•

No parece que está mal implementada, ESTÁ mal implementad.... este profe esta arrastrando muchas fallas...

Royer Guerrero Pinilla

student•

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

Carolina Acosta Muñoz

student•

Lo leeré más tarde, gracias!!!

Omar Rodríguez Aldama

student•

wow esta muy completo, gracias por compartirlo

Gonzalo Ferrando

student•

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

Gonzalo Ferrando

student•

Eso explica que los resultados den tan próximos: Si probamos con n = 100 se nota:

3.1948089599609375e-05
0.00035190582275390625

y con n = 1000

RecursionError: maximum recursion depth exceeded in comparison

Jose Cardenas

student•

No es un error, Eel factorial de un numero se puede escribir como n! = n*(n-1)! Intentalo en tu calculadora y verás que si

JAVIER SANTIAGO SALGADO

student•

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

Andres Julian Mendez Pizarro

student•

Por que se demoran en corregir el video, ya que la demora parecida es por que a la primera llamada de la recursividad se va al factorial del while lo que hace que se demoren practicamente lo mismo siempre.

Roger Carlos Ariel Alba

student•

Hola Andres,

Gracias por tu feedbak. Lo apreciamos. ¿Cuál es exactamente el problema? Estamos revisando ya el video. También nos puedes escribir a team@platzi.com y con gusto damos seguimiento a tu caso.

Saludos

Moisés Manuel Morín Hevia

student•

Yo lo veo todo bien

Alejandro Castaño Vargas

student•

Mi computadora cuenta con 12GB de RAM, sin embargo, cuando uso un n mayor o igual a 2900 el código no lanza errores ni nada, simplemente se detiene y no ejecuta el resto del código ¿alguien sabe qué sucede? RAM utilizable: 11,9 GB

Algunas obviedades como el 2 en las variables de tiempo o los 'aaaa' eran para ver dónde se detenía el programa

import time
import sys

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

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

if __name__ == '__main__':
    n = 2900

    sys.setrecursionlimit(n + 100)

    inicio2 = time.time()
    print('aaaa')
    factorial_r(n)
    print('aa')
    final2 = time.time()
    tiempo2 = final2-inicio2
    print(tiempo2)

    inicio = time.time()
    factorial(n)
    final = time.time()
    tiempo = final-inicio
    print (tiempo)

José Manuel Barajas Ramírez

student•

Me pasa lo mismo.

Vanessa Tejerina

student•

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&gt;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!

David Rosas

student•

Gracias! Sabes de esas cosas raras? Quisiera resolverlo jaja Encontre que podemos ver el limite importando sys y ...

import sys
print(sys.getrecursionlimit()) #(1000)

E incluso cambiarlo con sys.setrecursionlimit(1500) pero advierten que puede ser peligroso y deberiamos optar por cambiar el algoritmo iterativamente. https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it

Juan Nuñez

student•

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

Neo TRAN

student•

Quizás es una duda muy simple, pero en la función recursiva que tiene el profesor llama a factorial() en lugar de a factorial_r()

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

    return n * factorial(n - 1)

Para que una función sea recursiva se tiene que llamar a ella misma, ¿no? Entonces tendríamos

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

    return n * factorial_r(n - 1)

Quizás ya muchos han dado una respuesta a eso, pero me ha quedado esa duda

Juan Pablo Celiz

student•

Así es, tienes razón. Recursión.

Cesar Eduardo Montoya Santiago

student•

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)

Pedro Alejandro Rodríguez García

student•

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

Moisés Manuel Morín Hevia

student•

Hola, soy google.

Jherom Chacon

student•

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

Chris Rico

student•

Qu funcion tiene el import sys o generalmente para que mas se usa? gracias por tu aporte

Kevin Inca

student•

Programa corregido y con las limitantes de Python en 1M.

import time
import sys

sys.setrecursionlimit(1000000)
def factorial(n):
    respuesta = 1

    while n &gt; 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__ == &quot;__main__&quot;:
    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)```