递归的空间复杂度
递归折半查找的时间复杂度是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(n
k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
由递归方式求的N的阶乘（即N，），时间复杂度是多少
每次递归内部计算时间是常数，故O（n）。
用递归方法计算阶乘，函数表达式为f(n)=1 若n=0 f(n)=n*f(n-1)，若n0，如果n=0，就调用1次阶乘函数，如果n=1，就调用2次阶乘函数，如果n=2，就调用3次阶乘函数，如果n=3，就调用4次阶乘函数。
扩展资料：
注意事项：
利用递归树方法求算法复杂度，其实是提供了一个好的猜测，简单而直观。在递归树中每一个结点表示一个单一问题的代价，子问题对应某次递归函数调用，将树中每层中的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层次的递归调用总代价。
递归树最适合用来生成好的猜测，然后可用代入法来验证猜测是否正确。当使用递归树来生成好的猜测时，常常要忍受一点儿不精确，因为关注的是如何寻找解的一个上界。
参考资料来源：百度百科-递归算法
参考资料来源：百度百科-阶乘
参考资料来源：百度百科-时间复杂度
递归时间复杂度 推演计算
递归的时间复杂度计算较为麻烦。以下我们使用归并排序的例子，对递归复杂度进行推演。
假设现在有一个归并排序。他的运行总时间是 T（n） ，
我们通过将其分解成 2 个计算式，即 ： 2 * （T（n/2））+ n ，为什么加 n 呢？因为 n/2 只是递归计算的时间，实际还有合并的时间，在大部分递归中，不但有子任务的时间，还有合并子任务的时间也要计算（在递归计算中，子问题消耗的时间需要统计，合并子问题的结果所消耗的时间也要统计）。
现在，我们的公式是 2 * （T（n/2））+ n ，表达的是一颗高度是 1 的递归树：
如上图，我们需要把这颗递归树的 3 个节点的所有耗时都加上，最终的结果就是 T(N) ;
再看上图，我们递归了 1 层，如果递归 2 层、3层呢？
递归 2 层，表达式变为 4 *（T（n/4）)+ 2n .
递归 3 层，表达式变为 8 * （T（n/8）)+ 3n .
我们总结一下：
递归 2 层： 4（T（n/4）)+ 2n
递归 3 层： 8（T（n/8）)+ 3n
递归 4 层： 16（T（n/16）)+ 4n
······
递归 k 层： 2^k （T（n/2^k））+ kn
假设我们最终递归的结果是 1，那么：
T(n/2^k) = 1
·····反推 2^k = n
····· 那么 k = log2n
k 等于 log2N ，我们带入 k 到上面的公式： 2^k （T（n/2^k））+ kn ；
即 n + log2n * n ；
使用大 O 表达式，去除常数，低阶，系数，递归的时间复杂度为 O(nlogn) ;
关于递归树的推演，推荐观看一个视频，讲的很详细，地址：
算法概述
英国数学家图灵提出的计算模型, 一个两端无限长的由小格子组成的带子，每个格子可以存储一个数，一个可以在带子左右移动的游标或者指针或者不如叫磁头(head), 磁头可读或修改格子里的数。
默认说的是确定性图灵机，和非确定性图灵机功能上等价
著名计算机科学家沃思提出了下面的公式: 程序 = 数据结构 + 算法;
实际上，一个程序应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言来表示。因此，可以用下面的公式表示： 程序 = 算法 + 数据结构 + 程序设计方法 + 语言和环境;
简单点的比如：递归、递推、迭代、穷举、概率算法、随机算法等
复杂些的比如：分治算法、贪心算法、动态规划、回溯法、分支限界等，后面会赘述一些这几种算法的基本思想与常见应用。
算法由三部分影响：
1. 存储结构
2. 算法的空间复杂度
3. 算法的时间复杂度
clock() ：捕捉从程序开始运行到clock()被调用时所耗费的时间。这个 时间单位是clock tick，即“时钟打点”。
常数 CLK_TCK(或CLOCKS_PER_SEC) ：机器时钟每秒所走的时钟打点数。
对于相同输入规模的不同实例，算法的基本运算次数也不一样，可定义两种时间复杂度
最坏情况复杂度 平均复杂度
上界、下界都有无穷个，但是太大的上界、太小的上界对我们分析算法的效率没有帮助，一般我们取最小的上界与***的下界
当我们发现这个算法是 的时候，应该本能的想到有没有可能把它改进为 (尝试分治策略)
递归的时间复杂度一般稍微有点复杂，耐心一步一步分析带入、化简、计算
容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者。像 等，我们把它叫做 多项式级复杂度 ，因为它的规模n出现在底数的位置；
另一种像是 和 等，它是 非多项式级的复杂度 ，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。
对于同一个问题，不同的算法可能会产生不同的复杂度。最典型的例子就是排序，对于n个整数，选择排序和冒泡排序的复杂度为 ，快速排序的复杂度为 ，而使用基数排序的复杂度仅为 。
递归函数的时间复杂度应该怎么算
求解算法的时间复杂度的具体步骤是：
⑴ 找出算法中的基本语句；
算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
⑵ 计算基本语句的执行次数的数量级；
只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的***次幂正确即可，可以忽略所有低次幂和***次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
⑶ 用大Ο记号表示算法的时间性能。
将基本语句执行次数的数量级放入大Ο记号中。
如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：
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问题。
这只能基本的计算时间复杂度，具体的运行还会与硬件有关。
参考博客地址：
关于递归的时间复杂度和递归的时间复杂度是多少的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。