北京郵電大學(xué)--計(jì)算機(jī)學(xué)院--離散數(shù)學(xué)-3.2-growth-of-functions

1、Growth of Functions(函數(shù)增長(zhǎng)),,2,2024/3/18,College of Computer Science & Technology, BUPT,The Growth of Functions,We quantify the concept that g grows at least as fast as f.What really matters in comparing the complexit

2、y of algorithms?We only care about the behavior for large problems.Even bad algorithms can be used to solve small problems.Ignore implementation details such as loop counter incrementation, etc. We can straight-line a

3、ny loop.,3,2024/3/18,College of Computer Science & Technology, BUPT,Orders of Growth (§3.2),For functions over numbers, we often need to know a rough measure of how fast a function grows.If f(x) is faster growi

4、ng than g(x), then f(x) always eventually becomes larger than g(x) in the limit (for large enough values of x).Useful in engineering for showing that one design scales better or worse than another.,4,2024/3/18,College o

5、f Computer Science & Technology, BUPT,Orders of Growth - Motivation,Suppose you are designing a web site to process user data (e.g., financial records).Suppose database program A takes fA(n)=30n+8 microseconds to pr

6、ocess any n records, while program B takes fB(n)=n2+1 microseconds to process the n records.Which program do you choose, knowing you’ll want to support millions of users?,A,5,2024/3/18,College of Computer Science &

7、Technology, BUPT,Visualizing Orders of Growth,On a graph, asyou go to theright, the faster-growing func-tion always eventuallybecomes thelarger one...,,,,,fA(n)=30n+8,Increasing n ?,fB(n)=n2+1,Value of function ?,

8、6,2024/3/18,College of Computer Science & Technology, BUPT,Concept of order of growth,We say fA(n)=30n+8 is (at most) order n, or O(n).It is, at most, roughly proportional to n.fB(n)=n2+1 is order n2, or O(n2). I

9、t is (at most) roughly proportional to n2.Any function whose exact (tightest) order is O(n2) is faster-growing than any O(n) function.Later we will introduce Θ for expressing exact order.For large numbers of user reco

10、rds, the exactly order n2 function will always take more time.,7,2024/3/18,College of Computer Science & Technology, BUPT,The Big-O Notation,Definition: Let f and g be functions from N or R to R. Then g asymptotical

11、ly dominates(漸進(jìn)地支配) f, denoted f is O(g) or 'f is big-O of g, iff$k$c"n[n > k®| f (n) |£c | g(n) |]“f is at most order g”, or “f is O(g)”, or “f=O(g)” all just mean that f?O(g).Note:Choose kCho

12、ose c; it may depend on your choice of kOnce you choose k and c, you must prove the truth of the implication (often by induction),8,2024/3/18,College of Computer Science & Technology, BUPT,Points about the definitio

13、n,Note that f is O(g) so long as any values of c and k exist that satisfy the definition.But: The particular c, k, values that make the statement true are not unique: Any larger value of c and/or k will also work. You

14、are not required to find the smallest c and k values that work. (Indeed, in some cases, there may be no smallest values!),However, you should prove that the values you choose do work.,9,2024/3/18,College of Computer Sci

15、ence & Technology, BUPT,little-o of g,In calculusIfThenf is o(g) (called little-o of g),10,2024/3/18,College of Computer Science & Technology, BUPT,Theorem,If f is o(g) then f is O(g).Proof: by definition

16、of limit as n goes to infinity, f(n)/g(n) gets arbitrarily small.That is for any e >0, there must be an integer N such that when n > N, | f(n)/g(n) | < e .Hence, choose c = e and k = N.Q. E. D.,11,2024/3/18,C

17、ollege of Computer Science & Technology, BUPT,Example,3n + 5 is O(n2)Proof: It's easy to showusing the theory of limits.Hence 3n + 5 is o(n2) and so it is O(n2).Q. E. D.,12,2024/3/18,College of Computer Sci

18、ence & Technology, BUPT,Example,13,2024/3/18,College of Computer Science & Technology, BUPT,“Big-O” Proof Examples,Show that 30n+8 is O(n).Show ?c,k: ?n>k: 30n+8 ? cn.Let c=31, k=8. Assume n>k=8. Thenc

19、n = 31n = 30n + n > 30n+8, so 30n+8 k: n2+1 ? cn2.Let c=2, k=1. Assume n>1. Then cn2 = 2n2 = n2+n2 > n2+1, or n2+1< cn2.,14,2024/3/18,College of Computer Science & Technology, BUPT,Note 30n+8 isn’tle

20、ss than nanywhere (n>0).It isn’t evenless than 31neverywhere.But it is less than31n everywhere tothe right of n=8.,Big-O example, graphically,,,,Increasing n ?,Value of function ?,,n,30n+8,30n+8?O(n),15,2024/3

21、/18,College of Computer Science & Technology, BUPT,Some important Big-O results,Theorem 1Let f(x) = anxn + an-1xn-1 +…+ a1x+a0 ,where a0 , a1 , … an-1, an are real numbers. Then f(x) is O(xn) .n! is O(nn)log n! i

22、s O(nlogn)log n is O(n)1, log n, n, nlogn, n2, 2n, n!,16,2024/3/18,College of Computer Science & Technology, BUPT,The growth of combinations of functions,Theorem 2Suppose that f1 is O(g1) and f2 is O(g2) .Then f

23、1 + f2 is O(max{ g1, g2})Corollary 1If f1 , f2 are both O(g) then f1 + f2 is O(g).Theorem 3Suppose that f1 is O(g1) and f2 is O(g2) .Then f1f2 is O(g1g2),17,2024/3/18,College of Computer Science & Technology, B

24、UPT,Proof of f1f2 is O(g1g2),There is a k1 and c1 such that1. f1(n) k1.There is a k2 and c2 such that2. f2(n) k2.We must find a k3 and c3 such that3. f1(n)f2(n) k3.,18,2024/3/18,College of Computer Science &

25、Technology, BUPT,Proof of f1f2 is O(g1g2),We use the inequalityif 0 max{k1, k2} so that both inequalities 1 and 2. hold at the same time.Therefore, choosec3 = c1c2andk3 = max{k1, k2}.Q. E. D.,19,2024/3/18,College

26、of Computer Science & Technology, BUPT,Example,Find the complexity class of the function(nn!+ 3n+2 + 3n100 )(nn + n2n )Solution:This means to simplify the expression.Throw out stuff which you know doesn't gro

27、w as fast. And at last:nn! nn,20,2024/3/18,College of Computer Science & Technology, BUPT,Big-omega notation,Definition: Let f and g be functions from N or R to R. We say f is ?(g) or 'f is big- ? of g,' i

28、ff$k$c"n[n > k®| f (n) |?c | g(n) |]Note:Choose kChoose c; it may depend on your choice of kOnce you choose k and c, you must prove the truth of the implication (often by induction),21,2024/3/18,College

29、 of Computer Science & Technology, BUPT,Big-theta notation,If f?O(g) and g?O(f), then we say “g and f are of the same order” or “f is (exactly) order g” and write f??(g).Another, equivalent definition:?(g) ? {f:R?R

30、 | ?c1c2k>0 ?x>k: |c1g(x)|?|f(x)|?|c2g(x)| }“Everywhere beyond some point k, f(x) lies in between two multiples of g(x).”,22,2024/3/18,College of Computer Science & Technology, BUPT,? example,Determin

31、e whether:Quick solution:,23,2024/3/18,College of Computer Science & Technology, BUPT,,Theorem 4Let f(x) = anxn + an-1xn-1 +…+ a1x+a0 ,where a0 , a1 , … an-1, an are real numbers with an? 0 . Then f(x) is of order

32、 xn .,24,2024/3/18,College of Computer Science & Technology, BUPT,Review: Orders of Growth (§3.2),Definitions of order-of-growth sets, ?g:R?RO(g) :? {f | ? c>0 ?k ?x>k |f(x)| 0 ?k ?x>k |f(x)| < |cg(