随机选择算法时间复杂度分析

随机选择算法时间复杂度分析

首先提供算法的伪代码：

算法是递归算法
时间复杂度分析思路：计算每一次递归语句所消耗的时间，再求和。

为了分析需要，我们先定义如下的量：

定义状态j：数组长度在[(3/4)^(j+1)n,(3/4)^jn]时，程序处在状态j。
定义Xj: 程序处于状态j时调用的递归次数， 即调用Xj次递归之后程序进入第j+1个状态。
partition的时间复杂度为c* n，其中c为常数，n为数组长度，且一次partition至多遍历数组的两倍长度，即c<=2。

因此，我们可以得到时间复杂度的数学表述：

runtime<=Σ Xj*c *(3/4)^j * n---------------------------------------------------------------（1）

其中c是常数，(3/4)^j * n代表状态j下的数组长度。

于是，问题就转化成了求出Xj。
这里引入期望的概念，用E[]代表期望函数，

E[runtime] <= Σ E[Xj]*c *(3/4)^j * n -------------------------------------------------------（2）

，从上式可以看出，runtime的大小只取决于Xj的大小，所以只将E[]作用于Xj。

言归正传，Xj又是取决于什么呢，答案是每次partition的a的位置：
如果a在1/4arrsize~3/4arrsize时，下一次递归后状态一定会改变。
对于这样的a，我们开心地称之为good pivot！

而当a在0~1/4arrsize 和 3/4arrsize~1arrsize,如果分割方向正确，那么下次递归状态也会改变，但是不能保证一定改变，所以下面关于Xj的式子用“<=”表示。

那么选到good pivot的概率是多大呢？很简单，1/2!
所以我们可以算出Xj的值：

Xj<=1/(0.5)=2----------------------------------------------------------------------(3)

式3代入式2，得到

E[runtime] <= Σ 2*c *(3/4)^j * n

将Σ作用在(3/4)^j上就有

E[runtime] <= 2cn * Σ(3/4)^j

用等比数列求和公式，有

E[runtime] <= 8cn = O(n)

所以，我们得到算法时间复杂度为O(n)

最后

以上就是活泼夏天为你收集整理的随机选择算法时间复杂度分析的全部内容，希望文章能够帮你解决随机选择算法时间复杂度分析所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。