• Author / Uploaded
• Denisse Pedraza

Citation preview

COMPLEJIDAD EN EL ESPACIO 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 declaradas en el algoritmo. Memoria dinámica. Su cálculo no es tan simple ya que depende de cada ejecución del algoritmo. Ejemplo: algoritmo de búsqueda en arboles. Función búsqueda_arboles. Devuelve una solución o fallo. Inicializa un árbol de búsqueda con estado inicial. Bucle 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 (numero máximo de sucesiones) = 10 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.