"Algorithms and Data Structures" time and space complexity
Writing in the front
Some people may ridicule, what is the use of learning algorithms, at most is to go to the interview of the factory can be used, factory interview algorithm is just a stepping stone in the strong screen, I do not go to the factory, do not have to learn it, is it really so?
Certainly not in the computer industry development, whether the front or the back end, algorithm is advanced a stumbling block, can say not algorithm will never be a qualified senior engineer, want to into the giant will do some algorithm, but it is not just for the interview, it is closely linked with us, some people say that the frontend algorithm does not need? Where do you put the famous Virtual DOM? It is an embodiment of algorithms and data structures. Some people may say, I don't write Virtual DOM. Well, you want to make money, and if you want to make money in technology, algorithms are the cornerstone
Online articles, and there are a lot of algorithm program, said seven days to learn algorithm data structure, control algorithms and data structures, and so on and so on in 30 days, don't be silly, there is no shortcut to algorithm, can only rely on our accumulated bit by bit, first you need to do is to believe in yourself not a genius, followed by the brush every day, time tight can brush a week four or five questions, best rate is a topic every day, Later, if you have enough time or are skilled, you can even brush several questions a day. Even very smart people will forget the algorithm after a period of time, so it is important to keep going
Next let's started learning algorithm, and if you never brush algorithm, this article will take you to see what is algorithm, what is a data structure, at the same time, the arithmetic of brush good enough, we want to know your method and quality solution will be judged by two dimensions of time and space to reflect, this article will focus on, Before these are brush algorithm needs the necessary knowledge, if the road to your algorithm can bring enlightenment, that's awesome, my pleasure, if you already know about these knowledge, so might as well fast reading, see if it can do for your algorithm knowledge expansion, of course, if have a wrong place, you can also guide for me, is my pleasure
What is a data structure
Data structure is actually the way that the program stores organizational data. A data structure is organized by the data elements in the program according to certain logical relations, and is a combination of several data elements
Data structure is the basic unit of data processing in the program, used as a whole in the program
For example, A number 1 or A character A is A data structure
For example, a date, December 14, 2020, consists of three formats: year, month and day. It is also a data structure
For example, an array [1, 'a', 'December 14, 2020 '], which is a combination of numbers, characters, and date formats, is also a data structure
Popular, with a certain format of data is the data structure, we compare the common data structures are strings, arrays, objects, heap, stack, linked lists, trees, hash table, etc., you may to some of the data structure do not understand, don't worry, you don't need to immediately know what they are, for the front, JavaScript, the language we love and hate, has very few existing data structures, so it's important to know that structures like linked lists, trees, and so on are modeled by objects
Among many program design, the choice of data structure is a basic design considerations, the difficulty of system implementation and system structure are heavily dependent on the quality of whether to choose the optimal data structure, choose the optimal data structure can effectively improve the efficiency of running and managing the use of storage space, but you know, there is no perfect data structures, Each data structure has limitations as well as advantages. Choose the right data structure according to your requirements
What is an algorithm
What is an algorithm? We all know that 1 plus 2 plus 3 is 6, why is it 6? You might say, well, 1 plus 2 is 3, two 3's add up to 6, that's elementary school math, it's an algorithm in general, right
An algorithm is actually a complete step description to solve a problem, which is an accurate and complete step description to complete a task
The design of algorithms often depends on the data structure, and the implementation of algorithms depends more on the data structure adopted
The algorithm to propose a problem is a process from abstract to concrete

Analyze the problem, select the data structure, get the preliminary solution

Break the solution down into manageable steps

Choose reasonable loop variables for repeated steps

The algorithm is described concisely in natural language that is easily translated into program implementation
So once we know what an algorithm is, we look at time and space complexity, and we measure how good or bad an algorithm is and we usually look at it in two dimensions, right
 Time dimension: Refers to the time taken to execute the code, namely time complexity
 Spatial dimension: Refers to the space consumed by executing code, namely spatial complexity
Let's start with time and space complexity step by step
Time complexity
Before we talk about time complexity, we need to understand the concept of the number of code executions, also known as statement frequency or time frequency, which is called T(n)
Let's do it step by step with an example, but first let's look at the function fn1
function fn1(){
console.log("At the end of the sentence")
console.log("isboyjc")}Copy the code
Let's see how many times the statement in this function is executed
Log (" end of sentence ") and console.log("isboyjc"), so we say that the code inside this function is executed 2 times
Let's look at the function fn2
function fn2(n){
for(let i = 0; i n; i++){
console.log("At the end of the sentence")}}Copy the code
Let's start by looking at how many executable statements there are in function fn2
let i = 0
i n
i++
console.log("At the end of the sentence")
Copy the code
Let's say n is equal to 3, and then we plug it in and see how many times each execution is executed
Let I = 0 This statement is executed only once on the first time the for loop is declared
I n The number of times the statement is executed varies according to the size of parameter n. If n =3, the statement is executed when I =0, I =1, I =2, and I =3. That is, the statement is executed for n + 1 times
I ++ The number of times the statement is executed depends on the size of the parameter n. When n = 3, I =0, I =1, and I =2, n times
Console. log(" end of sentence ") this statement will be executed n times within the function again depending on the size of parameter n, n = 3 will be executed 3 times
1 + (n + 1) + n + n = (3n + 2)
Copy the code
So 3n + 2 times in fn2
The total number of executions of a piece of code is usually expressed by T(n), so the total number of executions of a call to the above two functions fn1/fn2 is
T(n) = 2 // fn1
T(n) = 3n + 2 // fn2
Copy the code
The n above refers to the size of the problem, the size or quantity of input data, or you can simply say that T is the function itself, and n is the parameter, which means that
The function fn1 is executed 2 times in any case
The total number of executions of the function fn2 will vary depending on the size of n
Let's think about it. Can we measure execution speed by the total number of times a piece of code is executed?
The answer, of course, is no, because when we have a lot of lines of code, it's too cumbersome to count the total number of times we execute it one by one, such as when we use a function in a function, or when we use a loop in a loop, to try to count exactly how many times we execute it
Therefore, in the algorithm, we generally use the simplified estimated value of T(n) to express the code execution speed. Usually, we use the big letter O to express the code execution speed, that is, the big O notation. Since it is estimation, it represents the change trend of the code execution time with the increase of the data scale. Also called a class of asymptotic time complexity
With this concept in mind, we can now calculate time complexity using the fn1/fn2 example above
// fn1
T(n) = 2
// fn2
T(n) = 3n + 2
Copy the code
First, let's look at the function fn1, whose total number of executions is 2, a constant (constant level), that is to say, the total number of executions of this function is 2 at any time, which is a constant value, so we can use the time complexity O to express it and directly estimate it as 1, that is, the time complexity is O(1).
If we look at the function fn2, the number of times T(n) is 3n + 2, which is constant *n + constant, we can view it as constant *n and constant +, and as n increases, only the former part changes, the latter part stays the same, Therefore, in the expression of time complexity, we can ignore the following constant, that is constant *n, and the constant in constant *n can be directly regarded as 1, or ignore the constant as the coefficient, then we can finally get the time complexity of function fn2 is n, that is O(n).
PS: I know someone might have given math back to the teacher, so explain
Constant: a constant is an ordinary value, which can be simply understood as a fixed value
Coefficient: the coefficient refers to the number factor of an algebraic monomial. For example, if a = 1 * A, its coefficient is 1, 2 and b = 2 * b, its coefficient is 2
Let's take another example, for example, let's substitute the polynomial T(n) of a function, find its time complexity
T(n) = 10n^4 + 100n^2 + 1000
Copy the code
In fact, for polynomials, we just keep the highest degree term, that is, n to the highest power, which in this case is n to the fourth power, and we ignore the coefficients and the constants, and we get O(n^4).
Conclusion:
When T(n) is constant, the time complexity is O(1), and vice versa (keep the highest degree term of T(n) and remove the coefficient of the highest degree term).
Next, let's look at a few examples to determine the time complexity of several pieces of code
Case 1:
function fn01(){
console.log("Look what this is.")
console.log("This is an output.")
console.log("Ha ha ha.")
let a = 1
return a
}
Copy the code
The above function Fn01 has only one statement, which is executed for 5 times without any change. The time complexity is O(1), which is a constant time complexity
Example 2:
function fn02(n){
for(let i = 0; i n; i++){
console.log("This is an output ?")}}Copy the code
As mentioned above, the function fn02 is the same as the previous example fn2, and the time complexity is O(n), which is the linear time complexity
Example 3:
function fn03(n){
for(let i = 0; i n; i++){
console.log("Outer cycle")
for(let j = 0; j n; j++){
console.log("Inner circulation")}}}Copy the code
If we look at the inner loop, the inner loop will execute approximately n times, and then the outer loop will execute approximately n times, which is n times n = n^2, so the time of fn03 is O(n^2), which is the square time of fn03, If it's a threelevel cycle it's O(n^3), cubed time
From this we can see that the time complexity of a piece of code is n to the power of the number of loops, so try to avoid nested layers of loops
Example 4:
So let's look at the function fn04
function fn04(n){
for(let i = 0; i n; i++){
console.log("Outer cycle")
for(let j = 0; j n; j++){
console.log("Inner circulation")}}for(let i = 0; i n; i++){
console.log("Ha ha ha.")}}Copy the code
This function has a double loop and a single loop, that is, approximately n^2 + n, and the time complexity of fn04 is O(n^2) according to what we said above.
Example 5:
It's definitely not just the usual loop up here, but let's look at the next one
function fn05(n){
for(let i = 0; i n; i++){
console.log("Outer cycle")
for(let j = i; j n; j++){
console.log("Inner circulation")}}}Copy the code
In fact, when this happens, let's just go in and try it out and see how it works
When I = 0, the inner loop will execute n times
When I = 1, the inner loop will execute n  1 times
When I = 2, the inner loop will execute n  2 times
When I = 3, the inner loop will execute n  3 times
And then we see the pattern, every time I increases by 1, the inner loop gets executed one less time, so it's easy
When I = n  2, the inner loop is executed twice
When I = n1, the inner loop will execute once
Finally, we add up the execution times of n inner loops to get an imprecise total execution times
T(n) = n + (n  1) + (n  2) +... +3 + 2 + 1
Copy the code
As above, this is an arithmetic sequence that, well, I know, will complement
A sequence is called an arithmetic sequence if, starting from the second term, the difference between each term and its predecessor is equal to the same constant, and this constant is called the tolerance of the arithmetic sequence, which is often denoted by the letter D
For example: 1,3,5,7,9... (2n1), the general formula of the arithmetic sequence S(n) is: S(n) = S1 + (n1) * d, and the formula of the first n terms is as follows
S(n) = n*S1 + n*(n  1)*d/2
/ / or
S(n) = n*(S1 + Sn)/2
Copy the code
So we get the result, in our above sequence, the tolerance d is 1, we just plug it into the formula, the second formula is easy, use the second one, the result is the same
// n*(S1 + Sn)/2
n*(n + 1) /2 = (n^2 + n)/2 = (1/2)n^2 + (1/2)n
Copy the code
In the end, we get (1/2)n^2 + (1/2)n, taking the highest order term as above and removing the coefficient, i.e., the time complexity is O(n^2).
Example 6:
Let's do another example
function fn06(n){
for(let i = 1; i n; i *= 2) {console.log("isboyjc")}}Copy the code
So again, if you don't know how to look at it, you can just plug in a couple of parameters and try it out, and see what the pattern is, right
We can use n=2, n=4, n=8, n=16, and observe the number of prints in the loop, or you can just run the code, but I won't go into that, so let's see what happens
n=2When printing1T (n) =1
n=4When printing2T (n) =2
n=8When printing3T (n) =3
n=16When printing4T (n) =4
Copy the code
For the execution times, the main image is generated in the loop statement I *=2, and each time the loop I will become twice itself. After careful observation, we can get such a regular result
n=2When printing1T (n) =1 / / 2 ^ 1 = 2
n=4When printing2T (n) =2 / / 2 ^ 2 = 4
n=8When printing3T (n) =3 / / 2 ^ 3 = 8
n=16When printing4T (n) =4 / / 2 ^ 4 = 16
Copy the code
So we can see from this, that 2 to the power is equal to n, which is 2 to the T of n is equal to n, so let's take T of n, just change it, which is log base 2 of n, which is T of n is equal to log base 2 of n
PS: It's math again
Log: If a to the n is equal to b, that is, a to the n is equal to b, and we want to evaluate n, then we can write log_a b for convenience, that is, log base A of b, where a is the base, b is the real number, and n is the log
You might be wondering why you're just looking at the number of prints in a loop and not counting all The Times it's executed, because as I said above, these intrinsic constants and coefficients are completely negligible. Okay, let's push this one last time, okay
Let I = 1 execute log_2 n + 1, I *=2 execute log_2 n + 1, I *=2 execute log_2 n, Minus the coefficient 3 and the constant 2, we get log 2 n, and the base of log can be omitted in the calculation of time complexity, so the final function Fn06 is order log n, which is logarithmic time complexity
Example 7:
Let me give you an example at the end
function fn07(n,m){
for(let i = 0; i n; i++){
while(j m){
console.log("Do you understand?")
j = j * 2}}}Copy the code
As shown in the figure above, this function takes two arguments that correspond to the inner and outer loops. Let's start with the inner loop. Does this look familiar? In fact, the inner loop is the same as the loop in fn06, except for one for and one while, and we won't talk about the time complexity in the last problem, so the inner loop is order log n.
Let's look at the outer loop, which is also explained above, and just look at the outer loop time is order n.
So the time complexity of fn07 is order (n*log n), which is the linear logarithmic time complexity
That's the output of the function. Do you see that?
Code word too tired, look at a picture:
I found a web map (intrusion and deletion) and used the chart to more clearly show the common time complexity curve
As shown in the figure above, the abscissa is n. It can be seen that the number of operations or execution time of different time complexity increases with the increase of n
Common time complexity orders are
 Constant level
O(1)
 Logarithmic,
O(log n)
 Linear level
O(n)
 Linear logarithmic order
O(n*log n)
 Square level
O(n^2)
 Cubic level
O(n^3)
 K to the power level
O(n^k)
 exponential
O(2^n)
From top to bottom, the time complexity is increasing and the execution efficiency is decreasing. Most of the commonly used ones are shown in the diagram above
Therefore, we should try to use low time complexity methods in programs or brush problems
So far as time complexity is concerned, we've also listed common time complexity, and now we'll look at space complexity
Spatial complexity
Spatial complexity is actually a way of expressing the storage space occupied by an algorithm or a piece of code during its running
We talked about time complexity, so it's a lot easier to talk about space complexity
The space complexity is S(n), and it will also be expressed in big O notation, so let's just do the example
Case 1:
function fn001(n){
for(let i = 0; i n; i++){
console.log("Spatial complexity")}}Copy the code
First of all, we know that the space complexity is related to the storage space, and the storage space is determined by something, it must be the declared variable, so let's go directly to the variable declaration in the function Fn001, there is only one I, which means that the function only opens up a space for I, so the space complexity of S(n) is O(1), You might say isn't I changing all the time, yes it is, but no matter how it changes, it's still a number, it takes up the same amount of space
The space complexity is the same as the time complexity, when the variable declared in the code is a constant, does not change according to the incoming value, then also its space complexity is O(1).
Example 2:
function fn002(n){
let arr = []
while(n){
arr.push(n)
}
}
Copy the code
So in this example we're declaring an array, and we know that arrays can hold all kinds of types, and in the loop, we're pushing elements into the array ARR based on the size of n, so as big as n is, the array has as many elements as it takes up, so the space complexity S(n) = O(n).
Summary of space complexity
In the case of space complexity, I've only listed two examples, because in general, we don't need the other ones, the space complexity is usually O(1)/O(n)/O(n^2), and the other ones are rare, but there are some, and it's easy to analyze space complexity once we know the time complexity, so I won't go into more details
In terms of analyzing spatial complexity, we can actually just start with the variables that are declared, and look at the variables that are declared in the body of a function and look at how they change depending on the values that are passed in
In addition, we have no enumerating recursive here, please note that recursion is the function of function, like Russian dolls, among which there are a problem, as we know, recursive functions, each layer in the recursive will open up a recursive stack, such as variable each recursive recursive stack space consumption will exist, it is also a space, whether have you declare variables, It exists as long as the stack recurses, which means as long as there is recursion, basically the least space complexity is O(n), so we don't use recursion as much as we can use iteration
Time vs. Space
We said in the beginning, to evaluate the efficiency of an algorithm, we mainly from the two dimensions of time and space, however, usually in our algorithm, time and space is the relationship between the fish and bear's paw, this time may have two kinds of solution, an algorithm is a kind of low time complexity, but the space complexity is a bit high, the other and vice
What to do at this point? Fine goods, in development, we are generally better than that of space time, you want to ah, a program that users don't care how much memory occupied, but he will care about you when he used the execution speed of this program, moreover, space, that is, disk, disk at this stage we can spend capacity, time is not so simple, so some relative cases, Space for time is acceptable
Although space for time is feasible, space for time cannot be blindly changed. We still need to reduce the complexity of the two dimensions as much as possible. In a few cases of opposition, space for time can be changed
When we brush the algorithm, we are not finished. We also need to analyze the time and space complexity of our problem solutions. We can analyze the complexity of various problem solutions and find the optimal solution by comparison
In the interview, if the interviewer to give you an algorithm, when you know several solutions, can be very loaded B asked, do you like time first or space first, I can solve, Ollie to, finish he will let you write ?
Just kidding, try to write as many solutions as possible during the interview and explain to the interviewer the different time and space complexity of each solution. It is great
The last
This article introduces some theoretical basis of the algorithm, after understanding you can brush the questions, it is recommended to brush a question every day according to the type of data structure
It is recommended that you brush the problem when you are bored at work. It is better to brush the algorithm when you touch the fish and water group at work. There is no harm in it
GitHub algorithm repository, using JavaScript to solve ing from zero algorithm questions/text/video questions, to pay attention to ? GitHub portal
This article and later brush each question has a video version, mainly in order to tell the idea of a handwritten, speak may not be good, see ? B station portal
See here, to a three even bar, if there is a mistake please correct, also welcome everyone to pay attention to the public number "not serious front end", and algorithm group of friends brush algorithm, more efficient