分析矩阵的嵌套for循环的时间复杂性 [英] Time Complexity of a nested for loop that parses a matrix
问题描述
假设我有一个矩阵，它有X行和Y列。元素的总数是X*Y，对吗？那么这就是n=X*Y吗？
for (i=0; i<X; i++)
{
for (j=0; j<Y; j++)
{
print(matrix[i][j]);
}
}
那么这不是意味着这个嵌套的for循环是O(N)吗？还是我误解了时间复杂性是如何起作用的？
一般来说，我以为所有嵌套的for循环都是O(n^2)，但如果它通过X*Y调用print()，这不是意味着时间复杂度是O(X*Y)，X*Y等于n吗？
推荐答案
此答案写得很仓促，受到了一些反对票，因此我决定澄清并重写
算法的时间复杂性是该算法的运算次数与该算法要解决的问题的大小的关系。
这里涉及两个大小。
第一个大小是矩阵X×Y的元素数，它对应于复杂性理论中所知的输入大小。设k=X×Y表示矩阵中元素的个数。由于孪生循环中的运算次数为X×Y，因此为O(K)。
第二个大小是矩阵的列数和行数。设m=max(X，Y)。孪生循环中的运算次数为O(m^2)。在线性代数中，这种大小通常用来刻画m×m矩阵上矩阵运算的复杂性。
当您谈论复杂性时，您必须准确地指定如何编码实例问题以及使用什么参数来指定其大小。在复杂性理论中，我们通常假设算法的输入是由来自某个有限字母表的字符串给出的，并根据长度为n的字符串对问题实例的操作次数的上界来衡量算法的复杂性。也就是说，在复杂性理论中，n通常是输入的大小。
在算法的实际复杂性分析中，我们经常使用在特定上下文中更有意义的其他实例大小度量。例如，如果A是图的连通矩阵，我们可以使用顶点数V作为问题实例的复杂性的度量，或者如果A是作用于向量空间的线性算子的矩阵，我们可以使用向量空间的维度作为这样的度量。对于平方矩阵，约定是用矩阵的维度来指定复杂性，即用n来衡量算法作用于n×n矩阵的复杂性。它通常具有实际意义，而且也符合特定应用领域的约定，即使它可能与复杂性理论的约定相冲突。
让我们将我们的孪生循环命名为矩阵扫描。如果Matrix Scan的实例的大小是矩阵的字符串编码的长度，那么您可以合理地这样说。假设条目的大小有限，它是矩阵中元素的数量k。那么我们可以说矩阵扫描的复杂度为O(K)。另一方面，如果我们采用m=max(X，Y)作为表征实例复杂性的参数，则X×Y矩阵的矩阵扫描复杂度也将为O(m^2)。对于方阵X=Y=m，O(K)=O(m^2)。
注意：评论中的一些人问我们是否总是可以找到问题的编码，以将任何多项式问题简化为线性问题。这不是真的。对于某些算法，操作数量的增长速度快于其输入的字符串编码长度。例如，没有将两个m×m矩阵与θ(m^2)次运算相乘的算法。这里，输入的大小增长为m^2，然而Ran Raz证明了运算数的增长速度至少与m^2logm一样快。如果n在O(m^2)中，则m^2logm在O(Nlogn)中，并且最著名的算法复杂度增长为O(m^(2+c))=O(n^(1+c/2))，其中对于Coppersmith-Winograd算法的版本，c至少是0.372，对于普通迭代算法，c=1。
这篇关于分析矩阵的嵌套for循环的时间复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
