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