一、排序算法
算法名称 时间复杂度（平均/最坏） 空间复杂度 适用场景 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更高效。
