h*********i
发帖数: 2605 | 1 我记得以前有人讨论过。一种方法是merge sort, maintain a heap，用时O(n^2logn)
，还有更快的方法么？ |
h*********i
发帖数: 2605 | |
k*k
发帖数: 49 | 3 Constructing Young's Tableau does not offer too much benefit on sorting...
for n^2 numbers, the lower bound for comparison-based sorting is
2 n^2 log n (or N log N if N == n^2)
given each row/col is sorted, sorting will take in O(N^1.5) N * sqrt(N);
N for total numbers, sqrt(N)=n for complexity to extract min from remaining matrix.
N*sqrt(N) > N log N ...
so i guess it is better just sort it directly. |
h*********i
发帖数: 2605 | 4 一共n*n个数字，怎么可能O(N)时间完成呢。
假设你说的是O(n^2)，虽然行列都sort好了，但是：
a1 a2
b1 b2
我们还是不知道b1和a2的相对大小
所以每次要从n行里找出最大的（用heap），用O(logn)时间。所以总共应该是O(n^
2logn)。
remaining matrix.
【在 k*k 的大作中提到】
: Constructing Young's Tableau does not offer too much benefit on sorting...
: for n^2 numbers, the lower bound for comparison-based sorting is
: 2 n^2 log n (or N log N if N == n^2)
: given each row/col is sorted, sorting will take in O(N^1.5) N * sqrt(N);
: N for total numbers, sqrt(N)=n for complexity to extract min from remaining matrix.
: N*sqrt(N) > N log N ...
: so i guess it is better just sort it directly.
|
h*********i
发帖数: 2605 | 5 发现你刚才修改过了。
我也觉得O(NlogN)是最快的。
remaining matrix.
【在 k*k 的大作中提到】
: Constructing Young's Tableau does not offer too much benefit on sorting...
: for n^2 numbers, the lower bound for comparison-based sorting is
: 2 n^2 log n (or N log N if N == n^2)
: given each row/col is sorted, sorting will take in O(N^1.5) N * sqrt(N);
: N for total numbers, sqrt(N)=n for complexity to extract min from remaining matrix.
: N*sqrt(N) > N log N ...
: so i guess it is better just sort it directly.
|
k*k
发帖数: 49 | 6 yes... but with additional space for min-heap
considering the complexity of constructing such a table in addition to the n
^2 log n sorting complexity...
young's table is really not a good way to tackle sorting problem.... |
