Evaluation of the effectiveness of the algorithm

“It’s amazing how many programmers have too expensive a way to figure out that their program cannot process the input data in less than a few days of computer time. It would be better to predict such cases with a pencil and paper.”
S. Goodman (S. Goodman), S. Hetdniemi (S. Hedetniemi)

"Less is more."
IN AND. Ulyanov (Lenin)

Above, we already talked about the need to analyze the constructed algorithm. Such an analysis should give a clear idea, firstly, about the capacitive and, secondly, about the time complexity of the process.

The first part is quite clear: we are talking about the size of the memory in which all the data involved in the computational process are to be placed. Naturally, these include input sets, intermediate and output information. Probably, not all the listed sets require simultaneous storage, - well, it means that it is possible to save. In some cases, however, the evaluation of capacitive complexity becomes less obvious: this is the case when using dynamic structures, but this is in another chapter.

But we will pay attention to the analysis of time complexity right now.

So, some problem has been posed, and an algorithm has been designed to solve it. It describes the computational process that ends in a finite number of action-steps. We have already said that the actual execution time of each individual step depends on the specific computing device. In other words, an integral participant in the computational process is not an algorithm! - is a performer . But in view of the intended performer, it is not a sin to evaluate his computational abilities in advance.

We can say that the algorithm should be clear to the performer. This means that any instruction of the algorithm must be included in the fixed set of instructions that the executor can implement. Let's say your pocket calculator is designed to perform several arithmetic operations, and a more powerful, programmable calculator is ready to run simple programs. Accordingly, the sets of built-in, elementary instructions of these devices differ. Moreover, any team that the second calculator is ready to perform still consists of a certain number of arithmetic and logical operations. Another thing is that we do not have to call them separately. Thus, either the algorithm explicitly prescribes to perform arithmetic-logical operations, and this level of programming is designed directly for the processor, or the "enlarged" instructions are used, and a special language is used to process them.

Thus, the client’s communication with an ATM provides for the participation of two executors of the algorithm, a person and an ATM, the first of whom access the second through a button interface. An experienced plastic card holder is familiar with the procedure, however, the second participant in the process does not take into account the client's competence, and therefore all necessary instructions are displayed alternately on the board. As you can see, the developers of the system that provides this dialogue brought the step-by-step specification of the algorithm to a certain level of "competence", breaking up the enlarged steps - "withdrawing cash" or "obtaining account information" - into smaller steps.

As we found out, the performer of our algorithm must "be able to" execute any instruction from among those that he perceives as elementary, and he will not execute any others. Actually, one of the differences between computer processors is the mismatch of their “personal” instruction sets.

But it would be absurd in the course offered to the reader to be guided by such an "intellectually limited" performer as an ordinary processor. On the contrary, the "abilities" of our implied performer must gradually develop. Therefore, as the distance from the initial pages increases , the level of detail will decrease, and the algorithms will be described in enlarged steps. So, an experienced chef is quite ready to fulfill the order to "cook roast beef" - remember, we faced him higher? - as an elementary instruction.

Suppose we were able to construct an algorithm for solving some problem. If so, what prevents to assume the existence of another algorithm, and another one? But if it is possible to construct a number of different algorithms for solving the same problem, then it seems reasonable to choose the “best” one. What is meant by this?

As a rule, we are talking about this solution, which, in comparison with competitors, needs the least time-consuming computational process. Of course, to give such an assessment is legitimate, only by referring to the same potential performer.

Further: the speed of implementation of the selected algorithm can significantly depend on the content of the input data set. For example, a fast "on average" mechanism is capable of failing in individual "bad" cases. And, if the task should probably be solved within a certain time of the processor, then in this case, we probably prefer the algorithm to be slower on average, but reliable in worse situations.

For examples again turn to the non-computer sphere. To drink a cup of coffee, it is necessary, in any case, to warm the water. The coffee maker or a powerful electric kettle is quite convenient and effective in this case. If electricity is brought to your house — and this is very likely — electricity, then the method of solving the problem that attracts one of these devices should be preferred in most cases. However, problems in the distribution panel, however rare they may appear, will deprive you of the expected pleasure (as well as the author, who refers here to his own sad experience, when the computer stops working at the same time as the coffee maker). So, gas stoves should not be canceled yet.

However, the most reliable, albeit the most time-consuming method remains: boil water on an open fire, spreading out a small fire. So that the reader does not forget to analyze the capacitive complexity of the algorithm, we note that the last example combines the properties of the worst efficiency both in time and in terms of resource requirements, taking into account irretrievable fuel consumption and low efficiency when the state of aggregation changes. However, even such an algorithm has the right to exist!

So, giving an estimate of the speed of the algorithm, one should consider the behavior of the computational process on average and, separately, in the extreme conditions for it, that is, in the worst case .

Modeling the "worst" cases is always associated with the content of the algorithm itself. You can offer only a small number of recipes for the selection and consideration of such situations. One of them is to test the behavior of the algorithm on input data that takes boundary values ​​from the allowed range. Another recipe: to test the algorithm on the largest possible in terms of input sets, which is important for the analysis of both temporal and capacitive efficiency.

Perhaps the ability to foresee "bad" situations - and they often arise when executing a ready-made program - is what distinguishes a qualified algorithmist from an ordinary coder. In connection with the expansion of the sphere of software production, even an independent specialization was formed - “program testers”.

A good training in the development of design skills for counterexamples to the algorithm being developed - and, of course, the program - will be the completion of tasks for the reader. They were built according to modern, - "olympiad", - canons. You will further be offered numerous examples, the solution of which is to write the appropriate programs. Finished programs will test the automated system, and test suites are designed so that the algorithm went through "fire and water." For this, the first tests check the operability “in general” from the point of view of obtaining the expected result, and then, if it corresponds to the formulation of the problem, “in particular” when the “bad”, in the sense we considered, sets are input to the program.

However, we will continue the discussion of how to evaluate the time efficiency of the algorithm itself. It is usually not associated with a specific computing facility, but is operated only with “steps”. In fact, it would be good to give such assessments that will be relevant even tomorrow, when the technical speed — hardware — is likely to increase.

Naturally, any step of the algorithm is implemented by a certain number of machine operations , or those very elementary instructions of the contractor, since you are unlikely to begin to design the algorithm in assembly language. Essentially, the analysis requires a degree of detailed elaboration of the algorithm so that, with respect to a single step, its further algorithmic development is not required. Here, only two situations are possible: either the fixed execution time of such a step is determined by a certain set of simple, without cycles, programming language commands, or it is a “consolidated” step, for which the corresponding analysis has already been carried out and the results are known.

Refer to the examples.

From the point of view of the number of machine operations, two different situations — the exchange of contents between variables occupying one machine word, or occupying two machine words — are unequal. But the estimation of algorithmic laboriousness does not take this into account.

For algorithms like the one just discussed, n steps to process n input values, it is obvious that the number of steps is a function of the number of elements being processed. We can assume that the number of steps is a function of the number of elements - f (n) .

In mathematics, there is a special mechanism for estimating the growth rate of a quantity of interest to the researcher: it is compared with some function whose behavior is well studied. It uses the notation g (n) = O (f (n)) , - it reads: O-large ), which we will refer to the discrete functions f (n) of natural n that we are interested in and to all functions g (n) that grow no faster than f (n) . The phrase “growing not faster” means that there is a pair of positive values ​​of M and n ₀ such that | g (n) | ≤M | f (n ₀ ) | for n≥n ₀ . They also say that the function g (n) is “of order f (n) for large n ”.

Such an O -notation gives us the upper estimate of the time complexity of the algorithm, its asymptotic complexity . Note that the use of the constants M and n ₀ , appearing in the definition, is actually associated with the “large” values ​​of the argument n and does little for its small values.

We indicate several important properties of O- operations:

• f (n) = O (f (n))

• c · O (f (n)) = O (f (n)) , where c is some constant

• O (f (n)) + O (f (n)) = O (f (n))

• O (O (f (n))) = O (f (n))

• O (f (n)) · O (g (n)) = O (f (n) · g (n))

In addition to the introduced terminology, another, so-called o- abstract (" o- small") is also useful. The designation o (f (n)) refers to functions that grow faster than f (n) .

Referring again to the example of the sum of an arithmetic progression, we can say that the asymptotic efficiency of the direct summation algorithm for n elements corresponds to linear complexity, since its speed, that is, the number of steps, according to property (a), is O (n) .

Generally speaking, if the algorithm is associated with processing n input elements, and there is no analytical expression — a formula — for quickly calculating the result, then achieving better efficiency than O (n) , if it is at all possible, should be viewed as a great success.

But more time-consuming algorithms, with the same amount of input set, exist, and it is not always possible to speed up the process.

In our examples we are talking about the upper estimates of the rate of increase in labor intensity. Usually, in the surface analysis of the algorithm, such an assessment is quite sufficient, especially when it comes to algorithms with the complexity of "different order", such as: O (n ² ) and O (n ³ ) . In the general case, if the efficiency of the algorithm is determined by the computational complexity of processing a polynomial of order k , it is often satisfied with the O (n ^k ) estimate, ignoring, according to property (b), the leading coefficient.

Such an approach, as a rule, justifies itself for the "large" n . Indeed, as follows from the definition of O- asymptotics, and the graphs are demonstrating this, no matter how small the coefficient is for the highest k -th member and, conversely, it is great, for any other m -three (m , the contribution of the first them in the behavior of the entire polynomial sooner or later becomes decisive.

However, a more thorough analysis is often of interest. In particular, when comparing the effectiveness of two equivalent, from the point of view of the O- asymptotics, algorithms. Then there is a need to clarify the first "approximation".

Thus, the estimate O (n ³ ) in the last example was obtained by us without disclosing the brackets in the product. To clarify it, it is enough to do several multiplications:

In practice, the “ O ( nk ) -scales” are insufficient for comparing the time complexity of algorithms. So, more efficient than the algorithm with linear complexity, is its competitor, whose behavior is estimated as O (log ₂ n) . The algorithm works even faster with constant complexity - O (1) , we have already dealt with one of them - it is an exchange algorithm. Accordingly, “between” O (n) and O (n ² ) is a place for O (n · log ₂ n) . Familiarity with such algorithms we have to.