线性和分配问题：结构化成本矩阵下的更快算法探究

你提的问题非常有意思——结构化成本矩阵确实是降低线性和分配问题（LSAP）复杂度的关键突破口，下面我分两部分来详细解答：

一、低秩、稀疏、带状成本矩阵的复杂度优化 #

标准匈牙利算法的$O(n^3)$复杂度是针对无结构的稠密成本矩阵而言的。当成本矩阵带有特定结构时，确实能找到更高效的算法：

• 低秩成本矩阵：如果成本矩阵可以分解为$C = UV^{T$（$U∈ℝ}{nk}$，$V∈ℝ^{nk}$，$k≪n$），有研究提出基于矩阵分解的改进算法，复杂度可以降到$O(kn²)$甚至更低，远优于$O(n³)$。核心思路是利用低秩特性减少每次迭代中需要处理的元素数量，避免全矩阵的遍历。
• 稀疏成本矩阵：如果成本矩阵中大部分元素是无穷大（或者说只有少量可行分配），可以采用稀疏版本的匈牙利算法。这类算法只处理非无穷大的元素，复杂度会和矩阵的非零元数量相关。比如当非零元数量为$O(n)$时，复杂度能降到$O(n²)$；如果是$O(n \log n)$的非零元，复杂度也能保持在接近$O(n²)$的水平，比标准$O(n³)$高效很多。
• 带状成本矩阵：当成本矩阵只有主对角线附近的一个窄带内有有限值时（比如带宽为$w$，$w≪n$），可以利用带状结构限制算法中搜索增广路径的范围。这类场景下，改进的匈牙利算法复杂度可以降到$O(nw²)$，当$w$远小于$n$时，性能提升非常明显。

二、分块对角成本矩阵的复杂度分析 #

你关于分块对角矩阵的推导是完全正确的！我们再理一遍逻辑：
假设成本矩阵是$b$个大小为$n/b$的对角块组成的分块对角矩阵，且所有非对角块的元素都是$+∞$——这意味着不同块之间的分配完全不可行（成本无穷大，不会被选中）。
此时整个LSAP问题会自然分解成$b$个独立的子LSAP问题，每个子问题的规模是$n/b$。每个子问题用标准匈牙利算法的复杂度是$O((n/b)^{3)$，$b$个子问题的总复杂度就是$O(b*(n/b)}3) = O(n³/b²)$。

举个直观的例子：如果$n=1000$，$b=10$，总复杂度会从$O(10^{9)$降到$O(10}7)$，性能直接提升两个数量级，这个优化效果非常显著。

备注：内容来源于stack exchange，提问作者calmcc