[其他] 離散：遞迴以及時間複雜度

[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)?

我問這個，主要是有點迷惑，是不是解遞迴後，
時間複雜度，有可能降低？還是時間複雜度一定維持不變？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.171.78.126 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1630027955.A.51E.html
推 sunev       : 轉二進位？
→ kilva       : 複雜度要看解式子的程式碼，而不是看程式碼本身
→ kilva       : 打錯~~不是看式子本身
→ pmove       : g(k)是paper上看到的一個遞迴函式，具體是拿來做啥
→ pmove       : ？並不重要，不過應該不是2進位。這邊只是借過來問
→ pmove       : 時間複雜度？還有解遞迴？最後問：解遞迴後，時間複
→ pmove       : 雜度是多少？
→ pmove       : 回2樓，程式碼就是遞迴直接轉程式碼，判斷是否偶數
→ pmove       : ？C程式碼： if (k % 2 == 0) { … } 其餘程式碼，
→ pmove       : 同理類推