随机选择算法时间复杂度分析
随机选择算法时间复杂度分析首先提供算法的伪代码：算法是递归算法时间复杂度分析思路：计算每一次递归语句所消耗的时间，再求和。为了分析需要，我们先定义如下的量：定义状态j：数组长度在[(3/4)(j+1)n,(3/4)jn]时，程序处在状态j。定义Xj: 程序处于状态j时调用的递归次数， 即调用Xj次递归之后程序进入第j+1个状态。partition的时间复杂度为c* n，其中c为常数，n为数组长度，且一次partition至多遍历数组的两倍长度，即c<=2。因此，我们可以得到时间复杂
