Teoria de la complejidad computacional

Introducción
El presente trabajo tiene como objetivo determinar cómo se ha de medir la complejidad de un algoritmo, de forma que sea posible compararlo con otros que resuelven el mismo problema y decidir cuál de todos ellos es más eficiente. Dicha complejidad viene dada por los recursos que consume del computador, tiempo del procesador y espacio de memoria necesarios para ejecutar elalgoritmo. Un algoritmo será tanto más eficiente cuantos menos recursos consuma. Un computador rápido no es suficiente si no se dispone de un algoritmo eficiente.
No obstante, la eficiencia suele contraponerse a la claridad del código, es decir, una mayor eficiencia suele suponer una menor comprensibilidad de éste. Además, un algoritmo eficiente requiere un mayor tiempo de desarrollo. Por tanto, es mejordesarrollar rápidamente en primer lugar un algoritmo claro, aunque sea ineficiente, y optimizarlo posteriormente.
La complejidad de un algoritmo se cuantifica con las medidas de complejidad, Complejidad temporal, tiempo de ejecución del algoritmo; Complejidad espacial, espacio de memoria que consume el algoritmo al ejecutarse.-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Teoría de la complejidad Computacional
La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, la complejidad inherente a la resolución de un problema computable. 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). Se pueden estudiar igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo. La teoría de la complejidad difiere de la teoría de lacomputabilidad en que ésta se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello.
Los problemas que tienen una solución con orden de complejidad lineal son los problemas que se resuelven en un tiempo que se relaciona linealmente con su tamaño.
Hoy en día las computadoras resuelven problemas mediante algoritmos que tienen comomáximo una complejidad o coste computacional polinómico, es decir, la relación entre el tamaño del problema y su tiempo de ejecución es polinómica. Éstos son problemas agrupados en la clase P. Los problemas que no pueden ser resueltos por nuestras computadoras (las cuales son Máquinas Determinísticas), que en general poseen costes factorial o combinatorio pero que podrían ser procesados por unamáquina no-determinista, están agrupados en la clase NP. Estos problemas no tienen una solución práctica, es decir, una máquina determinística (como una computadora actual) no puede resolverlos en un tiempo razonable.
Un problema dado puede verse como un conjunto de preguntas relacionadas, donde cada pregunta se representa por una cadena de caracteres de tamaño finito. Por ejemplo, el problemafactorización entera se describe como: Dado un entero escrito en notación binaria, retornar todos los factores primos de ese número. Una pregunta sobre un entero específico se llama una instancia. Por ejemplo, "Encontrar los factores primos del número 15" es una instancia del problema factorización entera.
La complejidad temporal de un problema es el número de pasos que toma resolver una instancia deun 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....