杨氏矩阵（Young Tableau）插入操作的时间复杂度是否为O(mn)

问题结论 #

你给出的时间复杂度结论是正确的，我们可以从你的算法步骤拆解时间开销来验证：

• 第一步将待插入元素放到右下角属于O(1)的常量操作，没有额外开销。
• 第二步向上移动元素的最坏情况是需要移动完整一列，最多执行m次交换操作，时间开销为O(m)（m为矩阵行数）。
• 第三步向左移动元素的最坏情况是需要移动完整一行，最多执行n次交换操作，时间开销为O(n)（n为矩阵列数）。
• 第四步错位元素归位是拉高整体复杂度的核心：你示例中仅产生了3个错位元素，但最坏场景下移位产生的错位元素数量可以达到O(m*n)量级，每个元素归位都需要做比较、移位操作，最终整体最坏时间复杂度就是O(m*n)。

额外补充 #

标准杨氏矩阵的插入操作最优时间复杂度可以做到O(m+n)，实现逻辑和你的方案差异在于：将元素放到右下角后，每次同时比较当前元素的上边、左边相邻元素，选择其中更大的那个进行交换，直到当前元素的上边和左边元素都小于自身、满足杨氏矩阵性质就停止，不需要额外单独做错位元素归位步骤，你当前的算法因为多了归位环节才拉高了时间复杂度。

内容的提问来源于stack exchange，提问作者Dawson Smith