Question on Big O notation scaling factor
I have 2 algorithms to do something (eg search a list) one has linear complexity and the other has log complexity (O(log n). If I am comparing operation on 100 and 1000 units, do I say the linear algorithm has scaling factor x10?
How do I express the log algo scaling factor? eg 100 items takes 2 seconds, 1000 items takes 3 seconds. The log of 1000 is 3, the log of 100 is 2. So what is the scale factor? x1.5?
I can see that the growth in time is logarithmic. Or do you just say the scaling factor is logarithmic? But what would you calculate if example was comparing 100 to 1000 items?
I would put it as "it scales in a linear/quadratic/cubic/logarithmic/exponential fashion", I wouldn't reference the exact scaling factor at all. The big O isn't about specific times, it is a way to put algorithms into certain classes, ie. linear class, logarithmic class etc.
The point isn't about making assumptions on the exact runtime (this is influenced by many details and depends entirely on the machine the algorithm is running on) but to be able to put it in relative terms, so you can say that an O(n²) algorithm will be slower than O(n), O(log n) at a glance.
Your question presupposes that "scaling factor" is meaningful for any order of complexity other than linear and this is simply not the case. But even for linear it's kind of meaningless. See, just because an algorithm is O(n) doesn't mean that an input of size 2x is going to take twice as "long" as an input of size x .
Your question also presupposes the common misconception that order of complexity is translatable into time. It is not. Order of complexity is useful for asymptotic analysis of algorithms, not for measuring time to completion give a particular input size.
In general, you can't compute a numeric scaling factor from just the Big O complexity because the Big O complexity omits the coefficients and constants that are critical to computing the scaling factor.
If algorithm A has an actual complexity of (1/1000) * n + 100 while algorithm B has an actual complexity of 100*log(n) + 1 , algorithm A is O(n) while algorithm B is O(log(n)). However, when you go from an n of 100 to an n of 1000, A goes from a cost of 100.1 to 101 while B goes from a cost of 201 to 301. Algorithm A's actual runtime increased by only 1% while algorithm B's actual runtime increased by 50%.
Big O notation is designed to tell you how something scales as n goes to infinity. When you're looking at an actual non-infinite range, it's entirely possible that the algorithm with a better Big O notation is slower and scales less efficiently than the algorithm with the worse Big O notation. For a sufficiently large n, the algorithm with the better Big O notation will eventually win. But there is no guarantee that the crossover point is actually within the realm of what is expected for any given purpose.
链接地址: http://www.djcxy.com/p/6812.html下一篇: 大O符号比例因子问题