【算法笔记】递归树应用实例:计算归并排序平均时间复杂度__gamer的博客-程序员秘密

技术标签: 归并排序  时间复杂度  递归树  算法与数据结构  

递归树

递归树是迭代的图形表示,可用于求解递推方程。


例1:利用递归树计算归并排序的平均时间复杂度。

归并排序伪代码:

MergeSort(A,p,r)
{
    
	if(p<r)
	{
    
		q = (p+r)/2;
		MergeSort(A,p,q);
		MergeSort(A,q+1,r);
		Merge(A,p,q,r);	//合并两个子数组
	}
	
}

根据以上的伪代码,可以写出归并排序的递推方程:
W ( n ) = 2 W ( n / 2 ) + n − 1 W(n) = 2W(n/2) + n-1 W(n)=2W(n/2)+n1
W ( 1 ) = 0 W(1) = 0 W(1)=0
其中, 2 W ( n / 2 ) 2W(n/2) 2W(n/2)表示对2个子问题进行归并排序, n − 1 n-1 n1表示合并2个有序的子数组的工作量(需要进行 n − 1 n-1 n1次比较)。

假设则递归树总共有k层, 则有 n = 2 k n = 2^k n=2k

举例,假设k=3,也就是n=8,则递归树有3层。

  • 第一层,每个节点的工作量为8,求W(8),对2个长度为4的有序数组进行合并,需要8-1=7次比较。
  • 第二层,每个节点的工足量为4,求2个W(4),对2个长度为2的有序数组进行合并,各需要4-1=3次比较
  • 第三层,每个节点的工足量为2,求4个W(2),对2个长度为1的有序数组进行合并,各需要2-1=1次比较,毕竟2个数比大小,1次比较就够了。

回到一般情况,画出递归树:

上述递归树共有k层,将右侧的所有值相加,结合等比数列求和公式,得到:
W ( n ) = ( n − 1 ) + ( n − 2 ) + ( n − 4 ) + . . . + ( n − 2 k − 1 ) = k n − ( 1 + 2 + 4 + . . . + 2 k − 1 ) = k n − ( 2 k − 1 ) \begin{aligned} W(n) &amp;= (n-1) + (n-2) + (n-4) +...+ (n-2^{k-1})\\ &amp;=kn - (1+2+4+...+2^{k-1})\\ &amp;=kn-(2^k-1) \end{aligned} W(n)=(n1)+(n2)+(n4)+...+(n2k1)=kn(1+2+4+...+2k1)=kn(2k1)

因为 n = 2 k n = 2^k n=2k,有
W ( n ) = n log ⁡ 2 n − n + 1 \begin{aligned} W(n) &amp;= n\log_2n-n+1 \end{aligned} W(n)=nlog2nn+1
所以,
T ( n ) = Θ ( n log ⁡ n ) T(n) = \Theta(n\log n) T(n)=Θ(nlogn)


参考资料:https://www.icourse163.org/course/PKU-1002525003

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/MASILEJFOAISEGJIAE/article/details/88399319

智能推荐

java_HashMap实现简易文字小城堡游戏(封装,继承的练习,低耦合)_KaiKai-G的博客-程序员秘密

界面以及控制端//城堡游戏 import java.util.HashMap; import java.util.Scanner; public class Game { private Room currentRoom; private HashMap&lt;String,Handler&gt; handlers =new HashMap&lt;String ...

Jenkins+Docker一键自动化部署Java Spring Boot 应用最简单详细流程_这把躺赢的博客-程序员秘密_docker+jenkins+springboot全自动部署

本文章实现最简单全面的Jenkins+docker+springboot 一键自动部署项目。步骤齐全,少走坑路。环境:centos7+git(gitee)简述实现步骤:在docker安装jenkins,配置jenkins基本信息,利用Dockerfile和shell脚本实现项目自动拉取打包并运行。有问题留言,看到会及时回复。一、安装dockerdocker安装社区版本CE1.确保 yum 包更新到最新。yum update2.卸载旧版本(如果安装过旧版本的话)yum remove doc

windows+caffe+vs2013+cuda6.5配置记录_查志强的博客-程序员秘密

【原文:http://www.mamicode.com/info-detail-850073.html】隔了大半年,因为论文的需要,又重新开始研究caffe。感谢niuzhiheng’s GitHub大神的贡献,caffe已经可以在Windows下使用了。参考了很多大神的博客,成功的在自己的笔记本配置好了Windows版本的caffe。现将自己的配置过程和配置中遇到的问题记录下来,希望

机器视觉检测中的图像预处理方法_机器学习算法那些事的博客-程序员秘密

本文以Dalsa sherlock软件为例,一起来了解一下视觉检测中平滑模糊的图像处理方法。1.观察灰度分布来描述一幅图像称为空间域,观察图像变化的频率被称为频域。2.频域分析:低频对...

SQL之更新数据以及空值处理_anansec的博客-程序员秘密_updatesql有空值不更新

前面有了SQL中select模块的详细介绍,那么与之对应的增删改也应该被关注,于是乎拿出我的数据库系统概论就是一顿细读,下面呢将我今晚的理解写于下方,希望对于正在看文章的你有所帮助!数据更新1、插入数据INSERT INTO Student(name,email) VALUES('张三','[email protected]'); --指定列进行插入INSERT INTO Student VAL...

div中追加内容的几种情况与div中内容隐藏与显示的问题_listener_life的博客-程序员秘密

div中追加内容的几种情况与div中内容的隐藏与显示的问题

随便推点

CentOS7 yum安装Tomcat并实现多域名与虚拟目录配置_青峰的博客-程序员秘密

最近正在学习开发servlet,在学习搭建服务器的时候遇到了不少问题,现在总结一下,留个笔记以备后用。一、安装Tomcat Tomact需要基于Java环境运行,所以同时需要安装java。yum install java-1.8.0*yum install tomcat1212二、多域名及虚拟目录的配置 用过yum安装好的Tomact的目录在 /usr/share/t

reader read()==-1中文问题_zhhaogen的博客-程序员秘密

在某次处理reader中,该流中含有中文字符,代码如下 Reader r = null; try { char c = (char) r.read(); while ((byte) c == -1) { // Do ... c = (char) r.read(); } } catch (IOException e) { e.pri

电流环扰动观测器、PI参数自动生成 观测器对扰动进行补偿,能有效提高电流环抗扰动能力_「已注销」的博客-程序员秘密_pi观测器

电流环扰动观测器、PI参数自动生成观测器对扰动进行补偿,能有效提高电流环抗扰动能力,并且能对反电势扰动起到很好的作用,效果如图所示…“钳位式“抗积分wind-up设计;文档详细介绍了使用规范地使用控制理论设计PI控制器的方法,PI参数由时域指标tr或者ts确定,而不是依赖祖传经验凑试…:53200625826049970求道电机控制...

GPON学习总结--gemport mapping_Calm_027的博客-程序员秘密_gemport

在G984.4和G988中所有篇幅都在介绍Managed entities(ME)。ME是ONU能力和业务的一种抽象模型,我们在OLT端开发GPON大部分的资源也是完成ME的配置和管理。1:在OLT上管理ME实现对ONU的配置管理;2:OLT上实现ONU的业务流转发模型,保证ONU业务正常,就是所说的gemport mapping 。一:单桥和多桥概念最

Java IO流(输入输出操作)_liu__jiang的博客-程序员秘密

Java IO流(输入输出操作)Java中执行输出和输入操作,需要通过IO流。例如最常见的System.out.println()就是一个输出流。IO流的类比较多,但核心体系就是由File、InputStream、OutputStream、Reader、Writer和Serializable(接口)组成的,后续会一一详细说明。I/O流基础概念按照流的方向分为输入流(InputStr...

DOM 文档对象模型详解_TDTE的博客-程序员秘密

节点及其类型:1). 元素节点2). 属性节点: 元素的属性, 可以直接通过属性的方式来操作.3). 文本节点: 是元素节点的子节点, 其内容为文本.在 html 文档的什么位置编写 js 代码?0). 直接在 html 页面中书写代码.Click Me!缺点:①. js 和 html 强耦合, 不利用代码的维护②. 若 click 相应函数是比较复杂的, 则需要先定义一...

推荐文章

热门文章

相关标签