线性查找第k小元素的算法设计分析与优化研究(2)

菜单

在数据量日益庞大的今天，我们希望有效地从 n 个不同数据构成的集合中选择其第 k 个顺序统计，所谓由 n 个不同元素组成的集合的第 k 个顺序统计就是指该集合中第 k 个的元素。

定义 1：选择问题即从 n 个不同数据构成的集合中选择其第 k 个顺序统计，线性时间选择是元素比较的最大次数和序列的大小呈线性关系。论文网

1.2 时间复杂度的概念

定义 2：通俗地讲，当我们遇到任何一个问题时，我们都需要方法来解决它，所需的方法称之为算法。

更加严格地来讲，算法是对某一特定类型问题求解步骤的一种描述，是指令的有穷序列的集合，其中一条指令包括一个或多个操作。算法可分为确定性算法和随机算法。而我们所研究的线性时间选择为确定性算法，即算法的每一个步骤都确切地定义。对于任意一个算法，总是在执行有穷步后结束，便可以得到该问题的解。

定义 3：算法的复杂性是在算法运行时需要耗费的计算机资源的量，耗费的时间资源量称为时间复杂度，时间复杂度是衡量算法是否有效的最好度量。时间复杂度反映了算法的效率。换句话说，这个量应该是只依赖于待解的问题的规模、算法的输入和算法本身的函数。

不同算法的时间复杂度通常不同，则需要有一个标准来评判算法效率的高低。

定义 4：设对于一切 n0 的整数有一个非负函数(n)。如果存在一个整数n0和一个正常数 c，且对任何 nn0都有(n)cg(n)，则称(n)是 O(g(n))。如果一个多

项式为 g(n)，其输入的长度为 n，则时间复杂度为 O(g(n))的算法为多项式算法。

线性时间是一种很好的多项式算法，线性时间中 g(n)=n，即(n)cn。它的时间复杂度很低，如果一个线性时间算法具有良好的性能，那么它就有较好的实际应用价值。因此，线性时间复杂度的算法研究就非常有必要了。

1.3 课题研究的意义

线性选择问题在网络路由、数据库搜索、人工智能、优化决策、生物信息处理算法等领域具有重要的应用。对于经典的线性时间选择问题（即线性时间查找第 k 小个元素），设对 n 个不同元素的数组调用算法需要 T(n)的时间，我们通过对关于 T(n)的表达式进行理论运算，求得其解的形式，用阶运算符 O 可表达为 T(n)= O(n)。那么对于实例来说，通过算法得出的结果是否符合线性时间呢？本次研究利用大量的实例，对该经典算法进行测试，观察实际得出的结果是否与理论值吻合，进而巩固该理论，使其能更好地应用于不同的领域。

1.4 本文的结构文献综述

本课题主要研究经典的线性时间选择问题，分为递归算法和非递归算法两种。本文余下的内容这样安排：第二章介绍相关技术的知识，递归、分治以及实验结果分析所需的绘图知识。第三章介绍递归求解线性时间选择问题，对递归的选择算法时间复杂度进行理论和实验分析。第四章介绍非递归求解选择问题，对算法的时间复杂度进行理论和实验分析。最后部分是本课题的结论。

2 相关技术的研究

2.1 递归

顾名思义，递归即自身调用自身。直接或间接地调用自身的算法称为递归算法，用函数本身给出定义的函数称为递归函数。在计算机算法设计与分析中，递归策略是十分有用的。它通常把一个规模较大较复杂的问题层层递归分解为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序便可清晰明了地处理了问题求解过程中多次重复的计算，大大地减少了程序的代码量，同时使得设计出的算法简捷易懂、易于分析。有些数据结构，如二叉树等，因为自身固