QUE ES LA COMPLEJIDAD DE LOS ALGORITMOS COMPUTACIONALES
La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, los recursos requeridos durante el cómputo de un algoritmo para resolver un problema. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema).
DIFERERNTES TIPOS DE COMPLEJIDAD
La complejidad temporal de un problema es el número de pasos que toma resolver una instancia de un problema, a partir del tamaño de la entrada utilizando el algoritmo más eficiente a disposición. Intuitivamente, si se toma una instancia con entrada de longitud n que puede resolverse en n² pasos, se dice que ese problema tiene una complejidad en tiempo de n². Por supuesto, el número exacto de pasos depende de la máquina en la que se implementa, del lenguaje utilizado y de otros factores. Para no tener que hablar del costo exacto de un cálculo se utiliza la notación O. Cuando un problema tiene costo en tiempo O(n²) en una configuración de computador y lenguaje dado, este costo será el mismo en todos los computadores, de manera que esta notación generaliza la noción de coste independientemente del equipo utilizado.
Los problemas de decisión se clasifican en conjuntos de complejidad comparable llamados clases de complejidad.
La clase de complejidad P es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina determinista en tiempo polinómico, lo que corresponde intuitivamente a problemas que pueden ser resueltos aún en el peor de sus casos.
La clase de complejidad NP es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina no determinista en tiempo polinómico. Esta clase contiene muchos problemas que se desean resolver en la práctica, incluyendo el problema de satisfacibilidad booleana y el problema del viajante, un camino Hamiltoniano para recorrer todos los vértices una sola vez. Todos los problemas de esta clase tienen la propiedad de que su solución puede ser verificada efectivamente.
¿COMO SE MIDE LA COMPLEJIDAD?
Un algoritmo será mas eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo.
La eficiencia de un algoritmo puede ser cuantificada con las siguientes medidas de complejidad:
Complejidad Temporal o Tiempo de ejecución: Tiempo de cómputo necesario para ejecutar algún programa.
Complejidad Espacial: Memoria que utiliza un programa para su ejecución, La eficiencia en memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo; es decir, el espacio en memoria que ocupan todas las variables propias al algoritmo. Para calcular la memoria estática de un algoritmo se suma la memoria que ocupan las variables declaradas en el algoritmo. Para el caso de la memoria dinámica, el cálculo no es tan simple ya que, este depende de cada ejecución del algoritmo.
Este análisis se basa en las Complejidades Temporales, con este fin, para cada problema determinaremos una medida N, que llamaremos tamaño de la entrada o número de datos a procesar por el programa, intentaremos hallar respuestas en función de dicha N.
El concepto exacto que cuantifica N dependerá de la naturaleza del problema, si hablamos de un array se puede ver a N como el rango del array, para una matriz, el número de elementos que la componen; para un grafo, podría ser el número de nodos o arcos que lo arman, no se puede establecer una regla para N, pues cada problema acarrea su propia lógica y complejidad.
El tiempo de Ejecución de un programa se mide en función de N, lo que designaremos como T(N).
Esta función se puede calcular físicamente ejecutando el programa acompañados de un reloj, o calcularse directamente sobre el código, contando las instrucciones a ser ejecutadas y multiplicando por el tiempo requerido por cada instrucción.
Bibliografía
http://www.monografias.com/trabajos27/complejidad-algoritmica/complejidad-algoritmica.shtml#complej
http://es.wikipedia.org/wiki/Complejidad_computacional
http://www.slideshare.net/joemmanuel/complejidad-computacional
