Hello,everyone.
We will continue with the first section of the Data Structure and Algorithm.
Today, we mainly introduce the measure of algorithm efficiency.
We must concern about the time and space performance after we design an algorithm especially the space performance.
For an algorithm like this ,if we divide it into several algorithm segment just as the four parts show/
It is obvious that the square of n is the most important part of it.
When n is large enough, other parts can be neglected.
So we mainly focus on the growth of the algorithm, especially when n grows to a certain scale, what level is the algorithm, linearly or n square or exponential.
The measurement of the algorithm makes it easier for us to estimate whether we can solve the problem in a time which we can put up with.
O notation is the most important analysis in the complexity analysis of algorithm.
Suppose the complexity function of the algorithm is f, if we can find a function g that when the scale of the problem is equal or larger than n0, there is a positive number c which makes f(n) equal to or smaller than cg(n), then f(n) is called in the set of O(n).
It also can be represented as f（n）=O（g（n））
O notation express the upper bound of growth of functions, which means the complexity of the algorithm will be no than the scale of g(n).
The upper bound may be more than one , it is best to find the most "tight" one.
There is another corresponding definition that the lower bound of the algorithm is O.
When the upper bound and the lower bound are the same, we represent is as Θ.
In many cases of data structure and algorithm, O notation and Θ notation are almost the same.
So many textbooks just talk about O notation.
For students non-computer major students, we just require you to master O notation.
You can understand Θ as O when you see it.
Let's look at the graphical representation of O notation.
The O notation means for the complexity function f(n), we need to find cg(n) that when n is larger than n0, the growth of cg(n) is larger than f(n). In other words, g(n) is larger than f(n), multiplied by a positive parameter c.
When we look at the graphical representation, we can see that f(n) may go beyond cg(n) in some situations when n is less than n0.
It doesn't matter.
We don't care about special situations of small scale like this.
When n is large enough, g(n) is the upper bound of f(n).
And in fact, we don't care about the definite value of c.
It means in the measurement of algorithm
we consider about the largest part of f(n), the coefficient of this part and the lower order polynomial behind it can be get rid of.
How to measure O notation?
We just need to the see the basic operation of the algorithm.
Bool operation and arithmetical operation take O(1) time.
It's the same with some simple IO operation. Simple operation mainly reads elements from memory or passes parameter.
But it doesn't contain operation of file or keyboard. They are IO operations of peripheral which take a lof of time and are uncontrollable.
O notation has two important operational rule.
The first one is the addition rule. If there are two code segment whose complexity is f1 and f2 individually. The most part we concerned about or the most time consuming part is the code segment with larger complexity.
The sequential structure, the decision structure and the switch structure are accustomed to addition rule.
The other rule is the multiplication rule.
For nested program segment, the algorithm cost of the inner loop and the outer loop must be multiplied together.
The total time taken is the product of these two loop.
The multiplication rule can be applied for loop structure like for and while.
Let's see the example, and we can find it is bicirculating, each loop is in the scale of n, and multiplied them together and get the scale of square of n.
And we can see the algorithm complexity we concerned about. The coefficients and the lower order item can be neglected.
In asymptotic algorithm analysis, there is Ω notation.
It is opposite to O notation.
We care the lower bound of the algorithm.
It means there is positive number c and no that when n is larger than n0, we can find f(n) which is larger than cg(n). In other words, f(n) is larger than g(n).
We also represent it as f（n）=Ω（g（n））
The lower bound of Ω notation may be more than one.
We usually need to find the most "tight" one.
From the graphical representation of Ω notation, we can see that it is similiar to O notation. We need to find a n0 that when n is larger than n0, f(n) is larger than cg(n).
We neglect the c, and say the lower bound of f(n) is Ω(g（n）).
When the lower bound is the same with the upper bound, it is a specific bound ,we use the Θ notation.
So we can have two inequation to define f(n).
The lower bound is c1g（n） and the upper bound is c2g（n） while f(n) is in the middle.
And when n is larger than n0, f(n) is in the middle of c1c1g（n）and c2g（n).
After we get the progressive growth rate of the algorithm, we can use it to compare with the growth curve of other functions and we can find that n is grown linearly,
In usual cases, many algorithms are related with its data scale n.
If you can find algorithm with complexity of logn, it is very effective.
But in some cases, we may need a constant algorithm.
For the example of engine, when the results of the indexs return, we'd like to have response speed of O(1).
We may use some special index and search strategy.
The growth rate of nlogn is very close to n when n is very large.
Many sort algorithms are very effective because complexity of them is nlogn.
When n is large enough, algorithm with the complexity of the square of n works quite slow.
For example, we have some sort methods with low efficiency whose complexity is O(n*n).
These algorithms could'r work well when n is above 1 milion.
There are some algorithm whose complexity is exponential.
These algorithms are quite complicated and can only handle with cases that n is small.
If we meet with some bad data, in these cases, our algorithm can be quite slow.
On the other hand, if we meet with good data , and in the best case, we can get the solution quickly. And most cases we meet with data neither good or bad.
The cost we calculated for these data is the average cost of the algorithm.
In mant cases, we need to consider in the worst and best and the average case, what is the time cost.
For the best case, we can take advantage of the special input case and assemble some rather good algorithm.
This kind of case exists in our sort algorithm.
For the worst case, we need to consider in some extreme condition , whether we can solve problem space like this or not.
For example. many software systems of us need to have pressure test to consider the worst case.
The average case is considered to see the performance of an algorithm in statistical sense.
We introduced several algorithms before, let's look at the example of finding k in order.
In the best case, the first element if compares is the value k searching for, and it takes O(1) time.
In the worst case, it will find the element until the last one or fail to find it at last.
The time taken will be O(n).
If we look at the average case. we suppose these values are distributed with same possibility. It means the possibility of k that occurs in every position is 1/n. And the cost of the algorithm in the average case is O(n).
Let's look at the case with diverse possibility. I suppose the possibility of k occurs in position 1 is 1/2, and that in position 2 is 1/4, and that in other places is shown as the equation. And we can get a result that is still O(n).
The method of binary search of K is a divide and conquer method. And the best case is that the first middle value is just the element we are searching for and it takes O(1) time.
What about the worst and the average case? Let's look at the example of binary search.
In fact, we can use a decision tree to observe the performance, the largest search length and the search length when search fails.
In the worst case ,the level we need to decline in the search tree is in the scale of logn.
So our largest search length and the search length when it fails are all in the scale of logn.
The average searching cost is O(logn).
Take care that our representation doesn't give the base of logn.
In the analysis of complexity of algorithm ,we mainly takes 2 as the base. Besides, because of the base changing formula, it is the same to use 10 or others as the base in the sense of O notation.
Because we don't care about the coefficients.
The space cost and time cost analysis method of the algorithm are similar to each other.
What we talked before are mainly about O notation,Θ notation from the view of the time.
We can also use this series of notation to observe our space cost.
Space cost is mainly related with the auxiliary space of the algorithm. In other words, how much temporary variable space do I need to complete the operation of the algorithm.
The tradeoff of time and space is a very inportant question in data structure.
Because when we are trying to solve the problem, we need some space to place related data and also need some time to execute the code of the algorithm.
So constraints of time and space are required in many applications.
Besides, the constraints and requirements of some software engineering must be also considered.
In usual cases, if we add space of the algorithm, we may get better perfomance if I allocate larger arrays.
On the other hand, if we have to save the space, we may need to consider more about the design of the algorithm. It means we may increase the time cost or the burden of writing the algorithm.
The tradeoff of time and space are questions we must consider carefully.
When we choose about the data structure and the algorithm, we must consider what is the question of us. It means we should think about what kind of data structure to express the data space of the question around the aim of the problem solving.
Then we consider to use what kind of algorithm to solve it.
In many cases, the design of data structure is prior to the design of algorithm.
Obviously, there are some problems that we can easily map it to a classical algorithm.
Then we consider to use some corresponding storage method to implement it.
We also need to consider the extendibility of data structure because the algorithm is very likely to be related with the problem scale.
When n is large enough, whether is our algorithm used to it?
For example the time cost of a linear algorithm is O(n), and it works well in usual cases.
But in the environment of search engine, we are faced with web pages with scale of several hundred million. If the time cost of the algorithm is linear, it may not meet our search demand. Some special index and search handling may be needed.
Finally leave you a few thinking questions.
First, we choose the data structure and algorithm mainly for problem solving.
what is the aim of problem solving.
We can see several examples.
In the process of choosing data structure and algorithm, how do we consider and what do we consider first, how is the process going on?
Besides we look back on the three factors of data structure, that is its logical structure, storage structure and operation.
Once one factor changes, we can think it as a different data structure.
Thank you!