• 斐波拉契数列时间复杂度分析
  • 递归版
    • 证明1
    • 证明2

斐波拉契数列时间复杂度分析

递归版

递归版本的时间复杂度分析，真的不知道怎么分析，需要根据f(n) = f(n-1) + f(n-2)推出通解。这显然是个数学问题。
不知道为什么他们会给出这结果，难道不管通项公式的后一项了？

通项公式如下:

证明1

证明2

还是看不太懂，为什么要给加法加个1呢？