[理工] 演算法 divide_and_conquer seika555 PTT批踢踢實業坊

[理工] 演算法 divide_and_conquer

作者: seika555 (kakkoii) 2018-09-09 12:26:55

https://imgur.com/3GQZN0a.jpg
關於上題的演算法在step 3 所提到的將y座標做排序
為什麼不用加進去 T(n)=2T(n/2)+θ(n) 變成
T(n)=2T(n/2)+θ(nlg(n)) 呢
是因為他在演算法裡面是先獨立出來自己排序
而不是在遞迴裡面所花到的時間嗎
還請大大們幫我解惑一下謝謝

作者: henry78925 (公車陰熊VER) 2018-09-09 22:28:00

寫錯了你的想法是對的複雜度是n log^2n

作者: FRAXIS (喔喔) 2018-09-10 04:46:00

只要一開始排序就夠了.. 所以在遞迴時只要花 O(n) 時間..

繼續閱讀

[理工] 離散 Catalan number 組合證法Nick12356464 [理工] 線代線性映射中的 onto 函數piskebee [理工] 計組 mips lbqazws3483 [理工] 線代eigenvectorhkdjiun Re: [理工] 線代 wronskianpiskebee [理工] 資結 Tree表示法 linked listpiskebee [心得] [英文]-台大107-共同英文AB卷答案speedwave [理工] 離散5-54qazws3483 Re: [理工] 線代 wronskianHonor1984 Re: [理工] 離散生成函數4-38Honor1984