The source of the
Zhou bi Suanjing, or the Circular Suanjing, or the Circular Suanjing, is a mathematical classic of the Han Dynasty. Zhou, the Circular Suanjin, or the Circular Suanjin, says in the text, “The method of counting derives from the circular square. The circle comes from the square, and the square comes from the moment. The moment comes from ninety-nine eighty-one.” All arithmetical methods are derived from the calculation of circles and each other, where the circle is derived from the square (the area of the circle is equal to the circumference of the square x PI /4), the square from the moment (the square is derived from the moment of two equal sides), and the moment is derived from the ninety-nine multiplication table. Back in the Spring and Autumn and Warring States periods, The Formula for Multiplication had become popular. Maths teachers from Shanghai have been hired by the Department for Education to train pupils in the UK after David Cameron was asked how much 8×9 equals.
Chinese teachers bring the art of maths to English schools
In the West, it was an Arab living in Baghdad, Al Khwarizmi, who introduced India’s more advanced decimal number system. Al Khawarizmi shows the steps of addition, subtraction, multiplication, division, and even square roots and PI. The characteristics of these steps are: simple, unambiguous, effective, limited steps, correct. Hundreds of years later, when the decimal system of Arabic numerals was in widespread use in Europe, Al Khwarizmi’s Latin-coded “Algorithm” was created to describe the rule-based behavior of numerical calculations.
Definition of algorithm
So what is an algorithm, literally, is a method or a rule of calculation. Computation here is not just arithmetic operations such as addition, subtraction, multiplication and division, but in a broad sense calculation of doing anything. Methods and laws mean using them to solve the problem at hand.
Take the World Cup, which is held every four years to select the best soccer nation in the world. In more than 200 countries, a round-robin league system, in which each team has to play against every other team to determine its position, would take 600 days at most, assuming that it plays every three days. How about, tired feel not love, or square dance to more relaxed. The sensible strategy for the tournament’s organizers would be to select a handful of teams from several continents, then gather together for a month to decide, and even split into several groups so that the best teams in each group can advance to the championship.
Logically, the best teams, regardless of format, always come out on top; And the above method of choosing the best of the best, the difficulty and cost are reduced a lot. There is a specific name for this process: Partition, which will be a big problem (look for the world’s best team), broken down into multiple types the same but smaller problems (looking for the best team a continent), if the problem is resolved, so big problem is much more easy to solve (continents best team PK, knew the world champion trophy, who). This is just one example of many algorithmic applications in life, so a complete dictionary definition from fact to abstraction is not necessary for the application and analyst. In fact, the definition of an algorithm varies depending on how you look at it.
If you’re a philosopher: an algorithm is an abstract sequence of actions that solves a problem.
If you’re a coder: An algorithm is a computational process that takes some input and produces some output.
If you like the lofty: An algorithm is a tool for solving a precisely defined computational problem.
But they all stressed one thing: the invariants of the algorithm, that is, the algorithm must be able to be followed step by step.
The heart of the algorithm
An algorithm is a method or rule for solving a problem. But there is not always one way to solve a problem. There are good and bad ways to solve a problem. How do we compare different algorithms for solving the same problem?
There are certainly many things that can be compared, such as modularity, correctness, maintainability, robustness, friendliness, simplicity, extensibility, and reliability, but these are not the primary concerns in algorithm design and analysis. But they are more like external attributes that humans attach to algorithms, because they often depend on other qualities of the person who uses or implements the algorithm: understanding, presentation, programming skills, data structure use and design skills.
So what is the heart or soul of the algorithm? Perhaps you can already guess: speed. That’s how fast they solve problems. Speed is often the difference between what works and what doesn’t. For example, an algorithm that takes years to run will not satisfy us, no matter how correct it is. In a practical sense, there is not much essential difference between the algorithm being correct and incorrect.
If an algorithm becomes hundreds or thousands of times more efficient as you improve it, sitting in front of a screen is no less enjoyable than many other things.
Heap machine or spell algorithm
When it comes to speed, they will move to Huaqiang North, the memory processor. But how far can the increase in computer speed solve some simple problems? Let’s look at a classic example.
We have a model that describes the increasing number of rabbits:
Origin: a pair of male and female rabbits
Rule: Each pair of rabbits gives birth to a pair of rabbits every month, and they can only give birth twice in their lifetime, and they die of old age after the second birth. (We assume that each pair of rabbits born continues to reproduce normally, so Please take a detour for Fang Zhouzi and The King of Fruit shell knowledge…)
If the number of rabbits in the NTH month is F(n), then F(n) rabbits contains the number of rabbits born in this month (that is, the total number of rabbits in (n-1) month F(n-1)), and the number of rabbits born in the last month (because the old rabbits from the last month have died in this month), that is, F(n-2). So F(n)=F(n-1) +F(n-2), the sequence of F(n) is called the Fibonacci sequence.
So let’s start with F(n), let’s say you want to know the number of rabbits at month 30, so F(30) is equal to F(29) plus F(28), so F(29) is equal to F(28) plus F(27), and we just keep breaking it down, and we just have to count how many F(0) there are. We write a piece of code, we run it, we take a friend out to play pool, we come back and maybe we get the answer. If you take the long view and want to know the number of rabbits at month 300, then you have to look for other algorithms. Because the number of F(0)’s is too large. This naive recursive solution, in fact, involves exponential operations on F of 0. You’ll be smart enough to realize that the Fibonacci sequence is a second-order recursive sequence, so you can end up with F(300) in logarithmic order, which is omitted here, but will be discussed later if you’re interested.
The problem is that as hardware becomes more powerful, practitioners of large-scale computing or big data often think faster algorithms may not be necessary. So let’s look at the naive recursive solution of Fibonacci numbers, which has a time complexity of 1.6 to the n, that is, it takes about 1.6 times longer to compute F(n+1) than F(n). With Moore’s Law doubling performance every 18 months, we can only compute one more unknown Fibonacci number per year.
We say that IBM’s Roadrunner supercomputer performs 30 times better than NEC’s Earth Simulator, but that only means the Roadrunner can compute seven more numbers in exponential complexity in the same amount of time. But using the log (n) algorithm, Roadrunner could calculate 10 to the 30th Fibonacci numbers.
So algorithm books aren’t all about filling coffee cups… The effect of the improved algorithm, rather than increasing the speed of the hardware, is still significant, isn’t it?
conclusion
The pursuit of algorithm efficiency, in any scene, can bring you unexpected surprises. For the breakthrough of products, the reduction of overhead and the condensation of technical atmosphere, what way is more effective and beautiful than thinking and paying attention to the algorithm?