关于Fib时间复杂度的证明

[allen6432]

如果有错，感谢指出^_^

[GingerBear]

太给力了， @allen6432 这推导果然高大上，看了几遍有几步还是没明白，那我就不耻下问了。

[dianadujing]

弱弱问一句，x平方=x+1的解不是这个吧？

[allen6432]

@dianadujing 你是对的！！！非常抱歉，那个入的两个值应该是[1+5^(1/2)}/2和[1-5^(1/2)}/2。 后面那个值因为绝对值比第一个小，所以它的幂方除以前面那个正直的幂方会随幂方增大而慢慢趋近于0，所以只用取前面那个正值。 火眼精金！！！给力！！！

[allen6432]

@GingerBear 你的第一个问题我下次图书馆遇见你单独告诉你怎么证明这个特征根的公式；你的第二个问题，我下个issue找一个时间复杂度是幂方的算法来讲讲，会看到我用同样地方法，设出系数a,b，然后求出a,b，然后求出通项。这个方法几乎使用于解决所有复杂度的结果是幂方的题目。 ps: 这个数学解题名词叫做 系数待定法。

[dianadujing]

@allen6432 给neil讲完别忘了把求解过程图片发上来哦~ Many thanks!

[allen6432]

@dianadujing 好的。其实我感觉用特征根的证明只需记住怎么解这类特征根方就行了.证明还是比较数学的。 不过我还是找时间证明下传上来