作者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/cn.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