Algorithmic complexity. Search algorithms

You've probably come across notations like O(log n) more than once or heard phrases like “logarithmic computational complexity” addressed to some algorithms. And if you still don’t understand what this means, this article is for you.

Difficulty rating

The complexity of algorithms is usually measured by their execution time or memory usage. In both cases, the complexity depends on the size of the input data: an array of 100 elements will be processed faster than a similar one of 1000. However, few people are interested in the exact time: it depends on the processor, data type, programming language and many other parameters. Only the asymptotic complexity is important, i.e. the complexity when the size of the input data tends to infinity.

Let's say some algorithm needs to perform 4n 3 + 7n conditional operations to process n elements of input data. As n increases, the final operating time will be significantly more affected by raising n to a cube than by multiplying it by 4 or adding 7n. Then they say that the time complexity of this algorithm is O(n 3), i.e., it depends cubically on the size of the input data.

The use of capital O (or so-called O-notation) comes from mathematics, where it is used to compare the asymptotic behavior of functions. Formally, O(f(n)) means that the running time of the algorithm (or the amount of memory occupied) grows depending on the size of the input data no faster than some constant multiplied by f(n) .

Examples

O(n) - linear complexity

For example, the algorithm for finding the largest element in an unsorted array has this complexity. We will have to go through all n elements of the array to understand which one is the maximum.

O(log n) - logarithmic complexity

The simplest example is binary search. If the array is sorted, we can check if it contains a particular value using the halving method. Let's check the middle element, if it is larger than the one we are looking for, then we will discard the second half of the array - it is definitely not there. If it is less, then vice versa - we will discard the initial half. And so we will continue to divide in half, and in the end we will check log n elements.

O(n 2) - quadratic complexity

For example, the insertion sort algorithm has this complexity. In the canonical implementation, it consists of two nested loops: one to go through the entire array, and the second to find the place for the next element in the already sorted part. Thus, the number of operations will depend on the size of the array as n * n, i.e. n 2.

There are other difficulty ratings, but they are all based on the same principle.

It also happens that the running time of the algorithm does not depend at all on the size of the input data. Then the complexity is denoted as O(1) . For example, to determine the value of the third element of an array, you do not need to remember the elements or go through them many times. You always just need to wait for the third element in the input data stream and this will be the result, which takes the same time to calculate for any amount of data.

The same is true for memory assessments when this is important. However, algorithms can use significantly more memory when increasing the size of the input data than others, but still run faster. And vice versa. This helps to choose the best ways to solve problems based on current conditions and requirements.

We already know that correctness is far from the only quality that a good program. One of the most important is efficiency, which primarily characterizes lead time programs for various input data (parameter).

Finding the exact dependency for a specific program is a rather difficult task. For this reason, they are usually limited asymptotic estimates this function, that is, a description of its approximate behavior for large values ​​of the parameter. Sometimes for asymptotic estimates they use the traditional relation (read “Big O”) between two functions , the definition of which can be found in any textbook on mathematical analysis, although it is more often used equivalence relation(read "theta big"). Its formal definition is, for example, in the book, although for now it will be enough for us to understand this issue in outline.

As a first example, let's return to the programs we just discussed for finding the factorial of a number. It is easy to see that the number of operations that must be performed to find the factorial ! numbers to a first approximation are directly proportional to this number, because the number of repetitions of the loop (iterations) in this program is equal to . In such a situation, it is customary to say that the program (or algorithm) has linear complexity(difficulty or ).

Is it possible to calculate factorial faster? It turns out yes. It is possible to write a program that will give the correct result for the same values ​​for which all the above programs do, without using either iteration or recursion. Its complexity will be , which actually means organizing calculations according to some formula without using loops and recursive calls!

No less interesting is the example of calculating the th Fibonacci number. In the process of its research, it was actually already found out that its complexity is exponential and equal to . Such programs are practically not applicable in practice. It is very easy to verify this by trying to calculate the 40th Fibonacci number using it. For this reason, the following task is quite relevant.

Problem 5.4 linear complexity.

Here is a solution to this problem in which the variables j and k contain the values ​​of two consecutive Fibonacci numbers.

Program text

public class FibIv1 ( public static void main(String args) throws Exception ( int n = Xterm.inputInt("Enter n ->< 0) { Xterm.print(" не определено\n"); } else if (n < 2) { Xterm.println(" = " + n); } else { long i = 0; long j = 1; long k; int m = n; while (--m >0) ( k = j; j += i; i = k; ) Xterm.println(" = " + j); ) ) )

The next question is quite natural - is it possible to find Fibonacci numbers even faster?

After studying certain branches of mathematics, it is quite simple to derive the following formula for the th Fibonacci number, which is easy to check for small values:

It might seem that based on it, it would be easy to write a program with complexity that does not use iteration or recursion.

Program text

public class FibIv2 ( public static void main(String args) throws Exception ( int n = Xterm.inputInt("Enter n -> "); double f = (1.0 + Math.sqrt(5.)) / 2.0; int j = (int)(Math.pow(f,n) / Math.sqrt(5.) + 0.5); Xterm.println("f(" + n + ") = " + j); ) )

This program actually uses a call to the exponentiation function ( Math.pow(f,n) ), which cannot be implemented in faster than logarithmic time (). Algorithms in which the number of operations is approximately proportional (in computer science it is customary not to indicate the base of the binary logarithm) are said to have logarithmic complexity ().

To calculate the th Fibonacci number, there is such an algorithm, the software implementation of which we will give without additional comments, otherwise you need to explain too much (the connection between Fibonacci numbers and powers of a certain matrix of order two, the use of classes for working with matrices, an algorithm for quickly raising a matrix to a power) .

Problem 5.5. Write a program that prints the th Fibonacci number that has logarithmic complexity.

Program text

public class FibIv3 ( public static void main(String args) throws Exception ( int n = Xterm.inputInt("Enter n -> "); Xterm.print("f(" + n + ")"); if (n< 0) { Xterm.println(" не определено"); } else if (n < 2) { Xterm.println(" = " + n); } else { Matrix b = new Matrix(1, 0, 0, 1); Matrix c = new Matrix(1, 1, 1, 0); while (n>0) ( if ((n&1) == 0) ( n >>>= 1; c.square(); ) else ( n -= 1; b.mul(c); ) ) Xterm.println(" = " + b.fib()); ) ) ) class Matrix ( private long a, b, c, d; public Matrix(long a, long b, long c, long d) ( this.a = a; this.b = b; this.c = c; this.d = d; ) public void mul(Matrix m) ( long a1 = a*m.a+b*m.c; long b1 = a*m.b+b*m.d; long c1 = c*m.a+ d*m.c; long d1 = c*m.b+d*m.d; a = a1; b = b1; c = c1; d = d1; ) public void square() ( mul(this); ) public long fib( ) ( return b; ) )

If you try to calculate the ten millionth Fibonacci number using this and the previous programs, the difference in calculation time will be quite obvious. Unfortunately, the result will be incorrect (in both cases) due to the limited range of long numbers.

In conclusion, we present comparison table execution times of algorithms with varying complexity and explain why, as computer speed increases, the importance of using fast algorithms increases significantly.

Let's consider four algorithms for solving the same problem, having complexities , , and , respectively. Let's assume that the second of these algorithms requires exactly one minute of time to execute on some computer with the parameter value. Then the execution time of all these four algorithms on the same computer for different parameter values ​​will be approximately the same as 10 300000 years

When novice programmers test their programs, the values ​​of the parameters on which they depend are usually small. Therefore, even if an ineffective algorithm was used when writing a program, this may go unnoticed. However, if similar program try to apply it in real conditions, its practical unsuitability will manifest itself immediately.

As the speed of computers increases, the values ​​of the parameters for which the operation of a particular algorithm is completed in an acceptable time also increase. Thus, the average value of , and, consequently, the ratio of the execution times of the fast and slow algorithms increases. How faster computer, the greater the relative loss when using a bad algorithm!

If there is one algorithm to solve a problem, then you can come up with many other algorithms to solve the same problem. Which algorithm is best suited to solve a particular problem? What criteria should be used to select an algorithm from among many possible ones? Typically, we make judgments about an algorithm based on its evaluation by a human performer. An algorithm seems complicated to us if, even after carefully studying it, we cannot understand what it does. We can call the algorithm complex and confusing due to the fact that it has a branched logical structure containing many condition checks and transitions. However, for a computer, executing a program that implements such an algorithm will not be difficult, since it executes one command after another, and it does not matter to the computer whether it is a multiplication operation or a condition test.

Moreover, we can write a cumbersome algorithm in which repeated actions are written out in a row (without using a cyclic structure). However, from the point of view of the computer implementation of such an algorithm, there is practically no difference whether a loop operator is used in the program (for example, the word “Hello” is displayed on the screen 10 times) or the operators for displaying the word “Hello” are written 10 times sequentially.

To evaluate the effectiveness of algorithms, the concept is introduced complexity of the algorithm.

Definition. Computational process generated by an algorithm is the sequence of algorithm steps passed during the execution of this algorithm.

Definition. Algorithm complexity- number of elementary steps in computing process this algorithm.

Please note, it is in the computational process, and not in the algorithm itself. Obviously, to compare the complexity of different algorithms, it is necessary that the complexity be calculated in the same elementary actions.

Definition. Time complexity of the algorithm is the time T required to complete it. It is equal to the product of the number of elementary actions and the average time to complete one action: T = kt.

Because the t depends on the executor implementing the algorithm, it is natural to assume that the complexity of the algorithm primarily depends on k. Obviously, to the greatest extent, the number of operations when executing the algorithm depends on the amount of data being processed. Indeed, alphabetizing a list of 100 names requires significantly fewer operations than ordering a list of 100,000 names. Therefore, the complexity of the algorithm is expressed as a function of the amount of input data.

Let there be an algorithm A. For it there is a parameter A, characterizing the amount of data processed by the algorithm, this parameter is often called dimension of the problem. Let us denote by T(n) algorithm execution time, through f- some function from P.

Definition. Let's say that T(n) algorithm has a growth order f(n), or, in another way, the algorithm has theoretical complexityO*(f(n)), if there are such constants from 1, from 2> 0 and number n 0, What c 1 f(n)) < T(p)< c 2 f(n) in front of everyone n >= n 0 . Here it is assumed that the function f(n) non-negative, but at least for n >= n 0 . If for T(p) condition T(n) is satisfied<= cf(n), then they say that the algorithm has theoretical complexity O(n) (read "o" big from n).

So, for example, an algorithm that performs only operations of reading data and storing them in RAM has linear complexity 0(n). The direct selection sorting algorithm has quadratic complexity 0(n 2) , since when sorting any array you need to do (p 2 - p)/2 comparison operations (in this case, there may be no permutation operations at all, for example, on an ordered array; in the worst case, it will be necessary to perform P permutations). And the complexity of the multiplication algorithm matrices(tables) of size P x P it will already be cubic O(n 3) , since computing each element of the resulting matrix requires P multiplications and n - 1 additions, and all these elements n 2.

To solve the problem, algorithms of any complexity can be developed. It is logical to use the best among them, i.e. having the least complexity.

Along with complexity, an important characteristic of the algorithm is efficiency. Efficiency means the fulfillment of the following requirement: not only the entire algorithm, but also each step of it must be such that the performer is able to complete them in a finite, reasonable time. For example, if an algorithm that produces a weather forecast for the next day will be executed for a week, then such an algorithm is simply not needed by anyone, even if its complexity is minimal for the class of similar problems.

If we consider algorithms implemented on a computer, then to the requirement of execution in a reasonable time is added the requirement of execution in a limited volume random access memory.

It is known that in many programming languages ​​there is no operation of exponentiation, therefore, the programmer must write such an algorithm independently. The operation of exponentiation is implemented through multiplication operations; As the exponent increases, the number of multiplication operations that take quite a long time to complete increases. Therefore, the question of creating an effective algorithm for exponentiation is relevant.

Let's consider a method for quickly calculating the natural power of a real number X. This method was described before our era in Ancient India.

Let's write it down P in the binary number system.

Let's replace each "1" in this entry with a pair of letters KH, and each "O" is a K.

Let's cross out the leftmost pair KH.

The resulting string, read from left to right, gives a quick calculation rule xn, if the letter TO be considered as the operation of squaring the result, and the letter X- as an operation of multiplying the result by X. Initially the result is X.

Example 1. Raise x to the power n = 100.

Let's convert the number n to the binary number system: n = 100 10 = 1100100,

We build the sequence KHKHKKHKK

Cross out AH on the left => KHKKKHKK

Calculate the desired value

K => square x => get x 2,

X => multiply the result by x => we get x 3

K => square the result => get x 6

K => square the result => we get x 12,

K => square the result => we get x 24,

X => multiply the result by x => we get x 25

K => square the result => get x 50

K => square the result => we get x 100.

Thus, we calculated the hundredth power of numbers in just 8 multiplications. This method is quite efficient, since it does not require additional RAM to store intermediate results. However, note that this method is not always the fastest.

For example, when n = 49, students can propose the following effective algorithm for exponentiation:

When implementing this algorithm, 7 multiplication operations were performed (instead of 48 operations when calculating “head-on”) and 3 cells were used (to store the variable X, to store the value x 16 and to store the current result obtained at each step). If we use the "Fast exponentiation" algorithm, we will get the same number of operations (7 multiplication operations), but to implement this algorithm we will only need 2 cells (to store the variable X and to store the current result).

The multiplication operation itself is implemented in the processor not “head-on”, but again through efficient recursive algorithms. You can read about one of these algorithms in the Reader. We will look at the “fast” multiplication algorithm, which was known back in Ancient Egypt; it is also called the “Russian” or “peasant” method. Let's look at an example of using this algorithm.

Example 2. Let's multiply 23 by 43 using the "Russian" method.

Answer: 23 x 43 = 23 + 46 + 184 + 736 = 989.

The total includes the numbers in the first column, next to which there are odd numbers in the second column.

O(1) - Most operations in a program are performed only once or only a few times. Algorithms of constant complexity. Any algorithm that always requires the same amount of time, regardless of the data size, has constant complexity.

O(N) - Program running time linear usually when each element of the input data needs to be processed only a linear number of times.

O(N 2), O(N 3), O(N a) - Polynomial complexity.

O(N 2)-quadratic complexity, O(N 3)-cubic complexity

O(Log(N)) - When is the program running time? logarithmic, the program starts to run much slower as N increases. This running time is usually found in programs that divide big problem into small ones and solve them separately.

O(N*log(N)) - This is the operating time for those algorithms that divide a big problem into small ones, and then, having solved them, combine their solutions.

O(2 N) = Exponential complexity. Such algorithms most often arise from an approach called brute force.

A programmer must be able to analyze algorithms and determine their complexity. The time complexity of an algorithm can be calculated based on an analysis of its control structures.

Algorithms without loops and recursive calls have constant complexity. If there is no recursion and loops, all control structures can be reduced to structures of constant complexity. Consequently, the entire algorithm is also characterized by constant complexity.

Determining the complexity of an algorithm mainly comes down to analyzing loops and recursive calls.

For example, consider an algorithm for processing array elements.
For i:=1 to N do
Begin
...
End;

The complexity of this algorithm is O(N), because The loop body is executed N times, and the complexity of the loop body is O(1).

If one loop is nested within another and both loops depend on the size of the same variable, then the entire design is characterized by quadratic complexity.
For i:=1 to N do
For j:=1 to N do
Begin
...
End;
The complexity of this program is O(N 2).

Exist two ways to analyze the complexity of an algorithm: bottom-up (from internal control structures to external ones) and descending (from external and internal).

O(H)=O(1)+O(1)+O(1)=O(1);
O(I)=O(N)*(O(F)+O(J))=O(N)*O(condition dominants)=O(N);
O(G)=O(N)*(O(C)+O(I)+O(K))=O(N)*(O(1)+O(N)+O(1))=O (N 2);
O(E)=O(N)*(O(B)+O(G)+O(L))=O(N)* O(N 2)= O(N 3);
O(D)=O(A)+O(E)=O(1)+ O(N 3)= O(N 3)

Complexity of this algorithm O(N 3).

Typically, about 90% of a program's running time requires repetition, and only 10% consists of actual calculations. Analysis of the complexity of programs shows which fragments these 90% fall into - these are the cycles of the greatest nesting depth. Repetitions can be organized as nested loops or nested recursion.

This information can be used by the programmer to build a more efficient program as follows. First of all, you can try to reduce the depth of nesting of repetitions. You should then consider reducing the number of statements in the most deeply nested loops. If 90% of the execution time is spent executing inner loops, then a 30% reduction in these small sections results in a 90% * 30% = 27% reduction in the execution time of the entire program.

This is the simplest example.

A separate branch of mathematics deals with the analysis of the effectiveness of algorithms, and finding the most optimal function is not so simple.

Let's evaluate algorithm for binary search in an array - dichotomy.

The essence of the algorithm: we go to the middle of the array and look for a match between the key and the value of the middle element. If we can't find a match, we look at the relative size of the key and the value of the middle element and then move to the bottom or top half of the list. In this half we again look for the middle and again compare it with the key. If that doesn’t work, divide the current interval by half again.

function search(low, high, key: integer): integer;
var
mid, data: integer;
begin
while low<=high do
begin
mid:=(low+high) div 2;
data:=a;
if key=data then
search:=mid
else
if key< data then
high:=mid-1
else
low:=mid+1;
end;
search:=-1;
end;

The first iteration of the loop deals with the entire list. Each subsequent iteration halves the size of the sublist. So, the list sizes for the algorithm are

n n/2 1 n/2 2 n/2 3 n/2 4 ... n/2 m

Eventually there will be an integer m such that

n/2 m<2 или n<2 m+1

Since m is the first integer for which n/2 m<2, то должно быть верно

n/2 m-1 >=2 or 2 m =

It follows that
2 m = We take the logarithm of each side of the inequality and get
m= The value of m is the largest integer that =<х.
So O(log 2 n).

Typically the problem to be solved has a natural "size" (usually the amount of data it processes) which we call N. Ultimately, we would like to have an expression for the time it takes the program to process data of size N as a function of N. Typically we are interested in the average case - the expected running time of the program on "typical" input data, and the worst case - the expected running time of the program on the worst input data.

Some algorithms are well understood in the sense that the exact mathematical formulas for the average and worst cases are known. Such formulas are developed by carefully studying the programs to find the running time in terms of mathematical characteristics, and then performing a mathematical analysis of them.

Several important reasons for this type of analysis:
1. Programs written in a high-level language are translated into machine codes, and it can be difficult to understand how long it will take to execute a particular statement.
2. Many programs are very sensitive to input data, and their effectiveness can greatly depend on them. The average case may turn out to be a mathematical fiction unrelated to the data on which the program is used, and the worst case is unlikely.

Best, average and worst cases play a very big role in sorting.
Amount of calculations when sorting

O-complexity analysis has become widespread in many practical applications. However, its limitations must be clearly understood.

TO main disadvantages of the approach The following can be included:
1) for complex algorithms, obtaining O-estimates is usually either very labor-intensive or practically impossible,
2) it is often difficult to determine the difficulty "on average",
3) O-scores are too coarse to reflect more subtle differences between algorithms,
4) O-analysis provides too little information (or none at all) for analyzing the behavior of algorithms when processing small amounts of data.

Defining complexity in O-notation is far from a trivial task. In particular, the efficiency of binary search is determined not by the depth of nesting of loops, but by the method of selecting each successive attempt.

Another difficulty is defining the “average case.” This is usually quite difficult to do due to the impossibility of predicting the operating conditions of the algorithm. Sometimes an algorithm is used as a fragment of a large, complex program. Sometimes the efficiency of the hardware and/or operating system, or some compiler component, significantly affects the complexity of the algorithm. Often the same algorithm can be used in many different applications.

Because of the difficulties associated with performing an "average" time complexity analysis of an algorithm, one often has to settle for worst-case and best-case estimates. These scores essentially define the lower and upper bounds of "average" difficulty. Actually, if it is not possible to analyze the complexity of an algorithm “on average,” it remains to follow one of Murphy’s laws, according to which the estimate obtained for the worst case can serve as a good approximation of the complexity “on average.”

Perhaps the main drawback of O-functions is their excessive coarseness. If algorithm A performs a certain task in 0.001*N s, while algorithm B requires 1000*N s to solve the same problem, then B is a million times faster than A. Nevertheless, A and B have the same same time complexity O(N).

Most of this lecture was devoted to the analysis of the time complexity of algorithms. There are other forms of complexity that should not be forgotten: spatial and intellectual complexity.

Space complexity as the amount of memory required to execute a program has already been mentioned earlier.

Analyzing the intellectual complexity of an algorithm examines the understandability of algorithms and the complexity of their development.

All three forms of complexity are usually interrelated. Typically, when developing an algorithm with a good time complexity estimate, you have to sacrifice its spatial and/or intellectual complexity. For example, the quicksort algorithm is significantly faster than the selection sort algorithm. The price for increasing sorting speed is expressed in the larger amount of memory required for sorting. The need for additional memory for quicksort is associated with multiple recursive calls.

The quicksort algorithm is also characterized by greater intellectual complexity compared to the insertion sort algorithm. If you ask a hundred people to sort a sequence of objects, most likely most of them will use the selection sort algorithm. It is also unlikely that any of them will use quick sort. The reasons for the greater intellectual and spatial complexity of quicksort are obvious: the algorithm is recursive, it is quite difficult to describe, the algorithm is longer (meaning the program text) than simpler sorting algorithms.

Hello! Today's lecture will be a little different from the rest. It will differ in that it is only indirectly related to Java. However, this topic is very important for every programmer. We'll talk about algorithms. What is an algorithm? In simple terms, this is a certain sequence of actions that must be performed to achieve the desired result. We often use algorithms in everyday life. For example, every morning you are faced with a task: to come to school or work, and at the same time be:

• Dressed
• Clean
• Well-fed

1. Wake up to an alarm clock.
2. Take a shower, wash your face.
3. Prepare breakfast, make coffee/tea.
4. Eat.
5. If you haven’t ironed your clothes since the evening, iron them.
6. Get dressed.
7. Leave the house.

1. Buy or download on the Internet “Dictionary of Russian Personal Names” 1966 edition.
2. Find every name on our list in this dictionary.
3. Write down on a piece of paper which page of the dictionary the name is on.
4. Put the names in order using the notes on a piece of paper.

Logarithmic complexity