三种不同搜索算法的实际搜索性能比较

I. 发现问题简介

搜索问题是在给定集合（或多个集合，以允许多个元素具有相同值）中找到给定值，我们将其称为搜索关键字. 有很多搜索算法可供选择，包括简单的顺序搜索，高效但半查找的有限应用，以及以另一种形式表示原始集的搜索算法，以方便搜索. 最后一类算法对于实际应用特别重要，因为它们对于访问大型中的信息是必不可少的.

对于搜索，在任何情况下都没有最佳算法. 某些算法比其他算法更快，但是需要更多的存储空间. 有些算法非常快，但仅适用于有序数组，依此类推. 与排序算法不同，搜索算法没有稳定性问题，但是还会发生其他问题. 具体来说，如果应用程序中的数据相对于搜索次数频繁变化，则必须结合其他两个操作来考虑搜索问题: 添加和删除数据集中的元素的操作. 在这种情况下，您必须自学选择数据结构和算法，以便在各种操作需求之间取得平衡. 而且，对于用于高效搜索的非常大的数据集，如何组织其结构是一个不寻常的挑战，这对实际应用具有非常重要的意义.

用于搜索问题的三种方法: 线性表直接搜索，二进制排序树搜索和平衡二进制排序树搜索.

1）每次从数组的第一个地址到数组的末尾，直到要搜索的元素和数组的末尾，都通过将数据集存储在数组中来直接搜索线性列表（LL）. 找到数组. 针对该方法给出了一种优化算法，将频率域添加到数组中的元素，将搜索频率最高的元素放置在数组的前面，并按频率对数组中的元素进行顺序排序.

2）二进制排序树（BST）搜索，BST也称为二进制搜索树，其定义为: 二进制排序树或空树，或具有以下属性的二进制树: ①如果左子树不是为空时，左子树上所有节点的值小于其根节点的值; ②如果右子树不为空，则右子树上所有节点的值大于其根节点的值; ③左右子树也是二叉排序树； ④没有相同键值的节点. 从BST的定义中，我们可以看到在BST中查找元素的过程从根节点开始. 每次根据要检查的元素与根节点之间的比较，确定搜索是否成功，或者搜索左或右子树，直到找到搜索为止. 这些元素都可以到达叶节点.

3）平衡二叉搜索树（Adelson-Velskii和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语言编写实验，并将实验中的测试数据存储在record.txt文本中，然后将文本数据导入到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中，我们可以看到二叉搜索树和AV1树的总搜索长度远低于直接线性表和带有频率的线性表. 但是，当该图接近900000个样本时，由于存储该搜索长度的int类型变量具有正溢出，因此显示的搜索长度似乎为负.

图3.9是图3.8的局部放大图，更清楚地显示了性能比较. 从图3.8可以直观地看出，具有频率的线性表可以在直接搜索线性表的基础上提高搜索性能，并减少总搜索长度. 从图3.9可以看出，AVL树的搜索性能平均，并且搜索所需的总搜索长度约为二叉搜索树的3/4.

三种不同搜索算法的实际搜索性能比较

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-167963-1.html