Contenido del curso
Análisis del Crecimiento de Funciones en Algoritmos
¿Cómo medir el crecimiento de una función matemática?
En un mundo donde las funciones matemáticas son esenciales para evaluar la eficiencia de algoritmos, entender cómo medir adecuadamente su crecimiento es crucial. Desde el análisis básico hasta la optimización de algoritmos, el conocimiento en esta área te permitirá prever comportamientos y tomar decisiones informadas. Descubre cómo contar pasos en un programa para determinar su complejidad.
¿Cuántos pasos se ejecutan en un programa?
Para empezar, es vital aprender a contar las operaciones dentro de un programa. Considera lo siguiente:
Asignaciones: Cada vez que realices una asignación de valor, anota que has llevado a cabo una operación.
Bucles independientes de X: Algunos bucles se ejecutan un número fijo de veces, sin importar el tamaño de la entrada. Por ejemplo, un bucle que itera mil veces siempre correrá esa cantidad de veces.
Bucles dependientes de X: Un bucle cuyo número de iteraciones depende del valor de X debe ser contado adecuadamente; si X es 100, el bucle correrá 100 veces.
¿Qué sucede con los bucles anidados?
Los bucles anidados presentan una complejidad mayor. Supón que tienes un bucle dentro de otro:
Interacción entre bucles: Si el primer bucle ejecuta X veces y el segundo también, obtienes un comportamiento que se puede describir como (X \times X = X^2).
Operaciones adicionales: Considera también las operaciones que se realizan dentro y fuera de los bucles.
¿Cómo representar matemáticamente las operaciones del programa?
La representación matemática de las operaciones te permite entender su crecimiento y prever el rendimiento del algoritmo:
¿Cuál es la importancia de los términos grandes?
El término de orden superior es el que dominará a medida que el tamaño del problema crezca.
¿Qué sigue después? La notación O grande
En la continuación de este tema, abordarás el concepto de notación O grande, que se enfoca en considerar solo los términos de mayor importancia y descartar los irrelevantes para simplificar el análisis de funciones y algoritmos. Esta herramienta es esencial para los desarrolladores buscando comprender rápidamente el comportamiento de sus programas en grandes escalas.
Christian Sanclemente
Estudiante
Alonso Cangalaya
Estudiante
sebastian felipe herrera sanchez
Estudiante
Jhon Freddy Puentes Nuñez
Estudiante
sergio vargas
Estudiante
David Pantoja Yescas
Estudiante
Mario Estanislao César Ariet
Estudiante
Luis Fernando Pedroza Taborda
Estudiante
Maria Guadalupe Diaz Escobar
Estudiante
Felipe Alexis Moreno Durán
Estudiante
María Fernanda Montaño Cabrera
EstudianteArturo Cadena Martinez
Estudiante
Royer Guerrero Pinilla
Estudiante
Juan García Bauzá
Estudiante
Carlos Rodríguez
Estudiante
Karl Behrens Gil
Estudiante
Walter Correa
Estudiante
Nicolás Cabrera
Estudiante
Andres Condezo Monge
Estudiante
Cristian Nahuel Kairiyama
Estudiante
Carlos Daniel Pimentel Díaz
Estudiante
José Martín Ghiena Ramos
Estudiante
Kenny Emmanuel Lajara Aquino
Estudiante
Carlos Eduardo Gomez García
Estudiante
Noldia Chavez Cavero
Estudiante
Wilson Delgado
Estudiante
Arturo Baduna
Estudiante
Edwin Jesset Barrientos Gonzales
EstudianteLuis Fernando Pedroza Taborda
Estudiante
Jaime Eduardo González Meléndez
Estudiante
Víctor Raúl Grajeda Aranda
Estudiante
Luis Mojica
Profesor
Guillermo Dario Acosta Cabrera
Estudiante
Elvis Alexander Espinoza
Estudiante
JULIAN ANDRES AGUILAR SALAZAR
Estudiante
Alexander Román
Estudiante
Adrián Castillo
EstudianteBraulio Alejo Aguilar
Estudiante
Ricardo Rito Anguiano
EstudianteAdrián Castillo
Estudiante
Rojo=función polinómica Azul = función lineal Amarillo = Función Logarítmica Verde = Constante.
Les comparto el libro: Introducción al Cálculo de James Stewart PDF-> https://drive.google.com/file/d/1fH0jmaSGXBo2IPPz3gmUToWWvr869iRz/view?usp=sharing
Gracias, gran aporte
Interesante tema. En algunas entrevistas y pruebas tecnicas lo preguntan. Ademas que esto se debe pensar al implementar/mejorar cualquier algoritmo.
Muy interesante, sería súper si pudieras compartir un poco más en relación a la entrevista o prueba técnica para estar preparados. Te lo agradecería.
si te creo David en varios vídeos dice que la habilidad de abstraer una formula para correrla en un programa y resolver un problema es lo que vuelve a un programador un programador
Comparto mi "conteo de operaciones" para el calculo de la raiz cuadrada de 2 usando los algoritmos vistos en el curso "Curso de Introducción al Pensamiento Computacional con Python"
def raizbruta(numero, epsilon = .0001): """ Calcula la raiz cuadrada con un error de epsilon recorriendo los números flotantes entre 0 y numero con un paso de epsilon numero float >0 al cual se calcula la raíz epsilon float >0 tolerancia del error """ assert type(numero) == float, f'argumento número debe tener formato float' assert numero >0, f'argumento número debe ser positivo' assert type(epsilon) == float, f'argumento epsilon debe tener formato float' assert epsilon >0, f'argumento epsilon debe ser positivo' prueba = epsilon conteo = 1 while numero-prueba**2 > epsilon: prueba += epsilon conteo += 4 """ 1 elevar al cuadrado 1 restar numero-prueba**2 1 evaluar desigualdad 1 sumar epsilon 4 total sin contar asignaciones """ print(f'Con una tolerancia de {epsilon} se usaron {conteo} cálculos para raizbruta') return prueba def raizbiseccion(numero, epsilon = .0001): """ Calcula la raiz con la busqueda por bisección para un error de epsilon. numero float >0 del cual queremos la raiz epsilon float >0 es el error o tolerancia para la aproximación """ assert type(numero) == float, f'argumento número debe tener formato float' assert numero >0, f'argumento número debe ser positivo' assert type(epsilon) == float, f'argumento epsilon debe tener formato float' assert epsilon >0, f'argumento epsilon debe ser positivo' prueba = 1 conteo = 1 while abs(prueba**2 - numero) > epsilon: prueba = (numero/prueba+prueba)*.5 conteo += 7 """ 1 elevar al cuadrado 1 restar numero 1 calcular abs 1 evaluar la desigualdad 1 numero/prueba 1 sumar prueba 1 multiplicar por .5 7 total de operaciones (sin contar asignaciones) """ print(f'Con una tolerancia de {epsilon} se usaron {conteo} cálculos para raizbiseccion') return prueba if __name__ == '__main__': numero = 2. for i in range(1,8): epsilon=10**(-1*i) print(raizbruta(numero,epsilon)) print(raizbiseccion(numero,epsilon))
Y estos son los resultados
con una tolerancia de 0.1 se usaron 53 cálculos para raizbruta 1.4000000000000001 Con una tolerancia de 0.1 se usaron 15 cálculos para raizbiseccion 1.4166666666666665 Con una tolerancia de 0.01 se usaron 565 cálculos para raizbruta 1.420000000000001 Con una tolerancia de 0.01 se usaron 15 cálculos para raizbiseccion 1.4166666666666665 Con una tolerancia de 0.001 se usaron 5653 cálculos para raizbruta 1.413999999999955 Con una tolerancia de 0.001 se usaron 22 cálculos para raizbiseccion 1.4142156862745097 Con una tolerancia de 0.0001 se usaron 56565 cálculos para raizbruta 1.4141999999998607 Con una tolerancia de 0.0001 se usaron 22 cálculos para raizbiseccion 1.4142156862745097 Con una tolerancia de 1e-05 se usaron 565685 cálculos para raizbruta 1.4142200000007974 Con una tolerancia de 1e-05 se usaron 22 cálculos para raizbiseccion 1.4142156862745097 Con una tolerancia de 1e-06 se usaron 5656853 cálculos para raizbruta 1.4142139999738421 Con una tolerancia de 1e-06 se usaron 29 cálculos para raizbiseccion 1.4142135623746899 Con una tolerancia de 1e-07 se usaron 56568541 cálculos para raizbruta 1.4142135999920156 Con una tolerancia de 1e-07 se usaron 29 cálculos para raizbiseccion 1.4142135623746899``` Como se ve, suponiendo que no hice mal el conteo, Cada iteración del método raizbiseccion tiene mas operaciones que las iteraciones de raizbruta. Sin embargo, el método de la bisección converge más rápido.
Wow Mario la sacastes del estadio con tremendo analisis, gracias por compartirlo.
Gracias por compartirlo
Realice la verificación del código por parte e identifique que la función descrita en el ejemplo es: F(x) = 1000 + X2 + 2X2
Si quisiéramos la función F(x) = 1000 + X + X2
Deberiamos escribir:
def f(x): respuesta = 0 for i in range(1000): respuesta += 1 for i in range(x): respuesta += 1 for i in range(x): for j in range(x): respuesta += 1 return respuesta```
completamente de acuerdo ya que en el codigo del video al entrar al segundo loop for se esta sumando x veces x lo que seria igual a x2
El profesor lo que hace es contar el numero de operaciones que se realizan en la función, no en si el resultado, pensé lo mismo al principio y lo volví a ver, el cuenta el número de operaciones, puedes ir al momento en que inicia a escribir en rojo para checar.
Deberian ondar mas en big o talvez cereando un curso de entrevistas tecnicas donde se incluya esto creo que tienen los recursos team platzi. Pista: Pablo Trinidad Google Dev
Totalmente de acuerdo. Este tema da para desarrollarlo muchísimo más.
Tienes toda la razón.
Les dejo un link con mis apuntes https://github.com/karlbehrensg/poo-y-algoritmos-python Conteo abstracto de operación
Con esta técnica contamos los pasos que realiza nuestro algoritmo. En el siguiente ejemplo respuesta tendrá los números de pasos que realiza nuestro código al ejecutar.
def f(x): respuesta = 0 for i in range(1000): respuesta += 1 for i in range(x): respuesta += x for i in range(x): for j in range(x): respuesta += 1 respuesta += 1 return respuesta
Bro excelente tu post, felicitaciones (Y)
Hola les comparto un vídeo muy interesante. Como analizar nuestros Algoritmos.
Gracias.
solo puedo decir que me explotó la cabeza gracias por compartirlo
Me di cuenta que el profesor David no definió bien el polinomio. Él escribió el polinomio como
1002 + x + 2x^2
cuando debió ser
1000 + x + 2x^2
¿Porqué? Porque cuando x = 0 los términos de grado 2 y grado 1 deben ser cero, haciendo que solo se ejecute el primer loop con range(1000). Esto es fácil de comprobar si se ejecuta el código: con x = 0 el resultado es 1000, no 1002. Y, cuando x = 1, el resultado es 1003, no 1005.
Si f(0) = 1000 + 0 + 2.0^2, el resultado es 1001, porque todo numero elevado en 0 es 1. Teniendo en cuenta que la función range(1000) no es inclusivo, el resultado es 999, más la revolución de la variable respuesta. De todas formas, creo que tienes razón en cuanto a la expresión del polinomio.
El profesor lo definió bien, porque aquí lo que se está tratando de hacer es calcular la complejidad del algoritmo (en base a la cantidad de operaciones que realizará el algoritmo), no el resultado que arrojará. Tu fórmula sirve para calcular el resultado del algoritmo, no la complejidad.
Ahora, imagina que te dicen que calcule la complejidad de un algoritmo que al final solo devuelve cientos de comparaciones y al final solo devuelve True o False. ¿Cómo utilizarías el resultado del algoritmo para calcular su complejidad? Dirías que su complejidad solo es 1 o 0 a pesar de que realizó cientos de operaciones internamente?
La respuesta no tiene nada que ver con la complejidad del algoritmo. La forma correcta en la que enseñó el profesor.
Interesante, por lo que veo básicamente estamos contando la cantidad de veces que el algoritmo va a ejecutar una operación mediante ecuaciones, es decir, contamos la cantidad de operaciones que se van a ejecutar dentro de ese algoritmo 🤔 Y gracias a esa ecuación, a medida que la variable va cambiando, podemos ver cuál es la sección del código está teniendo mayor peso, o al menos así es como lo interpreto yo 🤔
def f(x): respuesta = 0 for i in range(1000): respuesta += 1 for i in range(x): respuesta += x for i in range(x): for j in range(x): respuesta += 1 respuesta += 1 return respuesta```
Que fascinante!!!! no sabía que los polinomios podían llegar a aplicarse de tal forma!
A re tramposo ajaa
Big O notation se utiliza en informática para describir el rendimiento o la complejidad de un algoritmo. Big O describe específicamente el peor de los casos, y se puede utilizar para describir el tiempo de ejecución requerido o el espacio utilizado (por ejemplo en la memoria en el disco) por un algoritmo.
Esto me hace recordar de la clase de analisis de algoritmos donde se calculaba el tiempo de ejecución de cada algortimo (factorial, fibonacci, algoritmos de ordenamiento, etc), por eso no me dio tan duro entender este conteo abstracto de operación.
Para calcular la raíz de 17:
Mediante Enumeración Exhaustiva se utilizaron 11 operaciones, pero no se llegó a la solución :( Mediante Búsqueda Binaria se utilizaron 65 operaciones y se llegó a 4.12548828125 Mediante Aproximación se emplearon 12659 y se llegó a 4.1201171875
El resultado es 4.123105626, de manera que la Búsqueda Binaria fue el método que se acercó más a la solución con menos operaciones que la Aproximación.
No me queda del todo claro porqué los terminos que más nos importan son los que se acercan al infinito, alguien sabe porque?
Porque siempre nos ha importado lo desconocido, y no hay nada mas desconocido que el infinito (excepto para [George Cantor](https://es.wikipedia.org/wiki/Georg_Cantor.
Primero hay que notar que en el algoritmo del ejemplo, la x va a tener un gran peso en cuanto al numero de computaciones que va a llevar a un resultado ya que define las iteraciones en los for del mismo, luego una vez definida la ecuación, si hacemos que x vaya tomando valores cada vez mas grandes arbitrariamente(lo que se dice en términos matemáticos, 'x tiende a infinito') el valor que toma la expresión se hace cada vez mas grande(también tiende a infinito) y la constante que 1002 se vuelve insignificante(despreciable) en comparación con los otros términos.
Es claro que hay que tomar algunas clases de matemáticas para recordar cosas y también que a este profe no le entiendo nada jajajajajajaja, es un duro mucho respeto para el, pero sus dos cursos son los que mas trabajo me ha costado entender.
Choca esos 5 estamos igual.
Un poco de introdución a Big(o) :o
Platzi deberían crear un curso especifico de Big O Notation!
¿Por que ciclos de for anidados dice que es 2X**2? No logro comprender, si alguien me podría ayudar por favor
Hola Braulio_Alejo :D El ciclo for, como bien sabes, se encarga de ejectuar el codigo cierta cantidad de veces, segun la manera en que lo construimos, en este caso:
for i in range(x): for j in range(x): r+=1
Esto sucedera de la siguiente manera, digamos que x = 4 Comenzara el ciclo siendo: i = 0 Siendo que dentro de este bucle existe otro bucle: entrara en j = 0 y sumara, despues j sera igual a 1 y asi hasta que sea 3.
Teniendo esto, sabemos que entra 4 veces en J cuando I = 0 Una vez termina el ciclo de I = 0, tenemos que I tomara el valor de 1 I = 1, una vez pasando esto, volvera a iniciar el bucle de J desde 0 hasta que tenga el valor de 3.
Siendo esto, tenemos que cada vez que pasa por i, tambien pasara x veces por j, en este caso 4 veces.
Por lo tanto tenemos que x veces que i pasa por * x veces en j. sera igual a x^2
podemos verlo como una matriz: " i i i i | j j j j | | j j j j | | j j j j | | j j j j | Como veras, por cada i, el bucle se repite x veces, 4 + 4 +4 +4 Vamos a ver un segundo caso:
for i in range(x): for j in range(y): r+=1
En este caso para saber cuantas veces pasara el bucle, sera el valor de xy, puesto que se repetira en i en todos los numeros menores a x al igual que en j en todos los numeros menores a y.
Respuesta más corta: Primera X hace referencia al for en "i" Segunda X hace referencia al for en "j"
Multiplicas esas dos operaciones y obtienes: X*X = X^2
Y por ultimo dentro de el segundo for (El for de j) Se encuentran definidas dos operaciones respuesta "+= 1 y respuesta +=1" a esto hace referencia con 2
Por tanto da como resultado el: 2X^2
