CompSci 100E31.1BigOhAgainAgainÿ Have taken the attitude that mostly you can look things upÿ Now need to be able to do your own derivations ÿ Extend our menu of solutions to common recurrencesÿ Let’s look at previously shown tableCompSci 100E31.2Recognizing Common Recurrencesÿ Below are some algorithms and recurrence relation encounteredÿ Solve once, re-use in new contexts T must be explicitly identified n must be some measure of size of input/parametero T(n) is the time for quicksort to run on an n-element vectorT(n) = T(n/2) + O(1) binary search O( )T(n) = T(n-1) + O(1) sequential search O( )T(n) = 2T(n/2) + O(1) tree traversal O( )T(n) = 2T(n/2) + O(n) quicksort O( )T(n) = T(n-1) + O(n) selection sort O( )ÿ Remember the algorithm, re-derive complexitynlog nn log nnn2CompSci 100E31.3Big Oh for Quickselectÿ Quickselect finds the Nth Smallest item in a list For example { 13, 14, 11, 17, 15, 19, 12, 16, 18, 17} 4thsmallest is 14. Program partially sorts so that it ends up in the 4thindex position (3).ÿ Code on next slide Has much in common with Quicksort What are the differences?ÿ Recurrence Relation T(0) = 1 T(N) = T(N/2) + Nÿ What is Big Oh?CompSci 100E31.4Quickselectÿ Partially reorders list so that kindex smallest is in proper positionvoid quickselect(String[] list, int first,int last, int kIndex){int k, lastIndex = first;String pivot = list[first];for(k=first+1;k<=last;k++){if (list[k].compareTo(pivot) <= 0){lastIndex++;swap(list, lastIndex, k);}}swap(list,lastIndex,first);if (lastIndex == kIndex) return;if (kindex < lastIndex)quickslect(list,first,lastIndex-1,kindex);elsequickselect(list,lastIndex+1,last,kindex);}CompSci 100E31.5Solving Quickselect Big Ohÿ Plug, simplify, reduce, guess, verify?T(n) = T(n/2) + nT(1) = 1T(n) = T(n/2k)+(2-1/2k)n find the pattern!Now, let k=log n, then T(n) = T(0)+~2n = 1+2nÿ Get to base case, solve the recurrence: O(n)T(n/2)=T(n/2/2) + n/2 = T(n/4) + n/2T(n) = [T(n/4) + n/2]+n= T(n/4)+3n/2T(n/4)=T(n/4/2) + n/4 = T(n/8) + n/4T(n) = [T(n/8) + n/4] + 3n/2 = T(n/8)+7n/4CompSci 100E31.6Helpful formulaeÿ We always mean base 2 unless otherwise stated What is log(1024)? log(xy) log(xy) log(2n)2(log n)ÿ Sums (also, use sigma notation when possible) 1+2+4+8+…+2k= 2k+1–1= 1+2+3+…+n=n(n+1)/2 = a+ar+ar2+…+arn-1= a(rn- 1)/(r-1)=•log(x) + log(y)•y log(x)•nlog(2) = n•2(log n)=nkΣΣΣΣi=02inΣΣΣΣi=1in-1ΣΣΣΣi=0ariCompSci 100E31.7Towers of Hanoi// Initial state for n=3//// A B C// | | |// (_) 1 | |// (___) 2 | |// (_____) 3 | |Sample output responding to hanoi("A", "C", "B", 3);>Move disk 1 from A to C>Move disk 2 from A to B>Move disk 1 from C to B>Move disk 3 from A to C>Move disk 1 from B to A>Move disk 2 from B to C>Move disk 1 from A to CCompSci 100E31.8Towers of Hanoi codevoid hanoi(String from, String to, String via, int n)// Pre: n > 0 disks in pile "from" to be moved to pile "to"// with pile "via" available for intermediate storage. All// piles so that disk n always above disk n+k where k > 0.// Post: Messages generated to show how to move disks to pile "to"// with intermediate use of all piles but only one disk moved at// a time and at all times for all n, disk n above disk n+k where// k > 0. (I.e., at no time is a larger disk above a smaller disk// where smaller disks have smaller numbers than larger disks.){if (n == 1) // base case: only one disk in pileSystem.out.println("Move disk 1 from " + from + "to"+to);else {hanoi(from, via, to, n-1); // move disks above to alternateSystem.out.println("Move disk " +n+"from"+ from + "to"+ to);hanoi(via, to, from, n-1); // move disk above to target}}CompSci 100E31.9Solving Towers of Hanoi Big Ohÿ Recurrence relation:T(n) = 2T(n-1) + 1T(0) = 1T(n) = 2kT(n-k) + 2k-1 find the pattern!Now, let k=n, then T(n) = 2nT(0)+ 2n–1=2n+1-1ÿ Get to base case, solve the recurrence: O(2n)ÿ Oh – Oh !T(n-1) = 2T(n-1-1)+1=2T(n-2) + 1T(n) = 2[2T(n-2) + 1]+1= 4T(n-2) + 3T(n-2) = 2T(n-2-1)+1=2T(n-3) + 1T(n) = 4[2T(n-3) + 1]+3=8T(n-3) +
View Full Document