演算法 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進迴圈應該是不會被擋掉啦，也只能這樣假設了...

繼續閱讀