作者silence0925 (书山压力大)
看板Grad-ProbAsk
标题[理工] 资结题库
时间Tue Nov 20 21:44:44 2018
https://i.imgur.com/kieT9XQ.jpg
如图 答案为什麽不是D 麻烦大大们解惑
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.72.237.25
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1542721487.A.7CB.html
1F：推 nannnnn: 内层回圈大概是2i, 譬如说你带i=4进去，内层会做4+2+1大 11/20 22:45
2F：→ nannnnn: 约为2*4,之後2(1+2+···+n)大概n^2 11/20 22:45
4F：→ skyHuan: 少拍到一行XD 11/20 22:56
6F：→ silence0925: 抱歉s大 我还是不太懂 假如i=4时 goo不是只会跑3次 11/21 17:45
7F：→ silence0925: 吗 因为j=i=4 -> 2 ->1 三次 为什麽你们会把他们加起 11/21 17:45
8F：→ silence0925: 来 那个数字是j等於多少跟次数没关系不是吗 麻烦大大 11/21 17:45
9F：→ silence0925: 解惑 11/21 17:45
11F：推 skyHuan: 因为j的回圈要跑goo() 11/21 18:14
12F：→ skyHuan: 题目说goo(m)复杂度是O(m) 11/21 18:14
13F：→ skyHuan: j你跑的4 -> 2 -> 1要把他都加起来 11/21 18:14
14F：→ skyHuan: 大概就是1+2+2^2+... 共加log i次 11/21 18:14
15F：推 skyHuan: goo()的部分没有每次都跑到n，有至少一半的不到n，每次 11/21 18:17
16F：→ skyHuan: 都用n算是nlogn会太大 11/21 18:17
17F：推 nannnnn: s大 n的次数 因该是取floor是吗，另外我是看成每次j的回 11/21 18:53
18F：→ nannnnn: 圈都会执行i当下丢进来的数值的两倍，所以可以写成summa 11/21 18:53
19F：→ nannnnn: tion i从1到n (2i) 11/21 18:53
20F：推 skyHuan: 实际好像是logi取floor再多一次，但我会直接挑好算的数字 11/21 19:32
21F：→ skyHuan: 算，少1多1好像不会影响复杂度XD 11/21 19:32
22F：→ silence0925: 还是不太懂4 2 1为什麽需要加起来 在I=4时 goo指呼叫 11/21 19:42
23F：→ silence0925: 了3次 而不是4+2+1次啊 11/21 19:42
24F：→ silence0925: 抱歉 比较笨想不太懂 11/21 19:45
26F：→ nannnnn: 因为题目有说goo是O(m)假设i为4的那一轮近来，总共会做g 11/21 19:53
27F：→ nannnnn: oo(4),goo(2),goo(1)每次各花O(1),O(2),O(4)的时间， 11/21 19:53
28F：→ nannnnn: 所以i=4的时候总共花了大概c*7,c为常数，以此类推i=5,6, 11/21 19:53
29F：→ nannnnn: 7......加起来 11/21 19:53
30F：→ silence0925: 原来如此 了解了 谢谢两位大大的解释 11/21 20:00