在数据量日益庞大的今天，我们希望有效地从 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 递归

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