我需要转置一个由 char 数组表示的方阵。 有没有办法以低于 o(n^2) 的复杂度来执行它？ 无论如何，缓存效率最高的方法是什么？
最佳答案
不，你不能在 O(n^2) 内完成，这背后的原因是你需要至少触摸矩阵中的每个元素一次(这已经是 ( n*n). 因此你不能做得更好。
您能做的最好的事情是使用 O(1) 额外的内存(而不是时间)进行就地矩阵转置(在 wikipedia 中有很好的概述)。
请注意，您并不总是需要计算转置矩阵。对于很多应用程序，您可以只交换坐标(如果您需要 A[i][j] - 只需返回 A[j][i] -th 元素)
关于arrays - 高效的矩阵转置算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28014994/