Unformatted text preview:

Algorithm AnalysisOutlineWhy Algorithm analysisWhat is Algorithm Analysis?Big O NotationUpper and lower bounds of a functionFunctions in order of increasing growth rateSlide 8Examples of Algorithm Running TimesVarious growth ratesWorst-case vs. Average-case6.6 Static Searching problemCont.Sequential SearchBinary SearchBinary Search 3-ways comparisonsThe Max. Contiguous SubsequenceBrute Force Algorithm O(n3)O(n3) Algorithm AnalysisO(N2) algorithmO(N2) Algorithm cont.O(N) AlgorithmChecking an Algorithm AnalysisLimitations of Big-Oh AnalysisCommon errorsAlgorithm AnalysisDr. Bernard Chen Ph.D.University of Central ArkansasFall 2008OutlineBig O notationTwo examplesSearch programMax. Contiguous SubsequenceWhy Algorithm analysisGenerally, we use a computer because we need to process a large amount of data. When we run a program on large amounts of input, besides to make sure the program is correct, we must be certain that the program terminates within a reasonable amount of time.What is Algorithm Analysis?Algorithm: A clearly specified finite set of instructions a computer follows to solve a problem.Algorithm analysis: a process of determining the amount of time, resource, etc. required when executing an algorithm.Big O NotationBig O notation is used to capture the most dominant term in a function, and to represent the growth rate.Also called asymptotic upper bound. Ex: 100n3 + 30000n =>O(n3) 100n3 + 2n5+ 30000n =>O(n5)Upper and lower bounds of a functionFunctions in order of increasing growth rateFunction NameC ConstantLogN LogarithmicLog2N Log-squaredN LinearNlogN NlogNN2QuaraticN3Cubic2nExponentialFunctions in order of increasing growth rateExamples of Algorithm Running TimesMin element in an array :O(n)Closest points in the plane (an X-Y coordinate), ie. Smallest distance pairs: n(n-1)/2 => O(n2)Colinear points in the plane, ie. 3 points on a straight line: n(n-1)(n-2)/6 => O(n3)Various growth ratesT nT n nT n nT n nT n nT n n nT n nT n nT n T n n T n nn nkkn n( ) ( )( ) (log log )( ) (log )( ) ((log )( ) ( )( ) ( log )( ) ( )( ) ( )( ) ( ), ( ) ( ), ( ) ( !)    1 : Constant time : As fast as constant time : time) : time : time : famous for sorting : time : time : time;Practical for small values of (e.g., logarithmicpolylogarithmiclinearqualraticpolynomialexponential22 = or = )10 20nWorst-case vs. Average-caseA worst-case bound is a guarantee over all inputs of size N.In an average-case bound, the running time is measured as an average over all of the possible inputs of size N.We will mainly focus on worst-case analysis, but sometimes it is useful to do average one.6.6 Static Searching problemStatic Searching Problem Given an integer X and an array A, return the position of X in A or an indication that it is not present. If X occurs more than once, return any occurrence. The array A is never altered.Cont.Sequential search: =>O(n)Binary search (sorted data): => O(logn)Interpolation search (data must be uniform distributed): making guesses and search =>O(n) in worse case, but better than binary search on average Big-Oh performance, (impractical in general).Sequential SearchA sequential search steps through the data sequentially until an match is found.A sequential search is useful when the array is not sorted.A sequential search is linear O(n) (i.e. proportional to the size of input)Unsuccessful search --- n timesSuccessful search (worst) --- n timesSuccessful search (average) --- n/2 timesBinary SearchIf the array has been sorted, we can use binary search, which is performed from the middle of the array rather than the end.We keep track of low_end and high_end, which delimit the portion of the array in which an item, if present, must reside.If low_end is larger than high_end, we know the item is not present.Binary Search 3-ways comparisonstemplate < class Comparable>int binarySearch(int a[], int x){int low = 0;int high = a.size() – 1; int mid;while(low < high) {mid = (low + high) / 2;if(a[mid] < x)low = mid + 1;else if( a[mid] > x)high = mid - 1;else return mid;}return NOT_FOUND; // NOT_FOUND = -1}//binary search using three-ways comparisonsThe Max. Contiguous SubsequenceGiven (possibly negative) integers A1, A2, .., An, find (and identify the sequence corresponding to) the max. value of sum of Ak where k = i -> j. The max. contiguous sequence sum is zero if all the integer are negative.{-2, 11, -4, 13, -5, 2} =>20{1, -3, 4, -2, -1, 6} => 7Brute Force Algorithm O(n3)template <class Comparable>int maxSubSum(int a[]){ int n = a.size(); int maxSum = 0; for(int i = 0; i < n; i++){ // for each possible start point for(int j = i; j < n; j++){ // for each possible end point int thisSum = 0;for(int k = i; k <= j; k++) thisSum += a[k];//dominant termif( thisSum > maxSum){ maxSum = thisSum; seqStart = i; seqEnd = j; } } } return maxSum;} //A cubic maximum contiguous subsequence sum algorithmO(n3) Algorithm AnalysisWe do not need precise calculations for a Big-Oh estimate. In many cases, we can use the simple rule of multiplying the size of all the nested loopsO(N2) algorithmAn improved algorithm makes use of the fact that If we have already calculated the sum for the subsequence i, …, j-1. Then we need only one more addition to get the sum for the subsequence i, …, j. However, the cubic algorithm throws away this information. If we use this observation, we obtain an improved algorithm with the running time O(N2).O(N2) Algorithm cont.template <class Comparable>int maxSubsequenceSum(int a[]){int n = a.size();int maxSum = 0;for( int i = 0; i < n; i++){int thisSum = 0;for( int j = i; j < n; j++){thisSum += a[j];if( thisSum > maxSum){maxSum = thisSum;seqStart = i;seqEnd = j;}} }return maxSum;}//figure 6.5O(N) Algorithmtemplate <class Comparable>int maxSubsequenceSum(int a[]){int n = a.size();int thisSum = 0, maxSum = 0; int i=0;for( int j = 0; j < n; j++){thisSum += a[j];if( thisSum > maxSum){maxSum = thisSum;seqStart = i;seqEnd = j;}else if( thisSum < 0) {i = j + 1;thisSum = 0;} }return maxSum;}//figure 6.8Checking an Algorithm AnalysisIf it is possible, write codes to test your algorithm for various large n.Limitations of Big-Oh AnalysisBig-Oh is an estimate tool for algorithm analysis. It ignores


View Full Document

GSU CSC 2320 - Algorithm Analysis

Download Algorithm Analysis
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Algorithm Analysis and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Algorithm Analysis 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?