各种查找算法性能分析.doc

各种查找算法性能分析.doc各种查找算法性能分析
各种查找算法性能分析
1 / 13
各种查找算法性能分析
项 目 名 称：各种查找算法的性能测试
项目成员：
组编号：
完成时间：
目录
前言 2
正文 2
第一章 简介 2
顺序查找问题描述 2
二分查找问题描述 2
第二章 算法定义 2
顺序查找算法定义 2
二分查找算法定义 3
第三章 测试结果（ Testing Results) 5
实验结果表 5
散点图记录 5
第四章 分析和讨论 6
顺序查找分析 6
二分查找分析 6
附录：源代码（基于 C 语言的 ) 7
声明 ................................................................................................................................. 13
各种查找算法性能分析
各种查找算法性能分析
13 / 13
各种查找算法性能分析
前言
查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的值，我们称之为查找键。
对于查找问题来说，没有一种算法在任何情况下是都是最优的。有些算法速度比其他算法快，
但是需要较多的存储空间； 有些算法速度非常快， 但仅适用于有序数组。 查找问题没有稳定性的问题，但会发生其他的问题（动态查找表） 。
在数据结构课程中，我们已经学过了几种查找算法，比较有代表性的有顺序查找（蛮力查找） ，二分查找 （采用分治技术），哈希查找（理论上来讲是最好的查找方法） 。
第一章：简介（ Introduction ）
顺序查找问题描述：
顺序查找从表中最后一个记录开始， 逐个进行记录的关键字和给定值的比较， 若某个记录的关键字和给定值比
较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中
没有所查记录，查找不成功。
二分查找问题描述：
1）分析掌握折半查找算法思想，在此基础上，设计出递归算法和循环结构两种实现方法的折半查找函数。
（2）编写程序实现：在保存于数组 a[i]有序数据元素中查找数据元素 k 是否存在。数元素 k 要包含两种情况： 一种是数据元素 k 包含在数组中； 另一种是数据元素 k 不包含在数组中
3）数组中数据元素的有序化既可以初始赋值时实现， 也可以设计一个排序函数实现。
4）根据两种方法的实际运行时间，进行两种方法时间效率的分析对比。
第二章：算法定义（ Algorithm Specification ）
顺序查找
从表的一端向另一端逐个进行记录的关键字和给定值（要查找的元素）的比较，若某个记录
各种查找算法性能分析
各种查找算法性能分析
3 / 13
各种查找算法性能分析
的关键字和给定值比较相等，则查找成功，找到所查找记录；反之，若直至第一个记录，其关键
各种查找算法性能分析
各种查找算法性能分析
13 / 13
各种查找算法性能分析
字和给定值比较都不等，则表明表中没有所查记录，查找不成功。
顺序查找的算法如下：
int SeqSearch1(int r[ ], int n, int k) // 数组 r[1] ~ r[n] 存放查找集合， n 是数组中元
素的个数（即查找表的长度） ，k 是要查找的元素
{
i=n;// 从后往前把表中的元素与要查找的元素进行比较
while (i>0 && r[i]!=k)// 当 i>0 并且数组元素中的值不等于要查找元素时， i 减一
继续执行 while 循环
{ i--;}
return i;//i 的值为 0 则没找到，为非 0 则 i 为要查找元素的位置
}
二分查找
二分查找又称折半查找，二分查找首先要求待查找的表是有序表，如果要查找的元素是表的中间
的那个元素，