set::insert 的复杂度
我已经阅读到集合中的插入操作只需要 log(n) 时间.这怎么可能?
I have read that insert operation in a set takes only log(n) time. How is that possible?
要插入，首先我们要在排序后的数组中找到新元素必须位于的位置.使用二分查找需要 log(n).然后要插入到那个位置，它后面的所有元素都应该向右移动一个位置.又需要n次.
To insert, first we have find the location in the sorted array where the new element must sit. Using binary search it takes log(n). Then to insert in that location, all the elements succeeding it should be shifted one place to the right. It takes another n time.
我的怀疑是基于我的理解，即 set 是作为数组实现的，并且元素按排序顺序存储.如果我的理解有误，请纠正我.
My doubt is based on my understanding that set is implemented as an array and elements are stored in sorted order. Please correct me if my understanding is wrong.
推荐答案
std::set 通常实现为红黑二叉搜索树.在这种数据结构上插入的最坏情况是 O(log(n)) 复杂度，因为树保持平衡.
std::set is commonly implemented as a red-black binary search tree. Insertion on this data structure has a worst-case of O(log(n)) complexity, as the tree is kept balanced.
相关文章