作者LPH66 ( )
看板Math
标题Re: [其他] 离散：递回以及时间复杂度
时间Fri Aug 27 22:44:49 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)?
: 我问这个，主要是有点迷惑，是不是解递回後，
: 时间复杂度，有可能降低？还是时间复杂度一定维持不变？
你要注意你的递回是在描述什麽东西
如果这递回是直接描述你想要计算的值的话, 当然求出通式出来就是 O(1)
但如果你这递回是在描述一个递回演算法的操作次数的话
你解出来的只是原演算法的时间复杂度, 对原演算法的加速没有帮助
你应该是把这两个概念给混在一起了才会迷惑说到底解递回能不能加速
因为两者都是递回, 但描述的东西不一样
举个例子:
H(n) = 2 * H(n/2) + n, H(1) = 0
如果你只是想算 H(n) 的值多少那你可以解得 H(n) = n*log2(n)
那代随便一个 n 值去算函数值当然是 O(1)
但如果 H(n) 是在描述合并排序演算法的操作数目的话
解出来的 H(n) 式子对合并排序演算法加速是没有用的
因为这就代表合并排序演算法的时间复杂度就是 O(n*log(n))
--
◢ ˊ_▂▃▄▂_ˋ. ◣ ▅▅ ▅▅ ι●╮ █
▄▄▄▄▄
▍
./◤_▂▃▄▂_◥ \'▊ ＨＡＲＵＨＩ █████ ＜■┘ ▄▄▄▄▄▄▄
▎
⊿ ◤◤◥█◥◥█Δ ＩＳＭ By-gamejye ￠|\ ▌▌▌▌▌▄▌▌
▏
ζ(▏●‵◥′●▊)Ψ ▏ █
⊿Δ ▄▄▄ ▄▄▄▄
█/|▊ 〃 、 〃▋ |\ ▎ ハルヒ主义 █
▄▄▄█▄▄
◥◥|◣ ‵′ ◢/'◢◢
S.O.S 世界を大いに盛り上げるための凉宫ハルヒの団
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 180.177.0.237 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1630075491.A.3F7.html
※ 编辑: LPH66 (180.177.0.237 台湾), 08/27/2021 22:45:19
1F：推 pmove : 递回是直接描述所要计算的值 08/28 08:40
2F：→ mantour : 求出通式不代表值会自己变出来, 是否还要考虑用什 08/31 23:38
3F：→ mantour : 麽演算法去求通式的值 08/31 23:38
4F：→ mantour : 比如求费式数列第n项, 单纯递回是 O(n^2) 08/31 23:44
5F：→ mantour : 解出通式变成 c(a^n - b^n) 08/31 23:45
6F：→ mantour : 而求a^n如果用最笨的演算法是 O(n) , 如果聪明一点 08/31 23:46
7F：→ mantour : 则是 O(log n) 08/31 23:48
8F：→ mantour : 更正 单纯递回是 O(2^n) 08/31 23:49
9F：→ mantour : 即使不解出通式, 本来的递回式如果改用动态规划建表 08/31 23:53
10F：→ mantour : 也可以变成O(n), 其实解出通式也是演算法的一种 08/31 23:54
11F：→ mantour : 用不同演算法去算递回的值, 复杂度可以不同应该很 08/31 23:54
12F：→ mantour : 合理吧 08/31 23:54
13F：推 Vulpix : 费氏数列用定义递回是O(n)吧，每多算一项也只要一次 09/01 01:27
14F：→ Vulpix : 加法。就算连call前两项都要算进去，也还是O(n)。 09/01 01:28
15F：推 arrenwu : 费氏数列用单纯递回 f(n) = f(n-1)+f(n-2)是O(2^n) 09/01 04:33
16F：→ arrenwu : O(n) 是用for-loop(迭代)或者加入memoization 09/01 04:34
17F：→ LPH66 : 直接写不管重覆的应该是 O(φ^n) = O(f(n)) 09/01 08:22
18F：→ LPH66 : (因为唯一的终止条件是 f(1)=f(2)=1) 09/01 08:23
19F：→ LPH66 : 用 memoization 或 DP 式才是 O(n) 没错 09/01 08:23
20F：→ LPH66 : 然後计算通式的话指数可以用对数做, 这就成了 O(1) 09/01 08:24
21F：→ LPH66 : 啊, 我是在说任意底指数要乘一个对数值... 09/01 08:25
22F：→ LPH66 : 自然指数和自然对数即使用级数, 算到固定精度的时间 09/01 08:27
23F：→ LPH66 : 可以当做 O(1), 所以算通式在这意义下是 O(1) 09/01 08:28
24F：推 Vulpix : memorization是指这种吗？f(n)=f(n-1)+g(n-1)然後配 09/01 18:26
25F：→ Vulpix : 上g(n)=f(n-1)←这个？ 09/01 18:26
26F：→ Vulpix : 还真的没有r，好不直觉…… 09/01 18:28
27F：→ LPH66 : memoization 是算过的值写下来, 之後要就直接拿 09/01 21:48
28F：推 Vulpix : 所以如果之後要多次读取的话会很方便，但要付出记忆 09/01 22:14
29F：→ Vulpix : 体空间给他的概念吧。那跟上面那个是还有点不一样， 09/01 22:16
30F：→ Vulpix : 那个写法是过气的f,g可以扔掉。 09/01 22:17