作为经常啃组合优化问题的开发者，我来拆解你的问题——首先得明确：积和式是#P-完全问题，不存在多项式时间算法，所以当前最高效的计算方式都是基于包含-排除原理的指数级算法，也就是你提到的这三个公式。

三者的计算速度差异 #

从理论渐近复杂度来看，三者都是O(n*2^n)，这也是维基百科说“速度相当”的核心原因——当矩阵规模n足够大时，它们的增长趋势是完全一致的。但实际运行中，Balasubramanian-Bax-Franklin（简称BBF）和Glynn公式往往能比Ryser快一倍左右，这源于细节上的实打实优化：

• Ryser公式需要遍历所有非空子集，计算每个子集对应的行列式，还要根据子集大小判断符号，额外增加了分支判断的开销；
• BBF公式借助复数单位根的性质，把符号判断转化为复数运算中的相位处理，去掉了条件分支，同时减少了部分冗余计算；
• Glynn公式更进一步，利用子集的互补对称性，只需要遍历一半的子集（2^(n-1)个），每个子集的计算可以同时得到补集的结果，直接把行列式计算量砍了一半。

能否用数学方法证明某类公式更优？ #

首先，渐近复杂度层面没法分出胜负，因为三者的最高阶项都是n*2^n，系数也属于同一量级，渐近分析只关注增长趋势，所以从这个角度说它们是等价的。

但在常数因子优化上，是可以严格证明BBF和Glynn更高效的：

• 比如Glynn公式的推导中，通过数学变换可以证明，对于任意子集S，其对应的项和补集\bar{S}的项可以通过一次行列式计算得到，因此只需要计算2^(n-1)个行列式，而Ryser需要2^n - 1个——这个数量上的减半是可以严格推导的，属于数学上的明确优化；
• BBF公式则利用了单位根的正交性，将符号求和转化为复数域的线性组合，避免了Ryser中每个子集都要判断奇偶性的操作，这在数学上减少了计算步骤的数量，反映到代码中就是更低的运行开销。

不过要清楚，这种“更优”是在指数级框架下的常数因子提升，不是复杂度级别的突破——毕竟积和式的#P-完全性摆在那儿，我们没法指望找到比指数级更快的算法，这些公式已经是当前能做到的极致了。

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