Análisis de algoritmos
-
Upload
cristopher-morales-ruiz -
Category
Documents
-
view
21 -
download
0
Transcript of Análisis de algoritmos
![Page 1: Análisis de algoritmos](https://reader031.fdocumento.com/reader031/viewer/2022032502/55b97e94bb61eb010e8b466e/html5/thumbnails/1.jpg)
Análisis de AlgoritmosAutor: Arthur Morales
Docente: Pilar Pardo
26 marzo 2014
![Page 2: Análisis de algoritmos](https://reader031.fdocumento.com/reader031/viewer/2022032502/55b97e94bb61eb010e8b466e/html5/thumbnails/2.jpg)
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
![Page 3: Análisis de algoritmos](https://reader031.fdocumento.com/reader031/viewer/2022032502/55b97e94bb61eb010e8b466e/html5/thumbnails/3.jpg)
La co
mple
jidad d
e u
n A
lgoritm
o
MEDIDA
RECURSOS
ALGORITMO
![Page 4: Análisis de algoritmos](https://reader031.fdocumento.com/reader031/viewer/2022032502/55b97e94bb61eb010e8b466e/html5/thumbnails/4.jpg)
Si e
l recu
rso e
s esp
acio
…
Complejidad – Cantidad
Mem
oria
– E
jecu
ción
![Page 5: Análisis de algoritmos](https://reader031.fdocumento.com/reader031/viewer/2022032502/55b97e94bb61eb010e8b466e/html5/thumbnails/5.jpg)
Recurso Tiempo
•Tie
mp
o d
e
Eje
cució
n
![Page 6: Análisis de algoritmos](https://reader031.fdocumento.com/reader031/viewer/2022032502/55b97e94bb61eb010e8b466e/html5/thumbnails/6.jpg)
Si e
l recu
rso e
s esp
acio
…
• La complejidad se asocia a estructuras de
datos…
![Page 7: Análisis de algoritmos](https://reader031.fdocumento.com/reader031/viewer/2022032502/55b97e94bb61eb010e8b466e/html5/thumbnails/7.jpg)
Estu
dia
r su co
mporta
mie
nto
…• Datos muy Ordenados
• Datos muy Desordenados
![Page 8: Análisis de algoritmos](https://reader031.fdocumento.com/reader031/viewer/2022032502/55b97e94bb61eb010e8b466e/html5/thumbnails/8.jpg)
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
![Page 9: Análisis de algoritmos](https://reader031.fdocumento.com/reader031/viewer/2022032502/55b97e94bb61eb010e8b466e/html5/thumbnails/9.jpg)
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
![Page 10: Análisis de algoritmos](https://reader031.fdocumento.com/reader031/viewer/2022032502/55b97e94bb61eb010e8b466e/html5/thumbnails/10.jpg)
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
![Page 11: Análisis de algoritmos](https://reader031.fdocumento.com/reader031/viewer/2022032502/55b97e94bb61eb010e8b466e/html5/thumbnails/11.jpg)
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
![Page 12: Análisis de algoritmos](https://reader031.fdocumento.com/reader031/viewer/2022032502/55b97e94bb61eb010e8b466e/html5/thumbnails/12.jpg)
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
![Page 13: Análisis de algoritmos](https://reader031.fdocumento.com/reader031/viewer/2022032502/55b97e94bb61eb010e8b466e/html5/thumbnails/13.jpg)
CO
NC
LUSIÓ
N
Tamaño del Problema
Medir, calcular, ejecutar el código
Espacio – Tiempo de ejecución