Complejidad Computacional.La complejidad computacional estudia la eficiencia de los algoritmos estableciendo su efectividad de acuerdo al tiempo de corrida y al espacio requerido en la computadora o almacenamiento de datos, ayudando a evaluar la viabilidad de la implementacin prctica en tiempo y costo.Por otra parte, provee herramientas para clasificar la dificultad inherente de un problema, de esta manera se puede conocer previamente si la bsqueda de un algoritmo eficiente para la solucin de dicho problema es posible o no.Existen problemas que nicamente pueden resolverse utilizando un algoritmo de tiempo exponencial o incluso, puede ser que no exista algoritmo alguno, por lo cual, al tener este tipo de informacin puede optarse por la bsqueda o aplicacin de tcnicas heursticas existentes, que si bien no garantizan una solucin ptima, si pueden proporcionar una buena solucin o una aproximada.Las caractersticas principales de un algoritmo son:

Preciso y Definido. Cada paso debe ser definido en forma precisa e indicar el orden de realizacin.

Datos de entrada (input). El algoritmo recibe datos iniciales antes de su ejecucin. Datos de salida (output). El algoritmo tiene una o ms salidas, es decir, datos que tienen una relacin especfica respecto a los datos de entrada. Generalidad. Independientemente de las veces que se siga un algoritmo, se debe obtener el mismo resultado. Finito. Un algoritmo debe terminar siempre despus de un nmero finito de pasos.

Se pueden destacar diferentes problemas con base en la complejidad del algoritmo que se est utilizando en el momento e igualmente se implementan con el tiempo ya antes mencionados como (L, NL, P, P-Completo, NP, NP-Completo, NP Duro...), pero aun as unos de los ms utilizados y adems mencionados son tres, los de tipo P, de tipo NP y de tipo NP-Completo.

Tipo P Determinstico: Aquellos problemas para los que se conoce un algoritmo polinmico que los resuelve, por lo tanto puede llevarse a una respuesta ms acertada de mtodo determinstico, que el resto de problemas. Pero puede llegar el punto en el que el problema se vuelve muy extenso en donde la solucin se sale del rango de los de tipo P.Ejemplo: la suma de dos vectores A[n], B[n] y cuya suma se almacene enC[n] en cuyo tiempo de ejecucin sea de O(n).

Tipo NP No Determinstico: es contrario al de tipo p, aunque resuelva el problema en un tiempo polinmico puede que no se conozca el dato de salida o resultado as que opta por una solucin aproximada; adems de que es ms abarcado a los problemas de decisin.Ejemplo: sera el de saber si un nmero es primo ya que de cierta manera puede que no se sepa el resultado que se generara, pero aunque hace parte del tipo NP tambin se conoce que est incluido en los de P puesto que puede conocerse su resultado.

Tipo NP-Completo: es el subconjunto de los problemas de decisin en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo, todos los algoritmos conocidos para problemas NP-completos utilizan tiempo exponencial con respecto al tamao de la entrada por lo que se puede usar aproximacin, probabilidad, etc.Ejemplo: el problema de la subcadena, dado un conjunto de enteros,Existe algn subconjunto cuya suma sea exactamente cero?De {7, 3, 2, 5, 8}, la respuesta es SI, porque el subconjunto {3, 2, 5}Suma cero. Este problema es NP-completo.

Ejemplo

Problema que implementa el de tipo NP el del algoritmo de Floyd, es una implementacin del camino mnimo en donde se busca conocer el camino ms de menor costo entre dos puntos o nodos, que no se repitan nodos y que regrese al punto de partida y su implementacin es ms sencilla ya que este problema utiliza grafos para resolver este problema, aunque su crecimiento es exponencial de orden O(n^3) por la presencia del triple bucle.

Se muestra el camino ms ptimo y un camino heurstico, en comparacin, aunque el heurstico no acierta el resultado muestra un aproximado del mismo que puede o no ser factible de acuerdo a las circunstancias.

ConclusinPara terminar, se puede concluir que la complejidad computacional tiene como objetivo crear herramientas para as ver la eficiencia de un algoritmo especfico eficiencia que hable a principio del documento, tambin que la clasificacin en cuanto NP y P depende de sus condiciones cambien o no ya que un mismo problema puede ser P y NP al tiempo y todo varia por el nmero de datos que reciba, como el problema del viajero por ejemplo. y tambin puedo agregar que es de gran utilidad este porque a veces como programadores nos vemos envueltos en problemas difciles de realizar, en mi caso particular trate de convertir por as decirlo un algoritmo recursivo a programacin dinmica el cual encontr difcil eliminar 100 porciento la recursividad para ser ms exacto el algoritmo fue la funcin de ackerman que tiene como particularidad crecer muy rpido por ello puedo decir que convertir tal funcin a programacin dinmica se convirti por as decirlo en una complejidad computacional.

Webgrafa

http://www.ptolomeo.unam.mx:8080/xmlui/bitstream/handle/132.248.52.100/539/A5.pdf?sequence=5http://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_complejidad_computacional#Problemas_NP-completoshttp://www.algoritmia.net/articles.php?id=30

http://es.wikipedia.org/wiki/Problema_de_la_suma_de_subconjuntos

Anlisis de algoritmoComplejidad Computacional

Presentado por:Luis Fernando Pacheco Bertel

Dirigido a:Ing. Guillermo Hernndez

Facultad:Ciencias bsicas y arquitectura

Programa:Ingeniera de sistemas

Corporacin universitaria del caribe CECAR