set :: insert的复杂度 [英] complexity of 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.

我的怀疑是基于我的理解，即集合是作为数组实现的，元素按排序顺序存储。如果我的理解有误，请纠正我。

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.

这篇关于set :: insert的复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！