1、Algorithm Cost Algorithm Complexity,Lecture 23,Algorithm Cost,Back to Bunnies,Recall that we calculated Fibonacci Numbers using two different techniquesRecursionIteration,LB,Back to Bunnies,Recursive calculation of Fibonacci Numbers: Fib(1) = 1 Fib(2) = 1 Fib(N) = Fib(N-1) + Fib(N-2) So: Fib(3) = Fi
2、b(2) + Fib(1)= 1 + 1= 2,LB,Tree Recursion?,f(n),f(n-1),f(n-2),f(n-2),f(n-3),f(n-4),f(n-3),f(n-3),f(n-4),f(n-4),f(n-5),f(n-4),f(n-5),f(n-5),f(n-6),LB,Tree Recursion Example,f(6),f(5),f(4),f(4),f(3),f(2),f(3),f(3),f(2),f(2),f(1),f(2),f(1),f(2),f(1),LB,Recursively,public static int fibR(int n) if(n = 1
3、 | n =2)return 1;elsereturn fibR(n-1) + fibR(n-2); ,LB,Iteratively,public static int fibI(int n)int oldest = 1;int old = 1;int fib = 1;while(n- 2) fib = old + oldest;oldest = old;old = fib;return fib;,LB,Slight Modifications,LB,public static int fibR(int n) if(n = 1 | n =2)return 1;elsereturn fibR(n
4、-1) + fibR(n-2); ,public static int fibI(int n)int oldest = 1;int old = 1;int fib = 1;while(n- 2) fib = old + oldest;oldest = old;old = fib;return fib;,Add Counters,Demo,LB,Conclusion,Algorithm choice or design can make a big difference!,LB,Correctness is Not Enough,It isnt sufficient that our algor
5、ithms perform the required tasks.We want them to do so efficiently, making the best use of Space Time,Time and Space,Time Instructions take time. How fast does the algorithm perform? What affects its runtime?Space Data structures take space. What kind of data structures can be used? How does the cho
6、ice of data structure affect the runtime?,Time vs. Space,Very often, we can trade space for time:For example: maintain a collection of students with SSN information. Use an array of a billion elements and have immediate access (better time) Use an array of 35 elements and have to search (better spac
7、e),The Right Balance,The best solution uses a reasonable mix of space and time.Select effective data structures to represent your data model.Utilize efficient methods on these data structures.,Questions?,Algorithm Complexity,Scenarios,Ive got two algorithms that accomplish the same task Which is bet
8、ter?Given an algorithm, can I determine how long it will take to run? Input is unknown Dont want to trace all possible paths of executionFor different input, can I determine how an algorithms runtime changes?,Measuring the Growth of Work,While it is possible to measure the work done by an algorithm
9、for a given set of input, we need a way to: Measure the rate of growth of an algorithm based upon the size of the input Compare algorithms to determine which is better for the situation,Introducing Big O,Will allow us to evaluate algorithms. Has precise mathematical definition We will use simplified
10、 version in CS 1311Caution for the real world: Only tells part of the story!Used in a sense to put algorithms into families,LB,Why Use Big-O Notation,Used when we only know the asymptotic upper bound. If you are not guaranteed certain input, then it is a valid upper bound that even the worst-case in
11、put will be below. May often be determined by inspection of an algorithm. Thus we dont have to do a proof!,Size of Input,In analyzing rate of growth based upon size of input, well use a variable For each factor in the size, use a new variable N is most commonExamples: A linked list of N elements A 2
12、D array of N x M elements A Binary Search Tree of P elements,Formal Definition,For a given function g(n), O(g(n) is defined to be the set of functionsO(g(n) = f(n) : there exist positive constants c and n0 such that 0 f(n) cg(n) for all n n0,Visual O() Meaning,f(n),cg(n),n0,f(n) = O(g(n),Size of inp
13、ut,Work done,Our Algorithm,Upper Bound,Simplifying O() Answers (Throw-Away Math!),We say 3n2 + 2 = O(n2) drop constants!because we can show that there is a n0 and a c such that:0 3n2 + 2 cn2 for n n0i.e. c = 4 and n0 = 2 yields:0 3n2 + 2 4n2 for n 2,Correct but Meaningless,You could say 3n2 + 2 = O(
14、n6) or 3n2 + 2 = O(n7)But this is like answering: Whats the world record for the mile? Less than 3 days. How long does it take to drive to Chicago? Less than 11 years.,Comparing Algorithms,Now that we know the formal definition of O() notation (and what it means) If we can determine the O() of algor
15、ithms This establishes the worst they perform.Thus now we can compare them and see which has the “better” performance.,Comparing Factors,N,log N,N2,1,Size of input,Work done,Correctly Interpreting O(),O(1) or “Order One” Does not mean that it takes only one operation Does mean that the work doesnt c
16、hange as N changes Is notation for “constant work”O(N) or “Order N” Does not mean that it takes N operations Does mean that the work changes in a way that is proportional to N Is a notation for “work grows at a linear rate”,Complex/Combined Factors,Algorithms typically consist of a sequence of logic
17、al steps/sectionsWe need a way to analyze these more complex algorithmsIts easy analyze the sections and then combine them!,Example: Insert in a Sorted Linked List,Insert an element into an ordered list Find the right location Do the steps to create the node and add it to the list,17,38,142,head,/,I
18、nserting 75,Step 1: find the location = O(N),Example: Insert in a Sorted Linked List,Insert an element into an ordered list Find the right location Do the steps to create the node and add it to the list,17,38,142,head,/,Step 2: Do the node insertion = O(1),75,Combine the Analysis,Find the right loca
19、tion = O(N) Insert Node = O(1)Sequential, so add: O(N) + O(1) = O(N + 1) =,Example: Search a 2D Array,Search an unsorted 2D array (row, then column) Traverse all rows For each row, examine all the cells (changing columns),Row,Column,1 2 3 4 5,1 2 3 4 5 6 7 8 9 10,O(N),Example: Search a 2D Array,Sear
20、ch an unsorted 2D array (row, then column) Traverse all rows For each row, examine all the cells (changing columns),Row,Column,1 2 3 4 5,1 2 3 4 5 6 7 8 9 10,O(M),Combine the Analysis,Traverse rows = O(N) Examine all cells in row = O(M)Embedded, so multiply: O(N) x O(M) = O(N*M),Sequential Steps,If
21、steps appear sequentially (one after another), then add their respective O().loop . . . endloop loop . . . endloop,N,M,O(N + M),Embedded Steps,If steps appear embedded (one inside another), then multiply their respective O().looploop. . .endloop endloop,M,N,O(N*M),Correctly Determining O(),Can have
22、multiple factors: O(N*M) O(logP + N2) But keep only the dominant factors: O(N + NlogN) O(N*M + P) O(V2 + VlogV) Drop constants: O(2N + 3N2) ,O(NlogN),remains the same,O(V2), O(N2),O(N + N2),Summary,We use O() notation to discuss the rate at which the work of an algorithm grows with respect to the size of the input.O() is an upper bound, so only keep dominant terms and drop constants,Questions?,
