How to properly measure computational complexity (run-time) in Matlab?

15 次查看（过去 30 天）
John
John 2013-3-8
Basically, I am implementing an algorithm that has the same computational complexity as the FFT function in Matlab? The complexity is O(n log n). The algorithm I am implementing also has the same complexity. I am using wavelet transforms to compute FFT which produces the exact same results as the regular FFT function.
However, when I use tic and toc to measure the speeds, my algorithm takes longer than the classic FFT approach. It's spending a lot of time in the wavelet transform function that I'm using from the Wavelet toolbox.
Any suggestions? How do I really measure/judge computational complexity?

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

采纳的回答

Walter Roberson
Walter Roberson 2013-3-8
In order to get an experimental feel for computational complexity, you need to run the code with several different sizes of problems, and model how the time increases as the size of the problem increases.
Keep in mind that computational complexity is insensitive to constant multipliers or constant additions. Something that takes (say) always 100000 times longer, would be considered the same complexity.
  2 个评论
John
John 2013-3-8
If I run one algorithm that grows O(N) with the different sizes and then I run another algorithm that grows O(N^2), the O(N) algorithm is better? However, what if O(N) takes longer to run than O(N^2)? If I understand you correctly, the O(N) is still better in terms of complexity?
Walter Roberson
Walter Roberson 2013-3-8
Complexity represents the limit of efficiency as the problem size gets larger. So your O(N) code might take 10000*N and so might be much slower for small values than O(N^2) code that takes 3/2 * N^2 (for example), but past N=15000 or so the 10000*N would be faster than the 3/2 * N^2.

请先登录，再进行评论。

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Fourier Analysis and Filtering 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by