[理工] [DS]-遞迴

[bernachom (Terry)]

不好意思，請教一下

如果n=2^2^k

T(n)=3T(√n)+logn

經過計算

=> 3^k F(0)+k2^k

那時間複雜度應該會是什麼呢??

我已經知道logn=2^k, loglogn=k

那個3^k應該怎麼表示呢?

謝謝幫忙

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.216.151.223
推 GamesWang:把k帶入 3^loglogn = logn^log3  根據a^logc = c^loga
→ bernachom:所以時間複雜度是3^loglogn+((loglogn)logn)
→ bernachom:+號後面的log不影響，所以消掉了??剩下3^loglogn??
→ bernachom:謝謝幫忙
推 GamesWang:對
→ bernachom:謝謝^^