"""
Created on Sun May 10 19:49:22 2020
@author: xavik
"""
# -*- coding: utf-8 -*-
import math
import time
class Complejidad_algoritmica:
def __init__(self, n):
self.n = n
def constante(self):
return 1
def logaritmica(self):
return math.log10(self.n)
def lineal(self):
return self.n
def log_lineal(self):
return self.n * math.log10(self.n)
def polinomial(self):
return self.n**2
def exponencial(self):
return 2**self.n
def main():
nums = [1, 10, 100, 1000, 10000]
for n in nums:
complejidad = Complejidad_algoritmica(n)
print('n es igual a: {}'.format(n))
principio = time.time()
print(f'El resultado de complejidad constante para n igual a {n} es: ', complejidad.constante())
fin = time.time()
tiempo = fin - principio
print(f'has tardado {tiempo} segundos\n')
principio = time.time()
print(f'El resultado de complejidad logaritmica para n igual a {n} es: ', complejidad.logaritmica())
fin = time.time()
tiempo = fin - principio
print(f'has tardado {tiempo} segundos\n')
principio = time.time()
print(f'El resultado de complejidad lineal para n igual a {n} es: ', complejidad.lineal())
fin = time.time()
tiempo = fin - principio
print(f'has tardado {tiempo} segundos\n')
principio = time.time()
print(f'El resultado de complejidad logaritmica lineal para n igual a {n} es: ', complejidad.log_lineal())
fin = time.time()
tiempo = fin - principio
print(f'has tardado {tiempo} segundos\n')
principio = time.time()
print(f'El resultado de complejidad polinomial para n igual a {n} es: ', complejidad.polinomial())
fin = time.time()
tiempo = fin - principio
print(f'has tardado {tiempo} segundos\n')
principio = time.time()
print(f'El resultado de complejidad exponencial para n igual a {n} es: ', complejidad.exponencial())
fin = time.time()
tiempo = fin - principio
print(f'has tardado {tiempo} segundos\n')
print('\n\n')
if __name__ == '__main__':
main()```
Complejidad algorítmica
¿Ya tomaste el Curso de Pensamiento Computacional?
Introducción a la complejidad algorítmica
Abstracción
Notación asintótica
Clases de complejidad algorítmica
Algoritmos de búsqueda y ordenación
Búsqueda lineal
Búsqueda binaria
Ordenamiento de burbuja
Ordenamiento por inserción
Ordenamiento por mezcla
Ambientes virtuales
Ambientes virtuales
Graficado
¿Por qué graficar?
Graficado simple
Algoritmos de optimización
Introducción a la optimización
El problema del morral
Conclusiones
No tienes acceso a esta clase
¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera
Si ya tienes una cuenta,
Clases de complejidad algorítmica
5/16Recursos
¿Qué es la complejidad algorítmica?
La complejidad algorítmica es fundamental para evaluar la eficiencia de un algoritmo. Comprender su comportamiento no solo optimiza el uso de recursos, sino que también mejora nuestra capacidad para comparar y elegir el mejor enfoque ante un problema. A través de las distintas categorías de complejidad, es posible anticipar el rendimiento y escalabilidad de un algoritmo. Veamos cada una de estas categorías y sus características principales.
¿Qué caracteriza a la complejidad constante, O(1)?
La complejidad constante implica que el tiempo de ejecución de un algoritmo no cambia, independientemente del tamaño del input. Un ejemplo es una función que retorna un valor sin importar el input recibido:
def constante():
return 1
Este tipo de algoritmo es ideal, ya que su eficiencia no se ve afectada por el incremento del tamaño del input.
¿Cuándo se presenta la complejidad lineal, O(n)?
La complejidad lineal ocurre cuando el tiempo de ejecución crece proporcionalmente al tamaño del input. Por ejemplo, recorrer una lista de n elementos para encontrar un valor es un proceso lineal, ya que el tiempo aumenta con el número de elementos a revisar.
def busqueda_lineal(lista, objetivo):
for elemento in lista:
if elemento == objetivo:
return True
return False
Este tipo de algoritmo es eficiente en datasets pequeños, pero puede no ser práctico a escala muy grande.
¿Qué es la complejidad logarítmica, O(log n)?
Un algoritmo con complejidad logarítmica se convierte en eficiente ante grandes volúmenes de datos. A medida que el input crece, el tiempo de ejecución aumenta mucho más lento. Un ejemplo es la búsqueda binaria:
def busqueda_binaria(lista, objetivo):
inicio = 0
final = len(lista) - 1
while inicio <= final:
medio = (inicio + final) // 2
if lista[medio] == objetivo:
return True
elif lista[medio] < objetivo:
inicio = medio + 1
else:
final = medio - 1
return False
Este tipo de algoritmo es esencial para ejemplos como bases de datos que requieren alta escalabilidad.
¿En qué casos encontramos la complejidad lineal logarítmica, O(n log n)?
La complejidad O(n log n) es común en algoritmos de ordenamiento eficientes como el Merge Sort. Este tipo de algoritmos suelen dividir el problema en más pequeños, resolverlos (log n) y combinarlos (n).
def merge_sort(lista):
if len(lista) <= 1:
return lista
medio = len(lista) // 2
izquierda = merge_sort(lista[:medio])
derecha = merge_sort(lista[medio:])
return merge(izquierda, derecha)
def merge(izquierda, derecha):
resultado = []
i = j = 0
while i < len(izquierda) and j < len(derecha):
if izquierda[i] < derecha[j]:
resultado.append(izquierda[i])
i += 1
else:
resultado.append(derecha[j])
j += 1
resultado.extend(izquierda[i:])
resultado.extend(derecha[j:])
return resultado
Aunque no es tan eficiente como los algoritmos logarítmicos, brinda una buena combinación de eficiencia y cobertura de casos complejos.
¿Qué sucede con la complejidad cuadrática y exponencial?
Los algoritmos con complejidad cuadrática O(n²) y exponencial O(2ⁿ) presentan desafíos significativos: un incremento en el input se traduce en un crecimiento dramático del tiempo de ejecución. Utilizarlos en situaciones de datos vastos puede ser impráctico. Un ejemplo clásico son los algoritmos de fuerza bruta para resolver problemas como el de la mochila o el de Hamilton.
Con tanta diversidad, entender la complejidad algorítmica es crucial para elegir la estrategia adecuada. Investigar, compartir y experimentar con distintas soluciones no solo mejora el código, sino que ofrece herramientas valiosas para enfrentar desafíos computacionales eficientes y efectivos. ¡Atrévete a explorar y seguir aprendiendo en el emocionante mundo de los algoritmos!
Aportes 172
Preguntas 15
Ordenar por:
Acá el código y resultado del reto. 😮
import math
def num(n):
return 1
def logarithm(n):
return math.log10(n)
def lineal(n):
return n
def n_logarithm(n):
return n * math.log10(n)
def square(n):
return n**2
def exponential(n):
return 2**n
if __name__ == "__main__":
n = [10, 100, 1000, 1000000]
i = 0
for numbers in n:
print(num(n[i]))
print(logarithm(n[i]))
print(lineal(n[i]))
print(n_logarithm(n[i]))
print(square(n[i]))
print(exponential(n[i]))
print('\n')
i+=1
Ahí está solo el principio de 2^100000 D:
Wow
Clases de complejidad algorítmica:
- O(1) - Acceder a un elemento de una hash table o a un elemento de arreglo cuando conoces el indice
- O(n) - Buscar un elemento en un arreglo de tamaño n cuando no está arreglado y no se conoce el indice
- O(log n) - Búsqueda binaria o inserción en un árbol binario
- O(n log n) - Algunas funciones de ordenamiento como merge sort o quick sort
- O(n**2) - Algoritmos que recorran un arreglo y tengan que comparar un elemento con el resto para cumplir un objetivo. La mayoría de los problemas resultos con “fureza bruta” tienen una complejidad cuadrática o con algún exponente.
- O(2**n) - Fibonacci recursivo
O(1)
CONSTANTE
No crece, se mantiene igual hasta el infinito
O(n) Lineal (Proporcional al input) BUENO
Recorremos todas las posibilidades,
hasta encontrar lo que buscamos
NO ES MALO
O(log n)
Logarítmica ¿EL MEJOR?
(Google lo usa, la búsqueda binaria, es este tipo de algoritmo)
Crece de manera logarítmica al input,
cada vez crece menos, hacia el infinito…
O(n log n)
log lineal (Merge Sort)
Una parte crece de manera logarítmica al input
(se divide y divide, se vuelve mas chica y mas chica)
y la otra es CONSTANTE
O(n^2)
Polinomial
NO SE PUEDE UTILIZAR
Excepto que el input sea chico
Porque CRECE MUY RAPIDO
O(2^n)
Exponencial
A LA VERGA
Ok, el número es muchísimo más grande de lo que pensaba. Python hiso la operación extremadamente rápido, en aproximadamente 1 segundo, pero cuando empecé a seleccionarlo para copiarlo nunca terminé JAJAJAJA ¡¡ES GIGANTEEE!!
Hace poco leí en un comentario que era una mala práctica anidar un for dentro de otro for, en esta clase entiendo que es porque entra dentro de la categoría polinomial, sería O(n**2).
¿Es correcto?
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”.
Con esta lectura podran comprender mejor el O(log n) con la busqueda binaria como ejemplo:
https://uniwebsidad.com/libros/algoritmos-python/capitulo-8/busqueda-binaria
Espero no ser el único que le haya causado gracia la frase: y los exponenciales… esos si ya tiralos a la basura 😃
Clases de complejidad algorítmica
O(1): Constante
O(n): Lineal
O(log n): Logarítmica
O(n log n): log lineal
O(n2): Polinomial
O(2 ** n) : Exponencia
2^1000000 Es un numerito de 301030 digitos que no seria bonito ponerlo aqui.
Ojala que la funcion exponencial sea la que represente al crecimiento salarial de los programadores xD
Esta es una pedazo de clase donde entiendes todo, muchas gracias profee, cuando se hace bien también se dice
…jugando con un valor de 1000000 VSCode murió al calcular el exponencial 😄
import math
def O_constant(n):
return 1
def O_log_n(n):
return math.log(n)
def O_lineal(n):
return n
def O_lineal_log_n(n):
return n * math.log(n)
def O_polynomial(n):
return n**2
def O_exponencial(n):
return 2**n
values = [10, 100, 1000]
for v in values:
print(f'With {v}')
print(f'Constant: {O_constant(v)}')
print(f'Log n: {O_log_n(v)}')
print(f'Lineal: {O_lineal(v)}')
print(f'n log n: {O_lineal_log_n(v)}')
print(f'Polynomial: {O_polynomial(v)}')
print(f'Exponencial: {O_exponencial(v)}')
print(f'---------------------------------')
Esta es de las clases que más me han gustado, ahora les dejo por aquí una página con ejercicios en código no es de python pero lo importante es aplicar las herramientas conceptuales y aparte también dejo una pequeña lectura:
Ejercicios de Big-O
Lectura con ejemplos de diferentes algoritmos con Big-O
Aparte quien lo hubiera dicho, la búsqueda binaria es un O(log n), es fascinante. 😄
Algoritmos según su complejidad algorítmica:
O(1) = Calcular (−1)^n
O(n) = Tiempo de amortizacion usando un dijoint set
O(log n) = Búsqueda binaria
O(n log n) = Transformada de fourier
O(n2) = Convolución directa, ordenamiento burbuja
O(2n) = “Solving matrix chain multiplication via brute-force search” según wikipedia
Como curiosidad el nombre de Big O notation hace referencia a el Orden de una función que es en grandes rasgos que tanto crece la función.
A quien le interese, esta es la base de la optimizacion inteligente (una de las ramas de la inteligencia artifical).
Para diversos problemas de optimización no existe un algoritmo que los pueda resolver en tiempo polinomial. Estos problemas incluyen encontrar la ruta de menor costo entro los nodos de un grafo, encontrar la mejor manera de acomodar objetos en un contenedor, encontrar la calendarización de menor costo de una serie de tareas, etc.
A estos problemas se les clasifica como NP mientras que a los que si pueden resolverse de manera exacta en un tiempo polinomial se les conoce como P.
La optimización inteligente es la rama de la inteligencia que ha propuesto algoritmos inteligentes, llamados heuristicas, para aproximarse lo mas posible a la solución exacta de los problemas NP dentro de un tiempo polinomial. Algunos de estos algoritmos son los algoritmos genéticos (GA), recocido simulado (SA), optimizacion por colonia de hormigas (ACO), entre otros. Al dia de hoy se siguen proponiendo heuristicas nuevas y se sigue investigando cuales heuristicas son mejores para ciertos problemas.
Video Complementario:
https://www.youtube.com/watch?v=HEISXs0wYlM&t=497s
Ejemplos de código simple de varias categorías de Big O:
O(1) – Ejemplo de tiempo constante:
Este algoritmo imprime hola una vez y no depende de n, por lo que siempre se ejecutará en tiempo constante, por lo que es O(1) .
print “hello”;
O(log (n)) – Ejemplo logarítmico:
Esto actúa como “log_2”
Muestra un algoritmo que se ejecuta en log_2 (n). Observe que la operación de publicación del ciclo for múltiplos el valor actual de i por 2, por lo que va de 1 a 2 a 4 a 8 a 16 a 32 …
for(int i = 1; i <= n; i = i * 2) print “hello”;
O(n) - Ejemplo de tiempo lineal:
Este algoritmo es simple, que se imprime hola n veces.
for(int i = 0; i < n; i++) print “hello”;
O(n ^ 2) - n al cuadrado Ejemplo:
O(n^2) se obtiene fácilmente al anidar bucles estándar.
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) print “hello”;
O(n * log (n)) - Ejemplo:
Piense en esto como una combinación de O(log(n)) y O(n) . La anidación de los bucles for nos ayuda a obtener el O(n*log(n))
for(int i = 0; i < n; i++) for(int j = 1; j < n; j = j * 2) print “hello”;
Clases de complejidad algorítmica
O(1): Constante
O(n): Lineal
O(log n): Logarítmica
O(n log n): log lineal
O(n2): Polinomial
O(2 ** n) : Exponencia
>>> n = 2**1000000
>>> print(len(str(n)))
301030``` es muy largo
Este tipo de análisis nos permite optimizar, los programas que estamos desarrollando, He visto muchos casos, en los que un programa para generar un reporte, puede hacer que se trabe una operación completa. Porque pudiera generarse un crecimiento lineal de la complejidad.
Big O
-Métrica para eficiencia de un algoritmo
-Hoy en día se revisa que tan bueno es
-Se evalúa que el algoritmo sea eficiente y utilice optima mente los recursos
-Recordemos que gran parte del código se almacena en la nube, en la cual nos cobran dependiendo de los recursos que utilicemos.
Reto:
class Complejidad():
def __init__(self, n):
self.n = n
def Constante(self, n):
#print ('Hola mundo')
return 1
def Lineal(self, n):
return n
def Logaritmica(self, n):
return math.log10(n)
def nLogaritmoN(self, n):
return n * math.log10(n)
def Polinomial(self, n):
return n**2
def exponencial(self, n):
return 2**n
def main():
n = 1000000
complejidad = Complejidad(n)
print('El tiempo de complejidad constante es: ', complejidad.Constante(n))
print('El tiempo de complejidad lineal es: ', complejidad.Lineal(n))
print('El tiempo de complejidad Logaritmica es: ', complejidad.Logaritmica(n))
print('El tiempo de complejidad n logaritmo n es: ', complejidad.nLogaritmoN(n))
print('El tiempo de complejidad polinomial es: ', complejidad.Polinomial(n))
print('El tiempo de complejidad exponencial es: ', complejidad.exponencial(n))
if __name__ == '__main__':
main()
<# -*- coding: utf-8 -*-
import math
class Complejidad_algoritmica:
def __init__(self, n):
self.n = n
def constante(self):
return 1
def logaritmica(self):
return math.log10(self.n)
def lineal(self):
return self.n
def log_lineal(self):
return self.n * math.log10(self.n)
def polinomial(self):
return self.n**2
def exponencial(self):
return 2**self.n
def run():
#n = 10, 100, 1000 , 1000000
n = int(input("Introduce el valor de n: "))
bigO = Complejidad_algoritmica(n)
print("El tiempo de complejidad constante es:", bigO.constante())
print("El tiempo de complejidad logaritmica es:", bigO.logaritmica())
print("El tiempo de complejidad lineal es:", bigO.lineal())
print("El tiempo de complejidad log lineal es:", bigO.log_lineal())
print("El tiempo de complejidad polinomial es:", bigO.polinomial())
print("El tiempo de complejidad exponencial es:", bigO.exponencial())>
no es lo mismo n2 2n
si quiero que me den n plata voy a queer 2*n
LOGARITMO
A este tipo de algoritmos pertenece Busqueda Binaria
LINEAL
A este tipo de algoritmos pertenece Busqueda Lineal
Clases de complejidad algorítmica
- O(1) Constante
- O(n) Lineal
- O(log n) Logarítmica
- O (n log n) log lineal
- O (n**2) Polinomial
- O (2**n) Exponencial
➡️Página que te ayuda a visualizar la complejidad algorítmica: https://www.bigocheatsheet.com/
También muestra qué tipo de complejidad tienen las estructuras de datos y los algoritmos de ordenacinamiento.
****algunos ejemplos ****
- O(1) - Constante: No importa cuanto crezca el input, el algoritmo va a tardar el mismo tiempo.
- O(n) - Lineal: El crecimiento es de forma proporcional al crecimiento del input.
- O(log n) - Logarítmica: La función va a crecer de manera logarítmica respecto al input, al principio mucho y después se va a estabilizar y a crecer poco a poco.
- O(n log n) - log lineal: Significa que va a crecer de manera logarítmica pero también con una constante.
- O(n^2) - Polinomial: La base crece conforme crece el input.
- O(2^n) - Exponencial: El exponente crece conforme crece el input.
Les dejo un link a un video para profundizar este tema https://www.youtube.com/watch?v=MyAiCtuhiqQ&ab_channel=ChioCode
Mi ejercicio:
import numpy as np
import pandas as pd
import math
import time
class BigO_pruebas:
def __init__(self, numero):
self.numero = numero
def constante(self):
return (1)
def lineal(self):
return (2 * self.numero)
def logaritmica(self):
return (np.log(self.numero))
def loglineal(self):
return (self.numero * np.log(self.numero))
def polinomial(self):
return (self.numero ^ 2)
def exponencial(self):
return (2 ^ self.numero)
def factorial(self):
return (math.factorial(self.numero))
Pruebas_complejidad = BigO_pruebas(numero=100000)
inicio = time.time()
Pruebas_complejidad.factorial()
final = time.time()
registro = final - inicio
print(registro)
Muy interesante saber que existe todo un estudio acerca de la implementación y superioridad de un algoritmo. Muy buena esta clase.
Les comparto el código de una calculadora para estas operaciones:
"""
Created 28-January-2021
by lucasezequiel05
"""
"""
+Se importan time para la toma de tiempos de la operación
+Se importa math para realizar las operaciones logarítmicas.
+El programa solicita el ingreso de un número y una opción,
mostrando por pantalla resultado y el tiempo utilizado.
"""
import time
import math
class Calculadora:
def __init__(self):
pass
def logarithm(self,n):
return math.log10(n)
def lineal(self,n):
return n
def n_logarithm(self,n):
return n * math.log10(n)
def square(self,n):
return n**2
def exponential(self,n):
return 2**n
if __name__ == "__main__":
#Crea instancia
calculadora_math = Calculadora()
#Se ingresan los valores convirtiendolos a enteros.
number = int(input("Enter a number:\n"))
print(f'You have entered: {number}\n')
print("Select a operation (indicate the number):\n 1)lineal\n 2)logarithm\n 3)n_logarithm\n 4)square\n 5)exponential\n")
option = int(input("\n"))
#El bloque compara la opción correcta, toma los tiempos y muestra resultados.
if option == 1:
time_start = time.time()
result = calculadora_math.lineal(number)
time_end = time.time()
print(f'Result = {result}\n Tiempo de la operación: {time_end-time_start}')
elif option == 2:
time_start = time.time()
result = calculadora_math.logarithm(number)
time_end = time.time()
print(f'Result = {result}\n Tiempo de la operación: {time_end-time_start}')
elif option == 3:
time_start = time.time()
result = calculadora_math.n_logarithm(number)
time_end = time.time()
print(f'Result = {result}\n Tiempo de la operación: {time_end-time_start}')
elif option == 4:
time_start = time.time()
result = calculadora_math.square(number)
time_end = time.time()
print(f'Result = {result}\n Tiempo de la operación: {time_end-time_start}')
elif option == 5:
time_start = time.time()
result = calculadora_math.exponential(number)
time_end = time.time()
print(f'Result = {result}\n Tiempo de la operación: {time_end-time_start}')
else:
print("Invalid option")
De curioso me puse a encontrar 2^1000000000000. Primero intenté haciendo esto
import math
math.pow(2, 1000000000000)
Pero obtuve una excepción OverflowError: math range error.
Por lo que seguí buscando y encontré mpmath. Este paquete básicamente se concentra en precisión de números de punto flotante. Luego, abrí un google colaboratory e hice lo siguiente:
from mpmath import mp
ans = mp.power(2, 1000000000000)
print(ans)
y la respuesta fue:
9.57624423149274e+301029995663
Nótese que está elevado a la 301029995663 (¡¡Son demasiados ceros!!).
La documentación de power la pueden encontrar acá: https://mpmath.org/doc/current/functions/powers.html#power
Clases de Complejidad Algorítmica
- Constante O(1) → no depende del tamaño del input, siempre tardará lo mismo
- Logarítmica O(log(n)) → crecen rápido al inicio pero después se estabilizan, crecen muy poco con inputs grandes
- Lineal O(n) → Crecen de manera proporcional a tamaño del input
- Log lineal O(nlog(n)) → Crecen ligeramente más rápido que la complejidad lineal
- Polinomial O(n**a) → Crecen muy rápido y más a medida que a sea mayor.
- Exponencial O(a**2) → Crecen muy muy rápido, mientras mas grande el input más rápido crecen
- Factorial O(n!) → Crecen de manera similar a la complejidad exponencial
Nota:
- Las complejidades están ordenadas de manera creciente de mas eficiente a menos eficiente.
- Los algoritmos complejos cumplirán su función para números pequeños (no siempre trabajamos con Megadata)
Para aquellos que quieran ver la complejidad temporal y espacial de algunas estructuras de datos y algoritmos de ordenamiento. en la página de Big O Cheat Sheet podrán encontrar todo lo mencionado.
En el libro que dejo un compañero sobre programación competitiva https://cses.fi/book/book.pdf.
Dan ejemplos de los usos de la complejidad algorítmica.
<h2> Eficacia del agoritmo <h2>
nos habla de cuanto debe de ser el támano de imput máximo para cada caso.
Por ejemplo si el támano del archivo es 10^5 dedemos de optar por los del tipo n(log(n)), n, 1 o log (n).
Tambien deja algunos ejemplos de algoritmos de ciertas clases
O(n) Lineal: la complejidad crecerá de forma proporcional a medida que crezca el input.
O(log n) Logarítmica: nuestra función crecerá de forma logarítmica con respecto al input. Esto significa que en un inicio crecerá rápido, pero luego se estabilizara.
O(n log n) Log lineal: crecerá de forma logarítmica pero junto con una constante.
O(n²) Polinomial: crecen de forma cuadrática. No son recomendables a menos que el input de datos en pequeño.
O(2^n) Exponencial: crecerá de forma exponencial, por lo que la carga es muy alta. Para nada recomendable en ningún caso, solo para análisis conceptual.
Notas de la clase 😄
Clases de complejidad algorítmica.
- $O(1)$ constante, el algoritmo se trata el mismo tiempo sin importar cual sea el input.
- $O(n)$ lineal, por lo que el tiempo crece proporcionalmente al input.
- $O(\log n)$ logarítmica, crece siempre, pero si crecimiento decrece con el tamaño del input.
- $O(n \log n)$ log lineal.
- $O(n^2)$ polinomial.
- $O(2^n)$ exponencial (esta es la peor, salga de ahí compa 😆).
Muy bueno saber esto, cambia mucho la forma de pensar al momento de desarrollar.
este modulo me rompio mi cerebrito, toca verlo de nuevo
Una clase muy interesante , e importante tomar en cuenta todo esto no solo en el análisis de datos, si no en el desarrollo de aplicaciones en general donde podemos con nuestros algoritmos disminuir el rendimiento de la aplicación es especial si la aplicación va atender a muchos usuarios, estos tema marcan diferencia a la hora de ser un excelente desarrollador de software.
Otra clase que ayuda a investigar y a romperse el bocho LEVEL GOD:
import math
menu = """
Elije un número de esta lista:
10
100
1000
para entender mejor el
BIG O NOTATION
"""
opcion = int(input(menu))
if opcion == 10:
print(f'O(1) es {1}')
print(f'O(log n) es {math.log(opcion)}')
print(f'O(n log n) es {math.log10(opcion)}')
print(f'O(n) es igual {opcion}')
print(f'O(n**2) es igual a {opcion**2}')
print(f'O(2**n) es igual a {2**opcion}')
elif opcion == 100:
print(f'O(1) es {1}')
print(f'O(log n) es {math.log(opcion)}')
print(f'O(n log n) es {math.log10(opcion)}')
print(f'O(n) es igual {opcion}')
print(f'O(n**2) es igual a {opcion**2}')
print(f'O(2**n) es igual a {2**opcion}')
elif opcion == 1000:
print(f'O(1) es {1}')
print(f'O(log n) es {math.log(opcion)}')
print(f'O(n log n) es {math.log10(opcion)}')
print(f'O(n) es igual {opcion}')
print(f'O(n**2) es igual a {opcion**2}')
print(f'O(2**n) es igual a {2**opcion}')
else:
print('Elige una opción válida: 10, 100, 1000... NO MAMES HUEVÓN')
IMPORTANTE Por el bien de tu ordenador no intentes, la ultimacion de O(2 ^ n)
Creo que en la parte de O(log n) se refiere a la busqueda binaria no a la busqueda lineal
Me inspiré en un código de más abajo, aunque creo que lo entendí mucho más fáci con la herencia.
import math
def cte(n):
return 1
def lineal(n):
return n
def logaritmo(n):
return math.log10(n)
def loglineal(n):
return n * math.log10(n)
def polinomial(n):
return n**2
def exponencial(n):
return 2**n
if __name__ == "__main__":
n = [10, 100, 1000]
i = 0
for numbers in n:
print(cte(n[i]))
print(lineal(n[i]))
print(logaritmo(n[i]))
print(loglineal(n[i]))
print(polinomial(n[i]))
print(exponencial(n[i]))
i +=1
Que gran clase!!!
Solución a un problema debe ser pequeño-crecer constantemente
Entiendo que los loops anidados pueden caer en la categoría O(n²). Espero aprender cómo evitarlos.
Lo impresionante es que 2**1000000 se hace rapidísimo… una maravilla
import time
import math
class Complejidad():
def __init__(self, n):
self.n = n
def constante(n):
return 1
def lineal(n):
return n
def logaritmo(n):
return n * math.log10(n)
def nlogaritmon(n):
return n * math.log (n)
def polinomial(n):
return n ** 2
def exponencial(n):
return 2 ** n
def main():
n = int(input('Escribe el entero de n '))
comienzo = time.time()
complejidad = Complejidad.lineal(n)
final = time.time()
print(f'\n Algoritmo lineal {complejidad}')
print('El tiempo es solo un pretexto', final - comienzo)
comienzo = time.time()
complejidad = Complejidad.polinomial(n)
final = time.time()
print(f'\n Algoritmo polinomial {complejidad}')
print('El tiempo es solo un pretexto', final - comienzo)
comienzo = time.time()
complejidad = Complejidad.exponencial(n)
final = time.time()
print(f'\n Algoritmo exponencial {complejidad}')
print('El tiempo es solo un pretexto', final - comienzo)
comienzo = time.time()
complejidad = Complejidad.nlogaritmon(n)
final = time.time()
print(f'\n Algoritmo n por algoritmo de n {complejidad}')
print('El tiempo es solo un pretexto', final - comienzo)
if __name__ == '__main__':
main()
A la basura los algoritmos exponenciales sin anestesia !
Tipos de Complejidad
-Complejidad de Tiempo
-Complejidad de Espacio
Pensar en la eficiencia de tus algoritmos te lleva a replantear tus recursos, por lo tanto la infraestructura que requieres. A mayor eficiencia que tengas en tus procesos, menor tiempo y mayor rentabilidad.
Entonces me queda la duda de ¿cómo google y grandes empresas que usan big data tienen una metodología para llevar sus algoritmos/flujos de procesamiento de datos en el código a la forma de Log(n)?
Una buena manera de ver la escalabiliad de la matematica al computo.
Clases de complejidad algorítmica
O(1): Constante
O(n): Lineal
O(log n): Logarítmica
O(n log n): log lineal
O(n2): Polinomial
O(2 ** n) : Exponencial
La búsqueda binaria es de orden log(n)
Muy loco como crecen esos números, realmente en la vida diaria de uno, no les ponía mucha atención, pero si son super necesarios tenerlos en cuenta.
Solo por si alguien tenía curiosidad.
len(str(2**1000000))
301030
Tiene sentido por que se le da tanta importancia a los algoritmos de ordenamiento de datos, una vez ordenados se les puede aplicar busqueda binaria!!!
Me pareció muy interesante que a veces uno hace modelos super compactos y cree que es lo mejor, pero no, podría decise que sólo complica más
Hola. Aqui hay un ejemplo de un algoritmo lineal : https://www.lawebdelprogramador.com/codigo/Python/4738-Algoritmo-de-busqueda-lineal.html
medio
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
Es muy util aplicar estos conceptos a nuestros algoritmos para volverlos mas eficientes, a veces uno cree que a simple vista estan bien pero aplicando estos conceptos quizas uno podria estar equivocado, es tanto que he enfrentado a algoritmos que bloquean el servidor y consumen la memoria de la maquina virtual de Java.
Al calcularlo se me acabó el espacio de la terminal y borró lo de arriba, estoy seguro que la mayor parte del número ni si quiera se ve porque no hay suficiente espacio
Me ha tcado ver sbretod en los problemas de hacker ran que debes obtimizar tu soucion, de lo cntrarioo te mannda error
Tampoco hay que ser tan exagerado con los algoritmos n^a siendo a una constante. Por ejemplo SVM que es un algoritmo super usado es alrededor de n^4 y sigue siendo super usado aunque usted tenga 50 000 datos, ya después de eso es muy complejo y puede tardar mas. Hice el experimento y ya despues de 300 000 tarda un par d horas ya con 500 000 ni se te ocurra. Pero si nos da una idea hasta que punto podemos usar un algoritmo.
Grupo 1: Algoritmos Utilizables para Grandes Conjuntos de Datos
- O(1) - Complejidad Constante: Estos algoritmos son altamente eficientes y se utilizan para realizar operaciones que no dependen del tamaño de la entrada. Son ideales para acceder a elementos específicos en estructuras de datos y realizar cálculos instantáneos.
- O(log n) - Complejidad Logarítmica: Algoritmos como la búsqueda binaria son altamente eficientes y adecuados para grandes conjuntos de datos ordenados. Se utilizan en la búsqueda y recuperación de datos.
- O(n) - Complejidad Lineal: Algoritmos lineales son útiles para procesar y recorrer listas o matrices. Son adecuados para tareas como filtrado, conteo y búsqueda no ordenada.
Grupo 2: Algoritmos Eficientes para la Clasificación y Combinación
- O(n log n) - Complejidad Lineal Logarítmica: Estos algoritmos, como Merge Sort y Quick Sort, son eficientes para ordenar grandes conjuntos de datos. Se utilizan en tareas de clasificación y combinación.
Grupo 3: Algoritmos Limitados a Conjuntos de Datos Pequeños
- O(n^2) - Complejidad Polinomial: Algoritmos cuadráticos son adecuados para tamaños de entrada pequeños. Se utilizan para comparaciones exhaustivas y se vuelven ineficientes rápidamente a medida que aumenta el tamaño de la entrada.
Grupo 4: Algoritmos Impracticables.
- O(2^n) - Complejidad Exponencial: Algoritmos exponenciales son impracticables para la mayoría de los conjuntos de datos debido a su tiempo de ejecución extremadamente alto. Se utilizan en situaciones donde la eficiencia no es una preocupación primordial, como la resolución exacta de problemas de combinatoria.
4.Clases de complejidad algorítmica:
.
- O(1) Constante: no importa la cantidad de input que reciba, siempre demorara el mismo tiempo. Un ejemplo de eso es este Loop:
for i in range(1000): {esto es 1000}
respuesta += 1
-
- Este loop siempre va a dar una constante sin importar cuanto crezca n.
.
.
- Este loop siempre va a dar una constante sin importar cuanto crezca n.
-
O(n) Lineal: la complejidad crecerá de forma proporcional a medida que crezca el input. Si nosotros recibimos un input de 10, nos vamos a tardar 10 segundos adicionales, un input de 100, 10 veces más.
-
O(log n) Logarítmica: nuestra función crecerá de forma logarítmica con respecto al input. Esto significa que en un inicio crecerá rápido, pero luego se estabilizara y crecerá cada vez más poco.
-
O(n log n) Log lineal: crecerá de forma logarítmica pero junto con una constante. En Este algoritmo hay una parte que dividimos y se hace cada vez más chica, y más chica pero hay otra que se mantiene constante, así lo podemos reconocer.
-
O(n²) Polinomial: crecen de forma cuadrática. No son recomendables a menos que el input de datos en pequeño. Este tipo de algoritmos polinomiales lo podemos hacer cuando nuestros inputs y nuestros datasets son pequeños, pero ya en muestras grandes no los puedes hacer. Pueden ser útiles de vez en cuando pero lo ideal es no usarlos.
-
O(2^n) Exponencial: crecerá de forma exponencial, por lo que la carga es muy alta. Para nada recomendable en ningún caso, solo para análisis conceptual. Estos inputs no es lo que estamos buscando, no nos sirven, solo los puedes usar cuando tus inputs son bien bien BIEN poquitos (ni siquiera llegando a 100), de preferencia no usarlos nunca y como norma general: A la basura!
-
O(n!) Factorial: crece de forma factorial, por lo que al igual que el exponencial su carga es muy alta, por lo que jamás utilizar algoritmos de este tipo.
Muy bueno para la implementación, ahi es cuando también puede que explicito sea mejor que implícito.
Aquí voy .
Resumen de funciones matemáticas:
Gráfico complejidad algoritmica
Tabla valores complejidad algoritmica
“De hecho no tengo ni idea de como se lee este otro”
JAJAJAJ un crack el profe… Excelente clase!!!
En algún momento, sí analizamos en clase el genoma humano y tardamos semanas. Terrible jajaja.
Muy buena está clase de esta manera encuentro más fácil hacer una optimización de mis algoritmos
Un pequeño aporte al reto:
import math
def constant(n):
return f'Constant : {1}'
def linear(n):
return f'Linear : {n}'
def log(n):
return f'Log10 : {math.log10(n)}'
def linear_log(n):
return f'n*Log10 : {n*math.log10(n)}'
def polinomial(n):
return f'Cuadratic: {n**2}'
def exponential(n):
return f'Exponent : {2**n}'
# Generamos una lista de las funciones
bigO = [constant, linear, log, linear_log, polinomial, exponential]
# Generamos una lista de los valores de n a evaluar
numbers = [10, 100, 1000, 10000, 1000000]
def run():
# Para cada valor de n vamos a ejecutar cada funcion de la lista bigO
for n in numbers:
print(f'\nFor n = {n}\n')
for func in bigO:
try:
print(func(n))
except:
print("Good luck!")
if __name__ == '__main__':
run()
Y el Output en la termianl:
Nos sale un número de 301030 dígitos nada más.
Yo te ayudo con ese Good Luck!
n = 1000000
O(2^n)
6560522804947138628357351247569968293578735626161078371528453221144550905536063548828133195232585570936079438231016886521016119928110824533030320403377151621248435906581831815529894155615254543668879186918283694287083723853484626255109092588114760285036730898357269686350368638822669864908260268648188808647686742814111323529058725772436872789284545741546789286847729083403061260016251241580231116215741160295155843555644513235395208808397578480862850273381105559001961528655933483319995158052258936667863448800092536294825216018934082458323073763028810054902927676768053623941426120549133620101467971286129209750223376417698338193336310440609957986041710140543977943540519795339088338710287154524966254942379722824700708178560985010260187029788379156345817661044637811543574352360535635577489281515457719887048751025219868109281153783150708086574517184160542356900838238527807122149312649164397353099046886967068285743743268692987521581516112645014387815297998284651029999216971400964974027523583659576577489958771930061843371800234756076346087915512216234541856993703797494625391235565572274822313069130671160830938142177837647772626844859739301184749395920626081542264629390689969645013651630670235302195217810503980784320871690189782590164516589515775516834018802838786671859057541495595636017246391736202892575524743077954463066094339538228855331005021740572118479202244738377056809564699847535218246535815589792270982322050401998218041425025944068657795295996343242106962672014186650097587703507274558027861144441750587733869197880899767849642722221111717450763610489524473202468131948610561855455203916086627497592951292290725441211167913493101059837945174339081612488199311104832746801765357416931387177052025586767204683851738451217682367545897530468762915201225248481452016789849908816895164840994928879233156428187674679440883090303104014503244527703932793060013038256354845865571223309779506768314883613158282295637557473586823071655596471472247882562122251540885446992194667501041160900196357703442881859009113726752548376464768652797169410386201026870431691594319229348310080819821635684296614555082001210059301348926879608654261293745314845853997008769818736919048016945703716759986522599110320845242287682510650934339906533802035129585838428094821083194382934535833246938869988985809259384131115117606620927861452247906076953614908375679844774540669146972669039209639228114067815435111017054671331946970913218151747784238850724628442567740016104647270574998365414012910702955420479835856565314718713140275070888987468054950718503922951282020186211441391192214129188001758650746719114590340372550823872332857140835813683996678350033158337351529781442721882023418079478515538595552425510660514555493457175578371598071333292472912966072936257571148306374182244891435278905352210048706213344120876579649767011428488399022762644673027168746477192034847546284459943229196216099919089136233689996072704477785195025203377441251262276157156805266962829182654053004828339877964456942361560020559546584189552863024614180565845415964184011700673315692529137106282507275272531912508988897628743014938003937375000591805909867007302620129918685330661385842176257746184979635628178153970124511545823655667633376411674909818146194254980888887811918565070126681797821852567659233801324539707832696771056710771261912157235966917762144005172097353113881784893544562662037684519809127564155241303937489268460014344406104048897929460545179209793990330697003910634254771560001193806388516886725867439507115592995725892125729326561367617699096916080895022966110826974361252514366071595114866338359094326931554009213199178082758539953169512430261367291185750433179637546158487318310030994909547288264418475138427713616387375984054634185102583456885180966249800187083806345886364975095916988649621770811472595537011606840692141925387487658378986536042903884022180122105268329663363080982969015374595036274001954403417623503010336733144770955762968142522886072160439255179211776636207080193928637748446420368002739356486395214243084630963087319027663220565100051741387455685536998325752674753397511087717728286077540620185485444977373591294351309820019911021571809383068987744124269963152218064390070870752859380660621773776970386038104452803195892760019879777077145885466320137014986266601376547518471870012497626306525945383980826479099983837077095338462242549133138617309484841569669408431486712252152617596544099205216183663197427670879410908282251688442625353544175460215820502180979303948364277985433208912057104908626609003546022223624718479195661418006203713508635807680885081597622960860087771070976702107648791170118544281074802364847911606558369300912428101935746383931383413327972323756859329663978641321437660185320313185402185903615746536806174557146049084087852482146143709950803405093543183475242527333110546495930192462678051166126090439896224058208342435370566274251933610226094490341366473383659702201412448020197775893364750231060681267158727644909187219132152785158723401618380112584273138060905883830410362534624793166942417528392824615426813608062634285423537220600509638507141184324260554485919350462754175688962052244383455776873703869501539175705548933956656810374688938240478489387137252108593682622445488727094496073401689903855611885419736892077422388396740587373772114455382773836515634494830794730063096339411918618333114633980329900102979378355939051453474610143362361228142478139183701030894466561628972802441349442673364405956856231047796127585395302496149761228365805402144501922991273895815140051366060020196339485171090102986367986140109932523246622880832953361578406114604894933278372876480904101136780049824353594209934601966502153046849777837018995820071866979034382537709034966046192296608945364798544738687185055263428836449170882924341044255371128398379317186649282710528715222969103772484452906003542392944586611804863761861077716397303632674815293631975703477490749862066257959243498780179926718985469141687519378245545072741927823137618091662803785763814391799505212027633931894244421919654535114290497511136131916214695001308974106729300432867507636729792670284506355234811889508942666769638728526524901050165683293105531810477989017681827032488833736484766592259189344948694491351593545517554837467312651915819202342949829680911115248157901967453984009315149945336835334450729666115406611140661993259376865750688381287166326936505806018545331589132999225667838401178770546777532526180880822078655142058054392556475406784058367558621850127905621892857310581840010805031651308787317062745422672190302415548135048458640475103322813201365025360250268977292733162531184640019852391310117126701534244023810051661303394228140533599211397458947027992272134666645875334084206294191645719253143811241389149432634939961839552751988122684907415627459467917162696815819608829712858085390428826011358797835863206437199455261373865411936939971991264428520980540852190474100571989981565127937395468302296430397539260707382818443834995484000945992462217904519900529269262850231420025011407322119078542789867706571857887292431451342557302829132891405279532831791850467974394623857028918035767112464815712488171851605341867412774383000026837324169211179457936187692805260002827930475658511859502413304145076756522273824100601359568890885752445165033561941826913331528273908921786373174939606241229265628386164111171695191821042315238928204329157820827856610611685806239924740759564016178890961582207833721296746766553403159031926150028438087182286739756814837086286291900166239117519099738764389485293131829909881936968850598589195511967233164502705433986257237213426792732616601151015022530012440103025551051715092521569643434202729925630309242354440558199585547756533526431964907612134653371275171360057134450757769655076460204886363539728611230818281057202732776971599528819553547891534934584107026460651376450871096656691187054621236397885946515226817111418939001266917348213074603292514262493492519722549121377081697776538171128812362930760568678409750532230006583383776162587080725233735173057508561420960734752943171754973348542475844214522908165581022220558843232911001983592788376016327907221779596519256290875909197089277315880685022094926945769206527068203412075802953951564742610686121958300657720389929728416319842758583511481948106303133791755141612996612207910199434295305502896340272400851968777464334301675774316682797933885856782139729233313503612692211602680501218385206796801815026742310781209379086393711315137957479803454802044392315198333404794245990015674729963569971847258760895360185914621456882433436367182491375756714840110212702235007499470762977795587645487659097353712025438564373710678575923342611778094830424587472589521264368963838552043127139580097414361967483951621521292012056988889013954627812830376817518885165300394513107467419964719246440731851866852098118018425393993423331184259060892385691984634015226599412604421267952741536197707183095061255804724444565125173032775925342911567829206668496357411837379550710503133941818832680364275403144218543414778013942992390482311077649003961652425928639620219235580711852884224707024552838962791599015473630271733310410743900017314435576961908007558091914489960621125708812293771915466118030242999900097011752260149032938342306179150087158933753780164333412844325080850673226904228562973710859804086922550280859843709211830379001678577329590532091659765510829427651340563319065646571363003911274408827893022649605922277025571610162798257439383618462160779019390923934898221297506779551163170022415768555126784848121549523451808814718906768066078390786147577291401408930927131687715438919371338542810863506167730864864211103467330047462001726219789031401292247259476740647500051639146206421160256112282935486671943965861285532746475046961744876609315971741774603437853852687841186854015323587118058891508389937413509614037628068676860571473277840846736758817246383718551337724841780156290276081599432452454348866753462549228468910947250264832822930701927780145575276876792427561650884762273486427689685269220419935899531303513588166702134557702883961771735389739091692111836893014937167093102048855121396905795206925294657131041407727516568706847129026425463294517875331633513128280632562802243606103592649235144501070817765410451269440665044826987572166623698318227951710782990775129050082286613417115706150794557528283802793942503031673354446112717245847552126404418356131096221226009162702229164445915521987269562869411739017330098477086806767339323891460361636954936531600250249552566314497473365272981312658083609707293346795170732246117189014071807386163255122185087296425970380196595083763819801997331772085314879425960163711150354881940077087364642258648710923993288451574498599571663654071200878488527733871241953530607576617351830989225684280243199223726500603991156824296913029696975432546834844004711050393106695338575648351047255294111152726048482283276014012082190940207301612894109697590436522317068031426271083325522320384717744181520919630219250839456326935833644646997823953055075921155619545956886078335243803299200658225487266928348916663865027794263953900329969331668732881039135689899231590319403076637467886657730874203029212182527938741921936819417306678160693560951984111064902906450416860057382474973917880746372851861688801247675231087611364529987889755868612846135066434153478955238779989136987149828275432432549310643899782484631190168330829102605109657679592450476521429842393866225026722921960874040612605083212395572505204827001332501202630430665050434749686325636368625967772826443188959314860734591777820835734185578189265391601858568101850519625317814549108963555337167288493531127616663922544016160327029831502586354428278596119380892453358673396440087932919720736320595573341805106460320759365231428716923692015806305263991779853042854364114634434032872464908020413798857251225430840599891327397888182165247443799316699980164572003080723727636230907697433943575545836422606948640939588315762823024827772517903053135901487793495251068676000021669510902704593663796426496764202679833658581931982419201347295706250616825110719193247433805989240424128245406862821386031317687500769472215919171676014400757243100727038617763666614344960440433894997320069285155875821363349577548931526461373260436557897637435233575502059614594639914267078457534274059411623668543296329428493501015645203718097789318203625053646821129983705661091701537303456259412138856327109652373885427338632807007846108798075647335206606143357767935833412799499507984135571572551913198398897420356623511250714490001915667927899977496585385566766253712318659585995318665746782190832359374115472438367592376673563414259047778086496993847046363303251140401602098307045089501099590070004881332081357038493149233754450152788547708991071465220995924099874981764643602435395764765472384569977621370824606118543380704551627562491122141046867228244346226258918793519223162743466141572447083755974145871716313038208937300885446561014440687990894566388256860175415887473221239971049033581888446728052792053629034980299236140985350381756308297036046215476931819981835951016153267871722694260216655622789582766619735928229177044921723749276914993133306024879947491372915887332814817366331998658357566509351769620366887736033113272827698359291037132776018157102595201335570727516550656636335605016360250199600607017532072981546121536749906915682769812820617542944727893646814788659661798188930664360320235745100160398242949177243939601103093499082433355898961983438047835848202483843474351613953609143499786568267840874480068143453438408652596408681793072055542699142340776010282049293846700655074585772034271536581099313229009557011689563963836575495087255645037803271877345529314668088689934355667436786206070533060739655179794633545074001033418185048602790449583005010437901737201959704672618885299214829981759265879960950358904923608553112128756017267760035246978328470434702516566118534266796286187833517568190448742683445117215134267085099600206931615527192122154825322146061126843472806761318169652097055529778456790900358300729617347617307730439500865140179288684102458451971178520587006074316026832910445677876698526505161647949494849063451330147456996361967077883202423051993920765036012782487354886452357006118573206341491956347733408666400510603552254547422917405693132458017874313517348074959475615877396786797857656232380796868810375013814595064589326439302584204238751694144443126327006126275076714053427163302807342865426860669606548550012544316700179924891422202548022993703239263722697411555443126968458078981400443480590260064506109366995328474535628401224979948192205652464650109469471686454416539531410632541863084039746193060749538768713610203394450363343375660685045918975807429517385160712721925732498822978393357281875230172756609255834858903159078732230201904773970383700227005028173402128514736479501123719460447290580047751754178237095205303455519248927035016069816059479289987180848011774436550026476257716201014544686993323674730717221654934226313506084676331498655857350557662943569106664029108369769606597531621051733026734458527274227058882039855817507458542847107314044753075659832504565989506580489915970923318442062495305562053734355206643557261901255129468141524233880712893003932547393379817596063728309010545018769581421802311212269792533559839380015765288638212253582299314975583302907656301609581219971954129492830349719013404107218496411307076195813150471075325668306743348914752030133991350548269076899369178991544684114008681455935796751493957391790855783680364865618977501553267687763464613748580132758100918949076565848343172558385179856597373155310597385060500972509042588254910820336514332921583939644077522922155631751560137665967830801701762331737635061548880428191749083656610264629924507194850182056457832932461035342599816410099197056526109503913030606708227880369201308427781606797147226460608894293507870077718981988962700786278323133666474691326214121698953979459386620489145831155316620543030288456304269520380621721492656414746042473927855879301175602164451290566742130645566501905473281904500205578323875752998866162720773651867844192822291752274790059162803254080595952011851188742566319718271893219705736686095357685421706571845929690068698090487491456714266252615578868239624992913749316027034906869272373182784041248626922189849008974390394089978186103860460870417731244159545293068653563775962978243747848976636525047277507616793831599548438684062374287958223543832979255680200322951009211503844651739871842079862645320949084439046492240874391991861763327978457352583296880860600591621955094607882755387855138859609549091882218669321643386863540739903952124684987689171444574390915511672232469294459465405054611166114523385358948470425254783717257102823675405731843077836496165659758533564457058091520440695777771982180797266359953811614940278206229397692025602686479943681219537270528327362658197770248058923740830615153853186764963628392243650703566425705538109618635069437514648564534116158449507804770389839495980270780203629833294932906472785940321873464225729636025299260925866828316315534726297373234819387497751903167089595953797313962656728421040836193793359751472210652463760606657312254945265554139516764654518782029592517044953687233243741650630414198962431426623495638710042738359441762108864428240134721796374271958654822616736788281899340293076425563987638486521262400579077418306163408934326887385288793813829788821923963655133039641364983248172681015448068223772312443883273441480761584586329853285393095509266055840121308229140109347569976391964126802728755595950994854794483440111260238066245467772924052440059558168252530996709352487514479583433947487075467521736919803472176145186648907657805860132789381930193203806896768759184947958175346319183476531724460894271196591805373454445141313406096730168695429555062354894393878306316211997022129402357692741353508572854466638657128526339399046463939925786838878082215233894503605836902060522196495146507221141140836331525849319324603992461159521812444297843443099018165372336348925755220791983317133643267013729907096874057815317353138842878785514039330869608111941503333729164606226268459824375008454252906642049971783244678376455354661948591549947041796730296354302398768276962414313636520329805223412615794309226104721128456879650480126473516594417546589688122869334910054128790854808764087456882784682276563755641859893718251456649309350263182774622533999349433059870522046380667476806466278830805983918488425845920510773022352267650748585884919062904267355986505228926336285002099365532774817054885782756662109908076924101461041725087788538648019085897241047514806603105877872134130616146777313084198203727991033592936247458401831737185851065684216841738311394294441200566890362013441113977453776480255956606762935246777348764335700791755861682672445142567711482555761245554995857961079415314104771748059755754966296147017046528219417137788052446472907896103629803961982131029177579281542109063156666317342824830155787475105047789988084912958027252197273967424414210125886744012052329729392461431315133909158032731719798182578045112681329070124893048507544473286152619482837461999758390914383939226938385038488494483071532413946660773092945116108795440602755182031631378311218877310882737078215295416833692119680679035681797927953063854983152898140925559945378906111205577052311730819069513507253651007546717006838819342280064285510489035101118101933722287642019616331232087480345390865158439800302190088396062992521565728299517179824137927605392547353941722276740316431681380248962289461810535621506460854566739668741511108290129506681681763244264938219751502500999436612268135033523782871916186424767728364060765978335863270759911099769736425438338598680819772764834629340742453225518524706296721462754526999800648755427894541917222750551003247827927677315555254180000170590092270472561869735896251075522825247291257588311172640482015919306317665192365650241004219042754471629898678533007496752067315466308877530657101198228183721267088768390490147587612507436936400000565819986600507119723065284777032217896941853836752330283452137221119295647429106671761628971890809134762456250572909951937967603667164415926638107246412658836142536911244724562553759519816311462593052309626235041061761607014409099957809740685832043689929947895178272386713184434721254934765122447597029975892213705223791826392633752650622803501526402220062468624290049461460262370624485556029139391364867000140050985955114846782876122424515487353865589524126729435990122368162128389008849157671676477081254423330260043602227110988171738410500424556687519416889781277606072175379800368971928989435542505322753834600170806672983146588936963112873231616139332779674552977074976978319288804460666482055778235396715612528586017822770131140391583474428215727161865465036974806093381730713633144642774805870057762554808752485818056866281581982019393089788790228950835726238731969120619751382304123103892408813985519875415935393494460343672889007380620873300890104021910505720284924238773165291375211573490149241449322334951744415075651293172976290072068572469305312123173556073586394705205973485437406412037122796592846283497978501246738310904010660045497979697582671076924541631244169584904391389698110658286411606943386838174586311664339901468258288265421066735836011499486842551273354809544336398124817060506046640857199922518289875086560446320409641375160452506688638202563894893302753460416193556139441601107813730129913041733409388233352723374586179082667619669644713462722130235267987018460195612900711280010283579105568374843595721912632228202380402454946991898434710953202749321120083247306623091222718081807601525542320421312981501714180500561279537067847089069199891815098997899651905771361903039518147613525416123100634270734263652611006947776613217015411537149999610340595318572028671858583919219476121002886771740830761700813927079682552664360158921433254540756611061378749388299786464150609614235941320225264800592971694059481624305625209324695106643078916176036263057323629314580028184758794581177268754585192647008189400995084128832514334540168481180822434435731702313283083688909838595835765728729361513556011019130904192208936837848947136212685562390470816322237120970765000657193068321635109490676102544728144072522828837006406550140153917189811297885172463540880610316401148057997064342873452543093929098060637856475918101204825054425343426593022899862169791715019169950460370077208282924668853113594399280506997610305476496982958560248944250319190041837789241633072401676361020746423215336395282413001140698655225272054698055674305868565304335514321753247344782358912481590814293146688922350087066034426204374949331729774012025528238472767479018255077096391554558027034997799537821397534805318534658539377549335728144465560347590741787620730209517103726293520099852308065402676273470597399983873003831839142923378320347305901057330087753418510082371299392018965267342598908058326377905821986738682269004018879775131449613857789229849162237097941283538058006123118533751200693650016967702041643437402664192714613273915212803475476971770324366895453098735547750711647827515113412929631594717569323594820379420435184946356306652741837182059758575100127213953163179607329131638404047546370680418472862870070672258136663002122076451870810744073193067355318771614191147146639579795539140011868315503484377842091493036264580521117524500471768584807264594782640659802488446566283021126722713214868272964706629846747888968359262399609578076816823701591052135474655321715165483784309696259488846828760907758401326853221193833185658057502748353229296411604456961939069529195297137150687664918988488995539831045237577629193200403601438885218430775430618303300398041909398714197781555466728938879096958101077256271004028351720956106399598662778480486727190996617857862160436864731671706075222554258351940988686507346491965108905279491157630410089516797849630156369796642689962868489648349257317894987149760391584360160516937375402668664064080199201446220754719854423892541115204328638930067865801149105684649837931496360956856537911785899753854859438512754204397558532405897928920940369909601851559914977699777386255652352283620382287334294047762900541014558532308248831700732163892901361393959816124354170219565235117128923896011052260875370838174869357477935321625969953430707562119675159613494635475167129000027852325126165254192450509261504745412826212982840842786558209264762555831049896423522509473394897406326325153506101608332094187474929684027542779967280599660906798460087443444818127454841091588990031514533808097690435457229214336813425825605633842418416014903643429628787517074657885490293256805788743203497758360078027026957373547537742100839899069143394775238814458659211896594723368217452026673859744690118052944302451347331152478904029985399182201494545828491816870407913076136699230463001929530462411999685391549843485254668361375314283231565138876371615141531283056928045468500688931690185303146731504893665078864743304410189339106254992977587694926898484017424390373295167944312046623999890566166600860196817961738286882536864316731072956959220105443898714204393571183475734282192727156788844549746076420342972835281606488783906767327342249793054569792206002461692177500361039088280222508188149158035655025135205416341364985238225742665194447032087820856171742598925800138135744165567607403304042186029466225592741648363176954672249507271917609801298188184684043253777416347479620046746937199318764554247549641588626808227309812423434299351430313802757095395372410500188124519720940516021082854959876827283366899431776947792774631116746153455474686803798366337590405946386016564341508922894778335028348546841203736118921704622814539310566992305506073906897233548854814067727865706822352232179089542537169806322264554669590459628873988141004537373933798223965824547801446673306947238129781692193641551656247374110463724093775169406048313558157664459962801447302929349984030800995015147044793877083837617945163514984216492671530917504614850534103518817920128136795690879267348448640994858379209344924503618748947567341174021283995810720911200848800569928871376575369384467695958406904716337360797942302975406387962895701972614992953089138917515815835038322941281263079466594351124103586806840687254838753088517161862263251342050078259968446182599317442811819283985903474898426104676854212081141821130528288862081922782394421386748778208922306727002727682868415069070145258731455912122799849122004303039594003002934997717712183673561068584022435730899834866325854006389599738429396729219993214896142020985755342220058480892232686566694495638290324676928137210223577190253594832239240974428650889497898331439178592385553480409211665255949053260591890156434074570256784944276824933171202710367970170000143557921179330152870469020908895878577250308068861598414379166415885230580150022103093727603052736959735764755713559989297766908492583961948591811824334144181762866975728688431668486236534769412972873312323207888093006731089978951824036916375583032814625060517233204838414475523283366342465704114903008866086590740091418634296483639754823262401027260854290234250130334111412960063147784198221076833276135219697626003059049752632353850020717521691217247942193967492932686010119582326321844194848596011459221657611241049002597229825659511093800634268100243961256669728945838199501082398992517437047223217373001566317027125715213617534428704631487340630938762999389017566048380312371757885845539459629672690093085066986317627262457693628964391929591395526377826736473995518245751246927501531515372540505769550713003797328770397144987340325263134615113329762032043787269795948117823891254570771958684603496598909981391392068488126524740423582955804799483932079488479110344373180175596749674876982871173005046008581344113555936957280940517178609164020482871804582309353595015792906065331044316359420593127837056859280012209705912335463400531206756745494557982161302551094468832682877610247024162350017130024980144097990603533305511785523742054609826165186753861459328079969805380231992905303716390090005664821060644776817782933316264825991401644272703696969936504327482710314860575468860673533633579484633004980214665873419490403062596879036751461916487398636353470469448046993312556353644372451210977421739832791174760323730888113658099398660071781205906599682784195700406448575328460333602219334084409310292541198838556574175205290415166194131865240503816836456530657064875283017712587044952768353851030440638602201011603541933054027820969190912906864119479960240438586758908200538111949645091285049908637799499250523443146410954868360041605531259662449524919596908479175394328824592066471832617801270768398954022735385394137305033693013831870892269857328881347944702691459146377087169659963383939591195196211165253723995703351264033540795545683675509846042750991120522649414615087063452374279763958347699312219829537708107593742483489948469534415003809666241162701602817464632484417496481792809778011942811286202033622951185196049156522471316578810410158843476643436697384487493267387184511819557465069434824629266161178892547856307684678740365563023996604971342232971000611749768792174624706351347084846703949909178745214081550770741117686290293459237796838180457801539503867684863801915687120622513057963555463256083073093259173440381697113113680629111935040680110560990743006040439335853807491347889717041048741886613097363265565820115154582240324766745591993584164243036770460495710637216091520823580999306327177225962071067382453765261460941667483350120295876440409276849369709298373113094421920051014715374078665366895608849727421148307678795406468280939567607120851133236917815536166586150647920115880973774555044251979897620656161851267023656167997492028911213684080757332995443523698062275419159854158523860213114913900807257189575559079023808419699774894874752606945927046348153546708042827107944937234418244802206521117507330491836946562817427196044049777909489957326721912929442423871074731184214969978499595142136589959255955156290699265246068765756999885753180025324631998476530321691451101161653661784218061232897406146400577333943246941027811093004246369979527800734286665108208977987344003820502000575119580568266014952554133568561751284295060176954681355416396524238530766097971783820981899390585923350014344195297355365335155127055448747774123048747656920296866278860584190726304794832081408790847156505037095511136858777064883538810181855212751345946784006275316047717645076234355615152761896172829402992540403239043906672322592410929221379474938643065243431159030308893849054264832103757275130197882428300149778683307068042360310617437138566245782375600953407100394175003153844333710253226538011376441234438106810321394743205441384962860035332762588193731523973076361436075903377743458656910678107691890596733142802973705534764468454870410256179240004077096318135191200718924837385875557776074520416571683565038845601419318281402975663524718513176154915917727042645304951335437284505852086676824489056026422609219968720080011152355639530248671202135485641261926699524138902807997658975201850752489385221370035922606833723692894925194932003152304719858760671526733105076828810518622579415672942426963348855714166686333563354165375415644564578308735966688441410321724487152081723547411843058208653814878254514776026317622251033258847992871542716050953386303099677041748384119131589421069926038661450273108871457085941780111120261106182353701854204710874273549698445105327520737047326494038998890623641786465395504348149936862537618176881998776215422384835567611209088352187046749107182701892081369924939325829996310505017036463652368729894969291498951735164720754667372950316009417624785765590370264762241755482178130673672969860786509206713845068117062301695963242045089868195594947570196675873818456903305666773654473121942760643484593713771262809544405956567689630690994990213427316481327579476546347327866853423141210983991166983648990396961243495648128284372032592429124767395841149613256545594911142356885395985551631667100925888741404300792970930029867813082835075206504156665752980206264888635672022774182137533924958184148779154499201188150785786421596806383891728610448879547443162965490641394696278626722019663913100818038369005920500512175896903098793245533425315090473728393516190706252229619444892113938472389385055076636424556899295855507716937485553061482546266610572540084456087830156780041800319051986481292072009377749210255127893085236856618778078403763910697356299698572633747171579577174855261622839384401043523930277581444285405068322018144059602343475163149439877990944608722229561374652272678382265722045917818260627405361828321497531565314538515656821180761469524549148637379925363431434007446654317300320829171258312754210755962084536476018230256137294569684117161882778435438973759530101386402858858227779676112968715247677510244129725221046001827281808886297240357435708997211368210372868334371738882470625278124352600395460736919620231788372617281914199143637850560200195301888640561940809852657490018499384786407877680454545108247349390605262088869827405973031602116566542180254247592199794174634275353221811650406632126541157638947006968080049388477489842687749454095139929737769713277182591121363154343281523161854339748181849023755655534800319064653189906528852690001851665279775947774627609601036630530722030996588531544993288587856912932330389852755713412111690332227413302769128823246276589848420171889616232899360352313196310368205008643916142932815406650399323856622828874734226314856259097384889360918748231000389094138426546708237486890214588282210294645365089553329382256826352215162863204591112440130113789707756097687794228975360884878755757526994956024187271492412837757204213678195465203543790437689009964819917369061206450575793767436855567644599831415607196900519599337115269046931130459169467408626013768838782682545248228668435696252083033699638955255210414369733699970055320759414213231130385895028876272983737973829829170632309508843519421174775048433813012478250892414687157736754135762290308798166651847228533832161111495892971139387662466835137748982971594665880227563949034342111067442021784602087357211576244166833420170934657250297532695343838183153146856219510695026601634231572922259414896934566754728755644996977161945969447258568205779734689400597514560474623311761870351001406372528264936604216454600104890057220053191821025543191501229214806811514274583828716542994154403139945678796600612205704818239193306614209586407388080383326953286177241486105490757491777040167286030449342614668116362638022579263728979730114680366549746137075781758894372356495192636496202149108536705912304351130023006734977987923165478835572921692717065357122136778199059797997579803838743040047463219171234972439962460757067668386171064177553149308001839020087962219959377030677736526409641357475584135147073736578234678363907331702211874843361053510242158782726658757669310581639336016681699278226837312316971166007543611779631257757181211202789869818364696015153914350646472908342680268576191570077571067760123344819347964495909482768074689955568957336650705829748570372008017691105247125001506439006653856313630957734587746609243285571153853839743033178782853976186817644712652052749025656686874180077133497337832417710260914608863616301139418232862715823137467991318042405176492344817112364981923077509936188240235350335073279575215403264471970015745842646769127741819163649005368636434806536803359966378770450354921622259859273240716872518328270430145422204023470627256919910351927498010357145806816199577082202568979393383835044721620876468908478502874568802013708729924677059245813920001658240671211521240255066993904121713623972660313141828175798685251972121625734900837708694273697396467002856280899454187744444320492952537595108479895045397531311485366403366955378678355515761170131257273447785643595365309186185300730261006110617984508225981635521575962422455244337379714135512145002448612756439256099317631690909707324142990077891509733821863761705955687510660015060060171042702436174074329845536602157750169590491263381697480037202514064318970901997014080957071282372078817765597377004616224367956628000801141514762477925052689113177667282909278642009871454063412572284733317011021601717379625319663234141726125876635440912424522387929287455143984576376902409730336907351392301837167184746053864629256158371238707680529079829347703172695195113737250225908301780749982270362509755272265826861030226463922807914883339050107881630472045502496640650057618358787165615807062627687400759296992377408931395823845458886574937214656977358058304750480281047972895780883193934469776919618759744592516349615906006206214243710627532125048699003508729299266732254068849922535383989385713591205612508383736952980622022550087060938734443122423551531484380588724493868580182500688085544016918945319143530715139703017772290801583210756391033227258954290426150867017819319233004949503515628138614755836917682765597644474732375445821367755382247298900415666558174338781732928123507558856257235210700161939486164066145040166549423054670040434218683786173675483714640593451399639491685883330367973533943523586712660326409027903690629580287201969178509065498295663190010026057279026630064610344061895638484397831519158498295880888560912556106599816119695973754514808113873026789054499375427398534292075125944283595850459940629942127753188465651214666266493493846873762973470657912337733761537974125252350187946469123392132914966794422859557562560152330082168372491890080232106142420362659304180045558806852129032587782720496261598443352813601772442527157801092989257387903596768646850333578700755289819742430102239707225428217249536133207527428945056598211848067761573029813999380607058453050198044743033464041157928856331859783760836623018317201488925770972799389402274621125087278639684124952248216722218522614637684766424814600016000321538147324795528445376285165732605873098332321903839923988501595997336378588797253998300649243780322456585726500204510672479858073244320309297285743208865963480311664242175520125388848116798219826717944206802835232384186090142044135631812401480812716385607743054826961158915502284216445774786252446106428343370085378945697715964766569201693779359299472851020180197185283036022175162031518492093014390648802205588959215432165597459608412259966649546544465899561802286114589470941148481555753721533830861740522513448574470815614989024349504532291770925214707728000416112761125494575504736656570385742863651591988677101961926358840213175244830343367300696592958541463246538253535442801749550141973838302707039635624936117142398360555457277697189908342773559479401418231472642248235868109068118363200859775689657092243152887173386872733442403083551198358500298601751364935782013758693581171920801919246331785101921409915586429269764550332202730595975281651490799397977930370060725972331443732213103020780963818007324632891789635035645504372112397089623552687372339793310295400822578069032117204424914513692649547056218405667535473936988086743546263141758840983916635784618860022292090051555230771523596658492007858861512017765194223168920526300569963102390901675105846196595049461831119122563918446756365989409218999296856435818030084906756945358410511280894121088210630938211978493295572312666071494830841743602415280127284581103068835466869652225050493571428495218341173798278445951191903898848116445315053017843921855608656027791438284467594832588378629407566625405300978349926566375639787753806811053804651491749329136725316222166095904916683496897539314874358806463797345220236646636333073335150483116095202508406555656691019284373492542659196134081915259941473193441653057283136517687215274368275297329699398174670198934851408080360904381506098894399528124859554889485917632242466593732702215861948142928149069166203663320057365418254826132162610311477768210978114347859569814293885244591643174877903399969649737973181188394693163401409708256845574034250989603906906021631482997311834427230155343666128408840332495524146969069735844300388548318543565118479569337154093963079847729896798852085415799005461971626402792434902733844122965569470074472458371853267996518266956596995878642866804795026173684098031212284785264580890518401411889878137590448347367920462852950261429883950878841862705166247052858886272148300285460610323481801406422510025079722949560414100676939525692335070560336865493353831984416193340004105689103970547743833458476250940535454496113729294138245860430332827577299772696114162463971619906012937668616644011499324435198891685425038721714933437971738690312656373038780891917959355485055513651002437317550485948321182051999713004317796162890007259104003139573486920978812768075674918551363471671184762875192913539502304465747906434962915744805058839136235746894536556867073615640733823335795205223826956048781788408338009751924362581379707621800924023658088813126654500452791389240009738750563035059406215937340886811745024769065728030128893855807579334532662168456606120870569732517109755405177833551215897554696823718621311651361574736880337430483888977544800079161292347565532174865788092370346385640923597827342787093001983274857523148837679802282683699909801066278327680701936453815718927764800228474425637407937488726476499743965130875839818651319178188907327538283101914364643421547476149649072892647066600825549031109356952526313938596885862159310096134197979180680179816408235530219589140784034994334968199038310589382653846338160856233394039319154117850819309935288784656490602166663945060621587508945461601278610563752583489024728935859474484254229048465180632266406532638521106146056754651232109104999275792061513333054913742328443222711673405246431782608107414238207878028230614867525272779545445969327553517857912084281223413004749618620364780378214350717450787555675557110794943427813016849471047286454366181027870884946495614087302223687097338449190178598020196265708825911643159452059154486977850548060564991245160758028671510678537150244318352016600071230450706446183199752111065399832835726743420551936592286168970776382853827351625475610312968308771232885454548839797080854712492664367675280797003650247550176857851464577369934606210827110214301757679392237621282814890314700681873260082285528727937302033152420662142255588713350642694319440065142928912670673347047897773447661747794247472089929085276389896542416838721200149257534276466068223835090788097256739938307244521127515427881141851769375864639223728082165420282057361333298811527382574582858736829088014823235506893202879301191632077435007811604511764585077284619322296901774506480378441841155298972971185050821397051980987211849108512037968965180997247434179975084746035977118147826881326057530358275426650709417574237468154080074093175585000936626884655388589006114752511344646102702309935525746249050937088011237770498221693820707204662725579181032455379652787070256366482280227359384822038660114346127337259286983539744848832972626593964242743331108005743092713363146453346977611789518124417391127742639130503538807731919170011451900267533448230194838195673626100769972563864694425394131156388602862238575776297180524909120131858940309444649567652087639648706749573430934912827707709090008894553327092324836103187584425421490656429379259832453124707085910879107262044329865265697409831064139093084865096194649771398611513187578369176256051788611909254828729145302601639992574490726984730777053897321725755061640364572111242479916553968610195859083277962518991527993328944451933172814259267366944231371617111627225466700475809512935429819790467858566039217821540930686001957542198724412551739569751598655385153955415088946837518998563247834665030578381383433083428546231099134726111481247419052047161438182362580780541292664884443188381880112841396731322945758600356798268251159674304098156705101586849708528590834230868431926790301479698973343942143241958040505187034195814783809395792615504641055764606495646061097183743663092691277229221615559323717309083982367864276853944585041983139959309114294738193759733710286125135681410113431121091012140322628248291887056722378221686734683372965280493508380155948195580993957387769261229525351924330918044432503944365261794008341599919783254169032560306601796976130434469676019455873350452363036560598906666751675698583539762427163161659255614968567127623797137844945717908375429713982817718001019978533758761485563549404004299950046427488275089845796800326336975746434711505250320981065140339230088948125111275199653667874370241138630491782623916632538328143689828017710498562565043786880565715154116992192244934345671903450141989578466811246250397294306588163234351188826809113097013926658856689799940302784625056922070140024617282946569695311592424549540270140323285312663943040463296851044211713827296424586781684867497092676389070130147675544955250102974338349375544338718060555919869283437765648155445163387622456579373340422094705749455132776840382624782854734675734706059104972774889662877264266166182055437160176097397746658252156532030601336939838297918806848087363004555753834568804705491426673144765363432775502384750118426443568445165959647745818946063558918397614711936226939964324043459891549961732912457473790264133148055994609063407958365133579200750849191639540935559156882799589230541227503164548969520187130607032688805819426334246160788294730466239601593651375717670538438717801488746613634184325033766986974898119937782658774940629787051036761109182806245689654866246028088729329431553348972851695652643296342814551592927424887021918764584522352503110634447484986633001560225675009249395132021414458375820467116102087684318110928985238317635904571906405878933604267385310821520256398560172021288581310654449107926497827295660126938591075006052525921274458270797113971355495013712693226592930490040163000534325473536553196906113373022027496461485191933130335121053368875614492058391770135431576837801097039782333698511266603406704043223882914086061278246913860329488309404605810438526738428208051773406443598627334752107586739929088401524804037484130271488370036444064160796317564667113724027407869780750601064924068778181820539758088121058479497061007361329808359594439282208330095326688920466681575819487277412514777718736081106101389233219840174953001151399124078936177091634188831593524174575773722264747709366886397257986119851483715234649801789626599368617689890311044097129911562053579290225990120287513304397669201982317757517752008824521457923333218023426799509438508355758692126897123401112469351761980762678116108382779082582690972539388917990016885249681629943420025485479232384784553918822556261286450173552157811474690021507667715829251355805566829447014049959155863624059940626728751326084602927177319622930095544060303014164043504225839780904126400958372671659362152159061341567984265915686403257944064217509551485531876606359288511645401727521561449976139660019392907531486259185016148508157105317973627112682460485451502087270516722732166361944540123297268081468936198445470806881520651079207539881259587159599398216087443177279853481132859099672227557244135804212828057275889670522253490659904687053242213380316995310425495255639578243223440639252865039764221217528932939523357174039579838258836360158186992374888388535578674033444698384108690535582096945781518748832574342667126482908348091994564138192628376111196850811304348340582145516721142014466348280862408831994005451844560544420551735148979861285995466751037977769209447070524109066159581907482228533798363196484730098132435507558316827529305356188519887515910853677528191186354049868736940371308990049497191697635302929233230340299476868872129252926402624362537587050762399909731916688464367068678637757429737100791964315869545906589301888420786594846729387292833864932312834104668295619110433934928208566038652244546400557525910717075031070839722210809298597640953159751871509044016123087353346212511377456780365519019166941842665441746349802566493130916619857769348976883187986141426471944048830484739942400535452665179936257820588052361560636263434243591854944273533015590424026942240719510109994833677503004928314979337460071481236303568460581379802982520886377511252287964483499675066092029707692740175512740449628447069370865957999737687309797429116802405324331904522308660347997023225969779142036508306656143644677201308675418789536143682901950121418939008160443194343417746692970907268664901329832340045022700669518386103633931879784613839986910815507452495126838041268155697491161926785573487148238360513911748736960369249800020918590999138460816937414920047727943590234306671904681012736942173285595059721569140625937425312874347713709863447765834421734695131297087464465202908115573617308859629851456735410576920663637860431951300935189614894536340896433026446331496355202043164432394877835127555505876499765735790447694916420369277487163301260731638098731313536805158214547900679489180637893983046217103375557630553119534476041846899646797914985400536887172987244210310004862102710956343409981118754728149179945705641995313695068783310902546145459876956219516844344174929417431669184202887548718809619383707160556364098440019385033001852806066737250353178088278957493405694292491691245061976051075087954297284308308685176063785846033842764313471464559987457680236444869020379438649705838058270355290596594080343109976084690657221373994857562265518527183484297772965651249280658330037385439487373021024724584311938566607965797958963343551825895251074852721873251097136381588377510682006771181110168596626344609548417943768256246192181545205582754404683949078570860677659551617064943271962219194683259037222575999649403249747553960936417002239045818541063475920542874005271074664098769557282220018747535179702173440299031107042750201958801129445643438621860951563918577095181407819122866752991154723480620719781501732727948859587709772958425328479553594756354760671099874864646998319751214729362951284611946545030205616811483898752969173479123455131150638738200994020310574909072565206131388899903487425545992452912696711161287282055070870667101813756154465666968114248880060465825766494760314085362939499004576107434156830250994533040841011504532871017905034253176174932315965675777501474715131068214862984415565819516816948727606876226725040628123900016003694914958912056968438872699859570813310277105984155312452759577257179631496198948197684189939358546610835954253344284677429622753170370117719797701126053049043196631240575090820971236564400641122303521163854913358221216871076361352923517691985094019703854781777528690287949319499377120476760276725386096093761618013908277211748399000613719242612949458613662442575315833754161417181696283437442363059752639748604362973427383215664750556213209601056438950163589943141405338526297064908240219484072413056718242324828299454764958908220315622599895156803338456908060103797739223895668663113772884628174603473292800325815791055007211663596347180246295186485022150175833399580180382596322367685644883227108406135451690538840863123901229887789780506474398790620784869993102028482553875722058661991391974378119770600850270598317336394430834936955482063698046924451530658093114146868407476211300868590766221806220755852537462069997167234101561499422964561897923970738798426065844381687197693481117824516259349383839379672545255233952737526724381962267590568275293338261687286079199140696418270902341838120163363543114030393638775180197699999256409409580219480423908648323912875147495419973723739453689247206969592319839988905663707924092344574428787133815761978819433239157018559788562628430112811636071773824641021720030611404670980879185217862406941552529260334747575477586520318025116854715232286672003518521842961998496780048522710703127052413741824733082539467134517113278266708179553097844732764160070790318358116443336866546907897053454248169007148250327475319065464280824976840718593678426612640949305130374353264410653189802783616065572981888668618973433709417095319196898866950928389987657064146065715091185781201581379553979818433409219568253661368532872340089308691318379117818440330147690520163371813064939405992035786276169410054651652130438776807116614243919896609211870898643616505110887673710897180726206792280441751190247599399425140571378729585082220577180197041868430729734836748475003093810652755426878780053799397304191012696136074282147365330479809749443220266401168335042068821920314636061149410223352928274001967871215969074485087156737856768613452059046611518583440701951588149884962732694336960176685427869851057587667793586170804892473884007299887607686436780090910322713911409107619860670533813465647110842194199470763710261734340451107722645781477704513677216547065590870082030595886673422973506218535699036250490096333728093987864424739961214369146538584913869616680734636354746057521140975088754537092838323054266272763418957019571498048132599127985829099404369406911488277389085644444576508361767996760585107705827172005558682862431655730624490530379257204517931805139644085985468776476258649568643161005510957517689374385985897170817517572370376739307861090839245647948933289876546907767674649469447266024935617675083187281063140584277923561591655499355261518392995848751915058096695781494437362921595282004690039241689685546086872285924168521145763878635415977812062437373089686577947815086211989963465539489146135836643244658952124903528102811185626429125415058241996246026272186486799030748030005647179560890126783772373408030316632051171051132006312417933120882546436762314897792026174008534292793911394374990859090109317708540397986337305723121804622819478163489902541927602500524886436108940743049062144510115133014081687467186866272139054564990567968648163397464618889527226553324686635145258688765752358232285666531684459259203433112319924000805211701071343546592971495675078532803664047289361339755125629037531796760910552296424123669791572530120259366033073362600495785009452832231209771651949930078381172819232959576492598854637123171148720654845427865171709018704436470288331142807637404470838721862775946702594333232370930293593888820015505512186840199087378463823648294836014728724026926173484210843819335665118804267738590388961723310435946436176254215109329949293796628246696029621753349348315534599715106075238114432824357958756046801829936663346927498252184113139026154190762101570232777464912829167554131237002272757628421649388240673741858577571237989895175986725568600702493511694682921171113852563711376533487112022676879462444600041932855783251617241085645011001036578193204466256314580375135866175958334510775841705204022698031471290583891295636747619296417826487441672855818541664120161336264596269328635225914285144229375864163429343101487229024976509832906753689215241457079293625964237491439317020877311008625357775069148569092075651782488478598420407064596334261847462588170731310996021657706771510081099833511546595845746196783679831720727072683207591757100428209192420228872667749052301871236104888403162747109376
Interesante no solo conocer su Big O, si no también saber hacer el algoritmo jeje.
Clases de complejidad algoritmica
O(1) Constante
O(n) Lineal
O(log n) Logaritmica
O(n log n) Log lineal
O(n2) Polinomial
O(2n) Exponencial
Buena información, muy valiosa 😄.
Sólo decir que el primer ejemplo de búsqueda lineal a la que se refiere el profesor en realidad quiso decir búsqueda binaria. Ese algoritmo de búsqueda es el que tiene O(log n).
el exponencial lo puedes “tirar a la basura” porque cuando se tenga pocos inputs que ni siquiera llegue a 100 este no te va a servir para nada (exponencial).
- O(1) Constante.
- O(n) Lineal.
- O(log n) Logarítmica.
- O(n log n) log lineal.
- O(n**2) Polinomial.
- O(2**n) Exponencial.
Ejemplos de algoritmos de O(1), O(log n), O(n) y O(n^2) ordenados respecto a complejidad según la cheatsheet de BigO notation.
import numpy as np
# O(1)
# Always the same because it knows where is the index
food = ['chicken', 'beef', 'rice', 'donut']
def findByIndex(food, index):
return food[index]
# O( log(n) )
def binarySearch(arr, start, end, x):
# Check base case
if end >= start:
middle = start + ((end - start) // 2)
# Search at the middle
if arr[middle] == x:
return middle
elif x < arr[middle]:
# Search at the left
return binarySearch(arr, start, middle-1, x)
else:
# Search at the right
return binarySearch(arr, middle + 1, end, x)
else:
# Element is not present in the array
return -1
# O(n)
# It depends on how large the element is
def selectedFood(food):
for objectFood in food:
print(objectFood)
# O(n^2)
# No matter what it will do n twice
array = np.array( [1,2,3,4,5] )
def bubbleSort(array):
array2 = array.copy()
for i in range( len(array2) ):
for j in range( len(array2) - 1 ):
if array2[j] > array2[j+1]:
array2[j], array2[j+1] = array2[j+1], array2[j]
return array2
if __name__ == "__main__":
arr = [30, 40, 50, 60, 70, 80, 90, 100, 110]
print( binarySearch(arr, 0, len(arr), 90) )
print( binarySearch(arr, 0, len(arr), 95) )
print( binarySearch(arr, 0, len(arr), 45) )
print( binarySearch(arr, 0, len(arr), 30) )
Big-O notation cheat sheet:
Dejo este link con un par de ejemplos ilustrativos al final. Me pareció una forma interesante de entender el concepto de Big O notation.
https://www.geeksforgeeks.org/understanding-time-complexity-simple-examples/
Mi ejercicio para BigO:
import math
class BigO:
def __init__(self, n) -> None:
self.n = n
def operar(self):
print(f'''{self.constante()},
{self.lineal()},
{self.logartimo()},
{self.log_lineal()},
{self.polinomial()},
{self.exponencial()}''')
def constante(self):
return 1
def lineal(self):
return self.n
def logartimo(self):
return math.log(self.n)
def log_lineal(self):
return self.n * math.log(self.n)
def polinomial(self):
return pow(self.n, 2)
def exponencial(self):
return math.pow(2, self.n)
def main():
diez = BigO(10)
diez.operar()
cien = BigO(100)
cien.operar()
mil = BigO(1000)
mil.operar()
if __name__ == '__main__':
main()
Clases de complejidad algorítmica
O(1) Constante.
O(n) Lineal.
O(log n) Logarítmica.
O (n log n) log lineal.
O (n**2) Polinomial.
O (2**n) Exponencial.
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?