Comlejidad




COMPLEJIDAD COMPUTACIONAL






ANÁLISIS DE ALGORITMOS

















COMPLEJIDAD COMPUTACIONAL
La complejidad computacional es una rama de la teoría de la computación, estudia de manerainherente la solución de un problema considerando todos los algoritmos posibles para resolverlo. También estudia la eficiencia de estos, los cuales se establece su efectividad, en costo de tiempo yespacio requerido, provee las herramientas para clasificar la búsqueda de un algoritmo eficiente para la solución del problema si es posible o no.
Existen unos factores que influyen en la complejidad:Tamaño del problema: magnitudes que al aumentar incrementa la complejidad del algoritmo.
Naturaleza de los datos de entrada: en función de cuales sean los datos del problema se ejecutaran o nodeterminados instrucciones de decisión y será distinto el número de iteraciones de los bucles, el problema se resolverá en más o menos tiempo.
Mejor caso
Caso promedio
Peor caso
Los problemas los podemosdividir en dos grupos
Problemas decidibles: estos problemas cuentan con al menos un algoritmos para ser solucionado
Problemas indecidibles: son aquellos problemas que no se pueden resolver por unalgoritmo eficiente.




CLASE DE COMPLEJIDAD
Clase P
En esta clase se encuentran los algoritmos de complejidad polinómica(tiempo de ejecución está dado por un polinomio), se dice que son tratables en elsentido de que suelen ser abordados en la práctica. Los problemas para los que se conoce un algoritmo con esta complejidad se dice que forma parte de la clase p

Clase NP
Es el conjunto de todos losproblemas que se pueden resolver por algoritmos no determinístico, además se le pude aplicar un algoritmos de tiempo polinomico para comprobar si una posible solución es válida o no

Clase NP-completoEstos son los peores problemas posibles de la clase NP, son se extrema complejidad. Se caracteriza por ser todos iguales. Además es imposible de encontrar un una solución óptima. Esta clase se basa...