【数据结构与算法】-空间复杂度

空间复杂度概述

空间复杂度是衡量算法在运行过程中临时占用存储空间大小的一个重要指标。它描述了算法所需的额外存储空间与输入数据规模之间的关系。空间复杂度通常也用大O表示法（Big O notation）来表示。

常见的空间复杂度

1. O(1) - 常数空间复杂度

   • 描述：无论输入数据规模如何，算法所需的额外存储空间都是常数。
   • 示例：简单的数学运算。

     int add(int a, int b) {
         return a + b; // O(1)
     }
     

2. O(n) - 线性空间复杂度

   • 描述：算法所需的额外存储空间与输入数据规模成线性关系。
   • 示例：存储输入数组的副本。

     int[] copyArray(int[] array) {
         int[] copy = new int[array.length];
         for (int i = 0; i < array.length; i++) {
             copy[i] = array[i]; // O(n)
         }
         return copy;
     }
     

3. O(n^2) - 平方空间复杂度

   • 描述：算法所需的额外存储空间与输入数据规模的平方成正比。
   • 示例：存储二维数组。

     int[][] createMatrix(int n) {
         int[][] matrix = new int[n][n];
         for (int i = 0; i < n; i++) {
             for (int j = 0; j < n; j++) {
                 matrix[i][j] = i * j; // O(n^2)
             }
         }
         return matrix;
     }
     

4. O(log n) - 对数空间复杂度

   • 描述：算法所需的额外存储空间与输入数据规模的对数成正比。
   • 示例：递归调用栈的深度。

     int binarySearch(int[] array, int target, int left, int right) {
         if (left > right) return -1;
         int mid = left + (right - left) / 2;
         if (array[mid] == target) return mid;
         else if (array[mid] < target) return binarySearch(array, target, mid + 1, right);
         else return binarySearch(array, target, left, mid - 1); // O(log n)
     }
     

5. O(n log n) - 线性对数空间复杂度

   • 描述：算法所需的额外存储空间与输入数据规模的对数成线性关系。
   • 示例：归并排序的辅助数组。

     void mergeSort(int[] array, int[] temp, int left, int right) {
         if (left < right) {
             int mid = left + (right - left) / 2;
             mergeSort(array, temp, left, mid);
             mergeSort(array, temp, mid + 1, right);
             merge(array, temp, left, mid, right); // O(n log n)
         }
     }
     
     void merge(int[] array, int[] temp, int left, int mid, int right) {
         // 合并过程
     }
     

更复杂的空间复杂度分析

在实际应用中，有些算法的空间复杂度可能涉及多个因素，例如递归调用栈、动态分配的内存、缓存等。以下是一些更复杂的空间复杂度分析示例：

1. 递归调用栈

递归算法的空间复杂度不仅包括显式分配的内存，还包括递归调用栈的深度。

示例：递归计算斐波那契数列

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2); // O(n) 空间复杂度
}

• 分析：
  • 每次递归调用都会在调用栈中占用一定的空间。
  • 最深的递归调用栈深度为 n，因此空间复杂度为 O(n)。

2. 动态规划

动态规划算法通常需要额外的存储空间来保存中间结果，以避免重复计算。

示例：动态规划求解斐波那契数列

int fibonacci(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n]; // O(n) 空间复杂度
}

• 分析：
  • 使用一个长度为 n + 1 的数组 dp 来保存中间结果。
  • 因此，空间复杂度为 O(n)。

3. 多维数组

多维数组的使用会显著增加空间复杂度。

示例：二维动态规划求解最长公共子序列

int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length();
    int n = text2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n]; // O(m * n) 空间复杂度
}

• 分析：
  • 使用一个 (m + 1) x (n + 1) 的二维数组 dp 来保存中间结果。
  • 因此，空间复杂度为 O(m * n)。

4. 缓存和哈希表

缓存和哈希表的使用也会增加空间复杂度。

示例：缓存斐波那契数列

import java.util.HashMap;
import java.util.Map;

Map<Integer, Integer> cache = new HashMap<>();

int fibonacci(int n) {
    if (n <= 1) return n;
    if (cache.containsKey(n)) return cache.get(n);

    int result = fibonacci(n - 1) + fibonacci(n - 2);
    cache.put(n, result);
    return result; // O(n) 空间复杂度
}

• 分析：
  • 使用一个哈希表 cache 来缓存已经计算过的斐波那契数。
  • 在最坏情况下，哈希表的大小为 n，因此空间复杂度为 O(n)。

5. 图的遍历

图的遍历算法（如深度优先搜索和广度优先搜索）通常需要额外的空间来记录访问状态。

示例：深度优先搜索

import java.util.*;

void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {
    if (visited.contains(node)) return;
    visited.add(node);
    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        dfs(graph, neighbor, visited);
    }
}

void traverseGraph(Map<Integer, List<Integer>> graph) {
    Set<Integer> visited = new HashSet<>();
    for (int node : graph.keySet()) {
        if (!visited.contains(node)) {
            dfs(graph, node, visited);
        }
    } // O(V + E) 空间复杂度
}

• 分析：
  • 使用一个集合 visited 来记录访问过的节点。
  • 在最坏情况下，集合的大小为 V（顶点数），递归调用栈的深度为 E（边数），因此空间复杂度为 O(V + E)。

总结

• 递归调用栈：考虑递归调用栈的深度。
• 动态规划：考虑中间结果的存储空间。
• 多维数组：考虑多维数组的大小。
• 缓存和哈希表：考虑缓存和哈希表的大小。
• 图的遍历：考虑访问状态记录和递归调用栈的大小。