MarkAllenWeiss数据结构与算法分析课后习题答案2339.pdf

Chapter 2:Algorithm Analysis2.12/N,37,N,N,Nlog log N,Nlog N,Nlog(N2),Nlog2N,N1.5,N2,N2log N,N3,2N/2,2N.Nlog N and Nlog(N2)grow at the same rate.2.2(a)True.(b)False.A counterexampleis T1(N)=2N,T2(N)=N,and f(N)=N.(c)False.A counterexampleis T1(N)=N2,T2(N)=N,and f(N)=N2.(d)False.The same counterexampleas in part(c)applies.2.3We claim that Nlog N is the slower growing function.To see this,suppose otherwise.Then,N/log Nwould grow slower than log N.Taking logs of both sides,we find that,under this assumption,/log N log N grows slower than log log N.But the first expres-sion simplifies to log N.If L=log N,then we are claiming that L grows slower thanlog L,or equivalently,that2Lgrowsslowerthanlog2 L.Butwe knowthatlog2 L=(L),so the original assumption is false,proving the claim.2.4Clearly,logk1N=(logk2N)if k1 k2,so we need to worry only about positive integers.The claim is clearly true for k=0 and k=1.Suppose it is true for k i.Then,byLHospitals rule,NlimNlogiN_ _=Nlim iNlogi1N_The second limit is zero by the inductive hypothesis,proving the claim.2.5Let f(N)=1 when N is even,and N when N is odd.Likewise,let g(N)=1 when N isodd,and N when N is even.Then the ratio f(N)/g(N)oscillates between 0 and.2.6For all these programs,the following analysis will agree with a simulation:(I)The running time is O(N).(II)The running time is O(N2).(III)The running time is O(N3).(IV)The running time is O(N2).(V)j can be as large as i2,which could be as large as N2.k can be as large as j,which isN2.The running time is thus proportional to N.N2.N2,which is O(N5).(VI)The if statement is executed at most N3times,by previous arguments,but it is trueonly O(N2)times(because it is true exactly i times for each i).Thus the innermost loop isonly executed O(N2)times.Each time through,it takes O(j2)=O(N2)time,for a total ofO(N4).This is an example where multiplying loop sizes can occasionally give an overesti-mate.2.7(a)It should be clear that all algorithms generate only legal permutations.The first twoalgorithms have tests to guarantee no duplicates;the third algorithm works by shuffling anarray that initially has no duplicates,so none can occur.It is also clear that the first twoalgorithms are completely random,and that each permutation is equally likely.The thirdalgorithm,due to R.Floyd,is not as obvious;the correctness can be proved by induction.-4-SeeJ.Bentley,Programming Pearls,Communications of the ACM 30(1987),754-757.Note that if the second line of algorithm 3 is replaced with the statementSwap(Ai,A RandInt(0,N-1);then not all permutations are equally likely.To see this,notice that for N=3,there are 27equally likely ways of performing the three swaps,depending on the three random integers.Since there are only 6 permutations,and 6 does not evenly divide27,each permutation cannot possibly be equally represented.(b)For the first algorithm,the time to decide if a random number to be placed in Ai hasnot been used earlier is O(i).The expected number of random numbers that need to betried is N/(N i).This is obtained as follows:i of the N numbers would be duplicates.Thus the probability of success is(N i)/N.Thus the expected number of independenttrials is N/(N i).The time bound is thusi=0N1NiNi_ i=0N1NiN2_ N2i=0N1Ni1_ 1,the number of multiplies used islog N +b(N)12.18(a)A.(b)B.(c)The information given is not sufficient to determine an answer.We have only worst-case bounds.(d)Yes.2.19(a)Recursion is unnecessary if there are two or fewer elements.(b)One way to do this is to note that if the first N1 elements have a majority,then the lastelement cannot change this.Otherwise,the last element could be a majority.Thus if N isodd,ignore the last element.Run the algorithm as before.If no majority element emerges,then return the Nthelement as a candidate.(c)The running time is O(N),and satisfies T(N)=T(N/2)+O(N).(d)One copy of the original needs to be saved.After this,the B array,and indeed the recur-sion can be avoided by placing each Biin the A array.The difference is that the originalrecursive strategy implies that O(log N)arrays are used;this guarantees only two copies.2.20 Otherwise,we could perform operations in parallel by cleverly encoding several integersinto one.For instance,if A=001,B=101,C=111,D=100,we could add A and B at thesame time as C and D by adding 00A00C+00B00D.We could extend this to add N pairsof numbers at once in unit cost.2.22 No.If Low=1,High=2,then Mid=1,and the recursive call does not make progress.2.24 No.As in Exercise 2.22,no progress is made.-6-