RMQ问题

417

{% blockquote 百度百科 http://baike.baidu.com/view/1536346.htm RMQ 问题 %}
RMQ ( Range Minimum / Maximum Query )问题是指:
对于长度为 n 的数列 A ,回答若干询问 RMQ(A,i,j) ( i,j<=n ),返回数列 A 中下标在 i , j 里的最小(大)值
也就是说,RMQ 问题是指求区间最值的问题

{% endblockquote %}



显然,最直观的算法是用 O(n) 的时间找到查询范围内的最值,然后输出
当查询的次数 m 非常大时,时间复杂度是 O(n*m)
很可能是一个非常大的数字

于是有了一些其他的查询方法:

  1. 预处理区间
    O(n2) 的时间进行预处理
    分别用 Max[i][j]Min[i][j] 表示 [i,j] 的最值
    预处理时间 O(n2)
    单次查询时间 O(1)
    总时间 O(n2) + m * O(1)
    显然,当 n 比较大时,这种方法并不好

  1. **>线段树<**
    通过二分法,用 O(logn) 的时间建树,再用 O(logn) 的时间查询
    总时间 O(logn) + m * O(logn)
    综合来看时间复杂度能够接受,但是由于需要构建二叉树,因此对内存的占用较大

  1. **>ST算法<**
    将线段分成一个个 [i,i+2k-1] 的区间
    采用动态规划的方法在 O(nlogn) 的时间内预处理
    采用数学方法,在 O(1) 的时间内完成一次查询
    总时间 O(nlogn) + m * O(1)
    综合时间复杂度较低,并且对内存占用也比较小
    是解决RMQ问题的最好方法

发布评论
  • 点击查看/关闭被识别为广告的评论