北京邮电大学 计算机学院 离散数学 3.23.3-Growth of Functions.ppt

* * College of Computer Science Technology, BUPT Example 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 is executed (with possibly different times for different lines of code). * * College of Computer Science Technology, BUPT Complexity analysis of max procedure max(a1, a2, …, an: integers) v := a1 t1 for i := 2 to n t2 if ai v then v := ai t3 return v t4 First, what’s an expression for the exact total worst-case time? (Not its order of growth.) Times for each execution of each line. * * College of Computer Science Technology, BUPT Complexity analysis, cont. procedure max(a1, a2, …, an: integers) v := a1 t1 for i := 2 to n t2 if ai v then v := ai t3 return v t4 w.c.t.c.: Times for each execution of each line. * * College of Computer Science Technology, BUPT Complexity analysis, cont. Now, what is the simplest form of the exact (?) order of growth of t(n)? * * College of Computer Science Technology, BUPT Example 2: Linear Search procedure linear search (x: integer, a1, a2, …, an: distinct integers)i := 1 t1while (i ? n ? x ? ai) t2  i := i + 1 t3 if i ? n then location := i t4 else location := 0 t5 return location t6 * * College of Computer Science Technology, BUPT Linear search analysis Worst case time complexity order: Best case: Average case, if item is present: * * College of Computer Science Technology, BUPT Review §3.3: Complexity Algorithmic complexity = cost of computation. Focus on time complexity 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 growth properties of complexity functions. * * College of Computer Scie