作者chenbojyh (阿志)
看板Grad-ProbAsk
标题Re: [理工] [资结]-算时间复杂度
时间Thu Sep 17 23:58:37 2009
※ 引述《yesa315 (XD)》之铭言：
: http://ezproxy.lib.ncu.edu.tw:8080/~arhui/cexamn/exam/EC02_93_01.pdf
: 这是93中央资结考题
: 请问第5题怎麽算呢?
: 谢谢
我的想法你参考看看
我也不知道我想的对不对
假设 f(n)的执行次数为ａn
f(n)的执行次数亦等於"f(n-1)的执行次数+f(n-2)的执行次数 +4"
(4次代表执行if + / return 4个动作)
∴ａn = ａ(n-1) + ａ(n-2) + 4
ａ1=ａ2= 2 (if return 2个动作)
剩下就是离散的问题.....
我觉得你应该会(依你在板上的活跃程度猜的)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.227.132.235
※ 编辑: chenbojyh 来自: 61.227.132.235 (09/18 00:00)
1F：推 yesa315:谢谢 因为题库上有这题 但是他只写时间复杂度 实际上应该 09/18 14:27
2F：→ yesa315:不是写时间复杂度 而是把整个递回函式写出来才对吧? 09/18 14:28
3F：→ chenbojyh:题目的一个字 好像指出就是要写出close form 09/18 22:59