作者Eventis (何逸凡)
看板CSSE
标题Re: [问题] 一个资结和离散的问题
时间Sun Mar 6 23:12:02 2005
※ 引述《qmomo (momo)》之铭言：
: 这是研究所的一个考古题 但是我一直都找不到证明的方法 请大家来看看
: F(N) = F(n-1)/F(n-2) + 1
: 试问此递回公式的所做的 加法 和 除法 运算次数 的时间复杂度为何？
: 答案是 两个都是 O(2^N)
0.0"......
虽然说我也只会回答这种基本的问题XD
(但是在这个板看到这类问题感觉怪怪的@@)
以#/(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
正式的证明还是要解这个recurrence equation.........
: F'(N) = F'(N-1) + F'(N-2) + 1 ------ O(2^N)
--
不妨用fibonacci跟complexity当关键字google一下....^^
不过其实基本上那个递回定义一出来就可以直接写O(a^n)的说@@;;;
又因为此数列最小为0(temination condtion)
且除首两项外为严格增.
F(N) = F(N-1) + F(N-2) + 1 < 2F(N-1) for N -> infinite
所以 a = 2为其upper bound,满足big O notation.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.62.49.43
※ 编辑: Eventis 来自: 61.62.49.43 (03/07 07:20)
1F：推 Forcast:对阿总觉得和费氏级数有关 140.121.91.115 04/19