Algorithm construction

"Learning about new algorithms and learning how to use them is an important part of programmer education."
Howard johnston

"It is necessary to compose a law or a table according to which numbers would grow at inexplicable non-periodical intervals."
Daniel harms

We paid so much attention to the actual ability to evaluate the temporal efficiency of the algorithm, but so far we have not even tried to figure out how much this is needed in practice.

In fact, the computational process, according to the designed algorithm, should be performed on a modern computer, which, it seems to us, works “fairly quickly”. Would not the saving of resources, which the algorithmist so diligently achieves, is so small that it represents only a purely theoretical interest? Or, as they say in such cases, is the game worth the candle?

Let's try to figure it out using some numbers. Suppose, for definiteness, that we have a processor that can dozens of millions - 10 ⁷ - microinstructions per second ( mips ), and rejoice in a reader who already has a computer with such speed on the table. We also agree that the algorithm we have designed requires, on average, ten mips for each step. This is not much, if the step of the algorithm includes, say, calculating the memory address where the array element is located, fetching it and some further processing. Obviously, under such conditions only one second of computer time will be enough for a whole million - 10 ⁶ - algorithmic steps of the computational process!

"What are these algorithms where such speed may not be enough?" - the reader will ask. "Yes, many such algorithms!" - we will respond to the skeptic. And we mention, to begin with, the previously cited example of selecting triangles, the initial “raw material” for which is extracted from a set of segments. In fact, the effectiveness of the promising, “frontal” solution is estimated as O (n ³ ) , and, therefore, a set of thousands of segments ( 10 ³ ) will be processed over a quarter of an hour. So long to expect a result, sitting at the computer screen, - the lesson fascinating.

We will not argue that the proposed option, which requires O (n ³ ) steps, is the only possible one. On the contrary, the reader should reflect on how to manage resources more economically, and thus step on the path of designing efficient algorithms. But after all, this was required to prove: the algorithm that is already at our disposal provokes us to search for a better mechanism. Moreover, it is worth looking for the best solution if the time complexity of the finished algorithm is estimated as O (n ⁴ ) or O (n ⁵ ) . And do not say that such tasks do not happen - you will be mistaken.

However, you may be surprised that computational processes with the complexity O (n ³ ) , O (n ⁴ ), and even O (n ⁵ ) are not necessarily the products of bad algorithms. On the contrary, such tasks are not unique, although it is still too early to proceed to their formulation. We can only say that often more efficient algorithms are either not designed in principle, or simply have not yet been invented. We note their common property: they all belong to the class of so-called algorithms with polynomial time complexity - O (n ^k ) , where k is a constant, and, naturally, does not change with an increase in the number of elements n .

How are they solved, if it is necessary, for problems of class O (n ⁴ ) or O (n ⁵ ) for "large" n ? Well, firstly, we should not forget that we consider processes based on the sequential execution of instructions, and there is such an alternative as parallel computing. In addition, the ill-fated "quarter of an hour of waiting" is critical for the user working directly at the computer, but completely indifferent to him if the computing process takes place in the background of his "personal computer" or, especially, in batch mode of a large computing machine .

Much worse is the case with algorithms whose complexity is O (2 ⁿ ) , O (n!) , O (n ⁿ ) and more. In this list, each successive function "overlaps", for sufficiently large n , the previous functions of the same series. Or, as they say, majorizes them. Moreover, each of them majorizes polynomial complexity. Such algorithms are usually characterized as having an exponential complexity .

Let's look at an example.

As you can see, it is necessary to apply algorithms with computational complexity O (n!) Very carefully if we want to wait for the final result. What to do?

We note, for reference, that it is impossible to speed up the search in the above example, except to change the formulation of the problem. In our case, say, a more specific formulation of the problem, including the criterion for selecting suitable options, can lead to the discarding of whole "families" of pupils' seating options.

Suppose that in a class of 15 people, forming the next placement of them in the party, we fixed the choice of 5 certain students for places 1 through 5. Therefore, the remaining 10 places are the remaining 10 students, which corresponds to 10! choices. If the selection criterion used in the task allows fixing the unprofitability of the initial selection of the “first five”, then the whole family of 10! there is no point in sorting out the corresponding seating arrangements.

On this idea, in various variations, the reduction of brute force is based in many practical tasks. The mechanism itself is called the branch and bound method .

Incidentally, if the indication of the pairwise inequality of segments in the input set is removed from the conditions of the problem of counting the number of triangles, then the indicated method is quite applicable. Thus, the primary choice of two identical segments makes it senseless to go through all the other applicants for the third position.

Another approach to constructing an algorithm is to reduce the solution of the original, complex problem to the alternate solution of simpler subtasks . In this case, we proceed from two assumptions. First, the cumulative complexity of solving subtasks is noticeably less than for the general task. Secondly, the partial solutions of subtasks can be combined into a common solution. This mechanism is called either the method of particular goals , or the method of decomposition of the problem and the composition of solutions .

Here is an example of a situation where familiarity with the method of private goals was useful to the author. So, a few days before writing this piece of text, he had the problem of an urgent "move" - ​​from one room of the apartment to another - in connection with the repair. Since we did not want to stop the "production process", we had to transfer the workplace, that is, the writing desk, computer, and so on. Here are the subtasks: to separate the component parts of the computer, transfer them to the places of new deployment, and then assemble them. Each of the subtasks is solved autonomously, however, the sequence cannot be broken. If you are reading this text, it means that the method is justified. Of course, in the situation described, other equally unpleasant subtasks arose, but I don’t want to list them.

As you can see, for the application of the decomposition-composition method, the algorithmist must have solid experience, since, in fact, we are talking about reducing the original problem to such subtasks, the methods for solving which are already familiar to him.

Note that the methods based on the application of both of these approaches are related to the so-called exact algorithms that guarantee the obtaining of the desired solution. Unfortunately, these mechanisms cannot be called universal, if only because there are many types of tasks that have exponential complexity, which does not allow them to be “completed” to the end in a reasonable time.

In such cases, the only practical solution is to obtain an inaccurate solution. But do not think that the loss necessarily turn out to be significant. A simple analogy with approximate calculations, to which we resort, bringing up to “number” the solution of some problems familiar to the reader, in particular, planimetry or point dynamics, should reassure us.

Indeed, no one has yet managed to accurately calculate the value of the number π, because of the impossibility. However, it is possible to do this with predetermined accuracy, for which, by the way, there are quite a few different algorithms, and, most importantly, in all cases the computational process is finite. One of them is described in the first of the proposed exercises for the reader.

The algorithms described in the above exercises belong to the class of approximate . Their common feature is the possibility of obtaining such a solution, albeit an inaccurate one, that would be "as much as possible" different from the true one. For practical purposes, as already mentioned, this may be enough.

Paying attention to the possibilities of using exact and approximate algorithms, we are obliged, at least concisely, to touch on heuristic algorithms.

These include methods that allow us to find some solution that is obviously inaccurate, but suits us. However, in contrast to the approximate methods, it is no longer possible to judge the degree of "similarity" of the result to the true solution: neither the relative nor the absolute discrepancy can be assessed. Moreover, the heuristic algorithm is not at all obliged to use an iterative approach, and then the concept of approximation loses its meaning. The essence of the mechanism is that for the "too" difficult task, some of the requirements appearing in its original formulation are simply ignored. It can be said that the use of a heuristic algorithm is either based on some “knowledge” of what should happen, or is justified by intuition (however, where does the intuition itself come from without accumulated experience). In particular, this is manifested in the screening of "unimportant" conditions from the statement of the problem. The decision that can be obtained with such a "truncated" setting is taken as appropriate.

In search of illustration, let us again turn to “illegal” analogies beyond the framework of finite mathematics.

So, we do not doubt (which is already a heuristic) in the existence of finite limits to the physical capabilities of homo sapiens. For example, it is difficult to find a person who can punch through the wall of a bank safe. But, without conducting sufficient research, the reliability of deposits is guaranteed to be excessive.

Or: how high can an athlete jump up without resorting to special adaptations? As an approximate value, it seems reasonable to accept the current world achievement. Its excess by the next athlete gives a new iteration, reducing the absolute discrepancy with a certain "exact", but almost unattainable result. In this sense, it seems, we are dealing with an approximate algorithm. On the other hand, a change in the sports technique of performing a jump can significantly move the bar of higher achievements, as happened during the transition from the flip style to the fosbury-flop. The American Fosbury did not use his “flop”, and we could well remain in ignorance, taking the local extremum of the old style, which is approaching over the years, as an absolute extremum .