作者qmomo (momo)
看板CSSE
标题[问题] 一个资结和离散的问题
时间Sun Mar 6 22:00:08 2005
这是研究所的一个考古题 但是我一直都找不到证明的方法 请大家来看看
F(N) = F(n-1)/F(n-2) + 1
试问此递回公式的所做的 加法 和 除法 运算次数 的时间复杂度为何？
答案是 两个都是 O(2^N)
F'(N) = F'(N-1) + F'(N-2) + 1 ------ O(2^N)
我看了资结和离散的圣经版 但都没有此类的证明 证明O(2^N)这种的
请那位高手指教一下 或者大家来讨论看看:P
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.184.116.43