bib*_*sey 17 c++ stl set time-complexity
我已经读过一个集合中的插入操作只需要log(n)时间.怎么可能？
要插入,首先我们在排序数组中找到新元素必须位于的位置.使用二进制搜索需要log(n).然后要插入该位置,其后面的所有元素都应该向右移动一个位置.这需要另外n次.
我怀疑是基于我的理解,set是作为数组实现的,元素是按排序顺序存储的.如果我的理解是错误的,请纠正我.
cdh*_*wie 28
std::set通常实现为红黑二叉搜索树.由于树保持平衡,因此插入此数据结构具有O(log(n))复杂度的最坏情况.
std::set
归档时间：
14 年 前
查看次数：
25324 次
最近记录：
7 年，9 月 前