腾讯云

文章/答案/技术大牛

发布

社区首页 >问答首页 >递归关系的运行时

问递归关系的运行时
EN

Stack Overflow用户

提问于 2013-03-14 17:59:22

回答 1查看 213关注 0票数 1

刚刚做了一个测验: T(n) = 4T(sqrt(n)) +5

我用代换简化了它，得到了F(k) = 4F(k/2) +5

使用主定理，我猜它是O(logn)。这是准确的吗？

algorithm

complexity-theory

relation

recurrence

master-theorem

回答 1

Stack Overflow用户

回答已采纳

发布于 2013-03-14 18:37:39

定义

F(n) = T(2^n)

然后我们就有了那个

F(n) = 4F(n/2) + 5

根据主定理，我们得到了

a = 4
b = 2
f(n) = 5 = O(1) = O(m^0), so c = 0
0 < 2 = log_2(4)

所以我们在主定理的情况1中。在第一种情况下，我们有

F(n) = Theta(n^2)

所以

T(2^n) = Theta(n^2)

因此

T(n) = Theta(log(n^2)) = Theta(2logn) = Theta(log n)

所以，是的，你的答案似乎是正确的。

票数 2

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

原文链接：

https://stackoverflow.com/questions/15416779

复制

递归简论递归的重要法则

编程算法

递归的重要法则基准情形：必须总要有基准的情形，它们不用递归就能求解不断推进：递归求解过程中总能朝着一个基准的情形推进假设所有递归都能正常运行合成效益法则：求解同一问题的实例，切勿在不同递归做重

用户2436820

2018/09/05

4980

C# (类型、对象、线程栈和托管堆)在运行时的相互关系

c#.net

在介绍运行时的关系之前,先从一些计算机基础只是入手,如下图: 该图展示了已加载CLR的一个windows进程,该进程可能有多个线程,线程创建时会分配到1MB的栈空间.栈空间用于向方法传递实参,方法

郑小超.

2018/01/26

1.5K0

4.3递归运行的机制：递归的微观解读

编程算法

前言：在4.1节和4.2节中我们分别通过数组以及链表对递归进行了应用，那时我们只是对递归进行了宏观理解--递归是将问题化为更小问题的子过程。这一节我们对在4.1节中递归在数组中的应用和4.2节中递归在链表中的应用进行微观解读：

wfaceboss

2019/04/08

4530

PostgreSQL 使用递归SQL 找出数据库对象之间的依赖关系 - 例如视图依赖

数据库迁移递归对象函数

在数据库中对象与对象之间存在一定的依赖关系，例如继承表之间的依赖，视图与基表的依赖，主外键的依赖，序列的依赖等等。

保持热爱奔赴山海

2023/03/25

1.4K0

递归求数组的和_java递归教程

编程算法 java c++打包

给定一个含有n个元素的整型数组a，求a中所有元素的和。问题的难点在于如何使用递归上。如果使用递归，则需要考虑如何进行递归执行的开始以及终止条件，首先如果数组元素个数为0，那么和为0。同时，如果数组元素个数为n，那么先求出前n-1个元素之和，再加上a[n-1]即可。此时可以完成递归功能。总之，递归就是在某个函数的执行过程中首先判断它的终止条件参数，终止条件参数满足终止条件则执行完毕，终止条件参数不满足终止条件则调用它自身执行某项运算，比如这里求和就是执行加法。凡是递归一定都有一个参数作为终止条件，比如这里是数组中未加入求和队列的元素个数，初始为数组长度。因为终止条件参数的初始值为数组长度，所以从数组的最后一个元素作为求和队列的第一个元素开始，每递归一次就将数组中的一个元素划归到求和队列中，同时将终止条件参数减1，直到其未为0，标明所有元素都已加入求和队列，返回求和队列的值即可。可见递归至少有两个参数，终止条件参数以及递归对象。

全栈程序员站长

2022/09/28

1.4K0

递归与伪递归区别，Python 实现递归与尾递归

编程算法

递归函数在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。(1) 递归就是在过程或函数里调用自身。(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

学到老

2019/02/14

1.5K0

二叉树的非递归遍历（递归和非递归）

数据结构编程算法

二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。一.前序遍历前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。 1.递归实现 void pre_order(BTree

猿人谷

2018/01/17

1.5K0

递归与伪递归区别，Python 实现递归与尾递归

python 编程算法

递归函数在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。(1) 递归就是在过程或函数里调用自身。(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。递归一般用于解决三类问题： (1)数据的定义是按递归定义的。（n的阶乘）　 (2)问题解法按递归实现。（回溯）　 (3)数据的结构形式是按递归定义的。（二叉树的遍历，图的搜索）递归的缺点：　　递归解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，

学到老

2018/03/16

2K0

递归的使用

编程算法

递归函数更实用于有规律的多项式数组，它可以让你的求和更方便，就如同高中学习的等差和等比数列，了解递归，你就可以用程序来做高中的数列题，还可以在你的弟弟妹妹面前装一手。

算法与编程之美

2022/02/17

5380

简单的递归

编程算法

简单的递归 void recurs(argumentlist) { statements1 if (test) recurs(arguments)

用户8247415

2021/04/13

3950

Python的递归

python 递归

state = 1def set_state(state): while state: set = int(input('请输入9或5,显示"hello world"\n')) if set == 9 or set == 5: print('hello world') state = int(input('输入1继续，输入0停止！\n')) else: print('请输入要求的值！')

狼啸风云

2020/06/11

8030

递归的理解

编程算法其他

百度百科：编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。

xyj

2020/07/28

3950

递归的机制

编程算法

public class 递归 { public static void main(String[] args) { testa=new test(); a.DG(4); } } class test{ public void DG(int n){ if (n>2) { DG(n-1); } System.out.println(n); }

姜姜178

2022/11/18

1890

awk的递归

人工智能 html

　　想来惭愧，之前写的一篇文章《用awk写递归》里多少是传递了错误的信息。虽然那篇文章目的上是为了给出一种思路，但实际上awk是可以支持函数局部变量的。

窗户

2018/08/01

6200

递归的思路

编程算法

递归分为两个子过程：递过程：函数不断地调用自身，直到走到函数的终止条件，第一阶段结束。归过程：函数不断地返回的过程。

VIBE

2022/12/02

2690

java运行时异常和非运行时异常区别_常用的运行时异常

java ide 编程算法

Java把异常当做对象来处理，并定义一个基类java.lang.Throwable作为所有异常的超类。Java中的异常分为两大类：错误Error和异常Exception，Java异常体系结构如下图所示：

全栈程序员站长

2022/11/11

1.1K0

递归与尾递归

编程算法腾讯云测试服务

云海谷天

2022/08/09

7660

PHP递归算法_后序遍历的非递归算法

php 对象存储 html c++编程算法

我们在建设一个网站的时候，程序员们首选的当属PHP语言。我们对PHP还是比较熟悉的，接下来我们将会为大家介绍一下PHP递归算法。PHP，一个嵌套的缩写名称，是英文超级文本预处理语言(PHP:Hypertext Preprocessor)的缩写。

全栈程序员站长

2022/09/22

2.5K0

java递归下降分析_JAVA中的递归下降

编程算法

// These token indicates end-of-expression

全栈程序员站长

2022/07/04

1.1K0

递归与尾递归

编程算法 javascript java

在介绍递归与尾递归之前，我们来看看递归的定义：程序调用自身的编程技巧称为递归（ recursion）

踏浪

2019/11/28

1K0

相似问题

解析递归关系的运行时间

递归关系

为什么在分析递归算法的运行时间时会出现递归关系？

递归关系

check BST函数的运行时和递归关系是什么？

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

问递归关系的运行时
EN

回答 1

Stack Overflow用户

解析递归关系的运行时间

递归关系

为什么在分析递归算法的运行时间时会出现递归关系？

递归关系

check BST函数的运行时和递归关系是什么？

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问递归关系的运行时EN

回答 1

Stack Overflow用户

解析递归关系的运行时间

递归关系

为什么在分析递归算法的运行时间时会出现递归关系？

递归关系

check BST函数的运行时和递归关系是什么？

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问递归关系的运行时
EN