算法分析与复杂度理论实验作业.docx

PAGE 14 算法分析与复杂度理论 实验作业 1.第一题 1.1思路设计 整体算法设计过程参考快速选择算法RANDOMIZED-SELECT算法对xi的快速排序算法的partition进行了改进将判断条件修改为寻找使xixkwi满足的最小k位置可以实现在最坏情况为O(n)的时间内 算法的基本步骤如下 递归调用WSELECT 首先将n个元素划分为n/5个分组每个分组有5个元素其中最后一分组小于等于