What's the transpose complexity Big O in Matlab?

Question

Mohamed Mohsen 2019-12-9

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/495668-what-s-the-transpose-complexity-big-o-in-matlab

编辑： Mohamed Mohsen 2019-12-9

采纳的回答： Walter Roberson

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 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Walter Roberson 2019-12-9

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/495668-what-s-the-transpose-complexity-big-o-in-matlab#answer_405534

%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 个评论
显示 1更早的评论隐藏 1更早的评论

Walter Roberson 2019-12-9

在 MATLAB Online 中打开

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 2019-12-9