[理工] 演算法 divide_and_conquer

[seika555 (kakkoii)]

https://imgur.com/3GQZN0a.jpg

關於上題的演算法 在step 3 所提到的將y座標做排序

為什麼不用加進去 T(n)=2T(n/2)+θ(n) 變成

T(n)=2T(n/2)+θ(nlg(n)) 呢

是因為他在演算法裡面是先獨立出來自己排序

而不是在遞迴裡面所花到的時間嗎

還請大大們幫我解惑一下 謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.213.244
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1536467221.A.4A9.html
推 henry78925: 寫錯了 你的想法是對的 複雜度是n log^2n
謝謝h大 所以在令T(n)時間函數時 就是要考慮到丟去遞迴的情況以及各步驟的時間複雜
度嗎
※ 編輯: seika555 (114.137.81.168), 09/10/2018 00:18:08
推 FRAXIS: 只要一開始排序就夠了.. 所以在遞迴時只要花 O(n) 時間..
謝謝f大 所以題目意思說先排序完再去做遞迴嗎
※ 編輯: seika555 (114.137.217.75), 09/10/2018 12:29:28