三种不同查算法实际查性能的对⽐
⼀、查问题的介绍
查问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中寻⼀个给定的值，我们称之为查键。有许多查算法可供选择，其中既包括直截了当的顺序搜索，也包括效率极⾼但应⽤受限的折半查，还有那些将原集合⽤另⼀种形式表⽰以⽅便查的算法。最后⼀类算法对于现实应⽤具有特别重要的价值，因为它们对于⼤型数据库的信息存取来说是不可或缺的。
对于查来说，没有⼀种算法在任何情况下都是最优的。有些算法速度⽐其他算法快，但需要较多的存储空间；有些算法速度⾮常快，但仅适⽤于有序的数组，诸如此类。和排序算法不同，查算法没有稳定性问题，但会发⽣其他问题。具体来说，如果应⽤⾥的数据相对于查次数频繁变化，查问题就必须结合另外两种操作⼀起考虑：在数据集合中添加和删除元素的操作。在这种情况下，必须⾃习选择数据结构和算法，以便在各种操作的需求之间达到⼀个平衡。⽽且，对于⽤于⾼效查的特⼤型数据集合来说，如何组织其结构是⼀项不同寻常的挑战，⽽这对实际应⽤具有⾮常重要的意义。
针对查问题采⽤了三种⽅法：线性表直接查，⼆叉排序树查，平衡⼆叉排序树查三种⽅法。
1）其中线性表(Linear List,LL)直接查，通过将数据集合存储在数组中，每次从数组⾸地址开始⼀直搜索
到数组末尾，直到查到待查元素和到达数组末尾为⽌。并针对该⽅法给出了⼀个优化的算法，对数组中的元素增加⼀个频度域，将查频度最⾼的元素放在数组最前⾯，依次按频度对数组中元素进⾏排序。
2）⼆叉排序树（Binary Sort Tree,BST）查，BST⼜称⼆叉搜索树，其定义为：⼆叉排序树或者是⼀颗空树，或者是具有如下性质的⼆叉树：①若左⼦树不空，则左⼦树上所有节点的值均⼩于它的根节点的值；②若右⼦树不空，则右⼦树上所有节点的值均⼤于它的根节点的值；③左、右⼦树也分别是⼆叉排序树；④没有键值相等的节点。从BST的定义中可知，在BST中查⼀个元素的过程，即从根节点开始，每次根据待查元素与根节点的⽐较，决定查成功或者依左或右⼦树查，直到到待查元素或者都到叶⼦节点为⽌。
3）平衡⼆叉查树（Adelson-Velskii and Landis，AVL树），⼀棵AVL树是⼀棵⼆叉查树，其中每个节点的平衡因⼦定义为该节点左⼦树和右⼦树的⾼度差，这个平衡因⼦要么是0，要么为+1或者-1（⼀棵空树的⾼度定义为-1）。因此AVL树是⼀种特殊的⼆叉查树，其左右分⽀深度⽐较平衡，这样就缩短了树的⾼度，从⽽降低了查的次数。在AVL树种查元素的过程类似在⼆叉排序树中查元素。
⼆、对查问题的理论分析
设集合中的数据个数为n，则在采⽤线性表直接存储时，每次查⼀个元素，在最好的情况下，时间复
杂度是o(1)，最坏的情况下时间复杂度是o（n），因此平均查长度是
在对线性表直接查进⾏优化的算法中，增加了频度域，数组中数据按照数据查的频度从⾼到低排列，在这种算法上，最好的情况下，时间复杂度是o(1)，最坏的情况下时间复杂度是o（n）。数据的平均查长度依赖于所查的序列。但可以确定的是，其查长度低于优化前的查长度
在分析⼆叉排序树的理论查性能时，我们⾸先要清楚⼆叉排序树的形态，因为当⼆叉排序树的形态不同，其树的深度就会不同，因⽽查的性能也会不同。在极端的情况，⼆叉排序树退化为⼀个单分⽀的树，则其查性能跟线性表直接查相同。在这⾥我们可以分析，对⼀棵随机⽣成的⼆叉排序树，其平均查性能优于线性表直接查。为了确定⼆叉排序树查性能的上界和下界，我们⾸先分析⼀棵完全平衡的⼆叉排序树，即既是⼀棵平衡⼆叉树，⼜是⼀棵完全⼆叉树。假设每⼀个节点的查频率相同，则完全平衡⼆叉查树的平均查长度为
因此随机⽣成的⼀棵⼆叉查树的平均长度为
上述三种⽅法从时间复杂度上来说，查⼀个数据的时间复杂度都是o（n），空间复杂度均需要o（n）⼤⼩的辅助存储空间。
三、实验仿真结果
实验在VC6.0平台上，采⽤的C语⾔编写程序，将实验中测试的数据存储在⽂本中，再将⽂本数据导⼊到matlab中进⾏可视化⽐较。
图3.1和图3.2是测试不同查算法的运⾏所耗费的时间的实时输出截图。其中图3.1是样本数量较少情况下的运⾏输出图，图3.2是样本数量较⼤时候的运⾏输出图。每⼀次输出会连续输出四组数据，每⼀组数据包含两个数值，第⼀个数值表⽰的是查所耗费总的时间，第⼆个数值是查中总的查长度。
并将运⾏中的数据记录在⽂件中，图3.3和图3.4均是在测试样本数量不同时的各算法查性能的评价值。每⼀⾏为⼀个样本的记录，包含九个数字，第⼀个数值是测试样本的数量，后⾯的⼋个数字，两个⼀组，共四组，第⼀个数字是查所耗费的时间，第⼆个数字是查总的长度，四组数字分别对应，直接连表查，带频度的连表查，⼆叉查树和AVL树查。在图3.4中，有的部分数字是负数，那是因为查的长度值超过了C语⾔中int类型的最⼤数值表⽰范围，产⽣了溢出。
在图3.5中，是四种算法的查耗费时间的对⽐图，通过将上⾯记录的实验数据导⼊到Matlab中，⽣成的对⽐图。从图中我们可以直观看到四种算法中，线性表直接查所耗费的时间最长，带频度的线性变性能次之，相对⽐，⼆叉查树和AVL树的查性能要好得多，耗费的时间也⼤⼤的低于线性表。随着样本数量的增加，线性表查的时间耗费整体趋势呈正⽐例增长，⽽⼆叉排序树和⼆叉查树的时间变化⽐较缓慢。
图3.6和图3.7分别是对图3.5的局部进⾏放⼤所成的图。从这两幅图中，可以直观的看到两种线性表和两种⼆叉树数据结构算法的性能对⽐。
在下⾯，我们将呈现各算法总的查长度的性能对⽐图。在图3.8中，我们可以看到，相对于直接线性表和带频度的线性表来说，⼆叉查树和AVl树的总的查长度要低得多。⽽图中在接近900000样本时，所出现的查长度变为负数，是因为存储查长度的int类型变量发⽣了正向溢出。
二叉树的基本性质
图3.9分别为对图3.8的局部放⼤，更清晰的呈现其性能的对⽐。从图3.8中可以直观的看到，带频度的线性表能够在线性表直接查的基础上改进查性能，降低总的查长度。从图3.9中可以看到，AVL树的查性能在平均的情况向，其查所耗费的总的查长度，⼤约为⼆叉查树的3/4。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。