[理工] [DS]-遞迴樹

[bernachom (Terry)]

請教一下

有一題是T(n)=3T(√n)+logn

要計算他的時間複雜度

如果要掛樹的話，應該要怎麼掛呢?

而且，這一題的公比是大於1嗎??

如果大於1的話，樹會長怎樣呢?

謝謝幫忙

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.224.201.127
→ bernachom:是使用代入法嗎??
→ hucsnt:是用代入的沒錯 把右式的T(根號n)再代掉
→ hucsnt:然後一路代下去使T()形成常數項加上一堆log的式子 做整理
→ bernachom:我有看到課本有一題T(n)=2T(√n)+logn的例子
→ bernachom:可是前面沒LOG，後面卻跑出一堆LOG看得不是很懂..
→ bernachom:可以請教導一下嗎..謝謝幫忙.