作者seika555 (kakkoii)
看板Grad-ProbAsk
标题[理工] 演算法 divide_and_conquer
时间Sun Sep 9 12:26:55 2018
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1536467221.A.4A9.html
1F：推 henry78925: 写错了 你的想法是对的 复杂度是n log^2n09/09 22:28
谢谢h大 所以在令T(n)时间函数时 就是要考虑到丢去递回的情况以及各步骤的时间复杂
度吗
※ 编辑: seika555 (114.137.81.168), 09/10/2018 00:18:08
2F：推 FRAXIS: 只要一开始排序就够了.. 所以在递回时只要花 O(n) 时间..09/10 04:46
谢谢f大 所以题目意思说先排序完再去做递回吗
※ 编辑: seika555 (114.137.217.75), 09/10/2018 12:29:28