Characteristics of computer algorithms
1. There is poverty. An algorithm should contain finite operation steps, not infinite ones. In fact, "poor" often means "within a reasonable range". If you let a computer execute an algorithm that took 1000 years to complete, although it is poor, it exceeds the reasonable limit, and people do not regard it as an effective algorithm.
2. certainty. Every step in the algorithm should be clear and should not be vague. Every step in the algorithm should not be interpreted as a different meaning, but should be very clear. In other words, the meaning of the algorithm should be unique, and there should be no ambiguity.
3. There are zero or more inputs, and the so-called input means that the necessary information 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, and the algorithm without output is meaningless.
5. effectiveness. Every step in the algorithm should be executed effectively. And get a clear result.
: important algorithms
A* search algorithm
Commonly known as the A-star algorithm. This is an algorithm to find the lowest passing cost of the path with multiple nodes on the graphic plane. It is often used for mobile computing of NPC in games or BOT in online games. Like Dijkstra algorithm, this algorithm can find a shortest path. Like BFS, heuristic search is also carried out.
Beam search
Beam search method is a heuristic method to solve optimization problems. It is developed on the basis of branch and bound method. It uses heuristic method to estimate the k best paths, and only searches down from these k paths, that is, only the satisfactory nodes in each layer are kept, and other nodes are discarded permanently, which can greatly save running time compared with branch and bound method. Beam search was first applied in the field of artificial intelligence in the mid-1970s. 1976, Lowerre used the beam search method for the first time in his speech recognition system named HARPY. His goal is to search several potential optimal decision paths in parallel to reduce backtracking and get a solution quickly.
Binary search algorithm
A search algorithm for finding specific elements in an ordered array. The search process starts from the middle element of the array, and if the middle element is exactly the element to be searched, the search process ends; If a specific element is greater than or smaller than the middle element, the search is performed in the half of the array that is greater than or smaller than the middle element, and the comparison is started from the middle element. This search algorithm reduces the search range by half every comparison.
Branch and bound
Branch and bound algorithm is a method to search the solution of a problem in the solution space tree of the problem. But different from the backtracking algorithm, the branch-and-bound algorithm uses breadth-first or minimum cost-first method to search the solution space tree. In the branch-and-bound algorithm, each living node has only one chance to become an extended node.
data compression
Data compression is a technology to increase data density and ultimately reduce data storage space by reducing the redundancy of data stored in a computer or data in communication. Data compression is widely used in file storage and distributed systems. Data compression also represents the increase of media capacity and the expansion of network bandwidth.
Diffie-Hellman key agreement
Diffie-Hellman key exchange (D–H for short) is a security protocol. It allows both parties to establish a key through an insecure channel without any prior information of the other party. This key can be used as a symmetric key to encrypt communication content in subsequent communication.
Dijkstra algorithm
Dijkstra algorithm was invented by Dutch computer scientist Edsger Dijkstra. This 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 cities, the Dikoscher algorithm can be used to find the shortest path between two cities.
Dynamic programming
Dynamic programming is a method used in mathematics and computer science to solve optimization problems with overlapping subproblems. The basic idea is to decompose the original problem into similar subproblems, and in the process of solving, the solution of the original problem is obtained by solving the subproblems. The idea of dynamic programming is the basis of many algorithms and is widely used in computer science and engineering. Famous application examples include: solving the shortest path problem, knapsack problem, project management, network traffic optimization and so on. Here is another article in more detail.
Euclid algorithm
In mathematics, transitive division, also known as Euclid algorithm, is an algorithm for finding the greatest common divisor. The division of phases first appeared in Euclid's Elements of Geometry (Volume VII, Proposition 1 and Proposition 2), while in China it can be traced back to Nine Chapters of Arithmetic, which appeared in the Eastern Han Dynasty.
Maximum expectation algorithm
In statistical calculation, the maximum expectation (EM) algorithm is an algorithm to find the maximum likelihood estimation of parameters in the probability model, in which the probability model depends on an unobservable hidden variable. Maximum expectation is often used in data clustering fields of machine learning and computer vision. The maximum expectation algorithm is calculated alternately in two steps. The first step is to calculate the expectation (e), and calculate the maximum likelihood estimation value of hidden variables by using the existing estimation value; The second step is to maximize (m), which maximizes the maximum likelihood value obtained in step e to calculate the value of the parameter. The estimated values of the parameters found in step m are used in the calculation of the next step e, and the process is carried out alternately.
Fast Fourier transform
Fast Fourier transform (FFT) is a fast algorithm of discrete Fourier transform, and it can also be used to calculate the inverse of discrete Fourier transform. Fast Fourier transform has a wide range of applications, such as digital signal processing, calculating large integer multiplication, solving partial differential equations and so on.
hash function
HashFunction is a method to create small digital fingerprints from any type of data. This function scrambles the data and recreates a fingerprint called a hash value. Hash values are usually used to represent a short string of random letters and numbers. Good hash functions rarely have hash conflicts in the input domain. In hash table and data processing, not suppressing conflicts to distinguish data will make database records more difficult to find.
heapsort
Heapsort refers to a sort algorithm designed by using the data structure of heap tree. Heap tree is an approximate complete binary tree structure, which also satisfies the heap property: that is, the key value or index of child nodes is always smaller (or larger) than its parent node.
Combined classification
Merge sorting is an effective sorting algorithm based on merge operation. This algorithm is a very typical application of divide and conquer.
RANSAC algorithm
RANSAC is the abbreviation of "RANdom SAmpleConsensus". This algorithm is an iterative method to estimate the parameters of mathematical model from a set of observation data, which was proposed by Fischler and Bolles in 198 1. It is a non-deterministic algorithm, because it can only get reasonable results with a certain probability, and this probability increases with the increase of iteration times. The basic assumption of this algorithm is that there are "interior points" (those points that support model parameter estimation) and "outliers" (points that do not conform to the model) in the observation data set, and this group of observation data is affected by noise. RANSAC assumes that given a set of "inline" data, the best model can be obtained.
rsa algorithm
This is a public key encryption algorithm and the first one suitable for signature in the world. Today's RSA patent has expired and is widely used in e-commerce encryption. Everyone believes that this algorithm will be secure as long as the key is long enough.
Joint search
Union is a tree-like data structure, which is used to deal with the merging and query of disjoint sets. It is usually represented by forests.
viterbi algorithm
Find the most possible hidden state sequence.
References:
Computerized algorithm