“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 front-end 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 three-level 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 = n-1, 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… (2n-1), the general formula of the arithmetic sequence S(n) is: S(n) = S1 + (n-1) * 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 levelO(1)
• Logarithmic,O(log n)
• Linear levelO(n)
• Linear logarithmic orderO(n*log n)
• Square levelO(n^2)
• Cubic levelO(n^3)
• K to the power levelO(n^k)
• exponentialO(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