Complejidad

INTRODUCCION

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 la computabilidad 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 como má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 una má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.

DESARROLLO

COMPLEJIDAD EN EL TIEMPO

Para tener una medida del tiempo de ejecución de un programa, se debe pensar en los factores que tienen influencia en dicho valor.

• Velocidad de procesamiento.

• El compilador utilizado (calidad del código generado).

• Esta función se puede medir físicamente (ejecutando el programa, reloj en mano), o calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción.

• Así, un trozo sencillo de programa como:

• S1; for (int i= 0; i < N; i++) S2;

• requiere

• T(N)= t1 + t2*N

• siendo t1 el tiempo que lleve ejecutar la serie “S1” de sentencias, y t2 el que lleve la serie “S2”.

• Prácticamente todos los programas reales incluyen alguna sentencia condicional, haciendo que las sentencias efectivamente ejecutadas dependan de los datos concretos que se le presenten.

• Esto hace que mas que un valor T(N) debamos hablar de un rango de valores

• Tmin(N) ⇐ T(N) ⇐ Tmax(N)

• los extremos son habitualmente conocidos como “caso peor” y “caso mejor”.

• Entre ambos se hallara algun “caso promedio” o más frecuente.

• Cualquier fórmula T(N) incluye referencias al parámetro N y a una serie de constantes “Ti” que dependen de factores externos al algoritmo como pueden ser la calidad del código generado por el compilador y la velocidad de ejecución de instrucciones del ordenador que lo ejecuta.

EJEMPLO

*Codigo para crear un intervalo de tiempo

*Un proceso simple pero útil

import java.

class tiempo

{

InputStreamReader isr = new InputStreamReader(System.in);

BufferedReader br = new BufferedReader(isr);

public static void main(String args[]) throws IOException

{

long milisegundosactuales,milisegundos;

int tiempo = 0;

milisegundosactuales = System.currentTimeMillis();Variable para obtener el tiempo al abrir el programa

boolean evento = false;

while(true)

{

evento = false;Booleano para no tener que repetir código y poder maracar eventos relacionados con el tiempo

milisegundos = System.currentTimeMillis();Método para obtener el tiempo actual

if (milisegundosactuales == milisegundos)

{

milisegundosactuales = milisegundos + 1000;1000 milisegundos = 1 segundo

tiempo++;

System.out.println(tiempo);

evento = true;

System.out.println(evento);

}

else if((milisegundosactuales + 1000) < milisegundos)Metodo para evitar que se detenga el contador

milisegundosactuales = System.currentTimeMillis();

}

}

}

COMPLEJIDAD EN ESPACIO

La misma idea que se utiliza para medir la complejidad en tiempo de un algoritmo se utiliza para medir su complejidad en espacio. Decir que un programa es O( N ) en espacio significa que sus requerimientos de memoria aumentan proporcionalmente con el tamaño del problema. Esto es, si el problema se duplica, se necesita el doble de memoria. Del mismo modo, para un programa de complejidad O( N2 ) en espacio, la cantidad de memoria que se necesita para almacenar los datos crece con el cuadrado del tamaño del problema: si el problema se duplica, se requiere cuatro veces más memoria. En general, el cálculo de la complejidad en espacio de un algoritmo es un proceso sencillo que se realiza mediante el estudio de las estructuras de datos y su relación con el tamaño del problema.

El problema de eficiencia de un programa se puede plantear como un compromiso entre el tiempo y el espacio utilizados. En general, al aumentar el espacio utilizado para almacenar la información, se puede conseguir un mejor desempeño, y, entre más compactas sean las estructuras de datos, menos veloces resultan los algoritmos. Lo mismo sucede con el tipo de estructura de datos que utilice un programa, puesto que cada una de ellas lleva implícitas unas limitaciones de eficiencia para sus operaciones básicas de administración. Por eso, la etapa de diseño es tan importante dentro del proceso de construcción de software, ya que va a determinar en muchos aspectos la calidad del producto obtenido.

• Es la memoria que utiliza un programa para su ejecución. Lo que implica que la eficiencia en memoria de un algoritmo lo indica la cantidad de espacio requerido para ejecutarlo, es decir, el espacio memoria que ocupan todas las variables propias del algoritmo.

• Es la memoria que utiliza un programa para su ejecución; es decir, el espacio de memoria que ocupan todas las variables propias del algoritmo.

Esta se divide en Memoria Estática y Memoria Dinámica.

• Memoria estática. Para calcularla se suma de memoria que ocupan las variables

...