演算法 P26 程式時間複雜度

看板Grad-ProbAsk作者 (威猛先生)時間7年前 (2018/12/01 22:20), 7年前編輯推噓6(6推 0噓 22→)
留言28則, 5人參與, 8年前最新討論串1/1
我想請問這題b的時間複雜度要怎麼求 我試著寫出來 但感覺不對 另外我的a做法是對的嗎？ https://i.imgur.com/oKGKXSc.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.144.53 ※ 文章網址: https://www.ptt.cc/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
推
12/01 22:40, 7年前 , 1F
不對，他問複雜度你就不用理result是什麼了，把它想成O
12/01 22:40, 1F
→
12/01 22:40, 7年前 , 2F
（1就好）
12/01 22:40, 2F
→
12/01 22:41, 7年前 , 3F
O（1）,另外問一下 if不成立時也算執行一次嗎
12/01 22:41, 3F
→
12/01 22:42, 7年前 , 4F
這題是次數是算1/4n^2還是1/2n^2
12/01 22:42, 4F
→
12/01 22:49, 7年前 , 5F
你說a還是b的想法不對呢？
12/01 22:49, 5F
→
12/01 22:49, 7年前 , 6F
if不成立的時候要扣掉 因為會多算
12/01 22:49, 6F
推
12/01 22:58, 7年前 , 7F
12/01 22:58, 7F
→
12/01 22:59, 7年前 , 8F
上面空白的地方是n/2沒寫到...
12/01 22:59, 8F
→
12/01 22:59, 7年前 , 9F
其實那個if else可以直接當成一個O(1)的指令，因為不管if
12/01 22:59, 9F
→
12/01 22:59, 7年前 , 10F
有沒有成立都會做一次運算
12/01 22:59, 10F
→
12/01 23:18, 7年前 , 11F
感謝sky大解救 想都沒想到可以這樣想
12/01 23:18, 11F
推
12/01 23:31, 7年前 , 12F
我覺得這程式很奇怪...用int 宣告n?這樣n=0?還是null
12/01 23:31, 12F
→
12/01 23:31, 7年前 , 13F
?
12/01 23:31, 13F
→
12/01 23:31, 7年前 , 14F
這樣是不是根本無法做@@
12/01 23:31, 14F
→
12/01 23:32, 7年前 , 15F
是我多慮了…
12/01 23:32, 15F
→
12/01 23:36, 7年前 , 16F
這類型的題目如果是亂出的常常都會沒寫很好，出現沒初始
12/01 23:36, 16F
→
12/01 23:36, 7年前 , 17F
值或無窮迴圈的狀況，有時候只能自己假設跑得出來才能寫
12/01 23:36, 17F
→
12/01 23:36, 7年前 , 18F
了XD
12/01 23:36, 18F
→
12/01 23:37, 7年前 , 19F
不是亂出啦我的意思是直接用想的出題，沒有很嚴謹去測試
12/01 23:37, 19F
→
12/01 23:37, 7年前 , 20F
跑不跑得出來
12/01 23:37, 20F
推
12/01 23:47, 7年前 , 21F
這樣很兩難呢>''<，是要猜出題者要考我們會不會寫程
12/01 23:47, 21F
→
12/01 23:47, 7年前 , 22F
式，回答這題不會跑進while，還是像sky大講的，就自
12/01 23:47, 22F
→
12/01 23:47, 7年前 , 23F
己假設n，不要管它loop判斷式的問題...明明那些判斷
12/01 23:47, 23F
→
12/01 23:47, 7年前 , 24F
跟改變index值都會影響答案...
12/01 23:47, 24F
推
12/01 23:52, 7年前 , 25F
他都考複雜度了應該就是假設n很大了，一開始i跟j進迴圈
12/01 23:52, 25F
→
12/01 23:52, 7年前 , 26F
應該是不會被擋掉啦，也只能這樣假設了...
12/01 23:52, 26F
→
01/11 14:20, 8年前 , 27F
我想弱弱的問，為什麼a 的cost 是log n 呀？
01/11 14:20, 27F
推
01/11 14:23, 8年前 , 28F
我我我 我有看到了沒事沒事（ ・∀・）不好意思打擾了
01/11 14:23, 28F
‣ 更多 ENGneweu 的文章
文章代碼(AID): #1S0fZ3kI (Grad-ProbAsk)