作者arrenwu (不是綿芽的錯)
看板Math
標題Re: [其他] 離散：遞迴以及時間複雜度
時間Fri Aug 27 15:02:55 2021
※ 引述《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
入場時間：台灣時間 2021/10/12 (星期二) 下午 4:30
官網購票連結：https://watame1stlive.hololive.tv/tickets/
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.45.135.233 (美國)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1630047777.A.1F7.html
1F：推 pmove : 我贊同您的答案。另外就是我之前寫的paper, 有提到 08/27 16:12
2F：→ pmove : 另一個遞迴，如果直接轉程式，似乎是Big O(log n), 08/27 16:12
3F：→ pmove : 我paper是寫Big O(1), 可是解遞迴的話，似乎就是Big 08/27 16:12
4F：→ pmove : O(1)沒寫錯… 08/27 16:12
妳方便把妳提到的另外一組 遞迴 和 公式解 的情況寫上來嗎？
※ 編輯: arrenwu (98.45.135.233 美國), 08/28/2021 02:33:31
5F：推 Vulpix : 我覺得你的O(1)不是時間複雜度。 08/28 03:14
6F：→ Vulpix : 是不是因為 g(1+2^n)=-2+2^n 然後 g(k)≦k-3 才說 08/28 03:18
7F：→ Vulpix : g~O(1) 的？ 08/28 03:18
8F：推 pmove : 著作，不想曝光 XD 08/28 06:48
9F：→ pmove : Sorry, 著作是typo, 應該是拙作 08/28 06:50