看板 [ Grad-ProbAsk ]
討論串[理工] [演算法] 遞迴式問題
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#3
Re: [理工] [演算法] 遞迴式問題
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者FRAXIS (喔喔)時間15年前 (2010/06/16 21:14), 編輯資訊
0
0
0
內容預覽:
實際上也不是不能求，公比雖然大於一，但是因為樹高是有限的，. 最長就是一直切2/3的那一條路，高度是log_{2/3} n，. 最短的就是一直切1/3的那一條路，高度是log_3 n。. 可以用等比級數的公式去算總和，令r = (1+2^0.5)/3^0.5. 上限就是 n^(0.5) * (r^(
(還有67個字)
#2
Re: [理工] [演算法] 遞迴式問題
推噓5(6推 1噓 11→)留言18則，0人參與, 最新作者FRAXIS (喔喔)時間15年前 (2010/06/15 21:38), 編輯資訊
0
0
0
內容預覽:
感謝這位大大的指教，我研究了一下，每一階成本乘上樹高. 那我想請問一下. T(n) = T(n/2) + T(n/2) + O(1). 會變成多少？ 樹高是O(lg n)應該沒錯吧. 所以答案會是O(lg n)?? 或是答案至少裡面有一個lg n項？. --. ※ 發信站: 批踢踢實業坊(ptt.c
#1
Re: [理工] [演算法] 遞迴式問題
推噓3(3推 0噓 9→)留言12則，0人參與, 最新作者FRAXIS (喔喔)時間15年前 (2010/06/15 12:22), 編輯資訊
0
0
0
內容預覽:
可以用疊代一直展開，到最後會變成. O(n) + n^(1/2) + (n/3)^0.5 + (2n/3)^0.5 + ..... 應該就變成O(n)吧... 令 n = 2^2^k, F(k) = T(2^2^k). F(k) = F(k-1) + 1. 解開F(k) = O(k). 所以T(n)
首頁
上一頁
1
下一頁
尾頁