How to properly measure computational complexity (run-time) in Matlab?
조회 수: 19 (최근 30일)
이전 댓글 표시
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?
댓글 수: 0
채택된 답변
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
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에서 Multirate Signal Processing에 대해 자세히 알아보기
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!