Chinaunix首页 | 论坛 | 博客
  • 博客访问: 145940
  • 博文数量: 17
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1162
  • 用 户 组: 普通用户
  • 注册时间: 2013-02-20 23:47
个人简介

如果人生是一条隐含马尔科夫模型,那维特比算法告诉我已经偏离最优路线了,但如果起点是现在呢?

文章分类

全部博文(17)

文章存档

2014年(3)

2013年(14)

分类: 大数据

2013-10-25 20:35:08

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

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

就地分区版快排


点击(此处)折叠或打开

  1. private static int partition(int[] arr, int start, int end){
  2.     int pivot=arr[end];
  3.     int i=start-1;//i不在start..end这个区域内
  4.     int j;
  5.     for(j=start;j<end;j++){//-------------a
  6.       if(arr[j]<pivot){//------------------b
  7.         int tmp=arr[j];
  8.         arr[j]=arr[++i];
  9.         arr[i]=tmp;
  10.       }
  11.     }
  12.     arr[end]=arr[++i];
  13.     arr[i]=pivot;
  14.     return i;
  15.   }

  16.   private static void quicksort(int[] arr, int start, int end){
  17.     int i;
  18.     if(start<end){
  19.       i=partition(arr,start,end);
  20.       quicksort(arr,start,i-1);
  21.       quicksort(arr,i+1,end);
  22.     }
  23.   }

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

  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过程中ab就比较过呢,这个可以用反证法推翻,具体就不详解了

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

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

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

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

Xij =I{ij发生比较}=

1:ij发生比较

0ij未比较

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

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

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

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


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


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


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

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

Pr(ij发生比较)=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=1n-1,第二个是k=1n-i

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

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

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

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

  • ab比较了,则ac等于0的概率会增加我们并没有强制将它设为0,导致总期望下降的因素被减去了,最终导致求出的总期望偏高,而我们要求的正好是一个上限
  • 期望线性的性质并不要求相加的两个随机变量是独立的,推导T1.1恒成立


阅读(2809) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册