p********2
发帖数: 17 | 1 Randomized Quicksort Variants：
Regularly, RANDOMIZED QUICKSORT selects a single pivot element uniformly at
random. In this problem you will analyze two possible modifications to this
choice of pivot.
For an integer parameter k>=1, the HYBRID RANDOMIZED QUICKSORT algorithm
uses regular RANDOMIZED QUICKSORT whenever n>K , but uses I NSERTION S ORT
whenever n<=k . Analyze the expected running time of HYBRID RANDOMIZED Q
UICKSORT in terms of n and k .
Argue that this sorting algorithm runs in O(nk+nlog(n/k)) expected time. |
|
