作者stator (別急著吃棉花糖)
看板EE_DSnP
標題[問題] 關於時間複雜度的計算
時間Sun Oct 24 09:12:24 2010
老師和其他同學好，因為在算這題的時候遇到了問題
希望可以和你們討論一下。謝謝
1.下列有一函式Fun，其演算法的時間複雜度為何?
Fun(n:integer)
begin
if (n equals 0 or 1)then
fun=1
else fun=fun(n-1)+fun(n-2)
end
(A) O(n log n) (B) O(n^2) (C) O(2^n) (D)O(n!)
上課的時候老師有寫到要算big O 可以先算T(N)的執行次數
但這題遇到問題是
if那行會執行(n+1)還是n次呢?
而fun=1 應是會執行T(1)次
那else那行呢?
(我自己是想n次)
真正的T(n)該如何寫呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.64.170.130
1F：推 ric2k1:這篇文章有好幾個地方寫得不清楚，像是 T(N) 的定義，fun=1 10/24 12:08
2F：→ ric2k1:是甚麼意思，請先確定寫的東西是別人看得懂的再來問比較好 10/24 12:11
3F：→ ric2k1:還有，如果是根本課程無直接相關的問題，請說明一下來處與 10/24 12:12
4F：→ ric2k1:原因。 10/24 12:12
5F：推 Knossos:看一下Master Theorem 你就會寫了 10/24 14:06
6F：→ stator:謝謝樓上二位老師 10/25 13:15
7F：→ Knossos:QQ 你誤會了..我只是個大四生 10/25 18:36
8F：推 Knossos:算了一下 我覺得是O(n^2) 10/25 23:14
9F：→ Knossos:最長路徑n 最短n/2 全部加起來=O(n^2) 10/25 23:15
10F：→ Knossos:QQ 我加錯了 應該是theta(1.618^n)..所以是O(2^n) 10/29 17:37