Algorithm Analysis CSE235 Algorithm Analysis Analysis of Algorithms Mathematical Analysis of Algorithms Examples Slides by Christopher M Bourke Instructor Berthe Y Choueiry Useful Tools Fall 2007 Computer Science Engineering 235 1 18 Section 3 3 of Rosen cse235 cse unl edu Introduction Algorithm Analysis CSE235 Analysis of Algorithms How can we say that one algorithm performs better than another Quantify the resources required to execute Mathematical Analysis of Algorithms Time Examples Memory Useful Tools I O circuits power etc Time is not merely CPU clock cycles we want to study algorithms independent or 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 an algorithm s input size 2 18 Input Size Algorithm Analysis CSE235 Analysis of Algorithms Mathematical Analysis of Algorithms Examples 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 Numerical The number of bits needed to represent a number Useful Tools The choice of an input size greatly depends on the elementary operation the most relevant or important operation of an algorithm Comparisons Additions Multiplications 3 18 Orders of Growth Algorithm Analysis CSE235 Analysis of Algorithms Mathematical Analysis of Algorithms Examples Useful Tools 4 18 Small input sizes can usually be computed instantaneously thus we are most interested in how an algorithm 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 Intractability Algorithm Analysis CSE235 Analysis of Algorithms Mathematical Analysis of Algorithms Problems that we can solve today only with exponential or super exponential 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 of efficient execution It may take millions or billions of years Examples Useful Tools Tractable problems are problems that have efficient read polynomial algorithms to solve them Polynomial order of magnitude usually means there exists a polynomial p n nk for some constant k that always bounds the order of growth More on asymptotics in the next slide set Intractable problems may need to be solved using approximation or randomized algorithms 5 18 Worst Best and Average Case Algorithm Analysis CSE235 Analysis of Algorithms Mathematical Analysis of Algorithms Examples Some algorithms perform differently on various inputs of similar size It is sometimes helpful to consider the Worst Case Best Case and Average Case efficiencies of algorithms For example say we want to search an array A of size n for a given value K Useful Tools Worst Case K 6 A then we must search every item n comparisons Best Case K is the first item that we check so only one comparison 6 18 Average Case Algorithm Analysis CSE235 Analysis of Algorithms Mathematical Analysis of Algorithms Examples Since any worth while algorithm will be used quite extensively the average running time is arguably the best measure of its performance 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 Cavg n Useful Tools 7 18 p 2p ip np n 1 p n p 1 2 i n n 1 p n p n n 1 n 1 p n 2 If p 1 search succeeds Cavg n n 1 2 5n If p 0 search fails Cavg n n A more intuitive interpretation is that the algorithm must examine on average half of all elements in A Average Case Algorithm Analysis CSE235 Analysis of Algorithms Mathematical Analysis of Algorithms Examples Useful Tools 8 18 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 Mathematical Analysis of Algorithms Algorithm Analysis CSE235 Analysis of Algorithms Mathematical Analysis of Algorithms Examples After developing pseudo code for an algorithm we wish to analyze its efficiency 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 Decide on a parameter s for the input n 2 Identify the basic operation 3 Evaluate if the elementary operation depends only on n otherwise evaluate best worst and average case separately 4 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 Useful Tools 9 18 Analysis Examples Example I Algorithm Analysis CSE235 Analysis of Algorithms Consider the following code Algorithm UniqueElements Mathematical Analysis of Algorithms Examples Useful Tools 1 2 3 4 5 6 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 7 end 8 return true 10 18 Analysis Example Example I Analysis Algorithm Analysis CSE235 For this algorithm what is Analysis of Algorithms Mathematical Analysis of Algorithms Examples Useful Tools 11 18 The elementary operation Input Size Does the elementary operation depend only on n Analysis Example Example I Analysis Algorithm Analysis CSE235 For this algorithm what is Analysis of Algorithms Mathematical Analysis of Algorithms Examples The elementary operation Input Size Does the elementary operation depend only on n Useful Tools The outer for loop is run n 1 times More formally it contributes n 1 X i 1 11 18 Analysis Example Example I Analysis Algorithm Analysis CSE235 Analysis of Algorithms Mathematical Analysis of Algorithms Examples Useful Tools 12 18 The inner for loop depends on the outer for loop so it contributes n X j i 1 Analysis Example Example I Analysis Algorithm Analysis CSE235 Analysis of Algorithms The inner for loop depends on the outer for loop so it contributes n X Mathematical Analysis of Algorithms j i 1 Examples Useful Tools We observe that the elementary operation is executed once in each iteration thus we have Cworst n n 1 X n X i 1 j i 1 12 18 1 n n 1 2 Analysis Example Example II Algorithm Analysis CSE235 Analysis of Algorithms Mathematical Analysis of Algorithms The parity of a bit string determines whether or not the
View Full Document
Unlocking...