每次递归内部计算时间是常数,故O(n)。
用递归方法计算阶乘,函数表达式为f(n)=1 若n=0 f(n)=n*f(n-1),若n>0,如果n=0,就调用1次阶乘函数,如果n=1,就调用2次阶乘函数,如果n=2,就调用3次阶乘函数,如果n=3,就调用4次阶乘函数。
扩展资料:
注意事项:
利用递归树方法求算法复杂度,其实是提供了一个好的猜测,简单而直观。在递归树中每一个结点表示一个单一问题的代价,子问题对应某次递归函数调用,将树中每层中的代价求和,得到每层代价,然后将所有层的代价求和,得到所有层次的递归调用总代价。
递归树最适合用来生成好的猜测,然后可用代入法来验证猜测是否正确。当使用递归树来生成好的猜测时,常常要忍受一点儿不精确,因为关注的是如何寻找解的一个上界。
参考资料来源:百度百科-递归算法
参考资料来源:百度百科-阶乘
参考资料来源:百度百科-时间复杂度