Lio*_*gan 11 sorting algorithm
给定一个排序的整数数组,我们可以构建一个O(n ^ 2)中所有对的总和的排序数组吗？
一个简单的解决方案是在O(n ^ 2)中构建和数组,然后在O(n ^ 2(log(n ^ 2))= O(n ^ 2 logn)时间内对其进行排序.
另一个解决方案是在O(n ^ 2)中构建n个排序的n个数组 - 在O(n ^ 2 logn)时间内合并它们(例如参见这里).
我们可以做得更好吗？
Dav*_*tat 8
这是文献中称为分类X + Y的开放性问题.已知的最佳结果是使用O(n ^ 2)比较的O(n ^ 2 log n)时间算法,归因于Lambert和Steiger - Streinu.
归档时间：
12 年，5 月 前
查看次数：
289 次
最近记录：