算法分析与设计作业6 选第k小元素（分治法）
发布时间
阅读量：
阅读量
1.问题
假设集合L包含n个元素，从中确定第K小的元素，其中K的取值范围为1到n之间。
2.解析框架构建
当k等于|S1|加1时，m*即为所求的第k小元素；若以m作为划分依据，比m小的元素个数恰好为|S1|个，此时若k正好等于|S1|加1，则m即为所求的第k小元素。若k小于等于|S1|，则问题可简化为在S1中寻找第k小元素的子问题，此时k在子问题中的位置保持不变，即k1等于k。若k大于|S1|加1，则问题转化为在S2中寻找第k2小元素的子问题，其中k2与原问题中的k存在对应关系，即k2等于k减去|S1|再减去1。因此，在S中寻找第k小元素的问题等价于在S2中寻找第k2小元素的问题。
还没有任何评论哟~