STL算法复杂度对比表

༺ཌༀ我不会这道题ༀད༻

2025-12-28 11:49:51

发布于：上海

7阅读

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更高效。

有帮助，赞一个

去预览

0/2000

全部评论 2

136****2285

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]+right

2025-12-28 来自浙江