Slide 1So far…Now...Measuring CostWhat Does Cost Mean?Cost Measures (Time)ExampleAsymptotic CostBig-OhExampleDefinitionSlide 12ExamplesMore ExamplesImportant Big-Oh SetsExampleCaveats About ConstantsCaveats About ConstantsCaveats About ConstantsOmegaExamplesDefinitionSlide 23ThetaSlide 25InterpretingAnalysis Example 1Analysis Example 2Analysis Example 3CS 61B Data Structures and Programming Methodology July 10, 2008David SunSo far…•We’ve been mainly looking at–the syntax of the Java language.–key ideas in object-oriented programming: objects, inheritance, polymorphism, and dynamic binding, access privileges. –mechanisms provided in Java for organization of abstractions: abstracted classes, interfaces, packages.–Head First Java Chapter 1 - 11Now...•We are going to continue our voyage with Java, but with a different focus.•We are going to examine– a range of canonical data structures.–algorithms often associated with these data structures.–the focus is on the efficiency and cost of these algorithms and data structures.Measuring CostWhat Does Cost Mean?•Cost can mean–Development costs: How much engineering time? When delivered?–Costs of failure: How robust? How safe?–Operational cost (for programs, time to run, space requirements).•Is this program fast enough? Depends on:–What purpose.–What input data.Cost Measures (Time)•Cost Measures (Time)–Wall-clock or execution time–You can do this at home:time java FindPrimes 1000–Advantages: easy to measure, meaning is obvious. Appropriate where time is critical (real-time systems, e.g.).–Disadvantages: applies only to specific data set, compiler, machine, etc.•Number of times certain statements are executed:–Advantages: more general (not sensitive to speed of machine).–Disadvantages: still applies only to specific data sets.•Symbolic execution times:–Formulas for execution times or statement counts in terms of input size.–Advantages: applies to all inputs, makes scaling clear.–Disadvantage: practical formula must be approximate, may tell very little about actual time.Example•An algorithm for processing a retail store's inventory takes: –10,000 ms to read the initial inventory from disk, and then –10 ms to process each transaction–Processing n transactions takes (10,000 + 10 * n) ms.–10 * n is more important if n is very large.Asymptotic Cost•The constant coefficients can change:–If we had a faster computer or,–Use a different language or compiler. •The constant factors can get smaller as technology improves.•We want to express the speed of an algorithm independently of a specific implementation on a specific machine. •We examine the cost of the algorithms for large input sets i.e. the asymptotic cost.Big-Oh•Specify bounding from above:–Big-Oh says how slowly code might run as its input size grows. •Let n be the size of a program's input. Let T(n) be a function that equals to the algorithm's running time, given an input of size n. •Let f(n) be another function. We say that if and only if whenever n is big, and for some constant c.)(*)( nfcnT ))(()( nfOnT •Consider the cost function: T(n) = 10,000 + 10 * n,•Let's try out f(n) = n. We can choose c as large as we want:Example•As these functions extend forever to the right (infinity), their lines will never cross again. –For any n bigger than 1000, T(n) ≤ c * f(n).Definition•O(f(n)) is the set of all functions T(n) that satisfy: –There exist positive constants c and N such that, for all•In the example above: c = 20, and N = 1000.)(*)(, nfcnTNn •T(n) ≤ 2f(n) whenever, n ≥ 1•So: T(n) is in O(f(n))•Notice T(n) > f(n) everywhere.2f(n)f(n)T(n)Examples•If T(n) = 1,000,000 * n, T(n) is in O(n). –Let f(n) = n, set c = 1,000,000, N = 1: T(n) = 1,000,000 * n ≤ c * f(n)–Big-Oh notation doesn't care about (most) constant factors. –Generally leave constants out; it's unnecessary to write O(2n).•If T(n) = n, T(n) is in O(n3). –Let f(n) = n3, set c = 1, N = 1: T(n) = n ≤ n3 = f(n)–Big-Oh notation can be misleading. Just because an algorithm's running time is in O(n3) doesn't mean it's slow; it might also be in O(n).More Examples•If T(n) = n3 + n2 + n, then T(n) is in O(n3).–Let T(n) = n3, set c = 3, N = 1. T(n) = n3 + n2 + n ≤ 3 * n3 = c * f(n)–Big-Oh notation is usually used only to indicate the dominating term in the function. The other terms become insignificant when n is really big.Important Big-Oh SetsFunction Common NameO(1) ConstantO(log n) LogarithmicO( log2 n) Log-squaredO( ) Root-nO(n) LinearO(n log n) n log nO(n2) QuadraticO(n3) CubicO(n4) QuarticO(2n) Exponential O(en) Bigger exponentialSubset of nExample/** Find position of X in list Return -1 if not found */class List { . . . int find (Object X) {int c = 0;ListNode cur = head;for (; cur != null; cur = cur.next, c++) { if (cur .item.equals (X)) return c; }return -1;}•Choose representative operation: number of .equals tests.•If N is length of the list, then loop does at most N tests: worst-case time is N tests. •Worst-case time is O(N);Caveats About Constants•n2 is in O(n)–Justification: if we choose c = n, we get n2 ≤ n2. –c must be a constant; it cannot depend on n.WRONG!Caveats About Constants•e3n is in O(en) because the constant factor 3 don't matter.•10n is in O(2n) because the constant factor 10 don't matter.•Big-Oh notation doesn't care about most constant factors. But…•Constant factor in an exponent is not the same as a constant factor in front of a term. –e3n is bigger than en by a factor of e2n–10n is bigger than 2n by a factor of 5n.WRONG!WRONG!Caveats About Constants•Problem actual size does matter in practice.•Example:–An algorithm runs in time T(n) = n log n, and another algorithm runs in time U(n) = 100 * n–Big-Oh notation suggests you should use U(n), because T(n) dominates U(n) asymptotically. –In practice, U(n) is only faster than T(n) if your input size is greater than current estimates of the number of subatomic particles in the universe. –For U(n) ≤ T(n), 100 ≤ log n, 2100 ≤ nOmega•Big-Oh is an upper bound, it says, "Your algorithm is at least this good."•Omega gives us a lower bound, it says, "Your algorithm is at least this bad."•Omega is the reverse of Big-Oh: –If T(n) is in O(f(n)), f(n) is in Ω(T(n)).Examples•2n is in Ω(n) because n is in O(2n). •n2 is in Ω(n) because n is in
View Full Document
Unlocking...