Part I - Chapter 1 Overview

Want to make APP Same thing as WeChat , Can run small programs smoothly ？ | Experience will send you to Xinjiang 、 Huawei 、 Cherry keyboard ！>>>

Data structure introduction

Three reasons to use data structures ： efficiency 、 abstract 、 reusability
Introduction to the algorithm ： efficiency 、 abstract 、 reusability
General method of algorithm design ： Random method 、 Divide and conquer method 、 Dynamic programming 、 The law of greed 、 Approximate method

General method of algorithm design

Random method

Random methods rely on the statistical properties of random numbers . For example, an example of applying the stochastic method is Quick sort .

Divide and conquer method

Divide and conquer contains 3 A step ： decompose 、 solve 、 Merge . An example of divide and conquer is Merge sort

Dynamic programming

Dynamic programming is similar to divide and conquer , All of them decompose the larger problem into subproblems, and finally merge the results .
The difference , In dynamic planning , The way the problem is handled is related to the relationship between the subproblems . In divide and conquer , Each subproblem is independent .
therefore , In divide and conquer, you can use recursion （ The first 3 Chapter ） The way to solve each sub problem , Then merge the results with the results of other subproblems .

The law of greed

The greedy method can always make the best choice at present when solving problems . let me put it another way , It's not about the overall optimum , And it's just a local optimal solution in a sense .

An example of a greedy approach is Huffman coding （ The first 14 Chapter ）, It's a data compression algorithm .
The most important part of Huffman coding is to build a Huffman tree （ Also known as the optimal binary tree ）.

• (1) To build a Hoffman tree , From its leaf nodes, from the bottom up . Take each compressed symbol and the number of times they appear in the data （ frequency ） Save together as the root node of the binary tree .
• (2) Next , Select two root nodes with the minimum frequency as the left and right subtree nodes , Construct a new binary tree , And the frequency value of the new binary tree root node is the sum of the frequency values of the left and right subtree nodes .
• （3） Then repeat this step , Know to get the only tree , This is the final Hoffman tree .

The root node of the Huffman tree contains the total number of symbols in the data , Leaf nodes contain the original symbols and how often they appear .
Huffman coding is a greedy algorithm , Because every time it selects the most suitable two trees to merge .

Approximate method

The approximate method does not calculate the optimal solution , contrary , It only calculates “ Good enough. ” Solution . The approximate method is usually used to solve the problems that are expensive to calculate and unwilling to give up because of its value .

Salesman problem ( The first 16 Chapter ) It's a problem that is usually solved by approximation .