化妆水是怎么用的?# Fashion - 美丽时尚
p*2
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.
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.
