Scipy的linprog求解器的算法复杂度相关问题咨询

首先明确：scipy.optimize.linprog 支持多类求解器，你提到的文档对应其内置的**内点法（interior-point）**求解器，各求解器的复杂度情况如下：

• 内点法（interior-point）
  该求解器基于Mehrotra预测-校正原对偶内点法实现：
  • 最坏情况复杂度：对于含m个约束、n个变量的线性规划问题，理论最坏时间复杂度为O((m+n)³√L)，其中L为问题输入数据的总比特长度；部分场景下也可按*O(n³L)*估算，仅在极端构造的问题中才会触发该最坏情况。
  • 平均/实际运行复杂度：绝大多数工程场景下，该算法迭代次数稳定在20~50次，和问题规模几乎无关；单次迭代时间复杂度为O((m+n)³)，若问题的约束矩阵为稀疏矩阵，会针对性做稀疏优化，耗时和约束矩阵的非零元素数量正相关，远低于稠密场景的复杂度。
• 其他可选求解器
  若你使用linprog时指定了其他求解器，复杂度参考如下：
  • 修订单纯形法：最坏情况为指数级（典型触发场景为Klee-Minty立方体类构造问题），但平均运行复杂度为多项式级，中小规模稠密问题上实际运行速度通常优于内点法。
  • HiGHS系列求解器（Scipy 1.6+版本内置，为当前默认求解器）：包含的内点法、单纯形法复杂度和上述对应算法的理论复杂度一致，实测性能远高于旧版内置求解器。

官方文档未标注复杂度的原因是：线性规划求解器的实际运行性能受问题稀疏性、约束结构、数值稳定性等多重因素影响，理论复杂度仅能做参考，标注固定数值反而容易对用户产生误导，因此官方仅说明算法实现逻辑，不直接给出复杂度标注。

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