search

GingerBear / IS-Job-Hunting

分享一些找工作的信息和面试题
31 stars 7 forks source link

关于Fib时间复杂度的证明 #9

Open allen6432 opened 10 years ago

allen6432 commented 10 years ago

2014-01-19 21 50 04 2014-01-19 21 50 11 如果有错，感谢指出^_^

GingerBear commented 10 years ago

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

02d03b8a-817e-11e3-911e-efee1bff16b5 02d19d72-817e-11e3-9345-8545062a9951

dianadujing commented 10 years ago

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

allen6432 commented 10 years ago

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

allen6432 commented 10 years ago

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

dianadujing commented 10 years ago

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

allen6432 commented 10 years ago

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