Question? Leave a message!




Asymptotic Analysis

Asymptotic Analysis
ECE 250 Algorithms and Data Structures Asymptotic Analysis Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Asymptotic Analysis 2 2.3.1 Asymptotic Analysis In general, we will always analyze algorithms with respect to one or more variables We will begin with one variable: – The number of items n currently stored in an array or other data structure – The number of items expected to be stored in an array or other data structure – The dimensions of an n × n matrix Examples with multiple variables: – Dealing with n objects stored in m memory locations – Multiplying a k × m and an m × n matrix – Dealing with sparse matrices of size n × n with m nonzero entriesAsymptotic Analysis 3 2.3.1 Maximum Value For example, the time taken to find the largest object in an array of n random integers will take n operations int findmax( int array, int n ) int max = array0; for ( int i = 1; i n; ++i ) if ( arrayi max ) max = arrayi; return max; Asymptotic Analysis 4 2.3.1 Maximum Value One comment: – In this class, we will look at both simple C++ arrays and the standard template library (STL) structures – Instead of using the builtin array, we could use the STL vector class – The vector class is closer to the C/Java arrayAsymptotic Analysis 5 2.3.1 Maximum Value include vector int findmax( std::vectorint array ) if ( array.size() == 0 ) throw underflow(); int max = array0; for ( int i = 1; i array.size(); ++i ) if ( arrayi max ) max = arrayi; return max; Asymptotic Analysis 6 2.3.2 Linear and binary search There are other algorithms which are significantly faster as the problem size increases This plot shows maximum and average number of comparisons to find an entry in a sorted array of size n – Linear search – Binary search nAsymptotic Analysis 7 2.3.3 Asymptotic Analysis Given an algorithm: – We need to be able to describe these values mathematically – We need a systematic means of using the description of the algorithm together with the properties of an associated data structure – We need to do this in a machineindependent way For this, we need Landau symbols and the associated asymptotic analysisAsymptotic Analysis 8 2.3.3 Quadratic Growth Consider the two functions 2 2 f(n) = n and g(n) = n – 3n + 2 Around n = 0, they look very differentAsymptotic Analysis 9 2.3.3 Quadratic Growth Yet on the range n = 0, 1000, they are (relatively) indistinguishable:Asymptotic Analysis 10 2.3.3 Quadratic Growth The absolute difference is large, for example, f(1000) = 1 000 000 g(1000) = 997 002 but the relative difference is very small f(1000) g(1000)  0.002998 0.3 f(1000) and this difference goes to zero as n → ∞Asymptotic Analysis 11 2.3.3 Polynomial Growth To demonstrate with another example, 6 6 5 4 3 2 f(n) = n and g(n) = n – 23n +193n –729n +1206n – 648n Around n = 0, they are very differentAsymptotic Analysis 12 2.3.3 Polynomial Growth Still, around n = 1000, the relative difference is less than 3Asymptotic Analysis 13 2.3.3 Polynomial Growth The justification for both pairs of polynomials being similar is that, in both cases, they each had the same leading term: 2 6 n in the first case, n in the second Suppose however, that the coefficients of the leading terms were different – In this case, both functions would exhibit the same rate of growth, however, one would always be proportionally largerAsymptotic Analysis 14 2.3.4 Examples We will now look at two examples: – A comparison of selection sort and bubble sort – A comparison of insertion sort and quicksortAsymptotic Analysis 15 2.3.4.1 Counting Instructions Suppose we had two algorithms which sorted a list of size n and the run time (in ms) is given by 2 b (n) = 4.7n – 0.5n + 5 Bubble sort worst 2 b (n) = 3.8n + 0.5n + 5 best 2 s(n) = 4n + 14n + 12 Selection sort The smaller the value, the fewer instructions are run – For n ≤ 21, b (n) s(n) worst – For n ≥ 22, b (n) s(n) worstAsymptotic Analysis 16 2.3.4.1 Counting Instructions With small values of n, the algorithm described by s(n) requires more instructions than even the worstcase for bubble sortAsymptotic Analysis 17 2.3.4.1 Counting Instructions Near n = 1000, b (n) ≈ 1.175 s(n) and b (n) ≈ 0.95 s(n) worst bestAsymptotic Analysis 18 2.3.4.1 Counting Instructions Is this a serious difference between these two algorithms Because we can count the number instructions, we can also estimate how much time is required to run one of these algorithms on a computerAsymptotic Analysis 19 2.3.4.1 Counting Instructions Suppose we have a 1 GHz computer – The time (s) required to sort a list of up to n = 10 000 objects is under half a secondAsymptotic Analysis 20 2.3.4.1 Counting Instructions To sort a list with one million elements, it will take about 1 h Bubble sort could, under some conditions, be 200 s fasterAsymptotic Analysis 21 2.3.4.1 Counting Instructions How about running selection sort on a faster computer – For large values of n, selection sort on a faster computer will always be faster than bubble sortAsymptotic Analysis 22 2.3.4.1 Counting Instructions Justification k k – If f(n) = a n + ··· and g(n) = b n + ···, k k for large enough n, it will always be true that f(n) Mg(n) where we choose M = a /b + 1 k k In this case, we only need a computer which is M times faster (or slower) Question: – Is a linear search comparable to a binary search – Can we just run a linear search on a slower computerAsymptotic Analysis 23 2.3.4.2 Counting Instructions As another example: – Compare the number of instructions required for insertion sort and for quicksort – Both functions are concave up, although one more than the otherAsymptotic Analysis 24 2.3.4.2 Counting Instructions 2 Insertion sort, however, is growing at a rate of n while quicksort grows at a rate of n lg(n) – Nevertheless, the graphic suggests it is more useful to use insertion sort when sorting small lists—quicksort has a large overheadAsymptotic Analysis 25 2.3.4.2 Counting Instructions If the size of the list is too large (greater than 20), the additional overhead of quicksort quickly becomes insignificant – The quicksort algorithm becomes significantly more efficient – Question: can we just buy a faster computerAsymptotic Analysis 26 2.3.5 Weak ordering Consider the following definitions: – We will consider two functions to be equivalent, f g, if fn () 0 c lim c where n  gn () fn () – We will state that f g if lim 0 n  gn () For functions we are interested in, these define a weak orderingAsymptotic Analysis 27 2.3.5 Weak ordering Let f(n) and g(n) describe either the runtime of two algorithms – If f(n) g(n), then it is always possible to improve the performance of one function over the other by purchasing a faster computer – If f(n) g(n), then you can never purchase a computer fast enough so that the second function always runs in less time than the first Note that for small values of n, it may be reasonable to use an algorithm that is asymptotically more expensive, but we will consider these on a onebyone basisAsymptotic Analysis 28 2.3.5 Weak ordering In general, there are functions such that – If f(n) g(n), then it is always possible to improve the performance of one function over the other by purchasing a faster computer – If f(n) g(n), then you can never purchase a computer fast enough so that the second function always runs in less time than the first Note that for small values of n, it may be reasonable to use an algorithm that is asymptotically more expensive, but we will consider these on a onebyone basisAsymptotic Analysis 29 2.3.5 Landau Symbols st Recall Landau symbols from 1 year: A function f(n) = O(g(n)) if there exists N and c such that f(n) c g(n) whenever n N – The function f(n) has a rate of growth no greater than that of g(n)Asymptotic Analysis 30 2.3.5 Landau Symbols Before we begin, however, we will make some assumptions: – Our functions will describe the time or memory required to solve a problem of size n – We conclude we are restricting ourselves to certain functions: • They are defined for n ≥ 0 • They are strictly positive for all n – In fact, f(n) c for some value c 0 – That is, any problem requires at least one instruction and byte • They are increasing (monotonic increasing)Asymptotic Analysis 31 2.3.5 Landau Symbols Another Landau symbol is Q A function f(n) = Q(g(n)) if there exist positive N, c , and c such that 1 2 c g(n) f(n) c g(n) 1 2 whenever n N – The function f(n) has a rate of growth equal to that of g(n)Asymptotic Analysis 32 2.3.5 Landau Symbols These definitions are often unnecessarily tedious Note, however, that if f(n) and g(n) are polynomials of the same degree with positive leading coefficients: f(n) where lim c 0 c n g(n)Asymptotic Analysis 33 2.3.5 Landau Symbols f(n) Suppose that f(n) and g(n) satisfy lim c n g(n) From the definition, this means given c e 0 there f(n)  ce exists an N 0 such that whenever n N g(n) That is, f(n) ce ce g(n) g(n)ce f(n) g(n)ceAsymptotic Analysis 34 2.3.5 Landau Symbols However, the statement g(n) c  e   f(n)  g(n) c  e  says that f(n) = Q(g(n)) Note that this only goes one way: f(n) If lim  c where 0  c  ,  it follows that f(n) = Q(g(n)) n   g(n)Asymptotic Analysis 35 2.3.6 Landau Symbols We have a similar definition for O: f(n) 0 c If lim  c where , it follows that f(n) = O(g(n)) n g(n) There are other possibilities we would like to describe: f(n) lim 0 If , we will say f(n) = o(g(n)) n g(n) – The function f(n) has a rate of growth less than that of g(n) We would also like to describe the opposite cases: – The function f(n) has a rate of growth greater than that of g(n) – The function f(n) has a rate of growth greater than or equal to that of g(n)Asymptotic Analysis 36 2.3.7 Landau Symbols We will at times use five possible descriptions f(n) lim 0 f(n)o(g(n)) n g(n) f(n) f(n)O(g(n)) lim n g(n) f(n) f(n)Θ(g(n)) 0 lim n g(n) f(n) f(n)Ω(g(n)) lim 0 n g(n) f(n) lim f(n)ω(g(n)) n g(n)Asymptotic Analysis 37 2.3.7 Landau Symbols For the functions we are interested in, it can be said that f(n) = O(g(n)) is equivalent to f(n) = Q(g(n)) or f(n) = o(g(n)) and f(n) = W(g(n)) is equivalent to f(n) = Q(g(n)) or f(n) = w(g(n))Asymptotic Analysis 38 2.3.7 Landau Symbols Graphically, we can summarize these as follows: We say ifAsymptotic Analysis 39 2.3.8 Landau Symbols Some other observations we can make are: f(n) = Q(g(n))⇔ g(n) = Q(f(n)) f(n) = O(g(n))⇔ g(n) = W(f(n)) f(n) = o(g(n))⇔ g(n) = w(f(n))Asymptotic Analysis 40 2.3.8 BigQ as an Equivalence Relation If we look at the first relationship, we notice that f(n) = Q(g(n)) seems to describe an equivalence relation: 1. f(n) = Q(g(n)) if and only if g(n) = Q(f(n)) 2. f(n) = Q(f(n)) 3. If f(n) = Q(g(n)) and g(n) = Q(h(n)), it follows that f(n) = Q(h(n)) Consequently, we can group all functions into equivalence classes, where all functions within one class are bigtheta Q of each otherAsymptotic Analysis 41 2.3.8 BigQ as an Equivalence Relation For example, all of 2 2 2 n 100000 n – 4 n + 19 n + 1000000 2 2 323 n – 4 n ln(n) + 43 n + 10 42n + 32 2 2 3 n + 61 n ln (n) + 7n + 14 ln (n) + ln(n) are bigQ of each other 2 2 E.g., 42n + 32 = Q( 323 n – 4 n ln(n) + 43 n + 10 )Asymptotic Analysis 42 2.3.8 BigQ as an Equivalence Relation Recall that with the equivalence class of all 19year olds, we only had to pick one such student Similarly, we will select just one element to represent the entire class 2 of these functions: n – We could chose any function, but this is the simplestAsymptotic Analysis 43 2.3.8 BigQ as an Equivalence Relation The most common classes are given names: Q(1) constant Q(ln(n)) logarithmic Q(n) linear Q(n ln(n)) ―n log n” 2 Q(n ) quadratic 3 Q(n ) cubic n n n 2 , e , 4 , ... exponentialAsymptotic Analysis 44 2.3.8 Logarithms and Exponentials Recall that all logarithms are scalar multiples of each other – Therefore log (n)= Q(ln(n)) for any base b b Alternatively, there is no single equivalence class for exponential functions: n n a a  lim lim 0 – If 1 a b,  n n n b b  n n – Therefore a = o(b ) However, we will see that it is almost universally undesirable to have an exponentially growing functionAsymptotic Analysis 45 2.3.8 Logarithms and Exponentials n n n Plotting 2 , e , and 4 on the range 1, 10 already shows how significantly different the functions grow Note: 10 2 = 1024 10 e ≈ 22 026 10 4 = 1 048 576Asymptotic Analysis 46 2.3.9 Littleo as a Weak Ordering We can show that, for example p ln( n ) = o( n ) for any p 0 Proof: Using l’Hôpital’s rule, we have ln(n) 1/ n 1 1  p lim lim lim lim n 0 p p1 p n n n n n pn pn p Conversely, 1 = o(ln( n ))Asymptotic Analysis 47 2.3.9 Littleo as a Weak Ordering Other observations: – If p and q are real positive numbers where p q, it follows that p q n = o(n ) 3 – For example, matrixmatrix multiplication is Q(n ) but a refined algorithm lg(7) is Q(n ) where lg(7) ≈ 2.81 p p p q – Also, n = o(ln(n)n ), but ln(n)n = o(n ) p p • n has a slower rate of growth than ln(n)n , but p q • ln(n)n has a slower rate of growth than n for p qAsymptotic Analysis 48 2.3.9 Littleo as a Weak Ordering p If we restrict ourselves to functions f(n) which are Q(n ) and p Q(ln(n)n ), we note: – It is never true that f(n) = o(f(n)) – If f(n) ≠ Q(g(n)), it follows that either f(n) = o(g(n)) or g(n) = o(f(n)) – If f(n) = o(g(n)) and g(n) = o(h(n)), it follows that f(n) = o(h(n)) This defines a weak orderingAsymptotic Analysis 49 2.3.9 Littleo as a Weak Ordering Graphically, we can shown this relationship by marking these against the real lineAsymptotic Analysis 50 2.3.10 Algorithms Analysis We will use Landau symbols to describe the complexity of algorithms – E.g., adding a list of n doubles will be said to be a Q(n) algorithm An algorithm is said to have polynomial time complexity if its run d time may be described by O(n ) for some fixed d ≥ 0 – We will consider such algorithms to be efficient Problems that have no known polynomialtime algorithms are said to be intractable – Traveling salesman problem: find the shortest path that visits n cities 2 n – Best run time: Q(n 2 )Asymptotic Analysis 51 2.3.10 Algorithm Analysis In general, you don’t want to implement exponentialtime or exponentialmemory algorithms – Warning: don’t call a quadratic curve ―exponential‖, either...please
Website URL
Comment