Last Updated:

Basics of algorithm complexity analysis.

To solve the problem, it is often necessary to choose a method both from the number of algorithms different in the principle of their work, and from the number of possible implementations of one algorithm. For a finite number of steps, with different initial data, all of them will lead to the correct solution of the problem. But from the whole range of options, you should choose the most optimal methods.

The criterion of optimality is the complexity of the algorithmTemporal and spatial complexity are distinguished. Temporal complexity is determined by the number of elementary operations (instructions) performed by the algorithm to solve the problem. Spatial complexity is measured by the amount of memory expended by the algorithm. Only temporal complexity will be considered further.

There are two main classes of algorithms: repeat algorithms and recursive algorithms. Repeat algorithms are based on loop operators and conditional operators. Analyzing algorithms of this class will require counting all the cycles and operations within them. Recursive algorithms (recursive function – a function that calls itself) break the main problem into parts and solve each of them separately. Analyzing a recursive algorithm is usually more difficult. It requires counting the number of operations to split the task, executing the algorithm on each of the parts of the main task, as well as combining them.

What instructions do you count? The answer to this question is not always obvious, but at least opinions agree on one thing – only significant transactions should be taken into account when counting.

These usually include:

  • simple assignment: a ← b;
  • indexing an array element (finding its value);
  • arithmetic operations: -, +, *, /;
  • compare operations: <, >, =, <=, >=, <>;
  • logical operations: or, and, not.

The temporal complexity of the algorithm is significantly affected by the amount of input data. So, if when processing a small amount of data, the difference between the work of two different algorithms seems insignificant, then an increase in this volume will significantly affect the execution time of each of them.

But the temporal complexity often depends not only on the volume, but also on the values of the data, as well as the order in which they arrive. For example, many sorting algorithms will spend much less time arranging an array if it is already sorted. Because of such difficulties, the concept of temporal complexity is considered in three cases: worst, best and average.

The worst case corresponds to the least successful set of input data, when the algorithm has to perform the maximum number of elementary operations to solve the problem. At best, the input dataset will provide the fewest possible number of operations.

The average case is much more difficult to determine. Input data is broken down into possible groups, which they can be. Next, the probability of the appearance of each group is determined. After that, the time of operation of the algorithm on the data of each group is calculated. For us, the most interesting are the most and least favorable cases.

Let's calculate the number of instructions of the linear search algorithm:

At best, the element (key) you are looking for is equal to the value of the first element in the array. Then only four operations will be required:

  • in the loop header: assigning the variable i an initial value and comparing this value to the value of n;
  • in the branching operator: indexing the i-th element and comparing it with the key.

In the worst case, the desired element will be at the end of the array, or it will be completely absent. In this case, the cycle will perform n iterations, and the number of operations will increase to 2 + 4n:

  • in the heading of the cycle: initial assignment and first comparison, as well as ncomparisons and n increments of the counter value: 2+2n;
  • in the branching operator: n indexations and n comparisons: 2n.

Now let's calculate the number of instructions of the algorithm for finding the maximum element:

In the first line, two operations are performed: finding an element with an index of 0 in array A and assigning the value of this element to the Max variable. Before starting the loop body, two more operations are performed: initializing the counter variable i and comparing the value of this variable with the number of elements n. The cycle will perform an n-1 iteration, during which time i is incremented n-1 times and condition (i<n) is checked n-1 times.

The cyclo body executed n-1 times, hence the branching operator compared the values of the elements n-1 times, thereby executing two instructions at each iteration: finding the ith element and comparing it to Max. We get the number of operations of the algorithm: 2 + 2 + 4 (n-1) = 4 + 4n-4 = 4n.

 

This will be the complexity of the algorithm at best, i.e. the maximum element corresponded to the first element of the array, so the branching operator in the body of the loop was not executed. In the worst case, the array will be ordered in ascending order, which means that at each iteration you will need to replace the value of the Max variable.

This will require two more instructions on each iteration: finding the i-th element and assigning its value to the Max variable. As a result, we get the number of operations for the worst case: 4n + 2n = 6n.