When choosing an algorithm, one often speaks of the asymptotic behavior of a particular solution to a problem. At the same time, one can come across statements that, supposedly, "this" algorithm works for O (n), and "over there" works for O (n · log (n)), so the first is definitely better. Or, since both methods work for O (n²), it means that they can be considered equivalent, and there is no big sense in discussing how one can be better than the other.
Personally, I can not agree with this opinion, at least when it comes to the programming context, so I decided to write this article and share some thoughts about possible nuances.
How do you like that?
- Do not forget that the operations that can be taken as O (1) are very simple (addition / subtraction), but they are very sophisticated (multi-storey formulas with complex functions). The operations of division, calculation of trigonometric and logarithmic functions, degrees (including roots), etc., especially with real numbers, are performed many times (and sometimes tens and hundreds of times slower) than the operations of addition, subtraction and multiplication, especially with integers by numbers. Thus, even O (1) in different algorithms can differ by orders of magnitude.
- Even if the complexity of operations is approximately the same and their number, at first glance, is approximately the same, the actual number of operations can vary significantly. For example, one algorithm runs along the entire array, the other - only along its part (which formally can be of any length, but in practice it is quite short, say, 1/10 of the length of the array). And if this also happens in a nested loop, then we get a real speed difference of 100 times. In addition, if you remember, constants are not taken into account when determining asymptotic complexity. Those. even if you wrap your algorithm in a cycle of 1 million iterations, then your “O” will not change, in fact the speed will drop by about 6 decimal orders. In practice, this, of course, can hardly be found, but there are plenty of algorithms in which passing through the same array several times (or there are several sorting operations, repeated nested loops, etc.). And, say, log (n) can mean both log2 (n) and log10 (n), the difference between them is about 3.32 times.
- Do not forget that in addition to speed, there are other important parameters, for example, the amount of memory used. Therefore, an algorithm working for O (n²) in some cases may be more preferable than an algorithm working for O (n) or O (n · log (n)), but using a significant amount of memory. The number of used memory elements can also be estimated using "O", and when assessing the complexity of the algorithm, it would be nice to write an estimate of memory usage alongside.
- Some of the algorithms may require preliminary preparation (and, again, memory), and some may not. A good example is a number simplicity test. It can be implemented in many ways, but we will consider and compare only 2 of them: the enumeration method (with complexity about O (sqrt (n)) of division operations) and with the help of the sieve of Eratosthenes or Atkin (the simplicity test is performed in O (1), but with preliminary preparing an array of order O (n · log (log (n))) or O (n / log (log (n))), respectively). The memory usage for the last algorithm can be optimized to at least 32 megabytes per 1 billion numbers (i.e., up to 1 byte per 30 numbers), and these values can not even be calculated every time the program is started, but cached, saved to disk. Which method to prefer is highly dependent on the particular use case, sometimes the Miller or Miller-Rabin test will be much more preferable. By the way, the simplicity test by enumeration is a good example of the fact that, depending on the initial value (n), the operation of the algorithm can be completed both at the first iterations (an even number or a multiple of 3, 5, 7), and a rather decent time (large prime), although formally its complexity, as I said, is O (sqrt (n)). Who cares, here “ here ” I gave simple methods of algorithmic acceleration of the simplicity test for only one enumeration method with implementation in C ++. And here “ here ” is an example of implementation of the Miller method in Python.
- Not only the algorithm itself is important, but also its implementation. The same algorithm can vary in speed hundreds of times simply because of the choice of different programming languages. The algorithm working, say, for O (n · log (n)) in C / C ++ can be significantly faster than the algorithm working for O (n) in Python, and for rather large n. In addition, there are many nuances of optimization in relation to the platform, data storage format, branching, implementation of the functions of standard libraries, etc. For example, if one algorithm optimizes the processor cache, use SIMD or multi-threaded operation, and the other does not, speed it can differ many times or even tens of times (despite the fact that everything else is about the same). Sequential work with an array located in memory as a single block, only because of the specifics of its organization, is faster than with a linked list (of course, if you do not consider inserting elements at the beginning or in the middle of the array / list). Caching data obtained in previous iterations (for example, in recursive algorithms) can increase the speed by many orders of magnitude. Etc. Someone will maliciously exclaim: “ Why is this all? We are discussing the algorithms themselves, and not their implementation! »Moreover, some algorithms make it easy to implement good optimization, while others complicate this process or even make some kind of optimization impossible. I do not call for premature optimization , but it is not for nothing that experts in high-performance systems say: “ When writing such systems, you have to think about system performance already at the stage of system architecture and design, even before at least one line of code is written ” (quote from articles from the link above).
If you think again, you can probably find other nuances, but in my opinion, this is already enough to think carefully: is “O” really the only important indicator of the speed of the algorithm?
Does the difference in speed 2, 5, 10 times mean nothing? Why do most people prefer fast SSDs over slow HDDs? Indeed, copying algorithms are the same everywhere (at least, personally, I haven’t seen more than O (n) yet :) :)
And imagine what the difference can be if you summarize all these nuances! Some algorithms with a larger “O” can work a little faster than others with a smaller “O” (at least for relatively small n ... by the way, should n always tend to infinity when evaluating the speed of an algorithm?)
Practical example
As a concrete example, I will give methods for sorting arrays. Many people think that the methods for sorting with a bubble and inserts are approximately the same in speed (since the complexity of both is O (n²)). However, I have repeatedly seen in practice that inserts sorting works almost an order of magnitude faster. To illustrate this, some time ago I did a small comparative test of several sorting methods (the test results on my computer are laid out below in the comments, the ratio of sorting speed by bubble and inserts is indicated in the line “ Bubble / insertion sort time ratio ”).
In addition, the quick sorting algorithm (which also has many implementations that significantly differ both in speed and in depth of recursion) can be modified in such a way that when a certain threshold is reached for the size of the arrays into which the original array is divided (for example, when elements become less than 16; and sometimes even when a certain recursion depth is reached), sorting switches to ... sorting by inserts (or further quick sorting stops, and sorting by inserts is already applied later to the whole not completely sorted array). It would seem, why is this done, because sorting by inserts is much slower than quick sorting? However, in practice, it turns out that sorting small arrays often happens a little faster precisely with “inserts” than with the “fast” method (“ quick / quick-insertion sort time ratio ” in the same test using the link above). Even in cases where the speed of both methods is approximately equal, the depth of the recursion decreases.
Output
What conclusion can be drawn from all this? Very simple: theory is good, but it must be supported by practice and knowledge of possible pitfalls. As the Japanese proverb says, knowledge is the reward for action.
Epilogue
I want to thank readers for their interest in the article, especially those who shared their thoughts in the comments. This is my first article on Habré, and for me it is valuable. It was after reading your posts that I decided to add this epilogue.
Of course, for infinitely large amounts of data (n → ∞), an asymptotic estimate of complexity will reflect the nature of the growth of the running time of the algorithms as well as possible. And no argument that “addition is faster than division” or that “constant does matter” will not be as important as this estimate. However, in real life, not everything is as perfect as in mathematics, and the amount of data is almost always limited (and often quite small values). And this means that it makes sense to take into account other parameters and evaluate the real effectiveness taking into account these parameters and possible ranges of n. But here it is important to take a sober view of the situation: will "tomorrow" grow n by an order of magnitude, for example, in connection with technological growth or business growth? Maybe it really makes sense to use an algorithm that now works 1.5 times slower, but in a month it will be 2 times faster, and in a year - 5? Or even make 2 algorithms and dynamically choose between them depending on the amount of input data! On this occasion, I recalled the story of the disaster on Ariane 5 .
It is unlikely to be a discovery that any business should be approached wisely. Asymptotics was invented by smart people, and it is important. It will not be very reasonable to measure the speed without taking into account the asymptotic behavior. But in order to "go far", it is better to have two wheels, and not one. And even better - four. It is necessary to consider several parameters at once. And remember the priorities. Somewhere the most important will be the speed of the algorithm, somewhere the amount of memory used, somewhere it will be generally insignificant (due to small values), and it is much more important to write a function quickly. Etc.
Key ideas of the article:
- If speed is important to you, then when choosing an algorithm with the same asymptotics (speed and memory size), pay attention to other characteristics that can significantly affect speed (varying by several times or even orders of magnitude) and conduct tests. In some cases, fairly similar algorithms with the same complexity and similar operations, as in my example about sorting with a bubble and inserts, can differ significantly in speed (by the way, here is a link to another test of sorting algorithms , not mine).
- Small differences in the estimation of asymptotic complexity may overlap with other nuances (including those described above). For example, the logarithm can often be taken as a constant (since, for example, log2 (1'048'576) = 20, and log2 (1'073'741'824) = 30), so in the case of O (n) and O (n · log (n)) it makes sense to compare the real efficiency of the algorithms even for significant n. If the estimate is significant: O (n) and O (n²), then the first algorithm, of course, will almost always be faster already with a rather small amount of input data.