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.... |