complejidad computacional espacial

Vista previa del material en texto

COMPLEJIDAD COMPUTACIONAL ESPACIAL
UNIVERSIDAD PRIVADA DEL NORTE
INGENIERÍA DE SISTEMAS COMPUTACIONALES
TRUJILLO - PERÚ
ING. INFORMATICO: MITCHELL BLANCAS
Palabras Clave. Complejidad Espacial, memoria estática y memoria dinámica.
1. Complejidad Espacial. 
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 requisitos para ejecutarlo es decir, el espacio en memoria que ocupan todas las variables propias del algoritmo.
Sin embargo, resulta casi imposible conocer el tamaño del programa en memoria pues depende del lenguaje y arquitectura del computador, así pues nos limitamos a cuantificar el espacio en memoria requerido para almacenar los datos.
Existen 4 aspectos relevantes a considerar
· La cantidad de memoria requerida por el código del algoritmo.
· La cantidad de memoria requerida para almacenar los datos de entrada.
· La cantidad de memoria requerida para los datos de salida (algoritmos como los de ordenación suelen reorganizar los datos de entrada y por ello no necesitan memoria extra para la salida).
· La cantidad de memoria requerida en cuanto a espacio de trabajo del algoritmo para realizar los cálculos y asignaciones (tanto para variables como cualquier espacio necesario en la pila para almacenar llamadas a subrutinas, este espacio es particularmente significativo para algoritmos que utilizan técnicas recursivas)
Las primeras computadoras electrónicas y computadoras de escritorio, contaban con muy poca capacidad de memoria operativa. E.g la EDSAC 1949 tenía un máximo de 1024 17-bit words, mientras que la SinclairZX80 1980 sugirió con solo 1024 8-bit bytes de memoria operativa.
Las computadoras actuales cuentan con una memoria suficientemente grande de 16 GB y más, o sea que obliga a un algoritmo a ejecutarse reducidamente en cierta cantidad de memoria ya no representa el mismo problema que solía ser.
Pero la presencia de tres categorías diferentes de memoria pudiera ser significativa: 
· Memoria caché (usualmente RAM-estática): esta opera a una velocidad comparable a la del CPU.
· Memoria física principal (usualmente RAM-dinámica): esta opera un tanto más lenta que el CPU.
· Memoria virtual (usualmente en disco): esta da la impresión de una cantidad de memoria utilizable y opera en el orden de los miles más lenta que el CPU.
Ejemplo.- ALGORITMOS DE BÚSQUEDA EN ÁRBOLES.
· Función búsqueda_árboles. 
· Devuelve una solución o fallo.
· Inicializar un árbol de búsqueda con estado inicial.
Bucles hacer
· Si no hay candidatos para expandir.
· Entonces devolver fallo.
· En otro caso escoger nodo para expandir.
· Si el nodo es el objetivo.
· Entonces devolver solución.
· En otro caso expandir nodo.
M = profundidad máxima del árbol (puede ser infinita)
D = profundidad de la mejor solución (menor costo)
B = factor de ramificación (número máximo de sucesiones) = 10
Un algoritmo cuyas necesidades pueden ser satisfechas con la memoria caché será mucho más rápido que uno que necesite de la memoria principal y en consecuencia mucho más rápido que uno que necesita recurrirá la memoria virtual. Si se quiere profundizar aún más en dicho problema, existen sistemas que tienen hasta tres niveles de memoria caché, con diferentes y variadas velocidades. Sistemas diferentes tendrán diferentes cantidades asignadas a los tipos de memoria comentados, lo que conlleva a que las necesidades de memoria de un algoritmo varíen significativamente entre un sistema y otro.
La memoria que utiliza un programa para su ejecución; es decir el espacio de memoria que ocupan todas las variables propias del algoritmo se dividen en Memoria Estática y Memoria Dinámica.
1.1. Memoria Estática.
Para calcular la memoria estática, se suman la cantidad de memoria que ocupa cada una de las variables declaradas en el programa, Tomando en cuenta los tipos de datos primitivos del lenguaje de programación java podemos determinar el espacio que requiere cada una de las variables de un programa, de acuerdo a lo siguiente:
	Tipo de dato primitivo
	Tamaño en bits
	Tamaño en Bytes
	byte
char
short
int
float
long
double
	8
16
16
32
32
64
64
	1
2
2
4
4
8
8
1.2. Memoria Dinámica.
El cálculo de la memoria dinámica, no es tan simple ya que depende de cada ejecución del programa o algoritmo y el tipo de estructuras dinámicas que se estén utilizando.
 Una de las características primordiales en la selección de un algoritmo es que este sea sencillo de entender, calcular, codificar y depurar, así mismo que utilice eficientemente los recursos de la computadora y se ejecute con la mayor rapidez posible con un eficaz uso de memoria dinámica y estática.
2. Conclusiones.
· La memoria que usamos puede ser estática y dinámica según las variables que usemos y la estructura que desarrolle el algoritmo respectivamente.
· Antes de realizar un programa conviene elegir un buen algoritmo, que utilice pocos recursos, siendo usualmente los más importantes el tiempo que lleve ejecutarse y la cantidad de espacio en memoria que requiera. Es engañoso pensar que todos los algoritmos son “más o menos iguales” y confiar en nuestra habilidad como programadores para convertir un mal algoritmo en un producto eficaz.
3. Referencias. 
3.1. Bibliografía.
· Rodríguez Artalejo Mario, Gonzales Clero Pedro, Gómez Martin Marco,Estructuras de Datos. Un enfoque moderno, Primera Edición, Madrid, Editorial Complutense, 2011, 210, Volumen 1.
3.2. Webgrafia.
· Bustamante Dayana, Complejidad Espacial, [BLOG], 2008, Disponible en: http://estructuradedatosfacil.blogspot.pe/2008/09/complejidad-en-el-espacio.html 
· Apolinar Osvaldo, Analisis de los Algoritmos, [Scribd], 2011, Disponible en: https://es.scribd.com/doc/2873588/Estructura-de-datos-Antologia 
· Tutorial de Programación Multiplataforma, Análisis de Algoritmos, [TMP], 2013, Disponible en: http://itslr.edu.mx/archivos2013/TPM/temas/s3u7.html 
· Estructura de Datos , Análisis de algoritmos, [SitiesGoogle], Disponible en: https://sites.google.com/site/estdatjiq/home/unidad-vii