Question

在快速排序算法中引入随机过程的主要目的是什么？

在快速排序算法中引入随机过程的主要目的是什么？在快速排序算法中引入随机过程的主要目的是什么？
A) 保证算法总能在O(nlgn)时间内结束
B) 改善确定性算法的平均运行时间
C) 避免了算法最坏情况下的发生
D) 改善了确定性算法最坏情形下的平均运行时间

Answer 1

D。
在最坏情况下，快速排序的时间复杂度为O(n^2)；
引入随机过程，在每次划分过程中，主元素是随机选取的，在平均情况下，对输入数组的划分是比较均衡的，从而使得算法的期望运行时间为O(nlgn)。