Python中munkres库时间复杂度疑问：O(n³)还是O(n⁴)？

我完全理解你的困惑——刚看到这段Step4的代码时，我也差点以为它是O(n⁴)的复杂度。不过仔细拆解算法的执行流程和状态变化，就能明白它确实符合O(n³)的时间复杂度。

先理清匈牙利算法的复杂度核心 #

标准匈牙利算法的O(n³)复杂度，来自于三个层面的操作：

• 首先，矩阵的初始化（行/列减最小值）是O(n²)；
• 其次，寻找增广路径的过程是整个算法的核心，每次增广路径的寻找最多花费O(n²)时间，而最多需要O(n)次增广；
• 把这两部分结合起来，总复杂度就是O(n³)。

针对Step4代码的具体分析 #

你贴出的Step4代码是寻找未覆盖0并标记为prime的过程，看起来有嵌套循环，但实际上：

1. 单次Step4的循环次数是有限的
   代码里的循环逻辑是：找到未覆盖0→标记prime→如果行里有starred 0，就覆盖该行、揭开对应列→重复这个过程。
   每次执行“覆盖行+揭开列”的操作时，未覆盖的行与列的总数是严格递减的（覆盖一行减少一个未覆盖行，揭开一列增加一个未覆盖列，但整体来看，覆盖的行数会逐步增加，直到找到一个没有starred 0的行，触发Step5）。所以单次Step4里的循环最多执行O(n)次。

2. Step4的总调用次数被严格控制
   整个算法中，Step4只会在两种场景下被触发：要么是初始化后的标记阶段，要么是每次调整矩阵后的重新标记阶段。而每次增广路径完成后，starred 0的数量会增加1（最多增加n次），每次调整矩阵的操作也是O(n²)。把所有Step4的调用次数加起来，总迭代次数是O(n²)，乘以单次Step4的O(n)操作，就是O(n³)的总复杂度。

为什么看起来像O(n⁴)？ #

你可能是看到了嵌套的循环结构（比如外层的矩阵遍历+Step4内部的循环），但实际上这些循环并不是完全独立的嵌套——算法通过覆盖状态、starred/primed 0的数量这些状态变量，限制了循环的总执行次数，不会出现n⁴级别的迭代。

Munkres库的实现是遵循标准匈牙利算法的优化逻辑的，所以它的时间复杂度确实是O(n³)，只是从代码片段上看容易产生误解而已。

内容的提问来源于stack exchange，提问作者Taha Tariq