我只是想知道是否有一种方法可以在线性（或至少比n^2更好？）时间内计算排列的符号

例如，假设我有一个n个数字的数组，我在这个数组中置换两个元素，这将翻转排列的符号。我有一个函数可以在n^2时间内计算它，然而，似乎有一个更有效的算法。

我附上了一个二次时间计算的最小可重现示例，

import numpy as np

vals = np.arange(1,6,1)
pvals = np.arange(1,6,1)
pvals[0], pvals[1] = pvals[1], pvals[0] #swap

def quadratic(vals):
  sgn_matrix = np.sign(np.expand_dims(vals, -1) - np.expand_dims(vals, -2))
  return np.prod(np.tril(np.ones_like(sgn_matrix)) + np.triu(sgn_matrix, 1))

def sub_quadratic(vals):
  #algorithm quicker than quadratic time?

sgn = quadratic(vals)
print(sgn)   #prints +1 

psgn = quadratic(pvals)
print(psgn)  #prints -1 (because one permutation)

我环顾了一下SO（例如这里），人们一直在谈论循环排列，这种排列显然可以在线性时间内计算，但这是我完全没有意识到的，也找不到太多关于我自己的东西。

太长别读有人知道一种计算次二次时间排列符号的方法吗？