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