[理工] [ALGO] recursion tree

看板Grad-ProbAsk作者 (拜占庭)時間14年前 (2011/07/16 18:33), 編輯推噓2(2推 0噓 4→)
留言6則, 4人參與, 最新討論串1/1
請問recursion tree所得到的解 可以直接當作是一個遞迴式子的解嗎? recursion tree原先只是拿來猜可能的解而已 通常是需要再使用substitution method 但是書上幾乎都是分析完recursion tree後就沒使用substitution method了 不知道考試時這樣子會不會算沒有證明完整？ 謝謝回答! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.254.135.168
推
07/17 01:51, , 1F
你計算夠嚴謹的話，也算是完整的證明
07/17 01:51, 1F
→
07/17 13:47, , 2F
題外話 ,代換法+展開 會不會比較嚴謹?
07/17 13:47, 2F
→
07/17 21:23, , 3F
看改考卷的教授的感覺囉~
07/17 21:23, 3F
推
07/17 22:48, , 4F
一個遞回式子的"解"還是用離散的方法吧
07/17 22:48, 4F
→
07/17 22:48, , 5F
recursion tree只能求tight bound
07/17 22:48, 5F
→
07/18 09:31, , 6F
阿抱歉，打錯了，不是解 是時間複雜度
07/18 09:31, 6F
‣ 更多 Byzantin 的文章
文章代碼(AID): #1E8MaB-p (Grad-ProbAsk)