Learning algorithms, data structures, first look at complexity correlation;

Complexity analysis (I) How to analyze and calculate the execution efficiency and resource consumption of statistics?

What is complexity analysis

  • Data structures and algorithms solve the problem of ‘how to make the computer faster, more space saving’;

  • The performance of data structure and algorithm is analyzed from two dimensions of execution time and occupied space.

  • Time complexity and space complexity are used to describe performance problems respectively.

  • Complexity describes the growth relationship between algorithm execution time (or space occupied) and data size.

Why analyze complexity?

Through statistics and monitoring, we can get the time of algorithm execution and the size of memory occupied; This is called post-hoc statistics; Have the following disadvantages;

  • The test results are very dependent on the test environment: high-end processors are faster than low-end processors
  • Test results are greatly influenced by the size of the data: efficient sorting is sometimes affected by the size of the data;

In conclusion:

1. Complexity analysis is independent of execution environment, low cost, high efficiency, easy operation and strong guidance;

2. Mastering complexity analysis, we can write codes with better performance in the development process, which is conducive to improving efficiency and reducing the cost of system development and maintenance.

Large O complexity notation

Large O time complexity actually does not represent the real execution time of the code, but the changing trend of the code execution time with the increase of data size, so it is also called progressive time complexity. Time complexity for short;

1. Age: 43

The execution time of the algorithm is proportional to the execution times of each line of code, which is expressed by T(n) = O(f(n)), where T(n) represents the total execution time of the algorithm

F (n) represents the total number of code executions per line, while N tends to represent the size of the data.

Characteristics of 2.

In the process of computational complexity, the low-order, constant and coefficient parts do not increase around the left and right, so it can be ignored, and we just record a maximum magnitude.

Time complexity analysis

  1. Focus only on the piece of code that executes the most times, which is on the order of n, the time complexity of the entire piece of code to be analyzed;
  2. The rule of addition: the total complexity is equal to the complexity of the code with the highest magnitude;
  3. The product rule: the complexity of nested code equals the product of the complexity of both inside and outside of the nested code;

In conclusion:

1. Look at high frequencies in a single piece of code: loops, for example.

2. Maximization of multiple code segments: For example, if there are single loops and multiple loops in a single code segment, the complexity of multiple loops is taken.

3. Multiply nested code: recursion, multiple loops, etc

4. Add multiple scales: For example, if the method has two parameters that control the number of cycles, then add the complexity of the two.

Several common time complexities
1.O(1)

O(1) is just a way of saying constant time complexity, not just one line of code; For example, this code, even with three lines, is O(1), not O(3):

1 int i = 8;
2 int j = 6;
3 int sum = i + j;
Copy the code

Summary: As long as there are no loops, recursive statements in the algorithm, even if there are thousands of code complexity is O(1);

(2) O (logn), O (nlogn)

Logarithmic time complexity is very common and difficult to analyze. Such as:

1 i=1;
2 while(i<=n) { 
3 	i = i * 2;
4 }
Copy the code

You can see that the 3-line code loop executes the most times; Calculate how many times the code is executed to know the time complexity of the entire code;

As you can see from the code, the value of variable I starts at 1 and is multiplied by 2 each time through the loop. When greater than n, the loop ends. Remember that geometric sequence we learned in high school? In fact, the value of variable I is a geometric sequence. If I were to list them one by one, it would look something like this:

21 * 22 * 23* 24….. 2x = n

So x = log n squared n; The complexity of this code is O(log2n);

Look at the code below

1 i=1;
2 while(i<=n) { 
3 	i = i * 3;
4 }
Copy the code

So from what we just did, we know that x is equal to log base 3n; The complexity of this code is O(logn3n);

In fact, whether it’s base 2, base 3, or base 10, we can write down all logarithmic time complexity

To O (logn);

We know that logarithms can be converted to each other, so log base 3n is log base 3n times log base 2n, so O of log base 3n is equal to O of C log base 2n, where C log base 32 is a constant. Based on one of our previous theories, we can ignore the coefficient O(Cf(n)) = O(f(n)) when adopting the complexity of large O notation. So, order log base 2n is equal to order log base 3n. Therefore, in the expression method of logarithmic order time complexity, we ignore the “base” of logarithm and uniformly express it as O(logn).

O(nlogn): According to the product rule, if the time complexity of a piece of code is O(logn), we loop n times, the time complexity becomes O(nlogn); Common n(nlogn) : merge sort, quick sort time complexity is O(nlogn)

Spatial complexity analysis

As we mentioned earlier, the full name of time complexity is asymptotic time complexity, which represents the growth relationship between the execution time of the algorithm and the size of the data. By analogy, the full name of spatial complexity is asymptotic space complexity; Represents the growth relationship between algorithm storage space and data size;

1 function print(n) {
2   let a = 0;
3  let arr:[] = new Array(a)4  for(let i = 0; i < n ; i ++) {5    arr[i]= i*i
6 }
7}
Copy the code

As with the time complexity, we can see that in 3 lines of code, we claim an array space of size N to store variable I; But this is of constant order regardless of the size of the data; So ignore; Other than that, the rest of the code takes up no more space, so the space complexity of the entire code is O(n).

Common spatial complexity is O(1), O(n), O(n2), logarithmic complexity such as O(logn), O(nlogn) is not usually used. Moreover, spatial complexity analysis is much simpler than temporal complexity analysis. So, for spatial complexity, it’s enough to know what I just said.

Common complexity levels

Polynomial order:

As the size of the data increases, the execution time and space occupied by the algorithm increases in proportion to the polynomial. Including,

O (1) (constant), O (logn) (logarithmic order), O (n) (linear), O (nlogn) (linear logarithmic order), O (n ^ 2) (flat

Square), O(n^3)(cubic)

Non-polynomial order:

With the increase of data size, the execution time and space of the algorithm increase dramatically, and the performance of this algorithm is very poor. Including,

O(2^n), O(n!) (Factorial order)

Self learning record