摘 要: | 列车编组作业中要求将一个任意排列的车列依到站的先后次序重新排列,数学上将其抽象为随机排列的顺序剖分。落表算法是已有的最优算法。本文给出的算法得到与落表算法相同的结果,而对一类随机排列,其时间复杂度低于落表算法。1 落表算法的一些性质 以S(m,n)表示含有几个不同数字,且相邻数字不相同,长为m的所有排列的集合。当m=n时,落表算法的时间复杂度为O(n2)阶。 定理 给定 S(n,n) 随机等可能地取自S(n,n).随机变量X表示求P ()所需要的比较次数,则EX=O(n2),VarX=O(n3). 证明 取 为顺序排列,并且记P(X=k)=P k,当X=k时,若a=1,…
|