知识卡片
杨氏矩阵双向单调
Young tableau 是行从左到右、列从上到下均非降序的矩阵,可用 ∞ 标示空位。左上角最小有限值由定义直接推出。
习题 6-3 要求读者设计提取与插入:提取后让 ∞ 向右下沉,插入时让新值从空位向左上移动;每步只比较相邻行列,路径至多 m+n。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 杨氏矩阵双向单调
原书出处 · 1 处
- 第6章 堆排序 · 查看原书依据
An m × n Young tableau is an m × n matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom.
参考来源
- 位置:《算法导论(第4版)》第 6 章 6.5 节、Problems 与 Chapter notes(`OEBPS/chapter006.xhtml`,文本字符 [30000, 35000);图 6.5)。
- 结论依据:问题 6-3 给出行列双向非降序与 ∞ 空位定义,并要求证明提取、插入均可 O(m+n);相邻比较和路径长度是基于该定义的解题推导。
- 原始内容:An m × n Young tableau is an m × n matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom.