作者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/m.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