看板
[ Math ]
討論串[其他] 離散：遞迴以及時間複雜度
共 3 篇文章
首頁
上一頁
1
下一頁
尾頁
內容預覽:
你要注意你的遞迴是在描述什麼東西. 如果這遞迴是直接描述你想要計算的值的話, 當然求出通式出來就是 O(1). 但如果你這遞迴是在描述一個遞迴演算法的操作次數的話. 你解出來的只是原演算法的時間複雜度, 對原演算法的加速沒有幫助. 你應該是把這兩個概念給混在一起了才會迷惑說到底解遞迴能不能加速. 因
(還有520個字)
內容預覽:
1. 這個函數 g(k) 的時間複雜度是 O(logk). 定義 f(k) = k/2 ,if k is even. floor(k/2)+1 ,if k is odd. Claim: f(f(k)) < k/2 for k >= 4. Proof of Claim: 把 k 分成四種類別 4m,
(還有492個字)
內容預覽:
g(k) = { g(k/2) if k is even,. g(Floor(k/2)+1) + Floor(k/2) if k is odd,. }. with g(1) = -1. Note: Floor表示向下取整. 1. 請問計算這個遞迴的時間複雜度是Big O(logk)? 還是Big O
(還有81個字)
首頁
上一頁
1
下一頁
尾頁