作者AAQ8 ()
看板Grad-ProbAsk
标题[理工] 两题资结
时间Wed Nov 21 20:54:41 2018
https://i.imgur.com/wGylg0Y.jpg
https://i.imgur.com/PS0ZeWZ.jpg
第一张的算式看得懂
不过不知道为什麽是那样子算
第二张的b选项不知道错在哪里
麻烦各位
感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 110.28.34.21
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1542804884.A.9C5.html
1F：推 skyHuan: 你没拍到上一题XD 11/21 21:05
2F：→ skyHuan: 我记得这题好像跑了三个递回，资料量都是原本的2/3，空 11/21 21:05
3F：→ skyHuan: 间复杂度主要算的就是变动空间，这题就是跑递回的时候的s 11/21 21:05
4F：→ skyHuan: tack，他三次是分开跑的，每次需要的空间就是原本的2/3， 11/21 21:05
5F：→ skyHuan: 所以s(n)=s(2n/3)+O(1) 11/21 21:05
6F：→ skyHuan: (B) 的话不一定，事实上把空间变成2^n很可能光access这 11/21 21:06
7F：→ skyHuan: 些空间，时间复杂度就2^n了 11/21 21:06
8F：→ AAQ8: 想请问一下，时间复杂度是执行次数的成长速度，空间复杂度是 11/22 14:11
9F：→ AAQ8: 指记忆体需求的成长速度，这样子说正确吗 11/22 14:11
10F：推 skyHuan: 是的~ 就是当资料量是n的时候这个演算法需要多少时间/空 11/23 00:01
11F：→ skyHuan: 间随n改变的程度 11/23 00:01