算导学习——Young氏矩阵

  1. 1. 算导学习——Young氏矩阵
    1. 1.1. Young氏矩阵性质
    2. 1.2. Young tableau操作
      1. 1.2.1. 上滤
      2. 1.2.2. 下滤
      3. 1.2.3. 插入
      4. 1.2.4. 取最小值
      5. 1.2.5. 排序

算导学习——Young氏矩阵

Young氏矩阵(Young tableau):每一行从左到右排序,每一列从上到下排序。若某一元素为\(\infty\),则表示空。故一个Young氏矩阵可以保存\(n \le M \times N\)个有穷数。

Young氏矩阵性质

  • 对Young tableau中任意元素\(tableau[i,j]\),必有在以\((i,j)\)为右下角的“子矩阵”中,\(tableau[i,j]\)最大。

由此可知,在Young tableau中的非空元素部分,右下边界构成了整个矩阵的”最大值集“。

  • \(tableau[0,0] = \infty\),则表为空表,\(tableau[m,n] \neq \infty\),则表已满。

  • 各行、列有序

由此可知,Young tableau类似于一个二叉堆,任意一结点由二元组\((i,j)\)标识,且其二“子结点”为\((i-1, j)\)\((i, j-1)\)。但与二叉堆不同的是,不同结点的子结点中可能存在重叠。如\((i-1, j)\)\((i, j-1)\)有公共子结点\((i-1, j-1)\)。因此,可推知Young tableau拥有比二叉堆更强的“堆序性“。

Young tableau操作

上滤

如二叉堆一般,基本思想为寻找到结点\((i,j)\)及其两子结点\((i-1, j)\),\((i, j-1)\)的中最大值。若为其本身,则表明该部分已经有序且满足Young tableau的性质。

若不是,则交换其与最大值的位置,而后递归。此时即可知,为何要初始化Young tableau的空为\(\infty\)。因为仅当”空穴“为\(\infty\),与”空穴“的交换才总是有意义且成立的。

注意到tableau为二维数组,需要单独判断上边界与左边界。

同时需知,该上滤操作能成功的基础为除\((i,j)\)外,其他非空结点处的值有序,满足Young tableau的性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void  PercolateUp(ElementType tableau[][N], int i, int j) {

// at the top border
if (i == 0) {
ElementType key = tableau[i][j];
for (; j > 0 && key < tableau[i][j - 1]; j--) {
tableau[i][j] = tableau[i][j - 1];
}
tableau[i][j] = key;

return;
}

// at the left border
if (j == 0) {
ElementType key = tableau[i][j];
for (; i > 0 && key < tableau[i - 1][j]; i--) {
tableau[i][j] = tableau[i - 1][j];
}
tableau[i][j] = key;

return;
}

// find the max among the tableau[i][j], tableau[i-1][j], tableau[i][j-1].
// if tableau[i][j] is not the max, swap it with the maximum and recursive
int max_position_x = i, max_position_y = j;
if (tableau[max_position_x][max_position_y] < tableau[i - 1][j]) {
max_position_x = i - 1; max_position_y = j;
}
if (tableau[max_position_x][max_position_y] < tableau[i][j - 1]) {
max_position_x = i; max_position_y = j - 1;
}

// it means the young tableau is ordered
if (max_position_x == i && max_position_y == j) {
return;
}

swap(&tableau[i][j], &tableau[max_position_x][max_position_y]);
PercolateUp(tableau, max_position_x, max_position_y);
}

分析此算法在最差情况下的时间复杂度:

定义\(T(p)\)为任一\(M \times N\) Young tableau上的时间复杂度,其中\(p = m + n\)

\(T(p) = \begin{cases} \Theta(1) & p = 0 \\ T(p-1)+\Theta(1)& p \ge 1\end{cases}\)

\(\Rightarrow T(p) =\Theta(p) = \Theta(m+n)\)

下滤

与上滤基本相同,注意边界条件的改变即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void PercolateDown(ElementType tableau[][N], int i, int j) {

// at the bottom border
if (i == M - 1) {
ElementType key = tableau[i][j];
for (; j < N - 1 && tableau[i][j + 1] < key; j++) {
tableau[i][j] = tableau[i][j + 1];
}
tableau[i][j] = key;

return;
}

// at the right border
if (j == N - 1) {
ElementType key = tableau[i][j];
for (; i < M - 1 && tableau[i + 1][j] < key; i++) {
tableau[i][j] = tableau[i + 1][j];
}
tableau[i][j] = key;

return;
}


// find the min among the tableau[i][j], tableau[i+1][j], tableau[i][j+1].
// if tableau[i][j] is not the min, swap it with the minimum and recursive
int min_position_x = i, min_position_y = j;
if (tableau[i + 1][j] < tableau[min_position_x][min_position_y]) {
min_position_x = i + 1, min_position_y = j;
}
if (tableau[i][j + 1] < tableau[min_position_x][min_position_y]) {
min_position_x = i, min_position_y = j + 1;
}

if (min_position_x == i && min_position_y == j) {
return;
}

swap(&tableau[i][j], &tableau[min_position_x][min_position_y]);
PercolateDown(tableau, min_position_x, min_position_y);

}

此算法在最差情况下的时间复杂度:\(T(p) = \Theta(m+n)\)

插入

插入某元素可以很简单得由上滤得到,即将新插入的元素置于Young tableau的右下角,即设其为最大值,而后对其执行上滤操作。即可插入该值。

注意,根据Young tableau的性质,若右下角元素不为”空穴“,则表明整个表满了。不可继续执行Insert操作。

1
2
3
4
5
6
7
8
9
void Insert(ElementType tableau[][N], ElementType ele){
if (tableau[M - 1][N - 1] != INF) {
printf("the young tableau is full!");
return;
}

tableau[M-1][N-1] = ele;
PercolateUp(tableau, M - 1, N - 1);
}

此算法在最差情况下的时间复杂度:\(T(p) = \Theta(m+n)\)

取最小值

根据Young tableau的性质,第\((0,0)\)个元素即为最小值。取出该值后,应使其保持有序,采取与二叉堆类似的做法,将其赋值为\(\infty\),即设为空穴。而后将此元素下滤,即可保证Young tableau的有序性

1
2
3
4
5
6
7
8
9
ElementType ExtractMin(ElementType tableau[][N]) {

ElementType min = tableau[0][0];

tableau[0][0] = INF;
PercolateDown(tableau, 0, 0);

return min;
}

此算法在最差情况下的时间复杂度:\(T(p) = \Theta(m+n)\)

排序

使用一个\(n \times n\)的Young tableau,即可完成对\(n^2\)个数进行排序。时间复杂度为\(\Theta(n^3)\)

首先,将含有\(n^2\)个数的数组转化为一个Young tableau。采取不断将数组中的元素插入进一个空Young tableau中的方法实现

1
2
3
4
5
6
7
8
9
10
11
void ConvertArrayToYoungTableau(ElementType tableau[][N], const ElementType array[], int length) {

if (length > M * N) {
printf("the array is too long!");
return;
}

for (int i = 0; i < length; ++i) {
Insert(tableau, array[i]);
}
}

此算法在最差情况下的时间复杂度:\(T(p) = \Theta(n^3)\)

注意,此时一次插入的时间复杂度为\(\Theta(n)\),而数组长度为\(n^2\)

将该排序好的Young tableau不断的取出最小值,最终即可得到一个排好序数组。

具体方法实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Sort(ElementType array[], int length) {

ElementType tableau[M][N];
InitTableau(tableau);

ConvertArrayToYoungTableau(tableau, array, length);

// it means the tableau is empty
if (tableau[0][0] == INF) {
return;
}

for (int i = 0; i < length; ++i) {
array[i] = ExtractMin(tableau);
}
}

此算法在最差情况下的时间复杂度:\(T(p) = \Theta(n^2) + \Theta(n^3) + \Theta(n^3) = \Theta(n^3)\)