作者ENGneweu (威猛先生)
看板Grad-ProbAsk
标题[理工] 演算法 P26 程式时间复杂度
时间Sat Dec 1 22:20:49 2018
我想请问这题b的时间复杂度要怎麽求
我试着写出来 但感觉不对
另外我的a做法是对的吗？
https://i.imgur.com/oKGKXSc.jpg
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.231.144.53
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1543674051.A.B92.html
※ 编辑: ENGneweu (36.231.144.53), 12/01/2018 22:21:46
※ 编辑: ENGneweu (36.231.144.53), 12/01/2018 22:22:38
1F：推 Dora5566: 不对，他问复杂度你就不用理result是什麽了，把它想成O 12/01 22:40
2F：→ Dora5566: （1就好） 12/01 22:40
3F：→ Dora5566: O（1）,另外问一下 if不成立时也算执行一次吗 12/01 22:41
4F：→ Dora5566: 这题是次数是算1/4n^2还是1/2n^2 12/01 22:42
5F：→ ENGneweu: 你说a还是b的想法不对呢？ 12/01 22:49
6F：→ ENGneweu: if不成立的时候要扣掉 因为会多算 12/01 22:49
8F：→ skyHuan: 上面空白的地方是n/2没写到... 12/01 22:59
9F：→ skyHuan: 其实那个if else可以直接当成一个O(1)的指令，因为不管if 12/01 22:59
10F：→ skyHuan: 有没有成立都会做一次运算 12/01 22:59
11F：→ ENGneweu: 感谢sky大解救 想都没想到可以这样想 12/01 23:18
12F：推 jojoboy0115: 我觉得这程式很奇怪...用int 宣告n?这样n=0?还是null 12/01 23:31
13F：→ jojoboy0115: ? 12/01 23:31
14F：→ jojoboy0115: 这样是不是根本无法做@@ 12/01 23:31
15F：→ jojoboy0115: 是我多虑了… 12/01 23:32
16F：→ skyHuan: 这类型的题目如果是乱出的常常都会没写很好，出现没初始 12/01 23:36
17F：→ skyHuan: 值或无穷回圈的状况，有时候只能自己假设跑得出来才能写 12/01 23:36
18F：→ skyHuan: 了XD 12/01 23:36
19F：→ skyHuan: 不是乱出啦我的意思是直接用想的出题，没有很严谨去测试 12/01 23:37
20F：→ skyHuan: 跑不跑得出来 12/01 23:37
21F：推 jojoboy0115: 这样很两难呢>''<，是要猜出题者要考我们会不会写程 12/01 23:47
22F：→ jojoboy0115: 式，回答这题不会跑进while，还是像sky大讲的，就自 12/01 23:47
23F：→ jojoboy0115: 己假设n，不要管它loop判断式的问题...明明那些判断 12/01 23:47
24F：→ jojoboy0115: 跟改变index值都会影响答案... 12/01 23:47
25F：推 skyHuan: 他都考复杂度了应该就是假设n很大了，一开始i跟j进回圈 12/01 23:52
26F：→ skyHuan: 应该是不会被挡掉啦，也只能这样假设了... 12/01 23:52
27F：→ Marcolod: 我想弱弱的问，为什麽a 的cost 是log n 呀？ 01/11 14:20
28F：推 Marcolod: 我我我 我有看到了没事没事（ ・∀・）不好意思打扰了 01/11 14:23