Algorithms Analysis Section 3 3 of Rosen Spring 2010 CSCE 235 Introduction to Discrete Structures Course web page cse unl edu cse235 Questions cse235 cse unl edu Outline Introduction Input Size Order of Growth Intractability Worst Best and Average Cases Mathematical Analysis of Algorithms 3 Examples Summation tools CSCE 235 Spring 2010 Algorithm Analysis 2 Introduction How can we say that one algorithm performs better than another one Quantify the resources needed to run it Time Memory I O disk access Circuit power etc Time is not merely CPU clock cycle We want to study algorithms independent of implementations platforms and hardware We need an objective point of reference For that we measure time by the number of operations as a function of the size of the input to the algorithm CSCE 235 Spring 2010 Algorithm Analysis 3 Input Size For a given problem we characterize the input size n appropriately Sorting The number of items to be sorted Graphs The number of vertices and or edges Matrix manipulation The number of rows and colums Numerical operations the number of bits needed to represent a number The choice of an input size greatly depends on the elementary operation the most relevant or important operation of an algorithm Comparisons Additions Multiplications CSCE 235 Spring 2010 Algorithm Analysis 4 Outline Introduction Input Size Order of Growth Intractability Worst Best and Average Cases Mathematical Analysis of Algorithms 3 Examples Summation tools CSCE 235 Spring 2010 Algorithm Analysis 5 Order of Growth Small input sizes can usually be computed instantaneously thus we are most interested in how an algorithms performs as n Indeed for small values of n most such functions will be very similar in running time Only for sufficiently large n do differences in running time become apparent As n the differences become more and more stark CSCE 235 Spring 2010 Algorithm Analysis 6 Intractability Problems that we can solve today only with exponential or superexponential time algorithms are said to be likely intractable That is though they may be solved in a reasonable amount of time for small n for large n there is likely no hope for efficient execution It may take millions or billions of years Tractable problems are problems that have efficient read polynomial algorithms to solve them Polynomial order of magnitude usually means that there exists a polynomial p n nk for some constant k that always bounds the order of growth More on asymptotics in the next lecture Intractable problems may need to be solved using approximation or randomized algorithms except for small size of input CSCE 235 Spring 2010 Algorithm Analysis 7 Worst Best and Average Case Some algorithms perform differently on various input of similar size It is sometimes helpful to consider The worst case The best case The average case Performance of the algorithm For example say we want to search an array A of size n for a given value k Worst case k A then we must check every item Cost n comparisons Best case k is the first item in the array Cost 1 comparison Average case Probabilistic analysis CSCE 235 Spring 2010 Algorithm Analysis 8 Average Case Example Since any worthwhile algorithm will be used quite extensively the average running time is arguably the best measure of the performance of the algorithm if the worst case is not frequently encountered For searching an array and assuming that p is the probability of a successful search we have Caverage n p 2p ip np n n 1 p 1 2 i n p n n 1 p n n 1 2 p n n 1 p p n 1 2 n 1 p If p 0 search fails Caverage n n If p 1 search succeeds Caverage n n 1 2 n 2 Intuitively the algorithm must examine on average half of all the elements in A CSCE 235 Spring 2010 Algorithm Analysis 9 Average Case Importance Average case analysis of algorithms is important in a practical sense Often Cavg and Cworst have the same order of magnitude and thus from a theoretical point of view are no different from each other Practical implementations however require a real world examination and empirical analysis CSCE 235 Spring 2010 Algorithm Analysis 10 Outline Introduction Input Size Order of Growth Intractability Worst Best and Average Cases Mathematical Analysis of Algorithms 3 Examples Summation tools CSCE 235 Spring 2010 Algorithm Analysis 11 Mathematical Analysis of Algorithms After developing a pseudo code for an algorithm we wish to analyze its performance as a function of the size of the input n in terms of how many times the elementary operation is performed Here is a general strategy 1 2 3 4 Decide on a parameter s for the input n Identify the basic operation Evaluate if the elementary operation depends only on n Set up a summation corresponding to the number of elementary operations 5 Simplify the equation to get as simple of a function f n as possible CSCE 235 Spring 2010 Algorithm Analysis 12 Algorithm Analysis Example 1 1 UniqueElements Input Integer array A of size n Output True if all elements a A are distinct For i 1 n 1 Do For j i 1 n Do If ai aj Then Return false End End End Return true CSCE 235 Spring 2010 Algorithm Analysis 13 Algorithm Analysis Example 1 2 For this algorithm what is The elementary operation Comparing ai and aj Input size n size of A Does the elementary operation depend only on n The outer for loop runs n 1 times More formally it contributes i 1 n 1 The inner for loop depends on the outer for loop and n contributes j i 1 Algorithm Analysis CSCE 235 Spring 2010 14 Algorithm Analysis Example 1 3 We observe that the elementary operation is executes once in each iteration thus we have Cworst n i 1n 1 j i 1n 1 n n 1 2 CSCE 235 Spring 2010 Algorithm Analysis 15 Computing i 1 n 1 j i 1 n 1 j i 1n 1 1 1 1 1 n i 1 1 n i i 1n 1 n i i 1n 1 n i 1n 1 i n n 1 i 1n 1 i Computing i 1n 1 i Check Table 2 page 157 k 1n k n n 1 2 Rewrite i 1n 1 i i 1n i n n n 1 2 n n n 1 2 2 n n 1 2 i 1n 1 j i 1n 1 n n 1 n n 1 2 n n 1 2 CSCE 235 Spring 2010 Algorithm Analysis 16 Algorithm Analysis Example 2 1 The parity of a bit string determines whether or not the number of 1s in it is even or odd It is used as a simple form of error correction over communication networks CSCE 235 Spring 2010 Algorithm Analysis 17 Algorithm Analysis ParityChecking ParityChecking Input An integer n in binary as an array b Output 0 if parity is even 1 otherwise parity 0 While n 0 Do If b 0 1 Then parity parity 1 mod 2 End RightShift n End Return …
View Full Document
Unlocking...