作者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