斐波那契数列——递归法时间复杂度计算

斐波那契数列——递归法时间复杂度计算

斐波那契数列——递归法时间复杂度计算
画图:以F(6)为例:斐波那契数列到第六个数停止
每个节点运行都会开辟空间,使用时间
斐波那契数列——递归法时间复杂度计算
为了方便计算,把第五层的f(2)和f(1)放在第四层最右边,不会影响时间复杂度计算
斐波那契数列——递归法时间复杂度计算

第n层节点个数:2^n 个
前n层节点个数:1+2+4+……+2^n = (2 ^ n) - 1

F(6)有4层,推理:F(n) 有 n-2层
则F(n)一共有节点数 (2 ^ (n-2)) - 1 = ((2 ^n)/4)-1
计算时间复杂度规则:不看常数,不看系数,只看最高次数项
因此:O(F(n)) = O(2 ^n)