Topic Number 8op c u be8Algorithm Analysis"bit twiddling: 1. (pejorative) An exercise in tuning (see tune) in which incredible amounts of time and effort go to produce little noticeable improvement, ft ith th lt th t th d boften with the result that the code becomes incomprehensible."The Hackers Dictionary version447-The Hackers Dictionary, version 4.4.7CS 307 Fundamentals of Computer Science Algorithm Analysis1Is This Algorithm Fast?88Problem: given a problem, how fast does this code solve that problem?8Could try to measure the time it takes, but that is subject to lots of errors– multitasking operating system–speed of computerpp– language solution is written inCS 307 Fundamentals of Computer Science Algorithm Analysis2Attendance Question 188"My program finds all the primes between 2 and 1,000,000,000 in 1.37 seconds."– how good is this solution?A. GoodB. BadCIt dependsC.It dependsCS 307 Fundamentals of Computer Science Algorithm Analysis3Grading Algorithms88What we need is some way to grade algorithms and their representation via computer programs for efficiency– both time and space efficiency are concerns– are examples simply deal with time, not space8The grades used to characterize the galgorithm and code should be independent of platform, language, and compilerp,gg, p– We will look at Java examples as opposed to pseudocode algorithmsCS 307 Fundamentals of Computer Science Algorithm Analysis4Big O88The most common method and notation for discussing the execution time of algorithms is "Big O"8Big O is the asymptotic execution time of the algorithm8Big O is an upper boundsg O s a uppe bou ds8It is a mathematical tool8Hide a lot of unimportant details by assigning8Hide a lot of unimportant details by assigning a simple grade (function) to algorithmsCS 307 Fundamentals of Computer Science Algorithm Analysis5Typical Big O Functions – "Grades"FunctionCommon NameFunctionCommon NameN! factorial2NExponential2ExponentialNd, d > 3 PolynomialN3CubicN2QuadraticN N N Square root NN log N N log NN LinearN Root - nlog N LogarithmicCS 307 Fundamentals of Computer Science Algorithm Analysis61 ConstantBig O Functions88N is the size of the data set.8The functions do not include less dominant terms and do not include any coefficients.84N2+ 10N –100 is not a valid F(N).000 s ot a a d ( )– It would simply be O(N2)8It is possible to have two independent8It is possible to have two independent variables in the Big O function.example O(M + log N)–example O(M + log N)– M and N are sizes of two different, but interacting data setsCS 307 Fundamentals of Computer Science Algorithm Analysis7data setsActual vs. Big OSimplifiedTimeforpalgorithmto ltActualcompleteAmount of dataCS 307 Fundamentals of Computer Science Algorithm Analysis8Formal Definition of Big O88T(N) is O( F(N) ) if there are positive constants c and N0such that T(N) < cF(N) when N > N0 – N is the size of the data set the algorithm works on– T(N) is a function that characterizes the actualrunning time of the algorithm–F(N) is a function that characterizes an upper bounds on T(N). It is a limit on the running time of the algorithm (The t pical Big f nctions table)the algorithm. (The typical Big functions table)– c and N0are constants CS 307 Fundamentals of Computer Science Algorithm Analysis9What it Means88T(N) is the actual growth rate of the algorithm– can be equated to the number of executable statements in a program or chunk of code8F(N) is the function that bounds the growth rate– may be upper or lower bound8T(N) may not necessarily equal F(N)() y yq ()– constants and lesser terms ignored because it is a bounding functionCS 307 Fundamentals of Computer Science Algorithm Analysis10gYuck8H d l h dfiii ?8How do you apply the definition?8Hard to measure time without running programs dth ti f ll fi iand that is full of inaccuracies8Amount of time to complete should be directly proportional to the number of statements executedproportional to the number of statements executed for a given amount of data8Count up statements in a program or method or8Count up statements in a program or method or algorithm as a function of the amount of data–This is one techniqueThis is one technique 8Traditionally the amount of data is signified by the variable NCS 307 Fundamentals of Computer Science Algorithm Analysis11Counting Statements in Code88So what constitutes a statement?8Can’t I rewrite code and get a different answer, that is a different number of statements?8Yes, but the beauty of Big O is, in the end you get the same answeryou ge e sa e a s e– remember, it is a simplificationCS 307 Fundamentals of Computer Science Algorithm Analysis12Assumptions in For Counting Statements8Once found accessing the value of a primitive isOnce found accessing the value of a primitive is constant time. This is one statement:x = y; //one statement8mathematical operations and comparisons in boolean expressions are all constant time.x = y * 5 + z % 3; // one statement8if statement constant time if test and maximum time for each alternative are constantsif( iMySuit == DIAMONDS || iMySuit == HEARTS )return RED;return RED;elsereturn BLACK;// 2 t t t (b l i 1 t )CS 307 Fundamentals of Computer Science Algorithm Analysis13// 2 statements (boolean expression + 1 return)Counting Statements in LoopsAttendenance Question 2Attendenance Question 28Counting statements in loops often requires a bit of informal mathematical induction8What is output by the following code?int total = 0;for(int i = 0; i < 2; i++)total += 5;System.out.println( total );A. 2 B. 5 C. 10 D. 15 E. 20CS 307 Fundamentals of Computer Science Algorithm Analysis14Attendances Question 38What is output by the following code?What is output by the following code?int total = 0;// assume limit is an int>= 0for(int i = 0; i < limit; i++)total += 5;System.out.println( total );A. 0B. limitClimit*5C.limit 5D. limit * limitEli it5E.limit5CS 307 Fundamentals of Computer Science Algorithm Analysis15Counting Statements in Nested Loopsin Nested LoopsAttendance Question 48What is output by the following code?What is output by the following code?int total = 0;for(int i = 0; i < 2; i++)for(intj 0;j<2;j++)for(intj = 0; j < 2; j++)total += 5;System.out.println( total );A.0B. 10C20C.20D. 30E. 40CS 307 Fundamentals of Computer Science Algorithm Analysis16Attendance Question 58What is output by the following code?What is output by the following code?int total = 0;// assume limit is an int
View Full Document
Unlocking...