算法 P26 程式时间复杂度 ENGneweu PTT批踢踢实业坊

楼主: ENGneweu (威猛先生) 2018-12-01 22:20:49

我想请问这题b的时间复杂度要怎么求
我试着写出来但感觉不对
另外我的a做法是对的吗？
https://i.imgur.com/oKGKXSc.jpg

作者: Dora5566 (咩休干某) 2018-12-01 22:40:00

不对，他问复杂度你就不用理result是什么了，把它想成O（1就好）O（1）,另外问一下 if不成立时也算执行一次吗这题是次数是算1/4n^2还是1/2n^2

楼主: ENGneweu (威猛先生) 2018-12-01 22:49:00

你说a还是b的想法不对呢？if不成立的时候要扣掉因为会多算

作者: skyHuan (Huan) 2018-12-01 22:58:00

https://i.imgur.com/TMbbtAF.jpg上面空白的地方是n/2没写到...其实那个if else可以直接当成一个O(1)的指令，因为不管if有没有成立都会做一次运算

楼主: ENGneweu (威猛先生) 2018-12-01 23:18:00

感谢sky大解救想都没想到可以这样想

作者: jojoboy0115 (jojo) 2018-12-01 23:31:00

我觉得这程式很奇怪...用int 宣告n?这样n=0?还是null?这样是不是根本无法做@@是我多虑了…

作者: skyHuan (Huan) 2018-12-01 23:36:00

这类型的题目如果是乱出的常常都会没写很好，出现没初始值或无穷循环的状况，有时候只能自己假设跑得出来才能写了XD不是乱出啦我的意思是直接用想的出题，没有很严谨去测试跑不跑得出来

作者: jojoboy0115 (jojo) 2018-12-01 23:47:00

这样很两难呢>''<，是要猜出题者要考我们会不会写程式，回答这题不会跑进while，还是像sky大讲的，就自己假设n，不要管它loop判断式的问题...明明那些判断跟改变index值都会影响答案...

作者: skyHuan (Huan) 2018-12-01 23:52:00

他都考复杂度了应该就是假设n很大了，一开始i跟j进循环应该是不会被挡掉啦，也只能这样假设了...

继续阅读