STL算法复杂度对比表
2025-12-28 11:49:51
发布于：上海
13阅读
0回复
0点赞
一、排序算法
| 算法名称 | 时间复杂度（平均/最坏） | 空间复杂度 | 适用场景 |
|---|---|---|---|
std::sort |
O(n log n) / O(n log n) | O(1) | 基本类型排序 |
std::stable_sort |
O(n log n) / O(n (log n)²) | O(n) | 需保持相等元素顺序 |
std::partial_sort |
O(n log k) / O(n log k) | O(1) | 获取前k个最小元素 |
std::nth_element |
O(n) / O(n) | O(1) | 找到第n小元素 |
二、搜索算法
| 算法名称 | 时间复杂度 | 适用场景 |
|---|---|---|
std::find |
O(n) | 未排序序列 |
std::binary_search |
O(log n) | 已排序序列 |
std::lower_bound |
O(log n) | 已排序序列，返回第一个≥val的迭代器 |
std::upper_bound |
O(log n) | 已排序序列，返回第一个>val的迭代器 |
三、其他常用算法
| 算法名称 | 时间复杂度 | 适用场景 |
|---|---|---|
std::for_each |
O(n) | 遍历容器 |
std::transform |
O(n) | 搬运元素并应用函数 |
std::copy |
O(n) | 拷贝元素 |
std::remove |
O(n) | 删除元素 |
std::unique |
O(n) | 删除相邻重复元素 |
四、STL容器操作复杂度对比表
1. 序列容器
| 操作 | std::vector |
std::list |
std::deque |
|---|---|---|---|
| 随机访问 | O(1) | O(n) | O(1) |
| 头部插入/删除 | O(n) | O(1) | O(1) |
| 尾部插入/删除 | O(1) | O(1) | O(1) |
| 中间插入/删除 | O(n) | O(1) | O(n) |
2. 关联容器
| 操作 | std::set |
std::multiset |
std::map |
std::multimap |
|---|---|---|---|---|
| 插入 | O(log n) | O(log n) | O(log n) | O(log n) |
| 删除 | O(log n) | O(log n) | O(log n) | O(log n) |
| 查找 | O(log n) | O(log n) | O(log n) | O(log n) |
count |
O(log n) | O(log n) | O(log n) | O(log n) |
lower_bound |
O(log n) | O(log n) | O(log n) | O(log n) |
upper_bound |
O(log n) | O(log n) | O(log n) | O(log n) |
3. 哈希容器
| 操作 | std::unordered_set |
std::unordered_multiset |
std::unordered_map |
std::unordered_multimap |
|---|---|---|---|---|
| 插入 | O(1) | O(1) | O(1) | O(1) |
| 删除 | O(1) | O(1) | O(1) | O(1) |
| 查找 | O(1) | O(1) | O(1) | O(1) |
count |
O(1) | O(1) | O(1) | O(1) |
五、算法选择建议
- 数据规模：小规模数据可选简单算法，大规模数据需考虑时间复杂度。
- 是否已排序：已排序序列优先用
binary_search、lower_bound等O(log n)算法。 - 是否需稳定排序：需保持相等元素顺序时用
stable_sort。 - 内存限制：空间敏感场景避免高空间复杂度算法。
- 具体需求：如只需前k个最小元素，用
partial_sort更高效。
全部评论 2
def fast(arr): mod=arr[0] left=[] right=[] for i in arr[1:]: if i<mod:left.append(i) else:right.append(i) return left+[mod]+right2025-12-28 来自 浙江
0
有帮助，赞一个