This paper is the study note of Teacher Qin Chao’s Algorithm Training Camp, which includes personal record, personal summary, understanding and thoughts after learning. So a better learning algorithm.

preface

When learning any knowledge, we need to analyze clearly what the core of the knowledge is, so that we can get what in the core. If we blindly absorb knowledge, in fact, a lot of knowledge we are in the current scene, work, life can not use. It is also because we cannot use it after learning, so we forget it quickly, or give up easily in the process of learning.

In the course of a lifetime of learning, we find that learning what we urgently need to use or what can bring us value in a timely manner will help us learn more firmly and more consistently.

What is the core of learning Data Structures and Algorithms? And what do we get?

  1. Understand the underlying logic of programming;
  2. In the process of programming, have A Doraemon like 100 treasure tool bag;
  3. When encountering performance problems, there are algorithmic thinking logic and rules to solve the problem;
  4. Improve programming thinking;

This note documents the core temporal and spatial complexity of algorithms around which data Structures and Algorithms are developed. Its existence is also to solve our performance problems in the process of programming, but also let us have more advanced thinking and ideas, write better programs.

Complexity indicator Big O Notation

  • O (1): indicates the Constant Complexity – Constant Complexity
  • Dsmt4 (LOG N): Logarithmic Complexity
  • O (n): indicates the Linear Complexity
  • O (n^2): square Complexity -n Square Complexity
  • O (2^n): Exponential – Exponential Growth
  • O (n!) : Factorial – Factorial

How do you look at time complexity

  • Analysis function;
  • How many times does it run depending on n;
  • Finally, an average number of runs is obtained;

Complexity example

O (1) – constant complexity

let n = 1000;
console.log("Hello - your input is: " + n)
Copy the code

O (N) – Linear complexity

for (let i = 1; i <= n; i++) {
  console.log("Hello world - your input is: " + i)
}
Copy the code

O (N^2)

for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n; j++) {
  	console.log("Hello world - your input is: " + i + " and " + j)
  }
}
Copy the code

What if instead of nesting two for loops, we store them separately? What is the time complexity?

for (let i = 1; i <= n; i++) {
  console.log("Hello world - your i input is: " + i)
}

for (let j = 1; j <= n; j++) {
  console.log("Hello world - your j input is: " + j)
}
Copy the code

As many of you might have guessed, it’s 2 times n, which is order 2n. It’s actually order n time.

O(log(n))

for (let i = 1; i < n; i = i * 2) {
  console.log("Hello world - your input is: " + i);
}
Copy the code

O(k^n)

/ / the Fibonacci recursion
function fib (n) {
  if (n <= 2) return n;
  return fib(n- 1) + fib(n2 -);
}
Copy the code

Time complexity curve

  • yAxis isOperationsIt’s an exponential of operation complexity;
  • xAxis isElementsisnOur number of cycles;
  • Here we can see in thenWhen it’s small, the complexity is relatively stable;
  • But whennAs you get bigger and bigger, big-O complexity skyrockets;

So when we write programs, if we can reduce the time and space complexity from O(n^2) to O(n) or O(1), the optimization benefits are very high!

  • Be sure to write with time and space complexity in mind so that you can predict the performance level of the code;
  • Complete this procedure with the simplest time and space complexity;
  • That’s the top professional coder;
  • Because the higher the complexity, the more time (processing time) and resources (memory) the program consumes;

Reduce time and space complexity

Here’s an example of how to reduce complexity in programming:

Calculation: 1 + 2 + 3 +… + n

Method 1: Loop 1 to n and add (time complexity O(n))

let sum = 0
for (let i = 1; i < n; i++) {
  sum += i
}
console.log(sum)
Copy the code

Method 2: Sum formula = n(n+1)/2 (time complexity O(1))

let sum = n * (n + 1) / 2
console.log(sum)
Copy the code

Note:

  1. Before you do a problem set or interviewConfirm the topicTo ensure that all conditions and topics are understood correctly;
  2. Come up with all the possibilitiesSolutions;
  3. At the same timeCompare each methodTime and space complexity;
  4. The followingTo find the optimalSolution (fastest time, least memory usage)

Judge time and space complexity

The Fibonacci example

Formula: F(n) = F(n-1) + F(n-2)

We can use recursion directly to solve the problem:

function fib(n) {
  if (n <= 2) return n
  return fib(n - 1) + fib(n - 2)}Copy the code
  • thisfibOne of the Fibonacci functionsrecursive;
  • One at a timenValue, will loop recursivelyfibMethod to calculate layer by layer down;
  • We finally reachednLess than 2, return the lastnValue;

So how do we calculate the time of this recurrence?

  • To deduce the procedureThe complexity of theFirst we need to know exactly what the program is doing in this function;
  • Our distance is now incomingnfor6That’s runningfib(6)
  • At this time6Passed into this method, and returned isfib(5)+fib(4), at this momentfib(5)andfib(4)I’m going to re-enterfibDelta function, there are two branches here. By analogy, the following tree-like process appears:

  • From the expanded tree above, we can see that each layer is twice as large as the previous one:fib(6)Begin tofib(5)+fib(4)And thenfib(5)andfib(4)Two more unfold.
  • sofibonacciThe number of times that you execute it is oneExponential order -o (2^n)
  • We can see that here as wellfib(3),fib(4)Wait, it’s all been counted over and over again, so this isIt’s two to the sixth;
  • So instead of using the code examples above for problems and interviews, we need to add a caching mechanism to cache the results of repeated calculations or write them in a loop to reduce the complexity of the program.

Master Theorem

Any divide-and-conquer or recursive function can use this theorem to calculate its time complexity. There are four of the most common ones in this theorem, just remember those four.

Algorithm (Algorithem) Run time
Binary search O(log n)
Binary tree traversal O(n)
Optimal sorted matrix search O(n)
Merge sort O(n log n)

Frequently seen exam

  • Pre-order, middle-order, post-order in binary tree traversal: What is the time complexity?
    • The time complexity isO(n), each node is accessed once and only once, whether it is pre-ordered, mid-ordered or post-ordered.
    • So it’s the total number of nodes in the binary tree, which is equal toO(n)Linear time complexity;
  • Graph traversal: What is the time complexity?
    • Time is complicated as wellO(n)Here,nThat’s the total number of nodes in the graph;
  • Search algorithm: DFS, BFS time complexity?
    • DFS is depth-first and BFS is breadth-first.
    • Either depth-first or breadth-first, because the nodes are accessed only once, so is the time complexityO(n). (nThe total number of nodes in the search space.
  • Binary search: What is the time complexity?
    • The answer isO(log n)

conclusion

  • Program complexity: Big O Notation
    • O(1), O(log n), O(n), O(n^2),… And so on, the more complex the program the worse performance;
    • Analyzing the law of complexity: Analyzing the logic of the code to find the number of times the program is run;
    • Reducing program time and space complexity can improve code quality and optimize program performance.
  • The main theorem:
    • The time complexity of all didivide and conquer or recursive functions can be analyzed by the master theorem.
  • Often meet try:
    • Pre-order, middle-order, post-order in binary tree traversal: What is the time complexity? – O(n)
    • Graph traversal: What is the time complexity? – O(n)
    • Search algorithm: DFS, BFS time complexity? – O(n)
    • Binary search: What is the time complexity? – O(log n)

I am three diamonds, one in the galaxy of technology waiting for you to come together for a lifetime of wandering learning. Praise is power, attention is recognition, comment is love! See you next time 👋!

series

  • 📖 how to efficiently learn data structure and algorithm “three drill algorithm learning Notes” — to today, if you want to become a senior development engineer or enter a large factory, no matter the post is front end, back end or AI, algorithm is the most important. It doesn’t matter whether the position we need to enter the company ends up as an algorithm engineer.