algorithm - 是否有比 O(N²) 更好的算法来确定矩阵是否对称？

Question

算法要求

输入是大小为 N×N 的任意方阵 M，刚好 适合内存。

如果 M[i,j] = M[j,i] 对于所有 j≠i，算法的输出必须是 true， false 否则。

显而易见的解决方案

1. 检查转置是否等于矩阵本身 (M^T=M)。在许多环境中最容易编程，但(通常)消耗两倍的内存并且需要 N² 比较最坏的情况。因此，这是 O(N²) 并且具有高峰值内存。

2. 检查下三角部分是否等于上三角部分。当然，该算法会返回找到的第一个不等式。这将使最坏的情况(最坏的情况是，矩阵确实是对称的)需要 N²/2 - N 比较，因为不需要检查对角线。所以虽然它比选项 1 更好，但这仍然是 O(N²)。

问题

虽然很难看出它是如何可能的(N² 元素都必须以某种方式进行比较)，但是否有算法执行此检查比 O(N² )?

或者，如果有证据证明这种算法不存在:如何在多核 CPU(Intel 或 AMD)上最有效地实现它，同时考虑缓存友好性、最佳分支预测等因素特定于编译器的特化等？

这个问题主要源于学术兴趣，尽管我认为实际用途可能是确定在矩阵描述线性系统时使用什么求解器 AX=b...

Answer 1

由于您必须检查除对角线以外的所有元素，IMO 的复杂度不能比 O (n^2) 更好。