推 psalms945:逐一比對的話,不就沒有divide and conquer了嗎? 03/19 17:40
→ assassin88:再F大的第四句話 03/19 17:55
※ 引述《psalms945 (上善若水)》之銘言：
: ※ 引述《FRAXIS (喔喔)》之銘言：
: : 先按照x軸排序
: : 以x軸座標找出中點把問題切成等量的兩半，遞迴求解。
: : 找出左半的Maximal Point和右半的Maximal Point（按照y軸排序）
: : 因為左半的x佐標必小於右半的y座標，所以只要看y軸的大小就可以確定
: : 有沒有被dominate，方法類似Mergesort的merge步驟。
: 這個步驟是怎麼判定有沒有被dominate
: 可以解釋的再詳細一點嗎?3Q
因為一開始已經由x座標排序過所有的點，
因此若由x座標最大的點開始比對，
一但有任何一點的y座標大於目前最大x座標點的y座標(令為p)，
則表示目前最大這個點p有被dominate。
這樣不知道你了解了嗎??
: : 沒有被dominate的Maximal Point就是解答..
: : 整個演算法除了一開始的排序需要O(nlgn)之外，其餘部分跟Mergesort
: : 類似，所以複雜度就是O(nlgn)。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.57.79.232