MATLAB Answers

What's the transpose complexity Big O in Matlab?

5 ビュー (過去 30 日間)
Mohamed Mohsen
Mohamed Mohsen 2019 年 12 月 9 日
Edited: Mohamed Mohsen 2019 年 12 月 9 日
a = [1 2 3 4]
b = a' %what's the Big O complexity here for transposing the "a" 1D array.
a = [ [1 2 3 4] ; [5 6 7 8] ; [9 10 11 12]]
b = a' %what's the Big O complexity here for transposing the "a" 2D array.

  0 件のコメント

サインイン to comment.

採用された回答

Walter Roberson
Walter Roberson 2019 年 12 月 9 日
%what's the Big O complexity here for transposing the "a" 1D array.
O(1) -- that is, constant in the size of the array.
%what's the Big O complexity here for transposing the "a" 2D array
In theory, each element only needs to be touched once, so for an n x m matrix it would be O(n*m). (In practice, you need to worry about cache-line conflicts and cache sizes, so the most efficient algorithms in practice involve block algorithms and multiple CPUs, and calculating execution time for them gets more complex.)

  3 件のコメント

Mohamed Mohsen
Mohamed Mohsen 2019 年 12 月 9 日
Thanks for your quickly response,
So, your answer is that in case of 1D array it will be a constant with O(1) while in case of 2D array it will be O(n * m) and "m" is O(1) as previously descriped, therefore, the 2D array will become O(N)? is that what are you meaning here?
Thanks in advance.
Walter Roberson
Walter Roberson 2019 年 12 月 9 日
No, transposing a 2D array is not a matter of transposing a number of 1D arrays.
MATLAB stores vectors in increasing memory locations, and it keeps a header describing what the size is. For example for the 1 x 4 vector, it would store the information 2 (number of dimensions) and [1 4] (the dimensions), and it would store the data as well. The transpose of a vector involves the same elements in the same order, just with index relabled, (1,K) -> (K,1) . That can be implemented internally in MATLAB by just changing the header from 2, [1 4], to 2, [4 1] (same number of dimensions, but now 4 rows and 1 column.) It is a "reshape" operation, and in MATLAB, all reshape operations that do not move the relative locations in memory of values are implimented by creating a new size header instead of by moving anything in memory.
This strategy does not work for 2D arrays, as the relative locations of values has to change. For 2D or more arrays, to transpose, MATLAB has to make copies of values into new locations. Each value only has to be copied once, so the number of operations (other than for constructing the header) is the same as the number of values in the array.
Internally, the transpose operation on a 2D array for small arrays works like
output = zeros(size(Input,2), size(Input,1), class(Input));
for row = 1 : size(Input,1)
for col = 1 : size(Input,2)
output(col,row) = Input(row, col);
end
end
This is one read operation and one write operation for each input element, but big-O notation drops constant values (e.g., O(2*m*n) is simplified to O(m*n)
Mohamed Mohsen
Mohamed Mohsen 2019 年 12 月 9 日
Okay, I got it :))
Thanks a lot.

サインイン to comment.

More Answers (0)

サインイン してこの質問に回答します。


Translated by