Complexity summary

This paper has participated inProject DigginTo win the creative gift package and challenge the creative incentive money.

Basic concept

  • Time complexity: The time taken to execute the current algorithm
  • Space complexity: How much memory is required to perform the current algorithm

Why is complexity analysis needed

Console.time () and console.timeend () are often added to the header and tail of a piece of code, and then we can see the time and memory footprint of the algorithm through statistics and monitoring. Why do we need to do time and space complexity analysis?

First of all, the above method, in some ways, is not a problem, is the correct way to evaluate the efficiency of the algorithm, we can call it post-hoc statistical method, but it has some limitations.

1. Test results are highly dependent on the test environment

That is, different hardware conditions, the same string of code under different hardware execution results must be different

2. Test results are greatly influenced by data size

In other words, if we do not deliberately construct too large a data scale in the general test, the test results may not really reflect the performance of the algorithm

Time complexity analysis

1. Focus only on the piece of code that loops the most

The number of loops is the length of the ARR, and the total number of loops increases as the length of the ARR increases

function sum(arr) {
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
        sum += arr[i];
    }
    return sum;
}
Copy the code

So the above code can be expressed as O(n) time complexity

2. The total complexity is equal to the complexity of the code with the highest magnitude

Here is a three-part loop that evaluates sum, sum1, sum2, and returns the sum of the three values

function sum(arr) {
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
        sum += arr[i];
    }
    
    let sum1 = 0;
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) { sum1 = sum1 + arr[i] + arr[j]; }}let sum2 = 0;
    for (let k = 0; k < 100; k++) {
        sum2 += k;
    }
    return sum + sum1 + sum2;
}
Copy the code

The first loop time complexity is O(n), which increases with the length of the ARR, the second loop time complexity is O(n2), the third loop time complexity is O(1) because it is executed 100 times, independent of the size of n, so the last code time complexity is O(n2).

3. The complexity of nested code is equal to the product of the complexity of both inside and outside the nested code

This is already shown in the code above, the second loop, because there is a loop on the outside and a loop on the inside, so the time is O(n) times O(n) = O(n2).

Common time complexity

  • O(1)
  • O(logn)
  • O(n)
  • O(nlogn)
  • O(n2)

The one that’s a little bit harder to understand is logn, so let’s look at this code right here

function sum (arr) {
    let i = 1;
    let sum = 0;
    while(i < arr.length) {
        sum += arr[i];
        i = i * 2;
    }
    return sum;
}
Copy the code

It’s easy to see that every time we do a while loop, we multiply I by 2, so we just need to know how many times this line of code is executed to know the time complexity of the entire code

As you can see from the above, each loop is multiplied by 2, and when it is greater than n, the loop stops, so I is a geometric sequence, and at the end of the loop 2x is greater than = n, where n is the length of the array, so x can easily be calculated as x = log2n, So the time of this code is log base 2n

Now let’s change the above code

function sum (arr) {
    let i = 1;
    let sum = 0;
    while(i < arr.length) {
        sum += arr[i];
        i = i * 3;
    }
    return sum;
}
Copy the code

We can quickly figure out that the time complexity of the above code is x = log3n

In fact, whether it’s base 2, base 3, or some other number, we can write all logarithmic time as order logn. Why is that?

We know that logarithms can be converted to each other, so for example, if you want to convert log of 3n to log of 2n, you just write log of 32 times log of 2n, where the front is a constant, so we can ignore the coefficients, so in the logarithmic time complexity notation, we ignore the base of the logarithm, This is uniformly expressed as order logn.

If you understand where O(logn) comes from, then O(nlogn) is easy to understand, which is that the time complexity of a piece of code is O(logn), which happens to loop n times, and the final time complexity is O(nlogn), with an asymptotic diagram of the time complexity

Spatial complexity analysis

The time complexity mentioned above actually represents the increasing relationship between the time of algorithm execution and the size of data

Similarly, space complexity represents the growth relationship between the algorithm’s storage space and data size

function print(n)  {
    let i = 0;
    let a = [];
    for (i = 0; i < n; i++) {
        a[i] = i * i;
    }
    
    for (i = n - 1; i >= 0; i--) {
        console.log(a[i])
    }
}
Copy the code

The second line of the above code declares a variable I, but it is constant, so it has no relation to the size of the data. The third line of the above code applies for an array. As we can see from the following loop, the size of the array grows linearly according to the size of the data n, so the space complexity of the whole code is O(n).

The kind of spatial complexity we use is O(1) O(n) O(n2), and we don’t see anything like logarithmic complexity

Best, worst, average time complexity

Of course, in some textbooks, there will also be the above four time complexity analysis, if the calculation of time complexity method summarized above, it is very good to analyze the time complexity of each code

function find(arr, x) {
    let index = -1;
    for (let i = 0; i < arr.length; i++) {
        if(arr[i] === x) { index = i; }}return index;
}
Copy the code

The above code is actually used to find the index of x in the arR array, if not, return -1, so the time complexity above is O(n).

However, some experienced friends may ask the question, why do we continue to search when we can directly return index when we find the location of X? Therefore, this code is not efficient enough, which is great. You have considered the efficiency of code execution while writing the code, so let’s optimize it next

function find(arr, x) {
    let index = -1;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === x) {
            index = i;
            returnindex; }}return index;
}
Copy the code

Now, the question is, is it still O(n) in time after optimization?

Because this time x may appear in any position of the arr, if just the first element is x, then the time complexity is O (1), if the arr does not exist in the variable x, then you need to traverse the entire array, this time the time complexity is O (n), so in different circumstances, the time complexity of the code is not the same

In order to represent the different time complexity of code in different cases, we have the best case time complexity, worst case time complexity, and average case time complexity above

Best-case time complexity: In the best case, the time complexity of executing this code

Worst case time complexity: In the worst case, the time complexity of executing this code

Average Case Time complexity: Weighted average (expected value) from Probability Theory

Or use the above code, for example, to explain what is the average time complexity, the above said to involve in mathematics or expectations in the probability theory, you can probably associate it, you will first need to find the variable x position in the array, there are n + 1, which is in an array of 0 ~ n – 1 and not in the array. First of all, from the perspective of probability theory, the probability that the variable is in the array and the probability that it is not in the array is 1/2, and the probability that the variable is in the position 0 to n-1 is also 1/n, so the probability that the data we are looking for is anywhere from 0 to n-1 is 1/2 N

So the calculation becomes


1 ∗ 1 / 2 n + 2 ∗ 1 / 2 n + . . . + n ∗ 1 / 2 n + n ∗ 1 / 2 = ( 3 n + 1 ) / 4 1 * 1/2n + 2 * 1/2n + … + n * 1/2n + n * 1/2 = (3n + 1)/4

The parameter on the left represents where the variable X may appear in the array, and the last parameter represents where the variable is not in the array and has covered the entire length of the array. The result is still O(n) after removing the coefficients and constants.

Some of you might say, well, what’s the point of doing this, and yes, in many cases we don’t need to do this, but there’s an order of magnitude difference in the time complexity of the same piece of code in different cases, so we’re going to use these three different time complexities

Time and space complexity trade-off

Space for time: In many cases, we will have some performance bottlenecks in the process of development problems, for example, our performance can not meet the requirements of an interface 100 ms, then need to consider whether we can through the way of trading space for time to improve the interface processing speed, this often applies to some time and speed is more important and more space, Load balancing, for example, improves user experience by using multiple servers (space) in exchange for reduced latency (time)

Time for space: There is another case of time for space, which is usually used to run some planned tasks more, there is no major time problem, just need to finish the last run to tell us that the execution is complete, its starting point is memory and storage space resources we need to reduce occupation.

Of course, if the above two conditions need to be guaranteed, we need to adopt more advanced algorithms and data structures, using caching and other technologies to meet our requirements