分治算法应用举例_选择问题、选最大与最小、选第 k 小_利用分治法设计算法并编程实现解决以下两个选择问题(注意:不能对全部集合排序): 1-程序员宅基地

技术标签: 算法  分治算法  选择问题  选最大最小  选第二大  

选择问题

  • 输入:集合L (含n个不等的实数)
  • 输出:L中第 i 小元素
  • i=n,称为最大元素
  • i=1,称为最小元素
  • 位置处在中间的元素,称为中位元素
  • n为奇数,中位数唯一,i= (n+1)/2
  • n为偶数,可指定 i= n/2+1

选最大或最小

  • 算法:顺序比较,依次比较序列中的所有数,保存每次比较的较大值或较小值。
  • 时间复杂性:W(n-1)

同时选最大与最小

通常算法

  1. 顺序比较,先选最大max。
  2. 顺序比较,在剩余数组中选最小min,类似于选最大算法,但比较时保留较小的数。
    时间复杂性:W(n) = n-1 + n-2 = 2n-3

分组算法

  • 最坏情况时间复杂度3n/2-2

分治算法

  • 将数组 L 从中间划分为两个子数组 L1 和 L2
  • max = max { max1,max2 }
  • min = min { min2,min2 }
  • L1 和 L2 分别再分组,递归地在 L1 中求 max1 和 min1,递归地在 L2 中求 max2 和 min2
  • 最坏情况时间复杂度 3n/2 -2

选第二大

输入:n 个数的数组 L
输出:第二大的数
通常算法:顺序比较
1.顺序比较找到最大max
2.从剩下n -1个数中找最大,就是第二大(再次调用找最大)
时间复杂度:W( n ) = n -1 + n - 2 = 2n - 3

提高效率的途径

  • 成为第二大数的条件:仅在与最大数的比较中被淘汰。
  • 要确定第二大数,必须知道最大数。
  • 在确定最大数的过程中记录下被最大数直接淘汰的数。
  • 在上述范围(被最大数直接淘汰的数)内的最大数就是第二大数。
  • 设计思想:用空间换时间

锦标赛算法

  1. 两两分组比较,大者进入下一轮,直到剩下 1 个元素 max 为止。
  2. 在每次比较中淘汰较小元素,将被淘汰元素记录在淘汰它的元素的链表上。
  3. 检查 max 的链表,从中找到最大元,即第二大。
  • 实例:
    在这里插入图片描述
  • 时间复杂度分析
    第一阶段:元素数为n,比较次数为n-1,淘汰了n-1个元素
    第二阶段:元素数为logn比较次数为logn-1淘汰元素数为logn-1
    时间复杂度是W(n) = n - 1 + logn - 1 = n + logn - 2

一般性选择问题

  • 问题:选第 k 小。
  • 输入:数组 S,S 的长度 n,正整数 k,1<=k<=n。
  • 输出:第 k 小的数。

简单算法

  1. 调用k次选最小算法,时间复杂度为 O (k n) 。
  2. 先排序,然后输出第 k 小的数,时间复杂度为 O(n logn)。

分治算法

假设元素彼此不相等

设计思想:

  • 用某个元素 m* 作为标准将 S 划分成 S1 与 S2,其中 S1 的元素小于 m*,S2 的元素大于等于 m*。
  • 如果 k <= |S1|,则在 S1 中找第 k 小;如果 k = |S1| + 1,则 m* 是第 k 小,如果 k > |S1| + 1,则在 S2 中找第 k - |S1| - 1小。
  • 算法效率取决于子问题规模,如何通过 m* 控制子问题规模?
    将所有数分组并在组内排序,找到每组的中位数的中位数,就是 m* 的值。
    在这里插入图片描述实例中,B 中数据比 m* 大,C 中数据比 m* 小,A、D中的数据无法判断,即 8,7,10,4 需要与 9 比较。
  • 归约为子问题,递归实现。
    在这里插入图片描述

选择问题的算法分析

在这里插入图片描述
算法的时间复杂度:W(n)=O(nlogn)

递归调用

  1. 求 m* 的工作量与 |M| = n / t 相关,t 为每组元素数,t大,|M| 小。
  2. 归约后子问题大小与分组元素数 t 有关,t 大,子问题规模大。
  3. |M| 与归约后子问题规模之和小于 n,递归树每行的工作量构成公比小于 1 的等比级数,算法复杂度是 O(n)。
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43239560/article/details/104594959

智能推荐

在下拉列表框中实现placeholder_下拉框placeholder-程序员宅基地

文章浏览阅读1.1k次。我们知道表格的input只要有输入框,一般都可以设置Placeholder来提醒用户。然而,下拉列表外观类似一个输入框,却无法设置placeholder。这里采用一个替代的方式实现,我们可以把第一个选项设置为代替的“提示选项”,将其默认设置为selected和disabled,这样用户也不会误选这个选项。<select name="role" required> <option selected disabled value="">选择你的职业</._下拉框placeholder

Andoid TextView显示富文本html内容及问题处理_android textview html-程序员宅基地

文章浏览阅读2w次,点赞4次,收藏4次。html_android textview html

AVR 328pb串口基本介绍和使用-程序员宅基地

文章浏览阅读928次,点赞18次,收藏17次。AVR 328pb串口基本介绍和使用

MTK开发笔记-程序员宅基地

文章浏览阅读979次。MTK开发笔记1. Windows必须安装在C盘,否则会出现modis编译问题。2. 语言和输入法移植2.1 资源修改 – 这是我们需要修改的,2.2开始MTK已经帮你做好了。2.1.1 在\plutommi\Customer\CustResource\PLUTO_MMI\ref_list.txt中添加新语言的字符串资源。2.1.2

通信原理学习笔记-第一章《绪论》_rb=rb*h-程序员宅基地

文章浏览阅读919次,点赞7次,收藏15次。目录1.本节要点:2.通信系统模型3.通信系统概念解释1信源:信息产生源头2信道:传输信号的物理介质4.通信系统通信方式5.通信系统性能指标5.1有效性 5.2可靠性1.本节要点: 通信基本概念 通信模型、分类、通信方式 信息的度量 通信性能指标2.通信系统模型(1)一般模型(2)..._rb=rb*h

MR工作流程-程序员宅基地

文章浏览阅读647次。9)MRAppMaster分配在那些NM上运行map(即yarnchild进程),reduce任务。1)执行hadoop jar命令之后,生成RunJar进程,客户端向RM申请一个job。10)运行map和reduce任务的NM,向资源共享文件系统获取job相关资源。12)job任务结束后,MRAppmaster向RM注销自己,然RM回收资源。3)客户端提交相关资源(jar,xml)到共享文件系统(HDFS)2)RM向客户端发送job资源的提交路径,生成jobID。11)运行map,reduce任务。..._mr工作流程

随便推点

python读取xml节点_1.23_python pyqt5 qtextedit 获取xml所在节点-程序员宅基地

文章浏览阅读6.6k次。xml文件节点一般分文三类: 1、元素节点 (比如:Class、student)2、文本节点 (比如:标签对里有内容的,name、age)3、属性节点 (比如:login里的信息,包含用户、密码) 每个节点都拥有包含着关于节点信息的属性。这些属性是:nodeName(节点名称)nodeValue(节点值)nodeType(节点类型) 一、读取xml..._python pyqt5 qtextedit 获取xml所在节点

USB可安全地从计算机移除,遇到USB设备故障,怎样免费恢复丢失的USB数据?-程序员宅基地

文章浏览阅读2.1k次。原标题:遇到USB设备故障,怎样免费恢复丢失的USB数据?不难想象,USB数据丢失问题正在发生。正因为我们频繁使用这种设备,才使得USB数据恢复成为一个热门话题。您是那些在USB设备上遇到数据丢失问题的人之一吗? 不要惊慌; 我们写这篇文章来提供高质量但免费的USB数据恢复服务。 您准备好自己恢复USB数据吗? 请先下载迷你兔数据恢复工具,然后根据需要将其安装到驱动器中。之后,您需要查看软件中的提..._usb composite device事件已删除设备如何恢复

hide handkerchief(第一周f题)辗转相除_初中数论奥数辗转相除例题-程序员宅基地

文章浏览阅读402次。DescriptionThe Children’s Day has passed for some days .Has you remembered something happened at your childhood? I remembered I often played a game called hide handkerchief with my friends. Now _初中数论奥数辗转相除例题

centos7下jenkins安装与配置-程序员宅基地

文章浏览阅读796次。CentOS 7 安装 Jenkins如果你的系统没有自带git,那么也需要安装一个yum install git1.安装第一种方法sudo wget -O /etc/yum.repos.d/jenkins.repo https://pkg.jenkins.io/redhat-stable/jenkins.reposudo rpm --import https://pkg.jenkins.io/redhat-stable/jenkins.io.keyyum install je

机器学习发展历史回顾_机器学习历史-程序员宅基地

文章浏览阅读4.9k次,点赞7次,收藏31次。机器学习发展历史回顾本文为回溯机器学习发展历史阅读笔记,全文链接:机器学习发展历史回顾在之后的学习中会以此为学习路线,逐步阅读所有机器学习方面的经典论文,并对本文中简略提及的算法进行总结和详细分析。1 概述机器学习是现阶段解决很多人工智能问题的主流方法。最早的机器学习算法可以追溯到20世纪初,到今天为止,已经过去了100多年。从1980年机器学习称为一个独立的方向开始算起,到现在也已经过去了近40年。2 分类总体上,机器学习算法可以分为有监督学习,无监督学习,强化学习 3种类型。半监督学习可以认_机器学习历史

Qt:子类发送消息给父类_qt 类 a 的信号发给 appevent 类-程序员宅基地

文章浏览阅读559次。例子:比如QWidget发送消..._qt 类 a 的信号发给 appevent 类

推荐文章

热门文章

相关标签