Shulou(Shulou.com)05/31 Report--

This article mainly explains "what are the core algorithms that web programmers must master". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "what are the core algorithms that web programmers must master"?

First, the most basic algorithm

1. Time complexity

2. Space complexity

Generally, the first contact is the study of time complexity and space complexity, these two concepts and how to calculate, must be learned, but also the first to learn, mainly the maximum complexity, average complexity and so on. You can learn directly through blog search.

II. Basic data structure

1. Linear table

List (required)

Linked list (required)

Jump table (know the principle, application, and finally implement it yourself)

And check the collection (it is recommended to learn by doing exercises)

Needless to say, linked lists, lists must be, but the focus is on linked lists.

2. Stack and queue

Stack (must learn)

Queue (required)

Priority queue, heap (required)

Multi-level feedback queue (principle and Application)

In particular, priority queues are often used when doing exercises. Queues and stacks are the most basic data structures that must be learned.

3. Hash table (required)

Collision solution: open address method, chain address method, re-hash method, establishment

Public overflow area (required)

Bloom filter (principle and Application)

4. Tree

Binary tree: all kinds of traversal (recursive and non-recursive) (required)

Huffman Tree and coding (principle and Application)

AVL tree (required)

B Tree and B + Tree (principle and Application)

Prefix tree (principle and application)

Red-black tree (principle and application)

Segment tree (principle and application)

Tree-related knowledge is still a lot, it is recommended to read a book, you can read the "fourth edition of the algorithm."

5. Array

Tree array

Matrix (required)

III. Various common algorithms

1. Ten sorting algorithms

Simple sort: insert sort, select sort, bubble sort (required)

Divide and conquer sort: quick sort, merge sort (must learn, quick sort also pay attention to the selection of the middle axis)

Allocation sort: bucket sort, cardinality sort

Tree sort: heap sort (required)

Others: count sort (required), Hill sort

For the study of the top ten algorithms, if you do not understand, then I still recommend you to read a book, because after reading a book, you may not only know how to write this algorithm, but also know how it came from. The recommended book is the fourth edition of the algorithm, which is very detailed and has a lot of illustrations, so it is easy to understand.

2. Graph theory algorithm

Representation of graphs: adjacency matrix and adjacency table

Traversal algorithm: depth search and breadth search (required)

Shortest path algorithm: Floyd,Dijkstra (required)

Minimum spanning tree algorithm: Prim,Kruskal (required)

Practical common algorithms: critical path, topological sorting (principle and application)

Bipartite graph matching: pairing, Hungarian algorithm (principle and application)

Extension: centrality algorithm, community discovery algorithm (principle and application)

The diagram is still quite difficult, but I think many of the algorithms involved in the diagram are quite practical, such as the calculation of the shortest path, and so on. I still suggest reading here, you can read the fourth edition of the algorithm.

3. Search and backtracking algorithm

Greedy algorithm (required)

Heuristic search algorithm: A* pathfinding algorithm (understanding)

Map coloring algorithm, N Queen problem, optimal processing sequence

Traveling Salesman problem

This convenience is only related to some algorithms, I think if you can, learn them all. Like the idea of greedy algorithm, you must learn it. It is recommended to do exercises to learn, leetcode direct topic brush.

4. Dynamic planning

Tree DP:01 knapsack problem

Linear DP: longest common subsequence, longest common substring

Interval DP: Matrix maximum (sum and product)

Digital DP: digital Game

State compression DP: traveling Salesman

5. Character matching algorithm

Regular expression

Pattern matching: KMP, Boyer-Moore

6. Stream correlation algorithm

Maximum flow: shortest augmented path, Dinic algorithm

Maximum flow and minimum cut: the problem of maximum profit and the number of squares

Minimum cost maximum flow: minimum cost road, pastime

Thank you for your reading, these are the contents of "what are the core algorithms that web programmers must master?" after the study of this article, I believe you have a deeper understanding of the core algorithms that web programmers must master, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.