Introducción

La complejidad espacial de un algoritmo se refiere a la cantidad de memoria que necesita para su ejecución. Al igual que la complejidad temporal, es crucial para evaluar la eficiencia de un algoritmo, especialmente en sistemas con recursos limitados. En esta sección, aprenderemos a analizar la complejidad espacial y a entender cómo afecta el rendimiento de los algoritmos.

Conceptos Clave

Memoria Estática vs. Memoria Dinámica

Memoria Estática: La memoria que se asigna en tiempo de compilación. Ejemplos incluyen variables globales y locales.
Memoria Dinámica: La memoria que se asigna en tiempo de ejecución. Ejemplos incluyen estructuras de datos dinámicas como listas enlazadas y árboles.

Componentes de la Complejidad Espacial

Espacio de Entrada: Memoria utilizada por los datos de entrada.
Espacio Auxiliar: Memoria adicional utilizada por el algoritmo, excluyendo el espacio de entrada.

Notación Asintótica para Complejidad Espacial

Utilizamos la misma notación asintótica (O, Ω, Θ) para describir la complejidad espacial que para la temporal.

Ejemplos Prácticos

Ejemplo 1: Complejidad Espacial de un Algoritmo de Búsqueda Lineal

def busqueda_lineal(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

Análisis:

Espacio de Entrada: O(n) (donde n es el tamaño del array arr).
Espacio Auxiliar: O(1) (solo se utilizan variables i y x).

Ejemplo 2: Complejidad Espacial de un Algoritmo de Ordenamiento por Mezcla (Merge Sort)

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

Análisis:

Espacio de Entrada: O(n) (donde n es el tamaño del array arr).
Espacio Auxiliar: O(n) (debido a las sublistas L y R).

Ejercicios Prácticos

Ejercicio 1: Análisis de Complejidad Espacial de un Algoritmo de Búsqueda Binaria

def busqueda_binaria(arr, x):
    l = 0
    r = len(arr) - 1

    while l <= r:
        mid = l + (r - l) // 2

        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            l = mid + 1
        else:
            r = mid - 1

    return -1

Pregunta: ¿Cuál es la complejidad espacial de este algoritmo?

Solución:

Espacio de Entrada: O(n) (donde n es el tamaño del array arr).
Espacio Auxiliar: O(1) (solo se utilizan variables l, r, y mid).

Ejercicio 2: Análisis de Complejidad Espacial de un Algoritmo de Fibonacci Recursivo

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Pregunta: ¿Cuál es la complejidad espacial de este algoritmo?

Solución:

Espacio de Entrada: O(1) (solo se utiliza la variable n).
Espacio Auxiliar: O(n) (debido a la profundidad de la pila de llamadas recursivas).

Resumen

En esta sección, hemos aprendido sobre la complejidad espacial y cómo analizarla. Hemos visto ejemplos prácticos y realizado ejercicios para reforzar los conceptos. La comprensión de la complejidad espacial es esencial para diseñar algoritmos eficientes, especialmente en sistemas con recursos limitados. En la siguiente sección, exploraremos los diferentes casos de complejidad: mejor, peor y promedio.

Análisis de Complejidad Espacial

Introducción

Conceptos Clave

Memoria Estática vs. Memoria Dinámica

Componentes de la Complejidad Espacial

Notación Asintótica para Complejidad Espacial

Ejemplos Prácticos

Ejemplo 1: Complejidad Espacial de un Algoritmo de Búsqueda Lineal

Ejemplo 2: Complejidad Espacial de un Algoritmo de Ordenamiento por Mezcla (Merge Sort)

Ejercicios Prácticos

Ejercicio 1: Análisis de Complejidad Espacial de un Algoritmo de Búsqueda Binaria

Ejercicio 2: Análisis de Complejidad Espacial de un Algoritmo de Fibonacci Recursivo

Resumen

Curso de Análisis y Diseño de Algoritmos

Módulo 1: Introducción a los Algoritmos

Módulo 2: Análisis de Algoritmos

Módulo 3: Estrategias de Diseño de Algoritmos

Módulo 4: Algoritmos Clásicos

Módulo 5: Optimización de Algoritmos

Módulo 6: Prácticas y Ejercicios