递归函数的时间复杂度 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

分析递归函数的时间复杂度

递归算法的时间复杂度表达式： O(T) = R * O(s) O(T)表示时间复杂度 R表示递归调用的次数 O(s)每次递归调用计算的时间复杂度想想斐波那契函数，它的递归关系是f(n)...解释：这种情况下，我们最好是可以借助执行树，它是一颗被用来表示递归函数执行流程的数。树中的每一个节点代表递归函数的一次调用。所以，树中节点的总数与执行期间递归调用的数量相对应。...所以，我们可以估算出f(n)的时间复杂度就是O(2n) 备忘录备忘录技术是用来优化递归算法时间复杂度的技术。...通过缓存和重用中间结果的方式，备忘录可以极大地减少递归调用的次数，也就是减少执行树中分枝的数量。所以，当我们使用备忘录来分析递归算法的时间复杂度时候应该把这减少的部分考虑到。...现在我们就可以利用文章开头列出的公式来计算备忘录技术应用后的时间复杂度：O(1)n=O(n)。结论备忘录不仅优化算法的时间复杂度，而且还可以简化时间复杂度的计算。

7125 0

递归算法的时间复杂度

，第一层的遍历时间复杂度是n，第二层遍历的时间复杂度是n，内层的时间复杂度是O（n^2），再加上递归，最后的时间复杂度是O（2^n*n^2），这个算法可见很粗糙，假如递归深度到是100，最后执行效率简直会让人头皮发麻...第一层遍历时间复杂度是O(n)，加上递归，最后的时间复杂度是O(2^n*n)，不算太理想，最起码比第一次好点。再看看一个面试的常见的题目，斐波拉契数列，n=1,1,3,5,8,13......(n-2) 这个算法的时间复杂度是O(2^n)，关于时间复杂度具体看调用次数便能明白。...O(1)，这样这个算法的时间复杂度就是O(n)。...递归算法的优化大概就是避免重复运算，将中金状态保存起来，以便下次使用，从结构上来看，是将时间复杂度转换为空间复杂度来解决。

2.2K2 0

您找到你想要的搜索结果了吗？

是的

没有找到

递归时间复杂度推导

你好，我是zhenguo 今天这篇文章是一个资料精选，出自斯坦福大学课程讲义，5页PDF，来解决递归算法的时间复杂度。递归被广泛应用，尤其是分治思想，比如最常见的归并排序，最长字符前缀等。

2502 0

递归算法的时间复杂度分析

转自地址 http://blog.csdn.net/metasearch/article/details/4428865 在算法分析中，当一个算法中包含递归调用时，其时间复杂度的分析会转化为一个递归方程求解...这种递归方程是分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子问题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。...一、代入法大整数乘法计算时间的递归方程为：T(n) = 4T(n/2) + O(n)，其中T(1) = O(1)，我们猜测一个解T(n) = O(n2 )，根据符号O的定义，对n>n0，有...这里涉及的三类情况，都是拿f(n)与nlogb a 作比较，而递归方程解的渐近阶由这两个函数中的较大者决定。...在第一类情况下，函数nlogb a 较大，则T(n)=O(nlogb a )；在第三类情况下，函数f(n)较大，则T(n)=O(f (n))；在第二类情况下，两个函数一样大，则T(n)=O(nlogb

1.9K5 0

递归的时间复杂度（Master 公式）

我们在解决算法问题时，经常会用到递归。递归在较难理解的同时，其算法的复杂度也不是很方便计算。而为了较为简便地评估递归的算法复杂度，Master公式。...Master公式含义T(N):表示当输入规模为 N 时，算法所需的时间复杂度。N 通常代表问题的规模，比如数据的数量、数组的长度、图的顶点数等。a:表示子问题的数量。...在分治算法中，a 常常代表每次递归调用产生的子问题数量。例如，在归并排序中，a 的值为 2，因为每次递归调用会将问题分为两个子问题。T(N/b):表示每个子问题的时间复杂度。...O(N^d):表示除了递归调用之外，算法在每次递归步骤中所做的额外工作的时间复杂度。O(N^d) 是除了递归调用之外的时间开销的上界。d 是一个常数，表示额外工作的时间复杂度与 N 的关系。...，这样子的话不符合相同规模的划分，就不能使用 Master 公式来计算时间复杂度

1921 0

递归算法时间复杂度分析

递归算法时间复杂度分析时间复杂度：一般情况下，算法中基本操作重复的次数就是问题规模n的某个函数f（n），进而分析f（n）随n的变化情况并确定T（n）的数量级。...这里用‘o’来表示数量级，给出算法时间复杂度。 T（n）=o（f（n））；它表示随问题规模n的增大，算法的执行时间增长率和f（n）增长率成正比，这称作算法的渐进时间复杂度。...而我们一般情况下讨论的最坏的时间复杂度。空间复杂度：算法的空间复杂度并不是实际占用的空间，而是计算整个算法空间辅助空间单元的个数，与问题的规模没有关系。...经验和一些定理告诉我们，这些细节不会影响算法时间复杂度的渐近界。类似的，我们也可以用迭代法求解汉诺塔递归求解时的时间复杂度。但遗憾的是，迭代法一般适用于一阶的递推方程。...这个递推式将规模为n的问题分解为a个子问题，每个子问题的规模为n/bn/b，a个子问题递归地求解，每个花费时间T(n/b)T(n/b)。函数f(n)f(n)包含了问题分解和子问题解合并的代价。

2.6K2 0

剖析递归行为和递归行为时间复杂度的估算

一个递归行为的例子 master公式的使用 T(N) = a*T(N/b) + O(N^d) T(N)是样本量为N时的时间复杂度，N/b是划分成子问题的样本量，子问题发生了a次，后面O(N^d)是除去调用子过程之外的时间复杂度...(arr, mid + 1, R); return Math.max(maxLeft, maxRight); } T(N) = 2*T(N/2) + O(1); 这里划分成的递归子过程的样本量是...N/2，这个相同的样本量发生了2次，除去调用子过程之外的时间复杂度是O(1),因为求最大值和判断if复杂度是O(1),所以N^d=1，所以d=0....那么根据如下公式判断 1) log(b,a) > d -> 复杂度为O(N^log(b,a)) 2) log(b,a) = d -> 复杂度为O(N^d * logN) 3) log(b,a) 复杂度为O(N^d) 这里log(b, a)(以b为底a的对数) = log(2, 2)=1 > d=0 所以复杂度为O(N^log(2, 2))===>O(N)，因此也就可以解释为什么归并排序的时间复杂度为

1931 0

剖析递归行为和递归行为时间复杂度的估算

剖析递归行为和递归行为时间复杂度的估算 master公式：也叫主定理。它提供了一种通过渐近符号表示递推关系式的方法。应用Master定理可以很简便的求解递归方程。...master公式的使用递归行为形如: T(N) = a*T(N/b) + O(N^d) 均可用下面推到出时间复杂度 (1) log(b,a) > d -> 复杂度为O(N^log(b,a)) (2)...log(b,a) = d -> 复杂度为O(N^d * logN) (3) log(b,a) 复杂度为O(N^d) T(N)：递归的时间复杂度 N： ...递归行为的规模|样本数量 N/b：递归后子过程的规模 (b指的是子过程分为几块,比如递归比较运算是左右两块) a: 子过程调用次数 aT(N/b...): 所有子过程的时间复杂度 O(N^d) : 除去子过程之外剩下过程的时间复杂度注意： 1.使用master公式推到时间复杂度必须保证每次划分的子工程的规模是一样的如果形如:

5043 0

递归树：借助树来求解递归算法时间复杂度

利用递归树的时间复杂度分析方法并不难理解，关键还是在实战，所以，接下来我会通过三个实际的递归算法，带你实战一下递归的复杂度分析。学完这节课之后，你应该能真正掌握递归代码的复杂度分析。...，这个递归代码的时间复杂度会比较难分析。...这里我稍微说下，掌握分析的方法很重要，思路是重点，不要纠结于精确的时间复杂度到底是多少。内容小结今天，我们用递归树分析了递归代码的时间复杂度。...加上我们在排序那一节讲到的递推公式的时间复杂度分析方法，我们现在已经学习了两种递归代码的时间复杂度分析方法了。...有些代码比较适合用递推公式来分析，比如归并排序的时间复杂度、快速排序的最好情况时间复杂度；有些比较适合采用递归树来分析，比如快速排序的平均时间复杂度。

1.5K1 0

Master Method Restated-主项定理-递归时间复杂度

对于一个递归实现的分治算法，其时间复杂度表示为： T(n) = aT(n/b)+h(n) T(N)=aT(n/b)+O(N^d) b是规模 a是调用次数其中，a>=1; b>1; h(n)是不参与递归部分的时间复杂度...比较n^log b (a)与Θ(h(n)) 的大小（Θ的含义和“等于”类似，而大O的含义和“小于等于”类似，感觉好像这里都可以用）：若n^log b (a)= Θ(h(n)) ：该方法的复杂度为 Θ...(h(n)*log(n)) 若n^log b (a)的复杂度为 Θ(h(n)) 若n^log b (a)> Θ(h(n)) ：该方法的复杂度为 Θ(n^log b (a)...) 例如： T(n) = T(n/2)+1：Θ(log(n))（二分查找） T(n) = 2T(n/2)+n ：Θ(n*log(n))（归并排序）以上都属于“等于”的情况。

7612 0

一场面试，带你彻底掌握递归算法的时间复杂度

很多同学对递归算法的时间复杂度都不甚了解同一道题目，同样使用递归算法，有的同学写出了O(n)的代码，有的同学就写出了O(logn)的代码这是为什么呢，就是因为对递归的时间复杂度理解的不够深入导致的...如果恰巧正在读本文的你也对递归算法的时间复杂度懵懵懂懂，请认真读完本篇文章，一定会有所收获这里我想通过一道简单的面试题，来带大家逐步分析递归算法的时间复杂度，最后找出最优解。...每次n-1，递归了n次时间复杂度是O(n)，每次进行了一个乘法操作，乘法操作的时间复杂度一个常数项O(1) 所以这份代码的时间复杂度是 n * 1 = O(n) 这个时间复杂度可能就没有达到面试官的预期...这个结论在二叉树相关的面试题里也经常出现。这么如果是求x的n次方，这个递归树有多少个节点呢，如下图所示 ? 时间复杂度忽略掉常数项-1之后，我们发现这个递归算法的时间复杂度依然是O(n)。...如果同学们最后写出了这样的代码并且时间复杂度分析的非常清晰，相信面试官是比较满意的。最后希望通过这么一个简单的面试题，让大家真正了解了递归算法的时间复杂度该如何分析。

6771 0

时间复杂度

所以，可以用程序的执行步骤来描述时间复杂度，而程序执行的步骤可以表示成问题规模 n 的一个数学函数 T(n)。...而且，平均时间复杂度也会因为程序运行时间的不均匀分布(除非一次函数)而难以计算。最坏时间复杂度提供了一种保证，表明程序在此时间内一定能完成工作。因此，一般都是计算最坏时间复杂度。 ?...三、时间复杂度的大O记法时间复杂度常用大O记法来表示。时间复杂度可以表示成一个问题规模n的数学函数T(n)，大O记法是用一个与该数学函数渐近的简化数学函数来表示时间复杂度。...一般情况下，程序的时间复杂度是问题规模n的某个数学函数，用T(n)表示，若有(一定有)某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，函数T(n)的增长速度主要受函数...记作T(n)=O(f(n))，称O(f(n))为程序的渐近时间复杂度，简称时间复杂度。大O记法只关注时间复杂度数学函数的最高次项，忽略了其它低次项和常数项，同时忽略了最高次项的系数。

7132 0

时间复杂度

算法时间复杂度定义时间复杂度的定义是：如果一个问题的规模是n，解决这一问题所需算法所需要的时间是n的一个函数T(n)，则T(n)称为这一算法的时间复杂度。算法中基本操作的执行次数。...既然是T(n)的函数，随着模块n的增大，算法执行的时间的增长率和T(n)的增长率成正比，所以T(n)越小，算法的时间复杂度越低，算法的效率越高。通过时间的复杂度来看算法执行的好坏。...常见的算法时间复杂度时间复杂度与空间复杂度区别时间复杂度：全称渐进式时间复杂度，表示算法的执行时间与数据规模的增长关系；空间复杂度：全称渐进式空间复杂度，表示算法的存储空间与数据规模增长关系；...根据基本操作执行情况计算出规模n的函数f(n),并确定时间复杂度为T(n)=O( f(n)中增长最快的项/此项的系数 )。...而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。均摊时间复杂度就是一种特殊的平均时间复杂度

7011 0

时间复杂度

什么是时间复杂度？定性描述该算法的运行时间，一个函数、用大 O 表示，例如 O (1)、 O (n)、O (logN) ......(2 ^ n) 上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。...javascript for (let i = 0; i < n; i++) { console.log(i) } O(1) + O(n) = O(n) 当两个时间复杂度的代码在一块时，以时间复杂度较大的为准...，得到的结果就是真实的时间复杂度。...当时间复杂度进行相加时，却可以忽略不计。

2440 0

时间复杂度

今天用10分钟的时间,介绍下算法中最基本的一个概念,时间复杂度. 简单来说,就是一个算法,后者一个方法或者函数,执行时需要多长时间....CPU执行每条语句的真正时间忽略为1, 所用时间就是T(n)=1 + N + N = 2 * N + 1 根据时间复杂度的基本规则:去掉常数,保留最高阶最后结果为T(N)=O(2 * N +...1) = O(N) 也因为上述规则,时间复杂度,也称为渐进的时间复杂度....2个列子的区别在于他执行时会跳过很多数,执行的次数比O(N)少很多,也意味着,这个方法的时间复杂度要优于O(N)的....,显然执行次数,T(0)=T(1)=1,同时 T(n)=T(n - 1)+T(n - 2)+1,最后通过归纳证明,时间复杂度可以简化为O(2^N) 下面是常用的时间复杂度表达式和术语, 阶对应术语

4050 0

函数的递归

1.递归思想: 把一个复杂的问题拆分成一个一个小的问题，直到小的问题不能再被拆分。递是传递的意思，归是回归的意思，下文举例说明。 1条件：（1）递归存在条件，当不满足这个条件时就停止递归。...的阶乘就是n*(n-1)*(n-2)*........*1，这是一道数学问题，要把他转化为编程逻辑，一般先想到的是循环，从1一开始一直乘到n结束，使用递归也同样简单，如图利用这种方法完成递归，首先创建一个子函数...} 要想完成1234的分离，首先把4分离出来，其次在分离3，一直分离到1，传递参数进入子函数，1234>9,在进入123,，123也大于9，进入12，还是大于9，在进入1,1递归结束，首先完成1的打印...利用图来解释更为直观一些，函数递归一直执行到限制条件为止，正如开头所说，执行到1为止，依次回归，打印各位数字最后完成程序 #include void Print(long n) {...，却能执行复杂的计算，一定程度上为程序员节省了时间，但是递归有时也有缺点，计算过程复杂导致计算慢，更多的需要程序员去探索

571 0

算法的时间复杂度

算法的效率：是指算法执行的时间，算法执行时间需要通过算法编制的程序在计算机上运行时所消耗的时间来衡量。一个算法的优劣可以用空间复杂度和时间复杂度来衡量。时间复杂度：评估执行程序所需的时间。...算法设计时，时间复杂要比空间复杂度更容易复杂，所以本博文也在标题指明讨论的是时间复杂度。一般情况下，没有特殊说明，复杂度就是指时间复杂度。...（上面提到了）一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称为f(n)...是T(n)的同数量级函数。...T(n) = O(f(n))称函数T(n)以f(n)为界或称T(n)受限于f(n)。如果一个问题的规模是n，解决一问题的某一算法所需要的时间为T(n)。

1.2K2 0

时间复杂度

算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法复杂度分为时间复杂度和空间复杂度。...其作用: 时间复杂度是指执行算法所需要的计算工作量；空间复杂度是指执行这个算法所需要的内存空间。常数时间的操作：一个操作如果和数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。...时间复杂度为一个算法流程中，常数操作数量的指标。常用O（读作big O）来表示。...4....+3+2+1)次,每次操作是一个常数时间操作记为O(1)(读作bigO(1)) 所以整个时间化简复杂度应该是(N^2 /2+N+1)*O(1),也就是(aN^2+bN+1)*O(1) image.png...这次算法时间复杂度应去掉低阶项bN+1和N的系数A f(N)=N^2, O(f(n))=O(N^2) 评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是常数项时间

4103 0

时间复杂度

我们现在已经有执行函数了T(n)，我们得到算法的时间复杂度啦？...1、们知道常数项对函数的增长速度影响并不大，所以当 T(n) = c，c 为一个常数的时候，我们说这个算法的时间复杂度为 O(1)；如果 T(n) 不等于一个常数项时，直接将常数项省略。...比如第一个 Hello, World 的例子中 T(n) = 2，所以我们说那个函数(算法)的时间复杂度为 O(1)。 T(n) = n + 29，此时时间复杂度为 O(n)。...比如 T(n) = n^3 + n^2 + 29，此时时间复杂度为 O(n^3)。 3、因为函数的阶数对函数的增长速度的影响是最显著的，所以我们忽略与最高阶相乘的常数。...综合起来：如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时忽略最高项的系数后得到函数 f(n)，此时算法的时间复杂度就是 O(f(n))。为了方便描述，下文称此为大O推导法。

4832 1

时间复杂度

在了解时间复杂度之前，先了解一下原操作和时间频度 ---- 一.原操作原操作是指固有的数据类型的操作，可以理解为基本运算，下面的代码块中 3,6,7,9 都是原操作例1 1. void foo (int...二.时间频度 T(n) 时间频度是该算法所有原操作的执行次数,它是问题规模n的函数，用T(n)表示.下面采用简化方法去分析，即只考虑算法内最深层循环内的原操作例2 void foo (int n) {...printf("%d",i+j); //即深层原操作次数为n^2+10n } } } 即 T(n) = n^2+10n 三.时间复杂度...O(n) 时间复杂度是用时间频度的最大数量级表示： O(n) = ( T(n)的数量级 ) 例2中，T(n) = n^2+10n，其最大数量级为 n^2 (即忽略其常数和低级次幂) 最后 O(n) =...n^2 四.时间复杂度对照表 O(1) < O(log2 N) < O(n) < O(nlog2 N) < O(n^2） < O(n^3) < O(2^n) < O(n!)

3902 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭