如果您对置换向量有线性描述，那么您可以在 O(n) 时间内解决它。您要做的是计算排列中循环的大小。从大小你计算。如果该总和为奇数，则行列式为，否则为。计算周期大小的算法非常简单。您只需维护一个访问过的向量以跳过访问过的条目，然后遍历排列，对于每个未访问过的向量，您跳入排列直到找到当前元素，同时将所有地点标记为已访问。$s_j$$\sum_{i=1}^p (s_i-1)$$1$$-1$

例如，如果您有，您将获得个周期：、和。尺寸为。计算的总和是，行列式是。$p = [1,0,2,4,5,3]$$3$${0,1}$${2}$${3,4,5}$$2,1,3$$9$$-1$

当您没有向量形式（线性大小形式）的置换矩阵描述时，就会出现问题。如果你所拥有的实际上是一个矩阵，那么你就无法避免在时间内运行，因为无论如何你都读取了矩阵。但是，您不必计算矩阵的任何归约，例如高斯消元或 LU 分解。当您不知道值时，这些过程是为密集矩阵设计的。有两种方法。第一个是通过将矩阵简化为置换向量来使用先前的解决方案。这当然有效，并且再次简单明了。$O(n^2)$

然而，还有另一种解决方案，它仍然是二次时间，因为你必须读取矩阵，但它只通过矩阵一次。这个想法源自如何使用辅因子计算矩阵行列式。如果您选择任何行或列，则行列式是所选行或列元素的总和乘以它们的辅因子。如果元素的行和列索引是偶数，则辅因子为，乘以元素值，乘以小数的行列式（当前元素所在的没有行和列的矩阵。更多细节在这里：拉普拉斯展开$-1$$1$. 该算法对稠密矩阵无用，因为它是时间阶乘的。但有趣的是，对于置换矩阵，它工作得很好。这个想法遵循下一个基本原理：辅因子扩展实际上产生了一个术语（因为所有其他值都是），因此在每次迭代中，一个计算必须具有正确的符号。这可以通过维护的已访问向量和和$0$$-1$$1$. 需要一点注意，但该算法在读取矩阵时计算行列式，这应该比第一个变体快得多。如果迭代方向正确（考虑到矩阵在内存中的存储方式），则矩阵的读取应该对齐，并且对于 O(n^2)，结果应该尽可能快。