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

[arrenwu (不是綿芽的錯)]

※ 引述《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://www.ptt.cc/bbs/Math/M.1630047777.A.1F7.html
推 pmove       : 我贊同您的答案。另外就是我之前寫的paper, 有提到
→ pmove       : 另一個遞迴，如果直接轉程式，似乎是Big O(log n),
→ pmove       : 我paper是寫Big O(1), 可是解遞迴的話，似乎就是Big
→ pmove       :  O(1)沒寫錯…
妳方便把妳提到的另外一組 遞迴 和 公式解 的情況寫上來嗎？
※ 編輯: arrenwu (98.45.135.233 美國), 08/28/2021 02:33:31
推 Vulpix      : 我覺得你的O(1)不是時間複雜度。
→ Vulpix      : 是不是因為 g(1+2^n)=-2+2^n 然後 g(k)≦k-3 才說
→ Vulpix      : g~O(1) 的？
推 pmove       : 著作，不想曝光 XD
→ pmove       : Sorry, 著作是typo, 應該是拙作