[转帖]快速排序与概率论_AI.人工智能讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  AI.人工智能讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 2026 | 回复: 0   主题: [转帖]快速排序与概率论        下一篇 
    本主题由 Administrator 于 2019-3-2 21:04:58 移动
weiwei.fu
注册用户
等级:上尉
经验:661
发帖:47
精华:0
注册:2013-12-12
状态:离线
发送短消息息给weiwei.fu 加好友    发送短消息息给weiwei.fu 发消息
发表于: IP:您无权察看 2013-12-17 10:18:16 | [全部帖] [楼主帖] 楼主

原文转自: http://blog.chinaunix.net/uid-26726125-id-3963161.html

看过快排(特指算法导论中的就地分区版快排)多少会有下面几个疑问,本文为你逐一解答

  1. 主元为什么要挑最后一个元素(或者可以这么问,partition函数中i的值为什么要从一个不存在的下标开始)
  2. 在证明快排期望运行时间时,定义集合Z为原始集合排序后的集合有什么目的(Zi being ths ith smallest element )
  3. 在证明快排期望运行时间时,Xij明显不是独立随机变量(假设Xij=1,即第i个跟第j个发生比较了,那就说明两者有一个是主元,进而以后任何一个数都没法与其发生比较,也就是说Xi*或者Xj*恒为0),为什么还能把他们相加,最后用调和级数公式导出了nlogn的时间复杂度

就地分区版快排




点击(此处)折叠或打开

private static int partition(int[] arr, int start, int end){
      int pivot=arr[end];
      int i=start-1;//i不在start..end这个区域内
      int j;
      for(j=start;j<end;j++){//-------------a
            if(arr[j]<pivot){//------------------b
                  int tmp=arr[j];
                  arr[j]=arr[++i];
                  arr[i]=tmp;
            }
      }
      arr[end]=arr[++i];
      arr[i]=pivot;
      return i;
}
private static void quicksort(int[] arr, int start, int end){
      int i;
      if(start<end){
            i=partition(arr,start,end);
            quicksort(arr,start,i-1);
            quicksort(arr,i+1,end);
      }
}


要快速消化上面这段代码只需要明确下面三点即可:

  1. [start,i]这个闭区间内的数是下半区(区间内的数都小于主元,如果此区间为空,则说明还没分离出小于主元的元素,比如说初始化状态)
  2. 当a行代码的j++执行完后,(i,j)这个开区间是上半区(区间内的数都大于主元,如果此区间为空,则说明还没分离出大于主元的元素,比如说初始化状态)
  3. 如果把for循环过程比作经典游戏贪食蛇,则上半区就是那条前进的蛇:b行代码为false代表蛇吞了一个格子,长度加一,为true代表蛇前进一格:通过将蛇的最后一个格子调到前面来,而整体长度未增加

如果你能明白上面三点第一个问题就有解了:i必须从不存在的地址开始(start-1),否则初始化时下半区就有值了,关于为什么挑最后一个元素作为主元,如果你能看懂那个贪食蛇的demo就懂了——谁愿意蛇被截成两段啊-_-,你也可以挑第一个元素作为主元,但算导作者并没有这么做,其中的缘由我还真猜不出来

随机变量指示器求解快排时间复杂度



    求时间复杂度一般都是看for循环会循环多少次,但是快排是个例外,它是看for循环里执行的某行逻辑会发生多少次——j跟主元比较。

    我们可以很明显的看到快排中任何一对元素(假设a,b)最多只能比较一次,因为此轮比较后其中的一元素个会作为主元(假设a)被夹在中间,无缘下一轮partition,进而再也没法与任何元素(当然也包括b),有的人可能会问万一前面的几轮partition过程中a跟b就比较过呢,这个可以用反证法推翻,具体就不详解了

    算法导论中有这么一段原话:

where we are considering whether the comparison takes place at any time during the execution of the algorithm, not just during one iteration or one call of PARTITION


    中文意思是:我们只需要记住a跟b最多只会比较一次即可,至于谁是主元以及a还会不会跟c进行比较不用管,我们考虑的是整个算法的执行过程

    既然a跟b比较这个事件只会有两种结果:不发生or发生且仅有一次,设发生比较为事件X,对其建立随机变量指示器(indicator random variable):令a是原始集合中第i小的元素(即Zi ),b是Zj,定义Zij 为子集{Zi,Zi+1....Zj-1,Zj

}(即大小介于a,b之间的数集合),那么

Xij =I{i跟j发生比较}=

1:i跟j发生比较

0:i跟j未比较

于是整个算法总的比较次数就是上述指示器的和

X=??
Xij.......(第一个西格玛是i=1到n-1,第二个是j=i+1到n)


这个X就是我们要找的的时间复杂度,由期望值的线性性质--和的期望等于期望的和

E(X)=E(??
Xij)=??E(
Xij)=??(1*Pr(i跟j发生比较)+0*Pr(i跟j未比较))=??Pr(i跟j发生比较).........T1.1


不失一般性,我们已经令i是第i小的元素,j是第j小的元素,

定理1.1:如果递增集合Zij 中第一个成为partition函数主元的元素不在两端(设为Zk,i<k<j),则元素ZiZj无法比较,Xij=0

证明:用反证法即可证明,假设ZiZj还能比较,那么两者这这一轮partition过后一定被分到同一个区,假设在上半区,根据快排定义有:Zk<ZiZk<Zj,而集合Zij的递增的性质决定了Zk>Zi

,与假设矛盾,故定理1.1成立

    由定理1.1我们可以很轻易的计算出事件“i跟j发生比较”的概率是多少,那就是Zi或者Zj必须是在整个算法的过程优先于集合Zij 其他任何一个元素选作主元,这样i跟j才不会被分到两个分区里面进而失去比较的可能,而集合Zij

中任何一个元素被优先选为主元都是等可能的,故有

Pr(i跟j发生比较)=2*(1/j-i+1)

同时也回答了文初的问题2,集合Z递增有什么目的,就是为了讨论ZiZj

在一次partition过后的情况而特意设的

E(X)=??2*(1/j-i+1)

令k=j-i

E(X)=??2*(1/k+1)......(第一个西格玛是i=1到n-1,第二个是k=1到n-i)

E(X)<??2*(1/k)......(第一个西格玛是i=1到n-1,第二个是k=1到n)

由调和级数的公式可以消掉第二个西格玛

E(X)=?(lnn+O(1))=nlnn=O(nlgn)


对于文初的问题3,不独立的变量为何还能相加,会不会导致计算结果不准确,对此有两点是可以看到的

  • a跟b比较了,则a跟c等于0的概率会增加,我们并没有强制将它设为0,导致总期望下降的因素被减去了,最终导致求出的总期望偏高,而我们要求的正好是一个上限
  • 期望线性的性质并不要求相加的两个随机变量是独立的,推导T1.1恒成立
该贴由system转至本版2019-3-2 21:04:57



赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论