為什麼這篇遞迴時間複雜度鄉民發文收入到精華區：因為在遞迴時間複雜度這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者arrenwu (不是綿芽的錯)看板Math標題Re: [其他] 離散：遞迴以及時間複雜度時間F...
遞迴時間複雜度 在 混著 MIXFIT Online Magazine Instagram 的精選貼文
2021-03-08 10:47:08
- 《MIXFIT 本週新曲推薦》 🤙推薦一：蛋堡 SoftLipa -〈音菩薩〉 雖然〈音菩薩〉早就已經收錄在了蛋堡的《家常音樂》專輯中，不過正式 MV 則是在不久前才釋出。本次的 MV 可謂相當有趣，畫面就猶如一個充滿未來感的 3D 菩薩世界，觀眾可於手機或平板上用手指滑動螢幕，達到 360...
※ 引述《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)?
: 我問這個，主要是有點迷惑，是不是解遞迴後，
: 時間複雜度，有可能降低？還是時間複雜度一定維持不變？
1. 這個函數 g(k) 的時間複雜度是 O(logk)
定義 f(k) = k/2 ,if k is even
floor(k/2)+1 ,if k is odd
Claim: f(f(k)) < k/2 for k >= 4
Proof of Claim: 把 k 分成四種類別 4m, 4m+1, 4m+2, 4m+3 討論即可
有那個claim有啥用呢？ 那claim所表達的意涵是，
你計算 g(k) 一路抖抖抖抖抖到 g(1) 的次數，不會超過 2*ceiling(logk) 次
所以是 O(logk)
當然你想直接用 Master's Theorem 也行
2. 不知道 嘻嘻
3. 是可能降低的
因為你想得到的一般函數，時間複雜度比較高的 a^n (n是正整數) 也就 O(logn)
如果能寫成其他函數就可能更低
不過我是覺得 logk 其實也已經滿低了
--
角卷綿芽首次個人Live： Watame Night Fever!! in Zepp Tokyo
https://pbs.twimg.com/media/E9PIgJ7VkAUExEa.jpg
官網購票連結：https://watame1stlive.hololive.tv/tickets/
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.45.135.233 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1630047777.A.1F7.html
推 pmove : 我贊同您的答案。另外就是我之前寫的paper, 有提到 08/27 16:12
→ pmove : 另一個遞迴，如果直接轉程式，似乎是Big O(log n), 08/27 16:12
→ pmove : 我paper是寫Big O(1), 可是解遞迴的話，似乎就是Big 08/27 16:12
→ pmove : O(1)沒寫錯… 08/27 16:12
妳方便把妳提到的另外一組 遞迴 和 公式解 的情況寫上來嗎？※ 編輯: arrenwu (98.45.135.233 美國), 08/28/2021 02:33:31
推 Vulpix : 我覺得你的O(1)不是時間複雜度。 08/28 03:14
→ Vulpix : 是不是因為 g(1+2^n)=-2+2^n 然後 g(k)≦k-3 才說 08/28 03:18
→ Vulpix : g~O(1) 的？ 08/28 03:18
推 pmove : 著作，不想曝光 XD 08/28 06:48
→ pmove : Sorry, 著作是typo, 應該是拙作 08/28 06:50