作者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/cn.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