algorithm - 迭代对称矩阵(或 n 维数组)的时间复杂度

Question

我对迭代对称矩阵的时间复杂度感到好奇。

我知道对于标准矩阵(二维数组)，复杂度为 O(N^2)。然而，对于对称矩阵，我们只迭代它的上三角部分，而不是它的所有元素。

这是迭代对称矩阵的常见算法:

for(int i=0; i < symmetricM.length; i++) 
        for(int j=i; j < symmetricM.length; j++ )
            System.out.println("Elem: "+symmetricM[i][j]);

如果可能的话，我想将相同的推理扩展到任何对称多维数组。

我无法自己计算，但由于许多问题都是通过这种方法解决的，所以我希望在复杂性方面能够适应它。

谢谢。

Answer 1

让我们看看在对称二维数组中迭代的元素数量，它是 n^2/2，因为大小为 n 并且有 >2 维度，因此我们求 2 次方并除以 2 只得到一半的元素。所以O(n^2)。

现在让我们看看在对称 3 维数组中迭代的元素数量。是n^3/6。您可以用与计算 volume of a 3 dimensional triangle 相同的方式得出结论: ，因为所有数字都在这个三角形区域内。即使除以 3，时间复杂度也是 O(n^3)。

对于 4 维，它将是 n^4/(4*3*2)，即 O(n^4)。但对于 m 维度，它将是 n^m/m! 并且由于维度是一个参数，所以时间复杂度将是 O(n^m/m !)按照这个方法。

另一种计算方法是，如果您删除该维度的对角线，则如果没有重复元素并且所有元素都不同，则您要迭代的项目的索引与组合相同。我们知道组合的数量是 n!/m!(n-m)! 或 n 选择 m 所以这也可以是时间复杂度。

根据大多数factorial approximations最大的元素是 n^n 因此，当使用这些近似值并忽略相对较小的因素时，时间复杂度保持不变，因为:
n!/m!(n-m)! ≈ n^n/m!(n-m)^(n-m) > n^n/m!n^(n-m) = n^m/m!。

所以最终时间复杂度将是O(n^m/m!)。