文档介绍：1
2021/8/3
Review of last class
The framework of analyzing the time efficiency of an algorithm
The best-case, worse-case and average-case analysis
Rate of growth and three asymptotic notations , , O
2
2021/8/3
Fundamentals of the Analysis of Algorithm Efficiency
(II)
Chapter 2
1、 Formal definition of three asymptotic notations 2、 Mathematical Background 3、 Analysis of non-recursive algorithms
3
2021/8/3
Goals of this lecture
At the end of this lecture, you should
Master the three asymptotic notations , , O
Be familial with the basic mathematical tools
Master the analysis of non-recursive algorithms
4
2021/8/3
Asymptotic Notation:
-notation: asymptotic lower bound
Call f(n) = (g(n)) if there exist positive constants c and n0 such that 0 cg(n) f(n) for all n n0.
f(n) = 2n3+3n-5 = (n3)
f(n) = 2n3+3n-5 = (n2)
In the analysis literature, f(n) = (g(n)) means f(n) (g(n))
5
2021/8/3
Asymptotic Notation:
n
cg(n)
f(n)
n0
f(n) = (g(n))
6
2021/8/3
Asymptotic Notation:
-notation:
Call f(n) = (g(n)) if there exist positive constants c1, c2, and n0 such that
0 c1g(n) f(n) c2g(n) for all n n0.
f(n) = 2n3+3n-5 = (n3)
f(n) = 2n4+1 = (n3) ???
7
2021/8/3
Asymptotic Notation:
f(n) = (g(n))
n
f(n)
c2g(n)
n0
c1g(n)
8
2021/8/3
Useful properties of asymptotic notations
f(n) O(f(n))
f(n) O(g(n)) iff g(n) (f(n))
If f (n) O(g (n)) and g(n) O(h(n)) ,
then f(n) O(h(n))
If f1(n) O(g1(n)) and f2(n) O(g2(n)) ,
then f1(n) + f2(n) O(max{g1(n), g2(n)})
9
2021/8/3
Using Limits for Comparing Orders of Growth
A much more convenient method for comparing the orders of growth of two specific functions is based on computing the limit of the ratio of two functions:
The first two cases, say , mean that f(n) O(g(n))
The last two cases, say , mean that f(n) (g(n))
The second cases, say , mean that f(n