随机化快速选择算法的时间复杂度理论分析与实验研究(2)
时间:2018-11-26 11:18 来源:毕业论文 作者:毕业论文 点击:次
3.2.2 随机化的选择算法 15 3.3 实验结构设计 16 3.3.1 快速选择算法部分 16 3.3.2 随机化的选择算法部分 16 4 实验结果分析 17 4.1 快速选择算法的研究 17 4.1.1 波形图初步分析 17 4.1.2 输入数组对时间复杂度的影响 18 4.1.3 时间复杂度的最大值 22 4.1.4 时间复杂度的中位数 24 4.1.5 子序列长度对时间复杂度的影响 25 4.1.6 快速选择算法实验小结 27 4.2 随机化的选择算法的研究 27 4.2.1 时间复杂度的研究 27 4.2.2 时间复杂度的平均值 28 4.2.3 时间复杂度的最大值 30 4.2.4 时间复杂度的最小值 32 4.2.5 随机快速选择算法实验小结 32 结 论 34 致 谢 35 参考文献36 1 引言 1.1 选题背景与研究意义 算法是计算机科学的灵魂，某些经典的算法往往只有很少几行，但是却能解决很多大问题，就比如快速排序算法。并且算法是对编程思想的一种浓缩，往往看似越简单的算法，蕴含着越多的精华，并且更值得我们更深入的去学习和研究。而对算法进行研究，从表面上可以让我们更好的了解该算法，了解它的特性，从深层次来说，可以提高自我修养，对算法甚至对计算机科学有更高的认识。 排序是计算机科学中最重要的研究问题之一，2000年被列为20世纪对科学和工程计算的研究与实践影响最大的10大问题之一[2]。对于一个无序的数列，对其进行排序后，我们将获得我们想要的相应的数据。尤其是在当下的一个大数据时代，为了获得想要的数据，最简单的办法便是将其排序，然后再得到需要的任何数据。然而，有些时候，我们只是为了获得其中的少部分或者极少部分的数据，但是将其整个进行排序将花费我们大量的时间，于是我们便可以有针对性的只获得我们想要的数据。例如，我们只想获得一个数组中第k小的元素，当数组元素较小时，我们可以将数组进行排序，然后获得第k小元素。但是当数组元素过于庞大，这样做就会太浪费时间。最好的做法便是通过相应算法直接得到第k小元素，即随机化的快速选择算法和快速选择算法。这便有了我们本次的研究课题：随机化快速选择算法的时间复杂度理论分析与实验研究。 本课题是从《算法设计与分析》课程内容凝练并拔高出来的，立足于课本教学内容，但超越课本和大纲，属于探究式研究学习的内容。 快速选择算法目的是从n个数中不经过任何排序而能够快速地找到第k小元素。众所周知，排序算法在最坏情况下的最好时间复杂度是O(nlogn)。而快速选择算法的时间复杂度可以达到O(n)，即线性阶，但遗憾的是线性系数比较大，且随着划分的子序列长度而变化，具有不确定因素。我们设计并进行了一系列实验，探讨其线性时间复杂度与子序列长度的变化关系，旨在寻找该算法的最优时间复杂度。 另一方面，随机化的快速选择算法是在快速选择算法的基础上改造而成的随机算法，其基准元素由随机算法生成。可以证明[1]，随机化的选择算法的期望时间复杂度C(n)不超过4n，与快速选择算法相比，大大减小了算法运行时间。注意这里的“期望”的含义是关于对算法的随机变量求数学平均，并没有细致地给出求每个第k(k=1,2,…,n)小元素时的时间耗费情况。我们认为，在实际工程或应用研究中，由于问题的多样性，k的大小是变化的，文献[1]的分析仅仅考虑了问题输入规模n对算法期望时间复杂度的影响，粗略地给出了随机算法的期望时间复杂度的上界。我们考虑了k变化时的情况，通过理论分析和实验研究两种途径，从更小的信息粒度意义上深入研究了这个随机算法，研究了算法期望时间复杂度的下界，得到一个更为紧致的上界和关于平均时间复杂度的一个紧上界。 (责任编辑：qin) |