Notación asintótica

Estoy muy metido en el mundo de programacion competitiva, y en este ambito de la programacion es muy, muy importante entender el Big O notation para poder tener soluciones eficientes a los problemas dados.
Aqui les dejo un link de un libro que tiene un poco mas de informacion sobre el Big O notation.
Especificamente esta en el capitulo 2.

Un loop => crecimiento lineal.
Un loop dentro de otro => crecimiento cuadratico
Llamadas recursivas => crecimiento exponecncial.

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

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)

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

Nunca había, visto las condiciones de un programa como ecuaciones

Aqui dejo la correción de la ultima diapo 😄! f(0) = 0 .
Despues de eso todo estaba muy bien explicado 😄!! 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))

Y asi es como uno empieza a agarrarle cariño a las matematicas.

Ley de la suma: crecimiento lineal
Ley de la multiplicación: crecimiento cuadrático
Recursividad múltiple: crecimiento exponencial

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.

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)

¡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

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

Fuente: https://aviada.mx/blog/algoritmos/big-o-notation/

Esto se esta poniendo pesado, me encanta 😃

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.

loop = cremiento lineal
loop adentro de un loop = crecimiento cuadratico
funcion recursiva - genera mas de una llamada recursiva 2 o 3 o 4 = Crecimiento exponencial

En definitiva, se trata de evaluar cómo va a responder el algoritmo en términos universales y considerando siempre todos los casos posibles de uso, para así asegurar que su futura implementación y funcionamiento ocurran acordes a las necesidades y limitaciones inherentes al problema que enfrentamos. Más vale invertir algo más de tiempo en diseñar un buen algoritmo, que hacerlo a la ligera y tener que tirar todo el trabajo de implementación porque al final resulta no ser viable. Evaluad, valorad y entonces y sólo entonces, implementad.

Fibonacci recursivo puede ser se mejorado en su rendimiento a través de programación dinámica. =)

Notación asintótica

• Big O notation
• No importan 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 importan el término de mayor tamaño
  • Ley de la suma (n)
  • Ley multiplicación (n^2)
  • Ley recursiva (a^n)

Este tema me interesa muchisimo:
https://www.amazon.com/Computational-Complexity-Approach-Sanjeev-Arora/dp/0521424267/ref=sr_1_1?ie=UTF8&s=books&qid=1239836395&sr=8-1

Sí no les quedo muy claro aquí una referencia de Youtube donde queda más clara la Notación Asintótica:
Youtube

Crecimiento Asintotico:

Un loop --> crecimiento lineal.
Loops anidados --> crecimiento polinomial.
Llamadas recursivas --> crecimiento exponencial.

Es importante hacer una aclaración con respecto a los ejemplos de tiempo polinomial que se mostraron.Cuando un algoritmo es polinomial respecto al valor de la entrada, es exponencial respecto al tamaño de la entrada.

Usemos primero un ejemplo tradicional, con un algoritmo es_primo que calcula si un número n es primo.

    def isPrime(n):
        if n == 1: return False
        i = 2
        while( i*i <=n ):
            if n % i == 0:
                return False
            i += 1
        return True

Si aplicamos las reglas explicadas en la clase, vemos que los dos primeros pasos son atómicos, y que el while, es de orden lineal, O(n), respecto al valor de n. Ahora, supongamos que con mi algoritmo, yo quiero, calcular, un primo de 300 dígitos. El tamaño de la entrada, es 300. La cantidad de cálculos necesarias, es 2**300. Sigue siendo lineal, respecto al valor de n, pero al tamaño de al entrada no, y esto es lo importante. Comparemos eso, con el caso, de tener un algoritmo, encuenta_en_lista, y que hace una iteración exhaustiva, para encontrar un elemento:

def encuentra_en_lista(l, a_encontrar):
    for x in l:
        if x == a_encontrar:
            return x
    return None

Aquí una vez más, podemos usar las reglas que se explican en la clase, y lo de peso, es el ciclo for, y va determinado por el tamaño de la lista. Si l tiene tamaño 300, para el peor caso, que es que a_encontrar no esté en l, realiza 300 iteraciones. A medida que el tamaño de la entrada crece (y no el valor de esta, sea lo que sea “el valor de una lista”), crecen linealmente la cantidad de cálculos.

Fijémosnos, en el primer caso que se expone en la clase. Se hace un loop, en range(n), donde n, es un número. Nuevamente, si queremos hacer un for, con un número de 300 dígitos, tenemos que hacer 2**300 operaciones. Lo que importa para la máquina, es el tamaño de la entrada, no el valor que esta representa. Comparto ahora el aporte que se hizo en la clase pasada:

Lo que debe estar en el eje de las x, no es el valor de n, sino el tamaño en bits de n, o sea log(n), para que tenga sentido compararlo con otros algoritmos y poder evaluar su rendimiento en la máquina.

Parece una sutileza, pero es importante tener esto presente, incluso, podría no ser un problema, tener un algoritmo exponencial como el del ejemplo, todo depende de nuestra necesidad, y de los números que podríamos necesitar iterar. Baste citar, que en el caso del algoritmo es_primo que muestro, no resulta práctico en casi ninguna situación real.

Les dejo acá, la referencia en Wikipedia de lo que son los algoritmos pseudopolinomiales.

https://en.wikipedia.org/wiki/Pseudo-polynomial_time

Ojalá hagan un curso en donde se hable más a fondo de este tema, en la escuela nunca me quedó claro 😦
Menos cuando los algoritmos tienen crecimientos logarítmicos.

Super excelente, complejo, pero excelente!

Notación asintótica: Notación matemática utilizada para representar la complejidad espacial y temporal cuando n → ∞
Se definen tres tipos de notación:

• Notación O (big-omicron) ⇒ caso peor
• Notación Ω (omega) ⇒ caso mejor
• Notación Θ (big-theta) ⇒ caso promedio

Aqui mi aporte

Notas de la clase 😄
Notación asintótica.

• No importan variaciones pequeñas.
• El enfoque se centra en lo que pasa conforme el tamaño del problema se acerca al infinito.
• Se tiene que tener en cuenta en el mejor de los casos, promedio, y en el peor de los casos. Para medir el algoritmo, consideramos el peor.
• Usando Big O únicamente importa el termino de mayor tamaño, esto es, el que crece más rápido.
• Las complejidades:
  • suman: $O(n) + O(n) = O(2n) = O(n)$
  • multiplica: $O(n)*O(n) = O(n^2)$
• Ejemplo de Fibonacci recursivo va como $O(2^n)$

Algo que no se menciona en la clase explícitamente pero que es muy importante dejarlo en claro, es que existen 4 reglas básicas para el cálculo del big O de una función:
 

1. big O siempre tiene en cuenta el peor de los casos. Si es un loop, se debe considerar que se va a recorrer todo el loop sobre una entrada de tamaño infinito.
2. Eliminar constantes: big O se encarga de la forma en la que crece el número de operaciones, por lo que las constantes como O(2n) o O(n/2 +100) son irrelevantes al aumentar n a números muy grandes.
3. Diferentes términos para diferentes inputs: Si una función tiene diferentes inputs big O de esa función debe considerarse para cada diferente input como diferente término. Entonces si hay dos loops iterando sobre cada uno de los inputs big O sería O(a + b).
4. Eliminar los parámetros no dominantes: Si una función tiene en su big O más de una vez el término principal, por ej. O(n + n^2) entonces los parámetros no dominantes se eliminan. Entonces queda O(n^2). Esto se debe a que el término más dominante va a crecer mucho más rápido que los otros términos.
    

Los otros aspectos a tener en cuenta cuando se está calculando el big O de una función son los que David menciona sobre loops y loops anidados. Hay algunos casos especiales que seguramente se verán en clases posteriores, pero en general se debe tener en cuenta que cada caso se debe estudiar individualmente.

Hacia el infinito las pequeñas variaciones no importan

hay que ver la 2da derivada

Que libro nos ayuda a profundizar en este tema?

Veo que lo importante es observar que tipo de crecimiento con el Big o de manera de identificar si es de carácter, lineal, cuadrático o exponencial de manera entender como se va a desarrollar internamente el algoritmo

Les dejo mis apuntesdel video https://www.youtube.com/watch?v=D6xkbGLQesk:
Big O notation and Time complexity

Let’s suppose a simple algorithm which purpose is the sum of all elements in a given array, the code in Python would be:

´´´
def find_sum(given_array):
total = 0
for i in given_array:
total += I
return total
´´´

Its runtime vs element of array graphic would return a linear time complexity.

Nevertheless, algorithms can acquire different time complexities such as constant or quadratic. There is a better way we can represent these complexities in a more mathematical and general way, this is called Big O Notation. The representation of linear time is O(n) and for quadratic time O(n^2).

The way to obtain the Big O from a Time complexity is:
• Find the fastest growing term
• Take out the coefficient
So let’s suppose that we have the following equations for the Time complexity:
T = an+b = O(n)
T = an^2+bn+c = O(n^2 )

Muy buena clase, ayuda a determinar lo complejo que puede ser un algoritmo, quiero seguir leyendo mas sobre esto

Un loop => crecimiento lineal. Un loop dentro de otro => crecimiento cuadratico Llamadas recursivas => crecimiento exponecncial.

Existen varias notaciones asintóticas que se pueden usar para medir la complejidad de un algoritmo. Algunas más comunes son:

1. Big Oh: Es una notación que nos permite saber una cota superior de la cantidad de operaciones que realiza un algoritmo. Que se define como:
   No alt text provided for this image

Para un f(x) = O(g(x)), entonces∣f(x)∣ ≤ c∣g(x)∣, donde c es una constante mayor a 0, y a partir de un valor de x, que por lo general se escribe como x0.

1. Big Omega: Al igual que Big Oh, este da una cota, pero en este caso una inferior. Se define como:
   No alt text provided for this image

Para un f(x) = Ω(g(x)), entonces ∣f(x)∣ ≥ c∣g(x)∣, para c > 0 y x ≥ x0.

1. Big Theta: Es una notación que nos permite saber una cota inferior y superior del algoritmo. Su definición matemática es:
   No alt text provided for this image

Para un f(x) = Θ(g(x)), entonces f(x) = O(g(x)) y f(x) = Ω(g(x)), para x ≥ x0.

Además de estas, existen muchas más. Algunos ejemplos son:

    Little Oh: Es decir f(x) = o(g(x)) que se define como lim x→∞ g(x)/f(x) = 0.
    Little Omega: Es decir f(x)=ω(g(x)) que se define como lim x→∞ g(x)/f(x) ≠ 0.
    Landau Notation: Esta es una de las más peculiares, que se define como f(x)∼g(x), de manera que, lim x→∞ g(x)/f(x) = 1.

Estas últimas notaciones son poco utilizadas, pero es conveniente saber que existen.

"Nota: No te preocupes demasiado por las matemáticas, estas notaciones están hechas para poder ayudarte a medir la complejidad de tu algoritmo. Es recomendable que sepas que existen y usar las notaciones que más te convengan." 

Hay varias formas de resolver un problema usando un programa de computadora. Por ejemplo, hay varias formas de ordenar elementos en una matriz. Puede utilizar ordenamiento por mezcla , ordenamiento de burbuja , la ordenación por inserción , etc. Todos estos algoritmos tienen sus propias ventajas y desventajas. Se puede pensar en un algoritmo como un procedimiento o fórmula para resolver un problema en particular. La pregunta es, ¿qué algoritmo utilizar para resolver un problema específico cuando existen múltiples soluciones al problema?

El análisis de algoritmos se refiere al análisis de la complejidad de diferentes algoritmos y la búsqueda del algoritmo más eficiente para resolver el problema en cuestión. La notación Big-O es una medida estadística que se utiliza para describir la complejidad del algoritmo.

Notación asintótica.
No importan variaciones pequeñas.
El enfoque se centra en lo que pasa conforme el tamaño del problema se acerca al infinito.
Se tiene que tener en cuenta en el mejor de los casos, promedio, y en el peor de los casos. Para medir el algoritmo, consideramos el peor.
Usando Big O únicamente importa el termino de mayor tamaño, esto es, el que crece más rápido.
Las complejidades:
suman: $O(n) + O(n) = O(2n) = O(n)$
multiplica: $O(n)*O(n) = O(n^2)$

**Crecimiento asintótico: **El crecimiento cuando se acerca al infinito. Cuando se acerca al infinito los valores pequeños o constantes no importan. El enfoque se centra en lo que pasa conforme el tamaño del problema se acerca al infinito.

Las notaciones asintóticas son lenguajes que nos permitan analizar el tiempo de ejecución de un algoritmo identificando su comportamiento si el tamaño de entrada para el algoritmo aumenta. Esto también se conoce como la tasa de crecimiento de un algoritmo.

fibonacci recursibo

• No importan 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.
• Big O
• Solo importa el término de mayor tamaño.

# Ley de la suma

def f(n):
		for i in  range(n): # n pasos
				print(i)

		for i in range(n): # n pasos
				print(i)

# O(n) + O(n) = O(n+n) = O(2n) = O(n) se quita el 2 porque no importan los terminos especificos
# esta funcion crece con respecto a n de manera lineal

# Ley de la suma

def f(n):
		for i in  range(n): # n pasos
				print(i)

		for i in range(n * n): # n*n = n^2 pasos
				print(i)

# O(n) + O(n^2) = O(n + n^2) = O(n^2) solo interesa el termino mas grande (n^2)
# crece de manera cuadratica

# Ley de la multiplicación

def f(n):
		for i in range(n): 	
				for j in range(n):
						print(i, j)
# hay un loop adentro de otro, a diferencia del anterior donde estaban al mismo nivel
# por lo tanto se multiplica para saber el número de pasos

# O(n) * O(n) = O(n * n) = O(n^2)

Si hay un loop, probablemente sea de crecimiento lineal, si hay un loop dentro de otro loop probablemente sea de cuadrática.

# Recursividad multiple

def fibonacci(n): 
		if n == 0 or n == 1:
				return 1

		return fibonacci(n-1) + fibonacci(n-2)
# por cada llamada de fibonacci, se generan 2 llamadas mas
# conforme crezca n se llaman más y más funciones

# O(2^n)
# crecimiento exponencial
# si se hicieran 4 llamadas dentro de la funcion seria O(4^n) etc

Si tenemos una función recursiva que genera dos o más llamadas recursivas probablemente tenga un crecimiento exponencial.

Cuando tenemos casos recursivos, podemos observar que en caso de que cada llamada a la función, se llame dos veces a ella misma. Tenemos que: 2**n, debido a que estamos incrementando exponencialmente nuestras llamadas en dos cada vez.

Cuando tenemos casos recursivos, podemos observar que en caso de que cada llamada a la función, se llame dos veces a ella misma. Tenemos que: 2**n, debido a que estamos incrementando exponencialmente nuestras llamadas en dos cada vez.

Cuando tenemos una iteración dentro de otra, podemos decir que tenemos una potenciación.

Para nuestro Big O, solo necesitamos el término más grande. Eliminando todos los coeficientes más pequeños. Por lo que dentro de nuestras funciones, solo queda uno o dos.

Lo que importa en la complejidad algorítmica, no es la exactitud de las expresiones, sino su comportamiento.

La forma de expresarlo, podría ser: La función crece en O de n.

La O(n) crece con respecto a n de manera lineal, debido que da lo que recibe.

Puedes saber cómo se estima tu algoritmo, entendiendo, cuáles son los pasos que se siguen. Cómo por ejemplo, que en un loop, se multipliquen o se sumen x veces las variables, hace que tengamos algo como un O(n), si tenemos dos de estos loops, entonces sería algo como: O(n) + O(n) = O(n+n) = O(2n), que a la final nos puede dar O(n)

El peor de los casos, siempre será el caso al que debemos prestar atención. Para poder comparar efectivamente la complejidad.

No necesitamos nada más que el Big O, o la notación mayor, para determinar el rendimiento. Sin embargo, para el promedio se tienen medidas como el Big O omega.

Dentro del big O notation, tenemos: Mejor de los casos, promedio, peor de los casos.

No importan las variaciones pequeñsa en el asintotismo. Es por que ello, que nuestro modelo se enfoca justamente, en dónde se encuentra el crecimiento. Un crecimiento teorícamente al infinito.

El big O notation, nos permite tener un estimado, bien concreto,sin término que no importen a la larga.

La notación asintótica también es llamado,big O notation.

La notación asintótica nos permite representar la complejidad, y por ende la eficiencia, de un algoritmo, de tal manera que podemos proyectar el aumento de operaciones requeridas al aumentar el tamaño de la entrada (input).
Desde este punto de vista, el algoritmo más eficiente posible sería aquel en el que el número de operaciones llevadas a cabo no varíe según crezca la entrada. Esto es lo que sería una función constante.

Para los que quedaron con dudas
😃
Espero ayudarlos

En el caso del procesamiento de imágenes el número de operaciones es muy importante, imaginen que tenemos una imagen con una resolución de 1 megapixel = 1 millón de pixeles (algo bajo para las caracteíisticas actuales), si le hacemos 10 operaciones a la imagen, se convierten rapidamente en 10 millones de operaciones en total. Por eso hay que pensar en algoritmos eficientes con menor cantidad de operaciones, menor uso de recursos y mejores resultados.

**Crecimiento asintótico: **El crecimiento cuando se acerca al infinito. Cuando se acerca al infinito los valores pequeños o constantes no importan.

• El enfoque se centra en lo que pasa conforme el tamaño del problema se acerca al infinito.
• Se puede pensar en el mejor de los casos, en el promedio de casos, o en el peor de los casos. Se debe poder medir el algoritmo para ver que pasa en el peor de los casos. El mejor de los casos es difícil de saber.
• Big o.
• Solamente importa el término de mayor tamaño.
• Identificar si el crecimiento es lineal o cuadrático o mayor.

En este tema vimos lo siguiente:

• ¿En qué consiste el crecimiento asintótico?
• ¿Cuáles son algunos escenarios en la identificación de las leyes?

Me esta gustando demasiado este modulo

• No importan 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
• Big O
• Nada más importa el término de mayor tamaño

Se usa para poder analizar de manera muy descriptiva la eficiencia de un algoritmo. Teniendo en cuenta dos ideas.

• Dependiendo del tamaño de la entrada que recibe la función de nuestro algoritmo, el tiempo de ejecución va a variar.
• Enfocarnos en la tasa de crecimiento del tiempo de ejecución, es decir, en cuanto aumenta el tiempo para completar la función del algoritmo.

Recomiendo los siguientes links para profundizar aún más sobre el tema y sobre el Big O notation:

• Notación Asintótica
• Big O Notation

Esto se explica muy bien en el libro Cracking The Coding Interview, en donde hay un capítulo dedicado a Big O, usado para describir la eficiencia de los algoritmos.

Recomiendo este libro para practicar Big O notation: http://www.crackingthecodinginterview.com/

Landau Viendo como le llamas Big O a su notación.

Me encanta cuando la clase te hace investigar por fuera de la clase en sí. Este fue el caso. Investigar Big O Notation, por fuera de la clase, fue una clase aparte. Muchas gracias David por despertar la inquietud intelectual.

me encanta

puede q haya funciones que el num se haga mas grande sea mas facil?

Antes no media el rendimiento de mis algoritmos por que pensaba que no hacia falta, pero ahora cada vez que tenga la oportunidad lo voy a hacer.

Ahora agarra sentido las matimáticas de la Universidad (que enseñaro de forma caótica por cierto)

Ley de la multiplicacion

#Un loop dentro de otro loop se multiplican

def f(n):
	for i in range(n): #n pasos
		for j in range(n): #n pasos
		print(i, j)

#O(n) * O(n) = O(n * n) = O(n**2), la funcion crece en O de n**2
#Esta funcion es cuadratica

Son matemáticas aplicadas, big O es el límite cuando n tiende a infinito

bernardino rivadavi

Cuando es un algoritmo de varias lineas ( unas cientas) como se hace?

Creo haber entendido bien, se toman los valores mas relevantes.

entonces entiendo que cuando aparentemente la recursividad sea la solución … hay que hacer la aritmética correspondiente siempre.

Lo que intentamos determinar es que tipo de función es, descartando sus movimientos (arriba, abajo, derecha o izquierda) y aun mas descartando si esta se expande o se contrae tanto en x como en y, la simplificamos para saber como es su forma original

una aproximación

Este tema es muy complicado de que lo expliquen en las universidades. Es más,por lo mismo, ningún profesor lo explica.

Aroesti nunca decepciona. 😄

Interesante!!

ahora entiendo para que sirve la teoría de limites en introducción al calculo diferencial e integral… muy interesante ya que al ser una función asintotica por más que se acerque al eje de tendencia nunca lo cruzará y por ello el problema puede ir hasta infinito consumiendo grandes recursos.

La función crece en O de n o también la función es de “orden n”, “orden n^2”, etc

Lo importante de tomar el peor de los casos, es que ya tendremos en cuenta que nos puede sucede pero estos pueden ser menores a los presupuestados, dandonos una buena visión de lo que estamos por hacer con nuestras funciones.

Vengo de la clase de ordenamiento de burbuja y ahora si ya le agarre el royo a la notación asintótica 😃

Para el Big O, siempre se tomará en cuenta el termino con el crecimiento más rápido. Por eso cuando se tiene una suma de polinomios, solo se considera el de mayor grado. Se desprecia el termino constante que lo multiplica, si lo hay, dado que por lo mismo, solo importa el grado (exponente).

No solo hay crecimientos polinomiales, sino tambien exponenciales, logaritmicos, factoriales, constantes, infinitos, entre otros. La regla es la misma, siempre se debe tomar el termino de mayor crecimiento.

Yo soy auxiliar de calculo en la facultad de economía, pero jamas pensé usar todo lo que se para la programación, sencillamente me queda como anillo al dedo.

Marcador: Ley de la suma #2

Marcador: Ley de la suma #2

Marcador: Ley de la multiplicación

Marcador: Recursividad múltiple

Marcador: Ley de la suma

Jjajaj a recordar algebra mas que todo factorización, interesante tema para determinar la complejidad de nuestro algoritmos.

Marcador: slide

Para el Big O, siempre se tomará en cuenta el termino con el crecimiento más rápido. En un polinomio el de mayor exponente.
Constante: no crecimiento
Un loop: crecimiento lineal (Ley de la suma (n))
Un loop anidado en un loop: crecimiento polinomial: cuadratico, cúbico … (Ley multiplicación (n^a))
Llamadas recursivas: crecimiento exponencial. (Ley recursiva (a^n))

A profundizar en las matemáticas!

Muy interesante.