Guide language:
In the programmer community, there is often discussion about which big factory’s algorithm is good. So, algorithm this let programmer emotion complex thing, after all “fierce” in what? Are algorithms important to programmers? What algorithms should a qualified programmer know? In this issue, I’m going to explore with you what an algorithm really is.
Flow chart of algorithm for light bulb failure
The past lives of algorithms
An algorithm, as a valid method in mathematics and computer science, is a defined finite sequence of steps or steps that a computer can give instructions to, often used in computation, data processing, and automatic reasoning. It consists of a set of clearly defined instructions that can be clearly expressed in limited time and space.
In a popular way, an algorithm can be likened to a recipe. Let the people who know nothing about baking, can also according to the recipe provided on the “algorithm” steps, according to the proportion of mixing materials, with the appropriate dough strength, control the baking time, to make delicious bread.
At the same time, every time you bake bread, you don’t have to reinvent the baking process. This is also the primary characteristic of “algorithms” : algorithms are means of solving problems. We don’t have to invent a solution for every problem of the same kind. Therefore, the algorithm is a once and for all working method.
Beyond today’s narrow Internet terms, people have been exploring algorithms for thousands of years. In ancient China, algorithms were called “shu”. Zhou bi Suanjing and Jiuzhang Suanshu first appeared in Zhou bi Suanjing and Jiuzhang Suanshu. In particular, jiuzhang Suanshu gives four operations, the largest common divisor, the least common multiple, the square root, the cube root, the Eratostheni sieve method for finding prime numbers, and the algorithm for solving linear equations.
In the Western world, around 300 BC, The Euclid algorithm appeared, which is considered to be the first algorithm in history. Fast forward to 1842, and Ada Lovelace is widely considered the world’s first programmer, writing a program for the Babbage Analytical Machine to solve Bernoulli’s differential equations. Then, in the 20th century, the British mathematician Alan Turing developed his famous Turing thesis and proposed an abstract model of a hypothetical computer known as the Turing machine.
It was also from the Turing machine that algorithms really began to be used in computing. How important is it for programmers to know about algorithms in their “past lives”?
In a broad sense, algorithms affect every learner and user from a mathematical, logical, and even programming philosophy perspective. It’s not something you learn to use, but it’s important enough for programmers to determine how far they can go in the industry.
For programmers, an algorithm is a method, an idea, a way of thinking to solve a problem. Like a cookbook, it trains you to use the computer’s “way of thinking” to solve ordered problems, using the properties of regularity. Constantly optimizing the programming thinking of programmers. In the future, programmers may not use formal algorithms, but the underlying methodology is already integrated into the programmer’s working mind.
In the actual work, need to read some code, also do need algorithm foundation, for example, when looking at LevelDB, Redis source code, need to know what is the meaning of the hop table; Look at the Linux VMA to know what a red-black tree is; To read a Page cache, you need to understand the cardinality tree.
Finally, no matter how much programmers resist algorithms, they need to learn to handle interviews.
In the programmer interview, 75% of the questions will be related to algorithm, data structure, especially in some foreign companies, algorithm is the top priority in the interview, especially foreign managers especially like those ACM competition experience of the interviewer. When the interviewer suddenly says, “About algorithms, do you…” “, the interviewer can’t handle and may go home.
10 Algorithms programmers need to know
Here are ten basic algorithms programmers need to know about in their daily work.
1. Quicksort algorithm
Quicksort is a sort algorithm proposed by Tony Hall. On average, order n two items and compare them (nlogn) several times. In the worst case, a comparison of TWO (N2) steps is required, but this is not common. Quicksort is generally significantly faster than other two algorithms (NLOGN) because its innerloop can be implemented efficiently on most architectures.
2. Heap sort algorithm
Heapsort refers to a sort algorithm designed by using heap data structure. Heap is a nearly complete binary tree structure, and also satisfies the property of heap: that is, the key value or index of the child node is always smaller (or larger) than its parent node. The average time complexity of heap sort is two o (nlogn).
3. Merge sort
Mergesort is an efficient sorting algorithm based on merge operation. This algorithm is a very typical application of divide-and-conquer.
4. Binary search algorithm
Binary search algorithm is a search algorithm that looks for a particular element in an ordered array.
The search process starts with the middle element of the array. If the middle element is exactly the element being searched, the search process ends. If a particular element is greater than or less than the middle element, the search is performed on the half of the array that is greater than or less than the middle element, and the comparison begins with the middle element as it began.
If the array is empty at any step, it cannot be found. This search algorithm reduces the search area by half with each comparison. Half search Reduces the search area by half each time and the time complexity is two o (logn).
5.BFPRT(Linear Lookup Algorithm)
BFPRT algorithm solves a classic problem, that is, selecting the KTH largest (KTH smallest) element from a sequence of N elements. Through clever analysis, BFPRT can ensure that it is still linear time complexity in the worst case.
The idea of this algorithm is similar to the idea of quicksort, of course, in order to make the algorithm still achieve O(n) time complexity in the worst case, five authors of the algorithm have done a subtle treatment.
6.DFS (Depth-first Search)
Depth-First-Search algorithm is a kind of Search algorithm.
It traverses the nodes of the tree along its depth, searching branches as deep as possible. When all edges of node V have been explored, the search goes back to the starting node of the edge on which node V was found.
This process continues until all nodes reachable from the source node have been discovered. If there are undiscovered nodes, one of them is selected as the source node and the process is repeated until all nodes have been accessed.
7.BFS(Breadth-first Search)
Breadth-First-Search algorithm is a graphic Search algorithm. Simply put, BFS starts at the root node and traverses the nodes of the tree (graph) along its width.
If all nodes are accessed, the algorithm aborts. BFS is also blind search. Queue data structures are generally used to assist the IMPLEMENTATION of BFS algorithms.
8. Dijkstra algorithm
Dijkstra’s salgorithm (Orithm) was proposed by Dutch computer scientist Eizhel Dykstra.
Dikoscher algorithm uses breadth-first search to solve the single source shortest path problem of non-negatively-weighted directed graph, and finally obtains a shortest path tree. This algorithm is often used in routing algorithms or as a submodule of other graph algorithms.
The input of the algorithm consists of a weighted directed graph G and a source vertex S in G. V is the set of all vertices in G.
Every edge in a graph is a pair of ordered elements formed by two vertices. (u,v) means there’s a path from vertex u to v. We denote the set of all edges in G by E, and the weight of edges is defined by the weight function W :E→[0,∞]. So w(u,v) is the non-negative weight from vertex u to vertex v.
The weight of an edge can be thought of as the distance between two vertices. The weight of the path between any two points is the sum of the weights of all the edges of the path. Given that V has vertices S and t, Dijkstra can find the least weighted path from S to T (for example, the shortest path).
This algorithm can also find the shortest path from one vertex S to any other vertex in a graph. Dijkstra algorithm is the fastest single source shortest path algorithm for digraphs without negative weights.
9. Dynamic programming algorithm
Dynamicprogramming is a method used in mathematics, computer science, and economics to solve complex problems by breaking down original problems into relatively simple subproblems.
Dynamic programming is often applied to problems with overlapping subproblems and optimal substructures, and the time consumed by dynamic programming is often much less than that of the naive solution.
The basic idea behind dynamic programming is very simple. Roughly speaking, to solve a given problem, we need to solve its different parts (i.e., subproblems) and combine the solutions of the subproblems to get the solution of the original problem.
In general, many subproblems are very similar, so the dynamic programming method tries to solve each subproblem only once, thus reducing the amount of computation: once the solution of a given stator problem has been calculated, it is stored in memory so that the next time the solution of the same subproblem is needed, it can be directly looked up in the table. This approach is particularly useful when the number of repeating subproblems increases exponentially with respect to the size of the input.
The most classical problem about dynamic programming is knapsack problem.
10. Naive Bayesian classification algorithm
Naive Bayes classification algorithm is a simple probability classification algorithm based on Bayes theorem. The basis of Bayesian classification is probabilistic reasoning, which is how to complete reasoning and decision-making tasks when the existence of various conditions is uncertain and only the probability of their occurrence is known.
Probabilistic inference is corresponding to deterministic inference, while naive Bayes classifier is based on independent hypothesis, that is, each feature of the hypothesis sample is unrelated to other features.
Naive Bayes classifier relies on accurate natural probability model and can achieve very good classification effect in supervised learning sample set. In many practical applications, naive Bayesian model parameter estimation uses maximum likelihood estimation method, in other words naive Bayesian model can work without using Bayesian probability or any Bayesian model.
Despite these naive ideas and oversimplified assumptions naive Bayes classifier can still achieve quite good results in many complex realistic situations.
Knowing the importance of algorithms, are you interested in learning more about algorithms? But don’t worry, it’s been a thousand years since algorithms were invented. We learn to be handy, it is not a day to do it.