Case Analysis of time and Space complexity of JavaScript

This article mainly explains the "JavaScript time and space complexity case analysis", the content of the article is simple and clear, easy to learn and understand, now please follow the editor's ideas slowly in depth, together to study and learn "JavaScript time and space complexity case analysis" bar!

1. What is complexity analysis?

The data structure and algorithm solution is "how to make the computer solve the problem with faster time and more space".

Therefore, it is necessary to evaluate the performance of the data structure and algorithm from the two dimensions of execution time and occupied space.

Time complexity and space complexity are used to describe performance problems, which are collectively referred to as complexity.

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

two。 Why do you need a complexity analysis?

Compared with performance testing, complexity analysis has the characteristics of independent of execution environment, low cost, high efficiency, easy operation and strong guidance.

If you master the complexity analysis, you will be able to write code with better performance, which will help to reduce the cost of system development and maintenance.

3. How to carry out complexity analysis?

3.1 Big O representation

The execution time of the algorithm is proportional to the number of execution times per line of code, 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 times per line of code execution, and n often represents the size of the data. This is the large O time complexity representation.

3.2 time complexity

1) definition

The time complexity of the algorithm is the time measure of the algorithm.

The large O time complexity representation actually does not specifically represent the real execution time of the code, but represents the changing trend of the code execution time with the increase of data size, so it is also called progressive time complexity, referred to as time complexity (asymptotic time complexity).

Example 1:

Function aFun () {

Console.log ("Hello, World!"); / / needs to be executed once

Return 0; / / needs to be executed once

}

Then this method needs to perform two operations.

Example 2:

Function bFun (n) {

For (let I = 0; I < n; iTunes +) {/ / needs to be executed (n + 1) times

Console.log ("Hello, World!"); / / needs to be executed n times

}

Return 0; / / needs to be executed once

}

Then this method needs to perform (n + 1 + n + 1) = 2n + 2 operations.

Example 3:

Function cal (n) {

Let sum = 0; / / 1 time

Let I = 1; / / 1 time

Let j = 1; / / 1 time

For (; I)