Algorithm efficiency is a property of an algorithm that is associated with the computational resources used by the algorithm. The algorithm must be analyzed to determine the resources required by the algorithm. Algorithm efficiency can be thought of as analogous to the manufacturing productivity of repetitive or continuous processes.

To achieve maximum efficiency, we want to reduce resource usage. However, different resources (such as time and memory) cannot be directly compared, so which of two algorithms is considered more efficient often depends on which factor is more important, such as the requirement for high speed, minimal memory usage, or another measure of efficiency.

Please note that this article NOT about algorithm optimization, which is discussed in the articles program optimization, optimizing compiler, cycle optimization, object code optimizer, and so on. The term "optimization" itself is misleading because everything that can be done falls under the umbrella of "improvement."

Background

The importance of efficiency with an emphasis on execution time was emphasized by Ada Lovelace in 1843 regarding Charles Babbage's mechanical analytical engine:

“In almost all computing, there is a large choice of configurations possible to successfully complete the process, and different conventions should influence the choice for the purpose of performing the calculation. The essential thing is to choose a configuration that will result in minimizing the time required to perform the calculation."

Early electronic computers were very limited in both speed and memory. In some cases, it has been realized that there is a time-memory trade-off, in which a task must either use a large amount of memory to achieve high speed, or use a slower algorithm that uses a small amount of working memory. In this case, the fastest algorithm was used for which the available memory was sufficient.

Modern computers are much faster than those early computers and have much more memory (gigabytes instead of kilobytes). However, Donald Knuth emphasizes that efficiency remains an important factor:

“In established engineering disciplines, a 12% improvement is easily achievable and has never been considered prohibitive, and I believe the same should be true in programming.”

Review

An algorithm is considered efficient if its resource consumption (or resource cost) is at or below some acceptable level. Roughly speaking, "acceptable" here means "the algorithm will run for a reasonable amount of time on an available computer." Because there has been a significant increase in the processing power and available memory of computers since the 1950s, the current "acceptable level" was not acceptable even 10 years ago.

Computer manufacturers periodically release new models, often more powerful ones. The cost of software can be quite high, so in some cases it is easier and cheaper to get better performance by purchasing a faster computer that is compatible with your existing computer.

There are many ways to measure the resources used by an algorithm. The two most used measurements are speed and memory used. Other measurements may include transfer speed, temporary disk usage, long-term disk usage, power consumption, total cost of ownership, response time to external signals, and so on. Many of these measurements depend on the size of the algorithm's input data (that is, the quantities requiring data processing). Measurements may also depend on the way in which the data is presented (for example, some sorting algorithms perform poorly on already sorted data or when the data is sorted in reverse order).

In practice, there are other factors that influence the effectiveness of the algorithm, such as the required accuracy and/or reliability. As explained below, the way an algorithm is implemented can also have a significant effect on actual performance, although many aspects of the implementation are optimization issues.

Theoretical analysis

In the theoretical analysis of algorithms, it is common practice to estimate the complexity of an algorithm in its asymptotic behavior, that is, to reflect the complexity of the algorithm as a function of the size of the input n Big O notation is used. This estimate is generally quite accurate for large n, but may lead to incorrect conclusions at small values n(Thus, bubble sort, which is considered slow, may be faster than quick sort if you only need to sort a few elements).

Designation	Name	Examples
O(1) (\displaystyle O(1)\,)	permanent	Determining whether a number is even or odd. Using a constant size lookup table. Using a suitable hash function to select an element.
O (log ⁡ n) (\displaystyle O(\log n)\,)	logarithmic	Finding an element in a sorted array using binary search or balanced tree, similar to operations on the binomial heap.
O(n) (\displaystyle O(n)\,)	linear	Finding an element in an unsorted list or unbalanced tree (worst case). Addition of two n-bit numbers using end-to-end carry.
O (n log ⁡ n) (\displaystyle O(n\log n)\,)	quasilinear, logarithmically linear	Compute fast Fourier transform, heapsort, quicksort (best and average case), merge sort
O (n 2) (\displaystyle O(n^(2))\,)	square	Multiplying two n-digit numbers using a simple algorithm, bubble sort (worst case), Shell sort, quicksort (worst case), selection sort, insertion sort
O (c n) , c > 1 (\displaystyle O(c^(n)),\;c>1)	exponential	Finding an (exact) solution to the traveling salesman problem using dynamic programming. Determining if two logical statements are equivalent using exhaustive search

Verification Tests: Measuring Performance

For new versions of software or to provide comparison with rival systems, benchmarks are sometimes used to compare the relative performance of algorithms. If, for example, a new sorting algorithm is released, it can be compared with predecessors to ensure that the algorithm is at least as efficient on known data as others. Performance tests can be used by users to compare products from different manufacturers to evaluate which product will best suit their requirements in terms of functionality and performance.

Some benchmark tests provide comparative analysis of different compiling and interpreting languages, such as Roy Longbottom's PC Benchmark Collection, and The Computer Language Benchmarks Game compares the performance of implementations of typical tasks in some programming languages.

Implementation issues

Implementation issues may also affect actual performance. This includes the choice of programming language and the way in which the algorithm is actually coded, the choice of translator for the chosen language or the compiler options used, and even the operating system used. In some cases, a language implemented as an interpreter may be significantly slower than a language implemented as a compiler.

There are other factors that can affect timing or memory usage that are beyond the programmer's control. This includes data alignment, detailing, garbage collection , instruction - level parallelism and subroutine calling .

Some processors have the ability to perform vector operations, which allows one operation to process multiple operands. It may or may not be easy to use such features at the programming or compilation level. Algorithms designed for sequential computing may require complete redesign to accommodate parallel computing.

Another issue may arise with processor compatibility, where instructions may be implemented differently, so that instructions on some models may be relatively slower on other models. This can be a problem for the optimizing compiler.

Measuring Resource Usage

Measurements are usually expressed as a function of the size of the entrance n.

The two most important dimensions are:

• Time: How long the algorithm takes on the CPU.
• Memory: How much working memory (usually RAM) is needed for the algorithm. There are two aspects to this: the amount of memory for the code and the amount of memory for the data that the code operates on.

For battery-powered computers (such as laptops) or for very long/large calculations (such as supercomputers), a different kind of measurement is of interest:

• Direct energy consumption: Energy required to run a computer.
• Indirect energy consumption: Energy required for cooling, lighting, etc.

In some cases, other, less common measurements are needed:

• Gear size: Bandwidth may be the limiting factor. Compression can be used to reduce the amount of data transferred. Displaying a graphic or image (such as the Google logo) can result in tens of thousands of bytes being transferred (48K in this case). Compare this to transmitting the six bytes in the word "Google".
• External memory: Memory required on a disk or other external storage device. This memory can be used for temporary storage or for future use.
• Response time: This setting is especially important for real-time applications where the computer must respond quickly to external events.
• Total Cost of Ownership: The parameter is important when it is intended to execute a single algorithm.

Time

Theory

This type of test also significantly depends on the choice of programming language, compiler and its options, so that the compared algorithms must be implemented under the same conditions.

Memory

This section deals with the use of main memory (often RAM) needed by the algorithm. As with timing analysis above, analysis of an algorithm typically uses spatial complexity of the algorithm to estimate the required runtime memory as a function of the input size. The result is usually expressed in terms of "O" big.

There are four aspects of memory usage:

• The amount of memory required to store the algorithm code.
• The amount of memory required for the input data.
• The amount of memory required for any output (some algorithms, such as sorts, frequently rearrange the input and do not require additional memory for the output).
• The amount of memory required by the computational process during computation (this includes named variables and any stack space required for subroutine calls, which can be significant when using recursion).

Early electronic computers and home computers had relatively small working memory capacities. Thus, in 1949 the EDSAC had a maximum working memory of 1024 17-bit words, and in 1980 the Sinclair ZX80 was released with 1024 bytes of working memory.

Modern computers can have relatively large amounts of memory (perhaps gigabytes), so compressing the memory used by an algorithm into some given amount of memory is less required than before. However, the existence of three different categories of memory is significant:

• Cache (often static RAM) - runs at speeds comparable to the CPU
• Main physical memory (often dynamic RAM) - runs slightly slower than the CPU
• Virtual memory (often on disk) - gives the illusion of huge memory, but works thousands of times slower than RAM.

An algorithm whose required memory fits into the computer's cache is much faster than an algorithm that fits into main memory, which, in turn, will be much faster than an algorithm that uses virtual space. Complicating matters is the fact that some systems have up to three levels of cache. Different systems have different amounts of these types of memory, so the memory effect on an algorithm can vary significantly from one system to another.

In the early days of electronic computing, if an algorithm and its data did not fit into main memory, it could not be used. These days, using virtual memory provides massive memory, but at the cost of performance. If the algorithm and its data fit in the cache, very high speed can be achieved, so minimizing the memory required helps minimize time. An algorithm that does not fit entirely into the cache, but provides locality of links, can work relatively quickly.

Examples of effective algorithms

Criticism of the current state of programming

Programs are becoming slower more rapidly than computers are becoming faster.

May states:

In widespread systems, halving instruction execution can double battery life, and big data provides an opportunity for better algorithms: Reducing the number of operations from N x N to N x log(N) has a strong effect for large N... For N=30 billion, these the changes are similar to 50 years of technological improvements.

Competition for the best algorithm

The following competitions invite participation in the development of the best algorithms, the quality criteria of which are determined by the judges:

see also

• Arithmetic coding is a type of entropy coding with variable code length for efficient data compression
• An associative array is a data structure that can be made more efficient when used trees PATRICIA or Judy arrays
• Performance test - a method of measuring comparative execution time in certain cases
• Best, worst and average case- conventions for estimating execution time for three scenarios
• Binary search is a simple and effective technique for searching a sorted list
• Branch table

Goals and objectives of the lecture: introduction to methods for analyzing the complexity and efficiency of algorithms and data structures

Main issues: experimental and analytical analysis of the effectiveness of algorithms.

N. Wirth’s classic statement “A good program is the unity of a well-thought-out algorithm and effective data structures.”

Algorithm Analysis
The concepts of “algorithm and data structures” are central to the field of computer technology, but in order to call certain data structures and algorithms “high-quality and efficient”, precise techniques for analyzing them must be used. As a natural quality criterion, it is natural to highlight, firstly, execution time. Also important is the amount of memory and disk space resources spent, the speed of data access (efficiency of the data structure). Attention should also be paid to the reliability and reliability of decisions, their stability.

The algorithm should not be tied to a specific implementation. Due to the variety of programming tools used, algorithms that are different in implementation can produce results that differ in efficiency.

The execution time of an algorithm or operation on a data structure depends, as a rule, on a number of factors. The simplest way to determine the time required to execute an algorithm is to measure the time before and after the algorithm runs.

It should, however, be remembered that this method of estimating time is not accurate; first of all, it should be understood that in modern operating systems several tasks can be executed in parallel and the execution of a test case can be combined with other types of activity. Further, it should be understood that a stable dependence can be achieved only by conducting repeated tests, otherwise, due to the influence on the final result of the work of random factors depending on the specifics of the initial data, and other factors, the execution time of the algorithm will also be a random variable. When conducting research, it is necessary to run the algorithm with a different set of initial data; usually the data itself is generated randomly, so due to different sets of data, the time spent will also differ.

Once a set of estimates is obtained, a graph can be constructed and approximated.

Such an analysis should always be used when using non-trivial algorithms; this is similar to the recommendation to develop an application, using for debugging not a trial set of several dozen records or elements, but real data in full, which avoids modification or even complete reworking of the algorithm or structures data if they subsequently prove to be impractical. Having a set of experimental results, you can perform interpolation and extrapolation and determine the behavior of the algorithm in real conditions.

In general, we can say that the execution time of an algorithm or data structure method increases as the size of the source data increases, although it also depends on the type of data, even if the size is equal. In addition, execution time depends on the hardware (processor, clock frequency, memory size, disk space, etc.) and software (operating environment, programming language, compiler, interpreter, etc.) with which the implementation, compilation is carried out and execution of the algorithm. For example, all other things being equal, the execution time of an algorithm for a certain amount of source data will be less when using a more powerful computer or when writing the algorithm as a program in machine code compared to its execution by a virtual machine interpreting it into bytecodes.

The conclusion is that conducting empirical analysis of algorithms is not truly reliable. The main disadvantages can be reduced to the following three points:

1) experiments can be carried out only using a limited set of initial data; results obtained using another set are not taken into account.

2) to compare the effectiveness of two algorithms, it is necessary that experiments to determine their execution time be carried out on the same hardware and software;
3) to experimentally study the execution time of the algorithm, it is necessary to carry out its implementation and execution.

Thus, we come to the need to use general analysis methods for analyzing algorithms, which allows:

1) takes into account various types of input data;

2) allows you to evaluate the relative effectiveness of any two algorithms, regardless of hardware and software;

3) can be carried out according to the description of the algorithm without its direct implementation or experiments.

The essence of the general analysis is that the function f=f(n1, .., nm) is assigned to a certain algorithm. In its simplest form, it is a function of one variable n1 – the amount of input data. However, there may be other variables - for example, the accuracy of the calculation or its reliability. So, to determine whether a certain number is prime in the case of large numbers (the length of the binary representation is more than 200 bits), a probabilistic method is used, the reliability of which can be varied. The most well-known functions are linear, power, and logarithmic. Therefore, you should take the time to remember the basics of working with them.

When constructing algorithms, the first stage occurs using not a programming language, but a description in human language. Such descriptions are not programs, but at the same time they are more structured than ordinary text. In particular, “high-level” descriptions combine natural language and common programming language structures, making them accessible yet informative. Such descriptions facilitate high-level analysis of the data structure or algorithm. Such descriptions are usually called pseudocode. It should also be noted that pseudocode is often more useful for analysis than code in a specific programming language.

Sometimes there is a need to prove certain statements in relation to a certain data structure or algorithm. For example, you need to demonstrate the correctness and speed of execution of the algorithm. To strictly prove statements, it is necessary to use mathematical language, which will serve as proof or justification of statements. There are several simple ways to prove this.

Sometimes statements are written in a generalized form: “The set s contains an element x with property v. To prove this statement, it is enough to give an example x “belongs” to s, which has this property. In such a generalized form, as a rule, unlikely statements are written, for example: “Every element x of the set s has property P.” To prove the fallacy of this statement, it is enough to simply give an example: x “belongs” to s, which does not have the property P. In this case, the element x will act as a counter-example.

Example: It is stated that any number of the form 2^n - 1 is prime if n is an integer greater than 1. The statement is false.

Proof: To prove someone wrong, you need to find a counterexample.

This is a counter-example: 2^4 - 1 = 15, 15= 3 * 5.

There is another way, based on proof by contradiction (using negation). The main methods in this case are contraposition and contradiction. The use of contrast methods is similar to mirroring: in order to prove that “if x is true, then y is true,” we will assert the opposite, “if y is false, then x is false.” From a logical point of view, these statements are identical, but the second expression, which is a cotroposition of the first, is more convenient.

Example: If a*b is an odd number, then a is odd or b is odd.

Proof: to prove this statement, consider the contraposition: “If a is an even number and b is odd, then a*b is even. Let a = 2*x, for some integer x. Then a*b = 2*i*b, and therefore the product a*b is even.

When using methods of proof by contradiction, it is useful to use logic.

A or b = requires a or b to be executed, or both a and b at the same time.
. a and b = requires a and b to be executed simultaneously.
. a xor b = requires execution of a, but not b, or b, but not a.

When using the contradiction method to prove that a statement q is true, one first assumes that q is false and then shows that such an assumption leads to a contradiction (for example, 2 * 2<>4). Having come to such a contradiction, we can argue that a situation in which q is false does not exist, and, therefore, q is true.

In most cases, statements about program execution time or space use use an integer parameter n (representing the “size” of the problem). Then when we formulate a statement x(n), then for a set of values ​​n such statements are equivalent. Since this statement applies to an “infinite” set of numbers, it is impossible to provide an exhaustive direct proof. In such situations, induction methods are used. The method of induction is based on the fact; that for any n > 1. There is a finite sequence of actions that starts with something known to be true and ultimately leads to a proof that q(n) is true. Thus, a proof by induction begins with the statement that q(n) is true for n=1,2,3, etc. up to some constant k. Next we prove that the next “step” of inductions q(n+1), q(n+2) is also true for n > k.

When analyzing algorithms, calculating the number of operations and their execution time, one should not take into account “small details”; constant factors and constants should be neglected. In practice, the concept of a large function is used ABOUT. suppose that there are two functions f(n) and g(n), it is assumed that f(n)<= O(g(n)) , т.е. функция О ограничивает сверху значения функции f, начиная с n=n0.

For example, the algorithm for counting the number of elements equal to zero in an array is described by O(n), where n is the number of elements.

1) 20n3+7.2n2-21.78n + 5 is described as O(n3)

2)xn-2 + a(0) is described as O(xn).

2) 3*log(n) + log(log(n)) is described as O(log(n)).

3) 2100 is described as O(1)

4) 5/n is described as O(1/n).

Please note that the function o(n) limits the target time cost function from above, but you should always strive to choose such a function O(n) that there is maximum accuracy.

The most famous O functions in ascending order:

When using asymptotic analysis, be careful that when you use O notation, you often neglect constant factors and addition constants. However, if this value is large enough, although the form of the function O(1) is more preferable than the algorithm described by the function O(n), it is, of course, the second algorithm that will gain practical application.

Depending on the type of function f(n), the following classes of complexity of algorithms are distinguished.

Algorithm complexity classes depending on the complexity function
View f(n)	Characteristics of the class of algorithms
	Most instructions for most functions are executed one or more times. If all instructions in a program have this property, then the execution time of the program is constant.
log N	When a program's execution time is logarithmic, the program becomes slower as N increases. Such execution times are typically associated with programs that reduce a large problem to a set of smaller subproblems, reducing the size of the problem by some constant factor at each step. Changing the base does not greatly affect the change in the value of the logarithm: n
N	When a program's execution time is linear, it usually means that each input element undergoes little processing.
N log N	Runtime proportional to N log N occurs when an algorithm solves a problem by breaking it down into smaller subproblems, solving them independently, and then combining the solutions.
N 2	When the running time of an algorithm is quadratic, it is useful for practical use in solving relatively small problems. Quadratic execution time typically appears in algorithms that process all pairs of data items (perhaps in a double-nested loop).
N 3	A similar algorithm that processes triplets of data elements (possibly in a triple-nesting loop) has a cubic execution time and is practically applicable only for small problems.
2N	Only a few algorithms with exponential running time have practical applications, although such algorithms arise naturally when attempting to solve a problem directly, such as brute force.

Based on mathematical methods for studying asymptotic functions of complexity at infinity, five classes of algorithms are identified.

1. A class of fast algorithms with constant execution time, their complexity function is O(1). The intermediate state is occupied by algorithms with complexity O(log N), which are also classified in this class.

2. A class of rational or polynomial algorithms, the complexity function of which is determined polynomially from the input parameters. For example, O(N), O(N 2, O(N 3).

3. A class of subexponential algorithms with a degree of complexity O(N log N).

4.Class of exponential algorithms with a degree of complexity O(2 N).

5.Class of overexponential algorithms. There are algorithms with factorial complexity, but they generally have no practical application.

The memory state during algorithm execution is determined by the values ​​that require certain areas to be allocated. In this case, in the course of solving the problem, an additional number of cells can be used. By the amount of memory required by algorithm A for input D, we mean the maximum number of memory cells used during the execution of the algorithm. The capacity complexity of an algorithm is defined as the asymptotic estimate of the algorithm's worst-case memory capacity function.

Thus, the resource complexity of an algorithm in the worst, average and best cases is defined as an ordered pair of classes of functions of time and capacity complexity, specified by asymptotic notation and corresponding to the case under consideration.

The main algorithmic constructs in procedural programming are following, branching and looping. To obtain the complexity functions for the best, average and worst cases with a fixed input dimension, it is necessary to take into account differences in the evaluation of the main algorithmic structures.

• The complexity of the “Following” construction is the sum of the complexity of the blocks following each other: f=f 1 +f 2 +...+f n .
• The complexity of the "Branching" design is determined through the probability of transition to each of the instructions, determined by the condition. At the same time, checking the condition also has a certain complexity. To calculate the complexity of the worst case, the branching block that has the most complexity can be selected; for the best case, the block with less complexity can be selected. f if =f 1 +f then p then +f else (1-p then)
• The complexity of the "Loop" construction is determined by calculating the loop termination condition (usually of order 0(1)) and the product of the number of completed iterations of the loop by the largest possible number of operations of the loop body. If nested loops are used, their complexity is multiplied.

Thus, to estimate the complexity of an algorithm, a general method for obtaining the complexity function can be formulated.

1. Decomposition of the algorithm involves identifying the basic structures in the algorithm and estimating the complexity. In this case, the following of the main algorithmic structures is considered.
2. Line-by-line analysis of labor intensity for basic language operations implies either a cumulative analysis (taking into account all operations) or operational analysis (taking into account the complexity of each operation).
3. Inverse composition of the complexity function based on the methodology for analyzing basic algorithmic structures for the best, average and worst cases.

A feature of assessing the resource efficiency of recursive algorithms is the need to take into account additional memory costs and the mechanism for organizing recursion. Therefore, the complexity of recursive implementations of algorithms is related to the number of operations performed during one recursive call, as well as the number of such calls. The costs of returning values ​​and transferring control to the call point are also taken into account. When estimating the required stack memory, you need to take into account that at a particular point in time, it is not a recursion fragment that is stored on the stack, but a chain of recursive calls. Therefore, the stack size is determined by the maximum possible number of concurrent recursive calls received.

Programmer's library

“If debugging is a process of removing errors, then programming should be a process of introducing them”

E. Dijkstra

1.2. Why study algorithms? Efficiency of algorithms

Firstly, algorithms are vital components for solving any problems in various areas of computer science. Algorithms play a key role at the current stage of technology development. Here you can recall such common tasks as:

• solving mathematical equations of varying complexity, finding the product of matrices, inverse matrices;
• finding optimal ways to transport goods and people;
• finding optimal options for distributing resources between various nodes (manufacturers, machines, workers, processors, etc.);
• finding sequences in the genome that match;
• searching for information on the global Internet;
• making financial decisions in e-commerce;
• processing and analysis of audio and video information.

This list goes on and on and, in fact, it is almost impossible to find an area of ​​computer science and information science where certain algorithms are not used.

Secondly, high-quality and efficient algorithms can be catalysts for breakthroughs in industries that are, at first glance, far from computer science (quantum mechanics, economics and finance, the theory of evolution).

And thirdly, studying algorithms is also an incredibly interesting process that develops our mathematical abilities and logical thinking.

1.3. Efficiency of algorithms

Let's assume that the speed of a computer and the amount of its memory can be increased indefinitely. Would there be a need to study algorithms then? Yes, but only to demonstrate that the decoupling method has a finite running time and that it gives the correct answer. If computers were infinitely fast, an arbitrary correct method for solving a problem would do. Of course, then most often the method that is easier to implement would be chosen.

Today, computers are very powerful, but their speed is not infinite, and neither is their memory. Thus, in calculus, it is as limited a resource as the amount of memory required. These resources should be used wisely, which is facilitated by the use of algorithms that are efficient in terms of the use of time and memory resources.

Algorithms designed to solve the same problem can often vary greatly in efficiency. These differences can be much more noticeable than those caused by different hardware and software.

As noted above, this section will focus on the sorting task. The first algorithm that will be considered, inclusion sort, requires time to operate, the amount of which is estimated as c 1 n 2, where n is the size of the input data (Number of elements in the sequence to be sorted), c 1 is some constant. This expression indicates how the running time of the algorithm depends on the volume of source data. In the case of inclusion sort, this dependence is quadratic. The second algorithm, merge sort, requires time, the amount of which is estimated as 2 nLog 2 n. Typically, the inclusion sort constant is smaller than the merge sort constant, that is, c12 grows faster as n increases than the ILog 2 n function. And for some value n = n 0 a moment will be reached when the influence of the difference in constants ceases to matter and in the future the function c 2 nLog 2 n will be less than c 1 n 2 for any n > n 0.

To demonstrate this, consider two computers - A and B. Computer A is faster and runs the sorting algorithm, and computer B is slower and runs the merge sort algorithm. Both computers must sort a set consisting of a million numbers. Let's say that computer A performs a billion operations per second, and computer B only ten million, there is A running 100 times faster than B. To make the difference more noticeable, let's say that the code for the enable method was written by the best programmer in the world using instructions to the processor, and to sort n numbers with this algorithm you need to perform 2n 2 operations (that is, C 1 = 2). Merge sort on computer B was written by a novice programmer using a high-level language and the resulting code requires 50nlog 2 n operations (that is, c 2 = 50). Thus, to sort a million numbers, computer A would need

and to computer B -

Therefore, using code whose running time increases more slowly, even with a bad computer and a bad compiler, requires an order of magnitude less CPU time! For sorting 10,000,000 digits, the advantage of merge sort becomes even more noticeable: while inclusion sort requires about 2.3 days for such a task, then for merge sort it takes less than 20 minutes. The general rule is that the larger the number of elements to sort, the greater the advantage of merge sort. The above example demonstrates that algorithms, like computer software, are technology. Overall system performance depends as much on the efficiency of the algorithm as it does on the power of the hardware.

So, various options for computing machines are considered, from the simplest Turing machines to a homogeneous computing environment. All of them can be used to solve those problems for which an algorithm exists. Based on these models, more specialized models of computation are built, namely: non-branching arithmetic programs, bitwise computation, binary vector computation, and decision trees.

The algorithms have the following characteristics:

a) complexity;

b) labor intensity;

c) reliability, etc.

There are many criteria for assessing the complexity of algorithms. Most often we will be interested growth order the time and memory capacity required to solve the problem as the amount of input data increases. Let us associate with each specific task a certain number called its size. For example, the size of a matrix multiplication problem can be the largest size of the factor matrices; the size of a problem on a graph can be the number of edges of a given graph, etc.

The time taken by an algorithm as a function of problem size is called time complexity this algorithm. The behavior of this complexity in the limit as the problem size increases is called asymptotic time complexity. Similarly defined capacitive complexity And asymptotic capacity complexity.

An important motivation for considering formal computational models is the desire to reveal the computational complexity of various problems in order to obtain lower bounds for the computation time. To show that there is no algorithm that can complete a given task in less than a certain amount of time requires a precise and sometimes highly specialized definition of what an algorithm is. One example of such a definition is Turing machines.

4.1.1. Frame and frame machines*

Consider two cars:

1. Machines with random access to memory (equal access address machine - RAM) models a computer with one adder, in which program instructions cannot change themselves.

2. The stored program model is a machine with random access to memory and the ability to modify instructions (RAM*).

Fig.2.9 Structure of RAM machines (RAM*)

For RAM, the program is not written to memory, so the program does not modify itself. A program is a sequence of labeled commands. There are arithmetic instructions, I/O instructions, indirect addressing instructions, and branch instructions. All calculations are performed in register r 0 (adder), which, like any other memory register, can store an arbitrary integer. Each command consists of two parts - an operation code and an address. PAM commands are a subset of Assembly language commands; this subset can be expanded at will, but the order of complexity of the tasks will not change.

The operand can be one of the following types:

1. =i means the whole number itself i and is called a literal;

2. i- register contents i (i must be non-negative);

3. *i means indirect addressing, that is, the value of the operand is the contents of the register j,Where j- an integer that is in the register I;If j<0, the car stops.

You can determine the value of the program R using two objects: a mapping c from a set of non-negative integers to a set of integers and a “command counter”, which determines the next command to be executed. Function c is memory display, namely c(i)- integer contained in register number I (content register I).

At the beginning с(i)=0 for all i 0 , the program counter is set to the first instruction in P, and the output tape is empty. After execution k th team from R the counter automatically switches to (k+1)-th (that is, to the next) command, if k-my team was not a team like JUMP, HALT, JGTZ and the like.

The RAM* program is located in memory registers. Each RAM* command occupies two consecutive memory registers: the first register contains the operation code, the second - the address. The set of instructions for RAM* coincides with the corresponding set for RAM in everything except indirect addressing, which is excluded: RAM* can simulate indirect addressing by changing instructions during program execution.

In addition to checking that the algorithm implemented by the student as a solution is capable of producing the correct answer to the problem given certain initial data, when checking the solution, the running time of the program is also taken into account. This does not mean that it is vitally important to write optimal algorithms for all tasks without exception (which can often take a lot of time for their competent implementation and debugging). This simply means that in some individual tasks the time parameter can play a very important role. It may well happen that at some Olympiad round there will not be a single problem in which optimality is necessary. However, the opposite can also happen.

Thus, both students and teachers should be able to compare different algorithms based on their effectiveness. Schoolchildren - in order to choose the most appropriate way to solve a problem at the right moment, teachers - to competently select tasks and understand what solution the author of a particular problem had in mind when setting exactly such time limits.

To evaluate the effectiveness of the algorithm, a complexity function is used, denoted O (read “about big”). In fact, there are other assessments, but at the stage when a student is just beginning to get acquainted with various algorithms, they are not really needed. The complexity function reflects the pattern in which the program execution time will increase depending on the source data or their quantity.

An example of an algorithm whose execution time depends on the initial data is the algorithm for finding all natural divisors of the number N. Obviously, the larger the number, the more loop steps it will be necessary to perform. An example of an algorithm whose execution time depends on the amount of input data would be searching for the largest number in an array. The longer the array, the more comparison operations must be done to determine which number is the largest.

The main functions are:

l O(1) - such a complexity function indicates that the running time of the program is constant for any initial data;

l O(N) - the number of operations grows in proportion to N (here N can be either a task parameter or the number of elements in the array).

l O(log N) - the number of operations grows in proportion to the logarithm of N (this is exactly the complexity of, for example, the method of halves when searching for an element in an ordered array). As N increases by an order of magnitude, the number of operations changes by one. The base of the logarithm is usually not specified; we are interested in the nature of growth (fast/slow), and not the exact value of time.

l O(N2) - the number of operations increases in proportion to the square of N. In general, it can be O(Nk) depending on the complexity of the problem.

l O(N!) - the number of operations increases in proportion to the factorial N.

There are a number of subtleties here due to the fact that not all operations are performed in the same amount of time, so when estimating time complexity, those operations that require the most time are used.

Most often, when describing algorithms, an estimate of their operating time is given in its pure form, that is, without taking into account input/output operations.

Example: let's estimate the complexity of a program that enters an array from the keyboard and finds the largest element in it.

Let's add the number of operations N+(N-1)+1=2N. That is, there is such a constant that for any N the number of operations does not exceed CN. Therefore, the complexity of the algorithm is O(N).

Example: let's estimate the complexity of a program that enters an array from the keyboard and finds in it an element with a given property (for example, equal to a certain value).

The algorithm consists of the following steps:

Entering an array (N input operations) searching for an element with a given property (how lucky: the element can be located either closer to the beginning of the array or at the very end; if the element does not exist, then you need to make all N comparisons to make sure of this) outputting the result .

In the best case, this algorithm will require N+2 operations (input of the entire array, a single comparison, output), in the worst case (when there is no such element - 2N+1 operations). If N is a large number, for example about 106, then unity can be neglected. Therefore, the complexity of the algorithm is O(N).

Example: let's determine the complexity function of a word encryption algorithm of length L using the substitution method. Let there be a table in which for each character of the alphabet the character with which it must be replaced is written. Let's denote the number of letters of the alphabet S.

The algorithm consists of the following steps:

Entering a word (one operation) loop through all characters

1. for each character, find its replacement in the table (if the table is not ordered and does not have any properties that facilitate the search, then in the worst case there are S operations for one character if the searched element is at the very end)

2. output of the found symbol

End of the cycle

The total number of operations is 1+(S+1)*L. In the case of sufficiently large S and L units can be neglected, it turns out that the complexity function of this algorithm is O(S*L).

Example: let's define the complexity function of the algorithm for converting the natural number N into the binary number system (without data input and output operations).

The algorithm consists of the following steps:

Loop until the result of dividing a number by 2 is 0

1. divide the number by 2 and remember the remainder

2. take the result of division as a new number

End of the cycle

The total number of operations does not exceed 1+log2N. Therefore, this algorithm has a complexity of O(log N).

If a program consists of several parts with different complexity functions, then O The larger complexity function will “absorb” the smaller ones. For example, if you do O(N) array input, O(N2) sort, and O(N) output of the ordered array, then you can say that the entire program has O(N2) complexity.

The practical application of knowledge about the complexity functions of algorithms is twofold. Firstly, for a certain task, a more optimal algorithm can be chosen if there is relevant data about it in the literature. Secondly, knowing the running time of his solution on one set of initial data, a student can approximately estimate the running time of the same program on data that corresponds to the maximum restrictions for a given problem.

Questions

These tasks are used for self-testing on the material presented and are not mandatory.

1. Determine the complexity function of the algorithm for solving a quadratic equation.

2. Determine the complexity function of the algorithm for drawing a regular polygon based on a given number of sides.

3. Determine the complexity function of the algorithm for inserting an element into an array at a given position (with a preliminary shift of all elements with numbers greater than or equal to the given one by one position to the right).

4. Determine the complexity function of the algorithm for adding two natural numbers into a column (let A be the number of digits of the first number, B the number of digits of the second).

5. Determine the complexity function of the algorithm for multiplying two natural numbers in a column.