Clases de Complejidad Algorítmica y su Impacto en el Rendimiento
Contenido del curso
Xavier Salgado
Ovidio Bolivar Jaramillo J.
Manuel Alejandro Hermoso
Miguel Torres
Ivan Ezequiel Mazzalay
Samuel Martínez Hernández
Sebastian Avendaño
Alejandro Vargas
Beder Danilo Casa Condori
Christian Armando Consuelo Mayén
Lázaro Ventancor Cressatti
Miguel Andres Rendon Reyes
Nicolas Restrepo
Karla Ivon Damian
Julián Andrés Santos Méndez
Raymundo Soto Soto
Andres Barrera Canchon
Noldia Chavez Cavero
Guillermo Dario Acosta Cabrera
Juan Manuel Roa Mejia
Guillermo Dario Acosta Cabrera
Alejandrina Lara Tovar
Italo Buitron
Mauricio Gonzalez Falcon
Nicolás Mayorga Vargas
Platzi Nauta
Fredy Mendoza Vargas
Santiago Rios Olaya
David fernando Pinzon suarez
Mateo Echavarria
Sergio Eduardo Sinuco Leon
Cesar Morales
Erick Alay
Cesar Hernández Ramírez
CRISTIAN BARBERO PÉREZ
Cesar Hernández Ramírez
Jose Flores
Nicolás Arias González
Jose Flores
Iván Frías Gil
Gerson Montenegro
""" 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()```
muy chido el codigo
Muy buen código! Gracias por el aporte
Acá el código y resultado del reto. :O
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:
Es tremendo, yo lo calcule también y me da algo así jajajaaj
Que código tan elegante, me encantó, espero llegar a programar así!! Gracias por el aporte y mucho éxito!
Wow
ni la Matriz se ve tan densa XD. 👍
interesante
Clases de complejidad algorítmica:
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
JAAJJAA parce, muy charro.
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?
No es una mala practica, hay problemas donde no hay otra opción que anidar ciclos, sin embargo, si existe algo que no sea anidado y solucione lo que estas haciendo, usalo!, esto hará que tu algoritmo sea mas rápido y eficiente.
Cuando uno usa ciclos for anidados, por ejemplo para leer los renglones y columnas que corresponden a los pixeles de una imagen , es extremandamente tardado, imagínate, leeer mil por mil renglones y columnas, equivale a un millón de pixeles. Hay que implementar otro tipo de lectura en el arreglo.
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
Genial. Muchas gracias!
Hola Noldia, gracias por el aporte. Me sirvió bastante para comprender un poco más donde aparecen estas complejidades. Sin embargo, me surge una duda y espero que tu o alguien más pueda solucionarla.
En la explicación que plantean al final de este link dicen que para un input de 1'000.000, la cantidad de comparaciones sería igual a log 2 (1'000.000) = 20 como máximo.
A lo que me surgen 2 dudas.
Espero no ser el único que le haya causado gracia la frase: y los exponenciales.. esos si ya tiralos a la basura :-)
Que sigue, necesito saberlo. Que libro es??
Pobre Opus
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.
Como se mide en un programa real??
Igual que lo hicimos en la clase pasada por medio del tiempo, al observar que se aumenta determinadas cifras se podría determinar que tipo de algoritmo es o aplicando un poco de Big O se podría despejar
Puedes usar profilers
Ojala que la funcion exponencial sea la que represente al crecimiento salarial de los programadores xD
Jajaj :'D, ya quisiéramos eso
Una pregunta, ¿El maestro al decir busqueda lineal, no se refería a la binaria? es que si no recuerdo mal, la binaria era la que dividía el posible resultado a la mitad y a la mitad hasta encontrar el valor exacto. Si estoy mal porrfavor ilustrenme
Así es Cesar, bien visto
¡Gracias!
Como se determina que un algoritmo es logarítmico? en anteriores clases entendí como son los exponenciales, polinomial y constantes, pero me gustaría saber que elementos del código hacen que un algoritmo sea logarítmico.
Normalmente los algoritmos que son de complejidad logarítmica descartan una porción de los datos de entrada en cada iteración. Uno de los ejemplos más clásicos de estos es la Búsqueda Binaria. En este algoritmo de búsqueda arrancas con una lista ordenada, verificas si el elemento que buscas es mayor o menor que el elemento que está en la posición del medio. Si es mayor, entonces descartas la primera mitad de la lista y si es menor, descartas la segunda mitad. Repitiendo estos pasos hasta encontrar tu elemento. Como en cada iteración estás trabajando con la mitad de los datos que la iteración anterior, el algoritmo tiene complejidad O(log n).
gracias, pero entonces lo importante es determinar ese rasgo característico que nos indica la complejidad, como dices de que si hay alguna parte del código que empieza colocar limites significa que este es logarítmico.
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 :-D
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'---------------------------------')
