作者Byzantin (拜占庭)
看板Grad-ProbAsk
標題[理工] [ALGO] recursion tree
時間Sat Jul 16 18:33:45 2011
請問recursion tree所得到的解
可以直接當作是一個遞迴式子的解嗎?
recursion tree原先只是拿來猜可能的解而已
通常是需要再使用substitution method
但是書上幾乎都是分析完recursion tree後就沒使用substitution method了
不知道考試時這樣子會不會算沒有證明完整？
謝謝回答!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.254.135.168
推 kiwidoit:你計算夠嚴謹的話，也算是完整的證明 07/17 01:51
→ metalalive:題外話 ,代換法+展開 會不會比較嚴謹? 07/17 13:47
→ kiwidoit:看改考卷的教授的感覺囉~ 07/17 21:23
推 compulsory:一個遞回式子的"解"還是用離散的方法吧 07/17 22:48
→ compulsory:recursion tree只能求tight bound 07/17 22:48
→ Byzantin:阿抱歉，打錯了，不是解 是時間複雜度 07/18 09:31