試題詳解

 i. The worst-case running time and expected running time are equal to within constant factors for any randomized algorithm. 

ii. Sorting 6 elements with a comparison sort requires at least 10 comparisons in the worst case. 

iii. In Blum, Floyd, Pratt, Rivest, and Tarjan [1973] worst-case linear-time order statistics algorithm, instead of dividing the n elements into groups of 5, dividing them into groups of 3 gives the same linear time complexity.
iv. If a dynamic programming problem satisfies the optimal substructure property, then a locally optimal solution is a globally optimal.
(A)i
(B)i,iii,iv
(C)i,ii；,iv
(D)ii,iv
(E)iii,iv