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

看板Math作者 (不怕死，才算真正的活著)時間4年前 (2021/08/27 09:32), 編輯推噓1(1推 0噓 9→)
留言10則, 3人參與, 4年前最新討論串1/3 (看更多)
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
推
08/27 11:36, 4年前 , 1F
轉二進位？
08/27 11:36, 1F
→
08/27 12:04, 4年前 , 2F
複雜度要看解式子的程式碼，而不是看程式碼本身
08/27 12:04, 2F
→
08/27 12:05, 4年前 , 3F
打錯~~不是看式子本身
08/27 12:05, 3F
→
08/27 12:07, 4年前 , 4F
g(k)是paper上看到的一個遞迴函式，具體是拿來做啥
08/27 12:07, 4F
→
08/27 12:07, 4年前 , 5F
？並不重要，不過應該不是2進位。這邊只是借過來問
08/27 12:07, 5F
→
08/27 12:07, 4年前 , 6F
時間複雜度？還有解遞迴？最後問：解遞迴後，時間複
08/27 12:07, 6F
→
08/27 12:07, 4年前 , 7F
雜度是多少？
08/27 12:07, 7F
→
08/27 12:39, 4年前 , 8F
回2樓，程式碼就是遞迴直接轉程式碼，判斷是否偶數
08/27 12:39, 8F
→
08/27 12:39, 4年前 , 9F
？C程式碼： if (k % 2 == 0) { … } 其餘程式碼，
08/27 12:39, 9F
→
08/27 12:39, 4年前 , 10F
同理類推
08/27 12:39, 10F
‣ 更多 pmove 的文章
文章代碼(AID): #1XA42pKU (Math)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 3 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共3篇)
‣ 更多 pmove 的文章
文章代碼(AID): #1XA42pKU (Math)