当前位置 博文首页 > 文章内容

    「Wallace 笔记」分治实用 trick:中途相遇法 与 启发式分裂

    作者: 栏目:未分类 时间:2020-07-05 16:04:04

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    启发式分裂 (启发式分治)是 分治算法 中常用的一种基于启发式思想的优化策略。

    启发式分裂大多体现在计算顺序上。本人的初步理解是:通过 合理安排分治中额外计算部分的计算顺序 以达到优化复杂度的目的。

    由于关于启发式分裂的资料较少,因此本文可能存在不够严谨的地方,若有请指出。

    这种东西空讲没什么感觉,就根据几道例题看看吧。

    例题

    Luogu P4755 Beautiful Pair

    小D有个数列 \(\{a_1, a_2, \cdots a_n\}\),当一个数对 \((i,j)(i\le j)\)满足 \(a_i \times a_j \le \max\limits_{i \le k\le j} a_k\) 时,小D认为这个数对是美丽的.请你求出美丽的数对的数量。

    \(1\le a_i\le 10^9, 1\le n\le 10^5\)

    考虑分治算法,对于一个区间 \([l, r]\),先求出这个区间最大值的位置 \(p\),那么我们可以将这段区间分为两个主要的部分 \([l, p), (p, r]\)(位置 \(p\) 单独考虑)。

    数对 \((i, j)\) 完全位于 \([l, p) \text{ or } (p, r]\) 的情况可以递归处理,现在计算 \(i\in [l, p) \And j \in (p, r]\) 的情况。

    不难想到,可以对前半部分扫一遍,然后对于每一个 \(i\) 计算右边部分满足 \(a_i \times a_j \le a_p\)\(j\) 的个数。转化为 \(a_j \le \dfrac{a_p}{a_i}\),发现是求 一个区间内不大于某个值的数的个数。于是可以使用主席树用一个\(\log\) 完成单次统计。


    尝试着分析时间复杂度?不幸的是,如果每次递归中 \(p\) 都在非常后面的位置,那么我们会悲惨的发现复杂度被卡到了 \(O(n^2\log n)\)。于是我们尝试优化。

    可以发现,上面的算法中,如果我们反过来——不扫左边而扫右边,然后用主席树完成对左边的统计,好像也不是不可以。

    所以说扫哪边呢?


    答案是 扫较小的区间。很显然,我们会选择用更加高效的数据结构来应付规模相对较大的问题。

    接下来我们试着证复杂度:

    设扫描的区间(较小的区间)的长度为 \(x\),那么 \(T(n) = T(x) + T(n-x) + O(x\log n)\)

    • 最优情况下,即需要扫描的长度最小(\(x = 1\)):\(T(n) = T(n - 1) + O(\log n) = O(n\log n)\)
    • 最坏情况下,即刚好要扫描一半的当前区间(\(x = \dfrac{n}{2}\)):\(T(n) = 2T(\dfrac{n}{2}) + O(n\log n) = O(n\log^2 n)\)

    因此该算法的复杂度为 \(O(n\log^2 n)\)。于是AC。

    小结

    相信大家对启发式分裂有一定的了解了。

    像上面的例题,我们就是用合理的计算顺序,即到底选哪边暴力,哪边用数据结构统计,优化了复杂度。

    启发式分裂和启发式合并的主要思想很像,都是 “从小到大” 的原则。

    实际上,这样的结论大多数是凭直觉而来,所有某些时候第一感觉于是很重要的。

    中途相遇

    也是一种以改变计算顺序来优化时间的手段,个人认为也属于启发式分裂的范畴。

    中途相遇法的体现一般为:顺序不行,那就直接两边一起上。

    为了更深入地理解这个方法,下面仍然是一个例子。

    UVA 1608 CERC2012 Non-boring sequences

    如果一个序列的任意连续子序列都至少有一个元素唯一,则称这个序列“不无聊”,否则称这个序列“无聊”。给定 \(T\) 个序列 \(a\),长度为 \(n(n\le 10^5)\),求是否“无聊”。

    首先要知道,假如在整个数列中找到了一个位置 \(p\)\(a_p\) 的值在整个数列中是唯一的,由于子段 \(a[1, p-1]\)\(a[p+1, n]\) 都满足条件,那么显然整个数列就满足条件。证明见文末链接。

    根据这个性质我们可以这样分治:先找到一个满足上述条件的 \(p\),然后判断子段 \(a[1, p-1]\)\(a[p+1, n]\) 是否都满足条件即可。若找不到这样的 \(p\),则数列为“无聊”的。


    如何找这样的 \(p\)?如果我们直接从前往后,那么复杂度在最坏情况(\(p\) 总是在当前区间最后的位置)会被卡成 \(O(n^2)\)

    这就需要用 中途相遇 的思想了——两边同时开始向中间找。

    时间复杂度?我们发现这样子的最坏情况是 \(p\) 恰好在中间:\(T(n) = 2T(\dfrac{n}{2}) + O(n) = O(n\log n)\)。假如 \(p\) 在端点周围就更快了:\(T(n) = T(n - 1) + O(1) = O(n)\)

    于是以 \(O(n\log n)\) 的优秀效率 AC 了。

    小结

    中途相遇法在分治中是一种常见的方法。

    假如说在递归的计算中,发现正着做很慢,反着做也慢,此时不妨试试中途相遇,双管齐下。

    相关题目

    后记

    Non-boring sequences 中第一个命题的证明:https://www.cnblogs.com/-Wallace-/p/12874501.html