The basic complexity analysis algorithm complexity analysis: how to analyze, statistical algorithm execution efficiency and resource consumption?

This article will continue with four aspects of complexity analysis, Best Case Time complexity, Worst Case time complexity, average Case Time complexity Amortized time is new complexity.

Best – and worst-case time complexity

Take a look at the following example:

function find(array, n, x) {
  let i = 0;
  let pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break; }}return pos;
}
Copy the code

Find the location of the variable x in an unordered array. If none is found, -1 is returned. So is this code order n in time? So let’s figure it out.

Because the variable x you’re looking for can appear anywhere in the array. If the first element in the array happens to be the variable x we’re looking for, then we don’t need to go through the remaining n-1 data, and the time is O(1). But if there is no variable x in the array, then we need to iterate through the entire array, and the time is order n. Therefore, the time complexity of this code is different in different cases.

To represent the different time complexities of code in different situations, we need to introduce three concepts: best-case time complexity, worst-case time complexity, and average-case time complexity.

The best-case time complexity is, in the best case, the time complexity of executing this code. As we just said, in the best case, the variable x we’re looking for happens to be the first element in the array, and that’s the best case time.

The worst-case time complexity is, in the worst case, the time complexity of executing this code. As in the example above, if there is no variable x in the array, we need to traverse the entire array, so the worst-case time is the worst-case time.

Average case time complexity

Best-case time complexity and worst-case time complexity correspond to extreme case code complexity, which is not very likely to happen. To better represent average case complexity, we need to introduce another concept: average case time complexity

Use the example of finding the variable x

The position of the variable x in the array can be n+1:0 to n-1 and not in the array. We add up the number of elements to be traversed in each case and divide by n+1 to get the average of the number of elements to be traversed, that is:

As we know, the big O notation of time complexity can omit the coefficient, low order and constant, so after simplifying this formula, the average time complexity is O(n).

This conclusion is correct, but the calculation is slightly wrong. What exactly is the problem? The n+1 scenarios that we just talked about, they don’t all have the same probabilities. Let me walk you through it. (There’s a little bit of probability theory here, but it’s so simple, you don’t have to worry about it.)

We know that the variable x we’re looking for is either in the array or it’s not in the array at all. It’s a little tricky to figure out what the probabilities are for both of these, but just to make it easier for you to understand, let’s assume that the probabilities of being in an array and not being in an array are 1/2. In addition, the probability that the data to be searched appears in the n positions from 0 to n-1 is the same, which is 1/n. So, according to the probability product rule, the probability that the data you are looking for will appear anywhere from 0 to n-1 is 1/(2n).

So, the biggest problem with the previous derivation is that you don’t take into account the probabilities of what happens. If we take into account the probability of each scenario, the calculation of average time complexity looks like this:This is the value in probability theoryThe weighted average is also called the expected value, so the full term for average time complexity should be calledWeighted average time complexity or expected time complexity.

After introducing the probability, the weighted average of the previous code is (3n+1)/4. In big O notation, the weighted average time complexity of this code is still O(n) after removing the coefficients and constants.

You might say, well, average time complexity analysis is really complicated, and it involves probability theory. In fact, in most cases, we do not need to distinguish between best case, worst case, and average case time complexity. Many times, as in the examples we used in the last class, we can use only one complexity to meet the requirements. We use these three complexity representations only when the time complexity of the same piece of code varies by an order of magnitude in different cases.

Amortize the time complexity

Amortized time complexity, which sounds a little bit like average time complexity, is a very confusing concept. As mentioned earlier, for the most part, we don’t need to distinguish between best, worst, and average complexity. Average complexity is only used in some special cases, whereas amortized time complexity applies to more special and limited scenarios.

Take a look at the following example:

// array represents an array of length N
 // Array. length is equal to n
 int[] array = new int[n];
 int count = 0;
 
 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }
 
    array[count] = val;
    ++count;
 }
Copy the code

Let’s explain this code first. This code implements a function to insert data into an array. When the array is full (count == array.length), we loop through the sum through the for loop, empty the array, place the sum at the top of the array, and insert the new data. But if the array has free space to begin with, the data is inserted directly into the array.

So what is the time complexity of this code? You can start with the three kinds of time complexity analysis that we just talked about.

In the best case, there’s free space in the array, and all we need to do is insert the data into the array at index count, so the best case is O(1). In the worst case, there is no free space in the array, so we need to do the sum of the array once, and then insert the data, so the worst case is order n.

So what is the average time complexity? The answer is order 1. Again, you can do it in the same way that we did in probability theory.

Assuming that the length of the array is N, depending on where the data is inserted, we can divide it into n cases, each with a time complexity of O(1). In addition, there is the “extra” case where you insert data when there is no free space in the array, which is O(n) time. And all of these n+1 scenarios have the same probability of happening, which is 1 over n+1. Therefore, according to the calculation method of weighted average, the average time complexity obtained by us is:Compare the insert() example with the previous find() example. There is a big difference.

  • The find() function is O(1) in extreme cases. But insert() is O(1) in most cases. Only in rare cases, the complexity is high, O(n). This is the first way insert() differs from find().
  • For insert() function, the frequency of O(1) and O(n) time complexity inserts is very regular, and there is a certain sequential relationship, generally an O(n) insert is followed by n-1 O(1) insert operation, cyclic.

Therefore, for the complexity analysis of such a special scenario, we do not need to find out all the input cases and the corresponding probability of occurrence, and then calculate the weighted average as mentioned in the average complexity analysis method before.

For this special scenario, we introduce a simpler analysis method: amortization analysis method. The time complexity obtained through amortization analysis is named as amortized time complexity.

How to use amortization analysis to analyze the amortization time complexity of an algorithm?

Let’s continue with the example of inserting data into an array. Each O(n) insertion operation will be followed by n-1 O(1) insertion operation, so if the operation that takes more time is amortized to the next n-1 operation that takes less time, then the amortized time complexity of this set of continuous operations is O(1). So that’s the general idea of amortized analysis.

A data structure for a set of continuous operation, the time complexity in most cases is very low, only a few cases of high time complexity and the and the coherent temporal relationship between operation, this time, we can put together a set of operations analysis, look to whether can high time complexity of the operation of time consuming, Amortized to other operations that are less time complex. Moreover, in the case where amortized time complexity analysis can be applied, the general amortized time complexity is equal to the best-case time complexity.

It can be considered that the amortized time complexity is a special average time complexity.