Notación asintótica y complejidad algorítmica básica
Contenido del curso
Jhon Freddy Puentes Nuñez
Carlos Guzman
Jhon Freddy Puentes Nuñez
Alberto Sánchez
Brandy Luis Lopez Pacheco
Tomas Filippo
Diego Alejandro Medina López
José Raúl Gómez Hinojosa
Maria Guadalupe Diaz Escobar
José Ocando
Ricardo San Martín Hidalgo
Carlos Rodríguez
Zain Abimael Barradas Mendoza
Jose de Jesus Herrera Ledon
Mauricio Barrera
Noldia Chavez Cavero
Ronaldo Carbajal Tapahuasco
iecgerman .
Diego Cáceres
Mauricio Barrera
Lorenzo Enrique Piñango Cerezo
Karl Behrens Gil
Diego Ignacio Cusicanqui Adaros
Gabriel Ospina
Manuel Alejandro Hermoso
Raymundo Soto Soto
Óscar Felipe Betancur Lopera
Carmen Sánchez Salgado
Angel Gerardo Ochoategui Occampo
Anthony Smith Quispe De la cruz
Sebastián Gonzalez Quintero
Michelle Osorio
JESUS ALBERTO CARREÑO MARTINEZ
Sergio Daniel Castañeda Pérez
CRISTIAN BARBERO PÉREZ
Eber Laurente Lliuyacc
Iván Ricardo Bohórquez Basto
Mauricio Gonzalez Falcon
Ruben Dario Hernandez Centeno
JAVIER SANTIAGO SALGADO
Luis Fernando Pedroza Taborda
Juan Carlos Barbaran Meza
Fredy Mendoza Vargas
Un loop => crecimiento lineal. Un loop dentro de otro => crecimiento cuadratico Llamadas recursivas => crecimiento exponecncial.
Tengo la duda de si una función recursiva que solo se invoca así misma una vez, ejemplo la del factorial, también seria exponencial?
Hola @krloschicometal si, sería exponencial con una iteración.
Notacion asintótica
Big O notation.
Crecimiento asintótico
No importan las variaciones pequeñas.
El enfoque se centra en lo que pasa conforme el tamaño del problema se acerca al infinito
Mejor de los casos, promedio, peor de los casos.
Nada más importa el término de mayor tamaño.
Ejemplos:
def f(n) for i in range(n): print(i) for i in range(n): print(i)
O(n) + O(n) = O(n+n) = O(2n) = O(n) //Crecimiento lineal
def f(n) for i in range(n): print(i) for i in range(n * n): print(i)
O(n) + O(n*n) = O(n+n) = O(n + n^2) = O(n^2) //Crecimiento exponencial
def f(n) for i in range(n): for j in range(n): print(i,j)
O(n) O(n) = O(nn) = O(n^2) //Crecimiento exponencial
def fibonacci(n): if n == 0 or n ==1: return 1 return fibonacci(n - 1) + fibonacci(n - 2)
O(2**n) //tiene varias llamadas recursivas y eso hace al algoritmo con un crecimiento exponencial
Gran recopilacion
Hola! Espero que andes bien, cuando tenemos n^2 no es un crecimiento exponencial, es cuadrático, el crecimiento exponencial se da cuando tenemos el valor que ingresamos como exponente, por ejemplo 2^n
Buenas tardes, les informo que en la última diapositiva, la asociada a la serie de Fibonacci, hay un error ya que segun la diapositiva, la función para f(0) es igual a 1, pero según la definición de fibonacci f(0)=0. Saludos!
def fibonacci(n): if n==0: return 0 elif n==1: return 1 else: return fibonacci(n-1)+fibonacci(n-2)
Gracias!
Gracias por compartirlo
gracias
Grande tu aporte.
Nunca había, visto las condiciones de un programa como ecuaciones
Es la mejor manera de ver los programas.
Yo tampoco :o
Y asi es como uno empieza a agarrarle cariño a las matematicas.
Aqui dejo la correción de la ultima diapo :D! f(0) = 0 . Despues de eso todo estaba muy bien explicado :D!! Gracias por la clase
def fibonacci(n): if n==0: return 0 elif n==1: return 1 return fibonacci(n-1) + fibonacci(n-2) if __name__ == "__main__": n=int(input("Elije un numero ( ennésimo: ")) print(fibonacci(n))
Nice
Ley de la suma: crecimiento lineal Ley de la multiplicación: crecimiento cuadrático Recursividad múltiple: crecimiento exponencial
Gracias!
Muchas gracias :)
Les dejo un link con mis apuntes https://github.com/karlbehrensg/poo-y-algoritmos-python
Notación asintótica
Cuando hablamos de notación asintótica no importan las variaciones pequeñas, el enfoque se centra en lo que pasa conforme el tamaño del problema se acerca al infinito.
Siempre tenemos que estar preparados para cualquier caso, por lo que tenemos que saber medir a nuestro algoritmo en el mejor, promedio y peor de los casos.
Lo mejor que nos permite comparar nuestros algoritmos y su capacidad es medir el peor de los casos, ahí es donde entra el Big O notation, donde lo único que importa es el termino de mayor tamaño, sin importar las constantes que las acompañan.
# Ley de la suma def f(n): for i in range(n): print(i) for i in range(n): print(i) # En este caso el mayor término es n # O(n) + O(n) = O(n + n) = O(2n) = O(n)
# Ley de la suma def f(n): for i in range(n): print(i) for i in range(n * n): print(i) # En este caso el mayor término es n² # O(n) + O(n * n) = O(n + n²) = O(n²)
# Ley de la multiplicación def f(n): for i in range(n): for i in range(n): print(i, j) # En este caso el mayor término es n² # O(n) + O(n * n) = O(n * n) = O(n²)
# Recursividad múltiple def fibonacci(n): if n == 0 or n == 1: return 1 return fibonacci(n - 1) + fibonacci(n - 2) # En este caso el mayor término es 2**n (el símbolo ** denota "elevado a"), # ya que realiza recursividad 2 veces por n veces. # O(2**n)
Muy buenos tus apuntes, gracias!
En general si vemos un ciclo dentro de otro, el crecimiento es N**2, pero no lo tomen como regla definitiva. Es decir, si tenemos un código de este estilo , el análisis ya no es tan sencillo
for ( i =n; i >0; i= i/2) for (j =0; i <j; j++) contador ++
El tiempo para este caso es O(N log N) :| La recomendación que hacen los que saben del tema, es que miremos con cuidado cada caso, y no considerar que las reglas sirven siempre. Yo apenas inicio con este tema también.
Bien dicho! hay muchos factores a tomar en cuenta a medida que nuestro código se vuelve más complejo. ahora mismo como lo veo estamos gateando para luego aprender a caminar
¿Se podría deducir el comportamiento tabulando los tiempos de ejecución para distintos valores de n?
¡Saludos! Les comparto esta página sobre complejidad algorítmica hay una gráfica y tablas de resumen. https://www.bigocheatsheet.com/
We all use math every day; to predict weather, to tell time, to handle money. Math is more than formulas or equations; it’s logic, it’s rationality, it’s using your mind to solve the biggest mysteries we know. Competitive Programming 3 page 191
No entendi muy bien esta parte, alguien me lo podrías explicar, por favor. ¿Para que sirve? ¿Para que la utilizaremos en un futuro?¿Que relación tiene con las bases de datos?
La notación asintótica sirve para denotar la complejidad que tienen los algoritmos que creamos, son una característica importante a tener en cuenta a la hora de escoger entre un algoritmo u otro. Imagina que tenemos un algoritmo que pertenece al orden O(n^2) y otro que pertenece al orden O(2*n), a grandes rasgos preferiremos escoger el segundo algoritmo ya que con un gran número de entrada/valores tendremos un mayor rendimiento, piensa en las gráficas definidas por estos ordenes:
Ahora bien, teniendo en cuenta la gran diferencia entre ellos, podemos decir que a futuro nuestro segundo algoritmo es el más indicado, esto lo relacionaremos con las bases de datos en el caso de tener que procesar un gran conjunto de datos antes de insertarlos => El segundo algoritmo nos daría un rendimiento mucho mayor.
Hola Angel
La complejidad permite analizar y comparar de una forma estandar varios algoritmos y así nos permite hacer una selección optima para nuestras necesidades.
La relación con bases de datos por ejemplo sería el espacio de disco duro que va a utilizar cierta estructura de acuerdo a la cantidad de datos que tenemos.
Saludos.
Esto se esta poniendo pesado, me encanta :)
O(n log n)
Este es frecuentemente aplicado en los algoritmos de tipo Divide and Conquer donde el problema se va dividiendo en piezas mas pequeñas, por ejemplo: Quick Sort, Merge Sort, Heap Sort, etc.
var n = 100 for(var i = 0; i < n; i++) {//this loop is executed n times, so O(n) for(var j = n; j > 0; j/=2) {//this loop is executed O(log n) times console.log(n + j); } }
Hola. ¿Por qué el Big O de la función de Fibonacci es 2**n? No me quedó muy claro, gracias.
Buenas compañero, creo que con esta imagen se ve muy bien:
Si te das cuenta cada rama se divide en 2, es decir, el número de ramas se multiplica por dos en cada iteración, por eso es de la forma 2**n.
Haré un intento: La base 2 es debido a que en la función esta se llama recursivamente dos veces así misma. Como ves en la imagen que comparte @Cristian se bifurca dos veces en cada iteracación. Y bueno n es el parámetro de la serie.
¡Éxitos!
Utilizar la formulación matemática para calcular la eficiencia de mis recursos de máquina a la hora de elegir uno u otro algoritmo. Al escalarlo en datos masivos, esto se traduce en tiempo y dinero para mis clientes y/o para mis procesos, lo que se ve reflejado en oportunidades de mercado.
Sí no les quedo muy claro aquí una referencia de Youtube donde queda más clara la Notación Asintótica: Youtube
Gracias
Si Javier esta muy interesante, muchas gracias por la recomendación.
Notación asintótica
👍👍
