首页 > 试题广场 >

关于下列操作哪个复杂度为O(1)?

[不定项选择题]

关于下列操作复杂度为O(1)的是（） 

  • vector中插入元素(动态数组)
  • set中查找元素
  • hash_map中查找元素
  • deque尾部删除元素
查看正确选项
添加回答
西邮白白头像 西邮白白
vector插入 ,该位置插入后后面的都要改变O(n)
Set底层红黑树  O（logn）
Hash_map 底层哈希表 O（1）
Deque尾部可以直接修改O（1）
发表于 2020-10-27 19:48:19 回复(1)
牛客9367371号头像 牛客9367371号

set是红黑树 故logn

发表于 2018-07-14 01:20:25 回复(2)
牛客842641340号头像 牛客842641340号
A：如果是push_back的方式插入的话，时间复杂度的确是O(1),但是假如以 iterator insert(iterator it,const T& x):这种方式插入的话，它需要先找到指定元素，然后再再它前面添加。因为有查找整个过程，所以最差可能要全部遍历，所以为O(n)。
编辑于 2021-09-05 22:23:24 回复(0)
牛客693977198号头像 牛客693977198号
hash_map 如果遇到hash冲突应该就不是O(1)了吧
发表于 2021-07-28 14:43:31 回复(1)
LeonChenCN头像 LeonChenCN
题目中hash_map的hash算法未知，有些hash算法只生产少量的桶，每个桶要装载很多个对象，这样就没有O(1)的时间复杂度。
发表于 2023-04-19 13:55:58 回复(0)
不要葱花的西红柿很爱吃鱼头像 不要葱花的西红柿很爱吃鱼
set和map底层是红黑树，查询效率为O（longn） unordered_set和unordered_map底层是哈希表，查询效率为O（1）
发表于 2020-09-27 03:02:00 回复(0)
cherish蔡中顺头像 cherish蔡中顺
hash_map基于hash表，deque是双向队列
发表于 2018-07-14 14:21:20 回复(0)
君__头像 君__
vector那个 
分摊复杂度O（1）
发表于 2023-09-14 10:36:14 回复(0)
牛客580050057号头像 牛客580050057号
vector插入，该位置插入后后面的都要改变O(n)
set 底层红黑树 O(logn)
hast_map 底层哈希表 O(1)
deque尾部可以直接修改O(1)
发表于 2021-06-25 19:33:16 回复(0)
牛客894934275号头像 牛客894934275号
hash_map基于hash表，deque是双向队列
发表于 2020-09-04 19:23:52 回复(0)
码蹄疾hit头像 码蹄疾hit
C,hashMap, hash是根据hash码进行查找，肯定是o(1)
---------------
扫码关注公众号，每天更新一道面试题：

发表于 2018-07-14 10:28:46 回复(2)
提交观点

问题信息

C++工程师 摩拜 2018 C++
来自：摩拜2018校招客户端...
上传者：小小
难度：
11条回答 3873浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号