Ensamblador

Teoría de la complejidad computacional.
¿Qué es?
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 laresolució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 elespacio (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 pararesolver el problema en paralelo. La teoría de la complejidad difiere de la teoría de la computabilidad en que ésta se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomaren cuenta los recursos necesarios para ello.
Notación.
Existen diferentes notaciones para la complejidad asintótica.Una de ellas es la notación O, que permite especificar la cota superior de laejecución de un algoritmo.
La sentencia “f(n) es O(g(n))” significa que la tasa de crecimiento de f(n) no es mayor que la tasa de crecimiento de g(n).La notación “O” sirve para clasificar las funcionesde acuerdo con su tasa de crecimiento.
Ejemplo: la función n2 no es O(n)
n2  cn
n  c
La desigualdad anterior no puede
satisfacerse porque c
debe ser una constante



Ejemplos.
Unproblema 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 problema factorización entera sedescribe 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 losfactores 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 de un problema, a partir...