作者pmove (不怕死，才算真正的活著)
看板Math
標題[其他] 離散：遞迴以及時間複雜度
時間Fri Aug 27 09:32:33 2021
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)?
我問這個，主要是有點迷惑，是不是解遞迴後，
時間複雜度，有可能降低？還是時間複雜度一定維持不變？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.171.78.126 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1630027955.A.51E.html
1F：推 sunev : 轉二進位？ 08/27 11:36
2F：→ kilva : 複雜度要看解式子的程式碼，而不是看程式碼本身 08/27 12:04
3F：→ kilva : 打錯~~不是看式子本身 08/27 12:05
4F：→ pmove : g(k)是paper上看到的一個遞迴函式，具體是拿來做啥 08/27 12:07
5F：→ pmove : ？並不重要，不過應該不是2進位。這邊只是借過來問 08/27 12:07
6F：→ pmove : 時間複雜度？還有解遞迴？最後問：解遞迴後，時間複 08/27 12:07
7F：→ pmove : 雜度是多少？ 08/27 12:07
8F：→ pmove : 回2樓，程式碼就是遞迴直接轉程式碼，判斷是否偶數 08/27 12:39
9F：→ pmove : ？C程式碼： if (k % 2 == 0) { … } 其餘程式碼， 08/27 12:39
10F：→ pmove : 同理類推 08/27 12:39