What are the core algorithms a programmer must know?

First, the most basic algorithm

1. Time complexity

2. Spatial complexity

Generally, the first contact is time complexity and space complexity learning, these two concepts and how to calculate, is a must learn, but also must learn first, mainly has the maximum complexity, average complexity, etc., directly through the blog search to learn.

2. Basic data structure

1. Linear tables

List (Required)

Linked lists (Required)

Skip list (know the principle, application, and finally implement it by yourself)

And look up the set.

Needless to say, linked lists, lists must, but the point is linked lists.

2. Stacks and queues

Stack (required)

Queues (Required)

Priority queue, heap (required)

Multi-level feedback queue (Principle and Application)

Queue and stack are the most basic data structures.

3, Hash table (must learn)

Collision solution: open address, chain address, hash again, build

Public Overflow Area (Required)

Bloom filter (Principle and Application)

4, trees,

Binary trees: Various traversals (recursive and non-recursive) (Required)

Huffman Tree and Coding (Principles and Applications)

AVL tree (Required)

B tree and B+ Tree (Principle and Application)

Prefix Trees (Principles and Applications)

Red-black tree (Principle and Application)

Line Segment Tree (Principles and Applications)

Tree related knowledge is still a lot of, suggest reading, you can see “algorithm fourth edition”.

5, arrays,

Tree array

Matrices (required)

Three, various common algorithms

1. Ten sorting algorithms

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

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

Allocation sort: bucket sort, radix sort

Tree sort: heap sort (required)

Others: counting sort (required), Hill sort

For the learning of ten algorithms, if you do not understand, then I still quite recommend you to read a book, because after reading the book, you may not only know how to write this algorithm, but also know how he came. The recommended book is “Algorithm fourth Edition”, this book is very detailed, and with a lot of diagram demonstration, or quite good to understand.

2. Graph theory algorithm

Graph representation: adjacency matrix and adjacency list

Traversal algorithm: Deep search and wide search (must learn)

Shortest path algorithms: Floyd, Dijkstra (Required)

Minimum spanning Tree algorithm: Prim, Kruskal (Required)

Practical common algorithms: critical path, topology sort (principle and application)

Binary Graph Matching: Pairing, Hungarian Algorithm (Principles and Applications)

Extension: Centrality algorithm, Community Discovery algorithm (Principle and Application)

Figure is still more difficult, but I think figure involves a lot of algorithms are very practical, such as the calculation of the shortest path, figure related, I still suggest reading here, you can see the fourth edition of the Algorithm.

Search and backtracking algorithms

Greedy algorithms (required)

Heuristic search algorithm: A* Pathfinding algorithm (Understanding)

Map coloring algorithm, N Queen problem, optimal processing sequence

Travel agent problem

This is convenient just some algorithms related, I think if you can, learn them all. Ideas like greedy algorithms have to be learned. It is recommended to learn by brushing questions, leetcode direct topic brushing.

4. Dynamic programming

Tree DP: 01 knapsack problem

Linear DP: longest common subsequence, longest common substring

Interval DP: maximum value of the matrix (sum and product)

Digital DP: Digital games

State compression DP: Travel merchant

5. Character matching algorithm

Regular expression

Pattern matching: KMP, Boyer-Moore

I’ve written two articles on string matching, which are pretty good, and after reading these two articles, I think you pretty much know KMP and Boyer-Moore.

6. Flow correlation algorithm

Maximum flow: shortest augmented path, Dinic algorithm

Maximum flow and minimum cut: maximum profit problem, square number problem

Minimum cost maximum flow: minimum cost road, recreation

Does more articles and materials | click behind the text to the left left left 100 gpython self-study data package Ali cloud K8s practical manual guide] [ali cloud CDN row pit CDN ECS Hadoop large data of actual combat operations guide the conversation practice manual manual Knative cloud native application development guide OSS Operation and maintenance Combat manual White paper on cloud native architecture