迭代对称矩阵（或n维数组）的时间复杂度

Question

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

我知道对于标准矩阵（二维阵列），复杂度是O（N2）。但是，对于对称矩阵，我们只迭代它的上三角部分而不是遍及它的所有元素。

这是迭代对称矩阵的常用算法：

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

现在让我们看一下在对称三维数组中迭代的元素数量。这是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!)。