<jupyter_start><jupyter_text>Analisis de algoritmosAlumno: <NAME>Grupo: 3CM2Profesor: Dr. <NAME> 1Explicacion del programaComo vimos al inicio del semestre existen diversas complejidades para los algoritmos las cuales son logn, n, nlogn, n2, 2n y n!. Cada uno con diferentes tiempos de ejecución, en la anterior lista se meciono desde el mas rapido siendo logn el más rapido (aunque un algoritmo constante seria más rapido) hasta n! que es el mas lentoPara poder desarrollar esta practica fue necesario de hacer uso de la Big O tratando de encontrar la complejidad de alguna función para poder obtener cada caso, esto fue una tarea bastante interesante y entretenida, ya que teniamos algunos ejemplos ya hechos de algunas complejidades como fue la lineal, la cuadratica y la cubica, sin embargo, hacer la logaritmica, la exponencial y el factorial fue necesario de hacer uso tanto de la Big O como las ecuaciones de recurrencia para calcular la complejidad del algoritmo.El desarrollo de la función logaritmica solo me base en un ejemplo que ya habiamos hecho (una ecuacion de recurrencia), de esa ecuación veiamos que T(n/2) era lo que provocaba la complejidad logartimica y el "+1" era el caso base asi que solo fue necesario hacer el caso base y llamar la misma función con (n/2), es decir, funcion(n/2).El desarrollo de la función exponencial fue igual que la logaritmica solo me base en un ejemplo que ya habiamos hecho (una ecuacion de recurrencia), de esa ecuación veiamos que solo 2T(n-1) era lo que provocaba la complejidad exponencial y el "+1" era el caso base asi que solo fue necesario hacer el caso base y llamar la misma función con (n-1), es decir, funcion(n-1) pero ocupamos el doble con lo cual poniamos dos veces funcion(n-1).Por ultimo el desarrollo de la función factorial fue igual que las anteriores solo me base en un ejemplo que ya habiamos hecho (una ecuacion de recurrencia), de esa ecuación veiamos que solo n*T(n-1) era lo que provocaba la complejidad factorial y el "+1" era el caso base asi que solo fue necesario hacer el caso base y hacer un for para llamar de nuevo a la función provocando casi el hecho de tener n*T(n-1). ** Import packages Numpy and Matplotlib**<jupyter_code>import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline<jupyter_output><empty_output><jupyter_text>** Defining some functions **<jupyter_code>def func_n(n):
    res=0
    for i in range(len(n)):
        res=res+n[i]
    return res

def func_n_2(n):
    res=0
    for i in range(len(n)):
        for j in range(len(n)):
            res=res+n[i]
    return res

def func_n_3(n):
    res=0
    for i in range (len(n)):
        for j in range (len(n)):
            for k in range (len(n)):
                res=res+n[i]
    return res

def exponencial(n):
    if(n==0):
        return 0
    res1=exponencial(n-1)
    res2=exponencial(n-1)
    return res1+res2

def logaritmo(n):
    if(n==0):
        return 0
    res=logaritmo(n/2)
    return res

def factorial(n):
    for i in range(n):
        factorial(n-1)
    return n

def func_log_n(n):
    if len(n)==1:
        return n[0]
    mid=int(len(n)/2)
    res1=func_log_n(n[:mid])
    res2=func_log_n(n[mid:])
    return res1+res2

        
x = np.arange(1, 128, 1) #An array of 100 elements
x #Displays the array. Only works in a Jupyter notebook<jupyter_output><empty_output><jupyter_text>** Using matplotlib.pyplot to display some plots. More information on matplotlib.org **<jupyter_code>#plt.plot(x,10,label="constant")
plt.plot(x,x,label="linear")
plt.plot(x,np.log(x),label="log-n")
plt.plot(x,np.sqrt(x),label="sqrt")
#plt.plot(x,x*np.log(x),label="n-logn")
#plt.plot(x,x**2,label="cuadratic")
#plt.plot(x,x**3,label="cubic")
#plt.plot(x,2**x,label="2^n")
#plt.plot(x,factorial_array(x),label="factorial")
#print(x)

plt.xlabel('n')
plt.ylabel('time')

plt.title("Growth functions")

plt.legend()

plt.show()<jupyter_output><empty_output><jupyter_text>** Using Timer to measure the time for a function **<jupyter_code>import numpy as np
from timeit import Timer

size=64
x=np.arange(0,size)
y=np.zeros(size)
j=0

for i in x:

  n = i
  N = np.arange(0, n, 1) #An array of n elements


  #Setups the functions to be called
  setupstr="""
import numpy as np
from __main__ import func_n
from __main__ import n
from __main__ import N
"""

  #print(setupstr)

  #Each variable methodN has a string that holds to the stament to mearure in time
  method1="""
func_n(N)
"""

  nl = 1000 #The number of times that a methodN is executed
  t1 = Timer(method1, setupstr).timeit(nl)

  y[j]=t1
  j+=1

  #calculates the result
  r1=func_n(N)

  #Prints the time for each method
  print ('n=',n,"\t\ttime:", t1/nl," seconds\t result=",r1)


#Graph the results
print(x)
print(y)

plt.plot(x,y,label="func")
#plt.plot(x,x**2,label="cuadratic")

plt.xlabel('n')
plt.ylabel('time')

plt.title("Linear Growth")

plt.legend()

plt.show()

import numpy as np
from timeit import Timer

size=64
x=np.arange(0,size)
y=np.zeros(size)
j=0

for i in x:

  n = i
  N = np.arange(0, n, 1) #An array of n elements


  #Setups the functions to be called
  setupstr="""
import numpy as np
from __main__ import func_n_2
from __main__ import n
from __main__ import N
"""

  #print(setupstr)

  #Each variable methodN has a string that holds to the stament to mearure in time
  method1="""
func_n_2(N)
"""

  nl = 1000 #The number of times that a methodN is executed
  t1 = Timer(method1, setupstr).timeit(nl)

  y[j]=t1
  j+=1

  #calculates the result
  r1=func_n_2(N)

  #Prints the time for each method
  print ('n=',n,"\t\ttime:", t1/nl," seconds\t result=",r1)


#Graph the results
print(x)
print(y)

plt.plot(x,y,label="func")
#plt.plot(x,x**2,label="cuadratic")

plt.xlabel('n')
plt.ylabel('time')

plt.title("Cuadratic Growth")

plt.legend()

plt.show()
import numpy as np
from timeit import Timer

size=25
x=np.arange(0,size)
y=np.zeros(size)
j=0

for i in x:

  n = i
  N = np.arange(0, n, 1) #An array of n elements


  #Setups the functions to be called
  setupstr="""
import numpy as np
from __main__ import func_n_3
from __main__ import n
from __main__ import N
"""

  #print(setupstr)

  #Each variable methodN has a string that holds to the stament to mearure in time
  method1="""
func_n_3(N)
"""

  nl = 1000 #The number of times that a methodN is executed
  t1 = Timer(method1, setupstr).timeit(nl)

  y[j]=t1
  j+=1

  #calculates the result
  r1=func_n_3(N)

  #Prints the time for each method
  print ('n=',n,"\t\ttime:", t1/nl," seconds\t result=",r1)


#Graph the results
print(x)
print(y)

plt.plot(x,y,label="func")
#plt.plot(x,x**2,label="cuadratic")

plt.xlabel('n')
plt.ylabel('time')

plt.title("Cubic Growth")

plt.legend()

plt.show()
import numpy as np
from timeit import Timer

size=10
x=np.arange(0,size)
y=np.zeros(size)
j=0

for i in x:

  n = i
  N = np.arange(0, n, 1) #An array of n elements


  #Setups the functions to be called
  setupstr="""
import numpy as np
from __main__ import exponencial
from __main__ import i
"""

  #print(setupstr)

  #Each variable methodN has a string that holds to the stament to mearure in time
  method1="""
exponencial(i)
"""

  nl = 1000 #The number of times that a methodN is executed
  t1 = Timer(method1, setupstr).timeit(nl)

  y[j]=t1
  j+=1

  #calculates the result
  r1=exponencial(i)

  #Prints the time for each method
  print ('n=',n,"\t\ttime:", t1/nl," seconds\t result=",r1)


#Graph the results
#print(x)
#print(y)

plt.plot(x,y,label="func")
#plt.plot(x,x**2,label="cuadratic")

plt.xlabel('n')
plt.ylabel('time')

plt.title("Exponencial Growth")

plt.legend()

plt.show()
import numpy as np
from timeit import Timer

size=100
x=np.arange(0,size)
y=np.zeros(size)
j=0

for i in x:

  n = i
  N = np.arange(0, n, 1) #An array of n elements

  #Setups the functions to be called
  setupstr="""
import numpy as np
from __main__ import logaritmo
from __main__ import i
"""

  #print(setupstr)

  #Each variable methodN has a string that holds to the stament to mearure in time
  method1="""
logaritmo(i)
"""

  nl = 1000 #The number of times that a methodN is executed
  t1 = Timer(method1, setupstr).timeit(nl)

  y[j]=t1
  j+=1

  #calculates the result
  r1=logaritmo(i)

  #Prints the time for each method
  print ('n=',n,"\t\ttime:", t1/nl," seconds\t result=",r1)


#Graph the results
#print(x)
#print(y)

plt.plot(x,y,label="func")
#plt.plot(x,x**2,label="cuadratic")

plt.xlabel('n')
plt.ylabel('time')

plt.title("Logarithm Growth")

plt.legend()

plt.show()
import numpy as np
from timeit import Timer

size=10
x=np.arange(0,size)
y=np.zeros(size)
j=0

for i in x:

  n = i
  N = np.arange(0, n, 1) #An array of n elements

  #Setups the functions to be called
  setupstr="""
import numpy as np
from __main__ import factorial
from __main__ import i
"""

  #print(setupstr)

  #Each variable methodN has a string that holds to the stament to mearure in time
  method1="""
factorial(i)
"""

  nl = 1000 #The number of times that a methodN is executed
  t1 = Timer(method1, setupstr).timeit(nl)

  y[j]=t1
  j+=1

  #calculates the result
  r1=factorial(i)

  #Prints the time for each method
  print ('n=',n,"\t\ttime:", t1/nl," seconds\t result=",r1)


#Graph the results
#print(x)
#print(y)

plt.plot(x,y,label="func")
#plt.plot(x,x**2,label="cuadratic")

plt.xlabel('n')
plt.ylabel('time')

plt.title("Factorial Growth")

plt.legend()

plt.show()<jupyter_output>n= 0 		time: 2.0549999999275314e-07  seconds	 result= 0
n= 1 		time: 7.106000000050016e-07  seconds	 result= 1
n= 2 		time: 1.828299999999672e-06  seconds	 result= 2
n= 3 		time: 6.6951999999957935e-06  seconds	 result= 3
n= 4 		time: 3.131380000000661e-05  seconds	 result= 4
n= 5 		time: 0.00014155759999999874  seconds	 result= 5
n= 6 		time: 0.0008014768000000032  seconds	 result= 6
n= 7 		time: 0.0087209474  seconds	 result= 7
n= 8 		time: 0.11326981179999998  seconds	 result= 8
n= 9 		time: 1.009739352  seconds	 result= 9
StarcoderdataJupyterStructuredCleanDedup