Complejidad Computacional

COMPLEJIDAD COMPUTACIONAL

El primer paso para resolver un problema informático es encontrar un algoritmo que lo resuelva. Pero una vez resuelto el problema, nos surgen las siguientes dudas: ¿Exisiten algoritmos "mejores" para resolver el problema?
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.Podríamos decir que algoritmo, es una sucesión finita de operaciones elementales, que sabemos ejecutar cuando actua sobre una serie de datos. Un algoritmo, será mejor que otro en tiempo si, actuando sobre los mismos datos, el tiempo de ejecución es menor, y será mejor que otro en espacio si, actuando sobre los mismos datos, la memoria, principal o secundaria,que utilza es menor. Pero, tanto el tiempo como el espacio utilizado dependen de la máquina en la que ejecutemos el algoritmo, por tanto hay que determinar una forma para estudiar la eficiencia de los algoritmos independiente de la máquina que se utilice.

COMPLEJIDAD TEMPORAL

Se denomina complejidad temporal a la función T(n) que mide el número de instrucciones realizadas por el algoritmopara procesar los n elementos de entrada.
Cada instrucción tiene asociado un costo temporal.

Afecta al tiempo de ejecución el orden en que se procesen los elementos de entrada.
Podría considerarse que los valores de los n casos que se presentan como entrada son los correspondientes: a un caso típico, o a un caso promedio, o de peor caso. El peor caso es el más sencillo de definir (el quedemore más para cualquier entrada), pero si se desea otros tipos de entrada habría que definir qué se considera típico, o la distribución de los valores en el caso promedio.

* ALGORITMOS LINEALES:
Son aquellos que tienen una secuencia lineal, sin salto de líneas
Ejemplo: 1. Generar 4 numeros entre 0 y 1 con los siguinetes parametros: x0= 37 a= 19 c= 33 m= 100 Solucion: 37 x1=(19*37+33)mod100= 36 r1=36/99= 0.3636 x2= (19*36+33)mod100= 17 r2=17/99= 0.1717 x3= (19*17+33)mod100= 56 r3=56/99= 0.5657 x4= (19*56+33)mod100= 97 r4=97/99= 0.9798 76 77 96 57 16 37 36 17 56 97 76 56 97

* ALGORITMOS POLINÓNMICOS Y POLIMIALES
Diremos que un algoritmo es Polinomial si su peor caso de ejecución es de orden O ( N elevado a k ),donde N es el tamaño de la entrada y k es una constante. Seconsideran eficientes.
Función de tiempo tiene un orden O(n elevado x)
Ejemplo: f(n) = 2 n2, o bien g(n) = 8 n2 + 5

* ALGORITMOS EXPONENCIALES
Aquellos que son proporcionales a kN. En general son infactibles salvo un tamaño de entrada muy reducido. Los problemas de tiempo de ejecución exponencial no suelen ser muy útiles en la práctica por el elevadísimo tiempo de ejecución. El problema dela mochila resuelto por un algoritmo de fuerza bruta -simple vuelta atrás- es un ejemplo. Si N se duplica, el tiempo de ejecución se eleva al cuadrado.
Función de tiempo tiene un orden O(X elevado n)
Ejemplo: 3x2+9x+10=0

* CLASES P Y NP
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 quecorresponde 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, uncamino 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.
Ejemplo P: Algunos problemas naturales son completos para P, incluyendo la conectividad (o la accesibilidad) en grafos no dirigidos.
Una generalización de P es NP, que es la clase de lenguajes decidibles en tiempo...