CompSci 100E9.1Analyzing Algorithmsÿ Remember SortByFreqs APT Problem: Start with array of words (Strings) Find frequency of each word Return array of words ordered from most frequent to least (In case of a tie, return in alphabetical order)public class SortByFreqs {public String[] sort(String[] data) {// fill in code here}}ÿ There are several approaches to a solution Are they all equivalent?CompSci 100E9.2Analyzing Algorithmsÿ Consider three solutions to SortByFreqs, also code used in Anagram discussion Sort, then scan looking for changes Insert into Set, then count each unique string Find unique elements without sorting, sort these, then count each unique stringÿ We want to discuss trade-offs of these solutions Ease to develop, debug, verify Runtime efficiency Vocabulary for discussionCompSci 100E9.3What is big-Oh about? (preview)ÿ Intuition: avoid details when they don’t matter, and they don’t matter when input size (N) is big enough For polynomials, use only leading term, ignore coefficientst = 3n t = 6n-2 t = 15n + 44t=n2t=n2-6n+9 t = 3n2+4nÿ The first family is O(n), the second is O(n2) Intuition: family of curves, generally the same shape More formally: O(f(n)) is an upper-bound, when n is large enough the expression c*f(n) is larger Intuition: linear function: double input, double time, quadraticfunction: double input, quadruple the timeCompSci 100E9.4More on O-notation, big-Ohÿ Big-Oh hides/obscures some empirical analysis, but is good for general description of algorithm Allows us to compare algorithms in the limito 20N hours vs N2microseconds: which is better?ÿ O-notation is an upper-bound, this means that Nis O(N), but it is also O(N2); we try to provide tight bounds. Formally: A function g(N) is O(f(N)) if there exist constants cand nsuch that g(N) < cf(N) for all N>ncf(N)g(N)x=nCompSci 100E9.5Big-Oh calculations from codeÿ Search for element in an array: What is complexity of code (using O-notation)? What if array doubles, what happens to time?for(int k=0; k < a.length; k++) {if (a[k].equals(target)) return true;}return false;ÿ Complexity if we call N times on M-element vectors? What about best case? Average case? Worst case?CompSci 100E9.6Big-Oh calculations againÿ Alcohol APT: first string to occur 3 times What is complexity of code (using O-notation)?for(int k=0; k < a.length; k++) {int count = 0;for(int j=0; j <= k; k++) {if (a[j].equals(a[k])) count++;}if (count >= 3) return a[k];}return ""; // nothing occurs three times What happens to time if array doubles in size? 1+2+3+…+n-1, why and what’s O-notation?CompSci 100E9.7Amortization: Expanding ArrayListsÿ Expand capacity of list when add() calledÿ Calling add N times, doubling capacity as neededÿ What if we grow size by one each time?2m+1around 22m+2-22m+12m+1 - 2m+181.751485-841.5643-42122210001Capacity After addResizing Cost per itemCumulative costResizing costItem #CompSci 100E9.8Some helpful mathematicsÿ 1 + 2 + 3 + 4 + … + N N(N+1)/2, exactly = N2/2 + N/2 which is O(N2) why?ÿ N + N + N + …. + N (total of N times) N*N = N2which is O(N2)ÿ N + N + N + …. + N + … + N + … + N (total of 3N times) 3N*N = 3N2which is O(N2)ÿ 1 + 2 + 4 + … + 2N 2N+1–1= 2x2N–1which is O(2N)ÿ Impact of last statement on adding 2N+1 elements to a vector 1 + 2 + … + 2N+ 2N+1= 2N+2-1 = 4x2N-1 which is O(2N)CompSci 100E9.9Running times @ 106instructions/sec318centuries18.3 hr16.7 min0.0000301,000,000,00011.6 day19.91.00.0000201,000,0002.78 hr1.6610000.100000.000017100,0001.7 min0.1329000.010000.00001310,0001.00.0100000.001000.0000101,0000.10000.0006640.000100.0000071000.00010.0000330.000010.00000310O(N2)O(N log N)O(N)O(log
View Full Document
Unlocking...