算法空间复杂度优化技巧：滚动数组与状态压缩

xiaoshi 05-30 9 抢沙发

默认

摘要： ...

算法优化利器：滚动数组与状态压缩实战技巧

在算法设计与优化领域，空间复杂度常常成为制约程序性能的关键因素。本文将深入探讨两种高效的空间优化技术——滚动数组与状态压缩，帮助开发者在不牺牲时间效率的前提下，显著降低内存消耗。

为什么需要空间优化？

现代软件开发中，处理大规模数据已成为常态。当算法面对海量输入时，内存使用不当可能导致程序崩溃或性能急剧下降。特别是在移动设备和嵌入式系统中，内存资源更为有限，空间优化显得尤为重要。

空间优化不仅能减少内存占用，还能带来其他好处：减少缓存未命中、降低垃圾回收压力、提高数据局部性。这些因素综合作用，往往能带来意想不到的性能提升。

滚动数组：时间维度的空间优化

滚动数组是一种通过重复利用存储空间来降低空间复杂度的技术。其核心思想是：在动态规划等需要存储多阶段状态的算法中，识别出那些不再需要的旧状态，及时释放或重用它们占用的空间。

经典应用场景

斐波那契数列计算是理解滚动数组的绝佳例子。传统递归方法时间复杂度为O(2^n)，而动态规划方法可以优化到O(n)时间复杂度和O(n)空间复杂度：

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

观察发现，计算fib(i)只需要fib(i-1)和fib(i-2)两个前驱状态。因此，我们可以将空间复杂度优化到O(1)：

def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

二维问题的滚动优化

滚动数组在二维动态规划问题中同样大放异彩。考虑经典的背包问题，传统解法需要O(nW)空间：

def knapsack(values, weights, W):
    n = len(values)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

使用滚动数组优化后，空间复杂度降为O(W)：

def knapsack(values, weights, W):
    n = len(values)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
    return dp[W]

注意内层循环需要逆向遍历，以避免覆盖还未使用的前驱状态。

状态压缩：信息维度的空间优化

状态压缩是另一种强大的空间优化技术，特别适用于状态本身包含冗余信息的情况。它通过精妙的数据表示方式，减少存储每个状态所需的空间。

位运算的艺术

位操作是状态压缩的核心工具。考虑著名的N皇后问题，传统回溯算法需要维护多个二维数组来标记攻击范围。而通过位运算，我们可以将整个棋盘状态压缩到一个整数中：

def totalNQueens(n):
    def backtrack(row, cols, diags, anti_diags):
        if row == n:
            return 1
        count = 0
        for col in range(n):
            curr_diag = row - col
            curr_anti_diag = row + col
            if (cols & (1 << col)) or (diags & (1 << curr_diag)) or (anti_diags & (1 << curr_anti_diag)):
                continue
            cols |= 1 << col
            diags |= 1 << curr_diag
            anti_diags |= 1 << curr_anti_diag
            count += backtrack(row + 1, cols, diags, anti_diags)
            cols ^= 1 << col
            diags ^= 1 << curr_diag
            anti_diags ^= 1 << curr_anti_diag
        return count
    return backtrack(0, 0, 0, 0)

这种方法将空间复杂度从O(n²)降到了O(1)，仅使用几个整数就表示了整个棋盘状态。

集合的压缩表示

状态压缩还常用于处理集合操作。比如在旅行商问题(TSP)中，我们需要记录已经访问过的城市集合。传统方法可能使用数组或哈希表，而状态压缩则使用位掩码：

def tsp(dist):
    n = len(dist)
    memo = [[float('inf')] * n for _ in range(1 << n)]
    memo[1][0] = 0  # 从城市0出发，只访问过城市0

    for mask in range(1 << n):
        for last in range(n):
            if not (mask & (1 << last)):
                continue
            prev_mask = mask ^ (1 << last)
            for prev in range(n):
                if prev == last or not (prev_mask & (1 << prev)):
                    continue
                memo[mask][last] = min(memo[mask][last], memo[prev_mask][prev] + dist[prev][last])

    # 返回所有城市都访问过，最后回到起点0的最短路径
    return min(memo[(1 << n) - 1][last] + dist[last][0] for last in range(1, n))

这种方法将集合操作转化为位运算，极大提高了效率。

实战中的组合应用

滚动数组和状态压缩经常可以组合使用，产生更强大的优化效果。以动态规划中的股票买卖问题为例：

给定股票每天的价格，最多进行k次交易，求最大利润。传统解法需要三维数组dp[k][i][j]，表示第i天进行第j次交易时的状态。通过滚动数组和状态压缩，可以优化到O(k)空间：

def maxProfit(k, prices):
    if not prices:
        return 0
    n = len(prices)
    if k >= n // 2:  # 相当于可以无限次交易
        return sum(max(prices[i+1] - prices[i], 0) for i in range(n-1))

    buy = [float('-inf')] * (k + 1)
    sell = [0] * (k + 1)
    for price in prices:
        for j in range(1, k + 1):
            buy[j] = max(buy[j], sell[j-1] - price)
            sell[j] = max(sell[j], buy[j] + price)
    return sell[k]

这里，滚动数组优化了天数维度，而状态压缩则简化了交易次数的表示。