The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

最长不降子序列的nlogn算法 (转)

所谓“最长不降子序列问题”,就是在一个给定的序列中寻找一个子序列{ai}满足:

                       a1<=a2<=...<an

这个问题在一般教材上,往往会作为动态规划的引例。

即使用如下的状态转移方程进行计算:

                   F[i]=max{F[j]}+1     aj<=ai

但是它的复杂度是O(n^2)的,对于稍大的规模便无法承受。

那么有没有改进的方法呢?答案是肯定的。

----------------------------------------------------------------分割线------------------------------------------------------------------------------------------

我们维护一个数组C[i],这里C[i]表示F值为i的最小数。

不难发现   C[1]<=C[2]<=...<=C[n]

因此我们可以利用C[]通过二分查找确定F[j]的值。

----------------------------------------------------------------分割线------------------------------------------------------------------------------------------

实现如下:

const int N = 1001;

int a[N], C[N], f[N]; // f[i]用于记录a[0...i]的最大长度

int bsearch(const int *C, int size, const int &a)

{

    int l=0, r=size-1;

    while( l <= r )

    {

        int mid = (l+r)/2;

        if( a > C[mid-1] && a <= C[mid] ) return mid; // >&&<= 换为: >= && <

        else if( a < C[mid] ) r = mid-1;

        else l = mid+1;

    }

}

int LIS(const int *a, const int &n){

     int i, j, size = 1;

     C[0] = a[0]; f[0] = 1;

     for( i=1; i < n; ++i ){

          if( a[i] <= C[0] ) j = 0;                 // <= 换为: <

         else if( a[i] >C[size-1] ) j = size++;   // > 换为: >=

         else j = bsearch(C, size, a[i]);

         C[j] = a[i]; f[i] = j+1;

     }

     return size;

}

------------------------------------------------------------------分割线------------------------------------------------------------------------------------------

至此,我们了解了O(nlogn)的算法,它主要是利用了二分查找的方法对朴素的动态规划进行加速、优化,从而达到理想的效率。



转自:http://fqq11679.blog.hexun.com/21632261_d.html

posted on 2009-08-12 18:27 abilitytao 阅读(336) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理