In today's world, there are countless classic algorithms that have been discovered or created. If you must vote for the top ten algorithms you value the most, what would you choose? Some foreign netizens have launched a vote on StackExchange, allowing people to vote for the most classic algorithms in their minds, and finally produced the top ten classic algorithms with the highest number of votes below (The voting count ends on March 7, 2011）：
Tenth place: Huffman coding (Huffman coding)
Huffman Coding is a coding method, an entropy encoding (weight encoding) algorithm used for lossless data compression. In 1952, David A. Huffman was invented while studying for his PhD at MIT and published in "A Method for the Construction of Minimum-Redundancy Codes".
Ninth place: Binary Search (Binary Search)
To find elements in an ordered set, you can use the binary search algorithm, also known as binary search. The binary search algorithm first compares the sizes of elements and keys located in the middle of the set. There are three cases (assuming that the set is arranged from small to large):
1. If the key is smaller than the middle position, the matching element must be on the left (if any), so a binary search is applied to the area on the left.
2. The key is equal to the element at the middle position, so the element is found.
3. If the key is greater than the middle position, the matching element must be on the right (if any), so a binary search is applied to the area on the right.
In addition, when the set is empty, it means that it cannot be found.
Eighth place: Similar tests conducted by Miller-Rabin
This idea is to use the properties of prime numbers (such as using Fermat's Grand Theorem) to find witnessing no prime numbers. If there is no evidence that it is sufficient to find after a random test, this number is a prime number.
Seventh place: Depth First Search, Breadth First Search(Depth and breadth priority search)
They are the basis of many other algorithms. For a specific introduction to the depth and breadth priority search algorithm, please refer to this article:Teach you a thorough understanding: BFS and DFS priority search algorithms。
Sixth place: Gentry's Fully Homomorphic Encryption Scheme(Gentleman's Complete Homomorphic Encryption Mechanism) Algorithm.
This algorithm is beautiful, and it allows third parties to perform arbitrary encrypted data operations without getting the private key (not very familiar with it).
Fifth place: Floyd-Warshall all-pairs shortest path algorithm
For an introduction to this algorithm, please refer to this article I wrote: Comparison of several shortest path algorithms (/v_JULY_v/archive/2011/02/12/）。
d[]: 2D array. d[i,j] minimum cost, or adjacent edge of the shortest path.
for k from 1 to n:
for i from 1 to n:
for j from 1 to n:
d[i,j] = min(d[i,j], d[i,k] + d[k,j])
Fourth place: Quicksort (quick sort)
The quick sort algorithm covers almost all the list of all classic algorithms. It was selected as one of the top ten greatest algorithms of the 20th century (see this:Count the 10 greatest algorithms of the 20th century). For a specific introduction to the quick sorting algorithm, please refer to the article I wrote:In-depth analysis of Yizhisheng and quick sorting algorithm,and12. Continued: All versions of the C/C++ implementation of the quick sorting algorithm。
Third place: BFPRT algorithm
In 1973, Blum, Floyd, Pratt, Rivest, and Tarjan jointly published a paper called "Time bounds for selection", which gave an algorithm to select the average complexity of the k-th largest element in an array with O(N), commonly known as the "median algorithm of median". This algorithm relies on a carefully designed pivot selection method, that is, selecting the median of the median as the hub element, thus ensuring that linear time complexity can be achieved in the most case, defeating the fast sorting algorithm of average O(N*logN) and worst O(n^2) complexity.
In fact, this so-called BFPRT is the quick selection SELECT algorithm explained in this blog. For details, please refer to the following blog:Chapter 3: Finding the smallest number of k、14. In-depth analysis and implementation of quick selection of SELECT algorithm. In these two articles, this quick selection SELECT algorithm is given. By selecting the median median in the array as the hub element, it can achieve a proof of the complexity of the worst-case run time O(N).
Here I will briefly introduce the algorithm where the time complexity of selecting the kth largest element in the array is O(N):
Similar to segmentation algorithm in quick row:
After each segmentation, you can return the position s of the hub point in the array, and then compare the sizes of s and k.
If it is large, then recursively divide array[s..n] again,
If it is small, recursive array[left...s-1] //s is the intermediate hub point element.
Otherwise, return array[s], which is the value returned in the partition. //It is to find this s.
After finding the s value that meets the requirements, iterates over the element on the side that outputs smaller than s.
You can also refer to the following in Chapter 9: Introduction to Algorithm, which is based on the desired linear time, and there is a proof that the average time complexity of O(N) is found in the array. The original program randomly selects an element in the array as a hub element, and finally it can be proved that the expected running time of the program is O(n), and the elements are assumed to be different.
Second place: Knuth-Morris-Pratt string matching algorithm
For an introduction to this algorithm, please refer to this article:6. Teach you to fully understand KMP calculation from beginning to endLaw. The KMP algorithm was once lost in the top ten greatest algorithms of the 20th century, but people obviously cannot accept that such a beautiful and efficient KMP algorithm would be lost. Therefore, the final voting was born, and the KMP algorithm ranked second.
First place: Union-find
The union set is a tree-type data structure used to deal with the merging and querying problems of some disjoint sets. It is often expressed as a forest in use. A set is to make each element form a collection of single elements, and to merge the sets of elements belonging to the same group in a certain order. Parallel search finally occupied the first place on this list.
Supplement: The number of votes in the top three is only 4 votes and 8 votes. So this ranking will continue to change in the future. But no matter what the final result is, the top ten algorithms have been basically finalized.