作者sooge (喜欢平井桃)
看板Grad-ProbAsk
标题[理工] 资结 时间复杂度
时间Fri Oct 12 22:39:28 2018
https://i.imgur.com/ZYTZ4ya.jpg
请问这题要如何下手 题目看不太懂....
答案就只给一个O(n^2)而已
拜托了
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 120.105.145.196
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1539355170.A.3BB.html
1F：推 tataTangQQ: 一个loop call funtion，function里也有一个loop10/12 23:38
谢谢你 有看懂了
2F：推 befdawn: 後面还有题目吗？10/12 23:48
後面剩一个右大括号而已
3F：推 skyHuan: compute_value()副程式是O(k)10/13 00:22
4F：→ skyHuan: 主程式回圈i从1开始跑到n10/13 00:23
5F：→ skyHuan: i小於1000的时候是O(1)10/13 00:23
6F：→ skyHuan: i很大的时候(超过1000)就是O(i)10/13 00:23
7F：→ skyHuan: 复杂度=1+1+...+1+1000+1001+1002+...+n=O(n^2)10/13 00:23
可是题目上是写n<1000，不是i<1000
是题目有错吗
※ 编辑: sooge (125.231.41.246), 10/13/2018 02:11:54
8F：推 skyHuan: 喔喔喔我看错题目，那还是一样在n很大的时候回圈O(n)跑n10/13 07:47
9F：→ skyHuan: 次，所以O(n^2)10/13 07:47
10F：推 skyHuan: 复杂度是讨论n很大的时候。还有这题程式s没设初值跑应该10/13 07:49
11F：→ skyHuan: 会出错虽然跟这题无关XD10/13 07:49
另外我想问value=value+(i*k)这个式子
最後答案不是要变成
（0+1+.......k-1)*k=[(k-1)*k/2]*k吗
然後代回n应该是O(n^3)才对
为什麽会是O(n^2)
※ 编辑: sooge (125.231.41.246), 10/13/2018 10:32:59
12F：→ skyHuan: value=value+(i*k)这个式子只要O(1)，回圈跑k次所以compu 10/13 10:47
13F：→ skyHuan: te_value()整个副程式呼叫一次是O(k)，复杂度是看input d10/13 10:47
14F：→ skyHuan: ata大小不是看算出来的值 10/13 10:47
不知道我有没有理解错误 所以value=value+(i*k)可以直接看成value++的意思吗，因为
我们主要是要看它跑了几次回圈不是要看它算出来的值
※ 编辑: sooge (120.105.145.168), 10/13/2018 11:11:57
15F：推 skyHuan: 对啊今天如果有一个程式 10/13 11:25
16F：→ skyHuan: int test(int k){ return k*k; } 10/13 11:25
17F：→ skyHuan: 复杂度也是O(1)不是k^2 他只做了一次乘法 10/13 11:25
懂了 太谢谢你了!! 感谢
※ 编辑: sooge (120.105.145.153), 10/13/2018 11:33:32
18F：推 befdawn: 请问s大(可惜这边不能直接tag哈哈)，复杂度跟 input da 10/13 14:16
19F：→ befdawn: ta 大小有关，是指 input 值大小吗？(这样是算 bits？) 10/13 14:16
20F：→ skyHuan: 我说错了应该要说资料量大小影响到执行"次数"，比如资料 10/13 14:48
21F：→ skyHuan: 量是n，回圈跑到n，资料量就有影响到复杂度，像上面test( 10/13 14:48
22F：→ skyHuan: )函式如果只是算数"值"就不会影响复杂度 10/13 14:48
23F：→ skyHuan: int test(int k){ return k*k; } => O(1) 10/13 14:52
24F：→ skyHuan: int test(int k){ 10/13 14:52
25F：→ skyHuan: for(i=0;i<k;i++) printf("hello!"); } => O(k) 10/13 14:52
26F：推 befdawn: 了解，谢谢s大解说 10/13 15:10