您所在位置：网站首页 > 办公文档 > 模板/表格 > 财务表格用随机算法求第k小项

用随机算法求第k小项

6页

卖家[上传人]：汽***

文档编号：476203134

上传时间：2024-01-03

文档格式：DOCX

文档大小：19.58KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 金贝

/ 6 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、1，问题描述设A1,n是一个有n个数组成的无序数列，寻找其第k小元素就是将A按照非递减的顺序排列后，新序列中的第k个元素。寻找第k小元素最直接的方法就是直接将A进行排序，然后取出第k个元素，但是此类方法时间复杂度较高，至少需要(nlogn)时间，因为基本所有已学的排序方法在最坏情况下都需要这么多时间。在第三章中老师课上教导了利用分治法求第k小元素的算法，其时间复杂度为O（n）。其基本思想如下：在分治法递归调用的每一个划分步骤中都将舍弃一定比例的元素，而在剩余元素中寻找目标。故在我的理解中这种分治法的性能主要依赖于每次递归调用能舍去的元素的比例，以及为舍弃这些元素所花费的代价。在之后的学习中，我们又接触到了随机算法，不由思考，分治法中的划分可以不可以通过随机算法来随机选择一个位置，然后根据这个位置进行舍弃序列中的元素，有没有办法改进算法。2，随机选择算法Algorithm: RandomSelect (Alow, high, k)输入：数组Alow,.high和整数k，1 k high-low+1输出：Alowhigh中的第k小元素v random(low,high)x Av将Al

2、owhigh分成三部分 A1a|a x /(n)case | A1 | k : return RandomSelect(A11, |A1|, k) | A1 |+| A2 | k : return x | A1 |+| A2 | k: return RandomSelect(A31,|A3|, k-|A1|-|A2|)end case该部分算法ppt与书上已经提到，其时间复杂度的期望比较次数C(n)4n，此外每个元素与基准元素x至少比较一次。故C(n)n及nC(n)4n,故时间复杂度为（n）这部分书上与ppt上已有证明就不过多论述了3，对以上随机算法的一种思考改进分析以上算法不难发现，其先随机选择一个位置v，然后根据v进行对元素的舍弃，所以每次舍弃不同个元素的概率是相同的，我就思考可不可以让选中舍弃较多元素的位置的概率更大，让算法有更大几率舍弃掉较多的元素。算法的想法如下：如果随机选择一个位置的元素进行比较，每个位置的可能性是均等的，取到的数值可能最大、最小，也可能中间，如果是最大最小的情况，每次舍弃的数值就只能有一个，只有尽可能的取大小排在中间的数值，才能舍去较大的元素，故我思考

3、，不妨选择随机选择两个位置，v,j令x=(Av+Aj)/2,然后通过x进行分组，这样取到数值为中间大小的数比取到最大最小值的可能性更高，舍弃较多数的几率更大。进而进行了优化。理论上，选择的随机位置越多，平均后，舍弃掉较多数的可能越大，但是这就退化近似成取中值进行分治法求第k小元素的方法，丧失了随机算法的优点，将直接随机到最优解和较优解的可能性也降低了，所以我尝试取2个随机位置的方法进行优化。并且当选择两个随机位置时，序列长度小于等于2个时，没有执行随机算法的必要先从一个特例分析其取到各位置的理论概率大小，令n=8，其取到不同位置的概率如下表（为表示清晰，v,j位置为A进行排序后的位置）由表格数据可以发现，此时数组划分数据x可能处于不同的位置的概率分为别为:3/64,7/64,11/64,15/64,13/64,9/64,5/64,1/64 显然舍去较多数的几率更高。改进的随机算法：Algorithm: NewSelect (Alow, high, k)输入：数组Alow,.high和整数k，1 k high-low+1输出：Alowhigh中的第k小元素If(high-low2)

4、thenIf(k=1) then return min(Alow,Ahigh)Else return max(Alow,Ahigh)End ifelsev random(low,high)j random(low,high)x （Av+Aj）/2将Alowhigh分成三部分 A1a|a x /(n)case | A1 | k : return NewSelect(A11, |A1|, k) | A1 |+| A2 | k : return x | A1 |+| A2 | k: return NewSelect (A31,|A3|, k-|A1|-|A2|)end case end if 该算法的最坏情况与最初算法是一致的，但是其舍弃较大数的可能性应该较大，下面进行时间复杂度的理论分析4，时间复杂度分析仿照ppt上对原算法的证明方式，证明如下（因为个人对数学公式符号用电脑表示不熟悉，而且因为证明较繁琐故用手写证明拍照如下，往老师见谅。）由证明可知，改进后的算法的时间复杂度也是（n），虽然数量级相同，但是其前系数还是减小了。模拟仿真：实际编程，比较实际情况中原算法与改进算法的执行次数，发现其是否有改进。为使数据明显，取n值较大，当n=5000时，不同k的执行次数如表格:当k不同时，进行数据拟合，结果如下及O(k)=-2.1nlogn -469.2logn+26.80n+11010.2706当n改变时，做出其一次关系式，改进后的算法时间复杂度绘图如下O(n)= 2.579n5，总结通过以上的分析证明，以及最后的数据拟合可以发现，改进后的算法在解决第k小元素的问题上，算法时间复杂度最小，故其对原算法进行了改进。明显可见，随机算法时间复杂度远好于确定型的算法的时间复杂度，改变随机算法随机出的情况的不同概率也可以进一步优化随机算法。

《用随机算法求第k小项》由会员汽***分享，可在线阅读，更多相关《用随机算法求第k小项》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源

沪教版五年级数学上学期期末考试知识点检测

习作教学应向生活开放

2023年生产管理部文员工作总结（精选多篇）

小学副校长工作职责（9篇）

小班教师个人工作计划

初中学校关工委工作总结

小班数学小熊糖果店

小学学校校本研修计划范本（6篇）.doc

经典实用汽车租赁合同电子版（三篇）.doc

2021-2022年三年级上册第5课《日记二则》word教案

写字楼租赁合同示范文本（DOC 25页）

山东省滕州市滕西中学九年级英语下学期第一次质量检测试题答案不全

注册会计师《审计》考前冲刺密押卷含答案87

初中数学易错题(全国通用-上海专用-含参考答案)

党风廉政建设十不准

财务试用期期间的工作总结（2篇）.doc

小韭兰苗木购买合同

承包合同范文7篇

【新教材】高考化学二轮基础演练：3.2.1水的电离和溶液的酸碱性含答案

2014广州小升初语文基础复习

点击查看更多

新上传的WORD文档

关于《生物入侵者》教学设计 2021年寻找最美孝心少年观后感技术改造借款合同范文（六篇）医院设备科工作制度范本（四篇）九年级语文科第一次月测试题参考答案 2023年简单易懂的合作协议书天津租房合同制药工艺设计开题报告中国医科大学21春《社会医学》离线作业2参考答案61 教师个人三年发展规划歌唱祖国的歌古镇旅游市场分析某灌区取水枢纽进水闸结构布置期货委托合同范本_1.doc 义务教育国家课程设置实施计划方案