常用STL时间复杂度

发布时间 2023-06-21 13:18:04作者: tunecoming

缘由

  最近有好几次写题因为STL的时间复杂度弄错导致题目T了,还找不到原因后(自己以为时间复杂度没有问题),被学长狠狠嘲讽了:(

 所以写下这篇blog来总结常用的STL复杂度(我不想原地退役),希望以后不会错了。


vector

push_back : O(1)

pop_back : O(1)

insert : O(n)

erase : O(n)

find : O(n)

queue

push : O(1)

pop : O(1)

deque

push_back & push_front : O(1)

pop_back & pop_front : O(1)

erase : O(n)

priority_queue

push : O(log n)

pop : O(log n)

map

insert : O(log n)

erase : O(log n)

count : O(log n)

find : O(log n)

set

insert : O(log n)

find : O(log n)

erase : O(log n)

count : O(log n)


 

应该不至于这里都写错了吧。。。如果发现错误请一定告诉我(拜托了。。。我不想原地退役)。