CompSci 100E29.1BigOhAgainAgainÿ Have taken the attitude that mostly you can lookthings 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 100E29.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, r e-derive complexitynlog nn log nnn2CompSci 100E29.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 the4thindex position (3).ÿ Code on next slideþ Has much in common with Quicksortþ What are the differences?ÿ Recurrence R elationþ T(0) = 1þ T(N) = T(N/2) + Nÿ What is Big Oh?CompSci 100E29.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 100E29.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 100E29.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 100E29.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 100E29.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 100E29.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
Unlocking...