here is an interesting situation. Different people have different need.
For example, programmer need to develop a working solution. Client wants to solve problem efficiently. Theoretician wants to understand.
So we need to have a correct way to analysis our program.
which means when we know the data size and the program we write. we should predict the performance. we also can compare the algorithms which is with better performance.
The most important thing is that we should avoid performance bugs.
Clients get poor performance usually because poor programmer.
image.png
How measure the running time.
image.png
there is a good way to estimate the time complexity of your program is doublling hypothesis.
image.png
cost of basic operation
image.png
how many instruction below
image.png
to simplify it, we use tilde notation
Estimate running time (or memory) as a function of input size N.
Ignore lower order terms.
when N is large, terms are negligible
when N is small, we don't care
Common order of growth classification
image.png
image.png
image.png
Types of analyses
in an algorithm, there are three situation. best, worst, average
The best case is the lower bound on cost. it determined by "easiest" input. think as insertion sort with an already sort input.
The worst case it the upper bound on cost. it determined by "most difficult" input. think as the already sort input with a naive quick sort.
The average case is expected cost for random input. and we can provide a way to predict performance.
image.png
thus, the theory of algorithm should establish difficulty of a problem and develop optimal algorithm
we can suppress details in analysis, and we should care the worst case.
image.png
an specific algorithm usually have an upper bound. the lower bound is that we should proof the no algorithm can do better. For example, 1-sum lower bound is n, because at least we need to check all the element once in the input.
The optimal algorithm is that lower bound equals upper bound.
Memory
image.png
image.png
image.png
Quiz analysis
Q1
image.png
Solution: as we known, if we solve the 2-sum when the input is sorted. we can use two point which one is from the beginning, and another is from the ending. check the sum of the two pointer is bigger or smaller than the target to decide move which pointer. which time complexity is O (n)
the 3 sum is same, we can use one point from 0 - n, then make this problem in each for loop as a two sum problem.
Q2
image.png
Solution: the 3lgn method is naive. we can use binary search to find the peak of the bitonic array. if the point is increasing, we know peak is on the right. if is decreasing, we know the peak is on the left.
after knowing the peak, we just run another two binarysearch for the increasing part and decresing part to find the target.
the 2lgn method is nifty. we can search in the middle. if the point is in the decreasing tendency, if the target is larger than the middle. we can throw away right part. same as the increasing tendency.
image.png
the tricky part is happened on when the tar is smaller than the mid. now it have possibility on the left part and right part.
image.png
the interesting thing is when it is on the left part. even though the left array is not sorted but we still can run the binary search on it. because we know the target will not in the part larger than mid.
image.png
so the time complexity if in the first case, is lg n, if on the second cases, we need to run two binary search on the left side and right side, which is 2lgn
so the worst is 2lgn.
Q3
image.png
the idea behind the egg drop is that when we only have 1 egg, we have no choice, to find the target floor, we need brute force search from the bottom to top.
that is solution to version 0.
version 1 we have lg n eggs and lg n tosses.which function u can toss lgn, yes binary search. we can toss and n/2, if it break, then n/4 . if not break, go 3n/4. and so on.
version 2, eggs is lg T, and we have 2 lgT tosses. because at the beginning we do not know what exactly T is. so use first lg T tosses from 1,2,4,... to find the nearest 2^K = T. k = lgT. then use binary search with in k to find the T.
version 3, we only have two egg. and the tosses the 2 sqrt n. so the same thought we use 1 egg and sqrt N tosses to minimize range to sqrt n, so use another egg to brute force.
the question is that how to minimize range with 1 egg and sqrt N tosses. the answer is also use sqrt. we can toss on sqrt n, 2 * sqrt n, .... sqrt n * sqrt n
then search in k sqrt n to k+1 sqrt n.
version 4, idea is similar to above. the difference is that now we don't know the T is at the beginning. so we need to use 1 egg to find the nearest number to sqrt T.
so the tosses way is 1,4,9, 16...., find the number so use the brute force search.
course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226
网友评论