Computer algorithm is a detailed description of how a computer converts input into the required output in a step-by-step manner. In other words, an algorithm is a specific description of the calculation process performed on the computer.

Edit this paragraph Algorithm properties An algorithm must have the following properties: (1) The algorithm must first be correct, that is, for any set of inputs, including reasonable inputs and unreasonable inputs, it can always be obtained expected output. If an algorithm can only get the expected output for reasonable inputs, but cannot predict the output results under abnormal circumstances, then it is not correct. (2) The algorithm must be composed of a series of specific steps, and each step can be understood and executed by the computer, rather than an abstract and vague concept. (3) Each step has a definite order of execution, that is, where the previous step is and what the next step is, must be clear and unambiguous. (4) No matter how complex the algorithm is, it must end and terminate after a finite number of steps, that is, the steps of the algorithm must be limited. Under no circumstances can the algorithm get stuck in an infinite loop. The solution to a problem can be expressed in many ways, but only solutions that meet the above four conditions can be called algorithms. Edit this paragraph important algorithm A* search algorithm

Commonly known as the A star algorithm. This is an algorithm that finds the lowest pass cost for a path with multiple nodes on the graphics plane. It is often used for mobile calculation of NPCs in games or BOT mobile calculations of online games. This algorithm, like Dijkstra's algorithm, can find a shortest path; it also performs heuristic search like BFS.

Beam Search

The beam search method is a heuristic method for solving optimization problems. It is developed on the basis of the branch and bound method. It uses The heuristic method estimates the k best paths and only searches downwards from these k paths. That is, only satisfactory nodes in each layer will be retained, and other nodes will be permanently discarded, which is better than the branch-and-bound method. Can greatly save running time. Beam search was first used in the field of artificial intelligence in the mid-1970s. In 1976, Lowerre used the beam search method for the first time in his speech recognition system called HARPY. His goal was to search several potential optimal words in parallel. Optimize decision paths to reduce backtracking and obtain a solution quickly.

Binary search algorithm

A search algorithm for finding a specific element in an ordered array. The search process starts from the middle element of the array. If the middle element happens to be the element to be searched, the search process ends; if a specific element is greater than or less than the middle element, search in the half of the array that is greater than or less than the middle element. , and start the comparison from the middle element just like the beginning. This search algorithm reduces the search range by half with each comparison.

Branch and bound

The branch and bound algorithm is a method of searching for a solution to a problem on the problem's solution space tree. However, unlike the backtracking algorithm, the branch-and-bound algorithm uses the breadth-first or minimum-cost-first method to search the solution space tree, and in the branch-and-bound algorithm, each live node has only one chance to become an expansion node.

Data Compression

Data compression increases data density by reducing the redundancy of data stored in computers or data in communications, ultimately reducing data storage space. technology. Data compression has a very wide range of applications in the fields of file storage and distributed systems. Data compression also represents an increase in size media capacity and an expansion of network bandwidth.

Diffie–Hellman key exchange

Diffie–Hellman key exchange, referred to as "D-H", is a security protocol. It allows both parties to establish a key through an insecure channel without any prior information from the other party. This key can be used as a symmetric key to encrypt the communication content in subsequent communications.

Dijkstra’s algorithm

Dijkstra’s algorithm (Dijkstra) was invented by Dutch computer scientist Edsger Wybe Dijkstra.

The algorithm solves the shortest path problem from a single source point to other vertices in a directed graph. For example, if the vertices in the graph represent cities and the weights on the edges represent the driving distance between the cities, Dijkstra's algorithm can be used to find the shortest path between the two cities.

Dynamic Programming

Dynamic programming is a method used in mathematics and computer science to solve optimization problems that contain overlapping subproblems. The basic idea is to decompose the original problem into similar sub-problems, and in the process of solving the problem, the solution to the original problem is obtained through the solutions of the sub-problems. The idea of ??dynamic programming is the basis of many algorithms and is widely used in the fields of computer science and engineering. More famous application examples include: solving the shortest path problem, knapsack problem, project management, network flow optimization, etc. There is also an article here that goes into more detail.

Euclidean algorithm

In mathematics, the euclidean algorithm, also known as Euclidean algorithm, is an algorithm for finding the greatest common divisor. The method of euclidean division first appeared in Euclid's "Elements of Geometry" (Volume VII, Propositions i and ii), and in China it can be traced back to the "Nine Chapters on Arithmetic" that appeared in the Eastern Han Dynasty.

Maximum expectation (EM) algorithm

In statistical computing, the maximum expectation (EM) algorithm is an algorithm for finding the maximum likelihood estimate of parameters in a probabilistic model, where probability The model relies on unobservable latent variables (Latent Variable). Maximum expectation is often used in the fields of data clustering (Data Clustering) in machine learning and computer vision. The maximum expectation algorithm is calculated alternately in two steps. The first step is to calculate the expectation (E), using the existing estimates of the hidden variables to calculate its maximum likelihood estimate; the second step is to maximize (M), the maximum Use the maximum likelihood value obtained in step E to calculate the parameter value. The parameter estimates found at step M are used in the next step E, and this process continues alternately.

Fast Fourier Transform (FFT)

Fast Fourier Transform (FFT) is a fast algorithm for discrete Fourier transform and can also be used to calculate discrete The inverse transform of the Fourier transform. Fast Fourier transform has a wide range of applications, such as digital signal processing, calculating large integer multiplication, solving partial differential equations, etc.

Hash function

HashFunction is a method of creating a small digital "fingerprint" from any kind of data. This function shuffles the data to recreate a fingerprint called a hash value. A hash value is typically used to represent a short string of random letters and numbers. Good hash functions rarely have hash collisions in the input domain. In hash tables and data processing, failure to suppress collisions to distinguish data can make database records harder to find.

Heap sort

Heapsort refers to a sorting algorithm designed using the data structure of a stacked tree (heap). A stacked tree is a structure that approximates a complete binary tree and satisfies the stacking property: that is, the key value or index of a child node is always smaller (or larger) than its parent node.

Merge sort

Merge sort is an effective sorting algorithm based on merge operations. This algorithm is a very typical application using the divide and conquer method (Divide and Conquer).

RANSAC algorithm

RANSAC is the abbreviation of "RANdom SAmpleConsensus". This algorithm is an iterative method for estimating mathematical model parameters from a set of observation data. It was proposed by Fischler and Bolles in 1981. It is a non-deterministic algorithm because it can only obtain reasonable results with a certain probability. As the number of iterations increases, this probability increases. The basic assumption of this algorithm is that there are "inliers" (those points that support model parameter estimation) and "outliers" (points that do not conform to the model) in the observation data set, and this set of observation data is affected by noise. RANSAC assumes that given a set of "inliers" data, the best model that fits this set of points can be obtained.

RSA encryption algorithm

This is a public key encryption algorithm and the world's first algorithm suitable for signatures.

Today's RSA patent has expired and is widely used for e-commerce encryption. Everyone believes that as long as the key is long enough, this algorithm will be safe.

Union-find

Union-find is a tree-type data structure used to handle the merging and query problems of some disjoint sets (Disjoint Sets). It is often represented by forest in usage.

Viterbi algorithm

Finding the most probable sequence of hidden states (Finding most probable sequence of hidden states). Edit this paragraph algorithm characteristics: 1. Finite. An algorithm should contain a finite number of steps and cannot be infinite. In fact, "finiteness" often means "within a reasonable range." If a computer is asked to execute an algorithm that takes 1,000 years to complete, although it is finite, it exceeds a reasonable limit and people do not regard it as an efficient algorithm. 2. Certainty. Each step in the algorithm should be definite, not vague or ambiguous. Each step in the algorithm should not be interpreted as having different meanings, but should be very clear. In other words, the meaning of the algorithm should be unique and should not cause "ambiguity". 3. There are zero or more inputs. The so-called input refers to the necessary information that needs to be obtained from the outside world when executing the algorithm. 4. There are one or more outputs. The purpose of the algorithm is to solve the problem. An algorithm without output is meaningless. 5. Effectiveness. Every step in the algorithm should be executed efficiently. and get definite results. Edit this paragraph Algorithms and Programs Although algorithms and computer programs are closely related, there are differences between the two: a computer program is an instance of an algorithm, a specific form of expressing the algorithm through a certain computer language; the same algorithm can be expressed in any language expressed in a computer language.

Algorithm list Graph theory path problem 0/1 edge weight shortest path BFS Non-negative edge weight shortest path (Dijkstra) Characteristic negative edge weight shortest path that can be solved with Dijkstra Bellman-Ford Bellman-Ford's Yen-like optimization differential constraint system Floyd Generalized Path Problem Transitive Closure Minimax Distance/Maximum Distance Euler Path/Tour Circle-in-Loop Algorithm Euler Path/Tour for Mixed Graphs Hamilton Path/Tour Hamilton Path/Tour for Special Graphs Construction of Spanning Tree Problem Minimum Spanning Tree Chapter k small spanning tree optimal ratio spanning tree 0/1 fractional programming degree restriction spanning tree connectivity problem powerful DFS algorithm undirected graph connectivity cut point cut edge two connected branch directed graph connectivity strongly connected branch 2-SAT minimum point Topological sorting of basic directed acyclic graphs Relationship between directed acyclic graphs and dynamic programming Bipartite graph matching problem Conversion ideas between general graph problems and bipartite graph problems Maximum matching Minimum path coverage of directed graph Minimum coverage complete matching of 0/1 matrix Optimal Matching Stable Marriage Network Flow Problem Simple Characteristics of Network Flow Model and Relationship with Linear Programming Maximum Flow Minimum Cut Theorem Maximum Flow Problem Maximum Flow Problem with Upper and Lower Bounds Circular Flow Minimum Cost Maximum Flow/Maximum Cost Maximum Flow Chordogram Properties and decision combinatorics, ideas commonly used in solving combinatorial mathematics problems, approximation recursion/dynamic programming probability problem, Polya theorem, computational geometry/analytical geometry, core of computational geometry: cross product/area, main force of analytic geometry: complex basic shapes, point straight lines, line segment polygons, convex polygons / The introduction of the convex hull convex hull algorithm, the introduction of the volume wrap method Graham scan method horizontal order, the patch perfect convex hull algorithm of the *** line convex hull, the relevant determination of the intersection of two straight lines, the intersection point of two line segments in any polygon, the determination point in the convex Classical problem of determination within a polygon Minimum circumscribed circle algorithm Minimum circumscribed circle approximation O(n) Point set diameter Rotation stuck, heel-point polygon triangulation Mathematics/Number theory Greatest common denominator Euclid algorithm Extended Euclid algorithm Congruence equation/2 System of linear equations with linear indefinite equations, congruence equations, Gaussian elimination method, solution of linear equations in mod 2 domain, exact solution of system of integral coefficient equations, calculation of matrix determinant using matrix multiplication to quickly calculate recursion relations, fraction trees, continued fraction approximation Number theory calculation to find the divisors of N, find phi(N), find divisors and fast number theory transformation... Prime number problem Probability prime algorithm Probability factor decomposition Data structure Organizational structure Binary heap Left-skewed tree Binomial tree Winner tree jump table Style Icon Slanted Heap Reap Statistical Structure Tree Array Virtual Binary Tree Line Segment Tree Rectangular Area and Circle Area Union Relationship Structure Hash Table and Set Application of Path Compression Idea Data Structure Vector in STL Deque Set/Map Dynamic Programming/Memory Search Dynamics The difference in the way of thinking between planning and memory search The longest subsequence series problem The longest non-decreasing subsequence The longest common * subsequence Dynamic programming solution to a class of NP problems Tree type dynamic programming Knapsack problem Optimization of dynamic programming Quadrilateral inequality Function's convexity and concavity state design planning direction linear programming common ideas bisection minimum representation string KMP Trie structure suffix tree/suffix array LCA/RMQ finite state automata theory sort selection/bubble quick sort heap sort merge sort radix sort topological sort sort network

Extended reading:

1

"Introduction to Computer Algorithm Design and Analysis" edited by Zhu Qingxin and others, People's Posts and Telecommunications Press

Open classification ：

Computer, algorithm