当前位置: 首页 > 工具软件 > Young > 使用案例 >

Young氏矩阵

瞿和硕
2023-12-01

6-3 Young氏矩阵
    一个m x n的Young氏矩阵(Young tableau)是一个m x n的矩阵,其中每一行的数据都从左到右排序,每一列的数据都从上到下排序。Young氏矩阵中可能会有一些∞数据项,表示不存在的元素。所以,Young氏矩阵可以用来存放r≦mn个有限的数。
    a)画一个包含元素{9,6,3,2,4,8,5,14,12}的4 x 4的Young氏矩阵。
    b)讨论一个m x n的Young氏矩阵,如果Y[1,1]=∞,则Y为空;如果Y[m,n]<∞,则Y是满的(包含m x n个元素)。
    c)给出一个在非空m x n的Young氏矩阵上实现EXTRACT-MIN的算法,使其运行时间为O(m+n)。你的算法应该使用一个递归子过程,它通过递归地解决(m-1) x n或m x (n-1)子问题来解决m x n的问题。(提示:考虑一个MAX-HEPIFY。)定义T(p)为EXTRACT-MIN在任何m x n Young氏矩阵上的最大运行时间,其中p=m+n。给出表达T(p)的、界为O(m+n)的递归式,并解该递归式。
    d)说明如何在O(m+n)时间内,将一个新元素插入到一个未满的m x n Young氏矩阵中。
    e)在不用其他排序算法帮助的情况下,说明如何利用n x n Young氏矩阵对n^2个数排序的运行时间为O(n^3)。
    f)给出一个运行时间为O(m+n)的算法,来决定一个给定的数是否在于一个给定的的m x n Young氏矩阵内。

 

分析与解答:

     a)遵循每一行的数据都从左到右排序,每一列的数据都从上到下排序,可以很容易写出一个可能的Young氏矩阵

          2       3       4        5

          6       8       9        12

         14      ∞      ∞       ∞

          ∞      ∞      ∞       ∞

 

     b)Y[1,1]是Young氏矩阵中最小的元素,如果它为∞,说明矩阵中每个元素的值均不小于∞,即每个元素均是∞,所以Y为空;Y[m,n]是Young氏矩阵中最大的元素,如果Y[m,n]<∞,说明矩阵中每个元素均小于∞,即Y是满的

 

     c)采用类似堆中提取最小元素的方法:将Young氏矩阵中最末的元素和第一个元素交换,然后类似MAX-HEAPIFY的方法调整第一个元素,整个过程如下:

 

 

 

而YOUNG-MIN-HEPIFY是一个递归过程。YOUNG-MIN-HEAPIFY(A, m, n)会和它紧邻的结点比较,要么调用YOUNG-MIN-HEAPIFY(A, m, n-1),要么调用YOUNG-MIN-HEAPIFY(A, m-1, n)。若令p=m+n,则有:

     T(p)= T(p-1)+O(1)

则总的运行时间为O(p),即为O(m+n)

 

   d)采用类似堆中增加元素的方法,先将∞放在Young矩阵的末尾,然后采用类似INCREASE-KEY的方法,向上调整

 

 

 

 


类似于上面的分析,若令p=m+n,则有:

     T(p)= T(p-1)+O(1)

则总的运行时间为O(p),即为O(m+n)

 

    e)每次提取其中的最小元素,调用YOUNG-EXTRACT-MIN,共需调用n  x n次,而每次YOUNG-EXTRACT-MIN需要O(n+n)运行时间,故总的运行时间为O(n^3)

 

   f)每次与最右上角的元素X相比:如果等于X,则找到了;如果小于X,则去掉最上面一行;如果大于X,则去掉最右边一行。

每次比较去掉一行或一列,则该算法的运行时间为O(m+n)

 

 

 

 类似资料: