迭代对称矩阵（或 n 维数组）的时间复杂度
Time Complexity for iterating over symmetric matrix (or n-dimensional arrays)
我很好奇迭代 对称矩阵 的 时间复杂度 。
我知道对于标准矩阵（二维数组），复杂度为 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]);
如果可能的话，我想对任何对称的多维数组展开相同的推理。
我无法自己计算，但是由于很多问题都是用这种方法解决的，所以我想在复杂性方面对它感到满意。
谢谢。
让我们看看我们在对称二维数组中迭代的元素数量，它是 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!)。
我很好奇迭代 对称矩阵 的 时间复杂度 。
我知道对于标准矩阵（二维数组），复杂度为 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]);
如果可能的话，我想对任何对称的多维数组展开相同的推理。
我无法自己计算，但是由于很多问题都是用这种方法解决的，所以我想在复杂性方面对它感到满意。
谢谢。
让我们看看我们在对称二维数组中迭代的元素数量，它是 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!)。