Want to create interactive content? It’s easy in Genially!
Complejidad de tiempo python
Gabriela Lourdes Rod
Created on December 16, 2022
Start designing with a free template
Discover more than 1500 professional designs like these:
Transcript
Complejidad de tiempo en algoritmos
Complejidad de tiempo en algoritmos
EMPEZAR
Índice
¿Qué es?
Logarítmico
Tiempo constante
Otros
Lineal
Combinaciones
Cuadrático
Ejemplos
¿Qué es?
¿Recuerdas este veredicto de OmegaUp?
Es una herramienta que nos ayuda a determinar el tiempo que se tardará un algoritmo en realizar todas las operaciones indicadas.
TLE
Hoy aprenderemos por qué sucede y como resolverlo
SIGAMOS
O(1)
Tiempo constante
El tiempo de un algoritmo es constante cuando solo tenemos operaciones que se repiten una vez cada una.
SIGAMOS
O(n)
Lineal
El tiempo de un algoritmo es lineal cuando como máximo algún fragmento de su código se repite n veces.
SIGAMOS
O(n2)
Cuadrático
El tiempo de un algoritmo es cuadrático cuando como máximo algún fragmento de su código se repite un n cuadrado de veces. Usualmente lo vemos reflejado en bucles anidados.
SIGAMOS
O(nlogn)
Logarítmico
Un ejemplo de un algoritmo logarítmico es la búsqueda binaria, ya que en cada iteración, el exponente se va dividiendo entre dos. Realizando en total log2n operaciones. Otros ejemplos son las soluciones Divide & Conquer.
Cuando cada sector del código se repite un máximo de log2n de veces, nos encontramos ante un código de complejidad algorítmica.
SIGAMOS
Otros
Otras complejidades comunes son las siguientes:
O(n!)
Factorial
O(nx)
Polinómica
O(2n)
Exponencial
O(√n)
Radical
Combinaciones
A la hora de analizar algoritmos complejos, se deben revisar cada una de las partes que componen al código e ir verificando cuantas veces se repite cada operación. La complejidad total de un algoritmo es la mayor complejidad encontrada dentro del código.Analiza el siguiente código, posee complejidad O(q*N*logN)