Asymptotic analysis of algorithms
Before proceeding to the review of the asymptotic analysis of algorithms, I want to say a few words about when the written here will be relevant. Probably, many programmers, reading these lines, think to themselves that they have done very well all their life without all this, and of course there is some truth in these words, but if there is a question of proving effectiveness or, on the contrary, the inefficiency of some code, then without formal analysis is not enough, and in serious projects, such a need arises regularly.
In this article I will try to explain in a simple and understandable language, what is the complexity of algorithms and asymptotic analysis, as well as the possibilities of using this tool for writing your own effective code. Of course, in one short post it is not possible to cover completely such an extensive topic even at the superficial level, which I tried to adhere to, so if you like what is written here, I will be happy to continue publishing on this topic.
So let's get started.
In many papers describing certain algorithms, it is often possible to come across type designations:
O (g (n)), Ω (g (n)), (g (n)).
Let's figure out what it is, but first I will list the main classes of complexity used in the analysis:
f (n) = O (1) constant
f (n) = O (log (n)) logarithmic growth
f (n) = O (n) linear growth
f (n) = O (n * log (n)) quasilinear growth
f (n) = O (n ^ m) polynomial growth
f (n) = O (2 ^ n) exponential growth
')
If earlier you did not meet with similar designations, do not worry, after reading this article, everything will become much clearer.
And we begin with the symbol O.
O (g (n))
First, I will give a formal definition:
(1.1) A notation of the form f (n) = O (g (n)) means that the function f (n) increases more slowly than the function g (n) with c = c1 and n = N, where c1 and N can be arbitrarily large numbers, i.e. When c = c1 and n> = N, c * g (n)> = f (n).
Thus, O - means the upper limit of the complexity of the algorithm.
Let's now try to put this knowledge into practice.
Take the sorting problem known to any programmer. Suppose we need to sort an array of numbers of 10,000,000 elements. We agree to consider the worst case in which to perform the algorithm will need the largest number of iterations. Without hesitation, we decide to use bubble sorting as the simplest in terms of implementation.
Bubble sorting allows you to sort an array of any dimension without additional memory allocations. It seems that everything is fine and we begin to write code with a clear conscience (for examples, the Python language will be used here and later).
I intend not to introduce a check for at least one exchange (which by the way does not affect O - the complexity of the algorithm), in order to simplify the understanding of the essence.
Looking at the code, we immediately draw attention to the nested loop. What does this tell us? I hope that the reader is familiar with the basics of programming in any language (except functional, in which cycles are absent as such, and repetitions are implemented by recursion) and I have a vivid idea of ​​what nested loops are and how they work. In this example, the outer loop runs exactly n = 10,000,000 (since our array consists of 10,000,000 elements) and the inner loop runs the same number of times, this obviously means that the total number of iterations will be of the order of n ^ 2 Those. The number of iterations depends on the dimension of the input data as a function of n ^ 2. Now, knowing the complexity of the algorithm, we can check how well it will work in our case. Substituting the numbers in the formula n ^ 2, we get the answer 10 000 000 * 10 000 000 = 10 000 000 000 0000 iterations.
Hmmm, impressive ... In the cycle we have 3 commands, suppose that each of them takes 5 units of time (c1 = 5), then the total amount of time spent on sorting our array will be 5 * f (n ^ 2) (blue curve in fig.1).
fig.1.
the green curve corresponds to the graph f-ii x ^ 2 when c = 1, blue c = 5, red c = 7
Hereinafter, on all graphs, the abscissa axis will correspond to the dimension of the input data, and the ordinate axis will count the number of iterations necessary for the execution of the algorithm.
We are only interested in the part of the coordinate plane that corresponds to x values ​​greater than 0, since any array, by definition, cannot have a negative size, therefore, for convenience, we remove the left parts of the graphs of f-th, limiting it only to the first quarter of the coordinate plane.
fig.2.
the green curve corresponds to the graph f-ii x ^ 2 when c = 1, blue c = 5, red c = 7
Take c2 = 7. We see that the new f-iy grows faster than the previous one (the red curve in Figure 2). From the definition of (1.1), we conclude that when c2 = 7 and n> = 0, g (n) = 7 * n ^ 2 is always greater than or equal to ffi and f (n) = 5 * n ^ 2, therefore our The program has complexity O (n ^ 2).
Who has not fully understood this explanation, look at the graphs of f-th and notice that the f-ia marked in red, with n> = 0, always has a greater value on y than the function of f-ia marked in blue.
Now we will think, is it good or bad in our case and can we make the algorithm work more efficiently?
As can be understood from the graphs shown in Fig. 2, the quadratic function grows quite quickly and with a large amount of input data, sorting the array in this way can take quite a long time, and the increase in processor power will only affect the coefficient c1, but the algorithm itself will still belong to the class algorithms with a polynomial growth function O (n ^ 2) (here we again use the definition (1.1) and select such c2 and N for which c2 * n ^ 2 will increase faster than our function c1 * n ^ 2 starting from some n> = N) and if in the near future they invent a processor, If our array will be sorted in just a couple of seconds, then with a slightly larger amount of input data, this performance increase will be completely leveled by the number of necessary calculations.
The same temporary tool is the decision to implement an algorithm in a low-level language (for example, an assembler), since all we can do is, again, only slightly reduce the coefficient c1 while still remaining in the O (n ^ 2) complexity class .
And what will happen if instead of a single-core processor, we will use a 4-core processor? In fact, the result will not change much.
We divide our array into 4 parts and assign each part to a separate core. What will we get? Sorting each part will require exactly O ((n / 4) ^ 2). Since all parts are sorted simultaneously, this result will be the final sorting time of four subarrays, of dimension n / 4. We will erect the resulting expression in a square, thus obtaining the complexity equal to O (1/16 * n ^ 2 + n), where n is the iteration necessary for sorting the final array obtained by concatenation of four ready-made subarrays.
Since the analysis is asymptotic, then for sufficiently large n, the f-Ia n ^ 2 will make a much larger contribution to the final result than n and therefore we can safely neglect it, as the most slowly increasing term, by negligibility 1 / 16 (see (1.1)), which ultimately gives us all O (n ^ 2) too.
We come to the unflagging conclusion that an increase in the number of processors, as well as an increase in their frequency, does not give a significant increase with this sorting algorithm.
What can be done in this situation to radically speed up the sorting? It is necessary that in the worst case the complexity of the algorithm is less than O (n ^ 2). After thinking a bit, we decide that it would not be bad to come up with an algorithm whose complexity does not exceed O (n), i.e. is linear. Obviously, in the case of O (n), the speed of the program will increase N times, because instead of N ^ 2 iterations, we will only need to do N. The predicted speed increase is clearly visible in Fig.3.
The gray line indicates the linear complexity, and the three curves show the complexity of n ^ 2 with different coefficients c.
But it turns out that sorting with complexity O (n) in the general case is simply not possible ( doc )! So what kind of complexity can we expect at best? It is equal to O (n * log (n)), which is the theoretically proven minimum upper limit for any sorting algorithm based on comparing elements. This is certainly not something we expected to receive, but still it is not O (n ^ 2). It remains to find a sorting algorithm that meets our requirements.
Having rummaged on the Internet, we see that it is satisfied with "pyramidal sorting". I will not go into the details of the algorithm, anyone can read about it independently on the wiki , I will only say that its complexity belongs to the class O (n * log (n)) (that is, the maximum possible performance for sorting), but it is rather difficult to implement.
Let's look at the graphs below and compare the speed of increasing the number of calculations for the two considered sorting algorithms.
Fig.4.
The purple curve shows an algorithm with complexity n * log (n). It can be seen that on large n, pyramidal sorting greatly benefits the bubble sorting at any of the three coefficients we tested, but still inferior to the hypothetical sorting of linear complexity (gray line on the graph).
In any case, even on a slow computer, it will work much faster than a bubble on a fast one.
It remains an open question whether it is always advisable to prefer pyramidal sorting to bubble sorting?
fig.5.
As can be seen in Fig. 5, with small n, the differences between the two algorithms are quite small and the benefit from using pyramidal sorting is quite insignificant, and considering that the “bubble” is realized literally 5-6 lines of code, then for small n, it really is more preferable in terms of mental and time costs for implementation :)
In conclusion, in order to more clearly demonstrate the difference between the classes of complexity, I will give the following example:
Suppose we have a computer 45 years old. In my head, thoughts of large cabinets, which occupy a rather large area, immediately come up. Suppose that each command on such a machine runs in about 10 milliseconds. With such a speed of computations, having an algorithm of complexity O (n ^ 2), it will take a very long time to solve the posed problem and will have to abandon it as impossible for an admissible time, if we take an algorithm with complexity O (n * log (n)) then the situation will change radically and it will take no more than a month to complete the calculation.
Calculate how much it takes to sort the array in both cases.
super-non-optimal algorithm (it happens sometimes, but rarely):
O (2 ^ n) = oooooochen slowly, the universe will die before we finish our calculation ...
bubble:
O (n ^ 2) = 277777778 hours (classic “bubble”)
pyramidal sorting:
O (n * log (n)) = 647 hours (which is what we can actually achieve by applying pyramidal sorting)
fantastically efficient algorithm:
O (n) = 2.7 hours (our hypothetical algorithm that sorts in linear time)
and finally:
O (log (n)) = oooooochen fast, it's a pity that there are no miracles ...
The last two cases (although they are not possible in reality when sorting data) I cited only in order for the reader to feel the huge difference between the algorithms of different complexity classes.
Lastly, I want to note that the letter O usually denotes the minimum of the complexity classes to which this algorithm corresponds. For example, I could say that the complexity of sorting a bubble is O (2 ^ n) and theoretically this would be an absolutely correct statement, but in practice such an assessment would be meaningless.
In this article I will try to explain in a simple and understandable language, what is the complexity of algorithms and asymptotic analysis, as well as the possibilities of using this tool for writing your own effective code. Of course, in one short post it is not possible to cover completely such an extensive topic even at the superficial level, which I tried to adhere to, so if you like what is written here, I will be happy to continue publishing on this topic.
So let's get started.
In many papers describing certain algorithms, it is often possible to come across type designations:
O (g (n)), Ω (g (n)), (g (n)).
Let's figure out what it is, but first I will list the main classes of complexity used in the analysis:
f (n) = O (1) constant
f (n) = O (log (n)) logarithmic growth
f (n) = O (n) linear growth
f (n) = O (n * log (n)) quasilinear growth
f (n) = O (n ^ m) polynomial growth
f (n) = O (2 ^ n) exponential growth
')
If earlier you did not meet with similar designations, do not worry, after reading this article, everything will become much clearer.
And we begin with the symbol O.
O (g (n))
First, I will give a formal definition:
(1.1) A notation of the form f (n) = O (g (n)) means that the function f (n) increases more slowly than the function g (n) with c = c1 and n = N, where c1 and N can be arbitrarily large numbers, i.e. When c = c1 and n> = N, c * g (n)> = f (n).
Thus, O - means the upper limit of the complexity of the algorithm.
Let's now try to put this knowledge into practice.
Take the sorting problem known to any programmer. Suppose we need to sort an array of numbers of 10,000,000 elements. We agree to consider the worst case in which to perform the algorithm will need the largest number of iterations. Without hesitation, we decide to use bubble sorting as the simplest in terms of implementation.
Bubble sorting allows you to sort an array of any dimension without additional memory allocations. It seems that everything is fine and we begin to write code with a clear conscience (for examples, the Python language will be used here and later).
def bubble_sort(arr):
. . for j in xrange(0, N - 1):
. . . . for i in xrange(0, N - 1):
. . . . . . if(arr[i] > arr[i+1]):
. . . . . . . . tmp = arr[i]
. . . . . . . . arr[i] = arr[i+1]
. . . . . . . . arr[i+1] = tmp
I intend not to introduce a check for at least one exchange (which by the way does not affect O - the complexity of the algorithm), in order to simplify the understanding of the essence.
Looking at the code, we immediately draw attention to the nested loop. What does this tell us? I hope that the reader is familiar with the basics of programming in any language (except functional, in which cycles are absent as such, and repetitions are implemented by recursion) and I have a vivid idea of ​​what nested loops are and how they work. In this example, the outer loop runs exactly n = 10,000,000 (since our array consists of 10,000,000 elements) and the inner loop runs the same number of times, this obviously means that the total number of iterations will be of the order of n ^ 2 Those. The number of iterations depends on the dimension of the input data as a function of n ^ 2. Now, knowing the complexity of the algorithm, we can check how well it will work in our case. Substituting the numbers in the formula n ^ 2, we get the answer 10 000 000 * 10 000 000 = 10 000 000 000 0000 iterations.
Hmmm, impressive ... In the cycle we have 3 commands, suppose that each of them takes 5 units of time (c1 = 5), then the total amount of time spent on sorting our array will be 5 * f (n ^ 2) (blue curve in fig.1).
fig.1.
the green curve corresponds to the graph f-ii x ^ 2 when c = 1, blue c = 5, red c = 7
Hereinafter, on all graphs, the abscissa axis will correspond to the dimension of the input data, and the ordinate axis will count the number of iterations necessary for the execution of the algorithm.
We are only interested in the part of the coordinate plane that corresponds to x values ​​greater than 0, since any array, by definition, cannot have a negative size, therefore, for convenience, we remove the left parts of the graphs of f-th, limiting it only to the first quarter of the coordinate plane.
fig.2.
the green curve corresponds to the graph f-ii x ^ 2 when c = 1, blue c = 5, red c = 7
Take c2 = 7. We see that the new f-iy grows faster than the previous one (the red curve in Figure 2). From the definition of (1.1), we conclude that when c2 = 7 and n> = 0, g (n) = 7 * n ^ 2 is always greater than or equal to ffi and f (n) = 5 * n ^ 2, therefore our The program has complexity O (n ^ 2).
Who has not fully understood this explanation, look at the graphs of f-th and notice that the f-ia marked in red, with n> = 0, always has a greater value on y than the function of f-ia marked in blue.
Now we will think, is it good or bad in our case and can we make the algorithm work more efficiently?
As can be understood from the graphs shown in Fig. 2, the quadratic function grows quite quickly and with a large amount of input data, sorting the array in this way can take quite a long time, and the increase in processor power will only affect the coefficient c1, but the algorithm itself will still belong to the class algorithms with a polynomial growth function O (n ^ 2) (here we again use the definition (1.1) and select such c2 and N for which c2 * n ^ 2 will increase faster than our function c1 * n ^ 2 starting from some n> = N) and if in the near future they invent a processor, If our array will be sorted in just a couple of seconds, then with a slightly larger amount of input data, this performance increase will be completely leveled by the number of necessary calculations.
The same temporary tool is the decision to implement an algorithm in a low-level language (for example, an assembler), since all we can do is, again, only slightly reduce the coefficient c1 while still remaining in the O (n ^ 2) complexity class .
And what will happen if instead of a single-core processor, we will use a 4-core processor? In fact, the result will not change much.
We divide our array into 4 parts and assign each part to a separate core. What will we get? Sorting each part will require exactly O ((n / 4) ^ 2). Since all parts are sorted simultaneously, this result will be the final sorting time of four subarrays, of dimension n / 4. We will erect the resulting expression in a square, thus obtaining the complexity equal to O (1/16 * n ^ 2 + n), where n is the iteration necessary for sorting the final array obtained by concatenation of four ready-made subarrays.
Since the analysis is asymptotic, then for sufficiently large n, the f-Ia n ^ 2 will make a much larger contribution to the final result than n and therefore we can safely neglect it, as the most slowly increasing term, by negligibility 1 / 16 (see (1.1)), which ultimately gives us all O (n ^ 2) too.
We come to the unflagging conclusion that an increase in the number of processors, as well as an increase in their frequency, does not give a significant increase with this sorting algorithm.
What can be done in this situation to radically speed up the sorting? It is necessary that in the worst case the complexity of the algorithm is less than O (n ^ 2). After thinking a bit, we decide that it would not be bad to come up with an algorithm whose complexity does not exceed O (n), i.e. is linear. Obviously, in the case of O (n), the speed of the program will increase N times, because instead of N ^ 2 iterations, we will only need to do N. The predicted speed increase is clearly visible in Fig.3.
The gray line indicates the linear complexity, and the three curves show the complexity of n ^ 2 with different coefficients c.
But it turns out that sorting with complexity O (n) in the general case is simply not possible ( doc )! So what kind of complexity can we expect at best? It is equal to O (n * log (n)), which is the theoretically proven minimum upper limit for any sorting algorithm based on comparing elements. This is certainly not something we expected to receive, but still it is not O (n ^ 2). It remains to find a sorting algorithm that meets our requirements.
Having rummaged on the Internet, we see that it is satisfied with "pyramidal sorting". I will not go into the details of the algorithm, anyone can read about it independently on the wiki , I will only say that its complexity belongs to the class O (n * log (n)) (that is, the maximum possible performance for sorting), but it is rather difficult to implement.
Let's look at the graphs below and compare the speed of increasing the number of calculations for the two considered sorting algorithms.
Fig.4.
The purple curve shows an algorithm with complexity n * log (n). It can be seen that on large n, pyramidal sorting greatly benefits the bubble sorting at any of the three coefficients we tested, but still inferior to the hypothetical sorting of linear complexity (gray line on the graph).
In any case, even on a slow computer, it will work much faster than a bubble on a fast one.
It remains an open question whether it is always advisable to prefer pyramidal sorting to bubble sorting?
fig.5.
As can be seen in Fig. 5, with small n, the differences between the two algorithms are quite small and the benefit from using pyramidal sorting is quite insignificant, and considering that the “bubble” is realized literally 5-6 lines of code, then for small n, it really is more preferable in terms of mental and time costs for implementation :)
In conclusion, in order to more clearly demonstrate the difference between the classes of complexity, I will give the following example:
Suppose we have a computer 45 years old. In my head, thoughts of large cabinets, which occupy a rather large area, immediately come up. Suppose that each command on such a machine runs in about 10 milliseconds. With such a speed of computations, having an algorithm of complexity O (n ^ 2), it will take a very long time to solve the posed problem and will have to abandon it as impossible for an admissible time, if we take an algorithm with complexity O (n * log (n)) then the situation will change radically and it will take no more than a month to complete the calculation.
Calculate how much it takes to sort the array in both cases.
super-non-optimal algorithm (it happens sometimes, but rarely):
O (2 ^ n) = oooooochen slowly, the universe will die before we finish our calculation ...
bubble:
O (n ^ 2) = 277777778 hours (classic “bubble”)
pyramidal sorting:
O (n * log (n)) = 647 hours (which is what we can actually achieve by applying pyramidal sorting)
fantastically efficient algorithm:
O (n) = 2.7 hours (our hypothetical algorithm that sorts in linear time)
and finally:
O (log (n)) = oooooochen fast, it's a pity that there are no miracles ...
The last two cases (although they are not possible in reality when sorting data) I cited only in order for the reader to feel the huge difference between the algorithms of different complexity classes.
Lastly, I want to note that the letter O usually denotes the minimum of the complexity classes to which this algorithm corresponds. For example, I could say that the complexity of sorting a bubble is O (2 ^ n) and theoretically this would be an absolutely correct statement, but in practice such an assessment would be meaningless.
Source: https://habr.com/ru/post/78728/
All Articles