Complejidad
-
Upload
claudio-troncoso-ogalde -
Category
Education
-
view
107 -
download
1
description
Transcript of Complejidad
![Page 1: Complejidad](https://reader033.fdocumento.com/reader033/viewer/2022060203/559ea9f81a28abd62e8b4848/html5/thumbnails/1.jpg)
Análisis de algoritmo
Claudio Troncoso
![Page 2: Complejidad](https://reader033.fdocumento.com/reader033/viewer/2022060203/559ea9f81a28abd62e8b4848/html5/thumbnails/2.jpg)
![Page 3: Complejidad](https://reader033.fdocumento.com/reader033/viewer/2022060203/559ea9f81a28abd62e8b4848/html5/thumbnails/3.jpg)
La complejidad de un algoritmo se refleja en la dificultad del
problema
![Page 4: Complejidad](https://reader033.fdocumento.com/reader033/viewer/2022060203/559ea9f81a28abd62e8b4848/html5/thumbnails/4.jpg)
![Page 5: Complejidad](https://reader033.fdocumento.com/reader033/viewer/2022060203/559ea9f81a28abd62e8b4848/html5/thumbnails/5.jpg)
Si el recurso es espacio
Se tomara encuenta la cantidad de memoria requerida para su ejecución y como se ordenara el algoritmo
![Page 6: Complejidad](https://reader033.fdocumento.com/reader033/viewer/2022060203/559ea9f81a28abd62e8b4848/html5/thumbnails/6.jpg)
Si el recurso es Tiempo
Se asocia a la cantidad de tiempo que necesita el algoritmo para su ejecución
![Page 7: Complejidad](https://reader033.fdocumento.com/reader033/viewer/2022060203/559ea9f81a28abd62e8b4848/html5/thumbnails/7.jpg)
![Page 8: Complejidad](https://reader033.fdocumento.com/reader033/viewer/2022060203/559ea9f81a28abd62e8b4848/html5/thumbnails/8.jpg)
![Page 9: Complejidad](https://reader033.fdocumento.com/reader033/viewer/2022060203/559ea9f81a28abd62e8b4848/html5/thumbnails/9.jpg)
![Page 10: Complejidad](https://reader033.fdocumento.com/reader033/viewer/2022060203/559ea9f81a28abd62e8b4848/html5/thumbnails/10.jpg)
![Page 11: Complejidad](https://reader033.fdocumento.com/reader033/viewer/2022060203/559ea9f81a28abd62e8b4848/html5/thumbnails/11.jpg)
Mínimo de procesos para llegar a una solución
![Page 12: Complejidad](https://reader033.fdocumento.com/reader033/viewer/2022060203/559ea9f81a28abd62e8b4848/html5/thumbnails/12.jpg)
Tiempo de ejecución
Cuando los datos de entrada son grandes el tiempo de ejecución es mayor
Se denota como T(n)
![Page 13: Complejidad](https://reader033.fdocumento.com/reader033/viewer/2022060203/559ea9f81a28abd62e8b4848/html5/thumbnails/13.jpg)
Se denota por la Big-O
![Page 14: Complejidad](https://reader033.fdocumento.com/reader033/viewer/2022060203/559ea9f81a28abd62e8b4848/html5/thumbnails/14.jpg)
Complejidad Terminología
O(1) Complejidad Constante
O(n^2) Complejidad Cuadrática
O(Log n) Complejidad Logarítmica
O(n) Complejidad Lineal
O(n log n) Complejidad Casi-Lineal
O(n^b) Complejidad Poli nómica
O(b^n) Complejidad Exponencial
O(n!) Complejidad Factorial