use*_*785 3 arrays algorithm transpose matrix
我需要转置由字符数组表示的方阵。有没有办法以低于 o(n^2) 的复杂度来执行它？无论如何，最高效的缓存方法是什么？
Sal*_*ali 5
不，你不能用更少的时间做到这一点O(n^2)，其背后的原因是你需要至少接触矩阵中的每个元素一次（已经是（n*n）了。因此你不能做得更好。
O(n^2)
您能做的最好的事情就是使用O(1)额外的内存（而不是时间）进行就地矩阵转置（维基百科对此有很好的概述）。
O(1)
请注意，您并不总是需要计算转置矩阵。对于很多应用程序，您只需交换坐标（如果需要A[i][j]- 只需返回A[j][i]第一个元素）
A[i][j]
A[j][i]
归档时间：
10 年，10 月 前
查看次数：
8374 次
最近记录：