算法的空间复杂度：你的算法"吃"多少内存？

一、先来个生活比喻

想象你要整理房间：

1. 原地整理（O(1)）：就在原地整理，不需要额外空间
2. 借个桌子（O(n)）：需要借一张和物品数量成比例的桌子
3. 租个仓库（O(n²)）：需要按物品的平方比例租空间

二、空间复杂度到底是什么？

简单说：你的算法运行时需要多少额外内存

三、C#代码直观感受

1. O(1) - 常数空间（最省内存）

// 求数组中的最大值
int FindMax(int[] numbers)
{
    // 只用了固定几个变量，与数组大小无关
    int max = numbers[0];        // 1个变量
    int index = 0;               // 1个变量
    
    for (int i = 1; i < numbers.Length; i++)  // i是1个变量
    {
        if (numbers[i] > max)
        {
            max = numbers[i];
            index = i;
        }
    }
    // 总共：3个变量，与数组长度无关
    // 空间复杂度：O(1)
}

2. O(n) - 线性空间（常见）

// 复制一个数组（需要同样大小的新数组）
int[] CopyArray(int[] original)
{
    int[] copy = new int[original.Length];  // 创建新数组，大小与原数组相同
    
    for (int i = 0; i < original.Length; i++)
    {
        copy[i] = original[i];
    }
    // 空间复杂度：O(n) - 因为创建了新数组
    return copy;
}

// 反转字符串（创建新数组）
string ReverseString(string input)
{
    char[] chars = new char[input.Length];  // 创建新数组
    
    for (int i = 0; i < input.Length; i++)
    {
        chars[i] = input[input.Length - 1 - i];
    }
    // 空间复杂度：O(n)
    return new string(chars);
}

3. O(n²) - 平方空间（很占内存）

// 生成所有两两组合（存储所有组合）
List<(int, int)> GetAllPairs(int[] numbers)
{
    List<(int, int)> pairs = new List<(int, int)>();
    
    for (int i = 0; i < numbers.Length; i++)
    {
        for (int j = 0; j < numbers.Length; j++)
        {
            pairs.Add((numbers[i], numbers[j]));  // 添加所有组合
        }
    }
    // 存储n²个组合
    // 空间复杂度：O(n²)
    return pairs;
}

四、空间复杂度 vs 时间复杂度

using System;

class SpaceComplexityDemo
{
    // 方案1：省空间但费时间
    void FindDuplicates_SpaceEfficient(int[] numbers)
    {
        // 空间复杂度：O(1) - 只用了几个变量
        // 时间复杂度：O(n²) - 双重循环，很慢
        
        for (int i = 0; i < numbers.Length; i++)      // O(n)
        {
            for (int j = i + 1; j < numbers.Length; j++)  // O(n)
            {
                if (numbers[i] == numbers[j])
                {
                    Console.WriteLine($"重复: {numbers[i]}");
                }
            }
        }
    }
    
    // 方案2：省时间但费空间
    void FindDuplicates_TimeEfficient(int[] numbers)
    {
        // 空间复杂度：O(n) - 需要哈希表
        // 时间复杂度：O(n) - 很快
        
        HashSet<int> seen = new HashSet<int>();  // 需要额外O(n)空间
        
        foreach (int num in numbers)  // O(n)
        {
            if (seen.Contains(num))   // O(1)查找
            {
                Console.WriteLine($"重复: {num}");
            }
            else
            {
                seen.Add(num);        // O(1)添加
            }
        }
    }
}

五、实际内存占用对比

using System;
using System.Collections.Generic;

class MemoryComparison
{
    static void Main()
    {
        Console.WriteLine("不同空间复杂度算法的内存占用对比\n");
        
        // 假设每个整数占4字节
        int[] smallArray = new int[100];      // 400字节
        int[] mediumArray = new int[1000];    // 4KB
        int[] largeArray = new int[10000];    // 40KB
        
        Console.WriteLine("测试数据大小：");
        Console.WriteLine($"小数组：100个元素 ≈ {100 * 4}字节");
        Console.WriteLine($"中数组：1000个元素 ≈ {1000 * 4}字节");
        Console.WriteLine($"大数组：10000个元素 ≈ {10000 * 4}字节");
        
        Console.WriteLine("\n不同算法的空间需求：");
        
        // O(1) - 常数空间
        Console.WriteLine("\n1. O(1) - 常数空间：");
        Console.WriteLine("   无论数据多大，只使用固定几个变量");
        Console.WriteLine("   例如：max = numbers[0];  // 4字节");
        Console.WriteLine("         count = 0;         // 4字节");
        Console.WriteLine("   总共：~20字节");
        
        // O(n) - 线性空间  
        Console.WriteLine("\n2. O(n) - 线性空间：");
        Console.WriteLine("   复制数组：需要同样大小的空间");
        Console.WriteLine($"   小数组：需要 {100 * 4}字节的副本");
        Console.WriteLine($"   大数组：需要 {10000 * 4}字节的副本");
        
        // O(n²) - 平方空间
        Console.WriteLine("\n3. O(n²) - 平方空间（危险！）：");
        Console.WriteLine("   存储所有两两组合：");
        Console.WriteLine($"   小数组(100)：需要存储 {100 * 100} = 10,000个组合");
        Console.WriteLine($"   每个组合8字节 → 约 {10000 * 8}字节 ≈ 80KB");
        Console.WriteLine($"   大数组(10000)：需要 {10000 * 10000} = 100,000,000个组合");
        Console.WriteLine($"   约 {100000000 * 8}字节 ≈ 800MB！（可能内存溢出）");
        
        Console.WriteLine("\n⚠️ 注意：手机应用通常限制100-200MB内存");
        Console.WriteLine("⚠️ O(n²)算法在大数据时容易崩溃");
    }
}

六、如何快速判断空间复杂度？

看创建了多大的数据结构：

// O(1)：只用了固定大小的变量
int a = 10;                     // 1个int
int b = 20;                     // 1个int
// 总共：2个int，与输入无关

// O(n)：创建了和输入大小相关的数据结构
int[] copy = new int[array.Length];      // 大小与array相同
List<int> list = new List<int>(n);       // 容量为n

// O(n²)：创建了二维结构
int[,] matrix = new int[n, n];           // n×n矩阵
List<List<int>> grid = new List<List<int>>();
for (int i = 0; i < n; i++)              // n个列表
{
    grid.Add(new List<int>(n));          // 每个列表容量n
}

七、空间优化技巧

// 技巧1：原地操作（修改原数组，不创建副本）
void ReverseArrayInPlace(int[] array)
{
    // O(1)空间，O(n)时间
    int left = 0;
    int right = array.Length - 1;
    
    while (left < right)
    {
        // 原地交换，不需要额外数组
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
        
        left++;
        right--;
    }
}

// 技巧2：流式处理（一次处理一点，不全部加载）
void ProcessLargeFile(string filePath)
{
    // 使用StreamReader，一次只读一行
    using (var reader = new StreamReader(filePath))
    {
        string line;
        while ((line = reader.ReadLine()) != null)  // O(1)空间
        {
            ProcessLine(line);  // 处理当前行
        }
    }
    // 即使文件10GB，内存也只占用很少
}

// 技巧3：重用对象池
class ObjectPool<T> where T : new()
{
    private Queue<T> pool = new Queue<T>();
    
    public T Get()
    {
        if (pool.Count > 0)
            return pool.Dequeue();  // 重用现有对象
        else
            return new T();         // 必要时创建
    }
    
    public void Return(T obj)
    {
        pool.Enqueue(obj);          // 放回池中
    }
}

八、什么时候关注空间复杂度？

1. 移动设备应用：内存有限

// 手机应用要特别注意
void ProcessImageOnMobile(byte[] imageData)
{
    // 错误：创建多个副本
    // byte[] copy1 = new byte[imageData.Length];
    // byte[] copy2 = new byte[imageData.Length];
    // 可能内存不足！
    
    // 正确：原地处理
    ApplyFilterInPlace(imageData);
}

2. 大数据处理：数据量巨大

void ProcessBigData()
{
    // 错误：一次性加载所有数据到内存
    // List<DataItem> allData = LoadAllFromDatabase(); // 可能10GB！
    
    // 正确：分批处理
    int batchSize = 1000;
    int offset = 0;
    
    while (true)
    {
        List<DataItem> batch = LoadBatchFromDatabase(offset, batchSize);
        if (batch.Count == 0) break;
        
        ProcessBatch(batch);  // 处理当前批次
        offset += batchSize;
    }
}

3. 递归算法：容易栈溢出

// 危险：深度递归占用大量栈空间
int FibonacciBad(int n)  // 空间复杂度O(n)
{
    if (n <= 1) return n;
    return FibonacciBad(n - 1) + FibonacciBad(n - 2);
    // n=1000时，递归深度1000，可能栈溢出
}

// 安全：使用循环，空间O(1)
int FibonacciGood(int n)
{
    if (n <= 1) return n;
    
    int prev2 = 0;  // F(0)
    int prev1 = 1;  // F(1)
    
    for (int i = 2; i <= n; i++)
    {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;  // 空间O(1)
}

九、实际案例：图片处理

class ImageProcessor
{
    // 方案A：创建多个副本（空间复杂度高）
    public byte[] ProcessImage_A(byte[] image)
    {
        byte[] copy1 = new byte[image.Length];  // 副本1
        byte[] copy2 = new byte[image.Length];  // 副本2
        byte[] result = new byte[image.Length]; // 结果
        
        Array.Copy(image, copy1, image.Length);  // 复制
        ApplyBrightness(copy1, 10);              // 处理副本1
        Array.Copy(copy1, copy2, image.Length);  // 再复制
        ApplyContrast(copy2, 20);                // 处理副本2
        Array.Copy(copy2, result, image.Length); // 再复制
        
        // 总空间：原图 + 3个副本 = 4倍原图大小
        return result;
    }
    
    // 方案B：原地处理（空间复杂度低）
    public void ProcessImage_B(byte[] image)
    {
        // 直接在原图上修改
        ApplyBrightness(image, 10);    // 修改原图
        ApplyContrast(image, 20);      // 再修改原图
        
        // 总空间：只有原图
        // 注意：会修改原始数据
    }
    
    // 方案C：折中方案（一个副本）
    public byte[] ProcessImage_C(byte[] image)
    {
        byte[] result = new byte[image.Length];  // 一个副本
        
        Array.Copy(image, result, image.Length); // 复制一次
        ApplyBrightness(result, 10);             // 修改副本
        ApplyContrast(result, 20);               // 再修改副本
        
        // 总空间：原图 + 1个副本 = 2倍原图大小
        return result;
    }
}

十、空间复杂度总结表

复杂度	含义	示例	适用场景
O(1)	使用固定内存	几个变量	移动设备、嵌入式
O(log n)	使用对数内存	递归深度	二分查找、递归树
O(n)	使用线性内存	复制数组	一般数据处理
O(n²)	使用平方内存	矩阵、所有组合	小规模数据
O(2ⁿ)	使用指数内存	所有子集	极小规模或理论研究

十一、面试常考题

// 题目：找出数组中重复的数字
// 要求：不能修改原数组，空间复杂度O(1)

class InterviewQuestion
{
    // 方法1：哈希表法（空间O(n) - 不符合要求）
    int FindDuplicate_Hash(int[] nums)
    {
        HashSet<int> seen = new HashSet<int>();  // O(n)空间
        foreach (int num in nums)
        {
            if (seen.Contains(num))
                return num;
            seen.Add(num);
        }
        return -1;
    }
    
    // 方法2：排序法（空间O(1)或O(n)，取决于是否允许修改）
    int FindDuplicate_Sort(int[] nums)
    {
        // 如果允许修改原数组：O(1)空间
        // 如果不允许修改：需要复制数组，O(n)空间
        
        Array.Sort(nums);  // 如果nums是副本，则O(n)空间
        
        for (int i = 1; i < nums.Length; i++)
        {
            if (nums[i] == nums[i - 1])
                return nums[i];
        }
        return -1;
    }
    
    // 方法3：快慢指针法（空间O(1)，且不修改原数组）
    int FindDuplicate_Floyd(int[] nums)
    {
        // 利用数组索引和值形成链表
        int slow = nums[0];
        int fast = nums[0];
        
        // 第一阶段：找到相遇点
        do
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        
        // 第二阶段：找到环的入口
        slow = nums[0];
        while (slow != fast)
        {
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return slow;  // 空间复杂度：O(1)
    }
}

十二、一句话总结

空间复杂度就是：你的算法运行时需要多少额外内存。

• O(1)：省内存 ✅
• O(n)：正常 ✅
• O(n²)：很吃内存 ⚠️
• O(2ⁿ)：内存爆炸 ❌

记住：时间和空间往往要权衡。有时候用内存换速度，有时候用时间换内存。