How to calculate growth rate using Big O?
I am just starting to learn about Big O notation and had a question about how to calculate the growth rate of an algorithm. Suppose I had an algorithm with O(√n log n) time complexity, and for n = 10 my algorithm takes 2 seconds. If I want to know how long it would take with n = 100, do I set up a ratio where 2/x = (√10 log 10)/(√100 log 100) and then solve for x? Or can I just say that my input is 10 times larger, so it will take 2*(√10 log 10) seconds?
The first method is right. Big O doesn't care about constant multiples so you can determine the constant by solving for it with algebra.
c*(√10*log(10)) = 2
c = 2/(√10*log(10))
√100*log(100) * 2/(√10*log(10)) = x
However, keep in mind that big O also doesn't care about 'smaller' terms and so those constant overheads and other smaller-scaling factors will only make this calculation asymptotically accurate. For example, an algorithm governed by the following equation:
(√n log n + 1/n) = t
is still O(√n log n) and this will make your calculations less accurate for small values of n.
链接地址: http://www.djcxy.com/p/40048.html上一篇: 为什么堆排序的空间复杂度为O（1）？
下一篇: 如何使用Big O来计算增长率？