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

看板Math作者arrenwu (不是綿芽的錯)時間4年前 (2021/08/27 15:02)推噓3(3推 0噓 6→)

留言9則, 2人參與討論串2/3 (看更多)

※ 引述《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

08/27 16:12, 4年前 , 1^F

08/27 16:12, 1^F

→

pmove

08/27 16:12, 4年前 , 2^F

08/27 16:12, 2^F

→

pmove

08/27 16:12, 4年前 , 3^F

08/27 16:12, 3^F