展开查看详情
1 .Growth Rates of Functions 3/26/12
2 .Asymptotic Equivalence Def: For example, Note that n 2 +1 is being used to name the function f such that f(n ) = n 2 +1 for every n 3/26/12
3 .An example: Stirling’s formula 3/26/12
4 .Little-Oh: f = o(g ) Def: f(n ) = o( g(n ) ) iff For example, n 2 = o( n 3 ) since 3/26/12
5 .= o ( ∙ ) is “all one symbol” “ f = o(g )” is really a strict partial order on functions NEVER write “ o(g ) = f ”, etc. 3/26/12
6 .Big-Oh: O(∙) Asymptotic O rder of Growth: “ f grows no faster than g ” A Weak Partial Order 3/26/12
8 .f = o(g ) implies f = O(g ) 3/26/12
9 .Big-Omega f = Ω(g ) means g = O(f ) “ f grows at least as quickly as g ” 3/26/12
10 .Big-Theta: 𝛩 (∙) “Same order of growth” 3/26/12
11 .Rough Paraphrase f∼g : f and g grow to be roughly equal f= o(g ): f grows more slowly than g f = O(g ): f grows at most as quickly as g f = Ω(g ): f grows at least as quickly as g f = 𝛩(g ): f and g grow at the same rate 3/26/12
12 .Equivalent Defn of O(∙) “F rom some point on, the value of f is at most a constant multiple of the value of g ” 3/26/12
13 .Three Concrete Examples Polynomials Logarithmic functions Exponential functions 3/26/12
14 .Polynomials A ( univariate ) polynomial is a function such as f(n ) = 3n 5 +2n 2 -n+2 (for all natural numbers n ) This is a polynomial of degree 5 (the largest exponent) Or in general Theorem: If a< b then any polynomial of degree a is o(any polynomial of degree b ) If a≤b then any polynomial of degree a is O(any polynomial of degree b ) 3/26/12
15 .Logarithmic Functions A function f is logarithmic if it is Θ(log b n ) for some constant b . Theorem: All logarithmic functions are Θ () of each other, and are Θ(any logarithmic function of a polynomial) Theorem: Any logarithmic function is o(any polynomial) 3/26/12
16 .Exponential Functions A function is exponential if it is Θ(c n ) for some constant c >1. Theorem: Any polynomial is o(any exponential) If c < d then c n = o(d n ). 3/26/12
17 .Growth Rates and Analysis of Algorithms Let f(n ) measure the amount of time taken by an algorithm to solve a problem of size n . Most practical algorithms have polynomial running times E.g. sorting algorithms generally have running times that are quadratic (polynomial or degree 2) or less (for example, O(n log n )). Exhaustive search over an exponentially growing set of possible answers requires exponential time. 3/26/12
18 .Another way to look at it Suppose an algorithm can solve a problem of size S in time T and you give it twice as much time. If the running time is f(n )=n 2 , so that T=S 2 , then in time 2T you can solve a problem of size (2 1/2 )∙S If the running time is f(n )=2 n , so that T=2 S , then in time 2T you can solve a problem of size S+1 . In general doubling the time available to a polynomial algorithm results in a MULTIPLICATIVE increase in the size of the problem that can be solved But doubling the time available to an exponential algorithm results in an ADDITIVE increase to the size of the problem that can be solved. 3/26/12
热门城市
