Notación asintótica

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

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

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

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

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)

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.

¡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

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

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

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

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

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)

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

Crecimiento Asintotico:

Un loop --> crecimiento lineal.
Loops anidados --> crecimiento polinomial.
Llamadas recursivas --> 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. =)

• En programación el rendimiento o la complejidad de un algoritmo se suele medir utilizando una notación denominada Big-O, y también conocida como Notación Asintótica o Notación Landau (en honor a uno de sus inventores, a principios del siglo pasado, Edmund Landau).

• Ya contado aquí la importancia que tiene aprender a crear ciertos algoritmos aunque no los vayas a usar en el día a día. Pero además, en cualquier documentación o en cualquier libro o página que describa un algoritmo nos vamos a encontrar con la notación Big-O, por lo que es muy importante conocerla. Por ejemplo, si consultamos la documentación de MSDN para la función RemoveAt de una SortedList nos dice qué es una operación O(n):

• O(1): constante. La operación no depende del tamaño de los datos. Es el caso ideal, pero a la vez probablemente el menos frecuente. No se ve en la gráfica de más abajo porque la logarítmica le pasa justo por encima y la tapa.

• O(n): lineal. El tiempo de ejecución es directamente proporcional al tamaño de los datos. Crece en una línea recta.
  O(log n): logarítmica. por regla general se asocia con algoritmos que “trocean” el problema para abordarlo, como por ejemplo una búsqueda binaria.

• O(nlogn): en este caso se trata de funciones similares a las anteriores, pero que rompen el problema en varios trozos por cada elemento, volviendo a recomponer información tras la ejecución de cada “trozo”. Por ejemplo, el algoritmo de búsqueda Quicksort.

• O(n2): cuadrática. Es típico de algoritmos que necesitan realizar una iteración por todos los elementos en cada uno de los elementos a procesar. Por ejemplo el algoritmo de ordenación de burbuja. Si tuviese que hacer la iteración más de una vez serían de complejidad O(n3), O(n4), etc… pero se trata de casos muy raros y poco optimizados.

• O(2n): exponencial. Se trata de funciones que duplican su complejidad con cada elemento añadido al procesamiento. Son algoritmos muy raros pues en condiciones normales no debería ser necesario hacer algo así. Un ejemplo sería, por ejemplo, el cálculo recursivo de la serie de Fibonacci, que es muy poco eficiente (se calcula llamándose a sí misma la función con los dos números anteriores: F(n)=F(n-1)+F(n-2)).

• O(n!); explosión combinatoria. Un algoritmo que siga esta complejidad es un algoritmo totalmente fallido. Una explosión combinatoria se dispara de tal manera que cuando el conjunto crece un poco, lo normal es que se considere computacionalmente inviable. Solo se suele dar en algoritmos que tratan de resolver algo por la mera fuerza bruta. No deberías verlo nunca en un software “real”.

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 )

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.

Apuntes de la clase

3.Notación asintónica o Big O Notation:

.

• Cuando hablamos de variación asintónica no importan las variaciones pequeñas, lo que importan son los datos grandes, es decir, en el infinito los términos como 1000 realmente no hacen ninguna diferencia, así que los descartamos.
• El enfoque de la Big O Notation se centra en lo que pasa conforme el tamaño del problema se acerca al infinito. El termino cuadrático es el verdaderamente relevante conforme nuestro dataset, nuestro imput crece hasta el infinito.
• Nosotros podemos pensar en el mejor de los casos, el promedio, o en el peor de los casos: por ejemplo, si tenemos un algoritmo de búsquedas, muy pocas veces nos vamos a encontrar en escenarios donde encontremos el dato en el primer dato de la lista, también tenemos escenarios donde encontramos el dato a la mitad de la list, pero habrá casos en los que lo encontraremos en los últimos datos de la lista, y esos son los escenarios en los que mejor podremos comparar nuestros algoritmos y entender cual es la complejidad algoritmica, por lo tanto tenemos que pensar en esos escenarios y pensar que nuestro código sea optimo para correr en tales casos, por eso nos centramos en los datos grandes y ahí es cuando entra el Big 0 Notation. Lo que nos lleva a:
• En el Big O Notation nada más importa el termino de mayor tamañó
  
  3.1. Ley de la suma:

  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)

La famosa ley de la suma: O(n + n) = O(2n), pero recordando que NO son los pequeños terminos lo que nos importan ese resultado lo podemos simplificar en: O(n)

Entonces esta función crece de forma lineal porque no hay un crecimiento exponencial.

O(n) se lee foneticamente como “Big O de n” o simplemente “O de n”, y como esta función resultó en O(n) decimos que esta función crece en O de n.

3.2. Ley de la suma con multiplicación de n:

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



    for i in range(n * n):
        print(n)

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


3.3. Ley de la multiplicación:

def f(n):


    for i in range(n):

        for j in range(n):
            print(i, j)

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

la función tiene un crecimiento exponencial, especificamente un crecimiento cuadrático


3.4. Crecimiento exponencial de n con Fibonacci

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

    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

0(2n)

Mira este loop, por cada llamada que hacemos a esta función recursiva, la función se llama a si misma dos veces, así que estamos llamando a dos funciones por cada vez que tenemos n, por lo tanto ahora n se transforma en un exponente 0(2n) se refiere a 0(2^n). (así lo entendí yo)

Este también es un crecimiento exponencial.

Creo que lo que más me inquieta (y me gusta de esta clase) es que refrescas conocimientos que tenías guardados en una parte olvidada del cerebro, al menos en mi caso. Lo que más me emociona es entender como pondremos estos algoritmos en práctica. Y cual es el uso real de los mismos.

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.

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

• 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.

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

Ejemplo:

import random

# Generar una lista grande de números aleatorios
mi_lista_grande = [random.randint(1, 1000) for _ in range(10000)]

# Elemento a buscar
elemento_buscado = 500

# Algoritmo de búsqueda lineal
def busqueda_lineal(lista, elemento):
    for i in range(len(lista)):
        if lista[i] == elemento:
            return i
    return -1

# Algoritmo de búsqueda binaria (se asume que la lista está ordenada)
def busqueda_binaria(lista, elemento):
    izquierda, derecha = 0, len(lista) - 1
    while izquierda <= derecha:
        medio = (izquierda + derecha) // 2
        if lista[medio] == elemento:
            return medio
        elif lista[medio] < elemento:
            izquierda = medio + 1
        else:
            derecha = medio - 1
    return -1

# Medir el tiempo de ejecución del algoritmo de búsqueda lineal
import time
inicio = time.time()
indice_lineal = busqueda_lineal(mi_lista_grande, elemento_buscado)
fin = time.time()
tiempo_lineal = fin - inicio

# Medir el tiempo de ejecución del algoritmo de búsqueda binaria
inicio = time.time()
indice_binario = busqueda_binaria(sorted(mi_lista_grande), elemento_buscado)
fin = time.time()
tiempo_binario = fin - inicio

print("Resultado de la búsqueda lineal:", indice_lineal)
print("Resultado de la búsqueda binaria:", indice_binario)
print("Tiempo de búsqueda lineal:", tiempo_lineal, "segundos")
print("Tiempo de búsqueda binaria:", tiempo_binario, "segundos")

Un loop = crecimiento lineal. . Un loop dentro de otro = crecimiento cuadrático. . Llamadas recursivas = crecimiento exponecncial.

Excelente clase y explicación, sin embargo, a mi me funcionó mucho después de esta clase, ver este vídeo (está en inglés) para poder entender mejor el concepto.

https://www.youtube.com/watch?v=BgLTDT03QtU&t=198s

When we add the time complexities of these two loops together, we get O(n) + O(n) = O(n+n) = O(2n). However, when using Big O notation, we only care about the highest order term and we drop any constants. So, O(2n) simplifies to O(n).

👉 ¡Increíble clase de abstracciones! Hoy aprendimos sobre la notación asintomática y cómo comparar la complejidad de los algoritmos. Identificamos tres tipos de complejidad: lineal, cuadrática y exponencial. Además, vimos cómo la ley de la suma y la ley de la multiplicación pueden ayudarnos a simplificar la complejidad de los algoritmos.

¡No puedo esperar a seguir aprendiendo más sobre esto! ¿Qué les pareció a ustedes?

4. Notación asintótica

Crecimiento asintótico

• 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

# Ley de la suma

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

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

# 0(n) + 0(n) = 0(n + n) = 0(2n) = 0(n)

# Ley de la suma

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

    for i in range(n * n):
        print(i)

# 0(n) + 0(n * n) = 0(n + n^2) = 0(n^2)

# Ley de la multiplicación

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

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

# Recursividad múltiple

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

    return fibonacci(n - 1) + fibonacci(n - 2)

# 0(2^n)

Cuando programamos el rendimiento de nuestro algoritmo es algo importante para que no tarde mucho tiempo en ejecutarse. Hay varios factores que interfieren en el rendimiento de un algoritmo, como lo son: el uso del espacio del disco, memoria para su ejecución, tiempo de ejecución ene general, etc.

Para eso tenemos Big O Notation, nos permite determinar el rendimiento de nuestro algoritmo.

Big O Notation es una herramienta que determina la velocidad o complejidad de un algoritmo, nos dice el número de operaciones que un algoritmo va hacer.

No nos dice la velocidad del algoritmo en segundos, usaremos Big O Notation para comparar algoritmos por el número de operaciones que hacen. Big O Notation nos ayuda a identificar el peor escenario donde el algoritmo llegue a su punto más alto de exigencia.

Los términos Big O más utilizados son:

• O(1): Constante
• O(n): Lineal
• O(log n): Logarítmica
• O(n^2): Cuadrática
• O(2^n): Exponencial

# Ley d ela multiplicacion

def f(n):

    for i in range(n):

        for j in range(n):
            print(i, j)

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

Un gran video que lo explica.

Buena clase 😄.

https://en.wikipedia.org/wiki/Fibonacci_number

Buenas tardes, encontré unos videos donde se explica la complejidad algorítmica que me sirvieron para complementar estas clases.
link:
https://www.youtube.com/watch?v=MaY6FpP0FEU&list=PLh7JzoyIyU4ImojXCZDXcGFWl7pKSX8A3&index=2

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

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