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 choose 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!)。