[理工] [DS]-遞迴樹

看板Grad-ProbAsk作者 (Terry)時間13年前 (2010/10/24 01:48), 編輯推噓0(0推 0噓 6→)
留言6則, 2人參與, 最新討論串1/1
請教一下 有一題是T(n)=3T(√n)+logn 要計算他的時間複雜度 如果要掛樹的話，應該要怎麼掛呢? 而且，這一題的公比是大於1嗎?? 如果大於1的話，樹會長怎樣呢? 謝謝幫忙 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.224.201.127
→
10/24 17:01, , 1F
是使用代入法嗎??
10/24 17:01, 1F
→
10/25 08:37, , 2F
是用代入的沒錯 把右式的T(根號n)再代掉
10/25 08:37, 2F
→
10/25 08:38, , 3F
然後一路代下去使T()形成常數項加上一堆log的式子 做整理
10/25 08:38, 3F
→
10/25 09:09, , 4F
我有看到課本有一題T(n)=2T(√n)+logn的例子
10/25 09:09, 4F
→
10/25 09:09, , 5F
可是前面沒LOG，後面卻跑出一堆LOG看得不是很懂..
10/25 09:09, 5F
→
10/25 09:10, , 6F
可以請教導一下嗎..謝謝幫忙.
10/25 09:10, 6F
‣ 更多 bernachom 的文章
文章代碼(AID): #1Cmn_rEb (Grad-ProbAsk)