华南理工大学数据结构chapter1 and chapter3.pptVIP

* It provides more information in this example to say O(n2) than O(n3). * * * * For polynomial equations on T(n), we always have ?. There is no uncertainty, since once we have the equation, we have a “complete” analysis. * * 2. Ignore constants. 3. Drop low order terms. 4. Useful for analyzing loops. * Asymptotic analysis is defined for equations. We need to convert programs to equations to analyze them. The traditional notation is ?(1), not ?(c). ?(n) even though the value of sum is n2. * First statement is ?(1). Double for loop is ?i = ?(n2). Final for loop is ?(n). Result: ?(n2). * First loop, sum is n2. Second loop, sum is (n+1)(n)/2. Both are ?(n2). * First loop is ?n for k = 1 to log n, or ?(n log n). Second loop is ?2k for k = 0 to log n - 1, or ?(n). * if statement: The probabilities for the then/else clauses being executed must be independent of n. switch statement: The probabilities of the various clauses being executed must be independent of n. * * * * Big-Omega Example T(n) = c1n2 + c2n. c1n2 + c2n = c1n2 for all n 1. T(n) = cn2 for c = c1 and n0 = 1. Therefore, T(n) is in ?(n2) by the definition. We want the greatest lower bound. * 3.4.3 Theta Notation When big-Oh and ? meet, we indicate this by using ? (big-Theta) notation. Definition: An algorithm is said to be ?(h(n)) if it is in O(h(n)) and it is in ?(h(n)). * A Common Misunderstanding Confusing worst case with upper bound. Upper bound refers to a growth rate. Worst case refers to the worst input from among the choices for possible inputs of a given size. * 3.4.4 . Simplifying Rules If f(n) is in O(g(n)) and g(n) is in O(h(n)), then f(n) is in O(h(n)). If f(n) is in O(kg(n)) for any constant k 0, then f(n) is in O(g(n)). If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)), then (f1 + f2)(n) is in O(max(g1(n), g2(n))). If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)) then f1(n)f2(n) is in O(g1(n)g2(n)). * 3.5. Running Time Examples (1) Example 1: a = b; This assignment takes cons