[理工] 算法 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