Joh*_*ohn 7 algorithm array-algorithms
给定是整数对(a1,b1),...,(an,bn).如果和,对i是" 配对" .什么是快速确定不受任何其他对支配的对列表的算法？jai < ajbi < bj
我们可以检查所有对,并且对于每对,通过再次遍历所有对来检查它是否被任何其他对支配.这个算法是有序的n^2.有订购算法n还是n log n？
我们可以及时找到非支配对O(n log n).
按降序排序对a_i,然后迭代对.另外,跟踪b到目前为止看到的最大值,b_max.在每个步骤中,如果下一(a_i,b_i)
对的b值大于b_max,则将其附加到答案列表并更新b_max.最终答案列表将是非支配对.
正确性:当且仅当某一对具有更大的a
值且更大时,一对被支配b.当我们考虑一对时,我们将它的b值精确地b与具有较大值的对中的最大值进行比较a,因此当且仅当它不被支配时,我们将一对添加到列表中.
运行时:按值对对进行排序需要O(n log n)时间.迭代需要O(n)时间,因此整个运行时间是O(n log n).