This is the 9th day of my participation in the November Gwen Challenge. See details: The Last Gwen Challenge 2021.

preface

No more nonsense, data structure must learn! I will update a chapter every day. If I can’t finish one, I will divide it into two chapters

Data access

Second, the algorithm

2.1 Comparison of the two algorithms

Algorithms and data structures are inseparable

Calculate the sum from 1 to 100

#include <stdio.h>
void main(a)
{
    int sum;
    for (int i = 0; i < 101; i++)
    {
        sum += i;
    }
    printf("%d",sum);
}

PS D:\C> cd "d:\C\" ; if ($?) { gcc a.c -o a } ; if ($?) { .\a }
5050
Copy the code

So that’s an algorithm, but isn’t it a good one? Is it efficient?

Now what does gauss do as a teenager, sum from 1 to 100

In code

#include <stdio.h>
void main(a)
{
    int sum,n = 100;
    sum = (1+n)*n / 2;
    printf("%d",sum);
}
PS D:\C> cd "d:\C\" ; if ($?) { gcc a.c -o a } ; if ($?) { .\a }
5050
Copy the code

This is an arithmetic arithmetic of arithmetic progression

The first algorithm, written by the computer, takes 100 cycles to compute

You can see the difference between a good algorithm and a bad algorithm

All I can say is heifer goes to the South Pole and cow B goes to the pole

2.2 Algorithm Definition

Algorithm An algorithm is how do you solve a problem, a description of the steps to solve a particular problem, the way you do it, the steps to solve the problem, represented in a computer as a finite sequence of instructions, and each instruction represents one or more operations

As we saw in the previous example, there are multiple algorithms that can be used to solve a given problem.

Problems in the real world are so strange that algorithms are so variable, and there is no universal algorithm that can solve them all. Even a good algorithm for solving a small problem may not be suitable for it. The definition of an algorithm refers to instructions that can be executed by computing devices such as humans or machines. It can be a computer command, or it can be our ordinary language.Copy the code

To solve a certain problem or class of problems, instructions need to be expressed as a sequence of operations, including a set of operations, each operation to accomplish a specific function, this is an algorithm.

2.3 Characteristics of the algorithm

The algorithm has five basic characteristics: input, output, fineness, determinacy and feasibility.

2.3.1 INPUT and Output

The input and output characteristics are relatively easy to understand, and the algorithm has zero or more inputs. While input parameters are necessary for most algorithms, for rare cases, such as printing “Hello world! Such code does not require any input parameters, so the input of the algorithm can be zero. The algorithm has at least one or more outputs, the algorithm must have outputs, not outputs, why do you use this algorithm? The output can take the form of printout, return – one or more values, etc.

2.3.2 has poor sex

Fineness: An algorithm that executes a finite number of steps, terminates automatically without an infinite loop, and each step completes in an acceptable amount of time.

In reality, code is often written in an infinite loop, which is not satisfied with the finite. Of course, the concept of poverty here is not purely mathematical, but reasonable and acceptable in practical application of the “boundary”. You say that if you write an algorithm, the computer will need 20 years to calculate it, and it will definitely end. In the mathematical sense, it is poor, but the daughter-in-law has become a woman, so the significance of the algorithm is not great.

2.3.3 certainty

** Deterministic: Each step of the algorithm has a definite meaning, there is no ambiguity. ** algorithm under certain conditions, only one execution path, the same input can have only – one output result. Each step of the algorithm is precisely defined without ambiguity.

2.3.4 feasibility

Feasibility: Each step of the algorithm must be feasible, that is, each step can be performed a finite number of times.

** Feasibility means that the algorithm can be converted to run on the program and get correct results. ** Although there are extremely complex algorithms that are not implemented in today’s computing world, not because they are theoretically impossible, but because they are so complex that our current programming methods, tools, and brains limit their work, these are theoretical problems and not for us to consider at this time.

2.4 Requirements for algorithm design

Against 2.4.1 correctness

Correctness: The correctness of the algorithm means that the algorithm should at least have input, output and processing unambiguous, can correctly reflect the needs of the problem, can get the correct answer to the problem.

But the “right” algorithms often vary widely in usage, which can be broadly divided into the following four levels.

1. The algorithm program has no syntax errors. 2. The algorithm program can produce output results that meet the requirements for legitimate input data. 3. The algorithm program can obtain the results that meet the specifications for illegal input data. 4. The algorithm program has output results that meet the requirements for carefully selected or even difficult test data

2.4.2 readability

Readability: Algorithms are also designed to be easy to read, understand, and communicate.

2.4.3 robustness

A good algorithm should also be able to handle cases where input data is illegal. For example, the input time or distance should not be negative. Robustness: When the input data is invalid, the algorithm can do something about it, rather than producing exceptions or strange results.

2.4.4 High time efficiency and low storage

Finally, a good algorithm should have high time efficiency and low storage.

Time efficiency refers to the execution time of the algorithm. For the same problem, if multiple algorithms can solve it, the algorithm with short execution time has high efficiency, while the algorithm with long execution time has low efficiency.

The storage requirement refers to the maximum storage space required by an algorithm during its execution, mainly the memory or external disk storage space occupied by the algorithm program. The design algorithm should meet the requirements of high time efficiency and low storage as far as possible. In life, people want to spend the least money, with the shortest time, do the biggest thing, the algorithm is the same idea, the best with the least storage space, spend the least time, do the same thing is a good algorithm.

The examples in the book are really good!!

To sum up, a good algorithm should have the characteristics of correctness, readability, robustness, high efficiency and low storage

2.5 Measurement method of algorithm efficiency

2.5.1 Post-hoc statistical methods.

Statistical method after the event: this method is mainly through the design of good test procedures and data, the use of computer timer to compare the running time of the program prepared by different algorithms, so as to determine the efficiency of the algorithm.

2.5.2 Prior analysis and estimation method

Our computer forefathers, in order to evaluate algorithms more scientifically, developed a method called antecedent analysis estimation.

Pre-analysis estimation method: estimation of the algorithm based on statistical methods before computer programming.

That is, regardless of the hardware and software involved, the running time of a program depends on the quality of the algorithm and the size of the problem. The so-called problem input scale refers to the amount of input.

Obviously, the first algorithm performs 1+ (n+1) +n+1 times =2n+3 times; The second algorithm is 1+1+1=3 times.

In fact, the first and last statements of both algorithms are the same, so the code we care about is really the middle part of the code, and we consider the loop as a whole, ignoring the overhead of the head and tail loops, so these two algorithms are essentially the difference between n and 1. It’s easy to see how good an algorithm is.

We can get inspiration from the problem description, the same problem input size is n, the first kind of summation algorithm, find 1+2+… Plus n requires a piece of code to run n times. So the input size of the problem is such that the number of operations is f (n)= n, so obviously the same code that runs 100 times is 10 times the size of 10 operations.

In the second case, no matter what n is, the number of runs is 1, that is, f(n)=1;

And the third way, 100 operations is 100 times more than 10 operations. Because it’s f (n) =n^2

This point is also easy to understand!

2.6 Asymptotic growth of the function

Asymptotic growth of functions: Given two functions f(n) and g(n), if there exists an integer n such that f(n) is always larger than G (n) for all n> n, then we say that f(n) grows asymptotically faster than g(n).

Conclusion:

As n increases, it doesn’t really matter whether it’s +3 or +1, for example, A prime or B prime, so we can ignore these addition constants. In a later example, the significance of such a constant being ignored may become more obvious.

It doesn’t matter what the constant is.

If the highest order term is large, the function grows very fast as n grows.

When judging the efficiency of an algorithm, constants and other minor terms in the function can often be ignored, and the order of the principal term (the highest order term) should be paid more attention to.