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