w****x
发帖数: 2483 | 1 怎么inplace调整一个m*n普通矩阵成为一个Young tableau 矩阵？
能做到O(m*n)吗？ |
f*******4
发帖数: 64 | 2 如果基于比较的方法可以做到可以O(m*n), 那么对任意m*n个元素排序，只需要对young
进行(m*n)lgm的堆排序。
固定m的取值，相当于总排序时间为O(N)
【在 w****x 的大作中提到】
: 怎么inplace调整一个m*n普通矩阵成为一个Young tableau 矩阵？
: 能做到O(m*n)吗？
|
p******9
发帖数: 47 | 3 杨式矩阵长的挺像堆的，不知道能不能把杨式矩阵就看成堆，走一遍buildHeap的过程
？ |
l*********8
发帖数: 4642 | 4 我认为不能固定m的取值。 不然的话，我再固定n的取值，算法就算成O(1)了？ 呵呵
young
【在 f*******4 的大作中提到】
: 如果基于比较的方法可以做到可以O(m*n), 那么对任意m*n个元素排序，只需要对young
: 进行(m*n)lgm的堆排序。
: 固定m的取值，相当于总排序时间为O(N)
|
l*********8
发帖数: 4642 | 5 考虑一个比杨氏矩阵弱的情况A： 只要求矩阵每行有序，不要求每列也有序。
in-place 调整一个矩阵来满足条件A，可对每一行做quick-sort。
每一行时间是O(n*lgn), 有m行，所以总时间复杂度是O(m*n*lgn).
所以，我认为，对于要求更高的杨氏矩阵，不可能在O(m*n)time in-place调整完成。
【在 w****x 的大作中提到】
: 怎么inplace调整一个m*n普通矩阵成为一个Young tableau 矩阵？
: 能做到O(m*n)吗？
|
f*******4
发帖数: 64 | 6 针对N个数来说, N总能拆分成10*(N/10), 这样理解无问题吧？
【在 l*********8 的大作中提到】
: 我认为不能固定m的取值。 不然的话，我再固定n的取值，算法就算成O(1)了？ 呵呵
:
: young
|
l*********8
发帖数: 4642 | 7 O(N/10) 还是 O(N)啊
【在 f*******4 的大作中提到】
: 针对N个数来说, N总能拆分成10*(N/10), 这样理解无问题吧？
|
f*******4
发帖数: 64 | 8 只是行有序,根据决策树计算是O(m*nlgn)
根据决策树比较可以得出杨氏矩阵更难达到
题外，发现求杨氏矩阵的决策树具体表达式，貌似不那么简单？
。
【在 l*********8 的大作中提到】
: 考虑一个比杨氏矩阵弱的情况A： 只要求矩阵每行有序，不要求每列也有序。
: in-place 调整一个矩阵来满足条件A，可对每一行做quick-sort。
: 每一行时间是O(n*lgn), 有m行，所以总时间复杂度是O(m*n*lgn).
: 所以，我认为，对于要求更高的杨氏矩阵，不可能在O(m*n)time in-place调整完成。
|
l*********8
发帖数: 4642 | 9 是的， 我认为，杨氏矩阵不可能在O(m*n)time in-place调整完成。
【在 f*******4 的大作中提到】
: 只是行有序,根据决策树计算是O(m*nlgn)
: 根据决策树比较可以得出杨氏矩阵更难达到
: 题外，发现求杨氏矩阵的决策树具体表达式，貌似不那么简单？
:
: 。
|
f*******4
发帖数: 64 | 10 是啊，所以根据O(m*n)的结果，推出来矛盾
【在 l*********8 的大作中提到】
: O(N/10) 还是 O(N)啊
|
|
|
l*********8
发帖数: 4642 | 11 就算10000也是常量，但m在本题目里面是影响输入规模的变量
另外， 你的N跟n是一个意思吗？
【在 f*******4 的大作中提到】
: 是啊，所以根据O(m*n)的结果，推出来矛盾
|
f*******4
发帖数: 64 | 12 大小写有区别
假设m*n可以O(m*n)，那m=10的时候，也是成立的吧？
考虑对N个数排序，就可以先构造10 * (N/10)的数组了
_______
上头有点费劲了，直接考虑m=1
【在 l*********8 的大作中提到】
: 就算10000也是常量，但m在本题目里面是影响输入规模的变量
: 另外， 你的N跟n是一个意思吗？
|
w****x
发帖数: 2483 | |
w****x
发帖数: 2483 | 14 const int M = 5;
const int N = 6;
void siftMaintain(int a[M][N], int i, int j)
{
if (i >= M || j >= N)
return;
while (i >= 0 && j >= 0)
{
int imax = i;
int jmax = j;
if (i-1 >= 0 && a[i-1][j] > a[imax][jmax])
{
imax = i-1;
jmax = j;
}
if (j-1 >= 0 && a[i][j-1] > a[imax][jmax])
{
imax = i;
jmax = j-1;
}
if (imax == i && jmax == j)
break;
swap(a[i][j], a[imax][jmax]);
i = imax;
j = jmax;
}
}
void youngTabulify(int a[M][N])
{
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
siftMaintain(a, i, j);
}
写了一个 |
Y********f
发帖数: 410 | 15 求科普，啥是Young tableau矩阵
【在 w****x 的大作中提到】
: 怎么inplace调整一个m*n普通矩阵成为一个Young tableau 矩阵？
: 能做到O(m*n)吗？
|
