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