Big O Complexity for Matlab code - Sum of Matrix Operation
41 次查看(过去 30 天)
显示 更早的评论
Hello,
This is my first time really programming with MATLAB, and I'm trying to analyze the complexity. The challenge I have is how to think of the sum of matrix operation: e.g., say A is of (nxm), and I want to do sum(A), which returns an answer of (1xm). In this case, should I interpret it as O(m) for going through the columns? Or...?
I guess I'm having trouble how to interpret matrix operations -- is it similar to having a "loop" in java/c terms?
Thank you in advance for your help!
Catherine
0 个评论
采纳的回答
Walter Roberson
2014-2-2
Usually big-O notation is used with respect to one variable, with the others held fixed.
For a fixed m, sum(A) with A being n x m, is equivalent to doing m summations of length n. Each length n summations requires O(n) operations, so you would have m * O(n) . But multiplicative constants are ignored for big-O notation, so you would just say O(n)
If m varies according to n, then you have a different situation and you need to know the relationship. For example for sum(A) where A is n x n, that would give you n * O(n) which is O(n^2)
3 个评论
Walter Roberson
2014-2-2
When you have n^2 elements and you have to "touch" them all at least once, you cannot do it without at least n^2 operations.
更多回答(2 个)
Jan
2014-2-2
编辑:Jan
2014-2-2
The big-O notation is meaningful in coding theory. In practize analysing the computational complexity must consider the physical machine:
- Matlab's sum uses multi-threading above a certain limit of data - it was 89000 elements in some Matlab versions. Therefore the computing time for summing 88999 and 89000 elements can vary by up to the number of built-in cores. Unfortunately for single-thread machines, the trial to start mutliple threads wastes a lot of processing time (this might be cleaned in the newest Matlab versions).
- When an algorithm is multi-threaded, it depends on the details of the implementation, if the creation of the output can cause an invalidation of the cache-line: The RAM is copied in chunks of e.g. 64 bytes to the caches. When the different cores write to the same chunk of data, caring for the consistency of the output data requires a lot of time, such that the total processing speed can be degraded to a single-threaded version.
- The calculations are much faster, when the data match into the processor's data cache, because accessing the RAM is slow.
- Above a certain limit, data are stored in the virtual memory and swapped to the hard-disk. This is roughly a factor of 1000 slower than the RAM.
- The time for reserving memory for the result depends on the availability of free and zeroed memory. This detail cannot be controlled from the Matlab level, but depends on the operating system.
- Other applications should not occupy processor power, e.g. virus-scanners.
- Modern processors can vary their speed widely, e.g. by thermal throtteling or "turbo boost" (this actually means, that the processor runs slower, when all cores are under load). Therefore the processing speed depends e.g. on the cooling capabilities also.
In consequence the O-value of the algorithm does not have a strong correlation to the processing time, except if the problem is specified exactly: data size, cache sizes, enough free RAM, number of involved cores, processor type and temperature.
Nevertheless, Matlab's sum cannot do any magic and the underlying code is based on simple C-loops or perhaps some improved assembler code. Most matrix operations are performed by the BLAS library.
Amit
2014-2-2
编辑:Amit
2014-2-2
Matlab sum without specification of dimension, for a matrix, will be for the column.
However for a vector, either row or column, will be for the whole vector.
The Matlab documentation is really good. You can check easily either online or just by typing on command window:
help function name, Like
help sum
This will be very useful when you are programming and get stuck!
3 个评论
Amit
2014-2-2
This makes this question quite interesting. I am not sure which order this algorithm will fall but you can possibly do a test for this where you record time based on the number of elements.
I did a quick test (I am not sure how accurate that is) but it seems that it O(nm)
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Logical 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!