Hello,everyone.
We will continue with the first section of the Data Structure and Algorithm.
We mainly introduce characteristics and simple classification of algorithm
Algorithm plays a very important role in the problem solving of computer
Problem of our computer is a function actually
It maps the input data to the corresponding output
The process of mapping is algorithm.
Algorithm is composed of some specific effective sequence
And in the environment of the computer, we must realize it as a specific program which is written in a computer programming language
Then in a specific operating system environment, we must use specific compiler to translate it into a binary code that the machine can understand and execute to get the problem solved finally.
Algorithm has some related features
First, it needs to have universality, that is to say we write algorithm, in order to use it to solve the same problem again and again
For example, for an eight queen problem, we place eight queens on the chess board of 8*8. And the queens on the same line or in the same column or diagonal can't attack each other, so there can't be two queens on the same line or in the same column or diagonal
The eight queen problem can also be seen as four queen problem or n queen problem. Their solutions are similiar to each other.
For the n queen problem, we just conduct a parameterized process for the problem.
If we has written effective algorithm, problem of the same type can be solved correctly.
Another feature of algorithm is effectiveness.
The aim of writing algorithm is to solve the problem.
Problem solving is meaningful.
We write limited orderly sequence, and then solve the problem through an efficient algorithm.
Our results should be effective
Our process should be effective
Another feature of algorithm is deterministic
It means that every step of our algotithm is definite in the process of writing algorithm
When the program executes to somewhere, we'll have a data environment
What should be done in the next step can be known through the data input right now
For example, for a judgement such as if else.
If I have known the data input, it can be known which code segment the program will executes. The code segment will not be random assigned
It is obvious that in some situations such as artificial intelligence, you seem to be not sure and some random algorithm randoms select which code segment to execute.
But after we has written the code, we'll have decision according to the data.
It is not randomized.
It is very specific from the under layer.
Algorithm has the feature of finiteness.
It means that algorithm should be completed in a certain time with certain steps
We will never write an algorithm that loops all the time and the result can never be got
However the operating system we used commonly is an endless loop program.
It waits for instructions from the external environment such as the events of keyboard and mouse, and operates correspondingly.
The operating system should not be seen as an algorithm in the sense of algorithm because it is a endless loop program.
Let's look at an example of the queen problem.
For a situation of a four queen problem like this, we suppose the solution is a tetrad since we should not place two queens in the same line.
It represents the column value of the queen in each line.
Since there can't be two queens in the same column, it is an arrangement in fact.
For all the arrangement situations of the four queen problem, we enumerate them.
And we get a quadtree like this.
The quadtree is divided into four branches according to the value of the queen in the first line is placed as 1 or 2 3 4.
After it, we can see which column can the queen be placed in the second line.
And we can finally get a search space of quad tree like this.
For the 4 queen problem, I'm just judging the search space and take out the illegal solution if there is no good solution.
We finally get two sets of solutions.
These two sollutions are marked red.
We can seen that these two solutions are symmetrical.
There are some algorithm that can solve it better.
In other words, there are some branches that are sure to be meaningless without thinking about.
For example, if I place one queen in the first line and in the first column , and place one queen in the second column and in the second line. I will not consider the branch any more since there are two queens on the same diagonal.
The process of problem solving like this is the backtracking algorithm.
The backtracking algorithm can reduced the time of problem solving significantly because we can reduce the seach space significantly.
For the left part of the queen problem, the paths we marked as blue are the possible searchpath.
The right part is symmetrical to it, so we don't mark it again.
Let's look at the simple classification of algorith,.
For all the problems that we don't have very good algorithm, we can think about using the method of exhaustion.
We first look at what kind of property does the problem have, what kind of property does the data have. And then find whether there are some solutions more effective to solve it.
For the example of the four queen problem we talked about before, we can use the method of exhaustion to list all the solutions of it.
Then I use backtracking algorithm to search effectively.
The theory of backtracking algorithm is the process of trying to enter or trying to change or trace back.
In dara structure and algorithm, the traversal of tree and graph and many other problems use the idea of backtracking algorithm.
There is another kind of method called recursive partition.
Recursive partition works well for some specific problem.
For example, if we want to search K in an orderly array that has been sorted, we can use bisection algorithm to solve it recursively.
Greedy method is a special kind of algorithm
Its data has the property of greedy.
We try to get the optimal solution at present.
We try to get the optimal solution everytime and get the best result at last.
In our textbook, there are some algorithm in the form of greedy method.
The dynamic programming method is to get the best solution for a small-size problem and assemble them for a larger scale problem and finally get the best solution for the whole problem.
The dynamic programming method requires the property of optimal substructure.
Its substructure is actually overlap substructure.
Let's look at an example of method of exhaustion.
In an unordered array, we want to search the element of K.
Since there is no hint, we can just search one by one which is a process of exhaustion.
For the algorithm, we leave the first position of the array out as the lookout and place the value of K in it.
We search forward from the last element of the array.
If we find the element in the process of searching forward, we'll return its corresponding subscript.
We'll stop searching if we search forward to the first position of the array.
Because the value of K is put there as the lookout.
The function of setting lookout is to avoid the judgement of whether the suscript i has go beyond the lower bound of the array.
Effieciency of the algorithm will be higher without the judgement.
Let's look at a more effective method for finding the value of K.
The method requires the array to be sorted. In that way, we can find the value of K more quickly.
In the middle of the array, we compare the value with K
If it is equal, the algorithm ends.
If the element in the middle of the array is smaller than K, we'll find in the right part of the array.
If the element in the middle of the array is bigger than K, we'll find in the left part of the array.
Every time we fail to search, the scale will decrease to half-size, then we continue to search.
So it is a very effective algorithm.
Let's look at the algorithm of finding K using binary search.
Firstly ,we introduce the array, its length and the value of K.
I set the lower bound and upper bound of the search interval as 1 and the length of the array.
We leave the position which is indexed zero in the array out.
We get the index of the middle position mid, and compare the value in the position of mid with K.
If it is equal, we returns mid.
If k is smaller than the value in the position of mid with K, we'll search in the left part of the array and set the lower bound as the position of mid -1.
If k is bigger than the value in the position of mid with K, we'll search in the right part of the array and set the upper bound as the position of mid +1.
If no value is found to be equal to K until low < high which means the lower bound goes beyond the upper bound, the search process fails and returns 0.
It means the value K can not be found in the data area of 1 to length and the search fails.
Let's look at the graphical representation of the binary search.
We set the subscript low and high as the lower bound and upper bound.
mid is the middle position, and its index is 5.
The element we are searching for is 18.
18 is smaller than the 35 which is the value of the element indexed 5.
So we decrease the upperbound to mid - 1 and continue searching in the left part.
The median of the left part is 17 which is smaller than 18.
So we continue to search in the right part of the search interval.
The index of the middle position of the right part is 3, and its value is 18 , we find the data.
We can see the process is much quicker than the method of exhaustion which we search one by one.
Let's think for a while.
An algorithm requires you to move the elements of the array to the right place by k positions circularly.
For example, there is an array with 10 elements from zero to nine, I require to rotate by 3 positions, and the element of zero will move to 3 positions after the initial position of it.
It jusmps 3 positions, and the elements of 7 8 9 is folded over.
We get a new array.
The algorithm has constraints of time and space.
The so-called space constraint is that you can just use one auxiliary variable in the process of operating.
The size of the variable is constrained to the size of the array element.
The time constraint is that in the process of moving, the total number of moving and exchanging is only linearly correlated with n.
In other words, you cannot get an algorithm with the scale of the square of n.
Under such restrictions how will you to consider about the design of the algorithm?
This problem brings in the analysis of the efficiency of time and space which we'll talk about in the next section.
Thank you!