算法设计中，时间复杂度与空间复杂度的取舍是核心决策，需根据场景、资源约束和性能需求综合权衡。
一、取舍原则
| 场景 | 优先策略 | 典型做法 |
|---|---|---|
| 内存紧张（嵌入式/移动端） | 降低空间复杂度 | 迭代替代递归，空间 O(n)→O(1) |
| 计算紧张（实时系统/高频交易） | 降低时间复杂度 | 预计算+缓存，查询 O(n)→O(1) |
| 小规模数据 | 优先空间效率 | 插入排序 O(n²) 时间、O(1) 空间 |
| 大规模数据 | 优先时间效率 | 索引查询 O(log n) 替代全表扫描 O(n) |
| 快速响应（UI/API） | 降低时间复杂度 | 哈希表存储，O(1) 查询 |
| 长期运行（批处理） | 可接受高时间换空间 | 外部排序/流式处理 |
二、空间换时间
| 方法 | 说明 | 示例 |
|---|---|---|
| 缓存 | 存储中间结果避免重复计算 | 动态规划备忘录，O(2ⁿ)→O(n) |
| 预处理 | 提前构建索引/数据结构 | 搜索引擎倒排索引 |
| 哈希表 | 以空间换查找速度 | 词频统计 O(n log n)→O(n) |
三、时间换空间
| 方法 | 说明 | 示例 |
|---|---|---|
| 迭代替代递归 | 消除递归栈开销 | 阶乘计算空间 O(n)→O(1) |
| 流式处理 | 分块处理，减少内存 | 大文件排序：分块→归并 |
| 压缩数据结构 | 牺牲访问速度换空间 | 位图存储布尔值，空间 O(n)→O(n/8) |
四、折中方案
- 混合策略— B+树索引：O(log n) 时间 + O(n) 空间，平衡查询与存储
- 参数化调整— 快速排序在小数据时切换为插入排序
- 近似算法— 布隆过滤器：O(1) 时间 + O(n) 空间，允许一定误判
五、决策流程
明确需求（时间敏感 or 空间敏感） → 分析输入规模（小 → 空间优先；大 → 时间优先） → 评估候选算法（比较时间/空间复杂度） → 基准测试验证（实际环境测内存+耗时） → 动态调整（根据反馈优化策略）深入学习：时间复杂度详解 · 空间复杂度详解
