腾讯云

文章/答案/技术大牛

发布

社区首页 >问答首页 >求解递归T(n) = 4T(n/4) + 3log n的问题

问求解递归T(n) = 4T(n/4) + 3log n的问题
EN

Stack Overflow用户

提问于 2015-03-02 08:45:50

回答 1查看 1.1K关注 0票数 2

我对解决上面提到的问题感到很沮丧。我试着用大师的方法来解决这个问题，但我没有完成.

我有一个递归算法，需要3log n次(三个二进制搜索)来识别四个子问题，每个子问题的大小为n/4，然后单独求解，直到n小于输入给定的常量。因此，我得到了这样的结果：

T(n) = 4*T(n/4) + 3*log(n)

Base-Case if n < c (c = some constant given by program input):

T(n) = 1

我试图找到我的递归程序的渐近运行时间，并想用主定理来解决它。有人能告诉我是否可以用主定理与这个递推，如果是，这是主定理的哪一种情况？

非常感谢所有的帮助，谢谢。

asymptotic-complexity

performance

algorithm

recursion

回答 1

Stack Overflow用户

回答已采纳

发布于 2015-03-02 09:06:26

T(n) = O(n)，因为4基4的对数是1，3* log(n)是O(n ^ 0.5)(0.5 < 1)。它对应于描述这里的主定理的第一个例子。

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/28815073

复制

与 与标签的区别

搜索引擎 seo

与 用在网页上都能使字体加粗，二者的不同是：是物理元素 ;是逻辑元素。物理元素强调的是一种物理行为。比如说，把一段文字用b加粗，意思是告诉浏览器应该加粗显示，没有其他作用。而可以从字面理解知道它是强调的意思，是逻辑标签，强调文档逻辑。对于搜索引擎（SEO）来说，比重视的多。 和都是斜体，但是是逻辑元素，是物理元素。

windseek

2018/06/15

1.9K0

equals()与==的区别？

编程算法

== : 它的作用是判断两个对象的地址是不是相等。即判断两个对象是不是同一个对象。(基本数据类型==比较的是值，引用数据类型==比较的是内存地址)。

黑洞代码

2021/01/14

1.6K0

nohup 与 & 的区别

ssh https 网络安全

nohup -- invoke a utility immune to hangups : 运行命令忽略挂起信号

西湖醋鱼

2020/12/30

2.2K0

oracle与mysql结构区别_oracle与mysql的区别

oracle 数据库云数据库 SQL Server sql

oracle：可变长度varchar2、浮点型number，小数浮点型number(m,n)，可变二进制数据raw，大对象类型(存储无结构数据，最大4G)lob

全栈程序员站长

2022/10/05

3.7K0

%与mod的区别

%与mod的区别： %出来的数有正有负，符号取决于左操作数。。。而mod只能是（因为a = b * q + r (q > 0 and 0 <= r < q), then we have a mod q = r 中r要大于等于0小于q）。。。。。

杨鹏伟

2020/09/11

1.7K0

多线程thread与runnable的区别_handlerthread与thread的区别

网站 https 网络安全

按照MSDN上讲：“获取或设置一个值，该值指示某个线程是否为后台线程。” 其实这个解释并不到位，至少应该解释一下后台线程的概念！

全栈程序员站长

2022/11/08

1.1K0

CRM/PLM/SCM/MES与ERP的联系与区别

erp 企业

企业通过专设信息机构、信息主管，配备适应现代企业管理运营要求的自动化、智能化、高技术硬件、软件、设备、设施，建立包括网络、数据库和各类信息管理系统在内的工作平台，提高企业经营管理效率的发展模式。那么，在企业信息化建设中所用到的技术CRM、PLM、SCM、MES与ERP这些概念之间又有什么联系与区别呢？

用户5495712

2019/10/31

2.3K0

CharSequence与String的区别

编程算法

CharSequence与String都能用于定义字符串，但CharSequence是个接口，Sting实现了它。所以也可以把CharSequence看做String的父类。例如： public void setText(CharSequence string){ ... } public void setText(String string){ ... } 这2个方法可以同时存在一个类中，因为它们参数不同，都是setText()的重载。 (另外，在Android中，TextView的setText(

张拭心 shixinzhang

2022/05/06

7030

USART与UART的区别

https java 网络安全

USART(universal synchronous asynchronous receiver and transmitte): 通用同步异步收发器

全栈程序员站长

2022/07/21

8080

prepareStatement与Statement的区别

java 缓存数据库 linux sql

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/139855.html原文链接：https://javaforall.cn

全栈程序员站长

2022/09/03

3330

http与socket的区别

https 网络安全 http tcp/ip

手机能够使用联网功能是因为手机底层实现了TCP/IP协议，可以使手机终端通过无线网络建立TCP连接。TCP协议可以对上层网络提供接口，使上层网络数据的传输建立在“无差别”的网络之上。

全栈程序员站长

2022/08/05

5140

repository 与 dao的区别

存储数据库 sql

Repository是对象的仓库，也就是保存对象的地方，这个仓库就是我们普通意义的仓库，一个真正OO系统，业务层是围绕活动的对象进行，活动的对象是从仓库中获取的，也是通过交给仓库进行对象长久保管，也就是持久化意思，说白了，就是保存到数据库。而DAO则没有如此OO概念，DAO是Data access Object，DAO中有数据概念，还是没有摆脱数据库的影子。所以，Repository替代DAO，是OO深入的趋势，但是在具体处理中，由于性能或设计不够周到或者一些事情把握不定，DAO还会继续存在一段时间，属于过渡式消失。 Repository和DAO两个概念比较中发现，Repository是相对对象而言，而DAO是相对数据库而言，只要我们还是使用关系数据库保存对象，也可能这两者都同时存在，因为侧重点不一样，但是可以肯定的是，业务层应该直接和Repository打交道，而不是DAO.

乐事

2020/08/07

7K0

HTTP与HTTPS的区别

http 网站 https tcp/ip

超文本传输协议HTTP协议被用于在Web浏览器和网站服务器之间传递信息，HTTP协议以明文方式发送内容，不提供任何方式的数据加密，如果攻击者截取了Web浏览器和网站服务器之间的传输报文，就可以直接读懂其中的信息，因此，HTTP协议不适合传输一些敏感信息，比如：信用卡号、密码等支付信息。

软测小生

2019/07/05

8470

session与cookie的区别

网络安全存储网站

（4）设置cookie时间可以使cookie过期。但是使用session-destory（），我们将会销毁会话。

葆宁

2019/04/18

6890

进程与线程的区别？

word 并发程序进程线程

进程是什么？程序并不能单独运行，只有将程序装载到内存中，系统为它分配资源才能运行，而这种执行的程序就称之为进程。程序和进程的区别就在于：程序是指令的集合，它是进程运行的静态描述文本；进程是程序的一次执行活动，属于动态概念。在多道编程中（多道程序设计技术是在计算机内存中同时存放几道相互独立的程序），我们允许多个程序同时加载到内存中，在操作系统的调度下，可以实现并发地执行。这是这样的设计，大大提高了CPU的利用率。进程的出现让每个用户感觉到自己独享CPU，因此，进程就是为了在CPU上实现多道编程而提出的。

老九君

2018/03/06

2.3K1

线程与进程的区别

并发程序多线程进程线程

一个程序至少有一个进程，一个进程至少由一个线程线程的划分尺度小于进程，使得多线程程序的并发性高进程的执行过程中拥有独立的内存单元，而多个进程共享内存，从而极大的提高了程序的运行效率。线程在执行过程中与进程还是有区别的，每个独立的线程有一个程序的入口，顺序执行序列和程序的出口。但线程不能够独立执行，必须依存在于应用程序中。有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立作用，来实现进程的调度和管理以及资源分配，这是线程和进程的重要区别。进程是具有一定独立功能的程序关于某个数据集合上

莫问今朝

2019/02/25

8160

URI与URL的区别

其他

Web上可用的每种资源 - HTML文档、图像、视频片段、程序等 - 由一个通过通用资源标志符（Universal Resource Identifier, 简称"URI"）进行定位。 1.URI一般由三部分组成： 2.访问资源的命名机制。 3.存放资源的主机名。 4.资源自身的名称，由路径表示。考虑下面的URI，它表示了当前的HTML 4.0规范： http://www.webmonkey.com.cn/html/html40/ 这个URI是这样的：这是一个可通过HTTP协议访问

joshua317

2018/04/16

1.6K0

delete与delete[]的区别

ios

一直对C++中的delete和delete[]的区别不甚了解，今天遇到了，上网查了一下，得出了结论。做个备份，以免丢失。

瑾诺学长

2018/09/21

1.4K0

int与integer的区别

其他

int与integer的区别从大的方面来说就是基本数据类型与其包装类的区别： int 是基本类型，直接存数值，而integer是对象，用一个引用指向这个对象 1.Java 中的数据类型分为基本数据类型和复杂数据类型 int 是前者而integer 是后者（也就是一个类）；因此在类进行初始化时int类的变量初始为0.而Integer的变量则初始化为null. 2.初始化时：　　int i =1；Integer i= new Integer(1);(要把integer 当做一个类看)；但由于有了自动装箱和拆箱

Java帮帮

2018/03/16

1.1K0

NPAPI与PPAPI的区别

flash api windows

Adobe Flash Player PPAPI是Adobe Flash Player专为chrome内核而开发的，能够保证其在各种浏览器、操作系统和移动设备上使用。Flash开发的软件一般短小精悍，功能强大，兼容性高。文件后缀一般是swf，它能够让公司或个人构建出美妙的数字体验，使您能够在把交互式、丰富的内容与视频、图形和动画组合到一起的Web上，让用户享受最富表现力的、引人入胜的体验。

liuzhen007

2021/06/29

3.1K0

相似问题

ContentDispositionHeaderValue.FileName与asp.net内核中的IFormFile.FileName

==与===的区别

108

:+与&:+的区别

与的区别

<>与!=的区别

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

问求解递归T(n) = 4T(n/4) + 3log n的问题
EN