数据结构与算法(五)查询

很多时候,我们会比较在意查询的时间,因为这是用户最常使用的功能,并且是实时的需求,非常影响用户体验,以下是各种数据结构查询的效率,我们可以看到平衡二叉树等查找效率比较高,其实这是将时间前移了,因为平衡二叉树本身就是有序的,相当于已经对数据进行了一个排序,我们可以看到插入构造这个树的时间LOG(N)。

image

一.无序数据基础查找

像单链表这种无序队列,插入的时候很快的,直接加到末尾就可以,但是其查找确实耗时,使用了直接查找法。

所以为了加速查找的速度,需要将数据预先进行排序,一般就是生成的 时候就进行排序,比如数据库表加索引,构造二叉树,哈希表存储数据,这样在这些有序数据基础上进行数据查找就快多了,虽然在构造的时候会消耗时间,甚至让总时间都增加了,但是,有什么关系呢。

二.有序数据查找

无序数据查找效率比较慢,所以一般查找前都会排序,分担一部分的压力。

折半查找法

适用场景:针对已排序序列,并且只适用于