关于vector的删除指定元素的时间复杂度
  • 板块灌水区
  • 楼主ColinKIA
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/1/14 22:33
  • 上次更新2023/10/24 04:12:46
查看原帖
关于vector的删除指定元素的时间复杂度
647306
ColinKIA楼主2023/1/14 22:33

在某一题中(P1168),原题要求用对顶堆维护一个中位数,但是通过vector的inster函数和lower_bound可以水过,但是insert理论上是 O(n)O(n) 但是却可以过,说明insert常数较小,在网上的某篇博客中,说明了insert的时间复杂度不超过 O(n)O( \sqrt n) 甚至比肩 O(logn)O(logn),可是今天月赛T2使用二分加vector的删除函数erase和insert维护有序序列却T了,求erase的运行原理加时间复杂度

2023/1/14 22:33
加载中...