※ 引述《pmove (不怕死，才算真正的活著)》之銘言：
: 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(1)?
: 2. 請問上面這個g(k)是不是有辦法解遞迴成一個式子？
: 3. 如果有辦法解遞迴成式子，那時間複雜度是不是Big O(1)?
: 我問這個，主要是有點迷惑，是不是解遞迴後，
: 時間複雜度，有可能降低？還是時間複雜度一定維持不變？
你要注意你的遞迴是在描述什麼東西
如果這遞迴是直接描述你想要計算的值的話, 當然求出通式出來就是 O(1)
但如果你這遞迴是在描述一個遞迴演算法的操作次數的話
你解出來的只是原演算法的時間複雜度, 對原演算法的加速沒有幫助
你應該是把這兩個概念給混在一起了才會迷惑說到底解遞迴能不能加速
因為兩者都是遞迴, 但描述的東西不一樣
舉個例子:
H(n) = 2 * H(n/2) + n, H(1) = 0
如果你只是想算 H(n) 的值多少那你可以解得 H(n) = n*log2(n)
那代隨便一個 n 值去算函數值當然是 O(1)
但如果 H(n) 是在描述合併排序演算法的操作數目的話
解出來的 H(n) 式子對合併排序演算法加速是沒有用的
因為這就代表合併排序演算法的時間複雜度就是 O(n*log(n))
--
◢ ˊ_▂▃▄▂_ˋ. ◣ ▅▅ ▅▅ ι●╮ █▄▄▄▄▄
▍./◤_▂▃▄▂_◥ \'▊ ＨＡＲＵＨＩ █████ ＜■┘ ▄▄▄▄▄▄▄
▎⊿ ◤◤◥█◥◥█Δ ＩＳＭ By-gamejye ￠|\ ▌▌▌▌▌▄▌▌
▏ζ(▏●‵◥′●▊)Ψ ▏ █ ⊿Δ ▄▄▄ ▄▄▄▄
█/|▊ 〃 、 〃▋ |\ ▎ ハルヒ主義 █▄▄▄█▄▄
◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.0.237 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1630075491.A.3F7.html
※ 編輯: LPH66 (180.177.0.237 臺灣), 08/27/2021 22:45:19
推
08/28 08:40,
4年前
, 1F
08/28 08:40, 1F
討論串 (同標題文章)