complejidad compuatacional

Complejidad computacional
La complejidad computacional estudia la eficiencia de los algoritmos estableciendo la efectividad de estos basándose en el tiempo de ejecución así como el espaciorequerido en la computadora o almacenamiento de datos, y así poder evaluar y deducir su implementación practica en el tiempo y el costo.
Además este provee herramientas para clasificar la dificultadinherente de un problema, de esta manera se puede conocer previamente si la búsqueda que se hace a partir de un algoritmo es eficiente para la solución de dicho problema o si este es posible o no.
Una de lascosas importantes que se deben tener en cuenta al momento de seleccionar un algoritmo es el tiempo en que este va a tardar en arrojar una salida.
La mayoría de los problemas ocurren como problemasde optimización combinatoria en donde su dominio se compone de problemas de optimización donde el conjunto de posibles soluciones es discreto o se puede reducir a un conjunto discreto.
A medida quela complejidad del espacio de búsqueda aumenta, el coste de ejecución de dichos algoritmos puede aumentar de forma exponencial, convirtiendo la solución en prácticamente inviable.
La complejidad espuesta en práctica en tres casos (Mejor, Promedio, Peor).
COMPLEJIDAD DE MEJOR DE LOS CASOS: Se entiende que es el menor número de operaciones necesarias para resolver un problema.
COMPLEJIDAD DELPROMEDIO DE LOS CASOS: Se entiende que es el promedio del número de operaciones necesarias para resolver un problema.
COMPLEJIDAD DEL PEOR LOS CASOS: Se entiende que es el mayor número de operacionesnecesarias para resolver un problema.
La complejidad computacional tiene ligada una serie de problemas de decisión los cuales están reflejados en base a ciertos criterios los cuales están basados en lateoría de la computabilidad en donde se plantea si un problema es (Decidible, No decible, Parcialmente decidible).
DECIDIBLE: Un problema es decidible si existe un procedimiento mecánico que lo...