我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:爱彩网 > 二分搜索 >

C++中set的插入和查找 与二分查找对比 效率如何

归档日期:07-07       文本归类:二分搜索      文章编辑:爱尚语录

  我是分别用et插入25w个整数,然后再用nt与x匹配x是我输入的值另外是把25w个数据复制到数组f[]然后用二分查找匹配。。。。两种算法提交后前者共耗时2600ms空间9000kb后者耗...

  我是分别用 st.inset插入25w个整数,然后再用st.count与x匹配 x是我输入的值

  另外是把25w个数据复制到数组f[] 然后用二分查找匹配。。。。两种算法提交后 前者共耗时2600ms 空间9000kb 后者 耗时600ms 内存2000kb。。。。想问问具体为什么 据说set的查找也是二分。。lgn复杂度展开我来答

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  展开全部Set的底层是用的红黑树。而数组就是顺序表。这两种数据结构优劣不同。

  如果已知数据有序,那么顺序表的二分查找当然最快。但是顺序表的插入性能极差,比如我要在头部插入一个数据,则要吧所有的数据后移一格,开销极大。红黑树则平衡了插入性能和查找性能。所以就有你看到的数据了,set的时间空间性能都比较差。

  顺序复制数组,不涉及到插入,所以数组很快。但是插入,删除的话,红黑树需要一些时间来调整结构,所以有时间和空间的开销。

  如果你有这样的一批数据,数量比较大,假设25w左右,他们需要频繁的发生插入,删除,以及查找工作,那么数组就无法处理了,红黑树则是更好的选择。

  如果有不清楚的地方请追问。追问好吧谢谢您。。我忘了 提到 set里面是每次插入都有自动排序。。。而我在数组方面是先全部赋值完成再用sort排序。

  那么我那样使用set和二分查找造成的时间和空间的差别 是 因为 处理输入数据时,红黑树的插入过程每次都排序吗追答空间差别:红黑树是树,不仅仅需要存储你给的值,还要存储树所需的其他信息,比如子节点,父节点的地址,节点颜色。

  时间差别:红黑树并不是每次都需要排序,但是会在有些情况下对树进行调整,红黑树的插入策略还是有点小复杂的,你需要专门的研究。

  顺序表并不适合不断的插入。理由如下:即使你一直保证顺序表有序,那么当你使用二分查找找到需要插入的点的时候,进行数据插入,插入时候你不得不对后面所有的数据往后移动一格。当数据很大,移动大量的内存开销很大的。所以不适合插入。此外,当对数据进行删除,又要对大量内存向前移动一格。相比之下,红黑树的插入,删除性能就好很多。

  复杂度的确都是logN(排序其实是平均logN,最坏情况下是logN^2),有一个小问题是二分查找是绝对的2的对数次循环,红黑树并不是绝对平衡的平均下来会比2的对数次循环多。不过这个只是小问题。另外一个小问题是红黑树的每次循环的代价要比排序大,排序只是一个比较和一个可能的交换,红黑树是一个申请内存,初始化结构加一个可能的涉及三个节点的旋转。

  然后真正影响速度的大问题是内存局域性(memory locality),内存局域性差就不能有效利用CPU的高速缓存。

  排序方法你写入的时候不读取数据,排序的时候用的快速排序算法某种意义上也是一个牺牲绝对复杂度(最坏的情况下是logN^2)从而提高内存局域性的算法。二分查找是一个内存局域性差的操作,但是你只执行了一次。

  而set每次插入都是内存局域性几乎等于没有的操作,而且set本身的数据量又大很多,所以自然就慢了。

  set更适合需要不断插入,并且随时要在里面查找的情况(这种情况一般叫在线排序online sorting)。set插入的复杂度是logN,而排序的方法插入的复杂度是N。所以只要N足够大,就能抵消内存局域性的代价。但是你的情况显然不符合。追问谢谢。最后一段,set更适合不断地插入,然后随时查找。。。

  比较起 每次往数组赋值一个数,然后sort排序。。然后二分查找。。这两种效率应该一样吧。

  而我的 问题中 出现时间空间有差别应该是因为 前者是每次插入都排序。而后者只全部输入完成之后一次排序。吧追答向数组插入的复杂度是N(先用二分查找确定插入位置,然后把内容向后挪)。你说的加进去再排序的复杂度是N*logN,也就是排序的复杂度。向set插入的复杂度是logN。显然前者比后者慢太多了。即便向set插入一次循环的时间是排序一次循环的100倍。元素超过100个的时候排序就比set慢了。我那个方法元素超过1000个也开始比set慢了。(而且注意,其实set插入也没慢到100倍上)

  复杂度差一级是很可怕的,你的情况之所以它们两个的单次循环性能会影响结果,因为时间复杂度是一样的。

本文链接:http://pikeducation.com/erfensousuo/495.html