递归算法代码中如何计算算法复杂度计算（递归的空间复杂度）

本文目录

• 递归的空间复杂度
• 数据结构与算法Day20----递归算法时间复杂度的求解方法
• 递归算法时间复杂度题目求解答.
• 递归函数的时间复杂度应该怎么算
• 如何用递归树求快速排序时间复杂度
• 如何计算算法复杂度
• 算法导论 4-3 递归式 T(n)=2T(n/2)+n/lgn的复杂度求解
• 递归方程求时间复杂度
• 算法空间复杂度具体怎么算

递归的空间复杂度

递归折半查找的时间复杂度是O(log2n)，空间复杂度是O(log2n)，也是递归的最大深度非递归的时间复杂度是O(log2n)，空间复杂度是O(1)，仅仅用几个单变量就够。空间复杂度:是程序运行所以需要的额外消耗存储空间,一般的递归算法就要有o(n)的空间复杂度了,简单说就是递归集算时通常是反复调用同一个方法，递归n次，就需要n个空间。时间复杂度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f (n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(nk次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

数据结构与算法Day20----递归算法时间复杂度的求解方法

  递归的思想就是，将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。 如果把这个一层一层的分解过程画成图，它其实就是一棵树。给这棵树起一个名字，叫作递归树。节点里的数字表示数据的规模，一个节点的求解可以分解为左右子节点两个问题的求解。

  假设平均情况下，每次分区之后，两个分区的大小比例为 。当 时，如果用递推公式的方法来求解时间复杂度的话，递推公式就写成 。这个公式可以推导出时间复杂度，但是推导过程非常复杂。   如果采取递归树的方法，还是取 等于 ，也就是说，每次分区都很不平均，一个分区是另一个分区的 倍。快速排序的过程中，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所遍历的数据的个数之和就是 。   现在只要求出递归树的高度 ，这个快排过程遍历的数据个数就是 ，就是说，时间复杂度就是 。因为每次分区并不是均匀地一分为二，所以递归树并不是满二叉树。这样一个递归树的高度是多少呢？因为快速排序结束的条件就是待排序的小区间，大小为 ，也就是说叶子节点里的数据规模是 ，从根节点 到叶子节点 ，递归树中最短的一个路径每次都乘以 ，最长的一个路径每次都乘以 。通过计算可以得到，从根节点到叶子节点的最短路径是 ，最长的路径是 。   所以，遍历数据的个数总和就介于 和 之间。根据复杂度的大O表示法，对数复杂度的底数不管是多少，统一写成 ，所以，当分区大小比例是 时，快速排序的时间复杂度仍然是 。   刚刚假设 ，那如果 ，也就是说，每次分区极其不平均，两个区间大小是 ，这个时候的时间复杂度是多少呢？可以类比上面 的分析。当 的时候，树的最短路径就是 ，最长路径是 ，所以总遍历数据个数介于 和 之间。尽管底数变了，但是时间复杂度也仍然是 。也就是说，对于 等于 ， ，甚至是 ， ……，只要 的值不随 变化，是一个事先确定的常量，那快排的时间复杂度就是 。所以，从概率论的角度来说，快排的平均时间复杂度就是 。

   分解为 和 ，每次数据规模都是 或者 ，叶子节点的数据规模是 或者 。所以，从根节点走到叶子节点，每条路径是长短不一的。如果每次都是 ，那最长路径大约就是 ；如果每次都是 ，那最短路径大约就是 。   每次分解之后的合并操作只需要一次加法运算，把这次加法运算的时间消耗记作 。所以，从上往下，第一层的总时间消耗是 ，第二层的总时间消耗是 ，第三层的总时间消耗就是 。依次类推，第 层的时间消耗就是 ，那整个算法的总的时间消耗就是每一层时间消耗之和。   如果路径长度都为 ，那这个总和就是 。   如果路径长度都是 ，那整个算法的总的时间消耗就是 。   所以，这个算法的时间复杂度就介于 和 之间。虽然这样得到的结果还不够精确，只是一个范围，但是基本上知道了上面算法的时间复杂度是指数级的。

  第一层分解有 次交换操作，第二层有 个节点，每个节点分解需要 次交换，所以第二层总的交换次数是 。第三层有 个节点，每个节点分解需要 次交换，所以第三层总的交换次数是 。   以此类推，第 层总的交换次数就是 。最后一层的交换次数就是 。每一层的交换次数之和就是总的交换次数。   这个公式的求和比较复杂，看最后一个数， 等于 ，而前面的 个数都小于最后一个数，所以，总和肯定小于 ，也就是说，全排列的递归算法的时间复杂度大于 ，小于 ，虽然不是非常精确的时间复杂度，但是这样一个范围已经说明全排列的时间复杂度是非常高的。

递归算法时间复杂度题目求解答.

如果就按这个递归式子算,计算第n项需要的计算量An = ΣAi {i,0 -》 n-1}因此An = S(n-1) =》 An = 2*A(n-1)又因为0,1两项可以直接算得. 故 A0 = 1, A1 = 1所以第n项的计算量为{n=0 : 1, n》0 : 2^(n-1)}总的来说是O(2^n)级别 当然真正实现这个算法的时候不会这么采用暴力的计算.如果加入记忆化,把每个Ti的值先记下,则时间复杂度可以降到O(n^2)级别 进一步优化,可以尝试计算这个递归数列的通项.不过我简单试了下发现最后要计算1/n的和,这个据我所知只能直接计算.这样整个算法的复杂度可以降到O(n). 至于楼下说的O(1)的常数做法,我个人没有想到,也许在数据规模小的情况下可以使用查表法做到.

递归函数的时间复杂度应该怎么算

求解算法的时间复杂度的具体步骤是：　　⑴ 找出算法中的基本语句；　　算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。　　⑵ 计算基本语句的执行次数的数量级；　　只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。　　⑶ 用大Ο记号表示算法的时间性能。　　将基本语句执行次数的数量级放入大Ο记号中。　　如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：　　for (i=1; i《=n; i++)　　x++;　　for (i=1; i《=n; i++)　　for (j=1; j《=n; j++)　　x++;　　第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。　　常见的算法时间复杂度由小到大依次为：　　Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法，把这类问题称为P类问题，而把后者称为NP问题。这只能基本的计算时间复杂度，具体的运行还会与硬件有关。参考博客地址：

如何用递归树求快速排序时间复杂度

快速排序法的时间复杂度是nlogn（n×log以2为底n的对数）拓展：快速排序（Quicksort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

如何计算算法复杂度

问题一：程序中的时间复杂度是怎么计算的？ 算法复杂度的介绍，见百科： baike.baidu/view/7527 时间复杂度 时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 计算方法 1. 一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n）） 分析：随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以f（n）越小，算法的时间复杂度越低，算法的效率越高。 2. 在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n）） 例：算法： for（i=1;i》 问题二：如何计算算法的时间复杂度 求解算法的时间复杂度的具体步骤是：　　⑴找出算法中的基本语句；　　算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。　　⑵计算基本语句的执行次数的数量级；　　只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。　　⑶用大Ο记号表示算法的时间性能。　　将基本语句执行次数的数量级放入大Ο记号中。　　如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：　　for(i=1;i 问题三：C语言算法的时间复杂度如何计算啊？ 看看这个 每个循环都和上一层循环的参数有关。 所以要用地推公式： 设i(n)表示第一层循环的i为n时的循环次数，注意到他的下一层循环次数刚好就是n，分别是0,1,2...n-1 所以，把每一层循环设一个函数分别为：j(n),k(n),t(n) 则有 i(n)=j(0)+...+j(n-1) j(n)=k(0)+...+k(n-1) k(n)=t(0)+...+t(n-1) i(0)=j(0)=k(0)=0 t(n)=1 而总循环数是i(0)+i(1)...+i(n-1) 可以根据递推条件得出准确值 所以算法复杂度是O(i(0)+i(1)...+i(n-1)) 记得采纳啊 问题四：如何计算算法的时间复杂度和空间复杂度 是说明一个程序根据其数据n的规模大小 所使用的大致时间和空间 说白了 就是表示 如果随着n的增长 时间或空间会以什么样的方式进行增长 例 for(int i = 0; i 问题五：一个算法的时间复杂度是什么函数？ 关于n的函数，n是问题的规模 问题六：请问递归算法的时间复杂度如何计算呢? 递归算法的时间复杂度分析 收藏 在算法分析中，当一个算法中包含递归调用时，其时间复杂度的分析会转化为一个递归方程求解。实际上，这个问题是数学上求解渐近阶的问题，而递归方程的形式多种多样，其求解方法也是不一而足，比较常用的有以下四种方法： (1)代入法(Substitution Method) 代入法的基本步骤是先推测递归方程的显式解，然后用数学归纳法来验证该解是否合理。 (2)迭代法(Iteration Method) 迭代法的基本步骤是迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计。 (3)套用公式法(Master Method) 这个方法针对形如“T(n) = aT(n/b) + f(n)”的递归方程。这种递归方程是分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子问题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。 (4)差分方程法(Difference Formula Method) 可以将某些递归方程看成差分方程，通过解差分方程的方法来解递归方程，然后对解作出渐近阶估计。 下面就以上方法给出一些例子说明。 一、代入法 大整数乘法计算时间的递归方程为：T(n) = 4T(n/2) + O(n)，其中T(1) = O(1)，我们猜测一个解T(n) = O(n2 )，根据符号O的定义，对n》n0，有T(n) 》 问题七：如何计算时间复杂度 如何计算时间复杂度 定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数 T(n)称为这一算法的“时间复杂性”。 当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。 我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。 此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。 “大 O记法”：在这种描述中使用的基本参数是 n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。 这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。 O(1) Temp=i;i=j;j=temp; 以 上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时 间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。 O(n^2) 2.1. 交换i和j的内容 sum=0； （一次） for(i=1;i》 问题八：算法的时间复杂度 以下是考研时常用的计算方法，实际上最简单的方法采用多项式最大阶的方法，如： f(n)=a1*n^m+a2*n^(m-1)+.......an-1*n+an 的时间复杂度为:T(f(n))=O(n^m) 采用时间步法，找一个函数g(n),找一个自然数n0,使f(n)T(n)=O(n) (2)6n^2-12n+1=12)=7n^2=7*g(n)==》T(n)=O(n^2) (3)n(n+1)(n+2)/6=n0=2时)=n0=4)=2*g(n)===》T(n)=O(n^3) (4)2^(n+1)+100nT(n)=O(2^n)

算法导论 4-3 递归式 T(n)=2T(n/2)+n/lgn的复杂度求解

     在阅读算法导论第四章的时候，求解一些递归式的复杂度时，遇到了一些问题，因此将思路分享一下。      首先对于可以用主方法求解的形式，这里不再说明，符合主方法的三种情况只要套用公式即可得到正确答案。关于主方法使用递归树法进行证明，算法导论上已经解释的很详细，感兴趣可以参考一下。     在练习题 4.6-2 中提到了    ， 其中   ，要求证明主递归式的的解为       以   为例，很明显不符合主方法的条件，因为第三章讲到过  ，那么可以考虑使用递归树法，进行求解，然后再使用代入法进行数学归纳法的证明。     首先递归树高度为  （书中  以2为底，而不是10），叶节点数量为  ，即数量为n，每个叶节点复杂度为  ，因此叶节点总的复杂度为      然后计算中间节点包括根节点的复杂度，每一层有   个子节点          接下来计算等差数列之和即可                         即    总的复杂度       因此可以很清楚的看到，由于递归树的每层代价类似，最后结果多出来的   可以认为树的总层数进行累加的结果。     下面使用代入法验证该结论，由于证明渐近上界与证明渐近下界的过程类似，因此只证明上界。     设      则， 得证，其中      在思考题 4-3中 有类似   形式的递归式存在，其解为  ，有些解答认为是   实际上并不准确。     同样这种形式也不符合主方法的条件，同样使用递归树法进行近似的求解，然后再使用代入法证明答案的正确性。     在计算这个递归式需要使用一些调和级数的知识，在算法导论的附录A中有公式 A.7，调和级数求和的证明需要使用到积分的定理，这里就不赘述了。    同样，首先计算叶节点的复杂度，同上 叶节点数量为  ，即每个叶节点复杂度为  ，总的复杂度为      接下来计算中间节点包括根节点的复杂度，同上，一共有  层，各层之和为          这里的累加项不再是一个等比数列，而是一个调和级数，即为所以可以看出进行多出一次对数运算的原因在于分数的累加，因此总的复杂度 同样，下面使用代入法证明结果的正确性，因为证明步骤类似，这里也只证明渐近上界为  , 设 ，所以有下面证明  ，为了证明的简便，我们假设n为2的幂次，即  ，则对于极限  ，那么有于是，得证  

递归方程求时间复杂度

最近菜鸡作者苦于解递归方程求解时间复杂度的一些问题 整理一下思路 递归算法的运行时间常用递归表达式表示。 本文主要讲解如何从递归表达式求解出时间复杂度。 万变不离其宗，总结以下四种形式。

T(n) = T(n-1)+1

解：T(n) = T(n-1)+1 = +1 = T(n-2)+2 = T(n-3)+3 = ... = T(n-n)+n = n

故 O(n) = n

T(n) = T(n-1)+n-1

解：T(n) = T(n-1)+n-1 = T(n-2)+(n-2)+(n-1) = T(n-3)+(n-3)+(n-2)+(n-1) = ...

= T(n-(n-1))+n-(n-1)+...+(n-2)+(n-1) = 0+1+2+3+4+...+(n-1) = n(n-1)/2

故 O(n) = n^2

T(n) = 2T(n-1)+1

解：T(n) = 2T(n-1)+1 = 2( 2T(n-2)+1)+1 = 4T(n-2)+2+1 = ...

= 2 k)-1) = n(logn)+1

故 O(n)= n(logn)

算法空间复杂度具体怎么算

数据结构中算法空间复杂度计算方法：

一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。

若一个算法为递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表示开始进行的一次非递归调用)。

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。