知识卡片

普通读书笔记卡 · 3614

杨氏矩阵双向单调

理解等级:中级

Young tableau 是行从左到右、列从上到下均非降序的矩阵,可用 ∞ 标示空位。左上角最小有限值由定义直接推出。

习题 6-3 要求读者设计提取与插入:提取后让 ∞ 向右下沉,插入时让新值从空位向左上移动;每步只比较相邻行列,路径至多 m+n。

这张卡片看不懂?

已有反馈 · 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.