看板 [ CSSE ]
討論串[問題] 一個資結和離散的問題
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 一個資結和離散的問題
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者qmomo (momo)時間20年前 (2005/03/06 21:51), 編輯資訊
1
0
0
內容預覽:
這是研究所的一個考古題 但是我一直都找不到證明的方法 請大家來看看. F(N) = F(n-1)/F(n-2) + 1. 試問此遞迴公式的所做的 加法 和 除法 運算次數 的時間複雜度為何？. 答案是 兩個都是 O(2^N). F'(N) = F'(N-1) + F'(N-2) + 1 ------
#2
Re: [問題] 一個資結和離散的問題
推噓1(1推 0噓 0→)留言1則，0人參與, 最新作者Eventis (何逸凡)時間20年前 (2005/03/06 23:11), 編輯資訊
0
0
0
內容預覽:
0.0"....... 雖然說我也只會回答這種基本的問題XD. (但是在這個板看到這類問題感覺怪怪的@@). 以#/(n) 表示F(n)所需要的除法次數. 以#+(n) 表示F(n)所需要的加法次數. 總共需要的計算次數是. #/(n) = #/(n-1) + #/(n-2) + 1. ^^^^^^
(還有383個字)
#3
Re: [問題] 一個資結和離散的問題
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者qmomo (momo)時間20年前 (2005/03/08 20:13), 編輯資訊
0
0
0
內容預覽:
hohoho... 這是傳說中的計算機科學.... 喔喔喔 看到這行才發現我一直想錯 弄了兩三天 一直到現在才想通...=,=. 我一直覺得解出來是值的計算 忘記算出來的值 已經不是原命題的數字 而是次數... F(n) = d0 * [(1+根號5)/2]^n + d1 * [(1-根號5)/2]
首頁
上一頁
1
下一頁
尾頁