I need to transpose a square matrix that's represented by a char array. Is there a way to perform it in less than o(n^2) complexity? Anyway, what's the most cache-efficient way to do it?
-
You should specify what n means. Salvador Dali's answer interprets n to be the number of rows. Another reasonable interpretation would be the number of elements. One is possible, one is not.Praxeolitic– Praxeolitic2015-01-18 22:15:31 +00:00Commented Jan 18, 2015 at 22:15
Add a comment
|
3 Answers
No, you can not make it in less then O(n^2) and the reason behind this is that you need to at least touch each element in the matrix once (which is already (n*n). Therefore you can not do better.
The best you can do is to use O(1) additional memory (not time) doing in-place matrix transpose (which is nicely outlined in wikipedia).
Note that you do not always need to calculate transpose matrix. For a lot of applications you can just swap coordinates (if you need A[i][j] - just return A[j][i] -th element)
Comments
You can also add a 1 bit flag to your matrix class, turning transpose operation to simply xor on this flag O(1). All matrix element accessing operators should then swap row index with column index if transpose flag is set.
Comments
This will always take O(NM), since you have to calculate the corresponding transpose coordinate for every element:
// char matrix[N * M]
// char transpose[N * M]
for(int i = 0; i < N*M; i++)
transpose[i] = matrix[ (M * (i % N)) + (i / N) ];
If you are doing this with NxN matrices, then it will take O(n^2) to calculate the transpose. If you don't need to store the transpose, you could just iterate over it while inverting your indexes and effectively do the same thing without additional memory.
1 Comment
Joel
The time complexity is the same regardless of the array dimension (how you index the memory).