What's the transpose complexity Big O in Matlab?

18 ビュー (過去 30 日間)
Mohamed Mohsen
Mohamed Mohsen 2019 年 12 月 9 日
編集済み: 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.

採用された回答

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 件のコメント
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 日
編集済み: Mohamed Mohsen 2019 年 12 月 9 日
Okay, I got it :))
Thanks a lot.

サインインしてコメントする。

その他の回答 (0 件)

カテゴリ

Help Center および File ExchangeMatrix Indexing についてさらに検索

製品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by