各种查找算法的性能比较试(顺序查找、二分查找)各种查找算法的性能比较测试(顺序查找、二分查找).docVIP

算法设计与分析 各种查找算法的性能测试 目录 TOC \o 1-4 \h \u  HYPERLINK \l _Toc14182 摘要  PAGEREF _Toc14182 4  HYPERLINK \l _Toc24397 第一章：简介（Introduction）  PAGEREF _Toc24397 5  HYPERLINK \l _Toc24681 1.1 算法背景  PAGEREF _Toc24681 5  HYPERLINK \l _Toc7634 第二章：算法定义（Algorithm Specification）  PAGEREF _Toc7634 5  HYPERLINK \l _Toc25040 2.1 数据结构  PAGEREF _Toc25040 5  HYPERLINK \l _Toc9689 2.2顺序查找法的伪代码  PAGEREF _Toc9689 6  HYPERLINK \l _Toc23459 2.3 二分查找（递归）法的伪代码  PAGEREF _Toc23459 6  HYPERLINK \l _Toc24261 2.4 二分查找（非递归）法的伪代码  PAGEREF _Toc24261 7  HYPERLINK \l _Toc10571 第三章：测试结果（Testing Results）  PAGEREF _Toc10571 9  HYPERLINK \l _Toc18856 3.1 测试案例表  PAGEREF _Toc18856 9  HYPERLINK \l _Toc13749 3.2 散点图  PAGEREF _Toc13749 10  HYPERLINK \l _Toc25423 第四章：分析和讨论  PAGEREF _Toc25423 12  HYPERLINK \l _Toc14762 4.1 顺序查找  PAGEREF _Toc14762 12  HYPERLINK \l _Toc15311 4.1.1 基本原理  PAGEREF _Toc15311 12  HYPERLINK \l _Toc32178 4.2.2 时间复杂度分析  PAGEREF _Toc32178 12  HYPERLINK \l _Toc5959 4.2.3优缺点  PAGEREF _Toc5959 12  HYPERLINK \l _Toc17465 4.2.4该进的方法  PAGEREF _Toc17465 13  HYPERLINK \l _Toc18940 4.2 二分查找（递归与非递归）  PAGEREF _Toc18940 13  HYPERLINK \l _Toc26077 4.2.1 基本原理  PAGEREF _Toc26077 13  HYPERLINK \l _Toc20977 4.2.2 时间复杂度分析  PAGEREF _Toc20977 14  HYPERLINK \l _Toc14590 4.2.3优缺点  PAGEREF _Toc14590 14  HYPERLINK \l _Toc683 4.2.4 改进的方法  PAGEREF _Toc683 14  HYPERLINK \l _Toc26384 附录：源代码（基于C语言的）  PAGEREF _Toc26384 16  HYPERLINK \l _Toc31694 声明  PAGEREF _Toc31694 18  摘要 在计算机许多应用领域中，查找操作都是十分重要的研究技术。查找效率的好坏直接影响应用软件的性能，而查找算法又分静态查找和动态查找。 我们设置待查找表的元素为整数，用不同的测试数据做测试比较，长度取固定的三种，对象由随机数生成，无需人工干预来选择或者输入数据。比较的指标为关键字的查找次数。经过比较可以看到，当规模不断增加时，各种算法之间的差别是很大的。这三种查找方法中，顺序查找是一次从序列开始从头到尾逐个检查，是最简单的查找方法，但比较次数最多，虽说二分查找的效率比顺序查找高，但二分查找只适用于有序表，且限于顺序存储结构。 关键字：顺序查找、二分查找（递归与非递归） 第一章：简介（Introduction） 1.1 算法背景 查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的值，我们称之为查找键。 对于查找问题来说，没有一种算法在任何情况下是都是最优的。有些算法速度比