我需要转置一个由字符数组表示的方阵。是否有一种低于o(n^2)复杂度的方法来执行它？无论如何，最高效的缓存方式是什么？
3个回答
5
不，你不能在少于O(n^2)的时间内完成它，原因是你至少需要触碰矩阵中的每个元素一次（已经是n*n了）。因此你做不得更好。
最好的方法是使用O(1)的额外内存（而不是时间），进行原地矩阵转置（这在维基百科中有很好的概述）。
请注意，你并不总是需要计算转置矩阵。对于许多应用程序，你只需交换坐标（如果需要A [i] [j] - 只需返回A [j] [i] -th元素）。
最好的方法是使用O(1)的额外内存（而不是时间），进行原地矩阵转置（这在维基百科中有很好的概述）。
请注意，你并不总是需要计算转置矩阵。对于许多应用程序，你只需交换坐标（如果需要A [i] [j] - 只需返回A [j] [i] -th元素）。
- Salvador Dali
3
你还可以在矩阵类中添加一个1位标志，将转置操作简化为对该标志进行异或操作O(1)。如果设置了转置标志，则所有矩阵元素访问运算符应该交换行索引和列索引。
- Anonymous
0
这将始终需要O(NM)的时间，因为您必须为每个元素计算相应的转置坐标：
// char matrix[N * M]
// char transpose[N * M]
for(int i = 0; i < N*M; i++)
transpose[i] = matrix[ (M * (i % N)) + (i / N) ];
如果您正在处理NxN矩阵，则计算转置需要O(n^2)的时间。如果您不需要存储转置，您可以在反转索引时迭代它，并有效地完成相同的操作而无需额外的内存。
- Joel
1
1时间复杂度不受数组维度（如何索引内存）的影响。 - Joel
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接