首页 > 资讯 > 综合 > 正文

递归算法的时间复杂度是什么?递归方程复杂度计算公式推导是什么?

2022-10-28 16:22:09来源:酷狗科技  

递归算法的时间复杂度是:【T(n)=o(f(n))】,它表示随问题规模n的增大,算法的执行时间增长率和f(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)

可以将某些递归方程看成差分方程,通过解差分方程的方法来解递归方程,然后对解作出渐近阶估计。

扩展资料:

1.递归是指对一个问题的求解,可以通过同一问题的更简单的形式的求解来表示,并通过问题的简单形式的解求出复杂形式的解,是解决一类问题的重要方法。

2.递归程序设计是程序设计中常用的一种方法,它可以解决所有有递归属性的问题,并且是行之有效的.

3.但对于递归程序运行的效率比较低,无论是时间还是空间都比非递归程序更费,若在程序中消除递归调用,则其运行时间可大为节省.

关键词: 递归算法时间复杂度怎么求 递归行为时间复杂度估算 所有的递归算法空间复杂度 递归算法的时间复杂度是什么

责任编辑:hnmd003

精彩推送