随机化快速选择算法的时间复杂度理论分析与实验研究(3)
时间:2018-11-26 11:18 来源:毕业论文 作者:毕业论文 点击:次
1.2 算法思想与策略评述 快速选择算法也就是寻找第k小元素，即从大小为n的数组中找到第k小的元素。在二分查找中，每经过一步，则问题规模缩小一半，而快速选择算法借鉴了二分查找的这种思想，即“以某个元素为基准（或称为枢轴），抛弃部分无关元素，不断减小问题规模，加快问题求解进程”的策略。区别在于：二分查找每次以（有序）序列的中间元素作为基准，而快速选择算法每次以（无序）序列的中位数（或近似中位数）作为基准，这是二者的重要区别。 然而，在一个无序序列中寻找中位数也是需要一定时间耗费的。为了加快求解进程，可以将基准元素必须是中位数这一要求放宽，改进为使用任何一个元素，从而诞生了随机化的快速选择算法。随机化算法是基于随机方法的一种算法，在算法中使用随机函数，基于随机函数的随机性，因此返回值直接或者间接的影响了算法的执行流程或执行结果。 随机算法可以做如下定义：它是在接收输入的同时，为了随机选择的目的，还接收一串随机比特流并且在运行过程中使用该比特流的算法。对于相同的输入，在不同的时间运行随机算法可以得到不同的结果，由此得出对于相同的输入两次不同的随机算法的执行时间可能不同。随着计算机科学的发展，我们也越来越认识到，随机化对于算法的构造在很大的应用范围内越来越重要。随机算法有两个主要的优点：首先，用随机算法解决同一问题时往往比确定性算法所需的运行时间或空间通常小一些，在某些平均运行时间比较低的确定性算法中，仅是引入随机性就能打破传统的确定型算法诸多条条框框的束缚，将一个自然、简单、在最坏情况下表现不好的算法转化成对于每一种可能的输入都有很高可靠性的随机算法；其次。观察迄今为止已经发明的各种随机算法，它们总是易于理解和实现的。 随机算法可以分为三大类，即Lsa Vegas型算法、Monte Carlo型算法和Sherwood型算法。Las Vegas型算法建立的那些随机算法总是或者给出正确的解，或者算法求解失败，但是再次运行算法就有成功的可能。而Monte Carlo型算法的随机算法正好相反，Monte Carlo型算法总是给出解，但是偶尔可能会产生非正确的解，但是可以使产生非正确解的概率减到任意小，即满足每次运行时的随机选择都相互独立的条件下，多次运行原算法，可以将算法的错误概率降低到任意小。Sherwood型算法的思想方法在于在原有的确定型算法基础上，引入随机化因素，改变问题的输入或求解顺序，设法消除算法的时间复杂度与输入实例之间的关系。本文研究的随机化快速选择算法即属于Sherwood型算法。 1.3 国内外的研究现状 1.4 本文所做的工作及贡献 本文主要是研究随机化的快速选择算法和快速选择算法。 首先对快速选择算法进行研究，分析其波形图的规律，并对算法的时间复杂度进行研究。然后改变子序列长度，观察时间复杂度的变化，探讨其线性时间复杂度与子序列长度的变化关系，旨在寻找该算法的最优时间复杂度。 接着从理论上分析随机化快速选择算法的平均时间复杂度，并进行实践验证，然后对快速选择算法的平均时间复杂度的最大值和最小值进行研究，从中发现一些规律。 最后，对随机化的快速选择和快速选择算法进行总结，得出相应的结论。 2 算法与时间复杂度分析 2.1 快速选择算法 寻找一个元素序列中第k小的元素的最直接的方法就是对所有的元素排序并取出第k小的元素，这个方法需要 时间，这种朴素的方法虽然貌似“超额完成任务”，实际上是对计算资源的浪费，对于n较大时更是如此，因为所需时间不菲。为了加快求解进程，可以借鉴二分查找算法关于“以某个元素为基准（或称为枢轴），抛弃部分无关元素，不断减小问题规模，加快问题求解进程”的策略。具体而言，就是设法寻找中位数作为比较的基准元素mm，将所有元素分为三个部分，即小于mm的、等于mm的和大于mm的三个序列，然后根据k与三个序列长度之间的大小关系，判断待查找的第k小元素位于哪个序列内，然后抛弃剩余的无关元素序列，使问题规模不断减小，继续上述进程，直到查找成功。其中，寻找中位数的具体做法是：将n个元素的集合每5个元素分为一组，求出每组元素的中项，将这些中项组成一个集合，然后递归调用算法本身，在一个较小的序列中寻找中位数，作为全部元素的中位数的一个最佳近似估计。该算法的伪代码如下： (责任编辑：qin) |