Análisis de AlgoritmosAutor: Arthur Morales
Docente: Pilar Pardo
26 marzo 2014
Se expresa en función del tamaño del problema que se desea resolver.
¿Qu
é e
s com
ple
jidad
de u
n a
lgoritm
o?
Tamaño
Problema
La co
mple
jidad d
e u
n A
lgoritm
o
MEDIDA
RECURSOS
ALGORITMO
Si e
l recu
rso e
s esp
acio
…
Complejidad – Cantidad
Mem
oria
– E
jecu
ción
Recurso Tiempo
•Tie
mp
o d
e
Eje
cució
n
Si e
l recu
rso e
s esp
acio
…
• La complejidad se asocia a estructuras de
datos…
Estu
dia
r su co
mporta
mie
nto
…• Datos muy Ordenados
• Datos muy Desordenados
Com
ple
jidad…
• Peor Caso
Cantidad de operaciones
para garantizar una solución
• Caso Promedio
Promedio de operaciones con un tamaño determinado
• Tiempo de Ejecución T(n)
Medir, calcular, ejecutar el código
Nota
ción A
sintó
tica• Algoritmo aplicado
a grandes problemas
Algoritm
o aplicado a
pequeños problemas
N tiende a infinito = Comportamiento Asintótico
Se co
nsid
era
n fu
ncio
nes
asin
tótica
mente
no n
egativa
Se denomina Asintótica por medio de una función de los números naturales N.
Parte de Tiempo de ejecución a Espacio de Memoria de los Algoritmos
La complejidad del Algoritmo se denota como Big-O
Big-O
Complejidad
de algoritmo
Ord
en d
e
Com
ple
jidad
Identificación de familias de funciones.
Conjunto de funciones que comparten un mismo comportamiento asintótico
Orden de Complejidad O
Orden de
Complejidad
O
Com
ple
jidad y
Term
inolo
gía
Complejidad Terminología O(1) Complejidad constante O(n2) Complejidad cuadrática O(log n) Complejidad logarítmica O(n) Complejidad lineal O(n log n) Complejidad casi-lineal O(n^b) Complejidad polinómica O(b^n) Complejidad exponencial O(n!) Complejidad factorial
CO
NC
LUSIÓ
N
Tamaño del Problema
Medir, calcular, ejecutar el código
Espacio – Tiempo de ejecución