[理工] [DS]-遞迴

看板Grad-ProbAsk作者 (Terry)時間15年前 (2010/11/05 00:50), 編輯推噓2(2推 0噓 4→)
留言6則, 2人參與, 最新討論串1/1
不好意思，請教一下 如果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
推
11/05 01:03, , 1F
把k帶入 3^loglogn = logn^log3 根據a^logc = c^loga
11/05 01:03, 1F
→
11/05 01:15, , 2F
所以時間複雜度是3^loglogn+((loglogn)logn)
11/05 01:15, 2F
→
11/05 01:15, , 3F
+號後面的log不影響，所以消掉了??剩下3^loglogn??
11/05 01:15, 3F
→
11/05 01:15, , 4F
謝謝幫忙
11/05 01:15, 4F
推
11/06 00:26, , 5F
對
11/06 00:26, 5F
→
11/06 02:42, , 6F
謝謝^^
11/06 02:42, 6F
‣ 更多 bernachom 的文章
文章代碼(AID): #1CqkGvnS (Grad-ProbAsk)