作者qmomo (momo)
看板CSSE
标题Re: [问题] 一个资结和离散的问题
时间Tue Mar 8 20:28:28 2005
※ 引述《Eventis (何逸凡)》之铭言：
: ※ 引述《qmomo (momo)》之铭言：
: : 这是研究所的一个考古题 但是我一直都找不到证明的方法 请大家来看看
: : F(N) = F(n-1)/F(n-2) + 1
: : 试问此递回公式的所做的 加法 和 除法 运算次数 的时间复杂度为何？
: : 答案是 两个都是 O(2^N)
: 0.0"......
: 虽然说我也只会回答这种基本的问题XD
: (但是在这个板看到这类问题感觉怪怪的@@)
hohoho... 这是传说中的计算机科学...
: 以#/(n) 表示F(n)所需要的除法次数
: 以#+(n) 表示F(n)所需要的加法次数
: 总共需要的计算次数是
: #/(n) = #/(n-1) + #/(n-2) + 1
: ^^^^^^ ****** #
: 算出F(n-1)需要的除法 F(n-2) F(n-1)/F(n-2)
: #+(n) = #+(n-1) + #+(n-2) + 1
: 同上
: 相当於纯粹照定义计算费式数列的complexity,也就是2^n
喔喔喔 看到这行才发现我一直想错 弄了两三天 一直到现在才想通...=,=
我一直觉得解出来是值的计算 忘记算出来的值 已经不是原命题的数字 而是次数..
F(n) = d0 * [(1+根号5)/2]^n + d1 * [(1-根号5)/2]^n
= O([(1+根号5)/2]^n)
= O(2^n)
感谢喔:)....
: 正式的证明还是要解这个recurrence equation.........
: : F'(N) = F'(N-1) + F'(N-2) + 1 ------ O(2^N)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.184.116.43