北京郵電大學(xué)--計(jì)算機(jī)學(xué)院--離散數(shù)學(xué)-3.2&3.3-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(

33、x)|}?(g) :? {f | g?O(f)}?(g) :? O(g) ? ?(g),25,2024/3/18,College of Computer Science & Technology, BUPT,Homework,§3.2 26, 28, 62,26,2024/3/18,College of Computer Science & Technology, BUPT,What is comple

34、xity?,The word complexity has a variety of different technical meanings in different research fields.There is a field of complex systems, which studies complicated, difficult-to-analyze non-linear and chaotic natural &a

35、mp; artificial systems.Another concept: Informational or descriptional complexity: The amount of information needed to completely describe an object.As studied by Kolmogorov, Chaitin, Bennett, others… In this course,

36、we will study algorithmic or computational complexity.,27,2024/3/18,College of Computer Science & Technology, BUPT,§3.3: Algorithmic Complexity,The algorithmic complexity of a computation is, most generally, a m

37、easure of how difficult it is to perform the computation.That is, it measures some aspect of the cost of computation (in a general sense of “cost”).Amount of resources required to do a computation.Some of the most com

38、mon complexity measures:“Time” complexity: # of operations or steps required“Space” complexity: # of memory bits req’d,28,2024/3/18,College of Computer Science & Technology, BUPT,An interesting aside...,Another, in

39、creasingly important measure of complexity for computing is energy complexity – How much total physical energy is used up (rendered unavailable) as a result of performing the computation?Motivations: Battery life, ele

40、ctricity cost, computer overheating!Computer performance within power constraints.I research & develop reversible circuits & algorithms which reuse energy, trading off energy complexity against spacetime comple

41、xity.,29,2024/3/18,College of Computer Science & Technology, BUPT,Complexity Depends on Input,Most algorithms have different complexities for inputs of different sizes. E.g. searching a long list typically takes mo

42、re time than searching a short one.Therefore, complexity is usually expressed as a function of the input length.This function usually gives the complexity for the worst-case input of any given length.,30,2024/3/18,Coll

43、ege of Computer Science & Technology, BUPT,Complexity & Orders of Growth,Suppose algorithm A has worst-case time complexity (w.c.t.c., or just time) f(n) for inputs of length n, while algorithm B (for the same ta

44、sk) takes time g(n).Suppose that f??(g), also written .Which algorithm will be fastest on all sufficiently-large, worst-case inputs?,B,31,2024/3/18,College of Computer Science & Technology, BUPT,Example

45、 1: Max algorithm,Problem: Find the simplest form of the exact order of growth (?) of the worst-case time complexity (w.c.t.c.) of the max algorithm, assuming that each line of code takes some constant time every time it

46、 is executed (with possibly different times for different lines of code).,32,2024/3/18,College of Computer Science & Technology, BUPT,Complexity analysis of max,procedure max(a1, a2, …, an: integers) v := a1

47、 t1 for i := 2 to n t2 if ai > v then v := ai t3 return v t4First, what’s an expression for the exact total worst-case time? (Not its order of growth.),,Times for each execut

48、ion of each line.,33,2024/3/18,College of Computer Science & Technology, BUPT,Complexity analysis, cont.,procedure max(a1, a2, …, an: integers) v := a1t1 for i := 2 to nt2 if ai > v the

49、n v := ait3 return vt4w.c.t.c.:,,Times for each execution of each line.,34,2024/3/18,College of Computer Science & Technology, BUPT,Complexity analysis, cont.,Now, what is the simplest form of the exact (

50、?) order of growth of t(n)?,,35,2024/3/18,College of Computer Science & Technology, BUPT,Example 2: Linear Search,procedure linear search (x: integer, a1, a2, …, an: distinct integers)i := 1t1while (i ? n ? x

51、 ? ai)t2 i := i + 1t3 if i ? n then location := it4 else location := 0t5 return locationt6,36,2024/3/18,College of Computer Science & Technology, BUPT,Linear search analysis,Worst case time complex

52、ity order:Best case:Average case, if item is present:,37,2024/3/18,College of Computer Science & Technology, BUPT,Review §3.3: Complexity,Algorithmic complexity = cost of computation.Focus on time complexit

53、y for our course.Although space & energy are also important.Characterize complexity as a function of input size: Worst-case, best-case, or average-case.Use orders-of-growth notation to concisely summarize the grow

54、th properties of complexity functions.,38,2024/3/18,College of Computer Science & Technology, BUPT,Example 3: Binary Search,procedure binary search (x:integer, a1, a2, …, an: distinct integers, sorted smallest to lar

55、gest) i := 1 j := nwhile iam then i := m+1 else j := mendif x = ai then location := i else location := 0return location,,,,?(1),?(1),?(1),Key question:How many loop iterations?,39,2024/3/18,College of Computer Sc

56、ience & Technology, BUPT,Binary search analysis,Suppose that n is a power of 2, i.e., ?k: n=2k.Original range from i=1 to j=n contains n items.Each iteration: Size j?i+1 of range is cut in ~half.Loop terminates wh

57、en size of range is 1=20 (i=j).Therefore, the number of iterations is: k = log2n = ?(log2 n)= ?(log n)Even for n?2k (not an integral power of 2),time complexity is still ?(log2 n) = ?(log n).,40,2024/3/18,Colle

58、ge of Computer Science & Technology, BUPT,Names for some orders of growth,?(1)Constant?(logc n)Logarithmic (same order ?c)?(logc n)Polylogarithmic?(n)Linear?(nc)Polynomial (for any c)?(cn) Exponential

59、(for c>1)?(n!)Factorial,(With ca constant.),41,2024/3/18,College of Computer Science & Technology, BUPT,Problem Complexity,The complexity of a computational problem or task is (the order of growth of) the comp

60、lexity of the algorithm with the lowest order of growth of complexity for solving that problem or performing that task.E.g. the problem of searching an ordered list has at most logarithmic time complexity. (Complexity

61、is O(log n).),42,2024/3/18,College of Computer Science & Technology, BUPT,Tractable vs. intractable,A problem or algorithm with at most polynomial time complexity is considered tractable (or feasible). P is the set

62、of all tractable problems.A problem or algorithm that has complexity greater than polynomial is considered intractable (or infeasible).Note that n1,000,000 is technically tractable, but really very hard. nlog log log

63、n is technically intractable, but easy. Such cases are rare though.,43,2024/3/18,College of Computer Science & Technology, BUPT,Computer Time Examples,Assume time = 1 ns (10?9 second) per op, problem size = n bits,

64、and #ops is a function of n, as shown.,(125 kB),(1.25 bytes),44,2024/3/18,College of Computer Science & Technology, BUPT,Unsolvable problems,Turing discovered in the 1930’s that there are problems unsolvable by any a

65、lgorithm.Or equivalently, there are undecidable yes/no questions, and uncomputable functions.Classic example: the halting problem.Given an arbitrary algorithm and its input, will that algorithm eventually halt, or wil

66、l it continue forever in an “infinite loop?”,45,2024/3/18,College of Computer Science & Technology, BUPT,The Halting Problem (Turing‘36),The halting problem was the first mathematical function proven to have no algo

67、rithm that computes it! We say, it is uncomputable.The desired function is Halts(P,I) :≡ the truth value of this statement: “Program P, given input I, eventually terminates.”Theorem: Halts is uncomputable!I.e.,

68、there does not exist any algorithm A that computes Halts correctly for all possible inputs.Its proof is thus a non-existence proof.Corollary: General impossibility of predictive analysis of arbitrary computer programs

69、.,Alan Turing1912-1954,46,2024/3/18,College of Computer Science & Technology, BUPT,Proving the Theorem,Given any arbitrary program H(P,I),Consider algorithm Foiler, defined as:procedure Foiler(P: a program)halts

70、 := H(P,P)if halts then loop foreverNote that Foiler(Foiler) halts iff H(Foiler,Foiler) = F.So H does not compute the function Halts!,Foiler makes a liar out of H, by simply doing the opposite of whatever H predic